1 引 言

无线传感器网络(Wireless Sensor Networks,WSNs)是指在一定区域范围内,布撒大量具有信息采集和无线通信传输功能的微型智能传感器而组成的一种无线自组织网络[1].该网络可以对指定区域内的待监测量进行感知、处理和传输,最终将待监测量发送给观察者,从而可以实现远程检测的目的.无线传感器网络的这些特点决定了它在人们的日常生活和工农业生产中具有很大的实用价值.然而,无线传感器网络的节点能源大都来自于电池,随着电池能量的耗尽,很多环境下无法更换新的.并且当前技术无法对电池容量增大太多,能耗问题已经成为无线传感器网络发展的最大制约因素之一.因此,该问题成为了国内外学者研究的热点.其中,采用对无线传感器网络分簇路由进行优化来节约网络能耗是主要解决方式之一.

文献[2]所提出的LEACH是最早的分簇路由算法.该算法对所有传感器节点进行分簇,并在每个簇中选出一个簇头.这种方式与之前的方法相比,极大的节约了能耗.但是,该算法中所有簇头都是通过单跳的方式直接与Sink节点进行通信,这就会造成远离Sink节点的簇头能量消耗过快.此外,在选择簇头的时候,还存在无法保证簇头均匀分布的问题.近年来,群智能算法被引入到无线传感器网络中.其中,文献[3]在经典LEACH协议的基础上,引入蚁群优化(Ant Colony Optimization,ACO)算法,提出了一种基于蚁群的无线传感器网络分簇路由协议(ACO-LEACH),在一定程度上实现了节约能耗和延长网络生命周期的目的.但是,使用蚁群算法搜寻路径具有盲目性,容易造成局部最优解,并且最优路径的收敛速度比较慢.因此,本文在无线传感器网络的分簇阶段采用改进的LEACH协议对传感器进行分簇和簇头的选择;在簇间路由阶段,引入量子蚁群优化(Quantum Ant Colony Optimization,QACO)算法对无线传感器网络路由路径选择问题进行优化,找到全局最优解,加快了算法的收敛速度.提出了一种基于量子蚁群优化的无线传感器网络分簇路由算法(QACO-LEACH).该算法可以更好地节约节点的能耗,延长网络的生命周期.

2 量子蚁群算法

量子进化算法(Quantum Evolutionary Algorithm,QEA)是一种基于量子计算的一些理论和概念,并且模拟了量子态矢量表示和量子旋转门运算的概率进化算法[4].QEA在种群多样性、全局优化能力和收敛速度等方面表现出比传统遗传算法更好的性能.此外,该算法容易与其他算法融合的特点,也使得其在许多优化问题中得到广泛的应用.在研究量子进化算法的基础上,文献[5]和文献[6]详细阐述了进化计算和量子计算这两个概念,并且将这两个概念融合到蚁群算法中,提出了量子蚁群优化算法.在该算法中,量子比特可用于表示每只蚂蚁任意时刻的位置信息.在每只蚂蚁移动之前,根据选择概率来选择下一时刻的位置.这种选择概率可依据每条路径上的信息素强度和可见度大小判断得到.而蚂蚁位置的改变可以使用量子比特的更新来表示.因此,需要使用量子进化算法中的量子旋转门来更新代表每只蚂蚁此时位置信息的量子比特,从而实现蚂蚁的移动.在量子蚁群算法中,可以很好的解决蚁群算法中易于陷入局部最优的问题,主要是因为有效的增加了位置的多样性.所采取的措施之一就是每只蚂蚁的位置信息都使用量子比特的两个概率幅来表示.其次就是引入了量子非门,实现了蚂蚁位置的变异.在完成了蚂蚁位置变化之后,可根据蚂蚁位置信息的变化数据,更新路径的信息素强度和可见度大小.更新之后的信息素强度和可见度大小,又成为接下来其他蚂蚁选择概率的判断依据.与传统蚁群算法相比,同样数量的蚂蚁,量子蚁群算法的搜索空间更大,收敛速度更快,能更好的找到全局最优解.

3 基于量子蚁群算法的WSN分簇路由算法

传统的WSN分簇路由算法具有周期性,每个周期都包括两个阶段:簇形成阶段和簇间路由阶段[7].本文所提出的QACO-LEACH与此相同,在每一个周期中,我们将首先把所有节点划分成很多簇,然后才是等待数据的传输.

在簇形成阶段,每个簇中簇头的选择是需要解决的首要任务,该簇头节点将要承担比普通节点更多的额外任务,比如数据融合和收发消息等,这就必然会导致簇头节点比普通节点消耗更多的能量[8].因此,节点的剩余能量毋庸置疑是我们在选择簇头节点时必须要考虑的一个重要因素.此外,为了解决随机性选择簇头导致的簇头节点分布过于密集的情况,本文设定一个参数L,对于临近的两个待选簇头节点,首先判断两者之间的距离大小,若距离小于L,就比较两者各自的剩余能量大小.选择剩余能量大的节点作为簇头,另一个自然成为普通节点,从而确保形成的簇更加合理,避免了簇头“扎堆”现象.