Smart camera networks (SCNs) are increasingly used in applications such as homeland security, border control and traffic monitoring. The cameras are often wireless with an organically growing structure, to reduce the overhead of deployment. We frame a new and important problem in SCNs: how to transmit videos from multiple cameras with overlapping coverage given the limited available wireless bandwidth to maximize the quality of the received videos. We call this problem Coordinated Transport of Correlated Videos (CTCV). CTCV is a more general version of 3D video transport: in that problem, highly correlated videos from two cameras (that provide the 3D perspective) are jointly encoded exploiting their pre-defined and known overlap. In contrast, in CTCV there is an arbitrary number of cameras whose overlap is not known apriori and that require transmission as multiple video streams. To effectively support CTCV, we propose a video delivery protocol that consists of two primary components: (1) Consolidation of correlated videos from multiple cameras which removes spatially redundant fields-of-view; and (2) Network and coverage aware bandwidth allocation to optimize coverage quality cooperatively among the different video streams to match the available bandwidth. We formulate the problem of optimal bandwidth allocation for maximizing coverage. We propose and investigate different heuristic policies for bandwidth allocation. We evaluate CTCV using data from a small camera testbed as well as topologies from realistic deployments. Experiments show that CTCV achieves around 10 dB gains in video quality in the scenarios we consider.

Given the changing dynamics of mobility patterns and rapid growth of cities, transport agencies seek to respond more rapidly to needs of the public with the goal of offering an effective and competitive public transport system. A more data-centric approach for transport planning is part of the evolution of this process. In particular, the vast penetration of mobile phones provides an opportunity to monitor and derive insights on transport usage. Real time and historical analyses of such data can give a detailed understanding of mobility patterns of people and also suggest improvements to current transit systems. On its own, however, mobile geolocation data has a number of limitations. We thus propose a joint telco-and-farecard-based learning approach to understanding urban mobility. The approach enhances telecommunications data by leveraging it jointly with other sources of real-time data. The approach is illustrated on the First- and last-mile problem as well as route choice estimation within a densely-connected train network.

We handle the problem of efficient user-mobility driven macro-cell planning in cellular networks. As cellular networks embrace heterogeneous technologies (including long range 3G/4G and short range WiFi, Femto-cells, etc.), most traffic generated by static users gets absorbed by the short-range technologies, thereby increasingly leaving mobile user traffic to macro-cells. To this end, we consider a novel approach that factors in the trajectories of mobile users as well as the impact of city geographies and their associated road networks for macro-cell planning. Given a budget k of base-stations that can be upgraded, our approach selects a deployment that improves the most number of user trajectories. The generic formulation incorporates the notion of quality of service of a user trajectory as a parameter to allow different application-specific requirements, and operator choices. We show that the proposed trajectory utility maximization problem is NP-hard, and design multiple heuristics. We evaluate our algorithms with real and synthetic datasets emulating different city geographies to demonstrate their efficacy. For instance, with an upgrade budget k of 20%, our algorithms perform 3-8 times better in improving the user quality of service on trajectories when compared to greedy location-based base-station upgrades.

We consider the problem of target coverage in visual sensor networks with Pan-Tilt-Zoom (PTZ) cameras. The finely controllable movement in PTZ dimensions creates a large number of possible Field-of-View (FoV) settings, making it prohibitively expensive to consider them all in coverage algorithms. However, these FoVs are redundant as each group of targets is generally covered by many FoVs. Thus, an important problem is, how to identify FoVs that cover all maximal subsets of targets (MaxFoV) efficiently? We show that MaxFoV is an instance of generating all maximal cliques, which is NP-hard in general but polynomial if the number of cliques is polynomial. We construct an optimal algorithm to solve the problem with a worst case complexity of O(n3). Simulation and testbed experiments show that the algorithm drastically reduces the number of FoVs allowing multi-camera coverage to scale without sacrificing coverage quality.

Carrier Sense Multiple Access (CSMA) protocols are unable to effectively arbitrate the medium in wireless networks; problems such as hidden and exposed terminals occur frequently leading to collisions, poor performance and unfairness. CSMA networks can be optimized by careful tuning of transceiver parameters, such as transmission power and carrier sensing threshold, to maximize spatial reuse of wireless channel while minimizing collisions. However, existing studies fail to jointly optimize these parameters to eliminate collisions and maximize spatial reuse. Our approach leverages on the observation that links under CSMA interfere in one of the few discrete interaction modes; each mode leads to different behavior in terms of performance and fairness. The proposed methodology controls the transceiver parameters to convert destructive interaction modes (such as various types of hidden terminals) into constructive ones; we call this approach Interaction Engineering (IE). In this paper, we first formulate a model and centralized algorithm that computes the parameters based on one-to-one interaction between the links. We then develop a distributed IE protocol. We evaluate the protocols under Wireless LAN and multi-hop wireless networks using both simulation and testbed. We show that IE eliminates a vast majority of the collisions and significantly boosts spatial reuse. For example, in the WLAN scenarios, we observed a median improvement of 4x in throughput and more than 2.5x improvement in fairness, and orders of magnitude improvement in connection delay and jitter. IE also shows significant improvements in multi-hop networks, and under different forms of traffic such as video and TCP.

