Abstract
It is effective to construct a strongly connected dominating and absorbing set (SCDAS) instead of a virtual backbone network in a wireless network with unidirectional links. However, there exist few studies on the strongly connected dominating and absorbing sets in wireless networks. In this paper, we propose an addition-based localized heuristic algorithm for constructing a SCDAS in a wireless network. The algorithm can obtain a small SCDAS with a constant approximation ratio through three executive phases. Theoretical analysis demonstrates the correctness of our algorithm.
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
Tseng, Y.C., Ni, S.Y., Chen, Y.S., Sheu, J.P.: The broadcast storm problem in a mobile ad hoc network. Wireless Networks 8(2-3), 153–167 (2002)
Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proceedings of ICC 1997, pp. 376–380 (1997)
Gary, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness (1979)
Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7–14 (1999)
Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: Proceedings of INFOCOM 2002, pp. 1597–1604 (2002)
Sakai, K., Shen, F., Kim, K.M., Sun, M.T., Okada, H.: Multi-initiator connected dominating set construction for mobile ad hoc networks. In: Proceedings of ICC 2008, pp. 2431–2436 (2008)
Zhou, D., Sun, M.T., Lai, T.H.: A timer-based protocol for connected dominating set construction in ieee 802.11 multihop mobile ad hoc networks. In: Proceedings of Symposium on Applications and the Internet 2005, pp. 2–8 (2005)
Wu, J.: Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Transactions on Parallel and Distributed Systems 13(9), 866–881 (2002)
Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems 15(10), 908–920 (2004)
Wu, J., Dai, F., Yang, S.: Iterative local solutions for connected dominating set in ad hoc wireless networks. IEEE Transactions on Computers 57(5), 702–715 (2008)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Han, B., Jia, W.: Clustering wireless ad hoc networks with weakly connected dominating set. Journal of Parallel and Distributed Computing 67(6), 727–737 (2007)
Chen, Y.P., Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Proceedings of the 3rd ACM international Symposium on Mobile Ad Hoc Networking and Computing, pp. 165–172 (2002)
Qayyum, A., Viennot, L., Laouiti, A.: Multipoint relaying for flooding broadcast messages in mobile wireless networks. In: Proceedings of HICSS 2002, pp. 3866–3875 (2002)
Park, M.A., Willson, J., Wang, C., Wu, W., Farago, A.: A dominating and absorbent set in a wireless ad-hoc network with different transmission ranges. In: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 22–31 (2007)
Tiwari, R., Mishra, T., Li, Y., Thai, M.T.: K-Strongly connected m-dominating and absorbing set in wireless ad hoc networks with unidirectional links. In: Proceedings of WASA 2007, pp. 103–112 (2007)
Thai, M.T., Wang, F., Liu, D., Zhu, S., Du, D.Z.: Connected dominating sets in wireless networks with different transmission ranges. IEEE Transactions on Mobile Computing 6(7), 721–730 (2007)
Du, D.-Z., Thai, M.T., Li, Y., Liu, D., Zhu, S.: Strongly connected dominating sets in wireless sensor networks with unidirectional links. In: Zhou, X., Li, J., Shen, H.T., Kitsuregawa, M., Zhang, Y. (eds.) APWeb 2006. LNCS, vol. 3841, pp. 13–24. Springer, Heidelberg (2006)
Thai, M.T., Tiwari, R., Du, D.Z.: On construction of virtual backbone in wireless ad hoc networks with unidirectional links. IEEE Transactions on Mobile Computing 7(9), 1098–1109 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wan, S., Yu, J., Wang, N., Wang, C., Liu, F. (2014). An Algorithm for Constructing Strongly Connected Dominating and Absorbing Sets in Wireless Networks with Unidirectional Links. In: Sun, L., Ma, H., Hong, F. (eds) Advances in Wireless Sensor Networks. CWSN 2013. Communications in Computer and Information Science, vol 418. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-54522-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-54522-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-54521-4
Online ISBN: 978-3-642-54522-1
eBook Packages: Computer ScienceComputer Science (R0)
