基于DSR的改進(jìn)型綜合源路由協(xié)議*

祝嘉東，孫 君，許 暉，易輝躍

（1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000；2.上海無(wú)線通信研究中心，上海 200050）

0 引 言

在近年來(lái)物聯(lián)網(wǎng)技術(shù)高速發(fā)展的背景下，需要有面向物聯(lián)網(wǎng)的組網(wǎng)技術(shù)來(lái)承載網(wǎng)絡(luò)中信息傳輸?shù)墓δ?，而Mesh組網(wǎng)就是一種很好的解決方案。Mesh網(wǎng)絡(luò)具有多跳、自愈及自管理的特點(diǎn)，具有高速率、易組網(wǎng)、成本低及性能穩(wěn)定等優(yōu)勢(shì)[1]。在無(wú)線Mesh網(wǎng)絡(luò)中，路由協(xié)議是影響網(wǎng)絡(luò)性能的一個(gè)關(guān)鍵因素。無(wú)線Mesh網(wǎng)絡(luò)中的路由協(xié)議大多沿用Ad Hoc網(wǎng)絡(luò)路由協(xié)議并進(jìn)行改進(jìn)，大致分為主動(dòng)路由協(xié)議、被動(dòng)路由協(xié)議和混合路由協(xié)議三大類[2]。其中，動(dòng)態(tài)源路由（Dynamic Source Routing，DSR）協(xié)議是無(wú)線Mesh網(wǎng)絡(luò)中廣泛應(yīng)用的協(xié)議。

DSR是一種典型的源路由協(xié)議，即路由發(fā)現(xiàn)和路由維護(hù)都由源節(jié)點(diǎn)發(fā)起。在路由發(fā)現(xiàn)過(guò)程中，DSR采用泛洪機(jī)制向周?chē)?jié)點(diǎn)廣播RREQ路由請(qǐng)求分組。RREQ分組由源節(jié)點(diǎn)地址、請(qǐng)求識(shí)別碼、路由記錄和目的節(jié)點(diǎn)地址組成[3-4]，目的節(jié)點(diǎn)收到后返回RREP響應(yīng)分組。傳統(tǒng)DSR的路由發(fā)現(xiàn)過(guò)程如圖1所示。

圖1 RREQ的傳輸過(guò)程

DSR的路由發(fā)現(xiàn)遵守最小跳數(shù)準(zhǔn)則，C節(jié)點(diǎn)選擇了A-的路徑，F(xiàn)節(jié)點(diǎn)選擇了A-C-D-的路徑，最終建立路徑A-C-D-F[5]。最小跳數(shù)準(zhǔn)則的優(yōu)點(diǎn)是能夠快速建立有效路徑，缺點(diǎn)是某些處于網(wǎng)絡(luò)中心的節(jié)點(diǎn)會(huì)被一直重復(fù)使用，造成節(jié)點(diǎn)的負(fù)載過(guò)重和能量消耗過(guò)快，使得節(jié)點(diǎn)的生存時(shí)間變短，最后導(dǎo)致網(wǎng)絡(luò)的工作效率下降[6]。

