OPTIMAL TWO-TIER CELLULAR NETWORK DESIGN

by
Eylem Ekici
BS. in Computer Engineering, Boğaziçi University, 1997

Submitted to the Institute for Graduate Studies in
Science and Engineering in partial fulfillment of
the requirements for the degree of
Master of Science
in
Computer Engineering

Boğaziçi University
1998

OPTIMAL TWO-TIER CELLULAR NETWORK DESIGN

APPROVED BY:

			Assoc. Prof. Cem Ersoy	………………………………
			(Thesis Supervisor)
			Dr. Sema Akgün Oktuğ	………………………………
			Assoc. Prof. Günhan Dündar	………………………………

DATE OF APPROVAL	………………………………

ACKNOWLEDGMENTS
I would like to thank to my thesis supervisor Assoc. Prof. Cem Ersoy for his kind support and patience. Without his guidance, it would be impossible for me to finish this thesis. I would also like to thank to Dr. Sema Akgün Oktuğ and Assoc. Prof. Günhan Dündar for their participation in my thesis jury.
I would express my thanks to Sinan Önder for criticism in the early stages of this thesis and his partnership.
I particularly want to thank to my family and Özlem Doğan for their love, support and encouragement.

ABSTRACT
Wireless communications systems enable the end users to be mobile. Majority of the wireless communications networks are cellular networks. Several methods are developed to increase the performance of the cellular networks. The performance of the cellular networks depend on the correct determination of the design parameters as well as the architecture of the system and the traffic requirements. The performance of cellular networks also depends on their implementation cost.
One of the ways to improve the performance of the cellular networks is to build a second layer of macrocells on top of the microcell level. The system performance can further be increased by using guard channels and allowing calls to overflow to the upper layer when needed. In this thesis, we used simulated annealing (SA) to determine the design parameters of two-tier cellular networks with guard channels and overflow, for which the cost is minimized. We tested the system on example problems and obtained promising results.

ÖZET
Kablosuz haberleşme sistemleri, son kullanıcıların hareketliliğine izin verir. Kablosuz haberleşme ağlarının pek çoğu hücresel ağlardır. Hücresel ağların başarımını arttırmak için çeşitli yöntemler bulunmaktadır. Hücresel ağların başarımı sistem mimarisi ve trafik gereksinimlerine olduğu gibi, tasarım değişkenlerinin doğru belirlenmesine de dayanır. Bu başarım aynı zamanda sistem sistem maliyetine de bağlıdır.
Hücresel ağların başarımını arttırmanın yollarından birisi de küçük hücre düzeyinin üzerine büyük hücre katmanı kurmaktır. Sistem başarımı, koruma kanallarının kullanılması ve gerektiğinde aramaların üst katmana taşmalarına izin verilmesiyle daha da arttırılabilir. Bu çalışmada tavlama benzetimini, maliyeti en aza indirilecek olan iki katmanlı, koruma kanallı ve taşmalı hücresel ağların, tasarım değişkenlerinin belirlenmesinde kullandık. Örnek çalışmalar üzerinde yaptığımız denemeler oldukça iyi sonuçlar vermiştir.

TABLE OF CONTENTS
Page
ACKNOWLEDGMENTS	iii
ABSTRACT	iv
ÖZET	v
LIST OF FIGURES	ix
LIST OF TABLES	xi
LIST OF SYMBOLS	xii
1. INTRODUCTION	
2. PERSONAL COMMUNICATION SERVICES	
2.1 Cellular Concept	
2.2 Cellular Communication Network Preliminaries	
2.2.1 Cellular Network Infrastructure	
2.2.2 Communication Setup and Maintenance	
2.2.3 Mobility Management	
2.2.4 Channel Allocation Schemes	
2.3 Modeling Cellular Networks	
2.4 Cellular Network Design Approaches	
2.4.1 Prioritized Cellular Networks	
2.4.2 Multi-tier Cellular Networks	
3. PROBLEM DEFINITION	
3.1 Assumptions	
3.2 System Description	
3.3 	Constraints and Parameters	
Page
3.4 Problem Formulation	
4. SOLUTION TECHNIQUES	
4.1 Calculation of Cost and Performance Measures	
4.2 Simulated Annealing Algorithm	
4.2.1 Neighborhood Structure	
4.2.2 Stopping Criteria	
4.2.3 A Typical Run of SA Algorithm	
4.3 Greedy Search Algorithm	
4.4 Generate and Test Algorithm	
5. COMPUTATIONAL EXPERIMENTS	
5.1 Base Problem	
5.2 Effect of Some Parameters and Design Decisions	
5.2.1 Effect of Call Arrival Rate	
5.2.2 Effect of Mean Speeds	
5.2.3 Effect of Mean Call Duration	
5.2.4 Effect of the Call Blocking Threshold	
5.2.5 Effect of the Call Dropping Threshold	
5.2.6 Effect of the Area	
5.2.7 Effect of Cluster Size	
5.2.8 Effect of Number of Available Channels	
5.2.9 Effect of Overflow	
5.2.10 Effect of Guard Channels	
5.2.11 	Effect of Second Tier	

Page
5.2.12 Scale of the Effects of Parameters on the Cost	
5.3 Demonstration of Results	
5.3.1 Range of the SA Solutions	
5.3.2 Comparative Evaluation of SA, GS and GAT Solutions	
5.4 Effect of Call Arrival Rate Fluctuations	
5.5 Time Complexity	
6. 	CONCLUSION AND FUTURE WORK	
REFERENCES	82

LIST OF FIGURES
Page
FIGURE 2.1  A Cellular Layout (Cluster Size=7)	
FIGURE 2.2  A Macrocell Covering Seven Microcells	
FIGURE 3.1  Call Service Pattern	
FIGURE 4.1  Sample State Transition Diagram for Microcells (5/2)	
FIGURE 4.2  Sample State Transition Diagram for Macrocells (5/2)	
FIGURE 4.3  Pseudo-Procedure of SA Algorithm	
FIGURE 4.4  A Typical Run of SA Algorithm	
FIGURE 4.5  A Typical Run of GS Algorithm	
FIGURE 4.6  A Typical Run of GAT Algorithm	
FIGURE 5.1  Low Mobility Call Arrival Rate vs Cost	
FIGURE 5.2  High Mobility Call Arrival Rate vs. Cost	
FIGURE 5.3  Mean Low Mobility User Speed vs. Cost	
FIGURE 5.4  Mean High Mobility User Speed vs. Cost	
FIGURE 5.5  Mean Call Duration vs. Cost	
FIGURE 5.6  Threshold Probability for Call Blocking vs. Cost	
FIGURE 5.7  Threshold Probability for Call Dropping vs. Cost	
FIGURE 5.8  Coverage Area vs. Cost	
FIGURE 5.9  Cluster Size vs. Cost	
FIGURE 5.10  Number of Available Channels vs. Cost	
FIGURE 5.11  Low Mobility Call Arrival Rate vs. Cost (Overflow Comparison)	
FIGURE 5.12  High Mobility Call Arrival Rate vs. Cost (Overflow Comparison)	
FIGURE 5.13  Low Mobility Call Arrival Rate vs. Cost (Guard Channel Comparison)	
Page
FIGURE 5.14  High Mobility Call Arrival Rate vs. Cost (Guard Channel Comparison)	
FIGURE 5.15  High Mobility Arrival Rate vs. Single- and Two-Tier Costs	
FIGURE 5.16  Macrocell Setup Cost vs. Single- and Two-Tier Costs	
FIGURE 5.17  Low Mobility Call Arrival Increase vs. Pb/Pd	
FIGURE 5.18  High Mobility Call Arrival Increase vs. Pb/Pd	
FIGURE 5.19  Number of Available Channels vs. Mean Runtime of a Single SA Run	
FIGURE 5.20  Channel Number vs. Total Runtime	

LIST OF TABLES
Page
TABLE 3.1  User Supplied Parameters	
TABLE 3.2  Decision Parameters	
TABLE 5.1  Parameters of the Base Problem	
TABLE 5.2  Values of Decision Parameters for the Base Problem	
TABLE 5.3  Costs of Single- and Two-Tier Systems for Different Problems	
TABLE 5.4  Statistics of 10 SA Runs for Several Problems	
TABLE 5.5  Results Obtained with SA, GS and GAT Algorithms for Several Problems	

LIST OF SYMBOLS
A	Total area	
C	Total system cost	
C1	Macrocell cost	
C2	Microcell cost	
cr	Cooling rate	
CS	Cluster size	
Ch1	Number of channels reserved for each microcell	
Ch2	Number of channels reserved for each macrocell	
Chtotal	Total number of available channels	
D	Distance between cell centers	
FAm2	Call arrival rate per second per m2 for high mobility terminals	
G1	Number of guard channels reserved for each microcell	
G2	Number of guard channels reserved for each macrocell	
p	Radius increase/decrease factor	
Pb	Call blocking rate	
Pb,max	Maximum allowable call blocking probability	
Pd	Call dropping rate	
Pd,max	Maximum allowable call dropping probability	
Pi	Steady state probability for microcells	
Pij	Steady state probability for macrocells	
Pr	Received power level at a distance of r	
Q	Co-channel reuse factor	
r	Radius of a microcell	
R	Radius of a macrocell 	
SAm2	Call arrival rate per second per m2 for low mobility terminals	
S/I	Signal to co-channel interference ratio	
Ut	Inverse of mean call duration	
Ud1s	Inverse of dwell time of the low mobility users in the microcells	
Ud2s	Inverse of dwell time of the low mobility users in the macrocells	
Ud2f	Inverse of dwell time of the high mobility users in the macrocells	
vf	Mean speed of high mobility users	
vs	Mean speed of low mobility users	
1s	Low mobility call arrival rate to the microcells	
1sh	Low mobility handoff call arrival rate to the microcells	
1sh	Temporary low mobility handoff call arrival rate to the microcells	
2sh	Low mobility handoff call arrival rate to the macrocells	
2f	High mobility call arrival rate to the macrocells	
2fh	High mobility handoff call arrival rate to the macrocells	
os	Low mobility new call overflow rate	
osh	Low mobility handoff call overflow rate	
	Path loss exponent	

1.	INTRODUCTION
As the technology evolves, the demand for better and faster communication systems also increases. After the introduction of wireless communication systems a decade ago its growth has been rapid [1]. The number of wireless communication service users as well as the spectrum of the available services increased with an unexpected rate. The main reason for this growth was the newly introduced notion of terminal and user mobility. It is expected that the wireless communications will be the dominant mode of data access technology in the next century [2].
The main characteristics of all wireless communication systems are that the terminals are connected to the rest of the communications network via wireless links, that is, radio signals. The scale of the wireless links as well as the type of services varies drastically. These include cordless telephones, pagers, wireless local area networks [1], wireless ATM networks [3], mobile telephones, and some special purpose wireless communication systems [4]. The physical separation between the mobile terminal and the access point of the fixed network in all these systems vary from a few meters to tens of kilometers, and the devices used from simple, low power transceiver devices to satellites.
The common denominator in all the system mentioned, except for the cordless telephones, that the design of the network relies on the cellular concept [5]. In this approach, the total area to be included in the system is divided into so-called cells, where a subset of all available channels is used in each cell. The main idea is to use the channel subsets in cells that are far apart to ensure an interference-free communication scheme with potentially infinite coverage capability. The flexibility gained is deployed in many fields and cellular concept is regarded to be the standard way of designing wireless networks. Today, all large scale wireless networks are based on this concept.
Because of the large number of specialized systems, the research areas are very diverse. While some researchers aim to solve problems common to all systems, others focus on the problems special to a subset of the systems. Although the different research efforts may not seem correlated, they constitute a part of the solutions that may be used in the design of a new generation of wireless technologies, known as IMT-2000 [2]. The aim of this new generation system is to provide seamless communication anywhere, at any time. The data transfer capacity of the new system is planned to be around 2 to 20 Mbps, which will enable the transfer of multimedia containing messages. Furthermore, this system will include a large variety of services. Such a system is thought to include almost all of the services provided in today’s networks, and many that are not provided yet.
The system that combines the services mentioned into a single system as described above is called Personal Communication Services (PCS). Although the ideal PCS does not exist, the wireless cellular systems that are available are also called PCS provided that the user is mobile with its communication terminal.
The design efforts regarding wireless networks aim to improve the system performance while fulfilling certain constraints. There are several criteria that are used to measure the performance of wireless networks. Some of these measures are the data transfer rate, error probability, new call rejection rate and forced termination rate. The first two criteria are common to almost all communication networks, while the last one is used to measure the performance of the wireless networks only. They are used as both constraint and objective in the design phase.
There exist several ways to limit the probability of forced termination; the probability of termination of an ongoing call, where the term call refers to a communication session. One of them is to have spare channels, which are called guard channels, for the ongoing calls. Furthermore, since the mobility of the terminals plays an important role in the performance of the cellular systems, an ideal system should serve all mobility classes fairly. Combining both ideas, the focus of this work is chosen as designing a wireless cellular system with guard channels, deployment of two cellular layers on top of each other and overflow. The aim is to minimize the system cost while satisfying the maximum call blocking and forced termination probabilities.
In order to solve the design problem, a well-known artificial intelligence technique, Simulated Annealing (SA) [6], is chosen. It is a neighborhood search technique with incorporated probabilistic behavior. Hence, this technique combines the advantages of random search with the ones of greedy search. It basically starts with an initial feasible solution and tries to find better solutions. During the pace of the algorithm worse moves are accepted with a probability that decreases with time. This probabilistic behavior enables the algorithm to search beyond local minima. The choice of this technique helped to obtain near optimum solutions since the problem involves many local minima.
Many computational experiments are performed to assess the results of the outcomes and to evaluate the performance of the designed systems. The subject systems are chosen to cover a large space of possible requirements and constraints. Furthermore, experiments showing the effects of several system parameters and design decisions are performed. The behavior of the designed system under increasing load is presented with other computational experiments.
The outline of this thesis is as follows:
In the second section, cellular networks and some cellular network design approaches are examined. The preliminary concepts concerning cellular networks and underlying infrastructures are explained. Additionally, the traffic and mobility modeling in cellular networks are examined briefly.
In the third section, the design problem is formulated. The assumptions that ease the inspection of the system, constraints and decision variables are explained extensively. Furthermore, the objective function that will be used in the solution techniques is described and the calculation methods are presented.
The fourth section explains the solution technique extensively. In this section, the system description, neighborhood structures of the system descriptions, the stopping criteria are presented. Furthermore, a typical run of the SA algorithm is presented. Additionally, the alternative solution techniques implemented in order to compare with the results of the SA are also described.
In the fifth section, the results of the computational experiments are presented. It includes the results of different size problems, effects of input parameters and design decisions on the cost of the system and persistence of the system performance in case of traffic load fluctuations. The time complexity of the algorithm is also investigated in this section.
In the last section, conclusion of this work is drawn and some related problems that should be studied in the future are suggested.
2.	PERSONAL COMMUNICATION SERVICES
As described in the first section, Personal Communication Services are the collections of services that are provided in wireless communication systems. Since t hose systems deal with large amount of space, cellular networks are deployed. This section is devoted to cellular networks in general. The cellular concept, cellular network preliminaries, modeling and design issues are investigated in this section.
2.1	Cellular Concept
Wireless networks are characterized with their wireless last hops within the communication chain from any arbitrary node to any mobile terminal. This means that the mobile terminals are connected to the fixed network with a wireless link. This link is most of the time a radio channel. Radio channels are frequency bands used for communication that are separated from each other with guard bands. If two sources try to send data over the same channel at the same time, then the data sent cannot be received by the receiving end properly. Although there are alternative ways to access the medium and define the channel concept differently, this definition is enough for the discussion of the cellular concept.
If a large area is to be included in the wireless communication system, then there are a few possibilities to manage this. The first possibility is to have a single big transceiver antenna. This case is similar to the radio transmitters that service a large area. Let this antenna with its proper equipment be called Base Station (BS). On the other hand, if multiple users of the system want to use it, there should be enough channels available for each connection. Otherwise, the users should wait until the channels become available. If only one base station is present in a certain area, then there should be enough number of channels available in order to keep the rejection probability at a reasonable level, which is infeasible most of the time.
Since the number of channels are scarce most of the time and the number of users willing to use the system cannot be predetermined easily, it is necessary to reuse the limited number of channels in the system. If the antennas of the base stations are placed far enough from each other such that the interference level is below a certain level, both communication sessions can continue over the same channel simultaneously. Let the area in which a base station is active as a cell. The power level of the received signal can be expressed as in [5]:
 				     (2.1)
