王　帥　朱　磊　俞　璐　林萬里

(解放軍理工大學(xué)通信工程學(xué)院　江蘇 南京 210007)

?

基于“適應(yīng)活性”的QoS組播路由算法

王帥朱磊俞璐林萬里

(解放軍理工大學(xué)通信工程學(xué)院江蘇 南京 210007)

摘要自然災(zāi)害、戰(zhàn)爭(zhēng)等特殊應(yīng)用場(chǎng)景下通信網(wǎng)絡(luò)易受到物理攻擊和約束條件影響，難以為用戶提供穩(wěn)定服務(wù)。傳統(tǒng)的QoS路由算法基于穩(wěn)態(tài)網(wǎng)絡(luò)，在物理攻擊與多約束環(huán)境下難以適用。針對(duì)這一問題，首次提出并求解了“適應(yīng)活性”模型以綜合衡量節(jié)點(diǎn)及其相連鏈路的動(dòng)態(tài)服務(wù)性能。進(jìn)而通過改進(jìn)蟻群算法，提出了基于“適應(yīng)活性”的QoS組播路由算法。該算法能夠結(jié)合外界環(huán)境、業(yè)務(wù)需求與網(wǎng)絡(luò)狀態(tài)，綜合考慮鏈路與節(jié)點(diǎn)服務(wù)性能選擇路徑，在繼承傳統(tǒng)蟻群算法優(yōu)點(diǎn)的同時(shí)，解決了外界環(huán)境影響節(jié)點(diǎn)性能變化導(dǎo)致選路無法達(dá)到QoS最優(yōu)的問題。MATLAB仿真結(jié)果表明，該算法能夠在網(wǎng)絡(luò)性能變化時(shí)避開低性能節(jié)點(diǎn)，快速有效地選擇QoS最優(yōu)路徑。

關(guān)鍵詞物理攻擊與多約束模型QoS路由適應(yīng)活性蟻群算法

0引言

隨著因特網(wǎng)技術(shù)的不斷發(fā)展，各類新型多媒體業(yè)務(wù)對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量QoS的要求也越來越高。作為解決QoS問題的一項(xiàng)關(guān)鍵技術(shù)，QoS路由算法一直作為研究熱點(diǎn)，受到國(guó)內(nèi)外專家的重視。QoS路由是一種基于網(wǎng)絡(luò)可用資源和業(yè)務(wù)流QoS需求來選擇路徑的機(jī)制。Wang等已經(jīng)證明，當(dāng)路由選擇有兩個(gè)或多個(gè)QoS約束時(shí)，這樣的路由選擇問題就是一類NP完全問題[1]。針對(duì)這一問題，國(guó)內(nèi)外學(xué)者利用蟻群算法[2]、退火算法[3]、遺傳算法[4]、神經(jīng)網(wǎng)絡(luò)等啟發(fā)式算法設(shè)計(jì)路由算法，取得了較好的結(jié)果。

但是，現(xiàn)有路由算法主要應(yīng)用于穩(wěn)態(tài)網(wǎng)絡(luò)，節(jié)點(diǎn)服務(wù)能力差別不大且穩(wěn)定不變，因此現(xiàn)有路由算法主要將鏈路的花費(fèi)、時(shí)延等作為選路參數(shù)，對(duì)節(jié)點(diǎn)服務(wù)性能的影響考慮較少。在物理攻擊和多約束條件下，通信網(wǎng)絡(luò)受到攻擊的影響以及時(shí)間、空間、頻率、節(jié)點(diǎn)能量等多種約束條件的限制，難以為用戶提供穩(wěn)定的通信服務(wù)[5,6]。這就為現(xiàn)有的QoS路由選擇算法帶來了新的挑戰(zhàn)：1) 在物理攻擊和多約束環(huán)境中，節(jié)點(diǎn)及其相連鏈路(以下簡(jiǎn)稱節(jié)點(diǎn)(鏈路))服務(wù)能力受環(huán)境影響波動(dòng)較大，對(duì)于QoS路徑選擇的影響不可忽略[7]。2) 目前缺少能夠在物理攻擊和多約束環(huán)境下刻畫節(jié)點(diǎn)(鏈路)提供QoS綜合服務(wù)能力的度量指標(biāo)體系。

