DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
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.
DidaWiki

Strumenti Utente

Strumenti Sito

Strumenti Pagina