The term Pr is the power level received at a distance of d from the antenna, P0 is the measured power level at a distance of d0 and the  is the path loss exponent, which is in the order of two to four in the urban environments.
If the whole set of available channels will be used in each cell, then the received power level at an equal distance from both base stations will be equal if they work at the same power level. In any other location, one of the stations will be dominant. So in the near vicinity of the cell boundaries, there will exist locations where none of the base stations will be dominant. Hence, communication will not be possible. In order proper communication to continue, the signal level from the base station serving the calls in the cell should be so large that another base station using the same channels should be almost imperceptible. It is enough to consider only the nearest neighboring base stations that use the same channels because the signal power level received from other base stations will be at most 2- times that of the next such base station according to Formula 2.1.
In order not to leave any gaps between the cells, several strategies are developed. The frequency set is divided into subsets and each base station is assigned a certain subset. The subsets are assigned to the base stations such that the above condition of separation is satisfied. Once all the frequency subsets are assigned to the cells, the same subsets can be reassigned to other cells. The assignment is done such that none of the neighboring cells use the same frequency subset. This pattern is called frequency reuse since the frequencies can be reused at locations that are sufficiently apart. The placement of the base stations is one of the problems that has to be solved and is investigated in [7].
The ideal shape of the cells are hexagons. With hexagonal layout a certain area can be covered completely without leaving a gap. Furthermore, this shape can easily be obtained if the omni-directional antennas of the base stations are placed such that the boundaries of the cells are determined by the signal power of corresponding base stations. Another advantage of this shape is that the difference between the closest and furthest points on the boundaries are minimal among the shapes that can cover an area without any gap. This assures that the power level difference on the boundaries of a cell is minimal. In reality, though, the shapes of the cells are anything but hexagon due to terrestrial factors.

FIGURE 2.1  A Cellular Layout (Cluster Size=7)
If the whole frequency set is completely used by N cells, then these cells constitute a cluster and the cluster size in that system is N and is a very important system parameter. Figure 2.1 shows a typical cellular layout with cluster size equal to seven. The numbers in the hexagonal cells indicate the channel set used within the cell.
For hexagonal cells, the cluster size can be calculated as follows:
			      (2.2)
The co-channel reuse factor Q is the ratio of the distance D between the cell centers that use the same frequency set to the larger radius R of the hexagonal cell. Q and N are related to each other with the following formula.
					(2.3)
The signal to interference ratio S/I is the measure of requested signal to co-channel interference ratio. Furthermore, if there are i0 immediate neighbors using the same co-channel set, S/I can be approximated as:
				     (2.4)
If the value of Q is small, the system capacity increases since the value of N is also small and the channels can more frequently be used over a given area. On the other hand, if the value of Q is large, this leads to better transmission quality since the S/I ratio increases. At the same time system capacity decreases [5]. The choice of N depends on the quality of the transceivers used and the terrestrial factors. It should be chosen as small as possible and as large as necessary. Its value is not a cellular network design decision variable but it should be provided or calculated before the design phase starts.
When the necessary S/I is determined, the cluster size is also determined and vice versa. It is very interesting to note that calculation of the required signal to interference ratio is independent of actual radii and distances. Once the cluster size is determined, the designer is free to choose any radius for the cells. Hence, the cell radius is an engineering parameter in the cellular network design problems.
For more detailed information on cellular concept and frequency reuse the reader should refer to [5].
2.2	Cellular Communication Network Preliminaries
All the wireless communication networks based on the cellular concept are called cellular networks. In order to provide accessibility anywhere in the system and seamless communication, cellular networks have a rather complex structure. This section is devoted to cellular networks and their properties.
2.2.1	Cellular Network Infrastructure
Cellular networks can be examined mainly in two separate groups. The first part is the wireless part. This part is made up of base stations that serve the Mobile Terminals (MT) within their coverage range in the cells. The MTs communicate with the base stations using their transceivers. The additional equipment contained in the MT depends on the service provided by the system and the protocols used for communication between the MT and BS. The communication between the BS and MTs is established using the radio channels that are assigned to the base station.
The second part of the network is the fixed communication network. This part again depends on the aim of the communication system. In general, the base stations are attached to a controller that manages the calls and tracks all the mobile terminal activities in a cell. These controllers may be dedicated computers [8] or switches [9] in case of a local area network or ATM network, or so-called Mobile Switching Centers (MSC) in case of cellular telephone systems.
Every MSC is assigned a group of base stations. The grouping of the base stations to MSCs are done according to the amount of traffic between the base stations [10]. A base station communicates directly with its MSC for accessing other parts of the network for any reason. Hence, MSCs constitute gateways for the communication between the base stations and the rest of the network. The MSCs in a network are interconnected via communication links. Most of the time, the networks that are used for data transfer and signaling are separate. In cellular telephone networks, the maintenance data is sent over a dedicated network, while data transfer between the MSCs occurs over a different, separate network. In some cases, the data is transferred over Public Switched Telephone Networks (PSTN).
The MSCs tend to become the central constructs of a cellular network. In some systems, MSCs assign the channels to the calls. Therefore, the load on them is high. In order to prevent them from becoming a bottleneck, the load is tried to be shifted towards the base stations and distributed over the other network elements [11].
2.2.2	Communication Setup and Maintenance
The communication between the BS and MT occurs over radio channels. Each communication channel consists of a channel pair, one for communication from BS to MT, which is called down channel, and another for communication from MT to BS, which is called up channel. For every communication session, a channel pair is assigned. This pair is used while the session continues within the same cell. There is also another pair of channels tapped by all MTs, which are used for signaling purposes.
When a call for an MT arrives to the BS, the identity of the MT is broadcast via the down signaling channel. When the target MT identifies itself, it replies with a positive acknowledgment via the up signaling channel. Then, the BS specifies the channel pair that will be used for the communication. Afterwards, the data transfer and signaling continues on respective channels.
When an MT initiates a call, the BS is informed with a message sent via the up signaling channel. The call request is passed to MSC by BS, and the MSC handles the rest of the connection request. When the connection with the other party is established, the BS specifies the up and down communication channels to the initiator MT. The rest is similar to the previous case [5].
Since the mobile terminals are free to move, it is not guaranteed that any MT involved in a communication session will remain in the cell it once was during the lifetime of the session. When an MT goes over to another cell while a call proceeds, the call is passed to the new base station. This procedure is called handoff. The average number of handoffs during a session depends in the cell radii, mobility pattern of the mobile terminals and call duration.
Two thresholds are set for the handoff procedure. When the power level drops below the first threshold, the handoff procedure is triggered. As long as the power level remains above the second threshold, which is lower than the first one, the perception of the signal is enough for proper communication. In order to provide seamless communication, the received signal powers are monitored. The handoff must be completed before the signal level drops below the second threshold.
In case of a handoff, the call is transferred to the base station of which the received power level is highest. Therefore an MT, the initial and a final BS is involved in a handoff procedure. The transfer of pre-established communication links from one base station to another one takes time. It is possible that new resources are not available on the way to the new base station. Especially when the carried data rate cannot be determined beforehand, it may be difficult to allocate necessary resources on time. Hence, the gap between two threshold values should be chosen very carefully to allow the procedure enough time to be completed. Details and an overview of handoff strategies can be found in [12].
Another important issue is that the data should not be lost during the handoff. According to the properties and aims of the application and network, deployment of buffers may be necessary. If only multimedia content is transferred, the buffering may not be necessary. On the other hand, deployment of buffers is inevitable for handoffs for data transfer. The buffer deployment strategies and how the buffered data can be transferred to the MT is discussed in [13].
When the scope of the cellular networks are extended to include also multicasting, different considerations are necessary [14]. Buffering is also deployed in cases of multicasting data to many mobile terminals over heterogeneous data rates. The synchronization of data during handoffs is a very challenging problem. Possible solutions to this problem is presented in [15].
2.2.3	Mobility Management
It is not enough to provide access to the mobile terminals or keep the communication alive despite the mobility. It is also of vital importance to keep track of the locations of the mobile terminals. Again no assumption about the location of the mobile terminal is logical. Hence, there should be a way of finding the mobile terminal in a reasonable time and at a reasonable cost. The efforts to locate the mobile terminals in the entire network and update of the location information is called Mobility Management.
There are mainly two fundamental operations in location management [16]. The first one is location update. Location update corresponds to reporting the location of the mobile terminal to its home location register, a database at the home of the mobile terminal. The second operation is paging. This operation corresponds to broadcasting the identity of a mobile terminal over a certain area. These two operations are inevitable for locating the mobile terminal. When a call is directed to a mobile terminal, the home location register is checked to find out the location of the mobile terminal. Then, the call is redirected to the actual location of the mobile terminal. When the call reaches the designated location, the mobile terminal is paged.
The location data stands most of the time for a group of cells, which is called a location area [17]. The location update is performed when a mobile terminal enters the location area. If the location area consists of only one single cell, the exact location is retrieved from the home location register and the paging cost is minimized. But this would lead to high location update costs and create lots of signaling traffic significantly. On the other hand, if the size of the location area is increased, the frequency of location updates decreases. However, paging has to be performed in more than one cells. Note that even if the location area consists of only one cell, paging should be performed.
There are three major different location update strategies. The update may be based on the time elapsed, the number of movements [16] or the distance traveled [17]. In any case, the location uncertainty introduced with location areas persists. Therefore, for each approach, the trade-off between the traffic generated and paging cost has different levels. It is also possible to optimize the location update procedure. In order to achieve this, a hierarchical structure is proposed in [18]. Here the information dissemination follows a hierarchical structure. So the amount of data flowing in the network is lowered.
Different ideas and approaches are proposed in the literature to optimize the mobility management. These considerations also take different levels of constraints and mobility models into account. The common aims, though, are minimizing the paging and communication load while keeping the location delay in acceptable amounts. Some related approaches can be found in [16-19].
2.2.4	Channel Allocation Schemes
The total amount of channels available for the cellular network can be assigned to cells in different ways. The process of assigning channels either to cells or to calls is called channel allocation [20]. The schemes used differ in performance, flexibility and complexity. However, there is a tradeoff among these qualities, hence each scheme has advantages and disadvantages.
Channels can be distributed to cells statically, dynamically or in hybrid ways. The most commonly used scheme is to assign the channel sets statically to the cells. The cells may use the channels from the available set without any other constraint. This scheme performs well under the uniform traffic load over the cells. Its performance is also high in cases where the total traffic load is high.
In order to cope with situations where the traffic load differs from one cell to the other and where traffic load ratios do not change very much over the time, the cells may be borrowed to heavily loaded cells. If the channel set sizes are not equal, this corresponds to static borrowing. If the system has hot spots where the traffic intensity increases for short periods of time, then the channels may be lent by the lightly loaded neighboring cells to the temporarily highly loaded cell. Then the problem is solved at the cost of not being able to use the borrowed cells in a larger area than before [20]. 
It is also possible to set limits on the number of cells that can be borrowed in order to prevent starvation. In any case, a certain borrowing algorithm has to be deployed. The algorithm may choose channels from the richest cell. Another choice would be to borrow the first available channel in the neighborhood. It is also possible to return the used channels back to the donor as soon as a channel from the set of channels that belong to the cell that borrowed becomes available [20].
It is possible to assign the channels to the cells according to their needs. The channels are kept in a common set. The cells do not have their own channels. The assignment is done in call basis. In order to stick to the rules of frequency reuse, the determination of channels to be assigned has to be made carefully. The schemes that are based on the dynamic channel allocation are examined according to the way the assignment decision is performed [20].
The first scheme has a central decision element which decides on the channels that has to be assigned to calls. As it is the case for all centralized systems, the main drawback of this approach is that the central authority becomes the bottleneck of the system. So it is possible to distribute the decision to the base stations. The base stations collect local data from their vicinity and make their allocation decisions according to this. The resulting assignment is not optimal due to local character of the collected data. The results can be specialized and optimized for the one dimensional movement case [20].
Another possibility is to combine both approaches into one hybrid system. The entire channel spectrum is divided into two subsets. The first set is distributed to the cells statically. The remaining channels are assigned to cells according to the traffic load and call requests. Since the two systems are combined, any choice of the sub-strategies can be applied to the respective part of the scheme.
2.3	Modeling Cellular Networks
Terminal mobility creates a large amount of new problems when compared with the stationary terminals. Some of the solutions are presented in the preceding section. In order to obtain the performance measures of the systems without actually building them, it is necessary to develop traffic and mobility models that will correspond to the real life. Only after proper models are developed, assessment of new ideas as solutions to problems can be realistic.
In cellular networks, the presentation of the traffic is dependent on both time and space [21]. It is necessary to model the distribution of the mobile terminals over the space. The time dimension represents issues like the movement of the mobile terminals over the space. The movement can be examined over large periods of time in the general picture. It is also possible and necessary to examine the small scale movements in a given part of the whole area.
The density of the mobile terminals in a given area is primarily responsible in the creation of the traffic. The traffic load in the system is heavily dependent on this parameter. Determination of the mobility characteristics of the users in the coverage area of the communication system changes the mobile terminal distribution over the space. The density of mobile terminals may be concentrated at certain locations of the whole area. The concentration locations may be main streets and shopping centers. This picture may change in time tremendously, from day to night, on different days of the week or over the months. The terminal concentration locations may be the hot spots of the traffic during the day time. But over nights the terminal density may become more uniform. The terminal density modeling is investigated in [22, 23].
The mobility of the terminals should also be modeled. The effect of the location update on the system performance depends both on the decisions made for the cellular network and the movement of the mobile terminals. For determination of the effects quantitatively, the mobility should be modeled carefully [24]. Furthermore, the tendency of movement of the mobile terminals when they are involved in an active communication session in a certain area effects the handoff traffic extensively. Hence the mobility models are also used when modeling the handoff traffic [25].
Beyond space and movement considerations, another important parameter in cellular systems is the duration of the communication sessions [26]. It basically determines the duration a channel will be occupied in a cell. The availability of channels in the cells determines the call blocking and call dropping rates of the cellular systems. The speed of the mobile terminals can implicitly be represented with the mobility pattern, call duration and the cell residence time.
The call duration also represents in networks with constant data rates the amount of data that has to be carried by the network. Hence, the capacity of the fixed network should be chosen accordingly. In networks, where the data rates may be variable, the load on the system cannot be represented only by the call duration. One of the aims of the future cellular networks is to transfer multimedia containing messages between the mobile terminals. Since the multimedia traffic is bursty in nature, this should also be integrated into the system model. This way, not only the fixed part of the network but also the access methods of the wireless environment and their performance can be examined [27].
Mathematical models are needed to assess the performance of the cellular networks without building them physically. In [28] the mathematical models that are used for traffic modeling are summarized.
2.4	Cellular Network Design Approaches
While designing cellular networks, there are several goals to be achieved. Some designers try to achieve fairness in cellular networks [29] and some try to design a cellular network that has a high survivability [30]. But for the sake of this thesis, design efforts for achieving prioritized and multi-tier cellular networks are of higher importance. The proceeding sections will present the general ideas and some previous designs.
2.4.1	Prioritized Cellular Networks
In the cellular networks, the arriving calls are basically examined in two classes. The first class is made up of the new arriving call requests. The calls in the second class is the handoff calls. The handoff calls are different from the new calls in the sense that there exists an ongoing communication session. These are directed to the base station that is perceived the best. In the normal case, the calls are serviced as long as there are available channels in the cell. No distinction between new calls or handoff calls is in question.
When the new calls are not serviced due to lack of channels it is said that the call is blocked. When a handoff call cannot find free channels for the continuation of the session the call terminates forcefully. This situation is described as call dropping. But from the users point of view, this situation is far less desirable than the first one [31]. Therefore in some newer systems the handoff calls are given higher priorities. Cellular networks in which handoff calls are prioritized are called prioritized networks. 
The non-prioritized systems are examined in [32]. The formulation of the call blocking and dropping probabilities are presented under light and heavy traffic conditions. An approximation for the moderate traffic case is also available in this work.
In the literature, there has been many attempts to improve the performance of systems regarding the call dropping and call blocking. In this case, the mathematical model used to represent the call arrivals and determination of the arrival rates of the new calls and handoff calls play an important role. A bad choice of mathematical model or improper determination of the arrival rate may result in unrealistic results.
One of the simplest ways to give priority to the handoff calls is to reserve some channels exclusively for them [33]. These reserved channels are called guard channels. In this approach the handoff calls may use all available channels. On the other hand, the new calls get a channel assigned if the number of the channels in use is less than a certain threshold. The value of the threshold effect directly the probabilities of call blocking and dropping. Although the performance in terms of call dropping increases, the improvement has also its drawbacks. Reserving channels for handoff calls leaves less resources for the new calls and the probability of call blocking increases. In [33], an efficient way to minimize the call dropping probability while staying below a given call blocking probability threshold is presented.
Another method to increase the performance of the entire system is to queue the incoming calls in case they cannot be serviced immediately. The queue length effects the performance of the system extensively. Another important issue in queuing systems is the maximum allowable waiting time in the queue. This value is small for the handoff calls and larger for new calls. Furthermore, such systems are more complex than the non-queuing systems.
This system can also be combined with the idea of reserving some channels solely for the handoff purposes [34,35]. In this case, the handoff calls may use all the channels assigned to the cells. They are queued when there is no free channel available. The new calls may only use the channels that are not reserved for the handoff calls. When the channels that can be used by the new calls are occupied, then the calls are queued. Also a similar approach is proposed in [31] where the queue is not a FIFO queue but the priorities of the queued calls change with time.
The performance improvements for guard channel and queuing schemes are compared in [36] for various combination of parameters and mobility patterns.
It is also possible to try to improve the performance without reserving channels for the handoff calls. The method described in [37] is based on the estimation of the trajectory of the mobile terminal and acting proactively, without waiting for the handoff to occur. Another idea is to use the channels of the neighboring cells if no channel is available in the current cells [38]. This is only possible if the received power level from the neighboring base station is at an acceptable level. As can be predicted easily this method gives more chance to the mobile terminals that reside near the boundaries. However, the overall system performance increases even if the improvement is not evenly distributed among the mobile terminals.
All techniques mentioned assume a cellular system, which is based on the fixed channel allocation scheme. The reason for this is that the fixed channel allocation schemes are preferred because of their simplicity by many cellular network designers. If the channels can be borrowed from neighboring cells, a way to give priority to the handoff calls is to let the mobile terminal continue to use the same channel in the new cell if no channel is available in the new cell [39]. The performance of the system depends on the radius the channels may be borrowed. The system assumes linear arrangement of cells and uses only local data. The idea can be extended to let the mobile terminals carry the channels to any cell they may enter during the session. In this case, the standard deviation of the speed of the mobile terminals should be far less than its mean. These approaches are mostly preferred for the cellular networks that cover the highways [20, 39]
2.4.2	Multi-tier Cellular Networks
Since the cellular networks use radio links to reach the mobile terminals, multiple cellular networks can coexist in the same area. In such cases, the cells of different systems overlap. It is equally well possible to design systems that have multiple layers of cells that cover the same area. The cellular layers are interconnected with the wireline network and the control of the base stations that belong to different layers may be given to the same MSCs. Cellular networks that employ multiple layers of cells over the same area are called multi-tier cellular networks. Figure 2.2 shows a macrocell covering seven microcells. Since the microcells and macrocells overlap, in no part of the coverage area, the channel sets of the microcells and macrocells may be the same.
Note that the single-tier cellular networks may also have different cell radii over the entire coverage area. However, unless the cells of one tier overlap with the cells of another tier, the network cannot be called multi-tier. The existence of different cellular layers does not inhibit the functioning of other layers. But the functions of different layers are controlled by the MSCs and they are interrelated.
There are several reasons for designing multi-tier cellular networks. One aim is to provide service for mobile terminals with different mobility and traffic patterns. The required performance measures can be met if the traffic and mobility patterns can be divided into more homogeneous parts and treated separately. Consider a system where there are two mobility classes. If the cell radii are optimized for the slower mobile terminals, then the faster ones will have to make a lot of handoffs during one communication session. On the other hand, if the optimization is made regarding the handoff performance of faster mobile terminals, then the load in each cell may exceed acceptable limits. In multi-tier cellular networks, different layers give the designer the opportunity of class based optimization.

