论文部分内容阅读
无线传感器网络的出现使人们可以利用微小的传感器节点监测复杂的物理世界。因此,无线传感器网络被广泛应用于各个领域,如军事监测、环境监测、交通监测、以及结构健康监测等等,为人类的生活带来便利。调度问题是无线传感器网络的基础问题之一,包括通信调度问题和计算调度问题。调度问题研究网络中信道资源和计算资源的分配,直接影响了网络的性能。传统的无线传感器网络由配备电池能源的传感器节点组成,该节点称作有源传感器节点,因此,传统的无线传感器网络也称作有源传感器网络。传统的有源传感器网络的一个最大限制就是生命周期受限。在大多数应用中,由于监测环境恶劣或者监测范围巨大,人工为能量耗尽的有源传感器节点替换电池是困难的甚至是不可能的。此外,电池泄漏现象会引发环境污染问题。因此,一种新型无源传感器节点应运而生。无源传感器节点自身不配备电池等能源设备,而是通过能量获取技术,从周围环境中的能量源获取能量,如太阳能、风能、射频信号,等等。并且,无源传感器节点通过配备电容器实现能量的存储和释放。由无源传感器节点组成的网络称作无源传感器网络。由于周围环境中的能量源是不稳定的且不可控的,无源传感器网络具有能量供应不稳定且不可控的特点。这些能量特点使得无源传感器网络的调度问题更具挑战性,现有的为有源传感器网络设计的调度算法将不再适用。因此,本文研究了无源传感器网络的调度算法,主要研究成果如下。首先,本文研究了无源传感器网络的广播调度问题。数据的广播是无线传感器网络的基础操作之一,旨在将一个源节点的数据包传输至网络中所有其他节点。由于时效性是衡量无线传感器网络性能的重要标准之一,最小化时间延迟的广播调度问题受到广泛关注。在无源传感器网络中,无源传感器节点从周围环境中不稳定且不可控的能量源获取能量,导致其能量获取速率可能小于其能量消耗速率,使得无源传感器节点由于能量供应不足,无法时刻处于工作状态。因此,本文研究了为无源传感器网络生成可行的、通信无干扰的、且具有最小时间延迟的广播调度算法。本文首先证明了无源传感器网络的最小化时间延迟的广播调度问题是NP难的。应用能量预测技术,预测无源传感器节点的能量状态。根据预测的能量状态,提出了三个适用于不同能量获取环境的近似最小化时间延迟的广播调度算法。本文在理论上证明了所提出算法的正确性和近似比,分析了算法的时间复杂度,并通过大量实验验证了算法在降低广播时间延迟方面的性能。其次,本文研究了无源传感器网络的数据收集调度问题。无线传感器网络的一个重要功能是将分布在监测区域内的传感器节点采集的感知数据收集到汇聚节点,进行进一步的计算和处理。数据收集包括两种类型:一种是无融合的数据收集,一种是有融合的数据收集。本文首先研究了无融合的数据收集调度。无融合的数据收集是指在传输的过程中,不对传感器节点采集的感知数据进行任何网内计算,而是直接将原始感知数据收集至汇聚节点。无融合的数据收集适用于所有感知数据同等重要,或者感知数据之间的时空相关性不大的情况。本文结合无源传感器网络的能量特点,研究了为无源传感器网络生成可行的、通信无干扰的、且降低时间延迟的数据收集调度算法。根据干扰模型将网络划分为子区域,利用能量预测技术预测无源传感器节点的能量状态,并利用信息交换技术在邻居节点间传输包含能量状态和调度策略的信标信息,分布式地为网络生成降低时间延迟的数据收集调度。分别考虑了线型无源传感器网络和一般无源传感器网络,并为每种网络提出了一个具有时间延迟上界的数据收集调度算法。本文分析了所提出算法的时间复杂度,证明了算法生成的数据收集调度的时间延迟上界,并通过大量实验验证了所提出的算法可以有效降低无源传感器网络的数据收集时间延迟。第三,本文研究了无源传感器网络的数据聚集调度问题。数据聚集是一种有融合的数据收集,在感知数据传输的过程中,中继节点可以通过网内计算将接收到的数据进行融合,将数据融合的结果继续向汇聚节点传输,网内计算中常用的聚集函数有求最大值、求平均值、求和等等。数据聚集适用于感知数据之间的时空相关性很强,或者汇聚节点只需要获取网络中感知数据的某一聚集函数值的情况。本文研究了无源传感器网络的最小化时间延迟的数据聚集调度问题。本文首先证明了该问题是NP难的。结合无源传感器网络的能量特点,研究了为无源传感器生成可行的、通信无干扰的、且降低时间延迟的数据聚集调度算法。利用能量预测技术预测无源传感器节点的能量获取速率。基于预测的能量获取速率,首先为无源传感器网络构建能量获取速率-工作量平衡的数据聚集树。然后,根据干扰模型为数据聚集树上的无源传感器节点分配传输时间,提出了一个具有时间延迟上界的数据聚集调度算法。本文分析了该算法的时间复杂度,证明了算法的正确性以及算法生成的数据聚集调度的时间延迟上界,并通过大量实验验证了在无源传感器网络中,所提出的算法可以显著降低数据聚集的时间延迟。最后,本文研究了具有边缘计算能力的无源传感器网络的计算调度问题。在具有边缘计算能力的无源传感器网络中,计算能力有限的传感器节点可以通过无线通信,将计算任务上传到位于网络边缘的、具有较高计算能力的边缘设备上,如基站、接入点等,提高网络的计算能力。同时,边缘设备通过发射射频信号为无源传感器节点供能,无源传感器节点将接收到的射频信号转化为电能,供其传输和计算。网络中传感器节点完成的任务计算量是衡量具有边缘计算能力的无线传感器网络性能的重要标准之一,因此,最大化网络计算完成率的计算调度问题受到广泛关注。计算完成率定义为在一个具有边缘计算能力的无源传感器网络中,所有传感器节点完成的任务计算量与总需求的任务计算量的比值。在半双工传输模式下,边缘设备向传感器节点发射射频信号以及传感器节点向边缘设备上传计算任务无法同时进行,如何合理分配网络中的信道资源以提高网络性能是首先需要考虑的问题。当具有边缘计算能力的无源传感器网络包含多个边缘设备时,由于每个传感器节点向不同边缘设备上传计算任务消耗的时间和能量是不同的,如何合理分配网络中的计算资源以提高网络性能是第二个需要考虑的问题。因此,本文研究了为具有边缘计算能力的无源传感器网络生成具有最大计算完成率的计算调度算法。本文证明了在具有边缘计算能力的无源传感器网络中,最大计算完成率的计算调度问题是NP难的。首先,为传感器节点构建一个能量获取时间分配的候选集。对于每一个候选能量获取时间,解构问题的最优解,求解部分问题的最优解,并将剩余问题转化为广义指派问题求解,提出了近似最大化计算完成率的计算调度算法。本文在理论上证明了所提出算法的近似比,分析了算法的时间复杂度,并通过大量实验验证了在具有边缘计算能力的无源传感器网络中,所提出的算法可以显著提高网络的计算完成率。