基于多目标优化的传感器网络任务分配模型与算法

摘要

无线传感器网络(Wireless Sensor Networks，WSN)优化问题中最重要的是任务分配问题，因为任务分配方案直接决定着网络耗能模式，从而决定了网络的生命周期。现有的解决任务分配问题的算法有多种，三阶段启发式算法(3-PH)就是其中较好的算法，因为它算法综合考虑了影响任务分配问题的多个因素。但是，三阶段启发式算法也存在一些不足：(1)算法将过程分成三个阶段以解决多目标优化，这种方法不能有效协调各目标之间的关系；(2)随机迭代算法所固有的“无记忆性”不能将迭代过程中的优良个体有效保留；(3)假设节点间无通信冲突，而节点间却存在严重的通信冲突。
　　 针对三阶段启发式存在的不足，本文提出了两种算法：改进的三阶段启发式算法(G3-PH)和嵌套关键路径的遗传算法(GA)。G3-PH算法提出用目标协调优化算法将多目标转化为单目标，从而解决了多个目标协调性的问题。同时，G3-PH算法假设网络节点间存在通信冲突，只要网络节点上执行电压满足上界要求，则节点间的多个通信任务可以同时执行。但是G3-PH算法也存在“无记忆性”的问题，所以文章提出用GA算法解决任务分配问题，因为这种算法具有“记忆性”的特点，可以将迭代过程中所产生的优良个体有效保留。同时，本文在GA算法中引入关键路径算法和目标协调优化算法，分别用以解决路径选择问题和多目标优化问题，从而得出最更优解。
　　 最后，我们将3-PH，G3-PH，GA三种算法进行比较，仿真实验表明用GA算法解决任务分配问题，能够得到最小的网络能耗、最小的网络总延迟以及最大的网络均衡度，从而更好的解决了任务分配问题。