WSN数据融合调度算法研究最新进展

在无线传感器网络数据融合中首先需要解决数据传输的调度问题，评价一个调度策略优劣的关键要看其QoS性能。因此，应该首先明确在数据融合过程中涉及的关键QoS性能指标。现有文献中提出了使用四个集合性指标，即共同时延、共同丢包率、共同带宽及信息吞吐量，来度量无线传感器网络的QoS指标。虽然其体现了以数据为中心的特点，但并没有给出每个指标的确切定义。一些研究也分析了无线传感器网络支持QoS存在的难点问题，介绍了路由和MAC协议支持QoS的现状，但是也没有明确给出无线传感器网络QoS的度量指标。有学者从用户的角度提出四个QoS指标来描述无线传感器网络的性能，它们分别是节点密度、数据在空间/时间上的准确性/真实性、事件从产生到递交至汇聚节点的时延、网络的生命周期。从网络体系结构的角度看，数据融合是一种介于应用层和网络层之间的技术。因此，研究趋势为从应用层和网络层QoS度量指标的研究中，提出数据融合的QoS度量指标。

（一）基于能量和生命周期的数据融合调度算法

能量损耗问题是无线传感器网络研究的关键性问题，如何能使无线传感器网络运行能量最小同时使网络生命期最大是一项具有挑战性的研究工作。在研究数据融合节省能耗的问题时，很多研究者利用图论和最优化的相关知识开展研究。Kalpakis等人利用线性规划方法来研究数据融合问题。其假设已知传感器网络的所有节点的位置和能量供给，以及任意两个节点之间进行通信的代价。在网络循环工作中，每次循环中节点产生一个单位大小的数据分组，融合节点能将自身的分组和接收到的分组融合成相同大小的分组，MDLA问题就成为在传感器能量约束和边容量约束下，利用整数规划计算最优的容许流量网络问题，并给出了一种构造融合树的启发式方法。但具有线性松弛的整数规划方法有相当大的计算开销，为此提出一种开销小的启发式基于簇的最大生命周期算法。

能量高效的数据融合通常与路由技术结合，此时可以把网络看成是一个图，给每个连接赋予一个能反映经过这个连接所消耗的能量代价，然后选择一个算法，计算图中的最小代价路径。现有文献中提出了联合优化数据融合和路由的策略，给出达到最大网络生命期的最优化表达式，并利用分布式梯度算法达到最优解。现有文献中提出一种新颖的数据融合和路由策略，使用启发式方法在路由过程中，寻找最少数量的融合节点，以达到网络生命期的最大化。融合节点可能同时接收多个源节点的数据，造成MAC层的冲突和重传，增加了融合节点能量的消耗和延时，现有文献中提出将数据融合技术和路由技术结合，分析能量消耗在MAC层重传和数据融合路由之间的折中，给出了能量消耗一般方程式，并使用拉格朗日松弛算法得到最优解。

研究者还试图通过建立低能耗融合树和簇的方法实现数据融合。基于簇的研究的主要内容是簇的形成机制和簇头融合节点的动态选择机制。目前，一种基于簇的自适应数据融合方法ADA，能够实现时间和空间的自适应融合。为了防止簇头节点的失效，导致可靠性的降低，由此提出EERINA协议，在簇内首先使用Gossip算法充分利用无线信道的广播特性，减少数据的传输，并在融合的最后阶段选出簇头。随后，对EERINA协议进行改进使之能够适用于部分连接的网络。

基于树的数据融合算法研究的共同点是通过不同的方法建立、维护能量有效的数据融合树。研究者利用多种方法构建数据融合树。也有学者提出EADAT，基于剩余电量的算法，主要思想是分布和启发式地建立和维护一棵融合树，动态调整所有叶节点的无线通信来减少能源消耗，达到延长网络生命期的目的。E-Span和LPT算法都根据节点的剩余能量，来确定融合树中的父与子节点，以提高网络的生存期。在E-Span中，剩余能量最高的源节点被选定为根节点，其他节点根据其自身剩余能量及与根节点的距离来选择相应的父节点。应用于目标跟踪场合的传送树的概念（DCTC），是将移动目标附近的节点组成的动态树型结构，并且随着目标的移动动态地添加或者删除一些节点。移动目标附近的节点通过传送树结构进行协作跟踪，在保证对目标进行高效跟踪的同时减少节点间的通信开销。

