# Optimal Construction for Time-Convex Hull with Two Orthogonal Highways in
the $L_{1}$-metric

Jyun-Yu Chen1 , Po-Hsuan Chen2
1 Department of Computer Science and Information Engineering
National Chung Cheng University, Chiayi, Taiwan
<EMAIL_ADDRESS>
2 Department of Computer Science and Information Engineering
National Chung Cheng University, Chiayi, Taiwan
<EMAIL_ADDRESS>

###### Abstract

We consider the time-convex hull problem in the presence of two orthogonal
highways H. In this problem, the travelling speed on the highway is faster
than off the highway, and the time-convex hull of a point set P is the closure
of P with respect to the inclusion of shortest time-paths.

In this paper, we provide the algorithm for constructing the time-convex hull
with two orthogonal highways. We reach the optimal result of $O(n\log{n})$
time for arbitrary highway speed in the L1-metric. For the L2-metric with
infinite highway speed, we hit the goal of $O(n\log{n})$ time as well.

##  1 Introduction

Path planing of a transition network has been an important problem in recent
years. In a complex transition network, lots of models have been provided to
solve traffic issues. Highway is one of a simple model in it. We assume that
we can enter or exit the highway at any point, and the moving speed on the
highway is $v>1$, while the speed off the highway is $v=1$. Due to the
highway, the path of two points using highway may be faster than their
straight-line path. Therefore, we care about the minimum travelling time of a
path rather than its distance. To replace the definition of distance, we make
use of the measure named time-distance. The time-distance of two points is
defined to be the minimum travelling time from one point to the other one.

The convex hull in the presence of a highway was introduced by Hurtado et al
[5]. A set $S$ is convex if it contains the shortest time-path between any two
point in $S$. We define the time-convex hull of a set $S$, which is a closure
of $S$ with respect to the inclusion of shortest time-paths.

In previous works, the convex hull in the presence of highway was first solved
by Palop [6]. Palop has showed that, the convex hull in the presence of
highway is composed of convex polygons(clusters) with segments of highway
connecting all the components. According to the definition of clusters, the
shortest time-path of any two points which belongs to different clusters must
use the highway. Therefore, we can comprehend the degree of convenience in the
transportation network from the point density of each clusters.

Palop [6] provided a $\Theta({n^{2}})$ time algorithm for constructing the
convex hull in the presence of a highway by enumerating the shortest time-path
between two points. Then, Yu and Lee [7] studied the problem and provided an
$O(n\log{n})$ approach based on incremental point insertions. However, the
algorithm which they proposed does not return the correct answer in all
circumstances. Some critical cases which make the problem more tough were
overlooked. After that, Aloupis et al. [3] proposed the algorithm that takes
$O(n\log^{2}{n})$ time for $L_{2}$-metric and takes $O(n\log{n})$ time for
$L_{1}$-metric. They solved the cases which Yu and Lee [7] overlooked. Dai et
al. [4] provide the $O(n\log{n})$ algorithm for $L_{p}$-metric, where 1 $\leq
p\leq\infty$, and they reduce the cluster-merging step which was proposed by
Aloupis et al. [3] to a geometric query.

Our focus and contribution

We provide the algorithm for computing time-convex hull with two orthogonal
highways in two different distance metrics. First, we provide the algorithm
for $L_{1}$-metric with arbitrary highway speed and compute it in
$O(n\log{n})$ time. In the algorithm which is given by Aloupis et al. [3],
they proposed the approach to constructing the time convex hull with one
highway. Considering that there are two orthogonal highways in our model, we
divide the input point set into two parts and use the approach in each part.
However, after completing this work, the clusters may need to be merged
between two parts. Therefore, we use the approach given by Aloupis et al. [3]
as a subroutine in our algorithm and apply the data structure proposed by
Mitchell [2] to merge the clusters between two parts. All together the above
processes generate our $O(n\log{n})$-algorithm for $L_{1}$-metric.

Second, we provide the $O(n\log{n})$-algorithm for the special case in
$L_{2}$-metric where the highway speed is infinite. Our
$O(n\log{n})$-algorithm for $L_{2}$-metric with infinite highway speed include
the following steps: Like what we do in $L_{1}$-metric, we divide the input
point set into two parts and construct clusters with the algorithm proposed by
Dai et al. [4] in each part. Dai et al. use the symmetric property of cluster-
merging condition and reduce the time-convex hull problem to the geometric
query. Thus, the data structure proposed by Mitchell [2] could be used to
answer this particular geometric problem. Finally, after clusters are
constructed, we use the ray-shooting method to check if any point should be
merged with other cluster.

##  2 Notation and definition

In this section, we will present some definitions that are useful for the
following sections.

######  Definition 1 ($L_{p}$-metric).

for any two points a($a_{1}$,$a_{2}$,…,$a_{n}$), b($b_{1}$,$b_{2}$,…,$b_{n}$)
under $L_{p}$-metric, where p $\in$ $Z^{+}$, their distance is defined as
$\sqrt[p]{\sum_{i=1}^{n}|a_{i}-b_{i}|^{p}}$.

When the metric are different, the distance of two points will also be
different. Therefore, when we are solving the problems about distance, it’s
important to make sure that which metric it is.

######  Definition 2 (Highway).

The travelling speed $V_{H}$ on a highway _H_ in $\mathbb{R}^{2}$ is faster
than 1, while the travelling speed without highways is 1. In this paper, there
are two highways intersect perpendicularly.

Without loss of generality, we position highways as x-axis and y-axis, which
are denoted $H_{x}$ and $H_{y}$. Furthermore, because the properties of every
quadrants are the same, we could concern only the first quadrant.

######  Definition 3 (Side).

Split the space into two pieces by the function$:x=y$. The one closer to
$H_{x}$ is called $Side-H_{x}$, and the one closer to $H_{y}$ is called $Side-
H_{y}$.

Figure 1: Sides

With highways, the traffic time between points may less than not using
highways. To find the fastest path, we should check that how much time it
takes instead of how far it is. In other word, the measure of a path is not
length but time, which is called time distance.

######  Definition 4 (Time distance).

For any two points p and q, their time distance is the travelling time that
from one point to the other one. The time distance of p, q is denoted d(p, q).

For any two points $p$ and $q$, let STP($p$,$q$) be the set of their shortest
time-paths, which may either use highway or not. If STP(p,q) $\cap$ $H$
$\neq\varnothing$, then the shortest time-path of p,q use highway.

However, the shortest time-path of two points under $L_{1}$-metric is not
unique. Thus, we define the shortest time-path between any two points to be
the path closest to the highway. In other word, the shortest time-path in
$L_{1}$-metric would be ”L shape”(See Fig. 2).

