基于蚁群算法的高能效无线传感器网络路由方法

摘要

本发明公开一种基于蚁群算法的高能效无线传感器网络路由方法，由簇建立、簇内传输、簇间传输三部分组成。选择多跳中继节点时，采用启发式蚁群智能算法搜索多跳传输路由，在搜索过程中，消除期望重要性影响，选择节点时的概率完全由自身的链路信息素浓度决定，而局部链路信息素更新时，用协作域节点的剩余能量最小值和链路信息素增加度Q相乘除以传输能耗来更新，这个新的信息素更新方法将节点的剩余能量和传输能耗的大小经过适当放缩引入到链路的信息素更新中，当下一跳的协作域节点剩余能量越大且传输功耗越低则更易被选中，这样的传输路由方法能够减少网络总能量消耗，均衡网络节点的剩余能量，延长网络的工作寿命。

说明书

技术领域

本发明属于无线传感器网络路由领域，具体涉及一种基于蚁群算法的高 能效无线传感器网络路由方法。

背景技术

无线传感器网络是一个由大量低能耗、小尺寸、有无线通信能力的传感 器节点组成的无线自组织网络。这些传感器节点可以通过不同类型的微型传 感器节点监控、感知和采集环境数据。自从传感器网络出现后，它已经有了 很广泛的应用场景，在军事防御、流量监控、生物医疗、环境监测、紧急救 助和灾难救援方面扮演着重要角色。

在传统无线传感器网络中，每个传感器节点高度受限于电池电力。一旦 其被部署到感知区域后，节点的电池将很难替换。同时，每个节点传输信息 的能力也是受限的，所以如何减小能量消耗成为无线传感器网络研究中的重 要问题。在没有能量补充的无线传感器网络中，减小能量消耗的主要方法有： 冲突避免，减小开销，增加节点休眠时间和最优化路由等。其中，选择高能 效的路由方法是所有方法中最有效的。现存的路由算法有单跳传输，多跳传 输，协作MIMO（多输入多输出）单跳传输，协作MIMO多跳传输等。大多数 这些方法都是以簇的形式收集数据，并将数据融合后通过不同的传输方法传 输给远端基站。

目前较流行的无线传感器网络路由算法有LEACH（低功耗自适应集簇分 层型协议）、多跳LEACH、协作LEACH等。LEACH算法随机选择簇头节点并由 簇头节点把数据融合压缩后单跳传输给汇聚节点SINK（网关节点），该算法 可以使每个节点都有相等的概率成为簇头节点均衡每个节点的负担，簇头节 点对数据进行融合可以减小传输数据量进而减小能耗，但是随机选择簇头节 点忽视了节点的分布和剩余能量，可能会使形成的簇分布不合理个别节点能 量消耗过快。多跳LEACH改进了由于汇聚节点距感知区域过远导致簇头节点 单跳传输能耗过大的问题，但是多跳传输会使汇聚节点附近的簇首有大量的 数据需要转发导致“热区”问题。协作LEACH使用虚拟MIMO技术可在一定误 码率要求下得到更大的分集增益进而减小簇间远程传输的能耗，但其使用簇 间单跳传输的方法会使离汇聚节点较远的节点能量消耗过大。

发明内容

本发明所要解决的技术问题是现有传感器网络路由方法能量消耗不均 衡，个别节点死亡过快，簇间远程消耗能量大的问题，提供一种基于蚁群算 法的高能效无线传感器网络路由方法，以延长传感器网络的工作寿命。

为解决上述问题，本发明是通过以下方案实现的：

基于蚁群算法的高能效无线传感器网络路由方法，包括如下步骤：

（A）成簇阶段：

（A1）对监测区域内的传感器节点进行分簇，在每一轮开始时，先计算 每个节点对应的阀值函数T_i，后让每个节点随机生成一个0至1间的数，并 让这个数与该节点对应的阀值函数T_i进行比较，若这个数小于该节点对应的 阀值函数T_i并且该节点未被标记，则该节点选举自己为临时簇头节点；其中 阀值函数T_i的计算公式为：

$T_i=\frac{k}{N-k\times \left(r\mathrm{mod}\frac{N}{k}\right)}\times \frac{E_{\mathrm{remain}\_i}}{E_{\mathrm{initial}\_i}}---\left(1\right)$

式中，T_i为节点i的阀值函数，k为预期簇头节点数，N为总节点数，r 为当前网络运行轮数，mod为求余函数，E_{remain_i}为节点i当前剩余能量，E_{initial_i}为节点i初始能量；

