基于伙伴系统的IP 地址自动分配协议的研究

摘要：Ad Hoc网络IP地址自动分配是Ad Hoc网络能够正常运行的必要条件。论文对基于伙伴系统的分布式动态地址分配协议进行了优化与扩展，新加入节点首先要发出邻居可用地址池空间大小的探测消息，便于选取拥有最大可用地址池的邻居并向其发送可用地址池请求消息，减少了已存在节点可用地址池枯竭的可能，最大可能的实现网络中每个节点的可用地址池中ip地址数目的均衡，减少了已存在节点递归查找可用地址池的频率。实验结果表明，改进后的协议具有良好的性能。

关键词：Ad Hoc网络； IP地址自动分配； 伙伴系统； NS-2

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）34-7704-04

Ad Hoc网络是由一组可移动的无线节点自发组成的网络。网络在没有常规基础设施和中心管理系统的支持下进行通信，其网络的拓扑结构可能因为不可预知的节点移动和传输特性而随机改变。它是一种自组织性和抗毁性比较强的移动通信网络，它不会因为网络中某一个关键节点的瘫痪而造成整个自组织网络的瘫痪，当网络中担当某一任务的节点出现问题后，这个节点所承担的任务会迅速被其他节点所替代，有很强的冗余性，和自恢复性。

现阶段许多对移动Ad Hoc网络的研究大都建立在节点的IP地址已经手工分配好的基础之上，在实际应用中由于Ad Hoc网络内节点自身的特点不能做到对网络中移动的节点适时的做到手动IP地址的分配与回收，因此对基于Ad Hoc网络IP地址自动分配协议的研究意义重大。

目前国内外已经存在的几种经典的Ad Hoc网络IP地址自动配置协议：（1）、 用于Ad Hoc网络的改进的DHCP协议，此协议为每部分网络选择一个“领导”，领导扮演相当于DHCP服务器的角色，通过它向新的节点分配地址。领导拥有一个所有已被分配的IP地址的列表，新的节点要获得IP地址必须向它申请；（2）、基于硬件地址的IP地址分配，在基于硬件地址的IP地址分配协议中，采用基于硬件MAC地址的已知网络前缀和后缀（a well-known network prefix and a suffix）来组成响应的IP地址；（3）、预知地址分配法，预知地址分配法是选择一个函数f（n），并且由此函数产生的一系列的随机数作为节点的地址；（4）、MANETconf协议，该协议中每个节点通过维护一个全网所有已使用的地址表来保证新加入的节点不会发生冲突；基于伙伴系统的分布式动态地址分配协议；（5）、PMWRS解决方法，主机先在169.254/16 IP地址池中选择一个地址，再向网络的其他节点广播地址请求报文（AREQ报文）。如果在计时器超时后，没有收到其他节点的地址回复报文（AREP），该主机重新发送AREQ报文。如果在有限次尝试后，任然没有收到其他节点的回复报文，该主机就认为它所选的地址是合法的，并为自己配置该地址。

在以上几种协议中基于伙伴系统的IP地址自动分配协议在大规模的Ad Hoc网络中相对其它技术有较好的性能，更适合于目前Ad Hoc网络的发展趋势。当新加入的节点在向已存在节点申请IP地址池时只考虑到自身能否分配到地址池，并没考虑到每个节点IP地址池的均衡，从而导致已存在节点IP地址池的枯竭，而递归地再去申请地址池，增加了网络的开销，文章针对这个不足做了改进。

1 AdHoc网络IP地址自动配置协议的算法的设计

1.1 基于伙伴系统的IP地址自动分配协议算法

该协议是通过地址池的分配来为节点分配IP地址的。最初整个网络只有一个节点，它拥有整个IP地址池。当一个没有IP地址的节点A想要加入网络，它向邻近节点申请IP地址。邻近节点B接受申请后，将自己的IP地址池的一半地址分配给节点A，节点A可将收到的IP地址池中的第一个地址作为自己的IP地址。同时节点B还将发给节点A最新的IP地址表，此时节点A和B互称为伙伴。如果一个节点（以下称为服务节点）接受了另一个节点（以下称为客户节点或请求节点）的IP地址申请，但是服务节点已经分配完了自己的IP地址池，服务节点可以搜索IP地址表并向拥有最大IP地址池的节点申请IP地址，拥有最大IP地址池的节点分一半的IP地址给服务节点，服务节点就可以配置客户节点了。

1.2 改进的基于伙伴系统的IP地址自动分配协议算法

1.2.1 节点加入

