ZigBee传感网络Cluster-Tree改进路由算法研究 传感器, 可靠性, 网络, 成本, 技术

无线传感器网络(WSN )已经成为当前国际上备受关注的、知识高度集成的前沿热点研究领域之一,近年来出现了很多针对WSN的新路由协议和设计方法[ 1- 3] 。ZigBee技术拥有低成本、低功耗、低复杂度、网络容量大、可靠性高等方面的优势, 已经成为WSN的主流技术。随着ZigBee协议的不断升级, 基于ZigBee技术的无线传感器网络(以下简称ZigBee网络)必将在工业控制、工业无线定位、家庭网络、汽车自动化、楼宇自动化、消费电子、医疗设备等多个领域实现更广泛的应用[ 4] 。如何根据不同的需求设计高性能的Zigbee网络, 如何将Zigbee网络与其他网络进行可靠连接, 达到功能互补是目前研究的重点和热点问题, 这些问题都可以归结为网络的路由问题。一种可适应Zigbee网络的高效的路由算法可以有效降低节点能耗, 更好地延长网络生存时间。
1. ZigBee网络描述

Zigbee网络的数据传输方向是双向的, 支持3种网络拓扑结构, 分别是星型、树型和网状型网络,其各自的网络拓扑结构如图1所示。







星型网络中的节点通信距离短, 网络覆盖范围有限, 不利于网络功能扩展, 但其结构简单, 是一种常用且适合长期运行使用操作的网络; 网状型网络中的每个节点都可以作为路由节点, 源节点的数据可以通过多个路径到达目的节点, 具有较强的健壮性, 是一种高可靠性网络, 可提供多个数据通道, 是一个高级别的冗余性网络; 树型网络结合了星型结构和网状结构的优点, 具有很好的扩展性。

ZigBee网络同其他无线传感器网络主要的不同之处在于其采用的预先地址分配方式, 整个网络的地址分配方案由分布式算法根据一系列网络自定义参数来确定, 任何节点想要加入网络, 必须要通过已存在网络中的FFD(全功能设备, 包括路由器和协调器), 当成功加入网络后, 该节点自动获得一个唯一的网络地址。定义Cm 为最大子节点数, Rm 为子节点中最大的路由节点数, Lm 为最大网络深度。则网络深度为d 的路由节点所能分配的地址空间Cskip ( d )满足公式( 1), 分配给第k 个子路由器节点的地址Ak 满足公式( 2), 分配给第n个终端节点的地址An 满足公式( 3)。






2. Cluster Tree路由算法改进

2. 1 问题分析

Cluster Tree就是由主协调器展开生成的簇树状网络拓扑结构, 不需要存储路由表。树中的大部分设备为FFD, 具有转发功能, 而RFD (终端设备)作为树枝末尾处的叶节点, 一次只能连接到一个FFD 上。如果RFD节点要发送数据包到某目的节点, 则直接将该数据包发送给其父亲节点, 由父亲节点进行转发。如果一个网络地址和网络深度分别A 和d 的FFD节点要发送数据包到目的地址为D 的节点, 则先通过公式( 4)判断目的节点是不是该FFD的下属节点, 如果是其下属节点, 则按照公式( 5)转发数据包, 下一跳节点地址即为公式( 5)计算出的网络地址,如果不是其下属节点, 则把该数据包交给父亲节点转发, 下一跳节点地址即为父亲节点的地址[ 8] 。







Cluster Tree算法按树型结构分层遍历, 算法简单且查找目的节点的速度快, 通过簇首的数据融合可以减少信息冗余度和源节点的发送功率, 对于数据聚合非常有利[ 9] 。其缺点在于这种非自适应算法决定了其选择的路由不可能是最佳路由, 而且靠近树根的路由节点需转发大量的数据, 必须储备充足的能量。假设有图2所示的网络, 每个区域为一个簇, 区域0、区域1、区域2、区域3 的簇首分别为协调器、节点J、节点W、节点O。当源节点在区域1而目的节点不在区域1, 或者当源节点不在区域1而目的节点在区域1的所有通信都必须经过节点J来转发, 使得节点J 的通信负担过重, 造成能量损耗过快, 当能量减小到小于正常工作所需要的能量时,就会出现网络分割, 缩短网络寿命。当节点O 向节点V 通信时, 尽管他们的距离近, 相互都处于对方的信号覆盖范围, 但他们属于不同的簇, 必须经过上一级的中心协调器来转发, 数据传输走迂回路径, 额外消耗了网络的总体能量。






