一种无线多跳中继网络中节能路由及功率分配方法

摘要

本发明公开了网络通信技术领域中的一种无线多跳中继网络中节能路由及功率分配方法。首先随机建立初始化路由，对所述初始化路由建立过程中的信息素进行更新；其次，在此基础上通过设定方法建立路由，对路由中的信息素更新；根据路由中的信息素得到最优路由，更新设定方法的指定参数；重复上述步骤设定次；最后得到的最优路由就为最终的路由。本发明综合考虑了网络节点剩余能量、有限的节点发射功率、节点间干扰及链路传输速率，全面优化网络吞吐量及能量使用效率，使得该路由算法更能适应多变的无线多跳中继网络环境，同时达到网络节能的目的。

说明书

技术领域

本发明涉及网络通信技术领域，特别涉及一种无线多跳中继网络 中节能路由及功率分配方法。

背景技术

随着无线多跳中继网络的飞速发展，其应用范围越来越广。无 线多跳中继网络所指的是一种特定的网络结构，它具有分布式控 制、自组织、无中心的特点。并且由于无线多跳中继网络节点的传 输范围有限，源节点在向目的节点发送数据时需要其他中继节点的 辅助，一直以来，无线多跳中继网络研究的重点和难点主要存在于 路由协议的设计上，也是无线多跳中继网络的设计重点。经过多年 的研究，无线多跳中继网络路由协议得到了很大的发展，应用于各 种特定场景的协议也在不断的被提出和改善。

当前，无线多跳中继网络的路由协议的主要设计目标是：满足应 用需求的同时尽量降低网络开销，取得资源利用的整体有效性。此 类问题属于NP难问题（多项式复杂程度的非确定性问题），传统的 路由算法很难解决，可采用启发式算法来处理，而蚁群算法不依赖 于具体问题的数学描述，具有很强的全局优化能力和本质上的并行 性，是解决NP难问题的有效方法。

蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特征启发 而得出的。蚂蚁觅食过程通过个体之间的信息交流与相互协议最终 找到从蚁穴到食物源的最短路径，与无线网络路由问题有着惊人的 相似之处。因此，结合无线多跳中继网络环境进行引申，将蚂蚁觅 食过程中的“蚁穴”和“食物源”当作网络中的源节点和目的节 点，将蚂蚁的行为当作网络中的路由建立，蚁群算法中有一个蚂蚁 决策表，它包括所有节点选择下一跳中继节点的转移概率和关于节 点的本地信息，蚂蚁使用这个表来指导其搜索朝着搜索空间中最有 吸引力的区域移动，这正是网络通信中路由表的形成过程。因此， 蚁群算法能够应用于无线网络的路由，通过信息素的释放寻找并维 护从源节点到达目的节点的最优路由，按照信息素的挥发算法不断 对各中继节点的信息素值进行更新，以适应网络动态变化的需要。 目前已有许多基于蚁群优化的路由算法被提出，如ARA， ARAMA，AntHocNet等。

目前，网络中出现的典型路由协议其传统的实现机制是在源和宿 节点间选择一条固定的路径，在整个传输过程中均使用这条路径传 输，直至此次传输完毕。在链路状况比较好的时候，传统的路由机 制能够正常工作。但是，无线信道的不稳定性经常会导致节点传输 范围的瞬间变化，并且节点的移动或是开关机也会导致下一跳节点 不可达，就会导致频繁的MAC层的确认、重传现象，进而引起路由 层路由维护过程或路由更新过程，在无线信道质量变差或者节点间 相互距离正好处于临界覆盖范围的情况下这种现象更为严重。这种 链路的不可靠性和不稳定性会导致很大的路由维护开销，还会造成 上层业务出现很大的时延或大量的丢包现象。

此外，随着人们对蚁群算法等启发式算法的深入研究，蚁群算 法应用于解决路由问题也越来越多。但是，现有基于蚁群算法的路 由协议仍存在一些缺点：第一，当前使用蚁群算法进行路由的主要 考虑因素仍是路由跳数，少数路由算法考虑节点剩余能量、节点发 射功率、节点间传输干扰和链路传输速率；第二，现有蚁群算法自 身存在收敛速度慢和易陷入局部最优解的缺点，降低了路由算法的 性能；第三，由于网络层和MAC层是完全脱离的，网络层无法感知 物理层链路的情况，不能在选路时候考虑利用链路的效率、能量及 干扰等因素。

