基于負載均衡的MAP選擇方案的研究

孫文勝 馮志常

(杭州電子科技大學通信工程學院 浙江 杭州 310018)

基于負載均衡的MAP選擇方案的研究

孫文勝 馮志常

(杭州電子科技大學通信工程學院 浙江 杭州 310018)

針對層次移動IPv6中，移動節點(MN)選擇移動錨點(MAP)沒有考慮負載的問題，提出一種基于負載均衡的MAP選擇方案。在該方案中，當路徑中路由器的負載度量值大于所設置的閾值時，路由器就會丟棄數據分組以減小網絡內的擁塞。當MN進入新網絡時，根據設置的實時度量值來選擇負載小的路徑，然后向該路徑的源MAP進行注冊，使MN可以根據路徑負載的不同來選擇不同層的MAP，避免某些MAP成為整個網絡的瓶頸，均衡整個網絡的MAP負載。模擬實驗結果表明，該方案能使網絡中的MAP負載更加均衡。

HMIPv6 MAP選擇 負載均衡

0 引 言

近年來，隨著信息技術和經濟水平的飛速發展，人們的手持移動設備越來越多，如何減小移動終端切換時的時延是當下研究的熱點。移動IPv6(mobile IPv6，MIPv6)是目前被普遍接受的移動IP技術，但是由于移動主機切換時存在切換時延高的問題，不能很好滿足人們的實時需求。為此，互聯網工程任務組IETF(Internet Engineering Task Force)提出了層次移動IPv6(hierarchical mobile IPv6，HMIPv6)協議。HMIPv6通過引入移動錨點MAP(Mobile Anchor Point)并采用層級管理方式來優化MIPv6切換性能，當移動節點MN(Mobile Node)在域內移動時，其不必向歸屬代理HA(Home Agent)和對端節點CN(Correspondent Node)進行綁定注冊，大大減小了MN在域內的切換時延。因此為MN選擇一個最佳MAP，提高網絡的整體性能成為HMIPv6一個關鍵問題[1]。

目前主流的MAP選擇機制有：基于距離的MAP選擇機制和基于速度的MAP選擇機制[2]?；诰嚯x的MAP選擇機制是HMIPv6默認的方案，在該方案中，MN選擇層級最高的MAP，顯著減少了MN在域間切換的次數，但這種機制比較簡單，如果網絡中有大量的MN，最上層的MAP就會因為負載太大而使網絡性能大大降低[3]，成為整個網絡的瓶頸。對于如何根據MN的速度選擇最優的MAP，人們也提出了很多方案。如基于速度閾和基于MN移動的軌跡，它們都是根據MN的速度來選擇最佳MAP，但是由于MN運動時隨機性太大，很難準確地估計出它的速度。并且當網絡中MN的移動速度都相同時，它們就會選擇相同的MAP，使網絡中的某些MAP負載嚴重而成為整個網絡的瓶頸，而且MN的速度估測得未必準確。

除了上述兩種方案，文獻[4]提出了一種基于變換模擬退火思想的MAP選擇機制。該方案在MAP選擇過程中加入了隨機機制，MN在某一MAP域中停留時間越長，其就有越大的概率選擇底層的MAP。但是當網絡中MN非常少或有大量速度快的MN時，該方案的效果較差。文獻[5]提出了基于網絡拓撲的MAP選擇方案，該方案不用預先設定閾值，修改了路由器報文格式，但需要搜索拓撲的間隔要足夠短。文獻[6]提出了主動預防MAP過載的方案，在該方案中，MAP周期性的動態估計自身的負載，并向接入路由器AR(Access Router)發送自身的負載信息，AR根據收到的MAP負載信息，按照主動預防策略來選擇MAP，可如果網絡中存在大量MN和MAP，信令開銷會顯著增大。文獻[7]提出了基于移動特征的MAP選擇方案，該方案根據MN的移動特點動態地選擇MAP，通過設定固定閾值來區分不同速度和移動性等級的MN，但是如何針對不同類型的MN設定合理的閾值是比較困難的。

針對上述方案在選擇MAP沒有很好考慮MAP負載的問題，本文提出一種基于負載均衡的MAP選擇方案，該方案使MN可以根據路徑負載的不同來選擇不同層的MAP，使網絡的MAP負載更加均衡。

1 層次移動IPv6簡述

如圖1所示，HMIPv6將網絡分成不同的域，每個域中都有一個MAP充當臨時歸屬地代理。 MN在漫游的過程中，如果是在同一個域中的不同接入點之間發生切換，叫做域內微移動，如果在不同區域之間切換，就叫做域間宏移動。MN在發生切換后，會接收到AR發出的路由器通告RA(Router Advertisement)消息，MN從RA消息中可以獲得所在網絡所有MAP的選項信息，如MAP 的優先級、從MN到MAP的距離、MAP的地址等。MN可以依據上述信息判斷自身是否移動到新的MAP管理域中[8]。

