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

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)據(jù)已經(jīng)成為社會(huì)發(fā)展的核心內(nèi)容。作為末端采集系統(tǒng)，無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）可以實(shí)現(xiàn)物理世界與信息世界的有效融合。資源受限導(dǎo)致傳感器網(wǎng)絡(luò)在部署規(guī)模和運(yùn)行時(shí)間等方面存在大量難題和挑戰(zhàn)。利用節(jié)點(diǎn)的空間冗余性，可利用網(wǎng)絡(luò)中部分節(jié)點(diǎn)工作來節(jié)省能耗，這類方法最典型的做法是拓?fù)淇刂?，通過優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，使得網(wǎng)絡(luò)中節(jié)點(diǎn)的能耗均衡，延長(zhǎng)網(wǎng)絡(luò)生命時(shí)間。

其中，基于虛擬骨干的拓?fù)淇刂品椒ǎ?-4］通過求解一個(gè)確保網(wǎng)絡(luò)連通的連通支配集，覆蓋網(wǎng)絡(luò)中所有其它非骨干節(jié)點(diǎn)，目標(biāo)函數(shù)是減少工作節(jié)點(diǎn)規(guī)模。采用連通支配集作為虛擬骨干可以有效減少活躍節(jié)點(diǎn)數(shù)和路由開銷，同時(shí)對(duì)于節(jié)點(diǎn)的管理和維護(hù)也更加容易，是一種有效的節(jié)能方法。但是，在實(shí)際環(huán)境中可能會(huì)出現(xiàn)節(jié)點(diǎn)死亡和鏈路錯(cuò)誤等問題。

本文主要從節(jié)能和容錯(cuò)兩個(gè)方面對(duì)無線傳感器網(wǎng)絡(luò)的能量節(jié)省問題進(jìn)行研究，針對(duì)異構(gòu)網(wǎng)絡(luò)模型研究分布式容錯(cuò)數(shù)據(jù)收集算法，通過對(duì)活躍節(jié)點(diǎn)產(chǎn)生備份集的方法來生成容錯(cuò)拓?fù)?，減少處于工作的支配節(jié)點(diǎn)數(shù)，從而節(jié)省網(wǎng)絡(luò)能量，維持網(wǎng)絡(luò)的穩(wěn)定性。

1　相關(guān)研究工作

虛擬骨干網(wǎng)可以利用圖論中求解最小連通支配集（Minimum Connected Dominating Set，MCDS）問題的方法來構(gòu)建?，F(xiàn)有算法可以分為減少能耗和保證高可靠性。

EBCDS［5］通過選擇能量水平和度均比較大的節(jié)點(diǎn)組成連通支配集，支配集中的節(jié)點(diǎn)組成一個(gè)規(guī)模不大但具有較高能量水平的網(wǎng)絡(luò)骨干。網(wǎng)絡(luò)中的所有數(shù)據(jù)沿骨干在較小的尋路空間中轉(zhuǎn)發(fā)，能夠節(jié)省節(jié)點(diǎn)能量。但是，EBCDS在連通節(jié)點(diǎn)的過程，將三跳鄰域中所有的節(jié)點(diǎn)均進(jìn)行了連通且沒有考慮剪枝等操作，導(dǎo)致產(chǎn)生的連通支配集規(guī)模較大，同時(shí)算法的消息復(fù)雜度也較高。

以上算法沒有考慮節(jié)點(diǎn)能耗速率產(chǎn)生的影響，網(wǎng)絡(luò)的生命由能量最先耗盡的節(jié)點(diǎn)決定，它主要受到初始能量和能耗速率的影響。

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

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

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

此外，現(xiàn)有拓?fù)淇刂品椒ㄖ饕性谕瑯?gòu)網(wǎng)絡(luò)中，文獻(xiàn)［12-13］針對(duì)異構(gòu)網(wǎng)絡(luò)展開研究。文獻(xiàn)［12］在異構(gòu)網(wǎng)絡(luò)中提出了分布式拓?fù)淇刂扑惴ˋ3M，拓?fù)錁?gòu)建基于最小連通支配集構(gòu)建虛擬骨干樹，拓?fù)渚S護(hù)對(duì)網(wǎng)絡(luò)性能進(jìn)行評(píng)估。而文獻(xiàn)［13］基于反向連通支配集樹，改進(jìn)了節(jié)點(diǎn)的適應(yīng)度函數(shù)和算法流程，提出了一種低信息復(fù)雜度的分布式拓?fù)錁?gòu)建算法A3GMLM，優(yōu)化了產(chǎn)生的連通支配集的規(guī)模和通信開銷。

