Sensor networks are prone to congestion due to bursty and high-bandwidth data traffic, combined with wireless links and many-to-one data routing to a sink. Delayed and dropped packets then degrade the performance of the sensing application. In this paper, we investigate the value of separate handling of sensor control and data traffic, during times of congestion, in a closed-loop sensor network. We first show that prioritizing sensor control traffic over data traffic decreases the round-trip control-loop delay, and consequently increases the quantity and quality of the data collected by the sensor network. We then ground our analysis in a closed-loop meteorological sensor network, focusing on a storm-tracking application running over a network of X-band radars. Our application measures reflectivity (a measure of the number of scatterers in a unit volume of atmosphere known as a voxel) and tracks storms (i.e., regions of high reflectivity) using a Kalman filter. Considering data quantity, we show that prioritizing sensor control traffic increases the number of voxels, V, that can be scanned given a constant number of reflectivity samples, Nc, obtained per voxel. Here, utility increases linearly with the number of scanned voxels. Considering data quality, we show that prioritizing sensor control traffic increases the number of reflectivity samples, N, that can be obtained per voxel given a constant number of voxels, Vc, to scan. Here, since sensing accuracy improves only as a function of radicN, the gain in accuracy for the reflectivity estimate per voxel as N increases is relatively small except when prioritizing sensor control increases N significantly (such as when sensor control packets suffer severe delays). Because accuracy also degrades as a function of radicN, however, and because prioritizing sensor control traffic reduces the number of control packets dropped, data degradation is mitigated. Considering the performance of the tracking application, we then show that during times of severe congestion, not prioritizing sensor control can actually lead to tracking errors accumulating over time.

A fundamental problem in a large scale decentralized stream processing system is how to best utilize the available resources and admission control the bursty and high volume input streams so as to optimize overall system performance. We consider a distributed stream processing system consisting of a network of servers with heterogeneous capabilities that collectively provide processing services to multiple data streams. Our goal is to design a joint source admission control, data routing, and resource allocation mechanism that maximizes the overall system utility. Here resources include both link bandwidths and processor resources. The problem is formulated as a utility optimization problem. We describe an extended graph representation that unifies both types of resources seamlessly and present a novel scheme that transforms the admission control problem to a routing problem by introducing dummy nodes at sources. We then present a distributed gradient-based algorithm that iteratively updates the local resource allocation based on link data rates. We show that our algorithm guarantees optimality and demonstrate its performance through simulation.

In many energy-rechargeable wireless sensor networks, sensor nodes must both sense data from the environment, and cooperatively forward sensed data to data sinks. Both data sensing and data forwarding (including data transmission and reception) consume energy at sensor nodes. We present a distributed algorithm for optimal joint allocation of energy between sensing and communication at each node to maximize overall system utility (i.e., the aggregate amount of information received at the data sinks). We consider this problem in the context of wireless sensor networks with directional, non-steerable antennas. We first formulate a joint data-sensing and data-routing optimization problem with both per-node energy-expenditure constraints, and traditional flow routing/conservation constraints. We then simplify this problem by converting it to an equivalent routing problem, and present a distributed gradient-based algorithm that iteratively adjusts the per-node amount of energy allocated between sensing and communication to reach the system-wide optimum. We prove that our algorithm converges to the maximum system utility. We quantitatively demonstrate the energy balance achieved by this algorithm in a network of small, energy-constrained X-band radars, connected via point- to-point 802.11 links with non-steerable directional antennas.

2517-2527

In many energy-constrained wireless sensor networks, nodes cooperatively forward correlated sensed data to data sinks. In order to reduce the communication cost (e.g. overall en-ergy) used for data collection, previous works have focused on specific coding schemes, such as Slepian-Wolf Code or Explicit Entropy Code. However, the minimum communi-cation cost under arbitrary coding/routing schemes has not yet been characterized. In this paper, we consider the prob-lem of minimizing the total communication cost of a wireless sensor network with a single sink. We prove that the min-imum communication cost can be achieved using Slepian-Wolf Code and Commodity Flow Routing when the link communication cost is a convex function of link data rate. Furthermore, we find it useful to introduce a new metric

