一種應(yīng)急環(huán)境下無線傳感網(wǎng)節(jié)點接入與定向擴散方法

王 群 錢煥延 戚 湧 李千目 詹國勝

(1南京理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，南京 210094)

(2江蘇警官學(xué)院計算機信息與網(wǎng)絡(luò)安全系，南京 210031)

以數(shù)據(jù)為中心的無線傳感網(wǎng)把自然界中客觀存在的非信息技術(shù)元素通過各類接入方式主動融入信息網(wǎng)絡(luò)，引發(fā)了信息感知領(lǐng)域的一場新變革［1］.通過加強對無線傳感網(wǎng)在各類突發(fā)和應(yīng)急事件中的應(yīng)用研究和實戰(zhàn)創(chuàng)新，可充分發(fā)揮科技優(yōu)勢，有效降低事件造成的危害和影響.在應(yīng)急環(huán)境中，災(zāi)難的發(fā)生通常具有不可預(yù)見性和不可抗拒性，且災(zāi)難發(fā)生區(qū)域通常具有環(huán)境復(fù)雜惡劣、人員不方便或無法到達(dá)等特點，致使傳統(tǒng)的無線傳感網(wǎng)在節(jié)點部署、通信延時、信號區(qū)域覆蓋、節(jié)點能量損耗等方面受到制約［2-3］.在應(yīng)急救援過程中，移動節(jié)點由救援人員和移動機器人攜帶的個體傳感器組成.如果能夠提供一種將移動節(jié)點加入無線傳感網(wǎng)的機制，不僅可以靈活高效地獲取指定區(qū)域的現(xiàn)場信息，而且可以填補網(wǎng)絡(luò)中的監(jiān)測盲點，擴大對應(yīng)急環(huán)境的感知范圍，進(jìn)一步發(fā)揮無線傳感網(wǎng)在應(yīng)急救援中的應(yīng)用優(yōu)勢.

在應(yīng)急環(huán)境中，無線傳感網(wǎng)監(jiān)測系統(tǒng)應(yīng)具備的條件包括能對突發(fā)事件做出快速反應(yīng)、可實時查詢某一區(qū)域或某個監(jiān)測點的情況、可快速查詢某一監(jiān)測內(nèi)容出現(xiàn)異常的具體位置等.本文綜合分析了無線傳感網(wǎng)中基于分配、競爭和混合型這3種MAC協(xié)議類型［4-6］的特點，同時對 S-MAC 協(xié)議［7］、TMAC 協(xié)議［8］、B-MAC 協(xié)議［9］和 X-MAC 協(xié)議［10］等典型的競爭型MAC協(xié)議進(jìn)行討論，在此基礎(chǔ)上設(shè)計出一種基于X-MAC協(xié)議的移動節(jié)點接入機制.為了解決傳統(tǒng)定向擴散(directed diffusion，DD)路由算法中由于興趣擴散階段向全網(wǎng)廣播興趣報文而導(dǎo)致的流量和能耗過大問題，提出了一種興趣有效傳播路徑判定規(guī)則.該規(guī)則通過探測興趣有效傳播路徑，利用節(jié)點的位置信息使興趣的擴散具有明確的方向性.仿真實驗中，對傳統(tǒng)路由算法和改進(jìn)后的路由算法分別進(jìn)行了測試，并對結(jié)果進(jìn)行了對比分析.

1 系統(tǒng)結(jié)構(gòu)與節(jié)點接入設(shè)計

圖1 系統(tǒng)總體結(jié)構(gòu)

應(yīng)急環(huán)境下的無線傳感網(wǎng)系統(tǒng)結(jié)構(gòu)如圖1所示.現(xiàn)假設(shè)災(zāi)難發(fā)生區(qū)域為一個二維平面結(jié)構(gòu)，大量位置固定的傳感器節(jié)點隨機部署在監(jiān)測區(qū)域內(nèi)，個體傳感器作為移動節(jié)點在監(jiān)測區(qū)域內(nèi)根據(jù)工作要求自由移動，并與其他節(jié)點建立通信連接.整個監(jiān)測系統(tǒng)由監(jiān)測中心(又稱上位機)及配套服務(wù)器和無線傳感網(wǎng)2個部分組成.其中，可同時配備多種傳感器的無線傳感器節(jié)點負(fù)責(zé)采集并上傳其感知半徑范圍內(nèi)的環(huán)境信息;匯聚節(jié)點(Sink節(jié)點)作為無線傳感網(wǎng)與監(jiān)測中心的協(xié)調(diào)者，實現(xiàn)信息的上傳下達(dá)功能［11］.

