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

1、苏州大学本科生毕业设计（论文）IV目录 TOC o 1-3 h z u HYPERLINK l _Toc514425590 前 言 PAGEREF _Toc514425590 h 1 HYPERLINK l _Toc514425591 第一章 绪论 PAGEREF _Toc514425591 h 3 HYPERLINK l _Toc514425592 1.1 背景知识 PAGEREF _Toc514425592 h 3 HYPERLINK l _Toc514425593 1.1.1 无线充电技术基本定义 PAGEREF _Toc514425593 h 3 HYPERLINK l _Toc514

2、425594 1.1.2 无线充电技术研究历程 PAGEREF _Toc514425594 h 3 HYPERLINK l _Toc514425595 1.1.3 无线充电技术分类 PAGEREF _Toc514425595 h 4 HYPERLINK l _Toc514425596 1.1.4 无线充电技术标准 PAGEREF _Toc514425596 h 6 HYPERLINK l _Toc514425597 1.2 研究背景 PAGEREF _Toc514425597 h 7 HYPERLINK l _Toc514425598 1.2.1 无线充电技术优点 PAGEREF _Toc51

3、4425598 h 7 HYPERLINK l _Toc514425599 1.2.2 无线充电技术应用 PAGEREF _Toc514425599 h 7 HYPERLINK l _Toc514425600 1.3 研究动机 PAGEREF _Toc514425600 h 8 HYPERLINK l _Toc514425601 1.4 本文主要工作及创新点 PAGEREF _Toc514425601 h 9 HYPERLINK l _Toc514425602 1.5 本文组织安排 PAGEREF _Toc514425602 h 9 HYPERLINK l _Toc514425603 第二章

4、问题建模 PAGEREF _Toc514425603 h 11 HYPERLINK l _Toc514425604 2.1 问题初步建模 PAGEREF _Toc514425604 h 11 HYPERLINK l _Toc514425605 2.1.1充电模型 PAGEREF _Toc514425605 h 11 HYPERLINK l _Toc514425606 2.1.2充电功率及电磁辐射模型 PAGEREF _Toc514425606 h 11 HYPERLINK l _Toc514425607 2.2 本文问题建模 PAGEREF _Toc514425607 h 12 HYPERLI

5、NK l _Toc514425608 2.2.1充电任务 PAGEREF _Toc514425608 h 12 HYPERLINK l _Toc514425609 2.2.2充电效用 PAGEREF _Toc514425609 h 12 HYPERLINK l _Toc514425610 2.2.3问题形式化 PAGEREF _Toc514425610 h 13 HYPERLINK l _Toc514425611 2.3 本章小结 PAGEREF _Toc514425611 h 14 HYPERLINK l _Toc514425612 第三章 算法设计 PAGEREF _Toc51442561

6、2 h 15 HYPERLINK l _Toc514425613 3.1 集中式在线算法 PAGEREF _Toc514425613 h 15 HYPERLINK l _Toc514425614 3.1.1 区域划分及问题重构 PAGEREF _Toc514425614 h 15 HYPERLINK l _Toc514425615 3.1.2 时间交点划分 PAGEREF _Toc514425615 h 17 HYPERLINK l _Toc514425616 3.1.3算法形式化步骤 PAGEREF _Toc514425616 h 18 HYPERLINK l _Toc514425617 3

7、.1.4 解正则化 PAGEREF _Toc514425617 h 18 HYPERLINK l _Toc514425618 3.1.5 概率分布函数的二重积分化解问题 PAGEREF _Toc514425618 h 20 HYPERLINK l _Toc514425619 3.1.6 问题最终转化 PAGEREF _Toc514425619 h 21 HYPERLINK l _Toc514425620 3.2算法求解 PAGEREF _Toc514425620 h 21 HYPERLINK l _Toc514425621 3.2.1算法描述 PAGEREF _Toc514425621 h 2

8、1 HYPERLINK l _Toc514425622 3.2.2算法形式化步骤 PAGEREF _Toc514425622 h 22 HYPERLINK l _Toc514425623 3.3 本章小结 PAGEREF _Toc514425623 h 23 HYPERLINK l _Toc514425624 第四章 仿真实验 PAGEREF _Toc514425624 h 24 HYPERLINK l _Toc514425625 4.1 实验参数设置 PAGEREF _Toc514425625 h 24 HYPERLINK l _Toc514425626 4.2 基本实验结果分析 PAGER

