無線傳感器網絡定位算法綜述*

黃 毅，胡愛群

（東南大學信息科學與工程學院 南京210096）

1 引言

位置信息對于無線傳感器而言是非常重要的，一個沒有傳感器節點位置信息的WSN（無線傳感器網絡）是沒有應用意義的，因為幾乎所有的WSN應用場合都需要知道節點位置信息，比如：動物種群的跟蹤研究，大樓火災的預警，倉庫中貨物的管理，交通監控系統等。一個直接的方法是在節點上安裝GPS，但是由于WSN是由成百上千甚至更多的傳感器節點組成的，成本太高，而且它需要長距離通信，能量花費也很高，體積很大；也不能運用在室內，所以這種方法不適合用于WSN的定位。

多年來，很多國內外學者和研究機構針對WSN的特點——能量有限、價格低廉、自組織性、無線通信、多跳中繼、分布式處理、容錯性等，展開了深入的研究并提出了很多的定位算法。本文對無線傳感器網絡節點的坐標計算方法和國內外開展的定位算法研究工作進行了介紹和歸納，可供讀者在WSN的深入研究與應用中參考。本文把定位算法劃分成兩個類別：需要/不需要測距，而每種算法又兼有以下一種或幾種特點：需要/不需要錨節點（已知坐標的節點）、集中式/分布式、固定/移動等，這些在具體算法中會特別說明。

由于固定WSN的定位算法能擴展到移動的WSN中，所以這里主要以固定WSN的定位算法為主要內容，然后再介紹移動情況下的定位算法。

2 定位算法

首先，介紹一下常用的坐標計算方法。

（1）三邊測量術

三邊測量術是根據3個已知坐標的節點到未知節點的距離來確定節點坐標。已知A、B、C三個節點的坐標分別為(xa,ya)、(xb,yb)和(xc,yc)，它們到未知節點 D(x,y)的距離分別為 da、db和 dc，如圖 1（a）所示，則通過計算可以得到以下三個式子：

通過高斯消元法可以得到以下兩個式子：

寫成矩陣形式AX=b：

那么X=A-1b，注意的是A要可逆的充要條件是A、B、C三點不共線。

（2）三角測量術

三角測量術常用到基于AOA方法的測距中，它根據三個已知坐標的節點到未知節點的相對角度來確定節點坐標。已知A、B和C三個節點的坐標分別為(xa,ya)、(xb,yb)和(xc,yc)，假設節點 D 的坐標為(x,y)，如圖 1（b）所示。對于節點A、C和D，如果弧段AC在△ABC內，那么能夠惟一確定一個圓，并存在下列公式：

上式中，d1為圓半徑，O1為圓心，α為圓心角∠AO1C。

由以上三式能夠確定圓心O1點的坐標和半徑。同理可對A、B、D和B、C、D分別確定相應的圓心和半徑，最后利用三邊測量術確定D的坐標。

（3）多邊測量術

多邊測量術（多角可以化為多邊）是根據n個已知坐標的節點到未知節點的距離來確定節點坐標的。已知n個節點的坐標分別為(x1,y1)、(x2,y2)，…，(xn,yn)，它們到未知節點D的距離分別為 d1，d2，…，dn，假設節點 D的坐標為(x,y)，可以列出n個等式，形式如三邊測量術中描述，通過計算可以得AX=b。使用標準最小均方差估計方法可以得到節點D的坐標為：

這種方法充分利用了節點所收集到的定位信息，所以在很多定位算法中都有應用。如果考慮多徑和噪聲的影響，一種更為符合實際情況的變形如下[1]：

求使得下式達到最小的解即為所求坐標。

αi是第i個信號的權值，與實際信道有關。

2.1 需要測距

如果要采用以上三種坐標的計算方法，那么必須知道一個未知節點到至少三個錨節點的距離（角度信息也可以化為距離信息）。常用的 4種測距方法為：RSS（received signal strength）、TOA（time of arrival）、TDOA（time difference

通常情況下無線電波或聲波信號在介質中傳輸時，信號功率是隨傳播距離的變大而衰減的，這是RSS測距的理論基礎。針對無線電波信號傳播的信道，一般采用的模型如下式所示：

