無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究

彭燕

摘要： 文章介紹了無線傳感器節(jié)點(diǎn)定位技術(shù)的相關(guān)術(shù)語，結(jié)合常用的定位算法，主要介紹了DV-hop算法、質(zhì)心定位算法和DV-distance等算法進(jìn)行了介紹，不同的范圍可以使用不同的算法。最后定位算法的評(píng)價(jià)標(biāo)準(zhǔn)被介紹。

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.

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)；節(jié)點(diǎn)定位技術(shù)；節(jié)點(diǎn)定位算法

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

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2018）04-0192-02

0 引言

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

1 定位技術(shù)介紹

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

1.1 基本術(shù)語介紹

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

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

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

到達(dá)時(shí)間（time of arrival，TOA）：兩兩節(jié)點(diǎn)通信時(shí)所需時(shí)長(zhǎng)。

到達(dá)角度（angle of Arrial，AOA）：節(jié)點(diǎn)接收信號(hào)時(shí)軸線與所接收到的信號(hào)方向間的夾角角度。

接收信號(hào)強(qiáng)度（received signal strength indicator，RSSI）：某個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)傳送數(shù)據(jù)，接收所用的信號(hào)強(qiáng)度大小。

1.2 節(jié)點(diǎn)位置的計(jì)算方法

1.2.1 三邊測(cè)量法

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

1.2.2 極大似然估計(jì)法

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

1.3 定位技術(shù)分類

在傳感器網(wǎng)絡(luò)定位技術(shù)中，定位算法在采用不同的分類方式時(shí)可以被分類。根據(jù)是否知道測(cè)量節(jié)點(diǎn)間的距離，可將定位算法分為兩類，分別是基于距離和與距離無關(guān)。

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

基于TOA的定位、基于TDOA的定位、基于AOA的定位和基于RSSI的定位，這四種方法常用于傳感器網(wǎng)絡(luò)定位過程。到達(dá)時(shí)間、到達(dá)角度和信號(hào)衰減這三種技術(shù)是通用的測(cè)量技術(shù)。到達(dá)時(shí)間TOA和到達(dá)時(shí)間差TDOA用來表示到達(dá)時(shí)間。接收信號(hào)方向?qū)τ诠?jié)點(diǎn)自身軸線的角度就是到達(dá)角度AOA。已知發(fā)射節(jié)點(diǎn)的發(fā)射信號(hào)強(qiáng)度，接收點(diǎn)根據(jù)收到信號(hào)強(qiáng)度用于估算發(fā)送該信號(hào)的節(jié)點(diǎn)距離，這就是基于RSSI的定位算法。endprint

質(zhì)心算法、DV-hop算法、APIT算法、Amorphous算法是經(jīng)典的無需測(cè)距的定位算法。對(duì)高密度的信標(biāo)節(jié)點(diǎn)具有依賴的是質(zhì)心算法和APIT算法。依靠泛洪式路由，由確定未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的跳數(shù)信息來計(jì)算距離的算法是DV-hop算法和Amorphous算法。

2 典型的定位算法

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

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

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

3 定位算法的評(píng)價(jià)標(biāo)準(zhǔn)

節(jié)點(diǎn)定位算法的種類有很多，經(jīng)多年研究發(fā)現(xiàn)制定了標(biāo)準(zhǔn)，用于檢測(cè)衡量定位算法是否合格。它們是定位的精確性、節(jié)點(diǎn)的密度、錨節(jié)點(diǎn)密度、算法的代價(jià)、算法具有容錯(cuò)性和節(jié)點(diǎn)覆蓋率。

4 結(jié)束語

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

參考文獻(xiàn)：

[1]孫利民.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005：3-5.

[2]張偉.面向精細(xì)農(nóng)業(yè)的無線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)研究[D].浙江大學(xué)，2013.

[3]楊寧，田輝，張平，李立宏.無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究[J].無線電工程，2006（02）.endprint