9、EF _Toc514425626 h 24 HYPERLINK l _Toc514425627 4.2.1 充电器和充电设备分布 PAGEREF _Toc514425627 h 24 HYPERLINK l _Toc514425628 4.2.2 TOIP结果分析 PAGEREF _Toc514425628 h 25 HYPERLINK l _Toc514425629 4.2.3 区域划分结果 PAGEREF _Toc514425629 h 26 HYPERLINK l _Toc514425630 4.2.4 CALP结果分析 PAGEREF _Toc514425630 h 27 HYPERL

10、INK l _Toc514425631 4.3 对比算法设计 PAGEREF _Toc514425631 h 29 HYPERLINK l _Toc514425632 4.4 对比算法结果分析 PAGEREF _Toc514425632 h 30 HYPERLINK l _Toc514425633 4.5算法运行时间对比 PAGEREF _Toc514425633 h 32 HYPERLINK l _Toc514425634 4.6结论 PAGEREF _Toc514425634 h 32 HYPERLINK l _Toc514425635 4.7本章小结 PAGEREF _Toc514425

11、635 h 32 HYPERLINK l _Toc514425636 第五章 本文总结与展望 PAGEREF _Toc514425636 h 34 HYPERLINK l _Toc514425637 5.1 本文总结 PAGEREF _Toc514425637 h 34 HYPERLINK l _Toc514425638 5.2 未来研究展望 PAGEREF _Toc514425638 h 34 HYPERLINK l _Toc514425639 参考文献 PAGEREF _Toc514425639 h 36 HYPERLINK l _Toc514425640 致 谢 PAGEREF _Toc

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

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

14、 demand for commercialization, innovative and inventive products have been gradually enriching and improving peoples life. The ways of energy supplying for device have also quietly changed. From the initial lead-acid batteries to lithium batteries, rechargeable batteries, and solar cells, we witness

15、ed 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 convenience to peoples life. One of the key i

16、ssues 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. However, this is also the problem that t

17、he 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 out on condition that charging task arrives

18、 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 the same time.In this article, we will m

19、odel 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 end, we will carry out MATLAB simulation ex

20、periments to verify the performance of proposed algorithm.Keywords: Cool Charging; Wireless Charging; Dynamically Come; Received Power of Rechargeable Device; Charging Utility5。电磁感应式：原理：初级线圈通入变化的交流电，电磁感应在次级线圈产生感应电流。表1. SEQ 表1. * ARABIC 1几种无线充电技术的比较优点：对于短距离充电，充电效率较高。缺点：需要准确对准；金属涡流导致发热。电磁共振式原理：谐振器使发射端

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

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

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

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

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

26、h * MERGEFORMAT 6均有着广泛的应用前景。下面简单介绍几种常见的应用领域。便携式通讯设备&医疗器械WPT技术最近几年的研究开始投入于便携式设备和移动设备。由香港城市大学的许树源教授率领的团队研发诞生了依据感应式耦合技术（inductively coupled power transfer）的移动电话、MP3 等。医用植入式仪器的能源补给方式也将因WPT技术而转变。例如，具备无线充电功能嵌入身体的心脏起搏器可以大大减少医疗成本，同时降低病人因更换电池而带来的安全风险，并减少病人的病痛。交通运输&航空航天在交通运输领域，主要应用于智能车载平台、电动汽车等公共交通设施。微波无线输电技术

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

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

29、和行为健康产生负面影响 REF _Ref512264660 r h * MERGEFORMAT 7。发热：充电功率过高，当电池由于过大电流充放电或异常时，电池温度急剧上升，如果电池长时间工作在高温环境，如45 以上，会导致发热量过大，严重影响电池的有效使用寿命 REF _Ref512264676 r h * MERGEFORMAT 8。异物检测：检测无线充电磁场周围环境是否存在异物，以金属物体为主，因为金属受输电影响可能会发热导致火灾 REF _Ref512264683 r h * MERGEFORMAT 9。铁磁性金属会产生涡流效应和磁效应，对线圈的影响以涡流效应为主。金属体积越大，越靠近线

30、圈，对线圈参数的影响越大，涡流损耗也越大，对系统效率的影响也越严重 REF _Ref512264694 r h * MERGEFORMAT 10。因此，无线充电技术冷充电目标的实现，对无线充电技术的发展也会起到承前启后的作用，不仅可以保护充电器和充电设备，延长其有效使用寿命，还可以提升系统的充电效率。同时，充电器根据充电设备的功率约束条件，以在线方式自动调节发射功率，有效节省了能源，减少充电能量损失。1.4 本文主要工作及创新点本课题将在原有无线充电模型的基础上进行展开，研究在线充电算法，并提出冷充电的新概念，保证充电过程是低温安全的。本文主要的工作及创新点如下：（1）检索现有国内外资料，研究