发明内容

（一）要解决的技术问题

本发明要解决的技术问题是：如何提供一种路由方法，解决无 线多跳中继网络存在的网络吞吐量低、功率动态分配和能量使用效率 低的问题。

（二）技术方案

为解决上述技术问题，本发明提供了一种无线多跳中继网络中 节能路由及功率分配方法，其特征是，该方法包括以下步骤：

S1：随机建立初始化路由，对所述初始化路由建立过程中的信息 素进行更新，进入步骤S2；

S2：通过设定方法建立路由，对所述路由中的信息素更新；

S3：重复执行步骤S2第一设定次数后进入步骤S4；

S4：根据所述路由中的信息素得到最优路由，更新所述设定方法 的指定参数；若指定参数的更新次数小于第二设定次数，返回步骤S2； 否则，此时的最优路由就为最终的路由。

所述信息素通过节点发射功率、链路速率和路径信息求得。

对所述随机路由中的信息素进行更新具体为：

S11：通过贪婪算法对所述节点发射功率和链路速率进行分配；

S12：在所述节点发射功率和链路速率的基础上得到对应的链路； 当所述链路满足发射功率门限和干扰门限时，对所述链路分配节点发 射功率和链路速率；

S13：根据所述链路分配节点发射功率和链路速率对所述路径信 息进行更新。

所述步骤S2具体为：

S21：通过设定方法建立路由；

S22：通过贪婪算法对所述节点发射功率和链路速率进行分配；

S23：在所述节点发射功率和链路速率的基础上得到对应的链路； 当所述链路满足发射功率门限和干扰门限时，对所述链路分配节点发 射功率和链路速率；

S24：根据所述链路分配节点发射功率和链路速率对所述路径信 息进行更新。

根据所述路由中的信息素得到最优路由，更新所述设定方法的指 定参数具体为：

S41：根据所述节点发射功率、链路速率和路径信息计算每条路 径的适应度函数值，得到最大的适应度函数值对应的最优路由和该最 优路由的节点发射功率和链路速率；

S42：通过粒子群算法更新所述设定方法的指定参数。

所述设定方法为蚁群算法。

（三）有益效果

本发明通过贪婪算法对所述节点发射功率和链路速率进行分配 得到链路；通过发射功率门限和干扰门限条件对链路分配节点发射功 率和链路速率；根据链路分配节点发射功率和链路速率对所述路径信 息进行更新；根据节点发射功率、链路速率和路径信息计算每条路径 的总传输速率，得到最大的总传输速率对应的最优路由。本发明综合 考虑了网络节点剩余能量、有限的节点发射功率、节点间干扰及链 路传输速率等因素，以最大化全局路由传输速率为优化目标，随着 网络环境变化动态地建立路由和调整节点发射功率，从而提高了网 络吞吐量与能量使用效率，使得该路由方法更能适应多变的无线多 跳中继网路环境，同时达到网络节能的目的。

附图说明

图1是本发明流程图；

图2是网络拓扑结构图；

图3是本发明的实施例流程图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细 描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

为了解决无线多跳中继网络存在的网络吞吐量低、能量使用效率 低的问题。本发明提出了一种路由建立与功率分配的联合优化方法。

图1是本发明的流程图，本发明方法包括以下步骤：

S1：随机建立初始化路由，对所述初始化路由建立过程中的信息 素进行更新，进入步骤S2；信息素通过节点发射功率、链路速率和路 径信息求得。

S11：通过贪婪算法对所述节点发射功率和链路速率进行分配；

S12：在所述节点发射功率和链路速率的基础上得到对应的链 路；当所述链路满足发射功率门限和干扰门限时，对所述 链路分配节点发射功率和链路速率；

S13：根据所述链路分配节点发射功率和链路速率对所述路径 信息进行更新。

S2：通过设定方法建立路由，对所述路由中的信息素更新；

