ＭＡＮＥＴ與Ｉｎｔｅｒｎｅｔ互連的網關選擇策略研究進展

摘要：在系統描述當前各種典型的網關選擇策略基礎上，第一次給出了MANET與Internet互連的網關選擇策略的分類方法，并比較和分析了這些策略的優勢與不足；最后結合該領域當前的研究現狀，指出MANET與Internet互連的網關選擇策略的發展方向。

關鍵詞：移動自組網； Internet互連； 網關選擇

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)06－1626－04

0引言

移動Ad hoc網絡與Internet互連是近年來研究的熱點問題。為了實現MANET與Internet的互連就需要在兩者之間存在一種特殊的網關，它是 Ad hoc網絡與Internet互連的橋梁[1]。當移動節點有連接Internet的需求時，它首先要找到所有可到達的網關，即網關發現過程；然后移動節點通過有效的網關選擇策略在已經找到的這些備選網關中選擇一個最佳網關與Internet進行通信。

目前對網關選擇策略的研究尚處在起步階段[2]。文獻[3，4]用移動節點到網關的跳數作為網關選擇的標準，即移動節點選擇離自身最近的網關與Internet通信。這種最短路徑策略的優點是簡單、易實現且快速收斂、延遲小；但是，如果所有的移動節點都選擇該網關與Internet通信，就會出現網絡擁塞，該網關將會成為網絡瓶頸并最終導致網絡性能的下降。針對單純用跳數作為選擇標準所帶來的問題，研究者們從不同的角度提出了一些網關選擇策略。文獻[2]考慮到節點的移動性因素，選擇移動性較小的節點作為下一跳傳送分組的節點，因此可以通過傳送分組路徑的確定來選擇網關。文獻[5]除了跳數之外，還考慮到網絡的擁塞水平和信道爭用水平，并將這三者組合成一個參數作為選擇網關的標準。文獻[6]提出了一個基于網關負載的選擇策略。文獻[7，8]同時用跳數和網關負載作為網關選擇的標準。

本文在歸納和總結以上各種網關選擇策略[2， 5~8]的基礎上，第一次給出了一種網關選擇策略的分類方法；同時，對以上各種策略進行詳細的比較和分析，指出各自的優勢與不足；最后結合該領域當前的研究現狀，指出MANET與Internet互連的網關選擇策略的發展方向。

1網關選擇策略詳述

基于跳數的選擇策略就是最短路徑方法，本文不贅述。

1．1基于load策略

參考文獻[6]將出入網關的網絡流量分別記做出(outgoing traffic)/入(incoming traffic)流量，且出/入流量可以通過不同的網關。因此有兩種默認網關：出流量所通過的網關；入流量所經過的網關。

1．1．1出/入流量默認網關的選擇

網關的出流量負載由選擇這一網關作為其默認網關的節點數決定。當采用Ad hoc的被動路由協議時，源節點在發送數據包之前沒有發現到目的地址的路由，它就廣播RREQ消息到其鄰節點并啟動路由發現計時器。如果是網關收到RREQ消息，就回復P－RREP消息給源節點；如果目的節點收到RREQ消息，就回復給源節點RREP消息；如果目的節點在Internet上，就不會產生RREP消息且源節點的計時器過期，但在計時器過期之前，源節點會收到從不同網關發來的P－RREP消息，源節點選擇其中的一個作為默認網關。

為了讓源節點選擇一個較少負載的網關作為其默認網關，設計了一個自適應的延遲算法來回復P－RREP消息。當網關生成一個P－RREP消息后，根據其負載延遲發送P－RREP消息。負載越重，延遲發送的時間就越長。如圖1所示，為了回復源節點S發送的RREQ消息，網關用延遲的P－RREP消息作為應答。如果網關IG1比IG2的擁塞程度小，那么IG1回復P－RREP消息的延遲就比IG2小。那么源節點S收到的第一個從IG1回復的P－RREP消息的可能性就比IG2大。最終S就選擇IG1作為其默認網關發送數據到Internet節點。

