徐 駿,吳 敏,沙 超,倪凱悅,王汝傳

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院,江蘇 南京 210003)

基于移動(dòng)信標(biāo)的響應(yīng)式傳感網(wǎng)定位方法

徐 駿,吳 敏,沙 超,倪凱悅,王汝傳

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院、軟件學(xué)院,江蘇 南京 210003)

相對(duì)于靜態(tài)錨節(jié)點(diǎn)定位算法而言，基于移動(dòng)錨節(jié)點(diǎn)的定位機(jī)制能較好地提升定位的準(zhǔn)確性。由于受到移動(dòng)性的限制，某些靜態(tài)錨節(jié)點(diǎn)定位時(shí)會(huì)出現(xiàn)誤差過(guò)大的情況。為此，提出了基于蜂窩模型的移動(dòng)定位算法。該算法應(yīng)用中心錨節(jié)點(diǎn)和邊緣錨節(jié)點(diǎn)協(xié)作遍歷模型的中心和邊緣位置，可快速定位覆蓋區(qū)域的未知節(jié)點(diǎn)，且能去除移動(dòng)規(guī)劃設(shè)計(jì)中的冗余路徑，避免了同一路徑的冗余重復(fù)訪問(wèn)，有助于保證錨節(jié)點(diǎn)移動(dòng)的高效性和準(zhǔn)確性。該算法通常從捕獲的三個(gè)錨節(jié)點(diǎn)信息篩選出RSSI信號(hào)強(qiáng)度較大的兩個(gè)，以避免引入誤差過(guò)大的距離值，根據(jù)信號(hào)強(qiáng)度的衰減模型求解可以得到兩個(gè)位置信息，并由第三個(gè)距離信息作為判斷條件，唯一確定未知節(jié)點(diǎn)的坐標(biāo)信息。仿真結(jié)果表明，所提出的定位算法定位精度較好且定位的時(shí)間效率較高。

蜂窩模型；協(xié)作遍歷；移動(dòng)信標(biāo)；RSSI

0 引 言

無(wú)線傳感網(wǎng)技術(shù)在現(xiàn)實(shí)生活中應(yīng)用廣泛。通過(guò)在指定區(qū)域部署低功耗的傳感器節(jié)點(diǎn)，可實(shí)現(xiàn)目標(biāo)追蹤、資源勘探、環(huán)境監(jiān)測(cè)等應(yīng)用。這些應(yīng)用都要基于位置信息的捕獲，其中定位技術(shù)起到了關(guān)鍵作用[1-3]。

節(jié)點(diǎn)定位的過(guò)程就是通過(guò)相關(guān)的技術(shù)手段獲取網(wǎng)絡(luò)結(jié)構(gòu)中未知節(jié)點(diǎn)的絕對(duì)或相對(duì)位置信息。根據(jù)定位過(guò)程中是否需要測(cè)距，無(wú)線傳感器節(jié)點(diǎn)定位可以采用基于測(cè)距的定位技術(shù)和無(wú)需測(cè)距的定位技術(shù)。其中基于測(cè)距的定位方法需要額外的硬件支持，定位精度較高但容易受到環(huán)境因素的影響；而無(wú)需測(cè)距技術(shù)雖然定位精度較低，但是成本低且不易受外界環(huán)境的影響。

根據(jù)錨節(jié)點(diǎn)是否具有移動(dòng)性，定位算法還可以分為靜態(tài)定位算法和動(dòng)態(tài)定位算法。通常采用靜態(tài)定位時(shí)需要錨節(jié)點(diǎn)密度達(dá)到一定的程度來(lái)滿足節(jié)點(diǎn)之間的連通性[4]。而動(dòng)態(tài)定位算法可以使用較少的錨節(jié)點(diǎn)，而且部署更加靈活多變，近年來(lái)在定位領(lǐng)域應(yīng)用廣泛[5-8]。

移動(dòng)的信標(biāo)節(jié)點(diǎn)沿著事先設(shè)計(jì)好的移動(dòng)路徑遍歷整個(gè)網(wǎng)絡(luò)區(qū)域，并在移動(dòng)到相應(yīng)的位置廣播消息包。未知節(jié)點(diǎn)捕獲來(lái)自錨節(jié)點(diǎn)的消息包后保存并進(jìn)行分析，可以計(jì)算出未知節(jié)點(diǎn)的估計(jì)位置坐標(biāo)[9-11]。

目前的移動(dòng)定位算法移動(dòng)的隨機(jī)性太大，移動(dòng)的路徑規(guī)劃存在不合理的情況，效率較低。且在定位移動(dòng)的過(guò)程中節(jié)點(diǎn)的配合協(xié)作性不高，從而導(dǎo)致節(jié)點(diǎn)的定位誤差較大。