圖1 HMIPv6網絡拓撲

若MN判斷出自身已經移動到新的MAP管理域中，即發生域間宏移動時，它將依據RA報文來選擇新的MAP并進行注冊，然后再向HA和CN進行注冊更新，成功后新MAP就可以為MN轉發消息。若MN發生了域內微移動，只需向當前的MAP進行注冊，和域間宏移動相比，大大減小了信令開銷。圖2為HMIPv6的切換處理流程圖。

圖2 HMIPv6的切換處理流程

2 基于負載均衡的MAP選擇方案

在當前RA報文中，加入了新的MAP選項信息，其中包括：MAP 的優先級、從MN到MAP的距離、MAP所在網絡的網絡前綴等信息。本文提出的基于負載均衡的MAP選擇方案中所有的MAP都要單獨發送消息，所以在MAP選項信息中不再需要MAP的優先級。

2.1 路徑中路由器的負載度量機制

設計負載均衡協議的首要任務是確定負載度量方案，而MAC層接口隊列分組長度QLI(Queue Length of Interface)和接口隊列分組長度增量QLII(Queue Length Increment of Interface)不但直接反映了業務數據流量的情況，也間接反映了MN對共享廣播信道的競爭情況。因此本文使用兩者作為路由器的負載度量值。

在該方案中，為路徑中的路由器的負載度量值設定動態閾值(其中QLI的閾值為ΓQLI，QLII的閾值為ΓQLII)。當路徑中路由器收到上層路由器傳遞的消息時，不是馬上傳遞此消息，而是將自己的負載值與閾值相比較。若是小于閾值，則說明自身的負載較輕，繼續往下層傳遞數據，若是大于閾值，則說明自身的負載較重，應丟棄該中間數據分組。如果路由器同時滿足下面兩個條件，則路由器自身負載嚴重：

CurrentQLI>ΓQLI

CurrentQLII>ΓQLII

其中，ΓQLI是動態變化的，它反映了網絡負載的情況，隨網絡流量的變化而變化，它的計算方法為：

(1)

式中，AveTraffici是路由器i的負載平均值，SumAveTraffic是路徑中路由器i上層的路由器負載平均值之和，ni是從源MAP到路由器i的路徑上MAP的個數。

2.2MN對路徑的負載度量機制

本文使用路由器的隊列可用率ARQ(availableratioofqueue)、MAP收到的LBU報文總個數和路徑的跳數(HOP)作為路徑的即時負載度量值。當MN進入到一個域中時，會收到多個路徑的負載信息，所以MN需要對這些路徑上的信息進行比較，根據一定的機制選擇最佳的路徑。本文選擇的機制如下：

(1) 路徑上所有路由器的ARQ

第i個路由器的ARQ計算公式為：

(2)

式中，AQLIi=MQLIi-CQLIi，AQLIi為第i個路由器上可用的QLI，MQLIi為路由器i最大的QLI，CQLIi為第i個路由器當前的QLI。所以路徑r上的所有路由器的隊列可用率為：

ARQr=∏i∈NrARQi

(3)

ARQr的值越大，說明該路徑上所有路由器的隊列可用率越高，路徑r上的業務流量越小，應該選擇這一路徑作為最佳路由。ARQr越小，該路徑被選擇的概率就越小。

(2) 路徑r上MAP已經收到的LBU總數目NRr

MAP收到的LBU報文數量NRi越大，就說明該MAP要為越多的MN建立隧道，并通過隧道技術將CN發送給MN的數據轉發給MN，其需要處理的業務流量也就越大。路徑r上所有MAP收到的LBU報文個數NRr計算公式為：

NRr=∑i∈NrNRi

(4)

其中NRi為第i個MAP收到的LBU報文數量。

(3) 路徑r上的跳數HOP

HOP為從發送RA報文的源MAP到最終AR的跳數，路徑上的HOP越小意味著MN和MAP之間的路由器越少，這樣在其他條件相同的情況下，兩者之間傳輸的開銷越小。

根據ARQr、NRr和HOP，得出衡量路徑r上總負載LR(LoadofRoute)的計算公式為：

LR=a×(1-ARQr)+b×NRr+c×HOP

(5)

其中，a、b、c為預設的負載參數，在實驗時根據各個負載值的重要性來賦值。MN在收到RA消息時，根據上式計算出LR，選擇LR最小的路徑為最佳路由，并選擇該路徑上的MAP進行注冊。

2.3 方案描述

(1) 源MAP的操作

