2020 № 1(46)

Contents

Bredikhin S.V., Lyapunov V.M., Shcherbakova N.,G. Dynamics of the citation network of scientific articles
Sokolova O. D., Materukhin A.V. Analytical review of modern information technologies for collection, processing and analysis of data applied for monitoring atmospheric pollution air
Tarkhanova O. Y., Shakhov V. V. On Performance Evaluation of Wireless Sensor Networks
Perepelkin V. A. LuNA System for Automatic Construction of Numerical Parallel Programs for Multicomputers

S. V. Bredikhin, V. M. Lyapunov, N. G. Shcherbakova

Institute of Computational Mathematics and Mathematical Geophysics SB RAS,630090, Novosibirsk, Russia

DYNAMICS OF THE CITATION NETWORK OF SCIENTIFIC ARTICLES

UDK 001.12+303.2

DOI: 10.24411/2073-0667-2020-10001

Many complex networks are scale-free, namely their degree distribution follows a power law for large k. The graphs corresponding to the citation networks (CN) of scientific articles are included in this set. The vertices of citation network correspond to scientific articles, and directed edges to citations. Almost each new article contains some number of references (citations) to previously published ones. The number of references to a cited vertex is its in-degree. The appearance of new connects between old vertices is impossible.

The question is how growing networks self-organize into a scale-free structure. Simon (1955) assumes that the principle of "having much gets more” has effect. The study of this mechanism as applied to CN was performed in Price (1976). D. Price called the strategy, in which success breeds success, a cumulative advantage. For CN, the citation strategy is formulated as follows: the speed with which articles receive new citations is proportional to the citations already received.

Thanks to a series of works, the beginning of which was laid by the work Barabási, Albert (1999), the mechanism of cumulative advantage was called the preferred attachment, hereafter PA-mechanism. In Barabasi-Albert model the probability Π that a new node connects to a node i depends on the degree k_iof i as

Πki= kijkj.

A generalization of the PA-mechanism was presented in Krapivisky, et al (2000) as

Πki= kiαjkjα.=Ctkiα,

C(t) is a normalization constant.

Dorogovtsev and Mendes (2000) proposed that in some real networks the probability Π also depends on an age of node i, decaying as (t – t_i)^-v, where t_i is a timestep a node i was added to the network, t – a timestep a new node is added, ν is a tunable parameter. So,

Πki, ti∝ kifti,

where f(t_i) is an aging function.

In real networks Π(0) ≠ 0, which means there is a nonzero probability that a new node attaches to a node i, such that k_i = 0. So Dorogovtsev , et al. (2000) presented the model of a directed network such that

Πkiin= kiin+k0j(kjin+a) ,

where kiin is the number of incoming links, k₀ is the initial attractiveness of the node i.

So the likelihood that a newly added node will join node i after a time t has elapsed after the addition of node i to the directed network may be proportional to the following characteristics:

Πkiin,t∝(kiin+ k0)fit.

The aim of this work is to study the dynamical properties of the citation network of scientific articles based on data provided by the bibliographic database RePEc. We find that the distribution of incoming links follows the power law with parameters γ = 2,89, x_min = 207. So we want to prove the preferential attachment hypothesis that in this case states that the rate Π(kⁱⁿ) with which a node with k incoming links acquires new links is a monotonically increasing function of kⁱⁿ, hereinafter we use the denotation k instead of kⁱⁿ. To investigate the attachment mechanisms separately from aging we use the method presented in Jeong, et al. (2003). To avoid the influence of C(t) and an aging effect we study the attachment kernel A_k within a relatively short window time ΔT. The functional form of A_kcan be determined by measuring how many citations an article with k citation collected during some previous period T₀ receives within period ΔT. We plotted the function of attachment rate using different previous periods and found the linear fit. The results of approximation with a linear functions show that A_k has a form k + k₀, where k₀can be considered as the initial attractiveness. It should be noted that we have different estimations of A_kdepending on T₀.

When investigating an aging process we ignore the preferential attachment and explore age characteristics of nodes with the same degree. We study two distributions, S(t) and D(t). S(t) is the distribution of ages of citation from citing article to cited articles. D(t) is the distribution of ages to a cited article from citing articles. The numerical calculations show that S(t) increases during 2-3 years and then decays exponentially during approximately 25 years (irrespective of the selected t₀), then decreases slower. So it can be assumed that the aging function f(t) = (exp αt), α < 0. The distribution D(t) shows the linear growth for 20 years and then the exponential decay.

Our experiment shows that the citation process can be described by the linear preferential attachment, but given the process of aging is consistent with the attachment kernel only for the first 20 years after publication. It should be noted that fluctuations in the distributions and the dependence on selected time windows are observed which may be due to incomplete data.

Key words: citation network, power law, preferential attachment, initial attractiveness, aging.

References

1. Lotka A. J. The frequency distribution of scientific productivity // J. of the Washington Academy of Science. 1926, V.16. P.675-682.

2. Simon H. A. On a class of skew distribution functions // Biometrika. 1955. V.42. P.425-440.

3. Price D. J. de Solla. Networks of Scientific Papers // Science. 1965. V.149. P.510-515.

