论文部分内容阅读
最近在微电子机械系统(MEMS)和无线通信技术领域的进步使得人们对一种新型的网络系统-传感器网络的研究越来越多[1][2][3][4]。这种网络是由一些集成了传感、计算、通讯甚至移动能力的微小传感器节点组成。一个传感器网络通常会由大量的配置于探测区域的传感器节点构成,这些传感器节点的位置不需要事先确定,这就使得其可以随机部署于难以接近的地形或者灾难救援中,另一方面,这意味着传感器网络的协议和算法要有自组织的能力。在这种网络中多传感器节点的合作对于解决单个传感器节点的有限的传感、处理能力,特别是有限的能量供应是最本质的,并且可以提高决策过程的可信度。现在传感器网络已经得到了越来越多的应用,其中包括在军事,医疗,家庭中的应用。在通常的分布式网络中,低带宽的无线通信是传感器节点之间通讯的唯一方式。由于这些传感器节点通常是处理能力,带宽有限的微电源装置,这就使得电源消耗必须保持在足够小的水平以保证完成正常的通讯任务。在传统的分布式网络大都是基于一个共同的网络计算模型:C/S模型,但是C/S模型并不适合于分布式传感器网络中的数据融合。C/S模型存在网络流量大,不能实时的响应负荷变化等缺点。为了克服传统分布式网络的这些不足,一种称作基于移动代理的分布式网络(MADSNs)被提出来[13]。这种网络对于网络带宽需求大大减少,有着很强的网络稳定性,可扩展性。MADSNs中一个重要的问题就是移动代理路由的计算问题。在文献[18]中作者针对一种特殊的情形——目标识别与追踪环境下的MADSNs,研究了相应的移动代理路由问题。我们将MADSNs中的移动代理路由问题(MARP)表示为一个组合优化问题。问题的目标是要找一条路由并使得路径损耗和节点损耗尽量小。我们指出MARP问题是一个NP-C问题并且等价于一个特殊的MTSP问题。针对问题的特点,我们提出了一种改进的蚁群算法BB-AS来求解该问题。蚁群算法是由M.Dorigo等[28][29][30][31]于上世纪90年代提出的一类群智能优化算法,在解决传统优化方法难以奏效的具有NP-hard特性的组合优化问题,如中取得了令人鼓舞的效果,国际著名杂志《Nature》曾经多次对蚁群算法进行过报道[32][33][34]。目前,蚁群算法在理论和应用上都取得了很大进展,成为蓬勃发展的热点研究课题,但是蚁群算法也存在算法收敛慢等表现不如时兴的算法的缺点。针对基本蚁群算法收敛速度慢不适应于像MARP等问题求解的缺点,本文中,我们提出了一种基于产生概率和转移概率合成的转移概率计算,基于临域信息的初始化信息素加权,混合信息素更新等改进策略,结合2-opt局部搜索优化提出了BB-AS算法。在与当前比较优秀的MMAS的仿真比较显示该算法收敛速度大大提高,而且求解质量也很令人满意。通过对算法流程的改进我们又将BB-AS降低到与AS算法相同的水平,因此BB-AS算法比较适合于像MARP等实时应用。