Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

10.4 CHANNEL ASSIGNMENT IN MOBILE-RADIO SYSTEMS

At a high level, the channel-assignment problem is a resource-allocation problem [23]. The resources are communication channels in the radio time-frequency domain. Users and the base station are distributed geographically across the service area. A user's request to make a call is handled at the nearest base station, which decides whether to accept or to block the call. As a rule, in making that decision the base station communicates with other base stations, typically using an independent wired signaling network. An accepted call is allocated a channel for communication with its base station, which separately manages the connection (wireless or wired) to the call's destination.

Recent demands for mobile-telephone service has been growing rapidly. At the same time, the electromagnetic spectrum or frequencies allocated for this purpose are limited. Thus, the channel-assignment problem is subject to this limitation, as well as to the interference constraints between channels adjacent in the spectrum. This makes solving the problem of channel assignment very critical. Finding a valid channel assignment is known as an NP-complete problem [9]. Therefore, researchers have turned to heuristic techniques to find a good (suboptimal) solution to this problem.

10.4.1 A Channel-Assignment Problem

Gamst and Rave [25] defined the general form of the channel-assignment problem in an arbitrary cellular radio network. In their definition, the electromagnetic ...