# Border Effects on Connectivity for Randomly Oriented Directional Antenna Networks

Amitabha Bagchi, Federico Corò, Cristina Pinotti, Vlady Ravelomanana

► To cite this version:

Amitabha Bagchi, Federico Corò, Cristina Pinotti, Vlady Ravelomanana. Border Effects on Connectivity for Randomly Oriented Directional Antenna Networks. 17th Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net 2018), Jun 2018, Capri Island, Italy. pp.79-86. hal-01832533

HAL Id: hal-01832533

https://inria.hal.science/hal-01832533

Submitted on 8 Jul 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Border Effects on Connectivity for Randomly Oriented Directional Antenna Networks

Amitabha Bagchi*, Federico Corò†, Cristina M. Pinotti‡ and Vlady Ravelomanana§

*Department of Computer Science and Engineering, IIT Delhi, India

†Gran Sasso Science Institute (GSSI), L'Aquila, Italy

‡Department of Computer Science and Mathematics, University of Perugia, Italy

§Department of Computer Science, University of Denis Diderot, Paris, France

**Abstract**—We study the possibility of creating a fully connected ad-hoc network with bidirectional links between nodes equipped with randomly oriented directional antennas deployed in a circular planar region. The major contribution of our paper is to show that in the directional antenna setting there are always isolated nodes, no matter how high the transmission power of the antennas. We observe, however, that the isolated nodes are confined to a narrow annulus near the boundary of the region. We propose two solutions to achieve full connectivity in the directional setting: *T-core* that reorients isolated antennas towards the centre of the circular region, and *Greedy* that simply flips the antenna orientation. We show that the former heuristic, which needs information of the location of the centre of the region, achieves full connectivity with high probability and that, even the latter, which requires no extra information, is able to eliminate most of the isolation.

## 1. Introduction

Directionality of antennas focuses transmission power in a particular direction. It is well known that the millimeter-wave cellular wireless networks need to be significantly redesigned to fully achieve the requirement of highly directional and adaptive transmissions [1], [2], [3]. So, moving beyond point-to-point communication, it is crucial to understand how a *connected* network can be spontaneously formed by a set of nodes all equipped with *directional* antennas. In this paper, we specifically concern ourselves with connected networks that have *bidirectional* links since such networks can more easily perform complex coordination tasks (target tracking, event detection, routing, fault recovery etc) that can be very valuable in several settings. This paper presents an exploratory attempt to study the possibility of building ad-hoc connected mesh networks with bidirectional links using directional antennas.

A natural question that arises when we consider the possibility of forming such a network in directional antenna

setting is: if each node is assumed to be randomly positioned in a two-dimensional field, and if it orients its antenna along a randomly chosen direction, what is the probability that the network is connected? A similar question has been posed for omnidirectional networks. The seminal work of Gupta and Kumar [4] employs theory from the area of continuum percolation and random graphs to provide a critical transmission range to achieve connectivity assurances as $n$ grows to infinity for omnidirectional networks.

The main contribution of this paper is to show that in our directional antenna model, the *Directional Antenna Random Geometric Graph* (DARGG), it is not possible to achieve connectivity just by fixing a critical radius. We show that, in DARGG, nodes that are disconnected from the network exist with high probability if the radius of connectivity is taken to guarantee the same number of neighbours as the Gupta-Kumar radius guarantees in omnidirectional random graphs. We also give via simulations evidence that DARGG remains disconnected even at higher radii despite the fact that higher radii bring the guarantee of a higher number of neighbours.

However, we present an interesting finding regarding the disconnectedness of our DARGG: the disconnected nodes are confined to a narrow annulus at the border of the region of interest. This conclusion is important in two ways. Firstly, it tells us that the border effects that Gupta and Kumar handled cursorily because they did not affect their main result are crucial in the case of DARGG. Secondly, and more constructively, it gives us an idea on how to rectify the lack of connectedness in DARGG. We consider two simple decentralized methods for connecting the disconnected nodes to the network. The first, *T-core*, deterministically reorientats disconnected towards the center. This method eliminates all disconnections but requires the node to know where the center of the field is. The second method, *Greedy*, randomly flips the orientation of an isolated node by $\pi$ radians. This method does not require any location information but is still able to reduce the extent of disconnection significantly without completely eliminating it.

**Paper organisation.** We first discuss related work, with a specific discussion on the pitfalls of the Gupta-Kumar

<footnote>The work has been partially supported by GEO-SAFE (H2020-691161), by "RISE" Fondazione CR-PG, code 2016.0104.021, by the "GNCS - INdAM".</footnote>
approach in the directional case (Section 2). In Section 3, we
describe our model in detail and compare both theoretically
and experimentally the directional model DARGG with
two benchmark models: *Erdős-Bollobás Random Geomet-
ric Graph* (EBRGG) and *Vertex-Based Random Geometric
Graph* (VBRGG) proposed, respectively, by Gupta and Ku-
mar in [4] and by Bagchi et al. in [5]. We demonstrate
that DARGG is unrelated to the two benchmark models and
we show that, although DARGG achieves a high level of
connectivity at the benchmark radius at which EBRGG and
VBRGG achieve connectivity, it remains disconnected at
this radius. This sets us up to present our heuristics for
raising the connectivity level to 100%, which we do in
Section 4 along with rigorous mathematical analysis that
establishes how well they perform.

## 2. Related work

