基于人工鱼群算法的改进质心定位算法

汪 晨，张玲华

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003； 2.江苏省通信与网络技术工程研究中心，江苏 南京 210003)

0 引 言

无线传感器网络[1]是一种分布式自组织网络，由于网络的部署方式，传感器节点通常无法知道自身的位置[2]，例如由飞机向监测区域抛撒传感器节点。但是节点位置信息是大多数无线传感器网络应用的关键，一方面监测消息如果不携带位置信息往往是毫无意义的，另一方面节点位置信息还是众多无线传感器网络技术的基础，如负载均衡、拓扑配置[3]等。

通常情况下，无线传感器网络定位算法可分为两类：基于距离的(range-based)和距离无关的(range-free)[4]。基于距离的定位算法[5]使用到达角度或RSSI等技术测量点到点之间的距离；距离无关的定位算法[6]则利用跳数或网络连通度等信息来估计未知节点的坐标，因此它在成本和功耗方面与前者相比具有一定优势[7]。

文中提出了一种基于人工鱼群算法优化的节点定位算法，先利用加权质心算法获取待定位节点和锚节点的距离信息，然后利用多边定位算法构建误差函数，最后采用人工鱼群算法对误差函数进行优化以获得更好的定位精度。

1 人工鱼群算法

1.1 基本思想

人工鱼群算法是一种新型的智能优化算法[8]，其基本思想是:根据水域中鱼的数目最多的地方所含营养物质最多的特点，模仿鱼的聚群、觅食、追尾等行为，利用局部最优，经过逐步迭代、优化达到全局寻优。具体过程描述如下:随机生成n只人工鱼(候选解空间)组成初始种群;第i条人工鱼候选解表示为Xi=(xi1,xi2,…,xin)，其中d表示解的维数[9]；根据初始种群内的适应度对种群进行初始化设置，包括每条人工鱼的初始位置、人工鱼的视野Visual、人工鱼的步长Step、最大迭代次数IT、尝试次数Tn、拥挤度因子δ和要执行吞食行为的阈值T_value[10-11]。

假定第i条人工鱼当前位置为Xi(t)，下一个状态为Xi(t+1)，每次迭代人工鱼都选择一种行为来更新自己的位置信息，即在原位置Xi(t)的基础上加上一个增量ΔXi(t+1)。

人工鱼群算法的位置更新公式为[12]：

ΔXi(t+1)=Rand()*Step*[Xbetter(t+1)-Xi(t)]

(1)

Xi(t+1)=Xi(t)+ΔXi(t+1)

(2)

其中，Rand()是0到1之间产生的随机数；Xbetter(t+1)为更好的人工鱼位置。

经过上述更新公式，如果Xi(t+1)比Xi(t)更好，则用Xbetter(t+1)替换Xi(t+1)，否则根据式1和式2进行下次迭代更新，直到迭代结束或搜索到全局最优解。

1.2 人工鱼的基本行为描述

(1)觅食行为。

设Xi为人工鱼i的当前状态，Xj为人工鱼i在其视野Visual内的随机状态，其公式如下：

Xj=Xi+Visual*Rand()

(3)

