Local Algorithm for Establishing a Virtual Backbone in 3D Ad Hoc Network
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:60950", author = "Alaa E. Abdallah and M. Bsoul and Emad E. Abdallah and Ahmad Al-Khasawneh and Muath Alzghool", title = "Local Algorithm for Establishing a Virtual Backbone in 3D Ad Hoc Network", 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.", volume = "6", number = "3", pages = "397-5", }
