An Experimental Study of SmallWorld Network Models for Wireless Networks

Ziqian Dong, Zheng Wang, Wen Xie, Obinna Emelumadu, Chuan- Bi Lin, Roberto Rojas‐CessaJournal of Cyber Security and Mobility 2016 · DOI

TL;DR

This paper explores how "small-world" network properties, common in social networks, can be applied to wireless ad-hoc networks (MANETs). By simulating two popular small-world models (Watts-Strogatz and Newman-Watts) and testing them with common routing protocols, the authors demonstrate that these models can effectively represent wireless network structures and potentially improve routing efficiency.

What Problem Does This Paper Address?

The Internet of Things (IoT) is leading to an explosion of connected devices, creating complex wireless networks. Understanding and managing these networks is challenging due to their scale and dynamic nature. Small-world network theory, which describes networks with high clustering and short average path lengths (like "six degrees of separation"), offers a promising framework for modeling and analyzing such complex systems. However, bridging the gap between theoretical small-world models and their practical implementation in real-world wireless networks, particularly mobile ad-hoc networks (MANETs), requires experimental validation. This paper aims to investigate how two prominent small-world network models behave when applied to MANETs and how they interact with distributed routing protocols.

Methods

The researchers employed a two-pronged approach:

  1. Matlab Simulation: They first simulated the Watts-Strogatz (WS) and Newman-Watts (NW) small-world network models in Matlab. This allowed them to analyze the fundamental properties of these models, specifically focusing on the average path length and clustering coefficient as a function of the rewiring probability parameter 'p'. They also examined the degree distribution of nodes in these simulated networks.
  2. OPNET Simulation: To bridge the gap to practical implementation, they used OPNET (now Riverbed Modeler) to simulate a small-scale MANET. This simulation environment allowed them to:
  3. Implement a network with mobile nodes that act as both devices and routers, mimicking a decentralized ad-hoc network.
  4. Test two common distributed routing protocols: Ad hoc On-demand Vector Routing (AODV) and Optimized Link State Routing (OLSR).
  5. Introduce "jammers" to simulate real-world interference and noise, adding a layer of realism to the experiments.
  6. Evaluate network performance using metrics like transmission time, number of hops, and ping response times.

Datasets

Not discussed in the paper. The study relies on simulated network environments rather than real-world datasets.

Key Insights and Ideas

  • Newman-Watts Model's Suitability: The Newman-Watts (NW) model appears to be a better fit for modeling the small-world phenomenon in wireless networks compared to the Watts-Strogatz (WS) model, particularly in terms of its ability to maintain high clustering while achieving short path lengths.
  • Routing Protocol Performance: Both AODV and OLSR were tested, with OLSR generally showing faster response times, while AODV exhibited better reliability with less packet loss. This highlights a trade-off between speed and robustness in routing protocols for MANETs.
  • Bounded Hops in MANETs: The experiments confirmed that even in a small-scale MANET, the number of hops required to reach a destination is capped, supporting the small-world concept of efficient connectivity. For OLSR, this cap was observed to be around four hops.
  • Challenges of Practical Implementation: The paper acknowledges significant challenges in translating theoretical small-world models to real-world wireless networks. These include dealing with the dynamic nature of wireless links, network node geolocation, interoperability between different network types, and the complexity of multi-scale network implementations.

Key Results

  • Matlab Simulations: Both WS and NW models showed a rapid decrease in average shortest path length as the rewiring probability 'p' increased. The NW model, however, maintained higher clustering coefficients for a wider range of 'p' values, suggesting better small-world characteristics. Degree distributions in both models, for intermediate 'p' values, resembled those of Erdős-Rényi random graphs and Poisson distributions.
  • OPNET Simulations:
    • OLSR demonstrated lower average response times (under 100 ms) compared to AODV.
  • AODV showed lower packet loss, indicating greater reliability.
  • The number of hops for OLSR was consistently bounded, typically around four hops, validating the small-world hypothesis in a practical simulation.

Limitations and Future Work

Limitations:

  • Scale of Simulation: The OPNET simulation was conducted on a small network (up to 80 nodes, with a subset being mobile). The authors note that this limitation might raise concerns for validating small-world networks, which are typically characterized by a large number of nodes. However, they argue that for mobile routing, node range constraints make smaller-scale simulations relevant.
  • Interference Modeling: While jammers were used to simulate interference, the complexity of real-world signal interference in heterogeneous wireless environments is a significant challenge not fully captured.

Future Work:

  • Multi-Scale Networks: The authors suggest that multi-dimensional routing might be necessary for implementing small-world concepts in multi-scale networks that integrate various wireless access technologies.
  • Heterogeneous Networks: Further research is needed to address the challenges of implementing small-world models in practical, heterogeneous wireless networks, considering factors like delay, geolocation, and interoperability.
  • Distributed Routing Benefits: The paper highlights the potential for distributed routing in large-scale networks to benefit from small-world principles, especially in the context of the future Internet of Things.

Summary updated

Abstract

The concept of small world phenomenon has been observed and applied in many types of networks. This paper presents a study of two small-world network models in clustering formation and routing in wireless network, the Watts and Stragtz’s (WS) and the Newman and Watts (NW) models and evaluates their properties in term of average node degree and path length. We tested the small world phenomenon in wireless networks by simulating a wireless mobile ad hoc network with distributed routing protocols. We present the research challenges of bridging the gap between theoretical models and practical wireless network implementation. This study provides insights on how wireless networks behave under small world network models with distributed routing protocols.
BibTeX
@article{dong2016experimental,
  author = {Ziqian Dong and Zheng Wang and Wen Xie and Obinna Emelumadu and Chuan- Bi Lin and Roberto Rojas‐Cessa},
  title = {{An Experimental Study of SmallWorld Network Models for Wireless Networks}},
  journal = {Journal of Cyber Security and Mobility},
  year = {2016},
  doi = {10.13052/2245-1439.442},
}
Figure