基于佳點集的蝙蝠定位算法在WSN中應用*

謝國民,干毅軍,丁會巧

(1.遼寧工程技術大學電氣工程與控制工程學院,遼寧 葫蘆島 125105;2.烏魯木齊供電公司,烏魯木齊 830000)

基于佳點集的蝙蝠定位算法在WSN中應用*

謝國民1*,干毅軍1,丁會巧2

(1.遼寧工程技術大學電氣工程與控制工程學院,遼寧 葫蘆島 125105;2.烏魯木齊供電公司,烏魯木齊 830000)

針對無線傳感器網絡(WSN)節點的定位誤差較大的的問題,提出一種新的基于佳點集的蝙蝠定位算法。在改進的算法中,采用基于佳點集的方法對蝙蝠種群個體進行初始化優化,有效提高種群多樣性,避免算法過早陷入局部最優;引入部落機制及自適應更新方式,可有效避免局部最優解的吸引,加快收斂速度;通過重構部落利用pareto分級有效避免個別優秀個體被淘汰,增強了泛化能力,提高算法精度。通過MATLAB模擬仿真平臺仿真實驗表明,改進后的算法具有較好的收斂性和良好的尋優性能,降低測距誤差對定位的影響,提高節點的定位精度。算法系統實現條件簡單、精度高,具有較高的實際應用價值。

蝙蝠算法;佳點集;部落機制;WSN

無線傳感器網絡WSN(WirelessSensor Network)是由許多傳感器節點組成采用無線通信方式連接的一個多跳自組織的網絡系統,具備檢測感知、采集和處理信息的功能[1]。在無線傳感器網絡的應用中,實時獲取事件發生位置或節點信息是WSN的基本功能之一,因此節點定位是無線傳感器網絡中的一個重要問題,引入位置信息,才能使得無線傳感器網絡的許多檢測數據變得更有意義[2]。

針對WSN定位方法,國內外學者進行大量研究,定位算法分為兩類:節點自身的定位和目標節點的定位,其中節點自身定位算法分為基于測距技術的定位算法和無需測距的定位算法。基于測距技術的定位算法通過測量節點間的距離或者角度信息,使用三邊測量法、三角測量法或最大似然估計法來計算節點位置,包括RSSI(Received Signal Strength Indicator)定位[3]、TOA(Time of Arrival)定位[4]、TDOA(Time Difference On Arrival)定位[5]和AOA(Angle of Arrival)定位[6],算法定位精度較高,但因額外的硬件設置,成本大而使其使用受限;無需測距的定位算法有質心定位、凸規劃定位[7]、DV-HOP(Distance Vector HOP)定位、Amorphous定位、MDS-MAP定位[8]和APIT(Approximate PIT Test)定位[9],此類定位算法是通過錨節點的信息和網絡連通度來估計節點位置,無需額外硬件支持,算法簡單,成本低,但存在定位精度不高等缺點。隨著無線傳感器技術的發展,已將無線傳感器的節點定位問題轉換為約束優化問題,通過智能算法對節點進一步優化以提高定位精度[10-13]。蝙蝠算法BA(Bat Algorithm)具有模型簡單,尋優能力強等優點可用以解決WSN定位問題;但基本蝙蝠算法存在易早收斂、后期收斂速度慢、局部搜索能力弱等缺點。

針對蝙蝠算法的缺點,本文提出一種基于佳點集的自適應蝙蝠算法GBA(Good-Point Bat Algorithm)用于WSN系統中的節點定位,采用佳點集方法對WSN系統中的節點初始化進行優化,使其均勻分布于解空間,保持種群的多樣性;通過GBA算法全局搜索解空間,利用自適應搜索算子的位置更新方法,加快算法的收斂速度,提高蝙蝠算法的全局搜索能力。

圖1 無線傳感器網絡典型的體系結構

1 無線傳感器網絡體系

