余思東，黃 欣，潘紹明

(1.廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 現(xiàn)代教育技術(shù)與網(wǎng)絡(luò)信息中心,南寧 530007;2.廣西科技大學(xué) 電氣與信息工程學(xué)院，柳州 545006)

0 引 言

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

文獻(xiàn)[4-5]中認(rèn)為可信QoS路由指任何網(wǎng)絡(luò)環(huán)境下，都能為用戶提供具有服務(wù)質(zhì)量保證的路由，且該路由可信、可控、可管，可預(yù)知。其目的在于，優(yōu)化網(wǎng)絡(luò)安全環(huán)境，提高網(wǎng)絡(luò)安全服務(wù)能力。

由于網(wǎng)絡(luò)節(jié)點(diǎn)是信息傳輸主體，因而一直都是被攻擊的主要對(duì)象。文獻(xiàn)[6]中指出網(wǎng)絡(luò)節(jié)點(diǎn)是構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)的主要組成部分，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)危險(xiǎn)系數(shù)具有一定比例但低于某個(gè)閾值時(shí)，網(wǎng)絡(luò)環(huán)境將出現(xiàn)滯后服務(wù)現(xiàn)象；當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)危險(xiǎn)系數(shù)超過(guò)某個(gè)閾值時(shí)，整個(gè)網(wǎng)絡(luò)安全環(huán)境極度危險(xiǎn)。因此，網(wǎng)絡(luò)節(jié)點(diǎn)可信的QoS路由研究是可信QoS路由研究領(lǐng)域的重心。

1 相關(guān)的研究工作

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

以上研究成果的思路是首先構(gòu)建某種方法評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)可信度，然后在可信度滿足閾值的網(wǎng)絡(luò)節(jié)點(diǎn)集合中選擇QoS路由。但以上算法都具有共同不足之處，容易產(chǎn)生網(wǎng)絡(luò)節(jié)點(diǎn)可信度評(píng)估誤差問(wèn)題?？尚哦仍u(píng)估誤差指網(wǎng)絡(luò)節(jié)點(diǎn)行為在動(dòng)態(tài)發(fā)生變化，下一時(shí)刻行為產(chǎn)生的結(jié)果必將影響上一時(shí)刻評(píng)估值。即網(wǎng)絡(luò)節(jié)點(diǎn)在上一時(shí)刻評(píng)估的可信度值，在下一時(shí)刻可能發(fā)生變化。由于以上評(píng)估方法并不具備動(dòng)態(tài)評(píng)估特性，容易造成提供的可信QoS路由存在安全隱患。

本文從全局協(xié)同角度，提出一種基于元胞自動(dòng)機(jī)及復(fù)雜網(wǎng)絡(luò)SI擴(kuò)散理論的啟發(fā)式路由算法(Heuristic Algorithm Based on Cellular Automaton and SI，HACASI)，該算法具有動(dòng)態(tài)評(píng)估機(jī)制，從而保證具備動(dòng)態(tài)提供可信QoS路由能力。

2 模型及問(wèn)題描述

元胞自動(dòng)機(jī)是離散型動(dòng)力系統(tǒng)模型[12]，具有結(jié)構(gòu)簡(jiǎn)單、易于擴(kuò)展等特點(diǎn)，元胞之間依據(jù)局部變化規(guī)則協(xié)同合作，能夠模擬全局網(wǎng)絡(luò)環(huán)境演化過(guò)程，并能夠預(yù)測(cè)下一時(shí)刻網(wǎng)絡(luò)環(huán)境。但元胞自動(dòng)機(jī)只是一種框架模型，并不提供具體的變化規(guī)則。SI模型是基于傳染病擴(kuò)散的傳播模型[13]，能夠模擬危險(xiǎn)網(wǎng)絡(luò)節(jié)點(diǎn)，惡意傳播信息過(guò)程。兩者相結(jié)合能夠模擬網(wǎng)絡(luò)節(jié)點(diǎn)通信擴(kuò)散過(guò)程，預(yù)測(cè)下一時(shí)刻網(wǎng)絡(luò)環(huán)境及各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)。

2.1 模型

