基于灰色关联的ZigBee网络混合路由算法

金 勇，徐仁发，舒 红

(1.重庆邮电大学 移动通信技术重点实验室，重庆 400065；2.重庆邮电大学 通信工程应用研究所，重庆 400065)



基于灰色关联的ZigBee网络混合路由算法

金 勇1，2，徐仁发1，舒 红1

(1.重庆邮电大学 移动通信技术重点实验室，重庆 400065；2.重庆邮电大学 通信工程应用研究所，重庆 400065)

ZigBee网络混合路由算法(ZigBee Routing，ZBR)中将源节点和目的节点之间的最小跳数作为唯一的路由度量因素。但随着节点能量消耗以及节点的频繁移动，ZBR算法的这一特性会造成网络间歇性连接，从而导致网络性能下降。提出一种选择最优分组转发路径的ZigBee网络混合路由算法(Grey Relational Algorithm based ZBR，GRA-ZBR)。GRA-ZBR算法在目的节点选择路径时引入灰色关联算法，综合考虑节点剩余能量、链路质量、节点剩余队列长度以及路径长度等因素。仿真结果表明，GRA-ZBR算法可以有效提高网络分组投递率，降低平均端到端时延。

ZigBee网络；路由算法；灰色关联；路径选择

ZigBee网络是一种采用ZigBee技术的无线传感网络，随着“物联网+”理论的提出，ZigBee网络受到越来越多的关注[1]。ZigBee网络由于具有低成本、低功耗、低复杂度、高容量等特点而被广泛应用于智能家居、工业监测、智能交通等领域[2]。

不可避免地，ZigBee网络也会受到某些因素限制，如节点能量、同频段其他无线通信技术干扰、网络拥塞等，如何提供较为可靠的数据分组传输成为了ZigBee网络近期亟待解决的问题[3]。许多学者针对这一问题做出了广泛研究。文献[4]从节点能量优化角度出发，在分簇机制基础上，提出一种ZigBee网络能量优化算法(Cluster Label based ZBR，CLZBR)，通过簇内节点路由信息共享的方式有效减少节点能量消耗，从而效提高了网络分组投递率。文献[5]提出一种能量有效跨层网络操作模型，该模型根据节点间相对位置关系调整节点的发送功率，从而控制节点能量消耗水平，避免网络因为节点能量消耗过快导致网络可靠性低的问题。文献[6]提出一种链路状态感知的ZigBee路由算法(Link State Aware-AOMDV Junior，S-AOMDVjr)。该算法选择链路状态最好的路径进行数据转发，可保证算法在恶劣环境下的可靠性。文献[7]证明了网络中链路质量好坏与节点间距离大小呈正相关性，可通过节点间距离大小粗略估计链路质量。文献[8]从网络拥塞程度出发，根据链路的连通率和拥塞程度选择最合适的路径转发数据分组，可以有效减少网络时延。

大量研究表明：数据分组转发路径的优劣在很大程度上决定了路由算法的好坏[3]。所以，本文主要从选择最优路径方向做出研究。

1 ZBR路由算法

ZBR路由算法根据节点是否具有路由能力而将节点划分为RN+和RN-两种[9]。该算法的基本思路如下：路由过程中，RN+节点可以使用AODVjr路由算法发起路由发现过程，RN-节点只能使用Cluster-Tree路由算法[10]。ZBR路由算法的工作流程如图1所示。

图1 ZBR路由算法流程图

一方面，AODVjr算法可以通过全网广播路由请求消息(RouteREQuest，RREQ)来寻找源节点和目的节点之间的最短路径；但另一方面，转发大量冗余RREQ消息会导致网络能量消耗过快、分组投递率下降等问题。而Cluster-Tree算法尽管复杂度较低，极易实现，存储空间需求小，路由开销和能量消耗均被控制在一定程度内。但随着网络节点数量和节点密度的增加，Cluster-Tree算法中节点能量消耗极度不均衡，协调器附近节点能量消耗程度远远大于其他节点。另外，由于Cluster-Tree算法中采用的路径并非源节点和目的节点之间的最短路径，所以数据分组的传输时延较大。相较AODVjr算法和Cluster-Tree算法而言，ZBR路由算法在一定程度上缓解了AODVjr算法和Cluster-Tree算法存在的问题，所以，本文在ZBR算法基础上做出改进。

