無(wú)線傳感器網(wǎng)絡(luò)中的分布式動(dòng)態(tài)路徑規(guī)劃算法*

賈思強(qiáng)，高 翔，陸起涌，2*

(1.復(fù)旦大學(xué)電子工程系，上海，200433;2.復(fù)旦大學(xué)無(wú)錫研究院，江蘇無(wú)錫，214131)

將無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與移動(dòng)機(jī)器人技術(shù)相結(jié)合，既增強(qiáng)移動(dòng)機(jī)器人的感知能力，也提高了傳感器網(wǎng)絡(luò)對(duì)環(huán)境的控制力［1］。WSN通過(guò)無(wú)線通信及協(xié)作處理，為移動(dòng)主體提供當(dāng)前環(huán)境下的優(yōu)化路徑，實(shí)現(xiàn)快速安全的導(dǎo)航，對(duì)于災(zāi)害逃生，及時(shí)救援和未知環(huán)境探測(cè)等具有重要意義。無(wú)線傳感器節(jié)點(diǎn)通常受限于自身電量，因而需降低消息收發(fā)的頻率，另一方面，被監(jiān)控環(huán)境會(huì)隨時(shí)間不斷變化，計(jì)算最優(yōu)路徑需要大部分無(wú)線傳感器節(jié)點(diǎn)的協(xié)同處理，因此如何平衡通信代價(jià)和最優(yōu)路徑，使算法能夠具有良好的動(dòng)態(tài)性能，是學(xué)者們研究的焦點(diǎn)。

基于無(wú)線傳感器網(wǎng)絡(luò)的動(dòng)態(tài)路徑規(guī)劃算法可分為集中式和分布式。集中式算法［2－4］通過(guò)無(wú)線傳感器網(wǎng)絡(luò)將數(shù)據(jù)匯集到處理中心，算法利用全局信息(一般包括地圖信息)計(jì)算得到全局最優(yōu)路徑。集中式算法由于其較高的系統(tǒng)要求和網(wǎng)絡(luò)信息匯集延時(shí)，其適用場(chǎng)景受到限制，一般在緊急情況［2－3］和高復(fù)雜度環(huán)境［4］中采用。利用分布式算法進(jìn)行路徑規(guī)劃在系統(tǒng)代價(jià)和擴(kuò)展性方面具有優(yōu)勢(shì)。目前分布式算法主要集中在梯度勢(shì)場(chǎng)算法［5－12］和路標(biāo)算法［13－16］。梯度勢(shì)場(chǎng)算法［5－9］通常以危險(xiǎn)區(qū)域到各節(jié)點(diǎn)的跳數(shù)來(lái)構(gòu)造梯度勢(shì)場(chǎng)，對(duì)如何適應(yīng)環(huán)境的動(dòng)態(tài)變化考慮較少。文獻(xiàn)［5］以各危險(xiǎn)節(jié)點(diǎn)跳數(shù)平方的倒數(shù)和作為當(dāng)前節(jié)點(diǎn)的勢(shì)場(chǎng)值，通過(guò)最小生成樹(shù)算法計(jì)算出優(yōu)化路徑，文獻(xiàn)［8］進(jìn)一步改進(jìn)了梯度公式并對(duì)復(fù)雜場(chǎng)景做了分析，但其對(duì)危險(xiǎn)事件變化和局部最小值的處理會(huì)耗費(fèi)大量通信代價(jià)。為了增強(qiáng)動(dòng)態(tài)性，文獻(xiàn)［9］提出對(duì)于已計(jì)算出的優(yōu)化路徑主干進(jìn)行較頻繁的監(jiān)測(cè)，相對(duì)降低其他區(qū)域的監(jiān)測(cè)頻率，從而減少網(wǎng)絡(luò)消息收發(fā)數(shù)量。文獻(xiàn)［10］提出了以跳數(shù)為單位預(yù)測(cè)危險(xiǎn)區(qū)域的變化范圍，文獻(xiàn)［11］從最小暴露概率的角度建立梯度勢(shì)場(chǎng)，兩者在適用性方面均有不足。文獻(xiàn)［12］通過(guò)引入射頻接收信號(hào)強(qiáng)度RSS(Received Signal Strength)構(gòu)造偽梯度函數(shù)，但未考慮環(huán)境因素。路標(biāo)算法［13－16］借助環(huán)境地圖信息以不同機(jī)制在網(wǎng)絡(luò)中選取路標(biāo)節(jié)點(diǎn)，網(wǎng)絡(luò)消息在這些路標(biāo)節(jié)點(diǎn)通路間傳播。基本的路徑規(guī)劃和動(dòng)態(tài)調(diào)整算法被限制在路標(biāo)網(wǎng)絡(luò)上或被查詢(xún)區(qū)域內(nèi)，從而以路徑長(zhǎng)度的增加為代價(jià)降低了消息數(shù)量。文獻(xiàn)［17］和［18］結(jié)合地理位置和環(huán)境信息規(guī)劃路徑。文獻(xiàn)［18］改進(jìn)分布式的有向無(wú)環(huán)圖DAG(Directed Acyclic Graph)算法，使節(jié)點(diǎn)利用局部信息進(jìn)行動(dòng)態(tài)調(diào)整和路徑規(guī)劃，在降低消息數(shù)量方面取得了較好的效果，但對(duì)于狀態(tài)恢復(fù)節(jié)點(diǎn)沒(méi)有針對(duì)性的路徑修復(fù)。

