Adding more PHY to the MAC: Exploiting Physical Layer Effects in Wireless Networks (Series in Distributed Computing)

Traditional wireless algorithms all too often ignore the special qualities of the wireless medium. In this thesis, we propose new wireless transmission primitives for various applications and evaluate each of them on a wireless sensor network. In particular, we focus on integrating two properties into our primitives: the availability of transmission power control and the capture effect. First, we consider the problems of traffic prioritization and running multiple wireless algorithms in parallel. We propose a technique allowing to simultaneously run multiple algorithms of different priorities, with minimal overhead in terms of bandwidth and latency. This is done by assigning each priority a range of admissible received signal strengths at each node, and employing the capture effect to automatically enable reception of only the strongest incoming signal. The setup is transparent to the algorithms: each appears to have complete access to the network's resources as long as no algorithm of a higher priority wishes to use them. We discuss which properties of the network graph and the wireless hardware are beneficial to our technique. Second, we demonstrate the feasibility of achieving constructive interference using commodity wireless sensor nodes. In contrast to previous work, our technique does not rely on global external events as reference, but instead aims to minimize the errors in clock synchronization and transmission timing. Our evaluation shows that our technique is able to achieve constructive interference in over 30% of cases, even after multiple minutes of sleep. Third, we propose a class of transmission primitives which decouple packets' synchronization headers from their payloads, such that two or more different senders may contribute to a single received packet. We explore 2 applications: 1) enabling reception attempts of very weak packets, e.g., across a network chasm, and 2) the injection of shorter packets into longer ongoing transmissions. We investigate ways to vastly reduce the problems incurred by using a mismatching synchronization header for reception. In practice, we are able to successfully decode up to 30% of cross-chasm packets and up to 70% of injected packets. Fourth, we examine how transmission power control can improve wireless schedules. Based on the classic RAND scheduling algorithm we develop a version employing power control called PowerRAND. The schedules generated by PowerRAND are 20-25% shorter, i.e., achieve a 25-33% higher throughput than RAND. Our practical evaluation shows that these schedules are just as feasible in practice. Further, we discuss how power control provides flexibility to schedules in the face of changing environments.

Michael König received his M. Sc. degree in computer science from ETH Zurich, Switzerland, in 2012. In 2012 he joined the Distributed Computing Group of Professor Roger Wattenhofer at ETH Zurich as a Ph.D. student and research assistant. In 2017 he earned his Ph.D. degree for his work on wireless transmission primitives and network algorithms.