基于動態可信度的QoS路由優化與仿真

余思東，黃 欣，潘紹明

(1.廣西農業職業技術學院 現代教育技術與網絡信息中心,南寧 530007;2.廣西科技大學 電氣與信息工程學院，柳州 545006)

0 引 言

服務質量路由(Quality of Service Routing,QoSR)一直是工業界所關注的熱點[1-3]。而當前有關QoS路由的研究，都是基于網絡環境是可信網絡環境這個前提。但是，現實中這種前提是難以成立的，主要原因在于：Internet具有開放互聯特性，使得任何潛在威脅能夠方便、便捷地接入，且潛在威脅具有多樣性、隱藏性等特點；Internet設計初期，只考慮數據高效傳輸，而忽略數據傳輸過程中的安全機制，從而不能確保用戶使用安全；據統計，2015年國家互聯網應急中心(CNCERT)就檢測到10萬多個惡意軟件、木馬及僵尸網絡控制端試圖攻擊或控制Internet上服務器及主機，網絡安全問題時有發生，導致網絡環境不可信。面對如此復雜Internet環境，有關可信QoS路由相關技術的研究迫在眉睫。

文獻[4-5]中認為可信QoS路由指任何網絡環境下，都能為用戶提供具有服務質量保證的路由，且該路由可信、可控、可管，可預知。其目的在于，優化網絡安全環境，提高網絡安全服務能力。

由于網絡節點是信息傳輸主體，因而一直都是被攻擊的主要對象。文獻[6]中指出網絡節點是構建網絡結構的主要組成部分，當網絡節點危險系數具有一定比例但低于某個閾值時，網絡環境將出現滯后服務現象；當網絡節點危險系數超過某個閾值時，整個網絡安全環境極度危險。因此，網絡節點可信的QoS路由研究是可信QoS路由研究領域的重心。

1 相關的研究工作

當前關于網絡節點可信的QoS路由研究主要挑戰之一，如何在網絡節點動態條件下，對網絡節點進行評估，并依據評估結果選擇一條或多條可信路由。現有的研究成果只考慮網絡節點是靜態的，并沒有考慮網絡節點動態變化特性。如文獻[7]中提出一種網絡節點可信QoS路由算法，該算法基于區間形式描述用戶所需及可信所需的模糊性，并根據此定義及已有滑動窗口和窗臺的信任控制機制理論并結合滿意度函數建立模型，同時提出適合該模型的狩獵搜索可信路由算法。文獻[8]中在集中式路由基礎上構建一種適合低連接度結構的域內保護路由算法，通過構建備份路徑，解決集中式路由面臨的低連接度環境下游網絡節點失效問題。文獻[9]中基于貝葉斯理論提出一種網絡節點信任機制，該機制通過概率公式對待測節點的通信行為結果進行評估，具有一定的主觀性和隨機性。文獻[10]中提出一種自適應性路由算法，該算法分別把可信度與QoS滿意度作為優化目標，從多目標優化角度解決可信路由問題。文獻[11]中針對移動自組織網絡中移動節點主體及其信息傳遞安全性問題，提出一種基于博弈的移動節點信任評估模型。

以上研究成果的思路是首先構建某種方法評估網絡節點可信度，然后在可信度滿足閾值的網絡節點集合中選擇QoS路由。但以上算法都具有共同不足之處，容易產生網絡節點可信度評估誤差問題。可信度評估誤差指網絡節點行為在動態發生變化，下一時刻行為產生的結果必將影響上一時刻評估值。即網絡節點在上一時刻評估的可信度值，在下一時刻可能發生變化。由于以上評估方法并不具備動態評估特性，容易造成提供的可信QoS路由存在安全隱患。

本文從全局協同角度，提出一種基于元胞自動機及復雜網絡SI擴散理論的啟發式路由算法(Heuristic Algorithm Based on Cellular Automaton and SI，HACASI)，該算法具有動態評估機制，從而保證具備動態提供可信QoS路由能力。

2 模型及問題描述

元胞自動機是離散型動力系統模型[12]，具有結構簡單、易于擴展等特點，元胞之間依據局部變化規則協同合作，能夠模擬全局網絡環境演化過程，并能夠預測下一時刻網絡環境。但元胞自動機只是一種框架模型，并不提供具體的變化規則。SI模型是基于傳染病擴散的傳播模型[13]，能夠模擬危險網絡節點，惡意傳播信息過程。兩者相結合能夠模擬網絡節點通信擴散過程，預測下一時刻網絡環境及各個網絡節點狀態。

2.1 模型

