MAC coding for QoS guarantees in multi-hop mobile wireless networks

ABSTRACT

The coding theory goal of finding codes with the largest possible distance among its constituent code-words in an ever smaller dimensional space is analogous to the goal of finding separate yet efficient ways for the nodes of a network to transmit in a multiple access system. A Medium Access Control (MAC) strategy is proposed referred to as MAC coding that leverages the use of codes traditionally used for channel coding purposes. It is shown how these codes can be utilized to device a scheduling strategy that has the potential to guarantee a minimum level of performance for the nodes of a multi-hop mobile wireless ad hoc network in an efficient manner. Additionally, coding theory results are used to derive simple expressions for the minimum throughput and delay of nodes when using Reed-Solomon and Hermitian error correcting codes as MAC scheduling codes.The average performance of a large family of MAC scheduling codes is analytically compared to the one obtained by slotted-ALOHA, and a code-selection algorithm is proposed that can improve the average throughput of MAC coding when the number of nodes in the network is greater than the number of code-words available in a given code.

REFERENCES

• 1: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 2: Ji-Her Ju , Victor O. K. Li, An optimal topology-transparent scheduling method in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.298-306, June 1998 [doi>10.1109/90.700893]
• 3: F.J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North Holland Pub. 1977.
• 4: G. Einarsson, Address assignment for a time-frequency-coded, spread-spectrum system, The Bell Systems Tech. Journal, vol. 59, No. 7, Sept. 1980, pp. 1241--1255
• 5: G. Solomon, Optimal frequency hopping sequences for multiple-access, Proceedings of the Symposium of Spread Spectrum Communications, vol. 1, AD-915 852, 1973, pp. 33--35
• 6: Violet R. Syrotiuk , Charles J. Colbourn , Alan C.H. Ling, Topology-transparent scheduling for MANETs using orthogonal arrays, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.43-49, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941086]
• 7: C.H. Rentel and T. Kunz, Reed-Solomon and Hermitian code-based scheduling protocols for wireless Ad Hoc networks, The 4th Int. Conf. on Wireless and Ad Hoc Networks, Cancun, Mexico, October 2005
• 8: Oliver Pretzel, Codes and algebraic curves, Oxford University Press, Inc., New York, NY, 1998

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

General Terms:
Algorithms, Performance, Theory

Keywords:
MAC protocol, QoS, codes, multi-hop mobile wireless networks