S21：通过设定方法建立路由；

S22：通过贪婪算法对所述节点发射功率和链路速率进行分配；

S23：在所述节点发射功率和链路速率的基础上得到对应的链 路；当所述链路满足发射功率门限和干扰门限时，对所述 链路分配节点发射功率和链路速率；

S24：根据所述链路分配节点发射功率和链路速率对所述路径 信息进行更新。

S3：重复执行步骤S2第一设定次数后进入步骤S4；

S4：根据所述路由中的信息素得到最优路由，更新所述设定方法 的指定参数；若指定参数的更新次数小于第二设定次数，返回步骤S2； 否则，此时的最优路由就为最终的路由。

S41：根据所述节点发射功率、链路速率和路径信息计算每条 路径的适应度函数值，得到最大的适应度函数值对应的最 优路由和该最优路由的节点发射功率和链路速率；

S42：通过粒子群算法更新所述设定方法的指定参数。

以下通过一个实施例对本发明进行说明：

由于实际约束条件以及目标函数的限制，无线多跳中继网络路 由和功率控制联合优化问题是组合优化问题，无法找到复杂度有效 的最优解法。为此，本实施例使用混合蚁群优化算法以及贪婪算法 联合求解这类路由建立和功率控制问题。该算法分为两大部分：第 一部分，针对蚁群算法中影响算法性能的关键参数使用粒子群算法 进行动态调整，通过混合蚁群算法实现网络路由；第二部分，路由 搜索同时结合贪婪算法实现路径上各节点发射功率控制。

1.系统模型

本发明主要针对节点自身能量受限和节点间通信干扰约束的无 线无线多跳中继网络路由与功率控制联合优化提出基于混合蚁群的 优化算法，以达到优化网络吞吐量和提高能量使用效率的目的。网 络拓扑结构如图2所示，在475m×400m范围内，随机分布N个节 点，由邻居节点连接的可通信链路M条，形成一个网络拓扑结构。

本发明假设两两节点之间的信道符合平坦衰落模型，信道增益 发射端可知。并考虑到无线网络环境中的多径衰落现象，设信道增 益G_i,j满足瑞利分布。

设x_i,j表示路径上两节点通信二进制标志，定义为：

基于混合蚁群优化的无线多跳中继网络路由及功率控制联合算 法系统模型如下：

$\max =\underset{i=1}{\overset{N}{\Sigma }}\underset{j\ne i}{\overset{N}{\underset{j=1}{\Sigma }}}{x}_{i,j}·{\log }_2(1+{\mathrm{SNR}}_{i,j})---\left(2\right)$

s.t：

$x_{i,j}\in \left\{\mathrm{0,1}\right\},\forall i,j(i\ne j)---\left(3\right)$

$\underset{i=1}{\overset{N}{\Sigma }}\underset{j\ne i}{\overset{N}{\underset{j=1}{\Sigma }}}{x}_{i,j}·P_{i,j}\le P_{\mathrm{th}},\forall i,j---\left(4\right)$

$\underset{i=1}{\overset{N}{\Sigma }}\underset{j\ne i}{\overset{N}{\underset{j=1}{\Sigma }}}{x}_{i,j}·I_{i,j}\le I_{\mathrm{th}},\forall i,j---\left(5\right)$

${\mathrm{SNR}}_{i,j}\ge {\mathrm{SNR}}_{\mathrm{th}},\forall i,j(i\ne j)---\left(6\right)$

其中：

P_th表示一条路径可以提供的最大总发射功率门限值；

P_i,j表示链路(i,j)上节点i向节点j发送数据包所用的发射 功率；

SNR_i,j是链路(i,j)上的信噪比；

SINR_th表示可正确通信的最小信噪比门限值；

I_th表示某一条路径对其周围节点通信产生的总噪声功率 门限值；

I_i,j表示链路(i,j)上节点i向节点j发送数据包所用的发射 功率对周围节点通信产生的干扰。

链路(i,j)上的信噪比SNR_i,j表示如下：