當鄰節點移動時，每一個節點都控制一個與其移動性相關的值，即連接失敗的頻率，它與MTV相關。MTV越高就意味著路由失效的可能性越高。節點必須選擇具有較小MTV的節點作為到目的地址的下一跳節點。選擇具有較小移動性(MTV值)的下一跳節點能夠使網絡環境更加穩定。因為無法得知下一個節點的MTV是否為當前的MTV，在預先確定一個MTV的有效值后建立一個MTV的超時時間；在超時后開始發送下一個節點的MTV。

為了找到穩定的路由，選擇移動性較小的節點作為下一跳傳送分組的節點。因此可以通過傳送分組路徑的確定來選擇網關。首先比較MTV，如果節點具有相同的MTV，則比較它們到網關的跳數。如果跳數也相同，則用具有較長連接的生存期值作為選擇到網關路徑的標準。

1．3MMGD策略

MMGD[5]策略將擁塞水平(congestion level)和信道爭用水平(contention level)轉換成虛跳數；然后與移動節點到網關的物理跳數(實跳數)一起組成一個惟一參數用于選擇網關。首先，策略改進了網關通告消息和路由表。在網關通告消息中加入GWADV_METRIC，用它記錄組合的參數(虛跳數和實跳數)，即gw_metric= virtual hops + physical hops = congestion level + contention level + physical hops。同時修改了路由表，即將gw_metric加入到路由表中。

假設從不同網關到有線節點的開銷相同，那么對于任意一個固定節點，找移動節點到它的最小開銷問題就等價為移動節點有到網關的最佳路徑。這一路徑用gw_metric的值來衡量。

擁塞水平用每一個節點的隊列長度來表示：

ad_hop_congestion=K×SizeIFQueue2(3)

其中：K為擁塞索引(系數)。當節點的隊列長度增加時，擁塞水平也會增加。因此，采用不同的K值來測試對擁塞水平的影響。

用網絡分配矢量NAV來表示信道爭用水平。當某節點獲取信道后發送RTS到發出ACK的目的節點時，初始化NAV。因此NAV 是信道忙時的時間，用TNAV表示。為了避免到網關的不必要的由較低信道爭用引起的路由變化，TNAV必須超過TNAV的極限值(ThreshNAV)。在信道爭用水平轉換成虛跳數之前，節點不斷地監控信道并在下一個網關通告到達之前計算TNAV 。如果TNAV超過ThreshNAV，即表示高信道爭用。用式(4)計算信道爭用水平：

其中：W表示信道帶寬，為2 Mbps；C表示平均數據包字節數。當信道爭用水平轉換成虛跳數之后，將TNAV置0。

在MMGD中采用主動網關發現方法，即網關周期性地廣播網關通告消息。當某個移動節點收到網關通告消息后，將擁塞和信道爭用水平轉換成虛跳數，然后與節點到網關的物理跳數一起組成選擇網關的參數，更新網關通告中的gwadv_metric項。每一個移動節點通過比較在其路由表中gw_metric和收到的網關通告消息的gwadv_metric來選擇合適的網關。算法的流程如圖2所示。

移動節點將從同一個網關收到的新的網關通告消息緩存在其路由表中，僅當gwadv_metric比路由表中gw_metric小時才更新本地路由表。如果gwadv_metric＜gw_metric且網關通告消息來自不同網關，移動節點會用新的網關替換默認網關。

1．4Hops+load 策略

1．4．1最早的策略[7]

文獻[7]是目前最早的用跳數(網關和有Internet接入需求的MANET節點之間的距離)和網關的負載來選擇網關的策略。但在文獻[7]中，網關的負載定義為注冊到這個網關的MANET節點數。當滿足：

α×δ(i，j)+β×λj=min{α×δ(i，k)+β×λk∶1≤k≤n}(5)