FIGURE 2.2  A Macrocell Covering Seven Microcells
Another aim is to provide service in places, where there is no base stations can be built, with the help of the satellites. These places include oceans or high mountains. The service quality for the mobile users that use the satellite layer may not be as high as expected, but at least the connectivity is provided. This may be vital in emergency cases. Since the satellite beams cover almost circular regions, it is a good idea to make use of the available satellite resources in places where coverage is obtained via land base stations when it is necessary.
Once the decision for designing a multi-tier cellular network is made, it is also possible to exploit the advantages of the existence of multiple cellular layers. Then, when the resources of one layer is completely used, the calls arriving for that layer may be directed to other layers. This would help to reduce the probabilities of call blocking and dropping. In order to realize such a system, the placement of the base stations should not be arbitrary. It is a good practice to let the base station locations overlap where necessary and to choose the radius of larger cell such that the larger cell includes an integer number of smaller cells.
The design approaches overlap in some of the works available in the literature [40, 41]. The multiple layers are organized as described above. The overflow of calls that are not serviced in one layer to the others occur from smaller cells to the larger ones. The reverse overflows are not allowed in those approaches. The overflow decision can be done deterministic or probabilistic. The systems incorporate also the guard channels in each layer to give priority to the handoff calls.
In [40], Hu and Rappaport describe the system and give analytical results for a set of different parameters. The choice of parameters aims to present the performance of the system under different conditions. The efforts in [41] are aimed at the optimal spectrum partitioning once the system is set up. It is a simplified version of the system that is described by Hu and Rappaport and it makes use of mobility models of the mobile terminals while determining the system load. None of the mentioned works present how a system should be designed satisfying certain other constraints. Other interesting approaches in multi-tier network design can also be found in [42-44]. In [42], the aim is to design a minimum cost multi-tier cellular network. The call and handoff arrival rates are assumed to be known. [43] focuses on the cluster planning in a two-tier cellular network. The frequency planning and performance measures of the designed system is also presented. Finally, [44] deals with the resource allocation and media access control for a wireless multi-tier ATM network.
3.	PROBLEM DEFINITION
The purpose of this thesis is to design a minimum cost multi-tier cellular network with call overflow and guard channels that satisfy certain performance constraints. The idea of multi-tier cellular networks with overflow and guard channels is presented in [40]. The work presents the performance of the system for several configurations. In this thesis we worked with a similar system structure and tried to determine the parameters that describe the multi-tier cellular network rather than giving the performance measures once these parameters are supplied.
3.1	Assumptions
In majority of the cellular network design studies, several assumptions are necessary for calculating the performance of the system in a reasonable time.
The first assumption is about the mobile terminal classes. It is assumed that there are two classes of mobile terminal users. The high mobility class represent the mobile terminals that are used in cars and other vehicles. The low mobility class is made up of users that are primarily pedestrians. The speeds of the mobile terminal users are exponentially distributed with means vf and vs respectively.
The target is to design a high performance cellular network that will cover a large area like an entire city. Therefore it can be assumed that the distribution of the mobile terminals is even over the entire area, though with different rates. Furthermore, it is also assumed that the mobile terminals may move in any direction with equal probability. This assumption is valid both for high and low mobility classes.
The call duration is also exponentially distributed with mean 1/Ut. The call duration has the same distribution for both mobility classes. The time spent in a cell, which is called dwell time Ud, depends on the speed and trajectory of the mobile terminal as well as the shape of the cell. The cells are assumed to be hexagonal in general. However, for easy calculation of the dwell time, the cells are assumed to be circles. If the radius of a cell is r and the average speed of the mobile terminal is v, then the dwell time can be calculated as [41]:
 					  (3.1)
The call arrivals to the cells follow a Poisson distribution regardless of the mobility class. The mean rate for the call arrivals are determined by the mobile terminal density and the mean call generation rate of the individual mobile terminal users. The distribution for the high and low mobility terminals differ only in the mean rates.
There are also some assumptions regarding the communication network. It is assumed that the fixed network part is designed according to the results of the wireless part. The interconnection network has to have the ability of carrying the offered traffic and should be optimized in terms of communication performance. Hence the internal blocking cases, where the communication terminates or is affected due to congestion in the fixed network, is not considered.
The area that has to be covered should have uniform physical characteristics. This ensures that the required signal to interference ratio is almost constant over the entire area. So, the same cluster size can be used without any further consideration and for both tiers in the network. The signal to interference ratio may (and surely will) fluctuate, but the fluctuations should not so large that the cluster size has to be changed.
The antennas for both layers may be located at the same locations. Even in those cases the cost of setting up a microcell and a macrocell do not change. The base stations or the MSCs should also be capable of distinguishing the mobile terminals belonging to low mobility class and high mobility class. The distinction should be performed by using a threshold value. This threshold value can be chosen as the mean of the mean arrival rates.
3.2	System Description
The network to be designed is a two-tier cellular network. The cells of the lower tier are called microcells and their radii are smaller than those of the cells of the upper layer. Upper layer cells are called macrocells. The macrocells cover an integer number of microcells. Hence at the places where macrocell base station antennas are located, there are also other microcell base station antennas. Furthermore, the radius of the macrocells are constrained to be an odd integer multiple of the radius of the microcells. Hence the ratio of the radii, where R represents the radius of the macrocell and r the radius of the microcell, must satisfy:
				         (3.2)
Therefore, a macrocell can only cover 1, 7, 19, 37, 61, 91, 127… microcells. The calculation of these numbers follows an iterative formula. Hence the number of covered microcells Ni when R/r = i can be expressed as:
			         (3.3)
The total channel spectrum is divided by the cluster size into channel sets. Furthermore, each channel set is then divided among one microcell and one macrocell. This means that if the microcells has one less channel, then that channel will be used by the macrocells. The splitting of the channel sets are done during the design and is not changed afterwards. After the splitting of the channel sets some of the channels will be assigned as guard channels. Those channels are only used by the handoff calls; the new calls may not use the guard channels. The number of guard channels cannot be changed once the system is operational.
The arriving calls are serviced as follows:
The mobility class of the mobile terminal is determined. The calls of the slow MTs are primarily served by the appropriate microcells. When a new call arrives, then channel which is not used is assigned to that call if there is still channels available which are not guard channels. If only guard channels are available, then the new calls are overflowed to the macrocell that covers the microcell as overflowed new call. The handoff calls belonging to slow mobility terminals are serviced by the microcells if there is any kind of channel available. If all channels are occupied then the call is overflowed to the respective macrocell as overflowed handoff call. If a call, new or handoff, cannot be serviced by the microcell, then it is overflowed without any exception to the macrocell level. Figure 3.1 shows schematically how the calls are serviced and which order is followed in serving them.

