The Effects of Topology on Throughput Capacity of Large Scale Wireless Networks

Abstract

In this paper, we jointly consider the inhomogeneity and spatial dimension in large scale wireless networks. We study the effects of topology on the throughput capacity. This problem is inherently difficult since it is complex to handle the interference caused by simultaneous transmission. To solve this problem, we, according to the inhomogeneity of topology, divide the transmission into intra-cluster transmission and inter-cluster transmission. For the intra-cluster transmission, a spheroidal percolation model is constructed. The spheroidal percolation model guarantees a constant rate when a power control strategy is adopted. We also propose a cube percolation mode for the inter-cluster transmission. Different from the spheroidal percolation model, a constant transmission rate can be achieved without power control. For both transmissions, we propose a routing scheme with five phases. By comparing the achievable rate of each phase, we get the rate bottleneck, which is the throughput capacity of the network.

1. Introduction

Wireless ad hoc networks consist of a group of nodes. Each node communicates with each other over a wireless channel with the help of relay nodes. The lack of any centralized control and possible node mobility cause many issues in the network. The main problem is that of network capacity. Network capacity has been a hot issue in the past few years, and tremendous efforts have been made related to the capacity of wireless networks. Gupta and Kumar [1] started the research on the capacity of large scale wireless networks and provided ground-breaking results on the scaling law of wireless network capacity. They considered a unit area network consisting of n nodes uniformly distributed. By the rigorous derivation, a per-node transport capacity $\mathsf{\Theta }\left(\frac{1}{\sqrt{n}}\right)$ (Given two functions $f\left(n\right)$ and $g\left(n\right)$: $f\left(n\right)=o\left(g\right(n\left)\right)$ means ${lim}_{n\to \infty }\frac{f\left(n\right)}{g\left(n\right)}=0$; $f\left(n\right)=O\left(g\right(n\left)\right)$ means ${lim}_{n\to \infty }\frac{f\left(n\right)}{g\left(n\right)}=c<\infty$; if $g\left(n\right)=O\left(f\right(n\left)\right)$, $f\left(n\right)=\mathsf{\Omega }\left(g\right(n\left)\right)$ with high probability (w.h.p.); if both $f\left(n\right)=\mathsf{\Omega }\left(g\right(n\left)\right)$ and $f\left(n\right)=O\left(g\right(n\left)\right)$, $f\left(n\right)=\mathsf{\Theta }\left(g\right(n\left)\right)$; $f\left(n\right)=\tilde{\mathsf{\Theta }}\left(g\left(n\right)\right)$ means $f\left(n\right)=\mathsf{\Theta }\left(g\right(n\left)\right)$ when logarithmic term is ignored.) was obtained in arbitrary ad hoc networks. For the random ad hoc networks, an achievable per-node throughput capacity was $\mathsf{\Theta }\left(\frac{1}{\sqrt{nlogn}}\right)$. These results indicated that the per-node rate decreased when the number of nodes increased. After that, Franceschetti et al. [2] exploited percolation theory to wireless ad hoc network and showed that a per-node rate $\mathsf{\Theta }\left(\frac{1}{\sqrt{n}}\right)$ was achievable, which improved Kumar’s [1] by an order of $\mathsf{\Theta }\left(\sqrt{logn}\right)$. Motivated by their works, studies on network capacity of some specific networks such as cognitive network [3] hybrid network [4] and mobile wireless Ad hoc networks [5] were conducted.

In the seminal works of network capacity [1,2], the authors only considered the uniformly network topology, and each node randomly and uniformly selected a destination. They did not consider the impact of other factors, such as traffic patterns, transmission models and node attributes. Wang et al. [6] analyzed the impact of social interaction on the throughput capacity of wireless network. Later, Liu et al. [7] considered that the node is selfish and derived the throughput capacity of wireless networks under various extents of selfish via percolation theory. Since the results of throughput capacity were pessimistic, Liu [8] proposed a strategy to improve the throughput capacity by physical layer caching. Recently, Jeong [9] introduced infrastructure into the network, and the throughput was increased dramatically if the amount of infrastructure was larger than a threshold. Except for the above works which focused on homogeneous wireless ad hoc networks, many researchers turned their attention to the heterogeneous networks. In particular, Alfnao et al. [10] considered the nodes distributed according to the Shot Noise Cox Process (SNCP) [11] and obtained the upper bounds of throughput capacity using a combination of geometric and percolation arguments. Later, they further optimized [10] by employing a layered scheduling and complicated routing schemes [12].

