基于服务质量的层次化结构资源分配算法

2022-02-12丁铖陈锦荣曹小冬王翊

电信科学 2022年1期

关键词：层次化资源分配备份

丁铖，陈锦荣，曹小冬，王翊

研究与开发

基于服务质量的层次化结构资源分配算法

丁铖，陈锦荣，曹小冬，王翊

（中国南方电网有限责任公司广东电网公司佛山供电局，广东佛山 528010）

无线传感器网络（wireless sensor network，WSN）具有节点体积小、成本低、感知能力强等优势，被广泛应用于物联网（internet of things，IoT）场景中。如何在保证WSN负载平衡的前提下，提高业务服务质量（quality of service，QoS）成为众多学者关注的问题。在研究WSN中基于启发式的资源分配方法和基于层次化结构的资源分配方法基础上，提出了一种基于服务质量的层次化结构资源分配算法（quality of service based hierarchical resource allocation algorithm，QoSHRA）。首先，利用基于低能耗自适应聚类层次（low-energy adaptive clustering hierarchy，LEACH）协议的资源分配方法使整个网络形成层次化结构；然后，利用QoSHRA进行资源分配。仿真结果表明，QoSHRA在保证网络负载平衡的前提下，进一步节约了网络传输能耗，保障了业务分配的有效性，提高了网络资源的QoS需求满足率。

物联网；无线传感器网络；服务质量；资源分配方法

0 引言

物联网（internet of things，IoT）是将各种信息传感设备与互联网结合在一起的网络。作为21世纪初革命性的技术之一，它在现代无线电信场景中正迅速普及。无线传感器网络（wireless sensor network，WSN）具有节点体积小、成本低、感知能力强等优点，被广泛应用于IoT的各个领域中，是IoT的核心技术之一。在电力行业中，WSN在输电线路在线监测、配电网络智能抄表等方面作用突出，具有较强的研究价值。

由于传感器节点能量、数据处理能力及数据传输能力有限，如何高效利用WSN，平衡网络负载，成为IoT资源分配方式领域的主要研究点。传统的资源分配算法主要包含两种类型，一种是启发式算法，如基于蚁群的资源分配算法，通过建立能耗模型，将能量均衡因素加入概率转移、信息素更新等公式模型中，提高节点能量使用效率，达到平衡网络负载的目的；另一种是分层算法，如基于低能耗自适应聚类层次（low-energy adaptive clustering hierarchy，LEACH）协议的资源分配算法，通过选择合适的节点成为资源分配节点，并形成层次化结构，利用动态分层的方式，达到有效利用节点能量、平衡网络能耗的目的。然而，人们对WSN性能的要求远不止如此。以输电线路场景为例，面向输电线路在线监测的WSN具有监测业务多样、业务重要程度不同的特点，所以设计一种针对多业务场景的、能满足重要业务服务质量（quality of service，QoS）需求的WSN资源分配方法至关重要。

目前在面向QoS的WSN资源分配算法方面的研究主要有：

● 文献[10]提出了基于动态马尔可夫链的资源分配方案，将物联网中的业务流量分为优先级和非优先级，用于确保延迟敏感流量的QoS；

● 文献[11]提出了基于业务优先级的资源分配方案，通过改进Dijkstra算法将业务分为高优先级和低优先级，建立负载均衡模型，在保证高优先级业务QoS的前提下，使整个网络负载均衡；

● 文献[12]针对物联网技术中的传统资源分配方法节点能耗差异大、业务分配灵活性不足的问题，提出了一种基于能耗的启发式分层算法和一种基于业务优先级的层次化结构资源分配算法，将业务时延作为QoS的主要依据，为不同业务分配满足时延需求的传输路径，同时节约传输能耗，保证网络负载均衡，该算法的设计理念与本文提出的资源分配算法有一些相似之处。

综上所述，本文提出一种基于服务质量的层次化结构资源分配算法（quality of service based hierarchical resource allocation algorithm，QoSHRA）。

1 系统模型与算法研究

1.1 系统模型

1.1.1 拓扑模型

基于服务质量的层次化结构资源分配模型如图1所示，物联网主要由感知层、网络层、应用层组成。感知层主要用于感知各种信息并汇聚给网络层；网络层主要利用互联网将来自感知层的数据统一存储并管理；应用层主要是将网络层的数据处理后应用于IoT各个领域。本文重点研究物联网感知层的资源分配协议，物联网感知层主要由4部分组成：感知节点、资源分配节点、备份节点和网关节点。感知节点用于信息采集，并将信息发送给资源分配节点；资源分配节点用于收集感知节点及相邻资源分配节点发送的信息并对信息按相关资源分配协议进行信息转发；备份节点用于备份每个层次化结构内的资源分配节点，如果资源分配节点失效，则备份节点代替资源分配节点进行信息收集和转发；网关节点用于收集感知网络的信息，所有感知节点采集的信息最终都汇聚至网关节点。

