Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
The performance of distributed consensus algorithms, in terms of convergence time, depends significantly on the underlaying communication graph. As an example, two dimensional geographic graphs, where nodes are connected only to some nearest neighbors give slow convergence, since it takes long time to propagate information from one end of the area to the other. Adding longer links to such a network graph decreases the convergence time for a given network and changes the scalability properties as well, the convergence time increases linearly to the number of nodes in the geographic graph, while the increase is logarithmic if random long links are added.
Considering however the shared wireless medium, adding long communication links, that is, transmissions with high transmission power, have significant price, these transmissions introduce interference in a larger geographic area. Moreover, transmission to longer distances cost more energy, which can be a problem if the nodes have limited energy resources. Therefore, the scheduling of the transmissions, that is, the medium access control, and energy consumption have to be carefully considered when evaluating the performance of distributed consensus in wireless environment.
The complex networks literature has significant results on how to design network topologies that can achieve good graph properties in terms of network diameter, connectivity, or, the property that is of high importance in the case of distributed consensus, the spectral radius. However, these works do not address the limitations of wireless networks.
In this thesis we evaluate the performance of distributed, discrete time consensus in heterogeneous wireless networks. We consider the possibility of deploying a couple of nodes with high transmission power and good energy resources in the otherwise energy and transmission power limited wireless mesh network. We evaluate the performance of the consensus algorithm in terms of energy consumption and consensus delay, considering the generic path loss model, and a hypothetic MAC protocol to control the access to the shared wireless medium. We show that the heterogeneous network can achieve a performance that is comparable to the one of a homogeneous network with nodes that transmit with higher transmission power, and consequently, the heterogeneous network structure can efficiently decrease the power consumption of the low power nodes.