TEMPLE UNIVERSITY
TOUR: Time-sensitive Opportunistic Utilitybased Routing in Delay Tolerant Networks Mingjun Xiao a,b, Jie Wub, Cong Liu c, and Liusheng Huang a a
University of Science and Technology of China, China b Temple University, USA c Sun Yat-sen University , China
Outline • Introduction on utility-based routing • Motivation • Problem • Solution • Simulation • Conclusion
Introduction: utility-based routing • Concept : Utility-based routing [Jiewu 08, 12] – Utility is a composite metric Utility (u) = Benefit (b) – Cost (c) – Benefit is a reward for a routing – Cost is the total transmission cost for the routing – Benefit and cost are uniformed as the same unit – Objective is to maximize the utility of a routing
Introduction: utility-based routing • Motivation of Utility-based Routing – Valuable message: route (more reliable, costs more) – Regular message: route (less reliable, costs less) message sender
route 1 route 2
receiver
route k Benefit is the successful delivery reward
Motivation Utility-based routing
Delay Tolerant Network (DTN)
delivery delay is an important factor for the routing design Time-sensitive utility-based routing
Time-sensitive utility model • Benefit Benefit: a linearly decreasing reward over time ⎧b − t ⋅ δ , t ≤ b δ b(t ) = ⎨ t >b δ ⎩ 0,
• Utility Utility: u (t ) = b(t ) − c
u us=b δ cs
{
ui
b( t)
u(t) s
i
ud t d
Problem • Time-sensitive utility-based routing in DTN – DTN: V={1, 2, …}, λi, j , ci (i, j ∈V) – source s, destination d, initial benefit b, benefit decay coefficient δ (single copy copy)) – Objective: maximizeE[ud] or minimizeDs(us)=b-E[ud] for generality, minimize Di(u) u =b s
δ cs
{
ui
u
Di(u) = E[ u -ud]
ud t
s
i
d
Problem • A simple example – DTN: V={1, 2, 3, d}, λi, j , ci (i, j ∈V) – source s=3, destination d, initial benefit b=20, benefit decay coefficient δ=2 – Objective: minimize D3(u3) λ 3
.8 0 = 1
3,
c 3= 4 λ3
, 2=
0 .2
c1= 8 1
λ 1,
d=
0 .8
λ 3 , d = 0. 0 1 2
c 2= 4
d λ
0. = d 2,
2
Problem • The key problem when a node i meets another node, –when whether the node i should forward messages to this encountered node, or ignore this forwarding opportunity, so that the node i can achieve the minimum Di(u)
Solution • Basic idea: Time-Sensitive Opportunistic Forwarding – Dynamically select relays: forwarding set Ri (u) – Opportunistic forwarding scheme: only forward messages to nodes in forwarding sets; ignore the other nodes outside of the set
i
d
R i ( u)
Solution • Basic idea: Time-Sensitive Opportunistic Forwarding – Forwarding set Ri (u) is time-sensitive: vary with time, i.e., remaining utility u λ 3
.8 0 = 3,1
c1=8 1
λ1,
R*3 (u) d=0
c3=4 λ3,d=0.0 1
λ3
,2=0
.2
2
c2=4
.8 { d, 1 , 2 }
d λ2,
.2 0 = d
{d , 2 } {d}
φ 4
u 8
12
14
16
18 20 tim e
Solution • Determine optimal forwarding set – Computation formula Ri* (μ) ∗ i
R (u ) = arg min Di (u ) R (u ) R ( u )⊆ N i µ
Di (u = µ ) |R ( u ) = ∫
∑ρ
i, j
(u )( µ − u j + D j (u j ))du + p f ( µ ) µ
0 j∈R ( u )
i
j
μ-uj
d
D j(uj)
successful forwarding
failed forwarding
Solution • Determine optimal forwarding set For a single node i : Ri* (μ) – Assumption Assumption:: Dj (μ-ci)=Dj (uj) are known …
