Existing mechanisms for querying wireless sensor networks leak client interests to the servers performing the queries. The leaks are not only in terms of specific regions of interest but also of client access patterns. In this article we introduce the problem of preserving the privacy of clients querying a wireless sensor network owned by untrusted organizations. We first propose an efficient protocol, SPYC, that ensures full client privacy in settings where the servers providing access to the network are honest-but-curious and whose collaboration does not extend beyond well-defined administrative purposes. Furthermore, we study the same query privacy problem in a setting where servers exhibit malicious behavior or where powerful external attackers have access to sensor network traffic information. In this setting we propose two metrics for quantifying the privacy achieved by a client's query sequence. We then extend SPYC with a suite of practical algorithms, then analyze the privacy and efficiency levels they provide. Our TOSSIM simulations show that the proposed extensions are communication efficient while significantly improving client privacy levels.

Many real-world applications for sensor networks require event sampling with sufficient resolution over both spatial and temporal dimensions. When the deployed nodes are insufficient to fully cover the sensor field to satisfy this spatiotemporal sampling requirements of all events, nodes with intelligent mobility are crucial to improve the sampling quality. We measure the sampling quality using a utility function that incorporates both the importance and spatiotemporal properties of events. We then describe a Utility Driven Mobility (UDM) scheme, which enables autonomous mobility scheduling of nodes in a distributed fashion. We evaluate the performance of UDM via extensive simulation studies. Our work provides a practical framework for spatiotemporal sampling using mobile sensor networks.

Reprogramming over the network is an essential requirement in large-scale, long term wireless sensor network deployments. In this paper, we present LACONIC, a history-based code dissemination technique, for programmable wireless sensor networks supporting multiple applications. In order to attain network traffic abatement and timely code delivery, LACONIC exploits (1) application calling history and (2) code dissemination history. The application calling history is modeled by a Application Call Graph(ACG) which represents the calling relationships among multiple applications. Second, the code dissemination history as a set of observed previous code forwarding paths indicates previous code forwarding path of the associated application in the context of the application calling history. Therefore, the code request triggered by a requester is reached to the responder by traveling along the path, not being consecutively flooded. Using a flooding-based existing code dissemination work as the baseline, we show the effectiveness of Laconic in terms of network traffic and time delay through both probability model-based analysis and simulation results.

In a large-scale mobile gaming environment with limited wireless network bandwidth, efficient mechanisms for state update are crucial to allow graceful real-time interaction for a large number of players. By using the state updating threshold as a key parameter that bridges the resulting state distortion and the network traffic, we are able to study the fundamental traffic-distortion tradeoffs via both theoretical modeling and numerical analysis using real game traces. We consider a WiMAX link model, where the bandwidth allocation is driven by the underlying physical layer link quality as well as application layer gaming behaviors. Such a cross-layer optimization problem can be solved using standard convex programming techniques. By exploring the temporal locality of gaming behavior, we also propose a prediction method for on-line bandwidth adaptation. Using real data traces from a multiplayer driving game, TORCS, the proposed network-aware bandwidth allocation method (NABA) is able to achieve significant reduction in state distortion compared to two baselines: uniform and proportional policies.

We study the problem of constructing a data gathering tree over a wireless sensor network in order to minimize the total energy for compressing and transporting information from a set of source nodes to the sink. This problem is crucial for advanced computationally intensive applications, where traditional "maximum" in-network compression may result in significant computation energy. We investigate a tunable data compression technique that enables effective trade-offs between the computation and communication costs. We derive the optimal compression strategy for a given data gathering tree and then investigate the performance of different tree structures for networks deployed on a grid topology, as well as general graphs. Our analytical results pertaining to the grid topology and simulation results pertaining to the general graphs indicate that the performance of a simple greedy approximation to the Minimal Steiner Tree (MST) provides a constant-factor approximation for the grid topology and good average performance on the general graphs. Although, theoretically, a more complicated randomized algorithm offers a polylogarithmic performance bound, the simple greedy approximation of MST is attractive for practical implementation.

In large scale mobile gaming environments, efficient mechanisms for state update is crucial to allow graceful real-time interaction of a large number of players, under limited wireless network bandwidth. By using the state updating threshold as a key parameter that bridges the resulting state inconsistency (or distortion) and the network traffic, we are able to model the fundamental traffic-distortion tradeoffs. Given the tradeoffs for all users, an optimal bandwidth allocation can be derived using well-known convex programming techniques. By exploring the temporal locality of gaming behavior, we also propose a prediction method to realize on-line bandwidth adaptation. Using real data trace from a multi-player driving game, the proposed network aware bandwidth allocation method, NABA, is able to achieve significant reduction in state distortion compared to two baselines: Uniform and Proportional policies. NABA is also adaptable to variations in system parameters, including bandwidth constraint and network delay.

It is vital to support concurrent applications sharing a wireless sensor network in order to reduce the deployment and administrative costs, thus increasing the usability and efficiency of the network. We describe Melete 1 , a system that supports concurrent applications with efficiency, reliability, flexibility, programmability, and scalability. Our work is based on the Maté virtual machine [1] with significant modifications and enhancements. Melete enables reliable storage and execution of concurrent applications on a single sensor node. Dynamic grouping is used for flexible, on-the-fly deployment of applications based on contemporary status of the sensor nodes. The grouping procedure itself is programmed with the TinyScript language. A group-keyed code dissemination mechanism is also developed for reliable and efficient code distribution among sensor nodes. Both analytical and simulation results are presented to study the impact of several key parameters and optimization techniques on the code dissemination mechanism. Simulation results indicate satisfactory scalability of our techniques to both application code size and node density. The usefulness and effectiveness of Melete is also validated by empirical study.

