基于MPSO-DV-Hop的無線傳感器節(jié)點定位

周天綺，姜鳳茹

1.浙江長征職業(yè)技術(shù)學(xué)院 計算機(jī)與信息技術(shù)系，杭州 310023 2.河南牧業(yè)經(jīng)濟(jì)學(xué)院 應(yīng)用電子系，鄭州 450044

基于MPSO-DV-Hop的無線傳感器節(jié)點定位

周天綺1，姜鳳茹2

1.浙江長征職業(yè)技術(shù)學(xué)院 計算機(jī)與信息技術(shù)系，杭州 310023 2.河南牧業(yè)經(jīng)濟(jì)學(xué)院 應(yīng)用電子系，鄭州 450044

當(dāng)前無線傳感器網(wǎng)絡(luò)中的節(jié)點定位技術(shù)研究具有重要的理論和實際意義[1]，針對無線傳感器網(wǎng)絡(luò)節(jié)點定位問題，國內(nèi)外學(xué)者進(jìn)行了大量研究，主要有基于測距和免測距兩類傳感器節(jié)點定位算法[2]。測距算法需要利用距離或者角度信息進(jìn)行節(jié)點定位，主要有RSSI、TOA、TDOA、AOA等定位算法，它們定位精度高，但功耗大、成本高，不適合用于低功耗、低成本的應(yīng)用領(lǐng)域[3-5]。免測距算法根據(jù)網(wǎng)絡(luò)的連通性來實現(xiàn)節(jié)點的定位，主要有質(zhì)心算法、DV-Hop算法等，它們借助硬件設(shè)備少，計算簡單，但定位精度低[6-8]。DV-Hop算法是一種應(yīng)用最廣泛的免測距算法，針對其定位精度較低的問題，許多學(xué)者對其進(jìn)行了改進(jìn)，如引入了全網(wǎng)平均跳距以減少每跳距離與實際距離間的誤差；采用遺傳算法、模擬退火算法、蛙跳算法、粒子群算法對DV-Hop算法的誤差進(jìn)行校正，一定程度上提高了DV-Hop算法的定位精度[9-11]。在這些算法中，粒子群算法具有參數(shù)少、搜索能力強(qiáng)等優(yōu)點，與DV-Hop算法廣泛應(yīng)用于傳感器節(jié)點定位。但在實際應(yīng)用中，PSO算法存在一些不足，如在迭代后期，種群多樣性降低，易陷入局部最優(yōu)[12]。為了解決DV-hop算法定位精度低的難題，本文提出了一種多子群粒子群算法（Multi-subpopulation Particle Swarm Optimization algorithm，MPSO）優(yōu)化DV-Hop的無線傳感器節(jié)點定位（MPSO-DV-Hop）。實驗結(jié)果表明，MPSO-DV-Hop提高了傳感器節(jié)點定位精度，定位誤差小，拓寬了WSN應(yīng)用的范圍。

1 DV-Hop定位算法

根據(jù)距離矢量和GPS定位原理，2001年，Nieuleseu等人提出了DV-Hop傳感器節(jié)點定位算法，其只包含少數(shù)信標(biāo)節(jié)點，剩余節(jié)點為未知節(jié)點，需要通過定位算法來確定它們的位置，具有無需測量距離，硬件要求低等點，在硬件條件有限的WSN得到了廣泛的應(yīng)用。DV-Hop算法的定位過程分為三個階段：

（1）計算節(jié)點的最小跳數(shù)。信標(biāo)節(jié)點向網(wǎng)絡(luò)發(fā)送一個廣播信號，鄰居節(jié)點接收到信號后，記錄信標(biāo)節(jié)點的坐標(biāo)信息，并保存每個信標(biāo)節(jié)點的最小跳數(shù)，然后向其他的鄰居傳感器節(jié)點傳播，通過該方法，WSN網(wǎng)絡(luò)中全部節(jié)點可以得到信標(biāo)節(jié)點的位置信息和與信標(biāo)節(jié)點間的跳數(shù)。

（2）估算到信標(biāo)節(jié)點的跳段距離。通過第一階段后，每個信標(biāo)節(jié)點就可以得到其他信標(biāo)節(jié)點的坐標(biāo)值和跳數(shù)，然后通過式（1）計算平均每跳距離，同時將每跳平均距離廣播至網(wǎng)絡(luò)中，未知節(jié)點只保存第一個每跳平均距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點，未知節(jié)點將平均每跳距離值與最小跳數(shù)值相乘，得到其與信標(biāo)節(jié)點間的距離[13-14]。

