无线充电器网络中在线充电算法研究

1、苏州大学本科生毕业设计（论文）目 录前 言1第一章 绪论31.1 背景知识31.1.1 无线充电技术基本定义31.1.2 无线充电技术研究历程31.1.3 无线充电技术分类41.1.4 无线充电技术标准61.2 研究背景71.2.1 无线充电技术优点71.2.2 无线充电技术应用71.3 研究动机81.4 本文主要工作及创新点91.5 本文组织安排9第二章 问题建模112.1 问题初步建模112.1.1充电模型112.1.2充电功率及电磁辐射模型112.2 本文问题建模122.2.1充电任务122.2.2充电效用122.2.3问题形式化132.3 本章小结14第三章 算法设计153.1 集中式

2、在线算法153.1.1 区域划分及问题重构153.1.2 时间交点划分173.1.3算法形式化步骤183.1.4 解正则化183.1.5 概率分布函数的二重积分化解问题203.1.6 问题最终转化213.2算法求解213.2.1算法描述213.2.2算法形式化步骤223.3 本章小结23第四章 仿真实验244.1 实验参数设置244.2 基本实验结果分析244.2.1 充电器和充电设备分布244.2.2 TOIP结果分析254.2.3 区域划分结果264.2.4 CALP结果分析274.3 对比算法设计294.4 对比算法结果分析304.5算法运行时间对比324.6结论324.7本章小结32第

3、五章 本文总结与展望345.1 本文总结345.2 未来研究展望34参考文献36致 谢38摘要随着电子科技的高速发展与商业化需求的日益增长，日新月异的创新发明产品逐渐丰富并提高人民的生活，而设备的能量补给方式也在悄悄发生改变。从最初的铅蓄电池到锂电池，再到可充电电池、太阳能电池，见证了科技革命的一次次剧变。无线充电技术的出现，不仅是科技界的一次腾飞，也将会成为未来充电方式的发展趋势，给人们生活带来极大便利。无线充电技术的关键问题之一就是充电效用的优化问题，以往工作考虑的大多是电磁辐射约束，而忽略了充电设备的充电功率过大带来的一些问题，但这也是研究人员必须迎面直对的。我们提出一个新的概念：冷充电

4、（cool charging），限制充电设备的接收功率，从而缓解充电功率过大造成的一系列问题。本文研究的工作是在充电任务动态到达，不同充电任务起止时间不同的前提下，在充电设备接收功率阈值的约束条件下，实现无线充电在线最优调度，同时达到冷充电的目标。本文将对无线充电在线调度问题进行建模，得到形式化的问题定义，借助一定近似和离散的方法得到问题的约束条件，然后，使用线性规划的方法解决问题。最终，我们将开展MATLAB仿真实验，验证提出的算法性能。关键词：冷充电；无线充电；动态到达；充电设备接收功率；充电效用AbstractWith the rapid development of electroni

5、c technology and the increasing demand for commercialization, innovative and inventive products have been gradually enriching and improving people's life. The ways of energy supplying for device have also quietly changed. From the initial lead-acid batteries to lithium batteries, rechargeable ba

6、tteries, and solar cells, we witnessed the dramatic changes in scientific and technological revolution. The emerging of wireless charging technology is not only a take-off of the scientific and technological community, but also will lead the trend of future charging methods, bringing great convenien

7、ce to people's life. One of the key issues of wireless charging technology is the optimization of charging utility. In the past, most of the work considered electromagnetic radiation constraints, and thus some problems caused by excessive charging power of the rechargeable devices are neglected.

8、 However, this is also the problem that the research personnel must face up. We propose a new concept: cool charging, which limits the received power of the rechargeable device, and thus alleviates a series of problems caused by excessive charging power. The research work in our thesis is carried ou

9、t on condition that charging task arrives dynamically, different charge tasks start and end at different time. Then, under the constraint of the received power threshold of the rechargeable devices, the optimal online scheduling of wireless charging is achieved and the cool charging is guaranteed at

10、 the same time.In this article, we will model the problem of online scheduling of wireless charging and obtain a formal definition of the problem, and use certain approximate and discrete methods to get the constraints of the problem, and then apply linear programming to solve the problem. In the en

11、d, we will carry out MATLAB simulation experiments to verify the performance of proposed algorithm.Keywords: Cool Charging; Wireless Charging; Dynamically Come; Received Power of Rechargeable Device; Charging UtilityIV前言近年来，随着电子科技方面的高新技术不断创新与发展，各个研究领域的创造发明也在逐渐深刻地改变着人们的生活。在电子设备能量供给方面，从最初的铅蓄电池到锂电池，从有线

