# Joint Trajectory Design and User Scheduling of Aerial Cognitive Radio
Networks††thanks: Manuscript received.

Hongjiang Lei, Haosi Yang, Ki-Hong Park, Imran Shafique Ansari,
Jing Jiang, and Mohamed-Slim Alouini

###### Abstract

Unmanned aerial vehicles (UAVs) have been widely employed to enhance the end-
to-end performance of wireless communications since the links between UAVs and
terrestrial nodes are line-of-sight (LoS) with high probability. However, the
broadcast characteristics of signal propagation in LoS links make it
vulnerable to being wiretapped by malicious eavesdroppers, which poses a
considerable challenge to the security of wireless communications. This paper
investigates the security of aerial cognitive radio networks (CRNs). An
airborne base station transmits confidential messages to secondary users
utilizing the same spectrum as the primary network. An aerial base station
transmits jamming signals to suppress the eavesdropper to enhance secrecy
performance. The uncertainty of eavesdropping node locations is considered,
and the average secrecy rate of the cognitive user is maximized by optimizing
multiple users’ scheduling, the UAVs’ trajectory, and transmit power. To solve
the non-convex optimization problem with mixed multiple integers variable
problem, we propose an iterative algorithm based on block coordinate descent
and successive convex approximation. Numerical results verify the
effectiveness of our proposed algorithm and demonstrate that our scheme is
beneficial to improving the secrecy performance of aerial CRNs.

###### Index Terms:

Cognitive radio networks, cooperative jamming, physical layer security,
trajectory design, unmanned aerial vehicle.

##  I Introduction

###  I-A Background and Related Works

Because of high maneuverability, low cost, and flexibility for on-demand
deployment, low-altitude unmanned aerial vehicles (UAVs) are extensively
utilized in diverse fields for different applications and purposes, such as
real-time surveillance, traffic control, and communication relays because of
high maneuverability, low cost, and flexibility for on-demand deployment,
policing, and inspection, etc. Among all these application scenarios, UAV
communication is an up-and-coming technology that will become an essential
part of future mobile communication systems [1, 2]. Expressly, by adjusting
the position or designing the trajectory of UAVs, a reliable line-of-sight
link (LoS) can be provided to the terrestrial nodes (TNs) with high
possibility. Therefore, the altitude and the horizontal location of UAVs have
a decisive effect on the performance of UAV communication systems. Trajectory
design has become a critical issue to resolve in UAV communication system
design [3].

The most typical scenario of UAV-assisted wireless communications is providing
ubiquitous wireless coverage within the serving area for a given geographical
area [4], [5]. A communication system with multiple aerial base stations (BSs)
was investigated in [6] in which UAV trajectories were optimized to maximize
the minimum throughput concerning user scheduling coefficients and
transmitting power on UAVs. The authors proposed an effective iterative
algorithm based on the successive convex approximation (SCA) and the block
coordinate descent (BCD) to solve the mixed-integer non-convex optimization
problem. The results demonstrated that UAV communication systems could enhance
the system utility with additional flexibility for interference mitigation.
Considering a finite amount of energy and a certain quality of service
requirement, the max-min fairness problem was studied in [7]. When UAVs are
utilized to be relay nodes, long-distance wireless links between terrestrial
BSs and TNs can be quickly established, which is of great use in disaster or
other emergency scenarios [4]. In [8], the authors considered a UAV-assisted
cooperative system in which multiple UAVs were utilized as decode-and-forward
relays to forward signals to the TNs. The minimum transmission rate of the
system was maximized by jointly optimizing the flight trajectory of the relay
UAVs, the transmitting power on UAVs, and terrestrial BS. An iterative
algorithm was proposed to solve the joint optimization problem based on the
block coordinate ascent technique, introducing the slack variable and SCA
techniques. In [9], an aerial relay balanced the difference in transmission
rates between free space optical and radio frequency links, and the throughput
for delay-limited and delay-tolerant scenarios was maximized by carefully
designing the flight trajectory of the aerial relay, which in turn maximized
the throughput. In UAV-aided wireless sensor networks and the IoT
communication systems, UAVs are utilized as aerial access points to
disseminate/collect information to/from TNs [4], [5]. A mixed-integer non-
convex optimization problem was proposed to prolong the wireless sensor
network lifetime and the UAV’s trajectory were jointly optimized to minimize
the maximum energy consumption of all sensor nodes in [10]. An efficient
iterative algorithm was proposed to obtain a sub-optimal solution by applying
the SCA technique. In [11], two UAVs were utilized to provide energy for two
TNs and collect information from the two TNs alternately. A resource and
trajectory optimization scheme was proposed to maximize the minimum throughput
of TNs by joint optimization of UAVs’ trajectories, time allocation, and TNs’
transmit power. The minimum data collection rate was maximized by jointly
optimizing the 3D trajectory of UAVs and time allocation in [12]. The minimum
distances between UAVs were considered to avoid a collision and an efficient
iterative algorithm was proposed to solve the non-convex optimization problem.

Information security is one of the fundamental requirements for wireless
communication systems. High possibilities of LoS air-to-ground (A2G)
communication links make UAV-assisted wireless communication systems more
vulnerable and more prone to be eavesdropped by malicious nodes [13, 14, 15].
In [16], the secrecy performance of a UAV-aided wireless communication system
with multiple TNs was investigated and the minimum secrecy rate was maximized
by jointly optimizing aerial BS’s trajectory, the transmit power, and the
users association. An iterative algorithm was proposed by the SCA technique
and the alternating method, and their results showed that the secrecy rate was
improved. Because of LoS links with a weak path loss and high maneuverability,
UAVs can be utilized as aerial jammers to suppress the eavesdroppers [17, 18,
19]. In [17], the physical layer security issues of a dual-UAV communication
system with multiple TNs were investigated, and the minimum secrecy rate was
maximized by jointly optimizing the trajectories and the transmit powers of
both UAVs as well as the user scheduling. However, the location of the
eavesdropper is assumed to be available to the base station in [16] and [17].
In [18], the secrecy performance of a wireless system with one aerial BS and
one cooperative aerial friendly jammer was investigated, and the average
secrecy rate was maximized by jointly optimizing UAVs’ trajectory and the
transmit power. The location of the TN was assumed to be perfectly known while
the location of the eavesdropper was assumed to be partially known for both
UAVs. An iterative algorithm was proposed to solve the optimization problem
using the alternating optimization and SCA techniques. In comparison, Zhang
_et al._ investigated a dual-UAV communication system with multiple TNs in
[19]. Both the average secrecy rate and the secrecy energy efficiency were
maximized by jointly optimizing the user scheduling, the transmit power, the
trajectory, and the velocity of the two UAVs.

Although UAV-enabled cognitive radio networks (CRNs) can improve spectrum
efficiency compared to traditional wireless communication networks, how to
effectively mitigate the interference from A2G co-channel to the primary links
is an important and challenging problem [20, 21]. A UAV-enabled CRN with one
cognitive user (CU), multiple eavesdroppers, and multiple primary users (PUs)
was considered in [22] and the average secrecy rate of the CU in the worst-
case scenario was maximized by optimizing the aerial BS’s trajectory and
transmit power. The location of PUs and eavesdroppers is assumed to be
inaccurate and iterative algorithms based on bounded and probabilistic
location error models were proposed to obtain a suboptimal solution. Wang _et
al._ considered the secrecy performance of a CRN with multiple terrestrial CUs
and PUs, and a terrestrial eavesdropper in [23]. An aerial-friendly jammer was
utilized to enhance security. The total average secrecy rate of the CU was
maximized by jointly optimizing the sub-carrier allocation, the trajectory,
and the transmission power of the aerial jammer and the power of the cognitive
BS. In [24], the authors investigated the secrecy performance of a CRN with a
terrestrial CU, a PU, an eavesdropper, and a friendly jammer. Two scenarios
were considered in which all the location of ground nodes (including the CU,
PU, and eavesdropper) was assumed to be known and unknown, respectively. The
average achievable secrecy rate of the CU was maximized by jointly optimizing
the transmit power and three-dimensional (3D) trajectory of the aerial jammer.

###  I-B Motivation and Contributions

The combination of physical layer security technology and cognitive wireless
networks on UAV platforms exploits the advantages of high mobility, security,
flexibility, low cost, and on-demand distribution of UAVs. It efficiently
utilizes limited spectrum resources, guaranteeing high-quality transmission
during wireless communication. Motivated by this practical significance, in
this work, we investigate the dual collaborative UAV security scheduling for
multi-user transmission under the uncertainty of potential eavesdropping node
locations in a CRN. The main contributions of this paper are summarized as
follows:

  1. 1.

We propose a dual collaborative UAV system for physical layer security in a
multi-user scheduling scenario under the uncertainty of potential
eavesdropping node locations in CRNs. A legitimate UAV operates as an airborne
base station and transmits confidential messages to secondary users utilizing
the same spectrum licensed to the primary network. A friendly jamming UAV
disrupts eavesdropping by transmitting artificial noise. Meanwhile, a
malicious eavesdropping node at an uncertain location tries to wiretap the
confidential information. In this dual-UAV network, the average secrecy rate
is maximized by jointly optimizing the user scheduling, the transmit power of
UAVs, and the trajectory of the UAVs.

  2. 2.

The average sum secrecy rate is formulated by jointly optimizing the
scheduling, the transmit power, and the trajectory of the two UAVs subject to
the limited power constraints, the maximum flying speed, initial and final
position restrictions of UAVs, and threshold for the regular operation of the
primary network. Due to the non-convexity, the challenging optimization
problem is divided into several subproblems while transformed into
approximated convex forms via the SCA. Subsequently, the BCD technology is
employed to address these subproblems successively.

  3. 3.

