延迟约束与节能数据融合技术分析

虽然LMST的目标是通过选择最短边来构建一个节能结构，但在延迟方面不是最优的。在参考文献（Xu et al.，2009）中，作者们提出了一种数据融合协议。该协议首先采用了LMST，然后在报告时间方面进行了改进，以符合附加的延迟约束条件。与大多数现有延迟约束数据融合方案相比，该文献所采用的用于逼近通信延迟的指标是跳数。实际上，在每个数据包每跳经历的延迟中，与节点处理数据包所需的时间相比，空中传输距离可以忽略不计。当所有数据包长度相同时，延迟可以认为是相等的。因此，数据包经历的延迟与其传输跳数直接成正比。提出的算法称为理想跳进度（Desired Hop Progress，DHP），它满足给定延迟约束条件，但能耗却比参考文献（Melodia et al.，2005）中的已知竞争方案大大降低（能耗减少了25%～75%，网络生存周期为竞争方案的123%，这取决于网络配置）。现在，我们来详细描述该算法。

与先前的算法（L-PEDAP）一样，当某个执行器（可能存在多个）使用一条请求消息来洪泛网络时，树是建立在LMST边上的。由于采用了特殊的重传方案，因而每个节点在洪泛过程中，计算并记忆若干个参数，其中的一个主要参数是到汇聚节点的跳距。实际上记忆了两种距离：基于最小生成树的局部距离（LD），它代表仅使用LMST边时，到执行器的跳数；基于单位圆盘图的距离（UD），它是采用任意边时，到执行器的跳数。这些不同的距离如图7-4所示。图中粗边代表基于LMST的树，所有边一起构成UDG。然后，融合过程从树叶开始，到执行器结束，正如下面我们要介绍的。

每条请求（洪泛的数据包）包含融合过程中必须满足的延迟约束条件。如果仅使用LMST边即可满足延迟约束条件（即如果对于任意节点来说，LD等于或小于预计延迟），则融合过程与采用L-PEDAP算法类似，仅使用这些边。否则，报告节点试图使用UDG距离，来寻找LMST外面的捷径。更准确地说，在向其父节点发送融合数据包之前，每个节点计算一个特殊比值，来确定仅使用LMST边是否已经足够或者需要寻找一条捷径。我们将这个比值称为dhp，它可以定义为：

图7-4 DHP协议拓扑实例(www.xing528.com)

其中MED（Most Experienced Delay，最大经历延迟）表示子节点已经完成的跳数。实际上，这个比值的含义是代表应当在每个下一跳处获取的LD距离，从而延迟约束条件能够最终得到满足。如果该比值大于1，则它确定应当采用何种级别的捷径更为理想。考虑到图7-4中给出的场景，当延迟约束条件为3时，会执行如下结果。

由于节点8有一个等于延迟要求的UD，它无法接受任何子节点（因为无论哪条捷径都无法满足延迟约束条件）。因此，融合过程也不会考虑节点9。因为节点3和节点6的dhp值都为，它们试图使用一条捷径来获取两个LMST跳，因而选择节点2作为父节点。节点4、5、8计算其dhp值（也等于2），因而选择节点1（与节点2建立捷径）作为父节点。然后，节点2计算其dhp值（也等于2），于是选择节点7作为父节点。同样，节点1选择节点0作为父节点。反过来，节点7发现其报告必须直接发送给执行器，因为仅允许进行最后一跳（Delay-MED=1）。最后，节点0自然确定执行器作为其父节点。在这个实例中，几乎没有使用LMST边，该协议的关键是通常当延迟约束条件允许时使用这种边，它会在满足延迟约束条件的同时，节省融合功耗开销。

该论文还提出了DHP协议的两种变形（DHPA和DHPAC），它们分别将DHP协议与传感器任务调度和连通支配集（CDS）整合起来。关于CDS的详细讨论参见第1章。两种变形需要更少的传感器报告数据，因而降低了带宽使用，提高了能量效率。第一种变形DHPA，在选择主动节点集时采用了局部区域覆盖算法（Gal-lais et al.，2006）。主动节点监测环境，生成报告，而其他节点转入休眠模式，以节省能量。因此，DHP协议仅在主动节点上运行。在这种区域覆盖算法中，每个节点设置一个超时t，来启动覆盖评估和调度其任务。考虑到具有较短超时t的节点处于激活状态的较高，它们定义t=c/E_rest（c是一个常数，E_rest是剩余节点能量）。该定义优先选择那些剩余能量较高的节点。也就是说，节点的剩余能量越多，节点工作的概率越大。第二种变形DHPAC是DHPA和参考文献（Carle and Simplot-Ryl，2004）提出的局部CDS算法的组合。在这种组合中，CDS算法运行在由区域覆盖算法所确定的主动节点上。由于每个主动节点要么属于CDS，要么在CDS中有一个直接邻居，非CDS节点将直接将报告发送给最近的CDS邻居，而CDS节点将运行DHP协议来组织CDS内的数据融合。