# Joint Radio Resource Allocation and Base Station Location Selection in OFDMA Based Private Wireless Access Networks for Smart Grid

Authors: Peng Du; Yuan Zhang
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

This paper studies the base stations deployment problem in orthogonal frequency-division multiple access (OFDMA) based private wireless access networks for smart grid (SG). Firstly, we analyze the differences between private wireless access networks for SG and public cellular access networks. Then, we propose scheduling and power control based algorithms for the radio resource allocation subproblem andK-means, simulated annealing (SA), and particle swarm optimization (PSO) based algorithms for the base station (BS) location selection subproblem and iterate over these two sets of algorithms to solve the target problem. Simulation results show that the proposed method can effectively solve the target problem. Specifically, the combination of power control based resource allocation algorithm and PSO based location selection algorithm is recommended.


---

## Body

## 1. Introduction

It is critical that the underlying communication technology shall support efficient data exchange between various domains comprising smart grid (SG) [1]. This paper studies the orthogonal frequency-division multiple access (OFDMA) [2] based private wireless access networks for SG. Actually, wireless technologies can be used in the grid for monitoring, metering, and data gathering [3–17]. Specifically, SG devices such as switching station, distribution circuit, and distributed energy sites will produce various information data and send them periodically to the base station (BS) to realize the automation of power distribution and electricity information acquisition. In order to achieve this requirement, many technical problems need to be solved. Among them, this paper addresses the problem of how to optimize the deployment of BSs.This problem has been extensively studied in the literature for the public cellular access networks. However, the scenario of private wireless access networks for SG is quite different from that of the public cellular access networks.Property 1 (the locations of devices can be considered as fixed).
Due to the peculiarity of SG, the locations of most power devices can be considered as fixed or quasi-fixed.Property 2 (the uplink transmission is dominant [18, 19]).
The smart grid network is an uplink dominated network, as the main data flow is from power devices to control center. The most often requirement of communications in SG is devices periodically reporting status monitoring data to the control center via BSs. Therefore, the direction of most data transmissions will be uplink.Property 3 (the transmission rate requirement of devices can be considered as fixed [19]).
The communications happening in the SG belong to the type of machine-to-machine (M2M) communications and the uplink data transmission rate requirement of each device can be considered as fixed or quasi-fixed.Property 4 (the frequency separation requirement [19]).
Wireless networks are more vulnerable than their wired counterparts due to the potential for direct access to the transport medium. Hence, security must be considered at every layer of the protocol stack in the private wireless access networks for SG. In addition to the authentication, authorization, and encryption considered at the application layer, the frequency separation mechanism at the physical layer shall also be considered, which is explained as follows. Actually, data produced by different types of devices in smart grid shall be transmitted to different destination systems. For example, as shown in Figure1, the data produced by data terminal unit (DTU) shall be transmitted to the production service system, while the data produced by video terminal unit (VTU) shall be transmitted to the management service system. Due to the security purpose, the transmission paths used by different types of data shall be separated as much as possible. The separation can be achieved physically or logically. For example, four different approaches to construct the access network are illustrated in Figure 1, where the data paths in Figure 1(a) are the most separated; that is, the separation is achieved physically, while the data paths in Figure 1(d) are the least separated; that is, the separation can be achieved logically. Further, in addition to the separation for the wireline segment, data transmission over the wireless segment of data path shall also be separated for different types of devices. This requires that different types of devices shall use different frequency channels to transmit their data; that is, different types of devices sharing the same frequency channel will not be allowed. This is the frequency separation requirement considered in this work.Figure 1
The separation requirement.
(a)
(b)
(c)
(d)As a first step towards addressing the above issues, this paper investigates the problem of how to deploy BSs and allocate wireless resources so that the uplink transmission requirements are efficiently met. For this problem, we propose to decompose it into the resource allocation subproblem and the location selection subproblem and solve these two subproblems in an iterative fashion. The remainder of the paper is organized as follows. Section2 formulates the joint resource allocation and location selection problem. Section 3 presents the overall framework to address this problem. Sections 4 and 5 propose resource allocation and location selection algorithms, respectively. Simulation results are reported in Section 6. Finally, we conclude in Section 7.


## 2. Problem Formulation

Consider a set of SG devices scattered in an areaΨ. Let H denote the set of devices. For each device j
∈
H, let C
j denote the minimum uplink data rate requirement and P
j the uplink transmission power. The value of P
j shall satisfy 0
≤
P
j
≤
P
m
a
x, where P
m
a
x is the upper bound. For convenience, let C
=
{
C
j
} and P
=
{
P
j
}, respectively. Assume that all devices are classified into K different types. Let H
i denote the set of type-i SG devices, 1
≤
i
≤
K.Assume that the private wireless access network consists ofB BSs which are located in the area Ψ. Let z
b
=
(
z
b
1
,
z
b
2
) denote the deployment location of the bth BS, 1
≤
b
≤
B, where z
b
1 and z
b
2 are the horizontal and vertical ordinate of the deployment location, respectively. For convenience, let z
=
{
z
b
}. Not every location in Ψ can be the candidate location for BS. Assume that Θ denotes the candidate BS location set in Ψ and the deployment location of BS can only be selected from the elements of Θ. That is, we restrict z
b
∈
Θ. In addition, let Ω
=
{
S
1
,
S
2
,
…
,
S
B
} denote the relationship between SG devices and BSs, where S
b is the set of devices served by the bth BS. For simplicity and without loss of generality, we assume that the value of S
b is determined by the distance based rule. That is, a device will be served by the BS which is the closest to it.Consider a OFDMA based private wireless access network. The radio resource is defined as follows. In the frequency domain, assume that the total bandwidth is divided intoN channels. Let W and W
0 denote total and channel bandwidth in Hertz, respectively. In the time domain, assume that the time axes are organized into consecutive slots and L
0 consecutive slots constitute a frame. The basic resource unit for data transmission is a resource block (RB) which is defined as one channel in the frequency domain and one slot in the time domain, respectively. In each frame, assume that L slots can be used for uplink communications. Therefore, for each channel, there are L RBs which are allocatable. Finally, define binary variable Y
n
,
l
,
j to denote the results of radio resource allocation which is valued 1 if the lth RB of the nth channel is allocated to device j and 0 otherwise. Each device shall be allocated a number of RBs to meet its minimum data rate requirement. For convenience, let Y
=
{
Y
n
,
l
,
j
}.Given that the RB(
n
,
l
) has been allocated to device j, the received signal-interference-noise-ratio (SINR) experienced by device j on this RB at BS b can be written as(1)
γ
n
,
l
,
j
=
P
j
G
j
b
P
N
+
P
I
,where G
b
j is the path loss from device j to BS b, P
N is the power of background noise, P
I
=
∑
k
≠
j
,
k
∈
D
n
,
l
‍
P
k
G
k
b is the power of interference, and D
n
,
l is the set of devices which share the same RB with device j. For simplicity and without loss of generality, we assume that the path loss mainly depends on the distance and can be calculated according to the formula P
L
(
x
) for a distance separation of x meters and we assume that there is no interference between distant devices. Let C
^
n
,
l
,
j denote the uplink data rate achieved by device j on RB (
n
,
l
) which is calculated by the Shannon formula as(2)
C
^
n
,
l
,
j
=
W
0
l
o
g
1
+
γ
n
,
l
,
j
L
0
.Then, the total data rate achieved by device j, denoted as C
^
j, can be calculated as(3)
C
^
j
=
∑
n
,
l
:
Y
n
,
l
,
j
=
1
C
^
n
,
l
,
j
.For convenience, let C
^
=
{
C
^
j
}.Finally, the problem addressed in this paper can be formulated as, given the parametersΨ, H, C, K, {
H
i
}, P
m
a
x, B, Θ, W, W
0, N, L
0, and L, how to determine the values of deployment location z, transmission power P, and radio resource allocation Y, so that the achieved data rate C
^ approaches C as much as possible. The symbols used in this paper are summarized in List of Symbols.


## 3. The Framework

It is difficult to solvez, P, and Y simultaneously. Therefore, we decompose the problem into two subproblems. The first is the location selection subproblem which determines z; the second is the resource allocation subproblem which determines P and Y. Specifically, the resource allocation subproblem determines P and Y based on z produced by the location selection subproblem. Then, the payoff of the current z is calculated. Let V denote the payoff of a given z.The general expression of the payoff function can be written as(4)
V
=
∑
j
U
j
C
^
j
-
I
j
P
j
,where U
j
(
·
) is an increasing function representing the utility of device j and I
j
(
·
) is also an increasing function representing the cost of device j. In this paper, we firstly let U
j
(
C
^
j
)
=
C
^
j
/
C
j, where C
j is the minimum uplink data rate requirement of device j. Secondly, since the locations of devices in smart grid are fixed and the power can be supplied by alternating current adapter, we just let I
j
(
P
j
)
=
0. This is a difference between wireless communications for smart grid and for land mobile users. Therefore, we define the satisfaction ratio c
j of device j as the ratio between achieved data rate and required data rate; that is,(5)
c
j
=
C
^
j
C
j
,and we then define V as the sum of satisfaction ratio over all devices; that is,(6)
V
=
∑
j
c
j
,which is used to measure how good the given z is.The problem can be solved by solving these two subproblems in an iterative fashion. The value ofV for the current z will be fed back to the location selection subproblem for guided search of the better z. The next two sections will solve these two subproblems in sequence.


## 4. Resource Allocation Methods

The task of resource allocation is to determineP and Y given z. Two different methods based on different principles are presented. The first is scheduling based for which uplinks which are far away from each other are scheduled to share the same RB. The second is power control based for which the transmission power of each uplink is controlled so that uplinks which are not far away from each other can also share the same RB.


### 4.1. Scheduling Based Resource Allocation

This method consists of four steps, which are described in sequence as follows.


#### 4.1.1. Uplink Transmission Power Setting

This subsection determines the transmission powerP
j for each device j. As stated before, for this method, uplinks which are far away from each other (i.e., do not interfere with each other) will be scheduled to share the same RB. Therefore, for the scheduling based method, it can be expected that the interference power P
I in (1) is negligible. That is, we assume that there is no interference between distant devices. Thus, given the RB allocated to device j, the received SINR experienced by device j on this RB at BS b can be approximately written as(7)
γ
j
≈
P
j
G
j
b
P
N
≥
Γ
,where device j is served by BS b (i.e., j
∈
S
b) and Γ is the minimum SINR requirement. Γ is a system parameter and common to all devices and RBs. Therefore, the uplink transmission power P
j can be set to(8)
P
j
=
min
⁡
P
N
·
Γ
G
j
b
,
P
m
a
x
.That is, since in this method distant devices between which there is no interference are scheduled simultaneously, there is no power control and power is strictly a function of the target minimum SINR requirement.


