2018 № 1(38)

Kasyanov V.N., Kasyanova E.V. REPRESENTATION OF GRAPHS AND GRAPH MODELS: BASIC TOOLS OF THE GraphML LANGUAGE
Rane D., Shakhov V., Srivastava A. CBPM: A DYNAMIC PRICING MODEL FOR CLOUD-BASED SENSING INFRASTUCTURE
Zlotnikova R.E. OVERVIEW OF WIRELESS BODY AREA NETWORKS
Malyshkin V.E., Schukin G.A. DISTRIBUTED ALGORITHM OF MULTIDIMENSIONAL DATA LATTICE DISTRIBUTION ON MULTIDIMENSIONAL MULTICOMPUTER IN THE LuNA FRAGMENTED PROGRAMMING SYSTEM

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

REPRESENTATION OF GRAPHS AND GRAPH MODELS: BASIC TOOLS OF THE GraphML LANGUAGE

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.

References

1. Kasyanov V. N., Evstigneev V. A. Grafy v Programmirovanii: Obrabotka, Vizualizatsiia i Primenenie [Graphs in Programming: Processing, Visualization and Application]. St. Petersburg: BHV Petersburg, 2003.
2. Kasyanov V. N., Kasyanova E. V. Vizualizatziia Grafov i Grafovuh Modelej [Visualization of Graphs and Graph Models] Novosibirsk: Siberian Scientific Publishing House, 2010.
3. Di Battista G., Eades P., Tamassia R., Tollis I. G. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
4. Borgatti S. P., Everett M. G., and Freeman L. C. UCINET 6.0 , Analytic Technologies, 1999.
5. De Nooy W., Mrvar A., and Batagelj V. Exploratory social network analysis with Pajek. Cambridge University Press, 2005.
6. Winter A. Exchanging Graphs with GXL, Lecture Notes in Comput. Sci. 2002. Vol. 2265. P. 485–500. (Proc. 9th Int. Symp. Graph Drawing GD’2001).
7. Tsvetovat M., Reminga J., and Carley K. Dynetml: interchange format for rich social network data, NAACSOS Conference. Pittsburgh, PA, 2003.
8. GML. The Graph Modeling Language File Format. [Electron. Res.]: www.infosun.fmi.uni-passau.de/Graphlet/GML/.
9. Brandes U., Marshall M. S., North S. C. Graph data format workshop report, Lecture Notes in Comput. Sci. 2001. Vol. 1984. P. 410–418. (Proc. 8th Int. Symp. Graph Drawing GD’2000).
10. Brandes U., Eiglsperger M., Herman I., et al. GraphML progress report: structural layer proposal, Lecture Notes in Comput. Sci. 2002. Vol. 2265. P. 501–512. (Proc. 9th Int. Symp. Graph Drawing GD’2001).
11. Brandes U., Eiglsperger M., Lerner J. GraphML Primer. [Electron. Res.]: graphml.graphdrawing.org/primer/graphml-primer.html#EXT.
12. Brandes U., Eiglsperger M., Lerner J., Pich C. Graph markup language (GraphML). [Electron. Res.]: www.cs.brown.edu/~rt/gdhandbook/chapters/graphml.pdf.
13. W3C. Scalable Vector Graphics. [Electron. Res.]: www.w3.org/TR/SVG/.
14. W3C. SOAP. [Electron. Res.]: www.w3.org/TR/soap12-part0/.
15. Kasyanov V. N. Yazyk predstavleniya grafov GraphML: dopolnitel’nye vozmozhnosti, Informatika v nauke i obrazovanii [The GraphML language for graph presentation: additional tools, Informatics in science and education]. Novosibirsk: IIS SB RAN, 2012. P. 7–22.
16. Evstigneev V. N., Kasyanov V. N. Tolkovyj slovar’ po teorii grafov v informatike i programmirovanii [Explanatory Dictionary of Graph Theory in Computer Science and Programming]. Novosibirsk: Nauka Publ., 1999.
17. Kasyanov V. N., Zolotuhin T. A. Visual Graph — sistema dlya vizualizacii slozhno strukturirovannoj informacii bol’shogo ob"ema na osnove grafovyh modelej, Nauchnaia vizualizatsiia [Visual Graph – a system for visualization of big size complex structural information on the base of graph models, Scientific Visualization]. 2015. Vol. 7, N 4. P. 44–59.
18. Sugiyama K., Tagawa S., Toda M. Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man and Cybernetics. 1981. Vol. 11. N 2. P. 109–125.

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.

