基于网络微积分的WSNs属性界限研究

李 翠，巨永锋

(1.长安大学电子与控制工程学院，陕西 西安710064;2.江西赣粤高速公路股份有限公司，江西南昌330025)

0 引言

由于无线传感器节点的通信半径有限，不能覆盖整个网络，数据通常需要经过多跳转发才能抵达基站［1］。这使得WSNs的属性界限变得复杂。WSNs属性界限包括数据传输端到端延迟上界、节点缓冲区容量下界以及节点服务速率(即通信带宽)下界等。这些属性界限是配置WSNs相关功能参数(比如:节点分布密度、通信半径、缓冲区大小以及通信带宽等)的重要依据和提高网络服务质量的重要内容。

目前，关于WSNs属性界限方面的研究主要有2个研究方向:一个侧重于路由算法的设计［2～5］，研究如何减小网络时延，并寻找统计学意义上的时延界限;另一个则侧重于利用网络微积分计算WSNs属性界限，并根据计算结果进行网络配置［6～8］。文献［6］结合链路吞吐量模型对无线自组网的端到端延迟上界进行了研究，但其结论仅适用于只在源节点有输入数据流的串联节点系统。文献［7］利用网络微积分建立了一个通用分析模式，用于求解WSNs属性界限。该文献最大的贡献在于得出父节点到达曲线为各子节点到达曲线的函数这一结论。文献［8］将文献［7］的分析模式分别拓展到不同拓扑条件下的网络，如不确定性拓扑、多汇聚点拓扑以及树状路由拓扑等。文献［9］面向前馈(feed-forward)网络，对流经同一节点不同数据流的服务曲线进行区别化分配，以求解更精确的延迟上界。

基于网络微积分［10，11］，本文修正了流经节点的数据流输出上界，推导出更精确的WSNs属性界限，并通过数值分析对属性界限进行比较。

1 网络微积分相关概念

网络微积分基于最小加代数理论，是一种新的可用于网络建模和定量分析的数学工具，利用它可以分析网络延迟、队列缓冲区大小以及节点带宽等一些网络的基本属性。网络微积分主要包括到达曲线、服务曲线以及最小加代数下的卷积和反卷积等基本概念。其中，到达曲线用来描述一个数据流的输入特性并对其加以约束;服务曲线则反映了节点转发数据流的调度细节和服务能力，对数据流在流经节点时输入行为和输出行为之间的关系进行抽象。相关定义如下:

定义1 广义增函数:对于∀s≤1，若f(s)≤f(t)均成立，则称 f为广义增函数。

定义2 广义增函数集合:若 F={f(t)|，f(t)=0，∀t＜0;f(s)≤f(t)，t∈［0，+∞］}，则称 F 为广义增函数集合。

定义3 最小加卷积:对于∀f，g∈F，函数f和g的最小加卷积运算为

定义4 最小加反卷积:对于∀f，g∈F，函数f和g的最小加反卷积运算为

定义5 到达曲线:给定一个广义增函数α∈F，若输入流的累积函数R对任意时刻s和t均满足

其中，0≤s≤t，则称α是R的到达曲线。

定义6 服务曲线:给定一个广义增函数β∈F，对于一个系统S和流经S的流，在输入端和输出端该流的累积函数分别为R和R*，当且仅当

其中，0≤s≤t，则称β是S为数据流提供的服务曲线。

在已知数据流到达曲线α和服务曲线β的情况下，可以得出如下几个定理:

定理1 积压上界:假设到达曲线为α的数据流通过一个所提供服务曲线为β的系统S，那么，对任意时间t，系统S中积压的数据满足

定理2 延迟上界:假设到达曲线为α的数据流通过一个所提供服务曲线为β的系统S，那么，对任意时间t，数据流在S中的延迟满足

定理3 输出上界:假设到达曲线为α的数据流通过一个所提供服务曲线为β的系统S，那么，输出上界为

定理4 假设系统S1和S2提供的服务曲线分别为β1和β2，系统S1和系统S2串联后提供的总服务曲线为β，则 β =β1⊗β2。

2 流量模型与属性界限

2.1 感知数据到达曲线与服务曲线

假设传感器节点均为同构，监测区域具有比较平均的数据突发率，每个节点均能感知并接收到监测数据，从平均的角度看，可以认为不同的节点具有相同的监测数据量。监测数据输入对应节点时的到达曲线满足漏桶管制(leaky bucket regulated)［8］，到达曲线表示为

式中 rs和bs分别为每个节点感知范围内监测数据的平均速率和突发数据大小，bs又称为漏桶容量。

因节点是同构的，故假定每个节点均具有相同的服务能力，其基于速率—延迟的服务曲线为

式中 Rs为节点服务速率，且Rs≥ri;Ts为数据在节点缓冲区中的最大调度延迟;(x)+=max(0，x)。

2.2 输出上界

考察某FIFO节点(输入输出节点)输入—输出数据流的关系。在时刻t，输入端到达曲线为α(t)，输出端实际输出曲线为α'(t)，输出端输出上界为α*(t)。参考文献对数据流输出上界的求解均是基于定理3公式(7)，则满足式(8)流量约束条件的数据流输出上界为α*(t)=α(t)+rT。该输出上界与节点调度延迟T相关，明显偏大。假定数据流经过节点的实际延迟为d，由于节点服务速率足够大，故节点中积压数据实际应为rd，输出端实际输出曲线应为α'(t)=α(t)－rd≤α(t)。考虑到延迟d为变量，存在不确定性，因此，输出上界可取为

上式表明:在同一时刻t，输出端实际输出的流量不会高于输入端实际输入的流量，物理意义明确。和参考文献采用的输出上界相比，式(10)更精确且更符合实际情况。

2.3 属性界限