式中，h(i，j)是信標(biāo)節(jié)點i和 j之間的跳數(shù)，(xi，yi)、(xj，yj)是信標(biāo)節(jié)點i，j的坐標(biāo)。

（3）通過最大似然法計算自身位置。設(shè) P1(x1，y1)，P2(x2，y2)，…，Pn(xn，yn)表示n個信標(biāo)節(jié)點的坐標(biāo)位置，待定位節(jié)點 D的位置為(x，y)，其與標(biāo)節(jié)點估計距離分別為d1，d2，…，dn-1，可以建立式（2）的方程：

在測距過程，由于多種因素影響會產(chǎn)生一些隨機(jī)誤差，最合理的線性方程組應(yīng)為 AL+N=b，N為n-1維隨機(jī)誤差向量，采用最小二乘法得到方程組的解為：

2 MSPO-DV-Hop的節(jié)點定位算法

2.1 節(jié)點間跳數(shù)引起的誤差及改進(jìn)

DV-Hop算法的最大誤差如圖1所示。在圖1中，節(jié)點B、C獲得與信標(biāo)節(jié)點A間的跳距，信標(biāo)節(jié)點計算網(wǎng)絡(luò)平均每跳距離且在網(wǎng)絡(luò)中傳播，未知節(jié)點B、C接收到距離最近的信標(biāo)節(jié)點A的平均每跳距離并乘以跳數(shù)得到AB和AC跳段距離（如圖1虛線所示），但是AB和AC的實際距離應(yīng)為L1和L2，因此當(dāng)最小跳數(shù)過大，易產(chǎn)生定位誤差，且跳數(shù)過大誤差越大。為了減少這一誤差，對最小跳數(shù)進(jìn)行判定，假定M為某一門限值，若h＞M，則h=M；若h＜M，則保持跳數(shù)不變。

圖1 DV-Hop節(jié)點分布圖

2.2 最小二乘法引起的誤差及修正

2.2.1 誤差分析

從式（4）可知，dn是帶有誤差的測量距離，而向量b每個元素均包含dn，當(dāng)dn的誤差相當(dāng)小時，那么最小二乘得到節(jié)點定位結(jié)果可以滿足實際要求，但當(dāng)dn的誤差較大時，即使d1，d2，…，dn-1的誤差小，節(jié)點定位的誤差也將很大。

設(shè)信標(biāo)節(jié)點(xi，yi)，i=1，2，…，n，與未知節(jié)點(x，y)的實際距離為 ri，i=1，2，…，n，測距誤差 εi，那么|ri-di|＜εi，i=1，2，…，n。根據(jù)式（2）可知，(x，y)應(yīng)該滿足如下約束條件：

由于式（5）代表可行解的區(qū)域，那么該區(qū)域一定存在最優(yōu)解，且當(dāng) f(x，y)最小值時，節(jié)點定位總誤差最小，此時的坐標(biāo)(x，y)將為最優(yōu)值，這樣無線網(wǎng)絡(luò)傳感器節(jié)點定位問題轉(zhuǎn)化成一個約束優(yōu)化問題，因此采用MPSO對式（6）進(jìn)行求解。

2.2.2 MPSO算法

設(shè)粒子群在d維的空間搜索，粒子i的速度和位置分別為：vi=(vi1，xi2，…，vid)T和 xi=(xi1，xi2，…，xid)T，粒子i自身的歷史最優(yōu)位置為 pi=(pi1，pi2，…，pid)，種群歷史的最優(yōu)位置為 pg=(pg1，pg2，…，pgd)，其速度和位置更新方式為：

其中，c1、c2為加速系數(shù)；rand()為[0，1]之間的隨機(jī)數(shù)；t為當(dāng)前迭代次數(shù)；w為慣性權(quán)值。

在PSO算法中，當(dāng)某粒子發(fā)現(xiàn)一個局部最優(yōu)點時，其他粒子迅速向它靠攏，則粒子群就陷入局部極值點。為了解決該難題，將粒子群分為“利用”和“探索”兩類子群，“利用子群”對探索到的最優(yōu)區(qū)域進(jìn)行精細(xì)搜索，“探索子集”探索有希望的區(qū)域，從而保持子種群的多樣性。在圖2中，Sbi為具有N個粒子的子種群，Sbi_1為利用子群，Sbi_2為探索子群，在每次迭代過程中，依據(jù)粒子適應(yīng)度值，將Sbi分為Sbi_1和Sbi_2兩個子群，它們粒子個數(shù)根據(jù)式（9）、（10）確定，兩個子集群按照各自規(guī)則操作后，重新歸隊。

