Pawe L Rajba
email: pawel.rajba@uwr.edu.pl

Mieczys Law Wodecki
email: mieczyslaw.wodecki@uwr.edu.pl

Sampling method for the flow shop with uncertain parameters

Keywords: flowshop with deadlines, uncertain parameters, tabu search, normal distribution

In the classic approach for optimization problems modelling well defined parameters are assumed. However, in real life problems we find ourself very often in a situation where parameters are not defined precisely. This may have many sources like inaccurate measurement, inability to establishing precise values, randomness, inconsistent information or subjectivity.

In this paper we propose a sampling method for solving optimization problems with uncertain parameters modeled by random variables. Moreover, by applying confidence intervals theory, the execution time has been significantly reduced. We will also show an application of the method for the flowshop problem with deadlines and parameters modeled by random variables with the normal distribution.

Introduction

Practical machine scheduling problems are numerous and varied. They arise in diverse areas such as flexible manufacturing systems, production planning, communication, computer design, etc. A scheduling problem consists in finding sequences of jobs on given machines with the objective of minimizing some function. In a simpler version of the problem, the flow shop scheduling, all jobs pass through all machines in the some order. In this paper, we deal with another specific version of the problem called a permutation flow shop scheduling problem where each machine processes the jobs in the same order (F ||w i U i ).

Research concerning problems of algorithms arrangement refers mainly to deterministic models ( [START_REF] Aarts | Local search in combinatorial optimization[END_REF]). To solve such problems, which belong in the majority of cases to the NP-strongly hard class, rough algorithms are applied successfully ( [START_REF] Bożejko | Solving Flow Shop Problem by Parallel Simulated Annealing[END_REF], [START_REF] Grabowski | A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion[END_REF], [START_REF] Nowicki | A Fast tabu search algorithm for permutation flow shop problem[END_REF]). They are mainly based on local optimalization methods: simulated annealing, tabu search and a genetic algorithm. Determined by these algorithms, solutions only slightly differ from best solutions. However, in practice, in the course of a process realisation (according to the fixed schedule) very often it appears that certain parameters (e.g. the task completion time) are different from the initial ones. By the lack of the solutions stability in the fixed schedule there may occur a big mistake, which makes such a schedule unacceptable. That's why a necessity exists to construct such models and methods of their solutions that would take into account potential changes in the course of parameters process realisation and generate stable solutions ( [START_REF] Bożejko | Scheduling Problem with Uncertain Parameters in Just in Time System[END_REF], [START_REF] Rajba | Stability of scheduling with random processing times on one machine[END_REF], [START_REF] Zhu | General Stochastic Single-Machine Scheduling with Regular Cost Functions[END_REF]).

Problems of arrangements with uncertain data may be solved using methods based on elements of probability calculus ( [START_REF] Van Den Akker | Minimizing the number of late jobs in a stochastic setting using a chance constraint[END_REF], [START_REF] Vondrák | Probabilistic methods in combinatorial and stochastic optimization[END_REF], [START_REF] Dean | Approximation algorithms for stochastic scheduling problems[END_REF]). In this work we deal with the flow shop problem of tasks arrangement with the latest completion times and the minimalisation of the costs sum of tardy tasks ( [START_REF] Jang | Minimizing the expected number of tardy jobs when processing times are normally distributed[END_REF], [START_REF] Righter | Stochastic Scheduling[END_REF]). On the basis of this problem the resistance to a random variable of constructive solutions of parameters according to tabu search metaheuristics is examined.

In this study, permutation flow shop scheduling problem of the typical situation of the flexible production systems which occupy a very important place in recent production systems are taken into consideration with random variables due dates.

Flowshop problem

Let J = {1, . . . , N } be a set of jobs to be executed on M machines from the set M = {1, . . . , m}. At any given moment a specific machine can execute at most one job and all jobs needs to be executed without the preemption. Any job j ∈ J needs to be executed in sequence on every machine and if a job is being executed on the machine k then it means that it has been executed on machine the k -1 (k = 2, 3, . . . , M ). Jobs are executed in a given order determined by a permutation with a constraint that the permutation is applied on all machines. The execution of a job on a machine is named operation. In this section we consider flowshop problem with due dates defined as a set (p i,j , w i , d i ) (i = 1, . . . , N , j = 1, . . . , M ) where p i,j are processing times of operations, w i are weights for all jobs and d i are due dates for all jobs, but they are defined as random variables with the distribution

N (d i , c • d i ).
Let Π be the set of all permutations of the set J . For every permutation π ∈ Π we define

C π(i),j =      i k=1 p π(i),j , dla j = 1, C πi,j-1 + p π(i),j , dla i = 1, j > 1, max{C πi,j-1 , C πi-1,j } + p π(i),j , dla i > 1, j > 1,
as a completion time of execution job i on machine j in reference to permutation π.

The cost of execution of operations determined by permutation π is as follows

n i=1 w π(i) Ũiπ(i) .
where

Ũiπ(i) = 0 dla C π(i) d iπ(i) , 1 dla C π(i) > d iπ(i) .
We consider the optimization problem where the goal is to find a permutation π * ∈ Π which minimizes cost of execution of all operations:

W (π * ) = min π∈Π n i=1
w π(i) Ũiπ(i) .

Tabu search

Rough algorithms are used mainly to solve NP-hard problems of discrete optimization. Solutions determined by these algorithms are found to be fully satisfactory (very often they differ from the best known solutions approximately less than a few percent). One of realizations of constructive methods of these algorithms is the tabu search, whose basic elements are

• movement -a function which transforms one task into another,

• neighborhood -a subset of acceptable solutions set,

• tabu list -a list which contains attributes of a number of examined solutions.

Let π ∈ Π be a starting permutation, L T S a tabu list and π * the best solution found so far.

Algorithm 1 Tabu Search 1: repeat 2:
Determine the neighborhood N (π) of permutation π 3:

Delete from N (π) permutations forbidden by the list LTS 4:

Determine a permutation δ ∈ N (π), such that F(δ) = min{F(β) : β ∈ N (π)} 5:

if F(δ) < F(π * ) then 6:

π * := δ 7:

Place attributes δ on the list LTS 8:

π := δ 9: until the completion condition

Movement and Neighborhood

Let π = (π(1), . . . , π(n)) be any permutation from the set Π. By π k l (l = 1, 2, . . . , k -1, k + 1, . . . , n) we denote the permutation obtained from π by a change of positions π(k) with π(l). We say, in such a case, that a π k l permutation was generated from π by a type of a swap move s k l (i.e. a permutation π k l = s k l (π)). Then, let M (π(k)) be a set of swap moves of an element π(k), a set of all such movements

M(π) = π(k)∈L(π) M (π(k)).
The neighborhood of an element π ∈ Π is a set of permutations

N (π) = s k l (π) : s k l ∈ M(π) ∩ L(π) ,
where

L(π) = {π(i) : C π(i) > d π(i) } is a set of delay solutions in π.
By implementing an algorithm from the neighborhood permutations whose attributes are on the tabu list L TS are removed.

The Tabu Moves List

To prevent a cycle from arising some attributes of each movement are put on the list of tabu moves. It's served by means of the FIFO queue. Performing a movement s r j ∈ M(π) (i.e. generating it from π ∈ Π the π r j permutation) on the tabu list L T S attributes of this movement, i.e. the triple (π(r), j, F(π r j )) are put down.

Assuming that we examine a movement s k l ∈ M(β) generating from β ∈ Π a permutation β k l . If on the list L T S there is a triple (r, j, Ψ ) such that β(k) = r, l = j and F(β k l ) ≤ Ψ , then such a movement is forbidden and removed from the set M(β).

Robustness

Due to the fact that we consider uncertain environment and the actual values are not known at the moment of the algorithm execution, we need a way to measure the quality of solutions. We assume that we have a set of reference test data and there are two algorithms: the examined one and the reference one (classic in our paper). The scenario of verification is as follows. For a specific test instance both algorithms propose solutions π p (examined) and π d (reference) which we expect to be robust. Then we generate a set of disturbed subinstances based on the test instance and for every subinstance we calculate the cost of execution with reference to π p (cost w p ) and π d (cost w d ). We also calculate an "almost optimal" solution for the subinstance w * . Having that we calculate a relative error for all subinstances, then calculate relative error for all instances and by that we are able to take conclusion about the algorithm. We do that for both algorithms and compare the final values.

More formally, let define the basic robustness coefficient as a relative distance between examined and the reference solution, i.e. let w be a cost of "robust" solution (w p or w d ) and w * be the reference "almost optimal" solution cost. Then relative error

