于耕

摘要：在本文中首先介紹了節(jié)點坐標的計算方法，然后從集中式定位算法和分布式定位算法兩個方面討論了典型的節(jié)點定位算法。分析了當前無線傳感網(wǎng)絡節(jié)點定位技術存在的一些問題并指出了未來的研究方向和發(fā)展趨勢。

Abstract： In this paper， the calculation method of node coordinates is introduced first， and then the typical node localization algorithm is discussed from two aspects： centralized localization algorithm and distributed location algorithm. This paper analyzes some problems existing in the localization technology of wireless sensor networks， and points out the future research directions and development trends.

關鍵詞：無線傳感器網(wǎng)絡；節(jié)點定位；定位算法

Key words： wireless sensor networks；node localization；localization algorithm

中圖分類號：TN929.5；TP212.9 文獻標識碼：A 文章編號：1006-4311（2018）30-0194-03

0 引言

無線傳感器網(wǎng)絡（WSN）是將傳感器技術、嵌入式技術、無線通信技術和分布式數(shù)據(jù)計算技術相結合的一種自組網(wǎng)絡系統(tǒng)[1]。它可以實時采集網(wǎng)絡覆蓋區(qū)域的監(jiān)測信息，并且將這些信息發(fā)送給觀察者。

WSN最開始是在軍事領域中應用的[2]，隨著MEMS和微芯片制造技術的發(fā)展，傳感器節(jié)點成本的大大降低，功耗和體積的減小，WSN的新技術廣泛應用于日常生活和社會建設中，例如森林火災監(jiān)控、智能交通、健康醫(yī)療、物聯(lián)網(wǎng)[3]和車聯(lián)網(wǎng)[4]等。在這些應用中，傳感器節(jié)點的位置是至關重要的[5]。然而對于大規(guī)模的傳感器網(wǎng)絡來說，為每個節(jié)點安裝GPS接收器以獲得精確位置是不現(xiàn)實的[6]。因此，現(xiàn)在的辦法是給一部分節(jié)點安裝上GPS接收器[7]，剩下的節(jié)點利用這些節(jié)點進行自定位。所以，現(xiàn)在研究WSN節(jié)點的定位問題具有重要的理論意義和實際應用價值。

1 WSN節(jié)點定位的坐標計算方法

在WSN定位方法中，我們將知道自己位置坐標的節(jié)點稱為錨節(jié)點，需要定位的節(jié)點成為未知節(jié)點，在通信范圍內(nèi)可以直接通信的節(jié)點稱為該節(jié)點的鄰居節(jié)點。在節(jié)點定位階段，未知節(jié)點如果能夠獲得與臨近錨節(jié)點之間的距離，或者獲得未知節(jié)點與臨近錨節(jié)點之間的相對角度后，就可以用三邊測量法、三角測量法、極大似然估計法來計算未知節(jié)點的位置。

1.1 三邊測量法

2 節(jié)點定位常用算法分析

經(jīng)過多年的研究，國內(nèi)外學者對無線傳感器中的節(jié)點定位提出了眾多的改進算法，我們將這些算法可以分為集中式定位算法和分布式定位算法[11]。

2.1 集中式定位算法

集中式定位要求網(wǎng)絡把所有用于節(jié)點定位的信息通過多條路由傳送到一個點，然后在該節(jié)點運行定位算法對節(jié)點進行定位。這樣可以從整體出發(fā)來進行節(jié)點定位，獲得較高的定位精度。

2.1.1 基于傳輸時間差（TDOA）的算法

TDOA算法[12]是節(jié)點發(fā)送兩種已知傳播速度的測量信號，例如，電磁波和超聲波。因此，接收節(jié)點可以根據(jù)電磁波與超聲波的傳播時間差及其在空氣中傳播的速度來計算發(fā)送節(jié)點與接收節(jié)點之間的距離。根據(jù)計算出的距離利用第一節(jié)給出的坐標計算方法，即可計算出節(jié)點的坐標。利用該算法在視距范圍內(nèi)可以獲得較高的定位精度，但是該算法容易受外界環(huán)境的影響，而且該算法需要額外的硬件導致定位費用高。

2.1.2 MDS-MAP節(jié)點定位算法