時，一個MANET節點MNi將選擇一個移動網關MGj。其中：n是移動節點MNi可以偵聽到的所有網關數目;δ(i，j)表示MNi與MGj之間的物理距離(跳數)；λi表示MGj的負載；α記做用跳數作為判斷依據的權重值；β記做用網關的負載作為判斷依據的權重值，且α+ β= 1。通過式(5)給出的α和β值，可以推斷出更傾向于用哪個參數選擇網關。例如α=1，表示MNi與MGj之間的距離占主導地位，即一個MANET節點將選擇一個最近的移動網關而不考慮這個網關到底有多少MANET節點通過它與Internet連接；如果β=1，則表示網關的負載作為主要判斷標準，即MANET節點將選擇負載最小的移動網關而不考慮這個網關的物理距離；當α=β=0.5時，兩個選擇標準同樣重要。如果一個移動節點到其所有備選網關的距離都相等，那么它就選擇具有最小負載的移動網關；如果所有網關的負載相同，移動節點將選擇離自身最近的網關。為了更好地確定當前最佳網關，一個MANET節點需要嘗試不同的(α，β)組合，直到找到滿足式(5)的最佳的組合對。本文選取五組不同的(α，β)組合，即(α，β)∈{(1，0)，(0，1)，(0.25，0.75)，(0.5，0.5)，(0.75，0.25)}。通過模擬實驗進行了測試。結果表明，與僅使用跳數作為選擇標準的策略相比，本文的策略更有效。

1．4．2Load－balancing 策略[8]

文獻[8]提出了一個平衡負載的網關選擇策略。這里的負載指的是網關的流量負載(traffic load)。首先，每一個移動節點需要找到一個或多個到網關的路徑；這個節點選擇到每個網關的最佳路徑；最后，通過load－balancing 選擇策略，節點從這些備選網關中找出最佳網關。

網關將負載信息加入到網關通告消息中，通過廣播網關通告消息將負載信息廣播出去。比較移動節點到不同網關的跳數及到網關不同路徑上的網絡流量負載，如果跳數相同，則選擇負載小的路徑上的網關進行數據傳送。但當大量分組都經過這條路徑傳送時，勢必會造成網絡擁塞而導致分組丟失和傳送延遲。此時策略將重新選擇新的、負載低的網關傳送數據分組，因而可以達到平衡負載的目的。

1)負載的計算

網絡中移動節點MN每秒生成的平均包數為λ，λ獨立于網關(AG)的總數。當網絡節點數N增加時，網絡流量總數也會相應增加。每一個AG都有最大的流量負載ρmax。本文使AG的max降低以保證負載不會超過AG實際容量的90%。也就是說，AG被降低的最大流量負載是0.9ρmax。為了得到網關數量，必須獲得以下信息：每一個網關的無線信號覆蓋面積、節點密度σ、負載ρ。網關數量由式(6)得到：

#of IGs =（k×BW/×μ)/（max×ε）=（σ/ρ）/（max×ε）(6)

其中：k是所有的MANET節點；BW是帶寬；是活躍的節點數；μ為活躍的負載；ρ和分別為給定的負載和減少的最大負載，即max=0.9ρmax；ε是網關的效率；σ是在網關覆蓋范圍內的移動節點數。

考慮兩種情況：a)網絡中只有一個網關。將平均跳數值記做=1/n∑ni=1hi。這意味著網絡中存在-1個中繼節點，令節點S是網關AG中繼節點的可能性為(-1)/(n-1)。Ad hoc網絡中任一節點都可能為其他(n-1)個節點的中繼節點。因此，在任一節點的中繼流量是λ(-1)，那么每一個節點的總容量用式(7)表示：

2網關選擇策略分析

上文從不同角度討論了一些典型的MANET與Internet互連的網關選擇策略。從目前研究者們提出的各種網關發現策略來看，最簡單的方法是以移動節點到網關的跳數作為選擇標準；但僅用跳數存在一些缺陷，因此第二類方法是在跳數的基礎上又考慮到其他因素，如網關負載等，即綜合跳數與其他因素一起作為選擇標準。最后一類方法是直接選取跳數之外的因素作為選擇標準。因此，根據各種網關選擇策略所采用的不同選擇標準，可以將網關發現策略分成以下三類，如圖3所示。