構(gòu)建一個(gè)8元系統(tǒng)模型：LCA={D,RS,RM，R,f,FLAG,RS’,f’}:系統(tǒng)中每個(gè)元胞代表一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)之間的邊界條件定義為周期型。D為網(wǎng)絡(luò)空間維數(shù)(為方便討論在此定義為二維空間)，RS={可信，不可信}表示網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)集合，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)可信時(shí)FLAG為1，否則為0。RM為當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)鄰居狀態(tài)集合，RM={RM1,RM2,…,RMn}，n表示鄰居節(jié)點(diǎn)總數(shù)。R為節(jié)點(diǎn)鄰居半徑，當(dāng)R=1時(shí)定義為網(wǎng)絡(luò)節(jié)點(diǎn)直連下一跳，f為網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)演變規(guī)則集，F(xiàn)LAG為網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)標(biāo)志集合，F(xiàn)LAG為網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)標(biāo)志集合，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)可信時(shí)FLAG為1，否則為0。RS’為網(wǎng)絡(luò)節(jié)點(diǎn)擴(kuò)展?fàn)顟B(tài)集合，f’ 為擴(kuò)展演化規(guī)則集，初始時(shí)RS’和f’處于未激活狀態(tài)。

(1)網(wǎng)絡(luò)節(jié)點(diǎn)演變規(guī)則。對(duì)于任意節(jié)點(diǎn)i，根據(jù)SI模型定義，如果其為不可信節(jié)點(diǎn)，則以后狀態(tài)永遠(yuǎn)無(wú)法改變(不在本文討論范圍)。本文主要討論的是可信網(wǎng)絡(luò)節(jié)點(diǎn)，其受不可信節(jié)點(diǎn)影響，可轉(zhuǎn)變?yōu)椴豢尚艩顟B(tài)，也可依據(jù)一定規(guī)則維持原有可信狀態(tài)。

具體情況如下：假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)i在時(shí)刻t狀態(tài)為St(i)，在下一時(shí)刻t+1狀態(tài)變化為：

(1)

式中:Flag(i)為節(jié)點(diǎn)i狀態(tài)標(biāo)志;St+1(i)為節(jié)點(diǎn)i在下一時(shí)刻處于可信狀態(tài);It+1(i)為節(jié)點(diǎn)i在下一時(shí)刻處于不可信狀態(tài)，Qcom通信強(qiáng)度閾值，comt(i)為在時(shí)刻t節(jié)點(diǎn)i直連通信強(qiáng)度(與鄰接節(jié)點(diǎn)通信強(qiáng)度)，且：

(2)

式中:β1、β2為系數(shù)，NDt(i)表示在時(shí)刻t節(jié)點(diǎn)i對(duì)外通信強(qiáng)度，Trt(k)表示在時(shí)刻t與節(jié)點(diǎn)i通信的節(jié)點(diǎn)k可信度。且：

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

(3)

式中：αj為系數(shù)；FW()為權(quán)重函數(shù)；wij為節(jié)點(diǎn)對(duì)之間權(quán)重。

對(duì)任意節(jié)點(diǎn)k，在時(shí)刻t可信度為：

(4)

式中：η1、η2為系數(shù);Frt(k)為在時(shí)刻t節(jié)點(diǎn)k的通信頻率;x為變量。

(2)網(wǎng)絡(luò)穩(wěn)態(tài)規(guī)則。設(shè)參數(shù)T’∈(0,TE)為時(shí)間參數(shù)，其中：TE>0為正整數(shù)，對(duì)任意節(jié)點(diǎn)i，在T’ 范圍內(nèi)其狀態(tài)標(biāo)志Flag(i)不再改變，即Flag集合內(nèi)，F(xiàn)lag(i)保持不變，則稱網(wǎng)絡(luò)環(huán)境達(dá)到穩(wěn)態(tài)。

2.2 問(wèn)題描述

在網(wǎng)絡(luò)環(huán)境達(dá)到穩(wěn)態(tài)條件下，尋找一條從源節(jié)點(diǎn)Vs到目的節(jié)點(diǎn)Vt的可信路徑ps，在可信路徑上的每個(gè)中間網(wǎng)絡(luò)節(jié)點(diǎn)必須可信，且各項(xiàng)度量參數(shù)(包括帶寬bw、延遲dl、延遲抖動(dòng)jt、丟包率ls等)需滿足用戶服務(wù)要求：

Q:ps

(5)

(6)

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

3 算法設(shè)計(jì)

為使計(jì)算方便，對(duì)式(5)中每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)度量參數(shù)(鏈路上的度量參數(shù)歸并到網(wǎng)絡(luò)節(jié)點(diǎn)上)進(jìn)行歸一化變換，合并成一個(gè)加性度量參數(shù)。根據(jù)文獻(xiàn)[14]中研究，式(5)中凹性參數(shù)(帶寬)可通過(guò)剪枝策略對(duì)不滿足要求的鏈路(網(wǎng)絡(luò)節(jié)點(diǎn)之間的邊)進(jìn)行排除，乘性參數(shù)可通過(guò)對(duì)數(shù)變化，轉(zhuǎn)化為加性參數(shù)，則可信路由問(wèn)題可轉(zhuǎn)換為：

