本文是一篇软件工程硕士论文，本文考虑两个方面在无线充电部署方面，只要工作如下：本文的第一部分研究在给定静态传感器和充电功率预算下，如何部署充电器的位置和调节合适的功率使得充电效用最大化。该部分求解的问题是给定充电功率预算，和平面上一组传感器，将充电器部署在平面上，即确定位置和充电功率，从而使所有传感器的充电效用最大。
第一章 绪论
1.1研究背景
1.1.1 无线传感器网络
随着科学进步发展，无线方面技术逐渐成熟，例如通信技术、网络技术以及无线充电技术等，促进无线传感器网络的快速发展。无线传感网已经受到来自各个国家各种领域的广泛重视[1, 2]，并且近几年在军事，学术，工业都相应加大投入研究力度。早在 19 世纪 80 年代，美国 DARPA（国防部高级研究计划局）便开始建立自己的数据通讯无线传感器网络，接下来几年，亚洲和欧洲国家逐步加入，比如日本、朝鲜、德国、英国，我国也制定了相应的规划研究传感器网络。目前无线传感器网络涉及的领域已经越来越广泛了。
如图 1.1 典型传感器网络。一般情况下，工作人员在特定区域内部署各种类型传感器[3-6]，传感器的作用是感知或者监测环境内物理信息变化，比如湿度，温度，风力等，传感器将收集来的物理参数传输到汇聚节点，一般采用单跳或者多级跳方式发送数据。汇聚节点通过互联网或者其他通信网络传输到执行任务的管理节点，根据不同应用需求采取不同控制方案，智能化管理。
.........................
1.2相关工作
在过去的几年[30-32]，无线充电的能量传输在很多场景中，现存的研究大致可以分为静态充电器的布置和移动充电器。
对于具有移动充电器的情况，Fu 等人[33]研究最小充电延迟问题；他们通过规划移动充电器的最佳移动策略来解决问题，以便最小化将所有传感器设备充电到指定水平所需的时间。戴等人[34]研究了最小化移动充电器数量的问题，并规划了 2D 可充电传感器网络中的充电路线，以便所有设备都可以永久运行，他们证明了他们问题 NP.难的，并提出了近似算法。舒等人[35]考虑使用移动充电器的情况，并研究移动充电器的速度控制，以最大化整体充电功率。张等人[36]解决协同移动充电问题，其中移动充电器也可以相互充电。他们的目标是通过安排多个移动充电器来最大化能源效率。徐等人[7]研究如何在大规模无线传感器网络中安排多个移动充电器，使得在给定的监测周期内没有传感器会耗尽其能量。张等人[37]专注于解决无线移动充电器的行程选择和充电器关联问题Nikoletseas等[38]提出了一种能量平衡的交互式无线充电。现有研究已经考虑了各种决策变量和目标。为了最大化网络寿命，[39, 40]优化了充电顺序和数据包路由分配，[41]优化了充电器移动速度。为了使充电器移动时间在整个循环时间内所占的比例最大化，[42]优化了行驶路线和停车时间表。为了最大程度地利用能源，[43]优化了移动充电器之间的协作。为了使总充电延迟最小，[33]优化了停止位置和持续时间。[44]设计了基于 NDN 的能源监控和报告协议，特别着重于为多个同时发生的紧急事件调度移动充电器。为了同时最小化充电器行进距离和充电延迟，[45]优化了基于多个嵌套行程的同步充电序列。给定传感器的异质充电频率，[7]研究如何安排多个充电回合以最大程度地减小移动充电器的总移动距离。给定一组候选充电路线，[37]考虑了如何选择路线并确定相应的充电关联以最小化开销能量。与它们不同的是，我们的工作共同决定了充电器的放置和充电器分配，以改善充电质量，但要遵守预算限制。所以，主要研究充电器通过移动给传感器充电，主要关注一个或多个可移动传感器在网络中的移动路径，或者充电时间调度方案。
...............................
第二章 面向充电效用最大化的充电器部署优化
2.1引言
本章中，我们考虑在二维无线可充电器传感网的空间区域内，可充电的传感器节点随机部署，并且位置预先知道的，我们将其在上面布置静态充电器对其充电。如何在给定功率预算情况下，最大程度获得充电效用是本章主要研究内容。
研究的问题是在给定充电功率预算下，如何部署带档位的充电器的位置和充电功率使得充电效用最大化。本章考虑的充电器部署问题有如下几方面挑战，首先，充电器对传感器充电的充电功率，与它们两点之间的欧式距离有关并且有数学关系复杂，再加上充电器的充电功率又是可调节的，空间中传感器接受功率为各个充电器对它的叠加总和；其次，允许在平面任意位置部署充电器的位置，充电器功率又有多个档位，那么理论上解空间是无限的。
我们将求解 NP 完全集合覆盖问题归约为解决充电器部署的特殊情况，证明充电器部署是 NP 难问题。之后对问题进行重构，证明该问题是单调子模最大化，进而获得近似比为1 1/ 1+ 的贪心算法，这里 是平面区域离散化的误差阈值。
本章的组织结构如下：2.2 节介绍了本章工作中的可充电传感器网络模型，充电器的充电模型以及充电效用模型，并对部署问题进行描述。2.3 节把二维区域离散化。2.4 节对充电器部署优化问题进一步的分析讨论，提出解决方案。2.5 节通过仿真实验验证算法可靠性。2.6 节对本章中工作进行了总结。
............................
2.2仿真实验
这一部分，通过仿真评估我们提出算法的性能。具体而言，将提出的三个算法与本章 3.3节算法进行比较，研究了它们总功率（被选中的充电器功率之和）随小车个数 ，监测点个数 ，充电功率 以及充电时间 的变化情况。由于本章 3.2 节是标准的线性规划问题（LP），同样观察这些参数对其影响。
由于没有检测充电功率最小化的充电器部署优化的方法，我们自己设计了 3 个对比算法：暴力法、随机算法，贪心算法。第一个暴力法(OPT)，通过暴力枚举方法求出最优解；第二个随机算法(RAN)，随机选取监测点，直到满足约束条件；第三个贪心算法 GCN(greedychargernumber)，我们贪心准则为监测点通过小车个数，通过贪心选择经过小车个数最多的监测点，然而当监测点经过小车个数相同，随机选择监测点，直到满足条件。
接下来，我们将提出的算法与上述算法在不同设置进行比较。本节中绘制的每个数据点是 100 次随机种子重复实验的平均值，为了更好观察图像曲线，我们定义总消耗功率表示被选中的充电器功率之和。
我们首先研究小车 MVC（mobile charging vehicle）个数对总功率影响。如图 3.4 所示，小车数量较少，GCS 和 GCN 都接近最优解，但是随着小车的数量的增多，我们的算法 GCS总功率优于 RAN45.5%，优于 GCN 10%，主要原因当小车数量少的时候，两种贪心准则都可以把重要的监测点选择出来，所以效果都较好，但是随着小车数量增加，再加上小车经过监测点个数有限，会出现一些监测点经过小车个数相同的时候，而 GCN 算法当监测点经过小车相同时会随机选择监测点，导致总功率的增长率增加。而提出的 GCS 算法仍然会根据子模性选择较好监测点，并且是最优解1.5倍左右，符合定理 1 结论。LP 与 OPT 平均仅有 0.2 差距，这是因为 LP 充电器的功率是任意调节的来选出最优解，而 OPT 只是在已有充电器选出最优解。
.............................
第三章 面向充电功率最小化的充电器部署优化.................. 31
3.1引言.................... 31
3.2基础模型与问题形式化 .................. 31
第四章 总结与展望........................ 48
4.1总结............................ 48
4.2研究展望........................... 49
第三章 面向充电功率最小化的充电器部署优化
3.1引言
在无线可充电传感器网络中，通常会利用装载了可充电传感器的多个移动小车通过各自特定的周期性行驶路线执行各种数据监测任务，为了保证移动小车能够有充足的电能持续执行数据监测任务，可以考虑采用无线电能传输技术为移动小车提供持续的充电服务。具体地说，可以通过在网络中优化部署多个静态充电器，使得以各自特定的周期性路线行驶的每个移动小车都能够持续不断地执行监测任务。负责数据监测任务的移动小车有如下几个性质：首先，移动小车都有自己固定且周期性的行驶路径，每一个行驶周期从初始监测点出发，中间经过一系列固定的监测点，一个移动周期结束后会回到初始监测点并继续进行下一个周期的监测任务；其次，移动小车在其所经过的每个监测点都会停留一段时间执行监测任务，若某监测点部署了充电器，则移动小车在经过该监测点执行监测任务的同时将通过该监测点部署的充电器补充电池能量；最后，多个移动小车的行驶路线所经过的监测点可能会发生重叠，即每个监测点可能被多个移动小车通过。
无线充电器部署算法是无线可充电传感器网络领域研究的热门问题，有很多学者提出了相关解决方法，但是大多数方法考虑的是在传感器设备静态固定的情况下如何进行无线充电器的部署优化，而没有考虑在传感器设备移动的情况下，如何优化部署无线充电器从而为传感器设备提供持续不断的电能。实际上，很多应用场景都会利用移动传感器执行监测任务，因此，如何优化部署无线充电器为移动传感器设备持续提供电能是一个非常重要且具有实际意义的问题。
本章的组织结构如下：3.2 节介绍本章工作中的基础模型，并对部署问题进行描述。3.3 节是对问题进行详细分析，并提出解决方法
