# Improvement of the Global Connectivity using Integrated Satellite-Airborne-
Terrestrial Networks with Resource Optimization

Ahmad Alsharoa, Senior Member, IEEE, and Mohamed-Slim Alouini, Fellow, IEEE
Ahmad Alsharoa is with the Electrical and Computer Engineering Department,
Missouri University of Science and Technology, Rolla, Missouri 65409, USA,
E-mail<EMAIL_ADDRESS>
Mohamed-Slim Alouini is with the Computer, Electrical and Mathematical
Sciences and Engineering (CEMSE) Division, King Abdullah University of Science
and Technology (KAUST), Thuwal, Makkah Province, Saudi Arabia. E-mails:
<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a novel wireless scheme that integrates satellite,
airborne, and terrestrial networks aiming to support ground users. More
specifically, we study the enhancement of the achievable users’ throughput
assisted with terrestrial base stations, high altitude platforms (HAPs), and
satellite station. The goal is to optimize the resource allocations and the
HAPs’ locations in order to maximize the users’ throughput. In this context,
we propose to solve the optimization problem in two stages; first a short-term
stage and then a long-term stage. In the short-term stage, we start by
proposing a near optimal solution and low complexity solution to solve the
associations and power allocations. In the first solution, we formulate and
solve a binary linear optimization problem to find the best associations and
then using Taylor expansion approximation to optimally determine the power
allocations. While in the second solution, we propose a low complexity
approach based on frequency partitioning technique to solve the associations
and power allocations. One the other hand, in the long-term stage, we optimize
the locations of the HAPs by proposing an efficient algorithm based on a
recursive shrink-and-realign process. Finally, selected numerical results show
the advantages provided by our proposed optimization scheme.

###### Index Terms:

Terrestrial base stations, high altitude platforms, satellite station,
optimization.

##  I Introduction

###  I-A Background

With the rapid growth in mobile and wireless devices in addition to huge data
traffic, the traditional terrestrial network is expected to face difficulties
in supporting the demands of the users. In addition, it is infeasible to
develop terrestrial infrastructure in remote areas to provide
telecommunication services. To mitigate these limitations, integrating the
current terrestrial network with high altitude stations has become necessary
to provide global connectivity.

Integrating the terrestrial network with the space network, including
satellite stations, is one of the proposed solutions in order to increase the
network’s coverage and capacity. Several techniques have been studied in the
literature including using multiple spot beams at the satellite station
associated with multiple protocol label switching and spectrum access
controlled [1, 2]. For instance, In [1], a cooperative scheme base on non-
orthogonal multiple access has been proposed, where the satellite station
communicates with the users via the help of terrestrial base station (TBS)
working as a relay. While in [2], the authors propose to use TBSs as amplify
relays to maintain the communication links between multiple satellite stations
and multiple users. Furthermore, several spectrum resources techniques have
been investigated recently to improve the communication link by utilizing the
spectrum in efficient ways such as allocating the system resources to hot
beams in order to meet user demands or to address adverse channels [3, 4, 5].
For example, in [5], the spectrum management scheme of satellite-terrestrial
integration is proposed to address the unpredictable demands of users
associated with the satellite station. The authors in this work introduced a
hunger marketing strategy that manages the spectrum to influence users’
behavior in bandwidth planning and benefit satellite system meanwhile.
Therefore, allowing a more efficient dynamic spectrum management.

However, all traditional satellite communications techniques are constrained
due to the high path-loss attenuation of the communication links between the
satellite stations and the ground users. In addition to that, the satellite
stations can be located in various orbital heights and, thus, causing extra
delay when providing real-time services to ground users. To fill the gap, High
altitude platforms (HAPs) such as airships and balloons operating in the
stratosphere, at altitude of 17 Km to 20 Km, can be a promising wireless
solution that is expected to work along with the existed satellite and
terrestrial networks [6]. This altitude range is chosen because of its low
wind currents and low turbulence which reduces the energy consumptions aiming
to maintain the position of the HAP. Therefore, HAPs can act as aerial base
stations to improve the communication links between satellite stations and
ground users and hence improve the overall network throughput. This satellite-
airborne-terrestrial integrated system can be part of civilian life with high-
reward opportunities in improving the wireless utilization and provisioning
better wireless access for public safety and first responders.

###  I-B Related Works

HAPs acting as wireless BSs have been proposed to help the global connectivity
[7, 8]. The main advantages of using HAPs over the TBSs can be summarized as
follows [6, 9]:

  * •

High coverage area: The broadband coverage area of TBSs (coverage area radius
around 1000 m) is usually limited compare to HAPs (coverage area radius around
30 Km) due to large non-line-of-sight pathloss. Thus, only few HAPs can cover
some small countries [10].

  * •

Dynamic and quick deployment: The HAPs have the ability to fly to
infrastructure-less regions in order to enable on-demand services.

  * •

Low energy consumptions: The HAPs can be equipped with solar panels that
collecting energy during the daytime. Thus, with a careful trajectory
optimization, HAPs can be self powered [11, 12].

On the other hand, the main advantages using HAPs over the satellite stations
can be summarized as follows [7]

  * •

Quick and low cost deployment: HAPs can accommodate temporal and traffic
demand quickly, where one HAP is enough to start the service. Also, HAPs can
play a significant role in emergency or disaster relief applications by flying
to desired areas, in short timely manner, in order to restart the
communications [13]. In addition, the deployment cost of the HAPs is much less
than the satellite deployment cost.

  * •

Low propagation delays and strong signals: Due to the high path-loss
attenuation between satellite stations and ground users, HAPs can provide
services to ground users in lower delay [8].

Several papers in the literature have studied the deployment of the HAPs [14,
11, 12]. For instance, the work proposed in [14] investigates the HAPs’
deployment taking into consideration the quality-of-service (QoS) of ground
users. The authors propose a self-organized game theory model, where the HAPs
are modeled as rational and self-organized players with the goal of achieving
optimal configuration of the HAPs that maximizing the users’ QoS. While the
work in [11], propose trajectory optimization techniques for HAPs equipped
with solar power panels. More specifically, the authors in [11], proposed a
greedy heuristic and realtime solution to optimize the HAPs’ trajectory by
minimizing the consumed energy which is constrained by the amount of the
harvested energy. In [12], the authors extended their work presented in [11],
to include several trajectory optimization methods aiming to maximize the
storage energy in HAPs instead of minimizing the consumed energy.

Furthermore, improving the system throughput has been considered as another
important key factors in HAPs communications. The authors in [15], propose
multicast system model that uses orthogonal frequency division multiple access
(OFDMA) to find the best transmit powers, time slots, and sub-channels in
order to maximize the total ground users’ throughput. In other words, the goal
was to maximize the number of users that receive the requested multicast
streams in the HAP service area in a given OFDMA frame. The improvement of the
multiple HAPs’ capacity is presented in [16], where the authors show that the
HAPs can offer a spectrally efficiency by exploiting the directionality of the
user antenna. In other words, the authors explained how multiple HAPs can
share the same frequency band by taking the advantage of the users’ antenna
directionality. In [17], the authors investigated the multi-user multiple-
input multiple-output (MU-MIMO) in HAP communication, where the HAPs are
equipped with large-scale antenna arrays. The goal was to formulate and solve
a low computational complexity technique that maximizes the signal-to-
interference-noise ratio (SINR) and limits the interference between users.
However, all these works have not considered the back-hauling (BH) link for
the HAPs.

Few research in the literature have considered the integration between
satellite, airborne, and terrestrial networks [18, 19]. For instance, the work
in [18], consider using HAP as a relay to enhance the satellite link. The goal
was to reduce the total energy consumption while achieving certain downlink
users’ QoS from the satellite. While the authors in [19], present the idea of
bidirectional function offloading and its possible applications by exploring
the full advantages of integrated networks. More specifically, the work
studied the virtual network functionality and service function chaining that
enabling network reconfiguration framework.

###  I-C Contributions

This paper studies the resource allocation with front-hauling (FH) and back-
hauling (BH) associations in order to improve the global connectivity using
satellite, airborne, and terrestrial networks integration. Satellite station
and HAPs can play significant role in global connectivity in the case when the
TBSs are overloaded or to support users with high throughput located outside
the TBSs coverage areas (e.g., suburban and remote areas). The objective of
the proposed framework is to improve the downlink throughput of the ground
users while respecting the resource limitations. To the best of our knowledge,
the problem of resource, power management, and associations (including FH and
BH associations) for satellite, airborne, and terrestrial networks integration
has not been discussed so far. The main contributions of this work can be
summarized as follows:

  * •

The objective is to support the terrestrial network with satellite station and
HAPs in order to enhance the network performance. In our framework, an
optimization problem is formulated aiming to maximize the downlink users’
throughput while taking into account into account the power budgets
limitation, associations, and BH constraints.

  * •

We formulate two problems based on how often optimizing the parameters: short-
term stage and long-term stage. In the short-term stage, we solve the FH and
BH associations and power allocations with fixed HAPs’ location. In long-term
stage, and based on average users distribution, we optimize the locations of
the HAPs. In other words, the short-term stage variables can be optimized
frequently, while the long term stage variables can be optimized in long time
periods.

    * –

Short-term stage: Due to the non-convexity of the formulated problem, we
propose two solutions. In the first solution, we start by jointly optimize the
FH and BH association given fixed transmit power levels. Then, optimizing the
transmit powers using Taylor expansion approximations. In the second solution,
we propose a low complexity solution based on frequency partitioning (FP)
technique to optimize the associations and transmit powers.

    * –

Long-term stage: We propose an efficient and low complexity heuristic
algorithm based on shrink-and-realign (SR) process to optimize the locations
of the HAPs. Note that, this algorithm will be optimized once every long time
frame.

  * •

We consider different users objective functions utilities depending on the
level of fairness among users.

  * •

Finally, we analyze the performance of our proposed scheme under different
system parameters.

###  I-D Paper Organization

The remainder of this paper is organized as follows. Section 1 provides the
system model. The problem formulation is given in Section III. Section IV
describes the short-term stage by optimizing the associations and power
allocation solutions. Section V gives the long-term stage by optimizing the
locations of the HAPs. The numerical results are discussed in Section VI.
Finally, the paper is concluded in Section VII.

##  II System Model

We consider an integrated communication network consisting of three tiers: (i)
space tier with one satellite station, (ii) air tier with $L$ HAPs, and (iii)
ground tier with $M$ TBS. In addition, we also consider $W$ gate ways (GWs)
feeder stations to be used for the BH. We aim to provide downlink
communications to $U$ ground users in a certain geographical area as shown in
Fig. 1. In Table I, we summarize the main notations used in this paper.

TABLE I: List of Notations Notation | Description
---|---
$U$ | Number of users
$M$ | Number of TBSs
$L$ | Number of HAPs
$W$ | Number of GWs
$N^{S}$ | Number of available RBs at tier $S$
$\mathbb{J}^{U}_{u}$ | User geographical coordinates
$\mathbb{J}^{S}_{s}$ | BS $s$ geographical coordinates in tier $S$
$h^{S}_{su,n}$ | FH channel gain between BS $s$ and user $u$ over RB $n$
$g_{xy}$ | BH channel gain between $x$ and $y$
$A^{S}_{su}$ | Attenuation gain due to environment effect
$\Omega_{0},\Omega_{1},\Omega_{2}$ | Shadowed Rician fading parameters
$\kappa_{L}$ | Rician fading parameter
$\epsilon^{S}_{su,n}$ | A binary variable indicates the FH association between
| BS $s$ and user $u$ over RB $n$
$\delta_{wl}$ | A binary variable indicates the BH association between
| GW $w$ and HAP $l$
$P^{S}_{su,n}$ | FH transmit power of BS $s$ over RB $n$
$P_{0}$ | BH transmit power
$B^{S}$ | FH bandwidth of BS $s$ in tier $S$
$B_{0}$ | BH bandwidth
$\mathcal{N}_{0}$ | Noise power
$R^{S}_{su,n}$ | FH data rate from BS $s$ to user $u$ over RB $n$
$\bar{R}_{wl}$ | BH data rate from GW $w$ to HAP $l$
$T$ | Maximum shrink-and-realign iterations
Figure 1: System model.

