Open access

Base Station Design and Siting Based on Stochastic Geometry

Written By

Hui Zhang, Yifeng Xie, Liang Feng and Ying Fang

Submitted: 06 August 2012 Published: 13 February 2013

DOI: 10.5772/55493

From the Edited Volume

Vehicular Technologies - Deployment and Applications

Edited by Lorenzo Galati Giordano and Luca Reggiani

Chapter metrics overview

2,605 Chapter Downloads

View Full Metrics

1. Introduction

In this chapter, the base station (BS) design and siting method is introduced, which includs three parts: general BS design and siting method, stochastic geometry in BS design and siting, frequency planning for BS design and siting. Moreover, the concept of stochastic geometry is introduced, and also stochastic geometry theory is taken in wireless network analysis.

Stochastic geometry is a helpful method in modeling vehicular ad-hoc network, especially in vehicle to infrastructure communication. In this chapter some related concepts of stochastic geometry are introduced, which may help to establish the model of vehicular ad hoc network, such as vehicle to vehicle communication network.

Vehicular ad hoc networks (VANETs) are a special case of mobile ad hoc networks (MANETs), where such network is formed between vehicles [1]. We can analyze the stochastic model of MANETs to derive the model for VANETs. MANETs are wireless networks made of one type of nodes (Vehicle to Vehicle communication of VANETs is made of vehicles). Each node can either transmit or receive information using the same frequency band. Each node is denoted as the terminal (such as source and destination) or router (such as relay). Moreover, each hop by hop transmission and the connectivity between source and destination depend on the location of intermediate relay nodes [2]. With different distribution of the above nodes, various hot spots can be established. For example, assume these nodes are Poisson point process, written as P.P.P. Then we can use the properties of P.P.P. to derive formulas, such as SINR. [1,3] give some models by means of analyzing Aloha in VANETs using stochastic geometry theory. In actual scenarios, there are many ways to establish different stochastic geometry models for VANETs. It is not practical to deploy a high-density network for vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communication instantly. New workforce skills for the installation and maintenance of V2I applications need to be considered, as well as the privacy policy restrictions. V2I communication works well if cars are in low speed or keeping relative rest. But with high speed, cars cannot keep information interaction with infrastructures for a long time. Mobile relay station (MRS) is one scheme which can be used in high-speed conditions. MRS provides the information interaction between base station and mobile terminals in cars, reducing the connections from a single mobile terminal in the car to the base station. Group handover scheme and two-level resource allocation algorithm can also be considered in the MRS scheme. Heterogeneous vehicular wireless architecture based on different technologies,such as WAVE (IEEE 802.11p) and WiMAX (IEEE 802.16e) technology, can be a great help for V2I communication.

On the other hand, it’s a critical method for frequency planning in BS design and siting. Under this background, the frequency planning theoretical analysis is given in this chapter for OFDMA-based cellular systems, including four parts, respectively multigraph theory, algebraic analysis principle, extension theory and Stackelberg theory. In graph theory, the coloring theory in multi-graph and the level interference-limited theory are focused, resulting in an frequency reuse analysis from the optimization problem. In algebraic analysis principle, a quantitative analytic algebra to describe the relationship of frequency reuse factor between cell center and cell edge is given and the frequency reuse optimization problem is transformed into two-dimensional coordinate system, enables to take analytic algebra method to solve it. In extension theory analysis, the multi-dimensional cell-edge element model and its multi-element extension set is established for frequency allocation. In Stackelberg theory, the frequency optimization in cooperative communication is formulated into Stackelberg problem and a Stackelberg model is established for this architecture. On the basis of the above theoretical analysis, a soft fractional frequency reuse (SFFR) scheme is presented, including two parts: SFFR I and SFFRII. The numerical results show that 这个修改暂定 when FRF is large, while taken SFFRII scheme when FRF is small. Furthermore, it needs to take into account the size of FRF, both cell-edge and cell-center performance to choose the appropriate inner radius.

Advertisement

2. General BS design and siting method

Base station planning is very important in the whole process of wireless network optimization, including base station siting, the configuration of base station equipment, wireless network parameters setting and the analysis of wireless network performance.

2.1. Principle of BS design and siting

In BS design and siting, firstly it needs to determine the number of required BS according to the analysis of link budget and network capacity. The principle of base station design and siting is given as follows:

  1. Estimate the amount of base stations by means of link budget and coverage requirement.

  2. Analyze the capacity of actual network and then determine the required amount of base stations which can meet the need of capacity.

  3. Compare and choose base station according to the results of estimation and analysis.

The base station planning is complex. Both technical and feasible factors should be considered. The configuration of equipment is designed both hardware and software of base stations, based on the coverage, capacity, quality requirement and ability of design. By surveying the expected location of base stations and simulating the whole wireless network, the right wireless parameters can be chosen to meet the requirement of design, including transmission type, antenna height, antenna angle, carrier frequency, etc. Before actual base station design and siting, it’s always needed to simulate the performance of the whole wireless network by Monte Carlo method.

