基于鄰居協(xié)助的無(wú)線傳感器網(wǎng)絡(luò)定位算法

劉巍 楊美 阮蕓星 蔡霞

摘? 要： 在無(wú)線傳感器網(wǎng)絡(luò)定位中，所有的節(jié)點(diǎn)都可以測(cè)量彼此之間的距離。由于這些測(cè)量值存在誤差，在計(jì)算節(jié)點(diǎn)位置時(shí)需要選擇合適的測(cè)量距離。首先將節(jié)點(diǎn)測(cè)量信息構(gòu)成有向圖，然后獲取從錨節(jié)點(diǎn)到盲節(jié)點(diǎn)的拓?fù)漤樞?，最后利用最小二乘法?jì)算盲節(jié)點(diǎn)的位置。在挑選有向邊時(shí)采用粒子群算法，以盲節(jié)點(diǎn)的估計(jì)位置的聯(lián)合概率為適應(yīng)度函數(shù)來(lái)評(píng)價(jià)盲節(jié)點(diǎn)的估計(jì)位置的準(zhǔn)確性，從而挑選最優(yōu)測(cè)量值作為節(jié)點(diǎn)位置。相比采用距離無(wú)關(guān)的智能定位算法，本算法的定位準(zhǔn)確度更高。

關(guān)鍵詞： 鄰居協(xié)助; 無(wú)線傳感器網(wǎng)絡(luò); 節(jié)點(diǎn)定位; 聯(lián)合概率

中圖分類號(hào)：TP212.9? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1006-8228（2020）04-18-03

Neighbor-assisted localization algorithm for wireless sensor networks

Liu Wei， Yang Mei， Ruan Yunxing， Cai Xia

（School of Computer Science， Central China Normal University， Wuhan， Hubei 430079， China）

Abstract： In wireless sensor network localization， all nodes can measure the distance between each other. Due to the errors of these measurements， it is necessary to select the appropriate measurement distances when calculating the nodes' position. The proposed method is to construct a digraph by measuring distances firstly; then to obtain the topological order from anchor node to blind node; finally， the locations of blind nodes are calculated by least square method. When selecting the directed edge， particle swarm optimization algorithm is used to evaluate the accuracy of the estimated position of the blind nodes with the joint probability of the estimated positions of the blind nodes as the fitness function. Thus， the optimal measurement value is selected as the node location. Compared with the range-free localization intelligent algorithm， this algorithm has higher accuracy.

Key words： neighbor-assisted; wireless sensor networks; node location; joint probability

0 引言

節(jié)點(diǎn)定位是無(wú)線傳感器網(wǎng)絡(luò)中的支撐技術(shù)。大多數(shù)基于無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用，例如運(yùn)輸、救援、跟蹤、環(huán)境監(jiān)測(cè)等，都需要在已知節(jié)點(diǎn)位置的基礎(chǔ)上實(shí)現(xiàn)。

目前的定位算法主要包括基于距離的定位、距離無(wú)關(guān)的定位方法?；诰嚯x的定位算法包括：極大似然估計(jì)算法[1]、智能優(yōu)化定位算法[2-4]等利用節(jié)點(diǎn)之間的距離計(jì)算未知節(jié)點(diǎn)的位置。距離無(wú)關(guān)的定位算法[5]利用節(jié)點(diǎn)之間的鄰接關(guān)系，通過(guò)平均跳距，計(jì)算節(jié)點(diǎn)的位置。這些算法通過(guò)計(jì)算錨節(jié)點(diǎn)和盲節(jié)點(diǎn)之間的距離對(duì)盲節(jié)點(diǎn)定位，如圖1（a）中所示。但是這些算法往往忽略了大量的盲節(jié)點(diǎn)所獲取的距離信息，如圖1（b）中虛線所示。這些測(cè)量距離描述了節(jié)點(diǎn)和鄰居之間的相對(duì)位置信息。本文通過(guò)粒子群算法選擇部分測(cè)量數(shù)據(jù)作為極大似然估計(jì)定位算法的依據(jù)，再利用全部測(cè)量距離評(píng)估位置未知的節(jié)點(diǎn)位置，從中選擇最優(yōu)節(jié)點(diǎn)定位結(jié)果。

1 相關(guān)技術(shù)介紹

