基于移動信標的響應式傳感網定位方法

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

(南京郵電大學 計算機學院、軟件學院,江蘇 南京 210003)

基于移動信標的響應式傳感網定位方法

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

(南京郵電大學 計算機學院、軟件學院,江蘇 南京 210003)

相對于靜態錨節點定位算法而言，基于移動錨節點的定位機制能較好地提升定位的準確性。由于受到移動性的限制，某些靜態錨節點定位時會出現誤差過大的情況。為此，提出了基于蜂窩模型的移動定位算法。該算法應用中心錨節點和邊緣錨節點協作遍歷模型的中心和邊緣位置，可快速定位覆蓋區域的未知節點，且能去除移動規劃設計中的冗余路徑，避免了同一路徑的冗余重復訪問，有助于保證錨節點移動的高效性和準確性。該算法通常從捕獲的三個錨節點信息篩選出RSSI信號強度較大的兩個，以避免引入誤差過大的距離值，根據信號強度的衰減模型求解可以得到兩個位置信息，并由第三個距離信息作為判斷條件，唯一確定未知節點的坐標信息。仿真結果表明，所提出的定位算法定位精度較好且定位的時間效率較高。

蜂窩模型；協作遍歷；移動信標；RSSI

0 引 言

無線傳感網技術在現實生活中應用廣泛。通過在指定區域部署低功耗的傳感器節點，可實現目標追蹤、資源勘探、環境監測等應用。這些應用都要基于位置信息的捕獲，其中定位技術起到了關鍵作用[1-3]。

節點定位的過程就是通過相關的技術手段獲取網絡結構中未知節點的絕對或相對位置信息。根據定位過程中是否需要測距，無線傳感器節點定位可以采用基于測距的定位技術和無需測距的定位技術。其中基于測距的定位方法需要額外的硬件支持，定位精度較高但容易受到環境因素的影響；而無需測距技術雖然定位精度較低，但是成本低且不易受外界環境的影響。

根據錨節點是否具有移動性，定位算法還可以分為靜態定位算法和動態定位算法。通常采用靜態定位時需要錨節點密度達到一定的程度來滿足節點之間的連通性[4]。而動態定位算法可以使用較少的錨節點，而且部署更加靈活多變，近年來在定位領域應用廣泛[5-8]。

移動的信標節點沿著事先設計好的移動路徑遍歷整個網絡區域，并在移動到相應的位置廣播消息包。未知節點捕獲來自錨節點的消息包后保存并進行分析，可以計算出未知節點的估計位置坐標[9-11]。

目前的移動定位算法移動的隨機性太大，移動的路徑規劃存在不合理的情況，效率較低。且在定位移動的過程中節點的配合協作性不高，從而導致節點的定位誤差較大。

為此，提出了改進的RSSI定位算法以提升定位精度。在此基礎上，設計了基于蜂窩模型的移動規劃路徑，定義了中心錨節點和邊緣錨節點分別遍歷蜂窩區域的中心位置和六個邊緣位置，并在相應的區域廣播消息包，以保證定位區域的位置節點至少捕獲到來自三個錨節點的消息包。仿真驗證結果表明，所提出的移動定位算法在定位精度和定位的時間效率上均有明顯改善。

1 相關工作

使用移動定位算法來求解未知節點坐標時，移動錨節點會沿著設計好的移動軌跡移動，并在相應的位置停留一小段時間來廣播自身的消息包，而且需要保證待定位的未知節點至少需要捕獲到來自三個錨節點的消息才能確定唯一的位置信息。

移動錨節點定位算法相對于固定錨節點定位算法而言，不會因為錨節點的位置分布不均勻而導致某些節點無法定位，在很大程度上減少了錨節點的使用數量，而且能夠設計好的移動路徑算法來保證每個未知節點都能至少捕獲到來自三個錨節點的消息包。從以上分析可知，相對于固定的錨節點定位算法，移動錨節點定位算法在成本和效率上都有明顯提升。

