移动AdHoc接入网中外地代理选择算法的研究

计 算 机 工 程 第 33 卷 第20期

Vol.33 No.20 Computer Engineering · 网络与通信 ·

文章编号：1000—3428(2007)20—0119—03

文献标识码：A

2007年10月

October 2007

中图分类号：TP393

移动Ad Hoc接入网中外地代理选择算法的研究

陈 峰，马晓雷，刘元安

(北京邮电大学电信工程学院，北京 100876)

摘 要：在Ad Hoc接入网中，Ad Hoc节点通过外地代理与骨干网中的对等节点通信。外地代理的选择算法是影响Ad Hoc接入网整体性能的主要因素之一。针对Jelger算法存在切换频繁和平均跳数较大的缺点，该文提出了一种基于跳数和路由稳定度的改进算法。相对于Jelger算法，改进的算法可以减少切换次数和移动节点到外地代理的平均跳数，同时具有更小且更加稳定的丢包率。 关键词：Ad Hoc接入网；外地代理；Jelger算法；路由稳定度

Research on Foreign Agents Selection Algorithm

in Mobile Ad Hoc Access Networks

CHEN Feng, MA Xiao-lei, LIU Yuan-an

(Department. of Telecommunications Engineering, Beijing University of Posts and Telecommunications, Beijing 100876)

【Abstract】In Ad Hoc access networks, Ad Hoc nodes communicate with the correspondent nodes in the backbone networks via the foreign agent.One of the key components affecting the overall performance of Ad Hoc access networks is the algorithm used to select foreign agents. Since Jelgeralgorithm has the defect of frequent handoffs and more average hops, an improved algorithm based on hops and route stability http://wendang.chazidian.compared with Jelger algorithm, the proposed algorithm can remarkably decrease the handoff times and average hops to the foreign agents.Additionally, it has lower and more stable packets lost ratio.

【Key words】Ad Hoc access networks; foreign agents; Jelger algorithm; routing stability

Ad Hoc 网络通常被认为是一种独立的自组织网络。在 第4代移动通信系统的研究中，Ad Hoc网络不再作为一个独立自治的网络，而是作为一种接入网络连接到骨干网络中，称之为Ad Hoc接入网。 Ad Hoc接入网可以利用节点的多跳转发能力扩大移动通信系统的通信范围，均匀相邻子网的业务，提高小区边缘的数据速率。

无线Ad Hoc接入网的研究要点包括外地代理发现机制、外地代理选择算法和不同外地代理之间的切换算法。本文主要研究外地代理选择算法。不同的选择算法基于不同的参数，如跳数、网络负载等。目前提出的外地代理选择算法有基于跳数的Jelger算法[1]、基于跳数和网络流量的选择算法[2]，以及基于平衡网络负载的选择算法[3]等。由于跳数是影响Ad Hoc接入网通信质量的重要因素，因此本文提出的改进算法选择以Jelger算法为基础。

Jelger算法提出了3种更新算法以确定移动Ad Hoc节点选择哪个移动节点作为自己的上游邻居节点。其中F_DISTANCE 算法侧重于最小跳数，不考虑可能引起的频繁切换问题；F_DISTANCE_STABILITY和F_DELAY算法可以防止Ad Hoc节点在两个外地代理交界处来回移动引起的频繁切换，但是会造成节点无法接入到跳数更少的外地代理，从而带来一定的时延。本文提出了一种改进的外地代理选择算法，利用跳数和路由稳定度的限制，平衡了节点到外地代理的跳数和节点在不同外地代理之间切换次数的矛盾。

发现机制和Hybrid机制。Proactive机制是指外地代理通过洪泛的方式定期地广播代理通告，Ad Hoc接入网内的移动节点在收到代理通告后，根据代理通告内的反向路由信息更新本节点到外地代理的路由。Reactive机制是指移动Ad Hoc节点通过发起请求来发现外地代理。Ad Hoc节点将请求信息广播到邻居节点，邻居节点检查本节点的外地代理列表，如果该节点的外地代理列表内存在到某个外地代理的路由表项，就单播一个回复信息给请求节点，否则将外地代理请求转发给本节点的邻居节点。Hybrid机制是指通过限制代理通告的广播范围来防止代理通告在Ad Hoc网络内洪泛，减少网络负载。只有在广播范围之内的节点才能收到代理通告，没有收到代理通告的节点通过Reactive机制来发现外地代理。 1.2 注册