article

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

CBPM: A DYNAMIC PRICING MODEL FOR CLOUD-BASED SENSING INFRASTUCTURE

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.

References

1. Botts, Mike and Percivall, George and Reed, Carl and Davidson, John. OGCA Sensor Web Enablement: Overview and High Level Architecture // GeoSensor Networks: Second International Conference, GSN 2006, Boston, MA, USA, October 1–3, 2006, Revised Selected and Invited Papers. Springer Berlin Heidelberg, 2008. P. 175–190.
2. Mell, Peter and Grance, Tim. The NIST definition of cloud computing // Computer Security Division, Information Technology Laboratory, National Institute of Standards and Technology Gaithersburg. 2011.
3. Fox, Armando and Griffith, Rean and Joseph, Anthony and Katz, Randy and Konwinski, Andrew and Lee, Gunho and Patterson, David and Rabkin, Ariel and Stoica, Ion. Above the clouds: A Berkeley view of cloud computing. Dept. Electrical Engineering and Computer Sciences, University of California, Berkeley, Rep. UCB/EECS. 2009. V. 28. N 13.
4. Intacct Corporation. Moving to the Cloud: Understanding the Total Cost of Ownership. 2011.
5. Buyya, Rajkumar and Ranjan, Rajiv and Calheiros, Rodrigo N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit: Challenges and opportunities // International Conference on High Performance Computing & Simulation, 2009. HPCS’09. IEEE. P. 1–11.
6. Gartner [Electron. Resource]: http://www.gartner.com/it-glossary/cloud-services-brokerage-csb/.
7. Supply on demand: Adapting to change in consumption and delivery models // The Economist. 2013. [Electron. Resource. Accessed 11-November-2016]: https://www.eiuperspectives.economist.com/sites/default/files/EIU_Zuora_....
8. Al-Roomi, May and Al-Ebrahim, Shaikha and Buqrais, Sabika and Ahmad, Imtiaz. Cloud computing pricing models: A survey // International Journal of Grid & Distributed Computing. Citeseer, 2013. V. 6. N 5. P. 93–106.
9. Gabriel Bitran and Rene Caldentey. An Overview of Pricing Models for Revenue Management // Manufacturing and Service Operations Management. 2003. V. 5. N 3. P. 203-229.
10. Amazon EC2 spot request volatility. [Electron. Resource. Accessed 19-January-2016]: https://moz.com/devblog/amazon-ec2-spot-request-volatility-hits-1000hour/.
11. M. Yousif. A Plethora of Challenges and Opportunities // IEEE Cloud Computing. 2014. V. 1. N 2. P. 7–12.
12. Sharma, Bhanu and Thulasiram, Ruppa K. and Thulasiraman, Parimala and Garg, Saurabh K. and Buyya, Rajkumar. Pricing Cloud Compute Commodities: A Novel Financial Economic Model // Proc. of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2012). IEEE Computer Society, 2012. P. 451–457.
13. Agmon Ben-Yehuda, Orna and Ben-Yehuda, Muli and Schuster, Assaf and Tsafrir, Dan. Deconstructing Amazon EC2 spot instance pricing // ACM Transactions on Economics and Computation. ACM, 2013. V. 1. P. 16.
14. Buyya, Rajkumar and Abramson, David and Giddy, Jonathan and Stockinger, Heinz. Economic models for resource management and scheduling in Grid computing // Concurrency and Computation: Practice and Experience. 2002. V. 14. P. 1507–1542.
15. Abramson, David and Buyya, Rajkumar and Giddy, Jonathan. A Computational Economy for Grid Computing and Its Implementation in the Nimrod-G Resource Broker. Future Generation Computer Systems. Elsevier Science Publishers B. V. 2002. V. 18. P. 1061–1074
16. Gunther Stuer and Kurt Vanmechelen and Jan Broeckhove. A commodity market algorithm for pricing substitutable Grid resources // Future Generation Computer Systems. 2007. V. 23. 688–701.
17. Caracas, Alexandru and Altmann, Jörn. A Pricing Information Service for Grid Computing // Proc. of the 5th International Workshop on Middleware for Grid Computing: Held at the ACM/IFIP/USENIX 8th International Middleware Conference. ACM, 2007. P. 4:1–4:6.
18. Chee Shin Yeo and Srikumar Venugopal and Xingchen Chu and Rajkumar Buyya. Autonomic metered pricing for a utility computing service // Future Generation Computer Systems. 2010. V. 26. N 8. P. 1368–1380.
19. Roovers, Joris and Vanmechelen, Kurt and Broeckhove, Jan. A Reverse Auction Market for Cloud Resources // Proceedings of the 8th International Conference on Economics of Grids, Clouds, Systems, and Services. Springer-Verlag, 2012.
20. Barkha Javed and Peter Bloodsworth and Raihan Ur Rasool and Kamran Munir and Omer Rana. Cloud Market Maker: An automated dynamic pricing marketplace for cloud users // Future Generation Computer Systems. 2016.V. 54. P. 52–67.
21. Y. M. Teo and M. Mihailescu. A Strategy-proof Pricing Scheme for Multiple Resource Type Allocations // International Conference on Parallel Processing, 2009. ICPP ’09. 2009. 172–179.
22. M. Mihailescu and Y. M. Teo. Dynamic Resource Pricing on Federated Clouds // 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid). 2010. 513–517.
23. Karunakaran, Sowmya and Krishnaswamy, Venkataraghavan and Sundarraj, R. P. Service Research and Innovation: Third Australian Symposium, ASSRI 2013, Sydney, NSW, Australia, November 27-29, 2013, Revised Selected Papers // Decisions, Models and Opportunities in Cloud Computing Economics: A Review of Research on Pricing and Markets. Springer International Publishing, 2014. P. 85–99.
24. Li, Chu Fen. Cloud Computing System Management Under Flat Rate Pricing // Journal of Network and Systems Management. 2011. V. 19. N 3. P. 305–318.
25. Macìas, Mario and Guitart, Jordi. A Genetic Model for Pricing in Cloud Computing Markets // Proceedings of the 2011 ACM Symposium on Applied Computing. ACM, 2011. P. 113–118.
26. Wu, Shin-yi and Banker, Rajiv D. Best pricing strategy for information services // Journal of the Association for Information Systems . 2010. N 3. V. 11. P. 339–366.
27. Jianhui Huang and Robert J. Kauffman and Dan Ma. Pricing strategy for cloud computing: A damaged services perspective // Decision Support Systems. 2016. V. 78. P. 80–92.
28. Chun S., Choi B., Ko Y., Hwang S. Frontier and Innovation in Future Computing and Communications // The Comparison of Pricing Schemes for Cloud Services. Springer Netherlands, 2014. P. 853–861.
29. Amazon EC2 spot cloud. [Electron. Resource. Accessed 18-January-2016]: http://spotcloud.com/.
30. Cloudorado: Cloud computing comparison engine. [Electron. Resource. Accessed 03-November-2015]: https://www.cloudorado.com/.
31. Sivadon Chaisiri and Bu-Sung Lee and Dusit Niyato. Optimization of Resource Provisioning Cost in Cloud Computing // IEEE Transactions on Services Computing. 2012. V. 5. P. 164–177.
32. H. Li and J. Liu and G. Tang. A Pricing Algorithm for Cloud Computing Resources // Proceedings of the International Conference on Network Computing and Information Security (NCIS). 2011. V. 1. P. 69–73.
33. Chun, Se-Hak and Choi, Byong-Sam. Service models and pricing schemes for cloud computing // Cluster Computing. Springer // 2014. V. 17. P. 529–535.
34. Sharma, Bhanu and Thulasiram, Ruppa K and Thulasiraman, Parimala and Buyya, Rajkumar. Clabacus: a risk-adjusted cloud resources pricing model using financial option theory // IEEE Transactions on Cloud Computing. IEEE, 2015. V. 3. P. 332–344.
35. Mashayekhy, Lena and Nejad, Mahyar Movahed and Grosu, Daniel and Vasilakos, Athanasios V. An online mechanism for resource allocation and pricing in clouds // IEEE Transactions on Computers. IEEE, 2016. V. 65. P. 1172–1184.
36. K. Ahmed and M. Gregory. Integrating Wireless Sensor Networks with Cloud Computing // Proc. Seventh International Conference on Mobile Ad-hoc and Sensor Networks. 2011. P. 364–366.
37. D. Rane and A. Srivastava. Cloud Brokering Architecture for Dynamic Placement of Virtual Machines // 2015 IEEE 8th International Conference on Cloud Computing. 2015. P. 661–668.
38. Smart Cloud Broker. [Electron. Resource. Accessed 03-November-2015]: http://www.smartcloudbroker.com/

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.