無線傳感器網絡典型的體系結構如圖1所示。定位網絡是由隨機部署的待定位節點和參考錨節點組成。錨節點通過向其他節點廣播自身的位置信息,為其他節點確定位置提供信息。在傳感器網絡中除了知道自身位置信息的錨節點外就是待定位節點。待定位節點通過錨節點提供的信息和定位算法計算出自身的位置。定位算法就是以多節點構成的傳感器網絡為硬件基礎,通過相應的軟件設計實現的。精度高、容錯能力強定位算法將極大提高定位節點的定位精度。將基于佳點集的自適應蝙蝠算法應用于定位系統,將有效的提高定位節點的定位精度及定位速度。

2 基于佳點集的蝙蝠定位算法

2.1 基于佳點集蝙蝠定位算法方法論

選取適應度函數f(xi)來體現WSN定位系統的精度,f(xi)函數值大小在蝙蝠算法中代表種群個體位置的優劣,適應度函數與種群個體位置構成如式(1)所示關系:

(1)

蝙蝠算法通過超聲波搜索,利用回聲定位的原理進行獵物搜索,蝙蝠種群在初始化時個體應盡可能的均勻分布在整個搜索空間中[14],采用佳點集的蝙蝠算法在整個搜索空間內進行均勻搜索能以較快的收斂速度快速逼近最優解。

對于搜索空間中的初始種群,既不能粗略的隨機產生,又不能遍歷所有的狀況,通過數論中的佳點集原理設計出均勻分布于搜索空間的初始種群,以保持種群良好的多樣性。在佳點集的定義[15-18]中,設GD是D維歐式空間中的單位立方體,如果rGD,形為

(2)

其偏差φ(n)=C(r,ε)n-1+ε,則稱Pn(k)為佳點集,r為佳點,其中C(r,ε)是只與r、ε(ε>0)有關的常數。取rk={2cos(2πr/p)},1≤k≤n,p是滿足(p-D/2)≥D的最小素數,或rk={exp(k)},1≤k≤n,{a}表示a的小數部分。理論[19]上已證明,用n個佳點構成的加權和比采用任何其他n個點所得到的誤差都要小。

fi=fmin+β(fmax+fmin)

(3)

(4)

(5)

式中:fmin和fmax是聲音頻率的最小值和最大值;β[0,1]是一個服從均勻分布的隨機向量,x*表示當前全局最優解。

種群個體在不斷更新,蝙蝠個體在靠近獵物時,音量逐漸降低,脈沖頻率逐漸增高,直到蝙蝠個體i搜索到一只獵物時Ai=0,此時停止發音,其更新公式如下

(6)

(7)

為了提高蝙蝠算法的收斂能力以及避免陷入局部最優解,將部落機制引入蝙蝠算法中,將蝙蝠族群劃分為規模相同的部落,如圖2所示。

由圖2可以看出,該劃分策略分為兩部分:首先是由n個個體組成的部落內部尋出局部最優解轉移并記錄;其次是將轉移的局部最優解組成新部落尋找全局最優解。充分利用蝙蝠算法的局部搜索能力和全局信息交換能力可以使得全局最優信息能在種群群體中有效傳遞,提高了算法的收斂效率。

圖2 部落機制結構

為避免盲目搜索,定義個體適應度調節項和自適應搜索算子,根據個體在每個目標上的適應度值自適應調整搜索范圍,如下式所示:

(8)

(9)

(10)

將一次迭代后得到的種群,利用pareto,對相同pareto等級相同的個體按照個體優劣比較原則進行擁擠距離排序,并取出q個個體,更新種群w。

重新構造種群后,采用式(11)計算個體未更新次數:

(11)

2.2 基于佳點集蝙蝠定位算法流程

基于佳點集的蝙蝠定位算法主要思想是通過蝙蝠種群初始化使種群均勻分布,然后將均勻分布的種群個體劃分為若干部落尋找出各部落的最優個體,將部落最優個體組成新部落尋出最優個體,循環反復,尋找出最優個體。主要工作步驟如下:

Step 1 定義適應度函數f(xi),xi=(x1,x2,…,xd)T,其中d為維數,x為蝙蝠個體的位置,f(xi)的最優解就是蝙蝠個體搜索到獵物的位置;

Step 2 采用佳點集的方法隨機構成蝙蝠種群w,每個個體為xi=(i=1,2,…,n)(n為種群數量),并平均劃分為n個部落;定義蝙蝠個體所在位置xi和飛行速度vi以及頻率fi;定義蝙蝠發出的音量Ai、脈沖發生率ri、迭代次數。為了方便計算,音量和脈沖頻率都設為常數0.5。

Setp 4 選擇初始種群w中優秀的個體執行更新并記錄新個體,采用輪盤賭方式執行Q次選擇,按照個體優劣比較規則每次選出一個pareto等級較低、擁擠距離較大的優秀個體執行式(9),產生的新個體由式(10)記錄進入外部集合w′。

Setp 5 按照3.4策略重新構造種群w,并按式(11)記錄未被更新次數triali。

Setp 6 淘汰w中多次未被更新的個體。選擇triali值最大且pareto等級大于1的個體xi,隨機產生新的個體代替xi。

Setp 7 判斷是否達到算法結束條件,若達到,輸出最優解,否則轉到Setp 3。

為了配合改進后的更新策略,Setp 6調整了個體淘汰機制,直接選擇pareto等級不為1的最久未被更新的個體做更新,這樣算法在選擇被淘汰個體時避開了pareto等級為1的個體,防止優秀個體被淘汰。

3 基于佳點集的蝙蝠定位算法試驗和分析

3.1 基于佳點集的蝙蝠定位算法試驗參數設置

為了驗證GBA算法在傳感器定位方面的性能,利用MATLAB2014進行仿真測試,已知300個節點(包括錨節點和未知節點),錨節點比例為10%,節點通信半徑為30m,隨機分布于100m×100m的區域內。將GBA的定位性能與未改進的蝙蝠算法(BA)、粒子群優化算法(PSO)進行對比實驗,并采用平均定位誤差(error)作為定位結果評價標準,error定義為:

(12)

在改進的蝙蝠算法中,初始響度和初始飛行速度在區間[0,1]內隨機產生,初始頻率均為0,其他參數如表1所示。

表1 蝙蝠參數

3.2 基于佳點集的蝙蝠定位算法試驗結果分析

3.2.1 隨機與佳點集的初始化比較

圖3分別給出了隨機分布點法和佳點集布點法兩種不同方法構造的含有300個二維點的初始種群分布圖。從圖中可以看出,采用佳點集方法產生的初始種群分布比隨機方法產生的初始種群要均勻,有著較好的多樣性,算法表現較穩定且始終保持初始種群良好的多樣性,從而避免出現早熟現象,最終收斂到全局最優。

圖3 種群初始化

3.2.2 GBA、BA與PSO的收斂速度對比

GBA、BA以及PSO在定位過程中適應度值的變化曲線如圖4所示,從圖4可以看出,相對于PSO算法以及BA算法,GBA的求解速度明顯加快,只需經過43次迭代就找到了適應度最大值,即尋找到未知節點的最優解,而未經改進的BA算法和PSO算法則分別經歷了70次和130次才尋找到最優解。對比結果表明,改進的BA算法在傳感器的定位過程中不僅有效降低了傳感器的定位誤差,而且加快了定位問題的求解速度,是一種速度快、精度高的傳感器定位算法。

圖4 GBA、BA及PSO收斂速度對比

3.2.3 不同的測距誤差的定位性能比較