目前，對(duì)于DSR協(xié)議改進(jìn)的研究，一個(gè)主要的方向是網(wǎng)絡(luò)內(nèi)的負(fù)載平衡。文獻(xiàn)[7]提出一種主動(dòng)源路由協(xié)議PSR。該協(xié)議引入機(jī)會(huì)數(shù)據(jù)轉(zhuǎn)發(fā)的思想，著重于利用最小的網(wǎng)絡(luò)開(kāi)銷(xiāo)維護(hù)最大的網(wǎng)絡(luò)拓?fù)洹Ｎ墨I(xiàn)[8]提出協(xié)作源路由協(xié)議CDS改進(jìn)傳輸路徑上的整體性能表現(xiàn)。文獻(xiàn)[9]提出了混合蟻群算法DSR，通過(guò)混合蟻群算法和禁忌算法來(lái)優(yōu)化DSR的跳數(shù)、鏈路質(zhì)量和帶寬估計(jì)。文獻(xiàn)[10]提出SMSR最短多路由算法，采用節(jié)點(diǎn)不相關(guān)的多徑路由，但未考慮路徑的負(fù)載平衡。文獻(xiàn)[11]提出了一種基于負(fù)載均衡的路由DSR-LB，引入了節(jié)點(diǎn)隊(duì)列可用率IFQ，然而未考慮保留備用路徑或多徑路由，使得路由失效時(shí)需重新建立。文獻(xiàn)[12]提出IDSR多徑路由算法，引入QoS代價(jià)函數(shù)來(lái)判斷路徑質(zhì)量，然而代價(jià)函數(shù)只考慮了隊(duì)列負(fù)載和時(shí)延。因此，為了進(jìn)一步提升網(wǎng)絡(luò)性能，對(duì)于DSR協(xié)議的設(shè)計(jì)開(kāi)發(fā)與驗(yàn)證需要進(jìn)一步深入研究。

1 改進(jìn)型源路由協(xié)議ICMSR

針對(duì)上述有關(guān)DSR的問(wèn)題分析，本文通過(guò)引入一種綜合了路徑負(fù)載率、傳輸時(shí)延和路由跳數(shù)的改進(jìn)型負(fù)載均衡機(jī)制，并加入能量狀態(tài)管理和多徑路由，提出一種改進(jìn)型綜合源路由協(xié)議（Improved Comprehensive Multipath Source Routing，ICMSR），從而更好地實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，節(jié)約網(wǎng)絡(luò)能源，提升網(wǎng)絡(luò)性能。

1.1 改進(jìn)型負(fù)載均衡機(jī)制

針對(duì)現(xiàn)有DSR協(xié)議中負(fù)載均衡存在的不足，本文提出一種改進(jìn)的負(fù)載均衡機(jī)制，并提出了綜合路徑負(fù)載率、時(shí)延計(jì)算和路由跳數(shù)的負(fù)載均衡計(jì)算方法。

1.1.1 路徑負(fù)載率

設(shè)節(jié)點(diǎn)a的負(fù)載率為L(zhǎng)a，節(jié)點(diǎn)a的接口隊(duì)列最大長(zhǎng)度為Qa，節(jié)點(diǎn)a當(dāng)前可用的接口隊(duì)列長(zhǎng)度為Pa，因此得到節(jié)點(diǎn)a的負(fù)載率為：

路徑負(fù)載率取決于路徑上的最大節(jié)點(diǎn)負(fù)載率。設(shè)Lr為路徑r的路徑負(fù)載率，因此得到路徑負(fù)載率為：

1.1.2 時(shí)延計(jì)算

時(shí)延計(jì)算也是路由選擇判據(jù)中的一個(gè)重要參數(shù)。對(duì)于本文中的時(shí)延計(jì)算方法，首先給出表達(dá)式：

其中，m表示路徑r上數(shù)據(jù)傳輸經(jīng)過(guò)的鏈路數(shù)目，i表示路徑中兩個(gè)相鄰節(jié)點(diǎn)直連的某條鏈路，Dmax表示一個(gè)預(yù)設(shè)的時(shí)延閥值。如果網(wǎng)絡(luò)內(nèi)沒(méi)有一條路徑能在時(shí)延閥值內(nèi)將數(shù)據(jù)從源節(jié)點(diǎn)傳至目的節(jié)點(diǎn)，則代表網(wǎng)絡(luò)失效，需重新進(jìn)行路由發(fā)現(xiàn)。時(shí)延計(jì)算表達(dá)式是指計(jì)算路徑r上所有相鄰節(jié)點(diǎn)之間的傳輸時(shí)延總和，與預(yù)設(shè)的時(shí)延閥值作比較，得到一個(gè)時(shí)延計(jì)算的相對(duì)值。

1.1.3 路由跳數(shù)

