# Optimal Design for One-Dimensional ALOHA Ad Hoc Networks Based on Stochastic Geometry

Authors: Seunghee Lee; Ganguk Hwang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

The aims of this paper are to analyze the performance of a one-dimensional ALOHA ad hoc network and
to investigate the impact of the access probability of the ALOHA protocol on the network performance. As a performance metric we consider the average number of nodes that successfully receive a packet from an arbitrary node. To mathematically model the random locations of nodes and the interference in the ad hoc network, we use stochastic geometry theory. With the help of stochastic geometry theory, we model the ad hoc network, derive an analytic form of the performance metric, and finally obtain the optimal access probability that maximizes the performance metric. Numerical examples are provided to validate our analysis and to investigate the performance behavior.


---

## Body

## 1. Introduction

Ad hoc networks have been paid much attention because of their wide applications such as Mobile Ad Hoc Networks (MANETs) and Vehicular Ad Hoc Networks (VANETs). One of important design issues in ad hoc networks is to optimize the performance of wireless channel access protocols such as Carrier Sense Multiple Access (CSMA) and ALOHA. Even though many real ad hoc networks consider the CSMA protocol, the analysis of the CSMA is complex when we consider the interference in the network. On the other hand, the ALOHA protocol is simple to implement. Moreover, since the ALOHA protocol is a good approximation of the CSMA protocol, for example, from the viewpoint of throughput [1], and the analysis of the ALOHA protocol is relatively simple, ad hoc networks with the ALOHA protocol are widely considered and analyzed, for example [2, 3]. In fact, a recent simulation study in [4] shows that the behavior of CSMA appears similar to that of ALOHA as the network density becomes high and the analysis of dense VANETs with Aloha is performed to approximate the CSMA-based MAC protocol in [5].In this paper we consider a one-dimensional ad hoc network with the ALOHA protocol. The motivation of a one-dimensional network comes from its application to vehicular networks where vehicles are mostly located in a linear form. In the ALOHA protocol, each node having a packet in the network transmits independently with a given access probability, so that the performance of the ALOHA protocol is determined by the access probability. Hence, it is important to investigate the impact of the access probability on network performance of the ad hoc network, which is the objective of this paper.Bearing broadcast messages in mind, we consider a neighbor of an arbitrarily tagged node and focus on the average number of nodes in the neighbor that successfully receive a transmitted packet from the tagged node. To consider the random locations of nodes and the interference, we use stochastic geometry [6, 7], which is recently widely used in the analysis of wireless networks. Interference depends upon the path loss and the fading characteristics of wireless channels. Both of them can be interpreted as functions of the distance between users in the network, where stochastic geometry is involved. In the last decades, stochastic geometry and related techniques have attained so much interest among researchers in wireless network community. For its various applications, readers refer to [7–10] for cellular systems, [11] for ultrawideband, [12–16] for cognitive radio, [17, 18] for femtocells, and [19] for relay networks. For a comprehensive understanding, we refer the readers to a survey paper [20] and the references therein.Regarding the analysis of VANETs with the Aloha protocol based on stochastic geometry, [2, 3] analyze the performance of VANETs. While they derive the probability of packet capture at some distance in [2, 3], we focus on an arbitrary node, called the tagged node, in the ad hoc network and consider the number of nodes that successfully receive a packet transmitted from the tagged node as the performance metric. To compute the performance metric, we derive the conditional probability of packet capture at some distance, given the location of the nearest interfering node. Using the conditional probability we compute the average number of nodes that successfully receive a packet from the tagged node. Noting that the access probability of the Aloha protocol significantly affects our performance metric, we use our analytical result to find the optimal access probability of the Aloha protocol that maximizes the average number of nodes that successfully receive a transmitted packet.The remainder of this paper is organized as follows. In Section2 we describe our network model. In Section 3 we analyze the performance of the VANET with the Aloha protocol and formulate an optimization problem. In Section 4 we provide numerical and simulation results to validate our analysis and to investigate the performance behavior. In Section 5 we give our conclusions.


## 2. System Modeling

