《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模擬設(shè)計(jì) > 設(shè)計(jì)應(yīng)用 > 基于分布式多跳誤差估計(jì)目標(biāo)位置感知算法
基于分布式多跳誤差估計(jì)目標(biāo)位置感知算法
2017年電子技術(shù)應(yīng)用第11期
蔣從元1，楊 杰2
1.四川職業(yè)技術(shù)學(xué)院 電子電氣工程系，四川 遂寧629000；2.湖南科技學(xué)院 電子與信息工程學(xué)院，湖南 永州425000
摘要： 為了提高定位系統(tǒng)在目標(biāo)定位上的精度，減少過(guò)多的硬件設(shè)施投入和能量成本，提出分布式多跳誤差估計(jì)的能量高效目標(biāo)位置感知算法（NFDV-Hop）。在定位精度上，DV-Hop算法采用每跳的平均距離來(lái)估計(jì)錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的距離，導(dǎo)致估計(jì)距離與真實(shí)距離存在較大誤差，而NFDV-Hop算法使用錨節(jié)點(diǎn)的平均跳數(shù)的大小以及錨節(jié)點(diǎn)間的平均跳距離，求得未知節(jié)點(diǎn)的位置坐標(biāo)，并在得到坐標(biāo)估計(jì)值后引入位置比值來(lái)減少定位誤差。在能量?jī)?yōu)化上，DV-Hop算法需向節(jié)點(diǎn)多次廣播信息，而NFDV-Hop算法所采用的錨節(jié)點(diǎn)只需向其他節(jié)點(diǎn)廣播一次自身的位置坐標(biāo)信息，從而大大減少節(jié)點(diǎn)的能量消耗。仿真結(jié)果表明，相比基于最小二乘法的DV-Hop算法以及基于改進(jìn)粒子群優(yōu)化的DV-Hop算法，NFDV-Hop定位算法的定位精度分別提高了12.1%和9%。
中圖分類號(hào)： TN93；TP393
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.171111
中文引用格式： 蔣從元，楊杰. 基于分布式多跳誤差估計(jì)目標(biāo)位置感知算法[J].電子技術(shù)應(yīng)用，2017，43(11)：95-98.
英文引用格式： Jiang Congyuan，Yang Jie. Energy efficiency target position aware algorithm with distributed multi-hop error estimates[J].Application of Electronic Technique，2017，43(11)：95-98.
Energy efficiency target position aware algorithm with distributed multi-hop error estimates
Jiang Congyuan1，Yang Jie2
1.Department of Electrical and Electronic Engineering，Sichuan Vocational and Technical College，Suining 629000，China； 2.School of Electronic and Information Engineering，Hunan University of Science and Engineering，Yongzhou 425000，China
Abstract： In order to improve the accuracy of the positioning system on the target location, and reduce excessive investment in hardware and energy costs, an energy efficiency target position aware algorithm(NFDV-Hop) is proposed. The positioning accuracy, DV-Hop algorithm uses the average distance per hop to estimate the distance between anchor nodes and unknown nodes, resulting in an estimated distance and the true distance is large error. The average jump size NFDV-Hop algorithm uses anchor nodes and the average number of hops between nodes anchors the distance, to determine position coordinates of the unknown node, and obtain the coordinates of the position after the introduction of the ratio of the estimated value to reduce the positioning error. The energy optimization, DV-Hop algorithm requires to repeatedly broadcast the node information, and the anchor node NFDV-Hop algorithm uses with a single position coordinate information itself to other nodes broadcast, thus greatly reducing the energy consumption of the node. Simulation results show that, compared DV-Hop algorithm based on least squares method and the improved particle swarm optimization based on DV-Hop algorithm, positioning accuracy NFDV-Hop localization algorithm is increased by 12.1% and 9%.
Key words : distributed multi-hop error estimation;position aware；energy efficiency；positioning accuracy

