一种自修剪式的树型结构网络地址分配方法

摘要

本发明涉及一种自修剪式的树型结构网络地址分配方法。本发明方法中如果被申请路由器节点有空闲的网络地址分配给新节点，那么新节点得到网络地址，成功加入网络；如果没有空闲地址可以提供给新节点，则该路由器节点作为源路由器向网络中的其他路由器借用网络地址。具体借用网络地址步骤是：选取借用目标网络地址、组织借用数据包、发送借用数据包、接收借用数据包、组织出借地址应答数据包、返回借用应答数据包、接收借用应答数据包和分配借用地址。本发明方法使用较小的通信代价，使网络地址得到了充分的利用，利用闲置的网络地址，分配给网络地址需求更多的区域，增加网络的实际节点容纳量。

主权项

1、一种自修剪式的树型结构网络地址分配方法，当一个新的节点准备加入网络时，新节点探测周围环境中的路由器节点，并选择其中一个路由器，向该路由器发送加入网络申请；如果该路由器节点有空闲的网络地址分配给新节点，则选择一个地址分配给新节点，并将路由信息加入到路由表中，那么新节点得到网络地址，成功加入网络；如果该路由器节点已经没有空闲地址可以提供给新节点，则该路由器节点作为源路由器向网络中的其他路由器借用网络地址；其特征在于借用网络地址的具体方法是：(1)选取借用目标网络地址源路由器根据计算目标地址算法生成借用目标地址，具有借用目标网络地址的路由器节点为目标路由器，计算目标地址算法为：其中Addr表示计算得到的目标地址，Lm表示树型结构网络最大深度，rand表示生成随机数，Cskip计算公式如下：其中Cm表示最大子节点个数，Rm表示最大子路由器节点个数，d为路由器节点当前深度；(2)组织借用数据包源路由器计算得到借用目标地址后，源路由器组织借用数据包，借用数据包为一个包含借用序号、借用目标地址、新节点设备类型的三元组，其中借用序号为由源路由器生成每次自增1的值，该值初始化为0，当组织借用数据包时，将该值加1作为该次借用数据包的借用序号；借用目标地址为步骤(1)计算得到的地址；新节点设备类型根据步骤(1)中新节点的类型，取值为路由器类型或终端设备类型；(3)发送借用数据包当组织借用数据包完成之后，源路由器维护一个借用地址临时表，该表中每条记录表示一次网络地址借用记录，源路由器将步骤(2)生成的三元组信息插入到该临时表中，然后向目标路由器发出该借用数据包；(4)接收借用数据包当目标路由器接收到源路由器发出的借用请求数据包后，判断自身是否拥有空闲地址，如果存在未使用的空闲地址，则选择一个地址作为被借用地址；如果没有未使用的空闲地址存在，则目标路由器并不能出借地址给源路由器；(5)组织出借地址应答数据包出借地址应答数据包为一个包含出借序号，借用序号，被借用地址的三元组，其中出借序号为一个每次自增1的值，该值初始化为0，当组织出借应答数据包时，将该值加1作为该次出借数据包的出借序号；借用序号为步骤(4)中，目标路由器接收到的借用请求数据包中的借用序号，被借用目标地址为步骤(4)选择的被借用地址；被借用地址为步骤(4)选择的被借用地址，如果目标路由器没有未使用的空闲地址存在，则被借用地址选择一个不存在的网络地址X，用以表示没有空闲网络地址可以出借；(6)返回借用应答数据包目标路由器完成步骤(5)后，如果目标路由器有未使用的空闲地址出借，则维护一个出借地址表，该表中每条记录表示一次网络地址出借记录，目标路由器将步骤(5)生成的借用应答数据包插入出借地址表中；如果目标路由器没有未使用的空闲地址，则不维护出借地址表；目标路由器再将步骤(5)生成的三元组返回给源路由器；(7)接收借用应答数据包源路由器在完成步骤(3)发出借用数据包申请后，进入等待接收借用应答数据包的过程；如果源路由器接收到借用应答数据包，该借用应答数据包中的被借用地址为不存在的网络地址X时，表示地址借用失败，源路由器根据借用序号，找到借用地址临时表中的相应记录，删除该记录，重新进入步骤(1)；该借用应答数据包中的被借用地址为存在的网络地址时，表示地址借用成功，进入步骤(8)；如果源路由器没有接收到借用应答数据包，则表示目标路由器并不存在，则地址借用失败，源路由器根据借用序号，找到借用地址临时表中的相应记录，删除该记录，然后重新进入步骤(1)；(8)分配借用地址源路由器维护一个借用地址表，表中每条记录表示一次网络地址借用成功的记录；表中维护一个包含借用目标路由器地址和被借用地址的二元组，其中目标路由器地址即借用目标地址，被借用地址即步骤(7)接收到的借用应答数据包中的被借用地址，将二元组插入借用地址表中；根据借用应答数据包中的借用序号，找到借用地址临时表中对应的记录，删除该记录，并且将被借用地址分配给新节点，新节点地址分配完成，节点加入网络成功。