一种基于蚁群算法的水声多跳协作通信网络路由选择方法

摘要

一种基于蚁群算法的水声多跳协作通信网络路由选择方法，涉及水声网络。将协作通信引入水声多跳网络，形成水声多跳协作通信网络，根据水声通信能量消耗模型，提出适用于水声多跳协作通信网络的蚁群算法代价函数，用以优化路由选择；存在协作节点，使得每个中继节点的下一跳选择空间增大，提高路由选择的成功性；确保在既有中继节点又存在协作节点的情况下，能迅速有效地找到全局最优的路径；该最优路径可降低系统整体能量消耗，延长水声通信网络的生命周期。

说明书

技术领域

本发明涉及水声网络，尤其是涉及一种基于蚁群算法的水声多跳协作通信网络路由选择方法。

背景技术

随着陆地资源不断被开发，为缓解资源短缺问题，人们将探索的目光转移到蕴藏丰富、潜力巨大的海洋资源上。近年来，由于军事和民用领域对水声通信的应用需求逐步增加，水声通信及其网络技术的研究获得人们的青睐。

由于水声信道可利用带宽窄、水声信号传输衰减严重、水下节点能量供给受限等因素，研究表明，与直接进行远距离传输相比，通过短距离多跳实现远距离传输，可降低水声通信网络系统整体的能量消耗。借鉴陆上无线电信号处理技术，Cecilia等(Carbonelli C,Mitra U.Cooperative Multihop Communication for Underwater Acoustic Networks[C].in the Proceedings of the 1st ACM International Workshop on Underwater Networks,2006:97-100.)将协作通信技术引入水声通信网络，通过协作获得分集效益，进一步提高了水声多跳通信网络的性能。

水下传感器节点的发射功率、传输距离、处理数据所用的功率都受到严格的限制，并且对于水声多跳协作通信网络路由选择，其水下网络拓扑结构是动态变化的多跳协作网络，在源节点S和目的节点D之间的每一个节点都既可能成为中继节点R为其转发信息，也可能成为协作节点C在需要时参与协作转发。多跳水声协作通信网络中，每一跳的节点选取，在既有中继节点又存在协作节点的情况下，如何迅速合理地选择出最优路径，即在考虑协作节点C存在的情况下找出最优的中继节点R，是当前研究的重点也是难点。

针对水声多跳通信网络，鉴于蚁群算法的优点，陶强等(陶强,黄友锐,凌六一,等.基于改进蚁群算法的水下传感器网络路由策略[J].微电子学与计算机,2015,05:59-62.)将改进蚁群算法用于水下传感器网络的路由选择优化，以解决能量消耗和多径效应的问题；万智萍(万智萍.带选择适应性的水下传感器网络分布式路由算法[J].计算机应用研究,2014,12:3770-3772.)提出一种带选择适应性的水下传感器网络分布式路由算法，能以实时性、灵活性更好地搜索出最优的节点转发路径。但是，上述方法均是在不存在协作节点的情况下，进行水声多跳通信网络的蚁群算法设计的。

发明内容

本发明的目的在于提供可提高水声协作通信效率的一种基于蚁群算法的水声多跳协作通信网络路由选择方法。

本发明包括以下步骤：

1)选定源节点S和目的节点D；

2)计算各节点间的距离d_i,j及节点间的最优工作频率f_opt；

3)初始化参数；

在步骤3)中，所述初始化参数的具体方法可为：设定每轮搜索的蚂蚁数目为M只，搜索次数为N轮，两节点间可直接传输成功的距离阈值为d_hop，两节点间需要协作传输的距离阈值为d_cop，即当d_i,j<d_hop时节点间可直接正确传输，当d_hop<d_i,j<d_cop时两节点间需要协作节点协助才能成功传输，且d_hop<d_cop；初始化各节点间信息素浓度，启发信息为两节点间距离的倒数；设置初始化当前搜索轮数n＝0，初始化当前蚂蚁编号m＝0；

4)n＝n+1，将M只蚂蚁置于源节点，初始化各蚂蚁的禁忌表Tau；

5)m＝m+1；

6)当前蚂蚁位于节点i，计算蚂蚁转移到下一个节点j的概率，节点j从当前第m只蚂蚁的禁忌表Tau_m之外的节点中取得，若节点i和节点j之间的距离d_i,j<d_hop或者d_hop<d_i,j<d_cop，且节点i和节点j之间存在协作节点C；