(7)

(8)

式中:wj>0,j=1,2,…,為網(wǎng)絡(luò)節(jié)點(diǎn)上各個(gè)度量參數(shù)權(quán)重;f(xj)，j=1,2,… 為所對(duì)應(yīng)的各個(gè)加性度量參數(shù)函數(shù)值;δj為各個(gè)加性度量參數(shù)對(duì)應(yīng)的閾值。

基于式(6)提出HACASI算法，具體實(shí)現(xiàn)如下：

步驟1初始化8元網(wǎng)絡(luò)模型為二維空間模型，網(wǎng)絡(luò)節(jié)點(diǎn)邊界為周期性，網(wǎng)絡(luò)節(jié)點(diǎn)半徑為1，定義網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)集合RS和狀態(tài)標(biāo)志集合FLAG，設(shè)置時(shí)間參數(shù)T’，設(shè)置起始網(wǎng)絡(luò)節(jié)點(diǎn)Vs和終點(diǎn)網(wǎng)絡(luò)節(jié)點(diǎn)Vt。

步驟2在時(shí)間T′內(nèi)，依據(jù)演化規(guī)則式(1)～(4)，對(duì)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行狀態(tài)調(diào)整，并對(duì)其相應(yīng)的狀態(tài)標(biāo)志更新。

步驟3當(dāng)網(wǎng)絡(luò)模型達(dá)到穩(wěn)態(tài)時(shí)，激活RS′ 和f′，遍歷集合FLAG中所有FLAG為1的網(wǎng)絡(luò)節(jié)點(diǎn)，設(shè)置其擴(kuò)展?fàn)顟B(tài)集RS′={遍歷，未遍歷} ，并初始化為未遍歷狀態(tài)。

步驟4對(duì)任意網(wǎng)絡(luò)節(jié)點(diǎn)Vi，在時(shí)刻t，根據(jù)擴(kuò)展演化規(guī)則集f′計(jì)算如下：

若Vi為已遍歷狀態(tài)，則當(dāng)前狀態(tài)保持不變；

若Vi為未遍歷狀態(tài)，根據(jù)式(6)中合并度量參數(shù)，計(jì)算Vs和Vi之間的合并度量參數(shù)權(quán)重D(Vs,Vi)(如果Vi與Vs不能直連或不能經(jīng)過(guò)已遍歷網(wǎng)絡(luò)節(jié)點(diǎn)達(dá)到，則設(shè)為無(wú)窮大)；

步驟5網(wǎng)絡(luò)節(jié)點(diǎn)Vi與直連未遍歷網(wǎng)絡(luò)節(jié)點(diǎn)相互交換D(Vs,Vi)信息，并進(jìn)行大小排序，設(shè)數(shù)組變量Array_D保存排序結(jié)果。

步驟6在Array_D中挑選使得D(Vs,Vi)最小的網(wǎng)絡(luò)節(jié)點(diǎn)Vi并設(shè)置為已遍歷狀態(tài)，并從Array_D中刪除Vi，由Vs記錄下跳節(jié)點(diǎn)Vi。

步驟7如果Vi=Vt且其相應(yīng)的約束滿足條件，則退出；否則進(jìn)入Step8。

步驟8對(duì)所有未遍歷過(guò)的網(wǎng)絡(luò)節(jié)點(diǎn)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 仿真實(shí)驗(yàn)

實(shí)驗(yàn)硬件：服務(wù)節(jié)點(diǎn)30個(gè)，每個(gè)服務(wù)節(jié)點(diǎn)配置CPU為intel 酷睿 I7-6500U，內(nèi)存8GB，硬盤256GB，操作系統(tǒng)為L(zhǎng)inux Ubuntu Server。對(duì)于每個(gè)服務(wù)節(jié)點(diǎn)都可配置多個(gè)虛擬機(jī)環(huán)境。

網(wǎng)絡(luò)結(jié)構(gòu)：Waxman[15]模型隨機(jī)生成兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。隨機(jī)生成具有53節(jié)點(diǎn)，68鏈路拓?fù)浣Y(jié)構(gòu)(簡(jiǎn)稱NetOne)。

對(duì)于該網(wǎng)絡(luò)結(jié)構(gòu)，在每條鏈路上隨機(jī)產(chǎn)生n個(gè)度量參數(shù)，鏈路上度量參數(shù)值隨機(jī)產(chǎn)生，同時(shí)每個(gè)度量參數(shù)的約束隨機(jī)產(chǎn)生。

