Chapters

14 DTN Social Routing: Contact and Utility Models

emerging-paradigms
adhoc
dtn
social

14.1 Start With the Decision

A delay-tolerant node must choose a carrier before an end-to-end path exists. Contact history and utility scores guide that choice.

14.2 Route Overview

This is part 1 of 2. Continue with DTN Social Routing: Community and Forwarding Decisions.

14.3 Part Objectives

  • Compute forwarding utility from contact evidence.
  • Compare prediction and context-aware DTN routing.

14.4 Begin With a Better Carrier

A protocol means an agreed set of rules for passing data. Picture a health team whose staff carry phones between villages. One phone has a report for the clinic. Copying it to every phone may waste space and power. A better first choice may be a person who often reaches the clinic or meets people who do.

Start with a small contact record. Count who met whom, when, and for how long. Name the goal and the useful life of the report. Score two possible carriers with the same facts. Then check the result against a later set of meetings. Record copies, delivery, delay, energy, and any person or group that the rule leaves out.

Past contact can guide a choice, but people change shifts, routes, and habits. A popular carrier can become busy or reveal private patterns. Fewer copies save resources but may miss a rare path. This simple story does not prove that social ties stay stable or that the score is fair. Use the Practitioner layer to build a forwarding record and compare choices. Use the Under the Hood layer to inspect drift, utility maths, privacy, and resource bounds. Those deeper routes test the carrier rule before it becomes field policy.

Walk the first choice with names on paper. Sam meets Lee each day. Lee visits the clinic twice a week. Jo has more contacts but rarely goes near the clinic. The report expires tomorrow. Lee may be the best next carrier. Now change one fact. Lee starts a new shift. The old score may fail at once. Check age before each use. Check free space. Check power. Check whether the person agreed to this use. Keep a copy count. Keep a stop time. Keep a direct-send choice for rare urgent work.

The field record should stay easy to read. It should say why one carrier won. It should show the facts used that day. It should show who did not get a fair chance. It should show what happened after the copy left. If the report arrives, count the cost as well as the win. If it fails, keep the contact path that was tried. A useful rule learns from both results. It never treats a social score as a fixed fact about a person.

Run a small shadow test before the rule sends real work. Let the old route make the live choice. Let the new rule write only a suggested choice. Compare both with what later happened. Do this across work days, rest days, rain, and shift change. Look for one person who gets too much work. Look for one group that gets poor service. Change the rule or its limits before release.

Give people a clear way to leave the scheme. Remove old contact facts on time. Keep names out where a short device label will do. Limit who can read the contact map. A route plan can expose a human routine. Treat that risk as part of the network cost.

Set a plain stop rule. Stop broad copy when the report arrives. Stop when time ends. Stop when the copy cap is met. Stop when the carrier lacks safe space or power. Log the reason. A stopped copy is not always a failure; it may be the rule protecting the rest of the service.

14.5 Start Simple

Start with devices that have to pass useful data before any fixed network is guaranteed. In DTN Social Routing, the first question is not the protocol name; it is which neighbors, routes, failure signals, and degraded behaviors you would trust in the field.

14.6 Start With the Node That Usually Meets the Right People

Social routing starts from an observation: in many mobile systems, contacts are not random. Some devices, vehicles, people, or gateways regularly meet the communities that need the message.

For IoT deployments, that pattern can make forwarding more selective than flooding. Start with one carrier and one destination group. The routing question becomes whether past contact evidence is strong enough to trust the carrier with the next copy.

Chapter Roadmap
  • Begin With a Better Carrier
  • Start Simple
  • Start With the Node That Usually Meets the Right People
  • In 60 Seconds
  • Minimum Viable Understanding
  • Smart Messenger Service
  • Overview: Choose Carriers With Evidence
  • Forwarding Record
  • Checkpoint: Evidence Before Forwarding
  • Why Social Evidence Drifts
  • Prerequisites
  • Key Concepts
  • For Beginners: Social Routing
  • Related Chapters
  • Context-Aware Routing
  • Putting Numbers to It
  • Checkpoint: CAR Utility
  • Quick Check: Context-Aware Routing
In 60 Seconds

Context-aware routing (CAR) uses utility functions combining encounter probability, mobility patterns, and device resources to select optimal message carriers, reducing overhead to 200-350% while maintaining 88-93% delivery. SocialCast creates bounded replicas (gamma=5-10) that climb to higher-utility carriers over time. Social routing sacrifices ~7% delivery ratio compared to epidemic but uses 3-5x fewer resources — ideal for battery-constrained IoT with predictable mobility patterns.