However, most works are only conducted over the planar networks. With the development of network technology, wireless networks are expected to extend from two-dimensional space to three-dimensional space, connecting all kinds of objects such as sensors, computers, mobile phones, etc. The future three-dimensional wireless networks will be a fusion of the digital world and the physical world and bring together everything from individuals to objects, from data to services, etc. For example, in modern battlefields, three-dimensional wireless networks need to be deployed to connect various military units together, like aircrafts, troops, and fleets. Hence, it is necessary to develop the throughput capacity of three-dimensional wireless networks. Actually, there are some studies that have been done on throughput and routing protocol of three-dimensional wireless networks. Huang et al. [13] and Qing [14] investigated the throughput capacity and routing protocol of three-dimensional wireless networks, respectively. Gao et al. [15] analyzed the throughput of three-dimensional wireless networks via constructing a backbone routing scheme. The connectivity of three-dimensional wireless networks is analyzed in [16]. For the large scale three-dimensional wireless network, Gupta and Kumar [17] derived the transport capacity of three-dimensional arbitrary ad hoc networks and the throughput capacity of three-dimensional random ad hoc networks using both Physical Model and Protocol Model. After that, Hu et al. [18] obtained an achievable throughput capacity of three-dimensional wireless networks via percolation theory. Later, Li et al. [19] investigated the throughput capacity of three-dimensional regular ad hoc networks by employing a generalized physical model. Nevertheless, all of the research mentioned above focused on the homogeneous three-dimensional wireless network. Study of throughput capacity on heterogeneous three-dimensional wireless networks is still not involved, since the inhomogeneity would influence the through capacity significantly.

In this paper, we explore the achievable throughput capacity of three-dimensional heterogeneous wireless ad hoc networks via percolation theory [20,21]. Due to the heterogeneity of network topology, we establish a spheroidal percolation model and some “information pipes” to analyze throughput capacity. Specifically, we consider that there are n nodes distributed in a three-dimensional cube with edge $L=\mathsf{\Theta }(n^{\frac{\gamma }{3}})$, and the network volume $A=\mathsf{\Theta }\left(n^{\gamma }\right)$, where $0\le \gamma \le 1$ is the parameter of network size, if $\gamma =0$, the network is a dense network, $\gamma =1$, and the network is an extended network. The distribution of the nodes is according to the Shot Noise Cox Process (SNCP), which is an inhomogeneous Poisson node process. According to the node’s distribution, we deploy m clusters in the network randomly and uniformly, where $m=\mathsf{\Theta }\left(n^v\right)$, $0\le v\le 1$. Due to the inhomogeneity of network topology, we divide the transmission into two parts: the intra-cluster transmission and the inter-cluster transmission. For the first part, we establish a spheroidal percolation model and propose a routing strategy with five phases. On the basis of spheroidal percolation model, an achievable rate of $\mathsf{\Omega }\left(1/{(n^{1-v}{((1-v)logn)}^2)}^{\frac{1}{3}}\right)$ in the intra-cluster transmission is achieved. While for the inter-cluster transmission, since the node density among the clusters is much lower, following the idea of homogeneous three-dimensional wireless networks, we establish some “information pipes” crossing each cluster. Using these “information pipes”, nodes located in different clusters can successfully communicate with each other. By a proposed routing scheme, we can get an achievable rate of $\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)$ over the inter-cluster transmission, where $\underline{\mathsf{\Phi }}$ is the minimum node density. If the traffic of network is also heterogeneous, i.e., a node would be inclined to select a destination located in the same cluster, then we conclude that the per-node rate of three-dimensional heterogeneous wireless ad hoc networks falls into an interval of $\left[\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right),\mathsf{\Omega }\left(1/{(n^{1-v}{((1-v)logn)}^2)}^{\frac{1}{3}}\right)\right]$.

The contributions of this paper can be summarized as follows:

• We firstly study the impact of inhomogeneity on the throughput capacity three-dimensional wireless networks.
• Due to the inhomogeneity of network topology, we put forward a novel spheroidal percolation model for the analysis of intra-cluster traffic, based on which the achievable rate of intra-cluster transmission is derived.
• While for the inter-cluster traffic, “information pipes” are built among the clusters to obtain the achievable rate of inter-cluster transmission.

The rest of this paper is organized as follows: Section 2 gives the network model and transmission model. In Section 3, we establish a spheroidal percolation model and give a routing strategy with five phases to derive the achievable rate of intra-cluster transmission. In Section 4, we construct some “information pipes” to get the rate of the inter-cluster transmission and then get the lower bound of the throughput capacity in Section 5. We finally conclude this paper in Section 6.

2. System Models

2.1. Network Model

We suppose that there are n nodes randomly distributed in a three-dimensional area with edge $L=\mathsf{\Theta }(n^{\frac{\gamma }{3}})$, where the network volume is $A=\mathsf{\Theta }\left(n^{\gamma }\right)$, where $0\le \gamma \le 1$ is the parameter of network size, if $\gamma =0$, the network is a dense network, and $\gamma =1$, the network is an extended network. Each node randomly chooses a destination to which it wishes to send packets. All nodes follow a heterogeneous distribution which is called the Shot Noise Cox Process (SNCP). The SNCP can be described briefly as follows: we assume there are M clusters randomly and uniformly scattered over the network area, where $E\left(M\right)=m$. Let $C={\left\{c_j\right\}}_{j=1}^M$ be the center points of these clusters. Each center point independently generates a point process with a density of $q_{j}k(c_j,\xi )$ at location ξ, where $k(c_j,·)$ is a dispersion density function and $q_j$ equals the average number of nodes contained by cluster $c_j$. We assume that all clusters consist of the same number of nodes; hence, $q_j=n/m$. Moreover, according to the SNCP, the density function Φ at area ξ can be written as :

