無線傳感器網絡距離約束定位算法

張松濤 田鈞 宋樹祥

摘 要： 為克服稀疏信標結點和測距誤差問題，提出了一個距離約束定位算法。該算法先借助多跳以外的信標結點進行傳感器結點初始位置估算；然后利用直接鄰居信息進行結點位置迭代更新。為了提高定位準確性，新算法引入了一些改進措施。在初始位置估算階段，引入合理的可信度權值因素。在結點位置迭代更新階段，只選擇部分可靠鄰居結點用于鄰居結點距離檢測，并有選擇性地用上次迭代結果作為最新定位結果。仿真結果表明，與以前算法相比，新算法能降低定位誤差。

關鍵詞： 無線傳感器網絡； 定位； 距離約束； 迭代

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2015）09-08-04

Distance constraint localization algorithm in wireless sensor network

Zhang Songtao1， Tian Jun1， Song Shuxiang2

（1. Dept. of Electronic and Information Engineering， Foshan Polytechnic， Foshan， Guangdong 528137， China；

2. College of Electronic Engineering， Guangxi Normal University）

Abstract： In order to overcome the problem of sparse anchors and ranging error， a distance constrained localization algorithm is proposed. In this algorithm， the initial position of sensor nodes is estimated by using the anchors beyond the multi-hop， then the position of sensor nodes is updated by using the direct neighbor information. In order to improve the accuracy of localization， the new algorithm introduces some improvement measures. In the initial position estimation stage， the reasonable reliability weighting factor is introduced. In the node position iteration， only some selected reliable neighbor nodes are used to detect the distance to neighbor nodes， and the results of the last iteration are selectively used as the most recent results. Simulation results show that the new algorithm can reduce the localization error compared with the previous algorithms.

Key words： wireless sensor network； localization； distance constraint； iteration

0 引言

由大量傳感器結點協同合作構成的無線傳感器網絡，在工農業控制、軍事國防、生物醫療、環境監測、搶險救災等諸多領域有著廣泛的應用前景[1-2]。各結點感知數據、傳回數據，并在中心結點進行分析處理，成為各種應用的一種基本途徑。所以，沒有位置信息的測量數據會造成中心結點或中央處理器不知道測量數據發生的精確地點或大致范圍，使測量數據失去意義。而且，各結點的位置信息有助于網絡數據融合[3]、路由[4]、覆蓋[5]等算法的改善。

在一個傳感器網絡中，通常只有一小部分結點采用全球定位系統GPS技術或其他方式獲得結點自身位置信息（這部分結點我們稱為信標結點），其他絕大多數普通結點沒有自己的位置信息。估算普通結點的位置正是傳感器網絡定位技術要解決的問題。

對于一個平面網絡，某未知結點如果知道三個參考結點的位置和到相應參考結點的測量距離，就可以運行基本的三邊測量定位算法，估算出自身位置坐標。但使用通常的距離測量方法，測量結果會產生不同程度的誤差，對定位結果產生不利影響。因此，如何克服距離測量誤差的影響成為傳感器網絡結點定位技術挑戰性工作之一。定位技術的另一個難題是，由于多方面的原因，網絡中信標結點的數量較少。一個普通結點只有很小的可能性，能有三個或以上鄰居結點為信標結點，從而運行基本三邊測量定位算法來估算出自身位置。

為了改善上述稀疏信標結點和測量誤差問題，本文提出一種可靠鄰居結點距離約束定位算法（Distance Constraint Refinement with Credible Neighbors，DCRCN）。該算法以經典定位算法Hop-terrain[6]為基礎，采取有效策略控制結點位置迭代更新，以提高結點定位準確性和定位結點比例。

1 相關研究工作

文獻[7]對最新傳感器網絡定位方法，包括基于連通性定位方法、基于距離測量定位方法、基于角度測量定位方法、基于信標結點定位方法、無信標結點定位方法、概率定位方法、結點移動時的定位方法等，從問題產生動機、問題描述、解決方法及定位性能等方面，進行了比較全面的分析。

Savvides[8]等人提出的原子多邊形算法和Zhou[9]等人提出的三維歐氏距離定位算法都是利用直接鄰居信標結點運行三邊測量定位算法估算普通結點位置。獲得位置估算的普通結點轉變成為新的信標結點輔助其他普通結點進行位置估算。這些算法在網絡結點連通度（網絡中結點的平均鄰居個數）和信標結點比例較高時能夠實現較準確的結點定位。