Since the last decade, researchers have begun to study
millimeter-wave directional networks due to their ability
to save power, minimize interference, to penetrate urban
spaces, and to offer unprecedented spectrum and multi-
Gigabit-per-second (Gbps) data rates to a mobile device [3],
[6], [7]. Attention has also been devoted specifically to the
connectivity problem in directional antennas [8], [9], [10]. In
the literature, two approaches are used to achieve connec-
tivity in directional networks. The first approach involves
computing antenna orientations to ensure connectivity. In
the second approach the devices are allowed to randomly
orient themselves and connectivity is ensured by tuning
other antenna parameters (e.g. power) such that connectivity
is ensured in this scenario.

Since our work is in the random orientation paradigm,
and due to the constraints of space, we only survey those
papers within this paradigm. We observe that this paradigm
assumes that a generalisation of the “Gupta-Kumar ap-
proach” proposed in [4] will work to ensure connectivity in
the directional model. In this paper, we will show that there
are some serious pitfalls in working with this assumption.

The first of the two groups who followed a Gupta-Kumar
approach, Li et al. [9], faced the issue of dependency of
connections, i.e., given a node *u* and two other nodes, *v*
and *w* that were within transmission range, the probability
that *u* is connected to both *v* and *w* is, in general, *less*
than the product of the probabilities of the events “*u* is
connected to *v*” and “*u* is connected to *w*.” In other words
these events are negatively correlated. To see this let us
consider a beamwidth of 2θ = 2π/3 (although any value less
than π will work for this example). Consider the following
example: Place *u* at the origin of the real plane and place
*v* at (-1,0) and *w* at (1,0), assume connection range to be
1.5. Because of the way *v* and *w* have been placed, and
because the beamwidth is less than π, if *u* is connected
to *v* the probability that it is also connected to *w* is 0.
This dependency was not encountered by Gupta and Kumar
since, due to the omni-directional nature of their connec-
tivity function, *once we know that v and w are within u's*
*range*, connectivity is given. Although Li et al. identified the

problem of dependency, they viewed it as a limited problem
and, in fact, appear to have spotted some kind of *positive*
correlation pertaining to antenna side-lobes, and, relying on
some mathematically non-rigorous findings in the area of
statistical mechanics, they went ahead and assumed that
Gupta-Kumar's results are valid. As our results show, this
is not the case.

The second group of researchers [11], which included
two of the authors of this paper, applied a general theorem
they had provided in an earlier work [5] where, to handle the
problem of connectivity in a duty-cycled network, they had
defined a careful generalisation of Gupta-Kumar's model
that took vertex-based dependencies into account. However,
the generalisation, called the Vertex-Based Random Geo-
metric Graph (VBRGG), crucially depended on the fact that
the connectivity function was independent of the *position* of
the nodes. In fact, in the example offered above, the proba-
bility of *u* being connected to both the nodes is 0. However
if we shift *v* to some other position, say (1/√2, 1/√2), then
there is some non-zero probability of *u* being connected to
both *v* and *w*. The problem is this: the *extent* of negative
correlation between the connectivity functions can change
with position, even when the two nodes are at the same
distance from the common node.

In summary, both group of researchers were unable to
spot subtleties within the directional setting that were absent
in the omni-directional scenario considered by Gupta and
Kumar.

## 3. The connectivity problem in DA networks

In this section, we first present the DARGG model to
represent DA networks. We then show that it is incompa-
rable to the two benchmark generalisations of the Gupta-
Kumar model mentioned in Section 2. Then, we show the
radius that ensures connectivity in the benchmark models is
not able to ensure connectivity in DARGG. We also discover
that the isolated nodes are localized to the boundary of the
region. This will lead in the next section to simple and
decentralized methods to connect the network.

### 3.1. The DARGG(n, r, θ) model

We consider *Directional Antenna networks* (briefly, DA)
formed by *n* nodes located uniformly and independently at
random in a disk *D* of unit area. The center *O* of *D* is
called the *origin*. Each node is equipped with a directional
antenna that chooses, independently of all the other nodes,
its orientation *ψ* at random in [0, 2π]. All the antennas have
the same beamwidth 2θ. The random choices of the location
and orientation set up a randomly configured network of
directional antennas.

*Transmission region.* To model the directionality of
the antennas we consider an idealized *gain* function that
concentrates the antenna gain uniformly in a sector. To
formalise this, let us introduce notation: Given a point
z ∈ R², two angles – θ ∈ [0, π/2] and ψ ∈ [0, 2π] – and
a real r > 0, the sector S<sub>r,θ</sub>(z, ψ) is a sector of radius r
and width $2\theta$ centred at $z$, with the property that the ray originating at $z$ that bisects the sector forms an angle of $\psi$ with the positive $x$-axis.

As discussed above, each of our $n$ nodes chooses its location, $u \in \mathcal{D}$ and its orientation $\psi_u$ independently of all other random choices. Choosing a value $r$ that is related to the transmission power available to the antenna, and determining $\theta$ based on the extent to which the antenna is able to focus its power footprint along the direction of its orientation, our modeling assumption is this: The antenna at point $u$ is able to transmit to all the points in sector $S_{r,\theta}(u, \psi_u)$.

<figure><img src="image_2.png" /><figcaption>Figure 1. The parameters involved in setting a communication between two antennas.</figcaption></figure>

**Point-to-point communication.** Given the transmission pattern described above, point-to-point communication between two antennas $u$ and $v$ is said to be possible only if $u \in S_{r,\theta}(v, \psi_v)$ and $v \in S_{r,\theta}(u, \psi_u)$, i.e., if each of them lie in the other's transmission region (we abuse notation to use $u$ to denote both the antenna and its location).

Fig. 1 illustrates the parameters involved in the definition of point-to-point communications in DA.

**Definition 1.** Two antennas $u$ and $v$ can directly communicate only if they satisfy the following conditions:

1) the distance $d(u, v) \le r$;

2) the angle $\beta_u$ formed by the orientation $\psi_u$ and the line that connects $u$ and $v$ is no larger than $\theta$;