We compare the proposed algorithm with other benchmark strategies, which only
consider the fixed trajectory and transmit power of UAVs while considering
only the case of optimizing individual UAV trajectory and transmit power. The
simulation results verify the efficiency and the convergence of the proposed
algorithm.

###  I-C Organization

The rest of this paper is organized as follows. The system model and problem
formulation are provided in Section II. Section III presents a proposed
iterative algorithm for the case of friendly jammer drones to solve the same.
Simulation results are demonstrated in Section IV. Finally, Section V
concludes this paper.

##  II System Model and Problem Formulation

###  II-A System Model

Figure 1: Dual-UAV enabled secure communication system in CRN.

As shown in Fig. 1, we consider an underlay CRN with an airborne base station
(${S}$) transmitting confidential messages to CUs utilizing the same spectrum
licensed to the primary network. A malicious terrestrial eavesdropper ($E$) at
uncertain location is trying to wiretap the confidential information. A jammer
UAV (${J}$) sends jamming signals to suppress the eavesdropping capabilities
of $E$. It is assumed that there are $R$ PUs (${U_{r}},r=1,\cdots,R$) and $K$
CUs (${D_{k}},k=1,\cdots,K$) where all devices are equipped with a single
antenna. Similar to [18], ${S}$ and ${J}$ have only partial information about
$E$ due to the uncertainty of its location. A three-dimensional Cartesian
coordinate is utilized where ${S}$ and ${J}$ fly at a fixed altitude ${H_{1}}$
and ${H_{2}}$, respectively. The flight period of two UAVs, ${T}$, is divided
into ${N}$ time slots as ${\delta_{t}}=\frac{T}{N}$. When ${\delta_{t}}$ is
small enough, the position of UAVs at each point can be approximated as a
constant [6]. The horizontal positions of ${S}$ and ${J}$ at the $n$th slot
are expressed as
${{\mathbf{q}}_{S}}\left(n\right)={\left[{{x_{S}}\left(n\right),{y_{S}}\left(n\right)}\right]^{T}}$
and
${{\mathbf{q}}_{J}}\left(n\right)={\left[{{x_{J}}\left(n\right),{y_{J}}\left(n\right)}\right]^{T}}$,
respectively. In addition, ${{\bf{w}}_{{D_{k}}}}\in{\mathbb{R}^{2\times 1}}$,
${{\bf{w}}_{{U_{r}}}}\in{\mathbb{R}^{2\times 1}}$, and
${{\mathbf{w}}_{E}}\in{\mathbb{R}^{2\times 1}}$ denote the location
coordinates of ${D_{k}}$, ${U_{r}}$, and $E$. Similar to [19] and [23], all
the A2G links are assumed to be LoS links. For simplicity, it is assumed that
the A2G links are dominated by the LoS links, where the channel quality
depends only on Euclidean distance. Furthermore, the Doppler effect is also
assumed to be well compensated by the receivers. The channel coefficients
between $S$ and all the receivers ($D_{k}$, $U_{r}$, and $E$) at the $n$th
slot are expressed as

$\displaystyle{h_{S{D_{k}}}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{1}^{2}}},$
(1a) $\displaystyle{h_{S{U_{r}}}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|}^{2}}+H_{1}^{2}}},$
(1b) $\displaystyle{h_{SE}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\mathbf{w}}_{E}}}\right\|}^{2}}+H_{1}^{2}}},$
(1c)

where $\rho_{0}$ denotes the channel power gain at the reference distance.
Similarly, the channel coefficients between $J$ and all the receivers at the
$n$th slot are expressed as

$\displaystyle{h_{J{D_{k}}}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{2}^{2}}},$
(2a) $\displaystyle{h_{J{U_{r}}}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|}^{2}}+H_{2}^{2}}},$
(2b) $\displaystyle{h_{{JE}}}\left(n\right)$
$\displaystyle=\frac{{{\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{\mathbf{w}}_{E}}}\right\|}^{2}}+H_{2}^{2}}}.$
(2c)

Since the exact location of $E$ is not available for ${S}$ and ${J}$,
${{h_{SE}}}$ and ${{h_{JE}}}$ in (1c) and (2c) are inaccurate,
${{\mathbf{\hat{w}}}_{E}}\in{\mathbb{R}^{2\times 1}}$ and ${r_{E}}$ are
utilized to indicate the circle center and radius of the area wherein $E$ is
located. It is assumed that ${r_{E}}$ is smaller than the distance between $S$
and $E$, i.e.
$\left\|{{{\bf{q}}_{S}}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right\|\geq{r_{E}}$.
According to the triangle inequality, the distance between ${S}$ and $E$ is
expressed as

$\displaystyle\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\mathbf{w}}_{E}}}\right\|$
$\displaystyle\geqslant\left|{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|-\left\|{{{{\mathbf{\hat{w}}}}_{E}}-{{\mathbf{w}}_{E}}}\right\|}\right|$
(3)
$\displaystyle\geqslant\left|{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|-{r_{E}}}\right|.$

When ${r_{E}}=0$, it indicates that the base station is fully able to obtain
the location information of $E$. At this point, the whole problem degenerates
into the physical layer security problem of the UAV trajectory design based on
the perfect eavesdropping position considered in [16].

Similarly, the distance between ${J}$ and $E$ is expressed by the upper and
lower bounds, respectively, as follows.

$\displaystyle\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{\mathbf{w}}_{E}}}\right\|$
$\displaystyle\leqslant\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+\left\|{{{{\mathbf{\hat{w}}}}_{E}}-{{\mathbf{w}}_{E}}}\right\|\hfill$
(4)
$\displaystyle\leqslant\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}.$

Then ${{h_{SE}}}$ and ${{h_{JE}}}$ is rewritten as

${h_{SE}}\left(n\right)=\frac{{{\rho_{0}}}}{{{{\left({\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|-{r_{E}}}\right)}^{2}}+H_{1}^{2}}}$
(5)

and

${h_{{JE}}}\left(n\right)=\frac{{{\rho_{0}}}}{{{{\left({\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)}^{2}}+H_{2}^{2}}},$
(6)

respectively.

To enable all the CUs to be served fairly in one period, a binary variable
${\theta_{k}}\left(n\right)$ is utilized to characterize user scheduling in
the considered CRN [25]. More specifically, ${\theta_{k}}\left(n\right)=1$
signifies that only $D_{k}$ is scheduled to communicate with ${S}$ at the
${n}$th slot. Thus, we have

$\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right)}\leq 1,\forall n,$ (7)
${\theta_{k}}\left(n\right)\in\left\\{{0,\left.1\right\\}}\right.,\forall
n,k.$ (8)

It is assumed that ${S}$ for the $k$th user and ${J}$ transmit signals at the
${n}$th slot with power ${P_{k}}\left(n\right)$ and ${{P_{J}}\left(n\right)}$,
respectively. The average interference power constraint for $U_{r}$ is given
as [23]

$\frac{1}{N}\sum\limits_{n=1}^{N}{\left\\{{{P_{J}}\left(n\right){h_{J}}_{{U_{r}}}\left(n\right)+\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){P_{k}}\left(n\right){h_{S}}_{{U_{r}}}\left(n\right)}}\right\\}}\leqslant{\Gamma_{r}},$
(9)

where ${\Gamma_{r}}$ denotes a constant threshold value of the ${U_{r}}$ that
can tolerate the maximum average interference power.

In this work, it is assumed that the jamming signals transmitted by $J$ can be
a Gaussian pseudo-random sequence or the same utilizes deterministic waveforms
similar to the structure of the desired signal as [26], [27, 28]. Then the
jamming signals sent by ${J}$ can be cancelled by the received signal at all
the secondary receivers, the signal-to-noise ratio (SNR) for ${D_{k}}$ is
expressed as

${\gamma_{D_{k}}}=\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}},$
(10)

where ${{\sigma^{2}}}$ denotes the variance of additive white Gaussian noise
(AWGN). The achievable rate ${R_{S{D_{k}}}}\left(n\right)$ is expressed as

${R_{S{D_{k}}}}\left(n\right)={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right).$
(11)

Similarly, the signal-to-interference-plus-noise ratio (SINR) and achievable
rate at $E$ are expressed as

${\gamma_{E}}=\frac{{{P_{k}}\left(n\right){h_{SE}}}}{{{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}}$
(12)

and

${R_{E}}\left(n\right)={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{SE}}}}{{{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}}}\right),$
(13)

respectively. Then the secrecy rate at ${D_{k}}$ is expressed as

${R_{\sec}^{k}}\left(n\right)={\left[{{{\log}_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)-{{\log}_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{SE}}}}{{{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}}}\right)}\right]^{+}},$
(14)

where ${\left[x\right]^{+}}\triangleq\max\left({x,0}\right)$.

###  II-B Problem Formulation

In this work, the sum average secrecy rate is maximized with respect to UAV
trajectory, the transmit power, and the user scheduling. Let
${{\mathbf{\Theta}}}=\left\\{{{\theta_{k}}\left(n\right),\forall
k,n}\right\\}$,
${\mathbf{P}}=\left\\{{{P_{k}}\left(n\right),{P_{J}}\left(n\right),\forall
k,n}\right\\}$, and
${\mathbf{Q}}=\left\\{{{{\mathbf{q}}_{S}}\left(n\right),{{\mathbf{q}}_{J}}\left(n\right),\forall
n}\right\\}$. Therefore, we formulate the following optimization problem.