在WSNs中，传感器节点的通信半径有限，传输范围不能覆盖整个网络，数据通常需要通过多跳路由转发才能抵达基站。因此，网络中数据流呈现不均匀状态，数据流往基站方向汇聚，节点越靠近基站，则需要服务的数据流越多。对于网络中的某一传输路径，可以将其作为一个只接收数据流汇聚的系统，系统内任意一跳节点的输出数据全部往下一跳父节点传送。这个假定符合WSNs中数据流往基站汇聚的规律。

对于节点i，输入数据流为汇聚流，该汇聚流包括节点i自身感应数据流和子节点转发过来的数据流，如图1所示，其到达曲线如下式所示

式中 Ni，child_all是以节点i为必经路由的所有节点数量，即流经节点i的所有转发感应数据流的数量。

图1 流经节点i的汇聚数据流Fig 1 Aggregate data flows traversing node i

对于某总跳数为H的传输路径，源节点到基站的端到端延迟上界为各跳最大延迟之和，如下式

对于同构WSNs，端到端延迟上界应为

由式(14)可知，传输路径总跳数H越大，汇聚至该传输路径的数据流越多，则端到端延迟上界越大。

由式(5)和式(12)得到节点i缓冲区容量下界(即积压上界)为

若式(16)不能满足，则网络通信繁忙时节点缓冲区可能溢出，造成丢包。由式(16)可知，汇聚至节点i的数据流越多，积压上界越大。

为保证数据传输通畅，要求节点服务速率下界满足

若式(17)不能满足，则可能引起通信阻塞，从而造成数据丢失和网络延迟增大。

3 实验分析

以图2所示WSNs拓扑结构［7］为例进行数值分析。监测区域为8 d×8 d的正方形，均匀布置80个传感器，每个传感器节点通信半径为理想的。基站位于方形区域正中。在第一个节点死亡之前，节点总是以最短路径进行数据传输。部分传输路径如图2所示。假定为同构WSNs，rs=0.1 kbps，bs=0.2 kb，Rs=1 Mbps，Ts=0.1 s，服务速率和节点缓冲区足够大。WSNs属性界限如表1和表2所示。

图2 WSNs拓扑示意图Fig 2 Diagram of WSNs topology

表1 端到端延迟上界Tab 1 End-to-end delay upper bound

表2 积压上界与服务速率下界Tab 2 Backlog upper bound and service rate lower bound

由表1和表2可知，方法1求得的节点延迟上界和积压上界比方法2的要小，而服务速率下界相同。随着网络跳数的增加与节点梯度的减小(即离基站更近)，节点延迟上界和积压上界差异越来越大。这种差异来源于2种方法采用了不同的数据流输出函数上界。数值分析结果表明:网络规模越大，按本文属性界限进行网络配置能节约更多资源。

4 结论

本文对流经网络节点的数据流输出函数上界进行了改进，使其更符合物理意义，并由此推导出更精确的WSNs属性界限。与现有文献属性界限相比，本文求得的延迟上界和积压上界表达式更简单和精确，但服务速率下界是相同的。本文所得WSNs属性界限是WSNs网络配置的重要依据。数值分析结果表明:网络规模越大，按本文属性界限进行网络配置能节约更多资源。

［1］hajela R，Garimella R M，Sabnani D.LCSD:Leveling clustering and sectoring with dissemination nodes to perform energy efficient routing in mobile cognitive wireless sensor networks［C］∥2010 International Conference on Computational Intelligence and Communication Networks:IEEE Computer Society，2010:177－182.

［2］Pothuri P K，Sarangan V，Thomas J P.Delay-guaranteed，energyefficient routing in wireless sensor networks through topology control［C］∥ Proceedings of the 2006 IEEE International Conference，Piscataway，NJ，USA，IEEE，2006:35－41.

［3］Ahmed A A，Fisal N.A real-time routing protocol with load distribution in wireless sensor networks［J］.Computer Communications，2008，31(14):3190－3203.

［4］Xu Yingsheng，Ren Fengyuan，He Tao，et al.Building a potential field to provide real-time transmission in wireless sensor networks［C］∥Proceedings of the 13th ACM International Conference on Modeling，Analysis and Simulation of Wireless and Mobile Systems，New York，USA，ACM，2010:403－410.

［5］梁庆伟，姚道远，巩思亮.一种保障时延能量高效的无线传感器网络路由协议［J］.西安交通大学学报，2012，46(6):48－52.

［6］李庆华，陈志刚，黄国盛，等，基于网络演算的无线自组网端到端延迟上界研究［J］.系统仿真学报，2009，21(8):2248－2251.

［7］Schmitt JB，Roedig U.Sensor network calculus—A framework for worst case analysis［C］∥Proceedings of the International Conference on Distributed Computing in Sensor Systems(DCOSS05)，USA，2005:141－154.

［8］Koubaa A，Alves M，Tovar E.Modeling and worst-case dimensioning of cluster-tree wireless sensor networks［C/OL］∥Proceedings of the 27th IEEE Real-Time Systems Symposium(RTSS06’)，Rio de Janeiro，Brazil，2006.［2012—07—01］.http://citeseerx.ist.psu.edu.

［9］Kiefer A，Gollan N，Schmitt H B.Searching for tight performance bounds in feed-forward networks［C］∥Measurement，Modeling，and Evaluation of Computing Systems and Dependability and Fault Tolerance，Berlin，Germany:Springer，2010:227－241.

［10］Chang Chengshang，Cruz R L，Boudec J Y L，et al.A min-plus system theory for constrained traffic regulation and dynamic service guarantees［J］.IEEE/ACM Trans on Networking，2002，10(6):805－817.

［11］高文宇，陈乔松，王建新.网络微积分学研究［J］.微电子学与计算机，2004，21(11):76－80.