#### 4.1.2. Interference Graph Construction

The interference graph is used to indicate whether any two devices can reuse the same RB due to the interference between them. As indicated by Property4, different types of devices shall transmit data over different channels. So we need to construct interference graph for each type, respectively. Let G
i
(
V
i
,
E
i
) denote the interference graph for the ith type, 1
≤
i
≤
K, where V
i is the vertex set in which each vertex represents a device of the ith type and E
i is the edge set in which each edge e
j
,
k represents devices j and k which cannot reuse the same RB. There are two rules to decide if edge e
j
,
k exists. Assume that devices j and k are served by BS b
j and b
k, respectively. The first rule is if b
j
=
b
k, then edge e
j
,
k exists. The second rule is if b
j
≠
b
k but the interference caused to each other is too large, then edge e
j
,
k exists. Specifically, if the distance between device j and BS b
k is less than the interference radius R
j of device j or if the distance between device k and BS b
j is less than the interference radius R
k of device k, then edge e
j
,
k exists.The calculation of interference radius is as follows. For devicej, the interference radius R
j is defined as the distance at which the received SINR is η, where η is the SINR requirement to ensure that the device does not cause nonnegligible interference to other uplinks that are out of the range of interference radius. According to (7), we have the equation for R
j as(9)
P
j
·
P
L
R
j
P
N
=
η
,from which the value of R
j can be solved. After calculating the interference radius for each device, the interference graph G
i can be constructed. The procedure is outlined in Algorithm 1, where d
i
s
(
j
,
b
) in line (6) represents the distance between device j and BS b.Algorithm 1:Interference graph construction.
Require: z.
Ensure: G
i, 1
≤
i
≤
K.
(1)    for  i
=
1 to K  do
(2)     for  any two devices j and k in H
i  do
(3)      if  b
j
=
b
k  then
(4)       connect vertexes j and k in G
i;
(5)      end if
(6)      if  d
i
s
(
j
,
b
k
)
<
R
j or d
i
s
(
k
,
b
j
)
<
R
k  then
(7)       connect vertexes j and k in G
i;
(8)      end if
(9)     end for
(10) end for


#### 4.1.3. Utility Function Calculation

For eachi
,
1
≤
i
≤
K, the utility function F
i
,
n is defined as the sum of satisfaction ratio over all devices of the ith type given that a total of n channels have been allocated to them. To calculate F
i
,
n, define Δ
F
i
,
n as the sum of satisfaction ratio over all devices of the ith type given that the nth channel has been allocated to them. Then the value of F
i
,
n can be obtained according to(10)
F
i
,
n
=
F
i
,
n
-
1
+
Δ
F
i
,
n
,where F
i
,
0
=
0. Further, to calculate Δ
F
i
,
n, define Δ
F
i
,
n
,
l as the sum of satisfaction ratio over all devices of the ith type given that the lth RB of the nth channel has been allocated to them. Then the value of Δ
F
i
,
n can be obtained according to(11)
Δ
F
i
,
n
=
∑
l
=
1
L
Δ
F
i
,
n
,
l
.Let H
i
,
n
,
l denote the set of devices of the ith type that share the lth RB of the nth channel. Then the value of Δ
F
i
,
n
,
l can be calculated as(12)
Δ
F
i
,
n
,
l
=
∑
j
∈
H
i
,
n
,
l
C
^
n
,
l
,
j
C
j
,where C
^
n
,
l
,
j can be obtained by (2). Finally, we say a device is feasible in slot l if the total power allocated to this device in this slot does not exceed P
m
a
x. The procedure to calculate utility function is outlined in Algorithm 2, where the set H
i
,
n
,
l is determined in a heuristic manner in lines (4)–(10).Algorithm 2:Utility function calculation.
Require: G
i, 1
≤
i
≤
K.
Ensure: F
i
,
n and H
i
,
n
,
l.
(1)    for  i
=
1 to K  do
(2)     for  n
=
1 to N  do
(3)      for  l
=
1 to L  do
(4)       initialize H
i
,
n
,
l
=
∅;
(5)       delete from G
i devices which are not feasible in slot l anymore;
(6)       while  G
i
≠
∅  do
(7)        determine device j
∗ with the lowest satisfaction ratio in G
i;
(8)        put j
∗ into H
i
,
n
,
l;
(9)        delete j
∗ and devices connected to it from G
i;
(10)    end while
(11)    calculate Δ
F
i
,
n
,
l;
(12)    recover G
i;
(13)    update satisfaction ratio of all devices in G
i;
(14)   end for
(15)   calculate Δ
F
i
,
n;
(16)   calculate F
i
,
n;
(17)  end for
(18) end for


#### 4.1.4. RB Allocation

This subsection presents the RB allocation algorithm. As indicated by Property4, due to the security consideration, different types of devices shall use different frequency channels and different types sharing the same frequency channel are not allowed. This is the constraint which channel allocation shall satisfy. The procedure of the scheduling based RB allocation is outlined in Algorithm 3, where n
i denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
,
n
,
l
} which has been obtained in Algorithm 2, as shown in line (6).Algorithm 3:Scheduling based RB allocation.
Require: F
i
,
n and H
i
,
n
,
l.
Ensure: Y
n
,
l
,
j.
(1) initialize n
i
=
0, 1
≤
i
≤
K;
(2) for  n
=
1 to N  do
(3)  allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)  let n
i
∗
=
n
i
∗
+
1;
(5)  for  l
=
1 to L  do
(6)   allocate the lth RB to devices in H
i
∗
,
n
i
∗
,
l;
(7)   let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
,
n
i
∗
,
l;
(8)  end for
(9) end for


### 4.2. Power Control Based Resource Allocation

This method consists of four steps, which are described in sequence as follows.


#### 4.2.1. Grouping

LetS
b
i denote the set of type-i devices which are served by BS b, 1
≤
i
≤
K. The value of S
b
i can be derived from the value of S
b, which can be derived from the value of z. Let H
i
=
{
H
i
1
,
…
,
H
i
g
,
…
,
H
i
G
i
} denote the grouping for the ith type, where H
i
g is the set of devices of the ith type which can share the same RB and G
i is the number of groups. The procedure of grouping is outlined in Algorithm 4.Algorithm 4:Grouping.
Require: z.
Ensure: H
i
g.
(1)    for  i
=
1 to K  do
(2)     let G
i
=
max
⁡
S
1
i
,
S
2
i
,
…
,
S
B
i;
(3)     for  g
=
1 to G
i  do
(4)      for  b
=
1 to B  do
(5)       if  S
b
i
≠
∅  then
(6)        select any device j from S
b
i and put into H
i
g;
(7)        delete device j from S
b
i;
(8)       end if
(9)      end for
(10)  end for
(11) end for


#### 4.2.2. Uplink Transmission Power Control

Since all devices inH
i
g share the same RB, the received SINR in (1) can be rewritten as(13)
γ
n
,
l
,
j
=
P
j
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
G
k
b
≥
Γ
,where j
∈
H
i
g and Γ is the minimum SINR requirement. Similarly, Γ is a system parameter and common to all devices and RBs.We propose an iterative update algorithm for finding the minimum transmission power satisfying the above equation. Specifically, for thetth iteration, the optimal power P
j
[
t
] to be used by device j can be obtained by solving the following equation:(14)
P
j
t
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
t
-
1
G
k
b
=
Γ
,where P
k
[
t
-
1
] is the power settings obtained at iteration t
-
1. According to (14), the value of P
j
[
t
] can be easily obtained using the bisection method [20]. Additionally, if the value of P
j
[
t
] is greater than P
m
a
x, it will be set as P
m
a
x. The update of the values of transmission power proceeds in iterations until the power convergence.


#### 4.2.3. Utility Function Definitions

The utility functionF
i
,
n
,
g is defined as the sum of satisfaction ratio over all devices in H
i
g given that a total of n channels have been allocated to them. To calculate F
i
,
n
,
g, define Δ
F
i
,
n
,
g
,
l as the sum of satisfaction ratio over all devices in H
i
g given that the first l RBs of the nth channel have been allocated to them. Then the value of F
i
,
n
,
g can be obtained according to(15)
F
i
,
n
,
g
=
F
i
,
n
-
1
,
g
+
Δ
F
i
,
n
,
g
,
L
,where F
i
,
0
,
g
=
0 and the value of Δ
F
i
,
n
,
g
,
L can be obtained according to(16)
Δ
F
i
,
n
,
g
,
l
=
Δ
F
i
,
n
,
g
,
l
-
1
,
∑
j
∈
H
i
g
Y
n
,
l
,
j
=
0
Δ
F
i
,
n
,
g
,
l
-
1
+
∑
j
∈
H
i
g
C
^
n
,
l
,
j
C
j
,
o
t
h
e
r
w
i
s
e
,where F
i
,
n
,
g
,
0
=
0 and 1
≤
l
≤
L.


#### 4.2.4. RB Allocation

This subsection presents the RB allocation algorithm. Similarly, different types of devices are not allowed to share the same frequency channel, which is the constraint which channel allocation shall satisfy.For convenience, we define functionF
i
,
n as(17)
F
i
,
n
=
∑
g
=
1
G
i
F
i
,
n
,
g
.In addition, we say a group H
i
g is feasible in slot l if the total power allocated to each device j
∈
H
i
g in this slot does not exceed P
m
a
x. The procedure of the power control based RB allocation is outlined in Algorithm 5, where n
i also denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
g
} which has been obtained in Algorithm 4, as shown in line (6).Algorithm 5:Power control based RB allocation.
Require: H
i
g.
Ensure: Y
n
,
l
,
j.
(1)    initialize n
i
=
0, 1
≤
i
≤
K;
(2)    for  n
=
1 to N  do
(3)     allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)     let n
i
∗
=
n
i
∗
+
1;
(5)     for  l
=
1 to L  do
(6)      select H
i
∗
g
∗ which is feasible in slot l and has the minimum Δ
F
i
∗
,
n
i
∗
,
g
,
l
-
1;
(7)      let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
g
∗;
(8)      calculate Δ
F
i
∗
,
n
i
∗
,
g
,
l for each g;
(9)     end for
(10)  calculate F
i
,
n
i for each i;
(11) end for


## 4.1. Scheduling Based Resource Allocation

This method consists of four steps, which are described in sequence as follows.


### 4.1.1. Uplink Transmission Power Setting

This subsection determines the transmission powerP
j for each device j. As stated before, for this method, uplinks which are far away from each other (i.e., do not interfere with each other) will be scheduled to share the same RB. Therefore, for the scheduling based method, it can be expected that the interference power P
I in (1) is negligible. That is, we assume that there is no interference between distant devices. Thus, given the RB allocated to device j, the received SINR experienced by device j on this RB at BS b can be approximately written as(7)
γ
j
≈
P
j
G
j
b
P
N
≥
Γ
,where device j is served by BS b (i.e., j
∈
S
b) and Γ is the minimum SINR requirement. Γ is a system parameter and common to all devices and RBs. Therefore, the uplink transmission power P
j can be set to(8)
P
j
=
min
⁡
P
N
·
Γ
G
j
b
,
P
m
a
x
.That is, since in this method distant devices between which there is no interference are scheduled simultaneously, there is no power control and power is strictly a function of the target minimum SINR requirement.


