左 丹 莫建軍 肖 勝

（1.海軍裝備部 北京 100083）（2.海軍92980部隊(duì) 湛江 524000）（3.海軍工程大學(xué) 武漢 430033）

1 引言

無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）是一種分布式、自組織網(wǎng)絡(luò)，具有覆蓋面廣、自適應(yīng)性強(qiáng)、布局方便靈活等許多優(yōu)點(diǎn)，在民用、航空和軍事領(lǐng)域均具有非常廣闊的應(yīng)用前景。

節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)中一項(xiàng)關(guān)鍵支撐技術(shù)和研究熱點(diǎn)。受資源、成本和應(yīng)用環(huán)境的限制，每個節(jié)點(diǎn)均配置GPS接收器或者人工部署顯得不現(xiàn)實(shí)，因此研究適合無線傳感器網(wǎng)絡(luò)特點(diǎn)的定位機(jī)制十分重要［1］。目前的方法大多是基于多個固定信標(biāo)節(jié)點(diǎn)實(shí)現(xiàn)的，如三邊定位法、三角測量法、DV－HOP法、質(zhì)心法等［2～4］，要想取得較高的定位精度，往往對信標(biāo)節(jié)點(diǎn)的排布方式和數(shù)量存在較高的要求，還帶來了許多問題，主要表現(xiàn)在：在定位完成以后，信標(biāo)節(jié)點(diǎn)往往變?yōu)槠胀ü?jié)點(diǎn)使用，信標(biāo)節(jié)點(diǎn)過多會造成資源浪費(fèi)，提高網(wǎng)絡(luò)成本；另外，信標(biāo)節(jié)點(diǎn)過多可能導(dǎo)致計(jì)算負(fù)荷以及通訊負(fù)荷過大，影響實(shí)時性和可靠性。

因此，有人提出利用一個或幾個移動信標(biāo)來輔助定位。在這種方式下，裝備了GPS或其它定位裝置的移動信標(biāo)節(jié)點(diǎn)在部署區(qū)域內(nèi)移動，間隔一定距離或時間后發(fā)送當(dāng)前位置信息，未知節(jié)點(diǎn)根據(jù)接收到的信息完成自身位置估計(jì)，從而能減少信標(biāo)節(jié)點(diǎn)數(shù)目，有效降低網(wǎng)絡(luò)成本［5～9］。這種方式能夠有效節(jié)約網(wǎng)絡(luò)成本，同時具有較高的定位精度。但是，移動信標(biāo)運(yùn)動過程結(jié)束后，少量節(jié)點(diǎn)由于離移動信標(biāo)的路徑較遠(yuǎn)，從而難以接收足夠的定位信息。針對這種情況，為提高定位覆蓋率，本文選取部分符合條件的節(jié)點(diǎn)對接收信息進(jìn)行轉(zhuǎn)發(fā)，提出一種基于增量定位的移動信標(biāo)輔助節(jié)點(diǎn)定位算法。

2 相關(guān)模型

2.1 信號傳輸模型

這里采用距離邊界模型。假設(shè)發(fā)送節(jié)點(diǎn)可以將信號傳輸給其通信半徑范圍內(nèi)的未知節(jié)點(diǎn)。假設(shè)d表示發(fā)送節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的距離，R表示發(fā)送節(jié)點(diǎn)的通信半徑（發(fā)送節(jié)點(diǎn)可能是移動信標(biāo)，也可能是普通節(jié)點(diǎn)）。未知節(jié)點(diǎn)接收到移動信標(biāo)廣播信息的概率為P（d）。模型的數(shù)學(xué)描述如下：

同樣的，如果未知節(jié)點(diǎn)與信標(biāo)之間的距離小于R，則能夠接收到發(fā)送節(jié)點(diǎn)的廣播信息；否則，未知節(jié)點(diǎn)接收不到其廣播信息。

2.2 增量定位模型

如果移動信標(biāo)的路徑間距較大，在定位過程結(jié)束后，可能有少量節(jié)點(diǎn)可能由于離移動信標(biāo)的路徑較遠(yuǎn)，從而難以接收足夠的定位信息。為克服該問題，本文選取部分普通節(jié)點(diǎn)對接收到的信息進(jìn)行轉(zhuǎn)發(fā)，未知節(jié)點(diǎn)不但可以利用移動信標(biāo)的連續(xù)廣播信息，而且可以結(jié)合其它普通節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息完成增量定位，從而提高算法的定位覆蓋率。