3) the angle $\beta_v$ formed by the orientation $\psi_v$ and the line that connects $u$ and $v$ is no larger than $\theta$.

Condition 2 says that $v$ is in the transmission area of $u$, whereas Condition 3 says that $u$ is in the transmission area of $v$. So, any point-to-point undirected $(u, v)$ communication occurs if the two directed communications $u \to v$ and $v \to u$ exist. More specifically, if only one of these two directed communications occurs, it is ignored in our model.

In conclusion, any DA network whose antennas follow the idealized sector model of radius $r$ and width $\theta$ will be referred to as DARGG($n, r, \theta$) which is a random graph model whose underlying graph $G = (V, E)$ is built by associating a vertex to each antenna in DA, and adding an undirected edge $(u, v) \in E$ if $u$ and $v$ can establish a point-to-point communication.

**Marginal probability of edge formation in DARGG(n, r, θ).** Since the position and the orientation of the antennas are modelled by independent random variables, we compute the probability that a single edge belongs to $E$ as a joint probability. Hence, $P((u, v) \in E) = \frac{\theta^2}{\pi}r^2$ because $v$ belongs to the circle of radius $r$ centered at $u$ with probability $\pi r^2$ given that $\mathcal{D}$ has unit area, $u$ has probability $\frac{\theta}{\pi}$ to be oriented towards $u$, and the same probability has $v$ to be oriented towards $v$.

## 3.2. Comparing DARGG, EBRGG, and VBRGG

As discussed in Section 2 the question “What is the best (smallest) value of $r$ that ensures (with high probability) that DARGG($n, r, \theta$) is connected?” is misleading.

Let us recall the definition of the two random geometric graph models that are generalisations of the Gupta-Kumar model, that are closely related to DARGG($n, r, \theta$), but are qualitatively different in terms of their properties. The first of these models was described by Gupta and Kumar themselves [4], and also studied by Bollobás et al. [12]. In this model, we call it EBRGG($n, r, p$), $n$ nodes are placed randomly in $\mathcal{D}$ and an edge is placed between a pair of nodes $(u, v)$ with distance $d(u, v) \le r$ with probability $p$. All random choices of location of nodes and of placement of edges are taken to be independent in this model.

The second model was described by a team that included two of the authors of this paper [5] to study the connectivity of duty-cycled networks. In this model, VBRGG($n, r, p$), the nodes are placed randomly in $\mathcal{D}$ as before. As before, only those nodes $u, v$ which have $d(u, v) \le r$ can have an edge placed between them. However, to determine which of these eligible pairs actually have an edge placed between them, we work with a random variable $\psi$ and equip each node $u$ with a copy of the random variable $\psi$ which we call $\psi_u$. If $\psi$ is defined on a domain $X$, we also have a function $f: X \times X \to \{0, 1\}$ that determines whether $u$ and $v$ are connected. Further, we have that if $\psi_1$ and $\psi_2$ are two independent copies of $\psi$ then $P(f(\psi_1, \psi_2) = 1) = p$. Again we note that all random choices of the locations of the nodes and the copies of $\psi$ are independent of each other. Besides an important implicit assumption in [5] is that the function $f$ is independent of the locations of the nodes and depends only on the choice of the copies of $\psi$.

Setting $\gamma = \theta^2/\pi^2$, we now compare DARGG($n, r, \theta$) to EBRGG($n, r, \gamma$) and VBRGG($n, r, \gamma$) since the marginal probability of edge placement between any two nodes is the same in all three models.

**DARGG(n, r, θ) and EBRGG(n, r, γ) are unrelated.** To demonstrate the difference between DARGG($n, r, \theta$) and EBRGG($n, r, \gamma$), we return to an example presented in Section 2. Let us call this Example A: Place $u$ at the origin of the real plane and place $v$ at $(-1,0)$ and $w$ at $(1,0)$, assume $r = 1.5$ (hence, $r$ is greater than the radius of $\mathcal{D}$) and $\theta = \pi/3$. In DARGG($n, r, \theta$), the probability of both edges $(u, v)$ and $(u, w)$ existing simultaneously is 0 because $v$ and $w$ can never reside on the same sector of width $2\pi/3$, whereas in EBRGG($n, r, \gamma$) the probability is $\gamma^2 > 0$. From this example we see that there are cases where the edge set of EBRGG($n, r, \gamma$) is a superset of the edge set of DARGG($n, r, \theta$). However, there are situations where the domination is in the opposite direction. Let us call this Example B: Consider the example above, except we move $v$ to $(1 - \epsilon, 0)$ for a very small $\epsilon$ so that $v$ and $w$ are right next to each other and $v$ lies on the line joining $u$ to $w$. In this case, fixed the sector of $u$, independently from the value of $\theta$, either both $v$ and $w$ reside in the sector of $u$ or none. So if $\phi_v$ and $\phi_w$ are both oriented
towards $u$, and both $v$ and $w$ reside in the sector of $u$, then the probability that the two edges $(u, v)$ and $(u, w)$ simultaneously exist is 1. Hence the probability that $u$ is connected to both $v$ and $w$ in DARGG($n, r, \theta$) is $\theta^3/\pi^3$, i.e. the product of the probabilities of the three events (a) $S_{1.5,\theta}(u, \psi_u)$ contains both $v$ and $w$, (b) $S_{1.5,\theta}(v, \psi_v)$ contains $u$, and (c) $S_{1.5,\theta}(w, \psi_w)$ contains $u$. On the other hand, in EBRGG($n, r, \gamma$) the probability of both these edges existing is $\gamma^2 = \theta^4/\pi^4 < \theta^3/\pi^3$. So DARGG($n, r, \theta$) has a higher probability of having both these edges. Without formalizing this overly we note that these two examples can be used to argue that there is no stochastic domination between these two models in either direction.