本文主要在參考文獻(xiàn)［11-13］的基礎(chǔ)上，考慮數(shù)據(jù)收集過程節(jié)點(diǎn)的能耗速率的影響，提出了一種容錯(cuò)數(shù)據(jù)收集算法EBFT（Energy Balanced and Fault Tolerant），在節(jié)省網(wǎng)絡(luò)能量基礎(chǔ)上保證數(shù)據(jù)收集質(zhì)量。

2　算法描述

數(shù)據(jù)收集過程由連通支配集的構(gòu)建、數(shù)據(jù)傳輸和拓?fù)渚S護(hù)組成。為了節(jié)約能量，普通節(jié)點(diǎn)在大部分時(shí)間將關(guān)閉通信模塊，僅僅周期性向支配節(jié)點(diǎn)發(fā)送采集的數(shù)據(jù)，而活躍節(jié)點(diǎn)負(fù)責(zé)接收并融合其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)。假設(shè)鄰域內(nèi)不同節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)具有部分相關(guān)性，不同節(jié)點(diǎn)的數(shù)據(jù)可以完全匯聚為一個(gè)大小固定的數(shù)據(jù)包，然后通過路由最終到達(dá)Sink。當(dāng)網(wǎng)絡(luò)出現(xiàn)異常時(shí)，恢復(fù)、輪換或再生成拓?fù)?。本文所采用的網(wǎng)絡(luò)模型與數(shù)據(jù)模型均基于文獻(xiàn)［12］。

2.1相關(guān)定義

定義1節(jié)點(diǎn)的權(quán)值

結(jié)合節(jié)點(diǎn)的異構(gòu)性，算法優(yōu)先選擇能量多、采集能力強(qiáng)、鄰居節(jié)點(diǎn)多、通信半徑大、距離上層骨干節(jié)點(diǎn)距離遠(yuǎn)和故障少的節(jié)點(diǎn)作為支配節(jié)點(diǎn)，節(jié)點(diǎn)的權(quán)值定義如下：

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

定義2節(jié)點(diǎn)的容錯(cuò)度

在備份節(jié)點(diǎn)的選擇中需要對(duì)節(jié)點(diǎn)的容錯(cuò)屬性進(jìn)行分析，如果當(dāng)前節(jié)點(diǎn)與活躍節(jié)點(diǎn)的性能越相似，那么使用當(dāng)前節(jié)點(diǎn)進(jìn)行替代后就可以覆蓋更多節(jié)點(diǎn)，定義式（2）表示節(jié)點(diǎn)的容錯(cuò)度：

這里與式（1）不同的主要在第3部分，如果兩個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)越多那么該節(jié)點(diǎn)作為后備節(jié)點(diǎn)就可以覆蓋盡可能多的其他節(jié)點(diǎn)，這樣就能更好地維護(hù)網(wǎng)絡(luò)的容錯(cuò)性，減少活躍節(jié)點(diǎn)數(shù)。

2.2構(gòu)建連通支配集

本節(jié)算法在文獻(xiàn)［12］中拓?fù)錁?gòu)建算法的基礎(chǔ)上進(jìn)行改進(jìn)，在節(jié)點(diǎn)通信半徑存在異構(gòu)的網(wǎng)絡(luò)環(huán)境中進(jìn)一步優(yōu)化了消息開銷。本文只需要一次信息交換，具體方法如下：在節(jié)點(diǎn)上存儲(chǔ)通信半徑Ru并在Hello消息中依據(jù)接受到的信號(hào)強(qiáng)度RSSI計(jì)算距離信息，當(dāng)節(jié)點(diǎn)u收到了節(jié)點(diǎn)v發(fā)送的Hello消息時(shí)，節(jié)點(diǎn)通過RSSI可以獲得u，v之間的距離d（u，v），若Ru≥d（u，v）即表示節(jié)點(diǎn)之間可以通信。本文在此基礎(chǔ)上增加節(jié)點(diǎn)容錯(cuò)度、鄰居列表信息等參數(shù)，在異構(gòu)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)只需要發(fā)送兩次消息就可以獲得容錯(cuò)度計(jì)算所需要的參數(shù)，在節(jié)點(diǎn)通信半徑不同的網(wǎng)絡(luò)環(huán)境中進(jìn)一步優(yōu)化消息開銷。

2.3選擇備份節(jié)點(diǎn)

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

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

