無線傳感器網絡中一種基于移動Sink的數據收集算法*

張 蕾，張 堃，宋 軍

(北京建筑工程學院計算機教學與網絡信息部，北京 100044)

隨著物聯網技術、嵌入式技術以及低功耗的無線通信技術的發展，生產具備感應、無線通信以及信息處理能力的微型無線傳感器已成為可能，這些廉價的、低功耗的傳感器節點共同組織成無線傳感器網絡WSNs(Wireless Sensor Networks)，通過節點間的相互協作，將其監測和感應到的信息(溫度、濕度等)傳送到基站(Sink)，實現網絡數據收集功能。利用WSN進行數據收集可以應用到許多重要領域，如國防軍事、環境監測、交通管理、醫療衛生、抗震救災等［1］。

靜態無線傳感器網絡的研究，前提都是假設節點保持不動。但近年來提出的移動無線傳感器網絡mWSN(mobile WSN)概念，是針對某些實際應用中無線傳感器節點的移動是不可避免的，例如:監測野生動物生活習慣、追蹤醫院病人心跳情況［2－3］；還有交通指揮中心根據安裝在汽車上的傳感器節點來獲知、分析和處理這一地區的交通流量，進而發布實時有效的交通調度信息等。

數據收集是WSN研究的重點。隨著近年mWSN成為學術界的研究熱點，原來針對靜態無線傳感器網絡的數據收集協議由于網絡中的傳感器節點或Sink節點的移動引起的網絡拓撲變化、路徑失效等問題，已經不能應用到mWSN。因此針對mWSN的數據收集協議的研究在國內外得到了廣泛的重視。

本文從mWSN數據收集角度出發，基于分簇技術，利用移動Sink來解決多跳路由通信中的“熱區”問題，延長了網絡的生存期。

1 mWSN網絡體系結構

在進行網絡部署時，采取確定性部署與隨機部署相結合的特點，網絡中的移動傳感器節點是隨機部署，與此同時根據應用的需要部署一定數目的固定參考節點，這樣既能較好地適應網絡動態拓撲變化，又能構建較為穩定的網絡拓撲，達到節省能耗的目的。mWSN網絡層狀結構如圖1所示。將網絡分成固定數量、大小均勻的簇，每一個簇內有一個參考固定節點，一個簇頭節點(Cluster)和多個簇內成員節點。底層是簇內節點與Cluster的通信，上層是固定節點之間的通信。

圖1 移動無線傳感器網絡的層狀結構圖

圖2為mWSN網絡結構示意圖，n個傳感器節點部署在一個監測區域，根據應用的需要，除了在正方形網格上部署m個固定節點外，還在監測區域隨機均勻部署n－m個移動節點。其中的每一個固定節點坐標位置可知，移動節點的位置不可知，Cluster是通過分簇算法從移動節點中選出的。

圖2 mWSN網絡結構示意圖

WSN中的節點通過分簇算法被劃分成不同的簇，每個簇的形成都是由一個固定節點作為參考的，所以每一個簇由某個固定節點、一個Cluster和多個簇內成員節點組成，所有固定節點形成以Sink為根的一顆路由匯集樹［4－5］。圖3 描述了分簇網絡中的數據流［6］。

圖3 mWSN簇－樹結構示意圖

在圖3所示的簇－樹拓撲結構中，成員節點將數據發送給各自的Cluster，Cluster將數據融合后發送給對應的固定節點，再經由其它的中間固定節點路由發送到Sink。由于節點的移動性和Cluster負責簇內的通信調度，相對簇內成員節點，Cluster將消耗更多的能量。因此，網絡將定期地重新進行分簇，選擇能量較高的且距離固定節點最近的移動節點擔任Cluster，從而將所有負載均勻地分布到所有節點。該簇－樹拓撲結構既能實現高效節能，又能降低數據包碰撞的幾率，使得整個mWSN有較好的數據吞吐量［7］。

2 基于移動Sink的數據收集協議

本文主要研究在基于分簇技術的mWSN數據收集協議中使用移動Sink解決多跳路由通信中的“熱區”問題。

2.1 移動 Sink

mWSN中有節點移動和Sink移動。Sink移動可以延長網絡的生命周期，因為在一個部署固定Sink的WSN中，在數據收集過程中，Sink周圍的一跳節點會以更快的速度消耗完自己的能量。而在Sink移動的mWSN中，由于Sink的移動，其周圍的一跳節點在不斷變換，所以在多跳路由通信中，能使網絡中所有節點的能量消耗處在一個平均水平，顯著延長網絡的壽命，避免因多跳路由而出現能量空洞的“熱區”。

很多人已經認識到利用移動Sink來延長傳感器網絡生命周期的潛在好處。由于在不同時刻，多跳路由會隨時間、Sink位置而改變，因此，對于Sink移動問題，具有一定的理論難度。Yi等人在文獻［8］中，提出了一種移動Sink最佳運動理論。

