Network Topology and Protocol Design for Efficient Consensus in Sensor Networks

Doktorgradsavhandling ved Fakultet for teknologi og naturvitenskap, Universitetet i Agder, 2016In the new era of Internet of Things, complex sensor networks are becoming crucial to link the physical world to the Internet. These sensor networks, composed by hundreds or thousands of nodes, provide many important services to promote a heightened level of awareness about the area of interest such as in predictive maintenance, intelligent buildings, enhanced security systems, etc. In order to make these services possible, several signal processing tasks are needed to support their operation, some widely used examples of these tasks are parameter estimation, signal detection and target tracking. These tasks allow to improve the services by inferring missing data, reducing samples noise, etc., at the cost of some collaboration of the network nodes that implies their repeated communication over time. Most of these solutions are consensus-based strategies, which have recently attracted a great deal of research work because of its simplicity. These are in-network algorithms, where each node only exchanges information with its immediate neighbors and these are able to obtain global information as a function of some sensed data. A relevant example is the average consensus algorithm, which its goal is to obtain, in a distributed way, the average of the initial data. These algorithms avoid the need of performing all the computations at one or more sink nodes, thus, reducing congestion around them and incrementing the robustness of the network. In this dissertation, we focus on improving consensus algorithms in terms of different parameters and under different types of communications and network configurations. Each setting considered requires its own assumptions and methodologies, since the convergence conditions for each of them are related but different in general. In particular, in this work, all of the methodologies proposed are based on designing how the underlying communications are performed. In static networks, where the asymptotic convergence to the average value is easily ensured, a topology optimization can be a priori performed in terms of several relevant parameters. In particular, we optimize the network topology to make consensus algorithms fast and energy efficient. In this setting and for continuous systems, we derive a general framework to minimize several energy related functions under different network and nodes constraints To solve it, we propose a fractional convex-concave optimization problem with different constraints that leads to obtain the optimal topology in terms of the energy function considered. As a significant variation of the previous results, we also optimize the network topology in discrete systems. The discretization of the system introduces a weight matrix and certain step-size (related to the discrete increments of time) in the process. We show that if this step-size is small enough, the energy related problems stated before can be still casted as convex-concave fractional problems with the weight matrix as a unique optimization variable. As the step-size of the process increases in size, a discrete system requires a different approach. To solve it, we aim to find another formulation based on adding a constraint on the connectivity and solving the problem several times (for different values of the step-size). In addition, two low-complex methodologies with different computational requirements are proposed to a posteriori redesign an existing topology by the collaboration of the network nodes. On the contrary, in time-varying (random) networks, it is needed to guarantee a minimum accuracy of the algorithm, while maximizing the number of simultaneous exchanges of data to ensure fast convergence. Regarding random and asymmetric communications, we propose a novel gossip algorithm, which is based on the residual information that is generated when an asymmetric communication is performed. We exploit this information to preserve the summation of the process and accelerate it. Moreover, our proposal is useful in the case of having both unicast and broadcast communications, presenting faster convergence in both schemes than existing approaches in the related literature. When the problem of wireless interferences constraining the communications is additionally taken into account, we propose a novel and computationally efficient link scheduling protocol that correctly operates in the presence of secondary interference. Our protocol is easily implementable and does not require global knowledge of the network. The main objective of this new protocol is to be suitable for a cross-layer scheme in which the execution of the average consensus algorithm is favoured, ensuring necessary conditions for its convergence with certain accuracy. Additionally, the number of simultaneous links is additionally considered in order to make the convergence of the consensus process as fast as possible