基于跳距修正L-M優(yōu)化的WSN定位算法

喬 欣，史良馬，楊漢生，丁恩杰，王正創(chuàng)

(1.巢湖學(xué)院 機(jī)械與電子工程學(xué)院，安徽 巢湖 238000；2.中國(guó)礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇 徐州 221008)

基于跳距修正L-M優(yōu)化的WSN定位算法

喬 欣1，史良馬1，楊漢生1，丁恩杰2，王正創(chuàng)1

(1.巢湖學(xué)院 機(jī)械與電子工程學(xué)院，安徽 巢湖 238000；2.中國(guó)礦業(yè)大學(xué) 物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇 徐州 221008)

針對(duì)DV-Hop定位算法在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)洵h(huán)境下存在誤差較大的問(wèn)題，文中通過(guò)分析平均跳距估計(jì)、未知節(jié)點(diǎn)坐標(biāo)估計(jì)區(qū)域求解對(duì)定位精度的影響，提出了一種基于跳距修正L-M優(yōu)化的WSN定位算法CLDV-Hop(Correct L-M DV-Hop)；仿真結(jié)果表明，在不增加額外開(kāi)銷且仿真環(huán)境相同的條件下，CLDV-Hop算法比現(xiàn)有改進(jìn)的算法具有更高的定位精度，與DV-Hop算法相比精度提高了約33%～41%。

WSN；跳距修正；L-M優(yōu)化

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由布撒在區(qū)域內(nèi)能夠感知、處理、傳輸環(huán)境信息的大量傳感器節(jié)點(diǎn)組成，通常被用于環(huán)境監(jiān)測(cè)、醫(yī)療服務(wù)、軍事偵查、工業(yè)診斷、智能空間等領(lǐng)域[1]。不管是何領(lǐng)域，缺少目標(biāo)或傳感器節(jié)點(diǎn)位置信息的研究都是無(wú)意義的。因此，節(jié)點(diǎn)定位技術(shù)成為WSN中的重要研究課題。

目前，較為成熟的GPS定位系統(tǒng)可以實(shí)現(xiàn)WSN的節(jié)點(diǎn)定位，但考慮到價(jià)格、體積、能耗及環(huán)境等因素，故不可能大規(guī)模地布置[2]。許多研究者針對(duì)無(wú)需GPS模塊提出了各種定位算法，根據(jù)定位機(jī)制可劃分為基于測(cè)距的定位算法(Range-Based)和與距離無(wú)關(guān)的定位算法(Range-Free)[3]。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或者角度信息，常用的測(cè)距技術(shù)有RSSI、TOA、TDOA、AOA。后者僅根據(jù)網(wǎng)絡(luò)的連通性等信息即可實(shí)現(xiàn)定位[4]。如質(zhì)心算法、凸規(guī)劃算法、APIT算法及DV-Hop算法等[5]。Range-Based對(duì)硬件要求較高，并且需要多次測(cè)量來(lái)獲得合理的定位精度，所以計(jì)算量和通信開(kāi)銷很大。Range-Free定位機(jī)制憑借其在成本、功耗、復(fù)雜度等方面的優(yōu)勢(shì)，被廣泛應(yīng)用在大WSN。

DV-Hop是一種典型的無(wú)需測(cè)距定位算法，實(shí)現(xiàn)簡(jiǎn)單、定位精度較高[5]。但是，在節(jié)點(diǎn)隨機(jī)分布的WSN中，該算法的定位精度仍然不足[6]，故針對(duì)該算法精度、穩(wěn)定性、效率等存在的問(wèn)題，很多學(xué)者提出了相應(yīng)的改進(jìn)方案。文獻(xiàn)[7]提出利用三角不等式對(duì)未知節(jié)點(diǎn)到多跳錨節(jié)點(diǎn)的距離進(jìn)行約束，同時(shí)采用加權(quán)雙曲線進(jìn)行定位；文獻(xiàn)[8]提出用全新的方法計(jì)算錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離、利用加權(quán)最小二乘法進(jìn)行定位計(jì)算。本文提出了CLDV-Hop算法，并且與文獻(xiàn)[7]、文獻(xiàn)[8]中所述算法進(jìn)行仿真分析，結(jié)果表明，在節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，CLDV-Hop算法具有更高的定位精度與穩(wěn)定性。

1 算法描述與誤差分析

1.1 DV-Hop算法

DV-Hop算法的定位過(guò)程如下：

Step1 錨節(jié)點(diǎn)廣播自身信息并計(jì)算平均跳距[9]。錨節(jié)點(diǎn)將自身信息以數(shù)據(jù)包的格式廣播至網(wǎng)絡(luò)的所有節(jié)點(diǎn)。由圖1網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)淇芍^節(jié)點(diǎn)i,j之間的跳數(shù)為hij=3，未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)i的跳數(shù)為hip=3。