美國Berkeley大學 S.R.Madden等在文獻［9］中將WSN分為事件驅動和連續監測兩種類型。在事件驅動類型的WSN應用中，如果網絡中的Sink是可移動的，那么Sink向事件感知區域移動就能減少中轉節點的數量，從而降低能量開銷。

EARM［10］假設節點的發射功率可以調整，如果Sink距離路徑最后一跳節點的距離越來越遠，那么該節點不斷增大自己的發射功率來保持和Sink的連接，當距離遠到即使節點以最大發射功率也不能滿足維持連接的時候，移動Sink尋找一個新的鄰居節點，這個過程不斷持續下去。

分布式動態共享樹協議DST(Distributed Dynamic Shared Tree)［11］是一個在Sink高速移動的環境下，高效率、低時延的數據融合協議。DST采用基于Sink的生成樹方法，根據Sink的移動軌跡，很好地保持與Sink的通信，解決了過度的能量消耗和Sink位置更新消息的協議中增加的碰撞等問題。

2.2 MSDG算法的基本思想

本文提出一種基于移動Sink的數據收集協議MSDG(Mobile Sink-based Data Gathering)。當 Sink收集數據時，直接向自己的鄰居固定節點發起數據查詢請求報文；經分簇后，Sink根據移動軌跡沿途以最近的固定節點作為根節點動態構建由固定節點組成的路由樹；各個移動節點感知的數據經Cluster進行數據融合計算，然后將融合后的數據沿路由樹反向逐跳轉發給Sink節點。

2.3 MSDG算法實現的主要步驟

MSDG算法的主要實現步驟歸納如下:

(1)分布式分簇算法開始，每個固定節點發送Fixednode_Msg報文，移動節點接受Fixednode_Msg報文并計算與周圍固定節點的距離，選擇距離最近的作為參考固定節點；持續時間為Tc。

(2)形成簇，選擇Cluster，進行簇內k個節點優化調度；持續時間為TH。

(3)Sink給距離最近的固定節點發送Sink_Msg報文廣播，相鄰的固定節點收到廣播后，若是第一次收到，則將發送者作為父節點，對固定節點進行時隙劃分。然后繼續向鄰居固定節點轉發Sink_Msg報文直到源數據結束到構造樹的葉子節點。持續時間為Tt。

(4)簇內通信。簇內工作節點根據TDMA時隙劃分策略順序將感知數據Data_Msg傳輸給Cluster。Cluster將其存儲在緩沖區內進行數據融合處理后，更新Data_Msg的data內容，將ID統一換成Cluster的ID，再把融合后的Data_Msg轉發給相應的參考固定節點。持續時間為Tdl。

(5)簇間通信。固定節點將數據沿路由樹反向多跳路由到Sink節點。持續時間為Td2。

與文獻［12］中的數據收集協議一樣，本文提出的MSDG算法由Sink啟動，Sink采用泛洪廣播Init_Msg消息，內容包括 Tc，TH，Tt和 Td以及時間同步指令，進而觸發網絡的分簇進程。

3 仿真與結果

本節對 MSDG 與 LEACH［13－14］、ACE-L［15］進行仿真比較。

LEACH(Low Energy Adaptive Clustering Hierarchy)是典型的簇型數據收集協議，它將整個WSN劃分為多個邏輯上的簇，通過隨機的方式選舉Cluster，Cluster負責調度簇內所有節點的數據傳輸，并將簇內節點監測到的數據進行數據融合后，再傳送給Sink。LEACH的基本思想是通過隨機循環地選擇Cluster，從而將整個網絡的能量負載平均分配到每個傳感器節點中，達到降低網絡能源消耗、提高網絡整體生存時間的目的。但Cluster分布不均勻，Cluster和Sink單跳通信，對Cluster通信能力能耗要求比較高，分簇協議的性能依賴網絡結構、系統模型和應用場景。

ACE-L(Location-Based Algorithm for Cluster Establishment)是一種具有良好反饋機制的自適應分布式成簇算法。簇的形成包括簇的產生和簇的遷移兩個邏輯部分。基于相鄰節點之間的信息反饋，每個節點獨立運行ACE-L，最終由兩個邏輯部分交叉迭代形成簇。ACE-L具有良好的健壯性，對節點失效和報文丟失反應迅速，生成的簇能有效減少相互之間的重疊，降低簇間通信干擾的概率，并且成簇收斂速度與網絡規模無關，簇的分布均勻，性能優于LEACH，但是沒有考慮節點移動快慢等因素，節點的通信半徑限制了該算法只能適用于小范圍數據收集的WSN。

WSN中衡量數據收集協議性能的一個主要指標是網絡的生命周期，網絡的生命周期用網絡生存節點數與網絡運行輪數的關系表述。本文采用與文獻［12］相同的無線傳感器網絡能量耗費模型。

