分級移動ＩＰｖ６中一種新的自適應ＭＡＰ選擇算法

摘 要：分級移動IPv6中存在單點故障和負荷集中問題。提出一種基于分布式MAP結構的自適應MAP選擇算法，綜合考慮移動節點的當前速度、會話到達率、MAP負荷及距離等因素，以MN注冊后將產生的移動性管理信令開銷最小為依據進行選擇。仿真結果表明，自適應MAP選擇算法能夠根據移動節點和網絡的當前特性優化地選擇不同的MAP進行注冊，使移動性管理信令開銷最小，具有較好的負荷分擔效果，并一定程度上增強了分級結構的魯棒性。與最遠/近MAP選擇方案相比，自適應MAP選擇算法能夠提高網絡的吞吐量及減少平均切換時延。

關鍵詞：分級移動IPv6；移動錨節點；分布式；負荷分擔

中圖法分類號：TN915．04； TP393 文獻標識碼：A 文章編號：1001-3695(2006)10-0229-03

Novel Adaptive MAP Selection Algorithm for Hierarchical Mobile IPv6

HU Xiao，SONG Junde，SONG Mei

(College of Electronic Engineering， Beijing University of Posts Telecommunications， Beijing 100876， China)

Abstract:There exist the problems of the single point of failure and load convergence in hierarchical mobile IPv6. An adaptive MAP selection algorithm is proposed based on the distributed MAP architecture， which takes multiple factors into consideration such as MNs uptodate velocity and session arrival rate， MAPs load and distance. This algorithm selects the proper MAP according to the criteria of minimizing the signaling cost associated with mobility management. The simulation results show that the adaptive MAP selection algorithm can optimally select the MAP for different mobile nodes， balance the MAPs loads and increase the robustness of hierarchical structure at some extent. When compared with the furthest/nearest MAP selection schemes， the adaptive MAP selection algorithm can reduce the average handover latency and increase the throughput of the visited network.

Key words:Hierarchical Mobile IPv6 (HMIPv6);Mobility Anchor Point (MAP);Distributed;Load Balancing

移動IP是目前被普遍接受的解決移動終端在異種網絡間漫游的移動性管理技術［1］。但是，隨著小區范圍的縮小，用戶數量的增多，切換次數會大量增加，基本移動IP中用于移動性管理的信令開銷將急劇上升，而且切換時延增大，丟包率上升，使得系統性能嚴重下降。研究人員通過引入微移動性概念和分級結構來改善基本移動IP的性能，如分級移動IPv6（Hierarchical Mobile IPv6）， 蜂窩IP（Cellular IP）和區域注冊（Regional Registration）等［2］。但是，當前提出的分級結構存在兩個嚴重問題:①分級結構的魯棒性差［3］。其網關代理（如MAP，GFA等）是單點故障點，一旦網關代理失效，其服務域內的所有移動訪問節點將失去與網絡的連接。②網關代理是信令和業務的集中點。若沒有負荷分擔機制，容易造成節點負荷過重，從而影響整個網絡的性能。

1 相關研究

（1）分級移動IPv6（HMIPv6）

HMIPv6［4］是分級移動性管理中的一種典型方案，通過引入MAP(Mobility Anchor Point)節點將移動節點（MN）的位置更新過程本地化，并支持路由優化和快速切換。HMIPv6的分級MAP結構如圖1所示，MAP0為根MAP。當MN進入新的訪問域時，它會收到AR發出的路由器廣播消息（RA）。如果該訪問域包含多個MAP，則RA中含有多個MAP OPTION，每個MAP OPTION中包含相應MAP的優先級(可以根據MAP的負荷和工作情況調整)和MAP與AR的距離(跳數)。在MN需要進行注冊或位置更新時，首先要判斷向哪個MAP進行注冊。簡單的MAP選擇算法是選擇優先級不為零，且距離最遠的MAP進行注冊，以減少位置更新的次數［4］。以圖1為例，所有進入訪問域的MN都將選擇MAP0進行注冊，故MAP0節點的負荷會很重，并且其失效將使所有移動訪問節點均失去網絡連接。

（2）MAP選擇算法

