论文部分内容阅读
无线传感器网络是帮助人们认知、探索物理世界的重要工具,也帮助人们打破了信息世界与物理世界之间的壁垒。然而,由于传感器节点的供电单元一般为电池,使得传感器网络的网络寿命受限。同时,废弃的传感器节点中的电池也会对环境造成不可逆的污染。这两点严重阻碍了传感器网络的进一步发展。为了解决这个问题,研究者提出了无源传感器网络。无源传感器网络是由无源传感器组成的网络。无源传感器节点自身不携带电源,但可以从周围环境能源（太阳能、风能、射频能量等）中获取能量。由于这些能量源具有绿色环保,能量供给持久的特点,使得无源传感器网络具有环境友好,寿命无限的特点。本文主要研究无源传感器网络中的覆盖问题。网络覆盖是传感器网络中保障网络连通、感知数据完整、网络功能完善的重要指标。但由于周围环境能源具有供给持久、分布失衡、变化难测等特点,使得无源传感器网络中的覆盖问题更为复杂。本文针对不同类型的无源传感器网络中的覆盖问题进行了深入研究,主要研究成果如下:第一,本文研究了基于绿色能源的无源传感网的覆盖问题。在这种网络中,无源传感器节点通过环境中的绿色能源——太阳能、风能等获能。由于绿色能源具有分布失衡、能量波动等特点,导致无源节点的工作状态不稳定,网络的全覆盖很难保证。这使得,传统传感器网络中对网络覆盖的度量标准无法应用。另一方面,由于绿色能源的能量供给是持久的,使得网络不存在生命受限的问题,这也使得传感器网络中现存的以网络生命周期为优化目标的算法无法应用。为了应对以上两个挑战,本文首先重新定义了网络覆盖的度量,将网络覆盖质量定义为对监控区域的平均覆盖率。其次,本文以网络覆盖质量为优化目标,定义了覆盖质量最大化问题,并证明了该问题是NP-难的,给出了该问题解的代价的上界。同时,本文也给出了该问题具有多项式时间最优解的充分条件。当该条件不满足时,本文提出了两个集中式近似算法和一个分布式近似算法对该问题进行求解,并从理论与实验两个角度对所提的三种算法的有效性进行了分析验证。第二,本文研究了绿色能源分布敏感的无源传感网的覆盖问题。在这一问题中,本文主要研究如何通过部署传感网节点的地理位置和工作状态来适应绿色能源分布,最大化网络覆盖质量。通过节点地理位置的部署可以适应绿色能源在空间上的分布,而节点工作状态的调度则可以适应绿色能源在时间上的分布。然而,节点的能量获取状态与节点的工作状态相互影响,这使得如何合理地部署、调度无源节点,并最大化网络覆盖质量成为了一个复杂的问题。本文将节点的地理位置部署和工作状态调度合称为节点的联合部署,而本问题的目的就是通过网络的联合部署最大化网络的覆盖质量。本文证明了该问题为NP-难问题,同时也给出了该问题解的代价的上界。为了解决该问题,本文提出了一个基于放缩策略的近似算法。本文证明了该问题的近似比,也通过实验验证了该算法的有效性。第三,本文研究了基于无线充电的无源传感器网络的覆盖问题。在基于无线充电的无源传感器网络中,存在充电桩和基于被动RFID标签的无源传感器节点。在这种网络结构中,充电桩通过旋转有向天线来为不同方向的无源传感器节点充电,并获取节点上的感知数据。由于充电桩在旋转天线和为节点充电时均需要耗费能量,且在单位时间内,有向天线只能收取单一角度上的感知数据,因此,如何合理地调度充电桩的天线,在最小耗能的情况下收集足够的感知数据,保障网络的有效覆盖成为了一个重要问题。为此本文定义了适应该网络拓扑结构的时隙支配集来保障网络的数据覆盖。并提出了最优化时隙支配集构造问题,同时证明了该问题是NP-难的。本文从不同的需求（快照需求和连续需求）和网络规模（小规模网络和大规模网络）出发,提出了三种近似算法,并从理论上证明了这三种近似算法的时间复杂度、通信复杂度和近似比。同时,本文也通过大规模的模拟实验验证了三种算法的正确性和有效性。第四,本文研究了基于混合能源的无源传感网的覆盖问题。在基于混合能源的无源传感器网络中部署有充电桩,节点既可以从无线充电源中获取能量,也可以从绿色能源中获取能量。本文在这种网络中提出了数据-能量双覆盖的概念。能量覆盖是指通过合理地部署充电桩来对无源传感器节点构成覆盖,通过稳定的能量供给弥补绿色能源分布失衡、能量波动的缺点。数据覆盖是指通过调度无源节点工作对监控区域构成覆盖,有效地监控、收集区域中的感知数据。然而,由于充电桩的部署成本较高,且节点调度严重依赖于区域中的能量分布,使得如何合理地部署充电桩,调度节点工作,降低充电桩部署成本,提高网络覆盖质量成为了一个重要问题。本文通过以下两个子问题来解决这一问题。第一个问题主要研究如何构造数据-能量覆盖,使得网络覆盖质量达到给定阈值,并最小化充电桩部署成本。第二个问题主要研究如何构造数据-能量覆盖,使得充电桩部署成本在不超过给定阈值的前提下最大化网络覆盖质量。本文证明了这两个问题均为NP-难问题。并证明了数据覆盖与能量覆盖之间的关系。同时,依据以上关系,本文针对这两个问题提出了两个近似算法。最后本文通过理论分析和实验模拟对以上两个算法的有效性进行了验证。第五,本文研究了基于部分无源节点的传感网中的覆盖问题。基于部分无源节点的传感网是指,网络中既包括传统有源传感器节点,也包括无源传感器节点。由于现存有大量的传统无线传感器网络,本文考虑在传统的传感器网络中加入无源传感器节点,并通过构造覆盖,保证网络功能完善的前提下,进一步提高传统传感器网络的寿命。本文通过构造连通支配集来保障网络的覆盖与连通,并将网络寿命重新定义为网络中可工作连通支配集个数。这种新型的网络寿命定义方式充分地考虑到了感知数据的空间相关性。基于该定义,本文提出了无源传感器网络中的连通支配集构造问题,并证明了该问题为NP-难问题。为了解决该问题,本文首先提出了一个基于重构网络的集中式算法。其次,对于大规模的传感器网络,本文提出了一个基于局部信息的分布式算法。本文证明了以上两个算法的近似比,并通过实验进一步验证了文中提出算法的有效性。