We consider a one-dimensional ad hoc network where nodes are located according to a homogeneous Poisson point process (PPP) with intensityλ. For wireless channel access, the time axis is divided into slots of equal size and each node uses the ALOHA protocol with access probability p (0<p<1); that is, each node independently transmits its packet with probability p at each slot. We assume that simultaneous packet transmissions from multiple nodes might result in interference at receiving nodes and that interfered packets are deemed lost. To focus on the performance of the ALOHA protocol in the one-dimensional ad hoc network, we further assume that there are no other sources of packet loss. Under our assumption, we use stochastic geometry to capture the locations of nodes and the interference in packet transmission. For wireless channels, we use the Rayleigh fading model.For our analysis, we tag an arbitrary node and call it the tagged node. Due to the reduced Palm distribution of a Poisson point process (PPP) [21], without loss of generality we assume that the tagged node is located at the origin and other nodes are located in the entire axis of one dimension according to a PPP Φ with intensity λ.Consider an arbitrary slot time and suppose that the tagged node transmits its packet at the slot time. LetΦa be the set of nodes that simultaneously transmit their packets at the slot time. The nodes in Φa are called active nodes. The nodes in Φia≔Φ∖Φa are called inactive nodes that try to receive packets at the slot time. Since packet transmissions are performed independently from node to node, we see that Φa is a PPP with thinned intensity λp [21]. Moreover, Φia is a PPP with thinned intensity λ(1-p) [21].Figure1 provides a snapshot of the one-dimensional ad hoc network in the positive direction when the tagged node at the origin transmits a packet. In the figure triangles denote active nodes and upside down triangles denote inactive nodes. So the set of triangles forms Φa and the set of upside down triangles forms Φia in the figure.Figure 1
A snapshot of the one-dimensional ad hoc network with active and inactive nodes in the range of100m.We assume that one packet is transmitted during a slot time and that each node always has a packet to transmit. From the perspective of broadcast packets, as a performance metric we consider the average number of nodes in the neighbor of the tagged node, denoted byE[Ns], that successfully receive the packet from the tagged node. If the tagged node transmits a packet in such a way that E[Ns] is optimized, then the broadcasting speed becomes fast, which is desirable. Furthermore, the maximization of E[Ns] prevents the case where the nearest active node from the tagged node is too much close, which is not desirable in the design of an ad hoc network.To be more specific in the definition ofE[Ns], we define the neighbor of the tagged node by the interval between the tagged node and the nearest active node from the tagged node in the positive direction. Then E[Ns] is defined by the number of inactive nodes in the neighbor of the tagged node that successfully receive a packet transmitted from the tagged node. The reasons why we consider only inactive nodes in the positive direction in this paper are explained as follows. First, information forwarding is performed in the positive direction in practice. In fact, inactive nodes had better receive packets from their own nearest active nodes in front of them when the information is related with a safety or emergency situation in front of them such as the stopped-vehicle hazard warning. Second, the analysis of the average number of inactive nodes in the negative direction is the same as given in the next section, so we focus on the positive direction in this paper. Third, we assume that a node cannot transmit and receive a packet simultaneously. So only inactive nodes near the tagged node (i.e., the inactive nodes that are located between the tagged node and the nearest active node) are considered in the performance metric E[Ns].


## 3. Performance Analysis and Optimization