為此，提出了改進(jìn)的RSSI定位算法以提升定位精度。在此基礎(chǔ)上，設(shè)計(jì)了基于蜂窩模型的移動(dòng)規(guī)劃路徑，定義了中心錨節(jié)點(diǎn)和邊緣錨節(jié)點(diǎn)分別遍歷蜂窩區(qū)域的中心位置和六個(gè)邊緣位置，并在相應(yīng)的區(qū)域廣播消息包，以保證定位區(qū)域的位置節(jié)點(diǎn)至少捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的消息包。仿真驗(yàn)證結(jié)果表明，所提出的移動(dòng)定位算法在定位精度和定位的時(shí)間效率上均有明顯改善。

1 相關(guān)工作

使用移動(dòng)定位算法來(lái)求解未知節(jié)點(diǎn)坐標(biāo)時(shí)，移動(dòng)錨節(jié)點(diǎn)會(huì)沿著設(shè)計(jì)好的移動(dòng)軌跡移動(dòng)，并在相應(yīng)的位置停留一小段時(shí)間來(lái)廣播自身的消息包，而且需要保證待定位的未知節(jié)點(diǎn)至少需要捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的消息才能確定唯一的位置信息。

移動(dòng)錨節(jié)點(diǎn)定位算法相對(duì)于固定錨節(jié)點(diǎn)定位算法而言，不會(huì)因?yàn)殄^節(jié)點(diǎn)的位置分布不均勻而導(dǎo)致某些節(jié)點(diǎn)無(wú)法定位，在很大程度上減少了錨節(jié)點(diǎn)的使用數(shù)量，而且能夠設(shè)計(jì)好的移動(dòng)路徑算法來(lái)保證每個(gè)未知節(jié)點(diǎn)都能至少捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的消息包。從以上分析可知，相對(duì)于固定的錨節(jié)點(diǎn)定位算法，移動(dòng)錨節(jié)點(diǎn)定位算法在成本和效率上都有明顯提升。

在文獻(xiàn)[12]中，基于高斯馬爾可夫模型設(shè)計(jì)移動(dòng)的規(guī)劃路徑，分別設(shè)定了移動(dòng)錨節(jié)點(diǎn)的速度和方向，并對(duì)速度和方向分別引入了高斯隨機(jī)變量。節(jié)點(diǎn)的定位采用加權(quán)質(zhì)心算法，對(duì)距離值求解倒數(shù)作為其在總體樣本中的權(quán)值來(lái)求解具體的距離值。定位過(guò)程的權(quán)值求解過(guò)于簡(jiǎn)單，并不能很好地規(guī)避求解的距離誤差值。此外，高斯馬爾可夫移動(dòng)模型隨機(jī)性太大，導(dǎo)致錨節(jié)點(diǎn)遍歷路徑存在很多的重復(fù)路徑，移動(dòng)的效率較低。

文獻(xiàn)[13]采用MB-DV-Hop定位算法來(lái)實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的定位操作，移動(dòng)錨節(jié)點(diǎn)通過(guò)螺旋式移動(dòng)軌跡來(lái)遍歷網(wǎng)絡(luò)區(qū)域。未知節(jié)點(diǎn)實(shí)時(shí)捕獲來(lái)自錨節(jié)點(diǎn)的數(shù)據(jù)包，當(dāng)數(shù)據(jù)包個(gè)數(shù)達(dá)到三個(gè)時(shí)，就可以確定自身的坐標(biāo)，進(jìn)而轉(zhuǎn)化為靜態(tài)錨節(jié)點(diǎn)。再通過(guò)DV-Hop定位算法計(jì)算出移動(dòng)錨節(jié)點(diǎn)和靜態(tài)錨節(jié)點(diǎn)之間的平均跳距值，實(shí)現(xiàn)對(duì)尚未能定位節(jié)點(diǎn)的定位操作。但是DV-Hop定位算法節(jié)點(diǎn)的定位精度不高，且移動(dòng)錨節(jié)點(diǎn)的移動(dòng)路徑長(zhǎng)度過(guò)大，效率不高。

