MLSRP：一種面向Ad Hoc網(wǎng)絡(luò)的路由協(xié)議

趙洪巖，譚小波，徐 飛

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110159)

Ad Hoc 網(wǎng)絡(luò)應(yīng)用領(lǐng)域包含軍事通信、災(zāi)后緊急救援、傳感器網(wǎng)絡(luò)、局域網(wǎng)與個域網(wǎng)、車輛通信、與蜂窩系統(tǒng)結(jié)合等[1]，因此成為網(wǎng)絡(luò)研究領(lǐng)域的熱門話題。Ad Hoc 網(wǎng)絡(luò)應(yīng)用層次管理對整個網(wǎng)絡(luò)的移動節(jié)點(diǎn)分簇，實(shí)現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)分層，有助于對整個網(wǎng)絡(luò)進(jìn)行集中管理和提高網(wǎng)絡(luò)的可擴(kuò)展性[2]。在分簇網(wǎng)絡(luò)結(jié)構(gòu)中，由于簇間節(jié)點(diǎn)比較多且節(jié)點(diǎn)間相對移動性比較高，鏈路容易發(fā)生斷裂，所以采用路由維護(hù)開銷小的按需路由協(xié)議[3]。傳統(tǒng)的按需路由協(xié)議如按需距離矢量路由協(xié)議(AODV)協(xié)議[4]在建立路由時只建立單一路徑，使用此單一路徑傳輸數(shù)據(jù)，在負(fù)載較大時容易產(chǎn)生擁塞，降低網(wǎng)絡(luò)吞吐量?；贏ODV協(xié)議的多徑路由協(xié)議如按需多徑距離矢量路由協(xié)議(AOMDV)協(xié)議[5]，使用的是在主路徑失效后切換備份路徑繼續(xù)通信的策略，而不是使用負(fù)載分配、并行傳輸?shù)牟呗?，沒有真正意義上起到負(fù)載均衡的作用。AOMDV 協(xié)議在尋找下一跳時沒有考慮相鄰節(jié)點(diǎn)間的綜合移動性[6]，在分簇網(wǎng)絡(luò)結(jié)構(gòu)中建立的路由穩(wěn)定度低，鏈路容易發(fā)生斷裂。本文在 AODV 協(xié)議的基礎(chǔ)上設(shè)計(jì)一種適用于分簇網(wǎng)絡(luò)結(jié)構(gòu)的簇間路由協(xié)議，該協(xié)議具有增大鏈路穩(wěn)定性、均衡負(fù)載的特點(diǎn)。

1 分簇網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)介紹

1.1 分簇結(jié)構(gòu)的網(wǎng)絡(luò)模型

Ad Hoc 的分簇結(jié)構(gòu)的網(wǎng)路模型由簇首、普通簇成員和網(wǎng)關(guān)構(gòu)成[7]。通信分為簇內(nèi)通信與簇間通信[8]。網(wǎng)絡(luò)模型如圖1所示。

1.2 AODV 協(xié)議在分簇網(wǎng)絡(luò)結(jié)構(gòu)中的問題

圖2為AODV協(xié)議路由回復(fù)報文(RREP)傳輸過程。

如圖2所示，源節(jié)點(diǎn)S對目的節(jié)點(diǎn)D進(jìn)行路由查找，在找到節(jié)點(diǎn)D后，節(jié)點(diǎn)D向節(jié)點(diǎn)S發(fā)送RREP報文。假設(shè)節(jié)點(diǎn)C的RREP報文先到節(jié)點(diǎn)A，節(jié)點(diǎn)B的RREP報文后到節(jié)點(diǎn)A，此時節(jié)點(diǎn)A在AODV協(xié)議中，如果滿足以下兩個條件中的任意一個將更新前向路由。

(1)此RREP報文中的序列號比自身現(xiàn)有表項(xiàng)中D節(jié)點(diǎn)的序列號大；

(2)此RREP報文中的序列號與自身現(xiàn)有表項(xiàng)中節(jié)點(diǎn)D的序列號相同，但是此RREP報文中到節(jié)點(diǎn)D的跳數(shù)比自身現(xiàn)有表項(xiàng)中到節(jié)點(diǎn)D的跳數(shù)小。