$\displaystyle\mathcal{P}_{1}\,:\,\max\limits_{{{\mathbf{\Theta}},{\mathbf{P}},{\mathbf{Q}}}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){{R_{\sec}^{k}}}\left(n\right)}},$
(15a) $\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right)}\leq 1,\forall
n,$ (15b)
$\displaystyle{\theta_{k}}\left(n\right)\in\left\\{{0,\left.1\right\\}}\right.,\forall
n,k,$ (15c)
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right)}R_{\sec}^{k}\left(n\right)\geq{R_{\min}},$
(15d) $\displaystyle 0\leq{P_{k}}\left(n\right)\leq{P_{S}^{max}},\forall k,n,$
(15e) $\displaystyle
0\leq{\frac{1}{N}\sum\limits_{n=1}^{N}{\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){P_{k}}\left(n\right)\leq}}P_{S}^{ave}},\forall
k,n,$ (15f) $\displaystyle
0\leq{P_{J}}\left(n\right)\leq{P_{J}^{max}},{\rm{for}}\;\forall n,$ (15g)
$\displaystyle{\frac{1}{N}\sum\limits_{n=1}^{N}{{P_{J}}\left(n\right)}\leq{P_{J}^{ave}}},$
(15h)
$\displaystyle{{\mathbf{q}}_{i}}\left(1\right)={\mathbf{q}}_{i}^{0},{{\mathbf{q}}_{i}}\left(N\right)={\mathbf{q}}_{i}^{\textrm{F}},\forall
i\in\left\\{{S,J}\right\\},$ (15i)
$\displaystyle\left\|{{{\mathbf{q}}_{i}}\left({n+1}\right)-{{\mathbf{q}}_{i}}\left(n\right)}\right\|\leq{\delta_{t}}{V_{i,max}},\forall
i\in\left\\{{S,J}\right\\},n\in N,$ (15j)
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{\left\\{{{P_{J}}\left(n\right){h_{J}}_{{U_{r}}}\left(n\right)+\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){P_{k}}\left(n\right){h_{S}}_{{U_{r}}}\left(n\right)}}\right\\}}\leq{\Gamma_{r}},\forall
r,$ (15k)

where $P_{S}^{max}$ and $P_{J}^{max}$ denote the peak transmit power of UAVs,
$P_{S}^{ave}$ represents the average power of $S$ scheduling ${D_{k}}$, and
$P_{J}^{ave}$ denote the average transmission power of $J$, and
${\mathbf{q}}_{i}^{0}$ and ${\mathbf{q}}_{i}^{\textrm{F}}$ are the initial and
final positions of the UAVs, respectively. Eqs. (15b) and (15c) are the
scheduling constrains of ground users, respectively, (15d) is the constraint
that all users are scheduled fairly, where ${R_{\min}}$ is the minimum average
security rate, (15e) - (15h) are the peak and average power constraints of
transmitting and jamming signals in each time slot, respectively, (15i)
denotes the constraints on the initial and final positions of the UAVs, (15j)
depicts the maximum flight distance between adjacent time slots during the
flight, and (15k) considers the underlay condition.

Several factors make the original problem $\mathcal{P}_{1}$ challenging to
solve. First, the operator ${\left[x\right]^{+}}$ makes the objective function
non-smooth at zero value, and the optimization variable ${{\mathbf{\Theta}}}$
is binary and thus (15b) and (15c) involve integer constraints. Second, even
with fixed user scheduling, $\mathcal{P}_{1}$ is still non-convex concerning
transmitting power variable ${\mathbf{P}}$ and UAV trajectory variable
${\mathbf{Q}}$. Therefore, $\mathcal{P}_{1}$ is a mixed-integer non-convex
problem, which is challenging to optimally solve in general.

##  III Proposed Algorithm On Dual Collaborative UAVs

According to the method used in [18] and [23], we can remove the operator
${\left[x\right]^{+}}$. Meanwhile, to solve $\mathcal{P}_{1}$, alternating
optimization method is utilized to optimize the scheduling variable
${{\mathbf{\Theta}}}$, transmit power allocation ${{\mathbf{P}}}$, and
trajectory of UAV ${{\mathbf{Q}}}$ in an alternating manner, by considering
the others to be given.

###  III-A Subproblem 1.1: User Scheduling Optimization

In this subsection, the scheduling variable ${\mathbf{\Theta}}$ with given
$\left\\{{{\mathbf{P}},{\mathbf{Q}}}\right\\}$ is optimized firstly. The
binary variable ${\theta_{k}}\left(n\right)$ is relaxed into continuous
variables between 0 and 1 to restrain the binary constraint (15c). Then
$\mathcal{P}_{1}$ is reduced as

$\displaystyle\mathcal{P}_{1.1}\,:\,\max\limits_{{\mathbf{\Theta}},{\eta_{k}}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{\eta_{k}}$ (16a)
$\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right){R_{\sec}^{k}}\left(n\right)}\geqslant{\eta_{k}},$
(16b) $\displaystyle{\eta_{k}}\geq{R_{\min}},$ (16c) $\displaystyle
0\leqslant{\theta_{k}}\left(n\right)\leqslant 1,$ (16d)
$\displaystyle(\textrm{\ref{eq:C1}}),(\textrm{\ref{eq:C4}}),(\textrm{\ref{eq:C9}}),$
(16e)

where

${{R_{\sec}^{k}}}\left(n\right)={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)-{\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{SE}}}}{{{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}}}\right).$
(17)

$\mathcal{P}_{1.1}$ is a standard linear programming (LP), which can be solved
by existing optimization tools such as CVX.

###  III-B Subproblem 1.2: Transmit Power Optimization

For any given user scheduling as well as the trajectory of ${S}$ and ${J}$,
the optimization problem of transmit power is expressed as

$\displaystyle\mathcal{P}_{1.2}\,:\,\max\limits_{{\mathbf{P}},{\eta_{k}}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{\eta_{k}}\hfill$ (18a)
$\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right){{R_{\sec}^{k}}}\left(n\right)}\geqslant{\eta_{k}},$
(18b) $\displaystyle{\eta_{k}}\geq{R_{\min}},$ (18c)
$\displaystyle(\textrm{\ref{eq:C3}})-(\textrm{\ref{eq:C6}}),(\textrm{\ref{eq:C9}}).$
(18d)

where ${{R}_{\sec}^{k}}\left(n\right)$ is rewritten by

$\displaystyle{{R}_{\sec}^{k}}\left(n\right)$
$\displaystyle={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)-{\log_{2}}\left({{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}+{P_{k}}\left(n\right){h_{SE}}}\right)$
(19)
$\displaystyle+{\log_{2}}\left({{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}\right).$

It must be noted that (18b) is a non-convex constraint due to the second term
in (19) which is a convex function with respect to ${\mathbf{P}}$. To tackle
the non-convex constraint, the first-order Taylor expansion is utilized to
transform ${{R}_{\sec}^{k}}\left(n\right)$ into

$\displaystyle{R}_{\sec}^{k,\textrm{lb}}\left(n\right)$
$\displaystyle={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)+{\log_{2}}\left({{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}\right)$
(20)
$\displaystyle-{\log_{2}}\left({P_{J}^{m}\left(n\right){h_{JE}}+{\sigma^{2}}+P_{k}^{m}\left(n\right){h_{SE}}}\right)$
$\displaystyle-\frac{{{h_{JE}}\left({{P_{J}}\left(n\right)-P_{J}^{m}\left(n\right)}\right)+{h_{SE}}\left({{P_{k}}\left(n\right)-P_{k}^{m}\left(n\right)}\right)}}{{\ln(2)\left({{P_{J}}^{m}\left(n\right){h_{JE}}+{\sigma^{2}}+{P_{k}}^{m}\left(n\right){h_{SE}}}\right)}},$

where $\left\\{{P_{J}^{m}\left(n\right),P_{k}^{m}\left(n\right),\forall
n}\right\\}$ is a given feasible point in the ${m}$th iteration and the
subscript ‘lb’ denotes lower bound. For a given feasible point
$\left\\{{P_{J}^{m}\left(n\right),P_{k}^{m}\left(n\right),\forall
n}\right\\}$, ${R}_{\sec}^{k,\textrm{lb}}\left(n\right)$ is a convex function
with respect to the optimization variables ${{P_{k}}\left(n\right)}$ and
${{P_{J}}\left(n\right)}$.

By replacing ${{{R}_{\sec}^{k}}\left(n\right)}$ with
${R}_{\sec}^{k,\textrm{lb}}\left(n\right)$, $\mathcal{P}_{1.2}$ is
approximated as a convex optimization problem that can thus be solved by
standard convex optimization techniques such as CVX.

###  III-C Subproblem 1.3: Optimizing Trajectory of $S$

In this section, we aim at optimizing the trajectory of ${S}$ with given
$\left\\{{{\mathbf{\Theta}},{\mathbf{P}}}\right\\}$. $\mathcal{P}_{1}$ is
approximated as

$\displaystyle\mathcal{P}_{1.3}\,:\,\max\limits_{{{\mathbf{q}}_{S}},{\eta_{k}}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{\eta_{k}}$ (21a)
$\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right)}{R_{\sec,1}^{k}}\left(n\right)\geq{\eta_{k}},$
(21b) $\displaystyle{\eta_{k}}\geq{R_{\min}},$ (21c)
$\displaystyle(\textrm{\ref{eq:C7}})-(\textrm{\ref{eq:C9}}),$ (21d)

where
${R_{\sec,1}^{k}}\left(n\right)={\log_{2}}\left({1+\frac{{c\left(n\right){\rho_{0}}}}{{{{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{1}^{2}}}}\right)-{\log_{2}}\left({1+\frac{{t\left(n\right){\rho_{0}}}}{{{{\left({\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|-{r_{E}}}\right)}^{2}}+H_{2}^{2}}}}\right)$,
$c\left(n\right)=\frac{{{P_{k}}\left(n\right)}}{{{\sigma^{2}}}}$, and
$t\left(n\right)=\frac{{{P_{k}}\left(n\right)}}{{{P_{J}}\left(n\right){h_{JE}}+{\sigma^{2}}}}$.
It must be noted that $\mathcal{P}_{1.3}$ is a non-convex problem since the
function in ${R_{\sec,1}}\left(n\right)$ is a non-concave function with
respect to ${{{\mathbf{q}}_{S}}\left(n\right)}$ and (15k) is a non-convex
constraint. By introducing the slack variables and applying the successive
convex approximation (SCA), $\mathcal{P}_{1.3}$ is written as

$\displaystyle\mathcal{P}_{1.3}\,:\,\max\limits_{{{\mathbf{q}}_{S}},{\eta_{k}},{d_{SE}},{d_{S{U_{r}}}}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{\eta_{k}}$ (22a)
$\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right)}\left({{{\hat{R}}_{S{D_{k}}}}\left(n\right)-{{\log}_{2}}\left({1+\frac{{t\left(n\right){\rho_{0}}}}{{{d_{SE}}+H_{2}^{2}}}}\right)}\right)\geq{\eta_{k}},$
(22b) $\displaystyle{\eta_{k}}\geq{R_{\min}},$ (22c)
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{\left\\{{{P_{J}}\left(n\right){h_{J{U_{r}}}}\left(n\right)+\frac{{\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){P_{k}}\left(n\right)}{\rho_{0}}}}{{{d_{S{U_{r}}}}+H_{1}^{2}}}}\right\\}}\leq{\Gamma_{r}},\forall
r,$ (22d)
$\displaystyle{d_{SE}}\leq{\left({\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|-{r_{E}}}\right)^{2}},$
(22e)
$\displaystyle{d_{S{U_{r}}}}\leq{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|^{2}},\forall
r,$ (22f) $\displaystyle(\textrm{\ref{eq:C7}}),(\textrm{\ref{eq:C8}}),$ (22g)

