عملکرد و هزینه تجارت کردن در پیکر بندی دوباره منطقه پیگیری: روش پارتو بهینه سازی

Tracking Area (TA) design is one of the key tasks in location management of Long Term Evolution (LTE) networks. TA enables to trace and page User Equipments (UEs). As UEs distribution and mobility patterns change over time, TA design may have to undergo revisions. For revising the TA design, the cells to be reconfigured typically have to be temporary torn down. Consequently, this will result in service interruption and “cost”. There is always a trade-off between the performance in terms of the overall signaling overhead of the network and the reconfiguration cost. In this paper, we model this trade-off as a bi-objective optimization problem to which the solutions are characterized by Pareto-optimality. Solving the problem delivers a host of potential trade-offs among which the selection can be based on the preferences of a decision maker. An integer programming model has been developed and applied to the problem. Solving the integer programming model for various cost budget levels leads to an exact scheme for Pareto-optimization. In order to deliver Pareto-optimal solutions for large networks in one single run, a Genetic Algorithm (GA) embedded with Local Search (LS) is applied. Unlike many commonly adopted approaches in multi-objective optimization, our algorithm does not consider any weighted combination of the objectives. Comprehensive numerical results are presented in this study, using large-scale realistic or real-life network scenarios. The experiments demonstrate the effectiveness of the proposed approach.