In this section, we useE[Ns] as the performance metric of an ad hoc network with the ALOHA protocol and derive an analytic form of E[Ns] as a function of the access probability p. Then we find an optimal access probability p∗ that achieves the maximum value of E[Ns].We define the interference free distanceR as the distance such that any inactive node located within the distance from the tagged node can successfully receive the packet transmitted by the tagged node. To derive our performance metric, we first analyze R as follows.LetX be the location of the nearest active node. Since the set of active nodes Φa is a PPP with intensity λp, the probability density function of X is given by (1)fXx=λpe-λpx for x>0. Conditioned on X=x, suppose that there is an inactive node located at r (0<r<x).LetW denote the noise that is independent of the fading between nodes and α denote the path loss exponent. Then the signal to interference and noise ratio (SINR) at the inactive node at r is given by(2)F0/rαW+F1/x-rα+I++I-10<r<x.Here, F0 is the fading between the tagged node at the origin and the inactive node at r and F1 is the fading between the nearest active node at x and the inactive node at r. Moreover, I+ is the interference from all active nodes in the positive direction except the nearest active node, and I- is the interference from all active nodes in the negative direction.Correspondingly, letΦa+ be the set of active nodes in the positive direction except the nearest active node and let Φa- be the set of active nodes in the negative direction. Then the interferences I+ and I- are expressed as (3)I+=∑Xi+∈Φa+Fi+Xi++x-rα,I-=∑Yi-∈Φa-Fi-Yi-+rα,respectively. Here, Xi+ is the location of the ith nearest active node (from X=x) in Φa+ and Yi- is the location of the ith nearest active node in Φa-. Moreover, Fi+ is the fading between the ith nearest active node in Φa+ and the inactive node at r and Fi- is the fading between the ith nearest active node in Φa- and the inactive node at r. Then |Xi+| denotes the distance between X=x and Xi+ and |Yi-| denotes the distance between the origin and Yi-. Since we use the Rayleigh fading model, we assume that F0, F1, Fi+, and Fi- are independent exponential random variables with parameter μ. Note that 1/μ is the average transmission power.Assume that the inactive node can successfully receive the packet from the tagged node if its SINR value is greater than a thresholdθ. For the analysis of the interference free distance R, we have to consider the following important observation on the relation between the distance R and the location X of the nearest active node.Proposition 1.
LetX be the location of the nearest active node from the tagged node in the positive direction and let W be the exponential noise with mean 1/ν. Given that X=x, the conditional probability that R is greater than r is given by (4)PR>r∣X=x=νμθrα+ν·x-rαθrα+x-rαexp-λp∫0∞θrαθrα+t+x-rαdtexp-λp∫0∞θrαθrα+t+rαdtfor 0<r<x.Proof.
For0<r<X, observe first that (5)R>r=F0/rαW+F1/X-rα+I++I->θ. It then follows that (6)PR>rX=x=PF0/rαW+F1/x-rα+I++I->θ=PF0>θrαW+F1x-rα+I++I-=Ee-μθrαW+F1/x-rα+I++I-=aEe-μθrαWEe-μθrα/x-rαF1Ee-μθrαI+Ee-μθrαI-=νμθrα+ν·x1-rαθrα+x1-rα·LI+μθrα·LI-μθrα.Equality (a) in the above holds because W, F1, Fi+, and Fi- are mutually independent. The derivation of Laplace transform LI+(μθrα) of I+ is presented below. Consider (7)LI+μθrα=Ee-μθrα∑Xi+∈Φa+Fi+/Xi++x-rα=EΦa+∏Xi+∈Φa+EF+e-μθrαFi+/Xi++x-rα=EΦa+∏Xi+∈Φa+μμ+μθrα/Xi++x-rα=EΦa+∏Xi+∈Φa+Xi++x-rαXi++x-rα+θrα=exp⁡-λp∫0∞1-t+x-rαt+x-rα+θrαdt=exp⁡-λp∫0∞θrαt+x-rα+θrαdt.In the first equality, the expectation is taken over both the point process and the fading. Due to the independence in fading, the second equality holds. The third equality follows from the fact that (8)Ee-sF+=μμ+s.From Laplace functional of the homogeneous PPP Φa+ with intensity λp, we obtain the fifth equality.
Similarly, we derive Laplace transformLI-(μθrα) of I- as follows:(9)LI-μθrα=Ee-μθrα∑Yi-∈Φa-Fi-Yi-+rα=EΦa-∏Yi-∈Φa-EF-e-μθrαFi-Yi-+rα=EΦa-∏Yi-∈Φa-μμ+μθrα/Yi-+rα=EΦa-∏Yi-∈Φa-Yi-+rαYi-+rα+θrα=exp⁡-λp∫0∞1-t+rαt+rα+θrαdt=exp⁡-λp∫0∞θrαθrα+t+rαdt,where we use Laplace functional of the homogeneous PPP Φa- with intensity λp in the fifth equality.We are now ready to deriveE[Ns]. By the definition of R, note that the packet from the tagged node can be successfully received by an inactive node if the distance between the tagged node and the inactive node is not greater than R. Let Φia(s)[0,X] be the set of inactive nodes in the interval [0,X] that successfully receive the packet. Note that Φia is a PPP with intensity λ(1-p) and that an inactive node at r (0<r<X) successfully receives the packet from the tagged node with probability P{R>r∣X}. Let N(Φia(s)[0,X]) denote the number of nodes in Φia(s)[0,X]. Then Proposition 2 presents the analytic form of E[Ns].Proposition 2.
The average numberE[Ns] of nodes that successfully receive the packet from the tagged node is given by(10)ENs=λp21-p∫x=0∞∫r=0xνμθrα+ν·x-rαθrα+x-rαexp⁡-λp∫0∞θrαθrα+t+x-rαdtexp-λp∫0∞θrαθrα+t+rαdte-λpxdrdx.Proof.
From Proposition1 the desired result is obtained as follows: (11)ENs=PThetaggednodeisactiveENΦias0,X=p∫x=0∞ENΦias0,X∣X=xfXxdx=p∫x=0∞ENΦias0,x∣X=xfXxdx.
To obtain(12)ENΦias0,x∣X=x, we need to condition it on Φa+∪Φa- and compute (13)ENΦias0,x∣X=x=EENΦias0,x∣X=x,Φa+∪Φa-∣X=x because all transmissions from active nodes in Φa+∪Φa- simultaneously affect the packet receptions at the inactive nodes in Φia(s)[0,x] which causes correlations in the packet receptions at the inactive nodes. However, for a given Φa+∪Φa-, which implies that the locations of all active nodes are fixed, only the channel fading does matter in the packet receptions at the inactive nodes. Noting that the fading in a channel is assumed to be independent of all the other channels, the inactive nodes in Φia(s)[0,x] that successfully receive the packet from the tagged node form a (location dependent) thinned Poisson point process with thinning probability P{R>r∣X=x,Φa+∪Φa-}. Hence, we have (14)ENΦias0,x∣X=x,Φa+∪Φa-=∫r=0xλ1-pPR>r∣X=x,Φa+∪Φa-dr.It then follows that (15)ENΦias0,x∣X=x=EENΦias0,x∣X=x,Φa+∪Φa-∣X=x=E∫r=0xλ1-pPR>r∣X=x,Φa+∪Φa-dr∣X=x=∫r=0xλ1-pEPR>r∣X=x,Φa+∪Φa-∣X=xdr=∫r=0xλ1-pPR>r∣X=xdr. Combining the above two results together we get (16)ENs=p∫x=0∞ENΦias0,X∣X=xfXxdx=p∫x=0∞∫r=0xλ1-pPR>r∣X=xdrfXxdx=λp21-p∫x=0∞∫r=0xνμθrα+ν·x-rαθrα+x-rαexp⁡-λp∫0∞θrαθrα+t+x-rαdtexp⁡-λp∫0∞θrαθrα+t+rαdte-λpxdrdx.Observe that if the access probabilityp is too large, then the active nodes transmitting packets are likely to be close and hence most of their transmission ranges are overlapped, which results in decreasing E[Ns] due to severe interference. On the other hand, if the access probability p is too small, then E[Ns] is also degraded due to low packet transmission opportunity for each node. So it is important to find the optimal access probability p∗ that maximizes E[Ns].With the above observation, we formulate an optimization problem to obtain the optimal access probabilityp∗. However, before we provide our optimization problem we should mention a remark on the feasible region on the access probability p. According to the technical report of NHTSA [22], the required broadcast packet latency is set to be 100 msec. To satisfy the requirement on average in our model and to bear in mind that there are 100 msec/one slot time slots during 100 msec, each node should send at least one packet with the access probability of (17)pmin=oneslottime100msec. So the feasible region of the access probability p is pmin<p<1. With the feasible region of p our optimization problem is formulated as follows: (18)p∗≔argmaxpmin<p<1⁡ENs.


