張 蕾，張 堃，宋 軍

(北京建筑工程學(xué)院計(jì)算機(jī)教學(xué)與網(wǎng)絡(luò)信息部，北京 100044)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 移動(dòng) Sink

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

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

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

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

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

2.2 MSDG算法的基本思想

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

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

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

(1)分布式分簇算法開(kāi)始，每個(gè)固定節(jié)點(diǎn)發(fā)送Fixednode_Msg報(bào)文，移動(dòng)節(jié)點(diǎn)接受Fixednode_Msg報(bào)文并計(jì)算與周?chē)潭ü?jié)點(diǎn)的距離，選擇距離最近的作為參考固定節(jié)點(diǎn)；持續(xù)時(shí)間為T(mén)c。

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

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

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

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

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

3 仿真與結(jié)果

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

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

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

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

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

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

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

表1 實(shí)驗(yàn)參數(shù)

(1)移動(dòng)Sink與靜止Sink的對(duì)比分析

將MSDG與LEACH進(jìn)行比較，LEACH中Sink靜止不動(dòng)，而MSDG中的Sink是可移動(dòng)的。

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

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

(2)節(jié)點(diǎn)死亡數(shù)量與時(shí)間的關(guān)系

圖5是LEACH、ACE-L和MSDG 3種數(shù)據(jù)收集算法的網(wǎng)絡(luò)生存期比較圖?？梢钥闯?，MSDG的節(jié)點(diǎn)生存時(shí)間相對(duì)LEACH、ACE-L都有顯著提高，網(wǎng)絡(luò)生存期得以延長(zhǎng)。

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

4 總結(jié)

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

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

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

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

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

［5］李善倉(cāng)，張克旺.無(wú)線傳感器網(wǎng)絡(luò)原理與應(yīng)用［M］.北京:機(jī)械工業(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ú)線傳感器網(wǎng)絡(luò)分布式分簇和節(jié)能的數(shù)據(jù)收集協(xié)議研究［D］.長(zhǎng)沙:湖南大學(xué)，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ú)線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，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.