一種自適應(yīng)的負載均衡按需路由算法

劉軍帥,郝聚濤

(1.天津石油職業(yè)技術(shù)學(xué)院,天津 301607;2.上海理工大學(xué),上海 200093)

一種自適應(yīng)的負載均衡按需路由算法

劉軍帥1,郝聚濤2

(1.天津石油職業(yè)技術(shù)學(xué)院,天津 301607;2.上海理工大學(xué),上海 200093)

文章中,一種新的路由準則被引入到協(xié)議中,該準則用來從眾多的路徑中選擇負載最輕且剩余能量最大的路徑,用來提高分組傳遞率降低端到端時延。為了驗證算法的性能,對所提協(xié)議進行了全面的仿真研究。研究結(jié)果表明,文章所提協(xié)議在包投遞率和延遲性能方面均優(yōu)于現(xiàn)有的路由協(xié)議。

路由協(xié)議;負載均衡;移動自組織網(wǎng)絡(luò);能量感知路由

一、引言

移動自組網(wǎng)(Mobile Ad Hoc Netw orks,MAN ET)是由一組移動節(jié)點構(gòu)成的,不依賴于任何固定基礎(chǔ)設(shè)施的無線網(wǎng)絡(luò)[1]。處于無線傳輸范圍內(nèi)的節(jié)點可以直接通信,而相距較遠的節(jié)點則需要依靠中間節(jié)點的轉(zhuǎn)發(fā)進行通信。中間節(jié)點就充當(dāng)了路由器的角色。由于不需要固定基礎(chǔ)設(shè)施的支持,以及迅速部署的特點,Ad Hoc網(wǎng)絡(luò)非常適合通信基礎(chǔ)設(shè)施不存在或者無法正常使用的環(huán)境,其潛在的應(yīng)用領(lǐng)域非常廣泛,例如,軍事戰(zhàn)術(shù)網(wǎng),災(zāi)難救助,移動會議、傳感器網(wǎng)絡(luò)和個人域網(wǎng)等。Ad hoc網(wǎng)絡(luò)中,由于通信半徑的限制,網(wǎng)絡(luò)節(jié)點之間是通過多跳數(shù)據(jù)轉(zhuǎn)發(fā)機制進行數(shù)據(jù)交互的,需要路由協(xié)議完成分組轉(zhuǎn)發(fā)決策。與傳統(tǒng)路由協(xié)議相比,Ad hoc路由協(xié)議的設(shè)計面臨著網(wǎng)絡(luò)拓撲動態(tài)變化、帶寬受限、信道容量變化、移動終端有限的可用資源等新的問題和挑戰(zhàn)。為MAN ET設(shè)計一個高效的路由協(xié)議是非常重要的,需要智能策略來確定最小開銷的路由,以及保證路由具有很高的可擴展性。

在為數(shù)眾多的已有移動自組織網(wǎng)絡(luò)的路由協(xié)議中,動態(tài)源路由DSR[2,3]和AODV[4]是最為顯著的兩個代表。DSR利用源路由在移動自組織網(wǎng)絡(luò)中尋找源節(jié)點到目的節(jié)點的路由。這類先驗式路由,盡管每個數(shù)據(jù)分組都攜帶通往目的地的節(jié)點路徑上的各節(jié)點信息,但同時也增加了大量的信號傳輸開銷和能量消耗。由于帶寬和電池電量是稀有資源,這也給這類路由協(xié)議的很大的局限性。在AODV協(xié)議中,只要源節(jié)點需要發(fā)送數(shù)據(jù)便維護路由。如果源節(jié)點移動,或者源節(jié)點到目的節(jié)點中間的某個步驟變?yōu)椴豢傻竭_,路由發(fā)現(xiàn)過程便被重新發(fā)起。

