On approximate optimal dual power assignment for biconnectivity and edge-biconnectivity.

*(English)*Zbl 1145.68053Summary: Topology control is one of the major approaches to achieve energy efficiency as well as fault tolerance in wireless networks. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model.

The problem has arisen from the following practical origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerant connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity. Note that to achieve a minimum number of high-power nodes is harder than an optimization problem in the same model whose objective is to minimize the total power cost.

We first address these two optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model. Due to the NP-hardness, we propose an approximation algorithm, called prioritized edge selection algorithm, which achieves a 4-ratio approximation for 2-edge connectivity. After that, we modify the algorithm to solve the problem for 2-vertex connectivity and also achieve the same approximation ratio. We also show that the 4-ratio is tight for our algorithms in both cases.

The problem has arisen from the following practical origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerant connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity. Note that to achieve a minimum number of high-power nodes is harder than an optimization problem in the same model whose objective is to minimize the total power cost.

We first address these two optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model. Due to the NP-hardness, we propose an approximation algorithm, called prioritized edge selection algorithm, which achieves a 4-ratio approximation for 2-edge connectivity. After that, we modify the algorithm to solve the problem for 2-vertex connectivity and also achieve the same approximation ratio. We also show that the 4-ratio is tight for our algorithms in both cases.

##### MSC:

68W25 | Approximation algorithms |

05C40 | Connectivity |

68M15 | Reliability, testing and fault tolerance of networks and computer systems |

PDF
BibTeX
XML
Cite

\textit{C. Wang} et al., Theor. Comput. Sci. 396, No. 1--3, 180--190 (2008; Zbl 1145.68053)

Full Text:
DOI

##### References:

[1] | Lloyd, E.L.; Liu, R., Approximating the minimum number of maximum power users in ad hoc networks, Mobile networks and applications, 11, 129-142, (2006) |

[2] | Jian-Jia Chen, Hsueh-I Lu, Tei-Wei Kuo, Chuan-Yue Yang, Ai-Chun Pang, Dual power assignment for network connectivity in wireless sensor networks, in: 2005 Proceedings of the IEEE GLOBECOM, 2005 |

[3] | Calinescu, Gruia; Wan, Peng-Jun, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mobile networks and applications, 11, 121-128, (2006) |

[4] | Yanxia Rong, Hongsik Choi, Hyeong-Ah Choi, Dual power management for network connectivity inwireless sensor networks, in: Proceedings of the 18th International Parallel and Distributed Processing Symposium, 2004 |

[5] | M. Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, in: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, 2003 |

[6] | P. Sholander, G. Frank, A. Yankopolus, Energy-efficient network techniques for wireless sensor networks, in: Proceedings of the IEEE Milicom Conference, 2003 |

[7] | Ramanathan, R.; Rosales-Hain, R., Topology control of multihop wireless networks using transmit power adjustment, (), 403C413 |

[8] | 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, Wireless networks, 12, 287-299, (2006) |

[9] | E. Lloyd, R. Liu, M. Marathe, R. Ramanathan, S.S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, in: Proc. Third ACM International Symposium on Mobile Ad Hoc Networking and Computing MobiHoc, 2002, pp. 123-C134 |

[10] | Jia, Xiaohua; Kim, Dongsoo; Makki, Sam; Wan, Peng-Jun; Yi, Chih-Wei, Power assignment for k-connectivity in wireless ad hoc networks, Journal of combinatorial optimization, 9, 10, 213-222, (2005) · Zbl 1079.90512 |

[11] | A.E.F. Clementi, P. Penna, R. Silvestri, Hardness results for the power range assignment problem in packet radio networks, in: Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, 1999, pp. 197-208 |

[12] | M.A. Park, C. Wang, J.K.V. Willson III, W. Wu, A. Farago, Fault-tolerent dual-power assignment in wireless sensor networks, Technical Report, UTDCS-52-06, 2006 |

[13] | N. Poojary, S.V. Krishnamurthy, S. Dao, Medium access control in a network of ad hoc mobile nodes with heterogenous power capabilities, in: IEEE ICC’01, 2001, pp. 872-877 |

[14] | V. Shah, S.V. Krishnamurthy, N. Poojary, Improving the MAC layer performance in Ad Hoc networks of nodes with heterogeneous transmit power capabilities, in: IEEE ICC’04, pp. 2004 |

[15] | Kirousis, L.M.; Kranakis, E.; Krizanc, D.; Pelc, A., Power consumption in packet radio networks, Theoretical computer science, 243, 289C305, (2000) · Zbl 0944.68001 |

[16] | Reinhard Diestel, Graph Theory, Springer |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.