刘炳宏等人提出在移动目标追踪中，使用带有捷径的信息生成树，实现目标位置更新及查询成本的最小化。有学者提出采用定向传输方式，在消息路由机制基础上提出了一种基于估计代价的数据聚合树生成算法。该算法主要思想在于将节点能耗、传输距离与聚合收益三方面作为估计代价，优化聚合路径，实现数据聚合在能量与时延上的折中。现有文献中提出一种蚂蚁群居算法DAACA实现数据融合，通过信息素积累方法构建最佳融合树。通过测量节点不同状态下的能量消耗制定出了较为优化的睡眠调度算法，使得节点能够获取合理的融合调度，以降低整个融合汇聚过程的能量消耗。针对基于事件驱动的无线传感器网络数据聚集场景，将混合压缩感知的数据收集技术与数据收集树的构建过程相结合，以收集查询后节点最小剩余能量最大化为目标构造最大数据收集树集合，达到能够充分利用节点能量资源、显著提高网络能量效率的目标。

（二）基于时延的数据融合调度算法

无线传感器网络中，数据并不是同时到达融合节点，融合节点必须延迟一段时间来等待传感器节点数据的到来，为了能够使网内数据融合更有效，此时有三类问题需要解决。第一类是最小融合时间的计算问题。Chen等人提出最小数据融合时间问题（MDAT），即寻找最短时间内实现将融合数据传输到基站的策略，证明此问题为NP-hard问题，并设计（∆-1）近似算法解决MDAT问题，得出延时的界限为（∆-1）R，∆为融合树的最大度数，R为网络半径，两个参数随网络规模的增大而增大。延时与两个参数的乘积有关，当网络规模较大时具有相当高的延时。通过对基于最大独立集算法的设计，得到延时界限为23R+∆-18个时隙，其中∆为加性因子，使算法的延时近似于常量。以上算法以基站为计算与调度中心，该方法能耗高，并不是无冲突的。针对以上问题，提出分布式近似算法，延时界限为24D+6∆+16（D为网络直径）。

第二类问题是如何将最大融合延迟合理地分配到各个融合节点上，并能使信息融合达到最佳的效果。Xu等人则提出了一种性能更优的IAS算法，该算法基于网络最小连通支配集，通过调整被支配节点的传输目标以减少冲突，最终实现最大数量被支配节点同时进行传输。通过设计一种算法将某种应用所允许的最大延迟时间有效地分配到各个融合节点上，但实现时间分配的算法复杂度高，如何找到最优的融合延迟分配算法仍需进一步研究。

第三类是为融合更多的数据，等待时间的确定问题。定时策略在传感器节点需要周期性地向汇聚节点报告监测数据的应用中尤为重要，与三种数据融合模型进行比较，它们分别是周期性简单数据融合模型、周期性逐跳数据融合模型及周期性逐跳调整数据融合时机模型。研究表明根据节点在融合树中的位置来设置时序可以得到较理想的效果，并能维持较高的准确度和新鲜度。同时针对汇聚传输中数据传输的方向特征，提出了“瀑布超时”机制，即数据源节点首先超时并传输数据，然后下一跳节点超时，将接收到的数据与本地产生的数据进行融合并转发，直至汇聚节点。现有文献中提出一种基于多叶节点生成树的低延时数据融合调度方法。研究实时应用场景下最小延时数据融合调度问题。首先给出了最小延时数据融合调度问题的形式化描述，通过构建数据融合树，并设计相应的调度策略近似解决该问题。依据多叶节点融合树有利于增加同时传输的节点数量的思想，提出了一种多叶节点生成树构建算法，在融合树基础上设计一种最大干扰优先调度机制，实现最小延时数据融合调度。

（三）基于数据质量的数据融合调度算法(www.xing528.com)

数据质量是指汇聚节点接收到的采集数据的准确性，完整性和精确性。数据质量受传感器节点采集数据的精度、时间及位置信息，数据传输中的差错率以及分组丢失率和数据融合中损失的信息等因素的影响。

在满足能量和延时限定的条件下，汇聚节点采集最大数量的信息是提高数据质量的有效方法。现有文献对能量受限传感器网络最优信息抽取问题进行了深入研究。根据加性白噪声信道下的Shannon容量方程和信号衰减，把最优信息抽取问题形式化为一个满足能量约束条件的非线性流量规划问题。通过设置节点的传输功率和流量速率，限制节点发送信息量，从而最优化汇聚节点接收的信息量。目前，部分文献研究了将能量受限的混杂传感器网络最大数据提取问题，将其建模成多物网络流问题，并给出近似算法。

