一种战术MANET中QoS路由算法BLQRA

杨绪彬，张文强，郑　翔，张　妍

(1.解放军理工大学 通信工程学院，江苏 南京 210007；2.中国电子科技集团公司第二十八研究所，江苏 南京 210007)



一种战术MANET中QoS路由算法BLQRA

杨绪彬1，张文强1，郑翔1，张妍2

(1.解放军理工大学 通信工程学院，江苏 南京 210007；2.中国电子科技集团公司第二十八研究所，江苏 南京 210007)

针对战术移动自组织网络(MANET)中不同优先级业务服务质量(QoS)保障问题，提出了一种基于节点可用带宽接入门限及负载均衡的QoS路由算法(BLQRA)。利用蚁群优化的思想通过设计改进的蚁群算法搜索出满足各QoS约束且耗费最小的路径。仿真结果表明，在网络参数动态变化的情况下，算法实现了源节点到目的节点满足各QoS约束条件路径的有效寻找，并且与传统的ACRA算法相比，BLQRA算法最终收敛到了耗费更小的路径上。

战术移动自组织网络；负载均衡；QoS路由算法；蚁群优化

0　引　言

移动自组织网络(Mobile Ad Hoc Network, MANET)是由一组带有无线通信收发装置的移动终端节点组成的一种多跳的临时性无中心网络[1]，不同于蜂窝移动网络，MANET无需任何的固定的基础设施来支持路由和移动性管理。由于其易组建、自组织等特性，MANET在军用战术无线通信领域展现出了巨大的应用价值。目前，战术MANET已成为传递军事控制指令，战场感知数据及多媒体业务的基础平台。

QoS路由是为战术MANET中多媒体业务提供服务质量保障的一项关键技术。在QoS路由优化问题中，当同时对两个以上相互独立的参数提出要求时，这个问题就是一个NP完全问题[2]。其中蚁群优化[3](Ant Colony Optimization，ACO)作为一种启发式优化算法由于能够有效地解决NP完全问题而被应用于多约束QoS路由算法的设计。目前，研究学者已经提出了很多适用于MANET中基于蚁群的QoS路由算法，如ACRA[4]、ARAMA[5]、AntHocNet[6]、MC-AQARA[7]等。然而这些路由算法都没有考虑到业务等级问题。对于一个特定的战术通信网络，只有保障好重要用户的通信(例如首长的通信)才能发挥出最大的作战效能。 同时，为提高网络的整体资源利用率，防止网络因为个别节点负载过大而瘫痪，网络中各个节点的负载均衡也是战术MANET中QoS路由算法需要考虑的一个重点。基于此，本文对战术MANET中的业务等级进行了分类并提出了一种基于节点带宽接入门限及负载均衡的QoS路由算法BLQRA，该算法考虑了不同优先级业务的多种QoS约束条件，并利用改进的蚁群算法来寻找源节点与目的节点之间的最佳路径。

1　节点可用带宽接入门限设置

1.1业务等级分类

战术MANET中，从单兵到各级指挥员用户种类众多且等级不同。在战场环境下，当任务的重要程度、紧急状况不同时，用户发送业务的重要程度同样会有所差异。为此，本文根据用户的重要程度及业务的重要程度将业务等级(Service Level, SL)分为三类，如表1所示。

表1　业务等级分类

以S表示业务，则各等级业务优先级如下：

SSL=1>SSL=2>SSL=3

(1)

对应业务优先级：

321

其中3对应业务优先级最高，1对应的业务优先级最低。业务等级可以在IP报文的区分服务(DS)域中进行定义。

1.2节点可用带宽接入门限设置

为了保障高优先级业务的QoS，如图1所示，本文通过在节点中设置各类优先级业务的可用带宽接入门限值为高优先级业务预留带宽，从而保证高优先级业务的路由建立成功率。

图1　节点可用带宽接入门限设置

其中W1≤W2≤W3=Wt。Wt为节点在空闲时的总有效带宽，Wi为优先级为i的业务对应的节点可用带宽接入门限值，其中i=1,2,3。该门限值规定了各优先级业务可消耗节点带宽的上限。只有当路径上各节点满足对应优先级节点可用带宽接入门限时，路径才可以建立并分配带宽资源。其中，W1，W2值的设定可以根据网络中各优先级业务实时业务阻塞率进行动态调整，以在各优先级业务QoS保证与网络带宽资源利用率间达到一个最佳平衡。

