Piotr Panasiuk
email: p.panasiuk@mini.pw.edu.pl

Maciej Szymkowski
email: szymkowskimack@gmail.com

Marcin Dąbrowski
email: marcin.dabrowski@poczta.fm

Khalid Saeed
email: k.saeed@mini.pw.edu.pl

A Multimodal Biometric User Identification System Based on Keystroke Dynamics and Mouse Movements

Keywords: keystroke dynamics, mouse, biometrics, behavioral biometrics, authentication, systems security, multibiometrics, fusion, multimodal system

In this work it is shown how the behavioral biometrics allows to strengthen security of a personal computer during casual use. The user does not have to be even aware of verification system running in the background. Unfortunately, short passwords do not supply enough data for keystroke dynamics algorithms to be precise enough to keep the way and level the biometrics system requires. Behavioral biometrics cannot grant such authentication level as the other physiological biometric methods, e.g. fingerprint or retina scan. However, their transparency in analyzing data allows to merge methods into multimodal systems with a minimal cost. The benefit of keystroke dynamics is that it can be easily connected with some other biometric methods, especially with other human input interface devices. In this paper an approach to analyze keystroke dynamics along with mouse movement is presented. Even though both of the features are of behavioral character and hence with low repeatability, the results are good and promising for further research and modification.

Introduction

Today data safety is one of the most discussed terms. People need to prove who they really are at every turn. This includes banking, healthcare, communication and much more. Something you know and something you have -these are the most common methods used to prove your identity. You know your password, but you may forget it if you are not using it often or have too many of them to remember. Things such as tokens or cards can be used instead and they let you free of remembering sophisticated sequences of various letters, numbers and other special characters. The thing is, tokens and cards can be lost, stolen or even destroyed quite easily. Thus, another way for authentication is needed. Here comes biometrics. Something you are cannot be lost or forgotten. These are based on human behavioral and physical characteristics that can be measured and cannot be easy to imitate. Physiological features may include fingerprint, DNA, hand geometry, retinal scan and others that come from how organisms are built. Behavioral features on the other hand are based on how people do things, for example voice (the way one talks), gait (the way one walks) or keystroke dynamics (the way one strikes or touches the keys on the keyboard), and so on. This paper focuses on behavioral methods. They are cheaper in implementation, usually do not require specialized hardware and often work without bothering or notifying the user. On the other hand these features are often hard to repeat in exactly the same way. This introduces information noise. Both valid users may find it difficult to repeat the activity in the same manner to fit into their patterns and from the other side impostors may also be close to imitate valid data and be falsely accepted. The goal is to find a method that despite those difficulties will make the right decision with the highest possible accuracy.

One of the ways to make biometric algorithms more robust is to join multiple biometric features. This way the algorithm gets more data to analyze what helps it in correct classification. Thus this paper proposes a method to combine multiple behavioral features to provide greater reliability and safety in computer systems. In this particular case mouse movement and keystroke dynamics were chosen as they are not very involving to the user and are often naturally used together. What is more they use standard equipment of every personal computer nowadays.

Known approaches

Lately more interest in the field of behavioral biometrics has been observed. To account this, the authors of this paper decided to present some of the recent approaches in mouse and keystroke dynamics.

In [1] an interesting approach regarding mouse movement has been described. Authors analyzed user online activities by tracking mouse movements across web interfaces in certain areas of interest. One of three user activities was being recognized. Hidden Markov Models and Conditional Random Fields were used in the process. 51 students performed one of three tasks twice. Tasks were based on memorizing graphical representation of a given quadratic equation or discovering and memorizing intersection coordinates of two given quadratic equations. HMM and CRF models performance was evaluated using ratio of ground truth matches number of observation sequences to whole number of test sequences. Distance in pixel of the vicinity extent has been found accuracy determining as its higher value generally resulted in improved accuracy. For distance equal 0, HMM and PCRF models using classical observation sequences gave recognition rate of 88.24%.

Another interesting approach regarding mouse movement has been described in [2]. Authors presented a method for user emotional state prediction basing on mouse dynamics. To collect data, authors created a simple computer game that required users to click differently sized and colored rectangles in correct order since they were placed randomly. Samples from 262 users were gathered of which 44 users were asked after session, about their emotions during task. Two different states were distinguishable. Features including distance and direction were extracted from mouse logs among others. Classification was performed using: Logistic regression, Support Vector Machine, Random Forest, and C4.5. Authors used 10 fold cross validation for evaluation, dividing whole data into 10 random parts of same size, next using 9 for training and remaining one for validation. This setup allowed authors to obtain accuracy of 94.61% (for SVM) in prediction of user emotional state basing on mouse movement and knowing target. Without knowledge of user emotional state during collecting data, accuracy dropped to 82.38%.

Authors of [3] proposed a novel multimodal biometrics user verification technique based on keystroke dynamics and mouse movement. They focused on several layers of mouse events. This aspect seems interesting and worth further research. Authors claim that they have very good accuracy. The technique seems to be advanced however not all tests were performed and authors do not present the FAR level of the solution. FRR is quite low at range of 3.2% but in case of verification system, this value may be adjusted to any level by the cost of increasing the opposite metric -FAR. The classification method of the presented solution is not precisely described. Moreover, the results were calculated on unknown database that is not publicly available (state for April 23, 2016). Thus the results and accuracy cannot be confirmed.

A fuzzy approach based method on commands typed by users was considered by the authors in [4]. Authors presented a way to detect impostor by creating two different user activity profiles, local one based on recent activity of the user and one combining multiple local profiles representing user general computer behavior. Authors used publicly available SEA data set consisting of system calls made by 70 users, giving a total of 15000 recorded commands. 50 randomly chosen users were considered legitimate, and 20 were taken as impostors. The lowest FRR ratio of 0.8% paired with FAR equal to 70.1 was obtained by the mentioned method. Taking low computational complexity into account, this method can successfully be used in real-time.

Another keystroke dynamics based approach was presented by authors of [5]. In that paper user password typing dynamics was observed. Fuzzy sets were used to construct user model. Data for 51 users, each one typing the same password 400 times in 8 sessions of 50 tries, contained in publicly available database Keystroke Dynamics Benchmark Data Set by Kevin Killourhy and Roy Maxion [6] was used to perform experiments. Using proposed method allowed to obtain EER value of 9.2% -an improvement over original [6] methods giving best EER of 9.6%. According to authors, results improved greatly due to data normalization.

The authors of this paper also have achievements in the field of biometric methods. Apart from the algorithms suggested on the basis of physiological features, which is not the subject of this paper, many other behavioral approaches were introduced [7-14]. The mouse movement was considered for the first time in 2005 [7]. The work introduced then comprised a new method for analyzing biometric features for human authentication. The rhythm of the movement is individual and characteristic for each person, so it can be used for identification in small defined groups or verification for larger groups of users. The method analyzes the dynamics of the mouse cursor movement. The processed signal is the cursor changing speed obtained during the random movement of the mouse. This signal is transformed into frequency domain with Discrete Fourier Transform and then analyzed by Toeplitz matrix minimal eigenvalues method [7]. The resulting feature vector is used for classification performed by two methods: k-nearest neighbors and NN -artificial neural networks. The obtained results were promising and showed a large possibility of integrating the method with other features in multimodal biometrics systems.