Minimum Viable Understanding
  • Context-aware routing (CAR) uses utility functions combining encounter probability, mobility patterns, and resources to select the best message carriers, reducing overhead to 200-350% while maintaining 88-93% delivery
  • SocialCast creates a bounded number of message replicas (gamma=5-10) that “climb” to higher-utility carriers over time, exploiting social network structures for efficient publish-subscribe in DTN
  • The key trade-off: Social routing sacrifices ~7% delivery ratio compared to epidemic routing but uses 3-5x fewer resources, making it ideal for battery-constrained IoT devices with predictable mobility

“Instead of telling EVERYONE my message like in epidemic routing,” said Temperature Terry, “what if I only tell people who are LIKELY to meet the person I’m trying to reach?”

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 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!”

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!

14.7 Learning Objectives

By the end of this chapter, you will be able to:

  • Apply Context-Aware Routing: Use utility functions based on mobility, colocation, and resources
  • Design SocialCast Protocols: Implement social network-based forwarding with bounded replication
  • Calculate Utility Functions: Combine colocation probability, mobility scores, and resource levels
  • Optimize Forwarding Decisions: Select carriers based on delivery likelihood rather than flooding
  • Evaluate Trade-offs: Balance delivery ratio, latency, and resource consumption

14.8 Overview: Choose Carriers With Evidence

If you only need the intuition, this layer is enough: social DTN routing avoids copying every bundle to every contact. It forwards toward carriers that have measured evidence of reaching the destination, community, or subscriber group.

The word "social" does not mean the protocol guesses from labels such as friend, worker, or student. It means the forwarding decision uses observed contact structure: who meets whom, how recently, how often, for how long, and with what spare storage or battery. A campus shuttle, clinic nurse, field technician, or market bus can become a better carrier because the contact record shows repeated access to the destination group.

The humans behind those carriers usually play one of three overlapping roles in the wider sensing system: they can be the sensing target itself, as in personal health monitoring where the person's own body is what is measured; a sensor operator who carries and points a phone, wearable, or PDA at the surroundings; or a plain data source who shares an observation, such as a status update or a geotagged report, without carrying any dedicated sensor at all. Participatory sensing designs build on that last role deliberately: instead of only harvesting anonymous readings from a crowd, the goal is to let the same community access the aggregated data and act on it, using a geotagged location and timestamp as the evidence that a report is authentic. That framing matters for social DTN routing because it explains why device energy, participant selection, and privacy of users are recurring design pressures rather than incidental ones -- the "carrier" scoring this chapter builds on is a person first and a radio second.

The practical benefit is selectivity. Epidemic routing asks whether another node lacks the bundle. Social routing asks whether that node is a better future carrier than the current one, or whether an extra copy is justified by the replica budget. If the peer has weaker evidence, the correct action may be to keep the bundle and wait. That restraint is what saves energy and buffer space.

A useful overview therefore names the destination context as well as the carrier. Forwarding to "a central node" is incomplete; forwarding to a node that reliably reaches the clinic community, the maintenance team, or the bus depot is a measurable claim. The routing record should make that claim visible.

Before overview: Choose Carriers With Evidence, inspect Figure to compare "score peers" with "Candidate B". Their juxtaposition makes social DTN forwarding should choose the carrier with better measured utility, not the next random contact or every contact visible.

Context-aware DTN routing diagram showing a source comparing candidate carriers by encounter history, mobility, resource score, and total utility before forwarding to the highest-utility carrier for the destination.
Social DTN forwarding should choose the carrier with better measured utility, not the next random contact or every contact.

Read Figure from "score peers" to "Candidate B". Taken together, "score peers" and "Candidate B" express social DTN forwarding should choose the carrier with better measured utility, not the next random contact or every contact. For overview: Choose Carriers With Evidence, the observed relationship between "score peers" and "Candidate B" is evidence that "score peers" carries into the next decision.

Mobile summary: score candidate carriers by contact history, mobility, and resource state, then forward only when the peer has stronger evidence of reaching the destination.

Contact history

Past encounters estimate whether a carrier is likely to meet the destination again.

Community structure

Nodes that regularly meet the same group can carry messages into that group more efficiently.

Bounded copies

Protocols such as SocialCast keep the replica count limited so energy and buffer use remain controlled.

14.9 Forwarding Record

A social-routing design should record why one carrier is better than another. A utility score is useful only when the team can explain the measurement window, weighting, privacy limits, and resource constraints behind it.

Start by writing the score as a reviewable equation or decision table. Each input needs a unit, a sampling window, a decay rule, and a tie-breaker. For example, recent encounters with the destination may outrank older encounters, but a node with a nearly full buffer may still refuse the transfer. The record should state whether the protocol uses destination-specific utility, community membership, centrality, subscriber interest, or a combination of those signals.

