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.     

Channel assignment in cellular radio networks

The authors investigate algorithms based on simulated annealing to solve the channel assignment problem for cellular radio networks. The blocking probability of a network is chosen as the optimization criterion. In order to check the quality of the solutions obtained by simulated annealing, they examine some special types of networks which allow an effective calculation of optimal solutions by tailored algorithms. Their investigations show that simulated annealing is a very powerful tool for solving channel assignment problems     

Handover and channel assignment in mobile cellular networks

A taxonomy of channel assignment strategies is provided, and the complexity in each cellular component is discussed. Various handover scenarios and the roles of the base station and the mobile switching center are considered. Prioritization schemes are discussed, and the required intelligence distribution among the network components is defined     

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     

Reconfiguration of carrier assignment in cellular networks

We consider the problem of updating nominal carrier assignments in cellular networks, which dymamically operate with channel borrowing and reassignments, to match the timevarying offered traffic demands encountered on these systems. Assuming an existing assignment of nominal carriers and the new requirements in each cell, we formulate the problem of obtaining a new assignment such that the number of carriers required to meet the total traffic demand as well as the number of different assignments between the old and the new allocation are minimized. We introduce two approaches to obtain this new assignment. One approach treats the two objectives independently and is applicable to problems with cochannel interference constraints only. This approach produces a new assignment optimized with respect to the first goal, and then rearranges the frequencies of this new allocation so that the number of different assignments with respect to the previous allocation is minimum. A second approach aims at satisfying both goals at the same time and is applicable to problems with any type of interference constraints. The main advantage of this approach is the introduction of a single window parameter which can control the assignments produced, by favoring one goal at the expense of the other. We study several transition scenarios in macrocellular and microcellular environments, and show that in the majority of cases these objectives are conflicting, and that reconfiguration strongly depends on the amount of change of the traffic requirements.     

Minimization of frequency assignment span in cellular networks

We consider the problem of minimizing the span of frequencies required to satisfy a certain demand in a cellular network under certain interference constraints. A new iterative algorithm exploiting the special nature of such systems is presented. The general procedure has the ability to react to variations of the traffic demand as more and more channels are being assigned to cell requirements. Allocations of channels to cells are made with a method that borrows insight from the theory of convex maximization. This method is, however, equivalent to simple and fast heuristics when selecting proper values for its parameters. Our technique yields quite encouraging results, showing that it represents an efficient alternative to attacking this type of problems     

Location tracking of mobiles in cellular radio networks

Some useful services in cellular radio networks and also a class of handover algorithms require knowledge of the present position and velocity of mobiles. This paper deals with a method to track mobiles by on-line monitoring of field strength data of surrounding base stations at successive time points. Such data is available in present global system for mobile communication (GSM) systems each 0.48 s and also in code-division multiple-access (CDMA) systems for transmission control. Because of strong random fluctuations of the signals, appropriate smoothing is the key point of the procedure. We develop a locally linear prediction model of successive positions as a basis for Kalman filtering. This approach turns out to be extremely successful, achieving average mislocations of 70 m in simulated test runs. Further improvement is possible by using external geographical information     

Location management strategies for cellular mobile networks

Location management in mobile communication systems is concerned with those network functions necessary to allow the users to be reached wherever they are in the network coverage area. The basic operations for that purpose-paging and location updating-are resource-consuming since both involve signalling over the radio link between the mobile stations and base stations. Future cellular mobile communication networks (wireless personal communication networks (PCN)) will have to support a large number of users, so a significant amount of radio signalling can be expected. This paper describes the conventional location management strategy (the one used in modern cellular systems like the Global System for Mobile communications (GSM)) and reviews, describes and comments on some alternative location management proposals for future high-density PCN environments that aim to reduce this expected high (radio) signalling load     

Virtually fixed channel assignment in cellular mobile networks with recall and handoffs