In this paper, we consider the problem of finding an "efficient" and "robust" set of routes in the face of changing/uncertain traffic. The changes/uncertainty in exogenous traffic is characterized by multiple traffic matrices. Our goal is to find a set of routes that result in good average case performance over the set of traffic matrices, while avoiding bad worst case performance for any single traffic matrix. With multiple traffic matrices, previous work aims solely to optimize the average case performance Chun Zhang, et al., (2005), or the worst case performance David Applegate, et al., (2003). For a given set of traffic matrices, different sets of routes offer a different tradeoff between the average case and the worst case performance. In this paper, we quantify the performance of a routing configuration at both network level and link level. We propose a simple metric-a weighted sum of the average case and the worst case performance-to control the tradeoff between these two considerations. Despite of its simple form, this metric is very effective. We prove that optimizing routing using this metric has desirable properties, such as the average case performance being a decreasing, convex and differentiable function to the worst case performance. By extending previous work Chun Zhang, et al., (2005) Bernard Fortz, et al., (2002), we derive methods to find the optimal routes with respect to the proposed metric for two classes of intra-domain routing protocols: MPLS and OSPF/IS-IS. We evaluate our approach with data collected from an operational tier-I ISP. For MPLS, we find that there exists significant tradeoff (e.g., 15%-23% difference) between optimizing solely on the average case performance and solely on the worst case performance. Our approach can identify solutions that can dramatically improve the worst case performance (13%-15%) while only slightly sacrificing the average case performance (2.2%-3%), in comparison to that by optimizing solely on the average case performance. For OSPF/IS-IS, we still find a significant difference between the two optimization objectives, however, a fine-grained tradeoff is difficult to achieve due to the limited control that OSPF/IS-IS provide.

Ethernet, wireless LAN, ADSL, cable modem and dialup are common access networks, but have dramatically different characteristics. Fast and accurate classification of access network type can improve protocol or application performance significantly. In this paper, we propose a simple and efficient end-end scheme to classify the type of an access network into three categories: Ethernet, wireless LAN and low-bandwidth connection. Our scheme is based on the intrinsic characteristics of the various access networks and utilizes the median and entropy of packet pair inter-arrival times. Extensive experiments show that our scheme obtains accurate classification results in a very short time (10 to 100 seconds).

Routing optimization is used to find a set of routes that minimizes cost (delay, utilization). Previous work has addressed this problem for the case of a known, static end-to-end traffic matrix. In the Internet, it is difficult to accurately estimate a traffic matrix, and the constantly changing nature of Internet traffic makes it costly to maintain optimal routing by responding to traffic changes. Thus, it is of interest to maintain a set of routes that are "good" for a number of different possible traffic scenarios. In this paper, we explore ways to find an optimal set of routes with multiple traffic matrices to minimize expected cost. We focus on two general approaches, source-destination routing and destination routing. In the case of source-destination routing, we extend existing methods with a single traffic matrix to solve the optimization problem with multiple traffic matrices: we extend the convex optimization solution methods for a single traffic matrix to the multiple traffic matrix case; we also extend the gradient-based solution methods for a single traffic matrix to the multiple traffic matrix case. However, the multiple traffic matrix case requires many more control variables. In the case of destination routing, we encounter many more differences from the single traffic matrix case. The loop-free property, which is valid for the single traffic matrix case, is no longer valid for the multiple traffic matrix case, and it is difficult to extend existing methods for a single traffic matrix to solve the optimization problem with multiple traffic matrices. We show that it is NP-complete even to determine the feasibility of multiple traffic matrices. We thus propose and evaluate a heuristic algorithm for this case.