×

Variable neighborhood search variants for min-power symmetric connectivity problem. (English) Zbl 1391.90654

Summary: We consider the problem of optimal communication tree construction in a given undirected weighted graph. Such a problem occurs while minimizing the power consumption of data transmission in different distributed networks in the case when network elements are able to adjust their transmission ranges. In this paper, the most general strongly NP-hard formulation, when edge weights have arbitrary non-negative values, is considered. We propose new heuristics, mostly based on variable neighborhood search, for getting an approximate solution of the problem. An extensive comparative analysis between the proposed methods is performed. Numerical experiments demonstrate the high efficiency of the proposed heuristics.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B18 Communication networks in operations research
68M10 Network design and communication in computer systems
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Althaus, E.; Calinescu, G.; Mandoiu, I.; Prasad, S.; Tchervenski, N.; Zelikovsky, A., Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wirel Netw, 12, 3, 287-299, (2006)
[2] Brimberg, J.; Urosevic, D.; Mladenovic, N., Variable neighborhood search for the vertex weighted k-cardinality tree, Eur J Oper Res, 171, 74-84, (2006) · Zbl 1087.90061
[3] Carmi, P.; Katz, M., Power assignment in radio networks with two power levels, Algorithmica, 47, 183-201, (2007) · Zbl 1108.90015
[4] Erzin, A.; Plotnikov, R., Using VNS for the optimal synthesis of the communication tree in wireless sensor networks, Electron Notes Discret Math, 47, 21-28, (2015) · Zbl 1362.90123
[5] Erzin, A.; Plotnikov, R.; Shamardin, Y., On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem, J Appl Ind Math, 7, 142-152, (2013) · Zbl 1324.90181
[6] Fuchs B. On the hardness of range assignment problems, Tech. rep. TR05-113, electronic colloquium on computational complexity; 2005.
[7] Hanafi, S.; Lazic, J.; Mladenovic, N.; Wilbaut, C.; Crevits, I., New variable neighbourhood search based 0-1 MIP heuristics, Yugosl J Oper Res, (2015) · Zbl 1474.90301
[8] Hansen, P.; Mladenovic, N., Variable neighborhood search: principles and applications, Eur J Oper Res, 130, 449-467, (2001) · Zbl 0981.90063
[9] Kirousis, L.; Kranakis, E.; Krizanc, D.; Pelc, A., Power consumption in packet radio networks, Theor Comput Sci, 243, 289-305, (2000) · Zbl 0944.68001
[10] Pottie, G.; Kaiser, W., Wireless integrated network sensors, Commun ACM, 43, 5, 51-58, (2000)
[11] Wu, J.; Yang, S., Energy-efficient node scheduling models in sensor networks with adjustable ranges, Int J Found Comput Sci, 16, 1, 3-17, (2005) · Zbl 1096.68012
[12] Zhang, H.; Hou, J., Maintaining sensing coverage and connectivity in large sensor networks, Ad Hoc Sens Wirel Netw, 1, 1-2, 89-124, (2005)
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.