已知錨節(jié)點(diǎn)的坐標(biāo)(x,y)與錨節(jié)點(diǎn)間的跳數(shù)h，那么可以根據(jù)公式(1)計(jì)算出每個(gè)錨節(jié)點(diǎn)的平均跳距HS。

(1)

Step3 定位階段。如果網(wǎng)絡(luò)中未知節(jié)點(diǎn)能夠收到三個(gè)或者三個(gè)以上錨節(jié)點(diǎn)的信息，則可以執(zhí)行三邊定位法或最大似然估計(jì)法求解未知節(jié)點(diǎn)的坐標(biāo)。

假設(shè)待求未知節(jié)點(diǎn)p坐標(biāo)為(x,y)，第i個(gè)錨節(jié)點(diǎn)的坐標(biāo)記為(xi,yi)，節(jié)點(diǎn)p到錨節(jié)點(diǎn)i的距離記為di。若WSN中有m個(gè)錨節(jié)點(diǎn)能夠與未知節(jié)點(diǎn)p通信，則未知節(jié)點(diǎn)p的坐標(biāo)可以根據(jù)式(2)方程組估計(jì)得出。

(2)

上述方程組可以轉(zhuǎn)化為AX=b的形式。

方程AX=b利用最小二乘法解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)為：

X=(ATA)-1ATb

(3)

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2 CLDV-Hop算法

本節(jié)中，在不增加網(wǎng)絡(luò)通信量、硬件開(kāi)銷，不改變DV-Hop算法過(guò)程的條件下，本文對(duì)平均跳距和定位估計(jì)兩個(gè)方面進(jìn)行了改進(jìn)。

2.1 平均跳距修正

DV-Hop算法中獲得較為合理的平均跳距是保證定位精度的關(guān)鍵，本節(jié)，從兩個(gè)方面對(duì)平均跳距進(jìn)行修正，具體步驟如下：

1)節(jié)點(diǎn)在定位過(guò)程中，網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布，當(dāng)通信半徑r一定時(shí)，在節(jié)點(diǎn)分布的局部區(qū)域可能會(huì)形成“空洞”，使得距離一定的錨節(jié)點(diǎn)之間的跳數(shù)值可能變大，這就導(dǎo)致求解平均跳距誤差變大[10]。本文首先設(shè)定錨節(jié)點(diǎn)的跳數(shù)閾值δ，當(dāng)hij>δ時(shí)，令hij=0，dij=0。

2)在估計(jì)未知節(jié)點(diǎn)的坐標(biāo)時(shí)，未知節(jié)點(diǎn)將最先接收到錨節(jié)點(diǎn)平均跳距的信息作為其平均跳距。就整個(gè)節(jié)點(diǎn)非均勻分布的網(wǎng)絡(luò)而言，不足以表示整個(gè)網(wǎng)絡(luò)的平均跳距，可能會(huì)引起局部的定位精度偏差很大，使得整個(gè)網(wǎng)絡(luò)的定位精度不穩(wěn)定。因此，綜合考慮多個(gè)錨節(jié)點(diǎn)的平均跳距，能夠提高整個(gè)網(wǎng)絡(luò)的定位精度。

假設(shè)有m個(gè)錨節(jié)點(diǎn)，結(jié)合公式(1)，錨節(jié)點(diǎn)j平均跳距的修正因子?j可表示為：

(4)

2.2 基于L-M法優(yōu)化的定位估計(jì)

在DV-Hop算法中，如果能夠確定3個(gè)或者3個(gè)以上錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離，則可以通過(guò)三邊或者多邊定位法對(duì)未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行估計(jì)[11]。事實(shí)上，盡管通過(guò)平均跳距的修正，未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的跳段距離的估計(jì)也總是存在誤差，因?yàn)槎噙叾ㄎ环▽?duì)測(cè)距誤差敏感，當(dāng)測(cè)距誤差較大時(shí)，通過(guò)多邊定位法計(jì)算出的估計(jì)坐標(biāo)與真實(shí)坐標(biāo)之間存在更大的偏差，另外，在仿真過(guò)程中發(fā)現(xiàn)，當(dāng)ATA為病態(tài)矩陣時(shí)，通過(guò)多邊定位法所估計(jì)出的未知節(jié)點(diǎn)坐標(biāo)不僅誤差很大，而且定位精度的穩(wěn)定性較差，有時(shí)甚至得出錯(cuò)誤的結(jié)果[9]。