A promising approach for implementing channel assignment and control in cellular mobile telephone networks is the virtually fixed channel assignment (VFCA) scheme. In VFCA channels are allocated to cells according to the fixed channel assignment (FCA) scheme, but cells are allowed to borrow channels from one another. As such, VFCA maintains the efficiency of FCA, but adds the flexibility lacking in FCA. One feature of a VFCA network is that, to prevent co-channel interference, it requires several channels to be locked to serve a single call that borrows a channel. This feature raises the concern that VFCA may lead to chain reaction in channel borrowing among cells and cause the network performance to degrade, especially under heavy traffic conditions. In this paper, we propose the virtually fixed channel assignment with recall (VFCAWR) scheme: The network is implemented according to VFCA, but a cell can recall a locked channel to service an arriving handoff call, which occurs when a mobile unit crosses the boundary of its cell. We model the network as a three-dimensional Markov chain and derive its steady-state performance. Through modification of this basic model, we evaluate two dynamic channel assignment strategies, the virtual channel reservation (VCR) strategy and the linear switch-over (LSO) strategy, which exploit the unique borrowing/recall capability of VFCAWR to reduce the weighted cost of blocking fresh and handoff calls by reserving several virtual channels (the channels that may be borrowed from adjacent cells when necessary) for handoff calls. We validate the analytical models by simulation; the simulation test cases show that our models accurately predict the system performance measures of interest. Numerical and simulation results also show that both dynamic strategies outperform conventional channel reservation schemes based on fixed channel assignment and hybrid channel assignment. This revised version was published online in June 2006 with corrections to the Cover Date.     

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     

A dynamic channel assignment scheme for clustered multihop cellular networks

Whereas cellular systems have traditionally adopted single‐hop transmissions between the mobile station (MS) and the base station (BS), researchers expect multihop transmission to be utilised in the future. Cellular systems present several challenges, such as channel assignment, which are exacerbated by multimedia service traffic and an increasing number of subscribers. Recently, a clustered multihop cellular network (cMCN) architecture that complements traditional cellular systems has been proposed and studied using fixed channel assignment (FCA). However, the performance of FCA is limited when the traffic pattern varies in a service area. This paper proposes the use of dedicated information ports (DIPs) as clusterheads in cMCN, followed by a multihop dynamic channel assignment (mDCA) scheme. The mDCA works by assigning channels based on information about interference in surrounding cells. Two different channel searching strategies are developed and evaluated. Through computer simulation, we show that the proposed mDCA is able to achieve a significantly improved capacity which is maintained when the number of system channels is increased. Finally, issues regarding the implementation of the mDCA and future work on this topic are discussed. Copyright © 2007 John Wiley & Sons, Ltd.     

QoS provisioning in energy-efficient cooperative networks with power assignment and relay deployment planning

Wireless Networks - The cooperative network is an energy-efficient technology to provide ubiquitous broadband access and quality-of-service (QoS). This paper investigates the tradeoffs among QoS,...     

Coalesced CAP: an improved technique for frequency assignment in cellular networks

This paper presents an elegant technique for solving the channel assignment problem (CAP) for second generation (2G) cellular mobile networks, where channel allocation is made on a quasi-fixed basis and all sessions are connection oriented. It first maps a given CAP P to a modified coalesced CAP P' on a smaller subset of cells of the network, which appreciably reduces the search space. This helps to solve the problem P' by applying approximate algorithms very efficiently, reducing the computing time drastically. This solution to P' is then used to solve the original problem P by using a modified version of the forced assignment with rearrangement (FAR) operation reported by Tcha et al. (IEEE Trans. Veh. Technol., vol. 49, p. 390, 2000). The proposed technique has been tested on well-known benchmark problems. It has produced optimal solutions for all cases with an improved computation time. For instance, it needs only around 10 and 20 s (on an unloaded DEC Alpha station 200 4/233) to get an optimal assignment for the two most difficult benchmark problems 2 and 6, respectively, with zero call blocking, in contrast to around 60 and 72 s (on an unloaded Sun Ultra 60 workstation) reported by Ghosh et al. Moreover, as a by-product of this approach, there remain, in general, many unused or redundant channels that may be used for accommodating small perturbations in demands dynamically.     

Markov mobility model and registration area optimization in cellular networks

