ICDE 2024 | EcoCharge：基于估算成份的电动汽车充电桩的连续kNN排序框架

时空实验室 2024-04-22

168

基于各种方法优化利用可再生能源(RES)对电动汽车(EV)充电的研究，是当前一个重要的研究领域。然而，目前还没有其他研究专注于可持续的EV能量囤积。本次为大家带来国际数据库顶级会议ICDE上的论文《A Framework for Continuous kNN Ranking of EV Chargers with Estimated Components》。

一. 背景

近年来，人们对将可再生能源（RES）与电动汽车（EV）充电基础设施进行整合的兴趣日益增加，例如光伏电池板、风力涡轮机等。人们倾向于在闲置时间对EV充电，即使电池没有大量耗尽，也要确保车辆在出行时拥有充足的电量，这被称为能量囤积的习惯。EV被视为改善环境和减少温室气体排放的一种方式，使用非可再生能源进行能量囤积抵消了环境效益。可再生能源囤积技术可以适用于闲置时间的场景（当EV用户在等待或停放时）。例如以下场景：（i）电动出租车在闲置时等待接单或在线预订；（ii）父母在他们的EV中等待，而他们的孩子参加课后活动；（iii）EV用户去购物或购买服装，这时希望停放车辆的位置可以充电。因此，用户可以在附近一些充电站停车或改变路线，以有效地使用可再生能源来为他们的EV充电，减少碳足迹。

这项任务面临的挑战是：在哪里可持续进行能量囤积的决策取决于一系列估算成分（ECs），包括何时何地充电。这些估算成分包括：到达充电桩的绕路，取决于估算的交通情况；充电桩上可用的清洁电力，取决于估算的天气；以及充电桩的可用性，取决于估算的繁忙时间表，显示充电桩何时拥挤。在这样一个动态的背景下，传统的索引方法可能不是最合适的解决方案。

论文提出了带有估算组件的连续k最近邻查询算法（CkNN-EC）, 可以有效找到每个时间戳上移动对象的最近EV充电桩，这基于一个预定的行程，同时考虑一系列估算成分。并且设计了EcoCharge，这是一个创新的可再生能源囤积应用程序，用于城市环境中的EV充电，集成了CkNN-EC和动态缓存技术，以最小化绕路成本并最大化可持续充电水平，实验结果表明EcoCharge可以成为未来绿色出行的基础。

二. 相关定义与问题表述

2.1 符号表

符号	含义
b,B	电动汽车充电桩b，所有b的集合B
m,M	电动汽车m，所有m的集合M
p,P	p是行程P的一个路径段，P是一次预定的行程。
G	路网（由V个节点和E条边组成）
O	排名靠前的电动汽车充电桩提供表
L	可持续充电水平
A	充电桩的可用性
D	绕路行驶距离（从m到b的距离）
t	时间（例如，预计到达时间）
s	太阳光伏发电量
Ft	CPU执行时间

2.2问题表述

论文将问题建模为一个新的CkNN-EC查询，该查询通过采用可以表达模糊值的距离函数来检索路径段上每个点的k个最近邻，同时考虑一系列估算成分。假设B是一个道路网络上的EV充电站数据集，其中CkNN-EC查询检索路径P的每个路径段p的最近邻（例如k=1），其结果是一组<b，p>。如图1所示，其中B={b1，...，b20}，考虑路径P并强调沿着最终目的地方向移动，查询的1NN结果是{<b7，p1>，<b3，p2>，<b3，p3>，<b1，p4>，<b4，p5>，<b5，p6>，<b5，p7>，<b5，p8>}，即充电桩b7是路径p1段的最近邻。论文的方法利用了与天气预报、绕路成本和充电桩可用性相关的预测模型，路段内（即（xs，ys），...，（xe，ye））发生邻域转换的点称为分裂点SL。EcoCharge应用程序的目的是优化一个目标函数，以在车辆的可持续充电水平L、充电桩的可用性A和绕路成本D之间取得平衡。

图1 示例场景

三. 方法介绍

3.1 EcoCharge效率衡量指标

(1)可持续充电水平(L)

每个b的充电速率和功率生成水平st根据时间和位置而异。L包括一个下限和上限估算值，最终结果是一个区间Lmin到Lmax。论文通过将这些值除以环境的最大充电水平值来对这些值进行归一化：

(2)可用性(A)

为了能够确定在给定时间t的实时可访问性，每个EV充电桩的可用性是使用某些第三方服务（例如，Google地图POI繁忙时间表）进行估算。论文将这些值表示为百分比，其中0%表示不繁忙，100%表示繁忙：