文獻［4］中除提出基本的最遠MAP選擇算法外，也建議對優化的MAP選擇算法進行研究。相繼有基于速度和基于移動性［5］的MAP選擇算法被提出，這些算法考慮了移動節點的運動特性，更能合理地、動態地選擇MAP。但這些算法也存在兩個問題：①算法中沒有考慮移動節點的業務特性和MAP負荷這兩個因素，而實際上這兩個因素對MAP的選擇也很重要。例如業務量高的MN應該注冊到距離較近的MAP，以減少切換時延。②這些算法中均采用了固定的閾值來區分速度和移動性的等級，但是在不同的業務特性和網絡條件下，如何合理地設定這些閾值是比較困難的。

2 自適應MAP選擇算法

針對分級移動IPv6的單點故障和負荷集中問題，本文提出一種基于分布式MAP結構的自適應MAP選擇算法，使MN可以動態地選擇MAP進行位置更新，這在一定程度上可以達到負荷分擔和增強分級結構魯棒性的效果。該算法綜合考慮了MN的當前速度、會話到達率(Session Arrival Rate)、MAP負荷及距離因素，最優地選擇MAP，并無須設置固定的閾值來進行判斷。

（1）分布式MAP結構

在MAP部署上，采取一個訪問域內放置多個MAP，MAP與MAP之間沒有固定的分級關系，形成分布式MAP結構，如圖2所示。通常情況下，由一個MAP覆蓋整個訪問域，如MAP0，其余MAP覆蓋區域較小的熱點地區，如MAP1.1和MAP1.2。一般地，MAP0與AR的距離要遠一些，MAP域之間可以部分或全部重疊。MAP與AR之間仍然是分級結構，AR通過廣播該MAP的MAP OPTION表明AR屬于該MAP域，一個AR可以屬于多個MAP域。

（2）自適應MAP選擇算法

自適應MAP選擇算法綜合考慮了MN的當前速度、會話到達率、MAP負荷及距離等因素，以MN注冊后將產生的移動性管理信令開銷最小為依據進行選擇。如MN注冊到MAP0將產生信令開銷為C0，MN注冊到MAP1將產生信令開銷為C1，若C1＜C0，則MN選擇向MAP1進行注冊。可以看出，本算法的關鍵是要推導出MN注冊到不同MAP下的移動性管理信令開銷。

（3）移動性管理信令開銷

移動性管理信令開銷（信令開銷）的公式如式（1），包括兩部分：CLU為MN的位置更新(Location Update)開銷，即MN在位置變化后或周期性地向HA或MAP進行注冊時的信令開銷；CPD為分組傳遞（Packet Delivery）開銷，即發往MN的分組要經過一定的處理和傳送才能最終到達MN。

C=CLU+CPD（1）

為了詳細推導信令開銷公式，我們作如下假設：①AR域與MAP域均是正方形，一個MAP域內包含k× k個AR，AR域的邊長為l， 則MAP域的周長為L=4kl。②移動節點以密度ρ在MAP域內均勻分布，平均速度為v，運動方向在［0，2π］內均勻分布。根據文獻［6］，移動節點跨AR域的切換速率為rl=［ρv(4l)π］/［ρ(kl)2］=4vk2lπ（updates/s/terminal）；跨MAP域的切換速率為rh=4vklπ（updates/s/terminal）。③我們在MAP OPTION的保留區域添加了MAP當前已經注冊的MN個數，作為衡量節點負荷的一個因素。

①位置更新開銷

這里忽略MN的周期性位置更新開銷，因為這個開銷對于任何一種位置更新算法都是一樣的。簡化的位置更新開銷公式如下：

CLU=rhCuh+(k2rl-rh)Cul（2）

Cuh/Cul是MN進行家鄉注冊/區域注冊時位置更新信令的處理和傳輸開銷。對照分級移動IPv6的家鄉注冊和區域注冊過程，它們分別為式（3）和式（4）：

CUh=2af+2ag+ah+2Chg+2Cgf+2Cfm=2af+2ag+ah+2(lhg+lgf+ω)δU(3)

CUl=2af+ag+2Cgf+2Cfm=2af+ag+2(lgf+ω)δU(4)

