## 3 Network Connectivity Analysis
### Link Probability Analysis
With the following definitions, we can further outline the transitional region. **Definition 3:** If the link between two nodes has a high probability (\(>\)\(p_{h}\)) of having high PRR (\(>\)\(\xi_{h}\)), then the two nodes are strongly connected. The upper bound of the connected range is \(s_{l}\). **Definition 4:** If the link between two nodes has a high probability (\(>\)\(p_{h}\)) of having low PRR (\(<\)\(\xi_{l}\)), then the two nodes are almost disconnected. The lower bound of the disconnected range is \(s_{h}\). According to definition 3 and definition 4, the region between \(s_{l}\) and \(s_{h}\) is the transitional region, as illustrated in Figure 2. This agrees with empirical observations in [2, 28]. The existence of this region has been explained in [13], which is the joint effect of non-perfect-threshold receiver, noisy environment and multi-path effects. With consideration of different pass loss and shadow fading along different direction, we draw contour plot of the reception rate for a node located at the center of the region. Figure 3 shows the difference of the communication area of a Boolean disk model and a shadowing fading model. Figure 3(b) captures the real characteristic of wireless link and shows spatial irregularity as the empirical results in [14]. To calculate \(P(\bar{I})\), the value of \(\xi\) is crucial. As depicted in Figure 2, it is difficult to derive a continuous function for \(P(L|s)\). Instead, we calculate the expected value of \(P\), denoted as \(E(P)\). Thus, \(\xi\) can be written as:  
\[\xi=\int_{0}^{\infty}P(L\,|\,s)sds\approx\int_{0}^{\infty}\int_{-\infty}^{ \infty}\Psi(\gamma)f(\gamma\,|\,s)\cdot sd\gamma ds \tag{20}\]  
where \(f(\gamma|s)\) represents the probability density function of SNR. According to (17), we draw the PRR as a function of \(\gamma\). As the power-law relationship entails a sharp threshold, linear approximation turns available. \(\Psi(\gamma)\) can be approximated as the following piecewise linear functions:  
Figure 3: Contour plot for different link models. (a) Boolean disk model. **(b)** Log-normal shadowing based probabilistic model. Figure 2: Analytical PRR to distance, obtained from (19) and (17), \(P_{i}\)=-5 dB, \(\eta\)=3, \(\sigma\)=3.3, \(f\)=50 Byte, \(h\)=2 Byte. an N\(\times\)N matrix \(L(G)\)=\(D(G)\)-\(A(G)\), where \(D(G)\) is the diagonal matrix of vertex degrees, \(D(G)\)=diag(\(d(v_{i})\)), \(v_{i}\)\(\in\)\(V\); \(A(G)\) is the adjacent matrix of \(G\). The eigenvalues of \(L(G)\) are called the Laplacian eigenvalues, which are all real and nonnegative. The set of all \(N\) Laplacian eigenvalues \(\lambda_{i}\)\(\geq\)\(\lambda_{2}\)\(\geq\)\(\ldots\)\(\geq\)\(\lambda_{\text{N-I}}\)\(\geq\)0=\(\lambda_{\text{N}}\) is called the Laplacian spectrum of a graph \(G\). **Theorem 1:** If the graph \(G\) has \(C\) connected components, then \(L(G)\) has exactly \(C\) zero eigenvalues (other eigenvalues are positive). Based on Theorem 1, the graph is one-connected if \(L(G)\) possesses only one zero eigenvalue. The probability for one-connectivity is estimated from a representative sample of _ad hoc_ sensor networks' connectivity graph as the ratio between one-connected graph and all sample graphs. Figure 5 shows the simulated results. Each subplot corresponds to a different configuration. Figure 5(a) serves as a benchmark for comparison. The critical node densities in different scenarios are reported in \[\varphi(\gamma)=(1-\beta_{M}(\gamma))^{8(2/-h)} \tag{15}\]0 Through comparing and analyzing the 7 groups of simulated data, we draw the following conclusions and give the explanations. * In all simulation cases, as the node density increases, the network graph becomes denser and the transition from low connectivity to nearly full connected or appearance of giant component is quite sharp over a small range of \(\rho\). The phenomenon consists with the results in [22] which uses the theory of continuum percolation.