一種最優錨節點集合上的兩重粒子群優化DV-Hop定位算法

曹欲曉,嚴 奎,徐金寶

(1.南京工程學院計算機工程學院,南京 211167;2.南京工程學院工業中心,南京 211167)

?

一種最優錨節點集合上的兩重粒子群優化DV-Hop定位算法

曹欲曉1*,嚴 奎2,徐金寶1

(1.南京工程學院計算機工程學院,南京 211167;2.南京工程學院工業中心,南京 211167)

當前粒子群優化的DV-Hop定位改進算法,網絡中所有的錨節點都參與優化,但是一部分到未知節點估算距離誤差較大的錨節點會引入大的定位誤差。針對這種情況,首先提出了最優錨節點集合的概念;然后在定位過程中,應用離散粒子群算法構造了最優錨節點集合;最后在最優錨節點集合上應用連續粒子群算法對定位結果進行了優化。仿真實驗表明,最優錨節點集合上的兩重粒子群優化DV-Hop算法比DV-Hop和一次粒子群優化的DV-Hop明顯提高了定位精度。

無線傳感器網絡;節點定位;DV-Hop算法;粒子群算法;錨節點;最優錨節點集合

無線傳感器網絡WSN(Wireless Sensor Network)由大量部署在監控區域的傳感節點組成,用來獲取監控區域的相關信息。在WSN的大多數應用中,節點獲得的傳感數據要和自身的位置信息結合起來才有實際意義,沒有位置信息的數據往往毫無用處。因此節點定位是WSN領域中一項非常關鍵的支撐技術[1]。

WSN的節點定位根據是否需要測量節點間的距離或者角度等信息,分成基于測距的定位方法和無需測距的定位方法[2]兩種。基于測距的定位方法精度較高,但是需要額外的硬件設備支持;無需測距的定位方法精度相對要低,但是不需要額外的硬件設備,成本較低。DV-Hop即是無需測距定位方法中最為常用的一種,如何提高DV-Hop算法的定位精度具有重要的理論和實際價值[3]。很多研究者采用了多種方法來提高DV-Hop算法的定位精度。這些方法大致可以分成兩類:第1類是采用加權平均或者誤差修正的方法提高未知節點的平均跳距估算精度,第2類是應用群體智能算法[4]對DV-Hop定位的結果進行優化。文獻[5]根據未知節點接收的多個錨節點的平均跳距和到不同錨節點的跳數,把跳數的倒數作為權值進行加權平均,重新計算未知節點的平均跳距。文獻[6]把兩個錨節點之間的實際距離和估計距離的誤差的倒數作為權值,對錨節點的平均跳距進行加權平均。文獻[7]利用錨節點和未知節點實際距離和估計距離的誤差來修正每跳平均跳距。上述各種改進算法都是基于無偏估計準則計算的錨節點平均跳距。文獻[8-11]則把未知節點的定位抽象成一個優化問題,應用粒子群算法對DV-Hop的定位結果進行了優化,并讓全部錨節點參與整個優化過程。

現有的基于粒子群優化的DV-Hop(PSO DV-Hop)改進算法,對未知節點的位置進行優化時均是讓所有的錨節點都參與定位優化,但是由文獻[6]可知,在進行三邊測量定位時,如果某些錨節點的估計距離誤差過大,反而會使最終的定位誤差增大,所以并不是參加定位的錨節點的數量越多越好,應該在保證錨節點數量大于等于3個的前提下,選擇一個最優的錨節點集合進行定位。本文應用兩重粒子群算法對DV-Hop定位進行了改進,提出了一種新的DV-Hop改進算法:在三邊定位階段,首先應用離散粒子群算法構造一個到未知節點距離誤差最小的最優錨節點集合,接著再應用連續粒子群算法在最優錨節點集合上進行定位優化。仿真結果表明,本文算法在無需額外增加硬件設備的情況下,明顯提高了未知節點定位的精度。

1 DV-Hop算法