當(dāng)Black節(jié)點(diǎn)u突然失效時(shí)，它將廣播Active消息喚醒鄰域的Blue節(jié)點(diǎn)重新進(jìn)入工作狀態(tài)，下層的Black節(jié)點(diǎn)v收到消息后，將路由的發(fā)送對(duì)象從節(jié)點(diǎn)u調(diào)整為距離自身最近的Blue節(jié)點(diǎn)，然后繼續(xù)數(shù)據(jù)收集過程。

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

圖1　選擇備份節(jié)點(diǎn)的實(shí)例圖

2.4均衡能耗速率

為了均衡支配節(jié)點(diǎn)的能量消耗，最終使得所有節(jié)點(diǎn)盡可能在同一時(shí)刻死亡，需要平衡支配節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)的任務(wù)，讓能量較高節(jié)點(diǎn)承擔(dān)較重的任務(wù)負(fù)載?？紤]鄰居支配節(jié)點(diǎn)的個(gè)數(shù)、剩余能量以及支配節(jié)點(diǎn)與被支配節(jié)點(diǎn)鏈路之間的距離，定義了期望分配概率函數(shù)DEAP，將普通節(jié)點(diǎn)采集的數(shù)據(jù)以概率發(fā)送到支配節(jié)點(diǎn)上，這樣避免了集中消耗部分中心節(jié)點(diǎn)的能量，從而延長(zhǎng)了網(wǎng)絡(luò)的生命時(shí)間，對(duì)支配節(jié)點(diǎn)i的概率計(jì)算為：

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

3　性能分析

定理1EBFT連通支配集構(gòu)建算法最多需要發(fā)送5n的消息，算法的時(shí)間復(fù)雜度為O（n）。

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

在選擇備份節(jié)點(diǎn)集時(shí)，Black節(jié)點(diǎn)需要選擇鄰居節(jié)點(diǎn)列表中最優(yōu)的節(jié)點(diǎn)，需要O（Δ）的時(shí)間，當(dāng)網(wǎng)絡(luò)比較密集時(shí)Δ趨向于n，算法的時(shí)間復(fù)雜度為O（n）。

可見，我們連通支配集構(gòu)建的計(jì)算量是可行的，并隨著節(jié)點(diǎn)數(shù)目的增加線性增長(zhǎng)。接下來的兩個(gè)定理，確切的說明了在同構(gòu)及異構(gòu)網(wǎng)絡(luò)的節(jié)點(diǎn)維護(hù)過程中，因部分失效節(jié)點(diǎn)而喚醒的備份節(jié)點(diǎn)數(shù)目不會(huì)過多，不會(huì)造成嚴(yán)重的網(wǎng)絡(luò)浪費(fèi)。

定理2同構(gòu)網(wǎng)絡(luò)任一節(jié)點(diǎn)失效時(shí)，算法至多添加10個(gè)備份節(jié)點(diǎn)來保證網(wǎng)絡(luò)的連通性。

證明如圖2所示，假設(shè)Black節(jié)點(diǎn)u失效，我們需要選擇備份節(jié)點(diǎn)連通Black節(jié)點(diǎn)v和w，同時(shí)覆蓋節(jié)點(diǎn)u鄰域的所有Grey節(jié)點(diǎn)。因?yàn)橐評(píng)為中心的正六邊形將鄰域六等份，每一個(gè)扇形區(qū)域內(nèi)至多使用2個(gè)節(jié)點(diǎn)就能與其他區(qū)域連通。從節(jié)點(diǎn)w開始添加備份節(jié)點(diǎn)，最壞情況使用10個(gè)節(jié)點(diǎn)就能連通網(wǎng)絡(luò)。同時(shí)，這些節(jié)點(diǎn)可以完全覆蓋節(jié)點(diǎn)u的鄰域。

圖2　同構(gòu)網(wǎng)絡(luò)的備份節(jié)點(diǎn)分布圖

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

圖3　異構(gòu)網(wǎng)絡(luò)的備份節(jié)點(diǎn)分布圖

4　仿真實(shí)驗(yàn)及分析

4.1實(shí)驗(yàn)環(huán)境

仿真采用文獻(xiàn)［14］提供的平臺(tái)，隨機(jī)生成20個(gè)拓?fù)鋵?shí)例，運(yùn)行20次取平均值。仿真使用的參數(shù)見表1。

表1　仿真實(shí)驗(yàn)參數(shù)設(shè)置

4.2結(jié)果分析

為了驗(yàn)證算法的有效性，仿真實(shí)驗(yàn)選擇與EBCDS、DDA、AFTC三個(gè)當(dāng)前較新的算法進(jìn)行比較，這里選擇這三個(gè)算法的原因是EBCDS是當(dāng)前比較新的基于最大獨(dú)立集的算法，DDA是較新的k連通m-支配容錯(cuò)拓?fù)錁?gòu)建算法，AFTC采用與EBFT相同的思想構(gòu)建容錯(cuò)拓?fù)浣Y(jié)構(gòu)。

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

