一種基于跨層均衡的Ad Hoc網絡路由算法

王 碩 楊 毅 侯 森

（1.河南牧業經濟學院計算機應用系 河南 450044；2.國家數字交換系統工程技術研究中心 河南 450002）

0 引言

Ad Hoc網絡是一種無中心自組織的多跳無線網絡，它不需要依據任何固定設施為基礎，無中心，每個節點相互平等，可以隨意移動，網絡可隨時隨地組建和更改。隨著人們對個人通信日益增長的需求，Ad Hoc網絡的這些特性越來越被人們所重視。關于Ad Hoc網絡的路由選擇協議的研究正在成為目前研究的一個熱點。

魚眼域路由協議（FSR）是一種應用于Ad Hoc網絡的主動式分級路由協議。FSR使用了“魚眼域”思想，利用魚眼視覺的特點，在不同魚眼域中的節點以不同的頻率向鄰居節點廣播鏈路更新信息，這能夠大大減少鏈路狀態更新信息，從而降低了路由開銷。但是FSR算法在路徑選擇時，基于Dijistra最優路徑選擇算法根據跳數或鏈路質量選擇路徑，而沒有考慮網絡中節點的負載情況，往往會有多條路徑同時選中少數中間節點。當這些路徑上同時有數據包發送時，將會造成中間節點負載過重，發包沖突機會加大，丟包率上升，以至于網絡性能受制于中間節點負載容量的瓶頸。

圖1 中間節點i被兩條路徑同時選中的拓撲圖

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

1 CLBFSR路由協議算法

CLBFSR路由協議是由傳統的FSR算法演變而來，CLBFSR算法利用跨層（cross-layer）的思想，周期性的從MAC層收集本地節點流量負載情況，劃分負載等級。在計算和生成路由表時，將鄰節點的負載情況作為權重計算下一跳節點的代價函數f（x）。這樣當節點要發送數據包時，就可以根據它的鄰節點負載程度以及代價函數f（x）動態地選擇下一跳，從而避免向重負載節點發送數據。

負載狀態周期性更新。本文討論的流量均衡算法利用每條路徑上的下一跳節點負載情況來選擇傳輸路徑。而下一跳節點的負載情況由鄰節點本地產生和發布，如果要適時更新記錄鄰節點的負載程度又會造成大量的更新包，因而，本文采取周期性更新。更新周期和LSU包更新周期同步，對LSU包進行處理，加入本地節點負載狀態。鄰節點接收到LSU包后取出負載狀態，存入鄰節點表中相應位置。

CLBFSR采用獨立傳輸的方式。目前的流量均衡有多種實現方式，其中主要的有多徑分流和獨立傳輸兩種方式。采用多徑分流的方式對于大業務量、適時業務很有益處。然而基于魚眼域的選路機制只關心最鄰近幾條節點的情況，對于后續節點的選路并不確定。如果采用多徑分流的方式，后續節點仍有可能匯聚，實際效果并不好，而且隨著流量向下越分越細，旁路過多，數據流往往不可預測，延時反而會增大。所以，CLBFSR不采取多徑分流的方式進行流量均衡。

CLBFSR路由協議主要實現的功能有：

（1）流量控制，避免向重負載的節點發包，降低沖突和丟包率。

（2）擁塞控制，當周圍的路徑都處于重負載時，增大發包間隔。

1.1 代價函數的計算

本文討論的流量均衡算法同時考慮了鏈路丟包率的影響，根據負載程度對包率進行加權得到代價函數，因而，在從MAC層提取流量負載時同時統計節點之間鏈路的丟包情況，并記錄在鄰節點表中。

（1）流量：根據周期T內本地節點收、發的時隙數結合負載程度U來衡量，由本地節點統計得到：

表1 節點之間鏈路的狀態

（2）負載程度：指一個周期內節點的資源占用率，如（1）所示。

其中W指節點可用的資源總數，這里用一個周期內可以收發的時隙數計算，可表示為（2）。

所以，負載程度可表示為：

（3）根據U劃分負載狀態及等級。

（4）代價函數：

β代表鏈路丟包率，x的取值決定了β的權重，x的取值和劃分的等級數共同影響代價函數的逼近度，根據下圖可以看出等級劃分的越細膩，重負載流量對權重的影響越明顯。下表列出了當x=2、3、4時在各個取值點的數值：

表2 重負載流量對權重的影響

根據上表所示，結合我們劃分的八級等級，我們認為 x=3的權值分布更為合理一些。

1.2 負載信息的存儲

（1）鄰節點負載程度的存儲

本地節點在鄰節點表中對每一鄰節點增加 3bit，用來記錄上一周期鄰節點負載程度。網絡中每個節點在更新周期結束時，統計自己的負載程度，并隨著LSU包一起向鄰節點發布。本地節點收到鄰節點的LSU包后取出鄰節點負載信息，存儲在鄰節點表的相應位置。

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

當LSU更新周期到時，本地節點將本地topo表按上表形式寫入LSU包內。寫數據過程中監控寫入的節點是否是本地節點，在第一次出現本地節點的條目中寫入本地負載程度。

當本地節點收到鄰節點的LSU更新包時，讀數據的時候監控讀到的源節點是否是發包節點，在第一次出現發包節點條目的時候解析出發送鄰節點的負載程度，然后寫入鄰節點表的相應位置。

圖2 鄰節點表中負載程度的存儲

