一种能量有效的无线传感器网络轮询接入控制协议

何敏，赵东风，保利勇，左朝树

(1.云南大学信息学院，云南昆明 650091;2.西南通信研究所保密通信重点实验室，四川成都 610041)

无线传感器网络(wireless sensor networks，WSN)综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，在军事、环境监测、医疗、建筑物监测、智能家居和安全报警、反恐和公共安全、商业等领域都有重要的科研价值和广阔的应用前景.由于传感器节点通常依靠电池供电，能量有限，不能直接应用在现有的无线通信协议中，通常的解决办法是采用休眠机制，减少节点在空闲时期的能耗.随机竞争接入能为突发性数据提供灵活的服务，且控制相对简单，目前部分应用采用基于802.11的竞争类协议，但如何降低碰撞造成的能量消耗是这类协议的一个难题.

轮询方式既避免了碰撞，又能提供具有QoS保障的服务，因此被广泛应用到MAC协议的设计中.研究人员在纯 PCF(point coordination function)［1］系统的基础上，提出了一系列的改进算法［2-8］，如两级优先级轮询［2］、自适应调度［3］、自适应差额调度［4］等改进的PCF系统.这些系统通过对服务策略、调度机制的深入研究，改进了纯PCF系统的性能.文献［5］将没有处在激活状态的站点从轮询列表中删除，网络性能得到了显著的提高.文献［6］通过3级门限服务方式，较好地解决了实时业务在重负载下时延Qos不能得到满足的问题;但是对于低速传感器网络的节点来说，可能导致部分节点较长时间占用信道，欠缺公平性.文献［7］通过为不同业务类别分配服务配额的方式，采用加权轮询调度策略，以业务的平均分组到达率为依据，降低了排队的复杂度.文献［8］基于Zigbee技术，需要服务的节点采用CSMA/CA机制接入，中心采用轮询方式为各节点服务，没有服务需求的节点则休眠以节约能量;但节点在接入后不断发送POLL请求，在ACK响应前一直处于活跃状态，会造成能量浪费.不少学者也提出了一系列节能策略［8-13］，从不同层面解决WSN的能耗问题.

本文在周期性休眠的PCF基础上，提出了一种具有节能效果的轮询控制协议PCF-SS(point coordination function by site status)，在保证公平性的前提下，依据节点状态进行资源分配和服务.其基本思想是:中心在为某节点服务的同时获取该站点的剩余分组信息，且至少保留连续2轮的状态信息，并依据节点状态将其分配到不同优先级组内;同时，根据节点最近2次的状态估计下一轮的服务时间，并将预计的开始服务时刻在本轮服务结束前通知该节点，当节点接受服务后，即可转入休眠，直到下一轮服务时刻的到来，达到节能目的.

1 PCF-SS接入控制机制分析

1.1 PCF-SS接入过程描述

传感器网络节点能量和功率有限，导致传输距离有限.同时，在多数应用中，传感器网络一旦部署，节点的移动性很小，甚至不发生移动.分簇是实施分层控制的重要方法之一，PCF-SS协议适用于簇内节点与中心(簇首)的通信，信息通过簇首间的转发到达Sink.

每个节点可处于休眠、活跃、发送3种状态之一，分别对应空闲、唤醒(或请求服务)和接受服务，由相应的条件触发转换，如图1所示.初始布置后，当终端节点有分组发送时，即向中心发送请求，与中心握手后，加入服务队列，获得服务时间表，进入休眠等待，以减少能量消耗.如果较长时间没有分组发送，中心则将该节点从服务队列中删除，以减少空轮询次数，提高服务效率，直到节点有新的分组到达时，再次苏醒并申请加入服务队列.如果中心在一段时间内没有收到任何服务请求，也将转入短暂的休眠，并在下一时刻醒来后，监测信道，准备服务.

图1 节点状态转移图Fig.1 Status migration of a node

采用上述接入方法，终端节点可能会被延迟服务或提早苏醒，这种情况将在1.3节中进行分析.

1.2 服务策略

通常情况下，轮询系统中的各节点都能获得固定、均匀的服务时间，这对于对称型的系统是合理的.但是在实际应用中，节点的负载往往是不均衡的，根据需求进行可变配置的服务方式普遍存在.因此，系统以限定(K=1)服务为基础，根据节点繁忙程度划分优先级，分别对节点上一轮分组剩余量、本轮分组剩余量进行标识区分，并划分为4类，如表1所示.