移動節(jié)點接入網(wǎng)絡(luò)主要有被動接入和主動接入2種方式.在主動接入方式中，移動節(jié)點主動向周圍的靜止節(jié)點持續(xù)廣播請求接入消息，靜止節(jié)點收到請求接入消息后向移動節(jié)點發(fā)送響應(yīng)消息，從而建立連接.這種方式的接入延遲較小，而且靜止節(jié)點無需定期廣播邀請報文，減少了能量消耗;然而，移動節(jié)點廣播接入請求報文之前必須確認(rèn)無線信道空閑，避免干擾其他節(jié)點的正常通信.在應(yīng)急監(jiān)測系統(tǒng)中，個體傳感器節(jié)點能快速地在網(wǎng)絡(luò)內(nèi)穿梭，并對接入的響應(yīng)時間有較高的要求.因此，本文采用主動接入方式，實現(xiàn)對移動節(jié)點接入與動態(tài)鏈路的維護.具體過程可分為以下2個階段(見圖2):

圖2 B-MAC協(xié)議和X-MAC協(xié)議收發(fā)示意圖

①移動節(jié)點的接入過程.如圖3所示，移動節(jié)點在發(fā)起接入請求之前，首先偵聽信道是否空閑(偵聽時間設(shè)為tdm).若確認(rèn)信道空閑，則廣播接入請求消息，接入請求消息以頻閃前導(dǎo)碼的方式發(fā)送，頻閃間隔為tf，一次接入請求的最長持續(xù)時間為treq.若在時間treq內(nèi)移動節(jié)點未收到接入應(yīng)答信息，則重新偵聽信道是否空閑，進(jìn)入下一個偵聽-廣播接入請求階段，從而避免移動節(jié)點因長期占用信道資源而影響其他節(jié)點的正常通信.若在時間treq內(nèi)移動節(jié)點收到其他節(jié)點的接入應(yīng)答信息，則向源節(jié)點發(fā)送接入應(yīng)答確認(rèn)消息，從而建立通信連接.靜止節(jié)點收到移動節(jié)點的接入請求消息后，利用移動節(jié)點頻閃前導(dǎo)之間的間隔向移動節(jié)點發(fā)送移動接入應(yīng)答消息，并等待接收移動節(jié)點發(fā)送的接入應(yīng)答確認(rèn)消息.為了防止多個靜止節(jié)點收到接入請求消息后同時發(fā)送接入應(yīng)答消息而發(fā)生碰撞，需要采用一種避免沖突的機制.簡單起見，本文選擇每個靜止節(jié)點隨機產(chǎn)生一個數(shù)R(R∈［0，1］)，并與一個預(yù)先設(shè)定的固定值Rm比較.如果R≤Rm，則節(jié)點在當(dāng)前的間隙發(fā)送接入應(yīng)答消息;否則，等待下一個間隙重新進(jìn)行判斷.靜止節(jié)點在等待下一個間隙到來的過程中，如果在超時時間t0內(nèi)沒有再次收到移動節(jié)點的接入請求消息，則轉(zhuǎn)入睡眠狀態(tài)以防止過度偵聽而消耗能量.若靜止節(jié)點收到其他節(jié)點的接入應(yīng)答消息，則立刻退出競爭并轉(zhuǎn)入睡眠狀態(tài).如果在一個間隙內(nèi)移動節(jié)點收到多個靜止節(jié)點的接入應(yīng)答消息，則丟棄這些消息，繼續(xù)發(fā)送請求接入消息，任意接入應(yīng)答之間的競爭時間為tcom.在時間tdm，t0，tf中，一次接入請求的最長持續(xù)時間treq必須大于靜止節(jié)點的偵聽-睡眠周期td+ts，而且頻閃間隔tf必須小于靜止節(jié)點的偵聽時間td，以保證能夠喚醒靜止節(jié)點.移動節(jié)點的偵聽持續(xù)時間tdm同樣必須大于td+ts，以確保信道是空閑的.靜止節(jié)點偵聽的超時時間t0必須大于移動節(jié)點發(fā)送前導(dǎo)碼的頻閃間隔tf，以確保靜止節(jié)點不會過早轉(zhuǎn)入睡眠.