### 4.1.2. Interference Graph Construction

The interference graph is used to indicate whether any two devices can reuse the same RB due to the interference between them. As indicated by Property4, different types of devices shall transmit data over different channels. So we need to construct interference graph for each type, respectively. Let G
i
(
V
i
,
E
i
) denote the interference graph for the ith type, 1
≤
i
≤
K, where V
i is the vertex set in which each vertex represents a device of the ith type and E
i is the edge set in which each edge e
j
,
k represents devices j and k which cannot reuse the same RB. There are two rules to decide if edge e
j
,
k exists. Assume that devices j and k are served by BS b
j and b
k, respectively. The first rule is if b
j
=
b
k, then edge e
j
,
k exists. The second rule is if b
j
≠
b
k but the interference caused to each other is too large, then edge e
j
,
k exists. Specifically, if the distance between device j and BS b
k is less than the interference radius R
j of device j or if the distance between device k and BS b
j is less than the interference radius R
k of device k, then edge e
j
,
k exists.The calculation of interference radius is as follows. For devicej, the interference radius R
j is defined as the distance at which the received SINR is η, where η is the SINR requirement to ensure that the device does not cause nonnegligible interference to other uplinks that are out of the range of interference radius. According to (7), we have the equation for R
j as(9)
P
j
·
P
L
R
j
P
N
=
η
,from which the value of R
j can be solved. After calculating the interference radius for each device, the interference graph G
i can be constructed. The procedure is outlined in Algorithm 1, where d
i
s
(
j
,
b
) in line (6) represents the distance between device j and BS b.Algorithm 1:Interference graph construction.
Require: z.
Ensure: G
i, 1
≤
i
≤
K.
(1)    for  i
=
1 to K  do
(2)     for  any two devices j and k in H
i  do
(3)      if  b
j
=
b
k  then
(4)       connect vertexes j and k in G
i;
(5)      end if
(6)      if  d
i
s
(
j
,
b
k
)
<
R
j or d
i
s
(
k
,
b
j
)
<
R
k  then
(7)       connect vertexes j and k in G
i;
(8)      end if
(9)     end for
(10) end for


### 4.1.3. Utility Function Calculation

For eachi
,
1
≤
i
≤
K, the utility function F
i
,
n is defined as the sum of satisfaction ratio over all devices of the ith type given that a total of n channels have been allocated to them. To calculate F
i
,
n, define Δ
F
i
,
n as the sum of satisfaction ratio over all devices of the ith type given that the nth channel has been allocated to them. Then the value of F
i
,
n can be obtained according to(10)
F
i
,
n
=
F
i
,
n
-
1
+
Δ
F
i
,
n
,where F
i
,
0
=
0. Further, to calculate Δ
F
i
,
n, define Δ
F
i
,
n
,
l as the sum of satisfaction ratio over all devices of the ith type given that the lth RB of the nth channel has been allocated to them. Then the value of Δ
F
i
,
n can be obtained according to(11)
Δ
F
i
,
n
=
∑
l
=
1
L
Δ
F
i
,
n
,
l
.Let H
i
,
n
,
l denote the set of devices of the ith type that share the lth RB of the nth channel. Then the value of Δ
F
i
,
n
,
l can be calculated as(12)
Δ
F
i
,
n
,
l
=
∑
j
∈
H
i
,
n
,
l
C
^
n
,
l
,
j
C
j
,where C
^
n
,
l
,
j can be obtained by (2). Finally, we say a device is feasible in slot l if the total power allocated to this device in this slot does not exceed P
m
a
x. The procedure to calculate utility function is outlined in Algorithm 2, where the set H
i
,
n
,
l is determined in a heuristic manner in lines (4)–(10).Algorithm 2:Utility function calculation.
Require: G
i, 1
≤
i
≤
K.
Ensure: F
i
,
n and H
i
,
n
,
l.
(1)    for  i
=
1 to K  do
(2)     for  n
=
1 to N  do
(3)      for  l
=
1 to L  do
(4)       initialize H
i
,
n
,
l
=
∅;
(5)       delete from G
i devices which are not feasible in slot l anymore;
(6)       while  G
i
≠
∅  do
(7)        determine device j
∗ with the lowest satisfaction ratio in G
i;
(8)        put j
∗ into H
i
,
n
,
l;
(9)        delete j
∗ and devices connected to it from G
i;
(10)    end while
(11)    calculate Δ
F
i
,
n
,
l;
(12)    recover G
i;
(13)    update satisfaction ratio of all devices in G
i;
(14)   end for
(15)   calculate Δ
F
i
,
n;
(16)   calculate F
i
,
n;
(17)  end for
(18) end for


### 4.1.4. RB Allocation

This subsection presents the RB allocation algorithm. As indicated by Property4, due to the security consideration, different types of devices shall use different frequency channels and different types sharing the same frequency channel are not allowed. This is the constraint which channel allocation shall satisfy. The procedure of the scheduling based RB allocation is outlined in Algorithm 3, where n
i denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
,
n
,
l
} which has been obtained in Algorithm 2, as shown in line (6).Algorithm 3:Scheduling based RB allocation.
Require: F
i
,
n and H
i
,
n
,
l.
Ensure: Y
n
,
l
,
j.
(1) initialize n
i
=
0, 1
≤
i
≤
K;
(2) for  n
=
1 to N  do
(3)  allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)  let n
i
∗
=
n
i
∗
+
1;
(5)  for  l
=
1 to L  do
(6)   allocate the lth RB to devices in H
i
∗
,
n
i
∗
,
l;
(7)   let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
,
n
i
∗
,
l;
(8)  end for
(9) end for


## 4.1.1. Uplink Transmission Power Setting

This subsection determines the transmission powerP
j for each device j. As stated before, for this method, uplinks which are far away from each other (i.e., do not interfere with each other) will be scheduled to share the same RB. Therefore, for the scheduling based method, it can be expected that the interference power P
I in (1) is negligible. That is, we assume that there is no interference between distant devices. Thus, given the RB allocated to device j, the received SINR experienced by device j on this RB at BS b can be approximately written as(7)
γ
j
≈
P
j
G
j
b
P
N
≥
Γ
,where device j is served by BS b (i.e., j
∈
S
b) and Γ is the minimum SINR requirement. Γ is a system parameter and common to all devices and RBs. Therefore, the uplink transmission power P
j can be set to(8)
P
j
=
min
⁡
P
N
·
Γ
G
j
b
,
P
m
a
x
.That is, since in this method distant devices between which there is no interference are scheduled simultaneously, there is no power control and power is strictly a function of the target minimum SINR requirement.


## 4.1.2. Interference Graph Construction

The interference graph is used to indicate whether any two devices can reuse the same RB due to the interference between them. As indicated by Property4, different types of devices shall transmit data over different channels. So we need to construct interference graph for each type, respectively. Let G
i
(
V
i
,
E
i
) denote the interference graph for the ith type, 1
≤
i
≤
K, where V
i is the vertex set in which each vertex represents a device of the ith type and E
i is the edge set in which each edge e
j
,
k represents devices j and k which cannot reuse the same RB. There are two rules to decide if edge e
j
,
k exists. Assume that devices j and k are served by BS b
j and b
k, respectively. The first rule is if b
j
=
b
k, then edge e
j
,
k exists. The second rule is if b
j
≠
b
k but the interference caused to each other is too large, then edge e
j
,
k exists. Specifically, if the distance between device j and BS b
k is less than the interference radius R
j of device j or if the distance between device k and BS b
j is less than the interference radius R
k of device k, then edge e
j
,
k exists.The calculation of interference radius is as follows. For devicej, the interference radius R
j is defined as the distance at which the received SINR is η, where η is the SINR requirement to ensure that the device does not cause nonnegligible interference to other uplinks that are out of the range of interference radius. According to (7), we have the equation for R
j as(9)
P
j
·
P
L
R
j
P
N
=
η
,from which the value of R
j can be solved. After calculating the interference radius for each device, the interference graph G
i can be constructed. The procedure is outlined in Algorithm 1, where d
i
s
(
j
,
b
) in line (6) represents the distance between device j and BS b.Algorithm 1:Interference graph construction.
Require: z.
Ensure: G
i, 1
≤
i
≤
K.
(1)    for  i
=
1 to K  do
(2)     for  any two devices j and k in H
i  do
(3)      if  b
j
=
b
k  then
(4)       connect vertexes j and k in G
i;
(5)      end if
(6)      if  d
i
s
(
j
,
b
k
)
<
R
j or d
i
s
(
k
,
b
j
)
<
R
k  then
(7)       connect vertexes j and k in G
i;
(8)      end if
(9)     end for
(10) end for


## 4.1.3. Utility Function Calculation

For eachi
,
1
≤
i
≤
K, the utility function F
i
,
n is defined as the sum of satisfaction ratio over all devices of the ith type given that a total of n channels have been allocated to them. To calculate F
i
,
n, define Δ
F
i
,
n as the sum of satisfaction ratio over all devices of the ith type given that the nth channel has been allocated to them. Then the value of F
i
,
n can be obtained according to(10)
F
i
,
n
=
F
i
,
n
-
1
+
Δ
F
i
,
n
,where F
i
,
0
=
0. Further, to calculate Δ
F
i
,
n, define Δ
F
i
,
n
,
l as the sum of satisfaction ratio over all devices of the ith type given that the lth RB of the nth channel has been allocated to them. Then the value of Δ
F
i
,
n can be obtained according to(11)
Δ
F
i
,
n
=
∑
l
=
1
L
Δ
F
i
,
n
,
l
.Let H
i
,
n
,
l denote the set of devices of the ith type that share the lth RB of the nth channel. Then the value of Δ
F
i
,
n
,
l can be calculated as(12)
Δ
F
i
,
n
,
l
=
∑
j
∈
H
i
,
n
,
l
C
^
n
,
l
,
j
C
j
,where C
^
n
,
l
,
j can be obtained by (2). Finally, we say a device is feasible in slot l if the total power allocated to this device in this slot does not exceed P
m
a
x. The procedure to calculate utility function is outlined in Algorithm 2, where the set H
i
,
n
,
l is determined in a heuristic manner in lines (4)–(10).Algorithm 2:Utility function calculation.
Require: G
i, 1
≤
i
≤
K.
Ensure: F
i
,
n and H
i
,
n
,
l.
(1)    for  i
=
1 to K  do
(2)     for  n
=
1 to N  do
(3)      for  l
=
1 to L  do
(4)       initialize H
i
,
n
,
l
=
∅;
(5)       delete from G
i devices which are not feasible in slot l anymore;
(6)       while  G
i
≠
∅  do
(7)        determine device j
∗ with the lowest satisfaction ratio in G
i;
(8)        put j
∗ into H
i
,
n
,
l;
(9)        delete j
∗ and devices connected to it from G
i;
(10)    end while
(11)    calculate Δ
F
i
,
n
,
l;
(12)    recover G
i;
(13)    update satisfaction ratio of all devices in G
i;
(14)   end for
(15)   calculate Δ
F
i
,
n;
(16)   calculate F
i
,
n;
(17)  end for
(18) end for