Hidden Markov Models (HMMs) based map matching - that matches a sequence of location samples to a road network - has received a lot of traction in recent years. In this paper we revisit the basic assumption underlying HMM-based map matching algorithms, namely, the hypothesis that the true mobility is Markovian. We use the Chapman-Kolmogorov test and argue that mobility is non-Markovian (especially when the moving object has an intent to reach a specific destination) using thousands of real taxicab mobility datasets spanning several weeks. Based on these observations we present an alternate approach to the map matching problem that relies exclusively on shortest path computations, which are at most linear in the number of road segments, and thus avoids expensive complexity of HMM-based map matching algorithms (e.g., using a Viterbi decoder). We present extensive experimental results to show that our approach vastly outperforms HMM-based approaches in terms of both computational complexity and accuracy.

We design and implement a novel system called Async, which enables a mobile network operator (MNO) to efficiently manage the growth of mobile data by leveraging the delay-elastic nature of certain applications and the price-sensitive nature of certain users. Specifically, Async introduces an alternate “asynchronous” content-delivery paradigm for heavy content (e.g., videos), and facilitates an MNO to negotiate with users a delay in delivery in exchange for appropriate incentives. The MNO uses the negotiated delays to actively manage Async flows to reduce congestion and improve the quality-of-experience (QoE) of both delayed and regular flows. We show that in comparison to state-of-the-art, Async's network-based flow management enhances QoE for more than 30% of the regular flows, with up to 60% improvement in per-flow QoE metric, while still meeting the negotiated delivery times of 95% of the delayed flows. Async also lowers the delivery times of delayed flows by ∼67% and significantly increases robustness to traffic unpredictability. Our design is robust to disconnections and does not require any modifications to existing network infrastructure and protocols. Our prototype deployment (using Apache's mod_proxy and an Android app) on live networks confirms Async's efficacy in meeting EDTs for diverse deployment scenarios.

In this work, we demonstrate the design and implementation of a novel system called Async, which enables a mobile network operator (MNO) to efficiently manage the growth of mobile data. For this, we enable an opportunistic delivery model for the MNOs by leveraging the delay-elastic nature of certain applications such as video downloads, and the price-sensitive nature of certain users. Specifically, in Async, we enable an alternate content delivery paradigm that facilitates an MNO to control when, and at what price, the content is delivered to the users. In our system, users can select a price and expected delivery time (or EDT) option from a multitude of choices. We develop a prototype of such a system by extending Apache's mod_proxy module and by developing a service on the Android platform without requiring any modifications to existing network infrastructure or protocols. We demonstrate two applications using such a service: (1) download of large files, e.g., software updates, movie files, and (2) an educational App that downloads educational content on mobile devices.

Carrier Sense Multiple Access (CSMA) protocols are unable to effectively arbitrate the medium in multi-hop wireless networks; problems such as hidden and exposed terminals occur frequently leading to collisions, poor performance and unfairness. CSMA networks can be optimized by careful tuning of transceiver parameters, such as transmission power and carrier sensing threshold, to maximize transmission concurrency while minimizing collisions. Existing approaches optimize these parameters by considering only some aspects of CSMA operation (e.g., considering only PHY parameters such as SINR), thus leading to suboptimal solutions. We present a new approach that leverages recent insights into the behavior of CSMA networks. Specifically, this recent work identifies that links interfere only in a few discrete interaction modes at the MAC-layer. Each interaction mode determines how the interacting links interfere with each other and leads to different performance and fairness behavior. The proposed methodology controls the transciever parameters to convert the destructive interactions into constructive ones; we call this approach Interaction Engineering. The global optimization problem is computationally infeasible and requires central solution. Therefore, we first formulate an interaction engineering model that computes the parameters based on one-to-one interaction between the links. Second, we extend the model into a distributed interaction-aware MAC protocol (I-MAC). Testbed and simulation results show that collisions and retransmissions are almost completely eliminated, leading to large improvements in throughput and delay.

Carrier Sense Multiple Access (CSMA) based MAC protocols induce several types of harmful interactions, such as hidden and exposed terminals, in wireless networks. Existing routing protocols do not consider the effect of these MAC interactions on route quality, leading to the selection of inefficient routes. We propose a MAC Interaction Aware Routing Metric (MIAR) that explicitly accounts for MAC interactions among the links forming a route. The protocol favors routes with links that have better interactions and avoids ones with detrimental interactions. We compare the performance of the proposed metric with an existing shortest-path routing protocol and show that our metric substantially improves the performance and efficiency of the network.