$$\mathsf{\Phi }\left(\xi \right)=\sum _j{q}_{j}k(c_j,\xi ),$$

(1)

where $k(c_j,\xi )=k\left(\right||\xi -c_j\left|\right|)$ only depends on the Euclidean distance $\left|\right|\xi -c_j\left|\right|$ of location ξ from the cluster center $c_j$. In addition, the integral ${\int }_{A}k(c_j,\xi )d\xi$ over the network is finite. To simplify the model, we use function $s\left(\rho \right)$ to replace the density function $k(c_j,\xi )$, where $\rho =\left|\right|\xi -c_j\left|\right|$. In order to satisfy the finite integral over the network area, the function $s\left(\rho \right)$ is defined as follows:

$$s\left(\rho \right)=min(1,{\rho }^{-\delta }),$$

(2)

where δ denotes the heterogeneous exponent of $s\left(\rho \right)$ and $\delta >3$, since the integral of $s\left(\rho \right)$ over the network is finite.

In the large scale wireless network, we assume the average number of cluster centers scale as $m=\mathsf{\Theta }\left(n^v\right)$, with $v\in [0,1]$. Then, the number of nodes in each cluster is $\mathsf{\Theta }\left(n^{1-v}\right)$, i.e., $q_j=\mathsf{\Theta }\left(n^{1-v}\right)$ for $j=1,2,\cdots ,M$, since ${\int }_{A}k(c_j,\xi )d\xi$ is finite.

Let $d_c$ be the average distance between two neighboring cluster centers. Then, we have

$$d_c=\mathsf{\Theta }\left({\left(\frac{A}{m}\right)}^{\frac{1}{3}}\right)=\mathsf{\Theta }\left(n^{\frac{\gamma -v}{3}}\right).$$

(3)

Notice that if $\gamma <v$, the quantity $d_c\to 0$ as n goes to infinity. This case is called the cluster-dense regime, as shown in Figure 1a. On the contrary, if $\gamma >v$, the quantity $d_c\to \infty$. This case is named the cluster-sparse regime, as shown in Figure 1b. The network with the cluster-dense regime appears slightly heterogeneous and its capacity is similar to the homogeneous Poisson process (HPP) network. In this paper, we study the effects of topology and heterogeneity on the throughput capacity. Thus, we focus on the cluster-sparse model, i.e., $d_c\to \infty$. Correspondingly, let $\overline{\mathsf{\Phi }}$ and $\underline{\mathsf{\Phi }}$ denote the maximum node density and the minimum node density, respectively.

2.2. Transmission Model

We adopt the physical model [1] as the channel capacity between two nodes. Define $R_{ij}$ as the rate between transmitter node i to receiver node j. The data rate can be expressed as follows:

$$R_{ij}=log\left(1+\frac{P_i\ell (i,j)}{N_0+{\sum }_{\zeta \ne i}{P}_{\zeta }\ell (\zeta ,j)}\right)\mathrm{bit}/\mathrm{s},$$

(4)

where $\ell (i,j)$ represents the path loss between i and j, and we assume $\ell (i,j)=min\{1,1/d_{ij}^{\alpha }\}$ with $\alpha >3$. We also assume the physical link is over a unit bandwidth. $P_i$ is the transmission power of node i, $N_0$ stands for noise power of the channel at the receiver j, and ζ is the node which can transmit simultaneously with node i. $d_{i,j}$ is the transmission distance from node i to node j. In our strategy, we allocate different power for different nodes.

The per-node throughput capacity $R\left(n\right)$ is defined as the number of bits per second that, with high probability, (w.h.p.), all nodes can transmit to their intended destinations.

We summarize the notations in

Table 1. Notations.

Notation	Defination
n	The total number of nodes in the networks
L	Edge length of the network area
γ	Growth exponent of L: $L=\mathsf{\Theta }(n^{\frac{\gamma }{3}}),0\le \gamma \le 1$
m	Average number of cluster centers
v	Growth exponent of m: $m=\mathsf{\Theta }(n^v),0<v\le 1$
$q_j$	The number of nodes per cluster
$d_c$	Average distance between cluster centers: $d_c=\mathsf{\Theta }(n^{\frac{\gamma -v}{3}})$
$s\left(\rho \right)$	A dispersion density function
δ	Decay exponent of $s\left(\rho \right)$: $s\left(\rho \right)=min(1,{\rho }^{-\delta })$, $\delta >3$
$P_i$	The transmission power of node i
$\overline{\mathsf{\Phi }}$	The maximum node density
$\underline{\mathsf{\Phi }}$	The minimum node density
$R\left(n\right)$	Per-node throughput