FIGURE 3.1  Call Service Pattern
In the macrocell level, all the calls of the high mobility terminals and the overflowed calls are serviced. Once the calls reach the macrocell level, they are not differentiated according to their mobility classes. Therefore, the handoff calls of the high mobility class terminals and the overflowed handoff calls are treated equivalently. A similar rule applies also for the new calls. New calls may not use the guard channels upon their arrival. If no non-guard channel is available, new calls are blocked out of the system. The handoff calls that arrive to the macrocells may use any of the available channels. If also no guard channel is available, then the handoff calls leave the system forcefully.
In order a call blocking for the low mobility terminals to happen, all the channels that are not guard channels in a microcell-macrocell pair has to be in use. For the high mobility calls, it is enough to have the non-guard channels to be in use in the macrocell. The difference between the call blocking and dropping is that the calls are dropped after they enter the system. Since handoff calls have also advantage of being allowed to use the guard channels, call dropping rates are far less than the call blocking rates.
No matter whether new or handoff, the high mobility calls may not use the channels of the microcells. The calls belonging to the low mobility classes cannot return to microcell level even if channels become available in the microcells. Hence the flow of traffic between the layers has only one direction; from microcells to macrocells.
3.3	Constraints and Parameters
The problem is to design a two-tier cellular network at lowest cost. If one lets the performance of the system to become worse without bound, then the system setup cost would be zero. In that case, the system would consist of no base stations and the cost would be minimized. But then the call blocking probability would be 1.0, which is not acceptable. Therefore, minimum acceptable performance thresholds must be set for the system. 
The performance parameters are chosen to be call blocking rate and call dropping rate. Any solution is said to be feasible as long as it is in accordance with system description and the probability of call blocking and call dropping is below the specified thresholds. The values for the system parameters are in the order of 10-2 to 10-3 for the call blocking and for the call dropping 10-3 to 10-4.
For the system to be designed, some parameters describing the traffic pattern and the thresholds should be provided. These parameters cannot change the whole picture but allow the system to behave differently in the framework of the predefined models. The parameters that should be provided are as follows:
In order to describe the mobility, the average speeds of high and low mobility users are provided. These are denoted as vf and vs respectively. There are also some other parameters that have to be expressed implicitly. The mobile terminal density of both classes and the individual call arrival rates are represented in the call generation density parameters. For both mobility classes, two values indicating the mean value of the calls generated per second per m2 is provided. For completing the traffic generation patterns, the mean call duration is also given.
The effect of the physical environment and the requirements of the devices are reflected in the cluster size parameter. The cost of the system is the sum of the costs for each cell created in the system. The cost of the cells are dependent on the cost of the base station setup. Therefore, unit costs for the microcells and macrocells are also necessary parameters. 
In addition to these parameters, the total area to be covered is also supplied so that the total system cost can be calculated. Although the number of the microcells and macrocells that would be necessary to cover the given area depends on the shape of the area, it is assumed that these values are independent of the shape since the area in question is “large” compared with the area of microcells and macrocells. All input parameters are summarized in Table 3.1.
TABLE 3.1  User Supplied Parameters
Parameter	description	
vs	Mean speed of low mobility users	
vf	Mean speed of high mobility users	
SAm2	Call arrival rate per second per m2 for low mobility terminals	
FAm2	Call arrival rate per second per m2 for high mobility terminals	
1/Ut	Mean call duration	
C1	Macrocell cost	
C2	Microcell cost	
A	Total area	
CS	Cluster size	
Chtotal	Total number of available channels	
p	Radius increase/decrease factor	
cr	Cooling rate	
Pb,max	Maximum allowable call blocking probability	
Pd,max	Maximum allowable call dropping probability	

There are six decision variables for this problem. First of all, the cell radii for both tiers are calculated. Next decision variable is the partitioning of the channel sets. The number of channels that will be assigned to each microcell and to each macrocell is given among the results of the algorithm. Furthermore, the guard channel numbers for microcells and macrocells are also specified. Actually, once the cell radii are calculated the system cost is also determined. Hence only two of the decision variables are necessary for the cost calculation. The remaining decision parameters are used to implement the system. The decision parameters are summarized in Table 3.2.
TABLE 3.2  Decision Parameters
Parameter	description	
C	Total system cost	
Ch1	Number of channels reserved for each microcell	
Ch2	Number of channels reserved for each macrocell	
G1	Number of guard channels reserved for each microcell	
G2	Number of guard channels reserved for each macrocell	
R	Radius of a macrocell 	
r	Radius of a microcell	

Because of the presence of several decision parameters, the design problem in hand is a difficult one. Although it will be described in detail in the next section, the solution for the given problem is obtained using the Simulated Annealing neighborhood search method [6]. The parameters specific to the SA algorithm are the cooling rate and the radius increase/decrease factor. Their description is left to the next section.
3.4	Problem Formulation
The minimum cost two-tier cellular network design problem can be formulated as follows:
				 (3.4)
subject to the constraints
					    (3.5)
					    (3.6)
				      (3.7)
				      (3.8)
				          (3.9)
The values C1 and C2 corresponds to the cost of setting up a macrocell and a microcell respectively. C is the total system cost. N1 and N2 are the number of the microcells and macrocells respectively. R and r are the radii of microcells and macrocells respectively. While minimizing the total system cost, the resulting probabilities for call blocking and call dropping should stay below the provided limits as expressed in Formulae 3.5 and 3.6. The calculation of the of the call blocking and dropping probabilities are explained in Section 4.1.
4.	SOLUTION TECHNIQUES
In order to solve the problem mentioned in the last section primarily Simulated Annealing is used. The results obtained using the SA based algorithm are compared with the results obtained with two other methods. These methods are the Greedy Search (GS) algorithm and Generate and Test (GAT) algorithm. In all of the algorithms, the calculation of the of the cost and methods used for feasibility check are the same. This section is devoted to the solution techniques as well as the description of the cost and performance calculation procedures.
4.1	Calculation of Cost and Performance Measures
The calculation of the cost of the designed system is rather easy. Once the cell radii are determined, the areas of the cells are calculated. Then, the number of microcells and macrocells that would cover the given total area is determined. If the resulting system should have N1 microcells and N2 macrocells with C1 and C2 as their respective unit costs, the total cost C is simply computed as:
					(4.1)
The performance evaluation of this system is a more difficult task. First of all, the system is divided into two parts that can be examined one after the other. The first part corresponds to the microcell layer of the system. This part of the system is represented with a Markov Chain (M/M/s/s system) [45]. In this representation the state corresponds to the number of calls served by a microcell. The arrivals to the system is calculated by multiplying the mean call generation rate per second per m2 by the area of the microcell and denoted as 1s. The dwell time of the low mobility users in the microcells Ud1s are calculated according to Formula 3.1. A sample Markov chain for a microcell with five channels and two guard channels are presented in Figure 4.1.

FIGURE 4.1  Sample State Transition Diagram for Microcells (5/2)
The steady state probabilities Pi can be calculated using Erlang-B formula [45] as shown in Formulae 4.2 - 4.4.
			        (4.2)
		   (4.3)
				     (4.4)
In order to be able to apply Erlang-B formula, the asymptotic handoff rate 1sh should be calculated. The calculation of the 1sh is as follows: Start with an arbitrary value of 1sh and calculate the steady state probabilities. Calculate the 1sh value using Formula 4.5. Then replace the 1sh value with 1sh. Repeat this process until 1sh becomes equal to 1sh [40].
				(4.5)
Once the steady state probabilities are calculated, the overflow traffic is determined. First of all the probabilities for call blocking Pb1 and call dropping Pd1 are calculated. For the microcell level, Pd1 equals to the steady state probability Pch1. Pb1 on the other hand equals to the sum of the steady state probabilities for states i=Ch1-G1 to Ch1. If a macrocell covers N microcells, the total overflow new call and overflow handoff call traffic entering a macrocell (os and osh) can be calculated as follows:
					(4.6)
					(4.7)
The second part represents the macrocell level. The states in macrocell level correspond to the numbers of high and low mobility users (i and j) serviced by a macrocell. The state transition diagram for a macrocell with five ordinary and two guard channels is shown in Figure 4.2.

FIGURE 4.2  Sample State Transition Diagram for Macrocells (5/2)
The variables 2f and 2fh are the arrival rates of the new and handoff calls of high mobility users to a macrocell respectively. 2sh is the arrival rate of the handoff calls of the low mobility users once they entered the macrocells. 1/Ud2s and 1/Ud2f are the dwell times of low and high mobility users in the macrocells. The values for 2fh  and 2sh  are calculated using the same method that is described for the microcell handoff rate determination.
The states of the macrocells build a two dimensional chain. The system is solved for the steady state probabilities Pij as described in [45]. For the real values of Pij the handoff arrival rates should be calculated using the iterative method that is described. When the Pij values are determined, the call blocking and call dropping probabilities for the macrocells (Pb1 and Pd1) are calculated as follows:
				        (4.8)
				        (4.9)
Finally, the overall call blocking Pb and call Pd dropping probabilities are calculated. The call dropping probability reflects the probability of a call being not serviced by the system after the communication session starts. The probability of having a call blocked is the product of call blocking rates of both layers for slow mobility users. For high mobility users, it is the call blocking probability of the macrocell level. So, the weighted average of the call blocking probabilities within the coverage area of a macrocell reflects the average call blocking probability of the system. If N is the number of microcells that fits into a macrocell, the call blocking probability is given by:
				(4.10)
The calculation of the call dropping probabilities for low and high mobility users are based on the following idea: First of all, the probabilities that the calls are serviced by a given layer are calculated. Then the probabilities that a call has to leave a layer is calculated. Then regarding all the possible scenarios the call dropping rates are calculated. These rates are designated as Pds and Pdf. Then the average call dropping rate is calculated based on the same idea presented in Formula 4.10. The details of these calculations can be found in [40].
4.2	Simulated Annealing Algorithm
The SA algorithm [6] is chosen because the problem in hand had multiple plateaus in the objective function. The mentioned plateaus are caused by the existence of decision parameters that do not change the cost of the system but affect its performance; namely channel splitting. The available channels are shared by two layers. The distribution of the channels affects the performance a lot. Not including channel splitting to the variables that will be subject with change in the algorithm increases the time complexity and is also unnecessary since it is determined by the algorithm successfully.
The algorithm starts with an initial feasible solution and makes random moves within the range of the neighbors that can be reached from the current solution. Each step in the algorithm corresponds to visiting a feasible neighbor. The costs associated with the neighbors are considered before really passing on to the neighbor. If the cost of the neighbor is less than or equal to the current cost, the move is accepted. Otherwise the move is accepted with a probability that decreases in time.

FIGURE 4.3  Pseudo-Procedure of SA Algorithm
Figure 4.3 shows the pseudo-procedure of the SA algorithm. The generation of the initial feasible solution is done by generating random radii for microcells and macrocells and by distributing the available channels among the tiers randomly. Actually what is done is, the microcell radius is indeed selected randomly. Then also another random odd integer number is generated for the R/r ratio. When r and R/r ratio are selected, macrocell radius R is determined. Another random number Ch1, which lies between zero and the number of channels in the channel set, is generated. Ch1 is selected for to be assigned to the microcells. The remaining channels are assigned to the macrocells. This generation continues until the first feasible solution is found. The feasibility check includes the determination of the guard channels since the cell radii and the channel splitting is done beforehand. 
While determining the number of guard channels, the following strategy is used. First of all, guard channel numbers are reset to zero. In the outer loop, the guard channel number is increased. The inner loop is devoted to the guard channel number of the macrocells. Fixing the guard channel number of the microcells, the number of guard channels of the macrocells are increased. The performance measures, call blocking and dropping probabilities, are calculated. They are compared with the given threshold probabilities. The algorithm stops and returns a positive value as soon as a feasible solution is found, where the feasibility check is done only on the call blocking and dropping probabilities. The remaining feasibility measures are guaranteed by the rest of the algorithm.
While the guard channel number for the macrocells is increased, the inner loop is exited and the number of guard channels for the microcells is increased, if the call blocking probability exceeds the given threshold. The reason for this is, if the guard channel number in the macrocells are increased further, only the call dropping probability is improved and the call blocking probability becomes larger. So there is no point in checking further configurations where there are more layer two guard channels. But since the effect of the guard channels in the microcell level cannot be predicted, the search continues with an increased number of guard channels for the microcells.
Another exiting criterion for the inner loop is reaching the total number of channels available for the macrocells. In both cases, the guard channel number of the microcells is increased as the guard channel number of the macrocells is reset to zero. If the number of guard channels is increased up to the number of channels reserved for the microcells and still no feasible solution is found, a negative value is returned to the calling function. Hence the configuration cannot be feasible.
The reason why the stopping criterion is updated after the determination of the initial feasible solution is explained later on. But it is worth to say a few words about the initialization of the temperature. After the initial feasible solution is found, all of its neighbors are generated and the cost differences are calculated. The mean of the absolute values of the cost differences are chosen as the initial temperature. This way, the scale of the temperature is not fixed and also not determined by the user. It is chosen such that the first neighbors are accepted regardless of their costs. So, changing the magnitude of the costs does not effect the performance of the algorithm. When the algorithm proceeds, the temperature T is updated using the cooling rate provided by the user. The temperature is updated after three accepted neighbors. Formula 4.11 gives the update rule. In this formula, every accepted neighbor is regarded as a time unit.
			   (4.11)
