基于“適應活性”的QoS組播路由算法

王　帥　朱　磊　俞　璐　林萬里

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

?

基于“適應活性”的QoS組播路由算法

王帥朱磊俞璐林萬里

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

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

關鍵詞物理攻擊與多約束模型QoS路由適應活性蟻群算法

0引言

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

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

本文針對自然災害、戰爭等特殊應用場景下通信網絡易受到物理攻擊和約束條件影響，難以為用戶提供穩定服務[8]，現有QoS路由算法無法適用這一問題，提出基于“適應活性”的QoS路由算法。本文的主要工作有：

1) 構建節點(鏈路)的“適應活性”模型以反映網絡節點(鏈路)在受到物理攻擊和多約束條件下，實時適應不同業務和用戶需求的綜合能力。

2) 構建物理攻擊模型和節點服務行為模型，并以此為基礎結合網絡演算的相關知識求解“適應活性”模型。

3) 根據“適應活性”模型改進蟻群算法，提出一種能夠結合外界環境、業務需求與網絡狀態，綜合考慮鏈路與節點服務性能選擇路徑的QoS組播路由算法。

1“適應活性”模型的建立與求解

1.1“適應活性”建模

自然災害、戰爭等特殊應用場景下通信網絡節點性能波動較大，常規環境下用來分析節點性能的網絡建模、分析、評價方法難以滿足應急環境下的特殊需求。本文首次提出并構建的網絡節點(鏈路)“適應活性”模型是一套節點綜合服務性能指標，用以反映節點(鏈路)在動態變化的外界環境下，針對不同業務需求表現出的實時服務能力。“適應活性”的分析框架如圖1所示。

圖1　“適應活性”分析框架圖

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

(1)

1.2“適應活性”模型的求解

1.2.1物理攻擊模型的建立

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

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

b) 節點受攻擊后具有一定的恢復能力，恢復時間服從負指數分布，其參數由攻擊強度決定，節點恢復過程也可以稱為攻擊消化過程；

c) 設Amax(標準化后Amax為正整數)為節點能承受的最大累積攻擊強度，當未消化的攻擊強度累積至Amax，則節點完全損毀失效；

d) 節點在恢復期間提供部分服務，服務能力由節點服務速率刻畫。

(2)

(3)

1.2.2基于網絡演算的活性指標求解

本文根據網絡演算的相關理論求解活性指標，網絡演算是最近十多年國內外發展起來一門新的分析網絡中確定排隊系統的理論[10,11]，網絡演算將流入節點和流出節點的流量建模成到達曲線和服務曲線，以此定量分析網絡的實時變化性能。以數據型業務為例，假設業務流通過一個桶深為b(b)，以速率r(bps)釋放數據的漏桶整形器整形后流入節點k，則到達曲線α(t)為：

(4)

(5)

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

圖2　時延、帶寬、積壓分析

則可以求出t0時刻節點的時延為：

(6)

t0時刻節點的積壓為：

(7)

本文采用時延d(t)的導函數的絕對值刻畫時延抖動，旨在表示時延的即時變化幅度，時延抖動為：

(8)

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

圖3　丟包率分析

1.2.3多約束可行域的構建

本文主要考慮應急通信場景下時間、空間、頻率、節點能量等約束條件，如表1所示。

表1　多約束條件

(1) 時空頻可行域

通過分析應急通信場景下影響網絡性能的多種約束條件，構建時空頻可行域 ：

當節點處于可行域內時，才有可能為用戶提供服務。

(2) 剩余工作時間

節點的剩余工作時間由節點能量決定，通過節點能量衰減模型可估算出節點的剩余工作時間。節點受干擾時，能量在常規工作衰耗的基礎上加速衰耗，能量衰減模型表示為：

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

(9)

其中，PW(t)是t時刻的剩余能量，PW0(t)表示初始能量，λ(j)是與干擾強度j有關的參數。

2算法設計與分析