其中，d是離開信號發射源的距離，P0是在距離信號發射源d0點（記為N點）的信號接收功率，β是路徑損耗系數，根據環境的不同，通常為2～6。在參考點N處的功率是通過預測已知的，這樣通過接收信號的強度即可判斷距離d。

（2）TOA

TOA也可以叫做TOF（time of flight）。速度一定的情況下，檢測信號從發送到接收到的時間即和距離成正比，這種方法需要時鐘的同步。

（3）TDOA

TDOA可以分成兩種情況。①兩種速度不同且相差很大的信號，如無線電信號和超聲波信號，由于無線電波速度很快，一般情況下可以看成即時到達，而聲波傳輸相對就慢很多，在節點上同時安裝以上兩種信號的接收裝置，檢測到兩信號到達的時差，就可以計算出距離。這種方法可以避免同步，但由于要多安裝一種信號的接收裝置，成本和通信開銷相對較大。②同一種信號到達每個錨節點的時差，這種方法需要每個錨節點的時鐘同步。

（4）AOA

這種方法需要角度信息，而角度信息主要依靠在節點上安裝天線陣列來獲得，再通過三角測量術算出待定位節點坐標。AOA方法需要天線陣列，成本和能耗是兩個很大的問題，對于WSN來說AOA的實用性也較差。

表1[2]是各種現有的定位系統的相關信息，包括采用的技術和能達到的精度。

從表1中可以看出，大部分的定位技術不能直接應用到WSN中去，但是關鍵的測距技術是可以借鑒的。

2.2 不需要測距

在這類算法中假設節點只能和它鄰近的節點進行通信，也就是說只能和在其有效的通信距離內的節點進行通信，借助網絡信息可以從兩個較遠的節點通過多跳（multihop）的方式傳送。通過對跳數信息的處理可以估計出兩個節點間的距離，再通過相應的算法得到節點的位置。

（1）DV-hop

基于通信跳數的DV-hop算法是由NiCuleScu提出來的[3]。它的提出有兩個假設：①在一個大型網絡中，一個待定位節點可能無法與足夠多的錨節點直接通信；②在利用空中拋灑的方式對未知區域進行監控時，只可能少數的錨節點有預知的坐標信息，如安裝了GPS的錨節點，而其他節點通過中繼的方式和錨節點通信。它的基本原理是用跳段距離來代替節點間的實際距離。

表1 現有定位系統的各種相關信息

上式中，ci是錨節點i的跳段距離，分子部分是錨節點i到其他錨節點的歐式距離之和，分母部分是錨節點i到其他錨節點的跳數之和。待定位節點到錨節點i之間的距離估計通過下式得出：

cs表示待定位節點采用的跳段距離，hsi是待定位節點s和錨節點i之間的最小跳數。算出至少三個距離（2D），利用前面的極大似然估計，就可以估計出節點坐標。

DV-hop算法的優點很多，屬于分布式算法，算法簡單，通信開銷少，計算量也少，利用跳數信息代替精確測距，硬件設計也簡單，成本也低廉；不足是對網絡節點的密度依賴性較大——密度越大，定位精度越高，所以它不適用于非凸區域，當有障礙物時，跳數信息不能正確反映實際距離。參考文獻[4]結合RSSI來減小誤差，參考文獻[5]使用節點到鄰節點的測距來提高多跳距離的精度，這些都需要額外的硬件開銷。參考文獻[6]通過待定位節點和錨節點間距離限制來改善定位精度。

（2）AFL

NISSanka[7]等人提出的 A FL（anchor-free localization）算法是一種無需錨節點的定位方法，它分為兩步：首先，通過多跳確定一個相對坐標系，得到每個節點在這個坐標系中的位置坐標，然后，通過質量—彈簧（Mass-Spring）模型進行迭代優化。具體步驟如下：第一步，初始隨機選擇一個節點n0，然后選取一個距離其最大的點n1；再選取一個距離n1最大的點 n2；接著選 n3，使得|h13-h23|最小（hij表示節點i、j之間的最小跳數），如果有多個點，則選h13+h23最大的點；類似的選取n4，使得|h14-h24|最小，如有多個，則選h34最大的點；最后選取n5點，滿足|h15-h25|最小，如有多個點，則選取|h35-h45|最小的節點。這樣，選取的5個點能夠組成一個臨時的坐標系：以n5為原點，其余4個點為4個方向上的端點。那么，網絡中的每個點就有一個對應的坐標，如用極坐標（ρi,θi)，ρi=rhi,5，θi=tan，這里r為通信半徑。這樣得到的是每個節點的粗略坐標。第二步，再用質量—彈簧模型進行迭代優化，把點與點之間的實際測量距離看成是彈簧的平衡位置，那么根據之前的估計距離與實際距離之差，可以得到彈簧是被縮小了，或是被拉伸了，這樣整個網絡就存在能量，如圖2所示，我們的目標就是使得這個能量最小，那么調整后的節點坐標即為優化后的坐標。這個算法的好處是：無需錨節點和分布式。但在質量－彈簧優化階段，需要實測距離，這就限制了此方法的應用。還有一個問題是迭代收斂的問題，很可能網絡收斂到一個局部最優點，而不是全局最優，對此目前沒有很好的解決方法。圖2中O為系統無能量時的節點位置，O’為系統存在能量時的節點位置。

