基于逻辑区域的Zig Bee网络地址分配算法*

， ，

(西南科技大学 计算机科学与技术学院，四川 绵阳 621000)

0 引 言

Zig Bee协议[1]有2种地址分配机制：随机地址分配机制和分布式地址分配机制(distributed address assignment mechanism，DAAM)。随机地址分配机制是由父节点为子节点随机的分配网络地址；DAAM分配的地址呈规律性，包含了“地址—位置”的对应关系，通过对地址的计算能获得路由信息。DAAM实现简单，目前得到了广泛的研究和应用，但由于DAAM地址分配机制组网阶段就设定了网络参数Cm，Rm,Lm，造成了网络中地址的严重浪费，使得一些节点无法加入网络，形成了孤立节点[2,3]。

针对这些问题，目前已经有一些研究，如文献[4]针对网络中存在大量频繁移动节点的问题提出了相应的地址分配算法，但并没有充分解决出现孤立节点的问题。文献[5]分析了孤立节点形成的2种情况，提出了相应的改进算法，缓解了孤立节点问题。文献[6]提出了一种基于分段的按需可扩展地址分配算法，对路由节点的子节点地址空间进行分段式按需扩展，为更多节点分配地址的同时保持了节点间的“地址—位置”关系。但仍基于DAAM地址分配机制，不适用于节点位置变化频繁的网络。文献[7]和文献[8]提出了借地址的思路，子地址空间不足的路由节点向有剩余地址的路由节点借地址进行分配，这种方法的主要问题是会产生额外通信开销和部分节点无法使用树路由。

本文提出了一种基于逻辑区域按需地址分配机制，更加充分地利用了网络的可用地址，增加路由节点能够连接的子节点数。同时,将16 bits短地址分段，引入了簇首段和区域段，使其适应新算法，并保持了“地址—区域”的对应关系。针对提出的地址分配机制，改进了现有的Zig Bee网络树路由和AODVjr协议。

1 网络模型构建

1.1 模型定义

Zig Bee网络的数学模型为G=(V,E)，其中，V为节点的集合，V={ZC}∪Vc∪Vr∪Ve，ZC为网络协调器，Vc为簇首节点的集合，Vr为路由节点的集合，Ve为终端节点的集合，E为所有对称无线通信链路的集合。

为便于研究，本文中定义了下列概念：

定义1 地址空间[6](address space)：指具有一定位数的地址集合，本文中指Zig Bee网络的所有地址和各个区域段中的所有地址。

定义2 地址分段(address segmentation)：指将16 bits短地址按位数再分成前后2段，第一段称为簇首段，第二段称为区域段。

定义3 簇首段(cluster segmentation，CS)：Zig Bee网络由多个逻辑区域组成，每个逻辑区域中有一个簇首，簇首节点地址就是该逻辑区域的簇首段地址。

定义4 区域段(regional segmentation，RS)：16 bits地址分段后，第二段中的位数构成网络的子地址空间，分配了该子地址空间中地址的节点在逻辑上处于同一个区域内，拥有同一个簇首。

1.2 模型构建

本文构建的Zig Bee网络结构模型如图1所示，图中的每个六边形区域表示一个区域段子地址空间，子地址空间的地址连续，每个区域段有一个簇首，分配一个簇首段地址，且每个区域子地址空间包含的地址数相同，所有的簇首节点组成了网络的主框架结构。如果簇首段分配了i位，则区域段占有16-i位，这时网络中最多有2i个簇首，即有2i个区域段子地址空间，每个区域段子地址空间有216-i个连续的地址。表示网络模型中最多可分布2i个六边形，每个六边形中有一个簇首节点Vc，簇首节点均具有路由能力。ZC协调器节点是特殊的簇首节点，用于开始时组建网络。网络中的其它路由节点Vr和终端节点Ve分布在逻辑区域内，与簇首节点构成局部区域网络。不同逻辑区域间的节点通信都要经过簇首节点转发，同一逻辑区域的节点通信，只在本逻辑区域内建立路由。

图1 逻辑区域分布的网络模型示意图

2 基于逻辑区域的地址分配算法

本文根据按需分配地址空间的思想，提出了基于逻辑区域的地址分配算法(logical regional address assignment，LRAA)。地址分配算法将16 bits地址位数分成2段，这样就把整个地址空间分成了大小相同的连续区域片段。当需要分配地址的时候，区域段的簇首节点分配地址给新加入的节点，或协调器分配一个区域段给新加入的具有路由能力的节点，并把其作为该区域段的簇首。