文獻(xiàn)[14]使用三重定位覆蓋模型，并在錨節(jié)點(diǎn)移動(dòng)過(guò)程中會(huì)一直廣播包含自身位置信息的消息包。同時(shí)處在該模型區(qū)域的未知節(jié)點(diǎn)會(huì)實(shí)時(shí)地捕獲消息包，并通過(guò)比較來(lái)保存來(lái)自錨節(jié)點(diǎn)信號(hào)強(qiáng)度最大的消息包，將兩個(gè)最大的RSSI值所處的點(diǎn)坐標(biāo)值作為未知節(jié)點(diǎn)在邊上的投影點(diǎn)，取通過(guò)這兩個(gè)投影點(diǎn)的垂線的交點(diǎn)作為未知節(jié)點(diǎn)的坐標(biāo)值。單個(gè)錨節(jié)點(diǎn)的移動(dòng)路徑也是基于三重覆蓋模型，從而保證每個(gè)未知節(jié)點(diǎn)都能至少捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的消息包。錨節(jié)點(diǎn)移動(dòng)過(guò)程中一直廣播消息包會(huì)造成能量的浪費(fèi)，同時(shí)移動(dòng)路徑算法的效率不是很高。

文獻(xiàn)[15]也是基于三重覆蓋模型，提出移動(dòng)路徑規(guī)劃算法LTC和STC，并通過(guò)比較得出STC的移動(dòng)效率較高。STC移動(dòng)的思想是通過(guò)三個(gè)錨節(jié)點(diǎn)的相互配合來(lái)實(shí)現(xiàn)交替移動(dòng)，組成一個(gè)單位的三重覆蓋模型來(lái)保證未知節(jié)點(diǎn)捕獲到來(lái)自錨節(jié)點(diǎn)的消息包。定位算法使用TDOA，定位精度較高，但是要求使用額外的硬件設(shè)備，成本較高。使用三個(gè)錨節(jié)點(diǎn)來(lái)實(shí)現(xiàn)移動(dòng)路徑規(guī)劃，錨節(jié)點(diǎn)的利用效率不是很高。

這里基于蜂窩模型，并設(shè)定兩個(gè)錨節(jié)點(diǎn)分別遍歷蜂窩模型的中心位置和邊緣頂點(diǎn)位置，保證在定位區(qū)域的未知節(jié)點(diǎn)至少能夠捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的消息包，并記錄到達(dá)未知節(jié)點(diǎn)的信號(hào)強(qiáng)度值并根據(jù)信號(hào)衰減模型計(jì)算出對(duì)應(yīng)的距離信息，從而保證未知節(jié)點(diǎn)能實(shí)現(xiàn)定位操作。此外，還對(duì)RSSI定位算法進(jìn)行了改進(jìn)，在三邊定位過(guò)程中只捕獲最大的兩個(gè)信號(hào)強(qiáng)度，并利用最小的信號(hào)強(qiáng)度求解估計(jì)距離來(lái)最終判斷未知節(jié)點(diǎn)的坐標(biāo)。

2 RSSI定位算法優(yōu)化

對(duì)于移動(dòng)定位算法而言，是由多個(gè)定位算法沿著一個(gè)移動(dòng)路徑組成，需要確定相應(yīng)的定位模型和定位算法。

2.1 定位模型

三個(gè)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的通信距離均小于錨節(jié)點(diǎn)廣播消息的最大通信半徑。假設(shè)三個(gè)錨節(jié)點(diǎn)的坐標(biāo)分別為(xA,yA)、(xB,yB)、(xC,yC)，未知節(jié)點(diǎn)的坐標(biāo)為(xN,yN)以及到三個(gè)錨節(jié)點(diǎn)的距離分別為dA、dB和dC。根據(jù)距離公式求解可得：

(1)

(2)

(3)

將上面的公式整理可得：

(4)

上式簡(jiǎn)寫成：

(5)

(6)

根據(jù)式(5)分析，方程有且只有唯一解。

由此可得，對(duì)于某個(gè)未知節(jié)點(diǎn)進(jìn)行定位操作，則至少需要捕獲到三個(gè)錨節(jié)點(diǎn)的信息。

如圖1(左)所示，錨節(jié)點(diǎn)A的通信半徑所覆蓋的圓形區(qū)域，至少需六個(gè)額外的錨節(jié)點(diǎn)才能保證對(duì)該圓形覆蓋區(qū)域的所有未知節(jié)點(diǎn)實(shí)現(xiàn)定位操作。

圖1 通信覆蓋模型(左)與蜂窩模型(右)

將圖1的通信覆蓋模型簡(jiǎn)化為蜂窩模型，每個(gè)小的三角形構(gòu)成的區(qū)域都至少能捕獲到來(lái)自三個(gè)錨節(jié)點(diǎn)的信息。