式(1)為發射k比特數據耗損的能量ETx的計算公式，由發射電路耗損和功率放大耗損兩部分構成。功率放大耗損則根據發送者和接收者之間的距離分別采用自由空間模型和多路徑衰減模型，Eelec為發射電路的耗損能量，εfs為自由空間信道模型下功率放大所需能量、εmp為多路徑衰減信道模型下功率放大所需能量。

式(2)為接收k比特數據的能量耗損ERx的計算公式，僅由電路耗損引起。

實驗中，監視區域要求100%被覆蓋(即簇內所有節點都為活動節點)。實驗中未考慮緊急數據的處理。實驗結果均為100次獨立實驗結果的均值，每次獨立實驗都采用不同的隨機拓撲。取上式中參數為:Eelec=50 nJ/bit，εmp=0.0013 pJ/(bit·m4)，εfs=13 pJ/(bit·m2)，d=85 m。此外，對數據信號進行融合等處理時也將耗損能量，由Efusion表示融合單個數據信號所耗損的能量。對于任一Cluster，假設其簇內成員節點數為q，則將q個成員節點的數據信號和自身的數據信號融合為一個有效信號耗費的能量為Ecomp=(q+1)·Efusion·k。仿真實驗參數見表1。

表1 實驗參數

(1)移動Sink與靜止Sink的對比分析

將MSDG與LEACH進行比較，LEACH中Sink靜止不動，而MSDG中的Sink是可移動的。

圖4表明，MSDG中節點的能耗大約只有保持靜止情況下的一半，延長了網絡生命周期。

圖4 節點能耗比較

(2)節點死亡數量與時間的關系

圖5是LEACH、ACE-L和MSDG 3種數據收集算法的網絡生存期比較圖。可以看出，MSDG的節點生存時間相對LEACH、ACE-L都有顯著提高，網絡生存期得以延長。

圖5 3種算法網絡生命周期比較

4 總結

本文提出了基于移動Sink的數據收集協議MSDG，Sink沿途以最近的固定節點作為根節點動態構建由固定節點組成的路由樹，Cluster收集簇內所有普通節點的數據后做數據融合計算，將融合后的數據沿路由樹反向傳給Sink。仿真顯示MSDG在節點的平均能耗和網絡生存時間等方面的性能遠超過LEACH、ACE-L等算法。

［1］李虹.無線傳感器網絡中節能相關若干關鍵問題研究［D］.中國科學技術大學，2007:7－8.

［2］趙澤，崔莉.一種基于無線傳感器網絡的遠程醫療監護系統［J］.信息與控制，2006，35(2):265－269.

［3］楊靖，洪露，李澤滔，等.無線傳感器網絡中一種高能效數據收集協議［J］.傳感技術學報，2011，24(5):742－746.

［4］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京理工大學出版社，2007:8.

［5］李善倉，張克旺.無線傳感器網絡原理與應用［M］.北京:機械工業出版社，2008:3.

［6］Ossama Younis，Marwan Krunz，Srinivasan Ramasubramanian，et al.Node Clustering in Wireless Sensor Networks:Recent Developments and Deployment Challenges［J］.IEEE Network，June，2006.

［7］Tri Pham，Eun Jik Kim，Melody Moh.On Data Aggregation Quality and Energy Efficiency of Wireless Sensor Network Protocols-Extended Summary［C］//First International Conference on Broadband Networks.2004.730－732.

［8］Yi Shi Y.Thomas Hou.Theoretical Results on Base Station Movement Problem for Sensor Network［C］//The IEEE INFOCOM 2008 Proceedings.

［9］Luo J，Panchard J，Piorkowski M，et al.Mobi-Route:Routing towards a Mobile Sink for Improving Lifetime in Sensor Networks［C］//Proc.of the Int’l Conf on Distributed Computing in Sensor Systems，2006.

［10］Ye F，Zhong G，Lu S，et al.GRAdient Broadcast:A Robust Data Delivery Protocol for Large Scale Sensor Networks［J］.ACM Wireless Networks(WINET)，2005，11(2): － .

［11］KWang-il Hwang，Jeong Sik In，Doo-seop Eom.Distributed Dynamic Shared Tree for Minimum Energy Data Aggregation of Multiple Mobile Sinks in Wireless Sensor Networks［C］//EWSN O6，LNCS 3868，2006:132－147.

［12］徐建波.無線傳感器網絡分布式分簇和節能的數據收集協議研究［D］.長沙:湖南大學，2008.

［13］Wendi Rabiner Heinzelman，Anantha Chandrakasan，Hari Balakrishnan.Energy-Efficient Communication Protocol for Wireless Micro-Sensor Networks［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000.3005－3014.

［14］李成岳，申鉉京，陳海鵬，等.無線傳感器網絡中LEACH路由算法的研究與改進［J］.傳感技術學報，2010，23(8):1163－1167.

［15］Chuan-Ming Liu，Chuan-Hsiu Lee，Li-Chun Wang.Distributed Clustering Algorithms for Data-Gathering in Wireless Mobile Sensor Networks［J］.Journal of Parallel and Distributed Computing，2007，67(11):1187－1200.