WSN 中满足公平性的时分复用调度算法

高 强，李英涛，2，孙大洋，张 婧，2

（1.吉林大学 计算机科学与技术学院，吉林 长春130012；2.吉林大学 符号计算与知识工程教育部重点实验室，吉林 长春130012；3.吉林大学 通信工程学院，吉林 长春130012）

0 引 言

无线传感器网络由一系列能量有限的节点组成，如今已被广泛应用于各种应用环境［1］。在某些应用环境中，如自然环境监测、工业生产监测等，网络中的各个节点周期性产生数据的速率差异较大［2］。如果每个节点仍然按照相同的概率访问信道，势必会造成节点共享信道的不公平性，从而造成网络延时的增大和网络能耗过快、降低网络吞吐量和网络生存期。因此，考虑公平性的信道调度研究是十分必要的。

无线传感器网络中节能和数据传输中的冲突避免问题与MAC协议密切相关［3］。MAC 协议主要负责节点接入无线信道，是其它协议实现的基础，在无线传感网络中起着决定性作用［4］。在MAC协议中，根据信道的分配方式，可分为基于TDMA 的时分复用固定式和基于CSMA 的随机竞争式两种。基于时分复用的MAC 协议为网络中的节点分配独立的时隙，以避免节点间的相互冲突，节点在不属于自己的传输时隙内转入休眠状态以减少能量消耗，且能够在一定程度上保证网络传输的实时性［5］。

本文的设计目的是在深入分析现有的典型TDMA 调度算法的基础上，改进并提出一种能够有效满足信道分配公平性的方法。

1 相关工作

为了满足信道分配的需求，研究人员已经提出了大量有关TDMA 的算法［6］。

文献 ［7］中提出了一种结合CSMA 和TDMA 优点的混合MAC协议Z－MAC。Z－MAC协议的主要思想是节点根据网络信道的竞争程度，自适应地调整信道的接入方式。在低业务的情况下，CSMA 作为接入方式；在高业务的情况下，TDMA 作为接入方式。Z－MAC 是一个分布式的协议，具有良好的可扩展性，但是随着网络密度增加会引入较多的控制开销，且在低业务情况下延时较大。

文献 ［8］中提出了一种流量自适应介质访问协议TRAMA，该协议由相邻节点协议、传输时间安排交换协议和自适应选举算法组成，根据相邻区域的节点流量信息来选择当前时隙的发送节点和接收节点。TRAMA 通信开销小，但是延迟较长，比较适用于周期性数据采集和监测无线传感器网络方面的应用。

文献 ［9］中提出了一种基于图染色理论的时分复用调度算法GCSA，该算法分为两个阶段：染色阶段和调度阶段。染色阶段借鉴Brélaz染色策略，提出了一种分布式顶点染色算法DVCA，以达到接近最优的独立集划分。调度阶段根据染色阶段得到的染色结果使用基于优先权的调度策略为独立集分配时隙。该算法具有可扩展性且能得到较少的颜色以最大化独立集，但是调度策略解决网络的公平性问题有待改进。

文献 ［10］中提出了两种集中式时分复用调度算法：基于节点的调度和基于层次的调度。这两种算法使用顶点染色方法，以得到最小化无冲突时隙分配为目标，其性能取决于节点的层次分布状况，能够得到较少时延，但可扩展性较差。

针对以上协议目前存在的问题，本文基于DVCA［9］图染色算法，使用考虑通信干扰的冲突模型对非簇头节点的通信实现无冲突调度。节点间通过跟邻居节点进行交互获得局部信息进而做出决策，并且为流经数据量大的节点优先分配时隙。该调度算法有效地解决了数据流量分布不均匀的网络场景中信道分配的公平性问题，在降低能耗的同时保证网络具有较高的数据传输率。

2 网络模型

建立一个由n个随机部署的传感器节点构成的自组织网络，其应用场景为周期性的数据采集。将此传感器网络抽象成图G＝ （V，E）结构，图中点集V 代表网络中的节点，n＝｜V｜表示网络中的节点数目，边集E∈V×V 表示节点间的通信链路。若节点i和j 间形成一条路径，则图G中有 （i，j）∈E。由于网络为同构网络，因此可以在图G中使用无向边来表示链路，即若 （i，j）∈E，则 （j，i）∈E。

