# Consensus Filtering Algorithm with Incomplete Measurements

Authors: Yungang Wu; Zhenmin Tang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In order to improve the estimate performance of distributed sensor networks, we introduce an improved consensus-based distributed filtering algorithm. Firstly, sensors obtain the local estimates using their own measurements. Then through utilizing the data of neighbor nodes to update the local estimates, estimates in the networks can reach dynamic average consensus. Based on studying the value of consensus step size, we give a sufficient condition for the convergence of the algorithm and discusses the influences of the consensus step size and the detection probability on the accuracy and consensus of estimation. The numerical simulation demonstrates that the algorithm proposed in this paper can improve the accuracy and consensus of estimation, and it is more robust with incomplete measurements.


---

## Body

## 1. Introduction

The distributed estimation of sensor network has been widely used in target tracking, environment monitoring, rescuing in risk areas, and so on, which has attracted more and more attention [1–3]. In the traditional decentralized Kalman filtering, every node in the network needs to get all information of the other nodes, which cannot be easily realized in the project due to the communication topology and limited bandwidth. Fortunately, this problem can be solved with the distributed estimation method. In the distributed estimation, every node only needs to communicate with its neighboring nodes. Through local information exchange and fusion, we can achieve more precise estimation, and it can also decrease the time delay and energy loss of signal transmission.The consensus algorithm can be used for distributed estimation of sensor network. The consensus of network has been widely researched in many ways, such as flocking control [4], cooperative control of vehicle formations [5], and consensus of multiagent system [6]. Early in 2005, Spanos et al. studied the distributed estimation by consensus algorithm [7]. They proposed a Kalman-consensus algorithm for distributed estimation. The key of their work is to design a consensus algorithm that makes each node of the network able to track the average value of the observations, also known as dynamic average consensus. In [8], Olfati-Saber and Shamma designed a low-pass filter based on consensus algorithm, which can solve the problem of dynamic average consensus. In 2007, Olfati-Saber proposed three different distributed estimation algorithms [9], which are, respectively, based on consensus of observations, consensus of local estimates, and consensus of observations and local estimates. It also showed that the third algorithm can get more precise estimation. Later, Sun and Lemmon considered time-slotted frequency division multiple access networks assuming a regular network [10]. Under these assumptions it showed that throughput limits can be modeled as delays. It studied the impact these delays have on the time and energy that consensus filters require to achieve consensus. In 2009, Stanković et al. researched the distributed estimation with switching topology [11]. Through the consensus processing of local prediction, it proposed distributed estimation algorithms with switching topology. In 2011, Ugrinovskii studied the problem of distributed robust filtering with H
∞ consensus of estimates [12]. In [13], Battistelli and Chisci derived a novel distributed estimator which considers the problem of a consensus on local posterior PDF of each node. In 2015, Das and Moura proposed a consensus and innovations distributed estimator which studied distributed estimation of unstable dynamic random fields observed by a sparsely connected network of sensors [14].In practical applications, there may be a nonzero probability that any observation consists of noise alone if the target is absent; that is, the measurements are not consecutive but contain missing observations. The phenomenon is called incomplete measurements. The missing observations are caused by a variety of reasons, for example, the high maneuverability of the tracked target, a certain failure in the measurement, intermittent sensor failures, accidental loss of some collected data, or the possibility that some of the data may be jammed or coming from a high noise environment [15]. In 2014, Chen et al. studied the distributed Kalman filtering problem for a class of networked multisensor fusion systems with missing measurements, random transmission delays, and packet dropouts [16]. For the algorithm in [9], Wang et al. proposed a modified distributed estimation algorithm with incomplete measurements [17]. By theoretical analysis, they give a sufficient condition for the convergence of the estimation error system, with the condition that the measurement matrix should be invertible. They also studied the influence of the packet-dropping rate on their algorithm and found that the nodes with a large number of neighboring nodes play an important role in the distributed estimation. However, the assumed condition that the measurement matrix should be invertible in [17] is difficult to satisfy in practice. Moreover, this algorithm reduced the estimation precision and consensus.In practical engineering, the sensor network is generally distributed. If sensors in the distributed network estimate the targets states using their measurements, it would result in a large estimation error and there can be inconsistency of the estimations between each node. Motivated by the consensus property of distributed network, we introduce a modified consensus-based distributed filtering algorithm. Through communicating with their neighbor nodes using the proposed algorithm, the estimations of each sensor tend to coincide; that is, each sensor will get the same estimates of the target state. Firstly, sensors obtain the local estimates using their own measurements. Then through utilizing the data of neighbor nodes to update the local estimates, estimation in the network can reach dynamic average consensus. In [18], Spanos et al. studied the consensus dynamics in continuous system. While in actual engineering applications, the system can be always discrete. So we give some properties of the proposed consensus-based distributed filter in discrete system. The robust bound of the step size is obtained. Meanwhile, we give proof that the algorithm can reach dynamic average consensus. In this paper, we analyze the influences of the consensus step size and discuss the relationship between the detection probability and the estimation accuracy based on the presented algorithm. Finally, the numerical simulation demonstrates that the algorithm put forward can improve the accuracy and consensus of estimation, and it is more robust with incomplete measurements as compared to the algorithm in [17].The main contribution of this work is to propose a consensus-based distributed filter with incomplete measurements in discrete system that can achieve dynamic average consensus. It can solve the problem that each sensor node with some missing observations in distributed sensor network can get the same estimation of the target. And also, it gives a sufficient condition for the convergence of the algorithm that it does not require the observation matrix to be invertible. This would be more useful in practice.An outline of this paper is as follows. Section2 gives the problem statement. Section 3 introduces the consensus-based distributed filtering algorithm. In Section 4, the simulation results are used to evaluate the proposed algorithm. A summary of our conclusion is given in Section 5.


