Energy Balanced and Fault Tolerant Data Gathering Algorithmfor Heterogeneous Wireless Sensor Network*

YANG Mingxia，WANG Wanliang，MA Chenming（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 34000，China；.College of Information，Zhejiang University of Technology，Hangzhou 31003，China）

?

Energy Balanced and Fault Tolerant Data Gathering Algorithm
for Heterogeneous Wireless Sensor Network*

YANG Mingxia1，2，WANG Wanliang2*，MA Chenming2
（1.College of Electrical and Information Engineering，Quzhou University，Quzhou Zhejiang 324000，China；2.College of Information，Zhejiang University of Technology，Hangzhou 310023，China）

Virtual backbone based on connected dominating setcan prolong the lifetime of wireless sensor network. However，the network also needs to have a certain degree of fault tolerance due to characteristicsof the nodes that are prone to failure.In view of the problem that the fault tolerant methods of k-connected m-dominated set consume too much energy，a distributed data gathering algorithm for energy-saving and fault-tolerance is proposed in the new?ly heterogeneous network mode.The algorithm firstly construct connected dominating set，then select better degree of fault tolerance nodes as backup nodes，and finally balance the energy consumption of the dominated nodes in the data gathering process.Theoretical analysisand simulation experimentsconfirm that our algorithm not only can con?struct connected dominating set with low time and message overhead，but also ensure the fault tolerance and extend the network lifetime finally.

heterogeneous wireless sensornetwork；connected dominating set；data gathering；fault tolerant；load balance

隨著物聯網技術的快速發展，數據已經成為社會發展的核心內容。作為末端采集系統，無線傳感器網絡（Wireless Sensor Networks，WSNs）可以實現物理世界與信息世界的有效融合。資源受限導致傳感器網絡在部署規模和運行時間等方面存在大量難題和挑戰。利用節點的空間冗余性，可利用網絡中部分節點工作來節省能耗，這類方法最典型的做法是拓撲控制，通過優化網絡的拓撲結構，使得網絡中節點的能耗均衡，延長網絡生命時間。

其中，基于虛擬骨干的拓撲控制方法［1-4］通過求解一個確保網絡連通的連通支配集，覆蓋網絡中所有其它非骨干節點，目標函數是減少工作節點規模。采用連通支配集作為虛擬骨干可以有效減少活躍節點數和路由開銷，同時對于節點的管理和維護也更加容易，是一種有效的節能方法。但是，在實際環境中可能會出現節點死亡和鏈路錯誤等問題。

本文主要從節能和容錯兩個方面對無線傳感器網絡的能量節省問題進行研究，針對異構網絡模型研究分布式容錯數據收集算法，通過對活躍節點產生備份集的方法來生成容錯拓撲，減少處于工作的支配節點數，從而節省網絡能量，維持網絡的穩定性。

1　相關研究工作

虛擬骨干網可以利用圖論中求解最小連通支配集（Minimum Connected Dominating Set，MCDS）問題的方法來構建。現有算法可以分為減少能耗和保證高可靠性。

EBCDS［5］通過選擇能量水平和度均比較大的節點組成連通支配集，支配集中的節點組成一個規模不大但具有較高能量水平的網絡骨干。網絡中的所有數據沿骨干在較小的尋路空間中轉發，能夠節省節點能量。但是，EBCDS在連通節點的過程，將三跳鄰域中所有的節點均進行了連通且沒有考慮剪枝等操作，導致產生的連通支配集規模較大，同時算法的消息復雜度也較高。

以上算法沒有考慮節點能耗速率產生的影響，網絡的生命由能量最先耗盡的節點決定，它主要受到初始能量和能耗速率的影響。

在保證網絡可靠性方面，文獻［6］提出的CDSA算法通過選擇中間節點合并（1，1）-CDS中葉子塊的個數，最終使所有活躍節點在同一個塊中。文獻［7］將問題擴展到了任意k，m的取值，但是算法求解比較困難。k-CDS［8］將節點的參數Domi和Total分別初始化為k和所有鄰居節點Domi之和。算法通過消息交互獲得鄰居節點的Total，Total最大的節點成為支配節點并通知鄰居節點；鄰居節點收到消息后將Domi減1，然后通知其他節點對Total更新；如果節點的Domi等于0成為普通節點。反復執行上述過程，這樣形成的節點集是k支配的。然后，利用塊-割點圖將m-支配集2-連通。

