一种时分簇调度算法的实现*

任苗苗，范书瑞，2*，王悦良

（1.河北工业大学电子信息工程学院，天津 300401；2.昆士兰大学信息技术与电气工程系，昆士兰 4072，澳大利亚）

一种时分簇调度算法的实现*

任苗苗1，范书瑞1，2*，王悦良1

（1.河北工业大学电子信息工程学院，天津 300401；2.昆士兰大学信息技术与电气工程系，昆士兰 4072，澳大利亚）

无线传感器网络是一种典型的资源受限系统，研究信道和时隙在内的资源分配方法，对提高网络性能保障服务质量具有重要意义。为解决智慧医疗系统中传感网络结构不固定，服务质量无法保障问题，构建了一种非平衡的簇树结构，采用可避免碰撞、保证传输时延的时分簇调度算法进行传输任务的分配，将资源分配结果在TinyOS系统中进行实现，并采用CC2530平台进行验证。为便于修改数据流参数，使调度的结果更加直观，设计了图形用户界面。结果表明这种时分簇调度算法可以保证非平衡结构无线传感网络通信质量，为大规模簇树网络提供有效的服务保障。

无线传感器网络；资源分配；时分簇调度；TinyOS

近年来，物联网技术的快速发展，使无线传感器网络进一步得到普及。簇树结构是无线传感网络的一种常用网络，其中的源数据流通过各个路由遍历不同的簇，最终流入端节点。在相邻的簇间可能会发生数据的碰撞而使通信失败，这限制了网络规模，其关键是簇间调度和冲突避免无法很好的解决。MAC（Media Access Control，媒体接入控制）协议负责为网络中的各个节点分配无线通信资源的是，对整个网络的性能有直接影响。文献［1］对典型调度方法进行了分析，传统的MAC协议存在严重的冲突重传，不能满足资源有限、能量有限的无线传感网络的要求。针对MAC层的资源调度衍生了一系列解决算法。文献［2］采用自触发采样策略减少网络利用和能耗损耗的同时，确保了网络性能。文献［3］针对能量敏感问题设计了模型预测控制，确保WSN鲁棒性。文献［4］采用自适应GTS分配方法用于保证网络实时特性。这些从理论角度证明了IEEE802.15.4的GTS分配机制适用于现代工业网络控制系统。

GTS机制为节点提供了一种实时服务保障，满足对时间敏感场合的应用。但是如何均衡网络规模和网络性能，没有得到很好解决。针对不同的网络结构，研究人员提出了各种方法。文献［5］针对可分负载星型无线传感器网，提出以能耗均衡为目的的调度算法。在文献［6］中提出一种利用区分服务的GTS统筹算法来调度节点资源，但开销随网络的规模成几何级数增长，且算法对全网的时间同步要求过于苛刻，不适合用于大规模网络。文献［7］对传统的CSMA/CD做了改进，根据下行邻居节点数进行分组，通过组的有序竞争减轻碰撞问题。文献［8］设计了一种自适应的MAC层调度算法，根据路径信息判断数据量的大小从而合理分配时隙。文献［9］采用图论方法设计了动态调度算法的任务分配策略，减少任务间等待时间和通信时间。但是这些方法都不能克服信道的争用，无法满足工业应用实时性的要求。

文献［10］提出了针对IEEE802.15.4协议超帧结构的时分调度算法（TDCS），对簇树网络中不同节点的超帧区间进行了调度，有效解决同步信标帧之间的冲突。文献［11-12］研究了IEEE802.15.4的GTS机制，为节点提供了一种实时服务保障，满足对时间敏感场合的应用，可预测每个应用节点的最糟糕性能。这些都是已给出平衡簇树结构的无线传感器网络中。但是更多的应用场景是非平衡结构，上面的方法容易造成资源极大浪费，本文解决非平衡结构网络资源分配问题。

1 网络簇树结构

在簇树拓扑结构中，由于每个节点只与其设定好的父路由器和子节点通信，所以拥有固定的多跳通信路径。每个簇的活动在时间上式周期的，在每个活动周期都可以分为两部分：活跃期和非活跃期。每个除根节点外的路由器都可以属于两个簇，一次作为子节点，一次作为簇头节点。因此，当这两个簇任意一个处于活跃期时，路由器都会被唤醒，否则则进入低功耗模式，以节省能耗。针对智慧医疗中的不平衡网络结构，设计了如图1所示的非平衡的簇树结构网络。

图1 网络拓扑结构示意图

在TDCS算法中，为了描述非平衡簇树网络结构，将网络的拓扑结构用矩阵A=（aij）的形式表述。如果路由器i是路由器j的子节点，则aij=1，否则aij=0。矩阵A的维数等于网络中总的节点数。因此上述簇树结构的矩阵表示为：

2 任务分配及算法实现

本文采用的TDCS算法具有两种约束形式：相对于冲突域的簇资源约束和数据流的时序约束。因此，任务的设置包括一组簇任务和一组仅反映时间限制的虚拟任务。

2.1 任务定义与分配