12、充电到无线充电，人们的生活方式正在发生前所未有的改变。无线充电技术又称为无线电能传输技术（wireless power transfer），顾名思义，就是使用电磁辐射能量代替导线，给设备进行充电的技术。从技术原理以及实现方案来讲，目前无线充电技术主要有四种基本方式：电磁感应式、电磁共振式、无线电波式、电场耦合式。结合目前不同研究机构的最新研究成果，可细分为九种方式，具体将在文中论述。目前的无线充电行业主流的技术标准有三种：Power Matters Alliance（PMA）标准、Qi标准、Alliance for Wireless Power（A4WP）标准。无线电能传输技术的出现，拯救了依

13、靠导线连接充电的种种桎梏与障碍，如电线生产、架构、铺设、维护等产生的成本问题，携带不方便以及易磨损毁坏带来的不安全问题等。但是，世界上所有的事情都不是绝对的，失之东隅，收之桑榆，无线充电技术在日益丰富便利人们生活的同时，其带来的各种问题也一直伴随着它自身的成长与发展过程。充电功率（即，可充电设备接收功率）过大造成的电磁辐射严重、发热量大对设备造成损害、异物存在影响充电效率等问题，也是相关研究人员必须直面解决的。本课题将在原有无线充电模型的基础上进行展开，研究在线充电算法，并提出冷充电（cool charging）的新概念，限制充电设备的接收功率，保证充电过程是低温安全的，从而缓解功率过大造成的

14、一系列问题。在充电设备接收功率阈值的约束条件下，实现无线充电在线最优调度，完成带“冷充电”约束条件的最大化充电设备整体充电效用算法的编写与实现，并进行仿真实验，对算法的性能进行分析和完善。本文完成的主要工作及创新点有：（1）检索现有资料，研究分析充电功率过高引发的各种问题。（2）提出冷充电（cool charging）的新概念，定义基本充电模型及电磁辐射模型。（3）在充电任务动态到达的模式下，以在线方式调度充电过程，提出充电效用函数。（4）与以往不同，本文不直接考虑电磁辐射条件约束，转而考虑每个设备的最大接收功率的约束。（5）形式化带设备接收功率阈值约束的充电效用最大化目标函数，并提出“区域划

15、分”和“解正则化”的方法帮助求解问题。（6）编写算法实现总体充电效用最大化，并进行仿真实验，分析算法性能，分析将来可能出现的问题，做出总结。第一章 绪论本章介绍了无线充电技术的概况，包括研究历程、技术分类和标准，从无线充电技术的优点和应用出发阐述了研究背景，明确了本文的研究动机是冷充电，罗列了本文的主要工作及创新点，最后阐明了本文的组织安排。1.1 背景知识1.1.1 无线充电技术基本定义无线充电技术从广义上来讲又被称作无线电能传输技术（wireless power transfer，WPT），是指电能从电源到负载设备没有通过电气设备直接接触的能量传输方式，即它无需导线，依靠电磁波传播能量，然

16、后将电磁波能量转化为可供负载使用的电能，最终实现无线充电。1.1.2 无线充电技术研究历程过去的几百年见证了无线电能传输从理论基础到技术创新、研究成果，再到商品化应用的里程碑式的发展。1820年，安培发现了通电电流可以产生磁场，电与磁的关系开始受到关注。1831年，法拉利发现电磁感应现象。1864年，麦克斯韦建立了电磁场方程组1。1893年，美国科学家尼古拉·特斯拉在哥伦比亚世博会上，在没有电线的情况下点亮了无线磷光照明灯。1961年，William C. Brown 出版了第一篇提出以微波作为能量传输载体的研究文章，并开发了基于磁控管的微波整流天线。20世纪80年代，电磁感应式的无

17、线电能传输技术引起研究人员的关注，并逐渐兴起。2007年，美国MIT的Marin Soljacic教授带领他的研究团队，基于“磁耦合谐振式原理”，以40%的效率点亮了一盏距电源2m外的60W电灯，开辟了无线电能传输技术的新纪元2。2010年，海尔公司推出“无尾电视”。2011年3月，松下推出具有无线充电模块的太阳能电池板。2012年9月，诺基亚联合微软发布了一款能无线充电的手机。2013年，东南大学研发了单台充电功率可达3kW的磁耦合谐振式无线充电的电动汽车。2015年，KAIST在韩国南部城市建立了12km长的电动汽车无线供电示范工程。2016年，中惠创智公司在矿井设备监控系统中，采用WPT

18、技术，解决了设备供电安全问题3-4。下图1. 1标出了无线充电技术的历史概要及里程碑式事件。图1. 1无线电能传输发展简史1.1.3 无线充电技术分类随着无线电能传输技术的发展进步，基于不同原理无线输电的方式也百花齐放，占领了科技市场的不同角落。下表1. 1结合现有资料，从传输功率、传输距离、使用频率范围以及充电效率方面等对比了九大无线充电技术5。1) 电磁感应式：原理：初级线圈通入变化的交流电，电磁感应在次级线圈产生感应电流。表1. 1几种无线充电技术的比较优点：对于短距离充电，充电效率较高。缺点：需要准确对准；金属涡流导致发热。2) 电磁共振式原理：谐振器使发射端和接收端线圈达到调制频率，