## 4. Numerical Results

In this section we provide numerical and simulation results to validate our analysis. The simulation is conducted using MATLAB. The procedure is summarized as follows. First, we generate a Poisson random variable and set it to be the total number of nodes. The locations of nodes are independently generated by using a uniform random variable over the observation window. Next, we classify each node as active with probabilityp and inactive with probability 1-p, and each fading power between nodes is independently generated by using an exponential random variable. When the tagged node is active, pick up the nearest active node from the tagged node at the origin in the positive direction, and we only consider inactive nodes between the nearest active node and the tagged node, as explained before. Then we compute the SINR value for each inactive node considered and check whether the inactive node receives the packet successfully. Consequently, Ns is computed. The whole procedure is repeated 5×105 times so that the desired throughput E[Ns] is obtained.We first validate our result on the average numberE[Ns] of inactive nodes with successful packet reception and then find the optimal access probability p∗. We use the following parameters throughout this section which are adopted from [3]:(i)
The intensity of the network:λ=0.01 nodes/m.(ii)
The average of transmission power:1/μ=1W.(iii)
The path loss exponent:α=4.(iv)
The success threshold:θ=10dB.(v)
The observation window:10km.We use Proposition2 to compute E[Ns] and plot it in Figures 2 and 3 as we change the access probability p. We consider a zero-mean additive white Gaussian noise (AWGN) in this paper, which is widely used to model a noise in most of communication systems [23]. In this case, the power of the noise is exponentially distributed; that is, W follows an exponential distribution with parameter ν. Here, 1/ν indicates the average noise power. The exponential noise is also considered in [24, 25]. In Figure 2 we use 1/ν=10-10 mW and in Figure 3 we use 1/ν=10-6 mW. We also plot the simulation results in the figures. As can be seen in the figures, there exists the optimal access probability p∗ that maximizes our performance metric E[Ns]. In addition, we see from the figures that our analytical and simulation results are well matched, which shows the validity of our analysis. Another important observation from the figures is that the impact of the noise power is significant. That is, when the average noise power is very small such as 10-10 mW, the optimal access probability p∗ is very small. On the other hand, when the average noise power is not small such as 10-6 mW, the optimal access probability becomes large, that is, greater than 0.3.Figure 2
The average number of nodes that successfully receive the packet from the tagged node (W is exponential with mean 10-10 mW).Figure 3
The average number of nodes that successfully receive the packet from the tagged node (W is exponential with mean 10-6mW).We next investigate the behavior ofE[Ns] when we change the intensity λ of the PPP. We first fix p to be 0.1, 0.2, and 0.3, and we plot E[Ns] versus λ for each fixed p in Figure 4. From the figure, we see that E[Ns] increases rapidly for small values of λ, but it becomes almost invariant soon in λ. We see a similar behavior of E[Ns] when we use the optimal access probability p∗:=p∗(λ) for each λ, which is plotted in Figure 5.Figure 4
The average number of nodes that successfully receive the packet from the tagged node versus the intensity of network for fixed access probabilities.Figure 5
The average number of nodes that successfully receive the packet from the tagged node versus the intensity of network for optimal access probabilities.This is an interesting and useful result in practice. Consider the situation in an ad hoc network where the intensity of nodes is rapidly changing in time. In this case, since it is very difficult to adapt the access probability optimally according to the fast change in intensity, a fixed access probability is likely be used. Then, if the intensityλ is not too small, then the result in the figures concludes that it suffices to find an optimal access probability from which E[Ns] becomes almost invariant. For instance, for the ad hoc network we consider in this section we recommend p∗=0.1 for λ>0.1.However, when the intensityλ is small, for example, less than 0.1, the access probability should be adapted according to the change in intensity to achieve the optimal performance. In fact, the optimal access probability becomes larger as λ decreases.


## 5. Conclusions

In this paper we considered a one-dimensional ad hoc network with the ALOHA protocol. We used stochastic geometry theory to analyze the performance of the network. As a performance metric we considered the average number of inactive nodes that successfully receive a packet from an arbitrary node and derived an analytic form of the performance metric. With our analysis we formulated an optimization problem to obtain the optimal access probability that achieves the optimal performance. Our numerical and simulation studies showed the validity of our analysis. We also investigated the performance behavior of the ad hoc network with the ALOHA protocol.



---

*Source: 934671-2015-09-20.xml*