Abderrahim Benslimane
email: abderrahim.benslimane@univ-avignon.fr

Abderrezak Rachedi

Deepak Diwakar

Relative Fairness and Optimized Throughput for Mobile Ad hoc Networks *

Keywords: IEEE 802.11 MAC, Multihop, Ad hoc network, distributed algorithm, Relative Fairness

Although IEEE 802.11 provides several transmission rates, a suitable rate adaptation taking into account the relative fairness among all competitive stations, according to the underlying channel quality remains a challenge in Mobile Ad hoc Networks (MANETs). The absence of any fixed infrastructure and any centralized control makes the existing solutions for WLANs like CARA (collision-aware rate adaptation) not appropriate for MANETs. In this paper, we propose a new analytical model with a suitable approach to ensure a relative fairness among all competitive nodes of a particular channel. Our model deals with the channel quality while respecting the nodes, based on transmission successes and failures in a mobility context. Finally, each node calculates its own probability to access the channel in a distributed manner. We evaluate the performance of our scheme with others in the context of MANET via extensive and detailed simulations. The performance differentials are analysed using varying network load and transmission range. The simulation results illustrate that our proposed approach ensures a better tradeoff between fairness and throughput.

I. INTRODUCTION

Over the past years, wireless ad hoc networks have awaken critical opinions, that are still growing in the networking research community. IEEE 802.11 implements access methods for sharing the air medium in both cases: wireless LAN (which is centralized) and ad hoc networks (which is decentralized). The Distributed Coordination Function (DCF) is the fundamental MAC technique of the IEEE 802.11 [START_REF][END_REF]. It is based on Carrier-Sense Multiple Access and Collision Avoidance (CSMA/CA). 802.11 provides various transmission rates. In 802.11a, for instance, some discrete rates are available from 6mbps to 54mbps and in the most widely used 802.11b system/option, four different transmission rates are available, such as {1, 2, 5.5, 11}mbps. Although we have various transmission rates available in 802.11, there is no standard approach defined in 802.11 to select the appropriate rate for a specific condition and to ensure fairness among the competitive nodes. Various rate adaptation schemes are proposed, and take into account the Signal-to-Interference plus Noise Ratio (SINR), the Auto Rate Fall-back, the receiver feedback approach to Collision-Aware Rate Adaptation schemes. But they are not suitable for Mobile Ad hoc Networks (MANETs). A node can not adapt itself to its rate without taking into account the other competitive nodes, unlike in the centralized case. Even though it has appropriate or sufficient information about the other nodes, which are all its competitive nodes, it has no control over them. But this is not the case in Wireless Local Area Network (WLAN). If it does so in MANET, then that may become unfair with other competitive nodes.

IEEE 802.11 standard provides various transmission rates, but it does not specify any algorithm or protocol to efficiently use these rates, in order to make competitive nodes fair . The effectiveness of any rate adaptation scheme depends on how it is incorporating the effect of transmission failures (that may be caused by a channel error or by a collision). Many rate adaptation schemes have been proposed, for example in [START_REF] Chevillat | A Dynamic Link Adaptation Algorithm for IEEE 802.11a Wireless LANs[END_REF], [START_REF] Holland | A Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks[END_REF], [START_REF] Kamerman | WaveLAN-II: a high-performance Wireless LAN for the Unlicensed Band[END_REF] and [START_REF] Kim | CARA: Collision-Aware Rate Adaptation for IEEE 802.11 WLANS[END_REF], but unfortunately none of them properly takes into account this effect in their schemes. In RBAR [START_REF] Holland | A Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks[END_REF], based on SNR values, the receiver decides the next rate for the sender. But the receiver may not have a correct interpretation of the sender channel and other competitive nodes of the sender. Hence, it does not take into account the fairness among competitive nodes. In Automatic Rate Fall-back (ARF) [START_REF] Kamerman | WaveLAN-II: a high-performance Wireless LAN for the Unlicensed Band[END_REF], the sender deduces the channel condition by measuring consecutive successful and failed transmissions and adjusts its rate in accordance with them. But even in this scheme, the sender does not bother about other competitive nodes and adopts its rate without taking them into account. So, it is quite clear that ARF is not appropriate for MANETs to ensure fairness among active nodes, although it is widely used in WLAN. In [START_REF] Kim | CARA: Collision-Aware Rate Adaptation for IEEE 802.11 WLANS[END_REF] the authors tried to distinguish channel error and collision. A sender decrements its rate only upon a few consecutive transmission channel errors and increments upon some consecutive transmission successes. In some cases this approach gives a significant improvement to the throughput, compared to the previous schemes. However, this scheme does not take into account other competitive nodes, and in the case of MANET, it does not ensure fairness among competitive nodes.

In this paper, we propose an analytical model to select the rate, and this model takes into account the impact of competitive nodes, in order to create a relative fairness among the competitive nodes without significantly affecting the system throughput. This implies that a tradeoff has to be found between both of them. We propose a new approach called REFOT (Relative Fairness and Optimized Throughput), in order to ensure a balance point between absolute fairness and throughput. REFOT has the same principle as CARA (Collision-Aware Rate Adaptation), but it is adapted to MANETs' characteristics. We assess the channel quality according to the transmission failures/successes. Each competitive node belongs to the sender's transmission range. Competitive nodes can have access to the channel under different conditions, that ensure that the channel quality is evaluated by the sender before it selects its rate. Each node calculates the probability to access the channel by taking into account all its competitive nodes. A sender updates this probability each time it wants to send data.

The rest of the paper is organized as follows. In section 2, we present a few concepts and already existing techniques. Section 3 describes our analytical model. In section 4, we show the simulation setup, analysis and results. Finally, section 5 concludes the paper.

II. PRELIMINARIES

In this section, we briefly present IEEE 802.11 in DCF mode, RTS/CST mechanism and some existing rate adaptation techniques based on 802.11.

A. IEEE 802.11 DCF IEEE 802.11 Distributed Coordination Function (DCF) mode [START_REF][END_REF] combines Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) with a Request to Send/Clear to Send (RTS/CTS) handshake to avoid collisions. It works as follows: when a node wants to transmit a packet, if the node senses the medium idle for a period of time longer than or equal to a Distributed Inter Frame Space (DIFS), the packet transmission may begin with the following slot. Otherwise, the node should backoff for a certain period based on a value randomly selected from [0,CW], where CW is the contention window size. The backoff value cw is initially randomly selected from the range [0,CWmin], where CW min = 2 imin -1. CW is doubled if the transmitted packet fails, e.g., due to collisions or experiencing CRC errors. CW keeps on increasing until it reaches the upper bound CWmax, where CW max = 2 imax -1. Each time a packet transmission is successful, CW is reset to CWmin. Although DCF has a random backoff, it still can't ensure collision-free transmissions, because it might be possible that two or more nodes finish the backoff simultaneously. Beside collisions, transmission failures may also be caused by channel errors. Upon successful contention for the channel, the node requests the channel by sending a RTS to the receiver which, in return, replies with a CTS. The nodes in the vicinity that overhear the RTS or CTS defer their own transmission for a period that is long enough to let the subsequent DATA/ACK exchange happen. When the RTS/CTS handshake is completed, the sender starts the data transmission. The receiver acknowledges the data with an ACK. If no CTS or ACK is received, the sender exponentially backs off, and retransmits the RTS or the DATA. The scheme is called in this paper "Classical RTS/CTS". Since the number of transmission's retries is bounded by ssrc (station short-frame retry counter) and slrc (station long-frame retry counter), a packet is dropped after limited retries.

Usually, the RTS frame is used when the size of pending data is larger than the RT S threshold value. But using RTS/CTS handshake before every data transmission wastes the time of data transmission, mainly in the case where there is no such hidden terminal problem. Again this scheme does not take into account the channel quality and the effect of the presence of other competitive nodes in MANET and hence it can create unfairness among them.

B. IEEE802.11 ARF

