摘  要： 提出了一種基于負(fù)載均衡的DYMO路由協(xié)議改進(jìn)，通過仿真證明改進(jìn)的DYMO路由協(xié)議實(shí)現(xiàn)了網(wǎng)絡(luò)的優(yōu)化，增加了移動自組網(wǎng)的性能。
關(guān)鍵詞： 移動自組網(wǎng)；Ad Hoc路由協(xié)議；DYMO

　移動自組網(wǎng)MANET（Mobile Ad Hoc Networks）是由若干移動節(jié)點(diǎn)自行組成的網(wǎng)絡(luò)，整個網(wǎng)絡(luò)沒有固定的基礎(chǔ)設(shè)施，每個節(jié)點(diǎn)都可以自由地移動、加入以及退出網(wǎng)絡(luò)。移動自組網(wǎng)的研究最初是以一個獨(dú)立網(wǎng)絡(luò)存在的，隨著近年來移動自組網(wǎng)研究的不斷深入以及固定接入網(wǎng)的普及，實(shí)現(xiàn)Ad Hoc網(wǎng)絡(luò)與接入網(wǎng)技術(shù)的結(jié)合成為了移動自組網(wǎng)的一個重要研究方向。
　移動自組網(wǎng)中的路由協(xié)議分為兩大類。一是先驗(yàn)式路由協(xié)議，又稱為表驅(qū)動路由協(xié)議，這類協(xié)議類似于固定網(wǎng)絡(luò)的路由協(xié)議，在任何情況下，無論是否傳輸數(shù)據(jù)，每個節(jié)點(diǎn)都必須維護(hù)一張整個網(wǎng)絡(luò)的路由表。二是后驗(yàn)式路由協(xié)議，又稱為按需路由協(xié)議，這類路由協(xié)議是基于移動自組網(wǎng)的網(wǎng)絡(luò)拓?fù)洳粩嘧兓匦远芯砍龅摹YMO是最新的按需路由協(xié)議，由IETF的移動自組網(wǎng)工作組提出，是AODV路由協(xié)議的后繼協(xié)議，大量繼承了AODV路由協(xié)議的方法和機(jī)制，并且包含了一些DSR路由協(xié)議的特性。
　本文針對DYMO路由協(xié)議和接入網(wǎng)的結(jié)合，提出了基于網(wǎng)關(guān)發(fā)現(xiàn)以及網(wǎng)關(guān)負(fù)載均衡算法的改進(jìn)LB-DYMO路由協(xié)議，使得網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)能夠有效地分擔(dān)流量和能耗，延長節(jié)點(diǎn)存活時間。并通過仿真驗(yàn)證LB-DYMO路由協(xié)議能更好地與接入網(wǎng)結(jié)合。
1 DYMO路由協(xié)議
　DYMO路由協(xié)議的基本操作分為路由發(fā)現(xiàn)和路由維護(hù)兩個階段。
　在DYMO路由協(xié)議的路由發(fā)現(xiàn)階段，當(dāng)源節(jié)點(diǎn)要發(fā)送數(shù)據(jù)到目標(biāo)節(jié)點(diǎn)時會先查找源節(jié)點(diǎn)內(nèi)部的路由表，如果不存在目的節(jié)點(diǎn)的路由條目，源節(jié)點(diǎn)就先緩存要發(fā)送的數(shù)據(jù)，然后開啟一個路由發(fā)現(xiàn)進(jìn)程。首先，源節(jié)點(diǎn)廣播發(fā)送一個路由查詢包（RREQ）到它所有的鄰居節(jié)點(diǎn)，這些鄰居節(jié)點(diǎn)收到了RREQ后再查找它們內(nèi)部的路由表，如果還是沒有目的節(jié)點(diǎn)的路由條目，則這些鄰居節(jié)點(diǎn)繼續(xù)向它們的鄰居轉(zhuǎn)發(fā)這個RREQ包直到目的節(jié)點(diǎn)收到為止。DYMO包含了源動態(tài)DSR路由協(xié)議的特性，在RREQ包轉(zhuǎn)發(fā)的過程中加入了中間節(jié)點(diǎn)的節(jié)點(diǎn)信息。當(dāng)RREQ包到達(dá)目的節(jié)點(diǎn)時，目的節(jié)點(diǎn)會往源節(jié)點(diǎn)地址單播發(fā)送一個路由回應(yīng)（RREP）包。源節(jié)點(diǎn)收到這個RREP包時，源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的路由便建立起來了。
　路由維護(hù)階段分為兩個部分。當(dāng)一個活躍的節(jié)點(diǎn)檢測到其某條鄰接的鏈路斷裂時，這個節(jié)點(diǎn)就會發(fā)出一個路由錯誤（RRER）包來表示這條路由已經(jīng)破損且目標(biāo)節(jié)點(diǎn)不可達(dá)。在更新路由條目時，DYMO路由協(xié)議使用序列號來檢查條目的時效性，序列號數(shù)值越大則表明時效性越高，每個節(jié)點(diǎn)內(nèi)都保存其自身的序列號用來維持這個序列號機(jī)制，該機(jī)制能很好地保證路由無環(huán)。
2 改進(jìn)的LB-DYMO路由協(xié)議設(shè)計(jì)
　為了提高DYMO與接入網(wǎng)鏈接的效率，本文提出一種基于負(fù)載均衡算法的LB-DYMO路由協(xié)議。
2.1 基本思想
2.1.1網(wǎng)關(guān)發(fā)現(xiàn)
　為了實(shí)現(xiàn)自組網(wǎng)與有限接入網(wǎng)的結(jié)合，路由協(xié)議必須具備網(wǎng)關(guān)發(fā)現(xiàn)的能力。整個自組網(wǎng)絡(luò)至少需要一個連接外網(wǎng)的節(jié)點(diǎn)作為網(wǎng)關(guān)，這樣才能使網(wǎng)絡(luò)中的各個節(jié)點(diǎn)實(shí)現(xiàn)與Internet互聯(lián)。在移動自組網(wǎng)拓?fù)涓叨葎討B(tài)變化的環(huán)境下，能夠高效地發(fā)現(xiàn)網(wǎng)關(guān)并不容易。
　網(wǎng)關(guān)發(fā)現(xiàn)算法可以分為主動式和被動式兩大類，改進(jìn)的LB-DYMO采用被動式網(wǎng)關(guān)發(fā)現(xiàn)算法。由于DYMO路由協(xié)議本身是一個被動式路由發(fā)現(xiàn)的路由協(xié)議，因此被動式的網(wǎng)關(guān)發(fā)現(xiàn)算法的應(yīng)用能起到更好的效果。為了實(shí)現(xiàn)被動路由協(xié)議發(fā)現(xiàn)，可以在路由協(xié)議的路由回應(yīng)階段RREP包中加入IGW（網(wǎng)關(guān)）字段，表明該節(jié)點(diǎn)為網(wǎng)關(guān)。新的RREP格式如圖1所示，新加入的IGW字段利用了原來RREP報(bào)文所設(shè)置的保留位（Rsv）。
2.1.2 Load-balance（負(fù)載均衡）算法實(shí)現(xiàn)機(jī)制
　在LB-DYMO路由協(xié)議的網(wǎng)關(guān)發(fā)現(xiàn)過程之后，由于移動自組網(wǎng)的特性，網(wǎng)絡(luò)中可能存在多個網(wǎng)關(guān)。簡單地選取一條跳數(shù)最短的路由并不一定是最合適的路由。在多網(wǎng)關(guān)的移動自組網(wǎng)環(huán)境下，采用負(fù)載均衡算法不但能夠使得數(shù)據(jù)流避開帶寬較小的網(wǎng)關(guān)，選擇阻塞較小的網(wǎng)關(guān)，還能均衡各個節(jié)點(diǎn)的業(yè)務(wù)流量以及能耗。

