Gerhard
Haßlinger
Search
Methods in
Dynamic
Wireless Networks
Transient
analysis of basic random walks
Performance
studies on random walks prefer simulation,
although
transient analysis offers a simple and scalable alternative
Bounds
e.g. based on second largest eigenvalue of the transition matrix prove convergence but often are not tight
Performance criteria: Number of steps required
- to reach a
target node
- or for
network coverage
with predefined probability (e.g. 99%)
Transient
analysis
- computes the probability distribution for
the random walks’ sojourn
node step by step
- starting from a node or an arbitrary
initial distribution