Artoun, Ojenie (2010) Parabolic Yaotype Geometric Spanners in Wireless Ad Hoc Networks. Masters thesis, Concordia University.

PDF
 Accepted Version
644kB 
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 positionbased 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 nonexcluded
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 outdegree, is a tspanner 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 > Faculty 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:  08 Dec 2010 23:05 
References:  [1] A.E. Abdallah. Position based routing algorithms for threedimensional ad hoc networks. Ph.D thesis, Concordia University, 2009.
[2] L. Barriµere, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust positionbased 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 TR0708, SCS, Carleton University, Ottawa, Canada, 2007. [5] P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick. On the spanning ratio of Gabriel graphs and betaskeletons. 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):249264, 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 609616, 2001. [9] S. Capkum, M. Hamdi, and J.P. Hubaux. GPSfree positioning in mobile adhoc 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. Halfspace 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):399407, 1990. [12] T. Fevens, A.E. Abdallah, T. El Salti and L. Harutyunyan. A class of orientationinvariant Yaotype subgraphs of a unit disk graph. Proc. of the DIALMPOMC 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 427438, 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 boundeddegree planar power spanners of wireless adhoc 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] Xiangyang 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):10351047, 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 lowweight graph and its applications in wireless ad hoc networks. In In Proceedings of TwentyThird IEEE INFOCOM 2004, Hong Kong, China, March 2004. [27] M. Mauve, J. Widmer, and H. Hartenstein. A survey of positionbased routing in mobile adhoc networks. IEEE Network Magazine, 15(6):30{39, 2001. [28] S. Murthy, and J. GarciaLunaAceves. 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 distancevector routing for mobile computers. Computer Communication Review, pages 234244, October 94. [31] C. Perkins and E. Royer. Adhoc ondemand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90100, 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):161175, 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 kdimensional spaces and related problems. SIAM Jurnal of Computing, 11:721{736, 1982. 
Repository Staff Only: item control page
Downloads
Downloads per month over past year