**Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs.** / Alwasel, Bader; Wolthusen, Stephen D.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Published

**Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs.** / Alwasel, Bader; Wolthusen, Stephen D.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Alwasel, B & Wolthusen, SD 2015, Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs. in *The proceedings of the 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015).* IEEE, pp. 418-423. https://doi.org/10.1109/WAINA.2015.77

Alwasel, B., & Wolthusen, S. D. (2015). Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs. In *The proceedings of the 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015) *(pp. 418-423). IEEE. https://doi.org/10.1109/WAINA.2015.77

Alwasel B, Wolthusen SD. Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs. In The proceedings of the 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015). IEEE. 2015. p. 418-423 https://doi.org/10.1109/WAINA.2015.77

@inproceedings{64ac975d3cd54a36a0849d09f56b0a5e,

title = "Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-R{\`e}nyi Graphs",

abstract = "The ability of an attacker to take over control of a distributed system or to deny the defender the same is a general problem, but of particular significance in cyber-physical systems where even temporary loss of view or loss of control can result in outright failure and severe cascading effects. Moreover, many such cyber-physical systems not only exhibit a safe fail-stop behaviour such that they can be brought to a halt in a safe state, but also have hard real-time requirements such as in the case of electrical power networks and their constituent elements.We study the Power Dominating Set (PDS) problem originally by Haynes to study the structure of electric power networks and their efficient control, known to be equivalent to the maximum matching problem. However, PDS is generally known to be NP-complete with poor approximability with recent work focusing on studying properties of restricted graph classes. In this paper we describe the problems of controllability and structural controllability as represented by the PDS problem and investigate different attacks affecting control networks. We therefore review existing work on graph classes for which PDS has been studied before identifying possible embeddings of such structures in Erd{\"o}s-R{\'e}nyi graphs of different density as well as the approximation characteristics which can be achieved in order to adapt them for solving the partition elements of directed PDS problem. This allows the rapid identification of feasible alternative control structures where attackers have damaged or compromised the original control network, and to recover partial controllability if a control network has been partitioned.",

keywords = "Structural Controllability, Power Dominating Sets, Recovery from Attacks",

author = "Bader Alwasel and Wolthusen, {Stephen D.}",

year = "2015",

month = apr

day = "30",

doi = "10.1109/WAINA.2015.77",

language = "English",

isbn = "978-1-4799-1774-7",

pages = "418--423",

booktitle = "The proceedings of the 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015)",

publisher = "IEEE",

}

TY - GEN

T1 - Structural Controllability Analysis Via Embedding Power Dominating Set Approximation in ErdHos-Rènyi Graphs

AU - Alwasel, Bader

AU - Wolthusen, Stephen D.

PY - 2015/4/30

Y1 - 2015/4/30

N2 - The ability of an attacker to take over control of a distributed system or to deny the defender the same is a general problem, but of particular significance in cyber-physical systems where even temporary loss of view or loss of control can result in outright failure and severe cascading effects. Moreover, many such cyber-physical systems not only exhibit a safe fail-stop behaviour such that they can be brought to a halt in a safe state, but also have hard real-time requirements such as in the case of electrical power networks and their constituent elements.We study the Power Dominating Set (PDS) problem originally by Haynes to study the structure of electric power networks and their efficient control, known to be equivalent to the maximum matching problem. However, PDS is generally known to be NP-complete with poor approximability with recent work focusing on studying properties of restricted graph classes. In this paper we describe the problems of controllability and structural controllability as represented by the PDS problem and investigate different attacks affecting control networks. We therefore review existing work on graph classes for which PDS has been studied before identifying possible embeddings of such structures in Erdös-Rényi graphs of different density as well as the approximation characteristics which can be achieved in order to adapt them for solving the partition elements of directed PDS problem. This allows the rapid identification of feasible alternative control structures where attackers have damaged or compromised the original control network, and to recover partial controllability if a control network has been partitioned.

AB - The ability of an attacker to take over control of a distributed system or to deny the defender the same is a general problem, but of particular significance in cyber-physical systems where even temporary loss of view or loss of control can result in outright failure and severe cascading effects. Moreover, many such cyber-physical systems not only exhibit a safe fail-stop behaviour such that they can be brought to a halt in a safe state, but also have hard real-time requirements such as in the case of electrical power networks and their constituent elements.We study the Power Dominating Set (PDS) problem originally by Haynes to study the structure of electric power networks and their efficient control, known to be equivalent to the maximum matching problem. However, PDS is generally known to be NP-complete with poor approximability with recent work focusing on studying properties of restricted graph classes. In this paper we describe the problems of controllability and structural controllability as represented by the PDS problem and investigate different attacks affecting control networks. We therefore review existing work on graph classes for which PDS has been studied before identifying possible embeddings of such structures in Erdös-Rényi graphs of different density as well as the approximation characteristics which can be achieved in order to adapt them for solving the partition elements of directed PDS problem. This allows the rapid identification of feasible alternative control structures where attackers have damaged or compromised the original control network, and to recover partial controllability if a control network has been partitioned.

KW - Structural Controllability, Power Dominating Sets, Recovery from Attacks

U2 - 10.1109/WAINA.2015.77

DO - 10.1109/WAINA.2015.77

M3 - Conference contribution

SN - 978-1-4799-1774-7

SP - 418

EP - 423

BT - The proceedings of the 29th IEEE International Conference on Advanced Information Networking and Applications (AINA-2015)

PB - IEEE

ER -