簇任务Ti与网络结构中每一簇i相对应。当簇处于活跃期时，该簇的任务处理时间等于簇的超帧区间长度SD。每一个虚拟任务对应着给定数据流在给定簇中的活动。用 pi表示簇任务Ti的处理时间。 pi包括簇i活跃期中的竞争接入期CAP、所有接收信息方向的GTS和发送信息方向的GTS。

每个数据流存在一个或多个源节点和确定的一个汇聚节点。在本文中根据网络簇树图1定义了两个数据流，其具体参数如表1所示。

表1 数据流参数

根据网络簇树结构可知，数据流1由源节点12、13分别遍经簇4簇1，簇5簇2簇1，最后进入簇3的端节点。数据流2由源节点6、10分别遍经簇6，簇3 簇1，在簇2汇聚并到达端节点9。

2.2 任务调度

调度问题可以定义为寻找一个可用的调度（s1、s2、···、sn）来满足时序和资源约束。定义变量si为任务Ti的启动时间持续长度。不同任务将最大调度周期BI分割给不同si。

si可以用下式表示：

该调度算法采用整数线性规划（ILP）实现。得到二元的结果xij。该规划的约束条件如下：

通过上述规划得到的变量xij定义了任务Ti和Tj间的相互关系：

当xij=0，则任务Tj在Ti后；当xij=1时，则任务Ti在Tj后。

pj是任务Tj的处理时间，vij表示优先约束的偏移量。wij表示任务先后顺序的一个参量，如果wij大于零，则表示任务Ti的开始时间si要比任务Tj的开始时间sj至少延迟wij，wij小于零，则提前相应wij。

3 硬件实现

CC2530是一个兼容2.4GHz IEEE802.15.4的真正的片上系统，能以教低的成本建立大规模网络。由于TinyOS现阶段不支持CC2530节点，在组网前首先要设计CC2530相关组件，完成TinyOS操作系统在CC2530上的移植。TinyOS具有层次性的架构，其移植性直接与最底层的硬件抽象组件相关。

3.1 系统移植

系统移植包括CC2530的寄存器声明和组件移植。在ioCC2530.h文件声明了CC2530部寄存器配置，对应的timer、adc、radio等文件夹内包含了CC2530下对应时钟、射频、串口通信等功能的组件。

Timer组件是一个定时器组件，其Timer接口用来触发事件。先根据CC2530芯片内部定时器部分数据资料定义各层需要定制的接口和组件列表；然后用nesC语言编写上述各层列表中定义的接口、组件的代码和timer.h文件，并一起存放到timer文件夹中。

Radio组件是TinyOS的射频组件，提供Packet、Receive、AMSend和SpiltControl接口。Packet用来实现数据包的管理，Receive具有数据包的接收功能，AMSend具有发送数据包的功能，SpiltControl用来控制天线的状态，负责天线的开启和关闭。

3.2 信道扫描

为了创建良好的运行环境，需要扫描信道。通过获取CC2530的RSSI值，将RSSI数据自动附加到接收到的数据帧中。在处理接收数据帧的函数中对消息元结构体进行定义，设定有关RSSI的位定义。当接收完整的一帧数据时，只需要读取帧检测序列字段中的内容就可以获取RSSI的数值。

对于CC2530而言，接收信息的RSSI为只读字段。在接收到数据包后，程序自动触发Receive函数，在接收函数中调用上述定义的getRssi函数，即能返回接收信号的RSSI值，从而实现对RSSI的监控。关键接收函数：

3.3 计算结果应用

根据各节点实现的不同功能，将节点分为端节点、路由器、汇聚节点三种。对三种不同功能的节点分别进行程序设计。端节点负责发送数据；汇聚节点负责接收各节点发送来的数据；路由器从端节点接收数据后触发发送功能，将收到的数据向上转发给其由TDCS算法决定的父节点。对不同的传感器节点，在发送指令AMSend.send函数中根据TDCS计算结果，指定其发送的目标节点编号，关键代码如下：

连接好硬件节点，在cygwin命令窗口中针对节点类型进入apps/CC2530/TDCS下对应的文件夹，将程序编译下载到对应节点上。在汇聚节点上连接串口即可观察到实验结果。

4 测试效果

按照表1中给出的参数设定用户界面中的输入值，数据流1的源节点为12、13，汇聚节点为11；数据流2的源节点为6、10，汇聚节点为9。点击Calculate运行程序。根据调度结果显示，数据流1中从源节点12到汇聚节点11的传输依次激活簇4、1、3；数据流1中从源节点13到汇聚节点11的传输依次激活簇5、簇2、簇1、簇3；数据流2中从源节点10到汇聚节点9的传输依次激活簇3、簇1、簇2。如图2所示。

图2 数据流传输结果

同时可以观察到，由于两个数据流都没有经过簇6，所以簇6一直处于非活跃期，即簇6的簇任务T6的处理时间 p6=0。各簇激活的时序，从而决定了各数据流任务的执行时间。在第一时间段内簇4、簇5被同时激活，第二时间段内簇1处于活跃期，第3时间段激活簇3，第4时间段激活簇2。如图3所示。

图3 调度结果端到端延时

