基于物联网与GS算法的电动汽车充电推荐系统

赵雅兰，张大波，李鸿尧

（辽宁大学 信息学院，辽宁 沈阳 110031）

0 引 言

在科技发展和绿色经济的推动下，我国的电动汽车行业如雨后春笋进入高速发展时期。电动汽车有效解决了日渐枯竭的自然资源与经济可持续发展之间的矛盾。电动汽车逐渐走进千家万户的同时，电动汽车充电所引发的“里程焦虑”（range anxiety）问题也逐渐显露出来。本文基于物联网技术并运用博弈论中的盖尔-沙普利算法（Gale-Shapley algorithm, GS）为电动汽车用户与汽车充电站提供最佳的选择方案，在保证充电站吞吐量的同时，解决车主“里程焦虑”的痛点。

1 国内电动汽车发展现状

1.1 电动汽车充电现状

数据表明，我国电动汽车的销售量从2010年的不足1万辆一跃增长到2020年的136.7万辆，2020年的电动汽车销售量占全球电动汽车销售量的41%。我国新能源汽车市场呈现良好的发展态势。2019年电动汽车的平均续航里程为362千米，现在也有超长续航的电动汽车亮相于大众视野，例如，2020年比亚迪公司推出的“比亚迪汉EV”最长续航里程可达605千米。而电动汽车平均充满电的时间需要花费2小时，“比亚迪汉EV”充电至电池的80%，也需要0.42个小时。相较于传统的燃油汽车几分钟加油时间可以续航600多千米来说，电动汽车确实有着明显的短板。而就目前的充电桩数量和普及程度来看，与电动汽车配套的基础设施建设尚属不完善阶段。

1.2 现阶段存在的问题

由于电动汽车存在充电相对较慢的技术壁垒和当下基础设施建设不完善的现状，电动汽车用户都会在自己的电动汽车电量低于某一阈值时产生对电车电量耗尽的恐惧，称为“里程焦虑”。而反观充电站，其在运营过程中，会有大量的电动汽车进行充电，由于没有加油站那样高效的吞吐量，电动汽车的充电站常常会有众多车主排长队等候充电，这对于驾驶员以及充电站附近的交通来说都是难以忍受的。

现阶段，有很多的充电站或充电桩没有连接物联网，驾驶员无法得知这些充电站的基本信息。而对于一些已经联网的充电站，虽然可以实时显示站中充电桩的使用情况，但也有可能发生在驾驶员将电动汽车开到充电站时充电桩都被其他车辆占用的情况，驾驶员若想在此充电站充电则要花费很长的时间排队等候。即便有了预约系统，可能会出现充电站中有空闲的充电桩，但由于充电桩已被预约，急需充电的汽车充不上电的情况。

2 解决方案

针对以上问题提出电动汽车选择充电站的推荐系统，该系统将更多的充电站（充电桩）和电动汽车进行信息整合，采用窄带物联网技术（Narrow Band-Internet of Things, NB-IoT）进行联网，获取充电站中充电桩的使用情况、站中预约汽车数量的实时情况和电动汽车电池使用情况的数据等。这些数据上传到云端后，根据用户的选择、当前电池电量可以承载的里程、是否顺路等情况得出各个电动汽车选择充电站的偏好，根据当下充电站可以承载的充电数量、完成预约充电的时间，以及电动汽车可以到达充电站且上一辆电车正好完成充电等因素得出充电站选择汽车的偏好。在云端将两方的偏好用GS算法进行计算，可以得到既能使电动汽车最快充上电，也能使充电站实现利用率最大化的一种分配方案，并将该方案实时传送到电动汽车的应用程序和充电站的管理系统中。

3 系统架构

本文提出的电动汽车充电推荐系统的体系架构如图1所示。

图1 电动汽车充电推荐系统体系架构

该体系架构由安装在汽车和充电站的NB-IoT、用于传输数据和实现推荐算法的业务处理云主机以及用来接收信息实现人机交互的充电站、电动汽车和各手机终端三个部分组成。

3.1 NB-IoT终端

在电动汽车、充电站中和充电桩上安装物联网的微控制器，可以进行汽车的数据采集、数据的基本运算以及数据通信。其中的数据的传送采用NB-IoT技术，具有低功耗、覆盖广、速度快、成本低等优点，非常适合这个场景。

3.2 基站和云服务器

NB-IoT基站是基于NB-IoT协议用于信息中转的信息传送系统。汽车和充电站将实时的状态信息传送到附近的基站，基站通过NB-IoT网络将信息传送到业务处理云主机，在云端的服务主机通过优化的GS算法，得出在电动汽车可以快速排队的同时也能实现充电桩高效利用的最优解，将这个最优解记录下来，并将输出结果通过NB-IoT网络传到之前需要预约的车辆、充电站或者其他人机交互终端的附近基站。

3.3 人机交互各终端

人机交互各终端通过接收云端的业务处理主机传送来的数据，进行数据的展示。此时云主机可以对外提供数据获取接口，各个应用程序在获得数据后，可通过浏览器、APP、小程序或车载应用等完成人机页面的互动。

