Abstract
For message delivery in sensor network, greedy forwarding, face routing, and hybrid greedy-face routing have been used extensively. In this paper we present a method for improved face routing by introducing the notion of ‘floating chains’ and ‘external clusters’. The proposed technique removes unnecessary nodes and node clusters from the Gabriel graph extracted from the unit disk graph induced by sensor nodes. We present efficient algorithms for identifying solo-faced chains and external clusters in the network. Removal of such nodes leads to improved performance of face routing methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Bibliography
de Berg Mark, Van Kreveld Mark, Overmars Mark, and Schwarzkopf Otfried (1997) Computational Geometry: Algorithms and Applications, Springer. New York.
Bose P, Morin P, Stojmenovic I, Urrutia J (2001) Routing with guaranteed delivery in ad hoc network. Wireless networks. 609-616.
Cormen T, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT Press. Massachusetts.
Fortune S (1986) A sweep line algorithm for Voronoi diagram, Algorithmica. 2:153-174.
Gabriel KR, Sokal RR (1969) A new statistical approach to geographic variation analysis. Systematic zoology 18(3): 259-270.
Gao J, Guibas LJ, Hershberger L, Zhang L, Zhu (2001) A geometric spanner for routing in mobile networks. IEEE journal on selected areas in communications. 23:174-185.
Gewali L, Hada U (2013) Node filtering and face routing in sensor network. Proceedings of ITNG 2013: 686-691.
Matula DW, Sokal R (1980) Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane. Geographical analysis 12(3): 205-222
O’Rourke J (1994) Computational geometry in C. Cambridge University Press, New York.
Toussaint G (1980). The relative neighborhood graph of a finite planar set. Pattern recognition 12: 261-268.
Zhao F, Guibas L (2004) Wireless sensor network. Morgan Kaufmann. New York.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Gewali, L., Amatya, U. (2015). Identification of Redundant Node-Clusters for Improved Face Routing. In: Selvaraj, H., Zydek, D., Chmaj, G. (eds) Progress in Systems Engineering. Advances in Intelligent Systems and Computing, vol 366. Springer, Cham. https://doi.org/10.1007/978-3-319-08422-0_65
Download citation
DOI: https://doi.org/10.1007/978-3-319-08422-0_65
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08421-3
Online ISBN: 978-3-319-08422-0
eBook Packages: EngineeringEngineering (R0)