MDS-MAP節(jié)點定位算法[13]是由哥倫比亞大學的Yi等人最早提出來的一種集中式的定位算法，這種定位算法是基于多維定標（multidimensional scaling，MDS）技術來實現(xiàn)的。MDS-MAP節(jié)點定位算法可以分為三個部分：第一部分，計算任意節(jié)點之間的距離，然后用任意節(jié)點之間的最短距離生成定位算法用到的距離矩陣。第二步，使用MDS技術來處理第一步得到的距離矩陣，求出定位所需要的特征值。并且利用得到的特征值計算出所有節(jié)點的相對坐標。第三部，利用錨節(jié)點的絕對坐標將上一步得到的節(jié)點相對坐標轉(zhuǎn)換成絕對坐標。

MDS-MAP節(jié)點定位算法在錨節(jié)點密度較低的情況下具有較高的定位精度，但是由于該算法是集中式定位算法，計算量和通信代價較大。

2.1.3 基于信號強度（RSSI）的節(jié)點定位算法

RSSI算法[14]是根據(jù)接收到的信號強度與距離之間的關系來估計節(jié)點間的距離，然后節(jié)點的位置可以用三邊法或其他基于估計距離的方法計算出。因為目前幾乎所有的無線通信模塊都支持RSSI的測量功能，所以該算被廣泛的應用。由于該算法容易受到環(huán)境的影響，因此，可以應用在對定位要求不高的環(huán)境中。

2.2 分布式定位算法

分布式定位算法是將定位算法所需的任務根據(jù)一定規(guī)則分配給各個節(jié)點，節(jié)點和自己的鄰居節(jié)點交換定位算法所需的信息，然后各個節(jié)點根據(jù)交換得到的消息各自的計算自己的位置。

2.2.1 質(zhì)心定位算法

質(zhì)心定位算[15]是根據(jù)節(jié)點之間的連通性來進行定位的，是一種分布式計算的定位算法。Bulusu等人最早提出的質(zhì)心定位算法是用在GPS定位上的，隨后該方法被用在了無線傳感器節(jié)點定位上。質(zhì)心算法是求多邊形的幾何中心，多邊形頂點坐標的平均值就是所求的未知節(jié)點的坐標。

質(zhì)心算法簡單，容易在實際應用中實現(xiàn)，適合定位精度要求不高的環(huán)境中。

2.2.2 SBSL定位算法

2008年，戴桂蘭等人提出了一種基于球面坐標的動態(tài)定位算法[16]，該算法是一種分布式定位算法。此算法將節(jié)點定位問題轉(zhuǎn)化成求解多元線性方程組解的問題，最終用克萊姆法則來解決多解和無解的問題。該算法假設定位模型是以未知節(jié)點為球心，最大通信半徑為圓心的球面，錨節(jié)點在移動過程中周期性的向網(wǎng)絡中廣播錨節(jié)點的ID號，錨節(jié)點的空間位置。當能夠獲得球體表面上不共面的四個點后，未知節(jié)點的位置能夠被準確的求出來。該算法的定位精度對錨節(jié)點密度和通信半徑不敏感，并且該算法在通信量和計算量方面做到了適中。

2.2.3 矢量-路由（DV-Hop）算法

DV-Hop算法[17]是一種很常用的分布式定位算法，該算法的定位過程可以分三個部分：

①網(wǎng)絡中的所有錨節(jié)點向整個網(wǎng)絡洪泛自己初始化位置的數(shù)據(jù)包，每個接收數(shù)據(jù)包的節(jié)點都為錨節(jié)點建立一個表，其中包含錨節(jié)點的位置和最小跳數(shù)，然后將最小跳數(shù)值+1后轉(zhuǎn)發(fā)給周圍的節(jié)點。

其中Dsk是錨節(jié)點s和未知節(jié)點k的距離，hsk是這兩點之間的最小跳數(shù)。

通過這樣的方法可以求出未知節(jié)點到錨節(jié)點的距離，然后利用前面介紹的極大似然估計的方法可以求解出待定位節(jié)點的坐標。

3 節(jié)點定位進一步的研究方向

傳感器節(jié)點定位已經(jīng)得到了廣泛的研究，但是，仍然有一些重要的問題有待解決，特別是節(jié)點定位的大規(guī)模應用。以下列舉了存在的一些問題：

①人們在研究定位算法時只關注定位算法的精度，而忽略了能量消耗和定位效率。因此，傳感器節(jié)點定位中的能量消耗最小化問題值得我們關注。