表1 节点负载状态Table 1 The loads status of nodes

具体的服务方式如下.

1)初始时，系统按照限定(K=1)服务规则对N个节点进行依次服务，在服务过程中，根据节点的负载状态，将其划入到不同的优先级组内.

2)轻载队列采用限定(K=1)服务;忙队列采用可变(K≥1)服务，即在限定(K=1)的基础上，根据节点当前状态和上轮状态进行预判，调整优先级及下一轮的服务时间;繁忙队列采用门限服务规则.节点接受服务后，转入休眠状态.

3)中心根据服务时间表中剩余节点和前驱节点的预计服务时间，估算各节点下一轮服务的开始时间，并在服务结束前通知该节点.

4)由于节点接受服务后转入休眠状态，服务器不能感知其后续是否有分组到达，因此，轻载组内的节点被服务后，即使处于空闲状态，也被划分到轻负载组，直到下一轮服务时，仍然空闲才转入空闲组中，并将其从轮询列表中删除.

5)优先级高的节点采用逐级向下调整的策略调整其优先级，而低优先级的节点则根据状态直接调整到相应的优先级组.

6)空闲节点一直处于休眠状态，直到有分组到达，再申请接入网络接受服务.

7)每次服务结束后，中心都将进行信道检测，如果有新节点加入，则将其安排到轮询列表的最后.

根据统计原理，参与预测的历史状态次数越多，预测值就越可靠，但运算也越复杂，额外开销越大，因此，系统选取节点最近2轮的状态进行预判.此时，中心存储的轮询列表结构可表示为(节点号，服务顺序号，上轮剩余分组数，本轮剩余分组数，预分配服务数)，以1号站点为例，初始时刻表示为(1，1，0，0，K).

1.3 服务时间表

中心采用统一的服务时间表来确定各节点的服务时间和唤醒时刻.当中心为某节点服务时，根据其状态预判下一轮的服务时间，决定该节点的唤醒时刻，更新服务时间表，当节点接受服务后，转入休眠状态并启动一个唤醒时钟.

采用服务时间表带来的一个问题是节点可能延迟苏醒(晚醒)或提前苏醒(早醒).前者是因为中心对剩余节点的服务规则可能是门限或可变(K≥1)服务，而节点的分组到达数量是随机的，因此门限服务和可变(K≥1)服务所耗费的时间是不确定的.为此设定了一个门限值Tg来确定门限服务时间，中心可能不需要Tg时间就能完成对某节点的门限服务，这对后续节点来说，相当于延迟苏醒;同理，对可变(K≥1)服务也一样，当节点中的分组数少于K个时，也将引入延迟.后者正好相反，当中心对某节点的门限服务在Tg时间内不能完成时，将推迟后续节点的服务时间，但后续节点并不能感知，仍然按照时间表上的时间唤醒，相当于节点早醒.上述2种情况是休眠策略不可避免的，晚醒将增加系统时延，早醒则会增加节点的能耗.此外，当前节点可能没有分组发送，但服务器并不能感知(服务规则4))，这对服务器来说增加了一个额外的查询时间，既加大了系统延时，又增加了系统能耗.因此，为了减少延迟或进一步降低能耗，需要更加精确地估计服务时间，这就要求保留站点更多的历史状态，以实时地根据门限服务时间Tg和可变K值进行调整.

2 系统仿真及分析

2.1 仿真条件

为了便于分析，在仿真过程中进行如下假设.

1)每个节点在任一时隙内都以均值为λ的相互独立、同分布的概率分布向各自的存储器内送入信息分组.

2)任一节点在接受服务时，由其存储器内向外发送一个信息分组所用的时间变量β服从一个相互独立、同分布的概率分布.

3)不考虑节点位置对传输的影响，节点的转换时间γ为定值，信道为无差错状态.

4)节点的缓存容量足够大，不会出现分组溢出现象.

每轮服务结束后，均形成一个新的服务时间表，结构为(节点号，唤醒时钟)，在具体实现中，轮询服务表和服务时间表是结合在一起的.中心为某节点服务后，依据最近2次状态调整其优先级，根据轮询服务表中后续节点的服务时间，计算下一轮唤醒时刻，预测其分组到达数，更新轮询服务表中该节点的服务数.在仿真中，对忙组内的节点按照限定K=1+σ服务，其中在仿真中，σ采用了一个分段线性增长函数，直至最后逼近到门限值，即

式中:Nl为剩余分组数.

2.2 结果分析

