移动Ad Hoc 社交网络中的安全连通性分析

Dianjie Lu, Hu Bin, Xiangwei Zheng, Hong Liu, Guijuan ZhangScientia 2015 · DOI

Abstract

The security of mobile ad hoc social networks (MASNs) has received considerable attention in the past several years. In MASNs, achieving secure communication is challenging, because all the links must operate with mutual trust. In this paper, we explore the analytical characterization of secure connectivity in MASNs. First, we formulate the distribution of trust relationships between nodes as a renewal process, enabling us to construct a secure graph with four phases, namely geographic graph construction, trust graph construction, secure graph establishment, and secure graph augmentation. Then, we prove the existence of percolation phenomenon in secure MASNs using continuum percolation theory. Finally, we investigate the characterization of the critical density, which is the central problem of secure connectivity. By employing the clustering coefficient method, we derive a tighter lower bound on the critical density. Simulation results show that both the density and trust relationships of nodes can greatly impact the secure connectivity of MASNs. Our results enable a fundamental understanding of secure connectivity in MASNs.

Introduction

Mobile Ad Hoc Social Networks (MASNs) have emerged as a vital communication paradigm for scenarios lacking fixed infrastructure, such as disaster relief operations or spontaneous social gatherings. Unlike traditional Mobile Ad Hoc Networks (MANETs), where connectivity is determined solely by the physical proximity of nodes, MASNs introduce a critical social dimension: trust. In these networks, a link is only considered "secure" if the participating nodes are both within transmission range and share a mutual trust relationship. This dual constraint—physical and social—makes achieving global connectivity significantly more complex. This paper provides a rigorous analytical framework to characterize secure connectivity in MASNs, identifying the critical thresholds required for a functional network to emerge.

Modeling the Secure Graph

To analyze the macro-level behavior of MASNs, the authors propose a multi-layered graph construction process. This approach decomposes the complex network into manageable components:

  1. Geographic Graph ($G_g$): This layer represents the physical topology. A link exists between two nodes if their Euclidean distance is less than or equal to their transmission radius $r$.
  2. Trust Graph ($G_t$): This layer represents the social layer. Trust is modeled as a dynamic renewal process, where relationships toggle between authorized and unauthorized states over time.
  3. Secure Graph ($G_s$): This is the fundamental secure network, formed by the intersection of $G_g$ and $G_t$. A secure link exists only if nodes are physically close and trust each other.
  4. Augmented Secure Graph ($G_s^a$): Recognizing that direct trust is a strict requirement, the authors introduce "social bridges." If two nodes are physically close but do not trust each other, they can still communicate securely if they share a common trusted neighbor who acts as a relay.
Figure 4: The construction of a MASN involves decomposing connectivity into (a) the Geographic Graph based on physical range and (b) the Trust Graph based on social relationships.

Percolation Theory and the Critical Density

A central question in MASN research is: at what point does a collection of scattered nodes form a globally connected network? The authors apply continuum percolation theory to prove that MASNs exhibit a phase transition. As node density increases, the network suddenly transitions from a state of isolated clusters to one containing a "giant component" that spans the entire area.

The point at which this transition occurs is the critical density ($\lambda_c^s$). Identifying this threshold is crucial for network planning. To provide a more accurate estimate than previous models, the authors employ the clustering coefficient (CC) method. By accounting for the spatial correlation between neighboring nodes—the fact that if Node A is near Node B and Node B is near Node C, Node A is likely near Node C—they derive a tighter lower bound for the critical density. This mathematical refinement allows for more realistic predictions of network behavior in physical space.

The Impact of Social Augmentation

One of the paper's most significant insights is the role of the Augmented Secure Graph. By allowing "social bridges" to facilitate communication, the network can overcome the sparsity of direct trust relationships.

Figure 5: The Augmented Secure Graph illustrates how intermediate trusted nodes (social bridges) can connect nodes that lack direct trust, significantly improving global connectivity.

This augmentation effectively lowers the physical density required to reach the percolation threshold. In practical terms, it means that a secure network can be maintained with fewer users or over larger areas, provided there is a sufficient "web of trust" that allows for multi-hop secure relaying.

Simulation Results and Analysis

The theoretical framework was validated through extensive simulations in Matlab. The results confirm the existence of a sharp percolation threshold. For instance, at a node density of $\lambda = 1.2$, the largest secure component included only about 35.8% of the nodes. However, increasing the density to $\lambda = 1.8$ caused the giant component to encompass 88.9% of the nodes, signaling the onset of global connectivity.

The simulations also highlighted the sensitivity of the network to trust levels. The probability of trust acts as a scaling factor for physical density; if trust is rare, a much higher concentration of physical devices is required to ensure the network does not fragment.

Conclusion

This paper establishes a comprehensive mathematical foundation for understanding secure connectivity in Mobile Ad Hoc Social Networks. By integrating social trust models with physical topology and applying advanced percolation theory, the authors provide the tools necessary to calculate the critical density required for secure, large-scale communication. These results are instrumental for the design of resilient decentralized networks in both civilian and emergency contexts.

Summary updated

Abstract

The security of mobile ad hoc social networks (MASNs) has received considerable attention in the past several years. In MASNs, achieving secure communication is challenging, because all the links must operate with mutual trust. In this paper, we explore the analytical characterization of secure connectivity in MASNs. First, we formulate the distribution of trust relationships between nodes as a renewal process, enabling us to construct a secure graph with four phases, namely geographic graph construction, trust graph construction, secure graph establishment, and secure graph augmentation. Then, we prove the existence of percolation phenomenon in secure MASNs using continuum percolation theory. Finally, we investigate the characterization of the critical density, which is the central problem of secure connectivity. By employing the clustering coefficient method, we derive a tighter lower bound on the critical density. Simulation results show that both the density and trust relationships of nodes can greatly impact the secure connectivity of MASNs. Our results enable a fundamental understanding of secure connectivity in MASNs.
BibTeX
@inproceedings{lu2015ad,
  author = {Dianjie Lu and Hu Bin and Xiangwei Zheng and Hong Liu and Guijuan Zhang},
  title = {{移动Ad Hoc 社交网络中的安全连通性分析}},
  booktitle = {Scientia},
  year = {2015},
  doi = {10.1360/n112014-00255},
}
Figure