WSN  Vol.2 No.9 , September 2010
Weak Greedy Routing over Graph Embedding for Wireless Sensor Networks
Author(s) Zhigang Li, Nong Xiao
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.

Cite this paper
nullZ. Li and N. Xiao, "Weak Greedy Routing over Graph Embedding for Wireless Sensor Networks," Wireless Sensor Network, Vol. 2 No. 9, 2010, pp. 683-688. doi: 10.4236/wsn.2010.29082.
[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.