圖2 多子種群的示意圖

式中，E(t)為子種群進(jìn)化因子，CHs為探索常數(shù)，Hs為探索子群；HL為利用子群。

種群進(jìn)化因子E(t)定義如下：

從式（11）可知，當(dāng)E(t)＞0時，粒子群處于進(jìn)化狀態(tài)；當(dāng)E(t)=0時，粒子群進(jìn)化處于停滯狀態(tài)，因此，通過E(t)適應(yīng)確定探索粒子，保證“利用”和“探索”間平衡，克服PSO算法存在的不足，提高粒子群的搜索能力。

2.2.3 MPSO算法對誤差的修正步驟

步驟1把未知節(jié)點的每一個可行解看作粒子，在網(wǎng)絡(luò)通信區(qū)域?qū)γ恳粋€未知點的可解解速度和位置初始化，并設(shè)置粒子群算法的相關(guān)參數(shù)。

步驟2根據(jù)式（12）計算每一個粒子的適應(yīng)度值，將最優(yōu)粒子的位置保存 pi中，粒子群體最優(yōu)位置保存 pg中。粒子適應(yīng)度函數(shù)定義為：

步驟4根據(jù)適應(yīng)度值對粒子進(jìn)行排序，選擇前HL個粒子組成“利用”子群，其余粒子組成“探索”子群。

步驟5根據(jù)式（7）、（8）更新粒子的速度和位置，并調(diào)整權(quán)重。

步驟6將每個粒子的位置與自身的歷史最優(yōu)位置 pi比較，如果優(yōu)于 pi，該粒子位置代替自身歷史最好位置 pi。

步驟7將每個粒子的位置與種群的歷史最優(yōu)位置比較 pg，如果優(yōu)于 pg，該粒子位置代替種群歷史最好位置 pg。

步驟8根據(jù)式（12）計算新粒子群的適應(yīng)度值。

步驟9如果達(dá)到算法的終止條件，停止優(yōu)化，不然根返回步驟4繼續(xù)優(yōu)化。

步驟10輸出全局最優(yōu)粒子的位置對應(yīng)坐標(biāo)(x，y)。

3 仿真實驗

3.1 實驗場景

整個教學(xué)過程中，發(fā)現(xiàn)學(xué)生的學(xué)習(xí)興趣一直沒有衰減，面對問題，能層層去解決，表現(xiàn)出良好的秩序感，課堂氣氛和諧而不呆板，學(xué)生根據(jù)自己的能力，各司其職，井井有條。

假設(shè)節(jié)點隨機(jī)分布在400 m×400 m二維區(qū)域內(nèi)，節(jié)點總數(shù)為200，信標(biāo)節(jié)點為40，未知傳感器節(jié)點的位置隨機(jī)產(chǎn)生，傳感器節(jié)點的通信半徑均為20 m，限定門限值M=4，在MATLAB 2008平臺上實現(xiàn)傳感器節(jié)點定位算法。

3.2 對比算法和評價指標(biāo)

為了使MPSO-DV-Hop算法的定位結(jié)果更具說服力，采用DV-Hop算法、粒子群優(yōu)化DV-Hop算法（PSO-DV-Hop）進(jìn)行對比實驗。算法的性能評價指標(biāo)為平均定位誤差（ave_error），其計算公式為：

式中，una是未知節(jié)點的個數(shù)，error為每個未知節(jié)點的定位誤差，(Xe，Ye)、(Xt，Yt)分別是未知傳感器節(jié)點估計值和真實值。

3.3 跳數(shù)門限值的設(shè)定

設(shè)M=3、5、7，在不同的信標(biāo)節(jié)點個數(shù)條件下，MPSO-DVHop的仿真結(jié)果如圖3所示。從圖3中可知，在相同的信標(biāo)節(jié)點，跳數(shù)的門限值M越小，MPSO-DV-Hop算法的傳感器節(jié)點的定位誤差相應(yīng)越小，這表明，通過合理設(shè)置傳感器節(jié)點間跳數(shù)門限值，傳感器傳節(jié)點的定位精度得到提高。因此本文的跳數(shù)門限值M=3。