（3）MDS

MDS（multidimensional scaling）只是流形學習（manifold learning）方法其中的一種，它和 P CA（principal component analysis）、ISOMAP （isometric feature mapping）、LLE（locally linear embedding）等構成常用的流形學習方法[8]。在參考文獻[9]中，作者提到了流形學習能夠用來處理網絡定位問題。Y.Shang和 W .Ruml[10，11]利用 M DS 來 解決 W SN 中 的節點定位問題。這種方法可以不需要測距（也可以需要），利用在有效通信距離內的兩兩節點之間的相似度來進行定位，比如：連通度或歐式距離，我們泛稱它們為距離。設Xi=（xi1,xi2,…,xim）是m維空間上的一個點表示i、j兩點的距離，在一個有 n 個節點的 W SN中，有 n ×n個距離，可以組成一個平方距離矩陣A，由A可計算B=-HAH/2、XTX，其中 H =I-11T/N，1=（1，1，…，1）T，由于 B 是對稱且半正定的，所以存在奇異值分解B=UΛUT=XTX，則有X=Λ1/2UT，其中 Λ =diag（λ1，…，λr），r=rank（B），λ1≥λ2≥…≥λr為B的正特征值，U的列向量由與λ1≥λ2≥…≥λm相應的標準正交向量組成。對于WSN中2D和3D的情況，只要r取2或3即可。這只是得到了n個節點的相對位置坐標，如果有3個（3D是4個）或更多個錨節點坐標，通過坐標變換，可以得到所有節點的絕對坐標。這個算法的優勢是可以不需要錨節點，而且在錨節點較少的規則網絡中，也可以達到較好的效果，不足是算法較復雜，僅奇異值分解這一關鍵步驟就需要O（n3）的復雜度。之后也有人提出基于MDS的改進定位算法，如參考文獻[12]把整個網絡劃分成多個局部，對每個局部進行定位，再融合到全局中去，實現了分布式的計算。參考文獻[13]利用最短距離作為測地線距離代替歐式距離來實現定位，提高了精度，但是鄰近參數K的選擇較復雜。

（4）基于區域的定位算法

此類算法是通過劃分局部的節點區域來實現定位，也不需要測距，主要有質心Centroid算法、APIT算法、基于Voronoi圖算法[14]等。

質心Centroid算法[15]：把節點周圍多個（2D至少3個）錨節點組成一個多邊形，它的質心估計成節點的位置，如圖3（a）所示，因此，多邊形的面積越小，估計誤差會越小，此算法要求錨節點的密度很大且均勻分布，一般情況下，WSN達不到這種要求。但是，這種算法非常簡單，很容易在節點上實現，適用于定位精度不高的場合，同時，它也是分布式的算法。參考文獻[16]提出了基于權重的質心算法即加權質心算法（W-Centroid），加權質心算法引入接收信號強度來代替質心算法中的連通性，對于接收信號強度較大的錨節點就具有較大的權值。

圖3 基于區域的定位算法

APIT算法[17]：實際上它是質心算法的改進，它選取有效通信距離內的所有錨節點中的三個（2D）組成一個三角形，用檢測信號能量的方法判斷節點是否在三角形中，這樣，依次判斷每三個錨節點組成的三角形，最后，它們的交集即是節點所在的區域，如圖3（b）所示。相比基本的質心算法，它有著更小的有效區域，所以也能夠達到更高的定位精度。由于是質心算法的改進，所以質心算法的缺點它也存在。

