无线传感器网络传输调度方法综述

张晓玲，梁炜，于海斌，封锡盛

(中国科学院 沈阳自动化研究所 工业信息学重点实验室，辽宁 沈阳 110016)

1 引言

集数据采集、处理、无线传输等功能于一体的无线传感器网络扩展了人们的信息获取能力，将逻辑上的信息世界与真实物理世界融合在一起，将会改变人类与物理世界的交互方式[1～3]。1999年的美国商业周刊[4]认为无线传感器网络是 21世纪世界最具影响的21项技术之一。2003年的MIT新技术评论[5]认为无线传感器网络是改变世界的 10大新技术之一。2009年温家宝总理倡导“感知中国”，进一步推进无线传感器网络的研究。由于无线传感器网络技术是应用性非常强的技术，国内在开展这方面的研究工作时需要坚持需求牵引且面向具体应用。目前，针对无线传感器网络的研究已由基础研究转向了应用研究，例如新兴的工业无线传感器网络、物联网、智能电网等。然而，应用的多样性对于无线传感器网络的性能提出了更加苛刻的要求。其中，无线传感器网络协议栈中的介质访问控制(MAC，medium access control)子层负责为相互竞争的节点分配无线通信资源，是关系网络性能的关键技术[2]。目前针对不同的应用，研究人员提出了多种MAC协议，可以按照如下依据进行分类：第一，采用分布式控制还是集中式控制；第二，使用单一共享信道还是多个信道；第三，采用固定分配方式还是随机访问方式。根据第三种分类方式，可将MAC协议归纳为以下3类。

1) 采用固定分配方式，为每个传感器节点分配固定的通信时隙和信道，从而避免节点之间的相互干扰；具体的实现方式包括时分多址(TDMA，time division multiple access)方式、频分多址(FDMA，frequency division multiple access)方式或者码分多址(CDMA，code division multiple access)方式。

2) 采用随机竞争方式，传感器节点在需要发送数据时随机占用无线资源，重点考虑尽量减少节点间的冲突和干扰。

3) 混合方式，即固定分配和随机竞争结合的方法。

目前，对于大多数无线传感器网络的应用，如现在典型的工业无线传感器网络，固定分配方式是较为理想的解决方案。究其原因在于：首先，无线传感器网络对于性能具有确定性要求；其次，为了便于管理，现有无线传感器网络的拓扑结构相对固定且常为层次性结构；此外，网络中的数据大多具有周期性特征。固定分配方式的实现依赖于通信资源的分配。通常的研究方式将如何合理分配通信资源以保障应用需求归结为传输调度问题。

本文正是依托于这样的背景，对保证网络性能和用户需求的传输调度技术进行详细归纳，并总结了研究挑战和未来的研究工作。

2 传输调度问题概述

广义的传输调度问题通常包括6个要素：被调度对象、调度目标、调度算法、调度者、调度方案和调度代价。狭义的传输调度问题主要针对 MAC层进行研究。6个要素包括[6]：无线通信资源(时间和信道等)是被调度对象；调度目标通常是网络吞吐量、数据传输的实时性和可靠性、能耗、节点公平性等；调度算法实现对无线通信资源的合理有效分配；调度者可以是网络中的汇聚节点或者是单个节点；调度方案是经过调度算法控制后，节点收发报文的次序、时间及各种服务质量；调度代价包括计算的复杂度和缓存区的资源占用情况等。其中，调度算法(或称调度规则、调度机制)是连接其余5个要素的纽带。通常，为了获得一个满意的调度方案，通常需要在调度代价和调度目标之间进行折中，因此，传输调度问题往往转化为多目标优化问题。

传输调度问题出现的根源在于节点对有限资源的争用。无线传感器网络中，无线通信资源主要包括时隙和信道。因此，无线传感器网络的传输调度问题主要包括3个方面的研究内容：时隙分配、信道分配以及时隙和信道二维资源的联合分配。而在每个方面的研究中，需要在满足空间约束、顺序约束、截止期约束、可靠性约束、能量约束等约束条件[7]的基础上，解决以下 3个层面的问题。

1) 当网络中的多个节点之间存在冲突和干扰关系时，为节点分配通信的时隙和信道。

2) 当节点上有多个报文需要发送时，为每个报文分配占用时隙和信道的次序。

3) 优化节点的发射功率，控制节点对网络的干扰范围，降低传输调度的难度。

综合考虑无线传感器网络的应用特点和系统特性，衡量传输调度方法的优劣需要考虑以下几点。

1) 资源有效利用率：传输调度算法需要实现对无线信道的有效利用。当一条链路处于比较差的信道状态时，应尽量避免把当前的时隙分配给这条链路，以减少时隙浪费。

2) 延时特性：保证数据在截止期前到达接收方。过期的数据被认为是无效数据。

3) 可靠性：保证数据成功到达接收方，可通过合理分配无线通信资源、增加重传时隙、自适应跳频等方法实现。

4) 网络能耗：决定网络的工作时间，即网络寿命。

5) 实现复杂度：复杂度关系到传输调度算法的可实现性。虽然微电子技术和专用芯片飞速发展，但是复杂的传输调度算法将浪费大量的软硬件资源，可实现性较差；同时，复杂的传输调度算法的计算时间较长，不能迅速地做出决策，在网络动态性强的环境下实现困难。

6) 可扩展性：节点数量的增加对传输调度算法的影响较小。

在实际的传输调度算法设计中，需要根据应用场合和应用需求偏好，从上述评价指标中选择关键指标。

3 传输调度算法的分类

传输调度方法存在多种分类方式。根据可分配信道的数量，分为共享信道传输调度和多信道传输调度；根据对网络拓扑的依赖程度，分为拓扑相关和拓扑透明传输调度；根据被调度对象，分为节点激活、链路激活和混合激活传输调度；根据调度者，分为集中式传输调度、分布式传输调度和集中/分布混合式传输调度；根据接收者信息是否已知，分为广播传输调度和单播传输调度。下面对各种分类方式予以介绍。

1) 共享信道和多信道传输调度

共享信道传输调度针对网络中所有节点共享一条信道的情况，主要完成时隙分配，通常包括节点的时隙分配和节点内部任务的时隙分配2项工作，且这2项工作通常需要联合考虑。然而，将存在冲突关系的节点分配到不同信道传输可以很大程度降低干扰，提高网络的吞吐量。因此，目前大多数网络的研究集中于对多信道情况下各种技术的探索。传输调度方法进而由共享信道传输调度衍生为多信道传输调度。多信道传输调度主要完成信道的调度以及信道和时隙二维通信资源的调度，同样也包括节点的分配以及节点内部任务的分配2项工作，且这2项工作通常需要联合考虑。

2) 拓扑相关和拓扑透明传输调度

拓扑相关传输调度算法依赖网络的拓扑信息[8,9]，需要准确掌握网络的拓扑结构信息；而拓扑透明的传输调度算法仅依赖于节点数和节点可能的最大邻居数2个全局参数，与特定的拓扑结构无关，且不受节点移动性的影响。2类传输调度方法相比，拓扑相关传输调度方法带宽利用率高，调度结果逼近最优值，但收集网络信息的开销较大，且方法受网络拓扑结构的影响较大，仅适合于静态网络；拓扑透明的传输调度方法降低了传输调度重新计算和重新分配的代价，适合动态性较强的网络，但带宽利用率低于拓扑相关的传输调度方法，且网络延时较大。