Then test the rule with counterexamples. A highly central carrier may be useful for many destinations but overloaded; a familiar carrier may meet the destination often but have a weak battery; a privacy policy may forbid sharing raw encounter histories. The field acceptance run should replay at least one normal contact pattern, one schedule change, one full-buffer event, and one privacy-restricted contact trace before the score is trusted.

The forwarding record also needs a minimum-improvement rule. Transferring to a peer whose utility is only slightly higher can waste the contact window and create duplicate storage pressure. Many deployments require a threshold, such as "forward only when the peer score is higher by a configured margin" or "forward only when the peer reaches a community the current node rarely reaches." The exact number is local, but the rule must be explicit.

Utility inputs

Name the contact-history, mobility, centrality, similarity, battery, and buffer signals used by the score.

Forwarding rule

State when to transfer, keep, duplicate, expire, or refuse a bundle during a contact.

Replica budget

Record the gamma or copy limit, why it is acceptable, and what traffic gets priority when storage is tight.

Privacy boundary

Define what contact history can be stored, shared, anonymized, aggregated, or deleted.

Blueprint BinaCheckpoint: Evidence Before Forwarding

You now know:

  • Social routing does not forward to every contact; it forwards only when measured evidence says the peer is a better carrier.
  • A useful record names the sampling window, decay rule, resource limits, tie-breaker, and privacy boundary behind the score.
  • Old contact evidence can drift, so history decay and minimum-evidence rules matter as much as the utility formula.

14.10 Why Social Evidence Drifts

Social routing depends on patterns that can change. A strong carrier this month can become weak after a schedule change, event season, battery limit, buffer pressure, privacy policy, or community split.

Many social DTN protocols can be understood as local graph estimators. SimBet-style forwarding combines similarity to the destination's neighborhood with betweenness-like bridge value. Bubble Rap-style forwarding separates global centrality from community membership. CAR-style forwarding combines contact probability, mobility, and resource context. In constrained IoT nodes, these values are often approximated from encounter tables rather than computed from a complete graph.

That approximation creates drift. A node may look central because it used to meet everyone during a shift pattern that no longer exists. A community detector may lag after people move teams or a transport route changes. A resource score may be stale if battery and buffer readings are not refreshed before contact. Under the hood, the routing stack needs aging, confidence, and minimum-evidence rules so old social evidence cannot dominate new observations indefinitely.

Privacy controls also affect the algorithm. Raw contact graphs can reveal routines and relationships even when payloads are encrypted, so deployments may hash identifiers, aggregate counts, keep only local scores, or shorten retention windows. Those protections are useful, but they reduce what the routing layer can know. A defensible design records the resulting accuracy trade-off instead of pretending the privacy-preserving score is identical to an unrestricted encounter graph.

Failure handling closes the loop. When delivery drops, the investigation should compare the old score distribution with recent contact logs, not simply increase the replica budget. More copies can hide a stale utility model temporarily while draining the same resources social routing was chosen to protect.

  • History decay: recent contacts should usually matter more than old contacts.
  • Local approximation: practical nodes often estimate centrality from local or two-hop evidence, not a perfect global graph.
  • Replica discipline: bounded replication works only when transfer, expiry, and priority rules are enforced.
  • Privacy exposure: contact graphs can reveal movement and relationship patterns even when payloads are encrypted.

14.11 Prerequisites

Before diving into this chapter, you should be familiar with:

  • Social Routing: DTN routing exploiting human social patterns (community membership, centrality, contact frequency) for efficient message delivery
  • Social Centrality: Node’s position in a social network graph; highly central nodes (hubs) interact with many others and make better message carriers
  • Community Detection: Identifying groups of nodes that frequently contact each other; used in bubble routing and community-based routing
  • SimBet Routing: Combines social similarity (common contacts) and betweenness centrality to select next-hop carriers
  • Bubble Routing: Messages stay in source community until a node with higher global centrality can carry them to the destination community
  • Contact History: Past encounter records used to predict future contacts; stored in encounter tables indexed by node ID and time
  • Betweenness Centrality: Fraction of shortest paths in the social graph passing through a node; high-betweenness nodes are good message relays
  • Homophily: Tendency for people to contact socially similar others; enables community-based routing to outperform random routing

14.12 For Beginners: Social Routing

Social Routing - The Smart Strategy:

Instead of telling everyone (epidemic routing), tell people who are likely to meet the destination. Like asking “Can you deliver this message?” only to people who work near the recipient’s office.

SocialCast uses social patterns:

  • If Node A frequently encounters Node B, A has high “utility” for delivering to B.
  • Forward messages only to higher-utility carriers.
  • Bounded replication creates only 5-10 copies, not unlimited copies.
  • Result: high delivery with much lower overhead than epidemic flooding when contact patterns are predictable.

