無線傳感器網(wǎng)絡中一種基于移動Sink的數(shù)據(jù)收集算法*

張 蕾，張 堃，宋 軍

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

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

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

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

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

1 mWSN網(wǎng)絡體系結(jié)構(gòu)

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

圖1 移動無線傳感器網(wǎng)絡的層狀結(jié)構(gòu)圖

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

圖2 mWSN網(wǎng)絡結(jié)構(gòu)示意圖

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

圖3 mWSN簇－樹結(jié)構(gòu)示意圖

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

2 基于移動Sink的數(shù)據(jù)收集協(xié)議

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

2.1 移動 Sink

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

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

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

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

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

2.2 MSDG算法的基本思想

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

2.3 MSDG算法實現(xiàn)的主要步驟

MSDG算法的主要實現(xiàn)步驟歸納如下:

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

(2)形成簇，選擇Cluster，進行簇內(nèi)k個節(jié)點優(yōu)化調(diào)度；持續(xù)時間為TH。

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

(4)簇內(nèi)通信。簇內(nèi)工作節(jié)點根據(jù)TDMA時隙劃分策略順序?qū)⒏兄獢?shù)據(jù)Data_Msg傳輸給Cluster。Cluster將其存儲在緩沖區(qū)內(nèi)進行數(shù)據(jù)融合處理后，更新Data_Msg的data內(nèi)容，將ID統(tǒng)一換成Cluster的ID，再把融合后的Data_Msg轉(zhuǎn)發(fā)給相應的參考固定節(jié)點。持續(xù)時間為Tdl。

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

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

3 仿真與結(jié)果

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

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

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

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

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

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

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

表1 實驗參數(shù)

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

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

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

圖4 節(jié)點能耗比較

(2)節(jié)點死亡數(shù)量與時間的關系

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

圖5 3種算法網(wǎng)絡生命周期比較

4 總結(jié)

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

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

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

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

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

［5］李善倉，張克旺.無線傳感器網(wǎng)絡原理與應用［M］.北京:機械工業(yè)出版社，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］徐建波.無線傳感器網(wǎng)絡分布式分簇和節(jié)能的數(shù)據(jù)收集協(xié)議研究［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］李成岳，申鉉京，陳海鵬，等.無線傳感器網(wǎng)絡中LEACH路由算法的研究與改進［J］.傳感技術(shù)學報，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.