Overview

The problem of the throughput capacity of wireless networks has previously been studied in relation to the wireless bandwidth constraints of wireless links. However, in many applications the data delivery rate required for many applications, especially for monitoring environments is sufficiently low that the wireless bandwidth is not a limiting factor. The key cost in data delivery is then the energy spent in communication. The other consideration is the fidelity at which data can be collected. In a wireless sensor network, data from multiple correlated sensors is collected over multi-hop routes and fused to reproduce the phenomenon. However, the same distortion may be achieved using multiple rate allocations among the correlated sensors. These rate allocations would typically have different energy cost in routing depending on the network topology. We consider the interplay between these two considerations of distortion and energy. We study the various factors that affect this trade-off. We aim to derive bounds on the achievable performance with respect to this trade-off. Specifically, we relate the network lifetime L to the distortion D of the delivered data. Finally, we present low-complexity approximations for the efficient computation of the L(D) bound.

Approach & accomplishments

The energy consumed depends not just on the data rate but also on the routing scheme used. As an example, consider the network shown in Figure 1. The phenomenon to be sensed is present near node A, and it is to be reproduced at the base station.

Figure 1. Example network to demonstrate energy considerations.

Some of the key issues to be considered for determining the energy distortion performance are:

1. Choice of Sensors: The same level of distortion may be achievable through various choices of sensors acting as data sources. For each choice of sources, the energy cost of data delivery across the network varies. For instance, sensor A may need a lower data rate, since it measures the phenomenon at high SNR but require the use of longer routes, while sensor D may need a much a larger data-rate for the same distortion but send it using a shorter route.
2. Choice of Routes: The cost may vary even for the same data-rate beginning with the same source sensors depending on the route used. For instance, the cost of route A-B-D-C TO Base will be different from A TO Base due to number of nodes involved and the dependence of transmit power upon distance. Data may even be spread across multiple routes to maximally exploit the available batteries.
3. Protocol Overheads: The data collected is routed over multiple hops. The energy cost of initiating additional data collection at nodes already on an existing multi-hop route, may be lower than at nodes not on the chosen route due to wake-up and initiation overheads. The fidelity advantage from such nodes may however be lower than that from nodes not on the chosen route.
4. In-network Aggregation: As the data is routed, multiple streams from different sources may be aggregated within the network, reducing the cost of communication, though adding some processing cost, and limiting some choices of routes.

The above choices affect how energy is consumed at different nodes in the network and this expense must be subject to the battery availability at different nodes. The distribution of the sensed phenomenon is not necessarily uniform, and routing choices may be affected by this.

We model the energy cost of multi-path routing jointly with the rate-distortion function. Rather than working with asymptotic and random network placements, we include the exact network topology information into our constraints. We then use the joint constraints to set up an optimization problem which yields the best possible choice of routes for a given distortion performance in order to maximize the network lifetime. The optimization problem derived is non-linear and we also prove heuristics to linearize the constraints in order to utilize linear programming tools for solving the optimization with reasonable computation complexity. Figure 2 shows the upper and lower bound computed using our computationally tractable heuristics. The two bounds are well within an order of a magnitude and hence provide a useful estimate of the actual lifetime distortion curve which is computationally intractable to compute.

Figure 2. Computationally tractable calculation of the lower and upper bound on the lifetime distortion relationship.

These calculations yield important insights into the achievable distortions at desired lifetime requirements for the network.

Future Directions

The above work is a first step toward developing a framework for energy and distortion performance for multi-hop sensor networks. We are considering other computationally tractable methods to obtain closer estimates of the L(D) relationship than the initial heuristic. In addition, we are exploring better methods to use the non-linear constraints by restricting data generation to a small subset of nodes. Further, the system model used in the current work does not account for all the issues mentioned above. In particular, we assumed that data is not aggregated in-network as it propagates toward the fusion center. Also, protocol overheads of selecting multiple sensors were not explicitly accounted for. Future work would involve incorporating these factors. A distributed sensor selection and routing scheme to achieve the lifetime bound is also desirable.

People

PI’s: M.B. Srivastava and G.J Pottie

Participants: A. Kansal, graduate student; A. Ramamoorthy, graduate student.