${\mathrm{SNR}}_{i,j}=\frac{G_{i,j}{P}_{i,j}}{(N_0+\underset{u\ne i}{\overset{N}{\underset{u=1}{\Sigma }}}{G}_{u,j}{P}_{u,j})}\forall i,j(i\ne j)---\left(7\right)$

其中：

P_i,j为链路(i,j)上节点i的发射功率；

P_u,j为链路(u,j)上节点u的发射功率；

N₀为加性高斯白噪声；

G_i,j为节点i与节点j之间的信道增益；

G_u,j为节点u与节点j之间的信道增益。

并假设分配给每条路径的总发射功率在0至P_th范围内，其中，P_th指系统可允许的最大路径总发射功率，P_th与初始时刻路径上各个节 点发射功率总和成正比。

公式(3)所示的第一个约束条件表示路径上两节点通信二进制标 志x_i,j的取值范围；公式(4)所示的第二个约束条件表示一条路径可提 供的最大总发射功率约束；公式(5)所示的第三个约束条件表示一条 路径建立后对其周围节点通信产生的总噪声干扰功率约束；公式(6) 所示的第四个约束条件表示每条收发链路上可正确接收时的最小信 噪比约束。

2.基于混合蚁群优化的无线多跳中继网络路由及功率控制联合 算法

（1）算法提出背景

可知蚁群算法擅长解决离散优化问题，而粒子群算法擅长连续 问题的优化。贪婪算法（又称贪心算法）是指在对问题求解时，总是 做出在当前看来是最好的选择。考虑蚁群算法中启发因子α、期望 启发因子β、局部信息素挥发因子ρ和全局信息素挥发因子γ四个参 数对蚁群算法求解系统最优解时在收敛速度及解的搜索范围等方面 的影响程度；并且路由的性能和稳定性与节点剩余能量、节点发射 功率、节点间通信干扰及网络拓扑结构有紧密的关系，因此将路由 与参数调整、节点功率控制相结合提出基于混合蚁群优化的无线多 跳中继网络路由及功率控制联合算法，使搜索到的路由满足网络约 束条件。

（2）算法整体思想

基于混合蚁群优化的无线多跳中继网络路由及功率控制联合算 法（Hybrid ant colony optimization algorithm，HACO）的基本思想： 考虑节点剩余能量、节点传输干扰量、节点发射功率和链路传输速 率四个因素采用粒子群优化算法来自适应地调整蚁群算法中的四个 参数(α,β,ρ,γ)，其中，α为启发因子、β为期望启发因子、ρ为局 部信息素挥发因子、γ为全局信息素挥发因子。达到优化路由搜索算 法的高效、快速和全面等性能；同时借鉴贪婪思想根据网络环境适 当地对路径上的节点发射功率进行调整，功率控制的结果又反作用 于路由的搜索，实现两者的均衡优化。

（3）算法具体实施方法

本发明考虑到基本蚁群算法的两点主要缺点：第一最初算法开 始时，信息素的作用不明显，主要是因为各条路径上的信息素分配 差异不明显，需经过较长的一段时间，较好路径上的信息素优势才 会明显起来，从而最终收敛于较好解，但却使算法最初浪费了较长 一段时间。第二，正反馈机制虽然能强化较好解，但却使算法容易 出现停滞现象，即只取得了局部最优解就停止搜索，而未达到全局 最优解。

因此，本发明主要围绕节点选择机制、信息素更新机制及参数 调整三方面对基本蚁群算法进行改进，并且结合贪婪算法对节点发 射功率进行控制，从而实现路由与功率控制的联合优化。

本发明中假设有K只蚂蚁，在选择模型中引入随机数q和动态 参数q₀，实现伪随机比率选择机制；在信息素更新机制中将原有的 信息素更新方式分为局部信息素更新和全局信息素更新；在蚁群算 法参数调节中采用粒子群算法根据节点剩余能量、节点传输干扰量、 节点发射功率及链路传输速率实现参数调整。具体方案如下：

第一，改进型蚁群算法节点选择机制表示如下：

