TSSD: Rethinking Service Discovery in Mobile Social Networks through Temporal-Spatial Correlation

TL;DR

In the world of intermittently-connected Mobile Social Networks (MSN), finding a specific service—like a song or real-time traffic data—is like finding a needle in a moving haystack. TSSD (Temporal-Spatial correlation-based Service Discovery) moves away from unreliable keywords and static social ties. Instead, it leverages the mathematical "rhythm" of human movement to build time-varying communities, resulting in faster discovery and lower network strain.

The "Colleague Paradox": Why Current Methods Fail

Existing service discovery schemes generally fall into two camps:

1. Keyword-based (e.g., SPOON): Relies on users tagging their interests. However, inaccurate tagging and "topology mismatch" (where users with similar interests are physically far apart) often lead to irrelevant results.
2. Social-based (e.g., SSGQ): Relies on social ties. The fatal flaw here is what we might call the "Colleague Paradox": you might spend 8 hours a day in the same office as someone (high social tie), but while you want road traffic updates, they want the latest sports scores. Physical proximity does not equal interest alignment.

The Core Innovation: Time-Varying Communities

The authors of TSSD recognize that human behavior is regular but dynamic. We aren't just "points" in a social graph; we are entities moving through time and space.

1. Social Closeness Strength

Instead of just counting meetings, the authors define a metric that considers the average inter-contact time and frequency.

$T_{ij}=\frac{{\int }_{t=0}^{T}f(t)dt}{k}$

This formula captures the "direct" bond between nodes, ensuring that "closeness" accounts for how long you stay apart, not just how often you bump into each other.

2. The Transition Model

A community at a university library at 10:00 AM is a "Learning Community." By noon, those same people in a cafeteria form a "Dining/Comprehensive Community." TSSD uses a state transition matrix to predict these shifts, ensuring that query messages are routed to nodes that are likely to be in the right place at the right time.

Fig 1. Visualizing contact patterns used to calculate the social closeness metric.

How TSSD Finds Services

Discovery happens in two stages:

• Intra-community: If you're looking for something, TSSD uses an efficient version of Epidemic Routing (limited by a Time-to-Live/TTL value) to spread the word among your current group.
• Inter-community: If the service isn't local, TSSD finds a "bridge" node. This node is chosen based on behavior similarity (historical trajectory overlap), ensuring the message moves toward the community most likely to hold the service.

Fig 2. The logic of routing between different temporal-spatial clusters.

Evidence from the Field: MIT and Sigcomm

To prove their theory, the authors analyzed real-world datasets from MIT Reality and Sigcomm 09. The "Heatmaps" generated (see Fig 3) clearly show rhythm-based behavior: users occupy working places from 8 AM to 6 PM and homes during the night. TSSD exploits this "predictable mobility" to route queries.

Key Performance Wins:

• Success Rate: TSSD matches the high performance of keyword-based systems without their inherent overhead.
• Latency: TSSD achieves the lowest query delay among all tested schemes because it doesn't waste time searching in "topology-mismatched" areas.
• Efficiency: Communication overhead is kept low, with successful discoveries typically occurring within 6 hops.

Fig 3. Query delay comparison showing TSSD's superior efficiency over SSGQ and SPOON.

Critical Insight & Conclusion

The brilliance of TSSD lies in its rejection of "static" social definitions. By treating communities as time-varying states rather than fixed sets of people, it bridges the gap between opportunistic networking and social reality.

Future Outlook: While TSSD is robust, its reliance on historical encounter records suggests that "Cold Start" problems (new users with no history) could be a limitation. Integrating this with lightweight federated learning could potentially allow new users to "borrow" behavior templates from similar profiles, further enhancing discovery in fresh environments.