在實(shí)際測(cè)量中，不可避免存在測(cè)量誤差。極大似然估計(jì)的方法是在已知n個(gè)錨節(jié)點(diǎn)的位置和它們測(cè)量的n個(gè)距離信息的基礎(chǔ)上，通過(guò)最小二乘法，計(jì)算未知盲節(jié)點(diǎn)的位置坐標(biāo)。記n個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)為（x1，y1）……（xn，yn），盲節(jié)點(diǎn)的位置為（x，y），錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的測(cè)量距離為d1，……dn。對(duì)定位問(wèn)題建模，可以獲得式⑴所示的方程組。

⑴

對(duì)式⑴，從第1個(gè)方程開(kāi)始依此減去最后一個(gè)方程可以得到式⑵所示的線性方程：

AX=b ⑵

其中：

⑶

因此盲節(jié)點(diǎn)的位置坐標(biāo)為：

⑷

利用極大似然估計(jì)算法對(duì)節(jié)點(diǎn)定位時(shí)，錨節(jié)點(diǎn)越多，節(jié)點(diǎn)定位越準(zhǔn)確。但是當(dāng)錨節(jié)點(diǎn)共線或者幾乎共線的時(shí)候，細(xì)微的誤差都會(huì)帶來(lái)較大的誤差[6]。因此挑選合適的錨節(jié)點(diǎn)和合適的測(cè)量距離，對(duì)于計(jì)算節(jié)點(diǎn)的位置非常重要。

2 算法介紹

本文采用粒子群優(yōu)化算法從測(cè)量距離集合中挑選最優(yōu)測(cè)量距離，然后通過(guò)極大似然估計(jì)定位算法，從錨節(jié)點(diǎn)開(kāi)始依次計(jì)算所有盲節(jié)點(diǎn)的位置。

⑴ 解空間的描述

記G=（V，D）為無(wú)線傳感器網(wǎng)絡(luò)的有向圖，其中V是節(jié)點(diǎn)集合，包含全部錨節(jié)點(diǎn)和盲節(jié)點(diǎn);D是有向邊的集合D={di，j}，代表節(jié)點(diǎn)i到節(jié)點(diǎn)j的測(cè)量距離。從集合D中挑選合適的邊計(jì)算盲節(jié)點(diǎn)的位置的問(wèn)題，本質(zhì)上是0-1背包問(wèn)題。因此將所有節(jié)點(diǎn)的測(cè)量距離依次排列，構(gòu)成列向量作為解向量，當(dāng)Si，k=1時(shí)，表示第i條有向邊選中成為有向圖中的有向邊，當(dāng)si=0時(shí)，表示沒(méi)有選中第i邊。

⑵ 粒子群算法的迭代方案

對(duì)于解向量Sk，所有挑選的有向邊可以構(gòu)成有向圖Gk=（V，Dk），判斷有向圖是否是有向無(wú)環(huán)圖。當(dāng)有向圖為有向無(wú)環(huán)圖時(shí)，利用從錨節(jié)點(diǎn)到所有盲節(jié)點(diǎn)的拓?fù)漤樞蚩梢砸来斡?jì)算所有盲節(jié)點(diǎn)的位置坐標(biāo)。

⑶ 適應(yīng)度

記單個(gè)盲節(jié)點(diǎn)i的估計(jì)坐標(biāo)，它與它所有的鄰居節(jié)點(diǎn)的估計(jì)距離為，實(shí)測(cè)距離為D={di，j}，其中j=1：ni。用聯(lián)合概率評(píng)估節(jié)點(diǎn)i的估計(jì)坐標(biāo)的準(zhǔn)確性，如式⑸。

⑸

因此，所有盲節(jié)點(diǎn)的位置的聯(lián)合概率為式⑹：

⑹

3 實(shí)驗(yàn)

為了驗(yàn)證算法的有效性， 本文采用MATLAB進(jìn)行仿真。和DV-HOP[7]，PSO-DV-HOP[8]算法進(jìn)行對(duì)比。實(shí)驗(yàn)環(huán)境是在邊長(zhǎng)為100 m的正方形區(qū)域，隨機(jī)分布100個(gè)傳感器節(jié)點(diǎn)， 其中包含錨節(jié)點(diǎn)。本文所用算法的種群規(guī)模為60， 最大迭代次數(shù)均為100， 通信半徑為30m，傳感器的測(cè)量方差為0.1m。

標(biāo)記第i個(gè)盲節(jié)點(diǎn)的實(shí)際位置為（xi，yi），估計(jì)位置為，本文采用歸一化誤差作為衡量標(biāo)準(zhǔn)，公式如下：

