鹿建銀，王華本

(安徽新華學院信息工程學院，安徽合肥 230088)

?

基于螢火蟲算法的FADV-Hop定位算法研究

鹿建銀，王華本

(安徽新華學院信息工程學院，安徽合肥 230088)

針對無線傳感器網(wǎng)絡中距離向量-跳距(Distance Vector-Hop，DV-Hop)定位算法中定位誤差積累、定位精度不高的缺陷，本文采用螢火蟲算法(Firefly Algorithm)的策略，提出一種FADV-Hop定位算法，將DV-Hop定位算法中定位精度不足的問題進行多維優(yōu)化。通過理論推理仿真，實驗結果表明，F(xiàn)ADV-Hop定位算法降低了定位誤差，提高了定位精度。

螢火蟲算法；DV-Hop；定位算法

目前，無線傳感器網(wǎng)絡[1]技術發(fā)展迅猛，已被廣泛地應用在軍事、智能家居、智慧養(yǎng)老、地理環(huán)境監(jiān)測等領域，并且成為智慧城市建設研究的熱點之一。無線傳感器網(wǎng)絡定位技術是基于位置服務所要解決的關鍵問題。無線傳感器網(wǎng)絡定位算法主要有基于測距和無需測距兩大類，其中，基于測距的無線傳感器定位算法需要區(qū)域中無線設備的相對角度或者到達時間等信息對未知節(jié)點進行定位，定位結果比較精確，但是以花費大量的人力、物力、財力為代價?；跍y距的無線傳感器網(wǎng)絡定位算法主要有RSSI、TOA、AOA[2]等算法。測距無關的無線傳感器網(wǎng)絡定位算法是無需投入大量的設備和人力，定位效果主要取決于無線傳感器網(wǎng)絡中未知節(jié)點和信標節(jié)點的連通性，以及從鄰居節(jié)點獲取跳距等信息進行協(xié)助，達到實現(xiàn)對未知節(jié)點定位的目標，成本較低，定位精度不高，但是在很多場合下定位效果能夠滿足人們需求。因此，無需測距的定位算法具有被廣泛推行的趨勢。

DV-Hop定位算法[3]是目前被廣泛應用的無需測距的無線傳感器網(wǎng)絡定位算法，定位精度不高，但易于實現(xiàn)。針對DV-Hop算法中存在積累誤差大、定位精度不高的不足，已經(jīng)有很多研究學者提出了多種改進措施。韓震[4]提出了一種基于跳數(shù)修正的改進算法，但要結合RSSI技術，增加了網(wǎng)絡通信技術的復雜度。王洪元[5]提出了一種基于粒子群算法的優(yōu)化方案，定位精度有所改進，但要引入信號測量儀器，增加了硬件開銷。吳玉成[6]提出了一種基于最優(yōu)節(jié)點通信半徑的優(yōu)化措施，計算量并沒有增大，但以先分析網(wǎng)絡拓撲結構為前提，導致網(wǎng)絡收斂速度不夠靈活。因此，本文基于螢火蟲算法，提出FADV-Hop改進方案，將原有的定位精度不足問題轉(zhuǎn)化為多維優(yōu)化問題并進行求解。

1 DV-Hop算法分析

DV-Hop定位算法是由Dragos等人提出的一種基于距離矢量路由的無線傳感器網(wǎng)絡定位算法，它結構簡單，即使受自然環(huán)境等因素制約，對定位性能的影響不大，且成本較低，因此DV-Hop算法在不同環(huán)境得到了普遍應用。DV-Hop定位算法過程簡述為三步：計算平均每跳距離；計算最小跳數(shù)；計算未知節(jié)點的坐標值。

1.1 DV-Hop定位算法實現(xiàn)

首先，網(wǎng)絡中每個信標節(jié)點相互廣播，獲得網(wǎng)絡中其它信標節(jié)點的位置信息和到達的最小跳數(shù)，根據(jù)得到的跳數(shù)及其它信標節(jié)點的位置信息計算出平均每跳距離。

(1)

其中，對于信標節(jié)點i(xi,yi)、信標節(jié)點j(xj,yj)，hopij表示第i個、第j個信標節(jié)點之間的最小跳數(shù)。

其次，每個未知節(jié)點n獲得平均每跳距離HopSize，最小跳數(shù)hopi，便可計算與其它信標節(jié)點的距離dn。

dn=HopSize×hopi.

(2)

最后，計算未知節(jié)點的坐標值。(x1,y1),(x2,y2),…,(xn,yn)分別表示信標節(jié)點1至n的坐標值，未知節(jié)點到信標節(jié)點1,2,…,n之間的距離分別為d1,d2,…,dn。前n-1個式子依次減去第n個式子的結果，并線性化方程組AL=b，且令

(3)

即可計算出未知節(jié)點的坐標

L=(ATA)-1ATb.

(4)

1.2 問題的提出