DARGG($n, r, \theta$) and VBRGG($n, r, \gamma$) are unrelated. The locations of the three nodes in Example A and Example B discussed above also serve to show that DARGG($n, r, \theta$) and VBRGG($n, r, \gamma$) are unrelated. Let us consider the probability of placement of both edges $(u, v)$ and $(u, w)$ in VBRGG($n, r, \gamma$). In Example A, the probability is again $\gamma^2 > 0$ as opposed to 0 in the case of DARGG($n, r, \theta$). Similarly, in Example B the probability of both edges existing is $\gamma^2$ for VBRGG($n, r, \gamma$) which is less than $\theta^3/\pi^3$ which is the probability for DARGG($n, r, \theta$). Hence neither of these two models dominates the other.

A benchmark for the connectivity radius of DARGG($n, r, \theta$). At this point, the initial question about which is the radius that guarantees the connectivity in DARGG is still open. We recall that in [5] it has been proved the critical transmission radius for ensuring connectivity w.h.p. in VBRGG($n, r, \gamma$) as $n \to \infty$ is

$$R(n, \gamma) = \sqrt{\frac{\log n + c}{n\pi\gamma}} \quad (1)$$

where $c = \lim_{n \to \infty} c(n) = \infty$ as $n \to \infty$. The same critical transmission radius has been conjectured in [4] for the EBRGG($n, r, \gamma$). Since we have no better clues, we proceed our experimental research of the critical transmission in DARGG($n, r, \theta$) having in mind as a benchmark the radius $R(n, \gamma)$ in Eq. 1.

### 3.3. An experimental study of connectivity

We now present, in brief, the results of an extensive simulation study. We show that DARGG does not achieve connectivity even at very high radii and that the disconnected nodes are to be found near the boundary. Further, we show that the nature of boundary effects across DARGG, EBRGG, and VBRGG is very different at similar radii. Finally, in preparation for our connectivity-fixing heuristics (Section 4) we show that the benchmark radius that achieves full connectivity for VBRGG and EBRGG achieves a high connectivity for DARGG and serves as a good platform from where we can apply our heuristics to achieve full connectivity.

*Simulation setup.* We generate $n$ sensors placed uniformly at random in a unit disk, with $n$ being chosen fairly large, $2 \cdot 10^5 \le n \le 10^6$, since the study of the critical

transmission radius is carried out in a dense network setting. For each point we then choose the orientation $\psi$ at random in $[0, 2\pi]$. We set the parameter $\theta \in \{\frac{\pi}{6}, \frac{\pi}{4}, \frac{\pi}{3}, \frac{\pi}{2}\}$. We vary the sector radius $r$ from 0 to the largest possible radius $R_D = \frac{1}{\sqrt{\pi}}$ in $D$ and beyond. As said, we consider of particular interest the radius in Eq. 1. In this paper, since $\gamma = \frac{\theta^2}{\pi^2}$, $R(n, \gamma) = \sqrt{\frac{\log n + \log \log n}{\pi n}}$ will be denoted as $R(n, \theta)$ to stress the dependency with the beamwidth, or simply $R$ when the values $n$ and $\theta$ are clear from the context.

Having fixed a value of the beamwidth $\theta$ and of the transmission radius $r$, in DARGG, we add an edge $(u, v)$ to $E$ if $u \in S_{r,\theta}(v, \psi_v)$ and $v \in S_{r,\theta}(u, \psi_u)$. We build an instance of the EBRGG($n, r, \gamma$) model with $\gamma = \frac{\theta^2}{\pi^2}$, as follows: For each pair of nodes at distance at most $r$, we generate a random number $x$ uniformly distributed in $[0, 1]$, and we add the edge $(u, v)$ if $x \le \frac{\theta^2}{\pi^2}$. Moreover, we generate an instance of the VBRGG($n, r, \gamma$) with $\gamma = \frac{\theta^2}{\pi^2}$ by adding the edge $(u, v)$ if and only if $\psi_u \in \mathcal{I}[\pi + \psi_v - \theta, \pi + \psi_v + \theta]_{2\pi}$ and $\psi_v \in \mathcal{I}[\psi_u - \theta, \psi_u + \theta]_{2\pi}$, where $\mathcal{I}[a, b]_{2\pi}$ are the orientations that fall in the sector spanned while counterclockwise moving the ray $a$ over $b$. Finally, we simulate the RGG model by setting $\theta = \pi$ in the DARGG model.

For each instance of the above random graphs, the experiment consists in computing the connected components, and tracing their number and their sizes. We also count the number of isolated nodes and trace their position in $D$. Each experiment is repeated at least three times and the average value is reported.

DARGG is always disconnected. At first, we study if an arbitrary large radius can be used to connect the network under the DARGG model. We start studying the number of isolated nodes when the sector radius varies between $R_D$ and $2R_D$, i.e., from half the maximum possible distance between two points all the way up to the maximum possible distance between any two points. When the sectors have radius $2R_D$, any two antennas, independently of their position in $D$, are possible neighbors. Note that $R_D$ is more than 110 times the critical radius of the RGG model when $n = 2 \cdot 10^5$, and more than 240 times when $n = 10^6$.

Table 1 reports the results for $n = 2 \cdot 10^5$ and $n = 10^6$. There are always isolated nodes even when the radius is as long as the radius of the deployment area. As one can see, when the radius grows from $R_D$ to $2R_D$ and $\theta < \frac{\pi}{2}$, the number of isolated nodes remains the same for all cases. For all values of $\theta$, the number of isolated nodes marginally decreases while the radius increases from $R$ to $R_D$. We conclude that increasing the radius from the benchmark radius $R$ to $R_D$ or beyond does not improve the network connectivity, if $\theta < \frac{\pi}{2}$. Finally, observe that the case $\theta = \frac{\pi}{2}$ behaves more likely the omnidirectional case than $\theta < \frac{\pi}{2}$.

