移动自组网IP地址分配技术综述*

蔡炎宏，马正新

（清华大学 微波与数字通信国家重点实验室，北京 100084）

1 引言

移动自组网（Mobile Ad Hoc Network， MANET）是由移动节点自发组成的多跳无线网络，它的节点自由移动，网络拓扑结构动态变化。与传统电信网和因特网不同，移动自组网是无中心的网络，没有基础设施。这使得传统网络很多成熟的技术不能直接应用于移动自组网。一直以来，对移动自组网网络层的研究主要集中在路由方面。几乎所有对路由的研究都假定网络节点事先已配置好地址，但这一点实际上是难以做到的。对于小规模的网络来说，手动静态配置也许是可行的；但是对于大规模网络，尤其是允许节点自由加入和离开的开放型、实用型网络，事先配置地址是不现实的。而节点只有在获得网络地址以后才能进行路由和通信。但传统网络的地址动态配置协议不能直接应用于移动自组网[1]，因此，地址动态分配是移动自组网实用化、商用化的一大挑战。

2 地址分配技术分类评析

移动自组网的地址分配算法大体可分为4类。

2.1 基于状态维护的算法

这类方法有一个共同的特点：节点维护网络中地址分配的状态信息，即已分配地址或未分配地址列表，并且通过周期性的同步更新地址分配状态。典型的算法有MANETconf[2]和 Buddy[3]。

1）MANETconf

在该算法中，网络中的每个节点都维护整个网络的已分配IP地址信息，并通过泛洪的方式周期性同步更新该信息。最初网络中只有1个节点，它从可分配地址空间中取1个地址作为自己的地址。随后加入网络的节点选择它的1个邻居节点作为配置地址的代理节点，代理节点随后选择1个未分配的地址（记为x），通过一种特定的消息泛洪整个网络，征询其他节点的意见，只有网络中其他节点都给出肯定的答复，代理节点才将地址x分配给请求节点并更新所有节点的已分配地址表。否则，它选取另外1个地址并重复上述过程。为了应对网络的合并与分裂，该算法规定由网络中地址最小者产生1个网络标识UUID，并泛洪整个网络。当网络边缘节点检测到不同UUID的消息时，便检测出了网络的合并，于是交换各自的已分配地址表并处理冲突地址。网络合并后，将由合并后网络的地址最小节点产生新的网络标识。

该算法通过全网泛洪更新地址状态信息，排除地址冲突，协议开销较大；同时，每当有新节点加入，需要等除代理节点外其他节点都给出肯定答复后，代理节点才将预选的地址分配给新加入节点，配置延时较大；此外，随着网络节点数增加，协议开销和配置延时显著增大，该算法的可扩展性也较差。

2）Buddy

该算法在网络中的每个节点都可以为新加入的节点配置地址。最初网络中只有一个节点（记为A），它拥有整个IP地址池。当有新节点（记为B）加入时，新节点通过特定的邻居发现消息选择A作为配置节点。A将拥有的IP地址池分一半给B，B从获得的地址池中取第1个地址作为自己的地址，同时B也拥有为其他新加入节点配置地址的能力。A，B互称为伙伴（Buddy）。后续加入网络的节点都选择它的1个邻居节点作为配置节点，通过类似的方式获得该邻居地址池的一半，并取地址池的第1个地址作为自己的地址。如果有节点无通告离开网络，那么将造成IP地址的泄漏。为了处理这个问题，该算法采取了以下措施：节点间周期性地交换各自的IP地址表，不断更新IP地址信息，以使每个节点都拥有最新的IP地址表（如表1所示）。如果某个节点发现它的伙伴节点不在最新的IP地址表中，则可认为该节点已经无通告离开网络，于是吸收它的地址池到自己的地址池中，以防止IP地址泄漏。

该算法需要通过泛洪方式周期性地更新IP地址表，协议开销较大。同时，也因为周期性泛洪的存在，协议开销随节点规模的增大而迅速增加，可扩展性较差。但因为新加入节点只需它的邻居节点同意即可获得配置，无须等待网络中其他节点的同意，只有两跳延时，所以配置延时较小。而文献[4]采取类似Buddy的方法，只是地址回收部分有所差别。

表1 IP地址表

2.2 基于冲突检测的算法

这类算法有一个共同的特点：新节点加入网络时，从整个IP地址池中随机选取一个IP地址作为自己的地址，并通过主动或被动发现冲突的方式来更改地址，直到不出现冲突为止。主动检测冲突的方法被称为DAD（Duplicate Address Detection），被动检测冲突的方法为PDAD（Passive Duplicate Address Detection）。 PMWRS[5]和PACMAN[6]是这类算法的典型代表。

