Comparison of efficient random walk strategies for wireless multi-hop networks

Wireless multi-hop networks have drawn great attention from research and business communities, since they suit well diverse application scenarios, such as environmental monitoring, military support in hostile environments and emergency applications. However, this challenging communication paradigm requires solutions able to fit specific requirements in terms of resource constrains, node mobility and quality of service. Random Walks (RWs) are probabilistic approaches to perform distributed operations, such as data search and retrieval. They are effective and have relatively small overhead compared to classic schemes, such as flooding. To further improve performance of RWs, hybrid solutions may be employed. Such strategies increase system performance at the cost of additional energy consumption. In this work, we propose two novel schemes that exploit local topological information in order to increase the hybrid RW protocols performance. Through simulations, we compare hybrid protocols with a traditional RW solution, studying their performance in static and mobile scenarios. An analysis of the trade-off between the number of node revisits and energy consumption allows to identify the more fitting protocols for different application scenarios in wireless multi-hop networks. Advantages and drawbacks of different RW strategies are highlighted, along with research challenges that need to be investigated in the future.