如果不滿足以上兩點(diǎn)，節(jié)點(diǎn)A將節(jié)點(diǎn)B的RREP報文直接丟棄。

根據(jù)上述可知，AODV協(xié)議在尋找下一跳節(jié)點(diǎn)時，僅根據(jù)序列號和跳數(shù)建立的前向路由不一定是最穩(wěn)定的，而且路徑單一，當(dāng)鏈路發(fā)生斷裂時，將會重新尋找路由或進(jìn)行路由修復(fù)，將造成可靠性降低，端到端的時延增大，且骨干網(wǎng)中的每個節(jié)點(diǎn)參與簇內(nèi)和簇外路由，簇首節(jié)點(diǎn)本身的負(fù)載很大，使用單一路徑路由還會造成負(fù)載不均，容易造成網(wǎng)路擁塞，降低帶寬利用率。

所以，本文在AODV協(xié)議的基礎(chǔ)上提出多路徑鏈路穩(wěn)定路由協(xié)議(Multipath link stable routing protocol，MLSRP)。

2 多路徑鏈路穩(wěn)定路由協(xié)議設(shè)計(jì)

2.1 MLSRP的路由度量設(shè)計(jì)

MLSRP的路由度量需要考慮以下兩種因素：

(1)鏈路綜合穩(wěn)定性：是指從目的節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的綜合穩(wěn)定性。鏈路綜合穩(wěn)定性越大，說明該鏈路越不容易失效；

(2)節(jié)點(diǎn)負(fù)載：是指節(jié)點(diǎn)緩存隊(duì)列中的數(shù)據(jù)長度。鏈路綜合穩(wěn)定性的定義為

(1)

式中：LCSsum表示鏈路綜合穩(wěn)定性；CSi表示兩個相鄰節(jié)點(diǎn)的綜合穩(wěn)定性。

對于一條由節(jié)點(diǎn)D到節(jié)點(diǎn)A的鏈路，綜合穩(wěn)定性為

(1)D→E→B→A

LCSsum=CSDE+CSEB+CSBA

(2)D→E→C→A

LCSsum=CSDE+CSEC+CSCA

使用節(jié)點(diǎn)負(fù)載系數(shù)來反映節(jié)點(diǎn)負(fù)載的高低，其定義如式(2)所示。

(2)

式中：Li表示節(jié)點(diǎn)負(fù)載系數(shù)；L(i)表示節(jié)點(diǎn)i的數(shù)據(jù)鏈路層緩沖隊(duì)列中正在等待處理報文的實(shí)際長度；L_MAC表示節(jié)點(diǎn)i數(shù)據(jù)鏈路層緩沖隊(duì)列能夠支持的傳輸報文的最大長度。

從式(2)可知，Li的值越大，表明節(jié)點(diǎn)當(dāng)前時刻緩沖隊(duì)列中需要處理的報文數(shù)量越多，對應(yīng)的節(jié)點(diǎn)負(fù)載程度也越高。

綜上分析可以得出新的路由度量Metric的定義：對一條由節(jié)點(diǎn)i到節(jié)點(diǎn)j的鏈路Li，j，該鏈路的Metric值定義為

(3)

當(dāng)LCSsum的值越大，表示這條鏈路越穩(wěn)定，Metric的值也就越大。當(dāng)負(fù)載較小時，對應(yīng)的負(fù)載系數(shù)Li較小，Metric的值也就越大。

2.2 路由請求與路由應(yīng)答

路由請求的過程與AODV協(xié)議一致，本文不做贅述。

MLSRP的路由應(yīng)答流程如圖3所示，流程描述如下。

(1)目的節(jié)點(diǎn)收到路由請求報文(RREQ)后，將Li的初始值設(shè)為0，將LCSsum的初始值設(shè)為CS，CS為與之對應(yīng)的下游鄰居節(jié)點(diǎn)的綜合穩(wěn)定性，生成對應(yīng)的RREP報文，然后反向發(fā)送到對應(yīng)的下游鄰居節(jié)點(diǎn)。