ARF developed for Lucent Technology' WaveLAN-2 WLAN device [START_REF] Kamerman | WaveLAN-II: a high-performance Wireless LAN for the Unlicensed Band[END_REF], has widely implemented a rate adaptation scheme because of its simplicity. According to this scheme, if two consecutive ACKs are not received correctly, then the next retry of data transmission takes place at a lower rate and a timer is started. If a node receives 10 consecutive successful ACKs or if the timer expires, then the next transmission takes place at the next higher rate and the timer is set to zero. Indeed, ARF does not address the reason of transmission failures, i.e., channel errors or frame collisions. A node decreases its rate even though transmission failures caused by collisions which is not appropriate to have a better throughput. At the same time, this scheme does not take into account other competitive nodes and hence in MANETs, it may become unfair among active nodes.

C. CARA (Collision-Aware Rate Adaptation)

An adaptive use of RTS/CTS exchange is the core idea of this scheme. Unlike ARF, this scheme tries to distinguish the causes of transmission failures: collisions and channel errors. According to this distinction, a transmitter decrements its rate only on some consecutive channel errors, not on collisions. And hence this scheme outperforms ARF in many cases. This scheme uses probing of RTS/CTS to enable RTS/CTS exchanges. Although it has a better assessment of the channel quality than ARF and Classical RTS/CTS, it is well adapted for WLAN but not for MANET. CARA does not take into account the relative fairness among the competitive nodes that have access to the channel. In this paper, we focus on the relative fairness among the competitive nodes that have access to the channel. We give that balance between absolute fairness and throughput optimization.

III. REFOT: RELATIVE FAIRNESS AND OPTIMIZED THROUGHPUT

In this section, we present the model and show how to create a relative fairness among a channel's competitive nodes before adapting the rate. REFOT does not need any centralized coordination; it is adapted to any topology change and it takes into account MANETs' characteristics. Furthermore, REFOT ensures that the adaptation rate takes the other competitive nodes into account, in order to avoid unfair situations between competitive nodes without any degradation of the throughput.

Like in CARA, each node maintains variables to count consecutive transmission failures (n) and consecutive transmission successes (m). When the value of n reaches the RTS probing threshold (P th ), the transmitter enables the RTS/CTS exchange before sending data. If n reaches the consecutive failure threshold (N th ), the transmitter decrements its rate to a lower available rate. But, if m reaches the consecutive success threshold (M th ), the transmitter increments its rate to the next higher available rate. Moreover, we introduce two variables: the total number of transmissions (K(t)) and the total number of transmission failures (f (t)) till the current time t.

We also consider different transmission rates available in 802.11b {1 Mbps, 2 Mbps, 5.5 Mbps, 11 Mbps}. We note this set R dt and the current rate r. When the value of n reaches P th , RTS/CTS probing takes place and when this value (n) reaches N th , a transmitter chooses the lowest transmission rate in the R dt set. When the value of m reaches M th , the transmitter chooses the next available higher rate from R dt set. Hence, a transmitter knows the transmitting rate (r) at which it is going to transmit the data frame. In REFOT, a node observes its transmission failures and by taking into account the other competitive nodes, it calculates its probability to have access to the channel which is then used to calculate the backoff delay. First, a node i computes the probability of transmission failure P (i,f ) ; this probability is computed according its own experience of transmissions and failures:

P (i,f ) = f i (t) K i (t) (1)
A channel is defined as the radio area shared by the sender's competitive nodes. Logically, it represents the sender's carrier sense (CS). Let us consider a node i which belongs to the channel J. Then, we define a new metric to measure the channel quality. So, a node i computes the probability that the transmission fails within its current channel J, P (i,J) . Unlike the probability that the transmission fails, P (i,J) is the vision of node i on the state of its main channel J (i.e., its carrier sense) at the current time. We represent channel J as a set of neighbors in the carrier sense of node i at time t. To this aim, each node overhears the packets transmitted in its carrier sense in order to collect the transmission rate, the probability of transmission failure P (l,f ) and P (i,J) . Then, the probability that the transmission of node i fails within its current channel J is defined as follows:

P (i,J) = l∈J P (l,f ) r l l∈J r l (2)
where r l is the transmission rate of node l.

Each node i informs its neighbors about its current rate value r i , P (i,f ) and P (i,J) at each transmission. For example, we can use the Address 4 field (6 bytes) in the MAC header since it is not needed in ad-hoc mode [START_REF][END_REF]. Then each node calculates the probability to access the main channel as follows:

P (iAccessesJ) = 1 -P (i,J) i∈J (1 -P (i,J) ) (3)
This probability takes into account the neighbor nodes' behaviour. Each node evaluates its socialization in their society (channel). According to this metric, each node respects each other to access the communication channel. Then this probability is incorporated in order to determine the value of the lowest bound of the transmitter node's backoff window CW * min as follows:

CW * min = CW min .(1 -P (iAccessJ) ) if P (iAccessJ) = 1 CW min Otherwise
When a new node arrives, it has no information about its neighbors. So, the value of its P (iAccessJ) is initiated to 1, in order to prevent the new node from having immediately access to the channel. In that way, the backoff window of all competitive nodes is affected. The channel access of these nodes is dependent on the channel quality which is measured by the probability of transmission failure within the channel of node. This mechanism creates a relative fairness among competitive nodes. It also permits a good rate adaptation before the transmission. We have shown in the simulation's results that without affecting the average system's throughout significantly, we have a much better fairness index in comparison with CARA and classical RTS/CTS schemes, and that proves that our approach creates a relative fairness among competitive nodes, since we know that creating fairness and optimizing the throughput have a tradeoff. In order to understand this tradeoff, let us consider a simple example of a network consisting of 3 nodes with a static topology, in which there are two senders and one receiver. One sender is transmitting with a constant rate of 10M bps and another is transmitting with a rate of 1 Mbps, and both are sending data to the same receiver. In the optimal case, the maximum throughput per second can reach 10M bps if only the former gets a chance to transmit data. But if we create an absolute fairness (say let both transmit data for an equal time interval) then the throughput reaches only 5.5M bps. Our scheme has a balance point between creating a relative fairness and maximizing the throughput.

In order to study the fairness parameter, we use the Fairness Index (F I) as metric. The Fairness Index of a topology is defined as follows:

F I = N i=1 P (iAccessJ) r i N i=1 r i (4)
where N is the total number of nodes in the mentioned network topology. The probability to access the channel for each node and the transmission rate are important parameters in equation 4, which permits to calculate the F I. In REFOT, we give a new definition of P (iAccessJ) like in equation 3. But for others, like CARA and Classical RTS/CTS schemes, P (iAccessJ) is calculated as follows:

P (iAccessJ) = 1 Number of neighbouring nodes (5)
where the number of neighbor nodes can be estimated by overhearing (we assume that a node can overhear the transmission of the other nodes who fall into its transmission range properly). The Fairness Index value becomes 1 for the whole topology if each node belonging to the network has a probability to access the channel equal to 1. Here, we want to clearly state that the Fairness Index value varies with time. Since the rate changes in CARA and in REFOT, depending on the channel condition, a node may have different transmission rates at different times. Similarly, if the nodes that are present in the network are mobile, the probability to access the channel is dynamically estimated in our scheme, while this is not the case for CARA and Classical RTS/CTS approaches. Therefore, the Fairness Index value may vary with time and other parameters, such as: the channel quality, the number of competitor nodes, etc. Thus, we take an average value of this function over the simulation time to have the Fairness Index of a given topology in the whole simulation.

IV. SIMULATION SETUP AND PERFORMANCE ANALYSIS

In this section, we discuss the simulation's parameters and compare REFOT, CARA and Classical RTS/CTS approaches. We implemented these schemes in NS-2 [START_REF]The network simulator ns-2, Part of the VINT project[END_REF] in order to simulate them with different simulation's parameters. Simulation is done for static complex topology illustrated in figure 1 and various topologies with random way point mobility model for 10 and 20 nodes with several transmission ranges. Furthermore, we compared the impact of the different approaches with the UDP connections on the F I and on the throughput. We consider a network with 12 static nodes as shown in figure 1. We have flows f 1 , f 2 and f 3 which are in the same contention range and thus share one common channel. Similarly, f 3 , f 4 and f 5 share one common channel while flows f 5 , f 6 and f 7 share another common channel. All three channels are different. Since in our scheme fairness is measured on how a node respects other contenders to have access to the common resources, according to the Fairness Index (F I) equation 4, we have plotted the result of our simulation, F I versus simulation time. According to the result in figure 2, we can easily deduce that REFOT is much better to have a relative fairness among the senders. In the graph, we see that till 20sec the fairness index values are almost near to those of CARA and Classical RTS/CTS schemes but later, it raises and becomes significantly different. The probability to access the channel plays a key role in the evaluation of the Fairness Index ; its value is estimated by overhearing. Thus, a few seconds are required to correctly gather the information about the neighborhood so that a sender can estimate the

