On Exploiting Hotspot and Entropy for Data Forwarding in Delay Tolerant Networks

Peiyan Yuan, Huadóng Ma, Shaojie Tang

TL;DR

This paper introduces "Hoten," a novel routing metric for Delay Tolerant Networks (DTNs) that leverages human mobility patterns, specifically "hotspots" (frequently visited locations), and information theory (entropy) to predict node behavior. Hoten significantly outperforms existing methods in terms of message delivery and efficiency by better understanding social structures and individual "personalities."

What Problem Does This Paper Address?

Delay Tolerant Networks (DTNs) are characterized by intermittent connectivity, making traditional routing protocols ineffective. This is common in scenarios like interplanetary communication, vehicle ad-hoc networks, or even mobile devices that frequently lose connection. The challenge lies in efficiently forwarding messages when there's no guarantee of an end-to-end path. While some approaches use social structures to improve routing, calculating traditional social network metrics like centrality and similarity is computationally expensive and difficult in the dynamic, intermittently connected DTN environment. This paper aims to find more stable and computationally feasible social attributes to enhance DTN routing.

Methods

The core of the Hoten metric is built upon identifying and analyzing "hotspots" derived from real-world GPS traces. The authors propose a multi-faceted approach:

  • Hotspot Identification: They define two types of hotspots: "public hotspots" (locations frequently visited by many people) and "personal hotspots" (locations a specific individual frequently visits). They also introduce a method to determine the optimal size of these hotspots using the Hurst parameter to capture the bursty nature of human movement.
  • Centrality Measurement: Instead of traditional degree or betweenness centrality, Hoten uses the relative entropy between a node's personal hotspots and the system's public hotspots. A lower relative entropy indicates a node's personal habits align with common public locations, suggesting higher centrality.
  • Similarity Measurement: The similarity between two nodes is calculated using the inverse symmetrized entropy of their personal hotspots. This quantifies how alike their individual movement patterns are.
  • Personality Estimation: A node's "personality" is estimated using the entropy of its personal hotspots. Higher entropy suggests a more diverse range of frequented locations, reflecting a unique behavioral pattern.
  • Hoten Metric: These three components (centrality, similarity, and personality) are combined into a single utility score using a weighted linear combination. This score helps predict the likelihood of a message reaching its destination via a particular relay node.

Datasets

The authors evaluated their Hoten metric using five real-world DTN datasets:

  • KAIST
  • NCSU
  • New York City
  • Orlando
  • North Carolina State Fair

These datasets, collected over a period of approximately two years, represent a range of environments from well-connected to sparse.

Key Insights and Ideas

  • Hotspots as Stable Social Attributes: The paper argues that "hotspots" (both public and personal) are more stable indicators of social behavior than dynamic network topology or traditional social network metrics in DTNs.
  • Entropy for Quantifying Behavior: Leveraging information theory (entropy) provides a computationally efficient way to quantify complex behaviors like centrality, similarity, and personality from mobility data.
  • Personality Matters in Routing: Incorporating a node's "personality" (derived from their unique hotspot entropy) into routing decisions leads to more accurate predictions and improved performance.
  • Optimizing Hotspot Size: The use of the Hurst parameter to determine the optimal size of hotspots is a novel approach to balance the granularity of location data with the need for robust pattern identification.

Key Results

The Hoten metric demonstrated significant improvements over baseline routing schemes (Epidemic and SimBet) in trace-driven simulations:

  • Combined Overhead/Packet Delivery Ratio: Hoten largely outperforms other solutions in terms of this combined metric.
  • Average Number of Hops per Message: Hoten achieved a substantially lower average number of hops per message (e.g., near 7 hops at KAIST) compared to Epidemic (around 27 hops) and SimBet (around 41 hops).
  • Cumulative Packet Delivery Ratio (CPDR): Hoten generally improved CPDR over SimBet, though Epidemic still showed the highest CPDR (at the cost of higher overhead). An exception was noted at the "State Fair" dataset where SimBet performed better, attributed to the rapid convergence of adjacency matrices in well-connected scenarios.
  • Mean Delivery Delay: Epidemic had a better mean delivery delay, but Hoten's slightly longer delay was attributed to its ability to deliver messages that might have been dropped by SimBet.

Limitations and Future Work

  • Temporal Correlation: The authors acknowledge that the influence of temporal correlation of stay points on Hoten's performance is an area for future research.
  • Parameter Tuning: While the paper sets parameters for Hoten (e.g., weights for centrality, similarity, and personality) to 1/3, further investigation into optimal parameter tuning for different scenarios could be beneficial.
  • Dataset Specificity: The performance of Hoten might be influenced by the specific characteristics of the datasets used. Testing on a wider variety of mobility traces could provide more generalizable insights.

Summary updated

Abstract

Performance of data forwarding in Delay Tolerant Networks (DTNs) benefits considerably if one can make use of human mobility in terms of social structures. However, it is difficult and time-consuming to calculate the centrality and similarity of nodes by using solutions for traditional social networks, this is mainly because of the transient node contact and the intermittently connected environment. In this work, we are interested in the following question: Can we explore some other stable social attributes to quantify the centrality and similarity of nodes? Taking GPS traces of human walks from the real world, we find that there exist two known phenomena. One is public hotspot, the other is personal hotspot. Motivated by this observation, we present Hoten (hotspot and entropy), a novel routing metric to improve routing performance in DTNs. First, we use the relative entropy between the public hotspots and the personal hotspots to compute the centrality of nodes. Then we utilize the inverse symmetrized entropy of the personal hotspots between two nodes to compute the similarity between them. Third, we exploit the entropy of personal hotspots of a node to estimate its personality. Besides, we propose a method to ascertain the optimized size of hotspot. Finally, we compare our routing strategy with other state-of-the-art routing schemes through extensive trace-driven simulations, the results show that Hoten largely outperforms other solutions, especially in terms of combined overhead/packet delivery ratio and the average number of hops per message.
BibTeX
@misc{yuan2012exploiting,
  author = {Peiyan Yuan and Huadóng Ma and Shaojie Tang},
  title = {{On Exploiting Hotspot and Entropy for Data Forwarding in Delay Tolerant Networks}},
  year = {2012},
  eprint = {1205.0652},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1205.0652},
}
Figure