Periodic scheduling for wireless mesh networks

Wireless mesh networks (WMNs) provide flexible and low-cost Internet and Broadband access. Local access points (e.g. for WiFi access) connect to each other to facilitate a wide-area wireless mesh network. The star nature of access nodes disposes them to perfectly-periodic scheduling in which time is divided into time-slots, and each client gets a time slot at a predefined frequency. However, the problem of finding a feasible perfect-periodic schedule is NP-hard. We develop feasibility conditions for perfect periodic scheduling, using number-theoretic techniques, and devise a polynomial time algorithm for 3 co-prime frequencies. The results form a foundation for realistic scheduling of WMNs.