本文針對(duì)自然災(zāi)害、戰(zhàn)爭(zhēng)等特殊應(yīng)用場(chǎng)景下通信網(wǎng)絡(luò)易受到物理攻擊和約束條件影響，難以為用戶提供穩(wěn)定服務(wù)[8]，現(xiàn)有QoS路由算法無法適用這一問題，提出基于“適應(yīng)活性”的QoS路由算法。本文的主要工作有：

1) 構(gòu)建節(jié)點(diǎn)(鏈路)的“適應(yīng)活性”模型以反映網(wǎng)絡(luò)節(jié)點(diǎn)(鏈路)在受到物理攻擊和多約束條件下，實(shí)時(shí)適應(yīng)不同業(yè)務(wù)和用戶需求的綜合能力。

2) 構(gòu)建物理攻擊模型和節(jié)點(diǎn)服務(wù)行為模型，并以此為基礎(chǔ)結(jié)合網(wǎng)絡(luò)演算的相關(guān)知識(shí)求解“適應(yīng)活性”模型。

3) 根據(jù)“適應(yīng)活性”模型改進(jìn)蟻群算法，提出一種能夠結(jié)合外界環(huán)境、業(yè)務(wù)需求與網(wǎng)絡(luò)狀態(tài)，綜合考慮鏈路與節(jié)點(diǎn)服務(wù)性能選擇路徑的QoS組播路由算法。

1“適應(yīng)活性”模型的建立與求解

1.1“適應(yīng)活性”建模

自然災(zāi)害、戰(zhàn)爭(zhēng)等特殊應(yīng)用場(chǎng)景下通信網(wǎng)絡(luò)節(jié)點(diǎn)性能波動(dòng)較大，常規(guī)環(huán)境下用來分析節(jié)點(diǎn)性能的網(wǎng)絡(luò)建模、分析、評(píng)價(jià)方法難以滿足應(yīng)急環(huán)境下的特殊需求。本文首次提出并構(gòu)建的網(wǎng)絡(luò)節(jié)點(diǎn)(鏈路)“適應(yīng)活性”模型是一套節(jié)點(diǎn)綜合服務(wù)性能指標(biāo)，用以反映節(jié)點(diǎn)(鏈路)在動(dòng)態(tài)變化的外界環(huán)境下，針對(duì)不同業(yè)務(wù)需求表現(xiàn)出的實(shí)時(shí)服務(wù)能力?！斑m應(yīng)活性”的分析框架如圖1所示。

圖1　“適應(yīng)活性”分析框架圖

本文采用一個(gè)6元組形式化地描述節(jié)點(diǎn)(鏈路)的“適應(yīng)活性”。對(duì)于一個(gè)與n條鏈路相連的節(jié)點(diǎn)k，其“適應(yīng)活性”值可表述為：

(1)

1.2“適應(yīng)活性”模型的求解

1.2.1物理攻擊模型的建立

為求解“適應(yīng)活性”中各項(xiàng)指標(biāo)，首先需要構(gòu)建物理攻擊模型和多約束可行域。物理攻擊是指敵方通過火力打擊、電磁脈沖炸彈等手段造成通信網(wǎng)絡(luò)設(shè)備功能失效或通信效果不穩(wěn)定，是影響應(yīng)急網(wǎng)絡(luò)通信能力的主要因素[9]。本文采用如下的物理攻擊模型進(jìn)行分析：

a) 物理攻擊到達(dá)遵循泊松過程，攻擊強(qiáng)度服從參數(shù)為a的均勻分布；

b) 節(jié)點(diǎn)受攻擊后具有一定的恢復(fù)能力，恢復(fù)時(shí)間服從負(fù)指數(shù)分布，其參數(shù)由攻擊強(qiáng)度決定，節(jié)點(diǎn)恢復(fù)過程也可以稱為攻擊消化過程；

c) 設(shè)Amax(標(biāo)準(zhǔn)化后Amax為正整數(shù))為節(jié)點(diǎn)能承受的最大累積攻擊強(qiáng)度，當(dāng)未消化的攻擊強(qiáng)度累積至Amax，則節(jié)點(diǎn)完全損毀失效；