## 4.1.4. RB Allocation

This subsection presents the RB allocation algorithm. As indicated by Property4, due to the security consideration, different types of devices shall use different frequency channels and different types sharing the same frequency channel are not allowed. This is the constraint which channel allocation shall satisfy. The procedure of the scheduling based RB allocation is outlined in Algorithm 3, where n
i denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
,
n
,
l
} which has been obtained in Algorithm 2, as shown in line (6).Algorithm 3:Scheduling based RB allocation.
Require: F
i
,
n and H
i
,
n
,
l.
Ensure: Y
n
,
l
,
j.
(1) initialize n
i
=
0, 1
≤
i
≤
K;
(2) for  n
=
1 to N  do
(3)  allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)  let n
i
∗
=
n
i
∗
+
1;
(5)  for  l
=
1 to L  do
(6)   allocate the lth RB to devices in H
i
∗
,
n
i
∗
,
l;
(7)   let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
,
n
i
∗
,
l;
(8)  end for
(9) end for


## 4.2. Power Control Based Resource Allocation

This method consists of four steps, which are described in sequence as follows.


### 4.2.1. Grouping

LetS
b
i denote the set of type-i devices which are served by BS b, 1
≤
i
≤
K. The value of S
b
i can be derived from the value of S
b, which can be derived from the value of z. Let H
i
=
{
H
i
1
,
…
,
H
i
g
,
…
,
H
i
G
i
} denote the grouping for the ith type, where H
i
g is the set of devices of the ith type which can share the same RB and G
i is the number of groups. The procedure of grouping is outlined in Algorithm 4.Algorithm 4:Grouping.
Require: z.
Ensure: H
i
g.
(1)    for  i
=
1 to K  do
(2)     let G
i
=
max
⁡
S
1
i
,
S
2
i
,
…
,
S
B
i;
(3)     for  g
=
1 to G
i  do
(4)      for  b
=
1 to B  do
(5)       if  S
b
i
≠
∅  then
(6)        select any device j from S
b
i and put into H
i
g;
(7)        delete device j from S
b
i;
(8)       end if
(9)      end for
(10)  end for
(11) end for


### 4.2.2. Uplink Transmission Power Control

Since all devices inH
i
g share the same RB, the received SINR in (1) can be rewritten as(13)
γ
n
,
l
,
j
=
P
j
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
G
k
b
≥
Γ
,where j
∈
H
i
g and Γ is the minimum SINR requirement. Similarly, Γ is a system parameter and common to all devices and RBs.We propose an iterative update algorithm for finding the minimum transmission power satisfying the above equation. Specifically, for thetth iteration, the optimal power P
j
[
t
] to be used by device j can be obtained by solving the following equation:(14)
P
j
t
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
t
-
1
G
k
b
=
Γ
,where P
k
[
t
-
1
] is the power settings obtained at iteration t
-
1. According to (14), the value of P
j
[
t
] can be easily obtained using the bisection method [20]. Additionally, if the value of P
j
[
t
] is greater than P
m
a
x, it will be set as P
m
a
x. The update of the values of transmission power proceeds in iterations until the power convergence.


### 4.2.3. Utility Function Definitions

The utility functionF
i
,
n
,
g is defined as the sum of satisfaction ratio over all devices in H
i
g given that a total of n channels have been allocated to them. To calculate F
i
,
n
,
g, define Δ
F
i
,
n
,
g
,
l as the sum of satisfaction ratio over all devices in H
i
g given that the first l RBs of the nth channel have been allocated to them. Then the value of F
i
,
n
,
g can be obtained according to(15)
F
i
,
n
,
g
=
F
i
,
n
-
1
,
g
+
Δ
F
i
,
n
,
g
,
L
,where F
i
,
0
,
g
=
0 and the value of Δ
F
i
,
n
,
g
,
L can be obtained according to(16)
Δ
F
i
,
n
,
g
,
l
=
Δ
F
i
,
n
,
g
,
l
-
1
,
∑
j
∈
H
i
g
Y
n
,
l
,
j
=
0
Δ
F
i
,
n
,
g
,
l
-
1
+
∑
j
∈
H
i
g
C
^
n
,
l
,
j
C
j
,
o
t
h
e
r
w
i
s
e
,where F
i
,
n
,
g
,
0
=
0 and 1
≤
l
≤
L.


### 4.2.4. RB Allocation

This subsection presents the RB allocation algorithm. Similarly, different types of devices are not allowed to share the same frequency channel, which is the constraint which channel allocation shall satisfy.For convenience, we define functionF
i
,
n as(17)
F
i
,
n
=
∑
g
=
1
G
i
F
i
,
n
,
g
.In addition, we say a group H
i
g is feasible in slot l if the total power allocated to each device j
∈
H
i
g in this slot does not exceed P
m
a
x. The procedure of the power control based RB allocation is outlined in Algorithm 5, where n
i also denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
g
} which has been obtained in Algorithm 4, as shown in line (6).Algorithm 5:Power control based RB allocation.
Require: H
i
g.
Ensure: Y
n
,
l
,
j.
(1)    initialize n
i
=
0, 1
≤
i
≤
K;
(2)    for  n
=
1 to N  do
(3)     allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)     let n
i
∗
=
n
i
∗
+
1;
(5)     for  l
=
1 to L  do
(6)      select H
i
∗
g
∗ which is feasible in slot l and has the minimum Δ
F
i
∗
,
n
i
∗
,
g
,
l
-
1;
(7)      let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
g
∗;
(8)      calculate Δ
F
i
∗
,
n
i
∗
,
g
,
l for each g;
(9)     end for
(10)  calculate F
i
,
n
i for each i;
(11) end for


## 4.2.1. Grouping

LetS
b
i denote the set of type-i devices which are served by BS b, 1
≤
i
≤
K. The value of S
b
i can be derived from the value of S
b, which can be derived from the value of z. Let H
i
=
{
H
i
1
,
…
,
H
i
g
,
…
,
H
i
G
i
} denote the grouping for the ith type, where H
i
g is the set of devices of the ith type which can share the same RB and G
i is the number of groups. The procedure of grouping is outlined in Algorithm 4.Algorithm 4:Grouping.
Require: z.
Ensure: H
i
g.
(1)    for  i
=
1 to K  do
(2)     let G
i
=
max
⁡
S
1
i
,
S
2
i
,
…
,
S
B
i;
(3)     for  g
=
1 to G
i  do
(4)      for  b
=
1 to B  do
(5)       if  S
b
i
≠
∅  then
(6)        select any device j from S
b
i and put into H
i
g;
(7)        delete device j from S
b
i;
(8)       end if
(9)      end for
(10)  end for
(11) end for


## 4.2.2. Uplink Transmission Power Control

Since all devices inH
i
g share the same RB, the received SINR in (1) can be rewritten as(13)
γ
n
,
l
,
j
=
P
j
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
G
k
b
≥
Γ
,where j
∈
H
i
g and Γ is the minimum SINR requirement. Similarly, Γ is a system parameter and common to all devices and RBs.We propose an iterative update algorithm for finding the minimum transmission power satisfying the above equation. Specifically, for thetth iteration, the optimal power P
j
[
t
] to be used by device j can be obtained by solving the following equation:(14)
P
j
t
G
j
b
P
N
+
∑
k
≠
j
,
k
∈
H
i
g
P
k
t
-
1
G
k
b
=
Γ
,where P
k
[
t
-
1
] is the power settings obtained at iteration t
-
1. According to (14), the value of P
j
[
t
] can be easily obtained using the bisection method [20]. Additionally, if the value of P
j
[
t
] is greater than P
m
a
x, it will be set as P
m
a
x. The update of the values of transmission power proceeds in iterations until the power convergence.


## 4.2.3. Utility Function Definitions

The utility functionF
i
,
n
,
g is defined as the sum of satisfaction ratio over all devices in H
i
g given that a total of n channels have been allocated to them. To calculate F
i
,
n
,
g, define Δ
F
i
,
n
,
g
,
l as the sum of satisfaction ratio over all devices in H
i
g given that the first l RBs of the nth channel have been allocated to them. Then the value of F
i
,
n
,
g can be obtained according to(15)
F
i
,
n
,
g
=
F
i
,
n
-
1
,
g
+
Δ
F
i
,
n
,
g
,
L
,where F
i
,
0
,
g
=
0 and the value of Δ
F
i
,
n
,
g
,
L can be obtained according to(16)
Δ
F
i
,
n
,
g
,
l
=
Δ
F
i
,
n
,
g
,
l
-
1
,
∑
j
∈
H
i
g
Y
n
,
l
,
j
=
0
Δ
F
i
,
n
,
g
,
l
-
1
+
∑
j
∈
H
i
g
C
^
n
,
l
,
j
C
j
,
o
t
h
e
r
w
i
s
e
,where F
i
,
n
,
g
,
0
=
0 and 1
≤
l
≤
L.


## 4.2.4. RB Allocation

This subsection presents the RB allocation algorithm. Similarly, different types of devices are not allowed to share the same frequency channel, which is the constraint which channel allocation shall satisfy.For convenience, we define functionF
i
,
n as(17)
F
i
,
n
=
∑
g
=
1
G
i
F
i
,
n
,
g
.In addition, we say a group H
i
g is feasible in slot l if the total power allocated to each device j
∈
H
i
g in this slot does not exceed P
m
a
x. The procedure of the power control based RB allocation is outlined in Algorithm 5, where n
i also denotes the number of channels which have been allocated to the ith type. Specifically, after the type which is allocated to the nth channel has been selected in line (3), the RBs of the nth channel shall be allocated according to {
H
i
g
} which has been obtained in Algorithm 4, as shown in line (6).Algorithm 5:Power control based RB allocation.
Require: H
i
g.
Ensure: Y
n
,
l
,
j.
(1)    initialize n
i
=
0, 1
≤
i
≤
K;
(2)    for  n
=
1 to N  do
(3)     allocate the nth channel to the i
∗th type with the minimum F
i
,
n
i and break the tie arbitrarily;
(4)     let n
i
∗
=
n
i
∗
+
1;
(5)     for  l
=
1 to L  do
(6)      select H
i
∗
g
∗ which is feasible in slot l and has the minimum Δ
F
i
∗
,
n
i
∗
,
g
,
l
-
1;
(7)      let Y
n
,
l
,
j
=
1 for each j
∈
H
i
∗
g
∗;
(8)      calculate Δ
F
i
∗
,
n
i
∗
,
g
,
l for each g;
(9)     end for
(10)  calculate F
i
,
n
i for each i;
(11) end for


