基于復雜網絡的不同路由策略下交通流驅動的流行病傳播

張永強，李爽，馬金龍

(河北科技大學信息科學與工程學院，石家莊 050018)

流行病伴隨著人類社會的發展，如SARS、中東呼吸綜合征等尤其新型冠狀肺炎，超過200個國家和地區先后出現疫情，表現出大流行特征[1]。由此可見流行病嚴重地威脅著人類的生命與安全，給人類社會造成了極大的危害。

大多數經典的流行病傳播模型都未考慮交通流的驅動，假設如下：在每一個時間步，每個節點的傳染性與該節點的度成正比[2]，即被感染的節點會以相等的概率將流行病傳播到其所有鄰居節點。然而，對于真實的網絡，交通流是影響流行病傳播的重要因素。例如，在全球航空網絡中，如果人們沒有在城市之間進行相關的旅行活動，流行病就不可能在不同的地理區域之間傳播[3]。在社交網絡中，如果沒有蚊蟲叮咬，典型的登革熱流行病就不會在人群中傳播[4]。在上述傳播過程中，網絡中節點的傳染性與節點度沒有直接關系，而與交通流有關。這種耦合的傳播過程被稱為基于交通流的流行病傳播[5]。近年來，復雜網絡理論和路由算法被廣泛應用于交通運輸網絡[6-7]上和節點的能耗問題[8-9]中，而針對交通流驅動的流行病傳播動力學的研究相對較少。

Meloni等[10]提出了基于交通流的易感-感染-易感(susceptible-infected-susceptible，SIS)流行病傳播模型，發現流行病閾值不再取決于節點的度，而是直接取決于交通流。王亞奇等[11]在基于交通流的易感-感染(susceptible-infected，SI)流行病傳播模型上提出了一種改進的熟人免疫機理，結果表明：對網絡實施目標免疫能夠有效抑制流行病的傳播。Yang等[12-13]觀察到可以通過本地路由策略和有效路由協議策略控制流行病的傳播。Yang等[14-15]提出了一種通過去除網絡中部分邊來控制基于交通流的流行病傳播的方法，并研究了冪律度分布對基于交通流的流行病傳播的影響。鄭國慶等[16]在兩層星型網絡上建立了一個新的有效度流行病模型，研究發現切斷邊界與中心的傳播途徑以及免疫中心節點對降低發病率最有效。Chen等[17]在交通流驅動的流行病傳播上研究了異質感染率的影響，發現當感染率與節點度呈負相關時，可以有效地抑制流行病的蔓延。Jing等[18]研究了交通流分配策略對多層網絡中流行病傳播的影響，發現通過調整某一層的路由分配和增加某一層的平均連通性都可以有效地抑制流行病的傳播。多重結構[19-21]對流行病傳播的影響也開始受到關注。

研究表明，網絡的結構特征[14,16,19-21]和交通流的路由策略[12-13,18]都會影響流行病的傳播。其中，改變路由策略不需要對網絡拓撲結構進行重構，相比于改變網絡的結構特征成本較低、使用方便。鑒于此，研究不同的路由策略對基于交通流的流行病傳播動力學的影響。

1 模型

1.1 網絡模型

由于很多真實網絡(如互聯網、電話網絡和運輸網絡)具有無標度特性[22]，因此使用Barabási-Albert(BA)模型[23]來生成網絡模型。BA無標度網絡模型的生成算法步驟如下。

步驟1初始網絡。給定m0個原始節點，m0個節點可以是孤立的，也可以是全連通的。

步驟2增長網絡。每個時間步內都有一個具有m條邊的新節點加入網絡中，其中m≤m0。

步驟3連接規則。每個增加的新節點連接到已有節點w的概率與節點w的度成正比。

(1)

圖1 BA無標度網絡的演化過程

1.2 基于交通流的SI流行病傳播模型

以SI模型[24]為研究對象，研究基于交通流的流行病傳播過程。基于交通流的SI流行病傳播模型與傳統的SI流行病傳播模型不同：節點被感染的概率不僅與流行病的傳染率β有關，還與網絡中的交通流量有關。在基于交通流的流行病傳播模型中，數據包傳輸過程如下：在規模為N的網絡中，每個時間步產生λN個新數據包，它們隨機選擇源節點和目的節點。數據包存儲在節點隊列中，隊列采用先進先出(first-in-first-out)的原則，節點接受和轉發數據包的能力不受限制。數據包按照既定的路由策略進行傳輸，一旦到達目的節點，就會從網絡中移除。當易感節點收到來自感染節點的數據包時，該節點被感染的概率為β。最初，通常假設一部分節點受到感染。圖2描述了基于交通流的SI流行病傳播模型的傳播過程。

圖2 基于交通流的SI流行病傳播模型的傳播過程

由于無標度網絡中每個節點的度并不相同，因此度為v的節點組中被感染節點的密度為ρv(t)=Iv(t)/Nv。其中，Nv是度為v的節點數量，Iv(t)是t時刻度為v的被感染節點數量。根據平均場理論[25]，得出基于交通流的SI流行病傳播模型的反應速率方程為[26]

(2)

在不考慮節點之間的度相關性和約定P(v)為節點度分布函數的情況下，Θ(t)的表達式為

(3)

在初始傳播階段，感染節點所占比例較小，因此可以忽略感染節點密度(ρ)平方項的時間復雜度O(ρ2)，將式(2)簡化為

(4)

將式(3)代入式(4)得

(5)

由式(5)可得

Θ(t)=Θ(0)e1/τ

(6)

(7)