在基于負載均衡的MAP選擇方案中，每一個MAP都單獨向下層傳遞消息。因為MN在收到RA消息后是根據MAP的負載情況來選擇MAP，因此在MAP選項中不再需要MAP的優先級。同時在路由器通告消息中的可變長度選項中加入ARQ、NRr兩個字段來衡量該條路徑上的負載。其中ARQ、NRr都初始化為零。

(2) 路徑中路由器的操作

當路徑中路由器收到上層MAP傳來的消息時，根據QLI和QLII判斷自身是否重負載，如果自身當前的QLI、QLII分別大于閾值ΓQLI、ΓQLII，則說明路由器嚴重負載，應丟棄該分組，否則就根據式(3)更新ARQ的值，并將HOP的值加1。如果路由器收到MN發送的本地綁定更新消息，若目的地址不是自己，則把該消息單播出去；若目的地址就是自身，就為發送消息的MN的RCoA和LCoA建立綁定關系，并將自身存儲的NRi加1。

(3)MN的操作

當MN移動到新的MAP管理域后，最初默認選擇最高層MAP。當MN在新網絡中收到多條RA消息后，根據式(5)計算各路徑的LR。從中選擇LR值最小的路徑，向該路徑上的源MAP注冊。如果有多條路徑的LR值相同，就選擇最早收到的消息路徑上的源MAP并向其注冊。

3 仿真實驗

3.1 仿真環境設置

依照圖3所示拓撲圖，在虛擬機VMWorkstations8.0的Redhat9.0環境中，用軟件NS-2模擬一個網絡來驗證方案性能。每個AR的管理區域為一個以自身為圓心、以50m為半徑的圓形，在網絡結構中，相鄰AR間的距離為90m，保證相鄰AR間有10m的重疊范圍，并且AR的間距相等。

MAP1與HA、CN的鏈路均采用尾部丟棄算法。其他鏈路采用隨機早期檢測算法。仿真實驗設置的鏈路參數為：MN通過2Mbps的802.11WLAN無線鏈路接入到AR，其中MAP與HA、CN的鏈路帶寬為100Mbps，鏈路時延設為10ms，來模擬MN與HA、CN距離遠的場景。AR與MAP之間的鏈路是帶寬為2Mbps的雙向鏈路，MAP與MAP間之間的鏈路是帶寬為5Mbps的雙向鏈路。有線鏈路時延是2ms，無線鏈路時延是10ms，每個鏈路都設定為duplex-link類型。

圖3 新MAP選擇方案模擬實驗拓撲圖

仿真實驗中總共有50個MN，把這些MN分為兩部分，其中一部分MN的速度需要手工設置，另一部分MN的運動是隨機的，并且運動方向為單方向移動。兩部分的MN個數之比為2∶1。為了使實驗結果更易分析，在需要手工設置速度的MN中，把高速移動的MN和低速移動的MN的個數之比設置為2∶1。

3.2 仿真結果及分析

本節將新的MAP選擇方案和現有的MAP選擇方案進行了對比，其中SD-MAP表示基于速度的MAP選擇方案，DE-MAP表示基于距離的MAP選擇方案，LB-MAP表示本文提出的基于負載均衡的MAP選擇方案。本文從信令開銷和負載均衡兩方面來比較三種方案。

圖4為三種方案的信令開銷對比圖。從圖中可知，DE-MAP方案的信令開銷最小，SD-MAP方案的開銷最大。這是因為在DE-MAP方案中，MN總是選擇最高層次的MAP即MAP1，切換的次數最小。SD-MAP方案是完全根據MN的速度來選擇MAP，并沒有考慮路由器的負載問題。LB-MAP方案的信令開銷介于兩者之間，這是因為LB-MAP方案考慮每一個路由器的負載情況，并會根據不同負載度量值重要性的不同而設置不同的參數，考慮的因素更多，當一條路徑的負載較大時，MN就會選擇另一條路徑的源MAP。

圖4 信令開銷分析對比

在HMIPv6中，將每個MAP注冊的MN個數定義為該MAP的負載。由于模擬實驗中總共有50個MN，因此每個MAP的最大負載為50個MN。在實驗開始的不同時間采集數據，并且從各層MAP的負載情況來分析。

圖5是第三層MAP的負載情況。從圖中可知，在DE-MAP方案中，第三層MAP負載始終為50個MN。SD-MAP方案在穩定后，最高層MAP的負載情況在30到40之間，這是因為模擬實驗中高速和低速MN個數之比在2∶1左右，高速的MN就會選擇高層MAP。在LB-MAP方案中，實驗開始時，所有MN都選擇了第三層MAP，和本文的方案符合，因為在LB-MAP方案中，模擬實驗開始時默認選擇最高層的MAP。但是隨著實驗的進行，當MN判斷出其他層MAP的負載更小后，會轉而選擇其他層的MAP，使最高層MAP的負載減小。