分別定義兩個(gè)移動(dòng)的錨節(jié)點(diǎn)為中心錨節(jié)點(diǎn)和邊緣錨節(jié)點(diǎn)。中心錨節(jié)點(diǎn)遍歷蜂窩模型的中心位置，而邊緣錨節(jié)點(diǎn)分別遍歷蜂窩模型的六個(gè)頂點(diǎn)位置，且兩個(gè)錨節(jié)點(diǎn)分別在對(duì)應(yīng)的位置上廣播包含自身坐標(biāo)信息的消息包。依靠?jī)蓚€(gè)錨節(jié)點(diǎn)的分工協(xié)作能夠保證該區(qū)域的未知節(jié)點(diǎn)至少能捕獲到三個(gè)錨節(jié)點(diǎn)的信息包，從而實(shí)現(xiàn)定位操作。

2.2 消除最大誤差的改進(jìn)定位方案

基于RSSI的測(cè)距技術(shù)無(wú)需特殊硬件，在成本和功耗上都較低，因此在無(wú)線傳感器定位算法中得到了廣泛應(yīng)用。其中主要使用的無(wú)線電傳播模型有三類，其中最常用的是Shadowing[16]模型：

(7)

其中,PLd0表示初始信號(hào)強(qiáng)度;α表示射頻信號(hào)的衰減指數(shù);xσ表示方差為σ的對(duì)數(shù)誤差。

對(duì)圖1中蜂窩模型的三角形定位區(qū)域進(jìn)行分析，假設(shè)三個(gè)錨節(jié)點(diǎn)的坐標(biāo)值為(xA,yA)、(xB,yB)和(xC,yC)，以及未知節(jié)點(diǎn)D的坐標(biāo)為(xD,yD)。三個(gè)錨節(jié)點(diǎn)A、B和C分別向未知節(jié)點(diǎn)D發(fā)送數(shù)據(jù)包。篩選出RSSI信號(hào)強(qiáng)度最大的兩個(gè)錨節(jié)點(diǎn)信息表項(xiàng),并根據(jù)信號(hào)強(qiáng)度的衰減模型分別計(jì)算出這兩個(gè)距離信息。去除掉信號(hào)強(qiáng)度最弱的信息值，是為了避免引入誤差過(guò)大的距離值，從而能夠提高定位精度。

圖2 節(jié)點(diǎn)定位模型(左)及其所捕獲的信號(hào)強(qiáng)度近似相等的情形(右)

當(dāng)捕獲到來(lái)自兩個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度近似相等且小于來(lái)自另外一個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度時(shí)，將采用如下判定方法：

如圖2(右)所示，未知節(jié)點(diǎn)D捕獲到的來(lái)自錨節(jié)點(diǎn)B和C的信號(hào)強(qiáng)度近似相等，則可以確定未知節(jié)點(diǎn)D處在線段BC的中垂線附近。又有來(lái)自錨節(jié)點(diǎn)A的信號(hào)強(qiáng)度最大，則可以得到較為可信的未知節(jié)點(diǎn)D和A之間的距離信息為dD，從而可以求解出未知節(jié)點(diǎn)D的坐標(biāo)。求解過(guò)程如下：

由D近似處在線段BC的中垂線上，可以得到線段AD近似垂直于線段BC。為了便于計(jì)算，引入橫坐標(biāo)和縱坐標(biāo)的誤差值為xα和yα，則有：

(8)

且錨節(jié)點(diǎn)A和未知節(jié)點(diǎn)的距離為d，則有：

(9)

根據(jù)式(8)和式(9)，可以唯一確定未知節(jié)點(diǎn)D的坐標(biāo)值。

當(dāng)來(lái)自三個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度都近似相等，則可以確定未知節(jié)點(diǎn)D處在三個(gè)錨節(jié)點(diǎn)組成的三角形區(qū)域的中心附近。

該定位算法與傳統(tǒng)的RSSI三邊定位算法相比，去除誤差值最大的信號(hào)強(qiáng)度值。根據(jù)RSSI信號(hào)衰減模型可知，根據(jù)信號(hào)強(qiáng)度求得的距離值越大，該距離值與實(shí)際值的誤差也越大。因此排除掉信號(hào)強(qiáng)度最弱的信息值，可以相應(yīng)地減小定位的誤差值。

3 信標(biāo)節(jié)點(diǎn)移動(dòng)路徑設(shè)計(jì)

在完成了具體的定位算法后，需要對(duì)整體的信標(biāo)移動(dòng)路徑進(jìn)行設(shè)計(jì)。信標(biāo)移動(dòng)路徑設(shè)計(jì)的好壞在很大程度上決定了能夠訪問(wèn)的未知節(jié)點(diǎn)的總數(shù)、定位過(guò)程的總時(shí)間和精度等因素。