2.2 實(shí)現(xiàn)方案
　路由發(fā)現(xiàn)階段：LB-DYMO和DYMO使用同樣的方法，如果發(fā)現(xiàn)到達(dá)目的地址在源節(jié)點(diǎn)的路由表中找不到對應(yīng)路由，那么源節(jié)點(diǎn)就會廣播發(fā)送RREQ包至所有鄰居節(jié)點(diǎn)。
　路由回復(fù)階段：當(dāng)源節(jié)點(diǎn)所要到達(dá)的目的地址不存在于整個自組網(wǎng)中，那么LB-DYMO的被動網(wǎng)關(guān)發(fā)送算法就會被觸發(fā)。IGW收到通往外網(wǎng)網(wǎng)段的RREQ查詢包后，會在RREP包后加入IGW字段，表明本節(jié)點(diǎn)為網(wǎng)關(guān)。同時在RREP包按原路徑返回源節(jié)點(diǎn)時，還會綜合計(jì)算整個鏈路上的負(fù)載以及帶寬。在多網(wǎng)關(guān)的情況下，源節(jié)點(diǎn)會收到多個RREP包用來告知源節(jié)點(diǎn)有多條通往目的地址的路由存在。LB-DYMO通過RREP包返回時計(jì)算出的鏈路MetricGW值選擇合適的網(wǎng)關(guān)，在源節(jié)點(diǎn)的路由表中寫一條通往外網(wǎng)的默認(rèn)IGW，暫時未使用到的IGW會在路由表的默認(rèn)路由下寫為備份IGW。默認(rèn)網(wǎng)關(guān)的使用會分配GWtmin和GWtmax。分別表示默認(rèn)網(wǎng)關(guān)的最小生存以及最大生存時間。
　路由維護(hù)階段：一旦默認(rèn)IGW的使用時間到達(dá)了最大生存時間，LB-DYMO則會實(shí)行新一輪的路由發(fā)現(xiàn)策略，目的地為前默認(rèn)IGW節(jié)點(diǎn)以及各個備份IGW節(jié)點(diǎn)，然后通過收到的RREP包得到最新的鏈路MetricGW值，權(quán)衡之后再選出新的默認(rèn)IGW節(jié)點(diǎn)。
3 仿真結(jié)果及分析