需要接入骨干网的移动节点在收到外地代理的代理通告后要向外地代理注册，因为一些移动节点可能不需要接入到骨干网，外地代理必须通过注册消息来确认需要接入骨干网的移动节点的身份。首先，移动节点发送一个注册请求到外地代理，其中包括本节点的家乡地址，家乡代理地址和转交地址。外地代理将收到的注册请求转发给请求节点的家乡代理，家乡代理收到注册请求后为请求节点创建相应的表项并

基金项目：国家自然科学基金资助项目“移动性无线传感器网络研究”(F020303)；IST-FP6 Daidalos项目；与Microsoft合作异构网络融合项目

作者简介：陈 峰(1983－)，男，硕士研究生，主研方向：Ad Hoc网络；马晓雷，博士研究生；刘元安，教授、博士生导师 收稿日期：2006-10-25 E-mail：chenf.f1@http://wendang.chazidian.com

1 移动Ad Hoc接入网

1.1 外地代理发现

外地代理发现机制主要有3种：Proactive机制，Reactive

—119—

设定注册有效时间。最后，外地代理将从家乡代理反馈的注册回复转发给请求节点，请求节点收到注册回复后为该外地代理表项设定生存时间，节点必须在生存时间内重新向外地代理注册以更新注册有效时间。 1.3 路由发现

Ad Hoc网内的移动节点要与目的节点通信必须首先确定目的节点是否在Ad Hoc网内。首先，移动节点通过AODV[4]在Ad Hoc网内寻找到目的节点的路由，如果移动节点在一定时间内没有收到回复消息，则重新发起请求。如果尝试一定次数之后仍然没有收到回复消息，移动节点则认为目的节点不在Ad Hoc网内，于是移动节点就通过外地代理与目的节点进行通信。

路由会由于节点的随机移动而频繁的中断，导致数据包丢失，甚至通信中断。因此，选择具有较高路由稳定度的外地代理可以减少丢包率，提高通信质量。

(a)

2 外地代理的选择

在Ad Hoc网络内有多个外地代理的情况下，Ad Hoc网内的移动节点将会收到多个外地代理广播的代理通告，移动节点需要从中选择一个最优的外地代理。

Jelger算法是IETF提出的以跳数作为参数的选择算法，主要是通过确定移动节点的上游邻居节点来确定外地代理，包括3种更新算法：

(1)F_DISTANCE：该算法根据移动节点到外地代理的跳数来选择外地代理。移动节点收到邻居广播的代理通告信息后，将代理通告信息中的跳数与本节点至当前外地代理的跳数进行比较，如果代理通告中的跳数比该节点到当前外地代理跳数值小，则将上游邻居更新为发送此代理通告的邻居。

(2)F_DISTANCE_STABILITY：该算法与F_DISTANCE算法基本类似，只是多了一个限制条件，即在收到邻居发来的代理通告信息中，只有当该邻居与本节点有相同的网络前缀时，才可将该邻居作为上游邻居。节点的网络前缀不变，从而保证了网络前缀的连续性。

(3)F_DELAY：该算法与F_DISTANCE_STABILITY算法类似，增加了另外一个限制条件，即如果在收到当前邻居发来的代理通告信息中，序列号＝N，前缀＝P，则当第1次收到序列号＝N+1，前缀＝P的代理通告时，该邻居才可以作为上游邻居。该算法也可以保证网络前缀的连续性。