（A2）当所有节点都完成选举后，比较所有临时簇头节点的相互间隔距 离，若间隔距离小于最佳间隔距离R，则取消能量较小的节点的临时簇头节 点身份，最终剩下的临时簇头节点将被定为本轮网络的实际簇头节点；其中 最佳间隔距离R的计算公式为：

$R=L/\sqrt{\mathrm{k\pi }}---\left(2\right)$

式中，R为最佳间隔距离，L为传感器网络感知区域的边长，k为预期簇 头节点数；

（A3）簇头节点确定后，所有簇头节点将广播一个广告信息给网络内的 所有剩余节点，剩余节点依据接收到簇头节点广告信号的强度选择簇加入并 向加入簇的簇头节点发送确认加入信息；

（A4）每个簇的簇头节点在确认完簇内成员后，分别计算该簇内非簇头 节点的簇间数据传输能耗参考值δ，每个簇的簇头节点选择簇内簇间数据传 输能耗参考值δ最大的节点作为协作节点，其余为普通成员节点，完成协作 分簇；其中簇间数据传输能耗参考值δ的计算公式为：

δ=E_{remain_i}/P_{coop_i}                 （3）

式中，δ为簇间数据传输能耗参考值，E_{remain_i}是簇内的i号节点剩余能量， P_{coop_i}为预先已知的i节点协作传输数据到汇聚节点所需能耗；其中，簇头节 点是一个簇内的收集数据的节点，有几个簇就有几个簇头节点，而汇聚节点 在整个网络中只有一个，所有的簇头节点要把数据传给汇聚节点；

（B）路由阶段：

（B1）每个簇的簇头节点先收集相邻簇的簇头节点信息，这些信息包括 相邻节点的剩余能量、位置和信息素浓度，后根据收集到的信息更新信息素 浓度，再更新簇头节点路由表的邻节点概率P_ij^k；其中

信息素浓度的更新公式为：

τ_ij(t+△t)=(1-ρ)τ_ij(t)+△τ_ij             （4）

式中，ρ为预先已知的信息素挥发系数，△τ_ij为信息素释放量、其计算公 式为：

${\mathrm{\Delta \tau }}_{\mathrm{ij}}=\underset{k=1}{\overset{m}{\Sigma }}{{\mathrm{\Delta \tau }}_{\mathrm{ij}}}^k---\left(5\right)$

式中，△τ_ij为链路信息素释放量，△τ_ij^k为第k只蚂蚁的信息素浓度、其计 算公式为：

式中，△τ_ij^k为第k只蚂蚁的信息素浓度，Q为预先已知的蚂蚁完成一次路 径搜索信息素释放总量，C为簇i中簇头节点和协作节点剩余能量的最小值， L_k为第k只蚂蚁从簇i到簇j完成一次传输所需的能耗、其计算公式为；

$L_k=\underset{k=1}{\overset{h-1}{\Sigma }}((M_t+M_r)\times E_C+E_{\mathrm{amp}}\times d_{\mathrm{hop}}{(i,k)}^4)+M_t\times E_c+E_{\mathrm{amp}}\times d_{\mathrm{hop}}{(i,h)}^4---\left(7\right)$

式中，L_k为第k只蚂蚁从簇i到簇j完成一次传输所需的能耗，M_t和M_r分别为人为设定的、每个簇中用作协作MIMO的发送节点数和接收节点数，E_c为传输每比特数据电路能量消耗，E_amp为每比特每单位距离协作多跳传输能 耗，d_hop(i,k)为从簇i开始到汇聚节点的路径中第k跳的距离，h为该路径总 共需要的跳数；

邻节点概率P_ij^k的计算公式为：

式中，P_ij^k为邻节点概率，list_k为节点i中蚂蚁k可访问的邻节点集，τ_ij(t) 表示t时刻节点i到节点j的信息素浓度的大小，τ_is(t)表示t时刻节点i到 节点s的信息素浓度的大小，τ_ij^α(t)和τ_is^α(t)都是通过式（4）计算得到，α表 示剩余信息的相对重要程度，与剩余信息的相对重要性相关；η_ij表示节点i 到节点j的启发信息概率的大小，η_is表示节点i到节点s的启发信息概率的 大小，β表示期望值的相对重要程度，与期望信息的相对重要性相关；

η_ij的计算公式为：

${\eta }_{\mathrm{ij}}=\frac{1}{d_{\mathrm{ij}}}---\left(9\right)$

式中，η_ij为节点i到节点j的启发信息概率的大小，d_ij为节点i到节点 j的距离；

η_is的计算公式为：

${\eta }_{\mathrm{is}}=\frac{1}{d_{\mathrm{is}}}---\left(10\right)$