在Matlab仿真环境下，分别对带休眠的纯PCF系统、不访问空闲节点的限定(K=1)服务(设为PCF-noempty系统)和本文提出的PCF-SS 3个系统进行了仿真.在仿真中，以时隙为单位，假定单位服务时间β=10时隙，中心对节点的查询转换时间γ=1时隙，节点的分组到达率λ服从泊松分布.实验对节点数N=20和N=30 2种网络规模进行了仿真比较，主要收集和比较影响系统性能和能耗的平均等待时间、平均排队队长、节点平均晚醒时间量、节点平均早醒时间量、中心平均额外查询时间5个参数，并进行了归一化处理，结果如图2所示.

图2 系统性能比较Fig.2 Comparison of system performances

从图2(a)、2(b)可以看出，由于避免了对空闲节点的访问，PCF-SS、PCF-noempty系统的平均等待时间和平均排队队长与纯PCF系统比，性能显著提高.与PCF-nonempty系统相比，虽然PCF-SS采用了变K服务，但在轻负载下，多数节点依然按照限定(K=1)规则接受服务，所以性能改善不明显;但随着负载的加重，PCF-SS中负载重的节点能够接受可变(K≥1)服务，从而使系统的整体性能得到了提高.

图2(c)、2(d)对非空闲节点的平均晚醒时间和早醒时间进行了比较，在纯PCF系统中，不论节点是否空闲，中心均对其进行轮询，导致空闲节点浪费时间，而有业务的节点却只能休眠到其轮次到来时才能接受服务，相反，其早醒情况就几乎不会发生，所以早醒时间接近0(如图2(d)所示).而当负载变繁重后(如当 N=30，λ ＞0.002，此时 Nλ ×(β+γ)＞0.66)，节点空闲率大大下降，纯PCF 的空轮询也随之减少，节点的晚醒反而开始呈下降趋势.同理，在PCF-noempty系统中，虽然避免了对空闲节点的轮询，但由于采用限定(K=1)服务，即各节点分配的服务时间是相同的，在负载较轻时，周期性休眠后部分节点处于空闲状态，但仍然需要被轮询1次后才能被确认为空闲节点(由休眠机制决定)，相当于增加了非空闲节点的休眠时间(晚醒)，相反，早醒时间就能得到较好控制;随着负载的加重，节点空闲率降低，晚醒也呈明显下降趋势，但上轮空闲的节点在下一轮服务时很可能不再空闲，而非空闲节点并不能感知，依然周期性地醒来，相当于早醒，因此早醒时间呈上升趋势.而在PCF-SS系统中，虽然也需要对空闲节点空轮询1次，但由于采用了服务时间预估计的可变(K≥1)服务，非空闲节点的平均服务时间比PCF-noempty系统要长，空轮询1次的时间在总的服务时间中所占比例减小，等效于节点晚醒时间比值减小，但也因为服务时间是预估的，节点的实际服务时间比估计时间可能还要长，而后续节点依然按照服务时间表上的唤醒时间唤醒，即等效于早醒;因此，在负载不太重时，PCF-SS系统的早醒时间比PCF-noenpty系统有所增加，而随着负载加重，节点几乎都处于忙队列中，实际服务时间与估计服务时间趋于一致，早醒因素变得单一，这与PCF-noempty系统相同，因此两者早醒的走势一致.

图2(e)对中心(簇首)每轮次的平均额外查询时间进行了比较，平均额外查询时间即空闲节点的查询时间，可反映中心的能量浪费度.从图中可以看出，由于纯PCF系统对所有节点都依次轮询，因此能量浪费最大，但随着负载变大，空闲节点数减少，浪费量呈下降趋势.而在PCF-noempty和PCF-SS系统中，由于避免了对空闲节点的轮询，当轻负载时，空闲节点数多，额外查询时间比值很小，随着负载加大，节点在空闲与非空闲间切换，空轮询1次的概率增加，因此额外查询时间逐渐增加;但随着负载变得繁重，系统中几乎不存在空闲节点，空闲查询量又呈下降趋势.由于PCF-SS系统采用了服务时间预估计的可变(K≥1)服务，服务相同量的信息，所用的服务轮次比PCF-noempty少，空闲查询导致的能量浪费量比PCF-noempty系统有所降低，因此PCF-SS系统对延长中心(簇首)寿命更加有利.

3 结束语

