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

鹿建銀，王華本

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

?

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

鹿建銀，王華本

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

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

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

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

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

1 DV-Hop算法分析

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

1.1 DV-Hop定位算法實現

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

(1)

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

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

dn=HopSize×hopi.

(2)

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

(3)

即可計算出未知節點的坐標

L=(ATA)-1ATb.

(4)

1.2 問題的提出

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

(5)

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

(6)

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

2 基于螢火蟲算法優化的DV-Hop算法

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

2.1 螢火蟲算法思路

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

2.2 FADV-Hop定位算法

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

(7)

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

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

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

(8)

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

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

(9)

(10)

3 仿真及結果分析

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

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

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

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

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

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

3.2 性能分析

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

圖1 信標節點:未知節點=2∶3的網絡拓撲

圖2 信標節點:未知節點=3∶2的網絡拓撲

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

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

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

4 結語

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

[1]王驥,林杰華,謝仕義,等.基于無線傳感網絡的環境監測系統[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]韓震,肖鐵軍.基于跳數修正的DV-Hop改進算法[J].電子科技,2015(1):158-163.

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

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

[7]付平.人工螢火蟲算法的參數分析與改進及其應用[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

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

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

TP212

A

2095-7602(2016)08-0034-05