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 scheme, based on a periodic adaptation of the message routes aimed at minimizing the number of network links exploited. The resulting protocol is simple and easily implementable on WSN devices. The evaluation of our implementation shows that our protocol generates 50% less overhead than the base scheme without adaptation, a result close to the theoretical optimum we derived