A. A network case study

B. Impact of network density on fairness and throughput

Let use now discuss the various topologies with random way point mobility model with varying the transmission ranges. We took the max speed as 5m/sec, under the area of 800mx800m with TwoRayGround as propagation model. We varied the transmission range from 25m to 250m for a topology consisting of 10 to 20 nodes.

1) Case of 10 nodes with different transmission ranges: Figure 4 shows that REFOT ensures a much better fairness in comparison with CARA and Classical RTS/CTS approaches. We note that the F I value is approximately 40% greater than in CARA and Classical RTS/CTS schemes. Since CARA and Classical RTS/CTS approaches do not take into account the fairness with adapting rate among other contenders of the channel, both have a lower value of F I. It is obvious that, as the transmission range increases, the number of contenders in the channel increases, and hence, the probability to access the channel may decrease. Therefore, the F I may decrease while the transmission range increases. In figure 5, we notice that our approach has nearly the same throughput in comparison with CARA and classical RTS/CTS approaches. Our scheme gives a much better fairness among the contenders of the channel without negatively affect the throughput. We already pointed out that creating an absolute fairness and optimizing the throughput has a tradeoff, and our scheme gives a balance between these two aspects.

2) Case of 20 nodes with different transmission range:

We set the total number of nodes to 20 and we plot the obtained results in figure 6. We note that the F I decreases by 50% in comparison with the first case (10 nodes). However, it is much better in comparison with CARA and Classical RTS/CTS approaches. We remark that the F I value is always more than 30% increment in value compared to the other schemes. In order to illustrate the impact on the throughput, we plot figure 7. We remark that the throughput in our approach is a little less than CARA scheme but better than classical RTS/CTS schemes. When the transmission range increases, the F I decreases but the throughput increases ; we can have more ways to reach the destination, because in ad-hoc networks, the communication is based on multi-hops connection. All these results clearly prove that our scheme REFOT ensures a better tradeoff between fairness and throughput in different transmission ranges and with different number of nodes.

V. CONCLUSION In this paper, we have proposed an analytical model to adapt the transmission rate and to create a relative fairness among the competitors of the common channels without decreasing the throughput significantly in comparison with other approaches. The estimation of probability to access the channel that is dynamically calculated plays a key role in our approach. We have defined a fairness index which is a metric to estimate the fairness in the topology, which depends on the probability to access the channel. We have shown in various simulations that our scheme outperforms others in any complex scenario to create fairness without decreasing the throughput significantly. Hence our approach provides a balance between having a relative fairness in adapting the rate and having a good throughput. A future work is to study and analyse our scheme with different assumptions and conditions.

Fig. 1 .

 1 Fig. 1. A complex network topology

Fig. 2 .Fig. 3 .

 23 Fig. 2. Fairness index versus simulation time with UDP flows

Fig. 4 .Fig. 5 .

 45 Fig. 4. Fairness index versus transmission range (10 nodes with UDP flows)

Fig. 6 .

 6 Fig. 6. Fairness index versus transmission range (20 nodes with UDP flows)

Fig. 7 .

 7 Fig. 7. Throughput versus transmission range (20 nodes with UDP flows)

This work is supported by the ANR "Agence Nationale de la Recherche -France" within the project framework ARA/CLADIS.


Abderrezak Rachedi
email: abderrezak.rachedi@univ-avignon.fr

Abderrahim Benslimane
email: abderrahim.benslimane@univ-avignon.fr

Cross-Layer approach to improve the monitoring process for Mobile Ad Hoc Networks based on IEEE 802.11 *

The monitoring process consists in evaluating the behaviour of nodes in networks in order to detect if the monitored nodes well-behave or misbehave. Many existing solutions deal the problem at each layer separately. Actually new kinds of misbehaviour attacks are cross-layer. So, such smart misbehaviours cannot be detected at the level of one layer. In this paper, we propose a new cross-layer approach based on physical, MAC and routing layers for a monitoring mechanism. An analytical model is proposed to illustrate the parameters' effect on these different layers. The impact of the Signal to Noise Rate (SNR), the distance between monitor and monitored nodes are clearly introduced. Moreover, the difference between the carrier sense, the interference and the transmission ranges is taken into account in our model. The simulations' results show the effectiveness of the proposed analytical model, we reach until 90% of observation's correction in some cases.

I. INTRODUCTION

The detection of a certain type of misbehaviour nodes in Mobile Ad hoc Networks (MANETs) is one of the hardest issues. Misbehaviour means deviation from the regular activity of nodes, for example routing and forwarding. It arises because of several reasons, non-intentionally when a node is faulty or doesn't have any plan to attack any node in a network. Intentional misbehaviour can aim at taking advantage (like intercepting the network traffic, saving its power, increasing its bandwidth . . . etc) or just at constituting some damage in a network. Without any detection system of misbehaviour nodes, the result effects of misbehaviour have shown that they dramatically decreased the performance of the network [1] and produced the denial of service (DoS). In order to solve the problem, many recent works proposed the solution based on the preventive aspect, for example secure a routing using cryptography such as Ariadne or SRP [2] and ARAN protocols [START_REF] Sanzgiri | An Authenticated Routing Protocol for Secure Ad Hoc Networks[END_REF]. Although these solutions are limited in an open network, for example the unknown nodes can arrive in the network, the problem is how to protect the confident nodes against prospective attacks from unknown nodes. That's why we need to monitor the behaviour of nodes in a network. A recent research work was dealing with the reputation system based on the observation of the reaction of monitored nodes [2]. For example a watchdog solution based on packets forwarding to detect the non-forwarding nodes [START_REF] Marti | Mitigating Routing Misebehavior in Mobile Ad Hoc Networks[END_REF]. The definition of the monitoring process is the set of actions that are useful to supervise the nodes' behaviour. These actions depend on the services which we want to monitor (routing, authentication, integrity, . . . ). The major problem of a current proposal of monitoring process like watchdog for example is that it doesn't take into account some characteristics of MANETs.

In this paper, we study the monitoring process to maintain the security in Mobile Ad hoc Networks (MANETs). The impact of physical and MAC's parameters protocols on the monitoring mechanisms on MANETs are investigated. The distributed coordination function (DCF) mode in IEEE 802.11 is taken as an example. We analyze different situations of monitor and monitored nodes (a distance between them, a transmission time duration, a transmission probability, . . . ). Furthermore, we propose a new analytical model which takes into account the physical layer's parameters, the MAC layer's parameters and routing layer's parameters like a forwarding process. The model proposed improves the evaluation of the nodes' cooperation and clearly distinguishes nodes which can not and those which don't want to cooperate correctly.

The rest of the paper is organized as follows. In section 2, we introduce our motivation and the problematic in monitoring process. In section 3, we describe the network assumption and a model. In section 4, we present the analytic and simulation results of a proposed model. The last section is the conclusion and we also present our future works.

II. MOTIVATION

In MANETs, all the mobile nodes don't have the same information of their neighbours, because the characteristics of MANETs like dynamic topology and the hidden nodes complicate the problem of monitoring. If we only based on the monitoring process at the network level, for example the rate of packets forwarded, we would take the risk of get a false estimation of the monitored nodes' reputation. That's why we adopt a cross-layer approach to design the monitoring process. When a monitor node wants to supervise the behaviour of its neighbours, it needs to know some important piece of information like the number of nodes in the interference range, the throughput and delay in the neighbourhood of the monitored nodes.

When the monitor node A wants to monitor a node B which is its neighbour, the node A doesn't have any piece of information about the environment of the monitored node B, if a node C is located in the interference range of the node B and cannot be heard by the monitor node A. The node C can reduce the reputation of the node B by generating an important traffic to an other node out of a sensing region of the node A and prevent the monitored node B from communicating and forwarding packets. In this event, the monitor node A gives a low estimation of the node B's reputation and classes the node B as non-cooperative.

