Software & Systems

Articles of journal № 2 at 2018 year.

Order result by: Public date | Title | Authors

1. Adaptive algorithm for optimal route search in time-dependent network [№2 за 2018 год]
Author: Soldatenko A.A.
Visitors: 8057
The Time-Dependent Shortest-Path problem (TDSP) is an extension of the shortest path problem in a graph. TDSP problem arises when designing and operating telecommunications and transport networks. Such networks require considering time and possibility of appearing predictable situations for example traffic jams or traffic reduction. In this case, network is represented with an oriented graph G = (V, E) where for each arc (x, y)  E, two functions are defined. First function is time required for moving along the arc (x, y). Second function is arrival time in vertex y if the movement started from vertex x in time t. Such graph is called time-dependent network. The minimum time for moving from vertex x to vertex y is an optimal route between these vertices. It is known that TDSP for a general time-dependent network without any restrictions on network topology or arrival function is NP-hard. When arrival function satisfies FIFO (First-In First-Out) condition, TDSP problem is polynomially solvable. This paper studies TDSP problem for a polynomial case when arrival functions are monotonous. It is proposed to solve TDSP problem using a two-phased algorithm ALT (A* with Landmarks & Triangle). ALT algorithm is one of the modern least cost routing algorithms originally developed for solving the problem of the shortest path in a graph. In the first phase, ALT algorithm places landmarks in network vertices and calculates potential functions. In the second phase it finds the exact value of an optimal route in a graph with A* algorithm. The paper proposes modification of ALT algorithm which is capable of correct and efficient solving the TDSP problem for a sequence of queries for searching for optimal routes in a time-dependent network. The modification consists in using adaptive heuristic for landmark placement and special formulas for calculating potential functions. This heuristic uses experience of processing all completed queries; adapts current set of landmarks for next queries. There is a description of the modified ALT algorithm and estimation of its working time. The paper also gives a description of the software that implements the proposed algorithm. The results of computational experiments confirm the effectiveness of the modified ALT algorithm.

2. The algorithm for recognizing situations in a distributed video surveillance system [№2 за 2018 год]
Authors: A.Yu. Kruchinin, D.V. Kolmykov, R.R. Galimov
Visitors: 6125
CCTV systems are the most important means for preventing and timely handling of contingencies, such as crimes, emergency situations. A big number of cameras and a large control area makes it necessary to introduce video analytics to recognize dangerous situations. In this case it is necessary to take into account the data from a number of video cameras both for detecting a motion path of a recognized object and for increasing recognition reliability. The article proposes an algorithm for recognizing emergencies for a distributed video surveillance system based on stochastic grammars. Recognition of a situation occurs at 3 levels: images are recognized at the lower level, events are recognized at the average level, and situations are recognized at the top. To reduce the system response time, it is proposed to use a multi-agent architecture that allows distributing the load between intelligent cameras. Data exchange occurs only between nearby nodes, so network traffic reduces. The use of a large number of cameras involves zones controlled by several nodes. Combination of detection results from several cameras makes it possible to increase the estimate reliability. However, it is required to know the mutual arrangement of chambers and the angles of their turns. The article suggests some methods for automatic calibration of cameras in a distributed video surveillance system, ways of combining images from different cameras, in particular, based on speed rate vectors of objects. Taking into account certain features of a distributed video surveillance system, there is a developed algorithm for recognizing emergencies for an intelligent surveillance camera. Each camera generates probable situations based on previously recognized events. When a threshold value of probabilistic evaluation of the detection result is exceeded, its refinement is carried out in the process of interaction with neighboring nodes.

3. Algorithmic support of the information system for managing innovation projects in an industry [№2 за 2018 год]
Author: M.V. Chernovalova
Visitors: 7585
Current approaches to project management are focused on the consistent implementation of all phases. They do not take into account the influence of the results obtained earlier and uncertainty factors on innovation project performance indicators and the degree of its feasibility. The paper considers two algorithms that are aimed at solving these problems. The first algorithm takes into account the influence of uncertainty factors on innovation project work duration and implementation costs. A key feature of this algorithm is a system of fuzzy production rules to determine possible deviations of the results of individual project works from the set indicator values. When managing an innovative project, this allows taking into account external and internal uncertainties while minimizing innovation costs. The second algorithm is focused on minimizing the duration of a project or resource costs. The basis for this algorithm is the List Scheduling algorithm. It differs by using fuzzy production rules to provide efficient allocation of available resources depending on the set values of performance indicators, as well as forecasting performance time of a particular work with the allocated resource level. The article also presents the architecture of the proposed information system for project management. It implements the described algorithms and shows the main modules and data flows between them. It is focused on the complex automation of the process of managing innovative projects.

