2020 № 4(49)

CONTENTS

  1. Skopin I. N. Local and global time in modeling of evolving systems
  2. Shakhov V. V., Sokolova 0. D. Analysis of networks with non-stationary topology. Survey
  3. Vishnevsky V. M., Semenova О. V. Review on models of polling systems and their applications to telecommunication networks
  4. Krylova A. I., Lapteva N. A. Modeling the streamflow in the Lena River basin on the basis of a hvdrologieally correct digital elevation model

Igor N. Skopin

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

LOCAL AND GLOBAL TIME IN MODELING OF EVOLVING SYSTEMS

DOI: 10.24411/2073-0667-2020-10013

The study of evolving systems includes the reflection in the models of changes in the system during its existence. The processes that ensure development begin, execute and end within a certain time frame, which in itself indicates the need for modeling of the time. Not only hours, minutes, etc. arc important here, although in some simple eases this attachment of behavior to the time scale may be sufficient, as well as properties such as mutual influence and synchronization of element behavior, development under the influence of events, that arc external in relation to the system and its elements produced. In other words, at the model level arc significant the interactions of the elements, but not the moments of absolute time when these interactions occur.

One can talk about the local time of an individual element, defining it as a sequence of events in which the element operates during the system evolving. But this is not global time common to all elements. Such a time would become an additional entity of the model without any advantages for synchronizing interactions.

The problem of adequate time reflection in models is very important for any approach to the study of processes and phenomena. But when evolving systems arc studied, it takes on special significance. The common task in such eases is the reconstruction or imitation of the behavior of the system as the interaction of its elements in time. As a result, the concept of model time is required, which would reflect reality in concert with interactions.

The article contains definitions of notions related to local for the system elements times, proof of the correctness of constructing models based on the consideration of global time as a partial order relationship on the set of events that occur when the system model is executed. An aeeuratc definition of evolving systems is required to rigorous present the proposed approach to modeling. We give such a definition and prove its correctness, using the notion of the system element life cycle.

From the above it follows that our approach negatively refers to the use of global time as one of the basic notion of modeling. Nevertheless, it docs not limit the model developer and allows him to operate with global time, which becomes a concept subordinate to event-drived control and local time of system elements.

The proposed formal definition of concepts related to time cannot be considered as the only possible correct representation of time in models. This approach is adequate to modeling in tasks for which the activity of elements is essential. As important alternative approaches, we consider modeling based on quasi-parallel systems implemented, for example, in the programming languages Simula and Simula 67, as well as a number of other special solutions.

One of the main goals of this paper is the construction and justification of proposed concept the main property of which is the priority of local time of elements before global time. The structure of the

presentation obeys this goal. The next section 2 gives information on various types of representations of time used in modeling, in particular, in the study of evolving systems. Section 3 clarifies the notions that characterize a system as evolving. It also describes the event-driven control of interactions of elements that uses as a method for determining the time in models of evolving systems. The following sections 4-7 are devoted to formalizing proposed in the article concept. Section 4 justifies the use of local time of a system’s elements in the event-based organization of interactions in a model system. Section 5 introduces the concept of an evolving element and the associated with this notion of states and transitions from one state to another. Section 6 is devoted to proving the correctness of using partial ordering of events as the basis for determining the local time of an element. Section 7 completes the proof of the formal correctness of the proposed concept and shows how global time can be determined using event-driven control. The Conclusion presents information on other approaches to modeling time, conceptually close to the concept being developed. This part of the article also provides motivation for what tools are needed to support the proposed concept in modeling.

The research presented in this work showed that overcoming the difficult problems of globalization of time based on world clocks is achievable if global time is considered as an entity secondary to local times of elements of the system. On this basis, design patterns can be used that implement fairly general methods for constructing models of evolutionary development. The identification of situations in which such patterns are required, we consider as a promising work.