基于跳數的策略就是最短路徑方法。MTV策略、MMGD策略和hops+load策略屬于第二類方法。MTV策略考慮到節點的移動性因素，其目的就是要找到較穩定路由上的網關。這一方法的優點是減輕了由外圍節點移動、分組丟失、分組延遲造成的路由重建所引起的負擔，但引入的新路由表卻增加了計算量，消耗了一定的處理功率。MMGD策略的目標是選擇那些避開高數據流量或許多節點競爭無線信道路徑上的網關。仿真結果表明，在高信道爭用的擁塞的Ad hoc網絡中，MMGD策略能夠很好地改善分組投遞率和網絡性能，但目前的MMGD策略只支持主動網關發現方法。

在用跳數和負載作為網關選擇標準的策略中，最早的方法是選取不同的評判依據權重值，即(α，β)組合對找最佳網關，但僅用注冊到網關的MANET節點數來定義網關的負載并不全面。Load－balancing 策略采用網關的流量負載，其目的就是要選擇較少負載的網關，同時有效地利用資源。該策略是對單純采用跳數或load策略的一個折中考慮。這是因為最小跳數方法所選擇的最短路徑從負載平衡的角度來看并不一定是最佳的。然而，最小跳數卻是一個節約資源的方法。在負載平衡策略中，移動節點為了連接到一個輕負載的網關，也許需要經過許多中間節點，這將導致這些節點更多的網絡流量。因此，理想的方法應該是在最小跳數與負載平衡之間進行一定的折中考慮。在網絡擁塞的情況下，load－balancing策略可以使負載平衡分布；與單純基于跳數和負載的策略相比，策略可以提高數據分組傳送率，并減少平均延遲時間和分組丟失率。

基于load的策略屬于第三類方法，用網關負載作為選擇標準。它設計了一個被動網關發現方法，可以使負載均分到多個網關上；網關用一個延遲的P－RREP消息或代理請求通告(S－AA)消息作為RREQ或代理通告(AS)消息的回復，其中延遲被均分到當前各網關的負載中。源節點從較少擁塞的網關收到第一個P－RREP或S－AA消息的可能性較高，因此源節點就將這個網關作為默認網關。基于load策略的優點是可以平衡網關之間的負載并最終避免網絡擁塞。但是移動節點為了連接到一個輕負載的網關需要經過許多中間節點，因此基于load策略的效率不高。

3結束語

本文給出了移動Ad hoc網絡與Internet互連的網關選擇策略的分類方法，系統地描述了當前各種典型的網關選擇策略。目前，研究者們提出的網關選擇策略都存在各自的優勢與不足，并且只適合于一些特定場合。文獻[8]提出的load－balancing 策略將跳數和網關負載進行了折中考慮。這一策略是目前網關選擇策略中較理想的策略。網關選擇策略所面臨的挑戰和發展方向是如何更好地提供QoS保證。

參考文獻：

［1］胡中功，鄒莉，沈斌. Mobile Ad hoc network與Internet互連的技術研究[J].武漢科技學院學報， 2005， 18(6):65－69.

[2]SHIN C G， KIM S H， SHIN S. Stable gateway selection scheme based on MANET with Internet[C]//Proc of CIT.2006.

[3]JONSSON U， ALRIKSSON F， LARSSON T，et al. MIPMANET: mobile IP for mobile Ad hoc networks[C]//Proc of MobiHoc’2000.Boston: [s.n.]，2000:75－85.

[4]SUN Y， BELDING－ROYER E M， PERKINS C E. Internet connectivity for Ad hoc mobile networks[J].International Journal of Wireless Information Networks，2002，9(2):75－88.

[5]FU Yi，CHAN K M，TAN K S，et al. Multi－metric gateway discovery for MANET[C]//Proc of the 63rd VTC’06.2006:777－781.

[6]SHIN J，LEE H，NA J，et al. Load balancing among Internet gateways in Ad hoc networks[C]//Proc of the 62nd VTS’05.2005: 1677－1680 .

[7]AMMARI H，EI－REWINI H. Using hybrid selection schemes to support QoS when providing multihop wireless Internet access to mobile Ad hoc networks[C]//Proc of the 1st International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks.Washington DC:IEEE Computer Society，2004:148－155.

[8]PARK B，LEE C. QoS－aware Internet access schemes for wireless mobile Ad hoc networks[J].Elsevier Computer Communications， 2007，30(2):369－384.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文