ACM / Crossroads / Xrds11-4 / Introduction to Automatic Design of Wireless Networks

Introduction to Automatic Design of Wireless Networks

by K. E. Oliver

Introduction

Recent years have seen tremendous growth in the mobile communicationsindustry. Much of the success of second generation (2G) cellularnetworks was based on the uptake of Global System for MobileCommunications (GSM) as a worldwide standard, enabling voicecommunications to go wireless in many of the leading markets.However, GSM now struggles to accommodate the increased demand fordata services such as web browsing, picture messaging, videoconferencing, and audio and video streaming, because it was not designed for multimedia communication. Fortunately, in theearly 1990s, the International Telecommunications Union (ITU) hadthe foresight to define a new standard for third generation (3G)mobile networks. The resulting Wideband Code Division MultipleAccess (W-CDMA) standard has been designed from the outset toaccommodate a wide range of voice and data services. Currently, operators arecoming to terms with the new challenges involved in deployingUniversal Mobile Telecommunication System (UMTS) networks in acost effective manner. The global economic downturn, the largeservice fees paid for spectrum, and the increased competition fromWireless Local Area Network (WLAN) hot-spots mean that striking the right balance between financial constraints and quality of service is more important than ever.

The primary outlay for a network operator is in acquiring,deploying, renting, and maintaining base station sites. Along withthese financial constraints and increased health fears from thepublic, network operators have more motivation to reduce thenumber of sites deployed. Selecting good locations for basestation sites is a key factor in the design of cellular networks.This can be especially difficult in cities where buying propertyis subject to high prices and competition from other prospectivebuyers. The selected sites form the basis of a cellular networkthat will need to satisfy certain requirements at the time of thenetwork's launch and throughout the network's deployment. Suchrequirements include ensuring that mobile phone users always havesignal with a wide range of available services while reducing thecost of the network for the operator. This article demonstratesthe issues and challenges involved and shows how sophisticatedtechniques from computer science can be applied to the planning ofthird generation cellular networks.

Cellular Networks

Cellular networks are composed of:

• Mobile stations: used by the subscriber to communicate withthe cellular network and consist of the mobile equipment and thesubscriber identity module (SIM).
• Sites: places where base station equipment can be located.
• Base stations: located at a site and each base station hasan antenna.
• Antennas: can be omnidirectional, small directional, orlarge directional. An omnidirectional antenna sends a signal whichhas the same power in all directions (Figure 1), whereas a signal from adirectional antenna is focused in a certain direction (Figure 2). The power of an antenna can beincreased or decreased. Some elements associated with each antennaare: height, power, tilt (direction in the vertical plane), and azimuth (direction in the horizontal plane).

Figure 1: Horizontal radiation pattern for an omnidirectional antenna.

Figure 2: Horizontal radiation pattern for a directional antenna.

The type of antenna selected by the network planner will affectthe strength of the transmitted/received signal. When the signalis transmitted, it experiences a loss in power caused by the tiltof the antenna, shown in Figure 3, and the azimuth of theantenna, shown in Figure 4.

Figure 3: Vertical loss.

Figure 4: Horizontal loss.

When a base station transmits a signal to a mobile station, thecommunication link can be called the downlink. When amobile station transmits a signal to a base station, thecommunication link from a base station to a mobile station iscalled the uplink.

Understanding Propagation, Multiplexing, and Noise

Signal Propagation

The planning of cellular networks requires an understanding ofbasic concepts concerning the use of radio signals. The pathtraveled by the signal from one point to another through or alonga medium is called propagation. In cellular networks, a signal ispropagated from a base station and received at a mobile station,and vice versa. When a signal is transmitted through space itgets weaker with the distance traveled, resulting in the receivedpower being significantly less than the original transmittedpower. This is referred to as propagation loss.

When line of sight is lost between the sender and the receiver, thesituation becomes more complicated. Path loss or attenuation ofthe signal at the receiving mobile station or base station can beaffected by weather conditions such as heavy rain, which absorbsmuch of the transmitting antenna's radiated power.

