低能耗節點位置未知無線傳感器網絡控制方案



摘 要：介紹了一種低能耗節點位置未知的網絡控制方案，根據不同的網絡運行輪數設定網絡節點的通信半徑，使網絡具有良好的能量有效性。網絡中基站經過構建階段的啟動過程、節點信息收集過程和節點信息上報過程，獲得了整個網絡節點的相對位置分布，然后整合節點節點信息支路，得到具有回路鏈接的簇首節點集，其他節點根據自己鄰居信息選擇簇首節點，實現網絡近似最小能耗拓撲的構建。通過仿真與同類典型算法LEACHC、MCLB進行比較，結果顯示該方案應用于網絡運行時具有更長的網絡生命周期、更少的信息總數和更低的網絡構建代價。

關鍵詞：無線傳感器網絡； 低能耗； 節點位置未知； 能量有效性

0 引 言

無線傳感器網絡是由一個基站和大量的傳感節點構成。傳感節點通常被隨機放置在監測區域內，基站負責指導傳感節點工作并且收集傳感節點檢測到的信息，并將環境信息報送至監控中心。通常，傳感節點體積很小且具有感知周圍環境信息、數據處理與存儲和無線數據收發三個基本功能[1]。無線傳感節點在應用時受到很多限制如處理速度慢、存儲容量小、電能有限等，而基站具有外部電源支持，處理能力比傳感節點強大很多，它負責收集傳感節點的監測信息并轉發給用戶。由于無線傳感節點的能量有限性，降低能量消耗、延長網絡生命周期，成為無線傳感器網絡通信協議設計的首要目標。

分簇算法應用于無線傳感器網絡通信協議設計，被認為是一種減少網絡能量消耗的有效辦法[23]。它通過選擇一部分傳感節點作為簇首節點形成一個暫時固定的網絡構架，各簇首節點接收鄰居簇首節點、簇內節點感知的環境信息，進行數據融合，剔除冗余信息，并轉發至基站[46]。這一類的經典算法有：文獻[7]LEACHC是一種集中的聚類算法。在啟動階段，基站接收網絡中所有節點發送來的包含他們位置以及能量狀態的信息。基站運行本地算法獲得簇首以及分簇表，然后廣播包含簇首ID信息給每一個節點。簇頭確定后，普通節點選擇離其最近的簇頭加入該簇頭所管轄的區域，進而形成簇區域。協議維護階段與LEACH是一致的。簇的建立過程在每一輪里都需要進行一次，從而產生了很多的能量消耗和傳輸延遲。文獻[4]MCLB算法首先找出網絡中的冗余節點作為臨時簇頭，并隨機選擇一定數量的具有高的剩余能量的節點為簇頭，臨時簇頭和簇頭構成了一個數據轉發層，而其他節點構成了一個數據收集為主要功能的底層，簇頭廣播hello消息并找到屬于本簇的節點從而完成對網絡的分簇。在數據轉發上，存在節點節點、節點簇頭和簇頭簇頭多跳轉發至基站的混合模式，該算法中由于簇頭的位置具有隨機性，為了保證數據轉發的可靠連通，因此每個節點必須以較大的發射功率進行數據轉發而產生了不必要的能量浪費。文獻[8]提出的算法CDC將網絡進行分簇，每一簇自行選擇一個簇頭。簇頭承擔起收集簇內成員信息并進行數據融合，然后再將數據轉發給基站，并且依據信息選擇下一輪的簇頭。一旦簇內有節點死亡，簇首將發送信息給基站，對整個網絡進行重新分簇，否則簇首選擇能量最多的節點作為下一輪的簇首。

本文提出一種新的網絡控制方案由網絡構建階段和網絡維護階段組成。在網絡構建階段本文借鑒了文獻[9]的思想，設計了一種節約能耗的構建方法，首先由基站發出拓撲構建信息，每個節點完成對父節點和鄰居節點信息的收集并將信息在特定的時刻傳輸給自己的父節點，基站通過獲得的全網節點信息選擇一部分具有冗余連接的簇頭節點集，完成了一種期望的網絡拓撲特性并保證了網絡的連通性。一旦網絡構建完成，就進入網絡維護階段，在該階段每個節點根據網絡的需要轉換到特定的角色，當簇頭節點集中的一節點能量下降到一定值時，由它提出網絡重構，網絡運行的兩個階段狀態交替進行直到網絡不能正常運行。本文設計的網絡控制方案與文獻[7]LEACHC算法和文獻[4]的MCLB算法進行仿真比較網絡的生命期、網絡構建信息交替情況和網絡的構建代價。結果顯示本文提出的方案應用于網絡運行時具更長的生命周期、更少的構建階段信息總數和更低的網絡構建代價。

