基于復雜網絡的計算機病毒傳播路由算法

摘要：信息安全就是國家安全，為降低計算機病毒在計算機網絡中的傳播速度，提高計算機網絡的安全性，文章提出了基于復雜網絡的計算機病毒傳播路由算法。首先構建基于復雜網絡的計算機網絡模型，確定計算機病毒傳播模型。其次改進靜態路由協議和動態路由協議，在兩種協議的基礎上設置鄰居節點閾值，提出基于復雜網絡的計算機病毒傳播路由算法，將該算法采用BA網絡模型進行對比實驗，驗證其算法的可行性和有效性。實驗結果表明，與改進之前的算法相比，文中提出的基于復雜網絡的計算機病毒傳播路由算法，極大地降低了病毒的傳播速度，驗證了算法的可行性和有效性。

關鍵詞：復雜網絡；計算機病毒；路由策略；網絡安全

Computer Virus Propagation Routing Algorithm Based on Complex Network

WU Jietao

（Jinzhong Vocational and technical College， Jinzhong 030600， China）

Abstract： Information security is national security，in order to reduce the propagation speed of computer virus in computer network， improve the security of computer network， this paper presents the research of computer virus propagation routing algorithm based on complex network. Firstly， a computer network model based on complex network is constructed to determine the computer virus propagation model. Secondly， we improve the static routing protocol and dynamic routing protocol， set the neighbor node threshold on the basis of the two protocols， and propose a computer virus transmission routing algorithm based on complex network. The feasibility and effectiveness of the proposed algorithm are verified by comparative experiments in BA network model. The experimental results show that compared with the static routing protocol and dynamic routing protocol before the improved algorithm， the algorithm greatly reduces the virus transmission speed， and verifies the feasibility and effectiveness of the algorithm

Key words： complex network; computer virus; routing policy; network security

1" "研究背景

在日常生活中存在著各種各樣的網絡，網絡給人們的生活帶來了諸多便利。復雜網絡作為一種研究工具，被廣泛應用在生活實踐和科學研究中。借助復雜網絡工具能夠更好地指導和優化真實的網絡，復雜網絡中的節點度、出度、入度、平均度等理論被廣泛地用于解決各種復雜問題。在計算機網絡中，路由策略是數據包能夠快速到達目的地的有效方式，路由策略能夠實現網絡中更高的交通容量，實現高質量的數據包傳輸，避免網絡擁塞蔓延。設計有效的路由策略，優化網絡結構，對有限的網絡資源如節點的傳送能力、鏈路的帶寬等進行重新分配。

利用復雜網絡工具優化計算機網絡，有效提升網絡傳輸容量的路由策略主要是通過優化網絡中的傳輸路徑來實現的。路由策略[1]有靜態路由策略、動態路由策略、默認路由策略、負載均衡路由策略等。本地路由策略中網絡節點只有鄰居節點的信息，如本地靜態路由、本地動態路由和局部信息路由策略。還有一類策略是高效路徑策略、全局動態路由策略和最短路由策略。最短路徑路由策略[2]會選擇通過hub節點進行傳輸，從而可能導致網絡擁塞。

計算機病毒具有較強的傳播能力，并且能夠破壞計算機功能或者破壞數據[3]。在文獻[4]中提出易感者-被感染者-易感者模型集成到最短路由協議中，流行病可以通過數據包的傳輸在節點之間傳播。在每個時間步長，如果一個敏感節點從其感受的鄰居節點接收到新的數據包，那么它可能會被感染。Phys等人[5]中提出通過改變靜態本地路由和局部路由策略中的最優路徑來緩解病毒的流行傳播，這嚴重影響了網絡流量傳播。符航[6]提出通過切斷網絡中的一些邊緣來抑制交通樞紐中的流行病傳播。鄭文萍[7]表明，網絡的傳輸容量和網絡的最大節點介數有關，網絡中最大節點介數越大[8]，網絡的傳輸容量越低。然而，以上研究雖然減少了計算機病毒的傳播，但是也降低了計算機網絡的傳輸容量。

在不影響計算機網絡傳輸容量的基礎上，本算法首先利用復雜網絡工具構建計算機網絡模型；其次基于計算機網絡模型，改進靜態路由策略和動態路由策略，提出了基于復雜網絡的計算機病毒傳播路由算法降低計算機病毒在計算機網絡中的傳播；最后在BA無標度網絡模型中，通過對比實驗，驗證了算法的可行性和有效性。