融合在降低数据冗余的同时也给信息完整性和准确性带来隐患，为此需要开展数据融合的鲁棒性研究。有学者提出了事件簇的数据聚集容错机制EFSA。在生成事件簇的基础上，采用k-means算法提取加权平均数作为近似的事件值，并且计算和迭代地调整节点的可信度，作为聚集计算的数据权值和节点是否出现数据错误的指标。现有文献指出多路径数据融合容易引起对传感器监测数据的重复统计，为此将线性计数策略应用到多路径技术中。根据用户对数据质量的要求提供融合也是一个重要的研究方向。现有文献给出一种解决传感器网络中近似top-k查询的处理算法。

该算法根据用户对top-k查询的精度要求，在网络中构造一棵树。该树保证各个节点向汇聚节点返回满足用户精度要求的top-k查询结果，并使返回结果的通信代价最小。Yu等人研究了本地融合算法，确保数据融合得到的信息满足一定的准确度。若信息准确度不能满足预定要求，则传输较多的原始信息来弥补；若准确度在要求的范围内，则尽量在本地对数据进行处理以降低能耗。目前，一些文献对一种能量高效的保障数据精度的数据融合算法进行研究。该算法提出由于节点间无线链路的不可靠性，节点间30%的传输数据会丢弃，多路径是解决该问题的有效方法，但是多路径又会引起融合运算时的重复计算，从而影响数据精度。

（四）复合约束条件下的融合调度算法

数据融合的QoS保证经常需要综合考虑多个方面的性能指标，即实现在融合时延、网络能耗开销、数据融合精确度以及节点公平性保证等多个指标间的联合优化。

目前，部分文献集中研究了周期性融合过程中，能量消耗与融合结果精确度的平衡问题。为了实现延长传感器网络的生命周期，将数据融合结果的精确度与节点的能量消耗进行折中处理。其主要的实现方法是首先对网络中所有节点的状态进行监测，获取节点感知数据的变化模式、节点的能量消耗情况、节点到基站数据汇聚的通信开销等，然后根据监测结果将用户对融合结果的精确度做宏观的总体限定，并将这一限定分配到各个终端节点。此时，节点只有在限定的条件下（为了满足所分配的融合精度等级）才需要发起数据传输，而不是将所有采集到的数据全部上传，在保证融合精度的前提下尽可能地减少了数据的传输量。其他相关文献采用了类似的方法，该方案中通过设置一个用于调控融合精确度和网络能耗平衡的门限参数，通过该参数在两个性能指标之间实现全局下的平衡。

在数据融合过程中，融合能耗和时延的平衡是研究的另一个难点。为了尽可能降低融合过程的能耗，融合节点需要融合尽可能多的数据以减少通信量，但这必然会导致融合节点等待的时间过长，即融合的时延增加。YE等人提出了一种借助于半马尔科夫决策过程进行性能优化的模型，该模型将延时作为融合回报的折扣，根据采样值到达和接入信道的可用情况，此时节点可以建立优化方程用以对两个性能进行平衡处理，其处理结果是确定继续等待融合更多数据还是立即发送现有的融合结果。分布式的能量有效的最小延时数据融合算法DEDA（Delay-minimzed Energy-efficient Data Aggregation algorithm）是另一种兼顾融合时延和能耗的折中算法。该算法的主要思想是通过构建延时有效的网络结构，最小化数据融合延时，同时考虑网络节点之间的距离以节省传感器节点的传输功率和网络能量。

当前针对融合延时和能耗折中的研究主要集中在协议干扰模型下，然而对于能够更加精确地反映无线干扰特征的物理干扰模型下的延时和能耗的折中研究则鲜有开展。由于连续干扰消除技术的应用，接收器能够从多个发射器同时发射的信号中恢复所需信号，该模型能够减少延时，但是会造成能耗的增加。该文献提出使用连续干扰消除技术研究物理干扰模型下数据融合的延时和能耗的折中问题。

目前，一些文献针对数据融合中的通信延时、能量消耗和数据精度折中问题进行了深入分析。首先使用马尔科夫链分析部分数据融合问题，分析结果显示无融合的数据收集造成较大的能耗，而完全融合引起较大的传输延时。作者提出一种部分融合算法WRP（Waterfalls Random Partial aggregation）实现能耗和延时的折中，同时引入折中索引TOI（Trade Offs Index）的概念实现对延时、能耗和数据精度重要性的控制。