4.2.1	Neighborhood Structure
The system is represented by the parameters that are provided by the user, cell radii and channel splitting. Since the parameters provided by the user reflect the exterior characteristics of the system and cannot be changed, the neighbors of a system are determined by changing the decision parameters incrementally. The degree of the incremental moves are partly determined by the user.
First of all, the channel splitting can be changed. The incremental change is made by transferring one channel from microcells to macrocells or vice versa. Such changes have effect on the performance but not on the cost of the system. Therefore, they are always accepted by the algorithm. The routines that change the channel distribution are also controlling the feasibility of the channel transfers. So, no negative number of channels is produced. Neighbors generated by changing the channel distribution eases the changes in the cell radii.
The next change may be in the microcell radius. The microcell radius can be incremented or decremented by only a fixed percent value p, which is supplied by the user. For example, if p=0.05, then the microcell radius can be incremented or decremented by five percent only. No other value is used in the algorithm. The change in the microcell radius effects by the same percent value also the macrocell radius. This is of vital importance because the R/r ratio has always to be an odd integer. Most of the time, small changes in the microcell radius are not enough to change the R/r ratio to a valid integer when the macrocell radius is kept constant. Therefore, both radii are updated simultaneously in this case.
Since the R/r ratio is kept constant when the cell radius is incremented or decremented, another type of neighbor is generated by changing the R/r ratio. As can be predicted easily, the changes are in terms of adding or subtracting two from the current value. Again, no negative numbers are generated to provide feasibility. The changes in this ratio involve big cost differences. The fixed ratio values constitutes the plateau of the cost function. The SA algorithm is useful since it allows stochastically bad moves in terms of cost. So the ratio can be changed and also other combinations can be examined.
4.2.2	Stopping Criteria
The SA algorithm stops in four different cases. The first case is checked after the generation of the initial feasible solution. If all the neighbors are found to be infeasible during their generation, the algorithm does not proceed and tries to find another feasible solution.
Another stopping criterion is the number of successive neighbors that are accepted due to their costs but do not confirm with the call blocking and dropping constraints. If they exceed a certain threshold value, then the SA algorithm terminates, too. This situation is regarded as being not able to move out of a plateau. The threshold value is chosen to be 15.
The third criterion is the number of moves that do not change the cost of the system. The system may get blocked on a plateau, but it may be that two neighboring channel distributions confirm to the performance constraints. So the solutions oscillates between two solutions and the system may cool down without any improvement. Such cases are counted and the algorithm is terminated after 20 such moves.
Finally, as a precaution, the algorithm counts also the number of moves made since it started. The maximum allowable number of moves is set to be one thousand. Although it is claimed that the SA algorithms are independent of the starting point, in our implementation the algorithm is restarted unless the total number of runs reach one thousand. The best value recorded is the output of the total algorithm.
4.2.3	A Typical Run of SA Algorithm
The general behavior of the SA algorithm resembles the random search at the beginning and greedy search when the system is cooled down. Which of the mentioned techniques the SA algorithm is close to is determined by the cooling schedule. When cooled down too rapidly, the SA algorithm behaves like a greedy search algorithm. On the other hand, if the temperature is cooled down very slowly, the neighbors are selected almost randomly and the heuristic is close to a random search. This behavior is also recorded for the implemented version. Figure 4.4 shows the cost of the solutions during a typical run of SA algorithm.

FIGURE 4.4  A Typical Run of SA Algorithm
The iteration numbers in the range one to 90 show that the algorithm accepts almost every move. Afterwards in the next 30 moves the cost is improved reaching possibly another plateau. That plateau is left after 190 moves and the system starts to stabilize. The small oscillations around the cost value 200000 indicates this behavior. It is highly possible that the plateaus in Figure 4.4 correspond to different R/r ratios. When R/r ratio changes, the algorithm heads directly to another range where the cost does not change too much.
4.3	Greedy Search Algorithm
In order to compare the results that are obtained by the SA algorithm, another neighborhood search algorithm is also implemented. This is the Greedy Search (GS) algorithm. The greedy search algorithm is most of the time used for problems that have a convex cost function. If the cost function is not convex, like in this case, then the GS algorithm is run starting from different point of the feasible solution space. When the cost cannot be improved any further, then the algorithm is restarted.
Setting the initial temperature in the SA algorithm equal to zero yields in the GS algorithm. The distinction between them is that the stopping criterion for the GS algorithm is not reaching to 1000 accepted moves. In order to set the approximate running time of SA and GS algorithms, also the moves that are not accepted but for which the performance is calculated are counted. The mean value turned out to be around 1500 for the SA algorithm. Therefore, the stopping criterion for the GS algorithm is chosen as 1500 performance calculations. If they are not adjusted such that they have comparable running times, then the quality of the solutions cannot be compared. Then the number of feasible moves lies around 620.
The Figure 4.5 shows the values obtained during a run of the GS. It is easy to see that the performance of the GS algorithm mainly depends on the starting points. If the starting point is not very good, then the results are not of high quality. In order to obtain good results, the runtime should be increased so that more initial points are selected and examined.

FIGURE 4.5  A Typical Run of GS Algorithm
4.4	Generate and Test Algorithm
The aim of GAT algorithm is to traverse the feasible solution space randomly. As the number of the generated solutions increases, the optimal solutions are obtained with higher probabilities. They can be used as benchmarks for heuristic algorithms. There is no rule that relates the generation of the successive points in the solution space. For the generation of the feasible solution the routine that calculates the initial feasible solution for the SA algorithm is used.
The number of accepted solutions are bounded with the value 5000. After 5000 random feasible solutions are generated the algorithm terminates. The solutions that are not feasible are rejected and do not appear in the solution list. Their number is almost four times the accepted solution number. Hence, in each run approximately 25000 solutions are generated, but only 5000 of them are accepted.

FIGURE 4.6  A Typical Run of GAT Algorithm
The GAT method is chosen as a statistical quality measure. The minimum, maximum and mean values obtained helps to have a feeling about the distribution of the costs of the feasible solutions. The solutions obtained with the SA algorithm are assumed to be very close, if not better, to the best solution obtained with the GAT algorithm.
Figure 4.6 shows the distribution of the results obtained in a typical run. Only 4000 of the results were used to plot the chart and the solutions that produced costs exceeding 5000000 are not shown. In this run, the worst feasible solution obtained had a cost of 12000000. The minimum value is around 200000. The horizontal line at the bottom of the chart displays this value. The mean for this run was 2250000 and the standard deviation was 2100000, which is close to the mean. These numbers should present the huge size of the solution space.
5.	COMPUTATIONAL EXPERIMENTS
In order to present the characteristics of the two-tier cellular networks, several computational experiments were carried out. First of all a sample problem and the corresponding solution is presented. Furthermore several groups of tests are performed. 
The first group of experiments deal with the effect of the isolated parameters on the objective function. For all of these parameters, the relationship between the parameters supplied to the algorithm and the cost of the system is compared. Furthermore the effects of the design decisions are questioned. Their effect on the cost is compared with the cost of the system in hand. The comparison is made by comparing the costs under different arrival rates.
The aim of the experiments in the second group was to observe the solutions of the SA algorithm in a large part of the parameter space. By doing so, the behavior of the two-tier systems is presented. The selected solution technique is compared with other alternative solution techniques and the single-tier systems.
The performance of the system under some unexpected increases in the call arrival rates are examined. The increase in the call arrival rates include calls generated by both mobility class users. The obtained results are presented graphically.
Lastly, the time complexity of the algorithm is estimated partially by experimental measurements and partially by analysis of the algorithms used in the solution technique. The results of this analysis is also presented in this section.
5.1	Base Problem
In order to prepare the problem sets for comparison, a sample problem is chosen as the base problem. This base problem reflects a typical case that can be faced when designing a cellular network. We tried to choose the parameters describing the system characteristics and requirements such that they are not very far from the real life. Although some of the parameters may be over- or underestimated, we aimed to make pessimistic choices where necessary. Hence the performance of the system is supposed to be better in the real life cases.
The experiment sets are prepared by changing the values of the given system one by one. If the effect of one parameter on the obtained results is desired, then all parameters except for the parameter in question are selected equal to the parameter values of the base problem. Only the parameter in question takes different values. Therefore the changing parameters and their values are used to describe an experiment problem. Other parameters can be taken from Table 5.1.
An entire city is chosen as the target area to be covered. The entire coverage area is chosen large so that the assumptions about the uniform distribution of the mobile terminals and their uniform movement is satisfied. Therefore the total area to be included as coverage area is chosen to be 5000 km2. This area is large enough to cover an entire city of rectangular shape of size 100 km x 50 km.
The mean speeds of both mobility classes are chosen to be 1 m/s (3.6 km/h) and 8 m/s (28.8 km/h) for low and high mobility classes respectively. The first value corresponds to the mean walking speed of a pedestrian and the second one to the mean speed of a car in the city traffic. Furthermore the mean call duration is chosen as 100 seconds. This duration is rather short when compared with the mean call duration of the conventional telephone services. Although the mean call duration may take different values for different cities and countries, it is comparable with actual values.
The mean call arrival rate from the low mobility users is 8x10-8 calls per second per m2. This value corresponds to approximately 3500000 calls in 24 hours in a city of size 500 km2. The call arrival rate from the high mobility users is chosen as 25 percent of the arrival rate from the low mobility users.
The value for the cluster size is seven and this choice is very typical [5]. The total number of channels available is chosen to be 150. For this base problem, the cost for setting up a microcell and a macrocell is chosen as 10 and 30 cost units respectively. The maximum allowable call blocking and call dropping rates are 0.01 and 0.001 respectively. All these parameters are summarized in Table 5.1.
TABLE 5.1  Parameters of the Base Problem
Parameter	Value in the base problem	
vs	1 m/s	
vf	8 m/s	
SAm2	8x10-8per second per m2	
FAm2	2x10-8per second per m2	
1/Ut	100 seconds	
C1	10 Cost Units	
C2	30 Cost Units	
A	5000 km2	
CS	7	
Chtotal	150	
Pb,max	0.01	
Pd,max	0.001	

The resulting solution that is obtained from the SA algorithm gives all the necessary decision parameters needed to implement the two-tier cellular network. The values of the decision parameters are presented in Table 5.2.
TABLE 5.2  Values of Decision Parameters for the Base Problem
Parameter	Result of SA ALGORITHM	
C	152060 Cost Units	
Ch1	8	
Ch2	13	
G1	0	
G2	1	
R	1275 m	
r	425 m	
R/r	3	

According to the values obtained, the system will consist of macrocells and microcells that have a R/r ratio of three. This corresponds to the fact that a macrocell covers seven microcells. Another implication is that the system will consist of 10643 microcells and 1521 macrocells covering the same area. When 150 channels are distributed to all cells in a system with cluster size of seven, each microcell-macrocell pair gets 21 channels. These channels are split such that each microcell gets eight and each macrocell gets 13 channels. In the microcell level no guard channel is needed whereas one channel in each macrocell should be reserved as a guard channel.
5.2	Effect of Some Parameters and Design Decisions
In this section, the effect of some parameters on the cost of the two-tier cellular networks are examined in detail. The results are presented as charts. Furthermore some design decisions are also assessed using the same method. In all of the calculations, the input parameters are the parameters for the base problem. Only the parameter, for which the examination is done, is changed. The names of the parameters that are examined appear in the subsection headings.
5.2.1	Effect of Call Arrival Rate
The effect of the call arrivals on the cost is examined. The call arrival rates are examined separately. Based on the parameters of the base problem, first the call arrival rate of the low mobility platforms is increased from 5x10-8 to 15x10-8 calls per second per m2 with a step size of 1x 10-8 calls per second per m2. The results obtained are represented in Figure 5.1 graphically.

FIGURE 5.1  Low Mobility Call Arrival Rate vs Cost
The results obtained show that the effect of the low mobility call arrival rates on the cost is almost linear around the given parameters. The increase in the traffic is directly reflected to the cost. We believe that the cost will increase with a higher acceleration when the limits of the system is approached. However the obtained results show that the relationship within the range of typical parameters is linear.
Secondly the call arrival rate of the high mobility platforms are examined. The remaining parameters are as in the base problem. The arrival rates are increased from 0.5x10-8 to 5x10-8 calls per second per m2 with a step size of 0.5x10-8 calls per second per m2. The resulting graph is shown in Figure 5.2.
Disregarding the first point of the chart, the resulting graph is again pointing at a linear relationship between the high mobility call arrival rate and the system cost. This result is valid again for the given set of other parameters and the range in which the high mobility call arrival rate changes. Beyond the mentioned limits the call arrival rate and cost may have another type of relationship.

FIGURE 5.2  High Mobility Call Arrival Rate vs. Cost
As a conclusion it can be said that the system cost increases almost linearly with the increasing rate of the arrival rate. The cost of the system increases as the offered load increases. The reason for this is the increasing number of microcells and macrocells. The radii become smaller and more cells fit into the coverage area in order to increase the number of channels available in the system. This way, the offered traffic can be handled without violating the performance constraints. Hence, the cost of the entire system increases. The main distinction between both mobility classes is the slope of the linear relationship. The slope of the second graph is approximately 4.5 times the slope of the first graph. Hence the two-tier cellular network costs are more sensitive to the changes in the high mobility call arrivals.
5.2.2	Effect of Mean Speeds
The second parameter to focus on is the mean speed of both mobility classes. The speed changes of both mobility classes are examined separately. The first parameter that is changed is the mean speed of the low mobility users. Keeping the other parameters as in the base problem, the mean speed of the low mobility users are increased from 0.25 m/s to 2.5 m/s with a step size of 0.25 m/s. The resulting graph is shown in Figure 5.3.

FIGURE 5.3  Mean Low Mobility User Speed vs. Cost
The cost of the system increases when the mean speed of the low mobility users increases. However this increase starts with a higher slope for small values of mean speed and becomes less and less when the mean speed increases. This behavior may be an indication of the fact that the system starts to benefit from the second tier of the network as a place to forward the excess calls instead of decreasing the cell radii and increasing the channel amount per m2.
Similarly, the mean speed of the high mobility users are examined. Again keeping all parameters as in the base problem, the mean speed of the high mobility users is increased from 4 m/s to 22 m/s with 2 m/s steps. The results of this experiment is presented in Figure 5.4.

FIGURE 5.4  Mean High Mobility User Speed vs. Cost
With the increase of the mean speeds, the system cost again increases. In contrast to the mean speed increase of the previous case, the rate of the cost increase does not diminish with the increased mean speed of the high mobility users. In fact the mean speed/cost relationship seems to be linear. This can be regarded as an evidence of the fact mentioned before.
Since the arriving high mobility calls cannot be overflowed to another tier, the system should react with incorporating more resources by paying more. In the previous case, the system could use the excess resources available in the upper tier. In this case, the excess traffic should be handled again within the same tier. Hence, the performance requirements can be met only if the number of available channels per unit area is increased. This is done by decreasing the cell radii and increasing the system cost. It can also be concluded that increases in the mobility do not effect the system setup cost too much, since the users change cells equally likely and the lack of resources are temporary.
5.2.3	Effect of Mean Call Duration
The effect of mean call duration on the cost of the system is examined by a series of experiments. In these experiments, the mean call duration is increased from 50 seconds to 150 seconds with 50 second steps. The results are demonstrated in Figure 5.5.