0 引言

    在無(wú)線傳感器網(wǎng)絡(luò)定位算法[1-6]的研究上，譚志等[7]提出一種基于節(jié)點(diǎn)間覆蓋關(guān)系的改進(jìn)DV-Hop算法，該方法根據(jù)兩節(jié)點(diǎn)間的通信覆蓋率引入跳數(shù)系數(shù)，降低了每跳距離產(chǎn)生的誤差，在一定程度上降低了DV-hop算法的定位誤差。趙雁航等[8]提出一種基于跳距修正粒子群優(yōu)化的WSN 定位算法，該算法通過(guò)對(duì)錨節(jié)點(diǎn)廣播的數(shù)據(jù)分組結(jié)構(gòu)進(jìn)行了改進(jìn)，來(lái)對(duì)定位誤差進(jìn)行加權(quán)處理并對(duì)定位的迭代過(guò)程進(jìn)行優(yōu)化，提高了無(wú)線傳感器網(wǎng)絡(luò)的定位精度。吳玉成等[9]提出一種基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法，該算法通過(guò)分析網(wǎng)絡(luò)節(jié)點(diǎn)分布特性得到最優(yōu)節(jié)點(diǎn)通信半徑，并獲得受擾動(dòng)影響最小的錨節(jié)點(diǎn)優(yōu)化分布方案，采用加權(quán)方法修正未知節(jié)點(diǎn)位置，改善了節(jié)點(diǎn)隨機(jī)分布的無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位性能。朱敏等[10]提出一種基于DV-HOP改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)定位算法，該算法采用新的方式計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離，提出錨節(jié)點(diǎn)信任度的概念，并利用加權(quán)最小二乘法計(jì)算節(jié)點(diǎn)坐標(biāo)。該方法在提高定位精度的同時(shí)，減少了節(jié)點(diǎn)的通信量和計(jì)算量。JIANG K等[11]提出一種基于最小二乘法和DV-Hop算法的無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)定位算法，移動(dòng)信標(biāo)節(jié)點(diǎn)引入DV-Hop，允許在預(yù)先安排的方式下移動(dòng)信標(biāo)節(jié)點(diǎn)，并連續(xù)廣播其位置信息，形成多個(gè)虛擬信標(biāo)。該算法可以減少網(wǎng)絡(luò)的定位成本和復(fù)雜性。ZHANG Q G等[12]提出一種基于改進(jìn)粒子群優(yōu)化算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法，通過(guò)將DV-Hop算法和簡(jiǎn)單的粒子群優(yōu)化（tsPSO）算法結(jié)合在一起，該算法迭代地搜索未知節(jié)點(diǎn)，抑制對(duì)定位精度的距離估計(jì)誤差，可以實(shí)現(xiàn)比DV-Hop算法更高的定位精度[13-15]。

