無線傳感器網絡節點定位算法研究

于耕

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

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.

關鍵詞：無線傳感器網絡；節點定位；定位算法

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

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

0 引言

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

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

1 WSN節點定位的坐標計算方法

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

1.1 三邊測量法

2 節點定位常用算法分析

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

2.1 集中式定位算法

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

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

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

2.1.2 MDS-MAP節點定位算法

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

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

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

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

2.2 分布式定位算法

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

2.2.1 質心定位算法

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

質心算法簡單，容易在實際應用中實現，適合定位精度要求不高的環境中。

2.2.2 SBSL定位算法

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

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

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

①網絡中的所有錨節點向整個網絡洪泛自己初始化位置的數據包，每個接收數據包的節點都為錨節點建立一個表，其中包含錨節點的位置和最小跳數，然后將最小跳數值+1后轉發給周圍的節點。

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

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

3 節點定位進一步的研究方向

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

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

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

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

4 結論

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

參考文獻：

[1]任豐原，黃海寧，林闖.無線傳感器網絡[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]錢志鴻，王義君.面向物聯網的無線傳感器網絡綜述[J].電子信息學報，2013，35（1）：215-227.

[4]頓文濤，趙玉成，王力斌等.車聯網的關鍵技術及研究進展[J].農業網絡信息，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]王小平，羅軍，沈昌祥.三邊測量法的結果穩定性[J].計算機工程與科學，2012，34（6）：12-17.

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

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

[11]彭宇，王丹.無線傳感器網絡定位技術綜述[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]龍佳，卑璐璐，張申等.基于虛擬信標節點的改進加權質心定位修正算法[J].微電子學與計算機，2017，34（3）：74-78.

[16]戴桂蘭，趙沖沖，邱巖.一種基于球面坐標的無線傳感器網絡三維定位機制[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.