2020 № 4(49)

CONTENTS

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

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.

References

Avgustin A. Ispoved’. Seriva „Pamvatniki religiozno-filosofskoj mvsli“. Per. s lat. M. K. Sergeenko. 1991. M.: Izdatel’stvo „Ren„ssans“, SP IVO — SiD. ISBN 5-7664-0472-7.
Namestnikov A. M. Razrabotka imitacionnvh modelej v srede MATLAB // Meto-dicheskie ukazaniva diva studentov special’nostej 01719, 351400. Ul’yanovsk, Ul-GTU, 2004.
SHevchenko A. A. Upravlenie vremenem pri proektirovanii imitacionnvh modelej // CHast’ sb. Prikladnava informatika. N 3. 2006. Laboratoriva Matematicheskogo i komp’vuternogo modelirovaniva. S. 113-119.
Skopin I. N. Lokal’noe i global’noe vremva pri modelirovanii razvivavushchihsva si-stem. V sb. trudov Sed’moj mezhdunarodnoj konferencii pamvati akademika A. P. Ershova „Perspektivv sistem informatiki“. Rabochij seminar „Naukoemkoe pro-grammnoe obespechenie“. Novosibirsk: OOO „Sibirskoe Nauchnoe Izdatel’stvo“, 2009. S. 255-259.
Sistema. Bol’shoj Rossijskij enciklopedicheskij slovar’. M.: BRE. 2003, S. 1437.
Smirnov G. A. Okkam, Uil’yam // Novava filosofskava enciklopediva / In-t filosofii RAN; Nac. obshchestv.-nauch. fond. 2-e izd., ispr. i dopol. M.: Mvsl’, 2010. ISBN 978-5-244-01115-9.
Skopin I. N. Ierarhicheskie otnosheniva . metodologicheskava osnova izucheniva po-nyativa ierarhij // Vestnik Rossijskogo universiteta druzhbv narodov. Seriva „Informatizaciva obrazovaniva“. M.: RUDN, 2014. N 1. S. 56-63.
Skopin I. N. Subordinacionnve otnosheniva v metodike izucheniva ponvativa ierar-hichnosti // Vestnik Rossijskogo universiteta druzhbv narodov. Seriva „Informatizaciva obrazovaniva“. M.: RUDN, 2014. N 2. S. 35-49.
Dejkstra E. Vzaimodejstvie posledovatel’nyh processov. V sb. „YAzvki program-mirovaniva“, pod red. F. ZHenvui. Per. s angl. M.: „Mir“, 1972.
Lamport L. Time, clocks, and the ordering of events in a distributed systems // Commun. ACM. 1978. Vol. 21(7). P. 558-565.
Chandv К. M., Misra J. Distributed simulation: a case study in design and verification of distributed programs // IEEE Transactions on Software Engineering. 1978. Vol. SE-5(5). P. 440-452.
Ferscha A. Parallel and distributed simulation of discrete event systems // Parallel and Distributed Computing Handbook. McGraw-Hill. 1996. P. 1003-1041.
Kazakov YU. P., Smelvanskij R. L. Ob organizacii raspredelennogo imitacionnogo modelirovaniva // Programmirovanie. 1994. N 2. S. 45-63.
Fujimoto R. M. Parallel and Distributed Simulation Systems // Wiley Interscience, 2000.
Fujimoto R. M. Parallel and Distributed Simulation Systems // Proc. of the Winter Simulation Conf. 2001. P. 147-157.
Dal O. I., Nvugord K. Simula . vazvk diva programmirovaniva i opisaniva sistem s diskretnvmi sobytivami // Algoritmv i algoritmicheskie vazvki. Vvp. 2. M.: VC AN SSSR, 1967.
Dal О. I., Mvurhaug B., Nvugord K. Simula 67 universal’nvj vazvk programmirova-niva // Perevod s angl. K. S. Kuz’mina i E. I. YAkovleva. M.: Mir, 1969.
Nvgaard K., Dahl O.-J. The Development of the SIMULA Languages // History of programming languages. ACM New York, NY, USA, 1981. P. 439-480.
Nepejvoda N. N. Skopin I. N. Osnovaniva programmirovaniva. Izd-vo: Moskva-Izhevsk: Institut komp’yuternyh issledovanij. 2003. ISBN: 5-93972-299-7.
Backus J. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs // CACM, 21(8), August 1978. P. 613-641.
Malvshkin V. Assembling of Parallel Programs for Large Scale Numerical Modeling. . In the Handbook of Research on Scalable Computing Technologies. IGI Global, USA, 2010. Chapter 13, P. 295-311. ISBN 978-1-60566-661-7.
Keene S. Object-Oriented Programming in Common Lisp: A Programmer’s Guide to CLOS, 1988, Addison-Wesley. ISBN 0-201-17589-4
Haskell 98 Language and Libraries. The Revised Report. Dec. (Electron. Res.]: https://www. haskell.org/onlinereport/.
Akhmed-Zaki D., Lebedev D., Malvshkin V., Perepelkin V. Automated Construction of High Performance Distributed Programs in LuNA System // PaCT-2019 proceedings, LNCS 11657, Springer, 2019, P. 3-9. DOI: 10.1007/978-3-030-25636-4^1.
Ahmed-Zaki D. ZH., Lebedev D. V., Malvshkin V. E., Perepelkin V. A. Avtomati-zaciva konstruirovaniva raspredelennvh programm chislennogo modelirovaniva v si-steme LuNA na primere model’noj zadachi // Problemv informatiki, N 4, 2019. S. 53-64. DOI: 10.24411/2073-0667-2019-00017.
Okol’nishnikov V. V. Predstavlenie vremeni v imitacionnom modelirovanii // Vychislitel’nve tekhnologii. 2005. T. 10, N 5. S. 57-80.IEEE Std P1516.
IEEE Standard for Modeling and Simulation (MVS) High Level Architecture (HLA) — Framework and Rules. N.Y.: Institute of Electrical and Electronics Engineers, Inc., 2000.

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

article

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.

References