此外，還有類似的算法：SBL（sequenee-based loealization）[18]、SDP （semi-definite programming）[19]、 基 于Voronoi圖算法等，都是基于區域的思想。

3 移動節點定位

移動無線傳感器網絡（mobile wireless sensor network，MSN）的定位問題越來越受到人們的關注，由于節點的移動，定位的精度也會隨著移動速度的增大而降低，同時，又能獲得更多的位置信息來定位。在某些方面，移動機器人（mobile robot，MR）和 MSN有著相似之處，因此很多在MR中的定位算法可以移植到MSN中去，但是，MSN又有著自身的特點——計算和通信能力較弱，復雜的算法不可能運用到MSN中去。一種簡單有效的MSN定位算法MCL（Monte Carlo localization）[20]被廣泛研究。

Monte Carlo方法是馮·諾依曼在“曼哈頓計劃”中命名的一種計算機隨機模擬方法。L.Hu和 D.Evans[21]提出的MCL算法，是運用在移動網絡中的節點定位算法，它的關鍵思想是用一組隨機的帶權值的采樣點逼近節點可能的后驗分布，節點的位置由采樣點和權值確定。MCL把時間分成離散的單元，在每個單元中估計節點的位置，計算過程由兩部分組成：預測和過濾。在預測階段，依據節點之前的位置lt-1和最大移動速度vmax（一個時間單元內的最大移動位移），將t時刻的節點的可能位置限制在一個以lt-1為圓心、半徑為vmax的圓內，在這個圓內隨機選擇一個位置作為節點位置采樣。然后進入過濾階段，節點觀察它所有的鄰錨節點并和它們進行信息交換，找尋所有一跳（dsi

A.Baggio和K.Langendoen提出一種改進的MCL算法，稱為 MCB（Monte Carlo localization boxed）[22]。它的主要改進是把采樣區域限制在一個最小的有效范圍之內，使得估計的位置精度更加準確，而且還降低了計算開銷，這個區域被稱為錨節點盒或采樣盒，如圖4所示。在參考文獻[23]中利用了距離信息的MCL算法來提高估計精度，但是精度的改善是以增加通信開銷為代價的。參考文獻[24]中，一種二重的混合MCL被提出，精度進一步提高，但計算開銷也進一步增加。在WSN中，計算有效性是一個很重要的衡量標準，節點的簡約性決定了不可能有很強的計算能力，而在MCL中，主要的計算量取決于采樣個數的大小，由此參考文獻[25]提出了一種可變采樣數的MCL算法，既可以達到MCL相同的精度，又減少了計算開銷。

由于節點的移動性，移動節點本身可以提供定位信息，如在三個時刻與待測節點的測距可以確定這個節點的坐標，可以避免多跳和遠距離測量的誤差，因此，移動節點的路徑規劃就顯得很重要。

4 結束語

定位算法隨著WSN的發展而不斷發展，本文根據定位算法的特點，分類討論了目前主流的定位算法和它們的一些改進，但是，還有很多問題沒有解決，如能耗、同步、測距干擾、網絡優化、非凸區域等，都需要進一步改善。未來的研究方向可以從以下幾個方面考慮：方法的融合、智能天線、網絡的拓撲結構、模式識別等。

1 Turin George L,Jewell William S,Johnston Tom L.Simulation

of urban vehicle-monitoring systems.IEEE Transactions on Vehicular Technology,VT-21,Feb 1972

2 Zafer Sahinoglu,Sinan Gezici,Ismail Guvenc.Ultra-wideband positioning systems.Cambridge,Massachusetts,USA,Cambridge University Press,2008

3 Niculescu Dragos,Nath Badri.Ad hoc positioning system(APS).In:Conference Record /IEEE Global Telecommunications Conference,San Antonio,TX,United states 2001

4 Li Xiaoli,Shi Hongchi,Shang Yi.A partial-range-aware localization algorithm for ad-hoc wireless sensor networks.In:Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04),Tampa,FL,United States,Nov 2004

5 Savarese,Rabaey J,Langendoen K.Robust positioning algorithm for distributed ad-hoc wireless sensor networks.In:USENIX Technical Annual Conference,Monterey,CA,June 2002