In order to avoid this problem, the monitor node needs to know the MAC layer's parameters of its monitored neighbours. We conclude that the presence of an important traffic of nodes in the interference range of the monitored nodes and out of the carrier senses of the monitor nodes can punish the wellbehaving nodes and disturb the monitoring process.

The monitoring process proposed by Marti et al. [START_REF] Marti | Mitigating Routing Misebehavior in Mobile Ad Hoc Networks[END_REF], called Watchdog, is based on the network level; it didn't take into account the physical or the MAC level's parameters. The idea is that the monitor node can listen to the traffic of its neighbours, and detect if the monitored nodes forward the packets in the event of a routing procedure. The Watchdog's weaknesses are that it might not detect a misbehaving node in the presence of 1) monitor/monitored collisions, 2) limited transmission power, 3) false misbehaviour.

The monitor nodes can generate a false evaluation of the monitored nodes' cooperation in these following events:

• The case of a monitor collision: the monitor node can get a collision because some nodes transmit in its interference region but not in the sensing region of the monitored nodes; in this situation, the monitored node can forward the packets (subject of monitoring) but the monitor node cannot hear them. Therefore, the monitor node doesn't take into account these forwarding operations, that means the reputation reported is underestimated by the monitor node.

• The case of a monitored collision: the monitored node can have more collisions than a monitor node because it has many competing nodes that want to have access to the channel in its sensing range. In this case, the monitored node cannot transmit the packets, although it doesn't refuse to forward them. That's why, the monitor node needs to know what is going on in the hidden region (sensing region of the monitored node but not of the monitor node).

• The case concerning the presence of malicious nodes:

the presence of any malicious node in the common interference region of monitor and monitored nodes doesn't affect the monitoring process because both nodes (monitor and monitored ones) have the same observation in this region. The problem occurs when the malicious nodes are present in the interference region of the monitored nodes and cannot be heard by the monitor one. The goal of this work is to study the monitoring process in the different cases, monitor/monitored collision and false misbehaviour.

III. MONITORING MODEL

A. Network model and assumption

This subsection deals with the assumptions and the network model used in the analysis described below.

• Spacial distribution of nodes: we assume that nodes are distributed within topology which is a two-dimensional Poisson process's with parameter λ (memoryless property of Poisson distribution). • The transmission range (R t ): all nodes have the same transmission range (R t ). This means that nodes within a circle of radius R t centred at the transmitter may be able to receive correct packets. • The Carrier sensing range (R s ): the range inside which nodes are able to sense the signal, even though a correct packet reception may not be possible (it may not be able to decode the received packet correctly). • The interference range (R i ): the range inside which any new transmission may interfere with the packet reception.

The R i depends on the distance between a transmitter and a receiver (d) and the Signal to Noise Ratio (SNR) which must be above a certain threshold T SN R to consider if the signal is valid at the receiver or not. The R i is defined by,

R i = k T SN R * d
In practice, under the TWO-RAY GROUND model (open space environnement), k is equal to 4. The T SN R is usully set to 10. Then, the interference range is

R i = 4 √ 10 * d = 1.78 * d [5].
• The average number of nodes within a sensing range, an interference range and a transmission range with a radius R s , R i and R t respectively is N j ≈ λπR 2 j where j = {s, i, t} [START_REF] Takagi | Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals[END_REF].

• The probability that a node transmits in a randomly time slot is noted by τ which is independent on any time slot. The slot time size, σ, is set equal to the time needed by any node to detect the transmission of a packet from any other node. The transmission time T p of a packet is assumed to be the same for all nodes. The number of slot times γ necessary to transmit a packet is (γ = T p /σ).

Like [START_REF] Wang | Performance of Collision Avoidence Protocols in Single-Channel Ad Hoc Networks[END_REF] we assume that the duration of the successful packet transmission (RTS/CTS mode) is

T all = T rts + T cts + T data + T ack + 4σ
According to the assumptions quoted above, the relation between the carrier sensing range, the interference range and the transmission range is R t < R i < R s where R s = δR t , in some network simulator, like ns2 δ = 2.2 [START_REF]The network simulator ns-2, Part of the VINT project[END_REF].

B. The different hidden areas

The figure 1 illustrates the hidden sensing region and the hidden transmission region of two neighbour nodes A and B. The CS AB (r) (IR AB (r)) is the sensing region of the node A but not the sensing region of the node B (the interference Fig. 1. The different hidden regions, CS AB , IR AB and T R AB region of the node A but not the interference region of the node B). If any node in CS AB (r) transmits, the signal can be sensed by the node A but not by the node B. The difference between CS AB (r) and IR AB (r) is seen when a node in the region IR AB (r) transmits, it can create a collision in a receiver node A but it is not the case for the nodes in region CS AB (r). T R AB (r) is the transmission region of the node A but not the transmission region of the node B, that means the nodes in T R AB (r) can receive the packets correctly from the node A but it can not from the node B.

The difference between IR AB (r) and T R AB (r) is the problem of the hidden nodes, in T R AB (r) this problem is resolved by the RTS/CTS mechanism in IEEE 802.11 but in IR AB (r) the RTS/CTS mechanism cannot resolve this problem because the nodes in this region cannot decode the packets correctly when the node A transmits RTS/CTS/DATA/ACT. When a node senses a signal but cannot decode it, that means it cannot calculate a NAV (Network Allocation Vector), that's why it uses the EIFS (Extended Inter-Frame Spaces) 1 [START_REF]Wireless LAN Medium Access Control(MAC) and Physical Layer (PHY) specification[END_REF]. The IEEE 802.11 does not completely prevent from collisions due to a hidden node in the sensing region.

In the context of monitoring process, we assume that the node A monitors the node B. In order to get some piece of information about a cooperation with the node B, the node A transmits a few packets to it, so that it forwards them. After the monitor A has observed the behaviour of the node B, it generates the report about the forwarding rate. In this work, we focus on the region CS AB (r), IR AB (r) and the region T R AB (r) because these regions have important effects on the monitoring process. In the figure 1, when a node A monitors a node B, the node A cannot see what is happening in the region T R BA (r) (transmission region of the node B and not of the node A), the problem is that the monitor node A is unable to know if the node B doesn't want or if it can not transmit because the number of competition nodes in T R BA (r) is great. Another problem occurs in the monitoring process, in the interference region of the monitor node A and out of the carrier sense of the monitored node [IR A -CS B ]. When a 1 The EIFS is estimated at 364µs when using a 1 Mbps channel bit rate monitor A has a collision because a few nodes in IR AB (r) transmit, when a node B forwards a packet that it received from a node A, in this situation the node A is unable to know if the node B has successfully forwarded a packet or not. Thus, the monitor node A underestimated the forwarding ratio of the node B.

The regions T R AB (r) and CS AB (r) depend on the transmission range (R t ) and the sensing range (R s ) respectively and (d) is a distance between nodes A and B. We can formulate these regions by the equation 1:

CS AB (r) = πR 2 s -2R 2 s q(r/2R s ) where, r < R s T R AB (r) = πR 2 t -2R 2 t q(r/2R t ) where, r < R t (1)
where q(t) = arcos(t) -t (1 -t 2 ) and R s = αR t Fig. 2. The impact of a distance on the interference and the hidden areas Figure 2 shows an example of two neighbour nodes A and B with a different distance between them. Let r be the distance between two neighbour nodes A and B. In the case (a), the distance between node A and node B is greater than in the case (b), which means that the interference region and the region T R BA (r) in the case (a) is greater than in the case (b). When a node A comes closer to a node B, the region T R BA (r) becomes smaller and the interference region can be covered by the transmission area when the r

≤ R t 4 √ T SN R
. The average number of nodes in the region T R BA (r) depends on the distribution of the nodes and the mobility model. The greater a region T R BA (r) is, the bigger the probability to get a certain number (k) of nodes in this region is. The probability to get k nodes in the area T R BA (r) is noted p(k, T R BA (r)) and obtained by:

p(k, T R BA (r)) = e -λT R BA (r) (λT R BA (r)) k k! (2)
This analysis is valid for the CS BA (r) and IR BA (r) because it's proportional to the distance r. Remark: The monitoring process is more accurate when the monitor node A is close to the monitored node B, because the hidden region of the monitor T R BA (r) becomes small. As T R BA (r), IR BA (r) and CS BA (r) are proportional to r, when r is small, these areas are small and the probability to get a node in these regions is small, the carrier sense of a monitor node can also cover the interference region of a monitored node. Furthermore, the interference area can be covered by the transmission region when r ≤ 0.56 * R t . Thus, the probability to have a disturbance in the observation is small when the monitor node is close to the monitored node.

Therefore, before the monitor node generates the reputation report of the monitored node which is in its transmitting range, it needs to know that the event which disturbs the observation occurs and also to estimate the throughput of the monitored node. The accuracy of this information depends on the distance between monitor node A and monitored node B. The A S1S2 (d BC ) is a vulnerable region when a monitored node B transmits a packet to a node C. Furthermore, the vulnerable region of a monitor node A is the interference region of a monitor node A that is out of the sensing region of a monitored node B (A S3S4 (d AB )), where the d AB is the distance between monitor node A and monitored node B. The A S3S4 (d AB ) can have a negative impact on the monitor node's observation.

Any disturbing event in the monitoring process occurs "when a monitored node transmits successfully, and at least one node in the interference region of the monitor node and out of the sensing region of the monitored node transmits at the same time". In other words, the monitor node can correctly monitor its neighbour, if the following two conditions are met,

• 1: The monitored node transmits successfully a packet to another node of its neighbourhood. • Condition 2: The monitor node can correctly hear the transmission of a monitored node. No node in the interference region of a monitor node and out of the sensing region of a monitored node (A S3S4 (d AB )) transmits.

The monitor node needs to estimate the probability that the condition 1 and 2 are met, in order to calculate the probability that the monitor node correctly observes the monitored node when it transmits. This probability is noted P w .

P w = P {condition 1}.P {condition 2} (3)
The probability of condition 1 is defined as a successful packets' transmission of the monitored nodes noted P succ . P succ may give us information about the ability of the monitored nodes to transmit packets. However, the probability that a monitor node gets P succ of the monitored node is small, because it cannot see what happens in the whole sensing region of the monitored node, particularly in region CS BA (d AB ).

According to the assumptions quoted above, the monitor node A can estimate the average number of nodes in the region CS BA (d AB ), but another problem has to be solved is the traffic load in this region. Two main cases appear. The first one: the traffic is intensive, that means that all nodes have a packet to transmit (saturated case). In this case, many researches have been carried out in order to calculate P succ with the assumption that R t = R i = R s [START_REF] Bianchi | Performance Analysis of the IEEE 802.11 Distributed Coordination Function[END_REF] [6], but as far as we know no work took into account the difference between the transmission, the interference and the carrier sense ranges.

The second case (non-saturated case): the nodes have or not packets to transmit, that depends on the probability that nodes have a packet to transmit q. In order to calculate the P succ in this case a few researches have been carried out like Malone et al. [START_REF] Malone | Leith Modeling the 802.11 Distributed Coordination Function in Non-saturated Heterogeneous Conditions[END_REF] but they didn't take into account the difference between R t , R i and R s . In the second case, the monitor node A can not correctly estimate the P succ , it needs a cooperation with a monitored node's neighbors which overlaps the region CS BA (d BA ).

In order to calculate P w , we distinguish two different situations, the saturated case and the non-saturated case. In this work, we focus on the saturated case.

C. Saturate case

In this case, the estimated nodes in each region are the competiting nodes which want to have access to the channel.

The probability of condition 2 gives us information about the observation disruption of a monitor node. This probability is obtained by the assessment of the probability that any node in region A S3S4 (d AB ) transmits (P {cond.2}) in a vulnerable period. This period depends on the transmission time of a packet T all , when a node B starts to transmit at t s the vulnerable time interval is

[t s -T all -1, t s + T all -1].
The nodes in region A S3S4 (d AB ) must remain silent during the µ slots time where µ = (T all /σ), because a node in sensing and interference range waits for a EIFS when it can not calculate a NAV vector. If EIFS is greater than a T all , the packet can be received correctly by the receiver node C. Otherwise, a packet can not be correctly received. The region A S3S4 (d AB ) can be equal to zero when it is covered by the carrier sense of a node B. Thus, the P {cond.2}(d AB ) in the case of

d AB > Rs 1+ k √ T SN R
is given by,

P {cond.2}(d AB ) = ∞ k=0 (1 -τ ) k (N h ) k k! e -N h = e -τ N h .µ
where, N h = λA S3S4 (d AB ).

The final equation of P {cond.2}(d AB ) is obtained by,

P {cond.2}(d AB ) = 1 if d AB ≤ R s 1+ k √ T SN R e -τ N h .µ Otherwise (4)
In order to calculate A S3S4 (d AB ), we calculate the area of intersection of sensing region and interference region of two nodes X and Y; the distance between them both is d.

Ar {X T Y } (d) = R s (arccos(α) -α 1 -α 2 ) + R i (arccos(β) -β 1 -β 2 ) where α = R 2 s -R 2 i + d 2 2dR s and β = R 2 i -R 2 s + d 2 2dR i Therefore, the A S3S4 (d AB ) is expressed by, A S3S4 (d AB ) = 0 if d AB ≤ Rs 1+ k √ T SN R πR 2 s -Ar {A T B} (d AB ) Otherwise If A S1S2 (d BC ) = 0,
P w (d AB ) = P succ if d AB ≤ R s 1+ k √ T SN R P succ .e -τ N h .µ Otherwise (5)
The reputation report of the monitored node (B) generated by the monitor node (A) is given by,

R A,B (d AB ) = η.P w (d AB ) ( 6
)
where η is the forwarding ratio observed by a monitor node, η = #forwarded packets #total sent packets

The predictable forwarding packets of any monitored node depends on its reputation calculated by monitor nodes and the total number of packets it forwards.

#Forwarded packets = R * (A,B) .(#total sent packets).P w (7)

IV. NUMERICAL RESULTS AND DISCUSSION

In this section, we present the results of our model in different situations ; when the distance between monitor and monitored nodes is different and also the impact of the transmission probability τ .

The figure 4 shows the hidden area A S3S4 according to the distance between nodes A and B with 550m of sensing range and interference R i = 4 √ 10.d AB . When the distance between nodes is less than 200m the A S3S4 = 0, that means the region A S3S4 is covered by the sensing region of a node B in the case of R i = 1.78.d AB . When the sensibility of a signal is great the interference range becomes greater and the region A S3S4 becomes less covered by the sensing region of a node B as shows in the figure 4 when R i = 1.90.d AB .

The figure 5 illustrates the probability that any node in the region A s3s4 (d) transmits during the slot time µ = 1.σ. We remark that the probability P {cond.2} equals to one when the distance between A and B is less than 200 meter, due to the region A s3s4 (d) which is overlapped by the sensing region of a node B. However, when the distance between a node A and a node B becomes greater the P {cond.2}(d) decreases and it decreases rapidly when the probability of transmission τ is great. The figure 6 shows the P {cond.2}(d) when a transmission duration µ is great (µ = 5σ), we note that the P {cond.2}(d) is smaller than in the case of time duration µ = σ. We can conclude that the threshold T SN R , the distance between monitor and monitored nodes and the transmission time µ have an important impact on the monitoring process.

Figure 7 shows the probability that a monitor node A correctly receives the transmission from a monitored node B, that means a node A doesn't have a collision because no node in region A s3s4 (d AB ) transmits. We note the degradation of the monitor's observation when the distance between monitor and monitored nodes is great. In this case, the degradation of the monitor's observation can reach until 40%. Furthermore, the figure 8 and 9 illustrate the impact of the transmission probability τ and the number of slots time µ on the monitor's observation. The worst case occurs when the distance between monitor and monitored nodes is great and the probabilities of transmission τ and µ are great, and the degradation of the monitor's observation can reach until 95%.

V. CONCLUSION

In this paper, we have developed an analytical model for a monitor node in order to correctly evaluate the reputation and cooperation of a monitored node. The impact of the Signal to Noise Rate (SNR) and the distance between monitor and monitored nodes is clearly introduced, the monitor's best observation is when the monitor is close to the monitored node. In our model, the difference between transmission, interference and sensing ranges is taken into account, unlike many modellings which assume that sensing and transmission ranges are the same. Furthermore, with a cross-layer approach (Physical, MAC and routing layers) adopted for our model to get an accurate evaluation of a monitored node, we can correct until 90% of a monitor's observations.

