Hisso & Enhanced Hisso: Solving the Dynamic Routing Puzzle in Impromptu Mobile Social Networks

TL;DR

Researchers have developed Hisso and Enhanced Hisso, two hybrid routing algorithms specifically designed for "Impromptu" Mobile Social Networks (IMSNs)—networks formed on the fly at events like conferences or festivals. By combining Linear Regression on contact history with Dynamic Social Similarity, these algorithms significantly outperform traditional static social routing in terms of delivery ratio and latency.

Context: The Chaos of Impromptu Networks

Most Social Network Analysis (SNA) assumes a somewhat stable environment. However, in an IMSN, links are "time-dependent and short-term." You might be a "New Yorker" in your profile, but for three days at a conference in Texas, your social behavior is dictated by the event, not your home state.

Existing methods like Social-Profile-based (using static data like nationality) or Social-Analysis-based (using static graphs) fail because:

1. Temporal Loss: Aggregating contacts into a static graph ignores when people meet.
2. Context Shift: Static profiles don't capture immediate, event-driven mobility.

Methodology: The Power of Two Predictors

The authors suggest that to predict a future encounter ($r_{ud}$), we need to look at both the past and the "social vibe" of the current environment.

1. The History Predictor ($h_{ud}$)

Instead of just counting meetings, the authors use Least-Squares Linear Regression. By dividing time into intervals ($t$), they predict the number of contacts in the next interval ($n_{t+1}$). This captures whether two nodes are meeting more or less frequently over time.

2. The Dynamic Social Predictor ($s_{ud}$)

This is the "secret sauce." Instead of looking at a node's profile, it tracks who the node meets. If Node A meets "English-speaking Students" 90% of the time, and the destination is an English-speaking student, Node A is a statistically brilliant forwarder—regardless of Node A's own profile.

3. The "Social Circle" Innovation

Enhanced Hisso takes this further. It doesn't just look for the destination; it looks for the destination's "Social Circle"—a group of nodes socially similar to the target. This broadens the search space and avoids the "dead-end" problem in sparse opportunistic networks.

The weighted hybrid prediction formula (2) used in Enhanced Hisso.

Experiments & Results

The algorithms were tested using the INFOCOM 2006 trace, a real-world dataset of Bluetooth contacts among conference attendees.

Key Findings:

• Optimal Weighting: The study found that a 75/25 split ($\alpha =0.75,\beta =0.25$) between History and Social predictors yielded the best results, suggesting that direct history is the strongest signal, but social dynamic data is essential for "filling the gaps."
• Superiority over SOTA: Both Hisso variants beat "Profile" and "Analysis" based methods.
• Benefit of Multi-copy: Implementing the algorithms within a "Spray-and-Focus" framework (spreading 4 copies) maximized delivery without flooding the network.

Comparison of delivery ratio and latency across different routing strategies.

Critical Insight: Why it Works

The brilliance of Hisso lies in its Inductive Bias toward the temporal nature of human movement. By treating social features as a dynamic vector (the frequency of encountering certain types of people) rather than a static label, the model adapts to the "Impromptu" nature of the network.

Limitations & Future Work

• Computational Overhead: Calculating Euclidean similarity and linear regression on mobile devices with limited battery remains a concern for very large-scale networks.
• Trace Dependency: The results are highly dependent on the INFOCOM trace; different social settings (e.g., a city vs. a single building) might require different $\alpha /\beta$ weights.

Conclusion

The Hisso family of algorithms proves that in the volatile world of opportunistic networks, history + real-time social context is the winning formula. For developers of decentralized messaging apps or emergency response networks, the shift from static graphs to dynamic social predictors offers a clear path to more reliable communication.