.

3. The Intra-Cluster Transmission

3.1. The Spheroidal Percolation Model for Each Cluster

For the three-dimensional network model, we consider each cluster as a sphere that is divided by cones. The cones share the same vertex, i.e., the center of the cluster. As shown in Figure 2, if we project the sphere to a horizontal plane, the cones will be the same size sectors. Let y be the number of projective sectors, and the angle of each sector is equal to $\frac{2\pi }{y}$. According to the theory of solid geometry, it is easy to find that there are $\mathsf{\Theta }\left(y^2\right)$ cones in a sphere. Moreover, we also partition a sphere into $\frac{n/m}{y^2}$ concentric spheres. Since the node intensity is different in different areas, the radius of the i-th concentric sphere is defined as:

$$r_i={\left(1+\frac{2\pi }{y}\right)}^{i-1}·{\rho }_{min},$$

(5)

where ${\rho }_{min}$ denotes the minimum positive constant separation distance between the center and the other nodes in the cluster.

Intuitively, according to the partition, each sphere is divided into quasi-cubelets, and the farther the quasi-cubelets are located from the cluster center, the bigger the quasi-cubelets are. In particular, the radius of the entire sphere is:

$$r_{\frac{n/m}{y^2}+1}={\left(1+\frac{2\pi }{y}\right)}^{\frac{n/m}{y^2}}·{\rho }_{min},n\to \infty .$$

(6)

Since the average distance between two neighboring clusters is $d_c$, then take Equations (3) and (5) into consideration, we can derive the following equation:

$$r_{\frac{n/m}{y^2}+1}={\left(1+\frac{2\pi }{y}\right)}^{\frac{n/m}{y^2}}·{\rho }_{min}=e^{\frac{2\pi n^{1-v}}{y^3}}·{\rho }_{min}=\frac{d_c}{2}.$$

(7)

Based on Equation (7), we have

$$y=\mathsf{\Theta }\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right).$$

(8)

Let $s_i$ denote the quasi-cubelet between the ith and $(i+1)$th concentric sphere and $X\left(s_i\right)$ as the number of nodes distributed inside $s_i$. According to percolation theory [2], $s_i$ is open if it contains at least one node and closed otherwise. By the SNCP model, the probability that a quasi-cubelet is open can be written as:

$$\begin{array}{c}\hfill p_i\equiv P\left(X\left(s_i\right)\ge 1\right)\approx 1-e^{-r_i^{-\delta }{\left(r_i\frac{2\pi }{y}\right)}^3}\\ \hfill =1-e^{-r_i^{3-\delta }{\left(\frac{2\pi }{y}\right)}^3},\end{array}$$

(9)

where $r_i^{-\delta }$ and $r_i\frac{2\pi }{y}$ are the node density and arc length of quasi-cubelet $s_i$, respectively. While ${(r_i\frac{2\pi }{y})}^3$ can be viewed as the volume of quasi-cubelet $s_i$.

It is easy to find that $p_i$ decreases when i increases if $\delta >3$. In addition, if $i<j$, $P\left(X\left(s_i\right)\ge 1\right)>P\left(X\left(s_j\right)\ge 1\right)$.

According to the node’s distribution in each cluster, we have the following equation:

$${\left(r_i\frac{2\pi }{y}\right)}^3\times \frac{n}{m}{r}_i^{-\delta }=c_0,$$

(10)

where $c_0$ is a constant which denotes the number of nodes distributed in quasi-cubelets, and it is independent of n. By simple transformation of (10), the maximum radius ${\rho }_{max}$ of quasi-cubelets that guarantees it contains at least one node is

$${\rho }_{max}=r_z=\mathsf{\Theta }\left({((1-v)logn)}^{\frac{1}{\delta -3}}\right)$$

(11)

and the maximum number of concentric sphere is

$$i_{max}\equiv z=\mathsf{\Theta }\left(\frac{loglogn}{\delta -3}{\left(\frac{n^{1-v}}{logn}\right)}^{\frac{1}{3}}\right).$$

(12)

It indicates that there is w.h.p. at least one node in quasi-cubelet $s_i$, if $s_i$ is within the distance of $r_z$ away from the cluster center.

