论文部分内容阅读
随着人工智能的发展和移动设备的普及,无线充电技术以其灵活性、可靠性和可扩展性等优点受到了工业界和学术界的广泛重视。经过近几年来的快速发展,无线可充电传感器网络已经广泛应用在如医疗护理、环境检测以及智能电网等多个领域。无线可充电传感器网络充电效用优化问题主要关注如何通过设计充电器的充电方案或者调度传感器节点,尽可能地最大化网络整体性能。现有工作往往是针对静态充电器场景设计一次性的部署方案,针对可移动充电器场景设计路径选择和充电时间调度方案,然而却忽视了静态充电器场景下充电任务调度方案的可能性。本文主要研究无线可充电传感器网络安全充电任务调度问题,探索如何调度充电器充电功率,在保证安全充电的前提下,实现传感器网络整体有效充电能量最大化的同时尽量缩短充电时间。本文是第一个提出静态充电器布置场景下安全充电任务调度问题的工作,并给出近似最优的轮调度方案。在给出集中式近似最优方案的同时,本文还设计并实现了分布式近似最优算法。本文首先讨论最大化有效充电能量问题,然后在最大有效充电能量的基础上,针对减少充电时间的目标,分别提出针对小规模传感器网络的集中式算法和针对大规模传感器网络的分布式算法。为了实现最大化有效充电能量的目标,本文首先使用区域离散化技术来近似连续非线性的电磁辐射约束,然后提出一个正则化的方法将任意一个可行解映射成分段常量函数形式,并最终转化为很容易求解的线性规划问题。在实现最小化充电时间的集中式算法中,本文给出两种搜索算法,基于二次约束线性优化的二分搜索算法和基于线性规划的二分搜索算法。前者复杂度高且无法保证能够得到可行解,后者则可以在有限时间内求得近似最优解,并且求解时间只与求解精度和线性规划问题的规模相关。在实现最小化时间的分布式算法中,本文首先提出一个区域划分的方案,将较大规模的传感器网络划分成多个固定大小的子区域,每个子区域方案求解过程只需要知道子区域内充电器的信息,不同子区域可以并行求解。通过合理划分子区域,可以利用子区域的解计算全局解。然后,为了给出算法的最优近似边界,本文提出区域放缩和电磁辐射放缩两种方法,前者是为了降低有效充电能量和充电时间之间的耦合性,后者则是为了调整以适应全局的电磁辐射约束。本文最终证明,集中式算法性能达到1/(1+ε)的最优近似,分布式算法可以实现在最大化有效充电能量上超过(1-ε)的近似以及低于最优解的最短充电时间。为了验证算法的性能,本文设计并实现了仿真实验和实际实验。仿真实验表明,本文提出的分布式算法可以实现在误差阈值ε ≥ 0.2的情况下,有效充电能量超过最优充电方案的94.9%,且充电时间比最优充电方案缩短近47.1%。实际实验表明,本文提出的算法在真实场景中针对有效充电能量和充电时间都优于比较算法。