4 推荐系统中GS算法的应用分析与系统实现

根据电动汽车对于充电站的偏好和电动汽车目前的车况，通过云主机获得当前电动汽车对各个充电站的喜爱度偏好排行。而对于充电站，依照当前的路况信息、本充电站当前所承载的充电压力以及可以完成预约充电的时间等条件获得充电站选择汽车的偏好排名。在云端的处理服务器，合理处理两类偏好，计算得到最佳的汽车充电方案。目前得到的电动汽车和充电站偏好如表1所示。

表1 充电站与电动汽车充电偏好顺序表

根据表1，应用GS算法进行计算：

算法第一轮：CS1充电站没有收到预约，EV1向CS3发出预约，EV2、EV3向CS2发出预约、EV4向CS4发出预约，由于EV3＞EV2，所以电动汽车EV2轮空。

算法第二轮，EV2向CS4发出预约，CS4的喜爱偏好中EV2＞EV4，故电动汽车EV4轮空。

算法第三轮，EV4向CS3发出预约，CS3的喜爱偏好中EV1＞EV4，故EV4继续轮空。

算法第四轮，EV4向CS2发出预约，CS2的喜爱偏好中EV3＞EV4，故EV4再次轮空。

算法第五轮，EV4向CS1发出预约，CS1之前没有收到过预约，故EV4与CS1配对成功。

至此，充电站和电动汽车匹配完毕。通过此算法的运算，如果有些车辆没有预约到合适自己的充电站，在之后的匹配过程中，没有得到预约最优解的车辆会再次进入分配系统，按照算法第一轮的逻辑进行运算，直至全部电动汽车都预约到合适的充电站为止。

5 实验

5.1 实验比较对象

5.1.1 就近原则充电方案

就近原则充电方案是指在电动汽车需要充电的时候去离自己最近的充电站充电。

5.1.2 喜爱原则充电方案

每一个充电汽车车主会提前标记自己喜欢的充电站，喜欢的充电站可能是离车主家比较近，抑或是在某一个充电站充值了会员。喜欢原则充电方案即汽车车主去自己喜欢的充电站进行充电。

5.2 实验环境

本实验通过jdk1.7环境，模拟完成充电汽车进入充电站、汽车排队等候充电、完成一次充电周期和汽车驶离充电站等任务。由于充电汽车位置的随机性，充电汽车的位置信息和喜好偏向信息通过java中的Math.random()方法来实现，获得随机数据。

在实验过程中，测试100轮数据，每一轮测试生成不同的100辆充电汽车的位置信息和汽车对于充电站的偏好信息，按照就近原则充电方案、喜爱原则充电方案、GS算法充电方案，得到每一组算法的排队峰值、总充电时间、运行总里程以及进入汽车喜欢的充电站的总辆数数据，并画出折线图。

5.3 实验数据

在测试的程序中，模拟5个充电站，充电站之间距离10个单位长度，每个充电站有3个充电桩。再模拟100辆充电汽车，每个充电汽车充满电耗时20到30个随机单位时间，随机设置每辆汽车的充电站喜好偏向，随机设置每一个充电汽车充电的位置。每辆汽车从一个充电站到另一个充电站需要1个单位时间。每一个单位时间会随机出现5辆需要充电的汽车。

5.4 实验结果及分析

根据就近原则、喜爱原则和GS算法选择随机出现的一百辆电动车做实验，通过对所有充电站中排队峰值、充满电总用时、进入喜欢充电站的车辆总数以及进入充电站前运行的总单位长度进行对比，得出如图2、图3、图4、图5所示的数据对比图。

图2 使用不同算法计算随机出现的100辆车在所有充电站中的排队峰值

图3 使用不同算法计算随机出现的100辆车完全充满电的总用时

图4 使用不同算法计算随机出现的100辆车进入喜欢充电站的车辆总数

图5 使用不同算法计算随机出现的100辆车进入充电站前运行的总单位长度

由图3可知，使用GS算法作为充电汽车的调度算法，可以明显降低各个充电站的排队峰值，可以将一些排队比较严重的充电站中的排队车辆调度到一些没有排队压力的充电站充电。明显降低整个系统充电汽车的充电总时长。

由图4可知，使用GS算法，虽然不能像喜爱原则充电方案那样保证每一个车辆都到自己喜欢的充电站进行充电，但是在整个系统中排队不严重的情况下，仍然可以保证较大比例的车辆进入自己喜欢的充电站充电。进而可以推动各个充电站的会员制，提高充电站的服务质量，获得更高的经济效益。

由图5可知，使用GS算法，虽然不能像就近原则充电方案那样，整个系统中所有充电汽车用最短的距离进入了充电站进行充电，但是充电汽车仍然可以比使用喜爱原则充电方案运行更少的距离。

6 结 论

该推荐系统旨在通过物联网、互联网、电网、交通网的“四网”联动，实现充电站使用效率的最大化，并减少驾驶员的“里程焦虑”困扰。在此基础上运用经济学中的GS算法，对汽车和充电桩进行双选，使资源分配达到最优和最合理，从而实现汽车的快速充电以及充电站利用率的最大化。