Interference-aware Distributed Algorithms

This project is aimed at designing interference-aware distributed algorithms for classical problems in multi-hop wireless networks. The researchers found that time rounds used to measure time complexity in classical distributed algorithms (namely time rounds) does not fit such scenario. In each time round, the actual time may contain a large portion of handshaking or waiting time in order to deal with interference. Moreover, the handshaking or waiting time, depending on different network topologies, may vary significantly. In this project, the researchers consider the actual time, instead of time rounds, in designing our algorithms.The researchers introduce a powerful tool to be used in designing interference-aware distributed algorithms: the virtual backbone, which can often be applied in the following way. Given a classical problem and a network topology, the researchers can construct a virtual backbone first. Then they consider the sub-problem restricted to the virtual backbone and apply those distributed algorithms to obtain a solution in terms of time rounds. Finally, each time round is mapped to actual time slots in the wireless network and the algorithm therefore becomes interference-aware.In this project, the first objective is directly to design an interference-aware virtual backbone construction algorithm that has low latency and energy consumption. The second goal is to design a mapping, called the interference-aware mapping (IAM) that maps each time round in the virtual backbone to a transmission schedule (that uses time slots) in the original network. In one time round, each node in the backbone will do a 1-hop communication with all of its neighbors. The third goal is to apply these results to lots of classical distributed algorithms such as leader election, distributed consensus problem, shortest path, and many others. This project is expected to have impact on most classical distributed algorithms. The researchers believe that, through this study, they can make plenty of classical distributed algorithms interference-aware (and thus more practical).The models to be used to analyze those problems and design algorithms will first be the unit disk graph (UDG) model. After achieving these three goals, the researchers will use the more practical signal-to-interference- noise ratio (SINR) model. The researchers believe that the UDG model is a good starting point. Finally, as an ultimate goal, the researchers seek to use these results to bridge the gap between theory (classical distributed algorithms) and practice (real wireless scenarios) and therefore give contribution to the research area of wireless networks in Hong Kong.