4. Merton R. K. The Matthew Effect in Science // Science. 1968. V.159, iss.3810. P.56-63.

5. Cole J. R., Cole S. Social stratification in science. Chicago, IL:University of Chicago. 1973.

6. Price D. J. de Solla. A general theory of bibliometric and other cumulative advantage processes // J. of the American Society for Information Science. 1976. V.27(5-5). P.292-306.

7. Tsallis C., de Albuquerque M. P. Are citations of scientific papers a case of nonextensivity? // Eur. Phys. J. B. 2000. V.13, iss.4. P.777-780.

8. Redner S. How popular is your paper? An empirical study of the citation distribution // Eur. Phys. J. B. 1998. V.4, iss.2. P.131-134.

9. Peterson G. J., Presse S., Dill K. A. Nonunivessal power law scaling in the probability distribution of scientific citations // in Proc. Natl. Acad. Sci. USA. 2010. V.107, iss.37. P.16023-16027.

10.Barab'asi A.-L., Albert R. Emergence of scaling in random networks // Science. 1999. V.286. P.509-512.

11. RePEc. General principles. [Electron. Resource]. http://repec.org/.

12. Krapivisky P.L., Redner S., Leyvraz F. Connectivity of growing random networks // Phys. Rev. Lett. 2000. V.85. P.4629-4632.

13. Scherbakova N. G. Preferential attachment models // Problemi informatiki. 2019. N3. P.46-61 (in Russian).

14. Barab'asi A.-L., Albert R., Jeong H. Mean-field theory for scale-free random networks // Physica A. 1999. V.272. P.173-187.

15. Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Structure of growing network with preferential linking // Phys. Rev. Lett. 2000. V.85. P.4633-4636.

16. Barab'asi A. L., Jeong H., Neda Z., Ravasz E., Schubert A.,Vicsek T. Evolution of the social network of scientific collaborations // Physica A. 2002. V.311. P.590-614.

17. Jeong H., Neda Z., Barab'asi A. L. Measuring preferential attachment for evolving networks // EuroPhysics Letters. 2003. V.61. P.567-572.

18. Lehmann S., Lautrup B., Jackson A. D. Citation networks in high energy physics // Phys. Rev. E. 2003. V.68, 026113.

19. Redner S. Citation statistics from more than the century of physical review // arXiv:physics/0407137.

20. Wang M., Yu G., Yu D. Measuring the preferential attachment mechanism in citation networks // Physica A. 2008. V.387. P.4692-4698.

21. Dorogovtsev S. N., Mendes J. F. F. Evolution of reference networks with aging // Phys. Rev. E. 2000. V.62. P.1842-1845.

22. Zhu H., Wang X., Zhu J-Y. Effect of aging on network structure// Phys. Rev. E. 2003. V.68, 056121.

23. Hajra K.B., Sen P. Modelling aging characteristics in citation networks // Physica A. 2006. V.368. P.575-582.

24. Clauset A., Shalizi C. R., Newman M. E. J. Power-law distributions in empirical data // SIAM Review V.51. 2009. P.661-703.

25. igraph - The network analysis package [Electron. Resource]. https://igraph.org/.

26. Pollmann T. Forgetting and the ageing of scientific publications // Scientometrics. 2000. V.47, N1. P.43-54.

27. Lehmann S., Jackson A. D., Lautrup B. Life, death and preferential attachment// EuroPhysics Letters. 2005. V.69. P.298-303.

Bibliographic reference: Bredikhin S.V., Lyapunov V.M., Shcherbakova N.,G. Dynamics of the citation network of scientific articles //journal “Problems of informatics”. 2020, № 1. P. 5-20. DOI: 10.24411/2073-0667-2020-10001

article

O.,D. Sokolova, A.,V. Materukhin*

Institute of Computational Mathematics and Mathematical Geophysics SB RAS,630090, Novosibirsk, Russia

*Moscow State University of Geodesy and Cartography,105064, Moscow, Russia

ANALYTICAL REVIEW OF MODERN INFORMATION TECHNOLOGIES FOR COLLECTION, PROCESSING AND ANALYSIS OF DATA APPLIED FOR MONITORING ATMOSPHERIC POLLUTION AIR

UDK 528

DOI: 10.24411/2073-0667-2020-10002

The article is an analytical review of scientific publications on the topic of modern information technologies in the field of data collection, processing and analysis for monitoring air pollution in large cities. Modern large cities are the source of most emissions of harmful substances into the atmosphere. To monitor atmospheric pollution parameters, as a rule, either data obtained from few and fairly far from each other regular environmental monitoring stations are used, or data obtained as a result of expensive short-term field studies. This is not enough to obtain adequate information about the spatial distribution of pollutants or to identify sources of pollution. To monitor atmospheric pollution parameters with high spatial and temporal resolution are required.

Over the past two decades, progress has been made in the development of small-sized sensor devices with the added ability to determine their location, the so-called geosensors. The use of wireless geosensor networks for monitoring air quality is considered in many scientific publications. The aim of the review was to analyze modern scientific publications in this field of research. The problems of research are related to the tasks of managing of spatio-temporal data streams. The review presents articles that describe mathematical models and optimization algorithms for data collection processes, as well as their processing. Today, the scientific community has already reached a consensus about which information technologies are most preferable at this level-- data mining methods are the most promising tool for analyzing and predicting air pollution. The level of spatial and temporal granularity of data necessary for the application of these methods can be achieved using geosensor networks.