## 2. Problem Statement

In distributed tracking using sensor networks, each sensor of the network can be considered as a node. The objective is to estimate and track the state of the target using a distributed algorithm involving message-passing between a node and all of its neighbors over a network topologyG.Consider an undirected connected graphG
=
(
V
,
E
) of a sensor network with n sensors, where the vertex set V contains nodes n and E is the edge set. Each vertex of the graph is referred to as a node and endowed with a state x
i
(
k
), for every i
∈
V. The edge (
i
,
j
)
∈
E indicates that node i and node j can establish a communication link with each other.Moreover, we always assume that transmissions are successful and noise-free. Denote the adjacency matrix byA
d
=
[
a
i
,
j
]. If i
=
j, a
i
,
j
=
0. If i
≠
j, a
i
,
j
=
1 when (
j
,
i
)
∈
E; a
i
,
j
=
0 when (
j
,
i
)
∉
E. We denote the neighbors of node i as N
i
≜
{
j
∈
V
,
a
i
j
∉
0
}. L
=
D
-
A
d is the Laplacian of graph G:(1)
D
=
d
1
0
⋯
0
0
d
2
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
d
n
.
d
i
≜
∑
j
‍
a
i
j is the node degree of i.Figure1 illustrates the target tracking based on a distributed sensor network with five sensor nodes, where the solid black line represents that the two nodes can establish a communication link. The sensor network can be simplified as an undirected connected graph. There is an edge in the topology of the graph when two nodes can change information from each other. The set of neighbors N of the topology represents set of adjacent sensors of a sensor node. y
k
i is the observation of the ith node. The adjacency matrix A
d and the degree matrix D of the sample graph are(2)
A
d
=
0
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
0
,
D
=
3
0
0
0
0
0
1
0
0
0
0
0
3
0
0
0
0
0
1
0
0
0
0
0
2
.Figure 1
Sample graph of the distributed sensor network.From Figure1, the dynamic of the target and measurement equation are shown as follows:(3)
x
k
+
1
=
A
x
k
+
w
k
,
y
k
i
=
η
k
i
H
i
x
k
+
v
k
i
,
i
=
1,2
,
…
,
n
,where x
k
∈
R
m
×
1 is a state vector to be estimated, y
k
i
∈
R
r
×
1 is the observation of the ith sensor, and A
∈
R
m
×
m and H
i
∈
R
r
×
m are constant matrices with suitable dimensions. w
k
∈
R
m
×
1 and v
k
i
∈
R
r
×
1 are uncorrelated white noises with zero mean and satisfy the following condition:(4)
v
k
i
~
N
0
,
R
i
,
η
k
i
=
1
N
0
,
σ
I
r
,
η
k
i
=
0
(5)
cov
⁡
w
k
,
w
l
=
Q
δ
k
-
l
(6)
cov
⁡
v
k
i
,
v
l
j
=
R
i
δ
k
-
l
δ
i
-
j
,
η
k
i
=
1
σ
I
r
δ
k
-
l
δ
i
-
j
,
η
k
i
=
0
(7)
δ
s
=
0
,
s
≠
0
1
,
s
=
0
.In (4) and (6), I
r represents an identity matrix with applicable dimensions. In (4), if η
k
i
=
0, σ
→
∞. η
k
i is a random variable, and its probability distribution function is shown as follows:(8)
p
η
k
i
=
1
=
λ
i
,
p
η
k
i
=
0
=
1
-
λ
i
.
η
k
i
=
1 represents that at time k the sensor i can access the measurement; η
k
i
=
0 represents that the measurement is missing. λ
i represents the detection probability of node i.