The authors' team performed other multiple approaches on keystroke dynamics user identification over the past few years. Algorithms take into account many features including: dwell and flight times, average keystrokes per minute, overlapping specific keys, typing errors, the way of error correction and others. Using simple 1-NN classifier resulted in accuracy of 75.68% on 37 users [8]. Later approach used improved algorithm based on k-NN classifier on authors' database consisting of samples left by over 250 individuals. Gathered samples included one-word phrase and longer sentences in Polish and English. It was proven that even small number of samples may be enough for successful recognition with the high user amount and right choice of phrase. Best classification accuracy of 90.83% was obtained with 21 users [9]. Other algorithm modifications were conducted in the next works. On fixed-text approach high accuracy of 98.78% was obtained for 16 users, although decreasing with greater number of users (e.g. 72.3% for 79 individuals) [10]. Database quality, however, was taken into account in the following approaches. In [11] the authors used their own and Maxion- Killourhy's [6] databases with selfdeveloped improved algorithm allowing to discard samples with errors. Said method allowed accuracy increase of 3.6% for Maxion's data and increase of 5.6% for authors' database in comparison to initial values. Next [12] authors further analyzed database impact on results. Data gathering precision and conditions along with various algorithm modifications allowed authors to deeply compare mentioned databases and classification methods. This research lead to conclusion that databases with longer samples are more suitable for user identification than authentication and inclusion of user-specific imperfect samples can improve FRR. Additionally, updating training set over time is believed to affect classification accuracy in a positive way. Authentication by non-fixed text of various length was also taken into consideration by the authors [13]. Data were gathered over the Web using browser application and also locally with the use of dedicated applications. Sample length provided to be vital on recognition accuracy as longer texts generally allowed to obtain better results. Using statistical characteristics of the sample gave better outcome than using raw sample data, eventually leading to EER value of 6.1% for 200-keystroke long samples. Comparison of the Keystroke Dynamics databases was conducted by the authors in [14]. In said work newly-gathered database was presented and compared with existing one which is publicly available [6]. Authors collected it in the way it can be directly compared with Keystroke Dynamics Benchmark Data Set. That led to two databases being almost identical. It was possible by using the same phrase typed equal number of times by every user of both databases, i.e., 400 valid samples in 8 sessions. Main difference introduced with authors' database was that its data were collected in unsu-pervised, less restrictive conditions with the use of commonly available devices when Maxion's database was supervised and used specific high-precision devices. The use of the same algorithms on both databases resulted in differences in the outcome ranging up to about 30% in some situations, which led to the conclusion that new algorithms should be tested on multiple databases, including publicly available ones and not limiting to the ones gathered by the authors' for the specific research purpose. Moreover, less restrictive method of collecting data allowed to obtain generally higher recognition accuracy.

Proposed approach

In order to get data a web application has been created. It is located under the Internet address [15]. Users have to register in order to create their unique account. During the registration no biometric data are being collected. Then after logging in they can leave their biometric samples. Authors encourage everyone to visit our system and contribute to the database. User details like email address are stored only to remember the user and allow him to reset the password. The database is meant to be published online. More details will be available on the mentioned website in the near future as the samples set grows rapidly.

A sample in our database consists of two phrases that a user has to type and the mouse data recorded as an interaction with the user interface. The first phrase is a fixed text. It imitates fairly strong password "_Y9u3elike22". It is common for all users. The second phrase is a free-text phrase that a user comes up with spontaneously while typing it. Its only limitation is that it has to be not shorter than 80 characters and not longer than 4000. When it comes to mouse movement data are gathered in a raw form -events like button press, button release and move. Each data has a timestamp from the beginning of the sample and coordinates of a cursor on the web page. Keystroke events are recorded within each text field; however mouse events are being recorded for whole duration of leaving a complete sample. This means since pressing the first button, through selecting each text field and pressing additional button, until submitting a form by clicking the last button on the data acquisition web page.

Data examined during this research were only fixed phrase and mouse activity. From these data authors had to extract the most valuable features. Samples were gathered in unsupervised conditions so an algorithm for various corner-cases was applied. When it comes to mouse data single mouse moves are being extracted. Mouse move is considered as cursor position change from the beginning of a move until button press. Due to unwanted cursor movements during releasing the mouse by the user, authors decided to ignore move events after mouse click and before typing a text. Finally, the authors examined few mouse movement features -move time, move speed (in pixels per second) and move distance. As a separate feature mouse button dwell times while clicking buttons or text fields are accounted. When it comes to keyboard data we have tried to extract flight times and dwell times as they are the most common keystroke features, but to our surprise they did not perform well with success rate at about 11% using approach and setup presented in the following para-graph. It might be the case that the sample was really difficult, especially the first half of it. Some additional difficulties came up with shift key being pressed different amount of times. Authors tried to implement an algorithm that would deal with those differences however the overall recognition rate was really affected by those artifacts. So the dwell times of specific key presses were analyzed instead. They have proven to give really good accuracy which is presented in the next chapter.

After defining feature vectors our next step was the identification process. In this purpose authors used fast and simple k-NN algorithm. The most important part is the distance calculation. There are three features that are being extracted from both keystroke and mouse data. A keyboardDistance (1) is a distance calculated using Manhattan metrics between corresponding dwell times of a training and a testing sample. In a case of mouse data represented by mouseDistance (2) there are mouse key dwell times, the metric used is Manhattan metric as well. The last feature is moveDistance (3) which proved to be the best metric to calculate the moves and is defined by the Euclidean distance from the move start point to the move end point in a twodimensional space according to the move definition in a foregoing paragraph.

𝑘𝑒𝑦𝑏𝑜𝑎𝑟𝑑𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 1 𝑘 ∑|𝑑𝑤𝑒𝑙𝑙𝐴 𝑖 -𝑑𝑤𝑒𝑙𝑙𝐵 𝑖 | 𝑘 𝑖=0 (1)
𝑚𝑜𝑢𝑠𝑒𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 1 𝑚 ∑|𝑚𝑜𝑢𝑠𝑒𝐷𝑤𝑒𝑙𝑙𝐴 𝑖 -𝑚𝑜𝑢𝑠𝑒𝐷𝑤𝑒𝑙𝑙𝐵 𝑖 | 𝑚 𝑖=0 (2)
𝑚𝑜𝑣𝑒𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 1 𝑛 ∑ 𝑑𝑖𝑠𝑡(𝑚𝑜𝑣𝑒𝐴 𝑖 , 𝑚𝑜𝑣𝑒𝐵 𝑖 ) 𝑛 𝑖=0 (3)
As one can see each distance is normalized. To calculate the final distance between two samples authors use equation ( 4). What should be explained is that keyboard-Weight is the importance factor of keyboard event. Mouse events importance factor is mouseWeight and the moveWeight is the importance factor of the mouse moves.

𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝑘𝐷 • 𝑘𝑊 + 𝑚𝐷 • 𝑚𝑊 + 𝑚𝑜𝑣𝑒𝐷 • 𝑚𝑜𝑣𝑒𝑊 𝑘𝑊 + 𝑚𝑊 + 𝑚𝑜𝑣𝑒𝑊 (4)
where: kD -keyboardDistance kW -keyboardWeight mD -mouseDistance mW -mouseWeight moveD -moveDistance moveW -moveWeight Mentioned weights have been selected empirically. The detailed information about the experiment setup and preparation is described in the following chapter. After defining the distance the classic k-NN algorithm is being followed.

Results of the experiment

Authors' database has irregular amount of samples per user. This is due to constant growth of the dataset. Because of this the users that does not get sufficient amount of samples have been removed from the experimental setup. In our k-NN-based method the minimum number of samples per user is k. This number allows to prepare a valid training set having exactly k samples for each user. The rest of remaining user samples are used for a testing purpose. Finally for a k = 10 there are 50 valid classes in each of the experiments. This is why all setups has been limited to those 50 classes. So the users set among all experiment runs are the same. To get reliable results each experiment was repeated 100 times for each setup, every time using randomly selected training and testing samples.

At the beginning authors had to select proper feature weights to get the best results. This way the algorithm has been run for each of three features separately and authors got the information about accuracy of each of the methods. The weakest method was mouse dwell times alone with average success rate of about 12%. The second one that was mouse move distances gave the success rate around 31%. It is worth mentioning that while analyzing move speeds in pixels per second instead of move distances the accuracy has dropped to the level of 8%. Finally the best was keystroke dynamics with around 44% of accuracy. In order to obtain the best weight values authors picked the two weakest features and joined them using different weight ratio. After conducting the experiment with weights ranging from 0.0 to 1.0 with step of 0.05, the best ratio proved to be 0.8 for mouseWeight vs. 0.2 for moveWeight that returned the accuracy of around 40% for mouse data only. Figure 1 presents the results of classification accuracy after joining mouse dwell times and mouse movement features in comparison to keystroke dynamics alone. Having these results authors tested different moveWeight values and the results shown that the big increase can be gained. The accuracy of the algorithm in a setup where key-boardWeight = 2, mouseWeight = 0.4, and moveWeight = 0.1 returned the identification accuracy of 68.8% for 50 classes. This result has exceeded authors' expectations for such little of data. In Figure 2 one can see results of our experiments. Different values of parameter k (from 1 to 10) were taken into account whereas count of classes was stable and equal to 50. Each method accuracy has been marked separately and the optimal fusion method results are also presented.

