2018 № 1(38)



Kasyanov V.N., Kasyanova E.V.

A. P. Ershov Institute of Informatics Systems SD RAS,630090, Novosibirsk, Russia
Novosibirsk State University, 630090, Novosibirsk, Russia


UDC 004

Graphs are used almost everywhere in computer science. Any system that consists of discrete states (or sites) and connections between them can be modeled by a graph. For a long time among different formats being used for presentation of graphs was not a single one that would be widely accepted as the standard format. As a rule tools to work with graph models supported different graph formats, usually consisting of restricted subclasses of graphs and their representations.

Motivated by the goals of tool interoperability, access to benchmark data sets, and data exchange over the Web, the Steering Committee of the Graph Drawing Symposium started a new initiative with an informal workshop held in conjunction with the 8th Symposium on Graph Drawing. As a consequence, an informal task group was formed to propose a modern graph exchange format suitable in particular for data transfer between graph drawing tools and other applications. The main goal of the GraphML language has been formulated by the developers in the following way. The graph exchange format should be able to represent arbitrary graphs with arbitrary additional data, including layout and graphics information. The additional data should be stored in a format appropriate for the specific application, but should not complicate or interfere with the representation of data from other applications.

GraphML is designed with this and the following more pragmatic goals in mind:

1) Simplicity: The format should be easy to parse and interpret for both humans and machines. As a general principle, there should be no ambiguities and thus a single well-defined interpretation for each valid GraphML document.
2) Generality: There should be no limitation with respect to the graph model, i.e. hypergraphs, hierarchical graphs, etc. should be expressible within the same basic format.
3) Extensibility: It should be possible to extend the format in a well-defined way to represent additional data required by arbitrary applications or more sophisticated use (e.g., sending a layout algorithm together with the graph).
4) Robustness: Systems not capable of handling the full range of graph models or added information should be able to easily recognize and extract the subset they can handle.

Designed GraphML language for descriptions of graphs is based on XML. It allows describing directed, undirected and mixed graphs, hyper graphs and hierarchical graphs, as well as any specific attributes for specific applications. In particular, GraphML language fully supports attributed hierarchical graphs [17]. Thanks to its XML syntax, GraphML can be used in combination with other XML based formats. On the one hand, its own extension mechanism allows attaching <data> labels with complex content (possibly required to comply with other XML content models) to GraphML elements. Examples of such complex data labels are Scalable Vector Graphics describing the appearance of the nodes and edges in a drawing. On the other hand, GraphML can be integrated into other applications, e. g. in SOAP messages.

In this paper, only the basic tools of the GraphML language are described, which are sufficient to represent graph models in most applications. It discusses how graphs and graph data can be represented in GraphML format using a basic graph model that covers graphs containing directed and undirected edges, loops, multiple edges, and various labels (attributes) of nodes, edges, and graphs.

The work has been partially supported by the Russian Foundation for Basic Research under grant N 15-07-02029.

Key words: graph, graph data, graph model, GraphML.

Bibliographic reference: Kasyanov V.N., Kasyanova E.V. Representation of graphs and graph models: basic tools of the graphml language //journal “Problems of informatics”. 2018, № 1. P. 4-19.


 Rane D., Shakhov V.*, Srivastava A.

Indian Institute of Technology Indore, 453552, Indore, India
*Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia


UDC 004.75

Wireless sensor networks with cloud computing are drivers to a new stream of technologies like the Internet of Things and innovations in the communications. Cloud computing triumphs with multifaceted benefits to enterprises with cost saving economics, reduced operational, and support costs but higher productivity. The significant functionality of data collected and processed at wireless sensor nodes is rendered fast, uninterrupted and reliably with cloud computing and its optimized implementations. Therefore, sensor network firms are partnering with cloud service providers, which lease computing infrastructure as required. This paper suggests a model for optimizing the computing potential of the wireless sensor network in conjunction with the pricing model of the cloud. Integration of concepts of cloud and sensor networks takes the advantage of the scalable and dynamic aspect of cloud being exploited for sensory data. The results show that the proposed method adapts well with performance expectations of sensor networks and reduces the cost specific overheads for its largely processing based functioning. In order to facilitate the selection of appropriate cloud service provider, with a provision of dynamic pricing and assurance to optimize the final cost, Cloud Broker Pricing Model (CBPM) is proposed.

CBPM mainly offers a pricing band to a consumer, which assures that the charged price at any moment, will not beyond the limits of the band. This way, it offers the benefit of dynamic pricing with as well as the confirmation related to the highest price that can be charged. Moreover, the proposed system gives the freedom to utilize the services newly introduced by some another provider. Further, dynamic pricing on the basis of QoS is transparent for both sensor network cloud provider and consumer, however, if this pricing is decided manually or through pre-defined rules then the pricing scheme will be very complicated. Such pricing needs proper and regular analysis over complete monitored data and weighing of some features to seek importance of one feature over another. Therefore, as future work an advanced algorithm can be developed having the capability to continuously analyze a large amount of data through big data analytics and hence making optimized pricing decisions.