②移動鏈路維護.移動節(jié)點通過移動接入過程與靜止節(jié)點建立連接后，便可以進(jìn)行互相通信.移動節(jié)點在移動過程中不斷監(jiān)測與已連接的靜止節(jié)點之間的信號接收強度(RSSI)值，當(dāng)RSSI值下降到已設(shè)閥值時，移動節(jié)點向靜止節(jié)點發(fā)出連接斷開消息，斷開與靜止節(jié)點的連接.然后，移動節(jié)點再次發(fā)起移動接入過程，與其他靜止節(jié)點建立連接.

2 定向擴散路由設(shè)計

2.1 興趣擴散設(shè)計

改進(jìn)后的基于興趣有效傳播路徑判定規(guī)則的路由算法依舊分為興趣擴散、數(shù)據(jù)傳播和路徑加強3個階段(見圖4).本文主要針對應(yīng)急環(huán)境下的應(yīng)用要求，對DD協(xié)議中的興趣擴散階段和興趣分組的封裝方式進(jìn)行了改進(jìn).數(shù)據(jù)傳播和路徑加強階段仍使用傳統(tǒng)DD協(xié)議的路由規(guī)則.

圖4 DD協(xié)議原理示意圖

興趣(Interest)通過Sink節(jié)點注入網(wǎng)絡(luò)，通過一組鍵-值對來表示，包含了任務(wù)類型(type)、數(shù)據(jù)上傳時間間隔(interval)、目標(biāo)區(qū)域(rect)、Sink節(jié)點標(biāo)識(sinkID)、Sink節(jié)點坐標(biāo)(sinkLocation)、興趣產(chǎn)生的時間戳(timestamp)、興趣的有效期(expiresAt)、數(shù)據(jù)匹配條件(matchCond)等字段內(nèi)容.其中，任務(wù)類型是傳感器節(jié)點監(jiān)測的類型，如溫度、濕度、某類化學(xué)品的濃度、運動物體的速度等;數(shù)據(jù)匹配條件用于描述某種突發(fā)事件，如溫度高于100℃、速度大于20 m/s、空氣中二氧化硫的濃度大于0.56 mg/m3等.本文采用［type，rect，sinkID］3 個字段組合標(biāo)識一個唯一的興趣.如果2個興趣的這3個字段值都相同，則認(rèn)為這2個興趣是相同的.

興趣首先封裝在興趣分組(報文)中，興趣分組可在網(wǎng)絡(luò)節(jié)點間傳遞.興趣分組中除了包含興趣的上述字段外，還包括上一跳節(jié)點的標(biāo)識(preNodeID)和上一跳節(jié)點的位置(preNodeLocation)信息.興趣由Sink節(jié)點周期性地廣播到網(wǎng)絡(luò)中，初始的興趣分組中interval值較大(即數(shù)據(jù)上傳的頻率較小)，以便于嗅探網(wǎng)絡(luò)中是否有匹配該興趣的事件存在.周期性廣播用于維護在網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的無線傳感網(wǎng)中Sink節(jié)點到源節(jié)點之間的路由.傳感網(wǎng)中，在每一個節(jié)點的內(nèi)部都存在一個興趣緩存表(interest cache)，該表的每個條目關(guān)聯(lián)到一個不同的興趣，其字段內(nèi)容除了包含興趣的字段外，還包括最后收到匹配該興趣的消息時間戳(lastRecvTimestamp)和與該興趣對應(yīng)的梯度(gradients)列表.梯度列表中包含多個梯度，每個梯度對應(yīng)一個給本節(jié)點發(fā)送該興趣分組的鄰居節(jié)點.梯度字段包含鄰居節(jié)點的標(biāo)識(neighborID)、鄰居節(jié)點要求的數(shù)據(jù)上報速率(dataRate，即時間間隔，對應(yīng)于興趣中的interval字段)、該梯度有效期的起始時間(timestamp，對應(yīng)于興趣中的timestamp字段)和終止時間(expiresAt，對應(yīng)于興趣中的expiresAt字段)等.當(dāng)某個梯度的有效期終止時，從對應(yīng)梯度列表中移除，若某個興趣的梯度列表中的所有梯度均過期，則將該興趣條目從興趣緩存表中移除.