$p_{i,j}^k\left(t\right)=\left(\begin{array}{c}\frac{{\left[{\tau }_{i,j}\left(t\right)\right]}^{\alpha }·{\left[{\eta }_{i,j}\left(t\right)\right]}^{\beta }}{\underset{u\in A_k}{\Sigma }{\left[{\tau }_{i,u}\left(t\right)\right]}^{\alpha }·{\left[{\eta }_{i,u}\left(t\right)\right]}^{\beta }},j\in A_k\\ 0,\mathrm{others}\end{array}\right)---\left(8\right)$

$(i^{*},j^{*})=\left(\begin{array}{c}\arg \max \{{\left[{\tau }_{i,j}\left(t\right)\right]}^{\alpha }·{\left[{\eta }_{i,j}\left(t\right)\right]}^{\beta },j\in A_k\},q\le q_0\\ \arg \max \left\{p_{i,j}^k\left(t\right)\right\},q>q_0\end{array}\right)---\left(9\right)$

其中：

(i^*,j^*)为第k只蚂蚁在第i^*个节点时选择下一跳为第j^*个 节点的通信组合；

A_k为蚂蚁k在第i个节点时可选择的下一跳节点集，为避 免环路，将已经选作中间节点的节点从A_k集合中删 除；

为时刻t蚂蚁k在第i个节点时选择下一跳为第j个 节点的概率；

α为信息素启发因子；

η_i,j(t)为时刻t任意收发节点间链路(i,j)上的期望启发函 数，由它的定义可知：此参数与链路(i,j)上的传输速 率R_i,j和节点j的剩余能量比率成正比；η_i,u(t)同理表示 时刻t任意收发节点间链路(i,u)上的期望启发函数，其

中u∈A_k；

τ_i,j(t)为时刻t任意收发节点间链路(i,j)上的信息素浓度， 由它的定义可知：此参数与路径总的传输速率成正 比，与路径消耗总的发射功率成反比；τ_i,u(t)同理表示 时刻t任意收发节点间链路(i,u)上的信息素浓度，其中 u∈A_k；

β为期望启发式因子；

τ₀为信息素初始值。

η_i,j(t)定义为：

η_i,j(t)=Q₂·R_i,j+Q₃·Er_j    （10）

其中，Q₂,Q₃为正常数,表示蚂蚁k在节点j处 的剩余能量，表示节点j的初始最大能量；表示所 有蚂蚁在节点j处的剩余能量归一化值之和；表示所 有蚂蚁在通信链路(i,j)上的总比特数。可见R_i,j越大，Er_j越大，则 η_n,m越大，启发信息越大，适应度越高。

公式(9)中的参数q是一个在[0,1]区间满足均匀分布的随机数， q₀是一个随着求解代数增加逐渐增大的动态参数，它的大小决定了 利用先验知识与探索新组合之间的相对重要性。定义q₀随迭代次数 的增加而变化的公式为：

q₀=E+(NC×F)NC_max    (11)

其中，NC为当前迭代次数，E,F为固定参数，根据试验经 验，一般取E=0.2，F=0.7。此时，q₀的取值范围是： [E,E+F]。通过这样的设置有利于消除参数q₀对算法的影响。一般 在开始阶段q₀越小，则越有利于算法展开对新节点的探索，扩大算 法的搜索空间，避免过早陷入局部最优。而在算法结束阶段q₀越 大，则有利于算法的全局收敛。因此，一般来说q₀的变化范围越 大，则算法的搜索范围越大。

第二，对基本蚁群算法的信息素更新机制进行改进。具体如 下：

1)信息素局部更新。待蚂蚁k处于节点i并选择下一跳节点为j 后，便对节点连接组合(i,j)上的信息素按如下公式进行局部更新：

τ_i,j(t)=(1-ρ)·τ_i,j(t)+ρ·τ₀    （12）

其中：

ρ(0<ρ<1)为局部信息素蒸发系数；

τ_i,j(t)为时刻t收发链路(i,j)上的信息素浓度；

τ₀为信息素初始值。

局部信息素更新机制可减少已生成的收发链路对其他蚂蚁的影 响，从而增加对更多收发节点组合的探索。

2)信息素全局更新。待所有蚂蚁都完成了一次路径搜索后，在 K只蚂蚁所代表的K种路由方案中选择使得系统信息传输速率最大 的最优路由，并按照如下公式对最优解中的每个收发节点组合(i,j) 上的信息素进行全局更新：

