遗传-禁忌搜索优化的Amorphous定位算法

胡 伟,袁三男

(上海电力学院电子与信息工程学院,上海 200082)

随着近距离、低功耗无线通信技术的发展,无线传感器网络WSN(Wireless Sensor Networks)技术在现代社会中扮演着越来越重要的作用[1]。定位技术不仅是无线传感器网络技术中重要组成部分,也被人们广泛应用到生活中的各个领域[2]。在对未知节点定位的过程中,根据是否对已知节点进行实际测量,可以把定位算法分为测量距离定位算法和无距离测量定位算法[3-5]。基于距离测量的定位算法通常有基于到达时间的ToA测距、基于到达时间差的TDoA测距、基于到达角度的AoA测距和基于接收信号强度的RSSI测距等;无需测距的常见算法有质心算法、DV-Hop算法、APIT算法和Amorphous算法等。测量距离定位算法对硬件有更高的要求,需要投入更大的成本,所以研究无距离测量定位算法有着重要的意义。

本文主要针对Amorphous算法将通信半径作为平均每跳距离存在较大误差,导致定位误差明显的特点做了深入分析。为了提高Amorphous算法的定位精度,对算法中的各个参数包括锚节点的个数、节点通信半径和总节点的数目等参数优化[6]。该方法虽然可以减小误差,但实用性较差;为减小Amorphous算法在不同通信模型下的定位误差,可以在该算法离线计算网络平均连通度的基础上,建立了四种RSS阈值模型[7],该方法使定位误差得到抑制,但实现过程较复杂;针对Amorphous算法估计跳数值误差大的缺点提出设置跳数阀值,如果信标节点距未知节点跳数大于此阀值,则其不参与未知节点定位[8]。但是存在当未知节点到所有锚节点的距离都在阈值外时可能会产生无解的情况。

针对Amorphous算法定位误差大,遗传算法局部搜索能力较弱、单独的遗传算法比较费时的问题,本文提出基于遗传-禁忌搜索算法对传统的Amorphous定位算法进行优化。首先将传统Amorphous算法中对未知节点到锚节点的最小跳数的估计值进行修正,即利用接收器的信号强度与跳数进行一定比例的转换;其次利用禁忌搜索算法的禁忌表策略加强了遗传算法的局部搜索能力、避免了遗传算法产生重复解;最后使用遗传-禁忌搜索算法对优化后的Amorphous算法产生的初始解进行优化。本文提出的算法降低了Amorphous算法的定位误差,提高了对未知节点的定位精度。

1 Amorphous算法

Amorphous是由Radhika Nagpal等提出的定位算法。该算法的实现无需测量距离,通过获取未知节点与已知节点(锚节点)之间的最小跳数,估计未知节点位置[9]。该算法分为3个阶段:

①计算未知节点与每个锚节点之间的最小跳数:锚节点将含有id、坐标和跳数(初始化为0)的数据包发送到整个无线传感器网络中的邻居节点,邻居节点收到数据包后将跳数加1,继续转发给相邻的未知节点。如此往复,所有未知节点都将获得到锚节点坐标和到锚节点的跳数,为了使未知节点保存到锚节点的跳数最小,未知节点将只保留跳数最小的数据包丢弃其他数据包。然后利用式(1)计算局部跳数的平均值代替它与锚节点之间的最小跳数hop(i,k);

(1)

式中,h(j,k)和h(i,k)分别表示未知节点j和未知节点i到锚节点k的跳数,|nbrs(i)|表示未知节点i的邻居节点数目。

②计算未知节点到每个锚节点的跳段距离:采用式(2)计算网络平均连通度,

nlocal=NπR2/S

(2)

式中,N为网络总节点数,S为网络区域面积,R为网络中节点的通信半径。

无线信号的单跳覆盖距离使用式(3)计算

(3)

根据平均每跳距离及距各信标节点的局部跳数,由式(4)计算未知节点和各信标节点间的距离。

d(i,j)=HopSizei×hop(i,j)

(4)

式中,HopSizei表示未知节点i获得的平均每跳距离。

③利用三边测量法或极大似然估计算法,计算未知节点位置:现假设3个锚节点的坐标为(X1,Y1)、(X2,Y2)、(X3,Y3),他们与未知节点W(X、Y)的距离为d1、d2、d3。代入式(5),

(5)

写成矩阵形式AX=b;三边测量法估算W的坐标X=A-1b;极大似然估计法估算W的坐标X=(AT-A)-1AT-b。

2 遗传-禁忌搜索算法

遗传算法GA(Genetic Algorithm)1975年由美国Michigan大学的Holland教授与其同事首先提出[10],该算法是通过模拟自然进化过程搜索最优解的方 法[11]。禁忌搜索算法TS(Tabusearch)最早是由Glover等提出[12],具有独特的记忆功能,它具有搜索速度快局部搜索能力强等优点。在全局搜索方面遗传算法(GA)较禁忌搜索算法(TS)强,在局部搜索方面的表现则正好相反。基于此本文提出将两种算法结合在一起处理定位问题。GA中的选择过程与TS的移动过程是相似的,它们的目标都是进行单点寻优操作以改善解的结构。在本文中,利用GA迭代特性可以保证全局收敛;利用TS迭代特性可以保证解的多样性及局部收敛。