當(dāng)節(jié)點A收到其鄰居節(jié)點B廣播的一個興趣分組P時，可分以下幾種情形進(jìn)行處理:①若興趣緩存表TB不存在匹配的興趣，則根據(jù)興趣有效傳播路徑判定規(guī)則，判斷節(jié)點A是否在有效路徑上.若確認(rèn)其在有效路徑上，則在TB中新增一個興趣條目和對應(yīng)的梯度列表(此時僅包含一個梯度)，該興趣條目和梯度中各字段的值均取自興趣分組P，然后將興趣分組P中preNodeID和preNodeLocation字段的值更新為節(jié)點A的信息，并廣播更新后的興趣分組P;否則，丟棄興趣分組P.②若興趣緩存表TB中存在匹配的興趣，但對應(yīng)的梯度列表中不存在節(jié)點B對應(yīng)的梯度，則根據(jù)興趣有效傳播路徑判定規(guī)則，判斷節(jié)點A是否在有效路徑上.若確認(rèn)其在有效路徑上，則按需更新興趣緩存表TB中該興趣條目的lastRecvTimestamp，timestamp，expiresAt等字段，并在相應(yīng)梯度列表中新增一個梯度與節(jié)點B對應(yīng)，梯度各字段的值均取自興趣分組P，然后將興趣分組P中preNodeID和preNode-Location字段的值更新為節(jié)點A的信息，并廣播更新后的興趣分組P;否則，丟棄興趣分組P.③若興趣緩存表TB中存在匹配的興趣，且對應(yīng)的梯度列表存在節(jié)點B對應(yīng)的梯度，則判斷興趣分組P中的timestamp字段是否晚于該梯度中的timestamp字段.如果是，則認(rèn)為興趣分組P是一個更新的興趣分組，按需更新興趣條目的lastRecvTimestamp，timestamp，expiresAt等字段以及對應(yīng)梯度的dataR-ate，timestamp，expiresAt等字段，然后將興趣分組 P中preNodeID和preNodeLocation字段的值更新為節(jié)點A的信息，并廣播更新后的興趣分組P;否則，丟棄興趣分組P，以避免同一個消息在網(wǎng)絡(luò)中形成消息循環(huán).

2.2 興趣有效傳播路徑判定規(guī)則

節(jié)點A第1次收到其鄰居節(jié)點B廣播的一個興趣分組P時，根據(jù)興趣有效傳播路徑判定規(guī)則來判斷原來的興趣有效傳播路徑S→…→B(其中S表示Sink節(jié)點)添加了節(jié)點A后(即S→…→B→A)是否仍然為有效傳播路徑.節(jié)點A首先獲取興趣分組P中Sink節(jié)點的位置信息(sinkLocation字段)、目標(biāo)矩形區(qū)域(rect字段，如圖5中的矩形CDEF)以及節(jié)點B的位置信息(preNodeLocation字段)，然后依據(jù)如下步驟進(jìn)行判斷:

①如果節(jié)點A位于rect字段內(nèi)(可通過節(jié)點A的坐標(biāo)和rect字段中對角頂點的坐標(biāo)來判斷)，則認(rèn)為節(jié)點A位于興趣有效傳播路徑上，本次判定結(jié)束;否則，轉(zhuǎn)入步驟②.

②利用節(jié)點A，B的位置信息以及rect字段中對角頂點的坐標(biāo)，分別計算節(jié)點A，B與矩形4個角(以圖5中的矩形CDEF為例)的最近距離和最遠(yuǎn)距離，即

分別比較dA-min與 dB-min，dA-max與 dB-max的大小關(guān)系.如果(dA-min＜dB-min)‖(dA-max＜dB-max)，則轉(zhuǎn)入步驟③;否則，認(rèn)為節(jié)點A不在興趣有效傳播路徑上，本次判定結(jié)束.