31、分析并归纳抽取因可充电设备的充电（接收）功率过高出现的主要问题。（2）提出冷充电的新概念，为之后研究深度细化奠定基础。采用传统经典的基本充电模型。（3）充电任务动态到达，即每个充电任务开始和结束时间点各异，因此，以在线方式调度整个充电过程。（4）提出充电效用函数，定义充电效用为充电装置在充电周期收取的能量与所需电能比值，即充电过程获得的收益大小。（5）区别于之前研究，本文不直接考虑电磁辐射约束，而是考虑每个设备的接收功率阈值约束。（6）形式化最大充电效用目标函数，约束条件为每台设备接收功率最大值，并提出“区域划分”和“解正则化”的方法使得问题可求解。（7）编写算法实现我们提出的目标函数。（8）

32、进行MATLAB仿真实验，分析算法的性能，并设计其他算法进行对比分析，探讨潜在的问题，做出概括总结。1.5 本文组织安排本文共分为五章，各章内容组织安排如下：第一章：绪论。本章介绍了无线充电技术研究历程、技术分类、行业标准，研究背景，研究动机以及本文主要工作及创新点，最后阐明了本文的组织安排。第二章：问题建模。本章具体论述了无线充电模型、充电功率及电磁辐射模型、充电效用，最后形式化定义了本文的研究问题，包括目标函数及约束条件。第三章：算法设计。本章提出了求解目标函数的步骤及方法，从区域划分、时间交点划分、解正则化策略的提出到最后求解算法步骤的建立，展示了问题求解的详细过程。第四章：仿真实验。开

33、展MATLAB仿真实验，得到算法的运行结果，验证了算法的可行性和正确性，并设计执行了两种对比算法，得出最终结论。第五章：本文总结与展望。对文章做出总结，在本文基础上，展望未来研究内容的改善方向与提升空间。第二章 问题建模本章具体阐释了传统的经验无线充电模型、充电功率及电磁辐射模型以及充电效用函数，最后从本文具体问题着手，形式化定义了本文的研究问题，包括目标函数及约束条件。2.1 问题初步建模2.1.1充电模型假设在二维平面内，有n个无线充电器，用集合S=s1, s2, s3, , sn表示，有m个可充电设备，用集合O=o1, o2, o3, , om表示。所有的无线充电器都是相同规格的，可充电

34、设备通过接收无线充电器发射的电磁能量进行充电。可充电设备接收到的充电功率从直觉上理解是与其距充电器的距离相关的，即距充电器越近，充电功率越大，反之越小。我们采用经验全方向充电模型 REF _Ref514435992 r h * MERGEFORMAT 11，充电设备oj 接收到来自充电器si的充电功率如下：Psi,oj=d(si,oj)+2, dD0, dD（2. SEQ （式2. * ARABIC 1）可充电设备从充电器接收到的充电功率是Psi,oj，d表示充电设备与充电器的距离，参数和是预定义的常量，与充电器和可充电设备的硬件参数及周围环境因素有关，D表示充电器发射功率到达的距离上限。假设

