ZigBee网络树路由改进算法研究

1、ZigBee网络树路由改进算法研究摘 要：本文深入研究了 zigbee网络中树路由算法，并提出了基于邻居表 的改进树路由算法（ntr）：找到源节点和目的节点的公共邻居节点；建立一种 邻居节点选择策略。ntr在一定程度上可以解决树路由原有算法不灵活的缺 点，节省了地址空间，提高了路由效率。实验表明该算法减少了整个网络的路 由费用和延时时间，节约了网络的能量消耗，提高了网络的实时性。关键词：无线通信；zigbee；树路由；能耗0引言随着科研领域及产业界的广泛努力，作为wpan （无线个域网）的热点技术之一的zigbee技术已经取得了快速的发展。自从 zigbee联盟颁布了 1.0版 本的规范之后，

2、它就在军事、个人通信、紧急和临时场合发挥着重要的作用。 特别是随着无线传感器网络技术的发展，这项技术受到了越来越多的关注和重 视。最新的消息表明，zigbee联盟与rf4ce 集团已经制定了适用于各种遥控 型音频/视频消费类电子产品的 zigbee rf4ce 规范，可以看出zigbee技术自 身以及与其他技术的结合将在各个领域发挥着主导作用。目前zigbee所使用的路由算法之一的tree路由算法只是按照单纯的父 子关系来进行路由选择。当一个节点接收到数据后，如果发现该数据并不是给 自己的，那么它将根据自己的判断转发给它的父节点或者子节点，然后由其父 节点或者子节点按照同样的过程继续传送数据。

3、整个路由算法完全没有路由发 现过程，即完全没有路由开销的浪费。但是 tree路由算法最大的一个缺点就 是其建立的路由并不一定是最优或者最短的路径，同时又会在数据传输过程中 带来大量的时延，特别是在大规模节点网络中会导致不均衡的流量分配与整体 网络能量的消耗。在文献和文献中，t. kim 和wanzhi qiu 等人提出了利用邻 居表建立最短树路由的想法，以此来减少原有树路由的跳数，进而减少不必要 的路由开销。但是他们的文章里没有提到邻居表里的邻居节点是如何选择的， 如果节点选择不当，也会对增加一定的运算量和存储空间，所以邻居节点的选 择策略对于其网络性能的影响也不容忽视。本文的主要工作有两点：

4、一是对于 2跳的距离，提出找到源节点和目的节点的公共邻居节点；二是基于邻居表参 与的树路由算法提出一种邻居节点的选择策略。1 zigbee树路由算法分析zigbee协议中规定了两种路由算法：tree路由和aodvjr 路由。其中tree路由包括网络地址分配和tree路由算法，而aodv路由在这里 不做过多地介绍。1.1 网络地址分配加入zigbee网络的节点通过mac层提供的关联过程组成一棵逻辑树，当网络中 的节点允许一个新节点加入网络时，它们之间就形成了父子关系，每个进入网 络的节点都会得到父节点为其分配的用于路由和数据传输的16位网络地址。当网络形成时，zigbee协调器首先要根据需要规定

5、3个参数：每个父节 点最多可以连接的子节点个数 mc;子节点中最多可以连接的路由节点个数 m r ;网络的最大深度m l。其中m c应大于等于m r ,这样就可以保证协调器或者路由器可以连接至少(m c - m r ) 个终端节点。cskip(d)是网络深度为 d的父节点为其子节点分配的地址之间的偏移量，可按公式进行计算。如果一 个父节点的cskip(d)为0时，就不再具备为其子节点分配地址的能力，即不能 够再让别的节点通过它加入网络；如果一个父节点的cskip(d)大于0时，则可以接受其它节点成为它的子节点，并且将根据子节点是否具有路由能力来向子 节点分配不同的地址。利用cskip(d)作为