The frequency of the signal affects the transmission too: signalswith long wavelengths can be transmitted through sea water tosubmarines, while signals with high frequencies can be blocked bya tree. Since mobile phones are used indoors, in cars, and so on, there israrely line of sight between the receiver and thetransmitter. This results in a number of other influences on thereceived signal strength:

• blocking or shadowing, which can stop the signal, for example, when abuilding is situated in the path between a base station and amobile phone user;
• reflection and refraction of the signal as it hits anobstacle such as a building, which can alter the signal'sdirection and speed; and
• scattering and diffraction, which can transform the signalinto several weaker signals.

Figure 5: Line of site path loss from base station site to user.

If a communications link is to be established, the receiver mustreceive a signal of sufficiently high power. Thus, to assess thecoverage of their network, signal strength measurements should betaken at all points within the area the network operator wants tosupply. However, this process is costly and time-consuming due to thelarge amounts of data required for collection and storage. As analternative and to enable planning, many mathematical propagationmodels have been developed to predict the received signalstrengths at discrete points in the service area. Two such modelsare the Okurmara-Hata model [4] and theWalfisch-Ikegami model [11]. Each model is validfor given range of parameters, for example the Okurmara-Hata model is suitable to represent city and townenvironments.

Below is an example of a signal that is transmitted from a basestation and received at a mobile station. The received signal canbe estimated through the use of a simple equation that considerspropagation loss and various signal strength losses and gains.

Power received =		power transmitted by the base station
	+	gain of the base station's antenna
	-	loss of the base stations's antenna
	-	downlink propagation loss
	-	horizontal loss of the antenna
	-	vertical loss of the antenna
	-	mobile station loss
	+	mobile station gain

This sort of calculation is called a link budget and is calculatedfor both the uplink and the downlink.

Multiplexing

Multiplexing is not only fundamental in communication systems butis used by people everyday, allowing many users to share a mediumat the same time with little or no interference. Schiller[10] describes this medium sharing as beinganalogous with cars using multiple lanes on a highway. The cardrivers (users) use the same highways (medium) with hopefully noaccidents (interference). This is a space division multiplexingscheme because the cars use different lanes. It also uses timedivision multiplexing because different cars travel over the samespot on the highway, but not at the same instant in time. Inmobile communications, four different multiplexing schemes areemployed (Figure 6):

Figure 6: Multiplexing techniques.

• Space Divisional Multiple Access (SDMA):Transmitters that are operating on the same channel but that aregeographically separated such that they are outside interferencerange of one another can successfully communicate simultaneously.
• Frequency Divisional Multiple Access (FDMA):Different frequencies are assigned to different communicationlinks. A common example of FDMA is radio stations broadcasting inthe same geographical region: each station has its own frequency,to which the listener tunes in to receive the transmission.
• Time Divisional Multiple Access (TDMA):Each communication link uses the same channel but at differentpoints in time: they take it in turns to transmit. TDMA occurswhen calls are made that do not overlap in time; one call uses thechannel after another call has been completed and is no longerusing the channel.
• Wideband Code Divisional Multiple Access (WCDMA):The most recent and complex of the four multiplexing schemesmentioned, WCDMA [7] involves the use oforthogonal codes to distinguish between communication links. Codesare transmitted simultaneously and each recipient can decode onlythe signal he requires (using the mathematical properties of thecode); other recipients' signals appear only as background noise.The huge number of possible codes available means that this methodhas high security and that many communications can occursimultaneously.

In practice, these techniques may be combined, for example, incellular networks the use of SDMA is implicit within the structureof the network. Within a cellular network, FDMA, TDMA and WCDMAare employed to enable multiple calls to take placesimultaneously. Second generation GSM networks employ FTDMA(Frequency Time Division Multiple Access), which involves thediscritization of the frequency spectrum and time, respectively,whereas third generation systems, such as UMTS, use WCDMA.

Noise

In a cellular network, when a mobile station or base station wishesto receive a signal from a specific sender, any unwanted signalthat is received can be defined as noise. Noise can occur frombackground sources such as electrical equipment and atmosphericconditions that occur outside the communication system. It isimportant that the communication system can distinguish betweenwanted and unwanted signals, and the type of multiplexingtechnique used in the network can be a preventative measureagainst interference.