DV-Hop算法把未知節點的平均每跳距離乘以其到錨節點的跳數,以乘積作為未知節點到錨節點的距離。當獲得到達3個或3個以上錨節點的距離時,應用三邊測量法或極大似然法求出未知節點的坐標。DV-Hop的定位過程可以分成3個階段[12]。

第1階段:計算未知節點到錨節點的最小跳數。通過泛洪廣播的方式,網絡中的每個節點均可獲得到達所有錨節點的最小跳數。

第2階段:計算未知節點到錨節點的估計距離。每個錨節點根據第1階段獲得的其他錨節點的位置信息分組,利用式(1)計算自身的平均每跳距離。式(1)中,(xi,yi)是錨節點i的坐標,(xj,yj)是錨節點j的坐標,hij是錨節點i到j的跳數。

(1)

錨節點向網絡廣播自己的平均每跳距離,未知節點接收第1個平均跳距,利用式(2)計算自己到每個錨節點的距離,其中hi是第1階段獲得的到錨節點的跳數。

di=Hopsizei×hi

(2)

第3階段:計算未知節點坐標。未知節點根據第2階段計算出的di,利用三邊測量法或極大似然法計算自身坐標。

2 粒子群算法[13]

2.1 連續粒子群算法

(3)

(4)

式(4)中:w是慣性因子,c1是個體學習因子,c2是全局學習因子,r1和r2是區間[0,1]上的隨機數,PB是粒子的個體極值,GB是粒子群的全局極值。

2.2 離散粒子群算法

連續粒子群算法用來求解連續優化問題,為了解決組合優化問題,在連續粒子群的基礎上又提出了離散粒子群算法。二進制粒子群優化算法BPSO[14](Binary Particle Swarm Optimization)屬于離散粒子群算法中的一種。BPSO算法的位置矢量由實數空間變成了二進制空間,即粒子在每一維上的取值只能是0或1兩個值中的一個,但粒子的速度矢量仍然位于實數空間。BPSO算法的速度矢量更新公式用式(4)表示不變,位置矢量更新改用式(5)表示。

(5)

(6)

3 最優錨節點集合上的兩重粒子群優化DV-Hop算法

3.1 最優錨節點集合

設WSN中有m個錨節點,n個未知節點,現要對未知節點A進行定位。若A的定位坐標為(x,y),m個錨節點的坐標分別為(x1,y1)、(x2,y2)、…、(xm,ym),A到m個錨節點的估計距離分別是d1、d2、…、dm,實際距離分別是r1、r2、…、rm,則由兩點間的距離公式可得:

(7)

設A到m個錨節點估算距離的誤差分別是ε1、ε2、…、εm,則|ri-di|≤εi,把式(7)代入|ri-di|≤εi得,

(8)

求解(x,y),使式(9)取得最小值的解即是與未知節點A的真實坐標最為接近的定位結果。

(9)

式(9)的意義是:(x,y)作為計算出的未知節點A的坐標,如果(x,y)到各錨節點的實際距離ri與估算距離di的誤差的平方的和越小,則(x,y)就越接近A的真實坐標,那么定位的結果就越精確。為求得更為精確的(x,y),可以通過使式(9)的值最小來實現。這樣就把WSN節點的定位問題轉化成了一個優化問題,故可以應用粒子群算法求解。

由文獻[6]可知,如果未知節點到某些錨節點的估算距離di的誤差過大,反而會降低未知節點定位的精度,因此在定位過程中如果能排除這類di誤差過大的錨節點,而是在m個錨節點中選擇k個估算距離di誤差較小的錨節點參加定位,則能提高定位結果的精度,這樣的一組錨節點構成的集合稱為最優錨節點集合BANS(Best Anchor Nodes Set)。

3.2 兩重粒子群優化的DV-Hop原理

從m個錨節點中選擇k個構造一個最優錨節點集合,對網絡中任意一個錨節點,或者被選中進入最優錨節點集合,或者不被選中。選擇多少個錨節點,選擇哪些錨節點才能使錨節點集合最優屬于組合優化問題,可以應用離散粒子群算法求解。在構造最優錨節點集合過程中使用的粒子群稱為種群1。

