一種戰(zhàn)術(shù)MANET中QoS路由算法BLQRA

楊緒彬，張文強(qiáng)，鄭　翔，張　妍

(1.解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.中國電子科技集團(tuán)公司第二十八研究所，江蘇 南京 210007)

?

一種戰(zhàn)術(shù)MANET中QoS路由算法BLQRA

楊緒彬1，張文強(qiáng)1，鄭翔1，張妍2

(1.解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.中國電子科技集團(tuán)公司第二十八研究所，江蘇 南京 210007)

針對戰(zhàn)術(shù)移動(dòng)自組織網(wǎng)絡(luò)(MANET)中不同優(yōu)先級業(yè)務(wù)服務(wù)質(zhì)量(QoS)保障問題，提出了一種基于節(jié)點(diǎn)可用帶寬接入門限及負(fù)載均衡的QoS路由算法(BLQRA)。利用蟻群優(yōu)化的思想通過設(shè)計(jì)改進(jìn)的蟻群算法搜索出滿足各QoS約束且耗費(fèi)最小的路徑。仿真結(jié)果表明，在網(wǎng)絡(luò)參數(shù)動(dòng)態(tài)變化的情況下，算法實(shí)現(xiàn)了源節(jié)點(diǎn)到目的節(jié)點(diǎn)滿足各QoS約束條件路徑的有效尋找，并且與傳統(tǒng)的ACRA算法相比，BLQRA算法最終收斂到了耗費(fèi)更小的路徑上。

戰(zhàn)術(shù)移動(dòng)自組織網(wǎng)絡(luò)；負(fù)載均衡；QoS路由算法；蟻群優(yōu)化

0　引　言

移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad Hoc Network, MANET)是由一組帶有無線通信收發(fā)裝置的移動(dòng)終端節(jié)點(diǎn)組成的一種多跳的臨時(shí)性無中心網(wǎng)絡(luò)[1]，不同于蜂窩移動(dòng)網(wǎng)絡(luò)，MANET無需任何的固定的基礎(chǔ)設(shè)施來支持路由和移動(dòng)性管理。由于其易組建、自組織等特性，MANET在軍用戰(zhàn)術(shù)無線通信領(lǐng)域展現(xiàn)出了巨大的應(yīng)用價(jià)值。目前，戰(zhàn)術(shù)MANET已成為傳遞軍事控制指令，戰(zhàn)場感知數(shù)據(jù)及多媒體業(yè)務(wù)的基礎(chǔ)平臺。

QoS路由是為戰(zhàn)術(shù)MANET中多媒體業(yè)務(wù)提供服務(wù)質(zhì)量保障的一項(xiàng)關(guān)鍵技術(shù)。在QoS路由優(yōu)化問題中，當(dāng)同時(shí)對兩個(gè)以上相互獨(dú)立的參數(shù)提出要求時(shí)，這個(gè)問題就是一個(gè)NP完全問題[2]。其中蟻群優(yōu)化[3](Ant Colony Optimization，ACO)作為一種啟發(fā)式優(yōu)化算法由于能夠有效地解決NP完全問題而被應(yīng)用于多約束QoS路由算法的設(shè)計(jì)。目前，研究學(xué)者已經(jīng)提出了很多適用于MANET中基于蟻群的QoS路由算法，如ACRA[4]、ARAMA[5]、AntHocNet[6]、MC-AQARA[7]等。然而這些路由算法都沒有考慮到業(yè)務(wù)等級問題。對于一個(gè)特定的戰(zhàn)術(shù)通信網(wǎng)絡(luò)，只有保障好重要用戶的通信(例如首長的通信)才能發(fā)揮出最大的作戰(zhàn)效能。 同時(shí)，為提高網(wǎng)絡(luò)的整體資源利用率，防止網(wǎng)絡(luò)因?yàn)閭€(gè)別節(jié)點(diǎn)負(fù)載過大而癱瘓，網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的負(fù)載均衡也是戰(zhàn)術(shù)MANET中QoS路由算法需要考慮的一個(gè)重點(diǎn)?；诖?，本文對戰(zhàn)術(shù)MANET中的業(yè)務(wù)等級進(jìn)行了分類并提出了一種基于節(jié)點(diǎn)帶寬接入門限及負(fù)載均衡的QoS路由算法BLQRA，該算法考慮了不同優(yōu)先級業(yè)務(wù)的多種QoS約束條件，并利用改進(jìn)的蟻群算法來尋找源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的最佳路徑。

