Adhoc網(wǎng)絡(luò)中不相關(guān)多路由源端尋路算法

周婧

摘 要 路由方案是Ad hoc網(wǎng)絡(luò)中一個(gè)熱點(diǎn)研究領(lǐng)域。其中，按需路由算法由于其有效性在帶寬受限的Ad hoc網(wǎng)絡(luò)中得到比較大的發(fā)展。然而大部分的按需路由算法，建立并只使用單條路由，當(dāng)當(dāng)前使用的路徑的鏈路斷開(kāi)時(shí)，路由算法必須執(zhí)行一個(gè)路由修復(fù)過(guò)程。本文提出了不相關(guān)多路由源端路由算法（DMSR），建立并利用多條最大不相關(guān)路由。在本文算法中，中間節(jié)點(diǎn)等待一段時(shí)間以得到多個(gè)路由請(qǐng)求包（RREQ），然后在這個(gè)RREQ中，選擇相關(guān)性最小的多路徑，并將這些信息寫(xiě)入一個(gè)RREQ中，并將它廣播出去。從仿真結(jié)果可以看出本文的算法提高了數(shù)據(jù)包的正確傳輸率和業(yè)務(wù)均衡。

關(guān)鍵詞 通信保障 綜合保障 項(xiàng)目管理

1 引言

Ad hoc網(wǎng)絡(luò)是沒(méi)有中心節(jié)點(diǎn)的自組網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)中，沒(méi)有固定的路由器，或者無(wú)線基站。在Ad hoc網(wǎng)絡(luò)中，移動(dòng)節(jié)點(diǎn)之間的通信是通過(guò)點(diǎn)到點(diǎn)的多跳技術(shù)實(shí)現(xiàn)的，這就意味著網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)的變化，這就產(chǎn)生了許多值得探討的問(wèn)題。在Ad hoc網(wǎng)絡(luò)中，路由技術(shù)是至關(guān)重要的，在任何業(yè)務(wù)連接之前，都首先必須完成尋路的過(guò)程。

目前，Ad hoc網(wǎng)絡(luò)中最多的是按需路由。然而，很多已經(jīng)提出的按需路由協(xié)議，如傳統(tǒng)的DSR[1]，AODV[2]算法都只為每一個(gè)連接建立一條路徑，這不僅不能充分利用資源，而且無(wú)法有效處理?yè)砣?，鏈路斷開(kāi)等情況。多路由算法可以解決這些問(wèn)題。使用多條路徑可以提高帶寬的有效利用率和傳輸可靠性以達(dá)到一定的QoS保證。

目前，對(duì)多路由的研究主要集中在以下兩個(gè)方面：建立多路由和在這些多路由之間分配業(yè)務(wù)的策略。

本文提出一種新的不相關(guān)多路由源端路由算法（DMSR）。DMSR算法在DSR算法的基礎(chǔ)上主要做了以下的改進(jìn)：在尋路過(guò)程中，每個(gè)中間節(jié)點(diǎn)等待一段時(shí)間以接收到多個(gè)RREQ，然后在這個(gè)RREQ中，選擇相關(guān)性最小的多路徑，并將這些信息寫(xiě)入一個(gè)RREQ中，并將它廣播出去。DMSR可以找到最大不相關(guān)路徑，因此可以減小發(fā)起路由頻率，以減小時(shí)延，同時(shí)可以提高數(shù)據(jù)包的正確傳輸率。

2 Ad hoc中的多路由

在網(wǎng)絡(luò)拓?fù)洳淮_定的情況下，尋找到不相關(guān)的多路由是比較困難的。DSR協(xié)議能夠?qū)ふ业蕉鄺l路由，并在主路由斷裂的情況下將其他路由作為備份路由。然而，DSR并未將不相關(guān)性考慮進(jìn)來(lái)。在本篇文章里提出一種尋找不相關(guān)的多路由的方法。

2.1 DSR中的路由發(fā)現(xiàn)

在DSR算法中，如果源節(jié)點(diǎn)不知道到目的節(jié)點(diǎn)的路徑，那么源節(jié)點(diǎn)將通過(guò)洪泛路由請(qǐng)

求消息（RREQ）發(fā)起一個(gè)路由發(fā)現(xiàn)。在RREQ包頭中將依次記錄下這個(gè)RREQ包所經(jīng)過(guò)的節(jié)點(diǎn)的地址。當(dāng)一個(gè)節(jié)點(diǎn)接收到一個(gè)RREQ包，如果這是第一次接收到這個(gè)具有相同源節(jié)點(diǎn)地址和ID的RREQ包，這個(gè)節(jié)點(diǎn)經(jīng)過(guò)處理將RREQ廣播出去。反之，節(jié)點(diǎn)將這個(gè)RREQ丟棄。一點(diǎn)RREQ到達(dá)目的節(jié)點(diǎn)，目的節(jié)點(diǎn)將經(jīng)過(guò)RREQ中包含的路徑返回一個(gè)路由回復(fù)消息（RREP）到源節(jié)點(diǎn)。當(dāng)RREP到達(dá)源節(jié)點(diǎn)，源節(jié)點(diǎn)和所有中間節(jié)點(diǎn)都會(huì)知道一條到達(dá)目的結(jié)點(diǎn)的路徑。