In cellular networks noise that comes from the same cell is calledintra-cell interference while noise from adjacent cells iscalled inter-cell interference. In GSM systems, the noiseratio is managed by channel assignment. However, in systems usingWCDMA, where all users are share the same channel, interferencecan be caused through the use of codes. As a result, mobile stationusers affect each other's ability to transmit and receive signals.

Network Design Problem

The network design problem has several names and is typicallycalled one of the following: the network planning problem, theantenna positioning problem, the radio coverage problem, or thecell planning problem.

Informally, the network design problem requires a number of inputs:

• a list of locations available for base station sites (formedfrom legacy network site positions and/or newly acquired sitelocations);
• an area the network operator wants the network to supply,for which service, traffic and propagation information can begathered; and
• a list of available antenna types.

The aim of the cell planning problem is to select sites from alist of site locations, and for each determine the number of basestations required and the configuration of the antenna located ateach base station. When an antenna transmits a signal, it isreceived by mobile stations located within the signal's range.Normally, a mobile station will select the base station thattransmits the strongest signal. This happens for all base stationsand the set of regions produced is called the cell plan and thusthe process of planning cellular networks is called cell planning. Figure 7 provides an example of a cellplan for a suburban environment containing 45 active sites from acandidate set of 150 potential sites, each configured withomnidirectional base stations.

Figure 7:A cell plan for a suburban environment with 45active sites (colored white) each configured with omnidirectionalbase stations. Cells are multi-colored and mobile stations arerepresented by yellow dots.

In general, the cell planning problem has the following objectives:

• to minimize the cost of the network for the operator, for example, by using fewer sites;
• to maximize capacity with the aim of providing all mobilestations with their required service, for example, using more sites toassist to reduce the average load per site;
• maximize network coverage with the aim of covering allservice test points, for example, by deploying more sites;
• minimize noise and interference, which is heavily dependenton configuration, for example, change antenna tilt to reduce interference;and
• maintain rules for handover (the passing of a receivedsignal from one base station to another).

Meeting each of the objectives simultaneously is difficult and itis left to the network operator to define the objectives and theirrelative importance.

Planning Cellular Networks

When a network planner designs a network, there are many differentnetwork parameters to set and very little engineering timeavailable. As a result, the number of network design modificationsavailable to the network planner are limited. Manual networkplanning can involve a network engineer designing the networkalone or as part of a team. Computer systems have previously beenused to assist the network planner by analyzing the specifiedquality criteria and then guiding the network planner bysuggesting the most effective parameter changes.

A network design can be altered in a number of different ways:

• antenna power settings can be increased or decreased withina predefined range;
• antenna tilt can be adjusted;
• for sectorized cells the azimuths of the antennas belongingto the base stations can be jointly rotated allowing 360 differentpositions for the same azimuth configuration;
• base stations can be activated and deactivated; and
• omnidirectional antennas can be replaced by threedirectional antennas to form a sectorized cell, which can increasecell coverage and capacity.

The calculation below shows the number of possible configurationsfor one base station that are available to the network operatorwhen considering 10 possible power settings, 15 tilt settings and72 possible azimuth settings.

Configurations per base station =
	x	10	(possible power settings)
	x	15	(possible tilt settings)
	x	72	(possible azimuth settings)
=	10,800

Imagine a network that required 20 base stations each configuredwith an omnidirectional antenna. The number of possible networkdesigns available is approximately 10⁸⁰, which is more thanthe number of protons in the universe! That is considering a smallnetwork without considering evolving site selection. Networkplanners need to consider networks with around 200 site positions.In order to model the network in detail and meet the objectives,the cell planning problem becomes intractable. This emphasizes theneed for high performance automated cell planning tools.

Automated Design

Given the complexity of the cell planning problem, it is nosurprise that attempts have been made to use computers to helpautomate the cell planning process. Automated cell planning can besplit into four aspects: network modeling, network evaluation,network dimensioning, and network optimization; this process isshown in . Many approaches to this problemhave been adopted [1,2,3,6,8,9].