通過以上分析，可以求出一個未知節(jié)點的坐標，但是通過上述方式求得的未知節(jié)點坐標，由于平均跳距存在誤差，以及多跳誤差積累等因素，DV-Hop定位精度并不十分精確，但觀察式(6)中每個元素都出現(xiàn)dn，它表示未知節(jié)點與信標節(jié)點之間的距離，因此，只要保證dn越趨近真實值，最終得到未知節(jié)點的坐標值就越精確，更接近實際。但DV-Hop算法求解時，并不考慮dn誤差對定位精度所帶來的影響，dn存在誤差，又由于多跳，誤差累積，那么最終得到的結果誤差也會更大，從而大大影響定位性能。所以，DV-Hop定位算法是以犧牲定位精度來簡化定位過程的難度為代價的，從而很難得到預期定位效果。因此，筆者提出螢火蟲FADV-Hop定位算法，將坐標線性求解轉(zhuǎn)換為二維組合優(yōu)化問題來解決DV-Hop定位算法定位精度不高的缺陷。

(5)

適應度Fitness()函數(shù)用來表示未知節(jié)點與所有信標節(jié)點的誤差之和：

(6)

其中，n是無線傳感器網(wǎng)絡中信標節(jié)點的個數(shù)。由以上推論可知，當適應度Fitness()函數(shù)的值越小時，定位效果越精確。

2 基于螢火蟲算法優(yōu)化的DV-Hop算法

上文將問題從求解線性方程組轉(zhuǎn)化成求解多維優(yōu)化問題，下面討論使用螢火蟲算法的優(yōu)化求解該問題的過程。

2.1 螢火蟲算法思路

2008年，劍橋大學學者Yang Xinshe提出螢火蟲算法(FIREFLY，Algorithmic，F(xiàn)A)[7],它是一種基于自然啟發(fā)的群智能算法，是一種模仿自然界螢火蟲發(fā)光行為的仿生學智能算法，螢火蟲通過發(fā)光來吸引配偶進行繁衍，也有研究學者認為螢火蟲的發(fā)光行為對于捕食獵物同樣可用。但不管是哪一種說法，螢火蟲的發(fā)光行為都要遵循以下規(guī)則：第一，每只螢火蟲被其它螢火蟲所吸引的機會等同。光亮弱的螢火蟲個體會被光亮強的個體所吸引并朝之飛行；第二，螢火蟲所發(fā)出的光在傳播中會被空氣等媒體進行一定程度上的弱化，即隨著螢火蟲之間的距離逐漸增加，吸引力和亮度都會逐漸減??；第三，螢火蟲的亮度由智能算法中的目標函數(shù)限制并決定，如果螢火蟲的可視區(qū)域內(nèi)沒有比自己更亮的個體，螢火蟲將實施自由飛行策略。

2.2 FADV-Hop定位算法

在螢火蟲算法中，每一個體都是問題的一個可行解，包括吸引度、發(fā)光亮度、位置等屬性。個體的初始亮度就是引入這個個體所表示的可行解后得到的適應度函數(shù)(Fitness())的解。每個位置上的螢火蟲個體亮度是固定不變的，并且當前個體在其它位置上的亮度隨著距離的增大而減小，并且被傳輸媒體吸收率所影響，在本文中由于編碼取值范圍較低，要在一定程度上減弱亮度在傳播過程中的衰減量，因此，將當前個體在距離r處的位置亮度I(r)如下：

(7)

其中，I0表示螢火蟲初始亮度，γ是傳輸媒體的吸收率(即光亮吸收系數(shù)，表示熒光隨距離的增加和傳輸媒體吸收的光亮減弱程度)，r是兩個個體之間的距離，這里使用歐式距離進行計算。

個體之間的吸引力β也是相對的，其大小受到傳播距離r和傳輸媒體吸收率γ的局限，當前個體在距離r處位置上的吸引力為：

β(r)=β0e-γr2.

(8)

其中，β0是光源(r=0時)的吸引力，γ是傳輸媒體的吸收率。

當前個體i在可視范圍中發(fā)現(xiàn)比自己更亮的個體j時，使用式(10)對個體位置進行更新如下：

(9)

(10)

3 仿真及結果分析

FADV-Hop定位算法網(wǎng)絡仿真的區(qū)域是100m×100m，節(jié)點通信半徑r設置為30m。根據(jù)以往學者的研究經(jīng)驗，本文對螢火蟲算法中的各個參數(shù)設置初值如下：個體初始吸引度β0設置為1.0,隨機參數(shù)α設置為0.9，傳輸媒體吸收率γ由于編碼范圍過大，通過多次實驗對比，設置為0.009，算法迭代次數(shù)設置為50次。為了證明這里所提出的FADV-Hop算法在無線傳感器網(wǎng)絡定位中的優(yōu)越性，采用DV-Hop算法作為實驗對比。