DSR中這種廣播RREQ的方式極大的減小了找到不相關(guān)的多路徑的可能性。也就是說(shuō)DSR算法最后找到的多條路徑的一些節(jié)點(diǎn)是相同的。在一些文章的仿真結(jié)果中DSR找到完全不相關(guān)的多路徑的可能性幾乎為零。造成這種結(jié)果的原因是中間節(jié)點(diǎn)將丟棄后收到的相同的RREQ，而這些RREQ中包含著不相關(guān)的路徑。

2.2 不相關(guān)源多路由算法

A.路由發(fā)現(xiàn)

DMSR充分利用后來(lái)接收到的RREQ包。

當(dāng)一個(gè)中間節(jié)點(diǎn)收到第一RREQ包，它不是像DSR那樣立刻將自身地址加到這個(gè)RREQ上并將這個(gè)RREQ廣播出去，而是將收到的RREQ儲(chǔ)存在高速緩沖存儲(chǔ)器中，同時(shí)啟動(dòng)一個(gè)定時(shí)器，在定時(shí)器的這段之間內(nèi)，該節(jié)點(diǎn)等待其它相同的RREQ（即具有相同源節(jié)點(diǎn)地址和RREQ ID的RREQ）。

當(dāng)節(jié)點(diǎn)收到相同的RREQ，它首先要檢查這個(gè)RREQ中路徑的跳數(shù)是大于、小于或者等于之前收到的相同的RREQ的跳數(shù)。如果是大于，則節(jié)點(diǎn)丟棄該RREQ；如果等于，節(jié)點(diǎn)將RREQ記錄在cache中；如果小于，節(jié)點(diǎn)將刪除之前接收到的相同的RREQ，同時(shí)將新收到的RREQ記錄在高速緩沖存儲(chǔ)器中。

為了減小RREQ造成的信令開(kāi)銷，限制一個(gè)節(jié)點(diǎn)最多記錄三條相同的RREQ。為了減小時(shí)延，如果已經(jīng)記錄下三條RREQ，就將定時(shí)器歸零，開(kāi)始處理高速緩沖存儲(chǔ)器中的RREQ。

當(dāng)定時(shí)器到時(shí)，開(kāi)始處理高速緩沖存儲(chǔ)器中記錄的RREQ：

（1）如果高速緩沖存儲(chǔ)器中只有一個(gè)RREQ，該節(jié)點(diǎn)將自身地址附加在RREQ中的路由紀(jì)錄中，并將它廣播出去；

（2）如果高速緩沖存儲(chǔ)器中有不止一個(gè)RREQ，節(jié)點(diǎn)檢查是否存在一個(gè)RREQ中只有一條路徑。如果存在這樣的RREQ，節(jié)點(diǎn)首先選擇這條路徑，然后在其他RREQ中分別選擇一條與該路徑相干系數(shù)最小的路徑；如果相干系數(shù)一樣，則選擇首先記錄下的那條路徑；如果所有的RREQ都包含不止一條路徑，則節(jié)點(diǎn)首先選擇第一個(gè)收到的RREQ的第一條路徑，其他路徑的選擇準(zhǔn)則見(jiàn)2），然后：

（3）選擇完路徑，節(jié)點(diǎn)將自身地址附加到所選擇的路徑上，并將這些路徑寫(xiě)到原來(lái)收到的RREQ中，這些路徑的寫(xiě)入順序是：首先收到的RREQ中選擇的路徑是第一條路徑，第二個(gè)收到的RREQ中選擇的路徑是第二條路徑，同樣的，從最后收到的RREQ中選擇的路徑是第三條路徑。然后節(jié)點(diǎn)將新的RREQ廣播出去。

當(dāng)?shù)谝粋€(gè)RREQ到達(dá)目的節(jié)點(diǎn)，目的節(jié)點(diǎn)等待一段時(shí)間以接收到更多的RREQ，并從這些RREQ中選擇相干最小的多路徑。

在DMSR算法中，在一段時(shí)間內(nèi)收到的RREQ中，中間節(jié)點(diǎn)選擇跳數(shù)最小的路徑。因此，在目的節(jié)點(diǎn)可以得到跳數(shù)最小的路徑。同時(shí)DMSR算法中，優(yōu)先選擇先到達(dá)的路徑，這同樣可以減小時(shí)延。