There are few situations in which CBPM may not be useful as expected for wireless sensor networks. In the case of a very frequent change in demand for a computing resource, the system will indulge into the consistent migration of VMs, yielding no work but still paying the cost of migration. As a consequence, the system performance will also downgrade, where the system is greedy and decides to migrate to optimize the total cost. Further, there are issues in migration that needs to be handled. Therefore, as further research in cloud broker pricing model, authors recommend modeling a robust pricing model, capable enough to manage the frequent fluctuations in demand. Further, the behavior of inseparability of computing resources may lead to utility functions producing sub-optimal assignment. Measures should be taken in future work to address this issue as well.

Key words: Cloud computing, dynamic pricing, pricing band, pricing analysis, Cloud Broker Pricing Model.

Bibliographic reference:  Rane D., Shakhov V., Srivastava A. CBPM: a dynamic pricing model for cloud-based sensing infrastucture //journal “Problems of informatics”. 2018, № 1. P. 20-41.


Zlotnikova R.E.

Novosibirsk State Technical University,  630073, Novosibirsk, Russia


UDC 004.73:004.77

There is the common problem with all current fatal diseases. Nowadays many people experience the symptoms and have disease diagnosed when it is too late. Scientists investigated the way that most diseases can be prevented. They found out that well-timed detection could save many people and their health. This is the obvious reason to provide future health care systems with proactive wellness management and concentrate on early detection and prevention of diseases. Body area monitoring system is a good way to achieve more affordable and proactive health care system. Due to using such compact system monitoring vital signals allows patients to continue their normal activities instead of staying at home or in a hospital. Such kind of network consists of intelligent, low-power, micro and nano-technology sensors and actuators, which can be placed on the body, or implanted in the human body (or even in the blood stream), providing timely data. Such networks are commonly referred to as Wireless Body Area Networks. In addition to saving lives, use of WBANs will decrease health care costs by removing the need for costly in-hospital monitoring of patients.

WBANs interact through the Internet and other existing wireless technologies like ZigBee, WSNs, Bluetooth, Wireless Local Area Networks (WLAN), Wireless Personal Area Network (WPAN), video surveillance systems and cellular networks. Marketing potential for services and advanced consumer electronics will thoroughly spread out, allowing for a new generation of more intelligent and autonomous applications.
WBANs are intended for transforming how people interact with and benefit from information technology. WBAN sensors are capable of sampling, monitoring, processing and communicating various vital signs without causing any discomfort. The use of a WBAN allows all day long monitoring of one’s physiological parameters thereby providing greater mobility and flexibility to patients. As WBANs provide large time intervals of data from a patient’s natural environment, doctors will have a clearer view of the patient’s status. These facilities offer various system design and implementation opportunities with the major objectives of minimum delay, maximum throughput, maximum network lifetime and and reducing unnecessary communication related energy consumption (e. g. control frame overhead, idle listening and frame collisions). The user-oriented requirements of WBANs are equally challenging and have been defined as: ease of use, security, privacy, compatibility, value and safety.

There are few main communication standard solutions considered as reference are: IEEE 802.15.4, IEEE 802.15.6, and Bluetooth Low Energy. IEEE 802.15.4 (published in 2006), specifies the physical (PHY) and medium access control (MAC) layers for short-range wireless communications, devised to support low power, low cost, and low bit rate networks. The IEEE 802.15.6 (published in 2012), was specifically designed for wireless communications in the vicinity of, or inside, a human body. Finally, Bluetooth Low Energy (BT LE) (published in 2010) is the ultra-low power consumption configuration of Bluetooth technology, targeting several applications for small and cheap devices powered by button-cell batteries, such as wireless sensors. Due to the quite large number of available standards, it is necessary to identify the best solution, depending on the application requirements. For what concerns the main issues to be accounted for in the design of a WBAN, the impact of wireless medium, the battery lifetime and the coexistence with other wireless networks are of fundamental importance. The presence of the human body affects the radio wave propagation, leading to a specific and peculiar radio channel, which has to be properly accounted for in the design of the protocols. The need for long battery lifetime shall be addressed through energy efficient solutions since frequent battery replacements must be avoided, being a very hard task in some application (e.g., medical applications where nodes are implanted). The third main issue to be taken into account is the outage occurrence due to coexistence with other wireless networks operating in the same frequency band. As it will be remarked later in the paper, many standard solutions for WBAN operate in the licence-free Industrial Scientific and Medical (ISM) band centered at 2.45 GHz and this leads to coexistence issues with other networks operating in the same band (e.g., Wi-Fi IEEE 802.11).