圖4　實(shí)驗(yàn)1節(jié)點(diǎn)通信半徑變化時(shí)的活躍節(jié)點(diǎn)數(shù)

EBFT-Back和AFTC-Back是EBFT和AFTC產(chǎn)生的備份節(jié)點(diǎn)數(shù)。當(dāng)半徑較少時(shí)，更多節(jié)點(diǎn)需要作為備份節(jié)點(diǎn)保證網(wǎng)絡(luò)連通，當(dāng)通信半徑為20時(shí)，EBFT和AFTC產(chǎn)生的后備節(jié)點(diǎn)數(shù)分別為28.8和35.2，相比產(chǎn)生的活躍節(jié)點(diǎn)分別增加了7.0和9.1，這一差距隨著通信半徑的增加而減少，但是EBFT需要的后備節(jié)點(diǎn)數(shù)還是少于AFTC，這是因?yàn)锳FTC算法在選擇備份節(jié)點(diǎn)時(shí)，多個(gè)Black節(jié)點(diǎn)可能同時(shí)開始選擇，造成冗余節(jié)點(diǎn)被選入的問題。

仿真2將通信半徑設(shè)為30，通過改變節(jié)點(diǎn)數(shù)量觀察活躍節(jié)點(diǎn)的變化。如圖5所示，各個(gè)算法的活躍節(jié)點(diǎn)數(shù)一直在某個(gè)值附近波動(dòng)，這是因?yàn)楫?dāng)區(qū)域節(jié)點(diǎn)數(shù)達(dá)到一定密度時(shí)，當(dāng)前活躍節(jié)點(diǎn)已經(jīng)可以支配整個(gè)網(wǎng)絡(luò)，繼續(xù)增加節(jié)點(diǎn)數(shù)并不需要增加新的活躍節(jié)點(diǎn)數(shù)。圖中還發(fā)現(xiàn)DDA產(chǎn)生的活躍節(jié)點(diǎn)數(shù)要多于其他算法，而EBCDS的性能要優(yōu)于AFTC。

圖5　實(shí)驗(yàn)2節(jié)點(diǎn)數(shù)量變化時(shí)的活躍節(jié)點(diǎn)數(shù)

網(wǎng)絡(luò)生命是衡量算法的最終指標(biāo)，實(shí)驗(yàn)3將100個(gè)節(jié)點(diǎn)部署在網(wǎng)絡(luò)中，將通信半徑設(shè)為25，觀察各算法的最終的生命時(shí)間。如圖6所示，EBFT在將近800輪時(shí)才出現(xiàn)第一個(gè)節(jié)點(diǎn)的死亡，EBCDS、AFTC、DDA這一數(shù)據(jù)分別為681.6、590.7和477.5。顯然，EBFT能夠有效延長(zhǎng)網(wǎng)絡(luò)的生命時(shí)間，這是因?yàn)镋BFT不但可以生成規(guī)模較小的活躍節(jié)點(diǎn)集，而且算法的構(gòu)建能耗較小。此外，EBFT還增加了支配節(jié)點(diǎn)的負(fù)載均衡，其網(wǎng)絡(luò)壽命相比EBCDS可提高17.1%。相反，DDA算法不但具有較高的支配節(jié)點(diǎn)規(guī)模和構(gòu)建能耗，所以它的網(wǎng)絡(luò)生命時(shí)間較短也是可以理解的。

圖6　實(shí)驗(yàn)3理想環(huán)境時(shí)的生命周期

為了能夠更加真實(shí)模擬網(wǎng)絡(luò)的實(shí)際環(huán)境，需要考慮節(jié)點(diǎn)出錯(cuò)的可能性，在每一輪中使用隨機(jī)數(shù)模擬節(jié)點(diǎn)是否出現(xiàn)故障。相比理想環(huán)境，圖7顯示各個(gè)算法的生命時(shí)間均有所下降，EBFT、AFTC和DDA出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)的時(shí)刻為783.1、567.2和448.5，同比分別提前了14.4、23.5和29.0個(gè)輪次。這里需要注意的是EBCDS在節(jié)點(diǎn)失效環(huán)境中的生命時(shí)間不如AFTC，它的第一個(gè)節(jié)點(diǎn)出現(xiàn)死亡的時(shí)間為581.8，相比理想環(huán)境超過了100輪，這是因?yàn)槊看纬霈F(xiàn)節(jié)點(diǎn)失效時(shí)都需要重新運(yùn)行拓?fù)渚S護(hù)，使得網(wǎng)絡(luò)重構(gòu)的次數(shù)增多，減少了能量的利用率。

