Connectivity of a Dense Mesh of Randomly Oriented Directional Antennas Under a Realistic Fading Model

Abstract

We study mesh networks formed by nodes equipped with directional antennas in a high node-density setting. To do so we create a random geometric graph with n nodes placed uniformly at random. The antenna at each node chooses a direction of orientation at random and edges are placed between pairs of nodes based on their distance from each other and their directions of orientation according to the gain function of the antennas. To model the directionality of the antennas we consider a realistic gain function where the signal fades away from the direction of orientation. We also consider an idealised function that concentrates the gain uniformly in a sector of angle $2\theta$ centred around the direction of orientation. In this setting we show theoretically that with probability tending to 1 the optimal power required for achieving connectivity is significantly lower than that needed for connectivity in an omnidirectional setting. We capture mathematically the relationship between this optimal power level and the maximum gain of the antenna, showing that as the directionality of the antenna increases the power needed for connectivity decreases. However this optimal power level is also inversely proportional to the probability of connectivity of two randomly placed nodes, which decreases as directionality increases. We validate these results through simulation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Directional antennas are used in several applications including satellite communications, terrestrial microwave communications, VHF and UHF terrestrial TV transmission, cellular communication, and rural mesh networks [8]. Antenna directionality focuses transmission power in a particular direction and improves communication range while simultaneously reducing interference with nearby antennas. However, a drawback is that a priori knowledge of the location of the intended radio receiver and, in some cases, the ability to steer the antenna or switch beams in the relevant direction is required to form connections between pairs of nodes. A larger issue is of network-wide connectivity which becomes especially important in applications such as disaster management and military battlefield communications that require the rapid setup of a wireless multihop (mesh) network [7, 18]. In order to benefit from the ability of directional antennas to focus power in such settings it is critical to understand how a connected network can be formed using highly directional antenna beams. Hence the critical question is: Can fixed (non-steerable) directional antennas also be used to successfully build connected wireless mesh networks in which nodes and antenna orientations are chosen randomly?

While there has been a lot of discussion on the issue of capacity in highly directional antenna-based networks, there are few works in the literature that have addressed the question of connectivity. Notable among them is the work by Li et al. [13] which addresses this question but under an idealized model of directional transmission that assumes a sector shaped area of transmission (with some back lobes) with uniform power transmitted throughout the sector. In this paper we approach directional transmission in much greater generality and provide a result that holds for a large family of gain functions. We demonstrate how these results help us find the optimal power for connectivity in the dense mesh network setting. Using the gain function as our primary mode of describing the directionality of an antenna, we present a theorem that helps us determine the optimal power for connectivity for all gain functions that satisfy some moderate conditions. We further support our theoretical results through simulation using a particular family of gain functions that have been empirically found to accurately describe the power transmission pattern of directional antennas. Since in such models the gain of the antenna (i.e. the power transmitted per unit solid angle) is maximum in the direction of orientation and fades as we move away from this direction we refer to this model as the directional fading model or just the fading model. We determine the optimal power level needed to achieve connectivity for a mesh network whose antennas follow the fading model. We also revisit the simpler idealized model studied by Li et al. [13], we call it the ideal directional model or just the ideal model, and show how to set the parameters in this model so that any two antennas have the same probability of being connected in the ideal model as in the fading model. This result is obtained by equating the halfbeam of a directional antenna in the fading model with the width of the sector in the ideal model. We observe that under such an equivalence the optimal power level of the fading model is double of the optimal power level of the ideal model. This is of great help for deciding the antenna setting in the fading model when connected directional meshes are designed subject to constraints on the power transmission level.

Another important novelty of our paper is that our main result on connectivity is completely rigorous. A disadvantage of [13] is that they assume that if all the antennas are positioned randomly and their antennas are oriented randomly then the edges between nodes are formed independently. This assumption clearly does not hold, as we will show in detail in Sect. 3. Our mathematical results do not need the independence assumption. Hence we claim to present the first fully rigorous analysis of connectivity in dense mesh networks built with directional antennas.

