Scalable Electric Vehicle Charging Protocols

Liang Zhang, Vassilis Kekatos, Georgios B. Giannakis

TL;DR

This paper presents two new decentralized protocols designed to manage the massive influx of electric vehicles (EVs) onto the power grid. By utilizing the Frank-Wolfe optimization method and the Alternating Direction Method of Multipliers (ADMM), the authors achieve a 100x speedup over existing methods while ensuring grid stability and protecting user privacy.

What Problem Does This Paper Address?

As EVs become more common, uncoordinated charging—where everyone plugs in at once—threatens to overload local transformers and cause significant voltage drops. While "optimal charging" can solve this by shifting loads to "fill the valleys" of low demand, the math becomes incredibly difficult as the number of vehicles grows.

Existing solutions often struggle with two main issues:

  1. Scalability: Centralized systems that try to calculate every car's schedule at once become too slow for real-time use.
  2. Privacy and Security: Users are often reluctant to share their exact travel schedules with a central utility, and centralized pricing signals are vulnerable to data attacks or manipulation.

Methods

The authors break the problem into two scenarios:

1. Scalable Charging (No Grid Constraints)

For basic "valley-filling," the authors deploy the Frank-Wolfe method (also known as the conditional gradient algorithm).

  • The Innovation: Unlike standard "Projected Gradient Descent" (PGD) methods that require a computationally expensive "projection" step for every vehicle, Frank-Wolfe reduces the problem to a simple sorting task.
  • How it works: The charging center broadcasts a ranking of time slots (from cheapest to most expensive). Each EV controller then greedily picks the best slots for its needs. This is repeated iteratively until the system converges.

2. Network-Constrained Charging

When the grid is near its physical limits, the protocol must account for voltage levels and transformer capacities.

  • Linearized Grid Model: The authors use a linearized model for unbalanced distribution grids to keep the math tractable.
  • ADMM (Alternating Direction Method of Multipliers): This technique decomposes the massive grid-wide optimization into smaller pieces. Each "bus" (node) in the power grid only needs to communicate with its immediate neighbors to reach a global consensus on the optimal charging schedule.

Datasets

The researchers validated their protocols using:

  • IEEE 123-bus feeder: A standard, complex benchmark for testing unbalanced power distribution systems.
  • Southern California Edison (2014): Real-world residential load data used to create realistic "base load" profiles.
  • National Household Travel Survey (NHTS): Statistical data used to model realistic EV plug-in/out times and daily mileage for 59 simulated vehicles.

Key Insights and Ideas

  • Sorting is Sufficient: A major "aha moment" is that EV controllers don't actually need to know the exact price of electricity to optimize their charging; they only need to know the relative ranking of time slots. This makes the system much more resilient to price-manipulation attacks.
  • Privacy via Aggregation: The central controller doesn't need to see individual charging profiles. By using a tree-based communication structure, the system only ever sees the sum of the loads, keeping individual user habits private.
  • Computational Efficiency: Because the Frank-Wolfe update is a simple greedy selection based on sorting, its computation time is nearly constant regardless of how many time intervals are being planned. This is a massive improvement over traditional methods that slow down as the planning horizon increases.

Key Results

  • 100x Speedup: In simulations with 59 EVs, the Frank-Wolfe algorithm (Alg. 1) converged in 0.78 seconds, compared to 734.74 seconds for the PGD method and 82.47 seconds for a standard centralized solver (SeDuMi).
  • Constant Update Time: The average update time for the new protocol remained at roughly $3.5 \times 10^{-6}$ seconds per vehicle, while the competing PGD method's time increased linearly with the number of time slots.
  • Grid Stability: The ADMM-based scheme successfully managed charging for 60 EVs across the IEEE 123-bus system, maintaining all voltages within safe limits and preventing transformer overloads.

Limitations and Future Work

  • Linearization: The grid model used is a linear approximation. While accurate for many scenarios, future work could extend these protocols to the full, non-linear AC power flow equations.
  • Synchronicity: The current ADMM approach assumes all nodes update at the same time. The authors suggest that moving toward asynchronous updates (where nodes can update whenever they are ready) is a promising next step for real-world deployment.
  • Real-time Dynamics: The paper focuses on look-ahead scheduling; integrating these into a truly real-time, second-by-second control loop remains an open challenge.

Summary updated

Abstract

Although electric vehicles are considered a viable solution to reduce greenhouse gas emissions, their uncoordinated charging could have adverse effects on power system operation. Nevertheless, the task of optimal electric vehicle charging scales unfavorably with the fleet size and the number of control periods, especially when distribution grid limitations are enforced. To this end, vehicle charging is first tackled using the recently revived Frank-Wolfe method. The novel decentralized charging protocol has minimal computational requirements from vehicle controllers, enjoys provable acceleration over existing alternatives, enhances the security of the pricing mechanism against data attacks, and protects user privacy. To comply with voltage limits, a network-constrained EV charging problem is subsequently formulated. Leveraging a linearized model for unbalanced distribution grids, the goal is to minimize the power supply cost while respecting critical voltage regulation and substation capacity limitations. Optimizing variables across grid nodes is accomplished by exchanging information only between neighboring buses via the alternating direction method of multipliers. Numerical tests corroborate the optimality and efficiency of the novel schemes.
BibTeX
@article{zhang2016scalable,
  author = {Liang Zhang and Vassilis Kekatos and Georgios B. Giannakis},
  title = {{Scalable Electric Vehicle Charging Protocols}},
  journal = {IEEE Transactions on Power Systems},
  year = {2016},
  doi = {10.1109/tpwrs.2016.2582903},
}

Loading related content...

Figure