無線傳感器網(wǎng)絡(luò)定位綜述

陳亞楠+張牧

摘要：目前，無線傳感器網(wǎng)絡(luò)（WSN）需高效率地信息采集和處理，才能在廣泛的應(yīng)用中實(shí)現(xiàn)復(fù)雜的跟蹤或監(jiān)控任務(wù). 本文首先給出定位技術(shù)用到的專業(yè)術(shù)語、定位性能的評價(jià)標(biāo)準(zhǔn)以及分類方法；本文重點(diǎn)從基于測距和非測距兩個(gè)方面，詳細(xì)介紹相關(guān)的定位方法；最后提出目前WSN的定位技術(shù)所存在的缺陷和不足，展望未來的研究前景。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；定位；分類；測距；非測距

中圖分類號：TP311 文獻(xiàn)標(biāo)識(shí)碼：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 概述

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

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

2 無線傳感器網(wǎng)絡(luò)定位性能的評價(jià)標(biāo)準(zhǔn)

下面介紹幾種常見的性能評價(jià)標(biāo)準(zhǔn)：

1） 定位精度。精度問題是判斷一個(gè)節(jié)點(diǎn)定位算法性能好壞的首要標(biāo)準(zhǔn)。節(jié)點(diǎn)的誤差值與無限射程的比值是節(jié)點(diǎn)的定位精度值。另外，比如微軟的Radio Camera[8]，其將二位網(wǎng)格部署區(qū)域分成網(wǎng)格狀，這樣網(wǎng)格的大小就是其定位結(jié)果的精度。

2） 信標(biāo)節(jié)點(diǎn)密度。一般通過人工部署或者全球定位系統(tǒng)（GPS）來實(shí)現(xiàn)錨節(jié)點(diǎn)的定位。人工部署的節(jié)點(diǎn)應(yīng)用性不高，還受到網(wǎng)絡(luò)環(huán)境的影響。而使用全球定位系統(tǒng)（GPS）實(shí)現(xiàn)節(jié)點(diǎn)的定位，信標(biāo)節(jié)點(diǎn)的費(fèi)用超出普通節(jié)點(diǎn)的費(fèi)用100倍[4]. 所以信標(biāo)節(jié)點(diǎn)的密度也嚴(yán)重影響算法的性能。

3） 節(jié)點(diǎn)密度。在無線傳感網(wǎng)中，越增加節(jié)點(diǎn)的密度，部署網(wǎng)絡(luò)的費(fèi)用越高，越能受到節(jié)點(diǎn)之間通信沖突所導(dǎo)致的有限帶寬的阻礙。定位算法的精度會(huì)影響一些定位算法的性能，如在節(jié)點(diǎn)密集部署的情況下，DV-Hop[10，11]定位性能較高。

4） 自適應(yīng)性。通常情況下，良好的無線傳感器網(wǎng)絡(luò)環(huán)境和先進(jìn)的節(jié)點(diǎn)定位設(shè)備對定位系統(tǒng)和算法來說是需要的，但在實(shí)際應(yīng)用中經(jīng)常會(huì)出現(xiàn)一些問題。部署的環(huán)境或者節(jié)點(diǎn)本身問題導(dǎo)致節(jié)電定位失效。傳感器節(jié)點(diǎn)的物理維護(hù)或者其他高度精確的測量手段通常由于環(huán)境，能量消耗等因素而難以實(shí)現(xiàn)。節(jié)點(diǎn)通過自我糾錯(cuò)和調(diào)整來適應(yīng)各種環(huán)境，能降低產(chǎn)生誤差的概率，從而能提高傳感器節(jié)點(diǎn)定位的準(zhǔn)確度。

5） 功耗。因?yàn)閭鞲衅鞴?jié)點(diǎn)的能量是非常有限的，在已部署的外界環(huán)境中，節(jié)點(diǎn)所消耗的能量不會(huì)得到補(bǔ)充，所以定位技術(shù)的實(shí)現(xiàn)效果好壞也受到功耗的影響。在確保定位精度的情況下，存儲(chǔ)、通信成本、計(jì)算量的大小與功耗相關(guān)的時(shí)間復(fù)雜度是一組關(guān)鍵指標(biāo)。