2" "基于本地路由協議的計算機病毒消除算法研究

2.1 基于復雜網絡的計算機網絡模型

本文基于復雜網絡構建計算機網絡模型G，將主機或路由器抽象為節點N，將節點之間能夠傳輸數據包的路徑抽象為邊E。節點N既可以生成數據包，又可以轉發數據包。在一個時間步長中，節點會隨機產生R個數據包，這些數據包的源和目的是隨機選擇的。根據所選的本地路由協議[1]，每個節點最多可以向它的近鄰居節點發送C個數據包（C的取值根據具體網絡進行選取）。數據包可能通過路由策略發送給下一跳主機，當數據包傳達到目的地節點時，數據包會從目的節點中刪除，不進行二次發送。

節點的度[9]是指在計算機網絡模型中，其他節點和該節點連接的數量。節點的度決定著節點的重要程度，在計算機網絡模型中，節點的出度表示主機向其他主機或發送數據包的個數，節點的入度表示主機接收其他主機發送數據包的個數。

本算法采用易感染（SI）模型來觀察病毒在不同路由協議下的傳播情況。一個節點中存在數據包被感染被定義為受感染點節點。在易感節點中，所有的數據包都未被感染。在每個單位時間內，如果一個易感染節點從受感染的鄰居節點收到受感染的數據包，則該節點被感染的概率為β。

2.2 路由策略

在靜態路由策略[1]中，一個節點將數據包發送到目的節點，首先遍歷該節點的鄰居節點，如果目的節點在其鄰居節點中，則將數據包直接發送到目的節點，否則根據節點優先概率轉發到次鄰居節點（次鄰居節點指一個節點的鄰居節點的鄰居節點），節點的優先概率計算公式如式（1）：

（1）

在動態路由策略[1]中，依據節點的度和鄰居節點的度，其中源節點和目的節點之間的路徑確定如下公式：

（2）

2.3" 基于復雜網絡的計算機病毒傳播路由算法

依據靜態路由策略和動態路由策略，提出基于復雜網絡的計算機病毒傳播路由算法。由于靜態路由策略和動態路由策略中迂回和分組的盲目傳輸，因此數據包被盲目地傳輸到鄰居節點，而沒有考慮到數據包可能離目的地很近，導致路徑長度增大以及和更多的計算機病毒在整個網絡中傳播。為了限制本地協議中的迂回和減少數據包傳播路徑長度，依據復雜網絡中的度以及次近鄰節點集合改進靜態路由策略和動態路由策略，提出基于復雜網絡的計算機病毒傳播路由算法如下。

（1）當一個節點收到一個新的數據包時，首先在鄰居節點中搜索目的地。如果存在，則將數據包發送給鄰居節點。

（2）如果不存在，從次近鄰鄰居節點中搜索目的地。設置一個閾值s+t，搜索深度不得超過閾值，且次鄰居節點度不得超過鄰居節點。如果在次近鄰節點找到目的地，則將報文發送到這個下一跳鄰居節點。s的取值依據整個網絡的平均度。

（3）如果采用以上步驟仍然無法送達，則設置t的值，但是t值不超過s，遍歷次近鄰鄰居節點，尋找目的地。

（4）如果采用以上步驟都不滿足，則根據選擇的本地路由協議發送數據報。

節點度越高，通過該節點的數據包越多，該節點感染的概率越高，計算機病毒的傳播范圍越大。為降低計算機病毒的傳播，本算法在路由選擇協議中，通過設置次鄰居節點和搜索閾值，通過控制次鄰居節點的搜索閾值，使得數據包傳輸避開度高的鄰居節點，從而降低計算機病毒的傳播。

3" "實驗

本算法是基于復雜網絡的計算機網絡模型實現的，由于復雜網絡工具抽象的計算機網絡模型與BA無標度網絡特征十分相似，并且為了避免計算機病毒對實際網絡造成傷害，因此使用BA無標度網絡模型模擬來進行實驗分析。本文利用Python語言生成BA無標度網絡模型，該網絡度分布遵循冪律分布。