Figure 8: Automated cell planning process.

Modeling the network design problem often presents a trade offbetween abstraction and detail. Abstract models have previouslycompared and modeled the cell planning problem mathematicallyusing such mathematical areas as graph theory, set theory, andinteger linear programming. A network planner working for anoperator may take a detailed approach to modeling the network asthe results have to be accurate, but a more abstracted approachcould be useful for the network dimensioning stage or the processof evaluating a network. Either way, a planning tool must becapable of accurately modeling the system behavior when providedwith network design parameters and traffic demand scenarios.

Network dimensioning is applied to provide the first estimate ofthe network's capabilities in terms of coverage, capacity, and thequality of service provided to the mobile subscribers. The mainobjective of dimensioning is to simplify the complex task ofnetwork planning by making the necessary estimations andassumptions concerning the hardware or resources required toprovide a satisfactory service. Coverage planning usually consistsof a link budget calculation that calculates cell ranges (for boththe uplink and the downlink) and hence the cell coverage area.Capacity planning to estimate how many mobile users each cell canserve can be calculated through the use of pole capacity equationsor cell loading equations.

Network evaluation, which normally takes the form of static or dynamic system simulations, is required in order to ascertain a networkdesign's use with regards to meeting the operator's predictedtraffic demand and network performance targets. Network evaluationshould incorporate as many elements as necessary in order tofinally produce a system that is realistic.

Network optimization in automated cell planning is concerned withproviding a process to change the performance of a network,allowing the translation from desired quality of service targetsto measured network performance and finding the best possiblenetwork design. Sophisticated techniques from computer science canbe applied to network optimization through the use of heuristicsand meta-heuristic solution techniques such as greedy algorithms,exact algorithms, genetic algorithms, hill climbing algorithms,simulated annealing, and tabu search.

Greedy algorithms are used to activate and configure basestations with no further deactivation or reconfiguration. Thissort of algorithm is suitable to attain an initial network design.These methods have the advantage of being easy to implement, butmust be designed for each specific problem, and can often resultin poor-quality solutions that do not explore large proportions ofthe search space. On the other hand, exact algorithms tryall possible network designs and operate by rejecting unsuitabledesigns. As discussed earlier, networks tend to have hundreds ofbase stations. Given that each possible network design has to be examined,this type of algorithm is limited to small networks.

Genetic algorithms were initially developed thirty years agoand involve the use of algorithms based on natural selection.Firstly a population of candidate network designs is produced,which are represented by a string of genes or chromosome. As timepasses the population of candidate solutions evolve based on theuse of biological evolution as a problem-solving strategy. When acandidate solution is selected, it becomes a parent. Next theapplication of genetic operators such as mutation and crossoverare used to evolve the solutions. Crossover involves combiningaspects of parents' genes to produce offspring, whereas mutationinvolves randomly altering an offspring's genes to introducediversity. Genetic algorithms perform well for most combinatorialproblems and are thus suitable as an optimization technique forthe network planning problem.

Hill climbing algorithms can be used to generate asequence of network designs. At each iteration, a network design isperturbed to produce a neighborhood of candidate network designs.This alteration normally consists of slightly changing the networkdesign's parameters, for example, changing several base stations'parameters or activating/deactivating a base station. As a resultthe process for moving from one network design to another allowsthe local search space to be explored. At each iteration, the bestavailable network design in the neighborhood is selected and thenthe process repeats. The main disadvantage of this technique isthat it is often subject to getting stuck in a local optima. It isgenerally recommended that this algorithm is run many times, eachtime starting at a different position in the search space.Improvements to the basic hill climbing algorithm have resulted inmeta-heuristics being developed, such as simulated annealing andtabu search, which attempt to overcome these problems.

