PDF《讯技术》

文章编号:1001 - 893X( 2011)

01 -

0056 -

05 MANET 中IP 地址自动配置算法设计 卿利 ( 中国西南电子技术研究所,成都610036) 摘要 : 分析了具有全球连接的移动自组织网络中地址自动配置需要解决的地址唯一性、网络分裂与融合等关键问题,针对现有地址自动配置算法实现复杂、扩展性差、时延过长等不足,设计了一种自组织网络地址自动配置算法.

该 算法采用代理分配和自主分配相结合的方式,实现初始地址的快速分配,并在路由协议中引入虚拟地址概念,以维护本地地址的唯一性.算 法自动发现和选择默认出口网关,由网关分配全球唯一IP 地址.所 提出的方案具有开销小、实现简单、支持频繁的网络融合和分裂等优点,可适用于拓扑动态变化的自组织网络地址配置需要.关键词:移动自组织网络;

地址自动配置;

全球连接中图分类号:TP393 文献标识码:Adoi: 10.3969 / j. issn.1001 - 893x.2011.01.012 Design of an IP Address Auto - configuration Algorithm for MANET QING Li ( Southwest China Institute of Electronic Technology, Chengdu 610036, China) Abstract: In MANET( Mobile Ad Hoc Network)with global connectivity,an IP address auto - configuration scheme should be able to ensure address uniqueness and deal with problems caused by network merging and par titioning. In this paper a novel address auto - configuration algorithm that works with global connected MANET is designed. A node can be allocated a local address quickly based on an address agent or by oneself. The virtu al address is used to detect address duplication,which simplifies the DAD( Duplication Address Detection) mechanism. An outdoor gateway is chosen automatically to assign the global address. With the advantage of low overhead and simple operation even under the situation of frequent network partitioning and merging,it is appli cable to large - scale MANET. Key words: mobile Ad Hoc network( MANET) ;

address auto - configuration allocation;

global connectivity

1 引言 移动自组织网络(Mobile Ad Hoc Network, MANET) 包括全球连接MANET 和独立MANET 两种类型.全 球连接MANET 通过一个或多个网关与外部网络如Internet 相连接,独立MANET 则不与任何外部网络相连接[1-4] .IP 地址是MANET 重要的网络参数,地址自动配置作为MANET 的重要问题受到广泛关注[5-7] , IETF 已成立专门的自动配置工作组(AUTOCONFIG WG) . 在全球连接MANET 场景下,地址自动配置机制为MANET 节点分配本地IP 地址和全球唯一IP 地址,分别用以进行MANET 内部通信和MANET 节点与Internet 主机之间通信.地 址自动配置机制需要通过重复地址检测(Duplication Address Detection, ・

6 5 ・ 第51 卷第1期2011 年1月电讯技术Telecommunication Engineering Vol.51 No.1 Jan.

2011 收稿日期:2010 -

05 - 25;

修回日期:2010 -

11 -

23 DAD) 算法保证分配给节点的地址是唯一的,并在网络运行过程中检测和解决重复地址问题.MANET 节点移动性带来网络拓扑结构的动态变化,网络在运行过程中的分裂和融合现象将导致地址的泄漏和重复性问题,均为地址自动配置机制带来挑战.本文在全球连接的MANET 场景下,分析地址自动配置面临的主要问题,并设计一种简洁的解决方案.所 提出的算法具有通信开销小、简单快速、扩展性强的特点,支持频繁的网络融合和分裂,可适用于大型MANET 网络地址分配的需要.2问题分析考虑MANET 作为边沿网络由一个或多个网关连接到Internet 的场景.MANET 节点通过网关访问In ternet服务或与外部主机进行通信.网 关具有与MANET 节点相同的无线接口,并连接到基于IP 的有线网络,为MANET 节点和Internet 主机提供双向连接,如图1所示.MANET 与Internet 之间的连接并非总是可用,如汽车或地铁在停泊或进站后与Internet 连接,在离开停车场或地铁站时与Internet 断开.图1全球连接Ad hoc 网络示意图Fig.1 Scenario of MANET with global connectivity 对全球连接MANET, 节点需要配置本地地址和全球唯一地址两类地址.本 地地址用于在MANET 内部通信,全球唯一地址用于访问Internet 外部服务.MANET 中没有永久节点充当DHCP 服务器,要求地址自动配置算法能够保证所分配地址的唯一性,检测并解决地址冲突问题.MANET 的网络融合和分裂是地址自动配置算法需要考虑的重要问题[8] .由于移动性或电池失效等因素,一个或多个MANET 节点离开其它节点的通信范围时,即发生网络分裂;

分裂后的多个网络随后又可能融合成一个网络,如图2所示.地 址自动配置算法需要能够避免网络分裂后部分地址的不可用,即地址泄露,也要解决网络融合导致的地址冲突问题.图2网络融合Fig.2 Scenario of network merger MANET 可能存在与Internet 连接的多个网关,要求自动地址配置算法能够感知节点的可用网关,并选择一个作为默认出口点.默 认网关为节点分配全球唯一IP 地址,并将MANET 与Internet 主机之间的数据包正确路由到目的节点.当 节点与默认网关的连接失败时,要求自动配置算法能够重新选择默认网关,并建立节点与新默认网关之间的绑定关系.3IP 地址自动配置算法考虑IPv6 地址,将单播地址分成临时MANET 本地地址、永久MANET 本地地址和全球地址三类.在节点配置永久MANET 本地地址之前,使用临时MANET 本地地址进行地址配置控制消息或其它控制消息的单播传输,其前缀为 fec0: 0: 0: ffff: :/

