Fixed channel assignment in cellular radio networks using amodified genetic algorithm

With the limited frequency spectrum and an increasing demand for cellular communication services, the problem of channel assignment becomes increasingly important. However, finding a conflict-free channel assignment with the minimum channel span is NP hard. Therefore, we formulate the problem by assuming a given channel span. Our objective is to obtain a conflict-free channel assignment among the cells, which satisfies both the electromagnetic compatibility (EMC) constraints and traffic demand requirements. We propose an approach based on a modified genetic algorithm (GA). The approach consists of a genetic-fix algorithm that generates and manipulates individuals with fixed size (i.e., in binary representation, the number of ones is fixed) and a minimum-separation encoding scheme that eliminates redundant zeros in the solution representation. Using these two strategies, the search space can be reduced substantially. Simulations on the first four benchmark problems showed that this algorithm could achieve at least 80%, if not 100%, convergence to solutions within reasonable time. In the fifth benchmark problem, our algorithm found better solutions with shorter channel span than any existing algorithms. Such significant results indicate that our approach is indeed a good method for solving the channel-assignment problem     

基于反向链路状态的动态优化信道分配

本文提出了一种基于反向链路载干比的信道分配优化模型.这种模型较原有的兼容矩阵模型更接近实际系统,并且能够应用于分析干扰自适应信道分配方案.本文在提出这种模型的同时,对比了该模型和原有模型在描述信道分配问题的精度和能力上的优劣.此外,本文还提出了使用改进遗传算法求解该模型下信道分配问题的方法.分析和实验均说明本文提出的模型对实际环境进行了更精确的描述,通过使用这种模型求解信道分配问题能够更好利用信道资源.     

Channel Assignment for Cellular Networks Based on a Local Modified Hopfield Neural Network

In this paper, we propose a modified discrete Hopfield neural networks algorithm for the channel assignment problem. In opposition to previous work, we tried to apply the optimization locally on a per cell basis in order to reduce the CPU processing time and decrease the designed system complexity while obtaining a near-optimum solution. In addition, the research is extended to study the algorithm performance in a more realistic cellular system where the number of requested channels is continuously changing with time. In this paper, the channel assignment problem is formulated as an energy function which is at its minimum when all the defined compatibility constraints are satisfied and the assigned channel number (ACN) is equal to the requested channel number (RCN) in each cell.     

Static and dynamic channel assignment using neural networks

We examine the problem of assigning calls in a cellular mobile network to channels in the frequency domain. Such assignments must be made so that interference between calls is minimized, while demands for channels are satisfied. A new nonlinear integer programming representation of the static channel assignment (SCA) problem is formulated. We then propose two different neural networks for solving this problem. The first is an improved Hopfield (1982) neural network which resolves the issues of infeasibility and poor solution quality which have plagued the reputation of the Hopfield network. The second approach is a new self-organizing neural network which is able to solve the SCA problem and many other practical optimization problems due to its generalizing ability. A variety of test problems are used to compare the performance of the neural techniques against more traditional heuristic approaches. Finally, extensions to the dynamic channel assignment problem are considered     

Maximum packing channel assignment in cellular networks

We study the performance of the maximum packing channel assignment algorithm (MPA) in channelized cellular networks. MPA is a greedy algorithm, which rejects a call only when it is forced to do so, even if this involves rearrangement of channels assigned to the ongoing calls, without dropping any of them. We ignore handoffs and model the channel reuse constraints in the cellular network by a hypergraph. As the traffic and the number of channels are scaled together, we get a limiting regime where the blocking probability in the cells can be computed by solving a nonlinear optimization problem. The carried traffic in this limiting case is an upper bound on the performance of MPA for practical finite-channel systems. We show that the performance of MPA in a finite-channel cellular system can be closely approximated by considering a simple fixed-routing circuit-switched network. Thus, the finite-channel performance of MPA can be studied using methods well known in the area of circuit-switched networks. We compare the performance of MPA with other asymptotically optimal algorithms and demonstrate its optimality for low and moderate offered traffic. We envisage MPA as a practical channel assignment algorithm, for moderate size systems, and suggest approximations to reduce its complexity     

A multiagent system for frequency assignment in cellular radionetworks

We present a multiagent algorithm for the frequency assignment problem in cellular radio networks. The algorithm, that has been successfully applied to GSM networks, efficiently assigns frequencies to each radio cell satisfying the constraints given by a compatibility matrix     

Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds     

Optimal channel assignment in cellular networks

In this paper, we consider the problem of assigning frequencies to mobile terminals in a cellular network. We show that an optimal solution can be obtained by solving a sequence of alternating linear and quadratic maximization programming problems. We address co-channel constraints and adopt as an objective function the maximization of potentially established calls. Our algorithm is fairly general, and does not depend on any special network structure. This study indicates that mathematical programming can be used as an efficient technique for solving the aforementioned problem.     

Routing and wavelength assignment in optical networks from edgedisjoint path algorithms

