We conduct an extensive measurement study in an operational cellular network in dense urban settings and identify two key sources of inefficiencies in standard 3GPP handoff technique: wrong timing of handoff and sub-optimal base station association at a point. Based on our study, we propose a novel handoff technique that leverages (1) historical geo-tagged signal strength data from visible base stations at typical mobile user locations and (2) knowledge of the user trajectory. First, we formulate the handoff problem as a bi-criteria optimization problem and present a dynamic programming formulation that provides pareto-optimal solutions that maximize overall signal strength along user trajectory for a range of handoffs. Using an efficient utility based selection technique, we select a solution that balances the tradeoff between reducing number of handoffs and increasing the overall signal strength experienced by the user. Next, we present a much faster greedy heuristic that augments the solution obtained from the dynamic programming formulation when optimizing user performance in the presence of dynamic network load at each base station. A key contribution of our work is to show that striking a tradeoff between the two objectives is much harder in dense macro cellular base station deployments and an effective handoff technique should balance both these objectives well. We show that our technique takes a well balanced approach and achieves more than 25% reduction in the number of handoffs over the standard 3GPP handoff technique in an operational cellular network without incurring reduction in average signal strength, and even improving it by 1dB/sec in some cases. Finally, we propose a novel 3GPP standards compliant trajectory-aware location based handoff protocol and discuss the practical implementation aspects in cellular networks.

In this paper, we study the problem of efficient video delivery over the cellular downlink. The key objective is to maximize the Quality of Experience (QoE) of the user, as measured by application level metrics such as the buffering ratio and low bit rate ratio. We present a two-tiered solution with a standard base-station scheduler that works on a per-packet basis and a Video Management System (VMS) that works at the granularity of thousands of video frames. The video management system uses knowledge of the video playout curves and future channel states to develop a scheduling policy that is feasibility optimal. The algorithms are simple and leverage recent results on real-time scheduling in wireless networks. We evaluate the performance of our algorithms using real video traces and a standard channel model. The VMS ensures that the per-user QoE guarantees are maintained, as compared with a standard PF scheduler that is oblivious to application level QoE requirements.

We consider collocated wireless sensor networks, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and the goal of the network is to compute a given Boolean function of these measurements. We first consider the worst case setting and study optimal block computation strategies for computing symmetric Boolean functions. We study three classes of functions: threshold functions, delta functions and interval functions. We provide optimal strategies for the first two classes, and a scaling law order-optimal strategy with optimal preconstant for interval functions. We extend the results to the case of integer measurements and certain integer-valued functions. Next, we address the problem of minimizing the expected total number of bits that are transmitted when node measurements are random and drawn from independent Bernoulli distributions. In the case of computing a single instance of a Boolean threshold function, the problem reduces to one of determining the optimal order in which the nodes should transmit. We show that the optimal order of transmissions depends in an extremely simple way on the values of previously transmitted bits and the ordering of the marginal probabilities of the Boolean variables according to the k-th least likely rule: At any transmission, the node that transmits is the one that has the k-th least likely value of its Boolean variable, where k reduces by one whenever a node transmits a one. Initially the value of k is (n +1 - Threshold). Interestingly, the order of transmissions does not depend on the exact values of the probabilities of the Boolean variables. In the case of identically distributed measurements, we further show that the average-case complexity of block computation of a Boolean threshold function is O(θ), where θ is the threshold. We further show how to generalize to a pulse model of communication. One can also consider the related problem of approximate computation given a fixed number of bits. For the special case of the parity function, we show that the greedy strategy is optimal.