FIGURE 5.5  Mean Call Duration vs. Cost
The effect of the mean call duration is reflected to all mobility classes. Therefore a uniform increase in the traffic that should be carried is in question. The reflection of the mean call duration to the cost is linear for the given set of parameters. This indicates that the increasingly traffic load can only be compensated by adding more resources into the system because longer call duration causes the system resources to be locked by communication sessions longer. Then it is less likely that the calls entering cells find any free channels. Therefore, number of channels per unit area should be increased by decreasing the cell radii, hence, increasing the number of cells in the system.
5.2.4	Effect of the Call Blocking Threshold
The maximum allowable call blocking probability is one of the constraints of the problem. In order to demonstrate the effect of maximum allowable call blocking probability, its value is decreased starting at 0.015 down to 0.001 with a step size of 0.001. All other parameters are as in the base problem. The results of this experiment are shown graphically in Figure 5.6.

FIGURE 5.6  Threshold Probability for Call Blocking vs. Cost
In the graph of Figure 5.6, the effect of call blocking threshold is demonstrated with its unique effect on the cost. As the constraint gets more strict, the cost of the system goes over to different plateaus. The first plateau is between blocking probabilities 0.015 and 0.012 around 149000 unit costs. The next plateau is between probabilities 0.011 and 0.008 and it lies around 155000 unit costs. The final observable plateau is around 157500. The corresponding probability range is between 0.007 and 0.002. After this point, the probability value goes probably to another higher plateau. So, it does not make any difference to choose a point belonging to a plateau. The value for maximum allowable call blocking threshold should be chosen such that it is as strict as possible within the limits of a plateau, since relaxing the constraints has no effect on cost as long as one stays on a plateau.
The reason for this behavior can be that the system has to be in accordance with two constraints that are closely related. When the system has to support a certain call dropping rate, then increasing values of call blocking rate can be met automatically. After certain threshold values, the cell radii are adjusted to support the same dropping rate, where again a range of call blocking rates are supported automatically.
5.2.5	Effect of the Call Dropping Threshold
The next parameter to be inspected is the maximum allowable call dropping threshold. The value for this threshold is decreased from 0.01 to 0.001 with a step size of 0.001. The resulting values are shown in Figure 5.7.

FIGURE 5.7  Threshold Probability for Call Dropping vs. Cost
For a given call blocking rate, the call dropping rate has no effect on the cost until it reaches a certain value. Only if it is set to be smaller than that value, the cost of the system starts to increase. For threshold values larger than that value, the system cost remains constant. The mentioned break point is approximately at 0.004 for this case. The break point is set primarily by the call blocking rate. If that call blocking rate is satisfied, then the call dropping thresholds that are larger than the break point are satisfied anyway.
This behavior has a similar explanation as the previous case. For a certain blocking rate, several dropping rates may be supported. Once this threshold is exceeded, then the cell radii are adjusted such that more system resources are available to meet the call dropping constraints. Hence, the cost of the system starts to increase.
5.2.6	Effect of the Area
The decision parameters needed to physically construct the system are the channel allocations and the radii of the cells in both layers. Since the size of the area only effects the number of cells necessary, its effect is only on the cost. The relationship is linear and the decision parameters are not effected. This case is shown in Figure 5.8. For the given set of problems, the area to be covered is selected to range from 500 km2 to 5000 km2 with a step size of 500 km2.

FIGURE 5.8  Coverage Area vs. Cost
5.2.7	Effect of Cluster Size
The effect of the cluster size on the system cost is directly related with the partitioning of the channels available. The allowable values between 3 and 27 are tested for optimal design results. The results are presented in Figure 5.9.
It is clearly observable from the figure that the smaller the cluster size is the cheaper will be the system. If more channels per cluster can be reserved, then the performance of the system increases. Since the performance limits are set beforehand, the system can be relaxed to behave worse, but staying within the constraints. Hence the system cost is decreased. Since neighboring allowable values may take different values, a general tendency is hard to extract.

FIGURE 5.9  Cluster Size vs. Cost
5.2.8	Effect of Number of Available Channels
It is of vital importance to determine the number of channels that are needed to satisfy certain performance limits and still stay in certain budget constraints. Although there is no budget constraint in the definition of the problem, it can easily be incorporated. The number of total available channels are increased from 75 to 300 with 25-channel increments to demonstrate the effect of the channels on the system setup cost. Figure 5.10 summarizes the results.
Increasing the number of available channels decreases the system setup cost. The gain per unit increase in the number of channels is high where the channel numbers are small. The increase decreases for larger numbers of available channels. The cost differences indicate the need for additional channels to relieve the system. When the channel number in the system is already high, then the need for additional channels are decreasing. This is also reflected in the cost of the system.

FIGURE 5.10  Number of Available Channels vs. Cost
The explanation of this curve may be as follows. When additional channels are added into the system, then it becomes easier to satisfy the performance constraints. After a certain level, it becomes unnecessary to add additional channels to the system since the system has already enough resources. Hence, the effect of additional channels becomes less.
5.2.9	Effect of Overflow
One of the design decisions was to allow the overflow of the calls from the lower layer to the upper layer. This decision is supposed to improve the performance of the system. In order to demonstrate this behavior, tests are performed. The tests performed in Section 5.2.1 is also applied to the sample system with no overflow allowed. The results are presented in Figure 5.11 and 5.12 together with the results shown in Section 5.2.1 for the system that allows overflow. Figure 5.11 presents the effect of the increase in low mobility call arrival rate. Figure 5.12 presents the effect of the increase in high mobility call arrival rate.
In both cases the system with overflow yields better solutions in terms of cost. The gain in cost obtained by allowing the calls to overflow to upper layer is almost constant for both cases. There is only a small increase in the cost gap towards the end of the values tested. Hence these results justify the use of overflow mechanism.

FIGURE 5.11  Low Mobility Call Arrival Rate vs. Cost (Overflow Comparison)

FIGURE 5.12  High Mobility Call Arrival Rate vs. Cost (Overflow Comparison)
5.2.10	Effect of Guard Channels
Another design decision is to employ guard channels. This decision is supposed to improve the performance of the system. In order to demonstrate this behavior, tests are performed. The same strategy as in the Section 5.2.9 is used also here to demonstrate the quality of result. Figure 5.13 presents the effect of the increase in low mobility call arrival rate. Figure 5.14 presents the effect of the increase in high mobility call arrival rate.
It is observed that there are savings obtained by employing guard channels. In the examination of the high mobility call arrivals, the difference turns out to be low. When all decision parameters are checked, it is easy to observe that no guard channel is reserved for the microcells and at most two (usually one) guard channel(s) are (is) reserved in the macrocells. Hence their use is not very mandatory.

FIGURE 5.13  Low Mobility Call Arrival Rate vs. Cost (Guard Channel Comparison)

FIGURE 5.14  High Mobility Call Arrival Rate vs. Cost (Guard Channel Comparison)
5.2.11	Effect of Second Tier
One of the most fundamental design decisions is to have a second cellular tier on top of the microcell level. In order to show the effect of the added second level, several problems based on the base problem are created. These problems are also used in Section 5.3 and are explained there in detail. Table 5.3 shows the results obtained for single- and two-tier cellular networks. All the parameters are taken from the base problem except for the parameter specified in the description column.
TABLE 5.3  Costs of Single- and Two-Tier Systems for Different Problems
Prob. No	Description	Two-tier	Single-tier	
1	Base Problem	152060	125430	
2	Area=1000km2	30990	25110	
3	Area=50km2	1550	1290	
4	Slow Low Mobility Speed=0.25m/s	147000	129540	
5	Fast Low Mobility Speed=3m/s	157200	125340	
6	Slow High Mobility Speed=5m/s	149900	142980	
7	Fast High Mobility Speed=20m/s	162440	125250	
8	Low Mobility Arrival Rate=2e-8	112590	84900	
9	Low Mobility Arrival Rate=1.5e-7	195400	219540	
10	High Mobility Arrival Rate=5e-9	76990	119010	
11	High Mobility Arrival Rate=8e-8	489980	214560	
12	Frequent Call Arrivals	646790	477540	
13	More High Mobility Users	218300	82110	
14	Short Duration=40sec	54580	47400	
15	Long Duration=200sec	356570	251520	
16	Loose Performance Limits	124360	106530	
17	Strict Performance Limits	161180	126930	
18	Very Strict Performance Limits	172760	135990	
19	Cluster Size=3	47690	62670	
20	Cluster Size=19	1054040	785640	
21	Same Unit Price	121960	42350	
22	Price Ratio=1:5	181300	218300	
23	No Macrocell Setup Cost	37500	41770	

The result for the two-tier system is obtained using the SA algorithm. The algorithm for single-tier cellular network is derived from the SA algorithm for two-tier cellular network. The only manipulation performed is to remove the overflow concept and the microcell level. Hence the system is capable of giving service to both mobility classes and employing guard channels. Since the decision parameters are one cell radius and the guard channel number in each cell, the algorithm behaves like greedy search. Since the cell radius is decreased or increased by a fixed percentage value, the optimal cell radius is determined by allowing the system go to worse solutions and come back. A successive pair of increases and decreases in the cell radius does not yield in the original radius r. This case is presented in Formula 5.1.
				      (5.1)
The product (1+p)(1-p) is not equal to one if p is different than zero. Hence the optimum radius is obtained with finer step sizes. Hence the solution technique for singe-tier system is similar to but different than greedy search.
In Problems 1, 2 and 3 the area is changed. The growth of the system costs is linear, in accordance with the results of Section 5.2.6. The single-tier cellular network yields in approximately 17.5 percent cheaper solutions than the solutions for the two-tier cellular network. This ratio is equal for all three problems presented here, because the systems requirements are equivalent in all these problems and the area has no effect on the solution.
Problems 1 and 4-7 deal with the change of the mean speeds of the mobile terminals. The single-tier systems turn out to be cheaper for the problems in hand. The single-tier solutions become cheaper when the mobility is increased since, they tend to increase the cell radii to decrease the number of handoffs during a call. Meanwhile, the decrease in the cell radii also decreases. This is observable in the cost differences between the moderate and fast mean speeds and between the slow and moderate mean speeds for both mobility classes. The smaller the cell radii are the larger is the system cost. The first differences are considerably smaller than the second ones, hence the changes in the cell radii become smaller. If the tendency continues, the single-tier system will no longer be able to satisfy the performance constraints. Another observation is that the cost difference between the single-tier and two-tier systems decreases as the mean speeds decrease.
In Problems 1 and 8-13, the call arrival rates of both mobility classes are changed. The single-tier system has a lower cost in all problems but Problems 9 and 10. In Problem 9, the low mobility call arrival rate is large. In Problem 10, on the other hand, the high mobility call arrival rate is very small. Since Problem 13 has both values large and the single-tier system has lower cost, it can be concluded that the arrival rate ratios play an important role in determination of the system costs. If the ratio of the low mobility call arrival rate to the high mobility call arrival rate is large, then the cost of the two-tier system is lower than the cost of the single-tier system. In Problem 1 and 13, these ratios are 3.75 and 4 respectively. In Problems 9 and 10, same ratios are 7.5 and 16 respectively. Hence, in the vicinity of these parameters, the mentioned ratio should be at least around 8 so that the two-tier system can be cheaper than single-tier system.
In Problems 1, 14 and 15, different values of call duration are tested. As the solutions for two-tier network indicate, as the call duration becomes longer, the system cost increases. This result is in accordance with the results of Section 5.2.3. The same rule applies also for the single-tier systems. However the costs stay well below the costs of two-tier systems. Hence the call duration does not change the cost relationship between the competitor systems.
In Problems 1 and 16-18, the maximum allowable call blocking and dropping probabilities are changed. The two-tier system and the single-tier system have similar behaviors. When the performance requirements are tight, the cost of the system increases, but the cost of the two-tier system stays above the cost of the single-tier system. 
In Problems 1,19 and 20, when the cluster size is changed, the single-tier system turns out to be cost effective when the cluster size is high. For the case where clusters consist of three cells, the two-tier cellular network becomes cost effective. For others, the single-tier networks turns out to be cheaper.
In the remaining three problems, different ratios of the microcell and macrocell setup costs are tested. When the system costs for different price ratios are compared, it turns out that the single-tier system becomes more expensive than the two-tier system when the price ratio is above 1:5 as in Problem 22. On the other extreme, where the macrocell setup cost is zero as in Problem 23, the ratio becomes infinity, and the two-tier system becomes again cost effective. Therefore, one can conclude that the two-tier systems cost less if the one of the cell setup costs is much larger than the other one.
We also focused on the cases where the high mobility call arrival rate decreases and where the macrocell setup cost decreases. For these two cases, the performance of the two-tier and single-tier  cellular network costs are compared.

FIGURE 5.15  High Mobility Arrival Rate vs. Single- and Two-Tier Costs
In order to see the effect of the decreasing high mobility call arrival rates, we experimented with the systems, where the arrival rate decreases from its value in the base problem with 2.5x10-9 calls per second per m2. This is done in order to increase the ratio of the low mobility call arrival rate to the high mobility call arrival rate. For values that are less than 1.25x10-9 calls per second per m2, the two-tier system setup cost becomes less than the single-tier system cost. The results are in accordance with the results that are obtained for the problems presented in this section. As expected, the system cost decreases when the load on the system decreases. But when the two-tier system has a cost graph with a more negative slope. Hence, the two-tier system is indeed cost effective for the problems for which the high mobility call arrival rates are far less than the low mobility call arrival rate. The cost curves for both systems are presented in Figure 5.15.