One possible direction for a future work is to extend our model to the non-saturated case [START_REF] Malone | Leith Modeling the 802.11 Distributed Coordination Function in Non-saturated Heterogeneous Conditions[END_REF] and improve the watchdog process [START_REF] Marti | Mitigating Routing Misebehavior in Mobile Ad Hoc Networks[END_REF] by integrating our model.

Fig. 3 .

 3 Fig. 3. An illustration of different vulnerable regions in the monitoring process

Fig. 4 .Fig. 5 .

 45 Fig. 4. The hidden area A S3S4 versus distance between nodes A and B

Fig. 6 .

 6 Fig. 6. P {cond.2} versus distance between nodes A and B (case of µ = 5σ)

Fig. 7 .

 7 Fig. 7. P w versus distance between two nodes (τ = 0.4 and µ = 1.σ)

Fig. 8 .

 8 Fig. 8. P w versus distance between two nodes (τ = 0.4 and µ = 8.σ)

Fig. 9 .

 9 Fig. 9. P w versus distance between two nodes (τ = 0.8 and µ = 5.σ)

  that means that the carrier sensing region of a node B overlaps the interference region of a node C and no node transmits. Now, from equations 3 and 4, we can calculate P w (d AB ) as follows:

This work is supported by the ANR "Agence Nationale de la Recherche -France" within the project framework ARA/CLADIS.


Abderrezak Rachedi
email: abderrezak.rachedi@univ-avignon.fr

Abderrahim Benslimane
email: abderrahim.benslimane@polymtl.ca

A Secure Architecture for Mobile Ad Hoc Networks

Keywords: wireless ad hoc networks, security, clustering algorithm

In this paper, we propose a new architecture based on an efficient trust model and clustering algorithm in order to distribute a certification authority (CA) for ensuring the distribution of certificates in each cluster. We use the combination of fully self-organized security for trust model like PGP adapted to ad-hoc technology and the clustering algorithm which is based on the use of trust and mobility metric, in order to select the clusterhead and to establish PKI in each cluster for authentication and exchange of data. Furthermore, we present new approach Dynamic Demilitarized Zone (DDMZ) to protect CA in each cluster. The principle idea of DDMZ consists to select the dispensable nodes, also called registration authorities; these nodes must be confident and located at one-hope from the CA. Their roles are to receive, filter and treat the requests from any unknown node to CA. With this approach, we can avoid the single point of failure in each cluster. This architecture can be easily extended to other hierarchical routing protocols. Simulation results confirm that our architecture is scalable and secure.

Introduction

In recent years, much interest has been involved in the design of Mobile Ad-hoc Network (MANET) technologies. Mobile ad-hoc networks are characterized by their self-configuration, open peer-to-peer network architecture, shared wireless medium, stringent resource constraints, and highly dynamic network topology. These characteristics make them vulnerable to security attacks. Existing security solutions for wired or wireless networks with infrastructure cannot be directly applied to MANETs. Designing security solutions for MANET is the nontrivial challenges. The goal of security solutions is to provide security services, such as authentication, confidentiality, integrity, and availability to mobile users. In order to achieve this goal, we must develop some key management systems adapted to the characteristics of MANET. In this article, we propose a new architecture based on an efficient trust model and distributed clustering algorithm for designing the specific public key management systems. Our trust model is based on PGP (Pretty Good Privacy) approach [START_REF] Philip | The official PGP user's guide[END_REF] adapted to MANET characteristics, like fully self-organized security proposed by Hubaux et al. in [START_REF] Capkun | Self-Organized Public-Key Management for Mobile Ad Hoc Networks[END_REF]. Our distributed clustering algorithm uses the trust level and mobility metric for the selection of the cluster head (CH) which becomes certification authority (CA) in the cluster. In order to secure the cluster formation, we propose a new scheme which uses dispensable confident nodes, called registration authorities (RA). It consists to provide dynamic demilitarized zone (DDMZ) at one-hope from the CA in each cluster. The role of RAs is to protect CA, by receiving requests of certification, filtering and treating these demands before forwarding them to the CA.

The rest of the paper is organized as follows. In section 2, we discuss the related work on current key management systems developed for MANET. In section 3, we describe our global architecture, our trust model and the distributed clustering algorithm. In section 4, we present the simulation results of our distributed hierarchical architecture. In section 5, we study and analyse the security of our system. The last section consists of the conclusion.

Related work

Several works have been proposed in the literature to deal with the security problems in ad hoc networks. Specially, we investigate the distributed CA approach using threshold cryptography scheme and a clustering concept.

Distributed CA approach using threshold cryptography

Having a single central authority to distribute the public key certificate to all nodes is not suitable for MANET, because this scheme is vulnerable to single point of failure like ARAN (Authenticated Routing in Ad-hoc Networks protocol) [START_REF] Sanzgiri | An Authenticated Routing Protocol for Secure Ad Hoc Networks[END_REF]. If this node is compromised, the entire network becomes compromised.

Zhou and Haas's idea consists on distributing the CA role among n nodes of the network using (n, k + 1) threshold cryptography scheme [START_REF] Zhou | Securing Ad Hoc Networks[END_REF]. In this scheme the secret key is divided into n partial shares (S1, S2, • • • , Sn) where at least k+1 of n are partial shares which are needed to generate a secret S. The advantage is its increased availability, since any k+1 among n nodes in the local neighborhood of the requesting node can issue or renew a certificate. Another advantage is that any node, which does not have a secret share yet, can obtain a share from any group of at least k + 1 nodes which has already a share. Unfortunately, this scheme has some drawbacks: First, the k + 1 nodes must be initialized by a trusted authority. Second, the number k must be a trade-off between availability and robustness. Third, the system overloads the network because instead of sending only one request for obtaining certificate or revocation the node must send at least k + 1 request (k traffic add in network).

A clustering concept

Mobile ad-hoc network may be represented as a set of clusters. Each cluster is represented by a cluster-head (CH) and gateway nodes which manage the communication with adjacent clusters. Among several secure solutions based on clustering ad hoc networks which we studied, one is a cluster based security architecture proposed by Becheler et al. [START_REF] Bechler | A Cluster-Based Security Architecture for Ad Hoc Networks[END_REF]. This architecture use the threshold cryptography scheme (n, k) to distribute CA. The idea is to distribute the private key of CA over CHs where every CH holds a fragment of the whole key. In order to be certified, any guest node must possess a certain number (W ) of warranty certificates from warrantor nodes. After that, it must request at least (k) certificates from different CHs, whose association of these k certificates gives the network certificate. The drawbacks of the log-on procedure are as follow. First, this approach is not realistic, because the warrantors do not have any information about the new node to be guaranteed (the warrantors must have minimal information about nodes, so that they can decide to guarantee or not). Second, even the guest has already W certificates from guarantors, it cannot succeed to have K certificates from CHs and it will not be certified. Third, the network traffic generated by each new node in these procedure is at least 2 * (W + K) packets. The Becheler's architecture has some other drawbacks in merging networks process, it assembles several networks in one network. As the two network keys cannot be mixed, one of them must be dropped and the other must be distributed over the whole network. The criterion to choose the dominate key among these different network's keys depends on the number of CHs of each network. The network which has maximum CHs will become dominant network and its network key remains private key of CA. These processes present a point of failure, because in this architecture any node can construct its own cluster. Thus, a set of malicious nodes can form their network with the maximum of CHs, and then attack the network in order to merger in the network and take the CA control. This architecture does not contemplate the presence of two CHs in only one cluster due to the mobility of the nodes. Furthermore, the selection criteria of CHs are not mentioned in the paper. Also, to renew the network key, the intervention of a trust third party is needed so that it can subdivide the new key and distribute the fragment of the key over CHs. In the light of above factors, we believe that this architecture is not well adapted for Ad hoc environments.

Architecture

Firstly, we define a new trust model on which is based our architecture. Secondly, we present a clustering algorithm based trust and mobility metric to ensure a selection of trust and relatively stable confident node as CH which will become CA node in the cluster. Finally, we discuss how to evaluate certificate chain between clusters.