式中，η_is为节点i到节点s的启发信息概率的大小，d_is为节点i到节点 s的距离；

（B2）每个簇的簇头节点依据路由表中的邻节点概率P_ij^k寻找最优多跳传 输路径，并把路由信息广播给簇内的协作节点；

（3）稳定传输阶段：

每个簇的普通成员节点将采集到的数据广播给簇头节点和簇内协作节 点，簇头节点和协作节点在接收完所有簇内普通成员节点的数据后对自己采 集和接收到的数据进行压缩融合；然后簇头节点和协作节点查询其路由表中 的下一跳簇号，使用协作MIMO多播方法将融合数据转发给下一跳簇中的所有 协作节点，直到到达汇聚节点SINK。

进一步的，在步骤（A3）中，剩余节点向簇头节点发送的确认加入信息 包括该节点的ID号和该节点的剩余能量。

进一步的，在步骤（A4）中，每个簇的簇头节点在完成协作节点选择后 还需向所有节点广播TDMA规划和协作节点信息。

进一步的，在步骤（B1）中，计算邻节点概率P_ij^k时，剩余信息的相对重 要程度α的取值范围为α∈[0,5]；期望值的相对重要程度β的取值范围为β=0。

进一步的，在步骤（B1）中，在更新链路信息素释放量△τ_ij时，所述第k 只蚂蚁从簇i到簇j完成一次传输所需的能耗L_k需要经过乘以放缩系数进行 修正的步骤。即在更新链路信息素释放量△τ_ij时，用蚂蚁完成一次路径搜索信 息素释放总量Q乘以簇i中簇头和协作节点剩余能量的最小值C除以第k只 蚂蚁从簇i到簇j完成一次传输所需的能耗值经过适当的放缩后更新。

进一步的，在步骤（B1）中，所述用于修正第k只蚂蚁从簇i到簇j完 成一次传输所需的能耗L_k的放缩系数介于10⁴～10⁷之间。

本发明基于蚁群算法的高能效的无线传感器网络路由方法，适合于分层 传感器网络结构。此路由方法由簇建立、簇内传输、簇间传输三部分组成。 在簇建立阶段，采用分布式方法，每一轮未标记的所有节点产生随机数并与 全网的阈值函数相比选出簇头，然后其他节点根据接收到的信号强度加入簇， 之后根据所成簇的分布和规模采用取消过密簇和调整阈值函数自适应均衡 簇。在簇内阶段，成员节点采用广播的形式将感知数据发送给簇头和协作节 点。在簇间传输阶段，在簇内选择成员节点的剩余能量除以传输功耗的最大 值者作为协作节点，然后采用多跳协同MIMO的传输方法发送数据到SINK， 而选择多跳中继节点时，采用启发式蚁群智能算法搜索多跳传输路由，在搜 索过程中，消除期望重要性影响，选择节点时的概率完全由自身的链路信息 素浓度决定，而局部链路信息素更新时，用协作域节点的剩余能量最小值和 链路信息素增加度Q相乘除以传输能耗来更新，这个新的信息素更新方法将 节点的剩余能量和传输能耗的大小经过适当放缩引入到链路的信息素更新 中，当下一跳的协作域节点剩余能量越大且传输功耗越低则更易被选中，这 样的传输路由方法能够减少网络总能量消耗，均衡网络节点的剩余能量，延 长网络的工作寿命。

与现有技术相比，本发明具有如下优点：

1、在每一轮簇头节点选举时把节点剩余能量纳入考虑范围并根据簇头节 点密度调整簇头节点数量，并且在选取每个簇协作节点时以簇间传输能耗和 剩余能量作为选择标准，有效均衡了各节点能耗，避免个别节点能量消耗过 快，延长网络整体寿命。

2、簇间传输使用协作MIMO多播技术，充分利用了传感器网络节点分布 较密的特性，有效减少簇间传输的能耗。远程簇间传输采用多跳方式可以避 免单跳距离过远造成节点传输能耗过大。

3、使用蚁群算法搜索多跳传输最优路径并把剩余能量和距离加入启发因 子，可以避免个别节点因总要转发数据而过早能量耗尽，均衡了多跳能量消 耗，在均衡和能耗上取得较好的折中，进而延长网络的工作寿命。

附图说明

图1是本发明采用蚁群算法搜索到的协作MIMO多跳传输方法系统模型 图。

图2是本发明在MATLAB环境下仿真得到的网络工作寿命曲线。

具体实施方式

一种基于蚁群算法的高能效无线传感器网络路由方法，包括如下步骤：

