Examples of average-consensus protocols forming the weights

## Abstract

Kalman filtering in its distributed information form is reviewed and applied to a network of receivers tracking Global Navigation Satellite Systems (GNSS). We show, by employing consensus-based data-fusion rules between GNSS receivers, how the consensus-based Kalman filter (CKF) of individual receivers can deliver GNSS parameter solutions that have a comparable precision performance as their network-derived, fusion center dependent counterparts. This is relevant as in the near future the proliferation of low-cost receivers will give rise to a significant increase in the number of GNSS users. With the CKF or other distributed filtering techniques, GNSS users can therefore achieve high-precision solutions without the need of relying on a centralized computing center.

### Keywords

- distributed filtering
- consensus-based Kalman filter (CKF)
- global navigation satellite systems (GNSS)
- GNSS networks
- GNSS ionospheric observables

## 1. Introduction

Kalman filtering in its decentralized and distributed forms has received increasing attention in the sensor network community and has been extensively studied in recent years, see e.g. [1, 2, 3, 4, 5, 6, 7, 8]. While in the traditional centralized Kalman filter setup all sensor nodes have to send their measurements to a computing (fusion) center to obtain the state estimate, in the distributed filtering schemes the nodes only share limited information with their neighboring nodes (i.e. a subset of all other nodes) and yet obtain state estimates that are comparable to that of the centralized filter in a minimum-mean-squared-error sense. This particular feature of the distributed filters would potentially make the data communication between the nodes cost-effective and develop the nodes’ capacity to perform *parallel* computations.

Next to sensor networks, distributed filtering can therefore benefit several other applications such as formation flying of aerial vehicles [9], cooperative robotics [10] and disciplines that concern the Global Navigation Satellite Systems (GNSS). The latter is the topic of this present contribution. The GNSS have been proven to be an efficient tool for determination of time varying parameters that are of importance for Earth science disciplines like positioning, deformation, timing and atmosphere [11, 12]. Parameter estimation in GNSS often relies on the data processing of a *network* of receivers that collect measurements from visible GNSS satellites. In the context of sensor networks, GNSS network receivers therefore serve as sensor nodes, providing their data to a computing center, thereby computing network-based parameter solutions in a (near) real-time manner. In this contribution we intend to demonstrate how consensus algorithms [13] and the corresponding consensus-based Kalman filter (CKF), as a popular means for distributed filtering, can take an important role in GNSS applications for which a network of receivers are to be processed. Although each single receiver can run its own local filter to deliver GNSS-derived solutions, the precision of such single-receiver solutions is generally much lower than its network-derived counterparts, see e.g. [14, 15]. It will be shown, through a CKF setup, that single-receiver parameter solutions can achieve precision performances similar to that of their network-based versions, provided that a sufficient number of iterative communications between the neighboring receivers are established. The importance of such consensus-based single-receiver solutions is well appreciated in the light of the recent development of new GNSS constellations as well as the proliferation of low-cost mass-market receivers [16, 17, 18]. With the increase in the number and types of GNSS receivers, many more GNSS users can establish their own measurement setup to determine parameters that suit their needs. By taking recourse to the CKF or other distributed filtering techniques, GNSS users can therefore potentially deliver high-precision parameter solutions without the need of having a computing center.

The structure of this contribution is as follows. We first briefly review the principles of the standard Kalman filter and its information form in Section 2. The additivity property of the information filter that makes this filter particularly useful for distributed processing is also highlighted. In Section 3 we discuss average consensus rules on which the sensor nodes agree to fuse each other information. Different consensus protocols are discussed and a ‘probabilistic’ measure for the evaluation of their convergence rates is proposed. Section 4 is devoted to the CKF algorithmic steps. Its two time-scale nature is remarked and a three-step recursion for evaluating the consensus-based error variance matrix is developed. In Section 5 we apply the CKF theory to a small-scale network of GNSS receivers collecting ionospheric observables over time. Conducting a precision analysis, we compare the precision of the network-based ionospheric solutions with those of their single-receiver and consensus-based counterparts. It is shown how the CKF of each receiver responses to an increase in the number of iterative communications between the neighboring nodes. Concluding remarks and future outlook are provided in Section 6.

