基于鸡群算法的无线传感器网络定位研究*

李 鹏,陈桂芬,胡文韬

(长春理工大学电子信息工程学院,长春 130022)

无线传感器网络WSNs(Wireless Sensor Networks)是当前信息科学技术领域研究的热点之一,可实现特殊情况下信号的收集、处理和发送。由于其独特的学科交叉性,成为了二十一世纪极具发展潜力的关键技术。无线传感器网络是仅次于互联网的第二大网络,具有低成本、体积小、传输距离远等优势,广泛应用于军事、医疗环境监测等方面[1]。定位技术作为无线传感器网络的关键技术,在很多领域发挥重要作用。可以帮助人们实时获取所需的位置信息和实时情况,同时获取传感器节点的确切位置还确保了无线传感器网络后续的路由及覆盖算法的高效执行。因此研究无线传感器网络定位意义深远。

针对各种定位算法的不足之处很多学者提出了不同的改进优化算法。文献[2]通过筛查参考节点共线问题,尽量避免该情况影响定位精度,但增加了算法复杂度;文献[3]通过构造RSSI比值来修改跳数信息,并且通过系数加权方法来校正跳距长短,减少了估计误差,但造成多余的能耗;文献[4]将两代节点取平均值并用改进的粒子群算法优化节点定位,效果较明显,却存在一定误差;文献[5]改变节点通信半径,影响跳数,提高定位精度,效果不是特别明显;文献[6]通过改善最小均方误差的指标值来改变平均跳距,并获得最佳指标值,对提高定位精度起着重要作用,同样不可避免误差问题;文献[7]提出了一种结合RSSI技术校正通信半径周围节点跳距误差的新方法;文献[8]将改进后的鸡群算法应用于无线传感器网络定位,提高了收敛速度和定位精度,算法有待进一步完善;文献[9]提出RSSI测距与累计误差相结合的算法,相比原算法提高较大精度,但算法相对复杂;文献[10]通过分析理想和真实环境中的RSSI定位算法,研究了各种环境因素对定位精度的影响;文献[11]提出一种新的目标检测算法,实现了分布式一致性目标定位,并用信号强度估测在通信链路失效情况下的目标距离,并且相邻节点之间的信息交换缩短了定位时间。近年来,随着在传统算法的基础上衍生出来的群智能算法的兴起,再结合仿生学原理,研究人员根据生物进化机制对群智能算法进行数学建模,并利用群体间的默契合作,简单整体高效的求解复杂难懂的数学模型。而无线传感器网络定位问题一定程度上也可看做复杂的数学模型,因此群智能算法更适用于无线传感器网络定位问题。几年前提出的鸡群算法作为新兴的群智能算法,在收敛性、鲁棒性以及准确性方面较其他算法有着很大的优势,且很少有要调整的参数,为无线传感器网络定位算法的误差优化提供了新的解决思路。

考虑到上述算法优缺点,本文提出了一种将改进的鸡群算法与总结出的定位模型相结合的ICSO算法,首先提出基于pareto距离分级的适应度计算方法合理分配鸡群,并在此基础上优化母鸡位置公式,最后在小鸡位置公式中引入净能量增益,全面提高定位精度。仿真结果表明,与改进后的粒子群算法和其他改进后的鸡群算法相比,ICSO算法在多种条件下均能有效提高定位精度。

1 定位节点模型的建立

在众多经典的非测距算法中,DV-Hop算法以其简单易实现及定位精度较高而被备受关注。该算法经常使用最小二乘法计算节点坐标。但定位精度会受到累计误差的影响。针对这一问题总结一种节点定位模型,并对可能存在的误差进行分析。假设网络区域中(x,y)为未知节点坐标,(xi,yi)为参考节点坐标。参考节点和未知节点间的距离为di,i=1,2,…,n。则di可表示如下;

(1)

将式(1)变为线性方程组,如式(2):

AX=b

(2)

其中:

(3)

(4)

(5)

以上公式是在理想情况下构造的,而在实际问题中,距离测量的误差问题难以避免。即AX+N=b,N代表n-1维误差向量。要想让X更加准确,则应使N取最小值。求得:

X=(ATA)-1ATb

(6)

不难看出,参数b对X的求解起着至关重要的作用。确定b的最重要因素是dn。若dn的值较大,用于计算具体节点坐标的最小二乘法不能有效应用。针对这一弊端,将误差较大环境下的定位问题转换为函数约束优化问题。上式改写为:

(7)

节点间的距离测量误差公式如下:

|ri-di|<εi

(8)

εi为节点间的测距误差。ri是网络中参考节点i与未知节点的实际距离。i=1,2,…,n。即:

(9)

(10)

分析式(10),f(x,y)的值越小代表要求解的坐标值与实际值越接近。这样,将网络节点定位问题转换成多维约束优化方程。利用全局优化的鸡群算法迭代寻优特性,求解所求节点的具体位置。逐步迭代减小差值,直到获得最佳值。

2 鸡群算法

2.1 鸡群算法介绍

鸡群算法(Chicken Swarm Optimization,CSO)是在2014年由MENG Xianbing等[12]提出的一种基于鸡群觅食行为的智能搜索算法,将鸡群搜索行为和阶级制度归纳为求固定区域内最佳值的优化问题。成立前提如下:①鸡群分为若干子种群,每个种群由一只公鸡,较少数量的母鸡和较多的小鸡组成。②根据适应值不同分配公鸡、母鸡和小鸡。③鸡群中上下级制度到达某一代后再重新分配。④鸡群按分级制度觅食,小鸡可以其他个体发现的食物为食。

当使用鸡群算法解决优化问题时,鸡群中每只鸡看作该问题的解。N为整个种群的所有鸡个体数。假设NR、NH、NC、NM分别代表了公鸡、母鸡、小鸡以及鸡妈妈的个数。鸡群中个体寻食的位置更新公式与子群分配的角色有关[13]。三种鸡的位置更新公式分别如下:

①公鸡个体位置更新公式为:

(11)

(12)

②母鸡个体位置更新公式为:

(13)

(14)

S2=exp(fr2-fi)

(15)

其中,rand是[0,1]之间均匀分布的随机数;r1是第i只母鸡所在子群中的公鸡;r1是整个鸡群中的所有公鸡和母鸡中的任意个体,且r1≠r2。S1=0,第一只母鸡会追随其他鸡搜索而搜索。S2=0,小鸡只会在自己的周围搜索食物,不会表现出从其他群体抢夺偷窃以获取食物的行为。

③小鸡个体的更新方式为

(16)

2.2 适应值函数

鸡群搜索算法将定位问题中每个可能解视为搜索空间中鸡的位置。在鸡群搜索的每次迭代中,要设置一个适应值函数来评判当前鸡个体位置的优劣,引导其向位置较优的鸡靠拢。具体适应值函数设定为:

(17)

式中,要测量的节点位置由(x,y)表示,且第i个已知节点位置由(xi,yi)表示。因此可以通过求解fitness(i)的最小值来测算节点位置。

2.3 鸡群算法的改进

2.3.1 对鸡群个体选取方法的改进

传统鸡群算法中最好适应值个体是公鸡,较优的一些是母鸡,余下的是小鸡。总体而言,应使种群中公鸡数远小于母鸡,母鸡数远小于小鸡。传统鸡群算法只能保证公鸡个体一定会被选择出来,而不同实际情况下种群适应值往往相差很多,无法合理分配比例。针对这一问题,提出关于距离的pareto鸡群算法DPCSOA(Distance-based Pareto Chicken Swarm Optimization Algorithm)。该算法将每个子种群细分为两个种群:一个是使用标准鸡群算法种群Cn,另一个是从种群迭代至今得到的所有非劣解集的最优种群En。

(18)

第i只鸡寻找所有对于m=1,2,…,M的最小d(m)(i),即d(min)=mind(m)(i),记该最小距离的索引为m*,记F(e(m*))为F*。此后,如果第i只鸡劣于当前最佳组,则它进入最佳组,计算其适应值为距该鸡最小距离的最佳个体的适应值与该最小距离之和,即;

F(x)=F*+dmin

(19)

如果有比i只鸡更好的个体,则将所有这些个体从最佳组中移除。此外,如果第i只鸡不如任何最优解,那么将其阻止到最佳组并计算其适应值:

F(x)=max[0,(F*-dmin)]

(20)

采用以上方法计算鸡群每只个体适应值并评定优劣时,每只鸡个体可根据该位置个体的适应值和距最优解的距离综合考虑选择合适的母鸡与小鸡,使得鸡群等级配比更加合理化,有助于更准确寻找最佳解。

2.3.2 母鸡的随机游走策略

