An Approximately Optimal Algorithm for Scheduling Phasor Data Transmissions in Smart Grid Networks

摘要

In this paper, we devise a scheduling algorithm for ordering transmission ofsynchrophasor data from the substation to the control center in as short a timeframe as possible, within the realtime hierarchical communicationsinfrastructure in the electric grid. The problem is cast in the framework ofthe classic job scheduling with precedence constraints. The optimization setupcomprises the number of phasor measurement units (PMUs) to be installed on thegrid, a weight associated with each PMU, processing time at the control centerfor the PMUs, and precedence constraints between the PMUs. The solution to thePMU placement problem yields the optimum number of PMUs to be installed on thegrid, while the processing times are picked uniformly at random from apredefined set. The weight associated with each PMU and the precedenceconstraints are both assumed known. The scheduling problem is provably NP-hard,so we resort to approximation algorithms which provide solutions that aresuboptimal yet possessing polynomial time complexity. A lower bound on theoptimal schedule is derived using branch and bound techniques, and itsperformance evaluated using standard IEEE test bus systems. The schedulingpolicy is power grid-centric, since it takes into account the electricalproperties of the network under consideration.