N-GAIR: Non-Greedy Asynchronous Interference Reduction Algorithm in Wireless Networks
In this paper, we consider optimum channel/frequency allocation problem in wireless networks by reducing total network interference signal powers, which is an NP-complete problem. Its optimum solution for general wireless networks for even 2-channel case is not known. Turning the channel/frequency allocation problem into a maxCut graph partitioning problem, we i) propose a spectral clustering based channel allocation algorithm, called SpecPure, and ii) propose and analyze a novel Non-Greedy Asynchronous Interference Reduction Algorithm for Wireless Networks, called N-GAIR, and iii) extend the results in  to the case where the number of channels is arbitrary. By simulating various CDMA based ad-hoc networks, we examine various scenarios to compare the performances of the proposed algorithms with the reference algorithm. We draw various conclusions for different network scenarios. For example, the results show that the SpecPure algorithm performs well for “symmetric” base locations scenarios, while the N-GAIR performs best for random base locations scenarios. The results confirm the effectiveness of the proposed algorithms, which can be adopted by any cellular, cognitive, ad-hoc or mesh type radio networks.
Keywords: Mobile radio systems; optimum channel/frequency allocation; max cut, weighted graph partitioning; spectral clustering; minimum-interferencechannel-allocation algorithm.