Savarese等人提出一種由初始化和迭代更新兩階段組成、典型魯棒性定位算法Hop-terrain[6]。在初始化階段算法利用距離向量消息交換得到各結點之間的最短路徑跳數，信標結點利用自身位置及各信標結點之間的最短路徑跳數估算網絡平均單跳距離。各普通結點利用網絡平均單跳距離估算到信標結點的距離；然后進行三邊測量定位計算，估算自身初始位置。迭代更新階段普通結點利用鄰居結點的估算位置及測距信息，運行三邊測量定位算法，結合到鄰居結點和到信標結點距離約束檢測，進行位置迭代更新。

本文提出類似于Hop-terrain的DCRCN定位算法，對初始位置估算和迭代策略進行改進，較大地提高了結點定位準確性和定位結點比例。

2 DCRCN定位算法改進思路

DCRCN算法采用與Hop-terrain算法相似的兩個步驟：首先利用信標結點估算普通結點初始位置，然后利用鄰居結點迭代更新普通結點位置。迭代更新階段需要用鄰居結點的位置信息和到鄰居結點的測量距離。距離測量準確性與測距硬件和傳感器網絡環境密切相關。而位置迭代更新需要反復進行，每一次鄰居結點位置估計的準確性會對迭代性能形成直接影響。另外，測量誤差雖然與硬件密切相關，但有利的迭代策略可以改善它對結點定位準確性的影響。

根據上述思路，DCRCN定位算法相對于Hop-terrain算法在結點初始位置估算階段和結點坐標迭代更新階段分別作了相應改進。在結點初始坐標估算階段某結點運行三邊測量定位算法時，對直接鄰居信標結點采用測量距離而非跳數估算距離；對不同信標結點按到待求結點跳數大小賦以不同權值。在坐標迭代更新階段，為了降低結點定位誤差，要設法保留較好的中間結果。首先，如果某普通結點在某次迭代中無法成功運行三邊測量定位計算、或成功運行三邊測量定位計算但沒有通過距離約束檢測，我們將有選擇性地用上次估算位置作為最新估算位置；然后，只選擇部分可靠鄰居結點進行到鄰居結點距離檢測，而不采用原Hop-terrain算法中所有鄰居結點都參與到鄰居結點距離約束檢測的方法。

3 DCRCN定位算法

DCRCN算法首先利用信標結點信息進行結點初始坐標估算。這樣，對于一個連通網絡，所有普通結點都可以得到一個初始估算位置。然后，普通結點利用直接鄰居結點信息進行基于距離約束的結點位置迭代更新，用以降低結點定位誤差。下面將論述DCRCN算法兩個主要步驟。

3.1 估計普通結點初始位置

在一般傳感器網絡應用中，信標結點的比例很低，絕大多數普通結點因為沒有足夠的鄰居信標結點，所以不能直接運行三邊測量定位算法估算自身位置。

為了解決上述稀疏信標結點問題，用距離向量交換思想估算普通結點到信標結點的距離。普通結點先獲得以跳數為單位到信標結點的距離。信標結點利用到其他各信標結點的距離及跳數計算網絡每跳的平均距離，并用有控制的泛洪法把該平均距離作為一個修正值在網絡中傳播。普通結點獲得修正值即平均單跳距離，之后可計算到信標結點以米為單位的距離。

如果某信標結點為某普通結點的鄰居結點，則不用基于跳數的估計距離，而直接用兩點間的測量距離。某普通結點獲得足夠多信標結點的位置坐標和估算距離后，就可以運行帶權值的三邊測量定位算法估算自身初始坐標。由普通結點到若干信標結點的距離形成二次方程組，進一步整理成形如AX=b的線性方程組，再引入基于結點定位準確性的可信度權值參數，把線性方程組AX=b改成：

VAX=Vb ⑴

式⑴中，V為與可信度參數相關的權值向量，各元素按

⑵

取值。式⑵中，kij為普通結點i到信標結點j的最短路徑跳數，wj為信標結點j的可信度權值。后面我們將看到，所有信標結點的權值均為1。最后采用標準的最小均方差估計方法可以得到方程組的解，即普通結點的初始坐標估計[10]。

