Cost Efficient Data Aggregation Point Placement with Interdependent Communication and Power Networks in Smart Grid

In a smart grid, data aggregation points (DAPs) are communication hubs between sensors, actuators, and control center. Each DAP has a limited communication capacity and requires an installation cost. We want optimal placement for DAPs to minimize cost without compromising communication quality-of-service (QoS) requirements. DAP placement problem must not be dealt with as a communication issue in isolation because of interdependency between communication network and power network. Inter-network cascading failures may occur when a failure in DAP leads to a failure in power network, which leads to further failures in other DAPs. To avoid such failures, we have identified three requirements: power independence, communication robustness, and power robustness. We have formulated a constrained optimization problem, called cost minimization DAP placement (CMDP) to minimize DAP installation cost while satisfying communication QoS requirements, and avoiding inter-network cascading failures. CMDP is proven NP-hard, and we have proposed a heuristic algorithm to produce sub-optimal solution in reasonable time. Evaluation results show that for small systems, compared to exhaustive search, the heuristic algorithm produces identical solutions at computation time which is 375 000 times shorter. Results also indicate that communication robustness and power robustness requirements can increase linearly total DAP installation cost.