## 5. Location Selection Methods

The task of location selection is to search for the locationz. Three different location selection methods are presented. The first isK-means based [21]. This method is raw and is used as the benchmark in this work. The next two are simulated annealing (SA) based [22] and particle swarm optimization (PSO) based [23], respectively.


### 5.1.K-Means Based Location Selection

Initially,z
b
=
(
z
b
1
,
z
b
2
) is randomly selected from the candidate location set Θ as the deployment locations of BSs, where z
b
1 and z
b
2 are the horizontal and vertical ordinate of the deployment location, respectively. Then, we can obtain the corresponding Ω
=
{
S
1
,
S
2
,
…
,
S
B
} which describes the relationship between SG devices and BSs. Next, the BS locations are updated as follows. Assume that the locations of device j are x
j
=
(
x
j
1
,
x
j
2
), where x
j
1 and x
j
2 are the horizontal and vertical ordinate of the location of device j, respectively. The new BS locations can be calculated as(18)
z
b
h
=
1
S
b
∑
j
∈
S
b
x
j
h
,where 1
≤
b
≤
B
,
h
∈
{
1,2
}, and |
S
b
| is the number of devices served by the bth BS. For each b, if the calculated z
b does not belong to Θ, it shall be set as the element in Θ which is the closest to the calculated value.


### 5.2. SA Based Location Selection

The location selection is to iterate over all candidate locations to find the best location that maximizes the satisfaction ratio. Since the enumeration is practically impossible, an algorithm with controllable complexity which can output a solution within the given time limit is desirable. We consider a stochastic local search algorithm which progressively traverses from one location to its neighbor in a probabilistic manner for finding the global optimal solution. Specifically, an algorithm based on simulated annealing is proposed, as outlined in Algorithm6.Algorithm 6:SA based iterative procedure.
(1)    initialize c
=
0;
(2)    initialize t
=
t
i
n
i
t;
(3)    initialize  z;
(4)    determine the values of P and Y given  z;
(5)    determine the value of V given  z, P, and Y;
(6)    initialize  z
b
e
s
t
=
z  and V
b
e
s
t
=
V;
(7)    while  c
<
c
m
a
x  do
(8)     update  z
n
e
x
t;
(9)     update P
n
e
x
t and Y
n
e
x
t given  z
n
e
x
t;
(10)  update V
n
e
x
t given  z
n
e
x
t, P
n
e
x
t, and Y
n
e
x
t;
(11)  if  V
n
e
x
t
>
V  then
(12)   update  z
=
z
n
e
x
t  and V
=
V
n
e
x
t;
(13)   if  V
n
e
x
t
>
V
b
e
s
t  then
(14)    update z
b
e
s
t
=
z
n
e
x
t and V
b
e
s
t
=
V
n
e
x
t;
(15)   end if
(16)  else
(17)   update z
=
z
n
e
x
t and V
=
V
n
e
x
t with probability e
(
V
n
e
x
t
-
V
)
/
t;
(18)  end if
(19)  let c
=
c
+
1;
(20)  let t
=
α
t;
(21) end while
(22) return  z
b
e
s
t.Beginning with an initial location, the variablez
b
e
s
t records the location with the highest payoff obtained so far as the algorithm proceeds. In lines (4) and (9), the resource allocation methods in Section 4 are used to determine the values of P and Y. At each iteration, a new location z
n
e
x
t among the neighborhood of current location z is chosen in line (8). The new location z
n
e
x
t is determined as follows. First, for the current z, we can obtain Ω
=
{
S
1
,
S
2
,
…
,
S
B
} and then calculate the satisfactory ratio of each S
b
,
1
≤
b
≤
B. For each iteration only one BS location is changed. We choose BS b
∗ with the lowest satisfactory ratio to change the location. Specifically, we select a candidate BS location from Θ which is no more than d meters away from the original BS location as the new BS location, where d is a parameter. If z
n
e
x
t yields a better payoff than z, the search proceeds with z
n
e
x
t for the next iteration. Otherwise, z
n
e
x
t is still chosen with probability e
(
V
n
e
x
t
-
V
)
/
t based on the concept of simulated annealing in line (17). In line (20), the temperature t decreases after each iteration according to an annealing schedule t
=
α
t, where 0
<
α
<
1 is also a parameter. Different values of c
m
a
x, α, and d can be set to control the speed of cooling.


### 5.3. PSO Based Location Selection

In this subsection, a particle swarm optimization based algorithm is presented to search for the location. Assume that the swarm consists ofM particles and the search space is B dimensional. Let Z
m
=
(
z
m
1
,
…
,
z
m
b
,
…
,
z
m
B
) represent the position of the mth particle, where z
m
b is a two-dimensional vector representing the deployment location of the bth BS. Let v
m
=
(
v
m
1
,
…
,
v
m
b
,
…
,
v
m
B
) represent the velocity of the mth particle, where v
m
b
=
(
v
m
b
1
,
v
m
b
2
) is a two-dimensional vector for which v
m
b
1 and v
m
b
2 represent the horizontal and vertical velocity, respectively. Let P
m
=
(
p
m
1
,
…
,
p
m
b
,
…
,
p
m
B
) represent the position of the best solution found by the mth particle and let P
∗
=
(
p
1
∗
,
…
,
p
b
∗
,
…
,
p
B
∗
) represent the position of the best solution found by all particles during the search. The position of each particle is updated by using Z
m
[
t
+
1
]
=
Z
m
[
t
]
+
v
m
[
t
+
1
], where Z
m
[
t
] is the position of the mth particle at iteration t and v
m
[
t
+
1
] is the new velocity of the mth particle at iteration t
+
1. The velocities of the particles are updated according to v
m
[
t
+
1
]
=
w
v
m
[
t
]
+
c
1
ξ
(
P
m
[
t
]
-
Z
m
[
t
]
)
+
c
2
η
(
P
∗
[
t
]
-
Z
m
[
t
]
), where P
m
[
t
] is the position of the best solution found by the mth particle at iteration t, P
∗
[
t
] is the position of the best solution found by all particles during the search so far, and ξ and η are random values generated by the uniform distribution in the interval [
0,1
].Additionally, for the PSO based algorithm, there are two types of collisions. For the first type, the particles could be attracted to regions outside the feasible search spaceΘ; for the second type, the velocity of particles could be too large. The anticollision mechanisms for preserving the feasibility of solution are as follows. For the first type of collision, if z
m
b
∉
Θ occurs, we set z
m
b randomly selected location in Θ. For the second type of collision, if it occurs, we set(19)
v
m
b
h
=
v
m
a
x
,
i
f
v
m
b
h
>
v
m
a
x
-
v
m
a
x
,
i
f
v
m
b
h
<
-
v
m
a
x
,where h
∈
{
1,2
} and v
m
a
x is the velocity limit.The procedure for PSO based algorithm is outlined in Algorithm7, where c
m
a
x is the iteration limit.Algorithm 7:PSO based iterative procedure.
(1)    initialize c
=
1;
(2)    for  particle m
=
1 to M  do
(3)     initialize the velocity  v
m in [
-
v
m
a
x
,
v
m
a
x
];
(4)     initialize the position  Z
m in Θ;
(5)     determine the value of V
m given  Z
m;
(6)     initialize P
m
=
Z
m and V
b
e
s
t
,
m
=
V
m;
(7)    end for
(8)    calculate V
b
e
s
t
=
max
⁡
V
b
e
s
t
,
1
,
V
b
e
s
t
,
2
,
…
,
V
b
e
s
t
,
M and determine  P
∗;
(9)    while  c
<
c
m
a
x  do
(10)  for  particle m
=
1 to M  do
(11)   update the velocity v
m;
(12)   update the position Z
m;
(13)   determine the value of V
m given Z
m;
(14)   if  V
m
>
V
b
e
s
t
,
m  then
(15)    update V
b
e
s
t
,
m
=
V
m;
(16)    update  P
m;
(17)   end if
(18)  end for
(19)  calculate V
b
e
s
t
′
=
max
⁡
V
b
e
s
t
,
1
,
V
b
e
s
t
,
2
,
…
,
V
b
e
s
t
,
M;
(20)  if  V
b
e
s
t
′
>
V
b
e
s
t  then
(21)   update V
b
e
s
t
=
V
b
e
s
t
′;
(22)   update  P
∗;
(23)  end if
(24)  let c
=
c
+
1;
(25) end while
(26) return  P
∗.


## 5.1.K-Means Based Location Selection

Initially,z
b
=
(
z
b
1
,
z
b
2
) is randomly selected from the candidate location set Θ as the deployment locations of BSs, where z
b
1 and z
b
2 are the horizontal and vertical ordinate of the deployment location, respectively. Then, we can obtain the corresponding Ω
=
{
S
1
,
S
2
,
…
,
S
B
} which describes the relationship between SG devices and BSs. Next, the BS locations are updated as follows. Assume that the locations of device j are x
j
=
(
x
j
1
,
x
j
2
), where x
j
1 and x
j
2 are the horizontal and vertical ordinate of the location of device j, respectively. The new BS locations can be calculated as(18)
z
b
h
=
1
S
b
∑
j
∈
S
b
x
j
h
,where 1
≤
b
≤
B
,
h
∈
{
1,2
}, and |
S
b
| is the number of devices served by the bth BS. For each b, if the calculated z
b does not belong to Θ, it shall be set as the element in Θ which is the closest to the calculated value.


## 5.2. SA Based Location Selection