## 3. Consensus-Based Distributed Filtering Algorithm

Denote the local estimate of sensori by z
^
k
i
∈
R
m
×
1
.
θ
k
i
∈
R
m
×
1 is the intermediate variable. x
^
k
i
∈
R
m
×
1 is the final estimate. The process of our proposed consensus-based distributed filtering algorithm is shown as follows.Step 1.
Perform initialization:(9)
x
^
0
i
=
x
0
,
z
^
0
i
=
z
0
,
θ
0
i
=
θ
0
,
P
0
i
=
P
0
.Step 2.
Update the local estimates:(10)
K
k
i
=
A
P
k
i
H
i
T
H
i
P
k
i
H
i
T
+
R
i
-
1
,
P
k
+
1
i
=
A
P
k
i
A
T
+
Q
-
η
k
i
A
P
k
i
H
i
T
H
i
P
k
i
H
i
T
+
R
i
-
1
H
i
P
k
i
A
T
,
z
^
k
+
1
i
=
A
z
^
k
i
+
η
k
i
K
k
i
y
k
+
1
i
-
H
i
A
z
^
k
i
.Step 3.
Calculate the final estimates:(11)
θ
k
+
1
i
=
θ
k
i
+
ɛ
∑
j
∈
N
i
θ
k
j
-
θ
k
i
+
z
^
k
j
-
z
^
k
i
,
x
^
k
i
=
θ
k
i
+
z
^
k
i
, where ɛ represents the step size.In [18], Spanos et al. studied the filter in Step 3 for continuous system. In this paper, we will give some properties of the filter in Step 3 in discrete system case.Theorem 1.
The filter at stepk can be stable when the step size ɛ satisfies the following condition: 0
<
ɛ
<
1
/
d
m
a
x.Proof.
According to the properties of the Laplacian of graph, the filter in Step3 can be rewritten as(12)
θ
k
+
1
=
θ
k
-
ɛ
L
^
θ
k
-
ɛ
L
^
z
^
k
,
x
^
k
=
θ
k
+
z
^
k
,where d
m
a
x
≜
m
a
x
i
d
i, x
^
k
≜
c
o
l
(
x
^
k
1
,
x
^
k
2
,
…
,
x
^
k
n
)
∈
R
n
m
×
1, z
^
k
≜
c
o
l
(
z
^
k
1
,
z
^
k
2
,
…
,
z
^
k
n
)
∈
R
n
m
×
1, and L
^
≜
L
⊗
I
m.
The input and output transfer function of this filter is(13)
G
x
^
z
^
z
=
z
I
n
⊗
I
m
-
I
n
⊗
I
m
-
ɛ
L
^
-
1
z
-
1
.
In order to make this filter stable, the spectral radius ofI
n
⊗
I
m
-
ɛ
L
^ should satisfy the following condition:(14)
ρ
I
n
⊗
I
m
-
ɛ
L
^
<
1
.
According to the Gerschgorin lemma in [19], we have(15)
1
-
2
d
m
a
x
ɛ
≤
λ
I
n
⊗
I
m
-
ɛ
L
⊗
I
m
. So the step size should satisfy the following condition:(16)
0
<
ɛ
<
1
d
m
a
x
.
Next, we will discuss the dynamic average consensus of the filter in Step3. Firstly, we give the lemma that we need.Lemma 2 (see [19]).
SupposeB is a real symmetric matrix and so admits a spectral decomposition B
=
∑
i
=
1
n
‍
λ
i
G
i, where λ
i
(
i
=
1,2
,
…
,
n
) are real eigenvalues and G
i are orthogonal projections onto mutually orthogonal eigenspaces. It is a fact from graph theory that connectedness of graph implies the following:(1)
f
(
A
)
=
∑
i
=
1
n
‍
f
(
λ
i
)
G
i,
(2)
A
⊗
I
=
∑
i
=
1
n
‍
λ
i
G
i
⊗
I
.Theorem 3.
If the step size satisfies the stable condition in Theorem1 and the input signal z
^
(
z
) has all its poles in unit circular and has at most one pole at the unit circular, then the filter in Step 3 can reach dynamic average consensus; that is,(17)
l
i
m
k
→
∞
x
^
k
i
-
1
N
∑
i
=
1
n
z
^
k
i
=
0
,where z
^
k
(
z
) represents the Z-Transform of z
^
k.Proof.
Define the error vectore
k:(18)
e
k
=
x
^
k
-
1
N
1
1
T
⊗
I
m
z
^
k
,where 1
=
(
1,1
,
…
,
1
)
T
∈
R
n
×
1.
TheZ-Transform of (18) is(19)
e
z
=
x
^
z
-
1
N
1
1
T
⊗
I
m
z
^
z
.
According to (19), we have(20)
e
z
=
z
I
n
⊗
I
m
-
I
n
⊗
I
m
-
ɛ
L
⊗
I
m
-
1
z
-
1
z
^
z
-
1
N
1
1
T
⊗
I
m
z
^
z
.
The input and error transfer function is(21)
G
e
z
^
z
=
z
I
n
⊗
I
m
-
I
n
⊗
I
m
-
ɛ
L
⊗
I
m
-
1
z
-
1
-
1
N
1
1
T
⊗
I
m
.
According to Lemma2, we have(22)
L
=
∑
l
=
1
s
λ
l
Ω
l
G
e
z
^
z
=
∑
l
=
2
s
z
-
1
z
-
1
-
ɛ
λ
l
Ω
l
⊗
I
m
e
z
=
∑
l
=
2
s
z
-
1
z
-
1
-
ɛ
λ
l
Ω
l
⊗
I
m
z
^
z
.
According to the condition that the input signalz
^
(
z
) has all its poles in unit circular and has at most one pole at the unit circular and 0
<
ɛ
<
1
/
d
m
a
x, e
k is a bounded sequence. By final value theorem, we have(23)
l
i
m
k
→
∞
e
k
=
l
i
m
z
→
1
z
-
1
e
z
=
0
. Hence l
i
m
k
→
∞
(
x
^
k
-
1
/
N
1
1
T
⊗
I
m
z
^
k
)
=
0; that is, l
i
m
k
→
∞
(
x
^
k
i
-
1
/
N
∑
i
=
1
n
‍
z
^
k
i
)
=
0.