19、产生磁场共振传输电能。优点：实现了远距离大功率输电；效率一般。缺点：输电效率低下；电磁波辐射影响生物体安全。3) 无线电波式原理：发射天线将电磁波能量传播至接收天线，经过整流转换为电能使用。优点：小功率远距离充电。缺点：输电效率低；充电时间长。4) 电场耦合式原理：非对称偶极子在垂直方位耦合产生强感应电场，实现输电。 优点：输电距离远且效率高；发热量小；无需对准。缺点：设备尺寸大，功率不高。5) WattUp 原理：基于RF射频天线技术，将线圈替代为PCB天线。优点：远距离空间传输；体积小；“放下即充”；多个设备可同时充电。6) Wi-Fi无线充电原理：系统主要包括Wi-Fi接入点（路由器）和

20、定制充电传感器。优点：随走随充，空间自由。缺点：难以定位服务对象，能量利用率低。7) 超声波式原理：利用超声波隔空输送能量。优点：接收装置轻便价廉；技术相对安全；具有数据传送功能。缺点：在安全、功率等方面市场产品难以达到预期。8) AutoCharge聚焦光线充电原理：微软研究方案，包含两个模块：监测识别模块和充电模块，采用UltraFire CREE XM-L T6来聚焦LED光线。优点：全天随时充电；充电目标易识别。9) Wi-Charge红外光充电原理：发射机将能量转化为红外光，借助设备附带的接收机将红外光转化成电能。优点：无电磁辐射，相对安全。缺点：物体阻断光束后，充电会受到影响。充电

21、对象局限于移动设备等商品。1.1.4 无线充电技术标准目前的无线充电行业主流的标准大致有三种：Power Matters Alliance（PMA）标准、Qi标准、Alliance for Wireless Power（A4WP）标准。1) Qi标准Qi标准是目前最为主流的标准，是无线充电联盟WPC（Wireless Power Consortium）制定的业界首个无线充电国际标准。便携和通用是其两大特性。技术原理上，Qi标准采用当前主流的电磁感应技术。联盟成员主要有华为、诺基亚、HTC等知名公司。2) PMA标准PMA（电力事业联盟）标准是由宝洁与Powermat公司共同经营，成员包括AT&

22、amp;T、谷歌、BlackBerry等。其同样基于电磁感应原理。3) A4WP标准A4WP（无线电力联盟）标准由高通、三星以及Powermat公司共同创建。不过到目前为止，该无线充电标准都没有设备支持。其输电技术基于电磁谐振方式，输电距离相对较远。1.2 研究背景1.2.1 无线充电技术优点传统电气设备有线连接带来的电线外露损耗问题，较易产生摩擦火花，从而降低输电安全可靠性，使设备的使用周期减少。品质差的导线还会使接触电阻变大，引发局部高温导致火灾等危险事故。传统电线接触摩擦形成的电火花对采矿等特殊环境也构成极大的威胁。电线连接供电应用于水下探测领域时，还会招致电击风险6。与传统的线缆充电相

23、比，无线充电的亮点就彰明较著了。首先，其无需麻烦连接电线的特点提升了用户友好性。不同品牌型号的设备也可以选用相同的充电器。其次，它为无接触设备提供了更好的产品耐久性（如，防水防尘）。此外，灵活性大大提升，尤其对于因充电而必须更换电池或连接电线而带来费用昂贵、操作危险或实际不可行等问题的设备（如，身体植入式传感器）来说是明显有效的。最后，无线充电技术可实现按需充电，避免充电过量问题，并最小化能量损失。1.2.2 无线充电技术应用无线充电技术在便携式通讯设备、交通运输、医疗器械、水下探测、航空航天、电力系统、新能源发电等领域6均有着广泛的应用前景。下面简单介绍几种常见的应用领域。1) 便携式通讯设

24、备&医疗器械WPT技术最近几年的研究开始投入于便携式设备和移动设备。由香港城市大学的许树源教授率领的团队研发诞生了依据感应式耦合技术（inductively coupled power transfer）的移动电话、MP3 等。医用植入式仪器的能源补给方式也将因WPT技术而转变。例如，具备无线充电功能嵌入身体的心脏起搏器可以大大减少医疗成本，同时降低病人因更换电池而带来的安全风险，并减少病人的病痛。2) 交通运输&航空航天在交通运输领域，主要应用于智能车载平台、电动汽车等公共交通设施。微波无线输电技术的创新突破，使得微波向地面输送电能成为可能。利用空间太阳能电站集取的能量以微波