2　优化目标建模

2.1路径QoS参数定义

(2)

(3)

(4)

(5)

(6)

式中，D、DJ、C为加性度量参数，D(n)为在节点n上的时延，对应于分组在节点处的处理时延、排队时延及传输时延之和，D(e)为在链路e上的时延，对应于分组在链路上的传播时延；B和G为凹性度量参数，参照文献[8-10]，以节点的可用带宽近似反映当前的网络状况，将链路的可用带宽定义为该链路收发节点可用带宽的最小值，则整个路径的带宽为路径上各节点可用带宽的瓶颈值。整个路径的拥塞为路径上节点的最大拥塞，其中节点n处的拥塞定义为n的当前等待队列长度Qt与总的数据缓存队列长度Qtotal的比值，即：

G(n)=Qt/Qtotal

(7)

2.2算法目标

对于优先级为i的业务，本文提出算法的目标是搜索出拥有最小耗费且满足时延、时延抖动、拥塞限制以及节点接入带宽门限等QoS约束的路径，即：

(8)

式中，Dq、DJq分别为业务的时延和时延抖动约束，Gth为预先设好的拥塞阈值，Bq为业务的最小请求带宽，B′(n)为节点n上的已用带宽，B′(n)+Bq≤Wi(n)，n∈P(s,d)描述了路径上节点的接入带宽门限限制。

对于战术MANET，用户往往会忽略节点或者链路的实际费用，而更关心如何去平衡网络中各节点的负载，使得整个战术MANET的使用效率最大化。为此，在本文提出的算法中，将路径的耗费定义为路径各节点上拥塞的和值，而各链路的耗费为0，即：

(9)

最小化路径的耗费可以寻找到一条整体负载较轻的路径，而路径上拥塞阈值的限制可以使得所选择的路径避免网络中个别负载较大的节点。

3　BLQRA算法

3.1基本的蚁群算法

蚁群优化算法的基本思想是借鉴自然界蚂蚁群体的觅食行为。当蚂蚁离开巢穴寻找食物时会在所经过的路径上释放一定的信息素，信息素的强度表征着路径的远近，信息素强度越高，表示对应的路径距离越短，并且释放的信息素会随着时间挥发。后来的蚂蚁会根据信息素的强度来选择路径，路径上的信息素强度越大的路径被选择的概率也越大，由此形成了一个正反馈，最终，蚂蚁会集中到一条信息素浓度最大的最短路径。

蚁群优化算法具有的正反馈、分布式计算、启发性搜索等特点与网络优化的要求十分匹配，因此，蚂蚁的这种行为被可以被用到在MANET寻找满足多种约束条件的路径。如ACRA就是参照了最基本的蚁群算法中的蚁周模型在源节点与目的节点之间寻找一条最短路径。

3.2BLQRA算法规则

BLQRA算法在基本蚁群算法的基础上，对信息素的更新方式及状态转移规则进行了改进，并根据业务QoS要求对邻居节点的范围加以限制，减少了算法的开销，并使得算法能够快速收敛，在业务QoS约束下找到一条耗费最小的路径。

3.2.1状态转移规则

每只蚂蚁根据状态转移规则选择下一跳，在t时刻，第k只蚂蚁从节点i选择到邻居节点j的概率通过式(10)、(11)定义，其中邻居节点的范围限制在通信范围内能够满足拥塞阈值约束及节点带宽接入门限限制的下一跳节点。

(10)

(11)

式中，q为一个在[0,1]范围内服从均匀分布的随机数，q0∈(0,1)，为一个常数变异算子，它决定了先验知识与探索的相对重要性，并能防止算法陷入局部最优解。τi,j(t)为t时刻节点i与节点j之间的信息素浓度，ηi,j(t)为耗费启发函数，ηi,j(t)=1/C(i,j)，C(i,j)为节点i与节点j之间的耗费，根据前对对路径耗费的描述，C(i,j)定义为C(i,j)=G(j)。α(α≥0)为信息素重要程度因子，β(β≥0)为启发函数重要程度因子，α和β控制着路径上信息素浓度与本地耗费的相对重要性。

3.2.2本地更新规则

在路径建立过程中，蚂蚁所经过链路上的信息素浓度τi,j(t)会立即进行更新，其中信息素浓度本地更新规则定义为：

τi,j(t+1)=(1-ξ)τi,j(t)+ξτ0

(12)