The main problems that arise during the collection and transmission of data in a wireless geosensor network are problems of ensuring energy efficiency, speed and accuracy of transmission. For the effective functioning of monitoring networks, it is necessary to develop adequate mathematical models and methods that will optimize the data collection process. The review analyzes various approaches to solving this problem (for example, the use of mobile sinks or clustering of many geosensors). The review includes publications in which it is proposed to improve monitoring through the use of mobile nodes. The possibility of using Vehicle ad-hoc Sensor Networks (VANET) for monitoring air quality has been offered quite often in recent years-- sensors can be installed on cars that move in the transport network of a city. Thanks to mobility, the sensor node can take measurements in different places, thereby reducing the requirements for a large number of sensor nodes for monitoring the territory.

The bottleneck of most research projects in this area is the lack of the possibility of large-scale deployment of the proposed solutions. Therefore, the review focuses on the use of simulation to verify the effectiveness of various technological solutions. Some systems for modeling data streams from geosensors (for example, the MobGeoSensSimulation system), which measure air quality parameters over a large urban area and send data to a processing center, are analyzed.

The analysis of scientific publications carried out in the article suggests that the main trend in research in the field of monitoring atmospheric air pollution is the development of technological solutions associated with the use of wireless geosensor networks, and the current trend is the transition from stationary to mobile geosensors. Such a transition will allow the use of data mining methods with greater efficiency. Various solutions described in the modern scientific literature and intended for application at various levels of the atmospheric monitoring system are analyzed: at the level of data collection, at the level of data processing and at the level of data analysis. Another identified research trend is the development and study of computer modeling systems for monitoring systems.

Key words: monitoring of air pollution, wireless geo-sensor networks.

References

1. Nittel S. A survey of geosensor networks: Advances in dynamic environmental monitoring // Sensors. 2009. N 9(7). P. 5664-5678.

2. Duckham Matt, Decentralized Spatial Computing. Foundations of Geosensor Networks // Springer. 2014.

3. Yakubajlik O. E., Gosteva A. A., Erunova M. G., Kadochnikov A. A., Matveev A. G., Pyataev A. S., Tokarev A. V. Razrabotka sredstv informacionnoj podderzhki nablyudenij za sostoyaniem okruzhayushchej prirodnoj sredy // Vestnik KemGU. 2012. T. 2. N 4(52). S. 136-141.

4. Materuhin A. V. Teoreticheskie osnovy i metodologiya obrabotki potokov prostranstvenno-vremennyh dannyh: dissertaciya dots doktora tekhnicheskih nauk: 25.00.35 / Materuhin Andrej Viktorovich; [Mesto zashchity: Mosk. gos. un-t geodezii i kartografii]. Moskva, 2018.

5. Materuhin A. V. Matematicheskaya model' processov obrabotki potokov prostranstvenno-vremennyh dannyh v geoinformacionnoj sisteme // Izvestiya vysshih uchebnyh zavedenij. Geodeziya i aerofotosgrqqemka. 2018. T. 62. N 2. S. 237-243.

6. Gheyas I. A., Smith L. S. A Neural Network Approach to Time Series Forecasting // Proceedings of the World Congress on Engineering, London, 2009. Vol. 2. P. 1292-1296.

7. Rahman, N. H. A.; Lee, M. H.; Suhartono; Latif, M. T. Artificial neural networks and fuzzy time series forecasting: An application to air quality // Qual. Quant. 2015. N 49. P. 2633-2647.

8. Andreeva E. S., Lazareva E. O., Lipovickaya I. N. Prognoz urovnya zagryazneniya atmosfernogo vozduha v Sankt-Peterburge s primeneniem algoritma prinyatiya reshenij // Vestnik Moskovskogo universiteta. Seriya 5: Geografiya. 2019. N 2. S. 55-60.

9. Dincer,N. G., Akkus, O. A new fuzzy time series model based on robust clustering for forecasting of air pollution // Ecol. Inform. 2018. N 43. P. 157-164.

10. Lu Bai, Jianzhou Wang, Xuejiao Ma, Haiyan Lu. Air Pollution Forecasts: An Overview // International Journal of Environmental Research and Public Health, 2018.

11. Mishra, D.; Goyal, P. NO2 forecasting models Agra // Atmos. Pollut. Res. 2015. N 6. P. 99-106.

12. Tsujitaa W., Yoshinoa A., Ishidab H., and Moriizumi T. Gas sensor network for air-pollution monitoring // Sensors Actuators B, Chem. 2005. Vol. 110. N 2. P. 304-311.

13. Savinyh V. P., Majorov A. A., Materuhin A. V. Postroenie prostranstvennoj modeli zagryazneniya vozduha na osnove ispol'zovaniya potokov dannyh ot setej geosensorov // Geodeziya i kartografiya. 2017. N 12. T. 78. S. 39-43.

