蚁群优化算法(Ant Colony Optimization, ACO)^[11]是基于蚂蚁觅食过程而提出的一种群智能算法. 蚂蚁在寻找食物的过程中会在路径上释放一定的信息素，之后的蚂蚁通过感觉信息素的浓度，沿着信息素最高的路径寻找食物，同时继续释放信息素. 由于形成了正反馈机制，信息素会在通向食物源较短的路径上越积越多，吸引了更多的蚂蚁聚集到该路径中，从而最终选出最优路径.

假定蚂蚁种群的个数为m, 节点个数为n, 在初始阶段，m只蚂蚁被任意放置在不同的节点上，每条路径上的初始信息素为τ_ij(0). 蚂蚁根据每条路径上信息素的量决定转移方向，在t时刻从节点i移动到节点j的移动概率p_{i, j}(t)可表示为

其中，τ_{i, j}(t)表示t时刻节点(i, j)上的信息素数量，η_{i, j}(t)表示t时刻节点(i, j)上的启发函数，即η_{i, j}(t)=1/d_{i, j}. d_{i, j}表示节点(i, j)之间的欧几里得距离，α, β表示控制参数.

信息素的更新是指蚂蚁在找到食物后，对其在路径上留下的信息素进行更新

其中，Q为信息质量系数，表示蚂蚁一次释放的信息绝对质量，L_k表示本次周游中所走的路径总长度. ρ∈[0, 1]是挥发系数，Δτ_{i, j}^k (t)和Δτ_{i, j}(t)分别为一次循环第k只蚂蚁和m只蚂蚁在节点(i, j)处的信息素增量. 记录t时刻所有蚂蚁的行走节点信息，通过对比选取最佳适应度的蚂蚁信息. 经过多次迭代后的最佳适应度蚂蚁信息即为最优解.

在无线传感器网络中，为了满足数据采集质量和解析度的要求，以及尽可能增加网络寿命的需要，在传感器节点部署过程中实际数目往往大于感知任务所必须的数目. 但是，为了避免信息冗余，不可能所有传感器节点同时感知任务. 因此，需要考虑节点的信息效用和覆盖范围，节点间的距离及剩余能量等因素来选择一条最优路由将数据传输到基站. 节能路由采用最短路径优化算法计算传感器节点到基站的消息传输路径，首先建立最短路径的路由表，然后节点根据多条传输路径向基站节点发送感应数据时，此时只需选择其父节点作为传输中继，而不用向网络中每个节点做广播操作，从而避免了不必要的能量消耗.

假定WSN中，设定区域A内存有N个随机部署的传感器节点S={S₁, S₂, …, S_N}和一个基站，基站与网络区域存在一定距离. 传感器节点和基站不可移动，传感器节点能量受限，而基站能量不受限制. 所有传感器节点都可以直接或间接(通过中间传感器节点)与基站通信，每个传感器节点都有唯一的身份标识号(Identity Document, ID). 网络中用于发送和接收消息的无线信道是对称的.

本文采用多信息素蚁群算法对WSN中传感器节点间的距离、剩余能量和相邻节点数3个目标进行优化，利用第一信息素感测节点之间的距离，发现网络中每个传感器节点的可用邻居，并将它们的信息存储在一维矩阵中；第二信息素存储有关相邻节点剩余能量的信息；第三信息素使用概率密度分布函数确定树状结构中主动参与向BS传输所需传感器节点的最佳数量. 其中，第一信息素为局部信息素，第二、第三信息素为全局信息素. 局部信息素用于发现最佳节点间的距离，即最优局部路径；全局信息素用来控制全局最优路径. 初始化蚂蚁种群数量为M, ε为选择传感器节点的最小概率.

在上述模型假设的基础上，所有节点采用多信息素蚁群优化算法发现父节点. 首先，初始化蚂蚁种群，每个传感器节点释放一个前向蚂蚁k, 对于当前传感器节点i, 在其同步信号的时隙内广播一个数据包，该数据包包含其坐标和半径为r2的圆内剩余能量的信息. 其邻居节点j根据与节点i之间的距离，以下列概率接收该数据