In BS planning, the preliminary setting equipment load and carrier types in different area is determined according to prophase demand analysis, which divides into two parts, respectively link budget and capacity planning. There are two formulas, written as N1 and N2. N1 denotes as the number of base stations meeting coverage requirement and N2 denotes as the number of base stations meeting capacity requirement. Comparing N1 with N2, the number of base stations in this area is chosen as N=max (N1, N2). Then the base station planning is done for the total area. On the one hand, if N1<<N2, check whether the equipment overload. If it is, we can increase the carrier frequency of the large capacity demand area. On the other hand, the load can be decreased or increased according to different situations. The process of BS planning is shown in Fig.1.

Figure 1.

The general process of BS planning

2.2. Estimate the amount of BS

The basic process of estimating the amount of BS is given as follows:

  1. Determine the bearing capacity of the wireless network: derive the bearing capacity of the whole link by simulating and testing the network.

  2. Determine the parameters of the whole wireless network.

  3. Derive the minimum amount of BS to meet the requirement of coverage. The coverage area of each BS: R is the maximum cover radius of each BS. S is the coverage area of each BS. D is the average distance between two neighboring BSs. Based on antenna properties, BS can be divided into two types: Omni-directional and directional. Many directional BSs are three sectors. The coverage areas are different with different BS types.

  4. Derive the minimum amount of BS to meet the requirement of capacity. Table 1 shows the traffic capacity of different BS types.

  5. Determine the configuration of BS according to the capacity of each sector.

  6. Modify the number of BS for different areas.

Besides, some other factors can be considered in estimating the amount of BS, such as link budget, pre-planning and antenna types.

Typs of BSs Number of Sectors Number of carrier frequency Voice Channel(Erl) Visual telephone(Erl) Throughput of downlink(kbit/s)
Omni-directional 1 1 DUi NUi SVi
directional 3 1 3*DUi 3* NUi 3* SVi
directional 3 2 6*DUi 6* NUi 6* SVi
directional 3 3 9*DUi 9* NUi 9* SVi

Table 1.

Traffic capacity of different BS types

Ps : DUi, NUi,SVi (respectively denote as Dense Urban, Nomal Urban, Suburb and Village ) are the capacity of single sector of a BS.


  1. Omni-directional BS:

Figure 2.

Honeycomb structure of omni-directional BS(S=33R2/2)

  1. Three sector directional BS(clover)

Figure 3.

Honeycomb structure of three sector directional BS (clover) (S=93R2/8)

This structure is generally used in the downtown.

  1. Three sector directional BS(hexagon)

Figure 4.

Honeycomb structure of three sector directional BS (hexagon) (S=33R2/2)

This structure is generally used in villages.

Advertisement

3. Stochastic geometry in BS design and siting

With the development of communication technology, the density of users is increasing, as well as the interference. As both interference and density of users can be modeled by the spatial location of nodes, mathematical techniques have been used in this area, such as stochastic geometry, including point process theory [4]. In [5], a method is introduced to add optimal number of base stations to the optimal placement of an existing wireless data network, where the whole network is modeled as a P.P.P.

Cellular networks are usually modeled by placing the base stations according to a regular geometry such as a grid, with the mobile users scattered around the network either as a Poisson point process (i.e. uniform distribution) or deterministically. These models have been used extensively for cellular design and analysis but suffer from being both highly idealized and not very tractable. Mathematical analysis for conventional (1-tier) cellular networks is known to be hard, and so highly simplified system models or complex system level simulations are generally used for analysis and design respectively. To make matters worse, cellular networks are becoming increasingly complex due to the deployment of multiple classes of BSs that have distinctly traits.

Cellular networks are in a major transition from a carefully planned set of large tower-mounted base stations to an irregular deployment of heterogeneous infrastructure elements that often additionally includes micro, pico, and femtocells, as well as distributed antennas. For example, a typical 3G or 4G cellular network already has traditional BSs that are long-range and guarantee near-universal coverage, operator-management picocells and distributed antennas that have a more compact form factor, smaller coverage area and are used to increase capacity while eliminating coverage dead zones and femtocells, which have emerged more recently and are distinguished by their end-user installation arbitrary locations, very short range, and possibility of having a dozed-subscriber group. This evolution toward heterogeneity will continue to accelerate due to crushing demands for mobile data traffic caused by the proliferation of data-hungry devices and applications.

In this section, we plan to develop a tractable, flexible and accurate model for a downlink heterogeneous cellular network (HCN) consisting of K tiers of randomly located BSs, where each tier may differ in terms of randomly located BSs, where each tier may differ in terms of average transmit power, supported data rate and BS density.

3.1. Stochastic geometry theory

3.1.1. Poisson point process

A spatial point process (p.p.) Φ is a random, finite or countably-infinite collection of points in the d-dimensional Euclidean space Rd, without accumulation points[6].

Definition: Let Λbe a locally finite non-null measure on Rd. The possion print process Φof intensity measure Λis defined by means of its finite-dimensional distributions:

{Φ(A1)=n1,...,Φ(Ak)=nk}=i=1k(eΛ(Ai)Λ(Ai)nini!)E1

