Information Technology Reference
In-Depth Information
K-connectivity. The probability for the K-connectivity of an Ad Hoc network is derived
using only local information such as node numbers, the radio transmission range and
node density. “Connectivity” in DTNs is more challenging owing to its intermittent
connection and absence of end-to-end paths between nodes. Some researchers inves-
tigated the “connectivity” issue by employing Evolving Graphs[14], Contact
Graphs[15], Multi-graphs [16] and Social Graphs[17]. Vincent Borrel et al.[18] pro-
posed a space-time path in order to form an evolving graph. They developed an algo-
rithm which can classify current DTNs based on information regarding node contacts.
They also analyzed the impact on different DTNs of mobility parameters using two
mobility models: Random Way Point Model[19] and Random Walk Model[20].
Contact Graph is proposed by Rugved Jathar et al. in 2010. The author developed a
probabilistic routing protocol based on Contact Graph. The probability of nodes ac-
quiring contact with each other is illustrated by Contact Graph in order to enhance
efficiency of routing. Multi-graph is introduced by Kevin Fall et al. in ACM
SIGCOMM in 2004. They try to model the routing process of DTNs as a multi-graph
with time t as a variable. Multi-graph brings time t as a variable in order to describe a
communication process. Social Graph is proposed by T Hossmann et al. in INFOCOM
2009. The authors argue that in most current challenged networks, connections of
nodes are not entirely random.
3
Environment and Definientia
We introduce a Spatial-Temporal Graph to describe DTN and its “store-carry-forward”
communication fashion. By bringing time dimension into consideration, a sequence of
graphs labeled by time is proposed. With this approach, a dynamic DTN can be de-
scribed as a sequence of static graphs changing over time.
et
()
v
and
v
at
Definition 1:
The Spatial-Temporal Link
between node
vv
,
n
i
j
t
is,
time
et
()= , , ;,,
vvt
i j nN
∈
;
vv
,
n
i
j
n
i
j
Definition 2:
The Spatial-Temporal Path
Path
is a sequence of Spatial-Temporal
Links within the Message Life Time T. The store-carry-forward technology passes a
message along a Spatial-Temporal Path in order to complete a communication process,
T
vv
,
i
j
[
]
T
vv
Path
=
e
();,,
t
i j n
∈
0,
N
,
t
≤
T
;
,
vv
,
n
n
i
j
i
j
Definition 3:
The Spatial-Temporal Reachability
Reachability G t T
denotes the
property of a Spatial-Temporal Graph being Spatial-Temporal reachable, which means a
Spatial-Temporal Path between any pair of nodes always exist in Message Life Time T,
(( ,)
T
vv
Reachability G t
(( ,)
T
→∀∀ ∃
i
j Path
∧ ≤
t
T
;
,
i
j
ij Ni
,
∈≠
,
j
;