本文采用多邊定位法和L-M算法相結(jié)合的算法求解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，即首先通過(guò)多邊定位法獲得未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，然后把估計(jì)值作為L(zhǎng)-M算法的初值，進(jìn)一步對(duì)未知節(jié)點(diǎn)坐標(biāo)迭代求精。圖2畫出了錨節(jié)點(diǎn)為10時(shí)，其中一個(gè)未知節(jié)點(diǎn)的估計(jì)區(qū)域。

圖2 未知節(jié)點(diǎn)估計(jì)區(qū)域

從式(2)中可以看出，該方程組為超定方程組。因此，將式(2)轉(zhuǎn)換成：

(5)

式中，X為未知節(jié)點(diǎn)坐標(biāo)(x,y)，r(X)為殘差函數(shù)。

由此可將求解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)轉(zhuǎn)化為求式(5)的無(wú)約束極小平方和問(wèn)題，即minF(X)。L-M法在處理非線性最小二乘優(yōu)化問(wèn)題上具有明顯的優(yōu)勢(shì)，本文中選用L-M法進(jìn)行優(yōu)化。

L-M算法的迭代公式可以表示為：

(6)

其中：X(0)為通過(guò)式(4)求得未知節(jié)點(diǎn)的最小二乘解求的坐標(biāo)初值(x,y)，k為迭代變量，μ為阻尼參數(shù)，μ>0。r(X(k))為：

r(X(k))=(r1(X(k)),(r2(X(k)),…,(rm(X(k)))

J(X(k))為殘差函數(shù)r(X)在X(k)處一階導(dǎo)數(shù)組成的雅克比矩陣：

(7)

2.3CLDV-Hop定位算法的過(guò)程

CLDV-Hop算法步驟如下：

Step1:網(wǎng)絡(luò)初始化。同時(shí)給出文中仿真相關(guān)變量，如下表所示。

表1 仿真變量及參數(shù)設(shè)置

Step2:錨節(jié)點(diǎn)通過(guò)洪泛廣播的方式發(fā)送信息，包括自身ID、坐標(biāo)、跳數(shù)。

Step3:最短路徑算法計(jì)算節(jié)點(diǎn)間跳數(shù)、根據(jù)式(1)計(jì)算每個(gè)錨節(jié)點(diǎn)的平均跳距Dhop(AnchorAmount,1)并廣播至網(wǎng)絡(luò)、未知節(jié)點(diǎn)從最近的3個(gè)錨節(jié)點(diǎn)獲得加權(quán)平均跳距UNWDhop(UNAmount,1)，通過(guò)跳數(shù)與平均跳距的乘積估算出未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離DAll(AnchorAmount,UNAmount)。

Step6:通過(guò)平均定位誤差、歸一化平均定位誤差、均方根誤差對(duì)CLDV-Hop算法進(jìn)行評(píng)價(jià)。

3 仿真與實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)后算法的性能，本文利用MATLAB 2010b平臺(tái)對(duì)文中提出的CLDV-Hop定位算法進(jìn)行仿真分析，并同有關(guān)方法進(jìn)行了比較。仿真環(huán)境區(qū)域大小為100 m×100 m，并在該區(qū)域內(nèi)隨機(jī)放置100個(gè)節(jié)點(diǎn)，圖3為網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布圖。其他仿真參數(shù)參考表1。

圖3 網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布圖

圖4仿真了錨節(jié)點(diǎn)數(shù)20、通信半徑30時(shí)， DV-Hop和CLDV-Hop對(duì)未知節(jié)點(diǎn)定位的偏差。從圖中可以看出，改進(jìn)后算法的定位精度明顯比DV-Hop算法精度高的多。

圖4 未知節(jié)點(diǎn)定位偏差圖

圖5、6中分別對(duì)比了文獻(xiàn)[7]通過(guò)加權(quán)雙曲線定位算法(記為WDV-Hop)、文獻(xiàn)[8]采用新的方式計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)距離的算法(記為NDV-Hop)及傳統(tǒng)DV-Hop算法，仿真了幾種算法歸一化平均定位誤差與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的關(guān)系。圖5中設(shè)置通信半徑為20，錨節(jié)點(diǎn)為15個(gè)，從圖中可以看出，隨著網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加，文中提出的CLDV-Hop算法歸一化平均定位誤差更低。圖6中設(shè)置通信半徑為30，錨節(jié)點(diǎn)數(shù)為15個(gè)，從圖中可以看出，節(jié)點(diǎn)總數(shù)為150個(gè)時(shí)，DV-Hop算法歸一化誤差為0.321 4，NDV-Hop算法約為0.240 8，WDV-Hop算法約為0.231 7，而文中提出的CLDV-Hop算法僅為0.198 7。從圖5、6對(duì)比可以看出，通信半徑取值不同對(duì)定位精度影響較大，每個(gè)無(wú)線傳感網(wǎng)絡(luò)中都存在一個(gè)最優(yōu)通信半徑的問(wèn)題，實(shí)際應(yīng)用中要多次測(cè)試選擇最優(yōu)的通信半徑。