通过观察得到的端到端延时值可以发现，采TDCS调度算法后有了明显的改善，满足了簇树网络通信的低功耗与冲突避免的要求，能够用于保证非平衡结构无线传感网络通信质量。

5 结论

为了改善非平衡簇树网络通信中的延时与能耗问题，本文应用了时分簇调度（TDCS）算法，研究了簇树结构的无线传感器网络的通信机制，并对

TDCS算法进行仿真，设计了GUI图形用户界面。使用TinyOS的nesC语言编写程序，将仿真得到的调度结果在CC2530硬件节点上实现。由于非平衡结构簇树网络通信时各簇间歇处于活跃期或休眠期，

TDCS算法给出了一个最佳的时序调度方案，得到各簇活跃期的起始时间与延续区间。解决了无线传感器网络的降低能耗和冲突避免问题，提高了网络性能。

［1］ 张晓玲，梁炜，于海斌，等.无线传感器网络传输调度方法综述［J］.通信学报，2012，33（5）：143-157.

［2］ Tiberi U，Fischione C，Johansson K.H.Energy-Efficient SamPling of Networked cControl Systems over IEEE 802.15.4 Wireless Networks［J］.Automatica，2013，49：712-724.

［3］ Daniele Bernardini，Alberto Bemporad.Energy-Aware Robust Model Predictive Control Based on Noisy Wireless Sensors［J］.Automatica，2012，48：36-44.

［4］ Feng Xia，Ruonan Hao，Jie Li，et al.Adaptive GTS Allocation in IEEE 802.15.4 for Real-Time Wireless Sensor Network［J］.Journal of Systems Architecture，2013，59：1231-1242.

［5］ 刘端阳，暴占兵，程珍.一种可分负载WSN的能耗均衡负载调度算法［J］.传感技术学报，2014，27（2）：225-232.

［6］ 叶雪梅，朱云杰，蔡艳宁，等.无线簇树网下的GTS时隙调度算法［J］.传感器与微系统，2014，33（7）：133-136.

［7］ 赵小超，郑明才，廖瑞华.基于有序竞争的传感器网络的MAC协议［J］.计算机工程与应用，2012，48（18）：76-80.

［8］ 丁海霞.传感器网络中一种实时的自适应时隙调度算法［J］.计算机工程与应用，2010，46（22）：110-112.

［9］ 高治军，王洪玉，王鑫，等.智能建筑室内环境分布式可计算WSN任务调度研究［J］.传感技术学报，2014，27（3）：378-382.

［10］Anis Koubâa，Andre Cunha，Mario Alves，et al.TDBS：A Time Di-Vision Beacon Scheduling Mechanism for Zigbee Cluster-Tree Wireless Sensor Networks［J］.Real-Time Systems，2008，40（3）：321-354.

［11］Jurcik Petr，Koubâa Anis，Severino Ricardo，et al.Dimensioning and Worst-Case Analysis of Cluster-Tree Sensor Networks［J］. ACM Transactions on Sensor Networks，2010，7（2）：1-47.

［12］Hanzalek Z，Jurcik P.Energy Efficient Scheduling for Cluster-tree Wireless Sensor Networks with Time-Bounded Data Flows：Application to IEEE 802.15.4/ZigBee［J］.IEEE Transactions on Industrial Informatics，2010，6（3）：438-450.

任苗苗（1992-），女，本科，就读河北工业大学电子信息工程专业，研究方向网络资源分配方法，pingshan20@163.com；

范书瑞（1979-），男，讲师，博士，研究方向无线传感器网络和嵌入式系统，fansr@hebut.edu.cn。

The Implementation of a Division Cluster Scheduling Algorithm*

REN Miaomiao1，FAN Shurui1，2*，WANG Yueliang1
（1.School of Electric Information Engineering，Hebei University of Technology，Tianjin 300401，China；2.Information Technology and Electrical Engineering，The University of Queensland，Queensland 4072，Australia）

As a typical resource constrained system，Wireless Sensor Network（WSN）can be significantly improved the performance of guarantee quality of service（QoS）by effective resource allocation，including channel and time slot.But thestructureisnotfixedinsmartmedicalsystem，whichcanleadtotheuncertaintyservicequality.Anon-balancedclustertree structure is presentforovercoming the collision and uncertain delay，taking into accountthe allocation oftraffic. The resource parameter is implemented in TinyOS system，which be verified by CC2530 platform.And Graphical User Interface is designed for modifying data flow parameters and inspecting scheduling results.The experimental results show that this cluster tree scheduling algorithm can ensure the non-balanced structure of network quality，and provide theeffectiveserviceguaranteeforlarge-scaleclustertreenetwork.

wireless sensor network；resource allocation；division cluster scheduling algorithm；TinyOS EEACC：6250

TP273

A

1004-1699（2015）07-1073-05

10.3969/j.issn.1004-1699.2015.07.022

项目来源：河北省自然科学青年基金项目（F2013202102）；河北省科学研究与发展计划项目（11213566）；国家级大学生创新创业训练计划立项项目（201310080009，201410080006）

2014-11-19 修改日期：2015-04-03