International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Open Access | Fully Refereed | 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 Cite this Article?

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

How to Share this Article?

Enter Your Email Address


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, Pooja Saini

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

Similar Articles with Keyword 'MANET'

Downloads: 2

Review Papers, Computer Science & Engineering, India, Volume 3 Issue 12, December 2014

Pages: 1380 - 1382

A Literature Review of Enhancing Security in Mobile Ad-Hoc Networks Using Trust Management Security Scheme

Rajshree Ambatkar, Purnima Selokar

Share this Article

Downloads: 3

Review Papers, Computer Science & Engineering, India, Volume 3 Issue 6, June 2014

Pages: 2406 - 2408

Optimizing the Ad-Hoc Applications in Vehicular Network: A Study

Sumeet Sekhon, Dinesh Kumar

Share this Article

Similar Articles with Keyword 'quasi'

Downloads: 111

Research Paper, Computer Science & Engineering, India, Volume 3 Issue 12, December 2014

Pages: 658 - 661

A Better Approach for Privacy Preserving Data Publishing by Slicing

Mohd Faquroddin, G. Kiran Kumar

Share this Article

Downloads: 114

Research Paper, Computer Science & Engineering, India, Volume 3 Issue 4, April 2014

Pages: 840 - 844

Privacy Data Publishing Using Slicing and Tuple Grouping Strategy

E. Ashwini Kumari, N. Chandra Sekhar Reddy, G. V Geetha Madhavi

Share this Article

Similar Articles with Keyword 'unit'

Downloads: 1

Review Papers, Computer Science & Engineering, India, Volume 3 Issue 11, November 2014

Pages: 2267 - 2274

Two Accounts of Solitude in Online Communal Networks

Alla Venu Gopal, G. Srinivasa Reddy

Share this Article

Downloads: 3

Research Paper, Computer Science & Engineering, India, Volume 10 Issue 7, July 2021

Pages: 544 - 546

Green Computing: Current Research Trends

Vallabhi Ghansawant

Share this Article

Similar Articles with Keyword 'disk'

Downloads: 62 | Monthly Hits: ⮙1

Research Paper, Computer Science & Engineering, India, Volume 10 Issue 4, April 2021

Pages: 28 - 37

Glaucoma Detection Using Machine Learning

Sharanya S

Share this Article

Downloads: 100

Review Papers, Computer Science & Engineering, India, Volume 3 Issue 12, December 2014

Pages: 1058 - 1060

Data Integrity Proof in Cloud Computing using TPA with Privacy Preserving

Rushikesh P. Dhanokar

Share this Article

Similar Articles with Keyword 'graph'

Downloads: 105

Research Paper, Computer Science & Engineering, India, Volume 3 Issue 5, May 2014

Pages: 1751 - 1754

Joining Delay; Packet Delivery and Limitations of EGMP

G. Anandhi, Dr. S. K. Srivatsa

Share this Article

Downloads: 117 | Monthly Hits: ⮙2

Research Paper, Computer Science & Engineering, India, Volume 5 Issue 8, August 2016

Pages: 991 - 995

A Study and Comparative Analysis of Cryptographic Algorithms for Various File Formats

M. Meena, A. Komathi

Share this Article
Top