圖3 M值對定位誤差的影響

3.4 結(jié)果與分析

3.4.1 粒子群算法改進(jìn)的有效性

設(shè)定位目標(biāo)誤差為0.05 m，MPSO-DV-Hop、PSO-DV-Hop定位誤差與迭代次數(shù)關(guān)系如圖4所示。從圖4可知，MPSODV-Hop只要經(jīng)過10次迭代就可以達(dá)到傳感器節(jié)點定位精度要求，而PSO-DV-Hop要進(jìn)行35次以上的迭代才能得到傳感器節(jié)點定位精度要求，這表明MPSO算法通過引入“多子種群”機(jī)制，具有更優(yōu)的全局搜索能力，使算法的計算工作量大大減少，對于能量受限的WSN具有重要意義。

圖4 粒子群算法改進(jìn)前后的定位誤差比較

3.4.2 不同信標(biāo)節(jié)點下的定位性能比較

在不同的信標(biāo)節(jié)點下，DV-Hop、MPSO-DV-Hop、PSODV-Hop算法的傳感器節(jié)點平均定位誤差如圖5所示。從圖5可知，當(dāng)信標(biāo)節(jié)點數(shù)量較少時，3種算法的平均定位誤差都較大，隨著信標(biāo)節(jié)點數(shù)量的增加，傳感器節(jié)點平均定位誤差開始遞減，在相同的信標(biāo)節(jié)點下，PSO-DV-Hop的算法優(yōu)于經(jīng)典DV-Hop算法；相對于PSO-DV-Hop的算法，MSPO-DV-Hop算法的平均定位誤差明顯減小，尤其當(dāng)信標(biāo)點數(shù)量少時，MSPO-DV-Hop算法定位精度的提高幅度明顯優(yōu)于對比算法，這一點非常符合無線傳感器網(wǎng)絡(luò)的需求，信標(biāo)節(jié)點的定位需求越少，人力物力成本則會降低。

圖5 不同信標(biāo)節(jié)點下的3種算法的定位誤差

3.4.3 不同通信半徑下的定位性能比較

在不通信半徑情況下，DV-Hop、MPSO-DV-Hop、PSODV-Hop算法的傳感器節(jié)點平均定位誤差如圖6所示。從圖6可知，隨著通信半徑的增加，由于未知節(jié)點的可定位信標(biāo)節(jié)點數(shù)增加，同時信號強(qiáng)度增加，測距更加準(zhǔn)確，DV-Hop、MPSO-DV-Hop、PSO-DV-Hop算法的傳感器節(jié)點平均定位誤差逐漸減小，但在相同的通信半徑下，相對于DV-Hop、PSO-DV-Hop算法，MPSO-DV-Hop提高了傳感器的平均定位精度。

4 結(jié)束語

通過對無線傳感網(wǎng)絡(luò)DV-Hop定位算法的分析，針對其不足，提出了一種MPSO算法優(yōu)化DV-Hop的傳感器節(jié)點定位算法。改算法的核心思想是：修正節(jié)點間的跳數(shù)門限值，并結(jié)合了MPSO算法解決約束優(yōu)化問題的優(yōu)點對傳感器定位結(jié)果進(jìn)行修正，該法實現(xiàn)簡單，不需增加額外的設(shè)備，仿真結(jié)果表明，MSPO-DV-Hop提高了傳感器節(jié)點的定位精度，尤其在信標(biāo)節(jié)點少、通信半徑較小的情況下，優(yōu)越性更加明顯。

圖6 三種算法在不同通信半徑下的誤差

[1]王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報，2005，16（5）：857-868.

[2]CostaJ A，PatwariN，Hero O.Distributed weightedmultidimensional scaling for node localization in sensor networks[J].ACM Transactions on Sensor Networks，2006，2（1）：39-64.

[3]Minh N，Duc V，Challa S，et al.Nonnumeric MDS for sensorlocalization[C]//3rd InternationalSymposium on Wireless Pervasive Computing，2008：396-400.

[4]劉運(yùn)杰，金明錄，崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)定位算法[J].傳感技術(shù)學(xué)報，2009，23（5）：717-721.

[5]安恂，蔣挺，周正.一種用于無線傳感器網(wǎng)絡(luò)的質(zhì)心定位算法[J].計算機(jī)工程與應(yīng)用，2007，43（20）：136-138.

