基于遺傳算法的計算機網(wǎng)絡(luò)安全路由

　　摘 要： 提出基于遺傳算法的計算機網(wǎng)絡(luò)安全路由優(yōu)化方法，根據(jù)認證、接入控制和加密機制，多方向量化鏈路安全，結(jié)合服務(wù)質(zhì)量參數(shù)構(gòu)建多目標安全路由模型。根據(jù)公共緩沖池與最小預(yù)留帶寬的分配，選取多目標安全路由模型優(yōu)化目標為：可行路徑平均時延最低、三類安全度量最低以及最大帶寬利用率最低等。采用自適應(yīng)遺傳算法，以求解最優(yōu)染色體編碼問題替代計算機網(wǎng)絡(luò)安全路由問題;設(shè)置適應(yīng)度函數(shù)，將計算機網(wǎng)絡(luò)安全路由的目標函數(shù)最小化問題變換成最大化問題;選取算子進行交叉與變異，通過遺傳算法求解確定適應(yīng)度值最優(yōu)的個體，實現(xiàn)計算機網(wǎng)絡(luò)安全路由優(yōu)化。仿真結(jié)果顯示：該方法確定路徑的平均時延為135 ms左右，平均最大帶寬利用率在0.5%左右，三類安全度量數(shù)值均低于其他兩種對比方法，說明該方法更能保障計算機網(wǎng)絡(luò)通暢與資源使用安全性。

　　關(guān)鍵詞： 遺傳算法; 計算機網(wǎng)絡(luò); 安全路由; 安全度量; 帶寬鏈路; 適應(yīng)度函數(shù)

　　0 引 言

　　當代社會網(wǎng)絡(luò)信息技術(shù)在全球范圍內(nèi)普遍使用，網(wǎng)絡(luò)資源合理利用是確保網(wǎng)絡(luò)資源暢通的基礎(chǔ)[1]。實現(xiàn)網(wǎng)絡(luò)資源合理利用的前提條件之一是計算機網(wǎng)絡(luò)安全路由選擇，將安全作為路由選取指標，是計算機網(wǎng)絡(luò)安全路由研究的新方向[2]。計算機網(wǎng)絡(luò)路由的安全性通過單一的安全度量難以準確描述，需要根據(jù)多種安全因素綜合確定[3]。因此，本文提出基于遺傳算法的計算機網(wǎng)絡(luò)安全路由優(yōu)化方法，通過求解多目標安全路由模型為使用者提供安全性能更好的路由。

　　1 計算機網(wǎng)絡(luò)安全路由

　　1.1 多目標安全路由模型

　　將計算機網(wǎng)絡(luò)鏈路安全度量劃分為三類[4]：第一類安全度量根據(jù)認證機制定義;第二類安全度量根據(jù)接入控制定義;第三類安全度量根據(jù)加密機制定義。依照上述網(wǎng)絡(luò)鏈路安全度量的量化定義，在計算機網(wǎng)絡(luò)路由內(nèi)引入安全度量定義[5]，構(gòu)建多目標約束最優(yōu)化模型。作為應(yīng)用范圍較廣的區(qū)分服務(wù)模型之一，俄羅斯玩偶模型具有Inter?Serv的可擴展性、IP服務(wù)質(zhì)量好、無需信令、簡單有效等優(yōu)勢[6]，因此采用該模型構(gòu)建多目標約束最優(yōu)化模型。

　　多目標約束最優(yōu)化模型內(nèi)，以[K]描述計算機網(wǎng)絡(luò)對負載提供的服務(wù)種類，[P1，P2，…，PkkPk=1]表示各服務(wù)種類對應(yīng)帶寬比例，優(yōu)先級別根據(jù)下標判斷，下標值與優(yōu)先級別呈反比。不同帶寬部分由最小預(yù)留帶寬和公共緩沖池共同組成[7]，分別用[xi]和[yi]表示，各級劃分路由帶寬中[xi]所占比例為[w]，由此得到：

　　[xi=Pi?w?Cijyi=Pi?1-w?Cij] (1)

　　式中[Cij]為鏈路[i，j]的帶寬。在第[i]類負載有數(shù)據(jù)流到達的條件下，由[xi]作為第一批次傳輸服務(wù)提供者，若[xi]無法達成傳輸目的，則公共緩沖池內(nèi)的帶寬資源提供協(xié)助。為反映服務(wù)質(zhì)量的差異，在模型中加入搶占制度，優(yōu)先級別高的負載進行傳輸時可征用優(yōu)先級別較低負載的公用緩沖池[8]。俄羅斯玩偶模型帶寬分配模型如圖1所示。