种群中的母鸡是随着公鸡位置的变动而移动的。随着迭代的进行,鸡群算法寻优得到的最佳解会逐渐减小,迭代计算量的增加并不能有效提高算法的寻优精度,为此对母鸡的移动采取跟随公鸡与随机游走相结合的策略,每当母鸡朝期望方向行走一段距离后,会在自身一定范围内随机移动以在母鸡个体周围产生新解。随着迭代的进行,母鸡对公鸡的跟随程度减弱,这时增强母鸡个体的随机游走。正常在应用母鸡公式对母鸡定位以后,在母鸡周围随机搜索公式如下:

(21)

rand值在1和-1之间,在觅食的最初阶段,这种随机性可以被接受。一旦母鸡接近食物,进一步修改公式增加母鸡的移动能力,以展开更大范围的局部搜索。优化后的公式如下:

xnew=xi+θ1rand(xr1-xr2)+θ2εxold

(22)

(23)

式中,r1、r2是1到NH之间的随机数,r1≠r2。NH为母鸡数量。θ1+θ2=1,θmax为1,θmin为0,Gmax为最大迭代次数,t为当前迭代次数。

2.3.3 引入净能量增益

由于鸡群中的小鸡个体可以随意偷取其他个体发现的食物,且整个鸡群个体是由若干个子鸡群组成的,因此很容易出现小鸡偷食其他个体的食物后迷失方向、找不到自己的鸡妈妈等情况而造成的搜索误差问题。针对该问题本文修改了小鸡的位置公式,在公式中引入净能量增益系数,使小鸡更容易到达理想位置。

净能量增益的具体原理为:鸡群搜索食物依照严格的等级制度,觅食过程中所耗费的能量较高。虽然较大的食物会提供更高能量。但可能分布稀疏或距鸡群较远,而较小的食物虽获得的能量较少,却可能分布较多且距离较近。小鸡在搜索食物的过程中也会对能量进行取舍,即优先在本种群距离近的鸡妈妈周围搜寻能为其提供最大能量增益的食物,每当有一只小鸡在此觅食,将有更多同类型的小鸡被吸引过来。

Gij=|Ej-Ei|

(24)

(25)

Si,j=ri,jωkc

(26)

δij=eGi,j-eSi,j

(27)

Ei,Ej为小鸡ith与jth的目标函数值。Gi,j为小鸡觅食后可能获得的能量增益。Si,j为小鸡移动路径rij所消耗的能量。ri,j是第i只小鸡与第j只小鸡的笛卡尔距离。而实际情况中,小鸡的移动不可能是直线的,故引入变量w。kc为小鸡单位距离的能量消耗。δij给出净能量增益。引入净能量增益的小鸡位置公式如下:

(28)

2.4 基于改进鸡群算法的节点定位

鉴于鸡群算法优秀的寻优能力,结合上述三点定位模型,进行节点定位研究,用解决函数约束优化问题的思想确定待测节点的位置问题。然后使用鸡群算法进行智能搜索来确定待测节点的确切位置。具体步骤如下:

步骤1建立第一章提到的定位模型,用鸡群算法解决该模型转化成的寻优问题。

步骤2设鸡群规模N,根据pareto距离分级分配鸡群比例,迭代次数Gmax和其他参数。

步骤3初始化鸡群位置。

步骤4按照2.3.1节内容,将鸡群比例进行划分。

步骤5母鸡和小鸡按照2.3.2和2.3.3节进行局部搜索。

步骤6当所有子鸡群完成指定次数的局部搜索时,重新分配个体并更新最佳个体信息。

步骤7如果满足终止条件,则算法结束并输出全局最佳值。该值即待测节点最优位置的近似值。否则转到第四步,迭代次数加1。

3 算法仿真

为了验证ICSO算法在提高定位精度方面比其他算法具有明显的效果和优势,选取了应用于无线传感器网络定位的两种改进后的典型算法作为对比,分别是文献[4]改进的粒子群算法(MPSO)和文献[8]改进的鸡群算法(BIDCSO)。MPSO算法首先把上一代和当代节点位置的平均值作为下一代目标节点的参考节点,再优化粒子群算法的全局最优点位置,并利用改进粒子群算法优化定位结果,提高定位精度。BIDCSO在算法初期建立定位模型,并在改进鸡群算法中公鸡、母鸡以及小鸡的搜索方式后应用于总结好的定位模型,一定程度上减小了误差。主要比较对定位精度影响较大的定位时间、节点密度、通信半径等因素。假设理想条件下,在正方形监测区域中,具体参数如表1所示。

