王 碩 楊 毅 侯 森

（1.河南牧業(yè)經(jīng)濟(jì)學(xué)院計(jì)算機(jī)應(yīng)用系 河南 450044；2.國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 河南 450002）

0 引言

Ad Hoc網(wǎng)絡(luò)是一種無(wú)中心自組織的多跳無(wú)線網(wǎng)絡(luò)，它不需要依據(jù)任何固定設(shè)施為基礎(chǔ)，無(wú)中心，每個(gè)節(jié)點(diǎn)相互平等，可以隨意移動(dòng)，網(wǎng)絡(luò)可隨時(shí)隨地組建和更改。隨著人們對(duì)個(gè)人通信日益增長(zhǎng)的需求，Ad Hoc網(wǎng)絡(luò)的這些特性越來(lái)越被人們所重視。關(guān)于Ad Hoc網(wǎng)絡(luò)的路由選擇協(xié)議的研究正在成為目前研究的一個(gè)熱點(diǎn)。

魚(yú)眼域路由協(xié)議（FSR）是一種應(yīng)用于Ad Hoc網(wǎng)絡(luò)的主動(dòng)式分級(jí)路由協(xié)議。FSR使用了“魚(yú)眼域”思想，利用魚(yú)眼視覺(jué)的特點(diǎn)，在不同魚(yú)眼域中的節(jié)點(diǎn)以不同的頻率向鄰居節(jié)點(diǎn)廣播鏈路更新信息，這能夠大大減少鏈路狀態(tài)更新信息，從而降低了路由開(kāi)銷。但是FSR算法在路徑選擇時(shí)，基于Dijistra最優(yōu)路徑選擇算法根據(jù)跳數(shù)或鏈路質(zhì)量選擇路徑，而沒(méi)有考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載情況，往往會(huì)有多條路徑同時(shí)選中少數(shù)中間節(jié)點(diǎn)。當(dāng)這些路徑上同時(shí)有數(shù)據(jù)包發(fā)送時(shí)，將會(huì)造成中間節(jié)點(diǎn)負(fù)載過(guò)重，發(fā)包沖突機(jī)會(huì)加大，丟包率上升，以至于網(wǎng)絡(luò)性能受制于中間節(jié)點(diǎn)負(fù)載容量的瓶頸。

圖1 中間節(jié)點(diǎn)i被兩條路徑同時(shí)選中的拓?fù)鋱D

如上圖1所示，源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D之間存在兩條路徑，其中最優(yōu)路徑I的中間節(jié)點(diǎn)i同時(shí)被另一源、目的節(jié)點(diǎn)對(duì)S＇和D＇選中。當(dāng)源節(jié)點(diǎn)S有數(shù)據(jù)包要發(fā)往D時(shí)，采用通常的最優(yōu)路徑選擇算法，將會(huì)選擇S＞i＞D的路徑。假如S＇和D＇之間已經(jīng)有數(shù)據(jù)流傳輸，S發(fā)送的包將在節(jié)點(diǎn)i發(fā)生碰撞，造成丟包率上升，延時(shí)增大。我們看到S和D之間存在另一條路徑S>j>k>D，假設(shè)該路徑和最優(yōu)路徑質(zhì)量差別不大，而負(fù)載較輕，如果S選擇這條路徑將會(huì)極大地減少發(fā)包碰撞的概率，而且從全網(wǎng)的角度來(lái)看，流量得到了全局均衡。流量均衡算法正是基于這樣的考慮來(lái)改進(jìn)路由協(xié)議選路機(jī)制，突破單個(gè)節(jié)點(diǎn)的負(fù)載容量瓶頸，實(shí)現(xiàn)全局的性能提升。

1 CLBFSR路由協(xié)議算法

CLBFSR路由協(xié)議是由傳統(tǒng)的FSR算法演變而來(lái)，CLBFSR算法利用跨層（cross-layer）的思想，周期性的從MAC層收集本地節(jié)點(diǎn)流量負(fù)載情況，劃分負(fù)載等級(jí)。在計(jì)算和生成路由表時(shí)，將鄰節(jié)點(diǎn)的負(fù)載情況作為權(quán)重計(jì)算下一跳節(jié)點(diǎn)的代價(jià)函數(shù)f（x）。這樣當(dāng)節(jié)點(diǎn)要發(fā)送數(shù)據(jù)包時(shí)，就可以根據(jù)它的鄰節(jié)點(diǎn)負(fù)載程度以及代價(jià)函數(shù)f（x）動(dòng)態(tài)地選擇下一跳，從而避免向重負(fù)載節(jié)點(diǎn)發(fā)送數(shù)據(jù)。

