基于QoS的无线传感器网络感知调度协议

姚道远，王海林，张宝贤，刘海涛

（1. 中国科学院 上海微系统与信息技术研究所，上海 200050；2. 中国科学院 研究生院，北京100049）

1 引言

事件监测[1]是一类重要的无线传感器网络应用[2]，本文所面向的传感网应用是突发事件检测和汇报，传感器节点的工作区域内人员很难进入，结合应用需求和传感器节点具有电池容量有限和难以更换或充电等特点，事件检测无线传感器网络存在两大挑战。首先，系统需要提供应用要求的事件检测质量，即任何事件都需要在应用限定的较短时间内被检测到；其次，为尽可能延长网络生存时间，需提高协议的能量效率，减少节点能耗并考虑节点间能耗均衡。现有的大部分研究[3]集中于提供完全感知覆盖（传感器一直处在工作状态），事件发生后能立刻被检测到。但在实际应用中，大部分事件都会持续存在一段时间而不是瞬时消失[4]，类似事件包括火灾、盗窃和污染等。事件的这种特性使得传感器处于相对较低的感知任务占空比时仍可以满足监测要求。本文将重点研究满足应用指定的监测时延要求的节点级感知调度方法。

已有感知调度工作主要研究完全覆盖问题[5,6]，即：在保证目标区域中任意点在任意时刻都被至少k（k≥1）个节点不间断覆盖的前提下，如何有效减少参与执行该任务的节点总数，但是不间断覆盖（或称完全监测）将消耗大量的节点能量，因而能量利用效率不高。结合无线传感器网络的应用特性和要求，部分覆盖通过周期性节点睡眠调度（包括感知部件和通信部件）将可以在网络寿命和监测质量之间建立更良好的折衷关系，这是本文的主要研究对象。

目前国外有关局部覆盖领域的研究中，文献[7]提出了位置无关的分布式扩展网络生存时间的节点调度协议，基本思想是将所有传感器节点随机归类于k(k≥1)个不相交的节点子集，并按轮次调度。文献[8]分析了平均事件监测时延，节点布设改为与实际更相符的泊松点过程。文献[9]提出在监测和传输2个阶段最小化监测时延的优化算法，既没有探讨全局监测时延，也没有系统地分析节点间协同调度与监测时延之间的关系。文献[10]提出了泊松点分布下的过监测问题，设计了节点间协同唤醒协议，但没有给出时延的下界，也没有探讨平均监测时延、节点密度和调度机制之间的本质联系。以上算法没有讨论自适应节点密度以满足不同应用需求的问题，因此无法灵活调节任务占空比，以支持用户动态可控的监测时延等服务质量。国内相关研究中，文献[11]利用了邻居节点信息减少工作节点数量，但并不是针对具有一定时延容忍度的事件监测应用。文献[12]提出面向事件监测的基于栅格的感知调度方法，但要求节点获得一定精度的位置信息，也不是针对满足不同级别QoS应用需求的目标设计调度算法。

本文在分析点目标场景的事件监测时延的基础上，设计了适用于大规模随机布设场景的自适应分布式感知调度协议(ADSSP)，相比传统的随机调度协议，ADSSP能满足全网范围内动态可调的监测时延要求；通过对协议进行能耗均衡目标优化，相对延长了30%的网络生存时间。仿真验证了ADSSP协议的有效性。

2 理论分析

由于随机布设方式下节点空间分布通常可以由泊松分布过程描述，本节将首先给出节点泊松分布场景下的平均监测时延的理论结果和证明，表 1给出了分析过程中用到的变量名和描述。

表1 变量表名的描述

定理 1 假设每个传感器在区间[0,TC]的唤醒时刻随机独立分布，网络中n个传感器节点以泊松方式布设在区域 A=L×L的矩形区域内，令λ=/L2，则区域A中任意点的平均事件监测时延为

证明 根据泊松分布的特征，覆盖任一点P(P∈A)的节点数 XP满足概率分布 Pr(XP=k)=λke-λ/k。

当XP≥1时，时间在第1个超帧周期内能被监测到的时延为DC=TC/(XP+1)。DC的期望值是

由于事件可能在第N个超帧周期后被监测到，N满足概率分布Pr(N=i)=(1-ρ)iρ，其中ρ为第一个周期内被监测到的概率，则有ρ=1-Pr(XP=0)=1-e-λ。据此可以计算任一点的监测时延的期望值为

将E[DC]和Pr(N=i)代入上式并推导即可得到式(1)。定理1给出泊松分布场景下的平均事件监测延迟与全网平均节点密度的关系。

接下来介绍 ADSSP协议设计使用的相关结论是在点目标监测应用场景下推导获得。