δ = w -w * w * 100%
and it shows how many percent w is worse than w * .

In some scenarios we need to compare the sets of values based on the disturbed data, so we propose an extension to the basic error definition. Let consider s disturbed data instances, w 1 , . . . , w s be cost values obtained by examined algorithm and w * 1 , . . . w * s be reference cost values. Then we define extended relative error as follows:

∆ = w1+...+wn n - w * 1 +...+w * n n w * 1 +...+w * n n = (w 1 + . . . + w n ) -(w * 1 + . . . + w * n ) w * 1 + . . . + w * n
Let ψ be a data instance, D(ψ) be a set of disturbed data subinstances obtain from ψ based on the random variable d i and -A ref be an algorithm which find the reference solution, -A be the examined algorithm, π M,x be a solution obtained by algorithm M ∈ {A, A ref } for the problem instance x, -W (π M,x , y) be the cost of instance y calculated by applying a solution π M,x .

Then

∆(A, ψ, D(ψ)) = ϕ∈D(δ) W (π A,ψ , ϕ) -ϕ∈D(δ) F (π A ref ,ϕ , ϕ) ϕ∈D(δ) W (π A ref ,ϕ , ϕ)
, we define as solution robustness π A,ψ (obtained by the algorithm A for instance ψ) based on set of disturbed data D(ψ).

Let Ω be a set of test data for the examined problem. Then by

S(A, Ω) = 1 Ω ψ∈Ω ∆(A, ψ, D(ψ)) (1)
we define as the robustness coefficient for the algorithm A on the set of test data Ω. The less the value is, the better the algorithm is, i.e. solutions obtained by the examined algorithm are more robust and random changes in the actual data don't affect significantly the final execution cost.

Sampling method

The idea of the method is as follows. In every tabusearch algorithm iteration we are testing different candidate solutions from the neighbourhood to find the best one and improve the current global best solution. Let assume an instance (p i,j , w i , d i ) and that we examine the candidate solution, a permutation π. Due to the fact that d i is defined as random variable, we don't know the actual data that may come. What we propose in the sampling method is to simulate this actual scenario by testing the candidate solution on a sample of disturbed data generated from d i . We can describe the method in the following main steps:

1. Generate l vectors d k = (d k 1 , . . . , d k N ),
where k ∈ {1, . . . , l}. By that we get l deterministic instances (p i,j , w i , d k ).

2. For every deterministic instance a cost is calculated based on the candidate solution π. By that we obtain sample W π 1 , . . . , W π l . 3. We calculate a mean x and a standard deviation from s the sample which are used in the comparison by tabusearch. Of course less is better.

One can easily notice that in the above description we are missing the size of the sample, i.e. the value of l. We want the l to be as small as possible and meaningful on the other hand. To determine that we apply confidence intervals theory with the standard significance level α = 5%. Please note that we don't know the distribution of the sample W π 1 , . . . , W π l . By that we apply the following variant of significance level formula:

x -µ α s √ l < m < x + µ α s √ l
where l is a sample size (at least 30), x is the sample mean, s is the sample standard deviation and µ α is the value of random variable N (0, 1) under the condition:

Φ(µ α ) = 1 - α 2
what, according to the assumptions, provide µ α = 1, 96.

To sum up, the comparison criteria in the tabusearch method needs to be extended by the following code: Go to point 3

A remark: random sample don't need to be generated with every calculation of comparison criteria function. It is enough to generate it once for a specific data instance and this way it has been implemented in the computational experiments.

Computational experiments

In this section we describe the method for generating random data and elaborate the efficiency of the proposed method. The tabu search algorithm presented in section 3 has been appropriately applied. As a reference algorithm we use classic deterministic implementation of tabusearch which we compare with the adaptation of tabusearch for the sampling method. Moreover, the following customization has been applied:

start permutation: π = (1, 2, . . . , n), tabu list size: n, algorithm's iterations count: n.

In order to measure the efficiency of the proposed method we examine the computational complexity by checking samples' size and the robustness.

Test data

Both implemented algorithms have been examined on the commonly used reference test data which comes from [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF] where he hired variants with jobs' numbers N = 20, 50, 100 and machines' numbers M = 5, 10, 20 what give 9 combinations. For every combination 10 examples are available so in total we have 90 test examples. Due to the fact that published examples consist of only processing times we needed to complete those examples by generating weights (w i ) and due dates (d i ). We applied the following schema: w i has been generated uniformly from the range [START_REF] Aarts | Local search in combinatorial optimization[END_REF][START_REF] Righter | Stochastic Scheduling[END_REF] and d i has been generated uniformly from the range [P (1 -T -R/2), P (1 -T + R/2)] where P denotes the best known value for the makespan for the C max problem, T = 0.3 and R = 0.3 ( [11]).

Based on the reference data we create the random instances (p i,j , w i , d i ) as formulated in the problem definition in section 2 where p i,j and w i values come from previously described examples and d i ∼ N (d i , c • d i ) where c ∈ {0.05, 0.1, 0.15, 0.2, 0.25, 0.3}. Having that for every random instance we generated 100 disturbed deterministic subinstances according to distribution of the random variable d i , in total we obtained 90 • 5 • 100 = 54000 subinstances. The robustness coefficient 1 has been determined for both algorithms and results are presented in the next section.

Results

Before performing the complete set of tests we have checked whether sample measure on the mean only is good enough or is it worth introduce the standard deviation as well. It turned out the introducing standard deviation has a negligible influence on the final result, so all the tests have been executed with applying the mean only.

We executed tests for two main algorithms, but we examined the proposed method in more details to have a better insight into value that it brings. In the Tables 1, 2, 6.2, 6.2, 6.2, 6.2, 6.2, 6.2 there is a complete summary of all tested variants with main results. A quick observation leads to the conclusion that the proposed method gives much better results than the classic approach. Moreover, in all cases the results obtained by applying the sampling method are better in the sense of statistical significance than results obtained by the classic way. The only thing which is puzzling is the fact that the more value c is the less advantage of sampling method is. Another general observation is that for almost all test instances the sampling method gives better robustness than the classic approach. When the sample size is based on confidence intervals theory, we obtain the level 98, 5% of advantage. The best one is for the sample size N • M when we have the value 99, 4%. Even for a small sample size N • M • 0.03 the sampling method gives the level 92, 3% of advantage, finally we lose the advantage for a very small sample size N • M • 0.01.

Let's take a closer look at the relationship between the classic approach, the sampling one with sample size N M and the sampling one with sample size based on confidence intervals based sample size. On the chart one can see the robustness level (Figure 1). We can easily observe that for all values of parameter c the advantage of the sampling method is indisputable. We can also observe that we can get the best robustness when the sample size is N M . Finally, let's discuss the relationship between the algorithms' results with different sample size with reference to the robustness level (Figure 2). We can see that within the range [1..0.1] • N M the robustness levels are very close to each other. Only when the sample size is getting smaller (from 0.05N M ), the robustness level is getting significantly worse. In this paper we proposed a sampling method to solve optimization problems with uncertain parameters modeled by random variables. By applying confidence intervals we wanted to keep a very good balance between the execution time and the robustness level. We have seen an application of the method for the flowshop problem with deadlines and parameters modeled by random variables with the normal distribution. Based on the performed computational experiments we can conclude that the proposed method gives substantially more robust solutions than the classic approach and by applying confidence interval theory we achieve the goal of keeping balance between the execution time and the robustness level.