　　將圖1中的模型用[T]表示網(wǎng)絡(luò)拓撲描述。在[T=V，E，D，C]內(nèi)，[V]和[E]分別表示節(jié)點和邊的集合，[D]和[C]分別表示鏈路上的時延和帶寬。到達第[k]類服務(wù)業(yè)務(wù)流所需帶寬、鏈路[i，j]上承載的第[k]類服務(wù)業(yè)務(wù)量所需帶寬和鏈路[i，j]上的整體負載分別用[δk]，[fkij]和[rij]表示。由上述描述確定鏈路[i，j]上的帶寬利用率，也就是鏈路[i，j]上已占用帶寬加上服務(wù)請求帶寬占用量同鏈路[i，j]整體帶寬間的比值為：

　　[a=rij+δkCij] (2)

　　到達的[k]類數(shù)據(jù)流占用的整體鏈路帶寬和其在鏈路上分配的帶寬分別用[δk+fkij]和[Pk?Cij]描述，由此得到到達的[k]類數(shù)據(jù)流在優(yōu)先級別較低的公用緩沖池帶寬中所占比例為：

　　[β=maxi，j∈Pdδk+fkij-Pk?CijCij] (3)

　　由于服務(wù)等級有所差異，用[δkmax]表示各服務(wù)等級負載占用帶寬最大值，若服務(wù)等級為三級，則：

　　[δ1max=P1?Cij+1-w?P2+P3?Cij] (4)

　　[δ2max=P2?Cij+1-w?P3?Cij] (5)

　　[δ3max=P3?Cij] (6)

　　各鏈路上每一服務(wù)等級所用帶寬需小于等于上述公式中的上限。同時，優(yōu)先級別較低負載無法占用優(yōu)先級別較高負載的公用緩沖池帶寬[9]，公式描述為：

　　[rij+δk∈0，minδkmax，Cij-rij] (7)

　　基于上述分析，結(jié)合常規(guī)服務(wù)質(zhì)量參數(shù)，選取多目標安全路由模型優(yōu)化目標：可行路徑的平均時延最低;三類安全度量最低;最大帶寬利用率最低;到達[k]類數(shù)據(jù)流所占低優(yōu)先級別公用緩沖池帶寬比值最低;設(shè)定安全閾值，確保三類安全度量低于安全閾值;為確保服務(wù)請求實現(xiàn)，且計算機網(wǎng)絡(luò)順暢，需滿足鏈路帶寬大于到達的[k]類數(shù)據(jù)流帶寬加上已有負載的值。

　　1.2 遺傳算法

　　針對計算機網(wǎng)絡(luò)安全路由多目標優(yōu)化問題，需采用高效的優(yōu)化策略確定最優(yōu)解。遺傳算法是一種全局優(yōu)化搜索算法，不受搜索空間限制，不限定所求解的連續(xù)性，具有較強魯棒性與并行性[10]。因此，在求解計算機網(wǎng)絡(luò)安全路由時，利用自適應(yīng)遺傳算法，遺傳過程內(nèi)各代中不同個體均依照其適應(yīng)度高低自主確定有所差異的交叉概率與變異概率自適應(yīng)規(guī)則[11]，使群體內(nèi)不同個體具有自適應(yīng)調(diào)節(jié)功能，適應(yīng)環(huán)境波動。

　　1.2.1 問題編碼

　　依照遺傳算法，各染色體均能描述一個[n]位(bit)二進制編碼符號串，代表一個優(yōu)化指標，染色體內(nèi)每一位同一個指標狀態(tài)相對應(yīng)：1和0分別表示該指標已優(yōu)化和該指標未優(yōu)化。由此，以利用自適應(yīng)遺傳算法求解最優(yōu)染色體編碼問題替代計算機網(wǎng)絡(luò)安全路由問題[12]。

　　1.2.2 確定適應(yīng)度函數(shù)

　　根據(jù)式(8)設(shè)置適應(yīng)度函數(shù)，將計算機網(wǎng)絡(luò)安全路由的目標函數(shù)最小化問題變換成最大化問題[13]：

　　[F=γ-Z=γ-αi=1mαiεi+βj=1nhjhmaxsj] (8)

　　式中：[F]為適應(yīng)度函數(shù);[γ]為大于1的常數(shù);[α]與[β]為權(quán)重;[Z]為優(yōu)化目標函數(shù);[εi]為不安全性;[hmax]為不同優(yōu)化目標費用中的最大值;優(yōu)化目標[sj]需要費用[hj]。

　　1.2.3 確定遺傳算子[1] 2 [3]

　　推薦閱讀：計算機博士在什么期刊上發(fā)論文