3) 节点激活、链路激活和混合激活传输调度

节点激活传输调度是指为网络中的节点分配通信所需时隙和信道等，适合于高负载的广播和组播通信；链路激活是指为网络中的每条链路分配通信所需资源，适合于低负载的单播通信；混合激活是指为网络中的节点和链路都分配资源，适合于既有广播通信，也有单播通信的网络。根据网络的通信方式，3类传输调度方法适用于不同的网络环境。

4) 集中式、分布式和集中/分布混合式传输调度

集中式传输调度是指网络中的中心管理节点负责生成全网各个节点的调度方案，并将生成的调度结果分发给每个节点。分布式传输调度是指网络中的各个节点根据局部信息(如两跳或者三跳范围内的邻居节点)，分布式生成调度决策，或者通过协商生成调度决策。集中/分布混合式传输调度是由网络中的部分节点根据局部信息生成调度方案。集中式的传输调度的调度结果可以逼近最优结果，但是网络信息的收集和调度结果的分发过程会带来比较大的时间和控制开销；分布式传输调度的决策速度快，但相比集中式传输调度最优性较差；集中/分布混合式传输调度综合了集中式和分布式传输调度的优点。

5) 广播传输调度和单播传输调度

从接收者信息是否已知的角度分类，传输调度算法分为广播传输调度和单播传输调度。广播传输调度是指不需要知道接收者的信息，采用广播的方式发送数据；单播传输调度是指已知接收者的信息，为每个源-目的节点对分配通信所需资源。从实现的功能看，广播传输调度和单播传输调度分别对应于节点激活的传输调度和链路激活的传输调度，同样对应于不同的通信方式。

4 传输调度算法的研究现状

本节以共享信道传输调度和多信道传输调度的分类方式为主线，综合传输调度和功率控制联合设计这一研究热点，阐述无线传感器网络传输调度方法的研究现状。

4.1 共享信道传输调度

共享信道传输调度主要研究时隙的分配，即为网络中的每个节点或者每项任务分配传输数据所需的时隙。根据调度者分类，共享信道传输调度又可分为集中式和分布式传输调度。

1) 集中式共享信道传输调度

早期的集中式共享信道调度主要面向广播通信的网络。在网络组建以及网络控制阶段，节点通常以广播方式协调各自的行为。广播传输调度因此引起广大研究者的关注。广播传输调度问题是NP-完全问题，因而大部分算法采用集中启发式方法，需要掌握全局信息[10,11]。集中式广播传输调度算法一般采用图论的方法求解，以最大化时隙利用率或最小化超帧长度的方法来达到提高吞吐量和降低延时的目标。Arunabha和Vuong等人[12,13]通过寻找单个时隙内的最大传输集来最大化网络吞吐量，采用令牌深度优先搜索方法实现集中的启发式广播传输调度； Wang等人[14]采用神经网络、模拟退火等算法可以得到近优的广播调度方案，但算法复杂度高，且需要全局精确信息，工程实用性较差。

Ramanathan[10]将上述针对广播传输的调度方法进行了归纳和扩展，比较了时域、频域和码域中传输调度约束条件的相似性，首次提出了基于TDMA/FDMA/CDMA统一的传输调度架构。该架构基于物理空间上足够远的节点可以共享时隙、信道或编码的思想，致力于实现节点的空间复用。首先，利用图论的方法将网络模型搭建为有向图，且假设链路是单向非对称的。同时，根据被着色对象(节点或链路)、冲突关系(节点冲突或链路冲突)和传输方向(发送者和接收者)，将已有的 114种传输调度算法的约束归纳为11个原子约束，包括4个基于节点的约束和7个基于边的约束。图1所示的11个原子约束中，(1)～(4)为基于节点的约束，(5)～(11)为基于边的约束，其中，黑点和实线表示相互受干扰的节点和链路，空心点和虚线表示对其他节点和链路造成干扰的节点和链路。通过调整和限制 11个原子约束的组合方法，可以反映不同情况下的传输调度问题，同时作者设计了一个适用于时域、频域和码域的传输调度算法——UxDMA。

面向单播通信的共享信道传输调度往往采用集中式最大权链路调度算法[15～20]，选择无冲突链路集合中权值和最大的一组链路进行传输，目的在于保证网络吞吐量最大。该类算法以 Huanli等人[15]为代表。Yang等人[19]针对Huanli等人为代表的研究未考虑能耗的问题，提出一种基于最大权链路调度的最小能量调度 (MES，minimum energy scheduling)算法。MES算法基于随机流量模型和时变信道模型，以网络吞吐量和能耗作为优化指标，该算法可以作为能量受限的无线传感器网络协议设计的一个标志性算法。Nicholas等人[20]针对已有算法对于数据传输实时性、可靠性、公平性等考虑甚少的问题，提出一种简单易行且灵活的传输调度策略，旨在实现平均延时和公平性的折中。

图1 统一架构的原子约束

上述方法在考虑干扰时均采用协议干扰模型[21]，即如果节点i正在发送数据，则其邻居节点不能同时收发其他数据。然而，无线传输的范围不可能绝对抵达某个界限，协议干扰模型是对实际无线环境的简化，因此无法准确的描述无线干扰情况。理论和实验表明，节点j可以成功接收到来自节点i的数据的条件[22]是：节点i发往节点j的信号的强度与节点j接收到的所有干扰和噪声的比值大于一定阈值，即信号-干扰噪声比(SINR，signal to interference plus noise ratio)大于阈值，如式(1)所示。

其中，Pij表示节点i到节点j的传输功率；Gij表示节点i到节点j的信号增益；jη表示节点j上的热噪声表示网络中其他节点对节点j的累加干扰；γ0为用户自定义的阈值，取决于用于要求的QoS，如比特错误率(BER，bit error rate)。Gij通过远域模型Gij=di-jα表示。其中，dij表示节点i和节点j之间的欧几里得距离；α∈ [ 2,4]表示路径损耗因子。如果式(1)不能得到满足，则节点j无法成功接收到来自节点i的数据。

采用SINR干扰模型会给传输调度算法的设计带来新的挑战[23]：1) 引入SINR干扰作为约束，导致传输调度优化问题成为非凸优化问题，且导致大多数的问题成为NP-难问题，因此传统的凸规划技术不再适用于求解该类优化问题，需要另辟新的算法求解次优解；2)SINR的计算比较复杂，需要统计和记录大量的参数，因此采用SINR干扰模型会带来较大的计算开销。然而，采用SINR干扰模型可在理论上和实际中获得较好的网络性能。Moscibroda等人[24,25]指出，基于SINR干扰模型的传输调度算法能够提高网络的整体性能，如降低延时等。目前，基于SINR模型的传输调度算法成为新一轮的研究热点[22,26,27]。Goussevskaia等人[22]首次证明得出：基于SINR模型的传输调度问题是NP-完全问题，前提是假设节点分布在平面上。该项研究的另一个重大贡献在于将NP-完全问题中的一个典型实例“分化问题”[28]在多项式时间内化解为传输调度问题，从而为证明其他问题的计算复杂度提供了方法参考，如证明功率控制和传输调度联合问题的复杂度。Brar等人[26]基于SINR模型，提出一种多项式时间的启发式传输调度算法。并给出了节点均匀随机分布情况下该算法相对于最优算法的近似因数。Bjorklund等人[27]针对传统同步时分多址（STDMA）调度方法的最优解无法求得，导致启发式算法的性能不容易衡量的问题，以最小化超帧长度为优化目标，基于SINR干扰模型，利用列生成方法集中求解节点激活传输调度和链路激活传输调度这2个问题。

