并行调度两级轮询控制传感器网络MAC协议分析

官铮,邹丹,丁洪伟,钱文华

(1. 云南大学 信息学院，云南 昆明 650091； 2. 云南开放大学 机械与电子工程学院，云南 昆明 650091)

典型的无线传感器网络采用分层结构，由簇首节点收集子网中的数据并向上层节点转发最终传输到汇聚点，形成了一颗以汇聚节点为根的数据传输树。在树结构中作为簇首的节点相对普通数据采集节点具有更高的网络负载，为了避免由信息传输累积造成的拥塞，保障数据传输时延，传输过程中应为簇首节点分配更多的网络资源。 近年来，各国学者针对传感器网络的QoS保障问题做出了大量研究[1-2]，包括MAC(medium access control)、路由层到传输层的优化设计。介质访问控制协议决定着无线信道的使用方式，负责为节点分配无线通信资源，直接影响网络整体性能，受到了广泛的关注，从不同角度改善了网络的时延性能和时间同步条件[3-6]。然而，考虑网络流量不平衡环境下节点的区分优先级的控制协议相对较少。基于两级轮询控制的MAC协议可实现区分节点优先级的服务[7-9]，但数据传输权频繁地在普通节点和中心节点间切换，使得查询转化开销较大。针对上述问题，本文提出一种两级轮询并行调度MAC协议(parallel two-level polling control based MAC protocol, PTLP-MAC)优化算法，利用捎带技术实现了数据传输和查询转换的并行处理，从而减少查询转换开销、降低时延；最后通过仿真实验与已有方法对比证明了协议在时延特性方面的改进。

1 PTLP-MAC协议设计

假设网络中所有传感器节点都静止，Sink节点位于网络区域中心位置，传感器节点按照与Sink的距离划分为层，各层位于单跳范围内的节点组成簇，簇首为位于相邻内层一跳可达的节点，负责按照PTLP-MAC协议管理簇内节点，并对来自簇内成员节点的数据进行汇聚和融合。

1.1 接收者驱动的区分优先级并行调度

PTLP-MAC采用异步传输。数据的传递由接收者发起，负责数据收集的Sink节点(包括各层簇首节点)按预先指定的顺序向成员节点发送数据请求，节点收到请求信息后发送数据，这样可有效地避免冲突，且无需保持采集节点的全局同步，收到成员节点发送的数据包后回复ACK确认。

考虑到分层结构带来的节点间流量不均，PTLP-MAC从数据流量和节点在网络结构中的影响度考虑，将具有较高的数据流量和实时性要求的簇首设为中心节点，其余成员节点视为普通节点，通过以下策略能为中心节点和普通节点提供区分优先级服务：

1)调度顺序：以1, 2, …,N表示簇内的N个普通节点，H表示中心节点。Sink节点按照1→H→2→…→N→H的顺序向簇内节点请求数据，由此，簇首节点可获得更多的信道使用机会。

2)服务策略：每次收到来自Sink节点的数据请求后，普通节点只允许发送一个数据包，中心节点允许发送在缓冲区中排队等待的所有数据包(包括发送期间新到达的数据包)。

最后，协议采用捎带机制，在Sink节点回复的ACK确认包中捎带数据请求信息，成员节点通过侦听ACK帧判断自己是否为数据请求对象，从而实现数据传输和请求过程的并行处理，减少数据请求占用的时间来达到降低时延的目的。

1.2 介质访问控制机制

表1所示为各类节点需要维护的信息。

表1 节点保留参量

如图1所示，PTLP-MAC在IEEE802.15.4基础上引入3种信息包类型，数据请求包、数据包和确认包，接收者根据Type字段判断收到的信息类型。

图1 PTLP-MAC信息包格式Fig.1 PTLP-MAC packet format

并行调度机制主要通过ACK实现。当汇聚节点收到来自采集节点的数据包后发送ACK进行确认，簇内其他活动节点侦听该ACK信号，判断自己是否为下一请求对象。如果ACK中的Dest为普通节点地址，则中心节点判断自己为下一数据请求对象，立即发送数据；若Dest为中心节点地址，且Dsn字段为0，则普通节点判断自己为数据请求对象，立即发送数据。