1　節(jié)點(diǎn)可用帶寬接入門限設(shè)置

1.1業(yè)務(wù)等級分類

戰(zhàn)術(shù)MANET中，從單兵到各級指揮員用戶種類眾多且等級不同。在戰(zhàn)場環(huán)境下，當(dāng)任務(wù)的重要程度、緊急狀況不同時(shí)，用戶發(fā)送業(yè)務(wù)的重要程度同樣會有所差異。為此，本文根據(jù)用戶的重要程度及業(yè)務(wù)的重要程度將業(yè)務(wù)等級(Service Level, SL)分為三類，如表1所示。

表1　業(yè)務(wù)等級分類

以S表示業(yè)務(wù)，則各等級業(yè)務(wù)優(yōu)先級如下：

SSL=1>SSL=2>SSL=3

(1)

對應(yīng)業(yè)務(wù)優(yōu)先級：

321

其中3對應(yīng)業(yè)務(wù)優(yōu)先級最高，1對應(yīng)的業(yè)務(wù)優(yōu)先級最低。業(yè)務(wù)等級可以在IP報(bào)文的區(qū)分服務(wù)(DS)域中進(jìn)行定義。

1.2節(jié)點(diǎn)可用帶寬接入門限設(shè)置

為了保障高優(yōu)先級業(yè)務(wù)的QoS，如圖1所示，本文通過在節(jié)點(diǎn)中設(shè)置各類優(yōu)先級業(yè)務(wù)的可用帶寬接入門限值為高優(yōu)先級業(yè)務(wù)預(yù)留帶寬，從而保證高優(yōu)先級業(yè)務(wù)的路由建立成功率。

圖1　節(jié)點(diǎn)可用帶寬接入門限設(shè)置

其中W1≤W2≤W3=Wt。Wt為節(jié)點(diǎn)在空閑時(shí)的總有效帶寬，Wi為優(yōu)先級為i的業(yè)務(wù)對應(yīng)的節(jié)點(diǎn)可用帶寬接入門限值，其中i=1,2,3。該門限值規(guī)定了各優(yōu)先級業(yè)務(wù)可消耗節(jié)點(diǎn)帶寬的上限。只有當(dāng)路徑上各節(jié)點(diǎn)滿足對應(yīng)優(yōu)先級節(jié)點(diǎn)可用帶寬接入門限時(shí)，路徑才可以建立并分配帶寬資源。其中，W1，W2值的設(shè)定可以根據(jù)網(wǎng)絡(luò)中各優(yōu)先級業(yè)務(wù)實(shí)時(shí)業(yè)務(wù)阻塞率進(jìn)行動(dòng)態(tài)調(diào)整，以在各優(yōu)先級業(yè)務(wù)QoS保證與網(wǎng)絡(luò)帶寬資源利用率間達(dá)到一個(gè)最佳平衡。

2　優(yōu)化目標(biāo)建模

2.1路徑QoS參數(shù)定義

(2)

(3)

(4)

(5)

(6)