## 2. Kalman filtering

Consider a time series of observable random vectors *predict* the unobservable random state-vectors *realizations* of the random vectors

### 2.1. The Kalman filter standard assumptions

To predict the state-vectors in an optimal sense, one often uses the minimum mean squared error (MMSE) principle as the optimality criterion, see e.g., [19, 20, 21, 22, 23, 24, 25]. In case no restrictions are placed on the class of predictors, the MMSE predictor

Eq. (1) implies that (1) the BLP is unbiased, i.e.

The Kalman filter is a *recursive* BP (Gaussian case) or a recursive BLP. A recursive predictor, say *real-time* determination of temporally varying parameters. We now state the standard assumptions that make the Kalman filter recursion feasible.

*The dynamic model*: The linear dynamic model, describing the time-evolution of the state-vectors

with

and

for the time instances

*The measurement model*: The link between the observables

with

for

### 2.2. The three-step recursion

*Initialization*: As the mean of

That the initial error variance matrix

*Time update*: Let us choose

that are both uncorrelated with the previous data

The error variance matrix

*Measurement update*: In the presence of new data *not* necessarily the zero-correlation condition, that is, *fully* predicted by

that are both uncorrelated with *new* information. That is why *innovation* of

since

The error variance matrix

since

### 2.3. A remark on the filter initialization

In the derivation of the Kalman filter one assumes the mean of the random initial state-vector

Thus

The above error variance matrix *not* dependent on the variance matrix of

showing that *different purposes*. The error variance matrix *not* describe the quality of prediction, but instead the precision of the predictor

The MMSE of the BLUP recursion is never smaller than that of the Kalman filter, as the Kalman filter makes use of additional information, namely, the known mean

### 2.4. Filtering in information form

The three-step recursion presented in Eqs. (7), (9) and (12) concerns the time-evolution of the predictor *information* matrices

Given the definition above, the information filter recursion concerning the time-evolution of

where

The algorithmic steps of the information filter are presented in Figure 1 . In the absence of data, the filter is initialized by the zero information

*Singular matrix* *same* rank as that of

Matrix

shows an example of the representation (19). With Eq. (19), a generalization of the time update ( Figure 1 ) can be shown to be given by

Thus instead of

### 2.5. Additivity property of the information measurement update

As stated previously, the information filter delivers outcomes equivalent to those of the Kalman filter recursion. Thus any particular preference for the information filter must be attributed to the *computational* effort required for obtaining the outcomes. For instance, if handling matrix inversion requires low computational complexity when working with the input inverse-matrices *distributed* processing.

As shown in Figure 1 , the information measurement update is *additive* in the sense that the measurement information

Accordingly, the observable vector

Thus the measurement noise vectors *mutually* uncorrelated. With the extra assumption Eq. (23), the normal matrix

where

According to Eq. (24), the measurement information of each node, say

Now consider the situation where each node runs its own *local* information filter, thus having its own information states *central* counterparts *average* quantities

The local states

that are equal to the central states

To compute the average quantities *all* other nodes

## 3. Average consensus rules

In the previous section, we briefly discussed the potential applicability of the information filter as a tool for handling the measurement model Eq. (22) in a distributed manner. With the representation Eq. (28) however, one may be inclined to conclude that such applicability is limited to the case where the nodes

Instead of having direct connections, the idea is now to relax such a stringent requirement by assuming that the nodes are linked to each other *at least* through a ‘path’ so that information can flow from each node to all other nodes. It is therefore assumed that each node along the path plays the role of an *agent* transferring information to other nodes. To reach the averages *consensus protocols*, see e.g. [6, 8, 40]. Note that each node exchanges information with neighboring nodes (i.e. those to which the node has direct connections) and *not* the entire nodes. Therefore, a *repeated* application of the consensus protocols is required to be carried out. The notion is made precise below.

### 3.1. Communication graphs