式(5)中：α和β表示衰减参数，d_ij是传感器节点i和j之间的距离，r1和r2分别表示传感器节点检测到的最小和最大距离. 从式(5)可以看出，当前传感器节点i可以感知到半径为r1的圆内的所有事件，当半径超过r1后检测的概率呈指数下降，而在r2范围以外的事件将不会被感知.

根据式(5), 在当前传感器节点i的布尔圆盘模型范围内，将可以检测到的相邻节点组合成一个传感器节点覆盖集合A_neigh, 该集合可以采用表示为

根据式(6), 当前传感器节点i覆盖范围内的每个节点在t时刻的剩余能量定义为

式(7)中：residualEgy_j(t)表示覆盖集合A_neigh的第j个传感器节点的剩余能量.

每只蚂蚁根据第三信息素minSN_ij从其覆盖集A_neigh中发现传感器节点i所需的最小邻居节点数，此步骤的目标是从覆盖集中确定每个传感器节点所需的最小传感器节点数，以完成传输过程. 这是因为参与传输流量数据的节点越少，网络的生存期就越长. 为了实现这一目标，采用高斯函数初始化第三信息素MinSN_ij.

式(8)中：n_i是覆盖集合A_neigh中的传感器节点数，j=1, …, n_i. σ是一个常数，μ_i初始化为零，由于传感器节点i必须由一些传感器覆盖，当蚁群中出现蚂蚁未能组成有效的传感器覆盖集合时，说明传感器节点i区域内的传感器分布不足，因此需要增加μ_i值，确保在所有蚂蚁情况下都可以组成有效的传感器覆盖. 利用minSN_ij评估蚂蚁k在t时刻选择第l个节点作为邻居节点的概率.

式(9)中：n_k^l表示由蚂蚁k从覆盖集A_neigh中确定的最小节点数. 在每个节点的迭代开始时计算此概率，将概率大于预定义阈值ε的节点，选取为传感器节点i的邻居集.

为了识别当前传感器节点i所需节点数，可以通过计算由蚂蚁k设置的邻居集中每个传感器节点的概率来获得，其定义为

式(10)中：s表示已识别的相邻节点，V_p^k表示蚂蚁k选择第p相邻节点作为父节点的次数信息. 选择具有最大概率ParSel(sen_{i, p}^k)的节点作为当前传感器节点i的父节点.

当蚂蚁k选择节点p作为合格的父节点后，p传感器节点的记录值V_p^k更新为

式中：ΔV_pi^k为变量，当蚂蚁k选择节点p作为节点i的父节点时，ΔV_pi^k为固定常数，否则为0. 整个蚁群中所有蚂蚁都采用蚂蚁k的方式选择它们合格的父节点，其中具有最高V_p^k值的父节点作为最终父节点.

假定所有传感器节点都具有相同的功能，因此可以评估在一个传感器节点上实施该算法的复杂性. 在父节点选择过程中，传感器节点的算法复杂度为O(neigh), 其中neigh是传感器节点的邻居节点数量，而传感器节点的O(1)表示该节点直接与基站通信. 在树形成过程中，如果当前传感器是父节点，则传感器节点的算法复杂度计算为O(s), 其中与传感器节点关联的子节点数目不计其中. 否则，对于没有任何关联子节点的传感器节点，复杂度为O(1). 一旦树形成之后，开始执行TDMA(Time Division Multiple Access, TDMA)无线自组网时分多址接入^[12], 数据传输阶段启动.