d) 節(jié)點(diǎn)在恢復(fù)期間提供部分服務(wù)，服務(wù)能力由節(jié)點(diǎn)服務(wù)速率刻畫。

(2)

(3)

1.2.2基于網(wǎng)絡(luò)演算的活性指標(biāo)求解

本文根據(jù)網(wǎng)絡(luò)演算的相關(guān)理論求解活性指標(biāo)，網(wǎng)絡(luò)演算是最近十多年國(guó)內(nèi)外發(fā)展起來一門新的分析網(wǎng)絡(luò)中確定排隊(duì)系統(tǒng)的理論[10,11]，網(wǎng)絡(luò)演算將流入節(jié)點(diǎn)和流出節(jié)點(diǎn)的流量建模成到達(dá)曲線和服務(wù)曲線，以此定量分析網(wǎng)絡(luò)的實(shí)時(shí)變化性能。以數(shù)據(jù)型業(yè)務(wù)為例，假設(shè)業(yè)務(wù)流通過一個(gè)桶深為b(b)，以速率r(bps)釋放數(shù)據(jù)的漏桶整形器整形后流入節(jié)點(diǎn)k，則到達(dá)曲線α(t)為：

(4)

(5)

根據(jù)網(wǎng)絡(luò)演算，如圖2所示，時(shí)延d(t)為α(t)和β(t)之間的水平距離，數(shù)據(jù)積壓bl(t)為α(t)和β(t)之間的垂直距離，可用帶寬bw(t)為β(t)的切線斜率。

圖2　時(shí)延、帶寬、積壓分析

則可以求出t0時(shí)刻節(jié)點(diǎn)的時(shí)延為：

(6)

t0時(shí)刻節(jié)點(diǎn)的積壓為：

(7)

本文采用時(shí)延d(t)的導(dǎo)函數(shù)的絕對(duì)值刻畫時(shí)延抖動(dòng)，旨在表示時(shí)延的即時(shí)變化幅度，時(shí)延抖動(dòng)為：

(8)

丟包通常發(fā)生在緩沖區(qū)溢出或超過時(shí)延限制兩種情況下，分別稱作溢出丟包和超時(shí)丟包。如圖3所示，B、W分別為節(jié)點(diǎn)丟包率的時(shí)延和容量限制。則超時(shí)丟包量為d1-d3，溢出丟包量為d2-d4，丟包率為丟包量與數(shù)據(jù)總傳輸量的比值。

圖3　丟包率分析

1.2.3多約束可行域的構(gòu)建

本文主要考慮應(yīng)急通信場(chǎng)景下時(shí)間、空間、頻率、節(jié)點(diǎn)能量等約束條件，如表1所示。

表1　多約束條件

(1) 時(shí)空頻可行域

通過分析應(yīng)急通信場(chǎng)景下影響網(wǎng)絡(luò)性能的多種約束條件，構(gòu)建時(shí)空頻可行域 ：

當(dāng)節(jié)點(diǎn)處于可行域內(nèi)時(shí)，才有可能為用戶提供服務(wù)。

(2) 剩余工作時(shí)間

節(jié)點(diǎn)的剩余工作時(shí)間由節(jié)點(diǎn)能量決定，通過節(jié)點(diǎn)能量衰減模型可估算出節(jié)點(diǎn)的剩余工作時(shí)間。節(jié)點(diǎn)受干擾時(shí)，能量在常規(guī)工作衰耗的基礎(chǔ)上加速衰耗，能量衰減模型表示為：

PW(t)=PW0e-λ0te-λ(j)t

(9)

其中，PW(t)是t時(shí)刻的剩余能量，PW0(t)表示初始能量，λ(j)是與干擾強(qiáng)度j有關(guān)的參數(shù)。

2算法設(shè)計(jì)與分析

2.1蟻群算法介紹

蟻群算法是由意大利學(xué)者Droigo等人提出的一種進(jìn)化計(jì)算方法，具有分布式計(jì)算、無中心控制、分布式個(gè)體之間間接通信等特征。在眾多智能算法中，蟻群算法有較強(qiáng)的魯棒性，易于與其他算法結(jié)合，且在近年來國(guó)內(nèi)外學(xué)者的不斷研究下，蟻群算法存在的收斂速度較慢和易達(dá)到局部最優(yōu)解的問題也得到了很大改善，算法性能有了顯著提高[11,12]。