若求极大值时，当满足Xi>Xj(若求极小值满足Xi

(4)

(5)

(2)聚群行为。

设Xi为人工鱼i的当前状态，nf表示人工鱼数，Xc表示鱼群的中心位置，若Xc/nf>δXi，表示人工鱼的数量少，且在鱼群中心位置有丰富的食物，此时由式6继续更新人工鱼的状态。若不满足Xc/nf>δXi，重新进行觅食行为。

(6)

(3)追尾行为[13]。

设人工鱼i的当前状态为Xi，在鱼群搜索范围内(dijδXi时，Xj为最优状态，此时说明Xj方向食物充足，则人工鱼i向伙伴Xj方向前进一步；否则执行觅食行为。

(4)随机行为。

根据人工鱼的当前状态Xi，在其视野范围Visual内随机选取一个状态，如式7所示。

(7)

(5)公告板。

人工鱼的状态信息记录在公告板中。当完成上述行为后，对比此时状态和公告板中记录的状态。若当前状态比公告板中的状态好，则更新公告板，反之保持不变。

2 距离加权质心定位算法

质心定位算法是一种基于网络连通性的定位算法。其中心思想为：利用待测节点通信范围内的邻居锚节点进行位置估算，将所有锚节点分布位置连成一多边形，求出多边形质心作为待测节点的位置。由于质心算法中各个锚节点广播的信息存在误差，每个锚节点对待测节点影响程度也不同，特别当锚节点密度过低时甚至会出现无法定位的现象。针对这一缺点，可以通过加权因子体现各锚节点对质心位置的影响程度[14]，反映它们的内在关系。

(8)

由于传统的三边定位法在复杂的环境因素下定位精度不高，因此提出一种改进的加权质心方法以提高定位精度。将三边定位法求出的质心点通过改进的人工鱼群算法进行迭代更新，直至得到最优解。

3 人工鱼群质心定位算法

(9)

对于与待定位节点相关的n个锚节点，误差函数表示如下：

(10)

由于不同距离测距误差不同，所以对不同的锚节点进行加权，对距离较远的用较小权值，对距离较近的用较大权值。所以，通过待定位节点与锚节点的距离的倒数作为对误差函数的加权系数来构造人工鱼群算法的适应度函数。

(11)

通过人工鱼群算法对加权质心算法进行优化，记录未知节点与锚节点估计距离，与实际距离相比较，寻找误差最小值，从而估算未知节点的位置。文中的算法的流程如下：

(12)

Step2：初始化设置，包括人工鱼数量N、每条人工鱼的初始位置、人工鱼的视野Visual、人工鱼的步长Step、最大迭代次数IT、尝试次数Tn、拥挤度因子δ和要执行吞食行为的阈值T-value等。

Step3：比较每条人工鱼周围食物的浓度，选出浓度最大的人工鱼信息并记录在公告板中。

Step4：对每条人工鱼执行追尾行为、聚群行为和随机行为，采用行为选择策略，计算每条鱼食物浓度，选出最优值与公告板中的值相比较。如果好于公告板中的则替换，最终公告板值始终保持最优。

Step5：判断是否满足结束条件，如果满足则返回Step4，公告板值即最优值。

4 仿真实验与分析

4.1 仿真环境与参数

在Matlab平台上，将基于人工鱼群质心算法、加权质心算法以及质心算法在不同锚节点密度、不同节点密度和不同节点通信半径三种情况下进行仿真对比。仿真过程中，选择100 m×100 m的正方形区域，未知节点和锚节点随机部署在正方形区域内。同时，人工鱼群算法中群内解个数N=50，迭代次数IT=100，拥挤度因子δ=1，视野Visual=10，步长Step=8。为了减少实验中随机误差的干扰，每组参数独立运行50次，定位误差取50次运行结果的平均值。定位误差error为：

(13)

4.2 结果分析

在总节点数为100，节点通信半径为30 m，锚节点数从12个变化到30个的情况下，得到三种算法的定位误差对比图(见图1)。从图中可以看出，随着锚节点密度的增加，三种算法的定位误差都有所降低，但整个过程中鱼群质心定位算法的定位误差始终低于质心算法和加权质心算法的定位误差。

图1 不同锚节点密度的定位误差曲线

图2为平均定位误差随总节点个数的变化曲线。仿真时保持锚节点密度为20%不变，节点通信半径为30 m。仿真结果表明，鱼群质心算法的定位精度随总节点数的增加而提高，且明显优于其他两种算法。

图2 不同总节点数的定位误差曲线

图3中改变锚节点通信半径，观察平均定位误差的变化情况。随机分布100个传感器节点，其中锚节点密度为20%。仿真结果表明，在相同条件下，随着节点通信半径的增大，鱼群质心算法的定位精度高于质心算法和加权质心算法。

图3 不同半径的定位误差曲线

5 结束语

文中提出的改进算法是在加权质心算法的基础上，引入人工鱼群智能算法。利用人工鱼群算法稳定性好、全局寻优能力强的特点，减少质心定位算法中三边测量法带来的误差。该算法不可避免地增加了少量

的计算开销，但与传统质心算法和加权质心算法的对比表明，该算法具有更高的定位精度。

参考文献：

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] 王福豹，史 龙，任丰原．无线传感器网络中的自身定位系统和算法[J]．软件学报，2005，16(5):857-868．

[3] 陈节节.无线传感器网络三边测量法研究概述[J].硅谷,2010(24):7.

[4] 徐原博,钟丽鸿,崔 洋,等.基于无线传感器网络的极大似然定位法的分析[J].传感器与微系统,2011,30(10):37-40.

[5] 赵仕俊，孙美玲，唐懿芳.基于遗传模拟退火算法的无线传感器网络定位算法[J].计算机应用与软件，2009,26(10):189-192.

[6] 陈星舟，廖明宏，林建华.基于粒子群优化的无线传感器网络节点定位改进[J].计算机应用,2010,30(7):1736-1738.

[7] NICULESCU D,NATH B.DV based positioning in Ad Hoc net-works[J]. Telecommunication Systems,2003,22(1-4):267-280．

[8] KUANG Luobei, WANG Zhijun, XU Ming. End-to-end transmission time-based opportunistic routing protocols for bus networks[J].Turkish Journal of Electrical Engineering & Computer Sciences，2013,21(2):470-492．

[9] 张先超，刘兴长，张春园．基于次锚节点的无线传感器网络改进加权质心定位算法[J]．传感器与微系统，2015，34(2)：143-146．

[10] 江铭炎，袁东风．人工鱼群算法及其应用[M]．北京：科学出版社，2012.

[11] 唐 莉,张正军,王俐莉.人工鱼群算法的改进[J].计算机技术与发展,2016,26(11):37-40.

[11] 黄 仁，秦占明．基于人工鱼群算法的无线室内定位优化[J]．计算机应用，2015，35：14-17．

[12] 徐善永，黄友锐，曲立国.基于人工鱼群算法煤矿井下人员定位技术研究[J].煤炭工程，2013，45(11)：129-131.

[13] 李凌燕,杜永贵.改进型粒子群优化在WSNs节点定位中的应用[J].计算机应用与软件，2014,31(4):69-72.

[14] 朱 博，陈 曙．一种无线传感器网络质心定位改进算法[J]．传感技术学报，2010，23(6)：868-872.