In cellular communication systems, in order for a network to keep track of inactive mobile stations (MSs), each inactive MS has to update its location from time to time, called location registration. To lighten the task of tracking inactive MSs, the network divides its cells into groups, called location areas (LAs) and tracks inactive MSs at the LA level: an inactive MS sends a registration message to the network to update its location only when it travels to a new LA. Obviously, the performance of a location area design depends on network traffic and the mobility of MSs. In the paper, we propose a general Markov mobility model for MSs in cellular networks, provide a procedure to automatically estimate the system parameters according to the network traffic, derive the performance of LA design, and provide a clustering algorithm to optimize LA designs. A numerical example is provided to show the effectiveness of the proposed procedures. Copyright © 2009 John Wiley & Sons, Ltd.     

Radio planning and coverage optimization of 3G cellular networks

Radio planning and coverage optimization are critical issues for service providers and vendors that are deploying third generation mobile networks and need to control coverage as well as the huge costs involved. Due to the peculiarities of the Code Division Multiple Access (CDMA) scheme used in 3G cellular systems like UMTS and CDMA2000, network planning cannot be based only on signal predictions, and the approach relying on classical set covering formulations adopted for second generation systems is not appropriate. In this paper we investigate mathematical programming models for supporting the decisions on where to install new base stations and how to select their configuration (antenna height and tilt, sector orientations, maximum emission power, pilot signal, etc.) so as to find a trade-off between maximizing coverage and minimizing costs. The overall model takes into account signal-quality constraints in both uplink and downlink directions, as well as the power control mechanism and the pilot signal. Since even small and simplified instances of this NP-hard problem are beyond the reach of state-of-the-art techniques for mixed integer programming, we propose a Tabu Search algorithm which provides good solutions within a reasonable computing time. Computational results obtained for realistic instances, generated according to classical propagation models, with different traffic scenarios (voice and data) are reported and discussed. Preliminary results have been presented in [5, 7, 8]. This work has been supported by the “Progetto Cofinanziato 2001–2003” of the Italian Ministry of Education, University and Scientific Research (MIUR), Optimization models and methods for telecommunication network design and management. Edoardo Amaldi received the “Diplome” in Mathematical Engineering from the Swiss Federal Institute of Technology at Lausanne (EPFL) in 1988. After one year in the Computational and Neural Systems program, California Institute of Technology, USA, he came back at EPFL where he earned the “Doctoratés Sciences” (PhD) in October 1994. He then joined the School of Operations Research and Industrial Engineering, Cornell University, USA, where he did research and taught graduate courses in mathematical programming. Since 1998 he is with the Dipartimento di Elettronica e Informazione (DEI), Politecnico di Milano, Italy, where he is currently an Associate Professor in Operations Research. His main research interests are in discrete optimization, the design and analysis of algorithms, and computational complexity with applications in telecommunications, image/signal processing, machine learning, and computational biology/finance. In 2005 he received an IBM Faculty Award for his work on the maximum feasible subsystem problem. He serves on the Program Committees of several international workshops and conferences (including the European Symposium on Algorithms, International Network Optimization Conference, International Workshop on Efficient and Experimental Algorithms–WEA) and since 2005 he is on the Steering Committee of WEA. Antonio Capone is an Associate Professor at the Dipartimento di Elettronica e Informazione of the Technical University of Milan (Politecnico di Milano). His expertise is on networking and main research activities include protocol design (MAC and routing) and performance evaluation of wireless access and multi-hop networks, traffic management and quality of service issues in IP networks, and network planning and optimization. He received the M.S. and Ph.D. degrees in electrical engineering from the Politecnico di Milano in 1994 and 1998, respectively. In 2000 he was a visiting professor at UCLA, Computer Science department. He currently serves as editor of the Wiley Journal of Wireless Communications and Mobile Computing. He served in the technical program committee of several international conferences and he is a regular reviewer of the main journals in the networking area. He is currently involved in the scientific and technical activities of several national and European research projects, and he leads several industrial projects. He is a Senior Member of the IEEE. Federico Malucelli (Ferrara, 7/4/62) got a Laurea in Computer Science and Ph.D. in Computer Science both from Universita’ di Pisa in 1988 and 1993 respectively. Since 2003 he is full professor of Operations Research at the Politecnico di Milano. In 1998–2002 he was associate professor of Operations Research at the Politecnico of Milano, and from 1992 to 1998 research associate at Pisa and Perugia Universities. He has visited several foreign universities and research laboratories, including HP Laboratories, Palo Alto (USA), Universite’ de Montreal (Canada) and Linkoping Universitet (Sweden). He has served as research unit coordinator for several nationwide MIUR and CNR research projects on optimization in telecommunications networks and transportation systems. His main research interests include: models and algorithms for combinatorial optimization problems, with applications in particular to telecommunications, transportations, logistics, and electronic circuit design. He has published more than 30 articles on international scietific journals.     

