×

Energy consumption minimization in ad hoc wireless and multi-interface networks. (English) Zbl 1187.68044

Koster, Arie M. C. A. (ed.) et al., Graphs and algorithms in communication networks. Studies in broadband, optical, wireless and ad hoc networks. Berlin: Springer (ISBN 978-3-642-02249-4/hbk; 978-3-642-02250-0/ebook). Texts in Theoretical Computer Science. An EATCS Series, 335-355 (2010).
Summary: This chapter deals with energy consumption issues in wireless networks. In such networks, energy is a scarce resource and, hence, it must be used efficiently. Under these circumstances, we consider two interesting combinatorial optimization problems: Minimum Energy Broadcast Routing and Cost Minimization in Multi-interface Networks. The goal of the first problem is to perform broadcasting from a given source while minimizing the overall energy required for communication. The second problem refers to the choice of activating a set of available communication interfaces at the network nodes in order to satisfy the required connections in a wireless multi-interface network with minimum total cost. While Minimum Energy Broadcast Routing has been studied extensively during recent years, Cost Minimization in Multi-interface Networks is rather new. For both problems we survey recent complexity results and approximation algorithms under different assumptions.
For the entire collection see [Zbl 1181.68008].

MSC:

68M10 Network design and communication in computer systems
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ambühl, C.: An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, Springer, pp. 1139-1150, 2005 · Zbl 1085.68501
[2] Athanassopoulos, S., Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Experimental comparison of algorithms for energy-efficient multicasting in ad hoc networks. In: Proceedings of the 3rd International Conference on Ad Hoc Networks & Wireless (ADHOC NOW), LNCS 3158, Springer, pp. 183-196, 2004
[3] Ausiello, G.; D’Atri, A.; Protasi, M., Structure preserving reductions among convex optimization problems., Journal of Computer and System Sciences, 21, 1, 136-153 (1980) · Zbl 0441.68049 · doi:10.1016/0022-0000(80)90046-X
[4] Barsi, F., Navarra, A., Pinotti, M. C.: Cheapest Path in Multi-Interface Networks. In: Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN), LNCS, Springer, 2009
[5] Biló, V.; Flammini, M.; Melideo, G.; Moscardelli, L.; Navarra, A., Sharing the cost of multicast transmissions in euclidean and general wireless networks., Theoretical Computer Science, 369, 1-3, 269-284 (2006) · Zbl 1110.68005 · doi:10.1016/j.tcs.2006.09.004
[6] Brooks, R. L., On coloring the nodes of a network., Proceedings of Cambridge Philosophical Society, 37, 194-197 (1941) · Zbl 0027.26403 · doi:10.1017/S030500410002168X
[7] Čagalj, M., Hubaux, J., Enz, C.: Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues. In: Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MobiCom), ACM Press, pp. 172-182, 2002
[8] Cai, H.; Zhao, Y., On approximation ratios of minimum-energy multicast routing in wireless networks., Journal of Combinatorial Optimization, 9, 3, 243-262 (2005) · Zbl 1127.90014 · doi:10.1007/s10878-005-1409-4
[9] Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in adhoc wireless networks. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA), LNCS 2832, Springer, pp. 114-126, 2003 · Zbl 1266.68022
[10] Caporuscio, M.; Carzaniga, A.; Wolf, A. L., Design and evaluation of a support service for mobile, wireless publish/subscribe applications., IEEE Transactions on Software Engineering, 29, 12, 1059-1071 (2003) · doi:10.1109/TSE.2003.1265521
[11] Caporuscio, M., Charlet, D., Issarny, V., Navarra, A.: Energetic Performance of Service-oriented Multi-radio Networks: Issues and Perspectives. In: Proceedings of the 6th International Workshop on Software and Performance (WOSP), pp. 42-45. ACM Press, 2007
[12] Caragiannis, I., Flammini, M., Moscardelli, L.: An exponential improvement on the mst heuristic for minimum energy broadcasting in ad hoc wireless networks. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 4596, Springer, pp. 447-458, 2007 · Zbl 1171.68303
[13] Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: New results for energy-efficient broadcasting in wireless networks. In: Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC), LNCS 2518, Springer, pp. 332-343, 2002 · Zbl 1019.68501
[14] Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P., A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem., Information Processing Letters, 86, 3, 149-154 (2003) · Zbl 1173.68857 · doi:10.1016/S0020-0190(02)00484-2
[15] Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P., Energy-efficient wireless network design., Theory of Computing Systems, 39, 5, 593-617 (2006) · Zbl 1100.68505 · doi:10.1007/s00224-005-1204-8
[16] Cartigny, J., Simplot, D., Stojmenovic, I.: Localized minimum-energy broadcasting in ad hoc networks. In: Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3, IEEE Computer Society Press, pp. 2210-2217, 2003
[17] Chvátal, V., A greedy heuristic for the set-covering problem., Mathematics of Operations Research, 4, 3, 233-235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[18] Cilibrasi, R., Lotker, Z., Navarra, A., Perennes, S., Vitanyi, P.: About the lifespan of peer to peer networks. In: Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), LNCS 4305, Springer, pp. 290-304, 2006
[19] Clementi, A. E. F., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the complexity of computing minimum energy consumption broadcast subgraph. In: Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 2010, Springer, pp. 121-131, 2001 · Zbl 0976.68522
[20] Clementi, A. E. F.; Di Ianni, M.; Silvestri, R., The minimum broadcast range assignment problem on linear multi-hop wireless networks., Theoretical Computer Science, 299, 1-3, 751-761 (2003) · Zbl 1051.90007 · doi:10.1016/S0304-3975(02)00538-8
[21] Conway, J. H.; Sloane, N. J. A., “The Kissing Number Problem“ and “Bounds on Kissing Numbers”. (1998), New York: Springer-Verlag, New York
[22] Das, A. K.; Markas, R. J.; El-Sharkawai, M.; Arabshahi, P.; Gray, A., Minimum energy broadcast trees for wireless networks: Integer programming formulations., IEEE Computer Society, 2, 1001-1010 (2003)
[23] Faragó, A., Basagni, S.: The Effect of Multi-Radio Nodes on Network Connectivity—A Graph Theoretic Analysis. In: Proceedings of the 19th International IEEE Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), 2008
[24] Flammini, M., Klasing, R., Navarra, A., Perennes, S.: Improved approximation results for the Minimum Energy Broadcasting Problem. In: Proceedings of ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 85-91, 2004 · Zbl 1169.68313
[25] Flammini, M., Klasing, R., Navarra, A., Perennes, S.: Tightening the upper bound for the Minimum Energy Broadcasting. Wireless Networks, Vol. 14(5), pp. 959-669, 2008
[26] Flammini, M., Navarra, A., Perennes, S.: The “real” approximation factor of the MST heuristic for the minimum energy broadcasting. ACM Journal of Experimental Algorithmics, 11, 2006. Preliminary version in: Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA), LNCS 3503, Springer, pp. 22-31, 2005 · Zbl 1121.68406
[27] Frieze, A. M.; McDiarmid, C. J. H., On Random Minimum Length Spanning Trees., Combinatorica, 9, 363-374 (1989) · Zbl 0712.05050 · doi:10.1007/BF02125348
[28] Guha, S.; Khuller, S., Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets., Information and Computation, 150, 1, 57-74 (1999) · Zbl 1045.68594 · doi:10.1006/inco.1998.2754
[29] Hac, A.: Wireless sensor network designs. John Wiley & Sons, Ltd, 2003
[30] Kang, I., Poovendran, R.: Iterated local optimization for minimum energy broadcast. In: Proceedings of the 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pp. 332-341, 2005
[31] Klasing, R.; Flammini, M.; Navarra, A.; Perennes, S., Improved approximation results for the Minimum Energy Broadcasting Problem., Algorithmica, 49, 4, 318-336 (2007) · Zbl 1169.68313 · doi:10.1007/s00453-007-9077-7
[32] Klasing, R., Kosowski, A., Navarra, A.: Cost minimisation in multi-interface networks. In: Proceedings of the 1st EuroFGI International Conference on Network Control and Optimization (NET-COOP), LNCS 4465, Springer, pp. 276-285, 2007 · Zbl 1181.90058
[33] Klasing, R., Navarra, A., Papadopoulos, A., Perennes, S.: Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem. In: Proceedings of the 3rd IFIP-TC6 International Networking Conference, LNCS 3042, Springer, pp. 866-877, 2004
[34] Kosowski, A., Navarra, A.: Cost minimisation in unbounded multi-interface networks. In: Proceedings of the 2nd PPAM Workshop on Scheduling for Parallel Computing (SPC), Lecture Notes in Computer Science 4967, Springer-Verlag, pp. 1039-1047, 2007 · Zbl 1181.90058
[35] Kosowski, A., Navarra, A., Pinotti, M. C.: Connectivity in Multi-Interface Networks. In: Proceedings of the 4th International Symposium on Trustworthy Global Computing (TGC), LNCS, Springer, 2008
[36] Liang, W.: Constructing minimum-energy broadcast trees in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), ACM Press, pp. 112-122, 2002
[37] Li, F., Nikolaidis, I.: On minimum-energy broadcasting in all-wireless networks. In: Proceedings of the 26th Annual IEEE Conference on Local Computer Networks (LCN), IEEE Computer Society, p. 193, 2001
[38] Navarra, A., 3-D Minimum Energy Broadcasting problem., Ad Hoc Networks, 6, 5, 734-743 (2008) · doi:10.1016/j.adhoc.2007.06.003
[39] Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation, and complexity classes., Journal of Computer and System Sciences, 43, 425-440 (1991) · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[40] Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Anuual ACM Symposium on Theory of Computing (STOC), pp. 475-484, 1997 · Zbl 0963.68175
[41] Wan, P. J.; Calinescu, G.; Li, X.; Frieder, O., Minimum energy broadcasting in static ad hoc wireless networks., Wireless Networks, 8, 6, 607-617 (2002) · Zbl 1012.68962 · doi:10.1023/A:1020381720601
[42] Wieselthier, J. E., Nguyen, G. D., Ephremides, A.: On the construction of energy-efficient broadcast and multicast trees in wireless networks. In: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), IEEE Computer Society, pp. 585-594, 2000
[43] Yuan, D.: Computing Optimal or Near-Optimal Trees for Minimum-Energy Broadcasting in Wireless Networks. In: Proceedings of the 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pp. 323-331, 2005
[44] Zhao, F., Guibas, L.: Wireless sensor networks: an information processing approach. Morgan Kaufmann, 2004
[45] Zosin, L., Khuller, S.: On Directed Steiner Trees. In: Proceedings of the 13th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 59-63, 2002 · Zbl 1093.68629
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.