0 引言

　　为了满足低功耗、低成本的需求，短距离通信ZigBee技术应运而生，它是一种基于802.15.4的技术提案[1][2]。ZigBee网络的不同节点通过网络协调器来完成各个节点的协同工作[3]。ZigBee中的分布式地址分配机制(Distributed Address Assignment Mechanism，DAAM)算法具有简单以及包含“地址-位置”关系等优点。但是随着网络节点的增加，DAAM算法就会显示出它的弱点，这时有些节点因为分配不到地址无法加入网络而成为孤立节点[4]。

　　为了减少网络中的孤立节点，目前已开展很多该方面的研究。由于节点密度以及网络深度等原因将会造成网络地址的不足，但是此时有些路由节点仍有未使用的地址，这时可以向这些有剩余地址的路由节点借用地址来达到减少孤立节点数量的目的，这一思想在文献[5-6]有具体体现。文献[7-9]提出了进行地址扩展的思想。文献[10]提出了一种基于最小跳数的按需分配的地址分配算法。该方法首先由sink节点以洪泛方式向全网广播最小跳数的构建消息，从而使每一个网络节点都有到sink节点的最小跳数，然后根据已构建的最小跳数树获取地址。另外文献[11]提出了一种动态参数的分配算法，该方法可以减少孤立节点数量，但是增加了网络开销，并且扩展性不强，当网络节点很多时，增加了组网时间。

　　本文提出了一种基于动态参数的按需可扩展地址分配算法(AP-SAAM)，同时给出了改进的路由算法，使其兼容cluster-tree路由协议。

　　本文的贡献主要如下：

　　(1)提出了一种基于动态参数的按需可扩展地址分配算法，可以根据已知网络参数来决定扩展的地址大小，同时兼容原DAAM算法。

　　(2)可以根据网络状态进行参数调整以及扩展次数，具有很强的扩展性。

　　(3)给出了改进的路由算法，且与cluster-tree路由协议兼容。

1 系统模型

　　本文对地址的扩展思想为：首先计算出DAAM定义的地址空间，然后得出可以表示这些地址空间的最小比特位数a0，然后把剩余的地址分成Rm段，如果不进行地址扩展，就使用第一段地址空间；如果进行一次扩展，则使用第二段地址空间；以此类推，直到网络地址扩展完，每一段地址所占的比特位数如图1所示。

　　其中，ai表示各个地址块所占用的比特位数。

　　具体地址段的分配方式如下：

　　根据已知条件可以得出DAAM分配的最大空间Am，可用式(1)计算：

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

　　又因为

　　为了考虑一般性，我们只考虑Rm>1的情况，此时有：

　　整理得：

　　所以得出可表示Am的最小比特位数a：

　　a=min{a|2a≥Am}(5)

　　进而得出每一块地址段所占的比特位数为：

　　其中i表示地址块数，即扩展的次数。

　　假设O、R分别代表普通设备和路由设备，N1，N2分别表示没有获得网络地址的普通节点以及路由节点的个数，Li表示第i个网络设备的深度，Oam表示地址为a的普通节点的深为m，Rbm表示地址为b的路由节点的深度为n，则新的网络参数为：

　　然后进行第一次地址扩展，这时协调器只会给个路由节点分配扩展后的地址块，如果第一次扩展后仍有孤立节点，然后再进行第二次地址扩展，以此推论，直至整个地址空间用完，分配方法如式（8）：

　　且Nd≤，其中Achildren为扩展地址，i表示进行地址扩展的次数，Nd表示第i次扩展时路由节点数。

　　得到地址块的路由节点可以再次进行地址分配，分配方式仍按照原DAAM算法，参数为：。其可分配的地址大小为，其中i表示扩展次数，且1≤i≤Rm。

2 基于动态参数的按需可扩展地址分配算法

　　2.1 AP-SAAM算法步骤

　　(1)DAAM算法：

　　初始化：网络协调器把自己的地址设置为0，网络参数为Lm、Rm和Cm。

　　地址请求：节点向其邻居表中未被标记的潜在父节点发出入网请求(当有多个时随机选择)；如果未收到答复，则依次向其他未标记的节点发出入网请求，如果仍未得到回复，则向协调器发送第一次地址扩展请求，同时转向步骤(3)，如果仍没有获得地址，发送第二次地址扩展请求，以此类推。

　　地址分配：地址为Aparent的路由节点收到入网请求时，首先查询自己的地址空间，如果有地址，则按照原DAAM算法进行分配。

　　(2)地址扩展：

　　网络协调器收到借用地址请求后，根据式(6)对网络进行地址块的划分；然后按照式(7)计算。

　　(3)扩展地址分配：

　　此时网络协调器进行第一次地址扩展，根据式(8)对申请的个路由节点进行地址的分配（如有剩余，留作下次使用）。网络协调器需要维护这些路由节点的路由表，得到地址块的路由节点向其潜在父节点发出作为其子节点的请求，并上报自己的网络地址，同时标记自己的网络深度为其父节点深度加1，用Lj表示，当此路由节点再次收到节点的入网请求时，则按照式(9)进行地址的分配：

　　其中，Aparent为父节点地址，Li为申请加入的节点深度，且满足Li-Lj≤。

　　2.2 路由算法改进

　　经过扩展地址分配后，可能的网络地址结构如图2所示，其中A、B为获得扩展地址的节点区域，C为按照原DAAM算法得到地址的节点区域。对此，源节点以及目的节点的地址类型就会有四种情况，如表1所示。

　　假设源节点网络地址为A，深度为d；目的节点网络地址为D。首先判断式(10)、(11)是否成立

