基于多级反馈队列调度的电动汽车充电模型及其云实现

2016-11-14任旭,高晶晶,艾明浩等

中国科技信息 2016年21期

充电汽车的普及和推广，使人们在日常出行方面减少了化石燃料的使用，从一定程度上解决了能源短缺和大气污染的问题，但同时也造成了大规模充电行为对电网产生的巨大冲击，影响了电网的稳定运行。文章借鉴计算机操作系统任务调度算法，提出一种考虑到电网侧负荷以及充电公平性的多级反馈队列优化充电模型。电动汽车在关注的电网中按照以上提出的充电方案来进行充电，既没有违背公平原则，又实现了最优化充电，同时保证电网安全稳定运行，降低了资源浪费。电动汽车充电过程中涉及到了多方面的异构化信息，其中包括车联网、智能电网、充电设备网络和额外的有关信息。而以上模型的实现需要把多方面的数据信息加以融合，并且要解决海量数据带来的大数据处理问题。本文提出的电动汽车充电模型利用Hadoop云计算平台来解决大数据集的并行化计算问题，使用HDFS分布式文件系统和HBase非关系型数据库解决海量数据的存储问题。

当今社会对煤、石油、天然气等传统化石能源拥有巨大的需求，但是越来越严重的环境问题和能源紧缺，迫使公众亟待寻找一种可以节省能源并且环保可靠地交通工具，而电动汽车的出现解决了这一问题。但是大规模电动汽车在同一时间段集中充电将带来新一轮的负荷增长，尤其是电动汽车在高峰期充电将进一步加剧电网负荷峰谷差，将会对配电网的运行造成严重影响，包括电压跌落、线路或变压器负荷超载、加大损耗风险。另外，电动汽车对电网造成的叠加负荷也同时表现出随机性和分散性，使得调控电网变得更加复杂。因此，为了保证电网运行的稳定性，降低能源浪费以及达到效益最优化，对于电动汽车的充电行为模式进行优化是有必要的。

确定最优充电模式的唯一途径是综合考虑充电设备（包括充电站和充电桩）和充电汽车两方面的数据信息，并且对所有数据进行统一分析和处理。近年来，根据侧重点的不同，不同的研究机构和人员研究、比较了多种不同的充电模型。从研究层面上来划分的话，可以分为以下几个方面：1）单一电动汽车充电控制； 2）同一充电站多充电目标集中充电处理； 3）区域内多个站的电动汽车协调充电控制。文献针对有序充电的策略方法，归纳为基于最优经济运行的充电模型、最优市场机制和商业运营模式、时空有序性3类方法；文献提出一种基于电网负荷的有序充电控制模型，进行实时有序控制，提高了电网的安全性；文献在考虑电动汽车的充电功率、充电时间以及变压器可用容量等约束条件的前提下，提出基于多智能体协同控制的电动汽车充电优化策略；文献将电动汽车看成一个小型“集聚体”，以有功网损最小为目标函数，计及节点电压、线路潮流、配变容量、集中式充电功率的动态爬升约束以及充电能量平衡约束，提出基于配电网安全运行的充电优化问题模型；文献提出了一种基于分布式控制的电动汽车有序充电控制模型，并给出了分布式有序充电控制的优化计算方法；文献通过网格选取法，考虑到配电变压器的供电容量，从时间和功率两个维度来控制电动汽车的充电行为。但目前还未存在一种综合考虑电网和用户多种因素及优先级的充电方案，更无有效的算法实现此类充电方案。

为了得到多种优化方案，需要统一电网、充电设备和电动汽车三方面的数据信息，并进行有效的分析处理。伴随着电动汽车保有量的提升，为了满足充电需求，充电站和充电桩必将会在电网内增加负荷接入点，这样一来会造成各种异构化数据激增。云计算平台能够高效地采用集群化并行处理技术来解决海量数据的分析处理。实现区域电网内电动汽车优化充电需要综合考虑电网侧、用户侧多方面因素，结合多种经典优化算法，利用多维信息融合处理技术，本文提出了一种基于多级反馈队列的电动汽车优化充电模型，并阐述了在云计算平台对该模型的实现过程。

电动汽车多级反馈队列充电模型

模型需求目标分析