6、偏移量，向具有路由能力的子节点分 配网络地址。它会为第一个与它关联的路由节点分配比自己大1的地址，之后与之关联的路由节点的地址之间都相隔偏移量cskip(d),以此类推为所有的路由节点分配地址。zigbee协议中规定协调器的网络深度一定为 0,其网络地址 也一定为00假设父节点的地址为parent a ,对于它的第k个路由节点，其 地址分配公式如下 a = a + cskip(d) < (k < 1) +1 k parent (1< k <rm) (2)终端节点分配地址与为路由节点分配地址不同，第 n个与之关联的终 端子节点地址为n a可按下式计算an aparent

7、cskip d rm n = + ( ) ? +(1 < n < cm< rm ) (3)1.2 tree路由算法在tree路由网络中，协调器和路由器都是沿着树状结构传送数 据的。当一个节点接收到数据后，首先检查自己是否为目的节点，如果是则接 收数据。如果不是，再检查自己的后代节点是否为目的节点：如果是，则将数 据送到指定的子节点；如果不是后代节点，则将数据送给其父节点。假设目的 节点的网络地址为d ,则当有一个深度为d ,网络地址为a的路由节点，如 果满足下式则可以判断目的节点是本节点的后代节点。此时该节点会根据下式 来判断下一跳的地址如果目的节点地址是与本节点相连的终端节

8、点则直接发 送，否则就发送到目的节点所在地址的路由节点；如果目的节点不是本节点的 后代节点，即不满足式(4),则下一跳地址n就是该节点的父节点，向上继续寻 找目的节点所在的地址。2邻居表和路由成本2.1 邻居表邻居节点和邻居表是zigbee协议里规定的。当一个zigbee节点想要加入 一个网络的时候，它会以广播的形式将请求连接的信息传给其一跳通信范围内 的其他节点；收到请求连接信息的其他存在于已知网络中的节点会给要求加入 网络的节点传回一个信息；最后要求加入的zigbee节点会根据接到的信息选择一个合适的父节点，再回传一个加入信息并正式加入该网络。在这些信息相 互传送的过程中，该节点就可以从中

9、得知一跳范围内节点的一些基本信息并将 之存放在zigbee结构中用于存储邻居节点信息的预设空间内，那么存储邻居 节点的预设空间就是该节点的邻居表。邻居表的内容是可以调整的，根据用户 的需要可以设置邻居节点的一些基本信息，如扩展地址、网络地址、节点类 型、邻居节点与当前节点的关系和链路质量指示(lqi )等，当然还可以加入其 它相关信息。协议中指出，邻居表对于发现网络、发现潜在父节点和了解周围 节点信息有着很重要的作用。本文正是利用邻居表里的相关节点信息对原有 tree路由算法进行分析，找到路由费用最小的路径。另外，每当节点接收到从 邻居节点发来的任何帧的时候，其邻居表的信息就更新一次。2.2

10、路由成本在路由选择和品&由维护时，zigbee的路由算法使用了路由成本的度量方法 来比较路由的好坏。假定一个长度为l的路由p,则它的路由成本为其中，lp 为链路中发送数据包的概率。对于l p的测量或者估计，最直接和有效的方法 就是基于ieee802.15.4 的mac层和phy层所提供的每一帧的lqi通过平均所 计算的值。lqi的取值从0到255,其值越高表明链路质量越好，传输越可靠。平均 lqi值与cl值的关系是：lqi值大于75时，链路成本为1; lqi值在50和 70之间时，链路成本为3;其值小于50时，链路成本为7。3 ntr（neighbour-tree routing） 算

11、法zigbee协议中的树路由只是依靠相关节点的父节点或者子节点进行路由选 择，而不需要路由表的参与，所以相对来说比较简单。但是这种路由算法有一 个问题是无法避免的，那就是数据包可能要经过好几跳才能到达目的节点，即 使目的节点在这个节点的一跳通信范围之内。zigbee 中的树路由tree routing in zigbee本来一跳就可以到达的距离，按照树路由却需要4跳。可以看出树路由算法有其自身的局限性，多出的 跳数会浪费一定的路由费用，增加节点的功率消耗。如果节点在发送数据之 前，先考虑一下自己的邻居节点，也就是先审查一下自己邻居表里的节点，或 者以邻居表里的合适节点作为下一跳，参与路由算法，

