基于业务质量的网络资源分配方法

朱红　韦磊　李秋生　邵明驰　蔺鹏

摘 要：为了高效利用无线传感器网络（WSN）能源资源，论文提出了一种基于业务质量的网络资源分配方法（SQNR）。该算法基于业务质量需求分析，以节约传输能耗为优化目标，为不同优先级的业务分配不同的傳输路径，从而节约传输能耗、优化网络资源效用。仿真结果表明，论文提出的方法能够在保证业务质量要求的条件下，优化网络运行，并延长网络的生命周期。

关键词：无线传感器网络；资源分配；业务质量；生命周期

中图分类号：TP393 文献标识码：A

1 引言

无线传感器网络（WSN）是由部署在监测区域内大量的微型传感器节点构成的多跳自组织网络。该网络利用传感器节点采用无线通信方式协作地实时监测、感知和采集各种对象信息，并对数据进行处理[1]。WSN已在电力系统中的电量检测、配电网继电保护、故障定位、设备状态检测、应对自然灾害等方面都有广泛应用。同时，结合能源互联网中大量有源与无源的无线传感器，WSN还可应用于高塔监测、发/用电信息实时采集、高空视频协作传输等。然而，在电力通信网中不同业务的传输质量要求具有较大差异性[2]。因此，研究能在保证多种业务不同质量要求的前提下，节约能耗并延长资源分配网络生命周期的方法具有重要意义。

针对资源分配问题已有较多研究成果。Salehpour等人提出了一种用于大规模聚类的无线传感器网络资源分配算法。该算法令簇内节点将数据直接发送至簇头节点，簇头节点使用蚁群优化算法规划通往基站的最佳路径。算法通过使用蚁群优化算法和分簇来最小化算法的延迟，最终达到降低功耗，平衡负载的目的[3]。

Xiao等人提出了一种基于简单人工鱼群优化和蚁群优化的无线传感器网络聚类资源分配算法。与以往基于蚁群的路由算法不同，该算法使簇头节点的选择要考虑备选节点的位置和所需簇头节点的数量。该算法进一步优化了数据传输过程的能耗并提升了整个网络的负载平衡性[4]。

Yao等人提出了一种基于低能量自适应聚类分层集中算法的聚类资源分配协议。该算法是对LEACH-C算法的改进，在簇间路由方面执行一种单跳与多跳相结合的算法，所有数据在距离汇聚节点小于一定阈值后，数据通过单跳传输至汇聚节点。该算法降低了汇聚节点附近簇头节点的通信负载，提升了整个通信网络的负载均衡程度[5]。

从Heinzelman等人提出了LEACH分层资源分配协议开始，许多学者开始研究并扩展优化该协议[6，7]。然而，过去的簇间资源分配算法都没有考虑到对分配业务进行区分，从而降低了数据传输的灵活性。

为解决以上问题，本文提出了一种基于业务质量的网络资源分配方法（Service Quality based Network Resource allocation method，，SQNR）。该方法通过对到达簇头节点的不同业务，根据其优先级分配不同的传输路径实现负载均衡。通过本文设计的算法，可以在各业务数据满足其时延要求的情况下，低级别的业务通过“绕远”传输至目的节点，防止网络拥堵，避免节点负载不均衡，从而减少失效节点的数量，以延长达网络生命周期。

2 系统模型

假设整个网络中有N个传感器节点，每个传感器节点位置都固定并具有一定的记录能力。每个节点具有位置和剩余能量两种属性。节点的位置用二维坐标表示为P（x， y）， 剩余能量用Elast表示。假设所有节点的业务信息最终都汇聚至汇聚节点，并且汇聚节点的被配置太阳能电板以及蓄电池，该节点能量不受限制。

算法为时延要求比较低的业务分配路径时，由于时延需求比较低，可以在满足时延约束的条件下通过牺牲时延来达到负载均衡，例如图1中从黑色路径转为白色路径，从而提高的网络节点的利用率并延长了网络的生命周期。

2.1 能耗模型

发送节点发送n-bits数据所需要的能耗是[8]：

（1）

接收节点接收n-bits数据所需要的能耗是：

（2）

Eelec为发射电路损耗的能量，其值取决于节点本身的物理属性。因此整个网络的总能耗为：

（3）

为节点i与它的下一跳j的欧式距离：

（4）

Index是距离指数，随通信距离的变化而变化：

（5）

dthreshold是d的阈值：

（6）

为多路径衰减信道模型的功率放大系数，为自由能量衰减模型功率放大系数。

为网络中所有节点的平均剩余能量：

（7）

2.2 业务质量约束

在本文中，业务质量即为业务数据传输的时延。假设整个网络中传输的业务有M种，分别记为{S1， S2， …SM}，它们的时延限制分别为并且他们的关系为。

不同的业务真实的端到端一定要小于等于时延限制。所以时延的约束条件应该是：

（8）

假设同种业务的数据包的排队时延和处理时延近似相等，而由于数据传输的距离相比于速度可以忽略不计，即Lave=Lqueue+Lprocess+Ltransmission是一个定值，Lqueue， Lprocess， Ltransmission分别为同种业务的排队时延，处理时延和传播时延，因此可以将时延约束转化为跳数约束：

