Trajectory knowledge for improving topology control in mobile ad-hoc networks

ABSTRACT

While most topology control protocols only address limited network mobility, we propose in this paper a quasi-localized topology control algorithm that considers mobility predictions in order to construct and maintain a power efficient topology without relying on periodic beacons. Indeed, a node is capable of extracting linear trajectories of its neighboring nodes based on their positions and velocities. Based on such information, a node obtains a local prediction of neighborhood evolution and can thereafter proactively adapt the topology without relying on periodic beacons. Maintenance is driven on a per-event basis. It is therefore only when a node changes course that messages are exchanged in order to adapt the structure. Our approach is able to create and keep a stable kinetic backbone at a linear message and time complexity. It also improves concurrent communications by providing a significant reduction on local power assignments, therefore reducing interferences, increasing battery life and improving the overall network lifespan.

REFERENCES

• 1: P. Gupta and P. R. Kumar,"The capacity of wireless networks", in IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 388--404, March 2000.
• 2: S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar,"Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the compow protocol", in Proc. of the European Wireless'02, pp. 156--162, Florence, Italy, February 2002.
• 3: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 4: R. Ramanathan and R. Rosales-Hain,"Topology control of multihop wireless networks using transmit power adjustment", in Proc. IEEE INFOCOM 2000, pp. 404--413, Tel Aviv, Israel, March 2000.
• 5: V. Rodoplu and T. H. Meng,"Minimum energy mobile wireless networks", in IEEE J. Select. Areas Commun., pp. 1333--1344, vol. 17, no. 8, August 1999.
• 6: Li Li and Joseph Y. Helpern,"A Minimum-energy Path-preserving Topology-control Algorithm", in IEEE Transactions on Wireless Communications, pp. 910--921, vol. 3, no. 3, 2004.
• 7: Navid Nikaein , Houda Labiod , Christian Bonnet, DDR: distributed dynamic routing algorithm for mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 8: C. Gentile, J. Haerri, and R. E. Van Dyck, "Kinetic minimum-power routing and clustering in mobile ad-hoc networks," IEEE Proc. Vehicular Technology Conf. Fall 2002, pp. 1328--1332, September 2002.
• 9: R.J. Fontana and S.J. Gunderson, "Ultra-wideband precision asset location system", IEEE Conf. on Ultra Wideband Systems and Technologies, pp. 147--150, 2002.
• 10: C. Gentile and Luke Klein-Berndt, "Robust Location using System Dynamics and Motion Constraints", in Proc. of the IEEE International Conference on Communications (ICC'04), Paris, June 2004.
• 11: A. Laouiti et al, "Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks", 35th Annual Hawaii International Conference on System Sciences (HICSS'2001), Hawaii, USA, 2001.
• 12: T. Clausen et al, "Optimized Link State Routing Protocol", IEEE INMIC, Pakistan, 2001.
• 13: C.E. Perkins et al. "Ad Hoc On-Demand Distance Vector Routing", http://www.ietf.org/rfc/rfc3561.txt.
• 14: N. Li, J.C. Hou, L. Sha, "Design and analysis of an MST-based topology control algorithm", in Proc. of the IEEE Infocom Conference, pp. 1702--1712, Vol. 3, San Francisco, 2003.
• 15: J. Haerri and Christian Bonnet, "A Lower Bound for Vehicles' Trajectory Duration", in Proc of the IEEE 62nd Semiannual Vehicular Technology Conference (VTCFall'05), Dallas, USA, September 2005.
• 16: Ravi Prakash et al., "A Lower Bound for Broadcasting in Mobile Ad Hoc Networks", in EPFL Technical Report IC/2004/37, EPFL, Switzerland, 2004.
• 17: Xiang-Yang Li , Yu Wang , Wen-Zhan Song, Applications of k-Local MST for Topology Control and Broadcasting in Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.12, p.1057-1069, December 2004 [doi>10.1109/TPDS.2004.77]
• 18: Francisco Javier Ovalle-Martínez , Ivan Stojmenović , Fabián García-Nocetti , Julio Solano-González, Finding minimum transmission radii for preserving connectivity and constructing minimal spanning trees in ad hoc and sensor networks, Journal of Parallel and Distributed Computing, v.65 n.2, p.132-141, February 2005 [doi>10.1016/j.jpdc.2004.09.010]
• 19: Roger Wattenhofer, Aaron Zollinger "XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks", in 4th IEEE Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Santa Fe, April 2004.
• 20: Paolo Santi , Douglas M. Blough , Feodor Vainstein, A probabilistic analysis for the range assignment problem in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501446]
• 21: S. Basagni, D. Turgut, and S. K. Das, "Mobility-adaptive protocols for managing large ad hoc networks", in Proc. IEEE International Conference on Communications (ICC 2002), pp. 1539--1543, Helsinki, Finland, June 2001.

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Performance

Keywords:
localized topology control, power assignment, stochastic mobility prediction, trajectory, wireless ad hoc networks