2.1蟻群算法介紹

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

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

2.2基于“適應活性”的改進蟻群算法

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

(10)

(11)

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

(12)

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

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

(13)

其中phrm(w,n)為鏈路(w,n)上的信息素值，ρ為蒸發系數，Q為信息素更新系數，ε、η用來調節鏈路時延與節點活性值在信息素更新時的影響權重。

根據上述思想，本文提出的基于“適應活性”的蟻群改進算法的具體描述如下：

初始化初始化網絡中各鏈路的信息素強度、各仿真參數以及拓撲信息。根據網絡拓撲生成禁忌表，計算并構建節點“適應活性”表。創建螞蟻分組，啟動到p個目的節點的k輪螞蟻覓食活動，每輪派出m只螞蟻。

Step1初始化禁忌表和路徑信息，發送螞蟻分組，根據式(11)在當前節點的下一可選節點集中選擇下一節點，執行step2。

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

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

Step4判斷節點p是否是目的節點集中的最后一個節點，如果不是，則從目的節點集中選擇下一節點作為算法目的節點p，初始化網絡中各鏈路的信息素強度，轉入step1。否則轉入step5。

Step5整理各輪選路的最優路徑結果，并統計比對，找出最符合要求的路徑繪制組播樹。

3仿真結果與分析

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

圖4　標準蟻群系統算法選路結果

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

圖5　基于“適應活性”的QoS組播路由算法選路結果

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

表2　部分節點(鏈路)活性值

標準蟻群算法與本算法在組播樹費用收斂，單次迭代花費、時延收斂情況的對比結果如圖6、圖7、圖8所示。

圖6　組播樹費用收斂曲線對比

圖6顯示了選路時符合QoS需求，目的節點正確的路徑構成的組播樹的總費用。算法在一開始時讓螞蟻充分擴散以避免陷入局部最優解。隨著第一輪迭代結束，算法找出最優解并更新信息素，使后續螞蟻逐漸收斂至最優路徑上。圖6中標準蟻群算法約在第125只螞蟻時算法收斂，本算法約在第100只螞蟻處收斂。由于本算法在選路時避開了活性值較低的節點14，因此最優組播樹花費比標準蟻群算法選出的最優組播樹花費略高。

圖7　路徑費用變化情況對比

圖8　路徑時延變化情況對比

圖7、圖8為每一輪迭代中初次構建的組播樹的費用和時延，相比于標準蟻群系統算法，本算法最終構建的最優組播樹繞開了節點14，因此費用略微增多。但由于物理攻擊下節點14活性較低，所以本算法構建的最優組播樹總體延時反而小于標準蟻群算法構建的經過節點14的最短路徑時延。綜上所述，本算法具有和標準蟻群算法相差不多的收斂速度和求解能力，但在選路時能夠結合外界環境、業務需求與網絡狀態，綜合考慮鏈路與節點服務性能選擇路徑。因此能夠有效解決物理攻擊與多約束條件下的QoS路由組播問題。

4結語

本文提出并求解了節點(鏈路)的“適應活性”模型以反映網絡節點(鏈路)在外界物理攻擊和多約束條件下，實時適應不同業務和用戶需求的綜合能力。在此基礎上，本文對標準蟻群算法進行改進，提出了基于“適應活性”的QoS組播路由算法，用以解決物理攻擊和多約束條件下網絡QoS路由問題。仿真證明了該算法能夠結合外界環境、業務需求與網絡狀態，綜合考慮鏈路與節點性能選擇路徑，克服了傳統蟻群算法局限于求解穩態網絡的缺點。

參考文獻

[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 ‘adaptive 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 ‘adaptive 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年江蘇省自然科學基金項目(BK20 141071)。王帥，碩士，主研領域：網絡性能分析，網絡抗毀性。朱磊，教授。俞璐，副教授。林萬里，碩士。

中圖分類號TP393

文獻標識碼A

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