劉卉，曾利軍，高芳，李曉翠（湖南工學(xué)院計(jì)算機(jī)科學(xué)與信息學(xué)院，衡陽　421002）

無線傳感器網(wǎng)絡(luò)高效數(shù)據(jù)收集算法研究

劉卉，曾利軍，高芳，李曉翠
（湖南工學(xué)院計(jì)算機(jī)科學(xué)與信息學(xué)院，衡陽421002）

以有界均衡樹概念為基礎(chǔ)，隨機(jī)交換節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)路徑，通過負(fù)載均衡來實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集樹的壽命最大化。提出一種簡單但更為有效的傳感器節(jié)點(diǎn)交換策略，提高收斂速度。此外，還提出該算法的一種低能耗分布式版本。仿真實(shí)驗(yàn)結(jié)果表明，該算法可以有效提升數(shù)據(jù)收集樹的壽命，且時間復(fù)雜度低于其他當(dāng)前算法。

無線傳感器網(wǎng)絡(luò)；數(shù)據(jù)收集；網(wǎng)絡(luò)壽命；有界均衡樹

湖南省科技計(jì)劃項(xiàng)目（No.2013SK3177、No.2014GK3145）、衡陽市科技計(jì)劃項(xiàng)目（No.2013KG68）、湖南工學(xué)院大學(xué)生創(chuàng)新項(xiàng)目（No.H1436）、湖南工學(xué)院校級科研項(xiàng)目（No.HY12008）

0　引言

無線傳感器網(wǎng)絡(luò)（WSN）是近年來受到國內(nèi)外廣泛關(guān)注的研究熱點(diǎn)。無線傳感器網(wǎng)絡(luò)一般部署在條件惡劣或者人類很難進(jìn)入的環(huán)境中。在一個無線傳感器網(wǎng)絡(luò)中，分布著數(shù)量龐大的節(jié)點(diǎn)，這些節(jié)點(diǎn)往往被用戶用飛機(jī)或汽車運(yùn)輸，然后以隨機(jī)的方式放人指定區(qū)域執(zhí)行復(fù)雜的任務(wù)。數(shù)據(jù)收集是無線傳感器網(wǎng)絡(luò)中最重要的操作之一，能否有效地收集到合適的數(shù)據(jù)，直接關(guān)系到應(yīng)用的效果。由于WSN是由低功耗和能量受限的傳感器節(jié)點(diǎn)組成，WSN研究中的一個關(guān)鍵問題是設(shè)計(jì)有效的節(jié)能方案，以最大限度地提高網(wǎng)絡(luò)壽命。

1　相關(guān)工作

節(jié)能問題是目前無線傳感網(wǎng)中的研究熱點(diǎn)，相繼有眾多的學(xué)者提出了一系列方法用于延長無線傳感網(wǎng)絡(luò)壽命的方法，如林愷等人［4］提出一種利用能量預(yù)測選擇簇頭節(jié)點(diǎn)的分簇算法：CHEP利用文中建立的傳感器節(jié)點(diǎn)工作狀態(tài)轉(zhuǎn)換模型，CHEP算法將所得的剩余能量預(yù)測參數(shù)作為考慮因素引入閾值的計(jì)算，從而使高剩余能量且能耗較慢的節(jié)點(diǎn)能夠在每一輪中被優(yōu)先選為簇頭節(jié)點(diǎn)。仿真結(jié)果表明，CHEP能夠很好地平衡網(wǎng)絡(luò)負(fù)載，延長網(wǎng)絡(luò)壽命。曲家慶等人［5］基于拓?fù)浣Y(jié)構(gòu)的連通和覆蓋性建立節(jié)點(diǎn)的休眠調(diào)度模型，提出了一種優(yōu)化網(wǎng)絡(luò)壽命的新方法（CCLO）。該方法設(shè)計(jì)了一種根據(jù)節(jié)點(diǎn)剩余能量動態(tài)激活一組滿足連通覆蓋條件的工作節(jié)點(diǎn)，當(dāng)某個節(jié)點(diǎn)因能量耗盡而失效時，其鄰近的休眠節(jié)點(diǎn)將代替失效節(jié)點(diǎn)繼續(xù)維持網(wǎng)絡(luò)的正常工作。理論分析和仿真表明，CCLO能夠快速有效地判別冗余節(jié)點(diǎn)，保證無線傳感器網(wǎng)絡(luò)的覆蓋性和連通性的同時降低能耗，延長網(wǎng)絡(luò)壽命。張強(qiáng)等人［5］提出了一種新的數(shù)據(jù)聚合方案。分別對簇內(nèi)成員節(jié)點(diǎn)和簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)聚合處理，簇內(nèi)節(jié)點(diǎn)引入相對信息熵減少數(shù)據(jù)量的發(fā)送，而簇頭節(jié)點(diǎn)維持一個反饋比較值，當(dāng)接收到簇內(nèi)成員節(jié)點(diǎn)發(fā)送的數(shù)據(jù)或得到自身傳感器模塊的數(shù)據(jù)時，該值可以用來判斷是否轉(zhuǎn)發(fā)接收到的數(shù)據(jù)。通過與LEACH協(xié)議的仿真對比實(shí)驗(yàn)，結(jié)果表明新方案能有效減少網(wǎng)絡(luò)中的數(shù)據(jù)包傳送數(shù)目，降低節(jié)點(diǎn)能耗，并顯著地延長了網(wǎng)絡(luò)壽命。