The location selection is to iterate over all candidate locations to find the best location that maximizes the satisfaction ratio. Since the enumeration is practically impossible, an algorithm with controllable complexity which can output a solution within the given time limit is desirable. We consider a stochastic local search algorithm which progressively traverses from one location to its neighbor in a probabilistic manner for finding the global optimal solution. Specifically, an algorithm based on simulated annealing is proposed, as outlined in Algorithm6.Algorithm 6:SA based iterative procedure.
(1)    initialize c
=
0;
(2)    initialize t
=
t
i
n
i
t;
(3)    initialize  z;
(4)    determine the values of P and Y given  z;
(5)    determine the value of V given  z, P, and Y;
(6)    initialize  z
b
e
s
t
=
z  and V
b
e
s
t
=
V;
(7)    while  c
<
c
m
a
x  do
(8)     update  z
n
e
x
t;
(9)     update P
n
e
x
t and Y
n
e
x
t given  z
n
e
x
t;
(10)  update V
n
e
x
t given  z
n
e
x
t, P
n
e
x
t, and Y
n
e
x
t;
(11)  if  V
n
e
x
t
>
V  then
(12)   update  z
=
z
n
e
x
t  and V
=
V
n
e
x
t;
(13)   if  V
n
e
x
t
>
V
b
e
s
t  then
(14)    update z
b
e
s
t
=
z
n
e
x
t and V
b
e
s
t
=
V
n
e
x
t;
(15)   end if
(16)  else
(17)   update z
=
z
n
e
x
t and V
=
V
n
e
x
t with probability e
(
V
n
e
x
t
-
V
)
/
t;
(18)  end if
(19)  let c
=
c
+
1;
(20)  let t
=
α
t;
(21) end while
(22) return  z
b
e
s
t.Beginning with an initial location, the variablez
b
e
s
t records the location with the highest payoff obtained so far as the algorithm proceeds. In lines (4) and (9), the resource allocation methods in Section 4 are used to determine the values of P and Y. At each iteration, a new location z
n
e
x
t among the neighborhood of current location z is chosen in line (8). The new location z
n
e
x
t is determined as follows. First, for the current z, we can obtain Ω
=
{
S
1
,
S
2
,
…
,
S
B
} and then calculate the satisfactory ratio of each S
b
,
1
≤
b
≤
B. For each iteration only one BS location is changed. We choose BS b
∗ with the lowest satisfactory ratio to change the location. Specifically, we select a candidate BS location from Θ which is no more than d meters away from the original BS location as the new BS location, where d is a parameter. If z
n
e
x
t yields a better payoff than z, the search proceeds with z
n
e
x
t for the next iteration. Otherwise, z
n
e
x
t is still chosen with probability e
(
V
n
e
x
t
-
V
)
/
t based on the concept of simulated annealing in line (17). In line (20), the temperature t decreases after each iteration according to an annealing schedule t
=
α
t, where 0
<
α
<
1 is also a parameter. Different values of c
m
a
x, α, and d can be set to control the speed of cooling.


## 5.3. PSO Based Location Selection

In this subsection, a particle swarm optimization based algorithm is presented to search for the location. Assume that the swarm consists ofM particles and the search space is B dimensional. Let Z
m
=
(
z
m
1
,
…
,
z
m
b
,
…
,
z
m
B
) represent the position of the mth particle, where z
m
b is a two-dimensional vector representing the deployment location of the bth BS. Let v
m
=
(
v
m
1
,
…
,
v
m
b
,
…
,
v
m
B
) represent the velocity of the mth particle, where v
m
b
=
(
v
m
b
1
,
v
m
b
2
) is a two-dimensional vector for which v
m
b
1 and v
m
b
2 represent the horizontal and vertical velocity, respectively. Let P
m
=
(
p
m
1
,
…
,
p
m
b
,
…
,
p
m
B
) represent the position of the best solution found by the mth particle and let P
∗
=
(
p
1
∗
,
…
,
p
b
∗
,
…
,
p
B
∗
) represent the position of the best solution found by all particles during the search. The position of each particle is updated by using Z
m
[
t
+
1
]
=
Z
m
[
t
]
+
v
m
[
t
+
1
], where Z
m
[
t
] is the position of the mth particle at iteration t and v
m
[
t
+
1
] is the new velocity of the mth particle at iteration t
+
1. The velocities of the particles are updated according to v
m
[
t
+
1
]
=
w
v
m
[
t
]
+
c
1
ξ
(
P
m
[
t
]
-
Z
m
[
t
]
)
+
c
2
η
(
P
∗
[
t
]
-
Z
m
[
t
]
), where P
m
[
t
] is the position of the best solution found by the mth particle at iteration t, P
∗
[
t
] is the position of the best solution found by all particles during the search so far, and ξ and η are random values generated by the uniform distribution in the interval [
0,1
].Additionally, for the PSO based algorithm, there are two types of collisions. For the first type, the particles could be attracted to regions outside the feasible search spaceΘ; for the second type, the velocity of particles could be too large. The anticollision mechanisms for preserving the feasibility of solution are as follows. For the first type of collision, if z
m
b
∉
Θ occurs, we set z
m
b randomly selected location in Θ. For the second type of collision, if it occurs, we set(19)
v
m
b
h
=
v
m
a
x
,
i
f
v
m
b
h
>
v
m
a
x
-
v
m
a
x
,
i
f
v
m
b
h
<
-
v
m
a
x
,where h
∈
{
1,2
} and v
m
a
x is the velocity limit.The procedure for PSO based algorithm is outlined in Algorithm7, where c
m
a
x is the iteration limit.Algorithm 7:PSO based iterative procedure.
(1)    initialize c
=
1;
(2)    for  particle m
=
1 to M  do
(3)     initialize the velocity  v
m in [
-
v
m
a
x
,
v
m
a
x
];
(4)     initialize the position  Z
m in Θ;
(5)     determine the value of V
m given  Z
m;
(6)     initialize P
m
=
Z
m and V
b
e
s
t
,
m
=
V
m;
(7)    end for
(8)    calculate V
b
e
s
t
=
max
⁡
V
b
e
s
t
,
1
,
V
b
e
s
t
,
2
,
…
,
V
b
e
s
t
,
M and determine  P
∗;
(9)    while  c
<
c
m
a
x  do
(10)  for  particle m
=
1 to M  do
(11)   update the velocity v
m;
(12)   update the position Z
m;
(13)   determine the value of V
m given Z
m;
(14)   if  V
m
>
V
b
e
s
t
,
m  then
(15)    update V
b
e
s
t
,
m
=
V
m;
(16)    update  P
m;
(17)   end if
(18)  end for
(19)  calculate V
b
e
s
t
′
=
max
⁡
V
b
e
s
t
,
1
,
V
b
e
s
t
,
2
,
…
,
V
b
e
s
t
,
M;
(20)  if  V
b
e
s
t
′
>
V
b
e
s
t  then
(21)   update V
b
e
s
t
=
V
b
e
s
t
′;
(22)   update  P
∗;
(23)  end if
(24)  let c
=
c
+
1;
(25) end while
(26) return  P
∗.


## 6. Performance Evaluation

### 6.1. Parameter Setting

Assume there are a total ofK
=
3 types of SG devices. In the case of no particular description, the required uplink data rate of each type is C
1
=
100 kbps, C
2
=
400 kbps, and C
3
=
800 kbps, respectively, and the number of devices of each type is 50, 50, and 50, respectively. We randomly distribute these devices in a circle region Ψ with a radius of 1200 meters. Further, we assume that Θ contains a total of 350 candidate BS locations which are also randomly generated in Ψ. Based on the simulation settings in [24, 25], wireless communication related parameters are set as follows. The maximum transmission power P
m
a
x is 20 dBm. The path loss formula is P
L
(
x
)
=
6
+
42.68
log
⁡
(
x
) dB for a distance separation of x meters. The total bandwidth W is 5 MHz and the bandwidth of each channel W
0 is 180 kHz. Assume that the power of background noise P
N
=
N
0
W, where the noise power spectrum density N
0
=
-
174 dBm/Hz. The minimum SINR requirement Γ is 3 dB, which is used in (7) and (13) to determine transmit power. The SINR requirement η is -
2dB, which is used in (9) to determine interference radius. Finally, the number of slots in each frame L
0 is 20. In the case of no particular description, assume that the number of usable slots L is also 20. For SA, there are three parameters t
i
n
i
t, α, and d. For t
i
n
i
t and d, based on the recommendations in [20, 26, 27], we set t
i
n
i
t
=
1000 and d
=
30. For α, we have run many simulation experiments to find an appropriate value of it. Simulation results show that the larger the value of α is, the better the supporting ratio is. Therefore, since the value of α shall be between 0 and 1, we set α
=
0.99. For PSO, there are five parameters M, V
m
a
x, w, c
1, and c
2. For M, w, c
1, and c
2, based on the recommendations in [27, 28], we set M
=
10, w
=
0.7, c
1
=
2, and c
2
=
2. For V
m
a
x, we have run many simulation experiments to find an appropriate value of it. Simulation results show that the value of V
m
a
x shall not be too small or too large. Specifically, if the value of V
m
a
x is too small, the convergence rate of PSO will be very slow; if the value of V
m
a
x is too large, PSO will oscillate and not converge. Therefore, after many simulation experiments, we have selected V
m
a
x
=
150 to achieve acceptable convergence rate. Finally, for both algorithms, the iteration limit c
m
a
x is set to be 1000.Combining different resource allocation and location selection algorithms, we have a total of six different schemes. We evaluate the performance of above schemes for different parameter configurations. For each parameter configuration, we run simulation experiments for 1000 times and average the results.


### 6.2. Simulation Results

This subsection presents the performance evaluation results of the proposed schemes under different scenarios and the effects of various system parameters are evaluated and compared.


#### 6.2.1. Convergence

We show in Figure2 a typical trace of the progression of benefits for guided stochastic search in all schemes, where “PC” and “Sched” represent power control and scheduling based resource allocation algorithm, respectively. We can find that the payoff of the best location selection is increased gradually and will be converged to a constant value finally. Therefore, the curves in Figure 2 show that the proposed schemes are converged to a steady state. Additionally, we can observe that the solution quality and the required number of iterations to converge are significantly different from each other. Firstly, the final values of payoff for different schemes are different. Specifically, the “PC + PSO” scheme can achieve the highest payoff (i.e., 128.5030) among all schemes. Recall that the payoff is defined as the sum of satisfaction ratio over all devices where the satisfaction ratio of a device is defined as the ratio between achieved data rate and the required data rate. For this set of simulation experiments, since there are totally 150 devices (as stated in the beginning of Section 6.1), the value of payoff will not be higher than 150. Therefore, a payoff of 128.5030 means that most data rate requirements have been satisfied. Secondly, forK-means related schemes (i.e., the “PC +K-means” and “Sched +K-means” schemes), although their payoff is not high (i.e., 104.8572 and 100.1876), the required numbers of iterations to converge (i.e., 2 and 2) are much smaller than other schemes; that is, they converge much faster than other schemes. Therefore, we can conclude that different schemes can achieve different tradeoffs between solution quality and convergence rate.Figure 2
Convergence of the proposed schemes.For any devicej, if its uplink data rate requirement is met (i.e., C
^
j
≥
C
j), we say this device is satisfied. Further, we define the supporting ratio as the ratio between the number of devices which have been satisfied and the total number of devices. In the following simulation experiments, we will evaluate the impact of the number of channels (i.e., the total bandwidth), the number of BSs, and the number of devices on the performance (i.e., the supporting ratio) of all these six schemes. Additionally, we would like to claim that all the values plotted in Figures 3, 4, and 5 are obtained after the algorithms have converged to a steady state.Figure 3
Impact of the number of channels.Figure 4
Impact of the number of BSs.Figure 5
Impact of the number of devices.