Function 2 4 : 5 :

 245 Extention for comparison criteria in tabu search 1: z ← 0 current number of generated vectors 2: l ← 30 3: Generate l -z vectors (d k = (d k 1 , . . . , d k N ), where k ∈ {1, . . . , l}. By that we have l instances (pi,j, wi, d k ) For every new instance calculate cost in context of candidate solution π. We obtain sample W π 1 , . . . , W π l . Calculate mean x and standard deviation s from sample. 6: z ← l 7: if d 5%x or l > N • M then 8: return (x, s) 9: else 10: l ← l + 10%l 11:

Fig. 1 .

 1 Fig. 1. Comparison of the robustness level with reference to the main methods

Fig. 2 .

 2 Fig. 2. Comparison of the robustness level with reference to the sample size

Table 1 .

 1 Complete results summary for confidence intervals sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,79	0,26	2,04	75,48	89
	0,10	1,36	0,66	1,08	79,26	89
	0,15	2,00	1,14	0,75	83,17	89
	0,20	2,62	1,64	0,59	90,16	89
	0,25	3,31	2,27	0,46	89,54	88
	0,30	3,66	2,60	0,41	91,67	88
	Average	2,29	1,43	0,89	84,88	88,7

Table 2 .

 2 Complete results summary for N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,82	0,25	2,25	661,11	90
	0,10	1,38	0,63	1,21	661,11	90
	0,15	1,99	1,08	0,85	661,11	89
	0,20	2,63	1,59	0,66	661,11	90
	0,25	3,24	2,11	0,53	661,11	90
	0,30	3,61	2,47	0,46	661,11	88
	Average	2,28	1,35	0,99	661,11	89,5

Table 3 .

 3 Complete results summary for 0.3 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,82	0,26	2,11	198,33	87
	0,10	1,37	0,64	1,14	198,33	90
	0,15	2,00	1,11	0,80	198,33	89
	0,20	2,66	1,66	0,60	198,33	90
	0,25	3,25	2,15	0,51	198,33	89
	0,30	3,63	2,50	0,45	198,33	88
	Average	2,29	1,39	0,94	198,33	88,8

Table 4 .

 4 Complete results summary for 0.15 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,81	0,27	2,00	99,22	89
	0,10	1,37	0,65	1,12	99,22	90
	0,15	2,00	1,14	0,75	99,22	89
	0,20	2,64	1,69	0,57	99,22	89
	0,25	3,25	2,21	0,47	99,22	88
	0,30	3,67	2,60	0,41	99,22	88
	Average	2,29	1,43	0,89	99,22	88,8

Table 5 .

 5 Complete results summary for 0.1 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,80	0,28	1,86	66,11	87
	0,10	1,36	0,67	1,03	66,11	90
	0,15	1,98	1,17	0,70	66,11	89
	0,20	2,63	1,70	0,55	66,11	89
	0,25	3,26	2,26	0,44	66,11	87
	0,30	3,69	2,67	0,38	66,11	86
	Average	2,29	1,46	0,83	66,11	88

Table 6 .

 6 Complete results summary for 0.05 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,79	0,30	1,66	33,11	88
	0,10	1,36	0,72	0,89	33,11	88
	0,15	1,99	1,26	0,58	33,11	85
	0,20	2,68	1,84	0,46	33,11	85
	0,25	3,30	2,41	0,37	33,11	83
	0,30	3,77	2,89	0,30	33,11	83
	Average	2,32	1,57	0,71	33,11	85,3

Table 7 .

 7 Complete results summary for 0.03 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,78	0,33	1,38	19,89	87
	0,10	1,36	0,77	0,76	19,89	85
	0,15	1,99	1,31	0,52	19,89	82
	0,20	2,66	1,92	0,39	19,89	84
	0,25	3,32	2,53	0,31	19,89	84
	0,30	3,77	3,00	0,26	19,89	80
	Average	2,31	1,64	0,6	19,89	83,7

Table 8 .

 8 Complete results summary for 0.01 • N M sample size

	c	Classic Sampling Relatively Sample size #Better
	0,05	0,74	0,48	0,52	6,67	73
	0,10	1,33	1,01	0,32	6,67	72
	0,15	1,98	1,61	0,23	6,67	70
	0,20	2,66	2,26	0,18	6,67	71
	0,25	3,31	2,96	0,12	6,67	65
	0,30	3,82	3,52	0,08	6,67	62
	Average	2,31	1,97	0,24	6,67	68,8


Manali Chakraborty

Novarun Deb

Nabendu Chaki

POMSec: Pseudo-Opportunistic, Multipath Secured Routing Protocol for Communications in Smart Grid

Keywords: Opportunistic Routing, Multipath Routing, Wireless sensor network, Security, Energy efficiency, Smart Grid

Traffic engineering governs the operational performance of a network and its optimization. Splitting the network traffic using multipath routing is one of the standard techniques of traffic engineering. Multipath routing maximizes network resource utilization and throughput by giving nodes a choice of next hops for the same destination along with minimizing the delay. On the other hand, Opportunistic routing minimizes operational cost and the burden of redundant route maintenance by using a constrained redundancy in route selection. POMSec: Pseudo Opportunistic, Multipath Secure routing is one such algorithm that combines the advantages of both the routing methods and additionally implements an underlying trust model to secure the communication in Smart Grid.

Introduction

Wireless sensor networks are burdened with the task of transferring data from one node to another via wireless links and multiple hops, considering all the adversaries in the network. Each of the factors like unpredictable environmental behavior, dynamic network topologies, unreliable nature of communication or a combination of these may further contribute to failure of network services. Due to its dynamic nature, WSN is suitable for various types of applications [START_REF] Boa | Trust-based minimum cost opportunistic routing for Ad hoc networks[END_REF]. However, security is one of the most important aspect of every application with different QoS requirements, such as, throughput, energy efficiency, delay, etc. Security of any application is generally determined by its attributes [START_REF] Cheng | QoS Aware Geographic Opportunistic Routing in Wireless Sensor Networks[END_REF]. However, security solutions for sensor networks are different from ordinary networks having infrastructure. Besides, every appliction domain has its own unique characteristics and QoS parameters. Thus, it requires a secure and reliable routing protcol which will comply with application specific QoS parameters as well [START_REF] Lee | A Reliable and Hybrid Multipath Routing Protocol for Multi-Interface Tactical Ad Hoc Networks[END_REF].

In traditional routing the route between a pair of nodes is always static and data packets are tramsmitted through intermediate nodes over that pre determined route. Whereas, multipath routing adds desired level of redundancy to overcome link failures utilizing alternative routes [START_REF] Marina | Ad hoc On-demand Multipath Distance Vector Routing[END_REF]. Besides, in multipath routing environment, link failures do not always result in the initiation of route discovery. This is because the network is k -fault tolerant, for small values of k and hence link failures do not bring network services to a halt [START_REF] Mueller | Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges[END_REF]. Besides, multipath routing provides better load balancing and bandwidth aggregation [START_REF] Ganjali | Load Balancing in Ad Hoc Networks: Single-path Routing vs. Multi-path Routing[END_REF].

There exist several works, [START_REF] Zhang | Cluster-based Multi-path Routing Algorithm for Multi-hop Wireless Network[END_REF] to [START_REF] Varma | Statistical Energy Efficient Multipath Routing Protocol[END_REF] which propose to utilize multiple routes in order to provide stability and reliability in the network. However, in spite of all these benefits, multipath routing has several disadvantages: 1) Using multiple routes can increase significant energy cost, which is one of the most important QoS metric in WSNs; 2) Multiple route discovery and maintenance at every hop induces the operatinal cost of the network; and 3) Besides, multiple routes can introduce channel contentions and interference in the network, which result in the increment of delivery delay as well as cause transmission failures [START_REF] Agrakhed | Energy efficeient interference aware Multipath Routing protocol in WMSN[END_REF].

Opportunistic routing (OR) [START_REF] Hsu | Opportunistic routing -A review and the challenges ahead[END_REF], or anypath routing, is another routing protocol which takes advantage of the broadcasting ability of nodes in wireless medium. It does not use multiple routes, but selects best possible relay nodes among a set of candidate nodes to improve reliability, efficiency and fault tolerance. In OR, first, a source node broadcasts a packet among its neighbors. Then these candidate nodes select a best relay node among itself using some coordination algorithm and forward the data packet through that node. The same process continues until the transmission is successful, i.e., the specified packet reaches its destination.

We have considered Smart Grid as an application domain of our proposed routing protocol. Now, due to specific demands of Smart Grid, the associated communication system should have these following characteristics [START_REF]NIST Framework and Roadmap for Smart Grid Interoperability Standards[END_REF], [START_REF] Gungor | A Survey on Communication Networks for Electric System Automation[END_REF]:

-It should consider different type of traffic patterns in the network, e.g., unicast, multicast and broadcast. effective, open to active standards and public interfaces, backward compatible and most importantly secure to all the vulnerabilities from inside and outside of the network. Now, multipath routing and OR, both have their advantages and disadvantages. Multipath routing provides better reliability and fault tolerance, whereas OR improves network performances and also supports different traffic patterns.

However, multipath routing suffers from operational overhead of discovering and maintaining routes in every hop, which inturn increase the contention in the network. OR also suffers from duplicate reception problem at the destination and single path breakdown problem. Thus, it will be more effective to integrate the positive sides of both these paradigms in a single routing protocol.

The proposed work is a secure and pseudo opportunistic, multipath routing scheme that offers efficient load balancing. Like traditional OR methods, our protocol dynamically selects a set of forwarding nodes for packet transmission. However, the number of routes for packet transmission is not static, and the number of routes varies with the status of each intermediate node, at every hop along the path. The degree of routes at each hop depends heavily on the trust worthiness of neighbouring nodes. As an example, it may act like single-path routing, if the nodes are trustworthy and the communication is reliable and meets network requirements. Otherwise, the number of paths increased. The selection process is run-time and dynamic.