2.1 LRAA流程

LRAA流程包括初始化、地址请求、地址分配和区域段分配4个阶段，具体流程如下:

1)初始化:网络协调器将自己的地址设为0，并确定参数，簇首段CS、区域段RS和区域段中节点距簇首节点的最大跳数Lm，然后广播组网消息。

2)地址请求:无地址的节点收到广播的组网消息后，将所有的簇首地址存入邻居表；然后，从邻居表中选择一个信号最强的簇首节点，向其发送地址请求消息；如果收到无地址分配的消息，则依次向邻居表中的其它节点发送地址请求，直至发往所有邻居节点。

3)地址分配:如果簇首节点收到其它节点的地址分配请求，首先查看自己的区域段中是否有可分配的地址，若有,则采用随机地址分配机制分配地址；若无,剩余地址则直接发送无地址分配的消息到分配地址请求节点。

4)如果节点无法获得某个区域段的地址，则通过已知区域的簇首节点通知协调器为其分配一个新的区域段，当然，只有具有路由能力的节点才能向协调器申请一个的区域段，因为需要负责簇首的功能。

5)如果申请加入网络的节点距最近簇首节点的跳数超过区域段设定的最大跳数Lm，但是能够和已加入网络中的节点通信，则该已加入网络中的节点通过簇首节点向协调器申请一个新的区域段，并请求断开与源区域段中簇首节点的连接，成为新区域段中的簇首节点后接受申请加入网络节点的连接。

2.2 LRAA路由

为了适应新的网络地址分配机制，本文改进了AODVjr路由算法，将网络中的AODVjr路由算法分成两部分，分别是由簇首节点组成的主干网的路由和区域段中的路由。改进后的路由协议主要步骤如下，为了便于分析，本文设定CS段的位数是8，RS段的位数也是8，则网络中最多可以有256个区域段，每个区域段有256个地址。

1)在由簇首节点组成的主干网和逻辑区域段网络中分别使用按需路由协议AODVjr建立路由，并动态维护。主干网中建立路由时，收到路由请求RREQ包的非簇首节点不做处理；区域段中建立路由时，非该区域段中的节点收到RREQ包时不做处理。

2)地址为A的路由节点收到目的地址为D的数据分组时，计算地址A节点和目的节点是否属于同一区域段。判断的方法为

1111111100000000&A=1111111100000000&D.

(1)

3)如果式(1)成立，说明节点A和节点D属于同一个网络，使用区域段中的AODVjr路由算法将分组发送到目的节点。目的节点不存在时，丢弃分组。非同一区域段的节点收到分组后，直接丢弃不予处理。

4)如果式(1)不成立，说明目的节点D属于其它的区域段，节点A通过区域段中的AODVjr路由算法先将分组转发给自己所属区域段的簇首节点Ac，簇首节点Ac通过主干网中的AODVjr路由算法将分组转发到相应的区域段，分组到达目的节点D所在区域段后，簇首节点再通过区域段中的AODVjr路由算法将分组转发给目的节点D。如果目的节点不存在，则丢弃分组。

2.3 LRAA分析

LRAA具有随机地址分配的灵活性，能够充分地使用网络地址，同时具有分布式地址分配的“地址—区域”关系，具有相同簇首段的节点分布在同一逻辑区域内，由于协调器限定了区域中节点到簇首节点的最大跳数Lm，所以,在同一逻辑区域内的节点在物理位置上也集中分布在小范围区域内。LRAA可有效控制网络中路由查找包，处理位置频繁变化的节点。LRAA更适用于节点分布均匀的网络，当网络中某处的节点密度非常大时，可在此区域分配多个区域段，如图1(a)中的S区域所示。由图1可知,使用LRAA的网络延展性好，能够处理复杂的网络。若出现极端的情况，例如:网络节点处于一条线上，此时如果为每个节点分配一个区域段就会造成地址的浪费，此时需要改变最大跳数Lm值，将这些节点可容纳在一个区域段中。LRAA中簇首节点的维护开销大，易耗尽能量，可在区域段中指定其它合适路由节点为备用簇首节点，当原簇首节点因为被破坏或能量耗尽时，可与协调器协商启用备用簇首节点，同时,区域段中的路由由簇首节点的邻居路由节点来维护，可降低对簇首节点存储空间的需求。其次,16 bits地址中的CS段和RS段的具体分配对网络性能的影响在算法中也没有讨论，这些问题将在下一步工作中深入研究此问题。