并行调度方式下ACK需要增加Dsn及SNEXT字段用于携带请求信息，但相对于非并行调度策略中，Sink节点针对每个节点均需要发送数据请求包，采用并行调度策略从请求时间和流量占用上均有所节约。

各类节点介质访问控制算法如下所示。

算法1 Sink节点控制算法。

1)向中心节点发送数据请求包。

2)接收数据，当收到最后一个数据后，按轮询表顺序在ACK中捎带普通节点请求信息；若超时未收到数据，则按轮询表顺序向下一节点发送数据请求包。

3)接收1个数据包，在ACK中捎带中心节点数据请求信息；若超时未收到数据包，则进行1)。

算法2 中心节点控制算法。

1)数据到达进入活动状态，侦听信道；

2)若侦听到数据请求，则发送数据；若侦听到ACK，则发送数据；

3)按完全服务策略发送完所有数据后，进入休眠状态。此后若有新数据到达则进行1)。

算法3普通节点控制算法。

1)数据到达进入活动状态，侦听信道。

2)若侦听到数据请求，则发送1个数据包；若侦听到ACK，根据Dsn和SNEXT判断是否传输数据，若是则发送1个数据包。

3)若缓冲为空则休眠，此后若有新数据到达则进行1)；若缓冲区不为空则继续侦听。

基本的RR调度算法实现一般很简单，而且具有良好的O(1)时间复杂性和可扩展性，但无法提供时延保证。两级轮询机制在RR调度的基础上通过服务路径(调度顺序)区分中心节点和普通节点，为中心节点提供较高的时延特性保障，算法复杂度为O(N)，相比已有两级轮询控制机制，PTLP-MAC增设的捎带机制并未增加算法复杂度。

1.3 PTLP-MAC实例

图2 给出了一个PTLP-MAC的实例。假设子网中存在1个汇聚节点和3个采集节点，S表示汇聚节点，0号节点为簇首节点，1号和2号节点为成员节点。图2所示为子网范围内完成一轮数据传输的过程：

t1：S向0号节点发送数据请求包，0号节点接收后向S发送数据，直至缓存区为空，完成发送后进入休眠状态，直至下一个数据到达后被唤醒。S收到来自0号节点的数据包后，发送ACK确认。

t2：S向0号节点发送最后一个数据包的ACK，将Dsn字段设为0，向下一节点请求数据。

t3：1号节点侦听到ACK后确认自己为下一请求节点，向S发送数据。

t4：S向1号节点发送ACK，0号节点因有分组到达已被唤醒，通过侦听其中Dest字段为普通节点地址，从而判断自己为下一数据请求对象，开始发送数据。

t5：S向0号节点发送最后一个数据包的ACK，其中将Dsn字段设为0，对下一节点请求信息。

t6：2号节点因处于休眠状态未响应S请求；S节点等待超时后，向0号中心节点发送数据请求帧。

t7：0号节点处于休眠状态未响应请求，等待超时后，S向1号节点发出数据请求。

图2 PTLP-MAC信息包格式Fig.2 PTLP-MAC packet format

2 仿真实验及数值分析

2.1 PTLP-MAC仿真

为了验证论文所建数学模型对PTLP-MAC性能分析的正确性和有效性，利用MATLAB 7.0对协议运行情况进行仿真，对各节点平均排队队长和数据平均等待时延进行统计。模拟环境设置如下：假设网络规模从6节点增至81节点，节点均匀分布；采用11 Mbps信道，数据包长度为1 100 Byte，定义1个时隙宽度为20 μs，归一化后数据采集节点数据的采集率为0.002 (数据包/时隙)，发送一个数据包需5(时隙)，Sink节点完成一次数据请求时间为2(时隙)。

表2所示节点在轮询时刻其缓冲区中平均等待的数据包数，表3所示为节点中数据包等待发送的平均等待时延。

表2 信息分组平均排队队长(数据包)

表3 信息分组平均等待时延(时隙)