在傳感器節點的定位算法中,測距誤差對未知節點的位置信息有著直接的影響。不同的測距誤差下GBA、BA以及PSO的平均定位誤差試驗數據如表2所示。從表2可知,在測距誤差為8%時,GBA算法的定位誤差趨于穩定,為12.1%;BA算法的定位誤差為26.1%,是GBA的2.16倍;PSO算法的定位誤差是58.44%,是GBA算法的4.83倍。且隨著測距誤差的增大,BA算法和GBA算法的定位誤差也隨之增大,其變化趨勢如圖5所示。相對于PSO算法和BA算法,GBA算法的定位誤差更小,可以有效的抑制節點測距誤差的累計,一定程度上提高了傳感器節點的定位精度。同時,GBA算法相對于BA算法有著更強的局部搜索能力和信息交換能力。

表2 不同測距誤差下的定位誤差試驗數據

圖5 測距誤差變化的定位性能比較

3.2.4 不同錨節點數量的定位性能比較

不同數量錨節點的情況下,GBA、BA、PSO的平均定位誤差變化曲線如圖6所示。從圖6可知,隨著錨節點數的不斷增加,GBA、BA及PSO的定位性能越來越好,平均定位誤差越來越小。當具有相同的錨節點時,GBA算法的定位誤差最小,PSO算法的定位誤差最大。增加相同數量錨節點時,GBA、BA、PSO算法的定位誤差量平均減少5.34%、4.98%、5.99%。雖然PSO算法隨著錨節點數的增加,定位誤差減小速度較快,易獲得較高的定位精度,但相應的錨節點成本也隨之增加。而改進的蝙蝠算法(GBA)在較小的錨節點密度下即能獲得較高的節點定位精度,錨節點相關成本較低?？梢娤鄬τ诹硗鈨煞N算法,在相同的定位精度的條件下,GBA降低了節點定位成本,具有更好的定位價值。

圖6 不同數量錨節點時的定位性能對比

4 結論

為了改進蝙蝠算法在無線傳感器應用中的定位性能,本文提出了一種基于佳點集的自適應蝙蝠定位算法,其優越性體現如下:

利用佳點集對傳統蝙蝠算法進行種群初始化,使得種群搜索節點更均勻,保持了種群良好的多樣性;采用部落機制避免了最優解陷入局部最優,加快了算法的收斂速度,提高了定位精度;引入了改進的更新策略,使得在較小錨節點密度下,即獲得較高的節點定位精度,同時還降低了錨節點相關成本。

通過對比仿真實驗分析,改進后的蝙蝠算法具有更快的收斂速度和良好的收斂性能。降低了測距誤差對定位的影響,提高了傳感器節點的定位精度,為無線傳感器節點定位提供了一種較好的解決方案。

[1]Liu Q,Huang S P. Deployment Strategy of Wireless Seneor Networks for Internet of Things[J]. China Communication 2011,8(8):111-120.

[2]Hang J,Xu H H,Duong T Q,et al. Localization Algorithms of Wireless Sensor Networks:A Survey[J]. Telecommunication Systems,2011.4(52):1-18.

[3]Qiao G,Li X,Zeng J.Design and Implement of RSSI Positioning System on TinyOS Platform[J]. Electronic Science and Technology,2013,26(2):90-93.

[4]Monir Vaghefi S Y,Vaghefi R M. A Novel Multilayer Neural Network Model for TOA-Based Localization in Wireless Sensor Networks[C]//The 2011 International Joint Conference on Neural Networks(IJCNN). IEEE,2011:3079-3084.

[5]Kaune R,Horst J,Koch W. Accuracy Analysis for TDOA Localization in Sensor Networks[C]//2011 Proceedings of the 14th International Conference on InformationFusion(FUSION). IEEE,2011:1-8.

[6]Jiang J R,Lin C M,Lin F Y,et al. ALRD:AOA Localization with RSSI Differences of Directional Antennas forwireless Sensor Networks[C]//2012 International Conference on Information Society(i-Society). IEEE,2012:304-309.

[7]Doherty L,El Ghaoui L.Convex Position Estimationin Wireless Sensor Networks[C]//INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE.IEEE,2001,3:1655-1663.