The idea of using selective multipath routing is first proposed in ETSeM [START_REF] Chakraborty | ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol[END_REF]. In ETSeM each node is equipped to choose a set of forwarding nodes among its neighbours to transmit data. Route selection depends on the energy of nodes and number of paths set up through the nodes. However, the proposed routing protocol in [START_REF] Chakraborty | ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol[END_REF] has not been associated with any security measures to detect threats and this inspires us to propose a new secure routing algorithm where an additional trust model [START_REF] Deb | TIDS: Trust-Based Intrusion Detection System for Wireless Ad-hoc Networks[END_REF] is combined with routing mechanism. In the proposed work, every node evaluate the trust value of its next hop neighbour and the routes are selected based on these trust values. The proposed protocol offers the flexibility that it may use multiple paths with high degree of multiplicity when the intermediate destinations are not that trusted. On the contrary, the protocol save resources, and checks congestion by choosing a single path or lesser number of alternate paths for the next hop according to the health value of its neighbour nodes. Because of these characteristics, our proposed algorithm has been referred as Pseudo Opportunistic, Multipath Secure (POMSec) routing protocol. We have simulated our protocol using QualNet 5.2 and also compares the results with [START_REF] Chakraborty | ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol[END_REF] and another trust model proposed in [START_REF] Sen | HIDS: Honesty-Rate Based Collaborative Intrusion Detection System for Mobile Ad-Hoc Networks[END_REF].

The organization of this paper is described as follows: section 2 gives the state of the art review on related works and section 3 describes the proposed process in brief. The simulation results are presented in section 4. Finally section 5 concludes the paper.

State-of-the-Art Review

In this section, we discuss some of the significant works on multi-path as well as opportunistic routing for wireless networks. Besides, section 2.3 discusses some of the existing trust models.

Multi-path routing protocols

Effectiveness of multipath routing protocols primarily rely on two aspects: route discovery and route selection process [START_REF] Deb | Intrusion Detection in WIreless Ad Hoc Networks[END_REF]. The multipath routing algorithm proposed in [START_REF] Ye | An energy-efficient multipath routing protocol for wireless sensor networks[END_REF], has two different protocols: one for searching different multiple and node disjoint paths and another is for allocating the traffic optimally through those disjoint paths. Authors claimed that the algorithm works distributively and optimally balances the load in the network. In [START_REF] Agrakhed | Energy efficeient interference aware Multipath Routing protocol in WMSN[END_REF], each node first built a set of partially disjoint paths to destination among its neighbours.

REER [START_REF] Yahya | REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks[END_REF] considers remaining energy level and available buffer size of a node, and Signal-to-Noise ratio to determine next hop forwarding node in the route. This alogorithm has two methods of traffic allocation. First method selects a group of candidate nodes between every hop, and then the best route is chosen for data transmission. The second method breaks the transmitted message into several equal sized segments and then adds a XOR baed error correction code with them and transmits them through different paths. Thus guarantees the arrival of the packet to the destination without any delay.

RELAX [START_REF] Yahya | RELAX: An Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks[END_REF] effectively utilizes the relaxation technique of batteries to improve network lifetime. It also uses some metrics like remaining energy, Signalto-Noise ratio, and other variables to predict the best next hop node. RELAX splits the transmitted message into several equal sized segments, and then add XOR based FEC with them and transmit them through different paths. Thus, the protocol does not require flooding when there is a link failure and hence the lifetime of the network is increased.

SEEMPr [START_REF] Varma | Statistical Energy Efficient Multipath Routing Protocol[END_REF], tries to balance both the reliability and lifetime of a network, by providing the concept of criticality factor. The criticality factor determines the urgency of delivering a data packet. All packets do not have the same urgency. Thus, high priority packets follow optimal path, while other packets are sent through sub-optimal routes. Thus the energy consumption is distributed over the network.

The review above reflects that there already exist a good number of papers on multipath routing protocols. However, the trust worthiness of participating nodes is often not considered by the above protocols. In [START_REF] Mueller | Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges[END_REF], a secret-sharing algorithm has been used to secure the network. However, the degree of multiple path selection on a hop to hop basis depending on the trust-value of the next hop destination has not really been considered in the existing approaches.

Opportunistic routing protocols

Several works have been proposed in the field of OR. [START_REF] Boa | Trust-based minimum cost opportunistic routing for Ad hoc networks[END_REF] presents a survey of existing OR protocols in wireless network. Although OR is gaining a lot of attention due to its improved performance over other routing protocols in wireless environment, there is not much work present in Smart Grid area. PLC-OR [START_REF] Yoon | Opportunistic Routing for Smart Grid With Power Line Communication Access Networks[END_REF] is a power line communication based opportunistic routing in Smart Grid. Authors in this paper, uses static topological information of nodes to construct a routing table. It always selects a single path to the destination to avoid duplicate packet reception problem at the final destination. They used Dijkstra's algorithm for shortest path selection at each hop. Authors claim to reduce the transmission cost by using a static PLC-AN.

Authors of [START_REF] Qian | A reliable opportunistic routing for smart grid with in-home power line communication networks[END_REF] proposed another OR for Smart Grid. However, this algorithm differs from the previous one in terms of its ability to handle varying topology in a network. They also introduced a new parameter depending on the transmission time for existing routes to calculate the best forwarding node among a set of forward nodes. The estimation method of transmission time is based on the outage probability of the PLC channel. Using simulation and theoritical methods, authors claimed to prove that the throughput of the network can be maximized if remaining transmission time is used to select and identify the forwarding nodes.

Analysing the existing works on opportunistic routing protocol reflects that it performs better in a static network, otherwise the operational cost exceeds the performance gain of the network. Thus, the tradeoff between progressing gain and processing delay and cost will be one of the main important concern for OR. OR does not come with any inherent security model. Thus, providing a secure transmission will be another important aspect while implementing OR in Smart Grid. Furthermore, duplicate packet delivery is another problem for OR. It generally causes due to broadcasting nature of wireless media and the use of isometric antennas. Authors of [START_REF] Yoon | Opportunistic Routing for Smart Grid With Power Line Communication Access Networks[END_REF] claim to solve this problem by not allowing multipath routing, which restricted the selection of forwarding nodes within same transmission domain for a particular sender node. However, this inturn defeats the main purpose of OR, which exploits the broadcasting nature of wireless networks.

Trust models

Authors in [START_REF] Sen | HIDS: Honesty-Rate Based Collaborative Intrusion Detection System for Mobile Ad-Hoc Networks[END_REF] proposed an honesty based intrusion detection system for MANETs. In HIDS, each node is tagged with an unique identifier and an honesty metric. This honesty metric of each node gets updated periodically based on the packet forwarding information provided by one-hop neighbours.

TIDS [START_REF] Deb | TIDS: Trust-Based Intrusion Detection System for Wireless Ad-hoc Networks[END_REF] is a another intrusion detection system for Wireless Ad-Hoc Networks that uses the trust evolution process to mitigate threats. Each node in the network is assigned a predetermined and fixed trust value. As the node spends time within the network, its trust value gets updated. Trust value of nodes get updated based on direct references and indirect recommenmdations. Trust values of one -hop neighbours are evaluated as part of two different processes.

In [START_REF] Xiong | Building Trust in Decentralized Peer-to-Peer Electronic Communities[END_REF], another trust based model is proposed. The trust value of each node is calculated as a function of three different QoS parameters. A peer node will get rewarded every time it behaves properlly with its neighbours. Thus the trustworthiness of each node depends on how it interacts and wheather its neighbours are satisfied with its quality of service.

After reviewing several routing protocols and trust models we can conclude that neither multipath routing nor OR is perfectly tailor made for Smart Grid. In order to maximize the performance of Smart Grid, a combination of both the paradigms is necessary. Besides, there rarely exist some works, where trust models have been used in route discovery. This inspires us to propose an intelligent, selective and secure routing protocol which can use the perks of both opportunistic and multipath routing protocols with additional security mechanisms.

Description of the Process

This section briefly describes our proposed protocol for secure communication in Smart grid. Route selection in POMSec is dependent on energy depletion rate of the nodes, existing paths through the nodes and the trustworthiness of the nodes and their neighbours.

These following set of principles govern the proper execution of the proposed -Every node maintains two arrays -Health and Trust, of all its neighbour nodes.

-Every node has to store two variables -Remaining Energy and Path.