圖5 第三層MAP的負載情況

第二層MAP負載情況如圖6所示，從圖中可知，DE-MAP和SD-MAP方案在第二層MAP的負載始終為0。這是因為DE-MAP方案選擇的都是最高層的MAP；在SD-MAP方案中，高速的MN選擇最高層的MAP，低速的MN選擇最底層的MAP，使中間層MAP負載為0。在LB-MAP中，第二層MAP負載不為零，這是由于LB-MAP方案是根據負載來選擇MAP的，當MN發現第二層的MAP負載較小時，就會選擇該層的MAP。

圖6 第二層MAP的負載情況

第一層MAP負載情況如圖7所示。可以看出，DE-MAP方案在第一層的MAP負載為0，基于速度的SD-MAP方案在穩定后，最低層MAP的負載情況在10到20之間，這是因為模擬實驗中高速和低速MN個數之比在2∶1左右，低速度移動的MN選擇低層的MAP。在LB-MAP方案中， 最初最底層的MAP負載為0，隨著模擬實驗的進行，MN相繼選擇了最底層的MAP，這是因為MN在判斷出最底層的MAP負載較小時，會選擇最低層的MAP。

圖7 第一層MAP的負載情況

4 結 語

在DE-MAP方案中，MN選擇的全是最高層的MAP，雖然減小了信令開銷，但使最高層的MAP負載嚴重，容易成為整個網絡的瓶頸，同時其他層的MAP不能分擔最高層MAP的負載。在SD-MAP方案中，速度大的MN都選擇了最高層的MAP，速度小的MN都選擇了最低層的MAP，這樣就會使第二層的MAP處于空閑狀態，不能為其他層的MAP分擔負載。本文提出的基于負載均衡的LB-MAP方案，在實驗剛開始時和DE-MAP方案一樣，MN全都選擇最高層的MAP，但隨著實驗的進行，MN會根據MAP負載的不同來選擇其他層的MAP，每一個MAP都會承擔相應的負載，不會使一些MAP成為整個網絡的瓶頸，使整個網絡的MAP負載比較均衡。

但實驗的結果只是在虛擬機上仿真出來的，仿真環境的設置不同，模擬實驗的結果就會不同，并且仿真的環境和現實中還是有著很大差異，因此下一步要把方案應用到實際環境中。

[1] 王洪冠. 基于預測的MAP選擇算法的研究與實現[D]. 沈陽：東北大學, 2008: 71.

[2] 黃吉. 移動IPv6快速切換策略的研究[D]. 杭州：杭州電子科技大學, 2012: 70.

[3] 李明, 黃昌來, 任久春, 等.HMIPv6中的自適應MAP選擇算法[J]. 計算機應用與軟件, 2010, 27(3): 203-205.

[4] 白鑫茹. 一種分級移動IPv6的MAP選擇機制[D]. 廣州：華南理工大學, 2013: 71.

[5]SongJ,ZhangBJ,SunW,etal.AnimprovedfasthandoveralgorithmbasedonHMIPv6[C]//2007InternationalMulti-ConferenceonComputingintheGlobalInformationTechnology, 2007: 52.

[6]TaoM,YuanH,WeiW.ActiveoverloadpreventionbasedadaptiveMAPselectioninHMIPv6networks[J].WirelessNetworks, 2014, 20(2): 197-208.

[7] 朱小麗, 劉小甜. 一種基于MN移動特征的MAP選取算法[J]. 計算機工程, 2008, 34(21): 78-80.

[8] 李淵. 基于AdHoc網絡的跨層移動IPv6切換技術的研究[D]. 杭州：杭州電子科技大學, 2014: 64.

RESEARCH ON MAP SELECTION SCHEME BASED ON LOAD BALANCING

Sun Wensheng Feng Zhichang

(SchoolofCommunicationEngineering，HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

To deal with the problem that Mobile Node(MN) do not take load problem into account when it choose Mobile Anchor Point(MAP), an MAP selection scheme is proposed based on load balancing. In this scheme, when the load of the router in the path is greater than the threshold value, the data packet will be discarded to reduce the congestion in the network. When MN enters a new network, it will select the route with the smallest load according to the real-time measurement, and then register the source MAP. Thus, MN will select MAP in different layers according to the load of route, avoiding some MAP become the bottleneck of the entire network and balancing the MAP load in the whole network. The result of the simulation experiment shows that the new scheme can make the load of MAP in the network more balanced.

Hierarchical mobile IPv6 MAP selection Load balancing

2016-01-06。孫文勝，副教授，主研領域：多媒體通信與無線通信。馮志常，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2017.02.030