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

  • Evi Papaioannou University of Patras & CTI Diophantus
  • Christos Kaklamanis University of Patras & CTI Diophantus
  • Stavros Maras University of Patras
Keywords: Small multi-interface wireless networks, Energy-efficient communication, Connectivity, Greedy algorithm

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.

Author Biographies

Evi Papaioannou, University of Patras & CTI Diophantus
Department of Cultural Heritage Management and New Technologies & Department of Computer Engineering and Informatics, University of Patras, Asst Professor & CTI Diophantus
Christos Kaklamanis, University of Patras & CTI Diophantus
Department of Computer Engineering and Informatics, University of Patras, Professor & CTI Diophantus
Stavros Maras, University of Patras
Department of Computer Engineering and Informatics, University of Patras, Student

References

(1) Athanassopoulos, S., Caragiannis, Ι., Kaklamanis, C., Papaioannou, E., Energy-efficient communication in multi-interface wireless networks. Theory of Computing Systems, 2013. 52 (2), p. 285-296.

(2) Bahl, P., Adya, A., Padhye, J., Walman, A., Reconsidering wireless systems with multiple radios. ACM SIGCOMM Computer Communication Review, 2004. 34(5), p. 39-46.

(3) Cavalcanti, D., Gossain, H., Agrawal, D., Connectivity in multi-radio, multi-channel heterogeneous ad hoc networks. In Proceedings of the IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 05), 2005. IEEE Press, New York, p. 1322-1326.

(4) Draves, R., Padhye, J., Zill, B., Routing in multi-radio, multi-hop wireless mesh networks. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (Mobi- Com 04), 2004. ACM, New York, p. 114-128.

(5) Faragó, A., Basagni, S., The effect of multi-radio nodes on network connectivity: a graph theoretic analysis. In Proceedings of the IEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 08), 2008. IEEE Press, New York.

(6) Klasing, R., Kosowski, A., Navarra, A., Cost minimisation in wireless networks with bounded and unbounded number of interfaces. Networks, 2009. 53(3), p. 266-275.

(7) Kosowski, A., Navarra, A., Pinotti, M.C., Exploiting multi-interface networks: connectivity and cheapest paths. Wireless Networks, 2010. 16(4), p. 1063-1073.

(8) Kruskal, J., On the shortest spanning subtree of a graph and the traveling salesman problem. In Proceedings of the American Mathematical Society, 1956. 7, p. 48-50.

(9) Navarra, A., D'Angelo, G., Di Stefano, G., Multi-interface wireless networks: complexity and algorithms. Chapter in Wireless Sensor Networks: From Theory to Applications, CRC Press, Taylor & Francis Group, 2014. p. 119-156.

(10) Prömel, H.J., Steger, A., A new approximation algorithm for the Steiner tree problem with performance ratio 5/3. Journal of Algorithms, 2000. 36, p. 89-101.

(11) Prim, R. C., Shortest connection networks and some generalizations. Bell System Technical Journal, 1957. 36(6), p. 1389-1401.

(12) NetworkX,

https://networkx.github.io/documentation/stable/index.html

(13) Python, https://www.python.org/

Published
2018-05-03