基于萤火虫算法的FADV-Hop定位算法研究

2016-11-21鹿建银王华本

长春师范大学学报 2016年8期

关键词：信标定位精度萤火虫

鹿建银，王华本

(安徽新华学院信息工程学院，安徽合肥 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