The probabilistic and reliable connected power dominating set problems

As a variation of minimum dominating set problem, the power dominating set problem is proposed to achieve the complete observation of a power system by placing the smallest number of PMUs. Under different contingencies consisting line outages or PMU losses, the reliability of observation for each bus should be guaranteed to ensure the security and robustness of the power system. Thus, the probabilistic power dominating set (PPDS) problem is proposed in this paper. Given a pre-specified reliability level for each bus in the power system to be observed and known distribution of random events, an integer programming formulation, with consideration of zero-injection property, is presented for the PPDS problem. Additionally, the reliable connected power dominating set problem is studied to meet two requirements, including the connectivity of the PMU subgraph and the reliability of the connectivity of this subgraph. Numerical experiments based on several IEEE test cases are performed to find the best deployment of PMUs satisfying different requirements.