基于免疫粒子群优化的移动Sink路径规划算法

张 红，薛东亮，李战明*

(1 兰州理工大学 电气工程与信息工程学院，兰州 730050；2 河南信息工程学校，郑州 450011 )

无线传感器网络(Wireless Sensor Networks，WSN)通常由大量分布的自主传感器节点和 Sink 节点组成,通过协同通信实现对环境参数的持续监测.因此，在工业过程监控、智能家居控制、交通监控处理等领域具有广泛的应用价值和极具吸引力的市场潜力[1].由于节点受电池约束以及系统采用无线通信方式，能量效率是无线传感网研究领域关注的主要问题.在配置静态Sink 节点的传感网中,多跳路由相比单跳能显著地减少节点平均能耗，但是也易使靠近 Sink 节点的传感节点因为承载更多的数据转发任务导致失效较早，形成热点问题[2].于是,很多学者考虑在WSN引入可移动的 Sink 节点，通过变换驻留点位置实现更为均衡的节点能量消耗，从而延长网络生存时间.在这种模式下，Sink 节点的停留位置和移动路径的规划是研究的主要热点.

移动Sink的路径选择与优化关系到无线传感网的能量效率.Wichmann等[3]以飞行器作为移动Sink节点进行大范围传感器节点收集的载体并建立旅行商问题(Traveling Salesman Problem，TSP)算法的模型,充分考虑长路径条件下的数据延迟约束，但是对网络生存周期的关注不够.Kumar 等[4]假定节点都具备GPS模块，可以获得精确的位置信息，再利用分簇算法并将簇头节点位置设定为移动Sink的驻留点位置，进行路径的优化选择.Tashtarian 等[5]考虑了消息截止时间和事件驱动的应用场景，以节点事件触发的机制来规划Sink的移动.针对监控区域内Sink移动轨迹中可能遇到障碍物的情况，Ghosh等[6]提出了一种移动采集路径规划策略以提高网络的能量效率.Salarian等[7]提出了一种称为加权交会规划(weighted rendezvous planning, WRP)的启发式算法，根据每个传感器节点到驻留点位置和其要发送的数据量分配相应的权重，使得移动Sink的数据收集效率最大化.为了保证网络所有节点的能量下降同步以延长网络的生命周期，Lee等[8]从节点的地理分布和邻居节点能量消耗速度监测两个方面入手，提出一种分布式启发算法来求解移动Sink的停留位置选择问题.

本文将人工免疫算法和粒子群算法相结合，提出了基于免疫粒子群优化的移动Sink数据收集算法来进行路由规划，求解WSN移动Sink最优路径,有效提高网络整体的数据采集效率.

1 系统模型与问题描述

假设在M×M的矩形监测区域随机部署N个传感器节点和1个移动Sink节点，其中：传感器节点均有唯一标识,且为静止状态；节点间可以以多跳形式转发采集的数据；所有传感器节点具有相同的通信半径r和相同的初始能量E9; Sink节点可外接电源进行能量补充.

网络初始化后，Sink节点从初始位置开始，与通信范围内的传感器节点进行数据回收，汇集完毕后再移动到下一个区域，最终回到初始位置形成数据采集回路.设Tp为移动Sink完成一个周期的数据汇集形成的路径，该路径由多个驻留点的连接线路组成.假设驻留点数量为n，第i个驻留点坐标为：pi=(xi,yi)，移动Sink的遍历路径可以表示为：Tp={s,p1,p2,…,pn,s}，s=(x0,y0)为Sink节点初始位置.

为了问题描述方便，假设所有传感器节点采用固定的发射和接收功率,则在每一周期的能耗可以表示为:

(1)

因此,网络中的整体能耗可以表示为最小跳数和的形式：

(2)

从(2)式可以得到,系统能耗的最小化与所有节点到驻留点跳数之和最小化正相关.而传感器节数据转发的跳数与移动Sink节点选择的驻留点之间的距离有关.因此，Sink的移动路径的选择将直接影响整个网络的整体能耗.

此外，从直观上看，Sink的移动路径的长短会直接影响节点的数据转发延迟.因此，综合上述分析，将WSNs中移动Sink的路径规划问题的求解定义为多目标优化函数，表示为:

f(Tp)=D(Tp)+ETp(d),

(3)

其中，D(Tp)为路径总长度，ETp(d)为Sink通信半径d条件下的网络整体能耗.

2 免疫粒子群优化

对于路径优化问题，建立在生物智能或物理现象基础上的随机搜索算法被广泛采用.在众多的群智能搜索算法中，粒子群优化算法(Particle Swarm Optimization，PSO)由Kennedy等人提出后就受到广泛关注.PSO算法通过基于种群搜索策略的自适应随机优化，能够充分利用群体间个体信息的共享，使得整个群体能够沿着最优解的方向不断迁移，不断迭代最终找到最优解，该算法在控制参数设置、实现的易用性等方面具有显著优点；其不足之处在于算法的种群多样性较低以及易陷入局部最优.

本文将粒子群算法与人工免疫算法相结合，利用免疫算法在全局寻优和种群多样性保持能力等方面的优点，将免疫系统的自适应识别以及对侵入机体的抗原异物进行排斥的特性引入到粒子种群的演化过程中，以提高算法的收敛性能并有效避免传统算法在求解过程中陷入局部最优.

2.1 粒子的产生与更新

设粒子群大小为M，每个粒子对应一个路径规划方案，每个方案包括驻留点pi及遍历顺序Tp.算法初始化时，先随机设置驻留点和访问顺序，一旦驻留点被选择，则将其从备选点集合中删除，用D维向量来表示粒子i的信息，其位置信息为xi=(xi1,xi2,…,xiD)，速度信息为vi=(vi1,vi2,…，viD)，适应度值fitness.迭代过程中，粒子通过跟踪两个极值来进行更新：一是粒子本身所能找到的个体最优解Pbest，另一个是整个粒子种群目前所找到的历史最优解gbest.位置信息和速度信息的更新表示为：

