帶有能量補給的異構無線傳感器網絡拓撲控制算法

馬晨明 ，王萬良 ，洪 榛 ，姚信威

（1.浙江工業大學信息工程學院 杭州 310023；2.浙江工業大學計算機科學與技術學院 杭州 310023；3.浙江理工大學機械與自動控制學院 杭州 310018）

1 引言

無線傳感器網絡作為物聯網底層的重要組成部分，已經受到了國內外的廣泛關注[1]。受到成本和體積的限制，傳感器節點的能量一直是值得高度關注的問題。拓撲控制[2]是無線傳感器網絡中節約能量、增加運行時間的關鍵技術，可以均衡網絡的能耗，最終達到延長網絡生命時間的目的。拓撲控制主要由拓撲構建和拓撲維護[3]組成，拓撲構建用于優化網絡的拓撲結構，減少節點之間的通信干擾；拓撲維護是恢復、輪換、再生成拓撲的過程，節點在拓撲構建后將啟動拓撲維護以保障網絡的有效運行。

LBCDS[4]是一種集中式的拓撲構建算法，由某個節點對全局網絡拓撲信息進行搜集，然后再開始運行具體算法。算法首先計算網絡的平均節點度，然后采用貪心的思想依次選擇節點度最接近于平均節點度的節點作為活躍節點直到網絡完全連通。但是，該算法需要較長的計算時間，同時也沒有考慮節點的剩余能量的影響。

MIP-MCDS[5]和 NMIP-MCDS[6]采用令牌流對拓撲構建問題進行數學建模，以最小化網絡分發的令牌作為目標函數，求解完畢后，各個持有令牌的節點組成最小連通支配集。但是，該類算法需要獲得全網的拓撲結構信息，因此存在計算復雜度高、求解速度慢等問題。

EBCDS[7]是一種分布式拓撲構建算法，可以應用在節點比較密集的環境中。首先選擇能量水平和節點度均較大的節點構造最大獨立集，然后啟動一個超時搜集三跳內的路徑消息，超時結束后由ID較小的節點選擇較優的路徑連通。但是，EBCDS將三跳鄰域中所有節點均進行了連通，導致產生的連通支配集規模較大，同時算法的消息復雜度也較高。

以上文獻關注如何構建高效的網絡拓撲，而參考文獻[8]指出選擇合適的拓撲維護策略將大大增加網絡的生命時間。參考文獻[9]提出的拓撲維護方法以最小能量為目標簡化網絡拓撲，當節點發現它的鄰居節點出現故障后，它會重新運行拓撲構建算法以連通網絡。參考文獻[10]采用的是基于時間的拓撲維護策略，即定期觸發拓撲維護以平衡節點的能耗。參考文獻[11]對每個簇進行單獨維護，當簇頭的剩余能量低于簇內平均剩余能量時，需要選舉新的簇頭。算法要求保證新簇頭和原簇頭之間的距離小于k×d0/n，同時還需要簇頭滿足剩余能量大于簇內成員的平均能量。假設網絡不存在這樣的節點，原簇頭會一直運行，直到能量耗盡。

以上算法針對拓撲構建或拓撲維護單獨進行研究，而沒有將兩個過程很好地進行結合，同時以上算法均假設網絡節點性能完全相同，沒有考慮到可能存在不同計算、通信半徑或能量水平的節點，這在實際研究中是缺乏應用價值的。參考文獻[12]將拓撲構建和拓撲維護進行結合，同時考慮了節點通信半徑異構的問題，算法在初始時采用了兩輪消息交換的方式獲得鄰居節點信息，但是在通信開銷上仍然可以進一步優化。隨著節點能量采集技術的完善，節點已經可以將周圍環境中的太陽光照、熱力溫差、機械振動、氣流和壓力變化等能源持續不斷地轉化為可用的電能[13]，這對延長網絡的生命時間起到了重要的作用。