3 仿真实验

仿真实验中将DAAM算法和LRAA作为比较的参照，通过仿真实验比较二者之间在地址分配成功率、网络稳定性和算法效率等性能方面的差异。

3.1 仿真设置

仿真工具采用Omnet++，网络覆盖面积为400 m×400 m，网络中路由节点数分别为500,1 000,2 000,4 000,8 000个，节点密度范围为320 m～20 m2/个，节点在仿真区域中随机均匀分布，协调器位于仿真区域的中心。节点的MAC层和物理层采用IEEE 802.15.4标准，节点通信距离设为35 m，网络中具有路由能力的FFD节点与终端节点比例为1∶1，网络协调器参数初始化CS=8,RS=8,Lm=5。每个仿真实验做50次，结果取平均值。

3.2 仿真结果

1)地址分配成功率

从图2可看出，LRAA在五类网络环境中的地址分配成功率均明显高于DAAM算法，两类算法的平均地址分配成功率最小差距也近20 %，LRAA高效的地址分配在于算法有效地利用了网络地址，除了受网络的短地址限制外，并不受其他参数的限制，更多节点能够加入网络。

图2 地址分配成功率比较

2)控制报文开销

图3说明了LRAA的控制报文在各类网络中均不大于DAAM算法，同时仿真实验验证了前面的理论分析。随着网络节点数的增加，LRAA的优势明显的高于DAAM算法，原因是使用DAAM算法时，当网络规模变大，网络中无法分配到地址的节点迅速增加，造成了多次的地址请求，出现了大量的控制报文,而网络规模对LRAA的影响却很小。

图3 地址分配控制报文开销

3)地址分配平均耗时

图4表明了LRAA的地址分配平均耗时整体上小于DAAM。原因在于DAAM算法中无地址的节点会多次向邻居节点申请地址，增加了网络地址分配的延时。当网络中的节点规模较小时，2种算法都能给所有节点分配地址，平均耗时差别不明显，但当网络的规模变大时，LRAA的地址分配耗时明显的低于DAAM算法。

图4 地址分配平均耗时比较

4 结束语

本文提出了一种基于逻辑区域的按需地址分配算法——LRAA，当需要加入网络的节点无法找到合适的父节点时，就通知协调器再分配一块新的区域段地址给网络，算法的控制开销小，仅当需要向协调器申请新的区域段时才发送请求地址块包，算法同时使得节点具有“地址—区域”的特征，将区域段中的按需矢量路由算法和主干网的路由算法相分隔，避免由于AODVjr路由算法路由请求包的广播引起网络性能的下降。理论分析和仿真结果显示:与DAAM算法相比，LRAA能够充分的使用网络地址，控制开销和网络时延等性能均更加优异。

参考文献:

[1]Zig Bee Specification Version 2008.Zig Bee Document 053474r

17[S].2008.

[2]Lin Shizhuang,Liu Jingyu,Fang Yanjun.ZigBee based wireless sensor networks and its applications in industrial[C]∥IEEE International Conference on Automation and Logistics,2007:1979-1983.

[3]Li Yanrui,Shi Haibin,Tang Biyu.Address assignment and routing protocol for large-scale uneven wireless sensor networks[C]∥Int′l Symposium on Computer Network and Multimedia Technolo-gy(CNMT),2009:1-4.

[4]Lü Yunfei.Research on address shortage in a tree based ZigBee network[C]∥Int’l Conf on Information Security and Intelligence Control (ISIC),2012:70-74.

[5]Pan Mengshiuan,Tsai ChiaHung,Tseng Yuchee.The orphan problem in Zig Bee wireless networks[J].IEEE Transactions on Mobile Computing,2009,8(11):1572-1584.

[6]Ren Zhi,Li Pengxiang,Fang Jun.Segmentation-based on-demand scalable address assignment for Zig Bee networks[C]∥IEEE Vehicular Technology Conference,2011:1-5.

[7]Fang M Q,Wang J,Xu X H.A preemptive distributed address assignment mechanism for wireless sensor networks[C]∥Proceedings of the 4th International Conference on Wireless Communications,Networking and Mobile Computing,2008:1-5.

[8]Li Y R,Shi H B.Address assignment and routing protocal for large-scale uneven wireless sensor networks[C]∥2009 International Symposium on Computer Network and Multimedia Techno-logy,2009:1-4.