ISSN:
1572-9443
Keywords:
Scheduling
;
random polling
;
optimization
;
perturbation analysis
;
Golden Ratio policy
;
radio network
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract We address the problem of schedulingM customer classes in a single-server system, with customers arriving in one ofN arrival streams, as it arises in scheduling transmissions in packet radio networks. In general,N≠M and a customer from some stream may join one of several classes. We consider a slotted time model where at each scheduling epoch the server (channel) is assigned to a particular class (transmission set) and can serve multiple customers (packets) simultaneously, one from every arrival stream (network node) that can belong to this class. The assignment is based on arandom polling policy: the current time slot is allocated to theith class with probability θi. Our objective is to determine the optimal probabilities by adjusting them on line so as to optimize some overall performance measure. We present an approach based on perturbation analysis techniques, where all customer arrival processes can be arbitrary, and no information about them is required. The basis of this approach is the development of two sensitivity estimators leading to amarked slot and aphantom slot algorithm. The algorithms determine the effect of removing/ adding service slots to an existing schedule on the mean customer waiting times by directly observing the system. The optimal slot assignment probabilities are then used to design adeterministic scheduling policy based on the Golden Ratio policy. Finally, several numerical results based on a simple optimization algorithm are included.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01158437
Permalink