Figure 2: Shortest path under $L_{1}$-metric is L shape

######  Definition 5 (Shortest time-path in $L_{1}$-metric).

Any two points not using highway will choose the path which is the closest to
the highway.

Convex hull and Time-convex hull : In general definition, the convex hull of a
point set Q includes all the shortest paths of any pair in the point set Q. In
our model, considering time distance, a point set Q is said to be time-convex
if it contains all shortest time-paths of every pairs in Q.

######  Definition 6 (Time-convex hull).

The time-convex hull of a point set P, denoted TCH(P), is a minimum time-
convex set of any pairs in P. In other word, for any two points
$p_{1},p_{2}\in P$, STP($p_{1},p_{2}$) would located in TCH(P).

The time-convex hull is composed of two parts : two orthogonal straight-line
highways, and the set of convex connected components which is denoted by
clusters. To be brief, the polyhedrons of the time-convex hull of the point
set Q.

######  Definition 7 (Cluster).

For a point set P, clusters are defined to be the connected components of
TCH(P) $\backslash$ P.

Figure 3: Walking regions under $L_{1}$-metric

##  3 Walking Region

For any two points p, q, if the shortest time-path of p, q not use highway, or
we can say that, q lies in the walking region of p.

######  Definition 8 (Walking Region).

The walking region of a point p, denoted WR(p), is the set of points q such
that STP(p, q) does not use highway $H$.$\\{q\in\mathbb{R}^{2}:|pq|\leq
STP(p,q)\cap H\neq\varnothing\\}$

In the research of Aloupis et al. [3], they proposed the boundary of walking
region of points with one highway. According to definition 8, we know that the
walking region boundary is yielded by comparing the shortest path using
highway with the shortest path without highway. In our model, because there
are two orthogonal highways, the point $p$ can enter from $H_{x}$ or $H_{y}$
then out of $H_{x}$ or $H_{y}$. Thus, there are 4 kinds of the shortest paths
using highway (denoted highway path). We focus on first quadrant, we consider
only the points on $Side-H_{x}$ since the walking regions of the points on
$Side-H_{y}$ are symmetric with respect to $x=y$. For any point $p$ $\epsilon$
S, let $p^{\prime}_{x}$ be its orthogonal projection onto $H_{x}$,
$p^{\prime}_{y}$ be its orthogonal projection onto $H_{y}$, and the
intersection point of two highways $O$. The shortest paths between two points
$p$ and $q$ consists of either:

  1. -

The $L_{1}$ distance of $p$ and $q$.

  2. -

The horizontal segment $p^{\prime}_{x}$ $q^{\prime}_{x}$ and the vertical
segments $pp^{\prime}_{x}$ and $qq^{\prime}_{x}$.

  3. -

The horizontal segments $Op^{\prime}_{x}$ and $qq^{\prime}_{y}$ and the
vertical segments $pp^{\prime}_{x}$ and $Oq^{\prime}_{y}$.

  4. -

The horizontal segments $pp^{\prime}_{y}$ and $qq^{\prime}_{y}$ and the
vertical segment $p^{\prime}_{y}$ $q^{\prime}_{y}$.

  5. -

The horizontal segments $pp^{\prime}_{y}$ and $Oq^{\prime}_{y}$ and the
vertical segments $Op^{\prime}_{y}$ and $qq^{\prime}_{x}$.

The walking region of $a$ is the set $\\{b\in\mathbb{R}^{2}$ : $L_{1}$
distance of a and b $\leq$ every kinds of highway paths$\\}$.

######  Property 1 (Walking Region in $L_{1}$).

(See [3], [6]) For any point q = ($x_{q}$, $y_{q}$) with $x_{q},y_{q}\geq 0$ ,
$x_{q}\geq y_{q}$ , we have the following properties :

In the $L_{1}$-metric, there are 3 kinds of shape (See figure 3) related to
the x-coordinate and y-coordinate of $q$. The walking region of the point $q$
is the intersection of four regions :

  1. 1.

two segments with slope $\dfrac{(1-1/V_{H})}{2}$ and $-\dfrac{(1-1/V_{H})}{2}$
intersect at $(x_{q},0)$ and connect the half-line at horizontal line through
$q$.

  2. 2.

two segments with slope $\dfrac{(1-1/V_{H})}{2}$ and $-\dfrac{(1-1/V_{H})}{2}$
intersect at $(x_{q},\dfrac{(x_{q}-y_{q})}{2}+\dfrac{(x_{q}+y_{q})}{2V_{H}})$
and connect the half-line at horizontal line through $q$.

  3. 3.

two segments with slope $\dfrac{2}{(1-1/V_{H})}$ and $-\dfrac{2}{(1-1/V_{H})}$
which meet at $(0,y_{q})$ and join the half-line at vertical line through $q$.

  4. 4.

two segments with slope $\dfrac{2}{(1-1/V_{H})}$ and $-\dfrac{2}{(1-1/V_{H})}$
which meet at $((x_{q}-y_{q})/2+(y_{q}-x_{q})/2V_{H},y_{q})$ and join the
half-line at vertical line through $q$.

###### Proof.

For any point $p$, the 4 kinds of regions are the boundary of the set
$\\{q\in\mathbb{R}^{2}:|pq|\leq$ 4 kinds of highway path $\\}$. For example,
the first region is the set
$\\{q\in\mathbb{R}^{2}:|pq|\leq|pp_{x}^{\prime}|+|p_{x}^{\prime}q_{x}^{\prime}|/v+|qq_{x}^{\prime}|\\}$.
In other word, for any point $q$ in this region, the shortest path between $p$
and $q$ which does not use the highway is faster than using this highway path.
Therefore, for the point $q$ which is in the intersection of this four
regions, the shortest time-path between $p$ and $q$ do not use the highway.

∎

######  Property 2 (Walking region in $L_{2}$).

(See [4], [6]) For any point q = ($x_{q}$, $y_{q}$) with $x_{q},y_{q}\geq 0$ ,
$x_{q}\geq y_{q}$ , we have the following properties :

In the $L_{2}$-metric with infinite highway speed, the boundary of WR($p$) is
the intersection of two regions :

  1. 1.

The first region is characterized by the following two parabolas :
(a) _right discriminating parabola_ , which is the curve satisfying

$\displaystyle\begin{cases}x\geq x_{q}+y_{q}\tan\alpha,\quad\text{and}\\\
\sqrt{{{\left(x-x_{q}\right)}}^{2}+{{\left(y-y_{q}\right)}}^{2}}=y_{q}\sec\alpha+y\sec\alpha\end{cases}$