為了考慮節點能量采集技術對拓撲控制算法產生的影響，同時進一步降低當前算法的通信開銷并優化網絡的生命時間，本文在節點的通信半徑和能量水平存在異構的無線傳感器網絡模型中，提出了一種同時包含拓撲構建和拓撲維護過程的異構無線傳感器網絡拓撲控制算法(HELM)。算法首先運行拓撲構建過程，以較小的通信開銷生成連通支配集，然后利用鄰域節點信息并結合時間、能量和故障的觸發條件，提出了一種由sink節點執行決策的拓撲維護算法，進一步優化了A3M[12]算法在拓撲構建和拓撲維護過程中的能耗，并最大限度地延長網絡的運行時間。

2 系統模型

2.1 網絡模型

用圖G(V,E)表示該網絡模型，其中，V是節點集合，E是由V中節點組成的通信鏈路集合，假設：

·N個節點隨機部署在M×M的區域中；

·sink節點位于中心（M/2，M/2），且計算、存儲和能量均不受限制；

·為了能夠更好地控制成本，網絡由小部分高級節點和大部分普通節點組成，高級節點具有能量采集能力，而普通節點只含有有限的電池能量。節點通過ID進行唯一標識，不需要配備GPS獲得位置信息；

·節點可以通過接收信息的信號強度RSSI獲得鄰居節點之間的距離d；

·假設所有節點的通信半徑R∈[Rmin,Rmax]，則節點vi和vj之間存在通信鏈路 （當且僅當vi和vj相互處于對方的通信半徑內）；

·初始網絡拓撲為全連通圖。

2.2 能量補給模型

目前，傳感器節點的能量采集類型以太陽能和振動能為主，其中，太陽能的功率密度為10～15 mW/cm3，振動能功率密度約為0.275 mW/cm3。考慮到太陽能受到夜晚無光照的限制，本文研究內容以振動能為主，采用與參考文獻[14]相同的振動能源能量補給模型，假設振動中心獲得的振動能量最大，所有節點獲得的能量與振動中心的距離成反比，這樣不同位置由于機械振動強度不同，則所獲得的能量補給大小也不同。

3 拓撲構建

在通信半徑相同的網絡中，當節點u收到鄰居節點v的消息后，可以確定u、v處于同一通信半徑內。當節點的通信半徑存在異構時，參考文獻[12]采用兩輪消息交換的方式以獲得鄰居節點信息，但是這會增加通信開銷。通過比較節點之間的距離與通信半徑，只需要一次信息交換就能確定節點之間是否可以通信。假設節點u收到了v發送的hello消息，通過信號強度RSSI可以獲得u、v之間的距離 d（u,v），然后和通信半徑 Ru進行比較，如果 Ru≥d（u,v）就可以確定節點之間可以通信，這樣就確定了網絡中的鄰居節點集合。

下面對算法的相關術語進行描述。

·節點的顏色：白色，初始狀態；紅色，中間狀態；黑色，活躍節點；灰色，普通節點。

·N1:節點的鄰居節點集合。

·Hop:節點距離sink節點的跳數。

·E、Emax:分別表示節點的當前剩余能量和最大初始能量。

·R、Rmax:分別表示節點的通信半徑和網絡中最大節點的通信半徑。

·權值w1:支配節點不僅需要較高的剩余能量，還要考慮節點的能量采集能力，另外優先選擇通信半徑大、節點之間距離遠的節點，這樣可以減少支配集的規模，∑Eharvest(u)表示節點從上次成為活躍節點后到當前時間所采集的能量之和。

·competition(ID,E,Hop,First)消息:First表示最早收到的發送節點ID。