Primitives

The basic idea of our architecture consists of establishing dynamic public key infrastructure with CA as clusterhead that will change according to topology changes. We propose a clustering algorithm based on this trust model. A new concept is proposed to protect CA node in each cluster based on dispensable nodes.

Definition 1 DDMZ is defined as the zone of 1-hop or more from CA. It is formed by at least one or more confident nodes (RA). Their role is to not authorize unknown nodes to communicate directly with CA node. All guest nodes must be passed by DDMZ to request certificate from CA.

We assume that there are spare social relationships among nodes in order to establish trust relationship of any to-be-trust node with confident nodes. Also, every node has its own private/public key pair. Furthermore, the initial trust nodes (or confident nodes) are honest and do not issue false certificates. Moreover, each node manages a trust table. Initially, each trust node knows the identity and public key of other trust nodes (ID, K+). It means, if we have initially k trust nodes these nodes have k-1 entries (known mutually) in their trust table.

Trust Model

In our trust model, we define trust metric (T m) as continuous value on the [0..1] interval. A node i has a high trust value (T m(i) = 1), if it is known and exchanged keys over secure side channel (physical encounters and friends) with one or more of confident nodes [START_REF] Capkun | Mobility Helps Peer-to-Peer Security[END_REF] [START_REF] Capkun | Self-Organized Public-Key Management for Mobile Ad Hoc Networks[END_REF]. Another manner to obtain a high trust value is that a node must prove its good faith by adapting a good behavior and a cooperation. If a new node is added in the trust table by one or more confident nodes all others confident nodes will be aware. This is because confident nodes update and exchange their trust tables. Each new unknown node starts with T m = 0.1 its lower trust level.

Five roles of nodes are defined in each cluster and each role has particular trust level:

-CA k : Certification authority of cluster k which certificate public key of nodes belonging in the same cluster. CA k has high trust level, T m value must be equal one. -RA i,k : Registration Authority of cluster k assured by trust node i. The mean goal of RA is to protect CA against attackers that by DDMZ formation in order to prevent direct communication between unknown nodes and CA, for example, they treat and filter the requests of certification toward CA. Also, RAs must be confident nodes with T m(i) = 1.

-GW i,j : It is a gateway node ensuring a connection between two different clusters i and j. These Figure 1 shows the state transition diagram where each state represents the node's role in each cluster. The hierarchical monitoring process consists to supervise behaviors of nodes. Each node with high trust value monitors its neighbors nodes with low trust value. Figure 2 shows the possibility of a node with certain status to monitor other status nodes. CA can monitor other CAs and all other status. RA can monitor {GW,MN,VN} status, also GW can supervise {MN,VN} status. Finally MN node can supervise only VN status but VN cannot supervise any node.

In our trust model, the trust relationship is ensured by CAs between clusters. A CA can recommend node, with certain trust level, belonging in its cluster to another CA. It is also ensured by RA in order to recommend nodes which belong in the same cluster to the CA.

The trust value of a path depends on its trust chain which is represented by its certificate chain. The inter-cluster communication is based on the evaluation of the certificate chain. The trust evaluation between two nodes consists to take the small trust value of nodes (eg. Trust between RA and GW is min (1, w) where w ∈ [0.7 -0.9]). Figure 3

Distributed Clustering Algorithm

A clustering network in our architecture is ensured by a Secure Distributed Clustering Algorithm (SDCA). The main rules of this algorithm are as follow:

1. Only confident nodes (T m(i) = 1) can be candidate to become CA. 2. Each cluster-head is CA of only one cluster. 3. All confident neighbors of CA, can become RA in the cluster. 4. Other nodes are at distance of maximum d-hop from the CA according the predefined size of cluster.

Our algorithm selects CA of the cluster according to trade-off between security and stability. It is based on sending periodic beacons by each confident node to its neighbors at predefined interval time. Based on information available in the received beacons and after authentication and verification of beacon's integrity, the receivers update their information and decide about their cluster status.

The security parameter depends on trust metric, only nodes with T m = 1 and at least one trust neighbor (to establish DDMZ) can be candidate to become CA in the cluster. This constitutes the cluster formation condition. Moreover, to reinforce the security of the cluster, the algorithm selects the candidate with maximum trust degree; its means the trust node which has a maximum trust neighbors.

The stability parameter is very important on clustering algorithm, this parameter is defined as cluster-head duration. Several clustering strategies have been proposed in order to increase system stability, such as: Lowest-ID cluster-head selection based on ID [START_REF] Gerla | Multicluster, Mobile Multimedia Radio Networks[END_REF], max-connectivity algorithm [START_REF] Chiang | Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel[END_REF]. In our algorithm, we adopt a mobility metric [3][7] because this strategy gives good result 33% of reduction in the number of cluster-head changes compared with last approach [START_REF] Gerla | Multicluster, Mobile Multimedia Radio Networks[END_REF] [START_REF] Chiang | Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel[END_REF].

Each trust node puts the following information in the beacon before transmission:

-CA (Cluster-head): ID of the CA to which the node is attached.

-HopCount: hop count number to CA.

-Degree of Trust neighbors (DTN): each transmitter puts the number of its trust neighbors and their identities. -Relative mobility (RM): it indicates the relative stability of the trust node with respect to its trust neighbors as presented in [START_REF] Rachedi | A Hiearchical Distributed Architecture to Secure Ad-Hoc Networks[END_REF].

-ID number of the beacon (ID-num): it is the sequence number of the beacon which is incremented by one at each beacon transmission by the node. -Message Authenticated Code (MAC): this field is reserved to authenticate the beacon information signed with private key of the sender.

(M AC K-[CA, Hopcount, DT N, RM, ID -num])
This information permits to any trust receiver to authenticate the sender of the beacon and verify the integrity of information.

At first, each trust node sends successive hello packet in order to calculate the relative mobility RM, after that, it announces itself as CA by assigning its own address to the CA field of the beacon and initializes the Hop Count. When a trust node receives a beacon, from one of its neighbors, it executes the clustering algorithm to change its status from clusterhead (CH that is also CA) to RA or cluster-member only. The decision to change the status from CA to cluster-member depends on two main factors: security and stability parameters. Two security parameters in this algorithm have been defined: the trust level and the numbers of trust neighbors of CA candidate. These parameters indicate the security hardiness of the future cluster and the degree of attacks resistance. Another parameter is introduced: the stability of the CA. A CA is considered more stable than another one if it has low relative mobility. Any trust node with relative mobility more than certain threshold is not considered stable and will not enter in CA competition with others candidates. When competition between two candidate CAs, the CA with lower trust neighbors and also more relative mobility, loses the competition and becomes RA or member only, it depends on the distance (i.e., hop count) from the winner CA. If the hop count is equal to 1, the candidate CA becomes RA. It means that all trust nodes, directly connected (one-hop) to CA winner, can become RA. The nodes situated between two adjacent clusters can become gateway (GW). The below algorithm 1 is executed by each node which has high trust metric T m = 1; these nodes declare themselves as candidate to become CA. The extent of a node CA to manage nodes (in its cluster) at one hope or more depends on the value of d.

In order to detect the topology changes, we introduce the movement detection process. Movement of CA is detected by RA nodes while not receiving any beacon from CA for predefined period of time. Also, cluster's nodes can detect movement of RA nodes by not receiving beacons from them. The movement detection of nodes CA and RA is very important for the cluster lifetime.

Each cluster's node other than CA or RA receives the beacon from CA. It must verify the authentication and the integrity of the beacon information by using the CA's public key (K CA +). If the verification succeeds then the node updates any change about hop-count or new RA. If CA changes, cluster nodes verify the new CA identity. The information over the nodes can be assembled by trust model. Each member cluster's node update periodically the cluster's information (CA and RA nodes), for more detail, the reader can refer to [START_REF] Rachedi | A Hiearchical Distributed Architecture to Secure Ad-Hoc Networks[END_REF].

Performance evaluation

We have implemented our clustering algorithm as described previously. We use Network Simulator (NS-2) [START_REF]The network simulator ns-2. Part of the VINT project[END_REF] with CMU wireless extensions to simulate our algorithm. Simulation scenarios were generated with parameters listed in the table 1.

