Gerhard Haßlinger
Search Methods in
Dynamic Wireless Networks
–
q  Control of message overhead for flooding is difficult:
q     Unknown network coverage as a function of the distance d
q     Coverage may rise e.g. from 3% to 30% in one step d ® d + 1    
q
q  A random walk of predefined length L has fixed expense
q     Randoms walks can proceed in parallel, with forking or
q     can be enhanced by flooding with small d from some points
q     ̃ Many ways to combine random walks & flooding schemes
q          (see Gkantsidis et al., IEEE Infocom 2004 & ’05)
q     Network coverage is partial, but random walk searches are 
q     efficient e.g. for replicated data in P2P networks
q     Random network growth is also efficiently supported by r. walks
Network exploration by flooding & random walks