Source-linked AI summary
SWIM: A Simple Model to Generate Small Mobile Worlds
Alessandro Mei, Julinda Stefa
TL;DR
Mobile ad-hoc networking lacks a mobility model that is simultaneously simple, statistically realistic, and accurate for protocol evaluation. SWIM combines home proximity with destination popularity to generate synthetic traces, and its traces match real mobility statistics while accurately predicting forwarding-protocol performance.
Problem
Existing mobility models do not jointly provide simplicity, realistic trace statistics, and accurate prediction of real-world networking-protocol performance.
Method
SWIM assigns nodes homes and selects destinations using simple weights that combine distance from home with observed destination popularity.
Results
SWIM’s synthetic traces match real traces across inter-contact time, contact duration, and contact-count distributions, while accurately approximating two forwarding protocols’ performance.
Takeaways & Limitations
SWIM supports mobility analysis, theoretical work, and networking-protocol evaluation, including scenarios too large to have real traces.
Abstract
from arXiv · showhide
This paper presents small world in motion (SWIM), a new mobility model for ad-hoc networking. SWIM is relatively simple, is easily tuned by setting just a few parameters, and generates traces that look real--synthetic traces have the same statistical properties of real traces. SWIM shows experimentally and theoretically the presence of the power law and exponential decay dichotomy of inter-contact time, and, most importantly, our experiments show that it can predict very accurately the performance of forwarding protocols.
I. INTRODUCTION
Mobile ad-hoc networking needs mobility models that generate realistic synthetic traces for protocol evaluation. SWIM is introduced as a simple model whose traces match real mobility statistics and accurately approximate forwarding-protocol performance.
- Motivation: Synthetic mobility data supports practical analysis and validation of mobile ad-hoc networking protocols.Mobility models simulate real-life scenarios used to tune protocols and evaluate their performance.
- Observed mobility properties: Inter-contact time characterizes packet-forwarding opportunities, while contact duration limits how much data meetings can transfer.Real experiments observed characteristic distributions for both metrics.
- Limitations of existing models: RWP produces exponential inter-contact times, unlike real traces showing a power-law interval followed by an exponential cutoff.This mismatch contributes to the need for more realistic mobility models.
- SWIM contribution: SWIM uses simple human-mobility intuition and produces synthetic inter-contact, contact-duration, and contact-count distributions matching real traces.The model favors places near home where many people can meet.
- Protocol evaluation: Synthetic SWIM traces accurately approximate the performance of epidemic and delegation forwarding on real traces.The comparison uses the same model-generated output rather than protocol-specific tuning.
III. SMALL WORLD IN MOTION
Existing mobility models do not jointly provide simplicity, realistic statistical properties, and accurate protocol-performance prediction. SWIM addresses this gap with a few simple rules based on how people choose nearby, popular destinations.
- Design goals: A suitable mobility model should be simple, statistically realistic, and predictive of networking-protocol performance.Simplicity also supports understanding, implementation, tuning, and theoretical work.
- Research gap: No reviewed model meets all these requirements: RWP is simple but unrealistic, while other models sacrifice simplicity or lack accurate protocol prediction.The paper states that accurate real-world protocol-performance prediction had not been demonstrated.
- SWIM proposal: SWIM proposes a very simple model whose rules allow typical real-trace properties to emerge naturally.The authors also claim it can predict networking-protocol performance on real mobile networks extremely well.
- Human-mobility intuition: SWIM models human mobility through a trade-off between destination popularity and distance from home.People tend to choose nearby, popular places and spend longer periods in only a few locations.
B. The model in details
SWIM assigns each node a home and chooses destinations using weights that combine popularity with distance from home. It then models movement and waiting times to reproduce social and temporal mobility patterns.
- Destination selection: Each node receives a uniformly random home, and each destination’s weight increases with popularity while decreasing with distance from that home.The weight determines the probability of choosing a destination as the next location.
- Destination selection: The continuous network area is divided into cells, and nodes choose cells randomly in proportion to their weights before selecting a point uniformly within the chosen cell.Visited-cell information updates the popularity measure used for later choices.
- Movement: Nodes travel in straight lines at a distance-proportional constant speed, making every movement leg take constant time.The simulator sets speed equal to the distance between starting point and destination.
- Weight components: For a node A and cell C, seen(C) records encountered nodes, while distance(h_A,C) uses the cell center to measure distance from home.The distance function decays as a power law as the cell moves farther from home.
- Weight components: α ranges from 0 to 1 and controls the destination trade-off: larger values favor home-near places, while smaller values favor popular places.The paper associates both extremes with clustering, through locality or destination popularity respectively.
- Waiting time: Waiting times are intended to follow a power law because people stay longer in only a few places and briefly in many others.The paper contrasts this choice with the observed exponential cutoff in inter-contact times.
C. Power law and exponential decay dichotomy
SWIM reproduces the observed inter-contact-time dichotomy: a power-law head followed by an exponential cutoff. The paper also proves exponential tail decay under explicit assumptions.
- SWIM’s inter-contact-time distribution matches the real-trace dichotomy, with a power-law head followed by an exponential cutoff.When properly tuned, its distribution is described as strikingly similar to real-life experiments.
- The proof defines inter-contact time as the first t > 0 when nodes A and B return within transmitting radius r after separating.The nodes’ positions are represented by A(t) and B(t), with Euclidean distance determining visibility.
- Theorem 1 states that SWIM’s inter-contact-time tail has exponential decay when α > 0 and Assumption 1 holds.Assumption 1 requires distance(A,C) to be at least µ > 0 for every node and cell.
- The proof samples node positions at times separated by λ, choosing λ so each node makes a waypoint decision and completes a movement leg between snapshots.It additionally requires at least one node to be stationary at each intermediate snapshot.
- At each relevant snapshot, one node can choose the other’s cell with probability at least αµ, yielding the exponential tail bound.The conditional argument allows dependence on previous decisions rather than assuming independent node movements.
IV. REAL TRACES
The evaluation compares SWIM against three real-device traces: Cambridge 05, Cambridge 06, and Infocom 05. These datasets differ in device counts and durations.
- SWIM is evaluated against three traces collected using real devices carried by people: Infocom 05, Cambridge 05, and Cambridge 06.The comparison focuses on characteristics including inter-contact and contact distributions.
- Cambridge 05 used 12 Intel iMotes distributed to University of Cambridge students over 5 days.
- Cambridge 06 used 36 mobile devices plus 18 stationary devices over 11 days, although the stationary-node data were excluded.
- Infocom 05 used 41 devices distributed to students at the Infocom 2005 workshop over approximately 3 days.
A. The simulation environment
The simulation environment is a discrete-event simulator configured with node count, transmitting radius, simulation time, and destination waiting-time distribution. It outputs records for mobility and contact events.
- SWIM is evaluated with a discrete-event simulator whose inputs include node count, transmitting radius, simulation time, and destination waiting-time distribution.
- The simulator’s output is an event-record text file rather than a continuous record of node positions.Geographical positions could be added, but the event format already supports computing the reported contact measures.
- The simulator records Meet, Depart, Start, and Finish events with node or location identifiers and event times.Finish events record destination, node, and time; the output contains enough information to compute inter-contact intervals and contact statistics.
- During simulation, each sensor maintains a seen(C) vector that is updated at Finish and Start events but not during movement.Nodes need not agree on cell popularity, and the evaluated scenarios are not large enough to create a memory problem.
B. The experimental results
The experiments tune SWIM’s few parameters to three real scenarios and compare inter-contact and contact statistics. Across all experiments, one parameter choice matches all considered metrics simultaneously.
- The experiments tune SWIM to Infocom 05, Cambridge 05, and Cambridge 06 using inter-contact CCD, contact distribution, and contacts per node pair.These metrics represent information-transfer frequency and aspects of relationships between people.
- 300×300 m2, 41 nodes, and 3 days approximate the Infocom 05 scenario in the simulator.The real experiment took place in a relatively small area, described as a large hotel.
- For the Cambridge scenario, the simulator uses 11 nodes and 5 days, with α = 0.95 providing the best fit to the real traces.The parameter choice reflects more frequent meetings among students in the same year.
- Across all three experiments, SWIM generates synthetic traces that approximate the real traces.
- The same parameter choice produces good results for all considered metrics simultaneously in each experiment.
VI. COMPARATIVE PERFORMANCE OF FORWARDING
SWIM is evaluated by running Epidemic Forwarding and simplified Delegation Forwarding on real and synthetic traces, using the same tuning fitted to real traces. The results are intended to test SWIM's trace quality rather than forwarding-protocol quality.
- Protocol comparison: The evaluation compares Epidemic Forwarding and simplified Delegation Forwarding on real traces and SWIM-generated traces.The simplified delegation protocol is used as a worst-case benchmark against Epidemic Forwarding.
- Evaluation setup: The SWIM parameters used for forwarding evaluation are unchanged from those fitted to the real traces.They are not optimized separately for either forwarding protocol.
- Evaluation setup: Traffic uses uniformly random sources and destinations, Poisson message generation averaging one message per 4 seconds, infinite buffers, and persistent replicas.These assumptions are applied to each trace and forwarding protocol.
- Forwarding rules: Epidemic Forwarding sends a message unless the recipient already has a replica, providing upper bounds on success rate and average delay at high cost.Delegation Forwarding instead forwards only to nodes whose quality exceeds the message copy's current rate.
- Results: SWIM predicts the performance of both forwarding protocols very accurately on synthetic traces compared with real traces.The paper links this result to tuning SWIM using statistical properties such as inter-contact time, contact counts, and contact duration.
VII. CONCLUSIONS
The conclusion presents SWIM as a simple mobility model that produces realistic traces and accurately estimates forwarding-protocol performance. It also positions the model as useful for studying mobility and scaling to systems without real traces.
- VII. CONCLUSIONS: SWIM is presented as a simple ad hoc-networking mobility model that generates traces resembling real traces.The conclusion summarizes the model as simple, realistic, and accurate for forwarding-protocol estimation.
- VII. CONCLUSIONS: SWIM is reported to provide accurate estimates of forwarding-protocol performance in real mobile networks.This is stated as one of the model's principal conclusions.
- VII. CONCLUSIONS: SWIM is described as useful for improving understanding of human mobility and supporting theoretical work.The conclusion also identifies protocol-performance evaluation as an application.
- VII. CONCLUSIONS: The Infocom 05 comparison includes inter-contact-time and contact-duration distributions for the real trace and SWIM.The figure labels identify these two comparison panels.
- VII. CONCLUSIONS: SWIM is intended to scale to very large mobile systems for which real traces are unavailable.This is presented as a supported use case of the model.
P[X>T]
The supplied passages identify Cambridge 05 and Cambridge 06 comparisons with SWIM, alongside related mobility and opportunistic-forwarding work. They do not provide a substantive description of the P[X>T] results.
- P[X>T]: Figure 2 compares SWIM with Cambridge 05.The supplied caption names the two traces but does not state an outcome.
- P[X>T]: The surrounding references concern user mobility, pocket-switched networks, and opportunistic-forwarding algorithms.These topics are represented by the cited related-work entries.
- P[X>T]: Figure 3 compares SWIM with Cambridge 06.The supplied figure label names the two traces but does not state an outcome.