-Packet Receive (PR) and Packet Send (PS ) counters are stored in nodes, along with the addresses of the nodes from which it receive the packets and to which it forward those packets. After a certain time frame (decided by the system operator), these counter values are sent to the node's one-hop neighbours.

-The health of each node N depends on trust-worthiness of the nodes, the remaining energy of it and on the number of paths through N.

The Trust Model

In order to secure our protocol we evaluated the trust of each node. The evaluation process is done by a node for its one hop neighbours and vice versa. The trust model has two main underlying concepts: Direct Valuation and Indirect Reference [START_REF] Deb | TIDS: Trust-Based Intrusion Detection System for Wireless Ad-hoc Networks[END_REF]. Direct Valuation refers to the trust value evaluated by a node. It is calculated using two different parameters: Risk and Reputation.Risk measures a node's behavior in recent past and Reputation assess a node's long term behavior. These two parameters helps to achieve an optimality by balancing the most recent behavior of a node in contrast to its long term behavior. On the other hand, Indirect Reference are considered from those entire one-hop neighbors that are common to both the evaluator node and the target node.

At time t, an evaluator node calculates the Risk and Reputation of its neighbour node i as,

Risk = t |PR i -PS i | (1)
Reputation = t-n t |PR i -PS i | (2)
The Indirect Reference for m number of common neighbour Nodes (ND) between evaluator and target node, can be evaluated as,

Indirect Reference = m N D=1 t-n t |PR i -PS i | (3)
The reward for a node for the last time slice, is calculated using these three metrics as follows [START_REF] Deb | TIDS: Trust-Based Intrusion Detection System for Wireless Ad-hoc Networks[END_REF]:

"Reward = (α * Risk) + (β * Reputation) + (γ * Indirect Reference)" (4)
The above formula generates reward points for each nodes by assigning weights to α, β and γ. Also, these coefficients are normalized so that α + β + γ = 1. Now, we can calculate the trust value as:

"Trust(t) = Trust(t -1) + Reward" (5)
If the value for the variable Trust of a node, crosses the threshold value, then it considered as an attacker. The trust value of a node may vary according to equation (5).

Proposed algorithm

An outline of our proposed algorithm using the above mentioned trust model is given in figure 1. The value of the metric PATH is increased by one, whenever a node receives a ROUTE_REPLY packet . A source node can transmits data using the path that's derived this way. The load to the destination node is distributed proportionally through the routes according to the health of each node.

Figure 2(a) illustrates the route selection proces of the ETSeM algorithm given in [START_REF] Chakraborty | ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol[END_REF]. The significance of the algorithm after incorporating the trust model along the route selection process is depicted in figure 2(b). Figures 2(a) and 2(b) has the same set of nodes. The black node in figure 2(b) is detected as malicious in spite of its health more than or equal to 90%. This is because the trust value of the node is less than the threshold. POMSec can avoid all such malicious nodes in the route selection process with the help of the underlying trust model.

Experiments and Results

Simulation Settings

We have compared and analyzed the performance of POMSec with two different algorithms. First, another trust model, proposed in [START_REF] Sen | HIDS: Honesty-Rate Based Collaborative Intrusion Detection System for Mobile Ad-Hoc Networks[END_REF] is used with the ETSeM algorithm. Let's refer this change in the rest of this paper as H-ETSeM. Thereafter, extensive simulations of POMSec, ETSeM [START_REF] Chakraborty | ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol[END_REF] and H-ETSeM have been successfully performed in QualNet and the results have been plotted as graphs and discussed accordingly. The simulation scenario and settings are described in Table 1 below: 1. For EVERY node Broadcasts a HELLO message.

2. If a node receives a HELLO message, it replies with a REPLY HELLO message containing four variables -PR, PS, REMAINING ENERGY and PATH.

Simulation Results

A quantitative analysis of POMSec and detailed comparison with ETSeM and H-ETSeM are presented in this section. The node density for each experiment varies between 10 nodes to 50 nodes and the mobility is set at 30mps. We have used Constant Bit-Rate (CBR) traffic with 100 second runtime and 100 packets to transmit. A single CBR transmission is implemented for every 10 nodes, i.e., for fourty nodes there will be four different CBR traffics in the experiment. Data has been collected for every variation in node density and then averaged for final results. These results are then plotted on graphs.

Packet Delivery Ratio The first simulation checks the Packet Delivery Ratio (PDR) of POMSec and also compares it with others. PDR is an important parameter in routing and quite standard too. PDR represents the ratio of successfully receiving packets at destination over the packets sent by the sender through CBR traffic. Figure 3(a) shows the PDR for original ETSeM, H-ETSeM and POMSec. POMSec demonstrates more stable and higher PDR than the other two algorithms, inspite of having a trust based evaluation method in route selection.

Throughput Throughput is a measurement of how much data passed through a network in unit amount of time. In this simulation we measured it in Kilobits/sec by observing CBR Server stats. The results in figure 3(b) shows that the throughput for POMSec is better comparing to the other two algorithms. POM-Sec obviously looks promising in terms of efficient path selection and decisionmaking and better throughput values. End to End Delay It represents the total time required by every CBR packet to reach its destination. Figure 4(a) depicts that POMSec offers much smaller delay than both the algorithms, which in turn proves the effectiveness of our trust model. H-ETSeM brings in more instability with increasing node density as compared to ETSeM. This actually confirms that the overhead for trust value updation increases with higher number of nodes. Jitter In networking, the word jitter represents the average of the deviation of a packet against the mean latency of the network [START_REF] Comer | Computer Networks and Internets[END_REF].

Conclusion

We have done a detailed study of the existing works in multipath routing and opportunistic routing in section 2 of the paper. The survey reflects that many of them perform well in terms of throughput of the network and some of them are also energy efficient. However, none of these routing algorithms incorporate trust as a metric to determine the degree of multipath. Thats why we proposed an algorithm where trust evolution process is integrated with the route establishment process to provide security. Besides, a detailed comparison with other trust based approaches has been simulated in Qualnet and the results confirm that POMSec proves to be an improvement over existing algorithms, as it provides security as well as better throughput, PDA, delay and energy efficiency. POMSec has an unique feature that it distributed the traffic among nodes in such a way that the weaker nodes has lesser burden of routing than the nodes with more resources.

3 .

 3 If a node receives a REPLY HELLO message -(a) Extracts the value of the Variables -PR, PS, REMAINING ENERGY and PATH, and calculate the HEALTH, for each of its Neighbour nodes. (b) Every node stores the address of each neighbour node with the value of their corresponding HEALTH, in an array.

Fig. 1 .

 1 Fig. 1. Working principle of POMSec.

Fig. 2 .

 2 Fig. 2. Data communication between Source and Destination using ETSeM and POM-Sec.

Fig. 3 .

 3 Fig. 3. Comparative data analysis for PDR and throughput of ETSeM, H-ETSeM and POMSec.

Fig. 4 .

 4 Fig. 4. Comparative data analysis for End-to-end delay and Jitter of ETSeM, H-ETSeM and POMSec.