式中，ξ为本地信息素挥发因子，0<ξ<1。τ0为各路径上设置的信息素浓度初值，τ0通过式(13)设定:

τ0=1/N·CNN

(13)

式中，N为网络中的节点数目，CNN为通过最近邻算法得到的路径耗费。从上式可以看出，信息素初值τ0是一个很小的值，本地更新规则使得蚂蚁每次经过的链路上信息素浓度有所减少，以此降低了后续蚂蚁选择该链路的概率，增加了蚂蚁对未利用链路开发的机会，防止算法陷入停滞状态。

3.2.3全局更新规则

当所有蚂蚁完成一次迭代后，进行全局信息素更新。BLRAQ算法中，在每次迭代后只有迄今最优路径允许更新信息素。首先，我们定义一个目标函数Lk：

(14)

其中

(15)

(16)

在式(14)中，λ1和λ2分别为fd和fdj的正向权重，表征着在目标函数中时延和时延抖动的相对重要性。fd和fdj分别为时延和时延抖动参数的罚函数，如果第k只蚂蚁所在源到目的路径满足相应的时延约束和时延抖动约束，则相应的罚函数值为1，否则为设定的惩罚值。通过比较计算每次迭代后各蚂蚁所在路径的目标函数值，定义使得到目前为止Lk最大的路径为迄今最优路径，对应的蚂蚁为迄今最优蚂蚁，相应的目标函数值为Lbest。每完成一次迭代后，迄今最优路径按式(17)所述的全局更新规则更新信息素：

(17)

式中,ρ为全局信息素挥发因子，0<ρ<1。Q为常数，为迄今最优路径释放信息素的增益因子。通过全局更新规则，可以使得蚂蚁最终集中在一条满足业务QoS约束并使得路径耗费最小的路径上。

3.3BLQRA算法流程

给定业务等级和节点带宽接入门限限制及拥塞、时延、时延抖动等QoS约束，BLQRA算法按照如下步骤进行：

(1)通过去掉不满足节点接入带宽门限及拥塞阈值的链路简化网络拓扑；

(2)初始化算法迭代次数、蚂蚁数目，蚁群算法中的各个参数以及各链路上的信息素浓度τ0；

(3)每只蚂蚁按照状态转移规则选择下一跳；

(4)每次蚂蚁经过链路上的信息素浓度按照信息素本地更新规则进行更新；

(5)当蚂蚁到达目的节点后，计算所经过路径的目标函数值，每次迭代后，选出迄今最优路径并按照信息素全局更新规则进行更新；

(6)判断是否达到最大迭代次数，如果没有则迭代次数加1并进行新一轮的选路，直到达到最大迭代次数。

4　仿真设置与结果分析

本文采用MATLAB仿真平台对BLQRA算法进行仿真分析。

4.1网络拓扑构建

战术MANET拓扑结构动态变化，但在每一次执行路由算法的短时间内可认为网络拓扑及网络中的各QoS参数是固定不变的。本文采用改进的Salama博士的网络拓扑随机生成算法[11]对战术MANET进行拓扑构建及QoS参数设置。其中网络拓扑限定在100 km×100 km的范围内，节点数目为25。随机产生的网络拓扑如图2所示。

图2　网络拓扑模型

图2中，在通信范围内的各节点具有连接关系，链路上的时延、时延抖动以及节点处的时延、时延抖动、可用带宽、拥塞等QoS参数通过相应的QoS矩阵储存。其中在节点处显示的参数(x，y)中，x表示该节点当前的可用带宽，y表示该节点当前的拥塞值。

4.2参数设置及优化