式中，D、DJ、C為加性度量參數(shù)，D(n)為在節(jié)點(diǎn)n上的時(shí)延，對應(yīng)于分組在節(jié)點(diǎn)處的處理時(shí)延、排隊(duì)時(shí)延及傳輸時(shí)延之和，D(e)為在鏈路e上的時(shí)延，對應(yīng)于分組在鏈路上的傳播時(shí)延；B和G為凹性度量參數(shù)，參照文獻(xiàn)[8-10]，以節(jié)點(diǎn)的可用帶寬近似反映當(dāng)前的網(wǎng)絡(luò)狀況，將鏈路的可用帶寬定義為該鏈路收發(fā)節(jié)點(diǎn)可用帶寬的最小值，則整個(gè)路徑的帶寬為路徑上各節(jié)點(diǎn)可用帶寬的瓶頸值。整個(gè)路徑的擁塞為路徑上節(jié)點(diǎn)的最大擁塞，其中節(jié)點(diǎn)n處的擁塞定義為n的當(dāng)前等待隊(duì)列長度Qt與總的數(shù)據(jù)緩存隊(duì)列長度Qtotal的比值，即：

G(n)=Qt/Qtotal

(7)

2.2算法目標(biāo)

對于優(yōu)先級為i的業(yè)務(wù)，本文提出算法的目標(biāo)是搜索出擁有最小耗費(fèi)且滿足時(shí)延、時(shí)延抖動(dòng)、擁塞限制以及節(jié)點(diǎn)接入帶寬門限等QoS約束的路徑，即：

(8)

式中，Dq、DJq分別為業(yè)務(wù)的時(shí)延和時(shí)延抖動(dòng)約束，Gth為預(yù)先設(shè)好的擁塞閾值，Bq為業(yè)務(wù)的最小請求帶寬，B′(n)為節(jié)點(diǎn)n上的已用帶寬，B′(n)+Bq≤Wi(n)，n∈P(s,d)描述了路徑上節(jié)點(diǎn)的接入帶寬門限限制。

對于戰(zhàn)術(shù)MANET，用戶往往會忽略節(jié)點(diǎn)或者鏈路的實(shí)際費(fèi)用，而更關(guān)心如何去平衡網(wǎng)絡(luò)中各節(jié)點(diǎn)的負(fù)載，使得整個(gè)戰(zhàn)術(shù)MANET的使用效率最大化。為此，在本文提出的算法中，將路徑的耗費(fèi)定義為路徑各節(jié)點(diǎn)上擁塞的和值，而各鏈路的耗費(fèi)為0，即：

(9)

最小化路徑的耗費(fèi)可以尋找到一條整體負(fù)載較輕的路徑，而路徑上擁塞閾值的限制可以使得所選擇的路徑避免網(wǎng)絡(luò)中個(gè)別負(fù)載較大的節(jié)點(diǎn)。

3　BLQRA算法

3.1基本的蟻群算法

蟻群優(yōu)化算法的基本思想是借鑒自然界螞蟻群體的覓食行為。當(dāng)螞蟻離開巢穴尋找食物時(shí)會在所經(jīng)過的路徑上釋放一定的信息素，信息素的強(qiáng)度表征著路徑的遠(yuǎn)近，信息素強(qiáng)度越高，表示對應(yīng)的路徑距離越短，并且釋放的信息素會隨著時(shí)間揮發(fā)。后來的螞蟻會根據(jù)信息素的強(qiáng)度來選擇路徑，路徑上的信息素強(qiáng)度越大的路徑被選擇的概率也越大，由此形成了一個(gè)正反饋，最終，螞蟻會集中到一條信息素濃度最大的最短路徑。

蟻群優(yōu)化算法具有的正反饋、分布式計(jì)算、啟發(fā)性搜索等特點(diǎn)與網(wǎng)絡(luò)優(yōu)化的要求十分匹配，因此，螞蟻的這種行為被可以被用到在MANET尋找滿足多種約束條件的路徑。如ACRA就是參照了最基本的蟻群算法中的蟻周模型在源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間尋找一條最短路徑。

3.2BLQRA算法規(guī)則

BLQRA算法在基本蟻群算法的基礎(chǔ)上，對信息素的更新方式及狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行了改進(jìn)，并根據(jù)業(yè)務(wù)QoS要求對鄰居節(jié)點(diǎn)的范圍加以限制，減少了算法的開銷，并使得算法能夠快速收斂，在業(yè)務(wù)QoS約束下找到一條耗費(fèi)最小的路徑。