vij(k+1)=wvij(k)+c1r1(Pbest(k)-xij(k))+

c2r2(gbest(k)-xij(k)),

(4)

xij(k+1)=xij(k)+vij(k+1),

(5)

其中,w表示惯性权重，r1和r2是介于[0,1]之间的随机数，c1和c2是取非负值的学习因子，pbest(k)为第i个粒子在迭代轮次k所找到的个体最优值位置，gbest(k)为整个粒子种群在迭代轮次k所找到的全局最优值位置.

2.2 选择概率

在人工免疫算法中，一般通过亲和度对解的优良程度进行评价.将函数的候选解看做抗体((第i个粒子)，将目标函数的最优解看做抗原.当亲和度越高时，抗体与抗原越接近.因此，亲和度评价函数可以定义为：

g(xi)=emin{f(Tp,xi)}.

(6)

以多个最佳个体的平均值为疫苗的选取参照，定义疫苗为：

(7)

相似抗体越多，则算法越容易陷入局部最优，因而需要对相似的抗体采取抑制措施.定义抗体浓度来衡量抗体多样性程度.用X来表示抗体集合，有X={x1,x2,…,xn}，抗体浓度可以定义为：

(8)

为了保证选择过程中，对于某些浓度虽低但发展趋势较好的抗体也能有机会进化，将抗体促进与抑制的选择概率Prs定义为：

(9)

其中，δ为比例因子.

选择概率Prs能充分体现，对于浓度越高的抗体,选择的概率越小.另外，对于亲和度越高的抗体，也具有较高的选择概率.

2.3 算法步骤

算法的主要步骤描述如下：

步骤1：待优化函数的最优解为抗原，候选解为抗体.对WSN传感器节点数量，仿真区域大小等进行设定，设置粒子数量M，每个粒子代表一个可行的路径，学习因子c1,c2，权重wmax，wmin,当前迭代次数λ=1，迭代次数最大值λmax；初始抗体生成；

步骤2：抗体采用实数编码.在自变量范围内随机产生候选解X=(x1,x2,…,xn)T作为初始抗体群,初始速度V==(v1,v2,…,vn)T，计算所有抗体的亲和度.根据亲和度,计算出每个抗体和整个抗体群所经历的历史最好位置pbest和gbest；

步骤3：将亲和度从小到大排序，取一定比例的亲和度所对应的抗体作为抗体免疫记忆，以多个优良个体对应的基因的平均值作为疫苗；

步骤4：如果抗原是新的，则通过随机方式产生n个新抗体形成抗体群；否则，则从免疫记忆库进行抽取.计算抗体促进与抑制的选择概率后，采用轮盘赌方法选择进入下一代的抗体；

步骤5：对疫苗中一半的基因含量进行随机抽取，然后选择部分亲和度较低的抗体进行基因替换操作，提高种群的多样性选择.如果接种后的抗体其亲和度不如父代，则放弃并选择原有的抗体；

步骤6：粒子的位置按照公式(5)执行更新操作；

步骤7：重新计算每个抗体的亲和度.将每个抗体当前的pbest和所有经历过的pbest进行比较，如果优于则更新；同理，对整个抗体群，将当前gbest与所有经历过的gbest比较，优于则更新.粒子的速度按照公式(4)执行更新操作；

步骤8：一旦达到最大迭代次数或目标函数值收敛,算法终止;否则，跳转至步骤3继续执行.

3 实验结果与分析

首先，实验对传统粒子群算法与本文提出的算法在求解问题时，随迭代次数适应度值的变化情况如图1所示，在算法迭代相同次数下，本文算法得到的适应度值更低，表明加入了免疫算法的粒子群优化在求解最优解的过程中表现出更好的收敛性.图2是随算法的迭代，所能找到的解所对应的移动Sink对应路径，总体上来看本文提出的优化算法能够找到更优化的解，而且在迭代次数上可以反映免疫算法对解的优良程度的改进作用明显.

图1 适应度值的比较Fig.1 Comparison of fitness values

图2 路径长度的比较Fig. 2 Comparison of path length

为了对比算法在路径规划和能量效率的性能，本文算法与算法FDG-PS[9]和SMGF[10]在不同节点数量分布的环境下进行了仿真实验.在相同区域范围了配置不同数量的传感器节点，算法的其他参数保持不变.图3为三种算法所求得的Sink移动路径的总长度，图4为完成一次数据收集过程的网络整体能耗，Sink覆盖范围内的节点可采用多跳方式与Sink进行通信.从实验结果可以看到，随着传感器节点的增多,Sink节点的移动路径增加,AAA算法的路径长度小于其他两种算法的路径长度，说明本文算法找的解更优.另外，节点的能耗与数据转发的跳数有关，最终反映到Sink节点的驻留点位置选择上，本文算法能够得到更好的能量效率.

图3 网络平均能耗的比较Fig.3 Comparison of network average energy consumption

图4 路径长度的比较Fig.4 Comparison of path length

4 结语

针对无线传感网中采用移动Sink的方式收集节点采集带来的路径优化问题，本文提出了将人工免疫算法和粒子群算法相结合，寻求近似最优解.与其他算法进行了性能比较，本文提出的优化算法能够有效减少能耗和缩短遍历路径.后续我们将进一步研究基于多Sink的移动数据收集，以及考虑节点之间的协作来进一步压缩访问点的空间来研究进一步优化移动Sink路径.