根据网络特点作出如下假设：

（1）数据汇聚点DS位于一个方形观测区域A 的内部。所有节点在部署后不再发生位置移动。

（2）使用DWEHC［11］分簇协议得到所需要的网络拓扑结构。分簇后的网络结构如图1所示。

图1 分簇网络结构

（3）簇内节点采用多跳模式使用基于时分复用的MAC协议与簇头节点通信，簇头节点为簇内节点通信分配CDMA 编码以避免簇间冲突，而簇头节点以单跳模式使用基于竞争的MAC协议来向基站节点传输数据［12］。

（4）每个节点都是同构的，且有一个唯一的标识（ID）。

（5）网络中的节点可以自由调整发射功率，支持双向数据通信［13］。

（6）每个节点通过彼此通信知道自己及其直接邻居节点的地理位置。

（7）无线传感器网络中节点间的传输冲突分为主冲突和次冲突。本文使用文献 ［9］中得到冲突图的方法定义节点间的冲突关系。

3 算法介绍与相关定义

3.1 DVCA染色算法描述

将大规模无线自组织网络抽象成图G＝ （V，E）结构，图中的点集V 代表网络中的链路，这样把一个无线网络抽象为图，进而节点调度就转化成了顶点染色问题或独立集问题。独立集的定义如下：

定义1 独立集：给定图G＝ （V，E）的一个k 染色，用Vi来表示图G 中染以第i 色的顶点集合 （i＝1，2，…，k），则图G 的一个k 染色对应节点集合V 的一个划分［V1，V2，…，Vk］，其中每个Vi都是独立集，而图G 的顶点颜色数k 就是实现这种划分的最小自然数。

DVCA［9］是一种分布式顶点染色算法，该算法借鉴Brélaz染色策略。Brélaz算法是一种能够得到接近最优颜色数的集中式顶点染色算法，该算法反复选择有最小可用颜色数的节点进行染色。在DVCA 中，每个节点 （不包括基站）仅考虑自己在冲突图中两跳范围内的冲突节点的相关信息，计算自己的权值，判断自己是否为待染色节点，若是则使用最小的可用颜色来为自己染色。网络中节点独立运行该算法，利用广播获取局部染色信息。最终经过3个阶段将网络中的节点划分为若干独立集，每个独立集中的节点可以同时处于工作状态，互不干扰。DVCA 运行的轮数为O（degmax）（degmax 为冲突图的最大节点度），算法所用颜色数最多为degmax＋1。

3.2 TSFA调度算法描述

TSFA 调度算法分为分簇网络形成、独立集划分和优先级调度3 个阶段。其中前两个阶段是网络的启动时期，该时期算法的性能直接影响网络的服务质量。分簇网络形成阶段采用DWEHC协议进行分簇，该协议能有效减少网络中的能量消耗，延长网络生存期。在网络拓扑结构建立后，使用前文介绍的DVCA 算法对网络冲突图进行独立集划分。DVCA 算法能够最大化独立集，更好地实现时分复用算法中同一时隙内的空间复用。

定义2 监听速率：节点监听速率是在节点ni处产生数据的速率，即单位元时间内节点通过监听周围环境所获得的数据量，用d（ni）表示。

定义3 接收速率：节点接收速率是流经节点ni的数据速率，即单位元时间内ni的邻居节点发送给ni的数据量，用s（ni）表示。在这一过程中，节点ni可以是转发节点或者是数据融合节点。

定义4 数据权重：数据权重是衡量节点ni获得信道优先级的重要标准，用weight（ni）表示。数据权重越大，节点获得信道的优先级越高。

网络中任意节点数据权重weight（ni）设置如下

网络中任意节点记为ni（i∈ ｛1，2，…，n｝）。

经过网络初期的准备工作，算法正式进入核心阶段：优先级调度阶段。该阶段的主要工作是由簇头为簇内的独立集分配时隙。根据前文分析，为了保证网络的吞吐量和信道共享的公平性，网络拓扑结构和数据流量分布是需要考虑的两个重要因素。因此，如果能够得到独立集中节点的层次结构和独立集之间的数据流量大小，无疑能够更加合理地判断出各独立集占有时隙的优先级。这样，TSFA调度算法时隙分配问题转化为如式 （2）和式 （3）的priority优先级计算问题