2　系統(tǒng)建模

引入有界均衡樹概念，并展示最優(yōu)有界均衡樹如何解決壽命最大化問題。設(shè)G=（V，E）圖表示在監(jiān)測區(qū)域隨機(jī)部署的傳感器節(jié)點(diǎn)，其中V=｛v0，v1，…，vN｝表示與N個傳感器節(jié)點(diǎn)和Sinkv0對應(yīng)的頂點(diǎn)；E為表示傳感器間（無線）通信鏈路的邊集。假設(shè)傳感器部署的密度足夠大，可以保證G中無區(qū)域被隔離。我們稱G為N個傳感器的連通圖。

數(shù)據(jù)收集樹T=（VT，ET）是G=（V，E）的非周期性生成子圖，且Vj=V，Ej∈E，其中v0是第0層樹Ts的根。設(shè)L表示T中節(jié)點(diǎn)的最大層數(shù)。當(dāng)需要層數(shù)信息l時，節(jié)點(diǎn)可以表示為Vj；否則將出于簡便考慮而省略下標(biāo)。在圖G的有根生成樹T中，節(jié)點(diǎn)vi和vj如果有共同的母節(jié)點(diǎn)，則它們?yōu)榻忝霉?jié)點(diǎn)。節(jié)點(diǎn)vi的子節(jié)點(diǎn)集合表示為Ci。設(shè)M表示樹T中的葉節(jié)點(diǎn)集合。在圖G的不同數(shù)據(jù)收集樹中，可能有不同的路徑從vj通往Sink。我們將Tk表示為圖G第k個數(shù)據(jù)收集樹表示Tk中從vi到v0的路徑。以節(jié)點(diǎn)vi為根的子樹表示為T（vi），而節(jié)點(diǎn)vi的當(dāng)前能量預(yù)算表示為e。我們將v的數(shù)據(jù)接收率

ii表示為一次數(shù)據(jù)收集周期內(nèi)從子節(jié)點(diǎn)收到的數(shù)據(jù)量。這里，一次數(shù)據(jù)收集周期表示Sink從所有傳感器節(jié)點(diǎn)收集數(shù)據(jù)的過程。

vi的數(shù)據(jù)生成率定義為一次數(shù)據(jù)收集周期內(nèi)vi生成的數(shù)據(jù)量。類似地，vi的數(shù)據(jù)發(fā)送率定義為一次數(shù)據(jù)收集周期內(nèi)vi發(fā)送的數(shù)據(jù)量。我們將vi的能量損失率ri定義為vi花費(fèi)在數(shù)據(jù)收集周期期間的能量。對所有節(jié)點(diǎn)，用Et和Ec表示用于數(shù)據(jù)傳輸和接收的單位能量。數(shù)據(jù)生成的能耗則忽略不計(jì)［5］。因此，vi的能量損失率為。我們最后定義節(jié)點(diǎn)vi的負(fù)載γi為 ri與ei的比。請注意，在本文模型中，節(jié)點(diǎn)vi的壽命定義為。

圖1給出了連通圖和三種不同的數(shù)據(jù)收集樹T1，T2，T3。在該圖中，節(jié)點(diǎn)vi表示為vi。數(shù)據(jù)收集樹邊上的數(shù)字表示每次數(shù)據(jù)收集周期沿著該邊傳輸?shù)膯挝粩?shù)據(jù)量。在該例中，出于簡便考慮，假設(shè)每個節(jié)點(diǎn)的能量預(yù)算和數(shù)據(jù)生成率均為1。根據(jù)定義，樹的最大負(fù)載為3個單位，而樹T1，T2為4個單位。因?yàn)橐粋€節(jié)點(diǎn)的壽命與其負(fù)載成反比，所以樹T3首個節(jié)點(diǎn)能量用完的時間要早于樹T1，T2。

圖1　連通圖和3個可能的數(shù)據(jù)收集樹

3　LM-BBT算法

