作者简介:钱志鸿(1957-),男,教授,博士生导师.研究方向:无线网络技术.E-mail:dr.qzh@163.com
针对现有多径路由算法中存在的路径间干扰问题,通过屏蔽干扰节点,建立非干扰路径。同时,为了均衡网络能量消耗,根据每条路径当前的性能指标值,对源节点流量负载进行合理分配,从而延长网络生存周期。仿真结果表明,基于负载均衡的多径路由(Z-LBMR)算法相对同类型的路由算法在分组投递率、平均端到端时延和网络生存周期方面都有明显改善。
To overcome the problem of inter-path interference in existing multipath routing algorithms, a new algorithm, named Z-LBMR, based on load balancing is proposed, which can establish non-interference paths by shielding the interference nodes. Besides, to balance energy consumption of the network, the Z-LBMR algorithm allocates traffic load reasonably according to the current performance value of each path, thus, prolonging the network lifetime. Simulation results demonstrate that the Z-LBMR algorithm performs obviously better than existing multipath routing algorithms in packet delivery ratio, average end to end delay and network lifetime.
机器对机器(Machine to machine, M2M)技术使机器之间可以互相沟通而无需人工干预, 它的出现对物联网发展具有非常重要的意义。无线传感器是现在M2M通信的主要驱动力, 这使其成为M2M网络的重要组成部分[1]。无线传感器网络中数据的高效传输直接影响着M2M网络的整体性能。现今, 多路径路由方法被广泛应用于无线传感器网络, 它通过高效地利用网络资源提升网络性能[2]。多路径路由协议选择多个路径同时工作, 均衡节点能量消耗, 优化带宽的利用率, 同时提升了整个网络的路由可靠性和容错性[3]。
近年来, 如何在M2M网络中建立能量高效的路由一直备受研究人员的广泛关注。Tekbiyik等[4]研究了M2M网络以最短路径为基础的节能路由选择, 并对当前和未来M2M网络的应用和设计问题进行了分类。如何在资源受限的无线传感器网络中实现高效的多路径路由成为一个新的研究热点。Radi等[5]对近几年提出的多路径路由协议进行分类和研究, 分析了各类路由协议的优缺点以及在无线传感网络中应用所面临的问题。由于ZigBee自身低速率、低成本、低功耗、低复杂度及高可靠性等特点, 使得它在无线传感器网络中得到广泛应用[6]。在众多的多路径路由协议研究中, 针对ZigBee网络的研究较少。Bidai等[7]第一次提出基于树路由的ZigBee多径路由算法(Z-MHTR), 但是仿真表明多路径的使用并没有带来网络性能的提高, 反而因为路径间干扰和隐藏节点问题导致网络性能下降。后来他选择两条相关性最小的路径进行数据传输, 仿真结果表明网络性能要明显优于单路径网络[8]。Cao等[9]通过重新定义地址分配机制, 选择深度较小的节点为潜在父亲节点来避免数据分组碰撞, 理论和仿真表明其性能要优于Z-MHTR算法。然而以上研究都没有充分考虑路径间干扰问题, 也都没有对源节点流量负载的分配进行说明。
本文针对M2M通信对无线传感器网络提出的更高的健壮性和可靠性要求, 对基于ZigBee的无线传感网络路由算法进行研究。为了解决现有多路径路由算法存在的路径间相互干扰和负载分配不均的问题, 通过建立非干扰路径, 减少路径间干扰对数据传输的影响。同时通过对源节点流量负载进行合理分配, 达到均衡网络能耗、延长网络生存周期的目的。
M2M是各种异构的电子、通信和软件技术的结合。一个典型的M2M系统, 如图1所示。其系统架构由M2M区域网络、通信网络和远程客户端3部分组成[10]。
M2M区域网络:该网络提供智能设备与M2M网关之间的连接。M2M区域网络中技术主要包括:①个人区域网络技术, 诸如超宽带(UWB)、ZigBee和蓝牙; ②本地网络技术, 例如电力线通信(PLC)、无线网络连接、蜂窝型基站以及无线M-BUS等。
通信网络:通信网络是在一个M2M应用中智能设备与远程客户端连接的部分。它提供网关与远程客户端(或软件应用)的通信。通信网络的例子包括:xDSL、IEEE 802.11、局域网(LAN)以及全球移动通信系统(GSM)、通用分组无线业务(GPRS)和3G等移动通信技术。有些网关还支持全球定位系统(GPS)技术, 以便利用卫星通信传送位置数据。通信网络允许系统将信息发送到后端服务器, 处理该数据并通过互联网发送到监视和控制智能终端的设施。
远程客户端(或应用程序):这是信息的目的地。远程客户端可以是硬件或接收数据的专门软件。更具体地说, 客户端可以是手机、网页浏览器和智能短信设备等。这些客户端使用的软件应用程序可以对所接收的数据进行分析、报告和处理。
M2M区域网络位于整个M2M系统的最底层, 负责信息的采集或者控制命令的执行。每个子网络都是自组织的, 并被设计用于特定的应用。M2M区域网络是整个系统的基石, 其网络性能对整个M2M系统有着非常大的影响。选择通过ZigBee或IEEE 802.15.4标准对通信网络进行研究。该网络基于IEEE 802.15.4的物理和介质访问控制层, 上层由ZigBee协议栈定义。对其网络层的路由算法进行改进, 提高网络的健壮性和可靠性, 进而达到改善M2M网络整体性能的目标。
ZigBee有星状网、树状网和网状网3种网络拓扑结构。ZigBee网络中节点一般分为协调器, 路由器和终端节点3种[12]。协调器(Sink节点)负责网络初始化和维护; 路由器负责数据采集和传输; 终端节点负责数据采集。
在ZigBee网络中, 协调器采用分布式地址分配算法(Distributed address assignment mechanism, DAAM)为每个潜在的父节点分配一个有限的网络地址段。协调器建立网络时定义了网络的父节点可以连接的最大子节点数Cm、网络的最大深度Lm和父节点可以连接的最大路由节点数量Rm。可以根据组网参数计算出每个网络深度为
只有当偏移量大于0时, 该节点才具有为其子节点分配网络地址的能力, 即允许子节点的加入。具体分配机制如下:
(1)协调器将自身地址设置为0, 网络深度设置为0。
(2)假设父节点的地址为
(3)当其中第
上述计算的地址决定了设备之间的逻辑关系, 使得节点可以利用这种逻辑关系进行路由选择。树型网络拓扑路由算法中, 节点根据目的节点网络地址计算分组的下一跳, 假设地址为
如果式(4)成立, 则目的节点是接收节点的后代节点, 该数据帧将被转发给它的子节点
如果目的节点不是它的后代节点, 则将数据帧沿着树型结构转发给父节点。
ZigBee网络可以抽象为由多个传感器节点组成的无向图G=(V, E), 其中V为节点的集合, E为所有对称无线通信链路的集合[13]。ZigBee多路径路由就是在传感器节点和Sink节点之间寻找多条可传输链路。多路径ZigBee的设计基于以下前提条件:
(1)Sink节点位于网络中心, 其他节点随机部署在Sink节点周围, 且节点分布较为密集, 如图2所示。
(2)网络组网的地址分配机制和寻址算法采用上述ZigBee网络原有的Cluster-Tree算法。
(3)每个节点动态维护一个邻居表, 用来保存邻居节点信息; 节点的初始能量相同, 发送功率和接受功率也相同。
(4)在MAC层采用IEEE 802.15.4标准的非时隙CSMA/CA机制。并且当Sink节点成功接收数据分组时会返回ACK确认信息。
针对Z-MHTR等多径路由算法存在的路径间干扰和源节点负载分配问题, 提出一种基于负载均衡的ZigBee多径路由算法— — Z-LBMR算法。为了减少路径间干扰造成大量数据的碰撞和重传, 该算法通过屏蔽干扰节点来建立非干扰路径。同时, 为了源节点负载流量的合理分配, 避免主路径的过早死亡, 提出基于路径性能指标值的负载分配机制, 延长了网络生存周期, 提高了网络的整体性能。
无线链路的性能是随时间不断变化的, 而且相互之间容易受到干扰。ZigBee使用直接序列扩频(DSSS)进行数据传输, 容易受消极多径的影响。如果不同路径上的两个节点在彼此的通信范围内(互为邻居节点), 两条路径上的数据传输就会发生无线干扰。路径间大量的无线干扰会很大程度地降低分组投递率, 增加节点的能量消耗, 降低信息安全性[14]。为了解决这一问题, 在主路径建立过程中, 将其中间节点的邻居节点设置为干扰节点。所谓干扰节点就是在已建立路径的中间节点的通信范围内(互为邻居节点)的节点。干扰节点将不能参与新的路径的建立。
在网络建立过程中, 节点都会建立一个邻居表, 保存其邻居节点的信息, 并对其进行动态维护, 每个节点收到数据包时, 都要更新维护邻居表。邻居表的结构如表1所示。
在邻居表中, 共定义了五个字段:Neighbor ID为邻居节点地址; Relationship type为节点之间的连接关系, 包括子节点、父节点或邻近节点; Inuse flag为使用标志位, 1表示邻居节点已经被其他路径使用, 不能被用来建立新的路径, 0表示此节点可以用于新的路径的建立; Interference flag为干扰标志位, 1表示此节点为干扰节点, 不能用于新的路径建立; Depth为节点网络深度, 其值应小于
如果任意两条路径之间既没有公共节点也没有互为邻居的节点, 则为非干扰路径。利用非干扰路径可以提升网络性能, 少数非干扰路径要比大量干扰路径带来更好的网络性能。为了建立非干扰路径, 本文在路径建立过程中引入干扰节点这一概念, 即将主路径中间节点的邻居节点标志为干扰节点, 干扰节点不能参与新的路径的建立过程。本算法的路径建立过程与Z-MHTR算法不同, 不是利用特定拓扑结构的ZTP信息来建立节点不相交的路径。具体的多路径建立过程如下:
Step1 源节点按树路由发送ID=1寻路数据分组(寻路数据分组前面加一标志位ID, 用来标识不同路径), 同时向周围节点发布自己已参与路径的信息。
Step2 节点收到邻居节点参与路径的通知信息, 将邻居表中对应的标志位Inuse置为1, 并同时向邻居节点发送自己为干扰节点的信息。节点收到邻居节点干扰的通知信息后将邻居表中对应的干扰标志位Interference置为1。
Step3 当源节点收到Sink节点对主路径的确认消息后, 主路径建立完毕。此时源节点向邻居表中Inuse=0的邻居节点发送不同ID号(2, 3…)的寻路数据分组, 建立从路径。
Step4 从路径建立过程中, 节点选择邻居表中Inuse与Interference标志位都为0且网络深度最小的节点为下一跳节点。
Step5 当一个节点收到相同ID号的寻路数据分组时, 舍弃后到达的数据分组, 不进行转发。
Step6 当寻路数据分组成功到达Sink节点, Sink节点原路返回确认信息, 从路径建立完毕。
例子:网络拓扑结构如图3所示, 其中网络参数为(Lm,Cm,Rm)=(7,4,4)。源节点S需要向Sink节点D发送数据。首先按树路由策略建立一条主路径
源节点负载的合理分配可以避免主路径因为过度使用而过早失效, 使网络资源得到更高效的利用。要在源节点运行一个适当的负载均衡算法, 每条路径的链路质量、时延、剩余能量等信息必须是已知的。当Sink节点接收到源节点发送的信息后会回复一个ACK确认信息, 这个ACK包可以包含本文所需要的信息。当路径建立完毕, 并返回ACK确认信息后。源节点可以获得各路径性能指标的相关信息, 然后根据这些信息计算在各条路径上进行数据转发的比率, 完成负载分配。为了减少源节点计算和负载重新分配的开销, 只有当它们与最后的更新值相比变化超过10%时, ACK包才会被用来传播这些更新后的值。假设源节点收到来自第
式中:
根据计算得到的每条路径质量对源节点的流量负载进行合理的分配,
最后, 源节点根据每条路径的数据转发比率
采用NS2仿真软件, 利用IEEE 802.15.4的PHY层和MAC层, 实现了网络层路由协议的仿真。协调器节点位于网络中心, 网络中其他节点随机分布在协调器周围。将Z-LBMR算法、Z-MHTR算法以及TR算法在相同的仿真环境下, 分别在流量负载为1~100 packet/s的不同场景下进行分组投递率、平均端到端时延、网络生存周期及吞吐量等指标的仿真比较。所有仿真数据都是在网络独立运行20次后取平均值, 其他仿真参数如表2所示。
分组投递率是目的节点接收到的数据分组个数与源节点发送的据分组个数的比值, 用来衡量一个网络传输的可靠性。图4为Z-LBMR算法、Z-MHTR算法和TR算法分组投递率的比较, 可以发现, 当流量负载为1~20 packet/s时, 都能够很好地处理流量负载。然而随着流量负载的增加, 几种算法的分组投递率都在减小。这是由于信道上碰撞数的增加和数据包的队列长度超出容量阈值, 造成数据包的丢失。当流量负载超过20 packet/s时, 多径路由要优于单径路由, 主要是因为单一路径带宽容量不足以支持这样的流量负载, 且单一路径拥有更高的路径内碰撞和干扰。同时由于Z-LBMR算法路径建立过程中减少了路径间干扰, 所以其性能要优于Z-MHTR算法。
端到端时延为数据包从离开源点直到抵达终点时一共经历的时间。图5为Z-LBMR算法、Z-MHTR算法和TR算法平均端到端时延的比较。当流量负载较小时, 由于单一路径的平均跳数要低于多路径, 所以其时延相对较小。随着流量负载的增加, 多径和单径的平均端到端延迟都大大增加, 但是单路径的平均端到端时延要远远大于多径路由。这是因为流量负载的增加, 在源节点处将导致更多的排队时延。同时路径内和路径间干扰开始严重降低网络的性能。频繁的数据包冲突和干扰将导致数据包被重传, 增加数据传递时间。在多路径路由中, 数据分组被分配到多个节点不相交路径, 路径内部碰撞和干扰的数量减少, 导致较少的重传, 从而比单路径的端到端时延要小。同时Z-LBMR算法通过建立非干扰路径, 减少了因为路径间干扰而导致的分组碰撞, 更加减少数据分组的重传概率, 减小了平均端到端时延。
当网络中节点死亡导致Sink节点无法接收来自源节点的数据流量时, 网络瘫痪, 生命周期结束。图6为Z-LBMR算法、Z-MHTR算法和TR算法网络生存周期的比较。从图6中可以看出, 流量负载的增加会降低网络生存周期。对于单路径路由, 整个网络流量负载会仅沿一条路径传输, 当路径上第一个节点死亡时, Sink节点停止接收来自源节点的流量。在多路径路由中, 使用节点不相交路径, 网络总负载被分配到这些路径中, 从而可以减小单条路径的能量消耗, 延长网络的生存周期。当流量负载为1~20 packet/s时, 所有的路由技术的寿命大致相同。然而, 当流量负载超过20 packet/s, 更高量的数据分组在网络中传输, 这将带来更多的碰撞和干扰, 进而造成数据重传增加, 带来更多的能量消耗。而多路径路由可以享受多个路径的集成能力, 实现更长的网络寿命。同时Z-LBMR算法通过对每条路径质量进行分析, 进行合理的流量分配, 使得每条路径的能量消耗更加均匀, 可以更好地延长网络生存周期。所以当流量负载增加时, Z-LBMR算法要比Z-MHTR算法拥有更长的网络生存周期。
图7为Z-LBMR算法、Z-MHTR算法和TR算法吞吐量的比较。从图7中可以看出, 在吞吐量方面, Z-LBMR算法要优于Z-MHTR算法和TR算法。以分组投递率为QoS约束, 对网络的吞吐量进行分析。将分组投递率限制在96%, 单径TR算法路由的最大吞吐量为20.6 kbit/s, 多径Z-MHTR算法路由为41.5 kbit/s, 多径Z-LBMR算法路由为45.6 kbit/s。在满足一定链路服务质量的前提下, Z-LBMR算法可以提供更大的吞吐量, 一定程度上增加了网络带宽。
以M2M区域网络中ZigBee技术为切入点, 针对现有ZigBee多径路由算法的不足, 对其进行改进。优化了路径建立和选择机制, 减少了路径间干扰, 并综合考虑路径的LQI、延迟和剩余能量等性能指标对流量负载进行合理的分配。从仿真结果可以看出, 本文算法在保证数据传送成功率的同时, 有效地降低了网络开销, 减少了平均端到端时延, 增加了网络吞吐量, 延长了网络的生存周期, 从而达到提高整个ZigBee网络性能的目的。
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|