图1　基于服务质量的层次化结构资源分配模型

由图1可以看出，本文的资源分配算法是一种基于层次化结构的资源分配算法。根据基于LEACH协议的资源分配算法形成层次化结构后，每个资源分配节点会根据收集到的各个业务数据QoS要求不同而规划相匹配的路径进行信息传输。除此之外，备份节点会替代失效的资源分配节点进行信息传输，从而进一步保障业务QoS需求并优化网络能耗。

本文算法基于监测业务多样、感知节点能量有限的场景特征，并做出如下假设：

● 所有传感器都是静止的，不同监测业务的QoS要求不同，但数据大小基本一致；

● 所有传感器都知道自己的剩余能量，并根据通信距离调整传输功率；

● 链路是对称的，无线电信号在所有方向上具有相同的能量衰减；

● 所有传感器都能够在资源分配模式和信息感知模式下运行。

1.1.2 能量模型

假设两个距离为的节点之间传输bit数据时，发送端所消耗的能量sc为：

定义为两节点之间的欧氏距离，即：

节点接收bit所消耗的能量为：

其中，rc为接收数据需要的能量。

因此，如果整个网络共有个节点，则总能耗tc为：

其中，n*为节点向节点发送数据的过程中由于链路故障而使数据丢失的数量。

1.1.3 QoS要求

假设整个网络中有多种资源，每种资源的QoS要求主要由时延要求衡量，端到端的总时延主要包括传输时延、处理时延和排队时延，将第种资源记为S，其时延要求为cst，则资源分配节点从收集数据到数据传输至网关节点所用时间S应满足Scst。

假设资源分配节点对同种资源处理的QoS需求为常数，并假设资源在各个分配节点的排队时间相等且为常数，考虑到资源的传输速度值远大于距离值，则本文将忽略传输时延，将各个资源的QoS需求=que+pro设置为定值，其中，que、pro分别为同种资源的排队时延和处理时延。因此，本文将各个资源的QoS约束转换为跳数约束如式（9）所示。

1.2 算法研究

1.2.1 算法分析

（1）基于QoS分析与负载均衡的资源分配机制

本文设计的资源分配机制基于QoS分析。在每一轮的数据传输阶段，资源分配节点同时接收分层结构内节点数据及相邻资源分配节点的转发数据。假设每个业务资源都具有QoS要求，在分配资源过程中，每个资源分配节点利用Dijkstra算法计算到网关节点的最短距离；然后，对优先级最高的资源选择与之相对应的最优路由进行资源分配，并标记该路径；进而，考虑次优先级资源，在满足QoS要求的情况下，优先在未被标记的节点中选择与最优路由进行资源分配并同样对该路径进行标记，如果没有满足QoS要求的路径，则分配最短路径给该资源；最后，重复上述过程，直至所有资源被分配完毕。

1）基于数据有效率和QoS的路由排序机制

该机制首先根据以往数据传输是否满足QoS需求确定规划路径的数据有效率，综合考虑路径长度和数据有效率确定路由质量，并最终对路由表排序。

假设每个资源分配节点每次转发数据给相邻分配节点后，该分配节点对相邻分配节点的转发计数加1，转发计数用Cs表示（初始化为1），如果该转发数据在满足QoS需求的前提下到达网关节点，该分配节点对相邻分配头节点的接收计数加1，接收计数用Cr表示（初始化为1），则规划路径的数据有效率Eff为：

其中，表示发送数据的资源分配节点，表示接收数据的相邻资源分配节点。

在形成层次化结构后，每个资源分配节点利用Dijkstra算法初始化到网关节点的距离用Len表示，则路由质量评价式RQ为：

其中，表示发送数据的资源分配节点，表示接收数据的相邻资源分配节点，表示规划路径的数据有效率系数，表示路由长度倒数的系数。

2）基于QoS的资源排序机制

依据QoS要求制定优先级hc；每经过一个资源分配节点，更新优先级hc。

本文假设每个业务都具有一个基本QoS需求和最低QoS需求，基本QoS需求用hc表示，最低QoS需求用hc表示。初始化数据包的优先级为：