1 NFDV-Hop定位算法

    為了減少計(jì)算中的傳播誤差和提高定位精度，通過(guò)劃分最接近錨節(jié)點(diǎn)的距離方程，未知節(jié)點(diǎn)再通過(guò)從方程組利用獲得的信息更新位置信息。步驟如下：

    (1)在這個(gè)步驟中，每個(gè)錨節(jié)點(diǎn)廣播信標(biāo)包與它的位置（坐標(biāo)）并且跳數(shù)的值初始化為1。當(dāng)節(jié)點(diǎn)接收到信標(biāo)數(shù)據(jù)包，將生成一個(gè)表(xi，yi，n(hop))，這個(gè)表代表著節(jié)點(diǎn)所接收到的每個(gè)錨節(jié)點(diǎn)的位置坐標(biāo)以及跳數(shù)信息。如果接收到的數(shù)據(jù)包中關(guān)于達(dá)到一個(gè)特定的錨節(jié)點(diǎn)是包含較少的跳數(shù)值，則表中的跳數(shù)值被替換為收到的數(shù)據(jù)包的跳數(shù)值，并且在網(wǎng)絡(luò)中如果數(shù)據(jù)包被轉(zhuǎn)發(fā)，則跳數(shù)值增加1，否則該數(shù)據(jù)包將被丟棄。通過(guò)這種機(jī)制，網(wǎng)絡(luò)中的所有未知節(jié)點(diǎn)從每個(gè)錨節(jié)點(diǎn)獲得錨節(jié)點(diǎn)的坐標(biāo)和最小的跳數(shù)值。

    (2)未知節(jié)點(diǎn)從步驟(1)中獲得的錨節(jié)點(diǎn)的坐標(biāo)后，未知節(jié)點(diǎn)計(jì)算錨節(jié)點(diǎn)跳數(shù)的大小，在這里假設(shè)節(jié)點(diǎn)的通信范圍為R，用d(i，j)表示節(jié)點(diǎn)i到錨節(jié)點(diǎn)j的歐幾里得距離，由于節(jié)點(diǎn)的跳距離是一定小于其通信距離，因此節(jié)點(diǎn)到錨節(jié)點(diǎn)所需的最小跳數(shù)為：

    tx3-gs1.gif

    計(jì)算跳數(shù)后，未知節(jié)點(diǎn)使用跳數(shù)和錨節(jié)點(diǎn)之間的信息距離計(jì)算出錨節(jié)點(diǎn)的跳距離。為了使跳距離更加接近于實(shí)際跳距離的大小，未知節(jié)點(diǎn)采取錨節(jié)點(diǎn)之間的平均距離之比以及平均跳數(shù)來(lái)計(jì)算跳距離，得到：

tx3-gs2-4.gif

    而錨節(jié)點(diǎn)每一跳所產(chǎn)生的誤差，則與跳數(shù)以及錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j之間的距離有關(guān)：

tx3-gs5-7.gif

    一旦未知節(jié)點(diǎn)計(jì)算平均跳數(shù)的大小，則開始通過(guò)使用平均跳距離和各自的錨節(jié)點(diǎn)的最小跳數(shù)來(lái)估計(jì)與錨節(jié)點(diǎn)的距離，未知節(jié)點(diǎn)估計(jì)與第i個(gè)錨節(jié)點(diǎn)的距離為：

    tx3-gs8.gif

    通過(guò)每一次的距離劃分來(lái)得到最接近錨節(jié)點(diǎn)真實(shí)距離的距離方程，假設(shè)第j個(gè)錨節(jié)點(diǎn)是最接近未知節(jié)點(diǎn)的錨節(jié)點(diǎn)i，首先得到距離的劃分方程為：

tx3-gs9-13.gif

tx3-gs14.gif

2 實(shí)驗(yàn)仿真及分析

    在仿真實(shí)驗(yàn)中主要進(jìn)行定位誤差和計(jì)算成本的分析，算法是在Matlab7.0仿真軟件上進(jìn)行編程和運(yùn)行，在模擬的仿真環(huán)境中，包括了對(duì)100個(gè)隨機(jī)生成的傳感器節(jié)點(diǎn)部署，并且模擬的部署環(huán)境為一個(gè)面積為200×200的區(qū)域，每個(gè)節(jié)點(diǎn)都具有50 m的通信半徑，在仿真中，定位誤差定義為：

