Hybrid performance modelling of opportunistic networks

Luca Bortolussi, Vashti Galpin, Jane Hillston

TL;DR

This paper demonstrates how to use stochastic HYPE, a process algebra, to model opportunistic networks as hybrid systems. By treating high-volume data traffic as a continuous "fluid" rather than individual discrete packets, the authors enable efficient performance analysis of complex network behaviors, such as mobile data ferries collecting sensor data.

What Problem Does This Paper Address?

Opportunistic networks (OppNets) are characterized by intermittent connectivity, where nodes (like sensors or mobile devices) are often disconnected and must wait for a "store-carry-forward" opportunity to pass data.

Traditional performance modeling for these networks usually happens at the packet level. However, as data volumes grow (e.g., high-definition video sensors), tracking every individual packet becomes computationally prohibitive and slow. The challenge is to create a model that is high-level enough to be efficient but detailed enough to capture the "hybrid" nature of the system: continuous data flows interrupted by discrete, often random, connection events.

Methods

The authors utilize stochastic HYPE, an extension of the HYPE process algebra designed specifically for hybrid systems.

Key components of their approach include:

  • Fluid Abstraction: Instead of counting packets, data is modeled as a continuous quantity. The rate of change is governed by Ordinary Differential Equations (ODEs).
  • Compositional Modeling: HYPE allows the modeler to define "flows" (influences) locally. For example, a sensor's "input" and "output" are defined separately, and the global behavior of the buffer emerges automatically when these components are composed.
  • Stochastic & Deterministic Events: The model handles "urgent" events (like a buffer hitting its maximum capacity) and "stochastic" events (like a mobile ferry randomly coming into range of a sensor based on a probability distribution).
  • Simulation Software: The authors developed a Java-based tool that "flattens" the HYPE model into a set of discrete variables and ODEs, which are then numerically integrated using the MathCommons library.

Datasets

The paper does not use a real-world dataset; instead, it evaluates the approach using a synthetic case study designed to reflect a wildlife monitoring scenario (similar to projects like ZebraNet).

  • Setup: 10 stationary video sensors, each with 250MB of storage.
  • Scenario: Sensors record video 3 times a day; a mobile "ferry" collects this data over an 8-hour period and delivers it to a base station.
  • Variables: The study tests different ferry buffer sizes (600MB to 1400MB) and different mobility models (fixed vs. random routes).

Key Insights and Ideas

  • The Power of "Flows": One of the most significant "aha moments" is that HYPE removes the need for the modeler to manually write complex global ODEs. By defining individual influences (e.g., "uploading to ferry"), the system's differential equations are derived automatically from the semantics of the language.
  • Fairness in Routing: The results highlight that fixed routes (cyclical paths) are significantly more "fair" than random routes. In random mobility models, some sensors might be visited frequently while others are starved, leading to massive data loss even if the average visit frequency is the same.
  • Efficiency of Hybrid Simulation: Because the model doesn't track individual packets, simulations are remarkably fast. A complex 8-hour scenario with 10 sensors and a mobile ferry took only 6.5 seconds to simulate on a standard laptop.

Key Results

  • Route Comparison: Fixed routes (raef and rtbf) consistently resulted in less data dropped and more data collected compared to random routes (raer and rtbr).
  • Contact Frequency: As the Mean Time to Contact (MTC) increased (meaning the ferry visits less often), the amount of dropped data increased linearly across all models.
  • Buffer Impact: For lower ferry buffer capacities, the "return to base when full" policy (rtbf/rtbr) was shown to be essential to prevent the ferry from wandering aimlessly while unable to collect new data.
  • Data Volume: The fluid approach successfully modeled high-generation rates (megabytes per second) that would likely overwhelm traditional discrete-event simulators.

Limitations and Future Work

  • Abstract Mobility: Currently, the movement of the ferry is modeled abstractly using meeting rates (exponential distributions). The authors acknowledge the need to move toward 2D spatial models where HYPE can explicitly model continuous movement in a coordinate system.
  • Software Modularization: The current tool requires manual coding of models; the authors plan to develop a front-end for "parametric templates" to allow users to easily plug in different types of nodes and connections.
  • Computational Optimization: While already fast, the authors suggest that using dependency graphs to manage discrete variables and implementing multithreading could further scale the system for massive networks.

Summary updated

BibTeX
@inproceedings{bortolussi2012hybrid,
  author = {Luca Bortolussi and Vashti Galpin and Jane Hillston},
  title = {{Hybrid performance modelling of opportunistic networks}},
  booktitle = {QAPL},
  year = {2012},
  url = {https://openreview.net/forum?id=JuCOgTNpzWH},
}

Loading related content...

Figure