12、那么就可以减少其路由 跳数，节省一定的能量开销，如图 2所示。邻居表参与的树路由tree routing by using neighbor table一个节点的邻居表当它在加入网络的时候就已经获得了，当节点收到数据包的时候，就可 以借助邻居表的帮助。该ntr算法描述如下：首先该节点判断自己是否其目的节点，如果是，接收数据包；否则，利用 式判断是否为其后代节点，如果是，具下一跳转发给其恰当的子节点；否则， 则启用邻居表，查找邻居表中的节点（这里节点个数取4,而且父节点也作为其邻居节点），如果目的节点在表中，则下一跳直接转发给其对应的邻居节 点；否则，查找目的节点的邻居节点，如果目的节点和源节点

13、的邻居表中有相 同的邻居节点，说明从源节点到目的节点只需要2跳，下一跳则为这个共同的邻居节点。到达目的节点具有最佳路径（最小跳数）邻居节点的判断策略：首先找出 每个邻居节点与目的节点具有最大深度的公共父节点，然后根据公共父节点的 深度计算每个邻居节点到达目的节点的跳数，从中选择最小跳数的相应邻居节 点作为下一跳地址。如果此时有多个跳数相同的路径时，则比较邻居表中每个 邻居节点的lqi值，选取最大者作为下一跳的地址。ntr算法流程ntr algorithm flow4实验与仿真本文利用ns2里ieee802.15.4的phy层和mac层，实现了网络层路由协议的仿真，研究了改进 的路由算法，也就是

14、ntr路由算法对于整个网络的路由费用和端到端延时的影 响。所有的仿真数据均是在独立情况下运行 50次求得的平均值。发送数据的 源节点和接收数据的目的节点随机产生。本次实验的网络拓扑结构为：协调器 在网络的中心位置，其它节点随机分布在协调器的外围。仿真设置参数如表1所示。在节点分别为20、40、60、80和100的情况下，整个网络的路由费用如 图4所示。可以看出随着节点数目的增加，tr和ntr的路由费用也是增加 的，这是因为节点数目越多，网络拓扑越大，节点传输数据经过的跳数就越 多；ntr由于有了邻居表的帮助，特别是在的情况下，其跳数是大大减少的， 降低了路由跳数，节省了一定的功耗。tr 和nt

15、r 算法的平均跳数 average hop-counts of tr and ntr随着节点数目的增加，其对端到端延时时间的影响。由图得知，由于 ntr算法路由跳数 的减少，可以减少一定的延时时间，提高网络的实时性。正常的树路由很多时 候都经过网络协调器进行数据传输，特别是源节点和目的节点分别位于协调器 的上部区域和下部区域或者左侧和右侧的时候。有了邻居表的参与，可以不经 过协调器，用很少的跳数就可以将数据送到目的节点，减少了传输延时，节省 了协调器的能量。tr和ntr算法的端到端延时end to end delay of tr and ntr 这里将参 考文献中提出的短径树路由算法简称为 s

16、tr , str算法是在zigbee协议的基础 上，根据网络中的节点特性和节点自身的运算能力，利用邻居表中的邻居节点 找出跳数最少即路由成本最小的短径路由。同时该文献通过分析str算法的复杂度和路由费用说明了此算法是符合 zigbee协议的。正是比较了 str和ntr 算法各自节省的跳数百分比，从图中可以看出ntr比str算法在网络的总体效能上是有所提高的。3结论zigbee是一种新兴的短距离、低功率、低速率无线接入技术。zigbee所使用的路由算法之一的tree路由算法只是按照单纯的父子关系来进行路由选 择。这种算法不需要路由表，相对来说比较简单，可以节省一定的存储资源， 但是不灵活的路由和较低的效率的缺点也是很明显的。本文深入研究了树路由