论文部分内容阅读
摘 要：近年来，移动代理（MA）广泛应用于无线传感器网络（WSN）多个领域，使用MA可以增加网络的能源效益，在基于MA的WSN中，找到一个最佳路线以使MA从多个分布式传感器执行数据收集至关重要。针对单个MA在收集数据过程中存在时延大、路由效率低和能源消耗不均衡等缺点，本文提出了一种新的基于遗传算法的多移动代理路径规划（GA-MIP）来解决这些问题。实验结果表明，GA-MIP的性能优于同类算法。
关键词：多移动代理;路径规划;遗传算法;
一、前言：
WSN 广泛应用于工业和民用各个领域，包括工业过程监视和控制，环境和栖息地监视，医疗保健应用，家庭自动化和交通控制等。在WSN 中使用移动代理（MA）可以解决软件安装问题，动态更改应用程序功能或要求。作为一种特殊的软件，MA 可在传感器节点之间迁移以自主执行任务[1]。例如，从多个源节点收集传感数据并按需定义一些处理，根据时变网络动态自适应地处理传感数据是MA 调度程序（即宿节点）的典型应用要求。单MA 在小规模网络中表现优秀，但随着问题复杂度或网络规模加剧其性能急剧下降，因此使用多移动代理汇聚数据优势明显。在MA 迁移期间访问感知数据源节点的顺序对WSN 的性能极其重要，访问给定的数据源节点集的最佳路线是NP 难问题。针对该问题，本文提出了一种基于遗传算法（GA）的多MA 路径规划（GA-MIP），首先将MA 进行基因编码，在随机选择的基因中建立一个搜索空间，接着执行遗传进化过程，应用进化算子增加基因的多样性，然后根据适应度函数选择更好的基因进行下一代的遗传，经过多轮的迭代，找到最优的移动路径。
二、算法简介
遗传算法[2]是一种基于遗传和自然选择进化理论的自适应启发式搜索算法，模拟了自然界的优胜劣汰法则。在GA 中，问题的解视为一个具有特定遗传序列的个体，在继承来自父母混合基因的同时，有机会突变产生新的个体。通过适应度函数的评估后，优秀的个体可以继续生存，通过多轮遗传迭代，优秀的基因得以保留，这些基因便是解决问题的最优解。
（一）编码方式
设数据源节点数为[1，n]，则源编码为S=[MA1，MA2，…，MAn]，其中MAi=[a，b，c，d…n]，表示移动代理i 访问数据源节点的顺序，从a 出发经过b，c，d…到n 结束。组编码为M=[M1，M2，…，Mn]，其中M1 表示移动代理MA1 访问数据源节点的数目。源编码与组编码组合便是单个MIP 的基因。
（二）交叉算子
交叉算子是GA 中的关键组成部分，假设有两个长度对应相同的基因序列，在保证选择交叉片段相同的情况下，将父基因片段插入对应母基因片段之前。为消除基因的重复性，交叉之后应删除重复的源节点，并对所有的组编码进行降序排序。例如父基因源编码为A=[2，5，3，4;1，6，8;7，9]，母基因源编码为B=[1，2，5，3;6，7，9;8，4]，经交叉得源编码为[2，5，3，4;6，7，9;1，6，8;7，9]和[1，2，5，3;1，6，8;6，7，9;8，4]，去掉重复源节点后，得子节点为a=[2，5，3，4;6，7，9;1，8]，b=[1，2，5，3;6，8，7;9，2]。
（三）变异算子
為了保证基因的多样性，以增加产生最优解的可能性，需要对基因进行变异操作。对于两个独立的源编码和组编码分别进行变异并进行合并。源编码变异过程定义为随机选中代码中的两个元素并对位置进行交换，例如源编码为S=[2，5，3;7，3]，随机选择的元素为前两个元素， 则变异后的编码为S1=[5，2，3;7，3]。组编码通过增量的方式进行编译，对于随机选取的组代码中的元素，在确保增减序数后元素仍在源节点范围内，对第一个元素序数增加1，第二个序数渐少1，然后降序排列。其中，元素为n 则不进行加1 操作，元素为1 则不进行减1 操作。例如组编码M=[7，6，4，2，1]，随机选择前两个元素，则变异后M =[8，5，4，2，1]。
三、算法1实现
（一）适应度函数
设源节点的平均能量为e，通信时延为t，采用线性加权思想，将该类问题主体转化为多个单目标，通过设置网络能耗、两种权重因子，直观显示数据趋势并取得一种较为平衡的路径规划方案。适应度函数为：
f= αe + βt。
其中α和β为加权因子。
（二）算法流程
算法步骤如下：①初始化参数，设置计数器记录进化代数，随机生成100 个个体作为初始值，最大迭代数为T=500;②计算所有个体的适应值，③在群体中运用选择算子，把优化后的个体基因直接遗传或通过交叉遗传给下一代;④在群体中运用交叉算子;⑤在群体中运用变异算子，使得个体基因序列发生突变，增加种群多样性，⑥若迭代次数为T，则输出结果，终止算法，否则返回③。
四、实验结果
为验证GA-MIP 有效性，选取5～40 个数据源节点分别与基于贪婪策略的LCF 算法和GCF 算法、MADD 算法在能耗和时延两项指标上进行综合对比，设期望E = e ? t。E 表示为时延和能耗的乘积，该值越小说明所选择的路径越好。
五、总结与展望
本文基于遗传算法为多MA 规划移动路径，引入源编码与组编码改进交叉于遗传算子，通过设置新的适应值优化算法的迭代，以延迟和能耗做为目标，为多MA 规划最优路径，通过与LCF、GCF 和MADD 算法进行对比验证其有效性，相比较于同类算法更好的实现了网络的负载均衡，从而延长了网络的寿命。
参考文献：
[1].史霄波，张引，赵杉，肖登明.基于离散多目标优化粒子群算法多移动代理协作规划[J].通信学报，2016，37（06）：29-37
[2]金仙力，李金刚.基于遗传算法的多目标路径优化算法的研究[J].计算机技术与发展，2018，v.28;No.250（02）：60-64.
关键词：多移动代理;路径规划;遗传算法;
一、前言：
WSN 广泛应用于工业和民用各个领域，包括工业过程监视和控制，环境和栖息地监视，医疗保健应用，家庭自动化和交通控制等。在WSN 中使用移动代理（MA）可以解决软件安装问题，动态更改应用程序功能或要求。作为一种特殊的软件，MA 可在传感器节点之间迁移以自主执行任务[1]。例如，从多个源节点收集传感数据并按需定义一些处理，根据时变网络动态自适应地处理传感数据是MA 调度程序（即宿节点）的典型应用要求。单MA 在小规模网络中表现优秀，但随着问题复杂度或网络规模加剧其性能急剧下降，因此使用多移动代理汇聚数据优势明显。在MA 迁移期间访问感知数据源节点的顺序对WSN 的性能极其重要，访问给定的数据源节点集的最佳路线是NP 难问题。针对该问题，本文提出了一种基于遗传算法（GA）的多MA 路径规划（GA-MIP），首先将MA 进行基因编码，在随机选择的基因中建立一个搜索空间，接着执行遗传进化过程，应用进化算子增加基因的多样性，然后根据适应度函数选择更好的基因进行下一代的遗传，经过多轮的迭代，找到最优的移动路径。
二、算法简介
遗传算法[2]是一种基于遗传和自然选择进化理论的自适应启发式搜索算法，模拟了自然界的优胜劣汰法则。在GA 中，问题的解视为一个具有特定遗传序列的个体，在继承来自父母混合基因的同时，有机会突变产生新的个体。通过适应度函数的评估后，优秀的个体可以继续生存，通过多轮遗传迭代，优秀的基因得以保留，这些基因便是解决问题的最优解。
（一）编码方式
设数据源节点数为[1，n]，则源编码为S=[MA1，MA2，…，MAn]，其中MAi=[a，b，c，d…n]，表示移动代理i 访问数据源节点的顺序，从a 出发经过b，c，d…到n 结束。组编码为M=[M1，M2，…，Mn]，其中M1 表示移动代理MA1 访问数据源节点的数目。源编码与组编码组合便是单个MIP 的基因。
（二）交叉算子
交叉算子是GA 中的关键组成部分，假设有两个长度对应相同的基因序列，在保证选择交叉片段相同的情况下，将父基因片段插入对应母基因片段之前。为消除基因的重复性，交叉之后应删除重复的源节点，并对所有的组编码进行降序排序。例如父基因源编码为A=[2，5，3，4;1，6，8;7，9]，母基因源编码为B=[1，2，5，3;6，7，9;8，4]，经交叉得源编码为[2，5，3，4;6，7，9;1，6，8;7，9]和[1，2，5，3;1，6，8;6，7，9;8，4]，去掉重复源节点后，得子节点为a=[2，5，3，4;6，7，9;1，8]，b=[1，2，5，3;6，8，7;9，2]。
（三）变异算子
為了保证基因的多样性，以增加产生最优解的可能性，需要对基因进行变异操作。对于两个独立的源编码和组编码分别进行变异并进行合并。源编码变异过程定义为随机选中代码中的两个元素并对位置进行交换，例如源编码为S=[2，5，3;7，3]，随机选择的元素为前两个元素， 则变异后的编码为S1=[5，2，3;7，3]。组编码通过增量的方式进行编译，对于随机选取的组代码中的元素，在确保增减序数后元素仍在源节点范围内，对第一个元素序数增加1，第二个序数渐少1，然后降序排列。其中，元素为n 则不进行加1 操作，元素为1 则不进行减1 操作。例如组编码M=[7，6，4，2，1]，随机选择前两个元素，则变异后M =[8，5，4，2，1]。
三、算法1实现
（一）适应度函数
设源节点的平均能量为e，通信时延为t，采用线性加权思想，将该类问题主体转化为多个单目标，通过设置网络能耗、两种权重因子，直观显示数据趋势并取得一种较为平衡的路径规划方案。适应度函数为：
f= αe + βt。
其中α和β为加权因子。
（二）算法流程
算法步骤如下：①初始化参数，设置计数器记录进化代数，随机生成100 个个体作为初始值，最大迭代数为T=500;②计算所有个体的适应值，③在群体中运用选择算子，把优化后的个体基因直接遗传或通过交叉遗传给下一代;④在群体中运用交叉算子;⑤在群体中运用变异算子，使得个体基因序列发生突变，增加种群多样性，⑥若迭代次数为T，则输出结果，终止算法，否则返回③。
四、实验结果
为验证GA-MIP 有效性，选取5～40 个数据源节点分别与基于贪婪策略的LCF 算法和GCF 算法、MADD 算法在能耗和时延两项指标上进行综合对比，设期望E = e ? t。E 表示为时延和能耗的乘积，该值越小说明所选择的路径越好。
五、总结与展望
本文基于遗传算法为多MA 规划移动路径，引入源编码与组编码改进交叉于遗传算子，通过设置新的适应值优化算法的迭代，以延迟和能耗做为目标，为多MA 规划最优路径，通过与LCF、GCF 和MADD 算法进行对比验证其有效性，相比较于同类算法更好的实现了网络的负载均衡，从而延长了网络的寿命。
参考文献：
[1].史霄波，张引，赵杉，肖登明.基于离散多目标优化粒子群算法多移动代理协作规划[J].通信学报，2016，37（06）：29-37
[2]金仙力，李金刚.基于遗传算法的多目标路径优化算法的研究[J].计算机技术与发展，2018，v.28;No.250（02）：60-64.