假設(shè)帶定位節(jié)點(diǎn)部署在一個(gè)W×L的矩形網(wǎng)絡(luò)區(qū)域內(nèi)，且移動(dòng)錨節(jié)點(diǎn)通信半徑為R。

文獻(xiàn)[15]提出了基于三重覆蓋優(yōu)化的STC移動(dòng)路徑規(guī)劃算法，主要使用三個(gè)錨節(jié)點(diǎn)A、B和C交替移動(dòng)來(lái)實(shí)現(xiàn)移動(dòng)定位。STC具體移動(dòng)路徑如圖3所示。從最左端的三角形A1B1C1開始，錨節(jié)點(diǎn)A從開始的A1位置移動(dòng)到相對(duì)于線段B1C1的對(duì)稱位置A2；接著錨節(jié)點(diǎn)B從位置B1移動(dòng)到相對(duì)于線段C1A2的對(duì)稱位置B2；然后錨節(jié)點(diǎn)C從位置C1移動(dòng)到相對(duì)于線段A2B2的對(duì)稱位置C2，后續(xù)的節(jié)點(diǎn)移動(dòng)以此類推。

圖3 STC的信標(biāo)移動(dòng)路徑

(10)

這里設(shè)計(jì)的移動(dòng)路徑是基于蜂窩模型的移動(dòng)軌跡，主要由一個(gè)中心錨節(jié)點(diǎn)和一個(gè)邊緣錨節(jié)點(diǎn)配合來(lái)完成軌跡移動(dòng)。中心錨節(jié)點(diǎn)移動(dòng)到蜂窩模型的中心時(shí)，會(huì)通知邊緣錨節(jié)點(diǎn)訪問(wèn)蜂窩模型相應(yīng)的邊緣節(jié)點(diǎn)位置。如圖4所示，粗實(shí)線表示中心錨節(jié)點(diǎn)移動(dòng)的軌跡，粗虛線表示邊緣錨節(jié)點(diǎn)移動(dòng)的軌跡。

圖4 設(shè)計(jì)的錨節(jié)點(diǎn)移動(dòng)模型

(11)

由此分析得，該算法的移動(dòng)路徑長(zhǎng)度小于STC的移動(dòng)路徑長(zhǎng)度，且只使用了兩個(gè)錨節(jié)點(diǎn)，而STC中使用了三個(gè)錨節(jié)點(diǎn)。就路徑長(zhǎng)度和錨節(jié)點(diǎn)使用個(gè)數(shù)上分析可知，該路徑算法優(yōu)于STC路徑算法。

下面分析訪問(wèn)一個(gè)未知節(jié)點(diǎn)所需的平均時(shí)間。當(dāng)三個(gè)錨節(jié)點(diǎn)組成三重覆蓋模型時(shí)，該區(qū)域內(nèi)的節(jié)點(diǎn)就能實(shí)現(xiàn)定位。假設(shè)單位時(shí)間內(nèi)移動(dòng)的步長(zhǎng)為R，網(wǎng)絡(luò)模型的長(zhǎng)和寬分別設(shè)為L(zhǎng)和W，為了便于分析，假設(shè)節(jié)點(diǎn)均勻分布，每個(gè)三角形區(qū)域分布的節(jié)點(diǎn)數(shù)均為n。

對(duì)文獻(xiàn)[1]中的錨節(jié)點(diǎn)移動(dòng)軌跡分析得：

(12)

對(duì)錨節(jié)點(diǎn)移動(dòng)軌跡進(jìn)行分析得：

(13)

由式(12)-式(13)得：

(14)

當(dāng)L?R時(shí)可以得到上面的結(jié)果大于零。由此分析，對(duì)同一個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，該路徑移動(dòng)算法定位一個(gè)未知節(jié)點(diǎn)平均所需的時(shí)間較少。

4 仿真實(shí)驗(yàn)

將所提出的定位算法命名為MLD，并與單個(gè)錨節(jié)點(diǎn)的路徑規(guī)劃TRI[14]，以及文獻(xiàn)[15]提出的STC路徑規(guī)劃作對(duì)比實(shí)驗(yàn)。好的移動(dòng)規(guī)劃應(yīng)該能夠盡可能短地設(shè)計(jì)移動(dòng)路徑，并且能較好地提高節(jié)點(diǎn)的定位精度，此外還要在盡可能短的時(shí)間內(nèi)定位更多的節(jié)點(diǎn)。

實(shí)驗(yàn)從三個(gè)方面來(lái)分析定位算法的性能：

(1)相等時(shí)間內(nèi)能夠定位的節(jié)點(diǎn)比例；