（A）成簇阶段：对监测区域内的传感器节点进行分簇，依据阀值函数每 一轮随机选择簇头节点并使剩余能量多的节点成为簇头节点的概率增大，若 选出的簇头节点分布过密则取消一部分簇头节点自适应的调整的簇的分布规 模，除簇头节点外的普通节点依据接收到的簇头节点广播信号强度加入簇， 簇头节点依据簇间多跳MIMO传输的剩余能量、能耗大小选择协作节点；成簇 的过程通过步骤（A1）、（A2）自适应调整簇的分布和规模，通过步骤（A3） 选择协作节点。

（A1）对监测区域内的传感器节点进行分簇，以循环的方式随机选择簇 头节点,在每一轮开始时，先计算每个节点对应的阀值函数T_i，后让每个节点 随机生成一个0至1间的数，并让这个数与该节点对应的阀值函数T_i进行比 较，若这个数小于该节点对应的阀值函数T_i并且该节点未被标记，则该节点 选举自己为临时簇头节点；其中阀值函数T_i的计算公式为：

$T_i=\frac{k}{N-k\times \left(r\mathrm{mod}\frac{N}{k}\right)}\times \frac{E_{\mathrm{remain}\_i}}{E_{\mathrm{initial}\_i}}---\left(1\right)$

式中，T_i为节点i的阀值函数，k为预期簇头节点数，N为总节点数，r 为当前网络运行轮数，mod为求余函数，E_{remain_i}为节点i当前剩余能量，E_{initial_i}为节点i初始能量；

（A2）当所有节点都完成选举后，比较所有临时簇头节点的相互间隔距 离，若间隔距离小于最佳间隔距离R，则取消能量较小的节点的临时簇头节 点身份，最终剩下的临时簇头节点将被定为本轮网络的实际簇头节点；其中 最佳间隔距离R的计算公式为：

$R=L/\sqrt{\mathrm{k\pi }}---\left(2\right)$

式中，R为最佳间隔距离，L为传感器网络感知区域的边长，k为预期簇 头节点数；

（A3）簇头节点确定后，所有簇头节点将广播一个广告信息给网络内的 所有剩余节点，剩余节点依据接收到簇头节点广告信号的强度选择簇加入并 向加入簇的簇头节点发送确认加入信息；其中剩余节点向簇头节点发送的确 认加入信息包括该节点的ID号和该节点的剩余能量；

（A4）每个簇的簇头节点在确认完簇内成员后，分别计算该簇内非簇头 节点的簇间数据传输能耗参考值δ，每个簇的簇头节点选择簇内簇间数据传 输能耗参考值δ最大的节点作为协作节点，其余为普通成员节点，完成协作 分簇；簇头节点每个簇的簇头在完成协作节点选择后还需向所有节点广播 TDMA规划和协作节点信息。其中簇间数据传输能耗参考值δ的计算公式为：

δ=E_{remain_i}/P_{coop_i}                （3）

式中，δ为簇间数据传输能耗参考值，E_{remain_i}是簇内的i号节点剩余能量， P_{coop_i}为预先已知的该i节点协作传输数据到汇聚节点所需能耗，其根据能耗 模型以及距离计算得到；其中，簇头节点是一个簇内的收集数据的节点，有 几个簇就有几个簇头，而汇聚节点在整个网络中只有一个，所有的簇头要把 数据传给汇聚节点；

（B）路由阶段：使用蚁群算法寻找簇间多跳协作传输的最优路径，生成 簇头节点和协作节点的路由表。

（B1）每个簇的簇头节点先收集相邻簇的簇头节点信息，这些信息包括 相邻节点的剩余能量、位置和信息素浓度，后根据收集到的信息更新信息素 浓度，再更新簇头节点路由表的邻节点概率P_ij^k；其中

信息素浓度的更新公式为：

τ_ij(t+△t)=(1-ρ)τ_ij(t)+△τ_ij                 （4）

式中，ρ为信息素挥发系数，△τ_ij为信息素释放量、其计算公式为：

${\mathrm{\Delta \tau }}_{\mathrm{ij}}=\underset{k=1}{\overset{m}{\Sigma }}{{\mathrm{\Delta \tau }}_{\mathrm{ij}}}^k---\left(5\right)$

式中，△τ_ij为链路信息素释放量，△τ_ij^k为第k只蚂蚁的信息素浓度、其计 算公式为：