2.2.1 利用移動信標(biāo)的連續(xù)廣播信息

基于如下判斷：如果移動信標(biāo)連續(xù)兩次廣播信息中有且僅有一次被某個未知節(jié)點(diǎn)接收，則該未知節(jié)點(diǎn)必將剛剛進(jìn)入或離開移動信標(biāo)的信號傳輸范圍。為簡化計(jì)算，假設(shè)移動信標(biāo)以速度v作勻速直線運(yùn)動，其通信半徑為Rd，廣播周期為T。圖1顯示了節(jié)點(diǎn)利用移動信標(biāo)的連續(xù)廣播信息進(jìn)行定位的示意圖。

圖1 利用移動信標(biāo)的連續(xù)廣播信息定位

如圖所示，當(dāng)移動信標(biāo)處于A點(diǎn)時，未知節(jié)點(diǎn)未接收到廣播信息，而經(jīng)過一個廣播周期后，未知節(jié)點(diǎn)接收到移動信標(biāo)在B點(diǎn)的廣播信息。可以推斷，未知節(jié)點(diǎn)必定處于以A點(diǎn)為圓心、Rd為半徑的通信圓外，同時處于以B點(diǎn)為圓心、Rd為半徑的通信圓內(nèi)。假設(shè)經(jīng)過經(jīng)過k個廣播周期后，信標(biāo)節(jié)點(diǎn)運(yùn)動至C點(diǎn)，此時未知節(jié)點(diǎn)能夠接收到最后一個廣播信息（未能接收到信標(biāo)在后一廣播位置D點(diǎn)發(fā)送的信息），同樣可以推斷，未知節(jié)點(diǎn)必定在以C點(diǎn)為圓心、Rd為半徑的通信圓內(nèi)，同時處于以D點(diǎn)為圓心、Rd為半徑的通信圓外。利用所得到的約束條件，可以獲取未知節(jié)點(diǎn)初步的可能區(qū)域［12］。

2.2.2 利用普通節(jié)點(diǎn)的轉(zhuǎn)發(fā)信息

為提高定位覆蓋率，選取部分普通節(jié)點(diǎn)對接收的移動信標(biāo)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，以實(shí)現(xiàn)對未知節(jié)點(diǎn)的增量定位。數(shù)據(jù)包內(nèi)容包括ID和信標(biāo)的位置信息。為減少能量消耗，節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的頻率并不是周期性的，而是每當(dāng)接收到移動信標(biāo)的廣播信息后，才向外轉(zhuǎn)發(fā)一次。這樣可以保證其每次轉(zhuǎn)發(fā)的信息都包含不同的信標(biāo)位置信息，從而提高轉(zhuǎn)發(fā)效率。圖2為該過程的示意圖。

圖2 普通節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播信息示意圖

為減少累積誤差的影響，要求滿足以下條件的節(jié)點(diǎn)才能被選作轉(zhuǎn)發(fā)節(jié)點(diǎn)：

1）該節(jié)點(diǎn)本身已完成定位，即至少接收到三個（或以上）來自移動信標(biāo)或其它節(jié)點(diǎn)的非共線位置信息。

2）該節(jié)點(diǎn)之前接收到的廣播信息中有一半以上來自移動信標(biāo)。

另外，由于未知節(jié)點(diǎn)可以通過接收其它節(jié)點(diǎn)的數(shù)據(jù)包來進(jìn)行定位，數(shù)據(jù)包生存期越大，定位覆蓋率也越大。但是，數(shù)據(jù)包的生存期越大，數(shù)據(jù)包的收發(fā)次數(shù)就越大，通信開銷也越大，這里設(shè)置數(shù)據(jù)包的生存期為兩跳。當(dāng)一跳內(nèi)的普通節(jié)點(diǎn)收到信標(biāo)后，包的生存期減1，并將添加該節(jié)點(diǎn)的位置信息字段，向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，鄰居節(jié)點(diǎn)接收后根據(jù)ID判斷此數(shù)據(jù)包是否已經(jīng)存在，若不存在則添加此包，否則丟棄?？梢钥闯觯撘?guī)則本質(zhì)上是一個簡單的分布式最短路由協(xié)議。表1為數(shù)據(jù)包的主要字段。