The movement of mobile nodes is randomly generated and continuous within the whole simulation periode. In order to compare the algorithm proposed in the previous section with others clustering algorithms. We assume that all nodes of the network are high trust level which means that any node can become CH. In Figure 4, we note that there is difference between our algorithm, MOBIC and Lowest-ID in the transmission range 50 m, because our algorithm need at least two nodes to form cluster, only one (isolated node) cannot become CA for security raison. In this simulation, the number of conceived clusters does not exceed 25. With a transmission range between 50 and 125 m the number of clusters decreases and more of 150 m the network become more stable. However, while fixing d=2 we obtain less cluster-head compared to MOBIC and lowest-ID.

The cluster-head (CA) duration is the parameter which indicate the cluster stability. The longer CA duration means the system is more stable. The simulations with 100 nodes, 2500x2500 of scenarios size and 12.5m/s of maximum speed gives 12.8 second of average CA duration. Figure 5 shows the average number of different status of nodes in the network.

Algorithm 2: Algorithm executed by a node when its RA or CA is lost The average number of isolated nodes (nodes cannot join any cluster) decreases when the transmission range increases. Also the number of CAs decreases with longer transmission range. The number of other nodes (member of different clusters) increases when the transmission range increases. The number of isolated nodes must be reduced to get more security communication in the network.

Security analysis

The security of our architecture depends directly on the trust model. The presence of a great number of confident nodes increases the security of the network.

Nodes with low trust level cannot participate in the CA election process. Only a confident node can announce itself as CA candidate. If a malicious node try to be introduced in the CA process election by announcing itself as candidate, the confident nodes can detect this in authentication phase showed in algorithm 1. If malicious nodes succeed to form their cluster and try to communicate with other clusters; the CA of cluster destination can authenticate the CA of the source cluster in inter-cluster communication. All communications from a malicious cluster are ignored. The Denial-of-Service (DoS) attack over CA node is prevented by DDMZ where RA nodes filter all requests from unknown nodes. The robustness of DDMZ depends on the number of RAs which collaborate in order to protect CA of their cluster. If attackers try to impersonate legitimate nodes as CA or RA they will be detected by monitoring process and then isolated from the network. The malicious nodes can use the identity of legitimate nodes only if their private's keys are divulgated. If attackers try to compromise all the network, it must compromise all CAs.

The number of clusters formed by our proposed solution is related to the number and the mobility of confident nodes. The cluster size must be adapted with number of confident nodes in order to well secure CA node. The presence of two confident nodes is the minimum configuration of clustering and it must be reinforced. We can use the thresholds cryptography scheme in each cluster after CA election. A CA divides its private key into n partial shares which are distributed over RA nodes.

Our system's architecture obliges nodes to collaborate and to adapt well behaviors to obtain more trust levels. Each unknown node must begin with a visitor status and then obtain the member status. In order to evaluate the trust of CA authentication, we calculate the quality of authentication (QoA), so that, we apply attenuation factor to trust chain [START_REF] Yi | Quality of Authentication in Ad Hoc Networks[END_REF]. This factor is (1 -p) (d-1) where p is the probability of the existence of compromised or a malicious node in the network and d the length of the trust chain.

QoA(V 1 -V 2 ) = T C(V 1 -V 2 ) * (1 -p) (d-1) (1)
The more trust chain is longer the more risk to be compromised is important. In this case the cluster size must be carefully chosen. The QoA between two clusters depends of the trust chain (TC) which attach CA nodes of clusters and also percentage of malicious nodes in the network. The communication between CAs must passed via high trust chain and it is assured by getaway nodes (GW).

The figure 6 illustrate the quality of authentication versus probability of malicious nodes. We have plot curves in the case of cluster size 1 and 2 hop with maximum and minimum values of TC respectively 1 and 0.49 (0.7 * 0.7). We remark the QoA linearly decrease with probability of malicious nodes increase in the case of one hop of cluster size. When we increase the cluster size at two hop we note that, QoA decrease more fast with probability of malicious nodes than the case of one hop of cluster size. The figure 7 shows the general case of QoA with different values of TC and probability of malicious nodes. We compare three case of cluster size 1, 2, and 3 hop, we remark the best value of QoA is in the case of one hop of cluster size, low value of malicious nodes and high TC.

According to the last figures 7 and 6, we can conclude that, more of the cluster size is large, the risk to have weak QoA is hight.

Conclusion

In this paper, we have proposed a new architecture based on our trust model and clustering algorithm in order to distribute a certification authority (CA).

Our clustering algorithm is based on two parameters: security and stability. The security factor is related to the trust model; only confident nodes can become cluster-head and ensure CA role. The stability factor is presented by mobility metric in order to give more stable clusters. In our approach, the trust model is accomplished by monitoring process which allows any node with high trust metric to monitor and evaluate other nodes with low trust metric. In addition, we have proposed a new mechanism to protect CA, called DDMZ, which permits to increase security robustness of clusters and endures malicious nodes that try to attack CA or issue false certificates.

Our architecture ensures the security and availability of public key authentication in each cluster. This architecture is adapted to any topology changes.

Simulation results of our clustering algorithm showed the improvement of clusters stability compared to MOBIC and Lowest-ID algorithms. Furthermore, we remark that availability and robustness of DDMZ depend on the transmission range, the number and mobility of confidant nodes. We are also considering energy conservation and lifetime of the network while conceiving clusters. Our future work is to study and analyse our architecture in order to evaluate the resistance degrees of DDMZ faced to different DoS attacks.

  nodes must be certified by two different CA. GW nodes must haves good trust level with T m(g) ∈ [0.7 -1.0]. -M N i,k : it represents a member node i belonging to the cluster k which success to pass from visitor to member status by well behaviour and good cooperation. This status can be recommended by CA k to another CA node. Node i can communicate inside and outside its cluster. It has an average trust level T m(i) ∈ [0.5 -0.7] . -V N i,k : It is a visitor node i that belongs to cluster k, it has low trust certificate, because CA k and RA j,k nodes need to have more information about node i behavior. Node i cannot communicate outside its cluster. It has a minimal trust level T m(i) ∈ [0.1 -0.5] .

Fig. 1 .

 1 Fig. 1. State transition diagram Fig. 2. Monitoring scheme

  shows two examples of certificate chain. The best trust chain (T C) is given in the case of b: T C(b) > T C(a).

Fig. 3 .

 3 Fig. 3. Certificate Chain

Fig. 4 .Fig. 5 .

 45 Fig. 4. Comaprison between different clustering algorithms

Fig. 6 .Fig. 7 .

 67 Fig. 6. QoA versus probability of malicious nodes

Algorithm 1 :

 1 Clustering Algorithm executed by confident node RM i < RM j ) OR ((RM i == RM j ) AND (DT N j < DT N i )) then

	When receiving a beacon by node j from node i;
	begin
	Authentication do if (T m(i)! = 1) then
	RejectBeacon(); Goto(end);
	else if (HopCount >= d) then
	No -Competition; Goto(end);
	else if (Accept node i as CA;
	if (HopCount == 1) then
	Status(j) = RA;
	HopCount(i) = 1;
	else
	HopCount(i) = HopCount + 1;
	Status(j) = M N ;
	else if (RM

j < RM i ) OR (DT N j > DT N i ) then node j remains as CA candidate; else if (RM i == RM j ) AND (DT N j == DT N i ) then apply Lowest-ID; end

Table 1 .

 1 If node i does not receive any beacon from CA after Timeout predefined; Simulation parameters

	begin
	if It can recover CA with another RA then
	Keep previous CA;
	Update RA node and Hop count;
	else if It can find another CA then
	Join the new CA node;
	if (T m(i) == 1) then
	if (HopCount == 1) then
	Status(i) = RA N ODE;
	HopCount(newCA) = 1;
	else
	Status(i) = M N ;
	HopCount(newCA) = HopCount + 1;
	else
	Request Certificate to RA node;
	end
	Parameter	Value in our simulation
	Number of nodes (N) 50
	Network size (mxn)	670x670m2
	Constant mobility	20 m/sec
	Transmission Range	10 m -125 m
	Pause time	0.30 s
	Broadcast interval (BI) 0.75-1.25 s
	Discovery interval	10*BI s
	Contention periode	3.0 s