構建一個8元系統模型：LCA={D,RS,RM，R,f,FLAG,RS’,f’}:系統中每個元胞代表一個網絡節點，網絡節點之間的邊界條件定義為周期型。D為網絡空間維數(為方便討論在此定義為二維空間)，RS={可信，不可信}表示網絡節點狀態集合，當網絡節點可信時FLAG為1，否則為0。RM為當前網絡節點鄰居狀態集合，RM={RM1,RM2,…,RMn}，n表示鄰居節點總數。R為節點鄰居半徑，當R=1時定義為網絡節點直連下一跳，f為網絡節點狀態演變規則集，FLAG為網絡節點狀態標志集合，FLAG為網絡節點狀態標志集合，當網絡節點可信時FLAG為1，否則為0。RS’為網絡節點擴展狀態集合，f’ 為擴展演化規則集，初始時RS’和f’處于未激活狀態。

(1)網絡節點演變規則。對于任意節點i，根據SI模型定義，如果其為不可信節點，則以后狀態永遠無法改變(不在本文討論范圍)。本文主要討論的是可信網絡節點，其受不可信節點影響，可轉變為不可信狀態，也可依據一定規則維持原有可信狀態。

具體情況如下：假設網絡節點i在時刻t狀態為St(i)，在下一時刻t+1狀態變化為：

(1)

式中:Flag(i)為節點i狀態標志;St+1(i)為節點i在下一時刻處于可信狀態;It+1(i)為節點i在下一時刻處于不可信狀態，Qcom通信強度閾值，comt(i)為在時刻t節點i直連通信強度(與鄰接節點通信強度)，且：

(2)

式中:β1、β2為系數，NDt(i)表示在時刻t節點i對外通信強度，Trt(k)表示在時刻t與節點i通信的節點k可信度。且：

NDt(i)=∑jαjFW(wij)

(3)

式中：αj為系數；FW()為權重函數；wij為節點對之間權重。

對任意節點k，在時刻t可信度為：

(4)

式中：η1、η2為系數;Frt(k)為在時刻t節點k的通信頻率;x為變量。

(2)網絡穩態規則。設參數T’∈(0,TE)為時間參數，其中：TE>0為正整數，對任意節點i，在T’ 范圍內其狀態標志Flag(i)不再改變，即Flag集合內，Flag(i)保持不變，則稱網絡環境達到穩態。

2.2 問題描述

在網絡環境達到穩態條件下，尋找一條從源節點Vs到目的節點Vt的可信路徑ps，在可信路徑上的每個中間網絡節點必須可信，且各項度量參數(包括帶寬bw、延遲dl、延遲抖動jt、丟包率ls等)需滿足用戶服務要求：

Q:ps

(5)

(6)

式中：bw(Ubw)、dl(Udl)、jt(Ujt)、ls(Uls)分別表示其相應的閾值，Vi表示ps中間傳輸節點。

3 算法設計

為使計算方便，對式(5)中每個網絡節點度量參數(鏈路上的度量參數歸并到網絡節點上)進行歸一化變換，合并成一個加性度量參數。根據文獻[14]中研究，式(5)中凹性參數(帶寬)可通過剪枝策略對不滿足要求的鏈路(網絡節點之間的邊)進行排除，乘性參數可通過對數變化，轉化為加性參數，則可信路由問題可轉換為：

(7)

(8)

式中:wj>0,j=1,2,…,為網絡節點上各個度量參數權重;f(xj)，j=1,2,… 為所對應的各個加性度量參數函數值;δj為各個加性度量參數對應的閾值。

基于式(6)提出HACASI算法，具體實現如下：

步驟1初始化8元網絡模型為二維空間模型，網絡節點邊界為周期性，網絡節點半徑為1，定義網絡節點狀態集合RS和狀態標志集合FLAG，設置時間參數T’，設置起始網絡節點Vs和終點網絡節點Vt。

步驟2在時間T′內，依據演化規則式(1)～(4)，對每個網絡節點進行狀態調整，并對其相應的狀態標志更新。

步驟3當網絡模型達到穩態時，激活RS′ 和f′，遍歷集合FLAG中所有FLAG為1的網絡節點，設置其擴展狀態集RS′={遍歷，未遍歷} ，并初始化為未遍歷狀態。

步驟4對任意網絡節點Vi，在時刻t，根據擴展演化規則集f′計算如下：

若Vi為已遍歷狀態，則當前狀態保持不變；

若Vi為未遍歷狀態，根據式(6)中合并度量參數，計算Vs和Vi之間的合并度量參數權重D(Vs,Vi)(如果Vi與Vs不能直連或不能經過已遍歷網絡節點達到，則設為無窮大)；

步驟5網絡節點Vi與直連未遍歷網絡節點相互交換D(Vs,Vi)信息，并進行大小排序，設數組變量Array_D保存排序結果。

步驟6在Array_D中挑選使得D(Vs,Vi)最小的網絡節點Vi并設置為已遍歷狀態，并從Array_D中刪除Vi，由Vs記錄下跳節點Vi。

