基于WOA和LA的安全路由協議優化設計

熊 英，吳明芬

(1.江門開放大學 信息技術部，廣東 江門 529000；2.五邑大學 智能制造學部，廣東 江門 529000)

0 引 言

移動自組網(mobile ad hoc network，MANET)[1,2]基礎設施的缺失降低了惡意行為檢測效率，要求數據傳輸應盡可能選擇高安全性鏈路，安全路由協議優化問題隨之產生。

提高路由協議安全性可通過優化協議參數實現。文獻[3]以節點移動度為指標，設計多點延時改進機制，提出OLSR安全優化協議，丟包率降低，但鏈路負載和電池剩余能量等性能下降。文獻[4]為規避NP-C(nondetermi-nistic polynomial completeness)問題，提出基于信任度的服務質量路由(trust-based QoS routing，TQR)模型，丟包率和時延得到改善，但重傳分組數急劇增加，吞吐量降低。文獻[5]指出單指標優化模型的局限性，建立了時延、跳數、代價和可靠性等參量的多維目標函數，基于蟻群算法實現了NP-C尋優，但恒比特流(constant bit rate，CBR)丟包率較高。文獻[6,7]引入能量參數，分析了丟包率、時延/抖動，但協議復雜度增加，約束條件有待改進。于是安全路由協議問題變為多維目標函數優化問題，后者廣泛采用元啟發優化算法解決多維目標函數NC-C問題[8-11]。其中基于種群優化算法的鯨魚優化算法(whale optimization algorithm，WOA)通過模擬座頭鯨獵物包圍、氣泡攻擊/區域劃分、獵物尋找/域內搜索、獵物擊中等行為，實現全域螺旋搜索，被逐步用于安全路由協議的優化設計[12]。但文獻[13]指出，在WOA探索階段，低效的域劃分和域內搜索機制降低了算法收斂速度及最優解的尋優效率。同時文獻[14]提出的獅子算法(lion algorithm，LA)將搜索域一分為二(即male和female域)，各域內并行搜索，通過領域防護和領域接管驅散過時解，搜索效率較高。將LA引入WOA搜索環節，可一定程度上改善WOA的運行效率和協議的性能。

為此本文定義能量、時延、鏈路生存時間等安全參數，設計多維目標安全路由協議模型，基于WOA和LA提出尋優算法LAWOA，并分析協議相關性能。

1 安全路由協議設計

在安全協議路徑選擇過程中，存在鄰節點數或路徑數量較大的情形，為降低運算量、計算時延和協議復雜度，WOA、TQR、LA等算法一般對其中前k條路徑進行優選，本節同樣采用該方法對路徑優選。具體過程為：在給定一定拓撲結構的網絡模型及多播收發節點的基礎上，利用k-means算法從所有可用路徑中優選出前k條可用路徑，定義相關安全協議參數，設計與之對應的歸一化目標函數，并利用優化算法迭代查找最優解，此時安全性最高(目標函數最優)的路徑用于收發節點之間的數據傳輸，協議的安全性將會明顯提升。值得注意的是，k-means算法是成熟度比較高的算法，因此該安全協議的關鍵問題在于安全參數的選取(文中采用信任度、能量、時延、鏈路維持時間、移動性5個指標)、目標函數的定義和優化迭代算法的設計等環節。安全協議工作流程如圖1所示。

圖1 安全協議整體框架

2 參數選擇

如前所述，安全路由協議相關參數包括信任度、節點能量、鏈路維持時間、時延、節點距離/移動性等，本節給出5種參數的定量表達式，為多維目標函數的建立和求解提供參數基礎。

2.1 信任度

(1)

(2)

(3)

式中：N表示任意時刻節點的鄰節點數目。

將式(2)和式(3)代入式(1)即可獲得節點之間的信任度值，但其值是靜態的，與MANET節點動態性存在一定差距。為降低誤差，每次迭代后均采用移動平均模型[16]加權更新，即

(4)

加權因子ε∈(0,1)，用于實現t和t+1時刻信任度值的均衡。

2.2 能 量

MANET中所有節點均由電池供電，且電池剩余能量與通信時間成反比。當電池剩余能量低于數據收發能量閾值時，收發節點之間將隨時中斷，協議安全系數也降低，因此建立能量剩余模型用于節點狀態監控，可提高協議安全性。在不考慮電池發熱損耗的條件下，能量消耗用于數據分組的接收和發送，因此節點剩余能量等于初始能量與接收/發送分組所消耗能量的差值。令節點初始能量為最大歸一化值Pfull=1，任意時刻t剩余能量Pres(t)表示為

Pres(t)=Pres(t-1)-PTx·NTx(t-1)-PRx·NRx(t-1)

(5)