蟻群算法借鑒了螞蟻尋找食物的過程，通過引入信息素的概念以及信息素更新策略來模擬螞蟻的間接通信機(jī)制。在解決QoS路由問題時(shí)，假設(shè)目的節(jié)點(diǎn)有p個(gè)，在源節(jié)點(diǎn)釋放m只螞蟻，每只螞蟻會(huì)按照選路規(guī)則構(gòu)建路徑，尋找目的節(jié)點(diǎn)。在所有螞蟻構(gòu)建完回路后，對(duì)篩選出的符合約束要求的回路上的信息素進(jìn)行局部更新，同時(shí)所有路徑的信息素隨著時(shí)間推移而蒸發(fā)一部分，這樣已構(gòu)建的路徑上的信息素與其他路徑上的信息素相比就會(huì)相對(duì)增多。由于螞蟻傾向于選擇性能較好、花費(fèi)較少且信息素濃度較高的路徑，那么在多次迭代之后，螞蟻就會(huì)逐漸收斂到一條路徑，即求得的解上。

2.2基于“適應(yīng)活性”的改進(jìn)蟻群算法

一般來說，大部分基于蟻群算法的QoS路由算法在處理多約束問題時(shí)都是在選路規(guī)則或信息素更新規(guī)則中加入QoS度量指標(biāo)作為啟發(fā)因素，并通過參數(shù)來控制影響大小。算法通過設(shè)置禁忌表標(biāo)記已經(jīng)過節(jié)點(diǎn)來防止產(chǎn)生回路，螞蟻在選路時(shí)讀取禁忌表和路徑信息表來計(jì)算選路指標(biāo)。但是，現(xiàn)有算法中禁忌表和路徑信息表大都基于穩(wěn)態(tài)網(wǎng)絡(luò)和固定拓?fù)?，且進(jìn)行選路時(shí)主要考慮下一鏈路的花費(fèi)和時(shí)延等情況，很少考慮下一節(jié)點(diǎn)的服務(wù)性能。但是在物理攻擊和多約束條件下，網(wǎng)絡(luò)拓?fù)湔{(diào)整變化迅速、節(jié)點(diǎn)服務(wù)性能波動(dòng)明顯，傳統(tǒng)QoS路由選擇算法很難滿足路由選擇的時(shí)效性和環(huán)境適應(yīng)性等要求。對(duì)于整條路徑而言，QoS參數(shù)根據(jù)運(yùn)算性質(zhì)可分為加性參數(shù)(時(shí)延、數(shù)據(jù)積壓)、乘性參數(shù)(丟包率)和凹性參數(shù)(可用帶寬、時(shí)延抖動(dòng)、剩余工作時(shí)間)。但對(duì)于單個(gè)節(jié)點(diǎn)來說，QoS參數(shù)則可根據(jù)越大越好或越小越好分為正向指標(biāo)(可用帶寬、剩余工作時(shí)間)和負(fù)向指標(biāo)(數(shù)據(jù)積壓、時(shí)延、時(shí)延抖動(dòng)、丟包率)。為了對(duì)節(jié)點(diǎn)的動(dòng)態(tài)性能進(jìn)行衡量，本文首先根據(jù)QoS參數(shù)性質(zhì)將“適應(yīng)活性”轉(zhuǎn)換為一種復(fù)合型的網(wǎng)絡(luò)節(jié)點(diǎn)性能指標(biāo)。形式化地，通過鏈路(w,n)與節(jié)點(diǎn)w相連的節(jié)點(diǎn)n的適應(yīng)活性值復(fù)合型性能指標(biāo)可定義為：

(10)

(11)

從式(11)中可以看出，節(jié)點(diǎn)在選擇路徑時(shí)偏向于選擇信息素高、鏈路花費(fèi)少、延時(shí)小且下一節(jié)點(diǎn)活性高的路徑，α、β、γ、θ用來調(diào)整各參數(shù)的權(quán)重，保證了算法能夠在網(wǎng)絡(luò)性能動(dòng)態(tài)變化時(shí)找到符合QoS需求的路徑。由于比起網(wǎng)絡(luò)遭受攻擊的間隔，算法收斂所需要的時(shí)間量級(jí)明顯較小，因此活性指標(biāo)只要在需要重新選路之前刷新即可，以防止選路過程中網(wǎng)絡(luò)性能變化頻繁而導(dǎo)致算法難以收斂。同時(shí)，在對(duì)路徑信息素進(jìn)行更新時(shí)，也應(yīng)考慮與鏈路相連的下一節(jié)點(diǎn)的適應(yīng)活性值，當(dāng)螞蟻完成一輪選路后，對(duì)符合要求的路徑上的信息素按照式(12)進(jìn)行更新：

(12)

對(duì)其他路徑上的信息素按照式(13)進(jìn)行更新：

phrm(w,n)=(1-ρ)phrm(w,n)

(13)

其中phrm(w,n)為鏈路(w,n)上的信息素值，ρ為蒸發(fā)系數(shù)，Q為信息素更新系數(shù)，ε、η用來調(diào)節(jié)鏈路時(shí)延與節(jié)點(diǎn)活性值在信息素更新時(shí)的影響權(quán)重。

根據(jù)上述思想，本文提出的基于“適應(yīng)活性”的蟻群改進(jìn)算法的具體描述如下：

初始化初始化網(wǎng)絡(luò)中各鏈路的信息素強(qiáng)度、各仿真參數(shù)以及拓?fù)湫畔ⅰ８鶕?jù)網(wǎng)絡(luò)拓?fù)渖山杀?，?jì)算并構(gòu)建節(jié)點(diǎn)“適應(yīng)活性”表。創(chuàng)建螞蟻分組，啟動(dòng)到p個(gè)目的節(jié)點(diǎn)的k輪螞蟻覓食活動(dòng)，每輪派出m只螞蟻。