2.1 适应度函数的选取

根据最近的3个已知节点及其坐标可以构成未知节点的非线性方程组:

(6)

那么可以得到适应度函数为:

(7)

式中(xi,yi)表示的是未知节点的坐标,(aj,bj)表示的是第j个已知节点的的坐标,dj表示未知节点与第j个已知节点的估计距离。

2.2 选择算子的选取

从一个群体中选择优良的个体并淘汰劣质个体的过程被称为选择,而选择算子是建立在适应度评估值基础上的。即适应性强的个体,被选为下一代的概率就越大[13]。例如,设种群的个体数量为100,个体i的适应度用函数f(i)表示,Pi表示整个种群的适应度总和可用式(8)表示,

(8)

那么此个体被选中的概率用Pix可由式(9)表示

(9)

计算所有个体的适应度值,并对它们按照Pix从大到小的顺序进行排序。采用基于适应度的赌轮选择法,其基本思想是每个个体被选中的概率与其适应度大小成正比。

2.3 交叉率的选取

将种群中的两个父代个体的部分基因进行替换重组的过程称为交叉,通过这一操作可以在下一代中得到新型基因的个体。在遗传算法中,交叉率Pc值的大小是影响遗传算法性能的一个关键因素[14]。自适应遗传算法中的Pc值可由计算式(10)获得。

(10)

式中fmax表示群体中最大的适应值,favg表示群体的平均适应值,f表示要交叉的两个个体中较大的适应值,k1、k2为某一常数。

Pc值设置过大时,新个体产生的速度快,但是遗传算法稳定性可能也越弱,即具有高适应度的个体结构可能会被破坏;Pc值设置过小时,遗传算法的稳定性会变强,但会使得到最优解的过程变得缓慢。因此在实验时需要不断尝试不同的Pc值对整体算法过程的影响,经过多次实验我们得到Pc=0.6时实验效果较好,即在选出的下一代个体中以概率为0.6进行基因重组。此外,在交叉重组的过程中,为了避免出现“近亲结合”,基因代码差异较小的个体不能进行交叉操作。

2.4 禁忌对象和禁忌长度

禁忌对象和禁忌长度是禁忌表中两个重要的指标。禁忌算法的主要功能是避免一些重复性的操作,即将在计算过程中重复出现的数值放入到禁忌表中以此禁止对禁忌表中的元素进行操作,我们将禁忌表中的元素称为禁忌对象。禁忌长度指的是被禁忌对象不允许选取的迭代次数。

在实际操作中会给被禁对象X一个数t(禁忌长度),要求被禁对象X在t步迭代内被禁。在禁忌表中采用tabu(X)=t记忆,每迭代一步,该项指标做运算tabu(X)=t-1,直到tabu(x)=0时解禁。通过上诉操作后,所有元素将会被分为被禁元素和自由元素。禁忌长度的取值很关键。禁忌长度过短,一旦陷入局部最优点,出现循环无法跳出;禁忌长度过长,候选解全部被禁忌,造成计算时间较大,也可能造成计算无法继续下去。本文中所用的方法是直接给禁忌长度t赋值为10。

3 遗传-禁忌搜索优化的Amorphous算法

3.1 Amorphous算法的改进

在经典Amorphous定位算法中,用式(3)的数值作为每两个节点间的距离的大小,这样在计算未知节点实际位置时会产生较大的误差。例如,当P、Q两个节点都在O节点的通信半径内时且两个节点距离O节点的距离不同时,那么|PO|与|QO|不相等。但是在计算的过程中会被当做一跳处理,即|PO|与|QO|的数值相等。在现实的无线网络中这个问题也是普遍存在的。针对经典算法中的这一问题本文提出改进方法,即在无线网络通信中主要采取的是无线电或超声波的方式传播信号。可以在信号主要强度空间内划分若干区间,在接受端检测出某个节点的信号强度并就此信号强度转换成相应的跳数。例如,将信号强度在40 dBm～90 dBm划分成若干区间,40 dBm～50 dBm可以将跳数设置为1,50 dBm～60 dBm跳数设置为0.8,以此类推。

3.2 遗传-禁忌搜索优化的Amorphous算法

遗传-禁忌搜索优化的Amorphous算法分大致为2个阶段,第一阶段通过改进后的Amorphous算法获取未知节点的初始解;第二阶段是将上一阶段产生的初始解代入到人工智能算法中进行优化。程序流程如图1所示。

实现算法的具体步骤如下:

Step1根据锚节点的坐标使用改进后的Amorphous算法得到未知节点的坐标作为GATS算法的初始输入;

Step2计算初始坐标的适应度,判断是否满足GA的终止条件,即是否达到最大迭代次数或者达到最小的误差要求。满足这一条件直接输出结果;否则进行选择、交叉操作后将结果代入到下一步;