Our Contribution. We assume that nodes are deployed randomly in a finite circular area, and that each node is equipped with a directional antenna whose orientation is initially fixed randomly and kept fixed thereafter. The major contribution of our paper is that we show that for random directional mesh networks there is an optimal power level which is necessary and sufficient for connectivity to be achieved. We show that the optimal power level for connectivity is equal to $\alpha ^* P_T^o$ where $\alpha ^* = \frac{1}{\gamma _G G(0)^2},$ G(0) being the maximum gain of an antenna with gain function G and $P_T^o$ being the optimal power level for connectivity of an omnidirectional antenna. The quantity $\gamma _G$ is a function of the gain pattern (as captured by the gain function G) and is defined as follows: it is the probability that a node u connects with another node v that is placed uniformly at random in a unit disc centred at u, assuming both nodes are equipped with randomly oriented antennas whose radiation pattern is described by gain function G, and that both antennas have a power level that allows them to communicate only up to a unit distance in the direction of maximum gain. Here, we note that G(0) increases as directionality increases (and, in fact, G(0) is a measure of the directionality of an antenna) while $\gamma _G$ decreases as directionality increases, but we show that the overall effect is such that the power level required for connectivity is much lower than that of omnidirectional antennas, i.e., $\alpha ^* \ll 1$.

Organization. In Sect. 2 we review the literature related to our work. Our model of directional mesh networks is presented in Sect. 3. We discuss the conditions for connectivity in Sect. 4. Our connectivity results are validated through simulations in Sect. 5. Finally we present our conclusions in Sect. 6.

2 Related Work

Connectivity in mesh networks using omnidirectional antennas has been studied in depth since the seminal work of Gupta and Kumar [11]. They proved that for m nodes with omnidirectional antennas randomly placed in a disc of unit area, if transmission power for all nodes was set such that each node could communicate with any other node in a circular vicinity of area $(\log m + c(m))/m$, then the network is asymptotically connected with probability 1 if and only if $c(m)\rightarrow \infty$ [11]. Our connectivity result, Theorem 1 is an analog of this result for the more complex setting where the antennas are highly directional. Our work on connectivity benefits from the general theorem proved by Bagchi et al. [1].

Connectivity was widely studied within the omnidirectional model in mobile ad hoc networks [14], in thin finite strips [3], under a physical model for interferences [9], and when nodes are active independently with a certain probability [19, 21]. Several authors have studied connectivity of mesh networks equipped with steerable directional antennas in contrast to our work which considers non-steerable antennas. Kranakis et al. consider sensors deployed on a unit line and unit square with steerable directional antennas [12]. Given a set of nodes on a plane, each with a directional antenna, modeled as a sector, Caragiannis et al. investigated the problem of orienting the antennas to get a connected network [5]. Carmi et al. model the communication area of a steerable directional antenna as a wedge of infinite area which captures its directionality [6] and show that a sixty degree directional antenna suffices to form a connected network for arbitrarily located nodes. Xu et al. study the problem of connectivity through simulations when each node is equipped with several different directional antennas oriented uniformly in a circular fashion [20]. Yu et al. consider the problem of placement of wireless sensor nodes, with a view to ensuring connectivity and coverage [22]. In our work node placement is random. Bettstetter et al. considered a scenario of nodes deployed over a finite area and equipped with linear and circular antenna arrays used for random beamforming [4], demonstrating that increasing directionality leads to larger connected components. Our theoretical results support their experimental findings on connectivity.

Li et al. study asymptotic connectivity in a similar network scenario as ours [13]. Although they conjecture the same result as Theorem 1 of our paper their analysis suffers from a critical flaw. In the proof of their main theorem they use a theorem of Penrose, Theorem 3 of [16], which states that in a high density setting all the nodes of a random geometric graph are either isolated or part of a connected component almost surely. However, Penrose makes it clear that this result holds only for the case where each edge is formed independently of all others which is clearly not true here (see Sect. 3). Additionally they critically need the condition that in the random geometric graph formed by directional antennas in the infinite plane, when the density is supercritical the giant component is unique. For this they cite Theorem 6.3 from Meester and Roy [15], which also applies only if the independence assumption holds. We will see in Sect. 3 that the independence assumption does not hold in our setting.

3 Modeling Directional Mesh Networks

Directional Antennas. The power received by a receiving antenna, $P_{R_x}$, at distance r from a transmitting antenna that is transmitting at wavelength $\lambda$ with power $P_{T_x}$ is described by the Friis transmission equation:

$$\begin{aligned} P_{R_x} = P_{T_x}G_{R_x}G_{T_x}\left( \frac{\lambda }{4\pi r}\right) ^2, \end{aligned}$$

(1)

where $G_{R_x}$ and $G_{T_x}$ are the receiver and transmitters gains and depend on the orientations of the two antennas. For highly directional antennas these gains can be very high since these antennas tend to concentrate their beams in one direction. Gain is formally defined as the ratio of the power radiated in a given direction per unit solid angle to the average power radiated per unit solid angle, (c.f., e.g., [2, 17]).

Although the gain function depends on both the polar and azimuthal angles in 3 dimensions we will assume for ease of presentation that the gain function $G: [-\pi ,\pi ] \rightarrow \mathbb {R}_+ \cup \{0\}$ is defined over two dimensions, i.e., depends only on the azimuthal angle. We note that our methods are general and can be transposed to 3 dimensions with suitable modifications. We assume that our gain function has the following properties: (Directionality) $G(\psi ) = 0$ for $|\psi | \ge \pi /2$. (Symmetry around angle of orientation) $G(\psi ) = G(-\psi )$. (Monotonicity) $G(\psi ) > G(\psi ')$ whenever $|\psi | < |\psi '|$. The assumption that G takes non-zero values only in $[-\pi /2,\pi /2]$ neglects back-lobe transmission, which is a simplification we make for ease of presentation. From these properties we can additionally deduce that $G(\cdot )$ reaches its maximum value at 0. Also $G(\cdot )$ is not an invertible function, since it is not one-to-one. So we follow the convention, similar to that of inverse trigonometric functions, that $G^{-1}(x)$ is a positive valued function i.e. if $G(\psi ) = x$ then we say that $G^{-1}(x) = |\psi |$. Also, by the reciprocity principle it is known that the receiver gain and transmitter gain of an antenna are identical. In this paper we will deal with settings where all antennas are considered identical to each other and so we will consider only one single gain function at a time.

A Realistic Directional Fading Model. In a realistic antenna setting the gain decreases as we move away from the angle of orientation of the antenna. In this paper we will work with a family of gain functions that satisfy this property. We will refer to this model as the directional fading model or simply the fading model. This family of functions, which has been mentioned in the antenna theory literature as being of particular interest [2, 17], is:

$$\begin{aligned} G_f^{n}(\psi ) = \left\{ \begin{array}{l l} G_f^{n}(0) \cos ^n (\psi ) &{} \quad 0 \le |\psi | \le \frac{\pi }{2},\\ 0 &{} \quad |\psi | \ge \frac{\pi }{2}, \end{array} \right. \end{aligned}$$

(2)

where n takes even values and the f in the subscript of $G_f$ is to indicate the “fading” model and differentiate it from the ideal model we will also study (see below). The angle $\psi$ is relative to the angle of orientation of the antenna. Since, by the definition of gain, the integral of gain over the unit sphere should be $4\pi$, we can compute the normalization constant $G_f^{n}(0)$ for this family. We omit the exact calculation here only noting that in general $2n + 1$ is a reasonable approximation of $G_f^{n}(0)$ as n grows.

From now on, we simply denote the realistic gain function $G_f^n(\cdot )$ by $G(\cdot )$.

The Ideal Directional Model. As a theoretical counterpoint we introduce a simple idealised directional gain function that captures the idea of a beam of width $2\theta$ centred at the angle of orientation. The gain everywhere is a uniform non-zero value within this beam is and zero everywhere outside. We denote the ideal gain function $G_i^{\theta }(\cdot )$, using the subscript i for “ideal” to differentiate it from the fading model above. This gain function can be explicitly computed by integrating the uniform gain over the surface of the sphere centred at the antenna and equating this value to $4\pi$. By doing this we find.

$$\begin{aligned} G_i^\theta (\psi ) = \left\{ \begin{array}{l l} \frac{2}{1 - \cos (\theta )} &{} \quad 0 \le |\psi | \le \theta ,\\ 0 &{} \quad |\psi | > \theta , \end{array} \right. \end{aligned}$$

(3)

The Power Parameter $\alpha$ and Radius of Connectivity. In the omnidirectional case under the assumption of uniform unit gain in all directions, Gupta and Kumar showed that in the setting where m nodes are distributed uniformly at random in a unit disc and if each node can communicate with another node at distance r from it, then, the random graph thus formed is connected with probability tending to 1 as $m \rightarrow \infty$ if and only if the radius within which two nodes can communicate is

$$\begin{aligned} r_o(m) = \sqrt{\frac{\log (m) + c(m)}{m\pi }} \end{aligned}$$

(4)

where $c(m) \rightarrow \infty$ as $m \rightarrow \infty$ [10]. In the following when the number of nodes m is understood, we will often just use $r_o$ to denote this radius.

Restating this in terms of power, using the Friis transmission equation, we can say that if $P^*_R$ is the minimum received power required for the signal to be correctly received, then, since $G_{R_x} = G_{T_x} = 1$, the omnidirectional transmission power required is

$$\begin{aligned} P_T^o = P^*_R \left( \frac{4\pi r_o}{\lambda } \right) ^2. \end{aligned}$$

(5)

In this paper we will use this value of $P_T^o$ as a scaling constant for the transmission power used, and $r_o$ as a scaling constant for distances. In particular we will say that the transmission power used by our directional antennas is $P_T^d = \alpha P_T^o$.

We will use $\alpha$ as a parameter to tune the antenna transmission power for the rest of this paper. To find the furthest distance, $r_G(\alpha )$, that an antenna u with gain function $G(\cdot )$ and power parameter $\alpha$ can communicate we have to find the largest x such that the power received by an antenna v which is at distance x from the transmitting antenna u is at least $P^*_R$, i.e., we have to find x such that

$$\begin{aligned} \max _{\beta _1,\beta _2 \in [-\pi /2,\pi /2]} P_T^d G(\beta _1) G(\beta _2) \left( \frac{\lambda }{4\pi x}\right) ^2 \ge P^*_R \end{aligned}$$

(6)

where $\beta _1$ is the angle between the ray defining the angle of orientation of the transmitter and the line segment $u \rightarrow v$ and $\beta _2$ is defined analogously for the receiver (see Fig. 1.) Solving this by putting the values of $P_R^*$ and $P_T^d$, and observing that $G(\cdot )$ is maximised at G(0) by definition, we get that

$$\begin{aligned} r_G(\alpha ) = \sqrt{\alpha } \cdot G(0) \cdot r_o. \end{aligned}$$

(7)

Hence by varying $\alpha$ we can control the distance to which the connections can be made. Note that the maximum distances for the two models can be derived by using the values of $G_f^n(0)$ and $G_i^\theta (0)$.

Fig. 1.

Connecting transmitter to receiver.

Random Orientations and Connectivity Probability. Unlike in the simple RGG model studied by Gupta and Kumar [10], connectivity between two antennas in the directional setting does not depend only on the distance between them, it also depends on their angles of orientation. We now study the situation where the antennas are located in the 2-d plane and each antenna picks its angle of orientation uniformly at random from $[0,2\pi ]$.

Assuming that the receiver has fixed its angle of orientation ($\beta _2$ relative to the line joining receiver to transmitter) we compute the probability of connectivity at distance r by integrating over the range of values of the angle of orientation of the transmitter, $\beta _1$, within which the received power is at least $P_R^*$. This gives us:

$$\begin{aligned} g_G(r) = \int \limits _{-G^{-1}\left( \frac{r^2}{\alpha r_o^2\cdot G(0)}\right) }^{G^{-1}\left( \frac{r^2}{\alpha r_o^2\cdot G(0)}\right) } \frac{1}{2\pi ^2} \cdot G^{-1}\left( \frac{r^2}{\alpha r_o^2\cdot G(\beta _1)}\right) d\beta _1. \end{aligned}$$

(8)

The above function is non-trivial to compute in the fading model, but in the ideal directional model, under the gain function $G^\theta _i(\cdot )$ it reduces to

$$\begin{aligned} g_{G^\theta _i}(r) = \left\{ \begin{array}{l l} \frac{\theta ^2}{\pi ^2} &{} \quad 0 < r \le \sqrt{\alpha } \cdot \frac{2}{1 - \cos (\theta )}\cdot r_o ,\\ 0 &{} \quad \text{ otherwise, } \end{array} \right. \end{aligned}$$

(9)

This is simply the probability that the receiver lies in a randomly chosen sector of radius $r_i(\alpha )$ with angle $2\theta$ centred at the transmitter and vice-versa.

We also compute the probability, $\gamma _G$, that a node u connects with another node v that is placed uniformly at random in the disc of radius $r_f(\alpha ) = \sqrt{\alpha } G(0) r_o$ centred at u in the realistic fading model. This quantity is going to be critical in our study of network connectivity (Sect. 4). Conditioning on the position of u and integrating over the disc we get

$$\begin{aligned} \gamma _G = \int _{x=0}^{\sqrt{\alpha }r_o G(0)} g_G(x) \frac{2x}{\alpha r_o^2 G(0)^2} dx. \end{aligned}$$

(10)

An important point to note here is that $\gamma _G$ does not depend on $\alpha$ as long as $\alpha >0$. This can be seen by changing variables in (10), replacing x with z where $x = \sqrt{\alpha } r_o z$.

For the ideal model we compute the probability, $\gamma _{G_i}$, that a node u connects with another node v that is placed uniformly at random in the disc of radius $r_i(\alpha ) = \sqrt{\alpha } G_i^{\theta }(0) r_o$ centred at u. By substituting in Eq. 10 the probability of connectivity at distance x, i.e., $g_{G^\theta _i}(x)$ given by Eq. 9, we get $\gamma _{G_i}=\theta ^2/\pi ^2$.

A Random Graph Model. We model a mesh network of directional antennas as a random geometric graph, $H = (V,E)$, whose nodes are distributed uniformly at random in a unit disc in $\mathbb {R}^2$. Each node $u \in V$ is equipped with a directional antenna that chooses its angle of orientation $\xi _u$ uniformly at random from $[0,2\pi ]$ independently of all other nodes. The other parameters of the model are a power level $\alpha$ as defined in Sect. 3 and a gain function $G(\cdot )$.

For convenience we will use the following notation to refer to random graphs modeling networks using the directional fading and ideal directional model:

• $\text {DF-RGG}(m,n,\alpha )$: a random graph formed as above on m nodes with $G = G_f^{n}(\cdot )$ and power parameter $\alpha$, briefly DF-RGG when the parameter values are understood.

• $\text {DI-RGG}(m,\theta ,\alpha )$: a random graph formed as above on m nodes with $G = G_i^{\theta }(\cdot )$ and power parameter $\alpha$, briefly DI-RGG.

The Edge-Independence Assumption does not Hold. To show this let us consider the simpler ideal model. Assume there are three nodes x, y and z which are placed such that their pairwise distances are all equal to some $r>0$, i.e. they are placed at the vertices of an equilateral triangle of side length r. Consider a value of $\theta$ that is smaller than 30 degrees and an $\alpha$ large enough to ensure that each pair can communicate if the antenna orientations are correct. For a given pair of nodes, say x, y, the probability that they are connected is $\theta ^2/\pi ^2$. But clearly the probability of all three pairs being connected is 0 which is less than $\theta ^6/\pi ^6$ which is what it would have been if the probabilities of the edges being formed were independent. Hence, we find that the independence assumption does not hold and so the theory developed under this assumption cannot be used in this case as has been done by Li et al. [13]. We will now show how this problem can be handled.

4 Connectivity

In this section we show that highly directional antennas achieve network connectivity at a much lower power level than omnidirectional antennas. This is a somewhat counterintuitive result that we feel has major implications for the design of mesh networks.

A Connectivity Theorem for Directional Random Mesh Networks. We now present our main theorem on connectivity. The key factor in this theorem is the probability of connectivity $\gamma _G$ associated with an antenna with gain function G. As we showed in Sect. 3, this probability is independent of the transmission power and hence is a property of the antenna model alone and depends only on the gain function G. Our main theorem is:

Theorem 1

Suppose we are given a set V of m nodes distributed uniformly at random in a unit disc B of $\mathbb {R}^2$ and each node is equipped with an antenna with gain function G that is (a) non-zero in $[-\pi ,\pi ]$, (b) symmetric around the angle of orientation and (c) monotonically decreasing away from the angle of orientation. Assume that each antenna has transmission power that allows it to transmit to a distance of $r > 0$ in its direction of maximum gain. Denote by $\gamma _G$ the probability that two nodes that lie within distance r of each other are connected.

We construct a random graph model $\text {D-RGG}(m,G,r)$ by placing edges between each pair of points that can communicate with each other, and for this we have that $\text{ P }(\text {D-RGG}(m,G, r) \text{ is } \text{ connected })\rightarrow 1$ as $m \rightarrow \infty$ if and only if

$$\begin{aligned} \pi r(m)^2 \gamma _G = (\log m + c(m))/m, \end{aligned}$$

(11)

where $\lim _{m \rightarrow \infty } c(m) = \infty$ as $m \rightarrow \infty$.

Due to shortage of space we omit the proof of this theorem. We note that the optimal radius suggested by Theorem 1 is simply the optimal radius for omnidirectional antennas given by Gupta and Kumar [11] scaled by a factor of $1/\sqrt{\gamma _G}$. This implies that the radius of connectivity is larger than that for omnidirectional antennas, since $\gamma _G <1$, and appears to run counter to our claim that random directional mesh networks require lower power. However, as we have already seen the directionality of an antenna means that it can achieve a much larger transmission range, at least in the direction of orientation, and so we will find that the power required is much lower than that required for omnidirectional antennas.

Fig. 2.

Optimal power level vs model parameters for (b) the ideal model (parameter $\theta$) and (a) the fading model (parameter n).

Optimal Power for Connectivity. From Theorem 1 we deduce that the optimal radius $r_d$ of connectivity of the directional model with gain function G is given by $r_d = r_o/\sqrt{\gamma _G}$. The power level $\alpha$ that reaches the maximum distance $\sqrt{\alpha }G(0)r_o$ equal to $r_d$ will be called the optimal power level $\alpha ^*$ and is given in the fading and ideal model by, respectively:

In Fig. 2, after computing $\gamma _{f}(n)$ numerically for $n = 16, 32, 64, \ldots , 8192$, we plot $\alpha _f^*(n)$ versus n and $\alpha _i^*(\theta )$ versus $\theta$. It is worth noting that $\alpha ^*$ depends on n in the fading model and on $\theta$ in the ideal model. Since the gain in the direction of orientation is a measure of how “directional” the antenna beam is, i.e., how concentrated the signal is in the direction of orientation, the inverse relationship of the optimal power level to $G(0)^2$ implies that the power level required for connectivity decreases as the directionality of the antenna increases.

Table 1. The parameter n, associated angle $\theta (n)$ and corresponding optimal power levels and connectivity probabilities.

Comparing the Ideal Model and the Fading Model. It is not a priori clear how to determine which of the two models, ideal or fading, is more power efficient. In order to compare them, we propose to study the half-power beamwidth (or, simply, the halfbeam) for antennas with realistic gain function [17].

For an antenna of parameter n, the halfbeam is defined as the angle $2 \chi$ between the two directions in which the gain $G_f^n(\chi )$ is one half the maximum value, that is, $\chi$ such that $G_f^n(\chi )=\frac{1}{2}G_f^n(0)\cos ^n(0)$. Solving the above equation, we obtain that the halfbeam of an antenna of parameter n is the angle $2\chi =2 \cos ^{-1}\left( \root n \of {1/2}\right)$. Thus, we associate the fading model whose gain function has parameter n to the ideal model of parameter $\theta (n)=\cos ^{-1}\left( \root n \of {1/2}\right)$.

With this correspondence, we report the optimal power levels in Table 1: we compute $\alpha ^{*}_i(\theta (n))$ by recalling $\gamma _{G_i}=\theta ^2/\pi ^2$ and using Eq. 3. After computing $\gamma _G$ by numerical integration (see Eq. 10), we derive $\alpha ^{*}_f(n)$ using Eq. 2. Note that the values of $\alpha ^*_i(n)$ in Table 1 zoom into Fig. 2b since $\theta (n)$ lies in [0.74, 16.74].

In Table 1 we report the connectivity probabilities of the fading model with different values of the parameter n and those the associated DI-RGG, i.e. the ideal model with parameter $\theta (n)$. As we see, they almost coincide thus validating the engineering intuition that guided us in making this association. This connectivity probability is for a pair of points but when we come to network-wide connectivity the models differ: the optimal power level for DI-RGG is about half of that for the corresponding version of DF-RGG. This is because each DI-RGG antenna covers at a smaller area (i.e., halfbeam) than the one considered in DF-RGG but with a better (uniform) gain value. This shows that for network connectivity the halfbeam assumption is overly optimistic and gives us lower power levels than required. Nevertheless for all values of n the optimal power for the fading model is double that of the ideal model, and we can state as a rule of thumb that $\alpha ^*_f(n)=2 \alpha ^*_i(\theta (n))$. This is an important input for the design of a connected directional mesh in which the directional antennas transmit at power level at most $\alpha$.

Fig. 3.

The percentage of connectivity versus $\alpha$ in the fading model.

5 Simulation Results for the Fading and Ideal Models

In this section we experimentally test our results on connectivity in directional meshes. We built our own simulator and we ran the experiments on a 2.2 GHz Intel i3 processor with 4 GB of main memory. We implemented the algorithm in C++. We followed the communication model for the DF-RGGs and DI-RGGs described in Sect. 3. Our main metric in this study is what we call the percentage of connectivity or connectivity percentage, which is defined as the percentage of nodes in the largest connected component. First we validate our main result on the optimal power level for the fading model. Figure 3 shows the percentage of connectivity versus power level $\alpha$ for several values of the fading parameter n. For each value of n, the optimal power level $\alpha _f^*(n)$ is highlighted with a small cross. As one can see, whenever $n \le 4096$, the optimal power level derived in Eq. 12 is very accurate. Indeed, at $\alpha _f^*(n)$, the percentage of connectivity reaches the maximum value and after that, it remains stable. In other words, extra power would not significantly improve the connectivity. For $n=8192$, $\alpha _f^*(8192)$ is less accurate since the percentage of connectivity increases for $\alpha > \alpha _f^*(8192)$. This eventually shows that the connectivity probability is slightly overestimated in such extreme value of n. The remaining experiments test the percentage of connectivity in DF-RGG and DI-RGG at the optimal power level $\alpha ^*$, reported in Table 1. Figure 4 shows that the percentage of connectivity achieved in directional mesh is high and comparable to that of omnidirectional mesh, although the power used by directional models is well below $P_T^o$ which is conventionally set to 1 in our experiments. It also appears that for a more directional model to achieve a high connectivity percentage, we need a higher density than we need for a less directional model. Nonetheless, it is interesting to point out that when m is small, moderate directionality may achieve higher connectivity than omnidirectional networks, i.e., reaching further nodes within a (sufficiently wide) sector is more effective for achieving connectivity than reaching nodes that do not lie as far but are located all around the antenna. We then verified whether the power level derived by Eqs. 12 and 13 is necessary for achieving connectivity. For this purpose, we varied the connectivity radius in Eq. 4 below the optimal threshold using $c(m)=\{-\log \log (m),$ $-\log ^2\log (m),$ $-2\sqrt{\log (m)}\}$. Changing c(m), the radius reduces from $r_o$ to r, and the directional optimal power level is scaled by factor $F=(\frac{r}{r_o})^2$. The scale coefficients F used in Fig. 5 for the three values of c(m) are $\{0.64984, 0.41382, 0.37443\}$. We take $m = 5\cdot 10^5$ here. We note in Fig. 5 that the more we decrease the power level, the greater the loss in connectivity. The trends of the connectivity curves are the same for all values of n, sharpening for higher values of n.

Fig. 4.

The percentage of connectivity when: (a) m varies, (b) n varies.

Fig. 5.

The percentage of connectivity vs c(m): (a) in DF-RGG (b) in DI-RGG.

6 Conclusions

In this paper we have argued that connected mesh networks can be built using directional antennas and that such mesh networks can operate with much lower power than mesh networks built with isotropic omnidirectional antennas. We have also demonstrated how a simple idealised gain function can be used to approach mesh network design where the antennas have a more realistic and complex gain function.