DDA［9］首先構建（1，m）-CDS，然后從指定節點開始構建初始k連通分支。分支上的所有節點廣播KC消息，鄰居Black節點收到消息后對路徑進行確認，如果至少存在k條可行路徑，則廣播AC消息；否則，發送RC請求k連通路徑。當白色節點收到RC時，檢查自己是否存在k條連通路徑，如果存在回復CS消息給發送者，然后廣播KC消息成為Black節點；否則，將ID添加到請求列表中并向鄰居節點轉發RC請求。算法在最壞情況下需要收集網絡中所有節點的消息，時間和消息復雜度分別達到了O（n1.6）和O（n2）。

文獻［10］提出了一種生成候選節點的方法來分流工作負載過重的支配節點，盡管這只是針對能耗問題進行研究，但是這種思想仍然值得借鑒。文獻［11］采用類似思想，提出了以生成備份節點為主導的算法AFTC。AFTC對節點的容錯度進行研究，然后選擇容錯度高的節點構建網絡并生成備份節點集，相比（k，m）-CDS，該方法產生的活躍節點規模更小。但是，算法在實現中需要獲得每個節點的位置信息，而節點通常并不配備GPS等具有定位功能的昂貴設備，而且算法構建的消息開銷也過大，同時沒有對容錯算法的連通性的必要條件提供理論證明。

此外，現有拓撲控制方法主要集中在同構網絡中，文獻［12-13］針對異構網絡展開研究。文獻［12］在異構網絡中提出了分布式拓撲控制算法A3M，拓撲構建基于最小連通支配集構建虛擬骨干樹，拓撲維護對網絡性能進行評估。而文獻［13］基于反向連通支配集樹，改進了節點的適應度函數和算法流程，提出了一種低信息復雜度的分布式拓撲構建算法A3GMLM，優化了產生的連通支配集的規模和通信開銷。

本文主要在參考文獻［11-13］的基礎上，考慮數據收集過程節點的能耗速率的影響，提出了一種容錯數據收集算法EBFT（Energy Balanced and Fault Tolerant），在節省網絡能量基礎上保證數據收集質量。

2　算法描述

數據收集過程由連通支配集的構建、數據傳輸和拓撲維護組成。為了節約能量，普通節點在大部分時間將關閉通信模塊，僅僅周期性向支配節點發送采集的數據，而活躍節點負責接收并融合其他節點發送的數據。假設鄰域內不同節點產生的數據具有部分相關性，不同節點的數據可以完全匯聚為一個大小固定的數據包，然后通過路由最終到達Sink。當網絡出現異常時，恢復、輪換或再生成拓撲。本文所采用的網絡模型與數據模型均基于文獻［12］。

2.1相關定義

定義1節點的權值

結合節點的異構性，算法優先選擇能量多、采集能力強、鄰居節點多、通信半徑大、距離上層骨干節點距離遠和故障少的節點作為支配節點，節點的權值定義如下：

式（1）第1部分表示計時時段內節點被選為支配節點的影響因子，分母為節點單位時間消耗的能量值；第2部分可以在選舉支配節點時使用相對鄰居節點個數，原因是算法在初始化時需要通過兩輪的消息交換獲得鄰居節點的鄰居列表消息；第4項表明了節點的距離覆蓋利用效率（距離近的節點不要一起工作）；而式（1）的第5部分ω5p（μ）是當前節點失效的概率，p（μ）代表了正常工作的期望概率。。

定義2節點的容錯度

在備份節點的選擇中需要對節點的容錯屬性進行分析，如果當前節點與活躍節點的性能越相似，那么使用當前節點進行替代后就可以覆蓋更多節點，定義式（2）表示節點的容錯度：