τ_i,j(t+1)=(1-γ)·τ_i,j(t)+γ·Δτ_i,j    （13）

其中，γ(0<γ<1)表示全局信息素蒸发系数；Δτ_i,j为构成最优解 的各收发链路(i,j)上获得的信息素浓度增量，定义为：

${\mathrm{\Delta \tau }}_{i,j}=\left(\begin{array}{c}{\mathrm{FIT}}_{\mathrm{best}},\mathrm{if}(i,j)\in G_{\mathrm{best}}\\ 0,\mathrm{ohters}\end{array}\right)---\left(14\right)$

其中，G_best表示全局最优收发节点组合(i,j)集合；FIT_best表示 找到最优解的蚂蚁所获得的适应度，定义为：

${\mathrm{FIT}}_{\mathrm{best}}=\underset{1\le k\le L}{\max }\mathrm{fit}\left(k\right)---\left(15\right)$

$\mathrm{fit}\left(k\right)=Q_4·\frac{R_{\mathrm{sum}}^k}{P_{\mathrm{sum}}^k}---\left(16\right)$

其中：

Q₄为比例常数；

fit(k)表示蚂蚁k获得的适应度,它与蚂蚁k获得的总比特 数$R_{\mathrm{sum}}^k=\underset{i=1}{\overset{N}{\Sigma }}\underset{j=1}{\overset{N}{\Sigma }}{x}_{i,j}·R_{i,j}^k$成正比；

表示第k条路径中链路(i,j)上的信息传输速率，与蚂蚁

k在路径上所耗发射功率成反比；

表示第k条路径中链路(i,j)上节点i的发射功率。

可见蚂蚁所获得比特数越多，消耗的发射功率越少fit(k)的值越 大，解的质量就越高。

第三，蚁群算法中参数调整的粒子群算法。具体如下：

在本发明中，定义蚁群算法中的启发因子α、期望启发因子 β、局部信息素挥发因子ρ和全局信息素挥发因子γ为粒子i的位置 集合x_i的四个元素，如公式（17）所示。

x_i={α_i,β_i,ρ_i,γ_i}    （17）

定义粒子群算法适应度函数为：

$\mathrm{FIT}\_\mathrm{PSO}\left(i\right)=Q_1·\frac{R_{\mathrm{sum}}^i}{P_{\mathrm{sum}}^i}---\left(18\right)$

其中：

Q₁为比例常数；

为第i个粒子所代表的第i条从源节点到目的节点路径 上各链路传输速率总和；

为第i个粒子所代表的第i条从源节点到目的节点路径 上所有中间节点发射功率总和。

蚁群算法中的四个参数调整通过个体极值全局极值 和对应的速度实现，如公式（19）、（20）所示。

$v_{\mathrm{id}}^{t+1}=w{v}_{\mathrm{id}}^t+c_1{r}_1({\mathrm{pbest}}_{\mathrm{id}}^t-x_{\mathrm{id}}^t)+c_2{r}_2({\mathrm{gbest}}_d^t-x_{\mathrm{id}}^t),\forall d\in x_i---\left(19\right)$

$x_{\mathrm{id}}^{t+1}=x_{\mathrm{id}}^t+v_{\mathrm{id}}^{t+1}---\left(20\right)$

其中：

w为惯性权重，用来描述粒子上一代速度对当前一代的影 响；

c₁为加速常量，用来调节粒子向自身最好位置方向飞行的 步长；

c₂为加速常量，用来调节粒子向全局最好位置方向飞行的 步长；

r₁、r₂为符合均匀分布的两个相互独立的随机数。

第四，基于贪婪思想的功率控制算法。具体如下：

贪婪算法（又称贪心算法）是指在对问题求解时，总是做出在当 前看来是最好的选择。

首先，由公式（2）和公式（7）可得：

$P_{i,j}^k=\frac{(2^{R_{i,j}^k}-1)\times {\mathrm{Noise}}_j}{G_{i,j}}---\left(21\right)$

