Reed-Solomon and Hermitian Code-Based Scheduling Protocols for Wireless Ad Hoc Networks

  • Carlos H. Rentel
  • Thomas Kunz
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


In this work we investigate bounds on throughput and delay performance of a scheduling protocol that derives its decisions from codes traditionally used to correct or detect errors in the information carried over a noisy channel. In this paper we study the particular cases in which the Reed-Solomon and Hermitian code constructions are used. It is found that Hermitian codes outperform Reed-Solomon codes in minimum throughput guarantee and delay metrics when the number of nodes is in the order of thousands. The relative minimum distance of the code used to schedule the transmissions is identified as an important property that can be used to identify codes that can enable scheduling patterns with better minimum performance guarantees. Furthermore, the terminology of error control coding is used to present a more general and constructive framework for the study of code-based scheduling protocols.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Chlamtac, I., Farago, A.: Making transmission schedules immune to topology changes in multi-hop packet radio networks. IEEE/ACM Trans. Networking 2(1), 23–29 (1994)CrossRefGoogle Scholar
  2. 2.
    Ju, J.-H., Li, V.O.K.: An optimal topology-transparent scheduling method in multi-hop packet radio networks. IEEE/ACM Trans. Networking 6(3), 298–306 (1998)CrossRefGoogle Scholar
  3. 3.
    MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. North Holland Pub., Amsterdam (1977) ISBN: 0444850090Google Scholar
  4. 4.
    Einarsson, G.: Address assignment for a time-frequency-coded, spread-spectrum system. The Bell Systems Tech. Journal 59(7), 1241–1255 (1980)Google Scholar
  5. 5.
    Solomon, G.: Optimal frequency hopping sequences for multiple-access. In: Proceedings of the Symposium of Spread Spectrum Communications, vol. 1(AD-915 852), pp. 33–35 (1973)Google Scholar
  6. 6.
    Syrotiuk, V.R., Colbourn, C.J., Ling, A.C.H.: Topology-transparent scheduling for MANETs using orthogonal arrays. In: International Conference on Mobile Computing and Networking, San Diego, CA, pp. 43–49 (2003)Google Scholar
  7. 7.
    Hedayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal Arrays: Theory and Applications, 1st edn. Springer, Heidelberg (1999) ISBN: 0387987665Google Scholar
  8. 8.
    Rentel, C.H., Kunz, T.: On the average throughput performance of code-based scheduling protocols for Wireless Ad Hoc networks. In: ACM MobiHoc poster, Urbana-Champaign, Il (2005)Google Scholar
  9. 9.
    Wicker, S.B.: Error Control Systems for Digital Communication and Storage. Prentice Hall, Englewood Cliffs (1995) ISBN: 0132008092Google Scholar
  10. 10.
    Pretzel, O.: Codes and algebraic curves. Oxford science publications (1998) ISBN: 0198500394Google Scholar
  11. 11.
    Blake, I., Heegard, C., Hoholdt, T., Wei, V.: Algebraic-Geometry Codes. IEEE Transactions on Information Theory 44(6), 2596–2618 (1998)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Carlos H. Rentel
    • 1
  • Thomas Kunz
    • 1
  1. 1.Department of Systems and Computer EngineeringCarleton UniversityOttawaCanada

Personalised recommendations