(2)定位相同節(jié)點(diǎn)數(shù)錨節(jié)點(diǎn)移動(dòng)路徑總長(zhǎng)；

(3)節(jié)點(diǎn)定位誤差率。

采用Java對(duì)上述移動(dòng)定位算法進(jìn)行仿真實(shí)驗(yàn)。設(shè)定網(wǎng)絡(luò)未知節(jié)點(diǎn)的部署區(qū)域?yàn)?800 m×516 m)的矩形區(qū)域，內(nèi)有200個(gè)未知節(jié)點(diǎn)隨機(jī)分布其中。設(shè)定通信半徑為5 m、10 m、15 m和20 m。使用上述三種定位算法，并設(shè)定移動(dòng)步長(zhǎng)為R，且節(jié)點(diǎn)移動(dòng)到三重覆蓋模型的相應(yīng)位置時(shí)廣播數(shù)據(jù)包。

在相同的定位時(shí)間內(nèi)，移動(dòng)定位算法定位未知節(jié)點(diǎn)的比例能夠較好地反映定位算法的時(shí)間效率。定位節(jié)點(diǎn)的比例越高，說(shuō)明移動(dòng)定位算法移動(dòng)的時(shí)間效率越高。三種移動(dòng)定位算法的定位節(jié)點(diǎn)比例見圖5。

圖5 不同時(shí)間下的節(jié)點(diǎn)定位比例

隨著運(yùn)行時(shí)間和通信半徑R的增加，三種移動(dòng)定位算法的可定位節(jié)點(diǎn)數(shù)隨之增加。通信半徑的增加保證了在相同的移動(dòng)步長(zhǎng)下，錨節(jié)點(diǎn)廣播的消息包能夠被更多的未知節(jié)點(diǎn)捕獲到，從而能夠使更多的未知節(jié)點(diǎn)實(shí)現(xiàn)定位操作。

TRI可定位節(jié)點(diǎn)數(shù)最少，主要原因是單個(gè)錨節(jié)點(diǎn)沒有其他的輔助錨節(jié)點(diǎn)，在短時(shí)間內(nèi)移動(dòng)路徑長(zhǎng)度也較短，相對(duì)而言覆蓋未知節(jié)點(diǎn)的面積較小，這就導(dǎo)致定位的節(jié)點(diǎn)比例較少。MLD移動(dòng)定位算法相對(duì)STC而言，相同時(shí)間內(nèi)定位節(jié)點(diǎn)比例較高。主要原因是MLD和STC都是基于三重定位模型，且MLD的兩個(gè)錨節(jié)點(diǎn)的移動(dòng)路徑基本平行，不存在移動(dòng)路徑交叉的情況，在縱向上的移動(dòng)距離較少，從而避免了移動(dòng)路徑的過(guò)多冗余，保證了時(shí)間效率。此外，MLD只使用了兩個(gè)移動(dòng)錨節(jié)點(diǎn)，一定程度上節(jié)約了成本。

節(jié)點(diǎn)在定位的過(guò)程由于處在錨節(jié)點(diǎn)移動(dòng)覆蓋區(qū)域的盲區(qū)而導(dǎo)致節(jié)點(diǎn)的位置信息捕獲不到或誤差較大而導(dǎo)致節(jié)點(diǎn)無(wú)法定位。

遍歷完整個(gè)網(wǎng)絡(luò)后，可定位節(jié)點(diǎn)分析如表1所示。

表1 不同算法下的可定位節(jié)點(diǎn)分布情況

由表1可知，隨著通信半徑的增加，所能覆蓋的通信區(qū)域的面積也隨之增大，從而能減小定位盲區(qū)的面積。TRI由于是單個(gè)節(jié)點(diǎn)移動(dòng)來(lái)定位,且定位過(guò)程中根據(jù)信號(hào)強(qiáng)度的最大值的幾何運(yùn)算求解坐標(biāo)值，定位的誤差較大，從而導(dǎo)致節(jié)點(diǎn)定位的失效。STC和MLD的定位實(shí)現(xiàn)過(guò)程都是基于三重覆蓋定位模型，定位的原理基本相同，在相同通信半徑的情況下遍歷整個(gè)網(wǎng)絡(luò)區(qū)域后的整體定位的效率基本相同。

移動(dòng)相同的路徑所能定位的未知節(jié)點(diǎn)的比例也能夠反映移動(dòng)定位算法的效率，其實(shí)驗(yàn)結(jié)果如圖6所示。如果錨節(jié)點(diǎn)移動(dòng)的路徑長(zhǎng)度相同，而定位的節(jié)點(diǎn)數(shù)越多，則表明定位效率越好；反之說(shuō)明定位效率較差。

