無線傳感器網絡節(jié)點定位算法研究

彭燕

摘要： 文章介紹了無線傳感器節(jié)點定位技術的相關術語，結合常用的定位算法，主要介紹了DV-hop算法、質心定位算法和DV-distance等算法進行了介紹，不同的范圍可以使用不同的算法。最后定位算法的評價標準被介紹。

Abstract： This paper introduces the related terminology of wireless sensor node location technology， and introduces some commonly used algorithms such as DV-hop algorithm， centroid localization algorithm and DV-distance algorithm. Different algorithms can be used in different ranges. The final location algorithm evaluation criteria are introduced.

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

Key words： wireless sensor network node；node location technology；node location algorithm

中圖分類號：TP212.9 文獻標識碼：A 文章編號：1006-4311（2018）04-0192-02

0 引言

隨著社會大環(huán)境的不斷發(fā)展，各項技術的不斷完善，無線傳感器網絡被逐漸應用到各行各業(yè)。在傳感器網絡中，位置信息對于傳感器網絡監(jiān)測至關重要，可以說節(jié)點位置信息決定了整個網絡的信息傳遞。一般情況下，大量的傳感器節(jié)點被隨機地、無序地分布在特定區(qū)域，每個節(jié)點的位置信息是不確定的[1]。在實際應用過程中，如何實現低成本、低功耗和較高精度的節(jié)點定位是無線傳感器網絡系統(tǒng)的研究重點之一。

1 定位技術介紹

位置信息是傳感器節(jié)點數據采集最重要的組成部分，只有采集到了位置信息，傳感器節(jié)點的數據采集才是有意義的，只有這樣才能起到信息監(jiān)控的作用。然而在無線傳感器網絡中節(jié)點是隨機布置，位置信息是提前并不被知道的，節(jié)點自身的位置就需要在布置節(jié)點工作完成后由節(jié)點自主的給出來[2]。

1.1 基本術語介紹

節(jié)點被分為信標節(jié)點（beacon node）和未知節(jié)點（unknown node），其劃分依據是在傳感器網絡定位期間，節(jié)點是否了解自己的位置決定的。知道自己位置信息的是信標節(jié)點，這類節(jié)點的位置信息通常提前被知道，比如由GPS（global position system）定位系統(tǒng)提前知道。不知道自己位置信息的那部分節(jié)點是未知節(jié)點，這些節(jié)點通常被隨機布置在傳感器網絡中，通常用隨機發(fā)現的方式加入網絡。傳感器網絡定位技術作為一種定位技術，其原理就是利用已知的少數位置信息的信標節(jié)點確定未知的多數節(jié)點位置。方法是采用信標節(jié)點的信息來測量各個節(jié)點信息，以此估計測量節(jié)點之間的距離。此外，獲取節(jié)點位置信息的方式還包括測量節(jié)點的信息等，從而確定位置節(jié)點的位置信息。

跳數（hop count）：通信時，兩節(jié)點相互之間間隔的跳段總數。

鄰居節(jié)點（neighbor node）：通常相互之間通信的節(jié)點，每個節(jié)點相互之間即為相鄰節(jié)點。

到達時間（time of arrival，TOA）：兩兩節(jié)點通信時所需時長。

到達角度（angle of Arrial，AOA）：節(jié)點接收信號時軸線與所接收到的信號方向間的夾角角度。

接收信號強度（received signal strength indicator，RSSI）：某個節(jié)點到另一個節(jié)點傳送數據，接收所用的信號強度大小。

1.2 節(jié)點位置的計算方法

1.2.1 三邊測量法

思想是計算未知節(jié)點的位置信息，主要根據已知信標節(jié)點的坐標。A、B、C三個信標節(jié)點已知，他們距離未知節(jié)點D的距離為da、db和dc。三個圓交匯于一點，三個圓的圓心是信標節(jié)點，半徑選為信標節(jié)點到未知節(jié)點的距離，這一點就是未知節(jié)點的位置。

1.2.2 極大似然估計法