算法的主要思想是權值最大的節點會最先廣播competition消息而成為活躍節點。初始時，sink廣播competition消息而變成紅色，然后等待時間T1確定自己能否成為活躍節點。節點v收到消息后，先確認是否鄰居節點，如果發現自己的Hop屬性還沒有初始化或小于當前Hop+1，則進行更新，然后將鄰居節點信息存儲到N1。如果當前節點是白色，啟動與w1成反比的定時器T2。時間T2內，節點收到滿足連通性的消息時，則對N1進行更新。當T2結束，當前節點v設置First并廣播一個competition消息。如果在時間T1內，上層的紅色鄰居節點u收到了該消息，發現First==IDu，則當前節點成為黑色節點，否則查看First對應的ID是否在N1中，如果存在，則將它的顏色標記為黑色。時間T1結束后，如果當前節點仍然沒有收到First==IDu的消息，則當前節點變成灰色節點。

圖1給出了HELM算法的一個運行實例。初始時，節點 S廣播 competition消息，節點 A、B、C、D、E、F 處于 S的通信半徑內，將能收到S的消息，B不是S的鄰居節點，這是因為節點B的通信半徑RB

4 拓撲維護

本節提出了一種面向時間、能量、故障觸發機制的混合型拓撲維護算法。算法結合靜態和動態拓撲維護的優點，根據當前網絡狀況選擇局部或全局拓撲修復策略，以達到最小化網絡能耗的目的。局部拓撲修復是在能量不足或失效的節點鄰域內生成替代節點，可快速恢復網絡，所需要的時延和能耗也較少；全局拓撲修復需要對全網進行重構，這樣會消耗過多的能量而影響網絡的生命。拓撲維護過程描述如下。

圖1 拓撲構建算法的運行實例

在拓撲構建結束后，節點首先會對鄰居節點計算權值w2，然后按照w2的大小進行排序，得到有關節點的ID、顏色和w2的列表FList。w2計算如式(2)，這里考慮節點之間的距離越近，那么鄰居節點的權值w2就越高，因為兩個節點如果位于同一位置，那么該節點自然也就可以覆蓋當前節點所需要覆蓋的節點，而此時由于已經搜集了鄰域的節點能量，可以使用相對剩余能量來替代能量。

然后，各個節點會通過虛擬骨干向sink節點發送一個有關本地拓撲的local message，消息中包括節點的ID和FList。由于sink節點不受性能的約束，可以建立一個全局拓撲，利用該信息可以對失效或者能量不足的節點執行快速修復，下面對3種觸發機制進行描述。

基于時間觸發的機制是在sink節點中進行，sink節點記錄每次發生全局拓撲修復的時間，然后每隔一定的時間執行該過程以平衡節點之間的能耗。

基于故障觸發的機制是在當前的節點失效后的γ時間后觸發，如果sink節點在一定的間隔中沒有收到節點發送的數據，就會認為該節點失效了，然后開始執行拓撲維護策略。

基于能量觸發機制是在節點的剩余能量小于閾值時，向sink節點發送reconstruction消息 (send,gateway,sink)請求網絡重建，其中，send表示發送節點ID，gateway表示下一跳節點ID，sink表示基站ID。reconstruction消息沿著gateway向sink節點發送，如果當前節點ID不等于sink，節點繼續選擇合適的gateway進行轉發。信息到達基站后，sink節點開始評估網絡的狀態以執行合適的拓撲維護策略，下面對具體的策略進行描述。

sink節點對當前網絡進行評估，如果發現時間T內收到了多個節點的重建請求，則證明網絡已經并非最優，需要立即重啟全局拓撲修復，并對當前時間進行更新；如果請求數較少，sink節點會在全局拓撲中找到維護節點u，然后從u的FList中依次選擇灰色且性能最優的節點加入列表ReplaceID，直到完全覆蓋被替換節點u的FList中的所有灰色節點，如果局部拓撲修復不能得到連通的拓撲，那么sink節點會重啟全局拓撲修復以保證網絡的連通。

