Fast method for generating random geometric graphs for wireless networks modelling

Due to the high complexity of modern networks as well as the stochastic nature of network processes, the simulation becomes the main tool for communication systems analysis. In simulation studies of wireless technologies (wireless sensor networks, ad hoc-networks, cognitive radio, Internet of Things etc.), the random geometric graph (RGG) is the most commonly used mathematical model of network topology. This graph is constructed by randomly placing $N$ vertices in some metric space (according to a specified probability distribution), where each pair of vertices is connected by an edge iff the distance between them is smaller than a predetermined value (radius). Network simulation technique typically uses the rectangular region and the uniform distribution for vertices coordinates. Thus, the research and development of efficient RGG generators is an important problem. The paper describes a method for the fast generation of pseudo-random geometric graphs with the prescribed properties: 1) the vertices are uniformly distributed in the network region; 2) the region is fully covered by circles of a given radius centered at the vertices of the graph; 3) the graph is connected. To increase the generator performance, we construct an auxiliary grid covering the region. To guarantee the full coverage and graph connectivity, every cell of the grid contains at least one vertex. The corresponding cell size depends on the given transmission radius in a wireless network. The core idea of the proposed algorithm is to apply the procedure of edges construction only for nodes in adjacent cells. It allows to avoid unnecessary calculations. In the first stage of the algorithm, one vertex is randomly placed in each cell. To define the vertex coordinates, one of the standard generators of pseudo-random values for uniform distribution is used here and below. In the second part of the algorithm, the remaining vertices are randomly distributed over the region. The edges construction procedure based on adjacent cells is applied as well. The algorithm can be easily adapted for non-squared region. Experiments show that the proposed method, when compared to the traditional algorithm, drastically reduces the generation time (up to 10 times). The proposed generator is better than the existing analogues both in performance and reality of generated topologies.