In this paper, we develop the first rigorous distributed algorithm for link scheduling in the SINR model under any length-monotone sub-linear power assignments. Our algorithms give constant factor approximation guarantees, matching the bounds of the sequential algorithms for these problems, with provable bounds on the running time in terms of the graph topology. We also study a related and fundamental problem of local broadcasting for uniform power levels, and obtain similar bounds. These problems are much more challenging in the SINR model than in the more standard graph based interference models, because of the non-locality of the SINR model. Our algorithms are randomized and crucially rely on physical carrier sensing for the distributed communication steps. We find that the specific wireless device capability of duplex/halfduplex communication significantly impacts the performance. Our main technique involves the distributed computation of affectance and a construct called a ruling, which are likely to be useful in other scheduling problems in the SINR model. We also study the empirical performance of our algorithms, and find that the performance depends on the topology, and the approximation ratio is very close to the best sequential algorithm.

We describe a first principles based integrated modeling environment to study urban socio-communication networks which represent not just the physical cellular communication network, but also urban populations carrying digital devices interacting with the cellular network. The modeling environment is designed specifically to understand spectrum demand and dynamic cellular network traffic. One of its key features is its ability to support individual-based models at highly resolved spatial and temporal scales. We have instantiated the modeling environment by developing detailed models of population mobility, device ownership, calling patterns and call network. By composing these models using an appropriate in-built workflow, we obtain an integrated model that represents a dynamic socio-communication network for an entire urban region. In contrast with earlier papers that typically use proprietary data, these models use open source and commercial data sets. The dynamic model represents for a normative day, every individual in an entire region, with detailed demographics, a minute-by-minute schedule of each person's activities, the locations where these activities take place, and calling behavior of every individual. As an illustration of the applicability of the modeling environment, we have developed such a dynamic model for Portland, Oregon comprising of approximately 1.6 million individuals. We highlight the unique features of the models and the modeling environment by describing three realistic case studies.

We study the problem of throughput maximization in multihop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O(log Δm/loglog Δm) of the maximum, so that the per-session (end-to-end) delay is O(((log Δm/loglog Δm)Δ(c))2), where Δm=maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.

Designing efficient scheduling and power control algorithms for distributed wireless communication has been a challenging issue, especially in the physical interference model based on SINR constraints. In this paper, we discuss the first local distributed scheduling and power control algorithm in the SINR model that achieves an O(g(L)) approximation factor of the rate region, where O(g(L)) denotes the link diversity. As an intermediate step, we develop a scheduling algorithm in a k-hop interference model, which is used in the analysis of the more general model. Our algorithms are based on random-access and use local queue size information. Exchanging queue size information is challenging, and the complexity of this step is often ignored in prior local distributed algorithms. A novel aspect of our paper is the use of stale and infrequently updated queue size info, which significantly improves the complexity of our algorithms.

We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (equation) of the maximum, so that the per-session (end-to-end) delay is O (equation), where Δm= maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.

Publish/Subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this article, we present, evaluate benefits of, and compare with past work an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.

We investigate the construction of greedy embeddings in polylogarithmic dimensional Euclidian spaces in order to achieve scalable routing through geographic routing. We propose a practical algorithm which uses random projection to achieve greedy forwarding on a space of dimension O(log(n)) where nodes have coordinates of size O(log(n)), thus achieving greedy forwarding using a route table at each node of polylogarithmic size with respect to the number of nodes. We further improve this algorithm by using a quasi-greedy algorithm which ensures greedy forwarding works along a path-wise construction, allowing us to further reduce the dimension of the embedding. The proposed algorithm, denoted GLoVE-U, is fully distributed and practical to implement. We evaluate the performance using extensive simulations and show that our greedy forwarding algorithm delivers low path stretch and scales properly.

In unreliable and untrustworthy systems, information dissemination may suffer network failures and attacks from Byzantine nodes which are controlled by traitors or adversaries, and can perform destructive behaviors. Typically, Byzantine nodes together or individually "swallow" messages, or fake disseminated information. In this paper, we present an authentication-free, gossip-based real-time information dissemination mechanism called RT-LASIRC, in which "healthy" nodes utilize Byzantine features to defend against Byzantine attacks. We show that RT-LASIRC is robust against blackhole and message-faking attacks. Our experimental studies verify RT-LASIRC's effectiveness.

In this paper, we present a reliable real-time data delivery (communication) mechanism for ad-hoc networks, called RTRD. The mechanism makes use of a proactive wireless routing protocol (DSDV) for path finding and maintenance, and timely delivers data through a priori bandwidth reservation. In addition, to be robust to network failures, or to deliver large data chunks, it simultaneously delivers data in multiple paths. The simulation results conducted by NS-2 validate RTRD's effectiveness.