本文通過利用樹變換和節(jié)點(diǎn)交換策略來均衡數(shù)據(jù)收集樹的路徑負(fù)載。以圖1為例，通過丟棄邊（v2，v7）并加入邊（v7，v3）可以將樹T1變換為樹T2?？紤]到以vi為根的子樹表示為T（vi），通過這一操作，經(jīng)由v7將樹T （v2）變換為樹T（v3）。類似地，我們可以將T（v1）從T（vi）變換到T（v3）上，利用T1獲得T3s。出于簡便性考慮，我們再次假設(shè)對圖中的所有節(jié)點(diǎn)有ei=1，=1。在T3中，對第1層的每個節(jié)點(diǎn)有=2且Rti=3。如果Et=Ec=1，則v1，v2，v3的負(fù)載均為5個單位。根據(jù)定義3，所有葉節(jié)點(diǎn)的路徑負(fù)載也為5個單位。因此，對T3，路徑負(fù)載得到了完美的均衡。下面將詳細(xì)闡述本文提出的基于有界均衡樹的網(wǎng)絡(luò)壽命最大化算法LM-BBT。

LM-BBT算法主要包括3個函數(shù)：交換函數(shù)，潛在母節(jié)點(diǎn)搜索函數(shù)和更新樹函數(shù)。交換函數(shù)是LM-BBT的函數(shù)，而潛在母節(jié)點(diǎn)搜索函數(shù)用于當(dāng)節(jié)點(diǎn)被選擇用于交換時為其選擇合適的母節(jié)點(diǎn)。最后，更新樹函數(shù)可以更新節(jié)點(diǎn)的負(fù)載及路徑負(fù)載。

算法1：SWITCH（T）

1為每個vi∈V初始化（γi，σi）；

2為每個vi∈V設(shè)置β←0和Pi←1/2；

3設(shè)va為負(fù)載最高結(jié)點(diǎn)；

4 while βa≤βmaxdo

5if max｛σiM｝-min｛σiM｝≤δ then Return T；

6else

7Set α←Ca；將βa加1；

8while α≠? do

9按照FIFO次序把結(jié)點(diǎn)vj從α中刪除；

10W←FINDPOTENTIALPARENTS（G，vj）；

11if W=? then α←α∪Cj；

12else

13if SWITCHINGDECISION（pj）then

14從W中均勻選擇一個結(jié)點(diǎn)作為vj的新母結(jié)點(diǎn)

16else α←α∪Cj；

17UPDATETREE（T）；

18設(shè)置va為負(fù)載最大結(jié)點(diǎn)；

19then Return T；

算法1描述了交換函數(shù)，其中βi表示γi被選為最高負(fù)載節(jié)點(diǎn)的次數(shù)。此外，βmax表示一個節(jié)點(diǎn)可被選擇進(jìn)行交換的最大次數(shù)。我們稍后將討論如何調(diào)整βmax以實(shí)現(xiàn)收斂。最后，pi表示交換概率。首先，對已知樹T的所有節(jié)點(diǎn)的負(fù)載和路徑負(fù)載初始化。交換次數(shù)初始值和所有節(jié)點(diǎn)的初始交換概率分別設(shè)為0和1/2（第1-2行）。然后，選擇負(fù)載最高的節(jié)點(diǎn)va（第3行）。持續(xù)交換步驟，直到某個節(jié)點(diǎn)被選擇βmax次（第4行）。此時，while循環(huán)終止，返回更新樹（第19行）。在循環(huán)內(nèi)，如果到達(dá)δ有界條件，則返回樹。否則，Vα的子節(jié)點(diǎn)插入隊(duì)列α（第7行），且更新Vαs的計(jì)數(shù)。第2個循環(huán)一直持續(xù)，直到隊(duì)列為空（第8行）。在每一步驟中，將節(jié)點(diǎn)vj從隊(duì)列移除，且隊(duì)列W中元素均是其潛在母節(jié)點(diǎn)（第9-10行）。如果vj無任何潛在母節(jié)點(diǎn)，則把vj的子節(jié)點(diǎn)加入隊(duì)列，且考慮這些節(jié)點(diǎn)進(jìn)行后續(xù)步驟的交換過程（第11行）。將在本文小節(jié)稍后討論vj的潛在母節(jié)點(diǎn)選擇問題。如果vj有可與之交換的潛在母節(jié)點(diǎn)，則通過交換決策函數(shù)根據(jù)其當(dāng)前交換概率來做出隨機(jī)決策。如果決策結(jié)果是進(jìn)行交換，則以均勻概率從列表中選擇節(jié)點(diǎn)作為vj的新母節(jié)點(diǎn)。否則，vj與其當(dāng)前母節(jié)點(diǎn)保持，把的子節(jié)點(diǎn)加入隊(duì)列供后續(xù)處理（第13-16行）。請注意，當(dāng)vj被交換時，并不考慮對其子節(jié)點(diǎn)進(jìn)行交換，因?yàn)樵趘j交換之后，整個子樹T（vj）通過新的母節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。當(dāng)隊(duì)列為空時，表明va子節(jié)點(diǎn)的交換已經(jīng)完成。用新的節(jié)點(diǎn)負(fù)載和路徑負(fù)載數(shù)值對樹進(jìn)行更新，在下一輪中選擇負(fù)載最高的節(jié)點(diǎn)（第17-18行）。