for every k =1,2,… and all bounded, mutually disjoint sets Ai for i = 1,2,…k. If Λ(dx)=λdx is a multiple of Lebesgue measure (volume) in Rd, we call Φ is a homogeneous Poisson p.p. and λ is its intensity parameter[6].

Poisson point process is a tractable tool to model the random distribution of users or base stations with high density. Other point processes can also be used to analyze the distribution of base stations with high density.

3.1.2. Voronoi tessellation

In mathematics, a Voronoi tessellation is a special kind of division of a given space, determined by distances to a specified family of objects (subsets) in the space. These objects are usually called the sites or the generators and to each such object one associate a corresponding Voronoi cell, namely the set of all points in the given space whose distance to the given object is not greater than their distance to the other objects.

Definition: Given a simple point measure μ on Rd and a point xRd,the Voronoi cell Cx(μ)=Cx of the point xRd w.r.t μ is defined to be the set

Cx(μ)={yRd:|yx|<infxiμ,xix|yxi|}E2

The Voronoi cell is often defined as the closure of the last set. Given a simple point process Φ=iεxi on Rd, the Voronoi Tessellation (VT) generated by Φ is defined to be the marked point process[6].

ν=iε(xi,Cxi(Φ)xi)E3

Fig.5 depicts the Voronoi tesselation. The points in Voronoi cell are nearer to the corresponding object, which generates the Voronoi cell, rather than the other objects.

Figure 5.

Sample of Voronoi tessellation

A weighted Voronoi diagram is that we assign distinct weight to generator points of normal Voronoi Tessellations and it is more applicable under some situations. A Voronoi region Vi is the intersection of the dominance regions of pi over every other generator point in P. While we will have different formulae for dominance regions in weighted Voronoi diagrams, the idea remains the same. The dominance region of a generator point pi over another, pj, where ij and dw(px,py)is the weighted distance between points x and y, is written as

Domw(pi,pj)={p|dw(p,pi)dw(p,pj)}E4

Let

Vw(pi)=pjP\{pi}Domw(pi,pj)E5

Vw(pi) is called as a weighted Voronoi region and Vw={Vw(p1),Vw(p2),...,Vw(pn)} is called as the weighted Voronoi diagram [7].

3.2. Stochastic modeling

The cells served by base stations in mobile communications are far from the regular hexagonal shape which is often taken as a reference model. Then Voronoi tessellation and other knowledge of stochastic geometry will be helpful in analysis.

3.2.1. Basic cell model

In this model, assume the network is just a single hierarchical level, and all subscribers are served by the closest BS, where the Voronoi tessellation method is taken. Considering the configuration of the subscribers, the distribution of BS usually obeys stochastic point process. For the simplicity of analysis, such processes can be considered as Point possion processes.

Take two independent Poisson processes Π0 and Π1 as an example, Π0 and Π1represent the subscribers and the stations respectively. The parameters of this model come to be the intensity measures Λ0 and Λ1 of two processes. As the density of subscribers is bigger than the one of base stations, we can assume Λ0=αΛ1 for someα>>1. Fig.6. depicts the basic cell model, where the subscribers are connected with the base station of their corresponding Voronoi cell. The link between subscriber and base station is not shown in the picture.

Figure 6.

Basic cell model with a single hierarchical level of stations point: base station; *point: subscribers; blue line: cell boundary

3.2.2. Hierarchical model

In this model there are several tiers of stations, and the processes of these tiers are thought to be independent with the decreasing intensity λ0>λ1>>λN. We can assume stations of tier i are represented by a realization of a homogeneous Poisson process Πi [8-9].

A real wireless network is more complex.But we can separate it from several tiers, such as macro BSs, pico BSs and femto BSs. BSs are independent from each tier.In this model, there’s no connection between each tier. Fig.7. depicts a three tiers model. In this three tiers model, BSs of different tiers are not connected.

Figure 7.

Three tiers mode Macro BSs: points; femto BSs: x points; pico BSs: * points; line: macrocell boundary

Classical methods of communication theory are generally insufficient to analyze new types of networks, such as ad-hoc and sensor works. Stochastic geometry allows us to study the average behavior over many spatial realizations of a network, whose nodes are placed according to some probability distribution. So, it is a good tool for the analysis of new type networks. As the model with stochastic geometry is constructed, it needs to analyze the network performance combined with actual scenarios, which enable to get the useful result we want. More details about the stochastic models and the use of stochastic geometry knowledge to derive theorems in these models will be researched in the future.

Advertisement

4. Frequency planning for BS design and siting