Step1初始化禁忌表和路徑信息，發(fā)送螞蟻分組，根據(jù)式(11)在當(dāng)前節(jié)點(diǎn)的下一可選節(jié)點(diǎn)集中選擇下一節(jié)點(diǎn)，執(zhí)行step2。

Step2當(dāng)以p節(jié)點(diǎn)為目的節(jié)點(diǎn)的第j輪第i只螞蟻到達(dá)節(jié)點(diǎn)s時(shí)，如果s=p，則記錄路徑信息并與QoS約束條件比對(duì)，當(dāng)路徑符合QoS需求時(shí)螞蟻分組按原路返回源節(jié)點(diǎn)，轉(zhuǎn)入step3。如果s≠p，則更新禁忌表和可選節(jié)點(diǎn)集并根據(jù)式(11)在s的可選節(jié)點(diǎn)集中選擇下一節(jié)點(diǎn)設(shè)為s，重新開始step2，如果沒有下一節(jié)點(diǎn)可選，則丟棄分組。

Step3當(dāng)源節(jié)點(diǎn)收到返回的第j輪第i只螞蟻分組時(shí)，如果i=m，則本輪選路完成。在本輪選出的所有路徑中找出最優(yōu)路徑(根據(jù)業(yè)務(wù)需求可以是時(shí)延最小或花費(fèi)最小等)，并按照式(12)刷新所有經(jīng)過的路徑的信息素強(qiáng)度值，用式(13)刷新其他沒有經(jīng)過的路徑的強(qiáng)度值，將源節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)，當(dāng)j≠k時(shí)轉(zhuǎn)入step1，否則轉(zhuǎn)入step4。如果i≠m，則將源節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)，轉(zhuǎn)入step1。

Step4判斷節(jié)點(diǎn)p是否是目的節(jié)點(diǎn)集中的最后一個(gè)節(jié)點(diǎn)，如果不是，則從目的節(jié)點(diǎn)集中選擇下一節(jié)點(diǎn)作為算法目的節(jié)點(diǎn)p，初始化網(wǎng)絡(luò)中各鏈路的信息素強(qiáng)度，轉(zhuǎn)入step1。否則轉(zhuǎn)入step5。

Step5整理各輪選路的最優(yōu)路徑結(jié)果，并統(tǒng)計(jì)比對(duì)，找出最符合要求的路徑繪制組播樹。

3仿真結(jié)果與分析