在文獻[12]中，基于高斯馬爾可夫模型設計移動的規劃路徑，分別設定了移動錨節點的速度和方向，并對速度和方向分別引入了高斯隨機變量。節點的定位采用加權質心算法，對距離值求解倒數作為其在總體樣本中的權值來求解具體的距離值。定位過程的權值求解過于簡單，并不能很好地規避求解的距離誤差值。此外，高斯馬爾可夫移動模型隨機性太大，導致錨節點遍歷路徑存在很多的重復路徑，移動的效率較低。

文獻[13]采用MB-DV-Hop定位算法來實現對節點的定位操作，移動錨節點通過螺旋式移動軌跡來遍歷網絡區域。未知節點實時捕獲來自錨節點的數據包，當數據包個數達到三個時，就可以確定自身的坐標，進而轉化為靜態錨節點。再通過DV-Hop定位算法計算出移動錨節點和靜態錨節點之間的平均跳距值，實現對尚未能定位節點的定位操作。但是DV-Hop定位算法節點的定位精度不高，且移動錨節點的移動路徑長度過大，效率不高。

文獻[14]使用三重定位覆蓋模型，并在錨節點移動過程中會一直廣播包含自身位置信息的消息包。同時處在該模型區域的未知節點會實時地捕獲消息包，并通過比較來保存來自錨節點信號強度最大的消息包，將兩個最大的RSSI值所處的點坐標值作為未知節點在邊上的投影點，取通過這兩個投影點的垂線的交點作為未知節點的坐標值。單個錨節點的移動路徑也是基于三重覆蓋模型，從而保證每個未知節點都能至少捕獲到來自三個錨節點的消息包。錨節點移動過程中一直廣播消息包會造成能量的浪費，同時移動路徑算法的效率不是很高。

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

這里基于蜂窩模型，并設定兩個錨節點分別遍歷蜂窩模型的中心位置和邊緣頂點位置，保證在定位區域的未知節點至少能夠捕獲到來自三個錨節點的消息包，并記錄到達未知節點的信號強度值并根據信號衰減模型計算出對應的距離信息，從而保證未知節點能實現定位操作。此外，還對RSSI定位算法進行了改進，在三邊定位過程中只捕獲最大的兩個信號強度，并利用最小的信號強度求解估計距離來最終判斷未知節點的坐標。

2 RSSI定位算法優化

對于移動定位算法而言，是由多個定位算法沿著一個移動路徑組成，需要確定相應的定位模型和定位算法。

2.1 定位模型

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

(1)

(2)

(3)

將上面的公式整理可得：

(4)

上式簡寫成：

(5)

(6)

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

由此可得，對于某個未知節點進行定位操作，則至少需要捕獲到三個錨節點的信息。

如圖1(左)所示，錨節點A的通信半徑所覆蓋的圓形區域，至少需六個額外的錨節點才能保證對該圓形覆蓋區域的所有未知節點實現定位操作。

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

將圖1的通信覆蓋模型簡化為蜂窩模型，每個小的三角形構成的區域都至少能捕獲到來自三個錨節點的信息。

分別定義兩個移動的錨節點為中心錨節點和邊緣錨節點。中心錨節點遍歷蜂窩模型的中心位置，而邊緣錨節點分別遍歷蜂窩模型的六個頂點位置，且兩個錨節點分別在對應的位置上廣播包含自身坐標信息的消息包。依靠兩個錨節點的分工協作能夠保證該區域的未知節點至少能捕獲到三個錨節點的信息包，從而實現定位操作。

2.2 消除最大誤差的改進定位方案

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

(7)

其中,PLd0表示初始信號強度;α表示射頻信號的衰減指數;xσ表示方差為σ的對數誤差。

對圖1中蜂窩模型的三角形定位區域進行分析，假設三個錨節點的坐標值為(xA,yA)、(xB,yB)和(xC,yC)，以及未知節點D的坐標為(xD,yD)。三個錨節點A、B和C分別向未知節點D發送數據包。篩選出RSSI信號強度最大的兩個錨節點信息表項,并根據信號強度的衰減模型分別計算出這兩個距離信息。去除掉信號強度最弱的信息值，是為了避免引入誤差過大的距離值，從而能夠提高定位精度。