Isolated nodes are close to the boundary. We observed experimentally and we report in Table 2 that as the radius $r$ increases spatial pattern emerges in the isolated nodes of DARGG($n, r, \theta$): for small values of radius $r$, the isolated nodes are spread throughout $D$ but when $r$ increases, they progressively move towards the outer corona $\delta D$ of width equal to half of the transmission radius. This
<table><caption>TABLE 1. NUMBER OF ISOLATED NODES</caption><thead><tr><th>n</th><th>r</th><th>π/6</th><th>π/4</th><th>π/3</th><th>π/2</th></tr></thead><tbody><tr><td rowspan="3">2 · 10<sup>5</sup></td><td>R</td><td>1144</td><td>561</td><td>266</td><td>26</td></tr><tr><td>R<sub>D</sub></td><td>1129</td><td>530</td><td>233</td><td>2</td></tr><tr><td>2R<sub>D</sub></td><td>1129</td><td>530</td><td>233</td><td>1</td></tr><tr><td rowspan="3">10<sup>6</sup></td><td>R</td><td>2591</td><td>1271</td><td>618</td><td>74</td></tr><tr><td>R<sub>D</sub></td><td>2522</td><td>1222</td><td>543</td><td>4</td></tr><tr><td>2R<sub>D</sub></td><td>2522</td><td>1222</td><td>543</td><td>4</td></tr></tbody></table>

<table><caption>TABLE 2. PERCENTAGE OF ISOLATED NOTES</caption><thead><tr><th>θ</th><th colspan="2">π/2</th><th colspan="2">π/3</th><th colspan="2">π/4</th><th colspan="2">π/6</th></tr></thead><tbody><tr><td>r</td><td>R</td><td>R/2</td><td>R</td><td>R/2</td><td>R</td><td>R/2</td><td>R</td><td>R/2</td></tr><tr><td>δD</td><td>100</td><td>3</td><td>100</td><td>6.1</td><td>100</td><td>10.1</td><td>100</td><td>16.1</td></tr><tr><td>D - δD</td><td>0</td><td>97</td><td>0</td><td>93.9</td><td>0</td><td>89.9</td><td>0</td><td>83.9</td></tr></tbody></table>

leads us to believe that the restriction of isolated nodes to the outer corona is experimental evidence of the boundary effects. The boundary effects, that Gupta-Kumar in RGG and the authors of [5] in VBRGG found easy to handle, lead to significant complications in the directional setting.

Comparing boundary effects across DARGG, VBRGG, and EBRGG. Figures 2 and 3 plot the percentage of connectivity, that is, the size of the largest connected component versus the total number *n* of nodes, for different radii. EBRGG and VBRGG reach 100% percentage of connectivity, thus forming a unique connected component when *r* is equal to their critical radius, while DARGG does not. One must say that the size of the largest connected component in DARGG increases when *θ* increases. In particular, for *θ* = π/2, as reported in Table 1, only few nodes are left out. The 100% of connectivity is reached by EBRGG and VBRGG for all values of *θ* we have tested. We have now evidence via simulations that the border effect appears in DARGG but *does not* appear in the other two models at the values of *n* we have chosen. Thus, the border effect is a characteristic of DARGG not shared by at least the two other models that are closest to it without being explicitly directional.

High connectivity at the benchmark radius in DARGG. In the following, we show that in DARGG, although there are isolated nodes when $r = R(n, \theta)$, the benchmark radius ensures a very high connectivity. In our

<figure><img src="image_3.png" /><figcaption>Figure 2. The size of the largest connected component in EBRGG, VBRGG and DARGG model when $\theta = 30$ with $n = 2 \cdot 10^5$.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3. The size of the largest connected component in EBRGG, VBRGG and DARGG model when $\theta = 60$ with $n = 2 \cdot 10^5$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4. The percentages of connectivity when $n = 2 \cdot 10^5$</figcaption></figure>

simulations, the largest connected component always involves above 99% of the nodes, while the second largest connected component consists of very few nodes or even a single node.

For each value of $\theta$ and $n$, we run the following set of experiments: we compute the percentage of connectivity from $r = 0$ up to the first radius that reaches 99% of connectivity using an incremental step of 0.0005. Moreover, we compute the percentage of connectivity with the benchmark radius $r = R(n, \theta)$. We report the results in Figures 4 and 5, respectively, when $n = 2 \cdot 10^5$ and $n = 10^6$. All the curves present what is known in the random graphs literature as a “first-order phase transition phenomenon”, that is, a small increment of the radius leads to a big jump in the

<figure><img src="image_6.png" /><figcaption>Figure 5. The percentages of connectivity when $n = 10^6$</figcaption></figure>
connectivity percentage. The phenomenon is slightly more evident for $n = 10^6$ than for $n = 2 \cdot 10^5$. The black dot in each curve marks the percentage of connectivity that we can reach using the critical transmission radius $R(n, \theta)$. As the curves show, the percentage of connectivity increases with the beamwidth $\theta$. All the values of $\theta$ reach 99% of connectivity when $r \approx \frac{R(n, \theta)}{2}$. The growth of connectivity from $\frac{R(n, \theta)}{2}$ to the benchmark radius $R(n, \theta)$ is almost null and incredibly slow. As one can see in Fig. 6, only the experiments that use omnidirectional antennas, which exactly fall in the RGG model, lead to a connected network in a strict sense (i.e. 100%). All the other networks are above 99% at $r = R(n, \theta)$, as well illustrated in Fig. 6 and 7, which zoom in on the top part of the curves of Fig. 4 and 5, respectively. When $n = 10^6$, although the percentage of connectivity becomes closer to 100%, the networks remain disconnected in a strict sense for all values of $\theta$.