In LTE and its evolution system, many frequency planning schemes are derived from Soft Frequency Reuse (SFR) and Fractional Frequency Reuse (FFR). Kim et al[10]. propose an incremental frequency reuse (IFR) scheme that reuses effectively the radio spectrum through systematic segment allocation over a cluster of adjoining cells, which divides the entire frequency spectrum into several spectrum segments. Li et al[11]. give a cooperative frequency reuse scheme for coordinated multi-point transmission. Liang et al[12]. propose a frequency reuse scheme for OFDMA based two-hop relay enhanced cellular networks. Chen et al[13]. give an approach based on large-scale optimization to deal with networks with irregular cell layout. Wamser et al[14]. give some different strategies for user and resource allocation are evaluated along with fractional frequency reuse schemes in the uplink. Assaad et al[15]. give an analysis of the inter cell interference coordination problem and study the optimal fractional frequency reuse (FFR). Imran et al[16]. propose a novel self-organizing framework for adaptive frequency reuse and deployment in future cellular networks, which forms an optimization problem from spectral efficiency, fairness and energy efficiency. Novlan et al[17]. give a comparion of fractional frequency reuse approaches in the OFDMA cellular downlink, which mainly focuses on evaluating the two main types of FFR deployments, respectively Strict FFR and Soft Frequency Reuse (SFR).

However, the existing research mainly major in the form of application under different cellular scenarios, but lack of analyzing the theoretical basis for each frequency reuse scheme. It’s important to find some necessary theories to guide the design of frequency reuse scheme. Considering this problem, this paper makes an analysis of frequency reuse theoretical basis from four angles, respectively multigraph theory, algebraic analysis principle, extension theory and Stackelberg theory. By means of the above theoretical tools, we try to summarize the rules of frequency reuse design, give a way to find the optimal frequency reuse scheme. Furthermore, a soft fractional frequency reuse (SFFR) scheme is introduced, including two parts: SFFR I and SFFRⅡ.

The rest of this part is organized as follows: The multigraph theory, algebraic analysis principle, extension theory and Stackelberg theory are respectively introduced in Section 4.1, Section 4.2, Section 4.3 and Section 4.4. The soft fractional frequency reuse scheme is described in Section 4.5. Then the numerical results are analyzed in Section 4.6.

4.1. Multigraph theory

In [18], the coloring method in graph theory and the collection idea are taken into frequency reuse sets, dividing cellular users into different sets and providing a unique frequency reuse strategy to each set, which efficiently raise cellular frequency reuse factor. Ref.[19] adopts graph theory to discuss the problem of frequency allocation optimization, proposes a k-level interference-limited theory for the whole frequency sets. Moreover, it establishes an optimization model for frequency allocation. Ref.[20] analyzes the cellular frequency planning by multigraph T-coloring method. In graph theory, the concept of multigraph means that every pair of points is at most connected with K edges, also without no self-loop, such graph is written as K-multigraph. The concept of T-coloring can be defined as: In graph G, color each point in the set V(G) by T classes of colors, and the colors are different among each adjacent point, written as T-coloring in G graph. Ref.[21] describes some basic characteristics of frequency allocation in T-coloring. In view of graph theory in frequency optimization, we further analyze the frequency reuse optimization problem using multigraph coloring theory and k-level interference-limited theory.

Assume each cellular cell cluster is divided into n limited districts {a1,a2,,an}, and allocate the frequency f(ai) into each district ai. For the reuse of co-frequency resources, the level of interference is always different among districts due to the path loss of inter-cell interference. As shown in Fig.8., the co-frequency interference strength of No. 0 cell to its adjacent cell is inversely proportional to the path distance. By multigraph theory, the interference level can be mapped into interval according to the strength, which enables to optimize the frequency allocation.

Figure 8.

Inter-cell interference level

As shown in Fig.9., in order to analyze the inter-cell co-frequency interference, the interference strength in different districts is divided into several intervals by the descending range {[i1,i2],[i2,i3],,[im1,im]}, which map into each interference level l:{l1,l2,,lm}.

Figure 9.

Inter-cell interference level mapping

When District au and District av exist the interference with the same level, the frequency allocation in this area should satisfy:

{au,av}E|f(au)f(av)|T(l)E6

In particular, when K = 2, T(l0)={0}, which means the interference among au and av are the level l0. In order to optimize frequency allocation, it’s necessary to allocate different frequency among au and av. When K=2, T(l1)={0,1}, it means the interference among au and av are in the level l1, so the frequency allocation for such two area should not only satisfy difference, but also not adjacent.

Furthermore, we consider K different cells {G0,G1,,GK1}, and the number of frequency allocation area is V(G) for each cell. Moreover, the co-frequency interference among au and av are with the same level l. For inter-cell interference level l, we define the taboo collection T(l) for frequency allocation, as follows:

G0G1GK1E7
T(0)T(1)T(K1)E8

In the view of graph theory, the frequency reuse aims to allocate frequency into each point in multigraph, find the allocation function f to make the co-frequency interference minimum. Moreover, it enables to color the entire cell {G0,G1,,GK1} by T(l) color. In other words, the formula (4-1) is established under the function f.

4.2. Principles of algebraic analysis

Based on the multigraph theory, we propose an algebraic analysis method for frequency reuse, which change the relationship of cellular frequency reuse factor into quantitative algebra analytic formula, taking two-dimensional coordinates to solve this frequency reuse optimization problem.

Figure 10.

Cellular frequency reuse