本文受文獻(xiàn)［12］和［18］的思想啟發(fā)，在不借助WSN位置信息的前提下，針對(duì)梯度勢(shì)場(chǎng)算法在動(dòng)態(tài)調(diào)整方面的不足，綜合考慮規(guī)劃路徑長(zhǎng)度和安全性，以及動(dòng)態(tài)調(diào)整時(shí)的通信開(kāi)銷(xiāo)，結(jié)合環(huán)境因素構(gòu)造梯度勢(shì)場(chǎng)函數(shù)，提出了一種分布式動(dòng)態(tài)路徑規(guī)劃算法，并對(duì)該算法進(jìn)行了分析，擴(kuò)展和仿真比較。

1 問(wèn)題描述

1.1 問(wèn)題前提

WSN被隨機(jī)散布在監(jiān)控區(qū)域內(nèi)，系統(tǒng)不借助任何地理位置信息。移動(dòng)主體可能在該區(qū)域的任何位置請(qǐng)求被引導(dǎo)到任意目標(biāo)節(jié)點(diǎn)。當(dāng)一個(gè)危險(xiǎn)事件發(fā)生時(shí)，其附近的無(wú)線傳感器節(jié)點(diǎn)能夠感知到該危險(xiǎn)事件的發(fā)生和周?chē)h(huán)境的變化。每個(gè)節(jié)點(diǎn)讀取傳感器數(shù)據(jù)，與已設(shè)定的閾值比較，將自身標(biāo)記為安全或危險(xiǎn)。系統(tǒng)可以設(shè)定多個(gè)閾值，以分級(jí)標(biāo)定節(jié)點(diǎn)的當(dāng)前狀態(tài)。一個(gè)危險(xiǎn)事件可能發(fā)生擴(kuò)散，移動(dòng)或者消減。在危險(xiǎn)區(qū)域變化的過(guò)程中，原來(lái)受到影響的危險(xiǎn)節(jié)點(diǎn)可能重新改變狀態(tài)，恢復(fù)為安全節(jié)點(diǎn)。一條安全路徑的定義，對(duì)于安全節(jié)點(diǎn)來(lái)說(shuō)是該路徑沿途不經(jīng)過(guò)危險(xiǎn)節(jié)點(diǎn);對(duì)于危險(xiǎn)節(jié)點(diǎn)來(lái)說(shuō)是該路徑可以盡快逃離危險(xiǎn)區(qū)域并到達(dá)目標(biāo)節(jié)點(diǎn)。本文定義一條路徑的長(zhǎng)度是其相連的每個(gè)節(jié)點(diǎn)間距離的總和。移動(dòng)主體可以無(wú)線通信方式逐個(gè)經(jīng)過(guò)路徑節(jié)點(diǎn)，最終被引導(dǎo)到目標(biāo)節(jié)點(diǎn)。

1.2 算法目標(biāo)

基于以上前提，本文算法的目標(biāo)是為每一個(gè)節(jié)點(diǎn)提供一條到達(dá)目標(biāo)節(jié)點(diǎn)的優(yōu)化路徑，該路徑是確保安全和盡可能快速的。同時(shí)，隨著危險(xiǎn)事件的變化，網(wǎng)絡(luò)能夠通過(guò)較低的通信代價(jià)來(lái)實(shí)現(xiàn)動(dòng)態(tài)路徑規(guī)劃。