這里與式（1）不同的主要在第3部分，如果兩個節點的鄰居節點個數越多那么該節點作為后備節點就可以覆蓋盡可能多的其他節點，這樣就能更好地維護網絡的容錯性，減少活躍節點數。

2.2構建連通支配集

本節算法在文獻［12］中拓撲構建算法的基礎上進行改進，在節點通信半徑存在異構的網絡環境中進一步優化了消息開銷。本文只需要一次信息交換，具體方法如下：在節點上存儲通信半徑Ru并在Hello消息中依據接受到的信號強度RSSI計算距離信息，當節點u收到了節點v發送的Hello消息時，節點通過RSSI可以獲得u，v之間的距離d（u，v），若Ru≥d（u，v）即表示節點之間可以通信。本文在此基礎上增加節點容錯度、鄰居列表信息等參數，在異構網絡中每個節點只需要發送兩次消息就可以獲得容錯度計算所需要的參數，在節點通信半徑不同的網絡環境中進一步優化消息開銷。

2.3選擇備份節點

備份節點的選擇從某一“Black”節點v開始，從鄰居節點列表N1（v）中優先在FT屬性為true的記錄中選擇FD（u）最大的“Grey”節點加入到備份節點集Back（v），否則在FT==fasle的記錄中查找。在每一次選擇后，更新當前節點尚未覆蓋的節點集（Cover（v）=Cover（v）CNL（u）），其中Cover（v）被初始化為當前節點的鄰居節點集N1（v）∪v。該操作結束后，還需要對當前節點v的其他鄰居節點w對應的公共節點列表CNL進行更新（CNL（w）= CNL（w）CNL（u））；如果Cover（u）≠Φ，繼續選擇FD最大且CNL≠Φ的其他節點加入到Back（v）中直到Cover（u）=Φ。上述過程結束后，Black節點v廣播一個Notify（IDv，Back（v），NBlack（v））消息，其中NBlack表示當前節點下層的“Black”節點列表。

當Grey節點u收到Notify消息后，檢查IDu是否在Back列表中，如果存在成為Blue節點；如果是下層Black節點u收到該消息，則遍歷Back（v）列表，并更新N1（u）列表中對應記錄的FT屬性為true。完成操作后，按照其在鄰居支配節點列表NBlack中的索引位置等待超時結束選擇備份節點。

當Black節點u突然失效時，它將廣播Active消息喚醒鄰域的Blue節點重新進入工作狀態，下層的Black節點v收到消息后，將路由的發送對象從節點u調整為距離自身最近的Blue節點，然后繼續數據收集過程。

圖1給出了備份節點選擇的一個算法運行實例，假設S是初始執行節點。如圖1（a），節點S對鄰居節點的FD進行評估，選擇最大節點A加入到Back（s），此時因為A已經能夠覆蓋節點S需要覆蓋的所有節點（C，D，S，E，F），S廣播Notify消息。節點A收到消息后變成Blue，而C、F在N1列表中設置A的FT屬性等于true，然后C首先開始選擇備份節點，它首先從列表N1（C）中選擇FT==true的節點A更新Cover（C）（｛B｝），此時得到Cover（C）==Φ，即C將A作為Blue節點。圖1（c）中節點G首先被選為F的備份節點，但是此時發現其與節點S不再連通，需要繼續將E加入到Back中。圖1（d）中顯示了節點A、E、G、H最終被標記為Blue。

圖1　選擇備份節點的實例圖

2.4均衡能耗速率

為了均衡支配節點的能量消耗，最終使得所有節點盡可能在同一時刻死亡，需要平衡支配節點數據轉發的任務，讓能量較高節點承擔較重的任務負載。考慮鄰居支配節點的個數、剩余能量以及支配節點與被支配節點鏈路之間的距離，定義了期望分配概率函數DEAP，將普通節點采集的數據以概率發送到支配節點上，這樣避免了集中消耗部分中心節點的能量，從而延長了網絡的生命時間，對支配節點i的概率計算為：

