周天綺，姜鳳茹

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

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

周天綺1，姜鳳茹2

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

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

1 DV-Hop定位算法

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

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

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

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

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

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

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

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

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

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

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

2.2.1 誤差分析

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

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

由于式（5）代表可行解的區(qū)域，那么該區(qū)域一定存在最優(yōu)解，且當(dāng) f(x，y)最小值時(shí)，節(jié)點(diǎn)定位總誤差最小，此時(shí)的坐標(biāo)(x，y)將為最優(yōu)值，這樣無線網(wǎng)絡(luò)傳感器節(jié)點(diǎn)定位問題轉(zhuǎn)化成一個(gè)約束優(yōu)化問題，因此采用MPSO對(duì)式（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)一個(gè)局部最優(yōu)點(diǎn)時(shí)，其他粒子迅速向它靠攏，則粒子群就陷入局部極值點(diǎn)。為了解決該難題，將粒子群分為“利用”和“探索”兩類子群，“利用子群”對(duì)探索到的最優(yōu)區(qū)域進(jìn)行精細(xì)搜索，“探索子集”探索有希望的區(qū)域，從而保持子種群的多樣性。在圖2中，Sbi為具有N個(gè)粒子的子種群，Sbi_1為利用子群，Sbi_2為探索子群，在每次迭代過程中，依據(jù)粒子適應(yīng)度值，將Sbi分為Sbi_1和Sbi_2兩個(gè)子群，它們粒子個(gè)數(shù)根據(jù)式（9）、（10）確定，兩個(gè)子集群按照各自規(guī)則操作后，重新歸隊(duì)。

圖2 多子種群的示意圖

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

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

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

2.2.3 MPSO算法對(duì)誤差的修正步驟

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)場(chǎng)景

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

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

3.2 對(duì)比算法和評(píng)價(jià)指標(biāo)

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

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

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

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

圖3 M值對(duì)定位誤差的影響

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é)點(diǎn)定位精度要求，而PSO-DV-Hop要進(jìn)行35次以上的迭代才能得到傳感器節(jié)點(diǎn)定位精度要求，這表明MPSO算法通過引入“多子種群”機(jī)制，具有更優(yōu)的全局搜索能力，使算法的計(jì)算工作量大大減少，對(duì)于能量受限的WSN具有重要意義。

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

[1]王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào)，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é)報(bào)，2009，23（5）：717-721.

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

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

[7]肖玲，李仁發(fā)，羅娟.基于非度量多維標(biāo)度的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(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ì)算機(jī)應(yīng)用與軟件，2009，26（10）：189-192.

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

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

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

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

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

無線傳感網(wǎng)絡(luò)；節(jié)點(diǎn)定位；多子群粒子群優(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—），男，講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；姜鳳茹（1978—），女，講師，研究方向?yàn)樾盘?hào)處理。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