#### 6.2.2. Impact of the Number of Channels

The number of channels is equal toW
/
W
0, where W is the total bandwidth. Figure 3 shows the supporting ratio of all proposed schemes when the total bandwidth W or, equivalently, the number of channels is varied. For this set of simulation experiments, there are totally 150 devices, for which the sum of data rate requirements is 50
×
C
1
+
50
×
C
2
+
50
×
C
3
=
65Mbps. We set the number of BSs B to be 10. It can be observed that when the total bandwidth (i.e., the number of channels) increases, the supporting ratio increases. Specifically, when the total bandwidth is 9 MHz (i.e., the number of channels is 50), the supporting ratio of the “PC + PSO” and “PC + SA” schemes is as high as 1 (i.e., the data rate requirements of all 150 devices have been satisfied), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8713 and 0.8605, respectively (i.e., there are still 150
×
(
1
-
0.8713
)
=
20 and 150
×
(
1
-
0.8605
)
=
21 devices whose data rate requirements are not satisfied, resp.).Finally, it can be observed that the “PC + PSO” scheme is the best among all other schemes, which will be validated again by the following simulation results. This is due to two aspects of reasons. For the first reason, SA and PSO are metaheuristics, which efficiently explore the search space to find near-optimal solutions. By searching over a large set of feasible solutions, they can find good solutions with less computational effort compared to simple heuristics (e.g., theK-means method). Therefore, SA and PSO are superior toK-means in finding good solutions. For the second reason, if two devices are close to each other, they could interfere with each other if they use the same RB. For the PC method, the transmission power of each device is controlled so that devices which are close to each other can also share the same RB; for the Sched method, only devices which are far away from each other can share the same RB. Since the PC method allows devices which are close to each other to transmit data simultaneously, it can admit more devices than the Sched method. On the other hand, for the PC method, since there exists interference among neighbor devices, each device will have to increase its transmission power to combat such interference to meet the minimum SINR requirement. This makes devices using the PC method consume more power resource than the Sched method. Therefore, the PC method can admit more devices than the Sched method via consuming more power.


#### 6.2.3. Impact of the Number of BSs