Key terms:

  • PRoPHET: forwards to nodes with stronger encounter history, like asking someone who often sees the recipient.
  • Utility function: scores delivery likelihood, like estimating which courier is most likely to reach an address.
  • Context-aware routing: uses location, mobility, relationships, and resources instead of forwarding blindly.

DTN Series:

DTN Fundamentals

Store-carry-forward foundation.

DTN Epidemic Routing

Flooding baseline for comparison.

DTN Applications

ZebraNet and DakNet deployments.

Ad Hoc Routing: Reactive (DSR)

Connected network on-demand routing.

Multi-Hop Fundamentals

Relay and forwarding concepts.

Background:

Learning:

14.13 Context-Aware Routing

Time: ~12 min | Difficulty: Intermediate | Unit: P04.C01.U03

When node mobility is predictable or observable, smarter forwarding decisions can be made using context information.

14.13.1 Context-Aware Routing (CAR) Concept

Rather than blindly replicating packets, CAR uses utility functions to select best carriers based on:

  1. Mobility patterns: Where do nodes typically move?
  2. Colocation history: Which nodes frequently encounter destination?
  3. Social relationships: Friend networks, interest groups
  4. Resources: Battery, buffer space

14.13.2 Utility Function Design

Basic Utility Function:

U(X,D)=α⋅Pcolocation(X,D)+β⋅Mobility(X)+γ⋅Resources(X)U(X, D) = \alpha \cdot P_{colocation}(X, D) + \beta \cdot Mobility(X) + \gamma \cdot Resources(X)

Where:

  • U(X,D)U(X, D) = Utility of node X for delivering to destination D
  • Pcolocation(X,D)P_{colocation}(X, D) = Probability X will encounter D
  • Mobility(X)Mobility(X) = Mobility score (higher = visits more locations)
  • Resources(X)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: Pdaily=3/24=0.125P_{daily} = 3/24 = 0.125 per hour versus Pweekly=1/168=0.006P_{weekly} = 1/168 = 0.006 per hour. With α=0.6\alpha=0.6, β=0.3\beta=0.3, γ=0.1\gamma=0.1 and typical freshness/battery values of 0.8/0.9:

Uvehicle=0.6(0.125)+0.3(0.8)+0.1(0.9)=0.075+0.24+0.09=0.405U_{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):

Upedestrian=0.6(0.006)+0.3(0.8)+0.1(0.9)=0.004+0.24+0.09=0.334U_{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.210.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.

Blueprint BinaCheckpoint: CAR Utility

You now know:

  • CAR combines colocation probability, mobility, and resources into one reviewable utility score.
  • With weights alpha=0.6, beta=0.3, gamma=0.1, the delivery vehicle scores 0.405 while the pedestrian scores 0.334.
  • A higher score justifies forwarding only when the rule and improvement threshold are explicit enough to audit.

Colocation Prediction (Kalman Filter):

CAR can use a Kalman filter or another time-series predictor to estimate future encounters from 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_factor

14.13.3 CAR vs Epidemic Routing

Example Scenario:

Before CAR vs Epidemic Routing, inspect Figure 14.1 to compare “Forwards only to higher utility” with “much lower overhead”. Their juxtaposition makes CAR versus epidemic routing trade-off for disconnected IoT networks visible.

Comparison of epidemic routing and context-aware routing showing epidemic routing with many message copies and high delivery, and CAR with selective forwarding, fewer copies, slightly lower delivery, and lower energy use
Figure 14.1: CAR versus epidemic routing trade-off for disconnected IoT networks

Read Figure 14.1 from “Forwards only to higher utility” to “much lower overhead”. Taken together, “Forwards only to higher utility” and “much lower overhead” express CAR versus epidemic routing trade-off for disconnected IoT networks. For CAR vs Epidemic Routing, the observed relationship between “Forwards only to higher utility” and “much lower overhead” is evidence that “Forwards only to higher utility” carries into the next decision.

Performance comparison in the example trace:

  • Delivery ratio: epidemic reaches about 95%; CAR reaches about 88%.
  • Copy overhead: epidemic creates about 15 copies per delivered message; CAR creates about 3.
  • Average latency: epidemic is faster in this trace, about 450 seconds versus 520 seconds.
  • Energy per delivery: epidemic is high because many nodes carry copies; CAR is medium because it forwards selectively.

Trade-off:

  • CAR: Slightly lower delivery ratio, much lower overhead
  • Best when: Resources constrained, predictable mobility

Quick Check: Context-Aware Routing

14.14 Continue to the Next Part

Carry this evidence into DTN Social Routing: Community and Forwarding Decisions, which begins with SocialCast: Social-Based DTN Routing.