圖2 節點定位模型(左)及其所捕獲的信號強度近似相等的情形(右)

當捕獲到來自兩個錨節點的信號強度近似相等且小于來自另外一個錨節點的信號強度時，將采用如下判定方法：

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

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

(8)

且錨節點A和未知節點的距離為d，則有：

(9)

根據式(8)和式(9)，可以唯一確定未知節點D的坐標值。

當來自三個錨節點的信號強度都近似相等，則可以確定未知節點D處在三個錨節點組成的三角形區域的中心附近。

該定位算法與傳統的RSSI三邊定位算法相比，去除誤差值最大的信號強度值。根據RSSI信號衰減模型可知，根據信號強度求得的距離值越大，該距離值與實際值的誤差也越大。因此排除掉信號強度最弱的信息值，可以相應地減小定位的誤差值。

3 信標節點移動路徑設計

在完成了具體的定位算法后，需要對整體的信標移動路徑進行設計。信標移動路徑設計的好壞在很大程度上決定了能夠訪問的未知節點的總數、定位過程的總時間和精度等因素。

假設帶定位節點部署在一個W×L的矩形網絡區域內，且移動錨節點通信半徑為R。

文獻[15]提出了基于三重覆蓋優化的STC移動路徑規劃算法，主要使用三個錨節點A、B和C交替移動來實現移動定位。STC具體移動路徑如圖3所示。從最左端的三角形A1B1C1開始，錨節點A從開始的A1位置移動到相對于線段B1C1的對稱位置A2；接著錨節點B從位置B1移動到相對于線段C1A2的對稱位置B2；然后錨節點C從位置C1移動到相對于線段A2B2的對稱位置C2，后續的節點移動以此類推。

圖3 STC的信標移動路徑

(10)

這里設計的移動路徑是基于蜂窩模型的移動軌跡，主要由一個中心錨節點和一個邊緣錨節點配合來完成軌跡移動。中心錨節點移動到蜂窩模型的中心時，會通知邊緣錨節點訪問蜂窩模型相應的邊緣節點位置。如圖4所示，粗實線表示中心錨節點移動的軌跡，粗虛線表示邊緣錨節點移動的軌跡。

圖4 設計的錨節點移動模型

(11)

由此分析得，該算法的移動路徑長度小于STC的移動路徑長度，且只使用了兩個錨節點，而STC中使用了三個錨節點。就路徑長度和錨節點使用個數上分析可知，該路徑算法優于STC路徑算法。

下面分析訪問一個未知節點所需的平均時間。當三個錨節點組成三重覆蓋模型時，該區域內的節點就能實現定位。假設單位時間內移動的步長為R，網絡模型的長和寬分別設為L和W，為了便于分析，假設節點均勻分布，每個三角形區域分布的節點數均為n。

對文獻[1]中的錨節點移動軌跡分析得：

(12)

對錨節點移動軌跡進行分析得：

(13)

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

(14)

當L?R時可以得到上面的結果大于零。由此分析，對同一個網絡拓撲結構，該路徑移動算法定位一個未知節點平均所需的時間較少。

4 仿真實驗

將所提出的定位算法命名為MLD，并與單個錨節點的路徑規劃TRI[14]，以及文獻[15]提出的STC路徑規劃作對比實驗。好的移動規劃應該能夠盡可能短地設計移動路徑，并且能較好地提高節點的定位精度，此外還要在盡可能短的時間內定位更多的節點。

實驗從三個方面來分析定位算法的性能：

(1)相等時間內能夠定位的節點比例；

(2)定位相同節點數錨節點移動路徑總長；

(3)節點定位誤差率。

采用Java對上述移動定位算法進行仿真實驗。設定網絡未知節點的部署區域為(800 m×516 m)的矩形區域，內有200個未知節點隨機分布其中。設定通信半徑為5 m、10 m、15 m和20 m。使用上述三種定位算法，并設定移動步長為R，且節點移動到三重覆蓋模型的相應位置時廣播數據包。