Conclusions and Future Work

Biometric methods present a very convenient way to harden the computer system security. Even if the user knows the password it is really hard for him to repeat it in the same manner to breach the security. If it comes to identification, it is even a harder task because a user does not claim his identity. Thus the whole database has to be searched for matching the user pattern. Identification algorithms have to be fast and robust. Presented in this paper k-NN algorithm perfectly matches these requirements.

As it was presented, user identification by using mouse button dwell is not very reliable. When mouse moves are analyzed, the accuracy increases significantly. When both mouse button press and mouse move features are used together they are almost as effective as keystroke dynamics using dwell times. What was surprising in this experiment is the fact that flight times and dwell times which usually make the user typing features more persistent in time, resulted in a huge accuracy drop (from 44% to merely 11%). This is possible due to the short sample length and few ways to type the phrase correctly (using the shift key).

As expected, combining both keystroke dynamics and mouse features allowed to obtain much better recognition ratio than relying on them separately. Accuracy of 68.8% as a result of fusion is quite impressive, taking into account the high number of users in relation to quite short samples. Fusion of different biometric algorithms gives us a great advantage at low values of k which significantly decreases time required to prepare a user profile (training set). When the authors examined the speed of mouse movements, the success rate dropped dramatically (level of 5-8%, depending on the setup). There might be some inconsistencies in the mouse samples (users made mistakes, missed the button, etc.). However, unexpectedly strong feature turned out to be the position where user parks the mouse cursor and the position where he clicks items on the user interface.

Our database is continuously expanding as the existing users are leaving more of their samples, and new users are willing to help in the research. The authors encourage everyone to participate. The database will be publicly available online. For more information the reader can track the information given in the authors' system website [15]. In the near future the authors are planning to take into consideration more mouse-specific characteristics in addition to clicks and moves distances currently used in our algorithm. Authors believe that the analysis of other behavioral aspects will definitely improve the accuracy. Examples that are worth examining are: rapid mouse movements during mouse button press, cursor fixation on a target, mouse movement when user releases the device, and other issues that may come up during the research. Additionally, as an extension to this research authors would like to introduce some decision algorithm and understand user mistakes for better handling of unusual users and data anomalies.

Fig. 1 .

 1 Fig. 1. Influence of joining mouse button dwell times and mouse moves on algorithm accuracy.

Fig. 2 .

 2 Fig. 2. Chart presenting classification accuracy using different approaches along with differentk-nearest neighbor value used.

Acknowledgments

This work was partially supported by grant number S/WI/1/2013 from Bialystok University of Technology and funded from the resources for research by Ministry of Science and Higher Education. It was also partially supported by Neitec company.


Jerzy Greblicki
email: jerzy.greblicki@pwr.edu.pl

Walczyński Maciej
email: maciej.walczynski@wso.wroc.pl

Tadeusz General

Kościuszko

Determination of the optimal routes for autonomous unmanned aerial vehicle under varying wind with using of the traveling salesman problem algorithm

Keywords: multicopters, UAV, traveling salesman problem (TSP), drone routing problem (DRP)

The goal of this paper is to propose and test the algorithm for traveling salesman problem (TSP) for autonomous unmanned aerial vehicles. In this paper we consider the situation when the multicopter is flying under a variable wind and is intended to visit indicated points. We analyze the efficiency of the algorithm in case of limited flying time on a constant height.

Unmanned Aerial Vehicles

Unmanned Aerial Vehicle also known as drone is a kind of aerial machine. Drones have become one of the symbols of the global fight against terrorism. Nowdays the drones are very popular also in civil purposes. Those machines are used as a flying camera platform, platform for aerial inspection of buildings, bridges and Its hard to imagine that the history of UAV's is that long. Many of a UAVs futures are still under a laboratory experiments and the road to its commercialization and widespread use is still long.

Unmanned Aerial Vehicles in military solutions

The roots of Unmanned Aerial Vehicles (UAV) are strictly connected with the military solutions. One of the first UAVs was the aerial bomber balloon developed and patented in the New York in 1863 by an American inventor named Charles Parley. The idea of this solution was based on a hot-air balloon with a basket filled with explosives. This material was to be dropped on the enemy using a mechanism activated by the clock mechanism. Also, one of the first ideas of an unmanned airplane was strictly connected with army solutions in the war time. In 1916 the first airplane controlled by radio waves from the ground was created. Just a few days after the USA officially entered World War I in 1917 the American Army commissioned work on Unmanned Combat Aerial Vehicles (UCAV) [START_REF] Clark | Uninhabited Combat Aerial Vehicles: Airpower by the People, for the People, But Not with the People[END_REF]. Those first unmanned flying bombs based on biplane airplanes. There were several problems with those first UCAV's. One of the biggest problem was the limited aerodynamic knowledge in those times. It was almost impossible to build well flying unmanned airplane just less than twenty years after the first flight of the Wright Brothers [START_REF] Howard | The Story of the Wright Brothers[END_REF]. The period of the 30's and 40's was a time of significant development of the technological potential of the major world powers. One of the achievements of those troubled times is the missile V-1. It is the prototype of the later unmanned airborne vehicles equipped with disposable warheads. Years of the 50's and 60's along with the Cold War between the United States of America and the Union of Soviet Socialist Republics is another period of intensive development of unmanned aerial vehicles in the history. One example is here the American MGM-1 Matador or RGM-6 Regulus I. Starting from the 90's of the twentieth century drones (due to the development of electronics and IT) began to increasingly appear more numerous and in the arenas of armed conflict. It is sufficient to mention here the participation of the Israeli-American unmanned aerial vehicles RQ-Pioneer in such operations as "Desert Shield" "Desert Storm", or "UNSOM II".

Unmanned Aerial Vehicles in non-military solutions

Today, unmanned flying platforms are becoming increasingly popular due to the significant decline in prices . The use of a no -manned airborne platforms to shoot footage in high quality becomes widespread. Increasingly used unmanned platforms to support a number of projects, such as the inspection of hard to reach places with the use of video cameras and thermal imaging.

Fig. 3. Thermal image of one of the buildings in General Tadeusz Kościuszko Military Academy of Land Forces

In addition, the no -flying manned platforms begin to be used as robotic couriers carrying parcels. The number of drone applications continues to grow. List of examples of applications of drones is shown below:

 aerial photography  building inspections  geodesy and cartography  delivery of packages  meteorological measurements  SAR -" Search and Rescue " actions  agriculture  mining  study of wild life animals  video transmission  objects monitoring  assessment of damages  archeological discoveries  emergency medical services However, the drones are still not fully autonomous platforms capable of independent missions in varying conditions and are far from those which provide laboratories.

Autonomous Unmanned Aerial Vehicles

There are several types of civil UAV nowadays, but one of the most popular are multicopters. They are stable and easy for steering machines with the ability to hover in the given point of three-dimensional space. There are several types of multicopters but the most popular since to be quadrocopter. That is a milticopter with four vertically oriented propellers. We choose quadrocopters becouse of its relative low costs and the ability to immediately change the direction of flight.

Drone routing problem

Drone routing problem is a variation of Vehicle Routing Problem (VRP). This is well known problem which describe a situation when we need to visit a list of points and we need to determine the optimal path. The optimization may bases on distance, cost or even other criteria. In the case of multicopters determination of the optimum flight path it is extremely important due to the very limited time to operate in the air.

Determining the optimal route