<figure><img src="image_7.png" /><figcaption>Figure 6. The percentages of connectivity above 97% when $n = 2 \cdot 10^5$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7. The percentages of connectivity above 97% when $n = 10^6$</figcaption></figure>

*Discussion of simulation findings.* In conclusion, we believe that our benchmark radius guarantees connectivity except for the nodes on the distal corona. The DARGG model is affected by border effects, especially for small values of $\theta$, because the nodes oriented outside the disk have a limited number of nodes candidate to be neighbours. Inspired by this analysis, we propose in the next section two solutions to achieve full connectivity.

## 4. Border effects and isolated nodes

In this section, we theoretically prove that if the radius is set to the benchmark radius $R$, there are still isolated nodes and all of them belong to the outercorona $\delta D$ of the disk, thus confirming our experimental results. We also prove that these isolated vertices have their antennas oriented in such a way that their sectors do not intersect the core.

**Definition 2.** Given $n$ and $\theta$, let the outercorona $\delta D$ be the part of $D$ comprised between the two circumferences centered at the field origin $O$ and of respective radii $R_D$ and $R_D - \frac{R}{2}$. Let the area of outercorona be $A_{\delta D} = R\sqrt{\pi} - \frac{R^2\pi}{4}$. Let $n_{\text{BOUNDARY}}$ be the number of nodes falling in the outercorona $\delta D$.

**Definition 3.** Given $n$ and $\theta$, let the core denote $D - \delta D$, that is, $D$ except the outercorona $\delta D$. Let the area of core be $A_{D-\delta D} = 1 - R\sqrt{\pi} + \frac{R^2\pi}{4}$. Let $n_{\text{CORE}}$ be the number of nodes falling in the outercorona $\delta D$.

From our experimental work, we know that the isolated vertices concentrate in the outercorona when the benchmark transmission radius $R$ is adopted. The following lemma tells us that w.h.p. the number of nodes falling in the outercorona is $\sqrt{n \log n} \pm O(\sqrt{n})$.

**Lemma 1.** Recalling $\gamma = \frac{\theta^2}{\pi^2}$, the number of nodes $n_{\text{BOUNDARY}}$ that fall in the outercorona satisfies:

$$ \mathbb{P}\left[ \left| n_{\text{BOUNDARY}} - \sqrt{\frac{n \log n}{\gamma}} \right| > \sqrt{n} \right] \le O\left( \sqrt{\frac{\log n}{n}} \right) \quad (2) $$

and

$$ \mathbb{P}\left[ \left| n_{\text{CORE}} - n + \sqrt{\frac{n \log n}{\gamma}} \right| > \sqrt{n} \right] \le O\left( \sqrt{\frac{\log n}{n}} \right). \quad (3) $$

*Proof.* For any of the node $i$ ($i \in \{1, \dots, n\}$), let $X_i = 1$ if the node $i$ belongs to the core ($D - \delta D$) and 0 otherwise. That is $n_{\text{CORE}} = \sum_{i=1}^n X_i$. Since the nodes are uniformly distributed, $\mathbb{P}[X_i = 1] = A_{(D-\delta D)}$ because $D$ has unit area. By linearity of expectation, we have

$$ \mathbb{E}[n_{\text{CORE}}] = \sum_{i=1}^{n} \mathbb{E}(X_i) = A_{(D-\delta D)}n $$

We also have

$$ \begin{aligned} \mathbb{E}[n_{\text{CORE}}^2] &= \mathbb{E}\left[\sum_{i}^{n} X_i^2 + \sum_{i \neq j} X_i X_j\right] \\ &= A_{(D-\delta D)}n + A_{(D-\delta D)}^2(n^2 - n). \end{aligned} $$

Thus:

$$ \begin{aligned} \text{Var}(n_{\text{CORE}}) &= \mathbb{E}[n_{\text{CORE}}^2] - \mathbb{E}[n_{\text{CORE}}]^2 = \\ &= A_{\delta D} A_{(D-\delta D)} n = O(\sqrt{n \log n}). \end{aligned} $$
Applying the Chebyshev's inequality with $a = \sqrt{n}$ leads to the lemma

$$ \mathbb{P}[|n_{\text{CORE}} - \mathbb{E}[n_{\text{CORE}}]| > a] \le \frac{\text{Var}[n_{\text{CORE}}]}{a^2} \quad \square $$

Define an internal node to be a node falling in the core $\mathcal{D} - \delta\mathcal{D}$. The following statement tells us that for the radius $R$ there is asymptotically almost surely no isolated internal node.

**Lemma 2.** With probability at least $1 - O(e^{-c})$, there are no isolated internal nodes.

