基于路徑權(quán)值的多信道負載均衡路由算法

馬少飛， 曲家慶， 嚴 鵬， 田 華

(1.上海無線電設(shè)備研究所, 上海 200090; 2.上海水文總站, 上海 200232)

基于路徑權(quán)值的多信道負載均衡路由算法

馬少飛1， 曲家慶1， 嚴 鵬1， 田 華2

(1.上海無線電設(shè)備研究所, 上海 200090; 2.上海水文總站, 上海 200232)

針對水文監(jiān)測系統(tǒng)無線Mesh網(wǎng)絡(luò)中傳輸數(shù)據(jù)流量大、路由節(jié)點固定的特點，提出基于路徑權(quán)值的多信道負載均衡路由算法，通過對每條鏈路容量進行預測，以Dijkstra準則選擇最優(yōu)路徑，達到對負載流量均衡分配、提高網(wǎng)絡(luò)吞吐量的目的。OPNET仿真結(jié)果表明：新算法使信道資源得到充分利用，比AODV算法網(wǎng)絡(luò)吞吐量提高了3倍，具有更小的傳輸延遲。

網(wǎng)絡(luò)； 負載均衡； 多信道

0 引言

智慧海洋工程以實現(xiàn)海洋資源共享、海洋活動協(xié)同，挖掘新需求，創(chuàng)造新價值，達到智慧經(jīng)略海洋為目的，要建設(shè)智慧海洋必須以完善的海洋信息采集與傳輸體系為基礎(chǔ)，《長江口海洋環(huán)境多模監(jiān)測網(wǎng)關(guān)鍵技術(shù)研究與應用示范》課題，采用多模通信技術(shù)，在海上移動網(wǎng)絡(luò)覆蓋不到的區(qū)域建立無線Mesh專網(wǎng)，滿足視頻、圖像等大數(shù)據(jù)的可靠傳輸，通過無線Mesh專網(wǎng)與商用網(wǎng)絡(luò)的無縫融合，為近海海域提供Internet接入服務，實現(xiàn)長江口海洋環(huán)境監(jiān)測數(shù)據(jù)傳輸。

針對無線Mesh網(wǎng)絡(luò)的研究涵蓋了從應用層到物理層的各個層次[1-2]，主要是根據(jù)網(wǎng)絡(luò)的實際應用設(shè)計合適的協(xié)議和算法，其路由算法大多沿用Ad hoc網(wǎng)絡(luò)協(xié)議[3]，如DSR[4]，AODV[1，5]，DSDV等。文獻[4]和文獻[5]提出的AODV協(xié)議和DSR協(xié)議是兩種被廣泛應用的源發(fā)起按需路由協(xié)議，具有較低的路由開銷且實現(xiàn)簡單，但二者均以最小跳數(shù)作為路由判據(jù)，得到的往往不是最佳路由，其泛洪廣播占用了較大的無線信道帶寬，增加了分組的發(fā)送等待時延，在無線Mesh網(wǎng)絡(luò)中，節(jié)點通常是靜止的，由于AODV和DSR路由協(xié)議沒有考慮負載均衡的情況，當數(shù)據(jù)業(yè)務增大時，處于中心位置的節(jié)點就會發(fā)生擁堵。文獻[6]雖然考慮了負載均衡機制，但其網(wǎng)絡(luò)節(jié)點都處于單信道環(huán)境，無法發(fā)揮無線Mesh網(wǎng)絡(luò)多信道條件下的性能優(yōu)勢。

如果采用以上傳統(tǒng)算法作為長江口海洋環(huán)境監(jiān)測系統(tǒng)無線Mesh網(wǎng)絡(luò)的路由算法，將會面臨節(jié)點容量不足、視頻傳輸延遲大、數(shù)據(jù)傳輸速率低等問題，難以滿足系統(tǒng)需求。

本文根據(jù)海洋環(huán)境監(jiān)測系統(tǒng)傳輸數(shù)據(jù)量大、區(qū)域廣等特點，同時考慮了負載均衡和多信道的使用，提出了一種基于路徑權(quán)值的多信道負載均衡路由算法，以經(jīng)典的Dijkstra算法為節(jié)點選擇最優(yōu)路徑，提出了鏈路負載的預測方法，最后利用OPNET仿真平臺對AODV算法和新算法的性能進行了對比。結(jié)果證明，新算法比AODV算法網(wǎng)絡(luò)吞吐量提高了約三倍，且具有更小的傳輸延遲。

1 海洋環(huán)境監(jiān)測網(wǎng)