構造出最優錨節點集合后,再使用另外一個把粒子對應到了未知節點坐標的粒子群,應用連續粒子群算法對定位結果尋優。在這個過程中使用的粒子群稱為種群2。對定位結果的優化即為使適應值函數取得最小值為優化目標,以未知節點的坐標作為粒子的位置矢量,經過多次迭代,可以求得最為接近未知節點真實坐標的定位結果。

因為未知節點到錨節點的距離是由未知節點的平均跳距和它到錨節點的跳數相乘估算得到的,未知節點到哪些錨節點的估計距離誤差較小事先無法得知,所以最優錨節點集合的構造只能在求解未知節點坐標(x,y)的過程中,通過使適應值函數取得最小值來動態的構造。這就需要把構造最優錨節點集合的離散粒子群算法和在最優錨節點集合上最優化(x,y)的連續粒子群算法融合成一個整體來求解,這種方法稱為兩重粒子群優化的DV-Hop算法DBPSO DV-Hop(Double PSO DV-Hop)。

3.3 兩重粒子群優化的DV-Hop粒子編碼

應用粒子群算法求解優化問題的首要任務是粒子編碼。下面首先給出求解最優錨節點集合的離散粒子群編碼方案。從m個錨節點中選出k個構成最優錨節點集合,m個錨節點中的任意一個或者是集合中的一個元素,或者不是,只有兩種可能,因此可以構造一個m維的二進制空間作為粒子的搜索空間。

應用連續粒子群算法優化DV-Hop的粒子編碼,采用文獻[8-11]中給出的方案,即每個粒子對應未知節點的一個定位優化結果,粒子的兩個位置分量表示未知節點的兩個坐標,粒子在二維空間中飛行尋優。

3.4 兩重粒子群優化的DV-Hop適應值函數

由式(9)知,通過離散粒子群算法求解出的最優錨節點集合對最終定位結果的優化程度,需要通過di和ri(1≤i≤m)誤差的平方和來判定,所以DBPSO DV-Hop算法的離散粒子群和連續粒子群要共用同一個適應值函數,這個函數如式(10)所示。適應值函數的設計思想是參加定位的錨節點的di和ri的誤差的平方和的平均值最小。

(10)

式(10)中的XDi(1≤i≤m)是種群1中粒子的位置分量,x和y是種群2中粒子的位置分量,β是未知節點到錨節點跳數的倒數。

3.5 兩重粒子群優化的DV-Hop步驟

①初始化種群1、種群2的規模都是Q,確定慣性因子w、學習因子c1和c2的值。

②分別初始化種群1、種群2中每個粒子的位置和速度。種群1粒子的初始位置和速度由式(11)、式(12)給出,m是網絡中所有錨節點的個數,T(Q)是(0,1)區間上的一個閾值。

(11)

(12)

種群2的位置和速度由式(13)～式(15)給出。Xmax和Ymax是網絡中所有錨節點橫坐標和縱坐標的最大值,Vmin和Vmax是粒子速度的最小值和最大值,r(0,1)是區間[0,1]上的隨機數,rand()是隨機數函數。

(13)

(14)

(15)

③計算種群1中粒子和種群2中粒子的笛卡爾積,把笛卡爾積中的每個元素看做一個復合粒子,求出每個復合粒子的個體極值和全部復合粒子的全局極值。

④利用式(5)和式(4)更新種群1中每個粒子的位置和速度,利用式(3)和式(4)更新種群2中每個粒子的位置和速度。

⑤重復步驟③、步驟④,直到完成規定的迭代次數。此時復合粒子的全局極值就是優化后的待定位節點的坐標。

4 仿真結果及分析

4.1 3種算法使用的錨節點比較

由3.1知,對同一個未知節點定位,使用的錨節點不同會導致定位的精度有差別。DBPSO DV-Hop算法的核心思想是在所有錨節點中選出一個能使定位結果誤差最小的最優錨節點集合。下面給出錨節點比例為15%時,DV-Hop、PSO DV-Hop、DBPSO DV-Hop 3種算法定位階段所使用的錨節點的數量、未知節點到錨節點估算距離和實際距離誤差的平均值、平均定位誤差的比較。

