Weak Greedy Routing over Graph Embedding for Wireless Sensor Networks

Zhigang Li, Nong Xiao

Computer School, National University of Defense Technology, Changsha, Hunan, China.

DOI: 10.4236/wsn.2010.29082                

Abstract

In this paper we classify the greedy routing in sensor networks into two categories, strong greedy routing and weak greedy routing. Most existing work mainly focuses on weak greedy routing over geographic location network or strong greedy routing over greedy embedding network. It is a difficult job and needs much cost to obtain geographic location or greedy embedding of the network. We propose a light-weight Tree-based graph embedding (TGE) for sensor networks. Over the TGE, we design a weak greedy routing protocol, TGR. TGR can archive good performance on path stretch factor and load balance factor.

Keywords

WSN, Greedy routing, Graph embedding, TGR

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	F. Ren, H. Huang and C. Lin, “Wireless Sensor Networks,” Journal of Software, Vol. 14, No. 7, 2003, pp.1282-1291.
[2]	L. M. Sun, J. Z. Li, Y. Chen and H. S. Zhu, “Wireless Sensor Network, Tsinghua University Press, Beijing, 2005.
[3]	B. Karp and H. T. Kung, “Gpsr: Greedy Perimeter Stateless Routing for Wireless Networks,” The 6th ACM Annual International Conference on Mobile Computing and Networking, Boston, 2000, pp. 243-254.
[4]	H. Frey and I. Stojmenovic, “On Delivery Guarantees of Face and Combined Greedy Face Routing in Ad Hoc and Sensor Networks,” The 12th ACM Annual International Conference on Mobile Computing and Networking, Los Angeles, 2006, pp. 390-401.
[5]	M. Li and Y. Liu, “Rendered Path: Range-Free Localization in Anisotropic Sensor Networks with Holes,” The 13th ACM Annual International Conference on Mobile Computing and Networking, Québec, 2007, pp. 51-62.
[6]	X. B. Wu, G. Chen and K. D. Sajal, “Avoiding Energy Holes in Wireless Sensor Networks with Non-uniform Node Distribution,” IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 5, May 2008, pp. 710- 720.
[7]	A. Cvetkovski and M. Crovella, “Hyperbolic Embedding and Routing for Dynamic Graphs, The 28th Conference on Computer Communication, Rio de Janeiro, Brazil, April 2009, pp.1647-1655.
[8]	C. Papadimitriou and D. Ratajczak, “On a Conjecture Related to Geometric Routing,” Theoretical Computer Science, Vol. 344, No. 1, 2005, pp. 3-14.
[9]	A G. Joseph, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, Vol. 16, 2009, pp. 1-219.
[10]	J. V. Leeuwen and B. Tan, “Interval Routing,” Computer Journal, Vol. 30, 1987, pp. 298-307.
[11]	J. Newsome and D. Song, “Gem: Graph Embedding for Routing and Datacentric Storage in Sensor Networks without Geographic Information,” The 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, 2003, pp. 76-88.
[12]	A. L. Rosenberg and L. S. Heath, “Graph Separators, with Applications,” Kluwer Academic/Plenum Publishers, Norwell, Massachusetts, 2001.