無線傳感器網絡定位綜述

陳亞楠+張牧

摘要：目前，無線傳感器網絡（WSN）需高效率地信息采集和處理，才能在廣泛的應用中實現復雜的跟蹤或監控任務. 本文首先給出定位技術用到的專業術語、定位性能的評價標準以及分類方法；本文重點從基于測距和非測距兩個方面，詳細介紹相關的定位方法；最后提出目前WSN的定位技術所存在的缺陷和不足，展望未來的研究前景。

關鍵詞：無線傳感器網絡；定位；分類；測距；非測距

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）34-0057-04

Abstract： At present， wireless sensor networks （WSN） need to efficiently collect and process information in order to achieve complex tracking or monitoring tasks in a wide range of applications. This paper firstly introduces the basic conceptions used in positioning technology， positioning performance evaluation criteria and classification methods； Furthermore， some localization algorithms are introduced detailedly in two aspects which are range-based and range-free. Finally， the paper puts forward the shortcomings and shortcomings of WSN positioning technology， and looks forward to the future research prospects.

Key words： wireless sensor network； localization； classification； range-based； range-free

1 概述

傳感器節點在WSN中的相對位置對節點起著重要作用，一般若能獲得傳感器節點的位置信息，那么對傳感器節點所采集的信息對應用才有意義[1]。

在監測區域中部署傳感器節點一般通過飛機等一些工具隨意部署，部署好所有節點之后，這些節點的位置是無法確定。所以通過一定的定位算法來獲知傳感器節點。目前使用最多、最廣泛的是全球定位系統（Global Positioning System， GPS）.通過GPS獲取傳感器節點的相對位置，雖然使用較多，但會存在能量消耗高、價格不菲、易被干擾、魯棒性低等特點，使得無法完成精確定位任務。因此在無線傳感器網絡中，研究傳感器節點的定位算法顯得特別重要[2-3]。

2 無線傳感器網絡定位性能的評價標準

下面介紹幾種常見的性能評價標準：

1） 定位精度。精度問題是判斷一個節點定位算法性能好壞的首要標準。節點的誤差值與無限射程的比值是節點的定位精度值。另外，比如微軟的Radio Camera[8]，其將二位網格部署區域分成網格狀，這樣網格的大小就是其定位結果的精度。

2） 信標節點密度。一般通過人工部署或者全球定位系統（GPS）來實現錨節點的定位。人工部署的節點應用性不高，還受到網絡環境的影響。而使用全球定位系統（GPS）實現節點的定位，信標節點的費用超出普通節點的費用100倍[4]. 所以信標節點的密度也嚴重影響算法的性能。

3） 節點密度。在無線傳感網中，越增加節點的密度，部署網絡的費用越高，越能受到節點之間通信沖突所導致的有限帶寬的阻礙。定位算法的精度會影響一些定位算法的性能，如在節點密集部署的情況下，DV-Hop[10，11]定位性能較高。

4） 自適應性。通常情況下，良好的無線傳感器網絡環境和先進的節點定位設備對定位系統和算法來說是需要的，但在實際應用中經常會出現一些問題。部署的環境或者節點本身問題導致節電定位失效。傳感器節點的物理維護或者其他高度精確的測量手段通常由于環境，能量消耗等因素而難以實現。節點通過自我糾錯和調整來適應各種環境，能降低產生誤差的概率，從而能提高傳感器節點定位的準確度。

5） 功耗。因為傳感器節點的能量是非常有限的，在已部署的外界環境中，節點所消耗的能量不會得到補充，所以定位技術的實現效果好壞也受到功耗的影響。在確保定位精度的情況下，存儲、通信成本、計算量的大小與功耗相關的時間復雜度是一組關鍵指標。

6） 代價。可以從時間代價、空間代價、資金代價三個方面來評估定位算法。時間代價是指該定位系統安裝、配置時間和精確定位所需時間。空間代價則是指該定位系統需要的節點數目、硬件大小、基礎設施等。資金代價是指實現該定位系統所需的總資金。

這些性能指標既相互聯系又相互制約，所以一般具體情況具體選擇合適的定位技術或者算法[12]，這樣才能精確定位一個節點的位置信息。

3 WSN定位問題分析

3.1 基本定位術語

1） 錨節點或信標節點：精確知道位置信息的節點。

2） 未知節點：要精確定位的傳感器節點。

3） 鄰節點： 一些在節點通信半徑內的傳感器節點。

4） 跳段距離： 是指兩個傳感器節點間跳段數的總和。

5） 到達時間（Time Of Arrival ，TOA）：即信號在兩個節點之間傳播所需時間。

6） 到達時間差（Time Difference Of Arrival ，TDOA）：兩種不同的傳播速度的信號在兩個節點間傳播的時間差。

7） 接收信號強度指示（Received Signal Strength Indicator ，RSSI）：指傳感器節點接收信號強度大小。

8） 到達角度（Angle Of Arrival ，AOA）：節點接收到的信號相對于自身軸線的角度。

