淺說(shuō)網(wǎng)絡(luò)概率的負(fù)載均衡算法

前言：想要寫(xiě)出一篇引人入勝的文章？我們特意為您整理了淺說(shuō)網(wǎng)絡(luò)概率的負(fù)載均衡算法范文，希望能給你帶來(lái)靈感和參考，敬請(qǐng)閱讀。

1.基于概率的路由準(zhǔn)入

目前，門(mén)限準(zhǔn)則模糊了所有負(fù)載描述值低于門(mén)限的節(jié)點(diǎn)之間的差別，也模糊了所有負(fù)載描述值高于門(mén)限的節(jié)點(diǎn)之間的差別，這勢(shì)必對(duì)負(fù)載均衡的效果產(chǎn)生不利的影響。負(fù)載均衡中的路由準(zhǔn)入算法大部分基于門(mén)限準(zhǔn)則來(lái)實(shí)現(xiàn)。門(mén)限準(zhǔn)則通過(guò)設(shè)置一個(gè)門(mén)限值來(lái)判斷路由準(zhǔn)入，低于(或高于)門(mén)限值則準(zhǔn)入(或禁止)路由。但是可相比基于門(mén)限的路由準(zhǔn)入機(jī)制，基于概率的算法并不直接決定是否準(zhǔn)入路由，而是綜合各種信息得到一個(gè)準(zhǔn)入的概率，節(jié)點(diǎn)以這個(gè)概率進(jìn)行路由準(zhǔn)入。節(jié)點(diǎn)B、C和D都收到了來(lái)自源節(jié)點(diǎn)A的路由請(qǐng)求，在t1時(shí)刻節(jié)點(diǎn)B、C和D的負(fù)載描述值分別為8，10和12。如果門(mén)限值為7，那么三個(gè)節(jié)點(diǎn)的負(fù)載都高于門(mén)限值，則此門(mén)限值的設(shè)定就無(wú)法區(qū)別出節(jié)點(diǎn)B、C和D之間的負(fù)載差異；同樣，在t2時(shí)刻B、C、D3個(gè)節(jié)點(diǎn)的負(fù)載描述值分別為4、6、8時(shí)，如果門(mén)限值為10，那么此門(mén)限值也無(wú)法區(qū)別出3個(gè)節(jié)點(diǎn)之間的差異，而實(shí)際上3個(gè)節(jié)點(diǎn)的負(fù)載有較大的差異。概率算法針對(duì)不同的負(fù)載描述值得到不同的路由準(zhǔn)入概率。例如對(duì)于負(fù)載描述值8、10和12，概率算法分別給予80%、60%和30%的準(zhǔn)入概率，那么B、C和D三個(gè)節(jié)點(diǎn)路由準(zhǔn)入的結(jié)果必然不同，節(jié)點(diǎn)D轉(zhuǎn)發(fā)RREQ將多于其它兩個(gè)節(jié)點(diǎn)?；诟怕实乃惴軌驕?zhǔn)確區(qū)別節(jié)點(diǎn)之間的負(fù)載差異，對(duì)不同負(fù)載予不同的策略。對(duì)于一個(gè)既定的負(fù)載量，要求得到一個(gè)對(duì)應(yīng)的準(zhǔn)入概率。如果把給定的負(fù)載量L作為自變量，而對(duì)應(yīng)的準(zhǔn)入概率P作為函數(shù)值，那么就可以確定負(fù)載量和準(zhǔn)入概率之間的函數(shù)對(duì)應(yīng)關(guān)系：PF(L)其中P是準(zhǔn)入概率，L是節(jié)點(diǎn)的負(fù)載量，F(xiàn)是概率函數(shù)。給定一個(gè)負(fù)載L就可以通過(guò)上式算出路由準(zhǔn)入的概率P。概率函數(shù)F可以用多條曲線來(lái)擬合，理論上講，只要是單調(diào)下降的函數(shù)曲線都合適，使大的負(fù)載描述值對(duì)應(yīng)小的準(zhǔn)入概率(負(fù)載描述值越大，負(fù)載越重)，但是不同曲線對(duì)應(yīng)不同的協(xié)議性能。

2.基于歷史信息的負(fù)載映射

