摘  要： 针对无线传感器网络路径优化问题，提出了一种改进的最优保存的遗传模拟退火算法。利用LEACH算法构建初始路由表，使用GASA的高效率搜索，将路由计算和遗传演化计算同时进行，并直至寻找到近似最优路径为止。将最优保存遗传算法和模拟退火算法相结合，引入自适应的概率变化，有效地解决了这两种算法的早熟现象和时间问题。仿真实验表明，该算法有效地解决了无线传感器路径优化问题，具有定位准确、节能和搜索能力较强等优点。
关键词： 无线传感器网络；定位；最佳路径；遗传模拟退火算法

　随着计算机网络的飞速发展，无线传感器网络WSN(Wireless Sensor Networks)由于其良好的特性而成为研究的热点。WSN由许多功能相同或不同的廉价微型传感器节点以自组网络的方式构成，是计算机技术、通信技术和传感技术交叉融合的产物[1-2]。这些节点通常被撒播于无人监控或难以到达的区域，通过传感、数据采集、传送和融合来实现特定的应用，因此其在军事、工业、家居、环境、生态等诸多领域都有着广阔的应用前景。WSN的路径优化目标是寻找并建立节能高效的、从传感器节点到接收器节点(Sink)的数据传输的可靠路径，使WSN的寿命最大化。考虑到WSN节点能量有限且不能补充，WSN的路径优化不仅与路径长度有关，还与节省能量和整个网络能量的均衡消耗有关。
　WSN路径优化问题的关键技术是多目标优化求解，即采用何种方法来确定最优路径方案，以及如何评估所选路径方案的优劣程度，因此这个问题是一个NP-hard问题。
对于此类问题，比较常用的优化算法有遗传算法和模拟退火算法。遗传算法很容易陷入局部最优解，而不能搜索到全局最优解。模拟退火算法虽然能够跳出局部最优解，但它是一种个体寻优算法，且搜索空间很大，这导致搜索效率很低。因此还需要在现有的优化方法基础上进一步研究寻找更优化的方法。
1 WSN模型及拓扑描述
　在WSN中，获得监测数据的传感器节点为源节点，其数据经过多跳聚集到汇聚节点(Sink Node)或基站(Base Station)，再通过互联网或卫星到达管理节点或用户。本文采用的基于被动分簇算法的能源有效WSN模型是目前无线传感器网络中最适用于数据交换的一种[3]，即仅当网络中有数据通信要求时才在网络中建立分簇网络拓扑，而且网络拓扑的建立与维护都在本地完成，不需要单独的控制命令，以节省能量开销。分簇策略中最重要的是簇首选举机制和网关节点的选择机制，簇首选举采用“先声明者胜”的选举机制，网关节点的选择则是根据在网络健壮性和能源有效性之间平衡的原则来确定选择机制。在网络模型建立过程中设定了一些与网络拓扑的建立相关的处理机制，主要包括包的处理机制、簇首声明机制、簇成员形成机制以及网关节点声明机制，这些机制能有效地保证网络拓扑的建立。

2 遗传模拟退火算法
　遗传退火算法是一种混合的优化算法，它将模拟退火算法融入到遗传算法当中[4]。与基于遗传算法的总体运行过程类似，遗传模拟退火算法也是一组随机产生的初始种群中全局最优解的搜寻过程。它首先通过选择、交叉、变异等遗传操作产生一组新的个体，然后再独立地对所产生的个体进行模拟退火过程，并将结果作为下一代种群中的个体[4]。反复迭代地进行这个过程，直到满足某个终止条件为止。利用模拟退火算法的收敛性以避免出现“早熟”的收敛现象，可以提高算法的优化性能。同时，本文对变异算子引入了自适应变异的思想，使变异概率能够自适应地变化。
　当温度较高时，拥有较高的变异率，随着降温过程的继续，变异率不断地缩小以避免破坏优秀的基因。当退火进行到种群里的各个基因的适应度差距很小时，重置退火温度T，使种群的变异率加大，以丰富种群的多样性，加速能够使算法脱离局部最优点，提高了算法的搜索性能。根据问题求解的实际接近程度，对每一个染色体指定一个适应度的值。本文的遗传退火算法采用保留部分最佳染色体的方法，以保护当前最优染色体，提高算法的收敛性能。同时，为了解决由于采取保留最优解而使算法收敛于局部最优解的问题，在问题的解适应度的值相差较小时，用提高变异概率的方法来增强种群的多样性，使得问题跳出局部最优解。通过多次的上述操作，问题将最终收敛于全局最优解。
2.1 适应度函数的选取
　在本文的适应度函数中，为了避免“早熟”现象，即降低适应度较高的个体与其他个体适应度之间的差异，保持了群体具有多样性。遗传模拟退火算法的适应度函数[5]采用启发式方法，将其定义为：

2.3 选择
　设计选择算子时采用排序选择，选择策略为转盘式选择，同时使用最佳个体保留策略，即从当前种群中选择D%的最佳染色体直接复制到下一代种群中。

