基于改進NSGA2算法的空間網(wǎng)絡(luò)安全與性能優(yōu)化

苗祎璠,杜杉杉,任佳豪,劉 然,石樂義,*

(1.中國石油大學(xué)(華東)計算機科學(xué)與技術(shù)學(xué)院,山東 青島 266580;2.光大國際金融中心,山東 青島 266071;3.中國石油大學(xué)(華東)海洋與空間信息學(xué)院,山東 青島 266580)

0 引 言

近年來,航空航天以及無線通信技術(shù)不斷進步,空間衛(wèi)星網(wǎng)絡(luò)(簡稱空間網(wǎng)絡(luò))成為了國內(nèi)外重點研究方向之一。但其通信安全面臨著嚴峻挑戰(zhàn)[1],性能分析和優(yōu)化也成為了研究重點[2]。文獻[3]提出了一種針對移動衛(wèi)星環(huán)境的魯棒密鑰協(xié)商認證方案,具有較低的計算和通信開銷。文獻[4]提出一種適用于戰(zhàn)術(shù)衛(wèi)星的高性能組密鑰管理算法,減輕了衛(wèi)星節(jié)點的工作負載。現(xiàn)有工作多是對兩者獨立進行探討,綜合考慮空間網(wǎng)絡(luò)安全和性能間相互關(guān)系并進行權(quán)衡優(yōu)化的研究相對較少。隨著安全技術(shù)在空間網(wǎng)絡(luò)上的不斷應(yīng)用,網(wǎng)絡(luò)安全和網(wǎng)絡(luò)性能之間相互影響、制約,各種防護機制在提高網(wǎng)絡(luò)可靠性的同時,會帶來不同程度通信性能開銷的增加。綜合考慮性能、安全指標(biāo)等的聯(lián)合優(yōu)化已成為空間網(wǎng)絡(luò)研究領(lǐng)域的關(guān)鍵問題之一。

然而,空間網(wǎng)絡(luò)的安全與服務(wù)性能的聯(lián)合優(yōu)化可以看作一個多目標(biāo)優(yōu)化問題(Multi-Objective Optimization Problem, MOP)。其結(jié)果是一系列較優(yōu)的Pareto最優(yōu)解集(Pareto-optimal Set,PS)。針對此問題有傳統(tǒng)尺度化方法[5]以及進化算法[6]等。在眾多進化算法中,Deb等人提出的NSGA2算法[7]利用非支配等級和擁擠距離來衡量種群中個體的適應(yīng)度。但該算法在解的收斂性、分布性等方面仍存在局限性。此后出現(xiàn)了許多改進NSGA2算法的多目標(biāo)優(yōu)化方法[8],但近期針對空間網(wǎng)絡(luò)安全與性能的優(yōu)化研究暫無文獻查詢。因此,該文利用改進的NSGA2算法很好地解決了空間網(wǎng)絡(luò)安全與性能優(yōu)化問題。

另外,空間網(wǎng)絡(luò)安全和性能的均衡優(yōu)化決策也是一個關(guān)鍵問題。目前,有許多國內(nèi)外文獻針對NSGA2算法的優(yōu)化問題做了大量研究。常用的對非劣解集決策的方法有熵權(quán)法[9]、納什均衡博弈[10]等。文獻[11]以空間信息網(wǎng)絡(luò)的高生存能力和低消耗為目標(biāo),提出了改進的NSGA2算法,利用VIKOR方法對pareto最優(yōu)解進行模糊加權(quán),得到了好的收斂效果。為了成本和壓力間的均衡,文獻[12]將NSGA2算法和MOPSO算法結(jié)合進行多目標(biāo)優(yōu)化。Esmikhani等人[13]提出了基于多目標(biāo)種群的模擬退火算法和改進的NSGA2算法,提高了模型的運行時間、成本和可用性。

綜上所述,該文提出了基于改進NSGA2算法ISN-NSGA2(NSGA2 Algorithm Based on Improved Spatial Network)與修正納什議價模型的多目標(biāo)優(yōu)化決策方案,研究空間網(wǎng)絡(luò)中通信安全與服務(wù)性能間的聯(lián)合優(yōu)化。針對NSGA2種群收斂精度低、分布性較差的問題,設(shè)計了自適應(yīng)錦標(biāo)賽選擇算子,提出了基于擁擠熵的個體動態(tài)排擠策略,并基于修正的雙人納什議價模型進行最終解優(yōu)選。最后,針對結(jié)果的收斂性和分布性進行評價,驗證了新算法的有效性,并對模型進行了求解。

