ALCOMFT-TR-01-183

Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou
Randomized Call Control in Sparse Wireless Cellular Networks
Patras. Work packages 2 and 4. October 2001.

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 control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the benefit, i.e., the number of users that communicate without signal interference.

In previous work [CKP00,CKP01], the authors study the performance of algorithm p-Random; an intuitive on-line randomized call control algorithm for wireless cellular networks where each cell is a regular hexagon. In practice, however, at least parts of the network are expected to be sparser and irregular.

In the present work, we extend previous work on randomized call-control focusing on sparse wireless networks with irregular cell shape and small degree (three or four). We prove analytical upper bounds on the competitive ratio (defined as the maximum over all possible sequences of calls of the ratio of the benefit of the algorithm over the ratio of the optimal off-line algorithm) of algorithm p-Random against oblivious adversaries as a function of the parameter p. Optimizing the upper bound function, we prove that algorithm p-Random is 9/4- and 2.651-competitive on sparse wireless cellular networks supporting one frequency of degree three and four, respectively. Our algorithms extend to networks with many frequencies.

Postscript file: ALCOMFT-TR-01-183.ps.gz (75 kb).