基于图着色的TDMA调度方法性能仿真分析

龙源期刊网 https://www.wendangku.net/doc/ef10575358.html,

基于图着色的TDMA调度方法性能仿真分析

作者：张治学 曾波李姗姗

来源：《软件导刊》2014年第09期

摘要摘要：为深入研究基于图着色的TDMA调度算法性能，详细讨论了两种典型的面向传感器网络的基于图着色的TDMA调度方法实现原理，并通过实验从数据汇聚时间、传输延迟、能量消耗3个方面比较了算法的性能。结果表明，基于图着色的TDMA调度方法明显缩短了无线传感器网络的数据汇聚时间与传输延迟。

关键词关键词：无线传感器网络；TDMA；图着色；算法性能分析

DOIDOI：10.11907/rjdk.143230

中图分类号：TP337

文献标识码：A 文章编号文章编号：16727800（2014）009005903

0 引言

无线传感器网络因其成本低廉、部署灵活、覆盖范围广，在环境感知、入侵检测、战场监测等领域具有广泛的应用前景[1]。一般网络环境中，在传感器节点部署完毕之后，节点通常

采用自组织方式形成多跳数据汇聚树，并由一个数据汇聚节点，即Sink来完成数据汇聚：树中的节点周期性采集传感数据后，以单跳或多跳的方式传输至Sink，在多跳的传输过程中，位于树中不同高度的节点将兼顾数据中继功能，直到数据被投递到Sink[2]。

数据汇聚树的多跳数据传输特性，加上无线通信技术有限的无线干扰范围，使得在多个节点间进行数据的并发传输变成可能，从而缩短数据汇聚时间，提升网络带宽利用率。然而，由于大部分应用中，节点采用随机方式进行部署，造成节点密度、无线通信环境、无线干扰强度均存在很大差异，加上无线干扰与周边环境存在一定程度的时空相关性[3]，导致节点间数据

并发传输无法顺利进行。时分多址访问技术（TDMA）可以剔除无线冲突与空闲侦听，因此可以降低节点能量消耗与提高网络吞吐量。在此基础上，TDMA调度方法采用干扰感知方式为

每个节点分配无冲突TDMA时槽，实现互不干扰的节点利用相同时槽完成数据传输，从而缩短数据汇聚时间与传输延迟。

为了解决TDMA调度问题，可借鉴图论中图着色的方法。在图论中，图着色算法[46]可以实现任意相邻区域都具有不同的颜色。因此，可以采用如下方式将无线传感器网络形式化为图G：先将节点对应为图G中的顶点，对节点之间的数据传输关系采用有向边的方式在图G中进