Until now, each cluster is divided into a $c_1{\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\times c_2{\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\times c_3\frac{loglogn}{\delta -3}{\left(\frac{n^{1-v}}{logn}\right)}^{\frac{1}{3}}$ cubelets. We consider that a path of cubelets is open if any two adjacent cubelets are open. Based on Appendix I in [2], we can obtain that there are $\lceil \eta logm\rceil$ disjoint paths crossing a rectangle of size $m\times (\kappa logm-{ϵ}_m)$. Therefore, within the radius of ${\rho }_{max}$, there exists $\mathsf{\Theta }\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{2}{3}}\right)$ disjoint paths in the direction of the radius. Similarly, the paths in the directions of south–north and east–west are both $\mathsf{\Theta }\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right)$. In our proposed model, we call the transmission path highway systems. The highway system contains two parts. One is along the direction of the radius, and we call this radial highways (RH). The other is around the sphere, which is known as surrounding highways (SH). As shown in Figure 3, the routing strategy is divided into five consecutive phases. In the first phase, the transmitter drains the packets to the closest RH; in the second phase, the information is carried along the RH until it arrives at the quasi-cubelet, which is located at the same concentric sphere as the receiver. Then, the information will be transmitted around the sphere in which we take four directions (east, west, south, north) into account. That is, the information is transmitted in the direction of south–north, and then it is delivered in the direction of east–west in the fourth phase. Finally, in the last phase, the information is left from the highway to the receiver.

3.2. Per-Node Rate of Intra-Cluster Traffic

In this section, we will derive the rate of each phase. By comparing the rate of each phase, we obtain the rate bottleneck of intra-cluster transmission. First of all, we derive a general rate when the destination is located at d cubelets away.

Theorem 1.

In each quasi-cubelet $s_i$, each node can transmit w.h.p. at a rate $R\left(d\right)=\mathsf{\Omega }\left(d^{-\alpha -3}\right)$ to any destination located at distance d, where the distance d is not Euclidean distance but the number of quasi-cubelets.

Proof. 

In each cluster, for a node located ith concentric sphere and $r_i\le {\rho }_{max}$, it transmission power is

$$P_i=P_0·{\left(\frac{2\pi r_i}{y}\right)}^{\alpha },$$

(13)

where $P_0$ is a constant denoting the power of the sphere with the minimum radius.

Using the transmission model defined in Equation (4), we can derive the data rate if the destination is located d quasi-cubelets away. According to Equation (4), the key point is to handle the interference caused by simultaneous transmission.

For the interference caused by simultaneous transmission, as shown in Figure 4, firstly, we can prove that the interferences from the opposite directions are equal. Let $I_1$ and $I_2$ denote the interferences caused by the node located in $S_{i+l}$ and $S_{i-l}$, respectively, where l is the number of quasi-cubelets from a given quasi-cubelets i. Then, we have

$$I_1\left(l\right)=P_{i+l}\frac{1}{{(r_{i+l}-r_i)}^{\alpha }},$$

(14)

$$I_2\left(l\right)=P_{i-l}\frac{1}{{(r_i-r_{i-l})}^{\alpha }},$$

(15)

and

$$\frac{I_1\left(l\right)}{I_2\left(l\right)}=\frac{P_{i+l}}{P_{i-l}}·\frac{{(r_i-r_{i-l})}^{\alpha }}{{\left(r_{i+l}-r_i\right)}^{\alpha }}{=\left(\frac{r_{i+l}}{r_{i-l}}·\frac{r_i-r_{i-l}}{r_{i+l}-r_i}\right)}^{\alpha }={\left(1+\frac{2\pi }{y}\right)}^{l\alpha }.$$

(16)

Since $y=\mathsf{\Theta }\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right)$ and $\alpha >3$, when $l=o\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right)$, we can get $\frac{I_1\left(l\right)}{I_2\left(l\right)}\to 1$. We can conclude that, using appropriate power control strategy, the interferences from other transmitters are equal if the transmitters are located the same number of quasi-cubelets away.

Next, we will analyze the interference caused by the simultaneous transmitters in a cluster. For the intra-cluster transmission, we adopt Time Division Multiple Address (TDMA) scheduling and divide time into $k^3$ successive time slots, where $k=2(d+1)$. Then, we consider the disjoint set of subcubes that are allowed to transmit simultaneously. As shown in Figure 5, if the transmitter in a subcube $s_i$ transmits toward a destination node which is located in another subcube and the distance is at most d subcubes away, we find an upper bound for the interference at the receiver. Notice that, in the jth tier, the transmitters belonging to ${(2j+1)}^3-{(2j-1)}^3$ closest subcubes are located at a distance of at least $4jd$ subcubes from $s_i$.

Summing all the interferences, the upper bound of the interference could be given as follows:

$$\begin{array}{cc}\hfill I\left(d\right)& \le {\int }_{j=1}^{\infty }\left({\left(2j+1\right)}^3-{\left(2j-1\right)}^3\right)·P_{i+4jd}·{\left(\frac{1}{\sqrt{3}\left(r_{i+4jd}-r_i\right)}\right)}^{\alpha }\hfill \\ & \le \sum _{j=1}^{\infty }\left({\left(2j+1\right)}^3-{\left(2j-1\right)}^3\right){·P}_{i+4jd}·{\left(\frac{1}{4\sqrt{3}jd{r}_i·\frac{2\pi }{y}}\right)}^{\alpha }\hfill \\ & =\sum _{j=1}^{\infty }\left({\left(2j+1\right)}^3-{\left(2j-1\right)}^3\right)·P_0·{\left(\frac{1}{4\sqrt{3}jd}·{\left(1+\frac{2\pi }{y}\right)}^{4jd}\right)}^{\alpha }\hfill \\ & =P_0{\left(4\sqrt{3}d\right)}^{-\alpha }·\sum _{j=1}^{\infty }\frac{{\left(2j+1\right)}^3-{\left(2j-1\right)}^3}{j^{\alpha }}·{\left(1+\frac{2\pi }{y}\right)}^{4jd\alpha }.\hfill \end{array}$$