article

Zlotnikova R.E.

Novosibirsk State Technical University, 630073, Novosibirsk, Russia

OVERVIEW OF WIRELESS BODY AREA NETWORKS

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.

References

1. Milenkovic, C. Otto, and E. Jovanov. Wireless sensor networks for personal health monitoring: Issues and an implementation // Computer Communications. Special issue: Wireless Sensor Networks: Performance, Reliability, Security, and Beyond. 2006. V. 29. P. 2521–2533.
2. Denisenko M. B. Naselenie Rossii do 2025 goda. Pro et Contra. 2012. Ò. 16, N 4–5. P. 153–170.
3. Chen M., Gonzalez S., Vasilakos A., Cao H., and Leung V. Body area networks: A survey // Mobile Networks and Applications. 2011. V. 16. P. 171–193.
4. Ullah S., Shen B., Islam S. M. R., Khan P., Saleem S., and Kwak K. S. A study of medium access control protocols for wireless body area networks / arXiv preprint arXiv:1004.3890, 2010.
5. IEEE standard for local and metropolitan area networks: Part 15.6: Wireless body area networks // IEEE submission, February 2012.
6. Smith and L. Hanlen. Wireless body area networks : Towards a wearable intranet. ISCIT Tutorial, September 2012.
7. Kwon H. and Lee S. Energy-efficient multi-hop transmission in body area networks // in 20th IEEE Int. Symp. on Personal, Indoor and Mobile Radio Commun. (PIMRC). September 2009. P. 2142–2146.
8. Hanson M., Powell H., Barth A., Ringgenberg K., Calhoun B., Aylor J., and Lach J. Body area sensor networks: Challenges and opportunities // Computer. Jan. 2009. V. 42. P. 58–65.
9. Dishman. Inventing wellness systems for aging in place // Computer. May 2004. V. 37. P. 34–41.
10. Xing J. and Zhu Y. A survey on body area network. // in 5th Int. Conf. on Wireless Communications. Networking and Mobile Computing (WiCom ’09). Sept. 2009. P. 1–4.
11. Ullah S., Higgin H., Siddiqui M. A., and Kwak K. S. A study of implanted and wearable body sensor networks // in Proc. 2nd KES Int. Conf. on Agent and multi-agent systems: technologies and applications, (Berlin, Heidelberg). Springer-Verlag. 2008. P. 464–473.
12. Wang B. and Pei Y. Body area networks / Encyclopedia of Wireless and Mobile Communications, Edited by Borko Furht, Taylor and Francis. 2007. V. 98.
13. Ullah S., Khan P., Ullah N., Saleem S., Higgins H., and Kwak K. A review of wireless body area networks for medical applications / arXiv preprint arXiv:1001.0831. 2010. V. abs/1001.0831.
14. Lipprandt M., Eichelberg M., Thronicke W., Kruger J., Druke I., Willemsen D., Busch C., Fiehe C., Zeeb E., and Hein A. Osamid: An open service platform for healthcare monitoring applications // in 2nd Conf. on Human System Interactions (HSI’09). IEEE, 2009. P. 139–145.
15. Nehmer J., Becker M., Karshmer A., and Lamm R. Living assistance systems: an ambient intelligence approach // in Proc. 28th Int. Conf. on Software engineering. ACM, 2006. P. 43–50.
16. Latré B., Braem B., Moerman I., Blondia C., and Demeester P. A survey on wireless body area networks // Wirless Network. Jan. 2011. V. 17. P. 1–18.
17. N. de Vicq, Robert F., Penders J., Gyselinckx B., and Torfs T. Wireless body area network for sleep staging // in IEEE Biomedical Circuits and Systems Conf. (BIOCAS 2007). 2007. P. 163–166.
18. Lewis D. 802.15.6 call for applications-response summary / in 1508-0407-00-0006-tg6-applications-summary.doc.
19. Gopalan S. and Park J.-T. Energy-efficient mac protocols for wireless body area networks: Survey // in Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT) Int. Congress. 2010. P. 739–744.
20. Smith D., Miniutti D., Lamahewa T. A., and Hanlen L. Propagation models for body area networks: A survey and new outlook // IEEE Antennas and Propagation Mag., Dec. 2013.
21. Carrano R., Passos D., Magalhaes L., and Albuquerque C. Survey and taxonomy of duty cycling mechanisms in wireless sensor networks // IEEE Commun. Surveys Tutorials. 2013. V. P. N 99. P. 1–14.
22. Sudevalayam S. and Kulkarni P. Energy harvesting sensor nodes: Survey and implications // IEEE Commun. Surveys Tutorials. 2011. V. 13. N 3. P. 443–461.
23. Specification of the Bluetooth System version 4.0. Bluetooth SIG. June 2010. [El. Res.]: http://www.bluetooth.com.
24. Patel M. and Wang J. Applications, challenges, and prospective in emerging body area networking technologies // IEEE Trans. Wireless Commun. Feb. 2010. V. 17. N 1. P. 80–88.
25. Cao H., Leung V., Chow C., and Chan H. Enabling technologies for wireless body area networks: A survey and outlook // IEEE Commun. Mag. Dec. 2009. V. 47. N 12. P. 84–93.
26. Khan W., Xiang Y., Aalsalem M., and Arshad Q. Mobile phone sensing systems: A survey // IEEE Commun. Surveys Tutorials. 2013. V. 15. N 1. P. 402–427.
27. Bradley P. D. Implantable ultralow-power radio chip facilitates inbody communications // RF DESIGN. 2007. V. 30. N 6. P. 20.
28. Yuce M. R. and Ho C. K. Implementation of body area networks based on mics/wmts medical bands for healthcare systems // in 30th Annu. Int. Conf. IEEE Engineering in Medicine and Biology Society, 2008. EMBS 2008. IEEE, 2008. P. 3417–3421.
29. Tachtatzis C., Franco F., Tracey D., Timmons N., and Morrison J. An energy analysis of IEEE 802.15.6 scheduled access modes // in IEEE GLOBECOM Workshops (GC Wkshps). Dec. 2010. P. 1270–1275.
30. Khan J. Y., Yuce M. R., Bulger G., and Harding B. Wireless body area network (wban) design techniques and performance evaluation // J. of medical systems. 2012. V. 36, N 3. P. 1441–1457.
31. IEEE 802.15.4 Standard, Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (LR-WPANs). Piscataway, New Jersey, 08855-1331: IEEE, 2006. [Electron. Res.]: //standards.ieee.org/getieee802/802.15.html
32. IEEE standard for local and metropolitan area networks part 15.6: Wireless body area networks. IEEE Std 802.15.6-2012. February 2012. P. 1–271.
33. Reddy P., Reddy P. B., and Reddy V. K. Body area networks // J. of Telematics and Informatics. 2013. V. 1. N 1.
34. Astrin W., Li H.-B., and Kohno R. Standardization for body area networks // IEICE Trans. Commun., 2009. N 2. P. 366–72.
35. Elhadj Ben, Chaari L., and Kamoun L. A survey of routing protocols in wireless body area networks for healthcare applications // Int. J. of E-Health and Medical Commun. (IJEHMC). 2012. P. 1–18.
36. Kwak K., Ullah S., and Ullah N. An overview of IEEE 802.15.6 standard // in 3rd Int. Symp. on Applied Sciences in Biomedical and Communication Technologies (ISABEL). Nov. 2010. P. 1–6.
37. Ullah S., Higgins H., Braem B., Latre B., Blondia C., Moerman I., Saleem S., Rahman Z., and Kwak K. A comprehensive survey of wireless body area networks // J. of Medical Systems. 2010. P. 1–30.
38. Nehmer J., Becker M., Karshmer A., and Lamm R. Living assistance systems: an ambient intelligence approach // in Proc. 28th Int. Conf. on Software engineering. ACM, 2006. P. 43–50.
39. Schwoerer Li. Y., Yoon J., Farserotu J., Yang W., Sayrafian K., Miniutti D., and Lewis D. IEEE 802.15.6 regulation subcommittee report. May 2010.
40. Boulis, D. Smith, Miniutti D., Libman L., and Tselishchev Y. Challenges in body area networks for healthcare: the mac // IEEE Commun. Mag. May 2012. V. 50. N 5. P. 100–106.
41. Ullah S., Higgins H., Braem B., Latre B., Blondia C., Moerman I., Saleem S., Rahman Z., and Kwak K. A comprehensive survey of wireless body area networks // J. of Medical Systems. 2012. V. 36. P. 1065–1094.
42. Nehmer J., Becker M., Karshmer A., and Lamm R. Living assistance systems: an ambient intelligence approach // in Proc. 28th Int. Conf. on Software engineering. ACM, 2006. P. 43–50.
43. Pantelopoulos and Bourbakis N. A survey on wearable biosensor systems for health monitoring // in 30th Annu. Int. Conf. IEEE Engineering in Medicine and Biology Society 2008. EMBS 2008. P. 4887–4890.
44. Alemdar and C. Ersoy. Wireless sensor networks for healthcare: A survey // Computer Networks. 2010. V. 54. N 15. P. 2688–2710.
45. Kumar S., Kambhatla K., Hu F., Lifson M., and Xiao Y. Ubiquitous computing for remote cardiac patient monitoring: a survey // Int. J. of telemedicine and applications. 2008. V. 2008. P. 3.
46. Caldeira J., Rodrigues J., and Lorenz P. Toward ubiquitous mobility solutions for body sensor networks on healthcare // IEEE Commun. Mag. 2012. V. 50. N 5. P. 108–115.
47. Intra-mobility support solutions for healthcare wireless sensor networks 2013; handover issues // IEEE Sensors J. 2013. V. 13. N 11. P. 4339–4348.
48. Jeskindarov M. A. Glava 1.3 Mesto Rossii i perspektivy pozicionirovanija v mirovom hozjajstve v sovremennyh uslovijah // Vneshnejekonomicheskaja politika Rossii v uslovijah global’nyh vyzovov: Monografija /Finuniversitet; pod red. A. A. Tkachenko. Ì., 2015. P. 35–51.
49. Latré, Braem B., Moerman I., Blondia C., and Demeester P. A survey on wireless body area networks // Wireless Netw. 2011. V. 17. N 1. P. 1–18..
59. Shakhov Vladimir V., Migov Denis. Reliability of Ad Hoc Networks with Imperfect Nodes. Lecture Notes in Computer Science. Springer, 2014 .V. 8715. P. 49–58.
51. ITU — Radio Regulations. Volume 1, Sectio iv. [Electron. Res.]: http://life.itu.int/radioclub/rr/rindex.htm, 2012.
52. Carrano R., Passos D., Magalhaes L., and Albuquerque C. Survey and taxonomy of duty cycling mechanisms in wireless sensor networks // IEEE Commun. Surveys Tutorials. 2013. V. PP. N 99, P. 1–14.
53. FCC — Medical Body Area Networks — small entity compliance guide. [Electron. Res.]: http://www.fcc.gov/document/medical-body-area-networks, May 2013.
54. ITU TG 1–8 Working Group 1. Characteristics of ultra-wideband (UWB) devices. [Electron. Res.]: http://wcsp.eng.usf.edu/papers/UWBBasics.doc, Jan., 2003.
55. Chavez-Santiago R., Nolan K., Holland O., De Nardis L., Ferro J., Barroca N., Borges L., Velez F., Goncalves V., and Balasingham I. Cognitive radio for medical body area networks using ultra wideband // IEEE Wireless Commun. 2012. V. 19. N 4. P. 74–81.
56. Hovakeemian Y., Naik K., and Nayak A. A survey on dependability in body area networks // Medical Information Commun. Technology (ISMICT), 2011 5th Int. Symp. On. P. 10–14.
57. Lara O. and Labrador M. A survey on human activity recognition using wearable sensors // IEEE Commun. Surveys Tutorials. 2013. V. 15. N 3. P. 1192–1209.
58. Ullah S., Khan P., Ullah N., Saleem S., Higgins H., and Sup Kwak K. A review of wireless body area networks for medical applications // Int. J. of Commun., Netw. and System Sciences. 2009. V. 2. N 8. P. 797—803.
59. Seyedi M., Kibret B., Lai D. T., and Faulkner M. A survey on intrabody communications for body area network applications, 2013.
60. IEEE 802.15.4 Standard, Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for LowRate Wireless Personal Area Networks (LR-WPANs). Piscataway, New Jersey, 08855-1331: IEEE, 2006. [Electron. Res.]: //standards.ieee.org/getieee802/802.15.html.
61. Bae, H. Cho, Song K., Lee H., and Yoo H.-J. The signal transmission mechanism on the surface of human body for body channel communication // IEEE Trans. Microw. Theory Tech. 2012. V. 60. N 3. P. 582–593.
62. Akyildiz F., Brunetti F., and Blázquez C. Nanonetworks: A new communication paradigm // Comput. Netw. Aug. 2008. V. 52. N 12. P. 2260—2279.
63. La Polla M., Martinelli F., and Sgandurra D. A survey on security for mobile devices // IEEE Commun. Surveys Tutorials. 2013. V. 15. N 1. P. 446–471.
64. Shahov V. V. , Jurgenson A. N. , Sokolova O. D. Modelirovanie vozdejstvija ataki Black Hole na besprovodnye seti, Programmnye produkty i sistemy. 2017. Ò. 30. N 1. P. 34–39.
65. Shakhov V. V. Protecting Wireless Sensor Networks from Energy Exhausting Attacks, Lecture Notes in Computer Science. 2013. Springer. V. 7971. P. 184–193.
66. Galluccio, Melodia T., Palazzo S., and Santagati G. Challenges and implications of using ultrasonic communications in intra-body area networks // Wireless On-demand Network Systems and Services (WONS), 2012 9th Annu. Conf. on. 2012. P. 182–189.
67. Shakhov V. V., Koo I., Rodionov A. S. Energy exhaustion attacks in wireless networks // IEEE Int. Conf. on Computer and Information Sciences (SIBIRCON). 2017. P. 1–3.
68. Shakhov V. V., Koo I. Experiment Design for Parameter Estimation in Probabilistic Sensing Models // IEEE Sensors Journal. 2017. V. 17. I. 24. P. 8431–8437.
69. Shakhov V. V. Performance Evaluation of MAC Protocols in Energy Harvesting Wireless Sensor Networks. Lecture Notes in Computer Science. Springer, 2016. V. 9787. P. 344–352.
70. Materukhin A., Shakhov V. V., Sokolova O. D. An efficient method for collecting spatio-temporal data in the WSN using mobile sinks // IEEE Int. Conf. on Computer and Information Sciences (SIBIRCON), 2017. P. 118–120.

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