負(fù)載狀態(tài)周期性更新。本文討論的流量均衡算法利用每條路徑上的下一跳節(jié)點(diǎn)負(fù)載情況來(lái)選擇傳輸路徑。而下一跳節(jié)點(diǎn)的負(fù)載情況由鄰節(jié)點(diǎn)本地產(chǎn)生和發(fā)布，如果要適時(shí)更新記錄鄰節(jié)點(diǎn)的負(fù)載程度又會(huì)造成大量的更新包，因而，本文采取周期性更新。更新周期和LSU包更新周期同步，對(duì)LSU包進(jìn)行處理，加入本地節(jié)點(diǎn)負(fù)載狀態(tài)。鄰節(jié)點(diǎn)接收到LSU包后取出負(fù)載狀態(tài)，存入鄰節(jié)點(diǎn)表中相應(yīng)位置。

CLBFSR采用獨(dú)立傳輸?shù)姆绞?。目前的流量均衡有多種實(shí)現(xiàn)方式，其中主要的有多徑分流和獨(dú)立傳輸兩種方式。采用多徑分流的方式對(duì)于大業(yè)務(wù)量、適時(shí)業(yè)務(wù)很有益處。然而基于魚(yú)眼域的選路機(jī)制只關(guān)心最鄰近幾條節(jié)點(diǎn)的情況，對(duì)于后續(xù)節(jié)點(diǎn)的選路并不確定。如果采用多徑分流的方式，后續(xù)節(jié)點(diǎn)仍有可能匯聚，實(shí)際效果并不好，而且隨著流量向下越分越細(xì)，旁路過(guò)多，數(shù)據(jù)流往往不可預(yù)測(cè)，延時(shí)反而會(huì)增大。所以，CLBFSR不采取多徑分流的方式進(jìn)行流量均衡。

CLBFSR路由協(xié)議主要實(shí)現(xiàn)的功能有：

（1）流量控制，避免向重負(fù)載的節(jié)點(diǎn)發(fā)包，降低沖突和丟包率。

（2）擁塞控制，當(dāng)周圍的路徑都處于重負(fù)載時(shí)，增大發(fā)包間隔。

1.1 代價(jià)函數(shù)的計(jì)算

本文討論的流量均衡算法同時(shí)考慮了鏈路丟包率的影響，根據(jù)負(fù)載程度對(duì)包率進(jìn)行加權(quán)得到代價(jià)函數(shù)，因而，在從MAC層提取流量負(fù)載時(shí)同時(shí)統(tǒng)計(jì)節(jié)點(diǎn)之間鏈路的丟包情況，并記錄在鄰節(jié)點(diǎn)表中。

（1）流量：根據(jù)周期T內(nèi)本地節(jié)點(diǎn)收、發(fā)的時(shí)隙數(shù)結(jié)合負(fù)載程度U來(lái)衡量，由本地節(jié)點(diǎn)統(tǒng)計(jì)得到：

表1 節(jié)點(diǎn)之間鏈路的狀態(tài)

（2）負(fù)載程度：指一個(gè)周期內(nèi)節(jié)點(diǎn)的資源占用率，如（1）所示。

其中W指節(jié)點(diǎn)可用的資源總數(shù)，這里用一個(gè)周期內(nèi)可以收發(fā)的時(shí)隙數(shù)計(jì)算，可表示為（2）。

所以，負(fù)載程度可表示為：

（3）根據(jù)U劃分負(fù)載狀態(tài)及等級(jí)。

（4）代價(jià)函數(shù)：

β代表鏈路丟包率，x的取值決定了β的權(quán)重，x的取值和劃分的等級(jí)數(shù)共同影響代價(jià)函數(shù)的逼近度，根據(jù)下圖可以看出等級(jí)劃分的越細(xì)膩，重負(fù)載流量對(duì)權(quán)重的影響越明顯。下表列出了當(dāng)x=2、3、4時(shí)在各個(gè)取值點(diǎn)的數(shù)值：