(17)

Since $y=\mathsf{\Theta }\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right)$, $\alpha >3$ and $d=o\left({\left(\frac{n^{1-v}}{(1-v)logn}\right)}^{\frac{1}{3}}\right)$, the summation will be converged to some constant.

According to the tessellation of a cluster, the distance (Euclidean distance) between the transmitter and the receiver located at d quasi-cubelets away is at most $\frac{2\pi r_i}{y}d$. Thus, the received power at the receiver is bounded by:

$$S\left(d\right)\ge P_i{\left(\frac{2\pi r_i}{y}d\right)}^{-\alpha }=P_0·d^{-\alpha }.$$

(18)

Substituting Equations (17) and (18) into Equation (4), we obtain an asymptotic lower bound of the rate $R\left(d\right)$ of

$$R\left(d\right)=log\left(1+\frac{S\left(d\right)}{N_0+I\left(d\right)}\right)=\mathsf{\Omega }(d^{-\alpha }).$$

(19)

Since the time is divided into $k^3=8{(d+1)}^3$ time slots, the final rate for each subcube is

$$R\left(d\right)=\mathsf{\Omega }\left(d^{-\alpha -3}\right).$$

(20)

☐

In Equation (20), we have derived a general equation to calculate the data rate. Using Equation (20) and substituting d with different transmission distances, we can get the rate of each routing phase. In addition, Franceschetti et al. [2] had proved that the data rate bottleneck is located at the highway phase; thus, we will only compare the data rate of the highway phase.

Lemma 1.

Every node on the RH can achieve a rate of $\mathsf{\Omega }\left(1/{(n^{1-v}{(\left(1-v\right)logn)}^2)}^{\frac{1}{3}}\right)$ w.h.p.

Proof. 

According to the routing scheme, packets delivered on the highway are hop-by-hop, i.e., the packet is transmitted from one quasi-cubelet to its adjacent quasi-cubelet, which means that the distance d (number of quasi-cubelet) is one. Using Equation (20), let $d=1$, and we can get that the rate over each hop is $\mathsf{\Omega }\left(1\right)$. However, a highway may not sever one node; all the nodes on the highway need to share it. To derive the number of nodes sharing a highway, we employ Chernoff’s bound to derive it.

Chernoff Bound: Let X be a Poisson random variable of parameter λ. We have

$$Pr\left[X\ge \xi \right]\le \frac{e^{-\lambda }{\left(e\lambda \right)}^{\xi }}{{\xi }^{\xi }},\mathrm{for}\xi >\lambda ,$$

(21)

and

$$Pr\left[X\le \xi \right]\le \frac{e^{-\lambda }{\left(e\lambda \right)}^{\xi }}{{\xi }^{\xi }},\mathrm{for}\xi <\lambda .$$

(22)

For $0<\delta <1$, Chernoff bounds given in Equations (21) and (22) can be combined and simplified to

$$Pr\left[\left|X-\lambda \right|\ge \delta \lambda \right]\le 2e^{\frac{-{\delta }^2\lambda }{2}}.$$

(23)

Chernoff’s bound indicates that there are at most $\frac{2n}{m{y}^2}$ nodes in each cone w.h.p. Therefore, we can get that the data rate on the RH is

$$R_1=\mathsf{\Omega }\left(1/{(n^{1-v}{(\left(1-v\right)logn)}^2)}^{\frac{1}{3}}\right).$$

(24)

☐

Similar to Lemma 1, we derive the rate on SH. After comparing the rate on RH and SH, we obtain the rate bottleneck, which is also the throughput capacity of intra-cluster transmission.

Lemma 2.

The nodes on the SH can achieve a rate of $\mathsf{\Theta }\left({\left(\frac{(1-v)logn}{n^{1-v}}\right)}^{\frac{2}{3}}·f\left(\delta \right)\right)$ w.h.p., where $f(\delta )$ is called “heterogenous factor”, which is only decided by the heterogeneous topology of the node’s distribution.

Proof. 

Compared with the case of RH, the transmission around the cluster becomes more complicated since the number of nodes in each sphere-tier are not equal. If the number of nodes in every sphere-tier are identical, we can get a corresponding rate of $\mathsf{\Theta }\left({\left(\frac{\left(1-v\right)logn}{n^{1-v}}\right)}^{\frac{2}{3}}\right)$. Furthermore, taking the effect of heterogeneity into account, the achievable rate can be written as:

$$R_2=\mathsf{\Theta }\left({\left(\frac{\left(1-v\right)logn}{n^{1-v}}\right)}^{\frac{2}{3}}·f\left(\delta \right)\right).$$

(25)

☐

In the following Lemma, we analyze the impact of $f\left(\delta \right)$ and compare the rate on RH and SH.

Lemma 3.

For the intra-cluster traffic of each independent cluster, the nodes within radius ${\rho }_{max}$ can achieve a rate of $\mathsf{\Omega }\left(1/{\left(n^{1-v}{(\left(1-v\right)logn)}^2\right)}^{\frac{1}{3}}\right)$ w.h.p.

Proof. 

The routing strategy based on percolation theory has been deeply researched. Here, we give a rigorous derivation of the achievable rate during the highway phase in the intra-cluster transmission. To get the rate bottleneck, we need to compare the rates on the RH and SH. The rate on RH has been derived in Lemma 1. We will calculate the rate of SH. As the number of nodes on different paths is not in the same level, the condition along the cluster is more sophisticated with respect to the radial direction. According to the analysis above, we use $E\left(N_i\right)$ to denote the mathematical expectation number of nodes in each concentric sphere. Then, we can achieve the expectation from our model and simplify it as follows:

$$E\left(N_i\right)=\frac{n}{m}{\left(r_i\frac{2\pi }{y}\right)}^3\frac{1}{r_i^{\delta }}y,$$

(26)

where $\frac{n}{m}$ is the number of nodes in a cluster, $\frac{1}{r_i^{\delta }}$ is the node density of concentric sphere i and ${\left(r_i\frac{2\pi }{y}\right)}^{3}y$ is the volume of concentric sphere i.

Using (5) to substitute $r_i$, we can get:

$$\begin{array}{cc}\hfill E\left(N_i\right)& =\frac{n}{m}{\left(r_i\frac{2\pi }{y}\right)}^3\frac{1}{r_i^{\delta }}y\hfill \\ & =8{\pi }^3\frac{n}{m}{y}^{-2}{r}_i^{3-\delta }\hfill \\ & =8{\pi }^3\frac{n}{m}{y}^{-2}{\left(1+\frac{2\pi }{y}\right)}^{i(3-\delta )}\hfill \\ & =8{\pi }^3\frac{n}{m}{\left(\frac{(1-v)logn}{n^{1-v}}\right)}^{\frac{2}{3}}{\left(1+\frac{2\pi }{{\left(\frac{(1-v)logn}{n^{1-v}}\right)}^{\frac{2}{3}}}\right)}^{i(3-\delta )}.\hfill \end{array}$$

(27)

As for $\delta >3$, we can find that $E\left(N_i\right)$ decreases with the increasing of parameter i. Thus, the SH closest to the cluster center needs to service the most nodes. Then, we can get the achievable rate on the SH:

$$R_2>R_2(i=1)=\mathsf{\Theta }\left({\left(\frac{(1-v)logn}{n^{1-v}}\right)}^{\frac{2}{3}}{\left(1+\frac{2\pi }{{\left(\frac{(1-v)logn}{n^{1-v}}\right)}^{\frac{2}{3}}}\right)}^{3-\delta }\right).$$

(28)

In the end, comparing the $R_1$ and $R_2$, we can find that, for any i, $R_1<R_2$, i.e., the data rate on any SH larger than that of RH. Correspondingly, the rate bottleneck is on the RH. Thus, the data rate of intra-cluster is

$${R_{intra}=R}_1=\mathsf{\Omega }\left(1/{(n^{1-v}{(\left(1-v\right)logn)}^2)}^{\frac{1}{3}}\right).$$

(29)

☐

4. Transmission of Inter-Cluster

In this section, we will conduct a study on inter-cluster transmission. For the inter-cluster transmission, it is hard to guarantee that each quasi-cube contains at least one node if we still adopt the transmission strategy of the intra-cluster. Thus, a new policy is proposed in this section for the inter-cluster traffic. Since the lowest node density is $\underline{\mathsf{\Phi }}$, according to percolation theory [2,13], we can guarantee that each quasi-cube contains nodes with high probability if we partition the inter-cluster area into cubes with side lengths of $c\sqrt[3]{1/\underline{\mathsf{\Phi }}}$, where c is a constant. Similarly, we have the following Theorem.

Theorem 2.

For the inter-cluster traffic, we can obtain an achievable rate of $R_{inter}=\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)$.

Proof. 

Since the node density in the space among the clusters is much lower, we propose an idea of “information pipes”, as shown in Figure 6. In our network, we assume that $\overline{\mathsf{\Phi }}$ is the maximum node density and $\underline{\mathsf{\Phi }}$ is the minimum node density. The inter-cluster space is divided into cubelets with side lengths of $c\sqrt[3]{1/\underline{\mathsf{\Phi }}}$, where c is a constant.