②現(xiàn)有的定位算法大多依賴于錨節(jié)點，隨著錨節(jié)點數(shù)量的增加，定位精度也隨之提高。然而，具有更多資源的移動錨節(jié)點比普通的傳感器節(jié)點昂貴。因此，對于節(jié)點定位，我們需要充分利用未知節(jié)點和錨節(jié)點之間的獨特關系，以減少錨節(jié)點的使用。

③在現(xiàn)有的定位場景中，大多數(shù)節(jié)點定位算法應用于二維平面網(wǎng)絡區(qū)域。然而，在復雜的現(xiàn)實應用中，節(jié)點往往隨機的分布在三維空間中，這就使得二維空間的定位算法不一定適用于三維空間。因此，在以后的研究中要注重三維空間的節(jié)點定位。

4 結論

對于網(wǎng)絡功能和許多應用來說，無線傳感器網(wǎng)絡中節(jié)點的位置是至關重要的。在這篇論文中，我們介紹了節(jié)點坐標的計算方法，重點對集中式定位算法和分布式定位算法進行了分析，總結了節(jié)點定位研究領域存在的一些問題和今后可以研究的內(nèi)容和方向。希望我們指出的定位技術存在的問題，可以為今后改進定位算法提供一些參考和借鑒。

參考文獻：

[1]任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡[J].軟件學報，2003，14（7）：1282-1291.

[2]Y. H. Liu， Z. Yang， X. P. Wang and L. R. Rong， Location， localization， and localizability[J]. Journal of Computer Science and Technology， 2010， 25（2）： 274-297.

[3]錢志鴻，王義君.面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡綜述[J].電子信息學報，2013，35（1）：215-227.

[4]頓文濤，趙玉成，王力斌等.車聯(lián)網(wǎng)的關鍵技術及研究進展[J].農(nóng)業(yè)網(wǎng)絡信息，2015，8：46-50.

[5]F. Cadger， K. Curran， J. Santos and S. Moffett， A survey of geographical routing in wireless ad-hoc networks[J]， IEEE Communications Surveys & Tutorials， 2013， 15（2）： 621-653.

[6]L. R. Tang， Y. Gong， Y. T. Luo， S. H. Ke， A 3D position algorithm based on Euclidean for wireless sensor network[J]. Acta Electronica Sinica， 2012， 40（4）： 821-825.

[7]Y. Ding， C. Wang， L. Xiao， Using mobile beacons to locate sensors in obstructed environments[J]. Journalof Parallel & Distributed Computing， 2010， 70（6）： 644-656.

[8]王小平，羅軍，沈昌祥.三邊測量法的結果穩(wěn)定性[J].計算機工程與科學，2012，34（6）：12-17.

[9]李建坡，鐘鑫鑫，徐純.無線傳感器網(wǎng)絡動態(tài)節(jié)點定位算法綜述[J].東北電力大學學報，2015，35（1）：52-58.

[10]徐原博，鐘麗鴻，崔洋等.基于無線傳感器網(wǎng)絡的極大似然定位算法的分析[J].傳感器與微系統(tǒng)，2011，30（10）：37-40.

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

[12]C. Liu， J. Yang， F. Wang， Joint TDOA and AOA location algorithm[J]. Journal of Systems Engineering and Electronics， 2013， 24（2）： 183-188.

[13]Shang Yi， Ruml W， Zhang Y， e1 al. Localization from Connectivity in Sensor Network[J]. IEEE Transactions on Parallel & Distributed Systems， 2004， 15（11）： 961-974.

[14]H. P. Mistry， N. H. Mistry， RSSI based localization scheme in wireless sensor networks： A survey[C]. International Conference on Advanced Computing & Communication Technologies， 2015， 7（1）： 1611-1615.

[15]龍佳，卑璐璐，張申等.基于虛擬信標節(jié)點的改進加權質(zhì)心定位修正算法[J].微電子學與計算機，2017，34（3）：74-78.

[16]戴桂蘭，趙沖沖，邱巖.一種基于球面坐標的無線傳感器網(wǎng)絡三維定位機制[J].電子學報，2008，36（7）：1297-1303.

[17]S Tomic， I Mezei. Improvements of DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Telecommunication Systems， 2016， 61（1）： 93-106.