式 （2）中Vi是指染以第i 中颜色的独立集，priority（Vi）代表此独立集Vi占有时隙的优先级，level（j）表示独立集Vi中节点j 的层次数，Ni表示独立集Vi中的节点数。这种优先权定义综合了网络的节点数目和多跳结构等多种因素的影响。

如果考虑数据流量分布等因素，加入数据权重影响因子，则可提出如式 （2）所示的优先级计算方案

式中：Vi——染以第i中颜色的独立集，weight（j）——独立集Vi中节点j 的数据权重 （weight（j）的定义详见定义4），rand（Vi）——一个随机数，作为调整因子。这种方案充分考虑了网络中数据流量动态变化的特点，能够适应网络中的突发状况，更好地满足公平性的要求。

为了实现公平性，簇内每个节点需要周期性维护调度信息表。表内存在信息：节点标识id，节点颜色color，节点层次level，节点产生数据速率d，节点流经数据速率s。信息表组成如下所示：

调度信息表 （Node＿schedule＿info）

Node＿schedule＿info＝ （id，color，level，d，s）

簇内节点将这些信息放在数据包的包头中，在所属时隙内将数据包发送出去。这样调度信息表可以随着数据包的传输到达簇头节点，保证了TSFA 调度算法的正常运行。

根据以上分析，时分复用调度算法流程如图2、图3所示。

3.3 TSFA调度算法举例

为更好理解TSFA调度算法的工作流程，本文构建一个虚拟应用场景。该场景是一个以数据采集为目的的无线传感器网络，网络中节点监听周围环境信息，然后通过多跳模式将信息传送到基站。为简化分析，假设网络中的节点总数为10 （不包括基站节点），网络拓扑结构如图4所示。

在此结构图中，DS是基站节点，节点a和节点f是直接和DS通信的簇头节点 （两个簇简称为簇a和簇f）。节点b，c，d，e在以节点a为簇头的簇内，而节点g，h，i，k在以节点f为簇头的簇内。图4中实线表示主冲突关系，虚线表示次冲突关系。根据冲突关系应用DVCA［9］染色算法对网络中的节点进行染色，相同颜色的节点加入同一独立集。染色结果为簇a形成独立集 ｛b，e｝， ｛c｝， ｛d｝，簇f形成独立集 ｛h，i｝，｛g｝，｛k｝。然后簇头节点和簇内节点分别按照各自的工作流程运行调度算法。簇头节点根据簇内各节点的数据流量情况，计算各独立集的优先级，最后按照优先级的顺序分配时隙。网络中各节点的某一周期调度信息见表1，时隙分配情况见表2。

图2 簇内节点基本工作流程

图3 簇头节点基本工作流程

图4 网络拓扑结构

表1 节点调度信息

表2 时隙分配情况

4 实验与分析

本文通过MatLab仿真对满足公平性的时分复用调度算法TSFA 进行性能分析与评估，并与GCSA 和TRAMA进行性能比较。

实验中，在边长100 m 的正方形仿真区域内随机布置110个节点。Sink节点在网络监测区域的中心，实验参数见表3。

表3 实验参数

仿真实验从网络的吞吐量、时延和能量消耗3个性能指标分析TSFA 调度算法的性能，实验结果如图5，图6所示。其中，图5 （a）为3种算法的吞吐量比较。从图中可以看出，在算法开始执行阶段，由于TSFA 尚未了解网络中的流量分布，所以TSFA 和GCSA 的吞吐量没有明显差异。但是，随着时间的增加，TSFA 的吞吐量比GCSA 有一定的提高。这是由于在TSFA 调度模式下，簇头节点通过不断接收来自簇内各节点的数据权重信息，从而掌握簇内各独立集的数据流量大小，开始采用第二方案进行优先级调度。从图中还可以看到，TSFA 和TRAMA 都能维持较高的网络吞吐量要求，二者在吞吐量性能上优于GCSA算法。图5 （b）为3 种算法的时延比较。由于TSFA 和TRAMA 在信道利用率方面比GCSA 有着很大的改善，所以随着时间的增加，GCSA 的时延增加较为明显。这是因为TSFA 和TRAMA 都采用了基于流量的传输调度策略，使数据量大的节点优先占有信道，而无数据或数据量较少的节点进入低能耗模式，有效减少了丢包率及时延。图5（c）显示了网络中总能量的消耗情况。从图中可以看到，因为TSFA 能够减少网络延迟，提高信道利用率，所以能量消耗要大幅低于GCSA。同时，由于TSFA 与TRAMA相比，算法简单，通信开销较小，因此，TSFA 的能量消耗要比TRAMA 低。图6给出了网络数据流量分布差异变大时3种算法的比较结果。从图中可以看到，TSFA 在吞吐量的提升和降低延时、能量消耗方面效果更加显著