综上所述，集中式传输调度算法需要中心节点收集全局信息来生成全网调度，其带宽利用率高，但存在单点故障问题。此外，集中式传输调度算法不能很好地适应网络的动态变化，且需要浪费大量资源交互网络拓扑的变化信息，在节点快速、频繁移动时可能导致传输调度算法失效，网络瘫痪[29]。

2) 分布式共享信道传输调度

早期针对广播通信的分布式共享信道传输调度方法，通常以最小化超帧长度和最大化时隙利用率为目标[30～34]，且所得超帧长度与网络规模成正比。其中，最典型的算法包括Funabiki等人[30]提出的一种结合最小化超帧长度和最大化时隙利用率的算法。该算法在最小化超帧长度过程中，首先根据节点的两跳邻居数将全网的节点排序，然后依次给每个节点分配一个未被任意一个两跳邻居节点使用的最小时隙号。分配完成后，最大时隙号就是该网的最小超帧长度。在最大化时隙利用率过程中，按照相同规则为全网节点排序，依次为各节点分配最小时隙号，且允许节点使用多个未被两跳邻居节点使用的时隙。

为了适应网络的动态性、降低传输调度重新计算带来的协议开销，Chlamtac等人[35]面向单播通信，提出一种不依赖网络拓扑结构、仅依赖全局网络参数(最大节点数和节点的最大邻居数)的分布式传输调度方法，即拓扑透明传输调度方法。Chalamtac等人利用高斯域原理进行求解，保证网络中的每个节点在一个超帧周期内至少成功传输一次，且根据节点的流量要求动态增加节点的时隙数。然而，文中并没有对算法进行优化，算法的性能较差。基于Chalamtac等人的思想，Ju等人[36]以最大-最小吞吐量为优化目标，利用编码理论提出一种新的拓扑透明的传输调度解决方案。该方案不需要额外的控制参数，仅需要预估的节点数和最大邻居数作为参数。该算法在吞吐量和延时这2个方面的性能优于Chalamtac等人提出的算法。但算法的性能取决于节点数和邻居数的估计精度，因此算法的顽健性得不到保证。李卫等人[37]在螺纹协议T-TSMA[38,39]的基础上，提出一种根据当前网络拓扑和负载量，有效利用节点已分配和未分配时隙进行报文传输的调度方案(TTHM，topology transparent hybrid MAC protocol)。该算法不受最大节点密度的限制，便于分布式应用。

为了满足用户对QoS的要求，研究者们于80年代初开始研究基于预约的传输调度方法，即采用分布式竞争接入和预约调度结合发送数据的方法。基于预约的传输调度方法的主要目标是最大化网络寿命和协议的可扩展性，以及要求协议适应网络的变化。这些变化主要包括网络规模、拓扑、节点密度、节点加入和离开等。其他网络性能，如吞吐量、延时、可靠性和带宽利用率也是需要考虑的指标。典型的解决方案可以归纳为2类：基于控制信道预约的方法和基于控制时隙预约的方法。其中，基于控制信道预约的方法将信道划分为控制信道和数据传输信道；基于控制时隙预约的方法将时隙划分为控制时隙(或称预留时隙)和数据传输时隙。上述2类方法中，节点利用控制信道或者控制时隙预约数据传输所需的时隙，并利用预约成功的时隙进行数据传输。

基于控制信道和数据传输信道的方法中，控制信道用于节点交换传输调度请求、预约数据传输所需时隙以及解决隐藏终端和暴露终端冲突问题；数据传输信道用于节点传输数据。典型的研究包括IBM 托马斯▪沃森研究中心的 Cidon等人[8]于 1989年提出的分布式动态传输调度算法。该算法给出了该类传输调度的基本控制架构，主要解决多跳传输且网络动态性较强情况下的时隙分配问题。算法的基本思想是将信道划分为控制信道和数据传输信道。网络中的每个节点根据一跳的邻居信息分布式执行时隙分配算法。同时，针对控制开销不容忽视且固定优先级导致的不公平分配等缺陷，作者提出了优先级轮询算法和邻居等待算法。其中，优先级轮询算法在每个时隙开始，动态更换节点的优先级，保证网络中的每个节点在每个传输调度周期内都有机会传输数据；邻居等待算法在一个调度周期内，要求已分配时隙的节点等待其邻居节点全部被调度完成后，才可以再次参与分配过程，通过减少每个时隙的控制开销以降低整体控制开销。

Zhu等人[9]提出的 5阶段预留协议(FPRP，five-phase reservation protocol)适用于规模较大且节点动态性较强的网络。FPRP方法是一种通过5次握手，完成两跳范围内高概率、无冲突的分布式预约的广播传输调度机制。FPRP方法中的超帧结构如图2所示，该超帧结构与D-TDMA[40]方法所设计的超帧结构相似。Zhu等人[41]提出的E-TDMA算法是FPRP算法的改进版本，可以保证实时业务无冲突的发送，同时也能避免延时抖动，但控制开销较大、实现复杂且效率不高。电子科技大学通信抗干扰技术国家级重点实验室的郭伟等人[42]受文献[9]和文献[41]的启发，结合无线传感器网络的能量约束，提出了一种基于预约调度的 MAC协议——SSMAC。一方面解决了隐藏终端和暴露终端问题；另一方面在考虑节能的同时，降低了节点的接入延时，提高了报文的传输成功率且保证了延时、延时抖动、可用带宽和分组丢失率等 QoS指标。Phua等人[43]针对工业无线传感器网络中干扰周期性变化的特点，提出一种基于链路状态的传输调度(LSDS，link state dependent scheduling) 协议，其超帧结构如图3所示。LSDS协议只将信道的质量简单标记为“好”和“坏”，不能准确反映信道的实际质量。该算法虽然适用于干扰和衰减呈周期性变化的网络，但以随机方式建立调度使得其不适用于实时性、可靠性等要求较高的场合。

目前，部分学者对于汇聚传输的调度问题提出了分布式解决方案。Gandham等人[44]给出了对于节点数据为N的网络，通过传输调度最多只需要3N个时隙就能完成一次全网数据的汇聚传输，并提出了相应的算法。该算法虽然由各个节点自主决定传输时隙的分配，但是每个节点需要掌握网络拓扑中的分支总数、各分支长度、节点和各分支之间的传输干扰关系等多种信息，在计算复杂度上已经接近于集中式传输调度。孙利民等人[45]针对无线传感器网络汇聚传输的实时性，提出一种基于 TDMA的分布式节点调度算法。利用该算法进行一次全网数据收集，基本可以在 1.6～1.8倍网络节点数个时隙内完成，并且能够有效避免各节点之间的数据碰撞。另外，该算法调度时只需要各节点掌握一跳邻居信息，而在传输过程中节点最多只要缓存2个报文，因此满足无线传感器网络分布式、节点存储空间受限的要求。该算法在实时性和复杂度方面更具优势，但对网络局部区域突发性信息传输的实时性支持不够，也无法为多种不同级别的数据传输提供不同的实时性保证。

图2 FPRP和E-TDMA超帧结构

图3 LSDS超帧结构