Routing and wavelength assignment (RWA) problems in wavelength-routed optical networks are typically solved using a combination of integer programming and graph coloring. Such techniques are complex and make extensive use of heuristics. We explore an alternative solution technique in the well-known maximum edge disjoint paths (EDP) problem which can be naturally adapted to the RWA problem. Maximum EDP is NP-hard, but now it is known that simple greedy algorithms for it are as good as any of the more complex heuristic solutions. In this paper we investigate the performance of a simple greedy maximum edge disjoint paths algorithm applied to the RWA problem and compare it with a previously known solution method     

A three-stage heuristic combined neural-network algorithm forchannel assignment in cellular mobile systems

A three-stage algorithm of combining sequential heuristic methods into a parallel neural network is presented for the channel assignment problem in cellular mobile communication systems in this paper. The goal of this NP-complete problem is to find a channel assignment to requested calls with the minimum number of channels subject to interference constraints between channels. The three-stage algorithm consists of: (1) the regular interval assignment stage; (2) the greedy assignment stage; and (3) the neural-network assignment stage. In the first stage, the calls in a cell determining the lower bound on the total number of channels are assigned channels at regular intervals. In the second stage, the calls in a cell with the largest degree and its adjacent cells are assigned channels by a greedy heuristic method. In the third stage, the calls in the remaining cells are assigned channels by a binary neural network. The performance is verified through solving well-known benchmark problems. Especially for Sivarajan's benchmark problems, our three-stage algorithm first achieves the lower bound solutions in all of the 13 instances, while the computation time is comparable with existing algorithms     

A Viterbi-like algorithm with adaptive clustering for channelassignment in cellular radio networks

A new channel assignment algorithm, called the Viterbi (1967) -like algorithm (VLA), is proposed to solve the channel assignment problem in cellular radio networks. The basic idea of the proposed algorithm is step-by-step (sequential) channel assignment with the objectives of minimum bandwidth required at every step, subject to adjacent channel and cochannel separation constraints. The VLA provides the benefits of minimum required bandwidth, stability of solution, and fast execution time. The performance of the VLA is evaluated by computer simulation, applied first to 19 benchmark problems on channel assignment and then applied to study cellular radio network performance. Results from computer simulation studies show that bandwidth requirements by VLA closely match or are sometimes better than those of the existing channel assignment algorithms. Furthermore, it is found that execution of VLA is approximately two times faster than the local search algorithm-the existing channel assignment algorithm with the least bandwidth requirements. The combined advantages of minimum required bandwidth, stability of solution, and fast execution time make the VLA a useful candidate for cellular radio network planning     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

Neural network-based dynamic channel assignment for cellular mobilecommunication systems

Conventional dynamic channel assignment schemes are both time-consuming and algorithmically complex. An alternative approach, based on cascaded multilayered feedforward neural networks, is proposed and examined on two cellular systems with different configurations. Simulation results showed that the blocking performance of our multistage neural network approach can match that of an example conventional scheme with less complexity and higher computational efficiency. The example scheme considered here is the ordered channel search, which can achieve a reasonably high spectral efficiency as compared to that of an ideal dynamic channel allocation algorithm. We conclude that our neural network approach is well-suited to the dynamic channel allocation problem of future cellular or microcellular systems with decentralized control     

Design of an Efficient Channel Block Retuning

Cellular networks must be updated very often. Due to technical and economical reasons, the complete channel retuning of an urban network has to be done in several steps. The objective is then to define the steps in such a way that the increase in the interference level is minimum, and do not let it go further than a given threshold of minimum quality for the cellular network. We propose a greedy heuristic and an ascent–descent method including a Tabu Search module to retune a network in a given number of steps. All constraints of the channel assignment problem are taken into account (co-channel, adjacent channel, minimum channel spacing on antennas) as well as retuning constraints such as the number of steps and limits on the maximum number of cells which can be retuned at each step. Co-channel and adjacent channel constraints are expressed through compatibility matrices produced with a discretization of the signal-to-interference ratio. Numerical results are presented on a Bell Mobilité urban network of 359 cells.     

Optimal radio channel assignment through a new binary dynamic simulated annealing algorithm

The radio channel assignment problem (CAP) is classified as an NP-complete binary optimization problem, which creates the need for faster, yet optimal optimization algorithms to reduce the time of computation when solving such a complex problem. Simulated annealing (SA), a powerful optimal combinatorial search algorithm, was found to be very suitable for CAP. This paper extends the standard capabilities of SA and proposes a new CAP-oriented, quicker binary SA, the binary dynamic SA (BDSA) algorithm, as part of a newly proposed radio channel assignment approach. Simulation results proved that the proposed BDSA has very fast convergence as a stand-alone algorithm and even faster convergence with the newly proposed radio channel assignment approach. © 1998 John Wiley & Sons, Ltd.     

Offline Impairment-Aware Routing and Wavelength Assignment Algorithms in Translucent WDM Optical Networks

