A Simple Greedy Algorithm for Energy-Efficient Communication in Small Multi-Interface Wireless Networks

Abstract

Wireless networks have become extremely popular recently due to the wide range of applications they support and also because sophisticated and affordable wireless devices like smartphones, tablets, etc have actually become part of our everyday life. Wireless devices have heterogeneous characteristics, like computational power, energy-consumption levels, supported communication protocols. Modern wireless devices are usually equipped with multiple radio interfaces like, WiFi, GPRS, Bluetooth, and can switch between different communication networks for meeting connectivity requirements and, thus improving quality of service and data collection perspectives. Establishing a connection between any two such devices requires that they are close and share at least one common available interface. If communication is established between two wireless devices, then the involved communication cost reflects the energy these devices consume and equals the cost for activating a particular common interface. In this setting, the objective is to suggest a cost-efficient interface activation plan which can guarantee low-cost communication for any two such wireless devices.

We model this practical problem as an instance of the Spanning Tree problem in an appropriately defined multigraph corresponding to the actual multi-interface wireless network. When connectivity is feasible, we propose and experimentally evaluate a simple greedy algorithm indicating which interfaces must be activated so that cost-efficient connectivity is established between any two wireless devices in the network.