Michal Dolecki
email: michal.dolecki@kul.pl

Ryszard Kozera
email: ryszard.kozera@gmail.com

Michał Dolecki

Threshold Method of Detecting Long-Time TPM Synchronization

Keywords: neural networks, Tree Parity Machine, key exchange protocol

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

One of the most important aspects of information security is ensuring the confidentiality of communications. Two parties wish to exchange certain information in such a way, that unauthorized persons have no opportunity to guess the content of the communication. Confidentiality is implemented mainly through data encryption with usage of various cryptographic algorithms [START_REF] Menezes | Handbook of Applied Cryptography[END_REF], [START_REF] Stokłosa | Data Security in Informatical Systems[END_REF]. The cryptographic keys are additional input data used in the algorithms to encrypt and decrypt transmitted messages. Due to the keys used, the cryptography can be classified into two types, i.e. symmetric and asymmetric cryptography [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. Asymmetric cryptography requires from both parties to maintain two keys, one public and the second a private one. Public key is used to encrypt messages, and private one, to decrypt them. Symmetric cryptography uses the same key to both of these operations. In this scheme the security of key distribution and its storage becomes a vital issue. This leads to a paradox: on one hand if one strives to build a secure communication channel, one must have a secure key distribution channel first. On the other hand, if one has secure channel, then why not use it to the communication. To cope with this problem, the key exchange protocol exploiting an open channel can be used.

One of the most popular algorithms used for such key agreement is the Diffie-Hellman algorithm [START_REF] Menezes | Handbook of Applied Cryptography[END_REF], [START_REF] Stokłosa | Data Security in Informatical Systems[END_REF], which is based on computationally difficult problem of calculating discrete logarithms in cyclic groups. Such kind of problems cannot be solved in a reasonable amount of time [START_REF] Stinson | Cryptography, Theory and Practice[END_REF]. More specifically there is no proposed algorithm to solve these problems which operates in polynomial time but there may be an algorithm with greater computational complexity. Results presented by three physicists: E. Kanter, W. Kinzel and I. Kanter [START_REF] Kanter | Secure Exchange of Information by Synchronization of Neural Networks[END_REF] permit constructing the relatively secure [START_REF] Klein | Synchronization of Neural Networks by Mutual Learning and its Application to Cryptography[END_REF][START_REF] Klimov | Analysis of Neural Cryptography[END_REF][START_REF] Ruttor | Neural Synchronization and Cryptography[END_REF][START_REF] Ruttor | Genetic Attack on Neural Cryptography[END_REF] key exchange protocol using the phenomenon of artificial neural networks' synchronization by mutual learning.

The idea of applying neural networks in cryptology have emerged relatively recently [START_REF] Dourlens | Neuro-Cryptography[END_REF], [START_REF] Kotlarz | On Application of Neural Networks for S-Boxes Design[END_REF]. This approach represents an interesting alternative to the currently used algorithms based on number theory [START_REF] Kanter | Neural Cryptography[END_REF]. In the classical setting, artificial neural networks are built of interconnected layers of neurons. The input network's layer receives input signals and sends them in turn to the first hidden layer's neurons. The output values of neurons of one layer form the inputs for the next neurons' layer etc. Finally, the output of the last layer is the output of the entire network. Each impulse sent to the single neuron is modified by a certain weight. For each neuron, if the sum of weighted impulses exceeds a given threshold level, then the neuron transmits a signal (due to the specifically tuned up activation function). Network classifiers [START_REF] Hassoun | Fundamentals of Artificial Neural Networks[END_REF][START_REF] Osowski | Neural Networks in Algorithmic Approach[END_REF][START_REF] Rutkowski | Methods and Technics of Artificial Intelligence[END_REF] receive impulses which belong to one of several selected classes. The main characteristic feature of neural networks is their ability to learn from the presented examples. Such learning process consists of modifying the weights of the neurons to establish the most accurate classification of input impulses. The network is considered as a trained one, if the amount of misclassified input vectors is lower than the prescribed a priori specific acceptance level. For weights, that are real numbers, there are infinitely many different values ensuring a proper output of the given network. The specific and proper use of the network, in practice requires the additional conditions imposed on their structure (i.e. its topology) and neuron activation functions [START_REF] Kanter | Secure Exchange of Information by Synchronization of Neural Networks[END_REF][START_REF] Klein | Synchronization of Neural Networks by Mutual Learning and its Application to Cryptography[END_REF][START_REF] Klimov | Analysis of Neural Cryptography[END_REF][START_REF] Ruttor | Neural Synchronization and Cryptography[END_REF], [START_REF] Kanter | Neural Cryptography[END_REF], [START_REF] Kanter | The Theory of Neural Networks and Cryptography[END_REF].

In this paper we present the idea of key exchange protocol using neural networks, where the corresponding weights upon pertinent iterative procedure are set to be equal. We discuss first two methods measuring an overlap of both weight vectors by calculating first the cosine of the angle between them and then alternatively by using the Euclidian metric. Evidently, two approaches mentioned above rely on the knowledge of both networks weights' values which need to be sent via open channel. This, however is impossible in practical key exchange protocol as it would result in security breach. In order to make the weights publicly unknown we analyze the corresponding frequencies of publicly known common outputs of both networks (called here TPMs). Results presented in this paper indicate strong correlation between calculated frequencies and other methods for evaluating TPM's synchronization state. The latter lays foundation to formulate condition for classification of synchronization duration for a given time classes, especially to detect at early stage a long-term synchronization.

Threshold Method of Detecting Long-Time TPM Synchronization

Tree Parity Machine Synchronization

The mentioned above, proposed by three physicists Kanter, Kinzel and Kanter cryptographic key exchange protocol in an open communication channel resorts to the so-called Tree Parity Machine network (abbreviated here to TPM). The key exchange procedure abides to the following pattern: two sides of the communication i.e. A and B entities create a special TPM network with the same structure. Both networks start with randomly chosen initial weight vectors and , this initial state is kept secret. Both partners A and B apply a common and publicly available input vector and calculate next the results of their networks. In the next step they exchange their network's results on an open channel. Each party treats the result of the network of another side as the expected result for himself and teaches its own network accordingly (by selecting one of the agreed before learning scheme). The next step is to choose randomly new input vector and the above procedure is subsequently repeated. Upon performing some number of such cycles, both networks' weights coincide and they can be used as cryptographic keys for the established communication. This bidirectional interaction of two synchronizing networks leads to reaching much faster equal weights vectors, than unidirectional one, which potential attacker could also do.

TPM defines a multilayer, feed-forward network with characteristic tree-like structure created by non-overlapping receptive fields. Figure 1 shows the structure of the typical TPM network.

{ ∑ ∑ (1)
Commonly in the literature, the TPM network is shortly described with the aid of three parameters: K-N-L. The last layer neuron multiplies hidden layer neurons' out-puts and the result of its action is deemed as outcome of the entire network. This operation is given by following formula:

∏ (2)
TPM network has KN weights being integers within the range from -L to L. Thus, at each synchronization step, it may take one of ( ) states. For example, the weights of the network with parameters 3-101-3, takes one of states. The cryptographic key generated using weights would be bits long.

The network is considered as trained only if its result is equal to the expected one, like in classical Hebbian method [START_REF] Ruttor | Neural Synchronization and Cryptography[END_REF], [START_REF] Hassoun | Fundamentals of Artificial Neural Networks[END_REF]. In mutual learning, the expected values are generated by the other network. Hence our two networks are trained only if they both have equals outputs. Each network involved is trained in accordance with one of three methods:

1. Anti-Hebbian learning rule:

( ) ( ) . (3)
2. Hebbian learning rule:

( ) ( ) . (4)
3. Random-Walk learning rule:

( ) ( ) . ( 5
)
If the new value of the weight is greater than L, it is replaced by L, and analogously, if the value is less than -L, it is replaced with -L, respectively. In the first learning rule weights are modified once the results of both networks are different, and the process leads to the network synchronization with opposite vectors w. The remaining two methods lead to synchronization with the same weight values.

Each pair of neurons form synchronizing TPMs in each learning step perform one of three admissible weight change named in [START_REF] Rosen-Zvi | Mutual Learning in a Tree Parity Machine and its Application to Cryptography[END_REF] quiet, attractive or repulsive step. Let i denote the index of neuron in both networks A and B.

1.

or then A and B do not change the weights' values at all or don't change the weights of i-th neuron. In both these cases it is the so-called "quiet step". 2.

then the weight vectors and are modified according to one of the listed above learning rules. The modification applied depends on the common input vector and equal neurons output, so that the change is coordinated, because all these values are the same for both networks. Weight vectors change in the same direction, and this case is called "attractive step". 3.

[( ) ( )] this means, that the outputs of A and B are the same and one of the following events takes place: Threshold Method of Detecting Long-Time TPM Synchronization (a) the analyzed neuron of network A has the same output as the result of a whole network and the corresponding neuron in network B generates an output different than whole network B, (b) the i-th neuron of network A has different output, than the whole network A, and in network B the corresponding neuron has output equal to whole network B output. In both events, only one neuron, which output is equal to the whole network output, modifies its weights, while the weights of the second network's neuron remain unchanged. In general, this procedure results in a reduction of weight vectors compatibility, and this step has been called "repulsive step".

Synchronized TPM networks end up with the same weight vectors and remain synchronized regardless of the time of further learning. For each input vector both networks return the same result, so in each next learning step both network pass through the learning procedure and almost every time networks modify their weights. If K is odd, one changes here the weight of at least one neuron in both networks. For K even there is only one case in which the weights of entire network are not modified. Indeed the latter occurs when all of the hidden layer neurons return -1 and the entire network return 1. For such specific case no neuron will change its weight. In opposite, any other combinations of hidden layer outputs yield at least one neuron changing its weights. Summing-up, synchronized networks typically change the weight during next learning steps which every time yields the same changes in two networks and thus both networks remain synchronized.

The condition enforcing the termination of network's synchronization is to obtain exchange of consistent results of both networks in a sufficiently long period of time. As examined experimentally (see section Results of this paper), in 15000 analyzed synchronizations of the network with the structure 3-101-3 the longest exchange of consistent results by not synchronized network is 147 steps. Thus to be sure that both networks are already synchronized, they should exchange over 147 consistent outputs.

Synchronization is a stochastic process, and the time required to achieve the consistent weights values depends on the initial weights and the input signals generated at each step. The synchronization times of network with a given structure, creates histograms as shown in figure 2 [START_REF] Kanter | Neural Cryptography[END_REF]. Such histogram is created after 15000 synchronizations of the network 3-101-3, where the Random Walk learning rule is applied. The number of classes in the histogram is given by the Hunstberger formula (see [START_REF] Huntsberger | Elements of Statistical Inference[END_REF]), where here and is doubled subsequently for better readability of the chart. Along X-axis the number of learning cycles needed to achieve networks full synchronization is given. On the other hand along Y-axis the probability of finding TPM synchronized in a given number of cycles is specified.

Results

In this paper we analyze the synchronizations of the examined networks with the structure 3-101-3. Such networks enable to agree on key length of 909 bits. The first parameter K specifying the number of neurons in a hidden layer is set to 3, which is a typical value used commonly in TPM networks. The parameter L=3 sets the minimum and maximum weight value -L and L, respectively. Each weight must therefore be the integer from interval [ ], yielding 7 possible values, which is close to the power of 2. This choice of parameter allows to easily generate a fairly uniform distribution of bits with values 0 1 in a generated key. The number of bits needed to store the value of the weights is given by ( ) but in fact one has to use ⌈ ( )⌉ bits (here symbol ⌈ ⌉ denote the standard ceiling function). Therefore, it is important to minimize the difference between these values and select L which minimizes the following cost function

( ) ⌈ ( )⌉ ( ). (6)
Figure 3 shows the function b depending on the selection of the parameter L and taking the values of redundancy in bit representation of weight. It is transparent from the picture that the corresponding value of L is given by for some integer n. Our discussed network is synchronized 15000 times. The fastest synchronization is completed after 133 cycles, while the longest lasted for 1156 cycles. The average synchronization time is in turn 346 cycles. Due to the shape of the histogram (see figure 2) it is interesting to observe that the third quartile value reads as 398, which is slightly above 34% of longest synchronization time. The latter means that 75% of the networks synchronize relatively fast, but there is a group of cases with longer synchronization pattern [START_REF] Dolecki | Tree Parity Machine Synchronization Time -Statistical Analysis[END_REF].

Previous research on the synchronization dynamic [START_REF] Ruttor | Neural Synchronization and Cryptography[END_REF], [START_REF] Rosen-Zvi | Mutual Learning in a Tree Parity Machine and its Application to Cryptography[END_REF] is based on weights' vectors mutual overlap for each hidden layer neurons. This measurement tool is determined by the cosine of the angle between the vectors of weights (corresponding to the respective neurons in both networks A and B) according to the following formula:

√ √ (7)
At the initial synchronization phase the cosine renders a value close to 0, while in the end, when TPMs have the same weights, its value is equal to 1. In [START_REF] Dolecki | The Evaluation of the TPM Synchronization on the Basis of their Outputs[END_REF] different approach is presented. Namely, one analyzes the weights' vectors of all neurons and uses the Euclidean distance of these vectors

( ) ‖ ‖ √∑ ( ) . ( 8
)
This distance is connected with previously used mutual overlap by cosine theorem for unitary spaces. This parameter changes during the synchronization from relatively high values for non-synchronized network to 0 for synchronized one. Therefore, it has to be normalized and reversed to preserve the same characteristic as cosine. The normalization operation is accomplished by applying the formula:

( ) ( ) ( ) ( ) ( ) . (9)
In figure 4 we present the performance of the Modified Euclidean distance and the cosine measurement for the network 3-101-3 that synchronize within the time equal to the average synchronization time from the all analyzed network's time. The horizontal axis represents TPM's learning time and the vertical one, represents weights compatibility expressed as modified Euclidean distance and cosine. Reversed normalized distance and cosine have significant linear correlation. Further analysis of this case (see table 3 and 4 below) with the mean square error between the cosine and normalized distance shows that both of these parameters are well-suited to describe the dynamics of synchronization process. In the example mentioned above the mean square error is around 0.016.

The presented above method for modifying distance measurements yield results that stay in good linear correlation with frequency of common output of synchronizing TPMs. Let the ( ) be a sequence, and if and if , . The sequence ( ) is defined as an average of s elements from ( ) with indices --. This sequence is given by formula:

∑ , (10)
where ( ). During the synchronization process, the weight's vectors of both networks are generally closer, resulting in achieving equal values. The dynamics of these changes can be described by the cosine of the angle between the weights' vectors or by using normalized and reverse Euclidean distance. In both cases, one must know the weights' vectors of the two networks, which is impossible for practical cryptographic key exchange protocol. Linear dependence of the network synchronization level and frequency of the same results exchanged by both networks, permits to treat such frequencies as a tool to determinate how quickly the network will complete the synchronization process. Analyzing these frequencies indicates the threshold at which networks have compatibility level good enough to finish synchronization process in a very short time.

Given 15000 synchronizations of networks with parameters 3-101-3, 5 networks are selected that synchronized after 200 and after 900 cycles, respectively. Visibly, the first group includes the networks that synchronized relatively quickly, while the second one contains networks with the longest observed synchronization time. For each of tested networks we analyzed frequencies of compatible output of the network in 25, 50, 75, ..., 125 previous steps. Next we verified if any of these frequencies ex-Threshold Method of Detecting Long-Time TPM Synchronization ceeds the threshold value 0.7, 0.6, 0.65, ..., 0.85. The tables 1 and 2 illustrate the correlation coefficient between the reversed normalized Euclidean distance and the cosine (see the first column). In addition, they present the correlation coefficient between this distance and frequency calculated for given number of previous steps (the next columns). The green's intensity of the background indicates the best results. In addition for acquiring high linear relationship between distance and frequency it is also important to determine the compatibility of the above results. In order to achieve the latter we calculated the mean square error for the analyzed network. The corresponding results are demonstrated below in tables 3 and 4. The outcomes from these tables refer to both networks synchronized either in 200 or above 900 cycles, respectively. The obtained output structure is analogous to the previous tables. Again the green's intensity of the background indicates the best results. As previously the best results are obtained for frequencies of 50-100. As indicated in figures 5 and 6 in a long synchronization mode, there exists a threshold value close to 0.8 which, when exceeded in a some number of subsequent cycles, results in fast synchronization. In the case of networks that synchronizes quickly, calculated frequencies exceed this threshold also shortly before full synchronization. The experimental analysis of different threshold values ranging within 0.6 to 0.85 for all analyzed frequencies is also conducted. The fact of passing over a given threshold can be presented in the following schemes for frequencies calculated in 75 previous steps (figures 7 and 8): It is visible that frequencies generally increase during the network learning. This is consistent with an increase of compatibility of weights' vectors of the synchronizing networks. Thus the bigger threshold values are crossed by calculated frequencies after longer networks learning.

In the long synchronization only threshold 0.6 is exceeded before average learning time, which is 346 cycles for this TPM. Thus the use of the threshold set to 0.65 in this case indicates that there will be a high-speed synchronization. If this threshold is not exceeded in average or in third quartile time, it will be better to start synchronization with new, random weights.

Conclusions

The method of frequency analysis for exchange of equal results in TPM networks can be used to assess the synchronization level of both networks. As experimentally shown in this paper the calculated frequencies are not only strongly correlated with the distance between the weights' vectors but also are close to the values of modified distance. The latter is obtained by the small mean square error analysis. The charts containing the results of experiments presented herein shows that selecting the proper range for counting frequency and threshold (to be permanently exceeded) permits to specify whether one deals with either a short or a long synchronization.

Fig. 1 .

 1 Fig. 1. TPM structure

Fig. 2 .

 2 Fig. 2. Times of TPM 3-101-3 synchronization

Fig. 3 .

 3 Fig. 3. Function b

Fig. 4 .

 4 Fig. 4. Modified Euclidean distance and cosine for TPM 3-101-3

Fig. 5 .Fig. 6 .

 56 Fig. 5. Dynamics of short synchronization

Fig. 7 .Fig. 8 .

 78 Fig. 7. Crossing the threshold for TPM with synchronization time 200

Table 1

 1 lists generated herein results for networks synchronized fast in 200 cycles, whereas table 2 presents the same results for networks with synchronization time above 900 cycles. It is transparent once inspecting both tables, that the best fit is obtained for frequencies calculated on the basis of the latest 50-100 steps.

Table 1 .

 1 Correlation coefficient for TPM synchronized in 200 cycles

dist, cos dist, fr 25 dist, fr 50 dist, fr 75 dist, fr 100 dist, fr 125 TPM

	1	0,9675	0,9208	0,9547	0,9726	0,9736	0,9637
	TPM 2	0,9463	0,9773	0,9851	0,9809	0,9758	0,9688
	TPM 3	0,9452	0,9588	0,9820	0,9790	0,9673	0,9508
	TPM 4	0,9543	0,9515	0,9579	0,9652	0,9702	0,9683
	TPM 5	0,9583	0,9740	0,9818	0,9722	0,9510	0,9239

Table 2 .

 2 Correlation coefficient for TPM synchronized in 900 and more cycles

dist, cos dist, fr 25 dist, fr 50 dist, fr 75 dist, fr 100 dist, fr 125 TPM

	1	0,9171	0,8560	0,8857	0,8900	0,8875	0,8730
	TPM 2	0,9349	0,8804	0,9092	0,9057	0,8998	0,8896
	TPM 3	0,9403	0,9084	0,9193	0,9103	0,8887	0,8672
	TPM 4	0,9513	0,9215	0,9519	0,9391	0,9227	0,9109
	TPM 5	0,9359	0,8479	0,8844	0,8796	0,8544	0,8278

Table 3 .

 3 Mean square error for TPM synchronized in 200 cycles

dist, cos dist, fr 25 dist, fr 50 dist, fr 75 dist, fr 100 dist, fr 125 TPM

	1	0,0278	0,0376	0,0188	0,0111	0,0145	0,0256
	TPM 2	0,0363	0,0113	0,0047	0,0074	0,0151	0,0273
	TPM 3	0,0268	0,0089	0,0079	0,0187	0,0368	0,0598
	TPM 4	0,0368	0,0152	0,0114	0,0130	0,0199	0,0319
	TPM 5	0,0189	0,0071	0,0057	0,0164	0,0363	0,0624

Table 4 .

 4 Mean square error for TPM synchronized in 900 and more cycles

dist, cos dist, fr 25 dist, fr 50 dist, fr 75 dist, fr 100 dist, fr 125 TPM

  Figures 5 and 6 illustrate the reverse normalized Euclidean distance calculated from the knowledge of the weights' vectors for both networks and the frequency of reaching the common results by two networks in 50 and 75 previous cycles. There is one network synchronization in 200 and one in over 900 cycles, respectively.

	1	0,0347	0,0121	0,0095	0,0089	0,0092	0,0108
	TPM 2	0,0395	0,0189	0,0148	0,0134	0,0125	0,0124
	TPM 3	0,0514	0,0265	0,0232	0,0219	0,0222	0,0229
	TPM 4	0,0350	0,0141	0,0098	0,0097	0,0105	0,0112
	TPM 5	0,0365	0,0217	0,0169	0,0157	0,0167	0,0180


Marcin Szpyrka
email: mszpyrka@agh.edu.pl

Bartosz Jasiul
email: b.jasiul@wil.waw.pl

Konrad Wrona
email: konrad.wrona@ncia.nato.int

Filip Dziedzic
email: filipdz@student.agh.edu.pl

Telecommunications Networks Risk Assessment with Bayesian Networks

Keywords: telecommunications networks, risk assessment, Bayesian networks

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Modern network infrastructure enables transport of information between a sender and a receiver by using different paths composed of multiple network links and nodes. It is a heterogeneous environment which involves various protocols, operating systems, software and hardware [START_REF] Sliwa | IOEM -Ontology Engineering Methodology for Large Systems[END_REF]. Moreover, a network consists of separate administrative domains, managed by different authorities. In such complex environment software bugs, protocol flaws, non-installed patches, obsolete network components, etc. introduce a risk of unauthorised disclosure or modification of transmitted information.

The diversity of telecommunication devices and protocols must be taken into account when sensitive information is transmitted. It is important not only to protect information by cryptographic measures including confidentiality, integrity and authenticity, but to take into account availability of the information as well. The operator must be made aware of potential risk of information being compromised when a specific distribution path is chosen. Naive solution consisting of stopping information exchange in case of any non-negligible risk is not viable because existence of any, even smallest, applicable and not mitigated threat would lead to stopping all communication. The solution proposed in this paper focuses on delivering a measurable indicator of risk, socalled risk signature. The risk signature takes the form of quantitative values that can be compared during the decision process, thus offering an advantage over qualitative risk indicators, such as low, medium and high.

Motivation

The work presented in this paper has been motivated by challenges related to development of the Information Exchange Gateway (IEG) concept. The North Atlantic Treaty Organization (NATO) and national forces have defined the concept of an IEG to facilitate secure communications between different security and management domains [START_REF] Apiecionek | Safe exchange of information for civil-military operations[END_REF]. Related to IEG is the concept of Content-based Protection and Release (CPR) [START_REF] Wrona | Controlled information sharing in NATO operations[END_REF]. CPR aims to improve timely sharing of information in the NATO Network Enabled Capability (NNEC) and the Future Mission Network (FMN) [START_REF] Domingo | A NNEC-compliant approach for a Future Mission Network[END_REF] environments. Potential implementation scenario for the IEGs using CPR policies is communication between NATO domains and non-NATO organisations, such as United Nations, International Committee of the Red Cross and other non-government organisations.

In current operations timely sharing of information is hampered due to a number of limitations that are inherent to the traditional use of security markings. CPR overcomes these limitations by enforcing access control based on the content properties of an information object instead of a security marking. In CPR the decision to release information object to a user is based on a protection and release policy that expresses requirements the user and the operational environment (e.g. user's terminal) must meet in order to access an information object with a given set of content properties. The requirements are translated to user and terminal attributes; as such CPR is an extension to Attribute Based Access Control (ABAC) [START_REF] Hu | Guide to Attribute Based Access Control Definition and Considerations (Draft)[END_REF].

Of particular importance for the approach presented in our contribution is that the CPR policy can also take into account specific environmental attributes such as the risk signature of the network. This enable CPR to provide risk-based adaptive access control. In our proof-of-concept implementation based on XACML 3.0 architecture [START_REF]OASIS: eXtensible Access Control Markup Language ver[END_REF] such risk signature can be obtained by the Policy Information Point from a Dynamic Risk Assessment system [START_REF] Lagadec | Cyber Defence Situational Awareness and Dynamic Risk Assessment[END_REF]. Current IEG solution assumes that surroundings of the protected domain are hostile and their the main source of threats to the information exchange. However the state of the protected domain can also influence a level of risk involved in information exchange process. For example, if some software used on nodes of protected domain has some unpatched vulnerabilities, a communication channel between untrusted domain and protected domain may introduce a possible attack path for outsider attacker. Ability to perform such attack may depend on IEG accepting mediation of particular content type or protocols. If one cannot eliminate risk, in order to control the flow of information between the domains the level of risk should influence the decision whether the information will be sent or dropped. Thus IEG should be able to selectively and dynamically modify its release policy, depending on a level of risk existing in the internal system. In this paper we present an approach for dynamic risk assessment which can be used in order to support risk-adaptable access control [START_REF] Mcgraw | Risk-adaptable access control (radac)[END_REF].

Related Work

The presented approach is in accord with recent research in the network security area, where a number of approaches (including formal ones) to the analysis and design of security systems has been proposed. For example, a formal graph model of a computer network with a variable topology is consider in [START_REF] Matousek | A Formal Model for Network-Wide Security Analysis[END_REF]. The model is used for the verification of security constraints. An extension of attack graphs called multiple-prerequisite graphs is considered in [START_REF] Ingols | Practical attack graph generation for network defense[END_REF]. A computer software based on it is used to classify vulnerabilities and recommend actions to improve network security. Anticipation game framework with the so-called strategy objectives is considered in [START_REF] Bursztein | Using strategy objectives for network security analysis[END_REF]. This extension of attack graphs is used to coupe with both the financial and temporal aspects of attacks. Some authors focuses on formal approach to the design of network elements e.g. firewalls. For example, the design of a network firewall with a formalised rule-based framework called XTT2 [START_REF] Nalepa | Formalization and modeling of rules using the XTT2 method[END_REF] is proposed in [START_REF] Nalepa | Designing reliable Web security systems using rule-based systems approach[END_REF]. Another rule-based approach that uses RTCP-nets [START_REF] Szpyrka | Analysis of VME-Bus communication protocol -RTCP-net approach[END_REF] is considered in [START_REF] Szpyrka | Design and analysis of rule-based systems with Adder Designer[END_REF] and [START_REF] Szpyrka | Decision tables in Petri net models[END_REF]. Moreover, exclusion rule-based systems are proposed in [START_REF] Szpyrka | Exclusion rule-based systems -case study[END_REF]. Due to such frameworks possible anomalies in the security policy can be eliminated during the design stage.

There are several methodologies used to asses the risk. One of the most popular is CCTA Risk Analysis and Management Method (CRAMM) [START_REF]CCTA Risk Analysis and Management Method[END_REF], which is used in the UK, Denmark and Czech Republic. NATO uses a modified version of CRAMM, compliant with NATO security policy, supporting directives and guidance. CRAMM analyses vulnerabilities of the system and potential threats that may have impact on loss of assets and functionality. It is a qualitative methodology that covers identified aspects that may affect the risk: personnel security, physical security and security of information. It utilises a large database with detailed questions and it is compliant with ISO/IEC standard [18]. A week point of this technique is a lack of possibility to analyse algorithm used to calculate the risk.

Pilar [START_REF]EAR/Pilar -Risk Analysis Environment[END_REF] is a risk assessment tool based on Methodology for Information Systems Risk Analysis and Management (MAGERIT) [START_REF]Ministerio de Administraciones Públicas: MAGERIT -version 2, Methodology for Information Systems Risk Analysis and Management, Book I -The Method[END_REF] developed in Spain. This methodology provides a qualitative risk assessment. Risk is represented as the impact of the threat weighted by its rate (or expectation) of occurrence. A customised version of Pilar is used also within NATO.

The Expression of Needs and Identification of Security Objectives (EBIOS) [START_REF]des systèmes d'information: Expression des Besoins et Identification des Objectifs de Sécurité[END_REF] methodology has been created by the French National Security Agency. The methodology covers 5 steps: context, security needs, threats analysis, identification of security objectives and identification of security requirements. It allows to assess, communicate, and choose appropriate mitigation measures for risks related to information security.

Method for Harmonized Analysis of Risk (MEHARI) is another French information risk assessment method, developed by association of information security professionals and designed for an analysis of risk situations described through scenarios [START_REF]MEHARI -Method for Harmonized Analysis of Risk[END_REF].

The Operationally Critical Threat, Asset, and Vulnerability Evaluation (OCTAVE) method [START_REF] Alberts | Operationally Critical Threat, Asset, and Vulnerability Evaluation (OCTAVE) Framework[END_REF] is a framework for identifying and managing information security risks developed by Computer Emergency Response Team. It also is a suite of tools, techniques, and methods for risk-based information security strategic assessment and planning. The method is used to: (i) identify critical assets and the threats to those assets, (ii) identify the vulnerabilities, both organisational and technological, that expose those threats, creating risk to the organisation, and (iii) develop a protection strategy and risk mitigation plans to support the organisation's mission and priorities.

Case Study

As an illustrative example for the proposed approach and calculation of risk we will use hypothetical protected network shown in Fig. 1. The network provides an access to confidential data by using two redundant database servers. The only way to collect the data is to send a request to one of the two web servers. A web server sends a request to a database server and then provides the user with the received answer. A firewall is used to isolate the network from the Internet. The security policy allows users from other domains to send requests to the services located in the protected domain. Due to different transmission media, the possible access routes differ in the level of security [START_REF] Wrona | Real-time automated risk assessment in protected core networking[END_REF]. While estimating the risk of information retrieval, it is necessary to take under consideration different confidentiality protection levels for the used transmission media. Moreover, there are additional factors affecting the security of depicted network. These are various services offered in the domain and software installed on devices. Usually, the more equipment, protocols and software are used in the network, the more potential vulnerabilities are present. These vulnerabilities might be used for taking control of either a device or a service and can lead to revealing sensitive information to adversary. Scenario presented in Fig. 1 is partially related to current NATO works on providing information exchange capability for information domains with different classification levels, e.g., NATO Secret, NATO Confidential, and Mission Secret. In the past military networks with different confidentiality level had to be completely separated. Currently, in order to facilitate information sharing, collaboration and reduce duplication of data, there is a trend to provide controlled and secured interconnection of networks operating on different security levels. Risk assessment in this case is identified as a crucial element in taking decision whether to send (or not) the information.

Proposed Solution

The proposed risk analysis method is composed of two main components. The first component (see: box 1 in Fig. 2) is dedicated to evaluation of a risk level of individual network elements and the network as whole. The second one (see: box 2 in Fig. 2) is to assess the influence of the risk introduce by the individual network elements involved in execution of a service offered to the end user on the total risk signature of this service. The first part of risk assessment method is based on MulVAL tool [START_REF] Ou | MulVAL: A logic-based network security analyzer[END_REF] (see also Sec. 5.2). Attack trees [START_REF] Schneier | Attack trees: Modeling security threats[END_REF] were chosen to assess likelihood of successful attacks on assets vulnerabilities. Attack trees (see Sec. 3) provide a formal, methodical way of describing structure of attack on specific goal. Precisely, the root node represents the object of an attack and leafs are the steps that must be done to achieve the goal. For instance, if a malicious user of a corporate network wants to read a document stored at his supervisor's computer, he needs to get access to this computer. He can trick the supervisor into running specially prepared code that will send documents to him via e-mail (social engineering attack). Alternatively, he can brake into supervisor's office, then start the computer and guess the password. At last, he can recognise the infrastructure of the network, identify the computer he wants to take control over, compromise the personal firewall, which was not updated, and inject a code that will allow him to download the document by the FTP protocol.

The second part of our method takes into account that the specific services provided to the users usually rely only on a subset of all network elements. Therefore, the fact that some high risks elements are present in the network does not necessarily mean that the particular service is exposed to high risk as well. For example, the fact that an email server is exposed in a specific network configuration to a high security risk might be irrelevant for a service which provides end user with an access to geographic information stored in a database. Thus, in order to provide a meaningful assessment of risk level which a particular service is exposed to and therefore estimate risk which is transferred to the end user and his operations the risk assessment has to take into account a specific set of network links and nodes which are utilised by the service [START_REF] Wrona | Real-time automated risk assessment in protected core networking[END_REF]. Every service can be described as a work-flow, involving different network elements, such as servers, routers, and links. We model the dependencies between steps of the work-flow as Bayesian network (also called belief network) [START_REF] Barber | Bayesian Reasoning and Machine Learning[END_REF][START_REF] Darwiche | Modeling and reasoning with Bayesian networks[END_REF] (see also Sec. 5.3).

System Description

In the example considered in Sec. 4, it is assumed that the detailed network topology with its resources and connections among them must be described and provided to MulVAL tool. Vulnerabilities of network elements, software and protocols are obtained from National Vulnerability Database (NVD) [START_REF]National Vulnerability Database[END_REF]. This database, widely used by various security vendors and computer emergency response teams, includes information on specific threats. A record from NVD, called CVE (Common Vulnerabilities and Exposures [START_REF]Common Vulnerabilities and Exposures[END_REF]), contains:

-CVE Identifier (eg. CVE-2012-5689), -description (short information on vulnerability), -asset impacted (some software, protocol), -version infected, -severity, -impact, -score (value representing potential harmfulness of vulnerability).

MulVAL

The system description is used by MulVAL tool to calculate the risk of every affected network element. In fact, MulVAL is used three times in order to assess the risk for confidentiality (C), integrity (I) and availability (A). MulVAL (Multi-host, Multi-stage Vulnerability Analysis Language) [START_REF] Ou | MulVAL: A logic-based network security analyzer[END_REF] is a research tool used to manage the configuration of an enterprise network such that the security risks are appropriately controlled. MulVAL provides a reasoning engine for automatically identifying vulnerabilities in an enterprise network. It uses Datalog facts to represent configuration information and Datalog rules to represent attack techniques and OS security semantics. After analysing the configuration of a network, the MulVAL reasoning engine outputs a logical attack graph. An example of such a graph (borrowed from [START_REF]MulVAL Attack Paths Engine[END_REF]) is shown in Fig. 3. A logical attack graph directly encodes the logical causality relationship among configuration settings and potential attacker privileges. Its key goal is to show why an attack can happen. There are three kinds of vertices in such a graph: rectangle vertices represent facts, elliptic vertices represent reasoning rules and diamond vertices represent privileges an attacker can obtain through exploiting the vulnerabilities in the considered system. The part of a logical attack graph shown in Fig. 3 refers to estimating the probability of a successful database server attack.

At the first glance, the value of the risk obtained from MulVAL can be perceived as sufficient. In fact, this method delivers assessment of risk for the network. However, the obtained value does not take into account that some network components might be irrelevant for execution of a particular service, thus even if they are high risk assets, they may not have much influence on risk level for delivery of the service to the end user. In fact, there can be various routes more often used to exchange of information. Thus, additional method is required in order to amend the value obtained from the first assessment and to present the actual risk for the particular service or mission objective supported by the system.

Bayesian Networks

Bayesian networks [START_REF] Kjaerulff | Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis[END_REF] were identified as a suitable method to accomplish this goal. Bayesian networks allow for inverse representations of the probabilities concerning two events. For instance, event B is a consequence of event A, what can be described as A → B. It means that A is the reason for the consequence B. However, the question often is: What is the probability of A if B was observed? The answer can be calculated from the statement of Bayes' theory:

P (A|B) = P (A ∪ B) P (B) = P (B|A)P (A) P (B)
, where P (B) > 0

As noted earlier, we model the dependencies between steps of the service workflow as Bayesian network. The network elements are used by the service in a specific order which has to be captured in the model. Some of the elements might appear in these workflows several times (e.g. a particular link can be used for transmitting both a request to the database and an answer to the query). Similarly, the specific steps of the service workflow can be implemented by using several different network elements. For example, there might be several independent communication links available between a Web server and a database and the database might be replicated on several separate servers for sake of performance and redundancy. In order to deal with possible cycles, it was necessary to represent some of the nodes multiple times in the resulting Bayesian network. However, this multiplication does not interfere with the calculation of the final risk values, as the risk introduced by the particular network element is taken into account only once in the overall calculation. Every network element is assigned three independent risk values related to confidentiality, integrity and availability. For the network nodes, these risk values are calculated by using the information about relevant vulnerabilities, provided in the NVD, and known applicable attacks modeled using MulVal methodology. For the network links, a simplified model has been used, assigning static risk values in the C-I-A dimensions, depending on the characteristic of the links.

The reasoning in the Bayesian network describing service dependencies has been performed by clustering algorithm as described in [START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF]. This algorithm consists of two stages. In the first stage directed graph representing dependencies between vulnerabilities and attacks is decomposed to a tree. In the second stage the appropriate inference on the obtained tree is conducted. The overall risk level is calculated from a perspective of the user accessing the service and consists of three values, describing risk to confidentiality, integrity and availability of the service. The results and the proof of concept are shown in Sec. 6.

Proof of Concept

In order to validate the proposed approach in practice, a prototype software called Network risk assessment tool has been developed. The application uses a client-server architecture, with a front-end based on a Web browser supporting JavaScript. The software has been developed by using Java and Play Framework [START_REF]Play Framework[END_REF]. All the calculations for Bayesian networks were performed with the aid of the SMILE library [START_REF]SMILE Documentation[END_REF] and for Bayesian networks visualization the GeNIe development environment has been used. The back-end application uses the PostgreSQL database server to provide all data which is necessary for risk calculations.

The developed tool takes under consideration different network devices such as hosts, servers etc. and connections among them. The MulVAL software enable us to take into consideration firewalls configuration and dependencies among resources. Dynamically constructed Bayesian networks make it possible to assess the risk of functioning of any particular service. In order to provide reliable results, we have used real information about vulnerabilities obtained from the US National Vulnerability Database [START_REF]National Vulnerability Database[END_REF]. The application has been tested successfully. One of the test cases based on the network shown in Fig. 1 is presented below. Suppose, the possible communication routes are defined as shown in Fig. 4. In such a case, we have redundant routes used to access data stored in the database servers. The aim of the computation is to assess the risk for the service that guarantee access to the data.

The redundant routes decrease the risk of loss of access to the data significantly. On the other hand, the greater the number of devices in a network is, the greater the risk of data being compromised. It is a result of potential vulnerabilities introduced by every additional node or link. These vulnerabilities might be exploited by the adversary to get an access to information or to disrupt communication.

The considered test scenario illustrates also the impact of vulnerabilities on the risk for three security dimensions: confidentiality, integrity and availability. Different vulnerabilities have different influence on the assessed risk signature. This is due to variations in difficulty of vulnerability exploitation, harmfulness, impact on the whole communication, etc. As a part of validation scenarios, we have also simulated that some vulnerabilities were detected and the related risks mitigated, in order to observe how this process influences the overall risk signatures. Values of estimated risk are shown in Table . 1.

Conclusions

The approach presented in this paper is the first step to assess the risk of compromising services and information provided by a heterogeneous networking environment. Presented solution assesses the risk derived from vulnerabilities of both network links and network nodes, including the vulnerabilities introduced by software and hardware configuration. Current implementation takes into account network elements that are vulnerable to attacks resulting in leakage, modification or unavailability of transmitted data as well as static technical security countermeasures, which can be used to reduce the applicable attack surface. One possible extension of our model is the possibility of modeling of dynamic deployment of technical security countermeasures that reduce risk. Such technical countermeasures include, e.g. intrusion detection systems, network guards and dynamically changing security policy. Obviously, it is impossible to fully exclude the risk involved in the operation of telecommunication networks due to various malware, vulnerabilities of operating systems and network components. To imagine the number of threats, one can observe how often the software (including anti-virus tools) installed on his machine are updated. Therefore information stakeholders must deal with the risk and they need to know the risk signature of their system. The proposed solution provides them with a risk valuation, which can be used by network nodes to find the best route for information exchange and can help network administrators to take appropriate decision about which network links should be considered safe or risky. The novelty of our solution is in two-step risk assessment. The first step relies on evaluation of attack graphs and uses vulnerabilities description (based on NVD) and network configuration information to assess risk signature for individual network assets. Our approach take into account both risk self-induced by particular assets and the risk induced by the operational environment. The second step involves calculation of risk signature for a particular service offered by the system to end users. Calculation of risk is performed on the basis of Bayesian networks, which allow us not only to obtain a detailed risk signature, but also to analyze reasons and consequences of risk. Our approach is comprehensive and takes into account all system components and network communication links required to provide user with a service. The calculated risk signature covers all three dimensions of security, i.e. confidentiality, integrity and availability. Our solution is more of a quantitative than a qualitative methodology when compared to some of the widely used methods, such as CRAMM or Pilar. Thus, we believe that our proposal offers broader and more detailed approach to risk assessment for system objectives and user services.

Fig. 1 .

 1 Fig. 1. Network topology

Fig. 2 .

 2 Fig. 2. The proposed approach scheme

Fig. 3 .

 3 Fig.3. Example of MulVAL attack tree[START_REF]MulVAL Attack Paths Engine[END_REF]

Fig. 4 .

 4 Fig. 4. Possible communication routes

Table 1 .

 1 Description of the test case scenario

	No Step description

Acknowledgements

Work has been partially financed by the European Regional Development Fund the Innovative Economy Operational Programme, INSIGMA project no. 01.01.02-00-062/09.


Ayan Kumar Das

Rituparna Chaki
email: rituchaki@gmail.com

Atreyee Biswas
email: atreyee11@gmail.com

Power Aware Cluster Based Routing (PACBR) protocol for Wireless Sensor Network

Keywords: Wireless Sensor Network, Data aggregation, Network Lifetime, Energy Efficiency, Cluster Head, Heterogeneous

Energy efficiency is the main challenge of wireless sensor network (WSN). Many routing algorithms have been designed to meet the demand. Hierarchical clustering is one of the effective techniques for WSN to reduce the load in the network by data aggregation, thus saving energy. In this approach cluster heads take the responsibility to gather information of different events from its neighbors and send that to the sink node. Thus cluster heads loose its energy very early, which causes selection of new cluster head before starting of every round. This paper presents a multilevel cluster based protocol for energy efficient data communication. There is a cluster head selection phase followed by sensing of data, data gathering, aggregation and finally sending the aggregated data to the base station. Simulation results show that the performance of the proposed protocol is better than Energy Efficient Clustering Algorithm (EECA) for data aggregation in WSNs.

Introduction

A wireless sensor network consists of many small sensor nodes for sensing events in a particular area and sending that information to a sink node. The sensors are very small devices, with limited battery power, and often, with no source of recharge. This makes energy efficiency the main challenge for the researchers. Most of the power aware routing algorithms aim to find the best probable path to send the information between source and base station. Often, the sensor nodes are deployed very densely so that a number of nodes sense the same event. All these nodes try to send the redundant data to the sink node using multiple paths. This may cause a huge amount of energy drainage. Selection of a head node for a region or cluster can reduce the ener-gy drainage in such situations. All the cluster members send the sensed data to the cluster head. The cluster head collects data from the members, reduce those redundant data and aggregate all the collected data. The aggregated data will be sent to the base station only by the cluster head, thus saving energy. The proposed algorithm selects a cluster head in different clusters before starting every round of aggregation and sends data to base station. The energy of the cluster head reduces, thus making the selection of new cluster head necessary after completion of every round. The energy consumption for communication between two nodes is governed by the Inverse Square Law of energy. Further the network is divided into different levels and every level has multiple clusters. All the aggregated packets coming from different cluster heads of higher level will be further aggregated by a leader node of lower level which is selected among the cluster heads of that level. Leader node will be selected depending on the distance from the base station and its residual energy. Finally the leader node will send the total aggregated packet to the leader node of next lower level and ultimately to the base station.

The remaining part of this paper is organized as follows: Section 2 deals with the review of state of the art routing topologies, section 3 gives a description of the proposed methodology, section 4 contains the simulation reports and section 5 is the concluding part.

Review Works

Energy Efficiency and increasing network longevity is the main research area in wireless sensor network for the last few years. To reduce energy drainage many algorithms have been designed to form clusters. A cluster head is selected to aggregate collected data and send that to the base station. Energy Efficient Clustering Algorithm for data aggregation in WSN [START_REF] Sha | Energy EfficientClustering Algorithm for data aggregation in WSN[END_REF] is one of the examples of clustering algorithm. It includes two phases of clustering. One is the formation of cluster heads. In this phase every node broadcast their radius, residual energy and co-ordinates to the neighbor nodes. Then the nodes will calculate competition bids to select the cluster head. The other phase is data aggregation and tree construction, which includes calculation of weight values for cluster heads depending on the distance from the base station and remaining residual energy. These weight values help to select the leader node among the cluster heads. The aggregated data will be sent to base station only by leader node which leads to uniform energy dissipation and long network longevity. Another algorithm Energy Efficient Heterogeneous Clustered scheme for Wireless Sensor Network [START_REF] Kumar | Energy Efficient Heterogeneous Clustered scheme for Wireless Sensor Network[END_REF] has assumed that a percentage of sensor nodes are equipped with more energy and are immobile with known geographical locations. The introduction of computational heterogeneity includes more powerful microprocessor, more energy, complex data processing ability, which adds a lot of advantages to this model. The Link heterogeneity is introduced with the inclusion of high bandwidth and long distance network transceiver to prolong the lifetime of the network together with reliable data transmission. The Energy heterogeneity brought about the energy efficiency to the network, however increasing the implementation cost.

Low Energy Adaptive Clustering Hierarchy (LEACH) [START_REF] Geetha | Clustering in Wireless Sensor Networks: PerformanceComparison of LEACH& LEACH-C Protocols Using NS2[END_REF][START_REF] Xinhua | Performance Comparison of LEACH & LEACH-C Protocols by NS2[END_REF][START_REF] Heinzelman | An application-specific protocol architecture forwireless microsensor networks[END_REF]20] is also clusterbased protocol, which includes distributed cluster formation. LEACH randomly selects a few sensor nodes as cluster heads (CHs). Then it rotates this role to evenly distribute the energy consumption among the sensors in the network. The cluster head (CH) compress the collected data from different nodes that belong to the respective cluster. At last that the cluster head sends that aggregated packet to the base station in order to reduce the amount of information that must be transmitted to the base station. This protocol is most appropriate when there is a need for constant monitoring by the sensor network. A user may not need all the data immediately. Hence, periodic data transmissions are unnecessary which may drain the limited energy of the sensor nodes. After a given interval of time, a randomized rotation of the role of the CH is conducted so that uniform energy dissipation in the sensor network is obtained.

The Centralized approach on the other hand includes protocols such as LEACH-C [START_REF] Geetha | Clustering in Wireless Sensor Networks: PerformanceComparison of LEACH& LEACH-C Protocols Using NS2[END_REF][START_REF] Xinhua | Performance Comparison of LEACH & LEACH-C Protocols by NS2[END_REF] which proposes the sending of location awareness of the nodes to the base station which in turn would select the cluster head on the basis of remaining energy. Such process is though effective on the basis of total energy dissipation, formation of correct number of cluster heads, the main disadvantage of this process lies in the overhead caused due to continuous involvement of the base station.

Hybrid Energy-Efficient Distributed (HEED) routing [START_REF] Younis | HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[END_REF] is also a clustering approach, which is one of the most recognized energy-efficient clustering protocols. It extends the basic scheme of LEACH by using residual energy and node degree or density. In HEED, the initial probability for each node to become a tentative cluster head depends on its residual energy, and final heads are selected according to the intra-cluster communication cost. The clustering process is divided into a number of iterations, and terminates with in a constant number of iterations. HEED achieves fairly uniform distribution of cluster heads across the network.

PEGASIS [START_REF] Lindsey | PEGASIS: power efficient gathering in sensor information systems[END_REF] includes arranging of nodes into chains so that they can communicate only with their closest neighbor, thereby minimizing the power requirement for data transmission per second and reducing overhead. However failure of any intermediate node can cut off the link between other nodes and thus can detach a portion of the network.

Clustering and multi-hop routing with power control in Wireless Sensor Network provides clustering together with power control by means of algorithms like QFR and DCNPE [START_REF] Guo | Clustering and multi-hop routing with power control in wireless sensor networks[END_REF], which are power efficient and thus prolongs the network lifetime. These algorithms state that the process of clustering is completed in two different phases, namely, THE SET UP PHASE, where the node with the maximum residual energy and maximum intra cluster broadcast power, is chosen as the cluster head; and THE STEADY STATE PHASE, where packets of request are send by the Base station through a proper power level, confirming that those packets never appear twice for a node. On receiving the request the sensor nodes send sensed data to the cluster head in a single hop; which in turn follows a reverse way to the path through which request came to it from the base station, to send the aggregated data to the Base station. The intra cluster communication process is same as LEACH whereas inter cluster communication takes place only between two cluster heads. The base station follows a power efficient path to send requests to the cluster head. Cluster heads follow the reverse path, by which energy of the nodes involved is reduced considerably.

QOS supporting and optimal energy allocation for a cluster based Wireless Sensor Network [START_REF] Tang | QoS supporting and optimal energy allocation for a cluster based wireless sensor network[END_REF] states that together with energy efficiency, The Quality of Service, which includes source to link delay, data pass rate, data loss rate etc. must also be taken under consideration. The algorithm states that each cluster is controlled by a cluster head having a finite capacity called SINGLE FIXED RATE. The relaying of traffic from cluster to cluster till the sink to minimize the data congestion and increase network lifetime, makes the cluster heads depend on total relaying data rate from its own cluster as well as other clusters.

A novel hierarchical routing protocol algorithm for Wireless Sensor Networks [9] considers energy usage and packet latency together with security against node consideration attack. The simulation result proves that NHPRA can resist more against node consideration attack than LEACH due to the level maintained hierarchy adopted by them. The communication process among the sensors is same as GSPR, however the network is prone to outside node attack.

Energy Efficient Clustering under the joint Routing and coverage constraint [START_REF] Chamam | On planning of WSNs: Energy Efficient Clustering under the joint Routing and coverage constraint[END_REF] addresses optimal planning of the different states of sensors, providing energy efficient scheduling of the states, energy efficient routing, clustering and data aggregation. The algorithm formulates the problem as an ILP model and implementation of TABU search algorithm to manage exponentially increasing computation times. It mentions four different states of sensor node such as Transmit, Receive, Idle and Sleep. A subset of the total number of nodes will remain active at a time to save energy and reduce redundancy. The cluster heads are chosen dynamically on the basis of residual energy and distance from the neighbors and a spanning tree connects all cluster heads which are only capable of routing and thus send data to the sink. It is stated that all nodes have same sensing range and transmission range and the cluster heads are dynamically selected from the nodes.

Proposed Work

Most of the existing clustering algorithms send the aggregated packet to the base station from cluster head directly. As a result the energy of cluster head node goes down very quickly and it becomes non-functioning very soon. Some other algorithm like EECA [START_REF] Sha | Energy EfficientClustering Algorithm for data aggregation in WSN[END_REF] constructs a data aggregation tree where every sub cluster head sends the data to its parent node. The parent node contents of more weight value than its child.

The weight value will be calculated depending on the remaining energy and distance from the base station. The problem with this algorithm is the child cluster head may send the aggregated data to its immediate parent node which belongs to the same level, instead of sending it to the next level directly. This leads to wastage of energy, delay and also reduces network lifetime. The proposed algorithm PACBR will divide the network into different levels, many clusters with cluster heads can be there in a same level, and sends the aggregated data to the base station in an energy efficient way and increases network lifetime also.

Basic Methodology

The Power Aware Cluster Based Routing (PACBR) protocol for Wireless Sensor Network is proposed to send the information of devastating events from source node to base station. The algorithm clusterizes the sensor nodes and chooses a cluster head for every cluster. Every node will send the sensed data to its cluster head and it will take the responsibility to aggregate those data and send that to the base station via other cluster heads. The algorithm assumes that the network is a static network, that is, after deployment the nodes are motionless and contents of same initial energy.

Base station or sink node will be of high configuration, i.e. contents of high energy, enough memory etc., deployed in a controllable place outside the network region. All sensor nodes are capable of data aggregation, compute its own residual energy and can find its geographic location. All the sensor nodes send their geographic location to the base station which will group the sensor nodes into different clusters accordingly. The whole network will be divided in different levels and a level can have more than one clusters. The level nearest to base station will be the lowest level (i.e. level 1).

After deployment all the nodes will start to sense different events and send the sensed data to its cluster head. The cluster heads aggregate the data and send them to the sink node. A huge amount of energy is needed for this type of transmission which may cause early death of the cluster head. Thus for every round, change of cluster head is required. The algorithm helps to select the new cluster head and route the aggregated data to the base station.

The energy consumed in transmitting information from one node to another can be measured with the help of Inverse Square Law. It states that the intensity (energy per unit area perpendicular to the source) of linear waves radiating from a point source is inversely proportional to the square of the distance from the source. The intensity of energy for sending data from one node to another is thus -

(1)
Where C is a constant.

The consumption of energy will be increasing with the decrease in intensity. Thus energy consumed for a node i after sending n number of messages can be calculated as-

∑ (2)
Where, d = Distance between nodes i and j Nm = Total number of sent messages from node i to j k = Constant value E a = Energy required for data aggregation The residual energy for node i will be- [START_REF] Sha | Energy EfficientClustering Algorithm for data aggregation in WSN[END_REF] If the residual energy E Ri of node i is greater than the threshold value then it becomes a candidate node of cluster head selection process. Threshold value can be defined as energy required to accept data from all nodes, aggregate that, and send that to neighbor nodes. Every candidate node will calculate the selection probability value Pi for itself.

(4) Where, ∑

E Ri is the remaining energy at node i and D i is the average distance of that node from all its neighbor nodes lying in the same cluster. 'n' is the total number of neighbor nodes of node i in that cluster. Now all the nodes will broadcast their probability value P i to their neighbors. Every node will check the values and find the maximum. The node containing the maximum P i value will send the success message to all its neighbors.

A leader node is selected from among the cluster heads of the next lower level. The cluster head with highest weight value will selected as the leader node of that level. Every cluster head will try to send the aggregated data collected from different nodes to any of the cluster head of the next lower level. To select the cluster head of the next lower level it will calculate a weight value of those cluster heads by the following equation- [START_REF] Guo | Clustering and multi-hop routing with power control in wireless sensor networks[END_REF] Where, E R =Remaining energy of the cluster head of next lower level to which the current cluster head of higher level can send data. D B =Distance from the base station of the cluster head of next lower level. D N =Distance of the current cluster head from the cluster head of the next level to which it can send data. K=constant

The cluster head with highest weight value shall be called leader node of that level. Thus the cluster head will send the aggregated data to the leader node of next lower level. Then that leader node will send that to its next lower level leader node and so on. The process continues until the aggregated data reached at lowest level (i.e. level 1). The cluster head of lowest level will not try to calculate any weight value and send the aggregated data to the base station directly. Send data to CH 14.

Data

Aggregate collected data and send to base station

Prob_Broadcast(P[ ],n).

For every node of cluster i do-If cluster id matches with the cluster id of neighbor node j then Send the probability value to node j Find_max( ) .

Simulation Result

To analyze the performance of the algorithm, a network with 20 nodes is created, which are distributed equally in four clusters residing in two different levels. The parameter list is given below- The initial power of every node is considered 500 units. The size of each packet of data is taken as 1KB. After every round the total reduction in energy of the network and the total number of dead nodes is calculated. The result obtained is compared with that of Energy Efficient Clustering Algorithm (EECA) [START_REF] Sha | Energy EfficientClustering Algorithm for data aggregation in WSN[END_REF] which proves that after 6th round more nodes are dead for EECA with compare to PACBR. The above figure shows that after 6th round the algorithm EECA [START_REF] Sha | Energy EfficientClustering Algorithm for data aggregation in WSN[END_REF] lost more energy than PACBR. Thus the proposed algorithm PACBR can send the aggregated data to the base station in an energy efficient way and increases network lifetime.

Conclusion

The proposed algorithm Power Aware Cluster Based Routing (PACBR) protocol for Wireless Sensor Network takes care of the longevity of the network. It divides the network into different levels and each level contents of multiple clusters. Each cluster has a cluster head. The cluster heads collects sensed data from other nodes, aggregate that and sends that to the base station in an energy efficient way. The simulation results prove that the algorithm works more efficiently than other existing algorithms and also increases network lifetime.

1.Set max = 0 2 .Fig. 1 .

 21 Fig.1. Sending aggregated data through different levels

Fig. 2 .Fig. 3 .

 23 Fig.2. Number of dead nodes in the network after each round

Table 1 .

 1 Dictionary Variables list

		Variable name	Description
		N	Total Number of nodes
		x,y	Coordinate values of every node
		d[i][j]	Distance between nodes i and j
		P[node_number]	An array consists probability values of each node
		E[node_number]	An array consists remaining energy of each node
		E Ci	Stores consumed energy for node i
		D i	Average distance of all neighbor nodes from node i
	3.3	Description of PACBR algorithm
		1. Input geographic location (Two coordinate values
		x,y) of every node.
		2. Make the cluster depending on the value of x and y,
		and send the Cluster Information Packet (CIP) [Node
		ID, Cluster ID] to every node N i .
		3. //Calculate energy consumed for every node i-
		Repeat step 4 and 6 for i = 1 to n
		4. Repeat step 5 for j=1 to k
		5.	a) Read Nm and Ea
			b) Eci=Eci+(c*d[i][j]*Nm)+Ea
		//End of Inner loop
		6. //Calculate Residual Energy
			Set E[i]=E[i]-Eci
		//End of outer loop
		7. For i=1 to n repeat step 8
		8.	If E[i] > Eth Then
			a. Set S[i]=1
			b. For j=1 to n repeat step c
			c.	Set D=D+d[i][j]
			//End of loop
			d. Set Di=D/n
			e. Set P[i]=E[i]/Di
			Else
			Set S[i]=0, P[i]=0
		//End of Forlooop
		9. //Broadcast probability value of every node to its
		neighbor within cluster only
			Call Prob_Broadcast(P[ ],n)
		10.	//Find the max value among the received prob-
		ability values
		Call Find_max()
		11.	For i=1 to n repeat step 12

Table 2 .

 2 Parameter list

	Parameters	Description
	Network size	100 nodes
	Initial energy	5000J per node
	MAC Protocol	IEEE 802.15.4
	Power consumption Equivalent to packet size
		and distance
	Number of rounds	At least 6