叶雪梅， 朱云杰， 蔡艳宁， 范青刚， 李鹏远

(1.西安高科技研究所 计算机教研室，陕西 西安 721006；2.西安高科技研究所 401教研室，陕西 西安 721006)

0 引 言

随着微电子技术、计算机技术、通信技术的迅猛发展，无线传感器网络的性能和稳定性快速提升，其应用领域已经从环境监测、微控制等开始向低速率的即时通信方向发展。针对簇树结构下的各类路由优化算法进行研究的文章很多[1～3]，对网络的组建、路由的发现、生存能耗等问题进行了研究；然而对于网络的速率，各级设备的交互冲突和多跳延时问题，MAC协议的性能同样是一个决定性因素。Zig Bee技术所采用的IEEE 802.15.4[4]协议的MAC层规范是比较公认的适合在对等无线传感器网络中应用的协议之一。但仍存在多跳延时过大、邻近簇冲突、暴露节点、信道利用率低等问题，且未给出具体的信标帧或各级设备超帧分配的调度算法，因此，针对分配算法衍生了一系列研究。文献[5]提出了一种基于整数线性规划的时分簇调度方法来避免IEEE 802.15.4中超帧冲突，但其方法过于复杂。文献[6]提出了一种通道预留机制，是把信标帧中的GTS信息和预留地址信息单独作为一个命令帧发送,虽然节省了很多能量,但该命令帧的发送时隙不好确定。文献[7]设计了一个动态GTS请求帧，在一个超帧中动态GTS可以不止一次地分配给同一个节点，这样做的弊端是很可能被一个节点占据所有GTS资源。本文将基于IEEE 802.15.4标准，来研究簇树网络中的非竞争时段(contention free period，CFP)的通信冲突问题，并提出一种解决方法，以保证簇树网络中实时通信的畅通运行。

1 问题描述

1.1 簇树网络结构下的超帧调度机制

IEEE 802.15.4规范主要针对低速无线个域网(low-rate wireless personal area network，LR-WPAN )制定，它规定了物理层和介质访问控制子层与固定、便携式及移动设备之间的低数据率无线连接的规范[8]。在IEEE 802.15.4中使用以超帧为周期组织通信。每个超帧都以信标(beacon)帧为开始，并将通信时间划为活跃和不活跃2个部分，活跃时期又划分为3个阶段：信标发送时段、竞争访问时段(contention access period，CAP)和CFP。如图1所示，为一个超帧结构。

图1 超帧结构图

在CAP，设备使用带时隙的CSMA/CA访问机制。在CFP，协调器根据上一个超帧时期网络中设备申请GTS同步时隙的情况，将其划分成若干个GTS同步时隙。

1.2 簇间冲突与暴露节点

1)临近簇间冲突问题：图2中，路由器R1和R2是各自簇的簇首，通过超帧组织簇内通信，R1簇中设备M1和R2簇中设备M2由于位置相邻会产生通信干扰。如果M1和M2在各自超帧通信的GTS中有时间上的重叠，就会产生临近簇间的冲突，从而无法通信。

图2 临近簇间冲突

2)暴露节点问题：由于采用的是统一调度机制，所以不存在隐藏节点问题。当有一个节点要发送数据给邻居节点，但因为其它邻居节点正在发送数据，而影响了它的发送。如图3，路由节点S1和S2，S1和R1，S2和R2都处在彼此的通信半径内；R1和R2不在彼此通信范围内。当S1传送数据给R1时，S2却不能传送数据给R2。因为此时S2检测到正有节点在占用信道而放弃对信道的争用，事实上，S2可以传送数据给R2，因为R2并不在S1的通信范围内，S1则称为S2的暴露节点。同理，当S1正在接收R1的信息，而S2试图接收R2的信息时则请求不被允许，而实际上若R1和R2的覆盖半径并不相交时，S2的请求是可以被允许的。

图3 暴露节点问题

2 基于区分服务的GTS统筹调度算法