*Proof.* Let $\{v_1, v_2, \dots, v_{n_{\text{CORE}}}\}$ be the set of internal nodes, that is the vertex set inside $\mathcal{D} - \delta\mathcal{D}$. For each $v_i$ of this set, let $A_i$ be the event $v_i$ is an isolated vertex. This time, let $X_i = 1$ if $A_i$ occurs and 0 otherwise and set $X = X_1 + \dots + X_{n_{\text{CORE}}}$. We will show that $\mathbb{E}[X] \to 0$ as $n$ is large. As an internal node, $v_i$ is isolated iff no other vertex connected to it. Another node $v_j$ falls in the sector of $v_i$ with probability $\theta R^2$ and – given the orientation of $v_i$ – in order to create the edge $(v_i, v_j)$, we need $v_j$ to be oriented toward $v_i$. Such an orientation occurs with probability $\frac{\theta}{\pi}$. Thus, $\mathbb{P}[X_i = 1] \le (A_{\mathcal{D}} - \frac{\theta^2}{\pi} R^2)^{n-1} = (1 - \frac{\theta^2}{\pi} R^2)^{n-1}$. As $x \to 0$, $(1 - x) = e^{-x}(1 + o(1))$ we get using the benchmark radius $R$: $\mathbb{P}[X_i = 1] \le 2e^{-\log n - c}$. By linearity of expectation, $\mathbb{E}[X] \le n\mathbb{P}[X_i = 1] \le 2e^{-c}$ and by Markov's inequality $\mathbb{P}[X > 0] \le 2e^{-c}$ because $\text{Pr}(X \ge 1) \le \frac{\mathbb{E}(X)}{1}$. That is with probability at least $1 - O(e^{-c})$ none of the core vertices is isolated. $\square$

Using similar arguments and the fact that the number of nodes in $\mathcal{D} - \delta\mathcal{D}$ is w.h.p. $n_{\text{CORE}} = n - \sqrt{n \log n}/\gamma + O(\sqrt{n})$ we can prove a slightly more powerful result:

**Corollary 1.** With probability at least $1 - O(e^{-c})$, all the internal nodes have at least one internal neighbor.

The following lemma corroborate our experimental intuition. For nodes in $\delta\mathcal{D}$, it is most likely that they are isolated once their sector does not intersect the core.

**Lemma 3.** Let $v$ be a vertex of the outercorona $\delta\mathcal{D}$. Suppose that the sector $S_{R,\theta}(v, \psi_v)$ does not intersect the core. Then, with probability at least $1 - O(\frac{\log^{3/2} n}{n^{1/2}})$ $v$ is isolated.

*Proof.* If the sector of $v$ does not intersect the core then $v$ cannot be connected to any of the $n_{\text{CORE}}$ vertices in $\mathcal{D} - \delta\mathcal{D}$. Then, $v$ is connected to a vertex $u \in \delta\mathcal{D}$ with probability $\frac{\theta}{\pi}$. $A_{|S_{R,\theta}(v, \psi_v) \cap \delta\mathcal{D}|} \le \theta R^2$ where the first factor is the probability that $u$ is oriented toward $v$, the second factor reflects the fact that $u$ is in the sector of $v$ and simultaneously in the outercorona.

Since $A_{|S_{R,\theta}(v, \psi_v) \cap \delta\mathcal{D}|} \le \theta R^2$, the probability that $v$ is isolated is

$$ \left(1 - \frac{\theta}{\pi} A_{|S_{R,\theta}(v, \psi_v) \cap \delta\mathcal{D}|}\right)^{n_{\text{BOUNDARY}}} \ge \left(1 - \frac{\theta^2}{\pi} R^2\right)^{n_{\text{BOUNDARY}}} $$

As typical values of the random variable $n_{\text{BOUNDARY}}$ is of order $O(\sqrt{n \log n})$ with high probability, we can conclude that $v$ is isolated with probability larger than

$$ \exp\left(-O\left(\frac{\log^{3/2} n}{n^{1/2}}\right)\right) = 1 - O\left(\frac{\log^{3/2} n}{n^{1/2}}\right). \quad \square $$

## 4.1. Reconnecting isolated nodes

In the following, we consider two reorientation algorithms. The first algorithm, T-core, flips the orientation of the isolated nodes toward the origin $\mathcal{O}$ of $\mathcal{D}$. This algorithm requires that the center of the network is known by all the nodes and that they are equipped with a GPS device. The second algorithm, Greedy, flips the isolated nodes by adding $\pi$ to their orientation. This algorithm works very well in practice.

*Analysis of T-core algorithm.* Let $v$ be a node falling in $\delta\mathcal{D}$ whose orientation $\psi_v$ has been reoriented toward the center. In contrast with Lemma 3, $v$ can have now all of the $n$ nodes as potential neighbours. Then, $v$ is isolated with probability $(1 - \frac{\theta^2}{\pi} (R^2 - d(v)^2))^{n-1}$ where $d(v)$ is a random real variable uniformly distributed in $[0, \frac{R}{2}]$ since $v$ is in $\delta\mathcal{D}$ and at distance $d(v)$ from the internal circumference that limit the outercorona.