路徑中的一條鏈路可能由于移動(dòng)、擁塞、包沖突而斷裂，因此，修復(fù)斷裂的路徑非常重要。在DMSR算法中，當(dāng)一個(gè)節(jié)點(diǎn)不能夠?qū)鼈魉偷较乱粋€(gè)節(jié)點(diǎn)，就認(rèn)為到下一個(gè)節(jié)點(diǎn)的鏈路已經(jīng)斷開(kāi)，于是發(fā)出一個(gè)路由錯(cuò)誤包（RRER）到這條路徑的上游節(jié)點(diǎn)。這個(gè)RRER包中包含到源節(jié)點(diǎn)的路徑，以及斷開(kāi)鏈路的上游、下游節(jié)點(diǎn)。一旦收到RRER包，源節(jié)點(diǎn)將刪除其路由表中所有使用斷開(kāi)路由的表項(xiàng)，而同時(shí)源節(jié)點(diǎn)使用剩余的路徑傳送數(shù)據(jù)包。當(dāng)所有的路徑斷開(kāi)，源節(jié)點(diǎn)將重新發(fā)起一個(gè)路由發(fā)現(xiàn)過(guò)程。

2.3 DMSR和DSR的比較

圖2表示的是DMSR找到的多路徑，可以看出這些路徑是不相關(guān)的。圖3表示的是DSR找到的多路徑，這些多路徑幾乎是重疊的?？梢钥闯?，DMSR比DSR尋找多路徑的效率高得多。

3 仿真結(jié)果

3.1 仿真環(huán)境

3.3 結(jié)果與分析

圖4所示的是DMSR與DSR算法的數(shù)據(jù)包的正確傳輸率。從圖中可以看出，相對(duì)于DSR，DMSR提高了性能，尤其是當(dāng)移動(dòng)性增加時(shí)。當(dāng)使用多路由時(shí)，移動(dòng)性增加，性能的提高變得明顯，這是因?yàn)樵贒SR算法中，每一對(duì)業(yè)務(wù)只使用一條路徑，當(dāng)這條路徑失效時(shí)，源節(jié)點(diǎn)必須重新尋找一條新的路由，在此過(guò)程中，會(huì)造成包的丟失。但是在DMSR中，源節(jié)點(diǎn)可同時(shí)使用三條并行路徑，因此重新尋路的頻率被大大減小，尤其當(dāng)移動(dòng)性增大時(shí)，因此DMSR能夠正確傳送更多的數(shù)據(jù)包。

圖5所示的是兩種算法的平均端到端時(shí)延?？梢钥吹絻煞N算法的時(shí)延幾乎相同，但是DMSR算法比DSR算法的時(shí)延略微大一點(diǎn)。在DMSR中路由發(fā)現(xiàn)的頻率減小可以減小時(shí)延，但是在DMSR的尋路過(guò)程中RREQ必須從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn)以尋找到多條路徑，而在DSR中，尋路過(guò)程中的任一節(jié)點(diǎn)可以使用自己路由表中的信息，不需要一定要將RREQ包發(fā)送到目的節(jié)點(diǎn)，在這方面，DSR可以減小時(shí)延。

圖6所示的是兩種算法負(fù)載均衡的結(jié)果。從圖中可以看出DMSR的網(wǎng)絡(luò)CoV性能優(yōu)于DSR。這是因?yàn)镈MSR可以將網(wǎng)絡(luò)業(yè)務(wù)分?jǐn)偟蕉鄺l路徑上。而在DSR算法中所選用的路徑為源節(jié)點(diǎn)與目的結(jié)點(diǎn)之間的最短路徑，因此會(huì)將更多的業(yè)務(wù)分配到這些路徑上。隨著休息時(shí)間的減少，DMSR和DSR的網(wǎng)絡(luò)CoV也減小，這表明移動(dòng)性可以均衡負(fù)載。

4 結(jié)論

在本篇文章中，提出了一個(gè)新的ad hoc中的DMSR算法。DMSR算法在DSR算法的基礎(chǔ)上主要做了以下的改進(jìn)：在尋路過(guò)程中，每個(gè)中間節(jié)點(diǎn)等待一段時(shí)間以接收到多個(gè)RREQ，然后在這個(gè)RREQ中，選擇相關(guān)性最小的多路徑，并將這些信息寫(xiě)入一個(gè)RREQ中，并將它廣播出去。本文對(duì)DMSR的性能進(jìn)行了研究，結(jié)果表明DMSR可以提高數(shù)據(jù)包的正確傳輸率和業(yè)務(wù)均衡性。

參 考 文 獻(xiàn)

[1] D. Johnson and D. Maltz， Dynamic source Routing in Ad Hoc wireless networks， in Mobile Computing， T. Imielinski and H. Korth， editors， Kluwer Academic，1996.

[2] C.E. Perkins and E.M. Royer， Ad-hoc On-Demand Distance Vector Routing，Proc. 2nd IEEE Wksp. Mobile Comp. Sys. And Apps.， Feb. 1999， pp.99-100.