Routing in Communication Networks with Interdependent Power Grid

In smart grid, power grid and communication network are interdependent. With this interdependence, a failure in one network may lead to a cascade of failures across the networks. Considering such failures, we develop a model to determine communication route failure probability and quantify its impact in term of lost load. We formulate an optimization to find the set of optimal routes that minimize the impact triggered by an initial route failure. Unfortunately, the optimization is NP-hard and relies on a non-trivial algorithm to calculate the amount of lost load. We further transform the optimization into a dynamic programming problem using the Bellman's optimality equation. We propose a Gauss-Seidel value iteration algorithm to solve the dynamic programming problem. Simulation results confirm that the proposed algorithm can accurately find the set of optimal routes. For a network configuration with 7 power nodes and 22 routers, the algorithm can efficiently find optimal routes in 2.4 seconds while solving the original optimization takes more than 48 hours.