5　總結(jié)

本文對(duì)異構(gòu)無線傳感器網(wǎng)絡(luò)模型進(jìn)行了擴(kuò)展，在異構(gòu)網(wǎng)絡(luò)模型中研究分布式容錯(cuò)數(shù)據(jù)收集算法。算法針對(duì)k-連通m-支配集規(guī)模過大的問題，轉(zhuǎn)換了容錯(cuò)拓?fù)錁?gòu)建的思想，在不需要節(jié)點(diǎn)位置信息的情況下，通過對(duì)活躍節(jié)點(diǎn)產(chǎn)生備份集的方法來生成容錯(cuò)拓?fù)?，這樣可以減少處于工作的支配節(jié)點(diǎn)數(shù)。此外，還考慮了節(jié)點(diǎn)能耗速率對(duì)網(wǎng)絡(luò)生命的影響，對(duì)數(shù)據(jù)收集過程進(jìn)行了優(yōu)化。理論分析對(duì)算法在同構(gòu)和異構(gòu)兩種網(wǎng)絡(luò)環(huán)境中需要增加的節(jié)點(diǎn)數(shù)情況進(jìn)行了分析，保證了算法產(chǎn)生的后備節(jié)點(diǎn)的連通性。仿真實(shí)驗(yàn)進(jìn)一步證明EBFT在能效性、擴(kuò)展性、可靠性上都具有較好的優(yōu)越性。

［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］馬晨明，王萬良，洪榛，等.帶有能量補(bǔ)給的異構(gòu)無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄑ芯浚跩］.電信科學(xué)，2015，31（8）：2015181.

［3］馬晨明，王萬良，洪榛.無線傳感器網(wǎng)絡(luò)中一種改進(jìn)的能效數(shù)據(jù)收集協(xié)議［J］.計(jì)算機(jī)科學(xué)，2015，42（2）：65-69.

［4］He J，Ji S L，F(xiàn)an 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］奎曉燕，杜華坤，梁俊斌.無線傳感器網(wǎng)絡(luò)中一種能量均衡的基于連通支配集的數(shù)據(jù)收集算法［J］.電子學(xué)報(bào)，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］鄭嬋，尹令，孫世新.無線傳感器網(wǎng)絡(luò)中2-連通k-支配的容錯(cuò)連通支配集構(gòu)造［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］付永生，李善平，周波.無線傳感網(wǎng)絡(luò)中能量均衡的連通支配集算法［J］.傳感技術(shù)學(xué)報(bào)，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］馬晨明，王萬良，洪榛.異構(gòu)無線傳感器網(wǎng)絡(luò)中基于CDS樹的拓?fù)淇刂品椒ǎ跩］.傳感技術(shù)學(xué)報(bào)，2014，27（6）：814-820.

［13］楊明霞，王萬良，馬晨明.一種基于反向CDS樹的異構(gòu)WSNs拓?fù)淇刂品椒ǎ跩］.傳感技術(shù)學(xué)報(bào)，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-），女，浙江衢州人，衢州學(xué)院講師。浙江工業(yè)大學(xué)在讀博士，研究方向?yàn)橛?jì)算機(jī)自動(dòng)化、無線傳感器網(wǎng)絡(luò)；

王萬良（1957-），男，江蘇高郵人，博士生導(dǎo)師。國(guó)家級(jí)教學(xué)名師、享受國(guó)務(wù)院特殊政府津貼、浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院院長(zhǎng)，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)化控制、無線網(wǎng)絡(luò)。

EEACC：723010.3969/j.issn.1004-1699.2016.06.024

面向節(jié)能和容錯(cuò)的異構(gòu)WSNs數(shù)據(jù)收集算法*

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

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

異構(gòu)無線傳感器網(wǎng)絡(luò)；連通支配集；數(shù)據(jù)收集；容錯(cuò)；負(fù)載均衡

TP393

A

1004-1699（2016）06-0934-07

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

項(xiàng)目來源：國(guó)家自然科學(xué)基金項(xiàng)目（61379123）；浙江省自然科學(xué)基金項(xiàng)目（LY15F020041，LY15F030014）；衢州學(xué)院師資隊(duì)伍建設(shè)基金項(xiàng)目（XNZQN201308）；寧波市社會(huì)發(fā)展基金項(xiàng)目（2014C50006）