We consider the problem of distributing time-sensitive information from a collection of sources to mobile users traversing a wireless mesh network. Our strategy is to distributively select a set of well-placed nodes (warehouses) to act as intermediaries between the information sources and clusters of users. Warehouses are selected via the distributed construction of Hierarchical Well-Separated Trees (HSTs), which are sparse structures that induce a natural spatial clustering of the network. Unlike many traditional multicast protocols, our approach is not data driven. Rather, it is agnostic to the number and position of sources as well as to the mobility patterns of users. Whereas source-rooted tree multicast algorithms construct a separate routing infrastructure to support each source, our sparse and flexible infrastructure is precomputed and efficiently reused by sources and users, its cost amortized over time. Moreover, the route acquisition delay inherent in on-demand wireless ad hoc network protocols is avoided by exploiting the HST addressing scheme. Our algorithm ensures with high probability a guaranteed stretch bound for the information delivery path, and is robust to lossy links and node failure by providing alternative HST-induced routes. Nearby users are clustered and their requests aggregated, further reducing communication overhead.

We propose an interference-aware MAC protocol using a simple transmission strategy motivated by a game- theoretic approach. We formulate a channel access game, which considers nodes concurrently transmitting in nearby clusters, incorporating a realistic wireless communication model - the SINR model. Under inter-cluster interference, we derive a decentralized transmission strategy, which achieves a Bayesian Nash Equilibrium (BNE). The proposed MAC protocol balances network throughput and battery consumption at each transmission. We compare our BNE-based decentralized strategy with a centralized globally optimal strategy in terms of efficiency and balance. We further show that the transmission threshold should be adaptively tuned depending on the number of active users in the network, crosstalk, ambient noise, transmission cost, and radio-dependent receiver sensitivity. We also present a simple dynamic procedure for nodes to efficiently find a Nash Equilibrium (NE) without requiring each node to know the total number of active nodes or the channel gain distribution, and prove that this procedure is guaranteed to converge.

We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.