經上述基于距離向量交換得到普通結點到參考信標結點的距離估計、用基本三邊測量定位方法估算普通結點初始坐標后，就可著手開始普通結點位置迭代更新了。

3.2 迭代更新普通結點位置

結點坐標迭代更新，以普通結點初始位置為基礎，采用有效迭代策略，反復更新結點坐標，提高結點定位準確性。

一次迭代基本過程如下：各普通結點用單跳路由方式獲得鄰居結點最新的估算坐標及相互之間的距離信息。如果用于定位的參考鄰居結點數量足夠，某普通結點運行帶權值的三邊測量定位算法，以獲得新位置估算。對于獲得新位置估算的結點，利用鄰居結點和信標結點進行兩項距離約束檢測，有選擇性地用上次迭代結果作為最新坐標，以降低定位誤差。

到信標結點距離約束檢測與普通結點到信標結點的兩項距離大小比較：距離1，按普通結點的估計坐標計算到信標結點的距離；距離2，是該普通結點到該信標結點的最短路徑跳數與結點通信半徑的乘積。如果某普通結點到所有可連通信標結點均滿足距離1小于或等于距離2，則表明到信標結點距離檢測成功。

接下來，到鄰居結點距離約束檢測比較某普通結點到各鄰居結點測量距離與按估算位置計算距離的平均差值，以判斷結點定位的優劣。如果鄰居結點位置估算準確度不高，上述平均差值并不能很好地表示結點定位準確性。所以，我們只選取部分可靠鄰居結點用于到鄰居結點距離約束檢測。如果可用的鄰居結點數量足夠，當上述平均差值小于某一閾值（比如傳感器結點通信半徑R）時，我們認為到鄰居結點距離約束檢測成功。

如果某結點利用鄰居結點成功完成三邊測量定位計算并兩項距離約束檢測均成功，則接受本次位置更新。對于兩項距離約束檢測失敗的情況，如果該結點之前已成功定位，就用上次迭代結果更新該結點坐標；否則，用初始位置估算的結果更新該結點位置。

為了控制誤差傳播，參照結點初始坐標估算階段的方法，在三邊測量定位算法中，對各參考鄰居結點引入基于定位準確性的可信度權值向量W，表征各鄰居參考結點定位準確性高低，各元素取值在0到1之間。結點坐標迭代更新開始時，信標結點的可信度權值直接設置為1；普通結點的權值則設定為接近于0的某個值，如0.1。當某普通結點兩項距離約束檢測均成功時，用其鄰居結點可信度權值的均值來更新該結點定位可信度權值，以此來更新上述權值向量W。

由于受到鄰居結點和信標結點的距離約束，隨著結點位置不斷更新，結點估算位置不斷逼近真實位置。如果少數結點一直無法成功定位，給定一個迭代停止條件使算法有效終止。

4 算法性能評估

為了驗證算法有效性，本文搭建實驗平臺進行了廣泛的實驗仿真。我們把DCRCN算法定位性能的相關數據與Hop-terrain算法[6]進行了對比分析。

4.1 仿真環境設備

我們設計的實驗場景為一個正方形區域，邊長100m，400個傳感器結點隨機分布其中，一部分結點為信標結點。測量誤差按正態分布考慮，標準差取實際距離的5%。改變結點無線通信半徑和信標結點比例進行大量實驗。按結點無線通信半徑對定位誤差歸一化。

4.2 實驗結果分析

圖1是經初始位置估算后的定位誤差隨連通度變化情況。普通結點定位準確性隨著網絡連通度和信標結點比例的增加而提高。當信標結點比例為5%和10%時，在不同網絡連通度情況下DCRCN算法結點定位誤差比Hop-terrain算法小6-10%和2-6%。結點定位誤差的改善主要來自兩個方面。首先，對直接鄰居信標結點不用跳數估計距離而采用測量距離，提高了距離測量準確性；其次，在三邊測量定位計算中增加可信度權值因素，提高了運算的準確性。

圖1 初始位置估算后定位誤差隨連通度變化情況

圖2是經位置迭代更新后定位誤差隨連通度變化情況。經比較我們發現，在連通度為10以上時，DCRCN算法結點定位誤差比Hop-terrain算法均有不同程度的下降。但連通度在10以下時，DCRCN算法定位誤差比Hop-terrain算法略高。這主要是因為圖2描述的是網絡中成功定位結點的定位誤差，但在連通度比較低時，DCRCN算法的定位結點比例比Hop-terrain算法高很多（圖3的主要結論）。