表1 3種定位算法使用的錨節點比較

從表1還可以看出DBPSO DV-Hop算法經過多次迭代,選出的最優錨節點集合中的錨節點估計距離和實際距離的誤差較小,使用最優錨節點集合進行優化,定位結果的平均誤差也較小。

4.2 3種算法定位結果比較

(16)

為了驗證本文提出的DBPSO DV-Hop算法的性能,應用MATLAB軟件對DV-Hop、PSO DV-Hop、DBPSO DV-Hop 3種算法進行仿真。仿真環境設為:WSN分布在一個100 m×100 m的正方形區域中,隨機生成錨節點和未知節點的坐標,節點的通信半徑是50 m。種群1和種群2的規模均是20,慣性因子w=0.9,學習因子c1=c2=2,迭代次數為200次。為了減少隨機誤差的干擾,每種算法均運行100次取平均值作為最終的實驗結果。

圖1給出了在節點總數維持200不變,錨節點比例變化的情況下3種定位算法的平均誤差比較結果。由圖1可以看出,隨著錨節點比例的增大,3種定位方法的平均定位誤差都在減小,PSO DV-Hop和DBPSO DV-Hop的減小要快于DV-Hop。PSO DV-Hop比DV-Hop平均提高定位精度11%,DBPSO DV-Hop比DV-Hop平均提高定位精度26%。在錨節點比例從15%～25%的區間內,DBPSO DV-Hop定位精度遠高于PSO DV-Hop,但是當錨節點比例超過25%以后,兩者的差距反而減小。

圖1 節點總數不變錨節點比例改變的定位誤差比較

圖2 錨節點比例不變節點總數改變的定位誤差比較

圖2給出了在錨節點比例維持10%不變,節點總數變化的情況下3種定位算法的平均誤差比較結果。由圖2可以看出,在錨節點比例保持不變的情況下,隨著節點總數的增加,錨節點總數也隨之增加,3種定位算法的平均誤差均呈下降趨勢。PSO DV-Hop比DV-Hop平均提高定位精度16%,DBPSO DV-Hop比DV-Hop平均提高定位精度43%。

從以上兩種情況下的仿真結果可以看出,DBPSO DV-Hop算法的節點定位精度要明顯好于DV-Hop和PSO DV-Hop算法。

5 結語

粒子群算法作為一種性能良好、實現簡單的群體智能算法,被很多研究者應用到了WSN的節點定位中,但是目前的粒子群優化DV-Hop算法存在一個共同的問題,即定位尋優時使用了所有可以使用的錨節點,而有些錨節點的測距誤差過大,反而會降低最后定位的精度。因此本文的工作在于首先選出一組測距誤差較小的錨節點構成最優錨節點集合,只使用最優錨節點參加定位以減小測距誤差對定位結果的影響。在所有的錨節點中確定最優者時,由于哪些錨節點的測距誤差較小并不知道,所以采用了離散粒子群算法在所有錨節點中組合尋優進行查找。在確定了最優錨節點集合之后,再應用連續粒子群算法最終確定未知節點的坐標。

仿真實驗表明,本文提出的DBPSO DV-Hop算法在定位時使用的錨節點在數量上少于DV-Hop和PSO DV-Hop,但在錨節點和未知節點的距離精度上好于上述兩種算法。最終的定位結果也表明DBPSO DV-Hop比DV-Hop和PSO DV-Hop在很大程度上減小了定位誤差,提高了定位精度。但是DBPSO DV-Hop由于采用了兩次粒子群算法,增加了計算的復雜度,并且粒子群算法參數的選取也缺乏相應的理論指導,這是以后需要繼續研究改進之處。

[1]Niclescu D,Americ N L. Communication Paradigms for Sensor Network[J]. IEEE Communications Maganize,2005,43(3):116-122.