海洋環(huán)境監(jiān)測網(wǎng)是在海上無線Mesh專網(wǎng)，如圖1所示，每個觀測站是無線Mesh網(wǎng)絡(luò)中的一個節(jié)點，負責收集海洋環(huán)境數(shù)據(jù)終端的數(shù)據(jù)并將其通過無線Mesh網(wǎng)絡(luò)傳輸?shù)疥懮媳O(jiān)測中心。在網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)，每個無線Mesh網(wǎng)絡(luò)終端通過觀測站組成的網(wǎng)絡(luò)與其它終端通信，在陸上監(jiān)測中心建立無線Mesh網(wǎng)絡(luò)與Internet、移動網(wǎng)絡(luò)的網(wǎng)關(guān)，實現(xiàn)海上終端的上網(wǎng)功能。

圖1 海洋環(huán)境監(jiān)測網(wǎng)絡(luò)示意圖

多信道無線Mesh網(wǎng)絡(luò)主要包括無線路由器、無線接入路由器和網(wǎng)關(guān)三部分。無線路由器為傳輸數(shù)據(jù)選擇到監(jiān)測中心的最優(yōu)路徑；無線接入路由器具有路由功能的同時，還能提供無線提供接入服務；網(wǎng)關(guān)通過有線鏈路將Mesh網(wǎng)與Internet連接，為用戶提供寬帶接入服務。對于海上觀測站的無線Mesh網(wǎng)絡(luò)節(jié)點來說，只需要無線路由器和無線接入路由器。

2 算法研究

2.1路徑權(quán)值分配

無線Mesh網(wǎng)絡(luò)節(jié)點傳輸數(shù)據(jù)時有多條路徑可供選擇，本文以Dijkstra算法作為選擇最優(yōu)路徑的準則。定義一條路徑的權(quán)值W為該路徑上所有鏈路的最小權(quán)值，表示該路徑的帶寬受到其瓶頸鏈路的限制，所以在路徑選擇時，節(jié)點優(yōu)先選擇權(quán)值最大的路徑。

對網(wǎng)絡(luò)中各個鏈路的負載φ視為已知，得到鏈路i的容量為

(1)

式中：B為信道帶寬；In(i)表示鏈路i干擾范圍內(nèi)的所有鏈路?？梢钥闯?，鏈路i上的負載越大，它所能分享到的信道帶寬就越大；反之在鏈路i干擾范圍內(nèi)其他鏈路的負載越大，它分享到的帶寬就越小，式(1)表示鏈路i的帶寬占有情況。用φ′(i)表示鏈路i的當前負載，得到鏈路i的剩余容量為

(2)

在選擇路由時，將W(i)作為每個鏈路的權(quán)值。

2.2負載均衡原理

當網(wǎng)絡(luò)中的節(jié)點數(shù)目增加或數(shù)據(jù)業(yè)務量增大時，網(wǎng)絡(luò)吞吐量及性能受到限制，負載均衡的目的是將網(wǎng)絡(luò)負載分配到網(wǎng)絡(luò)中有足夠帶寬資源的節(jié)點，降低網(wǎng)絡(luò)擁塞的可能性，提高網(wǎng)絡(luò)吞吐量，減小數(shù)據(jù)傳輸延遲[6-8]。

a) 為每個負載依次選擇第1條最佳路；

b) 再為其選擇第2條最佳路由；

……

m) 找到第M條路由或者不存在可用的路由。

把N×M次的尋路操作稱為一輪尋路，得到負載Tn的第m條期望負載：

(3)

(4)

(5)

一輪尋路結(jié)束后，每個鏈路上的負載都得到了準確的預測，利用新的預測結(jié)果計算各個鏈路的容量C，就可能找到更優(yōu)的信道分配和路由方案，整個路由算法流程如圖2所示。

圖2 算法流程圖

3 實驗結(jié)果與分析

在OPNET仿真平臺中，對文獻[3]的AODV算法與本文提出的算法進行了仿真，驗證本文算法性能。仿真場景為25個節(jié)點隨機均勻分布在網(wǎng)絡(luò)當中，每個節(jié)點配有兩塊無線網(wǎng)卡，整個網(wǎng)絡(luò)共有12個不同信道，每個信道帶寬為11 Mbps，在網(wǎng)絡(luò)中隨機選擇20對節(jié)點為它們分配不同的CBR UDP負載，數(shù)據(jù)流從第10 s依次開始到100 s結(jié)束。定義網(wǎng)絡(luò)在時刻t的吞吐量

(6)

式中：N為網(wǎng)絡(luò)中端到端鏈路的個數(shù)；Ti(t)為第i條鏈路在時刻t內(nèi)收到的所有數(shù)據(jù)比特數(shù)。定義第i條鏈路的平均延遲

(7)

式中：K為該鏈路i在仿真時間內(nèi)收到的數(shù)據(jù)包總數(shù)；Ti(t)為該鏈路上的第k包的延遲，其中包括排隊等待時間和數(shù)據(jù)傳輸時間。

圖3是網(wǎng)絡(luò)吞吐量隨時間關(guān)系，橫軸表示時間，縱軸表示網(wǎng)絡(luò)吞吐量(Mbps)，AODV算法的吞吐量大致在4 Mbps左右趨于飽和，當網(wǎng)絡(luò)飽和時無線節(jié)點將處于避退狀態(tài)，吞吐量將會降低。