The way the nodes interact with each other to transfer information is referred to as the interaction topology between the nodes. The interaction topology is often described by a directed graph whose vertices and edges, respectively, represent the nodes and communication links [4]. The interaction topology may also undergo a *finite* number of changes over sessions *undirected* (or bidirectional) graphs. Examples of such representing a network of 20 nodes with their interaction links are shown in Figure 2 . Let an undirected graph at session **(b)**, the number of links between the nodes can be different for different sessions *connected*. In a ‘connected’ graph, every vertex is linked to all other vertices at least through one path. In order for information to flow from each node to all other nodes, the *union* of the graphs

is therefore assumed to be connected. We define the *neighbors* of node

### 3.2. Consensus protocols

Given the right-hand-vector *weighted-average* of the available vectors, i.e.

as an *approximation* of *no* direct links. In other words, the weighted-averages *repeat* the fusion rule Eq. (30), but now over the new vectors

with *session number*’ *number of iterative communications*’

The question that now comes to the fore is how to choose the weights

or

The

(

where the *asymptotically* reach average consensus [4]. It can be shown that (34) holds if the weight matrices

Examples of such consensus protocols are given in Table 1 . As shown, the weights form a symmetric weight matrix *at most* one neighbor at a session [4]. In this case, each node exchanges its information to just one neighbor at a session. Thus for two neighboring nodes

Protocols | ||
---|---|---|

Protocol 1 | ||

Protocol 2 | ||

Protocol 3 | ||

Protocol 4 | ||

otherwise |

To provide insight into the applicability of the protocols given in Table 1 , we apply them to the networks of Figure 2 . Twenty values (scalars), say

### 3.3. On convergence of consensus states

Figure 3 shows that the states *different* rates. The convergence rate depends on the initial states *random* vectors. In that case, can the results be still representative for judging the convergence performances of the protocols? To answer this question, let us define the difference vectors

Now let the initial states

Thus the closer the squared matrix *spectral* form as

with the eigenvalues

The above equation shows that the entries of the variance matrix (36) are largely driven by the second largest eigenvalue of

to evaluate the convergence rates of the protocols, where

which is the probability that the absolute differences

Figure 4 demonstrates that the convergence performance of Protocol 4 is clearly better than that of Protocol 2, as it delivers higher probabilities (for the networks of Figure 2 ). Such a conclusion however, cannot be made on the basis of the results of Figure 3 . This shows that results obtained on the basis of specific ‘realizations’ of

## 4. Consensus-based Kalman filters

### 4.1. Two time-scale approach

In Section 2.5 we discussed how the additivity property of the measurement update Eq. (26) offers possibilities for developing multiple distributed local filters *every* time instance *sampling* rate *sending* rate

Under the assumption

### 4.2. Time evolution of the CKF error covariances

With the consensus-based information filter, presented in Figure 6 , it is therefore feasible to develop multiple distributed filters, all running in parallel over time. By taking recourse to an average-consensus protocol, not all the nodes are needed to be directly linked, thereby allowing non-neighboring nodes to also benefit from information states of each other. The price one has to pay for such an attractive feature of the CKF is that the local predictors

will have a *poorer* precision performance than that of their central counterpart *approximations* of the averages *finite* number of communications *not* represent the error variance matrices

Note that the terms

since

that is not necessarily equal to

In Figure 7 we present the three-step recursion of the error variance matrix *extra* input, i.e., the term *a-priori* design and analyze sensor networks with different numbers of iterative communications.

To better appreciate the recursion given in Figure 7 , let us consider a special case where a *stationary* state-vector

The central error variance matrix

in which the scalar

Substitution into the stated recursion provides us with the time-evolution of the error variance matrix

This shows that the consensus-based error variance matrix

as

## 5. Applications to GNSS

The purpose of this section is to demonstrate how the CKF theory, discussed in Section 4, can play a pivotal role in applications for which the GNSS measurements of a *network* of receivers are to be processed in a real-time manner. In a GNSS network setup, each receiver serves as a sensor node for receiving observables from visible GNSS satellites to determine a range of different parameters such as positions and velocities in an Earth-centered Earth-fixed coordinate system, atmospheric delays, timing and instrumental biases, see e.g. [11, 12]. As the observation equations of the receivers have satellite specific parameters in common, the receivers’ observables are often integrated through a computing (fusion) center to provide network-derived parameter solutions that are more precise than their single-receiver versions. Now the idea is to deliver GNSS parameter solutions without the need of having a computing center, such that their precision performance is still comparable to that of network-derived solutions.

As previously discussed, consensus-based algorithms and in particular the CKF can be employed to process network data in a distributed filtering scheme, i.e. no computing center is required. In order to illustrate such applicability, we simulate a network of 13 GNSS receivers located in Perth, Western Australia ( Figure 8 ). As shown in the figure, each node (white circle) represents a receiver having data links (red lines) to its neighbors with inter-station distances up to 4 km. We therefore assume that the receivers receive each other data within the ranges not longer than 4 km. For instance, receiver 1 is directly connected to receivers 2 and 6, but not to receiver 3 (the inter-station distance between receivers 1 and 3 is about 8 km).

### 5.1. GNSS ionospheric observables: Dynamic and measurement models

Although the GNSS observables contain information on various positioning and non-positioning parameters, here we restrict ourselves to *ionospheric observables* of the GPS *pseudo-range* measurements only [44]. One should however bear in mind that such restriction is made just for the sake of presentation and illustration of the theory discussed in Sections 3 and 4. Would one, for instance, make use of the very precise carrier-phase measurements and/or formulate a multi-GNSS measurement setup, solutions of higher precision levels are therefore expected.

Let the scalar

where the term within

with

forming the variance matrices

Suppose that

Thus the state-vector

Thus the DCBs

### 5.2. Observational campaign

The network receivers

As the satellites revolve around the Earth, not all of which are simultaneously visible to the ‘small-scale’ network of Figure 8 . Their visibility over time is shown in Figure 10 (left panel) in which the satellites with elevation angles smaller than 10 degrees are excluded. There are 31 GPS satellites (i.e.

In the following we present precision analyses on the *measurement update* solutions of

### 5.3. Central (network-based) versus local (single-receiver) solutions

Before discussing the precision performance of the CKF solutions, we first compare the network-based (central) TEC solutions with the solutions that are obtained by the data of one single-receiver only (referred to as the local solutions). At the filter initialization, the standard-deviations of the local TEC solutions are *not* follow the average of its local versions. The standard-deviation results, after one hour of the filter initialization, are presented in Figure 11 . Only the results of the receiver 1 are shown as local solutions (in red). As shown, the standard-deviations get stable over time as the filters reach their steady-state. On the right panel of the figure, the local-to-central standard-deviation ratios are also presented. In case of the vertical TECs

### 5.4. Role of CKF in improving local solutions

With the results of Figure 11 , we observed that the central TEC solutions considerably outperform their local counterparts in the sense of delivering more precise outcomes, i.e. the local-to-central standard-deviation ratios are considerably larger than 1. We now employ the CKF for each node (receiver) *improve* the local solutions’ precision performance via consensus-based iterative communications between the receivers. In doing so, we make use of the three-step recursion given in Figure 7 to evaluate the error variance matrices

Next to the solutions of the TEC parameters

## 6. Concluding remarks and future outlook

In this contribution we reviewed Kalman filtering in its information form and showed how the additive measurement update (28) can be realized by employing average-consensus rules, even when *not* all nodes are directly connected, thus allowing the sensor nodes to develop their own distributed filters. The nodes are assumed linked to each other *at least* through a ‘path’ so that information can flow from each node to all other nodes. Under this assumption, average-consensus protocols can deliver consensus states

We developed a three-step recursion of the CKF error variance matrix ( Figure 7 ). This recursion conveys useful information about the precision performance of the local filters

## Acknowledgments

The second author is the recipient of an Australian Research Council Federation Fellowship (project number FF0883188). This support is gratefully acknowledged.