圖6 不同移動(dòng)路徑長(zhǎng)度節(jié)點(diǎn)定位比例圖

TRI算法實(shí)現(xiàn)的是單個(gè)錨節(jié)點(diǎn)的遍歷而不是多個(gè)節(jié)點(diǎn)協(xié)作式遍歷，從而導(dǎo)致在移動(dòng)相同路徑長(zhǎng)度的情況下節(jié)點(diǎn)的定位效率較差。STC算法在移動(dòng)過(guò)程需要三個(gè)移動(dòng)的錨節(jié)點(diǎn)來(lái)實(shí)現(xiàn)輔助定位，錨節(jié)點(diǎn)相對(duì)移動(dòng)的路徑長(zhǎng)度較大，而MLD移動(dòng)過(guò)程中只需要兩個(gè)錨節(jié)點(diǎn)，且基本上沿著直線移動(dòng)前進(jìn)，因此遍歷相同面積區(qū)域移動(dòng)的路徑長(zhǎng)度也就相對(duì)較短，從而可以定位更多的節(jié)點(diǎn)。

下面討論在不同的通信半徑下，訪問(wèn)整個(gè)網(wǎng)絡(luò)區(qū)域錨節(jié)點(diǎn)所移動(dòng)的路徑長(zhǎng)度，如圖7所示。訪問(wèn)的未知節(jié)點(diǎn)覆蓋的網(wǎng)絡(luò)區(qū)域的面積是恒定的，最終移動(dòng)路徑的長(zhǎng)短能夠較好地反映節(jié)點(diǎn)遍歷網(wǎng)絡(luò)區(qū)域的效率。

圖7 不同通信半徑下移動(dòng)路徑總長(zhǎng)度對(duì)比圖

隨著通信半徑的增大，能夠保證在相同的移動(dòng)路徑下遍歷更多的節(jié)點(diǎn)區(qū)域面積，因此節(jié)點(diǎn)的移動(dòng)路徑長(zhǎng)度也會(huì)隨之減少。TRI使用單個(gè)錨節(jié)點(diǎn)來(lái)遍歷該區(qū)域，不能實(shí)現(xiàn)分工協(xié)作，需要自身來(lái)完成更多的遍歷工作，也就導(dǎo)致移動(dòng)的路徑長(zhǎng)度偏大。STC移動(dòng)過(guò)程中是使用三個(gè)錨節(jié)點(diǎn)來(lái)實(shí)現(xiàn)遍歷，移動(dòng)路徑存在較多的交叉情況而不是平行進(jìn)行的，導(dǎo)致效率降低。而MLD在移動(dòng)過(guò)程中，中心錨節(jié)點(diǎn)和邊緣錨節(jié)點(diǎn)是平行移動(dòng)的，不存在交叉，顯著提高了遍歷的效率。

5 結(jié)束語(yǔ)

移動(dòng)信標(biāo)輔助定位中錨節(jié)點(diǎn)的移動(dòng)性保證了未知節(jié)點(diǎn)至少能夠捕獲到三個(gè)錨節(jié)點(diǎn)的信息，從而保證了定位的精度要求，減少了錨節(jié)點(diǎn)的使用數(shù)量，降低了定位成本。為此，提出的移動(dòng)定位算法使用兩個(gè)錨節(jié)點(diǎn)來(lái)分別遍歷蜂窩模型的中心和邊緣位置。采用改進(jìn)的RSSI定位算法，能較好地提高定位的精度和時(shí)間效率。移動(dòng)錨節(jié)點(diǎn)的移動(dòng)軌跡不存在交叉移動(dòng)的情況，避免了移動(dòng)路徑的冗余，因此能夠較好地提升定位的時(shí)間效率。相關(guān)的仿真實(shí)驗(yàn)也驗(yàn)證了上述內(nèi)容，同時(shí)表明，改進(jìn)的定位算法利用兩個(gè)邊長(zhǎng)和最長(zhǎng)邊的長(zhǎng)度判斷并計(jì)算出位置信息，規(guī)避了三邊定位的最大誤差值，在一定程度上提高了定位精度。

[1] 崔遜學(xué),左從菊.無(wú)線傳感器網(wǎng)絡(luò)簡(jiǎn)明教程[M].北京:清華大學(xué)出版社,2009.

[2] Li Fangmin,Han Ping,Luo Ting.Adaptive region localization algorithm based on packet loss rate and RSSI in wireless sensor networks[J].Journal of Communication,2009,30(9):15-23.

[3] Liu Y,Yang Z,Wang X,et al.Location,localization,and localizability[J].Journal of Computer Science and Technology,2010,25(2):274-297.

