1.4.2　分布式调度[32]

1. 基本概念

无线传感器网络、无线自组织网络和物联网等属于资源受限的网络，通常会受到节点能量、通信带宽、计算能力和存储能力等的约束。调度技术是在这些约束条件下优化网络性能的一种重要方法。网络中的节点调度根据是否能获取全局信息可以分为集中式调度与分布式调度。在分布式调度中，网络中的每个节点接收网络环境的局部信息并独立做出调度决策。

分布式调度的优化目标通常是：提高能量效率以延长网络的生存时间，减少数据包（从源节点发出到被目的节点接收）的网络延迟，提高目的节点的吞吐率，减少数据包从源节点到目的节点所经过的跳数等。优化目标可以是单个目标，也可以是多个目标的组合。优化目标的对象可以是整个网络，也可以是每个节点，对于后者的情况，节点之间的关系可以进一步分为竞争关系与合作关系。

分布式调度策略包括：控制节点处于活动状态还是休息状态；控制节点发送队列中不同数据包的发送顺序；控制不同数据包的发送时刻；为节点分配不同的发射功率；控制节点的位置等。节点在做决策时，可以仅考虑某个因素也可以同时考虑多个因素。分布式调度策略可以执行在某个协议层上，如MAC层或路由层，也可以通过多层协议之间共同协作最大限度地提高待优化目标。分布式调度算法的优劣，在于其是否能够达到待优化目标的最优值及对网络环境变化适应能力的强弱。

2. 主要目标[23]

当前，无线传感网分布式调度方法的主要目标是：

（1）提高节点能量效率，延长节点和网络的生存期。

（2）提高覆盖度。覆盖度是指在网络监控范围内，某一区域或某一位置能被多少个节点有效感知，提高覆盖度可以提高监控的可靠性和精确度。

（3）降低网络延迟，更好地实现实时监控和多媒体应用。网络延迟指数据包从源节点发出后被汇聚节点（Sink节点）接收所经历的时间。

（4）提高吞吐率。吞吐率是指Sink节点的数据接收率，反映网络带宽的利用状况，信号冲突和节点休眠会降低吞吐率。

（5）连通性，保证发送的数据能被Sink节点接收。节点能通过多跳通信将数据发送到Sink节点时，称该节点是连通的。

3. 调度方法分类[20]

1）节点调度

节点调度是在完成监控任务的前提下，通过减少处于工作状态的节点数量，达到节省节点能量和延长网络生存期的一类调度方法。该类方法一般将节点的状态划分为活动和休息两种。节点在活动时，完成感知、通信和处理等任务；在休息时，会处于某种程度的休眠状态。节点调度的前提是在降低节点能量消耗的同时，不降低系统的覆盖度要求。

2）包调度

传统网络中的包调度一般指路由器对所存储数据包的发送顺序进行调整。在无线通信中，包调度的主要目的是不同数据流分配信道带宽和最大化的信道带宽。包调度也是无线传感网节点级拥塞控制方法，可以解决不同数据流的带宽分配问题。

3）传输调度

传输调度是一种传输控制机制，通过对数据包发送时刻进行分配、平滑网络数据流量、降低数据包冲突概率来达到减少传输时延或节省节点能量的目的，该类方法可在网络协议的多个层中开展。当传输调度不与媒介访问结合时，通常采用基于统计的方法对节点的传输时机进行控制。

4）功率调度

功率调度通过减小节点的发射功率，减少数据包冲突的发生，来减少传输时延和由冲突引起的能量损耗，同时延长网络生存期。该类方法还可以提高同时发送数据的节点数量，提高网络带宽。但是，功率调度后，可能会造成更多的隐藏终端，引起网络拓扑变化，因此需要对数据冲突进行深入分析，同时要考虑如何保证网络的连通性。

5）MAC调度

MAC调度将信道访问控制与调度相结合，在为上层协议提供数据链路的同时，优化节点性能。根据物理信道竞争方式的不同，MAC调度可以分为无竞争（Content-Free Based）信道的MAC调度方法、基于竞争（Content Based）的MAC调度方法和混合策略的MAC调度方法三类。

无竞争信道的调度方法通过采用TDMA、CDMA或FDMA技术为节点分配不同的时槽、正交编码或工作频率，以减少信号冲突的产生。基于竞争的MAC协议广泛采用了各种调度机制来减少数据包的冲突，通过减少占空比来减小能量消耗、提高网络生存期。混合策略的MAC调度方法吸取竞争模型和无竞争模型调度方法的优点，虽然也是一种TDMA方法，但是考虑了物理层冲突，可以根据节点的工作负荷动态调整发送时占用的时槽。