蘇富林，馮桂蓮

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

1 引言

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

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

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

2 網(wǎng)絡多路徑負載均衡算法

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

圖1 網(wǎng)絡多路徑負載均衡機制

2.1 路由模塊

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

2.2 大象流檢測

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

(1)

式中，tth代表的是數(shù)據(jù)流平均大小的倍數(shù)。

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

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

(2)

根據(jù)上式計算結果，通過下式確定網(wǎng)絡的最大鏈路利用率umax

umax=max{ul}

(3)

(4)

2.3 網(wǎng)絡監(jiān)聽模塊

網(wǎng)絡監(jiān)聽模塊的主要任務是監(jiān)聽各節(jié)點在網(wǎng)絡中的實時信息。

(5)

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

(6)

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

3)網(wǎng)絡流接收率GA(t)

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

(7)

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

4)網(wǎng)絡帶寬占用率BP

(8)

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

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

(9)

2.4 計算決策模塊

2.4.1 興趣擴散

經(jīng)調查發(fā)現(xiàn)，由于大象流中包含了大量的數(shù)據(jù)，因此，在傳輸過程中容易造成網(wǎng)絡擁塞現(xiàn)象，在計算決策模塊中通過蟻群優(yōu)化算法[10，11]合理地調度大象流，避免網(wǎng)絡出現(xiàn)擁塞現(xiàn)象，實現(xiàn)多路徑的負載均衡。

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

(10)

式中，dji代表的是節(jié)點j和節(jié)點i在網(wǎng)絡中的路徑距離；ri代表的是節(jié)點i在網(wǎng)絡中的剩余能量。

根據(jù)節(jié)點剩余能量完成興趣消息中energy域的更新，消息包完成更新后通過鏈路傳輸?shù)骄W(wǎng)絡的鄰居節(jié)點中，停止傳播興趣消息的條件是興趣信息經(jīng)過多個節(jié)點最終傳輸?shù)皆垂?jié)點中。

2.4.2 多路徑建立

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

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

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

3)當鄰居節(jié)點在網(wǎng)絡中無法傳輸探測數(shù)據(jù)包時，返回上一步重新選擇可以傳輸探測數(shù)據(jù)包的鄰居節(jié)點。

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

根據(jù)上述過程，在網(wǎng)絡中獲得用于數(shù)據(jù)傳輸?shù)亩鄺l路徑。

2.4.3 路徑加強與負載均衡

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

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

(11)

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

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

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

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

(12)

3)根據(jù)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，根據(jù)上述過程獲得節(jié)點能量在網(wǎng)絡中對應的有效權重Er，同理獲得B、D在網(wǎng)絡多路徑負載分配過程中的有效權重Eb、Ed，結合有效權重Er、Eb、Ed計算路徑在網(wǎng)絡多路徑負載分配中的加強權重，根據(jù)計算結果為M條路徑分配負載，實現(xiàn)網(wǎng)路多路徑負載均衡，這種負載分配方式可以有效地避免節(jié)點在網(wǎng)絡中過早死亡。

3 實驗與分析

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

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

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

1)端到端時延

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

圖2 端到端時延測試結果

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

2)網(wǎng)絡能量消耗

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

圖3 網(wǎng)絡能量消耗測試結果

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

3)分組丟失率

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

表1 分組丟失率測試結果

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

4)網(wǎng)絡生命周期

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

圖4 網(wǎng)絡生命周期測試結果

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

4 結束語

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