Network flow models serve as a popular mathematical framework for the analysis and optimization of multi-hop wireless networks. They also serve to provide the understanding necessary to derive effective distributed protocols. However, the high computational complexity of realistic models restrict the translation of theoretical insights into distributed protocols. In this paper, we consider an NP-hard, mixed integer linear programming based routing model that computes single-path routes in a wireless network. We propose an efficient, polynomial time algorithm that applies domain specific heuristics to reduce the complexity. We employ a decomposition based approach to break the monolithic problem into several sub-problems that cooperate to find near-optimal routes. The sub-problem structure is chosen such that it captures the optimal route discovery process between a source and destination; this is a design principle that can be directly used in distributed routing protocols. We show that the resulting formulation achieves orders of magnitude improvement in the run-time. Simulation results show that the routes derived from the model are effective even in practical wireless networks with commonly used protocol stack.

Estimation of the available capacity in a multiple hop route in cognitive radio networks is challenging. Several complex problems like channel assignment, interference estimation and routing effects needs to be addressed. In this demonstration, we exhibit a capacity estimation engine that determines the available capacity of the routes in a dynamic cognitive radio network using USRP and WARP software-defined radios. In addition to the available capacity, we show the various types of MAC interference and its effect in the network. The tool demonstrates a fundamental capacity estimation block, which provides valuable input to higher level applications like routing, network provisioning and monitoring. A scheduling aware routing algorithm that exploits the capacity estimation engine and scheduling interactions is shown as an example application.

In multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This paper focuses on the unfairness arising due to unequal contention opportunities at a node; some nodes rarely observe an idle channel since two or more interferers that are not in range with each other can transmit together. Contention unfairness is unrelated to hidden terminals. In order to understand the impact of contention and gain insight into developing solutions for contention unfairness, we develop a model from first principles for contention in IEEE 802.11 networks. The accuracy of the model is validated through simulations and the results show that such unfairness is a common phenomenon. Based on the insights gained from the model, we propose and evaluate a distributed scheme that reduces the effect of unfairness due to contention. Simulation results show that the proposed scheme achieves an average improvement of 25% in fairness, with a small reduction in overall throughput.

In a Multi-hop Wireless Networks (MHWN), packets are routed between source and destination using a chain of intermediate nodes; chains are a fundamental communication structure in MHWNs whose behavior must be understood to enable building effective protocols. The behavior of chains is determined by a number of complex and interdependent processes that arise as the sources of different chain hops compete to transmit their packets on the shared medium. In this paper, we show that MAC level interactions play the primary role in determining the behavior of chains. We evaluate the types of chains that occur based on the MAC interactions between different links using realistic propagation and packet forwarding models. We discover that the presence of destructive interactions, due to different forms of hidden terminals, does not impact the throughput of an isolated chain significantly. However, due to the increased number of retransmissions required, the amount of band-width consumed is significantly higher in chains exhibiting destructive interactions, substantially influencing the over-all network performance. These results are validated by testbed experiments. We finally study how different types of chains interfere with each other and discover that well behaved chains in terms of self-interference are more resilient to interference from other chains.

Chains or multi-hop paths are the fundamental communication structure in multi-hop wireless networks. Understanding chain behavior is critical in order to build effective higher layer protocols. This paper examines the problem of how MAC level interactions influence chain behavior in a general multi-hop wireless network where multiple chains coexist. We first classify chains based on the MAC interactions observed between its hops when there is no external traffic. Then we identify the interactions across two interfering chains for the most common categories of chains. We study the probability of occurrence, and estimate the effect of MAC interactions on the performance of the chains. We also show that different chains exhibit different transmission patterns; this is an effect that is necessary for accurately estimating chain performance. We observe that destructive interactions arise more frequently among two interfering chains than they do within a single chain. Moreover, chains that have hidden terminals due to self-interference are more prone to have cross-chain hidden terminals. Thus, both intra-chain as well as cross-chain interactions, ultimately provide significant insight into how chains interact.

Carrier Sense Multiple Access (CSMA) protocols in Multi-hop Wireless Networks (MHWN) are known to suffer from different forms of hidden and exposed terminal problems, leading to inefficiency and unfairness. Recent studies have formally characterized the fundamental interactions in the IEEE 802.11 protocol by classifying and quantifying the possible interactions that arise between two interfering single hop links. However, existing studies use a simple disc based propagation model, which does not model the effect of interference accurately in the presence of capture. This paper advances this line of study by developing the analysis and performance models for the two-flow interference problem using a Signal-to-Interference-Noise (SINR) based propagation model with large scale fading. This model has been experimentally shown to accurately predict the performance in wireless testbeds. The analysis identifies four previously unknown categories of interactions, and affects the probability of occurrence of the other categories. Moreover, using a SINR model allows us for the first time to characterize the incidence of the exposed terminal problem. The paper proposes closed form expressions to estimate the probability of occurrence of each category. We then propose throughput estimation models for the frequently occurring new categories and validate them against simulation. We believe that collectively these contributions provide a substantial improvement in our understanding of the effect of interference from first principles, which is a vital step in developing protocols that account for it.