Yi等人[46]提出的一系列考虑SINR模型的分布式动态随机调度 (DRS，dynamic randomized scheduling)算法。DRS首次尝试分布式求解基于SINR模型的传输调度问题。该类算法以最大化吞吐量为优化目标，不需要知道节点的位置信息，控制开销较小，可以较好地适应网络拓扑和负载的动态性，但算法计算复杂度高，不适合应用于规模较大的网络。

综上所述，分布式共享信道传输调度算法不需要收集全局的网络信息，克服了算法受网络规模限制的缺陷，网络动态适应性较好，但控制开销较大、实现复杂、最优性相比集中式较差。

4.2 多信道传输调度

Kyasanur等人[47]指出采用多个信道传输可以有效避免冲突。图5和图6所示分别为单信道和多信道情况下的干扰问题。图4中，节点3有数据收发时，干扰同一路径上的节点1，2，4，5，8以及路径2上的节点9和节点10。采用多信道后，干扰范围内的节点通过采用其他信道进行传输，从而在一定程度上避免了干扰。图5中，节点3和节点4利用1号信道传输时，节点1，2，5，8，9，10可同时利用其他信道进行传输，最大程度实现了并行传输。

Shin等人[48]证明了最优的多信道传输调度是NP-难问题，且归纳出多信道传输调度的一般解决方案是在满足接口约束和信道约束的条件下，为节点分配尽可能多的信道。目前多信道传输调度的研究内容主要包括2个方面：信道调度以及时隙和信道联合调度。信道调度主要研究如何为网络中的节点分配通信所需信道。目前存在2类方法：动态信道分配法和半静态信道分配法。其中，动态信道分配法要求节点频繁改变通信所用的信道，如为每条链路分配信道且每发送1次数据改变1个信道。这种多信道调度方法要求快速的信道切换速度，而现有的硬件技术中信道切换时延为毫秒级，因此无法满足实时切换的要求。半静态信道分配法是根据负载量和网络拓扑的显著变化而改变信道。因此在网络环境和负载量相对稳定的条件下，信道切换不频繁。信道和时隙联合调度主要研究如何为网络中的节点分配通信所需的时隙和信道，目前这方面的研究比较初步。

图4 单信道无线传感器网络路径内和路径之间的干扰

图5 多信道无线传感器网络路径内和路径之间的干扰

下面以调度者为分类依据，总结多信道传输调度的研究现状。

1) 集中式多信道传输调度

针对图着色算法无法满足多信道调度中的接口约束、信道约束、网络连通约束和带宽约束，Raniwala等人[49]以最大化网络总吞吐量为优化目标，以信道数量、接口数量、网络连通要求和流量限制为约束条件，提出基于网络负载量变化的多信道启发式调度 (LACA，load-aware channel assignment)方法。LACA算法以预估的网络负载量的期望值为输入，将具有冲突关系的链路分组后，采用迭代方法按序为网络中的每个节点分配通信所需信道。该算法将单信道的IEEE 802.11标准扩展到多信道的应用场合，采用集中式的求解方法，且要求网络拓扑固定不变。但由于LACA算法侧重于满足流量约束，在迭代过程中仅以流量为反馈量修正信道调度结果，因此算法可行性方面考虑欠缺。

Das等人[50]以最大化并行传输的链路数为目标，以干扰、信道数和接口数为约束条件，提出 2个面向静态多信道调度问题的混合整数线性规划模型，但是并未给出可实现的多项式时间算法。Soldati和 Zhang等人[51～53]基于无线 HART标准，基于线型路由和树型路由下完成汇聚传输所需时隙数和信道数的理论下限值，提出一种时隙和信道联合分配的传输调度算法。

综上所述，集中式多信道传输调度算法需要收集全局网络信息，与集中式共享信道传输调度算法相似，也存在单点故障问题。

2) 分布式多信道传输调度

目前，大部分学者的研究集中于分布式多信道传输调度算法。分布式多信道传输调度算法大多数采用提前预留资源的方法。与分布式共享信道传输调度算法相比，这类方法将预留的资源扩展为时隙和信道。Nasipuri等人[54]提出一种基于CSMA的软信道预留算法。该算法由节点分布式执行，并要求节点同时可以侦听所有信道上的数据传输情况。当节点有数据需要发送时，从空闲信道中选择上次传输成功的信道进行传输。之后，Nasipuri等人[55]又改进了空闲信道选择方法，将发送端信道强度最大的信道作为最佳选择。该算法在网络吞吐量方面具有很好的性能，但由于要求每个节点上安装多个收发器，因此硬件成本太大。

Wu等人[56]将收发器的数量减为2个，提出了一种按需动态信道调度算法DCA。DCA算法中，网络中的信道被划为控制信道和数据信道。每个节点的2个收发器可以同时侦听到来自控制信道和数据信道的数据。节点之间通过RTS/CTS握手方式交互通信所需信道。由于节点的一个收发器始终侦听控制信道上的数据，因此，DCA算法不存在多信道隐藏终端。同时，DCA算法不需要精确同步，控制开销较小。但由于该算法采用专用信道进行协商，因此对于网络信道数较少的应用场合，控制开销较大；其次，对于可用信道数较多的应用场合，单条控制信道又会成为信道协商的瓶颈，导致无法充分利用数据信道。Jain等人[57]在DCA算法的基础上，改进了目的端节点选择信道的方法，选择质量最好的信道作为数据信道。但改进的 DCA算法仍然未解决DCA算法的缺陷。

So等人[58]针对上述算法中存在的硬件成本大、控制开销高和多信道隐藏终端问题，面向单收发器的节点，以时间为代价实现多信道传输调度的协商过程。在算法开始阶段，网络中的所有节点在规定的时间内采用统一信道进行协商，这一时间段称为信道协商阶段。信道协商阶段后，收发双方按照预先协商好的信道进行通信。该算法需要精确地全网时间同步以克服多信道隐藏终端问题；同时，由于采用单收发器，因此硬件成本小。但由于该算法需要另辟一段时间用于信道协商，因此在克服控制信道所需开销的同时，引入了新的时间开销，不适合实时性要求较高的应用场合。Ko等人[59]在探讨信道调度策略前，致力于达到3个方面的目标：1)仅依赖局部信息作出信道调度决策；2)信道调度策略基于网络的物理结构，而非动态的网络信息；3)信道调度的结果不应该频繁改变网络的连接状态，可为端到端的路由提供较为稳定的网络环境。基于上述目标，提出了一个分布式的轻型信道调度策略。该策略由节点分布式执行，以最小化局部干扰总和为目标，仅依赖节点的局部信息，采用贪婪算法进行求解，实现了网络连通性和信道多样性的折中。实验表明，该算法执行时间短且网络容量高，但未考虑接口数量对于信道调度的影响。

目前，针对无线传感器网络的时隙和信道联合调度的研究比较少见，典型的研究包括MMSN[60]、MCMAC[61]、Y-MAC[62]和 TFMAC[63]等。