1) 结论1：如图1所示的点目标监测应用中，阴影区域被K个传感器覆盖，每个传感器唤醒时刻满足 wi∈[0, TC]，则事件监测时延期望值E[D]≥TC/(2K)， 当 且 仅 当 di=wi+1-wi=TC/K(i=1,2,…,K-1)（不失一般性，假设 0≤wi≤wi+1≤TC(1≤i≤K-1)）时等号成立。

2) 结论2：假定点目标被K个传感器覆盖，最小平均时延要求为 DL，设 k=TC/(2DL)，系统参数µ=K/k，根据 µ的不同取值，可采用不同的调度策略以满足应用需求，具体如下。

② 1≤µ＜2，所有节点按照结论1的方式调度，但每个周期的唤醒概率γQ=2/(µ+1)。

图1 点目标监测图

3 自适应分布式感知调度协议

大规模传感器网络通常以随机抛射等方式将传感器节点布设在事件监测区域内。事件区域Ω为全网范围，每个节点的感知范围相同，每个节点的感知覆盖范围均在Ω内，假设网络中总节点数N，则全网范围内平均有效覆盖节点数为。现有研究中大规模随机布设网络大都以分簇方式组网，簇头和成员分别承担网络管理和感知功能。本文主要考虑既可以实现全网范围内大致相同的事件监测时延DL，又可以让网络满足灵活可控的事件监测时延的要求，并且最大化网络寿命。由于随机布设会导致局部节点密度不一致，现有的随机调度协议无法满足应用需求，因此需要考虑的问题有：(A)传感器节点如何获取局部的节点密度? (B)如何在节点级设计统一的协议，针对节点密度不均衡的情况，在保障事件监测时延的前提下最小化节点感知能耗？(C)能否通过协议优化尽可能平衡全网范围内的能量消耗，最大化网络寿命？根据结论1给出的点目标的分析结果，本文提出一种自适应分布式感知调度协议，并针对全网范围内能耗均衡的目标优化该协议。协议分3个阶段，分别为邻居信息收集阶段、确定调度方式阶段和值守阶段。邻居信息收集阶段解决问题(A)，确定调度方式阶段解决问题(B)和(C)。以下阶段中节点在时间上以超帧TC周期性地执行相应操作。

1) 邻居信息收集阶段

网络中所有传感器节点通过互相广播 HELLO帧获得邻居节点的基本信息(ID，与本节点的距离di)，建立各自的邻居信息列表NIT。任一节点s获得邻居信息后，计算自身所在局部的有效节点数K。假设邻居数为n，邻居i与s的距离为di(i=1,…,n)，首先计算两者的覆盖相交区域面积RED( i)=，然后使用式(2)计算参数K。

该参数即可表示节点s所在的局部区域密度λ*。

根据应用要求的全网范围内平均事件监测的时延DL，计算得到系统参数k =TC/(2DL)和µ=K/k。每个节点计算各自的参数µ(相邻节点的µ值可能不同，但差别不大)，根据µ值所在的区间，有3种情况，分别为 0＜µ＜1，1≤µ＜2 和 µ≥2，对应节点从稀疏分布到密集分布的不同情形。该阶段一般持续数个超帧周期，随后节点进入确定调度方式阶段。

2) 确定调度方式阶段

该阶段所有已确定协议参数µ的节点在τ(τ＞1，协议参数)个超帧周期内重复执行算法1，确定节点在值守阶段执行监测的工作参数向量(η, w)，并确定值守阶段各超帧周期的唤醒概率γQ，最后进入值守阶段。以下给出算法1的具体内容并做详细阐述。

算法1 参数(η, w)确定算法

① Input: NIT； // 邻居表，邻居节点的ID、间距di、序号ηi和唤醒时刻wiµ //节点的局部密度，通过计算K值后得到

② Output: (η, w)

③ if(0＜µ＜1 || 1≤µ＜2)

④ η⇐ Null；

⑤ else if(µ≥2)

⑦ η⇐ηmin，其中 ηmin= argmin{num(j)},0≤j≤

⑧ endif

⑨ 查询NIT，对邻居节点si(要求ηi==η或ηi==Null)中已初定的唤醒时刻

递增排序得到〈w1,w2,…,wn〉,其中 w1≤w2≤…≤wn，n≥0；

⑩ if(w当前未定) //当前节点调度时刻未定

⑪ if(n==0)

⑫ w⇐ TC/2；

⑬ else

⑭ 变量 wn+1⇐ w1+TC；

⑮ 计算 di⇐ wi+1-wi, i=1,…,n；

⑯ dmax⇐max{di, i=1,…,n}，并确定对应区间〈wx, wy〉；

⑰ 初定唤醒时刻w⇐(wx+ wy)/2；

⑱ endif

⑲ else

⑳ REPEAT

21 变量 wn+1⇐ w1+TC；

22 计算 di⇐ wi+1-wi, i=1,…,n；