基于第1.2节中描述的问题，考虑由中心协调器节点Sink来汇集网络的总体通信请求和协调时隙分配。将节点的通信请求细分为发送和接收2种类别，时隙分配时充分考虑节点之间的干扰和影响，尽可能地将互不影响的通信分配为并行状态，从而提高信道的利用率。

2.1 形式定义

定义1 冲突域CRi：在MAC协议中各节点之间只进行直接数据传递，所以，信道征用的冲突问题只在相邻节点之间发生，把节点Ri的CFP时段的信道冲突域CRi定义为，CRi={R/与Ri之间小于一跳范围的节点}。ai为节点Ri的状态值

定义2 时隙分配表Ti:Ri的GTS分配表Ti定义为k(CAP包含时隙数)维列向量Ti=[a1,a2,…,ak]T。

定义3 冲突矩阵C:节点的冲突矩阵C=Ti×CRi完整地描述了其与周边节点的信道共用情况，其大小与CFP包含的时隙数，节点的信号覆盖范围直接相关

定义4 区分服务的GTS请求帧(GTS-request to server,GRTS)：将算法的计算依据和控制信息整合成GRTS帧，如表1所示。

表1中各自段含义为：

表1 基于区分服务的GTS请求帧

服务类别(Server Style,SS)域,把数据分为实时数据流(RT)和尽力交付数据流(BE)。GTS个数和目的节点域成对使用，表示预请求通话的目的节点和时长。冲突域CRi为Ri节点的冲突域。编号为帧的防重复编号从1～255循环使用。

判定定理：Ri是无线网络中的任一路由节点，当其冲突域满足如下公式时，网络通信冲突不存在且可避免暴露节点问题

2.2 调度算法

基于以上思想本文提出一种基于区分服务的GTS统筹调度算法(a macroscopical GTS scheduling algorithm based on differentiated services)。算法的具体步骤如下：

1)生成各节点冲突域CRi，簇内节点在CAP以广播方式根据节点短地址寻找。

2)生成GRTS帧并发往Sink，依据采集数据和通信量的大小，计算所需时隙数，取定服务优先级对帧编号。

3)协调器节点对最先到达的节点请求进行分配，依据其冲突域CRi内各节点的分配表Ti生成冲突矩阵，寻找满足定理条件的包含连续k(k大于等于申请结点申请的时隙数)个GTS的CFP，按最小号优先原则从前到后进行分配，改写其Ti值,若无可分配资源则不分配。

4)重复步骤(3)，直到所有请求都被满足。

5)重新检验各节点的冲突域，对于不满足2.1中定理的各节点所分配的GTS全部收回，对于其请求重新运行步骤(3)分配。

6)GTS分配方案通知各节点。

3 实例分析与仿真实验

3.1 实例分析

以码头仓库湿度测量网络为应用背景，网络规模为200个终端，父节点最多可连接的子节点数Cm=18，子节点中最多可以连接的路由节点个数Rm=5，网络的最大深度Lm=4。中心协调器在网络中部，网络抽象图如图4所示。

图4 仓库湿度采集网络抽象图

R8节点请求给R4发送信息，需要2个GTS，若其GRTS帧为Sink收到的第一个请求帧，载荷部分如图5所示。

图5 帧的载荷

其冲突矩阵为

GTSR8R1R4N81N82N83N84N85N86N87N13N14N15N42100000000000000200000000000000300000000000000400000000000000500000000000000600000000000000700000000000000

Sink将第1，2时隙分配给R8节点，并对R4，R8的时隙分配表进行修改如下

TR8={1，1，0，0，0，0，0},

TR4={-1，-1，0，0，0，0，0}.

稍后N11节点也发出了它的GRTS帧，载荷段如图6。

图6 载荷段

其冲突矩阵为

GTSN11R1N01N12N15N65N6611001-1 102001-1 0013100-1 0104000-1 0-1 -1 5-1 -1 00010600000117-1 001000

3.2 仿真实验