③計算Sink節(jié)點到rect字段所在矩形4個角的最大值dS-max以及Sink節(jié)點與節(jié)點A之間的距離dSA.如果dSA≤dS-max，則認(rèn)為節(jié)點A在興趣有效傳播路徑上;否則，本次判定結(jié)束.

基于興趣有效傳播路徑判定規(guī)則的興趣擴散示意圖見圖5.

圖5 基于興趣有效傳播路徑判定規(guī)則的興趣擴散示意圖

3 實驗驗證及分析

仿真實驗場景為一塊大小為500 m×500 m的正方形區(qū)域，節(jié)點隨機地部署在正方形區(qū)域內(nèi).隨機選擇一個節(jié)點作為Sink節(jié)點，負(fù)責(zé)封裝興趣報文并將興趣報文廣播到網(wǎng)絡(luò)中.所有節(jié)點的通信半徑均設(shè)為90 m.無線電傳播模型為規(guī)則的球形.圖6為實驗中某次節(jié)點分布情況示意圖.圖中，虛線框內(nèi)區(qū)域表示興趣擴散的目標(biāo)區(qū)域(源節(jié)點).

圖6 節(jié)點部署示意圖

首先，選取20個節(jié)點進(jìn)行應(yīng)急環(huán)境下的接入有效性仿真，每一組實驗5次，統(tǒng)計其平均值.移動節(jié)點接入鄰近靜態(tài)節(jié)點組成的簇.圖7(a)顯示了6組實驗的結(jié)果.由圖可知，簇首數(shù)目沒有改變，證明了節(jié)點接入策略的有效性.在接入移動節(jié)點后，移動節(jié)點開始移動，直至退出所在簇，實驗結(jié)果見圖7(b).由圖可知，實驗中移動節(jié)點的離開并不影響簇數(shù)，由此證明了接入策略的有效性.簇首數(shù)目的減小是由于該組中移動節(jié)點和一個靜態(tài)節(jié)點成簇;隨著移動節(jié)點的退出，簇逐漸解散，靜態(tài)節(jié)點并入其他簇.由此可知，軟件仿真驗證了移動節(jié)點接入方法的有效性.

圖7 移動節(jié)點接入和退出的有效性驗證

其次，模擬實現(xiàn)了定向擴散路由算法中的興趣擴散階段.本實驗在相同的仿真環(huán)境下，分別對傳統(tǒng)DD路由算法和基于興趣有效傳播路徑判定規(guī)則的定向擴散(directed diffusion with decision rules，DDwDR)路由算法轉(zhuǎn)發(fā)的興趣報文數(shù)目進(jìn)行了統(tǒng)計.為了驗證網(wǎng)絡(luò)規(guī)模(節(jié)點數(shù)目)對這2種算法的影響，依次增加部署的節(jié)點總數(shù)并統(tǒng)計2種算法轉(zhuǎn)發(fā)的興趣報文數(shù)目.將統(tǒng)計結(jié)果以圖形方式展示并進(jìn)行對比.為了使數(shù)據(jù)更具說服力，所有統(tǒng)計結(jié)果均為相同條件下循環(huán)運行100次算法(每一次循環(huán)節(jié)點進(jìn)行重新部署)所得結(jié)果的平均值.

圖8 興趣擴散直觀圖

在圖6所示的節(jié)點分布下，基于2種路由算法得到的興趣擴散直觀圖見圖8.由圖可知，傳統(tǒng)的DD路由算法在全網(wǎng)范圍內(nèi)進(jìn)行興趣擴散，轉(zhuǎn)發(fā)的興趣報文數(shù)量較多;而DDwDR路由算法只在局部范圍內(nèi)進(jìn)行興趣擴散，轉(zhuǎn)發(fā)的興趣報文數(shù)量較少，且興趣能夠準(zhǔn)確地擴散至目標(biāo)區(qū)域中的所有節(jié)點.

