Distributed coding and algorithm optimization for large-scale networked systems

Abstract

In this thesis design and optimization of several distributed algorithms in large-scale networked systems is studied. The studied algorithms operate on networks of autonomous agents in general including the sensor networks and the ad hoc networks. The main focus here is on distributed algorithms operating on large-scale networks. This is due to their robustness to node failure and ability to extend according to the size and topology of the system. Regarding the optimization of the studied algorithms, it is aimed to increase their convergence rate to their equilibrium state considering the constraints of the system including the available bandwidth, memory and power for each agent. The first topic addresses the optimization of two algorithms; namely the distributed random gossip algorithm and the distributed average consensus algorithm. The underlying graph of the network is exploited to provide an analytical solution to the semidefinite programming formulation of the problems. In the second topic, two distributed algorithms are proposed for increasing data persistency in wireless sensor networks based on LT and Raptor codes. In the proposed algorithms, the sensed data is disseminated using random walks with the non-uniform stationary distribution. A new distributed method is proposed for assigning the transition probabilities of the random walks. The third topic studies distributed coding of LT codes in Y networks where multiple sources communicate with the same destination through a common relay node. The Adaptive Distributed LT coding algorithm is proposed that combines the LT codes with the network coding technique. The fourth topic addresses optimization of the LT codes for short message lengths. Unlike previous formulations, the provided novel semidefinite programming formulation has finite number of constraints while it is free of approximation.