25、形式给卫星供能，同时也可向地面发射，供设备补充电能。3) 水中探测在水中探测方面，无线电传输技术更是崭露头角。其使石油矿田等能源探测持续勘测、航行船舶长久续航变得容易便利，大大提高了效率。1.3 研究动机无线充电技术以其无需连接、非直接接触的强大优势为各行各业带来了便利，然而，充电功率过高带来的电磁辐射威胁、发热量大损害设备、异物存在降低充电效率等问题，也是每位研发职员必须斟酌的。我们提出冷充电（cool charging）的新概念，严格把控充电设备的接收功率。冷充电这个概念是由我们首先提出的。从字面上不难理解，“冷充电”就是在给需要充电的设备充电的过程中，保证“冷”的环境，那么冷的对象有哪些

26、？首先是充电设备，充电过程应保证设备发热量不能过高，否则会引起电池损耗、设备烧坏或爆炸等安全问题。其次是设备（包括充电器和充电设备）的周围环境，如果充电功率过高，而设备周围又存在金属物，则会引起涡流效应，严重情况下会引起火灾等安全事故。以下，简单介绍一下充电设备接收功率过大导致的问题：电磁辐射：无线电能传输技术是利用中高频电磁场耦合实现电能传输，电磁辐射功率越大，辐射至周围物体上的能量也越多。生命体长期暴露在超出安全限值的电磁环境中，会使其生物机能下降，增加患神经系统、心脑血管系统和生殖系统等疾病的概率，甚至还会对人的心理和行为健康产生负面影响7。发热：充电功率过高，当电池由于过大电流充放电或

27、异常时，电池温度急剧上升，如果电池长时间工作在高温环境，如45 以上，会导致发热量过大，严重影响电池的有效使用寿命8。异物检测：检测无线充电磁场周围环境是否存在异物，以金属物体为主，因为金属受输电影响可能会发热导致火灾9。铁磁性金属会产生涡流效应和磁效应，对线圈的影响以涡流效应为主。金属体积越大，越靠近线圈，对线圈参数的影响越大，涡流损耗也越大，对系统效率的影响也越严重10。因此，无线充电技术冷充电目标的实现，对无线充电技术的发展也会起到承前启后的作用，不仅可以保护充电器和充电设备，延长其有效使用寿命，还可以提升系统的充电效率。同时，充电器根据充电设备的功率约束条件，以在线方式自动调节发射功率

28、，有效节省了能源，减少充电能量损失。1.4 本文主要工作及创新点本课题将在原有无线充电模型的基础上进行展开，研究在线充电算法，并提出冷充电的新概念，保证充电过程是低温安全的。本文主要的工作及创新点如下：（1）检索现有国内外资料，研究分析并归纳抽取因可充电设备的充电（接收）功率过高出现的主要问题。（2）提出冷充电的新概念，为之后研究深度细化奠定基础。采用传统经典的基本充电模型。（3）充电任务动态到达，即每个充电任务开始和结束时间点各异，因此，以在线方式调度整个充电过程。（4）提出充电效用函数，定义充电效用为充电装置在充电周期收取的能量与所需电能比值，即充电过程获得的收益大小。（5）区别于之前研究

29、，本文不直接考虑电磁辐射约束，而是考虑每个设备的接收功率阈值约束。（6）形式化最大充电效用目标函数，约束条件为每台设备接收功率最大值，并提出“区域划分”和“解正则化”的方法使得问题可求解。（7）编写算法实现我们提出的目标函数。（8）进行MATLAB仿真实验，分析算法的性能，并设计其他算法进行对比分析，探讨潜在的问题，做出概括总结。1.5 本文组织安排本文共分为五章，各章内容组织安排如下：第一章：绪论。本章介绍了无线充电技术研究历程、技术分类、行业标准，研究背景，研究动机以及本文主要工作及创新点，最后阐明了本文的组织安排。第二章：问题建模。本章具体论述了无线充电模型、充电功率及电磁辐射模型、充电

30、效用，最后形式化定义了本文的研究问题，包括目标函数及约束条件。第三章：算法设计。本章提出了求解目标函数的步骤及方法，从区域划分、时间交点划分、解正则化策略的提出到最后求解算法步骤的建立，展示了问题求解的详细过程。第四章：仿真实验。开展MATLAB仿真实验，得到算法的运行结果，验证了算法的可行性和正确性，并设计执行了两种对比算法，得出最终结论。第五章：本文总结与展望。对文章做出总结，在本文基础上，展望未来研究内容的改善方向与提升空间。第二章 问题建模本章具体阐释了传统的经验无线充电模型、充电功率及电磁辐射模型以及充电效用函数，最后从本文具体问题着手，形式化定义了本文的研究问题，包括目标函数及约束