Zhou等人[60]首次面向无线传感器网络提出一种多信道MAC协议(MMSN，multi-frequency MAC for wireless sensor networks)。MMSN算法充分考虑了无线传感器网络的以下2个特点：出于能耗和成本考虑，传感器节点仅安装一个收发器，因此节点不能同时收发数据且不能同时工作在多个频段；无线传感器网络中的报文长度较短，因此传统方法中基于 RTS/CTS交互的通信方式带来的控制开销不容忽视。MMSN算法由信道分配和介质访问2个阶段组成。在信道分配阶段，节点分布式协商信道的分配且以广播方式通知邻居节点。MMSN算法在降低能耗和提高节点并行传输等方面性能突出，但其属于静态分配方法，不适用于网络环境动态变化的场合。为了克服静态分配不灵活的缺陷，Chen等人[61]为节点动态分配多个信道，并考虑分簇网络的信道和时隙联合调度，提出一种基于协调者的多信道MAC协议MCMAC。MCMAC算法将N个信道分为1个控制信道和(N-1)个数据传输信道，并扩展了IEEE 802.15.4的超帧结构，如图6所示。MCMAC算法在提高网络能效性、网络寿命方面可以获得较好的性能。但由于超帧的活动期阶段大部分时间用于簇成员请求信道分配，因此，控制开销比较大，影响网络吞吐量。

Kim等人[62]针对传统能量有效的多信道调度算法以牺牲吞吐量为代价的问题，提出一种能量有效的多信道轻型传输调度算法 Y-MAC，旨在解决网络中突发数据的传输问题。Y-MAC算法要求节点局部协调时隙的分配，是一个面向接收者的调度方法。Y-MAC算法避免了节点侦听信道的能耗，可以有效处理突发数据的传输；同时，采用多信道传输机制提高了数据传输的成功率且降低了延时。Jovanovic等人[63]以提高网络吞吐量为目的，提出一种分布式时隙和信道联合调度算法(TFMAC，time frequency MAC)。TFMAC算法中的超帧包括2个阶段：竞争阶段和非竞争阶段。其中，竞争阶段由控制时隙组成，用于节点收集邻居节点的时隙和信道分配结果，随机选择多个空闲时隙和一个接收信道，并广播自身的选择结果。非竞争阶段用于节点在指定的时隙和信道上进行通信。TFMAC算法中，每个节点的发送时隙数等于网络中的信道数。该算法可以最大限度地提高网络中节点的并行传输，提高网络吞吐量，但无法避免时隙和信道选择过程中的冲突问题，因此对于规模较大的网络效率比较低；同时，TFMAC算法为每个节点在每条信道上分配时隙，对于负载量较轻的应用，资源浪费严重。

综上所述，分布式多信道传输调度采用固定分配方式则灵活性不够，采用动态分配方式则控制开销较大、效率较低。

3) 集中/分布混合式多信道传输调度

由于传统的动态信道调度方法会改变网络的初始拓扑结构，影响网络其他方面的设计，如路由等，导致全网调度低效。为了克服上述问题，Subramanian和Gupta等人[64]在满足接口约束的前提下，以最小化网络干扰度为优化目标，采用半正定规划法求解该优化问题。将网络构造为冲突图，首次求取了网络干扰度的下限值。同时，以网络干扰和流量模型为输入，分别设计了集中式和分布式的启发式算法来逼近下限值。所提算法的优势在于提高了网络吞吐量、不影响路由决策、易于实现以及适用于正交信道和非正交信道的分配。

图6 IEEE 802.15.4和MAMAC的超帧比较

Martin等人[65]针对网络中信道数量受限的情况，提出一种分簇的信道调度方法(CCA，cluster channel assignment)，目的在于实现信道在多个簇之间的复用、最大化网络平均吞吐量以及最小化干扰。该方法是集中式和分布式结合的动态、按需的信道调度方法。CCA方法的优势在于：将信道分配的难度分散到每个簇内，易于执行；允许使用网络中的空闲信道，可以有效利用带宽且避免干扰；允许簇首自主调整本簇的信道分配，灵活性更强，且可以有效克服干扰等时空特性。

Nikolaidis等人[66]考虑无线传感器网络中的汇聚传输，通过构建树阶段和调度阶段实现调度。作者证明了所需调度长度的下限值，并基于该值利用二偶图的半匹配方法构建树，最后综合节点的权重和干扰约束等，采用基于排列的方法为网络中的每个节点分配通信资源。

针对我国新进颁布实施的工业无线网络标准WIA-PA，部分学者给出了集中和分布式结合的 2阶段资源调度方法[67,68]。该类方法面向网络-星型的混合拓扑结构，针对簇内和簇间的通信，采用搜索算法，分别为网络中簇内和簇间的不同设备分配信道和时隙资源。

综上所述，现有的多信道传输调度算法分配方式固定，开销较大，没有充分考虑无线环境的时变特性，对可靠性和实时性考虑也较少，因此不适合应用于环境复杂多变的无线网络中，特别是工业无线传感器网络。

4.3 传输调度和功率控制的联合

功率控制被用于动态调整发送节点的功率，不仅能够有效减少通信中的能量消耗，延长无线传感器网络的寿命，同时对于网络的拓扑控制与连通性、吞吐量、消息传递的实时性等系统性能具有显著的影响，而且可以通过MAC层或跨层协议的设计，优化网络性能，为提升QoS提供有效途径[69]。根据控制范围，功率控制方法包括：网络级控制、邻居节点级控制和独立节点级控制[69]。其中，网络级功率控制是指网络中所有节点均使用统一的优化功率值发送数据；邻居节点级功率控制是指每个节点均使用可覆盖其所有邻居节点的功率值发送数据，而节点之间的发射功率值并不相同；独立节点级功率控制是指发送节点可以针对每个单一的目的节点，自适应调整发射功率水平。

传输调度和功率控制的联合研究，大致包括 3个方面。1)功率控制-传输调度法。首先从上述3种功率控制方法中选择其一，确定节点的发射功率，从而确定网络的干扰范围和连通性后。研究传输调度算法；2)传输调度-功率控制法。首先按照一定的干扰模型，如协议干扰模型和SINR干扰模型等，确定传输调度方案，随后根据源-目的节点关系，调节节点的发射功率；3)传输调度和功率控制的联合研究。研究发现，将传输调度与功率控制独立研究的效率较低[70]。这主要是功率调节会引起节点发送范围的改变，从而引起周围信道容量的改变。为了提高传输调度和功率调节的效率，一些学者将二者的联合问题等价为一个高复杂性的非凸最优解问题，进行了研究。该类研究给出的一些调度算法是初步的，仅适用于小型网络的应用。

ElBatt和Ephremides[71]以提高单跳吞吐量和延长网络寿命为目的，首次针对传输调度和功率控制的联合问题进行了研究，并采用传输调度和功率控制交互的方式求解该联合问题。Lu等人[72]提出一种基于SINR干扰模型的能量高效传输调度和功率控制联合算法，属于上述的传输调度-功率控制法之列。首先将传输调度和功率控制的联合问题形式化为一个考虑能量、吞吐量和延时折中的优化问题TJSPC；随后，设计了2个指数时间和多项式时间的贪婪算法求解TJSPC问题；最后，在保证所有报文截止期约束的条件下，研究了以最小化能耗为目的的传输调度和功率控制联合问题。该算法针对静态单信道无线网络，因此不适合于动态场合，且所给优化模型无法有效扩展到多信道的应用场合中。Wang等人[73]提出一种适合于组播的传输调度和功率控制联合算法。该算法以功率控制为主，基于SINR模型，以最小化传输功率为优化目标，利用线性规划方法寻求功率最优值；如果搜索不到功率最优值，则调用传输调度和功率控制联合算法，利用传输调度最大限度降低干扰后，重新执行功率控制算法。该算法由节点分布式执行，依赖局部信息，属于一个次优算法。Moscibroda等人[74,75]分析了利用启发算法求解传输调度和功率控制联合问题在最坏情况下所需时隙的上限值，而没有给出与最优结果的逼近程度。针对上述问题，Fu等人[76]研究了SINR干扰模型下的最小超帧长度传输调度和功率控制联合问题，首次证明了SINR干扰模型下的最小超帧长度传输调度和功率控制联合问题是NP-完全问题，并提出一个多项式时间的集中式近似算法——保障贪婪算法GGS。同时，给出了GGS算法所求结果与最优结果的逼近度，并分析得出 GGS算法可适合于任何网络拓扑结构。然而，在一些网络环境中，GGS算法的最优性往往会松弛。因此，寻找紧界且分布式的算法是未来的一个研究挑战。

