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.