圖5 通信半徑為20時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)對(duì)定位誤差的影響

圖6 通信半徑為30時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)對(duì)定位誤差的影響

4 結(jié)論

本文提出了一種基于跳距修正L-M優(yōu)化的WSN定位算法，能夠應(yīng)用在節(jié)點(diǎn)隨機(jī)分布的大型無(wú)線傳感器網(wǎng)絡(luò)定位監(jiān)測(cè)，如地質(zhì)災(zāi)害監(jiān)測(cè)、水質(zhì)污染監(jiān)測(cè)、森林火災(zāi)監(jiān)測(cè)等。文中通過(guò)對(duì)平均跳距、定位計(jì)算兩個(gè)方面分別進(jìn)行改正，通過(guò)仿真

實(shí)驗(yàn)可以得出本文算法定位精度更高，是一種簡(jiǎn)單高效的WSN非測(cè)距定位算法。

[1]賈 琦，周新志.基于無(wú)線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進(jìn)和研究[J].計(jì)算機(jī)測(cè)量與控制,2013,21(11)：3043-3046.

[2] Capkun S, Hamdi M, Hubaux J P. GPS-free positioning in mobile Ad-Hoc networks[A]. Proc. Hawaii Int. Conf. on System Sciences[C]. Maui, HW, USA, 2001：3481-3490.

[3] 石為人,賈傳江,梁煥煥.一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2011,24(1):83-87.

[4] Girod L, Bychkovskiy V, Elson J. Locating tiny sensors in time and space: A case study[A]. Proceedings of the 2002 IEEE International Conference on Computer Design[C]. Freiburg (Germany) , 2002: 214-219.

[5] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems, 2003, 22(1-4):267-280.

[6] He T, Huang C D, Blum B M, et al. Range-Free Localization Schemes for Large Scale Sensor Networks[A]. Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking[C]. San Diego, United states，2003:81-95.

[7] 周 玲,康志偉,何怡剛.基于三角不等式的加權(quán)雙曲線定位DV-HOP算法[J].電子測(cè)量與儀器學(xué)報(bào),2013,27(5)：389-395.

[8] 朱 敏，劉昊霖，張志宏,等.一種基于DV-HOP改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版)，2012，44(1)：93-98.

[9] 喬 欣，常 飛，丁恩杰,等.基于跳距修正的WSN擬牛頓迭代定位算法[J].傳感技術(shù)學(xué)報(bào)，2014,27(6)：797-801.

[10]Ding E J, Qiao X, Chang F. Iterative algorithm for Quasi-Newton in WSN based on modifying average hopping distances[J]. WIT Transactions on Engineering Sciences, 2014(87):589-596.

[11] Ding E J, Qiao X, Chang F. Improved weighted Centroid localization algorithm based on RSSI differential correction[J]. International Journal on Smart Sensing and Intelligent Systems, 2014,7(3):1156-1173.

Iterative Algorithm for L-M in WSN Based on Modifying Average Hopping Distances

Qiao Xin1, Shi Liangma1, Yang Hansheng1, Ding Enjie2，Wang Zhengchuang1

(1.School of Mechanical and Electrical Engineering, Chaohu University, Chaohu 238000, China；2.CUMT-IoT Perception Mine Research Center，Xuzhou 221008，China)

Aiming at the existing large errors of the DV—Hop localization algorithm in network topology nodes distributed randomly, the passage try to solve the position accuracy by analyzing the estimate of the average hop and the unknown node coordinates region, proposed a CLDV-Hop algorithm in WSN based on modifying average hopping distances. The simulation results show that, without increasing the overhead and the same conditions as the simulation environment, CLDV-Hop algorithm has higher positioning accuracy than existing improved algorithms, and compared with DV-Hop algorithm accuracy is improved by about 33%～41%.

WSN; average hop distance correction; L-M optimization

2016-07-15；

2016-09-22。

安徽省高校省級(jí)科學(xué)研究重點(diǎn)項(xiàng)目(KJ2012A203);巢湖學(xué)院校級(jí)項(xiàng)目(XLY-201603)。

喬 欣(1988-)，女，安徽宿州人，碩士，助教，主要從事無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)，ZigBee技術(shù)等方向的研究。

1671-4598(2017)02-0116-04

10.16526/j.cnki.11-4762/tp.2017.02.032

TP393

A