实验结果表明，TSFA 能够有效提高信道利用率，延长网络生存时间，且更适用于网络数据流量分布不均的应用场景。

图5 WSN 的3种调度算法比较

图6 WSN 网络数据流量差异变大时3种调度算法比较

5 结束语

本文给出了一种满足公平性的无线传感器网络时分复用调度算法。其核心思想是利用分簇算法将网络组织成大小非均匀的簇，然后簇头通过染色算法将簇内节点划分成独立集，最后应用调度算法根据网络中的流量分布对各个独立集进行调度。算法在保证节点间数据传输不发生冲突的前提下，较好地解决了信道利用的公平性问题。实验结果表明，算法提高了网络吞吐量，降低了网络时延，减少了网络的能量消耗，延长网络使用寿命，并且在网络数据流量差异变大的时候性能更好。

［1］Beel Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey［J］.Computer Networks，2008，52（12）：2292－2330.

［2］HONG Feng，CHU Hongwei，JIN Zongke，et al.Review of recent progress on wireless sensor network applications ［J］.Journal of Computer Research and Development，2010，47（Suppl）：81－87 （in Chinese）.［洪峰，褚红伟，金宗科，等.无线传感器网络应用系统最新进展综述 ［J］.计算机研究与发展，2010，47 （Suppl）：81－87.］

［3］Hoon K，Sung－Gi M.Priority－based QoS MAC protocol for wireless sensor networks［C］／／Proc of the IEEE International Symposium on Parallel＆Distributed Processiong，2009：1－8

［4］ZHANG Xiaoke，ZENG Jianping，XU Chaonong，et al.Research on MAC scheduling algorithm for wireless network based on distributed graph coloring［J］.Journal of Computer Research and Development，2011，48 （z2）：216－222 （in Chinese）. ［张晓轲，曾健平，徐朝农，等.基于分布式图染色的无线MAC调度算法研究［J］.计算机研究与发展，2011，48 （z2）：216－222.］

［5］Mahfoudh S，Minet P，Amdouni I.Energy efficient routing and node activity scheduling in the OCARI wireless sensor network ［J］.Future Internet，2010，2 （3）：308－340.

［6］Suriyachai P，Roedig U，Scott A.A survey of MAC protocols for mission－critical applications in wireless sensor networks［J］.Communications Surveys ＆ Tutorials，IEEE，2012，14（2）：240－264.

［7］Rhee I，Warrier A，Aia M，et al.Z－MAC：A hybrid MAC for wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2008，16 （3）：511－524.

［8］Rajendran V，Obraczka K，Garcia－Luna－Aceves JJ.Energyefficient，collision－free medium access control for wireless sensor networks ［J］. Wireless Networks，2006，12 （1）：63－78.

［9］Kang H，Zhao Y，Mei F.A graph coloring based TDMA scheduling algorithm for wireless sensor networks［J］.Wireless Personal Communications，2013，72 （2）：1005－1022.

［10］Sinem Coleri Ergen，Pravin Varaiya.TDMA scheduling algorithms for wireless sensor networks［J］.Wireless Networks，2010，16 （4）：985－997.

［11］Ding P，Holliday JA，Celik A.Distributed energy－efficient hierarchical clustering for wireless sensor networks［M］／／Distributed Computing in Sensor Systems.Berlin：Springer Berlin Heidelberg，2005：322－339.

［12］Tao Shu，Marwan Krunz.Energy－efficient power／rate control and scheduling in hybrid TDMA／CDMA wireless sensor networks ［J］. Computer Networks，2009，53 （9）：1395－1408.

［13］Cardieri P.Modeling interference in wireless Ad Hoc networks［J］.IEEE Communications Surveys＆Tutorials，2010，12 （4），551－572.