淺說網絡概率的負載均衡算法
前言：想要寫出一篇引人入勝的文章？我們特意為您整理了淺說網絡概率的負載均衡算法范文，希望能給你帶來靈感和參考，敬請閱讀。
1.基于概率的路由準入
目前，門限準則模糊了所有負載描述值低于門限的節點之間的差別，也模糊了所有負載描述值高于門限的節點之間的差別，這勢必對負載均衡的效果產生不利的影響。負載均衡中的路由準入算法大部分基于門限準則來實現。門限準則通過設置一個門限值來判斷路由準入，低于(或高于)門限值則準入(或禁止)路由。但是可相比基于門限的路由準入機制，基于概率的算法并不直接決定是否準入路由，而是綜合各種信息得到一個準入的概率，節點以這個概率進行路由準入。節點B、C和D都收到了來自源節點A的路由請求，在t1時刻節點B、C和D的負載描述值分別為8，10和12。如果門限值為7，那么三個節點的負載都高于門限值，則此門限值的設定就無法區別出節點B、C和D之間的負載差異；同樣，在t2時刻B、C、D3個節點的負載描述值分別為4、6、8時，如果門限值為10，那么此門限值也無法區別出3個節點之間的差異，而實際上3個節點的負載有較大的差異。概率算法針對不同的負載描述值得到不同的路由準入概率。例如對于負載描述值8、10和12，概率算法分別給予80%、60%和30%的準入概率，那么B、C和D三個節點路由準入的結果必然不同，節點D轉發RREQ將多于其它兩個節點。基于概率的算法能夠準確區別節點之間的負載差異，對不同負載予不同的策略。對于一個既定的負載量，要求得到一個對應的準入概率。如果把給定的負載量L作為自變量，而對應的準入概率P作為函數值，那么就可以確定負載量和準入概率之間的函數對應關系：PF(L)其中P是準入概率，L是節點的負載量，F是概率函數。給定一個負載L就可以通過上式算出路由準入的概率P。概率函數F可以用多條曲線來擬合，理論上講，只要是單調下降的函數曲線都合適，使大的負載描述值對應小的準入概率(負載描述值越大，負載越重)，但是不同曲線對應不同的協議性能。
2.基于歷史信息的負載映射
在一定的網絡區域內，以節點隨機移動為例，理論上經過足夠長的時間，節點會遍歷網絡，經歷網絡的各種負載狀態，我們稱之為節點的網絡各態歷經性。也就是在經過足夠的時間后，節點能夠掌握足夠豐富的網絡負載信息，而這些信息與當前時刻其他節點的負載高度相關。節點之間沒有任何的負載信息交互。因此節點對網絡狀態感知的準確性就成為負載均衡的關鍵之一。基于歷史信息的負載映射利用節點的歷史負載信息來映射網絡的負載狀態，為節點的路由準入提供有效的參考。研究發現節點負載強度與節點在網絡中的位置有很大的關系，當節點處在網絡的中心區域時，由于經過的路由數比較多，所以節點負載一般較高；相反，當節點處在網絡邊緣時，負載較低。又由于節點的移動，節點在網絡中的位置不斷發生變化，從而節點的負載狀態也在不斷改變。所以，節點在歷經各種網絡負載狀態時，記錄下相應時刻的負載描述值，作為路由準入時的橫向比較參考，使路由準入更準確。四個相隔不遠時刻的網絡拓撲，圖中著色的節點為同一個節點A。從圖中可以看到，從t1時刻到t4時刻這段時間內，節點A由網絡的中心運動到了網絡的邊緣(其它節點也會移動，只是我們并不關心)，而節點移動之后的位置被其它節點取代。2(b)中的t2時刻，節點B運動到了節點A在t1時刻的位置，其它幾個圖同理。節點在網絡中位置的變化導致節點的負載狀態改變，在t1、t2、t3、t4四個時刻，節點A的負載描述值分別為9、7、5和3，可見節點的負載在逐漸降低。而在這個過程中，節點不斷記錄負載信息，包括變化過程中負載的最大值、最小值以及整個過程中的負載平均值等。節點A記錄的負載最大值是t1時刻，其負載描述值為9，負載的最小值是在t4時刻，其負載描述值為3，整個過程負載的平均值為（9+7+5+3）/4=6。節點利用這些歷史負載信息來映射網絡的負載狀態。比如節點記錄的歷史最大負載描述值為9，那么很可能此時網絡中的其它某個節點的負載值為9。通過當前的負載值與歷史負載值比較，節點很容易判斷出自己的負載輕重，從而決定是否準入路由，達到負載均衡的目的。
3.H&P算法
能夠描述網絡負載的表征量有很多，主要的有時延、信道占用時間、路由數和緩沖區隊列長度等。時延表征量是選擇一條時延最短的路徑；信道占用時間是以節點感知到的信道被占用的時間作為負載的度量；路由數是以經過節點的路由數目作為負載的度量；緩沖區隊列長度是以節點接口隊列緩沖區長度作為負載度量。不同的表征量各有特點，操作也不相同。時延和路由數表征量需要在節點之間交換表征量信息，增加了額外開銷，且對負載的描述不全面；信道占用時間是一個有效的負載度量，但是需要MAC協議支持，即需要跨層設計，這增加了協議的復雜性，也破壞了負載均衡算法與協議的松散耦合；緩沖區隊列長度對負載的描述簡單有效，而且具有獨立分布式運算、易于操作等特點。所以在H&P_DSR協議中選擇緩沖區隊列長度作為負載表征量。規則二：負載信息的學習與搜集。H&P算法中對網絡負載狀態的判讀依賴節點運行時搜集的信息。節點搜集到的負載信息越多，對網絡負載的分布情況判斷越準確，負載均衡的效果就越好。由于開始時節點沒有搜集到足夠的負載信息，所以前幾個周期并不進行路由準入的判斷，而是正常路由，只對網絡的負載情況進行采樣和記錄，其中包括節點運行過程中負載表增量的最大值(記為MaxL)、最小值(記為MinL)以及平均值記為AveL)。可以靈活的設置路由準入介入的時間，理論上此時間越長節點搜集到的信息越豐富，路由準入判斷越準確。實際中可根據具體的應用來設計，其與節點的移動速度、通信距離等有關。在當前仿真場景下，在2000*2000m2范圍內的區域內，節點的平均速度為20m/s，通信距離為400m，理論上節點從網絡邊緣進入到中心所用的時間大約30s。
可據此來設計路由準入介入的時間設置為30s，其他應用場景亦可據此計算。規則三：概率函數的設計。選用最常用和直觀的直線來擬合概率函數。設直線函數為：PF(L)*其中和是未知的常數。那么，根據規則二中節點記錄的歷史負載信息，應該是大的負載對應小的準入概率，而小的負載對應大的準入概率。最小的負載為MinL，對應最大的準入概率為MaxP，則得到一個坐標點A(MinL，MaxP)，同理，最大的負載為MaxL，最小的準入概率為MinP，得到另一個坐標點B(MaxL，MinP)。把已知的坐標點A和B代入直線函數中，得到方程組：MaxMinMinMaxPLPL解此方程組可得：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPPLLPP*(4)代入直線函數中，則可得到負載量和準入概率的映射函數：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPLPLLPPPF(L)當節點收到路由申請的時候，可通過上式代入負載描述值而得到路由準入的概率，進而決定是否接受此路由。公式中，MaxP和MinP是可調參數，其設置的原則是首先應保證路由的正常建立，在此基礎上優化路由選擇，降低冗余。要始終使輕載節點有較高的準入概率，而重載節點準入概率較小。MaxP限定了節點所能獲得的最大準入概率，不能太小，否則即使輕載節點也會拒絕路由申請而使路由建立失敗，導致源節點發送新的路由請求，反而增加了網絡開銷。MinP決定了節點的最低準入概率，節點至少以此概率準入路由申請。當網絡密度較小時，由于轉發路由申請的節點較少，為保證路由的建立，應提高的值，保證一定數量的路由申請成功。當網絡密度較大時，節點的一跳鄰居較多，為有效區別開不同負載節點之間的差異，使不同負載對應不同的準入概率，應該用較小的。這樣各概率能夠區別地分布在概率區間內，概率算法能過濾掉重載路由而篩選出輕載路由。所以，MaxP應該設置為一個較大的數值，而應該根據網絡密度進行調整，網絡密度較大的環境中設置較小的值，反之應設置較大。在當前的網絡仿真場景中，可近似得節點的平均鄰居數為4，節點的平均準入概率如果為50%，則可保證至少有兩個節點準入路由，保證了路由的建立，同時有一條備份路徑，冗余控制在可接受的范圍內。據此，協議中設置90%MaxP，20%MinP。節點根據當前的負載描述值，通過式可以得到路由準入的概率。
作者：王華東 侯燕 王鳳春 單位：周口師范學院計算