一種戰術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)