[8]Buja A,Swayne D F,Littman M,et al. XGvis:Interactive Data Visualization with Multidimensional Scaling[J]. Journal of Computational and Graphical Statistics,2004(5):21-53.

[9]彭宇,王丹. 無線傳感器網絡定位技術綜述[J]. 電子測量與儀器學報,2011,5(25):389-399.

[10]李牧東,熊搖偉,梁搖青. 基于人工蜂群改進算法的無線傳感器網絡定位算法[J]. 傳感技術學報.2013,26(2):241-245.

[11]曹欲曉,嚴奎,徐金寶. 一種最優錨節點集合上的兩重粒子群優化DV-HOP定位算法[J]. 傳感技術學報,2015,28(3):424-430.

[12]石欣,印愛民,張琦. 基于K最近鄰分類的無線傳感器網絡定位算法[J]. 儀器儀表學報,2014,10(35):2238-2247.

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

[14]黃光球,趙魏娟,陸秋琴. 求解大規模優化問題的可全局收斂蝙蝠算法[J]. 計算機應用研究,2013,30(5):1323-1328.

[15]李志俊,程家心. 免疫佳點集遺傳算法[J]. 計算機工程與應用,2007,43(28):37-40.

[16]肖赤心,蔡自心,王勇,等. 一種基于佳點集原理的約束優化進化算法[J]. 控制與決策,2009,24(2):249-253.

[17]梁昔明,陳富,龍文. 基于動態隨機搜索和佳點集構造的改進粒子群優化算法[J]. 計算機應用,2011,31(10):2796-2799.

[18]劉香品,宣士斌,劉峰. 引入佳點集和猴群翻過程的人工蜂群算法[J]. 模式識別與人工智能,2015,28(1):80-89.

[19]龍文,梁昔明,徐松金,等. 聚類佳點集交叉的約束優化混合進化算法[J]. 計算機研究與發展,2012,49(8):1753-1761.

A Positioning Algorithm Based on Bat Algorithm andGood-Point Setsin the Application of WSN*

XIEGuomin1*,GANYijun1,DINGHuiqiao2

(1.College of Electrical and Control Engineering,Liaoning Technical University,Huludao Liaoning 125105,China;2.Urumqi Power Supply Company,Xinjiang Autonomous Region,Urumqi 83000,China)

In order to solve the problem that node localization error in wireless sensor network(WSN)is large,this paper proposes a new bat positioning algorithm based on good point set. In the improved algorithm,the bat population individual is optimized by the good point set method,which can effectively improve the population diversity and prevent the algorithm from falling into the local optimum;The method by introducing tribal mechanism and adaptive updating can effectively avoid attracting the local optimal solution and expedite the convergence speed;Reconstructing the tribe by pareto classification can avoid eliminating the isolated outstanding individuals,enhance the generalization ability and improve the algorithm precision. By the simulation experiments on MATLAB,the results show that the improved algorithm has good convergence and searching performance,also reduces the influence of ranging error on positioning,and improves the nodes positioning accuracy. The algorithm is simple in implementation,high in precision and high in practical value.

bat algorithm;good-point set;tribal mechanism;WSN

謝國民(1969-)，男，遼寧阜新人，博士，副教授，研究生導師。主要從事電氣工程和智能檢測及電氣控制方面的研究工作，lngdxgm@163．com；干毅軍(1992-)，男，湖北武穴人，遼寧工程技術大學電氣與控制工程學院碩士研究生，主要研究方向為智能檢測與電氣控制，770827125@qq．com； 丁會巧(1991-)，女，河北滄州人，碩士研究生，主要研究指那個檢測與電氣控制?，F就職于國家電網烏魯木齊供電公司，313134949@qq．com。

項目來源:國家自然科學基金項目(51274118);遼寧省重點實驗室項目(LJZS003);遼寧省教育廳基金項目(UPRP20140464)

2017-01-06 修改日期:2017-03-10

TP391;TP212

A

1004-1699(2017)08-1252-06

C:7230

10.3969/j.issn.1004-1699.2017.08.021