Therefore, the network consists of many cuboids of side length $c\sqrt[3]{1/\underline{\mathsf{\Phi }}}\times c\sqrt[3]{1/\underline{\mathsf{\Phi }}}\times \sqrt[3]{A}$, or $c\sqrt[3]{1/\underline{\mathsf{\Phi }}}\times \sqrt[3]{A}\times c\sqrt[3]{1/\underline{\mathsf{\Phi }}}$, or $\sqrt[3]{A}\times c\sqrt[3]{1/\underline{\mathsf{\Phi }}}\times c\sqrt[3]{1/\underline{\mathsf{\Phi }}}$. Then, the nodes outside the cluster region can build up $\mathsf{\Omega }\left({\left(\sqrt[3]{A\underline{\mathsf{\Phi }}}\right)}^2\right)$ “information pipes” among these clusters , and these “information pipes” need to serve $\mathsf{\Theta }\left(m\right)$ clusters. Correspondingly, each cluster can enjoy $\mathsf{\Omega }\left(\frac{{\left(\sqrt[3]{A\underline{\mathsf{\Phi }}}\right)}^2}{m}\right)$ “information pipes” on average. Similar to the proof of Theorem 1, let $d=1$, and we get that the rate on the “information pipes” is also constant, while the difference is that we employ the same power to transmit in the “information pipes”. The reason is that the size of cubelets in the “information pipes” is equal. Intuitively, the power of inter-cluster transmission would be larger than that of intra-cluster transmission. The reason is that the node density among the clusters is much lower, and we need to enlarge the size of cubelets, such that we can guarantee that each cubelet contains at least one node w.h.p.

Based on the analysis above, there are $\mathsf{\Omega }\left({\left(\sqrt[3]{A\underline{\mathsf{\Phi }}}\right)}^2\right)$ “information pipes” in the network, and these “information pipes” need to sever at most n nodes. Thus, we can get the achievable rate for each node in the inter-cluster transmission is:

$$R_{inter}=\mathsf{\Omega }\left(\frac{{\left(\sqrt[3]{A\underline{\mathsf{\Phi }}}\right)}^2}{n}\right)=\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right).$$

(30)

☐

In particular, if the network model transforms to a homogeneous network, i.e., $\underline{\mathsf{\Phi }}=\mathsf{\Theta }\left(\overline{\mathsf{\Phi }}\right)=\mathsf{\Theta }\left(n^{1-\gamma }\right)$, we can get that the achievable rate is

$$R_h=\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)=\mathsf{\Omega }\left(\frac{1}{\sqrt[3]{n}}\right),$$

(31)

where $R_h$ is also the result of homogeneous three-dimensional wireless networks [17,18,19].

5. A Lower Bound on Capacity

For the three-dimensional heterogeneous wireless ad hoc networks where the nodes are distributed according to the SNCP, we can get that the achievable throughput capacity is :

$$R\left(n\right)=\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right).$$

(32)

Comparing the transmission of intra-cluster and inter-cluster, we can find the bottleneck of the throughput capacity is in the space with minimum node density. Thus, for the entire network, the achievable throughput capacity is $\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)$.

Furthermore, compared with the results in [19], we have obtained a tighter lower bound of throughput capacity in the 3D heterogeneous wireless networks. In particular, when the nodes are distributed uniformly, i.e., $\underline{\mathsf{\Phi }}=\mathsf{\Theta }\left(\overline{\mathsf{\Phi }}\right)=\mathsf{\Theta }\left(n^{1-\gamma }\right)$, then the per-node throughput can achieve $\mathsf{\Omega }(\frac{1}{\sqrt[3]{n}})$, which is the throughput capacity of three-dimensional homogeneous wireless networks.

6. Conclusions

In this paper, we exploit the percolation theory to achieve the throughput capacity of three-dimensional heterogeneous networks in which the nodes are distributed according to the SNCP. We focus on the cluster-sparse network. In order to get the lower bound of the throughput capacity, the transmission is divided into two parts: the intra-cluster transmission and the inter-cluster transmission. For the first part, we novelly establish a spheroidal percolation model in which the information is transmitted through five phases. The bottleneck of throughput capacity is due to the information carried through the RH. After the derivation, we get the achievable per-node rate of $\mathsf{\Omega }\left(1/{(n^{1-v}{((1-v)logn)}^2)}^{\frac{1}{3}}\right)$ for the intra-cluster transmission. For the inter-cluster transmission, we employ the idea of “information pipes” to complete the transmission and then obtain a per-node rate of $\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)$. Finally, taking the whole network traffic into account, the achievable per-node throughput capacity for three-dimensional heterogeneous wireless networks is $\mathsf{\Omega }\left(n^{\frac{2\gamma }{3}-1}{\underline{\mathsf{\Phi }}}^{\frac{2}{3}}\right)$.