1 系統模型

在本算法中，傳感節點周期性的充當簇頭節點或者普通節點，進行環境監測及數據轉發。無線傳感器網絡監測區域內隨機均勻放置N個傳感節點，其中有一個節點為基站，在本文所提出的控制方案中，進行了以下幾點假設：

（1） 每個傳感節點被賦于一個惟一的標號，傳感節點的能量有限，而基站有專門的供電系統。

（2） 每個傳感節點可根據需要調整自己的發射功率，最大發射功率滿足它們連接網絡中離它最遠的傳感節點。

（3） 所有傳感節點的位置不會發生移動，位置未知，具備通過接收信號的衰減程度來計算與信號發送方的距離。

2 LEPN網絡控制方案

LEPN控制方案下的網絡運行是基于輪的，每輪包含網絡構建和網絡維持兩大階段。在每一輪里，由基站定義各節點以一個特定的相同發射功率進行數據轉發，構建一個基于UDG（Unit Disk Graph）模型的分簇網絡來感知周圍環境信息并將信息可靠的由簇頭簇頭多跳轉發至基站的過程，本方案主要針對應用在任務艱巨、節點隨機布置的一些場合，因此設計時需滿足兩個基本的約束條件：形成的簇頭節點集可提供一個可靠的數據包多跳轉發能力；本方案具備的能量有效性應該和現有的基于分簇的網絡控制方案相當或者更好。為了滿足這些約束，LEPN網絡控制方案所確定的簇頭最終形成一條連通的閉合回路保證信息成功多跳轉發至基站，具有可靠性和能量有效性，因為基站節點獲得信息轉發路徑是閉合回路，具備的冗余性以防止信號在傳輸過程由于鏈接失敗而造成信息傳輸失敗；而該方案的另一個優點是不需要節點的位置和方向信息，從而節約了節點的硬件成本投入。

2.1 LEPN網絡構建階段

每一輪的LEPN網絡構建階段分為四個子過程，首先由基站設定本輪節點通信的發射功率，發起網絡構建，接下來各個節點根據接收信號的衰減程度判斷與信號發送者的距離以完成信息的收集，當每個節點都完成信息的收集，就進入了信息上報過程，直至基站，基站根據接收到的信息情況選擇簇頭節點集，再將包含簇頭節點的消息逐層傳遞給網絡中的每一個節點，節點通過接收到的信息來判斷自己在接下來的幾輪里是否成為回路中的簇頭節點以承擔環境信息監測和數據轉發的任務還是普通簇頭節點融合本簇內的監測數據再轉發，或者普通節點。用（如圖1）一個13節點的網絡構建過程來簡單描述（粗實線表示可以構成父子關系的簇首鏈接，細實線表示構成鄰居關系的簇首鏈接，虛線表示構成簇首與簇內成員的鏈接）。

2.1.1 基站啟動過程

當無線傳感器網絡剛剛布置完畢或者基站接收到某節點請求網絡重構的消息，并且基站中保存的簇頭節點集已經使用完畢（若基站中尚有未使用的簇頭節點集，那么網絡構建階段直接進入網絡拓撲構建過程，這樣有效的減少了網絡構建代價），基站進入了啟動過程，首先它根據網絡已運行的輪數設定下一輪各節點通信所采用的發射功率，基站節點以該發射功率廣播hello消息（HM）并啟動一個定時器1以等待它的子節點發來的HM，一幀完整的HM包含父節點標號、本節點標號、發射功率值、本節點的剩余能量以及充當簇頭的最低剩余能量值，基站發出的HM里父節點的內容為基站本身的標號。見圖1（a），節點B，C，E，I，J，K，L，M接收到了基站A發來的HM。

2.1.2 節點信息收集過程