则经过hc跳后，该数据包的优先级为：

（2）基于能耗的资源分配节点故障备份机制

考虑到非资源分配节点的故障备份需求不高，为了优化节点能耗，本文算法只保证资源分配节点的有效性。备份节点与资源分配节点之间周期性地进行故障检测以确定对方节点是否失效。

1）基于信息协商传感协议的故障定位机制

在资源分配节点进行信息转发的过程中，本文参考了一种基于传感器信息协商协议（sensor protocols for information via negotiation，SPIN）的故障诊断机制，并对该机制进行了改进。本文的故障诊断机制主要使用检测（CHECK）信息、认证（VERIFY）信息两种类型的信息。

步骤1 每个分层结构中，资源分配节点或备份节点周期性向对方发送CHECK信息。

步骤2 如果目的节点正常，在接收到CHECK信息后，回复VERIFY信息给CHECK信息发送节点；否则，如果CHECK信息发送节点在一定时间内未收到相应的VERIFY信息，则认为对方节点发生故障，启动故障节点备份机制。

步骤3 CHECK信息发送节点在收到相应的VERIFY信息后，确认对方节点未失效，本次故障诊断过程结束。

2）基于能耗的备份节点选择机制

在网络形成分层结构后，建立备份节点选择模型，利用该模型选出资源分配节点的备份节点。资源分配节点周期性地与备份节点同步路由信息。备份节点选择模型如下：

其中，为节点ID，1、2、3、4分别为节点与分层结构内其他节点的距离系数、节点与分层结构内资源分配节点的距离系数、节点与网关节点的距离系数以及节点剩余能量系数，ave-node为分层结构内节点与其他节点的平均距离，allot为分层结构内其他节点到资源分配节点的距离，sink为节点到网关节点的距离，remain为节点的剩余能量。

本文假设每个分层结构内有个节点，资源分配节点为0节点，则第个节点的ave-node可表示为：

其中，为两点之间的距离。则ave-node的平均数`ave-node可表示为：

则allot的平均数`allot可表示为：

则每个分层结构内非资源分配节点到网关节点距离的平均数`sink可表示为：

则每个分层结构内非资源分配节点的平均剩余能量`remain可表示为：

1.2.2 算法设计

（1）基于QoS分析与负载均衡的资源分配机制

在利用基于LEACH协议的资源分配算法形成层次化结构后，本文提出了一种基于QoS分析与负载均衡的资源分配机制。该机制首先对可分配资源的传输路径进行链路质量评估，然后根据业务QoS要求对业务数据排序，最终选择与业务QoS要求匹配的路径进行数据传输，保障业务的QoS需求并进一步优化节点能耗。基于QoS分析与负载均衡的资源分配机制流程如图2所示。

图2　基于QoS分析与负载均衡的资源分配机制流程

（2）基于能耗的资源分配节点故障备份机制

为了减小失效节点对资源分配可靠性的影响，提高数据传输质量，本文提出了一种基于能耗的资源分配节点故障备份机制。通过考虑层次化结构内节点的剩余能量、传输能耗、地理位置等因素，该机制建立基于能耗的备份节点选择机制，挑选出每个层次化结构内的备份节点。当资源分配节点失效或备份节点失效时，基于SPIN的故障诊断机制可以保证触发资源分配节点故障备份机制，从而维护整个网络的正常运转。基于能耗的资源分配节点故障备份机制流程如图3所示。

2 仿真实验与分析

2.1 仿真环境设置

本文模拟物联网下的长链状拓扑、多业务并存的场景结构，基于MATLAB仿真以验证QoSHRA的有效性。

2.2 仿真参数设置

仿真参数设置见表1。

图3　基于能耗的资源分配节点故障备份机制流程

表1　仿真参数设置

2.3 仿真实验

本文对文献[12]提出的基于时延和负载均衡的面向输电线路物联感知与监测应用的层次化结构路由规划方法（delay and load-balancing based hierarchical route planning method for transmission line IoT sensing and monitoring applications，DLHRP）、基于蚁群的资源分配算法和本文所提出的QoSHRA分别进行仿真实验。由于DLHRP的分层机制也是一种基于LEACH协议的资源分配机制，所以为了方便对比，在仿真时，使用DLHRP的分层机制形成层次化结构后，执行这3种资源分配算法。

QoSHRA是一种基于层次化结构的资源分配算法，本文记录了每次形成分层结构后网络节点的失效情况。在仿真时，记录3种算法的节点失效情况，不同资源分配算法的节点失效情况如图4所示。

