端到端時延下網(wǎng)絡(luò)多路徑負載均衡算法仿真

蘇富林，馮桂蓮

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

1 引言

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

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

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

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

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

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

2.1 路由模塊

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

2.2 大象流檢測

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

(1)

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

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

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

(2)

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

umax=max{ul}

(3)

(4)

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

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

(5)

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

(6)

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

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

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

(7)

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

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

(8)

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

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

(9)

2.4 計算決策模塊

2.4.1 興趣擴散

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

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

(10)

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

根據(jù)節(jié)點剩余能量完成興趣消息中energy域的更新，消息包完成更新后通過鏈路傳輸?shù)骄W(wǎng)絡(luò)的鄰居節(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ù)包。為了記錄傳輸路徑對應(yīng)的帶寬瓶頸和能量瓶頸，在探測數(shù)據(jù)包中設(shè)置minband域和minenergy域，minband域和minenergy域在網(wǎng)絡(luò)中的初始化處理可通過源節(jié)點完成，處理時需要利用鄰居節(jié)點在網(wǎng)絡(luò)中的帶寬以及源節(jié)點自身存儲的能量，在下述規(guī)則的基礎(chǔ)上使螞蟻自身攜帶的探測數(shù)據(jù)包傳輸?shù)骄W(wǎng)絡(luò)的任意中繼節(jié)點vi中：

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

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

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

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

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

2.4.3 路徑加強與負載均衡

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

τ(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)絡(luò)中的負載分配權(quán)重，以此實驗網(wǎng)絡(luò)多路徑的負載均衡，具體過程如下：

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

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

(12)

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

3 實驗與分析

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

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

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

1)端到端時延

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

圖2 端到端時延測試結(jié)果

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

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

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

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

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

3)分組丟失率

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

表1 分組丟失率測試結(jié)果

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

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

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

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

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

4 結(jié)束語

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