Gerhard Haßlinger
Search Methods in
Dynamic Wireless Networks
Dm: Distance to the destination after m random walk steps (with changes)
Dm  has a binomial distribution:
 
 for unrestricted range of distances in both directions
 with mean E(Dm) = D – m (q –p)/(q +p); variance s2(Dm) = mpq/(q +p)
 if  m(q –p)/(q +p) > D ̃ E(Dm) < 0 ̃ destination is reached with > 50%
 
Start
 
p
q
D:0
2
3
1
-1
-3
-2
S:D
p
q
Destination
Convergence bound for biased random walks
D:0
S:D
D-1
D-1
D+1
D+1
Example:
2-dim.
Grid