表1 典型传输调度算法的特点比较

5 传输调度算法的分析和比较

由于无线传感器网络中节点的构成、应用场景、用户需求等不尽相同，故传输调度算法具有多样性的特点，使得算法优劣的比较具有较大难度。表1使用本文的分类方法对上述重点介绍的传输调度算法进行了详细的比较。在实际应用中，应当根据网络的特点和用户的要求选择合适的传输调度算法。具体采用何种方法，主要根据具体的网络环境和用户需求而定，同时考虑网络结构、实现难度和部署成本等因素，并在诸多因素之间作出选择和折中。

6 结束语

如前所述，传输调度因其在保障网络性能和有效避免干扰等方面展现出的巨大潜力，正吸引着越来越多学者的关注。研究人员针对无线传感器网络的应用需求和新特征进行了大量卓有成效的研究，新的传输调度方法层出不穷。但由于各种传输调度方法关注的网络特性、优化的性能指标、采取的技术手段和面向的具体应用各不相同，因而实际效果千差万别。事实上，无线传感器网络的传输调度方法研究的趋势并没有呈现收敛性，也无法形成标准。究其原因：首先，传输调度方法不可避免的受到物理硬件平台和物理层协议的影响，而目前作为协议栈底层基础架构的物理层仍缺乏统一的标准；其次，无线传感器网络与应用高度相关，应用差异性使得传输调度方法无法兼顾所有的网络特性，只能在多个性能指标之间做出选择和折中。鉴于无线传感器网络对于应用相关的要求(主要为实时性和可靠性)更加严格，使得现阶段的研究工作在调度建模、约束满足、调度方法、容限分析、测试和验证等方面还存在很多需待解决的问题。下面予以概况，供今后研究参考。

1) 调度建模问题

建模是对实际问题的抽象和简化，是调度算法设计和分析的基础。无线传感器网络的传输调度问题具有复杂动态、多目标、多约束等特点，需要重点解决考虑多种因素、综合多种指标的传输调度建模问题。而针对目前无线传感器网络的应用特点，传输调度的约束主要由点到点单跳传输间的顺序关系、报文截止期、单跳成功率、与位置相关的信道占用以及能量等约束构成；传输调度的目标主要由资源利用率、截止期、能耗以及各目标的均衡构成。同时，无线传感器网络的应用环境，特别是工业应用环境，存在不确定因素：环境干扰严重、温度变化范围大(一般从-45℃～80℃)；高湿度、高震动以及频繁移动的人员和设备，使得信道的状态和容量会随着时间、位置和频率而变化；节点加入、离开和失效等导致网络拓扑结构和路由等也具有动态性。种种因素对传输调度的精确建模提出了更高的实用性和灵活性要求，增加了调度建模的难度。因此，需要对具有动态适应性、复杂时空约束和多目标的传输调度问题进行精确建模。

2) 约束满足问题

目前无线传感器网络对报文截止期和成功传输率的要求更加苛刻。在网络动态性强、信道时空变化频繁等前提下，如何将端到端的截止期约束和成功传输率约束转化为传输调度算法所能处理的单跳约束，是需要下一步解决的问题。而目前的传输调度方法对这2个约束考虑较少，致使现有研究成果无法直接应用。

3) 调度方法问题

大规模网络、周期性任务等特点，使得问题的求解面临着组合爆炸问题；大规模、分布式等特点，使得集中式算法无法满足应用，而分布式局部调度算法又面临着无法保证确定性要求和全局最优的困扰。非周期性任务、信道状态的动态变化、拓扑结构和路由的改变等不确定性因素，对传输调度方法提出了更高的自适应要求。现有的集中式传输调度方法，存在单点故障问题且开销较大，而分布式传输调度方法仅限于小规模网络的应用。此外，现有的传输调度方法分配方式固定，主要面向周期性任务，而且对网络的动态性考虑较少。因此，需要研究适用于大规模网络的、分布式优化的、适应网络动态性的、快速和轻型的传输调度方法。

4) 容限分析问题

网络容量和所需通信资源上下限，是评价传输调度算法优劣的关键指标。现有的研究主要针对Ad hoc网络以及网状结构的无线传感器网络进行分析，且不考虑底层协议对于网络容量的影响，从而导致分析结果过于理想。因此，需要研究考虑底层协议，特别是传输调度协议下的网络容量，为后续底层协议的设计和优化提供理论依据。

5) 测试和验证问题

无线传感器网络在工业中的应用才刚刚起步，现有的研究还主要采用仿真验证和小规模实验验证，缺乏完善的实验平台和验证体系。需要设计和开发实验平台，建立评价体系，以对研究成果进行有效地验证。

综上所述，面向无线传感器网络的传输调度问题，是具有明确应用背景和相当研究难度的问题，已有的传输调度理论和方法还不能满足实际问题的需求，尤其是目前对于可靠传输调度的研究仍然是一个空白。另一方面，在传输调度理论已经取得重要进展的前提下，针对新领域、发掘新问题，面向实际拓展研究的深度和广度，是传输调度理论研究的重要方向。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y,et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4):393-422.

[2] 孙利民,李建中.无线传感器网络[M].北京:清华大学出版社,2005.SUN L M, LI J Z. Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.

[3] ESTRIN D, GOVINDAN R, HEIDEMANN J. Next century challenges: scalable coordination in sensor networks[A]. Proc of ACM MOBICOM[C]. Seattie, USA, 1999. 263-270.

[4] 谷有臣,孔英,陈若辉.传感器技术的发展和趋势综述[J].物理实验,2002, 22(12): 40-42.GU Y C, KONG Y, CHENG R H. Development and trend of sensor technology[J]. Physics Experimentation, 2002, 22(12): 40-42.

[5] WEISER M. The computer for the twenty-first century[J]. Scientific American, 1991, 265(3): 94-104.

[6] 田乃硕,徐秀丽,马占友.离散时间排队论[M].北京:科学出版社, 2008.TIAN N S, XU X L, MA Z Y. Discrete Time Queuing Theory[M].Beijing: Science Press, 2008.

[7] STANKOVIC J A. Research challenges for wireless sensor networks[J]. SIGBED Review: Special Issue on Embedded Sensor Networks and Wireless Computing, 2004, 1(2): 9-12.

[8] CIDON I, SIDI M. Distributed assignment algorithms for multihop packet radio networks[J]. IEEE Transactions on Computers, 1989,38(10): 1353-1361.