然而,這些協(xié)議都沒有涉及到路由中的負載均衡問題。在實際應(yīng)用中,一些路由可能被擁塞,而另外一些則未被利用到。在這種情況下,部分節(jié)點將承擔(dān)過重的負載,網(wǎng)絡(luò)擁塞加劇,導(dǎo)致延遲增加、低包投遞率和高路由開銷等不滿意的后果,最終導(dǎo)致網(wǎng)絡(luò)性能降低。在負載均衡方面,目前文獻中的負載均衡方法可以被分為兩大類:多路徑方法和單路徑方法[5]。

在多徑路由方面,Yin和Lin提出了一種多徑負載均衡機制MALB,該機制通過循環(huán)調(diào)整每條路徑上的流量比例,達到最小化網(wǎng)絡(luò)端到端延遲的目的[6]。Wu和 Harms在兩條互不相較的路徑之間定義了一個系數(shù)作為分離路徑上節(jié)點間的連接數(shù)[7]。結(jié)果顯示,隨著系數(shù)增加,沿著路徑的時延也隨即增加。Zhang提出了一個多路徑源路由算法MSR[8],作為對DSR協(xié)議的擴展。MSR采用一種探測機制按需獲得動態(tài)路徑狀態(tài)。這種機制可以被用來刷新緩存中的信息,刪除陳舊路徑并及時發(fā)現(xiàn)新路徑。多路徑負載平衡問題就是尋求最優(yōu)解使得每條路徑上的流量最小。然而,在單路徑方法中,源節(jié)點和目的節(jié)點之間僅存在一條路徑。因此,在文獻中許多不同的負載均衡機制被提出。這些機制試圖引導(dǎo)數(shù)據(jù)包避開擁塞的路徑,以達到在網(wǎng)絡(luò)內(nèi)均衡負載的目的。例如,Zhu和Hassanein提出了一個新穎的路由協(xié)議稱為LBAR[9],在該協(xié)議中定義了一個新的路由準則為節(jié)點的活動性,用節(jié)點的活動性來表示節(jié)點的負載。在文獻[10]中,Lee和Riley也提出了一種機制,該機制給與負載過重的節(jié)點一自由,可以拒絕額外的通信通過它們,直到這種過載情況結(jié)束。Souihli和Frikha提出了將流量推向遠離網(wǎng)絡(luò)中心的機制以達到負載均衡的機制[11]。在該機制中使用了節(jié)點中心度作為路由準則。該機制提高了負載分布,使得網(wǎng)絡(luò)性能在平均時延和可靠性方面得到提升。

能量高效也是移動無線網(wǎng)絡(luò)重點關(guān)注的一個問題。由于多數(shù)移動節(jié)點是由電池供電,那么負載比較重的節(jié)點的電能可能被首先消耗完,并退出網(wǎng)絡(luò),導(dǎo)致網(wǎng)絡(luò)節(jié)點的減少,并引起完網(wǎng)絡(luò)的分割。此外,如果退出節(jié)點此時正處于某條通信鏈路中,那么可能導(dǎo)致鏈路的中端,從而引起路由發(fā)現(xiàn)開銷和包投遞延遲,同樣降低了網(wǎng)絡(luò)性能。

在文獻[12]中,作者研究發(fā)現(xiàn)多數(shù)最短路徑路由都要經(jīng)過網(wǎng)絡(luò)的中心,且節(jié)點越是接近網(wǎng)絡(luò)中心所擁有的路由表條目也越多?；谶@個觀察結(jié)果,Souihli提出了一個新的路由準則,采用路由表的大小來選擇路由。盡管這種負載均衡機制可以將數(shù)據(jù)流推向遠離網(wǎng)絡(luò)的中心,從而達到提高網(wǎng)絡(luò)性能的目的,但是也并非非常完美。負載非常重的應(yīng)用場景中,所有節(jié)點可能都想與其它節(jié)點進行通信,因此每個節(jié)點所擁有的路由表大小基本接近,那么在這種情況下,靠近網(wǎng)絡(luò)中心的節(jié)點仍然是負載最重的節(jié)點,成為整個網(wǎng)絡(luò)的瓶頸,制約網(wǎng)絡(luò)性能。

