Efficient distributed consensus in wireless sensor networks

Many applications of wireless sensor networks can be formulated as instances of the distributed average consensus problem. This problem involves reaching a network state where each node has the same value---the average of the initial values. Reaching a consensus can be challenging in practical scenarios where the network topology varies in time due to node mobility or unreliable wireless communication links. Randomized gossip algorithms are attractive methods for such scenarios because they do not require specialized routes; they rely on asynchronous updates between random pairs of nodes. However, the communication overhead of gossip is high on topologies that are generally used for modeling wireless sensor networks. Here we propose novel gossip algorithms that reach the consensus with fewer wireless transmissions compared to randomized gossip.We first propose greedy gossip with eavesdropping. This algorithm takes advantage of the broadcast nature of wireless transmissions such that nodes eavesdrop on the updates in their neighborhood. Consequently, when a node wakes up for gossip update, instead of choosing a neighbor randomly, it chooses the neighbor which has the most different value than its own. We prove that greedy updates in this fashion are guaranteed to converge faster than randomized gossip and the communication savings can be expressed as a function of the maximum number of neighbors in the network.Then we move on to studying the problem of reaching consensus on a high-dimensional vector. Although consensus on the entries of a vector can be achieved by running gossip in parallel for each entry, this can be wasteful when only few entries of the vector are significant. This thesis presents threshold and top-m selective gossip algorithms which aim to reach a consensus only on the significant entries of the consensus vector. Both algorithms focus communication resources at each update on exchanging only the significant entries of the local vectors. We prove that such myopic updates identify the significant entries of the consensus vector successfully. Using these algorithms, we propose novel approaches to decentralized compression and distributed particle filtering in wireless sensor networks. Numerical experiments demonstrate communication savings over existing methods.The methods proposed in this thesis are appropriate alternatives to randomized gossip because they do not require additional information to be transmitted beyond local neighborhoods. Taken together our results indicate that it is possible to decrease the communication overhead of randomized gossip while preserving its attractive properties.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.