本文针对无线传感器网络的MAC层，提出了一种依据节点状态进行资源分配和服务的轮询协议PCF-SS，通过对节点服务时间的预估计，采用统一服务时间表的方式来实现休眠.仿真实验表明，PCF-SS与周期性休眠的PCF机制相比，具有更好的节能效果和时延性能，特别是中心(簇首)的能量浪费大大减少，缓减了中心能量消耗的瓶颈效应，有利于延长网络生命周期.下一步的工作将结合节点的分组到达率分布，对服务K值进行更精确的估计，以进一步提升服务性能，降低等待能耗.

［1］LAN/MAN Standards Committee of the IEEE Computer Society.Part 11:wirelessLAN medium accesscontrol(MAC)and physical layer(PHY)pecifications［S］.New York，USA:IEEE-SA，1999.

［2］杨志军，赵东风，丁洪伟，等.两级优先级控制轮询系统研究［J］.电子学报，2009，37(7):1452-1456.

YANG Zhijun，ZHAO Dongfeng，DING Hongwei，et al.Research on two-class priority based polling system［J］.Acta Electronica Sinica，2009，37(7):1452-1456.

［3］廖勇，杨士中，徐昌彪.自适应 IEEE802.11 PCF调度算法［J］.计算机科学，2007，34(12):46-47，55.

LIAO Yong，YANG Shizhong，XU Changbiao.Adaptive scheme on IEEE 802.11 PCF［J］.Computer Science，2007，34(12):46-47，55.

［4］廖勇，杨士中，徐昌彪.基于NS2的自适应差额IEEE802.11 PCF轮询机制［J］.计算机科学，2009，36(11):36-39，96.

LIAO Yong，YANG Shizhong，XU Changbiao.Adaptive deficit IEEE 802.11 PCF polling scheme based on NS-2［J］.Computer Science，2009，36(11):36-39，96.

［5］CROW B，WIDJAJA I，KIM J G，et a1.IEEE 802.11 wireless loca1 area networks［J］.IEEE Communication Magazine，1997，35(9):116-126.

［6］李琰，朱光喜.3-gated:WLAN中基于负载自适应的动态调度机制［J］.计算机科学，2008，35(4):28-32.

LI Yan， ZHU Guangxi. 3-gated:dynamicscheduling scheme based on load adaptation over WLAN［J］.Computer Science，2008，35(4):28-32.

［7］黄建辉，钱德沛，王胜灵，等.用于无线传感器网络的比例公平队列调度算法［J］.西安交通大学学报，2008，42(2):129-132，151.HUANG Jianhui，QIAN Depei，WANG Shengling，et al.Proportional fairness scheduling algorithm used for wireless sensor network［J］.Journal of Xi’an Jiaotong University，2008，42(2):129-132，151.

［8］石为人，冯会伟，唐云建.一种无线传感器网络MAC层协议设计与实现［J］.计算机科学，2009，36(7):60-62，67.

SHI Weiren，FENG Huiwei，TANG Yunjian.Design and implement of wireless sensor network medium access control protocol［J］.Computer Science，2009，36(7):60-62，67.

［9］SHWE H Y，JIANG Xiaohong，HORIGUCHI S.Energy saving in wireless sensor networks［J］.Journal of Communication and Computer，2009，6(5):20-27.

［10］李云，周娴，尤肖虎，等.IMECN:一种新的无线传感器网络拓扑控制算法［J］.电子学报，2010，38(1):48-53.

LI Yun，ZHOU Xian，YOU Xiaohu，et al.IMECN—a new topology control algorithm for wireless sensor networks［J］.Acta Electronica Sinica，2010，38(1):48-53.

［11］刘亮，秦小麟，戴华，等.能量高效的无线传感器网络时空查询处理算法［J］.电子学报，2010，38(1):54-59.

LIU Liang，QIN Xiaolin，DAI Hua，et al.An energy efficient spatio-temporal query processing algorithm in wireless sensor networks［J］.Acta Electronica Sinica，2010，38(1):54-59.

［12］徐石玉，栾晓明.基于分簇的无线传感器网络时间同步方法［J］.应用科技，2010，37(6):27-30.

XU Shiyu，LUAN Xiaoming.Cluster-based time synchronization method for wireless sensor networks［J］.Applied Science and Technology，2010，37(6):27-30.

［13］EU Z A，TAN H P，SEACH W K G.Design and performance analysis of MAC schemes for wireless sensor networks powered by ambient energy harvesting［J］.Ad Hoc Networks，2011，9(3):300-323.