A simulated annealing based solution approach for the two-layered location registration and paging areas partitioning problem in cellular mobile networks

This paper presents a mathematical model and simulated annealing based solution approach for finding optimal location updates and paging area configuration for mobile communication networks. We use a two-layered zone-based location registration and paging scheme in which the costs of location updates and paging signaling traffic are reduced by introducing a two-step paging process. The location updates and paging procedures in a two-layered scheme are first described, and an approximation of the measure required for calculating the paging-related signaling volume is provided based on assumptions of cell shapes and mobile stations’ movement patterns. A simulated annealing (SA)-based solution method is devised along with a greedy heuristic, and computational experiments are conducted to illustrate the superiority of the proposed SA-based method over other solution methods.     

Some analytical results for congestion in subscriber line modules

In modern telephone exchanges, subscriber lines are usually connected to the so-called subscriber line modules. These modules serve both incoming and outgoing traffic. An important difference between these two types of calls lies in the fact that in the case of blocking due to all channels busy in the module, outgoing calls can be queued whereas incoming calls get busy signal and must be re-initiated in order to establish the required connection. The corresponding queueing model was discussed recently by Lederman, but only the model with losses has been studied analytically. In the present contribution, we study the model which takes into account subscriber retrials and investigate some of its properties such as existence of stationary regime, derive explicit formulas for the system characteristics, limit theorems for systems under high repetition intensity of blocked calls and limit theorems for systems under heavy traffic.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

A New Method,the Fusion Fission,for the Relaxed <Emphasis Type="Italic">k</Emphasis>-way Graph Partitioning Problem,and Comparisons with Some Multilevel Algorithms

In this paper a new graph partitioning problem is introduced, the relaxed k-way graph partitioning problem. It is close to the k-way, also called multi-way, graph partitioning problem, but with relaxed imbalance constraints. This problem arises in the air traffic control area. A new graph partitioning method is presented, the Fusion Fission, which can be used to resolve the relaxed k-way graph partitioning problem. The Fusion Fission method is compared to classical Multilevel packages and with a Simulated Annealing algorithm. The Fusion Fission algorithm and the Simulated Annealing algorithm, both require a longer computation time than the Multilevel algorithms, but they also find better partitions. However, the Fusion Fission algorithm partitions the graph with a smaller imbalance and a smaller cut than Simulated Annealing does.     

不确定条件下的乡村中小学布局优化

学校的合理规划布局是实现教育资源优化配置、提高办学效益和推动教育均衡发展的重要途径。已有许多学者研究了学校的布局问题,但基本上都忽略了交通网络条件以及不确定因素对学校布局的影响。本研究将在前人研究基础上,重点考虑交通网络对乡村中小学选址的影响,并假设旅行时间具有不确定性,从而以最小化学生旅行成本、学校建设、道路修建和道路升级成本为目标,构建不确定条件下的设施区位设计模型。在算法求解方面提出混合模拟退火算法,用于确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况。最后,将提出的模型和算法应用到实际案例中。     

Mobile WiMAX MAC and PHY layer optimization for IPTV

WiMAX (Worldwide Interoperability for Microwave Access) embodies the IEEE 802.16 family of standards that provision wireless broadband access. With the IEEE 802.16e?2005 mobility amendment, WiMAX promises to address the ever-increasing demand for mobile high speed wireless data in fourth-generation (4G) networks. WiMAX market studies continue to project increased subscriber growth rates and planned carrier trials worldwide. Coupled with these increasing growth rates and higher WiMAX throughput rates, bandwidth intensive video on demand (VoD), Internet Protocol TV (IPTV), and mobile TV services are emerging in the forefront of the mobile arena.In this paper, we explore and derive optimum system level WiMAX parameters by quantifying network performance using such video-rich services. The video traffic will sufficiently load and stress the network to exploit the potential bandwidth, delay, and mobility limitations. We use the OPNET Modeler to engineer simulation sequences and explore the impact of channel bandwidth, time division duplex (TDD) frame size, advanced antenna systems support, and retransmission schemes using four objective performance metrics while streaming a feature-length movie to a Mobile WiMAX subscriber. The objective of this paper is to provide greater insight into Mobile WiMAX system performance using emerging, load intensive and delay sensitive media streaming services.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

A discrete location model with fuzzy accessibility measures

In crisply defined discrete location problems, a number of facilities are to be located at specific points within an area, according to precisely quantified criteria. However in many location problems, especially those associated with social policies, non-crisply defined criteria are used such as, how ‘near’ or ‘accessible’ a facility is, or how ‘important’ certain issues are, etc. In these cases a fuzzy sets approach is more appropriate.This paper presents an application of the set partitioning (set covering with equality constraints) type of integer programming formulation to a discrete location problem with fuzzy accessibility criteria. The solution method suggested uses the symmetry of the objectives and the constraints introduced by Bellman and Zadeh.     

Receiver set partitioning and sequencing for multicasting traffic in a WDM lightwave single-hop network

This paper considers a receiver set partitioning and sequencing problem in a wavelength division multiplexing single-hop lightwave network for multicasting traffic. The problem is analysed in the approach of uncapacitated single batch-processing machine scheduling. In the analysis, several solution properties are characterized with respect to a mean flow time measure, based upon which two heuristic algorithms are developed, along with a dynamic programming algorithm. Several numerical experiments show that the heuristic algorithms generate good schedules. The problem is extended to consider two measures simultaneously including the mean flow time and the number of transmissions, for which the proposed algorithms also perform well.     

