基于蛙跳算法的無線傳感器網(wǎng)絡(luò)定位.docx

劉杰慧，等 基于蛙跳改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位基于蛙跳改進(jìn)算法的無線傳感器網(wǎng)絡(luò)定位*劉杰慧，王穎，謝萍，王茜（華北電力大學(xué) 控制與計(jì)算機(jī)工程學(xué)院，北京市102206）摘要：針對(duì)無線傳感器網(wǎng)絡(luò)（WSNs）定位過程當(dāng)中傳統(tǒng)的DV-Hop定位算法在計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)之間的平均跳距時(shí)存在較大誤差的問題，本文根據(jù)蛙跳算法（SFLA）計(jì)算速度快，全局搜索尋優(yōu)能力強(qiáng)的優(yōu)勢(shì)，結(jié)合定位的實(shí)際問題，提出了一種改進(jìn)的蛙跳算法。并將其引入到DV-Hop的算法設(shè)計(jì)中，實(shí)現(xiàn)節(jié)點(diǎn)的定位。關(guān)鍵詞：蛙跳算法、無線傳感器網(wǎng)絡(luò)、節(jié)點(diǎn)定位、DV-Hop算法Wireless sensor network localization based on improved algorithm leapfrogLIU Jie-hui,WANG Ying,XIE Ping,WANG Xi(School of control and computer engineering, north china electric power university, Beijing, 102206)Abstract：Exists for wireless sensor networks (WSNs) positioning process of traditional DV-Hop localization algorithm to calculate the average jump between anchor nodes and unknown nodes from the problem when large errors, according to leapfrog algorithm (SFLA) computing speed, global Search optimization capability advantages, combined with the practical problems locating proposed an improved leapfrog algorithm. And introduced into the DV-Hop algorithm design, the realization of positioning nodes.Keyword：Leapfrog algorithm, wireless sensor network, the node localization, DV - Hop algorithm0. 引言無線傳感器網(wǎng)絡(luò)（WSN）1,2 是一種新的獲取信息和處理信息的技術(shù)。其在入侵監(jiān)測(cè)、目標(biāo)跟蹤和定位相關(guān)領(lǐng)域有廣泛的應(yīng)用前景。無線傳感器網(wǎng)絡(luò)的許多應(yīng)用都需要傳感器節(jié)點(diǎn)明確其自身的位置信息，缺少位置信息的監(jiān)測(cè)消息幾乎沒有什么價(jià)值。這里必須解決的關(guān)鍵問題是如何確定無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息。因此，定位技術(shù)3-5作為無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，其定位算法也引起了國內(nèi)外越來越多學(xué)者的普遍關(guān)注。目前的無線傳感器網(wǎng)絡(luò)定位技術(shù)大體可分為兩類，分別是基于測(cè)距和非測(cè)距的定位技術(shù)。DV-Hop算法6是現(xiàn)有應(yīng)用最廣泛的無需測(cè)距定位算法之一，但是該算法的定位精度不是很理想。就這一問題，已經(jīng)有很多專家學(xué)者對(duì)其進(jìn)行了改進(jìn)。文獻(xiàn)7提出由改進(jìn)DV-Hop算法得到的估算位置然后再利用粒子群優(yōu)化算法對(duì)其進(jìn)行校正。將定位問題看成一個(gè)多維優(yōu)化問題。文獻(xiàn)8在分析了DV-Hop算法中多邊測(cè)量法的基礎(chǔ)上，提出了一種自適應(yīng)人工蜂群算法，并將其應(yīng)用于未知節(jié)點(diǎn)坐標(biāo)的計(jì)算階段，實(shí)現(xiàn)節(jié)點(diǎn)定位。文獻(xiàn)9針對(duì)DV-Hop的一種經(jīng)典改進(jìn)算法LPC中對(duì)影響定位精度的三個(gè)重要參數(shù)：錨節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)數(shù)目、節(jié)點(diǎn)通信半徑，進(jìn)行了進(jìn)一步優(yōu)化提高了定位精度。文獻(xiàn)10針對(duì)DV-Hop算法中平均每跳距離的計(jì)算方式進(jìn)行了改進(jìn)，利用蛙跳算法來求解平均每跳距離，使其更接近實(shí)際值，從而提高最終定位結(jié)果的精確度。本文針對(duì)DV-Hop算法在計(jì)算未知節(jié)點(diǎn)坐標(biāo)是精度不高這一缺陷，將節(jié)點(diǎn)定位問題轉(zhuǎn)化成最優(yōu)化求解問題，結(jié)合蛙跳算法的優(yōu)勢(shì)，并對(duì)蛙跳算法進(jìn)行了改進(jìn)，將改進(jìn)后的蛙跳算法應(yīng)用到DV-Hop算法中，提出了一種基于改進(jìn)蛙跳算法的DV-Hop改進(jìn)方案。通過仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法較傳統(tǒng)DV-Hop算法在精度和穩(wěn)定性上均有明顯的提高。 2.DV-Hop算法DV-Hop算法是由美國路特葛斯大學(xué)的Dragos Niculescu等人根據(jù)距離矢量路由和GPS定位的思想提出的一種分布式定位算法。其定位過程分為三個(gè)步驟：1) 計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的最小跳數(shù)。每個(gè)錨節(jié)點(diǎn)采用距離矢量路由協(xié)議向范圍內(nèi)的鄰居節(jié)點(diǎn)廣播其位置信息，其中包括錨節(jié)點(diǎn)的坐標(biāo)和跳數(shù)，跳數(shù)的初始值為0，接收節(jié)點(diǎn)記錄到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，忽略相同錨節(jié)點(diǎn)的較大的跳數(shù)信息，將跳數(shù)加1后轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，最終獲得全網(wǎng)每個(gè)節(jié)點(diǎn)到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)。2) 計(jì)算未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。每個(gè)錨節(jié)點(diǎn)根據(jù)到其它錨節(jié)點(diǎn)的坐標(biāo)信息和最小跳數(shù)，根據(jù)下式計(jì)算出平均跳距： (1)式（1）中，Hopsizei是第i個(gè)錨節(jié)點(diǎn)的平均跳距，（xi，yi），（xj，yj）分別為錨節(jié)點(diǎn)i，j的坐標(biāo)，Sij為錨節(jié)點(diǎn)i與j之間的跳數(shù)。錨節(jié)點(diǎn)計(jì)算出平均跳距后并將其廣播至網(wǎng)絡(luò)中，未知節(jié)點(diǎn)只記錄接收到的第一個(gè)平均跳距信息，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。未知節(jié)點(diǎn)接收到平均跳距后，就可以根據(jù)式（2）計(jì)算出到錨節(jié)點(diǎn)的距離： (2)其中，di為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離，Si為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的最小跳數(shù)。3) 當(dāng)估算出未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離后便可利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。式(2)中的di還可以用下列式子表示： (3)將方程組中（m-1）個(gè)方程分別減去第m個(gè)方程之后得到的方程組可用線性表達(dá)式AX=b表示，其中X=（x，y）T， (4) (5)使用標(biāo)準(zhǔn)的最小二乘法可以得到方程組的最小二乘解為 (6)綜上所述，由于測(cè)距誤差、環(huán)境因素、通信等因素的影響，di的值總存在一定誤差，影響了算法整體的定位精度。3. 混合蛙跳算法的DV-Hop算法改進(jìn)3.1 蛙跳算法描述蛙跳算法(SFLA)是一種基于群體智能的生物進(jìn)化算法11-13。蛙跳算法模擬了青蛙群體尋找食物時(shí)按子群分類進(jìn)行信息交換的過程，將全局搜索與子群局部搜索相混合，使SFLA能夠收斂于全局最優(yōu)解。蛙跳的基本思想是：1）種群劃分設(shè)有M只蛙組成初始種群體S=X1,X2,XM,P維解空間中的第只蛙表示為Xi=Xi1,Xi2,Xip,在生成初始種群后，按適應(yīng)度降序排列種群內(nèi)的青蛙，并將整個(gè)種群劃分成n個(gè)子群，每個(gè)子群包含k只青蛙，滿足關(guān)系Mnk；其中第1只青蛙分入第1子群，第2只青蛙分入第2子群，第n只青蛙分入第n子群，第n+1只青蛙分入第1子群，第n+2 只青蛙分入第 2 子群。依此類推，直到所有的M只青蛙劃分完畢。設(shè) Mj表示第j個(gè)族群青蛙的集合，則有 (7)2）局部搜索令每個(gè)子群中有最好適應(yīng)值和最差適應(yīng)值的青蛙分別記為和，所有子群中適應(yīng)度最好值的青蛙表示為，然后對(duì)每個(gè)子群進(jìn)行局部搜索，即只對(duì)SFLA算法規(guī)定的每個(gè)族群中適應(yīng)度值最差的解進(jìn)行更新，更新策略公式如下: (8) (9)其中，Di表示分量i上移動(dòng)的距離（1ip），Dmax表示青蛙所允許改變位置的最大值 ，Xnew為更新后的解，r為0到1之間的隨機(jī)數(shù)。如果Xnew優(yōu)于Xw，則令Xw=Xnew，否則，用代替重新按公式（8），（9）執(zhí)行更新策略，若Xnew仍不能優(yōu)于Xw，則隨機(jī)產(chǎn)生一個(gè)新的解取代Xw，重復(fù)上述過程，直到達(dá)到設(shè)定的局部搜索次數(shù)為止。3）全局信息交換當(dāng)全部的子群完成局部搜索后，將全部子群中的青蛙再混合并重新執(zhí)行劃分子群、局部搜索，如此重復(fù)直至達(dá)到事前設(shè)定好的中止條件（最大混合次數(shù)或搜索到最優(yōu)解）。3.2 改進(jìn)的蛙跳算法在傳統(tǒng)蛙跳算法中，由于r的設(shè)置僅是在0,1之間的隨機(jī)數(shù)，沒有考慮到位置更新，具有較大的隨機(jī)性，導(dǎo)致在尋優(yōu)過程中存在收斂速度較慢、搜索精度低的問題，嚴(yán)重影響了算法的性能。在位置更新時(shí)，較大的r有利于跳出局部極小值點(diǎn)，而較小的r有利于算法的收斂。通常較好的方法是在算法的初期使用較大的r以通過較高的探索能力得到較優(yōu)的解，而在后期則需要較小的r值，加快其收斂速度。因此將設(shè)計(jì)為迭代次數(shù)逐漸遞減的函數(shù)，r的設(shè)置如下： (10)其中，rmin為初始權(quán)重，rmax為終止權(quán)重，Cmax為最大迭代次數(shù)，C為當(dāng)前迭代次數(shù)，則（8）式更新為： (11)文獻(xiàn)14給出用來提高局部搜索空間的青蛙粒子更新策略，但這種更新策略仍然只采用，因此并沒有提高青蛙學(xué)習(xí)能力。本文在每個(gè)族群進(jìn)行局部深度搜索時(shí)，結(jié)合粒子群算法更新思想，將上一次更新的移動(dòng)距離引入到分量i上移動(dòng)的距離上，和歷史最優(yōu)個(gè)體k，因此，（11）式變成： (12) (13)其中，上一次分量i上更新時(shí)移動(dòng)的距離用Di表示，Di表示本次分量i上更新時(shí)移動(dòng)的距離，群體初始化時(shí)，隨機(jī)產(chǎn)Di生。與(13)式相比，(12)式不僅加大了算法搜索范圍，還具備了初步的學(xué)習(xí)能力。執(zhí)行更新策略，若Xnew不能優(yōu)于Xw，則按下式計(jì)算移動(dòng)距離： （14）在傳統(tǒng)的蛙跳算法中，如果經(jīng)過局部或全局最優(yōu)解更新后若Xnew仍不能優(yōu)于Xw，則隨機(jī)產(chǎn)生新的個(gè)體替代Xw，這個(gè)隨機(jī)產(chǎn)生的個(gè)體增加了算法盲目性，為了改進(jìn)這一問題，文章通過高斯變異取代隨機(jī)產(chǎn)生青蛙個(gè)體的方法，高斯變異是指在原來的個(gè)體的基礎(chǔ)上增加一個(gè)服從高斯分布的隨機(jī)擾動(dòng)，其公式如下： (15)其中,N(0，1) 為服從均值為0，均方差為1的高斯分布。3.3改進(jìn)DV-Hop定位算法通過對(duì)DV-Hop算法的定位過程分析可知，由于外界因素及內(nèi)部測(cè)量的誤差，導(dǎo)致在算法的第三階段測(cè)量錨節(jié)點(diǎn)與未知節(jié)點(diǎn)間距離時(shí)產(chǎn)生誤差，因此這就使得di的誤差較大。設(shè)Fi為測(cè)距的誤差，則，再由公式（3）可得： (16)從以上求解的過程可以看出，如果使（x，y）最接近真實(shí)值，總誤差最小，那么就得在由公式（16）計(jì)算出來的F(x,y)取最小值，這樣就把節(jié)點(diǎn)定位問題變成全局最優(yōu)化求解問題。 在蛙跳算法中適應(yīng)度函數(shù)的設(shè)定是尋優(yōu)求解過程中的關(guān)鍵問題，在錨節(jié)點(diǎn)與未知節(jié)點(diǎn)測(cè)距的過程中產(chǎn)生的誤差通常與兩節(jié)點(diǎn)間的距離有關(guān)，即距離越小，產(chǎn)生的誤差越小。距離越大，產(chǎn)生的誤差越大。因此，本文根據(jù)錨節(jié)點(diǎn)距離未知位節(jié)點(diǎn)的遠(yuǎn)近來給定權(quán)值的大小，給定的權(quán)值越大表示距離未知位節(jié)點(diǎn)越近，相反越小，不同位置的錨節(jié)點(diǎn)對(duì)定位結(jié)果的影響用給定權(quán)值的方法來控制?；谝陨戏治?，本文給定的適應(yīng)度函數(shù)為： (17)其中，cj表示未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間距離di的倒數(shù)。由公式(17)可知，未知節(jié)點(diǎn)坐標(biāo)受誤差的影響將被降到最低，這樣就提高了坐標(biāo)計(jì)算的準(zhǔn)確度。綜上所述，本文提出的基于改進(jìn)蛙跳算法的SFDV-Hop定位算法流程如圖1所示。圖1 SFDV-Hop定位算法流程圖4.仿真實(shí)驗(yàn)結(jié)果分析4.1仿真實(shí)驗(yàn)設(shè)計(jì)本文的實(shí)驗(yàn)在Matlab平臺(tái)上進(jìn)行，假設(shè)節(jié)點(diǎn)隨機(jī)分布在一個(gè)100m100m的網(wǎng)絡(luò)區(qū)域內(nèi)，并隨機(jī)產(chǎn)生未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的坐標(biāo)，每個(gè)節(jié)點(diǎn)的通信半徑R=20m，改進(jìn)蛙跳算法中種群大小100，子群個(gè)數(shù)10，子群內(nèi)最大搜索次數(shù)為10，最大全局搜索次數(shù)為200，rmin=0.4，rmax=1.2，r的初始值設(shè)為1，本文分別從平均定位誤差均方差和歸一化平均定位誤差兩個(gè)指標(biāo)來衡量算法的定位精確度和穩(wěn)定性。節(jié)點(diǎn)隨機(jī)分布圖如圖2所示。圖2節(jié)點(diǎn)隨機(jī)分布圖假設(shè)各次仿真時(shí)各網(wǎng)絡(luò)參數(shù)均不變，令仿真的次數(shù)為k，未知節(jié)點(diǎn)的個(gè)數(shù)為n，節(jié)點(diǎn)個(gè)數(shù)為M，第i個(gè)節(jié)點(diǎn)的實(shí)際坐標(biāo)和估算坐標(biāo)分辨用pi和qi表示，則一次實(shí)驗(yàn)中所有未知定位節(jié)點(diǎn)的平均定位誤差和定位誤差的均方差分別為： (18) (19)其中，式（18）中的e表示的平均定位誤差，式（19）中的為所有未知定位節(jié)點(diǎn)定位誤差的均方差。令R為節(jié)點(diǎn)的通信半徑，則基于k次實(shí)驗(yàn)統(tǒng)計(jì)的歸一化平均定位誤差為： (20)基于k次實(shí)驗(yàn)統(tǒng)計(jì)的歸一化的平均定位誤差的均方差分別為： (21)為了客觀地表現(xiàn)改進(jìn)DV-Hop算法的定位性能，通過k=500次仿真實(shí)驗(yàn)，將改進(jìn)算法(SFDV-Hop) 與DV-Hop算法進(jìn)行對(duì)比。4.2實(shí)驗(yàn)結(jié)果及分析圖3顯示了錨節(jié)點(diǎn)所占比例在10%-40%時(shí)，由式(20)計(jì)算出的平均定位誤差變化情況；圖4顯示了錨節(jié)點(diǎn)比例變化時(shí)，由式(21) 計(jì)算出的歸一化平均定位誤差均方差變化情況。從圖3、4可以看出：在節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)通信半徑不變的情況下，兩種算法的平均定位誤差和均方差均都隨著錨節(jié)點(diǎn)比例的增加而減小，并逐漸趨于平穩(wěn)；另外，在相同條件下，SFDV-Hop的平均定位誤差和均方差都明顯小于DV-Hop。 圖3錨節(jié)點(diǎn)數(shù)量與平均定位誤差的關(guān)系圖4錨節(jié)點(diǎn)數(shù)量與定位誤差的均方差關(guān)系圖5和圖6是在實(shí)驗(yàn)固定錨節(jié)點(diǎn)比例為10%，節(jié)點(diǎn)總數(shù)從50到400變化的情況下，對(duì)不同算法的性能進(jìn)行了比較，圖5、6分別顯示了由式(20)計(jì)算出的歸一化平均定位誤差變化情況；由式(21) 計(jì)算出的平均定位誤差標(biāo)準(zhǔn)差變化情況。從圖 5、6圖可以看出，在錨節(jié)點(diǎn)比例不變的情況下，定位算法的平均定位誤差、定位誤差均方差都隨節(jié)點(diǎn)個(gè)數(shù)的增加而逐漸遞減。另外，可以明顯的看出SFDV-Hop算法的平均定位誤差和均方差都明顯小于DV-Hop算法。圖5節(jié)點(diǎn)個(gè)數(shù)與歸一化定位算法的平均誤差關(guān)系圖6節(jié)點(diǎn)個(gè)數(shù)與歸一化定位算法誤差的均方差關(guān)系從以上的結(jié)果分析可以看出SFDV-Hop算法在定位的精確度和穩(wěn)定性方面都優(yōu)于DV-Hop算法，說明了將改進(jìn)蛙跳算法應(yīng)用在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位上是一種可行的方案，有效地提高了傳統(tǒng)DV-Hop算法的全局搜索能力和收斂速度。5.結(jié)論本文在分析DV-Hop算法中定位過程的基礎(chǔ)上，將節(jié)點(diǎn)定位問題轉(zhuǎn)化為最優(yōu)化求解問題，并利用蛙跳算法在解決最優(yōu)化問題的優(yōu)勢(shì)，結(jié)合具體問題，對(duì)蛙跳算法進(jìn)行改進(jìn)，并提出了基于改進(jìn)蛙跳算法的DV-Hop算法，該定位算法實(shí)現(xiàn)簡單，搜索速度快。通過仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的DV-Hop算法相比，在不同錨節(jié)點(diǎn)數(shù)目和節(jié)點(diǎn)個(gè)數(shù)的情況下，改進(jìn)的算法能明顯的減小定位時(shí)出現(xiàn)的誤差，使定位的精度和穩(wěn)定性得到了有效的提高。參考文獻(xiàn)：1彭宇,王丹. 無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述J. 電子測(cè)量與儀器學(xué)報(bào),2011,05:389-399.2周雅琴,譚定忠. 無線傳感器網(wǎng)絡(luò)應(yīng)用及研究現(xiàn)狀J. 傳感器世界,2009,05:35-40.3郭小華. 基于無線傳感器網(wǎng)絡(luò)的車輛定位技術(shù)研究J. 自動(dòng)化技術(shù)與應(yīng)用,2009,01:74-77+73.4汪苑,林錦國. 幾種常用室內(nèi)定位技術(shù)的探討J. 中國儀器儀表,2011,02:54-57.5劉瀟,劉幸,吳勝華. 基于RFID的智能家居用戶識(shí)別定位技術(shù)分析J. 物聯(lián)網(wǎng)技術(shù),2011,09:60-62.6張震,閆連山,劉江濤,李曉銀. 基于DV-hop的無線傳感器網(wǎng)絡(luò)定位算法研究J. 傳感