2 路徑規(guī)劃算法

2.1 梯度勢(shì)場(chǎng)函數(shù)構(gòu)造

考慮到RSS在一定程度上能夠反映兩節(jié)點(diǎn)間距離的遠(yuǎn)近和鏈路質(zhì)量［19］，本文如文獻(xiàn)［12］在梯度勢(shì)場(chǎng)函數(shù)中引入RSS，以進(jìn)一步優(yōu)化路徑長(zhǎng)度。本文構(gòu)建的梯度勢(shì)場(chǎng)是從目標(biāo)節(jié)點(diǎn)擴(kuò)散至末端節(jié)點(diǎn)，因此該梯度勢(shì)場(chǎng)函數(shù)與RSS成正比，而與跳數(shù)成反比。同時(shí)，梯度勢(shì)場(chǎng)函數(shù)應(yīng)與環(huán)境的危險(xiǎn)程度成反比，使安全節(jié)點(diǎn)不會(huì)選取危險(xiǎn)節(jié)點(diǎn)作為父節(jié)點(diǎn)而引導(dǎo)移動(dòng)主體進(jìn)入危險(xiǎn)區(qū)域。基于以上考慮，可構(gòu)造梯度勢(shì)場(chǎng)函數(shù)如式(1)。式中，pseu_和RSS分別代表當(dāng)前節(jié)點(diǎn)i收到的上一跳節(jié)點(diǎn)發(fā)送的梯度勢(shì)場(chǎng)值和接收信號(hào)強(qiáng)度，RSS需進(jìn)行歸一化處理，Hop-Count為上一跳節(jié)點(diǎn)的跳數(shù)加與當(dāng)前節(jié)點(diǎn)傳感器的數(shù)值相關(guān)，當(dāng)節(jié)點(diǎn)安全時(shí)其值為1，當(dāng)節(jié)點(diǎn)處于危險(xiǎn)狀態(tài)時(shí)取小于1大于0的數(shù)值。

目標(biāo)節(jié)點(diǎn)梯度勢(shì)場(chǎng)值為最大值pseu_gMAX。由于對(duì)跳數(shù)的不同處理，本文梯度勢(shì)場(chǎng)隨跳數(shù)的下降速度比文獻(xiàn)［12］中的慢，更有利于遠(yuǎn)距離節(jié)點(diǎn)梯度勢(shì)場(chǎng)值的區(qū)分。對(duì)于的處理事實(shí)上可以多樣化，在后文中將繼續(xù)討論，這里暫且將所有危險(xiǎn)狀態(tài)節(jié)點(diǎn)的定為同一值。

2.2 算法描述

2.2.1 梯度勢(shì)場(chǎng)建立

梯度勢(shì)場(chǎng)算法通常以CSMA(Carrier Sense Multiple Access)的方式進(jìn)行定向泛洪，傳播效率低。本文結(jié)合式(1)對(duì)該過(guò)程做相應(yīng)改進(jìn)，當(dāng)父節(jié)點(diǎn)廣播梯度消息后，其臨近的子節(jié)點(diǎn)中RSS強(qiáng)的應(yīng)較先廣播。因此，本文設(shè)計(jì)每個(gè)節(jié)點(diǎn)在初次收到上一跳節(jié)點(diǎn)消息后，做如式(2)計(jì)算的延時(shí)，在延時(shí)結(jié)束后進(jìn)入CSMA模式廣播。式中，d為網(wǎng)絡(luò)節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)，Δdelay為一個(gè)梯度消息的發(fā)送時(shí)間。

網(wǎng)絡(luò)梯度勢(shì)場(chǎng)的建立過(guò)程如下:

步驟1 目標(biāo)節(jié)點(diǎn)自身跳數(shù)為0，梯度勢(shì)場(chǎng)為最大值，其他節(jié)點(diǎn)跳數(shù)設(shè)為無(wú)窮，梯度勢(shì)場(chǎng)值為0;

步驟2 節(jié)點(diǎn)監(jiān)聽(tīng)來(lái)自鄰居節(jié)點(diǎn)的路由消息，包括跳數(shù)，接收信號(hào)強(qiáng)度，梯度勢(shì)場(chǎng)值和傳感器數(shù)據(jù);

