Distributed Estimation over Directed Graphs Resilient to Sensor Spoofing

Consider a system of $N$ agents where each agent is equipped with sensing, computing and communication capabilities - it can record measurements using its sensor, can perform computations using its own data and the information received from its neighbouring agents, and can also share its data with the neighbours. The aim of each agent is to estimate an unknown parameter $\theta^{*}(t)\in\mathbb{R}^{M}$ in a distributed manner even while some agents’ sensor measurements are corrupted by adversaries. The precise model of sensor measurement corruption will be described shortly.

The communication among the agents is modelled as a directed graph $\Gamma=(\mathcal{V},\mathcal{E})$, where the vertex set $\mathcal{V}=\{1,2,\ldots,N\}$ represents the set of $N$ agents. The set of directed edges $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ represents the information exchange links between the agents, where $(i,j)\in\mathcal{E}$ if agent $j$ can send information to agent $i$. A directed path from $i$ to $j$ is the sequence of directed edges $(i,i_{1}),(i_{1},i_{2}),\ldots,(i_{p},j)$. The set of in-neighbours of agent $j$ is defined as $\mathcal{N}_{j}=\{i\in\mathcal{V}:(j,i)\in\mathcal{E}\}$, and the corresponding in-degree is denoted as $d_{j}^{\textrm{in}}=|\mathcal{N}_{j}|$. The set of out-neighbours of agent-$j$ is defined as $\mathcal{O}_{j}=\{i\in\mathcal{V}:(i,j)\in\mathcal{E}\}$, and the corresponding out-degree is denoted as $d_{j}^{\text{out}}=|\mathcal{O}_{j}|$. A corresponding diagonal matrix is defined as $D^{\text{out}}=\text{diag}\big{(}d_{1}^{\text{out}},\ldots,d_{N}^{\text{out}}\big{)}$. The adjacency matrix, $A$ is a square matrix of size $N\times N$ defined as $A=[a_{ij}]$ where $a_{ij}=1$ if $(i,j)\in\mathcal{E}$, and $a_{ij}=0$ otherwise. The Laplacian, $L$ is defined as $L\coloneqq D^{\text{out}}-A$.

The flow of information is such that each agent $i$ is able to receive information from its in-neighbours $(\mathcal{N}_{i})$, and send its own data to its out-neighbours $(\mathcal{O}_{i})$. So the information about any agent $i$ can be received by another agent $j$ either directly if a directed communication link exists between them, or indirectly via intermediate agent(s) provided the corresponding directed path exists. In order to ensure that the information about every agent $i$ reaches every other agent $j,(i\neq j;i,j\in\mathcal{V})$, we introduce the following assumption.

Now we proceed to model the effect of the adversaries, which attack the agents with a motive to disrupt the estimation process thus trying to prevent them from correctly estimating the value $\theta^{*}(t)$. At every time-step $t\geq 0$, the agents which are under attack by the adversaries are termed as the the set of Bad (or affected) agents, denoted as $\mathcal{B}_{t}$. The remaining agents form the set of Good (or normal) agents, denoted as $\mathcal{G}_{t}$. The set of bad agents can vary with time, and are also not known a-priori to the set of good agents. So for each $t\geq 0$, the set $\mathcal{V}$ is partitioned into $\mathcal{G}_{t}$ and $\mathcal{B}_{t}$. Thus $\mathcal{G}_{t}\cup\mathcal{B}_{t}=\mathcal{V},\forall$ $t\geq 0$. The attack model of the adversary is sensor spoofing attacks. Here the adversary introduces spurious signals into the sensor readings non-invasively [10]. The corruption of sensor readings remains undetected by commonly used filters [19]. So even after nullifying the noise in sensor readings, the effect of the spoofing attack would still percolate into the measurements available to the agent. The agents use these sensor measurements to estimate the unknown parameter. In order to specifically highlight the effect of the adversary, we consider the sensor measurements available to the agents to be free of the effect of any measurement noise. The sensor measurements available to the agents under attack are arbitrary values manipulated by the adversary. Accordingly, we model the sensor measurements recorded by the agents as

