端到端時延下網絡多路徑負載均衡算法仿真

蘇富林，馮桂蓮

(1. 甘肅民族師范學院計算機科學系，甘肅 合作 747000；2. 青海民族大學物理與電子信息工程學院，青海 西寧 810007)

1 引言

傳感器節點通常由多個部分組成，其主要負責數據的傳輸與接收、節點供電和數據處理等工作[1]，傳感器節點在網絡中所占的空間較小，其電源供應能力、計算能力等都會受到約束，為了降低網絡能耗、延長網絡壽命，需要保證節點之間數據穩定、可靠地傳輸[2]，在此背景下，研究網絡多路徑負載均衡算法具有重要意義。

許紅亮[3]等人通過蜘蛛猴算法根據路徑信息計算鏈路空閑率，并將其作為路徑在網絡中的適應度值，根據計算結果評估路徑，并對路徑更新，將鏈路占用率最小作為指標選取最優轉發路徑，實現網絡多路徑負載均衡。該算法的端到端時延較長，且數據傳輸過程中的分組丟失率較高。呂翊[4]等人根據網絡前端結構特點構建路徑選取模型，計算路徑差分延遲和數據傳輸延遲，在粒子群優化算法的基礎上通過多級懲罰函數分配網絡負載，實現負載均衡，該算法的節點平均能耗較高，存在網絡能量消耗高的問題。李銳[5]等人根據節點特性，計算節點在網絡中的移動狀態概率和剩余能量，將鏈路質量最優作為目標，根據上述計算結果選取最優路徑，實現負載均衡，該算法的存活節點數量較少，網絡生命周期短。

為了解決上述算法中存在的問題，提出基于蟻群優化的網絡多路徑負載均衡算法。

2 網絡多路徑負載均衡算法

基于蟻群優化的網絡多路徑負載均衡算法主要在Floodlinght控制器中通過路由模塊、大象流檢測模塊、網絡監聽模塊和計算決策模塊實現網絡多路徑負載均衡，如圖1所示。

圖1 網絡多路徑負載均衡機制

2.1 路由模塊

數據中心網絡中的流可以分為大象流和老鼠流，通過路由模塊區分網絡中的大象流和老鼠流，確定轉發路徑，并在哈希散列的基礎上通過ECMP算法[6]調度老鼠流，在決策模塊中完成網絡大象流的調度。

2.2 大象流檢測

標記網絡中存在的大象流是調度的首要步驟，在大象流檢測過程中，用F={f1，f2，…，fx}表示鏈路中存在的大象流，可通過下式判斷網絡中存在的數據流是否為大象流

(1)

式中，tth代表的是數據流平均大小的倍數。

根據節點在網絡中構成的集合V={v1，v2，…，vn}以及鏈路構成的集合L組建圖G(V，L)，用于表示網絡的拓撲結構。

設ul代表的是鏈路利用率，其計算公式如下

(2)

根據上式計算結果，通過下式確定網絡的最大鏈路利用率umax

umax=max{ul}

(3)

(4)

2.3 網絡監聽模塊

網絡監聽模塊的主要任務是監聽各節點在網絡中的實時信息。

(5)

2)鏈路負載均衡度[7，8]，用n表示節點在網絡中的數量，設ZB(t)代表的是鏈路在當前網絡中的負載均衡程度，可通過下式計算得到

(6)

式中，lcij代表的是鏈路(i，j)在網絡中的帶寬；m描述的是網絡中鏈路的實際數量。

3)網絡流接收率GA(t)

GA(t)=gs(t)/gc(t)

(7)

式中，gc(t)代表的是總共發送的數據流；gs(t)代表的是接收到的數據流。

4)網絡帶寬占用率BP

(8)

式中，lpij代表的是鏈路在初始時刻的最大帶寬容量。

5)網絡吞吐量YR，描述的是網絡拓撲在網絡流時間無限長的情況下能夠發送成功的最大流數目[9]，其計算公式如下

