Mobility Models for Next Generation Wireless Networks

Chapter 4

Random Walk Models

Random walks are a large class of mobility models used in various scientific disciplines to study natural and human phenomena such as the path traced by a molecule as it travels through a liquid, the trajectory of a foraging animal, the financial status of a gambler, the time-varying price of a stock or share, and so on.

The term random walk was first introduced by the mathematician Karl Pearson in 1905 (Pearson 1905), and refers to a movement trajectory consisting of successive random steps. As in the taxonomy introduced in Chapter 3, random walks belong to the class of synthetic, entity-based mobility models. In particular, nodes in a network with random walk mobility move independently of each other. Thus, a mobile network with n nodes is modeled using n independent and stochastically equivalent random walks.

As mentioned above, several types of random walks have been defined and studied in various scientific disciplines starting at the end of the nineteenth century. An exhaustive coverage of the theory of random walks is well beyond the scope of this book, so the interested reader is referred to several existing books on random walks, such as Lawler and Limic (2010) and Rudnick and Gaspari (2010). In this chapter, we will present examples of random walks relevant to next generation wireless networks.

Random walks can be classified as either continuous or discrete depending on whether the spatial domain R is a continuous subregion or a discrete set ...