where $\zeta_{i}(t)\in\mathbb{R}^{M}$ is a vector of arbitrary values reflecting the effect of the adversaries. In the above model there is no boundedness assumption or stochastic approximation considered for $\zeta_{i}(t)$. This preserves the arbitrary nature of the data being manipulated by the adversary. So, if $|\mathcal{B}_{t}|=0$ $\forall t\geq 0$, then $y_{i}(t)=\theta^{*}(t)$ $\forall i\in\mathcal{V}$, and the estimation problem would be trivial as the sensor measurements directly provide the correct value of the parameter. Here we are interested in the non-trivial case where there exists some $t\geq 0$ such that $|\mathcal{B}_{t}|\neq 0$. This means some of the sensor measurements would be corrupted as $y_{i}(t)=\theta^{*}(t)+\zeta_{i}(t)$ $\forall i\in\mathcal{B}_{t}$. So each agent needs to perform some additional computations in order to estimate the true value of $\theta^{*}(t)$ in a distributed manner. It should be noted that under this threat model, the bad agents are still able to perform their computations as per design as well as communicate with their neighbours.

The unknown time-varying parameter that is to be estimated is some physical quantity which can be measured by a sensor. So we can safely assume its Euclidean norm to be bounded. Moreover, we also assume that the variations in the unknown parameter asymptotically decay with time.

As a consequence of (3), we have the time varying parameter $\theta^{*}(t)$ eventually converging to some constant value $\hat{\theta}$. Specifically, $\theta^{*}(t)\to\hat{\theta}\text{ as }t\to\infty$.

Remark : The above assumption focuses on a particular subset of dynamic parameter estimation. Note that this is a modest extension from the static parameter estimation case.

Now to estimate $\theta^{*}(t)$ in a distributed manner, for all $t\geq 0$ each agent $i$ maintains its own estimate of $\theta^{*}(t)$ denoted by $x_{i}(t)\in\mathbb{R}^{M}$, also referred to as the state of agent $i$. In order to update the state, each agent $i$ follows the discrete-time single integrator dynamics :

So at every time step, each agent $i$ performs the following steps in the given sequence :

1. $S1$ -

   broadcasts its own estimate $x_{i}(t)$ to its out-neighbours $\mathcal{O}_{i}$

2. $S2$ -

   receives the estimates from its corresponding in-neighbours : $x_{j}(t)$, $j\in\mathcal{N}_{i}$

3. $S3$ -

   collects sensor measurement of $\theta^{*}(t)$ : $y_{i}(t)$

4. $S4$ -

   updates its own estimate following (4), where $u_{i}(t)=f(y_{i}(t),\{x_{j}(t),j\in\mathcal{N}_{i}\})$, and $f$ is defined later in Section 3.2.

In a distributed estimation problem with $x_{i}(t)$ as the state of agent $i$ and $\theta^{*}(t)$ as the parameter of interest, the aim is to achieve

For the resilient estimation problem considered here, the additional challenge is to achieve (5) even in the presence of adversaries attacking some of the agents. In order to quantify how resilient an algorithm is to the adversarial attacks, we use a measure called the Resilience Index [15]. The resilience index $(s)$ is an upper bound on the fraction of agents which are under attack by the adversaries at any time-step $t$. So, $s\geq\frac{|\mathcal{B}_{t}|}{N}$ for all $t\geq 0$, $s\in\mathbb{R}$. Thus $s=0$ would indicate the trivial case where bad agents are totally absent. Having $s=1$ allows for the possibility of all the agents being under attack at any time-step $t$.

In the sequel, we initially proceed to design an algorithm which provides us with a suitable value of $u_{i}(t)$ $\forall t\geq 0$, for all $i\in\mathcal{V}$ introduced in (4). Then we present our main result on how the newly designed algorithm, under the assumptions made so far, achieves (5).