tx3-gs15.gif

    為了更好地驗(yàn)證本文所提出算法的性能，在實(shí)驗(yàn)中分別與文獻(xiàn)[11]的基于最小二乘法的DV-Hop算法以及文獻(xiàn)[12]的基于改進(jìn)粒子群優(yōu)化的DV-Hop算法進(jìn)行了對(duì)比，并得到了仿真結(jié)果的比較圖。

    圖1定位誤差是衡量定位算法性能的關(guān)鍵，為了驗(yàn)證算法的定位誤差情況，實(shí)驗(yàn)中在初始的節(jié)點(diǎn)數(shù)量的情況下增加節(jié)點(diǎn)數(shù)量，從初始的100個(gè)節(jié)點(diǎn)增加到300個(gè)，并得到在節(jié)點(diǎn)數(shù)量增加的過(guò)程中算法的定位誤差情況。從圖1的結(jié)果可以看出，節(jié)點(diǎn)數(shù)量越多，定位誤差越小，這是由于節(jié)點(diǎn)數(shù)量增多后，節(jié)點(diǎn)間的距離計(jì)算的誤差就相對(duì)減小，因此定位精度變高。從與基于最小二乘法的DV-Hop算法以及基于改進(jìn)粒子群優(yōu)化的DV-Hop算法的對(duì)比情況可以看出，本文方法的定位誤差保持在27.5%以下，定位誤差最低時(shí)僅為5.7%。而對(duì)比算法的定位誤差最低時(shí)分別為17.8%和14.7%。因?yàn)榛谧钚《朔ǖ腄V-Hop算法以及基于改進(jìn)粒子群優(yōu)化的DV-Hop算法都是專注于修改其估計(jì)平均跳距離，通過(guò)減小平均跳距離誤差來(lái)提高未知節(jié)點(diǎn)距離的估算精度，再通過(guò)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的位置關(guān)系來(lái)實(shí)現(xiàn)坐標(biāo)定位。然而平均跳距離作為估算距離始終存在一定的誤差，因此提高精度的能力有限。而NFDV-Hop算法除了通過(guò)多個(gè)錨節(jié)點(diǎn)的平均距離之比以及各自的錨節(jié)點(diǎn)的最小跳數(shù)來(lái)提高的平均跳距離的估算精度，而且估計(jì)的跳距離采用距離的劃分方程來(lái)得到未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，并引入位置比值來(lái)提高位置坐標(biāo)的估算精度。

tx3-t1.gif

    為了驗(yàn)證算法的節(jié)能性能，在實(shí)驗(yàn)中通過(guò)逐漸增加節(jié)點(diǎn)數(shù)量，得到網(wǎng)絡(luò)的平均節(jié)點(diǎn)能耗情況。從圖2的結(jié)果可以看出，本文的平均節(jié)點(diǎn)能耗相比對(duì)比算法少了很多，最高時(shí)僅為0.768 J，最低時(shí)為0.529 J，而兩種對(duì)比算法的最低平均節(jié)點(diǎn)能耗則分別為0.754 J和0.696 J，因此相比之下本文算法的節(jié)能性能更加顯著。

tx3-t2.gif

    當(dāng)錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí)，意味著可以用來(lái)作為距離測(cè)量的錨節(jié)點(diǎn)數(shù)量增多，即定位精度會(huì)有一定提升。該組實(shí)驗(yàn)即在錨節(jié)點(diǎn)占比提升的情況下，驗(yàn)證算法的定位誤差。從圖3的結(jié)果可以看出，3種算法的定位誤差都隨著錨節(jié)點(diǎn)占比的提升而減少，定位精度有所提升。從曲線的分布情況來(lái)看，定位誤差最低的為本文的NFDV-Hop定位算法，其次為改進(jìn)粒子群優(yōu)化的DV-Hop算法，而基于最小二乘法的DV-Hop算法的定位誤差最高。

tx3-t3.gif

    圖4為錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí)的平均節(jié)點(diǎn)能耗情況，由于本文算法的錨節(jié)點(diǎn)只需廣播一次自身的位置信息，因此錨節(jié)點(diǎn)占比的提升，意味著節(jié)點(diǎn)的總的通信成本降低，即平均節(jié)點(diǎn)能耗也降低。因此在錨節(jié)點(diǎn)在總的節(jié)點(diǎn)數(shù)量的占比增加時(shí)，本文算法的平均節(jié)點(diǎn)能耗的降低趨勢(shì)較為明顯，而另外兩種算法的能耗降低并不多，在錨節(jié)點(diǎn)占比為30%，本文算法的平均節(jié)點(diǎn)能耗為0.706 J，另外兩種算法分別為0.842 J和0.805 J。因?yàn)榛谧钚《朔ǖ腄V-Hop算法在廣播消息上與DV-Hop算法相同，并沒有起到節(jié)能效果，而基于改進(jìn)粒子群優(yōu)化的DV-Hop算法需要多次迭代，節(jié)能效果不理想。而NFDV-Hop定位算法專注于減小通信成本，通過(guò)有效減少信息的廣播次數(shù)減少節(jié)點(diǎn)的能量消耗，從實(shí)驗(yàn)結(jié)果來(lái)看起到了一定的效果。