article

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

DISTRIBUTED ALGORITHM OF MULTIDIMENSIONAL DATA LATTICE DISTRIBUTION ON MULTIDIMENSIONAL MULTICOMPUTER IN THE LuNA FRAGMENTED PROGRAMMING SYSTEM

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.

References

1. Malyshkin V. E., Perepelkin V. A., Schukin G. A. Scalable distributed data allocation in LuNA fragmented programming system // J. Supercomputing. 2017. V. 73. N 2. P. 726–-732. Springer US.
2. Malyshkin V. E., Perepelkin V. A., Schukin G. A. Distributed Algorithm of Data Allocation in the Fragmented Programming System LuNA // PaCT 2015. LNCS, V. 9251. P. 80–85. Springer, Heidelberg.
3. Malyshkin V. E., Perepelkin V. A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // PaCT 2011, LNCS, V. 6873, P. 53–61. Springer, Heidelberg.
4. Malyshkin V. E., Perepelkin V. A. Optimization Methods of Parallel Execution of Numerical Programs in the LuNA Fragmented Programming System // J. Supercomputing. 2012. V. 61, N 1, P. 235–248.
5. Malyshkin V. E., Perepelkin V. A. The PIC Implementation in LuNA System of Fragmented Programming // J. Supercomputing. 2014. V. 69. N 1. P. 89–97.
6. Kraeva M. A., Malyshkin V. E. Assembly Technology for Parallel Realization of Numerical Models on MIMD-Multicomputers // J. Future Generation Computer Systems. 2001. V. 17. N 6. P. 755–765.
7. Gonzalez-Escribano A., Torres Y., Fresno J., Llanos, D. R. An Extensible System for Multilevel Automatic Data Partition and Mapping // J. IEEE Transactions on Parallel and Distributed Systems. 2014. V. 25. N 5. P. 1145–1154.
8. Chamberlain B. L., Deitz S. J., Iten D., Choi S.-E. User-Defined Distributions and Layouts in Chapel: Philosophy and Framework // HotPar’10, 2nd USENIX conference on Hot topics in parallelism. 2010. P. 12–12. USENIX Association, Berkeley, CA, USA.
9. Bikshandi G., Guo J., Hoeflinger D., Almasi G., Fraguela B. B., Garzaran M. J., Padua, D., von Praun, C. Programming for Parallelism and Locality with Hierarchically Tiled Arrays // PPoPP’06, 11th ACM SIGPLAN symposium on Principles and practice of parallel programming. 2006. P. 48–57. ACM New York, NY, USA.
10. Furtado P., Baumann P. Storage of Multidimensional Arrays Based on Arbitrary Tiling // 15th International Conference on Data Engineering. 1999. P. 480–489. IEEE.
11. Begau C., Sutmann G. Adaptive dynamic load-balancing with irregular domain decomposition for particle simulations // J. Computer Physics Communications. 2015. V. 190. P. 51-–61. Elsevier B. V.
12. Fattebert J.-L., Richards D. F., Glosli J. N. Dynamic load balancing algorithm for molecular dynamics based on Voronoi cells domain decompositions // J. Computer Physics Communications. 2012. V. 183. N 12. P. 2608–2615. Elsevier B. V.
13. Deng Y., Peierls R. F., Rivera C. An Adaptive Load Balancing Method for Parallel Molecular Dynamics Simulations // J. of Computational Physics. 2000. V. 161. N 1. P. 250–263. Elsevier B. V.
14. Fleissner F., Eberhard P. Parallel load-balanced simulation for short-range interaction particle methods with hierarchical particle grouping based on orthogonal recursive bisection // Int. J. for Numerical Methods in Engineering. 2008. V. 74. N 4. P. 531–-553. John Wiley & Sons, Ltd.
15. Hayashi R., Horiguchi S. Efficiency of dynamic load balancing based on permanent cells for parallel molecular dynamics simulation // IPDPS 2000, 14th International Parallel and Distributed Processing Symposium. 2000. P. 85–92. IEEE.
16. Rope and Patch algorithms demonstration page. [Electron. res.]: http://ssd.sscc.ru/en/algorithms.

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.

article

Main menu

2018 № 1(38)

Contents

Main menu

You are here

2018 № 1(38)

Contents