CaltechAUTHORS
  A Caltech Library Service

MAP: medial axis based geometric routing in sensor networks

Bruck, Jehoshua and Gao, Jie and Jiang, Anxiao (Andrew) (2005) MAP: medial axis based geometric routing in sensor networks. In: MobiCom '05 Proceedings of the 11th annual international conference on Mobile computing and networking. ACM , New York, NY, pp. 88-102. ISBN 1-59593-020-5. https://resolver.caltech.edu/CaltechAUTHORS:20160811-164254714

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160811-164254714

Abstract

One of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communication. Important consideration includes scalability, routing complexity, the length of the communication paths and the load sharing of the routes. In this paper, we show that a compact and expressive abstraction of network connectivity by the medial axis enables efficient and localized routing. We propose MAP, a Medial Axis based naming and routing Protocol that does not require locations, makes routing decisions locally, and achieves good load balancing. In its preprocessing phase, MAP constructs the medial axis of the sensor field, defined as the set of nodes with at least two closest boundary nodes. The medial axis of the network captures both the complex geometry and non-trivial topology of the sensor field. It can be represented compactly by a graph whose size is comparable with the complexity of the geometric features (e.g., the number of holes). Each node is then given a name related to its position with respect to the medial axis. The routing scheme is derived through local decisions based on the names of the source and destination nodes and guarantees delivery with reasonable and natural routes. We show by both theoretical analysis and simulations that our medial axis based geometric routing scheme is scalable, produces short routes, achieves excellent load balancing, and is very robust to variations in the network model.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1080829.1080839DOIPaper
http://dl.acm.org/citation.cfm?doid=1080829.1080839PublisherPaper
http://resolver.caltech.edu/CaltechPARADISE:2005.ETR069Related ItemTechnical Report
ORCID:
AuthorORCID
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2005 ACM. This work was supported in part by the Lee Center for Advanced Networking at the California Institute of Technology, and by NSF grant CCR-TC-0209042.
Funders:
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
NSFCCR-TC-0209042
Subject Keywords:Algorithms, Design, Medial Axis, Routing, System Design, Sensor networks
Classification Code:C.2.2 [Computer Systems Organization ]: Computer-Communication Networks—Network Protocols; E.1 [Data]: Data Structures—graphs and networks
DOI:10.1145/1080829.1080839
Record Number:CaltechAUTHORS:20160811-164254714
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160811-164254714
Official Citation:Jehoshua Bruck, Jie Gao, and Anxiao (Andrew) Jiang. 2005. MAP: medial axis based geometric routing in sensor networks. In Proceedings of the 11th annual international conference on Mobile computing and networking (MobiCom '05). ACM, New York, NY, USA, 88-102. DOI=http://dx.doi.org/10.1145/1080829.1080839
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69578
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:12 Aug 2016 17:16
Last Modified:11 Nov 2021 04:16

Repository Staff Only: item control page