31、条件。2.1 问题初步建模2.1.1充电模型假设在二维平面内，有n个无线充电器，用集合S=s1, s2, s3, , sn表示，有m个可充电设备，用集合O=o1, o2, o3, , om表示。所有的无线充电器都是相同规格的，可充电设备通过接收无线充电器发射的电磁能量进行充电。可充电设备接收到的充电功率从直觉上理解是与其距充电器的距离相关的，即距充电器越近，充电功率越大，反之越小。我们采用经验全方向充电模型11，充电设备oj 接收到来自充电器si的充电功率如下：Psi,oj=d(si,oj)+2, dD0, d>D（2. 1）可充电设备从充电器接收到的充电功率是Psi,oj，d表示充电设

32、备与充电器的距离，参数和是预定义的常量，与充电器和可充电设备的硬件参数及周围环境因素有关，D表示充电器发射功率到达的距离上限。假设充电器可以从0到一个最大值连续地调节发射功率，定义调节因子xi为充电器si发射功率与最大功率的比值（0xi1），因此，设备从充电器接收的功率可表示为Psi,ojxi。同时，假设充电功率具有可加性，即可充电设备从多个充电器那接收到的充电功率是可叠加的。2.1.2充电功率及电磁辐射模型由于充电功率具有可叠加性质，因此，充电设备oj接收到的总功率是覆盖其的所有充电器发射功率之和，即：Poj=i=1nP(d(si,oj)=i=1nP(d(si,oj)xi（2. 2）其中，d

33、(si,oj)表示可充电设备oj到充电器si的距离。我们采用经验电磁能量辐射模型12，换句话说，平面上一点p处接收到的电磁辐射能量是与覆盖至那的充电功率成比例的，同时也具有可加性，即：ep=i=1ne(d(si,p)=C1i=1nP(d(si,p)xi（2. 3）C1是预定义的比例系数常量。同时，为了保证电磁辐射安全性约束，我们需要限制平面上的任意一点p处的EMR(ElectroMagnetic Radiation)值，即C1i=1nPdsi,p xit，在充电周期内的任意时间点t都不超出一个给定的EMR阈值，可表示为：C1i=1nPdsi,p xitRtp（2. 4）2.

34、2 本文问题建模2.2.1充电任务初步了解了基本的问题模型，下面提出本文的问题模型。假设有一些可充电设备动态地加入或离开平面，它们停留在期间内，这些可充电设备动态地提出m个无线充电任务Tjj=1m，并且通知它们周围的充电器处理。与以往不同的是，假设我们仅仅知道任务Tj可能的位置区域Aj和位置发生概率分布函数j，而不知道它的精确位置，其中，j表示任务Tj发生在位置p的可能性，具体可表示为j(p)。问题可形式化表示为一个五元组Tj=<Aj,j,trj,tej,Ej>，trj和tej分别代表任务的提出和结束时间，Ej表示可充电设备需要的充电能量。2.2.2充电效用假设充电效用函数

35、9984;(𝐸)13刻画了充电任务获得的一定量能量E的收益，并且通常是凹函数。任务Tj需要的充电能量为Ej，在结束时间tej前获得的能量为E，则充电效用可表示为：UE=1EjE,   EEj1,         E>Ej（2. 5）2.2.3问题形式化本文研究的是无线充电在线算法的研究，假设充电时间连续，充电器功率可连续调节，充电任务动态到达，因此任务提出的起始点不同。 正如前文提到的，若可充电设备接收到的充电功率过高，会对设备造成不可预估的损害，因此我

36、们约定，对于平面内任一设备oj，其最大接收功率为PjMAX，同时，由于设定的PjMAX值也是综合考量了EMR安全限制的条件下得出的，所以本文不直接考虑EMR条件约束，转而考虑每个设备oj的最大接收功率的约束。充电设备的数目为m，每个充电设备的充电任务Tj都有一个开始时间trj和结束时间tej，因此，如果要将其映射为统一的时间序列T(x)（便于求解问题），则T(x)的元素个数应该为2m，即T1T2m。假设时间ttT1,T2m表示整个调度算法的持续时间，T2m=maxtejj1,m。显而易见，对于充电任务Tj，其在点pAj接收到的功率是i=1nPsi,pxit，它在充电周期内接收到的总功率是trj

37、teji=1nPsi,pxitdt，考虑概率分布j后，任务Tj的预期充电效用为：（2. 6）由于每个充电任务对实际应用的贡献大小是不同的，换句话说即重要程度是各异的，所以对每个任务Tj都有一个权重值j，得到加权后的总充电效用为：（2. 7）为了保证冷充电，对于设备oj经过的任一区域x，需满足以下条件：i=1nPsi,pxitPjMAX (px; tT1,T2m)（2. 8）最后，我们定义带充电设备接收功率阈值约束条件的无线充电任务在线最优调度目标函数为：P1s.t. i=1nPsi,pxitPjMAX px; tT1,T2m0xit1. (i=1,2,n)2.3 本章小结本章对所研究的问题一步

38、步地进行了剖析，从初步问题建模，掌握基本的充电模型，再逐渐过渡到本文所研究无线传感器网络在线算法的研究，从冷充电目标得到条件约束，最终给出了本文问题的形式化定义。第三章 算法设计本章，我们提出了一种集中式算法来解决带功率约束的无线充电任务在线调度问题。由于可充电设备在某区域的接收功率函数是连续和非线性的，我们提出了一个区域划分的方法来近似充电功率，从而得到有限个线性约束。时间交点划分（Time Intersection pOint Partition，TIOP）算法是为了辅助解决解正则化定义问题，解正则化定义则是为了将问题等价转换成线性有限求解的过程。最后定义我们的研究问题为Online Sc

39、heduling of wireless Charging tAsks with rEceived Power constraints (OSCAEP)。本章提出了求解目标函数的步骤及方法，展现了求解问题的详尽过程。3.1 集中式在线算法3.1.1 区域划分及问题重构我们首先提出一个分段常数函数来近似非线性功率函数，如下Error! Reference source not found.所示：图3. 1功率近似函数函数中分段常量线段在横轴上d对应的端点设为l1,l2,lQ (l0=0,lQ=D)，然后我们以每个充电器为圆心，分别以l1,l2,lQ为半径画同心圆11，这样，对于每个充电器，整个二

40、维平面被划分成许多子区域，设子区域的数目为Z。同理，这些同心圆同样将任务Tj 的发生区域Aj划分成Vj个子区域，即：Ajvv=1Vj。由于在相同的子区域里，经过近似后的每个充电器发射的功率是个常数，那么，每个子区域从附近充电器接收的总充电功率也是常数。下Error! Reference source not found.展示了一个区域划分的例子，通过为三个无线充电器中的每一个绘制半径分别为l1和l2的两个同心圆，整个平面被划分为15块子区域，任务T1和T2的发生区域也被分别划分为子区域A11、A12、A13和子区域A21、A22。下面的定理说明了如何设置l1,l2,lQ的值。图3. 2区域划分

41、定理3. 1：设l0=0，lQ=D，lq=(1+q21)(qQ1)，并且使用以下分段常数函数P(d)作为充电功率函数：P(d) =Pl1,                                      

42、60;             d=l(0)Plq,              lq1<dl(q)(qQ)0,                  

43、;                                                  

44、;  d>D（3. 1）其中， 是预设误差阈值，任一子区域中任一位置的功率近似误差满足：1P(p)P(p)1（3. 2）由于在每个子区域Ajv的近似总功率是一致的，我们可以将子区域Ajv内任意一点的近似充电功率表示为：i=1nPijvxi(t)，Pijv表示当充电器si调到最大功率时Ajv处的近似功率。因此，所有充电任务的预期近似充电效用为：（3. 3）同样地，对于设备oj提出的充电任务Tj 的发生区域Aj被划分成的Vj个子区域，每个子区域内的近似功率也是一致的，因此得到的功率约束为：i=1nPijvxi(t)PjMAX(v1,Vj;tT1,T2m)（3. 4）相应地

45、，问题P1的近似版本可重新定义为：P2s.t. i=1nPijvxi(t)PjMAX(v1,Vj;tT1,T2m)0xit1. (i=1,2,n)其中，Pijv是在子区域Ajv内获得的充电器si的最大近似功率，我们的目标是为所有充电器确定调节因子xit i1,n;tT1,T2m。3.1.2 时间交点划分由于充电时间是连续的，我们构想了时间交点划分算法（Time Intersection pOint Partition，TIOP）来为解正则化做铺垫。充电任务Tj=<Aj,j,trj,tej,Ej>，trj和tej分别表示任务的提出和结束时间。首先，我们将充电任务Tj的开始时间trj和

46、结束时间tej一起非降序排列，并标记好每个时间点对应的任务标识号，以确保在某一时间段内能够获悉有哪些充电任务在进行。下图3. 3给出了一个时间交点划分的例子。从图中我们可以看到时间序列为：Tx=(tr1,tr2,tr3,te1,te3,te2,tr4,te4)，正如前面提到的，ttT1,T2m表示整个调度算法的持续时间，T2m=maxtejj1,m，因此，我们首先将时间序列Tx一一映射为T1T2m，然后将时间序列Tx的每个元素值减去首元素tr1的值，对于图3. 3的例子，将Tx=(tr1,tr2,tr3,te1,te3,te2,tr4,te4)映射为T1T8，T1=0，T8=te 4 tr1。

47、从图中可以看到，四个充电任务分别用不同的颜色标注，不同任务的充电时间周期有交叉重叠，而在实际充电中，某些时间点可能相同。图3. 3时间交点划分示例图3.1.3算法形式化步骤算法：时间交点划分算法（TIOP）输入：每个充电任务Tj的开始时间trj和结束时间tej输出：时间序列T1,T2,T2m1. 将开始时间序列trjs和结束时间序列tejs合并成一个序列task_time(i)s；2. 将task_time(i)s按照非降序排序；3. for 所有的task_time(i)s do4. Titask_time(i)；5. for 所有的task_time(i)s (i1) do6. TiTiT

48、1；7. 将首元素T1的值置为0。8. 输出时间序列T1,T2,T2m。3.1.4 解正则化问题P2的一个关键挑战在于充电器调节因子的随意性，它随时间连续变化。为解决这个问题，我们提出了一个解正则化的方法，下面给出它的规范化定义：定义3. 1：（解正则化）对于问题P2的任意可行解xit i1,n;tT1,T2m，在时间段Tk1 Tk (k=p,p+1,q1,q;q>p; T1=0)内，它的正则化形式定义为：xi,k=Tk1TkxitTkTk1(kp,q)引理3.1：对于问题P2的任意可行解，它的正则化形式仍然是可行的，并且完成相同的充电效用。证明：首先，我们证明正则解对于P2是可行的。从

49、问题P2的定义，给定一个可行解xit i1,n，则有i=1nPijvxi(t)PjMAX(v1,Vj)。对于tTk1 Tk)，i=1nPijvTk1Tkxi(t)Tk1TkPjMAX=(TkTk1)PjMAX，因此，i=1nPijvTk1Tkxi(t)TkTk1=i=1nPijvxi,kPjMAX。由于0xi(t)1，很明显，0xi,k=Tk1TkxitTkTk11，因此，xi,k是问题P2的可行解。然后，我们证明正则解可以达到相同的目标效用。对于设备oj，它在时间Tp,Tq获得的充电功率为：TpTqi=1nPijxitdt=i=1nPijk=pqTk1Tkxitdt=i=1nPijk=pq(

50、TkTk1)Tk1Tkxi(t)TkTk1dt=i=1nPijk=pqTk1Tkxi,kdt因此，我们可以得到：下图3. 4展示了一个正则化的例子，原始解x1(t)和x2(t)由淡蓝色和浅绿色实线表示，它们相对应的正则化形式分别由淡蓝色和浅绿色虚线表示。这里时间片有三段，对应地，每一个正则化形式有三段，它们在时间段0 T1)，T1 T2)，T2 T3)的值是常数。图3. 4正则化示例由引理3.1得知，任意可行解都等价于它的正则化形式，因此，我们只需要考虑解的正则化形式，因而，问题可以重写为问题P3：P3max xi,kj=1mjv=1VjPrAjvU(i=1nPijvk=pq(TkTk1)xi

51、,k)s.t. i=1nPijvxi,kPjMAX0xi,k1. (i=1,n;kp,q)3.1.5 概率分布函数的二重积分化解问题是双重积分问题，不易求解。就此，我们先来讨论PrAjv的几何意义，被积函数j表示任务Tj发生在位置p的可能性，积分区域是任务Tj可能发生的位置区域，那么PrAjv的几何意义相当于可能发生的子区域面积占总区域面积的比例。既然知道PrAjv的几何意义，问题就转化为求任务Tj可能发生的相应子区域的面积，我们采取“撒点法”来计算，计算后的结果定义为Arjv=PrAjv，则问题P3重写为P4：P4max xi,kj=1mjv=1VjArjvU(i=1nPijvk=pq(Tk

52、Tk1)xi,k)s.t. i=1nPijvxi,kPjMAX0xi,k1. (i=1,n;kp,q)3.1.6 问题最终转化问题P4不能直接被求解，因此，我们将它转化为线性规划问题。引入辅助变量yj，则问题P4重写为：P5max xi,k,yjj=1mjyjs.t. i=1nPijvxi,kPjMAXyjv=1VjArjvUi=1nPijvk=pq(TkTk1)xi,k0xi,k1. (i=1,n;k=1,q)注意xi,k(i=1,n;kp,q)和yj(j=1,m)是决策变量。3.2算法求解3.2.1算法描述我们提出了一种集中式的算法来求解问题P5。所谓集中，就是收集全网所有充电器和充电设备