普通節點v周圍可能有多個支配節點，v采集到數據后，需要選擇一個支配節點發送數據，DEAP（i）表示發給支配節點i的概率。式（3）中，E（i）表示當前節點的鄰居支配節點的剩余能量，Black_Num（i），dis（i，v）分別表示節點v的鄰居支配節點數和節點v與i之間的距離。所以，分子表明節點i的能量指數加權，可見能量指數越大，將數據發給支配節點i的概率越高；分母表示i的周邊支配節點能量指數加權求和；節點i，j的能量指數加權與其到節點v的距離dis（i，v），dis（j，v）成反比，將普通節點的數據優先傳給較近節點。

3　性能分析

定理1EBFT連通支配集構建算法最多需要發送5n的消息，算法的時間復雜度為O（n）。

證明連通支配集構建首先要在每個節點建立鄰居列表，需要計算節點的容錯度以選出備份節點集，亦因此節點需要獲得鄰居節點的鄰居列表信息（見式（2）），在對文獻［12］中的鄰居發現過程改進后，算法至多只需發送O（n）的消息數。備份節點選擇從任一Black節點開始，Black節點依據自身存儲的鄰居節點列表選擇后備節點后，將會廣播一個Notify消息通知列表中節點成為備份節點；下層的Black節點等待超時繼續向下選擇備份節點，所以整個算法至多發送5n的消息。

在選擇備份節點集時，Black節點需要選擇鄰居節點列表中最優的節點，需要O（Δ）的時間，當網絡比較密集時Δ趨向于n，算法的時間復雜度為O（n）。

可見，我們連通支配集構建的計算量是可行的，并隨著節點數目的增加線性增長。接下來的兩個定理，確切的說明了在同構及異構網絡的節點維護過程中，因部分失效節點而喚醒的備份節點數目不會過多，不會造成嚴重的網絡浪費。

定理2同構網絡任一節點失效時，算法至多添加10個備份節點來保證網絡的連通性。

證明如圖2所示，假設Black節點u失效，我們需要選擇備份節點連通Black節點v和w，同時覆蓋節點u鄰域的所有Grey節點。因為以u為中心的正六邊形將鄰域六等份，每一個扇形區域內至多使用2個節點就能與其他區域連通。從節點w開始添加備份節點，最壞情況使用10個節點就能連通網絡。同時，這些節點可以完全覆蓋節點u的鄰域。

圖2　同構網絡的備份節點分布圖

證明如圖3所示，假設節點的通信半徑R∈［Rmin，Rmax］，我們考慮任意弧度α的情況。假設節點間的距離d（u，w）=d（w，v）=Rmin，根據三角形余弦定理可得d（u，v）=Rmin（2cosα）；又因為d（u，v）= d（v，x），則d（u，x）=Rmin（2cosα）2；如上迭代可得Rmax=Rmin（2cosα）k，k為節點u與最大通信半徑之間至多需要的節點個數，解得。由于單位圓可以劃分為2π/α個圓弧，考慮連通性，共需要個節點。對該函數進行積分求解最大值，可得當α=π/5時得到極值。類似的，一個弧形區域內至多使用2個節點就能與相鄰區域連通，此時總共需要個節點。

圖3　異構網絡的備份節點分布圖

4　仿真實驗及分析

4.1實驗環境

仿真采用文獻［14］提供的平臺，隨機生成20個拓撲實例，運行20次取平均值。仿真使用的參數見表1。

表1　仿真實驗參數設置

4.2結果分析

為了驗證算法的有效性，仿真實驗選擇與EBCDS、DDA、AFTC三個當前較新的算法進行比較，這里選擇這三個算法的原因是EBCDS是當前比較新的基于最大獨立集的算法，DDA是較新的k連通m-支配容錯拓撲構建算法，AFTC采用與EBFT相同的思想構建容錯拓撲結構。

仿真1將100個節點部署到網絡中，觀察節點的通信半徑對產生的支配節點的影響。如圖4所示，EBFT在不同通信半徑下產生的支配節點數均要少于其他算法，當半徑為20時EBFT只需要21.8個節點作為支配節點，而EBCDS、AFTC、DDA分別需要24.5、26.2和41.3個節點。通信半徑加大時，各個算法所需要支配節點數都逐漸減少，當半徑為45時，EBFT、EBCDS、AFTC、DDA四個算法分別產生6.0、6.9、7.3和10.2個活躍節點。此時，算法之間的差距變小，其中DDA下降最快，這說明當通信半徑增大時構建（2，2）-CDS更加容易。

