一種無(wú)需GPS分布式迭代無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法

丁自詠 崔艷榮

摘要：針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中需依賴裝配有GPS的信標(biāo)節(jié)點(diǎn)來(lái)進(jìn)行節(jié)點(diǎn)定位可能產(chǎn)生的問(wèn)題進(jìn)行了分析。首先分析了基于信標(biāo)節(jié)點(diǎn)定位算法的不合理性，利用安裝了GPS的信標(biāo)系節(jié)點(diǎn)會(huì)增大節(jié)點(diǎn)能量消耗，引起能量空洞，縮短網(wǎng)絡(luò)生存期。提出一種無(wú)需GPS分布式迭代定位算法，算法的目的是減少節(jié)點(diǎn)對(duì)硬件的依賴，減少節(jié)點(diǎn)在定位過(guò)程信息傳遞和最小化交換的信息量以及最小化坐標(biāo)設(shè)置時(shí)間。將算法與現(xiàn)有的無(wú)GPS定位算法進(jìn)行比較，在算法復(fù)雜度、信息交換量以及坐標(biāo)形成時(shí)間上有很大的改進(jìn)。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；GPS；分布式；迭代；定位

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）10-0019-03

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

A Distributed and Iteration without GPS Positioning for Sensor Networks

DING Zi-yong， CUI Yan-rong

（The Yangtz university， Jingzhou 434023， China）

Abstract： Focusing on the possible problem in wireless sensor networks that rely on beacon nodes equipped with GPS to locate nodes. Firstly， the irrationality of the algorithm based on beacon node positioning is analyzed. The use of GPS-equipped beacon nodes will increase the energy consumption of nodes，cause the problem of energy hole in wireless and shorten network lifetime. A distributed and iteration without GPS positioning algorithm is proposed. The purpose of the algorithm is reduce the dependence of the node on the hardware， to reduce the information transfer， to minimize the amount of information exchanged and to minimize the time of set coordinates. Compared with the existing GPS-free positioning algorithm， the algorithm complexity， the quantity of information exchanged and the coordinate formation time has been greatly improved.

Key words： wireless sensor networks； GPS； distributed； iteration； positioning

1 引言

無(wú)線傳感器網(wǎng)絡(luò)WSNs（wireless sensor networks）是具有空間范圍大、節(jié)點(diǎn)能量有限、存儲(chǔ)空間較小、需進(jìn)行分布式協(xié)調(diào)等特點(diǎn)的自適應(yīng)網(wǎng)絡(luò)。在大規(guī)模WSNs中為了實(shí)現(xiàn)諸如：位置感知路由、資源有效協(xié)調(diào)、削弱能量空洞、均衡網(wǎng)絡(luò)負(fù)載、降低節(jié)點(diǎn)能耗、提高網(wǎng)絡(luò)性能等功能確定節(jié)點(diǎn)位置至關(guān)重要。有許多學(xué)者針對(duì)不同應(yīng)用領(lǐng)域已經(jīng)設(shè)計(jì)出很多的WSNs節(jié)點(diǎn)定位系統(tǒng)和算法。目前關(guān)于WSNs中節(jié)點(diǎn)定位的文獻(xiàn)大多是基于信標(biāo)節(jié)點(diǎn)來(lái)定位的，預(yù)先在信標(biāo)節(jié)點(diǎn)上裝載有GPS接收器，通過(guò)接收到的GPS信號(hào)來(lái)計(jì)算出自己所在的位置。參考文獻(xiàn)[1]中從集中式和分布式定位兩個(gè)方面介紹了利用信標(biāo)節(jié)點(diǎn)進(jìn)行定位的算法。在傳感器節(jié)點(diǎn)上安裝GPS接收器使其作為信標(biāo)節(jié)點(diǎn)優(yōu)先知道位置信息這是不合理的，安裝了GPS系統(tǒng)會(huì)加快節(jié)點(diǎn)能量消耗，減少網(wǎng)絡(luò)生存期。為了減少節(jié)點(diǎn)對(duì)硬件的依賴，延長(zhǎng)網(wǎng)絡(luò)生存期本文提出一種無(wú)需GPS分布式迭代的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法。

2 典型的無(wú)信標(biāo)節(jié)點(diǎn)定位算法