###  II-A Assumptions

We assume that the OFDMA technique is adopted. The available spectrum is
divided into number of resource blocks (RBs), where each RB in tier $S$ has a
bandwidth of $B^{S}$ Hz [20]. We assume that there is no interference between
different tiers, where the available bandwidth is divided sparsely between
these tiers. We denote by $N^{S}$ the number of available RBs at tier $S$
(i.e., $S=0$ for the space tier and $S=L$ for the air tier, and $S=M$ for the
ground tier). In addition to the above assumption, we make the following
practical assumptions: (i) a user is served at most by one BS111We refer to BS
as TBS, HAP, or satellite station. using only one RB. (ii) there is no intra-
cell interference on the downlink between users associated to the same BS as
they are using different sets of orthogonal RBs. (iii) an inter-cell
interference between users associate to different TBSs in the ground tier
(i.e., a TBS with nearby TBSs). On the other hand, we ignore this interference
in the space and air tiers because the satellite station and HAPs can be
equipped with different antennas and different beams where they allow managing
the resources in an efficient way by using different frequency sets (FSs)
[16]. Note that the antennas of HAPs are arranged to produce a regular
hexagonal structure, where multiple beam antenna payload at each HAP serve
multiple ground cells as shown in Fig. 2.

###  II-B Channel Model

We consider a 3D coordinate system where the coordinate of user $u$, BS $s$
are given, respectively, as
$\mathbb{J}^{U}_{u}=[x^{U}_{u},y^{U}_{u},0]^{\prime}$,
$\mathbb{J}^{S}_{s}=[x^{S}_{s},y^{S}_{s},z^{S}_{s}]^{\prime}$,
$S\in\\{M:\text{for TBSs},L:\text{for HAPs},0:\text{for satellite
station}\\}$, where $[.]^{\prime}$ denotes the transpose operator.

####  II-B1 Front-hauling Channel Model

Taking into account the fading and shadowing fluctuations in addition to the
pathloss, the channel gain between BS $s$ and user $u$ can be modeled as:

$h^{S}_{su,n}=\left(\frac{C}{4\pi
d^{S}_{su}f^{S}_{c}}\right)^{2}A^{S}_{su}F^{S}_{su,n},$ (1)

where $C$ and $f^{S}_{c}$ are the speed of light and carrier frequency in tier
$S$, respectively. $d^{S}_{su}$ is the distance between BS $s$ in tier $S$ and
user $u$. In (1), the first factor $\left(C/4\pi
d^{S}_{su}f^{S}_{c}\right)^{2}$ captures propagation and path-loss and the
second $A^{S}_{su}$ is the attenuation gain due to environment effects which
depends on the distance between the BS $s$ and user $u$ and given as [21, 15]:

$A^{S}_{su}=\left\\{\begin{array}[]{ll}A^{M}_{mu}=1\quad\quad,&\hbox{for
ground tier,}\\\
A^{L}_{lu}=10^{\frac{3d^{L}_{lu}\chi}{10z^{L}_{l}}},&\hbox{for air tier,}\\\
A^{0}_{0u}=10^{\frac{3d_{0u}\chi}{10z_{0}}},&\hbox{for space
tier,}\end{array}\right.$ (2)

where $\chi$ is the attenuation factor due to environment effects such as
rain, wind, cloud, etc. The last factor in (1), $F^{S}_{su,n}$, corresponds to
fading distribution between BS $s$ in tier $S$ and user $u$ over RB $n$. For
the ground tier ( i.e., $S=M$, $s=m$), $F^{S}_{su,n}$ corresponds to Rayleigh
fading power between TBS $m$ and user $u$ with a Rayleigh parameter $a$ such
that $E\\{|a|^{2}\\}=1$. For the air tier (i.e., $S=L$, $s=l$), $F^{S}_{su,n}$
is the Rician small scale gain between HAP $l$ and user $u$ over RB $n$ with
Rician factor equal to $\kappa_{L}$ [22, 15]. Finally, for the space tier
(i.e., $S=0$, $s=0$), the $F^{S}_{su,n}$ ia assumed as shadowed Rician fading
based on ($\Omega_{0},\Omega_{1},\Omega_{2}$), where $\Omega_{0}$, and
$2\Omega_{1}$ are the average power of the line-of-sight (LoS) component and
of the multipath component, respectively. $\Omega_{2}$ is a Nakagami parameter
ranging from $0$ to $\infty$ that shows the intensity of the fading [23].
Without loss in generality, fast fading is assumed to be approximately
constant over the subcarriers of a given RB, and independent identically
distributed (i.i.d) over RBs.

Figure 2: Location of the HAPs.

####  II-B2 Back-hauling Channel Model

We assume that the BH channel gain between $x$ and $y$ stations, i.e., between
GW ($x=w$) HAP $l$ ($y=l$) for the main BH link, and between satellite station
($x=0$) and HAP $l$ ($y=l$) for the alternative BH link, can be given as [22,
15, 24, 25]

$g_{xy}=\left(\frac{C}{4\pi d_{xy}f_{c}}\right)^{2}A_{xy}F_{xy},$ (3)

where $F_{xy}$, corresponds to Rician fading distribution between $x$ and user
$y$ with Rician factor equal to $\kappa_{xy}$. The choice of $\kappa_{xy}$
will be depends on the main or alternative BH links.

###  II-C Front-hauling Association

A ground user can be associated with only one BS (i.e., either a TBS, HAP, or
satellite station) at a certain time. Therefore, we introduce a binary
variable $\epsilon^{S}_{su,n}$, where $S\in\\{M,L,0\\}$, $s\in\\{m,l,0\\}$ for
TBS $m$, HAP $l$, and satellite station, respectively, is equal to 1 if BS $s$
is associated with user $u$ over the RB $n$ and 0 otherwise, and is given as
follows:

$\epsilon^{S}_{su,n}=\left\\{\begin{array}[]{ll}1,&\hbox{if BS $s$ is
associated with user $u$ over RB $n$.}\\\
0,&\hbox{otherwise.}\end{array}\right.$ (4)

We assume that each BS can be associated with multiple users. On the other
hand, each user can be associated with one BS at most using one RB. Hence, the
following condition should be respected:

$\sum_{S\in\\{M,L,0\\}}\sum_{s=1}^{S}\sum_{n=1}^{N^{S}}\epsilon^{S}_{su,n}\leq
1,\quad\forall u.$ (5)

In addition, in order to mitigate the intra-cell interference inside each cell
corresponding to BS $s$ in tier $S$, we assume that different RBs are
allocated to different users that associated with same BS $s$. Therefore, the
following condition should be satisfied, respectively:

$\sum_{u=1}^{U}\epsilon^{S}_{su,n}\leq 1,\quad\forall s,\forall S,\forall
n=1,..,N^{S}.$ (6)

###  II-D Back-hauling Association

It is assumed that HAP $l$ cab be associated with either GW $w$ as a main BH
link or with the satellite station as an alternative BH link based on the
users distributions and the quality of the BH link as shown in Fig. 1.
Therefore, we introduce another binary variable $\delta_{wl}$ for theBH
association where $\delta_{wl}$ ($w=0$ for satellite station and $w=1,..,W$
for GWs) is equal to 1 if HAP $l$ is associated with station $w$ and 0
otherwise. Without loss of generality, we assume that each HAP should be
strictly associated with one station (either one GW or satellite station).
Therefore, the following equality should be respected:

$\sum\limits_{w=0}^{W}\delta_{wl}=1,\quad\forall l.$ (7)

Finally, we denote by $\bar{L}_{w}$ the maximum number of HAPs that can be
associated to station $w$ in the BH, such that:

$\sum\limits_{l=1}^{L}\delta_{wl}\leq\bar{L}_{w}\quad\forall w.$ (8)

###  II-E Downlink Data Rates

It is assumed that the total spectrum is shared sparsely between tiers. The
achievable FH data rate of user $u$ served from a BS $S$, where
$S\in\\{M,L,0\\}$, over RB $n$ can be given as:

$R^{S}_{su,n}=B^{S}\epsilon^{S}_{su,n}\log_{2}\left(1+\frac{P^{S}_{su,n}\,h^{S}_{su,n}}{\mathcal{I}^{S}_{su}+\mathcal{N}_{0}B^{S}}\right),$
(9)

where $P^{S}_{su,n}$ is the BS transmitted power allocated to RB $n$,
$\mathcal{N}_{0}$ is the noise power, and $\mathcal{I}^{S}_{u}$ is the inter-
cell interference at the user $u$ caused by closest BS (no intra-cell
interference on the downlink direction between different tiers is assumed) and
expressed as follows:

$\mathcal{I}^{S}_{su}=\left\\{\begin{array}[]{ll}\sum\limits_{\begin{subarray}{c}\tilde{m}=1\\\
\tilde{m}\neq
m\end{subarray}}\limits^{M}\left(\sum\limits_{\begin{subarray}{c}\tilde{u}=1\\\
\tilde{u}\neq
u\end{subarray}}^{U}\epsilon^{M}_{\tilde{m}\tilde{u},n}P^{M}_{\tilde{m}\tilde{u},n}\right)h^{M}_{\tilde{m}u,n},&\hbox{for
ground tier,}\\\ 0,&\hbox{for air tier,}\\\ 0,&\hbox{for space
tier,}\end{array}\right.$ (10)

where $\epsilon^{M}_{\tilde{m}\tilde{u},n}$ is representing the exclusivity of
the TBS $m$ and RB allocation: $\epsilon^{M}_{\tilde{m}\tilde{u},n}=1$, if RB
$n$ of nearby station is allocated to another user $\tilde{u}$ from TBS $m$,
and $\epsilon^{S}_{\tilde{s}\tilde{u},n}=0$, otherwise. In fact, since the
same RB might be allocated to the more than one user in different TBSs
simultaneously in the ground tier, an inter-cell interference might be caused
to some users. In (10), it can be noticed that the inter-cell interference is
0 for both air and space tier since we ignored this interference because the
HAPs and satellite station are assumed to be equipped with different antennas
and different beams that allow managing the resources in an efficient way by
using different FSs for different ground cells [16].

Therefore, the BH data rate from station $w$ to HAP $l$ can be expressed as:

$\bar{R}_{wl}=\delta_{wl}B_{0}\log_{2}\left(1+\frac{P_{0}g_{wl}}{\mathcal{N}_{0}B_{0}}\right),$
(11)

where $B_{0}$ and $P_{0}$ are the BH bandwidth and transmit power at station
$w$, respectively.

##  III Problem Formulation

Our goal is to maximize the downlink data rate utility of ground users by
optimizing the FH and BH associations, BSs’ transmit power, and HAPs’
locations. Based on the system parameters, the optimizer will determine
whether using satellite station or HAPs would be more efficient than using
TBSs. For remote areas or heavy loaded areas where the TBSs’ would not able to
support all ground users, the optimizer may decide to use the HAPs and
satellite station when needed to support the ground users. This depends on
many factors such as the users’ location, number of the users to be served,
and existence of the TBSs. For instance, if the users in remote areas outside
the coverage of TBSs, then the satellite station and HAPs will try to
accommodate these users. In the case of highly loaded networks, the optimizer
is forced to use the network full capacity including the HAPs and satellite
station in order to meet the users’ demand. The optimization problem that we
formulate will also optimize the locationsof the HAPs and the BH association
such that the throughput is maximized. Therefore, our optimization problem can
be formulated as follows:

$\displaystyle\underset{\begin{subarray}{c}\epsilon^{S}_{su,n},\delta_{wl}\\\
P^{S}_{su,n},\mathbb{J}^{L}_{l}\end{subarray}}{\text{maximize}}\quad\mathcal{U}(R_{u})$
(12) subject to: $\displaystyle
0\leq\sum\limits_{n=1}^{N^{S}}\sum\limits^{U}_{u=1}\epsilon^{S}_{su,n}P^{S}_{su,n}\leq\bar{P}_{S},\quad\forall
s,S\in\\{M,L,0\\}$ (13)
$\displaystyle\sum\limits_{n=1}^{N^{L}}\sum\limits^{U}_{u=1}R^{L}_{lu,n}\leq\sum\limits_{w=0}^{W}\bar{R}_{wl},\quad\forall
l,$ (14)
$\displaystyle\sum_{S\in\\{M,L,0\\}}\sum_{s=1}^{S}\sum_{n=1}^{N^{S}}\epsilon^{S}_{su,n}\leq
1,\quad\forall u,$ (15) $\displaystyle\sum_{u=1}^{U}\epsilon^{S}_{su,n}\leq
1,\quad\forall s,\forall S,\forall n=1,..,N^{S},$ (16)
$\displaystyle\sum\limits_{w=0}^{W}\delta_{wl}=1,\quad\forall l,$ (17)
$\displaystyle\sum\limits_{l=0}^{L}\delta_{wl}\leq\bar{L}_{w}\quad\forall w,$
(18)

where $\mathcal{U}(R_{u})$ denotes the data rate utility of all users.
Constraint (13) represents the peak power constraints at BS $s$. Constraint
(14) represents the BH constraint of HAPs. Note that, we assume that the BH
links of TBSs using fiber links and satellite station using feeder link are
perfect, and hence not considering them in the BH constraint. Constraint (15)
is to ensure that each ground user can be associated with one BS over one RB.
Constraint (16) is to ensure there are no intra-cell interference between
users associated to the same BS. Finally, constraints (17) and (18) represent
the BH association conditions of HAPs.

###  III-A Utility Selection

In this section, we characterize two different utility metrics that will be
employed in the optimization problem given in (12)-(18).

####  III-A1 Max-Sum Utility (MSU)

The utility of this metric is equivalent to the sum FH data rate of the ground
users $\mathcal{U}(R_{u})=\sum^{U}_{u=1}R_{u}$ as it promotes users with
favorable channel gains and interference by allocating to them the best
resources. On the other hand, using this utility will deprive users with bad
channel gains and interference from the resources and thus they will have very
low data rates [26].

####  III-A2 Max-Min Utility (MMU)

Due to the unfairness of MSU resource allocation, the need for more fair
utility metrics arises. Max-min utility (MMU) is attempting to maximize the
minimum data rate in the total network such as
$\mathcal{U}(R_{u})=\underset{u}{\min}(R_{u})$ [27] Note that, by increasing
the priority of users having lower rates, MMU leads to more fairness in the
network. In order to simplify the problem for this approach, we introduce a
new decision variable $R_{\min}=\underset{u}{\min}(R_{u})$. Therefore, our
optimization problem can be re-formulated as:

$\displaystyle\underset{\begin{subarray}{c}\epsilon^{S}_{su,n},\delta_{wl}\\\
P^{S}_{su,n},\mathbb{J}^{L}_{l},R_{\min}\end{subarray}}{\text{maximize}}\quad
R_{\min}$ (19) subject to: $\displaystyle R_{u}\geq R_{\min},\quad\forall u,$
(20)
$\displaystyle\eqref{powerm},\eqref{rate_backhauling},\eqref{asso},\eqref{RB_BS},\eqref{asso_backhauling1},\eqref{asso_backhauling2}.$

The formulated optimization problem in (12)-(18) is a mixed integer non-linear
programming (MINLP), and solving it is a challenging task. In order to
simplify the problem, we propose to solve it in two stages: short-term stage
and long-term stage. In the former stage, we propose two solutions (near
optimal and low complexity solutions) to find the best associations and
transmit power allocations. While in the latter stage, the problem of
optimizing the locations of HAPs is investigated.

##  IV Short-term Stage

In the short-term stage and considering fix HAPs’ locations, we firstly solve
for the FH associations (i.e, $\epsilon^{S}_{su,n}$) and BH associations
(i.e., $\delta_{wl}$) using uninform power distributions, i.e.,
$P^{S}_{su,n}=\bar{P}_{S}/N^{S}$. We then optimize the transmit powers of the
BSs for these associations by approximating the optimization problem using
Tyler expansion.

In the sequel, we propose two solutions in this stage. In the first solution,
we propose a near optimal solution based on Taylor expansion approximation.
While in the second solution, an low complexity heuristic approach using
frequency partitioning (FP) technique is proposed, where we omit the inter-
cell interference among TBSs and, thus, solve the problem quickly.

###  IV-A Near Optimal Solution

In fact, by fixing the transmit powers, it can be seen that the optimization
problem becomes linear binary optimization problem in terms of
$\epsilon^{S}_{su,n}$ and $\delta_{wl}$, except (12) which is non linear with
respect to $\epsilon^{S}_{su,n}$ due to the existence of the
$\mathcal{I}^{M}_{mu}$ term in (10). On the other hand, by fixing
$\epsilon^{S}_{su,n}$ and $\delta_{wl}$, the optimization problem is convex
problem in $P^{S}_{su,n}$ except constraints (12) and (14). Therefore, in
order to solve the problem iteratively (solving the associations and them
transmit powers), the goal is to linearize (12) respects to
$\epsilon^{S}_{su,n}$ with fixed $P^{S}_{su,n}$. Then, approximate (12) and
(14) to convex ones respects to $P^{S}_{su,n}$ with fixed
$\epsilon^{S}_{su,n}$ and $\delta_{wl}$.

It can be notice that $\mathcal{I}^{M}_{mu}$ in (10) can be re-write as
$\sum\limits_{\begin{subarray}{c}\tilde{m}=1\\\ \tilde{m}\neq
m\end{subarray}}\limits^{M}\left(\sum\limits_{\begin{subarray}{c}\tilde{u}=1\\\
\tilde{u}\neq
u\end{subarray}}^{U}P^{M}_{\tilde{m}\tilde{u},n}\right)h^{M}_{\tilde{m}u,n}$
by adding the following constraint:

$0\leq
P^{M}_{\tilde{m}\tilde{u},n}\leq\epsilon^{M}_{\tilde{m}\tilde{u},n}\bar{P}_{M},\quad\forall\tilde{m},\forall\tilde{u}.$
(21)

Now, the optimization problem becomes a linear one with respect to
$\epsilon^{S}_{su,n}$ and $\delta_{wl}$ and thus, it can be solved using on-
the-shelf softwares such as Gurobi/CVX interface [28].

On the other hand, by fixing the association variables (i.e.,
$\epsilon^{S}_{su,n}$ and $\delta_{wl}$), the optimization problem in
(12)-(18) can be re-write as:

$\displaystyle\underset{P^{S}_{su,n}}{\text{maximize}}\quad\mathcal{U}(R_{u})$
(22) subject to: $\displaystyle
0\leq\sum\limits_{n=1}^{N^{S}}\sum\limits^{U}_{u=1}\epsilon^{S}_{su,n}P^{S}_{su,n}\leq\bar{P}_{S},\quad\forall
s,S\in\\{M,L,0\\}$ (23)
$\displaystyle\sum\limits_{n=1}^{N^{L}}\sum\limits^{U}_{u=1}R^{L}_{lu,n}\leq\sum\limits_{w=0}^{W}\bar{R}_{wl},\quad\forall
l.$ (24)

It can be noticed that the optimization problem (22)- (24) is convex problem
in $P^{S}_{su,n}$ except constraints (22) and (24). Therefore, the goal is to
convert these constraints into convex ones in terms of $P^{S}_{su,n}$ in order
to solve the power optimization problem efficiently.

####  IV-A1 Approximation of The Objective Function (22)

: Let us start with objective function (22) by expanding it as follows:

$\displaystyle R_{u}=$ $\displaystyle
B^{M}\sum_{m=1}^{M}\sum_{n=1}^{N^{M}}\epsilon^{M}_{mu,n}\log_{2}\left(1+\frac{P^{M}_{mu,n}\,h^{M}_{mu,n}}{\mathcal{I}^{M}_{u}+\mathcal{N}_{0}B^{M}}\right)+$
$\displaystyle
B^{L}\sum_{l=1}^{L}\sum_{n=1}^{N^{L}}\epsilon^{L}_{lu,n}\log_{2}\left(1+\frac{P^{L}_{lu,n}\,h^{L}_{lu,n}}{\mathcal{N}_{0}B^{L}}\right)+$
$\displaystyle
B^{0}\sum_{n=1}^{N^{0}}\epsilon^{0}_{0u,n}\log_{2}\left(1+\frac{P^{0}_{0u,n}\,h^{0}_{0u,n}}{\mathcal{N}_{0}B^{0}}\right).$
(25)

In (IV-A1), since we are maximizing the utility, then we need the function to
be concave. Note that the second and third terms are concave functions in
terms of $P^{L}_{lu,n}$ and $P^{0}_{0u,n}$. In order to convert the objective
function to a concave function, the first term in (IV-A1) needs to be concave
it terms of $P^{M}_{mu,n}$. Let us start by expanding the first term in
(IV-A1) as follows:

$\displaystyle
R^{M}_{mu,n}=\underbrace{\epsilon^{M}_{mu,n}B^{S}\log_{2}\left(\mathcal{N}_{0}B^{S}+\sum\limits_{m=1}^{M}\sum\limits_{u=1}^{U}P^{M}_{mu,n}h^{M}_{mu,n}\right)}_{\hat{R}^{M}_{mu,n}}$
$\displaystyle\underbrace{-\epsilon^{M}_{mu,n}B^{S}\log_{2}\left(\mathcal{N}_{0}B^{S}+\sum_{\begin{subarray}{c}\tilde{m}=1\\\
\tilde{m}\neq
l\end{subarray}}\limits^{M}\sum_{\begin{subarray}{c}\tilde{u}=1\\\
\tilde{u}\neq
u\end{subarray}}^{U}\epsilon^{M}_{\tilde{m}\tilde{u},n}P^{M}_{\tilde{m}\tilde{u},n}h^{M}_{\tilde{m}u,n}\right).}_{\check{R}^{M}_{mu,n}}$
(26)

Note that $\hat{R}^{M}_{mu,n}$ is concave, because the $\log$ of an affine
function is concave [29]. Also, $\check{R}^{M}_{mu,n}$ is a convex function,
and thus, it needs to be converted to a concave function. To tackle the non-
concavity of $\check{R}^{M}_{mu,n}$, the successive convex approximation (SCA)
technique can be applied where in each iteration, the original function is
approximated by a more tractable function at a given local point as given in
algorithm 1. Recall that $\check{R}^{M}_{mu,n}$ is convex in
$P^{M}_{\tilde{m}\tilde{u},n}$, and any convex function can be globally lower-
bounded by its first order Taylor expansion at any point. Therefore, given
$P^{M}_{\tilde{m}\tilde{u},n}(r)$ in iteration $r$, we obtain the following
lower bound for $\check{R}^{M}_{mu,n}(r)$:

$\displaystyle\check{R}^{M}_{mu,n}(r)\geq$
$\displaystyle-\epsilon^{M}_{mu,n}B^{S}\log_{2}\left(\psi(r)\right)$
$\displaystyle-\frac{\epsilon^{M}_{\tilde{m}\tilde{u},n}h^{M}_{\tilde{m}u,n}}{\ln(2)\psi(r)}(P^{M}_{\tilde{m}\tilde{u},n}-P^{M}_{\tilde{l}\tilde{u},n}(r)),$
(27)

where $\psi(r)=\mathcal{N}_{0}B^{S}+\sum_{\begin{subarray}{c}\tilde{m}=1\\\
\tilde{m}\neq l\end{subarray}}^{M}\sum_{\begin{subarray}{c}\tilde{u}=1\\\
\tilde{u}\neq
u\end{subarray}}^{U}\epsilon^{M}_{\tilde{m}\tilde{u},n}P^{M}_{\tilde{m}\tilde{u},n}h^{M}_{\tilde{m}u,n}$.

Algorithm 1 SCA Algorithm

Select feasible initial values $P^{M}_{\tilde{m}\tilde{u},n}$.

r=1.

repeat

Solve the optimization problem (22)-(24) using the interior-point method to
determine the new approximated solution $P^{M}_{\tilde{m}\tilde{u},n}(r)$.

until Convergence.

Now it can be seen that the objective function in (IV-A1) is a concave
function in terms of $P^{S}_{su,n}$.

####  IV-A2 Approximation of Constraint (24)

: We can approximate this constraint by ensuring that the data rate from HAP
$l$ to any associated users $u$ is smaller that the average BH constraint. In
other words, constraint (14) can be approximated as:

$\sum\limits_{n=1}^{N^{L}}\epsilon^{L}_{lu,n}\left(1+\frac{P^{L}_{lu,n}\,h^{L}_{lu,n}}{\mathcal{N}_{0}B^{S}}\right)\leq\frac{\omega}{\sum\limits_{n=1}^{N^{L}}\epsilon^{L}_{lu,n}},\quad\forall
l,\forall u,$ (28)

where $\omega=2^{(\sum_{w=0}^{W}\bar{R}_{wl})/B^{S}}$.

Now, our power allocation optimization problem given in (22)-(24) becomes
convex problem in respect to $P^{S}_{su,n}$ for fix associations and HAPs’
locations. Thus, the duality gap of our convex power allocation problem in
OFDMA system is zero. Hence, We can solve our convex transmit power allocation
optimization problem by exploiting its strong duality.

###  IV-B Low Complexity Solution

In subsection, we propose a low complexity and efficient technique to mitigate
the inter-cell interference between users associate to different TBSs in the
ground tier. We divide the users into two groups, 1) center users: users
located in areas close to the center of the TBSs’ cells and 2) edge users:
users located in the edges of the TBSs’ cells. We assume that TBSs can be
associated with the center users only. In this case, inter-cell interference
is assumed to be $\mathcal{I}^{M}_{mu}=0$ due to large distances between users
that using the same frequency bands in the ground tier. Hence, the association
problem is linear and we can omit constraint (21). On the other hand, the edge
users can be served by the HAPs and satellite station as shown in Fig 3.
Hence, (22) becomes a convex function with respect to $P^{S}_{su,n}$.

Therefore, the formulated optimization problem in (12)- (14) is a linear
assignment problem with respect to $\epsilon^{S}_{su,n}$ and $\delta_{wl}$ and
can be solved efficiently by using the Hungarian algorithm with complexity of
$(MN^{M}+LN^{L}+N^{0})^{3}$ [30].

On the other hand, by only approximating (24), the formulated optimization
problem in (22)- (24) becomes a convex optimization problem in terms of
$P^{S}_{su,n}$. Therefore, it can be solved efferently by solving the its dual
problem.

Figure 3: Frequency partitioning technique.

##  V Long-term Stage

Due to the non-convexity of the formulated optimization problem (12)-(18) even
with fixed associations and BSs transmit powers, we introduce a low complexity
and efficient algorithm based on the SR process. The proposed algorithm has
many advantages over other heuristic algorithms proposed in the literature
such as simple implementation, low complexity, and quick convergence to a near
optimal solution. Furthermore, since we solve this problem for long-term
stage, where the time slots are relatively long compared to the channel
coherence time and hence, we focus on the average statistics (such as average
channel gains) of the network. This implies that average users’ throughput is
assumed instead of instantaneous throughput.

We start our algorithm by generating initial next position candidates
$T_{l},\forall l$ as a circle with radius $r(i)$ around all current locations
of the HAPs to form the inial population. Next, we solve the average
associations and transmit powers of the BSs to determine maximum number of
average users inside the HAPs coverage areas for each candidates combination.
In other words, determine the value
$U^{L}_{\max}=\sum^{L}_{l=1}\sum^{N^{S}}_{n=1}\sum^{U}_{u=1}\epsilon^{L}_{lu,n}$,
after excluding the users associated to TBSs. We then find the initial best
local candidate combinations
$T^{i,\text{local}}=t_{l}^{i,\text{local}},\forall l$ that gives the maximum
number of users associated with HAPs for iteration $i$. After that, we apply
the SR process recursively to find the best global solution
$T^{*}=t_{l}^{*},\forall l$ by generating a new candidates on a circle of
radius (r(i+1)=r(i)/2) around each local solution. We repeat this process
until the size of the sample space decreases below a certain threshold
$I_{\max}$ or no improvement can be made. Fig. 4 shows an example of the
proposed algorithm using two HAPs ($L=2$), $T=4$, and three maximum iteration
$I_{\max}=3$. The details of the HAPs’ locations algorithm that optimize the
locations of the HAPs based on average users’ locations are given in Algorithm
2.

Figure 4: Proposed heuristic approach. Algorithm 2 HAPs’ Locations Algorithm

1: i=1.

2: Generate initial candidates $T$ in a circle of radius $r=r(i)$ around each
HAP $J_{l}^{\mathcal{L}}(t_{l}),\;l=1\cdots L$.

3: while Not converged or reaching $I_{\max}$ do

4: for $l=1\cdots L$ do

5: for $t_{l}=1\cdots T$ do

6: Find the optimized value of $\epsilon^{S}_{su,n}$, $\delta_{wl}$, and
$P^{S}_{su,n}$ as explained in Section. IV for average statistics.

7: Compute
$U^{L}_{\max}=\sum^{L}_{l=1}\sum^{N^{S}}_{n=1}\sum^{U}_{u=1}\epsilon^{L}_{lu,n}$.

8: end for

9: end for

10: Find
$t_{l}^{i,\text{local}}=\underset{t_{t}}{\arg\mathrm{max}}\,U^{L}_{\max}$,
(i.e., $t_{l}^{i,\text{local}}$ indicates the index of the best local
candidate that results in the highest $U^{L}_{\max}$ for iteration $i$).

11: $r=r(i)/2$

12: Start applying SR process for the local solution.

13: i=i+1.

14: end while

##  VI Simulation Results

In this section, selected simulation results are provided to demonstrate the
advantages of our proposed solution. The simulation results are set within
area of 180 Km $\times$ 180 Km. Within this area, $U$ users are distributed in
three different subareas (i.e., subarea 1: 30 Km2, subarea 2: 30 Km2, and
subarea 3: the remaining) with different dense distributions. Subarea 1
contains $M=9$ TBSs with coordinates are: x: (75 Km to 105 Km), and y: (0 Km
to 30 Km) and contains 40% of the total number of users. Subarea 2, has no
TBSs with coordinates are: x: (75 Km to 105 Km), and y: (150 Km to 180 Km) and
contains 30% of the total number of users. In other words, subarea 2 has dense
users but with no infrastructure (e.g., it ca flying at a fixed altitude be an
area with a damaged infrastructure or temporarily high traffic area). While
subarea 3 is the remaining area and contains 30% of the total number of users.
For example, subarea 1 and subarea 2 can be considered as urban areas with and
without TBSs, respectively, while subarea 3 can be considered as rural are.
The satellite station is assumed to be in a fixed location with the coordinate
[90,90,2000] Km. Also, we consider $L=5$ HAPs flying at a fixed altitude
$z^{L}_{l}=18$ Km, $\forall l=1,..,L$. We assume that the HAPs initially start
at location $\mathbb{J}^{L}_{1}=[90,90,18]$ Km,
$\mathbb{J}^{L}_{1}=[30,30,18]$ Km, $\mathbb{J}^{L}_{1}=[150,30,18]$ Km,
$\mathbb{J}^{L}_{1}=[30,150,18]$ Km, $\mathbb{J}^{L}_{1}=[150,150,18]$ Km. We
assume that $W=4$ and located in the four corners of the desired area. We
assume $N^{M}=50,N^{L}=100$, and $N^{0}=200$ available RBs in the FH in our
simulations. The maximum transmit power of TBS, HAP, and satellite station
are, respectively, given as {40,100,250} W. The noise power $N_{0}$ is assumed
to be $-174$ dBm. In Table II, we present the values of the remaining
environmental parameters used in the simulations unless otherwise stated [14,
15, 23].

TABLE II:  Simulation parameters Constant | Value | Constant | Value | Constant | Value
---|---|---|---|---|---
$f_{c}^{M}$ (GHz) | 1.8 |  $f_{c}^{L}$ (GHz) | $3.0$ |  $f_{c}^{0}$ (GHz) | $5.0$
$f_{c}$ (GHz) | $3.4$ | $\chi$ | $2$ |  $\kappa_{L}$,$\kappa_{0}$ | $10$
$B^{M}$ (kHz) | 1.8 |  $B^{L}$ (MHz) | $1.0$ |  $B^{L}$ (MHz) | $2.0$
$\Omega_{0}$ | $0.372$ | $\Omega_{1}$ | $0.0129$ | $\Omega_{2}$ | $7.64$

Fig. 5 plots the optimization of HAPs’ locations and BH associations using
average users location for two high and low users densities with $P_{0}=40$ W,
$B_{0}=4$ MHz, and $\bar{P}_{l}=100$ W. The figure also shows the BH
association of HAPs with the GWs. For instance, Fig. 5-a shows that the HAPs
try to accommodate maximum number of users by finding the best HAPs’ locations
that improved the FH and BH links at the same time. Note that the users
located outside the coverage areas of HAPs and TBSs are associated with
satellite station. While, in the case of low dense users, HAPs try to
associated with all users as shown in Fig. 5-b. This is can explained by the
fact that associating with HAPs, in general, provide a better data rate
instead of associating to satellite station due to the high path-loss
attenuation between satellite station and ground users. In this case, the HAPs
can provide services to ground users with much lower delay and higher
throughput.

Figure 5: HAP placement optimization with BH associations.

Fig. 6 plots the average data rate per user (i.e., $\sum^{U}_{u=1}$/$U$)
versus total number of users (i.e., subarea 1: 40%, subarea 2: 30%, subarea 3:
30%) with $P_{0}=40$ W, $B_{0}=4$ MHz, and $\bar{P}_{l}=100$ W. Our proposed
solutions (i.e., approximated and low complexity solutions) are compared with
two benchmark solutions: 1- optimizing only the FH and BH associations and the
HAPs’ locations with uniform power distribution (i.e.,
$P^{S}_{su,n}=\bar{P}_{S}/N^{S}$), and 2- optimizing only the placement of the
HAPs using random FH and BH associations with uniform power distribution. The
figure shows that for fixed resources, as $U$ increases, the average data rate
decreases due to the limitation of the available resources. Furthermore, the
figure shows that the approximate solution and low complexity solution achieve
almost the same performance for low values of $U$. However, there will be a
gap between the two proposed solutions when $U$ is relatively large. This is
can be explained by the fact that the low complexity solution forces some HAPs
to cover the TBSs coverage areas in order to implement the frequency
partitioning technique as shown in Fig. 3. This will not effect the
performance when $U$ is relatively low, but when $U$ is large, and because of
the limitation number of HAPs, then the HAPs located in the TBSs coverage
areas maybe be better to move to different locations. Thanks to the HAPs,
because HAPs have large coverage areas of HAP, this gap for large $U$ is still
acceptable. This figure also shows that our proposed solutions outperform the
other two benchmarks solutions. For instance, using $U=400$, our proposed
solution can enhance the average rate throughput by at least 39% and 88%
compared to optimize the associations with uniform power and to random
associations with uniform power, respectively. Furthermore, it can be noticed
that the gap between the proposed solutions and benchmarks solutions is
increased as $U$ increases. This is due to the fact, as $U$ increases, the
need of managing and optimizing the power is needed more.

Figure 6: Average data rate per user as a function of number of users.

All simulations show that MSU leads to the highest average data rate in the
system. However, this comes at the expense of fairness as it is shown in Table
III. Indeed, the table compares between the two different utilities for the
same channel realization with fixed $P_{0}=40$ W, $B_{0}=4$ MHz,
$\bar{P}_{l}=100$ W, and $U=400$ (for this realization, 160 user associated to
TBSs, 172 user associated to HAPs 172, and 68 user associated to satellite
station). In Table III, we denote $\bar{R}^{S}$, $R^{S}_{\max}$, and
$R^{S}_{\min}$ as average rate, maximum rate, and minimum rate in tier $S$,
respectively. Also, $P^{S}_{\max}$ and $P^{S}_{\min}$ denoted as maximum and
minimum transmit powers in tier $S$. By using one realization, it can be shown
that MSU enhances the average data rate, by allocating most of the resources
to users having the best channel conditions. On the other hand, MMU approach
maximizes the minimum data rate and provides almost the same rate for all
users. Hence, MMU leads to more fairness performance. The choice of the
utility is related to the service given to the users. For instance, if the
application requires same downlink rates betweenisers, then MMU can be used.
on the other hand, if it consists in a pure transmission without priorities,
then MSU could be employed.

TABLE III: Comparison between MSU and MMU for fixed $P_{0}=40$ W, $B_{0}=4$ MHz, $\bar{P}_{l}=100$ W, and $U=400$ | Users associated | $\bar{R}^{S}$ | ($R^{S}_{\max},P^{S}_{\max}$) | ($R^{S}_{\min},P^{S}_{\min}$)
---|---|---|---|---
| with | Mbits/s | (Mbits/s,W) | (Mbits/s,W)
MSU | TBSs | $2.14$ | $(4.13,15.25)$ | $(\sim 0,\sim 0)$
HAPs | $1.92$ | $(3.19,39.70)$ | $(.0415,1.2)$
Satellite | $(0.016)$ | $(0.085,97.53)$ | $(\sim 0,\sim 0)$
MMU | TBSs | $(1.91)$ | $(1.96,5.49)$ | $(1.88,8.20)$
HAPs | $(1.50)$ | $(1.81,3.91)$ | $(1.39,4.5)$
Satellite | $(0.01)$ | $(0.01,4.81)$ | $(0.01,4.65)$

Fig. 7 and Fig. 8 illustrate the performance of the average data rate for
users associated with HAPs using $U=400$. For instance, Fig. 7 plots the
effect of the BH bandwidth $B_{0}$ on the average data rate of HAPs’ users for
different BH transmit powers $P_{0}=\\{10,20,30,40\\}$ W with
$\bar{P}_{l}=100$ W. This figure shows that the average data rate of HAPs’
users is improving with the increase of $B_{0}$ up to a certain cutoff value,
that depends on the BH rate constraint as given in 14. This is due to the fact
that starting from this point of $B_{0}$ the average data rate can not be
enhanced further because it depends on the value of $P^{L}_{lu,n}$ which is
limited by $\bar{P}_{L}$ as given in (13). Also, Fig. 7 shows that the cutoff
value depends on the BH transmit power $P_{0}$. As $P_{0}$ increases the
corresponding $B_{0}$ value of the cutoff value decreases in order to respect
constraint 14. In this case, the bottleneck is the FH rate constraint which is
limited by $\bar{P}_{L}$.

Figure 7: Average data rate of HAPs’ users versus BH bandwidth.

On the other hand, to illustrate the BH bottleneck, Fig. 8 plots the average
data rate of HAPs’ users versus HAPs’ peak power $\bar{P}_{L}$ using
$P_{0}=40$ W. The figure shows that as $\bar{P}_{l}$ increases, the average
data rate is increases up to a certain point. This can be explained by
starting from this point of $\bar{P}_{l}$, the average data rate can not be
improved because it depends also on the BH data rate constraint $\bar{R}_{wl}$
as given in 14. Furthermore, it can be noticed that the average data rate is
enhanced as $B_{0}$ increases due to the reason, that increasing $B_{0}$ will
also increase the value of $\bar{R}_{wl}$ and thus, increase the BH
bottleneck.

Figure 8: Average data rate of HAPs’ users versus HAPs’ peak power.

Finally, Fig. 9 plots the convergence speed of the SR algorithm, defined by
the number of iterations needed to reach convergence, for both utilities, MSU
and MMU. Note that one iteration in Fig. 9 corresponds to one iteration of the
“while loop” given in Algorithm 2 line 4-13. It can be noticed that the
algorithm is converge within around 8-13 iterations.

Figure 9: Convergence of the proposed SR algorithm.

##  VII Conclusion

This paper proposed an efficient optimization framework using TBSs, HAPs, and
satellite station to provide connectivity to the ground users taking into
consideration the BH limitation. The objective was to maximize the users’
throughput by optimizing the front-hauling and back-hauling associations,
transmit powers of the base stations, and the HAPs’ locations. We proposed an
approximate and a low complexity solutions to optimally determine the decision
variables. The simulation results illustrated the behavior of our approach and
their significant impacts on the users’ throughput. In our next challenging
task, a free-space optical (FSO) communication link between GW and HAPs will
be considered in order to mitigate the BH bottleneck limitation thus enhance
the performance. However, it will add more complexity to the problem by
optimizing extra parameters such as the LoS angles.

## References

  * [1] X. Yan, H. Xiao, C. Wang, and K. An, “Outage performance of NOMA-based hybrid satellite-terrestrial relay networks,” _IEEE Wireless Communications Letters_ , vol. 7, no. 4, pp. 538–541, Aug. 2018.
  * [2] K. An, M. Lin, T. Liang, J. Wang, J. Wang, Y. Huang, and A. L. Swindlehurst, “Performance analysis of multi-antenna hybrid satellite-terrestrial relay networks in the presence of interference,” _IEEE Transactions on Communications_ , vol. 63, no. 11, pp. 4390–4404, Nov. 2015.
  * [3] U. Park, H. W. Kim, D. S. Oh, and B. J. Ku, “Flexible bandwidth allocation scheme based on traffic demands and channel conditions for multi-beam satellite systems,” in _Proc. of the IEEE Vehicular Technology Conference (VTC Fall), Quebec City, QC, Canada_ , Sep. 2012, pp. 1–5.
  * [4] J. Lei and M. A. Vazquez-Castro, “Joint power and carrier allocation for the multibeam satellite downlink with individual SINR constraints,” in _Proc. of the IEEE International Conference on Communications (ICC), Cape Town, South Africa_ , May 2010, pp. 1–5.
  * [5] F. Li, K. Lam, J. Hua, K. Zhao, N. Zhao, and L. Wang, “Improving spectrum management for satellite communication systems with hunger marketing,” _IEEE Wireless Communications Letters_ , vol. 8, no. 3, pp. 797–800, June 2019.
  * [6] X. Cao, P. Yang, M. Alzenad, X. Xi, D. Wu, and H. Yanikomeroglu, “Airborne communication networks: A survey,” _IEEE Journal on Selected Areas in Communications_ , vol. 36, no. 9, pp. 1907–1926, Sep. 2018.
  * [7] A. Mohammed, A. Mehmood, F. Pavlidou, and M. Mohorcic, “The role of high-altitude platforms (HAPs) in the global wireless connectivity,” _Proceedings of the IEEE_ , vol. 99, no. 11, pp. 1939–1953, Nov 2011.
  * [8] H. Lu, Y. Gui, X. Jiang, F. Wu, and C. W. Chen, “Compressed robust transmission for remote sensing services in space information networks,” _IEEE Wireless Communications_ , vol. 26, no. 2, pp. 46–54, Apr. 2019.
  * [9] ——, “Compressed robust transmission for remote sensing services in space information networks,” _IEEE Wireless Communications_ , vol. 26, no. 2, pp. 46–54, Apr. 2019.
  * [10] S. Karapantazis and F. Pavlidou, “Broadband communications via high-altitude platforms: A survey,” _IEEE Communications Surveys Tutorials_ , vol. 7, no. 1, pp. 2–31, First Quarter 2005.
  * [11] J. Marriott, B. Tezel, Z. Liu, and N. Stier, “Trajectory optimization of solar-powered high-altitude long endurance aircraft,” _Facebook Research_ , Oct. 2018.
  * [12] J. Marriott and B. Thomsen, “Energy-optimized trajectory planning for high altitude long endurance (HALE) aircraft,” _Facebook Research_ , Oct. 2018\.
  * [13] Z. Yang and A. Mohammed, “Wireless communications from high altitude platforms: Applications, deployment, and development,” in _Proc. of the 12th IEEE International Conference on Communication Technology, Nanjing, China_ , Nov. 2010, pp. 1476–1479.
  * [14] R. Zong, X. Gao, X. Wang, and L. Zongting, “Deployment of high altitude platforms network: A game theoretic approach,” in _Proc. of the International Conference on Computing, Networking and Communications (ICNC), Maui, HI, USA_ , Jan. 2012, pp. 304–308.
  * [15] A. Ibrahim and A. S. Alfa, “Using Lagrangian relaxation for radio resource allocation in high altitude platforms,” _IEEE Transactions on Wireless Communications_ , vol. 14, no. 10, pp. 5823–5835, Oct. 2015.
  * [16] D. Grace, J. Thornton, Guanhua Chen, G. P. White, and T. C. Tozer, “Improving the system capacity of broadband services using multiple high-altitude platforms,” _IEEE Transactions on Wireless Communications_ , vol. 4, no. 2, pp. 700–709, Mar. 2005.
  * [17] J. Tong, Y. Lu, D. Zhang, G. Cui, and W. Wang, “Max-min analog beamforming for high altitude platforms communication systems,” in _Proc. of the IEEE International Conference on Communications in China (ICCC), Beijing, China_ , Aug. 2018, pp. 872–876.
  * [18] Z. Chen, T. B. Lim, and M. Motani, “HAP-assisted LEO satellite downlink transmission: An energy harvesting perspective,” in _Proc. of the 15th IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Toronto, ON, Canada_ , June 2014, pp. 194–198.
  * [19] S. Zhou, G. Wang, S. Zhang, Z. Niu, and X. S. Shen, “Bidirectional mission offloading for agile space-air-ground integrated networks,” _IEEE Wireless Communications_ , vol. 26, no. 2, pp. 38–45, Apr. 2019.
  * [20] 3rd Generation Partnership Project, “Evolved universal terrestrial radio access E-UTRA; Physical channels and modulation,” 3GPP TS 36.211 3GPP V 11.2.0, Release 11, Apr. 2013.
  * [21] D. A. J. Pearce and D. Grace, “Optimum antenna configurations for millimetre-wave communications from high-altitude platforms,” _IET Communications_ , vol. 1, no. 3, pp. 359–364, June 2007.
  * [22] E. Falletti, M. Laddomada, M. Mondin, and F. Sellone, “Integrated services from high-altitude platforms: A flexible communication system,” _IEEE Communications Magazine_ , vol. 44, no. 2, pp. 85–94, Feb. 2006.
  * [23] A. Abdi, W. C. Lau, M.-S. Alouini, and M. Kaveh, “A new simple model for land mobile satellite channels: First- and second-order statistics,” _IEEE Transactions on Wireless Communications_ , vol. 2, no. 3, pp. 519–528, May 2003.
  * [24] A. Iqbal and K. M. Ahmed, “Outage probability analysis of multi-hop cooperative satellite-terrestrial network,” in _Proc. of the 8th Electrical Engineering/ Electronics, Computer, Telecommunications and Information Technology (ECTI) Association, Phuket, Thailand_ , May 2011, pp. 256–259.
  * [25] F. Dong, H. Li, X. Gong, Q. Liu, and J. Wang, “Energy-efficient transmissions for remote wireless sensor networks: An integrated HAP/satellite architecture for emergency scenarios,” _Sensors_ , vol. 15, no. 9, pp. 22 266–22 290, 2015.
  * [26] X. Bi, J. Zhang, Y. Wang, and P. Viswanath, “Fairness improvement of maximum C/I scheduler by dumb antennas in slow fading channel,” in _Proc. of the 72nd IEEE Vehicular Technology Conference (VTC Fall), Ottawa, Ontario, Canada_ , Sep. 2010, pp. 1–4.
  * [27] Y. Song and G. Li, “Cross-layer optimization for OFDM wireless networks-Part I: Theoretical framework,” _IEEE Transactions on Wireless Communications_ , vol. 4, no. 2, pp. 614–624, Apr. 2005.
  * [28] “Gurobi Optimizer Reference Manual,” 2016. Available [online]: http://www.gurobi.com/.
  * [29] S. Boyd and L. Vandenberghe, _Convex Optimization_. New York, NY, USA: Cambridge University Press, 2004.
  * [30] H. W. Kuhn, “The Hungarian Method for the Assignment Problem,” _50 Years of Integer Programming 1958-2008_. Berlin, Heidelberg, ch2. 2010.


# The Complexity of Data-Driven Norm Synthesis and Revision

Davide Dell’Anna  Natasha Alechina  Brian Logan  Maarten Löffler
Fabiano Dalpiaz  Mehdi Dastani
Utrecht University {d.dellanna, n.a.alechina, b.s.logan, m.loffler, f.dalpiaz,
<EMAIL_ADDRESS>
###### Abstract

Norms have been widely proposed as a way of coordinating and controlling the
activities of agents in a multi-agent system (MAS). A norm specifies the
behaviour an agent should follow in order to achieve the objective of the MAS.
However, designing norms to achieve a particular system objective can be
difficult, particularly when there is no direct link between the language in
which the system objective is stated and the language in which the norms can
be expressed. In this paper, we consider the problem of synthesising a norm
from traces of agent behaviour, where each trace is labelled with whether the
behaviour satisfies the system objective. We show that the norm synthesis
problem is NP-complete.

##  1 Introduction

There has been a considerable amount of work on using norms to coordinate the
activities of agents in a multi-agent system (MAS) (?). Norms can be viewed as
standards of behaviour which specify that certain states or sequences of
actions in a MAS should occur (obligations) or should not occur (prohibitions)
in order for the objective of the MAS to be realized (?). We focus on
conditional norms with deadlines which express behavioral properties (?).
Conditional norms are triggered (detached) in certain states of the MAS and
have a temporal dimension specified by a deadline. The satisfaction or
violation of a detached norm depends on whether the behaviour of the agent
brings about a specified state before a state in which the deadline condition
is true. Conditional norms are implemented in a MAS through enforcement. That
is, violation of a norm results in the violating agent incurring a sanction,
e.g., a fine; see, e.g., (?; ?) for how to determine an appropriate level of
sanction.

For many applications it is assumed that the MAS developer will design an
appropriate norm to realise the system objective. However, this can be
difficult, particularly when the internals of the agents are unknown, e.g., in
the case of open MAS (?), and when there is no direct connection between the
language in which the system objective is stated and the language in which
norms can be expressed. For example, one objective of a traffic system may be
to avoid traffic collisions, but ‘not colliding’ is not a property under
direct agent control, and prohibition of collisions cannot be stated as a
norm. A poorly designed norm may fail to achieve the system objective, or have
undesirable side effects, e.g., the objective is achieved, but the autonomy of
the agents is restricted unnecessarily.

The increasing availability of large amounts of system behaviour data
introduces the possibility of a new approach to the design of norms, namely
the synthesis of norms directly from data collected during the execution of
the system. For example, data may show that collisions always happen when an
agent’s speed is very high, allowing us to state a norm prohibiting agents
from speeding too much. In this paper, we consider the problem of synthesising
norms from traces of agent behaviour, where each trace is labelled with
whether the behaviour satisfies the system objective. We show that
synthesising a norm (i.e., an obligation or a prohibition) that correctly
classifies the traces (i.e., the norm is violated on traces where the
behaviour does not satisfy the system objective, and is not violated on other
traces) is an NP-complete problem. We also consider the problem of
synthesizing a norm that is “close” to a target norm. This problem is relevant
where there is an existing norm that does not achieve the system objective,
but which is accepted, e.g., by human users of a system, and we wish a minimal
modification that does achieve the objective. We show that the minimal norm
revision problem is also NP-complete.

There has been a considerable amount of work on the automated synthesis of
norms. For example, (?) consider the problem of synthesising a _social law_
that constrains the behaviour of the agents in a MAS so as to ensure that
agents in a _focal_ state are always able to reach another focal state no
matter what the other agents in the system do. They show that synthesising a
useful social law is NP-complete. In (?), the problem of synthesising a social
law is recast as an ATL model checking problem. They show that the problem of
whether there exists a social law satisfying an objective expressed as an
arbitrary ATL formula (feasibility) is NP-complete, while for objectives
expressed as propositional formulae, feasibility (and synthesis) is decidable
in polynomial time. In contrast to the approach we present here, these and
related approaches (e.g., (?; ?; ?)) are used to synthesise norms at design
time, and assume a complete model the agents’ behaviour is available, e.g., in
the form of a transition system or a Kripke structure. Another strand of work
focusses on the ‘online’ synthesis of norms, where norms emerge from the
interactions of agents in a decentralised way, e.g., (?; ?). Unlike our
approach, such approaches typically assume that the agents are cooperative,
and/or that some minimal standards of behaviour can be assumed. Closer to our
work are approaches that use agents’ behaviour to guide (centralised) norm
synthesis. For example, (?) present algorithms for the online synthesis of
compact action-based norms when the behaviour of agents leads to undesired
system states. In contrast, we consider norms that regulate patterns of
behaviour. (?) and (?) apply Inductive Logic Programming to norm synthesis and
revision. They represent the system objective in terms of desired outcomes of
event traces. In contrast to our approach, traces encode use cases provided by
a human developer, and the system objectives are expressed in the same
language as norms.

##  2 Preliminaries

In this section we give formal definitions of the behaviour of agents in the
MAS and of conditional norms.

We assume a finite propositional language $L$ that contains propositions
corresponding to properties of states of the MAS. A _state_ of the MAS is a
propositional assignment. A conjunction of all literals (propositions or their
negations) in a state $s$ will be referred to as a _state description_ of $s$.
A propositional formula is a boolean combination of propositional variables.
The definition of a propositional formula $\phi$ being true in a state $s$ is
standard.

A _trace_ is a finite sequence of states. We use the notation
$(s_{1},\ldots,s_{k})$ for a trace consisting of states $s_{1},\ldots,s_{k}$.
We denote the $i$-th state in a trace $\rho$ by $\rho[i]$. We assume that the
behaviour exhibited by the agents in the MAS is represented by a set of finite
traces $\Gamma$. For example, a trace could be generated by the actions of all
vehicles involved in a traffic accident. We denote by $S(\Gamma)$ or simply by
$S$ the set of states occurring in traces in $\Gamma$. Each subset $X$ of
$S(\Gamma)$ is definable by a propositional formula $\phi_{X}$ (a disjunction
of state descriptions of states in $X$). Note that the size of $\phi_{X}$ is
linear in the size of $X$ (the sum of sizes of state descriptions of states in
$X$). $\Gamma$ is partitioned into two sets $\Gamma_{T}$ (positive traces) and
$\Gamma_{F}$ (negative traces). The partition is performed with respect to the
system objective, which typically does not correspond directly to the
properties expressible in $L$.

The problem we wish to solve is how to generate a conditional norm which is
expressed using propositions from $L$ that is obeyed on traces in $\Gamma_{T}$
and violated on traces in $\Gamma_{F}$.

######  Definition 1 (Conditional Norm).

A _conditional norm_ (over $L$) is a tuple $(\phi_{C},Z(\phi_{Z}),\phi_{D})$,
where $\phi_{C}$, $\phi_{Z}$ and $\phi_{D}$ are propositional formulas over
$L$, and $Z\in\\{P,O\\}$ indicates whether the norm is a prohibition ($P$) or
an obligation ($O$).

We refer to $\phi_{C}$ as the (detachment) condition of the norm, and
$\phi_{D}$ as the deadline. $\phi_{Z}$ characterizes a state that is
prohibited (resp. obligated) to occur after a state where the condition of the
norm $\phi_{C}$ holds, and before a state where the deadline of the norm
$\phi_{D}$ holds. We define the conditions for violation of norms formally
below.

######  Definition 2 (Violation of Prohibition).

A conditional prohibition $(\phi_{C},P(\phi_{P}),\phi_{D})$ is violated on a
trace $(s_{1},s_{2},\ldots,s_{m})$ if there are $i,j$ with $1\leq i\leq j\leq
m$ such that $\phi_{C}$ is true at $s_{i}$, $\phi_{P}$ is true at $s_{j}$, and
there is no $k$ with $i<k<j$ such that $\phi_{D}$ is true at $s_{k}$.

######  Definition 3 (Violation of Obligation).

A conditional obligation $(\phi_{C},O(\phi_{O}),\phi_{D})$ is violated on a
trace $(s_{1},s_{2},\ldots,s_{m})$ if there are $i,j$ with $1\leq i\leq j\leq
m$ such that $\phi_{C}$ is true at $s_{i}$, $\phi_{D}$ is true at $s_{m}$, and
there is no $k$ with $i\leq k\leq j$ such that $\phi_{O}$ is true at $s_{k}$.

A conditional norm is obeyed on a trace if it is not violated on that trace.
Violation conditions of conditional norms can be expressed in Linear Time
Temporal Logic (LTL) and evaluated on finite traces in linear time (?).

##  3 Complexity of Norm Synthesis

Given a set of agent behaviour traces $\Gamma$ partitioned into $\Gamma_{T}$
and $\Gamma_{F}$, we wish to synthesize a norm that correctly classifies each
trace (that is, the norm is violated on all traces in $\Gamma_{F}$, and is not
violated on any trace in $\Gamma_{T}$). Clearly, this is not always possible;
two sets of traces may not be distinguishable by a single conditional norm (or
even by a set of conditional norms). For example:

$\Gamma_{T}=\\{(s_{1},s_{2},s_{3})\\},\>\Gamma_{F}=\\{(s_{1},s_{1},s_{2},s_{3})\\}$

cannot be distinguished by a conditional norm.

###  3.1 Prohibition Synthesis

Next we define formally the decision problem we call _prohibition synthesis_.

######  Definition 4.

The _prohibition synthesis problem_ is the following decision problem:

Instance

A finite set of propositions $L$; a finite set of finite traces $\Gamma$
partitioned into $\Gamma_{T}$ and $\Gamma_{F}$, each trace given as a sequence
of state descriptions over $L$.

Question

Are there three propositional formulas $\phi_{C}$, $\phi_{P}$, and $\phi_{D}$
over $L$ such that

Neg

every trace in $\Gamma_{F}$ violates $(\phi_{C},P(\phi_{P}),\phi_{D})$

Pos

no trace in $\Gamma_{T}$ violates $(\phi_{C},P(\phi_{P}),\phi_{D})$

The correspondence between sets of states and formulas over $L$ allows us to
restate the prohibition synthesis problem as follows: given a set of positive
traces $\Gamma_{T}$ and negative traces $\Gamma_{F}$, find three sets of
states $X_{C}$, $X_{P}$, $X_{D}$ such that:

Neg

For every trace $\rho\in\Gamma_{F}$, exist $i$ and $j$ with $i\leq j$ such
that $\rho[i]\in X_{C}$, $\rho[j]\in X_{P}$, and there is no $k$ with $i<k<j$
such that $\rho[k]\in X_{D}$.

Pos

For every trace $\rho\in\Gamma_{T}$, if for some $i$ and $j$, $i\leq j$,
$\rho[i]\in X_{C}$, $\rho[j]\in X_{P}$, then there exists $k$ such that
$i<k<j$ and $\rho[k]\in X_{D}$.

######  Theorem 1.

The prohibition synthesis problem is NP-complete.

###### Proof.

The prohibition synthesis problem is clearly in NP (a non-deterministic Turing
machine can guess the sets and check in polynomial time that they satisfy the
conditions). To prove that it is NP-hard, we reduce 3SAT (satisfiability of a
set of clauses with 3 literals) to prohibition synthesis.

Suppose an instance of 3SAT (a set of clauses $C_{1},\ldots,C_{n}$ over
variables $x_{1},\ldots,x_{m}$) is given. We generate an instance of the
prohibition synthesis problem such that it has a solution iff
$C_{1},\ldots,C_{n}$ are satisfiable (each clause contains at least one true
literal). The set of states in the prohibition synthesis problem consists of
two states $s$ and $t$ which are a technical device (intuitively they serve as
the detachment condition and the violation of the prohibition), and for each
variable $x_{i}$, two states $u_{i}$ and $v_{i}$, intuitively meaning that
$x_{i}$ is true ($u_{i}$) or false ($v_{i}$). Below is the rest of the
construction. Comments in square brackets explain the intuition behind it.

The set of negative traces $\Gamma_{F}$ contains:

  * •

a two state trace $(s,t)$ [together with $s,t\not\in X_{C}\cap X_{P}$ below,
this forces $s\in X_{C}$ and $t\in X_{P}$];

  * •

for every variable $x_{i}$ in the input, a trace $(s,v_{i},t,s,u_{i},t)$ [this
ensures that either $v_{i}$ or $u_{i}$ are not in $X_{D}$].

The set of positive traces $\Gamma_{T}$ contains:

  * •

a single state trace $(s)$ [so $s$ cannot be in $X_{C}\cap X_{P}$];

  * •

$(t)$ [so $t$ cannot be in $X_{C}\cap X_{P}$];

  * •

for every variable $x_{i}$ in the input: $(s,v_{i},u_{i},t)$ [this means that
either $v_{i}$ or $u_{i}$ are in $X_{D}$]; $(v_{i})$; $(u_{i})$; $(v_{i},t)$;
$(u_{i},t)$; $(s,v_{i})$; $(s,u_{i})$;

  * •

for every pair of variables $x_{i}$, $x_{j}$ in the input: $(v_{i},u_{j})$;
$(u_{j},v_{i})$ [this together with preceding traces ensures that $v_{i}$ and
$u_{i}$ are not in $X_{C}$ or $X_{P}$];

  * •

for each clause $C$ in the input over variables $x_{j},x_{k},x_{l}$:
$(s,z_{j}$, $z_{k},z_{l},t)$ where $z_{i}$ is $u_{i}$ if $x_{i}$ occurs in $C$
positively, and $v_{i}$ if it occurs negatively.

The reduction is polynomial in the number of variables (quadratic) and clauses
(linear).

We claim that there exists an assignment $f$ of $0,1$ to $x_{1},\ldots,x_{m}$
satisfying $C_{1},\ldots,C_{n}$ if, and only if, there is a solution to the
prohibition synthesis problem above where $X_{C}=\\{s\\}$, $X_{P}=\\{t\\}$,
and for every $i$, $u_{i}\in X_{D}$ iff $f(x_{i})=1$ and $v_{i}\in X_{D}$ iff
$f(x_{i})=0$.

Assume an assignment $f$ satisfying $C_{1},\ldots,C_{n}$ exists. Let
$X_{C}=\\{s\\}$ and $X_{P}=\\{t\\}$. For every $i$, place $u_{i}$ in $X_{D}$
if $f(x_{i})=1$ and $v_{i}\in X_{d}$ iff $f(x_{i})=0$. This produces a
solution because: $s,t$ satisfies Neg; for every $i$, either $u_{i}$ or
$v_{i}$ are not in $X_{D}$, so $s,v_{i},t,s,u_{i},t$ satisfies Neg. Positive
traces satisfy Pos: either $s$ followed by $t$ does not occur on a trace, or
$u_{i}$, $v_{i}$ occur between $s$ and $t$ and one of them is in $X_{D}$, or
(from the clause encoding) one of the literals in the clause is true, so for
positive $x_{i}$ it means that $u_{i}$ is in $X_{D}$ and Pos is satisfied, or
for negative $\neg x_{i}$ it means that $v_{i}$ is in $X_{D}$ and again Pos is
satisfied.

Assume there is a solution to the prohibition synthesis problem. It is clear
(see the comments in square brackets above) that it has to be of the form
$X_{C}=\\{s\\}$, $X_{P}=\\{t\\}$ and $X_{D}$ containing some $u_{i}$s and
$v_{i}$s. In particular, since $(s,v_{i},u_{i},t)$ is a positive trace, for
every $i$ either $u_{i}$ or $v_{i}$ has to be not in $X_{D}$. Set $f(x_{i})$
to be 1 if $u_{i}$ in $X_{D}$ and 0 otherwise. Then each clause $C=\\{\sim
x_{j},\sim x_{k},\sim x_{l}\\}$ (where $\sim x_{j}$ denotes $x_{j}$ if it
occurs positively or $\neg x_{j}$ if it occurs negatively) is satisfied by $f$
since for every clause there will be one literal which is true. This is
because $(s,z_{j},z_{k},z_{l},t)$ is a positive trace, and either for some
positive literal $x_{i}$, $u_{i}$ is in $X_{D}$, or for some negative literal
$\neg x_{i}$, $v_{i}$ is in $X_{D}$, so $u_{i}$ is not in $X_{D}$, so $f(\neg
x_{i})=1$. ∎

###  3.2 Obligation Synthesis

We now consider the _obligation synthesis problem_.

######  Definition 5.

The _obligation synthesis problem_ is the following decision problem:

Instance

A finite set of propositions $L$, a finite set $\Gamma$ of finite traces
partitioned into $\Gamma_{T}$ and $\Gamma_{F}$, where each trace is given as a
sequence of state descriptions.

Question

Are there three propositional formulas $\phi_{C}$, $\phi_{O}$, and $\phi_{D}$
over $L$ such that

Neg

every trace in $\Gamma_{F}$ violates $(\phi_{C},O(\phi_{O}),\phi_{D})$

Pos

no trace in $\Gamma_{T}$ violates $(\phi_{C},O(\phi_{O}),\phi_{D})$

Analogously to the prohibition synthesis problem, the obligation synthesis
problem can be equivalently restated in terms of states: are there three sets
of states $X_{C}$, $X_{O}$ and $X_{D}$ such that:

Neg

For every trace $\rho\in\Gamma_{F}$, there exist $i$ and $j$ with $i\leq j$
such that $\rho[i]\in X_{C}$, $\rho[j]\in X_{D}$, and there is no $k$ with
$i\leq k\leq j$ such that $\rho[k]\in X_{O}$

Pos

For every trace $\rho\in\Gamma_{T}$, if for some $i$ and $j$, $i\leq j$,
$\rho[i]\in X_{C}$, $\rho[j]\in X_{D}$, then there exists $k$ such that $i\leq
k\leq j$ and $\rho[k]\in X_{O}$.

######  Theorem 2.

The obligation synthesis problem is NP-complete.

###### Proof.

The obligation synthesis problem is clearly in NP. To prove that it is NP-
hard, we again use a reduction from the 3SAT problem.

As before, consider a set of clauses $C_{1},\ldots,C_{n}$ over variables
$x_{1},\ldots,x_{m}$, which is an instance of 3SAT. We generate an instance of
the obligation synthesis problem such that it has a solution iff
$C_{1},\ldots,C_{n}$ are satisfiable. The idea of the reduction is similar to
that for prohibitions. We use two auxiliary states $s$ and $t$, intuitively to
serve as the detachment condition and the deadline, and make sure that neither
of them is also the obligation, but now instead of inserting a deadline
between $s$ and $t$ in positive traces, we insert an obligation. We want to
make some subset of $\\{v_{i}:i\in[1,...m]\\}\cup\\{u_{i}:i\in[1,...m]\\}$ to
be the obligation ($X_{O}$), so that exactly one of $v_{i}$, $u_{i}$ for each
$i$ is in $X_{O}$. Then $u_{i}\in X_{O}$ can encode that $x_{i}$ is true, and
$v_{i}\in X_{O}$ that $x_{i}$ is false, and we can make the encoding work by
creating a positive trace corresponding to each clause so that at least one of
the literals in the clause should be true.

The set of negative traces contains:

  * •

a 2 state trace $(s,t)$ [this forces either
$s\in X_{C}\cap\overline{X_{D}}\cap\overline{X_{O}}$, $t\in
X_{D}\cap\overline{X_{C}}\cap\overline{X_{O}}$, or
$s\in X_{C}\cap X_{D}\cap\overline{X_{O}}$, or
$t\in X_{C}\cap X_{D}\cap\overline{X_{O}}$.

To rule out the latter two possibilities, we require below that $s$ and $t$ on
their own are positive traces.]

  * •

for every variable $x_{i}$ in the input, a trace $(s,v_{i},t,s,u_{i},t)$ [this
ensures that either $v_{i}$ or $u_{i}$ are not in $X_{O}$, because there is
one $(s,..,t)$ sub-trace that does not contain a state from $X_{O}$].

The set of positive traces contains:

  * •

a one state trace $(s)$ [so $s$ cannot be in $X_{C}\cap
X_{D}\cap\overline{X_{O}}$]

  * •

a one state trace $(t)$ [so $t$ cannot be in $X_{C}\cap
X_{D}\cap\overline{X_{O}}$]

  * •

for every variable $x_{i}$ in the input, a trace $(s,v_{i},u_{i},t)$ [this
ensures that either $v_{i}$ or $u_{i}$ are in $X_{O}$]

  * •

for each clause $C$ in the input over variables $x_{j},x_{k},x_{l}$, a trace
$(s,z_{j},z_{k},z_{l},t)$ where $z_{i}$ is $u_{i}$ if $x_{i}$ occurs in $C$
positively, and $v_{i}$ if it occurs negatively.

The reduction is linear in the number of variables and clauses.

We claim that there exists an assignment $f$ of $0,1$ to $x_{1},\ldots,x_{m}$
satisfying $C_{1},\ldots,C_{n}$ if, and only if, there is a solution to the
obligation synthesis problem above where $s\in X_{C}$, $t\in X_{D}$, and for
every $i$, $u_{i}\in X_{O}$ iff $f(x_{i})=1$ and $v_{i}\in X_{O}$ iff
$f(x_{i})=0$. The proof of this claim is analogous to that of Theorem 1.

Assume an assignment $f$ satisfying $C_{1},\ldots,C_{n}$ exists. Let
$X_{C}=\\{s\\}$ and $X_{D}=\\{t\\}$. For every $i$, place $u_{i}$ in $X_{O}$
iff $f(x_{i})=1$ and $v_{i}\in X_{O}$ iff $f(x_{i})=0$. It is easy to check
that this is a solution to the obligation synthesis problem.

Assume there is a solution to the obligation synthesis problem. It is clear
(see the comments in brackets above) that any solution should satisfy $s\in
X_{C}\cap\overline{X_{D}}\cap\overline{X_{O}}$ and $t\in
X_{D}\cap\overline{X_{C}}\cap\overline{X_{O}}$. Since $(s,v_{i},t,s,u_{i},t)$
is a negative trace for every $i$, this means that it contains an unsatisfied
conditional obligation. This means that for every $i$, either $v_{i}$ or
$u_{i}$ is not in $X_{O}$. Since $(s,v_{i},u_{i},t)$ is a positive trace, then
in any solution, for every $i$, either $u_{i}$ or $v_{i}$ has to be in
$X_{O}$. Hence we can use the membership in $X_{O}$ to produce a boolean
valuation of variables $x_{i}$ (1 if $u_{i}\in X_{O}$, and 0 if $v_{i}\in
X_{O}$). Since for every clause $C=\\{\sim x_{j},\sim x_{k},\sim x_{l}\\}$,
the trace $(s,z_{j},z_{k},z_{l},t)$ (where $z_{i}$ is $v_{i}$ if $\sim
x_{i}=\neg x_{i}$, and $u_{i}$ if $\sim x_{i}=x_{i}$) is a positive trace, at
least one of $z_{i}$ is in $X_{O}$. This means that the valuation based on the
membership in $X_{O}$ satisfies all the clauses (since at least one literal in
each clause will evaluate to 1). ∎

From Theorems 1 and 2, it follows immediately that the problem of generating a
set of norms of size at most $m$ that correctly classifies a set of traces
$\Gamma$ (that is, no norm $N_{i}$ is violated on any trace in $\Gamma_{T}$,
and all traces in $\Gamma_{F}$ violates at least one norm $N_{j}$) is also NP-
complete.

##  4 Complexity of Minimal Revision

In this section, we consider the problem of (minimally) revising conditional
prohibitions (we omit the treatment of obligations, which is analogous). This
problem is often relevant when there is an existing norm that does not achieve
the system objective, and we wish a minimal modification of the existing norm
that does achieve the objective.

Assume we are given a set of traces and a conditional prohibition
$(\phi_{C},P(\phi_{P}),\phi_{D})$, and need to change it in a minimal way so
that it classifies the traces correctly. The editing distance between
conditional prohibitions can be defined in various ways, e.g., for formulas
$\phi_{C},\phi_{P},\phi_{D}$ in disjunctive normal form, this could be the sum
of the numbers of added and removed disjuncts for all three formulas. Note
that the set of non-equivalent propositional formulas built from the set $L$
is finite, and so is the number of possible different conditional prohibitions
(or obligations). Regardless of how the distance between different conditional
norms is defined, for a fixed set of propositional variables $L$ there is a
maximal editing distance $max(L)$ between any two norms using formulas over
$L$.

Given some distance measure $dist$ defined for any two conditional
prohibitions $\alpha_{1}$ and $\alpha_{2}$ over $L$, the decision problem for
minimal revision can be stated as:

######  Definition 6.

The (decision form) of the minimal prohibition revision problem is as follows:

Instance

A number $m$; a finite set of propositions $L$; a finite set $\Gamma$ of
finite traces partitioned into $\Gamma_{T}$ and $\Gamma_{F}$; a conditional
prohibition $(\phi_{C},P(\phi_{P}),\phi_{D})$ over $L$.

Question

Are there three propositional formulas $\phi^{\prime}_{C}$,
$\phi^{\prime}_{P}$, and $\phi_{D}^{\prime}$ over $L$ such that

Dist

$dist((\phi_{C},P(\phi_{P}),\phi_{D}),(\phi^{\prime}_{C},P(\phi^{\prime}_{P}),\phi^{\prime}_{D}))\leq
m$

Neg

every trace in $\Gamma_{F}$ violates
$(\phi^{\prime}_{C},P(\phi^{\prime}_{P}),\phi^{\prime}_{D})$

Pos

no trace in $\Gamma_{T}$ violates
$(\phi^{\prime}_{C},P(\phi^{\prime}_{P}),\phi^{\prime}_{D})$

######  Theorem 3.

Let $dist(\alpha_{1},\alpha_{2})$ be computable in time polynomial in the size
of $\alpha_{1}$ and $\alpha_{2}$, and the range of $dist$ over norms built
over propositions from $L$ be bounded by $max(L)$. Then the minimal
prohibition revision problem is NP-complete.

###### Proof.

The membership in NP follows from the fact that a solution can be guessed and
checked in polynomial time.

NP-hardness is by reduction from the prohibition synthesis problem. Note that
if a solution to the prohibition synthesis problem exists, it will be at most
at distance $max(L)$ from the input norm. So to solve the prohibition
synthesis problem, we can ask for a solution to the minimal prohibition
revision problem with $m=max(L)$. ∎

##  5 Conclusions

We considered the problem of synthesising and minimally revising norms to
achieve a system objective from labelled traces of agent behaviour. We showed
that the problems of norm synthesis and revision are NP-complete. In future
work, we plan to investigate the synthesis of approximate norms (i.e., norms
that do not classify all traces perfectly), and more tractable heuristic
approaches to norm synthesis and revision.

## References

  * Ågotnes et al. 2007 Ågotnes, T.; van der Hoek, W.; Rodríguez-Aguilar, J. A.; Sierra, C.; and Wooldridge, M. J.  2007\.  On the logic of normative systems.  In Veloso, M. M., ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), 1175–1180.
  * Airiau, Sen, and Villatoro 2014 Airiau, S.; Sen, S.; and Villatoro, D.  2014\.  Emergence of conventions through social learning.  Autonomous Agents and Multi-Agent Systems 28(5):779–804.
  * Alechina, Dastani, and Logan 2013 Alechina, N.; Dastani, M.; and Logan, B.  2013\.  Reasoning about normative update.  In Rossi, F., ed., Proceedings of the Twenty Third International Joint Conference on Artificial Intelligence (IJCAI 2013), 20–26.  Beijing, China: IJCAI.
  * Alechina, Dastani, and Logan 2014 Alechina, N.; Dastani, M.; and Logan, B.  2014\.  Norm approximation for imperfect monitors.  In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, Paris, France, May 5-9, 2014, 117–124.
  * Artikis and Pitt 2001 Artikis, A., and Pitt, J.  2001\.  A formal model of open agent societies.  In Proceedings of the Fifth International Conference on Autonomous Agents, AGENTS 2001, Montreal, Canada, May 28 - June 1, 2001, 192–193.
  * Athakravi et al. 2012 Athakravi, D.; Corapi, D.; Russo, A.; Vos, M. D.; Padget, J. A.; and Satoh, K.  2012\.  Handling change in normative specifications.  In International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), 1369–1370.
  * Boella and van der Torre 2004 Boella, G., and van der Torre, L. W. N.  2004\.  Regulative and constitutive norms in normative multiagent systems.  In Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004), Whistler, Canada, June 2-5, 2004, 255–266.
  * Chopra et al. 2018 Chopra, A.; van der Torre, L.; Verhagen, H.; and Villata, S., eds.  2018\.  Handbook of Multiagent Systems.  London: College Publications.
  * Corapi et al. 2011 Corapi, D.; Russo, A.; Vos, M. D.; Padget, J. A.; and Satoh, K.  2011\.  Normative design using inductive learning.  Theory Pract. Log. Program. 11(4-5):783–799.
  * Dell’Anna, Dastani, and Dalpiaz 2020 Dell’Anna, D.; Dastani, M.; and Dalpiaz, F.  2020\.  Runtime revision of sanctions in normative multi-agent systems.  Autonomous Agents and Multi-Agent Systems 34(2):1–54.
  * Fitoussi and Tennenholtz 2000 Fitoussi, D., and Tennenholtz, M.  2000\.  Choosing social laws for multi-agent systems: Minimality and simplicity.  Artificial Intelligence 119(1):61–101.
  * Morales et al. 2015 Morales, J.; Lopez-Sanchez, M.; Rodriguez-Aguilar, J. A.; Vasconcelos, W.; and Wooldridge, M.  2015\.  Online automated synthesis of compact normative systems.  ACM Transactions on Autonomous and Adaptive Systems (TAAS) 10(1):1–33.
  * Savarimuthu and Cranefield 2011 Savarimuthu, B. T. R., and Cranefield, S.  2011\.  Norm creation, spreading and emergence: A survey of simulation models of norms in multi-agent systems.  Multiagent and Grid Systems 7(1):21–54.
  * Shoham and Tennenholtz 1995 Shoham, Y., and Tennenholtz, M.  1995\.  On social laws for artificial agent societies: Off-line design.  Artificial intelligence 73(1-2):231–252.
  * Tinnemeier et al. 2009 Tinnemeier, N.; Dastani, M.; Meyer, J.-J.; and van der Torre, L.  2009\.  Programming normative artifacts with declarative obligations and prohibitions.  In Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT’09), 69–78.
  * van der Hoek, Roberts, and Wooldridge 2007 van der Hoek, W.; Roberts, M.; and Wooldridge, M. J.  2007\.  Social laws in alternating time: effectiveness, feasibility, and synthesis.  Synthese 156(1):1–19.
  * Wooldridge and van der Hoek 2005 Wooldridge, M., and van der Hoek, W.  2005\.  On obligations and normative ability: Towards a logical analysis of the social contract.  Journal of Applied Logic 3(3):396–420.