tx3-t4.gif

3 結(jié)論

    本文提出了一種分布式多跳誤差估計(jì)的能量高效目標(biāo)位置鎖定算法，該算法在DV-Hop算法的基礎(chǔ)上，針對(duì)DV-Hop算法定位精度不高、通信成本較大的問(wèn)題，采用節(jié)能非測(cè)距優(yōu)化方法，錨節(jié)點(diǎn)只需廣播一次自身位置坐標(biāo)信息，有效減少通信能耗。使用錨節(jié)點(diǎn)的平均跳數(shù)的大小以及錨節(jié)點(diǎn)間的平均跳距離來(lái)求得未知節(jié)點(diǎn)的位置坐標(biāo)。在實(shí)驗(yàn)中，通過(guò)驗(yàn)證和對(duì)比的方法來(lái)體現(xiàn)本文算法在減小定位誤差和能量消耗上的有效性。

參考文獻(xiàn)

[1] YU C B，YU L，TAN J，et al.DV-Hop localization algorithm in WSN based on weighted of correction in hop distance[J].Applied Mechanics and Materials，2013，303：143-148.

[2] GUO Z，MIN L，LI H，et al.Improved DV-Hop localization algorithm based on RSSI value and hop correction[M].Advances in Wireless Sensor Networks.Springer Berlin Heidelberg，2013：97-102.

[3] CHAO J，HAN G，ZHU C，et al.Performance evaluation of DV-hop localization algorithm with mobility models for Mobile Wireless Sensor Networks[C].Wireless Communications and Mobile Computing Conference(IWCMC)，2013 9th International.IEEE，2013：1827-1832.

[4] HU Y，LI X.An improvement of DV-Hop localization algorithm for wireless sensor networks[J].Telecommunication Systems，2013，53(1)：13-18.

[5] ZHANG J，WANG H B，QIAO X G，et al.Node localization algorithm based on DV-HOP in wireless sensor networks[J].Applied Mechanics and Materials，2014，440：289-292.

[6] KUMAR S，LOBIYAL D K.Improvement over DV-Hop localization algorithm for wireless sensor networks[J].World Academy of Sciences, Engineering and Technology，2013：282-292.

[7] 譚志，張卉.基于節(jié)點(diǎn)間覆蓋關(guān)系的改進(jìn)DV-Hop算法[J].北京郵電大學(xué)學(xué)報(bào)，2014，37(1)：35-38.

[8] 趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優(yōu)化的WSN定位算法[J].通信學(xué)報(bào)，2013，34(9)：105-114.

[9] 吳玉成，李江雯.基于最優(yōu)節(jié)點(diǎn)通信半徑的改進(jìn)DV-Hop定位算法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，40(6)：36-41.

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

[11] JIANG K，YAO L，F(xiàn)ENG J.Wireless sensor networks target localization based on least square method and DV-Hop algorithm[J].Journal of Networks，2014，9(1)：176-182.

[12] ZHANG Q G，CHENG M.A node localization algorithm for wireless sensor network based on improved particle swarm optimization[M].Mechatronics and Automatic Control Systems.Springer International Publishing，2014：135-144.

[13] CHANDRASEKHAR V，SEAH W K G，CHOO Y S，et al.Localization in underwater sensor networks：survey and challenges[C].Proceedings of the 1st ACM international workshop on Underwater networks.ACM，2006：33-40.

[14] LIN J Z，LIU H，LI G，et al.Study for improved DV-Hop localization algorithm in WSN[J].Application Research of Computers，2009，26(4)：1272-1274.

[15] WANG Y，WANG X，WANG D，et al.Range-free localization using expected hop progress in wireless sensor networks[J].Parallel and Distributed Systems，IEEE Transactions on，2009，20(10)：1540-1552.

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。