6） 代價(jià)?？梢詮臅r(shí)間代價(jià)、空間代價(jià)、資金代價(jià)三個(gè)方面來評估定位算法。時(shí)間代價(jià)是指該定位系統(tǒng)安裝、配置時(shí)間和精確定位所需時(shí)間?？臻g代價(jià)則是指該定位系統(tǒng)需要的節(jié)點(diǎn)數(shù)目、硬件大小、基礎(chǔ)設(shè)施等。資金代價(jià)是指實(shí)現(xiàn)該定位系統(tǒng)所需的總資金。

這些性能指標(biāo)既相互聯(lián)系又相互制約，所以一般具體情況具體選擇合適的定位技術(shù)或者算法[12]，這樣才能精確定位一個(gè)節(jié)點(diǎn)的位置信息。

3 WSN定位問題分析

3.1 基本定位術(shù)語

1） 錨節(jié)點(diǎn)或信標(biāo)節(jié)點(diǎn)：精確知道位置信息的節(jié)點(diǎn)。

2） 未知節(jié)點(diǎn)：要精確定位的傳感器節(jié)點(diǎn)。

3） 鄰節(jié)點(diǎn)： 一些在節(jié)點(diǎn)通信半徑內(nèi)的傳感器節(jié)點(diǎn)。

4） 跳段距離： 是指兩個(gè)傳感器節(jié)點(diǎn)間跳段數(shù)的總和。

5） 到達(dá)時(shí)間（Time Of Arrival ，TOA）：即信號在兩個(gè)節(jié)點(diǎn)之間傳播所需時(shí)間。

6） 到達(dá)時(shí)間差（Time Difference Of Arrival ，TDOA）：兩種不同的傳播速度的信號在兩個(gè)節(jié)點(diǎn)間傳播的時(shí)間差。

7） 接收信號強(qiáng)度指示（Received Signal Strength Indicator ，RSSI）：指傳感器節(jié)點(diǎn)接收信號強(qiáng)度大小。

8） 到達(dá)角度（Angle Of Arrival ，AOA）：節(jié)點(diǎn)接收到的信號相對于自身軸線的角度。

3.2 網(wǎng)絡(luò)定位算法的分類

網(wǎng)絡(luò)定位有許多種方法各有利弊，這里主要介紹幾種常用的網(wǎng)絡(luò)定位算法

1） 絕對定位和相對定位

絕對定位是指確定一個(gè)點(diǎn)的絕對坐標(biāo)，例如一個(gè)物體的GPS坐標(biāo)就是其絕對位置，也就是絕對定位。相對定位則是根據(jù)一個(gè)已知絕對位置的點(diǎn)建立起一個(gè)網(wǎng)絡(luò)，通過這個(gè)網(wǎng)絡(luò)可以計(jì)算出其他節(jié)點(diǎn)的相對位置。目前來說相對定位更容易實(shí)現(xiàn)，而絕對定位則用途更加廣泛。

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

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

3） 集中定位和分布定位

集中定位通過一個(gè)類似星形拓?fù)渚W(wǎng)的方式，用一個(gè)中心節(jié)點(diǎn)連接所有的其他結(jié)點(diǎn)，其他節(jié)點(diǎn)將定位所需信息發(fā)送給中心節(jié)點(diǎn)，然后對節(jié)點(diǎn)進(jìn)行定位。分布定位是指節(jié)點(diǎn)通過與其他節(jié)點(diǎn)的信息交換和協(xié)調(diào)來對自身進(jìn)行定位。集中式定位對定位節(jié)點(diǎn)的計(jì)算能力要求低，本身中心節(jié)點(diǎn)的存儲(chǔ)量不受限制，但是拓展困難，不宜應(yīng)用于大型網(wǎng)絡(luò)。而分布定位對分節(jié)點(diǎn)的計(jì)算能力有一定的要求，并且對網(wǎng)速要求較低，靈活多變易擴(kuò)展適合大型網(wǎng)絡(luò)。

4） 移動(dòng)信標(biāo)和固定信標(biāo)定位

移動(dòng)信標(biāo)定位通過安裝一類定位設(shè)備如GPS、GNSS等，可在移動(dòng)過程中不斷向衛(wèi)星發(fā)送位置信息從而實(shí)現(xiàn)定位。固定信標(biāo)定位是指采用價(jià)格較低廉的定位設(shè)備易收到位置干擾等因素，需要固定節(jié)點(diǎn)，使得定位雖然較為精準(zhǔn)但是不夠靈活。由此可見在成本大幅降低的現(xiàn)在，移動(dòng)信標(biāo)必然成為未來定位的趨勢。