3.2.1狀態(tài)轉(zhuǎn)移規(guī)則

每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一跳，在t時(shí)刻，第k只螞蟻從節(jié)點(diǎn)i選擇到鄰居節(jié)點(diǎn)j的概率通過式(10)、(11)定義，其中鄰居節(jié)點(diǎn)的范圍限制在通信范圍內(nèi)能夠滿足擁塞閾值約束及節(jié)點(diǎn)帶寬接入門限限制的下一跳節(jié)點(diǎn)。

(10)

(11)

式中，q為一個(gè)在[0,1]范圍內(nèi)服從均勻分布的隨機(jī)數(shù)，q0∈(0,1)，為一個(gè)常數(shù)變異算子，它決定了先驗(yàn)知識與探索的相對重要性，并能防止算法陷入局部最優(yōu)解。τi,j(t)為t時(shí)刻節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信息素濃度，ηi,j(t)為耗費(fèi)啟發(fā)函數(shù)，ηi,j(t)=1/C(i,j)，C(i,j)為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的耗費(fèi)，根據(jù)前對對路徑耗費(fèi)的描述，C(i,j)定義為C(i,j)=G(j)。α(α≥0)為信息素重要程度因子，β(β≥0)為啟發(fā)函數(shù)重要程度因子，α和β控制著路徑上信息素濃度與本地耗費(fèi)的相對重要性。

3.2.2本地更新規(guī)則

在路徑建立過程中，螞蟻所經(jīng)過鏈路上的信息素濃度τi,j(t)會立即進(jìn)行更新，其中信息素濃度本地更新規(guī)則定義為：

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

(12)

式中，ξ為本地信息素?fù)]發(fā)因子，0<ξ<1。τ0為各路徑上設(shè)置的信息素濃度初值，τ0通過式(13)設(shè)定:

τ0=1/N·CNN

(13)

式中，N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目，CNN為通過最近鄰算法得到的路徑耗費(fèi)。從上式可以看出，信息素初值τ0是一個(gè)很小的值，本地更新規(guī)則使得螞蟻每次經(jīng)過的鏈路上信息素濃度有所減少，以此降低了后續(xù)螞蟻選擇該鏈路的概率，增加了螞蟻對未利用鏈路開發(fā)的機(jī)會，防止算法陷入停滯狀態(tài)。

3.2.3全局更新規(guī)則

當(dāng)所有螞蟻完成一次迭代后，進(jìn)行全局信息素更新。BLRAQ算法中，在每次迭代后只有迄今最優(yōu)路徑允許更新信息素。首先，我們定義一個(gè)目標(biāo)函數(shù)Lk：

(14)

其中

(15)

(16)

在式(14)中，λ1和λ2分別為fd和fdj的正向權(quán)重，表征著在目標(biāo)函數(shù)中時(shí)延和時(shí)延抖動(dòng)的相對重要性。fd和fdj分別為時(shí)延和時(shí)延抖動(dòng)參數(shù)的罰函數(shù)，如果第k只螞蟻所在源到目的路徑滿足相應(yīng)的時(shí)延約束和時(shí)延抖動(dòng)約束，則相應(yīng)的罰函數(shù)值為1，否則為設(shè)定的懲罰值。通過比較計(jì)算每次迭代后各螞蟻所在路徑的目標(biāo)函數(shù)值，定義使得到目前為止Lk最大的路徑為迄今最優(yōu)路徑，對應(yīng)的螞蟻為迄今最優(yōu)螞蟻，相應(yīng)的目標(biāo)函數(shù)值為Lbest。每完成一次迭代后，迄今最優(yōu)路徑按式(17)所述的全局更新規(guī)則更新信息素：

(17)

式中,ρ為全局信息素?fù)]發(fā)因子，0<ρ<1。Q為常數(shù)，為迄今最優(yōu)路徑釋放信息素的增益因子。通過全局更新規(guī)則，可以使得螞蟻?zhàn)罱K集中在一條滿足業(yè)務(wù)QoS約束并使得路徑耗費(fèi)最小的路徑上。