1 空間網(wǎng)絡(luò)安全-性能優(yōu)化問題建模

針對空間網(wǎng)絡(luò)安全性和通信性能分別選取量化指標(biāo)構(gòu)建優(yōu)化模型,從消息機密性、完整性以及真實性水平三個方面刻畫空間網(wǎng)絡(luò)通信安全程度,以時間延遲作為網(wǎng)絡(luò)性能的衡量指標(biāo)。根據(jù)相關(guān)研究成果給出形式化描述。

1.1 多目標(biāo)優(yōu)化模型描述與構(gòu)建

1.1.1 通信安全性

(1)機密性。主要用于保證有用的信息不會泄露給未授權(quán)用戶。機密性水平主要取決于密鑰長度和加密算法。該文假定機密性級別最高為四,機密性水平Clevel如下式[14]:

(1)

其中,Ksize表示密鑰長度,Kmin表示密鑰長度的最小取值,c1和c2為調(diào)節(jié)因子,具體取值取決于Ksize的范圍。

(2)完整性。消息認證碼(Message Authentication Code,MAC)是驗證消息是否完整的一種主要技術(shù)。數(shù)據(jù)完整性水平隨校驗和呈指數(shù)增加。消息完整性水平Ilevel描述如下[8]:

(2)

其中,Mac是由Hash函數(shù)生成的消息認證碼長度,Mmin表示認證碼長度的最小取值,c3和c4為調(diào)節(jié)因子,其值取決于Mac的變化范圍。

(3)可認證性。認證服務(wù)有效避免攻擊者通過假冒終端或衛(wèi)星實施惡意欺騙?？臻g網(wǎng)絡(luò)使用單位時間內(nèi)的認證次數(shù)來定量評估認證級別。對于特定認證算法,認證率越高,安全性越強。同理,身份認證水平Alevel可表示如下[14]:

(3)

其中,rm代表認證率,c5、c6均為常數(shù)且由rm的取值范圍確定。可以觀察到Alevel隨rm緩慢增長,當(dāng)rm趨于最大值時,Alevel也緩慢達到認證的最高安全級別。

根據(jù)上述分析,空間網(wǎng)絡(luò)通信安全水平由端到端認證水平、完整性水平和消息機密性水平組成,因此,總體通信安全性水平SL可以描述為:

SL=Clevel+Ilevel+Alevel

(4)

1.1.2 通信性能

假設(shè)單個數(shù)據(jù)包從發(fā)送端到達接收端的時間間隔,即總時延為T。由于安全參數(shù)的提高在增強網(wǎng)絡(luò)通信安全級別的同時也會帶來額外性能開銷,則T包括用戶端與衛(wèi)星端之間收發(fā)數(shù)據(jù)時的加解密處理時延Cdelay、消息完整性驗證時延Idelay、通信雙方的認證時延Adelay以及消息傳播時延Tdelay。

(1)機密性時延:由加密延遲和解密延遲構(gòu)成,加解密時間隨密鑰長度線性變化且呈正相關(guān)[8],可描述為式(5)。

Cdelay=c7Ksize+c8

(5)

其中,Ksize表示密鑰長度,c7、c8取決于具體加密算法。

(2)完整性驗證時延:對于同一完整性算法,消息完整性延遲隨校驗和長度線性增加[14]。因此,數(shù)據(jù)完整性延遲可描述為式(6)。

Idelay=c9MAC+c10

(6)

其中,c9和c10由具體完整性驗證算法決定。

(3)認證時延:是從發(fā)送身份驗證請求到接收應(yīng)答之間的時間[1]。其中,c11、c12主要取決于網(wǎng)絡(luò)狀態(tài)和認證算法。則單個數(shù)據(jù)包在整個傳輸過程T中的認證時延[8]為:

Adelay=T(c11rm+c12)

(7)

根據(jù)以上分析,可得單個數(shù)據(jù)包從地面發(fā)送端經(jīng)衛(wèi)星轉(zhuǎn)發(fā)到達地面接收端這一過程的總時延T為:

T=Cdelay+2Idelay+Adelay+Tdelay

(8)

1.2 問題模型

在上述工作基礎(chǔ)上,建立由空間網(wǎng)絡(luò)安全程度最大化和時間延遲最小化構(gòu)成的多目標(biāo)優(yōu)化數(shù)學(xué)模型如下:

(9)

其中,目標(biāo)函數(shù)SL代表網(wǎng)絡(luò)安全程度,追求自身最大化,T代表網(wǎng)絡(luò)通信時延,追求自身最小化,X=(Ksize,Mac,rm)為決策向量,決策向量組合成的策略總體稱為決策空間。

2 基于ISN-NSGA2算法的多目標(biāo)優(yōu)化模型及決策

2.1 基于改進ISN-NSGA2算法的多目標(biāo)優(yōu)化

NSGA2算法被廣泛應(yīng)用于多目標(biāo)優(yōu)化問題的求解。針對NSGA2種群收斂精度低、分布性差的缺陷,對錦標(biāo)賽選擇算子和精英選擇機制進行了改進設(shè)計,使得到的解集在收斂性、分布性上都表現(xiàn)更優(yōu)。

2.1.1 自適應(yīng)錦標(biāo)賽選擇算子

N元錦標(biāo)賽選擇是目前應(yīng)用最廣泛的一種選擇算子。首先在父種群中隨機取出N個個體,然后依據(jù)它們的非支配等級和擁擠距離選擇出最優(yōu)秀的個體作為下一代繁殖的親本。但它也存在著收斂速度過慢或局部收斂的缺陷。因此,該文構(gòu)造了一種自適應(yīng)錦標(biāo)賽選擇算子,將選擇強度N由固定值調(diào)整為隨進化過程動態(tài)變化,引入了Sigmoid非線性函數(shù):f(x)=1/(1+e-ax),使得N值隨迭代次數(shù)的增加而增大。該方法更能滿足算法不同進化過程的動態(tài)需求。不同a值對應(yīng)的Sigmoid曲線變化趨勢如圖1所示。

圖1 不同a值下的Sigmoid變化曲線

為了避免選擇強度變化趨勢過于陡峭,取a值為1對應(yīng)的函數(shù)形式,基于Sigmoid函數(shù)調(diào)整的自適應(yīng)錦標(biāo)賽選擇強度表達式如式(10)所示:

(10)

其中,Nmin和Nmax分別為選擇強度N的初始值和終止值,g為當(dāng)前進化代數(shù),Gen為進化次數(shù),round()為取整函數(shù)。圖2展示了錦標(biāo)賽選擇強度隨進化代數(shù)自適應(yīng)變化的情況,調(diào)整后的選擇規(guī)模隨著進化代數(shù)的增加而遞增。

圖2 自適應(yīng)錦標(biāo)賽選擇

2.1.2 基于擁擠熵的個體動態(tài)排擠

在NSGA2算法中,擁擠距離的計算在解的分布性和多樣性保持方面發(fā)揮著重要作用。當(dāng)規(guī)模過大時,同一等級中擁擠距離較小的個體將被直接淘汰。個體i的擁擠距離用各目標(biāo)函數(shù)上排序后相鄰兩解的歸一化距離之和表示:

(11)

(12)

圖3 個體分布熵

(13)

步驟1:對合并種群Ri進行快速非支配排序,得到k個非支配集F1,F2,…,Fk,對于每個非支配集F中的解計算其擁擠熵,得到個體i的擁擠熵iCDE;

步驟2:令Pt+1=Φ,i=1;

步驟3:執(zhí)行循環(huán),若|Pt+1|+|Fi|

步驟4:循環(huán)結(jié)束,執(zhí)行個體動態(tài)排擠:淘汰非支配集Fi中擁擠熵最小的個體,對其余個體重新計算擁擠熵,重復(fù)該過程,直至|Pt+1|=Pop。

2.1.3 ISN-NSGA2優(yōu)化算法流程

在上述基礎(chǔ)上,圖4給出了改進型算法的總體流程。改進的地方主要包括自適應(yīng)錦標(biāo)賽選擇和精英選擇。其中精英選擇包括快速非支配排序、個體擁擠熵計算和個體動態(tài)排擠。

圖4 INSGA2優(yōu)化算法總體流程