步驟3 節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)的梯度消息后，設(shè)定延時(shí)時(shí)間，判斷鄰居節(jié)點(diǎn)當(dāng)前狀態(tài);

步驟4 如鄰居處于安全狀態(tài)，則通過(guò)式(1)計(jì)算出相應(yīng)的勢(shì)場(chǎng)值，如該值大于自身當(dāng)前勢(shì)場(chǎng)值，則將鄰居節(jié)點(diǎn)記錄為父節(jié)點(diǎn)，將自身更新的梯度信息打包發(fā)送;特別地，對(duì)于當(dāng)前狀態(tài)為危險(xiǎn)的節(jié)點(diǎn)，且自身從未收到過(guò)來(lái)自安全節(jié)點(diǎn)的梯度消息，則將鄰居節(jié)點(diǎn)記錄為父節(jié)點(diǎn)，并將自身更新打包發(fā)送梯度消息;

步驟5 如鄰居處于危險(xiǎn)狀態(tài)，則只有在從未接收到來(lái)自安全節(jié)點(diǎn)的梯度消息且計(jì)算得勢(shì)場(chǎng)值大于當(dāng)前勢(shì)場(chǎng)值時(shí)，記錄父節(jié)點(diǎn)并打包發(fā)送梯度消息，否則拋棄來(lái)自危險(xiǎn)節(jié)點(diǎn)的梯度消息;

步驟6 該過(guò)程結(jié)束后，各節(jié)點(diǎn)建立起各自的鄰居信息表，最終確定的父節(jié)點(diǎn)為使自身梯度勢(shì)場(chǎng)值最高或最安全的鄰居節(jié)點(diǎn)。

2.2.2 動(dòng)態(tài)調(diào)整

當(dāng)監(jiān)控環(huán)境出現(xiàn)變化時(shí)，為實(shí)現(xiàn)算法目標(biāo)，網(wǎng)絡(luò)需要維持其自身的梯度趨勢(shì)，即每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)梯度勢(shì)場(chǎng)值必須大于自身節(jié)點(diǎn)。為了有效降低通信代價(jià)，算法僅在危險(xiǎn)區(qū)域造成網(wǎng)絡(luò)梯度無(wú)法維持時(shí)進(jìn)行必要的通信。網(wǎng)絡(luò)的動(dòng)態(tài)調(diào)整算法如下:

步驟1 各節(jié)點(diǎn)讀取自身傳感器數(shù)值，確定當(dāng)前狀態(tài)，如與之前相比發(fā)生狀態(tài)變化，則根據(jù)當(dāng)前的鄰居信息表通過(guò)式(1)計(jì)算出當(dāng)前最高梯度勢(shì)場(chǎng)值，記錄父節(jié)點(diǎn)并打包梯度信息進(jìn)行廣播;

步驟2 鄰居節(jié)點(diǎn)接收到梯度消息后更新自身鄰居信息表，根據(jù)鄰居信息通過(guò)式(1)計(jì)算出更新的最高梯度勢(shì)場(chǎng)值P;

步驟3 對(duì)于當(dāng)前狀態(tài)為安全的節(jié)點(diǎn)，如果該勢(shì)場(chǎng)值P較當(dāng)前勢(shì)場(chǎng)值下降，則查找鄰居表中梯度勢(shì)場(chǎng)值最大的安全鄰居，如其勢(shì)場(chǎng)值大于自身當(dāng)前勢(shì)場(chǎng)值，則不進(jìn)行廣播，維持當(dāng)前勢(shì)場(chǎng)值，否則記錄父節(jié)點(diǎn)并打包梯度信息進(jìn)行廣播;

步驟4 對(duì)于當(dāng)前狀態(tài)為危險(xiǎn)的節(jié)點(diǎn)，如果該勢(shì)場(chǎng)值P較當(dāng)前勢(shì)場(chǎng)值下降，則判斷該勢(shì)場(chǎng)值是否小于原鄰居勢(shì)場(chǎng)值中比當(dāng)前勢(shì)場(chǎng)值低的最大梯度勢(shì)場(chǎng)值，如大于則不進(jìn)行廣播，維持當(dāng)前勢(shì)場(chǎng)值，否則記錄父節(jié)點(diǎn)并打包梯度信息進(jìn)行廣播;