（9）

2.3 基于时延的业务优先级划分

首先，在业务达到之前，根据业务的时延要求为业务制定初始优先级x。然后，在调度时，根据网络实时拥塞状况，考察各优先级类的平均排队时延，对当前优先级X进行实时计算，即对某些积压严重的优先级数据包暂时提高其优先级等级。

假设数据包的初始优先级为x，且该数据包满足时延要求满足，则该数据包当前优先级 的计算方法为：

（10）

其中，Lqueue是该数据包在某一调度时刻的排队时延。v是用于提升业务优先级的具体量化值。假设，当前业务数据包的时延要求不满足时，对该数据包的优先级提升v，使其满足时延要求。Ls为该业务对数据包时延L要求的标准值。p为对业务时延的评估值，其计算方式如下：

（11）

2.4 负载均衡约束

本文采用传感器节点剩余能量的标准差来衡量整个网络的负载均衡程度，即。本文假设，所有剩余能量不为0的节点标准差越小，整个网络的负载越均衡。簇头节点在进行资源分配时，总能在满足相应业务质量要求的情况下，尽可能的分配使整个网络负载均衡的路径。

当整个传感器网络完成一次数据传输过程（单位：跳），每个节点的剩余能量进行如下更新：

（12）

整个传感器网络节点能量的标准差应该低于执行本次数据转发后所有节点能量的标准差，即在执行本次数据转发后，标准差应满足如下条件：

（13）

3 算法设计

3.1 算法分析

Dijkstra算法思想：设G=（V，E）是一个带权有向图，分顶点集合V为两组，已求出最短路径的顶点集合为第一组（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 ， 就将其顶点加入到集合S中，直到全部顶点都加入到S中，算法就结束了），其余未确定最短路径的顶点集合为第二组（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

本文采用改进型的Dijkstra算法。假设网络有两种业务：1业务和2业务，业务1的时延需求高于2。仍然设置一个带权有向图G=（V，E），那么将网络中的节点集合V分为三组，V=（V1，V2，U）。已经求出来的最短路径的节点集合为第一组（用V1表示）；在求第一组的最短路径集合时，同时记录并排序其他路径的集合，该集合为第二组（用V2表示）；其余未确定最短路径的集合为第三组（用U表示）。在选择当前节点的下一跳时，1业务选择V1集合中的顶点，2业务也优先选择V1集合中的节点（恰好2业务选择的节点没有被1业务使用），同时判断是否满足负载均衡约束，如果满足，则继续进行下一跳，如果不满足，则从V2集合中选择最短的路径下一跳，同样判断是否满足负载均衡约束，满足选择下一跳，若不满足则从集合V2选择次短路径的下一跳，一直循环直到满足负载均衡条件。

簇头节点在进行数据转发时，根据业务优先级划分后的最高优先级业务选择最短路径进行转发，对于较低优先级业务的转发需要考虑负载均衡约束条件，如果选择的较短路径不满足负载均衡约束，则选择更长的路径，这样可以均衡网络中节点的剩余能量，进而延长网络的生命周期。

3.2 算法步骤

本文的算法将由无线传感器网络的管理中心执行并将收集到的已排序好的路由表发送给各个簇头节点。网络管理中心已知所有节点的位置，剩余能量，点与点之间的权重（距离）等信息，并执行改进型的最短路径算法将所有路径放入V1， V2中。

改进型的最短路径算法流程如下：

Algorithm 1： Improved shortest path algorithm；

Input： Weight of each side w， G=（V，E）， V=（V1，V2，U）， source node s；

Output： V1， V2；

Initialization： V1=V2{s}； U={other vertices}； if u is not a neighbor of s， w=∞；

1： select a vertex x with the shortest distance to s from U， add x to V1； add other adjacent vertices to V2 set；

2： sort V2={VI， VII， VIII} according to their w；

3： select new vertex y with x as middle node；

4： if the distance from x to y is shorter than the distance from s to y；

5： w=w+w；

6： go to line 8；

7： else；

8： The vertices sorted in V2 set are taken as intermediate nodes and same operation is performed；

9： go to line 11；

10： end if；

11： if all vertices are included in V1 and V2；

12： end of the process；

13： else；

14： go to line 1；

15： end if。

在簇頭节点接收到路由表以后，每个簇头节点先对该时刻内到达的业务数据包进行时延分析并排序它们的业务优先级。在该时刻中，簇头节点优先考虑较高业务优先级的数据包，在为一个数据包规划路径时，先根据数据包的时延限制及排队情况更新其优先级，如果该数据包的优先级提升至最高，则按最短路径进行转发，如果不是，则簇头节点从排序好的V2中依次选择较短路径，并将所选路径上传至网络管理中心。网络管理中心分析该路径是否满足负载均衡约束，如果满足则该业务按所选路径进行数据转发，否则簇头节点从V2中依次选择较长路径并执行上述过程直至所选路径满足负载均衡约束。