F_DISTANCE算法可以确定到外地代理的最短路径，但是如果移动节点在两个不同的外地代理覆盖范围之间来回移动时，可能会不断改变接入外地代理和地址前缀，注册信息在本节点与不同外地代理之间不停地传送，造成网络负载增加。例如在图1的场景1中，A1、A2、A3、A4、A5、A6收到关于FA_A的广播代理通告信息以后选择了FA_A作为本节点的接入外地代理。若A2收到了FA_B的广播代理通告信息，按照F_DISTANCE的算法， A2会选择FA_B作为新的接入外地代理。同时A3、A4、A5、A6也开始同样的过程。如果A2在两个外地代理之间不停地切换，就会在网络中造成大量信令交互的负载。

F_DISTANCE_STABILITY和F_DELAY算法可以避免在F_DISTANCE算法中出现的频繁切换的问题，但是又出现了其他的问题。比如在场景2中，尽管A6距离FA_B只有两跳的距离，而距离当前接入外地代理FA_A有5跳的距离。但是由于A6一直都可以收到FA_A的广播代理通告，因此A6不能切换到FB_B。这就造成了路由长度增加，时延增大，导致服务质量下降。

另外在节点移动速度较快的移动Ad Hoc网络中，网络拓扑结构的动态变化也会对服务质量产生重要的影响，比如 ——120

(b)

图1 外地代理选择算法图示

针对上述情况，对Jelger算法进行了改进，在选择外地

代理时，综合考虑跳数和路由稳定度两种参数。为了描述方便，把移动节点最新收到的外地代理信息的相应代理称为更新外地代理。

Hop1：Ad Hoc节点距已经接入的外地代理的跳数； Hop2：Ad Hoc节点距更新外地代理的跳数；

路由稳定度(PET)定义为Ad Hoc节点距外地代理的最长路由生存时间，用公式表示为

PET=Min(LET1,LET2,LET3,…)

LET为链路稳定度，即每一跳的路由生存时间；

PET1：Ad Hoc节点到已接入的外地代理的路由稳定度； PET2：Ad Hoc节点到更新外地代理的路由稳定度。 改进算法如下所示：

Ad Hoc 节点收到外地代理通告信息 Begin