Tracing users cost-efficiently is one of the major challenges in mobility management of cellular networks [5]. Tracking Area (TA) is a logical grouping of cells in Long Term Evolution (LTE) networks [1] and [2]. TA manages and represents the location of User Equipments (UEs). Similar grouping concept is called Location Area (LA) in circuit-switched domain and Routing Area (RA) in packet-switched domain in GSM, GPRS and UMTS. Note that, although the optimization framework developed in this paper generalizes to other networks, we focus on LTE due to its emphasis on automatic network reconfiguration [1] and [2]. The concept of reconfiguration means that the management system has the intelligence of adapting network configurations to changes and trends in UE distribution and demand. In configuring TAs, a key consideration is to minimize the total amount of signaling overhead. The overall signaling overhead of a network consists of two separate terms: update overhead and paging overhead. In the standard strategy of TA update and UE paging, the Mobility Management Entity (MME) records the TA in which the UE is registered. When UE moves to a new TA, there will be an update signaling overhead. The location information that the MME has about the idle UE is the registered TA. The paging signaling overhead is incurred by the event that a UE is called. One paging strategy is to command all cells in the TA to broadcast messages to page the UE. (Alternatives have been proposed, where paging is first performed in a subset of the cells in the TA.) Having TAs of very small size (e.g., one cell per TA) virtually eliminates paging, but causes excessive registration, whereas TAs of too large size give the opposite effect. Thus the natural objective in TA planning is to reach an optimal balance between update and paging signaling. There are extensive studies on optimization methods to deal with this objective [4], [6], [7], [8], [9], [12], [31] and [38]. Consider a TA design that is optimized for a network in the planning phase. As UE distribution and mobility patterns change over time, the optimized TA configuration will no longer perform satisfactorily. To reduce the signaling overhead, TA reconfiguration becomes necessary. In this case, it is not feasible to make a new TA design from scratch, because TA reconfiguration has to use the current design as the starting point. Reconfiguring TA, such as moving a cell from its home TA to another, usually requires to restart the cell and consequently results in service interruption. Therefore, there is a trade-off between approaching minimum signaling overhead and the cost resulted from reconfiguration. In this study, we propose a bi-objective optimization framework for the TA reconfiguration problem. Unlike mono-objective optimization problems which have a unique optimal value, in bi-objective problems the solution set is formed by Pareto-optimal (non-dominated) points. We develop an integer programming model to optimize the overhead by reconfiguration subject to a cost budget constraint. Applying the model to various budget levels leads to a set of Pareto-optimal solutions. For an exact assessment of the Pareto-optimal frontier, the integer model should be run many times. Solving the integer programming model is very time-consuming and sometimes infeasible for large networks. To deal with large-scale networks, we propose a Genetic Algorithm (GA) embedded with Local Search (LS) to search for Pareto-optimal solutions in one single run. In the GA approach, we use the concept of dominance in the fitness evaluation, to the contrary of approaches that use a scalarization function or treat the various objectives separately. In our GA algorithm, the amount of dominance is referred to as the Preference Value (PV), which explicitly evaluates the solution in terms of Pareto-optimality. We demonstrate the performance of the proposed integer model and the GA algorithm via experiments using three large-scale realistic or real-life network scenarios. For the first two scenarios we were able to compare the results from the GA algorithm with the ones computed from the integer model. The last network was only solved by the GA algorithm since it was too large and not feasible to be solved with the integer programming model. The results demonstrate the ability of the approaches to deliver various Pareto-optimal solutions and thus giving the operator the opportunity of selecting a proper trade-off between the two objectives. In real systems, how often TAs are reconfigured varies by operators’ policies. Typically, TAs need to be revised when there are indications of signaling congestion, or new infrastructure is deployed (e.g., a major expansion of sites). Our optimization framework is intended for adapting TAs to long-term trends, rather than targeting short-term changes with a regularly repeated pattern, e.g., daytime and night-time user distributions. Thus applying the framework is not an on-line process with strict constraint on computing time. Yet it is not desirable to use an exponential-time algorithm, for which the computational effort (both in time and memory requirement) cannot be predicted at all. Therefore the computational efficiency is of significance even if not very crucial. Moreover, it is vital that the optimization algorithm is effective in exploring the Pareto frontier. The GA algorithm is designed with these aspects in mind. Another aspect is the impact of the time period of reconfiguration on performance. Clearly, the optimization results, in terms of the Pareto-optimal frontier, vary by the time point at which reconfiguration is considered. Frequent reconfigurations can keep the TA design close to optimal in signaling overhead, but the reconfigurations may due to short-term changes instead of long-term trends, resulting in oscillating TA patterns. In general, it is hard to determine the “right time” of reconfiguration, without knowing the performance of the current design in relation to optimality. The bi-objective optimization approach targets exploring all possible solutions trading signaling overhead against reconfiguration cost. Hence an operator can apply the approach frequently to determine the time for reconfiguration. The remainder of the paper is constructed as follows. In Section 2, we review some works that are relevant to our study. In Section 3, the system model is discussed in detail. In Section 4, the integer programming model is presented. In Section 5, we explain our approach for evaluating Pareto-optimal solutions. Section 6 is devoted to the Genetic Algorithm and Local Search. Section 7 gives a method to improve the efficiency of the algorithm. In Section 8, we conduct performance evaluation and present the numerical results. Section 9 concludes the paper.

A bi-objective optimization framework has been formulated to approach Pareto-optimal solutions for the trade-off between the signaling overhead and the TA reconfiguration cost. We have formulated an integer programming model and proposed a dominance-based GA algorithm to solve the problem. The integer programming model provides the exact Pareto-optimal solutions and the GA algorithm is simple in implementation and efficient in performance for large-scale networks. The experiments for several networks demonstrate that the characteristic of the Pareto-optimal frontier differs by network, and that the proposed GA algorithm provides close-to-optimal solutions for large-scale networks. The mathematical optimization framework and the solution algorithm can potentially be implemented in the MME to enhance the functionality of mobility management in LTE networks. Using statistics of cell load and handover, the optimization procedure is run as an automated process to continuously estimate the performance of the current TA configuration, and discover long-term improvements in signaling overhead along with the corresponding trade-off in reconfiguration cost. On top of the optimization process, a module analyzing the optimization results and generating candidate reconfiguration plans is needed. The module implements the operator’s preference and policies in TA reconfiguration, based on, for example, thresholds and criteria on the frequency and amount of signaling congestion, as well as the performance of the reconfiguration options. Design and implementation of the module form an interesting line of further research.