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

于耕

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

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.

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

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

中圖分類號(hào)：TN929.5；TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2018）30-0194-03

0 引言

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

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

1 WSN節(jié)點(diǎn)定位的坐標(biāo)計(jì)算方法

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

1.1 三邊測(cè)量法

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

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

2.1 集中式定位算法

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

2.1.1 基于傳輸時(shí)間差（TDOA）的算法

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

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

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

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

2.1.3 基于信號(hào)強(qiáng)度（RSSI）的節(jié)點(diǎn)定位算法

RSSI算法[14]是根據(jù)接收到的信號(hào)強(qiáng)度與距離之間的關(guān)系來(lái)估計(jì)節(jié)點(diǎn)間的距離，然后節(jié)點(diǎn)的位置可以用三邊法或其他基于估計(jì)距離的方法計(jì)算出。因?yàn)槟壳皫缀跛械臒o(wú)線通信模塊都支持RSSI的測(cè)量功能，所以該算被廣泛的應(yīng)用。由于該算法容易受到環(huán)境的影響，因此，可以應(yīng)用在對(duì)定位要求不高的環(huán)境中。

2.2 分布式定位算法

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

2.2.1 質(zhì)心定位算法

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

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

2.2.2 SBSL定位算法

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

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

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

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

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

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

3 節(jié)點(diǎn)定位進(jìn)一步的研究方向

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

①人們?cè)谘芯慷ㄎ凰惴〞r(shí)只關(guān)注定位算法的精度，而忽略了能量消耗和定位效率。因此，傳感器節(jié)點(diǎn)定位中的能量消耗最小化問(wèn)題值得我們關(guān)注。

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

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

4 結(jié)論

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

參考文獻(xiàn)：

[1]任豐原，黃海寧，林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)綜述[J].電子信息學(xué)報(bào)，2013，35（1）：215-227.

[4]頓文濤，趙玉成，王力斌等.車聯(lián)網(wǎng)的關(guān)鍵技術(shù)及研究進(jìn)展[J].農(nóng)業(yè)網(wǎng)絡(luò)信息，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]王小平，羅軍，沈昌祥.三邊測(cè)量法的結(jié)果穩(wěn)定性[J].計(jì)算機(jī)工程與科學(xué)，2012，34（6）：12-17.

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

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

[11]彭宇，王丹.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測(cè)量與儀器學(xué)報(bào)，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]龍佳，卑璐璐，張申等.基于虛擬信標(biāo)節(jié)點(diǎn)的改進(jìn)加權(quán)質(zhì)心定位修正算法[J].微電子學(xué)與計(jì)算機(jī)，2017，34（3）：74-78.

[16]戴桂蘭，趙沖沖，邱巖.一種基于球面坐標(biāo)的無(wú)線傳感器網(wǎng)絡(luò)三維定位機(jī)制[J].電子學(xué)報(bào)，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.