Key words: local and global time; partial order relation on a set of events; events, reaction of elements to events; event protocols.

 
Bibliographic reference:  Skopin I. N. Local and global time in modeling of evolving systems//journal “Problems of informatics”. 2020, № 4. P.5-26. DOI: 10.24411/2073-0667-2020-10013
 

V.V. Shakhov*’**, 0. D. Sokolova*

*Institute of Computational Mathematics and Mathematical Geophysics, 630090, Novosibirsk, Russia
**Novosibirsk State Technical University 630073, Novosibirsk, Russia

ANALYSIS OF NETWORKS WITH NON-STATION ARY TOPOLOGY.SURVEY

DOI: 10.24411/2073-0667-2020-10014

The study was supported by grant of the RFBR № 19-01-00562-a.

In recent years, the great technological leap comes with non-stationary network topology. The examples include systems with mobile subscribers, networks with nodes on vehicles (VANET, Vehicle ad-hoc network), unmanned aerial vehicles, etc. In addition, the topology of fixed networks can also change due to intentional or unintentional destructive effects, features network protocols (multiple relays, transmission range and route are highly variable., etc.). The methods used to solve problems of classical networks (for example, centralized routing with a hierarchy of pro-assigned routers) turn out to be ineffective under the new conditions; adaptation of models and approaches is required.

Both foreign and Russian companies are engaged in research on the optimization of data transmission in non-stationary networks, international projects are being carried out. Among the urgent tasks are the following: the impact of node mobility on network performance, localization of mobile nodes, determination of the effective transmission coverage area, energy efficiency, etc. One of these tasks is to improve the quality of communication between transport means and the Internet. In VANET networks, the role of stations transmitting information from moving objects to the network is performed by roadside equipment (RSU, road side unit). But their disadvantage is that they are stationary, after being installed on the side of the road, they cannot be moved. Therefore, as the traffic flow changes, there will be either a shortage or an excess of such facilities. Compared to stationary RSUs, unmanned aerial vehicles can move depending on changes in traffic flow. So, there is a problem of increasing the network coverage for VANET using unmanned aerial vehicles that act as base stations. Many publications are devoted to the description of technologies for localization of wireless mobile sensors, for example, based on the Monte-Carlo Location algorithm.

To solve some important applied problems, there is no need to analyze the behavior of the entire network with mobile nodes; it is enough to consider the behavior of the system in some neighborhood of interest to the researcher. For example, it can be the coverage area of the transceiver, which is equipped with a roadside infrastructure device, road segments where deliberate interference occurs, an area of increased air pollution, etc. In this case, to analyze various indicators of network efficiency, the theory of random processes is used, and here, Markov chains with continuous time occupy a special place, since they allow a fairly accurate description of the behavior of real systems. Also the mathematical apparatus is well developed for them. In particular, when studying automobile networks (VANET, V2X, IoV), Poisson streams of events are often used. The relevant Markov chain changes state under the influence of these streams. Using the Poisson process, both vehicle traffic and transmitted data packets flows are modeled.

In many publications, random graphs and hvpergraphs are considered as models of non-stationarv networks. The use of models and algorithms of graph theory allows you to investigate the relationship between various elements in the network, to solve the problems of optimizing data transmission. For example, hvpergraph models are useful for accounting for interference in networks with a large number of mobile nodes. The use of graph theory algorithms for solving problems is mainly divided into two categories: researching data on mobile users to determine traffic patterns and planning the functioning of a cellular network with a resource spectrum.

Further, in the proposed review, publications of recent years are analyzed, in which various methods of modeling networks with mobile nodes and algorithms for the optimal functioning of such networks are investigated.

Key words: non-stationarv networks, models of networks with mobile nodes, queuing systems, simulation.

Bibliographic reference :Shakhov V. V., Sokolova 0. D. Analysis of networks with non-stationary topology. Survey//journal “Problems of informatics”. 2020, № 4. P.27-42. DOI: 10.24411/2073-0667-2020-10014

