论文摘要
随着微电子技术、计算技术以及无线通信技术的进步,低功耗多功能的传感器得到了快速的发展,而且无线传感器网络已经被广泛地应用。数据聚集是无线传感器网络应用中一项重要的操作。本文主要研究传感器网络上的数据聚集调度问题。本文基于极大独立集提出了一种分布式聚集调度算法,为无线传感器网络中的数据聚集产生一个无冲突的调度。该分布式数据聚集调度算法可以分为两个阶段。第一个阶段是分布式聚集树构造算法,第二个阶段是分布式调度生成算法。我们在本文中详细地介绍了该聚集调度算法的细节实现,该算法通过贪心的方法对生成调度的时间延迟进行了优化。据我们所知,本文是第一篇分布式聚集调度算法。接下来我们给出了算法的理论分析。首先我们给出算法生成的调度的时间延迟上界为12 D+ 6Δ+ 16,其中D是网络的直径,Δ是网络图中的最大顶点度。在此之前具有最小时间延迟的数据聚集算法的时间延迟上界为（Δ- 1）R,其中R是网络的半径。然后我们以一个定理的形式给出了算法的通信复杂度和时间复杂度。我们还做了全面的模拟实验来考察该调度算法的性能。理论分析和实验结果均表明本文提出的调度算法优于先前的其他聚集调度算法。本文还提出了在传感器网络中有节点加入或失效的情况下的一种自适应的调度策略。和前面提出的调度算法类似,该自适应调度策略也分为两个阶段。第一阶段是自适应聚集树的维护算法,第二阶段为自适应的调度维护算法。我们对此策略进行了一定的理论分析和模拟实验,从中可以看到,该自适应调度算法能够以很少的通信开销有效地维护网络的调度。