FIGURE 5.16  Macrocell Setup Cost vs. Single- and Two-Tier Costs
In order to see the effect of the macrocell setup costs, the base problem is modified such that the macrocell cost is decreased from 10 unit costs to 0 unit costs as shown in Figure 5.16. It is assumed that the microcell layer is already present and for each macrocell, an additional price is paid. When the additional macrocell setup cost is less than 20 percent of the microcell cost, the two-tier system becomes cost effective. As described in this section previously, a similar behavior is observed when the macrocell cost is five times the microcell setup cost. Hence, it can be deduced from these results that the cost ratios less than 0.2 or greater than 5.0 causes systems like the one described in the base problem be handled cheaper with two-tier cellular networks.
As a result, it can be concluded that the two-tier systems are cheaper in certain cases. When the ratio of the cell setup costs is either very large or close to zero, the two-tier systems become cost effective when compared with the single-tier systems. A similar observation is made for cases where the ratio of the high mobility users are far less than the low mobility users. Systems capable of working with cluster sizes of three have cost advantages if they employ a proper two-tier structure. Finally, when the mobility in general decreases, the cost difference is changing in favor of the two-tier cellular network.
5.2.12	Scale of the Effects of Parameters on the Cost
The effect of the parameters on the system cost can be summarized as follows: As the load on the system or as the scale of the system increase, the system cost also increases. Similarly, as the performance requirements become stricter, the cost of the system increases. But the scale of these effects and their general tendencies are rather different. These behaviors are explained in the previous sections in detail.
We consider it necessary to take a look at the scale of the effects in general. It can be concluded that the most effect on cost is caused by the area and the call duration. It is easy to explain the effect of the area. When the area to be covered increases, the resources needed for the system also increases linearly. Hence, if the area is doubled, surely, the cost is doubled. The effect of the call duration is directly related with the load on the system. If the call duration becomes larger, then calls need to be serviced by more channels. Since the number of the channels are fixed, the changes can only be done in the cell radii. In order to increase the total number of channels available, more cells are deployed within the same coverage area. Therefore, the largest effect is caused by the call duration.
On the other hand, the increase in the mobility does not effect the cost very much. When the mobility is increased, only the handoff call arrival rate increases. Simultaneously, also the dwell times decrease. Hence, the occupation of the channels in general is not affected. But some temporary bottlenecks may be formed by frequent handoffs. These bottlenecks surely affects the overall performance. But this effect is reversed easily with only minor cost additions. Hence mobility has less effect on cost.
5.3	Demonstration of Results
In this section, the results of several tests are presented. All of these tests are based on the base problem defined in Section 5.1. In order to demonstrate the behavior of the two-tier cellular network in question, several nominal and extreme parameter configurations are tested and solutions are compared with other solution techniques. The other solution techniques are described in Sections 4.3 and 4.4. 
Section 5.3.1 shows that the range of the SA solutions is not large. Section 5.3.2 compares the results of the SA, GS and GAT algorithms. The obtained results are grouped according to the parameters changed. These parameters are given in the description column.
5.3.1	Range of the SA Solutions
The SA algorithm is chosen for the two-tier cellular network design problem because of its capability to search beyond local minima of the objective function. When the SA algorithm is run multiple times, with possibly different seeds, the results should be not too far from each other [6]. In order to check the validity of this statement, the following tests are performed. For six different randomly selected problems, the SA algorithm is run 10 times, and the best result obtained in each run is recorded. Then, the overall minimum in these 10 runs are found. Furthermore, in order to have an idea of the spread of other solutions, the mean value, standard deviation and the ratio of the standard deviation and the mean is calculated. The results are shown in Table 5.4.
TABLE 5.4  Statistics of 10 SA Runs for Several Problems
Prob. No	Description	Minimum	Mean	std. Dev.	std. dev. /mean	
4	Slow Low Mobility Speed=0.25m/s	146500	148086	1408.85	0.0095	
7	Fast High Mobility Speed=20m/s	162370	164442	1399.65	0.0085	
10	High Mobility Arrival Rate=5e-9	73140	75036	1473.36	0.0196	
12	Frequent Call Arrivals	646660	656579	7946.32	0.0121	
15	Long Duration=200sec	337170	344701	4250.13	0.0123	
17	Strict Performance Limits	161270	168524	20157.38	0.1196	
20	Cluster Size=19	1054540	1077312	29803.89	0.0277	

The results are rather good, since the minimum values found are close to the means. The ratio of the standard deviations and the means are also around a few percent except for the Problem 17. This jump in the ratio is caused by a single unsuccessful run of the SA algorithm. Hence it can be concluded that the solutions found are not very different from each other. As the number of the SA runs increases, only incremental gains can be obtained.
5.3.2	Comparative Evaluation of SA, GS and GAT Solutions
In this section, the performance of the SA algorithm is compared with the performances of the GS and GAT algorithms. In order to compare the GS and SA algorithms fairly, the basic SA algorithm is run until 1000 accepted moves are reached. This may correspond to multiple runs of the basic SA algorithm. It is fair to run the basic SA algorithm more than once, since the results do not change very much with increasing number of runs. By doing this, the number of evaluated solutions are determined approximately. Then the number of performance evaluations in the GS algorithm is set equal to the mean number of performance evaluations in the SA algorithm. Hence, the running time of both algorithms are normalized.
All the problems presented are variations of the base problem. The changed parameter is given in the description column as well as in the text. Same problems are also used in Sections 5.2.11 and 5.3.1. The obtained results are shown in Table 5.5.
TABLE 5.5  Results Obtained with SA, GS and GAT Algorithms for Several Problems
Prob. No	Description	SA	GS	GAT Min	GAT Avg	GAT Max	
1	Base Problem	152060	155390	151890	2118037	10895180	
2	Area=1000km2	30990	30380	30570	429610	2193440	
3	Area=50km2	1550	1660	1550	20789	108860	
4	Slow Low Mobility Speed=0.25m/s	147000	154050	148950	2099563	10901150	
5	Fast Low Mobility Speed=3m/s	157200	161260	157360	2145840	10925040	
6	Slow High Mobility Speed=5m/s	149900	154540	150460	2094752	10889240	
7	Fast High Mobility Speed=20m/s	162440	165560	164150	2204543	10942990	
8	Low Mobility Arrival Rate=2e-8	112590	118280	112300	2041311	10967040	
9	Low Mobility Arrival Rate=1.5e-7	195400	195860	193880	2278864	10919060	
10	High Mobility Arrival Rate=5e-9	76990	77380	92300	1325920	10913080	
11	High Mobility Arrival Rate=8e-8	489980	774880	484280	3516816	10997170	
12	Frequent Call Arrivals	646790	651960	645940	3765970	10979070	
13	More High Mobility Users	218300	212540	213240	2529019	10948990	
14	Short Duration=40sec	54580	56100	93250	1393697	10818160	
15	Long Duration=200sec	356570	372160	338460	2952800	10954990	
16	Loose Performance Limits	124360	123950	120970	1901178	10973050	
17	Strict Performance Limits	161180	165680	161100	2177883	10979070	
18	Very Strict Performance Limits	172760	180290	173660	2261686	10942990	
19	Cluster Size=3	47690	60690	89760	1400909	10889240	
20	Cluster Size=19	1054040	1069140	1052850	4531172	10991140	
21	Same Unit Price	121960	123350	120960	1920096	8792900	
22	Price Ratio=1:5	181300	188020	182160	2301842	13196610	
23	No Macrocell Setup Cost	37500	38020	105990	1821174	7698010	

The first parameter changed is the area. The results for different area sizes are calculated. The base problem is chosen as a large area. A medium sized city of 1000 km2 and a part of the city of size 50 km2 are chosen as targets in Problems 2 and 3 respectively.
When different areas are selected as input to the algorithms the solutions are produced that are actually almost identical to each other except for the total number of cells that are needed. This information can easily be extracted from the cost ratios. The ratios of the areas for the problems one, two and three behave like 100:20:1. Almost the same ratio is observed for the cost values in the SA column. Indeed, if the results obtained using SA algorithm are compared, one can see that the radii and channel splitting is the same for all three problems. Hence it can be concluded that the area has no effect on the decision variables but the cost.
In problems one and three, the GS algorithm finds slightly worse solutions whereas it finds a lucky starting point for the second problem and finds a slightly better result. When 5000 feasible solutions are generated the best results obtained are close to the solutions obtained with the SA algorithm. The mean and the maximum costs give a feeling about how big the feasible solution space is. For the first problem, the mean rate is 14 times larger than the best solution. Similar ratios can be found also for other problems.
The terminal mobility is a parameter that changes the number of handoffs during a call. In Problems 4-7, cases with different mobility rates are examined. For these considerations two parameters are altered independently. For low mobility terminals, slow, moderate and high mean speeds are selected as 0.25, 1 and 3 m/s respectively. For the high mobility terminals, slow, moderate and high mean speeds are selected as 5, 8 and 20 m/s respectively.
Problem 1 is the moderate speed rate for both mobility class comparisons. For the low mobility mean speeds, the system cost increases as the mean speed increases. In Problems 1, 4 and 5, as the mobility increases, the radii of both cellular layers decrease in order to increase the channels available per m2. Hence the system creates more resources for frequent handoffs. In this case, the frequent handoffs may create problems in the signaling part of the network, on which no special attention is paid in this work.
The solutions generated by the GAT algorithm are worse in Problems 4-7. The case for the GS algorithm is on the same course: None of the solutions obtained outperform the results of the SA algorithm. Hence the SA algorithm produces better results in considerably less time.
The call arrival rates are the main sources of load on the cellular networks. In Problems 8-13, the arrival rates originated by users of both mobility classes are changed to observe changes in the cost. The seldom, moderate and frequent call arrival rates of the low mobility class users are selected as 2x10-8, 8x10-8 and 1.5x10-7 calls per second per m2 respectively. The seldom, moderate and frequent call arrival rates of the high mobility class users are selected as 5x10-9, 2x10-8 and 8x10-8 calls per second per m2 respectively. The moderate arrival rates for both cases correspond to the base problem. In addition to these problems, another problem is inspected, where the load is very high. For this problem, the low mobility arrival rate is 3x10-7 and the high mobility arrival rate is 8x10-8 calls per second per m2. Another case, where the low mobility arrival rate is less than the high mobility case, is presented. The call arrival rates are 2x10-8 and 4x10-8 calls per second per m2 for low and high mobility users respectively.
There are several important facts that can be concluded from the obtained results. As can be expected, as the call arrival rates increase, the system cost also increases. Furthermore, according to the results of the problems 1, 9 and 11, when the call arrival rates of the high and low mobility users is multiplied approximately by two, the system cost effected most for the increase of the arrival rates of the high mobility calls.
In most of the tested problems, SA algorithm yields better results than the GS algorithm, sometimes with big differences. The solutions of the GAT algorithm indicates that the solutions of the SA algorithm is not very far from the best solutions found. Indeed, in Problems 8,9 and 11-13, the time needed for the GAT algorithm pays off. The best solutions for these problems belong to the GAT algorithm.
Another parameter that affects the load on the system is the duration of the calls. In the test Problems 1, 14 and 15, three different call duration values are considered. The short calls last 40 seconds. Medium length calls have a duration of 100 seconds, which corresponds to the base problem. Long calls last 200 seconds.
The solutions of the SA algorithm are better than the solutions of the GS algorithm in all three cases. The results of the GAT algorithm indicate that the system is capable of finding better results for shorter mean call duration values with both the GS and GAT algorithms. This may be caused by the increased search space created by the decreased call duration. Since the call duration is decreased, the .load on the system is also decreases. Hence more configurations may be generated without violating the performance constraints.
The maximum allowable call blocking and dropping thresholds sets the limits of the solution space. In Problems 1, 16, 17 and 18, four different models are considered. Problem 16 corresponds to loose limits with Pb,max=0.02 and Pd,max=0.01. The normal limits are the limits used in the base problem. The performance limits are Pb,max=0.01 and Pd,max=0.001. The strict limits are Pb,max=0.01 and Pd,max=0.0001 in Problem 17 and very strict limits are Pb,max=0.005 and Pd,max=0.0001 in Problem 18.
The solutions obtained with the GS algorithm are worse except for Problem 16. From the comparisons with the GAT algorithm, it can be concluded that the success of the SA algorithm increases as the performance limits become more strict, since the SA algorithm makes a more intelligent search than the GS and GAT algorithms.
Other factors effecting the solutions are cluster size that is used and the cost ratio of the microcells and macrocells. In Problems 19,1 and 20, cluster sizes are chosen as 3, 7 and 19. Problems 21, 1 and 22 correspond to the cost ratios 1:1, 1:3 and 1:5. In addition to these ratios, the case where the microcell antennas are capable of handling both tiers are considered. In the latter case, there is no macrocell setup cost.
Since the number of available channels are split into smaller chunks when cluster size increases, the cost of the system also increases. The GS algorithm never produces any better results than the SA algorithm for different cluster sizes. The GAT algorithm fails in cases where the system has much larger capacity than the offered load, as in Problem 19. In other problems, the GAT and SA algorithms produce results close to each other.
5.4	Effect of Call Arrival Rate Fluctuations
Before systems are designed, the characteristics of the environment and requirements are determined. Then, the designed systems are optimized to work with the fixed parameters. If the parameters change unexpectedly, then the required system performance cannot be guaranteed once the system is set up.
In our problem, call arrival rates may be fluctuating due to several reasons. The reasons may range from time of the day to special occasions and natural disasters. In such cases, the load on the system may increase beyond the mean rates. It is important to assess the performance of an already designed system under such conditions.
The main aim of the SA algorithm is to find solutions with the minimum cost. Therefore, the limits of the performance are approached as much as possible. This makes the whole system sensitive to such call arrival rate fluctuations. On the other hand, if the solution fails to approach the performance limits, then it may be that the system is more robust to the call arrival rate increases. 
Figure 5.17 shows the call blocking rates for several multiplication factors, where the low mobility call arrival rate increases, and two configurations of comparable costs. The configurations differ in the speed of threshold crossing and the slope of the probabilities. Note that the solution, which is more expensive, starts with better call blocking probability, crosses the threshold at a greater factor, but is more sensitive to call arrival rate increases. The similar case for the increase in high mobility call arrival is shown in Figure 5.18. It is worth to note that both systems are more sensitive to the fluctuations in the high mobility call arrivals.
Although the costs are not very different from each other, the responses of different solutions to load increases can be completely different and also unexpected. Therefore, to be prepared for the worst cases, the arrival rates should be multiplied by appropriate factors before designing the system. The factors mentioned may be around 1.2 or 1.3.

FIGURE 5.17  Low Mobility Call Arrival Increase vs. Pb/Pd

