Optimal Cost Network Design for Bounded Delay Data Transfer from PMU to Control Center

Communication network topology design problem in a smart grid environment has received considerable attention in recent times, because in this environment, power transmission control data, generated by Phasor Measurement Units (PMUs), needs to be exchanged between Substations (SS) and Controls Centers (CC) in real time. In this paper, we formalize this design problem studied in a previous paper as the Rooted Delay Constrained Minimum Spanning Tree (RDCMST) problem. While other researchers have studied the RDCMST problem in a topological setting, we study it in a geometric setting. We provide a modified version of the well-known Prim's algorithm for construction of a Minimum Spanning Tree of a graph to solve the RDCMST problem. We (i) establish the necessary and sufficient condition for the existence of a solution for the RDCMST problem, (ii) demonstrate that our algorithm may fail to find the optimal solution for some problem instances, (iii) characterize conditions on the input data which will ensure that our algorithm will find the optimal solution, and (iv) demonstrate that under some pathological condition, the ratio between our algorithm and the optimal solution can be arbitrarily large. We provide an Integer Linear Programming formulation for the problem for computation of the optimal solution. We evaluate the performance of our algorithm with real substation location data of Arizona. In our experiments, our algorithm always produced either optimal or near optimal solutions.