在一定的網(wǎng)絡(luò)區(qū)域內(nèi)，以節(jié)點(diǎn)隨機(jī)移動(dòng)為例，理論上經(jīng)過(guò)足夠長(zhǎng)的時(shí)間，節(jié)點(diǎn)會(huì)遍歷網(wǎng)絡(luò)，經(jīng)歷網(wǎng)絡(luò)的各種負(fù)載狀態(tài)，我們稱(chēng)之為節(jié)點(diǎn)的網(wǎng)絡(luò)各態(tài)歷經(jīng)性。也就是在經(jīng)過(guò)足夠的時(shí)間后，節(jié)點(diǎn)能夠掌握足夠豐富的網(wǎng)絡(luò)負(fù)載信息，而這些信息與當(dāng)前時(shí)刻其他節(jié)點(diǎn)的負(fù)載高度相關(guān)。節(jié)點(diǎn)之間沒(méi)有任何的負(fù)載信息交互。因此節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)狀態(tài)感知的準(zhǔn)確性就成為負(fù)載均衡的關(guān)鍵之一。基于歷史信息的負(fù)載映射利用節(jié)點(diǎn)的歷史負(fù)載信息來(lái)映射網(wǎng)絡(luò)的負(fù)載狀態(tài)，為節(jié)點(diǎn)的路由準(zhǔn)入提供有效的參考。研究發(fā)現(xiàn)節(jié)點(diǎn)負(fù)載強(qiáng)度與節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置有很大的關(guān)系，當(dāng)節(jié)點(diǎn)處在網(wǎng)絡(luò)的中心區(qū)域時(shí)，由于經(jīng)過(guò)的路由數(shù)比較多，所以節(jié)點(diǎn)負(fù)載一般較高；相反，當(dāng)節(jié)點(diǎn)處在網(wǎng)絡(luò)邊緣時(shí)，負(fù)載較低。又由于節(jié)點(diǎn)的移動(dòng)，節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置不斷發(fā)生變化，從而節(jié)點(diǎn)的負(fù)載狀態(tài)也在不斷改變。所以，節(jié)點(diǎn)在歷經(jīng)各種網(wǎng)絡(luò)負(fù)載狀態(tài)時(shí)，記錄下相應(yīng)時(shí)刻的負(fù)載描述值，作為路由準(zhǔn)入時(shí)的橫向比較參考，使路由準(zhǔn)入更準(zhǔn)確。四個(gè)相隔不遠(yuǎn)時(shí)刻的網(wǎng)絡(luò)拓?fù)?，圖中著色的節(jié)點(diǎn)為同一個(gè)節(jié)點(diǎn)A。從圖中可以看到，從t1時(shí)刻到t4時(shí)刻這段時(shí)間內(nèi)，節(jié)點(diǎn)A由網(wǎng)絡(luò)的中心運(yùn)動(dòng)到了網(wǎng)絡(luò)的邊緣(其它節(jié)點(diǎn)也會(huì)移動(dòng)，只是我們并不關(guān)心)，而節(jié)點(diǎn)移動(dòng)之后的位置被其它節(jié)點(diǎn)取代。2(b)中的t2時(shí)刻，節(jié)點(diǎn)B運(yùn)動(dòng)到了節(jié)點(diǎn)A在t1時(shí)刻的位置，其它幾個(gè)圖同理。節(jié)點(diǎn)在網(wǎng)絡(luò)中位置的變化導(dǎo)致節(jié)點(diǎn)的負(fù)載狀態(tài)改變，在t1、t2、t3、t4四個(gè)時(shí)刻，節(jié)點(diǎn)A的負(fù)載描述值分別為9、7、5和3，可見(jiàn)節(jié)點(diǎn)的負(fù)載在逐漸降低。而在這個(gè)過(guò)程中，節(jié)點(diǎn)不斷記錄負(fù)載信息，包括變化過(guò)程中負(fù)載的最大值、最小值以及整個(gè)過(guò)程中的負(fù)載平均值等。節(jié)點(diǎn)A記錄的負(fù)載最大值是t1時(shí)刻，其負(fù)載描述值為9，負(fù)載的最小值是在t4時(shí)刻，其負(fù)載描述值為3，整個(gè)過(guò)程負(fù)載的平均值為（9+7+5+3）/4=6。節(jié)點(diǎn)利用這些歷史負(fù)載信息來(lái)映射網(wǎng)絡(luò)的負(fù)載狀態(tài)。比如節(jié)點(diǎn)記錄的歷史最大負(fù)載描述值為9，那么很可能此時(shí)網(wǎng)絡(luò)中的其它某個(gè)節(jié)點(diǎn)的負(fù)載值為9。通過(guò)當(dāng)前的負(fù)載值與歷史負(fù)載值比較，節(jié)點(diǎn)很容易判斷出自己的負(fù)載輕重，從而決定是否準(zhǔn)入路由，達(dá)到負(fù)載均衡的目的。

