(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
A Novel Model for Optimized GSM Network Design
Alexei Barbosa de Aguiar, Plácido Rogério Pinheiro, Álvaro de Menezes S. Neto, Ruddy P. P. Cunha, Rebecca F. Pinheiro Graduate Program in Applied Informatics, University of Fortaleza Av. Washington Soares 1321, Sala J-30, Fortaleza, CE, Brazil, 60811-905 [email protected], [email protected], [email protected], [email protected], [email protected]
Abstract – GSM networks are very expensive. The network design process requires too many decisions in a combinatorial explosion. For this reason, the larger is the network, the harder is to achieve a totally human based optimized solution. The BSC (Base Station Control) nodes have to be geographically well allocated to reduce the transmission costs. There are decisions of association between BTS and BSC those impacts in the correct dimensioning of these BSC. The choice of BSC quantity and model capable of carrying the cumulated traffic of its affiliated BTS nodes in turn reflects on the total cost. In addition, the last component of the total cost is due to transmission for linking BSC nodes to MSC. These trunks have a major significance since the number of required E1 lines is larger than BTS to BSC link. This work presents an integer programming model and a computational tool for designing GSM (Global System for Mobile Communications) networks, regarding BSS (Base Station Subsystem) with optimized cost. Key words: GSM mobile network design, cellular telephony, Integer Programming (IP), Operations Research.
The Term Paper on Analysis and Design of Software Architecture
Outline 1 2 3 4 5 6 7 8 Development Process Requirements Quality Attributes Runtime QA Non-runtime QA Requirements Analysis: Example Architectural Analysis & Design Architectural Views Denis Helic (KMI, TU Graz) SA Analysis and Design Oct 19, 2011 2 / 78 Development Process Methodology Different software development processes have software architecture as a part of the process Rational unified ...
I. INTRODUCTION
packet data transmission services instead of handling voice calls. Many of its mechanics are identical or similar to its voice counterpart and deals with HLR as well. Hierarchically below each MSC we have BSC (Base Station Controller) nodes. They are not present in IS-136 (TDMA) networks. BSC reduces the cost of the network. One of the reason is that it concentrates the processing intelligence of BTS (Base Transceiver Stations) nodes, which are the most numerous and spread equipments. Other impacting factor is that, although BSC depends on MSC for many activities, it is the first layer telephony switch, geographically concentrating traffic. This means that the trunks that carries the traffic from BSC to MSC are statistically dimensioned based on Erlang’s traffic theory instead of one-by-one channel fashion. The BTS radiates the RF (Radio Frequency) signal to the mobile phones and receive its signal back. Antennas in the top of towers or buildings radiate this RF, creating coverage areas called cells. The geographical allocation of BTS is guided by RF coverage and traffic demand.
The GSM mobile networks have a very sophisticated architecture composed by different kind of equipments [14]. One of the most important of these equipments, located at the core of the network, is MSC (Mobile Switching Center).
MSC has many vital duties like register and unregister MS (Mobile Station), analyze call destinations, route calls, handle signaling, locate MS through paging, control handover, compress and crypt voice, etc. Indeed, it is one of the most expensive components of the network. The HLR (Home Location Register) works as a subscriber database, storing information concerning its state, location, parameters and service data. It is constantly queried and updated by MSC. The SGSN (Serving GPRS Support Node) are analogous to MSC but are dedicated to the
Fig.1. Mobile Network Design The focus here will be concentrated in the BSS (Base Station Subsystem) which faces the radio resources towards MS. BSS is the group of equipments and softwares that integrates BSC
The Report on Networks
Unit I Network architecture – layers – Physical links – Channel access on links – Hybrid multiple access techniques - Issues in the data link layer - Framing – Error correction and detection – Link-level Flow Control. Network Architecture Network architecture that guides the design and implementation of networks. Two of the most widely referenced architectures—the OSI architecture and the Internet ...
ISSN 1947 5500
(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
nodes, BTS nodes and MSC. transmission network plays an important role on linking them all. The network design usually starts at the cell planning department. The coverage area required given to cell planning engineer team and the traffic is estimated by geographic regions. This region’s traffic density variation can be very wide. When coverage is the goal, RF engineers look for sites with high altitudes and free of obstacles to reach larger distances. On the other hand, when the goal is traffic, hotspots are distributed with full equipped BTS nodes. Its radio channel’s power is configured lower and the RF irradiation is directed to the “near” ground with a higher antenna tilt angle. In urban areas the BTS proximity is limited by interference since there is a limited number of RF channels and they are repeated on and on along the coverage area. The BTS sites are allocated in a triangular grid pattern, where it is possible. This allocation is due to the coverage pattern of its tree groups of antennas, disposed with 120º angles between then. Once all BTS placements are determined with its correspondent channel dimensioning, it is possible to plan how many BSC nodes are need, witch capacity each one may have and its geographical allocation.
All this factors are highly related to the choices of which BTS nodes are linked to which BSC nodes. The links between BTS and BSC are E1 lines that hold voice channels slots. They are configured deterministically in a one-to-one basis, regarding the radio channels slots of the BTS. It is called Abis interface. On the other hand, trunks that link BSC to MSC are E1 lines dimensioned by the total traffic from all of its BTS. It is called A interface. These trunks are similar to trunks between two MSC or other conventional telephony switches. The voice channels in these trunks are seized statistically by demand and the total number of busy channels varies during the day. All calls must pass through the MSC, even when both subscribers are very close, in the same BTS and BSC area. The Erlang B formula calculates the blocking probability (or congestion, or Grade of Service GoS) to a given number of resources (voice channel, normally) and offered traffic. Each one of the three variables in this formula can be calculated from the two others depending on the context. The percentile of calls that are lost can be calculated for a given
The Term Paper on High Capacity Networks
High-capacity solutions are about building high-capacity networks in the most economical way, and therefore, GSM radio network capacity solutions are becoming increasingly important. Radio network capacity solutions can be divided into three categories: cell capacity, network capacity, and channel capacity. The author discusses various solutions for improving radio network capacity in each of ...
number of voice channels available in some equipment and the measured traffic. To solve a congestion scenario this formula provides the number of channels that would be necessary to flow this traffic for a maximum tolerable GoS (2%, for instance).
Other possibility is to calculate how much traffic can be carried with a given number of channels and the desired GoS. The Erlang B formula eq. (1) is shown below:
an eb = n! i n a Σ i=0 i!
(1)
eb is the probability of blocking, also known as
GoS, n is the number of resources (voice channels in this case) and a is the amount of traffic offered in Erlangs. Besides channel resources, some BSC have a deterministic way of allocation for other kind of resources. When a new radio channel is installed in a BTS, some required resources (processor and memory, for instance) are associated with this new radio channel in a fixed way. These resources are compromised with the radio channel, even though it is idle. Thus, this kind of BSC has a fixed maximal capacity, for instance, 4096 radio voice channels (slots).
Some more modern BSC uses a pool of resources that are associated to radio voice channels on demand, when a call is made. This feature increases the BSC capacity. Using this type of BSC, its maximum capacity cannot be determined by its number of radio channels, but by its traffic in Erlangs. For instance, the 4096 radio voice channel BSC could be equivalent to a 4058 Erlangs (at 2% GoS) BSC model, with virtually unlimited number of radio voice channels, depending on their traffic demand. So the A interface from BTS to BSC is made of deterministic channels in E1 lines. These lines waste transmission resources. Moreover, the A interface from BSC to MSC is made of statistical channels in E1 lines. These lines are more efficient. It was said that BSC reduces transmission costs, but they themselves represents network design costs. It is a design tradeoff. The more BSC we distribute along the coverage area, the lower are transmission costs, since the distances between BTS to BSC decreases. On the other hand, the BSC has its acquisition cost. The balance between these two costs is reached with
The Essay on Cost of equity capital
Introduction The rate of return that is required is employed in evaluating equity and is the least percentage in a year that is gained by investments of a company through the investors. The cost of equity is the rate of return on investments that is required by the shareholders of a company. The paper will discuss the three models which are the dividend growth, the CAPM and the arbitrage pricing ...
ISSN 1947 5500
(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
the optimal geographical allocation of the BSC, associated with its correct choice of model that has its respective capacity and cost. A typical GSM network has hundred or thousand BTS and tens or hundreds of BSC. The human capacity of designing efficient networks with such magnitudes is very limited and the network costs are high. The use of computational tools can reduce these costs radically. That is what is proposed here.
II. THE INTEGER PROGRAMMING MODEL
B. Restrictions In eq. (2), each BTS must be connected to one and only one BSC:
xij = 1,
j B
i
T
(2)
In eq. (3), the y lc dimensioning is made. It allows all traffic from BTS assigned to one BSC to flow over its links:
This is an Integer Programming model [8] capable of minimizing the total network cost and providing the design solution to achieve this minimal cost.
xil ai
i T c C
f c ylc , l
B
(3)
T = t1 , t 2 , t 3 ,
, t m BTS nodes; , wo BSC models;
In eq. (4), the BSC dimensioning is made accordingly to the given models and the total traffic demand.
B = b1 ,b2 ,b3 , ,bn BSC nodes;
W = w1 , w2 , w3 ,
i T
xij ai
k W
ek z jk , j
i T
l l B B
B
(4)
C = c0 , c1 , c2 ,…, c p Link capacities; x ij Decision variables for link allocation
between BTS node i and BSC node j; Decision variables for choosing the capacity c of E1 (2 Mbps) lines between BSC l and MSC;
The Essay on Database Model Hierarchical Structure Network
A Comparison of the Hierarchical, Network and Relational, Database Models Database models continue to evolve as the information management needs of organizations become more complex. From flat files to relational databases, the growing demands on data integrity, reliability and performance of database management systems (DBMS), has shaped the design of databases and their underlying models. In ...
xij
ylc z lw
0,1 ,
0,1 , 0,1 ,
j
c
B
C
(5) (6) (7)
y lc
k W
z lw
w choice.
Decision variables for BSC l model
III. MODEL APPLICATION
Link cost between BTS i and BSC j nodes in an analysis time period;
ct ij
This model has some issues applications that must be observed.
in
real
cm lc Link cost of capacity c between BSC l nodes and MSC in an analysis time period;
cb w BSC model w acquisition cost, considering an analysis time period;
ai
fc
BTS i traffic demand in Erlangs; Link capacity c in Erlangs; BSC model w traffic capacity in
ew
Erlangs.
A. Objective Function The objective function eq. (1) minimizes total cost of links between BTS and BSC, plus cost of E1 lines between BSC nodes and MSC, plus total cost of BSC’s acquisition.
minimize
i T j B
The set of BTS nodes T is known previously because RF engineers make its design as the first step. Its geographical location is determined by coverage and traffic requirements. Its traffic demand can be known previously by measuring other mobile network (old one that is being replaced, or by other overlaid technology such as TDMA (Time Division Multiple Access) or CDMA (Code Division Multiple Access).
When such data source is not available, this traffic demands can be estimated by average subscriber traffic and number of subscribers forecast based on population and marketing studies. The set of BSC nodes B can be generated based on all feasible sites possibilities. The sites that will have a BTS are good candidates, since its space will be already available by rental or buy. Other company buildings can be added to this set. The set B represents all possibilities, and not necessarily the actual BSC allocations. The more options this set B has, the better the allocation of the needed BSC nodes tends to be.
ct ij x ij +
l B c C
cm lc y lc +
d Bk W
cb k z dk (1)
ISSN 1947 5500
(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
The set W contains the available models of BSC. Normally a BSC manufacturer offers different choices of models. Each one has its capacity in Erlang (as it was modeled here) and price. The set C is a table of traffic capacities for an integer quantity of E1 lines. Each E1 line has a number of timeslots allocated for voice from the 31 available. Other timeslots are used for signaling and data links. Thus, the first E1 line may have a different number of voice timeslots than the second E1 line, and so on. Each voice timeslot carries 4 compressed voice channels, so called sub-timeslots. The elements of the set C are calculated by the reverse Erlang B formula, taking the number of voice channels and the defined GoS as incoming data and the traffic as outgoing data. The first element of set C is 0 E1 lines, which lead to 0 Erlang. The second element of set C is 1 E1 line and has a calculated traffic for 4 times the number of timeslots allocated for voice in this E1 line. This is because each timeslot has 4 sub-timeslots. The third element of set C is 2 E1 lines and has the traffic calculated for 4 times the number of timeslots allocated for voice in all 2 E1 lines, and so on. The size of the set C is determined by the maximal capacity of the larger BSC model. The link costs ct and cb in a given period of analysis must be determined by the transmission network ownership and/or contract. If the transmission network belongs to the own mobile company, its cost can be determined by a set of distance ranges or as a constant times the distance, plus an equipment fixed cost. If the mobile company contracts transmission lines from other company, the costs must be calculated based on specific contractual rules. For instance, discounts based on quantity can be applied. This integer programming model can be adapted to work with BSC that has maximum number of radio channels capacity, instead of maximum traffic capacity as presented.
The Essay on Henry Ford, Inventor of the Model T and Assembly Line.
March 29, 1999 U.S. History Henry Ford, Inventor of the Model T and Assembly Line. The Ford motor company is one of the most famous American car manufacturers in the world. The man who started it all was Henry Ford. Henry Ford was born in Springwells township Michigan on July 30, 1863. At a young age he showed mechanical and inventive skills, which he enhanced by getting a job as a machinist's ...
IV. COMPUTATIONAL RESULTS
minutes to solve. The data was generated using the following assumptions: The transmission cost was calculated multiplying the link distance by a constant. Local market cost approximations were used. The cost of n E1 line in the same link is assumed to be n times the cost of each E1 line. The BTS and MSC site geographical locations where generated randomly. For each BTS site, a BSC site candidate was generated. The traffic of each BTS was generated randomly from 0 to 80 Erlangs that is the approximated value that a BTS can handle with 1 E1 line. The set C was generated with 41 values, from 0 E1 lines until 40 E1 lines. For each capacity, the corresponding traffic was calculated accordingly to the exposed in the model application session (3).
Three BSC models where used in these simulations: Small, medium and large with 512, 2048 and 4096 Erlangs of capacity respectively. Each one had an acquisition cost compatible to the local market reality. OPL integrated modeling environment and Cplex 10.0 solver library [9] from Ilog Inc. were used in the simulations. OPL ran in a 64 bits Intel Core 2 Quad processor with 2.4 GHz clock and 4 GB of RAM memory. Despite the fact that 50 sites is a very small problem instance comparing to hundreds or even thousand sites of the real mobile networks, the simulations shown that this model works properly for the desirable purpose. Varying the costs, more or less BSC were allocated. Each BSC model was correctly chosen accordingly to the total traffic demanded by all BTS allocated to this BSC. The distances were minimized indirectly because of the linear cost by kilometer. The trunk between BSC and MSC was dimensioned to carry the total traffic demand by BSC, and its distance to MSC was effectively considered, since the amount of E1 lines was greater than one. The 20 problem instances were created and solved for each number of BTS sites varying from 5 until 50 with steps of 5. The data were generated randomly following the premises described in this section. The results are shown in table 1.
Simulations were made with many network sizes. The largest network size that could be solved in a reasonable time has about 50 sites. The different generated data caused big differences in the solving time. For instance: The smaller solving time for 50 sites with 3201 integer variables and 150 restrictions was 42.04 seconds, while other equivalent problem instances caused solver to spent more than 30
ISSN 1947 5500
(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
V. SCALABILITY ANALYSIS
Due to the wide range of random generated values, the problem instances have very high complexity variations. Thus, there were problem instances with 40 BTS that could not be solved within a reasonable time threshold. Some times the solver crashed because of memory lack. But, for the same reason, there are problems instances larger than 50 BTS that can be solved in a time interval even smaller than some particular instances of 40 BTS. The proposed model here is an Integer Programming one. The discrete nature of the variables requires an algorithm like Branchand-bound, Branch-and-cut or others. This sort of algorithms has an exponential complexity. This fact limits the larger instance size that can be handled. Actual networks often have hundred of BTS that is far beyond the range of this exact method. Aguiar and Pinheiro [13] used Lingo solver library and it was not able to handle problem instances larger than 40 BTS. The adoption of Cplex [9] expanded this boundary to 50 BTS, but it remains too small. A mean squares non-linear regression of the average times was made to determine the observed asymptotic complexity function. It is shown on eq. 8 and fig. 2.
BTS 5 10 15 20 25 30 35 40 45 50
Var. 96 241 436 681 976 1321 1716 2161 2656 3201
Const. 15 30 45 60 75 90 105 120 135 150
Density 9,72% 5,95% 4,43% 3,57% 3,01% 2,60% 2,29% 2,05% 1,86% 1,70%
Avg. Time 50,0 40,0 332,0 853,5 3561,5 19689,0 46287,5 600431,1 363032,5 752724,0
Std. Deviation 12,773 8,208 28,802 86,418 371,594 2872,227 4890,274 80263,118 44981,655 87873,235
Table 1 – Results After the model presentation, its application was shown explaining how to relate technical details of the real world with the model’s data generation. In computational results section, size and performance simulations were described. The scalability was analyzed lead to some conclusions. This model by itself can’t be used on real networks because of its limitation. Simulation with real networks can’t show the optimization potential because small networks can be well designed by human intuition and have smaller costs. Some methodology must be applied to extend the size of the problems to achieve hundred or thousand BTS sites. Thus, the optimization gain can be very effective.
y = 0,851e0,244x
(8)
The key to break this limitation and turn big network designs feasible is to use approximate approaches. Some methodologies like Lagrangean relaxation in Simple Subgradient, Bundle Methods and Space Dilatation Methods (Shor et al [6, 7]) can be used. Rigolon et al [3] show that the use of this tool in the first model extends the size of the largest mobile network to be designed. A framework that hybridizes exact methods and meta-heuristics has presented good results in expanding these boundaries in other classes of problems. Nepomuceno, Pinheiro and Coelho [11] used this framework to solve container loading problems. In the same problem category, Pinheiro and Coelho [12] presented a variation of the implementation to work with cutting problems.
VII. CONCLUSION
This work gave a solution to the BSS network design problem of mobile GSM carriers capturing its essence in a mathematical model. In introduction section some telecommunications background was given to help understanding the model. Then, the model was presented and explained.
ISSN 1947 5500
(IJCSIS) International Journal of Computer Science and Information Security Vol. 4, No. 1 & 2, 2009
Time 800,00 700,00 600,00 500,00 400,00 300,00 200,00 100,00 0,00
Average Time
y = 0,851e
0,244x
average time (s) Expon. average time(s)
0 5 10 15 20 25 30 35 40 45 50 55 Number of BTS
Fig. 2. Average time versus instance size
BIBLIOGRAPHICAL REFERENCES [1] Kubat, P e Smith, J. MacGregor. “A multi-period network design problem for cellular telecommunication systems”. European Journal of Operational Research, 134:439-456, 2001. [2] Kubat, P., Smith, J. MacGregor e Yum. C. “Design of celullar networks with diversity and capacity constraints”. IEEE Transactions on Reability, 49:165–175, 2000. [3] Rigolon, A. A., Pinheiro, P. R., Macambira, E. M., Ferreira, L. O. R. A. Approximate Algorithms in Mobile Telephone Network Projects. International Conference on Telecommunications and Networking, Bridgeport, Springer Verlag, 2005, v. XV, p. 234-347 [4] Rodrigues, S. I. M. Relaxação Lagrangeana e subgradientes com dilatação de espaço aplicados a um problema de grande porte. RJ, 1993. [6] Shor, N. Z.Utilization of the operation of space dilatation in the minimization of convex functions. Cybernetics, 1:7-15, 1970. [7] Shor, N. Z. Zhurbenko, N. G. A minimization method using the operation of extension of the space in the direction of the difference of two successive gradients. Cybernetics, 7(3):450-459, 1970. [8] Wolsey, L. A. Integer programming. John Wiley & Sons, 1998. [9] ILOG. ILOG CPLEX 10.0 User’s Manual, January 2006. [10] Shrage, L., Optimization Modeling with Lingo. Lindo Systems Inc., 1998. [11] N. V. Nepomuceno, P. R. Pinheiro, A. L. V. Coelho. Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms. Lecture Notes in Computer Science, v. 4446, p. 154-165, 2007. [12] N. V. Nepomuceno, P. R. Pinheiro, A. L. V. Coelho. A Hybrid Optimization Framework for Cutting and Packing Problems: Case Study on Constrained 2D Non-guillotine Cutting. In: C. Cotta and J. van Hemert. (Org.).
Recent Advances in Evolutionary Computation for Combinatorial Optimization. Berlin / Heidelberg: Springer-Verlag, 2008, v. 153, p. 87-99. [13] A. B. de Aguiar and P. R. Pinheiro. A Model for GSM Mobile Network Design, chapter Innovative Algorithms and Techniques in Automation, Industrial Eletronics and Telecomunications, pages 365-368. Springer Netherlands, Dordrecht, September 2007. [14] M. Mouly and M.-B. Pautet, GSM Protocol Architecture: Radio Sub – system Signaling , IEEE 41st Vehicular Technology Conference, 1991
ISSN 1947 5500