14. Rayane El Sibai, Yousra Chabchoub, Raja Chiky, Jacques Demerjian, Kablan Barbar. Assessing and Improving Sensors Data Quality in Streaming Context // 9th International Conference, Computational Collective Intelligence ICCCI 2017, Nicosia, Cyprus, September 27-29, 2017, Proceedings, Part II, 2017, Vol. 10449. P. 590-599.

15. Rai A., Kumar P., Pilla F., Skouloudis A., Sabatino S., Ratti C., Yasar A., and Rickerby D. End-user perspective of low-cost sensors for outdoor air pollution monitoring // Sci. Total Environ. 2017. Vol. 607-608. P. 691-705.

16. Duckham Matt, Nussbaum Doron, Sack Jorg Rudiger, Santoro Nicola. Efficient, Decentralized Computation of the Topology of Spatial Regions // IEEE Transactions on Computers. 2011. Vol. 60. N 8. P. 1100-1113.

17. Shahov V. V., Yurgenson A. N., Sokolova O. D. Effektivnyj metod generacii sluchajnyh geometricheskih grafov dlya modelirovaniya besprovodnyh setej // PDM. 2016. N 4 (34). S. 99-108.

18. Bieringer P. E.; Young G. S.; Rodriguez L. M.; Annunzio, A. J.; Vandenberghe F., Haupt S. E. Paradigms and commonalities in atmospheric source term estimation methods // Atmospheric Environment. Elsevier BV. 2017. N 156. P. 102-112.

19. Issartel J.-P. Emergence of a tracer source from air concentration measurements, a new strategy for linear assimilation // Atmospheric Chemistry and Physics, Copernicus GmbH, 2005. N 5. P. 249-273.

20. Mamonov A. V. Tsai Y.-H. R. Point source identification in nonlinear advection-diffusion-reaction systems // Inverse Problems, IOP Publishing, 2013. N 29. 035009.

21. Penenko V. V.; Penenko, A. V.; Tsvetova E. A. Gochakov A. V. Methods for Studying the Sensitivity of Air Quality Models and Inverse Problems of Geophysical Hydrothermodynamics // Journal of Applied Mechanics and Technical Physics, Pleiades Publishing Ltd, 2019. N 60. P. 392-399.

22. Penenko A., Mukatova Z. S., Penenko V., Gochakov A., Antokhin P. Numerical study of the direct variational algorithm of data assimilation in urban conditions // Atmospheric and ocean optics. 2018. N 31. P. 456-462.

23. Sun C., Li V., Lam J., and Leslie I. Optimal Citizen-Centric Sensor Placement for Air Quality Monitoring: A Case Study of City of Cambridge, the United Kingdom // IEEE Access, 2019. Vol. 7.

24. Sokolova O. D., YUrgenson A. N. Zadacha optimal'nogo razmeshcheniya ustrojstv analiza informacionnyh potokov v setyah // Problemy informatiki. 2010. N 2. S. 33-42.

25. S"a"askilahtiKirsti,KangaskorteRiitta,LuimulaMika & Yli-Hemminki, Juha. Collecting and visualizing wireless geosensor data using mobile devices // ACM International Conference Proceeding Series. 2010. 10.1145/1823854.1823882.

26. Ilka A. R., Gilberto C., Renato A., Antnio M. V. M. Data-Aware Clustering for Geosensor Networks Data Collection // Anais XIII Simpsio Brasileiro de Sensoriamento Remoto, INPE, 2007. P. 6059-6066.

27. Shahov V. V., Migov D. A., Sokolova O. D. Besprovodnye sensornye seti, osnashchennye sredstvami polucheniya energii iz okruzhayushchej sredy // Problemy informatiki. 2014. N 4. S. 69-79.

28. Materuhin A. V., SHahov V. V., Sokolova O. D. Modeli processov sbora prostranstvenno-vremennyh dannyh s ispol'zovaniem mobil'nyh stokov // Geodeziya i kartografiya. 2018. T. 79. N 12. S. 22-28.

29. Boubrima A., Bechkit W., Rivano H. Optimal WSN deployment models for air pollution monitoring // IEEE Trans. Wireless Commun. 2017. Vol. 16. N 5. P. 2723-2735.

30. Kaivonen Sami, Ngai Edith. Real-time air pollution monitoring with sensors on city bus // Digital Communications and Networks. 2019.

31. You-Chiun Wang, Guan-Wei Chen. Efficient Data Gathering and Estimation for Metropolitan Air Quality Monitoring by Using Vehicular Sensor Networks // IEEE Transactions On Vehicular Technology. 2017. Vol. 66. N 8. P. 7234-7248.

32. Penza M., Suriano D., Villani M. G., Spinelle L., and Gerboles M. Towards air quality indices in smart cities by calibrated low-cost sensors applied to networks // in Proc. IEEE Conf. Sensors, 2014. P. 2012-2017.

33. Shakhov V., Sokolova O. Towards Air Pollution Detection with Internet of Vehicles // Proceedings of 15th International Asian School-Seminar Optimization Problems of Complex Systems. OPCS-2019. P. 183-187.

34. Murty, R. N.; Mainland, G.; Rose, I.; Chowdhury, A. R.; Gosain, A.; Bers, J.; Welsh, M. CitySense: An Urban-Scale Wireless Sensor Network and Testbed // In Proceedings of the 2008 IEEE Conference on Technologies for Homeland Security, Waltham, MA, USA, 12-13 May 2008. P. 583-588.