FIGURE 5.18  High Mobility Call Arrival Increase vs. Pb/Pd
5.5	Time Complexity
The determination of the time complexity of the SA algorithm is a rather hard job. The algorithm consists of several disjoint parts. First of all, the innermost stage involves calculation of the steady state probabilities. This part of the algorithm involves calculations primarily connected with the number of the channels available. The calculation of the steady state probabilities involve several while-loops, but in none of the cases they are cascaded. Therefore, the contribution of the calculation of steady state probabilities to the time complexity is linear with respect to the number of available channels.
In the second innermost stage, the tier-level handoff rates are calculated. While calculating the handoff rates, an iterative method is used. Experimentation with the algorithm showed that the algorithm converges to a fixed handoff rate after 10 to 15 iterations, almost independent of the input parameters. Therefore, this part of the algorithm brings only a multiplication factor to the overall time complexity. However, since this value may be raised to several powers, it may effect the time complexity in a bad manner. Even in this case, that value will be a multiplication factor.
The other parameters do not have any impact on the calculation of the performance measures of the systems. Their effect is primarily on the outer shell, namely the SA algorithm. Since the SA algorithm is running several times beginning from the start, until the number of accepted moves reach 1000, the effects of the parameter changes are only observable in the number of times the SA algorithm is restarted. However, their contribution to the overall time complexity is hardly noticeable.
The effect of number of available channels is studied also with measurements. The code of the program is written with C++ and compiled with Microsoft Visual C++ 5.0 compiler. The tests are performed on PC with Intel Pentium 166 MHz microprocessor and 32 MB of RAM. For calculation of the values presented in the figures, at least 10 basic SA runs are made and the averages are calculated. The measurements showed that the number of the channels affect the runtime of a single run of the basic SA algorithm as shown in Figure 5.19. This behavior resembles a quadratic effect on the single run for small values of channel number. The effect becomes linear for larger numbers.

FIGURE 5.19  Number of Available Channels vs. Mean Runtime of a Single SA Run
The effect of the total number of channels, on the other hand, is smoother. The most probable reason for this observation is that the SA algorithm continues until a fixed number of moves are accepted. Hence the number of basic SA runs decreases if the duration of a single basic SA run increases. The impact of increasing the channel number is almost linear. As the number of the channels increase, the increase in the time needed to complete the SA algorithm decreases. Hence the total execution time does not increase too much if the number of channels available is high. The effect of the number of channels on the overall execution time is shown in Figure 5.20.

FIGURE 5.20  Channel Number vs. Total Runtime
6.	CONCLUSION AND FUTURE WORK
In the design of cellular communication networks, one of the most important aims is to create systems that are of minimum cost. Furthermore, the designed system should also confirm to the given performance constraints. One of the approaches used in the cellular network design is employment of multiple tiers on top of each other. This solution is preferred in cases where multiple mobility classes are present in the area of consideration. In order to improve the performance, several additional methods can be incorporated.
In this work, we concentrated on the design of a two-tier cellular network. The network has single direction call overflow capability and is capable of employing guard channels. The resulting cellular networks are networks for which the costs are minimized. The performance constraints are maximum allowable call blocking and call dropping probabilities. In order to find near-optimum solutions, the SA algorithm is used. The performance of the SA algorithm is compared with the performance of GS algorithm and GAT method. The performance of the two-tier cellular network is compared with the single tier cellular networks with guard channels.
Computational experiments showed that the SA algorithm outperforms the GS algorithm in most of the cases. The quality of the solutions are compared with the results of the GAT method. The cost values obtained with the SA algorithm are either better than the solutions of GAT, or they are very close to each other. Furthermore, the runtime of the SA method is effected only in little amounts from the changes in parameters.
When compared with single-tier networks, two-tier networks show their cost advantages in certain cases. When the ratio of the cell setup costs is either very large or close to zero, the two-tier systems become cost effective. Furthermore, when call arrival rate of low mobility users exceeds the call arrival rate of the high mobility users significantly, then the cost of single-tier networks exceeds the cost of two-tier networks. Finally, a similar advantage in favor of two-tier cellular networks is observed for the clusters consisting of three cells.
The effects of several parameters on the cost of the system is studied. Additionally, the effect of design decisions, having guard channels and allowing call overflow, are also considered. The behavior of the designed network in the case of call arrival rate fluctuations is also studied. Furthermore, the effects of some parameters and design decisions on the system performance are investigated.
There is still work that can be done related to the two-tier cellular network design. First of all, the number of tiers can be increased. Secondly, non-uniform mobility patterns should be studied. Better neighborhood structures for the SA algorithm should be developed. If necessary, the SA algorithm and/or the cooling schedule should be improved. Several other optimization techniques could be implemented and their performance could be compared with the results of this work. The alternative solution techniques may include Taboo Search and Genetic Algorithm. In order to minimize the time complexity of the system, the routines that calculate the system performance should be optimized. The robustness against the load fluctuations should be introduced as another performance measure.
More extensive comparisons with single tier cellular networks could be realized. Several new base problems corresponding to different environments could be defined. The input parameter space could be searched more extensively and compared with the results of other solution techniques.

REFERENCES
1. 	Katz, R. H., “Adaptation and Mobility in Wireless Information Systems,” IEEE Personal Communications Magazine, Vol. 1, No. 1, pp. 6-17, First Quarter 1994.
2. 	Shafi, M., A. Hashimoto, M. Umehira, S. Ogose and T. Murase, “Wireless Communications in the Twenty-First Century: A Perspective,” Proceedings of the IEEE, Vol. 85, No. 10, pp. 1622-1639, October 1997.
3. 	Agrawal, P., E. Hyden, P. Krzyzanowski, P. Mishra, M. B. Srivastava and J. A. Trotter, “SWAN: A Mobile Multimedia Wireless Network,” IEEE Personal Communications, pp. 18-33, April 1996.
4. 	Davies, N., G. S. Blair, K. Cheverst and A. Friday, “Supporting Collaborative Applications in Heterogeneous Mobile Environment,” Computer Communications Special Issue on Mobile Computing, Internal Report Number MPG-94-18, 1996.
5. 	Rappaport, T. S., Wireless Communications, New Jersey: Prentice Hall, 1996.
6. 	Brooks, S. P. and B. J. T. Morgan, “Optimization Using Simulated Annealing,” The Statistician, No. 44, pp. 241-257,1995.
7. 	Park, S. K., J. H. Lee and J. M. Hong, “A Mathematical Programming Approach to a Configuration Optimization Problem in Cellular Radio Networks,” Proceedings of the Global Telecommunications Conference (IEEE GLOBECOM ‘97), Arizona, 1997.
8. 	Passas, N., S. Paskalis, D. Vali and L. Merakos, “Quality-of-Service-Oriented Medium Access Control for Wireless ATM Networks,” IEEE Communications Magazine, pp. 42-50, November 1997.
9. 	Naghshineh, M. and M. Willebeck-LeMair, “End-to-End QoS Provisioning in Multimedia Wireless/Mobile Networks Using an Adaptive Framework,” IEEE Communications Magazine, pp. 72-81, November 1997.
10. 	Çayırcı, E. and C. Ersoy, “Cell Grouping in PCS Networks,” Proceedings of the Second Symposium on Computer Networks, pp. 14-21, Ankara, Turkey, 1997.
11. 	Acampora, A. S. and M. Naghshineh, “Control and Quality-of-Service Provisioning in High-Speed Microcellular Networks,” IEEE Personal Communications, pp. 36-43, Second Quarter 1994.
12. 	Pollini, P. P., “Trends in Handover Design,” 1996, htttp://www.ieee.org/comsoc/pollini.html
13. 	Acharya, A., J. Li, B. Rajagopalan and D. Raychaudhuri, “Mobility Management in Wireless ATM Networks,” IEEE Communications Magazine, pp. 100-109, November 1997.
14. 	Acharya, A. and B. R. Badrinath, “A Framework for Delivering Multicast Messages in Networks with Mobile Hosts,” Mobile Networks and Applications (MONET), Vol. 1, No. 2, pp. 199-219, 1996.
15. 	Brown, K. and S. Singh, “The Problem of Multicast in Mobile Networks,” Proceedings of IEEE Fifth International Conference on Computer Communications and Networks, Rockville, Maryland, October 1996.
16. 	Akyıldız, I. F., J. S. M. Ho and Y. Lin, “Movement-Based Location Update and Selective Paging for PCS Networks,” IEEE/ACM Transactions on Networking, Vol. 4, No. 4, pp. 629-638, August 1996.
17. 	Akyıldız, I. F. and J. S. M. Ho, “A mobile User Location Update and Paging Mechanism under Delay Constraints,” Proceedings of the Conference on Applications, Technologies, Architectures and Protocols for Computer Communications (ACM SIGCOMM ‘95), pp. 244-255, Cambridge, Massachusetts, 1995.
18. 	Rose, C. and R. Yates, “Location Uncertainty in Mobile Networks: A Theoretical Framework,” IEEE Communications Magazine, pp. 94-101, February 1997.
19. 	Liu, G. Y. and G. Q. Maguire Jr., “Efficient Mobility Management Support for Wireless Data Services,” Proceedings of VTC ‘95, Chicago, Illinois, 1995.
20. 	Katzela, I. and M. Naghshineh, “Channel Assignment Schemes for Cellular Mobile Telecommunication Systems: A Comprehensive Survey,” IEEE Personal Communications, pp. 10-31, June 1996.
21. 	Wirth, P. E., “The Role of Teletraffic Modeling in the New Communications Paradigms,” IEEE Communications Magazine, pp. 86-92, August 1997.
22. 	Markoulidakis, J. G., G. L. Lyberopoulos, D. F. Tsirkas and E. D. Sykas, “Mobility Modelling in Third-Generation Mobile Telecommunications Systems,” IEEE Personal Communications, pp.41-56, August 1997.
23. 	Lam, D., D. C. Cox and J. Widom, “Teletraffic Modeling for Personal Communications Services,” IEEE Communications Magazine, pp. 79-87, February 1997.
24. 	Lin, Y., “Modeling Techniques for Large-Scale PCS Networks,” IEEE Communications Magazine, pp. 102-107, February 1997.
25. 	Rajaratnam, M. and F. Takawira, “Handoff Traffic Modeling in Cellular Networks,” Proceedings of the Global Telecommunications Conference (IEEE GLOBECOM ‘97), Arizona, 1997.
26. 	Fang, Y., I. Chlamtac and Y. Lin, “Modeling PCS Networks Under General Call Holding Time and Cell Residence Time Distributions,” IEEE/ACM Transactions on Networking, Vol. 5, No. 6, pp. 893-906, December 1997.
27. 	Zhang, Z., I. Habib and T. Saadawi, “Supporting Multimedia Traffic over Microcellular Networks,” Proceedings of the Global Telecommunications Conference (IEEE GLOBECOM ‘97), Arizona, 1997.
28. 	Frost, V. S. and B. Melamed, “Traffic Modeling for Telecommunications Networks,” IEEE Communications Magazine, pp. 70-81, March 1994.
29. 	Lagrange, X. and B. Jabbari, “Fairness in Wireless Microcellular Networks,” IEEE Transactions on Vehicular Technology, Vol. 47, No. 2, pp. 427-479, May 1998.
30. 	Alevras, D., M. Grötschel, P. Jonas, U. Paul and R. Wessaely, “Survivable Mobile Phone Network Architectures: Models and Solution Methods,” IEEE Communications Magazine, pp. 88-93, March 1998.
31. 	Tekinay, Ş. and B. Jabbari, “A Measurement-Based Prioritization Scheme for Handovers in Mobile Cellular Networks,” IEEE Journal on Selected Areas in Communications, Vol. 10, No. 8, pp. 1343-1350, October 1992.
32. 	Sidi, M. and D. Starobinski, “New Call Blocking versus Handoff Blocking in Cellular Networks,” Proceedings of the Conference on Computer Communications (IEEE INFOCOM ‘96), 1996.
33. 	Oh, S. and D. Tcha, “Prioritized Channel Assignment in a Cellular Radio Network,” IEEE Transactions on Communications, Vol. 40, No. 7, pp.1259-1269, July 1992.
34. 	Guerin, R., “Queuing-Blocking System with Two Arrival Streams and Guard Channels,” IEEE Transactions on Communications, Vol. 36, No. 2, February 1988.
35. 	Lau, V. K. N. and S. V. Maric, “Mobility of Queued Call Requests of a New Call-Queuing Technique for Cellular Systems,” IEEE Transactions on Vehicular Technology, Vol. 4, No. 2, pp. 480-488, May 1998.
36. 	Hong, D. and S. S. Rappaport, “Traffic Modeling and Performance Analysis for Cellular Mobile Radio Telephone Systems with Prioritized and Nonprioritized Handoff Procedures,” IEEE Transactions on Vehicular Technology, Vol. VT-35, No. 3, pp. 77-92, August 1986.
37. 	Veeravalli, V. V. and O. E.  Kelly, “A Locally Optimal Handoff Algorithm for Cellular Communications,” IEEE Transactions on Vehicular Technology, Vol. 46, No. 3, pp. 603-609, August 1997.
38. 	Chu, T. and S. S. Rappaport, “Overlapping Coverage with Reuse Partitioning in Cellular Communication Systems,” IEEE Transactions on Vehicular Technology, Vol. 46, No. 1, pp. 41-54, February 1997.
39. 	Li, J., N. B. Shroff and E. K. P. Chong, “Channel Carrying: A Novel Handoff Scheme for Mobile Cellular Networks,” Proceedings of the Conference on Computer Communications (IEEE INFOCOM ‘97), Kobe, Japan, 1997.
40. 	Hu, L. and S. S. Rappaport, “Personal Communication Systems Using Multiple Hierarchical Cellular Overlays,” IEEE Journal on Selected Areas in Communications, Vol. 13, No. 2, pp. 406-415, February 1995.
41. 	Ortigoza-Guerrero, L. and A. H. Aghvami, “On Optimal Spectrum Partitioning in a Microcell/Macrocell Layout with Overflow,” Proceedings of the Global Telecommunications Conference (IEEE GLOBECOM ‘97), Arizona, 1997.
42. 	Ganz, A., C. M. Krishna, D. Tang and Z. J. Haas, “On Optimal Design of Multitier Wireless Cellular Systems,” IEEE Communications Magazine, pp. 88-93, February 1997.
43. 	Wang, L., L. S. Gordon and C. Lea, “Architecture Design, Frequency Planning, and Performance Analysis for a Microcell/Macrocell Overlaying System,” IEEE Transactions on Vehicular Technology, Vol. 46, No. 4, pp. 836-848, November 1997.
44. 	Akyol, B. A. and D. C. Cox, “A Dynamic Allocation and Media Access Control Proposal for a Multi-tier Wireless ATM Network,” Proceedings of the Global Telecommunications Conference (IEEE GLOBECOM ‘97), Arizona, 1997.
45. 	Bertsekas, D. and R. Gallager, Data Networks, Second Edition, New Jersey: Prentice Hall, 1992.