3.H&P算法

能夠描述網(wǎng)絡(luò)負(fù)載的表征量有很多，主要的有時(shí)延、信道占用時(shí)間、路由數(shù)和緩沖區(qū)隊(duì)列長(zhǎng)度等。時(shí)延表征量是選擇一條時(shí)延最短的路徑；信道占用時(shí)間是以節(jié)點(diǎn)感知到的信道被占用的時(shí)間作為負(fù)載的度量；路由數(shù)是以經(jīng)過(guò)節(jié)點(diǎn)的路由數(shù)目作為負(fù)載的度量；緩沖區(qū)隊(duì)列長(zhǎng)度是以節(jié)點(diǎn)接口隊(duì)列緩沖區(qū)長(zhǎng)度作為負(fù)載度量。不同的表征量各有特點(diǎn)，操作也不相同。時(shí)延和路由數(shù)表征量需要在節(jié)點(diǎn)之間交換表征量信息，增加了額外開(kāi)銷(xiāo)，且對(duì)負(fù)載的描述不全面；信道占用時(shí)間是一個(gè)有效的負(fù)載度量，但是需要MAC協(xié)議支持，即需要跨層設(shè)計(jì)，這增加了協(xié)議的復(fù)雜性，也破壞了負(fù)載均衡算法與協(xié)議的松散耦合；緩沖區(qū)隊(duì)列長(zhǎng)度對(duì)負(fù)載的描述簡(jiǎn)單有效，而且具有獨(dú)立分布式運(yùn)算、易于操作等特點(diǎn)。所以在H&P_DSR協(xié)議中選擇緩沖區(qū)隊(duì)列長(zhǎng)度作為負(fù)載表征量。規(guī)則二：負(fù)載信息的學(xué)習(xí)與搜集。H&P算法中對(duì)網(wǎng)絡(luò)負(fù)載狀態(tài)的判讀依賴(lài)節(jié)點(diǎn)運(yùn)行時(shí)搜集的信息。節(jié)點(diǎn)搜集到的負(fù)載信息越多，對(duì)網(wǎng)絡(luò)負(fù)載的分布情況判斷越準(zhǔn)確，負(fù)載均衡的效果就越好。由于開(kāi)始時(shí)節(jié)點(diǎn)沒(méi)有搜集到足夠的負(fù)載信息，所以前幾個(gè)周期并不進(jìn)行路由準(zhǔn)入的判斷，而是正常路由，只對(duì)網(wǎng)絡(luò)的負(fù)載情況進(jìn)行采樣和記錄，其中包括節(jié)點(diǎn)運(yùn)行過(guò)程中負(fù)載表增量的最大值(記為MaxL)、最小值(記為MinL)以及平均值記為AveL)?？梢造`活的設(shè)置路由準(zhǔn)入介入的時(shí)間，理論上此時(shí)間越長(zhǎng)節(jié)點(diǎn)搜集到的信息越豐富，路由準(zhǔn)入判斷越準(zhǔn)確。實(shí)際中可根據(jù)具體的應(yīng)用來(lái)設(shè)計(jì)，其與節(jié)點(diǎn)的移動(dòng)速度、通信距離等有關(guān)。在當(dāng)前仿真場(chǎng)景下，在2000*2000m2范圍內(nèi)的區(qū)域內(nèi)，節(jié)點(diǎn)的平均速度為20m/s，通信距離為400m，理論上節(jié)點(diǎn)從網(wǎng)絡(luò)邊緣進(jìn)入到中心所用的時(shí)間大約30s。

可據(jù)此來(lái)設(shè)計(jì)路由準(zhǔn)入介入的時(shí)間設(shè)置為30s，其他應(yīng)用場(chǎng)景亦可據(jù)此計(jì)算。規(guī)則三：概率函數(shù)的設(shè)計(jì)。選用最常用和直觀的直線來(lái)擬合概率函數(shù)。設(shè)直線函數(shù)為：PF(L)*其中和是未知的常數(shù)。那么，根據(jù)規(guī)則二中節(jié)點(diǎn)記錄的歷史負(fù)載信息，應(yīng)該是大的負(fù)載對(duì)應(yīng)小的準(zhǔn)入概率，而小的負(fù)載對(duì)應(yīng)大的準(zhǔn)入概率。最小的負(fù)載為MinL，對(duì)應(yīng)最大的準(zhǔn)入概率為MaxP，則得到一個(gè)坐標(biāo)點(diǎn)A(MinL，MaxP)，同理，最大的負(fù)載為MaxL，最小的準(zhǔn)入概率為MinP，得到另一個(gè)坐標(biāo)點(diǎn)B(MaxL，MinP)。把已知的坐標(biāo)點(diǎn)A和B代入直線函數(shù)中，得到方程組：MaxMinMinMaxPLPL解此方程組可得：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPPLLPP*(4)代入直線函數(shù)中，則可得到負(fù)載量和準(zhǔn)入概率的映射函數(shù)：MinMaxMinMinMaxMinMaxMinMinMaxLLLPPLPLLPPPF(L)當(dāng)節(jié)點(diǎn)收到路由申請(qǐng)的時(shí)候，可通過(guò)上式代入負(fù)載描述值而得到路由準(zhǔn)入的概率，進(jìn)而決定是否接受此路由。公式中，MaxP和MinP是可調(diào)參數(shù)，其設(shè)置的原則是首先應(yīng)保證路由的正常建立，在此基礎(chǔ)上優(yōu)化路由選擇，降低冗余。要始終使輕載節(jié)點(diǎn)有較高的準(zhǔn)入概率，而重載節(jié)點(diǎn)準(zhǔn)入概率較小。MaxP限定了節(jié)點(diǎn)所能獲得的最大準(zhǔn)入概率，不能太小，否則即使輕載節(jié)點(diǎn)也會(huì)拒絕路由申請(qǐng)而使路由建立失敗，導(dǎo)致源節(jié)點(diǎn)發(fā)送新的路由請(qǐng)求，反而增加了網(wǎng)絡(luò)開(kāi)銷(xiāo)。MinP決定了節(jié)點(diǎn)的最低準(zhǔn)入概率，節(jié)點(diǎn)至少以此概率準(zhǔn)入路由申請(qǐng)。當(dāng)網(wǎng)絡(luò)密度較小時(shí)，由于轉(zhuǎn)發(fā)路由申請(qǐng)的節(jié)點(diǎn)較少，為保證路由的建立，應(yīng)提高的值，保證一定數(shù)量的路由申請(qǐng)成功。當(dāng)網(wǎng)絡(luò)密度較大時(shí)，節(jié)點(diǎn)的一跳鄰居較多，為有效區(qū)別開(kāi)不同負(fù)載節(jié)點(diǎn)之間的差異，使不同負(fù)載對(duì)應(yīng)不同的準(zhǔn)入概率，應(yīng)該用較小的。這樣各概率能夠區(qū)別地分布在概率區(qū)間內(nèi)，概率算法能過(guò)濾掉重載路由而篩選出輕載路由。所以，MaxP應(yīng)該設(shè)置為一個(gè)較大的數(shù)值，而應(yīng)該根據(jù)網(wǎng)絡(luò)密度進(jìn)行調(diào)整，網(wǎng)絡(luò)密度較大的環(huán)境中設(shè)置較小的值，反之應(yīng)設(shè)置較大。在當(dāng)前的網(wǎng)絡(luò)仿真場(chǎng)景中，可近似得節(jié)點(diǎn)的平均鄰居數(shù)為4，節(jié)點(diǎn)的平均準(zhǔn)入概率如果為50%，則可保證至少有兩個(gè)節(jié)點(diǎn)準(zhǔn)入路由，保證了路由的建立，同時(shí)有一條備份路徑，冗余控制在可接受的范圍內(nèi)。據(jù)此，協(xié)議中設(shè)置90%MaxP，20%MinP。節(jié)點(diǎn)根據(jù)當(dāng)前的負(fù)載描述值，通過(guò)式可以得到路由準(zhǔn)入的概率。

作者：王華東 侯燕 王鳳春 單位：周口師范學(xué)院計(jì)算