Gerhard
Haßlinger
Search
Methods in
Dynamic
Wireless Networks
Extensions
of the transient analysis for random walks
The
following cases are tractable by extended analysis:
- Several random
walks in parallel
® product formula for the probability that independent
trials miss a node
- Random walk
without step back (except for nodes of
degree 1)
® increased state space for analysis: network edges
instead of nodes,
but the run time complexity is
unchanged
- Random walk
followed by flooding on distance d after the last step
® extend absorbing state to the set of all neighbors up to
distance d
- Random walk
search for replicated data on n nodes
® use a
set of n absorbing states or
assume a binomial distributed hit
count based on single node search