传感器网络中数据聚集最小延迟算法的研究

摘要

近年来,无线传感器网络引起了世界各国军事部门、工业界和学术界的极大关注。数据聚集是传感器网络中一个比较耗时的操作,特别是在高密度网络中。例如,在一个森林火灾监控系统中,需要把监测到的数据及时地进行数据聚集,以便发现异常,避免火灾迟报。因此,最小化数据聚集延迟问题(MDAL,Minimum DataAggregation Latency)成为一个重要的研究课题,该问题已被证明是NP难问题。
　　 本文首先提出了最小化数据聚集延迟调度的集中式算法(MERG)。该算法是基于联通支配集(Connected Dominating Set,CDS)结构的一种改进算法,理论分析得出延迟上限为15R+Δ-15,这里△为网络中的节点最大度数,R为网络半径。
　　 然后,根据传感器节点可多信道通信、功率可调等特点,首次提出一个基于分簇思想的多信道多功率相结合的数据聚集调度算法(MPMC),来降低通信延迟。该算法采用一种簇内小功率、簇间大功率的分簇思想,结合信道分配来降低通信延迟；通过信道分配算法和功率控制策略,簇间可无冲突同步进行通信,从而大大降低了数据聚集延迟；并分析了不同网络拓扑下使用的信道个数小于43,在传感器节点可用通信信道数范围内。
　　 最后,由于网络拓扑结构变化时集中式算法需重新收集网络中节点信息,重建拓扑结构,导致能量消耗过大、计算周期长等问题。本文提出一种分布式的多信道分配及多功率控制相结合的数据聚集调度算法(DMPMC),来降低聚集延迟。该算法以MPMC算法为基础,提出了网络自主建簇算法、分布式信道分配算法、分布式计算簇内数据聚集调度,然后将簇头节点信息汇集到sink节点,由sink节点计算簇间的数据聚集调度。理论分析得出DMPMC算法数据聚集延迟上限为R+O(log(R)+Δ,是目前延迟上限最小的算法。
　　 实验结果表明,MPMC算法和DMPMC与目前最好的单信道算法相比,平均延迟降低了70％；与目前最好的多信道算法,平均延迟降低了25％。