其中，Chg/Cgf/Cfm為位置更新信令在HA、MAP/MAP、AR/AR和MN之間的傳輸開銷；ah/ag/af為HA/MAP/AR上位置更新信令的處理開銷；δU為上行傳輸開銷與距離的比例常數；lhg/lgf為HA與MAP/MAP、AR之間的平均跳數；ω為單位距離上無線鏈路傳輸開銷為有線鏈路的倍數。

②分組傳遞開銷

如文獻［7］中定義，總分組傳遞開銷為HA，MAP和AR上的分組傳遞開銷之和，其公式如下:

CPD=CCNMAPPD+CMAPARPD+CARMNPD(5)

因為HMIPv6支持路由優化，即只有CN發送的第一個分組經由HA轉發，其余分組均直接路由給MAP，則從CN到MAP的分組傳遞開銷為

CCNMAPPD=λinδD(lch+lhg）+λin(E-1)δD×lcg+λinη(6)

其中，λin為MN的會話到達率；E為每個會話的平均分組個數；δD為下行傳輸開銷與距離的比例常數；lch/lcg為CN與HA/CN、MAP之間的平均跳數；η為HA上單個分組的處理開銷。

從MAP到AR的分組傳遞開銷為

CMAPARPD=λinE(δDlgf+PMAP）=λinE［δDlgf+(αn+βlog k)+φ］(7)

其中，n為MAP上已注冊的MN個數；α/β為訪問列表和路由表查詢的權重因子；k為MAP域內AR的個數；φ為MAP上單個分組的封裝/解封裝開銷。

無線鏈路上，從AR到MN的分組傳遞開銷為

CARMNPD=λinEωδD(8)

（4）會話到達率和速度的獲取

在計算MN的信令開銷時，需要獲得MN當前的移動速度和會話到達率。MN的移動速度可以通過統計MN在本次位置更新之前經過一個或n個小區所需時間T，利用已知的小區邊長估計MN經過的距離，以此來估計其速度。MN的會話到達率可以采用文獻［8］中的方法進行估計，當會話到來過程符合泊松分布時，該迭代方法得到的結果為會話到達率的無偏估計。

3 仿真結果

我們采用NS2作為仿真平臺，實現了分級移動IPv6和自適應MAP選擇算法。使用綜合的仿真場景（包括多種用戶移動模型［9］）來測試自適應MAP選擇（AMAP）方案的性能，并與最遠MAP選擇（FMAP）方案和最近MAP選擇（NMAP）方案進行比較。FMAP方案如前所述，可以減少切換次數；NMAP方案即MN總是選擇可用MAP中距離最近的一個注冊，如果MN總是在同一MAP域中移動，那么該方案的切換時延較小。仿真拓撲結構類似圖2，MAP0域中共有12個AR，MAP1.1和MAP1.2域中各包含四個AR。各AR之間重疊覆蓋，整個訪問域為無縫覆蓋。仿真場景中共30個MN，其中，16個MN符合熱點運動模型［9］，分布于MAP1.1域和MAP1.2域；14個MN為車道運動模型和隨機運動模型［9］，分布于MAP0域。

(1)信令開銷

圖3中，FMAP 方案的總信令開銷最小，而NMAP方案的總信令開銷最大，其原因是FMAP 方案下MN跨MAP域的切換次數最少。AMAP方案的信令開銷與FMAP方案非常接近，因為在AMAP方案中，MN綜合多種因素選擇合適的MAP，如速度快的MN將選擇MAP0注冊，速度慢的MN將選擇MAP1.1/MAP1.2注冊，所以MN跨MAP域的切換次數也是很少的。

(2)負荷分擔

定義每個MAP上注冊的MN個數為該MAP的負荷。從圖4中可以看出，FMAP方案不能分擔負荷，而NMAP和AMAP方案能夠在一定程度上進行負荷分擔。在NMAP方案中，MAP0的負荷在五個MN上下波動，而MAP1.1/MAP1.2的負荷在12個MN上下波動。其原因是符合車道運動模型和隨機運動模型的MN會經常更換MAP，而這種情況在AMAP方案中不存在，因為只要MAP和MN的特性參數變化不大，那么MN不會經常更換MAP。所以，經過一段時間，MAP0的負荷穩定在14個MN，而MAP1.1/MAP1.2的負荷穩定在八個MN。

(3)切換時延

切換時延為切換前最后一個分組到達時間與切換后第一個分組到達時間的間隔。這里，采用所有MN的平均切換時延作為衡量指標，每20s統計一次。圖5中，AMAP方案的平均切換時延最小，FMAP方案次之，NMAP方案最大。AMAP方案與FMAP方案相比，由于部分MN向距離較近的MAP1.1/MAP1.2注冊，故AMAP方案的平均切換時延更小；而NMAP方案中MN跨MAP域的切換次數較多，因此導致其平均切換時延增大。

(4)吞吐量

這里的吞吐量指整個訪問域的吞吐量，即通過三個MAP的總分組業務量。通信對端節點(Correspond Node)每隔50s增加200Kbps的數據帶寬。從圖6可以看出，FMAP方案的吞吐量在350s后趨于飽和（此時，每個通信對端節點發送的數據為1.2Mbps，總共1.2Mbps×30=36Mbps），這是因為MAP0與中心路由器之間的鏈路帶寬為40Mbps，而FMAP方案中的所有分組均經過MAP0，接近該鏈路的容量。在NMAP和AMAP方案中，由于進行了負荷分擔，故整個訪問域的吞吐量沒有飽和的趨勢，并且兩者的吞吐量是相同的。

4 結束語

基于分布式MAP結構，本文提出了一種自適應MAP選擇算法，該算法綜合考慮了MN的速度、會話到達率、MAP的負荷和距離因素，為MN選擇最優的MAP。自適應MAP選擇算法能夠進行MAP負荷分擔，并一定程度上增強了分級結構的魯棒性。仿真結果顯示，在三種MAP選擇方案中，綜合考慮信令開銷、負荷分擔，切換時延和吞吐量這幾個指標，自適應MAP選擇方案是最優的，并且，該算法不需要事先設置閾值進行判斷，使其可以適用于不同的應用場合。

參考文獻：

［1］Perkins C.IP Mobility Support［S］. RFC2002， IETF，1996.

［2］Campbell A T， Gomez J， Sanghyo Kim，et al.Comparison of IP Micromobility Protocols［J］. IEEE Wireless Commun.，2002，9(1):72-82．

［3］Omar H， Saadawi T， Lee M. Supporting Reduced Location Management Overhead and Fault Tolerence in MobileIP Systems［C］.Proc. of IEEE Symposium on Computer and Communications，1999.347-353.

［4］Soliman H， Castelluccia C， ElMalki K，et al. Hierarchical MIPv6 Mobility Management［Z］. draftietfmobileiphmipv6-08.txt，IETF Draft，2003.

［5］Natalizio E， Scicchitano A， Marano S. Mobility Anchor Point Selection Based on User Mobility in HMIPv6 Integrated with Fast Handover Mechanism［C］. IEEE Communication Society/WCNC，2005.14341439．

［6］Thomas R， Gilbert H， Mazziotto G. Influence of the Moving of the Mobile Stations on the Performance of a Radio Mobile Cellular Network［C］.Proc. of the 3rd Mordic Seminar on Digital Land Mobile Radio Communication，1988.

［7］Sangheon Pack， Minji Nam，Yanghee Choi.A Study on Optimal Hierarchy in MultiLevel Hierarchical Mobile IPv6 Networks［C］. IEEE Communications Society/GLOBECOM， 2004.290-294.

［8］Xie H，Tabbane S， Goodman D J. Dynamic Location Area Management and Performance Analysis［C］．Proc.of the 43rd IEEE VTC，1993.536-539.

［9］Hu Xiao， Song Junde，Ni John，et al.An User Profile Based Adaptive Paging Scheme for Mobile IP［C］．Proceedings of 2004 Global Mobile Congress，2004.514-519.

作者簡介：

胡曉(1972-)，女，博士研究生，主要研究方向為移動互聯網、移動IP相關技術；宋俊德(1938-)，男，教授，博導，主要研究方向為下一代通信網、網絡融合等；宋梅(1960-)，女，教授，主要研究方向為下一代通信網、移動性管理等。

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