路由跳數(shù)的作用在于限制網(wǎng)絡(luò)內(nèi)過(guò)多的路由跳數(shù)，降低網(wǎng)絡(luò)的復(fù)雜性和傳輸時(shí)間。預(yù)設(shè)一個(gè)最大跳數(shù)閥值為hmax，對(duì)于網(wǎng)絡(luò)中的某條路徑r，跳數(shù)為hr。在節(jié)點(diǎn)能量和節(jié)點(diǎn)負(fù)載率相同的情況下，如果路由的跳數(shù)越少，則表示路徑的開(kāi)銷(xiāo)和延遲越小。因此，在負(fù)載均衡表達(dá)式中最后加入路由跳數(shù)作為一個(gè)判定機(jī)制。

設(shè)路由跳數(shù)相對(duì)值為Hr，表達(dá)式為：

1.1.4 負(fù)載均衡機(jī)制計(jì)算式

綜合上述路徑負(fù)載率、時(shí)延計(jì)算和路由跳數(shù)，改進(jìn)的負(fù)載均衡機(jī)制計(jì)算如下：

其中，α、β、γ為預(yù)設(shè)常數(shù)，且滿足α+β+γ=1，0 ≤ α,β,γ≤ 1，可根據(jù)實(shí)驗(yàn)時(shí)的實(shí)際情況進(jìn)行調(diào)整。例如，設(shè)α=β=0，γ=1，則表示負(fù)載均衡機(jī)制只比較路徑跳數(shù)情況。目的節(jié)點(diǎn)收到RREQ分組后，會(huì)根據(jù)分組信息計(jì)算出Route_Load(r)，再選擇建立路徑。

1.2 能量狀態(tài)管理

網(wǎng)絡(luò)中節(jié)點(diǎn)能量有限，而節(jié)點(diǎn)在轉(zhuǎn)發(fā)數(shù)據(jù)的過(guò)程中一直在消耗能量，節(jié)點(diǎn)能量消耗完之后會(huì)造成節(jié)點(diǎn)失效使得傳輸中斷，降低了網(wǎng)絡(luò)生存時(shí)間。因此，為了延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間，需要引入一種能量狀態(tài)的監(jiān)控機(jī)制。

能量模型如下。設(shè)當(dāng)前時(shí)刻的能量狀態(tài)為Estate，則：

其中，Ecurrent節(jié)點(diǎn)當(dāng)前能量，Etotal為節(jié)點(diǎn)總能量。Ecurrent的表達(dá)式為：

節(jié)點(diǎn)的能量工作狀態(tài)分為4種——發(fā)送、接收、空閑和缺電。節(jié)點(diǎn)發(fā)送分組時(shí)表示節(jié)點(diǎn)處于發(fā)送狀態(tài)；節(jié)點(diǎn)接收分組時(shí)表示節(jié)點(diǎn)處于接收狀態(tài)；節(jié)點(diǎn)既不發(fā)送也未接收時(shí)為空閑狀態(tài)；當(dāng)節(jié)點(diǎn)的能量消耗的一定水平以下時(shí)，節(jié)點(diǎn)進(jìn)入缺電狀態(tài)。

因此，將節(jié)點(diǎn)的能量狀態(tài)分為“能量正常”和“能量不足”兩種等級(jí)，并設(shè)置一個(gè)能量門(mén)檻值Ethreshold。當(dāng)Estate≥Ethreshold時(shí)，則判定為節(jié)點(diǎn)“能量正?！保划?dāng)Estate＜Ethreshold時(shí)，則判定為節(jié)點(diǎn)“能量不足”，此時(shí)節(jié)點(diǎn)不再參與路由分組與數(shù)據(jù)節(jié)點(diǎn)的轉(zhuǎn)發(fā)。例如，可將Ethreshold設(shè)置為20%，保證節(jié)點(diǎn)的能量處于可工作狀態(tài)。當(dāng)網(wǎng)絡(luò)啟動(dòng)路由發(fā)現(xiàn)時(shí)，需首先檢查節(jié)點(diǎn)的能量狀態(tài)，以保證節(jié)點(diǎn)之后能正常工作。

