Wireless Relay Selection in Pocket Switched Networks Based on Spatial Regularity of Human Mobility

Jian-Hui Huang, Xiuzhen Cheng, Jingping Bi, Biao Chen

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

Abstract

Pocket switched networks (PSNs) take advantage of human mobility to deliver data. Investigations on real-world trace data indicate that human mobility shows an obvious spatial regularity: a human being usually visits a few places at high frequencies. These most frequently visited places form the home of a node, which is exploited in this paper to design two HomE based Relay selectiOn (HERO) algorithms. Both algorithms input single data copy into the network at any time. In the basic HERO, only the first node encountered by the source and whose home overlaps a destination’s home is selected as a relay while the enhanced HERO keeps finding more optimal relay that visits the destination’s home with higher probability. The two proposed algorithms only require the relays to exchange the information of their home and/or the visiting frequencies to their home when two nodes meet. As a result, the information update is reduced and there is no global status information that needs to be maintained. This causes light loads on relays because of the low communication cost and storage requirements. Additionally, only simple operations are needed in the two proposed algorithms, resulting in little computation overhead at relays. At last, a theoretical analysis is performed on some key metrics and then the real-world based simulations indicate that the two HERO algorithms are efficient and effective through employing only one or a few relays.
BibTeX
@article{huang2016wireless,
  author = {Jian-Hui Huang and Xiuzhen Cheng and Jingping Bi and Biao Chen},
  title = {{Wireless Relay Selection in Pocket Switched Networks Based on Spatial Regularity of Human Mobility}},
  journal = {Sensors},
  year = {2016},
  doi = {10.3390/s16010094},
}
Figure