Local Algorithm for Establishing a Virtual Backbone in 3D Ad Hoc Network

Authors: Alaa E. Abdallah, M. Bsoul, Emad E. Abdallah, Ahmad Al-Khasawneh, Muath Alzghool

Abstract:

Due to the limited lifetime of the nodes in ad hoc and sensor networks, energy efficiency needs to be an important design consideration in any routing algorithm. It is known that by employing a virtual backbone in a wireless network, the efficiency of any routing scheme for the network can be improved. One common design for routing protocols in mobile ad hoc networks is to use positioning information; we use the node-s geometric locations to introduce an algorithm that can construct the virtual backbone structure locally in 3D environment. The algorithm construction has a constant time.

Keywords: Virtual backbone, dominating set, UDG.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078180

References:

[1] A.E. Abdallah, T. Fevens, and J. Opatrny. 3d local algorithm for dominating sets of unit disk graphs. In Proc. of the Canadian Conference on Computational Geometry (CCCG2010), pages 35-38, Winnipeg - Canada, 2010.
[2] K. Alzoubi, X. Li, Y. Wang, P. Wan, and O. Frieder. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 14(4):408-421, 2003.
[3] K. Alzoubi, P. Wan, and O. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications Networks, 4(1):141-149, 2002.
[4] K. Alzoubi, P. Wan, and O. Frieder. Message-optimal connecteddominating- set construction for routing in mobile ad hoc networks. In Proc. of the Third ACM international Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 02), pages 157-164, Lausanne, June 2002.
[5] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks journal, 7(6):609-616, 2001.
[6] V. Chvatal. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, pages 233-235, 1979.
[7] B. Clark, C. Colbourn, and D. Johnson. Unit disk graphs. Discrete Math, 86:165-177, 1990.
[8] J. Czyzowicz, S. Dobrev, T. Fevens, H. Gonzalez-Aguilar, E. Kranakis, J. Opatrny, and J. Urrutia. Local algorithms for dominating and connected dominating sets of unit disk graphs. In Proc. of the 8th Latin American Theoretical Informatics Symposium LATIN08, April 2008.
[9] B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In Proc. of the IEEE International Conference on Communications (ICC 97), Vol. 1, pages 376-380, Monral, June 1997.
[10] B. Gao, Y. Yang, and H. Ma. An efficient approximation scheme for minimum connected dominating set in wireless ad hoc networks. In Proc. of the IEEE Vehicular Technology Conference, pages 2744-2748, Los Angeles, September 2004.
[11] M. Garey and D. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. CA:Freeman, San Francisco, 1979.
[12] D. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWA Publishing Company, Boston, MA, 1995.
[13] D. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, pages 256-278, 1974.
[14] R. Karp. Reducibility among combinatorial problems. In Proceedings of the Symposium on Complexity of Computer Computations, pages 85- 103, 1972.
[15] M. Mauve, J. Widmer, and H. Hartenstein. A survey of position-based routing in mobile ad-hoc networks. IEEE Network Magazine, 15(6):30- 39, 2001.
[16] P. Slavik. A tight analysis of the greedy algorithm for set cover. In Proc. of the 28th ACM Symposium on Theory of Computing (STOC), pages 435-441, 1996.
[17] J. Wu, F. Dai, M. Gao, and I. Stojmenovic. On calculating poweraware connected dominating sets for efficient routing in ad hoc wireless networks. IEEE/KICS Journal of Communications and Networks, 4(1):59-70, 2002.
[18] J. Wu and H. Li. A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems, 18(3):13-36, 2001.