圖4　實驗1節點通信半徑變化時的活躍節點數

EBFT-Back和AFTC-Back是EBFT和AFTC產生的備份節點數。當半徑較少時，更多節點需要作為備份節點保證網絡連通，當通信半徑為20時，EBFT和AFTC產生的后備節點數分別為28.8和35.2，相比產生的活躍節點分別增加了7.0和9.1，這一差距隨著通信半徑的增加而減少，但是EBFT需要的后備節點數還是少于AFTC，這是因為AFTC算法在選擇備份節點時，多個Black節點可能同時開始選擇，造成冗余節點被選入的問題。

仿真2將通信半徑設為30，通過改變節點數量觀察活躍節點的變化。如圖5所示，各個算法的活躍節點數一直在某個值附近波動，這是因為當區域節點數達到一定密度時，當前活躍節點已經可以支配整個網絡，繼續增加節點數并不需要增加新的活躍節點數。圖中還發現DDA產生的活躍節點數要多于其他算法，而EBCDS的性能要優于AFTC。

圖5　實驗2節點數量變化時的活躍節點數

網絡生命是衡量算法的最終指標，實驗3將100個節點部署在網絡中，將通信半徑設為25，觀察各算法的最終的生命時間。如圖6所示，EBFT在將近800輪時才出現第一個節點的死亡，EBCDS、AFTC、DDA這一數據分別為681.6、590.7和477.5。顯然，EBFT能夠有效延長網絡的生命時間，這是因為EBFT不但可以生成規模較小的活躍節點集，而且算法的構建能耗較小。此外，EBFT還增加了支配節點的負載均衡，其網絡壽命相比EBCDS可提高17.1%。相反，DDA算法不但具有較高的支配節點規模和構建能耗，所以它的網絡生命時間較短也是可以理解的。

圖6　實驗3理想環境時的生命周期

為了能夠更加真實模擬網絡的實際環境，需要考慮節點出錯的可能性，在每一輪中使用隨機數模擬節點是否出現故障。相比理想環境，圖7顯示各個算法的生命時間均有所下降，EBFT、AFTC和DDA出現第一個死亡節點的時刻為783.1、567.2和448.5，同比分別提前了14.4、23.5和29.0個輪次。這里需要注意的是EBCDS在節點失效環境中的生命時間不如AFTC，它的第一個節點出現死亡的時間為581.8，相比理想環境超過了100輪，這是因為每次出現節點失效時都需要重新運行拓撲維護，使得網絡重構的次數增多，減少了能量的利用率。

5　總結

本文對異構無線傳感器網絡模型進行了擴展，在異構網絡模型中研究分布式容錯數據收集算法。算法針對k-連通m-支配集規模過大的問題，轉換了容錯拓撲構建的思想，在不需要節點位置信息的情況下，通過對活躍節點產生備份集的方法來生成容錯拓撲，這樣可以減少處于工作的支配節點數。此外，還考慮了節點能耗速率對網絡生命的影響，對數據收集過程進行了優化。理論分析對算法在同構和異構兩種網絡環境中需要增加的節點數情況進行了分析，保證了算法產生的后備節點的連通性。仿真實驗進一步證明EBFT在能效性、擴展性、可靠性上都具有較好的優越性。

［1］Lee S，Mohamed Y.Recovery from Multiple Simultaneous Fail?ures inWireless Sensor Networks Using Minimum Steiner Tree［J］.Parallel and Distributed Computing，2010，70（5）：525-536.

［2］馬晨明，王萬良，洪榛，等.帶有能量補給的異構無線傳感器網絡拓撲控制算法研究［J］.電信科學，2015，31（8）：2015181.

［3］馬晨明，王萬良，洪榛.無線傳感器網絡中一種改進的能效數據收集協議［J］.計算機科學，2015，42（2）：65-69.