首次開機加電時Pres(t)=Pfull；PTx、PRx為發送、接收單位比特所需能量，NTx(t-1)、NRx(t-1)為對應的比特數目。對于PTx和PRx而言，考慮超短波通信頻段，當忽略發熱損耗時，二者歸一化值約為

PTx=3PRx=0.03

(6)

由于Pres(t)大于一定閾值Pthrehold即可維持數據收發，因此為簡化計算，對Pres(t)做二值化處理，即

(7)

2.3 鏈路維持時間

在MANET分組傳輸過程中，鏈路維持時間小于信息傳輸所需時間時，將導致節點之間通信中斷，鏈路修復周期內數據分組將丟棄。因此選擇的鏈路生存時間越長，路由協議越安全。鏈路生存時間與節點的移動性、方向性、電磁特性等相關。考慮坐標分別為(xs,ys)、(xd,yd)的節點ns和nd，歸一化鏈路維持時間定義為

(8)

(9)

其中，TM為鏈路維持時間，R為電磁波覆蓋范圍，vs、vd、φs、φd分別為ns和nd對應的運動速度和方向角。

2.4 時 延

任何分組傳輸都存在時延，時延越大，惡意節點成功檢測到正常用戶并實施攻擊的概率越高，且突發噪聲對通信鏈路的影響也越大，因此時延同樣可以作為衡量協議安全性的重要參數。時延包括傳輸時延、處理時延、排隊時延和傳播時延等。在此假設MANET終端節點配置及數據隨機產生函數完全相同，那么時延由傳播時延決定，其值與跳數相關。任意時刻t歸一化時延Rsd(t)定義為傳輸路徑中節點的跳數(或個數)NPath(i)與所有可用路徑中節點總數的比值，即

(10)

式中：P為t時刻路徑的總數，其值由路由表數據統計獲得。同時為降低統計誤差，利用移動平均模型對其加權平均，即

R′sd(t+1)=τRsd(t)+(1-τ)Rsd(t+1)

(11)

τ為加權系數，且τ∈(0,1)。

2.5 移動性

(12)

(13)

3 目標函數建立及優化算法設計

本節在信任度、能量、時延、鏈路維持時間、移動性等服務質量參數基礎上，定義多維目標優化函數及最優解形式，并基于LA和WOA設計與之對應的優化迭代搜索算法。

3.1 最優解形式

最優解編碼形式是算法迭代搜索過程的重要參數，也是譯碼獲得最優解的重要方法。由于安全協議目的是獲取源節點S到目的節點D之間的最佳路徑，等價于確定最值問題，因此求解過程可轉化為二分查找問題。理論上，對于MANET任意節點而言，所有節點都可能成為其鄰節點，對應路由數目應等于網絡節點數。而在協議實際運行過程中，任意微小時間間隔內(路由更新時間為ms級)，低速運行(如1 m/s)環境路由表中存儲的路徑數(記為k)可視為常數，且其值遠小于網絡節點數。因此為簡化計算，在所有S到D的直連和中繼路徑中，基于k-means按優先級順序優選出前k條路徑，每條路徑用pi表示，則k條路徑集合可記為P={p1,p2,…,pk}，于是路徑編號集合np={1,2,…,k}可視為S到D對應的路徑函數解，從p1～pk中確定使目標函數達到最值的解即為最優解。

3.2 多維目標函數定義

目標函數是確定最優路徑的關鍵。如前所述，信任度、能量、時延、鏈路維持時間和移動性等指標均影響著協議的安全性，因此協議設計中應兼顧指標之間的均衡，于是目標函數需由5個指標共同確定，建立目標函數與各指標之間的聯合表達式。例如信任度越大，鏈路選擇概率越高，協議安全系數越高，目標函數值也越大。同理可確定能量、時延、鏈路維持時間和移動性與安全協議的關系，于是歸一化目標函數定義為

(14)

式中：dthreshold、M分別表示協議允許距離最大值、鏈路維持時間最大值，二者為常數。使式(14)獲得最大值的路徑即為最優路徑，于是問題轉化為目標函數的優化求解。

3.3 優化算法設計

3.3.1 優化算法執行流程

WOA算法由圍獵(encircling prey，EP)、攻擊/開發(bubble-net attack or exploitation phase，BA)、搜索/探測(search for prey or exploration phase，SP)3個環節構成。EP實現本地獵物識別及包圍功能，BA實現目標的靠近，SP實現目標獵物的搜索。其中SP環節決定了WOA算法迭代的方向和搜索范圍，算法的快慢直接影響著WOA的效率。如前所述，WOA算法已被廣泛用于多參數優化設計中，但算法在SP更新環節冗余度較高，搜索范圍隨機性大、重復率高，使其收斂速度較慢。對于MANET而言，隨著節點的移動，拓撲結構和鏈路狀態均隨時間變化，過慢的收斂速度降低了算法的精度，最佳路徑誤差也隨之增加。不難理解，提高WOA算法的收斂速度將一定程度上提高協議的運行效率和安全路徑的精度。同時LA算法模擬獅子領域更迭、接管、挖掘、榮譽等群體行為，將群體一分為二(male和female兩類)并行種群更新，算法迭代及搜索效率提高，可很大程度上彌補WOA算法的不足。因此將LA算法融入WOA算法迭代過程能夠兼顧WOA多維目標函數搜索的適用性和LA算法的高效性。結合WOA和LA算法流程，新算法對應工作流程如圖2所示。

