Balancing distance and lifetime in delay constrained ad hoc networks

ABSTRACT

This paper addresses the problem of optimizing the packet transmission schedule in an ad hoc network with end-to-end delay constraints. The emphasis is to determine the proper relative weights assigned to the remaining distance and the remaining lifetime in order to rank the urgency of a packet. We consider a general class of transmission schemes that represent such relative weights using a single lifetime-distance factor, which includes, as special cases, schedules such as Earliest-Deadline-First and Largest-Distance-First. We propose an analytical framework, based on recursive non-homogeneous Markovian analysis, to study the effect of the lifetime-distance factor on packet loss probability in a general multihop environment, with different configurations of peer-node channel contention. Numerical results are presented to demonstrate how various network parameters affect the optimal lifetime-distance factor. We demonstrate quantitatively how the proper balance between distance and lifetime in a transmission schedule can significantly improve the network performance, even under imperfect schedule implementation.

REFERENCES

• 1: IEEE Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications IEEE Standard 802.11, Jun 1999.
• 2: M. Andrews and L. Zhang. Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule. In Proc. IEEE INFOCOM 1999.
• 3: D. J. Baker, A. Ephremides, and J. A. Flynn. The architectural organization of a mobile radio network with distributed control. IEEE J. Select. Areas Commun. SAC-2:226--237, January 1984.
• 4: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 5: Craig Barrack , Kai-Yeung Siu, A Distributed Scheduling Algorithm for Quality of Service Support in Multiaccess Networks, Proceedings of the Seventh Annual International Conference on Network Protocols, p.245, October 31-November 03, 1999
• 6: Chris Barrett , Achla Marathe , Madhav V. Marathe , Martin Drozda, Characterizing the interaction between routing and MAC protocols in ad-hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513812]
• 7: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 8: F. M. Chiussi and V. Sivaraman. Achieving high utilization in guaranteed services networks using early-deadline-first scheduling. In Proc. IEEE IWQoS 1998.
• 9: I. Daubechies and J. C. Lagarias. Sets of matrices all in finite products of which converge. Linear Algebra and Its Applications 161:227--263, 1992.
• 10: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 11: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Floor acquisition multiple access (FAMA) for packet-radio networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.262-273, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 12: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 13: Z. J. Haas and J. Deng. Dual busy tone multiple access (DBTMA)-a multiple access control scheme for ad hoc networks.IEEE Trans. on Communications 50(6):975--985, Jun 2002.
• 14: Z. J. Haas and et al. Wireless ad hoc networks. In J. Proakis, editor, Wiley Encyclopedia of Telecommunications John Wiley & Sons, 2002.
• 15: J. Hajnal. Weak ergodicity in nonhomogeneous markov chains. In Proc. Cambridge Philosophical Society volume 54, pages 233--246, 1958.
• 16: V. Kanodia , C. Li , A. Sabharwal , B. Sadeghi , E. Knightly, Distributed multi-hop scheduling and medium access with delay and throughput constraints, Proceedings of the 7th annual international conference on Mobile computing and networking, p.200-209, July 2001, Rome, Italy [doi>10.1145/381677.381697]
• 17: V. Kanodia , A. Sabharwal , B. Sadeghi , E. Knightly, Ordered packet scheduling in wireless ad hoc networks: mechanisms and performance analysis, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513808]
• 18: G. Karlsson. Asynchronous transfer of video. IEEE Communications Magazine 34:106--113, Feb 1996.
• 19: P. Karn. MACA - a new channel access method for packet radio. In ARRL/CRRL Amateur Radio 9th Computer Networking Conference 1990.
• 20: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 21: Chengzhi Li , Edward W. Knightly, Coordinated multihop scheduling: a framework for end-to-end services, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.776-789, December 2002 [doi>10.1109/TNET.2002.805024]
• 22: B. Liang and Z. J. Haas. Hybrid routing in ad hoc networks with a dynamic virtual backbone. In press, IEEE Trans. Wireless Comm. preliminary version in Proc. IEEE INFOCOM 2000.
• 23: Jörg Liebeherr , Dallas E. Wrege , Domenico Ferrari, Exact admission control for networks with a bounded delay service, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.885-901, Dec. 1996 [doi>10.1109/90.556345]
• 24: Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345923]
• 25: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 26: T. Ozugur, M. Naghshineh, P. Kermani, and J. Copeland. Fair media access for wireless LANs. In Proc. IEEE Globecom 1999.
• 27: A. Papoulis and S. U. Pillai. Probability, Random Variables, and Stochastic Processes Fourth Edition, McGraw-Hill, 2002.
• 28: C. E. Perkins, editor. Ad Hoc Networking Addison-Wesley Longman, 2001.
• 29: Kay Römer, Time synchronization 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/501436.501440]
• 30: R. Rozovsky , P. R. Kumar, SEEDEX: a MAC protocol for 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/501426.501427]
• 31: K. K. Vadde and V. R. Syrotiuk. Factor interaction on service delivery in mobile ad hoc networks. IEEE J. Selected Areas in Communications 22(7):1335--1346, Sep 2004.
• 32: Nitin H. Vaidya , Paramvir Bahl , Seema Gupta, Distributed fair scheduling in a wireless LAN, Proceedings of the 6th annual international conference on Mobile computing and networking, p.167-178, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345939]
• 33: C. Wu , V. Li, Receiver-initiated busy-tone multiple access in packet radio networks, Proceedings of the ACM workshop on Frontiers in computer communications technology, p.336-342, August 11-13, 1987, Stowe, Vermont, United States

INDEX TERMS

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

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
cross-layer design, delay constraint, multihop packet scheduling, stochastic analysis