Title :
Solving large scale channel allocation problems with splitting algorithms
Author :
Xie, Xi ; Wicker, Stephen B.
Author_Institution :
Sch. of Electr. Eng., Cornell Univ., Ithaca, NY, USA
Abstract :
The basic channel allocation problem (CAP) is known to be NP-hard. In this paper, splitting algorithms are proposed that significantly decrease computational load for centralized CAP algorithms by segmenting a problem, sequentially solving the smaller individual problems and then combining the solutions. This method is shown to have comparable performance with the non-splitting scheme for the same CAP algorithm. Experimental results using the random walk algorithm are presented
Keywords :
cellular radio; channel allocation; computational complexity; radiofrequency interference; random processes; NP-hard problem; QoS; cell layout; cellular radio; centralized CAP algorithms; computational complexity; experimental results; interference; large scale channel allocation problems; nonsplitting scheme; random walk algorithm; splitting algorithms; Algorithm design and analysis; Base stations; Channel allocation; Concurrent computing; Control systems; Interference; Large-scale systems; Partitioning algorithms; Quality of service; Wireless networks;
Conference_Titel :
Communications, 2000. ICC 2000. 2000 IEEE International Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-7803-6283-7
DOI :
10.1109/ICC.2000.853369
