复杂网络设备IP地址分配方案研究

时间：2024-05-04

汪钰斌

(江西农业大学南昌商学院，江西共青城 332020)

1 引言

复杂网络是指呈现高度复杂性的网络，复杂网络具有六大特征；节点数目巨大、网络结构不断发生变化、节点之间的连接权重存在差异、节点集属于非线性动力学系统、复杂网络中的节点可以代表任何事物、多重复杂性融合，安装复杂网络设备非常必要。复杂网络的不断发展，复杂网络设备也应运而生，并且逐渐被各领域所接受，例如空气污染监控方面。IP地址是用来标识节点，使能网络通信协议，在复杂网络中扮演着重要角色，但是由于网络中设备数量较大以及网络动态性，如果手动地为复杂网络设备进行IP地址分配是一件非常繁琐工作甚至是不可能实现的。迫切需要研究一种IP地址分配方案。周林等人[1]提出了一种基于动态参数的按需可扩展地址分配算法，根据分布式地址分配机制(DAAM)对16 bit地址空间进行分块，根据网络状况来动态调整参数以及进行地址一次或者多次扩展；同时改进路由算法，使其与Cluster-Tree协议兼容，该方法分配效率较高，但是可操作性较差；袁利永等人[2]提出了一种两段地址分配策略TFA，它将16位地址分成两段，前段地址用于全功能设备的地址分配，后段地址用于精简功能设备的地址分配。分析了TFA的mesh路由优化特性，提出了基于TFA的mesh路由算法，该方法地址分配成功率较高，但耗时较长。李鸿健等人[3]提出了一种基于地址映射的分段式地址分配算法，通过对子节点路由节点以及终端节点的地址进行扩展，建立了从子节点地址到扩展地址的映射，增加了路由节点所能拥有的子节点的最大个数，从而提高了节点的入网概率和孤立节点数量；同时给出了地址回收机制以及改进的路由算法，使其与cluster-tree协议兼容，该方法平均分配耗时较短，但是分配准确率较低。

针对上述问题，提出一种基于改进DAAM的IP地址动态分配方案。

2 复杂网络设备数学模型

复杂网络设备的网络数学模型表达式如下

G=(V，E)

(1)

式中，E代表复杂网络设备zigBee网络中所有对称无线通信链路的集合；V代表复杂网络设备zigBee网络中所有设备的集合，表达式如下

V={t}∪Vr∪Ve

(2)

其中，t代表复杂网络设备zigBee网络协调器；Vr代表zigBee网络所有路由设备的集合；Ve代表复杂网络设备zigBee网络所有终端设备的集合[4]。

在上述模型的基础上，为了便于研究复杂网络设备IP地址分配方案，做了以下定义：

定义1：复杂网络设备IP地址空间，是指具有一定位数的IP地址集合。

定义2：复杂网络设备IP地址分段，是指将一个IP地址空间划分为若干个容量更小的IP地址空间。

研究发现，传统的分布式地址分配方案(DAAM)定义的IP地址空间上限很少达到65535(216-1)，这意味着绝大多数情况下复杂网络设备zigBee网络中有剩余IP地址空间可供利用。对传统方法用16bit IP地址空间的概率进行推导。

根据传统方法的基本原理[5]，假设SDAAM代表复杂网络设备的IP地址空间；Am代表监控设备分配的最大IP地址，则有

SDAAM={1，Am}

(3)

Am=Cskip(0)×Rm+Cm-Rm

(4)

式中，Cskip(0)表示复杂网络设备之间的IP地址间隔；Rm表示复杂网络中每个父节点拥有的子节点中路由器的最大数目；Cm表示复杂网络中每个父节点拥有的子节点最大数目。

1)当Rm=1时，有：

Am=Cm×(Lm-1))×Rm+Cm-Rm=CmLm

(5)

其中，Lm表示复杂网络最大深度。

欲使Am=65535，须使CmRm=65535，通过因式分解可知65535是四个素数的乘积[6]，表达式如下

65535=3×5×17×257

(6)

根据上式可知，满足条件的RmLm组合个数为

(7)

2)当Rm>1时，有

(8)