圖2 優化算法流程

在t=0時刻，初始網絡模型給定后，可根據式(4)、式(7)、式(8)、式(11)、式(13)分別計算出Dsd、Pres、TM、Rsd、dns,nd等參數值，代入式(14)可計算無量綱目標函數f值，如果f值長時間保持不變(如迭代1000次f值不變)，算法迭代終止，并將該值賦予最優解，退出搜索；否則基于WOA和LA算法在群體中迭代搜索最優值，在任意迭代過程中，如果搜索所得目標函數值fnew>f，表示產生了更優質的解，將其存儲在f值中，否則f值保持不變；同時判斷搜索次數是否達到迭代次數上限，如果是，則表示搜索過程結束，否則繼續進行下一輪搜索，直至函數值最優。此時優化算法的關鍵在于基于WOA和LA算法搜索fnew值。

3.3.2 基于WOA和LA算法的搜索算法設計

基于WOA和LA算法思想，在此將新算法分為初始化、適應性評估、位置估計/更新、最優代理確定和結束5個階段執行。

(1)初始化

隨機生成包含n個值的解向量Fj，每個Fj記為

Fj={f1,f2,…,fn}

(15)

fj為表示第j條路徑。與此同時，初始化系數向量U和L，用于WOA算法的迭代，二者分別由式(16)、式(17)確定

U=2db-d

(16)

L=2d

(17)

其中，d從2向0線性遞減，b為[0,1]內的隨機數。

(2)目標函數估值

根據式(14)計算目標函數值。值得注意的是，初始化后，群體并不知道目標值/獵物的相關位置信息，因此目標函數值為空，那么此時計算獲得的目標函數值及其群體將作為最佳代理和最優值存儲，為下一步迭代使用。

(3)位置估計與更新

最佳代理確定后，WOA算法模擬虎頭鯨圍獵行為(包圍獵物、氣泡攻擊、尋找目標)搜索最優值，首先確定距離向量Q為

Q=|L·F*(i)-F(i)|

(18)

式中：F*(i)為最佳代理位置向量，此時根據WOA包圍獵物更新規則，第i+1次迭代值可表示為

F(i+1)=F*(i)-L·Q

(19)

在WOA攻擊環節，采用螺旋氣泡攻擊技術更新位置信息，該技術取決于代理與獵物之間的距離向量，螺旋函數表示為

F(i+1)=Q′·ehl·cos(2πl)+F*(i)

(20)

式中：Q′=|F*(i)-F(i)|表示最佳代理與目標獵物的距離，其值越小，表示越接近目標值；h表示指數螺旋函數的系數，決定螺旋函數的階數；l為[0,1]內的隨機數。為了改進搜索空間，加快算法執行效率，搜索更新過程引入LA算法，根據LA算法定義，更新規則為

F(i+1)=F(i)+(0.1q2-0.05)(F*(i)-q1F(i))

(21)

由式(19)可知

F*(i)=F(i+1)+L·Q

(22)

將式(22)代入式(21)可得

F(i+1)=F(i)+(0.1q2-0.05)(F(i+1)+L·Q-q1F(i))=

F(i)+0.1q2F(i+1)+0.1q2L·Q-0.1q2q1F(i)-0.05F(i+1)-0.05L·Q+0.05q1F(i)=F(i)(1-0.1q2q1+0.05q1)+

F(i+1)(0.1q2-0.05)+L·Q(0.1q2-0.05)

合并同類項

F(i+1)(1-0.1q2+0.05)=F(i)(1-0.1q2q1+0.05q1)+L·Q(0.1q2-0.05)

則

(23)

式中：F(i)、F(i+1)分別為位置更新后當前迭代和下次迭代位置向量。

(4)確定最優代理

當位置信息確定后，算法通過系數更新向量和距離向量生成下一代群體對應路徑集。在此基礎上，基于目標函數計算相應值，且目標函數僅保存目標函數最大值，并遞增迭代變量。

(5)結束

算法重復過程(2)～過程(4)，直至滿足以下兩個條件之一時退出：目標函數值長期不變；迭代次數達到最大值。