基于业务质量分析的网络资源分配方法流程如下：

Algorithm 2： Service Quality based Network Resource allocation method （SQNR）

Input： Packet hop limit H， packet priority x， cluster-head node set C， V1， V2， Esend， Ereceive；

Output： packet priority X， Elast ， ；

Initialization： initial energy of nodes Einit；

1： for each cluster-head node in set C；

2： analyze service quality requirements of arrived data packets and get packet priority x and delay limit in each of them；

3： sort arrived data packets according to their packets priority；

4： select a new data package；

5： update its packet priority X according to formula （10）；

6： if it is the highest-priority service；

7： select the next hop from V1；

8： if the package reach sink node；

9： go to line 4；

10： else；

11： go to line 5；

12： end if；

13： else；

14： select the next hop from V2 that can make decrease；

15： if the package reach sink node

16： go to line 4；

17： else；

18： go to line 5；

19： end if；

20： end if；

21： end for。

4 仿真實验

4.1 仿真参数设置

本文使用MATLAB模拟面向输电线路在线监测的WSN场景进行仿真实验。仿真参数如表1所示，仿真结果均为多次实验结果的均值。

4.2 仿真结果

仿真实验中，假设汇聚节点位于最右端，每个传感器节点都可以自发地产生数据包和转发数据包，所有的资源分配算法基于静态均匀分簇算法。对蚁群算法和SQNR算法的资源分配方式分别进行仿真，仿真结果如图2和图3所示。

从图2和图3中可以看出，对于蚁群算法，该算法在进行资源分配时，不考虑业务质量需求。它先尝试搜寻路径并在搜寻路径时留下信息素，最终根据留下信息素的多少判断传输方式的优劣。该算法会对所有需要转发的信息都采用最优的资源分配方式进行数据转发。而SQNR算法中，该算法对不同业务的优先级进行排序。对于低质量要求业务（时延要求低），该算法会在满足业务质量要求的前提下，选择节约能耗并使整个网络负载均衡的方式分配资源，最终使业务质量要求比较高的业务选择的较短路径，而业务质量要求比较低的业务选择“绕远”路径。

在仿真时，记录下两种算法每一轮的节点死亡情况，比较两种算法死亡第一个节点和30%，60%及90%节点死亡的轮数，结果如图4所示。

由于SQNR算法对于低时延要求的数据采用使整个网络负载均衡的路由规划方式，所以整个网络的能耗较为均衡，节点死亡较慢。由图4可以看出，SQNR算法的节点死亡时间晚于蚁群算法，因此有更好的能量效率。

图5为两种算法每五轮的所有生存节点剩余能量标准差。从图4中可以更加直观的看出，SQNR算法的每轮所有生存节点剩余能量标准差明显小于蚁群算法。

5 结束语

传感器网络被应用在生活中的各个领域。无线传感器网络（WSN）是传感器网络中较为复杂的一个分支。本文提出了一种无线传感器网络场景下的网络资源分配方法，即基于业务质量的网络资源分配方法（Service Quality based Network Resource allocation method， SQNR）。该算法是一种适用于簇间的资源分配方式。与基于蚁群算法的资源分配方式相比，SQNR算法通过转发不同业务数据包给不同的路径，节约了低延时要求业务的数据传输能耗并提升了整个网络的负载均衡程度。仿真结果显示，该算法可以在保证业务质量要求的前提下，有效平衡资源分配网络中各个节点的能耗，最终延长整个网络的生命周期。

基金项目：

1. 国网江苏省电力公司科技项目（项目编号：J2017072）；

2. 国家科技重大专项（项目编号：2017ZX03001013）。

参考文献

[1] R. Fang， J. Wang， W. Sun， Q. Li. QoS Model of WSNs Communication in Smart Distribution Grid [J]. International Journal of Distributed Sensor Networks， 2016（8）： 1-23.

[2] Verma S， Rana P. Wireless communication application in smart grid： An overview[C]// IEEE， 2015：310-314.

[3] Salehpour A A， Mirmobin B， Afzali-Kusha A， et al. An energy efficient routing protocol for cluster-based wireless sensor networks using ant colony optimization[C]// International Conference on Innovations in Information Technology. IEEE， 2008：455-459.

[4] Xiao H， Zhao X， Ogai H. A New Clustering Routing Algorithm for WSN based on Brief Artificial Fish-School Optimization and Ant Colony Optimization[J]. Ieej Transactions on Electronics Information & Systems C， 2013， 133（7）：1339-1349.

[5] Yao F. Cluster Routing based on Low Energy Adaptive Clustering Hierarchy Centralized Algorithm in Wireless Senor Network[J]. Information Security & Technology， 2014.

[6] Heinzelman W R， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless sensor networks[C]// Hawaii International Conference on System Sciences. IEEE， 2000：8020.

[7] 黃韬，杨宁，张智江，等. LEACH及其演进路由协议分析与仿真[J].无线电通信技术， 2009， 35（1）：4-7.

[8] 张志艳.无线传感器网络LEACH路由算法研究与改进[D].西南交通大学， 2014.