(9)

根据已知条件，Rm>1、Cm≥Rm和Lm≥1进行遍历搜索，得到满足上式条件的CmRmLm组合个数为3，即(4369，2，4)、(13107，4，2)、(21845，2，2)。

综上分析和计算可知，DAAM方案用完复杂网络设备网络16bitIP地址空间的方式有16+3=19种；由于Lm∈{1，65535}，Cm∈{1，65535}，则设备总的IP地址分配方案数量大于655352，则DAAM方案用完监控设备网络IP地址空间的概率为

P<19/655352(≈4.42×10-9)

(10)

根据上述式(10)，近似地P≈0。

3 复杂网络设备IP地址分配方案

复杂网络设备ZigBee标准默认的IP地址分配机制为DAAM，具体组网步骤如下：

1)假设复杂网络协调器设备IP地址为0；确定组网参数：Cm、Rm和Lm，采用泛洪的方式通知整个监控网络。

2)复杂网络设备通过对网络邻居表的查询，找出未被标记的深度最小的潜在父节点(有多个时随机选取)向其发送申请加入监控网络的信息，如果没有收到答复，则可以周期性地发送入网申请信息。

3)复杂网络中IP地址为Aparene的网内路由设备收到未入网的设备的入网请求后，作为父节点，根据申请设备类型以及申请入网的先后顺序按照以下公式为申请入网的监控设备分配IP地址

(11)

式中，d代表复杂网络父节点的深度，等于父节点与网络协调器之间的跳数Hp，d≤Lm-1；n代表子设备申请入网的顺序，1≤n≤Rm；Cskip(d)代表复杂网络中深度为d的路由设备在分配IP地址时的地址偏移量，计算表达式如下

(12)

4)当监控网络中的潜在父节点收到设备入网申请后，没有剩余的IP地址可以分配[7]，则回复拒绝加入的信息，对拒绝加入的潜在父节点进行标记，然后跳转回步骤(2)重新进行下一轮的入网申请。

4 复杂网络设备IP地址分配优化

传统的DAAM方案是定制式的，即每一级都严格按照三个组网参数Cm、Rm和Lm的值对设备IP地址进行分配，对于处理复杂网络动态网络中设备IP地址的分配无能为力，只适用于静态网络。根据第1节分析可知，由于传统的DAAM方案无法动态地平衡复杂网络树，所有的剩余IP地址(即网络协调器未分配的IP地址)一直都未使用，造成了IP地址资源的浪费[8]。

已知复杂网络的动态性有三个方面的体现，分别与参数Cm、Rm和Lm相对应，即：

①复杂网络局部范围内的路由设备接收的子路由设备已经饱和，数量达到Rm，但是在该范围内还有需要接入网络的子路由监控设备；

②复杂网络局部范围内的路由设备接收的子终端设备已经饱和，数量达到了Cm-Rm，但是在该范围内仍然有未入网的子终端监控设备；

③某个复杂网络深度为Lm的设备，还需要接收子设备入网，即监控网络中需要有深度更深的设备来扩大整体网络的监控覆盖范围[9]。

上述三种情况在传统的DAAM方案中均会以失败告终，研究提出一种IP地址动态分配方案，能够有效解决上述存在的问题。

复杂网络设备IP地址动态分配方案采用以下式(13)计算地址偏移量

(13)

式中，⎣x」代表不大于x的最大整数；Rm(d)和Tm(d)分别表示监控网络中深度为d的路由设备所能接收的最大子路由设备数量和最大子终端设备数量。

根据上述公式可知，相对于传统方法，所提方法移除了参数Lm，以实现复杂网络深度的动态拓展。

在上述式(13)中除监控网络协调器外每层的地址偏移量以上一层的地址偏移量为基础进行计算，网络协调器深度为d=0，监控网络中所有设备的深度为d≥1。复杂网络短IP地址的范围是0～0×FFFF，共65535个，其中有3个保留的特殊IP地址0×0000、0×FFFF、0×FFFF，分别代表监控网络协调器IP地址、设备使用64位长IP地址通信；无效的短IP地址，是监控设备没有入网的标志。因此，可用于复杂网络设备正常分配的IP地址有65533个，从中预留Tm(d)个IP地址给网络终端设备，其余的分给Rm(d)个路由设备。如果65533-Tm(d)不能被Rm(d)整除，则利用余数来处理监控网络终端设备的入网，其余各层的处理方式与网络协调器同理。复杂网络不同深度的设备IP地址余数计算公式如下