53、的相关信息，集中处理数据和散播处理结果。首先证明对于任意>0，我们的算法的近似比至少为1，它的时间复杂度为O=(n4.5m5.5)，n和m分别表示充电器和充电设备的数目。证明：首先，解正则化方法同样适用于问题P1，因此，问题P1可以等价表示为：(P1')s.t. i=1nPsi,pxi,kPjMAX px; kp,q0xi,k1. (i=1,2,n)设问题P1'和问题P5（或P4）的解分别是xi,k和xi,k，接下来我们证明(1)xi,k同样适用于问题P5。考虑平面上的任意一点p，经过区域划分后p必位于一子区域Ajv，即pAjv。根据1P(p)P(p)1（3. 2，我们得

54、出：1PpPp=i=1nPijvxi,ki=1nPsi,pxi,k，因此，可以得到结果i=1nPsi,pxi,k(1)i=1nPijvxi,kPjMAX，这表明(1)xi,k同样适用于问题P4，因此其解为(1)xi,k的充电总效用为：max xi,kjmjv=1VjArjvU(i=1nPijvk=pq(TkTk1)(1)xi,k)(1)Umax因此，证明我们的算法至少完成了(1)的近似比。接下来，我们简要分析提出的算法性能。根据已有几何学知识，计算交点的子区域数目Z=On22，由于每个充电任务也有充电子区域，因此Z=Omn22，这是区域划分部分的时间复杂度。求解问题P5线性约束的时间复杂度为C

55、=O(mnq)（q是时间片个数），而q=O2m=O(m)，因此C=Omnq=O(nm2)。利用Karmarkar算法14求解线性规划，时间复杂度为Onm3.5C=O(n4.5m5.5)，因此，最终算法的性能为O=(n4.5m5.5)。3.2.2算法形式化步骤我们提出了集中式线性规划算法（Centralized Algorithm with Linear Programming）来求解问题P5，具体步骤如下：算法：集中式在线性规划算法（CALP）输入：充电模型参数、最大充电距离D，近似误差，时间序列T1,T2,T2m，需要的充电能量Ej，每个可充电设备oj接收能量的阈值PjMAX。输出：充电效用

56、Umax，调节因子xi,k1. 根据充电模型参数、最大充电距离D，近似误差进行区域划分；2. 计算区域划分后每个子区域和每个设备处的近似功率；3. 设置求解线性规划方程需要的不同参数；4. 利用线性规划方程求解问题P5，得到最优的充电效用Umax；5. 输出最优充电效用Umax和调节因子xi,k。3.3 本章小结本章给出了求解目标函数的规范化流程，依次阐明了区域划分离散化近似、常数求解的过程；时间交点划分为规范化求解做铺垫；解正则化将问题的解规范化为可计算的形式的策略方法，最终详述了算法步骤。第四章 仿真实验本章，我们通过开展MATLAB仿真实验来模拟实际充电场景，验证我们提出的算法的性能。在

57、此基础上，我们将本文提出的算法CALP分别与GREEDY算法和TOMLAB的CONOPT算子进行对比研究，证明我们的算法是总体相对较优的。4.1 实验参数设置本实验为了模拟实际充电情景，将二维平面充电场地 模拟为region大小为50×50的充电区域，平面 内分别布置了9个充电器和20个可充电设备，其位置都是随机产生的。充电模型相关的参数设置：=200，=50，D=10， 初始设置为0.12。、D是充电模型Psi,oj=d(si,oj)+2, dD0, d>D（2. 1中对应的参数， 是定理3. 1中经过区域划分后充电功率的近似误差值。充电器charger和充电设备device

58、参数设置：其位置分布均服从二维高斯分布，由于高斯分布的期望值决定点的位置所在，而标准差决定分布幅度大小，充电区域region的范围是50×50，而最大充电距离D=10，由此设置高斯分布期望为25（充电中心区域），标准差为10。充电任务task参数设置：为了便于之后安排调度的相关计算方便，将task定义为包含6个域的结构体，分别为：id（充电设备标识）、type（任务类型：0表示开始时间，1表示结束时间）、value（时间值）、E_needs（需要的充电电能）、P_max（任务Tj对应的功率阈值约束PjMAX）、weight（每个任务对应的权重大小）。由于每个充电任务都有开始时间和结束

59、时间，因此，task的数目为2*m（m为可充电设备的数量）。4.2 基本实验结果分析4.2.1 充电器和充电设备分布下Error! Reference source not found.显示了充电器charger和充电设备device的分布情况，其中，绿色圆点表示充电器，蓝色菱形表示充电设备。以充电器为圆心，最大充电距离D为半径画圆，可以看出充电器和充电设备均集中在充电区域中心位置，多个充电器可到达的充电区域相互交叉重合，只有两个device（5和20）没有被覆盖到。在后面，会以P(d) =Pl1,        

60、                                            d=l(0)Plq,    &#

61、160;         lq1<dl(q)(qQ)0,                                     &#

62、160;                                d>D（3. 1P(d) =Pl1,              

63、;                                      d=l(0)Plq,          &

64、#160;   lq1<dl(q)(qQ)0,                                                                      d>D（3. 1中的l1,l2,lQ (l0=0,lQ=D)为半径，以每个充电器为圆心画同心圆进行区域划分，并对得到的每个子区域进行编号，计算每个子区域和每个设备接收到的来自覆盖其的充电器的对