This paper studies the challenging problem of energy minimization for data gathering over a multiple-sources single-sink communication substrate in wireless sensor networks by exploring the energy-latency tradeoffs using rate adaptation techniques. We consider a real-time scenario for mission-critical applications, where the data gathering must be performed within a specified latency constraint. We first propose an offline numerical optimization algorithm with performance analysis for a special case with a complete binary data gathering tree. Then, by discretizing the transmission time, we present a simple, distributed on-line protocol that relies only on the local information available at each sensor node. Extensive simulations were conducted for both long and short-range communication scenarios using two different source placement models. We used the baseline of transmitting all packets at the highest speed and shutting down the radios afterwards. Our simulation results show that compared with this baseline, up to 90% energy savings can be achieved by our techniques (both off-line and on-line), under different settings of several key system parameters

We study the problem of scheduling packet transmissions for data gathering in wireless sensor networks. The focus is to explore the energy-latency tradeoffs in wireless communication using techniques such as modulation scaling. The data aggregation tree - a multiple-source single-sink communication paradigm - is employed for abstracting the packet flow. We consider a real-time scenario where the data gathering must be performed within a specified latency constraint. We present algorithms to minimize the overall energy dissipation of the sensor nodes in the aggregation tree subject to the latency constraint. For the off-line problem, we propose (a) a numerical algorithm for the optimal solution, and (h) a pseudo-polynomial time approximation algorithm based on dynamic programming. We also discuss techniques for handling interference among the sensor nodes. Simulations have been conducted for both long-range communication and short-range communication. The simulation results show that compared with the classic shutdown technique, between 20% to 90% energy savings can be achieved by our techniques, under different settings of several key system parameters. We also develop an on-line distributed protocol that relies only on the local information available at each sensor node within the aggregation tree. Simulation results show that between 15% to 90% energy conservation can be achieved by the on-line protocol. The adaptability of the protocol with respect to variations in the packet size and latency constraint is also demonstrated through several run-time scenarios.

This paper studies the problem of determining an energy-balanced schedule for packet transmission over a multi-hop communication path in wireless sensor networks. We consider an epoch-based scenario where the packet must be transmitted within a specified latency constraint. The goal is to balance the energy dissipation along the path with respect to a full exploration of the energy-latency tradeoffs. We propose both an off-line approximation algorithm and an on-line protocol. Experimental results show that by using our off-line algorithm, up to 90% energy saving ban be achieved with a 10-hop communication path with radius of each hop at 10 m, and 60% with radius of each hop at approximately 2.2 m. Two runtime scenarios are also shown to demonstrate the ability of the on-line protocol to adapt the modulation settings with respect to system variations in data packet size and latency constraint.

In this paper, we study the problem of allocating a real-time application onto a set of homogeneous processing elements connected by a single-hop wireless network. A periodic application consisting of a set of communicating tasks is considered. Each element is equipped with discrete dynamic voltage scaling for exploring the energy-latency tradeoffs. The time and energy costs of both computation and communication activities are considered. The goal is to balance the energy dissipation of the elements during each period of the application with respect to the remaining energy of elements, such that the system lifetime is maximized. An Integer Linear Programming (ILP) formulation is first developed, which can be solved to obtain the optimal solution. We then propose an efficient 3-phase heuristic. Experimental results show that for small scale problems, the performance of the heuristic achieves up to 85% of the system lifetime obtained by the ILP-based approach. For large scale problems, the performance of the heuristic shows an improvement of 120-250\% in the system lifetime compared with the case where no voltage scaling is used. Further, we present two extensions of our approaches that consider multiple communication channels and techniques for exploring the energy-latency tradeoffs of the communication activities.

In recent years, power management and power reduction has become a critical issue in portable systems that are designed for real-time use. In this paper, we study the problem of static allocation of a set of independent tasks onto a real-time system consisting of heterogeneous processing elements, each enabled with discrete Dynamic Voltage Scaling. The allocation problem is first formulated as an extended Generalized Assignment Problem. A linearization heuristic (LR-heuristic) is then extended for solving the problem. An analysis of the upper bound on the number of tasks that the heuristic may fail to allocate is also presented. Our experiments show that when the real-time constraints are tight, the LR-heuristic achieves 15% off the optimal energy consumption for small size problems, while the performance of a classic greedy heuristic is around 90% off the optimal. A relative performance improvement of up-to 40% over the classic greedy heuristic is also observed for large size problems.

In this paper, we study the problem of mapping a set of independent paths onto a heterogeneous real-time system. Each path is a pipeline of several stages where each stage consists of one application. Each path has latency and throughput requirements that have to be satisfied. The general goal of this problem is to find an initial static mapping of all applications onto available system resources to maximize the allowable increase in input load, until dynamic remapping is required to avoid Quality of Service (QoS) violations on any path. The objective function considered in this paper is to find a static mapping such that the sum of the latencies of all paths is minimized, while satisfying all latency and throughput requirements. The motivation behind it is to give more room for each path to accommodate additional load at run-time. We develop an integer programming (IP) formulation for modeling this mapping problem. By solving the formulation, a feasible mapping can be found that satisfies latency and throughput requirements of all paths and optimizes the objective function. Two heuristics are given along with the IP formulation to provide efficient solutions. Experimental results show the correctness of the IP formulation and the effectiveness of our heuristics.