步驟5 對(duì)于所有節(jié)點(diǎn)，如果該勢(shì)場(chǎng)值P較當(dāng)前勢(shì)場(chǎng)值上升，則判斷相應(yīng)鄰居節(jié)點(diǎn)是否為當(dāng)前父節(jié)點(diǎn)，如不一致，則記錄父節(jié)點(diǎn)并打包梯度信息進(jìn)行廣播。

2.3 算法分析

在梯度勢(shì)場(chǎng)建立的過(guò)程中，每個(gè)節(jié)點(diǎn)選取最高梯度勢(shì)場(chǎng)值并確定父節(jié)點(diǎn)，由式(1)的性質(zhì)，其父節(jié)點(diǎn)勢(shì)場(chǎng)值必高于子節(jié)點(diǎn)，因而每條路徑的最高勢(shì)場(chǎng)值最終都將收斂于pseu_gMAX處，即目標(biāo)節(jié)點(diǎn)處。不妨反證假設(shè)存在局部梯度勢(shì)場(chǎng)最高區(qū)域，如該區(qū)域收斂到一個(gè)最大梯度勢(shì)場(chǎng)節(jié)點(diǎn)，則該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，與算法的問(wèn)題前提相悖，而根據(jù)本文算法，該局部區(qū)域節(jié)點(diǎn)將相互進(jìn)行多次梯度傳播和更新，直至該區(qū)域節(jié)點(diǎn)勢(shì)場(chǎng)值降到滿(mǎn)足條件選取區(qū)域外節(jié)點(diǎn)為路徑父節(jié)點(diǎn)。

算法對(duì)于危險(xiǎn)區(qū)域節(jié)點(diǎn)的處理方式較為嚴(yán)格，主要目的是使危險(xiǎn)區(qū)域內(nèi)的移動(dòng)主體能夠盡快脫離危險(xiǎn)區(qū)域，同時(shí)兼顧到達(dá)目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度，這之間的權(quán)衡關(guān)系通過(guò)來(lái)調(diào)節(jié)。在動(dòng)態(tài)調(diào)整過(guò)程中，最寬松的要求是每個(gè)節(jié)點(diǎn)存在一個(gè)比自身梯度勢(shì)場(chǎng)高的父節(jié)點(diǎn)，此限制條件如前文的分析思路一樣可得出其最終收斂于pseu_gMAX的結(jié)論。

每個(gè)節(jié)點(diǎn)對(duì)于梯度勢(shì)場(chǎng)的分布式計(jì)算和調(diào)整需要根據(jù)各鄰居梯度消息進(jìn)行如式(1)的計(jì)算，其運(yùn)算復(fù)雜度為O(Δ)，Δ為鄰居節(jié)點(diǎn)數(shù)，然后進(jìn)行排序運(yùn)算，其復(fù)雜度一般為 O(Δ2)或O(Δlog2Δ)。

2.4 算法擴(kuò)展

對(duì)于該算法的擴(kuò)展可以有兩個(gè)方面。一方面，前文中將所有危險(xiǎn)區(qū)域內(nèi)節(jié)點(diǎn)的環(huán)境因子設(shè)定為同一值，即所有超過(guò)閾值的無(wú)線傳感器節(jié)點(diǎn)采用相同的權(quán)值。事實(shí)上，環(huán)境因子可以根據(jù)節(jié)點(diǎn)的傳感數(shù)值進(jìn)行細(xì)化，從而根據(jù)實(shí)際情況進(jìn)一步設(shè)計(jì)出合理的路徑規(guī)劃策略。另一方面，本文算法可適用于前文所述的路標(biāo)算法上，在無(wú)線傳感器網(wǎng)絡(luò)選取了合適路標(biāo)節(jié)點(diǎn)子集后，可通過(guò)本文算法在路標(biāo)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間規(guī)劃路徑，算法的動(dòng)態(tài)調(diào)整策略同樣適用于路標(biāo)節(jié)點(diǎn)受到危險(xiǎn)事件影響的情況。

3 仿真與結(jié)果分析

3.1 仿真搭建

