Artoun, Ojenie (2010) Parabolic Yao-type Geometric Spanners in Wireless Ad Hoc Networks. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
644kBArtoun_MCompSc_S2010.pdf - Accepted Version |
Abstract
Geometric graphs are frequently used to model a wireless ad hoc network in order to build efficient routing algorithms. The network topology in mobile wireless networks may often change therefore position-based routing that uses the idea
of localized routing has an advantage over other types of routing protocols. Since a wireless network has limited memory and energy resources, topology control has an important role in enhancing certain desirable properties of
these networks. To achieve the goal of topology control, spanning subgraphs of the UDG graph such as Relative Neighborhood Graph, Gabriel Graph and Yao Graph are constructed, which are then routed upon rather than the original UDG.
In this thesis we introduce a spanning subgraph of the UDG graph that is a variation of the Displaced Apex Adaptive Yao (DAAY) graph. In this subgraph an exclusion zone based on a parabola is defined with respect to each non-excluded
nearest neighbor and positioned on each node, instead of a cone as with the DAAY subgraph, such that each nearest neighbor is inside the parabola. It also lets the apex of the parabola to move along the line segment between the node and its neighbor. The subgraph has two adjustable parameters, one each for the position of the apex with respect to the nearest neighbor, and the width of the parabola. Thus a directed or undirected spanning subgraph
of a UDG is constructed. We show that this spanning subgraph is connected, has a conditional bounded out-degree, is a t-spanner with bounded stretch factor, and contains the Euclidean minimum spanning tree as a subgraph.
Experimental comparisons with related spanning subgraphs are also presented.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Artoun, Ojenie |
| Institution: | Concordia University |
| Degree Name: | Master of Computer Science |
| Program: | Computer Science and Software Engineering |
| Date: | 11 January 2010 |
| Thesis Supervisor(s): | Fevens, Thomas |
| Keywords: | networks, ad hoc, wireless, spanner, topology control, localized routing, unit disk graph |
| ID Code: | 6792 |
| Deposited By: | OJENIE ARTOUN |
| Deposited On: | 14 Jul 2010 14:10 |
| Last Modified: | 18 Jan 2018 17:29 |
References:
[1] A.E. Abdallah. Position based routing algorithms for three-dimensional ad hoc networks. Ph.D thesis, Concordia University, 2009.[2] L. Barriµere, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wireless
Communications and Mobile Computing Journal, 3(2):141{153, 2003.
[3] S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward. A distance routing effect algorithm for mobility (DREAM). In Proc. of 4th ACM/IEEE Conference on Mobile Computing and Networking (Mobicom '98), pages 76{84, 1998.
[4] P. Bose, P. Carmi, M. Couture, M. Smid, and D. Xu. On a family of strong geometric spanners that admit local routing strategies. Technical Report TR-07-08, SCS, Carleton University, Ottawa, Canada, 2007.
[5] P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick. On the spanning ratio of Gabriel graphs and beta-skeletons. In Proceedings of the Latin American Theoretical Infocomatics (LATIN), pages 479{493, Mexico, 2002.
[6] P. Bose, J. Gudmundsson, and P. Morin. Ordered theta graphs. Computational Geometry: Theory and Applications, 28(1):11{18, 2004.
[7] P. Bose, J. Gudmundsson, and M. Smid. Constructing plane spanners of bounded degree and low weight. Algorithmica, 42(3{4):249-264, 2005.
[8] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, volume 7, Kluwer Academic
Publishers, pages 609-616, 2001.
[9] S. Capkum, M. Hamdi, and J.P. Hubaux. GPS-free positioning in mobile ad-hoc networks. In In Proceedings of Hawaii International Conference On System Sciences, 2001.
[10] E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, H. Tejeda, and J. Urrutia. Half-space proximal: A new local test for extracting a bounded dilation spanner. In Proceedings of the International Conference On Principles of Distributed Systems (OPODIS 2005), volume 3974 of LNCS, pages 235{245, Pisa, Italy, 2006.
[11] D. Dobkin, S. Friedman, and K. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete Computational Geometry, 5(4):399-407, 1990.
[12] T. Fevens, A.E. Abdallah, T. El Salti and L. Harutyunyan. A class of orientation-invariant Yao-type subgraphs of a unit disk graph. Proc. of the DIALM-POMC
International Workshop on Foundations of Mobile Computing, Portland, USA, 2007.
[13] K. Gabriel and R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259{278, 1969.
[14] S. Giordano, I. Stojmenovic, and L. Blazevic. Position based routing algorithms for ad hoc networks: a taxonomy. In X. Cheng, X. Huang, and D.Z. Du, editors, Ad hoc wireless networking, Kulwer Academic Publishers, pages 103{136, 2003.
[15] Z. Haas, and M. Pearlman. The performance of query control scheme for the zone routing protocol. ACM/IEEE Transactions on Networking, 9(4) pages 427-438, August 2001.
[16] D. Johnson, and D. Maltz. Dynamic Source Routing. Mobile Computing, Kulwer Academic Publishers, 1996.
[17] I. Kanj, and L. Perkovic. Improved stretch factor for bounded-degree planar power spanners of wireless ad-hoc networks. In S. Nikoletseas and J. D. P. Rolim, editors, ALGOSENSORS, volume 4240 of LNCS, pages 95{106. Springer, 2006.
[18] I. Kanj, and L. Perkovic. On Geometric Spanners of Euclidean Graphs and their Applications in Wireless Networks. Technical Report, DePaul University, Chicago, USA, 2007.
[19] B. Karp, and H.T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In ACM/IEEE International Conference on Mobile Computing and Networking, 2000.
[20] J. Keil, and C. Gutwin. Classes of graphs which approximate the complete euclidean graph. Discrete Computational Geometry, 7(1):13{28, 1992.
[21] Xiang-yang Li. Applications of Computational Geometry in Wireless Networks. Ad Hoc Wireless Networking, Kluwer Academic Publishers, 2003.
[22] X. Li. Topology Control in Wireless Ad Hoc Networks. Ad Hoc Networking, IEEE Press, 2003.
[23] X.-Y. Li, G. Calinescu, P.-J. Wan, and Y. Wang. Localized delaunay triangulation with application in Ad Hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems, 14(10):1035-1047, 2003.
[24] X.-Y. Li, P.-J.Wan, and Y.Wang. Power e±cient and sparse spanner for wireless ad hoc networks. In Proceedings of IEEE International Conference on Computer Communications and Networks (ICCCN01), pages 564{567, 2002.
[25] X.-Y. Li, Y. Wang, P.-J. Wan, and O. Frieder. Sparse power efficient topology for wireless networks. In In IEEE Hawaii International Conference On System Sciences, 2002.
[26] X.-Y. Li, Y. Wang, P.-J. Wan, W.-Z. Song, and O. Frieder. Localized low-weight graph and its applications in wireless ad hoc networks. In In Proceedings of Twenty-Third IEEE INFOCOM 2004, Hong Kong, China, March 2004.
[27] 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.
[28] S. Murthy, and J. Garcia-Luna-Aceves. A routing protocol for packet radio networks. In In Proceedings of the ACM International Conference on Mobile Computing and Networking, pages 86{95, 1995.
[29] G. Narasimhan, and M. Smid. Geometric Spanner Networks. Cambridge University Press, 2007.
[30] C. Perkins and P. Bhagwat. Highly dynamic destination sequenced distance-vector routing for mobile computers. Computer Communication Review, pages 234-244, October 94.
[31] C. Perkins and E. Royer. Ad-hoc on-demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90-100, Feb 1999.
[32] R. Rajaraman. Topology control and routing in ad hoc networks: A survey. SICACT News, 33:60{73, 2002.
[33] W.-Z. Song, Y. Wang, X.-Y. Li, and O. Frieder. Localized algorithms for energy efficient topology in wireless ad hoc networks. MONET, 10(6):911{923, 2005.
[34] G. Toussaint. The relative neighbourhood graph of a ¯nite planar set. Pattern Recognition, 12(4):261{268, 1980.
[35] Y. Wang and X.-Y. Li. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. MONET, 11(2):161-175, 2006.
[36] Y. Wang, X.-Y. Li, and O. Frieder. Distributed spannar with bounded degree for wireless ad hoc networks. International Journal on Foundations of Computer Science, 14(2):183{200, 2003.
[37] A.-C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Jurnal of Computing, 11:721{736, 1982.
Repository Staff Only: item control page
Download Statistics
Download Statistics