第7卷第3期 智能系统学报 Vol.7 No.3 2012年6月 CAAI Transactions on Intelligent Systems Jun.2012 D0I:10.3969/i.issn.16734785.201110002 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120518.0839.001.html 一种能量有效的无线传感器网络轮询接入控制协议 何敏，赵东风，保利勇，左朝树 (1.云南大学信息学院，云南昆明650091：2.西南通信研究所保密通信重点实脸室，四川成都610041) 摘要：周期性休眠的PCF机制虽然较好地解决了无线传感器网络的能耗问题，但没有考虑节点的负载状态，降低 了系统性能，也增加了系统的查询能耗.以限定(K=1)服务为基础，提出了一种改进的PCP轮询控制协议，即具有混 合服务策略的无线传感器网络轮询接入控制协议P℃F-SS.该协议在保障公平性的前提下，能够根据节点状态动态调 整优先级并改变服务K值，中心服务器AP则根据各节点的服务K值在每轮服务时对节点的下一轮服务时间进行预 估计，并采用统一的服务时间表唤醒节点，达到节能的效果.仿真实验表明系统的平均等待时间、平均排队队长等性 能指标比周期性休眠的P℃℉机制要好，能量的有效利用率更高，具有更长的生命周期，适合作为无线传感器网络的 MAC控制协议. 关键词：无线传感器网络：PCF;能量有效；轮询服务；接入控制；轮询接入控制 中图分类号：TP393文献标志码：A文章编号：1673-4785(2012)03026506 An energy-efficiency polling access control protocol for wireless sensor networks HE Min',ZHAO Dongfeng',BAO Liyong',ZUO Chaoshu? (1.School of Information Science and Engineering,Yunnan University,Kunming 650091,China;2.Science and Technology on Com- munication Security Laboratory,Southwest Institute of Communication,Chengdu 610041,China) Abstract:Although the energy waste is well controlled on the medium access control (MAC)layer under the peri- odic sleeping point coordination function(PCF)scheme in wireless sensor networks(WSN),the system perform- ance declined and the system query energy cost increased because the node loads were ignored.Based on the limit- ed service(K=1),an improved PCF polling control protocol,which is known as the point coordination function by the site status (PCF-SS)for WSN,was proposed.The priority of a node was variable by its status and the service K was correspondingly changed using this protocol.Therefore,the service time of the next turn could be assigned dynamically according to its status when the AP server came to service a node.Also,the nodes were awakened by a uniform service time table which was used to save their power.The experimental results indicate that the perform- ances,such as the mean value of queue length and message waiting time,are better than when using the periodic sleeping PCF scheme.The energy usage is more efficient and the lifecycle is longer,making it suitable for the MAC protocol of WSN. Keywords:wireless sensor networks (WSN);point coordination function(PCF);energy efficiency;polling serv- ice;access control;polling access controll 无线传感器网络（wireless sensor networks, 医疗、建筑物监测、智能家居和安全报警、反恐和公 WSN)综合了传感器技术、嵌入式计算技术、分布式 共安全、商业等领域都有重要的科研价值和广阔的 信息处理技术和无线通信技术，在军事、环境监测、 应用前景.由于传感器节点通常依靠电池供电，能量 收稿日期：2011-10-11.网络出版日期：2012-05-18. 有限，不能直接应用在现有的无线通信协议中，通常 基金项目：国家自然科学基金资助项目(61072079)：云南省教育厅科 的解决办法是采用休眠机制，减少节点在空闲时期 学研究基金资助项目(09y0042). 通信作者：何敏.E-mail:heather_.hee@163.com. 的能耗.随机竞争接入能为突发性数据提供灵活的
266 智能系统学报 第7卷 服务，且控制相对简单，目前部分应用采用基于 每个节点可处于休眠、活跃、发送3种状态之 802.11的竞争类协议，但如何降低碰撞造成的能量 一，分别对应空闲、唤醒（或请求服务）和接受服务， 消耗是这类协议的一个难题、 由相应的条件触发转换，如图1所示.初始布置后， 轮询方式既避免了碰撞，又能提供具有QS保 当终端节点有分组发送时，即向中心发送请求，与中 障的服务，因此被广泛应用到MAC协议的设计中. 心握手后，加入服务队列，获得服务时间表，进入休 研究人员在纯PCF(point coordination function)U系 眠等待，以减少能量消耗.如果较长时间没有分组发 统的基础上，提出了一系列的改进算法28]，如两级 送，中心则将该节点从服务队列中删除，以减少空轮 优先级轮询[2]、自适应调度3]、自适应差额调度4 询次数，提高服务效率，直到节点有新的分组到达 等改进的PCF系统.这些系统通过对服务策略、调 时，再次苏醒并申请加入服务队列.如果中心在一段 度机制的深入研究，改进了纯PCF系统的性能.文 时间内没有收到任何服务请求，也将转入短暂的休 献[5]将没有处在激活状态的站点从轮询列表中删 眠，并在下一时刻醒来后，监测信道，准备服务 除，网络性能得到了显著的提高.文献[6]通过3级 请求服务 门限服务方式，较好地解决了实时业务在重负载下 分组到达 时延Qos不能得到满足的问题；但是对于低速传感 无分组 活跃 器网络的节点来说，可能导致部分节点较长时间占 休眠 休眠 AP 用信道，欠缺公平性.文献[7]通过为不同业务类别 空闲 时间到 等待服务 询 分配服务配额的方式，采用加权轮询调度策略，以业 (初始化 务的平均分组到达率为依据，降低了排队的复杂度。 文献[8]基于Zigbee技术，需要服务的节点采用CS 发送 服务完毕，触 MA/CA机制接入，中心采用轮询方式为各节点服 发休眠定时器 务，没有服务需求的节点则休眠以节约能量；但节点 图1节点状态转移图 在接入后不断发送POLL请求，在ACK响应前一直 Fig.1 Status migration of a node 处于活跃状态，会造成能量浪费.不少学者也提出了 采用上述接入方法，终端节点可能会被延迟服 一系列节能策略B],从不同层面解决WSN的能耗 务或提早苏醒，这种情况将在1.3节中进行分析. 问题 1.2服务策略 本文在周期性休眠的PCF基础上，提出了一种 通常情况下，轮询系统中的各节点都能获得固 具有节能效果的轮询控制协议PCF-SS(point coordi- 定、均匀的服务时间，这对于对称型的系统是合理 nation function by site status),在保证公平性的前提 的.但是在实际应用中，节点的负载往往是不均衡 下，依据节点状态进行资源分配和服务.其基本思想 的，根据需求进行可变配置的服务方式普遍存在.因 是：中心在为某节点服务的同时获取该站点的剩余 此，系统以限定(K=1)服务为基础，根据节点繁忙 分组信息，且至少保留连续2轮的状态信息，并依据 程度划分优先级，分别对节点上一轮分组剩余量、本 节点状态将其分配到不同优先级组内；同时，根据节 轮分组剩余量进行标识区分，并划分为4类，如表1 点最近2次的状态估计下一轮的服务时间，并将预 所示。 计的开始服务时刻在本轮服务结束前通知该节点， 表1节点负载状态 当节点接受服务后，即可转入休眠，直到下一轮服务 Table 1 The loads status of nodes 时刻的到来，达到节能目的 负载分类优先级 服务策略 所属队列 1PCF-SS接入控制机制分析 空负载 0 不轮询 空闲队列 轻载 限定(K=1) 轻载队列 1.1PCF-SS接入过程描述 传感器网络节点能量和功率有限，导致传输距 较重负载 可变(K≥1) 忙队列 离有限.同时，在多数应用中，传感器网络一旦部署， 重负载 3 门限服务 繁忙队列 节点的移动性很小，甚至不发生移动.分簇是实施分 具体的服务方式如下 层控制的重要方法之一，PCF-SS协议适用于簇内节 1)初始时，系统按照限定(K=1)服务规则对N 点与中心（簇首）的通信，信息通过簇首间的转发到 个节点进行依次服务，在服务过程中，根据节点的负 达Sink. 载状态，将其划人到不同的优先级组内
第3期 何敏，等：一种能量有效的无线传感器网络轮询接入控制协议 ·267 2)轻载队列采用限定(K=1)服务；忙队列采用 间表上的时间唤醒，相当于节点早醒.上述2种情况 可变(K≥1)服务，即在限定(K=1)的基础上，根据 是休眠策略不可避免的，晚醒将增加系统时延，早醒 节点当前状态和上轮状态进行预判，调整优先级及 则会增加节点的能耗，此外，当前节点可能没有分组 下一轮的服务时间；繁忙队列采用门限服务规则.节 发送，但服务器并不能感知（服务规则4）)，这对服 点接受服务后，转人休眠状态 务器来说增加了一个额外的查询时间，既加大了系 3)中心根据服务时间表中剩余节点和前驱节 统延时，又增加了系统能耗.因此，为了减少延迟或 点的预计服务时间，估算各节点下一轮服务的开始 进一步降低能耗，需要更加精确地估计服务时间，这 时间，并在服务结束前通知该节点， 就要求保留站点更多的历史状态，以实时地根据门 4)由于节点接受服务后转入休眠状态，服务器 限服务时间T.和可变K值进行调整 不能感知其后续是否有分组到达，因此，轻载组内的 2 节点被服务后，即使处于空闲状态，也被划分到轻负 系统仿真及分析 载组，直到下一轮服务时，仍然空闲才转入空闲组 2.1仿真条件 中，并将其从轮询列表中删除 为了便于分析，在仿真过程中进行如下假设， 5)优先级高的节点采用逐级向下调整的策略 1)每个节点在任一时隙内都以均值为入的相 调整其优先级，而低优先级的节点则根据状态直接 互独立、同分布的概率分布向各自的存储器内送入 调整到相应的优先级组 信息分组， 6)空闲节点一直处于休眠状态，直到有分组到 2)任一节点在接受服务时，由其存储器内向外 达，再申请接入网络接受服务， 发送一个信息分组所用的时间变量B服从一个相互 7)每次服务结束后，中心都将进行信道检测， 独立、同分布的概率分布， 如果有新节点加入，则将其安排到轮询列表的最后 3)不考虑节点位置对传输的影响，节点的转换 根据统计原理，参与预测的历史状态次数越多， 时间y为定值，信道为无差错状态， 预测值就越可靠，但运算也越复杂，额外开销越大， 4)节点的缓存容量足够大，不会出现分组溢出 因此，系统选取节点最近2轮的状态进行预判.此 现象 时，中心存储的轮询列表结构可表示为（节点号，服 每轮服务结束后，均形成一个新的服务时间表， 务顺序号，上轮剩余分组数，本轮剩余分组数，预分 结构为（节点号，唤醒时钟），在具体实现中，轮询服 配服务数)，以1号站点为例，初始时刻表示为(1， 务表和服务时间表是结合在一起的.中心为某节点 100,K) 服务后，依据最近2次状态调整其优先级，根据轮询 1.3服务时间表 服务表中后续节点的服务时间，计算下一轮唤醒时 中心采用统一的服务时间表来确定各节点的服 刻，预测其分组到达数，更新轮询服务表中该节点的 务时间和唤醒时刻.当中心为某节点服务时，根据其 服务数.在仿真中，对忙组内的节点按照限定 状态预判下一轮的服务时间，决定该节点的唤醒时 K=1+σ服务，其中在仿真中，σ采用了一个分段线 刻，更新服务时间表，当节点接受服务后，转入休眠 性增长函数，直至最后逼近到门限值，即 状态并启动一个唤醒时钟， r1,N>1; 采用服务时间表带来的一个问题是节点可能延 2,N>3; 迟苏醒（晚醒）或提前苏醒（早醒），前者是因为中心 3,N>5. 对剩余节点的服务规则可能是门限或可变(K≥1) 式中：N为剩余分组数. 服务，而节点的分组到达数量是随机的，因此门限服 2.2结果分析 务和可变(K≥1)服务所耗费的时间是不确定的.为 在Matlab仿真环境下，分别对带休眠的纯PCF 此设定了一个门限值T。来确定门限服务时间，中心 系统、不访问空闲节点的限定(K=1)服务（设为 可能不需要T。时间就能完成对某节点的门限服务， PCF-noempty系统)和本文提出的PCF-SS3个系统 这对后续节点来说，相当于延迟苏醒；同理，对可变 进行了仿真.在仿真中，以时隙为单位，假定单位服 (K≥1)服务也一样，当节点中的分组数少于K个 务时间B=10时隙，中心对节点的查询转换时间 时，也将引入延迟.后者正好相反，当中心对某节点 y=1时隙，节点的分组到达率入服从泊松分布.实 的门限服务在T。时间内不能完成时，将推迟后续节 验对节点数N=20和N=302种网络规模进行了仿 点的服务时间，但后续节点并不能感知，仍然按照时 真比较，主要收集和比较影响系统性能和能耗的平
268 智能系统学报 第7卷 均等待时间、平均排队队长、节点平均晚醒时间量、 节点平均早醒时间量、中心平均额外查询时间5个 1.0 PCE-SS 参数，并进行了归一化处理，结果如图2所示 0.8 0.6 200 175 0.4 /W=30 150 N=30 0.2 125 N=20 100 N=20 0.5 .5 2.5 75 3.5 50 到达率 (e)中心平均额外查询时间的比较(B=10,y=1) 851.0152.0253.0354ǒ10 图2系统性能比较 到达率入 Fig.2 Comparison of system performances (a)节点平均等待时间的比较(B=10,y=1) 从图2(a)、2(b)可以看出，由于避免了对空闲节 点的访问，PCF-SS、PCF-noempty系统的平均等待时 1.0 --PCF-SS 间和平均排队队长与纯PCF系统比，性能显著提高 0.8 -PCF-noempty PCF 与PCF-nonempty系统相比，虽然PCF-SS采用了变K 0.6 20 服务，但在轻负载下，多数节点依然按照限定(K=1) 0.4 规则接受服务，所以性能改善不明显；但随着负载的 0.2 加重，PCF-SS中负载重的节点能够接受可变(K≥1) 服务，从而使系统的整体性能得到了提高。 0年 0.51.01.5 20253.03540X10 到达率 图2(c)、2(d)对非空闲节点的平均晚醒时间 和早醒时间进行了比较，在纯PCF系统中，不论节 (b)节点平均排队队长的比较(B=10,y=1) 点是否空闲，中心均对其进行轮询，导致空闲节点浪 费时间，而有业务的节点却只能休眠到其轮次到来 时才能接受服务，相反，其早醒情况就几乎不会发 -P℃F-SSN-20) -PCF-noempty 生，所以早醒时间接近0（如图2(d)所示）.而当负 PCF PCF-SS(N-30) 载变繁重后（如当N=30,入>0.002，此时W入× 15 N=20 (B+y)>0.66),节点空闲率大大下降，纯PCF的空 10 =30 轮询也随之减少，节点的晚醒反而开始呈下降趋势. 同理，在PCF-noempty系统中，虽然避免了对空闲节 0 10 0.5 1.5 2.5 3.5 点的轮询，但由于采用限定(K=1)服务，即各节点 到达率 分配的服务时间是相同的，在负载较轻时，周期性休 (c)节点平均晚醒时间的比较(B=10,y=1) 眠后部分节点处于空闲状态，但仍然需要被轮询1 次后才能被确认为空闲节点（由休眠机制决定），相 当于增加了非空闲节点的休眠时间（晚醒），相反， 2.0 -PCF-SS 早醒时间就能得到较好控制；随着负载的加重，节点 1.6 -PCF noempty -PCF( =20 -PCFIN=30) 空闲率降低，晚醒也呈明显下降趋势，但上轮空闲的 1.2 -30 节点在下一轮服务时很可能不再空闲，而非空闲节 0.8 N-20 点并不能感知，依然周期性地醒来，相当于早醒，因 0.4 此早醒时间呈上升趋势.而在PCF-SS系统中，虽然 0 也需要对空闲节点空轮询1次，但由于采用了服务 .5 2.5 3.5 *10 到达率 时间预估计的可变(K≥1)服务，非空闲节点的平均 服务时间比PCF-noempty系统要长，空轮询1次的 (d)节点平均早醒时间的比较(B=10,y=1) 时间在总的服务时间中所占比例减小，等效于节点
第3期 何敏，等：一种能量有效的无线传感器网络轮询接入控制协议 ·269· 晚醒时间比值减小，但也因为服务时间是预估的，节 Research on two-class priority based polling system[J].Ac- 点的实际服务时间比估计时间可能还要长，而后续 ta Electronica Sinica,2009,37(7):1452-1456 节点依然按照服务时间表上的唤醒时间唤醒，即等 [3]廖勇，杨士中，徐昌彪.自适应EEE802.11PCF调度算 效于早醒；因此，在负载不太重时，PCF-SS系统的早 法[J].计算机科学，2007,34(12)：4647,55， LIAO Yong,YANG Shizhong,XU Changbiao.Adaptive 醒时间比PCF-noenpty系统有所增加，而随着负载 scheme on IEEE 802.11 PCF J].Computer Science, 加重，节点几乎都处于忙队列中，实际服务时间与估 2007,34(12):4647,55. 计服务时间趋于一致，早醒因素变得单一，这与 [4]廖勇，杨士中，徐昌彪.基于NS2的自适应差额EEE802. PCF-noempty系统相同，因此两者早醒的走势一致. 11PCF轮询机制[J].计算机科学，2009,36(11)：36 图2(e)对中心（簇首）每轮次的平均额外查询 39,96 时间进行了比较，平均额外查询时间即空闲节点的 LIAO Yong,YANG Shizhong,XU Changbiao.Adaptive 查询时间，可反映中心的能量浪费度.从图中可以看 deficit IEEE 802.11 PCF polling scheme based on NS-2 出，由于纯P℃F系统对所有节点都依次轮询，因此 [J].Computer Science,2009,36(11):36-39,96. 能量浪费最大，但随着负载变大，空闲节点数减少， [5]CROW B,WIDJAJA I,KIM J G,et al.IEEE 802.11 浪费量呈下降趋势.而在PCF-noempty和PCF-SS系 wireless local area networks J].IEEE Communication Magazine,1997,35(9):116-126. 统中，由于避免了对空闲节点的轮询，当轻负载时， [6]李球，朱光喜.3-gated:WLAN中基于负载自适应的动态 空闲节点数多，额外查询时间比值很小，随着负载加 调度机制[J].计算机科学，2008,35(4)：2832， 大，节点在空闲与非空闲间切换，空轮询1次的概率 LI Yan,ZHU Guangxi.3-gated:dynamic scheduling 增加，因此额外查询时间逐渐增加；但随着负载变得 scheme based on load adaptation over WLAN[J].Computer 繁重，系统中几乎不存在空闲节点，空闲查询量又呈 Science,2008,35(4):28-32. 下降趋势.由于P℃F-SS系统采用了服务时间预估计 [7]黄建辉，钱德沛，王胜灵，等.用于无线传感器网络的比 的可变(K≥1)服务，服务相同量的信息，所用的服 例公平队列调度算法[J].西安交通大学学报，2008,42 务轮次比PCF-noempty少，空闲查询导致的能量浪 (2):129-132,151. 费量比PCF-noempty系统有所降低，因此PCF-SS系 HUANG Jianhui,QIAN Depei,WANG Shengling,et al. Proportional fairness scheduling algorithm used for wireless 统对延长中心（簇首）寿命更加有利， sensor network[J].Joumal of Xi'an Jiaotong University, 3结束语 2008,42(2):129-132,151. [8]石为人，冯会伟，唐云建.一种无线传感器网络MAC层 本文针对无线传感器网络的MAC层，提出了一 协议设计与实现[J].计算机科学，2009,36(7)：6062， 种依据节点状态进行资源分配和服务的轮询协议 67. PCP-SS,通过对节点服务时间的预估计，采用统一 SHI Weiren,FENG Huiwei,TANG Yunjian.Design and 服务时间表的方式来实现休眠。仿真实验表明， implement of wireless sensor network medium access control PCF-SS与周期性休眠的PCF机制相比，具有更好的 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 Commu- nication and Computer,2009,6(5):20-27. 于延长网络生命周期.下一步的工作将结合节点的 [10]李云，周娴，尤肖虎，等.MECN:一种新的无线传感器网 分组到达率分布，对服务K值进行更精确的估计， 络拓扑控制算法[J].电子学报，2010,38(1)：4853. 以进一步提升服务性能，降低等待能耗 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. [1]LAN/MAN Standards Committee of the IEEE Computer So- [11]刘亮，秦小麟，戴华，等.能量高效的无线传感器网络时 ciety.Part 11:wireless LAN medium access control 空查询处理算法J].电子学报，2010,38(1)：5459. (MAC)and physical layer (PHY)pecifications[S].New LIU Liang,QIN Xiaolin,DAI Hua,et al.An energy effi- York,USA:IEEE-SA,1999. cient spatio-temporal query processing algorithm in wireless [2]杨志军，赵东风，丁洪伟，等.两级优先级控制轮询系统 sensor networks[J].Acta Electronica Sinica,2010,38 研究[J].电子学报，2009,37(7)：1452-1456. (1):54-59 YANG Zhijun,ZHAO Dongfeng,DING Hongwei,et al. [12]徐石玉，栾晓明.基于分簇的无线传感器网络时间同步
.270. 智能系统学报 第7卷 方法[J].应用科技，2010,37(6)：2730. 赵东风，男，1957年生，教授，博士 XU Shiyu,LUAN Xiaoming.Cluster-based time synchro- 生导师，中国电子学会高级会员，教育 nization 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 perform- 与技术”学科带头人.主要研究方向为 ance analysis of MAC schemes for wireless sensor networks 通信网络理论、传感器网络、电磁环境 powered by ambient energy harvesting[J].Ad Hoc Net- 评估、网络系统仿真、机器人控制等.主持多项国家自然科学 w0rks,2011,9(3):300-323. 基金项目和国防军工项目，发表学术论文200余篇，被SC1、 作者简介： EI和ISTP检索40余篇 何敏，女，1975年生，副教授，博士， 主要研究方向为计算机网络与通信、轮 保利勇，男，1975年生，副教授，博 询系统理论、嵌入式应用等。 士，主要研究方向为计算机通信与网 络、轮询系统理论 The 15th International Conference on Human-Computer Interaction 第15届人机交互国际会议 The HCI Intemational 2013 Conference Proceedings,will be published by Springer in a multi-volume set.Papers will ap- pear in volumes of the Lecture Notes in Computer Science (LNCS)and Lecture Notes in Artificial Intelligence (LNAI) series.Extended Poster abstracts will be published in the Communications in Computer and Information Science (CCIS) series. All volumes will be available on-line through the SpringerLink Digital Library,readily accessible by all subscribing librar- ies around the world,and will be indexed by a number of services including EI and ISI CPCI-S. Important Dates Papers: Deadline for Abstract Receipt:12 October 2012 Notification of Review Outcome:30 November 2012 Deadline for Camera-ready Receipt:1 February 2013 Posters: Deadline for Abstract Receipt:1 February 2013 Notification of Review Outcome:22 February 2013 Deadline for Camera-ready Receipt:22 March 2013 Tutorials: Deadline for Abstract Receipt:12 October 2012 Notification of Review Outcome:9 November 2012 Deadline for Camera-ready Receipt:10 May 2013 Website:http://www.hcii2013.org/index.php