当一个新节点加入到网络后首先发送hello包（邻居消息请求包，请求邻居的IP地址和可用地址池），给周围相邻为一跳的邻居，同时启动邻居请求应答计时器和邻居请求计数器（初值为0）。在邻居请求应答计时器到期前，如果收到邻居的应答，便将邻居的IP地址写进自己的邻居表中，同时清除邻居请求应答计时器和邻居请求计数器；如果在邻居请求应答计时器到时仍没收到邻居应答则清除邻居请求应答计时器，重新发送邻居请求，重启邻居请求应答计时器，并将邻居请求计数器加一，当邻居请求计数器到达规定值后，就不再发送邻居消息请求包，此时该节点就认为他是该网络的第一个节点，随机选择一个ip地址池做为目前这个网络的可用地址池，并从该地址池中选择一个IP地址作为该节点的IP地址；

当新加入的节点收到邻居的IP地址并形成邻居表后，说明邻居关系已经建立，便会向邻居表中的每一位邻居发送可用地址池大小探测消息，并启动可用地址池大小探测消息计时器。 邻居在收到请求节点发送过来的可用地址池大小探测消息后便将自己的可用地址池的空间大小发送给请求节点，请求节点在可用地址池大小探测消息计时器到期之前将收到的邻居的可用地址池空间写入邻居的可用地址池空间表中，可用地址池大小探测消息计时器超时后将不再接收邻居的可用地址池空间大小消息。 请求节点比较邻居的可用地址池的空间的大小，从中选择一个地址池空间大的邻居并向其发送可用地址池请求消息，邻居收到可用地址请求消息后便查看自己的可用地址池，向请求者发送可用地址池应答消息，将自己的可用地址池的一半分配给请求节点，请求节点获得可用的地址池后从中选择一个最大的IP地址作为自己的IP地址，并保存获得的可用地址池。请求节点确定IP地址后，便向自己邻居表中的邻居发送自己的邻居表和可用地址池，便于强行离开时地址池的回收。

如果邻居收到请求节点的可用地址池大小探测消息后，发现自己的可用地址池空间大小为零，此时邻居节点便向他的邻居表中的邻居发送可用地址池大小探测消息，并同时启用可用地址池探测消息计时器，递归寻找可用地址池（视为和新加入的请求节点，寻找可用地址池的过程一样）；

以上主要思想见图1所示。

1.2.2 节点离开

当某一个节点协调离开（离开前发送离开通告消息）时需归还其IP地址。查找邻居表，发送地址池释放消息，将自身地址池归还给拥有最大IP地址的邻居，其他邻居收到消息后解除与该节点的邻居关系，并将该邻居节点拥有的邻居表删除；

节点需周期性的通告其邻居（一跳）其地址池，当节点强行离开时邻居竞争获得节点的地址池，拥有最大IP地址的节点（可通过保存邻居的邻居表获得强行离开节点的最大IP地址的邻居）获得地址池，为了防止拥有最大IP地址的邻居同时离开，必须设立应答机制，拥有最大IP地址的邻居回收强行离开节点的地址池后向强行离开节点的所有邻居发送地址池回收通知，让强行离开节点的其他所有邻居删除与强行离开节点的邻居关系和保存的强行离开节点的邻居表，当邻居节点通过hello包检测到邻居已经强行离开后，便启用邻居关系解除定时器，在定时器到时之前收到拥有最大IP地址邻居发来的地址池回收通知消息，则删除与强行离开节点的邻居关系和强行离开节点的邻居表，如果定时器超时还没有收到地址池回收通知消息，则定时器回复初始状态，由拥有第二大IP地址的邻居回收强行离开节点的地址池并向强行离开节点的所有邻居发送地址池回收通知，以此进行，知道强行离开节点的所有邻居收到地址池回收通知消息。

1.2.3网络的分割与合并

每一个自组网都有一个网络ID， 当一个节点通过与邻居间交换Hello报文获得邻居的信息后，发现邻居的网络ID与自己所在的网络ID号不同，说明两个自组织网络进行了合并，为了避免进行合并的网络发生IP地址冲突，此时收到不同网络ID的节点检查邻居的IP网段地址，如果和自己网络的ip地址处在不同的网段，则不多做处理，如果两个网络使用相同的IP地址网段，节点将自己的网络ID与处在不通网络的邻居的网络ID作比较选取网络ID较大的那个作为主动方，较小的一方为被动方，主动方向被动方发送IP地址网络号更改消息（改为与主动方不同的网段），被动方接收到IP地址网络号更改消息后便向自己网络内的所有节点发送IP地址前缀更改消息，为了使不同网络的IP地址前缀修改达到同步，主动方也向网络内的所有节点发送不同网络的地址前缀更改消息，使该网内的所有节点收到不通网络ID号时，让对方更改相同的IP地址前缀。

2 仿真数据分析

