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

周天綺，姜鳳茹

1.浙江長征職業技術學院 計算機與信息技術系，杭州 310023 2.河南牧業經濟學院 應用電子系，鄭州 450044

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

周天綺1，姜鳳茹2

1.浙江長征職業技術學院 計算機與信息技術系，杭州 310023 2.河南牧業經濟學院 應用電子系，鄭州 450044

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

1 DV-Hop定位算法

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

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

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

式中，h(i，j)是信標節點i和 j之間的跳數，(xi，yi)、(xj，yj)是信標節點i，j的坐標。

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

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

2 MSPO-DV-Hop的節點定位算法

2.1 節點間跳數引起的誤差及改進

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

圖1 DV-Hop節點分布圖

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

2.2.1 誤差分析

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

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

由于式（5）代表可行解的區域，那么該區域一定存在最優解，且當 f(x，y)最小值時，節點定位總誤差最小，此時的坐標(x，y)將為最優值，這樣無線網絡傳感器節點定位問題轉化成一個約束優化問題，因此采用MPSO對式（6）進行求解。

2.2.2 MPSO算法

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

其中，c1、c2為加速系數；rand()為[0，1]之間的隨機數；t為當前迭代次數；w為慣性權值。

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

圖2 多子種群的示意圖

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

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

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

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

步驟1把未知節點的每一個可行解看作粒子，在網絡通信區域對每一個未知點的可解解速度和位置初始化，并設置粒子群算法的相關參數。

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

步驟4根據適應度值對粒子進行排序，選擇前HL個粒子組成“利用”子群，其余粒子組成“探索”子群。

步驟5根據式（7）、（8）更新粒子的速度和位置，并調整權重。

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

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

步驟8根據式（12）計算新粒子群的適應度值。

步驟9如果達到算法的終止條件，停止優化，不然根返回步驟4繼續優化。

步驟10輸出全局最優粒子的位置對應坐標(x，y)。

3 仿真實驗

3.1 實驗場景

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

假設節點隨機分布在400 m×400 m二維區域內，節點總數為200，信標節點為40，未知傳感器節點的位置隨機產生，傳感器節點的通信半徑均為20 m，限定門限值M=4，在MATLAB 2008平臺上實現傳感器節點定位算法。

3.2 對比算法和評價指標

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

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

3.3 跳數門限值的設定

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

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

3.4 結果與分析

3.4.1 粒子群算法改進的有效性

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

圖4 粒子群算法改進前后的定位誤差比較

3.4.2 不同信標節點下的定位性能比較

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

圖5 不同信標節點下的3種算法的定位誤差

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

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

4 結束語

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

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

[1]王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，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]劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網絡修正加權定位算法[J].傳感技術學報，2009，23（5）：717-721.

[5]安恂，蔣挺，周正.一種用于無線傳感器網絡的質心定位算法[J].計算機工程與應用，2007，43（20）：136-138.

[6]周彥，文寶，李建勛.無線傳感器網絡節點近點加權質心定位方法[J].計算機工程與應用，2012，48（1）：87-89.

[7]肖玲，李仁發，羅娟.基于非度量多維標度的無線傳感器網絡節點定位算法[J].計算機研究與發展，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]趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網絡定位算法[J].計算機應用與軟件，2009，26（10）：189-192.

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

[11]孫澤宇，魏巍.一種改進無線傳感器網絡定位算法的研究[J].計算機仿真，2010，27（9）：125-127.

[12]林金朝，劉海波，李國軍，等.無線傳感器網絡中DV-Hop節點定位改進算法研究[J].計算機應用研究，2009，26（4）：1292-1295.

[13]吳黎愛，周力.無線傳感器網絡中一種修正DV-Hop算法[J].計算機系統應用，2012，31（4）：922-924.

[14]陳星舟，廖明宏，林建華.基于粒子群優化的無線傳感器網絡節點定位改進[J].計算機應用，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

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

無線傳感網絡；節點定位；多子群粒子群優化算法；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—），男，講師，研究方向為計算機網絡；姜鳳茹（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