4 常見的測距方法

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

4.1 到達(dá)時(shí)間測量法（TOA）

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

4.2 到達(dá)時(shí)間差測量法（TDOA）

4.3 到達(dá)信號強(qiáng)度測量法（RSSI）

基于RSSI的測距方案時(shí)通過測量CC2420接收到的射頻信號的強(qiáng)度，采用適當(dāng)?shù)碾姴ǖ膫鬏斈Ｐ蛯δ繕?biāo)節(jié)點(diǎn)的位置進(jìn)行判斷的一種測距方法。該算法的關(guān)鍵之處是通過測量RF信號的衰減程度來計(jì)算未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的距離。最后，測量的距離值用于估計(jì)未知節(jié)點(diǎn)的位置。

5 無需測距的定位算法

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

5.1 凸規(guī)劃定位算法

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

5.2 DV-Hop定位算法

一般分三個(gè)步驟：具體如下：

（1） 第一步，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)之間完成信息的交換。任意一個(gè)信標(biāo)節(jié)點(diǎn)將自己的信息傳送給無線傳感器網(wǎng)絡(luò)中除了本身節(jié)點(diǎn)以外的其他節(jié)點(diǎn)，這樣改信標(biāo)節(jié)點(diǎn)可以知道與其他信標(biāo)節(jié)點(diǎn)的跳數(shù)距離。

（2） 第二步，經(jīng)過第一步的發(fā)送信息后，求解兩個(gè)節(jié)點(diǎn)之間的跳距距離之和，然后求解平均距離，在WSN中傳播該值。每一個(gè)信標(biāo)節(jié)點(diǎn)一收到其他信標(biāo)節(jié)點(diǎn)的信息后，節(jié)點(diǎn)就求解它們之間的跳距，在WSN中把計(jì)算出來的跳距值最為校正值，驗(yàn)證節(jié)點(diǎn)之間的跳數(shù)距離是否是最小的，從而依次求出節(jié)點(diǎn)之間的跳距。

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

6 總結(jié)與展望

目前為止，無線傳感器網(wǎng)絡(luò)定位研究已經(jīng)得到廣泛開展，但仍有一些問題尚未解決或發(fā)現(xiàn)，最關(guān)注的問題仍然是節(jié)點(diǎn)的能耗問題，在精度和能量消耗上，一切定位算法應(yīng)考慮雙方面因素，選擇較優(yōu)的算法。

雖然目前定位算法、設(shè)備以及策略都已經(jīng)發(fā)展的比較成熟了，但對比信息技術(shù)的高速發(fā)展和物聯(lián)網(wǎng)的廣泛應(yīng)用，當(dāng)前的無線傳感網(wǎng)定位系統(tǒng)遠(yuǎn)不能達(dá)到人們需求。當(dāng)前的定位系統(tǒng)有以下問題亟待解決：

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

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

3） 隱私安全問題。在大范圍WSN中，未知位置的節(jié)點(diǎn)需要向信標(biāo)節(jié)點(diǎn)發(fā)送消息，從而會(huì)透露出自己的信息，因而網(wǎng)絡(luò)隱私問題在定位過程中需要主義的一環(huán)。而另一些應(yīng)用通過一些手段來得知節(jié)點(diǎn)的位置，可以很好地解決WSN節(jié)點(diǎn)的隱私安全問題。

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

參考文獻(xiàn)：

[1] 王焱，單欣欣，姜偉. 無線傳感網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)定位技術(shù)研究[J].傳感技術(shù)學(xué)報(bào)，2011，24（10）：1469-1472

[2] 郝志凱，王碩. 無線傳感器網(wǎng)絡(luò)定位綜述[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，36（1）：224-227.

[3] 滕國棟.無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的研究[D].杭州：浙江大學(xué)，2010.

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

[5] 彭宇，王丹. 無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報(bào)，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的無線傳感器網(wǎng)絡(luò)定位問題研究[D].長沙：國防科學(xué)技術(shù)大學(xué)，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.