In a Multi-Agent System (MAS), the communication network is usually modelled as a graph, with the nodes of the graph representing the agents and the edges between the nodes representing the corresponding communication links between the agents. When the flow of information between agents is bi-directional, the model used is an undirected graph. On the other hand, when the flow of information between agents is unidirectional, a directed graph (or digraph) is required to model it. The directed edges of the digraph represent the unidirectional communication links while preserving their direction of information flow. A weighted graph has each of its edges assigned a real or integer value, referred to as edge weights. Unless specifically mentioned, the edge weights are taken as unity.

In case of an undirected graph, the sum of edge weights of the incoming edges is equal to the sum of the edge weights of the outgoing ones. But this balance in edge weights does not necessarily hold true in the case of a digraph. To overcome this imbalance, we need to find a suitable weight vector $w\in\mathbb{R}^{N}$, where each outgoing edge of agent $i$ is assigned the weight $w_{i}$. These weights are said to balance the graph if $w_{i}d_{i}^{\text{out}}=\sum_{j\in\mathcal{N}_{i}}w_{j}$. The notion of a balanced graph is formally defined below.

The weights $\big{(}w_{1},w_{2},\ldots,w_{N}\big{)}$ which balance a given digraph are called the balancing weights of the corresponding digraph [17]. Note that an undirected graph is inherently balanced with $w=\mathbf{1}$ as the vector of balancing weights. On the other hand, for a strongly connected digraph the vector of balancing weights is non-trivial. Note that this vector of balancing weights is also unique to the given digraph, up to scaling [17]. For example, consider the strongly connected digraph shown in Fig.1. For this digraph the vector of balancing weights is $w=[0.5,1.5,1]^{T}$, which is non-trivial and unique up to scaling.

The SIU algorithm proposed in [15] for resilient estimation does not work in general for directed graphs. This is later illustrated through a numerical example in Fig.5 in Section 4. We propose to use the idea of balancing weights described above to achieve resilient estimation over digraphs. For the directed graph $\Gamma$, we use the following update rule, proposed in [17], to iteratively compute a set of balancing weights. Let $w_{i}(t)\in\mathbb{R}$ denote the weight at node $i$ at time-step $t$. The initial set of weights assigned to the agents satisfy : $w_{i}(0)\leq(1/d^{\text{out}}_{\text{max}})^{2\Phi+1}$, where $d^{\text{out}}_{\text{max}}$ represents the maximum out-degree and $\Phi$ represents the diameter of the concerned digraph [17]. Then for all $t\geq 0$,

Let $w(t)=\big{(}w_{1}(t),w_{2}(t),\ldots,w_{N}(t)\big{)}$ represent the vector of node-weights at time-step $t$. Then the corresponding vector representation of (7) is given by :

where $P\coloneqq 0.5\big{(}I+(D^{\text{out}})^{-1}A\big{)}$. So for the limiting case, $\lim_{t\rightarrow\infty}w(t)=\lim_{t\rightarrow\infty}P^{t}w(0)$. Now from Lemma 1 of [17], we know that $\lim_{t\rightarrow\infty}P^{t}$ exists, and that the sequence $\{w(t)\}_{t\geq 0}$ converges to the vector of balancing weights. So we define here the vector of weights which balances the digraph $\Gamma$ as

The time-varying weighted Laplacian matrix is represented as

Then the Laplacian matrix for the limiting case can be defined using the result from (9) in (10) as

Now as $w^{\infty}$ balances the digraph, $L_{\infty}$ satisfies the desired balancing condition expressed in (6). By definition of $L(t)$ we have $\mathbf{1}^{T}L(t)=\mathbf{0}^{T}$ for all $t\geq 0$. So to arrive at the desired balanced graph condition, we need $L(t)\mathbf{1}=\mathbf{0}$ which is eventually achieved with $L(t)$ converging to $L_{\infty}$ as $t\rightarrow\infty$. Next we state a lemma which provides an explicit rate for this convergence and additionally provides the rate of decay of $L(t)\mathbf{1}$ to $\mathbf{0}$.