⑺

其中，un為盲節(jié)點(diǎn)的個(gè)數(shù)，R為傳感器節(jié)點(diǎn)的通信半徑，K為實(shí)驗(yàn)重復(fù)的次數(shù)，實(shí)驗(yàn)中K=100。

本文分別調(diào)整錨節(jié)點(diǎn)比例、節(jié)點(diǎn)數(shù)量、通信半徑進(jìn)行比較分析。仿真結(jié)果如圖2所示。實(shí)驗(yàn)顯示，錨節(jié)點(diǎn)比例越高、節(jié)點(diǎn)數(shù)量越多、通信半徑越大，節(jié)點(diǎn)的歸一化的測(cè)量誤差越小。

⑴ 錨節(jié)點(diǎn)比例與定位準(zhǔn)確性的關(guān)系

調(diào)節(jié)錨節(jié)點(diǎn)占總節(jié)點(diǎn)的比例，進(jìn)行仿真，結(jié)果如圖2（a）所示，本算法在錨節(jié)點(diǎn)的比例大于25%時(shí)趨于穩(wěn)定，歸一化誤差明顯優(yōu)于DV_HOP和BPSO_DV_HOP算法，此時(shí)歸一化誤差只有BPSO_DV_HOP算法的3%。

⑵ 節(jié)點(diǎn)數(shù)量與定位準(zhǔn)確性的關(guān)系

調(diào)節(jié)總節(jié)點(diǎn)數(shù)目，進(jìn)行仿真，結(jié)果如圖2（b）所示，本算法在總節(jié)點(diǎn)數(shù)目大于100個(gè)時(shí)，歸一化誤差明顯優(yōu)于DV_HOP和BPSO_DV_HOP算法，在總節(jié)點(diǎn)數(shù)目為150個(gè)時(shí)趨于穩(wěn)定，節(jié)點(diǎn)的歸一化誤差只有BPSO_DV_HOP算法的1.6%。

⑶ 通信半徑與定位準(zhǔn)確性的關(guān)系

調(diào)節(jié)節(jié)點(diǎn)通信半徑，進(jìn)行仿真，結(jié)果如圖2（c）所示，本算法在通信半徑大于30m時(shí)，歸一化誤差明顯優(yōu)于DV_HOP和BPSO_DV_HOP算法。當(dāng)通信半徑為35m時(shí)，算法趨于穩(wěn)定，節(jié)點(diǎn)的歸一化誤差只有BPSO_DV_HOP算法的1.4%。

4 結(jié)論

在傳感器網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)之間可以相互感知距離，這有助于節(jié)點(diǎn)的定位。因此本文利用粒子群優(yōu)化算法，鄰居協(xié)助優(yōu)化定位，獲得最優(yōu)節(jié)點(diǎn)位置坐標(biāo)。結(jié)果顯示，相比于傳統(tǒng)的僅利用基于錨節(jié)點(diǎn)的測(cè)量信息，而忽略鄰居測(cè)距的定位算法，本算法定位精度更高。

參考文獻(xiàn)（References）：

[1] Bhaskar S A. Localization From Connectivity： A 1-bit?Maximum Likelihood Approach[J].IEEE/ACM Transactions on Networking，2015.24（5）：1506-1511

[2] 曹欲曉，嚴(yán)奎，徐金寶.一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，2015.28（3）：424-429

[3] 李鵬，陳桂芬，胡文韜.基于雞群算法的無(wú)線傳感器網(wǎng)絡(luò)定位研究[J].傳感技術(shù)學(xué)報(bào)，2019.32（6）：866-871，891

[4] 段亞青，王華倩，喬學(xué)工.基于測(cè)距和灰狼優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào)，2018.31（12）：1894-1899

[5] 任克強(qiáng)，李亞杰.WSN中DV-Hop節(jié)點(diǎn)定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報(bào)，2017.30（4）：611-617

[6] 吳凌飛，孟慶虎，梁華為.一種基于共線度的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào)，2009.22（5）：722-727

[7] GuiL， Val T， Wei A， et al. Improvement of range-freelocalization technology by a novel DV-hop protocol in wireless sensor networks[J]. Ad Hoc Networks，2015.24：55-73

[8] 范時(shí)平，羅丹，劉艷林.基于跳距與改進(jìn)粒子群算法的DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào)，2016.29（9）：1410-1415