As shown in Fig.10., considering soft frequency reuse (SFR), taking No.0 Cell as an example, we define the cell-center region 0C (0 Center, simply written as 0C) as variable y, the cell-edge region 0E (0 Edge, simply written as 0E) as variable x. In this way, we take two-dimensional coordinates to analyze the function of x and y. Since 0C is in the cell-center region, its maximum value of frequency reuse factor (FRF) is equivalent to 1, so the variable y should satisfy:

0<y1E9

0E is in the cell-edge region and its FRF is related with relevant partition way for cell-edge. When its FRF takes 1/k (k=3, 7… n), the variable should satisfy:

0<x1kE10

For 0C and 0E are still in the same cell, the total sum of FRF for the whole cell should be not more than 1, that is

0<x+y1E11

At the same time, when there’s not divided for cell-center and cell-edge, the total FRF can be expressed as

0<x+y1kE12

Figure 11.

Frequency reuse frequency reuse factor coordinates

Based on the above analysis, as shown in Fig.11., we take the sub-function as follows:

{0<x+y1,0<x1k,0<y10<x+y1k,0<x1k,0<y1kE13

The Algebraic analysis approach opens a new way to the analysis of cellular frequency reuse and optimization. Based on this idea, 0C and its reuse region {1E, 2E, 3E, 4E, 5E, 6E}, 0E and its interference region {1E, 2E, 3E, 4E, 5E, 6E} can be described into a form of two-dimensional coordinates, which enables to theoretically search the optimal cellular frequency reuse scheme.

4.3. Extension theory in frequency allocation

The frequency allocation in cellular systems could be modeled as the extension set in extension theory [22], by means of which we establish multi-dimensional cell-edge element model. Assume Nij denotes as the part of cellular area, written as(i_,j). cm denotes as the available probability for frequency set fm in Nij, written as cm(Nij){±1,0}. On the other hand, cm(Nij)=±1respectively means whether fm is taken in Nij, while cm(Nij)=0 means the critical state. According to the analysis of the inter-cell interference situation in cell-edge, cm(Nij) could be defined as:

  1. Initializationcm(Nij)=0

  2. If m=j, then cm(Nij)=1, and assign the sub-frequency setfj into Nij

  3. According to cm(Nij)×cm(Nji)=1, determine the other cm(Nij) values, making the co-frequency set not be reused in the adjacent cell-edge area, enabling to reduce the inter-cell interference.

On this basis, it can be obtained:

cm(Nij)={1,m=j1,m=i0,othersE14

Therefore, the n-dimension element model is established for the cell-edge sub-frequency set in Nij, that is:

Rij=[Nij,c1,c1(Nij)c2,c2(Nij)cn,cn(Nij)]E15

Define the correlation function in the extention set as:

K(cm(Ri))=j=1ncm(Nij),ijE16

where j=1ncm(Nij) denotes as the number of cell-edge area blocks. K(cm(Ri))>0 means fmavariable in Cell i, K(cm(Ri))<0 means fm unavariable in Cell i and K(cm(Ri))=0 means the critical state for fm. Based on the above analysis, the extention function is defined as:

TkK(cm(Ri))=K(cm(Ri))×(j=1,jincm(Nji))E17

Where j=1,jincm(Nji) represents the cell block area adjacent to the edge of the frequency of collection can be used in the area blocks. By means of extension theory, the frequency allocation in cellular system could be modeled by element model and multi-element extension set, enabling to frequency allocation optimization.

4.4. Stackelberg theory in frequency allocation

Recently, cellular cooperative communication for multiple base stations and multiple users is drawing attention as a solution to achieve high system throughput in cell-edge, such as cooperative beam, cooperative resource control, cooperative transmission, cooperative relaying, etc. As shown in Fig.12., it gives the network topology of cellular cooperative communication system, where several access points (AP) are connected into eNodeB and some cell-edge users are served by the cooperative AP. Moreover, as discussed in standardizing groups of IMT-advanced, cooperative communication technologies are expected to be essential in the next generation cellular networks. In this section, we consider taking Stackelberg theory to solve frequency allocation problem in OFDMA-based cooperative cellular systems.

Figure 12.

Cellular cooperative communication system

In 1952, Stackelberg [23] presented master-slave hierarchical decision-making issues, also known as Stackelberg problem. Its basic features include: Several independent decision-makers in decision-making, and each decision makers own some controlled decision variables. Some decisions by decision-maker may affect with each other. The decision-making system is always with a hierarchical structure and many decision-makers distribute at different decision-making levels (Fig.13.). The decision could be adjusted from upper decision-maker to lower decision-maker according to self-decision objective. Also, the decision by lower decision-maker affects upper decision-maker. Moreover, master-slave relationship exists among upper/lower decision-maker, and the optimum decision should satisfy both upper and lower decision-maker.

Figure 13.

Stackelberg problem

Master-slave model with single-objective decision-making

Maxx U0(x,y)      s.t(x,y)Ω0           Maxy U1(x,y)                   s.t(x,y)Ω1E18

where x, Ω0, U0(x,y) are the main decision variables, constraint set and utility function for the master. y, Ω1, U1(x,y) are the decision variables, constraints set and utility function for the slave. Usually, Stackelberg problem is with no-convex properties, including two categories: general two decision-making algorithm and two linear optimization algorithm. For the former, the algorithms based on penalty function and KKT conditions can be taken. For the latter, the algorithms based on KKT conditions and linear programming optimization can be taken.

Furthermore, we summarize the mathematical model of cooperation communication into Stackelberg problem: the primary unit L is decision-maker, the cooperative unit Fi is policy maker, and the number of cooperative nodes is NL, meeting i=1,...,NL. The uplink of UE j and Fi is written as i. the utility is written as Uij. By solving the maximum utility value, it can effectively solve the uplink power control problem based on Stackelberg equilibrium for cooperative communication, especially uplink power control problem based on Stackelberg equilibrium for cooperative communication.

4.5. Soft fractional frequency reuse

As shown in Fig.14., the characteristics of soft fractional frequency reuse (SFFR) scheme I is given as follows: the whole cell is divided into two parts, cell-center and cell-edge. In cell-center, the frequency reuse factor (FRF) is set as 1, while in cell-edge FRF is dynamic and the frequency allocation is orthogonal with the edge of other cells, which can avoid some inter-cell interference in cell-edge. On the other hand, users in every cell are divided into two major groups according to their geometry factor: cell-edge users who are interference-limited and caused by the neighboring cells, and cell-center users who are noise-limited. The available frequency resources in cell-edge are divided into some non-crossing subsets in SFFR I.

Since the cell-edge users are easily subject to serious interference, the frequency assignments to the cell-edge users greatly rely on radio link performance and system throughputs. Generally, the cell-edge can be split into 12 parts marked by 1, 4 and 9, just as the cell-edge of Cell 1 in Fig.7. For three adjacent cells, there are 9 parts in the cell-edge corner, which are in the shaded area. Moreover, we take this SFFR I model as an example to deduce the design of the available frequency band assignment for the fields marked by 1,2,..,9. In cell-edge, select frequency from the subsets u1, u2 , u3. If it’s not enough, add frequency from u4, u5 , u6. If inter-cell interference becomes serious, increase frequency in u4, u5, u6, and decrease the cover area in cell-edge. When the interference is controlled in a low extension, decrease the frequency in subsets of u4, u5, u6, and increase the cover area in cell-edge, enabling to improve the frequency utilization.

Figure 14.

Example of SFFR I scheme

As shown in Fig.15., the users in cell of SFFR II scheme are also divided in to two groups, respectively cell-center users and cell-edge users. Moreover, the available sub-carriers are divided into two no-overlapping parts: G and F. Besides, G is the available sub-carriers for cell-center users. Moreover, the FRF in cell-center is 1. F is the available sub-carriers for cell-edge uers, which is divided into 3 orthogonal parts, respectively u1, u2, u3, enabling to avoid inter-cell interference.

Figure 15.

Example of SFFR II scheme

4.6. Performance analysis

4.6.1. Performance analysis with increased users for SFFR

Fig.16. shows the system throughputs as the number of users increases, respectively for SFFR I and SFFR II when FRF is equal to 2/3. Fig.17. shows the average rates for cell-edge and cell-center users. Moreover, the ratio of inner radius and cell radius is 0.8. Some analysis results about Fig.16. and Fig.17. are given as follows:

Figure 16.

The system total throughputs(FRF = 2/3)

Figure 17.

The average rates in cell-center and cell-edge (FRF = 2/3)

  1. As shown in Fig.16, the system throughputs increase with the number of users increasing for such two SFFR schemes, but the gradient of the above curves decreases. The reason is that the probability of co-frequency intercell interference may increase as the users increase. As the sub-carrier resources are taken up, the throughputs become saturated or even decreased. On the other side, the blocking probability also increases for there’s no available sub-carriers allocated to the new users, which makes the actual number of users may not be increased.

  2. As shown in Fig.17, the cell-edge and cell-center average rates gradually decrease as the users increase. The reason is that the inter-cell interference increases, making the C/I decrease and users’ performance degrade. Similarly, partial users may be blocked for there’s not enough sub-carriers be allocated, making the average rates decrease.

  3. With the comparison of such two schemes, for FRF is equal to 2/3, SFFR II is better than SFFR I in the performance of total throughputs and cell-edge average rates, while the cell-center average rates is similar for SFFR II and SFFR I. In the SFFR I scheme, there’s overlap for the frequency allocation in cell-edge, while the different frequency sub-carriers are allocated into cell-edge users for the SFFR II scheme. Under this background, the co-frequency interference for cell-edge users is worse in SFFR I scheme than SFFR II scheme.

In addition, the cell-center users in the SFFR I scheme could take use of the available sub-carriers in cell-edge, reducing the blocking probability. At the same time, it makes cell-edge users be interfered more from the adjacent cell-center users. Because of the difference of frequency resource assignments, the performance in cell-edge is better in SFFRII than in SFFR I. On the other hand, it’s flexible for the SFFRII scheme, which could decrease the blocking probability in cell-center users for lack of sub-carriers. When the load is small, the cell-center Performance may be a little better in SFFRII than in SFFR I, but as the number of users increases, the performance of such two schemes gradually reach to similar level. In a whole, the total throughputs in SFFRII are more than in SFFR I.

4.6.2. Performance analysis with increased FRFs for SFFR

The total throughputs, cell-edge average rates and cell-center average rates for SFFR I and SFFRII are respectively given in Fig.18., Fig.19. and Fig.20., where the ratio of inner radius and cell radius is 0.8 and the number of users per cell is 65.

It can been seen from Fig.18, Fig.19 and Fig.20 that as the increase of FRF, both the total throughputs and the cell-center average rates increase, while the cell-edge average rates decrease. One reason is that for cell-edge users, the number of available sub-carriers in cell-edge decreases with the FRF increasing, which makes partial cell-edge users not be allocated to enough sub-carriers and be blocked further. On the other hand, more sub-carriers could be allocated to cell-center users, reducing the inter-cell interference and improving the average rates. Moreover, the average rates in cell-center are higher than in cell-edge. On the contrary, with the FRF decreases, the available sub-carriers in cell-edge increase, while decrease in cell-center. As a result, the performance is improved for cell-edge users, while degraded for cell-center users. In order to balance the spectrum efficiency and cell-edge performance, it’s necessary to set an appropriate FRF value for cellular system.

When the FRF is in a small value, the available sub-carriers decrease in cell-center, which make the cell-center performance of SFFR I scheme show better than SFFRII scheme. However, the cell-edge performance of SFFR I shows worse than SFFRII for more sub-carriers are reused in cell-center and the cell-edge users in SFFR I are interfered more seriously. On the contrary, When the FRF is in a large value, the available sub-carriers increase in cell-edge, which make the cell-edge performance of SFFR I scheme show better than SFFRII scheme, but the cell-center performance of SFFR I shows worse than SFFRII. According to the analysis, it can be taken SFFR I scheme when FRF is large, while taken SFFRII scheme when FRF is small.

Figure 18.

Cellular throughputs of different FRFs (2/3, 7/9, 8/9)

Figure 19.

Cell-edge average rates of different FRFs (2/3, 7/9, 8/9)

Figure 20.

Cell-center average rates of different FRFs (2/3, 7/9, 8/9)

4.6.3. Performance analysis of SFFRⅡ

As shown in Fig.21, with the inner radius increasing, the number of cell-edge user decreases, making its average rate increasing, improving the performance of cell-edge user. The larger the FRF is, the better the performance is.

Figure 21.

The average rate for cell-edge user (SFR)

As shown in Fig.22., with the inner radius increasing, more users are classified as cell-center users. For each fixed FRF, the frequency resources in cell-center is relatively constant, the increase of cell-center users may lead to insufficient resource allocation and larger co-frequency interference, so the average rate for cell-center user will decrease as the inner radius increases.

Figure 22.

The average rate for cell-center user (SFR)

Therefore, it needs to take into account the size of FRF, both cell-edge and cell-center performance to choose the appropriate inner radius. With the FRF increasing, the inner radius should be increased, making a rational division of cell-center users and cell-edge users.

Advertisement

5. Conclusions

In this chapter, the general BS design and siting method is introduced, which gives the general process of BS planning and the estimation method of BS number. Then, the basic theory about stochastic geometry is introduced in BS design and siting, respectively Poisson point process and Voronoi tessellation. Moreover, the stochastic modeling principle is also given for BS design and siting, respectively basic cell model and hierarchical model. Besides, this chapter gives an analysis on the frequency planning scheme in BS design and siting, and tries to find the theoretical basis of frequency planning from four parts, respectively multigraph theory, algebraic analysis principle, extension theory and Stackelberg theory.

In graph theory, we focus on coloring theory in multigraph and the level interference-limited theory, making an analysis of optimization problem in frequency reuse. In algebraic analysis principle, this proposal gives a quantitative analytic algebra to describe the relationship of frequency reuse factor between cell center and cell edge, and the frequency reuse optimization problem can be transformed into two-dimensional coordinate system, which enables to consider analytic algebra method to solve it. In extension theory analysis, the multi-dimensional cell-edge element model is established and the results show that frequency allocation in cellular system could be modeled by element model and its multi-element extension set. In Stackelberg theory, we formulate the frequency optimization in cooperative communication into Stackelberg problem and establish a Stackelberg model for this architecture.

On the basis of the above theoretical analysis, a soft fractional frequency reuse (SFFR) scheme is presented, including two parts: SFFR I and SFFRII. Moreover, the simulation is taken to compare SFFR performance with different FRF schemes, and the results show that it can be taken SFFR I scheme when FRF is large, while taken SFFRII scheme when FRF is small. Furthermore, it needs to take into account the size of FRF, both cell-edge and cell-center performance to choose the appropriate inner radius. In the future, we would further take Monte Carlo system simulation to compare different frequency reuse schemes and find the optimal scheme according to the proposed method.

Advertisement

Acknowledgments

This research is supported by National Natural Science Foundation Project of China (No. 61101084), State Key Laboratory of Networking and Switching Technology Open Project (No. SKLNST-2011-1-02) and the Fundamental Research Funds for the Central Universities.

References

  1. 1. Barłomiej Błaszczyszyn, Paul Mühlethaler, Yasser Toor. Stochastic analysis of Aloha in vehicular ad hoc networks, Annals of Telecommunications, Springer-Verlag, 2012.
  2. 2. Franc¸ois Baccelli and Bartłomiej Błaszczyszyn. Stochastic Geometry and Wireless Networks Volume II:Applications, Foundations and trends in networking, Now Publishers, 2009.
  3. 3. Ki Tae Kim, Seong Keun Oh. An Incremental Frequency Reuse Scheme for an OFDMA Cellular System and Its Performance. IEEE Vehicular Technology Conference-Spring, pp.1504-1508, 2008.
  4. 4. M.Haenggi, J.G.Andrews, F.Baccelli, O.Dousse, M.Franceschetti. Stochastic Geometry and Random Graphs for the Analysis and Design of Wireless Networks, IEEE Journal on Selected Areas in Communications, vol.27, no.7, pp.1029-1046, 2009.
  5. 5. Salman Malik, Alonso Silva, Jean-Marc Kelif. Optimal Base Station Placement: A Stochastic Method Using Interference Gradient In Downlink Case, Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, pp.66- 73, 2011
  6. 6. Francois Baccelli and Bartłomiej Błaszczyszyn. Stochastic Geometry and Wireless Networks: Theory, Foundations and Trends in Networking, vol.3, no.3-4, pp.249-449, 2009.
  7. 7. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Dr Sung Nok Chiu. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley Series in Probability and Statistics, vol.501, John Wiley & Sons, 2009.
  8. 8. François Baccelli, Maurice Klein, Marc Lebourges and Sergei Zuyev, Stochastic geometry and architecture of communication networks, Telecommunication Systems, vol.7, no.1-3, pp.209-227, 1997.
  9. 9. Bartłomiej Błaszczyszyn, Paul Muhlethaler. Stochastic Analysis of Non-slotted Aloha in Wireless Ad-Hoc Networks, IEEE Infocom, 2010.
  10. 10. Hui Zhang, et al. Frequency Reuse Analysis Using Multigraph Theory, International Conference on Green Communications and Networks, 2011.
  11. 11. Jingya Li, Hui Zhang, Xiaodong Xu, et al. A novel frequency reuse scheme for coordinated multi-point transmission. IEEE Vehicular Technology Conference-Spring, pp.1-5, 2010.
  12. 12. Min Liang, Fang Liu, Zhe Chen, et al. A novel frequency reuse scheme for OFDMA based relay enhanced cellular networks. IEEE Vehicular Technology Conference-Spring, pp.1-5, 2009.
  13. 13. Lei Chen, Di Yuan. Generalized frequency reuse schemes for OFDMA networks: optimization and comparison. IEEE Vehicular Technology Conference-Spring, pp.1-5, 2010.
  14. 14. F.Wamser, D.Mittelsta, D.Staehle. Soft frequency reuse in the uplink of an OFDMA network. IEEE Vehicular Technology Conference-Spring, pp.1-5, 2010.
  15. 15. M.Assaad. Optimal fractional frequency reuse (FFR) in multicellular OFDMA system. IEEE Vehicular Technology Conference-Fall, pp.1-5, 2010.
  16. 16. A.Imran, M.A.Imran, R.Tafazolli. A novel self organizing framework for adaptive frequency reuse and deployment in future cellular networks. IEEE International Symposium on Personal Indoor and Mobile Radio Communications, pp. 2354-2359, 2010.
  17. 17. T.Novlan, J.G.Andrews, Sohn Illsoo, et al. Comparison of fractional frequency reuse approaches in the OFDMA cellular downlink. IEEE Global Telecommunications Conference, pp.1-5, 2010.
  18. 18. 3GPP R1-050896, Description and simulations of interference management technique for OFDMA based E-UTRA downlink evaluation, Qualcomm, 2005.
  19. 19. W K Hale. Frequency assignment: theory and applications. Proc. of The IEEE, vol.68, no.12, pp.1497-1514, 1980.
  20. 20. Du Juan, Zhang Yu-qing, Zhan Su-juan. An algorithm to compute the span of the T-Colorings of multigraphs. Journal of the Hebei Academy of Sciences. vol.23, no.3, pp.1-4, 2006.
  21. 21. 3GPP R1-050738, Interference mitigation considerations and results on frequency reuse. Siemens, 2005.
  22. 22. Cai Wen. Extention Theory. Beijing: Science Press, pp.69-77, 2003.
  23. 23. Victor DeMiguel, Huifu Xu. A Stochastic Multiple-Leader Stackelberg Model. Operations Research, vol.57, no.5, pp.1220-1235.

Written By

Hui Zhang, Yifeng Xie, Liang Feng and Ying Fang

Submitted: 06 August 2012 Published: 13 February 2013