35. Shu-Chiung Hua, You-Chiun Wang, Chiuan-Yu Huanga, Yu-Chee Tsenga. Measuring air quality in city areas by vehicular wireless sensor networks // The Journal of Systems and Software. 2011. N 84. P. 205-212.

36. Materukhin A. V., Gvozdev O. G., Maiorov A. A. and Sokolova O. D. Simulation of Spatio-Temporal Data Streams from Geosensors Located on Mobile Objects // 15th International Asian School-Seminar Optimization Problems of Complex Systems (OPCS), Novosibirsk, Russia, 2019. P. 179-182. DOI: 10.1109/OPCS.2019.8880188.

Bibliographic reference: Sokolova O.,D., Materukhin A.,V. Analytical review of modern information technologies for collection, processing and analysis of data applied for monitoring atmospheric pollution air //journal “Problems of informatics”. 2020, № 1. P. 21-34. DOI: 10.24411/2073-0667-2020-10002

article

O.,Y. Tarkhanova, V.,V. Shakhov

Institute of Cytology and Genetics SB RAS,630090, Novosibirsk, Russia

* Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk State Technical University

ON PERFORMANCE EVALUATION OF WIRELESS SENSOR NETWORKS RENEWCOMMAND

UDK 004.942

DOI: 10.24411/2073-0667-2020-10003

This work was supported by the ICM&MG base project No 0315-2016-0006

Nowadays, Internet of Things (IoT) has received increased attention in many countries. IoT and Big Data technologies have a tremendous impact on all fields of human life. In the Russian Federation, a roadmap for the IoT development is presented by the Ministry of Industry and Trade. Issues of development and implementation of IoT technologies are in the focus of attention of senior government authorities. According to Cisco Systems, this year 50 billion devices will be connected to the Internet. McKinsey (an international consulting company specializing in strategic management advice) estimates the economic impact of IoT development at USD 11 trillion by 2025. Note that there are several standardization projects and initiatives in sensor networks that can ultimately converge with the Internet of things. For example, this concerns proposals developed as part of the projects of the 7th EU Framework Programme for the development of scientific research and technology (IoT-A). Other appropriate projects include COBIS, SENSEI, SARIF. The international non-profit organization Open Geospatial Consortium has developed and supported a set of standards for requesting, transmitting and processing sensor data via the Web. To standardize the inclusion of sensors in the IoT architecture, a number of initiatives have been proposed, for example, IEEE 1451, ISO / ICE 24753. Great progress in the field of micro-electro-mechanical technologies has enabled the development of inexpensive sensor nodes that communicate wirelessly. A wireless sensor network is a self-organizing group of spatially distributed sensors for monitoring environmental conditions and delivering the collected data in a decision center. Wireless sensor networks (WSNs) can be used in a wide range of applications, such as precision agriculture, air pollution monitoring, smart home etc. However, a sensor has to be compact and inexpensive. This is a stringent demand of market. A consequence of the low cost of the sensors is a significant limitation of their resources (battery capacity, computing capabilities, memory etc.). This restriction significantly affects the performance and reliability of both individual sensors and the network as a whole, which contradicts the requirements for technologies used in critical areas of human life. Thus, efficient tools for assessing the effectiveness of WSNs are required. In this paper we partially fill the mentioned gap.

We develop a theoretical approach for modeling and analyzing DoB attacks. The proposed methods are based on continuous time Markov chains. The theory of Markov process is generally used when the various quality metrics of WSNs are calculated. In previous papers the specifics of the network topology are often not taken into account. On the other hand, in a number of studies, focus has been placed on optimizing the network topology, while the characteristics of its elements are assumed to be given (e.g. the probabilities of nodes availability and their dynamic). An existent approach combining the accounting of the network topology, the details of the operation of its nodes, the quality of the channels is described as a general idea. Here, we apply this one for a specific application. Also, we investigate a situation when the optimal network topology does not exist in the general case. The best topology is determined by the parameters of the environment and duty, and also depends on time. The corresponding example has been provided. A method for WSNs performance analysis based on temporary colored Petri nets has been proposed. To verify the approach we use a typical LoRaWAN topology, for example the similar topology has been used in digital farming, Edge computing applications, etc. The results of performance analysis have been visualized and presented.

Key words: Wireless Sensor Networks, Performance Analysis, Markov chain, Petri Nets.

References

1. Uckelmann D., Harrison M., Michahelles F. Architecting the Internet of Thing. Springer: Berlin/Heidelberg, Germany, 2011. P. 10-11.

2. Cho J. et al. SARIF: A Novel Framework for Integrating Wireless Sensor and RFID Networks. Dec. 2007 // IEEE Wireless Commun. V. 14. N 6. P. 50-56.

3. Tarhanova O. Y. Application of wireless sensor networks in precision agriculture. Problems of Informatics, No 4, 2017, P. 16-46. (in Russian)

4. Romer K. and Mattern F. The design space of wireless sensor networks // IEEE Wireless Commun. Dec. 2004. V. 11. N 6. P. 54-61.