1）PMWRS[5]

该算法是由Perkins，Malinen，Wakikawa，Royer 和Sun等人提出，因此称为PMWRS算法。新加入网络的节点（记为A）从169.254/16 IP地址池中随机选择一个地址x，并向其他节点广播包含x的地址请求消息（AREQ）。收到该消息的节点将x与自身地址对比，如果相同，则回复消息AREP；如果不同，则不做处理。如果在计时器超时后，A没有收到其他节点的回复消息AREP，则再次发送AREQ消息，如果在有限次尝试（事先预设）后仍未收到AREP消息，则认为所选地址x没有冲突，并配置该地址。否则，从地址池中重新选取一个地址，并重复上述过程。

该算法复杂度较低，容易实现，但存在如下缺陷：首先计时器周期的选择非常关键，太短的周期会导致检测不出较远节点的冲突地址，太长的周期会导致配置延时过长。为保险起见，周期的选取应该与节点的规模成正比，但这样会带来较大的延时。其次，如果2个新加入节点同时从地址池中抽取到同一地址，可能会引起地址冲突。此外，该方法因为通过泛洪的方式排除冲突问题，协议开销较大，可扩展性较差。

2）PACMAN

为了避免实行DAD所带来的大量协议开销，该算法采用了PDAD的方式。加入网络的节点按照一定的方法从地址空间中取1个地址作为自己的地址。该算法分析路由协议产生的数据包，通过只存在重复地址时才可能发生的事件发现地址冲突，并采取相应措施处理冲突。比如在典型的链路状态路由协议中，每个节点都周期性地产生链路状态消息，该消息包含源地址、序列号等。假定每个节点的序列号都是周期性增加的，当某个节点收到了某条链路状态消息，源地址与自己地址相同，但序列号却比自己当前序列号大，则可确定发生了地址冲突。

该算法的优点是在地址分配过程中不产生控制信息，而是通过发现重复地址所特有的路由事件来发现冲突地址并处理冲突，协议开销较小。但该算法要求可分配地址空间比网络节点数大得多，否则发生地址冲突的可能性就较大，处理冲突引入的协议开销也会较大。此外，该算法依赖具体的路由协议，甚至路由协议的参数，适应范围过于狭窄。

2.3 基于网络分层的算法

这类算法的共同点：在进行地址分配之前，对网络的所有节点进行分簇；分簇以后，在簇内通过DAD方法排除冲突地址或者选举簇头管理簇内地址分配。为排除冲突地址的信息交互被局限在簇内，从而减少了协议开销，增强了可扩展性。在这类算法中，地址分配的协议开销降低了，但因为移动自组网的拓扑结构是动态变化的，维护网络的分层结构本身就是一笔不小的开销，所以分簇的方法显得尤为重要。IPv6Stateless[7]和SOAMAN[8]是这类算法的典型代表。

1）IPv6Stateless

该算法先把整个网络进行分层，即把1组相距小于或等于rs跳的节点划分为1个群，选举邻居节点数最多的节点作为群首节点，孤立节点可自立为群首。群内所有节点共同构成1个子网，群首节点负责选择1个随机的子网ID，并且在所有群首节点中进行DAD检验以保证该子网ID的唯一性。在子网ID确定下来以后，群首向群内节点周期性地广播RA （Router Advertisements）消息，消息中包含子网ID。新加入节点先随机产生1个本地链路地址，并在群内进行DAD检测，如果没有检测到冲突，则将该本地链路地址和接收到的RA中的子网ID合成节点地址；否则重新选取地址，并重复上述过程。

该算法实行了分层的网络结构，将本地链路地址的DAD检测限制在群内，而子网ID的DAD检测限制在群首节点之间，降低了协议开销。但随着节点的移动，网络拓扑动态变化，维护分层结构本身也是一笔不小的开销，所以该算法不适合节点移动快、拓扑变化剧烈的网络。

2）SOAMAN

该算法从所有节点中选举1个群首节点管理整个网络地址的分配，领导节点维护整个网络的已分配地址表，新加入节点需向群首节点申请地址。当有新节点加入网络时，它首先随机产生1个临时地址，该地址只用于与邻居节点（主要是代理申请地址的节点）的通信，不参与路由。然后，选择1个邻居节点作为申请地址的代理，该邻居节点随后向群首节点申请1个未分配的IP地址，并将其作为新加入节点的地址。