where

${\hat{R}_{S{D_{k}}}}\left(n\right)\geq{L^{m}}\left(n\right)\left({{{\left\|{{{\mathbf{q}}_{S}}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}-{{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}}\right)+{D^{m}}\left(n\right),\\\
$ (23)
${D^{m}}\left(n\right)={\log_{2}}\left({1+\frac{{c\left(n\right){\rho_{0}}}}{{{{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{1}^{2}}}}\right),\\\
$ (24)
${L^{m}}\left(n\right)=-\frac{{c\left(n\right){\rho_{0}}}}{{\ln(2)\left({{{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{1}^{2}+c\left(n\right){\rho_{0}}}\right)\left({{{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{D_{k}}}}}\right\|}^{2}}+H_{1}^{2}}\right)}}.$
(25)

It must be noted that (22e) and (22f) are non-convex functions since right-
hand-side of them are convex function. By applying SCA, the following convex
constraints are utilized

$\displaystyle{d_{SE}}$ $\displaystyle\leq
2{\left({{\mathbf{q}}_{S}^{m}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right)^{T}}\left({{{\mathbf{q}}_{S}}\left(n\right)-{\mathbf{q}}_{S}^{m}\left(n\right)}\right)$
(26)
$\displaystyle\;\;\;\;\;{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|^{2}}-2{r_{E}}\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}^{2},$
${d_{S{U_{r}}}}\leq{\left\|{{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|^{2}}+2{\left({{\mathbf{q}}_{S}^{m}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right)^{T}}\left({{{\mathbf{q}}_{S}}\left(n\right)-{\mathbf{q}}_{S}^{m}\left(n\right)}\right).$
(27)

By replacing (22e) and (22f) with (26) and (27), respectively,
$\mathcal{P}_{1.3}$ is reformulated as

$\displaystyle\mathcal{P}_{1.3}\,:\,\max\limits_{{{\mathbf{q}}_{S}},{\eta_{k}},{d_{SE}},{{d_{S{U_{r}}}}}}$
$\displaystyle\sum\limits_{k=1}^{K}{\eta_{k}}$ (28)
$\displaystyle{\mathrm{s.t.}}$
$\displaystyle(\textrm{\ref{eq:p1.3b}}),(\textrm{\ref{eq:p1.3g}}),(\textrm{\ref{eq:p1.3c}}),(\textrm{\ref{ddSE}}),(\textrm{\ref{dSUr}}),(\textrm{\ref{eq:p1.3f}}).$

Now $\mathcal{P}_{1.3}$ is a convex problem and can be solved by existing
optimization tools such as CVX.

###  III-D Subproblem 1.4: Optimizing Trajectory of $J$

Finally, we optimize ${{{\mathbf{q}}_{J}}\left(n\right)}$ with other variables
fixed. Similarly, $\mathcal{P}_{1}$ is approximated as

$\displaystyle\mathcal{P}_{1.4}\,:\,\max\limits_{{{\mathbf{q}}_{J}},{\eta_{k}},{d_{J{U_{r}}}},{d_{JE}}}\;$
$\displaystyle\sum\limits_{k=1}^{K}{{{\eta_{k}}}}$ (29a)
$\displaystyle{\mathrm{s.t.}}\;$
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{{\theta_{k}}\left(n\right){R_{\sec,2}^{k}}\left(n\right)}\geq{{\eta_{k}}},$
(29b) $\displaystyle{\eta_{k}}\geq{R_{\min}},$ (29c)
$\displaystyle{{\mathbf{q}}_{J}}\left(1\right)={\mathbf{q}}_{J}^{0},{{\mathbf{q}}_{J}}\left(n\right)={\mathbf{q}}_{J}^{F},$
(29d)
$\displaystyle\frac{1}{N}\sum\limits_{n=1}^{N}{\left\\{{\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{d_{J{U_{r}}}}+H_{2}^{2}}}+\sum\limits_{k=1}^{K}{{\theta_{k}}\left(n\right){P_{k}}\left(n\right){h_{S}}_{{U_{r}}}\left(n\right)}}\right\\}}\leq{\Gamma_{r}},\forall
r,$ (29e)
$\displaystyle{d_{J{U_{r}}}}\leq{\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|^{2}},$
(29f)

where

$\displaystyle{R_{\sec,2}^{k}}\left(n\right)$
$\displaystyle={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)-{\log_{2}}\left({\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{d_{JE}}+H_{2}^{2}}}+{\sigma^{2}}+{P_{k}}\left(n\right){h_{SE}}}\right)$
(30)
$\displaystyle+{\log_{2}}\left({\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{{\left({\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{\mathrm{E}}}}\right\|+{r_{E}}}\right)}^{2}}+H_{2}^{2}}}+{\sigma^{2}}}\right),$

where ${{d_{JE}}}$ is a new auxiliary variable and satisfies the following
constraints

