Joint Routing and 2D Transform Optimization for Irregular Sensor Network Grids Using Wavelet Lifting

We address the joint optimization of routing and compression for wireless sensor networks using a lifting-based 2D transform that can be computed along arbitrary routing trees. The proposed 2D transform allows for unidirectional computation, thereby eliminating costly backward transmissions often required by existing 2D transforms. We also propose a framework for optimizing the transform by selecting among a different set of coding schemes (i.e., different levels in the wavelet decomposition). Since our transform can operate on arbitrary routing trees, we focus on the problem of jointly optimizing routing trees based on inter-node data correlation and inter-node distance. The two extreme solutions would be i) to route data along paths that maximize inter-node data correlation (at the risk of increasing transport costs), corresponding to a minimum spanning tree (MST), or ii) to follow shortest path tree (SPT) routing (where inter-node data correlation may not be as high). We propose an optimization technique that exhaustively searches for the optimal tree over a set of combinations of MST and SPT. We also propose a heuristic approximation algorithm that is amenable for use on larger networks and with which we observe total cost reductions close to 10% for some of the data.

1 Introduction

In recent years, low-cost, densely deployed Wireless Sensor Networks (WSN) have been studied for applications such as instrumentation and enviromental monitoring, among many others [2]. Because these are typically battery powered devices, it is important to find power-efficient techniques for data gathering and transmission. These techniques entail both energy-efficient routing and low-cost in-network compression.