表1 數(shù)據(jù)包主要字段（a）移動信標(biāo)數(shù)據(jù)包

其中，TI（Transmit Indicator）為轉(zhuǎn)發(fā)標(biāo)識，TI＝0表示該數(shù)據(jù)包來自移動信標(biāo)，TI＝1表示該廣播信息來自普通節(jié)點(diǎn)。

通過數(shù)據(jù)包的轉(zhuǎn)發(fā)，部分處于移動信標(biāo)通信范圍之外的節(jié)點(diǎn)也可以得到定位信息，從而可以提高定位覆蓋率；同時，由于只有滿足一定約束條件的普通節(jié)點(diǎn)會被選中進(jìn)行轉(zhuǎn)發(fā)，因此節(jié)點(diǎn)的定位誤差不會產(chǎn)生較大的累積。

3 算法流程

每個普通節(jié)點(diǎn)都建立一個數(shù)據(jù)鏈表，用來存儲接收到的廣播信息，未知節(jié)點(diǎn)通過接收移動信標(biāo)和其它轉(zhuǎn)發(fā)節(jié)點(diǎn)的數(shù)據(jù)包進(jìn)行定位。這里對算法流程進(jìn)行簡要描述：

1）移動信標(biāo)在運(yùn)動過程中不斷周期性的廣播信息。移動信標(biāo)按照實(shí)現(xiàn)規(guī)劃的路徑運(yùn)動，廣播包括自身位置的數(shù)據(jù)包。

2）普通節(jié)點(diǎn)接收到數(shù)據(jù)包后，將數(shù)據(jù)包存儲在自身數(shù)據(jù)鏈表中，并判斷是否滿足前面介紹的轉(zhuǎn)發(fā)節(jié)點(diǎn)條件。（1）條件滿足，則對TI進(jìn)行判別：如TI＝0，將該數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，并在該數(shù)據(jù)包中添加自身位置信息字段；如TI＝1，不進(jìn)行轉(zhuǎn)發(fā)。（2）條件不滿足，則僅將該信息用作節(jié)點(diǎn)自身定位，不進(jìn)行轉(zhuǎn)發(fā)。

3）隨著移動信標(biāo)的不斷運(yùn)動，網(wǎng)絡(luò)中的定位節(jié)點(diǎn)將不斷增多，而未定位節(jié)點(diǎn)將越來越少，直至整個定位過程結(jié)束。

4 仿真結(jié)果

為驗(yàn)證所述算法的有效性，進(jìn)行了仿真分析。初始條件設(shè)置如下：200個浮標(biāo)節(jié)點(diǎn)隨機(jī)分布在2400m×2400m的某矩形區(qū)域，設(shè)左下角為坐標(biāo)原點(diǎn)。移動信標(biāo)的運(yùn)動路徑如圖3所示，起點(diǎn)為（－200，0），終點(diǎn)為（2600，2400），路徑平行線之間的間隔L＝400m，移動信標(biāo)的速度為20m／s，通信半徑為200m，普通節(jié)點(diǎn)的通信半徑為100m，信號傳輸?shù)牟灰?guī)則度DOI＝0.05。

4.1 與質(zhì)心定位方法的比較

分別在L＝400m和L＝600m的條件下，將傳統(tǒng)方法（普通節(jié)點(diǎn)不轉(zhuǎn)發(fā)信息）和基于增量定位的定位方法進(jìn)行了比較，結(jié)果分別如表2和表3所示。

圖3 移動信標(biāo)的運(yùn)動路徑

表2 間距為400m的算法性能比較

表3 間距為600m的算法性能比較

可以看出，當(dāng)L＝400m時，兩種方法的定位覆蓋率幾乎都達(dá)到100%。但當(dāng)L＝600m時，由于路徑間距大于兩倍通信半徑，移動信標(biāo)的廣播信息難以覆蓋整個網(wǎng)絡(luò)，此時，傳統(tǒng)方法的定位覆蓋率較之前下降很快，而所提出的方法通過選取部分節(jié)點(diǎn)對移動信標(biāo)的廣播信息進(jìn)行轉(zhuǎn)發(fā)，能夠維持較高的定位覆蓋率。同時，未知節(jié)點(diǎn)還能獲取更多的定位信息，因此獲得了較好的定位精度。此時，基于增量定位的移動信標(biāo)輔助節(jié)點(diǎn)定位算法在定位覆蓋率和定位精度兩項(xiàng)指標(biāo)上均優(yōu)于傳統(tǒng)方法，更適用于移動信標(biāo)路徑間距較大的場合。

