丁自詠 崔艷榮

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

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

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

文章編號：1009-3044（2019）10-0019-03

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

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

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

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

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

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

3.1 分簇

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

3.2 局部坐標(biāo)系

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

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

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

M2： [節(jié)點ID，主節(jié)點ID，M2，消息體]，M2 消息讓節(jié)點用來測其與鄰居節(jié)點的距離；

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

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

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

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

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

3.3 全局坐標(biāo)系

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

4 結(jié)論

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

參考文獻(xiàn)：

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

[2] 胡鵬莎.基于DV-HOP無線傳感器的網(wǎng)絡(luò)節(jié)點定位算法[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ǎng)絡(luò)RSSI測距方法與精度分析[J].電訊技術(shù)， 2010， （4）：83-87.

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

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

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

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

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