[go: up one dir, main page]

TWI398182B - 應用於無線感測器網路之多跳路由演算法 - Google Patents

應用於無線感測器網路之多跳路由演算法 Download PDF

Info

Publication number
TWI398182B
TWI398182B TW098129467A TW98129467A TWI398182B TW I398182 B TWI398182 B TW I398182B TW 098129467 A TW098129467 A TW 098129467A TW 98129467 A TW98129467 A TW 98129467A TW I398182 B TWI398182 B TW I398182B
Authority
TW
Taiwan
Prior art keywords
node
message
nodes
sensing
cluster head
Prior art date
Application number
TW098129467A
Other languages
English (en)
Other versions
TW201110788A (en
Inventor
Joe Air Jiang
Jyh Cherng Shieh
En Cheng Yang
Chwan Lu Tseng
Fu Ming Lu
Kuo Chi Liao
Cheng Long Chuang
Tzu Shiang Lin
Chia Pang Chen
Original Assignee
Univ Nat Taiwan
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Univ Nat Taiwan filed Critical Univ Nat Taiwan
Priority to TW098129467A priority Critical patent/TWI398182B/zh
Priority to US12/690,860 priority patent/US8549174B2/en
Publication of TW201110788A publication Critical patent/TW201110788A/zh
Application granted granted Critical
Publication of TWI398182B publication Critical patent/TWI398182B/zh

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
    • H04W40/32—Connectivity information management, e.g. connectivity discovery or connectivity update for defining a routing cluster membership
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W4/00—Services specially adapted for wireless communication networks; Facilities therefor
    • H04W4/06—Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W4/00—Services specially adapted for wireless communication networks; Facilities therefor
    • H04W4/12—Messaging; Mailboxes; Announcements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W84/00—Network topologies
    • H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W84/00—Network topologies
    • H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
    • H04W84/20—Leader-follower arrangements

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Description

應用於無線感測器網路之多跳路由演算法
本發明是關於一種應用於無線感測器網路之多跳路由演算法，特別是指一種應用於無線感測器網路之以能量及覆蓋率為基礎考量的多跳路由演算法。
無線感測器網路(Wireless Sensor Network,WSN)的概念早已被提出多年。在現代科技的發展下，一個具備無線傳輸能力的感測器，已能夠達到體積小、低成本、且本身具備感應環境與處理資訊的能力。傳統的應用上，乃是將大量的無線感測器散佈在一個區域，使其能夠達到涵蓋大範圍的感測面積，並讓這些無線感測器傳輸收集到的環境資訊回基地站進行彙整與分析。然而受限於感測器本身所需要的能量消耗，以及傳輸距離與信號接收等限制，WSN的應用尚存在許多的困難與障礙。
為了解決這些問題，目前已有習知的技術在探討如何減少感測器的能量損耗並延長使用壽命以提高WSN的使用效益。最早期的研究方法為低能量自適應叢集結構層次(Low-Energy Adaptive Cluster Hierarchy,LEACH)路由協定。
在LEACH的方法中，乃是將WSN區分為好幾個叢集，將每個叢集中的感測器區分好幾個叢集並自每個叢集中找出一個叢集頭(cluster head)，這些叢集內感測器會將資料傳輸至該叢集的叢集頭，而每個叢集的叢集頭再傳輸資料至基地站。這種叢集式的結構，能夠有效減少能量損耗、並延長網路的使用壽命。
此外，更有多種以叢集為基礎的WSN，其有些考量叢集頭的剩餘能量，有些則是找出傳輸最短距離，有些則是以感測資訊為主要考量重點等等。而在LEACH之後，則提出了一種基於LEACH的路由協定，其名為LEACH-Coverage-U。在這個方法中，乃是進一步考量感測器與感測器之間互相重疊的感測範圍，選出與其餘感測器的感測範圍重疊程度最高的，來當做該區域的叢集頭。透過這樣的方式，相較於LEACH將能夠更加的延長網路壽命。
然而，前述的這些方法，在感測範圍上仍存在許多的缺失與感測的盲點。對於像是軍事探查、醫療保健等緊急任務的應用，是不容許任何的失誤產生，故習知的技術明顯的不足。
爰是之故，申請人有鑑於習知技術之缺失，乃經悉心地推論與研究，創作出本發明「應用於無線感測器網路之多跳路由演算法」。
本案之主要目的係提供一種基於百分百網路覆蓋率的多跳路由演算的方法，藉由改善習用方法所造成的缺失與不足，進而儘可能的達到全面性的獲取覆蓋範圍的感測資料，並同時減少能量損耗、延長使用壽命。
根據本發明的構想，提出一種基於百分百網路覆蓋率的多跳路由演算的方法，其步驟包括從複數個節點中尋找一叢集頭；該叢集頭廣播一訊息；當任一節點接收到該訊息時，則繼續廣播該訊息，直到該複數個節點皆接收到該訊息為止；每一節點根據接收的該訊息選擇一父節點；每一節點傳輸其收集的一感測訊息與該訊息至對應的該父節點；以及該叢集頭收集接收自所有該父節點的該感測訊息與該訊息，再傳輸該感測訊息與該訊息至一基地站。
根據上述的構想，其中從複數個節點中尋找一叢集頭時，更包括根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離來計算一第一比重值，以尋找該叢集頭。
根據上述的構想，其中任一覆蓋區為任一節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
根據上述的構想，其中每一節點根據接收的該訊息選擇一父節點時，更包括根據另一節點的剩餘電量以及每一節點與該另一節點的距離來計算一第二比重值，以選擇該父節點。
根據上述的構想，更包括當該複數個節點中仍有具電量的節點時，重複下列步驟：從複數個節點中尋找一叢集頭至該叢集頭收集接收自所有該父節點的該感測訊息與該訊息，再傳輸該感測訊息與該訊息至一基地站。
根據上述的構想，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
根據上述的構想，其中該感測訊息至少包括每一節點感測範圍內的環境訊息與環境變化狀況。
根據上述的構想，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息。
根據本發明的另一構想，提出一種基於百分百網路覆蓋率的感測系統，其包括複數個節點；複數個父節點，其中每一父節點對應至少一節點，並自對應的該節點接收一訊息；一叢集頭，其中該叢集頭自該複數個父節點接收該訊息；以及一基地站，其接收傳輸自該叢集頭的該訊息，其中該感測系統使用一多跳路由演算法，該演算法包括多回合的演算，當每回合進行演算時，根據一第一最大比重值自該複數個節點中得出該叢集頭，並根據一第二最大比重值得出該複數個父節點。
根據上述的構想，其中該第一最大比重值是根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離而被計算。
根據上述的構想，其中任一覆蓋區為任一節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
根據上述的構想，其中每一節點對應至少一候選節點以傳輸該訊息，且該第二最大比重值是根據該候選節點的剩餘電量以及每一節點與該候選節點間的各距離而被計算。
根據上述的構想，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
根據上述的構想，其中該訊息至少包括一感測訊息，其包括每一節點感測範圍內的環境訊息與環境變化狀況。
根據上述的構想，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息。
根據上述的構想，其中當該多跳路由演算法進行完一回合的演算，且該複數個節點中仍有具電量的節點時，則進行再一回合的演算。
根據本發明的又一構想，提出一種基於百分百網路覆蓋率的多跳路由演算的方法，其步驟包括從複數個節點中尋找一叢集頭；以該叢集頭為基礎，對該複數個節點建立複數個層級；該複數個節點根據該層級依序傳輸一訊息；以及該叢集頭接收該訊息後，傳輸該訊息至一基地站。
根據上述的構想，其中從複數個節點中尋找一叢集頭時，更包括根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離來計算一第一比重值，以尋找該叢集頭。
根據上述的構想，其中任一覆蓋區為任一節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
根據上述的構想，其中以該叢集頭為基礎，對該複數個節點建立複數個層級時，更包括根據每一節點與該叢集頭間的各距離使該複數個層級被建立。
根據上述的構想，其中每一節點對應至少一候選節點以傳輸該訊息，且該複數個節點根據該層級依序傳輸一訊息時，更包括根據該候選節點的剩餘電量以及每一節點與該候選節點的距離來計算一第二比重值，以決定每個層級中接收該訊息的節點。
根據上述的構想，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
根據上述的構想，其中該訊息更至少包括一感測訊息，其包括每一節點感測範圍內的環境訊息與環境變化狀況。
根據上述的構想，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息。
根據上述的構想，更包括當該複數個節點中仍有具電量的節點時，重複下列步驟：從複數個節點中尋找一叢集頭至該叢集頭接收該訊息後，傳輸該訊息至一基地站。
本案將可由以下的實施例說明而得到充分了解，使得熟習本技藝之人士可以據以完成之，然本案之實施並非可由下列實施案例而被限制其實施型態。
在此我們定義一特定區域，該特定區域中以隨機的方式佈置多個節點，也就是多個感測器，每個感測器則具有一定的感測能力以及感測範圍。該特定區域中有多個興趣點，該興趣點即為所欲感測的特定點，佈置後每個節點可以知道其本身的感測範圍內存在哪些興趣點。一基地站則可位於該特地區域的外部或內部，以接收每個感測器收集的感測訊息。此外，在此提到的距離，其代表根據節點與節點以及節點與基地站之間訊號傳遞的強弱來決定，意即若節點與節點以及節點與基地站之間，彼此接收或傳送的訊號強，則判定兩者距離近。本案所提出的演算法，是基於在百分之百的無線網路感測覆蓋率之前提下進行，也就是所有興趣點皆被至少一個以上的節點感測範圍所覆蓋。上述的這些設定，以目前的技術來說皆可做到，故在此不加贅述。
請參閱第一圖，其為本案所提出的多跳路由演算法之流程圖。演算法開始時(步驟11)，首先以一種叢集頭選擇機制從所有存活的節點中，也就是仍具有電量、具有感測能力與傳送能力的節點中，選擇一個作為叢集頭(步驟12)。該叢集頭選擇機制是根據一第一比重值H來做選擇。該第一比重值H定義如下：
其中Hi 代表第i個節點(Si )的第一比重值；REi 代表第i個節點的目前剩餘電量；C(Si )代表在第i個節點所具有的感測範圍內，被涵蓋的興趣點的數量；O(Si )代表第i個節點所具有的感測範圍與其餘節點所具有的感測範圍之總和的交集內，被涵蓋的興趣點的數量；BS代表基地站，d(Si ,BS)則代表第i個節點與基地站之間的距離(以訊號傳送或接收強度來決定)。
由上述的定義可知，若REi 越大，則代表第i個節點目前的剩餘電量越多；若O(Si )與C(Si )的比值越接近於1，則代表對於第i個節點來說，其感測範圍下涵蓋的興趣點，和其餘的節點之感測範圍所涵蓋的興趣點重複性越大，甚至完全相同，故該節點的作用性越小；而若d(Si ,BS)值越小，則代表第i個節點與BS之間的距離越近。因此，經由這三個參數可知，若Hi 越大，則該節點可能目前剩餘電量越多、本身作用性小、或是與BS距離相近，故越適合做叢集頭，例如第二圖所示，其為本案的無線感測器網路拓墣示意圖。
透過這個選擇機制找出叢集頭之後，該叢集頭則開始廣播一訊息(步驟13)，該訊息包含叢集頭本身的資訊，例如節點編號、目前剩餘電量等。而接收到該叢集頭發送的該訊息的節點，將可以根據訊號強度而得知與叢集頭之間的距離。接著這些節點則繼續廣播該訊息出去，此時會同時對該訊息進行更新的動作。也就是說，經由這些節點廣播後的訊息，除了包含初始的資訊以外，還會包含這些節點本身的資訊，也就是節點編號、目前剩餘電量、以及與叢集頭的距離等資訊。如此依次接收、廣播並更新下去，直到所有的節點皆接收到該訊息為止。
透過這樣的方式，將得以建立一個層級式的架構，意即由叢集頭開始，依次接收到訊息的節點則分為第一層、第二層等等。故當每個節點接收到該訊息時，亦可同時獲知目前所在的層級，並把這個資訊更新到訊息當中而廣播出去。
接著每個節點將可根據接收到的訊息選擇前一層級中的特定節點來作為一父節點(步驟14)。在這個選擇機制中，單一節點可能為許多節點的父節點，其選擇的依據乃由一第二比重值Φk 而定。該第二比重值Φk 定義如下：
其中Φk 代表第i個節點選擇第k個節點作為父節點的第二比重值；d(Si ,Sk )代表第i個節點與第k個節點間的距離；REk 代表第k個節點的目前剩餘電量。由上述的定義可知，若REk 越大，則代表第k個節點目前的剩餘電量越多，而若d(Si ,BS)值越小，則代表第i個節點與第k個節點之間的距離越近。因此，經由這兩個參數可知，若Φk 越大，則第k個節點可能目前剩餘電量越多或是與第i個節點的距離相近，故越適合被選做父節點。
當整個感測系統中決定叢集頭以及父節點時，每個節點即可開始傳送其收集到的感測訊息至所選擇的父節點(步驟15)。感測訊息包括每個節點感測範圍內的環境訊息與環境變化狀況，且該感測訊息可包括一參數值、一影像訊息以及一聲音訊息的至少其中之一。在這個步驟當中，每個節點亦同時將本身的訊息傳送回去，也就是節點目前的剩餘電量等等資訊。而每個父節點接收到這些感測訊息與子節點本身的訊息後，也會將父節點本身收集到的感測訊息以及自身的訊息再傳送給上一層級的父節點。如此依序傳送回去，當叢集頭收集到所有節點的感測訊息以及所有節點本身的訊息後，則傳送至基地站的系統進行資料的處理與匯總，並完成這一回合的動作(步驟16)。
此時感測系統可以判斷是否仍有存活的節點在該特定區域當中，若仍有存活的節點，則再進行下一回合的演算動作(步驟17)。演算法會重新找出這個回合中最適合做叢集頭的節點以及父節點，接著每個節點同樣依次傳送訊息，最後至基地站匯總，也就是重複步驟12至16的動作。而若該特定區域當中已沒有任何存活的節點時，則結束整個流程(步驟18)。
經由本案所提出的多跳路由演算法，相較於傳統的LEACH以及LEACH-Coverage-U而言，能夠有更長的網路使用壽命。請參閱第三圖(a)以及第三圖(b)，其為本案所提出的演算法相較於傳統的LEACH以及LEACH-Coverage-U的曲線示意圖。
由第三圖(a)可知，在同樣區域的情況下，以100個節點為初始條件對三種演算法進行模擬，本案所提出的演算法明顯能夠大幅度的延長節點的存活時間，大約在第1550個回合時，才開始有節點耗盡能量，並且存活節點數量曲線開始迅速的下降。此外，由第三圖(b)可知，本演算法亦明顯能夠大幅度的延長無線感測器網路維持百分之百覆蓋率的時間。大約在第1590個回合時，感測覆蓋率曲線才開始脫離百分之百的標準，並接著迅速下降。這是因為本演算法能夠有效且平均的分擔使用所有節點的能量，因此更能確保整體的無線感測器網路品質穩定性。
另外，在方程式(1)中，我們更可進一步定義兩係數τ1 、τ2 如下所示：
經由實驗的証明，發現當τ1 =1、τ2 =3.1時，經由方程式(3)所決定的第一比重值將能更佳的延長無線感測器網路的使用壽命與週期。
而在方程式(2)中，亦同樣可定義兩係數λ1 、λ2 如下所示：
同樣的，當λ1 =0.7、λ2 =3.3時，對於延長無線感測器網路的使用壽命，能夠有更好的表現。當然前述對於係數τ1 、τ2 、λ1 、λ2 的數值僅為本案的較佳實施例。不考慮係數的使用或採用其餘的數值也依然可行。
在本實施例中，方程式(1)、(3)對於O(Si )與C(Si )的定義，是考量感測範圍下的興趣點的數量。然而，這裡也可以代表感測範圍下所涵蓋的面積，也就是所涵蓋的某一區域。因此，若O(Si )與C(Si )的比值越接近於1，則代表對於第i個節點來說，其感測範圍下涵蓋的區域，和其餘的節點之感測範圍所涵蓋的區域重複性越大，甚至完全相同，故該節點的作用性則越小，越適合被選為叢集頭。
綜上所述，本案所提出的多跳路由演算法，對於無線感測器網路來說，具有節能、節點能量平均使用、提升網路穩定性、以及延長網路使用壽命等優點。且對於網路感測覆蓋率而言，亦能夠長期維持百分之百的覆蓋率。因此對於特殊情況的應用，像是軍事探查、醫療救援以及居家安全等任務，將能更符合需求，有效的全方位監測到區域內所有角落，以提供使用者完善詳盡的情報與資訊。
本案實為一難得一見、值得珍惜的罕見發明，惟以上所述者，僅為本發明之較佳實施例，當不能以之限定本發明所實施之範圍。即大凡本發明申請專利範圍所作之均等變化與修飾，皆應仍屬於本發明專利涵蓋之範圍。
11．．．開始
12．．．以一種叢集頭選擇機制，從所有存活的節點中，選擇一個作為叢集頭
13．．．該叢集頭廣播一訊息
14．．．每個節點根據接收到的訊息選擇一父節點
15．．．每個節點傳送其收集到的訊息至所選擇的父節點
16．．．當叢集頭收集到所有節點的感測訊息以及所有節點本身的訊息後，則傳送至基地站
17．．．是否有存活的節點
18．．．結束
第一圖：本案的多跳路由演算法之流程圖。
第二圖：本案的無線感測器網路拓墣示意圖。
第三圖(a)：本案所提出的演算法相較於傳統的LEACH以及LEACH-Coverage-U的曲線示意圖。
第三圖(b)：本案所提出的演算法相較於傳統的LEACH以及LEACH-Coverage-U的曲線示意圖。
11．．．開始
12．．．以一種叢集頭選擇機制，從所有存活的節點中，選擇一個作為叢集頭
13．．．該叢集頭廣播一訊息
14．．．每個節點根據接收到的訊息選擇一父節點
15．．．每個節點傳送其收集到的訊息至所選擇的父節點
16．．．當叢集頭收集到所有節點的感測訊息以及所有節點本身的訊息後，則傳送至基地站
17．．．是否有存活的節點
18．．．結束

Claims (22)

  1. 一種基於百分百網路覆蓋率的多跳路由演算的方法，其包括下列步驟：(a)藉由下列子步驟來從複數個節點中尋找一叢集頭；(a1)根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離來計算一第一比重值，以尋找該叢集頭；(b)該叢集頭廣播一訊息；(c)當任一節點接收到該訊息時，則繼續廣播該訊息，直到該複數個節點皆接收到該訊息為止；(d)每一節點根據接收的該訊息選擇一父節點；(e)每一節點傳輸其收集的一感測訊息與該訊息至對應的該父節點；以及(f)該叢集頭收集接收自所有該父節點的該感測訊息與該訊息，再傳輸該感測訊息與該訊息至一基地站。
  2. 如申請專利範圍第1項所述之方法，其中任一覆蓋區為任一節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
  3. 如申請專利範圍第1項所述之方法，其中步驟(d)更包括下列步驟：(d1)根據另一節點的剩餘電量以及每一節點與該另一節點的距離來計算一第二比重值，以選擇該父節點。
  4. 如申請專利範圍第1項所述之方法，更包括下列步驟：(g)當該複數個節點中仍有具電量的節點時，重複步驟(a)-(f)。
  5. 如申請專利範圍第1項所述之方法，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
  6. 如申請專利範圍第1項所述之方法，其中該感測訊息至少包括每一節點感測範圍內的環境訊息與環境變化狀況。
  7. 如申請專利範圍第6項所述之方法，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息。
  8. 一種基於百分百網路覆蓋率的感測系統，其至少包括：複數個節點；複數個父節點，其中每一父節點對應至少一節點，並自對應的該節點接收一訊息；一叢集頭，其中該叢集頭自該複數個父節點接收該訊息；以及一基地站，其接收傳輸自該叢集頭的該訊息，其中該感測系統使用一多跳路由演算法，該演算法包括多回合的演算，當每回合進行演算時，根據一第一最大比重值自該複數個節點中得出該叢集頭，並根據一第二最大比重值得出該複數個父節點，其中該第一最大比重值是根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離而被計算。
  9. 如申請專利範圍第8項所述之感測系統，其中任一覆蓋區為任一節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
  10. 如申請專利範圍第8項所述之感測系統，其中每一節點對應至少一候選節點以傳輸該訊息，且該第二最大比重值是根據該候選 節點的剩餘電量以及每一節點與該候選節點間的各距離而被計算。
  11. 如申請專利範圍第8項所述之感測系統，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
  12. 如申請專利範圍第8項所述之感測系統，其中該訊息更至少包括：一感測訊息，其包括每一節點感測範圍內的環境訊息與環境變化狀況。
  13. 如申請專利範圍第12項所述之感測系統，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息。
  14. 如申請專利範圍第8項所述之感測系統，其中當該多跳路由演算法進行完一回合的演算，且該複數個節點中仍有具電量的節點時，則進行再一回合的演算。
  15. 一種基於百分百網路覆蓋率的多跳路由演算的方法，其包括下列步驟：(a)藉由下列子步驟來從複數個節點中尋找一叢集頭；(a1)根據每一節點的剩餘電量、每一節點的覆蓋區和每一節點與其餘節點的覆蓋區交集的比值、以及每一節點與該基地站之間的各距離來計算一第一比重值，以尋找該叢集頭；(b)以該叢集頭為基礎，對該複數個節點建立複數個層級；(c)該複數個節點根據該層級依序傳輸一訊息；以及(d)該叢集頭接收該訊息後，傳輸該訊息至一基地站。
  16. 如申請專利範圍第15項所述之方法，其中任一覆蓋區為任一 節點的感測範圍，其包括鄰近所欲感測的興趣點的數量，或是鄰近所欲感測的區域面積。
  17. 如申請專利範圍第15項所述之方法，其中步驟(b)更包括下列步驟：(b1)根據每一節點與該叢集頭間的各距離使該複數個層級被建立。
  18. 如申請專利範圍第15項所述之方法，其中每一節點對應至少一候選節點以傳輸該訊息，且步驟(c)更包括下列步驟：(c1)根據該候選節點的剩餘電量以及每一節點與該候選節點的距離來計算一第二比重值，以決定每個層級中接收該訊息的節點。
  19. 如申請專利範圍第15項所述之方法，其中該訊息至少包括傳送該訊息的任一節點與該叢集頭的：編號、目前剩餘電量、所在層級以及與鄰近節點間的距離。
  20. 如申請專利範圍第15項所述之方法，其中該訊息更至少包括：一感測訊息，其包括每一節點感測範圍內的環境訊息與環境變化狀況。
  21. 如申請專利範圍第20項所述之方法，其中該感測訊息至少包括一參數值或一影像訊息或一聲音訊息之一。
  22. 如申請專利範圍第15項所述之方法，更包括下列步驟：(e)當該複數個節點中仍有具電量的節點時，重複步驟(a)-(d)。
TW098129467A 2009-09-01 2009-09-01 應用於無線感測器網路之多跳路由演算法 TWI398182B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
TW098129467A TWI398182B (zh) 2009-09-01 2009-09-01 應用於無線感測器網路之多跳路由演算法
US12/690,860 US8549174B2 (en) 2009-09-01 2010-01-20 Routing method for network and sensing system

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW098129467A TWI398182B (zh) 2009-09-01 2009-09-01 應用於無線感測器網路之多跳路由演算法

Publications (2)

Publication Number Publication Date
TW201110788A TW201110788A (en) 2011-03-16
TWI398182B true TWI398182B (zh) 2013-06-01

Family

ID=43626503

Family Applications (1)

Application Number Title Priority Date Filing Date
TW098129467A TWI398182B (zh) 2009-09-01 2009-09-01 應用於無線感測器網路之多跳路由演算法

Country Status (2)

Country Link
US (1) US8549174B2 (zh)
TW (1) TWI398182B (zh)

Families Citing this family (28)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8849926B2 (en) * 2010-08-06 2014-09-30 Simon Fraser University System and method for self-calibrating, self-organizing and localizing sensors in wireless sensor networks
US8634329B2 (en) * 2011-01-31 2014-01-21 Alcatel Lucent Method for improved topology mapping in wireless communication networks
WO2012139288A1 (en) 2011-04-13 2012-10-18 Renesas Mobile Corporation Sensor network information collection via mobile gateway
CN102158927A (zh) * 2011-05-20 2011-08-17 北京邮电大学 一种高能效的无线传感器网络非均匀分簇路由方法
CN102244892B (zh) * 2011-07-04 2013-12-11 南京邮电大学 一种基于免疫算法的移动传感网分簇方法
CN102625407A (zh) * 2012-01-13 2012-08-01 燕山大学 小区无线抄表系统和小区无线抄表路由构建方法
CN103269500B (zh) * 2013-04-19 2016-01-06 西安电子科技大学 基于平均负载和能量均衡的无线传感器网络簇内通信方法
CN104640056B (zh) * 2013-11-07 2021-08-17 中兴通讯股份有限公司 一种控制节点选取及分配资源的方法和装置
CN104065574A (zh) * 2014-07-09 2014-09-24 哈尔滨工程大学 一种无线传感器网络层内非均匀分簇路由方法
CN104320796A (zh) * 2014-10-28 2015-01-28 河海大学常州校区 基于leach协议的无线传感器网络数据传输方法
MY177521A (en) * 2014-11-04 2020-09-17 Mimos Berhad A system and method for next hop selection in a wireless sensor network
US10243832B2 (en) 2014-12-23 2019-03-26 Industrial Technology Research Institute Routing message delivery method applicable to network node and network node using the same and communication network using the same
US10244542B2 (en) * 2016-02-03 2019-03-26 Microsoft Technology Licensing, Llc Mobile communication device clustering
CN106231648B (zh) * 2016-08-02 2019-06-07 南方科技大学 控制方法和控制装置
CN106255038B (zh) * 2016-08-04 2019-10-08 南京邮电大学 一种无线传感器网络安全数据融合方法
CN106332249B (zh) 2016-08-22 2020-04-21 南方科技大学 控制方法和控制装置
CN106375964B (zh) * 2016-08-31 2019-05-07 北京千安哲信息技术有限公司 一种体域网中的节点及簇头节点的选择方法
CN108738029B (zh) * 2017-04-14 2021-06-11 桂林电子科技大学 无线传感器网络中参考节点的移动路径动态规划方法
CN108366126A (zh) * 2018-03-03 2018-08-03 深圳大图科创技术开发有限公司 一种基于wsn技术的病虫害监测预警系统
CN108430048A (zh) * 2018-03-03 2018-08-21 深圳万发创新进出口贸易有限公司 一种基于wsn技术的酒厂储酒罐温度监测系统
CN108848476A (zh) * 2018-06-21 2018-11-20 河南科技大学 传感器网络中基于通信距离控制的高能效数据汇聚算法
CN108827387B (zh) * 2018-07-03 2019-10-29 怀来斯达铭数据有限公司 机械设备智能实时监测系统
CN112135328B (zh) * 2019-06-04 2022-08-26 快住智能科技（苏州）有限公司 基于物联网的人工智能监测系统
CN110602757B (zh) * 2019-09-18 2023-05-12 上海海事大学 基于自适应遗传算法的无线传感器网络分簇路由方法
CN110557799B (zh) * 2019-09-26 2020-06-09 中南大学 一种智慧城市边缘网络中基于移动车辆的数据采集方法
CN111885507B (zh) * 2020-06-19 2022-01-04 国网湖南省电力有限公司供电服务中心（计量中心） 一种双介质融合通信网络的感知方法
CN112188584B (zh) * 2020-09-16 2022-09-16 中山火炬职业技术学院 基于重心法的无线传感器网络多跳分簇方法和系统
CN114827933A (zh) * 2022-04-14 2022-07-29 黑龙江大学 面向无线传感器网络的多路径路由方法

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030151513A1 (en) * 2002-01-10 2003-08-14 Falk Herrmann Self-organizing hierarchical wireless network for surveillance and control
US20040018839A1 (en) * 2002-06-06 2004-01-29 Oleg Andric Protocol and structure for mobile nodes in a self-organizing communication network
US20070047510A1 (en) * 2005-08-31 2007-03-01 Samsung Electronics Co., Ltd. Beacon scheduling method in multi-hop ad-hoc networks
TW200908610A (en) * 2007-08-14 2009-02-16 Univ Nat Pingtung Sci & Tech Constructing method for information transmitting model in wireless sensor network

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7184421B1 (en) * 2001-12-21 2007-02-27 Itt Manufacturing Enterprises, Inc. Method and apparatus for on demand multicast and unicast using controlled flood multicast communications
US7281057B2 (en) * 2002-04-29 2007-10-09 Harris Corporation Hierarchical mobile ad-hoc network and methods for performing reactive routing therein
US7475158B2 (en) * 2004-05-28 2009-01-06 International Business Machines Corporation Method for enabling a wireless sensor network by mote communication
FI118291B (fi) * 2004-12-22 2007-09-14 Timo D Haemaelaeinen Energiatehokas langaton anturiverkko, solmulaitteita sitä varten sekä menetelmä tietoliikenteen järjestämiseksi langattomassa anturiverkossa
US7385503B1 (en) * 2006-08-03 2008-06-10 Rosemount, Inc. Self powered son device network
KR100972081B1 (ko) * 2008-09-24 2010-07-22 주식회사 케이티 무선노드의 이동성을 지원하는 위치인식 메시징 방법

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030151513A1 (en) * 2002-01-10 2003-08-14 Falk Herrmann Self-organizing hierarchical wireless network for surveillance and control
US20040018839A1 (en) * 2002-06-06 2004-01-29 Oleg Andric Protocol and structure for mobile nodes in a self-organizing communication network
US20070047510A1 (en) * 2005-08-31 2007-03-01 Samsung Electronics Co., Ltd. Beacon scheduling method in multi-hop ad-hoc networks
TW200908610A (en) * 2007-08-14 2009-02-16 Univ Nat Pingtung Sci & Tech Constructing method for information transmitting model in wireless sensor network

Also Published As

Publication number Publication date
US8549174B2 (en) 2013-10-01
US20110055424A1 (en) 2011-03-03
TW201110788A (en) 2011-03-16

Similar Documents

Publication Publication Date Title
TWI398182B (zh) 應用於無線感測器網路之多跳路由演算法
Palan et al. Low energy adaptive clustering hierarchy (LEACH) protocol: A retrospective analysis
CN104038965B (zh) 一种高效利用能源的移动无线传感网机会路由方法
Aslam et al. A multi-criterion optimization technique for energy efficient cluster formation in wireless sensor networks
CN106604346B (zh) 无线传感器网络能量有效机会路由的实现方法
CN101013926B (zh) 一种无线传感器网络通信方法和系统
CN103249108B (zh) 基于非均匀分簇的无线传感器网络能耗均衡路由方法
CN103052147B (zh) 一种基于无线传感网的能量有效性多级环形组网的方法
CN102014455B (zh) 一种基于节点间相关性的无线传感器网络分簇路由方法
Yu et al. An energy-efficient chain-based routing protocol in wireless sensor network
CN104602313A (zh) 一种海上搜救无线传感网的环境自适应路由方法
ECE A survey on energy efficient routing in wireless sensor networks
CN100373886C (zh) 基于自适应退避策略的无线传感器网络分布式分簇方法
Sengul et al. A survey of adaptive services to cope with dynamics in wireless self-organizing networks
CN104168631A (zh) 无线传感器网络能耗均衡覆盖调度及路由跨层设计方法
Jerbi et al. A novel clustering algorithm for coverage a large scale in WSN
Sun et al. Study on the Wireless Sensor Network Monitoring System Based on ZigBee Technology and Optimization Algorithm Simulation
Zytoune et al. Stochastic low energy adaptive clustering hierarchy
John et al. Brain Storm water optimisation-driven secure multicast routing and route maintenance in IoT
Kumar et al. An energy-aware and intelligent cluster-based event detection scheme in wireless sensor networks
CN105323817A (zh) 异构传感器网络中基于簇树拓扑结构的tdma调度方法
Lu et al. Hierarchical ring-based data gathering for dense wireless sensor networks
Khedo et al. Misense hierarchical cluster based routing algorithm (MiCRA) for wireless sensor networks
Tan et al. HCEP: a hybrid cluster-based energy-efficient protocol for wireless sensor networks
Jing et al. A cluster-based multipath delivery scheme for wireless sensor networks

Legal Events

Date Code Title Description
MM4A Annulment or lapse of patent due to non-payment of fees