本節(jié)使用Matlab模擬物理攻擊和多約束條件下的網(wǎng)絡(luò)環(huán)境，并對(duì)標(biāo)準(zhǔn)蟻群系統(tǒng)算法和本算法進(jìn)行仿真實(shí)現(xiàn)，進(jìn)而通過對(duì)比算法結(jié)果來驗(yàn)證本算法的有效性。首先在空間約束為10km的正方形區(qū)域中生成25個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)。選擇10km作為空間約束，一是符合戰(zhàn)場(chǎng)通信網(wǎng)絡(luò)規(guī)模，二是可使鏈路時(shí)延單位數(shù)量級(jí)與節(jié)點(diǎn)時(shí)延相同，在之后的分析中可以通過比對(duì)不同算法選擇路徑的總時(shí)延驗(yàn)證本文算法兼顧節(jié)點(diǎn)與鏈路進(jìn)行選路的特點(diǎn)。設(shè)置仿真參數(shù)α=2、β=2、ε=1、η=0.5、Q=5×10-5初始信息素為1，路徑花費(fèi)cost以跳數(shù)衡量。從源節(jié)點(diǎn)發(fā)送漏桶型數(shù)據(jù)，發(fā)送速率r=6(bit/s)，桶深b=10(bit)。每輪釋放螞蟻50只，算法迭代30輪，則選路結(jié)果如圖4所示。

圖4　標(biāo)準(zhǔn)蟻群系統(tǒng)算法選路結(jié)果

如圖4所示，節(jié)點(diǎn)13為源節(jié)點(diǎn)，節(jié)點(diǎn)9、12、20、23為目的節(jié)點(diǎn)。由于路徑花費(fèi)為跳數(shù)，路徑時(shí)延=節(jié)點(diǎn)距離/數(shù)據(jù)傳播速度，則該選路問題可以簡(jiǎn)化為一個(gè)最短路徑求解問題?？梢姌?biāo)準(zhǔn)蟻群算法所選路徑為最優(yōu)解。此時(shí)在不考慮通信靜默的情況下，按照1.2.1節(jié)中的攻擊模型對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)施加物理攻擊。攻擊頻率λ=1次/min，標(biāo)準(zhǔn)化后單次攻擊強(qiáng)度服從a=3的均勻分布，節(jié)點(diǎn)修復(fù)速率μ=2/min。為了對(duì)比選路結(jié)果，假設(shè)中間節(jié)點(diǎn)14能夠承受的最大累積攻擊強(qiáng)度A=5，其余節(jié)點(diǎn)能夠承受的最大累積攻擊強(qiáng)度A=10，節(jié)點(diǎn)能夠提供的最大服務(wù)速率R=10(bit/s)，按照1.2.2節(jié)的分析和式(10)構(gòu)建節(jié)點(diǎn)(鏈路)“適應(yīng)活性”表。物理攻擊開始5分鐘后，同時(shí)運(yùn)用標(biāo)準(zhǔn)蟻群算法與本算法進(jìn)行選路。由于標(biāo)準(zhǔn)蟻群系統(tǒng)算法并不考慮環(huán)境影響與節(jié)點(diǎn)性能，因此選路結(jié)果仍為圖4所示，而本算法選路結(jié)果如圖5所示。

圖5　基于“適應(yīng)活性”的QoS組播路由算法選路結(jié)果

fwn表示通過鏈路(w,n)與節(jié)點(diǎn)w相連的節(jié)點(diǎn)n的復(fù)合適應(yīng)活性值。則取活性表的相關(guān)部分如表2所示，結(jié)合比較圖4與圖5可知，節(jié)點(diǎn)14在受攻擊條件下“適應(yīng)活性”值較低，說明其在時(shí)延、積壓、丟包率等服務(wù)性能上相比其他節(jié)點(diǎn)較弱。在綜合考慮鏈路花費(fèi)、鏈路時(shí)延和下一節(jié)點(diǎn)“適應(yīng)活性”的情況下，算法選路繞過節(jié)點(diǎn)14，選擇花費(fèi)為3的路徑[13,6,8,12]。而其他三條路徑相關(guān)節(jié)點(diǎn)“適應(yīng)活性”值相差不大，本文算法選路結(jié)果與標(biāo)準(zhǔn)蟻群系統(tǒng)算法選路結(jié)果相同。由于穩(wěn)態(tài)環(huán)境下各個(gè)節(jié)點(diǎn)之間的“適應(yīng)活性”指標(biāo)可認(rèn)為是相等的，則上述實(shí)驗(yàn)結(jié)果證明本算法可適用于穩(wěn)態(tài)環(huán)境，且在物理攻擊和多約束下可以根據(jù)節(jié)點(diǎn)“適應(yīng)活性”選擇更優(yōu)的QoS路徑。