In many situations there is no possibility to control robots in real time. For example, control of a Martian rover must be done with using a class of offline algorithms due to a significant delay due to large distances what must overcome a radio signal from Earth to Mars and back . In addition, autonomous process of robots will need to create more and more new solutions which allows to limit the role of a man in control process. Process of determination of the optimal paths in limited time of drone flight requires a series of calculations. These calculations can be made with using a high performance workstation. That workstation may be located on ground, and path for copter flight may be send to drone with WiFi. On the other hand drones equipped with on-board computers are of considerable Capacity . An example can be DJI Matrice 600 multicopter, which can be equipped with the calculation module with 326 GigaFLOPS onboard. This computer bases on the NVIDIA Tegra K1 quad-core ARM Cortex-A15 processor with 192 GPU cores. Maximal CPU frequency is up to 2.2GHz Such a large number of floating point operations that may be performed on -board of drone allows to make advanced signal processing from the high resolution camera, analyzing the signals from the sensors in real time. In addition, it is possible to calculate and correct the path through the drone during its flight.

Determining the optimal route in variable wind situation

In this paper we present the method to find a good solution to TSP for modeling UAV (multirotator) vehicle in windy environment. The main deference is that distance of flight that we have to consider depends strongly on direction of flight. Upwind flight is much more expensive in terms of host because UAV have to flight against a wind. Downwind flight is respectively much more cost effective. In light of this TSP solution for UAV have to consider also wind factor.

In this paper we also presented numerical tests for route planning for UAV. By means of computer simulations on benchmarks taken from the TSPLIB we have obtained very promising results using a cluster of personal computers and the MPI library.

2.3

Definition of problem

The classical traveling salesman problem (TSP) is defined on an undirected graph 𝐺 = (𝑉, 𝐸), where 𝑉 = {1,2, … , 𝑛} is a vertex (cites) set and 𝐸 = {{𝑖, 𝑗}: 𝑖 ≠ 𝑗, 𝑖, 𝑗𝜖𝑉} is an edge set. A non-negative cost (distance) matrix 𝐶 is defined on 𝐸. The matrix 𝐶 is symmetric (𝑐 𝑖,𝑗 = 𝑐 𝑗,𝑖 , 𝑖, 𝑗 ∈ 𝑉) and satisfies the triangle inequality(𝑐 𝑖,𝑗 + 𝑐 𝑖,𝑘 ≥ 𝑐 𝑖,𝑘 for all 𝑖, 𝑗, 𝑘 ∈ 𝑉). The problem deals with finding a minimum length Hamiltonian cycle (a tour that passes through each city exactly once, and returns to the starting city) on a 𝐺.

Each feasible solution of the TSP (a cycle including all the nodes of a 𝐺) is a permutation of elements of the set V. Let

𝐿(𝛿) = ∑ 𝑐 𝛿(𝑗),𝛿(𝑗+1) + 𝑛-1 𝑗=1 𝑐 𝛿(𝑛),𝛿(1) (1)
denotes length of traveling salesmen's tour

(𝛿(1), 𝛿(2), … , 𝛿(𝑛), 𝛿(1)), 𝛿𝜖Π, (2)
where Π is set of all permutations of elements of the set V.

In real environment route planning for UAV have to consider fact that UAV flows with masses of air (wind drag). We have to define ground speed of UAV. When UAV moves down wind speed of vehicle is added to speed of wind and ground speed is relatively higher. When UAV moves up wind speed of vehicle is substracted from speed of wind and ground speed is relatively lower. That means that flight distance is differs (𝑐 𝑖,𝑗 ≠ 𝑐 𝑗,𝑖 , 𝑖, 𝑗 ∈ 𝑉) and matrix 𝐶 𝑤𝑖𝑛𝑑 is not symmetrical. Let 𝐶 𝑤𝑖𝑛𝑑 denotes distance matrix in windy environment. 𝐶 𝑤𝑖𝑛𝑑 can be calculated from C in following way.

Lets assume that matrix 𝑊 𝑠 denotes wind speed, and element of 𝑤 𝑖,𝑗 of matrix 𝑊 𝑠 denotes wind speed, on route between cities i and j. Moreover matrix 𝑊 𝛼 denotes direction (angle of wind), and element of 𝛼 𝑖,𝑗 of matrix 𝑊 𝑑 denotes wind direction, on route between cities i and j. In light of this we may analyze influence of wind on way between cities i and j. Example situation is presented on figure when we consider downwind flight. We may see that flight time is reduced comparing to windless environment. From perspective of UAV destination city is closer than it is. Speed over the ground is called ground speed, speed of UAV relative to ground is called air speed. Similar situation is presented on figure below when vehicle moves upwind. It is also important to note that flight time as well as drag influence depends also on speed of vehicle. More over if speed of wind is higher than speed of vehicle distance is equal to infinity (vehicle can't move that direction).

On this basis we are able to calculate new matrix 𝐶 𝑤𝑖𝑛𝑑 in a following way.

where 𝑡 𝑖,𝑗 denotes flight time between cities i and j.

We may notice that during flight from j to i wind speed is the same but direction is opposite. In light of this new matrix 𝐶 𝑤𝑖𝑛𝑑 is not symmetrical.

Modification of C matrix to non-symmetrical makes possible usage of almost all know methods for solving TSP problem [START_REF] Reinelt | TSPLIB -a traveling salesman problem library[END_REF][START_REF] Papadimitriou | The complexity of the Lin-Kernighan heuristic for the traveling salesman problem[END_REF][START_REF] Johnson | The traveling salesman problem: a case study in local optimization[END_REF]. In this paper we would like to focus on analysis of wind influence on solution of TSP so we decided to use deterministic approach, to find local minimum. For all test cases optimization algorithm is applied (e.g. 2-exchange Lin-Kerninghan algorithm, the so-called "2-opt") but distance matrix is 𝐶 𝑤𝑖𝑛𝑑 . In next section experimental results are presented.

In this analysis we have limited our considerations only to a distance analysis. We would like to underline that power consumptions is also very important factor. Drag force depends on velocity second power in light of this flying down wind may reduce power consumption significantly. We plan to extend this model in next steps of research.

Experimental results

We have tested influence of wind on TSPLIB benchmark set. We have analyzed tree situations: no wind, east wind, west wind. We have tested our solution on set of benchmarks with using Lenovo Y50-70 computer with Intel i5 processor and 8GB RAM under the control of Linux Ubuntu 16.04 operating system. All test cases were solved with 2-opt algorithm [START_REF] Englert | Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP[END_REF]. Results are presented below. We may have noticed that wind has strong influence on solution. In some cases it extends length by 10%. And the planed route differs between windless conditions and windy environment.

Conclusions

.In this paper we proposed and tested the algorithm for traveling salesman problem (TSP) for autonomous unmanned aerial vehicles. We described and tested situations with different vectors of wind speed, air speed and ground speed with using deterministic approach, to find local minimum. For very limited time of flight of multicopters proposed method can allow for autonomous execution of the mission under varying wind. In this paper we represents only the theoretical considerations and its a startingpoint for further research .

Fig. 1 .

 1 Fig. 1. Kettering Bug one of the first UCAV's from late 1910's 1 .

Fig. 2 .

 2 Fig. 2. RGM-6 Regulus I from 1958 2 .

Fig. 4 .

 4 Fig. 4. DJI Inspire 1 quadrocopter

Fig. 5 .Fig. 6 .

 56 Fig. 5. Analysis of UAV speed in windy environment (downwind flight)

  𝑐 𝑖,𝑗 * cos(𝛼 𝑖,𝑗 ) + 𝑤 𝑖,𝑗 * cos(𝛼 𝑖,𝑗 ) * 𝑡 𝑖,𝑗 ) 2 + (𝑐 𝑖,𝑗 * sin(𝛼 𝑖,𝑗 ) + 𝑤 𝑖,𝑗 * sin(𝛼 𝑖,𝑗 ) * 𝑡 𝑖,𝑗 )

	𝑐 𝑖,𝑗 ′ =
	√ (2 2

Table 1

 1

			. Results
	Name of	Number of		Distance
	benchmark	cities	Windless	East wind	West wind
	kroA100	100	22876	23456	25642
	kroA150	150	28996	29012	27805
	kroA200	200	33213	33900	33100
	kroB100	100	23077	24021	23534

https://commons.wikimedia.org/wiki/File:USS_Tunny_SSG-282_Regulus1_launch_NAN9-


Joanna Swiebocka-Wiek
email: jsw@agh.edu.pl

Skull stripping for MRI images using morphological operators

Keywords: skull stripping, brain extraction, morphological operators, image segmentation, MRI

One of the most common MRI (Magnetic Resonance Imaging)use is a brain visualisation. Brain anatomy is highly complicated therefore it might be difficult to extract only these structures which have diagnostic value. In a consequence it is so necessary to develop and apply most efficient brain's segmentation algorithms. One of the first steps in case of neurological MRI analysis is skull stripping. It involves removing extra-meningeal tissue from the head image, therefore it is essential to find the best method to determine the brain and skull boundaries. In T1-weighted images, cerebrospinal fluid (CSF) space and skull are dark, that is why the edges between the brain and the skull are well-marked but even strong edges might be unsettled because of finite resolution during MRI acquisition or the presence of other anatomical partial structures within the brain (connections between the brain and optic nerves or brainstem). There are many ways to perform this operation, none of them is not so great as to constitute a standard proceedings. In many cases, there are limitations associated with the development environment, license and images input that hinder skull stripping without specialised software. Proposed method is free of these constraints. It is based on application of morphological operations and image filtration to enhance the result of the edge detection and to provide better tissues separation. The efficiency was compared with other methods, common in commercial use, and the results of this comparison was presented in this paper.

Introduction

Skull stripping is a process of the brain tissue segmentation (cortex and cerebellum) from surrounding region (skull and nonbrain area). It is also a very important preprocessing step which precedes further analysis in case of many MRI neurological images (such as image registration or tissue classification) [START_REF] Zhuang | Skull-stripping Magnetic Resonance Brain Images Using a Model-based Level Set[END_REF]. In clinical practice, this method is widely used in developing automated methods for progress evaluation of neurodegenrative diseases such as: Alzheimer's disease, multiple sclerosis and other neurological disorders like brain aging or even some mental illness. In search of the most effective skull stripping techniques there were proposed many innovative automatic and semiautomatic brain segmentation techniques [START_REF] Grau | Improved watershed transform for medical image segmentation using prior information[END_REF] [START_REF] Somasundaram | Skull Stripping of MRI using Clustering and Resonance Method[END_REF] [2] [START_REF] Carass | A joint registration and segmentation approach to skull stripping[END_REF], particularly in the filed of MR image processing. However, published studies comparing common used algorithms [START_REF] Fennema-Notestine | Quantitative Evaluation of Automated Skullstripping Method Applied to Contemporary and Legacy Images, Effects of Diagnosis, Bias Correction, and Slice Location[END_REF] demonstrate that each of methodologies has significant number of advantages and disadvantages as well, so it's very difficult to find one approach which could be consider as the ideal solution. These factors result in increasing need for the further development and examination of new effective skull stripping methods. In this paper one of approaches will be introduced.

Proposed method

All images used and processed in this paper are the private property of the Author. They were registered in the John Paul II Hospital in Cracov. The images were registered with the following acquisition parameters: magnetic field: 3T, Spin Echo sequence,T1-weighted, slice thickness: 3mmm and contrast application). During selection of images for algorithms evaluation, the key criteria was to ensure their representativeness (to choose the most common type of images, which are also most often processed and compared in scientific dissertations). Algorithm was tested on images in all 3 projections, all scans were acquired in the middle of the T1-weighted session so that the area of the brain was possibly the greatest in in any case. Skull stripping techniques can be divided into 3 main categories [START_REF] Zhuang | Skull-stripping Magnetic Resonance Brain Images Using a Model-based Level Set[END_REF]:

-intensity-based methods. They are based on the threshold classification.

The main disadvantage of this approach is its significant sensitivity for intensity fluctuations (in case of MRI caused for example by magnetic field inhomogeneity, registered noise or even device's properties) -morphology-based methods. The basic idea is to combine the use of morphological operations, thresholding and edge detection techniques, in order to separate the area of the brain from the surrounding tissue in the most precisely way. -deformable model-based methods which applied the active contour deformation and fitting to localise brain area and its identification by using image characteristic.

The algorithm presented in this paper belongs to morphology-based methods' group. It was implemented using JAVA and MATLAB environment [START_REF] Landini | Advanced Image Processing in Magnetic Resonance Imaging[END_REF], [START_REF] Gonzalez | Digital Image Processing using Matlab[END_REF], [11]. The proposed method has 5 steps.

1. image thresholding (segmentation), 2. filling the gaps in extracted objects using morphological operators, 3. edge detection and improving the edges if it's needed 4. selection of the largest area in the image and creating a binary mask 5. combining the binary mask and the input image as an output image.

Image thresholding

Image thresholding is essential for best algorithm's effectiveness. It allows to separate the background noise and foreground brain tissues [START_REF] Tadeusiewicz | Pozyskiwanie obrazw medycznych oraz ich przetwarzanie, analiza, automatyczne rozpoznawanie i diagnostyczna interpretacja[END_REF]. In this paper 3 techniques were tested [START_REF] Landini | Advanced Image Processing in Magnetic Resonance Imaging[END_REF]:

-Global thresholding. It relies on selection of the arbitrary threshold (usually it is gray scale image mean or median intensity) and its comparing with each pixel value. If the value is greater than or equal to the threshold the pixel is converted to white (for values smaller than threshold pixel became black). -Local thresholding. In this method separate threshold is determined for a particular part of the image or each pixel individually. Frequently the threshold is calculated as mean or median intensity value in pixel's surrounding with defined radius. -Mixed thresholding which is the same as the local thresholding with only one difference: if the mean or median local to a given pixel differs, by more than a predetermined value from the global threshold, global thresholding is applied.

The best results were obtained for mixed thresholding method. Local thresholding leaves too many details in the image, which made it unclear with specific structures poorly separated. In case of global thresholding part of the important (from the diagnostic point of view) edges were removed from the image, what disqualifies this method for further application. In Figures 1,2, 3 the results for each technique and each imaging plane were presented.

Designing a mask for the brain extraction

The next step was to create a mask which multiplied by the input image would allow to extract only the brain tissue region. Mask was designed using morphological operations, which are based on the application of so called (structural element). It is a set of pixels which may have different shapes and sizes and contain any combination of 0 and 1 values. If pixel's value is not significant it could be marked in structural element as z. Following morphological operators were applied in proposed method:

-Dilatation (thickening) The structural element is compared with each pixel of the image. If at least one pixel the neighborhood has a value equal to "1", the focal point also receives it (in another case is assigned the value "0"). Types of structural element strongly affects the output image. -Erosion (thinning). This operation applies rotated structural element for each pixel in the image. If even one pixel in the neighborhood has a value equal to "0", the focal point also receives this value. Otherwise, its value does not change. This is an operation which is the inverse of dilatation. Erosion is significantly influenced by the choice of the structural element -Opening Imposition of dilatation operation on the result of the erosion of the original image.It causes image smoothing (removal of details, the greater the structural element is used, the stronger image smoothing can be observed). -Closing The imposition of erosion operations on the result of dilatation of the original image. It removes all the holes in the image and the concave lower than the structural element (the greater structural element, the more elements are filled in).

During creating the mask, the main goal was to examine the influence of the various structural elements (shape, size) and the sequence morphological operations selection, for the output mask image.Matlab packages allows to analyze up to nine types of structural elements with different shapes and sizes: diamond (with defined radius), disk (with defined radius), line (with defined length and angle), octagon (with defined distance from the structuring element origin to the octagon's size, along to the vertical and horizontal axis), pair (the structure with 2 elements), periodicline, rectangle (with specified 2-piece vector defining its size), square (with specified width) and even arbitrary structural element (shape defined by user). In the first step of choosing the optimal structural element, the line and periodicline options were rejected. Assuming that in each imaging plane, the brain structure is nearly symmetrical, structural element should not favor any processing direction. In a consequence it cannot take the angle as a procedure input parameter. In the next step, the square and rectangular structural elements were rejected as well form the further analysis.It was examined that increasing their size of even one pixel can cause unwanted sharpening of the brain edges. The mask constructing procedure should guarantee keeping the edges unchanged in their course and shape, because of their diagnostic value. On the other hand, rectangular structural element was used as very effective in later algorithm's stages for removing single black pixel (or small group of pixels) within a created mask. Disk, square, diamond and octagon structural elements were tested. It was assumed that due to the edge course, the structural element size can not be too high. Disk with radius equal to 3 has 25 elements (5x5 matrix)and square element with width equal to 5 and give same unsatisfactory results. Diamond with the same radius 3 and octagon in the smallest possible size has 49 elements (7x7 matrix). That is why the maximum acceptable radius of structural element was assigned as 2. For this size disk and diamond look identical. Finally, the disk element with radius equal to 2 was chosen as providing the best visual results. Unfortunately even then it was not possible to avoid leaving some small unwanted clusters of black pixels. In some cases these clusters caused additional signal areas extractions inside the mask area. Therefore in this step all the gaps in the image were removed by using morphological operators once again (square structural element as it was mentioned before). In Figures 4,5, 6 the received masks for each imaging plane were shown. From left to right: image after mixed thresholding, mask received after image erosion, mask revised by removing small areas from the image Fig. 6. The following steps of creating mask for brain region extraction (horizontal plane). From left to right: image after mixed thresholding, mask received after image erosion, mask revised by removing small areas from the image

Edge detection

Edge detection allows to verify if there is a correlation between the edges of the mask (applied for the brain extraction) and the anatomical edges of the input image. Overlap of the brain's boundaries in the input image with the boundaries set by the proposed skull stripping method would prove that algorithm is correct. For each imaging plane the Canny edge detection filter was applied. Next, image presenting the edges was combined with corresponding input image. In each case correlation was confirmed which means that mask corresponds to the brain area and that it can be applied for the brain extraction.

Selection of the largest area in the image

The main purpose of next step is to find the largest area in the image of connected white pixels representing the brain tissue. The goal was achieved by assigning labels to each object in the image and counting the number of pixels with a given tag. This operation was performed using built-in Matlab functions. Based on the results a mask representing the brain area was created. With the received mask it was possible to separate the brain tissue (represented by white pixels) from the area diagnostically irrelevant(background represented by black pixels). The last algorithm step was combining the the binary mask image and an input MRI image. The output image consists only this part of the input image that corresponds to the brain tissue. In Figure 8 the results of skull stripping for each imaging plane was shown. The method gave the satisfactory and promising results, although after more careful analysis it can be seen that some part of the information is missing. It is particularly visible on the edges of the isolated brain (white matter area). In addition, the edges are slightly sharpened, and in a consequence the shape of the brain is not recreated in an ideal way.

Comparison with other methods

To be able to fully evaluate the algorithm's capabilities it is necessary to compare it with other commonly used brain extraction methods. The most popular are AFNI (3DSkullStrip module)[13] and FSL (BET algorithm) [14]. AFNI approach is automated process based on three steps: preprocessing (removing artifacts and brain positioning), expanding a spherical surface Obtained images were compared with FSL-BET results and some alternative method, also based on using morphological operators. In case of alternative approach first step was image global thresholding with the threshold equals to After that small noise speckles were removed by using bwareaopen function(the concept of speckles means all connected components that have fewer than 10 pixels). In next step the holes in binary image were removed by applying imfill function. In a final step single erosion with disk structural element (radius 15) was made. The results of all method comparison were shown in Figures 9,[START_REF] Gonzalez | Digital Image Processing using Matlab[END_REF]11. As it can be seen only in case of horizontal plane all methods gave similar results. In case of sagittal and coronal plane, proposed in this paper method not only makes it possible to eliminate the skull structure but also extract only the brain tissue. This was possible thanks to an implementation in the algorithm the part which is responsible for the selection of the largest area in the image. Based on this area, filtration mask was built. It can also be noted that in the alternative method filtration leads to the removal some of the brain tissue sections which is unacceptable in case of diagnostic applications. In addition FSL methods in coronal plane leaves some redundant tissue. Another approach to verify the algorithm's effectiveness is to evaluate its performance in the boundary conditions. In this case, it is the analysis of images in which the share of the signal from the skull and the brain tissue is comparable. It turns out that the algorithm may encounter some difficulties at the stage of segmentation (thresholding). The main cause is the lack of the cerebrospinal fluid signal which low intensity (dark, similar to black color) would precisely separate two light areas: the skull and brain tissue. As a result, even in the case of mixed thresholding, automatically predetermined threshold is too low and the tissues are not separated properly. The implementation of further steps of the algorithm was considered unreliable. That is why algorithm's application in the boundary conditions will be a subject of further development and research. The obtained results was presented in Figure 12.

Summary and conclusions

In this paper a skull stripping method for T1-weighted MRI images based on using morphological operators was proposed. The algorithm gives satisfactory and promising results. However despite the fact the area of the skull was removed from the image completely, closer image analysis shows cerebrospinal fluid (CSF) space the was partially preserved, while it should be removed as well. This will be the subject of further work and algorithm improvement. Another challenge is to correct edge detection of the brain area i.e. by using morphological gradients. In the present algorithm's version, the edges are sharpened, what is related to the partial loss of information on the borders of the area. Proposed method was compared with the commonly used solutions which have certain limitations associated with programming environment (AFNI, FSL). The algorithm assured comparable and is some cases even better results. High efficiency of the algorithm is associated with the use of the thresholding as one of the basic processing steps which allows for precise separation of the structures. It is planned to perform the algorithm's evaluation on a large database of images to confirm its effectiveness for images with a higher degree of complexity. The algorithm has a preliminary study status, therefore it is also planned in a future to compare its efficiency with other common used skull stripping methods and taking into consideration gray-scale morphology. .

Fig. 1 .Fig. 2 .

 12 Fig. 1. Different thresholding method comparison (sagittal plane). From left to right: input image, global threshold, local threshold, mixed threshold

Fig. 3 .

 3 Fig. 3. Different thresholding method comparison (coronal plane). From left to right: input image, global threshold, local threshold, mixed threshold

Fig. 4 .Fig. 5 .

 45 Fig. 4. The following steps of creating mask for brain region extraction (coronal plane). From left to right: image after mixed thresholding, mask received after image erosion, mask revised by removing small areas from the image

Fig. 7 .

 7 Fig. 7. The effect of imposing the edge of the brain extraction mask on the input image (in all planes)

Fig. 8 .

 8 Fig. 8. Skull stripping result after algorithm implementation in all planes

Fig. 9 .Fig. 10 .

 910 Fig. 9. Comparison of the proposed method (b), FSL-BET result (c) and the alternative Matlab approach (d). Horizontal plane. Methods description was presented in the text

Fig. 12 .

 12 Fig. 12. Different thresholding method comparison (horizontal plane). From left to right: input image, global threshold, local threshold, mixed threshold

Table 1 .

 1 Comparison of the Author's method with FSL and AFNI approach.

	Criteria	Author's method	FSL	AFNI
	Supported files DICOM, JPG, BMP, PNG, TIFF NIFTI, DICOM	NIFTI, DICOM
	Operating system	WINDOWS	Unix, Mac OS	Unix, Mac OS
	Difficulties	-	--	at least 16 scans required


J Balicki
email: balicki@eti.pg.gda.pl

W Korłub

J Paluszak
email: jpaluszak@gmail.com

M Tyszka

Harmony search for self-configuration of fault-tolerant and intelligent grids

In this paper, harmony search algorithms have been proposed to selfconfiguration of intelligent grids for big data processing. Self-configuration of computer grids lies in the fact that new computer nodes are automatically configured by software agents and then integrated into the grid. A base node works due to several configuration parameters that define some aspects of data communications and energy power consumption. We propose some optimization agents that are based on harmony search to find a suboptimal configuration of fault-tolerant grids processing big data. Criteria such as probability that all tasks meet their deadlines and also a reliability of grid are considered. Finally, some experimental results have been considered.

Introduction

An intelligent grid is supposed to manage its resources to meet the task requirements on the way to achieving the common objective. Self-configuration of computer grids lies in the fact that new computer nodes are automatically configured by software agents and then integrated into the grid. The whole process of self-configuration is similar to the "plug-and-play" rule for some operating systems. However, configuring agents launch connectivity and download some configuration parameters. If a new computer node is added to the middleware layer and powered on, it is instantly identified and registered by configuration agents.

A base node works due to several configuration parameters that define some aspects of data communications and energy power consumption. These parameters can be improved to change grid behavior, based on some administrator observations. Another way is to delegate this competences to optimization agents they find the most adjusted configuration to the workload and resource using. One of the most commonly used criterion of grid behavior is its reliability that should be maximized. The main dilemma is the fact that this problem is NP-hard and it is impossible to find an optimal configuration for hundreds of nodes.

In the presented model, we propose some optimization agents that are based on harmony search to find a suboptimal configuration of fault-tolerant grids processing big data. A fault-tolerant grid deals with failures of its nodes and software where each node has some duplicated servers associated with its [START_REF] Varvarigou | Module replication for fault-tolerant real-time distributed systems[END_REF]. One node is the primary, and some associated nodes are dedicated for backup [START_REF] Huang | Improve availability of fault-tolerant computing: Optimal multi-task allocation in MapReduce[END_REF]. Tasks are performed by primary and backup servers, concurrently. Another model of grid is based on assumption that there are no fault-tolerant nodes. A grid node cooperates with other nodes as backups. In case of a node failing, all tasks allocated to this server are re-allocated to one of its backups. Some algorithms of resource using take into account the failure/repair rates and the fault-tolerant overheads. These algorithms can improve the grid performance meaningfully, but the quality of configuration and delay for its founding are still under construction [START_REF] Kafil | Optimal Task Assignment in Heterogeneous Distributed Computing Systems[END_REF][START_REF] Węglarz | Preemptable malleable task scheduling problem[END_REF].

In this paper, an outlook of harmony search metaheuristics is discussed in Section 2. Moreover, specific aspects for big data are presented in Section 3. Especially, Map-Reduce model for BD processing is studied in Section 4. Then, intelligent agents based on harmony search for improvement of fault-tolerant measure are described in Section 5. Moreover, some outcomes from numerical experiments are interpreted in Section 6.

Outlook of Harmony Search Metaheuristics

Harmony search can be applied for self-configuration support of some fault-tolerant grids. Harmony search metaheuristics HS models phenomena related to the process of playing on musical instruments [41]. An optimization process can be compared to a process of selection the best sound while improvising jazz musicians. Similarly, a conductor of orchestra searches the best harmony of several instruments or a compositor creates the best melody for different music lanes [START_REF] Afshari | Application of an improved harmony search algorithm in well placement optimization using streamline simulation[END_REF]. The HM concept was suggested by Zong Woo Geem [START_REF] Geem | A new heuristic optimization algorithm: harmony search[END_REF][START_REF] Zou | A novel global harmony search algorithm for reliability problems[END_REF]. Figure 1 shows a diagram of the basic version of the HS metaheuristics [START_REF] Ahmed | Harmony search algorithm for optimal word size in symbolic time series representation[END_REF].

The HS algorithm determines a solution for one-criterion optimization problem with continuous decision variables that can be formulated, as follows [START_REF] Al-Betar | University course timetabling using a hybrid harmony search metaheuristic algorithm[END_REF]:

min 𝑥∈𝑿 𝑓(𝑥), (1)
where:

f(x) -a value of an objective function f for solution x∈ 𝑿, 𝑓: 𝑹 𝐽 𝑚𝑎𝑥 → 𝑹;

x -a vector of decision variables, x=[x 1 ,…,x j ,…,𝑥 𝐽 𝑚𝑎𝑥 ] T for 𝑙 𝑗 ≤x j ≤ 𝑢 𝑗 , j= 1, 𝐽 𝑚𝑎𝑥 ̅̅̅̅̅̅̅̅̅ ;

𝐽 𝑚𝑎𝑥 -a number of decision variables;

X -a set of decision variables.

The lower limit vector is 𝑙 = [𝑙 1 , … , 𝑙 𝑗 , … , 𝑙 𝐽 𝑚𝑎𝑥 ] 𝑇 and the upper limit vector is 𝑢 = [𝑢 1 , … , 𝑢 𝑗 , … , 𝑢 𝐽 𝑚𝑎𝑥 ] 𝑇 , wherein 𝑙 𝑗 ∈ 𝑹, 𝑢 𝑗 ∈ 𝑹, 𝑙 𝑗 ≤ 𝑢 𝑗 for 𝑗 = 1, 𝐽 𝑚𝑎𝑥 ̅̅̅̅̅̅̅̅̅ . An initialization the harmonic memory HM (Fig. 1) occurs after setting the following parameters:

• HMS -Harmony Memory Size;

• HMCR -Harmony Memory Considering Rate is the probability of a random event that the value of the decision variable during improvisation (constructing a solution) is drawn from the memory HM; an uniform distribution is assumed to draw;

• PAR -Pitch Adjusting Rate is the rate of the randomly selected decision variable;

• NGmax -Number of Generations (Improvisations);

• BW -Bandwidth of Generations that is the width of the interval to modify the value of the decision variable that is randomly selected from memory; the new value of the decision variable is modified by adding the value from the range [-BW, BW]. case of violation of restrictions. The efficiency of each solution can be increased by an amount such that the accepted value of non-negative. The basic version of the harmony search algorithm has been repeatedly modified to adjust to solve some optimization problems [START_REF] Leyton-Brown | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF].

Intelligent Agent Architecture for Big Data

Big data (an acronym BD) is related to databases with petabyte capacities 10 15 B. 10 terabytes is a large capacity for a financial transaction system, but it is too small to test a web search engine. BD is uncooperative to work with using some relational database management systems like DB2, INGRES, Oracle, Sybase or SQL Server. Big data requires hundred thousand processors for data processing like supercomputers [START_REF] Shwe | A fault tolerant approach in cluster computing system[END_REF], grids [11] or clouds [START_REF] Balicki | Big data paradigm developed in volunteer grid system with genetic programming scheduler[END_REF]. Especially, cloud architectures are preferred to BD processing because of commercial data centers with expensive information. Tasks developed SQL-like queries to BD are massive parallel because the short time of a query performing is required. For instance, a query for multi-terabyte datasets at BigQuery service in Google Cloud is performed during few seconds. BigQuery service is scalable cloud like IaaS Infrastructure as a Service. Furthermore, this RESTful web service enables interactive analysis cooperating with Google Storage [START_REF] Gunarathne | Cloud computing paradigms for pleasingly parallel biomedical applications[END_REF]. The most important tasks are related to analytics, capture, search, sharing, storage, and visualizing. Moreover, some BD mining tasks can be used to find predictions as well as some descriptive statistics tasks can be developed for business intelligence [START_REF] Li | Application of Multilayered Multi-Agent Data Mining Architecture to Bank Domain[END_REF].

BD can be characterized by the 4Vs model due to high volume, extraordinary velocity, great data variety, and veracity. Data can be captured via Internet of Things from different sensors like smartphones, tablets, microphones, cameras, computers, radars, satellites, radio-telescopes and the other sensors. Moreover, data can be captured from social networks. A storage capacity can achieve many petabytes for one volume that is high volume [START_REF] Marz | Big data -Principles and best practices of scalable realtime data systems[END_REF]. MongoDB is one of perspective solutions for BD because the NoSQL database supports data stored to different nodes. Mongo DB can cooperate with massively parallel cluster with lots of CPUs, GPUs, RAM units and disks [START_REF] De | Artificial Intelligence and Big Data[END_REF]. A crucial problem with BD is related to reading from a storage system to obtain the rapid answer on a complex query that is divided on some parallel operations acting on diverse data. Big data can be spread over some partitions that run on some separate modes with own table spaces, logs, and configurations. In that case, a query is performed on all partitions concurrently [START_REF] Snijders | Big Data': Big gaps of knowledge in the field of Internet[END_REF]44].

In an experimental grid called Comcute, two kinds of intelligent tasks have been considered to implement a middleware layer [START_REF]Comcute[END_REF]. This grid is dedicated to parallel computting with using volunteer computing. Agents for data management send data from source databases to distribution agents. Then, distribution agents cooperate with web computers to calculate results and return them to management agents. Both types of agents can autonomously move from one host to another to improve quality of grid resource using. Moreover, the other agents based on harmony search have been introduced to optimize big data processing regarding some fault-tolerant aspects. These harmony search schedulers can cooperate with distributors and managers to give them information about optimal workload in a grid [START_REF] Balicki | Multicriteria evolutionary algorithm with tabu search for task assignment[END_REF][START_REF] Balicki | Genetic programming with negative selection for volunteer computing system optimization[END_REF].

The lambda architecture is developed for real-time BD analysis [START_REF] Marz | Big data -Principles and best practices of scalable realtime data systems[END_REF]. The batch layer of this architecture supports offline data processing by MapReduce framework [START_REF] Vavilapalli | Apache hadoop yarn: Yet another resource negotiator[END_REF]. This layer produces batch views of data, which can be exposed to external applications (Fig. 2). The serving layer offers prepared views to clients. The speed layer is responsible for real-time processing of data streams. It analyses data that was not yet processed by the batch layer. Speed layer produces real-time views that can be coupled with batch views to create complete representation of the extracted knowledge [START_REF] Jennings | Applications of intelligent agents[END_REF]. Fig. 2. Multi-agent real-time processing utilizing lambda architecture [START_REF] Twardowski | Multi-agent Architecture for Real-Time Big Data Processing[END_REF] The lambda architecture can be defined in terms of a heterogeneous multiagent system [START_REF] Twardowski | Multi-agent Architecture for Real-Time Big Data Processing[END_REF]. An implementation requires integration of a few components: one for batch processing, another one for serving views, a different solution for real-time stream analysis and a component that merges real-time views with batch views [START_REF] Wooldridge | Introduction to MultiAgent Systems[END_REF].

The use of multiagent environment will provide a common way for information exchange between different component and a common execution model [START_REF] Verbrugge | A coevolutionary differential evolution with harmony search for reliabilityredundancy optimization[END_REF]. The differences between individual components of the lambda architecture lead to inherently heterogeneous realizations so the ability to handle diversity in agent systems in another motivation for this approach [START_REF] Leyton-Brown | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF].