3.1 基于螢火蟲算法改進DV-Hop算法

仿真區(qū)域內(nèi)有m個通信節(jié)點，其中有n個信標節(jié)點，那么未知節(jié)點數(shù)為(m-n)個，信標節(jié)點的位置信息已知,將螢火蟲算法引入DV-Hop算法中對未知節(jié)點進行定位，流程如下：

第一步，使用式(1)計算每個信標節(jié)點的平均每跳距離。

第二步，每個未知節(jié)點從距離跳數(shù)最小的信標節(jié)點處獲得平均每跳距離，并使用式(2)計算到每個信標節(jié)點的距離。根據(jù)式(7)計算適應度Fitness()函數(shù)。

第三步，初始化種群，設置迭代次數(shù)t=0、I0、α、β0等參數(shù)，以及種群大小、最大迭代次數(shù)Tmax等。對于當前個體，如果有比自己更亮的個體存在，則對當前位置按式(10)進行更新，否則自由飛行。t=t+1，若t=Tmax，算法結束。

3.2 性能分析

圖1為信標節(jié)點與未知節(jié)點的比例為2∶3的拓撲圖，圖2為信標節(jié)點與未知節(jié)點的比例為3∶2的拓撲圖。兩圖中星號表示信標節(jié)點，圓點表示未知節(jié)點。

圖1 信標節(jié)點:未知節(jié)點=2∶3的網(wǎng)絡拓撲

圖2 信標節(jié)點:未知節(jié)點=3∶2的網(wǎng)絡拓撲

圖3表示不同節(jié)點密度(3∶2)和平均定位誤差之間的變化關系，節(jié)點平均誤差計算由式(11)計算得出。DV-Hop定位算法中平均定位誤差為8.1614, FADV-Hop定位算法中平均定位誤差為3.2415。

圖3 不同節(jié)點密度(2∶3)和平均定位誤差

圖4表示信標節(jié)點與未知節(jié)點的分布比例為3∶2的場景下，F(xiàn)ADV-Hop和DV-Hop平均定位誤差對比分析，DV-Hop的平均定位誤差為7.6639, FADV-Hop的平均定位誤差為4.6353。

4 結語

綜上所述，本文在DV-Hop算法的基礎上，針對其中存在平均每跳距離的計算所帶來的定位誤差，基于螢火蟲算法，提出FADV-Hop定位算法，并給出具體改進策略、理論推理和實驗證明，得出結論：在同等網(wǎng)絡環(huán)境下，F(xiàn)ADV-Hop算法的定位精度明顯提高。

[1]王驥,林杰華,謝仕義,等.基于無線傳感網(wǎng)絡的環(huán)境監(jiān)測系統(tǒng)[J].傳感技術學報,2015(11):1732-1740.

[2]楊陽,毛永毅,鄭敏.基于小波變換的AOA定位算法[J].微型機與應用,2014(3):47-49,54.

[3]Xiaoyin Li,Lianshan Yan,Wei Pan,et al.Optimization of DV-Hop localization algorithm in hybrid optical wireless sensor networks[J].Journal of Heuristics,2015(21):177-195.

[4]韓震,肖鐵軍.基于跳數(shù)修正的DV-Hop改進算法[J].電子科技,2015(1):158-163.

[5]王洪元,焦筱悛,王天成.基于自適應粒子群優(yōu)化算法的節(jié)點定位研究[J].化工自動化及儀表,2014(3):267-270.

[6]吳玉成,李江雯.基于最優(yōu)節(jié)點通信半徑的改進DV-Hop定位算法[J].華南理工大學學報2012(6):36-42.

[7]付平.人工螢火蟲算法的參數(shù)分析與改進及其應用[D].南昌:華東交通大學,2014.

A New FADV-Hop Location Algorithm Based on Firefly Algorithm

LU Jian-yin, WANG Hua-ben

(Anhui Xinhua University, Hefei Anhui 230088, China)

In Wireless Sensor Network Distance Vector-Hop localization algorithm in positioning error accumulation, defects of the positioning accuracy is not high, the Firefly algorithm strategy, a FADV-Hop location algorithm is proposed, into the problem of DV- Hop localization algorithm in positioning accuracy is insufficient for multidimensional optimization problem. By theoretical and simulation results, the experimental results show that the FADV-Hop positioning algorithm reduces the positioning error and improves the positioning accuracy.

Firefly Algorithm; DV-Hop; localisation algorithm

2016-03-09

安徽省重點自然科學研究項目“智慧旅游平臺——物聯(lián)網(wǎng)位置感知服務在旅游行業(yè)的應用”(KJ2014A096)；國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目“基于位置感知服務的創(chuàng)新與研究”(201412216019)。

鹿建銀(1975- )，女，副教授，碩士，從事無線傳感器網(wǎng)絡研究。

TP212

A

2095-7602(2016)08-0034-05