article


V. M. Vishnevsky, O.V. Semenova

Institute of Control Sciences of Russian Academy of Sciences 117997, Moscow, Russia

REVIEW ON MODELS OF POLLING SYSTEMS AND THEIR APPLICATIONS TO TELECOMMUNICATION NETWORKS

DOI: 10.24411/2073-0667-2020-10015

The research is supported by the Russian Foundation for Basic Research, project N 19-29-06043.

The pThe research is supported by the Russian Foundation for Basic Research, project N 19-29-06043.aper provides an overview of studies on stochastic polling systems published in 2007 2019. Due to the applicability of the stochastic polling models, the researchers face new and more complicated polling models. Stochastic polling models arc effectively used for performance evaluation, design and optimization of the telecommunication systems and networks, transport systems and road management systems, traffic, production systems and inventory management systems. Polling systems arc queuing systems with multiple queues and a common server (or a multiple servers). Each queue has its own input of customers. Following to a certain rule, the server visits the queues and serves the customers. In the review, we separately discuss the results for two-queue systems as a special ease of polling systems. Then we discuss new and already known methods for polling system analysis including the mean value analysis and its application to the systems with heavy load to approximate the performance characteristics. We also present the results concerning the specifics in polling models: a polling order, service disciplines, methods to queue or to group arriving customers, and a feedback in polling systems. The new direction in the polling system models is investigation of how the customer service order within a queue affects the performance characteristics. The results on polling systems with correlated arrivals (MAP, BMAP, and the group Poisson arrivals simultaneously to all queues) arc also considered. Then we briefly present the results on multi-server and non-discrctc polling systems (the continuous systems where the number of waiting places arc nondcnumcrablc and the fluid polling models) arc briefly presented.

Key words: polling systems, polling order, queue service discipline, mean value analysis, probability generating function method, broadband wireless networks.

Bibliographic reference: Vishnevsky V. M., Semenova О. V. Review on models of polling systems and their applications to telecommunication networks //journal “Problems of informatics”. 2020, № 4. P.43-70. DOI: 10.24411/2073-0667-2020-10015

article


A. I. Krylova, N.A. Lapteva*

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia
♦Federal Budgetary Research Institution ,, State Research Center of Virology and Biotechnology „Vector" Federal Service for Surveillance on Consumer Rights Protection and Human Well-being, 630559, Koltsovo, Novosibirsk Region, Russia

MODELING THE STREAMFLOW IN THE LENA RIVER BASIN ON THE BASIS OF A HYDROLOGICALLY CORRECT DIGITAL ELEVATION MODEL

DOI: 10.24411/2073-0667-2020-10016

This article presents the results of numerical modelling of river runoff hvdrographs and long-term runoff dynamics for the Lena River basin using MERRA reanalvsis data for the period of 1985 2005. On the basis of the new version of the climatic linear hydrological model of the river flow for calculating the flow hvdrograph in the outlet section of the Kyusvur of the Lena River, the transformation of overland flow and baseflow for each calculation gridbox of the catchment, taking into account the time of water travel through the gridbox, is performed according to the linear two-parameter Kalinin- Milvukov model, and to calculate the flow transformation into of the river network, a linear model of the formation of the water balance in the channel network is used. The previously developed climate model of river flow used the model structure proposed at the Max Planck Institute, according to which the lateral watcrflow on land was divided into three components, that is overland flow, baseflow and riverflow. The sum of the three flow processes equals the outflow from a gridbox. The same approach is used in the new version of the model. According to the Ivalinin-Milyukov model, the travel curve (the influence function of a linear system) for calculating the water discharge is similar to the discrete representation of the gamma distribution. The parameterization of the retention coefficient for overland flow and baseflow is determined by formulas that depend on the characteristics of the grid cell. To calculate the riverflow in the channel cell, the water balance equation is solved using parameterization for the water discharge at the outlet from the cell, which is proportional to the water supply in the cell, the effective water velocity taking into account the tortuosity of the channel, and is inversely proportional to the distance between the calculated gridboxes.

