NDLI: Localized Delaunay triangulation with application in ad hoc wireless networks

Please wait, while we are loading the content...

Localized Delaunay triangulation with application in ad hoc wireless networks

Content Provider	IEEE Xplore Digital Library
Author	Xiang-Yang Li Calinescu, G. Peng-Jun Wan Yu Wang
Copyright Year	1990
Abstract	Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RING) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. (1999) recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance /spl par/uv/spl par/ is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2 5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG.
Sponsorship	IEEE Computer Society
Starting Page	1035
Ending Page	1047
Page Count	13
File Size	961415
File Format	PDF
ISSN	10459219
Volume Number	14
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Intelligent networks Wireless networks Routing protocols Network topology Wireless sensor networks Mobile ad hoc networks Cost function Global Positioning System Broadcasting Euclidean distance
Content Type	Text
Resource Type	Article
Subject	Signal Processing Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Localized fault-tolerant topology control in wireless ad hoc networks

Distributed Hashing for Scalable Multicast in Wireless Ad Hoc Networks

Improving source routing reliability in mobile ad hoc networks

Reactive planar spanner construction in wireless ad hoc and sensor networks

Localized topology control for unicast and broadcast in wireless ad hoc networks

Applications of k-local MST for topology control and broadcasting in wireless ad hoc networks

An Edge Constrained Localized Delaunay Graph for Geographic Routing in Mobile Ad Hoc Networks

Greedy Local Delaunay Triangulation Routing for Wireless Ad Hoc Networks

An Efficient Routing Approach over Mobile Wireless Ad-Hoc Sensor Networks

Localized Delaunay triangulation with application in ad hoc wireless networks

Similar Documents

Localized fault-tolerant topology control in wireless ad hoc networks

Distributed Hashing for Scalable Multicast in Wireless Ad Hoc Networks

Improving source routing reliability in mobile ad hoc networks

Reactive planar spanner construction in wireless ad hoc and sensor networks

Localized topology control for unicast and broadcast in wireless ad hoc networks

Applications of k-local MST for topology control and broadcasting in wireless ad hoc networks

An Edge Constrained Localized Delaunay Graph for Geographic Routing in Mobile Ad Hoc Networks

Greedy Local Delaunay Triangulation Routing for Wireless Ad Hoc Networks

An Efficient Routing Approach over Mobile Wireless Ad-Hoc Sensor Networks

Localized Delaunay triangulation with application in ad hoc wireless networks