Network flow models have proven to be an effective tool in the analysis, optimization and design of network protocols. Critical to the success of these models in general multi-hop wireless networks (MHWNs) is an accurate estimation of the effect of CSMA scheduling. While the existing models capture coarse grained estimates of interference, they do not account for the substantial impact of MAC scheduling. On the other hand, accurate models of throughput in CSMA networks exist. However, they are unsuitable for use as a part of a network flow formulation because of their complexity and some of their underlying assumptions. This paper contributes an efficient and constructive model to estimate the effect of scheduling on interfering links in general MHWN settings. We integrate this approach with a network flow routing model which works with aggregate estimates of capacity to improve the quality of the solution. Simulation results show that accounting for scheduling effects leads to large improvements in the quality of the solution.

We formulate the real-time routing problem in static multi-hop wireless networks as an optimization problem, whose solution is the optimal routes relative to an end- to-end delay based objective. The problem is formulated as a mixed integer linear program. The variance of the delay with respect to the aggregate interference measures is empirically studied and a linear approximation is proposed. We show that this formulation yields routes that significantly outperform the best routes obtained by OLSR. Finally, we discuss the applications of such a model both in terms of capacity analysis, on-line algorithms for static scenarios, and extensions to allow the development of distributed protocols that solve the optimization problem.

Routing in multi-hop wireless networks is typically greedy, with every connection attempting to establish a path that minimizes its number of hops. However, interference plays a major role in limiting the capacity of such networks; this effect is ignored by most existing protocols. It is likely that approaches that coordinate routing to account for mutual interference would be able to achieve better performance than traditional approaches. Modeling routing with interference constraints is a complex non-linear optimization problem. We approach the problem using a multi commodity flow (MCF) formulation. We analyze the interaction of multiple routes and propose effective objective functions which attempt to maximize interference separation while limiting path inflation. Initial experimental results show significant improvement in performance over a traditional routing protocol. We evaluate the formulation against routes obtained using DSR under several scenarios and show that better performance is achieved in terms of throughput, goodput, and end-to-end delay

Localization is a fundamental operation in mobile and self-configuring networks such as sensor networks and mobile ad hoc networks. For example, sensor location is often critical for data interpretation. Existing research focuses on localization mechanisms: algorithms and infrastructure designed to allow the sensors to determine their location. In a mobile environment, the underlying localization mechanism must be invoked repeatedly to maintain accurate location information. We propose and investigate adaptive and predictive protocols that control the frequency of localization based on sensor mobility behavior to reduce the energy requirements for localization while bounding the localization error. In addition, we evaluate the energy-accuracy tradeoffs. Our results indicate that the proposed protocols reduce the localization energy significantly without sacrificing accuracy.

Route discovery in reactive routing protocols for MANETs use flooding to disseminate route requests. Such operations rely on MAC level broadcasts to reach all nearby nodes without prior knowledge of their identity. For networks with directional antennas, this creates the following challenge: only neighbors in omni-directional range are discovered, leading to long paths and suboptimal operation. To address this problem sweeping directional MAC broadcasts are often used. Sweeping broadcasts have a high overhead; in addition, we observe that they can cause suboptimal route discovery, especially under high loads. To address these shortcomings, we propose a new directional route discovery approach called route compaction. Route compaction relies on enhanced version of omni-directional route discovery to find paths, avoiding the problems with sweeping broadcast. Route compaction then attempts to compact routes by replacing multiple hops with a single directional hop whenever possible. Our experiments show that this approach provides excellent directional route discovery capability at a lower overhead than sweeping broadcast.

In existing directional MAC protocols a single queue is used at the MAC layer; this is inherited from omnidirectional implementations. However, while there is a single channel state in omnidirectional transmission (either the channel is busy or not), the state of the channel varies with the desired direction of transmission in directional antennas. Thus, existing implementations which use a single FIFO queue potentially lead to head of line blocking if the medium is busy in the direction of the packet at the top of the queue but is available in other directions. We propose a new queuing organization which could take advantage of the channel more effectively using the underlying antenna system by eliminating head of line blocking. We also identify a problem with the directional virtual carrier sense implementation due to side-lobes and provide a solution to it. Our results indicate that by using a greedy approach, to schedule the packet which has the least wait time, increases the overall throughput and reduces end-to-end delay considerably, especially under heavy loads.