表2　部分節(jié)點(diǎn)(鏈路)活性值

標(biāo)準(zhǔn)蟻群算法與本算法在組播樹費(fèi)用收斂，單次迭代花費(fèi)、時(shí)延收斂情況的對(duì)比結(jié)果如圖6、圖7、圖8所示。

圖6　組播樹費(fèi)用收斂曲線對(duì)比

圖6顯示了選路時(shí)符合QoS需求，目的節(jié)點(diǎn)正確的路徑構(gòu)成的組播樹的總費(fèi)用。算法在一開始時(shí)讓螞蟻充分?jǐn)U散以避免陷入局部最優(yōu)解。隨著第一輪迭代結(jié)束，算法找出最優(yōu)解并更新信息素，使后續(xù)螞蟻逐漸收斂至最優(yōu)路徑上。圖6中標(biāo)準(zhǔn)蟻群算法約在第125只螞蟻時(shí)算法收斂，本算法約在第100只螞蟻處收斂。由于本算法在選路時(shí)避開了活性值較低的節(jié)點(diǎn)14，因此最優(yōu)組播樹花費(fèi)比標(biāo)準(zhǔn)蟻群算法選出的最優(yōu)組播樹花費(fèi)略高。

圖7　路徑費(fèi)用變化情況對(duì)比

圖8　路徑時(shí)延變化情況對(duì)比

圖7、圖8為每一輪迭代中初次構(gòu)建的組播樹的費(fèi)用和時(shí)延，相比于標(biāo)準(zhǔn)蟻群系統(tǒng)算法，本算法最終構(gòu)建的最優(yōu)組播樹繞開了節(jié)點(diǎn)14，因此費(fèi)用略微增多。但由于物理攻擊下節(jié)點(diǎn)14活性較低，所以本算法構(gòu)建的最優(yōu)組播樹總體延時(shí)反而小于標(biāo)準(zhǔn)蟻群算法構(gòu)建的經(jīng)過節(jié)點(diǎn)14的最短路徑時(shí)延。綜上所述，本算法具有和標(biāo)準(zhǔn)蟻群算法相差不多的收斂速度和求解能力，但在選路時(shí)能夠結(jié)合外界環(huán)境、業(yè)務(wù)需求與網(wǎng)絡(luò)狀態(tài)，綜合考慮鏈路與節(jié)點(diǎn)服務(wù)性能選擇路徑。因此能夠有效解決物理攻擊與多約束條件下的QoS路由組播問題。

4結(jié)語(yǔ)

本文提出并求解了節(jié)點(diǎn)(鏈路)的“適應(yīng)活性”模型以反映網(wǎng)絡(luò)節(jié)點(diǎn)(鏈路)在外界物理攻擊和多約束條件下，實(shí)時(shí)適應(yīng)不同業(yè)務(wù)和用戶需求的綜合能力。在此基礎(chǔ)上，本文對(duì)標(biāo)準(zhǔn)蟻群算法進(jìn)行改進(jìn)，提出了基于“適應(yīng)活性”的QoS組播路由算法，用以解決物理攻擊和多約束條件下網(wǎng)絡(luò)QoS路由問題。仿真證明了該算法能夠結(jié)合外界環(huán)境、業(yè)務(wù)需求與網(wǎng)絡(luò)狀態(tài)，綜合考慮鏈路與節(jié)點(diǎn)性能選擇路徑，克服了傳統(tǒng)蟻群算法局限于求解穩(wěn)態(tài)網(wǎng)絡(luò)的缺點(diǎn)。

參考文獻(xiàn)

