# Throughput Capacity of Selfish Wireless _Ad Hoc_ Networks with General Node Density
## 3 Achievable Rate
### Construction of the Backbone Network  
According to percolation theory, a square is said to be open if it contains at least one AN, and closed otherwise. To construct the backbone of the network, we divide the network area into squares of dimensions \(l(n)\times l(n)\), where \(l(n)=c_{0}\sqrt{\frac{1}{5p(n)}}\). By appropriately choosing the constant \(c_{0}\), we can adjust the probability that a square contains at least one AN:  
\[P(\text{a square contains at least one AN})=1-e^{-c_{0}^{2}}\equiv p_{o} \tag{2}\] \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline \(n\) & Total number of nodes in the network. \\ \(\zeta\) & Node density. \\ \(A\) & Network area; \(A=n/\zeta\). \\ \(p(n)\) & Probability that a node will forward other transmission. \\ \(S\) & Set of simultaneous nodes. \\ \(R_{i,j}\) & Point to point rate. \\ \(P\) & Power of transmission. \\ \(d_{ij}\) & The distance between node \(i\) and \(j\). \\ \(N_{0}\) & Power of noise. \\ \(\alpha\) & Path loss exponent. \\ \(T(n)\) & The achievable throughput. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. Note that squares are open (closed) with probability \(p_{o}\), related to \(p(n)\) and \(\zeta\) and independently of each other. As Figure 2 shows, in each square we draw a horizontal edge (thick lines) across it, and in the vertical direction as well. An edge is said to be open if there exists at least one AN in the square and closed otherwise. On the basis of construction, we establish a bond percolation model [23]. Consequently, the probability that an edge is open is \(p_{o}\). Since the number of nodes located in a given square follows Poisson random process with parameter \(\frac{1}{\xi p(n)}\), we can get Lemma 1:  
**Lemma 1**. : _Let \(N_{i}\) denote the number of node contained in a given square \(s_{i}\). Let \(E_{i}\) be the event \(\frac{1}{8p(n)}\leq N_{i}\leq\frac{2}{p(n)},\forall i\). Then,_  
\[p_{a}(n)\equiv P(E_{i})>1-16\left(2/e\right)^{1/4p(n)} \tag{3}\]  
Proof. : The lemma can be proven simply by applying the Chernoff bound and the Union bound. According to the backbone construction, we use \(m(n)\) to denote the number of horizontal (vertical) edges which compose the side length of the area \(\mathbb{A}\). Then,  
\[m(n)=\frac{\sqrt{A}}{\sqrt{2}l(n)}=\sqrt{c_{1}np(n)} \tag{4}\]  
Notice that \(m(n)\rightarrow\infty\) as \(n\rightarrow\infty\), and \(c_{1}\) is a constant. Next we divide the area \(\mathbb{A}\) into horizontal rectangular slabs with dimensions \(\sqrt{A}\times\sqrt{2}l(n)\left(\kappa\log m(n)+\epsilon_{n}\right)\), where \(\kappa>0\), as shown in Figure 3. Let \(R_{n}^{i}\) denote the \(i\)-th slab, where \(i\leq\frac{m(n)}{\kappa\log m(n)+\epsilon_{n}}\). The parameter \(\epsilon_{n}\) is the smallest nonnegative number, as the number of rectangular slabs \(\frac{m(n)}{\kappa\log m(n)+\epsilon_{n}}\) is an integer. As proven in Theorem 1 of [5], many open paths from left to right exist inside each slab. Let \(C_{N}^{i}\) be the maximal number of disjoint left-to-right crossing paths in rectangle \(R_{n}^{i}\) and \(N_{n}=\min_{i}C_{n}^{i}\). The following lemma shows that there exists a large number of crossing paths in each horizontal rectangular slab of \(\mathbb{A}\). **Lemma 2**. : _For all \(\kappa>0\), there exists a \(\delta\) satisfying \(0<\delta<\kappa\) such that_  
\[\lim_{n\rightarrow\infty}P\left(N_{n}\leq\delta\log m(n)\right)=0 \tag{5}\]  
Proof. : According to Theorem 5 in [5], we note that when \(p>\frac{5}{6}\) for large \(n\). Taking the limits as \(n\rightarrow\infty\), the inequality (16) in [5] derives the condition \(0<\delta<\kappa\). Figure 2: A new square system. We partition the network with side length \(l(n)\), and the thick line represents that there is at least one altruistic node in the square.