Lamis Hamrouni

Ramla 📧

Bensaci

Mohammed Lamine Kherfi

Belal Khaldi
email: khaldi.belal@univ-ouargla.dz

Oussama Aiadi
email: aiadi.oussama@univ-ouargla.dz

Automatic recognition of plant leaves using parallel combination of classifiers

Keywords: Morphological features, parallel classifiers, leaf classification, plant leaves, image recognition

Because they are exploited in many fields such as medicine, agriculture, chemistry and others, plants are of fundamental importance to life on earth. Before it can be used, a plant need to firstly be identified and categorized. However, a manual identification task requires time, and it is not an easy task to do. This is because some plants look visually similar to the human eye, whereas some others may be unknown to it. Therefore, there has been an increasing interest in developing a system that automatically fulfils such tasks fast and accurate. In this paper, we propose an automatic plant classification system based on a parallel combination technique of multiple classifiers. We have considered using three widely known classifiers namely Naïve Bayes (NB), K-Nearest Neighbour (KNN) and Support Vector Machine (SVM). Our system has been evaluated using the well-known Flavia dataset. It has shown a better performance than those obtained using only one classifier.

Introduction

Plants play an important role in our life, without them there will be no existence of the earth's ecology. They are widely exploited in our life such as in food, breath, health, and even in industry fields such as medicine, economic agriculture and so on. There are millions of plants species, some of them are subject to the danger of extinction [START_REF] Murphy | A meta-analysis of declines in local species richness from human disturbances[END_REF]. Therefore, there is an urgent need for identifying plant species.

Traditionally, botanists classify plants using molecular biology and cellular features of leaves. Nevertheless, this task is very tedious, requires time and need the presence of expertise which is not available in all times. Additionally, an expert on one species or family may be unfamiliar with another. Subsequently, fast and accurate automatic plant identification system is highly needed.

Plants are usually classified using their leaves, stems, fruits or flowers. Leaves seem to be the most suitable parts that can be used to identify a plant. This is due to their availability in all seasons. In addition, leaves flatness makes it easy to be represented by the computer in some 2D.

In recent years, plant identification techniques have become a hot topic of research [START_REF] Tharwat | One-dimensional vs.Two-Dimensional based Features Plant Identification Approach[END_REF]. Authors in [START_REF] Anami | A Combined Color, Texture and Edge Features Based Approach for Identification and Classification of Indian Medicinal[END_REF] have exploited the visual features of leaves in combination with Random Forest (RF) and Linear Discriminant Analysis (LDA) to classify and identify 30 plant species. In [START_REF] Wu | A Leaf Recognition Algorithm for Plant Classification Using Probabilistic Neural Network[END_REF] a similar technique, but using Artificial Neural Networks (ANN) this time, has been opted for to identify 12 plant species. Pedro et al. [START_REF] Silva | Evaluation of Features for Leaf Discrimination[END_REF] have focused on developing a system that can automatically identify medicinal plants such as herbs, shrubs and trees. As a classifier, they use ANN then Support Vector Machine (SVM).

Reader should notice that the former works use only one classifier in their systems. Thus, some other works have tried to improve them by combining and using more than one classifiers in the system. In [START_REF] Rahman | Automatic recognition of plant leaves diseases based on serial combination of two SVM classifiers[END_REF] as instance, authors suggest using a serial combination of two SVMs. Their main idea was to devote one classifier for color features, and the other one for both shape and texture features. Their evaluation has been carried out on a dataset that contains six diseases classes. The system reports an 87.7% accuracy. In [START_REF] El Massi | Automatic recognition of the damages and symptoms on plant leaves using parallel combination of two classifiers[END_REF], authors have used a parallel combination of two classifiers namely, ANN and SVM. The first one was devoted to texture, color and shape features, whereas, then the second one uses shape and texture features. The evaluation has been carried out on a dataset that is composed of six diseases classes and they reported 91.46% accuracy.

In this paper, we introduce a system that parallel combines three classifier namely SVM, NB and KNN. As features, we consider extracting shape features (i.e., morphological features) from the leaves. The evaluation of our system has been accomplished using the well-known Flavia dataset. More details about the proposed system will be given in the next section.

The rest of the paper is organized as follow: section 2 present the architecture of our system and then discuss the used morphological features. In Section 3, we conduct experimentations on the proposed system and report results. Finally, we draw some conclusions.

Proposed system

In order to achieve a better performance, our system consists in a parallel combination of three classifiers namely SVM, NB and KNN. These classifiers are trained using a set of morphological features that we extract from the leaves. In Fig. 1, we illustrate a general scheme that resumes the different main stages of our system.

preprocessing

The preprocessing stage is, generally, responsible for applying a set of treatment (e.g., noise reduction, rotation, transformation, etc.) on the image before employing it for features extraction. In our work, we firstly converted the original color images to graylevel then to binary images. Thereafter, a smoothing filter is applied to these binary images to reduce the noise. The steps involved in pre-processing are illustrated in Fig. 2.

Fig. 2. Preprocessing stage (a)

.Image in RGB color space,(b).Gray-level image, (c).Binary image.

Features extraction

This stage aims to transform the objects into a vector of numeric values (i.e., feature vector). There are many types of features that can be extracted from an image, such as shape [START_REF] Asrani | Contour based retrieval for plant species[END_REF], texture [START_REF] Casanova | Plant leaf identification using gabor wavelets[END_REF], and color [START_REF] Kadir | Leaf classification using shape, color, and texture features[END_REF] features.

In this stage and after having the original image transformed into binary, we extract a set of shape features that describe the morphology of a leaf. Morphological features are obtained by extracting the basic geometrical properties [START_REF] Harish | Classification of plant leaves using Morphological features and Zernike moments[END_REF] of the leaf such as: diameter, area, perimeter, major and minor. Fig. 3 shows an example of some geometrical features extracted from a leaf image.

Fig. 3. Basic geometrical features

In our method, we extract the following five morphological features:

1. Diameter: is the longest distance between two points of the leaf contour D. 2. Area: is the number of pixels that constitute the area of the leaf. 3. Major axis length: is the distance between two terminal points orthogonal to minor axis length LP. 4. Minor axis length: is the longest distance orthogonal to major axis length WD. 5. Perimeter: the number of pixels at the margin of the leaf P.

In addition and based on these features, we extract another set of digital morphological features that were introduced by the authers of [START_REF] Harish | Classification of plant leaves using Morphological features and Zernike moments[END_REF] [START_REF] Buttrey | Using k-nearest-neighbor classification in the leaves of a tree[END_REF], which are:. 6. Aspect Ratio: is defined as the ratio of major axis length LP to minor axis length WP. It is also called Eccentricity or Slimness. It is given by Aspect Ratio=LP/WP. 7. Perimeter Ratio of Physiological length & width: this features is the ratio of perimeter leaf and the sum of major and minor axis length, given by PRPW=P/(LP+WP). 8. Perimeter Ratio of Diameter: it is the ratio of perimeter to the diameter, given by PRD=P/D. 9. Rectangularity: The similarity between the leaf and a rectangle, given by R=(Lp*Wp)/A. 10. Narrow Factor: the ratio of the diameter D and length Lp (i.e., NF = D/Lp). 11. Circularity: The ratio involving the area A of the leaf and the square of its perimeter P, given by C = 4πA/P2. 12. Solidity: The ratio between A the area of the leaf and Ach the area of a convex hull, given by S = A/Ach. Fig. 4 shows some of morphological features.

Classification

Classification or categorization is, generally, the process in which images are recognized, differentiated, and understood. The classifier needs to, firstly, be subjected to a set of labeled data (i.e., training set). Then, test samples will be provided to the classifier in order to recognize them.

In our work, a portion of the feature vectors, which are extracted in the previous stage, will be used to train our system that consists in three types of classifiers: KNN [l1,12], NB [START_REF] Russell | Artificial Intelligence: A modern approach[END_REF] and SVM [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF][START_REF] Chapelle | Support vector machines for histogram based image classification[END_REF]. These three classifiers are combined in parallel. The parallel approach allows the different classifiers to operate independently of each other. The results of each classifier are then merged in order to obtain a higher recognition rate.

K-Nearest Neighbor (KNN)

KNN [START_REF] Harish | Classification of plant leaves using Morphological features and Zernike moments[END_REF] is a simple yet very effective classification method. For a given test sample s, KNN mainly consists in determining the k closest training example to this s. It then states the class C that has the max membership degree to s as a class of s. the similarity could be extracted using the next formula [START_REF] Murphy | A meta-analysis of declines in local species richness from human disturbances[END_REF].

𝒅(𝒙 𝒓 , 𝒙 𝒔 ) = [∑ 𝒄 𝒊 𝑷 𝒊=𝟏 (𝒙 𝒓𝒊 , 𝒙 𝒔 𝒊)] 𝟏 𝟐 (1)

Support Vector Machine (SVM).

SVM is a supervised classifier that has a great effectiveness especially with high dimensional data [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF]. Formally, SVM constructs a hyperplane (alt. hyperplanes) that has the highest distance to the nearest training-data point of any class [START_REF] Chapelle | Support vector machines for histogram based image classification[END_REF].

Naive Bayes (NB)

Naive Bayes classifiers [START_REF] Russell | Artificial Intelligence: A modern approach[END_REF] are a family of simple probabilistic classifiers based on applying Bayes' theorem with strong (naive) independence assumptions between the features [START_REF] Russell | Artificial Intelligence: A modern approach[END_REF].

𝑃( 𝑐 𝑥 ⁄ ) = P( x 𝑐 ⁄ )P(c) P(x) (2)
where:

─ 𝑃( 𝑐 𝑥 ⁄ ): is the posterior probability of class c (i.e., target) given predictor x (i.e., attributes). ─ P(c): is the prior probability of class. ─ P( x 𝑐 ⁄ ) : is the likelihood, which is the probability of predictor given a class. ─ P(x) : is the prior probability of predictor.