将仿真得到的中心节点和普通节点仿真实验结果对比，比较显示，当网络规模和系统负载随节点数增大时，节点缓冲区中平均等待的数据包数量和数据平均等待时延均有所增加，中心节点中平均等待发送的数据包数量和数据包平均等待时延均明显小于普通节点，因此PTLP-MAC能为中心节点提供较好的时延保证，有效实现节点优先级区分，避免数据在传输汇聚树中的根节点处发生拥塞。

2.2 轮询控制MAC协议比较

目前基于调度的MAC协议在调度策略和休眠机制上各有所长，但信道接入方式大多基于Round Robin控制方式；另外，文献[8]中提出了离散时间两级轮询控制策略以实现节点优先级的区分，本文在此基础上通过发送和请求的并行处理以减小查询请求开销，将对PTLP-MAC、文献[8]及Round Robin (RR)进行比较，主要从时延保障角度出发，针对平均循环查询周期、发送时刻节点缓冲区的平均排队队长和数据发送平均等待时延等进行分析比较，对本文所述控制协议进行性能评估。

2.2.1 平均循环周期

平均循环周期定义为Sink节点按查询表顺序对成员节点完成一轮数据请求耗费的平均时间。图3为普通节点数从5增加到80，网络平均循环周期的变化趋势。

图3 平均循环周期Fig.3 Mean cycle time

随着节点数的增加，文献[8]平均循环周期略大于RR，这是由于文献[8]通过增加请求次数来保障对中心节点的高优先级服务，但也增加了数据请求开销，PTLP-MAC通过ACK捎带节约了数据请求时间，随着网络负载加大后捎带更易实现，因此随着节点数的增加，PTLP-MAC在平均循环周期上的优势更加明显。

2.2.2 平均排队队长

平均排队队长定义为成员节点在响应数据请求时，其缓冲区内排队等待发送的平均数据包数量。文献[8]和PTLP-MAC节点被区分为中心节点和普通节点2类，在此将分别讨论。由于RR中没有对节点类型进行区分，所有节点公平接入，而文献[8]及PTLP-MAC通过查询路径和服务策略的设置将更多的信道接入机会分配给中心节点，因此，如图4所示，文献[8]及PTLP-MAC中心节点平均排队队长明显低于RR。将2类两级轮询控制方式下的中心节点平均排队队长进一步进行比较，如图5曲线图所示，PTLP-MAC控制下的平均排队队长小于文献[8]。由于文献[8]中Sink每次向普通节点发送请求之前都要优先向中心队列请求数据，相当于增加了相邻2个普通队列发送数据的时间间隔，因此如图6所示在相同网络环境下，文献[8]普通节点平均排队队长略大于RR。相比之下PTLP-MAC由于将数据发送和请求并行处理，如图4～6所示，该方法在确保中心节点优先级的同时也对普通节点的服务质量提供保障，2类节点排队队长均小于RR。

图4 中心结点平均排队队长比较Fig.4 Comparison of average packets length in key node

图5 两级轮询机制中心节点平均排队队长比较 Fig.5 Comparison of average packets length in center node between two-level polling schemes

图6 普通节点平均排队队长Fig.6 Average packets length in normal nodes

2.2.3 平均等待时延

平均等待时延定义为从数据包进入节点到被允许发送的平均时间间隔。图6～7所示为3类轮询控制策略下节点中数据的平均等待时延，由于PTLP-MAC在查询路径和服务策略上的设置，使中心节点中数据包的平均等待时延远低于普通节点，另外采用ACK捎带请求信息，可减小数据请求包的发送数量，尤其在高负载环境下显著降低了数据请求开销。图7是PTLP-MAC与文献[8]和RR的中心节点平均等待时延的比较，其中PTLP-MAC与文献[8]的时延明显低于RR，为进一步对比PTLP-MAC和文献[8]，将对比图中相关部分在图8放大显示，如图9所示，PTLP-MAC中心节点的时延特性低于文献[8]。

图7 中心结点平均等待时延Fig.7 Average waiting time in center node

图8 两级轮询机制中心节点平均等待时延比较Fig.8 Comparison of average waiting time in center node between two-level polling schemes

图9 普通节点平均等待时延Fig.9 Average waiting time in normal nodes

3 结束语

