Abstract
As the use of mobile communications systems grows, the need arises for new and more efficient channel allocation techniques. The total number of available channels on a real-world network is in fact a scarce resource, and many assignment heuristics suffer from a clear lack of flexibility (this is the case of Fixed Channel Allocation), or from high computational and communication complexity (as with channel borrowing techniques). Performance can be improved by representing the system with an objective function whose minimum is associated with a good configuration; the various constraints appear as penalty terms in the function. The problem is thus reduced to the search for a minimum, that is often performed via heuristic algorithms like Hopfield neural networks, simulated annealing or reinforcement learning. These strategies usually require a central process to have global information and decide for all cells. We consider an objective-function formulation of the channel assignment problem that has been previously solved by search heuristics; we prove that the search time for the global minimum of the objective function is O(nlog n), and therefore there is no need for search techniques. Finally we show that the algorithm that arises from this formulation can be modified so that global knowledge and synchronization are no longer required, and we give its distributed version. By simulating a cellular network with mobile hosts on a hexagonal cell pattern with uniform call distribution, we show that our technique actually performs better than the best known algorithms.
Similar content being viewed by others
References
E. Upfal and E. Shamir, Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces, Journal of Algorithms 5 (1984) 488–501.
A.A. Bertossi and M.A. Bonuccelli, Code assignment for hidden terminal interference avoidance in multihop packet radio networks, IEEE/ACM Transactions on Networking 3 (1995) 441–449.
R. Battiti, A.A. Bertossi and M.A. Bonuccelli, Assigning codes in wireless networks: Bounds and scaling properties, Wireless Networks 5 (1999) 195–209.
O. Bertazioli and L. Favalli, GSM - Il Sistema Europeo di Comunicazione Mobile: Tecniche, Architettura e Procedure (ATES, Hoepli, Milan, 1996).
I. Katzela and M. Nagshineh, Channel assignment schemes for cellular mobile telecommunication systems: A comprehensive survey, IEEE Personal Communications (June 1996) 10–31.
S. Jordan and E.J. Schwabe, Worst-case performance of cellular channel assignment policies, Wireless Networks 2 (1996) 265–275.
S. Singh and D. Bertsekas, Reinforcement learning for dynamic channel allocation in cellular telephone systems, in: NIPS96 (1996).
M. Duque-Antón, D. Kunk and B. Rüber, Channel assignment for cellular radio networks using simulated annealing, IEEE Transactions on Vehicular Technology 42(1) (February 1993) 14–21.
E. Del Re, R. Fantacci and L. Ronga, A dynamic channel allocation technique based on Hopfield neural networks, IEEE Transactions on Vehicular Technology 45(1) (February 1996) 26–32.
K.L. Yeung and T.-S.P. Yum, Compact pattern based dynamic channel assignment for cellular mobile systems, IEEE Transactions on Vehicular Technology 43(4) (November 1994) 892–896.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Battiti, R., Bertossi, A.A. & Brunato, M. Cellular Channel Assignment: A New Localized and Distributed Strategy. Mobile Networks and Applications 6, 493–500 (2001). https://doi.org/10.1023/A:1011806003955
Issue Date:
DOI: https://doi.org/10.1023/A:1011806003955