2 GRA-ZBR路由算法

2.1 灰色关联理论

灰色系统是由邓聚龙教授在20世纪80年代提出的科学理论[11]，其中，灰色关联分析算法根据各影响因子在发展过程中出现的相似或差异情况来描述它们之间的关联程度。本文采用灰色关联分析算法来分析目的节点接收到的各RREQ消息中携带的影响因子。目的节点选择灰色关联度最大的RREQ消息回复RREP消息，并将该RREQ消息转发路径作为数据分组转发路径。灰色关联分析算法主要步骤如下：

1)选择影响因子

ZBR路由算法将路径长度作为路径选择的唯一度量因素，这将导致网络性能随着时间推移而快速下降。本文在考虑路径长度因素的基础上，进一步将节点剩余能量、链路质量、节点剩余队列长度等作为影响评估因子。其中，链路质量反映出节点间距离大小，节点剩余队列长度反映出链路的拥塞程度。

2)RREQ消息处理

路由发现过程中，目的节点会接收到来自多个中间节点转发的RREQ分组。假设目的节点d接收到m条RREQ分组，则由这些RREQ分组组成的序列如

X=[x1,x2,x3,...,xm]

(1)

3)影响因子序列

RREQ分组由代表不同含义的字段组成，将代表特定影响因子的n个字段读取出来。由此生成影响因子序列，如

X=[xi(1),xi(2),xi(3),…,xi(n)],i=1,2,…,m

(2)

此外，X还可以写成矩阵形式，如

(3)

4)无量纲化处理

根据各影响因子对路径好坏的正相关性和负相关性，将影响因子分成效益型因子(剩余能量、链路质量、剩余队列长度)和成本型因子(路径长度)。效益型因子和成本型因子的处理方式[12]为

k=1,2,3,…,n

(4)

k=1,2,3,…,n

(5)

5)参考序列

为了更准确地反映出各RREQ消息的优劣程度，本文根据实时网络状况设定最优、最差两个参考序列，分别如

2,…,m

(6)

2,…,m

(7)

6)灰色关联系数

影响评估因子的最优、最差灰色关联系数[12]的计算式如

(8)

(9)

式中：ξ为分辨系数，且有ξ=0.5。

7)灰色关联度

各条RREQ消息的最优、最差灰色关联度的计算式为

(10)

(11)

8)RREQ消息灰色关联度

各条RREQ消息的灰色关联度[12]的计算式为

(12)

GRA-ZBR算法实际上是将各条RREQ消息中的影响评估因子字段分别与最优、最差参考序列相比较，最终计算最优灰色关联度占灰色关联度总和的比重。所占比重越大，表明该条RREQ消息中影响评估因子与最优参考序列关联越大，该条RREQ消息的转发路径质量越好。

2.2 GRA-ZBR路由算法实现过程

与经典ZBR算法相比，GRA-ZBR算法主要对路由发现过程做出改进，如图2所示。

图2 GRA-ZBR算法流程图

GRA-ZBR路由算法主要步骤如下：

步骤1，有数据传输需求的节点首先查询自身路由表，若具有目的节点相关表项，则根据该目的路由表进行数据分组转发；否则，判断自身节点类型。

步骤2，若源节点为RN-节点，则使用Cluster-Tree路由算法转发数据分组；若源节点为RN+节点，则进入路由发现过程。

步骤3，将源节点的剩余能量、剩余队列长度、链路质量、路径跳数等信息添加到RREQ消息对应字段。

步骤4，中间节点接收到RREQ消息后，判断自身是否为目的节点：若当前节点为中间节点，则更新RREQ消息中对应字段，将新的RREQ消息向周围节点转发出去。根据木桶原理可知，通信链路性能取决于最差的因素，所以，剩余能量、剩余队列长度以及链路质量字段更新方式如下：将当前节点对应影响因子数值与RREQ消息中对应字段数值作比较，它们中的较小值成为新的RREQ消息中对应的字段数值。另外，每经过一个中间节点，路径跳数字段的数值加1。