24 假设 w 未定，重复步骤⑪ ～ ⑰)计算w，变量w*⇐w；

25 以w*为当前唤醒时刻，重复步骤21 ～23 ，计算均方差 σ，变量 σ1⇐σ；

26 if (σ1-σ2＞th)

27 更新 w ⇐ w*；

28 else

29 BREAK； //满足程序终止条件，循环结束

30 endif

31 until(τ-1帧的迭代计算执行完毕)

32 endif

33 广播DEWU帧；

34 end

首先给出伪代码中的部分变量说明。

num(j)：指邻居节点中，按照参数η对邻居节点分集（共个集合），第j个集合的元素个数，其中0≤j≤-1。

算法1中确定参数η的步骤③～⑧执行1个帧周期，传感器通过随机退避机制广播包含ID、η和w值的DEWU帧，减少信号冲突。退避方式是节点根据自身计算得到的µ值，计算广播调度时刻更新帧DEWU的退避时间，选择区间[0, µBOmax]，BOmax为协议参数，并设置退避定时器。µ值最大的节点最先确定自身的参数η=0, w=TC/2，并广播DEWU帧。节点接收到邻居的 DEWU后，将信息添加到邻居列表NIT。当µ≥2时，节点将选择0～-1序号的节点个数按照从大到小排序，选择节点个数最小的序号，其他情形η =null。确定参数w的步骤执行时间为 τ(τ＞1)个帧，每个帧的开始时刻，节点如果侦测到信道空闲，则计算并决定是否更新当前调度时刻w，在第1个帧内，唤醒时刻未定，通过步骤⑪～⑰计算得到，并得到初步确定。接下来的τ-1帧内，重复步骤21～30，不断调整自身的唤醒时刻w，计算均方差的公式如下：

根据协议参数µ的取值，确定唤醒概率γQ的取值。

1≤µ＜2，根据结论 2，节点的唤醒概率 γQ=2/(µ+1)；

µ≥2，节点在确定的唤醒周期内以概率 γQ=1唤醒工作；

0＜µ＜1，节点每个周期的唤醒概率γQ=1，由结论2知节点每个周期内唤醒次，唤醒时刻可表示为。其中wi(0)取算法1获得的参数w。假设调度时刻排序后下一个邻居节点的唤醒时刻为 wj(0)，根据 di=wj(0)-wi(0)，计算得到：

综上，节点需要维护调度参数(η, w)，但在1≤µ＜2和 0＜µ＜1这 2种情况下，节点在每个周期均唤醒工作，η无意义，此时设置η=null。不同密度分布情形下，各节点确定调度参数(η, w)的方法如算法1伪代码所示。接下来所有节点进入值守阶段，在确定的调度周期和调度时刻内，以确定的唤醒概率γQ工作。

3) 能耗均衡优化

在保证平均监测时延满足应用需求的前提下可通过基于剩余能量动态调整感知占空比对协议进行全网能耗均衡优化，为此引入剩余能量加权因子ω。

其中，Einit为初始能量，Ethr为感知能量门限，Eres为当前节点剩余能量，α(α≥2的整数)为协议参数。当 Eres=Einit时，ω=1；当 Eres=Ethr时，ω=0；其他0＜ω＜1。

各节点计算得到自身加权因子 ω*和获得邻居加权因子ωi，1≤i≤n，计算平均加权因子。

更新式(2)，各节点计算本地的有效覆盖节点数K。

4) 协议复杂度分析

协议的复杂度主要由算法1决定，各节点独立执行算法1，接收邻居信息并执行排序操作，因此协议的复杂度为O(dlgd)，其中d为最大邻居节点数。

4 仿真验证

4.1 仿真场景

网络通过分簇方式管理，假设簇间保持时间同步，各簇内传感器节点独立工作互不干扰，因此可以通过仿真考虑单个簇的协议性能表征全网性能。在图2所示的K个节点随机布设场景中，各传感器节点的覆盖半径为 rs，节点 1为负责网络管理的Sink节点（或簇头节点），事件发生的范围是以节点1所在的位置为圆心，以re为半径的圆。仿真平台为QualNet-v4.0，在QualNet中设置物理层采用802.15.4-PHY协议，双径模型，理想无衰落信道；MAC层采用802.15.4-MAC协议。其他仿真参数见表2。

图2 随机布设场景(K=22)

表2 仿真参数

4.2 仿真结果

以下仿真性能包括监测时延均值和方差，其中均值计算方法在之前已有叙述，监测时延方差V[D]的统计方式见式(8)。

其中，Di为节点 i的监测时延，为所有的节点的平均监测时延。接下来介绍随机调度协议：网络拓扑建立后，传感器节点在每个帧[0, TC)内随机选择自身调度时刻 w，节点每个帧唤醒一次，执行感知任务，监测到事件后，将数据上传到簇头或Sink节点。