(2)下游鄰居節(jié)點(diǎn)收到RREP報文，判斷該節(jié)點(diǎn)是否為源節(jié)點(diǎn)，如果是源節(jié)點(diǎn)則停止轉(zhuǎn)發(fā)，準(zhǔn)備發(fā)送數(shù)據(jù)；否則，為中間節(jié)點(diǎn)。每個中間節(jié)點(diǎn)只要接收到RREP報文后，就將與下游鄰居節(jié)點(diǎn)的CS加上RREP報文中LCSsum，更新RREP報文中LCSsum，然后查看自身的Li；如果自身的Li大于RREP報文中的Li，更新RREP報文中Li，否則RREP報文中的Li不變，然后沿著反向路由廣播出去，并建立前向路由，重復(fù)(2)。

2.3 負(fù)載分配

節(jié)點(diǎn)S向節(jié)點(diǎn)D發(fā)送數(shù)據(jù)的過程如圖4所示。

負(fù)載分配的基本原理如下：

每個節(jié)點(diǎn)收到目的節(jié)點(diǎn)回復(fù)的多個RREP報文后，從每個收到的RREP報文中獲取相應(yīng)信息，計(jì)算出各條鏈路的Metric。根據(jù)所有Metric計(jì)算與下游相鄰節(jié)點(diǎn)間鏈路的負(fù)載比例，并將負(fù)載比例記錄在前向路由表中。在發(fā)送數(shù)據(jù)時，按照負(fù)載比例為每條鏈路分配負(fù)載。

負(fù)載比例為某條路徑的Metric所占總Metric的比例，其定義為

(4)

式中：LAi表示鏈路的負(fù)載比例；Metrici表示每條鏈路的路由度量。

2.4 路由維護(hù)

在源節(jié)點(diǎn)第一次發(fā)送數(shù)據(jù)前，根據(jù)負(fù)載比例計(jì)算每條鏈路的總負(fù)載比例和路徑修復(fù)標(biāo)志位。發(fā)送數(shù)據(jù)時，將鏈路總負(fù)載比例放入IP包頭中選項(xiàng)位置，發(fā)送數(shù)據(jù)時經(jīng)過的每個節(jié)點(diǎn)都計(jì)算一次每條鏈路的總負(fù)載比例和路徑修復(fù)標(biāo)志位，并將路徑修復(fù)標(biāo)志位放入前向路由表中。

每條鏈路的總負(fù)載比例定義式為

(5)

式中TLA表示該鏈路的總負(fù)載比例。

路徑修復(fù)標(biāo)志位F，其定義式為

(6)

式中n表示從源節(jié)點(diǎn)到目的節(jié)點(diǎn)路徑的個數(shù)。

如果某條鏈路失效，將執(zhí)行如下操作進(jìn)行動態(tài)調(diào)整負(fù)載。

(1)如果失效鏈路上游節(jié)點(diǎn)為源節(jié)點(diǎn)，源節(jié)點(diǎn)重新進(jìn)行路由查找，廣播RREQ報文；否則轉(zhuǎn)(2)。

(2)查看前向路由表的路徑修復(fù)標(biāo)志位，如果路徑修復(fù)標(biāo)志位為1，說明此路徑重要，斷裂處的上游節(jié)點(diǎn)進(jìn)行本地修復(fù)，轉(zhuǎn)(3)；否則轉(zhuǎn)(5)。

(3)如果修復(fù)成功，向源節(jié)點(diǎn)發(fā)送RREP報文，經(jīng)過的每個節(jié)點(diǎn)都更新負(fù)載比例，重新為每條鏈路分配負(fù)載；否則轉(zhuǎn)(4)。

(4)如果修復(fù)失敗，向源節(jié)點(diǎn)發(fā)送路由錯誤(RERR)報文，源節(jié)點(diǎn)重新發(fā)起路由查找。

(5)如果路徑修復(fù)標(biāo)志位為0，說明此路徑次要，不修復(fù)。

路由維護(hù)流程如圖5所示。

2.5 相關(guān)報文與路由表設(shè)計(jì)

MLSRP的RREP報文與前向路由表設(shè)計(jì)如下。

(1)路由回復(fù)報文