${d_{JE}}\leq{\left({\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)^{2}}.$
(31)

By SCA, non-concave form in (30) is converted as

$\displaystyle{R}_{\sec,2}^{\textrm{lb}}\left(n\right)$
$\displaystyle={\log_{2}}\left({1+\frac{{{P_{k}}\left(n\right){h_{S{D_{k}}}}}}{{{\sigma^{2}}}}}\right)-{\log_{2}}\left({\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{d_{JE}}+H_{2}^{2}}}+{\sigma^{2}}+{P_{k}}\left(n\right){h_{SE}}}\right)$
(32)
$\displaystyle+N^{m}\left(n\right)+M^{m}\left(n\right)\left({{{\left({\left\|{{{\mathbf{q}}_{J}}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)}^{2}}-{{\left({\left\|{{\mathbf{q}}_{J}^{m}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)}^{2}}}\right),$

where

${M^{m}}\left(n\right)=\frac{{{{\left({\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{{\left({\left\|{{\bf{q}}_{J}^{m}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)}^{2}}+H_{2}^{2}}}+{\sigma^{2}}}\right)}^{-1}}}}{{\ln(2)}},$
(33)

and

$N^{m}\left(n\right)={\log_{2}}\left({\frac{{{P_{J}}\left(n\right){\rho_{0}}}}{{{{\left({\left\|{{\mathbf{q}}_{J}^{m}\left(n\right)-{{{\mathbf{\hat{w}}}}_{E}}}\right\|+{r_{E}}}\right)}^{2}}+H_{2}^{2}}}+{\sigma^{2}}}\right).$
(34)

Similar to $\mathcal{P}_{1.3}$, (29f) and (31) are approximated as

$\displaystyle r_{E}^{2}\leq{d_{JE}}$
$\displaystyle\leq{\left\|{{\bf{q}}_{J}^{m}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right\|^{2}}+r_{E}^{2}$
(35)
$\displaystyle+\left({2{{\left({{\bf{q}}_{J}^{m}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right)}^{T}}+\frac{{2{r_{E}}{{\left({{\bf{q}}_{J}^{m}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right)}^{T}}}}{{\left\|{{\bf{q}}_{J}^{m}\left(n\right)-{{{\bf{\hat{w}}}}_{E}}}\right\|}}}\right)\left({{{\bf{q}}_{J}}\left(n\right)-{\bf{q}}_{J}^{m}\left(n\right)}\right),$

and

${d_{J{U_{r}}}}\leq{\left\|{{{\mathbf{q}}_{J}}^{m}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right\|^{2}}+2{\left({{{\mathbf{q}}_{J}}^{m}\left(n\right)-{{\bf{w}}_{{U_{r}}}}}\right)^{T}}\left({{{\mathbf{q}}_{J}}\left(n\right)-{{\mathbf{q}}_{J}}^{m}\left(n\right)}\right),$
(36)

respectively. Then $\mathcal{P}_{1}$ is reformulated as

$\displaystyle\mathcal{P}_{1.4}\,:\,\max\limits_{{{\mathbf{q}}_{J}},{\eta_{k}},{d_{J{U_{r}}}},{d_{JE}}}$
$\displaystyle\sum\limits_{k=1}^{K}{{{\eta_{k}}}}$ (37)
$\displaystyle{\mathrm{s.t.}}$
$\displaystyle(\textrm{\ref{eq:p1.4b}}),(\textrm{\ref{eq:p1.4f}}),(\textrm{\ref{eq:p1.4c}}),(\textrm{\ref{eq:p1.4d}}),(\textrm{\ref{dJE2}}),\mathrm{and}\;(\textrm{\ref{dJUr}}).$

$\mathcal{P}_{1.4}$ is a convex problem and can be solved by existing
optimization tools such as CVX.

Input: Initialize feasible points

while
_$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)-R\left({{{\mathbf{\Theta}}^{m-1}},{{\mathbf{P}}^{m-1}},{\mathbf{q}}_{S}^{m-1},{\mathbf{q}}_{J}^{m-1}}\right)\succ{\varepsilon}$_
do

1\. Solve ($\mathcal{P}_{1.1}$) for given
$\left\\{{{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right\\}$
and obtain the solution ${{{\mathbf{\Theta}}^{m+1}}}$;

2\. Solve ($\mathcal{P}_{1.2}$) for given
$\left\\{{{{\mathbf{\Theta}}^{m+1}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right\\}$
and obtain the solution ${{{\mathbf{P}}^{m+1}}}$;

3\. Solve ($\mathcal{P}_{1.3}$) for given
$\left\\{{{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{J}^{m}}\right\\}$
and obtain the solution ${{\mathbf{q}}_{S}^{m+1}}$;

4\. Solve ($\mathcal{P}_{1.4}$) for given
$\left\\{{{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m+1}}\right\\}$
and obtain the solution ${{\mathbf{q}}_{J}^{m+1}}$;

4\. $m=m+1$;

5\. Compute the objective value
$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$.

end while

Output:
$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$
with
${{\mathbf{\Theta}}^{*}}={{\mathbf{\Theta}}^{m}},\;{{\mathbf{P}}^{*}}={{\mathbf{P}}^{m}},\;{\mathbf{q}}_{S}^{*}={\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{*}={\mathbf{q}}_{J}^{m}$.

Algorithm 1 Iterative Algorithm for Problem ($\mathcal{P}_{1}$)

###  III-E Overall Algorithm, Convergence, and Complexity

An iterative algorithm is proposed to solve $\mathcal{P}_{1}$ through
combining four subproblems discussed above and applying BCD. We need to select
the initial feasible points and obtain the suboptimal solution by solving
$\mathcal{P}_{1.1}$, $\mathcal{P}_{1.2}$, $\mathcal{P}_{1.3}$, and
$\mathcal{P}_{1.4}$ alternatively. The obtained solutions in each iteration
are utilized as the feasible input points for the next iteration. Defining the
objective function of the original problem $\mathcal{P}_{1}$ at the $m$th
iteration as
$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$,
Algorithm 1 summarizes the details of overall iterations for
$\mathcal{P}_{1}$, where $\varepsilon$ denotes the tolerance of convergence.
The convergence of Algorithm 1 is proved as follows.

###### Proof.

In Step 1 of Algorithm 1, a standard linear problem $\mathcal{P}_{1.1}$ is
solved and we obtain the solution ${{\mathbf{\Theta}}^{m+1}}$. Thus, we have

$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)\leq
R\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right).$
(38)

Then, the suboptimal solution ${{{\mathbf{P}}^{m+1}}}$ is obtained through
solving $\mathcal{P}_{1.3}$ as

$\displaystyle
R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$
$\displaystyle=R\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$
(39)
$\displaystyle\leq{R^{lb}}\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$
$\displaystyle\leq
R\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right),$

where
${R^{lb}}\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)$
is the objective function of the approximate problem $\mathcal{P}_{1.3}$,
which is a lower bound to the objective function of $\mathcal{P}_{1}$. Eq.
(39) indicates that the objective function is always non-decreasing after each
iteration.

The proof of the convergence in Step 3 and Step 4 is similar to that of (39),
and the result follows

$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)\leq
R\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m+1},{\mathbf{q}}_{J}^{m}}\right),$
(40)

and

$R\left({{{\mathbf{\Theta}}^{m}},{{\mathbf{P}}^{m}},{\mathbf{q}}_{S}^{m},{\mathbf{q}}_{J}^{m}}\right)\leq
R\left({{{\mathbf{\Theta}}^{m+1}},{{\mathbf{P}}^{m+1}},{\mathbf{q}}_{S}^{m+1},{\mathbf{q}}_{J}^{m+1}}\right).$
(41)

Thus, we further find the objective function in $\mathcal{P}_{1}$ is non-
decreasing after each iteration, which is upper bounded by a finite value due
to the feasible set under the constraints. Then Algorithm 1 is convergent. ∎

The complexity of Algorithm 1 comes from two aspects. The first aspect is
about the complexity analysis of the user scheduling coefficient, which is
solved via standard linear programming by the interior point method with
complexity ${\cal
O}\left({\sqrt{N\left({K+1}\right)}\log\frac{1}{\varepsilon}}\right)$. The
second aspect is about the complexity analysis of solving transmit power and
UAV trajectory optimization by using SCA, where the complexity is ${\cal
O}\left({{{\left({\left({K+R+1}\right)N}\right)}^{3.5}}\log\frac{1}{\varepsilon}}\right)$.
It is assumed that the number of iterations in the outer and inner loops are
$M_{1}$ and ${M_{2}}$. Thus, the total complexity of Algorithm 1 is ${\cal
O}\left({{M_{1}}\sqrt{N\left({K+1}\right)}\log\frac{1}{\varepsilon}+{M_{2}}{{\left({\left({K+R+1}\right)N}\right)}^{3.5}}\log\frac{1}{\varepsilon}}\right)$.

##  IV Numerical Results and Analysis

In this section, numerical results are provided for verifying the convergence
and effectiveness of the proposed algorithm. We consider a 2-D square area
with three CUs ($K=3$), two PUs ($R=2$), and an Eve. The horizonal coordinates
are set as ${\left[{-55,-10};{0,-65};{50,-5}\right]^{T}}$ and
${\left[{30,25};{-30,25}\right]^{T}}$. The center of the circle of the area
where $E$ is located is set as
${{\bf{\hat{w}}}_{E}}={\left[{15,-15}\right]^{T}}$. According to [23], the
maximum flight speed of UAVs is set as ${V_{\max}}=7$ m/s and the altitudes of
$S$ and $J$ are set as ${H_{1}}=15$ m and ${H_{2}}=10$ m, respectively. The
channel power gain at a reference distance of 1 m is ${\rho_{0}}=-30$ dBm and
the noise power is set as ${\sigma^{2}}=-90$ dBm. The maximum transmit power
levels of the UAVs are $P_{S}^{\max}=4P_{S}^{ave}$ and
$P_{J}^{\max}=4P_{J}^{ave}$, respectively. The average interference power
threshold at the PU is set as ${\Gamma_{r}}=-80$ dBm and and the error
tolerance is set as ${\varepsilon}=0.001$.

The numerical results of three benchmark schemes are presented in the
simulations.

  1. 1.

Benchmark I: Both $S$ and $J$ utilize constant transmit power and follow a
circular flight path.

  2. 2.

Benchmark II: $S$ is designed with joint optimization of power and trajectory,
$J$ keeps flying with a constant power and circular trajectory.

  3. 3.

Benchmark III: $J$ takes a joint optimization of power and trajectory to
disrupt $E$, and $S$ flies with constant transmitting power and circular
flight trajectory.

The initial flight trajectory of UAVs is set as circular with constant speed
whose center is the geometric center of ground nodes, i.e.,
$C=\frac{1}{K}\sum\limits_{k=1}^{K}{{{\bf{w}}_{{D_{k}}}}}$. It is suitable for
${S}$ to visit all CUs and its initial flight radius for $S$ can be computed
according to
${{{R}}_{S}}=\min\left({\frac{{{{{V}}_{\max}}T}}{{2\pi}},\left\|{C-{{\bf{w}}_{{D_{k}}}}}\right\|}\right)$.
The initial flight path of the ${J}$ must cover region where the eavesdropping
node is uncertain. Therefore, its initial flight radius for $S$ is defined as
${R_{J}}=\frac{1}{2}{R_{S}}$. Based on initial flight trajectories, the
initial power is set as $P_{S}^{0}=P_{S}^{ave}$ and $P_{J}^{0}=P_{J}^{ave}$.
Similar to [29], if ${{R_{S{D_{k}}}}\left(n\right)-{R_{E}}\left(n\right)}$ is
non-negative, $P_{S}=0$.

Figure 2: Relationship between the sum average secrecy rate and the number of
iterations.

Fig. 2 demonstrates the sum average secrecy rate of the considered system
versus the number of iterations for UAVs in different flight periods under
varying uncertain eavesdropping coverage. The results demonstrate the
convergence of the proposed scheme regarding the jointly optimized user
scheduling coefficients, the UAV transmitting power, and the UAV flight
trajectory. One can observe that the average sum secrecy rate increases
quickly with the flight time, the number of iterations, and converges within
around 15 iterations in the listed four flight periods. Furthermore, as the
range of eavesdropping uncertainty area decreases, the system’s average sum
secrecy rate gradually increases.

Figure 3: The optimal trajectory of UAVs during the flight cycle.

Fig. 3 demonstrates the optimal UAV trajectories achieved by jointly
optimizing user scheduling, UAV transmitting power, and flight trajectories,
in which the black arrows denote the flight directions of the two UAVs, which
are in opposite directions. By adopting the proposed iterative algorithm, the
flight trajectory of UAVs eventually changes from the initial circular
trajectory to the flight trajectory. It can be observed that $S$ starts from
the departure point and gradually approaches, hovers, and leaves each
cognitive user, which means the approach of scheduling CUs within each time
slot is utilized by the base station in the considered system using the
frequency band authorized by the primary network. Moreover, based on the
trajectory of the jammer UAV, although the location of $E$ cannot be obtained
precisely, an optimal trajectory is obtained to fly around the area where $E$
is located through a joint optimization algorithm to better suppress
eavesdropping the legitimate signals.

Figure 4: Dynamic power variation during the flight cycle of the UAVs.

Fig. 4 illustrates the dynamic variation of the UAV transmitting power during
a flight cycle. One can observe ${P_{S}}$ and ${P_{J}}$ keep a tendency to
couple. When ${P_{J}}$ experiences an upward trend, ${P_{S}}$ experiences a
downward trend.

Figure 5: User scheduling during the UAVs flight cycle.

The user scheduling result is plotted in Fig. 5. It can be observed that all
the CUs are alternately awake, which indicates that only one user is scheduled
by $S$ in each time slot, at which point the unscheduled users keep silent.
The UAV hovers over the target area for a period, all the CUs obtain service
in turn. Since UAV cannot completely cover users in a time slot, it is
necessary to optimize the user scheduling to ensure the secure communication
on each user. Therefore, the minimum average security rate must be satisfied
as (15d). For all users satisfying secure communication at the same slot, the
user with the largest secure rate will be scheduled. Since the average secrecy
rate is optimized considering the minimum secrecy rate on all the CUs,
fairness is achieved among these CUs, as shown in Fig. 5.

Figure 6: Performance comparison of the proposed scheme and the NPC scheme
with varying ${{r_{E}}}$.

In Fig. 6, we compare the performance between the proposed scheme and no power
control (NPC) scheme with varying time and radius of the eavesdropper
uncertainty area. One can observe the average secrecy rate has an increasing
trend with increasing flight time of the UAVs and/or performing power control.
The eavesdropper uncertainty area radius, which reflects the CSI between the
UAV and the eavesdropping node, has a considerable impact on the average
security rate of the considered system. The smaller the ${r_{E}}$, the clearer
the base station is about the location information of the eavesdropper.

Figure 7: The sum average secrecy rate versus $T$ with different scenarios.

Fig. 7 demonstrates the variation of the secrecy rate of the system with time
$T$ for different scenarios wherein constant transmit power is utilized on $S$
and/or $J$. One can clearly observe that the sum secrecy rate of the system
obtained by the proposed iterative algorithm based on BCD and SCA is much
better than the other scenarios. Comparing with optimizing trajectory of $S$
alone, optimizing both the power and trajectory of $J$ can effectively cope
with the uncertainty of the eavesdropper location. The scheme proposed in this
work, i.e., optimizing the power and trajectory of both $S$ and $J$ can
maximize the security performance of the considered system.

Figure 8: The sum average secrecy rate versus interference threshold
constraint ${\Gamma_{r}}$ with different scenarios.

Fig. 8 illustrates the effect of the interference power thresholds of the PUs
on the average secrecy rate concerning the flight time under different
scenarios. It is observed that the average secrecy rate achieved by all
schemes increases rapidly in the lower-${\Gamma_{r}}$ region then tends to be
saturated. This is because the available transmit power in the
lower-${\Gamma_{r}}$ region increases with the relaxation of the average
interference power thresholds constraints, then $S$ has a higher degree of
freedom in power allocation. Thus, the secrecy rate is effectively improved.
However, in the larger-${\Gamma_{r}}$ region, the transmit power on $S$ and
$J$ are restricted by $P_{S}^{\max}$ and $P_{J}^{\max}$ to meet the maximum
power constraints rather than interference threshold constraints.

##  V Conclusion

This paper investigates a dual collaborative UAV system for physical layer
security in a multi-user scheduling scenario on the uncertainty of potential
eavesdropping node locations in CRNs. The joint design of maximizing the
average secrecy rate is formulated as a mixed-integer non-convex problem by
considering UAV trajectories, user scheduling, and transmit power. An
efficient iterative algorithm based on BCD and SCA was proposed to tackle the
challenging non-convex problem and achieve a suboptimal solution. Numerical
results verified the convergence and effectiveness of our proposed algorithm.

## References

  * [1] Q. Wu, J. Xu, Y. Zeng, D. W. K. Ng, N. Al-Dhahir, R. Schober, and A. L. Swindlehurst, “A comprehensive overview on 5G-and-beyond networks with UAVs: From communications to sensing and intelligence,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 10, pp. 2912-2945, Oct. 2021.
  * [2] B. Li, Z. Fei, and Y. Zhang, “UAV communications for 5G and beyond: Recent advances and future trends,” _IEEE Internet Things J._ , vol. 6, no. 2, pp. 1-23, Apr. 2019.
  * [3] Q. Wu, L. Liu, and R. Zhang, “Fundamental trade-offs in communication and trajectory design for UAV-enabled wireless network,” _IEEE Wireless Commun._ , vol. 26, no. 1, pp. 36-44, Feb. 2019.
  * [4] Y. Zeng, R. Zhang, and T. J. Lim, “Wireless communications with unmanned aerial vehicles: Opportunities and challenges,” _IEEE Commun. Mag._ , vol. 54, no. 5, pp. 36-42, May 2016.
  * [5] Y. Zeng, Q. Wu, and R. Zhang, “Accessing from the sky: A tutorial on UAV communications for 5G and beyond,” _Proc. IEEE_ , vol. 107, no. 12, pp. 2327-2375, Dec. 2019.
  * [6] Q. Wu, Y. Zeng, and R. Zhang, “Joint trajectory and communication design for multi-UAV Enabled wireless networks,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 3, pp. 2109-2121, Mar. 2018.
  * [7] A. Bejaoui, K.-H. Park, and M.-S. Alouini, “A QoS-oriented trajectory optimization in swarming unmanned-aerial-vehicles communications,” _IEEE Wireless Commun. Lett._ , vol. 9, no. 6, pp. 791-794, Jun. 2020.
  * [8] T. Liu, M. Cui, G. Zhang, Q. Wu, X. Chu, and J. Zhang, “3D trajectory and transmit power optimization for UAV-enabled multi-link relaying systems,” _IEEE Trans. Green Commun. Netw._ , vol. 5, no. 1, pp. 392-405, Mar. 2021.
  * [9] J.-H. Lee, K.-H. Park, Y.-C. Ko, and M.-S. Alouini, “Throughput maximization of mixed FSO/RF UAV-aided mobile relaying with a buffer,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 1, pp. 683-694, Jan. 2021.
  * [10] C. Zhan, Y. Zeng, and R. Zhang, “Energy-efficient data collection in UAV enabled wireless sensor network,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 3, pp. 328-331, Jun. 2018.
  * [11] W. Lu, P. Si, F. Lu, B. Li, Z. Liu, S. Hu, and Y. Gong, “Resource and trajectory optimization in UAV-powered wireless communication system,” _Sci. China Inf. Sci._ , vol. 64, no. 4, pp. 1-14, Mar. 2021.
  * [12] W. Luo, Y. Shen, B. Yang, S. Wang, and X. Guan, “Joint 3-D trajectory and resource optimization in multi-UAV-enabled IoT networks wth wireless power transfer,” _IEEE Internet Things J._ , vol. 8, no. 10, pp. 7833-7848, May. 2021.
  * [13] Q. Wu, W. Mei, and R. Zhang, “Safeguarding wireless network with UAVs: A physical layer security perspective,” _IEEE Wireless Commun._ , vol. 26, no. 5, pp. 12-18, Oct. 2019.
  * [14] H.-M. Wang, X. Zhang, and J.-C. Jiang, “UAV-Involved wireless physical-layer secure communications: Overview and research directions,” _IEEE Wireless Commun._ , vol. 26, no. 5, pp. 32-39, Oct. 2019.
  * [15] B. Li, Z. Fei, Y. Zhang, and M. Guizani, “Secure UAV communication networks over 5G,” _IEEE Wireless Commun._ , vol. 26, no. 5, pp. 114-120, Oct. 2019.
  * [16] Z. Li, M. Chen, C. Pan, N. Huang, Z. Yang, and A. Nallanathan, “Joint trajectory and communication design for secure UAV networks,” _IEEE Commun. Lett._ , vol. 23, no. 4, pp. 636-639, Apr. 2019.
  * [17] H. Lee, S. Eom, J. Park, and I. Lee, “UAV-aided secure communications with cooperative jamming,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 10, pp. 9385-9392, Oct. 2018.
  * [18] C. Zhong, J. Yao, and J. Xu, “Secure UAV communication with cooperative jamming and trajectory control,” IEEE Commun. Lett., vol. 23, no. 2, pp. 286-289, Feb. 2019.
  * [19] R. Zhang, X. Pang, W. Lu, N. Zhao, Y. Chen, and D. Niyato, “Dual-UAV enabled secure data collection with propulsion limitation,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 11, pp. 7445-7459, Jun. 2021.
  * [20] Y. Huang, W. Mei, J. Xu, L. Qiu, and R. Zhang, “Cognitive UAV communication via joint maneuver and power control,” _IEEE Trans. Commun._ , vol. 67, no. 11, pp. 7872-7888, Nov. 2019.
  * [21] Z. Ullah, F. Al-Turjman, and L. Mostarda, “Cognition in UAV-aided 5G and beyond communications: A survey,” IEEE Trans. Cogn. Commun. Netw., vol. 6, no. 3, pp. 872-891, Sept 2020.
  * [22] Y. Zhou, F. Zhou, H. Zhou, D. W. K. Ng, and R. Q. Hu, “Robust trajectory and transmit power optimization for secure UAV-enabled cognitive radio networks,” _IEEE Trans. Commun._ , vol. 68, no. 7, pp. 4022-4034, Jul. 2020.
  * [23] Y. Wang, L. Chen, Y. Zhou, X. Liu, F. Zhou, and N. Al-Dhahir, “Resource allocation and trajectory design in UAV-assisted jamming wideband cognitive radio networks,” _IEEE Trans. Cogn. Commun. Netw._ , vol. 7, no. 2, pp. 635-647, Jun. 2021.
  * [24] P. X. Nguyen, V.-D. Nguyen, H. V. Nguyen, and O.-S. Shin, “UAV-assisted secure communications in terrestrial cognitive radio networks: Joint power control and 3D trajectory optimization,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 4, pp. 3298-3313, Apr. 2021.
  * [25] Y. Chen, N. Li, X. Zhong, and W. Xie, “Joint trajectory and scheduling optimization for the mobile UAV aerial base station: A fairness version,” Applied Sciences., vol. 9, no. 15, pp. 1-13, Jul. 2019.
  * [26] L. Lv, F. Zhou, J. Chen, and N. Al-Dhahir, “Secure cooperative communications with an untrusted relay: A NOMA-inspired jamming and relaying approach,” _IEEE Trans. Inf. Forensics Security_ , vol. 14, no. 12, pp. 3191-3205, Dec. 2019.
  * [27] Y. Cai, F. Cui, Q. Shi, M. Zhao, and G. Y. Li, “Dual-UAV-enabled secure communications: Joint trajectory design and user scheduling,” IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 1972-1985, Sept. 2018.
  * [28] H. Xing, L. Liu, and R. Zhang, “Secrecy wireless information and power transfer in fading wiretap channel,” IEEE Trans. Veh. Technol., vol. 65, no. 1, pp. 180-190, Jan. 2016.
  * [29] G. Zhang, Q. Wu, M. Cui, and R. Zhang, “Securing UAV communications via joint trajectory and power control,” IEEE Trans. Wireless Commun., vol. 18, no. 2, pp. 1376-1389, Feb. 2019.


# Learning Theory and Support Vector Machines
a primer

Michael Banf
EducatedGuess.ai
Siegen, Germany
<EMAIL_ADDRESS>

###### Abstract

The main goal of statistical learning theory is to provide a fundamental
framework for the problem of decision making and model construction based on
sets of data. Here, we present a brief introduction to the fundamentals of
statistical learning theory, in particular the difference between empirical
and structural risk minimization, including one of its most prominent
implementations, i.e. the Support Vector Machine.

_K_ eywords Machine Learning $\cdot$ Statistical Learning Theory $\cdot$
Supervised Learning

## Introduction to Statistical Learning Theory

The main goal of statistical learning theory [4],[2] is to provide a
fundamental framework for the problem of decision making and model
construction based on sets of data. Assumptions can be made of the statistical
nature about the underlying phenomena. One of the original problems in
applying statistical learning theory is that of binary pattern recognition.
Here, given two classes of entities, one has to assign a novel unclassified
object to either of the two classes. This problem can be formalized as follow:
Suppose we are given $m$ observations, where each observation $i$ consists of
the data $\boldsymbol{x}_{i}\in\mathcal{R}^{n},i=1,...,m$, as well as a
“ground truth” labeling $y_{i}\in\\{-1,1\\}$. Then, given the data

$(\boldsymbol{x}_{1},y_{1}),...,(\boldsymbol{x}_{m},y_{m})\in\mathcal{X}\times\\{-1,1\\}$
(1)

we want to estimate a decision function
$f\rightarrow\mathcal{X}\times\\{-1,1\\}$ that is able to generalize, i.e.
avoid model overfitting, to unseen data points, i.e. minimizing the expected
risk:

$R(\alpha)=\int\frac{1}{2}\mid y-f(\boldsymbol{x},\alpha)\mid
dP(\boldsymbol{x},y)$ (2)

It is assumed that some unknown probability distribution
$P(y,\boldsymbol{x})$, from which the data is, independently drawn and
identically distributed (iid), drawn, does exists. Therefore, if
$p(y,\boldsymbol{x})$ exists, $dP(y,\boldsymbol{x})$ may be written as
$p(\boldsymbol{x},y)d\boldsymbol{x}dy$, in order to state the true error rate.
Statistical learning theory proves the necessity to restrict the set of
functions from which $f$ can be selected with respect to the capacity suitable
for the number of available training data, and it provides some upper bound on
the test error, depending on the capacity of the function class as well as the
empirical risk. Subsequently, minimizing this bound provides the basis for
structural risk minimization [2]. The empirical risk $R_{emp}(\alpha)$ is
defined as the measured mean error rate on the training data:

$R_{emp}(\alpha)=\frac{1}{2m}\sum_{i=1}^{m}\mid
y_{i}-f(\boldsymbol{x}_{i},\alpha)\mid$ (3)

Here, $R_{emp}(\alpha)$ is a fixed number for a particular choice of $\alpha$
and a particular training set $\\{\boldsymbol{x}_{i},y_{i}\\}$.
$\frac{1}{2}\mid y_{i}-f(\boldsymbol{x}_{i},\alpha)\mid$ is known as the loss
function.

For binary classification, output values are either 0 or 1. Thus, choosing
$\eta$ such that $0\leq\eta\leq 1$ yields the following bound for the loss
function, with probability $1\>\text{-}\>\eta$ [2]:

$R(\alpha)\leq
R_{emp}(\alpha)+\sqrt{(\frac{h(\log(2m/h)+1)-\log(\eta/4)}{m})}$ (4)

$h$ denotes a non-negative integer called the Vapnik Chervonenkis (VC)
dimension and describes a property of a set of functions $\\{f(\alpha)\\}$. It
can be defined for various classes of functions $f$. A given set of $m$
observations can be labeled in all possible $2m$ ways, and for each labeling,
a member of the set $\\{f(\alpha)\\}$ can be found that correctly assigns
those labels. This is described as “shattering” this set of observations by
that set of functions. Hence, the VC dimension for such a set of functions
$\\{f(\alpha)\\}$ is defined as the maximum number of training points that can
be “shattered” by $\\{f(\alpha)\\}$. Note that if the VC dimension would be
$h$, there is at least one particular set of $h$ points that can be shattered.
In general, however, it is not the case that each set of $h$ points can be
shattered.

The second term on the right hand side of equation (4) is called the “VC
confidence” and the whole right hand side of equation (4) the “risk bound”,
which is independent of $P(\boldsymbol{x},y)$. The risk bound only presumes
that both, the training and test data, are drawn independently according to
$P(\boldsymbol{x},y)$. Generally, it is not possible to compute the left hand
side, however, if $h$ is known, one can compute the right hand side.

## Structural Risk Minimization

Thus, given several different families of functions
$f(\boldsymbol{x},\alpha)$, called “learning machines” and choosing a fixed,
sufficiently small $\eta$, by then taking that machine which minimizes the
right hand side, one can choose that machine which provides the lowest upper
bound on the actual risk. This provides a method for selecting a learning
machine for a given task and is the fundamental idea of structural risk
minimization. The VC confidence is described as a monotonic increasing
function of $h$ (see in figure 1) for any number of observations $m$ and given
a selection of learning machines whose empirical risk would be equal to zero,
one wants to select a learning machine whose set of functions, associated with
it, has a minimal VC dimension, which then leads to a better upper bound on
the actual error, as illustrated in figure 1. In general, for non zero
empirical risk, one selects that specific learning machine that will minimize
the right hand side of equation (4).

Figure 1: Finding the best model complexity to avoid underfitting, i.e. not
being able to separate the data appropriately, as well as overfitting, i.e. no
being able to generalize to unseen data.

## Support Vector Machines

Support Vector Machines can be considered an approximate implementation of the
principle of structural risk minimization, as they try to minimize a
combination of the empirical risk in equation (3), and a capacity term derived
for the class of hyper-planes in a dot product space $\mathcal{H}$ [2],

$\langle\boldsymbol{w},\boldsymbol{x}\rangle+b=0\textnormal{\quad with
\quad}\boldsymbol{w}\in\mathcal{H},b\in\mathbb{R}$ (5)

corresponding to decision functions

$f(x)=sgn(\langle\boldsymbol{w},\boldsymbol{x}\rangle+b).$ (6)

### Hard and Soft Margin Solutions

In case of a linearly separable set of observations, a unique optimal hyper-
plane exists, differentiated by the maximal margin of separation between any
observation point $\boldsymbol{x}_{i}$ and the hyper-plane, as visualized in
figure 2 (left). Such a case is called a hard margin solution. This optimal
hyper-plane would be the solution of

$\underset{\boldsymbol{w}\in\mathcal{H},b\in\mathbb{R}}{maximize}\>\min\\{\|\boldsymbol{x}-\boldsymbol{x}_{i}\|\mid\boldsymbol{x}\in\mathcal{H},\langle\boldsymbol{w},\boldsymbol{x}\rangle+b=0,i=1,...,m\\}$
(7)

Further, the capacity of the class of separating hyper-planes decreases with
increasing margin. As illustrated in figure 2 (left), in order to construct
the optimal hyper-plane, on needs to solve the following quadratic programming
problem

$\underset{\boldsymbol{w}\in\mathcal{H},b\in\mathbb{R}}{minimize}\>\frac{1}{2}\|\boldsymbol{w}\|^{2}\newline
\textnormal{\quad subject to
\quad}y_{i}(\langle\boldsymbol{w},\boldsymbol{x}_{i}\rangle+b)\geq
1\textnormal{\quad}\forall i=1,...,m$ (8)

The constraints ensure that $f(\boldsymbol{x}_{i})$ will be $+1$ for
$y_{i}=+1$, and $\text{-}1$ for $y_{i}=\text{-}1$. This constrained
optimization problem in equation (8) is computed based on Lagrange multipliers
[1] $\alpha_{i}\geq 0\>\>(\boldsymbol{\alpha}:=(\alpha_{1},...,\alpha_{m}))$
and a Lagrangian

$L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}-\sum_{i=1}^{m}\alpha_{i}(y_{i}(\langle\boldsymbol{w},\boldsymbol{x}_{i}\rangle+b)-1)$
(9)

$L$ has some saddle point in $\boldsymbol{w}$, $b$ and $\boldsymbol{\alpha}$
at the optimal solution of the primal optimization problem. Therefore, it is
minimized with respect to the primal variables $\boldsymbol{w}$ and $b$ and
maximized with respect to the dual variables $\alpha_{i}$. Moreover, the
product between constraints and Lagrange multipliers in $L$ diminishes at
optimality, i.e.,

$\alpha_{i}(y_{i}(\langle\boldsymbol{w},\boldsymbol{x}_{i}\rangle+b)-1)=0\textnormal{\quad}\forall
i=1,...,m$ (10)

known in optimization theory [3] as Karush-Kuhn-Tucker conditions [3],[1].
Minimization with respect to the primal variables requires

$\frac{\partial}{\partial\>b}L(\boldsymbol{w},b,\boldsymbol{\alpha})=-\sum_{i=1}^{m}\alpha_{i}\>y_{i}=0$
(11)

The solution has some expansion in terms of a subset of the observations, i.e.
the Support Vectors, with non-zero $\alpha_{i}$:

$\frac{\partial}{\partial\>\boldsymbol{w}}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\boldsymbol{w}-\sum_{i=1}^{m}\alpha_{i}\>y_{i}\>\boldsymbol{x}_{i}=0$
(12)

Figure 2: Left: Linear separable classification. Optimal hyperplane is shown
as a solid line. Weight vector $\boldsymbol{w}$ and a threshold $b$ yield
$y_{i}(\langle\boldsymbol{w},\boldsymbol{x}_{i}\rangle+b)>0\textnormal{\quad}\forall
i=1,...,m$. Support Vectors lie on the borders of the margin (dashed lines).
Right: Examples of a non-linear separation surface found using a radial basis
function kernel
$k(\boldsymbol{x},\boldsymbol{x^{\prime}})=e^{-\|\boldsymbol{x}-\boldsymbol{x^{\prime}}\|^{2}}$.

Most often, only a fraction of the training examples actually end up being
Support Vectors and due to the Karush-Kuhn-Tucker conditions, Support Vectors
define the margin (see figure 2 (left)). Thus, once all $\alpha_{i}$ have been
found, we can compute $b$ . All remaining training examples
$(\boldsymbol{x}_{j},y_{j})$ turn out to be irrelevant as their constraints
$y_{j}(\langle\boldsymbol{w},\boldsymbol{x}_{j}\rangle+b)\geq 1$ can be
discarded. Therefore, the hyper-plane is completely determined by the
observations closest to them. Substitution of equation (11) and equation (12)
by the Lagrangian in equation (9) eliminates the primal variables
$\boldsymbol{w}$ and $b$, resulting in the dual optimization problem:

$\underset{\alpha\in\mathbb{R}^{m}}{maximize}\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\>\alpha_{j}\>y_{i}\>y_{j}\>K_{ij}\textnormal{\quad
subject to \quad}\alpha_{i}\geq 0\quad\forall
i=1,...,m\>\wedge\>\sum_{i=1}^{m}\alpha_{i}\>y_{i}=0$ (13)

with $K_{ij}:=\langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle$. Based on
equation (12), the decision function in equation (6) is written as

$f(\boldsymbol{x})=sgn\left(\sum_{i=1}^{m}y_{i}\>\alpha_{i}\>\langle\boldsymbol{x},\boldsymbol{x}_{i}\rangle+b\right)$
(14)

Here, $b$ can be computed using equation (10). In practise, however, a
separating hyper-plane may not exist, e.g. if noise within the training data
causes a large overlap of the classes. In consideration of such a case, slack
variables $\xi_{i}\geq 0\>\forall i=1,...,m$ are introduced in order to relax
the constraints of equation (8) to

$y_{i}(\langle\boldsymbol{w},\boldsymbol{x}_{i}\rangle+b)\geq
1-\xi_{i}\quad\forall i=1,...,m$ (15)

Thus, a learning machine that generalizes appropriately is found by
controlling both, the classifier capacity, based on $\|\boldsymbol{w}\|$, and
the sum of the slack variables $\sum_{i=1}^{m}\xi_{i}$, which provides an
upper bound on the number of training errors. Such a classifier, known as soft
margin solutions, is obtained by minimizing the objective function

$\frac{1}{2}\|\boldsymbol{w}\|^{2}+C\>\sum_{i=1}^{m}\xi_{i}$ (16)

subject to the constraints on $\xi_{i}$ and equation (15). The constant $C>0$
determines the trade-off between margin maximization and training error
minimization. Again, this leads to the problem of maximizing equation (13),
subject to modified constraint with the only difference from the separable
case being an upper bound $C$ on the Lagrange multipliers $\alpha_{i}$.
Another realization replaces the parameter $C$ by a parameter $\nu\in(0,1]$
that provides upper and lower bounds for the subset of examples which become
Support Vectors and those which will have non-zero slack variables,
respectively [2].

### Non Linear Support Vector Machines

If the decision function $f$ in equation (6) is not linear, all above methods
have to be generalized to these cases. Boser et al. [5], proved that a rather
old method [6], referred to as kernel trick, can be used to accomplish this in
a straightforward manner. Thereby, symmetric similarity measures of the form
$k:\mathcal{H}\times\mathcal{H}\rightarrow\mathcal{R}$, with
$(\boldsymbol{x},\boldsymbol{x^{\prime}})\rightarrow
k(\boldsymbol{x},\boldsymbol{x^{\prime}})$, are considered. These functions,
given two observations $x$ and $x^{\prime}$ return a real number value
denoting their similarity. To allow for a variety of similarity measures and
learning algorithms, the observations are represented as vectors in an
arbitrary selected feature space $\boldsymbol{\Phi}$, due to the mapping:
$\boldsymbol{\Phi}=\mathcal{X}\rightarrow\mathcal{H}$ with
$\boldsymbol{x}\rightarrow\boldsymbol{\Phi}(\boldsymbol{x})$. The function $k$
is often referred to as a kernel. Some popular kernel choice are Gaussian,
$k(\boldsymbol{x},\boldsymbol{x^{\prime}})=e^{-\frac{\|\boldsymbol{x}-\boldsymbol{x^{\prime}}\|^{2}}{2\sigma^{2}}}$,
or Radial Basis Functions,
$k(\boldsymbol{x},\boldsymbol{x^{\prime}})=e^{\gamma\|\boldsymbol{x}-\boldsymbol{x^{\prime}}\|^{2}}$,
as shown in figure 2 (right). Finally, $f$ can be rewritten as

$f(x)=sgn\left(\sum_{i=1}^{m}y_{i}\>\alpha_{i}\>k(\boldsymbol{x},\boldsymbol{x_{i}})+b\right)$
(17)

Furthermore, in the quadratic optimization problem (13) the definition of
$K_{ij}$ becomes $K_{ij}=k(\boldsymbol{x_{i}},\boldsymbol{x_{j}})$.

### Probability Estimates

As discussed, Support Vector Machines predict only class labels without
probability information. However, several extensions to provide probability
estimates have been presented [7],[8]. Briefly, given $n$ classes of data, for
any observation $\boldsymbol{x}$, the goal would be to estimate

$p_{i}=P(y=i|\boldsymbol{x}),\>i=1,...,n$ (18)

Following [7],[8], in the context of the one-against-one (i.e., pairwise)
approach for multi-class classification, we first estimate pairwise class
probabilities as

$r_{ij}\approx P(y=i|y=i\>\wedge\>j,\boldsymbol{x})$ (19)

If $\widehat{f}$ is the decision value at $\boldsymbol{x}$, then we assume

$r_{ij}\approx\frac{1}{1+e^{A\>\widehat{f}+B}}$ (20)

where $A$ and $B$ are estimated by minimizing the negative log likelihood of
training data, using their labels and decision values. It has been observed
that decision values from training may overfit the model in equation (20), so
cross-validation is conducted to obtain decision values before minimizing the
negative log likelihood. After collecting all $r_{ij}$ values, Wu et al. [7]
propose various possible approaches to obtain $p_{i},\>\forall i$.

### Hyper-parameter Estimation

Also there exist a varity of sophisticated approaches to infer the best set of
hyper-parameters, i.e. the most appropriate parameters $C$ for linear Support
Vector Machines, as well as $(C,\gamma)$, for Radial basis functions based
non-linear Support Vector Machines, would be grid search based cross
validation.

## References

  * [1] C. J. C. Burge.  A tutorial on support vector machines for pattern recognition.  In Data Mining and Knowledge Discovery, pages 121–167. 1998.
  * [2] B. Schoelkopf, and A. Smola.  Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond.  MIT Press. 2001
  * [3] R. Fletcher.  Practical Methods of Optimization.  John Wiley and Sons,. 1987.
  * [4] V. N. Vapnik.  The Nature of Statistical Learning Theory.  In Transactions on Neural Networks., IEEE, 1999.
  * [5] B. E. Boser, I. M. Guyon and V. N. Vapnik  A training algorithm for optimal margin classifiers.  In COLT ’92 Proceedings of the fifth annual workshop on Computational learning theory., 144-152 , 1992.
  * [6] M.A. Aizerman, E.M. Braverman and L.I. Rozonoer  Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning.  In Automation and Remote Control., 25, 821-837. , 1964.
  * [7] T. Wu, C. Lin and R. C. Weng.  Probability Estimates for Multi-class Classification by Pairwise Coupling.  In Journal of Machine Learning Research., 2004
  * [8] J. Platt.  Probabilistic outputs for support vector machines and comparison to regularized likelihood methods.  In A. Smola, P. Bartlett, B. Schoelkopf, and D. Schuurmans (eds.): Advances in Large Margin Classifiers. Cambridge, MA, MIT Press., 1999.