CPR: Leveraging Social Routines for Optimal Routing in Mobile Social Networks

TL;DR

Mobile Social Networks (MSNs) often struggle with "broken" links caused by user movement. The Contact Probability based Routing (CPR) protocol turns this challenge into an advantage by modeling the predictable nature of human life. By predicting when and where a user will likely meet others based on their weekly routines, CPR selects the most "socially active" nodes as data carriers, significantly boosting delivery speed and success rates.

Problem & Motivation: The Chaos of Mobility

In an ideal network, every node is always connected. In an MSN, nodes (phones, pads) only connect when they are within Wi-Fi or Bluetooth range—a scenario technically known as a Delay Tolerant Network (DTN).

Prior works like Socialcast attempted to use Kalman filters to predict movement, but they often missed the "social" in social networks. People aren't random particles; they have Life Regulations. We go to the same office at 9 AM and the same gym on Tuesdays. Existing protocols failed to capture this periodic habit, leading to "carriers" who held onto data but never met the intended recipients.

Methodology: Human Predictability as an Algorithm

The core innovation lies in two models: CPEM and UCM.

1. Contact Probability Estimating Model (CPEM)

CPR maintains a contact log that divides a day into $K$ time slots. It doesn't just treat all history equally; it uses a weighted system where contacts from 1 day ago and 1 week ago carry more weight because human behavior is most likely to repeat on those cycles.

$P_{ij}=\frac{{\sum }_{k=1}^L{w}_k\cdot N_{ij,-k}}{{\sum }_{k=1}^L{N}_{ij,-k}}$

2. Utility Compute Model (UCM)

How do you choose the best "courier" for a message? The UCM calculates a Utility score ($U_i$). A node is a good carrier if it has a high probability of meeting interested users soon.

The protocol uses a Reference Window ($\gamma$)—a "look-ahead" mechanism that evaluates potential contacts in the immediate future time slots.

Experiments & Results

The authors tested CPR against Socialcast using the Agenda Driven model, which simulates realistic human activities (work, home, social).

Key Findings:

• The Power of Weights: The best performance was achieved when weights for "1 day ago" and "7 days ago" were prioritized, proving that our weekly rhythm is the strongest predictor of connectivity.
• Reference Window Optimization: As shown in the charts below, a window size of approximately 4 to 6 slots balances high delivery efficiency with low delay.
• Superior Efficiency: CPR consistently outperformed Socialcast. Even with a small percentage of carriers (6.25%), CPR reached a higher delivery efficiency in a shorter time frame.

Critical Insight & Conclusion

CPR demonstrates that context-aware routing is more than just tracking GPS; it’s about modeling social behavior. By formalizing the repetitive nature of social life into the CPEM log, the network transforms from a collection of moving parts into a structured, predictable system.

Limitations: The paper honestly notes that being a "carrier" consumes battery and memory. Furthermore, maintaining a detailed contact log raises privacy concerns. If a carrier knows where I will be next Tuesday, that is sensitive data. Future research must integrate Privacy-Preserving Computation to mask individual identities while still allowing the utility of the group pattern to be harvested.

The Takeaway: For future MSN architectures, the focus should shift from reactive routing (responding to a connection) to proactive routing (positioning data where a connection is likely to happen).