綜上，基于WOA和LA的新算法執行流程如圖3所示。

圖3 迭代搜索流程

4 結果分析

4.1 實驗環境

算法測試在Linux環境下進行，所需實驗環境包括硬件、軟件和模型參數3個方面，硬件為測試提供算力支撐，軟件涵蓋了測試所需的系統、網絡仿真器(network simulator，NS)、圖形顯示、協議(內置WOA等算法，在此名稱由算法替代)等方面，模型參數用于確保各算法在仿實際環境中的順利執行，仿真過程涉及的主要實驗參數設置見表1，惡意節點在t=0.5時刻隨機選擇網絡節點開始運行。

表1 仿真參數設置

4.2 性能指標

就協議安全性而言，需考量吞吐量和丟包率兩個重要指標。同時為衡量算法運行效率，需增加時間復雜度等性能分析。其中吞吐量為單位時間內數據分組的總數，單位為字節/s(或b/s)，用Throughput表示；丟包率是指未接收分組與發送分組的比值，為無量綱參數，用Loss表示；時間復雜度可用算法收斂時間定性表征。為此Throughput和Loss表達式分別為

(24)

(25)

4.3 仿真結果

為了更好地說明LAWOA算法的性能，在此對WOA、TQR和LAWOA對應的Throughput、Loss、算法運行時間結果進行對比分析。圖4為節點分布圖，圖5、圖6分別為Throughput曲線和Loss曲線，表2為算法收斂時間。

從圖5可看出，吞吐量與節點數目成正比，與惡意節點比例成反比。隨著惡意節點(t=0.5)的加入，吞吐量迅速遞減，當達到一定時間(50節點、100節點對應t=7、t=8時刻)后，網絡趨于穩定，吞吐量保持不變，且惡意節點比例越高，吞吐量下降速率越快。同時LAWOA對應 協議吞吐量明顯高于WOA與TQR算法(50節點、100節點分別高約300字節/s、400字節/s)。原因在于：一是當惡意節點執行攻擊行為后，部分網絡帶寬用于傳輸惡意節點分組，使得用于傳輸數據分組的帶寬受限，吞吐量降低，且惡意節點數越多，帶寬浪費越嚴重，吞吐量降低越快，到達一定程度后，網絡將出現擁塞，節點根據退避算法和重發機制強制推遲分組發送，正常節點和惡意節點處于競爭發送分組的穩定狀態；二是LAWOA對應協議收斂速度比WOA和TQR快，有效降低了惡意節點的作用時間，對應吞吐量得到明顯提升。

圖4 節點分布

圖5 吞吐量曲線

圖6 丟包率曲線

表2 算法收斂時間/s

從圖6可以看出，丟包率與節點數、惡意節點比例均成正比，且隨著惡意節點的加入，丟包率迅速增加，達到一定時間后趨于平穩，與TQR、WOA算法對應協議相比，LAWOA算法丟包率降低了10%～12%。原因在于：一是惡意節點導致網絡擁塞，而且分組碰撞概率增加，使得丟包率增加；二是LAWOA算法以較高效率收斂到最佳路徑，使得節點檢測到路徑變差時，可迅速切換到最佳路徑，分組丟棄概率降低，從而網絡整體丟包率降低。

從表2可看出，總體而言，隨著惡意節點比例的增加，收斂時間變長，速度變慢。原因在于，惡意節點的加入導致MANET節點對正常/惡意節點產生誤判，節點需重新發送測試分組以確定節點類型，判定時間延長，路徑選擇時間增加，算法收斂速度降低。同理，網絡節點數越多，算法對節點類型的判定時間越長，同時節點獲得網絡拓撲信息的時間變長，路徑選擇復雜度增加，算法收斂速度降低。與圖5、圖6相比，Throughput和Loss穩定點并不是收斂點，可能原因在于其它鏈路綜合Throughput和Loss與平均值是一致的，獲得最優安全路徑后保持性能指標恒定。此外惡意節點比例0～20%遞增時，LAWOA收斂時間比TQR和WOA對應值低5%～15%。其原因在于LA算法將搜索域分為male和female兩部分，各部分能夠分別識別各自域內的惡意節點，但并非速率減半，因為LA算法還要實現域間整合，同樣需要一定時間，因此收斂時間提升，并非效率加倍。

5 結束語

本文針對路由協議安全問題，提出一種安全路由協議模型，引入5種安全定量參數，設計對應的多維目標優化函數，并基于WOA和LA提出相應的優化算法，通過吞吐量和丟包率驗證了優化模型的性能。但是仍存在以下不足：①網絡規模有待增加；②高速移動環境中的協議安全性能尚未驗證；③網絡長期特性尚未討論；④最優路徑轉換時間尚缺少定量分析。后期將對以上問題展開進一步研究。