算法2中的潛在母節(jié)點(diǎn)搜索函數(shù)可以返回已知節(jié)點(diǎn)vi的潛在母節(jié)點(diǎn)列表。具體來說，如果它的路徑負(fù)載低于vj的路徑負(fù)載且相關(guān)幅度超過δ，則vj的相鄰節(jié)點(diǎn)vi加入相應(yīng)的潛在母節(jié)點(diǎn)列表。在每次交換過程中，算法3中的樹更新函數(shù)可以獲得樹中每個節(jié)點(diǎn)vi的新數(shù)值（γi，σi）。

算法2：FINDPOTENTIALPARENTS（G，vj）

1for G中vj的任意相鄰結(jié)點(diǎn)vido

3Return W；

算法3：UPDATETREE（T）

1對T按照自下而上遍歷順序?yàn)樗衯i∈V計(jì)算γi；

2對T按照自上而下遍歷順序?yàn)樗衯i∈V計(jì)算σi。

4　結(jié)語

本文提出一種高效的隨機(jī)交換算法LM-BBT，通過負(fù)載均衡來實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集樹的壽命最大化。本文方法以有界均衡樹概念為基礎(chǔ)，隨機(jī)交換節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)路徑。我們提出一種簡單但更為有效的傳感器節(jié)點(diǎn)交換策略，提高了收斂速度。我們還提出了本文算法的一種低能耗分布式版本。仿真結(jié)果證明，本文算法可以有效提升數(shù)據(jù)收集樹的壽命，且時間復(fù)雜度低于其他當(dāng)前算法。在下一步工作中，我們將研究δ對各種場景下壽命的影響。此外，我們還將把交換概率描述為不同網(wǎng)絡(luò)參數(shù)（例如密度、度數(shù)）的函數(shù)，以降低收斂時間。

［1］錢志鴻，王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述［J］.電子與信息學(xué)報，2013，35（1）∶215-227.

［2］Aderohunmu F A，Paci G，Brunelli D，et al.An Application-Specific Forecasting Algorithm for Extending WSN Lifetime［C］.Distributed Computing in Sensor Systems（DCOSS），2013 IEEE International Conference on.IEEE，2013∶374-381.

［3］Asorey-Cacheda R，García-Sánchez A J，García-Sánchez F，et al.On Maximizing the Lifetime of Wireless Sensor Networks by Optimally Assigning Energy Supplies［J］.Sensors，2013，13（8）∶10219-10244.

［4］林愷，趙海，尹震宇，等.一種基于能量預(yù)測的無線傳感器網(wǎng)絡(luò)分簇算法［J］.電子學(xué)報，2008，36（4）∶824-828.

［5］Buragohain C，Agrawal D，Suri S.Power Aware Routing for Sensor Databases［C］.INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE.IEEE，2005，3∶1747-1757.

Wireless Sensor Networks；Data Gathering；Lifetime of Networks；Bounded Balanced Tree

Research on Efficient Data Gathering Algorithm for Wireless Sensor Networks

LIU Hui，ZENG Li-jun，GAO Fang，LI Xiao-cui
（Department of Computer and InformationScience，Hunan Institute of Technology，Hengyang 421002）

Based on the concept of the bounded balanced trees，our algorithm randomly switches the data forwarding paths of nodes，and the lifetime of data gathering tree of WSN is maximization through the load balancing.Provides a simple yet effective switching strategy for the sensor nodes，resulting into faster convergence.Presents a distributed implementation of our scheme with low energy overhead.The simulation results confirm that our approaches can significantly increase the lifetime of data collection trees with a lower time complexity than other existing schemes.

1007-1423（2016）20-0010-04

10.3969/j.issn.1007-1423.2016.20.002

劉卉（1980－），女，湖南衡陽人，碩士，副教授，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、智能信息處理

曾利軍（1976-），男，湖南邵東人，副教授，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、最優(yōu)控制、智能信息處理

高芳（1994－），女，湖南衡陽人，本科，在校學(xué)生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)

李曉翠（1986-），女，湖南衡陽人，講師，碩士研究生，研究方向?yàn)橹悄苄畔⑻幚?/p>

2016-04-12

2016-06-30