步骤5，目的节点接收到RREQ消息后不会直接回复RREQ消息，而是启动定时器。通过灰色关联分析算法计算在定时器时间段内接收到的各条RREQ消息的灰色关联度，其中，不同的影响因素对路径好坏影响程度不同。由于节点剩余能量因素不仅反映了路径的稳定性，还与路径长度因素一起影响着网络整体生存时间。因此，为节点能量分配的权值最重，ρk为0.4。针对节点频繁移动的场景，若在路径选择时考虑LQI因素，则可以有效延长路由有效时间。所以，LQI因素的权重设置为0.3。其余两个影响因素的权值均设为0.15。为了简化算法复杂度，在网络运行期间，上述影响因子权重固定不变。

步骤6，目的节点选择灰色关联度最大的RREQ消息回复RREP消息。

步骤7，源节点接收到RREP消息后，建立源节点和目的节点之间数据分组转发路径。

3 仿真分析

为了验证GRA-ZBR算法的性能，本文采用NS2.35+Cygwin软件平台，在IEEE 802.15.4PHY层和MAC基础上来实现网络层的仿真。本文将GRA-ZBR算法与ZigBee网络经典路由算法AODVjr和ZBR在不同节点数量、不同移动速率等场景下进行仿真实验，性能指标包括分组投递率和平均端到端时延。所有仿真结果都是网络独立运行50次后取得的算术平均值。实验过程中所有节点随机分布，数据分组最大联机数为10个，平均发包率为1 packet/s，其余参数设置如表1所示。

表1 仿真参数设置

3.1 分组投递率

图3为最大移动速率设置为6 m/s时，3种算法在不同节点数量场景下的分组投递率比较，可以发现，随着网络规模逐渐加大，网络中的冗余RREQ消息增多，网络拥堵现象越来越频繁，所以3种算法的分组投递率都有所降低。但由于GRA-ZBR算法在选择路径时考虑到节点剩余队列长度这一因素，有效避免选择堵塞节点作为数据分组转发的中间节点，在一定程度上缓解了网络拥堵问题，所以性能优于AODVjr算法和ZBR算法。

图3 不同节点数量下的分组投递率

图4为节点数量固定在80时，3种算法在不同节点最大移动速率场景下的分组投递率比较情况。随着节点移动速率加快，通信链路质量变差，网络逐渐出现间歇性连接，3种算法的分组投递率曲线均呈下降趋势。对于只考虑路径跳数的AODVjr算法和ZBR算法而言，分组投递率下降速率随着节点移动速率而增加。但由于GRA-ZBR算法在路径选择时添加了路径质量这一度量因素，转发数据分组使用的链路不易断裂，所以，分组投递率下降趋势较为平缓。

图4 不同最大移动速率下的分组投递率

3.2 平均端到端时延

图5为最大移动速率设置为6 m/s时，3种算法在不同节点数量场景下的平均端到端时延比较，可见，随着网络节点数量的增加，网络拥塞情况日益严重，数据分组在排队等待阶段花费的时间越多，3种算法的平均端到端时延均呈上升趋势。尽管AODVjr算法可以选择源节点与目的节点之间的最短路径转发数据分组，但AODVjr算法在网络拥塞情况较为严重。而GRA-ZBR算法在考虑路径长度基础上，避免选择拥塞情况较为严重的节点作为中间节点，所以性能优于其他算法。

图5 不同节点数量下的端到端时延

图6为节点数量固定在80时，3种算法在不同节点最大移动速率场景下的平均端到端时延比较结果，随着网络中节点移动性增强，转发路径上的通信链路逐渐开始断裂，越来越多的数据分组需要重新寻找转发路径，所以3种算法的平均端到端时延越来越大。但是由于GRA-ZBR算法在路径选择时选择链路质量作为路由度量因素，有效降低了中间链路发生断裂的可能性，所以GRA-ZBR算法的性能优于AODVjr算法和ZBR算法。

图6 不同最大移动速率下的端到端时延

4 小结

节点移动特性逐渐成为ZigBee网络路由算法设计的一大挑战，而经典ZigBee网络ZBR路由算法仅以路径长度作为路径选择依据，未考虑实时网络链路状态，从而导致网络性能下降。本文针对这一问题，提出一种基于灰色关联的ZigBee网络混合路由算法GRA-ZBR，该算法根据链路实时能量水平、拥塞程度、链路质量以及路径长度作为路由度量依据，选择最佳路径进行数据传输。仿真结果证明，GRA-ZBR算法在较大网络规模和移动速率的复杂场景下，仍然能将分组投递率和端到端时延等性能指标控制在可接受范围内，验证了GRA-ZBR算法的有效性。但由于GRA-ZBR算法在RREQ消息中增加了3个字段，所以，系统控制开销会稍高于原ZBR算法。

