Fast method for generating random geometric graphs for wireless networks modelling

V. V. Shakhov ; A. N. Yurgenson ; O. D. Sokolova

Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 99-109.

Résumé

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.

Détail

Keywords: wireless network, network topology, random geometric graph generator.
Mots-clés : simulation

Bibliographie

[1] D. Wagner, R. Wattenhofer (eds.), Algorithms for Sensor and Ad Hoc Networks, LNCS, 4621, 2007, 416 pp.

[2] Penrose M. D., Random Geometric Graphs, Oxford Studies in Probability, Oxford University Press, 2003 | MR | Zbl

[3] Clark B. N., Colbourn C. J., Johnson D. S., “Unit disk graphs”, Discr. Math., 86:13 (1990), 165–177 | DOI | MR | Zbl

[4] Onat F. A., Stojmenovic I., Yanikomeroglu H., “Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks”, Pervasive and Mobile Computing, 4:5 (2008), 597–615 | DOI

[5] Guo Y., Duan L., Zhang R., “Optimal pricing and load sharing for energy saving with cooperative communications”, IEEE Trans. Wireless Communications, 15:2 (2016), 951–964 | DOI

[6] Paris S., Nita-Rotaru C., Martignon F., Capone A., “Cross-layer metrics for reliable routing in wireless mesh networks”, IEEE/ACM Trans. Networking, 21:3 (2013), 1003–1016 | DOI | MR

[7] Seo J., Kim M., Hur I., et al., “DRDT: Distributed and Reliable Data Transmission with cooperative nodes for lossy wireless sensor networks”, Sensors, 10:4 (2010), 2793–2811 | DOI

[8] Tsitsiashvili G. Sh., Osipova M. A., Losev A. S., “Asymptotics for connectivity probability of graph with low reliable arcs”, Prikladnaya Diskretnaya Matematika, 2013, no. 1, 93–98 (in Russian)

[9] Melent'ev V. A., “An analytical approach to the synthesis of regular graphs with preset values of the order, degree and girth”, Prikladnaya Diskretnaya Matematika, 2010, no. 2, 74–86 (in Russian)

[10] Camilo T., Silva J. S., Rodrigues A., Boavida F., “GENSEN: A topology generator for real wireless sensor networks deployment”, LNCS, 4761, 2007, 436–445

[11] Gavrilenko V. G., El'tsov A. Yu., Konyuchenko A. V. et al., “The development of sensor network simulator with a detailed simulation of the physical level in the ANYLOGIC environment”, Imitatsionnoe Modelirovanie. Teoriya i Praktika, Proc. IMMOD-2005, v. 1, SSTC Publ., St. Petersburg, 2005, 182–185 (in Russian)

[12] Zhou C., Krishnamachari B., “Localized topology generation mechanisms for wireless sensor networks”, IEEE GLOBECOM' 03 (San Francisco, CA, December 2003), 1269–1273 | Zbl

[13] Shakhov V. V., Sokolova O. D., Yurgenson A. N., “A fast method for network topology generating”, LNCS, 8715, 2014, 96–101