Simulated Annealing is used to find near-optimalsolutions in a large search spaces that are typically subject tomany constraints. This technique is linked to thermodynamicsconcerning the process of annealing, which involves the gradualcooling of metals to increase their strength. The slow reductionof temperature facilitates a stronger binding of the metal. Theanalogy to optimization is made by allowing most new candidatesolutions or network designs to to be accepted at first, but as thetemperature cools, the rate of acceptance declines. Tabu searchalso goes beyond terminating at a local optima. The notion ofexploiting certain forms of flexible memory to control the searchprocess is the principle theme. Tabu search maintains ahistory of the states encountered during the search and thishistory record then helps to determine the solutions that may bereached by a move from the current solution.

Challenges of 3G Network Planning

To date, three generations of mobile phone networks have beenintroduced [12]. First generation systems (1G)started in the 1980s and were based on analogue transmissiontechniques. In the early 1990s, second generation networks weredeployed throughout the world, with Europeintroducing GSM. The purpose of GSM was to provide a unifiedstandard in Europe. GSM enabled voice traffic to go wireless andlater evolved to meet the requirements of data traffic and otherservices, producing the following enhancements: GSM and ValueAdded Services (VAS), GSM and General Packet Radio Services(GPRS), and GSM and Enhanced Data-rates in GSM Environment (EDGE).Nowadays, third generation networks are being introduced with anaim to provide the transmission of high bit rate services that areindependent of the technology platform and with network design andplanning standards that are the same globally.

Since the introduction of second generation cellular systems,significant expertise has accrued in network planning. Thecomplexity of the network planning problem is increased when thirdgeneration networks are considered. Radio network planners face anumber of new challenges in the move from second generationnetworks to third generation networks. The following sectionsdiscuss some of these new challenges.

Services

Third generation UMTS networks were developed for the high datarate services they could offer over GSM, GPRS, and EDGE networks.UMTS offers higher bit rate services that have been classified as:

• Conversational: The best known service in this class isspeech. It also contains video-telephony and video games;
• Streaming: This class enables multimedia streaming fortransferring data;
• Interactive: Involves data requests to remote computers i.e.web browsing, database retrieval and server access; and
• Background: Data traffic of applications such as emaildelivery, SMS and downloads.

These services are discussed in detail in[5].

When designing a network the planner has to consider the differentservice types available as the type of traffic (i.e., service type)will not be homogeneous in UMTS. As a result, a service mixmust be defined that represents the percentage of active usersthat utilize each service. GSM has voice dominated traffic with asmall proportion of data services. However, the data channelconsumes the same capacity as voice and the network planning doesnot change subject to the type of traffic. The main feature ofUMTS networks is the introduction of data services. Theinterference caused by data-rate users is dependent on where theuser is located in the cell. For example, a high data-rate user on the edgeof the cell could cause increased interference for other mobilestations. Therefore research into cell planning for UMTS mustconsider the mixed service scenarios and design networks that canhandle increased traffic loads.

Site Locations Are More Restricted in UMTS

Operators want to reuse as many GSM site locations in their UMTSnetworks due to the difficulties in acquiring good site locationsin urban areas and the opportunity to cut network costs. As aresult, UMTS network planning is constrained by a sizable numberof pre-defined site locations.

Multiplexing Problems

FTDMA in second generation network planning is associated with the channel assignmentproblem, which aims to generate a frequency plan to help mitigateelectromagnetic interference. This approach is not feasible forUMTS networks using WCDMA due to the wider carrier bandwidth thatprevents load balancing by swapping carriers among cells. InWCDMA, users, cells and channels are separated by code rather thanfrequency and, as such, WCDMA uses one frequency while FTDMA usesmany. As a frequency plan to reduce the interference does notexist, balancing the traffic load amongst the cells relies heavilyon the adjustment of site positions, antenna configurations, powerlevels, and radio resource management (RRM) algorithms, each ofwhich affects both coverage objectives and capacity objectivessimultaneously.

Coverage and Capacity Planning