本文利用CC2430無(wú)線模塊模型在OMNET++4.1平臺(tái)進(jìn)行仿真。實(shí)驗(yàn)設(shè)計(jì)在500 m×500 m的平面空間里隨機(jī)散布若干節(jié)點(diǎn)，設(shè)定節(jié)點(diǎn)的穩(wěn)定通信距離為50 m，目標(biāo)節(jié)點(diǎn)坐標(biāo)為(450 m，450 m)，最大梯度勢(shì)場(chǎng)值為50 000，環(huán)境因子設(shè)定為 0.4。實(shí)驗(yàn)?zāi)M危險(xiǎn)事件最初以坐標(biāo)(175 m，325 m)為圓心，50 m為半徑存在于此空間內(nèi)，而后擴(kuò)散為半徑75 m的圓形區(qū)域，最后以此形狀轉(zhuǎn)移至以坐標(biāo)(200 m，300 m)為圓心。這里首先給出示例圖1，呈現(xiàn)一個(gè)WSN在3種情況下的網(wǎng)絡(luò)拓?fù)渥兓渲刑幱谖ｋU(xiǎn)狀態(tài)的節(jié)點(diǎn)選擇盡快逃離危險(xiǎn)區(qū)域的路徑，同時(shí)兼顧選擇離目標(biāo)節(jié)點(diǎn)較近的鄰居為父節(jié)點(diǎn)。在環(huán)境變化先后，安全狀態(tài)節(jié)點(diǎn)動(dòng)態(tài)調(diào)整各自的路徑避開(kāi)危險(xiǎn)區(qū)域，從三幅圖的對(duì)比可發(fā)現(xiàn)，這種路徑的變化僅發(fā)生在危險(xiǎn)事件附近局部區(qū)域。

圖1 模擬環(huán)境變化先后WSN拓?fù)浞抡媸纠龍D

盡管文獻(xiàn)［18］算法(下文簡(jiǎn)稱(chēng)“DAG算法”)借助了位置信息，但考慮到本文算法與其在目標(biāo)和策略上的相近性，這里將其納為參考對(duì)象進(jìn)行比較。

3.2 路徑長(zhǎng)度

作為路徑規(guī)劃的首要目標(biāo)，實(shí)驗(yàn)在路徑長(zhǎng)度方面將本文算法與DAG算法和文獻(xiàn)［8］算法(下文簡(jiǎn)稱(chēng)“Tseng算法”)對(duì)比。在初始狀態(tài)下，比較所有節(jié)點(diǎn)的路徑平均長(zhǎng)度，圖2表明了本文算法在路徑長(zhǎng)度上的優(yōu)勢(shì)。在危險(xiǎn)區(qū)域擴(kuò)散和轉(zhuǎn)移的情況下，為了突出算法的動(dòng)態(tài)性能，本文選取在環(huán)境變化先后路徑受到影響的節(jié)點(diǎn)在平均長(zhǎng)度上做比較，同樣可以看到本文算法的優(yōu)勢(shì)。相比于DAG算法這種優(yōu)勢(shì)在危險(xiǎn)區(qū)域轉(zhuǎn)移時(shí)稍有增加，原因是本文算法在路徑恢復(fù)處理方面對(duì)規(guī)劃路徑長(zhǎng)度的要求更高。

3.3 路徑安全性

本文以WSN中所有節(jié)點(diǎn)路徑途經(jīng)危險(xiǎn)區(qū)域的總次數(shù)作為路徑安全性指標(biāo)來(lái)進(jìn)行比較。經(jīng)仿真驗(yàn)證，三種算法都使安全區(qū)節(jié)點(diǎn)路徑有效避開(kāi)危險(xiǎn)區(qū)域，該指標(biāo)實(shí)際考察了各算法對(duì)于危險(xiǎn)區(qū)域內(nèi)節(jié)點(diǎn)脫離危險(xiǎn)的路徑規(guī)劃能力。從圖3中可看出，本文算法與DAG算法在途經(jīng)次數(shù)上幾乎一樣，僅在節(jié)點(diǎn)較少時(shí)差距相對(duì)明顯。分析認(rèn)為，DAG算法借助位置信息僅考慮節(jié)點(diǎn)如何最快脫離危險(xiǎn)區(qū)域，而不兼顧其脫離后到達(dá)目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度。圖4是在網(wǎng)絡(luò)含300個(gè)節(jié)點(diǎn)時(shí)將不同的情況做比較，事實(shí)上通過(guò)減小環(huán)境因子，本文算法將達(dá)到與DAG算法一致的處理策略和效果。