[2]Bulusu N,Heidemann J,Estrin D. GPS-Less Low Cost Outdoor Localization for Very Small Devices[J]. IEEE Personal Communications Magzine,2000,7(5):28-34.

[3]張震,閆連山,劉江濤,等. 基于DV-Hop的無線傳感器網絡定位算法研究[J]. 傳感技術學報,2011,24(10):1470-1472.

[4]Hackwood S,Beni G. Self-Organization of Sensors for Swarm Intelligence[C]//IEEE International Conference on Robotics and Automation. Piscataway,NJ,USA:IEEE Press,1992:819-829.

[5]劉峰,張翰,楊驥. 一種基于加權處理的無線傳感器網絡平均跳距離估計算法[J]. 電子與信息學報,2008,30(5):1222-1225.

[6]趙雁航,錢志鴻,尚小航,等. 基于跳距修正粒子群優化的WSN定位算法[J]. 通信學報,2013,34(9):105-114.

[7]石為人,賈傳江,梁煥煥. 一種改進的無線傳感器網絡DV-Hop定位算法[J]. 傳感技術學報,2011,24(1):83-87.

[8]張迅,王平,邢建春,等. 傳感器網絡中改進的粒子群優化定位算法[J]. 計算機科學,2012,39(12):51-54.

[9]蔡紹濱,高振國,潘海為,等. 帶有罰函數的無線傳感器網絡粒子群定位算法[J]. 計算機研究與發展,2012,49(6):1228-1234.

[10]崔煥慶,王英龍,呂家亮,等. 基于隨機微粒群算法的分布式節點定位算法[J]. 山東大學學報:理學版,2012,47(9):51-55.

[11]陳星舟,廖明宏,林建華. 基于粒子群優化的無線傳感器網絡節點定位改進[J]. 計算機應用,2010,30(7):1736-1738.

[12]Niculescu D,Nat h B. DV Based Positioning in Ad Hoc Networks[J]. Journal of Telecommunication Systems,2003,22(14):267-280.

[13]Kennedy J,Eberhart R C. Particle Swarm Optimization[C]//IEEE International Conference on Neural Networks,Ⅳ. Piscataway,NJ,USA:IEEE Service Center,1995:1942-1948.

[14]Kennedy J,Eberhart R C. A Discrete Binary Version of the Particle Swarm Algorithm[C]//The 1997 Conference on System,Cybernetics and Informatics. Piscataway,NJ USA:IEEE Press,1997:4104-4109.

A Kind of Double Particle Swarm Optimization DV-Hop Localization Algorithm Based on Best Anchor Nodes Set

CAOYuxiao1*,YANKui2,XUJinbao1

(1.School of Computer Engineering,Nanjing Institute of Technology,Nanjing 211167,China;2.Industrial Center,Nanjing Institute of Technology,Nanjing 211167,China)

For the improved DV-Hop algorithms based on particle swarm optimization,almost all the anchor nodes in the network are involved in the locating optimization. However,the anchor nodes which have obvious errors between anchor and unknown nodes will lead to big errors of localization. Hence,the concept of best anchor nodes set is proposed. During the process of location,the best anchor nodes set is constructed by employing the discrete particle swarm optimization algorithm. Then the continuous particle swarm optimization algorithm is used to optimize localization for the best anchor nodes set. The simulation results show that the proposed method is effective.

wireless sensor network;node localization;DV-Hop algrothrim;particle swarm optimization algrothrim;anchor node;best anchor nodes set

曹欲曉(1971-),男,山東臨沂人,碩士,講師.主要研究方向為智能算法、無線傳感器網絡,caoyx@njit.edu.cn;

嚴 奎(1976-),男,四川南充人,碩士,講師,主要究研方向為控制理論與控制工程,yankui@njit.edu.cn;

徐金寶(1970-),男,江蘇南京人,碩士,副教授.主要研究方向為數據挖掘,智能算法,xujb@njit.edu.cn。

2014-10-20 修改日期:2014-12-22

C:7030;6150P

10.3969/j.issn.1004-1699.2015.03.022

TP393

A

1004-1699(2015)03-0424-06