Evolving realistic topologies for wireless mesh network simulation with EvoTopo

The topology model is an important aspect of wireless mesh network simulation. To test a new protocol typically several different topologies are necessary to perform a statistically significant number of simulation runs. Simply using topologies of real-world networks directly is not sufficient because the number of topology data available is less than the number of topologies required for simulation. Therefore, artificially generated topologies are used. Unfortunately, many simulators use either a uniform node distribution or even just a simple grid topology which both differ significantly from real-world topologies. We first revisit the differences between uniform and grid topologies vs. real-world topologies using four different real-world networks to motivate the need for such a tool and then present EvoTopo , a new approach to generate more realistic topologies. EvoTopo uses a genetic algorithm to create the desired number of simulation topologies from the node positions of one real-world network. The generated topologies are evolved to be “similar” w.r.t. homogeneity of the node distribution, nearest neighbor distance, and node density. We evaluate our algorithm analyzing average overall node distance, the degree distribution of nodes, and the performance of a simple flooding algorithm and compare our algorithm to other approaches. The EvoTopo tool and the four sample topologies can be downloaded from our homepage; generated topologies are written to a simple text file which can be imported into a simulator of choice.