DidaWiki

The new generation of wireless networks (e.g., 802.16/WiMAX, etc.) offers different kind of services (e.g., VoIP, videophone, audio and video streaming, etc.), having different requirements of quality of service, but the wireless system resource, the bandwidth, is limited and must be shared among many users. Therefore, these networks need to adopt both sophisticated transmission techniques, such as the OFDMA one, and proper packet scheduling algorithms that allocates the bandwidth to many user transmissions. We investigate two scheduling problems: The first one, is called Minimum Length OFDMA Scheduling (or MOLOS), and deals with the problem of scheduling best effort traffic in a system adopting variable-length frames, with the objective of producing a legal schedule (i.e. one meeting all the system constraints) with minimum length. We noticed that, although fixed-frame length leads to an easier system management, it often does not fully exploit the system capabilities. This is especially true when the traffic is not high, and the fixed-length of the schedule is too large, leaving some empty time slots at the end of the frame. We formally prove that MLOS is NP-complete, and thus computationally intractable, even in an extremely simple and basic case. The NP-completeness of MLOS excludes the possibility of optimally solve MLOS with an algorithm having a polynomial time complexity. Since in OFDMA systems a schedule must be produced in few milliseconds, we proposed fast and simple heuristics, and evaluate their average performance by means of a simulation experiment. The second problem we investigate, deals with the scheduling of real time traffic, with the objective of meeting as many deadlines as possible or equivalently, minimizing the packet drop ratio. The traffic we consider is a periodic one (e.g., phone call, VoIP, etc.), consisting of fixed-size packets issued at fixed periodic intervals. Packets transmitted later than deadline expiration are dropped, but a given percentage of missed deadlines is tolerated. We deduced from the NP-completeness of MLOS, that also this problem in NP-complete, even in a very restricted case, when all deadlines are equal to one time slot and it is asked to minimize the number of missed deadlines. We presented two heuristic algorithms, W-EDF and S-EDF, which decide on the user to be scheduled first combining several information about users and their service requests, and applying the \time slot-per-time slot“ scheme and the \deadline-per-deadline” one, respectively. We evaluated proposed heuristics performance by means of a simulation experiment, and showed that S-EDF heuristic performs better than W-EDF one, in the average case.