Map-Reduce Model for Fault-Tolerant Grid

Grid and volunteer computing systems are different from super-computing systems because inexpensive hardware commodities have been widely deployed, which is helpful to the scalability. But it also brings a large number of hardware failures. Moreover, many machines constantly restart to update systems, which cause huge software failures [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF]. Similarly, the popular cloud computing model MapReduce also has to overcome the failures [START_REF]Apache Hadoop[END_REF][START_REF] Balicki | An Adaptive Quantum-based Multiobjective Evolutionary Algorithm for Efficient Task Assignment in Distributed Systems[END_REF].

When a job consists of thousands tasks, the possibility of a few failed tasks is very high. Several fault-tolerant applications can be executed in the platform, which can use the result despite of some failed tasks. To support such fault-tolerant computing, an open source implementation of MapReduce can be applied. Hadoop has already provided the interface, by which the job can tolerate a given percentage of failed tasks. It was observed that optimizing the availability of individual task is not an effective approach for ensuring the high availability of these multi-task jobs [START_REF] Qiu | Using MapReduce Technologies in Bioinformatics and Medical Informatics[END_REF].

However, Hadoop implicitly assume the nodes are homogeneous, but it doesn't hold in practice. These motivate to propose an optimal multi-task allocation scheme towards heterogeneous environments, which can tolerant a given percentage of failures to total tasks [START_REF] Ostrowski | MapReduce Design Patterns for Social Networking Analysis[END_REF]. In this case the reduce function's responsibility is to sum the each key's values [START_REF] Shvachko | The Hadoop distributed file system[END_REF].