表2 重負(fù)載流量對(duì)權(quán)重的影響

根據(jù)上表所示，結(jié)合我們劃分的八級(jí)等級(jí)，我們認(rèn)為 x=3的權(quán)值分布更為合理一些。

1.2 負(fù)載信息的存儲(chǔ)

（1）鄰節(jié)點(diǎn)負(fù)載程度的存儲(chǔ)

本地節(jié)點(diǎn)在鄰節(jié)點(diǎn)表中對(duì)每一鄰節(jié)點(diǎn)增加 3bit，用來(lái)記錄上一周期鄰節(jié)點(diǎn)負(fù)載程度。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在更新周期結(jié)束時(shí)，統(tǒng)計(jì)自己的負(fù)載程度，并隨著LSU包一起向鄰節(jié)點(diǎn)發(fā)布。本地節(jié)點(diǎn)收到鄰節(jié)點(diǎn)的LSU包后取出鄰節(jié)點(diǎn)負(fù)載信息，存儲(chǔ)在鄰節(jié)點(diǎn)表的相應(yīng)位置。

（2）在LSU包中增加本地負(fù)載程度信息

當(dāng)LSU更新周期到時(shí)，本地節(jié)點(diǎn)將本地topo表按上表形式寫(xiě)入LSU包內(nèi)。寫(xiě)數(shù)據(jù)過(guò)程中監(jiān)控寫(xiě)入的節(jié)點(diǎn)是否是本地節(jié)點(diǎn)，在第一次出現(xiàn)本地節(jié)點(diǎn)的條目中寫(xiě)入本地負(fù)載程度。

當(dāng)本地節(jié)點(diǎn)收到鄰節(jié)點(diǎn)的LSU更新包時(shí)，讀數(shù)據(jù)的時(shí)候監(jiān)控讀到的源節(jié)點(diǎn)是否是發(fā)包節(jié)點(diǎn)，在第一次出現(xiàn)發(fā)包節(jié)點(diǎn)條目的時(shí)候解析出發(fā)送鄰節(jié)點(diǎn)的負(fù)載程度，然后寫(xiě)入鄰節(jié)點(diǎn)表的相應(yīng)位置。

圖2 鄰節(jié)點(diǎn)表中負(fù)載程度的存儲(chǔ)

圖3 寫(xiě)入本地負(fù)載程度的topo包格式

2 算法流程

（1）初始化階段，流量均衡模塊在已經(jīng)生成鄰節(jié)點(diǎn)表和路由表的基礎(chǔ)上進(jìn)行初始化。各節(jié)點(diǎn)根據(jù)路由表生成階段統(tǒng)計(jì)得到的負(fù)載程度選擇傳輸路徑。對(duì)于新入網(wǎng)的節(jié)點(diǎn)，應(yīng)該將其本地負(fù)載U和鏈路丟包率β都置0，然后通過(guò)入網(wǎng)過(guò)程更新這兩個(gè)參數(shù)。

（2）當(dāng)新的周期到來(lái)時(shí)，首先計(jì)算作為傳輸路徑的主路由上的下一跳負(fù)載程度U1和可靠性函數(shù)f1（x）。如果下一跳節(jié)點(diǎn)負(fù)載狀態(tài)是輕負(fù)載，仍然選用該路徑作為傳輸路徑，不做進(jìn)一步運(yùn)算，等待下一個(gè)周期到來(lái)；如果下一跳節(jié)點(diǎn)負(fù)載狀態(tài)是中度以上負(fù)載，則繼續(xù)計(jì)算其他鄰節(jié)點(diǎn)負(fù)載程度Ui和可靠性函數(shù)fi（x）。如果負(fù)載狀態(tài)已經(jīng)進(jìn)入了重負(fù)載范圍，在轉(zhuǎn)向計(jì)算另一路徑負(fù)載程度的同時(shí)還要觸發(fā)擁塞控制子模塊中的開(kāi)啟判斷“與門”，等待算法進(jìn)一步判斷。

（3）判斷備用路由上的下一跳節(jié)點(diǎn)是否輕負(fù)載。若是，對(duì)比各條路徑上的可靠性函數(shù)。根據(jù)Dijistra最優(yōu)路徑選擇算法計(jì)算出考慮負(fù)載后的最短路徑（代價(jià)函數(shù)最?。?，下一周期切換傳輸路徑到備用路由；若不是，則繼續(xù)判斷負(fù)載是否為重負(fù)載，如果是則觸發(fā)擁塞控制與門。

