Enhanced Random Walk With Choice: An Empirical Study
John Alexandris, Gregory Karagiorgos · International Journal on Applications of Graph Theory In wireless Ad Hoc Networks And sensor Networks · 2014
The Random Walk with d Choice ( ) RWC d is a recently proposed variation of the simple Random Walk that first selects a subset of d neighbor nodes and then decides to move to the node which minimizes the value of a certain parameter; this parameter captures the number of past visits of the walk to that node.In this paper, we propose the Enhanced Random Walk with d Choice algorithm ( , ) ERWC d h which first selects a subset of d neighbor nodes and then decides to move to the node which minimizes a value H defined at every node; this H value depends on a parameter h and captures information about past visits of the walk to that node and -with a certain weight -to its neighbors.Simulations of the Enhanced Random Walk with d Choice algorithm on various types of graphs indicate beneficial results with respect to Cover Time and Load Balancing.The graph types used are the Random Geometric Graph, Torus, Grid, Hypercube, Lollipop and Bernoulli.