We have constructed a new schematized model hydrographic network of the Lena River Basin on the basis of a hvdrologicallv correct digital elevation model with a resolution of (1/3)° x (1/3)°, obtained from SRTM30 and GT0P03Q data. The fragment of data including the Lena River basin: 53° T72° N, 103° T140° E was transformed using geostatic kriging modelling into a gridded topographic dataset with a resolution of (1/3)° x (1/3)°. This work was carried out on the basis of the Surfer 8 software package used in the Microsoft Windows environment. Along with kriging, other methods of spatial analysis were considered. According to the results of evaluating the accuracy of the methods for various terrain conditions, the kriging method with an exponential semivariogram model was chosen. In addition to the SRTM30 and GT0P03Q data, topographic maps of the Lena River Basin in the scale of one centimeter to two and ten kilometers were used. For each gridbox a single flow direction was calculated according to the maximum topography gradient with adjacent 8 gridboxes. The granularity of the model hydrographic network depends on the setting of a threshold for the minimum number of gridboxes flowing into a catchment gridbox. For the constructed drainage network, the threshold value turned out to be 20. This value determined the network practically free of artifacts even in low-lying parts of the catchment. Comparison of this schematization with the real area of ??the basin showed an excess of schematization bv ~ 40 thousand km2 (50 gridboxes).

For numerical experiments on simulation of the runoff hvdrograph in the Lena River Basin, retrospective analysis data of the modern era were used for MERRA research and applications for 1985-2005. The use of the global reanalvsis database MERRA allows to determine the distributed fields of surface runoff and drainage by simple balance ratios using data on precipitation, evaporation and surface air temperature. These fields are required to initialize a linear climatic river flow model as input data. Two parameters and one correction factor (common for the entire basin) were calibrated. Those were the air temperature at the surface at which the snow begins to melt, the effective velocity of water movement in the river channel, taking into account its tortuosity and the flow coefficient, which determines which part of the moisture content goes into the overland flow, and which into the ground. The data on water discharge from the R-ArcticNET archive made it possible to simulate the regulated flow and assess the impact of the reservoir at the Chernyshevskv, Svuldvukar, Suntar, Khatvryk-Khomo gauging stations, located near the alignment of HPP-I, II downstream the Vilvui River, as well as at the closing outlet section of the Kvusvur of Lena River basin. The modelling results showed the seasonal regulation of the lower reaches of the Vilvui and Lena rivers by the Vilvui reservoir. The annual hydrological cycle calculated according to the new version of the climatic model of the river flow corresponds to the current dynamics of flow in the basin in winter, spring and summer-autumn periods, which is characterized by low winter flow from November to April, high flood from May to July, significant floods from August to October. The model interannual flow variability contains a small linear trend in the outlet section of the Kvusvur, which may indicate the response of the river runoff to climatic changes in the period of 1985-2005. However, in comparison with the linear trend obtained from the measurement data, it is rather insignificant. The estimates of the results of simulation of the monthly flow discharge, obtained using two statistical criteria for the correspondence of the calculated and measured discharge values, turned out to be close in the efficiency of calculations to the estimates of the results obtained by the VIC hydrological model and by the model of heat and moisture exchange of the underlying land surface with the SWAP atmosphere.

Key words: numerical modeling, river runoff, Lena Kiver basin, hydrologicallv correct elevation model, linear climate model, runoff hvdrograph, global database, gauging station.

Bibliographic reference: Krylova A. I., Lapteva N. A. Modeling the streamflow in the Lena River basin on the basis of a hvdrologieally correct digital elevation model //journal “Problems of informatics”. 2020, № 4. P.71-88. DOI: 10.24411/2073-0667-2020-10016

article