[1] Wang Z,Crowcroft J.Quality of service for supporting multi-media applications[J].IEEE JSAC,1996,9(14):1228-1234.

[2] Dorigo M,Stützle T.Ant colony optimization:overview and recent advances[M].Handbook of metaheuristics.Springer US,2010:227-263.

[3] Xu Y,Qu R.Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighborhoods[J].Journal of the Operational Research Society,2011,62(2):313-325.

[4] Zafar S,Soni M K.Trust based QOS protocol (TBQP) using meta-heuristic genetic algorithm for optimizing and securing MANET[C]//Optimization,Reliabilty,and Information Technology (ICROIT),2014 International Conference on.IEEE,2014:173-177.

[5] Zakaria A H,Saman M Y M,Noor A S M,et al.Performance Analysis of Mobile Ad Hoc Networks Using Queuing Theory[C]//Proceedings of the First International Conference on Advanced Data and Information Engineering (DaEng-2013).Springer Singapore,2014:555-562.

[6] Zhang L,Liu J,Yang K.Quality of service modelling of virtualized wireless networks:A network calculus approach.Mobile Networks and Applications[J].Mobile Network and Applications,2014,19(4):572-582.

[7] Badenhop C W,Mullins B E.A black hole attack model using topology approximation for reactive ad-hoc routing protocols[J].International Journal of Security and Networks,2014,9(2):63-77.

[8] Peng S,Wang G,Hu Z,et al.Survivability modeling and analysis on 3D mobile ad-hoc networks[J].Journal of Central South University of Technology,2011,18(2):1144-1152.

[9] Yao F,Xu R,Liang Q,et al.Some key issues on modeling and simulation of military communication network[C]//Computer Science and Electronics Engineering (ICCSEE),2012 International Conference on.IEEE,2012,1:532-535.

[10] Fidler M.Survey of deterministic and stochastic service curve models in the network calculus[J].Communications Surveys & Tutorials,IEEE,2010,12(1):59-86.

[11] Kanan A,Eldos T,AlKahtani M.Mobile Ad Hoc Networks Routing Using Ant Colony Optimization[J].World of Computer Science and Information Technology Journal (WCSIT) ISSN,2013,20(1):2221-0741.

[12] Metri R,Agrawal S.Ant colony optimization algorithm based an intelligent protocol to improve QoS of MANETs[C]//Circuits,Systems,Communication and Information Technology Applications (CSCITA),2014 International Conference on.IEEE,2014:121-125.

A QoS MULTICAST ROUTING ALGORITHM BASED ON ‘ADAPTIVE LIVING’

Wang ShuaiZhu LeiYu LuLin Wanli

(CollegeofCommunicationsEngineering,PLAUniversityofScienceandTechnology,Nanjing210007,Jiangsu,China)

AbstractIn special application scenarios such as the natural disasters and the wars, communication networks are difficult to provide stable services to users because it is prone to the effects of physical attacks and multi-constraints. Traditional QoS routing algorithms are based on steady network, they are no longer suitable under the condition of physical attacks and multi-constraints. Aiming at this problem, in the paper we put forward and calculate for the first time the ‘a(chǎn)daptive living’ model to comprehensively measure the dynamic service performance of network nodes and their connecting links. Furthermore, by improving the ant colony optimisation algorithm we put forward an ‘a(chǎn)daptive living’-based QoS multicast routing algorithm. The algorithm can consider comprehensively the selection path of the link and the service performance of nodes in combination with the external environment, service requirements and network status, while inheriting the advantage of traditional ant colony optimisation, it solves the problem that the external environment affects the variation of node performance which in turn causes the path selection cannot reach QoS optimum. Result of simulation on MATLAB shows that the algorithm can keep away from low performance nodes when the networks performance varying, and can fast and effectively select QoS optimal path.

KeywordsModels of physical attacks and multi-constraintsQoS routingAdaptive livingAnt colony optimisation

收稿日期：2014-12-30。2014年江蘇省自然科學(xué)基金項(xiàng)目(BK20 141071)。王帥，碩士，主研領(lǐng)域：網(wǎng)絡(luò)性能分析，網(wǎng)絡(luò)抗毀性。朱磊，教授。俞璐，副教授。林萬里，碩士。

中圖分類號(hào)TP393

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.05.066