［4］He J，Ji S L，Fan P Z，et al.Constructing a Load-Balanced Virtual Backbone in Wireless Sensor Networks［C］//Procof2012 Interna?tional Conference on Computing Networking and Communications（ICNC），Maui，Hawaii，USA，2012：959-963.

［5］奎曉燕，杜華坤，梁俊斌.無線傳感器網絡中一種能量均衡的基于連通支配集的數據收集算法［J］.電子學報，2013，41（8）：1521-1528.

［6］Wang F，Thai MT，Du D Z.On the Construction of 2-Connected Virtual Backbone in Wireless Networks［J］.IEEE Transactions on Wireless Communications，2009，8（3）：1230-1237.

［7］Thai M T，Zhang N，Tiwari R，et al.OnApproximation Algorithms of k-Connectedm-Dominating Sets in Disk Graphs［J］.Theoretical Computer Science，2007，385：49-59.

［8］鄭嬋，尹令，孫世新.無線傳感器網絡中2-連通k-支配的容錯連通支配集構造［J］.控制與決策，2013，28（5）：650-656.

［9］Li Y S，Wu Y W，Ai C Y，et al.On the Construction ofk-Connect?edm-Dominating Sets in Wireless Networks［J］.Combinatorial Op?timization，2012，1（23）：118-139.

［10］付永生，李善平，周波.無線傳感網絡中能量均衡的連通支配集算法［J］.傳感技術學報，2010，23（8）：1142-1145.

［11］Yin R R，Liu B，Li Y Q，et al.Adaptively Fault-Tolerant Topology Control Algorithm for Wireless Sensor Networks［J］.The Journal of China Universities of Posts and Telecommunications，2012，19（ZK2）：13-38.

［12］馬晨明，王萬良，洪榛.異構無線傳感器網絡中基于CDS樹的拓撲控制方法［J］.傳感技術學報，2014，27（6）：814-820.

［13］楊明霞，王萬良，馬晨明.一種基于反向CDS樹的異構WSNs拓撲控制方法［J］.傳感技術學報，2016，29（2）：248-255.

［14］Wightman P M，Labrador M A.Atarraya：A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Networks［C］//Proc of 2nd International Conference on Simulation Tools and Techniques，Rome，Italy，2009：26-35.

楊明霞（1979-），女，浙江衢州人，衢州學院講師。浙江工業大學在讀博士，研究方向為計算機自動化、無線傳感器網絡；

王萬良（1957-），男，江蘇高郵人，博士生導師。國家級教學名師、享受國務院特殊政府津貼、浙江工業大學計算機科學與技術學院院長，研究方向為計算機網絡化控制、無線網絡。

EEACC：723010.3969/j.issn.1004-1699.2016.06.024

面向節能和容錯的異構WSNs數據收集算法*

楊明霞1，2，王萬良2*，馬晨明2
（1.衢州學院電氣與信息工程學院，浙江衢州324000；2.浙江工業大學計算機學院，杭州310023）

采用連通支配集作為虛擬骨干可以延長無線傳感器網絡的生命時間，但是考慮節點容易失效的特性，網絡還需要具有一定的容錯性。針對k-連通m-支配集的容錯方法能耗過大的問題，提出了一種面向節能和容錯的分布式數據收集算法。算法首先構建連通支配集，然后選擇容錯度大的節點作為備份節點，最后在數據收集過程對支配節點的能耗進行均衡。理論分析和仿真實驗證實算法不僅以較小的時間和消息開銷構建規模較優的連通支配集，而且還保證了容錯性并最終延長了網絡的生命時間。

異構無線傳感器網絡；連通支配集；數據收集；容錯；負載均衡

TP393

A

1004-1699（2016）06-0934-07

2016-01-06修改日期：2016-03-24

項目來源：國家自然科學基金項目（61379123）；浙江省自然科學基金項目（LY15F020041，LY15F030014）；衢州學院師資隊伍建設基金項目（XNZQN201308）；寧波市社會發展基金項目（2014C50006）