Combining classifiers

The main aim of combining classifiers is to improve the accuracy. Several works have been proposed in this context [START_REF] Rahman | Automatic recognition of plant leaves diseases based on serial combination of two SVM classifiers[END_REF]. Classifier combination schemes could be roughly categorized into three main approaches, namely: sequential, parallel and hybrid combination.

Sequential combination

The sequential combination consists in placing one classifier after the other. It simpler words, the outcome of one classifier will be the input of another. Such a cascade structure helps to improve the decision taken from the previous step by including reliable samplers or excluding unreliable ones [START_REF] Rahman | Automatic recognition of plant leaves diseases based on serial combination of two SVM classifiers[END_REF].

Parallel combination

In parallel combination, the different classifiers operate independently of each other. Then, the obtained results are fused together, by some method, to produce a final decision [START_REF] El Massi | Automatic recognition of the damages and symptoms on plant leaves using parallel combination of two classifiers[END_REF].

Hybrid combination

The hybrid combination scheme takes the advantages of the two previous schemes (i.e., sequential and parallel combination) in order to reach a more reliable decision. It illustrates the two aspects of the combination which are: in on the one hand reducing all possible classes and in the other hand finding the consensus between all classifiers, in order to reach a final decision [START_REF] El Massi | A Hybrid Combination of Multiple SVM Classifiers for Automatic Recognition of the Damages and Symptoms on Plant Leaves[END_REF].

In our system, we combine the classifiers in parallel way and we opted for votingbased methods [START_REF] Ho | Decision combination in multiple classifier systems[END_REF]. In such module, each classifier provides a certain number of votes (i.e., potential classes for a given image). The final decision is then made based on these votes using the following formula:

𝐸(𝑥) = { 𝑐 𝑖 𝑠𝑖 ∑ 𝑒(𝑖) 𝑖 = 𝑚𝑎𝑥 𝑐 𝑖 ∈{1,…,𝑀} ∑ 𝑒(𝑗) ≥ 𝛼𝐾 𝑗 𝑒𝑙𝑠𝑒 𝑟𝑒𝑗𝑒𝑐𝑡 (3)
where K is the number of the combined classifiers, α is a threshold that represents the needed number of votes for the same class to be relevant.

Voting-based method could be categorized into two main categories, the simple majority vote and the weighted vote.

In simple majority vote [START_REF] Bahler | Methods for combining heterogeneous sets of classifiers[END_REF], each classifier votes for one class to be relevant to an input image. The final decision will, then, be made regarding the number of votes for each class. The relevant class is the one with the heights number of votes. Although this method is simple and effective, it suffers from the problem of rejection if all classes have the same votes number [START_REF] Rahman | Multiple classifier decision combination strategies for character recognition: A review[END_REF].

In the other hand, the weighted vote method associates each classifier with some coefficient (i.e., weight) that indicates the importance of the corresponding classifier in the combination. Selecting weights for different classifiers is a critical process and highly affects the quality of the results.

To take advantage of both the former voting methods, we suggest combining them in one module. In our used module, the system tries, firstly, majority vote method. If a conflict accrues using majority vote, then, the system opts for weighted vote method. The following algorithm resumes these two steps.

If (DSVM==DKNN==DNb) Then

FD ← DSVM+DKNN+DNB Else FD ← α DNB + β DKNN+Ω DSVM Endif

Experimental results

The evaluation of the used approach has been carried out on Flavia dataset [START_REF] Wu | A Leaf Recognition Algorithm for Plant Classification Using Probabilistic Neural Network[END_REF]. Flavia contains 1907 images that are categorized into 32 classes. In our experiments, the dataset has been divided into two subsets. The First one consists of 1284 images (70%) used for training, whereas the rest 623 images (30%) have been used to test the system. We opted for Accuracy to be used as an evaluation metric of our system. It is given by the following formula.

Accuracy (%) = Nc Nt * 100 ( 4
)
where Nc is the number of correctly classified images and Nt is the total number test.

In order to prove the performance of our method, we have firstly classify images using independently each classifier. Table 1 shows the obtained results. From the Table 1 we can see that the best result has been yielded by naive-bayes (72%). Because It makes use of all the features contained in the data, and analyses them individually as though they are equally important and independent of each other. Additionally, we can see that SVM has not performs well compared to the others (59%). This low performance can be attributed to the low-dimensionality of the used data [START_REF] Chapelle | Support vector machines for histogram based image classification[END_REF].

After evaluating each classifier separately, we will, next, evaluate the combinations of different classifiers. The obtained results are shown in Fig. 6. As Fig. 6 shows, combining classifiers does not improve results but rather decrease them in most cases. Because of suffering from low-dimensionality of data, SVM degrade the results of the different combinations by declaring conflicts in classification. Such issue could be resolved by assigning weights to the different classifiers. Thus and according to Table 1, the best classifiers has been associated with higher weights, combined then evaluated (i.e., 𝛼 = 2, 𝛽 = 2, Ω = 1). As it is illustrated in Fig. 6, combining these three classifiers with their corresponding weighs has yielded better results (76%).

Conclusion

In this paper, we have proposed an automatic plant classification system. Our system is based on a parallel combination of three classifiers namely KNN, NB and SVM with two combining modules namely sample majority vote and weighted vote. These classifiers are firstly trained with a set of morphological features that describes the shape of the leaf. Our system has been evaluated using the well-known Flavia dataset. After evaluating each classifier separately, we have found out that NB is the best classifier among all. We, then evaluate the different possible combinations of classifiers. Results indicates that SVM negatively effects the results because of the low-dimensionality of data especially by using simple majority vote module. To solve this issue, we have opted for weighted vote with the following weights 2, 2 and 1 that corresponds respectively to NB, KNN and SVM. By associating the lowest weight to SVM, our system reduces its negative effect to the voting process. The former combination has yielded best results. Future works should consider using more powerful classifiers such as neural networks or discriminate analysis. Average accuracy(%)

Fig. 1 .

 1 Fig. 1. Architecture of the proposed system.

Fig. 4 .

 4 Fig. 4. Morphological features. (a). Form ellipse, (c). Rectangularity (d). Circularity

  Fig 5 shows representative simples from this dataset.

Fig. 5 .

 5 Fig. 5. Representative samples from Flavia dataset.

Fig. 6 .

 6 Fig. 6. Comparing the accuarcy yielded by different classifiers.

Table 1 .

 1 Accuracy results using each classifier separately.

	Classifier	Average accuracy%
	NB	72,231
	KNN	65,810
	SVM	59,390


Hadjer Goumidi
email: hadjer.goumidi@univ-setif.dz

Zibouda Aliouat
email: zaliouat@univ-setif.dz

Makhlouf Aliouat
email: maliouat@univ-setif.dz

Ecient Broadcast of Alert Messages in VANETs

Keywords: Hadjer Goumidi, Zibouda Aliouat, Makhlouf Aliouat Ecient Broadcast, Emergency message, Dependable delivery, VANETs

de documents scientifiques 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

The technological development that has seen the world of today aects all areas, particularly the communication area which is experiencing a considerable evolution by the advances of wireless technology which has partially solved the problem of road accidents. Our work is coming in this context. In order to solve the problem of vehicle crashes, researchers think to exploit this technology enabling vehicles to establish direct (or indirect) links between them for being aware of potential critical situations like imminent accident or dangerous obstacles. This enabling technology is represented by VANET (Vehicular Ad hoc NETwork). Indeed, one of the promising applications of these networks is to allow vehicles equipped with specic sensors to detect the immediate environment, and alert drivers of vehicles around early in case of accident risks. VANET as comfort communication can be made by two means: Periodic Safety Message (Referred in the sequel as Beacon) and Event Driven Message (referred as Emergency Message). Both message types share only one control channel. The Beacon messages are messages about status of sender vehicle. Status information includes position, speed, heading towards, etc • • • about the sender.

Beacons provide resent or latest information of the sender vehicle to all present vehicles in the network, which help to know the position in the current network and anticipate the movement of vehicles.

Beacon messages are sent antagonistically to neighboring vehicles every 10 seconds. Emergency Messages are messages sent by a vehicle that detects a potential dangerous situation on the road; this information should be dispersed as alarm or alert to other vehicles pointing out a prospective danger that could aect the incoming vehicles. VANET is a high mobile or volatile network where nodes are kept changing their positions, moving in speed, which means that these vehicles may be get inuence, even if they are very far from the danger. They can reach a danger in short time, so a fraction of second should be very important to avoid a danger [START_REF] Samara | Intelligent emergency message broadcasting in vanet using pso[END_REF]. Because of the importance of these messages exchanged between vehicles, it is necessary to ensure that these messages attain the largest number of vehicles in a minimum delay. These emergency messages are delivered in broadcasting way, where all the vehicles within the coverage area of the sender should receive the messages. The communication range of sender is not enough, due to the fading eects and attenuation; it hardly reaches a 1000 m (which is the DSRC communication range). Critical information should be received by vehicles, in time, far from the danger for avoiding risks. The prospect of message reception can reach 99% in short distances and can be decreased up to 20% at half of the communication range [START_REF] Torrent-Moreno | Broadcast reception rates and effects of priority access in 802.11-based vehicular ad-hoc networks[END_REF]. Therefore, it is necessary to provide a technique for raising the emergency message reception with high reliability and availability. The dissemination of the emergency messages poses several problems such as collisions, the problem of broadcast storm, problem of the hidden node etc. Several works such as PCBB, CBB, and EMDV... have been proposed to solve the problem of broadcasting emergency messages in VANETs.

Related Works

In [START_REF] Chen | An emergency message dissemination protocol using n-way search with power control for vanets[END_REF], authors proposed a Dynamic Search-Assisted Broadcast (DSAB) protocol to ecient broadcast of emergency messages in VANETs. It based on controlling dynamically the transmission power to estimate the vehicle density and the use of n-way search mechanism to nd the farthest vehicle in VANETs. The problem of this protocol is the choose of one vehicle which is the farthest one to rebroadcast the message because in VANET, vehicles always change their position and the farthest vehicle may do not receive the message, it may become out of range transmission when sending the message or it cannot receive the message because of the channel problems. A Distribution-Adaptive Distance with Channel Quality (DADCQ) protocol for ecient multi-hop broadcast of VANET is presented in [START_REF] Slavik | Spatial distribution and channel quality adaptive protocol for multihop wireless broadcast routing in vanet[END_REF]. It combines local spatial distribution information and other factors with the distance method heuristic to select rebroadcasting nodes. Authors in [START_REF] Li | A distance-aware safety-related message broadcasting algorithm for vehicular networks[END_REF] presentd new distance-aware safety-related message broadcasting algorithm to enhance the propagation distance in the latency time of safety related message broadcasting. It generates the lenghts of backo times by calculating the distances between the source node and its forwarding node. The farthest forwarding vehicle has the highest probability to forward messages. In [START_REF] Yang | A data dissemination mechanism for motorway environment in vanets[END_REF], authors proposed an algorithm for data dissemination mechanism for motorway environment in VANETs. This protocol is based on an improved K-nearest neighbors prediction to predict the status of the nodes, and on construction of a forwarder set to avoid the broadcast storm problem. Limited Area-Based (LAB) scheme [START_REF] Kang | Limited area broadcast for warning message delivery over vehicular ad-hoc networks[END_REF] adjusts the size of an area that contains the broadcasting nodes for obtaining a faster propagation time. Authors in [START_REF] Virdaus | A counting-based broadcast model of emergency message dissemination in vanets[END_REF] presented a counting-based broadcast model of emergency message dissemination in VANETs which is based on counting all possible cases of contention window assignments to all the vehicles simultaneously receiving a broadcast message. In [START_REF] Samara | Intelligent emergency message broadcasting in vanet using pso[END_REF], authors proposed Pso Contention Based Broadcast (PCBB) protocol that allows vehicles to increase the reception percentage of emergency information. In this protocol the network must be divided into several segments to help the sender to determine the next forwarder of the emergency message which is the furthest vehicle in the last non-empty segment. The MIN is the lower bound of the last non-empty segment it calculated using the tness function [START_REF] Samara | Intelligent emergency message broadcasting in vanet using pso[END_REF].

This protocol has a serious problem because the MIN calculation by tness function is not always correct. In some cases, the MIN is greater than the max, this algorithm can be applied only in dense areas where the number of vehicles is large and the distance between them is small.

In [START_REF] Batish | Ecient broadcasting protocol for vehicular ad-hoc network[END_REF], the authors proposed that the reception probability of the broadcast message instantly decreases at a distance greater than 66% of the transmission range, then they choose the forwarder as the node that has a distance equal to 66% of the transmission range. To resolve the problem of the Protocol PCBB, we tried to apply this algorithm which chooses the node that has a distance equal to 66% of the transmission range of the transmitter as forwarder When we choose the node 66%, not the max (the farthest), the message takes a great reception time than that of the max. This algorithm does not use segmentation, so the forwarder has not potential nodes, and if the message fails to arrive to the forwarder it will be lost.

THE PROPOSED PROTOCOL

As a rst step in our approach, we will present the EBAM (Ecient Broadcast of Alert Messages) protocol that ensures safe transmission of alert messages. From the disadvantages noted during the study of the protocols proposed in the specialized literature, we were able to identify an approach to avoid some problems detected in these protocols. The approach also assured high reliability avoiding collisions, decreasing the channel load with minimal cost and low response time. EBAM protocol can be used in all areas (dense and sparse networks) contrary to PCBB algorithm which can be applied only in dense areas. The main idea of our protocol is to transmit the message to the farthest node within the transmission range. This node is dened as a forwarder. If the forwarder does not receive the message we resort to using potential nodes, such as the min of these nodes represents 60% of the farthest node distance.

We choose 60% as a lower bound because in [START_REF] Batish | Ecient broadcasting protocol for vehicular ad-hoc network[END_REF] authors suppose that the distance 66% is the most appropriate to increase the reception rate.

Our approach has four steps:

Preparing to send

Each node n i knows the position of its neighbor nodes because of periodic security messages that are transmitted every second (beacon), allowing to calculate the distance between nodes to select the forwarder.

The selection of forwarder inspired from the PCBB protocol, which is the furthest vehicle in the last non-empty segment by using the formula (1):

F i,j = j / max(Dist i,k ); k ∈ V i (1)
The RSU sends its location to all nodes in its transmission range periodically, and each vehicle can calculate the distance between it and the RSU, for deciding which will receive the emergency message (forwarder or the RSU) by using the formula (2):

Dist i,j = min(Dist i,RSU , Dist i,Fi,j ) (2)
In sparse area, we can found the case when the RSU is within transmission range of node (i) and it is farther than the forwarder as explain in example of Fig. 1.So, each vehicle must check if the RSU is within its transmission range, it will receive the message , else it sends the message to forwarder. We calculate the min by using formula (3):

Bmin i = Dist i,Fi,j × 60% (3)
When a vehicle detects an emergency (e.g. accident), it creates an alert message ADV-ALERT, the format of this message is represented in Priority identier this identier is used to classify the messages according to their importance in order to make it easier for the receiving vehicle to know the importance of the messages.

Forwarder ID We select the forwarder as the last vehicle in the last non-empty segment to avoid collisions and to transmit the message very quickly.

Transmission time and Delay

The emergency message requires a short time, and the transmission of the emergency message after this time occupies the channel and loads the network without interest. The sender denes its message transmission time and the delay (Del) of this message.

Position the absence of characterization of the emergency event causes network load problem and can cause collisions leading to message loss and delay in reception. To solve this problem, the vehicle that detects the event sends the position of that event using GPS.

Min it is necessary to send the min in the message, for each vehicle that receives this message to know if it is a potential node or not.

Data the emergency message must contain important data such as:

-If there are victims or wounded persons.

-The nature of the urgent case (accident, avalanche...). If a vehicle detects an event, it checks whether the same location exists in the emergency message table, if so, it does not creates the message, otherwise it creates the message and it adds the location of this event. The use of the event position can help the emergency vehicles (ambulances) to intervene more quickly.

SourceID MessageID PriorityID ForwarderID Transmission time Delay Position Min Data

The sending step

After the creation of the emergency message ADV-ALERT and the selection of the forwarder, the sender broadcasts the message in the network to alert other vehicles about any potential danger.

Receiving step

Each vehicle existing in the transmission range of the sender that receives the message ADV-ALERT, checks if it is a potential node by using formula (4):

S = Dist i,j -Bmin j ; j ∈ P i , S 0 j ∈ V i , S < 0 (4)
The vehicles running in the last segment (potential nodes) initiate a contention time for waiting the forwarder to transmit a reply by using the formula (5) as explained in the example of Fig. 2.

CT = tt + t 1 + t 2 + ε (5)
Then they detect the channel if no reply has been transmitted from the forwarder or other vehicles. It means that the forwarder has not received the message, so the rst vehicle from the potential vehicles set that transmits the reply is dened as a forwarder. Once the reply is transmitted, the other vehicles stop the transmission to avoid collisions. Fig. 3 depicts the receiving step. Before sending the reply, the forwarder must check if it saved the ADV-ALERT in its emergency message table for sending the reply and for transmitting the ADV-ALERT to its forwarder. As shown in Fig. 4, it must check:

Priority ID: The forwarder checks the importance of the message if it is a big number, it does not save it, if none it checks the other indices (if they are acceptable) it saves the message in the table according to its priority level.

Transmission time and Delay: In general, the alert message is urgent and it does not take much time. Each vehicle receiving this message must calculate D using formula [START_REF] Slavik | Spatial distribution and channel quality adaptive protocol for multihop wireless broadcast routing in vanet[END_REF]. To decide saving the message or not, in its emergency message table for the retransmission, the node uses the formula [START_REF] Torrent-Moreno | Broadcast reception rates and effects of priority access in 802.11-based vehicular ad-hoc networks[END_REF]:

D m = T r -T e (6)
h = Del -D m , m ∈ T [i] , h 0 m ∈ T [i] ,
h < 0 (7)

Fig. 3: Alert message reception owchart.

After each 30s, each vehicle must update its table, the messages that exceed the delay will be deleted. Source ID and Message ID are used to check if the message is transmitted before or not. If the forwarder found that the ADV-ALERT message has the same Source ID of a message stored in the emergency message table, it should check its message ID: if it found the same message ID then it does not save the message, otherwise the message will be saved.

Rebroadcasting steps

After saving the ADV-ALERT in emergency message table, The forwarder must broadcast it in its transmission range to its forwarder and follow the same steps dened previously.

Simulation

4.1 Simulation parameters the simulation parametres are shown in table 3.

Fig. 5 shows the number of messages transmitted, lost and received over the time for the PCBB protocol. We note that only one message is received the rest of messages are lost (the Min is greater than the max) until the end of the simulation.

Fig. 6 shows the number of messages transmitted, lost and received over the time for the 66% protocol. It is clear that the number of lost messages is great, only 8 messages among 307 sent messages are received and the rest is lost. This loss is due to the absence of potential nodes. Fig. 7 shows the number of messages transmitted, lost and received over the time for EBAM proposal. We note that in the proposed protocol the time that the message reach the RSU and the numbre of messages transmitted is less than in the PCBB and 66% protocols, this is due to the absence of lost messages practically. So the vehicle does not need to retransmit the message. At any time of simulation a packet sent can be not yet received but at the end of simulation all packets sent reached the destination. Fig. 8 shows messages loss rate according to the number of messages transmitted in the three protocols. We note that the messages loss rate in our protocol is approximately zero, and the two other protocols have a great loss rate compared to the EBAM, but the loss rate of the PCBB protocol is greater than in the 66% protocol.

Fig. 9 shows the reception delay of alert messages according to the three protocols. We calculate the reception delay of alert message by using the expression [START_REF] Torrent-Moreno | Broadcast reception rates and effects of priority access in 802.11-based vehicular ad-hoc networks[END_REF]. From Fig. 9, we note that in EBAM, a message is received after 40.63s from its transmission, but in the other two protocols the message does not arrive at the RSU (the simulation time is exhausted and the message did not achieve its destination). The loss rate of the three protocols is calculated by ( 8):

M sg L = M sg s -M sg r ; LR = M sg L M sgs (8)

Evaluation of protocol performance

For evaluating our protocol performance, we tested various scenarios by changing the parameters. We remark that the reception rate is almost 20% when nodes broadcast the message between them. When one RSU broadcasts it, the reception rate is increased up to 80%, and in the case where two RSUs broadcast the message, the reception rate reach approximately 100%(the RSUs almost cover all the Topology).

Fig. 11 represents the simulation result of reception delay in second compared with the number of nodes. In this scenario we change only the number of nodes we use, 50, 100, 200, 350 and 500 nodes. The reception delay is decreased with the increase of the number of nodes. This is due to the number of vehicles that transmit the message. When the number of vehicles becomes important, the message takes less reception time.

Fig. 12 represent the simulation result of reception delay in second related to the changing in speed. In this gure we change the speed parametre; we test speed of 6, 12, 20, 40 and 100 m/s with xed number of nodes (100 nodes). The reception delay decreaseed up with the increase of speed due to the speeds of the vehicles transmitting the message. When the speed of the vehicles is important the message takes less time to be received.

Conclusion

In this paper, we studied the problem of ecient emergency message transmission in VANETs in order to propose a solution respecting dependable communications and specic time constraints of VANET environments. The EBAM proposed protocol showed an appreciable improvement of successfully delivered urgent messages in accordance with the real time constraint. This enhanced result obtained even at high network density and high node velocities is of great importance in order to well-timed reacting to crucial events (Like road accidents) by rescue services. As a future work, it is desirable to increase the improvement of the proposal, by considering the vehicle directions using GPS.

Fig. 1 :

 1 Fig. 1: Case of RSU further than forwarder.

Fig. 2 :

 2 Fig. 2: Contention time illustration.

Fig. 4 :

 4 Fig. 4: Flowchart for checking message saving.

Fig. 5 :

 5 Fig. 5: Number of messages transmitted, received and lost in the PCBB protocol.

Fig. 6 :Fig. 7 :

 67 Fig. 6: Number of messages transmitted, received and lost in the 66% protocol

  Fig. 10 represents the reception rate of the alert messages compared with the number of nodes according to the number of RSUs. In this gure we change the number of nodes and RSUs and the topology; we use, 50, 100, 200, 350 and 500 nodes, with 0, 1 or 2 RSUs in topology of 2000*2000 (m 2 ).

Fig. 8 :

 8 Fig. 8: Messages loss in the three protocols

Fig. 11 :

 11 Fig. 11: Reception delay according to number of nodes.

Fig. 12 :

 12 Fig. 12: Reception delay vs speed.

Table 1 :

 1 Value notations table

	Notation Fij Vi Dist a,b Bmin(i) Del D m T(i) Pi CT tt t1 t2 LR Msgs Msgr MsgL	Value The forwarder of node (i) The neighbors of node (i) The distance between node a and b The lower bound (min) of node (i) The delay of message dened by the sender The delay of message Message Emergency message table of node (i) Potential node for node (i) Contention time Transmission time The duration of message transmission to the forwarder The duration of ACK transmission from potential node to forwarder Loss rate Messages sent Messages received Massages lost

Table 2 .

 2 The emergency message contains:Source identier to avoid the problem of broadcast storm, we use this identier which prevents the sender to retransmit the same message.Message identier We use this identier to dierentiate messages transmitted by the same sender. If the transmitter detects various accidents, it must send a various emergency messages, and vehicles must dierentiate if this message is a new emergency message or it is a broadcast storm problem.

Table 2 :

 2 Format of the emergency message.

Table 3 :

 3 Simulation parameters.

	Topology (m 2 )	1000*1000
	Number of nodes	100
	Number of RSUs	1
	Communication range of nodes	300 m
	Communication range of RSU	1000 m
	Speed (m/s)	6
	MAC layer	MAC 802_ 11
	Simulation Time(s)	300 s
	Mobility model	Random Following IDM_ LC


Zibouda Aliouat
email: zaliouat@univ-setif.dz

Makhlouf Aliouat
email: maliouat@univ-setif.dz

Improved Sensed Data Dependability and Integrity in Wireless Sensor Networks

Keywords: WSN, Dependable Data Sensing, Trusted Data Aggregation, Secure Data Transmission

The mainspring of a Wireless Sensor Network (WSN) is to capture data from an interesting deployment area and sending them out to the end user. However, one can ask to what extent the end user can have confidence in the use of these data? Especially when these collected data are employed in a crucial application that definitely excludes wrong data use. Thereby, WSN mission success is basically dependent on trustworthy of the data delivery process to the end user. To reach this goal, some obstacles, related to malicious node behavior or failure nodes, must be avoided or tolerated. Therefore, we propose, in this paper, a scheme to improve the dependability of the data sensed by sensor nodes in one hand and the reliable communication of these data to the sink in other hand. The proposal is based on a fault tolerant sensing process and the resilience to malware threat on the transmitted data from nodes to sink. The proposal was integrated to the well know Leach protocol and the performance evaluation, carried out on NS2 simulator, showed convincing results in terms of energy conserving, received data rate and node failure occurrence and attack detections.

Introduction

Dependable data sensing is of paramount importance in WSNs. Indeed, what should be the consequences when wrong data are used, particularly in deployed critical applications? To make suitable decision from application outcomes, the end users have to rely on consistent information gathered by sensor nodes from the area of interest. Otherwise, not only the application outcomes should be erroneous, but they could lead to a disaster if they should be used to generate a final critical decision. Data should be correct since the time they are captured until the time they should be used by the WSN controller. To this end, data must be free from alterations purposely induced by an adversary or due to a sensor failed component or resulting from the unpredictable wireless environment.

Prospective wrong data received by an end user, after data aggregation process [START_REF] Ramar | A survey on data aggregation techniques in WSNs[END_REF], may have been corrupted from diverse ways such as: a malfunctioning of node sens-ing unit, any impairment during transmission or alteration of data integrity caused by malware or intruder at any node acting as router located along the routing path. This is for what is devoted the work reported in this paper; more precisely, coping with the tricky issue of node fault tolerance in case of unit sensing failure and security issue related to data integrity in case of network attack by intruders. The two problems have been treated separately in the specialized literature; they should be conjointly considered in order to reach end user confidence requirements in consuming collected data. We point out that node failures concern any flaws in correct data forwarding but more precisely incorrect data sensing generated by lack of energy or fault occurrence in sensing unit.

In the sequel, the paper is organized as follows: in section 2, we give a related work dealt with the data aggregation issue; section 3 presents our proposals for dependable data sensing and aggregation and performance evaluation of our proposals. We conclude the paper by a conclusion and future work.

Related Works

Several approaches have been proposed for reliably aggregating data in WSNs or securing them. These approaches coped only with routing problems like adversary attacks or node malfunctioning to forward data they have in charge. De Cristofaro et al. [START_REF] De Cristofaro | FAIR: Fuzzy-based Aggregation Providing Innetwork Resilience for Real-time Wireless Sensor Networks[END_REF] have proposed FAIR (Fuzzy-based Aggregation providing In-network Resilience for real-time Wireless Sensor Networks) an algorithm for robust data aggregation in real time. Witness nodes are used to confirm the outcomes of the aggregation process. The protocol seems to be robust but is only suitable for small WSNs and suffers from security lack and time overhead.

Wang et al. [START_REF] Wang | Energy-Efficient and Scalable Aggregation Secure Data a secure protocol[END_REF] have proposed EESSDA (Energy-Efficient and Scalable Aggregation Secure Data) a protocol using secure channel data encryption scheme. EESSDA uses several steps: creation of an aggregation tree rooted by the sink, creation of a secure channel between children and parents sharing a common key. Any node waits a certain time to receive data from its children, aggregates them with its own data and sends the new result to its parent. The protocol is costly and suffers from lack of security, because a compromised node near BS may jeopardize the aggregates confidentiality.

Shivakumar et al [START_REF] Shivakumar | An Efficient and Reliable Data Routing for In-Network Aggregation in Wireless Sensor Network[END_REF] proposed ERDRA (Efficient and Reliable Data Routing for In-Network Aggregation in Wireless Sensor Networks) a protocol building a routing tree with the shortest path connecting all nodes for reliable data aggregation. The tree is used by coordinators, elected among nodes having detected a new event, to collect data and sending them along a reliable new path. Weaknesses: Compromising a channel involves to intercept all messages, time overhead.

In [START_REF] Jose | PEPPDA: Power efficient privacy preserving data aggregation for wireless sensor networks[END_REF] Jose et al. have proposed a data aggregation protocol, ensuring confidentiality, authentication and freshness, suitable for the critical time applications. The message authentication is obtained via a key pair and a secret identification of each node. The protocol uses a tree aggregation including terminal nodes, parent nodes and sink. The protocol suffers from possible internal attacks, CPU overload and an unsafe key management mechanism.

Zhu et al. [START_REF] Zhu | An Efficient Confidentiality and Integrity Preserving Aggregation Protocol in Wireless Sensor Networks[END_REF] proposed ECIPAP (Efficient Confidentiality and Integrity Preserving Aggregation Protocol), an effective protocol ensuring confidentiality and aggregated data integrity. A node getting sensed data sends them to its parent with a Mac. Each parent node aggregates the received value with its own and sends the result to the upper level until reaching the sink. The latter decrypts the received message and broadcasts the aggregated data allowing each node to verify if its own data have been added. Protocol weaknesses: Possible internal attacks and time overhead.

Lathamanju et al. [START_REF] Lathamanju | CRSR Algorithm: A Secure Data Aggregation Algorithm in WSN[END_REF] proposed a secure data aggregation algorithm improving network life time and ensuring safety and security via Diffie-Hellman algorithm. Nodes are classified as friends or malicious. When a node wants to send data, it initiates a request message to route. Each intermediate node forwards the request if the sender is not malicious. When the destination node receives the route request, it sends an ACK response and its public key. The source node evaluates the best route with the largest number of friend nodes to send data. Protocol Weaknesses: Time overhead and resources waste.

BabuKaruppiah et al. [START_REF] Babukaruppiah | A Novel Approach to Detect the Shortest Path for Secure Data Aggregation Using Fuzzy Logic in WSNs[END_REF] have proposed NADSPSD (A Novel Approach to Detect the Shortest Path for Secure Data Aggregation using Fuzzy Logic in WSNs) an effective technique to detect the shortest path using fuzzy logic to secure the data aggregation. It is based on trust and residual energy of a node. The selection of the best route to send aggregated data is based on the combination of the path length, the available energy level and the node reputation. Protocol weakness: Cost and lack of security.

In [START_REF] Jia1 | A Recovery Algorithm based on Minimum Distance Redundant Nodes in Fault Management in WSNs[END_REF], Jia et al. have proposed MDRN (Minimum Distance Redundant Nodes) a fault recovery protocol which is deployed on the receiver node that has knowledge of node locations and failed ones. By choosing an appropriate number of redundant nodes, the algorithm will provide an accurate recovery. The proposal is feasible and effective to deal with the coverage hole issue caused by failed node. The protocol is unable to deal with multiple faults and requires a significant nodes redundancy.

Proposed Protocols

WSNs are typically deployed in harsh unattended environment. The inherent node vulnerabilities may lead to an unauthorized modification of sensed data. To overcome this problem, we present a solution offering safe data aggregation and sensing fault tolerance capability.

Description of the first Proposal

The different proposals work with the following hypothesis: -A WSN with N sensor nodes organized in clusters with a Cluster Head (CH) as manager and aggregator for each cluster. Each node i has a unique identifier Idi. The Base Station (BS) is assumed to be robust and reliable, with inexhaustible resources. -A compromised node may send corrupted data to the BS.

Notations: Emin : minimal energy amount, Round: period for changing aggregators.

Frame: temporal interval for data sensing, Vmax: maximal value, R: node communication range.

The first proposal named LEACH-FD (Low Energy Adaptive Clustering Hierarchy Fault Discovering) is a version improving the well-known LEACH Protocol [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Micro sensor Networks[END_REF] by including a filtering to eliminate incorrect data before their aggregation.

Proposed Protocol Steps:

The algorithm takes place in rounds having approximately the same interval of time determined in advance. Each round consists of an initialization phase and a transmission phase. The general proposed algorithm is the following:  Selecting of ClusterHeads (CHs) as done in LEACH protocol.  Request dissemination by CHs to all nodes  A node may join a CH by sending it a join request.  Formation of TDMA-schedule by CHs and Phase of data transmission to the CHs  Filtering received data and aggregation and sending them to the base station.

The different phases are described hereafter:

Initialization phase: This leads to the clusters formation by electing a Cluster-Head (CH) for each cluster and establishing nodes channel access strategy within each cluster. This phase begins by local decision making to become cluster-head. Each node Ni chooses a random number rn, if rn ≤ t, the node Ni becomes cluster-Head as in [START_REF] Jia1 | A Recovery Algorithm based on Minimum Distance Redundant Nodes in Fault Management in WSNs[END_REF]. When elected, a CH must inform its neighboring nodes of its new rank. The cluster member nodes managed by a CH are those nodes having joined CH according to the signal strength of the rank notification message sent out by CH. Each member node has to inform a CH of its decision to be membership. After that, the communications within a cluster can be made according to the TDMA communication protocol. For this, each CH establishes a TDMA schedule for its members.

Transmission phase: Data transmission operation is repeated at each frame, where nodes send data to their respective CH once a frame during their own allocated slots. Outside their slots, nodes get into sleeping mode for conserving their energy [START_REF] Aliouat | Improved WSN Capabilities through Efficient Duty-Cycle Mechanism[END_REF].

Aggregation step:

We added an important preliminary step to the aggregation operation, in which, after receiving data sensed by all nodes, each aggregator has to locally perform a filtering of received data to eliminate potential erroneous sensed data before the final aggregation process. A suitable detection algorithm of outliers should detect most of the errors and the number of false positive must be as small as possible. It uses the median, which is classified statistically among the robust features for detecting outliers [START_REF] Titouna | FDS: Fault Detection Scheme for Wireless Sensor Networks[END_REF].

Simulation Results: For the sake of limited space, the details of simulation are given only for the third proposal. Therefore, the conducted simulations showed that the proposal works only if each cluster includes more than two sensors nodes in order to be able to compare the values sent out from a cluster. Ignoring the incorrect values is not enough, but we must determine the causes in order to avoid using them in the future. When a node Ni sends an abnormal value compared to other nodes Nj, j≠i, this does not necessarily imply that Ni is failed. We can find a case where an event is triggered at a node level but other nodes have not yet discovered it. Therefore, we must add a method to ensure that the value sent is correct without waiting for the next frame since in the critical systems, delays in event discovery are crucial.

Description of the second proposal

We present a new protocol FDP (Fault Discovering Protocol), that uses neither the centralized approach nor the only distributed one but it combines the two. That is, the aggregators selection is done by the BS to ensure a global view of the network and a good energy management, but each node chooses its aggregator alone to reduce the load on the BS. This proposal is trust based where nodes history is used to decide if a node is faulty or not. The BS maintains a table of confidence in which each node has a certain degree of confidence. This value may change if sensed data by a node are not correct. It always uses sensed data filtering at the aggregators' level, but it adds a procedure to determine if a sensor is really faulty.

Proposed Algorithm: This algorithm is also carried out in rounds. Each round consists of an initialization phase, transmission phase and verification phase see Fig. 1.

Initialization Phase: This phase is composed of 3 sub-phases: aggregators selection, clusters formation and scheduling. At the beginning of each round, each node checks its residual energy if it is greater than a threshold value Emin, then it sends to BS a message containing its location X, Y and its energy level E.  Aggregators Selection: In this phase, BS will retrieve all data sent by nodes and then will choose nodes with maximum value of confidence as aggregators. If there are two nodes with same value, the node with maximum energy will be chosen. Also, in case of equality, the node with the smallest index is selected. After that, BS will broadcast a message including the CH identities and their coordinates.  Clusters formation: Upon reception of the information message sent by the BS, if the receiver node is a CH, it will do nothing, otherwise (standard node) it chooses from the list of the aggregator nodes the node closest to it as its leader. The node must inform its leader by sending it a JOIN message (belonging) containing the identity of the member node.

An Aggregator receiving JOIN message adds the sender to a list containing all member nodes. After that, any aggregator builds a TDMA-schedule and sends it to its members. Each one will know as well, its position in this TDMA-schedule and the data transmission time slot to its aggregator. The TDMA-schedule allows avoiding collisions between nodes which minimizes nodes energy consumption. This energy savings is also enhanced by node going to sleep out of its own time slot.

Transmission Phase: This phase also is decomposed in frames whose size is larger than that of the frame of the first proposal, because each frame contains 3 sub-phases: transmission, data filtering and accepted data aggregation (Fig. 2).

 Data Transmission: It is decomposed into several time slots, a slot in a frame is dedicated to a single node during which it transmits its data to the aggregator. Each node sends a message containing the sensed value and its residual energy.  Aggregation Phase: When the aggregator receives data from a node Ni, it checks if the energy of Ni is less than Emin, if so, it will ignore the received value otherwise it will store it in a list. At the end of each frame, the aggregator will count the number of values in its list, if this number is greater than 3 then it will filter the data using the procedure used in the first proposal but this time when it finds an abnormal value it will send an alert message to the BS containing the node identity that has captured the incorrect value.

Verification Phase: It contains two sub-phases: data verification, data confirmation.

 Data Verification: This sub phase is carried out when the BS receives an alert message containing the ID of a node; it will send a request for that node to re-capture data in its proximity according to radius R.

 Confirmation phase: When a node receives a confirmation message, it will sense again and return the value captured for the second time. When the BS receives a confirmation message, it will compare the data received and if there is a difference between the data of the nodes, so the node is considered faulty. BS will decrement trust value of a node having sent incorrect values, if this value reaches 3 then that node is declared faulty. These operations are repeated until the round end.

The initialization phase is repeated at each round up to the simulation end caused either by the exhaustion of the simulation time set to 3600 s or by the condition " the number of remaining nodes in WSN is less than the number of aggregators" but the confirmation phase is made only in case of a problem.

Simulation Results:

The simulation results show that we cannot surely conclude if the sensor node that sent incorrect values is failed or compromised. Also the FDP protocol does not cover the case of failed aggregator.

Description of the Third Proposal.

This proposal FDAP (Fault Discovering and Attack Protocol) is to enhance the second proposal to which is added an encryption mechanism for node authentication.

Proposed Algorithm: Each round consists of an initialization phase (Fig. 4), a transmission phase (Fig. 5) and a confirmation phase (Fig. 6); this is before the phase of key management (Fig. 3). The main phases of the third proposal are as follows: Key management and authentication nodes: Key management is carried out a time the deployment is achieved and before nodes are operating as sensors. So, BS assigns to each node Ni a unique identifier IDi and a symmetrical key that BS shares with the node Ni and a large integer value M is also preset, where key > M. the other phases remain the same until the confirmation phase of detecting erroneous data. The verification phase remains the same except that it is added a technique of cryptography to ensure the nodes authentication: ˗ Detection of compromised node: When BS receives an alert message containing the ID of a node; it will send it a message containing a random value S asking it to encrypt the value using its private key. The BS will also send to the neighbors of this node a confirmation message in the same way as in the previous proposal. A node Nj which receives a confirmation message of its identity, uses the following expression to encrypt the received value: C = ENC (value received) = value received + key(Nj) MOD M. then it sends a confirmation message containing the value C. When the base station receives this message, it will decrypt it using this expression: d=Dec(C) = C key(Nj) MOD M. Finally BS compares D and S if they are equal then the authentication is ensured otherwise the node Nj has been compromised.

˗

Detection of faulty aggregator: The base station can receive final erroneous aggregate values due to a faulty aggregator, so we add a procedure to cover this case. The BS will check the values received from the aggregators if it finds a value superior to Vmax, it will trigger the verification procedure. But now, it does not send to the nodes in the vicinity of the aggregator but to all members of its cluster. BS will then compare the new received values with those of the aggregator, if there is a large difference, BS will decrement confidence value of the aggregator. BS will then play the role of the aggregator during the remaining time of the current round.

Proposal Performance Evaluation

The performance evaluation of our final proposal is carried out through the well known simulator NS2 according to the network parameters summarized in the table 1 hereafter. The metrics of performance evaluation used are detected anomalies, life time duration, energy consumed and the data amount received by the base station. The three algorithms are used to simulate the same scenario designed to sense the temperature in a forest and monitor fires (The scenario contains a failed node, an intruder and a fire). Table 2 shows the anomalies recorded by sensor nodes according to the three proposals. As a result, the first proposal detects no anomalies while the 2nd proposal detects only failures and fires but the 3rd proposal detects all the assumed anomalies (failures, fires and attacks). Comparison between different proposal versions: Fig. 7 showed the energy consumed as a function of simulation time in different proposals. We note a great improvement obtained by FDP and FDAP regarding to Leach-FD version. Therefore, the strategy of aggregator's selection we proposed gives lower energy consumption which is vital for WSNs to last longer until achieving their missions. Also, we note that the use of cryptography in the third protocol does not consume a lot of energy. Fig. 8 shows the network life time duration ensured par different proposals. It represents the number of survival nodes during the entire simulation. From the curves, we note that FDP and FDAP allow ensuring a survival of all nodes until point of time 320 and 350, and maintain a functionality of all nodes during this period and prolong the life time of the WSN, while the life time duration of nodes in improved leach-FD is limited to time 200 only. We justify this difference by the new technique of selecting the aggregators used by FDP and FDAP.

Conclusion

Since the decision taken by the end user of a WSN greatly depends on the data sensed by nodes from an area of interest, these data which have undergone an aggregation process, must be as dependable as possible to ensure the success of the network mission. That is why our protocol is designed to transmit only reliable data from healthy nodes avoiding so those that are faulty or compromised by intruders. The results of simulation carried out via the well known Network Simulator NS2 shown that our third proposal is able to detect all the considered anomalies like failure node or node attack. The convincing results have been obtained in an efficient way in terms of energy consumption and network life time duration. To be complete, we intend to include in our protocol the robustness of the sink to cope with both fault occurrences and attacks.

Fig. 2 :

 2 Fig. 2: Transmission Phase.

Fig. 1 .

 1 Fig. 1. 2nd Proposal Phases.

Fig. 3 .

 3 Fig. 3. Phases of the 3rd proposition.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Initialization phase flowchart.

Fig. 6 .

 6 Fig. 6. Verification phase Flowchart

Fig. 7 .Fig. 8 .

 78 Fig. 7. Energy consumed by nodes.Fig. 8. Alive nodes number function of time.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Data amount received by BS.Fig. 10. Energy consumed in FDAP.Proposals behavior in presence of faults:The results obtained after variation of the number of failed nodes are illustrated by the figures 10-12 with 2%, 5% and 10%.of failed nodes. Fig.10represents the energy consumption as a function of simulation time in FDAP in the three cases: 2%, 5% and 10% of faulty nodes. The curves show a difference in energy consumption between the three cases. When a node fails, the number of messages, during the verification phase, increases leading to the increase of energy dissipation. Fig.11represents the life time duration of WSN in FDAP. We note a reduction in the WSN life time each time the number of failed nodes has increased. Fig.12represents the data received by BS in FDAP in the three different cases. The results showed that the number of failed nodes impacts negatively the performance of the protocol where we note a big difference in the amount of data received by BS because of the elimination of incorrect values.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Nodes Life time duration in FDAP . Fig. 12. Data amount received by BS in FDAP.

Table 1 .

 1 Parameters used in the simulation process

	Parameters	Values	Parameters	Values
	Size of the network	1000 m * 1000 m	Round Time Duration	30 s
	Base station position	50, 175	Initial Energy Amount	2 joules

Table 2 .

 2 Anomalies detected during simulation operation

	Proposals	Failure	Attack	Fire
	1 st Proposal	No	No	No
	2 nd Proposal	Yes	No	Yes
	3 rd Proposal	Yes	Yes	Yes


Khedidja Medani
email: khadidja_medani@univ-setif.dzmaliouat@univ-setif.dzzaliouat@univ-setif.dz

Makhlouf Aliouat

Zibouda Aliouat

Impact of Clustering Stability on the Improvement of Time Synchronization in VANETs

Keywords: Intelligent transportation systems, VANETs, Clustering, Time synchronization performance

Vehicular Ad Hoc NETworks (VANETs) has been developed to be, as a part of the Internet of Vehicles (IoVs), one of the most promoting technologies in the near future. Extensive researches are focusing on developing appropriate solutions in order to provide better Quality of Services (QoS) to these latter. This paper deals with network performance improvement based on clustering mechanism to reduce the number of communications caused by the high frequency of arrival/departure of vehicles while maintaining relevant clock synchronization solutions adequately operating. Thus, we attempt to adopt certain known clustering algorithms to our previous solution of time synchronization in VANETs namely OTRB (Osets Table Robust Broadcasting) in order to evaluate the impact of a hierarchical communication on time synchronization process. An analytical study with a comparison on the inuence of the clustering mechanism is given. The comparison takes place using simulation software NS2 (Network Simulator 2) and VanetMobiSim (VANET Mobility Simulator). The performance parameters include the average of arrival/departure of nodes and the number of isolated nodes. Simulation results reveal that an appropriate method should reduce the overhead of re-clustering and lead to an ecient network coverage with the best time synchronization rate.

Introduction

The emergent Vehicular ad hoc networks (VANETs) tend to improve road safety and users infotainment during displacement. To this end, nodes in VANETs, as moving vehicles, exchange their information using wireless ad hoc communications. Due to the nature of the medium access, vehicles communicate directly with one another or with the available infrastructure using single hop communication. To reach a further destination, multi-hop communications can be established using relay nodes. However, the constraints created by the intrinsic characteristic of VANETs, such as the high density of nodes, make data routing a challenging task. To handle such a limitation, data should be spread among an optimized route to ensure reliable delivery with an optimized communication overhead. This can take place by splitting the network into small groups, clusters. For each cluster, a node is elected as a coordinator to communicate data with its members on the one hand and to spread the information to other clusters on the other hand. In addition, several issues depend on a strong assumption of reliable clustering mechanism.

The standard IEEE 802.11 p has been proposed to deal with VANETs safety application. However, due to the high density of nodes, the standard suers predictability, fairness, low throughput and high collision rate [START_REF] Yin | Performance evaluation of safety applications over dsrc vehicular ad hoc networks[END_REF]. In addition, the high rate of transmitted data, such as safety packet dissemination, make network prone to face high congestion. So, collisions, especially when large transmission scope is used, lead to packet loss rate increases. To deal with these drawbacks and to improve reliability, many researchers suggest network partitioning into small clusters in order to allow better shared medium access control. Where clustering is used to limit the channel contention and provide fair channel access. Furthermore, clustering algorithms allow power control and packet delivery enhancement.

Time synchronization in VANETs is crucial. Several proposed algorithms, whatever derived from MANETs or not, rely on some sort of logical clustering view [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF]. The aim is to provide local time synchronization among the neighboring nodes in order to reach global time synchronization. For instance, in HCS [START_REF] Sam | A vehicle control system using a time synchronized hybrid vanet to reduce road accidents caused by human error[END_REF] and OTRB [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF] protocols, nodes synchronize their clocks by the aid of a randomly selected node, which is considered as a reliable source of time. The time synchronization solution performances are related to the selected node. This elected node can be seen as the coordinator of its neighbors. Such protocols rely on the assumption that the algorithm provides reliable clustering with a minimized number of in / out moving vehicles.

In order to enhance its performances, the present paper carries a study case on the inuence of clustering algorithms in time synchronization using OTRB protocol. OTRB algorithm requires the organized clusters to be stable for a period of time enough to achieve the time synchronization. The stability parameters, which refer to the average lifetime of the cluster, is related to the synchronization round period in OTRB. In turn, this latter is related to the synchronized group scale and the desired time precision [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF]. Dierent clustering algorithms in the literature take only into account the distance between nodes and their directions as parameters to form the clusters. However, vehicles displacement is related to the road infrastructure. Even vehicles move roughly with same velocities starting from a nearby zone, they can be found in further ways after a while. Therefore, other parameters, like the velocity of nodes, should be considered in order to deal with the high rate of arrival/departure of nodes.

The main contribution of this paper is to explore the impact of clustering on time synchronization process. To this end, we adopt an appropriate clustering algorithm to our previous solution OTRB. The best clustering algorithm should improve the synchronization rate and enhance the communication overhead.

The rest of the paper is organized as follow: section II introduces the main clustering algorithm concepts and their requirement in VNAETs, while section III gives an overview of the proposed solution of clustering issue. Section IV is dedicated to the OTRB protocol. In section V, a comparison of the implemented clustering protocols under OTRB context is discussed in order to evaluate its performance. Finally, section VI concludes the paper.

Basic clustering notions and requirements

The clustering is dened by the grouping of similar object items into clusters. In [START_REF] Graepel | Statistical physics of clustering algorithms[END_REF], a mathematical denition is given as follows: let X ∈ R mn a set of items representing a set of m objects x i in R n . The goal of the clustering algorithm is to divide X into K groups C k . Each one is called a cluster. Where all objects that belong to the same cluster are more alike than objects in dierent clusters. The result of the algorithm is an injective mapping X → C of object items X i to clusters C k .

The clustering can be exclusive, overlapping or fuzzy. In case of exclusive clustering, one object (node) can be found in one and just one cluster. When, in overlapping clustering, the node can belong to more than one cluster (>=1). Whereas, in fuzzy clustering, for each node is assigned a membership weight. Therefore, the node belongs to the cluster according to its associated weight. Fuzzy algorithms can be used to improve exclusive clustering by avoiding the arbitrary node assignment. In the case, the node will be assigned to the cluster within its membership weight is highest.

In VANETs, clustering is the act of grouping the vehicles into multiple clusters (groups of vehicles). In which, vehicles belonging to the same cluster have the same properties, such as velocity, position and direction.

Under each cluster structure, there is one node acting as a coordinator of the group. It is the cluster-head node (CH). The remaining nodes are classied to cluster-member (CM) and/or cluster-gateway (GW) nodes. In term of communication, a cluster-gateway node is able to communicate with all the clusters in which it belongs. Consequently, this latter represents the relay node of its clusters. In other words, it is the relationship between the neighboring clusters.

It is announced in [START_REF] Chakrabarti | Data mining: know it all[END_REF] that The clusters should reect some mechanism at work in the domain from which instances or data points are drawn, a mechanism that causes some instances to bear a stronger resemblance to one another than they do to the remaining instances. Regarding to vehicular environments, several parameters have been considered, such as node density, position, speed and direction. These parameters dene the requirement that should be employed by any clustering algorithm. From which, we dene the following that aects clustering eciency and network performance [START_REF] Rasmeet S Bali | Clustering in vehicular ad hoc networks: taxonomy, challenges and solutions[END_REF] [7] :

1. Cluster transmission overhead: The cluster transmission overhead refers as to the average number of packets exchanged to maintain the cluster structure.

The more the transmission overhead is less, the more the clustering algorithm is desired. 2. Cluster convergence: Cluster Convergence refers as to the time needed for all the nodes in order to join a cluster. The clustering algorithm that takes large convergence time is less suitable. 3. Cluster connect time: this parameter refers as to the rate of connection of the vehicle to one cluster. The highest connect time rate is given, the more suitable clustering algorithm. 4. Cluster stability: the cluster stability refers as to the average lifetime of the cluster. The best clustering algorithm goes after high stability.

Related work

For the purpose of supporting Quality of Service (QoS) in VANETs networking, stable clustering of the moving vehicles is required. The design of clustering algorithms enables organized medium access control and simplied data communication task. Several works in MANETs literature focus on improving the generated communication overhead by minimizing the number of clusters.

In [START_REF] Gerla | Multicluster, mobile, multimedia radio network[END_REF], Gerla et al propose to select the node having the highest number of neighbors as a CH in its vicinity. The proposed scheme minimizes the number of clusters. On the other hand, it deteriorates the network throughput due to the high rate of CMs within a cluster. This technique is not suitable for VANETs environment characterized by the high density of its nodes.

Other works, such as [START_REF] Richard | Adaptive clustering for mobile wireless networks[END_REF] selects the node with the lowest ID in its vicinity to be a CH of non-overlapping cluster. This protocol does not take nodes' mobility character into consideration. Then, CH selection process has to be frequently invoked especially in case of highly networks topology change, such as in VANETs. This will increase the cluster transmission overhead, which in turn reduces the network performances.

Su and Zhang [START_REF] Su | Clustering-based multichannel mac protocols for qos provisionings over vehicular ad hoc networks[END_REF] propose their algorithm which is a time and size based CH selection. The node that succeeds on sending its invite-to-join packet rst and has more neighboring nodes is selected to be a CH. As the vehicles move in and out of the cluster frequently, there is high frequent of arrival and departure of nodes. Thus, maintaining the cluster stability becomes a hard task. Whereas, the mobility of vehicle in VANET systems is a major challenge to ensure clustering stability. Many researches in the current literature attempt to deal such a limitation.

In [START_REF] Guenter | Medium access concept for vanets based on clustering[END_REF] the authors adopted the idea of [START_REF] Ra Santos | Inter vehicular data exchange between fast moving road trac using an ad-hoc cluster-based location routing algorithm and 802[END_REF]. In which, a node will announce itself as a CH in case it does not receive any Hello packet from its vicinity. Nevertheless, the node is allowed to be a CM in at least one cluster. The authors in the presented algorithm permit the merging of two adjacent clusters if their CHs come in direct communication range. The new CH is the one with the suitable weighed factor. This factor is calculated for each CH considering the mobility, connectivity and distance factors. However, CMs can be found out of the new elected CH, thus the possibility of frequent disconnection between the communicating nodes.

Kayis and Lichuan in [START_REF] Kayis | Clustering formation for inter-vehicle communication[END_REF] a speed-based classication in order to partition the vehicles into clusters. In which, seven groups of velocities are dened based on the min and the max speed boundaries. The "First Declaration Wins Rule" is adopted to select the set of the CHs. However, the nodes speed changes from node to node and can also change over the time. Therefore, nodes can frequently leave their group to join the more suitable. The algorithm may exhibit a frequent change in the network topology due to high cluster change rate. In addition, the CH can easily lose the connection with its member nodes.

A heuristic position-based clustering algorithm is proposed in [START_REF] Wang | A position-based clustering technique for ad hoc intervehicle communication[END_REF]. The cluster formation is obtained by the partition of the network based on the geographical position and the priority associated with each vehicle. Each node calculates its priority value using its node ID, the current time and the eligibility value. The eligibility value increases with the travel time of the node and decreases when the node speed deviates largely from the average speed. The node with the highest priority in all its one-hop neighbors and one of its two-hop neighbors is elected to be a CH. Also, in the proposed technique, in order to optimize the cluster size, a maximum distance between the CH and its members is predened. However, simulation results show that the formation of small cluster size increases the cluster reconguration rate. On the other hand, large communication range decreases the cluster transmission eciency.

Wu et al [START_REF] Wu | A cluster-head selection and update algorithm for ad hoc networks[END_REF] have proposed the Type-based Cluster-forming Algorithm (TCA) in order to reduce the update frequency of CHs in emergency ad hoc networks. Each node is assigned a stability factor, S, which is updated frequently. The node having a lower value of S has low mobility and reliable connectivity. The node with the lower stability factor is more likely to be elected as a CH. However, because of the assumption that the nodes have slow speeds, this algorithm generates more communication overhead for the cluster updating. This makes the algorithm not suitable to be implemented in VANETs environment.

A distributed CH selection is proposed in [START_REF] Khalid | A fuzzylogic-based cluster head selection algorithm in vanets[END_REF] to dynamically organize the network into clusters. The novel proposed algorithm is speed and distance based. The CH is selected according to its relative speed and the distance within its neighbors. Also, fuzzy logic inference system is used for predicting the future speed and position of all the CMs. As the maintenance phase is adaptable to the drivers' behavior, the proposed algorithm is highly stable. However, the distributed cluster overhead causes the number of messages received/transmitted to be decreased [START_REF] Rasmeet S Bali | Clustering in vehicular ad hoc networks: taxonomy, challenges and solutions[END_REF]. Also, the algorithm is implemented under medium vehicle density and low-speed conditions.

Rawashdeh and Mahmud [START_REF] Zaydoun | A novel algorithm to form stable clusters in vehicular ad hoc networks on highways[END_REF] attempts to deal with the clustering issue with stability on highway VANET environments. The authors apart from the assumption that the existence of VANETs nodes in the same geographic proximity does not mean that they exhibit the same mobility pattern", and try to improve the stability by making the network topology less dynamic. In addition to the velocity and the position, the proposed approach takes the location and the velocity dierence between the nodes into consideration. Each node runs the algorithm in fully distributed manner. First, a separation of the vehicles into highly mobile and low mobile groups is made. The network partition should provide a minimized number of clusters and ensure that all the CMs are stable with respect to one another. Then, the set of nodes with the highest suitable value are elected as CH nodes. Each node calculates its suitable value, which is calculated based to the velocity and the distance with regard to its stable neighbors. The closer velocity to the average velocities of its stable neighbors the node has, the highest suitable value is given. Simulation results show that the proposed algorithm improves the average cluster lifetime, which increases the stability of network topology.

In [START_REF] Dror | Fast randomized algorithm for 2-hops clustering in vehicular ad-hoc networks[END_REF] a new clustering algorithm in vehicular ad hoc networks is presented. The proposed scheme, called Hierarchical Clustering Algorithm (HCA), provides network two-hop clustering in fully distributed randomized fashion. Three roles can be dened to form the network hierarchy, in which a node can be a cluster head (CH), cluster relay (CR) or slave node. The CR nodes relay the transmitted data between the CHs and the slaves. The algorithm forms the clusters running four steps; cluster Relays Selection, ClusterHead Selection, Cluster Formation and Scheduling and Cluster Maintenance. Where it debates fast clusters construction in the rst third steps and leave the mobility handling to the maintenance phase. However, the algorithm improves the clustering stability at the price of transmission eciency and the average of clustering overhead. Also, the high rate of inter-cluster interferences causes frequent cluster changes and message loss due to message collisions. Another clustering algorithm for VANETs is proposed by Hassan abadi et al. in [START_REF] Hassanabadi | Clustering in vehicular ad hoc networks using anity propagation[END_REF]. The authors have presented the Anity PROpagation for VEhiclar networks (APROVE) protocol which attempts to produce high stability clustering taking into account the mobility parameter of nodes. In the proposed protocol, the CH selection is based on nodes' interdistance. The closest node to its neighbors is selected. This scheme suers long cluster convergence time in order to make all the nodes belong to a cluster.

In [START_REF] Kwon | Neighbor stability-based vanet clustering for urban vehicular environments[END_REF], the authors rely on neighbor vehicles' mobility to maintain VANETs stable clustering in rounds. In which, the node with the lowest neighbor vehicles mobility is elected to be the CH in its vicinity. Each node is assumed to have a unique identity, ID and maintain a neighbor vehicles table, which includes, for each neighbor, its ID and the neighbor vehicles mobility value. The neighbor vehicle table will be updated at each round and the neighbor vehicle mobility is calculated considering the number of vehicles entering/leaving the service convergence of the node.

In [START_REF] Ren | A mobility-based scheme for dynamic clustering in vehicular ad-hoc networks (vanets)[END_REF] a new oriented VANETs clustering scheme for urban city scenario is presented. In order to improve clustering stability, the proposed scheme considers the vehicles direction, position and the link lifetime estimation. Each node is able to estimate its speed and distance relative to its one-hop neighbors. The nearest vehicle into the central geographical position is likely chosen as a CH. The algorithm denes a safe distance threshold, D which D is less than the transmission range. The vehicles within this value are considered having more stable links with the CH. Therefore, the CMs are selected by the CH from its one-hop neighbors, in which the cluster size is dened by L ≤ 2D.

An analytical study that evaluates the impact of the clustering mechanism on the QoS of VANET systems implementation must be carried out. By way of illustration, we analyze the inuence of the clustering protocol performed while maintaining proper clock synchronization using OTRB protocol [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF]. The analytical study is carried out using network simulator (NS2) to compare the impact of the rate of arrival/departure nodes on the performance of OTRB protocol. To this end, the following sections demonstrate the behavior of OTRB protocol to maintain synchronized clocks in VANET systems. Then the simulation results are presented.

OTRB protocol overview

For the purpose of time synchronization in distributed VANET environments, the OTRB protocol is proposed in [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF] by Medani et al. The main idea is to set a number of nodes, named transporter nodes, to spread the time information over the entire network. For each transporter node, the time information broadcasted consists of the osets related to all its neighbors. However, the transporter node is supposed to be a reliable source of time.

The OTRB protocol performs time synchronization relying on pair-wise time synchronization mechanism [START_REF] Sundararaman | Clock synchronization for wireless sensor networks: a survey[END_REF]. Initially, each transporter node broadcasts a synchronization packet to its neighbors. Upon receiving this synchronization packet, neighboring nodes respond by their time values as shown in Figure 1. Then, the transporter node calculates the clock oset relative to each neighbor i and broadcasts the estimated values, as a time table, allowing all of them to synchronize to one another.

The transporter node selection phase has an important impact on OTRB performance in terms of time synchronization rate and communication overhead. Thus, the transporter node should have a higher stability relative to its neighbors. That is, a node leaving its synchronized group before the synchronization will be achieved, generates more synchronization requests. In this case, time synchronization maintenance requires more communication overhead. The more the overhead is generated, the more the communication collisions. In turn, a high rate of collisions decreases the time synchronization rate. On the other hand, the transporter node selection phase should be as fast as possible in order to deal with the time synchronization requirements, delay latency for example.

It is stated in [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF] that each transporter node with its synchronized group can be seen as a cluster. Where the transporter node represents the CH and its neighbors represent the CMs (see gure 2). Each node can join more than one transporter node. In the rest of this paper, we refer to the transporter node as the CH, and to the synchronized group as the CMs.

To show the inuence of the clustering algorithm on OTRB performance, in the next sections, we present the simulation and the comparison of three

Round period

Fig. 1: OTRB protocol process [START_REF] Medani | Fault tolerant time synchronization using osets table robust broadcasting protocol for vehicular ad hoc networks[END_REF].

clustering algorithms (CBLR [START_REF] Ra Santos | Inter vehicular data exchange between fast moving road trac using an ad-hoc cluster-based location routing algorithm and 802[END_REF], LID [START_REF] Richard | Adaptive clustering for mobile wireless networks[END_REF] and NMCS [START_REF] Kwon | Neighbor stability-based vanet clustering for urban vehicular environments[END_REF]) working under OTRB protocol.

Simulation results

The proposed time synchronization OTRB protocol relies on a strong assumption of stable clustering mechanism. To evaluate its performance and show its better quality of functioning, we adopt three clustering protocols CBLR [START_REF] Ra Santos | Inter vehicular data exchange between fast moving road trac using an ad-hoc cluster-based location routing algorithm and 802[END_REF], LID [START_REF] Richard | Adaptive clustering for mobile wireless networks[END_REF] and NMCS [START_REF] Kwon | Neighbor stability-based vanet clustering for urban vehicular environments[END_REF]to work under the referred OTRB and the behavior of the protocol is observed for each one. The time synchronization rate and the average communication overhead needed to accomplish the synchronization process are measured with regard to the essential clustering stability parameters.

In order to meet OTRB requirements, the implementation of these protocols is adapted to maintain overlapping clustering; where a node is permitted to be a CM in more than one cluster.

1. CBLR: CBLR is originally adopted on OTRB protocol upon its creation.

A set of CHs are selected randomly, in which, a node will announce itself as a CH if this latter does not receive any synchronization packet from its vicinity. When receiving several synchronization packets, a node is allowed to be CMs in more than one cluster. 2. LID: LID protocol selects nodes with the lowest ID in their vicinity as CHs of non-overlapping clusters. As OTRB protocol requires overlapping clusters, LID is thus modied to allow nodes joining several clusters, if possible, in our contribution. 3. NMCS: In NMCS, the node having the lowest neighbor vehicles mobility is selected to be the CH in its vicinity. NMCS protocol allows overlapping clustering. For each node, a degree is dened as the sum of the number of nodes that have left/arrived the node's transmission range. The sum is then divided by the total number of neighbors to normalize the degree of node's mobility regarding its vicinity. The node having the lowest value for this metric is supposed to be located in a relatively stable environment, indicating that such node is a good candidate for the CH role.

The simulation of the three referred protocols holds under the parameters shown in Table 1. A scenario of 199 nodes with random positions is initially generated. The mobility model follows the Intelligent Driver Model with Lane Changing (IDM_LC) of VANET Mobility Simulator (VANETMobiSim), in which, vehicles regulate their velocity according to neighboring vehicle movements. This model also supports smart intersection and lane changing management. In order to evaluate OTRB performances, we observe the changes in the synchronization rate and the communication overhead for each clustering protocol implemented under OTRB. On the other hand, to shed the light on the inuence of the clustering protocol stability on OTRB performance, the average of arrival/departure and isolated nodes are captured in parallel.

As shown in Figure 3, NMCS protocol reduces the average of the nodes moving into new clusters during the synchronization process. That is, NMCS protocol favors nodes located in a stable environment relative to their vicinities to be CH nodes. In contrast, CBLR and LID protocols do not take into account nodes' mobility while performing the clustering operation. In addition, relying on the lowest ID and the random metrics to select the CH nodes in LID and CBLR respectively multiplies the risk of having so much number of CHs and a high number of isolated nodes (see Figure 4). Actually, the clustering stability metrics, arrival/departure, and isolated nodes aect the performance of OTRB protocol. Table 2 shows that the more stable is the clustering protocol, the more OTRB performances are improved.

Figure 5 exhibits that the synchronization rate of OTRB using NMCS outperforms OTRB using the two other protocols. This is due to the improvement in the average of arrival/departure nodes which reveals successful clock synchronization process in the overall of nodes. Therefore, the number of messages generated in order to accomplish the synchronization process is minimized. On the other hand, the more the number of isolated nodes, the more supplementary synchronization requests are generated. For that, using NMCS under OTRB protocol improves the communication overhead compared to CBLR and LID protocols under OTRB (see Figure 6).

Conclusion

Because time synchronization is an essential attribute of VANET networks, because VANETs are included in a larger area: the IoV which itself is part of the largest networks: the IoT, then the quality of service of the synchronization process must fulll the expected objective in accordance with network importance. The paper is dealing with the impact of the well know clustering nodes organization on time synchronization ORTB protocol in order to improve the latter capabilities. Several known clustering algorithms have been used by ORTB and the comparative analysis of simulation results reveals that better performance, in term of synchronization rate and average communication overhead, is oered by the high stability clustering algorithm. However, multi-metric algorithms can be used to further enhance the clustering stability and so the network performance. This can be the subject of future work.

Fig. 2 :

 2 Fig. 2: Network architecture in OTRB [2].

Fig. 3 :

 3 Fig. 3: Average of new arrival nodes per round.

Fig. 4 :

 4 Fig. 4: Number of isolated nodes per round.

Fig. 6 :

 6 Fig. 6: Communication overhead comparison.

Table 1 :

 1 Simulation parameters

	Topology (m * m) Nodes number Data transmission range (m) Time of simulation (s) Physical channel
	3400*4900	199	300	200	IEEE 802.11b

Table 2 :

 2 Comparison. Implemented protocol Arrival / departure nodes Isolated nodes Synchronization rate (s) Communication overhead

	CBLR under OTRB	High	Low	Medium	High
	LID under OTRB	Medium	Medium	Medium	High
	NMCS under OTRB Low	Medium	Improved	Improved