在相同的定位時間內，移動定位算法定位未知節點的比例能夠較好地反映定位算法的時間效率。定位節點的比例越高，說明移動定位算法移動的時間效率越高。三種移動定位算法的定位節點比例見圖5。

圖5 不同時間下的節點定位比例

隨著運行時間和通信半徑R的增加，三種移動定位算法的可定位節點數隨之增加。通信半徑的增加保證了在相同的移動步長下，錨節點廣播的消息包能夠被更多的未知節點捕獲到，從而能夠使更多的未知節點實現定位操作。

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

節點在定位的過程由于處在錨節點移動覆蓋區域的盲區而導致節點的位置信息捕獲不到或誤差較大而導致節點無法定位。

遍歷完整個網絡后，可定位節點分析如表1所示。

表1 不同算法下的可定位節點分布情況

由表1可知，隨著通信半徑的增加，所能覆蓋的通信區域的面積也隨之增大，從而能減小定位盲區的面積。TRI由于是單個節點移動來定位,且定位過程中根據信號強度的最大值的幾何運算求解坐標值，定位的誤差較大，從而導致節點定位的失效。STC和MLD的定位實現過程都是基于三重覆蓋定位模型，定位的原理基本相同，在相同通信半徑的情況下遍歷整個網絡區域后的整體定位的效率基本相同。

移動相同的路徑所能定位的未知節點的比例也能夠反映移動定位算法的效率，其實驗結果如圖6所示。如果錨節點移動的路徑長度相同，而定位的節點數越多，則表明定位效率越好；反之說明定位效率較差。

圖6 不同移動路徑長度節點定位比例圖

TRI算法實現的是單個錨節點的遍歷而不是多個節點協作式遍歷，從而導致在移動相同路徑長度的情況下節點的定位效率較差。STC算法在移動過程需要三個移動的錨節點來實現輔助定位，錨節點相對移動的路徑長度較大，而MLD移動過程中只需要兩個錨節點，且基本上沿著直線移動前進，因此遍歷相同面積區域移動的路徑長度也就相對較短，從而可以定位更多的節點。

下面討論在不同的通信半徑下，訪問整個網絡區域錨節點所移動的路徑長度，如圖7所示。訪問的未知節點覆蓋的網絡區域的面積是恒定的，最終移動路徑的長短能夠較好地反映節點遍歷網絡區域的效率。

圖7 不同通信半徑下移動路徑總長度對比圖

隨著通信半徑的增大，能夠保證在相同的移動路徑下遍歷更多的節點區域面積，因此節點的移動路徑長度也會隨之減少。TRI使用單個錨節點來遍歷該區域，不能實現分工協作，需要自身來完成更多的遍歷工作，也就導致移動的路徑長度偏大。STC移動過程中是使用三個錨節點來實現遍歷，移動路徑存在較多的交叉情況而不是平行進行的，導致效率降低。而MLD在移動過程中，中心錨節點和邊緣錨節點是平行移動的，不存在交叉，顯著提高了遍歷的效率。

5 結束語

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

[1] 崔遜學,左從菊.無線傳感器網絡簡明教程[M].北京:清華大學出版社,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] 姚忠孝,俞 立,董齊芬.基于移動信標的DV-Hop無線傳感網絡定位算法[J].傳感技術學報,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] 崔煥慶,王英龍,郭 強,等.多移動信標輔助的分布式節點定位方法[J].通信學報,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 網絡出版時間：2017-04-28

國家自然科學基金資助項目(61572260)；江蘇省優秀青年基金(BK20160089)；江蘇省研究生創新工程項目(SJZZ16_0147,SJZZ16_0149,SJZZ16_0150,KYLX15_0842)

徐 駿(1990-)，男，碩士研究生，研究方向為無線傳感網定位技術；吳 敏，博士，副教授，研究方向為無線自組織網絡協同信息處理技術；沙 超，博士，副教授，研究方向為無線傳感網能耗均衡技術；王汝傳，教授，研究方向為物聯網信息處理技術。

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