隨 后 ，sink節點將decision message(flag,time,ReplaceID)沿著虛擬骨干對全網進行發送，其中，flag表示拓撲修復策略，time表示需要等待的時延，如果是局部修復策略，ReplaceID表示需要成為活躍節點的ID集合，否則該集合為空。活躍節點將收到的消息向普通節點進行轉發，節點收到消息后檢查是否需要成為活躍節點。

5 理論分析

定理1如果初始網絡是連通的，那么通過拓撲構建后形成的支配集也是連通的。

證明算法形成的支配集由黑色節點組成。由于節點共存在4種顏色，初始時所有節點都是白色，節點一旦廣播competition消息就會變成紅色，然后根據是否收到滿足First等于自己ID的消息來決定成為黑色或灰色節點，也就是說算法結束后只可能存在白色、黑色、灰色節點。假如還存在白色節點，那就說明該節點沒有收到過其他節點廣播的competition消息，這與定理假設初始網絡是連通的相矛盾，得證。

定理2拓撲構建算法中每個節點至多只需要發送一次消息，而時間復雜度為O(n)。

證明當前節點收到上層節點發送的消息后，會在超時結束后廣播一次消息，并根據收到消息的First屬性決定變為黑色或灰色。此外，節點的操作不需要排序，均能在常數時間內完成，因此算法的時間復雜度為O(n)。

定理3拓撲維護算法至多只需要發送2n的消息，算法的時間復雜度為O(nlgn)。

證明節點需要對鄰居節點計算權值w2并排序，這個過程需要O(ΔlgΔ)的時間，Δ為最大鄰居節點數。消息沿著虛擬骨干向基站轉發，最壞的情況下，消息被轉發n次到達sink節點。基于時間機制的拓撲維護策略每隔時間T進行重構，不需要其他額外操作；基于能量和故障機制的拓撲維護策略，采用局部拓撲修復時，至多需要O(Δ)的時間來判斷是否可以生成替代節點集ReplaceID，而采用全局拓撲維護時需要O(1)的時間決定。sink節點根據當前網絡狀況將執行的策略和時延封裝在decision消息并沿著拓撲反向轉發至多n次，因此拓撲維護發送的消息最多不會超過2n，而算法的時間復雜度在最壞情況下為O(n lg n)。

6 仿真實驗及分析

6.1 實驗環境及參數設置

仿真實驗選擇性能較好且同時包含拓撲構建和拓撲維護過程的異構無線傳感器網絡拓撲控制算法A3M作為比較對象，實驗采用基于網絡事件驅動的軟件Atarraya[15]進行評估，仿真開始時，振動能源的能量采集速率λ=0，隨著時間的增加，λ將以0.001 mJ/unit的速率遞增，算法采用的能耗模型與參考文獻[12]相同，其他參數見表1。

表1 仿真實驗參數設置

6.2 實驗結果

首先通過一組節點狀態轉換圖闡述仿真實驗的運行過程。實驗初始時，將150個通信半徑和能量各不相同的傳感器節點部署到網絡中，如圖2(a)所示，此時所有節點均為白色。當算法運行結束后，可以得到如圖2(b)所示的網絡拓撲，其中，黑色表示活躍節點，灰色表示處于休眠的節點。實驗結果取自隨機生成的20個拓撲實例分別運行10次后的平均值，從通信開銷和網絡生命時間對算法進行評估。

實驗1主要對拓撲構建算法的通信開銷進行評估，當網絡節點數為100時，觀察發送和接收的消息數隨著最大通信半徑變化而發生的改變。如圖3所示，HELM不管是需要發送還是需要接收的消息數都要比A3M更少，特別是當節點的最大通信半徑較大(40 m)時，HELM需要接收的消息數為3 212.3條，而A3M需要接收大約7 942.5條消息，相當于HELM節省了59.6%的通信開銷，這說明HELM的擴展性較好。