其中，${\mathrm{Noise}}_j=N_0+\underset{u\ne i}{\overset{N}{\underset{u=1}{\Sigma }}}{G}_{u,j}{P}_{u,j}.$

可以看出，每增加1比特，在收发链路(i,j)上的发送节点i的发 射功率增加量按如下公式计算可得：

${\mathrm{\Delta P}}_{i,j}^k=[(2^{R_{i,j}^k+1}-1)-(2^{R_{i,j}^k}-1)]\times \frac{{\mathrm{Noise}}_j}{G_{i,j}}=\frac{2^{R_{i,j}^k}\times {\mathrm{Noise}}_j}{G_{i,j}}---\left(22\right)$

于是，收发链路(i,j)上增加的发射功率对周围节点产生的噪声 功率增加量为：

${\mathrm{\Delta I}}_{i,j}^k=\underset{r\ne i}{\overset{N}{\underset{r=1}{\Sigma }}}(G_{i,r}·{\mathrm{\Delta P}}_{i,j}^k)---\left(23\right)$

其中：

G_i,r表示节点i与节点r之间的信道增益。

为了保证在每一次为收发链路分配比特数和发射功率时的选择 是最佳的，并且满足无线多跳中继网络的资源分配约束条件，如公 式（4）、公式（5）所示。在本发明的贪婪算法中定义了如下两类判 决因子：

${\alpha }_{i,j}^P=\frac{P_{\mathrm{th}}-\tilde{P}}{{\mathrm{\Delta P}}_{i,j}^k},\forall i,j$

$\left(24\right)$

${\alpha }_{i,j}^I=\frac{I_{\mathrm{th}}-\tilde{I}}{{\mathrm{\Delta I}}_{i,j}^k},\forall i,j$

其中：

为贪婪算法中定义的一个关于链路上节点通信发射功 率代价的判决因子。其值越大，表明在链路(i,j)上增 加传输相同大小的数据比其他链路所需的节点发射功 率少，并且链路总的发射功率离功率约束值相差较 大，说明此链路(i,j)性能较好，反之亦然。

为贪婪算法中定义的一个关于链路上节点通信发射功 率对周围节点产生干扰的代价判决因子。其值越大， 表明在链路(i,j)上增加传输相同大小的数据比其他链 路所需的节点发射功率少，即对周围节点通信产生干 扰小，说明此链路(i,j)性能较好，反之亦然。

表示已经分配给各个收发链路的发射功 率总和，表示链路(i,j)上节点i现有的发射功率； 表示已经分配给各个收发链路的发射功率 对周围节点通信噪声干扰功率总和，表示链路(i,j) 上节点i现有的发射功率对周围节点通信产生的干扰。

对于使用蚁群算法搜索到的路径，为了使系统的信息传输速率 最大化，并且为了实现在增加相同比特数的情况下，选择发射功率 增加量和噪声干扰最小值所在的链路。只要判断出每个收发链路 (i,j)的值表示链路(i,j)上关于节点发射功率和链路节点 发射功率对周围节点通信产生干扰两方面的判别因子中的较小者。 说明选出某一条链路在节点发射功率和干扰两个方面特定较差的一 个判决因子，用于后续算法的执行）；然后求出所有收发链路中的最 大者所对应的组合方式(i^*,j^*)即可，如公式（25）和公式 （26）所示：

${\alpha }_{i,j}^{\min }=\min ({\alpha }_{i,j}^P,{\alpha }_{i,j}^I)\forall i,j---\left(25\right)$

$(i^{*},j^{*})=\arg \max \left({\alpha }_{i,j}^{\min }\right)---\left(26\right)$

于是，假设为选出的组合(i^*,j^*)分配1比特，由公式(23)和公式 (24)计算出当在选出的分配组合(i^*,j^*)中增加1比特时，发射功率增 加量和噪声功率增加量ΔI_i,j，并判断是否满足发射功率门限(P_th) 和噪声功率门限(I_th)的约束条件，若满足则在此组合中分配1比特， 继续执行下一次比特数分配与发射功率控制；否则不分配。

3.算法步骤

综上所述，基于混合蚁群算法的无线自组织网络功率可自适应 分配的路由方法的步骤如下所述，算法流程图如图3所示。