圖2 模擬環(huán)境變化先后WSN內(nèi)節(jié)點(diǎn)路徑長(zhǎng)度對(duì)比

3.4 動(dòng)態(tài)調(diào)整通信代價(jià)

本文以動(dòng)態(tài)調(diào)整過(guò)程中節(jié)點(diǎn)間消息收發(fā)的總數(shù)作為通信代價(jià)的衡量標(biāo)準(zhǔn)。對(duì)比仿真中不再與泛洪形式的梯度勢(shì)場(chǎng)算法相比較，而是與一般的以廣度優(yōu)先遍歷(BFS)泛洪WSN并在泛洪結(jié)束后即可規(guī)劃路徑的算法相對(duì)比。模擬實(shí)驗(yàn)中放置400個(gè)節(jié)點(diǎn)，圖5(a)模擬危險(xiǎn)區(qū)域從半徑30 m依次擴(kuò)散至50 m到80 m，圖5(b)模擬半徑75 m的危險(xiǎn)區(qū)域向東南方向以每周期依次移動(dòng)20 m到50 m。從圖5中可看出，本文算法相較于BFS泛洪方法優(yōu)勢(shì)明顯，而與泛洪形式的梯度勢(shì)場(chǎng)算法對(duì)比則將效果更優(yōu)。與DAG算法相比，兩者的消息數(shù)量在危險(xiǎn)區(qū)域擴(kuò)散和移動(dòng)實(shí)驗(yàn)中分別最大相差16和33，從絕對(duì)值來(lái)看并不大。經(jīng)分析，這樣的差距主要由于本文算法中的動(dòng)態(tài)調(diào)整并不僅限于狀態(tài)發(fā)生變化的節(jié)點(diǎn)，對(duì)其附近及后續(xù)節(jié)點(diǎn)做出更好的路徑規(guī)劃亦有作用，因而相對(duì)增加了通信開(kāi)銷(xiāo)。

圖3 模擬環(huán)境變化先后WSN內(nèi)節(jié)點(diǎn)途經(jīng)危險(xiǎn)區(qū)域次數(shù)對(duì)比

圖4 對(duì)路徑安全性的影響

綜上，本文算法在規(guī)劃路徑長(zhǎng)度和安全性方面具有一定優(yōu)勢(shì);相比Tseng算法，本文算法可顯著降低動(dòng)態(tài)調(diào)整時(shí)的通信開(kāi)銷(xiāo);相比DAG算法，本文算法可在不借助位置信息條件下，以相近的通信開(kāi)銷(xiāo)動(dòng)態(tài)處理路徑規(guī)劃，且路徑自恢復(fù)效果更好。

圖5 WSN動(dòng)態(tài)調(diào)整路徑規(guī)劃的通信代價(jià)對(duì)比

4 結(jié)論

本文針對(duì)梯度勢(shì)場(chǎng)算法在動(dòng)態(tài)調(diào)整方面的不足，綜合考慮規(guī)劃路徑長(zhǎng)度，路徑安全性和通信代價(jià)，結(jié)合環(huán)境因素構(gòu)造梯度勢(shì)場(chǎng)函數(shù)，提出了一種分布式動(dòng)態(tài)路徑規(guī)劃算法，在環(huán)境變化時(shí)各節(jié)點(diǎn)依據(jù)局部信息動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)梯度勢(shì)場(chǎng)，為每個(gè)節(jié)點(diǎn)提供優(yōu)化路徑。仿真結(jié)果顯示了本文算法在WSN受到危險(xiǎn)區(qū)域變化影響的情況下，能夠規(guī)劃出較短路徑，有效降低通信代價(jià)并可靈活處理路徑安全性。算法不借助WSN地理位置信息，相對(duì)簡(jiǎn)捷易實(shí)現(xiàn)，可進(jìn)一步研究將其與路標(biāo)算法相結(jié)合，利于大規(guī)模WSN中路徑規(guī)劃性能的提升。

［1］ 薛晗，李迅，馬宏緒.基于無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)機(jī)器人智能導(dǎo)航算法［J］.傳感技術(shù)學(xué)報(bào)，2008，21(5):834－840.

［2］ Li S，Zhan A，Wu X，et al.ERN:Emergence Rescue Navigation with Wireless Sensor Networks［C］//15th International Conference on Parallel and Distributed Systems(ICPADS).Shenzhen，China，2009:361－368.

