Abstract
In this paper, we introduce a new clustering problem in underwater sensor networks, namely minimum average routing path clustering problem (MARPCP). To deal with the high complexity of MARPCP, we relax it to a special case of minimum weight dominating set problem (MWDSP). We show an existing algorithm for MWDSP can produce an approximate solution for MARPCP. Also, we design a constant factor approximation algorithm for MARPCP, which is much faster than the first method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akyildiz I.F., Pompili D., Melodia T.: Underwater acoustic sensor networks: research challenges. J. Ad Hoc Netw. 3(3), 257–279 (2005)
Yu J.Y., Chong P.H.J.: A survey of clustering schemes for mobile ad hoc networks. IEEE Commun. Surv. Tutor. 7(1), 32–48 (2005)
Govindan, R., Hellerstein, J.M., Hong, W., Madden, S., Franklin, M., Shenker, S.: The sensor network as a database. USC Technical Report No. 02-771, September 2002
Wang, P., Li, C., Zheng, J.: Distributed minimum-cost clustering protocol for underwater sensor networks (UWSNs). IEEE International Conference on Communications (ICC 2007), pp. 3510–3515, June 2007
Belding-Royer E.M.: Multi-level hierarchies for scalable ad hoc routing. Wireless Netw. 9(5), 461–478 (2003)
Li, X., Fang, S.-L., Zhang, Y.-C.: The study on clustering algorithm of the underwater acoustic sensor networks. In: The 14th International Conference on Mechatronics and Machine Vision in Practice (M2VIP 2007), Dec 2007
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: The 33rd Annual Hawaii International Conference on System Sciences, Jan 2000
Akyildiz I.F., Su W., Sankarasubramaniam Y., Cayirci E.: Wireless sensor networks: a survey. Comput. Netw. Int. J. Comput. Telecommun. Netw. 38(4), 393–422 (2002)
Wang, W., Kim, D., Willson, J., Thuraisingham, B., Wu, W.: A better approximation for minimum average routing path clustering problem in Multi-hop 2-D underwater sensor networks. Discrete Math. Algorithms Appl. 1(2) June (2009)
Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX-RANDOM 2006), pp. 3–14 (2006)
Dai D., Yu C.: A \({5+\epsilon}\) -approximation algorithm for minimum weighted dominating set in unit disk graph. Theor. Comput. Sci. 410, 756–765 (2009)
Chvatal V.: A greedy heuristic for the set covering problem. Math. Methods Oper. Res. 4, 233–235 (1979)
Wu W., Du H., Jia X., Li Y., Huang S.C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352, 1–7 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kim, D., Wang, W., Ding, L. et al. Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks. Optim Lett 4, 383–392 (2010). https://doi.org/10.1007/s11590-009-0168-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-009-0168-z