## 4. Simulation and Analysis

Consider a distributed sensor network with20 nodes, with d
m
a
x
=
9. The dynamic equation of the system is(24)
x
k
+
1
=
A
x
k
+
w
k
, where A is the state-transition matrix:(25)
A
=
1
0.0015
0.03
1
.The other parameters of the system are shown as follows:(26)
c
o
v
w
k
,
w
l
=
Q
δ
k
-
l
Q
=
1
0
0
0.25
H
i
=
h
1
0
0
h
2
h
1
∈
0.6,0.8
,
h
2
∈
0.6,0.8
R
i
=
r
1
0
0
r
2
r
1
∈
4,16
,
r
2
∈
4,16
.The original state of the system isx
0
=
15
-
10
T.According to Theorem1, the value range of the step size is ɛ
∈
(
0,1
/
9
). Define e
k and χ
k as the estimate error and consensus error:(27)
e
k
≜
1
n
∑
i
=
1
n
ξ
k
i
T
ξ
k
i
ξ
k
i
=
x
^
k
i
-
x
k
i
χ
k
≜
1
n
∑
i
=
1
n
κ
k
i
T
κ
k
i
κ
k
i
=
1
n
∑
i
=
1
n
x
^
k
i
-
x
^
k
i
.We usee
k to evaluate the estimate accuracy and use χ
k to evaluate the degree of deviation of the algorithm. The estimate error e
k in distributed sensor network represents the average deviation between the estimation results and the true value of the target state, while the consensus error χ
k represents the average estimation deviation between each sensor. We compare the algorithm proposed in this paper (Algorithm 1) to the algorithm in [17] (Algorithm 2) without observation data loss, as shown in Figure 2. Because the provided algorithm uses more information of neighbor nodes, it can improve the accuracy and consensus of estimation.Figure 2
Comparison of the errors in the idea case: (a) estimation errors; (b) consistency errors.
(a)
(b)In the actual system, the detection probability of observation system is always less than one. We compare the two algorithms with incomplete measurements under the condition thatλ
i
=
0.8, as shown in Figure 3. We can find that the algorithm that we propose in this paper is more robust with incomplete measurements. Furthermore, from the process of our algorithm we find that the step size ɛ and detection probability can affect estimate results. We compare the estimate results with different values of ɛ and λ
i in Figures 4 and 5.Figure 3
Comparison of the errors with incomplete measurements: (a) estimation errors; (b) consistency errors.
(a)
(b)Figure 4
Comparing results with different probabilities.Figure 5
Comparing estimation results with different step sizes.Next, we will investigate the influence of dynamic equation and state on steady state consensus error. Consider the following two dynamic systems ((a) and (b)):(28)
a
:
A
=
1
0.1
0
1
,
x
0
=
15
1
T
,
b
:
B
=
1
0.1
0
1
,
x
0
=
15
5
T
.The other parameters are assigned as(29)
H
i
=
0
1
,
Q
=
0.1
3
3
0.1
2
2
0.1
3
2
0.1
.The essential difference between the two cases is that the changes ratios of state are obviously different from each other. We will use the following network to test the influence of change ratio on consensus error. Consider 50 nodes distributed randomly in the area[
100,100
]; the distance between nodes less than 20 has a link, as shown in Figure 6. The comparison of consensus errors is shown in Figure 7.Figure 6
Sensor network with 50 nodes.Figure 7
Comparison of consistency errors.From Figure7, we conclude that, with the proposed consensus filtering algorithm in this paper, the system with smaller changes ratio of state leads to a better performance of consensus. Review the equations of these two dynamic systems in (28); they are similar to the motion equations of CV (constant velocity) mode in target tracking filed. From the simulation results above, that is to say, the target with smaller velocity, we will get the lower consistency error. Therefore, the filtering performance will be affected by the specific dynamic system, which will give a better performance for the dynamic system with slow changes of state.


## 5. Conclusion

In this paper, we proposed a modified consensus filtering algorithm based on distributed sensor network. Compared to the continuous system in [18], we give some properties of the proposed consensus-based distributed filter in discrete system. We give a sufficient condition for the convergence of the algorithm and discuss the influences of the consensus step size and the detection probability on the accuracy and consensus of estimation. As compared to the algorithm in [17], it does not need the condition that the observation matrix should be invertible. Also, it can improve the estimation accuracy and consensus, and it is more robust with incomplete measurements. The developed algorithm can be used in different practical applications, such as the fire control system and the wireless sensor network. At the same time, the provided algorithm needs more information from neighbor nodes. Therefore, energy consumption of the sensor network will increase. So how to make the tradeoff between the estimation accuracy and energy consumption in practical application needs further investigation.



---

*Source: 131247-2015-11-30.xml*