2.2 基于修正雙人納什議價模型的雙目標(biāo)決策

在得到問題的一組非支配解后,基于修正的雙人納什議價模型進行最優(yōu)解決策。經(jīng)典雙人納什議價博弈模型為:

(14)

其中,di表示第i個博弈參與方的“談判破裂點”,即雙方能接受的最低效益;fi(Xj)表示第i個博弈方執(zhí)行策略Xj效益;S=(X1,X2,…,Xn)表示雙方的策略空間。博弈的目標(biāo)是各參與者從各自“談判破裂點”出發(fā),通過不斷討價還價,進行各自收益的提高,并通過相互合作最大化聯(lián)合效益U。當(dāng)U值最大化時,聯(lián)合收益最大,也即達到合作博弈的均衡,此時的解Xj就稱為“納什議價解”(Nash Bargaining Solution,NBS)。

將納什議價博弈思想應(yīng)用于多目標(biāo)決策。每個優(yōu)化目標(biāo)都被看作合作博弈中的參與方,目標(biāo)函數(shù)可表征各博弈方的收益情況,Pareto最優(yōu)解集則作為博弈方的決策策略空間?？臻g網(wǎng)絡(luò)安全性與時延代價的納什議價博弈模型被描述為:

{SL(X),T(X)}∈PF

(15)

由于在空間網(wǎng)絡(luò)環(huán)境下,對安全和性能均有較高要求,在原有模型基礎(chǔ)上,使用Minmax方法進行目標(biāo)函數(shù)的無量綱化處理,修正后的式子如式(16)所示:

(16)

3 實驗分析與模型求解

3.1 實驗性能測試

3.1.1 實驗設(shè)置

該文選取多目標(biāo)優(yōu)化領(lǐng)域普遍采用的二目標(biāo)標(biāo)準(zhǔn)測試函數(shù)ZDT1、ZDT2、ZDT3、ZDT6和三目標(biāo)標(biāo)準(zhǔn)測試函數(shù)DTLZ2對ISN-NSGA2算法、NSGA2算法進行性能測試。實驗環(huán)境在Windows 10 X64系統(tǒng)下,電腦配置1.00 GHz CPU和8 GB RAM,基于MATLAB R2020編程實現(xiàn)算法并畫圖。采用世代距離(Generational Distance,GD)和間距評價指標(biāo)(Spacing,SP)對求解結(jié)果的收斂性和分布性進行評價。GD和SP指標(biāo)的具體計算如下:

(17)

vi,vj∈P;i,j=1,2,…,|P|

(18)

(19)

3.1.2 測試與結(jié)果分析

為比較兩種算法在分布性和收斂性上的性能差異,執(zhí)行參數(shù)均統(tǒng)一設(shè)置如下:編碼方式選擇實數(shù)編碼,種群規(guī)模取值100,進化代數(shù)為200,采用模擬二進制交叉、多項式變異,交叉和變異概率分別為0.9和0.1。標(biāo)準(zhǔn)算法采用二元錦標(biāo)賽選擇,ISN-NSGA2算法采用自適應(yīng)錦標(biāo)賽選擇,其中Nmax設(shè)置為20,Nmin設(shè)置為2。圖5給出了兩種算法在5個標(biāo)準(zhǔn)測試問題上所求Pareto前沿分布效果。圖中深色部分為測試函數(shù)的真實前沿。

圖5 兩種算法在5個測試函數(shù)上獲得的Pareto前沿

左側(cè)為原算法,右側(cè)為改進算法。在解的收斂性方面,ISN-NSGA2的求解結(jié)果與真實前沿更為接近。分布性方面,ISN-NSGA2算法得到的Pareto前沿分布均勻且連續(xù),這說明在解的多樣性和分布性上ISN-NSGA2明顯優(yōu)于標(biāo)準(zhǔn)算法。

從統(tǒng)計數(shù)據(jù)的角度對算法作了進一步比較。將標(biāo)準(zhǔn)NSGA2、改進的NSGA2[15]、基于分解的多目標(biāo)進化算法(Multi-Objective Evolutionary Algorithm based on Decomposition,MOEAD)[16]和文中ISN-NSGA2算法在5個標(biāo)準(zhǔn)測試函數(shù)上分別獨立運行50次,進化代數(shù)為100,并對得到的指標(biāo)結(jié)果統(tǒng)計最大、最小和平均值。