假設有3個或者以上各信標節(jié)點1，2，…n包圍住未知節(jié)點U。信標節(jié)點的坐標位置為（x1，y1），（x2，y2），…，（xn，yn）。d1，d2，…，dn為信標節(jié)點到未知節(jié)點的距離。設（x，y）為未知節(jié)點坐標。那么各信標節(jié)點到未知節(jié)點的距離可列寫n元方程組，對方程組進行重新排列可得到AX=b的方程組，并解這個方程組，方法是使用最小二乘法。未知節(jié)點的估計坐標（x，y）就可以被估計出來。

1.3 定位技術分類

在傳感器網絡定位技術中，定位算法在采用不同的分類方式時可以被分類。根據是否知道測量節(jié)點間的距離，可將定位算法分為兩類，分別是基于距離和與距離無關。

基于距離的算法，可用三個步驟來描述：測量位置節(jié)點到鄰居節(jié)點的距離或角度，計算未知節(jié)點到已知信標節(jié)點的距離或方位這是其一；利用三邊測距法估算普通節(jié)點的初始位置，根據信標節(jié)點的坐標及其到信標節(jié)點的距離或角度信息，這是其二。最后，對普通節(jié)點的估算位置來迭代求精并采用相對的措施。

基于TOA的定位、基于TDOA的定位、基于AOA的定位和基于RSSI的定位，這四種方法常用于傳感器網絡定位過程。到達時間、到達角度和信號衰減這三種技術是通用的測量技術。到達時間TOA和到達時間差TDOA用來表示到達時間。接收信號方向對于節(jié)點自身軸線的角度就是到達角度AOA。已知發(fā)射節(jié)點的發(fā)射信號強度，接收點根據收到信號強度用于估算發(fā)送該信號的節(jié)點距離，這就是基于RSSI的定位算法。endprint

質心算法、DV-hop算法、APIT算法、Amorphous算法是經典的無需測距的定位算法。對高密度的信標節(jié)點具有依賴的是質心算法和APIT算法。依靠泛洪式路由，由確定未知節(jié)點到信標節(jié)點的跳數信息來計算距離的算法是DV-hop算法和Amorphous算法。

2 典型的定位算法

2.1 質心定位算法 傳感器節(jié)點接收到相鄰的信標節(jié)點按一定周期發(fā)送來信標信號。信標節(jié)點的ID及其位置信息包含在此信標信號中。信標節(jié)點數目在未知節(jié)點周圍是不一定的，因此，未知節(jié)點接收到的信標節(jié)點數目并不固定，由未知節(jié)點所接收到的信標節(jié)點總數目是一門限，若該門限超過某一有限k，一段時間后，可將此未知節(jié)點當成是這些信標節(jié)點組成多邊形的質心。

2.2 DV-hop算法 未知節(jié)點第一步先計算與信標節(jié)點的最小跳數，第二步估算平均每跳的距離，并采用平均每跳距離乘以最小跳數的方法，估算出未知節(jié)點與信標節(jié)點間的距離，第三步是利用三邊測距法或極大似然估計法計算未知節(jié)點的坐標，在距離向量-跳段DV-hop（distance vector-hop）定位算法中。

2.3 DV-distance算法 與DV-hop相似，DV-distance算法也是采用平均每跳距離的方式計算實際距離。但兩者之間也存在明顯區(qū)別，后者是利用RSSI來測量相鄰節(jié)點間的距離。

3 定位算法的評價標準

節(jié)點定位算法的種類有很多，經多年研究發(fā)現制定了標準，用于檢測衡量定位算法是否合格。它們是定位的精確性、節(jié)點的密度、錨節(jié)點密度、算法的代價、算法具有容錯性和節(jié)點覆蓋率。

4 結束語

本文首先介紹了定位技術的相關術語，然后說明了常用的定位算法，并分析了其評價標準。當前關于定位算法種類繁多，包括DV-hop算法、質心定位算法、DV-distance算法等，且每種算法都有其適用范圍，可結合實際情況擇優(yōu)選用。

參考文獻：

[1]孫利民.無線傳感器網絡[M].北京：清華大學出版社，2005：3-5.

[2]張偉.面向精細農業(yè)的無線傳感器網絡關鍵技術研究[D].浙江大學，2013.

[3]楊寧，田輝，張平，李立宏.無線傳感器網絡拓撲結構研究[J].無線電工程，2006（02）.endprint