7)蚂蚁m按照转盘策略转移至所选择的节点j，并根据节点间的距离d_i,j及节点间的最优工作频率f_opt计算出该跳的能量消耗代价函数L_m,(i,j)，同时将节点j加入禁忌表，重复步骤6)，直至蚂蚁m到达目的节点D，终止此蚂蚁的循环，并计算该路径的总能量消耗代价函数L_m，转到步骤8)；

在步骤7)中，所述蚂蚁m按照转盘策略转移至所选择的节点j，并根据节点间的距离d_i,j及节点间的最优工作频率f_opt，定义能量消耗为发送功率与接收功率的比值(陶强,黄友锐,凌六一,等.基于改进蚁群算法的水下传感器网络路由策略[J].微电子学与计算机,2015,05:59-62.)，此比值为采用最优工作频率f_opt时发送功率对于距离d_i,j的衰减，则按照水声通信能量消耗模型(刘广钟，刘晓晖.基于节能的定向扩散水声传感器网络路由算法[J].计算机系统应用，2011,20(12):95-98.)计算出两节点的能量消耗U，以通信网络整体的能量消耗为代价函数寻找最优路径，计算出该跳的能量消耗代价函数L_m,(i,j)，同时将节点j加入禁忌表Tau_m；从节点i到节点j，若存在协作传输，则节点采取半功率发送，计算出各种可能的协作方案的能量消耗L_m,(i,j),Ck，找出能量消耗最小的那个方案，确定最优协作节点C_k。重复步骤6)，直至蚂蚁m到达目的节点D，终止此蚂蚁的循环，并计算该路径的总能量消耗代价函数L_m，转到步骤8)；适用于水声多跳协作通信网络的蚁群算法代价函数如下：

$L_{m,(i,j)}=\frac{U\left(d_{i,j}\right)+\lambda U\left(d_{c_k,j}\right)}{1+\lambda }$

L_m＝∑L_m,(i,j)，

其中L_m,(i,j)为蚂蚁m经过路径(i,j)的能量消耗代价函数，总能量消耗代价函数L_m等于每段路径的能量消耗代价函数相加，d_ck,j为协作节点C_k与下一节点j间的距离,当节点i和节点j之间需要协作节点时，λ＝1，否则λ＝0。

8)信息素局部更新；

在步骤8)中，所述信息素局部更新的具体方法可为：更新蚂蚁m经过的各路径上的信息素浓度，若m>M，转步骤9)，否则转步骤到5)，采用如下规则更新信息素：

${\tau }_{ij}=(1-\rho ){\tau }_{ij}+{\mathrm{\Delta \tau }}_{ij}^m$

其中，Z表示一常数，其值越大，表示局部信息素增加的就越快，ρ是挥发因子，表示路径上的原有信息素会逐渐消散，避免了信息素不断累积，覆盖随机启发信息的情况出现，因此1-ρ是信息素残留因子。

9)信息素全局更新：找出本轮搜索中能量消耗最低(即M只蚂蚁中L_m最小)的路径，更新本轮搜索最优路径上的信息素浓度，转到步骤4)，直到n>N，输出N轮搜索中能量消耗最低的路径，即全局最优解，结束程序。

本发明将协作通信引入水声多跳网络，形成水声多跳协作通信网络，根据水声通信能量消耗模型，提出适用于水声多跳协作通信网络的蚁群算法代价函数，用以优化路由选择；存在协作节点，使得每个中继节点的下一跳选择空间增大，提高路由选择的成功性；确保在既有中继节点又存在协作节点的情况下，能迅速有效地找到全局最优的路径；该最优路径可降低系统整体能量消耗，延长水声通信网络的生命周期。本发明利用蚁群算法随机性和正反馈等寻找全局最优解的优越性，基于水声通信能量消耗模型，结合协作通信技术，将节点的能量消耗作为代价函数寻找全局最优路径，使信息传输的能量消耗降到最低。

本发明具有以下突出优点：

1)将协作通信引入水声多跳网络，形成新的水声多跳协作通信网络，该网络同时存在中继节点和协作节点，使得每个中继节点的下一跳选择空间增大，提高路由选择的成功性，在多变的海洋信道环境下，具有更强的适应能力；