圖3 網(wǎng)絡(luò)吞吐量

本文的新算法采用多信道的網(wǎng)絡(luò)將干擾劃分到了不同的信道上，大大減少了通信碰撞概率，可以使網(wǎng)絡(luò)整體吞吐量提高3倍以上。同時由于新算法在選路時考慮了負載的平衡，并將優(yōu)化后的路徑信息反饋給信道進行重新分配，從而使網(wǎng)絡(luò)中的信道資源得到更充分的利用。圖4是20個節(jié)點的平均傳輸延遲，為了能直觀地分析延遲狀況，將不存在通路的傳輸延遲統(tǒng)一設(shè)為2 s，可以看到，對于采用AODV算法的單信道網(wǎng)絡(luò)，第6個和第12個路徑由于沒有可用路徑而不能相互通信，可見單信道無線網(wǎng)絡(luò)的實際容量是很低的，而本文提出的算法的網(wǎng)絡(luò)是多信道網(wǎng)絡(luò)，這20個節(jié)點都能正常傳輸，而且采用新算法比AODV算法具有更小的延遲，且算法的最大延遲不超過0.35 s。

圖4 節(jié)點傳輸延遲

4 結(jié)論

本文的路由算法采用Dijkstra算法選擇最優(yōu) 路徑，并提出負載平衡路由策略，同時采用多信道網(wǎng)絡(luò)傳輸，將網(wǎng)絡(luò)負載均衡地分配到高質(zhì)量的路徑上。與AODV算法相比，網(wǎng)絡(luò)吞吐量提高了3倍；具有更小的數(shù)據(jù)傳輸延遲；由于是多信道網(wǎng)絡(luò)，即使有20個節(jié)點時也能正常傳輸?；谒惴ǖ膬?yōu)點，采用本文算法的無線Mesh網(wǎng)絡(luò)能夠容納更多節(jié)點，數(shù)據(jù)傳輸速率更高，時延更短，為長江口海洋環(huán)境監(jiān)測系統(tǒng)傳輸視頻、圖像等大數(shù)據(jù)提供了有力的保證。此外，Dijkstra算法雖是最優(yōu)路徑選擇的經(jīng)典算法，但其在時間效率和空間效率等方面存在嚴重不足，這也是本文今后需要研究改進的方向。

[1] 王月姣.無線Mesh網(wǎng)絡(luò)路由協(xié)議研究[D].上海：上海交通大學, 2008： 4-13.

[2] 沈強,方旭明,宋文.無線Mesh網(wǎng)絡(luò)路由協(xié)議研究[J] 數(shù)據(jù)通信, 2005,(4): 30-33.

[3] Bruno R, Conti M, Gregori E. Mesh Networks: Commodity Multihop Ad Hoc Networks[J]. IEEE Communications Magazine, 2005, 43(3): 123-131.

[4] Majumder K, Sarkar S.K. Performance Analysis of AODV and DSR Routing Protocols in Hybrid Network Scenario[C]. India Conference (INDICON), Annual IEEE, 2009: 1-4.

[5] Perkins C, Belding-Royer E, Das S. Ad Hoc On-demand Distance Vector (AODV) Routing[R]. IETF RFC 3561, 2003(3): 3-6.

[6] 王穎. 無線Mesh網(wǎng)絡(luò)中負載均衡機制的研究[D].長沙：湖南大學, 2010: 7-20.

[7] 陳祥.無線自組織網(wǎng)絡(luò)負載均衡路由研究[D].成都：電子科技大學, 2007: 16-19.

[8] Manikantan D, Shila, Anjali T. Load-aware Traffic Engineering for Mesh Networks[C]. Proceedings of 16th International Conference on Computer Communications and Networks. IEEE press, 2007: 1701-1704.

AMulti-channelLoadBalanceRoutingAlgorithmBasedonPathWeigh

MAShao-fei1,QUJia-qing1,YANGPeng1,TIANHua2

(1.Shanghai Radio Equipment Rasearch Institude, Shanghai 200090, China;2.Shanghai Hydrological Sation, Shanghai 200232, China)

For the characteristics of heavy traffic and fixed router node in wireless mesh network of hydrological monitoring system, a multi-channel load balance routing algorithm based on path weight is proposed. By forecasting capacity of each link and choosing the optimal path with Dijkstra criterion, the load traffic is balanced and network throughput is increased. The simulation result on OPNET shows that the new algorithm is three times higher than AODV for network throughput, has smaller propagation delay and makes full use of the channel resources.

network; load balance; multi channel

1671-0576(2017)02-0056-04

2016-11-23

馬少飛(1991-)，男，碩士，主要從事信息與信號處理技術(shù)研究。

TN911.7

A