5. Shakhov Vladimir. Performance Evaluation of MAC Protocols in Energy Harvesting Wireless Sensor Networks. Lecture Notes in Computer Science // Springer. 2016. V. 9787. P. 344-352.

6. Kurs A., Karalis A., Moffatt R., Joannopoulos J. D., Fisher P. and Soljacic M. Wireless power transfer via strongly coupled magnetic resonances // Science. 2007. V. 317. N 5834. P. 83-86.

7. Yang, S. Wireless Sensor Networks: Principles, Design and Applications // Springer-Verlag London. 2014. ISBN 978-1-4471-5505-8.

8. Karl, H. & Willig, A. Protocols and Architectures for Wireless Sensor Networks. John Wiley & Sons. 2007.

9. Borges L. M., Velez F. J., Lebres A. S. Survey on the characterization and classification of wireless sensor networks applications // IEEE Commun. Surv. Tuts., Nov. 2014. V. 16. N 4. P. 1860-1890.

10. Ding Z. etc. Impact of Optimal Hop Distance on the Network Lifetime for Wireless Sensor Networks With QoS Requirements // IEEE Communications Letters. 2019. Vol. 23. N 3.

11. Xiaobo Tan, Hai Zhao, Guangjie Han, Wenbo Zhang, Teng Zhu QSDN-WISE: A New QoS-Based Routing Protocol for Software-Defined Wireless Sensor Networks // Access IEEE. 2019. V. 7. P. 61070-61082.

12. Atia G. K., Veeravalli V. V., and Fuemmeler J. A. Sensor scheduling for energy-efficient target tracking in sensor networks // IEEE Trans. Signal Process., Oct. 2011. V. 59. N 10. P. 4923-4937.

13. Yeow W.-L., Tham C.-K., and Wong W.-C. Energy efficient multiple target tracking in wireless sensor networks // IEEE Trans. Veh. Technol., Mar. 2007. V. 56. N 2. P. 918-928.

14. Pandana C. and Liu K. R. Near-optimal reinforcement learning framework for energy-aware sensor communications // IEEE J. Sel. Areas Commun., Apr. 2005. V. 23. N 4. P. 788-797.

15. Shakhov Vladimir, Koo Insoo. Depletion-of-Battery Attack: Specificity, Modelling and Analysis // Sensors, June 2018. V. 18. N 6.

16. Chau, C.; Qin, F.; Sayed, S.; Wahab, M.; Yang, Y. Harnessing battery recovery effect in wireless sensor networks: experiments and analysis // IEEE J. Sel. Areas Commun. 2010. N 28. P. 1222-1232.

17. Bouabdallah, F.; Bouabdallah, N.; Boutaba, R. On balancing energy consumption in wireless sensor networks // IEEE Trans. Veh. Technol. 2009. N 58. P. 2909-2924.

18. Meng, T.; Li, X.; Zhang, S.; Zhao, Y. A Hybrid Secure Scheme for Wireless Sensor Networks against Timing Attacks Using Continuous-Time Markov Chain and Queueing Model // Sensors. 2016. N 16. P. 1606.

19. Alsheikh M. A. etc. Markov decision processes with applications in wireless sensor networks: A survey // IEEE Commun. Surveys Tuts. 2015. V. 17. N 3. P. 1239-1267, 3rd Quart.

20. Shakhov Vladimir V. A Graph-based Method for Performance Analysis of Energy Harvesting Wireless Sensor Networks Reliability // Lecture Notes in Electrical Engineering, Springer, 2016. V. 391. P. 127-132.

21. Kamgueu P. O., Nataf E., Ndie T. D. Survey on RPL enhancements: A focus on topology, security and mobility // Computer Communications. 2018. V. 120. P. 10-21.

22. DATA COLLECTION NETWORK FOR AGRICULTURE AND OTHER APPLICATIONS, US 2014/0024313 A1.

23. Shakhov V. V., Migov D. A. Reliability of Ad Hoc Networks with Imperfect Nodes // Springer LNCS, 2014. V. 8715. P. 49-58.

24. Page Lavon B., Perry Jo Ellen. Reliability of Directed Networks using: the Factoring Theorem // IEEE Transactions on Reliability, 1989 Dec. V. 38, N 5.

25. Migov D. Parallel Methods for Network Reliability Calculation and Cumulative Updating of Network Reliability Bounds // Proc. of the IEEE 2nd Russian-Pacic Conference on Computer Technology and Applications. 2015. P. 1-5.

26. Yu Z. et al. Trustworthiness Modeling and Analysis of Cyber-physical Manufacturing Systems // IEEE Access, 2017. V. 5.

27. Peterson James L. Petri net theory and the modeling of systems. MIR Publishers, Moscow. 1984. P. 264 (Russian edition).

28. Jensen Kurt, Kristensen Lars M. Colored Petri Nets. Modelling and Validation of Concurrent Systems / Springer-Verlag Berlin Heidelberg 2009.

29. [Electron. res.]: urlhttps://zigbeealliance.org/.

30. Tung H. Y. et al. The generic design of a high-traffic advanced metering infrastructure using ZigBee // IEEE Trans. Ind. Informat., Feb. 2014. V. 10. N 1. P. 836-844.

