Keywords
Trusted Nodes, Networked Dynamical Systems, Resilient Distributed State Estimation
Presentation Type
Poster
Research Abstract
We study estimation of the state of a dynamical system via a network of nodes (or sensors). Such networks are vulnerable to malicious adversaries that compromise some of the nodes and cause them to deviate from the estimation algorithm. It is thus vital to increase the robustness of the system against such attacks. We consider the problem of allocating enough budget to make a small fraction of the nodes attack-immune, thereby making them “trusted”. These nodes must be chosen carefully so that the entire network is capable of reliably estimating the state of the system. We prove that this problem is computationally hard and thus unlikely to admit a fast algorithm that will find an optimal solution. We propose an intuitive greedy algorithm, which iteratively and myopically chooses trusted nodes, and identify certain network topologies where the greedy algorithm performs optimally or poorly. Furthermore, we study various aspects of the proposed greedy algorithm based on three popular random graph models that are often used to represent large-scale complex networks.
Session Track
Sensing and Measurement
Recommended Citation
Xingchen Wang, Shreyas Sundaram, and Aritra Mitra,
"Selecting Trusted Nodes for Resilient Distributed State Estimation of Linear Time Invariant Systems"
(August 2, 2018).
The Summer Undergraduate Research Fellowship (SURF) Symposium.
Paper 121.
https://docs.lib.purdue.edu/surf/2018/Presentations/121
Symposium poster
Selecting Trusted Nodes for Resilient Distributed State Estimation of Linear Time Invariant Systems
We study estimation of the state of a dynamical system via a network of nodes (or sensors). Such networks are vulnerable to malicious adversaries that compromise some of the nodes and cause them to deviate from the estimation algorithm. It is thus vital to increase the robustness of the system against such attacks. We consider the problem of allocating enough budget to make a small fraction of the nodes attack-immune, thereby making them “trusted”. These nodes must be chosen carefully so that the entire network is capable of reliably estimating the state of the system. We prove that this problem is computationally hard and thus unlikely to admit a fast algorithm that will find an optimal solution. We propose an intuitive greedy algorithm, which iteratively and myopically chooses trusted nodes, and identify certain network topologies where the greedy algorithm performs optimally or poorly. Furthermore, we study various aspects of the proposed greedy algorithm based on three popular random graph models that are often used to represent large-scale complex networks.