WSNs中基于蚁群模拟退火算法的移动Agent访问路径规划.pdf

2012年10月西北工业大学学报Oct．2012
第30卷第5期JournalofNorthwesternPolytechnicalUniversityVol．30No．5

WSNs中基于蚁群模拟退火算法的
移动Agent访问路径规划

张亚明1，史浩山1，刘燕2，姜飞3

()1．西北工业大学电子信息学院，陕西西安710072;2．空军工程大学电讯工程学院，陕西西安710077
3．解放军西安通信学院通信指挥系，陕西西安710106

摘要:关于无线传感器网络(WSNs)中移动Agent(MA)路由规划问题的解决方法，基本都以把它抽
象成为一个无向全连通图(CompletelyConnectedGraph)作为分析的前提，但一跳网络在实际的WSNs
应用中并不合理。文章提出一种适用于多跳WSNs的基于蚁群模拟退火算法(ACA-SAA)的移动A-
gent访问路径规划模型。在Sink节点建立包含源节点在内的本地网络节点关系表LNNRT，将MA访
问路径分解为定向子路径、数据融合子路径和返回子路径，利用ACA-SAA算法分别对子路径的解进
行进化计算以求得最优解路径。仿真结果表明，随着网络规模的扩大，该优化模型优势明显，ACA-
SAA表现出比SAA和ACA算法更好的性能。

关键词:无线传感器网络，路由算法，移动Agent，蚁群算法，模拟退火算法
中图分类号:TP393文献标识码:A文章编号:1000-2758(2012)05-0629-07

无线传感器网络(WirelessSensorNetworks，婪算法。但这两种算法的性能与起始节点、节点分
WSNs)由大量具有数据感知、信息处理和无线通信布和数量等因素有关，波动较大，也难以保证可形成
能力的传感器节点所组成［1］。由于节点资源严重闭合的Agent访问路径。目前国内外的研究多采用
受限，因此，如何设计出一种有效的数据融合算法一遗传算法(GeneticAlgorithm，GA)来有效解决MA
直是WSN研究中的一个难点。Qi等［2］针对此问题的路径规划问题［4-6］，并都获得了较满意的结果。
提出了一种在WSN中基于移动Agent(MobileA-但它们的不足在于:①大都把WSNs抽象成一个无
gent，MA)的分布式计算模型，MA由Sink节点创建向全连通图(CompletelyConnectedGraph)或基于簇
之后，可在节点间自主迁移并进行数据处理，最终携的拓扑结构［2］，网络内或簇内各节点之间距离都为
带融合后的数据返回Sink节点。这为有效减少网一跳，从而将MA路径规划问题转化成典型NP完
络负载、带宽及延时，实现网络的可扩展性、可靠性全问题［7］之后利用GA算法求解，这并不符合多跳
及容错性提供了较好的解决思路。网络的特点。②GA算法并不适用于多跳网络。在
在基于MA的WSNs中，MA按一定路径访问网WSNs中，MA从Sink出发，经多跳之后回到Sink，
络节点，数据融合结果一旦满足应用所需，MA将终解路径中的相邻节点之间都存在连接关系，GA中
止访问并返回Sink节点。移动Agent访问路径规的交叉和变异操作将会以大概率导致新解成为不合
［］
划3确定MA在WSNs中的访问节点集及先后顺法解。③多数方法设定Sink节点可获得全网拓扑
序，要求以较小的系统代价满足较好的应用性能，是信息和各节点访问代价，但并没有给出获得相关信
WSNs中有效实施MA机制的核心问题之一。针对息的方法。④出于算法实现考虑，多数方法附加网
MA在WSNs中的访问路径规划问题，Qi等［2］最早络节点不能被重复访问以缩小搜索空间，但其在实
提出了全局最近邻优先(GlobalClosestFirst，GCF)际应用中并不合理。为解决上述方法的缺陷，本文
和局部最近邻优先(LocalClosestFirst，LCF)两种贪提出一种适用于多跳WSNs的基于蚁群(AntColony

收稿日期:2011-10-28
作者简介:张亚明(1980—)，西北工业大学博士研究生，主要从事无线传感器网络关键技术研究。

书
·630·西北工业大学学报第30卷

Algorithm，ACA)模拟退火(simulatedannealingalgo-2.1MA访问路径规划模型概述
rithm，SAA)算法(ACA-SAA)的MA访问路径规划首先基于文献［8］，利用改进后的定向扩散
模型。(DirectedDiffusion，DD)机制解决源节点的发现以
及各节点的本地邻居关系表(即梯度)的建立。通
1WSNs中MA的访问路径规划问题过扩展探测数据发送机制，使各节点在转发探测数
据包时同时将包含自己位置信息的邻居关系表转
发，这样，在接收探测数据包的同时，可建立基
MA的访问路径规划即为确定MA在W