35、充电器可以从0到一个最大值连续地调节发射功率，定义调节因子xi为充电器si发射功率与最大功率的比值（0 xi1），因此，设备从充电器接收的功率可表示为Psi,ojxi。同时，假设充电功率具有可加性，即可充电设备从多个充电器那接收到的充电功率是可叠加的。2.1.2充电功率及电磁辐射模型由于充电功率具有可叠加性质，因此，充电设备oj接收到的总功率是覆盖其的所有充电器发射功率之和，即：Poj=i=1nP(d(si,oj)=i=1nP(d(si,oj)xi（2. SEQ （式2. * ARABIC 2）其中，d(si,oj)表示可充电设备oj到充电器si的距离。我们采用经验电磁能量辐射模型 REF _

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

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

38、14436054 r h * MERGEFORMAT 13刻画了充电任务获得的一定量能量E的收益，并且通常是凹函数。任务Tj需要的充电能量为Ej，在结束时间tej前获得的能量为E，则充电效用可表示为：UE=1EjE,EEj1,EEj（2. SEQ （式2. * ARABIC 5）2.2.3问题形式化本文研究的是无线充电在线算法的研究，假设充电时间连续，充电器功率可连续调节，充电任务动态到达，因此任务提出的起始点不同。 正如前文提到的，若可充电设备接收到的充电功率过高，会对设备造成不可预估的损害，因此我们约定，对于平面内任一设备oj，其最大接收功率为PjMAX，同时，由于设定的PjMAX值也是综

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

40、 （式2. * ARABIC 6）由于每个充电任务对实际应用的贡献大小是不同的，换句话说即重要程度是各异的，所以对每个任务Tj都有一个权重值j，得到加权后的总充电效用为：（2. SEQ （式2. * ARABIC 7）为了保证冷充电，对于设备oj经过的任一区域x，需满足以下条件：i=1nPsi,pxitPjMAX (px; tT1,T2m)（2. SEQ （式2. * ARABIC 8）最后，我们定义带充电设备接收功率阈值约束条件的无线充电任务在线最优调度目标函数为：P SEQ P * ARABIC 1s.t. i=1nPsi,pxitPjMAX px; tT1,T2m0 xit1. (i=1

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

42、过程。最后定义我们的研究问题为Online Scheduling of wireless Charging tAsks with rEceived Power constraints (OSCAEP)。本章提出了求解目标函数的步骤及方法，展现了求解问题的详尽过程。3.1 集中式在线算法3.1.1 区域划分及问题重构我们首先提出一个分段常数函数来近似非线性功率函数，如下 REF _Ref512543699 h * MERGEFORMAT REF _Ref512543885 h * MERGEFORMAT 图3. 1所示：图3. SEQ 图3. * ARABIC 1功率近似函数函数中分段常量线段在

43、横轴上d对应的端点设为l1,l2,lQ (l0=0,lQ=D)，然后我们以每个充电器为圆心，分别以l1,l2,lQ为半径画同心圆 REF _Ref514435992 r h * MERGEFORMAT 11，这样，对于每个充电器，整个二维平面被划分成许多子区域，设子区域的数目为Z。同理，这些同心圆同样将任务Tj 的发生区域Aj划分成Vj个子区域，即：Ajvv=1Vj。由于在相同的子区域里，经过近似后的每个充电器发射的功率是个常数，那么，每个子区域从附近充电器接收的总充电功率也是常数。下 REF _Ref512543777 h * MERGEFORMAT REF _Ref512543929 h

44、* MERGEFORMAT 图3. 2展示了一个区域划分的例子，通过为三个无线充电器中的每一个绘制半径分别为l1和l2的两个同心圆，整个平面被划分为15块子区域，任务T1和T2的发生区域也被分别划分为子区域A11、A12、A13和子区域A21、A22。下面的定理说明了如何设置l1,l2,lQ的值。图3. SEQ 图3. * ARABIC 2区域划分定理3. SEQ 定理3. * ARABIC 1：设l0=0，lQ=D，lq=(1+q2-1)(qQ-1)，并且使用以下分段常数函数P(d)作为充电功率函数：P(d) =Pl1,d=l(0)Plq,lq-1D（3. SEQ （式3. * ARABIC

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

46、1,T2m)（3. SEQ （式3. * ARABIC 4）相应地，问题 REF _Ref512437632 h * MERGEFORMAT P1的近似版本可重新定义为：P SEQ P * ARABIC 2s.t. i=1nPijvxi(t)PjMAX(v1,Vj;tT1,T2m)0 xit1. (i=1,2,n)其中，Pijv是在子区域Ajv内获得的充电器si的最大近似功率，我们的目标是为所有充电器确定调节因子xit i1,n;tT1,T2m。3.1.2 时间交点划分由于充电时间是连续的，我们构想了时间交点划分算法（Time Intersection pOint Partition，TIOP

47、）来为解正则化做铺垫。充电任务Tj=，trj和tej分别表示任务的提出和结束时间。首先，我们将充电任务Tj的开始时间trj和结束时间tej一起非降序排列，并标记好每个时间点对应的任务标识号，以确保在某一时间段内能够获悉有哪些充电任务在进行。下 REF _Ref512543996 h * MERGEFORMAT 图3. 3给出了一个时间交点划分的例子。从图中我们可以看到时间序列为：Tx=(tr1,tr2,tr3,te1,te3,te2,tr4,te4)，正如前面提到的，ttT1,T2m表示整个调度算法的持续时间，T2m=maxtejj1,m，因此，我们首先将时间序列Tx一一映射为T1T2m，然后

48、将时间序列Tx的每个元素值减去首元素tr1的值，对于 REF _Ref512543996 h * MERGEFORMAT 图3. 3的例子，将Tx=(tr1,tr2,tr3,te1,te3,te2,tr4,te4)映射为T1T8，T1=0，T8=te 4- tr1。从图中可以看到，四个充电任务分别用不同的颜色标注，不同任务的充电时间周期有交叉重叠，而在实际充电中，某些时间点可能相同。图3. SEQ 图3. * ARABIC 3时间交点划分示例图3.1.3算法形式化步骤算法：时间交点划分算法（TIOP）输入：每个充电任务Tj的开始时间trj和结束时间tej输出：时间序列T1,T2,T2m1. 将

49、开始时间序列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. TiTi-T1；7. 将首元素T1的值置为0。8. 输出时间序列T1,T2,T2m。3.1.4 解正则化问题 REF _Ref512437767 h P2的一个关键挑战在于充电器调节因子的随意性，它随时间连续变化。为解决这个问题，我们提出了一个解正则化的方法，下面给出它的规范化定义：定义3. SEQ 定义3.

50、 * ARABIC 1：（解正则化）对于问题 REF _Ref512437767 h P2的任意可行解xit i1,n;tT1,T2m，在时间段Tk-1 Tk (k=p,p+1,q-1,q;qp; T1=0)内，它的正则化形式定义为：xi,k=Tk-1TkxitTk-Tk-1(kp,q)引理3. SEQ 引理3. * ARABIC 1：对于问题 REF _Ref512437767 h P2的任意可行解，它的正则化形式仍然是可行的，并且完成相同的充电效用。证明：首先，我们证明正则解对于 REF _Ref512437767 h P2是可行的。从问题 REF _Ref512437767 h P2的定

51、义，给定一个可行解xit i1,n，则有i=1nPijvxi(t)PjMAX(v1,Vj)。对于tTk-1 Tk)，i=1nPijvTk-1Tkxi(t)Tk-1TkPjMAX=(Tk-Tk-1)PjMAX，因此，i=1nPijvTk-1Tkxi(t)Tk-Tk-1=i=1nPijvxi,kPjMAX。由于0 xi(t)1，很明显，0 xi,k=Tk-1TkxitTk-Tk-11，因此，xi,k是问题 REF _Ref512437767 h P2的可行解。然后，我们证明正则解可以达到相同的目标效用。对于设备oj，它在时间Tp,Tq获得的充电功率为：TpTqi=1nPijxitdt=i=1nPi

52、jk=pqTk-1Tkxitdt=i=1nPijk=pq(Tk-Tk-1)Tk-1Tkxi(t)Tk-Tk-1dt=i=1nPijk=pqTk-1Tkxi,kdt因此，我们可以得到：下 REF _Ref512544074 h * MERGEFORMAT 图3. 4展示了一个正则化的例子，原始解x1(t)和x2(t)由淡蓝色和浅绿色实线表示，它们相对应的正则化形式分别由淡蓝色和浅绿色虚线表示。这里时间片有三段，对应地，每一个正则化形式有三段，它们在时间段0 T1)，T1 T2)，T2 T3)的值是常数。图3. SEQ 图3. * ARABIC 4正则化示例由 REF _Ref512439168