（4）當(dāng)擁塞控制模塊與門的所有輸入均為是（即“1”）的時(shí)候，開(kāi)啟擁塞控制模塊，告訴數(shù)據(jù)發(fā)送模塊增大發(fā)包間隔，從而減少發(fā)送流量，避免擁塞。

（5）當(dāng)一個(gè)周期結(jié)束時(shí)本地節(jié)點(diǎn)統(tǒng)計(jì)收、發(fā)片數(shù)S和R，然后計(jì)算出本地節(jié)點(diǎn)該周期內(nèi)的負(fù)載程度，按照等級(jí)進(jìn)行編碼，等到需要發(fā)送LSU更新包時(shí)將負(fù)載程度編碼C按照的方法寫(xiě)入LSU包相應(yīng)得位置，向鄰節(jié)點(diǎn)發(fā)送。當(dāng)本地節(jié)點(diǎn)收到鄰節(jié)點(diǎn)的LSU包時(shí)相應(yīng)得解析出鄰節(jié)點(diǎn)的負(fù)載程度編碼，寫(xiě)入鄰節(jié)點(diǎn)表中。然后進(jìn)行新一輪的判斷。

3 仿真分析

為了驗(yàn)證算法的可行性，筆者進(jìn)行了仿真試驗(yàn)。

3.1 仿真環(huán)境

仿真基于MIL3公司的網(wǎng)絡(luò)仿真平臺(tái)OPNET 11.5，OPNET已對(duì)包括TORA，DSR，AODV等Ad Hoc路由協(xié)議建模并將其集成在標(biāo)準(zhǔn)庫(kù)中，因而基于 OPNET能夠保證仿真的準(zhǔn)確性。

仿真場(chǎng)景的網(wǎng)絡(luò)拓?fù)鋱D如圖1所示：7個(gè)移動(dòng)節(jié)點(diǎn)分布在3.5km×3.5km的空間內(nèi)，其中SOURCE（192.10.1.4）為業(yè)務(wù)源節(jié)點(diǎn)，仿真持續(xù)時(shí)間 500秒，從仿真時(shí)間 100s開(kāi)始向DESTINATION（192.10.1.1）發(fā)送數(shù)據(jù)。源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間有兩條路徑可以選擇：

SOURCE-> intermediate_node_3-> DESTINATION；

SOURCE-> intermediate_node_2-> intermediate_node_1->DESTINATION.

另外，節(jié)點(diǎn)SOURCE_0（192.10.1.6）和DESTINATION_0（192.10.1.7）為中間節(jié)點(diǎn) node_3接收范圍內(nèi)的干擾節(jié)點(diǎn)，SOURCE_0有大量的數(shù)據(jù)流也要通過(guò) node_3傳遞到DESTINATION_0，從而導(dǎo)致node_3 的負(fù)載程度上升。

MAC層采用IEEE 802.11標(biāo)準(zhǔn)，通信方式為全雙工，傳輸業(yè)務(wù)流選取CBR恒定比特率。

3.2 仿真過(guò)程及分析

筆者首先設(shè)置SOURCE和SOURCE_0以發(fā)包間隔1000ms，每包固定長(zhǎng)度為2048bits分別向DESTINATION和DESTINATION_0發(fā)包。圖4是網(wǎng)絡(luò)端到端時(shí)延。通過(guò)圖4可以看出在網(wǎng)絡(luò)流量較低時(shí)，對(duì)比CLBFSR（實(shí)線）、FSR（虛線加三角）和AODV（點(diǎn)虛線）的表現(xiàn)，我們發(fā)現(xiàn)三種協(xié)議端到端延時(shí)基本相近，都保持在0.01到0.0125之間。AODV由于是被動(dòng)按需式路由，存在“請(qǐng)求”“應(yīng)答”機(jī)制，所以延時(shí)略高于其他二者。CLBFSR在低流量時(shí)不進(jìn)行均衡，因而路由過(guò)程和傳統(tǒng)的FSR 一樣，二者差異不大。

圖4 發(fā)包間隔1000ms時(shí)網(wǎng)絡(luò)端到端延時(shí)