该算法新节点在加入网络过程只需通过邻居代理向群首节点申请地址，而不需要泛洪整个网络，也不需要等待网络中其他节点的确认消息，降低了协议开销和配置延时。但是，整个网络只划分1个群，群首管理整个网络的地址分配，并且需要周期性广播信号以检测网络的分裂与合并，所以群首节点的负载较大，可能成为整个网络的瓶颈，可扩展性不强。

2.4 其他算法

这些算法没有统一的规律可循，它们通过某种特殊的方法或技巧为节点分配地址，可能带来某一方面性能的提高，但也可能引起其他方面的一些问题。这里重点介绍 Prophet[9]和 MACBased[10]。

1）Prophet

该算法通过一个特殊的函数f（n）来生成地址，要求该函数产生2个相同随机数的时间间隔足够长。网络中的第1个节点随机选择1个数作为自己的地址，第2个节点加入网络时，第1个节点以自己的地址作为生成函数f（n）的种子生成1个数，作为第2节点的地址，以此类推。

该算法在地址分配过程中不需要通过泛洪排除重复地址，也不需要等待其他节点的确认消息，协议开销较小，配置延时较小，可扩展性较好，但符合条件的f（n）不好找。其次，要求可分配的地址空间比实际使用的地址数大得多才行。再次，在节点频繁加入离开网络的情况下，还是可能产生重复地址的。

2）MACBased

该算法将IP地址和网卡的MAC地址对应起来，用MAC地址的已知网络前缀和后缀组成相应的IP地址。该算法认为在全球范围内所有网卡的MAC地址是唯一的，不会有重复地址。但是，网卡的MAC地址可以通过对E2PROM编程更改。其次，可能出现不同网卡使用同一MAC地址的情况，所以MAC地址的唯一性得不到保证。再次，将IP地址与硬件地址对应起来，知道了IP地址就知道了相应的主机，个人隐私得不到保护。

3 性能比较

对于移动自组网的地址分配技术，一般从是否存在重复地址、协议开销、配置延时、可扩展性、是否支持网络分裂与合并这几个方面来评价它们的性能。表2给出了4类地址分配技术典型算法的比较。

表2 典型地址分配算法的性能对比

4 小结

移动自组网的网络拓扑结构动态变化，在这样的环境下，地址动态分配是一项具有挑战性的工作。目前，不存在一般条件下各方面性能都较好的地址分配算法。应考虑具体的应用条件，选择合适的算法。

影响移动自组网地址动态分配算法性能的主要因素是网络拓扑的动态变化。如何感知和预测拓扑的变化以消除拓扑变化引起的各种问题，将成为未来改进算法性能的主要方向。

[1]NetworkWorkingGroup-RFC2131，Dynamichost configuration protocol[S].1997.

[2]NESARGI S，PRAKASH R.MANETconf:configuration of hosts in a mobile Ad Hoc network[C]//Proc.IEEE INFOCOM.New York，USA：[s.n.]，2002：1059-1068.

[3]MOSHIN M，PRAKASH R.IP address assignment in a mobile Ad Hoc network[C]//Proc.Military Communications Conference（MILCOM 2002）.California， USA：[s.n]，2002： 856-861.

[4]PRAKASH A，PATNAIK L M.An address assignment for the automatic configuration of mobile Ad Hoc networks[J].Personal and Ubiquitous Computing，2004，8（1）：47-54.

[5]PERKINS C E，MALINEN J T，WIKIKAWA R.IP address autocon figuration for Ad Hoc networks[S].2001.

[6]WENIGER K.PACMAN:passive autoconfiguration for mobile Ad Hoc networks[J].IEEE Journal on Selected Areas in Communications（JSAC），2005，23（3）：507-519.

[7]WENIGER K，ZITTERBART M.IPv6 autoconfiguration in large scale mobile Ad Hoc networks[C]//Proc.European Wireless 2002.Florence，Italy：[s.n.]，2002：142-148.

[8]TONER S，MAHONY D.Self-organising node address management in Ad-hoc networks[C]//Proc.No.8 IFIP-TC6 International Conference.Venice，Italy：[s.n.]，2003：476-483.

[9]ZHOU Hongbo，NI L M，MUTKA M W.Prophet address allocation for large scale MANETs[C]//Proc.IEEE Conference on Computer Communications（INFOCOM）.San Francisco，CA：[s.n.]，2003：423-434.

[10]IETF RFC 2462，IPv6 stateless address autoconfiguration[S].1998.