基于上面的分析,在文本中我們提出了一個按需負載均衡的路由協(xié)議,在該協(xié)議中一個兼顧節(jié)點能量和負載的路由準則被提出,可以有效克服Souihli算法中所存在的問題。該路由準則會從眾多路徑中選擇負載最輕且平均剩余能量值最大的路徑。而負載的表示采用了Souihli所提出的用節(jié)點路由表大小來表示節(jié)點目前的負載。

二、自適應(yīng)負載均衡路由:原理和實現(xiàn)

按需路由協(xié)議是一種按需路由協(xié)議,只有在兩個節(jié)點需要進行通信,且源節(jié)點沒有到達目的節(jié)點的路由時,才進行路由發(fā)現(xiàn)過程。以AODV為例,在AODV中使用廣播式路由發(fā)現(xiàn)機制。當(dāng)源節(jié)點想與另一節(jié)點進行通信,而它的路由表中又沒有到達目的節(jié)點的路由條目時,就廣播一個路由請求(RREQ)報文。中間節(jié)點在收到RREQ報文時,首先比較本節(jié)點和目的節(jié)點的IP地址,如果自己是目的節(jié)點,就向源節(jié)點回復(fù)路由響應(yīng)(RREP)報文,如果自己不是目的節(jié)點,則根據(jù)RREQ報文中的源IP地址和廣播ID判斷是否收到過該RREQ報文,如果收到過,則丟棄該RREQ報文,若沒有收到過該RREQ報文,就記錄相關(guān)信息,用以形成反向路由。記錄的信息主要包括目的地址、源地址、廣播ID、源序列號、反向路由超時時長,同時將RREQ報文中的跳數(shù)字段(hop count)值加1,并向鄰居節(jié)點轉(zhuǎn)發(fā)RREQ報文。當(dāng)中繼節(jié)點或目的節(jié)點沿著反向路徑回復(fù)RREP報文時,這條路徑上的節(jié)點建立前向路由。當(dāng)RREP報文到達源節(jié)點后,源節(jié)點就可以使用已經(jīng)建立的路由發(fā)送數(shù)據(jù)報文。

由按需路由協(xié)議的原理可以看出,該類協(xié)議非常適合結(jié)點移動比較頻繁的無線網(wǎng)絡(luò)。然而當(dāng)網(wǎng)絡(luò)一旦運行平穩(wěn),數(shù)據(jù)傳輸總是集中在所選的最短路徑上,導(dǎo)致處在多條通信鏈路上的節(jié)點成為網(wǎng)絡(luò)瓶頸,引起網(wǎng)絡(luò)性能下降。這主要是由于協(xié)議使用最短路徑作為路由選擇標準所導(dǎo)致的。

在本文中,我們所提的協(xié)議仍然是一個按需路由協(xié)議,并且也包括路由發(fā)現(xiàn)和路由維護兩個過程。在每個階段,協(xié)議采用AODV相似的機制,區(qū)別就是路由選擇的標準。新的路由標準同時考慮了節(jié)點的負載和節(jié)點的剩余電量,目的就是從眾多可能的路徑中選出平均負載最小同時剩余電量最大的一條路徑。該路由準則可以表示為:

式中sizeof(rtb(i))表示節(jié)點i的路由表大小。N表示當(dāng)前路徑中的所有節(jié)點數(shù)量,Er(i)反映了節(jié)點i的剩余能量。

在實施這個協(xié)議時,需要在路由請求包的頭部增個三個項,分別用來表示路由的平均負載、平均剩余能量和新的路由標準。在本文中所采用的能量模型能量模型計算公式為:

即當(dāng)一個節(jié)點發(fā)送或者接收一個包時所消耗的能量是由該節(jié)點發(fā)送或接收的功率和處理該包所需要的時間決定的。式中,處理一個包所需要的時間為:

式中,Ptx、Prx分別代表發(fā)送和接收時的功率。

對于轉(zhuǎn)發(fā)一個包所消耗的全部能量為:

在路由發(fā)現(xiàn)階段,當(dāng)發(fā)送點想要向目的節(jié)點發(fā)送數(shù)據(jù),而此時發(fā)送節(jié)點并沒有可用路由,源節(jié)點就要發(fā)送一個 RREQ消息,該消息包含它的路由表大小、剩余能量和一個新的路由準則作為它的附加信息。此時,新的路由準則的計算公式為:

當(dāng)中間節(jié)點I收到RREQ消息后,它會根據(jù)自己的實際情況,更新消息中的三個字段值。對于路由表項和剩余能量平均值的計算公式為:

式中,X表示路由表大小或者是剩余能量項,n表示由源節(jié)點到目前節(jié)點所經(jīng)歷的跳數(shù)。Avgx(n)代表 X項在前一節(jié)點處的平均值。

最后,當(dāng)目標節(jié)點D收集到來自于不同路徑的RREQ消息后,目的節(jié)點會從中選出對應(yīng)于新的路由標準值最小的那條路徑,而不是最短路徑,并沿此路徑發(fā)送一個RREP消息給源節(jié)點。至此,源節(jié)點和目的節(jié)點之間的路由建立。

三、協(xié)議仿真和性能評估

為了驗證所提協(xié)議性能,本文在網(wǎng)絡(luò)模擬平臺NS2上進行了模擬試驗,并與AODV協(xié)議和Souihli的方法[11]進行了比較。

1.仿真環(huán)境設(shè)置

在仿真模型中,設(shè)置了50個移動節(jié)點,隨機分布在1200mx1200m的矩形區(qū)域內(nèi)。無線傳輸模型采用雙徑地面反射模型,MAC層協(xié)議采用 IEEE802.11。傳輸層使用UDP,數(shù)據(jù)流采用CBR業(yè)務(wù),包長度為512B,數(shù)據(jù)流輛分別設(shè)為:1Mb/s,5 Mb/s,10 Mb/s,15 Mb/s and 25 Mb/s.,最大連接數(shù)為100。節(jié)點的無線發(fā)射半徑均為250m.。節(jié)點的移動模型采用隨機移動模型,節(jié)點速度在0到25正態(tài)分布,節(jié)點在運動到一個目的地后不做停留繼續(xù)運動。所有節(jié)點的初始能量設(shè)置為60焦,發(fā)射功率和接收功率分別為200mW和600mW。仿真時間設(shè)為300秒。

2.性能準則

在仿真試驗中,我們重點對各種協(xié)議采用如下準則進行了對比:

(1)包投遞率(PDR)

包投遞率表示為目的節(jié)點接收到的包的數(shù)量與源節(jié)點發(fā)送包數(shù)量之比。

(2)端到端延遲

端到端延遲代表了所有包由源節(jié)點到達目的節(jié)點所經(jīng)歷時間的平均值。

3.性能評價

(1)包投遞率(PDR)

在圖1中,給出了三種協(xié)議在負載分別為1Mb/s,5 Mb/s,10 Mb/s,15 Mb/s和25 Mb/s的情況下,包投遞率方面的比較結(jié)果。由圖可以看出,在網(wǎng)絡(luò)負載較重的情況下,Souihli的方法[11]和本文所提的方法在包投遞率性能方面要強于AODV協(xié)議。同時伴隨著負載逐漸增大,本文所提的算法在包投遞率方面較之Souihli的方法[11]有更加突出的表現(xiàn)。

圖1 包投遞率比較

(2)端到端延遲

圖2給出了三種協(xié)議在六種不同的負載下在端到端時延上的表現(xiàn)。在相對較輕的負載情況下,三種協(xié)議產(chǎn)生的時延大小差別不大。當(dāng)給網(wǎng)絡(luò)增大負載時,由AODV協(xié)議所產(chǎn)生的延遲逐漸變大,大大超過Souihli的和本文所提的方法。同時可以看出,本文所提協(xié)議在時延方面也要優(yōu)于Souihli的方法。

圖2 端到端延遲對比

四、結(jié)論

路由協(xié)議設(shè)計是移動自組織網(wǎng)絡(luò)能否正常運作的重要條件。通常的一些協(xié)議在路由設(shè)計時僅考慮路徑的長度問題,而沒有結(jié)合路徑上各節(jié)點的其它特征。這種路由準則雖然簡單,但也容易導(dǎo)致各節(jié)點負載分配不均衡問題的產(chǎn)生。本文引入了一個新的路由準則,該準則同時考慮了節(jié)點的負載和節(jié)點的剩余能量問題。通過采用新的路由準則,路由協(xié)議會在眾多可選的路徑中選擇一條負載最輕且剩余電量盡可能大的路徑來傳輸數(shù)據(jù)。實驗仿真結(jié)果也顯示,本文所提的協(xié)議在包投遞率和端到端時延方面有著顯著的性能。

[1]Toh C.K.,Ad Hoc Mobile Wireless Networks:Protocols and Systems[M].Prentice Hall,2001.

[2]David B.Johnson,Davis A.Maltz,“The Dynamic Source Routing Protocol for Mobile Ad HocNetworks”[S].IETF Draft,Oct.1999.

[3]David B.Johnson,Davis A.Maltz,“Dynamic Source Routing in Ad Hoc Networks[J]”.Mobile Computing,T.Imielinski and H.Korth,Eds.Kulwer,1996,pp.152-81.

[4]Charles E.Perkins,Elizabeth M.Royer,Samir R.Das,“Ad Hoc On-demand Distance Vector Routing[S]”.IETF Draft,Oct.1999.

[5]Ganjali Y.,Keshavarzian A.,Load balancing in ad hoc networks:single-path routing vs.multi-path routing[C].in:Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004),March 2004.

[6]Yin S.,Lin X.,MALB:MANET adaptive load balancing[C].in:IEEE Vehicular Technology Conference(VTC2004-Fall),vol.4,September 2004,pp.2843-2847.

[7]Wu K.,Harms J.,Performance study of a multipath routing method for wireless mobile ad hoc networks[C].in:Proceeding of the Ninth International Symposium on Modeling,Analysis,and Simulation of Computer and Telecommu2 nications Systems(MASCOTS’01),August 2001.

[8]Zhang L.,Zhao Z.,Shu Y.,et al.Load balancing of multipath source routing in ad hoc networks[C].in:Proceed2 ing of the IEEE International Conference on Communications(ICC 2002),May2002.

[9]Zhou A.,Hassanein H.,Load-balanced wireless ad hoc routing[C].in:IEEE Canadian Conference on Electrical and Computer Engineering,vol.2,2001,pp.1157-1161.

[10]Lee Y.J.,Riley G.F.,A workload-based adaptive load-balancing technique for mobile ad hoc networks[C].in:IEEE Wireless Communications and Networking Conference(WCNC’2005),vol.1,2005,pp.2002-2007.

[11]Oussama Souihli,Mounir Frikha,Mahmoud Ben Hamouda,Load-balancing in MANET shortest-path routing protocols[J].Ad Hoc Networks xxx(2008)xxx-xxx).

[12]Pham P.,Perreau S.,Performance analysis of reactive shortest path and multi-path routing mechanisms with load balance[C].IEEE Conference on Computer Communications(INFOCOM 2003).

An Adaptive Algorithm of L oad Balancing on Demand Circuit

LIU Jun-shuai1,HAO Ju-tao2

(1.Tianjin Petroleum Vocational and Technical College,Tianjin 301607 China;2.University of Shanghai for Science and Technology,Shanghai 200093 China)

This essay introduces a new route principle into the treaty,which chooses the lightest and most powerf ul load f rom many circuits to imp rove the transfer speed and reduce the end-to-end time-lag.To imp rove its f unction,it makes a complete simulate research.The result shows that it is superior to existing circuits’treaty on package delivery f raction and delay.

route treaty;load balance;mobile self-organized network;energy perception route

TP393

A

1673-582X(2011)08-0032-05

2010-10-10

劉軍帥 (1977-),男,天津石油職業(yè)技術(shù)學(xué)院講師,碩士,主要從事焊接技術(shù)及自動化教學(xué)與研究。