Channel assignment algorithms satisfying cochannel and adjacent channel reuse constraints in cellular mobile networks

Improved channel assignment algorithms for cellular networks were designed by modeling the interference constraints in terms of a hypergraph. However, these algorithms only considered cochannel reuse constraints. Receiver filter responses impose restrictions on simultaneous adjacent channel usage in the same cell or in neighboring cells. We first present some heuristics for designing fixed channel assignment algorithms with a minimum number of channels satisfying both cochannel and adjacent channel reuse constraints. An asymptotically tight upper bound for the traffic carried by the system in the presence of arbitrary cochannel and adjacent channel use constraints was developed by Deora (1995). However, this bound is computationally intractable even for small systems like a regular hexagonal cellular system of 19 cells. We have obtained approximations to this bound using the optimal solutions for cochannel reuse constraints only and a further graph theoretic approach. Our approximations are computationally much more efficient and have turned out to track very closely the exact performance bounds in most cases of interest.     

CDMA蜂窝网频谱规划方案的比较分析

本文建议了CDMA蜂窝网频谱规划的两种方案,频率复用系数分别为K=4/3与K=3.文中以纯语音业务为例讨论了不同频谱规划之间的区别.仿真结果显示目前所普遍采用的K=4/3的频谱规划方案并非最佳选择,当小区之间移动终端分布不均匀时,K=3的频谱规划方案在小区容量方面优于K=4/3的规划方案.     

A neural network parallel algorithm for channel assignment problemsin cellular radio networks

The channel assignment problem involves not only assigning channels or frequencies to each radio cell. but also satisfying frequency constraints given by a compatibility matrix. The proposed parallel algorithm is based on an artificial neural network composed of nm processing elements for an n-cell-m-frequency problem. The algorithm runs not only on a sequential machine but also on a parallel machine with up to a maximum of nm processors. The algorithm was tested by solving eight benchmark problems where the total number of frequencies varied from 100 to 533. The algorithm found the solutions in nearly constant time with nm processors. The simulation results showed that the algorithm found better solutions than the existing algorithm in one out of eight problems     

Location estimation and trajectory prediction for cellular networks with mobile base stations

This paper provides mobility estimation and prediction for a variant of the GSM network that resembles an ad hoc wireless mobile network in which base stations and users are both mobile. We propose using a Robust Extended Kalman Filter (REKF) to derive an estimate of the mobile user's next mobile base station from the user's location, heading, and altitude, to improve connection reliability and bandwidth efficiency of the underlying system. Our analysis demonstrates that our algorithm can successfully track the mobile users with less system complexity, as it requires measurements from only one or two closest mobile base stations. Further, the technique is robust against system uncertainties caused by the inherent deterministic nature of the mobility model. Through simulation, we show the accuracy of our prediction algorithm and the simplicity of its implementation.     

An improved mechanism for multiple MBMS sessions assignment in B3G cellular networks

In Universal Mobile Telecommunication System (UMTS), the downlink capacity is limited by the base station transmission power. Therefore, power control plays an important role to minimize the transmitted power shared among unicast and multicast users within a cell. In Multimedia Broadcast/Multicast Service (MBMS), power control targets to the efficient utilization of radio and network resources. However, the expected high demand for such services stresses the need for an efficient scheme, capable of dynamically allocating radio resources to parallel MBMS sessions. This paper proposes a power control mechanism for efficient MBMS session assignment in next generation UMTS networks. The mechanism shares efficiently the available power resources of UMTS base stations to MBMS sessions running in the network. Furthermore, the mechanism is evaluated through several realistic scenarios and the results indicate the ability of the mechanism to utilize efficiently the radio resources and to ensure the service continuity when parallel MBMS services run in the network. Our approach is compared with current 3rd Generation Partnership Project (3GPP) approaches, such as these presented in TS 25.346 and in TR 25.922, in order to highlight the enhancements that it provides.