BA無標度網絡有兩種生產機制：成長機制和優先依戀機制。首先從少量個完全連接節點開始，然后整個網絡節點數量隨著后期增加新的節點而增加。每個新節點優先連接到m（）個舊節點，連接到現有節點i的概率與速度成正比。BA隨機網絡會生成少量度比較大的節點，以及大量節點度數小的節點。如圖1（a）所示是使用Gephi工具繪制的BA無標度網絡模型圖。該網絡模型是N=500且平均度k=4.875的網絡，圖1（b）所示是BA網絡模型的平均度分布圖。

圖2（a）和圖2（b）分別顯示了本地靜態路由策略和動態路由協議兩種不同協議下，不同感染率β值下感染節點隨時間的變化情況。從圖中可知β=0.2時，是理想狀態下的傳播感染率，有利于我們觀察計算機病毒的傳播速度。從兩張圖中可以看出計算機病毒的傳播速度非常快，表明計算機病毒具有很高的敏感性。

如圖3（a）和圖3（b）所示，將基于復雜網絡的計算機病毒傳播路由算法分別應用于本地靜態路由協議策略和本地動態路由協議策略中，不論是圖3（a）還是圖3（b），都明顯看到計算機病毒在網絡模型中傳播速度大幅度減小。這是因為計算機病毒通過在相鄰節點中搜索的數據包目的地減少，同時設置閾值，數據包被強制避開負載較高的節點，進而減小了計算機病毒在網絡模型上的傳播速度以及傳播范圍。

圖3（a）和圖3（b）中顯示了隨著時間的變化，計算機病毒在計算機網絡模型中傳輸過程中，應用改進算法進行數據包的傳輸，感染節點數增加速率明顯減緩，節點感染所用的時間增加，表明計算機病毒在網絡模型中傳播速度明顯減小，說明了改進算法的有效性。對比圖3（a）和圖3（b）發現，改進算法應用在動態路由策略中的效果比在靜態路由算法中明顯，在不同的感染率下，采用改進動態路由算法感染速度明顯比采用改進靜態路由算法小。對比圖2（a）和

圖3（a）中發現，在計算機網絡模型中，使用改進算法進行數據包傳輸，80%的節點被感染所使用的時間明顯增加。綜上所述，通過與靜態路由策略和動態路由策略進行實驗對比，驗證了本文提出的基于復雜網絡的計算機病毒傳播路由算法的可行性和有效性。

4" "結束語

本文中研究了計算機病毒在靜態路由協議和動態路由協議下的傳播情況，對靜態路由和動態路由進行算法改進，提出了基于復雜網絡的計算機病毒傳播路由算法，并將其應用于構建的基于復雜網絡計算機網絡模型中，利用BA無標度網絡進行模擬實驗，驗證了計算機病毒感染數隨著時間的變化情況。對比實驗證明，通過該路由策略進行傳遞數據包，能夠減小計算機病毒在網絡模型中的傳播速度，保障計算機網絡安全，進而保障國家安全。

參考文獻

[1] 王靜，鄢鵬．計算機網絡路由優化策略研究[J]．計算機光盤軟件與應用，2015，18（02）：302-303.

[2] 魏金棟．復雜網絡路由策略及魯棒性研究[D]．石家莊：河北科技大學，2023.

[3] 羅旭航，祝清意，劉煜杭．兩類非線性WSI計算機病毒傳播模型[J]．復雜系統與復雜性科學，2023（12）：1-10.

[4] 趙勇．基于網絡攻擊的計算機病毒傳播模型的優化算法研究[J]．信息技術與信息化，2021（03）：140-142.

[5] Phys. Rev. E.Optimal transport on complex networks，2006，（74）：046106

[6] 符航．網絡中心度視角下的城市疫情風險研究[D]．廣州：暨南大學，2022.

[7] 鄭文萍，王丹，王杰．基于模塊性的檢測簇結構的圖聚類算法研究[J]．小型微型計算機系統，2016，37（07）：1618-1623.

[8] A.Ould Baba Alweimine.Local routing protocols performance for computer virus elimination in complex networks，Physica A： 2019，（536）.

[9] 王魯．復雜網絡拓撲結構分析與路由策略研究[D]．北京：北京郵電大學，2018

作者簡介：武結桃（1995-），女，碩士研究生，研究方向為復雜網絡、計算機網絡。