1.3 ICMSR的工作流程

1.3.1 路由發(fā)現(xiàn)

基于DSR的改進(jìn)路由協(xié)議，由于同樣采用了源路由思想，因此在路由發(fā)現(xiàn)過(guò)程中也分別包含了對(duì)源節(jié)點(diǎn)、中間節(jié)點(diǎn)及目的節(jié)點(diǎn)的操作。圖2給出了路由發(fā)現(xiàn)流程圖。

圖2 路由發(fā)現(xiàn)流程

（1）源節(jié)點(diǎn)想要發(fā)送數(shù)據(jù)到目的節(jié)點(diǎn)，先檢查自身路由表中有無(wú)到目的節(jié)點(diǎn)的路由。如果有則直接發(fā)送；如果沒(méi)有則啟動(dòng)路由發(fā)現(xiàn)，廣播發(fā)送RREQ分組。本文的改進(jìn)路由協(xié)議在傳統(tǒng)DSR的RREQ分組基礎(chǔ)上，需加入新的字段Load Rate、Delay和Hop，用來(lái)記錄負(fù)載信息，如圖3所示。

圖3 改進(jìn)的RREQ分組

（2）中間節(jié)點(diǎn)收到RREQ分組后，首先判斷自身的能量狀態(tài)，如果處于“能量正?！睜顟B(tài)，則可以繼續(xù)工作；如果處于“能量不足”狀態(tài)，則不再轉(zhuǎn)發(fā)RREQ，退出工作。其次，根據(jù)分組中的DSR_RREQ字段檢查自身是否已存在路由表中，如果有則丟棄該分組，如果沒(méi)有則把自身地址加入到DSR_RREQ字段中。最后，計(jì)算自身的路徑負(fù)載率、時(shí)延和跳數(shù)，更新RREQ內(nèi)對(duì)應(yīng)的字段，繼續(xù)廣播轉(zhuǎn)發(fā)RREQ分組。下一跳的節(jié)點(diǎn)收到RREQ，如果計(jì)算負(fù)載后較上一節(jié)點(diǎn)高，更新并記錄到分組中，時(shí)延和跳數(shù)則繼續(xù)累加。

（3）目的節(jié)點(diǎn)收到RREQ分組，根據(jù)公式計(jì)算出路徑總負(fù)載Route_Load(r)。根據(jù)多徑路由選擇規(guī)則建立多徑路由，并向源節(jié)點(diǎn)返回RREP。

1.3.2 路由維護(hù)

路由維護(hù)過(guò)程與DSR基本一致，即路徑中斷時(shí)源節(jié)點(diǎn)收到RRER分組，刪除該路由項(xiàng)。由于多徑路由的存在，此時(shí)網(wǎng)絡(luò)仍可以正常工作，直至所有路徑失效，源節(jié)點(diǎn)重新啟動(dòng)路由發(fā)現(xiàn)。

1.3.3 多徑路由緩存

多徑路由的主要思想是在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條可用路徑，并根據(jù)一定條件選擇其中若干條路徑進(jìn)行數(shù)據(jù)傳輸。對(duì)于多徑路由的選取，需根據(jù)節(jié)點(diǎn)不相關(guān)原則，在某條路徑失效時(shí)不會(huì)影響到其他路徑的傳輸。然而，隨著多徑路由數(shù)的增加，網(wǎng)絡(luò)開(kāi)銷(xiāo)也會(huì)增加[13]。本文選擇2條路徑在網(wǎng)絡(luò)中工作。

圖4給出了多徑路由選擇的過(guò)程，具體過(guò)程如下：

（1）目的節(jié)點(diǎn)會(huì)收到若干組RREQ，將這些RREQ分組構(gòu)成的路徑組成一個(gè)集合Q。