實(shí)驗(yàn)指標(biāo)：① 節(jié)點(diǎn)可信比(Node Trusty Precision Rate,NTPR),該指標(biāo)主要衡量網(wǎng)絡(luò)節(jié)點(diǎn)被攻擊后，在下一時(shí)刻評(píng)價(jià)網(wǎng)絡(luò)節(jié)點(diǎn)可信，總體預(yù)測(cè)成功比例。② 可信QoS路由成功率(Trusty QoS Routing Success Rate,TRSR),該指標(biāo)主要檢測(cè)算法計(jì)算出的路由結(jié)果是否滿足用戶需求且保證路由是可信的。

測(cè)量手段：對(duì)NetTest，實(shí)驗(yàn)仿真時(shí)間總長(zhǎng)為90 s，每隔18 s隨機(jī)模擬產(chǎn)生一次對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的攻擊。

根據(jù)以上實(shí)驗(yàn)定義，分別驗(yàn)證本文提出的算法HACASI與算法HTRA[7]和算法AHPSO[10]的NTPR和TRSR性能。

NTPR實(shí)驗(yàn)結(jié)果如下：

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

圖1 NetTest模擬環(huán)境實(shí)驗(yàn)結(jié)果1

圖2中，橫坐標(biāo)表示實(shí)驗(yàn)時(shí)間，縱坐標(biāo)表示NTPR。實(shí)驗(yàn)仿真時(shí)間達(dá)到52 s處且經(jīng)過(guò)2次模擬攻擊后，HACASI算法的NTPR平均維持在93%左右，HTRA算法和AHPSO算法的NTPR分別維持在87.8%和88.2%。但實(shí)驗(yàn)仿真時(shí)間達(dá)到130 s處且連續(xù)經(jīng)過(guò)3次以上模擬攻擊后，HACASI算法的NTPR平均維持在76.3%左右，HTRA算法和AHPSO算法的NTPR分別維持在63%和64.8%，識(shí)別率分別提高了21%和17.7%。

圖2 NetTest模擬環(huán)境實(shí)驗(yàn)結(jié)果2

TRSR實(shí)驗(yàn)結(jié)果如下：

圖3中，橫坐標(biāo)表示實(shí)驗(yàn)時(shí)間，縱坐標(biāo)表示TRSR。實(shí)驗(yàn)仿真達(dá)到36 s且經(jīng)過(guò)2次模擬攻擊后，HACASI算法的TRSR平均維持在93.5%左右，HTRA算法和AHPSO算法的TRSR分別維持在91%和90.6%。但實(shí)驗(yàn)仿真達(dá)到90 s且連續(xù)經(jīng)過(guò)3次模擬攻擊后，HACASI算法的TRSR平均維持在77.4、3%左右，HTRA算法和AHPSO算法的TRSR分別維持在70%和69.3%，路由成功率分別提高了10.4%和11.5%。

圖3 NetTest模擬環(huán)境實(shí)驗(yàn)結(jié)果3

圖4中，橫坐標(biāo)表示實(shí)驗(yàn)時(shí)間，縱坐標(biāo)表示TRSR。實(shí)驗(yàn)仿真時(shí)間達(dá)到52 s處且經(jīng)過(guò)2次模擬攻擊后，HACASI算法的TRSR平均維持在92.3%左右，HTRA算法和AHPSO算法的TRSR分別維持在89.3%和88.5%。但實(shí)驗(yàn)仿真時(shí)間達(dá)到130 s處且連續(xù)經(jīng)過(guò)3次以上模擬攻擊后，HACASI算法的TRSR平均維持在77.6%左右，HTRA算法和AHPSO算法的TRSR分別維持在64.7%和66%，路由成功率分別提高了19.9%和17.5%。

圖4 NetTest模擬環(huán)境實(shí)驗(yàn)結(jié)果4

從4次試驗(yàn)結(jié)果可知，隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大及模擬攻擊次數(shù)增多，HACASI算法表現(xiàn)出具有較好的擴(kuò)展性、可信性和可靠性。

5 結(jié) 語(yǔ)

針對(duì)現(xiàn)有研究成果不具備動(dòng)態(tài)評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)可信度能力，提出一種啟發(fā)式算法，該算法引入元胞自動(dòng)機(jī)和復(fù)雜網(wǎng)絡(luò)SI模型，建立具有全局協(xié)同機(jī)制的網(wǎng)絡(luò)節(jié)點(diǎn)可信度動(dòng)態(tài)評(píng)估模型，有效降低網(wǎng)絡(luò)節(jié)點(diǎn)可信度評(píng)估誤差，提高QoS路由可信度。但本文未考慮路由失敗重傳機(jī)制以及信息內(nèi)容可信等問(wèn)題，這些將是未來(lái)工作的重點(diǎn)。