Combinatorial Approach for Geographic Routing with Delivery Guarantees
Kasun Samarasinghe, Pierre Leone
2014
Abstract
In this paper we present a novel combinatorial approach for geographic routing with delivery guarantees. Proposed algorithm can be seen as a variant of GFG (Greedy Face Greedy of Bose et.al) algorithm, but based on the defined combinatorial properties of the graph. We utilize a distributed planarization algorithm of a geometric graph, which is based on the Schnyder’s characterization of planar graphs. The new approach is combinatorial in the sense that the nodes are ordered with respect to three distinct order relations satisfying the suitable properties. The coordinate system motivated the development of this routing algorithm is VRAC (Virtual Raw Anchor Coordinates), which localizes nodes based on the raw distances from three fixed anchors. Since the positions of the anchors need not to be known, the nodes localized by the VRAC coordinate system does not correspond to the exact geographic location of nodes, yet leaving sufficient information to define necessary combinatorial constructs.
DownloadPaper Citation
in Harvard Style
Samarasinghe K. and Leone P. (2014). Combinatorial Approach for Geographic Routing with Delivery Guarantees . In Proceedings of the 3rd International Conference on Sensor Networks - Volume 1: SENSORNETS, ISBN 978-989-758-001-7, pages 195-204. DOI: 10.5220/0004712501950204
in Bibtex Style
@conference{sensornets14,
author={Kasun Samarasinghe and Pierre Leone},
title={Combinatorial Approach for Geographic Routing with Delivery Guarantees},
booktitle={Proceedings of the 3rd International Conference on Sensor Networks - Volume 1: SENSORNETS,},
year={2014},
pages={195-204},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004712501950204},
isbn={978-989-758-001-7},
}
in EndNote Style
TY - CONF
JO - Proceedings of the 3rd International Conference on Sensor Networks - Volume 1: SENSORNETS,
TI - Combinatorial Approach for Geographic Routing with Delivery Guarantees
SN - 978-989-758-001-7
AU - Samarasinghe K.
AU - Leone P.
PY - 2014
SP - 195
EP - 204
DO - 10.5220/0004712501950204