对能量为0或发生故障的节点数量进行统计。基于蚁群的资源分配算法和DLHRP的失效节点数都存在波动，这是因为这两种算法未考虑资源分配节点失效情况，当资源分配节点失效时，该层次化结构内的所有节点数据都无法传输至网关节点，而本文算法具有故障备份机制，可以保证资源分配节点的有效性。本文提出的QoSHRA失效节点数明显小于另外两种算法，这是因为本文算法是一种基于业务优先级的资源分配方法，可以在为不同资源分配路径的同时，考虑整个网络的能耗状况，与DLHRP相比，QoSHRA通过建立链路质量模型和业务优先级模型，能够在保证网络QoS的前提下，进一步优化网络能耗。

图4　不同资源分配算法的节点失效情况

为了直观地看出3种资源分配算法下的网络节点能量均衡情况，记录了3种算法的有效节点剩余能量标准差，不同资源分配算法的有效节点剩余能量标准差如图5所示。

图5　不同资源分配算法的有效节点剩余能量标准差

与蚁群算法相比，本文所提出的QoSHRA和DLHRP都能使整个网络节点具有更小的能量差异，这是因为QoSHRA和DLHRP在进行资源分配的时候，会考虑每个节点的负载情况，使业务更加均衡地分配给每个相邻资源分配节点传输。与DLHRP相比，本文算法通过建立链路质量模型和业务优先级模型，使资源分配更加高效，通过建立故障备份机制，减少了失效节点数量，进一步均衡网络能耗。

与DLHRP相比，本文所提出的QoSHRA在进行路由规划时对链路质量进行了分析，同时，为保证业务资源能够有效传输至网关节点，本文提出了一种基于能耗的资源分配节点故障备份机制。为了突出本文算法在保障业务QoS需求方面的优越性，对每次形成分层结构后各个业务的QoS满足率进行了统计，业务QoS需求满足率如图6所示。

图6　业务QoS需求满足率

图6中，本文所提出QoSHRA的业务QoS需求满足率明显高于DLHRP，这是因为本文算法的资源分配节点在进行路径规划的时候考虑了链路质量，对业务资源优先选择高QoS保障的路径进行传输。除此之外，本文所提出的故障备份机制保障了每个资源分配节点的有效性，降低了节点失效率，提高了整个网络的QoS。

3 结束语

为了提高面向多业务场景的WSN的QoS，更有效地利用有限的能源资源，本文提出了QoSHRA。该算法主要包含基于QoS分析与负载均衡的资源分配机制和基于能耗的资源分配节点故障备份机制两个子机制。通过建立基于QoS分析与负载均衡的资源分配机制，资源分配节点能够为不同QoS需求的业务分配与其匹配的传输路径，从而提高整个网络的QoS，节约传输能耗、平衡网络负载；通过建立基于能耗的资源分配节点故障备份机制，为每个资源分配节点选出合理的备份，从而保证资源分配节点的有效性，提高路由质量。仿真结果显示，与基于蚁群的资源分配算法相比，QoSHRA可以平衡网络负载，节约网络传输能耗；与DLHRP相比，QoSHRA可以进一步节约网络传输能耗，保障业务分配的有效性，提高网络的QoS需求满足率。

[1] PORTILLA J, MUJICA G, LEE J S, et al. The extreme edge at the bottom of the internet of things: a review[J]. IEEE Sensors Journal, 2019, 19(9): 3179-3190.

[2] ATZORI L, IERA A, MORABITO G. The internet of things: a survey[J]. Computer Networks, 2010, 54(15): 2787-2805.

[3] Attia T M. Challenges and opportunities in the future applications of IoT technology[C]//Proceedings of 2nd Europe-Middle East-North African Regional ITS Conference. New York: International Telecommunications Society (ITS), 2019: 52.

[4] XU N. A survey of sensor network applications[J]. Ad Hoc & Sensor Wireless Networks, 2002, 25(1): 1-44.

[5] GAUTAM P R, KUMAR S, VERMA A, et al. Energy-efficient localisation of sensor nodes in WSNs using single beacon node[J]. IET Communications, 2020, 14(9): 1459-1466.

[6] XUE J B, ZHANG T, WANG W H. A routing algorithm based on high energy efficiency in cooperation WSN[M]//Lecture Notes in Electrical Engineering. London: Springer London, 2013: 129-136.