一旦節點接收到HM，就表明網絡構建階段到了節點信息收集過程，如圖1（a）中，節點B，C，E，I，J，K，L，M接收到一個HM，就開始判斷本節點與HM發送者之間的相對距離，如果該距離小于本輪通信距離的一半（R/2），則認定該HM發送者為自己的簇首節點，如節點I，K，L認定A為它們的簇首，于是它們向A發送一幀簇首確認消息，就進入了睡眠狀態，關閉發射模塊，等待網絡的維持階段到來再轉換到數據監測狀態。離A較遠（相對距離大于R/2）的節點M，B，J，E，C，如果節點的剩余能量足夠充當簇首節點的，則廣播一幀包含本節點剩余能量信息的競爭簇首消息（CM）并啟動一個定時器2（定時時間小于定時器1），定時器2到達后，各節點對R/2范圍內的節點信息進行判斷，如果得知本節點能量最大，則設定自己為簇首節點并成為A的子節點，然后廣播發送HM，如M，J，E，D，A將接收到B節點的HM，M，J認定B為簇首，見圖1（b），而A接收到B節點得知B為自己的子節點；節點C在定時器2結束后，發現R/2范圍內無其他節點與之競爭，也設自己為簇首節點并認A為父節點發送HM；假使J也在E的R/2范圍內，且能量高于E節點，E接收不到J的HM，卻接收到其他父節點為A節點的HM（如B，C）時，E節點認定自己為簇首節點，并發送HM消息，此時BE，EC之間接收到HM消息，即認定相互之間為簇首間的鄰居成員并計算存儲他們之間的相對距離與鄰居節點的剩余能量，見圖1（c）；如果某節點的能量太小，不足以充當簇首節點，那么，它會選擇離自己較近的一個簇首節點，加入該簇。某節點一旦有了父節點，就認定該節點處于被覆蓋狀態。而且當一個節點有了子節點，那么它就進入了活躍狀態，開始等待信息上報過程的到來。按照這種方式，所有的節點都接收到HM消息，但是如圖1（d）所示，節點G，F，H，C廣播HM后，在設定的定時器1時間到達內未接收到任何認定它們為父節點的HM，因此它們認為信息收集過程結束，并由它們發起進入信息上報過程。

2.1.3 節點信息上報過程

在節點信息上報過程中，只有充當父子關系的節點，同時，也是扮演簇首角色的節點，發送它的鄰居序列給自己的父節點。在本例中，完成信息收集過程后，A，B，C，D，E，F，G，H成為簇首成員。簇首F是G的鄰居。因此，簇首G發送{FG}以及FG的相對距離的消息給它的父節點D。這些節點的組合方式為構成一定性質的簇頭簇頭鏈接的提供了可靠的信息，每個父節點都在等待著它的所有子節點發來的上報消息，再添加自己的信息，發送給自己的父節點。如簇首節點D接收到它的子簇頭節點G發送來的消息后，它就發送有{FGD}，{FD}，{ED}路徑信息給節點B，依次進行信息傳遞，最終的信息將匯聚至基站。當基站節點接收到所有子節點發來的上報信息，則網絡構建進入了下一過程。在信息上報過程中，節點發送完上報消息后就進入睡眠狀態，關閉發射模塊以保存能量。

2.1.4 網絡拓撲構建過程

網絡拓撲構建過程在基站節點上進行，當基站A接收到所有子簇頭節點（BCE）發送來的上報信息，就開始對支路進行整合，如果兩條數據通路有共同的節點，如{ABDF}和{AEFD}兩條支路有兩個共同的節點A，F，那么可以組合出一個具有閉合回路的數據通道ABDFEA，對于不同的回路也根據判斷是否有共同節點而對它們進行整合成更大的閉合回路。一旦基站完成選擇多個構成回路的簇頭集，它開始為其他簇頭節點以盡少的步數連接到某一回路簇頭節點，在基站A處，將形成多個具有回路性質的簇頭簇頭節點集，基站將選擇其中一個簇頭集信息廣播給網絡中的每一個節點。網絡中的節點通過判斷基站的廣播信息（簇頭簇頭之間數據轉發的路由信息），決定自己是充當回路簇頭或支路簇頭節點進行數據收集、融合、轉發，或者充當普通簇內節點實現對周圍環境的監測。至此進入了網絡維持階段。

2.2 LEPN網絡維持階段

網絡維持階段，簇頭將根據簇內的節點數目為每個簇內節點分配TDMA時間表。簇內節點持續采集周圍環境信息，并在自己的通信時隙內以單跳通信的方式將數據傳送給相應的簇頭。為了有效節約節點能耗，普通節點的發送器在不屬于自己通信的時隙進入睡眠狀態；而簇頭必須使自己的接收器時刻處于開啟狀態，以便接收簇內節點發送過來的所有數據。簇頭節點接收到簇內所有的數據后，將對數據進行必要的數據融合處理，然后根據路由信息將數據經簇頭簇頭多跳傳輸至基站。

3 仿真實驗

無線傳感節點的能量有限性決定節點能量的高效使用是網絡控制設計的首要目標，也是延長網絡生命周期的一種有效手段。本文仿真設定在30 km×30 km的監測區域內，將200個節點隨機分布，節點的通信半徑在5～45 km內可調。為了便于計算節點收發信息的能量消耗，使用文獻[7]所描述的無線通信模型：