In an era where communication has a most important role in modern societies, designing efficient algorithms for data transmission is of the outmost importance. TDMA is a technology used in many communication systems such as satellite, cell phone as well as other wireless or mobile networks. Most 2G cellular systems as well as some 3G are TDMA based. In order to transmit data in such systems we need to cluster them in packages. To achieve a faster transmission we are allowed to preempt the transmission of any packet in order to resume at a later time. Preemption can be used to reduce idleness of some stations. Such preemptions though come with a reconfiguration cost in order to setup for the next transmission. In this paper we propose two algorithms which yield improved transmission scheduling. These two algorithms we call MGA and IMGA (Improved MGA). We have proven an approximation ratio for MGA and ran experiments to establish that it works even better in practice. In order to conclude that MGA will be a very helpful tool in constructing an improved schedule for packet routing using preemtion with a setup cost, we compare its results to two other efficient algorithms designed by researchers in the past: A-PBS(d+1) and GWA. To establish the efficiency of IMGA we ran experiments in comparison to MGA as well as A-PBS(d+1) and GWA. IMGA has proven to produce the most efficient schedule on all counts.
Download