當(dāng)筆者將干擾節(jié)點(diǎn)SOURCE_0發(fā)包間隔減小為250ms時(shí)，即發(fā)包速率提高到每秒40包，收集到端到端延時(shí)和全網(wǎng)丟包率如圖6、圖7。圖5所示的是中間節(jié)點(diǎn)node_2（即SOURCE到DESTINATION的第二條路徑上的下一跳）的流量負(fù)載曲線。

圖5 發(fā)包間隔250ms時(shí)流量圖

圖6 發(fā)包間隔250ms時(shí)丟包率

通過(guò)圖5表示，在傳統(tǒng)的FSR路由協(xié)議中node_2所經(jīng)過(guò)的路徑上流量趨近于零，第二條路徑?jīng)]有被使用，兩個(gè)數(shù)據(jù)源節(jié)點(diǎn)均選用了node_3節(jié)點(diǎn)傳輸，數(shù)據(jù)包在node_3發(fā)生碰撞，從而導(dǎo)致FSR丟包率急劇上升如圖6中所示。在AODV路由協(xié)議中，路由選擇也是依據(jù)最短跳數(shù)決定，因而SOURCE選出的下一跳往往仍是node_3，但當(dāng)AODV的丟包率達(dá)到一定程度時(shí)，可能出現(xiàn)AODV的“路由請(qǐng)求”包不能收到node_3的“應(yīng)答”，短時(shí)間內(nèi)會(huì)迂回到node_2—node_1上去，因而出現(xiàn)了幾個(gè)波動(dòng)。

圖5中實(shí)線所示的是經(jīng)過(guò)流量均衡的CLBFSR算法，可以看到中間節(jié)點(diǎn)node_2承擔(dān)了一部分流量，當(dāng)源節(jié)點(diǎn)發(fā)現(xiàn)node_3負(fù)載增加到中度負(fù)載時(shí)，下一個(gè)周期內(nèi)將會(huì)把一部分流量發(fā)往node_2，選用第二條路徑，減小包在node_3的沖突，因而我們可以看到圖6中CLBFSR的丟包率遠(yuǎn)遠(yuǎn)低于FSR和AODV。另外我們注意當(dāng)源節(jié)點(diǎn)的流量路由到node_2上時(shí)，node_3的負(fù)載等級(jí)會(huì)下降，從而可能導(dǎo)致下一個(gè)周期源節(jié)點(diǎn)重新選擇node_3為下一跳，所以我們看到圖5中CLBFSR中node_2上的流量負(fù)載會(huì)出現(xiàn)連續(xù)的起伏波動(dòng)。

圖7所示的是發(fā)包間隔250ms時(shí)網(wǎng)絡(luò)端到端延時(shí)。我們看到流量負(fù)載變大時(shí)，F(xiàn)SR的延時(shí)大約在0.018秒；流量均衡CLBFSR比FSR低10%左右，大約在0.15附近；而AODV的延時(shí)依然最大，上升到了0.02秒之上。從上述幾個(gè)指標(biāo)看經(jīng)過(guò)流量均衡后的CLBFSR算法的確可以減少數(shù)據(jù)包沖突，降低丟包率和端到端延時(shí)，達(dá)到全局優(yōu)化的效果。

圖7 發(fā)包間隔250ms時(shí)網(wǎng)絡(luò)端到端延時(shí)

4 結(jié)束語(yǔ)

傳統(tǒng)的FSR算法沒(méi)有考慮節(jié)點(diǎn)流量情況，可能造成節(jié)點(diǎn)負(fù)載過(guò)重，導(dǎo)致發(fā)包沖突，網(wǎng)絡(luò)資源得不到充分利用。本文提出了基于流量均衡的CLBFSR算法，根據(jù)各節(jié)點(diǎn)自身的業(yè)務(wù)量產(chǎn)生負(fù)載程度，通過(guò)周期交換通知鄰近節(jié)點(diǎn)，從而在鄰節(jié)點(diǎn)下一周期發(fā)包時(shí)給出路選擇參考。這種方法可以避免部分節(jié)點(diǎn)負(fù)載過(guò)重導(dǎo)致的沖突和丟包，從全局角度實(shí)現(xiàn)了流量均衡，能夠減小傳輸延時(shí)，提高網(wǎng)絡(luò)吞吐量。