图3比较了ADSSP协议与最优调度算法的平均延迟的性能。仿真中通过保持rs不变，调整节点分布密度以改变 K值。由图 3可以看出，ADSSP协议在不同密度分布情况下都能获得接近理论最优的监测性能。

图3 ADSSP协议的事件监测时延性能

图4为ADSSP协议根据应用调整任务占空比后获得的监测时延均值和方差的性能，且与点目标平均监测时延下界进行对比。横坐标为 K(K=DL/2TC，DL为监测时延应用需求)；ADSSP_E[D]为ADSSP协议的监测时延均值；点目标为点目标时的监测时延下界；ADSSP_V[D]为ADSSP协议的监测时延方差。由图4可以看出，ADSSP协议能通过灵活改变协议参数K以满足不同的应用需求。

图4 ADSSP协议监测时延平均值和方差

图5为ADSSP协议和随机调度协议在同一布设场景下的性能对比。仿真中通过调节覆盖半径rs，改变网络平均有效覆盖节点数K ，获得对应的监测时延均值和方差。从图5可知，ADSSP协议的监测时延和方差均比对应的随机调度协议小。

图5 ADSSP和随机调度协议的监测时延均值和方差对比

图6和图7为根据节点剩余能量对ADSSP协议进行优化与未优化时的节点生存时间和平均监测时延对比图。综合图6和图7，优化的协议能获得更为均衡的能耗速度和更长的节点生存时间(前 5个节点平均生存时间延长17.9%)；平均监测时延仅增加5%。

图6 ADSSP协议优化前后网络生存时间对比

图7 ADSSP协议优化前后平均监测时延对比

图8为随机调度协议和优化后的ADSSP协议在满足相同全网平均监测时延的前提下(E[D]=15.85ms)节点生存时间。仿真中协议参数k=4，仿真统计次数为100次。本文考虑以前5个死亡节点的平均生存时间为网络的生存时间，优化后的 ADSSP协议相对于随机调度协议延长了30.5%的生存时间。

图8 不同协议导致的网络生存时间对比

5 结束语

为满足大规模随机部署情况下传感器网络对事件监测时延的不同要求和尽可能延长网络生存时间，本文设计了自适应分布式感知调度协议，仿真结果表明 ADSSP可以提供全网范围内可调的感知质量保证，并延长了网络生存时间。

[1] BRENNAN S, MIELKE A, TORNEY D. Radioactive source detection by sensor networks[J]. IEEE Transactions on Nuclear Science, 2005,52(3):813-819.

[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Journal of Computer Networks, 2008, 52(12): 2292-2330.

[3] LUO H M, WANG H Z. A precise coverage control protocol with limited communication in wireless sensor networks[A]. IEEE International Symposium on Embedded Computing[C]. 2008. 149-154.

[4] DUTTA P, GRIMMER M, ARORA A. Design of a wireless sensor network platform for detecting rare, random, and ephemeral events[A].IEEE IPSN’05[C]. California, USA, 2005.497-502.

[5] YEN L H, CHENG Y M. Range-based sleep scheduling (RBSS) for wireless sensor networks[J]. Journal of Wireless Personal Communications, 2009, 48(3):411-423.

[6] LIU J X, GU N J, and HE S. An energy-aware coverage based node scheduling scheme for wireless sensor networks[A]. ICYCS[C].Zhangjiajie, China ,2008.462-468.

[7] LIU C, WU K, KING V. Randomized coverage-preserving scheduling schemes for wireless sensor networks[A]. IFIP Networking 2005[C].Waterloo Ontario, Canada, 2005.1-10.

[8] JIANG J, LIU C, WU G F. On location-free node scheduling scheme for random wireless sensor networks[A]. ICESS[C]. Xi’an,China,2005.484-493.

[9] CAO Q, ABDELZAHER T, HE T. Towards optimal sleep scheduling in sensor networks for rare-event detection[A]. IPSN[C]. Los Angeles,USA, 2005.1-8.

[10] ZHU Y M, LIONEL M N. Probabilistic wakeup: adaptive duty cycling for energy efficient event detection[A]. MSWiM[C]. Greece,2007.360-367.

[11] 石高涛, 廖明宏. 大规模传感器网络随机睡眠调度节能机制[J]. 计算机研究与发展, 2006, 43(4): 579-585.SHI G T, LIAO M H. Random sleep scheduling energy efficient scheme for large wireless sensor networks[J]. Journal of Computer Research and Development, 2006, 43(4): 579-585.

[12] 胡湘华, 杨学军. 面向事件监测的无线传感网感知调度[J]. 软件学报, 2008, 19(9): 2413-2421.HU X H, YANG X J. Sensing scheduling algorithm of wireless sensor networks for event detection applications[J]. Journal of Software, 2008,19(9):2413-2421.