在仿真中，我们固定3号节点为源节点，25号节点为目的节点，网络中所有节点的三类优先级业务接入带宽门限值设置相同，为W1=14 Mb/s、W2=17 Mb/s、W3=20 Mb/s(各节点总带宽。其他参数设置为：Gth=0.8、Bq=1 Mb/s、Dq=20 ms，DJq=5 ms，q0=0.5，ξ=0.2，λ1=λ2=1，rd=rdj=0.5，Q=10。

本文提出BLQRA算法中，α及β参数的设置对算法十分重要。如果α过大，算法容易停滞过早收敛；如果α远小于1，则算法收敛速度慢，且较难寻找到最优解。同理，如果β设置过大，蚂蚁会较容易选择到局部耗费最优的路径，算法易陷入局部最优解。图3和图4分别描述了α和β对算法路径耗费的影响。

图3　α对路径耗费的影响

图4　β对路径耗费的影响

在图3和图4中，业务等级SL为2，迭代次数为100，平均耗费是指在第100次迭代时所有达到目的节点蚂蚁路径耗费的平均值，最小耗费是指在所有100次迭代中达到目的节点蚂蚁的最小耗费，每组结果取100次仿真的平均值。最小耗费的值反映了算法搜索最优解的能力，最小耗费越小，算法搜索最优解的能力越强，平均耗费与最小耗费的差值反映了算法的收敛性，差值越大，表明算法越不收敛，差值越小，表明算法收敛性越强。从仿真结果可以看出，α和β设置的过大或者过小，算法都达不到最优的性能，容易陷入到局部最优解，尤其是当β值较大时，算法很难收敛且容易选择到局部最优的路径。当α=β=1时，平均最小耗费最小，且收敛性较强，算法的性能达到最佳。因此，在接下来的仿真中，我们将α和β设置都设置为1。

4.3算法有效性

图5、图6分别为业务等级为2和3时，BLQRA算法选择出的一条满足各QoS约束条件且路径耗费最短的源节点到目的节点的路径。

图5　SL=2时路径选择结果

图6　SL=3时路径选择结果

通过比较图5和图6的路径选择结果可以发现，在相同的网络参数及QoS需求下，当业务等级不同时，路径选择结果可能会不一样，由于节点对各优先级业务接入带宽门限设置的不同，业务等级为2路径上9号节点的可用带宽不能满足业务等级为3时的接入条件，因此业务等级为3的业务选择了另一条路径上各节点可用带宽都较大的路径，以此使当前可用带宽较低的节点能够为高优先级业务预留一定的带宽，保证了在高优先级业务在网络整体可用带宽较低时路由建立的成功率。此外，从路径选择的结果中可以看出，BLQRA算法避开了网络中拥塞较重的节点，选择的路径整体负载较轻。

为验证BLQRA算法在网络参数动态变化时选择路径的正确性，我们通过先后改变业务等级为2的耗费最短路径上9号节点与12节点QoS参数后得到路径选择结果如图7、图8所示。

图7　改变9号节点参数后SL=2时的路径选择结果

图8　改变12号节点参数后SL=2时的路径选择结果

图7为将9号节点拥塞值从0.3增大为0.7后业务等级为2时的路径选择结果，从仿真结果可以看出BLQRA算法避开了拥塞的9号节点，选择了另一条整体负载较轻的路径，且该路径能满足其他QoS约束，验证了算法的负载均衡性。

图8为将12号节点可用带宽从7.5 Mb/s减少为3.5 Mb/s后业务等级为2时的路径选择结果，从仿真结果中可以看出BLQRA算法绕开了不满足节点接入带宽门限的12号节点，预留了该节点的带宽，从而保证了高优先级业务的路由建立成功率，使得高优先级业务能够得到更好的QoS保障。

4.4算法先进性

图9是BLQRA算法与传统的ACRA算法的对比，其中在BLQRA算法中业务等级为2，ACRA算法的结果是采用原有算法的思想，将耗费定义为节点拥塞得出的。相对于ACRA，BLQRA算法收敛速度相对较慢，但最终能够获得更佳的路径。从仿真结果中可以看出，BLQRA算法在迭代次数大于100次后已基本收敛，平均耗费与最小耗费差值较ACRA大是由于BLQRA算法采用的局部信息素更新规则使得蚂蚁每次走过的路径上信息素浓度都有所减少，因此即使在蚂蚁搜寻到最优路径后后续蚂蚁的搜索仍具有一定的随机性，以此保证了BLQRA算法搜索到全局最优解的能力。

图9　与传统ACRA算法对比

5　结　语

与民用Ad Hoc网络不同，战术移动互联网络具有特殊的军事背景，网络中的用户具有等级差异性，业务的重要程度也会随着战场环境而改变。为了提高网络的使用效率，并使高优先级业务得到更好的服务质量保障，本文针对战术MANET提出了一种基于带宽接入门限及负载均衡的QoS算法BLQRA。该算法对不同优先级业务设置了不同的节点接入带宽门限，从而为高优先级业务预留了带宽。此外，在算法中，路径的耗费定义为路径各节点拥塞的和值，因此算法能够找到一条整体负载较轻的路径。仿真结果验证了算法的有效性和先进性。

[1]韩彬斌, 王培康, 张晓辉.自组网内的延迟限制QoS路由算法研究[J].通信技术, 2002 (02): 53-55.

HAN B B,WANG P K, ZHANG X H. Research on Delay Constrained Quality-of-Service Routing in Ad Hoc Networks[J].Commutations Technology,2002(02):53-55.

[2]CHEN S, Nahrstedt K. On Finding Multi-Constrained Paths[C]//ICC 98：Proceedings of the 1998 IEEE International Conference on Communications. Piscataway: IEEE, 1998, 2: 874-879.

[3]Dorigo M, Birattari M, Stulzle T. Ant Colony Optimization[J]. Computational Intelligence Magazine,IEEE,2006,1(4):28-39.

[4]Dirigo M, Di Caro G, Sampels M. Ant Algorithms: Third International Workshop, ANTS 2002, Brussels, Belgium, September 12-14, 2002. Proceedings[M]. Springer Science & Business Media,2003.

[5]Hussein O, Saadawi T. Ant Routing Algorithm for Mobile Ad-Hoc Networks (ARAMA)[C]// Proceedings of 2003 IEEE International Conference on Performance, Computing, and Communications.Piscataway: IEEE, 2003:281-290.

[6]Di Caro G, Ducatelle F, Gambardella L M, et al. Ant HocNet: An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks[J]. European Transactions on Telecommunications,2005,16(5):443-455.

[7]D Qing-song,Z Jiang,Z Er-yang. Location Aided Multi-Constrained Ant Colony QoS Routing Algorithm for Tactical MANETs[C]// Proceedings of 2011 7th International Conference on Wireless Communications,Networking and Mobile Computing(WiCOM).Piscataway:IEEE,2011:1-5.

[8]De Renesse R, Friderikos V,Aghvami H. Resource Information Acquisition for QoS Provision in Mobile Ad Hoc Networks [J]. Electronics Letters,2006,42(11):642-644.

[9]De Renesse R, Friderikos V.Aghvami H. Cross-Layer Cooperation for Accurate Admission Control Decisions in Mobile Ad Hoc Networks [J]. IET Communications, 2007, 1(4): 577-586.

[10]CHEN L, Heinzeiman W B. QoS-Aware Routing based on Bandwidth Estimation for Mobile Ad Hoc Networks [J]. IEEE Journal on Selected Areas in Communications, 2005, 23(3): 561-572.

[11]周灵. Waxman-Salama模型网络拓扑生成算法设计与实现[J]. 湖南理工学院学报:自然科学版),2008,21(02):40-42.