(b) The _left discriminating parabola_ which is symmetric to the right
discriminating parabola with respect to the line $x=x_{q}$.

  2. 2.

The second region is characterized by the following two parabolas :
(a) _right discriminating parabola_ , which is the curve satisfying

$\displaystyle\begin{cases}y\geq y_{q}-x_{q}\tan\alpha,\quad\text{and}\\\
\sqrt{{{\left(x-x_{q}\right)}}^{2}+{{\left(y-y_{q}\right)}}^{2}}=y_{q}\sec\alpha+x\sec\alpha\end{cases}$

(b) The _left discriminating parabola_ which is symmetric to the right
discriminating parabola with respect to the line $x=x_{q}$.

Figure 4: Walking regions under $L_{2}$-metric with infinite $V_{H}$

###### Proof.

It is similar to the case in $L_{1}$-metric. In $L_{2}$-metric, the shortest
path of the point in $Side-H_{x}$ always enter the highway $H_{x}$ because of
the infinite highway speed. So, there are just 2 kinds of highway paths and
regions.

∎

##  4 Optimal Construction in $L_{1}$-metric

In our model, there exist two orthogonal highways and a point set. The two
orthogonal highways could be regard as x-axis and y-axis.

Image that there is another line: $x=y$ in the model. By $x=y$, the point set
could be separated into two part, $x<y$ and $x\geq y$, which is the same to
definition of $side$(definition 3). Thus, each point can be assigned to one
side.

According to the definition 3, we can infer that if two points on the same
side using highway, they must use the highway on their side. It’s easy to
prove the correctness since the closet highway of the two points are both the
one on their side. Therefore, at most one highway would be used by these two
points.

######  Lemma 1.

Any two points on the same side use at most one highway.

###### Proof.

Assume there are two point p, q on side-$H_{k}$ (k can be x or y). Because p
and q are on side-$H_{k}$, the closet highway to them are both $H_{k}$. So, if
p to q using highway, it need to ”enter $H_{k}$, leave $H_{k}$”, which use
only one highway $H_{k}$. ∎

By lemma 1, for points on the same side, at most one highway would be used,
which is the same to the research of previous works [3, 4]. By previous works,
the time-convex hull for a given set S of n points in $L_{p}$-metric can be
computed in $O(n\log{n})$ time using $O(n)$ space, where $1\leq p\leq\infty$.
Consequently, clusters could also be constructed in O($n\log{n}$).

######  Corollary 2.

[3, 4] For a point set $S_{k}$ on $Side-H_{k}$, clusters could be constructed
in O($n\log{n}$).

For a point set S, we separate all points into two sides. Points on $Side-
H_{x}$ are sorted by their x-coordinates, and points on $Side-H_{y}$ are
sorted by their y-coordinates. By lemma 1 and corollary 2, we could construct
clusters on each side.

However, the walking regions of clusters we constructed on one side may
contain some points on the other side, which means that we may need to merge
clusters on different sides.

To merge the clusters on different sides, we record the boundary of walking
region of each cluster. Take the points on $Side-H_{y}$ for example, if any
point $p$ on $Side-H_{y}$ lies inside the walking region of any cluster
$C_{X}$ on $Side-H_{x}$, we would mark $C_{X}$ and the cluster $C_{Y}$ that
$p$ belongs to. The marked clusters would be merged into a new cluster in
subsequent steps.

After all points on $Side-H_{y}$ have been checked, we execute the same
process to $Side-H_{x}$ and mark the clusters we found. Finally, these marked
clusters would be merged into a new cluster. The cluster merging of different
sides is called side inclusion.

Figure 5: Every marked clusters are located at bottom left of
$\overline{C_{t}C_{r}}$

######  Lemma 3 (merge approach).

Let $C_{t}$ be the topmost cluster on $Side-H_{y}$ and $C_{r}$ be the
rightmost cluster on $Side-H_{x}$ we marked. Merging $C_{t}$ and $C_{r}$ will
also merge every clusters on the left of $C_{r}$ or below of $C_{t}$.

###### Proof.

Let $P_{t}$ be a point of $C_{t}$ and $P_{r}$ be a point of $C_{r}$. $P_{t}$
and $P_{r}$ lie in the walking region of each other. Denote $s$ to be the
shortest time-path between $P_{t}$ and $P_{r}$. Since $P_{t}$ and $P_{r}$ lie
in the walking region of each other, $s$ doesn’t use highway. Suppose that $s$
intersects another cluster at some point $x$. Because of the fact that a
subpath of a shortest path is also a shortest path, neither the path
$\overline{P_{t}x}$ nor the path $\overline{P_{r}x}$ use the highway. Thus,
$x$ and one of $P_{r}$ or $P_{t}$ must be in the same cluster before merging,
which is a contradiction to the assumption. ∎

By lemma 3, the only marked clusters which need to be merged are the topmost
cluster $C_{t}$ and the rightmost cluster $C_{r}$. Because merging $C_{t}$ and
$C_{r}$ will also merge every clusters on the bottom-left of them, the new
cluster after merging will contain all the other points before $C_{t}$ and
$C_{r}$. Thus, all marked clusters have been merged and no more clusters would
be merged again. We could end the side inclusion and construct the time-convex
hull.

Although the structure of our algorithm has been introduced, we haven’t
explained how to find the clusters need to be marked.

Our algorithm is based on the research that was proposed by Aloupis et al [3].
In their research, construct a time-convex hull with one highway in the
$L_{1}$-metric takes only $O(n\log{n})$. Therefore, by corollary 2, we could
construct clusters on each side by the method of Aloupis et al in
$O(n\log{n})$.

Point inclusion is an approach to construct clusters with one highway, which
was also proposed by Aloupis et al [3]. Take $Side-H_{x}$ for example, we
would sort the point set $S_{x}$ by their x-coordinates first, and check the
walking region of each point one by one. The walking regions are saved as
linked lists, which record the boundaries of the walking region for each
point. If a new point $P_{i}$ lies in the walking region of $P_{i-k}$, then
all points between $P_{i-k}$ and $P_{i}$ would be merged into a new cluster.
After solving $P_{i}$, we will turns to do point inclusion to $P_{i+1}$, until
every points in $S_{x}$ are solved.

The algorithm saves the boundaries of walking regions when constructing
clusters, so we can check if any points on the other side lie on the walking
region at the same time.

######  Definition 9 (Segment-dragging query).

The segment-dragging query, denoted Q(L). Q(L) ask that, for any line segment
L with finite slope and a point set P, if P$\cap L^{+}$ is empty or not, where
$L^{+}$ is the half plane to the right of L or above L.