Figure 4 (Fig. 5 .

 45 Fig. 5. Comparative data analysis for Energy depletion rate of ETSeM, H-ETSeM and POMSec.

-

  It need to be scalable and flexible to incorporate new renewable sources and distributed energy resources in the netwrok. -Due to the large and evolving architecture of smart Grid, distributed or cluster based networks will be more suitable for it. -The communication system should monitor the network devices and perform fault detection, isolation, and recovery. -Every device should get uniquely identified and addressed. -It should support different QoS parameters for a variety of applications and functions which have different latency and loss requirements, different bandwidth, different security requirements, different real time and non reat time data constraints etc. -Besides, the communication system should be interoperable, dynamic, cost

  4. If a node is a SOURCE node OR receives a ROUTE REQUEST message, Checks its array for the HEALTHIEST node in its Neighbour.

	If the value of the HEALTHIEST node is > 90%
	Send a ROUTE REQUEST message to the HEALTHIEST node.
	Else if the value of the HEALTHIEST node is > 75%
	Send a ROUTE REQUEST message to the HEALTHIEST and second
	HEALTHIEST node.
	Else if the value of the HEALTHIEST node is > 60%
	Send a ROUTE REQUEST message to the HEALTHIEST, second HEALTHIEST
	and third HEALTHIEST node.
	Else if the value of the HEALTHIEST node is > 45%
	Send a ROUTE REQUEST message to the HEALTHIEST, second
	HEALTHIEST, third HEALTHIEST and fourth HEALTHIEST node.
	Else
	Flood the ROUTE REQUEST message.
	5. If a node receives a ROUTE REQUEST message it will RELAY the ROUTE REQUEST
	message as in STEP 4.
	6. If a node is a DESTINATION node OR receives a ROUTE REPLY message, it will
	initiate a ROUTE REPLY message to the nodes, from which it gets the ROUTE
	REQUEST message.

Table 1 .

 1 Parameter Settings for Simulation Environment

	Parameter	Value
	Experimental area	1500 * 1500m 2
	Running time for each simulation 100 sec
	Mac Layer protocol	DCF of IEEE 802.11b standard
	Traffic Model	CBR
	Number of CBR traffics	10% of the total number of nodes
	Mobility	Random Waypoint
	Initial Energy level for each node 5000

Acknowledgments

We would like to thank the Centre of Excellence in System Biology and Biomedical Engineering (TEQIP II), University of Calcutta for infrastructural and financial support towards publishing the results of our research work. This work is a part of the Ph.D. work of Manali Chakraborty, a Senior Research Fellow of Council of Scientific & Industrial Research (CSIR), Government of India. We would like to acknowledge CSIR, for providing the support required for carrying out the research work.


Lukasz Gadomer
email: l.gadomer@pb.edu.pl

Zenon A Sosnowski
email: z.sosnowski@pb.edu.pl

Using Cluster-Context Fuzzy Decision Trees in Fuzzy Random Forest

Keywords: Context-Cluster Fuzzy Decision Tree, C-Fuzzy Decision Tree, Context-Based Fuzzy Clustering, Fuzzy Random Forest

Cluster-Context Fuzzy Decision Tree is the classifier which joins C-Fuzzy Decision Tree with Context-Based Fuzzy Clustering method. The idea of using this kind of tree in the Fuzzy Random Forest is presented in this paper. The created ensemble classifier has similar assumptions to the Fuzzy Random Forest, but differs in the kind of used trees and all aspects connected with this difference. The quality of the created classifier was evaluated by several experiments performed on different datasets. There were tested both datasets with discrete and continuous attributes and decision classes. The aspect of using a randomness in the created classifier was also evaluated.

Introduction

The classification and regression are popular problems in data science. There were created many solutions in order to deal with these issues. In this paper authors present their innovative ensemble classifier which was designed in order to meet both these problems. The idea of this solution is creating a classifier which works with the similar assumptions to Fuzzy Random Forest [START_REF] Bonissone | A fuzzy random forest[END_REF] but instead of Janikow Fuzzy Trees [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] it uses Cluster-Context Fuzzy Decision Trees [START_REF] Sosnowski | Decision rules with fuzzy granulation of knowledge (in Polish)[END_REF]. This kind of tree connects the Context-Based Fuzzy Clustering [START_REF] Pedrycz | Conditional Fuzzy C-Means[END_REF] [START_REF] Pedrycz | Designing decision trees with the use of fuzzy granulation[END_REF] with C-Fuzzy Decision Tree [START_REF] Pedrycz | C-fuzzy decision trees[END_REF]. The objective of this paper was to prove that the created classifier can successfully deal with both regression and classification problems.

The first part of this paper treats about theoretical aspects of the created classifier. The theory about Context-Based Fuzzy Clustering [START_REF] Pedrycz | Conditional Fuzzy C-Means[END_REF] [START_REF] Pedrycz | Designing decision trees with the use of fuzzy granulation[END_REF], C-Fuzzy Decision Trees [START_REF] Pedrycz | C-fuzzy decision trees[END_REF], Context-Cluster Fuzzy Decision Trees [START_REF] Sosnowski | Decision rules with fuzzy granulation of knowledge (in Polish)[END_REF] and C-Fuzzy Random Forest [START_REF] Bonissone | A fuzzy random forest[END_REF] is described there. After that, the idea of using Cluster-Context Fuzzy Decision Trees in Fuzzy Random Forest is presented. Then, the performed experiments with the achieved results are shown. The results achieved by created trees grouped into the forest were compared with the ones obtained with the trees working singly. The influence of using randomness during the tree construction process on the achieved results is also tested. The quality of the created solution is evaluated on the different datasets, containing continuous and discrete attributes, both for classification and regression problems.

Notation

In this paper we used the following notations (based on [START_REF] Bonissone | A fuzzy random forest[END_REF] and [START_REF] Pedrycz | C-fuzzy decision trees[END_REF]):

-K is the number of contexts, k is a particular context -T is the number of tree groups in the ensemble; in each tree group there are K trees connnected with the contextes, t is the particular tree group, t k is a particular tree in t group -N t is the number of nodes in the tree group t k , n is a particular leaf reached in a tree group t k , -I is the number of classes, i is a particular class, -C is the number of clusters, c is a particular cluster,

-E is a training dataset, -e is a data instance, -V k = [V 1k , V 2k , ..., V bk ] is the variability vector for k context, -U k = [U 1k , U 2k , ..., U |E|k ]
is the tree's partition matrix of the training objects for k context, -U ik = [u 1k , u 2k , ..., u Ck ] are memberships of the ith object to the c cluster for k context, -B = {B 1 , B 2 , ..., B b } are the unsplitted nodes, -S is the number of objects from the dataset for which the membership function value is greater than 0 for t k tree in k context, s is the particular object, -X = [X 1 , X 2 , ..., X K ] is the vector of objects from the dataset for which the membership function value is greater than 0 for whole tree t, -X k = [X 1k , X 2k , ..., X Ck ] is the vector of objects from the dataset for which the membership function value is greater than 0 for c cluster, -X ck = [x 1 , x 2 , ..., x S , y k ] is the vector of objects from the dataset for which the membership function value is greater than 0 for c cluster for k context.

Related work

C-Fuzzy Decision Trees

C-Fuzzy Decision Trees are the kind of trees proposed by W. Pedrycz and Z. A.

Sosnowski in [START_REF] Pedrycz | C-fuzzy decision trees[END_REF]. The main motivation to create these trees was the awareness of problems and limits of traditional decision trees, which usually operate on a relatively small set of discrete attributes, choose the single attribute which brings the most information gain to split the node during the tree construction process and are designed to operate on discrete class problems (in their traditional form -the continuous problems are handled by regression trees). The creating of C-Fuzzy Decision Trees was intended to be a solution of these problems. According to their assumptions, C-Fuzzy Decision Trees treat data as collection of information granules, analogous to fuzzy clusters. These granules are generic building blocks of the tree -the data is grouped in such multivariable granules characterized by high homogenity (low variablity). The first step of C-Fuzzy Decision Tree construction process is grouping the data set into c clusters. It is performed in the way that the similar objects are placed in the same cluster. Each cluster is characterized by its centroid, called prototype, which is randomly selected first and then improved iteratively. After the grouping objects into clusters is finished, the given heterogenity criterion is used to compute the diversity of the each of these clusters. This value decides if the node is selected to split or not. From all of the nodes the one with the lowest diversity value is chosen to split. This node is divided into c clusters using fuzzy clustering method [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF]. After that, for each node created that way, the diversity is computed and the selection to split is performed. These steps are repeated until the algorithm achieves the given stop criterion. Each node of the tree has 0 or c children. The growth of the tree can be breadth or deep intensive.

The tree growth stop criterion could be, for example, defined in the following way: [START_REF] Pedrycz | C-fuzzy decision trees[END_REF] -All nodes achieve higher heterogenity than assumed boundary value, -There aren't enough elements in any node to perform the split. The minimal number of elements in the node which allows for the split is c, -The structurability index achieves the lower value than assumed boundary value, -The number of iterations (splits) achieved the boundary value.

After the tree is constructed it can be used in classification mode. Each object which has to be classified starts from the root node. The membership degrees (numbers between 0 and 1 which sums to 1 fot the node's children) of this object to the children of the given node are computed. The object gets to the node where he belongs with the highest membership among the computed ones. The same operation is repeated until the object achieves to the node which has no children. The classification result is the class assigned to this node.

Context-Based Fuzzy Clustering

Clustering is a tool used for data analysis which purpose is to find structures (groups) in multivariable datasets. The idea of context-based clustering [START_REF] Pedrycz | Conditional Fuzzy C-Means[END_REF] is to search such groups of data with applying the context. The context is a kind of information granule, defined in a decision attribute, using which the search for structure in the data is focused. The general task of clustering, formulated as reveal a structure in data X, with context-based clustering is reformulated as reveal a structure in data X in context A, where A is the information granule of interest (context of clustering).

The conditioning aspect (context sensitivity) of the clustering mechanism is used in the algorithm by taking into consideration the conditioning variable (context) assuming the values f 1 , f 2 , ..., f N on the corresponding patterns. In other words, f k is the level of involvement of x k in the considered context, f k = A(x k ). f k can be connected with computed membership values of x k , say u 1k , u 2k , ..., u Ck the way expressed in the following formula:

c ∑ i=1 u ik = f k , k = 1, 2, ..., N (1)
It is important that the selected context directly impacts the resulting data to be considered. The finite support of context A does not take into consideration these data points which the membership values are equal to zero. It means only a certain subset of the original data to be used for further clustering. Considering this fact, the partition matrix U , previously defined as

U = { u ik ∈ [0, 1] c ∑ i=1 u ik = 1 and 0 < N ∑ k=1 u ik < N for all i = 1, 2, ..., c } (2)
can be modified into the family

U (A) = { u ik ∈ [0, 1] c ∑ i=1 u ik = f k ∀ k and 0 < N ∑ k=1 u ik < N ∀ i } (3)
The overall Context-Based Fuzzy Clustering algorithm can be summarized as the following sequence of steps (the number of clusters c is given):

1. Select the termination criterion ε (ε > 0), distance function ||•||, fuzzification
parameter m (by default m = 2.0), then initialize the partition matrix U ∈ U .

Calculate prototypes (centers) of the clusters the same way as in standard

FCM algorithm [START_REF] Bezdek | Pattern Recognition with Fuzzy Objective Function Algorithms[END_REF]:

υ i = ∑ N k=1 u m ik x k ∑ N k=1 u m ik , i = 1, 2, ..., c (4)
3. Update partition matrix

u ik = f k ∑ c j=1 ( ||x k -vi|| ||x k -vj || ) 2 m-1 , i = 1, 2, ..., c, j = 1, 2, ..., N (5) 4. Compare U ′ to U . If ||U ′ -U || < ε,
||a -b|| = n ∑ i=1 (a i -b i ) 2 σ 2 i ( 6
)
where σ i are standard deviations of the corresponding attributes.

Cluster-Context Fuzzy Decision Trees

The main idea of Cluster-Context Fuzzy Decision Trees is joining Context-Based Clustering, presented in Section 3.2 and C-Fuzzy Decision Trees, described in Section 3.1. This kind of trees were presented in [START_REF] Sosnowski | Decision rules with fuzzy granulation of knowledge (in Polish)[END_REF]. Author predicted that joining these two algorithms allows to achieve better results than C-Fuzzy Decision Trees, especially for regression problem.

It is important to notice that notation presented in Section 2 each Cluster-Context Fuzzy Decision Tree t consists of k C-Fuzzy Decision Trees t k . It means that the structure called "tree" t when writing about Cluster-Context Fuzzy Decision Trees refers to the group of C-Fuzzy Deicision Trees t k , not a single tree. As it can be confusing, it is worth to remember about it.

The first thing which should be done before starting construction of Cluster-Context Fuzzy Decision Tree is dividing decision attribute into contexts. The number of contexts is the algorithm parameter which should be adjusted according to the dataset. In the theoretically perfect situation the number of contexts should respond the number of object groups in the dataset. The division can be performed using any membership function. In this research three membership functions were chosen: gaussian, trapezoidal and triangular. The example division result using these functions into five contexts is presented in Figure 1. In order to fit the division to the given problem in the best possible way it is also possible to configure the shape of membership function. In the created solution authors allowed to do this using "context configuration" parameterits default value is 1, lower numbers makes contexts wider, higher numbersshorter. Figure 1 showed divisions for default context configuration value, on Figure 2 the example divisions using values 0.6 and 1.6 are presented. When contexts are prepared, it is possible to create and learn Cluster-Context Fuzzy Decision Trees according to the Algorithm 1. end for 6:

Algorithm 1 Cluster-Context Fuzzy Decision Tree learning

Assign to class with the higher U ik value from k achieved values (classification) or compute the distance between the y k and the decision value in the chosen node n (regression) 7: end procedure

Fuzzy random forests

The Fuzzy Random Forest classifier was first presented in [START_REF] Bonissone | A fuzzy random forest: Fundamental for design and construction[END_REF] and then widely described in [START_REF] Bonissone | Combination methods in a Fuzzy Random Forest[END_REF] and [START_REF] Bonissone | A fuzzy random forest[END_REF]. The mentioned classifier was based on two papers cited before: [START_REF] Janikow | Fuzzy decision trees: issues and methods[END_REF] and [START_REF] Breiman | Random Forests[END_REF]. Fuzzy random forest, according to its assumptions, combines the robustness of ensemble classifiers, the power of the randomness to decrease the correlation betweeen the trees and increase the diversity of them and the flexibility of fuzzy logic for dealing with imperfect data [START_REF] Bonissone | A fuzzy random forest[END_REF].

Fuzzy random forest construction process is similar to Forest-RI, described in [START_REF] Breiman | Random Forests[END_REF]. After the forest is constructed, the algorithm begins its working from the root of each tree. First, a random set of attributes is chosen (it has the same size for each node). For each of these attributes information gain is computed, using all of the objects from training set. Attribute with the highest information gain is chosen to node split. When the node is splitted, selected attribute is removed from the set of attributes possible to select in order to divide the following nodes. Then, for all of the following tree nodes, this operation is repeated using a new set of randomly selected attributes (attributes which were used before are excluded from the selection) and the same training set.

According to described algorithm trees are constructed. Each tree is created using randomly selected set of attributes, different for each tree, which ensures diversity of trees in the forest.

Using Cluster-Context Fuzzy Decision Trees in Fuzzy Random Forest

The classifier which uses Cluster-Context Fuzzy Decision Trees in Fuzzy Random Forest is proposed in this section. This ensemble classifier bases on the idea of Fuzzy Random Forest and uses Cluster-Context Fuzzy Decision Trees as constituent classifiers. The idea of Fuzzy Random Forest with C-Fuzzy Decision Trees was presented in [START_REF] Gadomer | Fuzzy Random Forest with C-Fuzzy Decision Trees[END_REF]. It is expected that introducing the contexts with their advantages into the forest will increase the classification accuracy, especially in the area of continuous decision class problems.

The randomness in the created classifier is ensured by two main aspects. The first of them refers to the assumptions of Random Forest. When the tree is being constructed, the node to split is selected randomly. It can be full randomness (selecting the random node to split instead of the most heterogenous) or limited (selecting the set of nodes with the highest diversity, then randomly selecting one of them to perform the split). The second aspect refers to the C-Fuzzy Decision Trees, which take part in Cluster-Context Fuzzy Decision Trees, and it concerns partition matrix creation proces. The first coordinates of centroids (prototypes) of each clusters are selected randomly. Objects which belong to the parent node are divided into clusters grouped around these prototypes using the shortest distance criterion. After that the prototypes and the partition matrix are being corrected iteratively until they achieve the stop criterion. What is more, each tree in the forest can be selected from the set of created trees. Each tree from such set is tested and the best of them is being chosen as the part of forest. The size of this set is given and the same for the each tree in the forest.

The split selection idea is similar to the one used in Fuzzy Random Forest, but it refers to nodes instead of attributes. In Fuzzy Random Forest, the random attribute was being chosen to split during the Fuzzy Trees construction process. In Fuzzy Random Forest with Cluster-Context Decision Trees the choice concerns the node to split selection. Some nodes does not have to be splitted (it can happen when the stop criterion is achieved). Each Cluster-Context Fuzzy Decision Tree in the forest can be similar or different -it depends on the chosen algorithm parameters. It allows to adjust the classifier to the given problem in a flexible way.

The Fuzzy Random Forest with Cluster-Context Fuzzy Decision Trees is created using Algorithm 4.

Algorithm 4 Fuzzy Random Forest with Cluster-Context Fuzzy Decision Trees learning

1: procedure FRFwCC-FDTlearning 2:

for 1 to T do 3:

1. Take a random sample of |E| examples with replacement from the dataset E 4:

2. Apply Algorithm 1 to the subset of examples obtained in the previous step to construct C-Fuzzy Decision Tree 5:

end for 6: end procedure

The constructed forest can be used for classification and regression problems. For the classification issue, the decision-making strategy assumpts making the final decision by forest after individual decisions of trees are made. This process is performed according to the Algorithm 5.

The weighted averaging is performed to let the best trees in the forest (the ones which during the learning process achieved the lowest prediction error)

Algorithm 5 Fuzzy Random Forest with Cluster-Context Fuzzy Decision Trees classification

1: procedure FRFwCC-FDTclassification 2:

Perform tree's individual decisions according to Algorithm 3 3:

Assign to class according to the simple majority vote of trees decisions (classification) or perform weighted averaging the final prediction (regression) 4: end procedure have the biggest influence on the final prediction. It is performed according to the following formula:

result = T ∑ i=1 result i × result T -i n(n + 1) 2 , ∀i result i < result i+1 (7)

Experimental studies

The main objectives of performed experiments were to test the quality of created classifier on classification and regression process and to check the influence of the randomness on the results. To check the classification process, experiments were performed on four popular datasets from UCI Machine Learning Repository [START_REF] Lichman | UCI machine learning repository[END_REF]: Ionosphere, Dermatology, Pima-Diabetes and Hepatitis. To check the regression process another two datasets from this repository were used: Automobile Data and Housing. Each dataset was randomly divided into five equal parts (or as close to the equal as it's possible). For classification problems, each of these parts had the same proportions of objects with each decision class (or as close to the same as it's possible). This random and proportional division was saved and used for each experiment.

Each experiment was performed with 5-fold crossvalidation. Four of five parts were used to train the forest, one to test it. This operation was repeated five times, each time the other part was excluded from the training process and used for evaluation. At the end all classification accuracies of the out of bag parts were averaged.

Classification parameters were chosen individually for each dataset with parameter optimization process. There were tested multiple combinations of parameters for forests which consist of five trees. According to these results the classification parameter combinations for the final classifier were chosen. Each forest in the experiment consist of fifty trees.

Ahieved results were compared with Fuzzy Random Forest with C-Fuzzy Decision Trees and Fuzzy Random Forest C-Fuzzy Decision Trees. Some of the results which serve as a base to compare were prsented in our previous work: [START_REF] Gadomer | Fuzzy Random Forest with C-Fuzzy Decision Trees[END_REF].

All of the results are presented in Section 6.

Results and discussion

The classifiers' parameters chosen for each dataset are presented in Table 1. As it was expected, ensemble classifiers which use Cluster-Context Fuzzy Decision Trees allowed to achieve better results that forests with C-Fuzzy Decision Trees. The differences were more significant for Auto Data dataset. For housing dataset all results achieved using ensembles with Cluster-Context Fuzzy Decision Trees were also better that using forests with C-Fuzzy Decision Trees, but the differences were smaller.

Dataset

For each of created ensemble classifiers: Fuzzy Forest with C-Fuzzy Decision Trees, Fuzzy Random Forest with C-Fuzzy Decision Trees, Fuzzy Forest with Cluster-Context Fuzzy Decision Trees and Fuzzy Random Forest with Cluster-Context Fuzzy Decision Trees results achieved using weights were better that without using them. It clearly means that it is worth to use weighted average instead of arithmetic average. The arithmetic average of the results achieved by trees which are part of the forest does not allow to use the full strength of the ensemble. The weighted average allows forest to work the way it was desinged for.

For the ensemble which use C-Fuzzy Decision Trees in most cases using randomness increased the quality of the classifier. The difference was more significant for Auto Data dataset. For Housing dataset the differences between using randomness and not were slight. It means that using randomness can improve the classification accuracy, but it depends on the dataset and the classifier's configuration.

Datasets with discrete decision class

The results achieved for datasets with discrete decision class are presented in Table 3. In most cases using forest with Cluster-Context Fuzzy Decision Trees allowed to achieve better results that with ensemble using C-Fuzzy Decision Trees. Using randomness in Fuzzy Random Forest with Cluster-Context Fuzzy Decision Trees in most cases also allowed to improve classification accuracy (for Dermatology dataset it was the same, for the other ones it was better). All of these improvements were small but noticeable.

Dataset

It is worth to notice the reason classification of the accuracy imrpovement in the given classifier configuration. On the sample visualization of contexts presented in Figure 2 it is showed that for the context configuration parameter equal to 0.6 all of the contexts are relative wide. For the decision attribute division into two or three contexts all of these contexts, for all of the decision attribute's values, has a value greater than zero. It means for each context no objects from the dataset are excluded from the C-Fuzzy Decision Trees which are part of Cluster-Context Decision Tree. In this case the ensemble classifier with Cluster-Context Fuzzy Decision Tree works the similar way to the forest with C-Fuzzy Decision Trees, but each tree is chosen from the best of K. In this special case choosing the best trees allowed to slightly improve classification accuracies. It is also worth to notice that during the parameters optimization the other (typical) cases produced a little worse results that the given one.

Conclusion

The Fuzzy Random Forest with Cluster-Context Decision Trees classifier was presented in this paper. The created solution was tested using datasets both with continuous and discrete decision attribute. The classification accuracy was compared with the results achieved with the Fuzzy Random Forest with C-Fuzzy Decision Trees. The experiments showed that in most cases Fuzzy Random Forest with Cluster-Context Decision Trees gives better results that Fuzzy Random Forest with C-Fuzzy Decision Trees, especially for datasets with continuous decision attribute. It was also showed that using weights are really important for datasets with continuous decision attribute. All these results showed that the Fuzzy Random Forest with Cluster-Context Decision Trees is the valuable ensemble classifier which can allow to achieve good results in many classification or regression problems.

Fig. 1 .

 1 Fig. 1. Example division of decision attribute into five contexts using (from left) triangular, gaussian and trapezoidal membership functions.

Fig. 2 .

 2 Fig. 2. Example division of decision attribute into four contexts using gaussian function with context configuration value (from left) 0.6 and 1.6.

  then stop, else return to step (2) and proceed with computing by setting up U equal to U ′ Used distance function is the weighted Euclidean distance function, defined as follows:

  Each C-Fuzzy Decision Tree in Cluster-Context Fuzzy Decision Tree is created using Algorithm 2.Created Cluster-Context Fuzzy Decision Tree can be used in classification and regression process. It is performed according to the Algorithm 3.

	Algorithm 3 Cluster-Context Fuzzy Decision Trees classification
	1: procedure CC-FDTclassification
	2:	for 1 to K do
	3:	1. Run the example x k to obtain the tree's partition matrix U ik
	4:	2. Choose the class c where c = arg max i,i=1,2,...,I	U ik (classification) or choose
		the node n where n = max U ik (regression)
	5:
	1: procedure CC-FDTlearning
	2:	for 1 to K do
	3:	1. Start with the examples in X k
	4:	2. Create C-Fuzzy Decision Tree for context k using Algorithm 2
	5:	end for
	6: end procedure
	Algorithm 2 C-Fuzzy Decision Tree learning
	1: procedure C-FDTlearning
	2:	1. Start with the examples in X k for k context,
	3:	2. Create the partition matrix U k randomly
	4:	3. Perform FCM
	5:	while Stop criterion is not satisfied do
	6:	4. Divide the samples belonging to the splitted node into its children
	7:	5. Make a random selection of nodes from the set of unsplitted nodes B
	8:	6. Compute the variability matrix V k
	9:	7. Choose the node with maximum variability to split nodes
	10:	8. Perform FCM
	11:	end while
	12: end procedure

Table 1 .

 1 Classifier parameters for datasets 6.

		Hepatitis Dermatology Pima Indians Diabetes Ionosphere Auto Data Housing
	Number of clusters	2	2	2	2	2	3
	Number of contexts	3	2	3	2	9	2
	Membership function Gaussian	Triangular	Gaussian	Gaussian	Gaussian Gaussian
	Context configuration	0.6	1.6	0.6	0.6	0.6	0.6

1 Datasets with continuous decision attribute

  The results achieved for datasets with continuous decision attribute are presented in Table2. Numbers in the table are the average distances between the predicted value and the original value.

	Dataset	Auto Data Housing
	Fuzzy Forest with C-Fuzzy Decision Trees without weights	3277.55	3.98
	Fuzzy Forest with C-Fuzzy Decision Trees with weights	3244	3.92
	Fuzzy Random Forest with C-Fuzzy Decision Trees without weights	3192.9	3.97
	Fuzzy Random Forest with C-Fuzzy Decision Trees with weights	3178.26	3.94
	Fuzzy Forest with Cluster-Context Fuzzy Decision Trees without weights	3064.58	3.91
	Fuzzy Forest with Cluster-Context Fuzzy Decision Trees with weights	3025.41	3.86
	Fuzzy

Random Forest with Cluster-Context Fuzzy Decision Trees without weights

	3023.92	3.87
	Fuzzy

Random Forest with Cluster-Context Fuzzy Decision Trees with weights

	3015.59	3.85

Table 2 .

 2 Results for datasets with sontinuous class attribute

Table 3 .

 3 Classification errors for datasets with discrete class attribute

	Hepatitis Dermatology Pima Indians Diabetes Ionosphere

Acknowledgment

This work was supported by the grant S/WI/1/2013 from Bialystok University of Technology founded by Ministry of Science and Higher Education.