if(节点当前没有接入到任何外地代理) 设置更新外地代理为该节点的接入外地代理; Else {

if(已经接入的外地代理前缀＝更新外地代理前缀) {

if ((Hop1>Hop2)||((Hop1=Hop2)&&(PET1<PET2)) 设置到更新外地代理的上游节点为该节点新的上游节点; } Else {

if ((Hop1>=2*Hop2)||((2*Hop2>Hop1>Hop2)&&(PET1<PET2))) 设置更改外地代理为该节点的接入外地代理，并且设置到更新外地代理的上游节点为该节点新的上游节点;

} } End

当移动Ad Hoc节点收到外地代理广播的通告信息后，首先检查该节点的外地代理表项，如果不存在或者是当前的

表项已经过期，则将更新外地代理作为该节点的接入外地代理。否则，该节点将更新外地代理的前缀与当前接入的外地代理前缀进行比较。如果代理通告来自于同一个外地代理，即代理前缀相同，则移动节点选择到外地代理跳数少的路由。若到外地代理的跳数相同，则应该选择具有更高路由稳定度的路由，同时更新外地代理的上游节点。

如果代理通告来自不同的外地代理，则移动节点只有在以下两种情况时才会选择更新外地代理作为接入外地代理：(1)移动节点到当前接入的外地代理的跳数大于等于两倍的到更新外地代理的跳数；(2)移动节点到当前接入的外地代理的跳数大于到更新外地代理的跳数但小于2倍的距更新外地代理的跳数，并且移动节点到更新外地代理的路由稳定度高于节点到当前接入的外地代理的路由稳定度。

而在改进算法中，当跳数和路由稳定度满足一定的条件就可以进行切换，因而可以减少平均跳数，降低时延。 3.3 丢包率

由于目前移动Ad Hoc切换算法的研究还不成熟，F_DISTANCE算法造成的频繁切换是不可接受的。因此，本 文只比较了改进算法和F_DELAY算法的丢包率。根据图4 可以看出，改进算法要比F_DELAY算法具有更小并且更加稳定的丢包率。

V/(m·s-1)

3 仿真结果

笔者采用OPNET仿真软件对500m×1 000m范围内的50个随机移动的节点进行了仿真，在仿真场景中有3个外地代理，外地代理以10s的间隔广播代理通告，移动节点以时间

节间隔t(t服从参数为0.2的指数分布)向外地代理发送数据，

点的发射距离为120m。分别仿真了Jelger算法和改进算法在3m/s速度下的切换次数和平均跳数，同时还仿真了改进算法和F_DELAY算法在不同移动速度下的丢包率。 3.1 切换次数

从图2可以看出，改进算法可以比F_DELAY算法减少约50％的切换次数。F_DELAY算法只侧重选择具有最少跳数的路由，而没有考虑频繁切换可能造成的影响，改进算法通过提高切换标准达到了既限制切换次数又尽可能减少跳数的目的。

54

pk lost ratio

图4 改进算法和F_DELAY算法丢包率的比较

随着节点移动速度的增加，网络拓扑变化越来越快，路由稳定度越来越低，链路的中断频率不断变大，F_DELAY算法的丢包率也随之增大，特别是当节点移动速度超过20m/s时，丢包率急剧恶化。而改进算法由于采用了路由稳定度作为参数，选择路由稳定度较高的路由，因此即使节点移动速度比较快，仍然能保持相对稳定的丢包率。由于目前没有有效的切换算法，在仿真中没有设计切换过程，导致了在切换过程中数据包的丢失比较严重，如果采用有效的切换算法，两种算法的丢包率将会得到改善。

4 结束语

本文针对Jelger算法存在的不足，以跳数和路由稳定度为参数对Jelger算法进行了改进，通过仿真证实了改进算法可以减少切换次数和平均跳数，同时可以保证比Jelger算法更少并且更加稳定的丢包率。但是只考虑了跳数和路由稳定度两个方面，在后面的工作中还将综合考虑QoS、负载、计费等需求，进行更为详细的仿真比较，提出更好的外地代理选择算法。

参考文献

1 Jelger C, Noel T, Frey A. Gateway and Address Autoconfiguration for IPv6 Ad Hoc Networks[Z]. (2003-10). Internet-Draft,draftjelger- manet- gateway-autoconf-v6-01.txt. 2003-10.

2 Sethom K, Afifi H, Li F Y. Gateway Selection in Multi-homed Ad Hoc Networks[Z]. (2006-01). draft-sethom-adhoc-gateway-selection-01. txt.

3 Zhao J H, Yang X Z, Liu H W. Load-balancing Strategy of Multi-gateway for Ad Hoc Internet Connectivity[C]//Proc. of International Conference on Information Technology: Coding and Computing. 2005-04, 2: 592-596.

4 Perkins C, Belding-Royer E M. Ad Hoc On-demand Distance Vector (AODV) Routing[C]//Proc. of the 2nd IEEE Workshop on Mobile Computing Systems and Applications. 1999-02: 90-100.

5 Xi J, Bettstetter C. Wireless Multi-hop Internet Access: Gateway

3.02.52.01.51.00.50.0

0 1 2 3 4 5 6

V/(m·s-1)

切换次数

3210

切换次数

0 1 2 3 4 5 6 7

-1

V/(m·s)

(a)F_DELAY算法 (b)改进算法

图2 F_DELAY算法改进算法的切换次数

3.2 平均跳数

从图3看出，改进算法可以比F_DISTANCE算法减少约30％的跳数，由于F_DISTANCE算法的主要思想是保持网络前缀的一致性，即使移动节点到更新外地代理的跳数远远小于到已经接入的外地代理的跳数，仍然不会改变接入的外地代理。

3.02.52.0跳数

1.51.00.50.0

0 1 2 3 4 5 6

V/(m·s)

-1

2.001.751.501.251.000.750.500.200.00

跳数

0 1 2 3 4 5 6 7

V/(m·s-1)

(a)F_DELAY算法 (b)改进算法

Discovery, Routing, and Addressing[C]//Proc. of Int’l. Conf. on the 3rd Generation Wireless and Beyond, San Francisco, CA, USA. 2002-05.

图3 F_DISTANCE算法和改进算法的平均跳数

—121—