Efficient Routing from Multiple Sources to Multiple Sinks in Wireless Sensor Networks

Initial deployments of wireless sensor networks (WSNs) were based on a many-to-one communication paradigm, where a single sink collects data from a number of data sources. Recently, however, scenarios with multiple sinks are increasingly being proposed, e.g., to deal with actuator nodes or to support high-level programming abstractions. The resulting many-to-many communication makes the existing solutions for single-sink scenarios inefficient. In this paper, we propose a scheme for routing data efficiently from multiple sources to multiple sinks. We first study the problem from a theoretical standpoint, by mapping it to the multi-commodity network design problem. This allows us to derive an optimal solution that, albeit based on global knowledge and therefore impractical, provides us with a theoretical lower bound to evaluate decentralized solutions against. Then, we propose our own decentralized seheme, based on a periodic adaptation of the message routes aimed at minimizing the numbe...