Easily-managed and topology-independent location service for self-organizing networks

ABSTRACT

The need for efficient location mechanisms is an important issue in scalable self-organizing networks. Existing solutions are inherently dependent on the spatial distribution of nodes in the topology. This leads to limitations that go against the principles of self-organization. In this paper, we propose Twins, an easily-managed location service for self-organizing networks. Twins defines a logical multidimensional space that is a strict mathematical representation of the network geographic space. This representation is obtained through Hilbert space-filling curves. The geographic space is used for addressing and routing, while localization is based on the curve. Control messages are routed based on the logical structure while data packets are routed in a hop-by-hop basis with greedy next-hop choice. In this paper, we evaluate the Twins management operations in terms of fairness of space sharing and logical/geographic distances between nodes and their location servers. Our results show that Twins assures a fair distribution of control overhead and scales well with the number of nodes.

REFERENCES

• 1: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 2: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 3: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 4: J. P. Hubaux, T. Gross, J. Y. L. Boudec, and M. Vetterli, "Towards self-organized mobile ad hoc networks: the terminodes project," IEEE Communications Magazine, vol. 39, no. 1, pp. 118--124, Jan. 2001.
• 5: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 6: Yuan Xue , Baochun Li , Klara Nahrstedt, A Scalable Location Management Scheme in Mobile Ad-Hoc Networks, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.102, November 14-16, 2001
• 7: Z. Xu, M. Mahalingam, and M. Karlsson, "Turning heterogeneity into an advantage in overlay routing," In Proceedings of IEEE Infocom, (San Francisco, CA), Mar. 2003.
• 8: A. C. Viana, M. D. Amorim, S. Fdida, and J. F. Rezende, "Self-organization in spontaneous networks: the approach of DHT-based routing protocols," To appear in Ad Hoc Networks Journal, 2005.
• 9: J. Ridoux, A. Fladenmuller, Y. Viniotis, and K. Salamatian, "Trellis-based virtual regular addressing structures in self-organized networks," in Proceedings of IFIP Networking, (Waterloo, Canada), pp. 511--522, May 2005.
• 10: B. Chen and R. Morris, "L+: Scalable landmark routing and address lookup for multi-hop wireless networks," tech. rep., Massachusetts Institute of Technology, Cambridge, Massachusetts - MIT LCS Technical Report 837 (MIT-LCS-TR-837), Mar. 2002.
• 11: J. Eriksson, M. Faloutsos, and S. Krishnamurthy, "Scalable ad hoc routing: The case for dynamic addressing," In Proceedings of IEEE Infocom, (Hong Kong), Mar. 2004.
• 12: Tetsuo Asano , Desh Ranjan , Thomas Roos , Emo Welzl , Peter Widmayer, Space-filling curves and their use in the design of geometric data structures, Theoretical Computer Science, v.181 n.1, p.3-15, July 15, 1997 [doi>10.1016/S0304-3975(96)00259-9]
• 13: B. Moghaddam, K. J. Hintz, and C. V. Steward, "Space-filling curves for image compression," in Automatic Object Recognition, 1991.
• 14: Loren K. Platzman , John J. Bartholdi, III, Spacefilling curves and the planar travelling salesman problem, Journal of the ACM (JACM), v.36 n.4, p.719-737, Oct. 1989 [doi>10.1145/76359.76361]
• 15: D. Hilbert, Ueber Stetige Abbildung Einer Linie auf ein Flachenstuck. Mathematische Annalenn, 38:459--460., 1891.
• 16: Greg Breinholt , Christoph Schierz, Algorithm 781: generating Hilbert's space-filling curve by recursion, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.184-189, June 1998 [doi>10.1145/290200.290219]
• 17: E. D. Kaplan, Understanding GPS: Principles and Applications. Artech House Telecommunications Library, 1996.
• 18: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 19: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 20: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Design, Management

Keywords:
location service, network topology, protocol architecture, routing protocols, self-organizing networks, wireless communication