We call the query searching the half plane to the right of L segment
horizontal-dragging query, while searching the half plane above L is called
segment vertical-dragging query

######  Lemma 4.

(Chazelle [1] and Mitchell [2]) Segment-dragging query takes O($n\log{n}$)
constructed time, O($n$) space, O($\log{n}$) query time.

By property 1, for the incoming point $p_{i}$ on $Side-H_{x}$, its left
boundaries of walking region consist of at most three segments on $Side-H_{y}$
(See fig. 3), while the right boundary consist only one vertical segment on
$Side-H_{y}$. Therefore, we extend the right boundary to a vertical line $R$,
and invoke the segment horizontal-dragging query for each left boundaries to
$R$. If the query return yes, it means that the cluster of $p_{i}$ must be
merged with some clusters on the other side, so the cluster $p_{i}$ belongs to
would be marked.

######  Lemma 5.

Each point evokes at most 3 segment-dragging queries.

However, checking points is not enough. As fig. 6, the cluster that contains
$p_{1}$ and $p_{2}$ should also contain $p_{3}$, but $p_{3}$ is neither in the
walking region of $p_{1}$ or $p_{2}$. The cause of the problem is that the
walking region of a cluster includes not only the walking regions of its
convex vertices, but also the walking regions of the line segments that
connect the convex vertices.

Figure 6: Edge inclusion

To deal with the problem, we need to check whether the walking region of the
line segments(gray area in fig. 6) causes side inclusion, which is called edge
inclusion. The edge of a cluster would only be formed when clusters are
merged. Whenever a new edge is formed, the segment-dragging query would be
invoked to check if the walking region of the edge contains any points on the
other side. If the query return yes, mark the cluster which the edge belongs
to.

After solving all the points on $Side-H_{x}$, we perform the same process for
the points on $Side-H_{y}$.

For clusters we marked above, we pick out the topmost cluster $C_{t}$ and the
rightmost cluster $C_{r}$. By lemma 3, merging $C_{t}$ and $C_{r}$ will also
merge all the other clusters before them. Therefore, we can get the final
clusters after merging $C_{t}$ and $C_{r}$.

After we obtain the final clusters, the time-convex hull could be constructed
by linear scan in O($n$). The linear scan start from the last point
$P_{x_{n}}$ on $Side-H_{x}$ to the fist point $P_{x_{1}}$, then turn to $Side-
H_{y}$ from the first point $P_{y_{1}}$ to the last point $P_{y_{n}}$.

For clusters using only one highway, details steps have been record in the
work of Yu and Lee [7] and Aloupis et al [3]. By lemma 3, after side
inclusion, there is no more than one cluster using two highways, and the
cluster must be the first cluster on both $Side-H_{x}$ and $Side-H_{y}$.
Therefore, we can scan all points in the cluster linearly, and the details
would be the same to the method of constructing clusters using only one
highway.

######  Theorem 6.

The time-convex hull with two orthogonal highways under $L_{1}$-metric can be
computed in $O(n\log{n})$ time.

###### Proof.

By corollary 2, clusters on each sides could be constructed in $O(n\log{n})$
times.

For a point set contains n points, by lemma 5, each point would evoke at most
3 segment-dragging queries. Thus, the segment-dragging query would be evoked
at most $O(n)$ times for n points. Since there are at most n clusters, and
each merging create only one newly-formed edge, the segment-dragging query
would be evoked at most $O(n)$ times for n edges. By lemma 4, segment-dragging
query takes $O(\log{n})$ times. To sum up, the side inclusion tests totally
take O($n\log{n}$) times.

In the last step, it takes $O(n)$ times to construct the time-convex hull by
linear scan.

Therefore, the time-convex hull with two orthogonal highways under
$L_{1}$-metric can be computed in $O(n\log{n})$ time. ∎

##  5 Optimal Construction in $L_{2}$-metric with infinite highway speed

In this section, we just care about the case of infinite highway speed. By
lemma 3, our approach is to find the topmost marked cluster $C_{t}$ and the
rightmost marked cluster $C_{r}$ as well. For this goal, we need to construct
clusters first and check where $C_{t}$ and $C_{r}$ are. Like what we do under
$L_{1}$-metric, we process the point inclusion to every points. However, due
to the different shape of walking regions between $L_{1}$ and $L_{2}$ metric,
edge inclusions may also be happened during point inclusion. The method of
constructing clusters with one highway under $L_{2}$-metric was proposed by
Dai [4], which takes $O(n\log{n})$ time.

(a) edge inclusion on the same side (b) new-formed edge e

(c) edge inclusion on the other side

Figure 7: edge inclusion

The edge inclusion will be happened when the clusters are merged. When the
clusters are merged, a new hull edge will be created (See Fig. 7(b)), and we
exploit segment vertical-dragging query for this test. The approach we used is
referred to the work of Dai [4]. Let E be the set of newly-formed edges. We
randomly pick one edge $e$ in E to check if there are any points that lie in
this area $WR(e)$, which means that the clusters need to be merged. Otherwise
we check another edge in E until E is empty. This step just check the clusters
on the same side.

On the other side, edge inclusion may also occur(See Fig. 7(c)). Thus the
walking region of edge e on the other side also need to be checked. We invoke
segment horizontal-dragging query again to check if $WR(e)$ on the other side
contain any points. If the query return yes, this cluster will be marked.

After the edge inclusion test of incoming point $p_{i}$, we need to maintain
the outermost boundary of clusters on the other side, i.e. if $p_{i}$ is on
$Side-H_{x}$, we would maintain the outermost boundaries of clusters on $Side-
H_{y}$ (See Fig.8) . This process will be done in both side. The boundary will
be stored as linked-lists which consist of two points and a curve. Below we
describe how to maintain the boundary.

When a new point $q_{i}$ arrives, we will check the intersection between
$WR(q_{i})$ and $x=y$. Denoted these two points $b_{j}$ and $b_{k}$, where
$b_{j}$’s y-coordinate is less than $b_{k}$’s y-coordinate :
1\. If $b_{j}$’s and $b_{k}$’s y-coordinate are both larger than the tail of
linked-list $L_{k}$, we can update the linked-list directly.
2\. If $b_{j}$’s and $b_{k}$’s y-coordinate are both less than $L_{k}$, the
walking region will be covered and we can go next point $q_{i+1}$.
3\. After case 1 and 2, we check if the walking region of $q_{i}$ intersects
with the boundary which is represented by $L_{k}$.

If yes, update the linked list and go for next point $q_{i+1}$.

If no, $L_{k}$ will be covered and never be used, we can delete it and keeping
going to $L_{k-1}$