[1]任智，李鹏翔.基于分段的ZigBee网络按需可扩展地址分配算法[J].通信学报，2012，33(5)：131-137.

[2]白乐强，王玉涛，孙晶晶.基于邻居表的能量均衡ZigBee树路由改进算法[J].计算机工程与设计，2015，36(12)：3204-3208.

[3]韩挺.基于信任理论的路由协议安全技术研究[D].北京：北京邮电大学，2015.

[4]钱志鸿，朱爽，王雪.基于分簇机制的ZigBee混合路由能量优化算法[J].计算机学报，2013，36(3)：485-493.

[5]AL-JEMELI M，HUSSIN F A. An energy efficient cross-layer network operation model for IEEE 802.15.4-based mobile wireless sensor networks[J].IEEE sensors journal，2014，15(2)：

[6]谢忠明，何华冰，李云飞.一种基于链路状态感知的Zigbee多径路由算法[J].微电子学与计算机，2015，32(9)：65-75.

[7]GOMEZ C，BOIX A，PARADELLS J. Impact of LQI-based routing metrics on the performance of a one-to-one routing protocol for IEEE 802.15.4 multihop networks[J].Eurasip journal on wireless communications & networking，2010，4(2)：50-50.

[8]SECCI L，BURATTI C. Reducing traffic congestion in ZigBee networks：experimental results[C]//2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC).Sardinia：IEEE，2013：627-632.

[9]ICHIHARA T，MITANI T，SHINOHARA N. Study and development of an intermittent microwave power transmission system for a ZigBee device[C]//2014 IEEE Wireless Power Transfer Conference (WPTC). Jeju：IEEE，2014：40-43.

[10]MURUGAN T S. Shortest energy based optimal route in zigbee mesh network[J]. International journal of applied engineering research，2015，10(15)：35258-35260.

[11]宋倩倩，王宏刚，卢光跃.基于灰色关联度的Leach算法的改进[J].电视技术，2015，39(3)：144-147.

[12]邓聚龙.灰色控制系统[M].武汉：华中理工大学出版社，1995.

金 勇(1974— )，硕士生导师，主要研究方向为移动通信网络规划与优化等；

徐仁发(1989— )，硕士生，主研物联网、无线传感网络等；

舒 红(1991— )，女，硕士生，主研无线传感网络、移动通信技术等。

责任编辑：许 盈

Hybrid routing algorithm based on grey relational algorithm in ZigBee network

JIN Yong1,2,XU Renfa1,SHU Hong1

(1.ChongqingKeyLabofMobileCommunicationsTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China；2.CommunicationEngineeringApplicationResearchInstitute,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

The hop-count between the source node and the destination node is the only routing metric in ZigBee network hybrid routing algorithm (ZigBee Routing, ZBR). However, this property of the algorithm leads to the intermittent connectivity of the network, with the energy consumption of nodes and the frequent mobility of nodes. As a result, the performance of the ZigBee network degrades. In this paper, a grey relational algorithm is proposed based on ZigBee network hybrid routing algorithm (Grey Relational Algorithm based ZBR, GRA-ZBR), which can select the best path between the source node and the destination node. At first, GRA-ZBR takes various factors, including the residual energy, link quality, the remaining queue length and hop-count, into consideration. Then, the best path is selected via grey relational algorithm. Experimental results show that GRA-ZBR can improve the network packet delivery ratio and reduce the average end-to-end delay, effectively.

ZigBee network; routing algorithm; grey relational; path selection

金勇，徐仁发，舒红.基于灰色关联的ZigBee网络混合路由算法[J].电视技术，2016，40(11)：70-74. JIN Y，XU R F，SHU H.Hybrid routing algorithm based on grey relational algorithm in ZigBee network[J].Video engineering，2016，40(11)：70-74.

TN949.6

A

10.16280/j.videoe.2016.11.015

长江学者和创新团队发展计划(1RT1299);重庆市科委项目(CSTC2012JJA40044;CSTC2013YYKFA40010)

2016-03-01