（2）從集合Q中找出除了源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D以外具有最后一個(gè)公共節(jié)點(diǎn)C的路徑，組合成一個(gè)子集合Q1，子集合Q1結(jié)構(gòu)如下：

也就是說(shuō)，在子集合Q1中，節(jié)點(diǎn)C之前的路徑都是相同的，節(jié)點(diǎn)C之后的路徑是不同的。

（3）從子集合Q1中根據(jù)判據(jù)選出最適合路徑進(jìn)行記錄，然后把子集合Q1從Q中刪除。

（4）檢查集合Q中是否還存在剩余路徑，若存在，則返回第2步繼續(xù)查找；若不存在，則進(jìn)行下一步。

（5）統(tǒng)計(jì)Q中的路由數(shù)目，若路由數(shù)目大于2條，則選取前2條加入路由表中；若路由數(shù)目小于2條，則直接加入表中。

圖4 多徑路由緩存

路由選擇完畢并記錄后，選擇其中一條路徑作為主路徑進(jìn)行數(shù)據(jù)傳輸，另一條作為備用。當(dāng)主路徑因故障失效時(shí)，可立即切換到備用路徑繼續(xù)傳輸，同時(shí)啟動(dòng)主路徑修復(fù)。這樣可以保證網(wǎng)絡(luò)中不會(huì)因?yàn)槁窂绞Ф斐蓚鬏斝氏陆礫14]。

2 仿真實(shí)驗(yàn)

2.1 仿真模型及環(huán)境設(shè)置

為了驗(yàn)證所提ICMSR協(xié)議的性能，通過(guò)Opnet 14.5進(jìn)行仿真實(shí)驗(yàn)。節(jié)點(diǎn)模型的協(xié)議棧分為應(yīng)用層、路由層、數(shù)據(jù)鏈路層和物理層，如圖5所示。

圖5 節(jié)點(diǎn)協(xié)議棧模型

source模塊：業(yè)務(wù)產(chǎn)生模塊，每個(gè)節(jié)點(diǎn)按照配置好的參數(shù)產(chǎn)生數(shù)據(jù)分組，如果節(jié)點(diǎn)屬性中的目的節(jié)點(diǎn)設(shè)置為None，則表示不產(chǎn)生數(shù)據(jù)包。

sink模塊：業(yè)務(wù)銷(xiāo)毀模塊，當(dāng)數(shù)據(jù)包傳遞到目的節(jié)點(diǎn)的路由層后，將數(shù)據(jù)包投遞到此模塊進(jìn)行銷(xiāo)毀。

route模塊：路由模塊，首先通過(guò)RREQ/RREP分組建立路由，然后接收應(yīng)用層產(chǎn)生的數(shù)據(jù)包，并按照建立好的路由信息按照源路由方式進(jìn)行轉(zhuǎn)發(fā)。此模塊會(huì)實(shí)現(xiàn)基本DSR協(xié)議算法和改進(jìn)后的ICMSR協(xié)議算法。

mac_inf模塊：路由層與MAC層之間的接口，將路由下一跳轉(zhuǎn)換成MAC幀目的地址。

802_11_DCF_mac模塊：MAC層模塊，使用Opnet中內(nèi)置的IEEE 802.11標(biāo)準(zhǔn)模型，在無(wú)線環(huán)境下解決多址接入的問(wèn)題。

port tx/port rx模塊：一對(duì)無(wú)線收發(fā)信機(jī)，模擬數(shù)據(jù)包在無(wú)線信道中傳輸?shù)倪^(guò)程。

energy模塊：能量管理模塊。

仿真環(huán)境設(shè)置為500 m×500 m的區(qū)域，隨機(jī)分布30個(gè)節(jié)點(diǎn)，具體的參數(shù)配置見(jiàn)表1。

表1 仿真參數(shù)

2.2 性能指標(biāo)