參考文獻(xiàn)[3]中，作者提出了一種在移動(dòng)自組網(wǎng)中實(shí)現(xiàn)無(wú)GPS定位的分布式定位算法。該算法選擇網(wǎng)絡(luò)中節(jié)點(diǎn)密度最大處的一組節(jié)點(diǎn)作為建立全局坐標(biāo)的參考點(diǎn)，將這組節(jié)點(diǎn)中連通度最大的節(jié)點(diǎn)作為全局坐標(biāo)系的原點(diǎn)。先根據(jù)節(jié)點(diǎn)之間測(cè)得的距離在每個(gè)節(jié)點(diǎn)建立一個(gè)局部坐標(biāo)系。然后每個(gè)節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)間的信息交換將其坐標(biāo)單獨(dú)重定向到原點(diǎn)的坐標(biāo)。由于所有的節(jié)點(diǎn)都需要進(jìn)行坐標(biāo)的建立和轉(zhuǎn)換計(jì)算，因此此過(guò)程中節(jié)點(diǎn)信息交換數(shù)量大，通信開(kāi)銷需消耗大量的節(jié)點(diǎn)能量。

參考文獻(xiàn)[4]中，作者針對(duì)上述算法的缺陷，設(shè)計(jì)了一種基于分簇的無(wú)線傳感器節(jié)點(diǎn)定位算法。節(jié)點(diǎn)部署后，每個(gè)節(jié)點(diǎn)開(kāi)始遞減一個(gè)隨機(jī)計(jì)時(shí)器，如果節(jié)點(diǎn)i的計(jì)時(shí)器在任何其他節(jié)點(diǎn)與它聯(lián)系前過(guò)期，則i成為主節(jié)點(diǎn)并廣播一條將自己建立為主節(jié)點(diǎn)（main node）的消息。所有接收到i廣播消息的節(jié)點(diǎn)停止計(jì)時(shí)器成為i的從節(jié)點(diǎn)。分簇形成后在每個(gè)簇內(nèi)建立局部坐標(biāo)系。主節(jié)點(diǎn)i中的一些從節(jié)點(diǎn)也可以接收到其它主節(jié)點(diǎn)發(fā)送的消息，這些節(jié)點(diǎn)稱為邊界節(jié)點(diǎn)（border node）。局部坐標(biāo)系通過(guò)邊界節(jié)點(diǎn)向主節(jié)點(diǎn)ID小的簇進(jìn)行坐標(biāo)轉(zhuǎn)換，逐步建立一個(gè)全局的坐標(biāo)系。該算法無(wú)須每個(gè)節(jié)點(diǎn)都進(jìn)行坐標(biāo)的轉(zhuǎn)換，通信開(kāi)銷相比前面的算法開(kāi)銷更小，更適合大規(guī)模網(wǎng)絡(luò)中節(jié)點(diǎn)定位。但該算法進(jìn)行坐標(biāo)系的轉(zhuǎn)換時(shí)算法較復(fù)雜、所需時(shí)間較長(zhǎng)，本文在此基礎(chǔ)上提出限定局部坐標(biāo)系方向的算法以此來(lái)減少算法復(fù)雜度和坐標(biāo)形成時(shí)間。

3 改進(jìn)的無(wú)GPS定位算法

本文提出的算法采用分簇的方法來(lái)建立全局坐標(biāo)系。整個(gè)過(guò)程分為3個(gè)階段：簇的形成、局部坐標(biāo)系的建立、全局坐標(biāo)系的建立。

3.1 分簇

假設(shè)節(jié)點(diǎn)在給定平均密度的地理區(qū)域內(nèi)隨機(jī)部署。節(jié)點(diǎn)部署完后每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，如果節(jié)點(diǎn)i的隨機(jī)數(shù)小于閾值T （根據(jù)網(wǎng)絡(luò)規(guī)模合理設(shè)計(jì)）則i廣播一條自己是主節(jié)點(diǎn)的消息。所有接收到i廣播消息的節(jié)點(diǎn)成為節(jié)點(diǎn)i的從節(jié)點(diǎn)。主節(jié)點(diǎn)i中的一些邊界節(jié)點(diǎn)也可以從其他主節(jié)點(diǎn)哪里接收消息，利用邊界節(jié)點(diǎn)進(jìn)行坐標(biāo)的平移。當(dāng)某個(gè)節(jié)點(diǎn)的隨機(jī)數(shù)小于閾值T時(shí)就會(huì)成為主節(jié)點(diǎn)并發(fā)送M1消息，收到M1消息的其他節(jié)點(diǎn)就會(huì)成為該主節(jié)點(diǎn)的成員節(jié)點(diǎn)，當(dāng)某個(gè)節(jié)點(diǎn)接收到2個(gè)或2個(gè)以上的M1消息時(shí)，它將作為邊界節(jié)點(diǎn)。如下算法1描述節(jié)點(diǎn)分簇過(guò)程。