為實(shí)現(xiàn)MLSRP，在AODV協(xié)議的RREP報文基礎(chǔ)上增加了LCSsum字段和Li字段。RREP報文格式如圖6所示。

(2)前向路由表

節(jié)點(diǎn)在接收RREP報文后建立前向路由表，在AODV協(xié)議的前向路由表基礎(chǔ)上增加了負(fù)載比例LAi字段和路徑修復(fù)標(biāo)志位F字段。前向路由表格式如表1所示。

表1 前向路由表格式

3 仿真與驗(yàn)證

3.1 仿真場景與參數(shù)設(shè)置

采用NS-2平臺[9]對提出的路由設(shè)計(jì)進(jìn)行仿真。網(wǎng)絡(luò)的仿真場景是20km×20km的自組織網(wǎng)絡(luò)，生成100個節(jié)點(diǎn)。節(jié)點(diǎn)的最大通信半徑設(shè)置為300m，每個節(jié)點(diǎn)的初始運(yùn)動速度設(shè)置為2m/s，其中設(shè)置節(jié)點(diǎn)的最小移動速度為2m/s，最大移動速度為30m/s，并向同一方向移動，每個節(jié)點(diǎn)的間距為100m。網(wǎng)絡(luò)負(fù)載以CBR[10]的形式生成。使用基于綜合移動性預(yù)測的分簇算法[6]生成分簇網(wǎng)絡(luò)結(jié)構(gòu)。對多路徑鏈路穩(wěn)定路由協(xié)議(MLSRP)、傳統(tǒng)的AODV及傳統(tǒng)的AOMDV的端到端的時延和吞吐量進(jìn)行仿真。

3.2 仿真結(jié)果分析

(1)對于多種協(xié)議的平均端到端時延仿真結(jié)果如圖7所示。在低負(fù)載的情況下，時延都較小且呈上升后穩(wěn)定的趨勢，但MLSRP的端到端時延高于其它的兩種協(xié)議；這是由于MLSRP考慮的因素很多，需要計(jì)算節(jié)點(diǎn)間綜合穩(wěn)定性和負(fù)載系數(shù)，從而帶來更大的基礎(chǔ)時延。隨著負(fù)載逐漸增大，MLSRP的端到端時延小于其它兩種路由協(xié)議；這是由于MLSRP在尋找下一跳節(jié)點(diǎn)時考慮節(jié)點(diǎn)間的綜合穩(wěn)定度，尋找到的下一跳節(jié)點(diǎn)穩(wěn)定度高，鏈路不易斷開，減少了觸發(fā)路由維護(hù)機(jī)制的次數(shù)，從而減小了端到端的時延。

(2)對于多種協(xié)議的網(wǎng)絡(luò)吞吐量仿真結(jié)果如圖8所示，隨著負(fù)載的增加，MLSRP與AOMDV協(xié)議的吞吐量都比AODV協(xié)議高，這是由于MLSRP與AODV協(xié)議都是多路徑路由協(xié)議，降低了單位時間內(nèi)重新建立路由的次數(shù)。MLSRP的吞吐量比AOMDV協(xié)議的吞吐量高；這是由于MLSRP使用負(fù)載分配和并行傳輸?shù)牟呗裕ㄟ^路由應(yīng)答獲取不同路徑的擁塞程度信息，動態(tài)調(diào)整不同路徑的負(fù)載，使網(wǎng)絡(luò)負(fù)載均衡，提高了網(wǎng)絡(luò)吞吐量和降低網(wǎng)絡(luò)擁塞程度，實(shí)現(xiàn)網(wǎng)絡(luò)資源利用率最大化。

4 結(jié)論

MLSRP將鏈路綜合穩(wěn)定性與節(jié)點(diǎn)負(fù)載作為路由度量，根據(jù)負(fù)載比例為多條路徑分配負(fù)載，根據(jù)鏈路的總負(fù)載比例修復(fù)鏈路并及時調(diào)整負(fù)載，所以該協(xié)議具有鏈路穩(wěn)定性高、負(fù)載均衡的特點(diǎn)，能夠降低端到端時延，增大網(wǎng)絡(luò)吞吐量。