A study on distributed/centralized scheduling for wireless mesh network

ABSTRACT

The IEEE 802.16 standard proposes the Media Access Control (MAC) protocol for the Wireless Metropolitan Area Network (WMAN). Two transmission modes are defined in the IEEE 802.16, including Point-to-Multipoint (PMP) mode and mesh mode. In the 802.16 mesh mode, allocation of minislots can be handled by the centralized and distributed scheduling mechanisms. This paper proposes the Combined Distributed and Centralized (CDC) scheme to combine the distributed scheduling and centralized scheduling mechanisms so that the minislot allocation can be more flexible, and the utilization is increased. Two scheduling algorithms, Round Robin (RR) and Greedy, are proposed as the baseline algorithms for the centralized scheduling mechanism. We conduct simulation experiments to investigate the performance of the CDC scheme with the RR and Greedy algorithms. Our study indicates that with CDC scheme, the minislot utilization can be significantly increased.

REFERENCES

• 1: IEEE standard for local and metropolitan area networks part 16: Air interface for fixed broadband wireless access systems, May 2004.
• 2: I. Akyildiz and X. Wang. A survey on wireless mesh networks. IEEE Commun. Mag., 43(9):S23--S30, Sept. 2005.
• 3: R.-G. Cheng, S.-M. Cheng, and P. Lin. Power-efficient routing PER mechanism for odma systems. IEEE Trans. Veh. Technol., May 2006. to be published.
• 4: S.-M. Cheng, P. Lin, and D.-W. Huang. Minislot allocation for wireless mesh network. Under preparation.
• 5: 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]
• 6: I. Chlamtac and A. Lerner. Fair algorithms for maximal link activation in multihop radio networks. IEEE Trans. Commun., 35(7):739--746, July 1987.
• 7: Arr-Mien Chou , Victor O. K. Li, Slot allocation strategies for TDMA protocols in multihop packet radio networks, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.710-716, May 1992, Florence, Italy
• 8: S. Gandham, M. Dawande, and R. Prakash. Link scheduling in sensor networks: distributed edge coloring revisited. In INFOCOM '05, volume 4, pages 2492 -- 2501, 2005.
• 9: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 10: P. Lin, C.-H. Gan, and C.-C. Hsu. OVSF code channel assignment with dynamic code set and buffering adjustment fo UMTS. IEEE Trans. Veh. Technol., (2):591--602, Mar. 2005.
• 11: R. Nelson and L. Kleinrock. Spatial TDMA: A collison-free multihop channel access protocol. IEEE Trans. Commun., 33(9):934--944, Sept. 1985.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Performance

Keywords:
802.16, mesh, performance, scheduling, wireless