4. Algorithmic software of software maintenance complex controlling the reliability level of flight facilities [№2 за 2018 год]
Authors: Dopira R.V., V.A. Dikarev, Potapov A.N., E.E. Bueshev, I.A. Yuriev
Visitors: 5856
Improvement of technical means complexes is related to the need for research on extending the life of equipment while reducing operational costs. One of the ways of improving qualitative indicators of a technical condition (TC) of such complexes throughout their life cycle while reducing operational costs is the transition to technical service (TS) with pe-riodical inspection. Nowadays when using automated control systems (management information systems), maintenance methods with periodic monitoring that consider the actual condition of the equipment are becoming more and more popular. It should be noted that none of the methods is implemented without the prevention; each of them has its specificity when determining the timing and amount of preventive maintenance. To solve of the problem of determining rational frequency using statistical projections successfully, the paper proposes algorithmic support for software maintenance complex controlling the level of reliability of flight facilities. In this case, the developers of an algorithm took into account the volume and frequency of maintenance. The developed algorithm is implemented as a software complex, which allows determining optimal periods of maintenance. The algorithm efficiency is verified based on functioning of the automated workplace of a near zone head to control the engineering status of radio facilities. According to the engineering status, the software package determines the optimal maintenance periods for technical means complexes.

5. Extracting a data schema from the SPARQL endpoint [№2 за 2018 год]
Authors: А.О. Mochalov, Muromtsev D.I.
Visitors: 5621
The paper is devoted to the problem of extracting a data schema from the SPARQL endpoint. The data schema is necessary for writing queries and searching information, as well as for optimizing query execution. The paper considers the existing methods for extracting schemes, notes minuses and pluses of each method. It defines the notion of a data schema to develop own method. A data schema is a dictionary of all triplets, where the predicates are all fixed predicates from the RDFS namespace, as well as triplets that logically follow from the dataset according to RDFS semantics, except for triplets that are elements of well-known dictionaries (RDF, RDFS, Void, OWL, XML Schema, XSD). The elements from the SPARQL endpoint schema will be retrieved using RDFS rules. The work does not use all RDFS semantics rules as not all rules return the elements of the schema according to the definition of the data scheme adopted in this paper. The paper describes the developed method in detail and presents its architecture. It uses the business rules management system Drools to work with inference rules. The paper presents the advantages and disadvantages of the developed method that showed the expected test results. It it noted that the number of classes and properties can be different for the schemes developed and obtained by the developed method. This is only due to the fact that the developed method uses RDF rules.

6. Continuous execution of system dynamics models on input data stream [№2 за 2018 год]
Authors: I.А. Perl, М.М. Petrova, А.А. Mulyukin, О.V. Kalenova
Visitors: 6303
This article describes a new approach to system dynamics models execution. In most cases when model execution is involved, the input data is a set of static and known data. It is expected that on the model output modeler will get a set of other system or event characteristics computed by the model based on the input parameters. This approach is still used widely in different industries, but it is not the only scenario. With growing popularity of some concepts such as the Internet of Things, the demand on modeling-based solutions, which take continuous data streams as input, has grown significantly. In comparison with stand-alone client-side modeling systems, cloud-based solutions, such as sdCloud, became a reasonable answer to the industry request. Such systems can provide an ability of continuous execution of system dynamics models. In other words, these systems are ready to accept an incoming data stream and perform model execution that will result in streaming modeling results back to the end-user. Running system dynamics models in parallel with the describing process allows performing predictive modeling of the system status in the future. It also allows finding additional hidden external impacts to the model. For example, such approach can be a base for predictive maintenance of complicated technical systems, because it allows computing nearest maintenance time more efficiently.

7. On the issue of assessing stability of functioning of communication network elements [№2 за 2018 год]
Author: Popkov G.V.
Visitors: 5625
The article considers the issues of assessing stability of power grid functioning to destructive destabilizing influences (DDI). The proposed method represents an attacked telecommunication network as dynamic hyper network that allow objective assessing an attacked network state in the context of stability. The author introduces a concept of DDI and the related concept of a DDI channel that affects NE elements of a communication network at different levels of hyper network models. Simplicity and convenience of representing an attacked network in the form of dynamic hyper networks makes it possible to extend the class of problems related to determining stability of communication networks to external destructive influences, in particular, to find correlation links between private intruder models, attack models and vulnerability models of a power grid at the investigated level. Such approach allows designing stable communication networks taking into account dynamically changing external factors connected with threats directed to a communication network structure. It also allows effective detecting and blocking threats related to external information influences while ensuring accessibility, integrity, confidentiality of user information. Due to the proposed approaches, it seems appropriate to create knowledge ontologies based on a network response to DDI at network monitoring points, which in turn will effectively design and install information protection tools in real network structures. The author proposes a private mathematical model of external destabilizing influence, which is based on the probability theory. It makes it possible to trace dynamic changes in a network structure and determine quantitative estimates of QoS applications.