實驗2將節點的最大通信半徑固定為30 m，通過改變節點的數量來觀察算法的通信開銷。如圖4所示，隨著節點數量的增加，需要發送和接收的消息數都在不斷增加。HELM需要發送的消息數量等于節點的數量，而A3M需要發送的消息數量為300～650條。相比之下，兩個算法需要接收的消息數量更多，當網絡節點數為200個時，HELM、A3M分別需要接收9 310.5條、22 475.8條消息，從圖4中曲線的變化趨勢預測，當節點數量更密集時，這一情況會更加明顯。

實驗3對拓撲維護的性能進行評估，將最大通信半徑為20 m的100個節點進行部署，節點每隔10個單元時間向sink節點發送數據,拓撲維護中的時間、能量、故障閾值見表1中的T1、T2、T3，這里暫不考慮數據融合和能量采集的影響，觀察通信覆蓋率隨時間的變化情況。圖5顯示了4種拓撲維護策略的運行情況，HELM和A3M兩種拓撲維護策略與靜態和動態拓撲維護相比都將延長網絡的運行時間，特別是HELM，直到時間點20 988.2時開始出現第一個節點的死亡而導致通信覆蓋率下降，這一現象在A3M中發生在時間點17 558.1，此時HELM提高了19.5%的網絡運行時間，這是因為HELM的拓撲維護策略只有在不得已的情況下才對網絡進行重構，否則對當前拓撲執行局部修復以減少網絡能耗。

實驗4在實驗3的基礎上對HELM中基于時間機制的維護策略進行評估，觀察時間輪換的策略對通信覆蓋率產生的影響。從圖6中發現，考慮時間因素能夠得到更好的通信覆蓋率。當第一個節點死亡時，不考慮時間輪換的策略相比考慮時間輪換的策略提前了2 158.2個單位時間，隨著時間的不斷增加，兩個算法的通信覆蓋率差距在不斷變大，這是因為基于時間輪換的策略使得節點之間的能量消耗更加平衡，而不考慮時間輪換的策略可能由于某些關鍵節點的死亡而使得網絡性能快速下降。

實驗5在實驗3的基礎上對HELM中基于故障機制的拓撲維護策略進行評估，將節點的故障率分別設為1%和3%，觀察通信覆蓋率的變化情況。如圖7所示，隨著節點故障率的增加，在相同生命時間下兩種拓撲維護策略的通信覆蓋率都有所下降，其中，HELM拓撲維護策略的第一個死亡節點的時間提前了1 836.5個時間單元。此外，由圖可知，A3M拓撲維護策略下降得更快，這是因為當節點失效時，A3M不但每次都需要進行拓撲重構，而且在重構過程中A3M需要發送和接收的消息數量比HELM更多，這就造成A3M的能耗更大，嚴重影響了網絡的生命時間。

實驗6對能量補給模型的性能進行評估，觀察是否考慮能量采集對網絡的生命時間產生的影響。如圖8所示，隨著時間的增加剩余存活節點數量逐漸下降，但是考慮能量補給的網絡的存活節點數量始終要大于不考慮能量補給的網絡節點數量，這是因為部分節點可以通過采集而有效補給能量。帶有能量補給的網絡出現第一個死亡節點的時間為23 568.5，相比無能量補給模型，該模型相當于延長了7.2%的網絡生命時間。

7 結束語

隨著傳感器節點可以通過能量采集進行供能，當前拓撲控制算法需要考慮節點能量補給的特性以延長網絡的生命時間，本文在通信半徑和能量存在異構的網絡中提出了一種結合拓撲構建和拓撲維護過程的拓撲控制算法。算法首先以較少的通信開銷構建連通支配集，而當拓撲不再高效時，及時運行拓撲維護算法，由sink節點決定采用局部或全局拓撲修復策略以節約網絡能量。仿真結果顯示，拓撲構建算法相比A3M可以節省超過59%的通信開銷，而拓撲維護策略更是將網絡的運行時間提高了將近20%。此外，與無能量補給的網絡模型相比，帶有能量補給的網絡模型最終使網絡的生命時間延長了7.2%。HELM可以應用在環境比較惡劣的地區，當節點失效時可以通過較小的能耗代價保障網絡拓撲的質量。

