Abstract | We address an important communication issue arising in
wireless cellular networks that utilize frequency division
multiplexing (FDM) technology. In such networks, many
users within the same geographical region (cell) can communicate
simultaneously with other users of the network
using distinct frequencies. The spectrum of the available
frequencies is limited; thus, efficient solutions to the call
controlproblemareessential.Theobjectiveofthecallcontrol
problem is, given a spectrum of available frequencies
and users that wish tocommunicate, to maximize the benefit,
i.e., the number of users that communicate without
signalinterference.Weconsidercellularnetworksofreuse
distance k ≥ 2 and we study the online version of the
problem using competitive analysis. In cellular networks
of reuse distance 2, the previously best known algorithm
that beats the lower bound of 3 on the competitiveness
of deterministic algorithms, works on networks with one
frequency, achieves a competitive ratio against oblivious
adversaries, which is between 2.469 and 2.651, and uses
a number of random bits at least proportional to the size
of the network.We significantly improve this result by presentingaseriesofsimplerandomizedalgorithmsthathave
competitiveratiossignificantlysmallerthan3,workonnetworks
with arbitrarily many frequencies, and use only a
constant number of random bits or a comparable weak
random source. The best competitiveness upper bound
we obtain is 16/7 using only four random bits. In cellular
networks of reuse distance k > 2, we present simple
randomized online call control algorithms with competitive
ratios, which significantly beat the lower bounds on
the competitiveness of deterministic ones and use only
O(log k )randombits. Also,weshownewlowerboundson
thecompetitivenessofonlinecallcontrolalgorithmsincellularnetworksofanyreusedistance.
Inparticular,weshow
thatnoonline algorithm can achieve competitive ratio better
than 2, 25/12, and 2.5, in cellular networks with reuse
distancek ∈ 2, 3, 4,k = 5,andk ≥ 6, respectively. |