移動自組織網(wǎng)絡中基于概率的負載均衡算法

移動自組織網(wǎng)絡中基于概率的負載均衡算法

0基于路由準入的負載均衡算法移動自組織網(wǎng)絡（移動應用程序網(wǎng)絡）的無線通道體積有限。如果網(wǎng)絡負載較大，網(wǎng)絡負載容易過載，網(wǎng)絡性能就會下降。經(jīng)典的按需路由協(xié)議AODV［1］和DSR［2］等在網(wǎng)絡輕負載情況下表現(xiàn)良好,但在負載較重的情況下性能都急劇惡化［3］。主要是由于協(xié)議在路徑選擇時傾向于使用相同的節(jié)點作為中間節(jié)點,大量的數(shù)據(jù)通過少量節(jié)點必然引起網(wǎng)絡的擁塞。隨著業(yè)務流負載強度的增大,擁塞導致路由信息的丟失將很快觸發(fā)更多路由控制分組的產(chǎn)生,從而進一步加重網(wǎng)絡擁塞。網(wǎng)絡擁塞帶來的網(wǎng)絡性能下降使負載均衡技術(shù)受到越來越多的關(guān)注。目前,負載均衡一般在路由層實現(xiàn),主要的負載均衡技術(shù)有蟻群算法、基于感知的負載均衡算法等。蟻群算法由意大利學者提出,是一種優(yōu)良的啟發(fā)式隨機優(yōu)化算法,采用正反饋機制實現(xiàn)分布式全局優(yōu)化,通過信息素的不斷更新最終收斂于最優(yōu)路徑上,其固有的并行計算特性有利于實現(xiàn)分散控制。現(xiàn)在蟻群算法已經(jīng)以多種方式應用于路由協(xié)議中［4，5］。另一種研究得較多的算法是基于感知的負載均衡算法。文獻提出一種基于統(tǒng)計量的負載度量方法,節(jié)點統(tǒng)計接收到的數(shù)據(jù)包數(shù),并以此設計了一個統(tǒng)計量LVC(loadcoefficientofvariance)作為負載的度量,然后在網(wǎng)絡中選擇一條最優(yōu)度量值的路徑,從而達到負載均衡的目的。文獻提出一種負載均衡算法,其以節(jié)點的空閑時間和鄰居節(jié)點的空閑時間作為聯(lián)合度量,既考慮了節(jié)點本身的負載情況,同時也考慮了其他發(fā)送節(jié)點競爭信道時帶來的影響。文獻提出一種基于信道占用率的負載均衡算法,其以節(jié)點感知到的信道占用率作為負載度量值。這些負載均衡算法都以隊列長度、時延、信道繁忙度等一個或幾個參數(shù)作為負載輕重的度量,其思想都是在路由建立過程中攜帶負載信息,目的節(jié)點選擇負載較輕的路徑建立路由。蟻群算法需要向網(wǎng)絡中發(fā)送螞蟻分組來進行負載均衡,而基于感知的負載均衡算法需要在節(jié)點間傳播負載信息。無論哪種算法都需要占用額外的信道資源,尤其大部分負載信息需要在網(wǎng)絡中以廣播方式存在,占用大量的信道資源,將對網(wǎng)絡的性能帶來嚴重影響［9］。本文對基于路由準入的負載均衡算法進行研究?；诼酚蓽嗜氲乃惴ú恍枰加妙~外的信道資源,并且能夠有效控制路由時廣播包的洪泛,減少對信道資源的占用,與路由協(xié)議的松散耦合也使算法應用更加靈活。文獻就路由準入算法有了一些論述,并提出一種基于路由準入的負載均衡算法,其以接口隊列長度作為負載度量,以一個固定的隊列長度值作為路由準入的門限。但是,基于門限的算法適應性不強,算法對高于門限或低于門限的度量值一并處理,不夠準確;由于缺乏與網(wǎng)絡負載狀態(tài)的橫向比較,其調(diào)度算法也不準確。本文提出了一種新的基于路由準入的負載均衡算法———H&P(historicalandprobability)算法。該算法由基于歷史信息的負載映射機制和基于概率的路由準入組成,算法能有效解決路由準入中負載狀態(tài)判斷不準和門限準入規(guī)則適應性不強的問題,并把H&P算法與經(jīng)典的按需路由協(xié)議DSR相結(jié)合,設計了H&P_DSR協(xié)議。1算法描述1.1節(jié)點按負載描述的安全評估目前,負載均衡中的路由準入算法大部分基于門限準則來實現(xiàn)［11］。門限準則通過設置一個門限值來判斷路由準入,低于(或高于)門限值則準入(或禁止)路由。但是可以看到,門限準則模糊了所有負載描述值低于門限的節(jié)點之間的差別,也模糊了所有負載描述值高于門限的節(jié)點之間的差別,這勢必對負載均衡的效果產(chǎn)生不利的影響。相比基于門限的路由準入機制,基于概率的算法并不直接決定是否準入路由,而是綜合各種信息得到一個準入的概率,節(jié)點以該概率進行路由準入。如圖1所示,節(jié)點B、C和D都收到了來自源節(jié)點A的路由請求,在t1時刻節(jié)點B、C和D的負載描述值分別為8、10和12。如果門限值為7,那么三個節(jié)點的負載都高于門限值,則此門限值的設定就無法區(qū)別出節(jié)點B、C和D之間的負載差異;同樣,在t2時刻B、C、D三個節(jié)點的負載描述值分別為4、6、8時,如果門限值為10,那么此門限值也無法區(qū)別出三個節(jié)點之間的差異,而實際上三個節(jié)點的負載有較大的差異。概率算法針對不同的負載描述值得到不同的路由準入概率。例如對于負載描述值8、10和12,概率算法分別給予80%、60%和30%的準入概率,那么B、C和D三個節(jié)點路由準入的結(jié)果必然不同,節(jié)點D轉(zhuǎn)發(fā)RREQ將多于其他兩個節(jié)點?；诟怕实乃惴軌驕蚀_區(qū)別節(jié)點之間的負載差異,對不同負載給予不同的策略。對于一個既定的負載量,要求得到一個對應的準入概率。如果把給定的負載量L作為自變量,而對應的準入概率P作為函數(shù)值,那么就可以確定負載量和準入概率之間的函數(shù)對應關(guān)系:其中:P是準入概率,L是節(jié)點的負載量,F是概率函數(shù)。給定一個負載L就可以通過式(1)算出路由準入的概率P。概率函數(shù)F可以用多條曲線來擬合,理論上講,只要是單調(diào)下降的函數(shù)曲線都合適,使大的負載描述值對應小的準入概率(負載描述值越大,負載越重),但是不同曲線對應不同的協(xié)議性能。1.2節(jié)點在網(wǎng)絡區(qū)域內(nèi)的負載狀態(tài)變化基于路由準入的負載調(diào)度算法是完全分布式運算的,節(jié)點之間沒有任何的負載信息交互。因此節(jié)點對網(wǎng)絡狀態(tài)感知的準確性就成為負載均衡的關(guān)鍵之一。基于歷史信息的負載映射利用節(jié)點的歷史負載信息來映射網(wǎng)絡的負載狀態(tài),為節(jié)點的路由準入提供有效的參考。研究發(fā)現(xiàn)節(jié)點負載強度與節(jié)點在網(wǎng)絡中的位置有很大的關(guān)系,當節(jié)點處在網(wǎng)絡的中心區(qū)域時,由于經(jīng)過的路由數(shù)比較多,所以節(jié)點負載一般較高;相反,當節(jié)點處在網(wǎng)絡邊緣時,負載較低。又由于節(jié)點的移動,節(jié)點在網(wǎng)絡中的位置不斷發(fā)生變化,從而節(jié)點的負載狀態(tài)也在不斷改變。在一定的網(wǎng)絡區(qū)域內(nèi),以節(jié)點隨機移動為例,理論上經(jīng)過足夠長的時間,節(jié)點會遍歷網(wǎng)絡,經(jīng)歷網(wǎng)絡的各種負載狀態(tài),稱之為節(jié)點的網(wǎng)絡各態(tài)歷經(jīng)性。也就是在經(jīng)過足夠的時間后,節(jié)點能夠掌握足夠豐富的網(wǎng)絡負載信息,而這些信息與當前時刻其他節(jié)點的負載高度相關(guān)。所以,節(jié)點在歷經(jīng)各種網(wǎng)絡負載狀態(tài)時,記錄下相應時刻的負載描述值,作為路由準入時的橫向比較參考,使路由準入更準確。圖2是四個相隔不遠時刻的網(wǎng)絡拓撲,圖中著色的節(jié)點為同一個節(jié)點A。從圖中可以看到,從t1時刻到t4時刻這段時間內(nèi),節(jié)點A由網(wǎng)絡的中心運動到了網(wǎng)絡的邊緣(其他節(jié)點也會移動,只是筆者并不關(guān)心),而節(jié)點移動之后的位置被其他節(jié)點取代。如圖2(b)中的t2時刻,節(jié)點B運動到了節(jié)點A在t1時刻的位置,其他幾個圖同理。節(jié)點在網(wǎng)絡中位置的變化導致節(jié)點的負載狀態(tài)改變,在t1、t2、t3、t4四個時刻,節(jié)點A的負載描述值分別為9、7、5和3,可見節(jié)點的負載在逐漸降低。而在這個過程中,節(jié)點不斷記錄負載信息,包括變化過程中負載的最大值、最小值以及整個過程中的負載平均值等。節(jié)點A記錄的負載最大值是t1時刻,其負載描述值為9,負載的最小值是在t4時刻,其負載描述值為3,整個過程負載的平均值為(9+7+5+3)/4=6。節(jié)點利用這些歷史負載信息來映射網(wǎng)絡的負載狀態(tài)。如節(jié)點記錄的歷史最大負載描述值為9,那么很可能此時網(wǎng)絡中的其他某個節(jié)點的負載值為9。通過當前的負載值與歷史負載值比較,節(jié)點很容易判斷出自己的負載輕重,從而決定是否準入路由,達到負載均衡的目的。1.3負載信息的設計DSR(dynamicsourcerouting)是MANET中的經(jīng)典按需源路由協(xié)議,鑒于其研究的廣泛性和代表性,本節(jié)在DSR協(xié)議中實現(xiàn)H&P算法,添加了H&P算法的新協(xié)議稱為H&P_DSR協(xié)議。H&P_DSR協(xié)議的路由過程類似于DSR協(xié)議。當源節(jié)點沒有到達目的節(jié)點的路由時,廣播RREQ發(fā)起路由尋找,中間節(jié)點利用H&P算法決定是否準入路由。準入路由的節(jié)點轉(zhuǎn)發(fā)RREQ,其他節(jié)點丟棄路由申請,目的節(jié)點收到RREQ之后回送路由應答RREP,最終形成源節(jié)點到目的節(jié)點的路由。H&P_DSR協(xié)議中的H&P算法主要通過以下幾個規(guī)則實現(xiàn):規(guī)則1負載表征量的設計。能夠描述網(wǎng)絡負載的表征量有很多,主要的有時延、信道占用時間、路由數(shù)和緩沖區(qū)隊列長度等。時延表征量是選擇一條時延最短的路徑;信道占用時間是以節(jié)點感知到的信道被占用的時間作為負載的度量;路由數(shù)是以經(jīng)過節(jié)點的路由數(shù)目作為負載的度量;緩沖區(qū)隊列長度是以節(jié)點接口隊列緩沖區(qū)長度作為負載度量。不同的表征量各有特點,操作也不相同。時延和路由數(shù)表征量需要在節(jié)點之間交換表征量信息,增加了額外開銷,且對負載的描述不全面;信道占用時間是一個有效的負載度量［12］,但是需要MAC協(xié)議支持,即需要跨層設計,這增加了協(xié)議的復雜性,也破壞了負載均衡算法與協(xié)議的松散耦合;緩沖區(qū)隊列長度對負載的描述簡單有效,而且具有獨立分布式運算、易于操作等特點。所以在H&P_DSR協(xié)議中選擇緩沖區(qū)隊列長度作為負載表征量。規(guī)則2負載信息的學習與搜集。H&P算法中對網(wǎng)絡負載狀態(tài)的判讀依賴節(jié)點運行時搜集的信息。節(jié)點搜集到的負載信息越多,對網(wǎng)絡負載的分布情況判斷越準確,負載均衡的效果就越好。由于開始時節(jié)點沒有搜集到足夠的負載信息,所以前幾個周期并不進行路由準入的判斷,而是正常路由,只對網(wǎng)絡的負載情況進行采樣和記錄,其中包括節(jié)點運行過程中負載表增量的最大值(記為Lmax)、最小值(記為Lmin)以及平均值(記為Lave)?？梢造`活地設置路由準入介入的時間,理論上此時間越長節(jié)點搜集到的信息越豐富,路由準入判斷越準確。實際中可根據(jù)具體的應用來設計,其與節(jié)點的移動速度、通信距離等有關(guān)。在當前仿真場景下,在2000×2000m2范圍內(nèi)的區(qū)域內(nèi),節(jié)點的平均速度為20m/s,通信距離為400m,理論上節(jié)點從網(wǎng)絡邊緣進入到中心所用的時間大約為30s?？蓳?jù)此來設計路由準入介入的時間設置為30s,其他應用場景亦可據(jù)此計算。規(guī)則3概率函數(shù)的設計。選用最常用和直觀的直線來擬合概率函數(shù)。設直線函數(shù)為其中:α和β是未知的常數(shù)。那么,根據(jù)規(guī)則2中節(jié)點記錄的歷史負載信息,應該是大的負載對應小的準入概率,而小的負載對應大的準入概率。最小的負載為Lmin,對應最大的準入概率為Pmax,則得到一個坐標點A(Lmin,Pmax),同理,最大的負載為Lmax,最小的準入概率為Pmin,得到另一個坐標點B(Lmax,Pmin)。把已知的坐標點A和B代入直線函數(shù)中,得到方程組:解此方程組可得:代入直線函數(shù)中,則可得到負載量和準入概率的映射函數(shù):當節(jié)點收到路由申請的時候,可通過式(5)代入負載描述值而得到路由準入的概率,進而決定是否接受此路由。式(5)中,Pmax和Pmin是可調(diào)參數(shù),其設置的原則是首先應保證路由的正常建立,在此基礎上優(yōu)化路由選擇,降低冗余。要始終使輕載節(jié)點有較高的準入概率,而重載節(jié)點準入概率較小。Pmax限定了節(jié)點所能獲得的最大準入概率,Pmax不能太小,否則即使輕載節(jié)點也會拒絕路由申請而使路由建立失敗,導致源節(jié)點發(fā)送新的路由請求,反而增加了網(wǎng)絡開銷。Pmin決定了節(jié)點的最低準入概率,節(jié)點至少以此概率準入路由申請。當網(wǎng)絡密度較小時,由于轉(zhuǎn)發(fā)路由申請的節(jié)點較少,為保證路由的建立,應提高Pmin的值,保證一定數(shù)量的路由申請成功。當網(wǎng)絡密度較大時,節(jié)點的一跳鄰居較多,為有效區(qū)別開不同負載節(jié)點之間的差異,使不同負載對應不同的準入概率,應該用較小的Pmin。這樣各概率能夠區(qū)別地分布在概率區(qū)間內(nèi),概率算法能過濾掉重載路由而篩選出輕載路由。Pmax應該設置為一個較大的數(shù)值,而Pmin應該根據(jù)網(wǎng)絡密度進行調(diào)整,網(wǎng)絡密度較大的環(huán)境中設置較小的Pmin值,反之Pmin應設置較大。在當前的網(wǎng)絡仿真場景中,可近似得節(jié)點的平均鄰居數(shù)為4,節(jié)點的平均準入概率如果為50%,則可保證至少有兩個節(jié)點準入路由,保證了路由的建立,同時有一條備份路徑,冗余控制在可接受的范圍內(nèi)。據(jù)此,協(xié)議中設置PMax=90%,PMin=20%。節(jié)點根據(jù)當前的負載描述值,通過式(5)可以得到路由準入的概率。2仿真結(jié)果及驗證本章在Qualnet仿真平臺上仿真驗證H&P_DSR協(xié)議的性能,首先仿真比較基于概率的和基于門限的準入算法,然后對H&P_DSR協(xié)議的性能進行驗證。仿真主要通過網(wǎng)絡吞吐量和平均端到端時延兩個指標來衡量協(xié)議的性能。2.1負載表征及仿真本節(jié)通過仿真比較基于概率的路由準入和基于門限的路由準入。仿真參數(shù)設置如表1所示。仿真中設置32個節(jié)點分布在2000×2000的區(qū)域內(nèi),應用層配置16對CBR流,CBR流數(shù)據(jù)包的長度隨機選擇,通過改變發(fā)送數(shù)據(jù)的間隔來調(diào)整CBR流添加到網(wǎng)絡中的負載。路由協(xié)議采用H&P_DSR協(xié)議,其中分別采用基于門限和基于概率的算法。目前,門限算法中門限值一般根據(jù)經(jīng)驗或采取實驗的方法手工設定［10］。公平起見,首先通過實驗獲得負載表征量的參考數(shù)據(jù)來設置門限算法中的門限值。在當前仿真設置下,設置重載和輕載兩種網(wǎng)絡負載情況,采用沒有均衡的DSR協(xié)議,在網(wǎng)絡穩(wěn)定時,分別測得重載和輕載狀態(tài)下某個時刻各節(jié)點的負載表征值分別如圖3和4所示。圖中橫坐標對應節(jié)點,縱坐標是各節(jié)點對應的負載表征值,圖中直線為所有節(jié)點的平均負載表征值。由圖可見,無論在重載還是輕載時,節(jié)點間的負載差異均較大。即使在網(wǎng)絡重載時,也有負載很輕的節(jié)點。計算得到重載情況下平均負載表征值為10.096,在輕載情況下平均負載表征值為5.115,故門限算法中分別設置兩個門限值A=10和B=5,以使門限能夠區(qū)別開不同負載的節(jié)點,起到負載均衡的作用。對基于門限和概率的算法進行仿真,仿真30次取平均值,結(jié)果如圖5和6所示。圖5是網(wǎng)絡吞吐量曲線圖,圖6是平均端到端時延曲線圖,其中橫坐標都是歸一化的網(wǎng)絡負荷,縱坐標分別是網(wǎng)絡吞吐量和平均端到端時延。圖中基于門限A的曲線其判決門限為10,基于門限B的曲線其判決門限為5。當網(wǎng)絡輕載時,節(jié)點的平均負載表征值為5,這時大部分節(jié)點的負載描述值都在門限5上下波動,判決門限5時對網(wǎng)絡狀態(tài)的變化較為敏感,能夠反映網(wǎng)絡不同部分之間負載的差異,所以能夠?qū)W(wǎng)絡的負載起到均衡的作用;當門限為10時,因為網(wǎng)絡負載較輕,絕大部分節(jié)點的負載描述值都低于10,所以判決門限10無法通過路由的準入對網(wǎng)絡的負載進行有效的均衡,影響了均衡的效果。當網(wǎng)絡負載逐漸加重后,各節(jié)點的負載描述值在10上下波動,這時判決門限10能夠準確地區(qū)別開不同節(jié)點之間的負載差異;相反判決門限5將普遍低于絕大部分節(jié)點的負載描述值,其無法有效地對網(wǎng)絡的負載進行均衡,此時網(wǎng)絡的吞吐量和時延性能都不同程度地下降。從仿真曲線可以看到,在網(wǎng)絡輕載時,門限值為5的算法性能更好,在網(wǎng)絡重載時,門限值為10的算法性能更好。對比門限算法曲線和概率算法曲線,可以看到概率算法無論在網(wǎng)絡吞吐量還是網(wǎng)絡時延方面都好于門限算法。尤其在網(wǎng)絡重載時,優(yōu)勢更加明顯。概率算法以連續(xù)曲線的方式對待不同的負載,能夠有效區(qū)別負載之間的差異,并根據(jù)這種差異采取不同的準入控制;而門限算法只能對門限值附近的負載狀態(tài)進行有效的區(qū)分,當節(jié)點感知到的負載都低于或高于判決門限時,都采取同樣的判斷結(jié)果,影響了負載均衡的準確性。2.2路由協(xié)議仿真本節(jié)通過仿真比較H&P_DSR和DSR協(xié)議的性能。仿真場景和參數(shù)設置如2.1節(jié),路由協(xié)議分別為H&P_DSR和DSR。仿真30次取平均值,結(jié)果如圖7和8所示。仿真結(jié)果與理論分析一致,H&P_DSR協(xié)議中的負載均衡算法能夠準確有效地工作,這使H&P_DSR協(xié)議無論在網(wǎng)