تخصیص کانال های رادیویی تلفن همراه با استفاده از برنامه ریزی پویا توسعه یافته

The channel assignment is an important aspect of cellular radio networks. Because of the limitations on the frequency spectrum, the optimal or near-optimal channel assignment has become an essential part of the network operations of wireless personal communication systems. We formulate a new strategy for the channel assignment problem in agreement with the electromagnetic compatibility constraints. We introduce and formulate the extended dynamic programming (EDP), as an extension of dynamic programming for solving the channel assignment problem in a cellular system. Using EDP an algorithm is developed for fixed channel assignment problem and it is tested and compared with other existing methods by solving different problems. In agreement with electromagnetic compatibility constraints, solution strategy based on EDP algorithm finds many valid solutions with minimum possible bandwidth.

The frequency assignment is an essential part of all applications of wireless communication networks. This requires tuning the transmitter and receiver to the same frequency. The selection of frequencies for all wireless connections can be done by solving a frequency assignment problem. In fact, the channel assignment involves the operation of assigning the required number of channels to each cell such that none of the electromagnetic compatibility constraints are violated. Two major paradigms in channel assignment are the fixed and dynamic approach. In the fixed channel assignment, the allocations are permanent to cells so that all cells can use all the channels assigned to them simultaneously without interference. Normally dynamic channel assignment provides better performance than fixed channel assignment except under heavy traffic load condition where fixed channel assignment outperforms dynamic channel assignment, see [1], since heavy traffic load is expected in the future generations (3G and beyond) of cellular radio networks, hence, an efficient fixed channel assignment scheme that provides high spectrum usage efficiently is desired. The approach by which all the available frequencies are assigned to each cell appropriately to reach the optimal solutions in some sense forms the key issue for the fixed channel assignment. When a call arrives in a cell, it is assigned to an unused channel and when there is no channel available, then the call is blocked without any pre-determined arrangements. However, in dynamic channel assignment, channels are assigned to different calls such that every channel is available to every call as required if the channel reuse constraint is not violated. Channel assignment can be based on some constraints that are usually in terms of frequency spacing between channels. An important set of constraints are the electromagnetic compatibility constraints [2], they are usually in terms of co-channel, the adjacent channel, and co-site constraints. The co-channel constraint is a descriptive terminology for the case when the same frequency cannot be used simultaneously by some radio cells or antennae that are geographically close. The adjacent channel constraint causes similar frequencies not to be assigned to adjacent radio channels simultaneously. The other important constraint is known as co-site where any pair of frequencies assigned to the radio cells at a site must be some distance apart, the higher the power emanating from the cell the larger is the frequency separation from other cells. Generally speaking, besides these constraints, there seems some practical issues that are of important considerations as well. They may include the extensions and adaptation to the existing network for the future changes. The difficulty in dealing with all these issues simultaneously often lead to methods that are unsatisfying theoretically and can breakdown unexpectedly. In this paper we only consider co-channel and adjacent channel constraints, and co-site frequency separation because these constraints represent the most important interference problems to avoid. We also assume that interference can be avoided if there is sufficient channel separation between the frequencies assigned to pairs of cells, this separation can be zero if no interference can occur between different cells. Considering all the constraints andmaintaining the importance of each objective, mathematically, appears as a combinatorial optimization and graph coloring which is known as NP-complete problem. Among recent developments in channel assignment problem include applications of neural networks [3] where a parallel algorithm is developed that is composed of nm processing elements for an n-cell-m-frequency problem, some more results based on applications of neural network are found in [4] and [5]. By considering the combinatorial optimization nature of channel assignment problem-simulated annealing [6], [7] and [8], tabu search [7] is also used. By considering pattern approach which fits naturally in most channel assignment problems a two-phase [9], heuristic algorithms [9], [10] and [11] are also formulated to deal with the channel assignment. Other researchers applied an adaptive local search [12] for the same purpose where an exhaustive local search is used to cope with the computational intractability of NP-hard combinatorial optimization. Another procedure allows the minimum distance between the consecutive channels of the same cell to vary between different spectrum points and as subsequent channels are being assigned according to electromagnetic compatibility constraints the spectrum width between consecutive channels are reduced by means of a fast iterative method [13], Genetic algorithms [14] and [15] are also applied for meeting electromagnetic compatibility constraints, for some more discussions of the other successfully tested methods in channel assignment problem, see [7]. In this paper, we base our solution approach on the use of the synchronized sequential decision strategy. Dynamic programming (DP) is a widely utilized scheme in operation research as a solution scheme for sequential decision problem [16], [17], [18] and [19]. The fundamental problem addressed by DP can be stated as “given a weighted, directed graph with an initial vertex, find the best path to some terminating vertex.” In our case, the terminating vertex is among a specified set of vertices, and the best path is interpreted as the lowest cost path, i.e. no interference and the least bandwidth, to reach channel assignment. However, DP is not directly applicable for channel assignment problem, therefore, we introduce and formulate EDP for such a task. The remainder of this paper is organized as follows: in Section 2, we discuss the fixed channel assignment using electromagnetic compatibility constraints. In Section 3, we provide the required modification as to DP resulting in a new algorithm, we call EDP. In Section 4, some simulation results and comparisons for a number of benchmark channel assignment problems are presented, and afterwards some concluding remarks at the end.

In this paper, we described a new and efficient approach to channel assignment problem for cellular networks. Our strategy is based on synchronous version of DP and we formulated EDP algorithm. We modified DP by introducing a nonnegative cost function that represents the minimum cost of moving from a call in a cell to another call in another cell in a cellular structure. This makes it possible to find some optimum paths for a fixed channel assignment plan with zero amount of interference and the least maximum bandwidth in a cellular structure. EDP differs from the existing methods in, its independence from any initial condition requirements, also, it can always determine more than one valid solution that meets electromagnetic compatibility constraints. EDP is based on a multistage minimization and a Trellis like structure and for practical problems better solutions than previously available ones are determined. We compared EDP against other methods used in channel assignment and showed through simulations that EDP always achieves the least maximum bandwidth and does not violate electromagnetic compatibility constraints. By repeating EDP on a problem the lower bound needed for the algorithm can be determined.