مقایسه های متا هیوریستیک متفاوت برای حل مشکل برنامه ریزی جهانی شبکه های سیستم جهانی ارتباطات راه دور تلفن همراه

In this paper, we investigate and compare, through extensive simulation, the use of three meta-heuristic algorithms in order to find “good” feasible solutions for the global topology planning problem of universal mobile telecommunications system (UMTS) networks. The latter has been shown to be NP-hard as it is composed of three different subproblems (each one being NP-hard): the cell planning subproblem, the access network planning subproblem and the core network planning subproblem. As a result, we concentrate our effort on the development of approximate algorithms based on tabu search, genetic algorithm and simulated annealing. Numerical results show that these three algorithms perform relatively well. The tabu search algorithm returns the best solutions (on average, within 1.04% of the optimal solution) while the genetic algorithm seems to be slightly faster than the other two. Finally, simulated annealing finds the worst solutions (on average, within 4.91% of the optimal solution) and takes much more time than the other two algorithms.

Nowadays, the universal mobile telecommunications system (UMTS) takes a very important role in the wireless communication market. Serious network planning helps network operators to plan/build their network according to the required performance with long term profitability. The primary task of the overall network planning process is the topology planning, which describes the network infrastructure and the required initial investment. From the network infrastructure point of view, the UMTS network is composed of two parts: the radio access network (RAN), also called the universal terrestrial radio access network (UTRAN), and the core network (CN). The radio access network, which is based on the wideband code division multiple access (W-CDMA) technology, is composed of node Bs and radio network controllers (RNCs). The node B, formerly known as base station in 2G networks, houses the radio transceiver and provides the interface between the radio link and the network itself. The RNC, previously known as base station controller in 2G networks, provides connectivity between node Bs and the core network. It is also responsible for the call and mobility management and takes the full charge of radio resource management without involving the core network. The core network includes two domains: a circuit-switched (CS) domain and a packet-switched (PS) domain. On one side, the CS domain deals with real-time traffic, like voice, and provides connectivity to the public switched telephone network (PSTN). On the other side, the PS domain handles other types of traffic such as time non-sensitive services and ultimately provides a connection to the public IP network. The CN definitions are based on the 2G/2.5G network specifications. In fact, the CN makes use of the existing general packet radio system (GPRS) infrastructure, such as the mobile switching controller (MSC), the gateway MSC (GMSC), the home location register (HLR) and the visitor location register (VLR) for the CS side and the serving GPRS support node (SGSN) and the gateway GPRS support node (GGSN) for the PS side. A typical UMTS (release 99) network infrastructure is shown in Fig. 1

Since the global planning problem of UMTS networks is NP-hard, approximate algorithms are required to find “good” solutions within a reasonable amount of time. In this paper, we proposed two new meta-heuristics to solve this problem: genetic algorithm and simulated annealing. The proposed algorithms deal simultaneously with the cell, the access network and the core network planning subproblems. We also performed a comparative analysis in order to find the best algorithm to plan UMTS networks in the uplink direction. From the results, we can clearly say that the three algorithms (GA, SA and TS) provide relatively good results. In fact, the average gap for the three algorithms is below 5%. Tabu search provide the best solutions with an average gap of 1.04%. The genetic algorithm is the fastest one with an average execution time 296 s. Finally, the simulated annealing algorithm is the worst algorithm in terms of solutions found (average gap of 4.91%) and execution time (average of 3,614 s per problem). In this paper, only the uplink direction was considered. As a result, it might be interesting to consider the downlink direction or even both directions simultaneously since mobile users are using more and more data services. We are also planning to look at newer generation of cellular networks such as long term evolution (LTE) which is an evolved version of UMTS networks. Finally, we are also looking at ways to reduce the complexity of the problem such that larger instances of the problem could be solved. One interesting option could be to reduce the size of the problem before actually solving it.