3.3BLQRA算法流程

給定業(yè)務(wù)等級和節(jié)點(diǎn)帶寬接入門限限制及擁塞、時(shí)延、時(shí)延抖動(dòng)等QoS約束，BLQRA算法按照如下步驟進(jìn)行：

(1)通過去掉不滿足節(jié)點(diǎn)接入帶寬門限及擁塞閾值的鏈路簡化網(wǎng)絡(luò)拓?fù)洌?/p>

(2)初始化算法迭代次數(shù)、螞蟻數(shù)目，蟻群算法中的各個(gè)參數(shù)以及各鏈路上的信息素濃度τ0；

(3)每只螞蟻按照狀態(tài)轉(zhuǎn)移規(guī)則選擇下一跳；

(4)每次螞蟻經(jīng)過鏈路上的信息素濃度按照信息素本地更新規(guī)則進(jìn)行更新；

(5)當(dāng)螞蟻到達(dá)目的節(jié)點(diǎn)后，計(jì)算所經(jīng)過路徑的目標(biāo)函數(shù)值，每次迭代后，選出迄今最優(yōu)路徑并按照信息素全局更新規(guī)則進(jìn)行更新；

(6)判斷是否達(dá)到最大迭代次數(shù)，如果沒有則迭代次數(shù)加1并進(jìn)行新一輪的選路，直到達(dá)到最大迭代次數(shù)。

4　仿真設(shè)置與結(jié)果分析

本文采用MATLAB仿真平臺對BLQRA算法進(jìn)行仿真分析。

4.1網(wǎng)絡(luò)拓?fù)錁?gòu)建

戰(zhàn)術(shù)MANET拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，但在每一次執(zhí)行路由算法的短時(shí)間內(nèi)可認(rèn)為網(wǎng)絡(luò)拓?fù)浼熬W(wǎng)絡(luò)中的各QoS參數(shù)是固定不變的。本文采用改進(jìn)的Salama博士的網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法[11]對戰(zhàn)術(shù)MANET進(jìn)行拓?fù)錁?gòu)建及QoS參數(shù)設(shè)置。其中網(wǎng)絡(luò)拓?fù)湎薅ㄔ?00 km×100 km的范圍內(nèi)，節(jié)點(diǎn)數(shù)目為25。隨機(jī)產(chǎn)生的網(wǎng)絡(luò)拓?fù)淙鐖D2所示。

圖2　網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

圖2中，在通信范圍內(nèi)的各節(jié)點(diǎn)具有連接關(guān)系，鏈路上的時(shí)延、時(shí)延抖動(dòng)以及節(jié)點(diǎn)處的時(shí)延、時(shí)延抖動(dòng)、可用帶寬、擁塞等QoS參數(shù)通過相應(yīng)的QoS矩陣儲存。其中在節(jié)點(diǎn)處顯示的參數(shù)(x，y)中，x表示該節(jié)點(diǎn)當(dāng)前的可用帶寬，y表示該節(jié)點(diǎn)當(dāng)前的擁塞值。

4.2參數(shù)設(shè)置及優(yōu)化