8. A method of automated development of the semantic dialogue system database model [№2 за 2018 год]
Author: Posevkin R.V.
Visitors: 7270
The paper considers the problem of intellectual database content analysis for creating a semantic database model. Voice assistants are created to simplify interaction with mobile devices such as smartphones and tablets. A text dialogue system is an analogue of this approach. As a result, user can interact with software using natural language. User interface is a set of software solutions that helps to search, review, obtain and process information from a database that is external storage. Natural language interface is a sort of user interface that accepts and processes natural language queries. This interface can also use natural language in output to show found information to a user. A semantic database model is an important part of the dialogue system. This model includes interconnections and internal structure of a database. Manual creating of a semantic database model significantly increases time and labour costs, as well as development cost of a software system. The main purpose of the article is automation of development of a dialogue system semantic database model. The proposed method uses a set of approaches to automated creating of an existing database semantic model. An object domain thesaurus helps to define semantics and solve the problem of polysemy in text processing. Patterns helps to extract interconnections in a database. The analysis of database field content allows determining data semantic and nature. Locale indication allows decreasing the time for a database content analysis.

9. A method for determining the capabilities of parallel execution of data mining algorithm functions [№2 за 2018 год]
Author: I.I. Kholod
Visitors: 5843
The article describes the method for determining the possibility of parallel execution of data mining algorithm functions. The input parameters of the method are: a data mining algorithm represented as a composition of thread-safe functions, and a mining model represented as an array of unified element trees describing the patterns mined by the algorithm. When determining the possibilities of parallelization, the method takes into account information dependencies between functions, which are determined by a set of used and modifiable elements of a mining model. The method analyzes data connections for each pair of algorithm functions when testing the possibility of task parallelization, as well as for calling functions in loops for different iterations, while verifying the possibility of data parallelization. The analysis includes checking necessary and sufficient conditions for parallel execution for systems with shared and distributed memory. They extend the Bernstein conditions used in compiler theory and are sufficient, but not necessary. The method determines the possibilities of parallel execution of functions for shared memory systems and distributed memory systems. In this case, parallel performance of functions in shared memory systems is more efficient due to the lack of calls for the cloning function and combining of mining models. The result of the proposed method is the parallel form of the source data analysis algorithm. It contains insertions of special functions of higher order that provide parallel execution of algorithm functions that satisfy necessary and sufficient conditions. To illustrate the proposed method, the paper shows parallelizing 1R classification algorithm. It defines algorithm functions that can be paralleled, both by data and by tasks. The result is a parallel form of the 1R algorithm with parallelization function inserts for shared memory systems and distributed memory systems.

10. A methodical approach to modeling of complex technical system support with spare parts [№2 за 2018 год]
Authors: D.Yu. Brezhnev, Dopira R.V., A.A. Sudarikov
Visitors: 6654
The article considers a methodical approach to constructing a model of a multilevel system for providing spare parts for complex technical systems. The model is designed to justify a quantitative and nomenclature composition of spare parts kits considering the requirements for efficiency of performance restoration of the equipment samples in the system. The key idea is to put the simulated flow of requests to the model input and to investigate the response of a spare parts system by modeling the time for fulfillment of requests from sets of spare parts, tools of various levels, gradually increasing their nomenclature and quantity composition. At the same time, the simulated stream of requests can be different from the simplest one. It allows reasonable distributing applications for spare parts between sets of spare parts, tools of various levels. The model provides for the possibility of using one of three strategies for replenishment of spare parts kits both in the maintenance system of spare parts and in the specific nomenclature of spare parts in particular. The principle of modular representation of spare parts sets allows modeling a system of providing spare parts in different versions of a single-level or multi-level structure depending on application conditions or the principles of constructing complex technical systems. Modeling takes into account the contribution of each spare part cost to the total cost of the spare parts maintenance system with restriction for the required delay time related spare parts delivery. As a result, it is possible to justify the composition of spare parts kits of a complex technical system in an optimal way.

| 1 | 2 | 3 | Next → ►