本文针对基于调度的无线传感器网络轮询控制MAC协议族在时间同步以及非均衡传输等方面的不足，从时延保障的角度出发，提出了一种接收者发起的两级轮询控制并行调度MAC协议优化算法。协议根据节点数据流量及在分层结构中的身份(簇首或成员)，将节点划分为中心节点和普通节点，通过轮询过程中轮询路径以及服务方式的设置为中心节点分配了更多的信道资源，同时采用ACK捎带技术实现数据发送和请求的并行处理，有效降低数据等待时延，且控制过程中无需进行全局时间同步。此外，本文采用嵌入式马尔可夫链和概率母函数的方法对提出的进行数学建模并实现了平均循环周期、平均排队队长和平均等待时延等关键参数的精确解析，从理论上证明了该协议在确保时延性能上的有效性。

参考文献:

[1]文浩,林闯,任丰原,等.无线传感器网络的QoS体系结构[J]. 计算机学报, 2009, 32(3): 432-440.

WEN Hao， LIN Chuang， REN Fengyuan， et al. QoS architecture in wireless sensor network[J]. Chinese Journal of Computers, 2009, 32(3): 432-440.

[2]TAN J, SHROFF N B. Transition from heavy to light tails in retransmission durations[C]//IEEE INFOCOM. San Diego, USA, 2010: 1-9.

[3]RAJENDRAN V, OBRACZKA K, GARCIA J J. Energy-efficient, collision-free medium access control for wireless sensor networks[C]//Proceedings of the ACM SenSys. Los Angeles, 2003: 181-192.

[4]SALAJEGHEH M. HyMAC: hybrid TDMA/FDMA medium access control protocol for wireless sensor networks[C]//Proceedings of PIMRC. Athens, Greece, 2007: 1-5.

[5]张德升,李金宝,郭龙江.基于多信道预约的传感器网络MAC协议研究[J]. 通信学报, 2011, 32(4): 126-137.

ZHANG Desheng, LI Jinbao, GUO Longjiang. Study on multi-channel reservation based MAC protocol for sensor networks[J]. Journal on Communications, 2011, 32(4): 126-137.

[6]YANG P, ZI L, DAJI Q, et al. Delay-bounded MAC with minimal idle listening for sensor networks[C]//IEEE INFOCOM. Shanghai, China, 2011: 1314-1322.

[7]刘强,张中兆,张乃通. 排队优先权站点轮询系统的平均周期时间[J] . 通信学报, 1999, 20 (2): 86-91.

LIU Qiang, ZHANG Zhongzhao, ZHANG Naitong. Mean cyclic time of queueing priority station polling system[J]. Journal of China Institute of Communications, 1999, 20 (2): 86-91.

[8]LIU Q, ZHAO D, ZHOU D. An analytic model for enhancing IEEE 802.11 point coordination function media access control protocol[J]. European Transactions on Telecommunications, 2011, 22: 332-338.

[9]姚道远, 张宝贤,刘海. 保障监测时延的无线传感器网络感知调度算法[J]. 电子与信息学报，2010, 32(7): 1591-1596.

YAO Daoyuan, ZHANG Baoxian, LIU Hai. Algorithms for detection latency guaranteed scheduling in wireless sensor networks[J]. Journal of Electronics and Information Technology, 2010, 32(7): 1591-1596.

[10]凡高娟, 孙力娟, 王汝传, 等. 非均匀分布下无线传感器网络节点调度机制[J]. 通信学报, 2011, 32(3): 10-17.

FAN Gaojuan, SUN Lijuan, WANG Ruchuan, et al. Non-uniform distribution node cheduling scheme in wireless sensor networks [J]. Journal on Communications, 2011, 32(3): 10-17.

[11]IBE O C, XIAN C. Stability conditions for multi-queue systems with cyclic service[J]. IEEE Trans Aut Control, 1988, 33(1): 102-103.

[12]赵东风, 郑苏民. 完全服务排队模型分析[J] . 电子学报, 1994, 22( 5): 102-107.

ZHAO Dongfeng, ZHENG Sumin. Analysis of a polling model with exhaustive service[J]. Acta Electronica Sinica, 1994, 22(5): 102-107.

[13]ZHAO D. Performance analysis of polling systems with limited service[J]. Journal of Electronics, 1998, 15(1): 43-49.