式中，△τ_ij^k为第k只蚂蚁的信息素浓度，Q为蚂蚁完成一次路径搜索信息 素释放总量，C为簇i中簇头节点和协作节点剩余能量的最小值，L_k为第k 只蚂蚁从簇i到簇j完成一次传输所需的能耗。通过式（6）更新信息素后， 可使得蚂蚁找到的路径节点传输功耗最低，能量消耗更小。为了合理计算信 息素的更新大小，这里需要给L_k乘以系数（如10⁶）进行修正，即L_k需要做适 当的放缩，其计算公式为；

$L_k=\underset{k=1}{\overset{h-1}{\Sigma }}((M_t+M_r)\times E_C+E_{\mathrm{amp}}\times d_{\mathrm{hop}}{(i,k)}^4)+M_t\times E_c+E_{\mathrm{amp}}\times d_{\mathrm{hop}}{(i,h)}^4---\left(7\right)$

式中，L_k为第k只蚂蚁从簇i到簇j完成一次传输所需的能耗，M_t和M_r分别为每个簇中用作协作MIMO的发送节点数和接收节点数，E_c为传输每比特 数据电路能量消耗，E_amp为每比特每单位距离协作多跳传输能耗，d_hop(i,k)为 从簇i开始到汇聚节点的路径中第k跳的距离，h为该路径总共需要的跳数；

邻节点概率P_ij^k的计算公式为：

式中，P_ij^k为邻节点概率，list_k为节点i中蚂蚁k可访问的邻节点集，τ_ij(t) 表示t时刻节点i到节点j的信息素浓度的大小，τ_is(t)表示t时刻节点i到 节点s的信息素浓度的大小，τ_ij^α(t)通过τ_ij(t+△t)=(1-ρ)τ_ij(t)+△τ_ij即式（4）计 算得到，τ_is^α(t)通过τ_is(t+△t)=(1-ρ)τ_is(t)+△τ_is即式（4）计算得到，α表示剩余 信息的相对重要程度，与剩余信息的相对重要性相关；η_ij表示节点i到节点 j的启发信息概率的大小，η_is表示节点i到节点s的启发信息概率的大小，β 表示期望值的相对重要程度，与期望信息的相对重要性相关；τ_is(t)和η_is中的 小标s是代表一个变量，s∈list_k。

η_ij的计算公式为：

${\eta }_{\mathrm{ij}}=\frac{1}{d_{\mathrm{ij}}}---\left(9\right)$

式中，η_ij为节点i到节点j的启发信息概率的大小，d_ij为节点i到节点 j的距离；

η_is的计算公式为：

${\eta }_{\mathrm{is}}=\frac{1}{d_{\mathrm{is}}}---\left(10\right)$

在本实施例中，剩余信息的相对重要程度α的取值范围为α∈[0,5]；计算 邻节点概率P_ij^k时，期望值的相对重要程度β的取值范围为β=0，以消除期望 重要性的影响。

（B2）每个簇的簇头节点依据路由表中的邻节点概率P_ij^k寻找最优多跳传 输路径，并把路由信息广播给簇内的协作节点；

（3）稳定传输阶段：

每个簇的普通成员节点将采集到的数据广播给簇头节点和簇内协作节 点，簇头节点和协作节点在接收完所有簇内普通成员节点的数据后对自己采 集和接收到的数据进行压缩融合；然后簇头节点和协作节点查询其路由表中 的下一跳簇号，使用协作MIMO多播方法将融合数据转发给下一跳簇中的所有 协作节点，直到到达汇聚节点SINK。

在MATLAB仿真环境下，使用Monte Carlo对本发明的网络工作寿命进行 仿真。仿真场景为在100×100区域内随机均匀布置100个传感器节点，汇聚节 点距离最近节点位置为120，每轮每个传感器节点发送数据为2000比特。

本发明的路由方法和协作LEACH在网络工作寿命方面的比较如图2所示。 COOP-LEACH的第一个节点的死亡时间约为1100轮，而ACAMIMO的第一个节 点的死亡时间约为1700轮，这说明本发明可以使各节点能量消耗均衡，延长 网络的工作寿命。这主要是因为成簇阶段把节点剩余能量纳入选择因素，避 免了个别节点能量消耗过快，簇间协作MIMO多跳传输方案减小了簇间传输能 耗，用剩余能量和传输功耗共同构建信息素更新方法的蚁群算法可以搜索得 到多条传输的最优路径，在能耗和均衡方面取得较好的折中。I-ACAMIMO第 一个节点死亡周期在1900轮左右，说明改进的基于蚁群算法的多跳传输路由 方法比简单的基于蚁群算法的多跳传输路由方法更节省能耗，改进的方法利 用新的搜索反馈机制选择的中继节点更节省能耗，延长了工作寿命。