物联网分布式调度

　　分布式调度问题是物联网中的难点。由于物联网采用的是无线传输信道，传输媒介是电磁波，因此很容易受天气和地理环境的干扰。同时，以无线信道传输数据还会因为传输距离太远而产生信号衰减和信号失真，这些特性决定了物联网分布式调度的复杂性。

　　传输信号时，电磁波会逐渐衰减，衰减的原因有两个：一是传输距离导致的衰减；二是信号频率导致的衰减。电磁波传输衰减损耗计算公式为：


　　其中，表示信号频率，单位是MHz，d表示传输距离，单位是km。传播信号的损耗随着传输距离的增加而逐渐变大，在密度不同的介质中进行信息传播，传播信号衰减更大，每次穿过撞墙，信号强度便会缩减10%左右，信号传播速度会降至原来的60%～70%。

　　信号通过无线传输时，也会受到绕射、散射以及反射的影响而导致信号接收差的情况。绕射就是传播信号在无线传输时，如果遇到尖锐的边缘阻挡，就会自动饶过障碍物继续传播的现象；散射是指信号传输时碰到大量比信号波小的障碍物，就会自动射散的现象；而反射现象指的是信号在传输过程中，遇到比信号波长的障碍物会进行反射。

　　除了上述原因之外，不同的无线信号还会互相干扰，这也是导致信号损耗的另一个原因。而在理想传播路径中，传播的损耗公式可表示为：


　　该公式中，hs表示发射端的电线高度，hr表示接收端的电线高度。一般来说，这两种电线高度与信号的耗损也有关系，在一定范围内，电线越高，信号耗损越小，当电线高度是平时的一倍时，能够减少信号耗损6dB。现阶段，由于传输数据的量越来越大，基于无线传输的调度算法开始无法满足当前需要，越来越多的大规模无线传输网络开始使用分布式调度算法，因此，分布式算法的设计受到很多通信企业的重视。

　　（1）图算法调度技术

　　网络连接关系可以用一个有向或无向图来表示，这样就能以建立图像模型的方式来解决MAC层的调度问题。如下图所示：

　　该图形模型主要由一个边长为10cm的正方形构成，假设正方形的每一个顶点都表示一个节点，则该模型中存在四个节点，即图中所示的①②③④。在线路对称的情况下，设每一个节点的传输距离都为12m。然后，再建立信号干扰模型，如下图：

　　既表示了链路的连接关系，又表示了形成的链路冲撞关系。

　　上图是一个调度方案，按照寻找最大独立集的方式，可得{{1'，3'}，{1”，3”}，{2'，4'}，{2”，4”}}。

　　通过调度节点和1-跳干扰模型，得出的合理调度方案之一为{{1，3}，{2，4}}。在特定情况下，调度问题可以转化为其他种类的问题。例如，如果将节点作为调度对象，模型是1-跳干扰模型的情况下，调度问题就可转化成两种问题，第一是图的最大化集成问题，第二是图的点染色问题，而如果将链路作为相应的调度对象，也可将调度问题转化为两种问题，一是图的匹配问题，二是图的边染色问题。图的点染色和边染色问题分别对应NP问题和NPC问题。调度算法的性能指标有多种，其中，算法的计算复杂度是比较重要的一个。

　　（2）极大独立集算法分析

　　极大独立集问题属于NPC问题，研究该问题可以实现分布式调度算法。以下是Schneider算法的状态转化图：

　　平衡节点；②competitor表示竞争节点；③ruled表示平衡节点的邻居节点；④dominator表示加入MIS的节点；⑤dominated表示dominator的邻居节点。

　　在算法的运算过程中，开始时，节点都处于competitor状态；结束时，存在两种情况：非极大集中的节点处于dominated状态，极大集中的节点则处于dominator状态。

　　网络中的节点会在不同的状态进行不同的工作，当节点处于competitor状态时，会与r值进行相关比较，然后才自动更新；当节点处于ruler状态，节点地址发生转移，重新进入competitor状态。最终的结果是所有节点的最终状态不是处于dominator状态，就是处于dominated状态。

　　算法执行时，整个过程分成三个层级，第一层级由若干个stage组成，第二层级由每个stage下包含的若干个phase组成，第三层级的每个phase由几个domination组成。在domination阶段，竞争节点会与相邻节点比较r值，之后进行自我更新。若一个phase阶段中对应的所有domination阶段结束，则该phase阶段结束；若每个sage对应的所有phae阶段结束，则该stage阶段结束；当所有的stage阶段结束时，在MIS中的节点会处于dominator状态，不在MIS中的节点会处于dominated状态，最后，算法结束。