4.2 與質(zhì)心定位方法的比較

圖4 不同廣播周期下的定位精度

在前面仿真場景的基礎(chǔ)上，保持其它參數(shù)不變，調(diào)整移動信標(biāo)的廣播周期，得到的平均定位誤差如圖4所示?？梢姡S著廣播周期的增長，該算法的平均定位誤差也顯著增加。這主要是由于廣播周期變大后，節(jié)點(diǎn)獲取的定位信息將減少。同時，在信標(biāo)通信半徑較大的情況下，未知節(jié)點(diǎn)將獲得更多來自移動信標(biāo)的廣播信息，因此平均定位誤差也將減小。

另外，在前面仿真場景的基礎(chǔ)上，調(diào)整普通節(jié)點(diǎn)的通信半徑，算法性能的仿真結(jié)果如表4所示。

表4 節(jié)點(diǎn)通信半徑對算法性能的影響

5 結(jié)語

本文針對無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位問題，初步考慮節(jié)點(diǎn)之間的協(xié)作，提出一種基于增量定位的移動信標(biāo)輔助節(jié)點(diǎn)定位算法。該算法針對網(wǎng)絡(luò)中可能有少量節(jié)點(diǎn)難以接收足夠定位信息的情況，選取部分節(jié)點(diǎn)對接收信息進(jìn)行轉(zhuǎn)發(fā)，以提高定位覆蓋率。通過仿真可以看出，在移動信標(biāo)的路徑長度和通信半徑不變的情況下，該方法可獲取較高的定位覆蓋率，適用于信標(biāo)路徑間距較大的場合。

［1］Akyildiz I F，Su W.Wireless Sensor Network：A Survey［J］.Computer Networks，2002，38（4）：393－422.

［2］Patwari N，Hero III AO，Perkins M，et al.Relative location estimation in wireless sensor networks［J］.IEEE Trans on Signal Processing，2003，51（8）：2137－2148.

［3］Bulusu N，Heidemann J，Estrin D.GPS－less low cost outdoor localization for very small devices［C］／／IEEE Personal Communication，2000，7（5）：28－34.

［4］Bahl P，Padmanabhan VN.RADAR：An In－building RF－based User Location and Tracking System［C］／／Proc.of the 19th Annual Joint Conference on IEEE Computer and Communications Societies.Aviv，Israel：IEEE Press，2000：775－784.

［5］Sichitiu ML，Ramadurai V.Localization of Wireless Sensor Networks with a Mobile Beacon［C］／／Proceedings of the 1st IEEE Conference on Mobile Ad－Hoc and Sensor Systems.IEEE Computer Society，2004：174－183.

［6］Pathirana P N，Bulusu N.Node localization using mobile robots in delay－tolerant sensor networks［J］.IEEE Transactions on Mobile Computing，2005，4（3）：285－296.

［7］Priyantha N，Balakrishnan.Mobile assiated localization in wireless sensor network［C］／／Proceedings of 24th IEEE Conference on Computer Communication.Miami，USA，2005：172－183.

［8］Dimitrios K，Saumitra M，Charlie Y.Path Planning of Mobile Landmarks for Localization in Wireless Sensor Networks［J］.Computer Communications，2007（30）：2577－2592.

［9］白鳳娥，孔新店，牟匯慧.無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議改進(jìn)算法［J］.計(jì)算機(jī)與數(shù)字工程，2011，39（2）.

［10］孫昕，王鑫.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)動態(tài)密鑰管理方案［J］.計(jì)算機(jī)與數(shù)字工程，2011，39（10）.

［11］Aram G，Bhaskar K，Kristina L，et al.Distributed online localization in sensor networks using a moving target［C］／／Proceedings of the 3rd International Conference on Information Processing in Sensor Networks.Los Angeles，USA，2004：61－70.

［12］Bin Xiao，Hekang Chen，Shuigeng Zhou.Distributed Localization Using a Moving Beacon in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed System，2008，19（5）：587－600.