3.2 局部坐標(biāo)系

無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)間測(cè)距的方法有：信號(hào)強(qiáng)度法RSSI、到達(dá)角度分AOA、到達(dá)時(shí)間法TOA和到達(dá)時(shí)間差法TDOA。節(jié)點(diǎn)定位是否能夠滿足精度要求，很大程度上取決于距離測(cè)量的精度。造成測(cè)量誤差的主要原因是測(cè)量誤差和非視距誤差。參考文獻(xiàn)[5]中詳細(xì)地分析了RSSI測(cè)距技術(shù)的特點(diǎn)。本文采用RSSI來(lái)測(cè)量節(jié)點(diǎn)間的距離。

分簇完成后為了建立局部坐標(biāo)系，需獲得節(jié)點(diǎn)間的距離估計(jì)值，在本算法中采用不同類型的消息進(jìn)行通信。節(jié)點(diǎn)可以發(fā)送以下5種類型的消息：

M1： [節(jié)點(diǎn)ID， M1，消息體]，M1消息由主節(jié)點(diǎn)發(fā)送給從節(jié)點(diǎn)，告知鄰居節(jié)點(diǎn)自己將作為它的主節(jié)點(diǎn)；

M2： [節(jié)點(diǎn)ID，主節(jié)點(diǎn)ID，M2，消息體]，M2 消息讓節(jié)點(diǎn)用來(lái)測(cè)其與鄰居節(jié)點(diǎn)的距離；

M3： [節(jié)點(diǎn)ID，主節(jié)點(diǎn)ID，M3，消息體]，M3消息由從節(jié)點(diǎn)發(fā)送給主節(jié)點(diǎn)包含從節(jié)點(diǎn)到其鄰居節(jié)點(diǎn)的距離；

M4： [節(jié)點(diǎn)ID， M4，消息體]，M4消息由主節(jié)點(diǎn)發(fā)送，主要包含坐標(biāo)轉(zhuǎn)換信息；

M5： [節(jié)點(diǎn)ID，主節(jié)點(diǎn)ID， M5，消息體]，M5消息由邊界節(jié)點(diǎn)發(fā)送給主節(jié)點(diǎn)，用于查找發(fā)送感興趣消息的節(jié)點(diǎn)。

局部坐標(biāo)形成時(shí)，簇內(nèi)成員節(jié)點(diǎn)發(fā)送M2消息測(cè)量它與鄰居節(jié)點(diǎn)間的距離。當(dāng)成員節(jié)點(diǎn)j獲得到2個(gè)或2個(gè)以上的距離估計(jì)值時(shí)，j就發(fā)送M3消息將這些距離估計(jì)值發(fā)送給它的主節(jié)點(diǎn)。主節(jié)點(diǎn)收集到所有成員節(jié)點(diǎn)的距離估計(jì)值后使用三角測(cè)量法來(lái)建立局部坐標(biāo)系。簇中存在多個(gè)邊界節(jié)點(diǎn)時(shí)，主節(jié)點(diǎn)選取ID較大的邊界節(jié)點(diǎn)來(lái)建立X軸，邊界節(jié)點(diǎn)與主節(jié)點(diǎn)連線作為正X軸，主節(jié)點(diǎn)作為原點(diǎn)建立Y軸。如下算法2中描述了局部坐標(biāo)系的建立過(guò)程。

α是△pik中ip和ik的夾角。主節(jié)點(diǎn)中其他節(jié)點(diǎn)借助已經(jīng)定位的節(jié)點(diǎn)用相同的方法來(lái)定位。如圖1所示是局部坐標(biāo)系中節(jié)點(diǎn)定位示意圖。