表1和表2分別給出了四種算法求解的GD和SP相關(guān)值。從表中數(shù)據(jù)可以觀察到,文中算法的GD和SP的平均值均小于標(biāo)準(zhǔn)算法,說明ISN-NSGA2在收斂性和分布性上相較于其他算法均有提升。

表1 四種算法的GD值比較

表2 四種算法的SP值比較

圖6給出了在ZDT1和DTLZ2函數(shù)下,標(biāo)準(zhǔn)NSGA2和文中算法獨立運行20次獲得的GD指標(biāo)平均值隨進化代數(shù)變化過程的曲線。對比可以發(fā)現(xiàn),新算法的GD值降得更快,算法收斂速度提高,且在相同進化代數(shù)下,其值均小于標(biāo)準(zhǔn)算法的GD值。

圖6 不同進化代數(shù)下兩種算法GD值變化曲線

綜上,提出的自適應(yīng)錦標(biāo)賽選擇算子和基于擁擠熵的個體動態(tài)排擠策略是有效的,改進的算法相比標(biāo)準(zhǔn)算法在解分布性和收斂性上都表現(xiàn)更優(yōu)。

3.2 模型求解

采用ISN-NSGA2算法對模型(9)進行求解。模型的決策變量為X=(Ksize,Mac,rm),密鑰長度Ksize、消息認證碼長度Mac的范圍為:[16,32,64,128,256,512,1 024,2 048],認證率rm的范圍為[0.05,0.35],表3給出了模型中各參數(shù)的取值[9-10]。求解得到在各目標(biāo)上的一組Pareto最優(yōu)前沿如圖7所示。橫坐標(biāo)表示空間網(wǎng)絡(luò)通信的安全水平,縱坐標(biāo)表示時延,圖中Pareto最優(yōu)解的分布體現(xiàn)了兩目標(biāo)間相互制約的關(guān)系。并利用式(16)進行最優(yōu)解決策,最終結(jié)果如圖8所示。

表3 參數(shù)

圖7 Pareto最優(yōu)前沿

圖8 最優(yōu)解決策

目標(biāo)函數(shù)SL=11.03,T=1 078.4 ms,由公式(16)可得最優(yōu)解決策,聯(lián)合收益U最大為0.782 4,策略X=(Ksize,Mac,rm)=(128,256,0.21),即設(shè)置密鑰長度為128 bits、消息認證碼長度256 bits,認證率0.21/min時,網(wǎng)絡(luò)整體利益最大且能實現(xiàn)空間網(wǎng)絡(luò)安全程度與通信性能優(yōu)化。

4 結(jié)束語

研究了空間網(wǎng)絡(luò)中通信安全與服務(wù)性能間的聯(lián)合優(yōu)化。選取機密性、完整性、可認證性水平作為安全程度的量化指標(biāo),時延作為性能的衡量指標(biāo),以安全程度最大化、網(wǎng)絡(luò)時延最小化為目標(biāo)構(gòu)建了數(shù)學(xué)模型。為求解該問題,提出改進NSGA2算法與修正納什議價模型的多目標(biāo)優(yōu)化決策方案。ISN-NSGA2采用了自適應(yīng)錦標(biāo)賽選擇算子,將選擇強度由固定值改進為隨進化過程動態(tài)調(diào)整,有效改善了種群的收斂精度;引入擁擠熵作為新的擁擠度度量方法,更加準(zhǔn)確地評估解的優(yōu)劣,并將個體一次性排擠改為逐個淘汰,實現(xiàn)對非支配解集的均勻“修剪”;基于修正的雙人納什議價模型進行最優(yōu)解決策,通過將目標(biāo)建模為博弈雙方,在其相互競合作用下得到整體利益最大且兼顧雙方公平的策略。實驗表明,新算法在總體上有顯著的收斂性、分布性和穩(wěn)定性方面的優(yōu)勢。對模型求解能夠得到獲得滿意網(wǎng)絡(luò)通信質(zhì)量和安全強度的折中優(yōu)化解。所提方案兼顧了遺傳算法全局尋優(yōu)、通用性強的優(yōu)點,同時為解的優(yōu)選提供了一種公平客觀的方法。