《電子技術應用》
您所在的位置:首頁 > 通信與網絡 > 設計應用 > 基于負載均衡的DYMO路由協(xié)議改進
基于負載均衡的DYMO路由協(xié)議改進
來源:微型機與應用2013年第23期
王競超,葉建芳
(東華大學 信息科學與技術學院,上海 201620)
摘要: 提出了一種基于負載均衡的DYMO路由協(xié)議改進,通過仿真證明改進的DYMO路由協(xié)議實現(xiàn)了網絡的優(yōu)化,增加了移動自組網的性能。
Abstract:
Key words :

摘  要: 提出了一種基于負載均衡的DYMO路由協(xié)議改進,通過仿真證明改進的DYMO路由協(xié)議實現(xiàn)了網絡的優(yōu)化,增加了移動自組網的性能。
關鍵詞: 移動自組網;Ad Hoc路由協(xié)議;DYMO

 移動自組網MANET(Mobile Ad Hoc Networks)是由若干移動節(jié)點自行組成的網絡,整個網絡沒有固定的基礎設施,每個節(jié)點都可以自由地移動、加入以及退出網絡。移動自組網的研究最初是以一個獨立網絡存在的,隨著近年來移動自組網研究的不斷深入以及固定接入網的普及,實現(xiàn)Ad Hoc網絡與接入網技術的結合成為了移動自組網的一個重要研究方向。
 移動自組網中的路由協(xié)議分為兩大類。一是先驗式路由協(xié)議,又稱為表驅動路由協(xié)議,這類協(xié)議類似于固定網絡的路由協(xié)議,在任何情況下,無論是否傳輸數(shù)據,每個節(jié)點都必須維護一張整個網絡的路由表。二是后驗式路由協(xié)議,又稱為按需路由協(xié)議,這類路由協(xié)議是基于移動自組網的網絡拓撲不斷變化特性而研究出的。DYMO是最新的按需路由協(xié)議,由IETF的移動自組網工作組提出,是AODV路由協(xié)議的后繼協(xié)議,大量繼承了AODV路由協(xié)議的方法和機制,并且包含了一些DSR路由協(xié)議的特性。
 本文針對DYMO路由協(xié)議和接入網的結合,提出了基于網關發(fā)現(xiàn)以及網關負載均衡算法的改進LB-DYMO路由協(xié)議,使得網絡內的節(jié)點能夠有效地分擔流量和能耗,延長節(jié)點存活時間。并通過仿真驗證LB-DYMO路由協(xié)議能更好地與接入網結合。
1 DYMO路由協(xié)議
 DYMO路由協(xié)議的基本操作分為路由發(fā)現(xiàn)和路由維護兩個階段。
 在DYMO路由協(xié)議的路由發(fā)現(xiàn)階段,當源節(jié)點要發(fā)送數(shù)據到目標節(jié)點時會先查找源節(jié)點內部的路由表,如果不存在目的節(jié)點的路由條目,源節(jié)點就先緩存要發(fā)送的數(shù)據,然后開啟一個路由發(fā)現(xiàn)進程。首先,源節(jié)點廣播發(fā)送一個路由查詢包(RREQ)到它所有的鄰居節(jié)點,這些鄰居節(jié)點收到了RREQ后再查找它們內部的路由表,如果還是沒有目的節(jié)點的路由條目,則這些鄰居節(jié)點繼續(xù)向它們的鄰居轉發(fā)這個RREQ包直到目的節(jié)點收到為止。DYMO包含了源動態(tài)DSR路由協(xié)議的特性,在RREQ包轉發(fā)的過程中加入了中間節(jié)點的節(jié)點信息。當RREQ包到達目的節(jié)點時,目的節(jié)點會往源節(jié)點地址單播發(fā)送一個路由回應(RREP)包。源節(jié)點收到這個RREP包時,源節(jié)點與目的節(jié)點之間的路由便建立起來了。
 路由維護階段分為兩個部分。當一個活躍的節(jié)點檢測到其某條鄰接的鏈路斷裂時,這個節(jié)點就會發(fā)出一個路由錯誤(RRER)包來表示這條路由已經破損且目標節(jié)點不可達。在更新路由條目時,DYMO路由協(xié)議使用序列號來檢查條目的時效性,序列號數(shù)值越大則表明時效性越高,每個節(jié)點內都保存其自身的序列號用來維持這個序列號機制,該機制能很好地保證路由無環(huán)。
2 改進的LB-DYMO路由協(xié)議設計
 為了提高DYMO與接入網鏈接的效率,本文提出一種基于負載均衡算法的LB-DYMO路由協(xié)議。
2.1 基本思想
2.1.1網關發(fā)現(xiàn)

 為了實現(xiàn)自組網與有限接入網的結合,路由協(xié)議必須具備網關發(fā)現(xiàn)的能力。整個自組網絡至少需要一個連接外網的節(jié)點作為網關,這樣才能使網絡中的各個節(jié)點實現(xiàn)與Internet互聯(lián)。在移動自組網拓撲高度動態(tài)變化的環(huán)境下,能夠高效地發(fā)現(xiàn)網關并不容易。
 網關發(fā)現(xiàn)算法可以分為主動式和被動式兩大類,改進的LB-DYMO采用被動式網關發(fā)現(xiàn)算法。由于DYMO路由協(xié)議本身是一個被動式路由發(fā)現(xiàn)的路由協(xié)議,因此被動式的網關發(fā)現(xiàn)算法的應用能起到更好的效果。為了實現(xiàn)被動路由協(xié)議發(fā)現(xiàn),可以在路由協(xié)議的路由回應階段RREP包中加入IGW(網關)字段,表明該節(jié)點為網關。新的RREP格式如圖1所示,新加入的IGW字段利用了原來RREP報文所設置的保留位(Rsv)。
2.1.2 Load-balance(負載均衡)算法實現(xiàn)機制
 在LB-DYMO路由協(xié)議的網關發(fā)現(xiàn)過程之后,由于移動自組網的特性,網絡中可能存在多個網關。簡單地選取一條跳數(shù)最短的路由并不一定是最合適的路由。在多網關的移動自組網環(huán)境下,采用負載均衡算法不但能夠使得數(shù)據流避開帶寬較小的網關,選擇阻塞較小的網關,還能均衡各個節(jié)點的業(yè)務流量以及能耗。

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

 


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

 本文在DYMO路由協(xié)議的基礎上進行了改進,根據各自的MetriGW值來選擇不同路徑到達不同的網關實現(xiàn)負載均衡。仿真結果表明,LB-DYMO的分組投遞率較DYMO有一定程度的提高,但是由于協(xié)議復雜度的增加,路由開銷和端到端延時也相應增加。今后的工作將是研究如何能進一步提高LB-DYMO路由協(xié)議的各項性能,以及如何從理論出發(fā)更好地實現(xiàn)自組網的網關負載均衡。
參考文獻
[1] 陳林星,曾曦,曹毅.移動Ad Hoc網絡:自組織分組無線網絡技術[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網絡基于路由協(xié)議的擁塞控制[J].微型機與應用,2011(4):65-67.
[4] 劉銳,曾素華.AODV路由協(xié)議負載均衡的改進[J].四川兵工學報,2008(6):147-148.

此內容為AET網站原創(chuàng),未經授權禁止轉載。