(3)绕路成本(D)

从起点v0到目标充电桩vk的路径是节点序列P = <v0，v1，...，vk>，其中w表示边缘的权重，以CO₂排放（例如，或kWh消耗）表示。如果需要避开以到达所选充电桩，则将CO₂排放分别添加到总计算的行程成本中。如果充电桩位于预定行程的路径上，则不会绕路，因此不会额外添加CO₂排放。此外，绕路行程准确考虑了从云地理信息系统（GIS）服务（例如Google地图）检索到的给定时间和位置的实时交通信息（例如拥挤情况）。因此，D包含下限和上限估算值，论文通过将这些值除以环境的最大绕路距离来对这些值进行归一化。路径P的段p到所有充电桩B的最小绕路成本为：

(4)可持续性评分(SC)

论文将SC评估为加权和函数，其中w1是L目标的权重，w2是A目标的权重，w3是D目标的权重。这些权重是可配置的，可以根据用户的个人偏好和优先级来定制决策过程。使用以SC为距离函数的CkNN，EcoCharge生成两个结果集，一个基于SCmin，另一个基于SCmax，最终输出是它们的交集，其中包含k个充电桩。

3.2 EcoCharge算法

算法1 EcoCharge算法

如算法1所示，为了连续监控kNN的结果，CkNN-EC方法需要将整个路程分段（第2行），这些段依次用于确定查询对象的kNN。所有充电桩与查询对象之间的路网距离必须在查询对象到达预定行程的段交叉点SL时更新。对于每个段pi，查找kNN的过程由两个阶段组成。
（1）过滤阶段：

根据驾驶员的位置（例如段pi），过滤过程确保仅考虑最合适的k个充电桩，同时剪枝所有其他充电桩。特定阶段循环遍历整个EV充电桩池，并基于多个估计成分检查每个充电桩。第一个成分是L，考虑到给定时间的充电速率和功率生成（5-6行）。由于天气条件可能随时变化（例如，晴朗的天空在10分钟内变为多云），因此还考虑了上限和下限估计。第二个成分专注于根据ETA估计的A，分析了EV用户预计何时到达充电站，从而估计潜在的高峰使用时间，并确保充电桩可访问。第二个成分与前面的情况类似，生成具有上限和下限可用性值的区间（7-8行）。最后一个成分是绕路成本（D），它计算到达充电站和返回预定行程所需的距离和时间。返回阶段回到相同的段p_i，也可以是下一个段（即pi+1），由于交通条件和意外情况的变化，考虑了下限和上限估计值（9-10行）。

（2）细化阶段：

在这个阶段，池中被筛选的候选充电桩中的每个充电桩都经另一个评估以评估其适用性。评估通过以下方程进行：

该方程利用可持续性得分SC的最小和最大区间值的交集（16行）。随后，一个可持续性函数对结果进行排序（17行），以确保只识别出最相关和最有效的充电站，为用户提供优化的可再生存储策略。

图2所示场景，其中车辆m正在进行预定行程P（由几个路径段pi ∈ P组成），并且有20个EV充电桩b1, ..., b20。假设1小时行程的天气预报为晴天，这意味着EV充电站产生可持续能源。用户希望在时间戳10:15am时访问一个充电站来为其EV充电。基于用户的当前位置、充电站b的天气条件下的可持续充电水平L、b的可用性A以及到达b的绕路成本D，决定在何处充电。为简单起见，在这个例子中不考虑任何权重。考虑到10:15am时车辆位置和路径段p4的最近充电站，有几个选择：（i）充电桩b1可用，绕路成本为D_b₁= -2kWh，而可持续充电增益为L_b₁= +9kWh，即SC_b₁= +7kWh；（ii）充电桩b2可用，绕路成本D_b₂= -1kWh，而可持续充电增益为L_b₂= +4kWh，即SC_b₂= +3kWh；和（iii）充电桩b3可用，绕路成本为D_b₃= -2kWh，而可持续充电增益为L_b₃= +4kWh，即SC_b₃= +2kWh，最后路段的排序如下<b1, b2, b3>（从高到低）。

图2 在P的p中选择b的示意图

3.3 EcoCharge架构

