“Instead of telling EVERYONE my message like in epidemic routing,” said Sammy the Sensor, “what if I only tell people who are LIKELY to meet the person I’m trying to reach?”
Max the Microcontroller snapped his fingers. “Like if you need to send a message to the school librarian, don’t give copies to random strangers – give it to kids who go to that school every day!”
“Exactly!” said Bella the Battery. “That’s social routing! Each person gets a ‘usefulness score.’ The kid who visits the library every day scores 0.9 out of 1.0. A random tourist scores 0.1. You only hand your message to high-scoring people!”
Lila the LED added, “And the best part is: you only make 5-10 copies instead of hundreds. Each copy finds its way to a better and better messenger until someone delivers it. It’s like your message ‘climbs’ toward the destination!”
The Squad’s math: Epidemic routing = 95% delivery but 1000% overhead (expensive!). Social routing = 88% delivery but only 200% overhead (5x cheaper!). For battery-powered sensors, that savings means years more battery life!
By the end of this chapter, you will be able to:
Before diving into this chapter, you should be familiar with:
DTN Series:
Background:
Learning:
When node mobility is predictable or observable, smarter forwarding decisions can be made using context information.
Rather than blindly replicating packets, CAR uses utility functions to select best carriers based on:
Basic Utility Function:
\[ U(X, D) = \alpha \cdot P_{colocation}(X, D) + \beta \cdot Mobility(X) + \gamma \cdot Resources(X) \]
Where: - \(U(X, D)\) = Utility of node X for delivering to destination D - \(P_{colocation}(X, D)\) = Probability X will encounter D - \(Mobility(X)\) = Mobility score (higher = visits more locations) - \(Resources(X)\) = Battery level, buffer space - \(\alpha, \beta, \gamma\) = Weighting parameters
For a delivery vehicle passing city hall 3 times/day versus once/week, the encounter probability scales linearly: \(P_{daily} = 3/24 = 0.125\) per hour versus \(P_{weekly} = 1/168 = 0.006\) per hour. With \(\alpha=0.6\), \(\beta=0.3\), \(\gamma=0.1\) and typical freshness/battery values of 0.8/0.9:
\[U_{vehicle} = 0.6(0.125) + 0.3(0.8) + 0.1(0.9) = 0.075 + 0.24 + 0.09 = 0.405\]
versus pedestrian (once/week):
\[U_{pedestrian} = 0.6(0.006) + 0.3(0.8) + 0.1(0.9) = 0.004 + 0.24 + 0.09 = 0.334\]
The 21% utility advantage (\(0.405 / 0.334 = 1.21\)) means messages preferentially climb to vehicle carriers, reducing delivery time from 7 days to ~8 hours despite only 21% better utility.
Colocation Prediction (Kalman Filter):
CAR uses Kalman filter to predict future encounters based on past history:
def predict_colocation(node_x, node_d, history):
"""
Predict probability node_x will encounter node_d
based on past encounter history using Kalman filter
"""
# Historical encounter frequency
encounters = sum(1 for t in history if met(node_x, node_d, t))
total_windows = len(history)
# Kalman filter state
# (Simplified - real implementation more complex)
predicted_rate = encounters / total_windows
# Adjust for time since last encounter
time_since_last = time_now() - last_encounter_time(node_x, node_d)
decay_factor = exp(-time_since_last / DECAY_CONSTANT)
return predicted_rate * decay_factorExample Scenario:
Performance Comparison:
| Metric | Epidemic | CAR |
|---|---|---|
| Delivery Ratio | 95% | 88% |
| Overhead (copies) | 15.3 | 3.2 |
| Average Latency | 450s | 520s |
| Energy per Delivery | High | Medium |
Trade-off:
SocialCast extends CAR by exploiting social network structures for packet dissemination.
Message Replication Strategy:
Key Properties:
Delivery vs Replicas:
Overhead vs Replicas:
Optimal Configuration:
TTL Impact:
Scenario: A smart city deploys sensors on delivery vehicles for air quality monitoring. Calculate which vehicle should carry pollution alerts to city hall.
Given:
Steps:
Result: Message forwarded from Vehicle A to Vehicle B (or C), increasing delivery probability from 14% to 100% per day.
Key Insight: SocialCast’s “utility climbing” ensures messages naturally flow toward nodes with better access to the destination. The delivery vehicle example shows how urban mobility patterns create predictable utility scores that SocialCast can exploit.
Question 1: In context-aware routing, what is the primary purpose of the utility function U(X, D)?
b) To calculate the probability that node X will successfully deliver a message to destination D. The utility function combines colocation probability (how often X encounters D), mobility patterns, and available resources (battery, buffer) into a single score. Messages are forwarded only to nodes with higher utility scores, ensuring they “climb” toward better carriers over time.
Question 2: Why does SocialCast use bounded replication (gamma copies) instead of unlimited replication like epidemic routing?
b) Bounded replication limits resource consumption while maintaining good delivery. SocialCast creates only gamma copies (typically 5-10), which is sufficient for 88-93% delivery but uses 3-5x fewer resources than epidemic routing’s unlimited copies. For battery-constrained IoT devices, this resource efficiency is critical. The slight reduction in delivery ratio (from 95% to 88%) is an acceptable trade-off.
Question 3: A delivery vehicle (Vehicle B) passes city hall 3 times per day. Another vehicle (Vehicle A) passes it once per week. Using SocialCast’s forwarding rule, what happens when Vehicle A carrying a message for city hall encounters Vehicle B?
b) Vehicle A forwards the message to Vehicle B because B has higher utility. SocialCast’s core rule is: forward only to nodes with utility(neighbor) > utility(self). Vehicle B’s encounter rate with city hall (3/day) is much higher than Vehicle A’s (1/week), giving B a higher utility score. The message “climbs” to the better carrier, dramatically increasing delivery probability from 14% to nearly 100% per day.
| Concept | Relationship | Connected Concept |
|---|---|---|
| Utility Functions | Select carriers based on combined | Encounter Probability and Mobility Patterns |
| SocialCast Bounded Replication | Creates limited copies that climb toward | Higher-Utility Carriers |
| Context-Aware Routing | Reduces overhead dramatically compared to | Epidemic Flooding |
| Colocation Prediction | Uses past encounter history to estimate | Future Contact Probability |
| Social Network Structures | Exploit predictable human/animal patterns enabling | Intelligent Forwarding Decisions |
Social routing relies on contact history as a predictor of future contacts. Work schedules, commuting patterns, and social behavior change over weeks and months. Routing decisions based on stale contact history (months old) may be less accurate than routing based on current network state. Implement contact history decay to weight recent contacts more heavily.
Betweenness centrality requires global network graph knowledge — knowing all nodes and their interconnections. In a distributed DTN, this information is unavailable. Practical social routing uses local approximations (encounter counts, two-hop neighbor counts) that underestimate true centrality.
Social routing exploits human mobility patterns (workplace, home, social events). Animal tracking, vehicle networks, or robot swarms have different mobility patterns that may not exhibit the community structure social routing exploits. Always validate that the target environment exhibits social-like contact patterns before applying social routing.
Social routing requires nodes to share and track contact history. This creates detailed records of who met whom and when — personal location data. Deployments must consider privacy implications and anonymization techniques. Publishing contact graphs can reveal sensitive information about individuals’ movements.
This chapter covered context-aware and social-based DTN routing:
| If you want to… | Read this |
|---|---|
| Study DTN epidemic routing | DTN Epidemic Routing |
| Learn DTN fundamentals | DTN Store-Carry-Forward |
| Explore DTN application domains | DTN Applications |
| Review social DTN and hybrid approaches | DTN, Social Routing and VANET Integration |
| Study UAV swarm coordination | UAV Swarm Coordination |
103.5.1 SocialCast Concepts
Key Insight: People with similar interests tend to be colocated periodically.
Application: Publish-subscribe in DTN - Publishers: Generate content - Subscribers: Want to receive content matching interests - Carriers: Mobile nodes with high utility transport messages