MapReduce is applied to solve several problems like large-scale machine learning for the Google News. Moreover, an extraction of data is used to produce reports of popular queries and extraction of geographical locations from a large corpus of web pages for localized search. In 2004, Google changed an indexing system that produces data used for web search service to system that used MapReduce. The new indexing system takes input documents that have been retrieved from a crawling system store as a set of files, and then they are processed by from five to ten MapReduce operations. It is easier to operate because of automatic resolving problems like machine failures, slow machines and networking hiccups [START_REF] Guojun | Large-Scale Social Network Analysis Based on MapReduce[END_REF][START_REF] Mardani | Fraud detection in Process Aware Information systems using MapReduce[END_REF].

Harmony Search Agents for Local Grid Self-configuration

Intelligent agents can optimize a grid resource management for tasks related to big data queries. An agent based on harmony search metaheuristics AHS can reconfigure a local part of a grid. The whole grid is divided on zones and the AHS is assigned to its grid zone to support self-optimization of a system. The main part of AHS is a multi-objective scheduler for tasks from a middleware layer. This scheduler optimizes a probability that all tasks meet their deadlines, and the grid reliability [START_REF] Cao | Agent Mining: The Synergy of Agents and Data Mining[END_REF]. We assume that each computer and each link between them are assumed to fail independently with exponential rates. It is preferred to allocate modules to computers on which failures are least likely to occur during the execution of task modules [START_REF] Ajith | Algorithms for reliability-oriented module allocation in distributed computing systems[END_REF]. The rationale assumption is that repair and recovery times are largely implementationdependent. Moreover, repair and recovery routines usually introduce too high time overheads to be used on-line for time-critical applications [START_REF] Balicki | Negative selection with ranking procedure in tabu-based multi-criterion evolutionary algorithm for task assignment[END_REF].