to check these three cases.

Figure 8: The boundary of walking region of points in Side-$H_{x}$

We construct the linked-list of points on $Side-H_{x}$ first. After the
boundary is constructed, ray shooting could be executed to compare each point
on $Side-H_{y}$ with the linked list which is made of walking regions from
$Side-H_{x}$. The ray shooting would start from the last point $P_{y_{n}}$ of
$Side-H_{y}$ and the tail of linked list $L_{k}$.

If $L_{k}$ is to the left of $P_{y_{n}}$, it means that $P_{y_{n}}$ lies in
the walking region of some clusters on $Side-H_{x}$. Therefore, we could mark
the cluster that $P_{y_{n}}$ belongs to and stop the ray shooting on $Side-
H_{y}$. Otherwise, when $L_{k}$ is not to the left of $P_{y_{n}}$ but to the
right of it, we could make sure that $P_{y_{n}}$ doesn’t lie in any walking
region of clusters on $Side-H_{x}$ for the fact that the linked list is
y-monotone. Thus we should search the next point $P_{y_{n-1}}$.

When the y-coordinate of $P_{y_{n}}$ is less than $L_{k}$, we traverse the
next curve $L_{k-1}$. Like the concept of the former, we would search next
point $P_{y_{n-1}}$ if the y-coordinate of $L_{k}$ is less than $P_{y_{n}}$.
The ray shooting will be executed continuously until all points on $Side-
H_{y}$ have been searched or all curves in the linked list have been
traversed.

After we have traversed every points, $C_{t}$ and $C_{r}$ could be found and
we can complete the final clusters after merging them. If there are no marked
cluster in either $Side-H_{x}$ or $Side-H_{y}$, it means that the cluster-
merging between different sides would not happen, which is the same to the
case of one highway that has been solved efficiently by Dai [4].

In the point inclusion test, it can be done in $O(n\log{n})$ by Dai [4].
Furthermore, in the edge inclusion test, every cluster-merging create one hull
edge at most and take $O(\log{n})$ in each test. Therefore, it takes
$O(n\log{n})$ in edge inclusion test. In the process of maintain the outermost
boundary, each point intersect at most two points and every nodes are just
traversed at most one time, so it takes $O(n)$ time in ray shooting test.
Thus, the time-convex hull with two orthogonal highways of infinite speed
under $L_{2}$-metric can be computed in $O(n\log{n})$ time.

######  Theorem 7.

The time-convex hull with two orthogonal highways of infinite speed under
$L_{2}$-metric can be computed in $O(n\log{n})$ time.

##  6 Conclusion

In this paper, we give an O($n\log{n}$) time algorithm for the time-convex
hull with two orthogonal highways under $L_{1}$-metric. For $L_{2}$-metric, we
provide O($n\log{n}$) time algorithm in the special case where the highway
speed is infinite. There are some extensions of this work, e.g.,
$L_{2}$-metric with general highway speed, $L_{p}$-metric where 1 $\leq
p\leq\infty$, or, with multiple highways.

## References

  * [1] Bernard Chazelle. An algorithm for segment-dragging and its implementation. Algorithmica volume 3, pages 205–221(1988)
  * [2] Joseph S. B. Mitchell. L 1 shortest paths among polygonal obstacles in the plane. Algorithmica volume 8, pages 55–88(1992)
  * [3] Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O’Rourke, Belén Palop. Highway hull revisited. Computational Geometry 43 (2010) 115–130.
  * [4] Bang-Sin Dai, Mong-Jen Kao, D.T.Lee. Optimal time-convex hull for a straight-line highway in $L_{p}$-metrics. Computational Geometry 53 (2016) 1–20
  * [5] F. Hurtado, B. Palop, V. Sacristán. Diagramas de Voronoi con distancias temporales (Spanish). Actas de los VIII Encuentros de Geometra Computacional, 1999, pp.279–288
  * [6] B. Palop. Algorithmic problems on proximity and location under metric constraints. Ph.D thesis, Universitat Politécnica de Catalunya, 2003.
  * [7] Teng-Kai Yu, D. T. Lee Time convex hull with a highway 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007).


# Multi-stage Jamming Attacks Detection using Deep Learning Combined with
Kernelized Support Vector Machine in 5G Cloud Radio Access Networks

Marouane Hachimi1, Georges Kaddoum1, Ghyslain Gagnon1 and Poulmanogo Illy1
1Electrical Engineering Department, École de technologie supérieure, Montréal,
Canada
Email<EMAIL_ADDRESS>
###### Abstract

In 5G networks, the Cloud Radio Access Network (C-RAN) is considered a
promising future architecture in terms of minimizing energy consumption and
allocating resources efficiently by providing real-time cloud infrastructures,
cooperative radio, and centralized data processing. Recently, given their
vulnerability to malicious attacks, the security of C-RAN networks has
attracted significant attention. Among various anomaly-based intrusion
detection techniques, the most promising one is the machine learning-based
intrusion detection as it learns without human assistance and adjusts actions
accordingly. In this direction, many solutions have been proposed, but they
show either low accuracy in terms of attack classification or they offer just
a single layer of attack detection. This research focuses on deploying a
multi-stage machine learning-based intrusion detection (ML-IDS) in 5G C-RAN
that can detect and classify four types of jamming attacks: constant jamming,
random jamming, deceptive jamming, and reactive jamming. This deployment
enhances security by minimizing the false negatives in C-RAN architectures.
The experimental evaluation of the proposed solution is carried out using WSN-
DS (Wireless Sensor Networks DataSet), which is a dedicated wireless dataset
for intrusion detection. The final classification accuracy of attacks is
94.51% with a 7.84% false negative rate.

###### Index Terms:

Cloud Radio Access Network, Jamming attacks, Machine Learning-based Intrusion
Detection System, Multilayer Perceptron, Support Vector Machine, Wireless
Sensor Networks DataSet.

##  I INTRODUCTION

In recent years, with the strong growth in the number of customers, the
consumption of data traffic from wireless terminals has drastically increased
[1-4]. Moreover, according to a study conducted by the ”Beijing Key Laboratory
of Network System Architecture and Convergence, China” on mobile Internet
penetration in the world from 2013 to 2019 [1], 48.8% of the world’s mobile
phones had access to the Internet in 2014. This figure reached 61.2% in 2018,
with an average annual increase of 8.3% in the number of mobile devices. In
this context, due to the shortage of spectrum and bandwidth, traditional RANs
are not able to meet the growing demands of mobile users. Cloud Radio Access
Network (C-RANs) architectures present a promising solution to potentially
increase the network flexibility and improve its performance, possibly
overcoming the problems of traditional RANs [3]. In fact, real-time cloud
infrastructures, cooperative radio, centralized data processing, and cloud
radio access networks are increasingly sought by mobile operators to meet the
requirements of end-users. Since IBM defined the concept of C-RAN in 2010,
this technology has attracted significant attention around the world. The
fifth generation of mobile technologies (5G) established C-RAN as its
architecture to support their new mobile services and communications [4].