[9] ZHU C, CORSON M S. A five-phase reservation protocol (FPRP) for mobile ad hoc networks[A]. Proc of IEEE Conference on Computer Communications (INFOCOM)[C]. San Francisco,USA,1998. 322-331.[10] RAMANATHAN R. A unified framework and algorithm for channel assignment in wireless networks[J]. Wireless Networks, 1999, 5(2):81-94.

[11] RAMANATHAN S, LLOYD E L. Scheduling algorithm for multihop radio networks[J]. IEEE/ACM Transactions on Networking, 1993,1(2): 166-177.

[12] ARUNABHA S, JEFFRY M C. Scheduling in packet radio networks -a new approach[A]. Proc of IEEE GLOBECOM[C]. Rio de Janeiro,Brazil, 1999. 650-654.

[13] VUONG T H P, HUYNH D T. Adapting broadcasting sets to topology changes in packet radio networks[A]. Proc of the 8th International Conference on Computer Communications and Networks (IC3N 1999)[C]. Boston, USA,1999. 263-268.

[14] WANG G, ANSARI N. Optimal broadcast scheduling in packet radio networks using meanfield annealing[J]. IEEE JSAC, 1997, 15(2):250-260.

[15] HUANLI P S, RAMAMRITHAM K. Scheduling messages with deadlines in multi-hop real-time sensor networks[A]. Proc of IEEE Real Time and Embedded Technology and Applications Symposium[C].San Francisco, USA, 2005. 415-425.

[16] HAJEK B, SASAKI G. Link scheduling in polynomial time[J]. IEEE Transactions on Informatic Theory, 1988, 34(5): 910-917.

[17] YI Y, PROUTIERE A, CHIANG M. Complexity in wireless scheduling: impact and tradeoffs[A]. Proc of 9th ACM MOBIHOC[C]. Hong Kong, China, 2008. 33-42.

[18] WARRIER S, JANAKIRAMAN, RHEE I. Diffq: practical differential backlog congestion control for wireless networks[A]. Proc of IEEE INFOCOM[C]. Rio de Janeirio, Brazil, 2009. 1-9.

[19] YANG S, ZHANG C, FANG Y G. Minimum energy scheduling in multi-hop wireless networks with retransmissions[J]. IEEE Transactions on Wireless Communications, 2010, 9(1): 348-355.

[20] ADITYA D, NICHOLAS B. On the fairness delay trade-off in wireless packet scheduling[A]. Proc of IEEE GLOBECOM[C]. St Louis,USA, 2005. 2544-2548.

[21] GUPTA P, KUMAR P R. The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000, 46(2): 388-404.

[22] GOUSSEVSKAIS O, OSWALD Y A, WATTENHOFER R. Complexity in geometric SINR[A]. Proc of ACM MOBIHOC’09[C]. Louisiana, USA, 2009. 100-109.

[23] CHAFEKAR D, KUMAR V S A, MARATHE M V. Cross-layer latency minimization in wireless networks with SINR constraints[A].Proc 8th ACM MOBICOM[C]. Montreal,Canada, 2007. 110-119.

[24] MOSCIBRODA T, WATTENHOFER R, WEBER Y. Topology control meets SINR: the scheduling complexity of arbitrary topologies[A].Proc of ACM MOBIHOC[C]. Florence, Italy, 2006. 310-321.

[25] MOSCIBRODA T, WATTENHOFER R. The complexity of connectivity in wireless networks[A]. Proc of IEEE INFORCOM[C]. Barcelona, Spain, 2006. 1-13.

[26] BRAR G, BLOUGH DM, SANTI P. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks[A]. Proc of ACM MOBICOM[C].Los Angeles, USA, 2006. 2-13.

[27] BJORKLUND P, VARBRAND P, YUAN D. A column generation method for spatial TDMA scheduling in ad hoc networks[J]. Ad Hoc Network, 2004, 2(4): 405-418.

[28] KARP R M. Reducibility among combinatorial problems[A]. Proceedings of Symposium on the Complexity of Computer Computations[C]. New York, USA, 1972. 85-103.

[29] 吕俊,于全,汪李峰.移动Ad Hoc网络中基于TDMA的媒体访问控制技术[J].现代通信技术,2004,17(3):13-19.LU J, YU Q, WANG L F. TDMA medium access control technology in mobile ad hoc network[J]. Modern Communication Technology,2004, 17(3):13-19.

[30] FUNABIKI N, TAKEFUJI Y. A parallel algorithm for broadcast scheduling problem in packet radio networks[J]. IEEE Transactions on Communications, 1993, 41(6): 828-831.

[31] POST M, KERSHENBAUM A, SARACHIK P. A distributed evolutionary algorithm for reorganizing network communications[A]. Proceedings of MILCOM’85[C]. Boston, USA, 1985. 133-139.

[32] POND L C, LI V O K. A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks[A]. Proc of IEEE MILCOM’89[C]. Boston, USA, 1989. 70-74.

[33] RAMASWAMI R, PARHI K K. Distributed scheduling of broadcast in a radio network[A]. Proc of IEEE INFORCOM’89[C]. Ottawa,Canada, 1989. 497-504.

[34] EPHREMIDES A, TRUONG T. Scheduling broadcasts in multihop radio networks[J]. IEEE Transactions on Communications, 1990,38(4): 456-460.

[35] CHLAMTAC I, FARAGO A. Making transmission schedules immune to topology changes in multi-hop packet radio networks[J].IEEE/ACM Transactions on Networking, 1994, 2(1): 23-29.

[36] JU J H, VICTOR O K, L I. An optimal topology-transparent schedul-ing method in multihop packet radio networks[J]. IEEE/ACM Transactions on Networking, 1998, 6(3): 298-306.

[37] 李卫,王杉,魏急波. Ad hoc网络中基于拓扑透明特性的混合 MAC协议[J]. 软件学报, 2009, 20(6): 1642-1650.LI W, WANG S, WEI J B. Topology-transparent hybrid MAC protocol for ad hoc networks[J]. Journal of Software, 2009, 20(6):1642-1650.

[38] CHLAMTA I, FARAGO A, ZHANG H. Time-spread multiple-access(TSMA) protocols for multihop mobile radio networks[J]. IEEE/ACM Transactions on Networking, 1997, 5(6): 804-817.

[39] KRISHNAN R, STERBENZ J P G. An Evaluation of the TSMA Protocol as a Control Channel Mechanism in MMWN[R]. BBN Technical Report, 2000.

[40] JOSEPH K, WILSON N D, GANESH R,et al. Packet CDMA versus dynamic TDMA for multiple access in an integrated voice/data PCN[J]. IEEE JSAC, 1993, 11(6): 870-884.

[41] ZHU C X, CORSONMS M C. An Evolutionary-TDMA Scheduling Protocol (E-TDMA) for Mobile Ad Hoc Networks[R]. ISR Technical Report, 2001.

[42] 杨双懋,郭伟.基于预约调度的无线传感器网络的MAC协议[J].计算机应用研究, 2008, 25(3):855-859.YANG S M, GUO W. Schedule-based sensor MAC protocol in wireless sensor network[J]. Application Research of Computers, 2008,25(3): 855-859.

[43] PHUA V, DATTA A, CARDELL-OLIVER R. A TDMA-based MAC procotol for industrial wireless sensor network applications using link state dependent scheduling[A]. IEEE GLOBECOM '06[C]. San Francisco, USA, 2006. 1-6.