(14)

在传统的DAAM方案中，处于复杂网络边缘的新增设备，通常无法动态入网，这是由于边缘设备往往已经达到最大深度，而监控网络最大深度值一般设置较小(默认设置为5)。而所提方法中，移除了参数Lm来计算地址偏移量，解除了监控网络深度拓展的束缚，并且可以通过调整组网参数改变监控网络深度，具有深度动态可拓展性。

在上述计算的基础上，引入借地址的策略，即动态IP地址均衡的基本原理，通过定义以下四种命令控制帧解决复杂网络IP地址动态入网的问题。①强制入网申请命令；②强制入网应答命令；③借址申请命令；④借址应答命令。

5 实验分析

实验中将基于动态参数的分配方法(文献[1]方法)、基于地址映射的分配方法(文献[3]方法)与所提方法进行对比实验，通过实验测试对比复杂网络设备两种不同IP地址分配方案的分配效果、监控网络稳定性和运算效率等方面的性能差异性。

采用Windows7平台上的OPNET模拟软件对两种IP地址分配方案进行模拟。复杂网络覆盖面积为1000m×1000m，监控网络中路由设备的数量分别为1000，2000，3000，5000，8000个，设备密度范围为350～20m2/个，设备在实验区域内随机分布，网络协调局位于实验区域的中心位置，各个设备之间的通信距离为50m。监控网络组网初始化参数为：Cm=8，Rm=8，每个实验进行20次，取平均值。实验结果如图1所示。

图1 不同方法的监控设备IP地址分配结果

图1(a)为圆点表示需要进行复杂网络的布控点，三角形表示进行基于动态参数的分配方法监控设备IP地址分配结果，很多布控的点并没有与黑色三角形点重合，说明部分监控设备甚至没有分配到IP地址。图1(b)中的黑色小正方形表示基于地址映射的分配方法的监控设备IP地址分配结果，从图中可以看出，采用传统方法进行监控设备IP地址分配，存在重叠现象，即对同一空气污染监控设备分配了两个或两个以上IP地址，有的监控设备甚至没有分配到IP地址。图1(c)中的菱形小黑点表示采用所提方法进行监控设备IP地址分配结果，所提方法菱形小黑点与需要布控的点完全重合，说明采用所提方法实现了复杂网络设备的IP地址分配，这是由于所提方法有效地利用了监控网络的剩余IP地址空间，不受组网参数Lm的限制，使得更多的设备能够及时加入监控网络中，同时采用的借地址策略使得监控设备分配到的IP地址更加均衡。

为了验证所提方法的分配效率，以控制报文数量为测量指标，同样的监控设备，所需的控制报文数量越小，说明IP地址分配效率越高。实验结果如图2所示。

图2 不同方法的控制报文开销

图2展示了传统方法的控制报文在各类复杂网络中均小于所提方法，同时实验结果验证了随着监控网络中设备数量的增加，所提方法的优势显著高于对比方案，这是由于采用传统方法进行监控设备IP地址分配时，当监控规模变大时，监控网络中无法分配到IP地址的设备数量迅速增加，造成了多次的设备IP地址入网申请，出现了控制报文开销较大的问题，而所提方法受到的影响却很小。

为了进一步验证所提方法的设备IP地址分配平均耗时，进行如下实验，实验结果如图3所示。

图3 不同方案的设备IP地址分配平均耗时

如图3所示传统方法对复杂网络设备进行IP地址分配的平均耗时整体上小于所提方法，这是由于传统方法中对于空气污染监控网络中无IP地址的设备会多次向邻居设备申请IP地址，增加了IP地址分配延时，当监控网络中的设备规模较小时，两种方案的平均耗时没有太大差别，而当监控网络的规模变大时，所提方法显示出优越性。