A C-RAN network, which has a mesh topology, is composed of three main
components: Virtualized Base-Band Unit (BBU) pool, Remote Radio Head (RRH),
and a fronthaul network connecting the RRHs to the BBU pool. RRHs collect
wireless signals from all wireless devices and the fronthaul network sends
them to the BBU pool. Thanks to a Digital Signal Processor (DSP) controller in
the BBU pool, the C-RAN network can re-assign the fronthaul network to meet
the changing traffic needs of mobile devices [5].

Recently, because of their vulnerability to malicious attacks, the security of
C-RAN networks has drawn special attention and concern [6]. Due to the open
nature of wireless networks, both authorized and illegitimate users can access
the communication channel. Thus, C-RANs inherit all the attacks that can be
performed on wireless networks, including the most popular jamming attacks.
Due to their ability to easily disable radio channels that use strong high-
level security measures, jamming attacks represent the most serious security
threat in the wireless communication field. Several forms of this attack can
be used against C-RAN, namely constant jamming, random jamming, deceptive
jamming, and reactive jamming [7].

In this context, Intrusion Detection System (IDS) have been developed to
enhance the security of the network. Signature-based intrusion detection
(S-IDS) is a valuable technology which could protect C-RAN networks against
the known attacks. However, this method fails to identify new attacks [8]. On
the other hand, anomaly-based intrusion detection (A-IDS) can resolve this
limitation by detecting unknown or novel attacks. Among various anomaly-based
intrusion detection techniques, machine learning-based intrusion detection
(ML-IDS) shows great potential. In this direction, different solutions have
been proposed to tackle security threats.

Syed et al. [9] proposed a new radio modulation network-based intrusion
detection system for jamming attacks named LIDS. They implemented two LIDS
algorithms based on the Kullback Leibler Divergence (KLD) and Hamming distance
(HD). The detection rates achieved are of 98% and 88%, respectively with a 5%
false positive rate. Imen et al. [10] designed an intrusion detection
mechanism to limit DoS attacks in Wireless Sensor Networks. They implemented
five machine learning algorithms to detect and classify DoS attacks. Oscar et
al. [11] presented a machine learning-based jamming detection approach capable
of detecting constant and reactive jammers under various scenarios in 802.11
networks. Yi et al. [12] presented a machine learning method for launching
jamming attacks in wireless communications and also introduced a defense
strategy. For vehicular ad hoc networks (VANETs). Dimitrios et al. [13]
presented a method for detecting and clustering radio frequency (RF) jamming
attacks based on the use of unsupervised machine learning. Thi et al. [14]
designed a machine learning based IDS to classify four DoS attacks in Wireless
Sensor Networks (WSN).

This work aims to deploy a new multi-stage ML-IDS with a double detection
check against jamming attacks which ensures a high attack detection accuracy.
Precisely, our main contributions are summarized as follows:

  * •

We propose a new ML-IDS concept based on supervised and deep learning for the
detection and classification of jamming attacks.

  * •

We enhance the security of C-RAN networks by deploying a high accuracy multi-
stage jamming attack detection mechanism.

  * •

We implement our final solution into the BBU pool without greatly affecting
the latency.

##  II Types Of Jammers And Intrusion Detection Systems

In this section we will go through the existing types of jammers then we will
justify the chosen detection method.

###  II-A Types Of Jammers

A jammer is an equipment that can disturb a node’s signal by increasing its
power spectral density (PSD). There are several types of jammers that may be
used against C-RAN networks, namely: constant jammer, random jammer, deceptive
jammer, and reactive jammer.

####  II-A1 Constant jammer

a constant jammer continuously produces radio signals completely random. They
do not follow any underlying MAC protocol and are only random bits.

####  II-A2 Random jammer

a random jammer works randomly in two states; sleep and jamming. During the
sleep state, it is idle and during the jamming state, it acts as a constant
jammer.

####  II-A3 Deceptive jammer

as deceptive jammer is a constant jammer that continuously transmits regular
packets. It is more difficult to detect because it transmits legitimate
packets instead of random bits.

####  II-A4 Reactive jammer

a reactive or intelligent jammer is activated when it detects a transmission
on the channel and starts sending illegitimate packets. If the channel is
inactive, it stays inactive and continues sensing the channel.

###  II-B The Chosen Detection Method

IDSs are strategically placed on a network to detect threats and monitor
network traffic. IDS uses network or host-based approaches to recognize
attacks by collecting data from network systems and sources and analyzing it
to identify potential threats.

As we can see in Figure 1, there are several intrusion detection methods, the
most popular being signature-based. Signature-based detection is governed by a
set of rules used to match models in network traffic. It detects well-known
attacks; however, it has a major drawback since it is incapable of identifying
new attacks. On the other hand, anomaly based-IDS detect unknown or novel
attacks. Anomaly-based IDS detect attacks that have not been dealt with
before.

Fig. 1: Hierarchical Classification of IDS [8].

Among the various anomaly based-IDS techniques such as Machine Learning based
IDS (ML-IDS), Knowledge Based IDS (K-IDS), Data Mining based IDS (DM-IDS),
Statistical Anomaly based IDS (SA-IDS), the most promising one is ML-IDS since
it is capable of gradually improving its performance by learning over time
while performing a given task.

##  III The Proposed System Model

This section presents the proposed system model by first exhibiting the
architecture deployed and then justifying the chosen implemented classifiers.

###  III-A The Deployment Architecture

The deployed architecture of the proposed ML-IDS in C-RAN architecture is
shown in Figure 2 with its mesh topology using Low Energy Aware Cluster
Hierarchy (LEACH) routing protocol. LEACH is an adaptive and self-organized
clustering protocol in WSNs that is characterized by its simplicity and low
energy. LEACH assumes that the base station (BS) is fixed and located far from
the sensor nodes. The main idea of the LEACH protocol is to arrange nodes into
clusters to distribute energy among all nodes in the network. In addition, in
each cluster there is a Cluster Head (CH) node that collects the data received
from the sensors in its cluster and transmits it to the BS. At the BSs we have
a number of antennas distributed geographically to provide higher coverage.