Physical impairments in optical fiber transmission necessitate the use of regeneration at certain intermediate nodes, at least for certain lengthy lightpaths. We design and implement impairment-aware algorithms for routing and wavelength assignment (IA-RWA) in translucent optical networks. We focus on the offline version of the problem, where we are given a network topology, the number of available wavelengths and a traffic matrix. The proposed algorithm selects the 3R regeneration sites and the number of regenerators that need to be deployed on these sites, solving the regenerator placement problem for the given set of requested connections. The problem can be also posed in a slightly different setting, where a (sparse) placement of regenerators in the network is given as input and the algorithm selects which of the available regenerators to use, solving the regenerator assignment problem. We formulate the problem of regenerator placement and regenerator assignment, as a virtual topology design problem, and address it using various algorithms, ranging from a series of integer linear programming (ILP) formulations to simple greedy heuristic algorithms. Once the sequence of regenerators to be used by the non-transparent connections has been determined, we transform the initial traffic matrix by replacing non-transparent connections with a sequence of transparent connections that terminate and begin at the specified 3R intermediate nodes. Using the transformed matrix we then apply an IA-RWA algorithm designed for transparent (as opposed to translucent) networks to route the traffic. Blocked connections are re-routed using any remaining regenerator(s) in the last phase of the algorithm.      

Lagrangean Based Methods for Solving Large-Scale Cellular Network Design Problems

The cellular network design (CND) problem is formulated as a comprehensive linear mixed integer programming model integrating the base station location (BSL) problem, the frequency channel assignment (FCA) problem and the topological network design (TND) problem. A solution algorithm based on Lagrangean relaxation is proposed for solving this complex cellular network design problem. Pursuing the optimum solution through exact algorithms to this problem appears to be unrealistic considering the large scale nature and NP-hardness of the problem. Therefore, the solution algorithm strategy consists in computing effective lower and upper bounds for the problem. Lower bounds are evaluated through a Lagrangean relaxation technique and subgradient method. A Lagrangean heuristic is developed to compute upper bounds based on the Lagrangean solution. The bounds are improved through a customized branch and bound algorithm which takes in account specific knowledge of the problem to improve its efficiency. Thirty two random test instances are solved using the proposed algorithm and the CPLEX optimization package. The results show that the duality gap is excessive, so it cannot guarantee the quality of the solution. However, the proposed algorithm provides optimal or near optimal solutions for the problem instances for which CPLEX also provides the optimal solution. It further suggests that the proposed algorithm provides optimal or near optimal solutions for the other instances too. Finally, the results demonstrate that the proposed algorithm is superior to CPLEX as a solution approach for the CND problem.     

Joint Throughput Optimization for Wireless Mesh Networks

In this paper, we address the problem of joint channel assignment, link scheduling, and routing for throughput optimization in wireless networks with multiradios and multichannels. We mathematically formulate this problem by taking into account the interference, the number of available radios the set of usable channels, and other resource constraints at nodes. We also consider the possible combining of several consecutive channels into one so that a network interface card (NIC) can use the channel with larger range of frequencies and thus improve the channel capacity. Furthermore, we consider several interference models and assume a general yet practical network model in which two nodes may still not communicate directly even if one is within the transmission range of the other. We designed efficient algorithm for throughput (or fairness) optimization by finding flow routing, scheduling of transmissions, and dynamic channel assignment and combining. We show that the performance, fairness and throughput, achieved by our method is within a constant factor of the optimum. Our model also can deal with the situation when each node will charge a certain amount for relaying data to a neighboring node and each flow has a budget constraint. Our extensive evaluation shows that our algorithm can effectively exploit the number of channels and radios. In addition, it shows that combining multiple channels and assigning them to a single user at some time slots indeed increases the maximum throughput of the system compared to assigning a single channel.     

Channel assignment using genetic algorithm based on geometric symmetry

The paper deals with the channel assignment problem in a hexagonal cellular network with two-band buffering, where channel interference does not extend beyond two cells. Here, for cellular networks with homogeneous demands, we find some lower bounds on the minimum bandwidth required for various relative values of s/sub 0/, s/sub 1/, and s/sub 2/, the minimum frequency separations to avoid interference for calls in the same cell, or in cells at distances of one and two, respectively. We then present an algorithm for solving the channel assignment problem in its general form using the elitist model of genetic algorithm (EGA). We next apply this technique to the special case of hexagonal cellular networks with two-band buffering. For homogeneous demands, we apply EGA for assigning channels to a small subset of nodes and then extend it for the entire cellular network, which ensures faster convergence. Moreover, we show that our approach is also applicable to cases of nonhomogeneous demands. Application of our proposed methodology to well-known benchmark problems generates optimal results within a reasonable computing time.     

Robust vector quantization for wireless channels

This study focuses on two issues: parametric modeling of the channel and index assignment of codevectors, to design a vector quantizer that achieves high robustness against channel errors. We first formulate the design of a robust zero-redundancy vector quantizer as a combinatorial optimization problem leading to a genetic search for a minimum-distortion index assignment. The performance is further enhanced by the use of the Fritchman (1967) channel model that more closely characterizes the statistical dependencies between error sequences. This study also presents an index assignment algorithm based on the Fritchman model with parameter values estimated using a real-coded genetic algorithm. Simulation results indicate that the global explorative properties of genetic algorithms make them very effective in estimating Fritchman model parameters, and use of this model can match index assignment to expected channel conditions