【正文】 負載均衡問題不光存在于艦船編隊網(wǎng)絡(luò)中，在大多數(shù)的Ad Hoc網(wǎng)絡(luò)中都存在著負載均衡問題。鑒于艦船編隊網(wǎng)絡(luò)的應(yīng)用需要和問題存在的普遍性，本章對負載均衡問題進行研究。本章第二節(jié)介紹負載均衡問題的提出，第三節(jié)介紹負載均衡的關(guān)鍵技術(shù)，第四節(jié)提出并設(shè)計基于信道負荷的負載感知方法和基于歷史信息概率路由準入的負載調(diào)度算法及CLBamp。HIBHSRP協(xié)議，第五節(jié)給出算法和協(xié)議的仿真分析，最后對本章進行小結(jié)。現(xiàn)有大多數(shù)Ad Hoc網(wǎng)絡(luò)路由協(xié)議在路由選擇和維護過程中都沒有考慮節(jié)點的負載和網(wǎng)絡(luò)擁塞情況，協(xié)議運行的結(jié)果是眾多路由經(jīng)過部分處于網(wǎng)絡(luò)中心的節(jié)點，而大量數(shù)據(jù)通過少量節(jié)點傳輸必然導(dǎo)致網(wǎng)絡(luò)出現(xiàn)擁塞，使分組排隊時延和分組丟失率增加。隨著業(yè)務(wù)流負載強度的增大，擁塞導(dǎo)致路由信息的丟失將很快觸發(fā)更多路由控制分組的產(chǎn)生，從而進一步加重網(wǎng)絡(luò)擁塞，如典型的按需路由協(xié)議AODV和DSR的分組傳輸時延隨著節(jié)點移動性的降低反而呈上升趨勢[26]。此外，被過度使用的節(jié)點的能量消耗過快，縮短了網(wǎng)絡(luò)的總體生存時間。因此，有必要在路由選擇過程中考慮節(jié)點的負載情況，對網(wǎng)絡(luò)進行負載均衡。負載均衡在本質(zhì)上就是利用分組傳輸可能存在的多條路徑構(gòu)建分組路由，通過有足夠剩余容量的節(jié)點轉(zhuǎn)發(fā)分組，使網(wǎng)絡(luò)保持連續(xù)、高效、穩(wěn)定的運行，以減輕現(xiàn)存的和潛在的網(wǎng)絡(luò)擁塞，為上層業(yè)務(wù)提供更好的服務(wù)質(zhì)量。隨著對負載均衡問題認識的深入，學(xué)者已經(jīng)對路由中的負載均衡問題做了大量的研究，這些研究主要集中在兩個方面：一是負載感知，二是負載調(diào)度。前者告訴我們網(wǎng)絡(luò)的負載狀態(tài)，后者關(guān)注如何調(diào)度負載把其均勻分布到網(wǎng)絡(luò)中。在設(shè)計無線自組網(wǎng)負載均衡路由協(xié)議的時候，要實現(xiàn)網(wǎng)絡(luò)的負載均衡，首先就要獲得網(wǎng)絡(luò)的負載分布情況，然后才能根據(jù)負載的分布情況對負載進行調(diào)度。在沒有中心節(jié)點的Ad Hoc網(wǎng)絡(luò)環(huán)境中，網(wǎng)絡(luò)負載的分布情況通常是各節(jié)點進行分布式的探測，然后再根據(jù)預(yù)設(shè)的負載均衡算法進行均衡。因此，研究負載探測方法的目的是為了向負載調(diào)度算法提供準確的負載信息，從而保證負載調(diào)度算法能夠正確及時的進行負載均衡。負載感知方法總結(jié)起來有以下幾種：基于緩沖區(qū)隊列長度的負載感知方法：基于緩沖區(qū)隊列長度的負載感知方法中，節(jié)點用緩沖區(qū)中等待發(fā)送數(shù)據(jù)隊列的長度來表征負載的狀態(tài)。當一個新的數(shù)據(jù)包從上層到達網(wǎng)絡(luò)層時，其要先進入緩沖區(qū)隊列等待，后進入隊列的數(shù)據(jù)要等待前邊的數(shù)據(jù)包發(fā)送完之后才能進入信道被發(fā)送。當緩沖區(qū)隊列較長時，節(jié)點在隊列中等待的時間就較長，那么數(shù)據(jù)的時延將會變大，而且當數(shù)據(jù)的發(fā)送速度小于數(shù)據(jù)的接納速度時，其緩沖區(qū)隊列不斷變長，最后將導(dǎo)致緩沖區(qū)溢出，后續(xù)的數(shù)據(jù)將會被丟棄。所以節(jié)點緩沖區(qū)隊列的長度在很大程度上反應(yīng)了節(jié)點負載的輕重，節(jié)點緩沖區(qū)隊列長度越小，節(jié)點的負載就越輕，反之則越重?；诼窂綍r延的負載感知方法：基于路徑延時的負載感知方法是把數(shù)據(jù)的時延作為節(jié)點負載輕重的度量。路徑時延是指數(shù)據(jù)從源節(jié)點到目的節(jié)點所走路徑的總時延，路徑時延由各節(jié)點處理時延累積形成。在Ad Hoc網(wǎng)絡(luò)中，由于節(jié)點的通信距離受限，多數(shù)情況下數(shù)據(jù)需要多跳轉(zhuǎn)發(fā)才能到達目的節(jié)點，而數(shù)據(jù)經(jīng)過每個節(jié)點的處理都需要一段時間(包括數(shù)據(jù)接收、數(shù)據(jù)排隊調(diào)度、數(shù)據(jù)發(fā)送)，所以數(shù)據(jù)從源節(jié)點到目的節(jié)點的路徑時延就是整條路由上所有節(jié)點處理時延的總和。時延是一個綜合表征量，如果不考慮數(shù)據(jù)的接收和發(fā)送時間，那么時延主要產(chǎn)生于節(jié)點的排隊等待。一方面，當一個節(jié)點的緩沖區(qū)隊列較長時，后續(xù)到來的數(shù)據(jù)就要經(jīng)過排隊，等隊列中比它先來的數(shù)據(jù)都發(fā)送完畢之后該數(shù)據(jù)包才能被發(fā)送；另一方面，因為節(jié)點要于其鄰居節(jié)點共享無線廣播信道，由于鄰居節(jié)點對信道的占用使該節(jié)點獲得信道的機會減少，導(dǎo)致數(shù)據(jù)在緩沖區(qū)隊列中等待產(chǎn)生時延。所以，時延能夠在一定程度上反應(yīng)路徑上的負載情況，時延越小則路徑上的負載越輕，反之則越重。基于信道利用率的負載感知方法：在基于信道利用率的負載感知方法中，節(jié)點通過監(jiān)測信道的使用情況來感知負載的輕重。Ad Hoc網(wǎng)絡(luò)中，物理信道是共享式無線廣播信道，節(jié)點必須與其他節(jié)點競爭（在基于競爭式的MAC協(xié)議中）來獲得物理信道發(fā)送數(shù)據(jù)，當參與競爭信道的節(jié)點較多時，節(jié)點獲得信道的概率將大大減少，數(shù)據(jù)發(fā)送的機會也將大大減少。不同的協(xié)議對信道利用率的定義不盡相同，有的協(xié)議對信道利用率的定義為單位時間內(nèi)物理信道發(fā)送的數(shù)據(jù)包的個數(shù)，數(shù)據(jù)包數(shù)越多信道的利用率就越高，相應(yīng)則負載就越重；有的協(xié)議則定義為參與競爭的鄰居節(jié)點的個數(shù)，參與信道競爭的節(jié)點個數(shù)越多，節(jié)點獲得信道的機會將減少，負載相應(yīng)就越重。Ad Hoc網(wǎng)絡(luò)中負載均衡路由協(xié)議的業(yè)務(wù)調(diào)度，是將網(wǎng)絡(luò)的流量在全網(wǎng)中進行合理地分配，避免向少數(shù)網(wǎng)絡(luò)節(jié)點和區(qū)域集中，以減輕網(wǎng)絡(luò)擁塞。好的負載調(diào)度策略應(yīng)該能夠根據(jù)負載感知的結(jié)果，把負載均勻的分布到網(wǎng)絡(luò)中去。目前負載調(diào)度策略有些是用在先應(yīng)式路由協(xié)議中的，有些是用在反應(yīng)式路由協(xié)議中的?？傮w看來主要有以下幾種：基于蟻群的負載調(diào)度算法；螞蟻有能力在沒有任何提示的情況下找到從其巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑。其根本原因是螞蟻在尋找食物時，能在其走過的路上釋放一種特殊的分泌物——信息素(Pheromone)，隨著時間的推移，該物質(zhì)會逐漸揮發(fā)。后來的螞蟻選擇該路徑的概率與當時這條路徑上該物質(zhì)的濃度成正比。當一條路徑上通過的螞蟻越來越多時，其留下的信息素也越來越多，后來螞蟻選擇該路徑的概率也越高，從而增加了該路徑的信息素濃度值。而濃度越大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。通過這種正反饋機制，螞蟻最終可以發(fā)現(xiàn)最短路徑。蟻群優(yōu)化方法(ACO:Ant Colony Optimization)[27][28]，又稱螞蟻算法，是一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，具有自組織及自動學(xué)習(xí)的能力。蟻群優(yōu)化算法的原理是一種正反饋機制或稱增強型學(xué)習(xí)系統(tǒng)，通過信息素的不斷更新達到最終收斂于優(yōu)化路徑上[29]。最早在有線網(wǎng)絡(luò)，如ABC[30]、AntNet[31]中引入了基于蟻群優(yōu)化的路由方案，其通過螞蟻進行路由發(fā)現(xiàn)與維護的基本思想為后續(xù)基于蟻群優(yōu)化的路由協(xié)議所繼承。但由于在網(wǎng)絡(luò)中采用周期性發(fā)送螞蟻分組的方法進行路由發(fā)現(xiàn)和路由維護將引入很大的時延和路由開銷，難以快速適應(yīng)網(wǎng)絡(luò)拓撲的頻繁變化，不能直接應(yīng)用于動態(tài)拓撲的Ad Hoc網(wǎng)絡(luò)中。當前所提出的基于蟻群優(yōu)化的Ad Hoc網(wǎng)絡(luò)路由協(xié)議大多需要通過其它的機制來解決上述問題，如GPS/AL[32][33]和AntAODV[34][35]都采用了類似于螞蟻的移動代理對網(wǎng)絡(luò)進行大范圍地掃描，將移動代理所經(jīng)過的網(wǎng)絡(luò)中對路由有用的信息進行收集和發(fā)布。其中，GPS/AL是一種依賴于位置信息的源路由協(xié)議，需要固定網(wǎng)絡(luò)基礎(chǔ)設(shè)施的支持；而AntAODV則將蟻群優(yōu)化算法的主動特征和AODV的按需特性結(jié)合起來，以改善路由發(fā)現(xiàn)的時延性能和協(xié)議對網(wǎng)絡(luò)拓撲變化的適應(yīng)能力?；诼酚蓱?yīng)答優(yōu)化的負載調(diào)度算法；基于路由應(yīng)答優(yōu)化的負載調(diào)度算法針對反應(yīng)式路由協(xié)議的路由應(yīng)答過程而提出。當源節(jié)點沒有到目的節(jié)點的路由時，向其他節(jié)點廣播RREQ尋路，RREQ通過其它節(jié)點的轉(zhuǎn)發(fā)最終到達目的節(jié)點。由于RREQ是廣播發(fā)送的，所以最終會有多個RREQ從不同的路徑到達目的節(jié)點，依據(jù)不同的選路準則可以選擇不同的路徑。有的路徑從源節(jié)點到達目的節(jié)點經(jīng)過最少的跳數(shù)，有的路徑從源節(jié)點到目的節(jié)點的延時最小，總之各條路徑各有自己的優(yōu)缺點。對于不同的協(xié)議選擇路徑的依據(jù)并不相同，DSR協(xié)議選擇以最短路徑構(gòu)造路由，而AODV選擇第一個到達的RREQ回送RREP，這些選路的準則不同很大程度上決定了路由協(xié)議之間的性能差異。在反應(yīng)式的負載均衡路由協(xié)議中，在選擇路徑的時候主要依據(jù)路徑上的負載情況。常見的做法是在RREQ中增加一個或幾個字段，中間節(jié)點在轉(zhuǎn)發(fā)RREQ時把自己的負載信息添加到RREQ的相應(yīng)字段中。目的節(jié)點收到多條路徑到來的RREQ之后，根據(jù)不同路徑的負載情況來選擇一條負載最輕的路徑回送RREP，從而在源節(jié)點到目的節(jié)點之間建立起一條相對最優(yōu)的路由。這種負載調(diào)度方法能夠在若干條可能的路徑中比較和選擇，只要RREQ中的信息對負載的描述足夠準確，其最終能形成從源到目的的相對最優(yōu)路由。但是其缺點也比較明顯：一方面在RREQ中增加了負載信息，而RREQ是在全網(wǎng)廣播的，所以其增加的控制開銷較大；另一方面，RREQ在網(wǎng)絡(luò)中的擴散沒有得到較好的控制，許多不可能成為路由中繼的節(jié)點也參加了對RREQ的發(fā)送，資源浪費較嚴重?；诼酚蓽嗜霗C制的負載調(diào)度算法；基于路由準入機制的負載調(diào)度是在反應(yīng)式路由協(xié)議的路由建立階段進行的。源節(jié)點如果沒有到目的節(jié)點的路由，將廣播RREQ消息發(fā)起路由尋找，中間節(jié)點收到RREQ之后根據(jù)自身的負載情況選擇是否轉(zhuǎn)發(fā)。如果節(jié)點感知到負載較輕，那么其將參加RREQ的轉(zhuǎn)發(fā)，從而允許路由從節(jié)點經(jīng)過，也使數(shù)據(jù)可能流經(jīng)節(jié)點；如果節(jié)點感知到負載較重，那么其丟棄RREQ，從而把節(jié)點排除在路由之外，減少流經(jīng)節(jié)點的數(shù)據(jù)。基于路由準入的負載調(diào)度使數(shù)據(jù)繞過負載較重的節(jié)點而經(jīng)過負載較輕的節(jié)點，從而實現(xiàn)了負載流量在網(wǎng)絡(luò)中的均衡，避免和緩解了網(wǎng)絡(luò)的擁塞?；诼酚蓽嗜氲呢撦d調(diào)度算法是完全分布式的協(xié)調(diào)，節(jié)點只是根據(jù)自己本地負載信息進行路由準入，一方面不需要在RREQ中增加任何的開銷；另一方面負載重的節(jié)點對RREQ的選擇性丟棄，控制了RREQ的廣播，減小了控制開銷，負載輕的節(jié)點對RREQ的轉(zhuǎn)發(fā)又在網(wǎng)絡(luò)中建立了多條路由，保證了路由的穩(wěn)定性。算法的難點在于節(jié)點如何判斷負載的輕重。從負載均衡的本質(zhì)看，均衡的目的是把負載均勻的分布到網(wǎng)絡(luò)中去，也就是要把負載較重節(jié)點的負載分攤到負載較輕的節(jié)點上。這其中隱含著節(jié)點之間負載輕重的比較，算法的難點正在于此。由于節(jié)點沒有與相鄰節(jié)點之間交互任何關(guān)于負載的信息，所以每個節(jié)點都對其它節(jié)點的負載情況一無所知，也就很難得到負載輕重的比較。節(jié)點完全根據(jù)自身的負載情況進行路由準入，所以對負載的調(diào)度可能會出現(xiàn)一定的誤差，最終形成的路由可能不是最優(yōu)路由。目前學(xué)者已經(jīng)對負載均衡問題做了大量的研究，提出了許多具有負載均衡功能的路由協(xié)議，下面就一些比較具有代表性的負載均衡路由協(xié)議進行簡單的介紹。基于流的負載感知路由協(xié)議ABR（AssociativityBased Routing）[36]中，協(xié)議把節(jié)點間聯(lián)合計數(shù)值、路由的轉(zhuǎn)發(fā)負載、鏈路的傳輸負載、網(wǎng)段計數(shù)信息附加在路由請求分組中，目的節(jié)點收到路由請求后，選擇穩(wěn)定性強和質(zhì)量(轉(zhuǎn)發(fā)能力和傳輸能力)高的最佳路由。ABR以聯(lián)合穩(wěn)定度作為路由選擇的度量，考慮了路徑負載因素，但它只是將負載因素作為次要的選擇依據(jù)，其負載由經(jīng)過節(jié)點的路由數(shù)目來度量，對實際的流量負載計算不準確。LBAR（LoadBalanced Wireless Ad hoc Routing）[37]協(xié)議則將節(jié)點的網(wǎng)絡(luò)負載定義為經(jīng)過節(jié)點及其鄰居節(jié)點的路由數(shù)。其考慮了無線信道與有線網(wǎng)絡(luò)信道的區(qū)別，較ABR能更細致地反映Ad Hoc網(wǎng)絡(luò)的特點。Ad Hoc網(wǎng)中由于采用共享廣播信道，使得分組的時延不僅由當前節(jié)點的業(yè)務(wù)負載引起，其它鄰居節(jié)點的業(yè)務(wù)流負載也同樣會導(dǎo)致本節(jié)點分組的傳輸時延，稱為業(yè)務(wù)流干擾。在存在業(yè)務(wù)流干擾的情況下，LBAR選擇正在發(fā)送業(yè)務(wù)流負載最小和鄰居節(jié)點干擾最小的路徑。由于不同路由的業(yè)務(wù)流不可能完全相同，因此該協(xié)議也不能準確地計算出實際的流量負載。基于分組的負載感知協(xié)議DLAR(Dynamic LoadAware Routing)[38]中，使用緩存在節(jié)點接口隊列中的分組數(shù)量作為負載的度量。中間節(jié)點在發(fā)送數(shù)據(jù)的時候周期性地把負載信息添加到數(shù)據(jù)包的相應(yīng)域中發(fā)送出去，這樣目的節(jié)點就能夠?qū)β酚傻呢撦d進行實時的監(jiān)控。但是周期性的發(fā)送負載信息勢必會增加路由的開銷。LSR(LoadSensitive Routing)[39]是一種反應(yīng)式的負載均衡路由協(xié)議，其利用緩存在節(jié)點及其鄰居節(jié)點緩存中數(shù)據(jù)包的總和表征負載，并且提出了一種路由比較函數(shù)來確定最佳路由，但需仔細為函數(shù)選擇合適的參數(shù)來提高協(xié)議的性能。在負載感知路由協(xié)議LWR(Load aWare Routing)[40]中，利用信道利用率、隊列長度、鄰居節(jié)點數(shù)目和退避計數(shù)器來反映網(wǎng)絡(luò)的負載情況，當節(jié)點獲知網(wǎng)絡(luò)負載較重時，則在接收到源節(jié)點發(fā)送的RREQ時直接丟棄，使數(shù)據(jù)避開負載較重的節(jié)點，同時減小不必要的數(shù)據(jù)轉(zhuǎn)發(fā)。但是，這種算法需要收集上述所有信息，因此可能無法及時反映網(wǎng)絡(luò)狀態(tài)，并且該算法中需要一些系統(tǒng)的預(yù)設(shè)參數(shù)，這些參數(shù)設(shè)置不當將使得系統(tǒng)性能嚴重下降。LARA(Load Aware Routing in Ad Hoc)[41]協(xié)議用通信量密度(traffic density)來度量負載，其中通信量密度代表MAC層競爭(擁塞)的程度。協(xié)議要求每個節(jié)點在鄰居表中維持一個鄰居節(jié)點的通信量隊列(周期內(nèi)接口隊列長度的平均值)，并通過周期性的發(fā)送Hello分組來更新此隊列。協(xié)議周期性信息的發(fā)送增加了路由的開銷。CLAOR (A Crosslayer LoadAware based antcolony Optimization Routing) [42]是將蟻群優(yōu)化和跨層優(yōu)化結(jié)合起來的負載均衡路由協(xié)議。協(xié)議將整個路徑中節(jié)點MAC層的總平均估計時延和節(jié)點隊列緩存的占用情況結(jié)合起來，共同作為路由選擇和路由調(diào)整的度量，并通過擁塞節(jié)點丟棄螞蟻分組以及借助部分兼具螞蟻功能的數(shù)據(jù)分組實現(xiàn)路由表的維護減少控制開銷，增加算法的可擴展性。 典型負載均衡路由協(xié)議協(xié)議路由方式中間節(jié)點應(yīng)答方式負載指標負載信息作用階段負載均衡的方法ABR按需允許節(jié)點的路由數(shù)目路由應(yīng)答階段目的節(jié)點選擇輕載路由LBAR按需禁止節(jié)點及其鄰居的路由數(shù)目路由應(yīng)答階段目的節(jié)點選擇輕載路由DLAR按需禁止節(jié)點的隊列緩存路由應(yīng)答階段目的節(jié)點選擇輕載路由LWR按需允許信道利用率、隊列長度、鄰居節(jié)點數(shù)、退避計數(shù)器路由請求階段重載節(jié)點丟棄路由請求LSR按需禁止節(jié)點和鄰居節(jié)點緩存數(shù)據(jù)包數(shù)路由應(yīng)答階段目的節(jié)點選擇輕載路由LARA按需禁止節(jié)點和鄰居節(jié)點接口隊列緩存之和路由應(yīng)答階段目的節(jié)點選擇輕載路由CLAO