3.3 全局坐標(biāo)系

當(dāng)所有主節(jié)點(diǎn)建立了本地坐標(biāo)系以后，通過(guò)邊界節(jié)點(diǎn)建立全局坐標(biāo)系。假設(shè)主節(jié)點(diǎn)i和j共享邊界節(jié)點(diǎn)k，在局部坐標(biāo)系建立完成后，將Y軸平移到k點(diǎn)，則此時(shí)i點(diǎn)坐標(biāo)為（dik，0），k點(diǎn)坐標(biāo)為（0，0）。坐標(biāo)發(fā)生變化后主節(jié)點(diǎn)i發(fā)送M4消息告訴從節(jié)點(diǎn)位置發(fā)生變化。從節(jié)點(diǎn)更改其坐標(biāo)。這一過(guò)程一直持續(xù)到系統(tǒng)收斂到ID最小的邊界節(jié)點(diǎn)。如圖2所示是全局坐標(biāo)系建立示意圖。

4 結(jié)論

與參考文獻(xiàn)[4]中的定位算法與本文提出的無(wú)GPS定位算法進(jìn)行分析比較。在文獻(xiàn)[4]中在形成全局坐標(biāo)系的過(guò)程中，需要借助2個(gè)邊界節(jié)點(diǎn)來(lái)測(cè)量?jī)芍鞴?jié)點(diǎn)間的距離和坐標(biāo)需要旋轉(zhuǎn)的角度，算法復(fù)雜度較高。計(jì)算出坐標(biāo)平移過(guò)程中所需的角度和距離后，主節(jié)點(diǎn)廣播這些消息，從節(jié)點(diǎn)重新進(jìn)行定位計(jì)算通信開(kāi)銷和計(jì)算開(kāi)銷都比較大。而本文提出的定位方案中，在收斂到全局坐標(biāo)系時(shí)，只需要將坐標(biāo)系Y軸進(jìn)行平移，算法復(fù)雜度低，主節(jié)點(diǎn)只需廣播其到邊界節(jié)點(diǎn)的距離即可，通信開(kāi)銷小。在形成局部坐標(biāo)系時(shí)采用隨機(jī)數(shù)的方法可以減少坐標(biāo)建立時(shí)間。綜上所述，本文提出的算法性能優(yōu)于文獻(xiàn)[4]中算法，更適合于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)定位。

參考文獻(xiàn)：

[1] 于耕，任武君.無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[J].價(jià)值工程， 2018， 37（30）：194-196.

[2] 胡鵬莎.基于DV-HOP無(wú)線傳感器的網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].電子技術(shù)與軟件工程， 2019， （2）：19-21.

[3] S. Capkun， M. Hamdi and J.-P. Hubaux， “GPS-free positioning in mobile ad-hoc networks，” Proceedings of Hawaii International Conference on System Sciences， pp. 3481-3490， Maui， HW， January 2001.

[4] R Iyengar ； B Sikdar. Scalable and distributed GPS free positioning for sensor networks[J]. IEEE International Conference on Communications ，2003 ，1 ：338-342.

[5] 詹杰，吳伶錫，唐志軍.無(wú)線傳感器網(wǎng)絡(luò)RSSI測(cè)距方法與精度分析[J].電訊技術(shù)， 2010， （4）：83-87.

[6] 蔡志強(qiáng)，谷雨，胡燏翀，許胤龍.一種無(wú)信標(biāo)無(wú)線傳感器網(wǎng)絡(luò)中的目標(biāo)定位策略[J].計(jì)算機(jī)應(yīng)用， 2007，（8）：1835-1838.

[7] 汪晗，成昂軒，王坤，等.無(wú)線傳感器網(wǎng)絡(luò)分布式迭代定位誤差控制算法[J].電子與信息學(xué)報(bào)，2018，40（1）：72-78.

[8] 郭建全，趙偉，黃松嶺.大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)分布式無(wú)錨節(jié)點(diǎn)定位算法[J].高技術(shù)通訊，2011（6）：555-561.

[9] 基于質(zhì)心迭代估計(jì)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].物理學(xué)報(bào)，2016 （3）：9-17.

【通聯(lián)編輯：梁書】