The overhead performing time of the task T v by the computer } ,..., ,..., { 1

J j j       
is represented by t vj . Let the computer j  be failed inde- pendently due to an exponential distribution with rate j  . Computers can be allocated to nodes and also tasks can be assigned to them in purpose to maximize the reliability function R, as below [START_REF] Kartik | Task allocation algorithms for maximizing reliability of distributed computing systems[END_REF]:

), exp( ) ( 1 1 1       V v I i J j ij m vi vj j x x t x R   (1)
where 3 shows the relation between the measure of system reliability R and time of using this system for the chosen two-computer system for λ 1 =0.001 [TU -1 ] and λ 2 =0.002 [TU -1 ]. Task scheduling algorithm

      ,
T IJ Ij I ij J m VI m vi m I m x x x x x x x x x x        Figure
Let the distributed application A n starts running after λ n and complete it before δ n [31]. Figure 4 shows an example of the task flow graph for two applications. Task m 2 is performed with the probability q in a sub-graph denoted as OR (Fig. 4) and task m 3 -with the probability (1-q). Task may be performed at the most L max times in a subgraph denoted as Loop, and each repetition of this module is performed with the probability p. The task flow graph is split on some instances to schedule tasks if the subgraph OR appears. There are 2L max instances for the task graph from Figure 4. The instance, where task m 2 appears and task m 5 runs k times, occurs with the probability:

p i =q(1-p) p k-1 (2)
An allocation of modules to computers )) ( (

 . ( 3
)
Probability that all tasks meet their deadlines for K instances of the flow graph is calculated, as follows [START_REF] Shatz | Models & algorithms for reliability-oriented task-allocation in redundant distributed-computer systems[END_REF]:

      K i M m v v i D i v x C d p x P 1 )) ( ( ) (  . ( 4
)
Fig. 4. A flow graph for two applications Figure 5 shows an example of a compromise configuration for its middleware zone in the Comcute grid that was found by the agent based on the harmony search for its area consisted on 14 modules divided among 2 computers. NP-hard multi-objective optimization problem of grid resource using to improve the level of fault-tolerance.

Our future works will focus on testing the other AI algorithms to find fault-tolerant configurations. Moreover, quantum-inspired algorithm can support big data, too [START_REF] Balicki | An Adaptive Quantum-based Multiobjective Evolutionary Algorithm for Efficient Task Assignment in Distributed Systems[END_REF].

Fig. 1 .

 1 Fig. 1. A diagram of the harmony search algorithm[START_REF] Paluszak | Optimizing the use of resources in distributed systems with grid architecture[END_REF]

Fig. 3 .

 3 Fig. 3. The time-depended reliability of two-computer system

.

  schedule tasks for each computer. Times of task completions (C 1 ,...,C v ,...,C V ) can be calculated for scheduled allocation modules to computers x. Let d v represents the completion deadline for the vth task. If v v d C  , then the time constraint is satisfied what can The state of deadline constraints regarding the ith instance of the flow graph with the set of tasks marked M i is determined, as below [32]:

Fig. 5 .

 5 Fig. 5. A compromise configuration in the Comcute grid: a) criterion space b) a solution