Figure4 shows the supporting ratio of all proposed schemes when the number of BSs B is varied. We can observe that when the number of BSs increases, the supporting ratio increases, since the average distance between devices and access points is shortened. Specifically, when the number of BSs is 15, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is 1 and 0.9767, respectively (i.e., there are zero and 150
×
(
1
-
0.9767
)
=
4 devices whose data rate requirements are not satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8447 and 0.7743, respectively (i.e., there are still 150
×
(
1
-
0.8447
)
=
24 and 150
×
(
1
-
0.7743
)
=
34 devices whose data rate requirements are not satisfied, resp.). Therefore, we can conclude that the “PC + PSO” scheme is the best one and for the simulated scenario at least 15 BSs shall be deployed so that the supporting ratio of one can be achieved. For the following simulations, we will set the value of B to be 15.


#### 6.2.4. Impact of the Number of Devices

Figure5 shows the supporting ratio of all proposed schemes when the number of devices is varied. For convenience, let N
i denote the number of devices of the ith type. Let N
i
,
i
n
i
t denote the initial value of N
i. As stated in the beginning of Section 6.1, we set N
1
,
i
n
i
t
=
50, N
2
,
i
n
i
t
=
50, and N
3
,
i
n
i
t
=
50. We will collect the performance metrics (i.e., the supporting ratio) which is a function of (N
1, N
2, N
3). However, it is hard to visualize high-dimensional data when the dimension is greater than two. Therefore, we run the simulation for three times. For the jth (j
=
1,2
,
3) run, we change the values of N
j
=
N
j
,
i
n
i
t
+
n while keeping the values of other N
i (i
≠
j) fixed to be N
i
,
i
n
i
t, where n
=
10,20,30,40,50. Due to the limited space, we only plot the simulation results of the second run in Figure 5 where the horizontal axis represents the number of devices of the second type. We can observe that when the number of devices increases, the supporting ratio decreases, since the radio resource consumed by each type of devices increases. Specifically, when the number of devices of the second type is increased to be 100, there are totally 50
+
100
+
50
=
200 devices, for which the sum of data rate requirements is 50
×
C
1
+
100
×
C
2
+
50
×
C
3
=
85Mbps. For this scenario, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is still 0.8626 and 0.8420, respectively (i.e., there are 150
×
0.8626
=
129 and 150
×
0.8420
=
126 devices whose data rate requirements can be satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is only 0.6600 and 0.6015, respectively (i.e., there are only 150
×
0.6600
=
99 and 150
×
0.6015
=
90 devices whose data rate requirements have been satisfied, resp.). Comparing these curves, we can also conclude that the “PC + PSO” scheme is more preferable than other schemes.


## 6.1. Parameter Setting

Assume there are a total ofK
=
3 types of SG devices. In the case of no particular description, the required uplink data rate of each type is C
1
=
100 kbps, C
2
=
400 kbps, and C
3
=
800 kbps, respectively, and the number of devices of each type is 50, 50, and 50, respectively. We randomly distribute these devices in a circle region Ψ with a radius of 1200 meters. Further, we assume that Θ contains a total of 350 candidate BS locations which are also randomly generated in Ψ. Based on the simulation settings in [24, 25], wireless communication related parameters are set as follows. The maximum transmission power P
m
a
x is 20 dBm. The path loss formula is P
L
(
x
)
=
6
+
42.68
log
⁡
(
x
) dB for a distance separation of x meters. The total bandwidth W is 5 MHz and the bandwidth of each channel W
0 is 180 kHz. Assume that the power of background noise P
N
=
N
0
W, where the noise power spectrum density N
0
=
-
174 dBm/Hz. The minimum SINR requirement Γ is 3 dB, which is used in (7) and (13) to determine transmit power. The SINR requirement η is -
2dB, which is used in (9) to determine interference radius. Finally, the number of slots in each frame L
0 is 20. In the case of no particular description, assume that the number of usable slots L is also 20. For SA, there are three parameters t
i
n
i
t, α, and d. For t
i
n
i
t and d, based on the recommendations in [20, 26, 27], we set t
i
n
i
t
=
1000 and d
=
30. For α, we have run many simulation experiments to find an appropriate value of it. Simulation results show that the larger the value of α is, the better the supporting ratio is. Therefore, since the value of α shall be between 0 and 1, we set α
=
0.99. For PSO, there are five parameters M, V
m
a
x, w, c
1, and c
2. For M, w, c
1, and c
2, based on the recommendations in [27, 28], we set M
=
10, w
=
0.7, c
1
=
2, and c
2
=
2. For V
m
a
x, we have run many simulation experiments to find an appropriate value of it. Simulation results show that the value of V
m
a
x shall not be too small or too large. Specifically, if the value of V
m
a
x is too small, the convergence rate of PSO will be very slow; if the value of V
m
a
x is too large, PSO will oscillate and not converge. Therefore, after many simulation experiments, we have selected V
m
a
x
=
150 to achieve acceptable convergence rate. Finally, for both algorithms, the iteration limit c
m
a
x is set to be 1000.Combining different resource allocation and location selection algorithms, we have a total of six different schemes. We evaluate the performance of above schemes for different parameter configurations. For each parameter configuration, we run simulation experiments for 1000 times and average the results.


## 6.2. Simulation Results

This subsection presents the performance evaluation results of the proposed schemes under different scenarios and the effects of various system parameters are evaluated and compared.


### 6.2.1. Convergence

We show in Figure2 a typical trace of the progression of benefits for guided stochastic search in all schemes, where “PC” and “Sched” represent power control and scheduling based resource allocation algorithm, respectively. We can find that the payoff of the best location selection is increased gradually and will be converged to a constant value finally. Therefore, the curves in Figure 2 show that the proposed schemes are converged to a steady state. Additionally, we can observe that the solution quality and the required number of iterations to converge are significantly different from each other. Firstly, the final values of payoff for different schemes are different. Specifically, the “PC + PSO” scheme can achieve the highest payoff (i.e., 128.5030) among all schemes. Recall that the payoff is defined as the sum of satisfaction ratio over all devices where the satisfaction ratio of a device is defined as the ratio between achieved data rate and the required data rate. For this set of simulation experiments, since there are totally 150 devices (as stated in the beginning of Section 6.1), the value of payoff will not be higher than 150. Therefore, a payoff of 128.5030 means that most data rate requirements have been satisfied. Secondly, forK-means related schemes (i.e., the “PC +K-means” and “Sched +K-means” schemes), although their payoff is not high (i.e., 104.8572 and 100.1876), the required numbers of iterations to converge (i.e., 2 and 2) are much smaller than other schemes; that is, they converge much faster than other schemes. Therefore, we can conclude that different schemes can achieve different tradeoffs between solution quality and convergence rate.Figure 2
Convergence of the proposed schemes.For any devicej, if its uplink data rate requirement is met (i.e., C
^
j
≥
C
j), we say this device is satisfied. Further, we define the supporting ratio as the ratio between the number of devices which have been satisfied and the total number of devices. In the following simulation experiments, we will evaluate the impact of the number of channels (i.e., the total bandwidth), the number of BSs, and the number of devices on the performance (i.e., the supporting ratio) of all these six schemes. Additionally, we would like to claim that all the values plotted in Figures 3, 4, and 5 are obtained after the algorithms have converged to a steady state.Figure 3
Impact of the number of channels.Figure 4
Impact of the number of BSs.Figure 5
Impact of the number of devices.


### 6.2.2. Impact of the Number of Channels

The number of channels is equal toW
/
W
0, where W is the total bandwidth. Figure 3 shows the supporting ratio of all proposed schemes when the total bandwidth W or, equivalently, the number of channels is varied. For this set of simulation experiments, there are totally 150 devices, for which the sum of data rate requirements is 50
×
C
1
+
50
×
C
2
+
50
×
C
3
=
65Mbps. We set the number of BSs B to be 10. It can be observed that when the total bandwidth (i.e., the number of channels) increases, the supporting ratio increases. Specifically, when the total bandwidth is 9 MHz (i.e., the number of channels is 50), the supporting ratio of the “PC + PSO” and “PC + SA” schemes is as high as 1 (i.e., the data rate requirements of all 150 devices have been satisfied), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8713 and 0.8605, respectively (i.e., there are still 150
×
(
1
-
0.8713
)
=
20 and 150
×
(
1
-
0.8605
)
=
21 devices whose data rate requirements are not satisfied, resp.).Finally, it can be observed that the “PC + PSO” scheme is the best among all other schemes, which will be validated again by the following simulation results. This is due to two aspects of reasons. For the first reason, SA and PSO are metaheuristics, which efficiently explore the search space to find near-optimal solutions. By searching over a large set of feasible solutions, they can find good solutions with less computational effort compared to simple heuristics (e.g., theK-means method). Therefore, SA and PSO are superior toK-means in finding good solutions. For the second reason, if two devices are close to each other, they could interfere with each other if they use the same RB. For the PC method, the transmission power of each device is controlled so that devices which are close to each other can also share the same RB; for the Sched method, only devices which are far away from each other can share the same RB. Since the PC method allows devices which are close to each other to transmit data simultaneously, it can admit more devices than the Sched method. On the other hand, for the PC method, since there exists interference among neighbor devices, each device will have to increase its transmission power to combat such interference to meet the minimum SINR requirement. This makes devices using the PC method consume more power resource than the Sched method. Therefore, the PC method can admit more devices than the Sched method via consuming more power.


### 6.2.3. Impact of the Number of BSs

Figure4 shows the supporting ratio of all proposed schemes when the number of BSs B is varied. We can observe that when the number of BSs increases, the supporting ratio increases, since the average distance between devices and access points is shortened. Specifically, when the number of BSs is 15, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is 1 and 0.9767, respectively (i.e., there are zero and 150
×
(
1
-
0.9767
)
=
4 devices whose data rate requirements are not satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8447 and 0.7743, respectively (i.e., there are still 150
×
(
1
-
0.8447
)
=
24 and 150
×
(
1
-
0.7743
)
=
34 devices whose data rate requirements are not satisfied, resp.). Therefore, we can conclude that the “PC + PSO” scheme is the best one and for the simulated scenario at least 15 BSs shall be deployed so that the supporting ratio of one can be achieved. For the following simulations, we will set the value of B to be 15.


### 6.2.4. Impact of the Number of Devices

Figure5 shows the supporting ratio of all proposed schemes when the number of devices is varied. For convenience, let N
i denote the number of devices of the ith type. Let N
i
,
i
n
i
t denote the initial value of N
i. As stated in the beginning of Section 6.1, we set N
1
,
i
n
i
t
=
50, N
2
,
i
n
i
t
=
50, and N
3
,
i
n
i
t
=
50. We will collect the performance metrics (i.e., the supporting ratio) which is a function of (N
1, N
2, N
3). However, it is hard to visualize high-dimensional data when the dimension is greater than two. Therefore, we run the simulation for three times. For the jth (j
=
1,2
,
3) run, we change the values of N
j
=
N
j
,
i
n
i
t
+
n while keeping the values of other N
i (i
≠
j) fixed to be N
i
,
i
n
i
t, where n
=
10,20,30,40,50. Due to the limited space, we only plot the simulation results of the second run in Figure 5 where the horizontal axis represents the number of devices of the second type. We can observe that when the number of devices increases, the supporting ratio decreases, since the radio resource consumed by each type of devices increases. Specifically, when the number of devices of the second type is increased to be 100, there are totally 50
+
100
+
50
=
200 devices, for which the sum of data rate requirements is 50
×
C
1
+
100
×
C
2
+
50
×
C
3
=
85Mbps. For this scenario, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is still 0.8626 and 0.8420, respectively (i.e., there are 150
×
0.8626
=
129 and 150
×
0.8420
=
126 devices whose data rate requirements can be satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is only 0.6600 and 0.6015, respectively (i.e., there are only 150
×
0.6600
=
99 and 150
×
0.6015
=
90 devices whose data rate requirements have been satisfied, resp.). Comparing these curves, we can also conclude that the “PC + PSO” scheme is more preferable than other schemes.


## 6.2.1. Convergence

We show in Figure2 a typical trace of the progression of benefits for guided stochastic search in all schemes, where “PC” and “Sched” represent power control and scheduling based resource allocation algorithm, respectively. We can find that the payoff of the best location selection is increased gradually and will be converged to a constant value finally. Therefore, the curves in Figure 2 show that the proposed schemes are converged to a steady state. Additionally, we can observe that the solution quality and the required number of iterations to converge are significantly different from each other. Firstly, the final values of payoff for different schemes are different. Specifically, the “PC + PSO” scheme can achieve the highest payoff (i.e., 128.5030) among all schemes. Recall that the payoff is defined as the sum of satisfaction ratio over all devices where the satisfaction ratio of a device is defined as the ratio between achieved data rate and the required data rate. For this set of simulation experiments, since there are totally 150 devices (as stated in the beginning of Section 6.1), the value of payoff will not be higher than 150. Therefore, a payoff of 128.5030 means that most data rate requirements have been satisfied. Secondly, forK-means related schemes (i.e., the “PC +K-means” and “Sched +K-means” schemes), although their payoff is not high (i.e., 104.8572 and 100.1876), the required numbers of iterations to converge (i.e., 2 and 2) are much smaller than other schemes; that is, they converge much faster than other schemes. Therefore, we can conclude that different schemes can achieve different tradeoffs between solution quality and convergence rate.Figure 2
Convergence of the proposed schemes.For any devicej, if its uplink data rate requirement is met (i.e., C
^
j
≥
C
j), we say this device is satisfied. Further, we define the supporting ratio as the ratio between the number of devices which have been satisfied and the total number of devices. In the following simulation experiments, we will evaluate the impact of the number of channels (i.e., the total bandwidth), the number of BSs, and the number of devices on the performance (i.e., the supporting ratio) of all these six schemes. Additionally, we would like to claim that all the values plotted in Figures 3, 4, and 5 are obtained after the algorithms have converged to a steady state.Figure 3
Impact of the number of channels.Figure 4
Impact of the number of BSs.Figure 5
Impact of the number of devices.


## 6.2.2. Impact of the Number of Channels

The number of channels is equal toW
/
W
0, where W is the total bandwidth. Figure 3 shows the supporting ratio of all proposed schemes when the total bandwidth W or, equivalently, the number of channels is varied. For this set of simulation experiments, there are totally 150 devices, for which the sum of data rate requirements is 50
×
C
1
+
50
×
C
2
+
50
×
C
3
=
65Mbps. We set the number of BSs B to be 10. It can be observed that when the total bandwidth (i.e., the number of channels) increases, the supporting ratio increases. Specifically, when the total bandwidth is 9 MHz (i.e., the number of channels is 50), the supporting ratio of the “PC + PSO” and “PC + SA” schemes is as high as 1 (i.e., the data rate requirements of all 150 devices have been satisfied), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8713 and 0.8605, respectively (i.e., there are still 150
×
(
1
-
0.8713
)
=
20 and 150
×
(
1
-
0.8605
)
=
21 devices whose data rate requirements are not satisfied, resp.).Finally, it can be observed that the “PC + PSO” scheme is the best among all other schemes, which will be validated again by the following simulation results. This is due to two aspects of reasons. For the first reason, SA and PSO are metaheuristics, which efficiently explore the search space to find near-optimal solutions. By searching over a large set of feasible solutions, they can find good solutions with less computational effort compared to simple heuristics (e.g., theK-means method). Therefore, SA and PSO are superior toK-means in finding good solutions. For the second reason, if two devices are close to each other, they could interfere with each other if they use the same RB. For the PC method, the transmission power of each device is controlled so that devices which are close to each other can also share the same RB; for the Sched method, only devices which are far away from each other can share the same RB. Since the PC method allows devices which are close to each other to transmit data simultaneously, it can admit more devices than the Sched method. On the other hand, for the PC method, since there exists interference among neighbor devices, each device will have to increase its transmission power to combat such interference to meet the minimum SINR requirement. This makes devices using the PC method consume more power resource than the Sched method. Therefore, the PC method can admit more devices than the Sched method via consuming more power.


## 6.2.3. Impact of the Number of BSs

Figure4 shows the supporting ratio of all proposed schemes when the number of BSs B is varied. We can observe that when the number of BSs increases, the supporting ratio increases, since the average distance between devices and access points is shortened. Specifically, when the number of BSs is 15, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is 1 and 0.9767, respectively (i.e., there are zero and 150
×
(
1
-
0.9767
)
=
4 devices whose data rate requirements are not satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is just 0.8447 and 0.7743, respectively (i.e., there are still 150
×
(
1
-
0.8447
)
=
24 and 150
×
(
1
-
0.7743
)
=
34 devices whose data rate requirements are not satisfied, resp.). Therefore, we can conclude that the “PC + PSO” scheme is the best one and for the simulated scenario at least 15 BSs shall be deployed so that the supporting ratio of one can be achieved. For the following simulations, we will set the value of B to be 15.


## 6.2.4. Impact of the Number of Devices

Figure5 shows the supporting ratio of all proposed schemes when the number of devices is varied. For convenience, let N
i denote the number of devices of the ith type. Let N
i
,
i
n
i
t denote the initial value of N
i. As stated in the beginning of Section 6.1, we set N
1
,
i
n
i
t
=
50, N
2
,
i
n
i
t
=
50, and N
3
,
i
n
i
t
=
50. We will collect the performance metrics (i.e., the supporting ratio) which is a function of (N
1, N
2, N
3). However, it is hard to visualize high-dimensional data when the dimension is greater than two. Therefore, we run the simulation for three times. For the jth (j
=
1,2
,
3) run, we change the values of N
j
=
N
j
,
i
n
i
t
+
n while keeping the values of other N
i (i
≠
j) fixed to be N
i
,
i
n
i
t, where n
=
10,20,30,40,50. Due to the limited space, we only plot the simulation results of the second run in Figure 5 where the horizontal axis represents the number of devices of the second type. We can observe that when the number of devices increases, the supporting ratio decreases, since the radio resource consumed by each type of devices increases. Specifically, when the number of devices of the second type is increased to be 100, there are totally 50
+
100
+
50
=
200 devices, for which the sum of data rate requirements is 50
×
C
1
+
100
×
C
2
+
50
×
C
3
=
85Mbps. For this scenario, the supporting ratio of the “PC + PSO” and “PC + SA” schemes is still 0.8626 and 0.8420, respectively (i.e., there are 150
×
0.8626
=
129 and 150
×
0.8420
=
126 devices whose data rate requirements can be satisfied, resp.), but the supporting ratio of the “PC +K-means” and “Sched +K-means” schemes is only 0.6600 and 0.6015, respectively (i.e., there are only 150
×
0.6600
=
99 and 150
×
0.6015
=
90 devices whose data rate requirements have been satisfied, resp.). Comparing these curves, we can also conclude that the “PC + PSO” scheme is more preferable than other schemes.


## 7. Conclusions

In this paper, we study the joint BS location selection, transmission power control, and wireless channel allocation problem in OFDMA based private wireless access networks for smart grid. We transform the joint problem into channel allocation and site selection subproblems and solve these two subproblems iteratively. According to the simulation results, the combination of power control based resource allocation algorithm and PSO based location selection algorithm is recommended to solve the joint problem.



---

*Source: 7948018-2016-10-23.xml*