[44] GANDHAM S, ZHANG Y, HUANG Q F. Distributed minimal time convergecast scheduling in wireless sensor networks[A]. Proc of the 26the International Conference on Distributed Computing Systems(ICDCS)[C]. Lisboa, Portugal, 2006. 50-57.

[45] 柯欣,孙利民,吴志美.基于无线传感器网络汇聚传输实时性的分布式调度算法[J].通信学报,2007,28(4): 44-50.KE X, SUN L M, WU Z M. Distributed scheduling for real-time convergecast in wireless sensor networks[J]. Journal on Communication,2007, 28(4): 44-50.

[46] YI Y, VECIANA G D, SHAKKOTTAI S. On optimal MAC scheduling with physical interference[A]. Proc IEEE INFOCOM[C]. Anchorage, USA, 2007. 294-302.

[47] KYASANUR P, VAIDYA N H. Capacity of multi-channel wireless networks: impact of number of channels and interfaces[A]. Proc of ACM MOBICOM[C]. Cologne, German, 2005. 1-15.

[48] KIM Y G, SHIN H J, CHA H J. Y-MAC: an energy-efficient multi-channel MAC protocol for dense wireless sensor networks[A].Proc of International Conference on Information Processing in Sensor Networks (IPSN 2008)[C]. St Louis, USA, 2008. 55-63.

[49] RANIWALA R, CHIUEH T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[A]. IEEE INFOCOM’05[C]. Miami, USA, 2005.2223-2234

[50] DAS A, ALAZEMI H, VIJAYAKUMAR R,et al. Optimization models for fixed channel assignment in wireless mesh networks with multiple radios[A]. Proc of IEEE SECON[C]. Santa Clara, USA, 2005.

[51] SOLDTI P. On Cross-layer Design and Resource Scheduling in Wireless Networks[D]. Stockholm, Sweden, KTH, 2009.

[52] SOLDTI P, ZHANG H, HOHANSSON M. Deadline-Constrained Transmission Scheduling and Data Evacuation in WirelessHART Networks[R]. KTH Technical Report, 2009.

[53] ZHANG H, SOLDTI P, HOHANSSON M. Optimal link scheduling and channel assignment for convergecast in linear WirelessHART networks[A]. The 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT’09)[C].Seoul, Korea, 2009. 1-8.

[54] NASIPURI A, DAS S R. A multichannel CSMA MAC protocol for multihop wireless networks[A]. Proc of IEEE Wireless Communications and Networking Conference (WCNC)[C]. New Orleans,USA,1999. 1402-1406.

[55] NASIPURI A, DAS S R. Multichannel CSMA with signal power-based channel selection for multihop wireless networks[A]. Proc of IEEE Vehicular Technology Conference (VTC)[C]. Tokyo, Japan, 2000. 211-218.

[56] WU S L, LIN C Y, TSENG Y C,et al. A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks[A]. Int Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN)[C]. Dallas, USA, 2000. 232-237.

[57] JAIN N, DAS S. A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[A].Proc of 9th International Conference on Computer Communications and Networks (IC3N)[C]. Scottsdale, USA, 2001. 432-439.

[58] SO J, VAIDYA N H. Multi-channel MAC for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[A].Proc of ACM MOBIHOC[C]. Roppongi Hills, Japan, 2004. 222-233.

[59] KO B J, MISRA V, PADHYE J,et al. Distributed channel assignment in multi-hop 802.11 mesh networks[A]. Proc of IEEE Wireless Communications and Networking Conference (WCNC’07)[C]. Hong Kong,China, 2007.

[60] ZHOU G, HUANG C D, YAN T,et al. MMSN: multi-frequency media access control for wireless sensor networks[A]. Proc of IEEE INFOCOM[C]. Barcelona, Spain, 2006. 1-13.

[61] CHEN X, HAN P, HE P S,et al. A multi-channel MAC protocol for wireless sensor networks[A]. Proc 6th IEEE International Conference on Computer and Information Technology (CIT’06)[C]. Bhubaneswar,India, 2006.1-6.

[62] KIM Y G, SHIN H J, CHA H J. Y-MAC: an energy-efficient multi-channel MAC protocol for dense wireless sensor networks[A].Proc of International Conference on Information Processing in Sensor Networks (IPSN 2008)[C]. St Louis,USA, 2008. 55-63.

[63] JOVANOVIC M D, DJORDIEVIC G L. TFMAC: multi-channel MAC protocol for wireless sensor networks[A]. Proc of IEEE INFOCOM[C]. Barcelona, Spain, 2006. 23-26.

[64] SUBRAMANIAN A P, GUPTA H, DAS S R. Minimum interference channel assignment in multi-radio wireless mesh networks[A]. Proc of IEEE SECON[C]. San Diego, USA, 2007. 481-490.

[65] SADEQ A, AMINE K, MARTIN K. Dynamic channel assignment for wireless mesh networks using clustering[A]. Proc of Seventh International Conference on Networking (ICN 2008)[C]. Cancun, Maxico,2008. 539-544.

[66] MALHOTRA B, NIKOLAIDIS I, NASCIMENTO M A. Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011, 17(2): 319-335.

[67] ZHANG X L, Capcity Analysis and Transmission Scheduling for Industrial Wireless Sensor Networks[D]. Doctoral Thesis, Shenyang,SIA, 2011.

[68] LIANG W, ZHANG X L, XIAO Y,et al. Survey and experiments of WIA-PA specification of industrial wireless network[J]. Wireless Communications and Mobile Computing, 2011, 11(8): 1197-1212.

[69] 李方敏, 徐文君, 刘新华. 无线传感器网络功率控制技术[J]. 软件学报, 2008, 19(3): 716-732.LI F M, XU W J, LIU X H. Power control for wireless sensor networks[J]. Journal of Software, 2008, 19(3): 716-732.

[70] GOLDSMITH A, WICKER S. Design challenges for energy-constrained ad hoc wireless networks[J]. IEEE Wireless Communications, 2002, 9(4): 8-27.

[71] ELBATT T, EPREMIDES A. Joint scheduling and power control for wireless ad hoc networks[J]. IEEE Transaction on Wireless Communications, 2002, 3(1): 74-85.

[72] LU G, KRISHNAMACHARI B. Energy efficient joint scheduling and power control for wireless sensor networks[A]. Proc of Sensor and Ad Hoc Communications and Networks (IEEE SECON’05)[C].Santa Clara, USA, 2005. 361-373.

[73] WANG K, CARLA F C, RAMESH R R,et al. A distributed joint scheduling and power control algorithm for multicasting in wireless ad hoc networks[A]. IEEE International Conference on Communications(ICC’03)[C]. Anchorage, USA, 2003. 725-731.

[74] MOSCIBRODA T, WATTENHOFER R. Minimizing interference in ad hoc and sensor networks[A]. Proc of DLALM-POMC’05[C].Cologne, German, 2005. 1-10.

[75] MOSCIBRODA T, OSWALD Y A, WATTENHOFER R. How optimal are wireless scheduling protocols[A]. Proc of IEEE INFORCOM[C]. Anchorage, USA, 2007. 1433-1441.

[76] FU L Q, LIEW S C, HUANG J W. Power controlled scheduling with consecutive transmission constraints: complexity analysis and algorithm design[A]. Proc of IEEE INFOCOM[C]. Rio de Janeiro,Brazil, 2009. 1530-1538.