Title :
Greedy Routing on Hierarchical Clusters
Author :
Bouabene, Ghazi ; Sifalakis, Manolis ; Tschudin, Christian
Author_Institution :
Comput. Sci. & Math. Dept, Univ. of Basel, Basel, Switzerland
Abstract :
Greedy geometric routing is one of the most appealing options for sensor and ad-hoc networks due to its simplicity, scalability and mainly stateless operation. However, its performance may vary when a low-dimensional embedding results in a graph with void regions and local minima locations. In this paper, we advocate the benefits of clustering for improving the performance of greedy routing over an existing embedding. Our contributions include: (a) an examination of the effects of clustering on influencing routing near void regions and overcoming problems with local minima, (b) a generic framework for enabling a cluster view for greedy routes, that can work with any low-dimensional embedding, and (c) a quantitative evaluation of the performance improvement we achieve, using some reference clustering approaches, over a number of virtual coordinate systems for geometric routing.
Keywords :
greedy algorithms; hierarchical systems; statistical analysis; telecommunication network routing; greedy routing; hierarchical clusters; influencing routing; low dimensional embedding; overcoming problems; quantitative evaluation; reference clustering approaches; virtual coordinate systems; Clustering algorithms; Clustering methods; Logic gates; Measurement; Routing; Switches; Topology; Clustering; Graph embedding; Greedy routing; Sensor networks;
Conference_Titel :
Embedded and Ubiquitous Computing (EUC), 2011 IFIP 9th International Conference on
Conference_Location :
Melbourne, VIC
Print_ISBN :
978-1-4577-1822-9
DOI :
10.1109/EUC.2011.40
