TL;DR
This paper introduces two novel algorithms, HERO (HomE based Relay selection), for efficient data delivery in Pocket Switched Networks (PSNs). By exploiting the predictable spatial regularity of human mobility, HERO selects relays based on their "home" locations, significantly reducing communication overhead and improving delivery efficiency compared to existing methods.
What Problem Does This Paper Address?
Pocket Switched Networks (PSNs) leverage the mobility of users and their devices to form opportunistic communication networks. Unlike traditional IP-centric networks, PSNs are characterized by intermittent connectivity, limited resources, and time-varying topologies, making them suitable for delay/disruption tolerant communications. A critical challenge in PSNs is relay selection: choosing the right intermediate nodes to forward data efficiently. Existing methods often require global network knowledge, frequent updates, or impose heavy burdens on nodes, hindering scalability and efficiency. This paper addresses the need for a lightweight, scalable, and efficient relay selection mechanism that can operate with minimal overhead.
Methods
The core innovation of this paper lies in the HERO (HomE based Relay selection) model, which capitalizes on the observed spatial regularity of human mobility. The authors define a node's "home" as the set of locations it visits with high frequency.
- HERO Model: The network is divided into zones, and each node has a "home" consisting of frequently visited zones. Relay selection is based on the proximity of a potential relay's home to the destination's current zone.
- Basic HERO Algorithm: This algorithm selects the first encountered node that is a "home node" (its home overlaps with the destination's zone) as a relay.
- Enhanced HERO Algorithm: This algorithm refines the selection by considering the "intensity of visiting" (frequency of visits) to the destination zone, aiming to find a relay with a higher probability of reaching the destination.
Both algorithms are designed to be:
- Lightweight: Requiring only local information and minimal updates.
- Scalable: Not needing global network status.
- Efficient: Minimizing computation and storage overhead on nodes.
Datasets
The primary dataset used for evaluation is the Dartmouth College's wireless local area network (WLAN) mobility trace data. This dataset records the mobility trajectory of nodes, allowing the authors to analyze spatial regularity and validate their algorithms. The authors note that this dataset is used to represent visited places by associated Access Points (APs).
Key Insights and Ideas
- Human Mobility is Predictable: The most significant insight is that human movement exhibits strong spatial regularity, with individuals frequently returning to a few key locations. This predictability is a valuable resource for network design.
- "Home" as a Routing Anchor: Defining a node's "home" based on frequently visited locations provides a stable and effective basis for relay selection, reducing the need for dynamic, real-time routing decisions.
- Reduced Overhead: By relying on "home" information and local encounters, HERO drastically cuts down on the communication and storage burdens typically associated with PSN routing protocols.
- Enhanced vs. Basic HERO: The enhanced HERO, by considering visiting intensity, offers improved performance over the basic version, demonstrating the benefit of finer-grained relay selection.
Key Results
- Improved Delivery Ratio: The HERO algorithms, particularly the enhanced version, show a higher delivery ratio compared to the MobySpace algorithm, especially as the average home size increases.
- Reduced Relay Latency: The enhanced HERO consistently demonstrates lower average relay latency than the basic HERO.
- Efficiency: The algorithms are shown to be efficient, with low computation and communication overhead.
- Comparison: While Epidemic routing offers the best delivery ratio, it comes with significantly higher transmission costs. HERO algorithms provide a good balance between performance and cost, outperforming MobySpace.
Limitations and Future Work
- Single-Copy Focus: The current HERO algorithms are designed for single-copy data delivery. The authors suggest that the relay selection principles can be ported to multi-copy strategies, but this is a direction for future work.
- Large-Scale Sparse Networks: In very large and sparse networks, the "slow-start phase" can be an issue, leading to slow data propagation. The authors propose a variant that selects the closest home-based relay if a suitable one isn't found quickly.
- Multi-Copy Variants: Future work will focus on developing multi-copy versions of HERO.
- Sociality Integration: The authors plan to design a "Social HERO" framework that incorporates both mobility and social characteristics of human beings for even more effective relay selection.
Summary updated