系统的核心位于一个由集中式服务器支持的EcoCharge客户端，该客户端与外部API交互以检索必要的数据（见图3）。借助外部API，EcoCharge信息服务器（EIS）获取实时天气预报数据、详细的路网信息以及基于用户位置的所有可用EV充电站的列表，通过使用智能缓存机制来减少对冗余API调用的请求。该服务可以以三种操作模式提供给用户：（i）Mode 1，EcoCharge在车辆的嵌入式操作系统中运行（例如，汽车操作系统，大众汽车操作系统）；（ii）Mode 2，EIS集中进行EcoCharge计算；和（iii）Mode 3，EcoCharge功能由边缘设备管理（例如，使用Android Auto或Apple CarPlay的智能手机）。

图3 EcoCharge架构

3.4 动态缓存

EcoCharge采用了一种动态缓存方法，通过将问题分解为更小、更简单的子问题，并仅解决每个子问题一次来适应。它将解决方案（即提供表）和API响应存储在表中，并使用它们来解决类似的问题，直到完全解决整个问题。优势在于能够避免冗余计算并通过重复使用已生成的解决方案来降低问题的总体复杂性，从而实现显著加速。论文采用了自下而上的方法来解决各个子问题，并将它们的结果存储在一个表中，然后可以使用这些结果来解决未来的查询。

图4 动态缓存（自下而上）

如图4所示，EV户在具有多个充电站B的路网中的当前位置p_i。EcoCharge通常会开始计算每个充电站的可持续性得分SC_b（即解决子问题），以形成基于用户位置的提供表O₁。O₁包含按可持续性得分排序的最佳充电站，优先考虑得分最高的充电站。然后，根据预定行程，按照驾驶员的下一个位置p_i+₁，将需要解决一个新的问题。考虑到上一个位置和当前位置之间的距离，可以重新应用已计算的解决方案来解决更大的问题。因此，论文使用半径参数R，允许用户在他们期望的地理半径内收到电动汽车充电桩，并且使用参数Q指示用户从上一个位置到当前位置的首选距离，以便获取服务器更新和计算新的解决方案。通过这种方式，算法不需要在每个新的路径段中循环遍历充电站的整个搜索空间，如果先前的电动汽车位置的要求与R和Q参数匹配，则O₁可以调整为O₂，直到用户的最终目的地。

四. 实验

4.1 实验设置

数据集：实验采用4个轨迹数据集Oldenburg（合成数据集）、California、T-drive和Geolife。Oldenburg包含德国Oldenburg市45km x 35km区域内的4,000条车辆轨迹；California包含美国加利福尼亚州1,220 km x 400 km区域内的7,000条车辆轨迹；T-drive包含2008年2月2日至2月8日期间在中国北京市行驶的10,357条出租车轨迹；Geolife包含17,621条各种类型和采样率的轨迹。

实验环境：实验在Ubuntu服务器上进行，配有6GB的内存、4个虚拟CPU(@ 2.60GHz)和10K RPM RAID-5 LSILogic SCSI磁盘。

指标：可持续充电水平（L）、可用性（A）、绕路成本（D）和 CPU执行时间（Ft）。

对比方法：Brute-Force、Index-Quadtree和Random。

4.2 实验结果

4.2.1 性能评估

如图5示，EcoCharge在保持高可持续性得分的同时实现了更快的执行速度，通过优化用户配置参数和智能继承现有数据，EcoCharge成功平衡了绕路成本、可用性和可持续充电水平，为EV车主提供了更快、更准确的结果。

图5 性能评估

4.2.2 不同半径(R)下的性能评估

如图6所示，较低的半径(R)导致更快的执行速度，但与较高半径值相比，可持续性得分逐渐降低。不同数据集表现出相似的趋势，用户可以根据个人偏好和需求，选择是否愿意花费更多时间以获取更多的充电器选择。

图6 EcoCharge的R-opt评估

4.2.3 不同距离范围(Q)下的性能评估

如图7所示，当配置的距离范围较长时，执行时间略微加快，但与较短距离范围相比，可持续性得分逐渐下降。不同数据集表现出相似的趋势，选择适当的距离范围值对于在执行速度和可持续性得分之间进行权衡至关重要。

图7 EcoCharge的Q-opt评估

4.2.4剔除研究

论文对EcoCharge算法进行了权重参数的剔除研究，针对不同距离函数进行了评估。图，将所有权重视为相等（AWE）的配置优于其他距离函数，在可持续性得分（SC）方面表现最佳，约为97.5-99％。与其他距离函数相比，AWE配置在各个权重参数上都取得了平衡，这突显了权重配置对系统性能的重要性。结果表明，不同权重参数之间存在明显的相互作用，系统的性能对权重配置非常敏感，因此微调这些权重对于优化EcoCharge的操作至关重要。