为了验证本文提出的路由方案的有效性，通过在网络仿真器NS2环境中进行仿真测试，采用波士顿大学提供的无线传感器网络仿真框架，对本文设计算法的性能进行测试. 传感器节点的数目为100, 在100 m×100 m的网络区域内随机分布，并且以速度为4 000 bits/s数据包的形式传输传感信息，基站位于网络区域外. 为了定量评估算法的性能，采用第一节点死亡、半数节点死亡、网络生存周期和节点剩余能量作为测试指标，并与低功耗自适应集簇分层型路由算法(Low Energy Adaptive Clustering Hierarchy, LEACH)^[8]、基于单信息素蚁群优化算法(Ant Colony Optimization, ACO)^[10]、基于树的聚类算法(Tree based clustering, TBC)^[13]和多目标分布式模糊聚类算法(Multi-objective distributed fuzzy clustering algorithm, MODFCA)^[14]等现有算法进行比较.

为了评估本文提出的节能路由算法的性能，采用以下绩效指标进行评估：①第一节点的死亡时间(First Node Dead, FND), 此度量描述第一个节点死亡后的轮循次数，通常用于评估周期性部署的WSN性能；②半数节点的死亡时间(Half Node Dead, HND), 此参数用于表示半数节点死亡的轮循次数，并在无线网络的应用区域(覆盖范围是主要关注区域)中考虑使用；③网络生存周期(Network lifetime, NLT), 网络生存周期通过所有节点死亡之后的轮循次数来衡量，用于衡量网络的总寿命；④节点剩余能量(Remaining Energy, RE), 每个传感器必须消耗一些能量来传输数据，该数据根据所使用的路由策略有所不同，可以在每个轮循之后从节点自身显示的能量中减去传感器节点所消耗的能量来计算.

图 1给出了不同节能方案在FND, HND, NLT指标上的能量效率. 从图 1中可以看出，本文通过考虑多个信息素来发现传感器节点和BS之间优化路由的方法明显优于其他方案.

根据剩余能量和100×100 m²网络区域内活动节点的数量进一步评估算法的性能，测试结果如图 2、图 3所示. 从图 2、图 3中可以观察到，本文方法的节点剩余能量在1 200轮循后为0, 比ACO方法延长了200轮，网络寿命提高20%, 这是因为本文方法具有选择功耗最小父节点的优化能力.

在无线网络的初始部署阶段，可能无法精确预测真正需要的节点数量，因此在网络设计过程中需要考虑可伸缩性，即在不重组整个网络的情况下，确定网络在一定的可接受阈值范围内容纳额外传感节点的能力. WSN网络路由协议必须具有足够的能力来提供所需的网络可伸缩性，以便适当地执行. 因此，本文为了验证算法的可扩展性，将传感器节点的数量从100个增加至300个. 可伸缩性通过测量每个节能路由方案执行轮循次数之后的第一个节点死亡时间来计算，轮循次数或稳定周期越大，可伸缩性越好.图 4给出了测试对比结果. 从图 4中可以看出，在100×100 m²区域内，当节点数目从100个增加到300个时，所有路由方案的稳定周期(轮循次数)都有所增加，这是因为随着节点数目增加，节点间距离减小. 相对于其他方案，本文提出的算法在传输期间利用较少节点能量消耗的多个信息素来选择最佳可用父节点，从而赋予了更大的可伸缩性.

在不同数量的传感器节点上计算网络的总剩余能量(Total remaining energy, TRE), 以揭示本文提出方案的稳健性，对比结果如图 5所示.图 5a、图 5b分别给出了不同节能方案在传感器节点数量为100和300时总剩余能量的测试结果，从图 5中可以看出，与其他方案相比，本文提出的方法具有明显优势.

本文提出一种基于多信息素蚁群优化的无线传感器网络节能路由算法，用于解决当前节能路由算法中出现的路由开销较大，传感器节点能耗高的问题. 该算法采用多信息素蚁群优化算法通过检测节点间的距离、剩余能量和相邻节点数来优化有效的路由，将传感器节点感知信息以最经济的能耗路径传输到基站，实现了节省路由开销和传感器节点能量的目的. 实验结果表明，本文提出的节能方案能够有效延长网络的使用寿命，比其他节能路由算法的性能更佳.