We consider the problem of information aggregation in sensor networks, where one is interested in computing a function of the sensor measurements. We allow for block processing and study in-network function computation in directed graphs and undirected graphs. We study how the structure of the function affects the encoding strategies and the effect of interactive information exchange. Depending on the application, there could be a designated collector node, or every node might want to compute the function. We begin by considering a directed graph C = (γ. ε) on the sensor nodes, where the goal is to determine the optimal encoders on each edge which achieve function computation at the collector node. Our goal is to characterize the rate region in R|ε|, i.e., the set of points for which there exist feasible encoders with given rates which achieve zero-error computation for asymptotically large block length. We determine the solution for directed trees, specifying the optimal encoder and decoder for each edge. For general directed acyclic graphs, we provide an outer bound on the rate region by finding the disambiguation requirements for each cut, and describe examples where this outer bound is tight. Next, we address the scenario where nodes are connected in an undirected tree network, and every node wishes to compute a given symmetric Boolean function of the sensor data. Undirected edges permit interactive computation, and we therefore study the effect of interaction on the aggregation and communication strategies. We focus on sum-threshold functions and determine the minimum worst case total number of bits to be exchanged on each edge. The optimal strategy involves recursive in-network aggregation which is reminiscent of message passing. In the case of general graphs, we present a cut-set lower bound and an achievable scheme based on aggregation along trees. For complete graphs, we prove that the complexity of this scheme is no more than twice that of the optimal scheme.

We address a sequential decision problem that arises in the computation of symmetric Boolean functions of distributed data. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements. We suppose that the measurements are independent and Bernoulli distributed. Thus, the problem of optimal computation becomes the problem of optimally ordering nodes' transmissions so as to minimize the total expected number of bits. We solve the ordering problem for the class of Boolean threshold functions. The optimal ordering is dynamic, i.e., it could potentially depend on the values of previously transmitted bits. Further, it depends only on the ordering of the marginal probabilites, but not on their exact values. This provides an elegant structure for the optimal strategy. For the case where each node has a block of measurements, the problem is significantly harder, and we conjecture the optimal strategy.

In this paper, we address the scenario where nodes with sensor data are connected in a tree network, and every node wants to compute a given symmetric Boolean function of the sensor data. We first consider the problem of computing a function of two nodes with integer measurements. We allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total number of bits to be exchanged to perform the desired computation. We establish lower bounds using fooling sets, and provide a novel scheme which attains the lower bounds, using information theoretic tools. For a class of functions called sum-threshold functions, this scheme is shown to be optimal. We then turn to tree networks and derive a lower bound for the number of bits exchanged on each link by viewing it as a two node problem. We show that the protocol of recursive in-network aggregation achieves this lower bound in the case of sum-threshold functions. Thus we have provided a communication and in-network computation strategy that is optimal for each link. All the results can be extended to the case of non-binary alphabets. In the case of general graphs, we present a cut-set lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, the complexity of this scheme is no more than twice that of the optimal scheme.

Sensor networks potentially feature large numbers of nodes. The nodes can monitor and sense their environment over time, communicate with each other over a wireless network, and process information that they exchange with each other. They differ from data networks in that the network as a whole may be designed for a specific application. We study the theoretical foundations of such large-scale sensor networks. We address four fundamental organizational and operational issues related to large sensor networks: connectivity, capacity, clocks, and function computation. To begin with, a sensor network must be connected so that information can indeed be exchanged between nodes. The connectivity graph of an ad hoc network is modeled as a random graph and the critical range for asymptotic connectivity is determined, as well as the critical number of neighbors that a node needs to connect to. Next, given connectivity, we address the issue of how much data can be transported over the sensor network. We present fundamental bounds on capacity under several models, as well as architectural implications for how wireless communication should be organized. Temporal information is important both for the applications of sensor networks as well as their operation. We present fundamental bounds on the synchronizability of clocks in networks, and also present and analyze algorithms for clock synchronization. Finally, we turn to the issue of gathering relevant information, which sensor networks are designed to do. One needs to study optimal strategies for in-network aggregation of data, in order to reliably compute a composite function of sensor measurements, as well as the complexity of doing so. We address the issue of how such computation can be performed efficiently in a sensor network and the algorithms for doing so, for some classes of functions.