2.4 交叉和变异
　交叉采用算术交叉，它是指两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。通过对父代染色体间区域进行多次交叉操作，然后利用包含在新个体集合中的信息进行信息最大化的选择，对每一代个体进行基于适应度的选择。
　变异采用离散单点变异。本文采用替换路径中的节点和删除路径中多余节点两种方法。替换方法为：(1)寻找路径仍未达到目的节点时，把路径的最后一个节点替换为可以与其前一个节点构成链路的节点。(2)在适应度值满足并已达到目标节点的路径中，引入自适应的概率变化进行替换，替换准则为寻找既能与其前一节点又能与其后一节点构成链路的节点替换当前节点。删除多余节点的方法为：对任选的一条路径，随机选择一个变异节点，寻找路径中所选择变异节点之后的节点中是否有能与其构成链路的节点，如果有，则与之相连，将中间的节点舍弃。
2.5 终止条件
　本文的遗传模拟退火算法(GASA)终止条件采用复合准则：迭代次数达到预设要求和种群成熟度满足一定条件，且种群的平均适应值提高不足1%；或进化代数已达到预先设定的最大值，停止迭代。
3 改进的遗传模拟退火算法IGASA
　根据上述改进算法的基本思想，建立一种适用于WSN路径寻优的遗传退火算法。
　(1)种群的初始化。设定种群大小、初始温度、染色体长度、交叉概率、变异概率。重置T的次数、各个个体差异度。随机初始化种群，为了改善初始化搜索性能，为每一个染色体指定一个适应度的值。
　(2)适应度函数的判断。筛选当前最好的个体进入下一代种群。
　(3)进行遗传操作。选择策略采用轮盘赌算子和最优保存策略相结合，交叉采用实数编码的算术交叉，变异采用离散单点变异。
　(4)模拟退火操作。新解接受条件采用Metropolis准则。
　(5)更新、迭代过程。根据已筛选的当前最好个体和遗传退火操作新生成的染色体，加速种群的进化，生成下一代新种群。计算种群中各个个体的适应度值，当小于给定值时，重置T，以增大变异的概率，更新父代个体中最优个体和最差个体，避免陷入局部最优解。
　(6)判断重置T的次数是否等于设定值，如果等于，转到(7)，否则，转到(2)。
　(7)如果保留下来的个体中包含全局最优值，或者计算的代数大于限定值，算法结束；否则，转到(2)。
　(8)输出最佳目标函数值。
　本文提出的IGASA算法伪代码如下：

　上述代码中，P(t)是GA的种群大小，Tt是初始温度，noONodes是未知节点的个数，noOAnchors是锚节点的个数，R是节点的无线射程距离，L是每个T值的迭代次数。
4 仿真结果
　为了评价IGASA算法在WSN路径选择上的性能，本文将此算法与相关的算法应用Matlab仿真进行了比较。仿真中，设实验的WSN有500个节点，将未知节点随机部署到一个100×100的规则正方形区域内，无线射程R设为10。根据参考文献[5]-[6]对两种算法的种群适应度值和网络生命周期进行比较，再通过运行时间的变化，均能证明应用本方法可以实现对WSN路径的优化。
　(1)应用IGASA算法对WSN进行路径优化仿真，种群适应度均值及最优个体的进化如图1所示。从多次仿真结果可以看出，IGASA算法在种群均值变化的同时，最优个体的适应度值均能在较小的范围浮动，全部成功地找到了优秀可行路径，接近最优结果。

　(2)应用IGASA算法和GA算法的路由路径在网络中运行，通过对如图2所示的网络生命周期的比较可以看出，随着源节点个数的增加，基于IGASA的网络生命周期一直大于基于GA的网络生命周期，从而有效均衡了网络能耗。

　将IGASA与基于GA的WSN路径优化进行比较，运行结果如表1所示，目标为通过降低搜索时间以使能耗减小。各参数如下：交叉率为0.38，变异率为0.2，种群大小为20，保存最优解占4%，对每种情况均运行20次。
本文引入GASA解决WSN的路径优化问题，采用循环策略改进了WSN的遗传路径优化算法，并将改进后的IGASA算法应用于WSN路径优化上。IGASA在确保遗传算法有效性的前提下，增强了收敛效率，防止了“早熟”现象的发生。相对于标准模拟退火算法以及最优保存遗传算法，该算法提高了算法的收敛效率又不失算法的收敛速度，具有相对的优越性。仿真结果表明，该方法取得了良好的定位效果，实现了最佳路径寻优的目的，可以满足实际运行需要。下一步将继续对模拟退火和选择部分进行改进，以获得更好的效果。

参考文献
[1] 周洪伟，原锦辉，张来顺.遗传算法“早熟”现象的改进策略[J].计算机工程，2007，33(19)：201-203.
[2] 刘泉，梁小宇.一种基于被动分簇算法的能源有效WSN模型[J].计算机工程与应用，2007，43(16)：142-145.
[3] 李陶深，李朔，陈松乔，等.基于遗传算法的网络选播路由算法的研究[J].小型微型计算机系统，2005，26(1)：50-55.
[4] 曹恒智，余先川.单亲遗传模拟退火及在组合优化问题中的应用[J].北京邮电大学学报，2008，31(3)：38-41.
[5] 雷霖，李伟峰，王厚军.基于遗传算法的无线传感器网络路径优化[J].电子科技大学学报，2009，38(2)：227-230.
[6] TAM V， CHENG K Y， LUI K S. Using micro-genetic algorithms to improve localization in wireless sensor networks[J]. Journal of Communications， Academy， 2006(7)：47-52.