性能指標(biāo)主要觀察網(wǎng)絡(luò)生存時(shí)間、分組投遞率、端到端時(shí)延和網(wǎng)絡(luò)吞吐量，通過(guò)設(shè)置不同的負(fù)載量來(lái)考察協(xié)議在不同負(fù)載情況下的性能表現(xiàn)。

圖6為網(wǎng)絡(luò)生存時(shí)間隨著負(fù)載量變化的曲線?？梢钥闯觯捎贗CMSR加入了能量狀態(tài)管理，能更有效地利用每個(gè)節(jié)點(diǎn)的能量，相比傳統(tǒng)DSR，能夠延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

圖6 網(wǎng)絡(luò)生存時(shí)間

圖7為分組投遞成功率隨著負(fù)載量變化的曲線。對(duì)比文獻(xiàn)[12]的IDSR協(xié)議和傳統(tǒng)DSR協(xié)議可以看出，隨著負(fù)載量的增大，ICMSR的分組投遞成功率要始終優(yōu)于DSR和IDSR。原因在于：ICMSR考慮了路徑負(fù)載率，能夠有效減少節(jié)點(diǎn)因擁塞而產(chǎn)生的傳輸效率下降；由于ICMSR維護(hù)了主備用路徑，在路徑失效時(shí)可以立即切換到備用路徑，同時(shí)啟動(dòng)主路徑修復(fù)，可以保證網(wǎng)絡(luò)中不會(huì)因?yàn)槁窂绞Ф斐蓚鬏斅氏陆担欢鳬DSR采用多路徑同時(shí)傳輸，當(dāng)一條路徑失效時(shí)，將剩余數(shù)據(jù)分配到其他可用路徑上會(huì)造成擁堵。

圖7 分組投遞成功率

圖8為端到端時(shí)延隨負(fù)載量變化的曲線。對(duì)比IDSR協(xié)議和傳統(tǒng)DSR協(xié)議可以看出，隨著負(fù)載量的增大，ICMSR的端到端時(shí)延要更低，原因在于ICMSR的負(fù)載均衡機(jī)制綜合考慮了路徑負(fù)載、時(shí)延和跳數(shù)，并對(duì)時(shí)延和跳數(shù)設(shè)定了約束條件，同時(shí)維護(hù)節(jié)點(diǎn)不相關(guān)的主/備用路徑也有利于降低傳輸時(shí)延。

圖8 端到端時(shí)延

圖9為網(wǎng)絡(luò)吞吐量隨負(fù)載量變化的曲線。對(duì)比IDSR和傳統(tǒng)DSR協(xié)議，可以看出隨著負(fù)載量增大，ICMSR在網(wǎng)絡(luò)吞吐量上更有優(yōu)勢(shì)。

圖9 網(wǎng)絡(luò)吞吐量

3 結(jié) 語(yǔ)

本文從實(shí)際應(yīng)用的角度出發(fā)，對(duì)無(wú)線Mesh網(wǎng)絡(luò)的路由協(xié)議進(jìn)行調(diào)查研究，最終選取了DSR協(xié)議作為研究對(duì)象。隨后進(jìn)行問(wèn)題分析，指出DSR在路由發(fā)現(xiàn)過(guò)程中的不足?；贒SR協(xié)議，通過(guò)引入一種綜合了路徑負(fù)載率、時(shí)延和跳數(shù)的負(fù)載均衡機(jī)制，并加入能量狀態(tài)監(jiān)控和多徑路由，提出了一種改進(jìn)型綜合源路由協(xié)議ICMSR。仿真結(jié)果表明，改進(jìn)協(xié)議在分組投遞率、端到端時(shí)延等性能指標(biāo)上相較于傳統(tǒng)DSR都有較大提升。今后將繼續(xù)對(duì)其進(jìn)行改進(jìn)，以期在硬件產(chǎn)品上實(shí)現(xiàn)協(xié)議功能，推出無(wú)線Mesh網(wǎng)絡(luò)產(chǎn)品。