Bibliographic reference: Tarkhanova O.,Y., Shakhov V.,V. On Performance Evaluation of Wireless Sensor Networks //journal “Problems of informatics”. 2020, № 1. P. 35-65. DOI: 10.24411/2073-0667-2020-10003

article

V.,A. Perepelkin

Institute of Computational Mathematics and Mathematical Geophysics SB RAS,630090, Novosibirsk, Russia

LUNA SYSTEM FOR AUTOMATIC CONSTRUCTION OFNUMERICAL PARALLEL PROGRAMS FOR MULTICOMPUTERS

UDK 004.4'242

DOI: 10.24411/2073-0667-2020-10004

Usage of supercomputers for numerical simulations implies the complexity of distributed parallel programs development. Non-functional requirements for such programs include efficiency, memory and network bandwidth economy, tuning to available resources, fault tolerance and check pointing support, dynamic workload balancing, etc. To satisfy these requirements one has to concern peculiarities of application algorithm, hardware configuration and data. The development requires skills and knowledge supercomputer users are unlikely to have. To reduce the complexity of parallel programs development, debugging and modification diverse systems and tools of programs construction automation exist and evolve. Such tools accept a high level description of an application algorithm, as well as hardware configuration description, to produce and execute a parallel program, which implements the algorithm and fits into the non-functional requirements. Thus some of the programmer's burden is eliminated. Also such systems and tools are necessary to implement an active knowledge technology, where application algorithm is synthesized automatically based on application problem specification and has then to be automatically executed.

Automatic parallel programs construction system has to employ a high-level description of an application algorithm. The algorithm representation should be independent from hardware configuration and allow tuning of algorithm execution to given hardware and data. The representation should comprise independently computable parts which system should be able to dynamically map to given resources.

According to such demands the fragmented programming technology (FPT) is being developed in ICMMG SB RAS, as well as LuNA system for automatic numerical parallel programs construction (LuNA stands for Language for Numerical Algorithms). In the FPT computations are represented as the fragmented algorithm (FA) -- a countable set of computational tasks called computational fragments (CFs). A CF is defined by two finite sets of input and output arguments -- immutable data objects called data fragments (DFs) -- and an operation on the DFs, which computes values of output DFs from values of input DFs. Execution of FA is the execution of all the CFs once their input DFs are computed. Operations are side-effect-free sequential subroutines, thus a CF can be executed on any computing node dynamically, provided its input DFs' values are transferred to the node. The job of the programming system is to dynamically map DFs and CFs to computing nodes, provide input DFs transfer to CFs and execute CFs to produce new DFs. During FA execution the system redistributes CFs and DFs in order to balance workload, employs replication to provide fault tolerance, saves DFs values for check pointing or performs other jobs to provide necessary non-functional properties of the program execution.

In order to improve non-functional properties of FA execution supplementary information called recommendations can be provided by the user. Recommendations are means to overcome the fundamental difficulty of efficient execution of an application algorithm, represented in a high-level language, such as LuNA. Using recommendations the user can explicitly declare properties of the algorithm, which are hard to obtain automatically, but can significantly affect execution (e.g. estimated operations execution time). Also the user can employ recommendations to express his insight on how the computations should be performed in order to achieve high efficiency (instead of programming it in a low-level language, such as C+MPI). The system will follow the recommendations in cases, where good efficiency is hard to achieve automatically.

An experiment of automatic CFs mapping to resources using profiling is concerned. An application (matrices multiplication test) was run multiple times in the profiling mode. After each run the CFs mapping to computing nodes was adjusted to avoid load imbalances, which occurred in the previous execution. After few executions the execution time of the program decreased to the time of an efficient hand-made implementation of the same algorithm. This shows the possibility to automatically tune a FA execution to hardware configuration.

Another experiment shows automatic provision of dynamic load balancing on the example application of self-gravitating dust cloud simulation using Particle-in-Cell method. The application is an example of a problem, where workload distribution cannot be predicted statically and depends on input data. Necessary dynamic workload balancing was provided by LuNA system automatically based on the Rope of Beads algorithm, which preserves distributed data structure when balancing.

A number of other models and real-life applications were developed using the LuNA system. The efficiency of the constructed program is generally lower, than the one of hand-coded implementation, but reduction of labourness of program development, debugging and modification is often worth it. In future it is planned to implement other system algorithms and heuristics to improve the quality of automatically constructed programs, and to use LuNA system as a basis for active knowledge system construction.

Key words: Fragmented programming technology, automatic parallel programs construction, high performance computing, LuNA system.

References

1. Victor Malyshkin. Active Knowledge, LuNA and Literacy for Oncoming Centuries // 2015. LNCS, Vol. 9465. P. 292-303.

2. Ken Kennedy, Charles Koelbel, and Hans Zima. The rise and fall of High Performance Fortran: an historical object lesson. In Proceedings of the third ACM SIGPLAN conference on History of programming languages (HOPL III). Association for Computing Machinery, New York, NY, USA, 2007. 7-1-7-22. DOI: 10.1145/1238844.1238851.

3. Inkrementalnoye rasparallelivanie dlya klasterov v sisteme SAPFOR / V. A. Bakhtin, O. F. Zhukova, N. A. Kataev et al. // Trudy Vseross. nauchn. konf. Nauchnyi servis v seti INTERNET. 2017.