[7] BEIRANVAND Z, PATOOGHY A, FAZELI M. I-LEACH: an efficient routing algorithm to improve performance & to reduce energy consumption in Wireless Sensor Networks[C]//Proceedings of 5th Conference on Information and Knowledge Technology. Piscataway: IEEE Press, 2013: 13-18.

[8] KONG P Y, LIU C W, JIANG J A. Cost-efficient placement of communication connections for transmission line monitoring[J]. IEEE Transactions on Industrial Electronics, 2017, 64(5): 4058-4067.

[9] DU L, WANG C S, LI X Z, et al. A novel power supply of online monitoring systems for power transmission lines[J]. IEEE Transactions on Industrial Electronics, 2010, 57(8): 2889-2895.

[10] SHARMA R, KUMAR N. QoS-alert Markov chain based scheduling scheme in Internet of Things[C]//Proceedings of 2015 IEEE Globecom Workshops (GC Wkshps). Piscataway: IEEE Press, 2015: 1-6.

[11] LI P, XU S Y, SUN K, et al. A path planning method of wireless sensor networks based on service priority[C]// Proceedings of 2017 13th International Conference on Network and Service Management (CNSM). Piscataway: IEEE Press, 2017: 1-4.

[12] DING C, XU S Y, CHEN X Y, et al. A delay and Load-balancing based hierarchical route planning method for transmission line IoT sensing and monitoring applications[C]// Proceedings of 2019 IFIP/IEEE Symposium on Integrated Network and Service Management (IM). Piscataway: IEEE Press, 2019: 207-215.

[13] 陆俊, 朱炎平, 徐志强, 等. 面向输电线路监测的无线传感网络可靠路由方法研究[J]. 电网技术, 2017, 41(2): 644-650.

LU J, ZHU Y P, XU Z Q, et al. A reliable wireless sensor network routing method for power transmission line monitoring[J]. Power System Technology, 2017, 41(2): 644-650.

[14] 吕涛. 无线传感器网络分簇路由协议及其应用研究[D]. 成都: 电子科技大学, 2013.

LÜ T. Research on cluster-based routing protocol and its application for wireless sensor networks[D]. Chengdu: University of Electronic Science and Technology of China, 2013.

[15] 罗杰. 输电线路状态监测中的无线传感器网络时延研究[D]. 长沙: 湖南大学, 2014.

LUO J. Research on delay of wireless sensor network in transmission line condition monitoring[D]. Changsha: Hunan University, 2014.

[16] KUMAR DEVA SARMA H, RAI P, DEKA B. Energy efficient communication protocol for wireless sensor networks with mobile node[C]//Proceedings of International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014). Piscataway: IEEE Press, 2014: 1-6.

[17] PAUL A K, SATO T. Effective data gathering and energy efficient communication protocol in wireless sensor network[C]//Proceedings of 2011 The 14th International Symposium on Wireless Personal Multimedia Communications (WPMC). Piscataway: IEEE Press, 2011: 1-5.

[18] ZHU H, LI Q S, SHAO M C, et al. A Load-balancing and Fault-tolerant based route planning algorithm for wireless sensor networks[C]//Proceedings of 2018 IEEE International Conference on Electronics and Communication Engineering (ICECE). Piscataway: IEEE Press, 2018: 81-85.

Quality of service based hierarchical resource allocation algorithm

DING Cheng, CHEN Jinrong, CAO Xiaodong, WANG Yi

Foshan Power Supply Bureau of China Southern Power Grid Co., Ltd., Foshan 528010, China

Wireless sensor network (WSN) is widely used in the internet of things (IoT) scene because of its small size, low cost and strong sensing ability. How to improve the quality of service (QoS) under the premise of load balancing in WSN has become the focus of many scholars. Based on the study of heuristic resource allocation method and hierarchical structure resource allocation method in WSN, a quality of service based hierarchical resource allocation algorithm (QoSHRA) was proposed. Firstly, the resource allocation method based on low energy adaptive clustering hierarchy (LEACH) made the whole network form a hierarchical structure. Then, QoSHRA was used for resource allocation. The simulation results show that QoSHRA can further save the energy consumption of network transmission, ensure the effectiveness of service allocation, and improve the satisfaction rate of network resource QoS requirements on the premise of ensuring network load balancing.

internet of things, wireless sensor network, quality of service, resource allocation method

TP393

10.11959/j.issn.1000−0801.2022005

2021−08−15；

2021−12−10

丁铖（1993−），男，中国南方电网有限责任公司广东电网公司佛山供电局助理工程师，主要研究方向为物联网与无线传感器网络。