當(dāng)節(jié)點總數(shù)在［60，300］內(nèi)以20為遞增值逐漸增加時，2種算法轉(zhuǎn)發(fā)的興趣報文數(shù)目統(tǒng)計結(jié)果見圖9.由圖可知，在相同條件下，與傳統(tǒng)的DD路由算法相比，采用DDwDR路由算法可大幅減少網(wǎng)絡(luò)中轉(zhuǎn)發(fā)的興趣報文數(shù)目.隨著節(jié)點總數(shù)的增多，基于前者轉(zhuǎn)發(fā)的興趣報文數(shù)目急劇增加，而后者轉(zhuǎn)發(fā)的興趣報文數(shù)目的漲幅相對較小且較為平穩(wěn).

圖9 轉(zhuǎn)發(fā)的興趣報文數(shù)與節(jié)點總數(shù)的關(guān)系

4 結(jié)語

在應(yīng)急環(huán)境下，系統(tǒng)內(nèi)的感知節(jié)點并非周期性地將采集到的所有數(shù)據(jù)進(jìn)行上傳，而是在發(fā)生突發(fā)事件(如監(jiān)測值超出已設(shè)閾值)或收到查詢命令時才上傳數(shù)據(jù).本文研究了應(yīng)急環(huán)境下無線傳感網(wǎng)移動節(jié)點的接入機制和基于查詢驅(qū)動的定向擴散路由算法，基于X-MAC協(xié)議設(shè)計了一種移動節(jié)點的接入機制，提出了一種改進(jìn)的DDwDR路由算法，利用節(jié)點的位置信息使興趣擴散具有明確的方向性，從而解決了傳統(tǒng)DD算法中數(shù)據(jù)傳遞和能量消耗等問題.設(shè)計實現(xiàn)了相應(yīng)的仿真實驗，以驗證分析使用興趣有效傳播路徑判定規(guī)則對DD路由性能的影響.結(jié)果表明，使用該判定規(guī)則的改進(jìn)路由算法可大幅減少網(wǎng)絡(luò)中轉(zhuǎn)發(fā)的興趣報文數(shù)和消息回路，節(jié)約網(wǎng)絡(luò)能量;相比傳統(tǒng)的定向擴散路由，其性能有較大程度提升，更適于應(yīng)急環(huán)境中使用.

References)

［1］Bertand A，Szurley J，Ruckebusch P，et al.Efficientcalculation of sensor utility and sensor removal in wireless sensor networks for adaptive signal estimation and beamforming［J］.IEEE Transactions on Signal Processing Journal，2012，60(11):5857-5869.

［2］Li Qianmu，Hou Jun，Qi Yong，et al.The rule engineer model on the high-speed processing of disaster warning information［J］.Disaster Advances，2012，5(4):432-437.

［3］He Shibo，Chen Jiming，Peng Cheng，et al.Maintaining quality of sensing with actors in wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems Journal，2012，23(9):1657-1667.

［4］Li Qianmu，Jia Li.Rough outlier detection based security risk analysis methodology［J］.China Communications，2012，5(7):14-21.

［5］Li Qianmu，Mao Haiyan，Zhang Hong.The design and cost analysis of DCP algorithm based on directional circle［J］.International Journal of Radio Frequency Identification and Wireless Sensor Networks，2012，2(2):1-7.

［6］Chen Siyuan，Huang Minsu，Tang Shaojie，et al.Capacity of data collection in arbitrary wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems Journal，2012，23(1):52-60.

［7］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proceedings of the 21st International Annual Joint Conference of the IEEE Computer and Communications Societies. New York，USA，2002:1567-1576.

［8］van Dam T，Langendoen K.An adaptive energy-efficient MAC protocol for wireless sensor networks［C］//Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.Los Angeles，CA，USA，2003:171-180.

［9］Polastre J，Hill J，Culler D.Versatile low power media access for wireless sensor networks［C］//Proceedings of the 2nd International Conference on Embedded Networked Sensor System.Baltimore，MD，USA，2004:95-107.

［10］Buettner M，Yee G V，Anderson E，et al.X-MAC:a short preamble MAC protocol for duty-cycled wireless sensor networks［C］//Proceedings of the 4th International Conference on Embedded Networked Sensor System.Boulder，CO，USA，2006:307-320.

［11］Yang Xiao，Miao Peng.Tight performance bounds of multihop fair access for MAC protocols in wireless sensor networks and underwater sensor networks［J］.IEEE Transactions on Mobile Computing Journal，2012，11(10):1538-1554.