[6]周彥，文寶，李建勛.無線傳感器網(wǎng)絡(luò)節(jié)點近點加權(quán)質(zhì)心定位方法[J].計算機(jī)工程與應(yīng)用，2012，48（1）：87-89.

[7]肖玲，李仁發(fā)，羅娟.基于非度量多維標(biāo)度的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].計算機(jī)研究與發(fā)展，2007，44（3）：399-405.

[8]LorinczK，Welsh M.A robustdecentralized approach to RF-based location tracking[C]//Proceedings of International Workshop on Location and Centex Awareness.Berlin，Germany：Springer-Verlag Press，2005：63-82.

[9]趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機(jī)應(yīng)用與軟件，2009，26（10）：189-192.

[10]鄧力.基于遺傳算法WSN節(jié)點定位算法研究[J].計算機(jī)仿真，2011，28（9）：161-164.

[11]孫澤宇，魏巍.一種改進(jìn)無線傳感器網(wǎng)絡(luò)定位算法的研究[J].計算機(jī)仿真，2010，27（9）：125-127.

[12]林金朝，劉海波，李國軍，等.無線傳感器網(wǎng)絡(luò)中DV-Hop節(jié)點定位改進(jìn)算法研究[J].計算機(jī)應(yīng)用研究，2009，26（4）：1292-1295.

[13]吳黎愛，周力.無線傳感器網(wǎng)絡(luò)中一種修正DV-Hop算法[J].計算機(jī)系統(tǒng)應(yīng)用，2012，31（4）：922-924.

[14]陳星舟，廖明宏，林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點定位改進(jìn)[J].計算機(jī)應(yīng)用，2010，30（7）：1736-1739.

ZHOU Tianqi1,JIANG Fengru2

1.Department of Computer and InformationTechnology,Zhejiang Changzheng Professional&Technical College,Hangzhou 310023,China 2.Department of Applications Electronics,Henan University of Animal Husbandry and Economy,Zhengzhou 450044,China

Localization is one of most important technolony of wireless sensor network,in order to reduce the error of node localization for DV-Hop algorithm in wireless sensor networks,a node localization algorithm based on Multi-population Particle Swarm Optimization（MPSO）algorithm and DV-Hop algorithm is proposed.The hops between nodes are modified by threshold value to improve the estimating accuracy of the hop distance,and then in the third stage of DV-Hop algorithm which MPSO algorithm is used to correct the localization error,the simulation analysis of MPSO-DV-Hop algorithm is carried out on MATLAB2008.The results show that the algorithm can improve the localization accuracy of the sensor without increasing cost situation.It has a high pratical value.

wireless sensor network;node localization;Multi-subpopulation Particle Swarm Optimization（MPSO）algorithm; DV-Hop algorithm

節(jié)點定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)，為減小DV-Hop算法的節(jié)點定位誤差，提出一種多子群粒子群（MPSO）算法優(yōu)化DV-Hop的節(jié)點定位算法（MPSO-DV-Hop）。通過設(shè)置門限值修正節(jié)點間的跳數(shù)，提高了跳段距離估算精度，DV-Hop的第3階段引入MPSO算法，對節(jié)點定位誤差進(jìn)行校正，通過引入多子群加快算法收斂速度，提高DV-Hop算法的節(jié)點定位精度，在MATLAB2008平臺上對算法仿真分析。結(jié)果表明，MPSO-DV-Hop算法在不增加成本情況下，提高了傳感器的節(jié)點定位精度，具有較高的應(yīng)用價值。

無線傳感網(wǎng)絡(luò)；節(jié)點定位；多子群粒子群優(yōu)化算法；DV-Hop算法

A

TP391.9

10.3778/j.issn.1002-8331.1305-0390

ZHOU Tianqi,JIANG Fengru.Node localization of wireless sensor network based on MPSO-DV-Hop.Computer Engineering and Applications,2013,49（23）：52-55.

周天綺（1976—），男，講師，研究方向為計算機(jī)網(wǎng)絡(luò)；姜鳳茹（1978—），女，講師，研究方向為信號處理。E-mail：zhoutianqi_2012@126.com

2013-05-29

2013-07-15

1002-8331（2013）23-0052-04

CNKI出版日期：2013-07-22 http://www.cnki.net/kcms/detail/11.2127.TP.20130722.0921.002.html