Algorithmic Foundations of Wireless Communication Networks

The last years have seen an ever growing interest in wireless communication networks and their applications. Nowadays, wirelesscommunication devices are omnipresent in our lifes. Already today, for many of us, living without being able to make phone calls, sendmessages, or even access the Internet almost always and everywhere is hard to imagine. In addition to well-established technologies such as cellular networks (i.e., mobile phones) or WLAN that are based on a fixed, stationary network infrastructure, also new, more decentralized application scenarios are emerging and will become increasingly important. Over the last decade, specifically, wireless ad hoc and sensor networks have received a lot of attention. These are potentially large-scale (in terms of number of devices and of coveredarea) networks that are formed by autonomous nodes. Communication is directly between nodes via wireless radio without relying onadditional infrastructure.From an algorithmic point of view, systems based on wireless communication pose unique challenges that are not present in standardwired networks. In particular, traditional network models based on point-to-point links are not valid in the wireless world because in awireless network, the communication medium has to be shared by all participants and consequently, transmissions can collide andinterfere. Further, especially in the context of mobile ad hoc and sensor networks, there are numerous additional interesting andchallenging questions. Wireless networks are potentially large and decentralized, so that the coordination of the autonomous networknodes is difficult. Coordination becomes especially non-trivial if nodes move and the network topology becomes dynamic. Sensor networks might consist of a large number of simple, small, battery-operated devices. Achieving the required goals while keeping the energy consumption low, therefore is another imminent and important requirement in such a setting.The study of algorithms and lower bounds for wireless radio networks is further complicated by the diversity and complexity of possibleassumptions about the networks’ behavior. Devices may have clocks that are exactly, or approximately synchronized. Devices may operate in slots or asynchronously. Devices and communication may be subject to various types and amounts of failure. Simultaneous transmission may cause collisions, which might or might not be detected by message senders or receivers. Message reception may be determined by geographical distance or by more complex criteria such as signal-to-noise ratio. Devices may move, under any of a variety of mobility constraints. This situation causes problems. Results for one set of network assumptions might prove invalid for a slightlydifferent set of assumptions. Moreover, these low-level assumptions require algorithm designers to grapple with low-level problems such as contention management, again and again, making it difficult to highlight interesting high-level algorithmic issues. In this project, we plan to extend the algorithmic foundations of wireless networks and investigate the above mentioned challenges. Wewill focus on three main directions: 1) We want to understand the inherent complexity of basic tasks under the various assumptions. Particularly, we are interested in the effects of unreliable links and network components; 2) We propose to simplify the study of algorithms and lower bounds for wireless networks by defining simple abstract models for Medium Access Control (MAC) layers. Ourmain goal is to separate low-level contention management issues from solving the actual high-level problem; 3) We will study the complexity of basic network problems in the presence of mobile nodes and more general dynamic networks.