International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064


Downloads: 117

Research Paper | Computer Science & Engineering | India | Volume 2 Issue 10, October 2013


Randomized Geographic Routing with Guaranteed Delivery and Low Stretch

A. Felicia | K. Brindha


Abstract: A wireless network is critical for evaluating the performance of network protocols and improving their designs. Many protocols for wireless networks routing, topology control, information storage/retrieval and numerous other applications have been based on the idealized unit-disk graph (UDG) network model. The significant deviation of the UDG model from many real wireless networks is substantially limiting the applicability of such protocols. A more general network model, the quasi unit disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the designs of key network protocols and algorithms. In this paper, we present results on two important properties of quasi-UDGs: separability and the existence of power efficient spanners. Network separability is a fundamental property leading to efficient network algorithms and fast parallel computation. We prove that every quasi-UDG has a corresponding grid graph with small balanced separators that captures its connectivity properties. We also study the problem of constructing an energy efficient backbone for a quasi-UDG. We present a distributed localized algorithm that, given a quasi-UDG, constructs a nearly planar backbone with a constant stretch factor and a bounded degree. We demonstrate the excellent performance of these auxiliary graphs through simulations and show their applications in efficient routing.


Keywords: quasi unit disk graph, GPSR, MANET, 4D network


Edition: Volume 2 Issue 10, October 2013,


Pages: 15 - 19


How to Download this Article?

You Need to Register Your Email Address Before You Can Download the Article PDF


How to Cite this Article?

A. Felicia, K. Brindha, "Randomized Geographic Routing with Guaranteed Delivery and Low Stretch", International Journal of Science and Research (IJSR), Volume 2 Issue 10, October 2013, pp. 15-19, https://www.ijsr.net/get_abstract.php?paper_id=21091304

Similar Articles with Keyword 'GPSR'

Downloads: 100

Research Paper, Computer Science & Engineering, India, Volume 4 Issue 6, June 2015

Pages: 1353 - 1357

Analysis of Energy Efficiency and Throughput for IEEE 802.11 based Mobile Adhoc Networks

Manpreet Kaur [24] | Pooja Saini [3]

Share this Article

Downloads: 112

Review Papers, Computer Science & Engineering, India, Volume 4 Issue 1, January 2015

Pages: 1987 - 1989

Secured Routing Using ALERT in MANETs

Aniket K. Khasnikar | Smita Kapse

Share this Article
Top