2)根据水声通信能量消耗模型，提出适用于水声多跳协作通信网络的蚁群算法代价函数，用以优化路由选择，利用蚁群算法随机性和正反馈等寻找全局最优解的优越性，可以让蚁群迅速寻找到水声多跳协作通信网络中能量消耗最小的路由路径，延长水声通信网络的生命周期。

附图说明

图1为水下传感器节点网络拓扑图。(图中网络节点序号分别为1～18，其中S为源节点，D为目的节点)

图2为水声协作网络中节点覆盖区域模型图。

图3为水声协作网络中协作节点选择示意图。

图4为路径走向概率轮盘分布。

图5为轮盘选择路径落点分布。

图6为基于蚁群算法的水声多跳协作通信网络的最优路径图。(图中网络节点序号分别为1～18，其中S为源节点，D为目的节点，C为协作节点)

图7为基于蚁群算法的水声多跳协作通信网络的代价函数(能量消耗)随搜索次数变化图。

图8为基于蚁群算法的水声多跳通信网络的最优路径图。(图中网络节点序号分别为1～18，其中S为源节点，D为目的节点)

图9为基于蚁群算法的水声多跳通信网络的代价函数值(能量消耗)随搜索次数变化图。

具体实施方式

下面结合附图和具体实施例对本发明做详细描述。

本发明依据水声通信能量消耗模型，结合协作通信技术，在水声多跳协作通信网络中能迅速找到能量消耗最小的路径，包括以下步骤：

1)考虑一个中小型的网络拓扑，如图1，选定节点1为源节点S，节点18为目的节点D；

2)计算各节点间的距离d_i,j及节点间的最优工作频率f_opt；

3)初始化参数：设定每轮搜索的蚂蚁数目为M只，搜索次数为N轮，两节点间可直接传输成功的距离阈值为d_hop，两节点间需要协作传输的距离阈值为d_cop，即当d_i,j<d_hop时节点间可直接正确传输，当d_hop<d_i,j<d_cop时两节点间需要协作节点协助才能成功传输，且d_hop<d_cop；初始化各节点间信息素浓度，启发信息为两节点间距离的倒数；n＝0(初始化当前搜索轮数)，m＝0(初始化当前蚂蚁编号)；

4)n＝n+1，将M只蚂蚁置于源节点，初始化各蚂蚁的禁忌表Tau；

5)m＝m+1；

6)当前蚂蚁位于节点i，计算蚂蚁转移到下一个节点j(节点j从当前第m只蚂蚁的禁忌表Tau_m之外的节点中取得)的概率，若节点i和节点j之间的距离d_i,j<d_hop或者d_hop<d_i,j<d_cop，且节点i和节点j之间存在协作节点C时，则转移概率P根据下式确定，否则P＝0：

$P_{i,j}^m=\left(\begin{array}{cc}\frac{{\tau }_{ij}^{\alpha }{\eta }_{ij}^{\beta }}{{\Sigma }_{s\notin {\mathrm{Tau}}_m}{\tau }_{is}^{\alpha }{\eta }_{is}^{\beta }}& j\notin {\mathrm{Tau}}_m\\ 0& j\in {\mathrm{Tau}}_m\end{array}\right)$

其中，表示第m只蚂蚁由节点i转移到节点j的概率，τ_ij为路径(i,j)上的信息素浓度，τ_ij越大，表示这条路径越优。η_ij为选择路径(i,j)的启发信息，α，β分别表征信息素浓度和启发信息所占的比重。Tau_m是蚂蚁m的禁忌表，蚂蚁m每经过一个节点，就将该节点添加到禁忌表中。即Tau_m中都是蚂蚁m已经经过的节点，在选择下一个节点时，要将已经走过的节点排除在外；

7)蚂蚁m按照转盘策略转移至所选择的节点j，并根据节点间的距离d_i,j及节点间的最优工作频率f_opt，定义能量消耗为发送功率与接收功率的比值，此比值为采用最优工作频率f_opt时发送功率对于距离d_i,j的衰减，按照水声通信能量消耗模型计算出两节点的能量消耗U，以通信网络整体的能量消耗为代价函数寻找最优路径，计算出该跳的能量消耗代价函数L_m,(i,j)，同时将节点j加入禁忌表Tau_m；从节点i到节点j，若存在协作传输，则节点采取半功率发送，计算出各种可能的协作方案的能量消耗L_m,(i,j),Ck，找出能量消耗最小的那个方案，确定最优协作节点C_k。重复步骤6)，直至蚂蚁m到达目的节点D，终止此蚂蚁的循环，并计算该路径的总能量消耗代价函数L_m，转到步骤8)；适用于水声多跳协作通信网络的蚁群算法代价函数如下：

