A Simple Greedy Algorithm for Energy-Efficient Communication in Small Multi-Interface Wireless Networks
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.
(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.
(13) Python, https://www.python.org/
Copyright (c) 2018 Transactions on Networks and Communications
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors wishing to include figures, tables, or text passages that have already been published elsewhere are required to obtain permission from the copyright owner(s) for both the print and online format and to include evidence that such permission has been granted when submitting their papers. Any material received without such evidence will be assumed to originate from the authors.
All authors of manuscripts accepted for publication in the journal Transactions on Networks and Communications are required to license the Scholar Publishing to publish the manuscript. Each author should sign one of the following forms, as appropriate:
License to publish; to be used by most authors. This grants the publisher a license of copyright. Download forms (MS Word formats) - (doc)
Publication agreement — Crown copyright; to be used by authors who are public servants in a Commonwealth country, such as Canada, U.K., Australia. Download forms (Adobe or MS Word formats) - (doc)
License to publish — U.S. official; to be used by authors who are officials of the U.S. government. Download forms (Adobe or MS Word formats) – (doc)
The preferred method to submit a completed, signed copyright form is to upload it within the task assigned to you in the Manuscript submission system, after the submission of your manuscript. Alternatively, you can submit it by email firstname.lastname@example.org