UML CS Research Paper Repository
Individual Paper Details

Browse By:  

Paper No.   Title   Author   Adviser   Topic   Type   Keyword  

Other Functions:  

Submit a Report   Reload Repository   View Credits

Rathi, H.M., Daniels, K.M., and Chandra, K. (2004).  A Shifting Strategy for Dynamic Channel Assignment.  INFORMS Journal on Computing.

This paper presents a new method for dynamic channel assignment (DCA) in wireless cellular systems under random spatio-temporal variation of traffic demand.  The method uses a two-phase integer programming (IP) based heuristic to minimize the number of channels required to satisfy the traffic demand and a threshold criterion based on the carrier-to-interference ratio.  The threshold determines a minimum reuse distance.  Reuse distance motivates the use of local demand and solutions to small subproblems to obtain tight lower and upper bounds on the minimum number of channels within a practical amount of execution time.  A core IP model (CIP) enforces demand satisfaction and cumulative interference constraints.  Lower bounds are generated for each possible state of the random demand function using local demand requirements and solutions to small instances of the CIP.  Upper bounds are found using a two-phase heuristic based on the CIP.  The first phase, SHIFT-IP, attempts to assemble a provably optimal solution for the entire cellular system using optimal solutions generated for sub-regions whose size is related to the reuse distance.  SHIFT-IP obtains global solutions by a fixed increment circular shift of each channel number assigned in a local solution.  When SHIFT-IP cannot match the best lower bound a second phase, GREEDY-IP, is executed.  GREEDY-IP uses the CIP iteratively by augmenting local solutions to an ordered list of ascending demand values.  The performance of the new DCA approach is evaluated for spatial distributions where 20% of the cells exhibit random demand in time, dictated by a two-state Markov process. SHIFT-IP obtains optimal results for an average of 86% of the demand states.  The results are compared with a non-IP greedy algorithm that sequentially allocates the first available channel that satisfies interference constraints.  The methods are comparable in performance when variable demand cell groups are well separated in space.  The IP solutions based on local optimization quickly yield globally optimal results for such cases.  For densely packed variable demand cell groups where cumulative interference rather than reuse distance is the governing criterion, the IP-based solutions yield fewer channels than given by the sequential assignment algorithm.  However, the IP approach is optimal less often for densely packed variable demand cell groups than for sparse ones.  Introducing randomized permutations of local channel assignments into SHIFT-IP helps mitigate this density effect.