Second generation network planning concentrates on coverageplanning. A GSM network can be designed to maximize coverage bytaking steps to limit the interference and using small cells andgood frequency plans. Initially, GSM networks provide high areacoverage across a service area, and then focus moves to increasingthe networks capacity by a process called cell splitting. Cellsplitting involves reducing the cell sizes by adding extra sitesand base stations in to the service area. However, in thirdgeneration systems, coverage and capacity cannot be consideredseparately and more detailed capacity planning is required. Withthe use of WCDMA technology in UMTS, the size of a cell isdependent on the traffic load, which results in a process calledcell breathing. In GSM when signals are sent in the uplink or inthe downlink they can generally be considered as static. In UMTS,power control algorithms are required to ensure that each mobilestation within the network transmits enough energy to conveyinformation while causing minimal interference to other mobilestations. This ensures that a signal transmitted by a mobile stationat the edge of a cell can be received by the base station with the samesignal strength as that received from a mobile station that is located nearer.

Handover

Cellular systems require handover procedures because single cells donot cover the whole service area. In GSM networks handover wasreferred to as hard: as every cell had a differentfrequency. In a WCDMA network because only one channel is used, thehandover is referred to as soft (when a mobile station isconnected to more than one base station at different sites) andsofter (when a mobile station is connected to more than onebase station from the same site). This results in network planners needingtight control over soft handover areas.

Conclusions

Expertise developed by network planners for second generationcellular networks can be used in the planning of third generationsystems. The added planning constraints mean that cell planningfor third generation systems is more complicated, and as such,network operators should place emphasis on the benefits ofdeveloping automated cell planning tools. The cell planningprocess should not be considered finished once the network hasbeen deployed. Continued planning, carried after network roll-out,would allow the use of actual and not predicted traffic demanddata, which would positively impact on the objectives for goodcapacity, coverage and quality of service.

References

1

Amaldi, E., Capone, A., and Malucelli, F. (2001). Optimizing base station siting in UMTS networks. In Proceedings of 53rd IEEE Vehicular Technology Conference, 4, 2828-2832.

2

Anderson, H. R. and McGeehan, J. P. (1994). Optimizing microcell base station locations using simulated annealing techniques. In Proceedings of 44th IEEE Vehicular Technology Conference, 2, 858-862, Stockholm, Sweden.

3

Dehgan, S., Lister, D., Owen, R., and Jones, P. (2000). W-CDMA capacity and planning issues. Electronics & Communication Engineering Journal, 101-118.

4

Hata, M. (1980). Empirical formula for propagation loss in land mobile radio services. IEEE Transactions on Vehicular Technology, 29(3): 317-325.

5

Holma, H. and Toskala, A. (2000). WCDMA for UMTS. John Wiley & Sons, Chichester, England.

6

Hurley, S. (2002). Planning effective cellular mobile radio networks. IEEE Transactions on Vehicular Technology, 51(2): 243-253.

7

Kim, K. (2000). Handbook of CDMA System Design, Engineering and Optimization. Prentice Hall, New Jersey.

8

Mathar, R. and Niessen, T. (2001). Optimal base station positioning and channel assignment for 3G mobile networks by integer programming. Annals of Operations Research, 107: 225-236.

9

Molina, A., Athanasiadou, G. E., and Nix, A. R. (2002). Automated W-CDMA micro cellular deployment and coverage reconfiguration based on situation awareness. In Proceedings of 55th IEEE Vehicular Technology Conference, 1170-1174.

10

Schiller, J. (2000). Mobile Communications. Addision-Wesley, London.

11

Walfisch, J. and Bertoni, H. L. (1988). A theoretical model of UHF propagation in urban environments. IEEE Transactions on Antennas and Propagation, 36(12): 1788-1796.

12

Walters, L. and Kritzinger, P. S. (2002). Cellular networks: Past, present and future. Crossroads: The ACM Student Magazine, 7(2).

---

Biography

Kathryn Oliver ()is a Ph.D. student at the Centre for IntelligentNetwork Design, Cardiff University in the UK. Her researchinterests include modeling, dimensioning and optimization ofcellular networks, specifically UMTS networks. She received herB.Sc. (Hons.) in Computer Science from Cardiff University in July2001. Professor S. Hurley and Dr S.M. Allen are her Ph.D. supervisors.