(9)

2.4 計算決策模塊

2.4.1 興趣擴散

經調查發現，由于大象流中包含了大量的數據，因此，在傳輸過程中容易造成網絡擁塞現象，在計算決策模塊中通過蟻群優化算法[10，11]合理地調度大象流，避免網絡出現擁塞現象，實現多路徑的負載均衡。

目的節點vd在網絡中周期性地傳送興趣消息，興趣消息包可以采集節點在網絡中的剩余能量信息，通過格式interest=(type，interval，rect，timestamp，expiresat，energy)表示，將energy域增加到網絡多路徑負載均衡算法中，其主要目的是表示節點在網絡中的剩余能量。將鄰居節點vi內存在的興趣消息存儲到節點vj對應的梯度表中，鄰居節點vi的剩余能量均記錄在興趣消息中，在梯度表中添加啟發因子ιji，啟發因子ιji可通過下式計算得到

(10)

式中，dji代表的是節點j和節點i在網絡中的路徑距離；ri代表的是節點i在網絡中的剩余能量。

根據節點剩余能量完成興趣消息中energy域的更新，消息包完成更新后通過鏈路傳輸到網絡的鄰居節點中，停止傳播興趣消息的條件是興趣信息經過多個節點最終傳輸到源節點中。

2.4.2 多路徑建立

在源節點中，M只螞蟻獲取探測數據包，并將其傳輸到下一個節點中，用probe=(type，instance，location，intensity，confidence，timestamp，minband，minenergy)描述源節點中存在的探測數據包。為了記錄傳輸路徑對應的帶寬瓶頸和能量瓶頸，在探測數據包中設置minband域和minenergy域，minband域和minenergy域在網絡中的初始化處理可通過源節點完成，處理時需要利用鄰居節點在網絡中的帶寬以及源節點自身存儲的能量，在下述規則的基礎上使螞蟻自身攜帶的探測數據包傳輸到網絡的任意中繼節點vi中：

1)判斷螞蟻在前進過程中是否經過該節點，若經過該節點，終止前進；若沒有經過該節點，判斷下一個目的節點與當前節點之間的距離，選擇距離較近的節點作為螞蟻訪問的節點[12，13]。

2)獲取鏈路帶寬bij和節點vi的能量ri，針對探測數據包中存在的minenergy域和minband域，通過min(ri，minenergy)、min(bij，minband)完成更新。

3)當鄰居節點在網絡中無法傳輸探測數據包時，返回上一步重新選擇可以傳輸探測數據包的鄰居節點。

4)當梯度表中存在的鄰居節點在網絡中都無法傳輸探測數據包時，節點vi需要重新設置一個梯度表，刪除原始的梯度表，新設置的梯度表中不包含目前獲取的探測數據包內存在的信息。

根據上述過程，在網絡中獲得用于數據傳輸的多條路徑。

2.4.3 路徑加強與負載均衡

根據前向螞蟻建立的傳輸路徑，后向螞蟻可以返回到網絡的源節點中，設τ(i，j)代表的是全局信息素，設置信息素揮發程度ε，通過下式對τ(i，j)展開更新處理，獲得更新后的全局信息素τ(i，j)new，其主要目的是加強上述過程構建的路徑

τ(i，j)new←(1-ε)τ(i，j)old+ε[Δτ(i，j)+ηmaxτ(i，j)]

(11)

式中，τ(i，j)old代表的是原始全局信息素；η為引入的參數；Δτ(i，j)描述的是信息素在更新過程中產生的增量。

通過層次分析法[14，15]計算M條路徑在網絡中的負載分配權重，以此實驗網絡多路徑的負載均衡，具體過程如下：

1)根據接收的探測數據包，確定負載分配過程中的決策因子，即M條路徑對應的寬瓶頸向量B=(b1，b2，…，bM)T、傳輸延遲向量D=(d1，d2，…，dM)T和能量瓶頸向量R=(r1，r2，…，rM)T。