Step3上一步产生的结果产生邻域解和候选集,首先判断是否满足藐视准则,若满足则直接更新禁忌表、用当前解更替最优解;若不满足,则判断候选解属性,将非禁忌对象对应的解作为当前解,更新禁忌表;完成上述步骤后判断是否满足TS终止条件,若满足终止条件返回到上一步;若不满足终止条件,将在这一步骤中循环直至达到满足TS终止条件跳回Step 2。

图1 遗传-禁忌搜索优化的Amorphous算法流程图

4 仿真分析

4.1 仿真环境

为了验证本文提出的算法在实际操作中的应用效果,在MATLAB平台进行了IAmorphous-GATS定位算法的仿真实验。迭代次数为100,交叉概率为0.6,禁忌表长度为10。为验证本文提出优化算法的优化效果,使用Amorphous算法、IAmorphous算法和IAmorphous-GATS定位算法在一定条件下进行对比。

使用归一化定位误差比较不同算法的定位性能,

(11)

4.2 仿真实验与分析

在做仿真实验的过程中,主要是观察通信半径、锚节点比例及节点总数对定位算法的影响。因此,在实验中采取控制变量法对这三个影响因素分别进行了观察。为了得到更好的实验对比效果,本次实验包括传统Amorphous定位算法、改进跳数的IAmorphous-TS(Improved Amorphous Tabu-Search Location)定位算法、IAmorphous-GA(Improved Amorphous Genetic-Algorithm Location)定位算法和IAmorphous-GATS(Improved Amorphous Genetic-Algorithm Tabu-Search Location)。

4.2.1 不同通信半径

观察通信半径对实验的算法的影响时,控制节点总数为100,锚节点比例为30%。仿真结果如图2所示,对于三种定位算法整体来看,都是随着通信半径的增加定位的误差在逐渐减小。最终在通信半径大于30 m时误差逐渐趋于平稳,主要是随着通信半径的增加未知节点到锚节点的跳数减小且最终将为某一固定值,计算的位置信息也将不再变动。从仿真结果可以看出,本文提出的IAmorphous-GATS算法对提高定位精度有较好的效果,虽然IAmorphous-GATS相对于传统的Amorphous算法误差有所减小,但是在通信半径在小于25 m前没有达到很好的优化效果。从仿真数值上看,IAmorphous-GATS的优化效果更加明显,定位误差分别比传统Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降29.3%、24.7%、16.1%。

图2 通信半径与定位误差关系图

4.2.2 不同锚节点比例

观察锚节点比例对实验的算法的影响时,控制节点总数为100,通信半径为30 m。从仿真图中可以看出,如图3所示,随着锚节点比例的增加,定位精度在上升,定位误差在减小,当锚节点比例达到20%时,定位误差逐渐趋于平稳。产生这一现象的主要原因是随着锚节点比例的增加减小了锚节点到未知节点间的跳数,从而减小了锚节点到未知节点的距离差值,使得整体的误差也在减小。从仿真结果可以看出,本文提出的IAmorphous-GATS定位算法在锚节点比例在达到30%后定位误差趋于平稳。IAmorphous-GATS算法对修正未知节点信息有明显的优化效果,与传统Amorphous定位算法相比有更小的定位误差,更高的定位精度。从仿真数值上看,IAmorphous-GATS的优化效果明显,定位误差分别比传统Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降30.2%、20.6%、14.7%。

图3 锚节点比例与定位误差关系图

4.2.3 不同节点总数

观察节点总数对实验的算法的影响时,控制通信半径为30 m,锚节点比例为30%。仿真结果如图4所示,从仿真结果中可以看出随着节点总数的增加,整体平均定位误差在减小。在节点总数达到250个时平均定位误差逐渐趋于平稳。从仿真结果可以看出,本文提出的IAmorphous-GATS定位算法对修正未知节点信息有更明显的优化效果,与传统Amorphous定位算法相比有更小的定位误差,更高的定位精度。从仿真数值上看,IAmorphous-GATS的优化效果更加明显,定位误差分别比传统Amorphous定位算法、IAmorphous-TS定位算法、IAmorphous-GA定位算法下降33.9%、23.3%、13.5%。

图4 节点总数与定位误差关系图

4.2.4 算法复杂度

为了解本文提出算法的在实际执行时占用时间资源的情况,设置节点总数为100、通信半径为40 m、锚节点所占比例为30%时算法运行情况。这也说明了IAmorphous-GATS也以一定的算法复杂度换取了定位精度。

表1 算法的运行时间

5 结论

本文针对传统的Amorphous定位算法进行了分析,在以Amorphous算法为基础的条件下进行了未知节点定位信息的优化。首先提出使用划分区间的方法在跳数上增加比例设置,然后对输出结果使用遗传和禁忌搜索算法进行了优化。通过仿真实验结果可以看出本文提出的对传统定位算法的优化方案降低了定位误差取得了很好的实验效果。在保证更高的定位精度的情况下对算法中的各个参数如何进行调整以及对算法结构进行进一步的优化是下一步的研究重点。