充电汽车的充电行为主要包含了三个行为主体：电网、充电汽车和充电代理商。三者之间的交互包含了能量和数据两种交互信息。要提出最优化的充电模型，需要处理好三个关系：一是政府、企业和市场的关系；二是产品、基础设施和商业模式的关系；三是汽车的使用者、电力企业和充电代理商的关系。对于汽车的使用者，重点是关注充电电价、充电耗时以及充电是否方便等需求；对于后两者，重点是关注电网运行的安全性和稳定性、是否符合公平性原则以及电能是否充分利用。保证用户公平性是充电服务最重要的目标之一，关系到电能有序利用的实施效果。公平性原则是为了满足电动汽车用户有突发性充电需求，避免了电能不能补充的情况。而保证电网稳定运行和提升能源利用率，又是对充电进行优化的最终目标。因此，最优充电模型应该关注排队早、时间要求迫切、充电时间长的充电汽车首先充电。并且在充电过程中，要实时地进行策略调整来满足各方的不同需求。这里综合考虑多方面关系，根据各方需求，建立区域电网内多级反馈队列优化充电模型。

基于多级反馈队列的优化充电模型建立

在计算机操作系统中，有一种作业调度的应用场景：在同一时刻，大量作业同时请求有限资源，系统如何调度从而为作业有序地分配资源。参考作业调度的工作流程，可以用类似的方案处理电动汽车充电的工作任务。在满足公平性原则的前提下，将每一次的充电行为看做是一个调度任务，相对应的电力能源就是资源。模型的最终目的是得到最优的任务执行序列，来达到较高的电力能源利用率以及最小的电网负荷。

多级反馈队列进程调度算法为了保证公平性和较高的资源利用率，采用了基于高优先级优先调度和时间轮转片轮转调度算法，在处理过程中不断进行调整。在本文提出的电动汽车充电模型中，根据排队时间长短、充电时间长短、充电时间紧迫性以及已经等待的时间等指标来定义任务的初始优先级。然后把充电的全部过程切成等长的时间，不同的任务队列对应的单条时间长度可以不同。每个单独的时间充电完成以后，调整优先级，然后根据调整后的优先级进行任务调度。

图1为多级反馈队列优化充电模型整体架构图。

多级反馈队列优化充电模型调度算法分为以下步骤：

1）在考虑了任务时长、已经排队时长以及用户紧迫度等因素以后，对可以参与有序充电队列调度的充电任务计算对应的任务优先级。本文依据响应比算法，以充电紧迫程度为优先级，提出公式（1）作为优先级计算公式。

公式中，T表示完成充电所需的剩余时间，W表示已经排队时长，TC表示当前时间，TU表示用户设置的充电任务截止时间（即取车时间）。（TU-TC）-T表示距离任务截止的时间和剩余任务所需要的时间之差，用来表示当前用户充电任务紧迫程度。对于等待而未充电的用户，其剩余充电所需时长T为固定值，而W即等待时间逐渐增大，因此响应比会增加；对于正在充电的用户来说，其一开始等待的时长W已经为定值，而剩余充电所需时长T则逐渐变小，因此响应比会降低。对于公式分母部分，无论等待充电还是正在充电的用户，随着时间的推移，距离设置的充电结束时间值越近，TU-TC越小，代表任务越紧迫，其响应比也就越高。而分母增加-T则是为了保证充电能够完整的进行，因为若到了距离结束时限的时长无限接近于充电时长T还未开始充电，则（TU-TC）-T无限接近于0，整个响应比会无限大，使优先级达到最大。

2）根据优先级，设置多级队列。根据优先级确定各个任务执行的先后顺序，同时依据优先级的大小分到若干不同等级的任务队列当中。不同等级的队列对应不同大小的时间片，时间片长短和队列的优先级成反比。

3）首先，按照优先级从高到低的顺序选择队列中的充电任务开始执行，每次时间片执行完毕，需要再一次计算来确定各个任务的优先级，并以此为依据，再次分配充电任务到不同的队列中。

4）只有当优先级最高的队列中的任务完成以后，才处理优先级次一级的队列中的任务。

图2和图3分别为车辆接入流程和车辆充电流程。其中，车辆接入流程为事件驱动型，即车辆接入事件激活流程，将充电任务存入充电优先队列；车辆充电流程为时间驱动型，即时间片不断轮转，每次时间片轮转结束时，从优先级队列中取出任务进行充电，并重新计算优先级队列。