步驟7如果Vi=Vt且其相應的約束滿足條件，則退出；否則進入Step8。

步驟8對所有未遍歷過的網絡節點Vj，如果D(Vs,Vj)>[D(Vs,Vi)+D(Vi,Vj)] 則按照公式D(Vs,Vj)=[D(Vs,Vi)+D(Vi,Vj)]更新(D(Vi,Vj)參考步驟4中(2))，并返回步驟4。

4 仿真實驗

實驗硬件：服務節點30個，每個服務節點配置CPU為intel 酷睿 I7-6500U，內存8GB，硬盤256GB，操作系統為Linux Ubuntu Server。對于每個服務節點都可配置多個虛擬機環境。

網絡結構：Waxman[15]模型隨機生成兩種網絡拓撲結構。隨機生成具有53節點，68鏈路拓撲結構(簡稱NetOne)。

對于該網絡結構，在每條鏈路上隨機產生n個度量參數，鏈路上度量參數值隨機產生，同時每個度量參數的約束隨機產生。

實驗指標：① 節點可信比(Node Trusty Precision Rate,NTPR),該指標主要衡量網絡節點被攻擊后，在下一時刻評價網絡節點可信，總體預測成功比例。② 可信QoS路由成功率(Trusty QoS Routing Success Rate,TRSR),該指標主要檢測算法計算出的路由結果是否滿足用戶需求且保證路由是可信的。

測量手段：對NetTest，實驗仿真時間總長為90 s，每隔18 s隨機模擬產生一次對網絡節點的攻擊。

根據以上實驗定義，分別驗證本文提出的算法HACASI與算法HTRA[7]和算法AHPSO[10]的NTPR和TRSR性能。

NTPR實驗結果如下：

圖1中，橫坐標表示實驗時間，縱坐標表示NTPR。實驗仿真時間達到36 s處且經過2次模擬攻擊后，HACASI算法的NTPR平均維持在90.6%左右，HTRA算法和AHPSO算法的NTPR分別維持在88%和89.3%。但實驗仿真時間達到72s和90s處且經過3～5次以上模擬攻擊后，HACASI算法的NTPR平均維持在78%左右，HTRA算法和AHPSO算法的NTPR分別維持在68.5%和69.8%，識別率分別提高了13.9%和11.7%。

圖1 NetTest模擬環境實驗結果1

圖2中，橫坐標表示實驗時間，縱坐標表示NTPR。實驗仿真時間達到52 s處且經過2次模擬攻擊后，HACASI算法的NTPR平均維持在93%左右，HTRA算法和AHPSO算法的NTPR分別維持在87.8%和88.2%。但實驗仿真時間達到130 s處且連續經過3次以上模擬攻擊后，HACASI算法的NTPR平均維持在76.3%左右，HTRA算法和AHPSO算法的NTPR分別維持在63%和64.8%，識別率分別提高了21%和17.7%。

圖2 NetTest模擬環境實驗結果2

TRSR實驗結果如下：

圖3中，橫坐標表示實驗時間，縱坐標表示TRSR。實驗仿真達到36 s且經過2次模擬攻擊后，HACASI算法的TRSR平均維持在93.5%左右，HTRA算法和AHPSO算法的TRSR分別維持在91%和90.6%。但實驗仿真達到90 s且連續經過3次模擬攻擊后，HACASI算法的TRSR平均維持在77.4、3%左右，HTRA算法和AHPSO算法的TRSR分別維持在70%和69.3%，路由成功率分別提高了10.4%和11.5%。

圖3 NetTest模擬環境實驗結果3

圖4中，橫坐標表示實驗時間，縱坐標表示TRSR。實驗仿真時間達到52 s處且經過2次模擬攻擊后，HACASI算法的TRSR平均維持在92.3%左右，HTRA算法和AHPSO算法的TRSR分別維持在89.3%和88.5%。但實驗仿真時間達到130 s處且連續經過3次以上模擬攻擊后，HACASI算法的TRSR平均維持在77.6%左右，HTRA算法和AHPSO算法的TRSR分別維持在64.7%和66%，路由成功率分別提高了19.9%和17.5%。

圖4 NetTest模擬環境實驗結果4

從4次試驗結果可知，隨著網絡規模擴大及模擬攻擊次數增多，HACASI算法表現出具有較好的擴展性、可信性和可靠性。

5 結 語

針對現有研究成果不具備動態評估網絡節點可信度能力，提出一種啟發式算法，該算法引入元胞自動機和復雜網絡SI模型，建立具有全局協同機制的網絡節點可信度動態評估模型，有效降低網絡節點可信度評估誤差，提高QoS路由可信度。但本文未考慮路由失敗重傳機制以及信息內容可信等問題，這些將是未來工作的重點。