Now for any node $v$ falling in the boundary, let $X_v = 1$ if $v$ is isolated and $X_v = 0$ otherwise. After the reorientation of the isolated nodes, the expected number of isolated vertices is then $\sum_{\text{re-oriented vertex } v} (1 - \frac{\theta^2}{\pi} R^2 (1 - d'(v)^2))^{n-1}$, where $d'(v)$ is a random variable uniformly distributed in $[0, 1/2]$.

By Lemma 1, we have to sum on at most $O(\sqrt{n \log n})$ values. Thus, using again $(1 - x) \sim e^{-x}$ (as $x \to 0$) and approximating the summation by an integral, the expectation above is asymptotically

$$ \le O(\sqrt{n \log n}). \int_0^{1/2} \frac{1}{n(1-x^2)} dx. $$

Since

$$ \int_0^{1/2} \frac{1}{n^{1-x^2}} dx = \frac{\sqrt{\pi}}{2} \frac{\text{erf}(\frac{1}{2}\sqrt{-\log n})}{n\sqrt{-\log n}} $$

where erf is the standard error function (see Abramowitz and Stegun [13, Section 7.1.1]), using the asymptotic approximation

$$ \text{erf}(ix) = \frac{i}{\sqrt{\pi x}} \left(1 + O\left(\frac{1}{x^2}\right)\right) e^{ix^2} $$

for large $x$, we get after some algebra

$$ \int_0^{1/2} \frac{1}{n^{1-x^2}} dx \le O\left(\frac{1}{n^{3/4} \log n}\right) $$

for large $n$. Thus the expected number of isolated nodes after reorientation is at most $O(\frac{1}{n^{1/4} \log^{1/4} n})$. Using Markov's inequality, the following important observation follows:
**Lemma 4.** All the nodes of the outercorona after the T-core reorientation are no more isolated with probability at least $1 - O\left(\frac{1}{n^{1/4} \log^{1/4} n}\right)$.

*Analysis of the Greedy algorithm.* To analyze the greedy algorithm, we compute the probability that after the greedy flip, an isolated node $v$ still does not meet the core. We define such a node *butterfly*. As illustrated in Fig. 8, the probability that a node $v$ is a butterfly is $P[v \text{ is a butterfly}] = 1 - \frac{2(\alpha(x)+\theta)}{\pi}$ where $\alpha(x) = \arcsin\left(\frac{1/\sqrt{\pi}-R/2}{1/\sqrt{\pi}-R/2+x}\right)$ with $x$ is a random variable uniformly distributed in $[0, R/2]$.

<figure><img src="image_9.png" /><figcaption>Figure 8. A butterfly and illustration of its probability.</figcaption></figure>

For any of the node $i$ in the outercorona $\delta D$, let $X_i = 1$ if the node $i$ is a butterfly and 0 otherwise. Let the number of butterfly nodes be $n_{\text{BUTTERFLY}} = \sum_{v \in \delta D} \left(1 - \frac{2(\alpha(x)+\theta)}{\pi}\right)$.

By Lemma 1 and by using the approximation of $\alpha(x)$ for $R \to 0$, it can be proved:

**Lemma 5.** The expected number of isolated nodes after the Greedy flip algorithm is at least of order $O(\log n)$. $\square$

<figure><img src="image_10.png" /><figcaption>Figure 9. The average number of isolated nodes when $n = 10^6$ in DARGG($n, R, \gamma$) (without any reorientation), with T-Core, and Greedy algorithms. The error bars represent the 95% confidence interval.</figcaption></figure>

Fig. 9 reports the effectiveness of the reorientation algorithms experimentally tested.

## 5. Conclusion

In this paper, we studied the issues involved in creating a connected mesh network with bidirectional links using directional antennas. We showed that there is no critical radius

that alone guarantees connectivity as instead it happens for omnidirectional networks. We proved that the disconnected nodes are confined to a narrow corona at the border of the region of deployment and we presented two decentralized random protocols for network formation which rely on adequate transmission power and some additional local reconfiguration.

As a future work, we intend to extend our study to the robustness of DARGG for discovering the largest percentage of nodes that can be destroyed still preserving the network functionality.

## References

[1] K. Chebrolu and B. Raman, “FRACTEL: a fresh perspective on (rural) mesh networks,” in *Proc. 2007 workshop on Networked systems for developing regions*, p. 8, ACM, 2007.

[2] P. Carmi, M. J. Katz, Z. Lotker, and A. Rosén, “Connectivity guarantees for wireless networks with directional antennas,” *Comput. Geom.*, vol. 44, no. 9, pp. 477–485, 2011.

[3] T. Rappaport, S. Sun, R. Mayzus, and et al., “Millimeter wave mobile communications for 5g cellular: It will work!,” *IEEE Access*, vol. 1, pp. 335–349, 2013.

[4] P. Gupta and P. R. Kumar, “Critical power for asymptotic connectivity in wireless networks,” in *Stochastic analysis, control, optimization and applications*, pp. 547–566, Springer, 1999.

[5] A. Bagchi, C. M. Pinotti, S. Galhotra, and T. Mangla, “Optimal radius for connectivity in duty-cycled wireless sensor networks,” *ACM T Sensor Network*, vol. 11, no. 2, p. Article No. 36, 2015.

[6] G. MacCartney and T. Rappaport, “Rural macrocell path loss models for millimeter wave wireless communications,” *IEEE Journal on Selected Areas in Communications*, vol. 35, no. 7, pp. 1663–1677, 2017.

[7] T. Rappaport, Y. Xing, and et al., “Overview of millimeter wave communications for fifth-generation (5g) wireless networks with a focus on propagation models,” *IEEE Transactions on Antennas and Propagation*, vol. 65, pp. 6213–6230, Dec 2017.

[8] E. Kranakis, D. Krizanc, and O. Morales, “Maintaining connectivity in sensor networks using directional antennae,” in *Theoretical Aspects of Distributed Computing in Sensor Networks*, pp. 59–84, Springer, 2011.

[9] P. Li, C. Zhang, and Y. Fang, “Asymptotic connectivity in wireless ad hoc networks using directional antennas,” *IEEE/ACM Trans. Netw.*, vol. 17, no. 4, pp. 1106–1117, 2009.

[10] U. Okorafor and D. Kundur, “On the relevance of node isolation to the k-connectivity of wireless optical sensor networks,” *IEEE Transactions on Mobile Computing*, vol. 8, no. 10, pp. 1427–1440, 2009.

[11] A. Bagchi, F. B. Sorbelli, M. C. Pinotti, and V. J. Ribeiro, “Connectivity of a dense mesh of randomly oriented directional antennas under a realistic fading model,” in *ALGOSENSORS 2015*, pp. 13–26, 2015.

[12] B. Bollobás, *Random Graphs*. Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2001.

[13] M. Abramowitz and I. A. Stegun, *Handbook of Mathematical Functions*. Dover Publications, 1965.