圖3 寫入本地負載程度的topo包格式

2 算法流程

（1）初始化階段，流量均衡模塊在已經生成鄰節點表和路由表的基礎上進行初始化。各節點根據路由表生成階段統計得到的負載程度選擇傳輸路徑。對于新入網的節點，應該將其本地負載U和鏈路丟包率β都置0，然后通過入網過程更新這兩個參數。

（2）當新的周期到來時，首先計算作為傳輸路徑的主路由上的下一跳負載程度U1和可靠性函數f1（x）。如果下一跳節點負載狀態是輕負載，仍然選用該路徑作為傳輸路徑，不做進一步運算，等待下一個周期到來；如果下一跳節點負載狀態是中度以上負載，則繼續計算其他鄰節點負載程度Ui和可靠性函數fi（x）。如果負載狀態已經進入了重負載范圍，在轉向計算另一路徑負載程度的同時還要觸發擁塞控制子模塊中的開啟判斷“與門”，等待算法進一步判斷。

（3）判斷備用路由上的下一跳節點是否輕負載。若是，對比各條路徑上的可靠性函數。根據Dijistra最優路徑選擇算法計算出考慮負載后的最短路徑（代價函數最小），下一周期切換傳輸路徑到備用路由；若不是，則繼續判斷負載是否為重負載，如果是則觸發擁塞控制與門。

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

（5）當一個周期結束時本地節點統計收、發片數S和R，然后計算出本地節點該周期內的負載程度，按照等級進行編碼，等到需要發送LSU更新包時將負載程度編碼C按照的方法寫入LSU包相應得位置，向鄰節點發送。當本地節點收到鄰節點的LSU包時相應得解析出鄰節點的負載程度編碼，寫入鄰節點表中。然后進行新一輪的判斷。

3 仿真分析

為了驗證算法的可行性，筆者進行了仿真試驗。

3.1 仿真環境

仿真基于MIL3公司的網絡仿真平臺OPNET 11.5，OPNET已對包括TORA，DSR，AODV等Ad Hoc路由協議建模并將其集成在標準庫中，因而基于 OPNET能夠保證仿真的準確性。

仿真場景的網絡拓撲圖如圖1所示：7個移動節點分布在3.5km×3.5km的空間內，其中SOURCE（192.10.1.4）為業務源節點，仿真持續時間 500秒，從仿真時間 100s開始向DESTINATION（192.10.1.1）發送數據。源節點和目標節點之間有兩條路徑可以選擇：

SOURCE-> intermediate_node_3-> DESTINATION；

SOURCE-> intermediate_node_2-> intermediate_node_1->DESTINATION.

另外，節點SOURCE_0（192.10.1.6）和DESTINATION_0（192.10.1.7）為中間節點 node_3接收范圍內的干擾節點，SOURCE_0有大量的數據流也要通過 node_3傳遞到DESTINATION_0，從而導致node_3 的負載程度上升。

MAC層采用IEEE 802.11標準，通信方式為全雙工，傳輸業務流選取CBR恒定比特率。

3.2 仿真過程及分析

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

圖4 發包間隔1000ms時網絡端到端延時

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

圖5 發包間隔250ms時流量圖

圖6 發包間隔250ms時丟包率

通過圖5表示，在傳統的FSR路由協議中node_2所經過的路徑上流量趨近于零，第二條路徑沒有被使用，兩個數據源節點均選用了node_3節點傳輸，數據包在node_3發生碰撞，從而導致FSR丟包率急劇上升如圖6中所示。在AODV路由協議中，路由選擇也是依據最短跳數決定，因而SOURCE選出的下一跳往往仍是node_3，但當AODV的丟包率達到一定程度時，可能出現AODV的“路由請求”包不能收到node_3的“應答”，短時間內會迂回到node_2—node_1上去，因而出現了幾個波動。

圖5中實線所示的是經過流量均衡的CLBFSR算法，可以看到中間節點node_2承擔了一部分流量，當源節點發現node_3負載增加到中度負載時，下一個周期內將會把一部分流量發往node_2，選用第二條路徑，減小包在node_3的沖突，因而我們可以看到圖6中CLBFSR的丟包率遠遠低于FSR和AODV。另外我們注意當源節點的流量路由到node_2上時，node_3的負載等級會下降，從而可能導致下一個周期源節點重新選擇node_3為下一跳，所以我們看到圖5中CLBFSR中node_2上的流量負載會出現連續的起伏波動。

圖7所示的是發包間隔250ms時網絡端到端延時。我們看到流量負載變大時，FSR的延時大約在0.018秒；流量均衡CLBFSR比FSR低10%左右，大約在0.15附近；而AODV的延時依然最大，上升到了0.02秒之上。從上述幾個指標看經過流量均衡后的CLBFSR算法的確可以減少數據包沖突，降低丟包率和端到端延時，達到全局優化的效果。

圖7 發包間隔250ms時網絡端到端延時

4 結束語

傳統的FSR算法沒有考慮節點流量情況，可能造成節點負載過重，導致發包沖突，網絡資源得不到充分利用。本文提出了基于流量均衡的CLBFSR算法，根據各節點自身的業務量產生負載程度，通過周期交換通知鄰近節點，從而在鄰節點下一周期發包時給出路選擇參考。這種方法可以避免部分節點負載過重導致的沖突和丟包，從全局角度實現了流量均衡，能夠減小傳輸延時，提高網絡吞吐量。