本次仿真使用的网络仿真工具为NS-2，版本为2.32。使用脚本语言gawk得到仿真预期要得到的数据后，使用绘制曲线图像工具gunplot将这些数据绘制成后缀为png格式的图片。该文中IP地址自动配置协议仿真环境如下：节点数量为100个节点，节点出现频率为0.003s/个、0.005s/个和0.01s/个，场景大小为1000m*1000m，路由协议使用DSDV，设定IP地址池空间为节点数量的2倍和10倍，得到图2和图3分别为协议改进前和改进后的仿真结果，通过数据的对比可以看出，在IP地址池空间较大的情况下协议改进前后对IP地址自动配置所需时间没有影响，但是在IP地址池空间较小的情况下改进后的协议对IP地址自动配置所需的时间明显少于原来的协议；图4表明在IP地址池为节点数量的2倍的前提下，节点出现频率在一定的范围内，随着节点出现频率的增加，一定时间内配置IP地址的节点数的速度增加；高于这个频率范围，随着时间的增加，一定时间内配置IP地址的节点数的速度逐渐减少。

3 结论

由于Ad Hoc网络中的节点不像有线网络中的节点有一定的固定位置，网络中节点的自由加入和离开，以及节点在网络中的自由移动，这导致了无法对网络中的每个节点进行手工的配置静态IP地址，因而必须采取动态自动分配IP地址的方法。由于它没有常规的基础设施和可集中管理的中心管理系统，这就决定了在Ad Hoc网络中对每个节点IP地址的分配不同通过和有线网络相同的方法通过一个服务器进行集中的地址分配，而应采取分布式的地址分配方法。而现在每个Ad Hoc网络都有自身的特点，比如所采用的无线自组织网络协议，每个网络对节点自身所带能源的使用时间长短的要求，这就需要每个自组织网络都要有与之对应的IP地址自动分配方式，现在的无线自组网中没有形成一个统一的IP地址自动分配协议，所以如何设计一个稳定性强，占用系统开销小的IP地址自动分配协议将是我们努力的方向，该文的研究为此做出了有益的探索。

参考文献：

[1] 孟昊，钟章队，艾渤.AdHoc网络路由协议研究及其性能比较[J].信息与电子工程，2009，4.

[2] 公维宾，常义林，沈中.AdHoc网络中改善拓扑控制性能的移动控制算法[J].软件学报，2011，22（10）：2335-2345.

[3] 曾任杰，于敬东.AdHoc网中IP地址分配技术综述[J].通信技术，2007，40（12）.

[4] 戴立渊.AdHoc无线网络路由协议的设计与实现[D]. 成都：电子科技大学，2012.

[5] 李环宇，李茹，史晶，任春雷.基于NS_2的MANET中IP地址自动配置协议的实现[J].内蒙古大学学报（自然科学版），2009，5.

[6] 沈奔，秦军，万丽.无线AdHoc网络中AODV路由算法的研究与改进[J].计算机技术与发展，2011，3.

[7] 单思宇.无线自组网中的路由协议[J].电脑知识与技术，2009，8.

[8] 陈爱国，张曦煌.移动自组网的IP地址自动配置技术研究[J].计算机工程与应用，2007.43（35）：146-149.

[9] 李环宇.异构AdHoc网络中IP地址自动配置协议的设计与实现[J].计算机应用技术，2009，5（5）.

[10] 蔡炎宏，马征新.移动自组网IP地址分配技术综述[J].宽带网络，2010（2）.

[11] 陈哲愚.基于NS_2的移动Adhoc网络路由协议性能分析[J].西安邮电学院学报，2009，8.

[12] Mohsin M， Prakash R. IP Address Assignment In A Mobile Ad Hoc Network[C].MILCOM 2002. Proceedings Volume 2，7-10 Oct.2002，2：856-861.

[13] Toner S，Mahony D. Self-Organising Node Address Management in Ad-hoc Networks[D].Networks & Telecomminications Research Grop（NTRG） Trinity College，Dublin 2，Ireland，2003.

[14] Mangues B J，Martinez P G，Chelius G，Evaluation of router address autoconfiguration time during network initialization for centralized and distributed schemes[C].Global Telecommuni-cations Conference，2005，GLOBECOM’05. IEEE Volume 2，28 Nov.-2 Dec.2005，5.

[15] Zhou H，Ni L，Mutka M.Prophet Address Allocation for Large Scale MANETs[C].INFOCOM 2003 .Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE Volume 2，30 March-3 April 2003，2：1304-1311.

[16] Nesargi S，Prakash R.MANETconf：Configuration of Hosts in a Mobile Ad Hoc Network[C]. INFOCOM 2002.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE Volume 2，23-27 June 2002，2：1059-1068.

[17] Perkins C E，Malinen J T，Wikikawa R，et al.IP Address Autoconfiguration for Ad Hoc Networks[DB/OL].IETF Internetr Draft， draft-ietf-manet-autoconf-01.txt， Work-inprogress， November 2001.