Each antenna is connected with a Remote Radio Head (RRH) through a coaxial
cable, and every RRH is connected to a Base Band Unit (BBU) pool via an
optical fiber which has a very low loss. The Fronthaul is the part between the
RRHs and the BBU pool which is the physical section while the part between the
BBU pool and the mobile core network (internet, cloud computing resources …)
is called Backhaul which is the virtual section of the network.

Fig. 2: Architecture for deploying the proposed ML-IDS in C-RAN environments.

The proposed ML-IDS collects mobile traffic flowing between the clusters and
the FrontHaul, and processes it with Multilayer Perceptron (MLP). Our model
classifies traffic into five classes, namely constant jamming, random jamming,
deceptive jamming, reactive jamming, and normal traffic. If classified as
normal by MLP, the traffic is processed again by a Kernelized Support Vector
Machine (KSVM). The motivation to add a KSVM after the MLP is to reduce the
false negatives that the MLP has created. In a false negative, the system
decides that the situation is normal while in reality there is an attack.

The ML-IDS is deployed into the virtualized BBU pool for several reasons.
First, the virtualized BBU pool contains all the functionalities of the C-RAN
network such as spectrum allocation, confidential user data, network slicing,
cloud services management, etc. Thus, the BBU pool controls the entire C-RAN
network. Second, the objective of a jamming attack is to add noise in the area
between clusters and BSs where the BBU pool is the only part of the C-RAN that
monitors this area. And finally, the BBU pool is the infrastructure that
contains enough resources to run such a detection engine without greatly
affecting the latency.

###  III-B The Implemented Classifiers

Two classifiers have been implemented in the BBU Pool to detect the
aforementioned four types of jamming attacks. Therefore, if an attack is
missed with the first classifier the second one will be able to detect it. The
first classifier is MLP which is a deep learning algorithm. MLP consists of a
system of interconnected neurons as shown in Figure 3, which is a model
representing a non-linear mapping between input and output vectors.

Fig. 3: A multilayer perceptron with several hidden layers [15].

MLP has been chosen because of the very large number of input vectors (we have
374661 vectors in our case) so the stochastic gradient drop is often the best
choice (especially for classification) in terms of speed, ability, and
control. MLP was chosen among all deep learning algorithms (CNN, RNN, LSTM,
DBM…) because of its flexibility which allows it to be applied to different
types of data.

The second algorithm implemented is the KSVM which is an efficient binary
classifier. Knowing that jamming attacks are not linearly separable in a low
dimension space, the KSVM handles such situations when using a kernel
function. This function maps the data in a different space where a linear
hyperplane can be used to split the attacks. The process is illustrated in
Figure 4. This is called the kernel trick as the kernel function transforms
the data into a higher dimensional feature space so that a linear separation
is possible.

Fig. 4: Non-linear classifier using Kernel trick [16].

The decision limit or so-called hyperplane separating the classes has
weighting coefficients given by the vector W, which we need to estimate. The
KSVM classifier tries to maximize the distance between this vector W and the
nearest points (support vectors) so that it becomes our constraint. This is
equivalent to minimizing the following equation:

$W(\alpha)=-\sum_{i=1}^{l}\alpha_{i}+\frac{1}{2}\sum_{i=1}^{l}\sum_{j=1}^{l}y_{i}y_{j}\alpha_{i}\alpha_{j}x_{i}x_{j}$

Subject to:

$\sum_{i=1}^{l}y_{i}\alpha_{i}=0$

Where l is the number of data points in our training data, y denote the
outputs of the data points, x is the feature vector in each training example,
and $\alpha$ is the Lagrangian constant.

##  IV WSN-DS Description

To obtain experimental results, the WSN-DS, which is a specialized dataset for
WSNs was used to classify attacks, which is a dedicated wireless dataset for
intrusion detection [9]. It contains exactly 374,661 simple connection
vectors, each of which includes 23 features and is labeled as normal or
attack. The specific types of attacks are grouped into different categories of
attacks, namely Constant jamming, Random jamming, Deceptive jamming, and
Reactive jamming, in addition to the normal case (without attack).

The WSN-DS contains 23 attributes (features) to help determine the state of
every node in the C-RAN network. Principal Component Analysis (PCA) is a
statistical technique primarily used for dimensionality reduction which
consists of selecting the attributes that contain the maximum amount of
information in the order of importance, to have a model that is easier to
interpret and that reduces the calculation time required. As we can see in
Figure 5, we were able to extract the most important features from the 23, and
these selected attributes are listed as follows:

  * •

Energy consumption: the amount of energy consumed in the previous round.

At first, each node generates an arbitrary number between 0 and 1, then a
threshold is computed T(n) using the formula below. If the chosen random
number is less than the threshold value, the node will become a Cluster Head
(CH).

$T(n)=\begin{cases}\frac{p}{1-p\times(r\bmod p^{-1})}&\forall n\in N\\\
0&\text{ otherwise }\end{cases}$

where p is the CH probability, N is the set of nodes that have not been a CH
in the last 1/p rounds, and r is the current round.

  * •

Is CH: A flag to distinguish whether the node is a CH (value 1) or a normal
node (value 0).

  * •

ADV CH send: the number of advertise CH broadcast messages sent to the nodes.

  * •

ADV SCH send: the number of advertise TDMA schedule broadcast messages sent to
the nodes.

  * •

Data sent to BS: the amount of packets of data transmitted to the RRH.

  * •

Distance CH to BS: the distance between the CH and the RRH.

  * •

Data received: the number of packets received from CHs.

  * •

ADV CH receives: the number of advertise CH messages received from CHs.

  * •

Join REQ receive: the number of join request messages received by the CHs from
the nodes.

  * •

Time: the current simulation time of the node.

Fig. 5: Top 10 most important features in WSN-DS.

The WSN-DS was separated into 70% training data and 30% testing data. Table I
shows the data separation.

TABLE I: Number of records used in training and testing datasets. Class | Number of records used in dataset
---|---
Training set (70%) | Testing set (30%)
Normal | 238103 | 101963
Constant jamming | 10233 | 4363
Random jamming | 6960 | 3089
Deceptive jamming | 4650 | 1988
Reactive jamming | 2316 | 996
Sum | 262262 | 112399

##  V Experimentation results

The results obtained from the dataset are presented in this section. All the
tasks are performed using the Python programming language and Scikit-learn
library. Experiments were conducted on an Intel(R) Xeon(R) CPU E3-1225 v5,
16.00 GB RAM with Windows 10 Enterprise 2016 LTSB 64-bit Operating System, and
x64-Based Processor. Table II show the classification accuracy obtained for
each stage.

TABLE II: Classification accuracy for each stage. Method used | Accuracy
---|---
MLP (first stage) | 81,73 %
MLP + KSVM (second stage) | 94,51 %