6 Ji Weiwei,Liu Zhong.An improvement of DV-Hop algorithm in wireless sensor networks.In:2006 International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM 2006,Wuhan,China,2006

7 Priyantha Nissanka B,Balakrishnan Hari,Demaine Erik,et al.Anchor-free distributed localization in sensor networks.In:Proceedings of the First International Conference on Embedded Networked Sensor Systems,Los Angeles,CA,United States,2003

8 陳維桓.微分流形初步 （第二版）.北京：高等教育出版社，2001

9 Patwari N,Hero A,III.Manifold learning algorithms for localization in wireless sensor networks.In:Acoustics,Speech,and Signal Processing,2004 (ICASSP’04),Montreal,Que,Canada,May 2004

10 Shang Yi,Ruml Wheeler,Zhang,Ying,et al.Localization from mere connectivity. In: Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc),Annapolis,MD,United States,June 2003

11 Shang Yi,Ruml Wheeler.Improved MDS-based localization.In:IEEE INFOCOM,Hongkong,China,March 2004

12 Ding Yingqiang,Du Liufeng,Yang Ting,et al.Distributed localization algorithm for wireless sensor network based on multidimensional scaling and the shortest path distance correction.Transactions of Tianjin University,2009,15(4):237～244

13 Wang Chengqun,Chen Jiming,Sun Youxian,et al.Wireless Sensor Networks Localization with Isomap.In:ICC'09,Dresden,Germany,June 2009

14 Jiang Jie,Song Zhen,Zhang Heying,et al.Voronoi-based improved algorithm for connected coverage problem in wireless sensor networks.Lecture Notes in Computer Science(including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),v3824 LNCS,2005,Embedded and Ubiquitous Computing-International Conference EUC 2005,Proceedings,Nagasaki,Japan,Dec 2005

15 Bulusu Nirupama,Heidemann John,Estrin Deborah.GPS-less low cost outdoor localization for very small devices.IEEE Personal Communications,7(5):28～34

16 Shen Xingfa,Wang Zhi,Jiang Peng,et al.Connectivity and RSSI based localization scheme for wireless sensor networks.In:Advances in Intelligent Computing,International Conference on Intelligent Computing(ICIC 2005),Hefei,China,2005

17 He Tian,Huang Chengdu,Brian M.Blum,et al.Range-free localization schemes for large scale sensor networks.In:ACM International Conference on MobileComPutingandNetworking(MobiCom),SanDiego,Califomia,USA,2003

18 Yedavalli Kiran, Krishnamachari Bhaskar. Sequence-based localization in wireless sensor networks.IEEE Transactions on Mobile Computing,7(1):81～94

19 Biswas Pratik,Ye Yinyu.Semidefinite programming for ad hoc wireless sensor network localization. Third International Symposium on Information Processing in Sensor Networks(IPSN 2004),Berkeley,CA,United States,2004

20 Yuan Liang,Chen Weidong,Xi Yugeng.A review of control and localization for mobile sensor networks.In:Proceedings of the World Congress on Intelligent Control and Automation(WCICA),Dalian,China,June 2006

21 Hu Lingxuan,David Evans.Localization for mobile sensor networks.In:Proc of MobiCom 2004,Philadelphia,PA,USA,Sept 2004

22 Aline Baggio,Koen Langendoen.Monte-Carlo localization for mobile wireless sensor networks.In:Proc of Mobile Ad-hoc and Sensor Networks,Second International Conference,MSN 2006,Hong Kong,China,Dec 2006

23 Dil Bram, Dulman Stefan, Havinga Paul. Range-based localization in mobile sensor networks.Lecture Notes in Computer Science(including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),v3868 LNCS,2006,Wireless Sensor Networks-Third European Workshop,EWSN 2006,Proceedings,Zurich,Switzerland,Febrary 2006

24 Enrique Stevens-Navarro,Vijayanth Vivekanandan,Vincent W S Wong.Dual and mixture Monte Carlo localization algorithms for mobile wireless sensor networks.In:Proc of IEEE Wireless Communications and Networking Conference (WCNC'07),Hong Kong,China,March 2007

25 Wang Weidong,Zhu Qingxin.Varying the sample number for Monte Carlo localization in mobile sensor networks.In:Proceedings-2nd International Multi-Symposiums on Computer and Computational Sciences(IMSCCS'07),Iowa City,IA,United States,August 2007