在仿真中，我們固定3號節(jié)點(diǎn)為源節(jié)點(diǎn)，25號節(jié)點(diǎn)為目的節(jié)點(diǎn)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的三類優(yōu)先級業(yè)務(wù)接入帶寬門限值設(shè)置相同，為W1=14 Mb/s、W2=17 Mb/s、W3=20 Mb/s(各節(jié)點(diǎn)總帶寬。其他參數(shù)設(shè)置為：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算法中，α及β參數(shù)的設(shè)置對算法十分重要。如果α過大，算法容易停滯過早收斂；如果α遠(yuǎn)小于1，則算法收斂速度慢，且較難尋找到最優(yōu)解。同理，如果β設(shè)置過大，螞蟻會較容易選擇到局部耗費(fèi)最優(yōu)的路徑，算法易陷入局部最優(yōu)解。圖3和圖4分別描述了α和β對算法路徑耗費(fèi)的影響。

圖3　α對路徑耗費(fèi)的影響

圖4　β對路徑耗費(fèi)的影響

在圖3和圖4中，業(yè)務(wù)等級SL為2，迭代次數(shù)為100，平均耗費(fèi)是指在第100次迭代時(shí)所有達(dá)到目的節(jié)點(diǎn)螞蟻路徑耗費(fèi)的平均值，最小耗費(fèi)是指在所有100次迭代中達(dá)到目的節(jié)點(diǎn)螞蟻的最小耗費(fèi)，每組結(jié)果取100次仿真的平均值。最小耗費(fèi)的值反映了算法搜索最優(yōu)解的能力，最小耗費(fèi)越小，算法搜索最優(yōu)解的能力越強(qiáng)，平均耗費(fèi)與最小耗費(fèi)的差值反映了算法的收斂性，差值越大，表明算法越不收斂，差值越小，表明算法收斂性越強(qiáng)。從仿真結(jié)果可以看出，α和β設(shè)置的過大或者過小，算法都達(dá)不到最優(yōu)的性能，容易陷入到局部最優(yōu)解，尤其是當(dāng)β值較大時(shí)，算法很難收斂且容易選擇到局部最優(yōu)的路徑。當(dāng)α=β=1時(shí)，平均最小耗費(fèi)最小，且收斂性較強(qiáng)，算法的性能達(dá)到最佳。因此，在接下來的仿真中，我們將α和β設(shè)置都設(shè)置為1。

4.3算法有效性

圖5、圖6分別為業(yè)務(wù)等級為2和3時(shí)，BLQRA算法選擇出的一條滿足各QoS約束條件且路徑耗費(fèi)最短的源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑。

圖5　SL=2時(shí)路徑選擇結(jié)果

圖6　SL=3時(shí)路徑選擇結(jié)果

通過比較圖5和圖6的路徑選擇結(jié)果可以發(fā)現(xiàn)，在相同的網(wǎng)絡(luò)參數(shù)及QoS需求下，當(dāng)業(yè)務(wù)等級不同時(shí)，路徑選擇結(jié)果可能會不一樣，由于節(jié)點(diǎn)對各優(yōu)先級業(yè)務(wù)接入帶寬門限設(shè)置的不同，業(yè)務(wù)等級為2路徑上9號節(jié)點(diǎn)的可用帶寬不能滿足業(yè)務(wù)等級為3時(shí)的接入條件，因此業(yè)務(wù)等級為3的業(yè)務(wù)選擇了另一條路徑上各節(jié)點(diǎn)可用帶寬都較大的路徑，以此使當(dāng)前可用帶寬較低的節(jié)點(diǎn)能夠?yàn)楦邇?yōu)先級業(yè)務(wù)預(yù)留一定的帶寬，保證了在高優(yōu)先級業(yè)務(wù)在網(wǎng)絡(luò)整體可用帶寬較低時(shí)路由建立的成功率。此外，從路徑選擇的結(jié)果中可以看出，BLQRA算法避開了網(wǎng)絡(luò)中擁塞較重的節(jié)點(diǎn)，選擇的路徑整體負(fù)載較輕。

為驗(yàn)證BLQRA算法在網(wǎng)絡(luò)參數(shù)動(dòng)態(tài)變化時(shí)選擇路徑的正確性，我們通過先后改變業(yè)務(wù)等級為2的耗費(fèi)最短路徑上9號節(jié)點(diǎn)與12節(jié)點(diǎn)QoS參數(shù)后得到路徑選擇結(jié)果如圖7、圖8所示。

圖7　改變9號節(jié)點(diǎn)參數(shù)后SL=2時(shí)的路徑選擇結(jié)果

圖8　改變12號節(jié)點(diǎn)參數(shù)后SL=2時(shí)的路徑選擇結(jié)果

