Perfect periodic scheduling for three basic cycles |
| |
Authors: | Eun-Seok Kim Celia A. Glass |
| |
Affiliation: | 1. International Management and Innovation, Business School, Middlesex University, London, NW4 4BT, UK 2. Cass Business School, City University London, 106 Bunhill Row, London, EC1Y 8TZ, UK
|
| |
Abstract: | Periodic scheduling has many attractions for wireless telecommunications. It offers energy saving where equipment can be turned off between transmissions, and high-quality reception through the elimination of jitter, caused by irregularity of reception. However, perfect periodic schedules, in which each (of $n$ ) client is serviced at regular, prespecified intervals, are notoriously difficult to construct. The problem is known to be NP-hard even when service times are identical. This paper focuses on cases of up to three distinct periodicities, with unit service times. Our contribution is to derive a $O(n^4)$ test for the existence of a feasible schedule, and a method of constructing a feasible schedule if one exists, for the given combination of client periodicities. We also indicate why schedules with a higher number of periodicities are unlikely to be useful in practice. This methodology can be used to support perfect periodic scheduling in a wide range in real world settings, including machine maintenance service, wireless mesh networks and various other telecommunication networks transmitting packet size data. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|