To evaluate the proposed approach, We compared our multi-stage model with
another work that used just MLP [10] applied to the same dataset to confirm
that our approach is the most appropriate. Table III illustrates that our
model can provide better accuracy of attacks classification than just the MLP
model.

TABLE III: Global and classes accuracies. Model | Accuracy of attacks classification |  Global Acc
---|---|---
Rando. | Const. | React. | Decept. | Norm.
MLP [10] | 92.8% | 75.6% | 99.4% | 92.2% | 99.8% | 91.9%
| MLP +
---
KSVM
95.3% | 82.9% | 99.6% | 94.7% | 100% | 94.5%

Moreover, Receiver Operating Characteristic (ROC) curve is used to visualise
the performance of the classifiers. It gives us the trade-off between the True
Positive Rate (TPR) and the False Positive Rate (FPR) at different
classification thresholds.

$TPR=\frac{TP}{TP+FN}$ $FPR=\frac{FP}{TN+FP}$

As shown in the equations above, TPR is the proportion of observations that
are correctly predicted to be positive. However, FPR is the proportion of
observations that are incorrectly predicted to be positive. Figure 6 shows the
ROC curve for each model.

Fig. 6: Receiver operating characteristic curve.

These results showed that the application of MLP and KSVM to WSN-DS dataset
provides a higher classification accuracy and better security in C-RAN
architectures.

##  VI Conclusion and Future Work

In the present paper, we proposed an efficient multi-stage solution that can
detect four different types of jamming attacks in Cloud Radio Access Networks
(C-RAN) by deploying a new machine learning-based intrusion detection system
(ML-IDS). We have implemented a multi-stage detection based on supervised and
deep learning classifiers to reduce the number of attacks missed and to
decrease the system’s false negatives and false positives rates. The proposed
solution guarantees a high detection and classification accuracy that can
reach up to 94%. In the future, we aim to create our wireless dataset for
intrusion detection to include other types of jamming attacks such as shot
noise-based intelligent jamming. In addition, several attacks that target
C-RAN architectures like eavesdropping attacks, primary user emulation
attacks, and impersonation attacks will be included.

## References

  * [1] J. Yang, Y. Qiao, X. Zhang, H. He, F. Liu and G. Cheng, ”Characterizing User Behavior in Mobile Internet,” in IEEE Transactions on Emerging Topics in Computing, vol. 3, no. 1, pp. 95-106, March 2015.
  * [2] C. I, J. Huang, R. Duan, C. Cui, J. Jiang and L. Li, ”Recent Progress on C-RAN Centralization and Cloudification,” in IEEE Access, vol. 2, pp. 1030-1039, 2014.
  * [3] M. Hadzialic, B. Dosenovic, M. Dzaferagic and J. Musovic, ”Cloud-RAN: Innovative radio access network architecture,” Proceedings ELMAR-2013, Zadar, 2013, pp. 115-120.
  * [4] S. Buzzi, C. I, T. E. Klein, H. V. Poor, C. Yang and A. Zappone, ”A Survey of Energy-Efficient Techniques for 5G Networks and Challenges Ahead,” in IEEE Journal on Selected Areas in Communications, vol. 34, no. 4, pp. 697-709, April 2016.
  * [5] K. Boulos, M. El Helou and S. Lahoud, ”RRH clustering in cloud radio access networks,” 2015 International Conference on Applied Research in Computer Science and Engineering (ICAR), Beirut, 2015, pp. 1-6.
  * [6] F. Tian, P. Zhang and Z. Yan, ”A Survey on C-RAN Security,” in IEEE Access, vol. 5, pp. 13372-13386, 2017.
  * [7] A. Mpitziopoulos, D. Gavalas, C. Konstantopoulos and G. Pantziou, ”A survey on jamming attacks and countermeasures in WSNs,” in IEEE Communications Surveys anf Tutorials, vol. 11, no. 4, pp. 42-56, Fourth Quarter 2009.
  * [8] Veeramreddy, Jyothsna, Prasad, V. Prasad, Koneti. (2011). A Review of Anomaly based Intrusion Detection Systems. International Journal of Computer Applications. 28. 26-35.
  * [9] S. M. Danish, A. Nasir, H. K. Qureshi, A. B. Ashfaq, S. Mumtaz and J. Rodriguez, ”Network Intrusion Detection System for Jamming Attack in LoRaWAN Join Procedure,” 2018 IEEE International Conference on Communications (ICC), Kansas City, MO, 2018.
  * [10] Iman Almomani, Bassam Al-Kasasbeh, and Mousa AL-Akhras, “WSN-DS: A Dataset for Intrusion Detection Systems in Wireless Sensor Networks,” Journal of Sensors, 16 pages, 2016.
  * [11] O. Puñal, I. Aktaş, C. Schnelke, G. Abidin, K. Wehrle and J. Gross, ”Machine learning-based jamming detection for IEEE 802.11: Design and experimental evaluation,” Proceeding of IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks 2014, Sydney, NSW, 2014, pp. 1-10.
  * [12] Y. Shi, Y. E. Sagduyu, and J. H. Li, ”Adversarial Deep Learning for Cognitive Radio Security: Jamming Attack and Defense Strategies,” 2018 IEEE International Conference on Communications Workshops (ICC Workshops), Kansas City, MO, 2018, pp. 1-6.
  * [13] D. Karagiannis, A. Argyriou, ”Jamming attack detection in a pair of RF communicating vehicles using unsupervised machine learning,” Vehicular Communications, Volume 13, 2018, Pages 56-63.
  * [14] T. Le, T. Park, D. Cho and H. Kim, ”An Effective Classification for DoS Attacks in Wireless Sensor Networks,” 2018 Tenth International Conference on Ubiquitous and Future Networks (ICUFN), Prague, 2018, pp. 689-692.
  * [15] M.WGardnera, S.RDorlinga ”Artificial neural networks (the multilayer perceptron)—a review of applications in the atmospheric sciences” in Atmospheric Environment , IEEE, 1 August 1998, Pages 2627-2636.
  * [16] José Luis Rojo-Álvarez; Manel Martínez-Ramón; Jordi Muñoz-Marí; Gustau Camps-Valls, ”Support Vector Machine and Kernel Classification Algorithms,” in Digital Signal Processing with Kernel Methods , , IEEE, 2018, pp.433-502.
  * [17] Illy, P., Kaddoum, G., Moreira, C.M., Kaur, K. Garg, S. (2019). Securing Fog-to-Things Environment Using Intrusion Detection System Based On Ensemble Learning. ArXiv, abs/1901.10933.