Wireless body-area networks offers the possibility to reach a totally new level of communications, with particular propagation characteristics that differentiate the body-area-network channel from many other radio-propagation channels.

Key words: wireless networks, Wireless Networking Technologies, Wireless body area networks, monitoring, sensors, classification, topology, System requirements, power consumption.

Bibliographic reference:  Zlotnikova R.E. Overview of wireless body area networks //journal “Problems of informatics”. 2018, № 1. P. 42-66. 


Malyshkin* V.E., Schukin G.A.

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


UDC 004.021

The paper presents a scalable distributed algorithm for dynamic data allocation in LuNA fragmented programming system. The proposed algorithm is optimized for data lattice distribution on a grid network topology. The algorithm takes into account data structure of the application numerical model executed and enables dynamic load balancing.
Implementation of numerical models on multicomputers with large number of computing nodes is a challenging problem in the domain of high-performance parallel computing. Effective resources allocation and balancing strategies are necessary to achieve good efficiency and scalability of parallel programs. LuNA is a fragmented programming system which is being developed in Supercomputer Software Department of Institute of Computational Mathematics and Mathematical Geophysics SB RAS. LuNA’s main objective is automation of construction of parallel programs, which implement large-scale numerical models for large-scale multicomputers.

In LuNA system an application algorithm is represented as two sets: a set of immutable data pieces (data fragments, DF) and a set of side-effect free computational processes (computational fragments, CF). All these fragments can be distributed over computational nodes of a multicomputer. Each DF is produced by one CF and can be used as an input by other CFs; each CF is executed only once and requires values of all its input DFs to be gathered on a single node for its execution. Execution of a program is managed by LuNA’s runtime system. The runtime system performs distribution and migration of DFs and CFs over nodes of a multicomputer and deliverance of input DFs to their corresponding CFs to provide execution of all CFs in the program.
Efficiency of LuNA program execution (in terms of running time, memory consumption, communications amount, etc.) heavily depends on quality of CFs and DFs distribution. LuNA’s runtime system may use different algorithms for data distribution and load balancing. First, algorithm Rope was developed, which supported distribution of a general data structures on a one-dimensional grid network. One of requirements of a quality data distribution is data locality, i.e. dependent data fragments should be allocated on the same or neighbor nodes to minimize communications. To improve data locality for multidimensional data lattices on multidimensional grid networks, new Patch algorithm was developed.

As in Rope algorithm, Patch uses mapping of data fragments to intermediate coordinates. The mapping is a constant function during execution of a program, thus it can be computed on any node without communications. Each coordinate is represented as a cell, and all coordinates are represented as a mesh of cells. That intermediate mapping is to account data dependencies: dependent (neighbor) data fragments should be mapped to the same or neighbor cells; that way they will be distributed on the same or neighbor nodes. The cell mesh is split on cell domains, each node receives its own cell domain. Each data fragment is allocated on the node containing cell to which its is mapped. Each cell stores information about current location (node) of all cells adjacent to it in the cell mesh. With this information it is possible to find a location of any cell from any node, using only local communications between nodes. This search is used for initial data fragment allocation and also to serve requests for data fragments from computational fragments.
For the purpose of dynamic load balancing mapping of cells to nodes can be changed. Migration of workload is accomplished by migration of cells between cell domains. Migration of cells causes migration of actual data fragments, mapped to these cells, and subsequent change of workload. To organize exchange of workload, diffusion scheme is used. All nodes are organized into overlapping groups, each group consisting of main node and its neighbors. Each node knows its own workload and workload of its neighbors in a group. Formulas for workload evaluation can be different, for example value of workload can be proportional to a volume of memory occupied by data on the node. Workloads of neighboring nodes are compared periodically; if the main node is overloaded (its workload exceeds average workload of the group by some threshold), it migrates cells to underloaded nodes. Only cells on domains’ borders are eligible for migration, i.e. ordering of cells’ coordinates isn’t changed after migration. That way data locality is preserved during dynamic load balancing.

Usage of only local communications for data allocation and load balancing makes proposed algorithm scalable to a large number of computational nodes, because no global synchronization (that can impede scalability) is used.

Testing of Patch algorithm has shown improvements over Rope algorithm, both in average length of communications between nodes in a topology and in average volume of transmitted data. Further development, testing and optimization of the algorithm are planned.

Key words: scalable distributed system algorithm, dynamic data allocation, distributed algorithms with local interactions, fragmented programming technology, fragmented programming system LuNA.

Bibliographic reference: Malyshkin V.E., Schukin G.A. Distributed algorithm of multidimensional data lattice distribution on multidimensional multicomputer in the LuNA fragmented programming system // journal “Problems of informatics”. 2018, № 1. P. 67-80.