　本文仿真采用NS2網(wǎng)絡(luò)仿真模擬軟件，設(shè)計(jì)的仿真場景為1 500 m×1 500 m，節(jié)點(diǎn)數(shù)量為100個的矩形區(qū)域，仿真時間為300 s。NS2中選擇的節(jié)點(diǎn)運(yùn)動模式為Random waypoint，MAC層采用IEEE 802.11介質(zhì)訪問控制協(xié)議。傳輸層采用UDP協(xié)議，應(yīng)用層發(fā)送包大小為512 B的恒定比特率（CBR）數(shù)據(jù)流，整個自組網(wǎng)絡(luò)中的IGW數(shù)量為3。
　實(shí)驗(yàn)結(jié)果如圖2~圖4所示，圖2和圖3顯示的是數(shù)據(jù)包傳輸速率在5~40 packet/s情況下，LB-DYMO與DYMO的端到端時延與歸一化路由開銷比較。由圖可知，LB-DYMO的路由開銷和時延都在一定程度上比DYMO高，這是由于LB-DYMO在路由回應(yīng)以及路由維護(hù)階段均比DYMO復(fù)雜。圖4顯示的是在不同數(shù)據(jù)包傳輸速率下，LB-DYMO與DYMO分組投遞率的比較。由圖可知，加入了負(fù)載均衡算法的LB-DYMO的表現(xiàn)比DYMO有一定提高。

　本文在DYMO路由協(xié)議的基礎(chǔ)上進(jìn)行了改進(jìn)，根據(jù)各自的MetriGW值來選擇不同路徑到達(dá)不同的網(wǎng)關(guān)實(shí)現(xiàn)負(fù)載均衡。仿真結(jié)果表明，LB-DYMO的分組投遞率較DYMO有一定程度的提高，但是由于協(xié)議復(fù)雜度的增加，路由開銷和端到端延時也相應(yīng)增加。今后的工作將是研究如何能進(jìn)一步提高LB-DYMO路由協(xié)議的各項(xiàng)性能，以及如何從理論出發(fā)更好地實(shí)現(xiàn)自組網(wǎng)的網(wǎng)關(guān)負(fù)載均衡。
參考文獻(xiàn)
[1] 陳林星，曾曦，曹毅.移動Ad Hoc網(wǎng)絡(luò)：自組織分組無線網(wǎng)絡(luò)技術(shù)[M].北京：電子工業(yè)出版社，2012.
[2] PERKINS C， CHAKERES I. Dynamic MANET on-demand（DYMO）routing[EB/OL]. http：//tools.ietf.org/html/draft-ietf-manet-dymo-26.
[3] 徐煒，周少瓊，柏詩玉.移動Ad hoc網(wǎng)絡(luò)基于路由協(xié)議的擁塞控制[J].微型機(jī)與應(yīng)用，2011（4）：65-67.
[4] 劉銳，曾素華.AODV路由協(xié)議負(fù)載均衡的改進(jìn)[J].四川兵工學(xué)報(bào)，2008（6）：147-148.