Optimal number of bypasses: minimizing cost of calls to wireless phones under Calling Party Pays

In telecommunications, Calling Party Pays is a billing formula that prescribes that the person who makes the call pays its full cost. Under CPP land-line to wireless phone calls have a high cost for many organizations. They can reduce this cost at the expense of installing wireless bypasses to replace land-line to wireless traffic with wireless-to-wireless traffic, when the latter is cheaper than the former. Thus, for a given time-horizon, the cost of the project is a trade-off between traffic to-wireless and the number of bypasses. We present a method to determine the number of bypasses that minimizes the expected cost of the project. This method takes into account hourly varying traffic intensity. Our method takes advantage of parallels with inventory models for rental items. Examples illustrate the economic value of our approach.     

Benders decomposition for variational inequalities

The partitioning technique of J.F. Benders, which was generalized to nonlinear programming by Geoffrion, is further generalized to linearly constrained variational inequality problems. The conditions under which such a generalization is possible and appropriate are examined.An important area of application is the asymmetric traffic assignment problem for which the decomposition assumes a simple and effective form. A computational example demonstrates the algorithm.This research was supported in part by NFS grants ECE-8420830 and ECS-8516365.     

Applications of the urban traffic control strategy TUC

Despite the long-lasting research and developments in the field of urban traffic control systems, the continuously increasing mobility requirements urge for solutions that will release urban areas from the serious congestion problems and their consequences. From the control point of view, this may be translated into the employment of traffic-responsive systems that respond automatically to the prevailing traffic conditions. This is the aim of the signal control strategy TUC, whose basic philosophy, design methodology, characteristics and application results under both simulated and field conditions are presented in this paper. Based on a store-and-forward type of mathematical modelling and using well-known methodological tools from Automatic Control Theory, the TUC strategy addresses in a simple but efficient way, as demonstrated from the applications so far, the problem of co-ordinated, traffic-responsive signal control in large-scale urban networks.     

Application of renewal theory to call handover counting and dynamic location management in cellular mobile networks

Mobility management in wireless cellular networks is one of the main issues for resource optimization. It is aimed to keep track of Mobile Stations (MSs) in the different Location Areas (LAs) or Registration Areas (RAs) for an efficient call delivery. The optimization issues of these location strategies look for a minimization of the generated signaling traffic. We describe the three basic strategies for location management: distance-based, time-based and movement-based, and their corresponding optimization cost. We emphasize that counting the number of wireless cell crossings or handovers occurring in the call duration time or during inter-call times is a fundamental issue for mobility management analysis. We present the main approaches in the literature to deal with these problems with a special emphasis to renewal theory to model the probabilistic structure of these optimization problems.     

A tiling and routing heuristic for the screening of cytological samples

In the screening of cytological samples, a slide is examined using a microscope. Since the area of the specimen is very large compared with the area of a microscope field of view (FOV), a large number of FOVs is needed to cover the entire specimen area. A heuristic reducing the number of FOVs has been developed to aid in screening these specimens on the automated microscopy workstation. A smear slide is prescreened on a computer-aided optimal microscope system and locations of diagnostically significant material are stored. The heuristic computes a set of FOVs that covers this material and a route between them. As the problem is of large scale and must be solved repeatedly in real time any heuristic must be very fast. Our heuristic solves a set partitioning problem, followed by a traveling salesman problem. It produces a good solution within a very short computing time.     

Linear and quadratic programming approaches for the general graph partitioning problem

The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.     

Novel hybrid heuristics for an extension of the dynamic relay deployment problem over disaster areas

In this paper, we propose a novel autonomous intelligent tool for the optimum design of a wireless relayed communication network deployed over disaster areas. The so-called dynamic relay deployment problem consists of finding the optimum number of deployed relays and their location aimed at simultaneously maximizing the overall number of mobile nodes covered and minimizing the cost of the deployment. In this paper, we extend the problem by considering diverse relay models characterized by different coverage radii and associated costs. To efficiently tackle this problem we derive a novel hybrid scheme comprising: (1) a Harmony Search (HS)-based global search procedure and (2) a modified version of the well-known K-means clustering algorithm as a local search technique. Single- and bi-objective formulations of the algorithm are proposed for emergency and strategic operational planning, respectively. Monte Carlo simulations are run over a emulated scenario based on real statistical data from the Castilla La Mancha region (center of Spain) to show that, in comparison with a standard implementation of the K-means algorithm followed by a exhaustive search procedure over all relay-model combinations, the proposed scheme renders on average better coverage levels and reduced costs providing, at the same time, an intelligent tool capable of simultaneously determining the number and models of the relays to be deployed.     

Optimal Network Design for Wireless Local Area Network

Network design for wireless local area networks is an important issue in the deployment of these networks. Research activities are presently being undertaken in two major areas: determining the location of base stations (BSs) and assigning the frequency channels for these stations. Our BS location problem selects a set of BSs to provide the best demand area coverage and maximize the signal level and physical area attendance priority. Adequate channel assignment reduces signal interference and improves network throughput. This paper reports a real world experiment where we applied the concepts of two classical outdoor problems namely the optimal BS location problem and the fixed channel assignment problem to build a WLAN into an indoor environment. We propose a mathematical model that we solve by a commercial software and report the computational results.     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.