表1 仿真环境参数

针对以上参数每种仿真实验重复进行100次取平均值,再根据平均误差对比各种定位算法的优劣,具体公式如下:

(29)

①不同性能参数比较

三种算法分别运行100次的性能参数对比如表2。

表2 MPSO、BIDCSO、ICSO算法的性能比较

由表2可见,在同等情况下与另外两种算法相比,ICSO算法具有更小的误差,且迭代时间更短,更容易快速、精确的定位未知节点位置,恰好体现了无线传感器网络高效、精确的定位特点。

②不同节点定位误差比较

三种算法对无线传感器网络节点优化定位后的误差波动曲线如图1。

图1 定位误差对比图

可以看出ICSO定位误差明显小于另两种算法。且图像波动范围明显较小,即在节点定位过程中节点位置的估测距离与实际距离相差更小,在复杂的网络中ICSO算法具有更好的定位稳定性。

③参考节点比例对平均定位精度影响

随着参考节点比例增加三种算法定位误差变化曲线如图2。

图2 不同参考节点比例的定位误差比较

总体看来,随着参考节点比例的升高,定位效果都趋于更优。ICSO算法的定位精度较MPSO算法和BIDCSO算法分别提高了19.2%和6%。可以看出当参考节点比例从5%提升至20%的过程中,误差降低效果最为明显。由于优化了鸡群的速度与位置更新公式,所以定位效果更优于文献[8]改进的算法。参考节点比例逐步增大到一定比例后,三种算法的定位误差均逐步趋于平稳。

图3 不同节点密度的定位误差比较

④节点密度对平均定位精度的影响

随着节点密度增加三种算法定位误差变化曲线如图3。

显而随着节点密度变大,三种定位算法均可不同程度的减小定位误差。ICSO算法的定位精度较MPSO算法和BIDCSO算法分别提高了22.1%和10.5%。当总节点数介于40和80之间误差下降最为明显。在网络节点多的情况下,需要种群具有高效的移动性以提高寻优精度,所以本文算法较优于文献[8]算法。但当节点总数增大到80以后定位精度并没有大幅度提升,这是由于节点过于密集,增加了节点间不必要的通信,损耗了更多能量。所以我们应根据实际情况合理选择节点数量。同时,可以看出,当待测区域密度较小时,ICSO算法具有明显的优点和良好的稳定性。因此在节点密度方面改进的鸡群算法可有效提高定位精度。

⑤通信半径对平均定位精度的影响

随着通信半径增加三种算法定位误差变化曲线如图4。

图4 不同通信半径的定位误差比较

根据每条曲线的趋势,通信半径对三种算法的节点定位误差影响都较大。ICSO算法的定位精度较MPSO算法和BIDCSO算法分别提高了12.1%和4.4%,优势较明显。由于非测距算法与节点间距离无关,因此通信半径对定位误差影响很大,当通信半径很小时,有效锚节点数量较少,定位效果不理想,但是本文改进的算法具有更完善的速度位置寻优公式,所以比另两种算法在通信半径小的条件下具有更高的精度。由此可见,该算法同样适用于节点稀疏的环境。

⑥定位区域面积对平均定位精度的影响

随着定位区域面积增加三种算法定位误差变化曲线如图5。

图5 不同区域长度的定位误差比较

根据图5可以看出,待测区域面积越大,定位误差越高。ICSO算法的定位误差较MPSO算法和BIDCSO算法分别下降了8.5%和4.7%,在定位区域较大的环境下ICSO算法依然能保持较好的定位精度。随着区域面积的变大,对鸡群多样性有着更高的要求,本文改进的算法相比文献[8]的多样性有一定程度的提高,且不易陷入局部最优,因此本文改进的算法会更好的适用于定位区域面积较大的环境。

4 结论

针对无线传感器网络定位误差较大的问题,本文提出了一种将三点定位模型与改进鸡群算法相结合的ICSO算法。该算法用pareto距离分级思想分配鸡群比例,并引入随机游走策略优化母鸡的位置,扩大搜索范围,再用净能量增益改进小鸡的位置,综合提高定位精度。仿真结果显示,本文提出的算法有效提高了节点的定位精度,且该算法迭代次数少,收敛性好,易于实现。由于本算法没有考虑障碍物密集度较高的情况,下一步工作中将随机设置一定数量的障碍物,使该算法应用范围更广。