式(7)中：τ為流行病爆發的時間尺度。

由式(7)可知，τ與傳染率β和每個時間步生成的數據包數目λN成反比。

2 策略分析與仿真

分析3種路由策略對基于交通流的流行病傳播動力學的影響，路由策略包括內容如下。

(1)有效路徑(efficient path, EP)路由策略[27]。研究發現網絡中度值大的節點容易成為擁塞的瓶頸節點，所以將網絡中節點的度值作為路由選擇的代價函數。例如，從節點i到節點j的路徑為P(i→j):=i≡x1,x2,…,xn≡j，其代價函數為

(8)

式(8)中：k(xl)為節點xl的度；α為可調參數，α=1是EP路由策略的最優參數值。

(2)最短路徑(shortest path,SP)路由策略[28]。數據包選擇多條路徑中邊數最少的那一條路徑作為傳輸路徑。當式(8)中的α=0時，EP路由策略恢復為SP路由策略。

(3)概率路徑(probability path,PP)路由策略[29]。為了能夠更加有效的發揮中心節點傳輸數據包的能力，減少數據包在路由路徑上等待時間的概率，提出了PP路由策略，可表示為

(9)

使路由函數R[α,P(i→j)]取得最大值的路徑就是概率路由路徑P*(i→j)。

(10)

然后，在BA無標度網絡上對不同路由策略下基于交通流的SI流行病傳播模型進行仿真實驗。設定BA網絡的平均度為=10，節點的處理能力為無窮大。在這種情況下，網絡中不會出現交通流擁塞。將初始感染節點的密度設置為ρ0=0.1。

圖3(a)、圖4(a)和圖5(a)分別展示了在N=400、1 200、2 000的網絡規模中，SP路由策略下感染節點密度ρ(t)與數據包生成率λ的對應關系。圖3(b)、圖4(b)和圖5(b)分別展示了在N=400、1 200、2 000的網絡規模中，PP路由策略下感染節點密度ρ(t)與數據包生成率λ的對應關系。圖3(c)、圖4(c)和圖5(c)分別展示了在N=400、1 200、2 000的網絡規模中，EP路由策略下感染節點密度ρ(t)與數據包生成率λ的對應關系。其中傳染率β=0.1。從圖3～圖5中可以看出，在這3種路由策略下，不同的網絡規模中，感染節點的密度ρ(t)都隨著數據包生成率λ的增加而增加。這是因為當網絡中傳輸的數據包數量增加時，就會把流行病傳播給更多的節點，這顯然與傳統的SI流行病傳播模型不同。該仿真結果證明了式(7)中的結論：在確定β和N的情況下，流行病的傳播隨著λ的增加而變快。因此，在流行病爆發時控制交通流量可以有效地提高流行病的爆發閾值，抑制流行病的傳播。

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

圖6(a)、圖7(a)和圖8(a)分別展示了在N=400、1 200、2 000的網絡規模中，SP路由策略下感染節點密度ρ(t)與傳染率β的對應關系。圖6(b)、圖7(b)和圖8(b)分別展示了在N=400、1 200、2 000的網絡規模中，PP路由策略下感染節點密度ρ(t)與傳染率β的對應關系。圖6(c)、圖7(c)和圖8(c)分別展示了在N=400、1 200、2 000的網絡規模中，EP路由策略下感染節點密度ρ(t)與傳染率β的對應關系。其中數據包生成率λ=0.1。從圖6～圖8中可以看出，在這3種路由策略下，不同的網絡規模中，感染節點的密度ρ(t)都隨著傳染率β的增加而增加。這說明流行病傳播不僅與交通流有關，還與流行病自身固有屬性有關。因此，在制定有關流行病傳播的防控策略時，要進行綜合考慮。該仿真結果驗證了式(7)中的結論：在確定λ和N的情況下，β的增加會導致流行病的傳播閾值降低。

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

表示感染節點密度的范圍是[0, 0.2)；表示感染節點密度的范圍是[0.2, 0.3)；表示感染節點密度的范圍是[0.3, 0.4)；表示感染節點密度的范圍是[0.4, 0.5)；表示感染節點密度的范圍是[0.5, 0.6)；表示感染節點密度的范圍是[0.6, 0.7)；表示感染節點密度的范圍是[0.7, 1]

圖9的仿真實驗結果(以N=1 200的網絡規模為例)證明了上述結論，可以看出，在SP路由策略、PP路由策略和EP路由策略中，EP路由策略下被感染的數據包在節點上的分布最均勻，即交通范圍更廣。而PP路由策略下被感染的數據包在節點上的分布最集中，即交通范圍更小。所以得出結論：相比于SP路由策略，PP路由策略會抑制流行病的傳播，而EP路由策略會加速流行病的傳播。

圖9 不同路由策略下被感染的數據包在節點上的分布情況

3 結論

基于交通流的流行病傳播與其數據包進行傳輸時采用的路由策略密切相關。研究了3種路由策略對基于交通流的流行病傳播的影響，發現相比于SP路由策略，PP路由策略可以有效地抑制流行病的傳播，而EP路由策略則會加速流行病的傳播，仿真結果在不同的網絡規模上具有魯棒性。除此之外，還發現在不同的路由策略下，減少交通流量和降低傳染率可以有效地抑制流行病的傳播。因此，當流行病爆發時，在交通流和傳染率一定的情況下，可以通過調整路由策略來抑制流行病的傳播。這些研究結果對在突發公共衛生事件下，交通管理部門有針對性地制定防控策略，保障基本民生，穩定經濟運行具有一定指導意義。