2)分析上述決策因子對網絡多條路徑負載分配產生的影響，遵循從大到小的順序對帶寬瓶頸?3、傳輸延遲?2和能量瓶頸?1排序，在此基礎上，構建比較矩陣Φ

(12)

3)根據B=(b1，b2，…，bM)T、D=(d1，d2，…，dM)T、R=(r1，r2，…，rM)T中存在的分量比值，在負載分配過程中建立對應的比較距離，以R=(r1，r2，…，rM)T為例，記φij=ri/rj，獲得向量R的比較矩陣Φr=(rij)M×M，根據上述過程獲得節點能量在網絡中對應的有效權重Er，同理獲得B、D在網絡多路徑負載分配過程中的有效權重Eb、Ed，結合有效權重Er、Eb、Ed計算路徑在網絡多路徑負載分配中的加強權重，根據計算結果為M條路徑分配負載，實現網路多路徑負載均衡，這種負載分配方式可以有效地避免節點在網絡中過早死亡。

3 實驗與分析

為了驗證所提算法的整體有效性，選用文獻[3]方法和文獻[4]方法作為對比算法，展開端到端時延、網絡能量消耗、分組丟失率和網絡生命周期測試。為了保證實驗的真實性和公平性，在MATLAB仿真軟件的支持下設置以下兩個仿真場景：

仿真場景1：將600個節點放置在600m×600m的區域內展開測試；

仿真場景2：將300個節點放置在800m×600m的區域內展開測試。

1)端到端時延

圖2為不同場景下所提算法、文獻[3]方法和文獻[4]方法的端到端時延測試結果。

圖2 端到端時延測試結果

由圖2可知，在不同仿真場景中，所提算法的端到端時延均低于其 它兩種方法，因為所提算法在螞蟻目的節點選擇過程中，選擇距離較近的節點作為下一跳節點，縮短了數據傳輸距離，進而降低了端到端時延。

2)網絡能量消耗

圖3為不同場景下所提算法、文獻[3]方法和文獻[4]方法的網絡能量消耗測試結果。

圖3 網絡能量消耗測試結果

由于仿真場景2的區域面積較大且節點數量少，仿真場景1的區域面積小且節點數量多，因此三種方法在仿真場景2中的節點平均能量消耗高于仿真場景1中的節點平均能量消耗，但所提算法在兩個仿真場景中的節點平均能量消耗均是最少的，表明所提算法的網絡能量消耗小。

3)分組丟失率

選取仿真場景1作為測試環境，測試所提算法、文獻[3]方法和文獻[4]方法的分組丟失率，分組丟失率越高，表明信息在傳輸路徑中丟失的數據越多，測試結果如表1所示。

表1 分組丟失率測試結果

由表1中的數據可知，所提算法的分組丟失率最低，其最低值僅為2.1%，表明所提算法在數據傳輸過程中可以保證數據的傳輸安全性和完整性。

4)網絡生命周期

將仿真場景2作為實驗環境，測試所提算法、文獻[3]方法和文獻[4]方法的網絡生命周期，測試結果如圖4所示。

圖4 網絡生命周期測試結果

存活節點數量與網絡生命周期之間成正比，當網絡中的存活節點較多時，網絡工作的時間就越長，即網絡生命周期越長，由圖4可知，在仿真測試的100s之前所提算法可保證節點全部存活，100s之后開始出現節點死亡，存活節點數量減少，但與其 它兩種方法相比，所提算法的存活節點數量較多，表明網絡生命周期長。

4 結束語

目前網絡多路徑負載均衡算法存在端到端時延長、網絡能量消耗大、分組丟失率高和網絡生命周期短的問題，提出基于蟻群優化的網絡多路徑負載均衡算法，該算法在網絡多路徑負載均衡過程中引入蟻群優化算法，妥善解決了目前算法中的弊端。