$L_{m,(i,j)}=\frac{U\left(d_{i,j}\right)+\lambda U\left(d_{c_k,j}\right)}{1+\lambda }$

L_m＝∑L_m,(i,j)，

其中L_m,(i,j)为蚂蚁m经过路径(i,j)的能量消耗，总的能量消耗L_m等于每段路径的能量消耗相加，d_ck,j为协作节点C_k与下一节点j间的距离,当节点i和节点j之间需要协作节点时，λ＝1，否则λ＝0；

此处需说明的是，当距离d_i,j<d_hop时，节点j能接收并成功解码来自上一节点i的信息，此时不需要协作节点C的帮助，即式中的λ＝0；当d_hop<d_i,j<d_cop时，节点j无法准确解码出来自上一节点i的信息，此时需要协作节点C的协助，利用来自协作节点C和上一节点i的信息进行解码，即式中的λ＝1；而当d_i,j>d_cop时，由于两点间距离太远，即使存在协作节点C的协助，节点j也无法成功解码出节点i传送的信息。因此，如图2所示，中继节点j的选择必须在半径d_cop的范围内，同时C的选择需位于两个节点i、j之间，才能有效地承担协作任务，参与协作解码。如图3所示，在两个节点之间可能存在多个可协作节点C_k，源节点S和目的节点D周围存在多个节点(节点1、节点2、节点3、节点4和节点5)，但只有节点1、节点2和节点3是可能作为协作节点C的，因为节点4和节点5距源节点S或目的节点D均太远，无法有效承担协作传输任务。通过比较各节点分别作为协作节点时，信息传输的能量消耗大小，能量消耗最小的节点作为S-D间的最优协作节点C_k。

8)信息素局部更新：更新蚂蚁m经过的各路径上的信息素浓度，若m>M，转步骤9)，否则转步骤到5)，采用如下规则更新信息素：

${\tau }_{ij}=(1-\rho ){\tau }_{ij}+{\mathrm{\Delta \tau }}_{ij}^m$

其中，Z表示一常数，其值越大，表示局部信息素增加的就越快，ρ是挥发因子，表示路径上的原有的信息素会逐渐消散，避免了信息素不断累积，覆盖随机启发信息的情况出现，因此1-ρ是信息素残留因子。

9)信息素全局更新：找出本轮搜索中能量消耗最低(即M只蚂蚁中L_m最小)的路径，更新本轮搜索最优路径上的信息素浓度。转到步骤4)，直到n>N，输出N轮搜索中能量消耗最低的路径，即全局最优解，结束程序，采用如下规则更新全局信息素：

${\tau }_{ij}=(1-\rho ){\tau }_{ij}+{\mathrm{\Delta \tau }}_{ij}^{best}$

其中，Q为一常数，其值越大，表示全局更新时最优路径上的信息素浓度增加的就越快。

针对本发明所述方法，为解决蚁群算法陷入局部最优的问题，尽可能地提高该算法的全局寻优、收敛能力，引入路径随机性形成带有正反馈的随机搜索算法(姜文波.蚁群算法局部最优解决机制的探讨[J].智能计算机与应用,2014,03:53-54.)。随机性采用转盘策略，利用转盘选择来决定蚂蚁下一个转移的节点。具体方法如下：

在[0，1]之间取一个随机数r，用r减转移概率P₁，若减去后的结果小于或等于0就选择该节点作为下一个转移点，若减去后仍然大于0，就继续再减去P₂，如此反复直到减去后的结果小于或等于0，此时即用最后减去时的那个概率值对应的点作为下一个转移点。如图4所示，假设[0，1]之间取得的随机数是0.91，转盘的箭头就顺时针旋转0.91圈，箭头落入G所在的区域里，因此蚂蚁就选择G作为下一个转移点。由图5可见，在[0，1]之间取一个随机数，这个数字落在F区域内的可能性最大，E次之，G最小。因此蚂蚁向概率值大的点前进的可能性也更大，但也存在向概率小的点转移的可能，这样就可使蚂蚁有机会探索新的路径，从而避免算法停滞或陷入局部最优解。利用转盘策略，使蚁群算法成为带有正反馈的随机搜索算法。正反馈加快收敛速度，随机性避免局部最优。