［3］ Chen L W，Cheng J H，Tseng Y C，et al.LEGS:A Load-balancing Emergency Guiding System based on Wireless Sensor Networks［C］//2012 IEEE International Conference on Pervasive Computing and Communications Workshops(PERCOM Workshops).Lugano，2012:486－488.

［4］ Imen C，Anis K，Hachemi B，et al.Smart PATH:A Hybrid ACO-GA Algorithm for Robot Path Planning［C］//2012 IEEE Congress on Evolutionary Computation(CEC).Brisbane，Australia，2012:1－8.

［5］ Li Q，Rosa D M，Rus D.Distributed Algorithms for Guiding Navi-gation Across a Sensor Network［C］//Proceedings of the 9th annual International Conference on Mobile Computing and Networking.San Diego，CA，USA，2003:313－325.

［6］ Xiao Q，Xiao B，Luo J，et al.Reliable Navigation of Mobile Sensors in Wireless Sensor Networks Without Localization Service［C］//17th International Workshop on Quality of Service，IWQoS，2009.Charleston，SC，2009:1－9.

［7］ Verma A，Sawant H，Tan J.Selection and Navigation of Mobile Sensor Nodes Using a Sensor Network［C］//Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications.Kauai Island，HI，2005:41－50.

［8］ Tseng Y C，Pan M S，Tsai Y Y.Wireless Sensor Networks for E-mergency Navigation［J］.Computer，2006，39(7):55－62.

［9］ Keith J O，Tucker R B.Distributed Path Planning for Robots in Dynamic Environments Using a Pervasive Embedded Network［C］//Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems，AAMAS 2004.New York，NY，USA，2004:1538－1539.

［10］ Wu X，Tan S，Chen T，et al.Distributed Dynamic Navigation for Sensor Networks［J］.Tsinghua Science and Technology，2011，16(6):648－656.

［11］ Ferrari S，F(xiàn)oderaro G.A Potential Field Approach to Finding Minimum-exposure Paths in Wireless Sensor Networks［C］//2010 IEEE International Conference on Robotics and Automation(ICRA).Anchorage，AK，USA，2010:335－341.

［12］ Deshpande N，Crant E，Henderson C.T.Experiments With a Pseudo-gradient Algorithm for Target Localization Using Wireless Sensor Networks［C］//2010 IEEE Conference on Multisensor Fusion and Integration for Intelligent Systems.Salt Lake City，UT，2010:74－79.

［13］ Alankus G，Atay N，Lu C，et al.Adaptive Embedded Roadmaps for Sensor Networks［C］//2007 IEEE International Conference on Robotics and Automation.Roma，2007:3645－3652.

［14］ Alankus G，Atay N，Lu C，et al.Spatiotemporal Query Strategies for Navigation in Dynamic Sensor Network Environments［C］//2005 IEEE/RSJ International Conference on Intelligent Robots and Systems，2005(IROS 2005).Edmonton，Alta，2005:3718－3725.

［15］ Bhattacharya S，Atay N Alankus G，et al.Roadmap Query for Sensor Network Assisted Navigation in Dynamic Environments［C］//Proceedings of the Second IEEE international conference on Distributed Computing in Sensor Systems.San Francisco，CA，2006:17－36.

［16］ Yao Z，Gupta K.Backbone-based Roadmaps for Robot Navigation in Sensor Networks［C］//2008 IEEE International Conference on Robotics and Automation，ICRA 2008.Pasadena，CA，USA，2008:1023－1029.

［17］梁華為，陳萬(wàn)明，李帥，等.基于無(wú)線傳感器網(wǎng)絡(luò)的移動(dòng)目標(biāo)導(dǎo)航方法［J］.傳感技術(shù)學(xué)報(bào)，2007，20(7):1620－1624.

［18］ Buragohain C，Agrawal D，Suri S.Distributed in-network Path Planning for Sensor Network Navigation in Dynamic Hazardous Environments［J］.Wireless Communications and Mobile Computing，2012，12(8):739－754.

［19］ Maheshwari R，Jain S，Das S R.A Measurement Study of Interference Modeling and Scheduling in Low-power Wireless Networks［C］//Proceedings of the 6th ACM conference on Embedded network sensor systems.Raleigh，NC，USA，2008:141－154.