Optimization of packet scheduling in wireless systems with smart antennas: geometric models and algorithms

Beam forming techniques of adaptive antenna arrays (smart antennas) allow to reduce the mutual interference of simultaneous transmission in wireless access systems exploiting angular separation of user terminals. At the radio resource management layer the information on the arrival direction of signals can be taken into account by the scheduling algorithm so that transmissions of too close user terminals can be scheduled in different time-slots, while transmissions of users with an enough angular separation can be simultaneous. In other words, time diversity is exploited by the scheduling algorithm when spatial diversity is not sufficient to obtain good quality transmissions. In this paper we propose a novel approach to the problem of packet scheduling with smart antennas using mathematical programming. Based on a simplified system model we formulate two combinatorial optimization problems. In the first problem we have to select a subset of users, which can be simultaneously served in a given time slot so as to maximize the number or the total priority of the users served. An arc-circular model is proposed together with an exact polynomial-time algorithm, which searches for a path of maximum total weight in an appropriate graph. In the second problem users must be partitioned into non-interfering subsets so as to minimize the number of time slots needed to transmit all the given packets. For both problems heuristics have been devised in order to obtain approximate solutions in the short time available for packet scheduling in real systems.