圖7為將9號節(jié)點(diǎn)擁塞值從0.3增大為0.7后業(yè)務(wù)等級為2時(shí)的路徑選擇結(jié)果，從仿真結(jié)果可以看出BLQRA算法避開了擁塞的9號節(jié)點(diǎn)，選擇了另一條整體負(fù)載較輕的路徑，且該路徑能滿足其他QoS約束，驗(yàn)證了算法的負(fù)載均衡性。

圖8為將12號節(jié)點(diǎn)可用帶寬從7.5 Mb/s減少為3.5 Mb/s后業(yè)務(wù)等級為2時(shí)的路徑選擇結(jié)果，從仿真結(jié)果中可以看出BLQRA算法繞開了不滿足節(jié)點(diǎn)接入帶寬門限的12號節(jié)點(diǎn)，預(yù)留了該節(jié)點(diǎn)的帶寬，從而保證了高優(yōu)先級業(yè)務(wù)的路由建立成功率，使得高優(yōu)先級業(yè)務(wù)能夠得到更好的QoS保障。

4.4算法先進(jìn)性

圖9是BLQRA算法與傳統(tǒng)的ACRA算法的對比，其中在BLQRA算法中業(yè)務(wù)等級為2，ACRA算法的結(jié)果是采用原有算法的思想，將耗費(fèi)定義為節(jié)點(diǎn)擁塞得出的。相對于ACRA，BLQRA算法收斂速度相對較慢，但最終能夠獲得更佳的路徑。從仿真結(jié)果中可以看出，BLQRA算法在迭代次數(shù)大于100次后已基本收斂，平均耗費(fèi)與最小耗費(fèi)差值較ACRA大是由于BLQRA算法采用的局部信息素更新規(guī)則使得螞蟻每次走過的路徑上信息素濃度都有所減少，因此即使在螞蟻搜尋到最優(yōu)路徑后后續(xù)螞蟻的搜索仍具有一定的隨機(jī)性，以此保證了BLQRA算法搜索到全局最優(yōu)解的能力。

圖9　與傳統(tǒng)ACRA算法對比

5　結(jié)　語

與民用Ad Hoc網(wǎng)絡(luò)不同，戰(zhàn)術(shù)移動(dòng)互聯(lián)網(wǎng)絡(luò)具有特殊的軍事背景，網(wǎng)絡(luò)中的用戶具有等級差異性，業(yè)務(wù)的重要程度也會隨著戰(zhàn)場環(huán)境而改變。為了提高網(wǎng)絡(luò)的使用效率，并使高優(yōu)先級業(yè)務(wù)得到更好的服務(wù)質(zhì)量保障，本文針對戰(zhàn)術(shù)MANET提出了一種基于帶寬接入門限及負(fù)載均衡的QoS算法BLQRA。該算法對不同優(yōu)先級業(yè)務(wù)設(shè)置了不同的節(jié)點(diǎn)接入帶寬門限，從而為高優(yōu)先級業(yè)務(wù)預(yù)留了帶寬。此外，在算法中，路徑的耗費(fèi)定義為路徑各節(jié)點(diǎn)擁塞的和值，因此算法能夠找到一條整體負(fù)載較輕的路徑。仿真結(jié)果驗(yàn)證了算法的有效性和先進(jìn)性。

[1]韓彬斌, 王培康, 張曉輝.自組網(wǎng)內(nèi)的延遲限制QoS路由算法研究[J].通信技術(shù), 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模型網(wǎng)絡(luò)拓?fù)渖伤惴ㄔO(shè)計(jì)與實(shí)現(xiàn)[J]. 湖南理工學(xué)院學(xué)報(bào):自然科學(xué)版),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—)，男，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)規(guī)劃與管理；

張文強(qiáng)(1977—)，男，博士，副教授，主要研究方向?yàn)橄到y(tǒng)工程與控制；

鄭翔(1980—)，男，博士，副教授，主要研究方向?yàn)橄到y(tǒng)工程與控制；

張妍(1983—)，女，學(xué)士，工程師，主要研究方向?yàn)橥ㄐ啪W(wǎng)絡(luò)。

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

江蘇省自然科學(xué)基金(No.BK20140065)