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

In this paper, we propose a new approach to the fixed channel assignment problem by modifying the dynamic programming technique. This new strategy extends the already known dynamic programming so that the channel assignment solutions can be obtained. There is no need to have an initial random solution for convergence. One of the questions in the fixed channel assignment is the minimum bandwidth, which is usually unknown; the new strategy can obtain this lower bound. Parallel processing can be implemented over the proposed algorithm. The existing fixed channel assignment methods do not have all these in one place. The performance of modified dynamic programming (MDP) is evaluated by computer simulation, applied to seven well-known benchmark problems on channel assignment. The channel assignment strategies results shows that required bandwidths of modified dynamic programming are closely match or sometimes better than the algorithms that we have investigated.

The appearance of cellular mobile communication systems and their rapid growth due to the portability and the availability of these systems provided an important alternative in the field of wireless mobile communications. The increasing demand of new services in this field, however, is in contrast to the capacity constraints inherent in the current communication systems. Hence, the use of techniques, which are capable of ensuring that the frequency spectrum assigned for use in mobile communications will be better utilized, is gaining an ever-increasing importance. This makes the task of channel assignment more and more crucial [1]. The channel assignment problem (CAP) in this paper is based on a common model. The service area of the system is divided into a number of hexagonal cells. Every user is located in one cell. When a user requests a call in this system, a channel is assigned to that user to provide the communication service. This channel assignment must satisfy the electromagnetic compatibility (EMC) constraints to avoid the radio interference between channels. Three types of EMC constraints have usually been considered in CAP. 1. The co-channel constraint (CCC): The same channel cannot be assigned to cells that have a certain distance from each other. 2. The adjacent channel constraint (ACC): Adjacent channels cannot be assigned to adjacent cells simultaneously. In other words, any pair of channels in adjacent cells must have specified distance. Note that the distance indicates the difference in the channel domain. 3. The co-site constraint (CSC): Any pair of channels in a cell must have a specified distance. This distance is usually larger than necessary distance for ACC. The channel assignment problem (CAP) is then to allocate channel to every requested call in a cellular radio network subject to the above three EMC constraints such that the required bandwidth is minimized. Channel assignment is generally classified into fixed and dynamic. In fixed channel assignment (FCA), channels are nominally assigned to cells in advance according to the predetermined estimated traffic intensity. In dynamic channel assignment (DCA), channels are assigned dynamically as calls arrive. The latter method makes cellular systems more efficient particularly if the traffic distribution is unknown or changes with time, but has the disadvantage of requiring more complex control and is generally time consuming [2]. Normally, DCA gives better performance than FCA except under heavy traffic load condition, where FCA outperforms DCA [3]. Since heavy traffic load is expected in the future generation of cellular radio networks, an efficient FCA scheme that can provide high spectrum usage efficiency is desired. The FCA problem has been studied extensively for the past three decades. A comprehensive summary of the work done before 1980 can be found in [4]. Various extensions or combinations of the above two schemes have been discussed in the literature. The most basic are the hybrid channel assignment (HCA) and the borrowing channel assignment (BCA). In HCA, the set of channels of the cellular system is divided into two subsets, from which the one uses FCA and the other DCA. In BCA , the channel assignment is initially fixed. If there are incoming calls for a cell whose channels are all occupied, the cell borrows channels from its neighboring cells and thus call blocking is prevented [5] and [6]. In the simplest form of the channel assignment problem, the co-channel constraint only is considered, and the problem is known to be equivalent to a graph coloring problem [4]. Since the graph coloring problem is known to be non-deterministic polynomial-complete (NP-complete) [7], therefore, CAP is also NP-complete. So, the calculation time and the computation complexity of searching for the optimum solution in the channel assignment problem grow exponentially with the problem size. The rest of the paper is organized as follows. In Section 2, we review existing solution approaches for the channel assignment problem. In Section 3, we formulate the channel assignment problem. In Section 4, we discuss two typical problems, in which dynamic programming has been extensively used. In Section 5, we introduce modified dynamic programming based on dynamic programming represented in Section 4. In Section 6, we assess the quality of MDP method by using it to solve seven well-known benchmark channel assignment problems and then compare the results with three of the existing channel assignment algorithms. Finally, we conclude our work in Section 7.

In this paper, we proposed a new and efficient algorithm to solve channel assignment problems in cellular radio networks that is based on synchronous version of DP and has a Trellis structure. We modified DP by defining function ζ (k , ℓ) as (20) to apply co-channel, adjacent channel and co-site constraints on channel assignment problem and adding term View the MathML source∑k=m-11ζ(ξk(ℓ),j) that represents frequency interference of the current channel with all previous channels. Consequently, MDP can find some optimum or near optimum solutions for a fixed channel assignment problem with no interference and the least bandwidth in a cellular structure. MDP differs from the other three methods in its independence from any initial solution requirements, also it can determine more than one valid solution and it is able to find the actual value of lb for a specific problem. We compared the performance of MDP against the other three methods used in channel assignment problem and showed through simulations that MDP achieves better solutions with the least necessary bandwidth that does not violate any electromagnetic compatibility constraints.