以上提出的基于多级反馈队列实现的充电模型，在保证电网稳定运行的基础上，同时兼顾了每一个用户的实际充电需求，达到了不同用户之间的公平。

图1 多级反馈队列优化充电模型整体架构

图2 车辆接入流程

图3 车辆充电流程

基于云计算平台的多级反馈队列充电模型MR算法实现

区域电网电动汽车多信息源融合问题分析

实现多级反馈队列充电模型需要考虑到以下几个方面：充电汽车、充电用户个人、充电站以及电网负荷等多方面的数据信息。在处理充电任务时，需要综合分析多方数据，不可避免的会遇到以下问题：

1）综合分析多方数据时遇到的异构数据问题。

2）电动汽车和充电设备（包括充电站和充电桩）分散性较强，并会产生海量数据，这些数据的存储问题需要解决。

3）实现模型计算时需要考虑到多种因素，最终得到最优方案，这导致分析计算复杂，计算量巨大。

4）充电方案的生成需要具有时效性，充电用户提交的充电需求应该迅速得到反馈。

综上所述，在处理电动汽车充电任务时所遇到的问题呈现出数据量大，处理时效性强等特点。想要解决以上问题，需要使用云平台实现对大数据的处理。Hadoop是一个能够对大量数据进行分布式处理的软件平台，实现了MapReduce编程模型和HDFS分布式存储架构。对于电动汽车充电任务而言，MapReduce模型实现了海量数据计算的并行化处理，HDFS存储结构解决了充电任务过程中需要存储的多方信息分散化的问题，并保证了数据的统一管理。

基于Hadoop的多级反馈队列优化充电模型系统架构和平台搭建

基于Hadoop的多级反馈队列优化充电模型系统架构如图4所示。

在实现模型系统时，按照逻辑层次的划分，主要分为以下几个部分：

1）物理层：其中包括实际的计算机服务器、虚拟机集群、计算机通信网络共同组成的服务器集群。

2）数据储存和基础计算层：是实现Hadoop云计算平台的关键部分。通过和物理层的数据联系，搭建了云计算平台最主要的三个部分：HDFS、HBase、MapReduce。

3）高级计算层：是更高级业务计算的处理部分，已经存储到数据储存层的数据通过数据总线提交到这一层，同时通过基础计算层提供的接口来实现复杂的计算模型。

4）业务交互层：实现平台业务对用户的可视化展示并提供用户操作服务，交互手段包括Web应用和手机App。

5）调度控制层：实现了平台各个模块之间的控制管理，可以提供平台业务功能模块控制、平台服务器间工作负荷调整以及日志管理等功能。

6）消息数据总线：为平台不同模块之间的数据和信息交互提供了通道，对平台各个模块进行了解耦合，为平台提供了良好的可扩展性。

平台软硬件环境配置如表1所示。

图4 多优化充电系统架构

表1 软硬件平台

在集群上搭建Hadoop-1.1.2内核的云计算环境，其他组件版本为JDK-1.7.0_67，HBase -0.94.11。

基于HBase的分布式存储结构

基于多级反馈队列的充电模型采用非关系型数据库HBase，因为HBase可以实现对充电任务中海量数据的存储并且提供对这些超大数据的快速索引。另外，HBase对Hadoop也有很好的支持。根据HBase具有的延展特性和非关系特性，在设计存储数据库的时候，主要创建了两个层次的数据表：第一，包含了多种电网侧基础数据（包括充电设备信息、电网负荷信息等）的基础数据表；第二，记录了从用户创建充电任务开始与之相关的需求和操作信息的充电任务表。

在HBase数据库中，表的结构是由RowKey、列族、时间戳和Cell组成的。表2和表3分别为两张表的基础结构，由于空间关系，未列出具体列键信息。

表2 基础数据表结构

表3 充电任务表结构

基于MapReduce的模型并行化算法实现

多级反馈队列充电模型的M-R算法按照MapReduce机制分为Map阶段和Reduce阶段，依据框架接口设计Map函数和Reduce函数。模型中各个充电任务的优先级是由Map函数计算得来的，而通过比较优先级得出多级反馈队列由Reduce函数完成。这个算法包含一个二次排序过程，将各个充电任务按照优先级进行排序，使传入Reduce的是已排好序的任务，从而提升效率。模型的实现过程如表4、5、6所示。