ZHOU Ling. Design and Implement of Random Network Topology Using Waxman-Salama Model[J]. Journal of Hunan Institute of Science and Technology (Natural Science Edition), 2008, 21(2):40-42.)

杨绪彬(1990—)，男，硕士研究生，主要研究方向为网络规划与管理；

张文强(1977—)，男，博士，副教授，主要研究方向为系统工程与控制；

郑翔(1980—)，男，博士，副教授，主要研究方向为系统工程与控制；

张妍(1983—)，女，学士，工程师，主要研究方向为通信网络。

Natural Science Foundation of Jiangsu Province(No.BK20140065)

A QoS Routing Algorithm BLQRA for Tactical MANET

YANG Xu-bin1，ZHANG Wen-qiang1，ZHENG Xiang1，ZHANG Yan2

(1.Department of Communication Engineering, PLA University of Science and Technology,Nanjing Jiangsu 210007,China；2.No.28 Institute of CETC,Nanjing Jiangsu 210007,China)

Aiming at QoS (Quality of Service) guarantee for different priority service in tactical MANET (Mobile Ad Hoc Network), a QoS routing algorithm BLQRA based on available bandwidth access threshold and load balance of the nodes is proposed. Based on the idea of ACO (Ant Colony Optimization), a modified ant colony algorithm is designed and implemented,thus to search the routes which could satisfy the requirement of minimum cost under the QoS constraints. Simulation results show that the proposed BLQRA algorithm could realize effective search of the route from the source node and the destination node under the condition of dynamic network parameters, and as compared with traditional ACRA algorithm, may eventually converge to a route of less cost.

tactical mobile Ad Hoc network; load balance; QoS routing algorithm; ant colony optimization

10.3969/j.issn.1002-0802.2016.03.013

2015-10-16；

2016-02-09Received date:2015-10-16；Revised date：2016-02-09

TP393

A

1002-0802(2016)03-0318-07

江苏省自然科学基金(No.BK20140065)