Abstract
Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the symmetric topology, or a directed graph referred to as the asymmetric topology. The Min-Power Symmetric (resp., Asymmetric) k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint the induced symmetric (resp. asymmetric) topology is k-connected. Similarly, the Min-Power Symmetric (resp., Asymmetric) k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the induced symmetric (resp., asymmetric) topology is k-edge connected.
The Min-Power Symmetric Biconnectivity problem and the Min-Power Symmetric Edge-Biconnectivity problem has been studied by Lloyd et. al [21]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [17], which we refer to as Algorithm KR, has an approximation ratio of at most 2(2-2/n)(2+1/n) for Min-Power Symmetric Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [18], which we refer to as Algorithm KV, has an approximation ratio of at most 8(1-1/n) for Min-Power Symmetric Edge-Biconnectivity.
In this paper, we first establish the NP-hardness of Min-Power Symmetric (Edge-)Biconnectivity. Then we show that Algorithm KR has an approximation ratio of at most 4 for both Min-Power Symmetric Biconnectivity and Min-Power Asymmetric Biconnectivity, and Algorithm KV has an approximation ratio of at most 2k for both Min-Power Symmetric k-Edge Connectivity and Min-Power Asymmetric k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Symmetric Biconnectivity and Min-Power Asymmetric Biconnectivity. This new algorithm is best suited for distributed implementation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Althaus, E., Calinescu, G., Mandoiu, I., Prasad, S., Tchervenski, N., Zelikovsky, A.: Power Efficient Range Assignment in Ad-hoc Wireless Networks. In: Proc. IEEE Wireless Communications and Networking Conference (2003)
Blough, D.M., Leoncini, M., Resta, G., Santi, P.: On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks. In: Proc. 2nd IFIP International Conference on Theoretical Computer Science, Montreal (August 2002)
Calamoneri, T., Petreschi, R.: An Efficient Orthogonal Grid Drawing Algorithm for Cubic Graphs. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 31–40. Springer, Heidelberg (1995)
Calinescu, G., Mandoiu, I., Zelikovsky, A.: Symmetric Connectivity with Minimum Power Consumption in Radio Networks. In: Proc. 2nd IFIP International Conference on Theoretical Computer Science, Montreal (August 2002)
Chen, W.T., Huang, N.F.: The Strongly Connecting Problem on Multihop Packet Radio Networks. IEEE Transactions on Communications 37(3), 293–295 (1989)
Clementi, A., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 121–131. Springer, Heidelberg (2001)
Clementi, A., Penna, P., Silvestri, R.: Hardness Results for The Power Range Assignment Problem in Packet Radio Networks. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 197–208. Springer, Heidelberg (1999)
Clementi, P.: The Power Range Assignment Problem in Radio Networks on the Plane. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 651–660. Springer, Heidelberg (2000)
Clementi, A., Huiban, G., Penna, P., Verhoeven, Y.C.: Some Recent Theoretical Advances and Open Questions on Energy Consumption in Ad-Hoc Wireless Networks. In: 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (2002)
Diestel, R. (ed.): Graph Theory. Graduate Texts in Mathematics, 2nd edn. vol. 173. Springer, New York (2000)
Edmonds, J.: Edge-disjoint branchings. In: Rustin, R. (ed.) Combinatorial Algorithms, pp. 91–96. Algorithmics Press, New York (1972)
Edmonds, J.: Matroid intersection. Annals of Discrete Mathematics 4, 185–204 (1979)
Frank, A., Tardos, É.: An application of submodular flows. Linear Algebra and its Applications 114/115, 329–348 (1989)
Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: Proc. 23rd ACM Symposium on Theory of Computing, May 1991, pp. 112–122 (1991)
Gabow, H.N.: A representation for crossing set families with applications to submodular flow problems. In: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, pp. 202–211 (1993)
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The Planar Hamiltonian Circuit Problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)
Khuller, S., Raghavachari, B.: Improved approximation algorithms for uniform connectivity problems. Journal of Algorithms 21, 433–450 (1996)
Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. Journal of ACM 41(2), 214–235 (1994)
Kirousis, L.M., Kranakis, E., Krizanc, D., Pelc, A.: Power Consumption in Packet Radio Networks. Theoretical Computer Science 243(1-2), 289–305 (2000); A preliminary version of this papers also appeared in Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science, LNCS,vol 1200, pp. 363 - 374 (1997)
Lawler, E.L.: Matroid intersection algorithms. Mathematical Programming 9, 31–56 (1975)
Lloyd, E., Liu, R., Marathe, M., Ramanathan, R., Ravi, S.S.: Algorithmic Aspects of Topology Control Problems for Ad hoc Networks. In: Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Lausanne, Switzerland (June 2002)
Rappaport, T.S.: Wireless Communications: Principles and Practices. Prentice-Hall, Englewood Cliffs (1996)
Ramanathan, R., Rosales-Hain, R.: Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment. In: IEEE INFOCOM 2000 (2000)
van Lint, J.H., Wilson, R.M.: A course in combinatorics. Cambridge University Press, Cambridge (1992)
Wan, P.-J., Calinescu, G., Li, X.-Y., Frieder, O.: Minimum Energy Broadcast Routing in Static Ad Hoc Wireless Networks. In: IEEE INFOCOM 2001 (2001)
Whitty, R.W.: Vertex-disjoint paths and edge-disjoint branchings in directed graphs. J. Graph Theory 11(3), 349–358 (1987)
Wieselthier, J.E., Nguyen, G.D., Ephremides, A.: On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In: IEEE INFOCOM 2000 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calinescu, G., Wan, PJ. (2003). Range Assignment for High Connectivity in Wireless Ad Hoc Networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds) Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2003. Lecture Notes in Computer Science, vol 2865. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39611-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-39611-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20260-8
Online ISBN: 978-3-540-39611-6
eBook Packages: Springer Book Archive