3.2 網絡定位算法的分類

網絡定位有許多種方法各有利弊，這里主要介紹幾種常用的網絡定位算法

1） 絕對定位和相對定位

絕對定位是指確定一個點的絕對坐標，例如一個物體的GPS坐標就是其絕對位置，也就是絕對定位。相對定位則是根據一個已知絕對位置的點建立起一個網絡，通過這個網絡可以計算出其他節點的相對位置。目前來說相對定位更容易實現，而絕對定位則用途更加廣泛。

2） 測距定位和無需測距定位

測距定位是指利用額外的測距設備測量兩節點間的距離，假設已經知道了一個點位置，則通過測量距離以及其方向我們就可以準確定位另一個點的位置。無需測距定位測不需要通過測量距離來實現定位，如可以通過發送無線電波，根據接收時間和電波速度就可以計算兩點之間的距離實現定位。測距定位需要有額外的設備，造價昂貴且精準度不是特別高，無需測距定位成本較低，但對算法要求較高，需要精確的時間同步等額外條件。

3） 集中定位和分布定位

集中定位通過一個類似星形拓撲網的方式，用一個中心節點連接所有的其他結點，其他節點將定位所需信息發送給中心節點，然后對節點進行定位。分布定位是指節點通過與其他節點的信息交換和協調來對自身進行定位。集中式定位對定位節點的計算能力要求低，本身中心節點的存儲量不受限制，但是拓展困難，不宜應用于大型網絡。而分布定位對分節點的計算能力有一定的要求，并且對網速要求較低，靈活多變易擴展適合大型網絡。

4） 移動信標和固定信標定位

移動信標定位通過安裝一類定位設備如GPS、GNSS等，可在移動過程中不斷向衛星發送位置信息從而實現定位。固定信標定位是指采用價格較低廉的定位設備易收到位置干擾等因素，需要固定節點，使得定位雖然較為精準但是不夠靈活。由此可見在成本大幅降低的現在，移動信標必然成為未來定位的趨勢。

4 常見的測距方法

測距是測距定位方法中最核心的一部分，主要通過額外的測距設備獲得節點之間的距離、角度等關鍵的定位，但測距的精度很大程度上由儀器設備的精度決定，因此很難在物聯網中流行開來，我們都知道物聯網中的節點大多數是廉價的低能耗的傳感器設備，但不乏通過低價的測距設備通過算法優化得到較好的定位方法，常見的技術有TOA、TDOA、AOA和RSSI四種。

4.1 到達時間測量法（TOA）

物理信號在兩個節點之間傳播的總時間T，測量之前已知信號的傳播速度V，那么可得治兩個節點之間的距離為S=V*T，這種方式也是最易想到的。但是此方法嚴格要求節點的傳播時間，如果傳播的時間不同步，那么節點定位會產生誤差，所以需嚴格要求測量節點的硬件。

4.2 到達時間差測量法（TDOA）

4.3 到達信號強度測量法（RSSI）

基于RSSI的測距方案時通過測量CC2420接收到的射頻信號的強度，采用適當的電波的傳輸模型對目標節點的位置進行判斷的一種測距方法。該算法的關鍵之處是通過測量RF信號的衰減程度來計算未知節點和信標節點間的距離。最后，測量的距離值用于估計未知節點的位置。

5 無需測距的定位算法

基于測距的節點定位算法的最優之處就是能精確節點的位置信息，然而該算法需要較高的硬件，較高的硬件要求使得算法的成本、能耗也高。為此人們提出了Range-Free算法。 Range-Free算法無需精確測量傳感器節點的角度和距離，該算法雖然對硬件的要求不高，但它會產生的誤差反而會大大提高了。Range-Free還具有可擴展性、規模性及代價小等一些優點。質心算法（Centroid Algorithm）、DV-Hop（Distance Vector-Hop）定位、凸規劃（Convex Optimization）定位算法等都具有典型的基于無須測距的定位算法。

5.1 凸規劃定位算法

用節點之間相互通信問題轉化為一個凸集問題，我們可以通過凸約束優化問題來解決解決凸集問題。然而要想得到一個全局最優的結果，我們可以結合SDP和LP這兩種方法來確定傳感器節點的位置信息[6]. 與此同時，我們會得到節點的可能存在區域，如圖3所示的矩形區域，最后可知未知節點的位置就是該矩形區域的質心。

5.2 DV-Hop定位算法

一般分三個步驟：具體如下：

（1） 第一步，網絡中的所有節點之間完成信息的交換。任意一個信標節點將自己的信息傳送給無線傳感器網絡中除了本身節點以外的其他節點，這樣改信標節點可以知道與其他信標節點的跳數距離。

（2） 第二步，經過第一步的發送信息后，求解兩個節點之間的跳距距離之和，然后求解平均距離，在WSN中傳播該值。每一個信標節點一收到其他信標節點的信息后，節點就求解它們之間的跳距，在WSN中把計算出來的跳距值最為校正值，驗證節點之間的跳數距離是否是最小的，從而依次求出節點之間的跳距。

