無線傳感器網絡高效數據收集算法研究

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

無線傳感器網絡高效數據收集算法研究

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

以有界均衡樹概念為基礎，隨機交換節點的數據轉發路徑，通過負載均衡來實現無線傳感器網絡數據采集樹的壽命最大化。提出一種簡單但更為有效的傳感器節點交換策略，提高收斂速度。此外，還提出該算法的一種低能耗分布式版本。仿真實驗結果表明，該算法可以有效提升數據收集樹的壽命，且時間復雜度低于其他當前算法。

無線傳感器網絡；數據收集；網絡壽命；有界均衡樹

湖南省科技計劃項目（No.2013SK3177、No.2014GK3145）、衡陽市科技計劃項目（No.2013KG68）、湖南工學院大學生創新項目（No.H1436）、湖南工學院校級科研項目（No.HY12008）

0　引言

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

1　相關工作

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

2　系統建模

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

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

ii表示為一次數據收集周期內從子節點收到的數據量。這里，一次數據收集周期表示Sink從所有傳感器節點收集數據的過程。

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

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

圖1　連通圖和3個可能的數據收集樹

3　LM-BBT算法

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

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

算法1：SWITCH（T）

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

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

3設va為負載最高結點；

4 while βa≤βmaxdo

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

6else

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

8while α≠? do

9按照FIFO次序把結點vj從α中刪除；

10W←FINDPOTENTIALPARENTS（G，vj）；

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

12else

13if SWITCHINGDECISION（pj）then

14從W中均勻選擇一個結點作為vj的新母結點

16else α←α∪Cj；

17UPDATETREE（T）；

18設置va為負載最大結點；

19then Return T；

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

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

算法2：FINDPOTENTIALPARENTS（G，vj）

1for G中vj的任意相鄰結點vido

3Return W；

算法3：UPDATETREE（T）

1對T按照自下而上遍歷順序為所有vi∈V計算γi；

2對T按照自上而下遍歷順序為所有vi∈V計算σi。

4　結語

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

［1］錢志鴻，王義君.面向物聯網的無線傳感器網絡綜述［J］.電子與信息學報，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］林愷，趙海，尹震宇，等.一種基于能量預測的無線傳感器網絡分簇算法［J］.電子學報，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－），女，湖南衡陽人，碩士，副教授，研究方向為無線傳感器網絡、智能信息處理

曾利軍（1976-），男，湖南邵東人，副教授，碩士研究生，研究方向為數據挖掘、最優控制、智能信息處理

高芳（1994－），女，湖南衡陽人，本科，在校學生，研究方向為無線傳感器網絡

李曉翠（1986-），女，湖南衡陽人，講師，碩士研究生，研究方向為智能信息處理

2016-04-12

2016-06-30