（1）初始化

第一步：K只前向蚂蚁从源节点出发初始化随机选择当前所在 节点的一个邻居中继节点作为其下一跳节点，在选择节点过程中前 向蚂蚁记录经过中继节点的ID号和路径信息。前向蚂蚁到达目的节 点后消失，从而建立K种初始化随机路由方案。

第二步：针对初始化随机路由方案，到达目的节点的前向蚂蚁 立即消失，后向蚂蚁产生并携带着对应的前向蚂蚁的信息以及前向 蚂蚁经过的所有中继节点的ID和路径信息。首先，后向蚂蚁使用贪 婪算法根据记录的路径信息进行链路传输速率和发射功率分配，即 按公式(22)和公式(23)计算每个分配方案中的每个链路每增加1比 特，所增加的发射功率和对周围节点产生的噪声干扰。然后，按公 式(24)、公式(25)和公式(26)找到最佳的(i^*,j^*)组合。并且判断是否 满足发射功率门限和干扰门限等约束条件，若满足，则分配链路速 率和功率；否则，不分配链路速率和功率。最后，待链路速率和发 射功率分配结束，后向蚂蚁沿着对应于前向蚂蚁的路径反向返回， 并根据记录的节点发射功率和链路传输速率对路径上各链路的信息 素进行更新。

(2)主循环

第三步：对于每一代中的第k只前向蚂蚁，首先，使用混合蚁群 算法进行路由建立，即按公式(8)和(9)选择下一跳中继节点，直到下 一跳为目的节点，获得一种路由方案；然后，前向蚂蚁到达目的节点 后立即消失，同时后向蚂蚁生成并携带着对应的前向蚂蚁的信息以 及前向蚂蚁经过的所有中继节点的ID和路径信息，按照贪婪算法对 路径上的每一条链路(i,j)进行比特数和发射功率分配；最后，后向蚂 蚁沿着对应于前向蚂蚁的路径反向返回，并根据记录的节点发射功 率和链路比特数对每个链路(i,j)上的信息素按照公式(13)进行局部 更新。

第四步：循环执行第三步，直到K只前向和后向蚂蚁对都全部 完成一次路由建立，即获得K种路由方案，然后执行第五步。

第五步：K只后向蚂蚁返回源节点后立即消失，决策蚂蚁产生 并记录K只后向蚂蚁记录的节点发射功率和链路速率以及路径信 息。首先，决策蚂蚁计算每一条路径上各链路总的传输速率并找出中的最大值R_max，并记录R_max对应的路由方案以及速率 和发射功率的分配方案；然后，决策蚂蚁将当前速率最大值R_max与 前一代全局速率最优解R_best比较，更新全局最优解。最后，决策蚂 蚁使用粒子群算法按照公式（18）计算所有路由方案对应的粒子群算 法适应度函数，并求出粒子的个体极值和全局极值；按照公式（19） 和公式（20）对粒子的速度及位置进行更新，即对应于蚁群算法中的 四个参数(α,β,ρ,γ)进行更新，以便下一代使用。

第六步：决策蚂蚁按记录的路径信息向目的节点运动，并按照 公式(13)进行信息素的全局更新，完成启发信息（公式10）的更新以 及其他参数的更新，以便下一代使用。到达目的节点后立即消失。

第七步：NC加1，进入下一代；跳转至第三步执行。

(3)结束

第八步：当NC>NC_max时，算法结束。

本发明通过贪婪算法对所述节点发射功率和链路速率进行分配 得到链路；通过发射功率门限和干扰门限条件对链路分配节点发射功 率和链路速率；根据链路分配节点发射功率和链路速率对所述路径信 息进行更新；根据节点发射功率、链路速率和路径信息计算每条路径 的总传输速率，得到最大的总传输速率对应的最优路由。本发明综合 考虑了网络节点剩余能量、有限的节点发射功率、节点间干扰及链 路传输速率，全面优化网络吞吐量及能量使用效率，使得该路由算 法更能适应多变的无线多跳中继网络环境，同时达到网络节能的目 的。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关 技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下， 还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明 的范畴，本发明的专利保护范围应由权利要求限定。