（3） 第三步，得出未知傳感器節點的位置信息。通過第二步的方法，可以得出未知節點與信標節點之間的距離，而已知信標節點的位置信息，所以可以求解出未知節點的具體位置[9]。

6 總結與展望

目前為止，無線傳感器網絡定位研究已經得到廣泛開展，但仍有一些問題尚未解決或發現，最關注的問題仍然是節點的能耗問題，在精度和能量消耗上，一切定位算法應考慮雙方面因素，選擇較優的算法。

雖然目前定位算法、設備以及策略都已經發展的比較成熟了，但對比信息技術的高速發展和物聯網的廣泛應用，當前的無線傳感網定位系統遠不能達到人們需求。當前的定位系統有以下問題亟待解決：

1） 定位精度有待提高。無線傳感網中高精度定都往往依賴于高精度的測距，而高精度的測距需要價格較高的額外設備，對于廉價的傳感器網絡不易實現，并且在高精度下必然帶來較高的能耗問題，因此低功耗和高精度不可能同時滿足。對于這種情況我們需要在精度和能耗之間有效折衷，提出一個低功耗、高精度的節點定位算法很有意義。

2） 實用性差。很多學者提出的非測距都是通過仿真模擬實驗得知算法的優越性，仿真模擬考慮到的因素與現實因素相比，模擬考慮的因素單一，實用性低等。因此提出具有實用價值的定位算法很有現實意義。

3） 隱私安全問題。在大范圍WSN中，未知位置的節點需要向信標節點發送消息，從而會透露出自己的信息，因而網絡隱私問題在定位過程中需要主義的一環。而另一些應用通過一些手段來得知節點的位置，可以很好地解決WSN節點的隱私安全問題。

4） 挖掘可用的新信息。微電子技術的發展使得傳感器體積越來越小，功耗越來越低，由此產生的可穿戴設備對人們的生活產生巨大的影響帶來了巨大的便利，通過這些可穿戴設備可實現隨時隨地的定位，我們可以知道人們在哪，通過這些信息，判斷出他們的愛好可以做到精準的廣告投放，同時可以統計在同一片地區的人們，推薦為微博好友。對于位置的檢測可以用來預測速度提供運動速度記錄，從而提供更好的跑步方案，總之位置信息可以有大量新的有用的信息有待挖掘。

參考文獻：

[1] 王焱，單欣欣，姜偉. 無線傳感網絡中移動節點定位技術研究[J].傳感技術學報，2011，24（10）：1469-1472

[2] 郝志凱，王碩. 無線傳感器網絡定位綜述[J].華中科技大學學報：自然科學版，2008，36（1）：224-227.

[3] 滕國棟.無線傳感網絡節點定位算法的研究[D].杭州：浙江大學，2010.

[4] Spec：Smartdust chip with integrated RF communications.2001.http：//www.jlhlabs.com/jhill_cs/spec/

[5] 彭宇，王丹. 無線傳感器網絡定位技術綜述[J].電子測量與儀器學報，2011，25（5）：389-399.

[6] Doherty L ，Pister KSJ ，Ghaoui LE.Convex Position Estimation in Wireless Sensor Networks[C] // Proc. of the IEEE INFOCOM 2001.Vol.3 ， Anchorage ： IEEE Computer and Communication Societies ， 2001： 1655-1663.

[7] 張浩亮.基于TDOA的無線傳感器網絡定位問題研究[D].長沙：國防科學技術大學，2011.

[8] Meguerdichian S，Koushanfar F，Potkonjak M，Srivastava MB.Coverage problems in wireless ad-hoc sensor networks.In：Proc.of the IEEE INFOCOM 2001.V01.3，Anchorage：IEEE Computer and Communications Societies，2001.1380-1387.http：//www.cs.ucla.edu/～miodrag/papers/Meguerdichian_Infocom_01.pdf.

[9] Zhao W，Liu C，Shu Y，et al.A SPC-based adaptive RTO algorithm[C]//2011 7th International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM），2011：1-4.

[10] Nicolescu D，Nath B.Ad-Hoc positioning systems（APS）.In：Proc.ofthe 2001 IEEE Global Telecommunications Cone V01.5，San Antonio：IEEE Communications Society，2001.2926-2931.http：//paul.rutgers.edu/～dnicules/research/aps/aoa—infocom.pdf.

[11] Niculescu D， Nath B.DV based positioning in ad hoe networks.Journal of Telecommunication Systems，2003，22（1/4）：267-280.

[12] Bulusu N， Estrin D， Heidemann J.Tradeoffs in location support systems：The ease for quality-expressive location models for applications. In： Proc. ofthe Ubicomp 2001 Workshop on Location Modeling for Applications.Atlanta，2001.7-12. http：//lecs.cs.ucla.edu/～bulusu/papers/Bulusu01d.pdf.