基于SP调度策略的簇树型无线传感网络QoS上界研究

陈越洋，顾 平，张 超

(广西大学计算机与电子信息学院，广西 南宁 530004)

0 引言

无线传感网络(Wireless Sensor Network，WSN)是由大量廉价的同构或异构具有无线通信与计算能力的微型传感器节点，部署在无人值守的监控或测量区域，能够根据检测目标或对象自主完成给定任务，并将准确的信息传送到远程用户的智能检测网络[1]。目前，利用网络演算对无线传感网络进行性能分析主要是基于经典的 FIFO队列调度[2-4]，忽略了终端节点产生数据流比路由节点产生数据流需要更多的跳数才能到达汇聚节点的数据流特点。本文在簇树网络拓扑中引入SP队列调度，将路由节点的数据转发服务优先提供给终端节点产生的数据流，减小网络的端到端时延。本文在文献[3-4]的已有网络流量模型基础上，利用网络演算的相关理论，推导出最坏条件下的节点队列长度、单跳时延上界，并结合文献[5-6]中的总流量分析法，求解该调度策略下的最大端到端时延。

1 确定性网络演算的基本工具

定义1 到达曲线(Arrival Curves)[7-8]:给定一个函数α(t)，且α∈Γ，Γ为广义增函数集合，若通信流的累积函数R(t)对任意时刻t≥s≥0满足R(t)－R(s)≤α(t－s)，则称 α(t)为 R(t)的到达曲线。

定义2 服务曲线(Service Curves)[9-11]:给定一个通信流的累积函数R(t)，对于函数β(t)∈Γ，且β(0)=0，若通信流的输出函数R*(t)满足R*≥R⊗β，则称节点为通信流R(t)提供服务曲线β(t)。

定理1 积压上界定理[10]:假定一个到达曲线为α(t)的通信流穿过一个网络系统，该系统为通信流提供的服务曲线为β(t)，则对任意时刻t，通信流在该系统中的积压数据(队列长度)Q(t)满足如下的关系:

定理2 时延上界定理[7，10-11]:假定一个到达曲线为α(t)的通信流穿过一个网络系统，该系统为通信流提供的服务曲线为β(t)，对任意时刻t，通信流在该系统中的延迟D(t)满足如下的关系:

定理 3 输出受限特性[5，7，11]:假定一个到达曲线为α(t)的通信流穿过一个网络系统，该系统为通信流提供的服务曲线为β(t)，则输出流受限于α*(t)=α∅β。

2 簇树型无线传感网络

簇树型无线传感网络是一种分层拓扑结构，以单簇星型网络拓扑为基础，簇与簇之间形成树的结构，见图1。

图1 簇树型无线传感网络结构

网络主要包含3种节点:根节点(root)、路由节点(router)、终端节点(end-node)。本文假设，这3种节点都具有感知能力，根节点不获取感知数据。

本文将采用以下参数对簇树网络进行配置:

1)网络深度H:即数据流从网络最底层路由节点到根节点要经过的逻辑跳数(Logic Hop)。设根节点的深度为0，则最底层路由节点所在簇内的终端节点的深度为H+1。

2)Nr(Maximum Number of Child-routers):路由节点所连接的最大子路由节点数目。

3)Ne(Maximum Number of End-Nodes):路由节点所连接的最大的终端节点数目。

本文研究在最坏情况下的网络服务质量，即所有终端节点和路由节点都被要求向汇聚节点发送传感数据。

3 基于SP调度策略的无线传感网络QoS上界研究

3.1 SP 队列调度

严格优先级队列调度是常用队列调度算法的一种。SP调度算法严格按照队列的优先级从高到低的次序，先发送级别较高的队列中的分组，直到高优先级队列为空，才会发送较低优先级队列中的分组。调度过程如图2所示。

图2 SP队列调度

在本文中，对路由节点引入SP调度策略，优先给转发数据流αtransmit提供服务，即转发数据流的优先级要高于路由节点自身的传感数据流αself－sense。所以对于自身传感数据流而言，其获得的路由节点提供的保证服务的服务曲线为 βself－sense=[β － αtransmit]+。但是形成汇聚转发流的各数据流之间没有优先级。

在簇树拓扑结构中，由于最深处的路由节点形成了2个优先级的数据流，分别是汇聚转发流和自身传感流，那么在上层的父路由节点中，这2个数据流获得保证服务的优先级也不同，这样的优先级会在数据向上汇聚的过程中一直保持。也就是说，随着数据流向上汇聚，数据流之间的优先级数量会不断增加。对于H-i层的路由节点来说，其优先级数目为:

对于任意含有子路由节点的节点来说，其优先级情况为:簇内汇聚传感数据流+子路由节点汇聚转发数据流＞所有子路由自身传感数据流＞自身传感数据流。

αH，self－sense表示深度为H的路由节点的自身传感数据流，那么所有子路有节点自身传感数据流之间会形成如下的优先级:

3.2 输入输出流计算

本文假设传感数据流在进入网络之前经过漏桶整形，其到达曲线为[7]:α =b+r·t。父路由节点为其子节点提供基于速率-延迟的保证服务，其服务曲线为[12-13]:β =R(t－T)+。那么，在簇树网络拓扑结构中，H层路由节点获得H－1层父路由节点提供的保证服务为:

3.2.1 位于深度为H的路由节点的数据流分析

这里是路由节点的底层，对于该层的任意路由节点来说，没有子路由节点，就只有终端节点的数据流向上汇聚，引入SP调度策略之后，会出现2个不同优先级的逻辑队列 αH，0和 αH，1，分别表示自身传感数据流和簇内所有终端的输出流汇聚而成的转发数据流，其计算到达曲线分别为:

由于SP调度策略的影响，这2个队列分别能获得其父路由节点(深度为H－1)所提供的服务保证为:

由公式(1)、公式(2)和定理3可以求出深度为H的路由节点的输出上界为:

3.2.2 深度为H－1的数据流分析

调度策略对H层数据流的影响会延续到H－1层。对于H－1层的路由节点来说将会形成如下的逻辑队列。

其优先级为flow2＞flow1＞flow0，所以各数据流从其父路由节点获得的保证服务如下:

类似可求出深度为H－i的路由节点中各队列的输出流:

类似地，可以推导出深度为H－i(0≤i≤Depth－1)的一般性表达式:

各数据流获得服务的优先级为flowi+1＞flowi＞…＞flow1＞flow0，所以可求出各数据流所获得的保证服务的服务曲线如下:

各队列的输出流:

3.3 单节点服务质量上界研究

3.3.1 缓存上界推导

对于每个节点来说，缓存的大小等于所有逻辑队列的队列长度之和。由公式(6)、(7)和定理1可推导节点缓存大小为:

3.3.2 时延上界推导

根据公式(6)、(7)和定理2可推导各队列的时延上界:

3.4 端到端时延上界推导

由于本文引入了SP调度策略，使得数据流优先级在向上汇聚的过程中不断增加，各路由节点中会有数据分流形成各自优先级的汇聚流，从其父路由节点获得服务保证。所以本文在计算端到端时延时，采用总流分析法，即数据流的端到端时延就等于该流通过的所有服务节点的单跳时延之和。

所以，数据流从各深度路由节点到达汇聚节点的端到端时延上界为:

4 实例分析

本文采用文献[2]中的数据进行实例分析，对WSN进行如下的基本参数设置:H=3，Nr=2，Ne=3，RTS=0.586 kb/s，b=0.2 kb/s，r=0.1 kb/s，终端节点获得路由节点保证服务的固定时延T=0.1 s;根据上文推导的公式(9)～(11)，通过Matlab得出该实例中各节点的缓冲区大小和网络的单跳时延上界，结果如表1、表2所示。

表1 缓冲区队列长度

表2 时延上界

从表1、表2中可以看出，SP队列调度增加了路由节点的缓存开销，增大路由节点产生数据流到达汇聚节点的时延，但是降低了终端节点到汇聚节点的端到端时延。在簇树型无线传感网络中路由节点的数量远小于终端节点的数量，本文中路由节点数目和终端节点数目之比是1∶3，所以以牺牲小部分数据流的时延和增加一部分缓存为代价，换取绝大多数的传感数据能更快地到达汇聚节点，提升总体服务质量是可行的。

5 结束语

本文研究了SP调度策略下的簇树型无线传感网络服务质量，分析了SP调度策略给簇树型无线传感网络中各数据流获得保证服务带来的影响，基于网络演算推导了网络服务质量相关指标的确定上界。实验结果表明，虽然SP队列调度增加了缓存需求，增大了路由节点自身传感数据流到达汇聚节点的时延，但是也明显降低了终端节点产生数据流到汇聚节点的端到端时延。而在实际应用中，终端节点数目会远大于路由节点数目，所以SP调度策略对于提升网络整体的服务质量是有意义的。下一步的研究，可以对节点的占空比进行调节，以获得性能和时延的平衡，也可以利用随机网络演算来对网络的性能进行研究。

[1] 王营冠，王智.无线传感器网络[M].北京:电子工业出版社，2012.

[2] 洪雁兵，王一军，刘桂波，等.基于网络演算的簇树WSN性能上界分析[J].计算机工程与应用，2012，48(19):48-53.

[3] Jurcik P，Severino R，Koubaa A，et a1.Dimensioning and worst-case analysis of cluster-tree sensor networks[J].ACM Transactions on Sensor Networks，2010，7(2):Article 14.

[4] Koubaa A，Alves M，Tovar E.Modeling and worst-case dimensioning of cluster-tree wireless sensor networks[C]//Proceedings of the 27th IEEE Real-Time Systems Symposium.2006:412-421.

[5] 李翠，巨永锋，李雪.WSN中单数据流端到端延迟上界研究[J].计算机应用研究，2013，30(6):1820-1823.

[6] Schmitt J B，Zdarsky F A，Thiele L.A comprehensive worst-case calculus for wireless sensor networks with in-network processing[C]//Proceedings of the 28th IEEE Real-Time Systems Symposium.2007:193-202.

[7] 李焕忠.基于随机网络演算的性能分析技术研究[D].长沙:国防科学技术大学，2011.

[8] Le Boudec J-Y，Thiran P.Network Calculus:A Theory of Deterministic Queuing Systems for the Internet[M].Springer Verlag，2001.

[9] Firoiu V，Le Boudec J-Y，Towsley D，et al.Theories and models for Internet quality of service[J].Proceedings of the IEEE，2002，90(9):1565-1591.

[10] 张连明.基于网络演算的自相似网络性能上界模型研究[D].长沙:中南大学，2006.

[11] 陈京文.基于统计型演算论的网络服务性能分析[D].武汉:华中科技大学，2007.

[12] 陈艳平.基于网络演算的QoS分析方法与保障技术[D].哈尔滨:哈尔滨工程大学，2012.

[13] 柴明.基于ETS的自相似网络QoS性能评价[D].南宁:广西大学，2012.