53、h 引理3. 1得知，任意可行解都等价于它的正则化形式，因此，我们只需要考虑解的正则化形式，因而，问题可以重写为问题 REF _Ref512438618 h P3：P SEQ P * ARABIC 3max xi,kj=1mjv=1VjPrAjvU(i=1nPijvk=pq(Tk-Tk-1)xi,k)s.t. i=1nPijvxi,kPjMAX0 xi,k1. (i=1,n;kp,q)3.1.5 概率分布函数的二重积分化解问题是双重积分问题，不易求解。就此，我们先来讨论PrAjv的几何意义，被积函数j表示任务Tj发生在位置p的可能性，积分区域是任务Tj可能发生的位置区域，那么PrAjv的几何意

54、义相当于可能发生的子区域面积占总区域面积的比例。既然知道PrAjv的几何意义，问题就转化为求任务Tj可能发生的相应子区域的面积，我们采取“撒点法”来计算，计算后的结果定义为Arjv=PrAjv，则问题 REF _Ref512438618 h P3重写为 REF _Ref512438693 h P4：P SEQ P * ARABIC 4max xi,kj=1mjv=1VjArjvU(i=1nPijvk=pq(Tk-Tk-1)xi,k)s.t. i=1nPijvxi,kPjMAX0 xi,k1. (i=1,n;kp,q)3.1.6 问题最终转化问题 REF _Ref512438693 h P4不能