　　如果式(10)和式(11)都成立，则执行步骤1；如果式(10)成立，式(11)不成立，则执行步骤2；如果式(10)不成立，式(11)成立，则执行步骤3；如果式(10)不成立，式(11)不成立，则执行步骤4。

　　步骤1：首先判断逻辑表达式(12)是否成立，其中参数为Lm、Rm、Cm。

　　A<D<A+Cskip(d-1)(12)

　　如果不成立，则交给A的父节点；如果成立，且D是A的一跳邻居节点，则修改下一跳地址Ne=D，若不是一跳邻居节点，则通过式(13)计算下一跳地址，其中参数为Lm、Rm、Cm。

　　其中0≤d≤Lm。

　　步骤2：首先判断逻辑表达式(14)是否成立：

　　其中Achildren为节点A的子节点。

　　如果成立，则表示目的节点属于节点A的子节点的扩展地址域，然后修改下一跳地址Ne=Achildren；如果不成立，则修改下一跳地址为A的父节点即：Ne=Aparpent。

　　步骤3：修改下一跳地址为A的父节点即：Ne=Aparpent。

　　步骤4：首先判断逻辑表达式(12)是否成立，其中参数为。

　　如果不成立，则交给A的父节点；如果成立，若D是A的一跳邻居节点，则修改下一跳地址Ne=D，若不是一跳邻居节点，则通过式(13)计算下一跳地址，其中参数为，且0≤d≤。

　　综上所述，修改的路由协议能够满足地址分配算法。

3 算法仿真

　　把DAAM、EDAA-BA[5]、RBAC[9]作为比较对象，通过OPNET仿真来观察它们在性能方面的差异。其中网络参数分别设为Cm=4，Rm=2，Lm=15。

　　图3表示的是平均地址分配成功率与网络节点个数之间的关系。从图中可以看出，EDAA-BA、RBAC以及AP-SAAM的分配成功率要高于DAAM，且AP-SAAM最高，特别是随着节点数的增加，AP-SAAM的性能更优，这是因为AP-SAAM能够根据网络状况实施地址扩展，从而能够分配更多的地址，进而提高节点入网的概率。

　　图4表示的是平均分配耗时与网络节点个数之间的关系，有图可知，EDAA-BA、RBAC以及AP-SAAM都比DAAM平均耗时大，其中EDAA-BA耗时最大，这是因为其不断进行借用地址花费了大量的时间，这一现象随着节点的增加、网络结构的复杂变得更加明显，RBAC和AP-SAAM的平均耗时相当。

　　图5表示的是平均路由跳数与网络节点个数之间的关系，其中路由跳数表示节点到其潜在邻居节点的跳数。从图中可以看出RBAC算法和AP-SAAM算法相当，而EDAA-BA要优于其它三种算法，这是因为EDAA-BA算法在进行借用地址时专门考虑了迂回问题。

4 结束语

　　本文提出了一种基于动态参数的按需可扩展地址分配算法，当地址充足时，使用DAAM算法；当出现地址不足时，对剩余地址空间进行扩展，根据已知参数对剩余地址块灵活的分配，同时根据网络状况进行一次或者多次扩展，从而很好地解决了孤立节点问题。

参考文献

　　[1] Huang Yu-Kai，Pang，Ai-Chun，Hsiu，Pi-Cheng，et al.Distubuted throughput optimization for ZigBee cluster-treeNetworks[J].IEEE Computer Society，2012(5)，23(3)：513-520.

　　[2] 宁炳武，刘军民.基于CC2430的Zigbee网络节点设计[J].电子技术应用，2008(3)：95-99.

　　[3] Natalia C Fer，Marcelo D D Mor，Otto C M B Dua.AnEfficient and Robust Addressing Protocol for Node Auto-configuration in Ad Hoc Networks[J].IEEE/ACM Transac-tions on Networking，2013(4)，3(21)：845-856.

　　[5] KARAPISTROLI E，PAVLIDOU F N，GRAGOPOULOS I，etal.An overview of the IEEE 802.15.4a standard[J].IEEECommunications Magazine，2010，48(1)：47-53.

　　[6] 姚玉坤，陈永超，李鹏翔，等.ZigBee网络中基于借地址的高效分布式地址分配算法[J].重庆大学学报，2012(8)，35（8）：151-158.

　　[7] Natalia C F，Marcelo D D M，Otto Carlos M B D.AnEfficient and Robust Addressing Protocol for Node Autoconfiguration in Ad Hoc Networks[J].IEEE/ACM Transac-tions on Networking, Jun.2013，vol.21：845-856.

　　[8] 任智，李鹏翔，姚玉坤，等.基于分段的ZigBee网络按需可扩展地址分配算法[J].通信学报，2012，33（5）：131-137.

　　[9] Li-Hsing Yen，Wei-Ting Tsai.The room shortage problemof three-based Zigbee/IEEE 802.15.4 wireless networks[J].Computer Communication，2010(33)：454-462.

　　[10] 胡义，文建国，罗娟.时间驱动型传感器网络地址分配算法研究[J].计算机工程与应用，2009，45(33)：83-85.

　　[11] Shu-Chiung Hu，Cheng-Kuan Lin，Yu-Chee Tseng.Automatic parameter selection for the ZigBee distributedaddress assignment mechanism[C].2013 IEEE 24th Inter-national Symposium on Personal, Indoor and Mobile RadioCommunications: Mobile and Wireless Networks, 8-11Sept 2013, London, United Kingdom，2013：2062-2066.