[4] Yang Zheng, Wu Chensu,Liu Yunhao.Localization calculation:wireless network positioning[M].Beijing:Tinghua University Press,2014.

[5] Chui W Y,Chen B S,Yang C Y.Robust relative localization estimation in wireless sensor networks with inexact position problems[J].IEEE Transactions on Mobile Computing,2012,11(6):935-946.

[6] Kim E,Kim K.Distance estimation with weighted least squares for mobile beacon-based localization in wireless sensor networks[J].IEEE Signal Processing Letters,2010,17(6):559-562.

[7] Zhang B,Yu F.Low-complex energy-efficient localization algorithm for wireless sensor networks using directional antenna[J].IET Communication,2010,4(13):1617-1623.

[8] Ou C H.A localization scheme for wireless sensor networks using mobile anchors with directional antennas[J].IEEE Sensor Journal,2011,11(7):1607-1616.

[9] Huang R, Zaruba G V.Monte Carlo localization of wireless sensor networks with a single mobile beacon[J].Wireless Networks,2009,15(8):978-990.

[10] Ding Y,Wang C,Xiao L.Using mobile beacons to locate sensors in obstructed environments[J].Journal of Parallel and Distributed Computing,2010,70(6):644-656.

[11] Zhang B,Yu F,Zhang Z.Collaborative localization algorithm for wireless sensor networks using mobile anchors[C]//Proceedings of 2nd Asia-Pacific conference on computational intelligence and industrial applications.Wuhan,China:[s.n.],2009:309-312.

[12] Shi Q J,He C.Multi-power level mobile beacon assisted distributed node localization algorithm[J].Journal on Communications,2009,30(10):8-13.

[13] 姚忠孝,俞 立,董齊芬.基于移動(dòng)信標(biāo)的DV-Hop無(wú)線傳感網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22(10):1504-1509.

[14] Guo Zhongwen,Guo Ying,Hong Feng,et al.Perpendicular intersection:locating wireless sensors with mobile beacon[J].IEEE Transactions on Vehicular Technology,2010,59(7):3501-3509.

[15] 崔煥慶,王英龍,郭 強(qiáng),等.多移動(dòng)信標(biāo)輔助的分布式節(jié)點(diǎn)定位方法[J].通信學(xué)報(bào),2012,33(3):103-111.

[16] Zhong Z,Luo D,Liu S,et al.An adaptive localization approach for wireless sensor networks based on Gauss-Markov mobility model[J].Acta Automatical Sinica,2010,36(11):1557-1568.

A Mobile-beacon Based Localization Algorithm in Responsive Sensor Networks

XU Jun，WU Min，SHA Chao，NI Kai-yue，WANG Ru-chuan

(Computer and Software College of Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Compared with static anchor localization scheme,the localization algorithm based on multi-mobile anchor can improve the accuracy of the localization greatly.Due to restriction of the mobility,it can lead to the large error of location for the unknown nodes.The mobile-anchor localization proposed is on the basis of Hexagon-based model,where the central and the border anchors are applied to visit the relevant positions with corporation,and it can get the position information of the unknown nodes in shorter time.Besides，the design of the mobile planning can get rid of the redundant path and improve the accuracy and efficiency.Picking out of two with larger strength from the three messages and it can remove the result with larger error.Then from two messages,the two results of the position of the unknown node can be obtained.And according to the three messages,the only final result can be gotten.The algorithm of RSSI is improved and can get better accuracy of localization.Simulation results show that the proposed measure has the better accuracy of the localization and higher rate of efficiency.

Hexagon-based model;visiting with corporation;mobile beacon;RSSI

2016-02-18

2016-06-15 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(61572260)；江蘇省優(yōu)秀青年基金(BK20160089)；江蘇省研究生創(chuàng)新工程項(xiàng)目(SJZZ16_0147,SJZZ16_0149,SJZZ16_0150,KYLX15_0842)

徐 駿(1990-)，男，碩士研究生，研究方向?yàn)闊o(wú)線傳感網(wǎng)定位技術(shù)；吳 敏，博士，副教授，研究方向?yàn)闊o(wú)線自組織網(wǎng)絡(luò)協(xié)同信息處理技術(shù)；沙 超，博士，副教授，研究方向?yàn)闊o(wú)線傳感網(wǎng)能耗均衡技術(shù)；王汝傳，教授，研究方向?yàn)槲锫?lián)網(wǎng)信息處理技術(shù)。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.006.html

TP31

A

1673-629X(2017)06-0199-06

10.3969/j.issn.1673-629X.2017.06.042