因此, 许多从事ZigBee技术的研究人员都提出相应的Cluster Tree改进算法[ 8, 10 - 11 ] , 这些算法中,或者提出簇首轮换机制、或者提出建立分布式簇树骨干网、或者提出选择邻居节点路由, 对Cluster Tree路由优化有明显的改善。算法没有对簇首节点的剩余能量进行仔细分析, 中心协调器无法预知现有簇首节点是否接近死亡; 本文提出的Cluster Tree路由改进算法对簇首的选择必须考虑到节点的剩余能量, 并结合AODV jr算法来降低路由距离,进而减少转发数据的能量损耗。
2. 2 改进的Cluster Tree算法

对Cluster Tree算法的改进重点应该是尽量避免小能量的FFD 转发大数据量。假设节点正常工作需要的最小能量值为Emin, 节点所在的网络深度为d i, 则该节点成为簇首所需要的最小能量E 可用公式( 6)来模拟, k1 / (d i + 1)代表簇首必须储备的能量, 因为节点深度从0开始编号, 所以公式中用深度加1表示, 而且深度越小的节点转发数据的概率更大, 对能量要求越高, 能量要求与深度成反比, k1为一特定系数, 作用在于调节簇首储备的能量值。






普通的路由节点和簇首的剩余能量Power都可用公式( 7)来模拟, E 0 为节点初始能量, k2 t / ( di + 1)代表节点在时间t范围内所消耗掉的能量, 随着节点工作时间越长, 节点的剩余能量越小, 随着节点深度越小, 节点消耗能量越快。K 2 为一特定系数, 作用在于调节能量衰减的速度, 簇首的系数比普通路由节点的系数大。

改进后的簇首形成过程如下:

( 1)当簇首通过公式( 7)计算出自身能量较小,不再满足公式( 6)确定的最小簇首能量时, 向中心协调器发送申请, 请求更换簇首。

( 2)当网络规模庞大, 或者网络中有的簇首因能量小而不适合再当簇首时, 中心协调器就发布竞争簇首的信息。并开始等待路由节点的簇首申请。

( 3)路由节点收到竞争簇首信息后, 获取自己的网络深度, 并判断是否有足够的能量储备来竞争簇首, 如果能量充足则转( 4), 否则转( 8)。

( 4)发送RREQ 报文, 并附加簇首申请信息, 要求每个收到该类RREQ 的节点都回复RREP包, 把收到回复的节点加入到邻居节点列表, 转( 5)。

( 5)路由节点向中心协调器申请成为簇首, 并附带上自己的邻居节点列表。

( 6)中心协调器收到簇首申请后, 选择邻居节点多的子设备为新簇首。这样可以最大限度地缩小不同簇之间消息传递的条数, 减小延迟和通信开销,避免不必要的能量耗费。

( 7)新簇首发送簇首广播报文, 根据收到的响应获取簇首与成员节点之间的路由信息, 并维护自己的成员列表。

( 8)没有成为簇首的节点加入到父节点的簇。具体流程如图3 所示。分簇算法的思路为: 选择簇首时考虑节点的能量状态, 以此来降低小能量节点成为簇首的概率; 适当加大簇内深度, 减小簇首数目, 进而减小簇间通信次数, 总体降低节点的能量消耗, 延长网络的生命周期[ 8] 。







申请成为簇首的节点需要广播RREP分组, 处理邻居节点的响应分组, 势必会额外消耗掉一部分能量, 但它避免了簇首死亡而造成网络分割的情况,有效降低短木桶效应对网络寿命的影响。簇首由中心协调器根据簇首申请者的邻居成员列表来指派, 因此, 中心协调器知道所有簇首的成员列表, 并把这个信息公布给各个簇首, 各个簇首也就知道整个网络的拓扑结构, 并且知道每个节点所在的簇首。簇与簇间通信时, 结合AODV jr路由算法,采用洪泛RREQ 路由请求包的方式来寻求最佳路径, 簇内的成员节点不能广播RREQ 包, 只能由簇首发起, 这样可以适当抑止RREQ 的洪泛问题以达到减少RREQ 包的数量进而减少转发RREQ 包消耗的能量。RREQ 的目标节点只能是FFD 节点, 如果转发数据的目标节点是RFD 时, 则由目标节点的父节点转交。具体路由算法如下:

( 1)当源节点有数据要发送给目标节点时, 首先在自己的路由表中查询到目标节点的路由, 如果有路由则直接转发, 如果没有到目标节点的路由, 则查询是否有到目标节点簇首的路由, 如果有则把数据转发给目标节点的簇首, 否则就把数据交给自己的簇首转发, 转( 2)。

( 2)源节点簇首查询是否有到目标节点的路由, 如果路由存在, 则立即转发数据, 如果没有到目标节点的路由, 则查询是否有到目标节点簇首的路由, 如果有则把数据转发给目标节点的簇首, 否则就洪泛到目标节点的RREQ 包, 即开启一个路由发现过程。

( 3)节点收到RREQ 包时, 首先判断自己是否为FFD 节点, 如果不是, 则直接丢弃RREQ 包, 如果是FFD 节点, 则转( 4)。

( 4)确定自己是否为目标节点或者目标节点的父节点, 如果是, 则在路由表中添加到源节点簇首的路由信息, 并返回RREP路由确认包。否则转( 5)。

( 5)中间节点判断是否有到源节点簇首的路由, 如果有则转( 6) , 如果没有到源节点簇首的路由, 则转( 7)。

( 6)根据新收到的RREQ 路由请求包确定到源节点簇首的路由成本, 并与原有的路由成本比较, 如果路由成本高于原有路由, 则丢弃RREQ 包。否则就更新原有路由, 并继续广播RREQ 包。路由成本高于原有路由表明原有路由更近, 本节点已经接收到按照原有路由到达本节点的RREQ, 此次收到的RREQ 包是因为洪泛而产生的重复RREQ 包, 对寻找最佳路由没有意义, 丢弃该包可节省网络能量。
( 7)创建到源节点簇首的路由, 并继续广播RREQ 包。

( 8)中间节点收到目标节点回复的RREP 包时, 也能获取中间节点与目标节点之间的路由信息。具体流程如图4 所示。基本思路就是借助AODV jr算法, 利用路由请求包RREQ 和路由回复包RREP来为源节点、目标节点、中间节点之间寻找最佳的路由, 并适当抑制RREQ 的洪泛问题, 总体上减少降低端到端转发数据消耗的能量和数据传输时延。







3. 仿真实验结果

为了评估改进算法的性能, 在NS2中分别改进前后的Cluster Tree 算法进行了仿真。重点通过网络的死亡节点数、数据传送成功率、端到端延迟来进行对比分析, 仿真结果表明, 这种改进算法能够达到预期的效果。

在仿真环境中, 设置网络范围为300 m *300m,采用CBR 作为数据信息源, 数据包长度为128 bit,网络节点数为200, 网络参数Cm = 5、Rm = 4、Lm = 6,整个网络分为5个簇, 数据包的源节点和目标节点随机选择, 仿真实验结果如图5、6、7所示。






图5显示了网络中的死亡节点数, 从图中可以看出, 算法改进后的死亡节点数明显减少。因为除中心协调器外, 网络中的簇首消耗能量较大, 而改进算法避免低能量节点成为簇首, 延缓了小能量节点的能量减小到小于正常工作所需能量的时间。图6显示了网络中数据包发送的成功率, 从图中可见, 算法改进后, 数据从源节点成功地到达目标节点的比例有所提高。报文发送成功率受网络拓扑结构、信号干扰程度、数据接收能力、网络中的数据流量、死亡节点数等因素的影响。本次仿真时, 网络流量设置为50数据包/ s, 数据包的源节点和目标节点都是随机选择的, 因为改进前后的死亡节点数不同,进而使得数据包发送成功率得到较大程度的改善。

图7显示了数据包从源节点到目标节点的传输延时。算法改进后, 端到端的平均时延减小, 随着节点数增加, 网络中的数据流量也会增加, 进而造成延时也加大。在借助AODV jr思想对Cluster Tree算法改进后, 源节点与目标节点之间的路由得到优化, 数据包的平均传输路径变短, 从而降低了端到端的传输时延。

4 结束语

基于IEEE802.15.4的ZigBee网络是一种新兴的无线传感器网络, 具有广阔的应用场合和发展前景, 对其路由算法进行研究并改进, 对于提高网络利用率、延长网络生命周期有着重要意义。本文对传统ZigBee网络中的Cluster Tree 路由进行分析, 并提出了实用性较强的改进算法。仿真结果显示改进的路由算法能提高数据发送成功率、减少网络中的死亡节点数、降低端到端的传输延时, 对ZigBee网络的应用推广具有较高的实用价值。