Reinforcement Learning for Dynamic Channel Allocation in Cellular Telephone Systems
Authors: Dimitri P. Bertsekas Satinder P. Singh
Published in: Advances in Neural Information Processing Systems 9  (NIPS 1996) (Main Conference Track), 1996

Abstract: In cellular telephone systems, an important problem is to dynami(cid:173) cally allocate the communication resource  (channels) so as to max(cid:173) imize  service  in  a  stochastic  caller  environment.  This problem  is  naturally formulated  as  a  dynamic programming problem and  we  use a reinforcement learning (RL) method to find  dynamic channel  allocation policies that are better than previous heuristic solutions.  The policies obtained perform well for  a  broad variety of call traf(cid:173) fic  patterns.  We  present  results  on  a  large  cellular  system  with  approximately 4949  states. 
In  cellular  communication systems,  an  important problem  is  to  allocate the com(cid:173) munication resource  (bandwidth) so as to maximize the service provided to a set of  mobile callers whose  demand for  service  changes stochastically.  A given  geograph(cid:173) ical  area is  divided  into mutually disjoint  cells,  and each  cell  serves  the  calls that  are  within  its  boundaries  (see  Figure  1a).  The total system  bandwidth is  divided  into channels, with each channel centered  around a frequency.  Each channel can be  used simultaneously at different  cells,  provided these  cells are sufficiently separated  spatially, so that there  is  no interference  between  them.  The minimum separation  distance between simultaneous reuse of the same channel is called the  channel reuse  constraint. 
When a call requests service in a given cell  either a free  channel  (one that does not  violate the channel  reuse  constraint)  may be assigned  to the  call, or else  the call  is  blocked  from  the system;  this  will  happen  if no free  channel  can  be found.  Also,  when a mobile caller crosses from one cell to another, the call is  "handed off"  to the  cell of entry;  that is,  a  new  free  channel is provided to the call at the new  cell.  If no  such  channel  is available,  the call  must be dropped/disconnected  from  the system. 
RLfor Dynamic Channel Allocation 
975 
One  objective  of a  channel  allocation  policy  is  to  allocate  the  available  channels  to calls  so  that the  number of blocked  calls is  minimized.  An  additional objective  is  to  minimize the  number of calls  that  are  dropped  when  they  are  handed off to  a  busy  cell.  These  two objectives  must  be  weighted  appropriately  to reflect  their  relative importance, since dropping existing calls is generally more undesirable than  blocking new  calls.  To  illustrate  the  qualitative  nature  of the  channel  assignment  decisions,  suppose  that  there  are  only  two  channels  and  three  cells  arranged  in  a  line.  Assume  a  channel  reuse  constraint  of 2,  i.e.,  a  channel  may  be  used  simultaneously  in  cells  1 and  3,  but may not  be  used  in  channel  2  if it is  already  used  in  cell  1 or  in  cell  3.  Suppose  that  the  system  is  serving  one  call  in  cell  1 and  another  call  in  cell  3.  Then  serving  both  calls  on  the  same  channel  results  in  a  better  channel  usage  pattern than serving them on different  channels,  since  in  the former case the other  channel  is  free  to  be  used  in  cell  2.  The  purpose  of the  channel  assignment  and  channel rearrangement strategy is,  roughly speaking, to create such favorable usage  patterns that minimize the likelihood of calls  being blocked. 
We formulate the channel assignment problem as a dynamic programming problem,  which,  however,  is too complex to be solved exactly.  We introduce approximations  based on the methodology of reinforcement learning (RL) (e.g.,  Barto,  Bradtke and  Singh,  1995, or the recent textbook by  Bertsekas and Tsitsiklis, 1996).  Our method  learns channel allocation policies that outperform not only the most commonly used  policy  in  cellular  systems,  but  also  the  best  heuristic  policy  we  could  find  in  the  literature. 
1  CHANNEL ASSIGNMENT POLICIES 
Many cellular systems are based on a fixed  assignment  (FA) channel allocation; that  is,  the set  of channels  is  partitioned,  and  the  partitions are  permanently  assigned  to cells  so  that  all  cells  can  use  all  the  channels  assigned  to them  simultaneously  without  interference  (see  Figure  1a).  When  a  call  arrives  in  a  cell,  if any  pre(cid:173) assigned channel is unused; it is assigned, else the call is blocked.  No rearrangement  is done when a call terminates.  Such a policy is static and cannot take advantage of  temporary stochastic  variations in  demand for  service.  More  efficient  are  dynamic  channel  allocation  policies,  which  assign  channels  to different  cells,  so  that  every  channel  is  available to every  cell  on  a  need  basis,  unless  the  channel  is  used  in  a  nearby  cell  and the reuse  constraint is  violated. 
The  best  existing  dynamic  channel  allocation  policy  we  found  in  the  literature  is  Borrowing with  Directional Channel  Locking  (BDCL)  of Zhang  &  Yum  (1989).  It  numbers the  channels  from  1 to N,  partitions and  assigns  them to cells  as  in  FA.  The  channels  assigned  to  a  cell  are  its  nominal  channels.  If a  nominal  channel  is  available  when  a  call  arrives  in  a  cell,  the  smallest  numbered  such  channel  is  assigned  to the call.  If no  nominal channel  is  available, then  the  largest  numbered  free  channel  is  borrowed from  the neighbour  with the most free  channels.  When a  channel  is  borrowed,  careful  accounting  of the  directional  effect  of which  cells  can  no  longer  use  that  channel  because  of interference  is  done.  The  call  is  blocked  if  there  are  no free  channels  at  all.  When a  call  terminates  in  a  cell  and the channel  so  freed  is  a  nominal channel,  say  numbered  i,  of that  cell,  then  if there  is  a  call  in  that  cell  on  a  borrowed  channel,  the  call  on  the  smallest  numbered  borrowed  channel  is  reassigned  to i  and the borrowed  channel  is  returned  to the appropriate  cell.  If there  is no  call  on  a  borrowed  channel,  then  if there  is  a  call  on  a  nominal  channel numbered  larger than i, the call on the highest numbered nominal channel  is  reassigned  to i.  If the call just terminated was  itself on  a  borrowed channel,  the 
976 
S.  Singh and D.  Bertsekas 
call on the smallest numbered borrowed channel is reassigned to it and that channel  is  returned  to the  cell  from  which  it  was  borrowed.  Notice  that  when  a  borrowed  channel  is  returned  to its original cell,  a  nominal channel  becomes free  in that cell  and triggers  a  reassignment.  Thus,  in the  worst  case  a  call  termination in one  cell  can sequentially cause reassignments in arbitrarily far  away cells - making BDCL  somewhat impractical. 
BOCL is quite sophisticated and combines the notions of channel-ordering, nominal  channels,  and  channel  borrowing.  Zhang  and  Yum  (1989)  show  that  BOCL  is  superior  to  its  competitors,  including  FA.  Generally,  BOCL  has  continued  to  be  highly  regarded  in  the  literature  as  a  powerful  heuristic  (Enrico  et.al.,  1996) .  In  this  paper,  we  compare  the  performance  of dynamic  channel  allocation  policies  learned  by  RL  with  both  FA  and  BOCL. 
1.1  DYNAMIC  PROGRAMMING FORMULATION 
We  can formulate the dynamic channel allocation problem using dynamic program(cid:173) ming (e.g.,  Bertsekas,  1995).  State transitions occur when channels become free due  to call departures,  or  when  a  call  arrives  at a  given  cell  and  wishes  to be  assigned  a  channel,  or when  there  is  a  handoff,  which  can  be  viewed  as  a  simultaneous call  departure  from  one  cell  and  a  call  arrival  at  another  cell.  The  state  at  each  time  consists of two components: 
(1)  The  list  of occupied  and  unoccupied  channels  at  each  cell.  We  call  this  the  configuration of the cellular system.  It is  exponential in the number of cells.  (2) The event that causes the state transition (arrival, departure, or handoff).  This 
component of the state is uncontrollable. 
The  decision/control  applied  at  the  time of a  call  departure  is  the  rearrangement  of the  channels  in  use  with  the  aim of creating  a  more favorable  channel  packing  pattern  among  the  cells  (one  that  will  leave  more  channels  free  for  future  assign(cid:173) ments) .  Unlike  BDCL,  our  RL  solution  will restrict  this rearrangement  to the  cell  with  the  current  call departure.  The  control exercised  at the time of a  call  arrival  is  the  assignment of a  free  channel,  or the blocking of the call if no free  channel  is  currently  available.  In  general,  it may also  be  useful  to  do  admission  control,  i.e.,  to  allow  the  possibility  of not  accepting  a  new  call  even  when  there  exists  a  free  channel to minimize the dropping of ongoing calls during handoff in the future.  We  address  admission control in a separate paper  and here  restrict  ourselves  to always  accepting a call if a free  channel is available.  The objective is to learn a  policy that  assigns  decisions  (assignment or  rearrangement  depending  on  event)  to each  state  so  as  to  maximize 
J  =  E {lCO  e- f3t e(t)dt} , 
where  E{-} is  the expectation operator,  e(t) is  the number of ongoing calls at time  t,  and j3  is  a discount factor that makes immediate profit more valuable than future  profit.  Maximizing J  is equivalent to minimizing the expected  (discounted)  number  of blocked  calls over  an infinite horizon. 
2  REINFORCEMENT LEARNING SOLUTION 
RL  methods solve optimal control (or dynamic programming) problems by  learning  good  approximations  to  the  optimal  value  function,  J*,  given  by  the  solution  to 
RLfor Dynamic Channel Allocation 
977 
the  Bellman optimality equation  which  takes  the  following form  for  the  dynamic  channel allocation problem: