Abstract
One approach to guarantee the performance of underwater acoustic sensor networks is to deploy multiple Surface-level Gateways (SGs) at the surface. This paper addresses the connected (or survivable) Constrained Surface-level Gateway Placement (C-SGP) problem for 3-D underwater acoustic sensor networks. Given a set of candidate locations where SGs can be placed, our objective is to place minimum number of SGs at a subset of candidate locations such that it is connected (or 2-connected) from any USN to the base station. We propose a polynomial time approximation algorithm for the connected C-SGP problem and survivable C-SGP problem, respectively. Simulations are conducted to verify our algorithms’ efficiency.
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
Akyildiz, I.F., Pompili, D., Melodia, T.: Underwater Acoustic Sensor Networks: Research Challenges. Elesviers Journal of Ad Hoc Networks 3(3), 257–279 (2005)
Pompili, D., Melodia, T., Akyildiz, I.F.: Deployment Analysis in Underwater Acoustic Wireless Sensor Networks. In: Proc. of the ACM WUWNet (2006)
Ibrahim, S., Cui, J.H., Ammar, R.: Surface-Level Gateway Deployment for Underwater Sensor Networks. In: Proc. of the IEEE MILCOM (2007)
Seah, W.K.G., Tan, H.X.: Multipath Virtual Sink Architecture for Underwater Sensor Networks. In: Proc. of the OCEANS (2006)
Zhang, W., Xue, G., Misra, S.: Fault-tolerant Relay Node Placement in Wireless Sensor Networks: Problem and Algorithms. In: Proc. of the IEEE INFOCOM (2007)
Han, X., Cao, X., Lloyd, E.L., Shen, C.C.: Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks. In: Proc. of the IEEE INFOCOM (2007)
Lloyd, E., Xue, G.: Relay Node Placement in Wireless Sensor Networks. IEEE Trans. on Computers 56, 134–138 (2007)
Misra, S., Hong, S.D., Xue, G., Tang, J.: Constrained Relay Node Placement in Wireless Sensor Networks to Meet Connectivity and Survivability Requirements. In: Proc. of the IEEE INFCOM (2008)
Ke, W., Liu, B., Tsai, M.: Constructing a Wireless Sensor Network to Fully Cover Critical Grids by Deploying Minimum Sensors on Grid Points is NP-Complete. IEEE Trans. on Computers 56, 710–715 (2007)
Mader, W.: Uber Minimal n-fach Zusammenhangende, Unendliche Graphen Undein Extremal Problem. Arch. Math. 23, 553–560 (1972)
Conway, J.H., Sloane, N.J.A.: Sphere Packing, Lattices and Groups, 3rd edn. Springer, New York (1999)
Butenko, S., Ursulenko, O.: On Minimum Connected Dominating Set Problem in Unit-Ball Graphs. Preprint Submitted to Elervier Science (2007)
Kou, L.T., Markowsky, G., Berman, L.: A Fast Algorithm for Steiner Tree. Acta Informatica 15, 141–145 (1981)
Du, D., Hu, X.: Steiner Tree Problems in Computer Communication Networks. World Scientific Publishing Co. Pte. Ltd., Singapore (2008)
Fleischer, L.: A 2-approximation for Minimum Cost {0, 1, 2}-Vertex Connectivity. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, p. 115. Springer, Heidelberg (2001)
Robins, G., Zelikovsky, A.: Tighter Bound for Graph Steiner Tree Approximation. SIAM J. on Discrete Mathmatics 19, 122–134 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, D., Li, Z., Ma, W., Chen, H. (2010). Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks. In: Wu, W., Daescu, O. (eds) Combinatorial Optimization and Applications. COCOA 2010. Lecture Notes in Computer Science, vol 6509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17461-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-17461-2_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17460-5
Online ISBN: 978-3-642-17461-2
eBook Packages: Computer ScienceComputer Science (R0)