The proof of Lemma 1 is given in Appendix 6.

Now we introduce our algorithm, Resilient Estimation through Weight Balancing (REWB). It consists of two main update steps : one for the state of the agents, and the other for the node weights.
The updates performed by agent $i$ at time-step $t$ are :

1. i)

   Updating the estimate

   $$\begin{split}x_{i}(t+1)=\big{(}1&-\beta(t)w_{i}(t)d_{i}^{\text{out}}\big{)}x_{i}(t)\\ &+\beta(t)\Big{(}\sum_{j\in\mathcal{N}_{i}}w_{j}(t)x_{j}(t)\Big{)}\\ &+\alpha(t)k_{i}(t)\big{(}y_{i}(t)-x_{i}(t)\big{)}\end{split}$$

   (12)

2. ii)

   Updating the weight

   $$w_{i}(t+1)=\frac{1}{2}w_{i}(t)+\frac{1}{d_{i}^{\text{out}}}\Big{(}\sum_{j\in\mathcal{N}_{i}}\frac{1}{2}w_{j}(t)\Big{)}$$

   (13)

The update law (12), used by agents to update their estimate of $\theta^{*}(t)$, is based upon the consensus+innovation approach. The first two terms, dealing with the agent’s own and neighbours’ estimates and the corresponding node-weights, constitute the consensus part of the update law. The third term, involving the measurements $y_{i}(t)$ and a scaling factor $k_{i}(t)$, constitute the innovation part. These two parts working simultaneously through the same update law help in achieving the smaller goals $G1$ and $G2$ mentioned before. The above update law uses step-size parameters $\beta(t)$ and $\alpha(t)$ to assign proper weightage to its consensus and innovation parts respectively. The parameters are defined as :

where $0<\alpha_{0}\leq 1/(1-2s)$ , $0<\beta_{0}<\psi$ , $0<\beta_{1}<\alpha_{1}<\theta_{1}$. The constant $\psi$ is defined as $\psi\coloneqq 2/\big{(}Nd^{\text{in}}_{\text{max}}(d^{\text{in}}_{\text{max}}+d^{\text{out}}_{\text{max}})\big{)}$. Note that $\beta_{1}<\alpha_{1}$ implies that, in the state update law (12), the weight of the innovation term decays faster than the weight of the consensus term.

The scaling factor, $k_{i}(t)$, is used in the innovation part in order to ensure that the effect of the adversaries on the state of an agent always remains bounded.

where $\gamma(t)$ is the output of a dynamical system defined as

The dynamics of $\gamma_{1}(t)$ and $\gamma_{2}(t)$ are defined as

where, $\mu(t)=\frac{\mu_{0}}{(t+1)^{\mu_{1}}}$, $\mu_{0}>0$, $\beta_{1}<\mu_{1}<\alpha_{1}$, $c_{1}>0$, $c_{2}>0$, $0<\eta<1$. The above time-varying system in two variables plays a crucial role in proving our main result. From the definition of $k_{i}(t)$ in (15), a corresponding diagonal matrix is defined as

Let $x(t)=\big{(}x_{1}^{T}(t),x_{2}^{T}(t),\ldots,x_{N}^{T}(t)\big{)}\in\mathbb{R}^{N\times M}$ represent the matrix whose rows are the state vectors of the agents at time-step $t$. Also let $y(t)=\big{(}y_{1}^{T}(t),y_{2}^{T}(t),\ldots,y_{N}^{T}(t)\big{)}\in\mathbb{R}^{N\times M}$ represent the matrix whose rows are the sensor measurements of the agents at time-step $t$. Now we summarise our REWB algorithm as follows :

The following theorem states our main result on resilient distributed estimation using the REWB algorithm.

The proof of Theorem-1 is given in Appendix-8. Here we provide a remark on the above theorem.