55、直接被求解，因此，我们将它转化为线性规划问题。引入辅助变量yj，则问题 REF _Ref512438693 h P4重写为：P SEQ P * ARABIC 5max xi,k,yjj=1mjyjs.t. i=1nPijvxi,kPjMAXyjv=1VjArjvUi=1nPijvk=pq(Tk-Tk-1)xi,k0 xi,k1. (i=1,n;k=1,q)注意xi,k(i=1,n;kp,q)和yj(j=1,m)是决策变量。3.2算法求解3.2.1算法描述我们提出了一种集中式的算法来求解问题 REF _Ref512545769 h P5。所谓集中，就是收集全网所有充电器和充电设备的相关信息，集中

56、处理数据和散播处理结果。首先证明对于任意0，我们的算法的近似比至少为1-，它的时间复杂度为O=(n4.5m5.5)，n和m分别表示充电器和充电设备的数目。证明：首先，解正则化方法同样适用于问题 REF _Ref512437632 h P1，因此，问题 REF _Ref512437632 h P1可以等价表示为：(P1)s.t. i=1nPsi,pxi,kPjMAX px; kp,q0 xi,k1. (i=1,2,n)设问题P1和问题 REF _Ref512545769 h P5（或 REF _Ref512438693 h P4）的解分别是xi,k*和xi,k*，接下来我们证明(1-)xi,k*

57、同样适用于问题 REF _Ref512545769 h P5。考虑平面上的任意一点p，经过区域划分后p必位于一子区域Ajv，即pAjv。根据 REF _Ref512544299 h * MERGEFORMAT 式3.2，我们得出：1-PpPp=i=1nPijvxi,ki=1nPsi,pxi,k，因此，可以得到结果i=1nPsi,pxi,k*(1-)i=1nPijvxi,k*PjMAX，这表明(1-)xi,k*同样适用于问题 REF _Ref512438693 h P4，因此其解为(1-)xi,k*的充电总效用为：max xi,kjmjv=1VjArjvU(i=1nPijvk=pq(Tk-Tk-

58、1)(1-)xi,k*)(1-)Umax因此，证明我们的算法至少完成了(1-)的近似比。接下来，我们简要分析提出的算法性能。根据已有几何学知识，计算交点的子区域数目Z=On2-2，由于每个充电任务也有充电子区域，因此Z=Omn2-2，这是区域划分部分的时间复杂度。求解问题 REF _Ref512545769 h P5线性约束的时间复杂度为C=O(mnq)（q是时间片个数），而q=O2m=O(m)，因此C=Omnq=O(nm2)。利用Karmarkar算法 REF _Ref514436079 r h * MERGEFORMAT 14求解线性规划，时间复杂度为Onm3.5C=O(n4.5m5.5)

59、，因此，最终算法的性能为O=(n4.5m5.5)。3.2.2算法形式化步骤我们提出了集中式线性规划算法（Centralized Algorithm with Linear Programming）来求解问题 REF _Ref512545769 h P5，具体步骤如下：算法：集中式在线性规划算法（CALP）输入：充电模型参数、最大充电距离D，近似误差，时间序列T1,T2,T2m，需要的充电能量Ej，每个可充电设备oj接收能量的阈值PjMAX。输出：充电效用Umax，调节因子xi,k1. 根据充电模型参数、最大充电距离D，近似误差进行区域划分；2. 计算区域划分后每个子区域和每个设备处的近似功率；

60、3. 设置求解线性规划方程需要的不同参数；4. 利用线性规划方程求解问题 REF _Ref512545769 h P5，得到最优的充电效用Umax；5. 输出最优充电效用Umax和调节因子xi,k。3.3 本章小结本章给出了求解目标函数的规范化流程，依次阐明了区域划分离散化近似、常数求解的过程；时间交点划分为规范化求解做铺垫；解正则化将问题的解规范化为可计算的形式的策略方法，最终详述了算法步骤。第四章 仿真实验本章，我们通过开展MATLAB仿真实验来模拟实际充电场景，验证我们提出的算法的性能。在此基础上，我们将本文提出的算法CALP分别与GREEDY算法和TOMLAB的CONOPT算子进行对比