1 錢志鴻,王義君.面向物聯網的無線傳感器網絡綜述.電子與信息學報,2013,35(1)：215～227 Qian Z H,Wang Y J.Internet of things-oriented wireless sensor networks review. Journal of Electronics & Information Technology,2013,35(1):215～227

2 Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks. IEEE Communications Surveys and Tutorials,2013,15(1):121～144

3 Labrador M A,Wightman P M.Topology Control in Wireless Sensor Network.Berlin:Springer,2009

4 He J,Ji S L,Fan P Z,et al.Constructing a load-balanced virtual backbone in wireless sensor networks.Proceedings of International Conference on Computing Networking and Communications,Maui,Hawaii,USA,2012:147～163

5 Wightman P M,Fabregas A,Labrador M A.An optimal solution to the MCDS problem for topology construction in wireless sensor networks.Proceedings of IEEE Latin-American Conference on Communications,Bogota,Columbia,2010:1～6

6 洪榛,俞立,張貴軍等.基于最小連通支配集的無線傳感網拓撲構建研究.電子與信息學報,2012,34(8)：2000～2006 Hong Z,Yu L,Zhang G J,et al.Topology construction based on minimum connected dominating set for wireless sensor networks.Journal of Electronics&Information Technology,2012,34(8):2000～2006

7 奎曉燕,杜華坤,梁俊斌.無線傳感器網絡中一種能量均衡的基于連通支配集的數據收集算法.電子學報,2013,41(8)：1521～1528 Kui X Y,Du H K,Liang J B.An energy-balanced connected dominating sets for data gathering in wireless sensor networks.Acta Electronica Sinica,2013,41(8):1521～1528

8 Wightman P M,Labrador M A.Topology maintenance:extending the lifetime of wireless sensor networks.IEEE Latin America Transactions,2010,8(4):1～6

9 沈中,常義林,崔燦等.一種可自維護無線網絡拓撲最小能量特性的分布式拓撲控制算法.計算機學報,2007,30(4)：569～578 Shen Z,Chang Y L,Cui C,et al.A distributed topology control algorithm for self-maintenance of the minimum-energy property of a wireless networks topology.Chinese Journal of Computers,2007,30(4):569～578

10 Liao Y,Qi H,Li W.Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks.IEEE Sensors Journal,2013,13(5):1498～1506

11 康一梅,李志軍,胡江等.一種低能耗層次型無線傳感器網絡拓撲控制算法.自動化學報,2010,36(4)：543～549 Kang Y M,Li Z J,Hu J,et al.A Low-power hierarchical wireless sensor network topology control algorithm.Acta Automatica Sinica,2010,36(4):543～549

12 馬晨明,王萬良,洪榛.異構無線傳感器網絡中基于CDS樹的拓撲控制方法.傳感技術學報,2014,27(6)：814～820 Ma C M,Wang W L,Hong Z.A topology control method based on CDS tree in heterogeneous wireless sensor network.Chinese Journal of Sensors and Actuators,2014,27(6):814～820

13 Sudevalayam S,Kulkarni P.Energy harvesting sensor nodes:survey and implications.Communications Surveys&Tutorials,2011,13(3):443～461

14 姚玉坤,王冠,任智等.能耗均衡的自供能無線傳感器網絡分簇路由算法.傳感技術學報,2013,10(26)：1420～1425 Yao Y K,Wang G,Ren Z,et al.Energy balanced clustering algorithm for self-energized wireless sensor networks.Chinese Journal of Sensors and Actuators,2013,10(26):1420～1425

15 Wightman P M,Labrador M A.Atarraya:a simulation tool to teach and research topology control algorithms for wireless sensor networks.Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009