4. Apache Hadoop. [Electron. Res.]: https://hadoop.apache.org/.

5. Wu W., Bouteiller A., Bosilca G., Faverge M., Dongarra J. Hierarchical DAG Scheduling for Hybrid Distributed Systems // 29th IEEE International Parallel & Distributed Processing Symposium, 2014.

6. Kale, Laxmikant V. and Bhatele, Abhinav. Parallel Science and Engineering Applications: The Charm++ Approach. Taylor & Francis Group, CRC Press. 2013. ISBN: 9781466504127.

7. Abramov S. M., Kuznetsov A. A., Roganov V. A. Krossplatformennaya versiya T-sistemy s otkrytoy arkhitekturoy // Vychislitelnye metody i programmirovaniye. 2007. Vol. 8. N 1. Razdel 2. P. 175-180.

8. Datta, Kaushik & Bonachea, Dan & Yelick, Katherine. Titanium Performance and Potential: An NPB Experimental Study. 4339. 2005. P. 200-214. DOI: 10.1007/978-3-540-69330-7_14.

9. Tarek El-Ghazawi and Lauren Smith. UPC: unified parallel C // In Proceedings of the 2006 ACM/IEEE conference on Supercomputing (SC '06). Association for Computing Machinery, New York, NY, USA, 27-es. 2006. DOI: https://doi.org/10.1145/1188455.1188483

10. Kemal Ebcioglu, Vijay Saraswat, Vivek Sarkar. X10: Programming for hierarchical parallelism and non-uniform data access. International Workshop on Language Runtimes, OOPSLA 2004.

11. Andrianov A. N., Efimkin K. N., Levashov V. Y., Shishkova I. N. The Norma language application to solution of strong nonequilibrium transfer process problem with condensation of mixtures on the multiprocessor system // Computational Science-- ICCS 2001, Lecture Notes in Computer Science. May, 2001. V. 2073, P. 502-510.

12. Treichler, Sean & Bauer, Michael & Aiken, Alex. Realm: An event-based low-level runtime for distributed memory architectures // Parallel Architectures and Compilation Techniques-- Conference Proceedings, PACT. 2014. DOI: 10.1145/2628071.2628084.

13. Malyshkin V. E., Perepelkin V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // In: Malyshkin V. (eds) Parallel Computing Technologies // PaCT 2011. Lecture Notes in Computer Science. 2011. V. 6873. Springer, Berlin, Heidelberg.

14. Malyshkin. V., Perepelkin. V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // Journal of Supercomputing, S. I.: Parallel Computing Technologies. Springer, 2017. P. 1-7. DOI: 10.1007/s11227-016-1781-0.

15. Perepelkin V. A. Optimizatsiya ispolneniya fragmentirovannykh programm na osnove profilirovaniya // Shestaya Sibirskaya konverentsiya po parallelnym i vysokoproizvoditelnym vychisleniyam: Programma i tezisy dokladov. Tomsk: Izd-vo Tom. un-ta, 2011. P. 117-122.

16. Malyshkin. V., Perepelkin. V. The PIC Implementation in LuNA System of Fragmented Programming // The Journal of Supercomputing, Special Issue on Parallel Computing Technologies. Springer, 2014. P. 89-97. DOI: 10.1007/s11227-014-1216-8.

17. Akhmed-Zaki, D., Lebedev, D., Perepelkin, V. Implementation of a three dimensional three-phase fluid flow (glqqoil-water-gasgrqq) numerical model in LuNA fragmented programming system // Journal of Supercomputing. Springer, 2017. N 73(2). P. 624-630. DOI: 10.1007/s11227-016-1780-1.

18. Daribayev B., Perepelkin V., Lebedev D., Akhmed-Zaki D. Implementation of the Two-Dimensional Elliptic Equation Model in LuNA Fragmented Programming System // 2018 IEEE 12th International Conference on Application of Information and Communication Technologies (AICT). 2018. P. 1-4.

19. Kireev S. E., Perepelkin V. A. Issledovaniye proizvoditelnosti realizatsii metoda IADE v sisteme fragmentirovannogo programmirovaniya LuNA // Parallelnyye vychislitelnye tekhnologii (PaVT'2016): trydy mezhdunarodnoy nauchnoy konferentsii (28 March-- 1 April 2016, Arkhangelsk). Chelyabinsk: Izdatelskiy tsentr YuUrGU, 2016, p. 780.

20. Nikolay B., Perepelkin. V. Automated GPU Support in LuNA Fragmented Programming System // Parallel Computing Technologies. PaCT 2017. Lecture Notes in Computer Science. Springer, Cham, 2017. V. 10421. P. 272-277. DOI: 10.1007/978-3-319-62932-2_26.

Bibliographic reference: Perepelkin V.,A. LuNA System for Automatic Construction of Numerical Parallel Programs for Multicomputers //journal “Problems of informatics”. 2020, № 1. P. 66-74. DOI: 10.24411/2073-0667-2020-10004

article

Main menu

2020 № 1(46)

Languages

Main menu

You are here

2020 № 1(46)

Languages