Mobility in wireless networks: friend or foe : network design and control in the age of mobile computing

Wireless networking technologies allow computing devices to move while keeping them online, but the device mobility poses considerable technical challenges. Network designers, on the one hand, consider mobility to be harmful because it leads to dynamic and unpredictable links among devices. Compared with traditional wired networks, it indeed becomes much more difficult to design network control functions, such as routing path maintenance, in an efficient way under mobility. On the other hand, some researchers also realize that, by involving mobility into network design (i.e., controlling mobility in a desirable way), mobility can improve the performance of wireless networks. Inspired by these two seemingly contradictory thoughts, we focus this thesis on the understanding, tackling, and exploiting of mobility in wireless networks. In the first part of this thesis, we take an antagonistic view on mobility and try to cope with its harm. We are concerned with the design of reliable protocols that support many-to-many communications (also called group communication service) under random node mobility constraints in mobile ad hoc networks. Our approach deviates from the conventional point of view (where protocols tend to predict the consequence of mobility and adapt to it), i.e., we "fight fire with fire" by exploiting the non-deterministic nature of ad hoc networks. In line with this concept, we propose a group communication system, PILOT, that guarantees reliability in a probabilistic manner. PILOT includes Route Driven Gossip (RDG, a probabilistic multicast protocol) and two services built upon: Probabilistic quorum systems for ad-hoc networks (PAN) to provide reliable storages and Reliable RDG (R2DG) for supporting multicast streams. Our proposal is innovative because 1) it makes reliable group communication service available in ad hoc networks, and 2) it also provides predictability of the service such that we can fine tune the protocol parameters to obtain the desired tradeoff between reliability and overhead. In addition, we also demonstrate the application of PILOT by proposing a distributed certification authority, DICTATE, that makes use of its services. In the second part of this thesis, we look at the favorable aspects of mobility. We involve controllable mobility in designing energy-conserving protocols in static wireless networks (in particular wireless sensor networks). We observe that the many-to-one transmission style in sensor networks poses a major threat to the network lifetime, because the sensor nodes located near a sink have to relay data for a large part of the network and thus deplete their batteries very quickly. Existing energy efficient/conserving routing protocols cannot completely solve the problem as they only balance the load among nodes whose distances from a sink are roughly the same. Inspired by a recent trend of using mobile sinks in sensor networks, we propose a solution that suggests the sinks be mobile; in this wa