Wu X. A Hybrid View of Mobility in MANETs: Analytical Models and Simulation Study // Computer Comm. 2008.Vol. 31. N. 16. P. 3810-3821.
Barani, H., Fathv, M. An Algorithm for Localization in Vehicular Ad-Hoc Networks. // Journal of Computer Science. 2010. Vol. 6. N 2. P. 168-172.
Liu C., Yang O., Li G, Shu Y. Effective Transmission Coverage Area-Based Link Dynamics Characterization of VANET in Highway Scenario // International Journal of Distributed Sensor Networks. 2015. Vol. 11. N 10.
Elhosenv M., Shankar K. Energy Efficient Optimal Routing for Communication in VANETs via Clustering Model. // Emerging Technologies for Connected Internet of Vehicles and Intelligent Transportation System Networks. Studies in Systems, Decision and Control. 2020. Vol. 242.
Liu T., Zhao L., Li B., Zhao C. Research on the Enhancement of VANET Coverage Based on UAV. // Liang Q., Wang W., Liu X., Na Z., Jia M., Zhang B. (eds) Communications, Signal Processing, and Systems. CSPS.2019. Lecture Notes in Electrical Engineering. Vol. 571. Springer, Singapore.
Qiu, Z., Wu, L., Zhang, P. An Efficient Localization Method for Mobile Nodes in Wireless Sensor Networks // International Journal of Online Engineering.2017. Vol. 13. N 3.
Sokolova O., Yurgenson A. Using graph, hvpergraph, and hvpernet models for network analysis problems // Proc. 7th International Forum on Strategic Technology (IFOST), 2012.
Reddy A. R., Venkatesh D., Ramesh K. Hvpergraph Interference Models in Wireless Ad-Hoc Networks with Low Complexity Distributed Scheduling // International journal of scientific research. 2012. 2. P. 237-240.
Webb J., Docemmilli F., Bonin, M. Graph Theory Applications in Network Security // ArXiv.2015. abs/1511.04785.
Yang L., Yu Y. H. A Mobile Frequency Allocation Algorithm Based on the Graph Theory // International Conference on Computer Information Systems and Industrial Applications. 2015.
Goldin D., Attia S. A. Unit Disk Graph Based Modelling of a Network of Mobile Agents // Proceedings of the First IFAC Workshop on Estimation and Control of Networked Systems. Venice, Italy. 2009.
Sorokin A. A., Dmitriev V. N. Opisanie sistem svvazi s dinamicheskoj topologiej seti pri pomoshchi modeli „mercavushchego grafa“ // Vestnik AGTU. Seriva: Upravlenie, vychislitel’nava tekhnika i informatika. 2009. N 2. S. 134-139.
Eiza M. H., Ni Q. An Evolving Graph-Based Reliable Routing Scheme for VANETs // IEEE Transactions on Vehicular Technology. 2013. Vol. 62. N. 4. P. 1493-1504.
Liu К., Ng J. К. Y., Lee V. С. S., Son S. Н., Stojmenovic I. Cooperative Data Scheduling in Hybrid Vehicular Ad Hoc Networks: VANET as a Software Defined Network // IEEE ACM Transactions on Networking.2016. Vol. 24. N 3. P. 1759-1773.
Mokdad, L., Ben-Othman, J., Nguyen, A.T. DJAVAN: Detecting jamming attacks in Vehicle Ad hoc Networks // Performance Evaluation. 2015. Vol. 87. P. 47-59.
Shakhov V., Sokolova O. Towards Air Pollution Detection with Internet of Vehicles // 15th International Asian School-Seminar Optimization Problems of Complex Systems, Novosibirsk, Russia, 2019, P. 183-186.
Deng D., Lien S., Lin C., Hung S., Chen W. Latency Control in Software-Defined Mobile-Edge Vehicular Networking // IEEE Communications Magazine. 2017. Vol. 55. N 8, P. 87-93.
Zhou S., Sun Y., Jiang Z., Niu Z. Exploiting Moving Intelligence: Delay-Optimized Computation Offloading in Vehicular Fog Networks // IEEE Communications Magazine. 2019. Vol. 57. N 5. P. 49-55.
Zhou Z., Yu H., Xu C., Chang Z., Mumtaz S., Rodriguez J. BEGIN: Big Data Enabled Energy- Efficient Vehicular Edge Computing // IEEE Communications Magazine. 2018. Vol. 56. N 12. P. 82-89.
Bertsekas D., Gallager R. Seti peredachi dannvh. M.: Mir, 1989.
Zhu H., Fu L., Xue G., Zhu Y., Li M., NiL. M. Recognizing Exponential Inter-Contact Time in VANETs // Proceedings IEEE INFOCOM, San Diego, CA, 2010. P. 1-5.
Jiang R., Zhu Y., Yang Y. Improving Throughput and Fairness of Converge cast in Vehicular Networks // IEEE Transactions on Mobile Computing. 2017. Vol. 16. N 11. P. 3070-3083.
Li Y., Jin D., Hui P., ChenS. Contact-aware data replication in roadside unit aided vehicular delay tolerant networks // IEEE Transactions on Mobile Computing. 2016. Vol. 15. N 2. P. 306-321.
LiuY., Peng M., Shou G., Chen Y., Chen S. Toward Edge Intelligence: Multiaccess Edge Computing for 5G and Internet of Things // IEEE Internet of Things Journal. 2020. Vol. 7. N 8. P. 6722-6747.
Guo H., Liu J., Zhang J. Computation Offloading for Multi-Access Mobile Edge Computing in Ultra-Dense Networks // IEEE Communications Magazine. 2018. Vol. 56. N 8. P. 14-19.
Mao Y., You, C. Zhang J., Huang K., Letaief К. B. A Survey on Mobile Edge Computing: The Communication Perspective // IEEE Communications Surveys k, Tutorials. 2017. Vol. 19. N 4. P. 2322-2358.
Krylov V. V., Samohvalova S. S. Teoriva teletrafika i ее prilozheniva // SPb.: BHV-Peterburg, 2005.
Hashim M. F., Abdul Razak, N. I. Ultra-Dense Networks: Integration with Device to Device (D2D) Communication // Wireless Personal Communications. 2019. Vol. 106. P. 911-925.
Zhang К., Mao, Y. Leng S., He Y., Zhang Y. Mobile-Edge Computing for Vehicular Networks: A Promising Network Paradigm with Predictive Off-Loading // IEEE Vehicular Technology Magazine. 2017. Vol. 12. N 2. P. 36-44.
Thai M., Lin Y., Lai Y., Chien H. Workload and Capacity Optimization for Cloud-Edge Computing Systems with Vertical and Horizontal Offloading // IEEE Transactions on Network and Service Management. 2020. Vol. 17. N 1. P. 227-238.
Cui L., Xu C., Yang S., Huang J. Z., Li J., Wang X., Ming Z., Lu N. Joint Optimization of Energy Consumption and Latency in Mobile Edge Computing for Internet of Things // IEEE Internet of Things Journal. 2019. Vol. 6. P. 4791-4803.
Chen Y., Sun Y., Feng T., Li S. A Collaborative Service Deployment and Application Assignment Method for Regional Edge Computing Enabled IoT // IEEE Access. 2020. Vol. 8. P. 112659-112673.
Islambouli R., Sharafeddine S. Optimized 3D Deployment of UAV-Mounted Cloudlets to Support Latency-Sensitive Services in IoT Networks // IEEE Access. 2019. Vol. 7. P. 172860-172870.
Ebrahimzadeh A., Maier N4. Cooperative Computation Offloading in FiWi Enhanced 4G HetNets Using Self-Organizing MEC // IEEE Transactions on Wireless Communications. 2020. Vol. 19. N 7. P. 4480-4493.
Wang S., Zhang X., Yan Z., Wenbo W. Cooperative Edge Computing With Sleep Control Under Nonuniform Traffic in Mobile Edge Networks // IEEE Internet of Things Journal. 2019. Vol. 6. N 3. P. 4295-4306.
Hajipour J. Stochastic Buffer-Aided Relay-Assisted MEC // IEEE Communications Letters. 2020. Vol. 24. N 4. P. 931-934.
Doan T. V., You D., Salah H., Nguyen G. T., Fitzek H. P. F. MEC-assisted Immersive Services: Orchestration Framework and Protocol // IEEE Intern. Symposium on Broadband Multimedia Systems and Broadcasting (BMSB), Jeju, Korea (South), 2019. P. 1-6.
Wu S., Xia W., Cui W., Chao Q., Lan Z., Yan F., Shen L. An Efficient Offloading Algorithm Based on Support Vector Machine for Mobile Edge Computing in Vehicular Networks // 10th International Conference on Wireless Communications and Signal Processing (WCSP), Hangzhou. 2018. P. 1-6.
Zhang Q., Chen J., Ji L., Feng Z., Han Z., Chen Z. Response Delay Optimization in Mobile Edge Computing Enabled UAV Swarm // IEEE Transactions on Vehicular Technology. 2020. Vol. 69. N 3. P. 3280-3295.
Belogaev A., Elokhin A., Krasilov A., Khorov E., Akvildiz I. F.Cost-Effective V2X Task Offloading in MEC-Assisted Intelligent Transportation Systems // IEEE Access. 2020. Vol. 8. P. 169010-169023.
Zhou Z., Yu S., Chen W., Chen X. CE-IoT: Cost-Effective Cloud-Edge Resource Provisioning for Heterogeneous IoT Applications // IEEE Internet of Things Journal. 2020. Vol. 7. N 9. P. 8600-8614.
Nguyen M. N. H., Zaw C. W., Kim K., Tran N. H., Hong C. S. Let’s Share the Resource When We’re Co-Located: Co-location Edge Computing // IEEE Transactions on Vehicular Technology. 2020. Vol. 69. N 5. P. 5618-5633.
Wang Y., Yang J., Guo X., Qu Z. A Game-Theoretic Approach to Computation Offloading in Satellite Edge Computing // IEEE Access. 2020. Vol. 8. P. 12510-12520.
Al-Mavouf Y. R. B., Ismail M.. Abdullah N. F., Al-Qaraawi S. M.. Mahdi O. A. Survey on VANET technologies and simulation models // ARPN Journal of Engineering and Applied Sciences. 2016. Vol. 11. N 15. P. 9414-9427.
Jukic Z., Arshad M. Review of Simulation Based Comparison of VANET Protocols // New Technologies, Development and Application. NT 2018. Lecture Notes in Networks and Systems. Vol. 42. Springer.
Sanguesa J. A., Fogue M., Garrido P., Martinez F. J., Cano J.-C., Calafate С. T. A survey and comparative study of broadcast warning message dissemination schemes for VANETs / Mobile Information Systems. 2016, art.ID 8714142, 18 p.
Elgazzar M. M. A., Alshareef A. VANET Simulator: Full Design Architecture // International Journal of Engineering and Advanced Technology. 2020. Vol. 9. N 3.
Jia D., Lu K., Wang J., Zhang X., Shen X. A Survey on Platoon-Based Vehicular Cyber-Phvsical Systems // IEEE Communications Surveys & Tutorials. 2016. Vol. 18. N 1. P. 263-284.
VISSIM. (Electron. Res.]: http://www.ptv-vision.com/en-uk/products/vision-traffic- suite/ptv-vissim/overview/.
Harri J., Fiore M., Bonnet F. Vehicular mobility simulation with Vanet MobiSim // Simulation. 2009. Vol. 87. N 4. P. 275-300.
Behrisch M., Bieker L., Erdmann J., Krajzewicz D. SUMO simulation of urban Mobilitv-an overview // in Proc. 3rd Int. Conf. Adv. Svst. SIMUL. 2011. P. 63-68.
NS-3. (Electron. Res.]: https://www.nsnam.org/.
Omnetpp. (Electron. Res.]: www.omnetpp.org.
TraNS. [Electron. Res.]: http://lca.epfl.ch/projects/trans/.
Rudometov S. V., Sokolova O. D. Modelirovanie peredachi soobshchenij mezhdu dvizhushchimisva ob“ektami v transportnoj srede // Programmnve produktv i sistemv. 2019. T. 32. N 1. S. 1111 15.
Sanguesa J.A., Fogue M., Garrido P., Martinez F., Cano J., Calafate C. A Survey and Comparative Study of Broadcast Warning Message Dissemination Schemes for VANETs // Mob. Inf. Svst. 2016.
Yang F., Wu N., Qiao Y., Zhou M.. Su R., Qu T. Modeling and Optimal Cyclic Scheduling of Time-Constrained Single-Robot-Arm Cluster Tools via Petri Nets and Linear Programming // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2020. Vol. 50. N 3. P. 87П883.
Alam T., Bobadilla L., Shell D. A. Space-Efficient Filters for Mobile Robot Localization from Discrete Limit Cycles // IEEE Robotics and Automation Letters. 2018. Vol. 3. N 1. P. 257-264.
Zhang H., Niu M. Modeling and Analysis of Long-Term Average User Throughput in Mobile Ultra Dense Networks // IEEE Wireless Communications Letters. 2019. Vol. 8. N 5. P. 1498-1501.
Abdel-Aziz M. K., Samarakoon S., Liu C., Bennis M., Saad W. Optimized Age of Information Tail for Ultra-Reliable Low-Latency Communications in Vehicular Networks // IEEE Transactions on Communications. 2020. Vol. 68. N 3. P. 1911-1924.
Centenaro M., Tomasin S., Benvenuto N., Yang S. Predictive Voice-Over-Internet Protocol Fallback Over Vehicular Channels: Employing Artificial Intelligence at the Edge of 5G Networks // IEEE Vehicular Technology Magazine. 2020. Vol. 15. N 2. P. 72-78.

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.