下面对本发明所述方法的可行性进行计算机仿真验证。

随机布置了水下传感器节点网络拓扑模型，总共18个节点，源节点S和目的节点D如图1所示。各参数设置如下：N＝30，Q＝1000，Z＝500，α＝2，β＝1，ρ＝0.3，蚂蚁规模：M＝4，初始化各路径上的信息素浓度τⁱ_j＝1。假设水声通信在浅海区域进行，则设定k＝1.5，柱面波方式传播。同时设定距离阈值d_cop＝4km、d_hop＝2.5km，即下一节点距离满足在半径4km范围内的才有可能成功传输，距离小于4km但超过2.5km的需要协作节点C协作才能成功传输，距离小于2.5km的无需协作节点C即可成功传输。

以下是对于本发明所述方法仿真结果的分析：

1)有协作策略分析：

图6为本实施例中基于蚁群算法的水声多跳协作通信网络的最优路由选择结果，仿真运行时间为32.774810s，其最优路径为：

S→5→10→13→D，4跳完成。

其中节点4为从源节点S到节点5的最优协作节点，节点9为从节点5到节点10的最优协作节点，节点12为从节点10到节点13的最优协作节点，节点16为从节点13到目的节点D的最优协作节点。由图6可见，从源节点S到节点5之间可作为协作节点的有节点2、节点3、节点4三个，算法通过计算三种方案各自的能量消耗代价函数L_Ck可知，选择节点4做协作节点时的能量消耗低于选择节点2或者节点3的能量消耗，因此选择节点4作为最优协作节点。同理，在其他协作传输的过程中选出相应的最优协作节点。图7为本实施例中基于蚁群算法的水声多跳协作通信网络的最优路由选择的代价函数值，即能量消耗随搜索次数增加而变化的曲线图。由图7可见，开始搜索时，曲线的抖动较大，这是由于转盘策略的加入使得搜索的随机性加强，有利于算法跳出局部最优解，找出全局最优路径。随着搜索次数的增加，代价函数值虽然波动仍较大，但有一个减小的总趋势，说明算法在向全局最优解逼近。在第16次时，算法收敛到全局最优解，之后不再变化。此时的代价函数值(能量消耗)为最低值：Lm＝3145108.143607385。

2)无协作策略分析：

图8为本实施例中，当不考虑协作传输策略时，基于蚁群算法的水声多跳通信网络的最优路由选择结果，仿真运行时间为17.542168秒，其最优路径为：

S→3→5→7→9→10→12→13→14→16→D，10跳完成。

由于没有协作节点的帮助，节点之间的可传输距离减小，因此将信息从S传输到D需要经历更多的跳数，当采取协作策略时仅需要4跳就能完成的传输任务，无协作策略需要10跳才能完成。由此可见，采取协作传输策略可以减少传输所需的跳数，进而降低系统整体的能量消耗。

由图9可见，当无协作策略时，代价函数值(能量消耗)整体高于有协作策略时的能量消耗，最终收敛达到的最小值Lm＝5657436.463287456，为有协作策略时能量消耗的1.87倍左右。因此，可以发现，同样是基于蚁群算法，水声多跳协作通信网络路由选择算法要优于无协作策略算法。

从MATLAB仿真运行时间可以看出，有协作策略时收敛速度略低于无协作策略算法的收敛速度(但收敛速度都较快，均在35s以内)，主要的原因有二：一是采取协作策略，每个节点下一跳的选择空间增大，解空间增大导致搜索最优解的时间延长；二是采取协作策略，除了需要找出中继节点R外，还需同时找出最优协作节点C，导致运行时间加长。

综上，从两种方案最终寻找到的最优路径来看，有协作策略收敛的代价函数(能量消耗)最小值远低于无协作策略收敛的代价函数(能量消耗)。可见，基于蚁群算法的水声多跳协作通信网络路由选择算法，扩大了每一跳选择的空间，提高了路由选择的成功性；同时，验证了结合水声通信能量消耗模型提出的水声多跳协作通信网络的代价函数，可以寻找到能量消耗最小的路径，且优于无协作策略算法。