圖2 坐標迭代更新后定位誤差隨連通度變化情況

圖3是定位結點比例隨連通度變化的情況。隨著網絡連通度的增加，定位結點比例不斷增加。同時，DCRCN算法的定位結點比例比Hop-terrain算法有明顯提高，尤其在網絡連通度比較低時，DCRCN算法定位結點比例比Hop-terrain算法高10-20%左右。

圖3 位置迭代更新后定位結點比例隨連通度變化情況

圖4是結點定位累積誤差分布圖。當信標結點比例為5%時，DCRCN算法定位誤差小于50%的結點占所有普通結點比例為61.96%（Hop-terrain算法為53.91%），比Hop-terrain算法高8個百分點。總體上，當信標結點比例分別為5%和10%時，DCRCN算法定位誤差小于10%-100%的結點占所有普通結點比例比Hop-terrain算法相應要高2-5百分點。所以，在相同實驗條件下，DCRCN算法具有較小定位誤差的結點比例比Hop-terrain算法高。DCRCN算法定位準確性的提高，除了前面提到的在結點初始位置估算階段的改善外，同樣有結點位置迭代更新階段的改善，這包括：在坐標迭代更新時有選擇性地用上次迭代位置作為本次迭代位置；只選擇部分可靠鄰居結點到鄰居結點距離檢測。通過以上措施，降低了定位誤差。

圖4 累積誤差分布（連通度7.5）

我們改變網絡拓撲，在格形網絡（將平面網絡分割成等大小均勻分布的格子，各結點在每個格子內隨機分布）中也做了大量實驗，得出了與上述隨機布撒的均勻分布網絡比較類似的結果：DCRCN算法定位結點比例和結點定位準確性比Hop-terrain算法都有不錯的提高。

5 結束語

本文提出一種可靠鄰居結點距離約束定位算法。在估計結點初始位置階段，對直接鄰居信標結點采用測量距離取代跳數估算距離，同時在三邊測量定位計算時增加合理的可信度權值因素。在結點位置迭代更新階段，只選擇部分可靠鄰居結點進行到鄰居結點距離約束檢測，并根據可靠鄰居距離約束關系有選擇性地用上次迭代位置作為最新估算位置。以上幾個方面的改善，有效地提高了定位結點比例，降低了結點定位誤差。

參考文獻：

[1] 孫利民，李建中，陳渝等.無線傳感器網絡[M].清華大學出版社，2005.

[2] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al.

Wireless sensor networks： a survey[J]. Computer Networks，2002.38（4）：393-422

[3] Wang Cheng，TANG Shao-Jie and LI Xiang-Yang. SelectCast：

scalable data aggregation scheme in wireless sensor networks[C] // Proceedings of IEEE INFOCOM， Shanghai， China，2011.4：10-15

[4] YU Xiao-Kang， YIN Xiao-Tian， HAN Wei， et al. Scalable routing

in 3D high genus sensor networks using graph embedding[C] // Proceedings of IEEE INFOCOM， Orlando， FL， USA，2012.3：25-30

[5] LIU Chang-Lei and CAO Guo-Hong. Distributed critical location

coverage in wireless sensor networks with lifetime constraint[C] // Proceedings of IEEE INFOCOM， Orlando， FL， USA，2012.3：25-30

[6] SAVARESE C， RABAEY J， and LANGENDOEN K. Robust

positioning algorithms for distributed ad-hoc wireless sensor networks[C] // Proceedings of the USENIX Technical Annual Conference， Monterey， CA， USA，2002.6：10-15

[7] WANG Jing， GHOSH R K， and DAS S K. A survey on sensor

localization[J]. Journal of Control Theory and Applications，2010.8（1）：2-11

[8] SAVVIDES A， HAN C C， and STRIVASTAVA M B. Dynamic

fine-grained localization in ad-hoc networks of sensors[C] // Proceedings of ACM MobiCom， Rome， Italy，2001.7：16-21

[9] ZHOU Zhong， CUI Jun-Hong， and ZHOU Sheng-Li. Localization

for large-scale underwater sensor networks[C] // Proceedings of IFIP Networking， Atlanta， GA， USA，2007.5：14-18

[10] GOLUB G. Matrix computations[M]. 3rd edition， The Johns

Hopkins University Press，1996.