近年来,无线能量传输技术的突破较好地解决了无线传感器网络中的能量供应问题,并且使得无线可充电传感器网络的发展成为可能。针对无线可充电传感器网络,大多数现有研究工作主要考虑传统的充电网络模型,即所有的充电站和传感器都由用户进行部署和维护。不同于现有工作,本文提出了一个新颖的协作充电服务模型。在该模型中,网络中的所有充电站由一个充电服务提供商(Charging Service Provider,CSP)进行部署和维护,用户根据特定的充电需求定期向CSP请求充电服务,并通知网络中的传感器设备移动到对应的充电站接受CSP提供的充电服务,最终用户依据充电服务时间向CSP支付相应的充电服务费用。基于上述充电服务模型,本文主要研究高时效低成本的传感器设备移动协作充电调度优化问题,即如何找到一个最优的传感器设备协作充电调度策略,以使得在满足时效性约束的前提下实现总充电服务费用最小化。本文分别针对不同类型的应用场景,对上述问题进行了深入的研究。(1)针对延迟非敏感(delay-insensitive)的应用场景,研究了基于位置一致性的高时效低成本的传感器设备移动协作充电调度优化问题。在该问题中,每个传感器设备在停止服务时间的约束下,选择合适的充电站完成充电后返回其初始部署位置。本文首先证明了该问题的NP困难性,接着探究了单充电站情况下的目标问题,并提出了一个多项式时间复杂度的最优解决方案,在此基础上,进一步结合贪心法与剪枝法的思想,为多充电站情况下的目标问题提出了一个多项式时间复杂度的有效近似算法。最终通过大量的仿真实验表明,本文的算法相比于其它对比算法,至少能够提高20%以上的性能。(2)针对延迟敏感(delay-sensitive)的应用场景,研究了基于拓扑一致性的高时效低成本的传感器设备移动协作充电调度问题。该问题放宽了对传感器设备移动范围的约束,使其完成充电后不一定必须回到初始部署位置,而只需保证所有传感器设备充电完成后回到的位置所形成的拓扑结构和初始部署位置形成的拓扑结构一致即可。针对该问题,本文首先研究单充电站情况下的调度,并通过三次优化,将其等价转换为最大基数瓶颈二部图匹配问题,并设计了一个多项式时间复杂度的最优化算法。然后在此基础上,使用贪心法和迭代法的思想,为多充电站情况下的目标问题提出了一个多项式时间复杂度的高效解决方案,并通过广泛的仿真实验证明了本文所提出的算法相比于其它对比算法具有明显的性能优势。
暂无评论