96 , 用常量MANET- INIT- PREFIX 表示,地址中最低的32 位为伪随机数;

具有前缀为 fec0: 0: 0: ffff: :/

64 ( 表示为常量MANET- PREFIX) ,且不与MANET INITPREFIX 重叠的地址,作为永久MANET 本地地址[7] , 如图3所示.具 有全球地址前缀的地址为全球IP 地址.图3MANET 本地地址结构Fig.3 Local IP address of MANET 3.1 MANET 本地地址分配本地地址分配主要包括自主分配和代理分配两种方式.自 主分配方式即由节点自己随机选择主机・75・第1期卿利:MANET 中IP 地址自动配置算法设计总第266 期地址与前缀MANETPREFIX 合并得到试探性永久地址,经DAD 算法验证唯一性后作为正式永久地址分配给端口[8] ;

代理分配方式即节点选择一个邻居作为代理节点(Initiator) 负责地址分配,地址代理产生候选地址后,收到全网成员确认候选地址唯一性的应答消息后将该地址分配给节点[9] . 自主分配方式可能存在频繁的地址分配失败,特别是可用地址空间较小或网络规模较大,节点试探性地址选择到已使用地址的概率较大,使得节点地址分配频繁失败而带来时延的增加.特 别是同时有多个节点入网时,该方式的效率非常低.代 理分配方式的主要问题是在进行地址唯一性检验时,要求全网所有节点返回应答信息,将浪费过多的网络带宽,等待应答所带来的时延将非常长.为解决以上问题,采用自主分配和代理分配相结合的方式.节 点入网时,首先搜索当前网络成员,以确定地址代理.节 点随机产生临时地址作为永久地址分配前控制消息的源地址,广播入网请求消息(JOINT- REQ) ,启动入网应答定时器,并 侦听MANET 成员的广告消息(ADV- MESSAGE) .已入网的成员节点周期发送ADV- MESSAGE 消息,若收到JOINT- REQ 消息,表示有新节点入网,则事件触发ADV- MESSAGE 消息的传输.入网节点根据不同情况进行如下处理:(1) 若入网应答定时器超时,节点未收到ADV- MESSAGE 消息,重复该过程直到达到一定尝试次数门限,则节点自己作为代理节点,在预置可用地址范围内随机产生试探性永久地址;

(2) 若节点收到ADV- MESSAGE 消息,则选择最先收到消息的源节点作为代理节点,发送地址分配请求消息(ADD- REQ) .代理节点收到ADDREQ 消息,发送地址分配应答消息(ADD- REP) , 并本地保存网络已分配地址信息(如来自主动路由的全网拓扑表或被动路由获取的消息源地址记录),在未分配地址集合中选择试探性永久地址.地址代理节点为检验试探性永久地址的唯一性,执行重复地址检测(DAD) 算法如下:首先,以全节点组播地址作为IP 包头部目的地址,发送AREQ 消息,并等待应答消息.AREQ 消息的跳数设置为默认网络半径(或采用扩展环搜索算法[13]设置跳数).如 果尝试性永久地址已被MANET 的其它节点占用,则使用该地址的节点收到AREQ 消息发现地址冲突,立即产生一个AREP 消息,沿着AREQ 传输所建立的路径单播发送给地址代理;

其次,如果地址代理在一定时间内未收到任何AREP 消息,则认为该尝试性永久地址未在网络中使用,将作为永久IP 地址进行分配.分 配IP 地址时,若节点自己即为地址代理,直接配置给端口;

否则,地址代理发送地址分配消息(ADD- ALLOC) 给地址请求节点;

否则,如果地址代理接收到一个AREP 消息,表示尝试性永久地址已被使用,地址代理另选一个尝试性永久地址,并重复以上过程,直到成功获得唯一地址或尝试的次数超过一定预先设定的值而放弃地址配置.需要注意的是,可能多个节点同时加入网络,从而选择到相同的地址,使地址分配失败而重复该过程.为 了减小尝试地址冲突概率,在发送AREQ 消息时需在发送时间上引入一个随机增量,以避免多个节点同时发送AREQ 消息.3.2 维护地址唯一性在MANET 运行过程中,多种原因可能导致地址冲突.比 如,分配地址时,执行DAD 过程中未收到某节点发出的AREP 消息,或两个MANET 融合成一个网络时有两个节点同时使用了相同的地址,都会产生地址冲突.因 此,要求自动地址配置协议能够在网络生命周期内检测和解决地址冲突问题.由于节点移动性带来MANET 拓扑频繁变化,仅仅依靠数据包的路径信息无法分辨相同源地址的消息是否来自同一个节点.为 了维护地址唯一性,采用虚拟地址概念[10 - 11] .每个节点选择一个128 位的伪随机键值,与本地IP 地址构成的二元组(键值,IP 地址)称为虚拟地址.在 路由协议的所有控制消息头部增加一个键值域,每次发送路由控制消息时,将节点键值填入到控制消息中.为 保证网络中所有节点键值的唯一性,构造函数f(s) 以生成不重复的128 位值:f(s)= Random(s)| Time( ) ( 1) 式中,Random(s) 为种子为s的随机函数,生成一个96 位随机值;

Time( ) 函数产生32 ........