本文采用NS2网络仿真软件，网络拓扑为图4所示。竞争窗口值采用NS2默认值。物理层采用TwoRayGround模型，节点接收距离RXThreshold为120 m。载波频率为2.4 GHz，发送功率为100 mW，天线高度为15 cm，增益为1。仿真采用恒定比特率CBR业务流模拟实时数据业务，数据包大小为512 byte。路由层采用了AODV协议。MAC层分别使用了文献[7]中的动态GTS请求算法简称为DGS和本文的算法简称为MGS(macroscopical GTS scheduling)。通过仿真比较2种情况下的网络性能。图7～图9给出了网络吞吐率、丢包率、发送时延随发送速率变化的比较情况。

由图7仿真结果可以看出:开始时由于通信量少，所以,冲突的发生和信道征用问题不是很尖锐，网络的性能差别不大。但随着网络负荷的增大，发送速率的提高，信道的征用问题、时隙的竞争问题开始明显起来，本文提出的算法在发送速率达到300 kB/s以前吞吐率近似呈线性增加，而DGS算法则受发送速率影响较大，网络的吞吐量随发送速率上升较缓。由图8可以看出：本文算法在200 kB/s的发送速率下，传播时延较稳定，而DGS算法则存在较大的波动性，从图中可以看到其出现了几次明显的抖动，传播时延不稳定。由图9可见，2种算法的丢包率相差无几，可见改变时隙的分配算法对网络的丢包率影响不大。

图7 网络吞吐率

图8 网络平均时延

图9 丢包率

4 结束语

统筹调度机制相比于竞争机制，在节点密集，网络负荷大的情况下能发挥出更好的优势。本文针对无线簇树网络中的通信冲突和暴露节点问题展开研究，提出了一种分析理论和判定准则，并在此基础上给出了一种基于区分服务的GTS统筹调度算法。从仿真结果来看，算法能够充分利用信道，合理分配时隙，避免不必要的通信冲突，在不影响丢包率的前提下提高网络吞吐率、缩短稳定网络时延，体现出了明显优势，同时映证了判定准则的正确性。但算法在应用范围上还具有局限性，其带宽开销、时间开销随网络的规模成几何级数增加，所以，不适用于大规模无线网络。算法在GTS的资源利用问题上没有加以考虑，分配时隙时，采用最小号优先原则，对于连续的大GTS时段申请，缺乏保障；同时算法对全网的时间同步要求也比较苛刻，这一点也没能考虑。

参考文献:

[1] 李小青，李 晖，杨 凯.一种基于D-S证据理论的Ad Hoc网络安全路由协议[J].计算机研究与发展,2011，48(8)：1406-1413.

[2] 钟 智，樊晓平，罗大庸，等.一种基于网格的无线传感器网络分簇路由协议[J].传感器与微系统,2012,30(12)：18-20.

[3] 洪 榛，俞 立，张贵军.无线传感器网络自适应分布式聚簇路由协议[J].自动化学报,2011,37(10)：1197-1205.

[4] IEEE Std 802.15.4TM.IEEE standard for information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements-part 15.4:Wireless medium aceess control(MAC)and physical layer(PHY)specifications for low-rate wireless personal area networks(LR-WPANs)[S].NewYork:IEEE Press.2003.

[5] Jurcik Peter．Real-time communication over cluster-tree wireless sensor networks[R]．Report，Porto:IPP-HURRAY ，2010．

[6] Cheng Liang,Bourgeois A G.Efficient channel reservation for multicasting GTS allocation and pending addresses in IEEE 802.15.4[C]∥Proc of the 3rd Int’l Conf on Wireless and Mobile Communications,2007:46-46.

[7] Song Jun keun, Ryoo Jeong Dong,Kim Sang Cheol, et al. A dynamic GTS allocation algorithm in IEEE 802.15.4 for QoS gua-ranteed real-time applications[C]∥Proc of IEEE Int’l Symp on Consumer Electronics,2007:1-6.

[8] 蒋 挺，赵成林,紫 蜂.技术及应用[M].北京:北京邮电大学出版社，2006:46-115.