References

Vishnevsky V. M., Semenova О. V. Sistemv pollinga: tcoriva i primeneniye v shirokopolosnvkh besprovodnykh setvakh. M.: Tcklmosfcra, 2007. [in Russian]
Vishnevsky V., Semenova O. Polling Systems: Theory and Applications for Broadband Wireless Networks /7 LAMBERT Academic Publishing, 2012.
Boon M. A. A., van dor Mei R. D., Winands E. M. M. Applications of polling systems /7 Surveys in Operations Research and Management Science. 2011. V. 16, N 2. P. 67 82.
Cao .J., Feng W., Chen Y., Go N., Wang S. Performance analysis of a polling model with BMAP and aeross-ciueue state-dependent service discipline /7 IEEE Access. 2019. V. 7. P. 127230 127253.
He M., Guan Z., Wu Z., Lu L., Zhou Z., Anisetti M., Damiani E. A polling access control with exhaustive service in wireless body area networks for mobile healthcare using the sleeping schema /7 ■Journal of Ambient Intelligence and Humanized Computing. 2019. V. 10, N 10. P. 3761 3774.
Granville К., Drekic S. A 2-class maintenance model with dynamic server behavior // TOP. DOI: https://doi.org/10.1007/sll750-019-00509-l.
Takagi H. Analysis of polling systems. MIT Press, 1986.
Borst S.C. Polling systems. Amsterdam: Stichting Mathematisch Centrum, 1996.
Vishnevskii V. M., Semenova O.V. Mathematical methods to study the polling systems // Automation and Remote Control. 2006. V. 67, N 2. P. 173-220.
Vishnevsky V. M., Mishkov G.K., Semenova O.V. New models and methods to study polling systems // Proceedings of the International Conference proceedings Distributed Computer and Communication Networks. Theory and Applications (DCCN-2009, Moscow). M.: R&D Company „Information and Networking Technologies“, 2009. P. 79-85. fin Russian]
Borst S.C., Boxma O.J. Polling: past, present, and perspective // TOP. 2018. V. 26, N 3. P. 335-369.
Vishnevsky V. M., Semenova O.V., Bui D.T., Sokolov A.M. Adaptive cyclic polling systems: analysis and application to the broadband wireless networks // Lecture Notes in Computer Science. 2019. V. 11965. P. 30-42.
Winands E. M.M., Adan I. J.B.F., van Houtum G.J., Down D.G. A state-dependent polling model with fc-limited service // Probability in the Engineering and Informational Sciences. 2009. V. 23, N 2. P. 385-408.
Boon M. A. A., Adan I. J. B. F., Boxma O.J. A two-queue polling model with two priority levels in the first queue // Discrete Event Dynamic Systems. 2010. V. 20, N 4. P. 511-536.
Vlasiou M., Adan I. J. B. F., Boxma O.J. A two-station queue with dependent preparation and service times // European Journal of Operational Research. 2009. V. 195, N 1. P. 104-116.
Chernova N., Foss S., Kim B. A polling system whose stability region depends on the whole distribution of service times // Operations Research Letters. 2013. V. 41, N 2. P. 188-190.
Dorsman J.-P. L., Boxma O.J., van der Mei R. D. On two-queue Markovian polling systems with exhaustive service // Queueing Systems. 2014. V. 78, N 4. P. 287-311.
Boon M.A.A., Winands E. M.M. Heavy-traffic analysis of fc-limited polling systems // Probability in the Engineering and Informational Sciences. 2014. V. 28, N 4. P. 451-471.
Adan I. J.B.F., Boxma O. J., Kapodistria S., Kulkarni V. G. The shorter queue polling model // Annals of Operations Research. 2016. V. 241, N 1. P. 167-200.
Gaidamaka Yu.V. Model with threshold control for analysing a server with SIP protocol in the overload mode // Automatic Control and Computer Science. 2013. V. 47, N 4. P. 211-218.
Shorgin S., Samouvlov K., Gaidamaka Y., Etezov S. Polling system with threshold control for modeling of SIP server under overload // Advances in Intelligent Systems and Computing. 2014. V. 240. P. 97-107.
Avrachenkov K., Perel E., Yechiali U. Finite-buffer polling system with threshold-based switching policy // TOP. 2016. V. 24, No. 3. P. 541-571.
Perel E., Yechiali U. Two-queue polling systems with switching policy based on the queue that is not being served // Stochastic Models. 2017. V. 33, N 3. P. 430-450.
Jolles A., Perel E., Yechiali U. Alternating server with non-zero switch-over times and opposite- queue threshold-based switching policy // Performance Evaluation. 2018. V. 126. P. 22-38.
Perel E., Perel N., Yechiali U. A polling system with „Join the shortest — serve the longest¹¹policy // Computers k, Operations Research. 2019. V. 114, 104809.
Liu Z., Chu Y., Wu J. On the three-queue priority polling system with threshold service policy // Journal of Applied Mathematics and Computing. 2017. V. 53, N 1. P. 445-470.
Chernova N., Foss S., Kim B. On the stability of a polling system with an adaptive service mechanism // Annals of Operations Research. 2012. V. 198, N 1. P. 125-144.
Winands E. M. M., Adan I. J. B. F., van Houtum G. J. Mean value analysis for polling systems // Queueing Systems. 2006. V. 54. P. 35-44.
van Vuuren М., Winands Е.М.М. Iterative approximation of fc-limited polling systems // Queueing Systems. 2007. V. 55. N 3. P. 161-178.
van der Mei R. D., Winands E. Heavy traffic analysis of polling models by mean value analysis // Performance Evaluation. 2008. V. 65, N 6-7. P. 400-416.
Vishnevsky V. M., Semenova O.V. Adaptive dynamical polling in wireless networks // Cybernetics and Information Technologies. 2008. V. 8, N 1. P. 3-11.
Wierman A., Winands E., Boxma O.J. Scheduling in polling systems // Performance Evaluation. 2007. V. 64, N 9-12. P. 1009-1028.
Boon M.A.A., van Wijk A. C.C., Adan I.J.B.F., Boxma O.J. A polling model with smart customers // Queueing Systems. 2010. V. 66. P. 239-274.
Vishnevskii V. M., Semenova O.V., Shpilev S.A. A duplex cyclic polling system for mixed queues // Automation and Remote Control. 2009. V. 70. P. 2050-2060.
Yechiali U. Analysis and control of polling systems // Performance Evaluate of Computer and Communication Systems. Ed. Donatielo L., Nelson R. Springer-Verlag. 1993. P. 630-650.
Boxma O.J., Kella O., Kosinski K.M. Queue lengths and workloads in polling systems // Operations Research Letters. 2011. V. 39. N 6. P. 401-405.
Resing J. A. C. Polling systems and multitype branching processes // Queueing Systems. 1993. V. 13. P. 413-426.
Guan Z., Zhao D. A delay-guaranteed two-level polling model // Advances in Computer Science and Information Engineering. Advances in Intelligent and Soft Computing. 2012. V. 168. P. 153-158.
Saffer Z., Telek M. Unified analysis of BMAP/G/1 cyclic polling models // Queueing Systems. 2010. V. 64, N 1. P. 69-102.
Vishnevsky V. M., Dudin A.N., Klimenok V. I. Stokhasticheskive sistemv s korrelirovannvmi potokami. Teoriva i primenenive v telekommunikatsionnvkh setvakh. M.: Tekhnosfera, 2018.
Dudin A. N., Klimenok V. I., Vishnevsky V. M. Methods to Study Queuing Systems with Correlated Arrivals. 2020. Springer. 410 p.
Hiravama T., Hong S.J., Krunz M.M. A new approach to analysis of polling systems // Queueing Systems. 2004. V. 48, N 1-2. P. 135-158.
Hiravama T. Multiclass polling systems with Markovian feedback: mean sojourn times in gated and exhaustive systems with local priority and FCFS service orders // Journal of the Operations Research Society of Japan. 2005. V. 48, N3. P. 226-255.
Hiravama T. Markovian polling systems: functional computation for mean waiting times and its computational complexity // Advances in Queueing Theory and Network Applications. W. Yue et al. (eds.) 2009. P. 119-146. '
Rvkov V. V. On analysis of periodic polling systems // Automation and Remote Control. 2009. V. 70. P.*997-1018.
van der Mei R. D. Towards a unifying theory on branching-type polling systems in heavy traffic // Queueing Systems. 2007. V. 57, N l.P. 29-46.'
Semenova O.V., Bui D.T. Paket prikladnvkh programm diva issledovaniva sistem pollinga // Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenive, vvchisliternava tekhnika i informatika. N 50. P. 106-113. fin Russianj
Saffer Z. BMAP/G/1 cyclic polling model with binomial disciplines // Modern Probabilistic Methods for Analysis of Telecommunication Networks. Communications in Computer and Information Science. 2013. V. 356. P. 157-166.
Vishnevsky V. M., Semenova O.V., Bui D.T. Using machine learning to study polling systems with correlated flow input // Proceedings of the Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems 2020 (ITTMM 2020). Moscow, RUDN, April 1317, 2020. P. 248-253. fin Russianj
Saffer Z., Telek М. Stability of periodic polling system with BMAP arrivals // European Journal of Operational Research. 2009. V. 197, N 1. R 188-195.
Vis P., Bekker R., van der Mei R. D. Transient analysis of cycle lengths in cyclic polling systems // Performance Evaluation. 2015. V. 91. P. 303-317.
Dorsman J.-P. L., Borst S.C., Boxma O.J., Vlasiou M. Markovian polling systems with an application to wireless random-access networks // Performance Evaluation. 2015. V. 85-86. P. 33-51.
Hiravama T. Analysis of multiclass Markovian polling systems with feedback and composite scheduling algorithms // Annals of Operations Research. 2012. V. 198, N 1. P. 83-123.
Fiems D., Altman E. Gated polling with stationary ergodic walking times, Markovian routing and random feedback // Annals of Operations Research. 2012. V. 198, N 1. P. 145-164.
MacPhee I., Menshikov M., Petritis D., Popov S. A Markov chain model of a polling system with parameter regeneration // Annals of Applied Probability. 2007. V. 17, N 5-6. P. 1447-1473.
MacPhee I., Menshikov M., Petritis D., Popov S. Polling systems with parameter regeneration, the general case // Annals of Applied Probability. 2008. V. 18, N 6. P. 2131-2155.
Lee T. Analysis of single buffer random polling system with state-dependent input process and server/station breakdowns // International Journal of Operations Research and Information Systems (IJORIS). 2018. V. 9, N 1. P. 22-50.
Guan Z., Zhao D., Zhao Y. A discrete time two-level mixed service parallel polling model // Journal of Electronics (China). 2012. V. 29, N 1-2. P. 103-110.
Yang Z., Ding H. Characteristics of a two-class polling system model // Tsinghua Science and Technology. 2014. V. 19, N 5. P. 516-520.
Bao L., Zhao D., Zhao Y. A priority-based polling scheduling algorithm for arbitration policy in Network on Chip // Journal of Electronics (China). 2012. V. 29, N 1-2. P. 120-127.
Vishnevsky V. M., Dudin A.N., Semenova O.V., Klimenok V. I. Performance analysis of the BMAP/G/1 queue with gated servicing and adaptive vacations // Performance Evaluation. 2011. V. 68, N 5. P. 446-462.
Vishnevsky V. M., Dudin A.N., Klimenok V. I., Semenova O.V., Shpilev S. Approximate method to study M/G/1-type polling system with adaptive polling mechanism // Quality Technology and Quantitative Management. 2012. V. 2. P. 211-228.
Semenova O.V., Bui D.T. Method of generating functions for performance characteristic analysis of the polling systems with adaptive polling and gated service // Communications in Computer and Information Science. 2018. V. 912. P. 348-359.
Boon M. A. A., Adan I. J. B. F. Mixed gated/exhaustive service in a polling model with priorities // Queueing Systems. 2009. V. 63, N 1-4. P. 383-399.
Boon M.A.A., Adan I. J.B.F., Boxma O.J. A polling model with multiple priority levels // Performance Evaluation. 2010. V. 67, N 6. P. 468-484.
Shapira G., Levy H. On fairness in polling systems // Annals of Operations Research. 2016. https://doi.org/10.1007/sl0479-016-2247-8
Boon M., Boxma O.J., Winands E.J.J. On open problem in polling systems // Queueing Systems. 2011. V. 68. N 3-4. P. 365-374.
Winands E.M.M. Branching-type polling systems with large setups // OR Spectrum. 2011. V. 33. P. 77-97.
Hanbali A. A., de Haan R., Boucherie R. J., van Ommeren J.-K. Time-limited polling systems with batch arrivals and phase-type service times // Annals of Operations Research. 2012. V. 198, N 1. P. 57-82.
Boxma O. J., Groenendijk W.P. Pseudo conservation laws in cyclic-service systems // Journal of Applied Probability. 1987. V. 24, N 4. P. 949-964.
Leonovich A., Ferng H.-W. Modeling the IEEE 802.lie HCCA mode // Wireless Networks. 2013. V. 19, N 5. P. 771-783.
de Haan R., Boucherie R. J., van Ommeren J.-K. A polling model with an autonomous server // Queueing Systems. 2009. V. 62, N 3. P. 279-308.
Horng S.-С., Lin S.-Y. Ordinal optimization of G/G/1/K polling systems with k-limited service discipline // Journal of Optimization Theory and Applications. 2009. V. 140, N 2. P. 213-231.
van der Mei R. D., Roubos A. Polling models with multi-phase gated service // Annals of Operations Research. 2012. V. 198, N 1. P. 25-56.
van Wijk A. С. C., Adan I. J. B. F., Boxma O. J., Wierman A. Fairness and efficiency for polling models with the k-gated service discipline // Performance Evaluation. 2012. V. 69, N 6. P. 274-288.
Remerova M., Foss S., Zwart B. Random fluid limit of an overloaded polling model // Advances in Applied Probability. 2014. V. 46, N 1. P. 76-101.
Ling Y., Liu C., Li Y. Study on queue strategy of gated polling multi-access communication system // Recent Advances in Computer Science and Information Engineering. Lecture Notes in Electrical Engineering. 2012. V. 124. P. 99-105.
Vishnevskii V. M., Lakontcev D. V., Semenova О. V., Shpilev S. A. Model sistemv pollinga dlia issledovaniia shirokopolosnvkh besprovodnvkh setei // Avtomatika i telemehanika. 2006. N 12. P. 123— 135.
Vatutin V. A. Multitype Branching processes with immigration in random environment, and polling systems // Siberian Advances in Mathematics. 2011. V. 21, N 1. P. 42-72.
Abidini M. A., Boxma O., Resing J. Analysis and optimization of vacation and polling models with retrials // Performance Evaluation. 2016. V. 98. P. 52-69.
Kim B., Kim J. Analysis of the waiting time distribution for polling systems with retrials and glue periods // Annals of Operations Research. 2019. V. 277, N 2. P. 197-212.
Dorsman J. L., van der Mei R. D., Winands E. M. M. Polling systems with batch service // OR Spectrum. 2012. V. 34. P. 743-761.
Boon M. A. A., Winands E. M. M., Adan I. J. B. F., van Wijk A. С. C. Closed-form waiting time approximations for polling systems // Performance Evaluation. 2011. V. 68, N 3. P. 290-306.
Jiang T., Liu L., Zhu Y. Analysis of a batch service polling system in a multi-phase random environment // Methodology and Computing in Applied Probability. 2017. P. 1-20.
Shomronv M., Yechiali U. Polling systems with positive and negative customers // Technical Report, Department of Statistics and Operations Research, Tel-Aviv University, Tel-Aviv, Israel. 2006.
Shomronv M., Yechiali U. Polling systems with job failures and with station failures // Technical Report, Department of Statistics and Operations Research, Tel-Aviv University, Tel-Aviv, Israel. 2006.
Zorine A. V. On ergodicitv conditions in a polling model with Markov modulated input and state-dependent routing // Queueing Systems. 2014. V. 76, N 2. P. 223-241.
Boon M. A. A. A polling model with reneging at polling instants // Annals of Operations Research. 2012. V. 198, Nl.P. 5-23.
Granville K., Drekic S. On a 2-class polling model with reneging and kj-limited service // Annals of Operations Research. 2019. V. 274, N 1. P. 267-290.
Neuts M.F. Matrix-geometric solutions in stochastic models: an algorithmic approach. Baltimore: Johns Hopkins University Press, 1981.
Boxma O.J., Bruin J., Fralix B.H. Sojourn times in polling systems with various service disciplines // Performance Evaluation. 2009. V. 66, N 11. P. 621-639.
Bekker R., Vis P., Dorsman J.L., van der Mei R. D., Winands E. M. M. The impact of scheduling policies on the waiting-time distributions in polling systems // Queueing Systems: Theory and Applications. 2015. V. 79, N 2. P. 145-172.
Vis P., Bekker R., van der Mei R. D. Heavy-traffic limits for polling models with exhaustive service and non-FCFS service order policies // Advances in Applied Probability. 2015. V. 47, N 4. P. 989-1014.
Kim В., Kim J. Sojourn time distribution in polling systems with processor-sharing policy // Performance Evaluation. 2017. Vol. 114, N 9. P. 97-112.
Cao J., Xie W. Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines // Queueing Systems. 2016. V. 85, N 1-2. P. 117— 147.
Chen W.-L. Computing the moments of polling models with batch Poisson arrivals by transform inversion // INFORMS Journal of Computing. 2019. V. 31, N 3. P. 411-632.
Suman R., Krishnamurthv A. Analysis of tandem polling queues with finite buffers // Annals of Operations Research. 2019. https://doi.org/10.1007/sl0479-019-03358-0
Antunes N., Fricker C., Roberts J. Stability of multi-server polling system with server limits // Queueing Systems. 2011. Vol. 68. P. 229-235.
Boxma O., van der Wal J., Yechiali U. Polling with batch service // Stochastic Models. 2008. V. 24, No.4. P. 604-625.
Vlasiou M., Yechiali U. M/G/x polling systems with random visit times // Probability in the Engineering and Informational Sciences. 2008. V. 22, N 1. P. 212-245.
van der Mei R. D., Winands E. M.M. A note on polling models with renewal arrivals and nonzero switch-over times // Operations Research Letters. 2008. V. 36. P. 500-505.
van der Mei R. D., Levy H. Polling systems in heavy traffic: Exhaustiveness of service policies // Queueing Systems. 1997. V. 27, N 3-4. P. 227-250.
Dorsman J. L., van der Mei R. D., Winands E. M. M. A new method for deriving waiting-time approximations in polling systems with renewal arrivals // Stochastic Models. 2011. V. 27. P. 318-332.
Boon M.A.A., van der Mei R. D., Winands E. M.M. Heavy traffic analysis of roving server networks // Stochastic Models. 2017. V. 33, N 3. P. 1-21.
Mevfrovt T. M. M., Boon M. A. A., Borst S. C., Boxma O. J. Performance of large-scale polling systems with branching-type and limited service // Performance Evaluation. 2019. V. 133. P. 1 21.
Kavitha V., Combes R. Mixed polling with rerouting and applications // Performance Evaluation. 2013. V. 70, N 11. P. 1001-1027.
Boxma O., Ivanovs J., Kosinski K., Mandjes M. Levy-driven polling systems and continuous- state branching processes // Stochastic Systems. 2011. V. 1, N 2. P. 411-436.
Leskela L., Unger F. Stability of a spatial polling system with greedy myopic service // Annals of Operations Research. 2012. Vol. 198, N 1. P. 165-183.
Kavitha V., Altman E. Continuous polling models and application to ferry assisted WLAN // Annals of Operations Research. 2012. Vol. 198, N 1. P. 185-218.
Beekhuizen P., Denteneer D., Resing J. Reduction of a polling network to a single node // Queueing Systems. 2008. V. 58, No. 4. P. 303-319.
Matveev A., Feoktistova V., Bolshakova K. On global near optimality of special periodic protocols for fluid polling systems with setups // Journal of Optimization Theory and Applications. 2016. V. 171, N 3. P. 1055-1070.
Saffer Z., Telek M., Horvath G. Fluid polling system with Markov modulated load and gated discipline // Lecture Notes in Computer Science. 2018. V. 10932. P. 86-102.
Yechiali U., Czerniak O. Fluid polling systems // Queueing Systems. 2009. V. 63, N 12. P. 401-435.
Czerniak O., Altman E., Yechiali U. Orchestrating parallel TCP connections: cyclic and probabilistic polling policies // Performance Evaluation. 2012. V. 69, N 3-4. P. 150-163.

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 km² (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.

References

Stocker, T. F., Qin D., Plattner G.-K., Tignor M., Allen S. K., Boschung J., Nauels A., Xia Y., Вех V. and Midglev P. M. (eds.) Change 2013: The Physical Science Basis. Contribution of Working Group I to the Fifth Assessment Report of the Intergovernmental Panel on Climate Change. Cambridge University Press, Cambridge, United Kingdom and New York, NY, USA. 2013.
Georgiadi A. G., Koronkevich N. I., Milvukova I. P., Kislov A. V., Anisimov O. A., Barabanova E. A., Kashutina E. A., Borodin O. O. Scenarnava ocenka verovatnv'x izmenenij rechnogo stoka v bassejnax krupnejshix rek Rossii. Ch. 1. Bassejn reki Lenv¹. M.: Maks Press, 2011.
Gusev E. M., Nasonova O. N., Dzhogan L. Ya. Fiziko-matematicheskoe modelirovanie mnogoletnej dinamiki sutochnv'x znachenij rechnogo stoka i snegozapasov v bassejne r. Lenv¹ // Vodnv'e resursv¹. 2016. T. 43. N 1. S. 24-36.
Georgiadi A. G., Koronkevich N. I., Barabanova E. A., Kashutina E. A., Milvukova I. P. О vklade klimaticheskix i antropogennv'x faktorov v izmeneniva stoka krupnv'x rek Russkoj ravninv¹ i Sibiri // DAN. 2019. T. 488. N 5. S. 539 511.
Kuzin V. L, Lapteva N. A. Matematicheskoe modelirovanie klimaticheskogo rechnogo stoka iz Ob‘-Irty‘shskogo bassejna // Optika atmosferv¹ i okeana. 2012. T.25. N 6. S. 539-543.
Kuzin V. I., Lapteva N. A. Matematicheskoe modelirovanie stoka osnovnv'x rek Sibiri // Optika atmosferv¹ i okeana. 2014. T. 27. N 6. S. 525-529.
Kanae S., Nishio K., Oki T., Musiake K. Hvdrograph estimations by flow routing modeling from AGCM output in major basins of the world // Annual J. Hydraulic Engineering. 1995. V. 39. P. 97-102.
Oki T., Nishimura T., Dirmever P. Assessment of annual runoff from land surface models using Total Runoff Integrating Pathways (TRIP) // J. Meteorol. Soc. Of Japan. 1999. V. 77, N IB. P. 235-255.
Rienecker M. M.. Suarez M. J., Gelaro R., Todling R., Bacmeister J., Liu E., Bosilovich M. G. et al. MERRA: NASA’s Modern-Era Retrospective Analysis for Research and Applications. // J. Climate. 2011. V. 24. P. 3624-3648. doi:10.1175/JCLI-D-ll-00015.1
(Electron. Res.]: https://gmao.dsfc.nasa.gov/reanalysis/MERRA.
Hagemann S., Dumenil L. A parametrization of the lateral waterflow for the global scale // Climate Dynamics. 1998. V. 14. P. 17-31.
BoLshivanov D. Yu., Makarov A. S., Shnajder V., Shtof G. Proisxozhdenie i razvitie dektv¹ reki Lem". SPb.: A ANIL 2013.
(Electron. Res.]: http://www.r-arcticnet.sr.unh.edU/v4.0/index.html.
Mostaxov S. E. Reka Lena. Yakutsk: Yakut, kn. izd-vo, 1972.
(Electron. Res.]: http://dds.cr.usgs.gov/srtm/version2_l/.
Surfer8. User’s Guide. Contouring and 3DSurfaceMappingforScientist and Engineers. Golden Software Inc., 2002.
Dzh. S. De'vis Statisticheskij analiz dannv'x v geologii. Kn. 2. M.: Nedra. 1990.
Tan Q., Xu X. Comparative analysis of spatial interpolation methods: An experimental study // Sensors k, Transducers Journal. 2014. V. 165, Is. 2. P. 155-163.
Mineev A. L., Kutinov Yu. G., Chistova Z. B., Polyakova E. V. Podgotovka cifrovoj modeli rekefa diva issledovaniva e‘kzogennv‘x processov severnv'x territory Rossijskoj Federacii // Zhurn. Prostranstvo i Vremya.'2015. N 3 (21). S. 278-291.
Mirovoj vodnv'j balans i vodnv'e resursv¹ Zemli. Pod red. Korzun V. I.(pred.) i dr. L.: Gidrometeoizdat. 1974.
Oki T., Sud Y. C. Design of total runoff integrating pathways (TRIP) — a global river channel network // Earth Interactions. 1998. V. 2. P. 1-36.
Krylova A. I., Lapteva N. A. Reproduction of runoff hvdrograph in the Lena River basin with a hydrologicallv correct digital elevation model // Bull. Nov. Comp. Center. Numerical Modeling in Atmosphere, Ocean, and Environment Studies. N 17. 2019. P. 51-58.
Hagemann S., Dumenil Gates L. Validation of the hydrological cycle of ECMWF and NCEP reanalvses using the MPI hydrological discharge model // J. Geophvs. Res. 2001. V. 106. N D2. P. 1503-1510.
Magriczkij D. V. Faktorv¹ i zakonomernosti mnogoletnix izmenenij stoka vodv¹, vzveshennv'x nanosov i teplotv¹ na nizhnej Lene i Vilvue // Vest. Mosk. Un-ta. 2015. Ser. 5. Geografiva. N 6. S. 85-95.
Ye B., Yang D., Kane D. L. Changes in Lena River streamflow hydrology: human impacts versus natural variations // Water Resources Research. 2003. V. 39. N 7, 1200, doi: 10.1029/ 2003WR001991.2003.
Lammers, R. B.; Shiklomanov, A. I.; Vorosmartv, C. J.; Fekete, В. M.; Peterson, B. J. Assessment of contemporary Arctic river runoff based on observational discharge records // J. Geophvs. Res. 2001. V. 106. N D4. P. 3321-3334. doi:10.1029/2000JD900444.
Shamseldin A. Y., O’Connor К. М. Non-linear neural network technique for updating of river flow forecasts // Hydrology and Earth System Sciences. 2001. V. 5. N 4. P. 577-597.
Nash J. E. and Sutcliffe J. V. River flow forecasting through conceptual models. Part 1. A discussion of principles // J. Hydrol., 1970. V. 10. N 3. P. 282-290.
Liang X., Lettenmaier D. P., Wood E. F., Burges S. J. A simple hydrologicallv based model of land surface water and energy fluxes for GCMs // J. Geophvs. Res. 1994. V. 99 (D7). P.14415-14428.
Su F., Adam J. C., Bowling L. C., Lettenmaier D. P. Streamflow simulations of the terrestrial Arctic domain // J. Geophvs. Res. 2005. V. 110. N D08112. doi:10.1029/2004JD005518.
Gusev E. M., Nasonova O. N. Modelirovanie processov teplovlagoobmena sushi s atmosferoj v lokabnom masshtabe diva territorij s mnogoletnej merzlotoj // Pochvovedenie. 2004. N 9. S. 1077-1092.
Gusev E. M., Nasonova O. N. Modelirovanie teplo i vlagoobmena poverxnosti sushi s atmosferoj. M.: Nauka, 2010.
Apollov B. A., Kalinin G. P., Komarov V. D. Kurs gidrologicheskix prognozov. L.: Gidrometeoizdat. 1974

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

Main menu

You are here

2020 № 4(49)

Languages