Mohamed Belaoued
email: m.belaoued@univ-skikda.dz

Smaine Mazouzi
email: s.mazouzi@univ-skikda.dz

A Real-Time PE-Malware Detection System Based on CHI-Square Test and PE-File Features

Keywords: Malware, Malware Analysis, Chi-square test (KHI²), PE-Optional Header

Constructing an efficient malware detection system requires taking into consideration two important aspects, which are the accuracy and the detection time. However, finding an appropriate balance between these two characteristics remains at this time a very challenging problem. In this paper, we present a real-time PE (Portable Executable) malware detection system, which is based on the analysis of the information stored in the PE-Optional Header fields (PEF). Our system used a combination of the Chi-square (KHI²) score and the Phi (φ) coefficient as feature selection method. We have evaluated our system using Rotation Forest classifier implemented in WEKA and we reached more than 97% of accuracy. Our system is able to categorize a file in 0.077 seconds, which makes it adequate for real-time detection of malware.

Introduction

Malware, abbreviation for "malicious software", is a term used to designate any computer program that is designed to accomplish unauthorized actions without the user"s consent. The number of new discovered malware has grown steadily over the past ten years. Therefore, it is crucial to have an efficient protection against this kind of malicious programs. The existing anti-malware techniques can be broadly classified in three classes, which are signature-based, behavioral-based and heuristic-based techniques [START_REF] Bazrafshan | A survey on heuristic malware detection techniques[END_REF]. Signature-based techniques are widely used by most of commercial antivirus software (AV). These techniques are very accurate for detecting known malware that exist in the signatures" database [START_REF] Bazrafshan | A survey on heuristic malware detection techniques[END_REF]. However, they are not able to deal with unknown malware or newly launched ones, often developed after discovering a zero-day exploit [START_REF] Ye | CIMDS: Adapting postprocessing techniques of associative classification for malware detection[END_REF]. Even if the recent AV have become more accurate, they are still very slow to take countermeasures when a new threat is discovered [START_REF] June | Anti-malware vendors slow to respond[END_REF][START_REF] Salehi | Using feature generation from API calls for malware detection[END_REF].

The behavioral analysis also known as dynamic analysis consists of monitoring the execution of the analyzed program in an isolated environment (i.e. Sandbox or virtual machine) [START_REF] Aycock | Computer viruses and malware[END_REF]. During the monitoring process, the actions that the program accomplishes (such as API calls, Systems calls, network traffic, etc.) are recorded and used to generate behavior features for categorizing the program (malware or benign). Such techniques are very accurate and they are able to detect unknown malware [START_REF] Aycock | Computer viruses and malware[END_REF]. However, their main drawback is that the monitoring process is run for a couple of minutes at most, therefore it can"t observe the entire capabilities of the program [START_REF] Salehi | Using feature generation from API calls for malware detection[END_REF]. Moreover, the time required for the monitoring process makes such techniques not suitable for real-time detection.

The heuristic-based analyses investigate different file features such as Opcode instructions, structural information (Such as header information), and API (Application Programming interface) calls [START_REF] Bazrafshan | A survey on heuristic malware detection techniques[END_REF], [START_REF] Aycock | Computer viruses and malware[END_REF]. These sets of information are used as features for the classification process, which is generally done using machine learning-based classifiers such as decision trees and Bayes Algorithm [START_REF] Bazrafshan | A survey on heuristic malware detection techniques[END_REF], [START_REF] Shabtai | Detection of malicious code by applying machine learning classifiers on static features : A state-ofthe-art survey[END_REF]. The Heuristic based Anti-malware systems are very accurate and are able to deal with unknown malware [START_REF] Bazrafshan | A survey on heuristic malware detection techniques[END_REF], [START_REF] Aycock | Computer viruses and malware[END_REF][START_REF] Shabtai | Detection of malicious code by applying machine learning classifiers on static features : A state-ofthe-art survey[END_REF]. They are also easy to implement compared to the behavioral ones. However, the existing systems suffer from the inconvenient of their high processing overhead, since most of them use a large number of features, which yields to intensive computations. Due to that, most of the existing heuristic techniques are inadequate for real-time detection, which is a very suitable characteristic especially in such sensitive systems.

In this paper, we introduce a real-time PE (Portable Executable, See section 2) malware detection system, which consists of three different components, which are the PE-parser, feature selection module and a decision module. The PE parser was developed using Python language, and it statically (i.e. without executing the analyzed program) extracts the information contained in the PE-Optional header fields (PEF, see Section 2). PE header information (including Optional header ones) are very quick to extract, which is convenient for our real-time purposes. For the same purposes, our analysis was restricted on the Optional header only. We believe that using other types of features such as File-header fields or other structural information will considerably increase the number of features, which will have a direct impact on the detection time. The feature selection module was also developed using Python, and it is based on the KHI² test, which is a statistical method used for hypothesis testing [START_REF] Fornasini | The Chi Square test. The Uncertainty in Physical Measurements:An Introduction to Data Analysis in the Physics Laboratory[END_REF]. The decision module is based on Rotation Forest classifier [START_REF] Rodríguez | Rotation forest: A New classifier ensemble method[END_REF] that is available in Waikato Environment for Knowledge Analysis (WEKA) [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. This paper is organized as fellows: Section 2 introduces the PE file format in order to facilitate the comprehension of the rest of the sections. Section 3 is devoted to most known related works, published in the literature. In section 4, we present our proposed system"s architecture. In section 5, we present our experimental results. Section 6 concludes our work and underlines its perspectives.

PE File Format

PE is an abbreviation for Portable Executable [START_REF] Pietrek | Peering Inside the PE: A Tour of the Win32 Portable Executable File Format[END_REF], and it represents the common file format for binary executables and DLLs under Windows operating systems. A PE file is structured in layers and it is mainly composed of a DOS Header, PE Header, Section Headers (Section table), and a number of sections, as shown in "figure 1".

Fig. 1. PE file format

 The DOS Header is used if the file is run from the DOS. So it can then check whether it is a valid executable or not.

 The PE header is an IMAGE_NT_HEADERS data structure, which contains three members: PE-Signature, File Header, and the Optional Header. This latter is the subject of our work and is composed of several fields [START_REF] Pietrek | Peering Inside the PE: A Tour of the Win32 Portable Executable File Format[END_REF] as illustrated in figure 2. The values of the latter fields will be used as discriminators for the benignmalware categorization process.

Fig. 2. Members of the PE-Optional Header

Related Work

In the last decade, security researchers have introduced new malware detection methods, in order to overcome the limitations of the standard signature-based ones. Schultz et al. [START_REF] Schultz | Data mining methods for detection of new malicious executables[END_REF] were the first authors to introduce a machine learning based malware detection system. The proposed system is based on the analysis of different information contained in the PE file such as strings and API calls. They used a classification method based on Naïve Bayes, and they achieved 97.11% of accuracy. The method presented in [START_REF] Wang | Using API sequence and bayes algorithm to detect suspicious behavior[END_REF] is based on API calls and Naïve Bayes classifier. The extracted APIs were used to construct models of suspicious behaviors, by grouping some APIs according to scenarios that a malware can accomplish, such as obtaining

PE Header

Signature File Header Optional Header the system"s directory, writing malicious data into files, and registry updates. They achieved an overall accuracy of 93.7%.

Ye et al. [START_REF] Ye | CIMDS: Adapting postprocessing techniques of associative classification for malware detection[END_REF] have introduced a malware detection system that is based on the analysis of the set of APIs called by PE programs. The authors proposed a feature selection method based on the KHI² test. They used an Object Oriented Association (OOA) mining based classification method. Their system achieved an overall accuracy of 67.5% and a detection time of 0.09s.

The system proposed by Salehi et al. [START_REF] Salehi | Using feature generation from API calls for malware detection[END_REF] is based on analyzing API calls and their arguments. They trained their system using different classifiers and they have obtained an overall accuracy of 98.1%. Extracting APIs arguments requires executing the program; therefore, this method has the inconvenient of dynamic approaches mentioned previously.

Proposed Method

Our proposed malware detection system categorizes a file in three different phases, which are the feature extraction, the feature selection, and the decision (classification).

Feature extraction

As mentioned previously, our system relies on the analysis of the PE Optional Header fields (PEFs) and in order to extract these features from the analyzed file we developed a module written in Python by using a third party Python module called pefile [13]. PEFs are generated by concatenating the field"s name and value (ex. Check-Sum0 designates that the feature CheckSum has a value equal to 0).

Feature selection

In order to reduce the number of obtained PEFs and keep only the most relevant ones, we developed a feature selection method, which is based on the chi-square (KHI²) test. The KHI² is a statistical method, which is used to determine whether there is a significant association between two qualitative variables. This association is expressed by the distance D between an observed frequency O and an expected one E (which represents the case of independence between the variables) and the greater is that distance stronger is the correlation between the variables. In our case, we will study that association between the variable "PEF" that has two modalities: "present" and "absent". This variable represents the presence or not of a specific PEF in a PE file. The second variable is "PE" that has also two modalities: "Malware" and "Benign" that corresponds to the two categories of PE files that we used. The first step to do when conducting a KHI² test, is to define the two hypotheses H 0 and H 1 that one will be accepted, and the other rejected. H 0 and H 1 represent respectively the case of independency and the case of dependency between the two variables. Note that accepting H 0 for a PEF means that it is not specific to any catego-ry of PE-files. Therefore, it will be considered as irrelevant and will be removed. In our case, H 0 and H 1 are defined as follows:  H 0 : The presence or absence of a PEF is independent of the PE file"s type (malware or benign).

 H 1 : The presence or absence of PEF is related to the PE file"s type (malware or benign).

For every PEF, we have a contingency table as shown in table 1.

Table 1. Contingency Table of a PEF.

N, M, and T are respectively the total number of malware PE, the total number of benign PE, and the total number of all PE files (T=N+M). N1 and N2 are respectively the number of malware PE that have a PEF and the number of malware PE that do not have the PEF, such as N = N1 +N2. M1 and M2 are respectively the number of benign PE that have a PEF and the number of benign PE that do not have the PEF, such as M = M1 + M2. The KHI² score (D²) is calculated using the formula (1):

   c r, c r, c r, E )² E (O D² (1)
Where O r,c is the observed frequency count at level r of row variable and level c of column variable. And E r,c is the expected frequency. E r,c is defined by equation (2) .

T

n n E c r c r,   (2)
Where n r , and n c represent respectively the sum on row r and the sum on column c. After calculating the KHI² values for the obtained PEFs, we have to determine which of two hypotheses are accepted or rejected for every PEF. To do that, we have to compare the obtained KHI² scores of every PEF to a threshold, which represents the theoretical KHI² value (χ²). That value is obtained by first calculating the degree of freedom (DF), and choosing a signification level α that represents the error probability when accepting or rejecting an hypothesis. Considering DF and α, the χ²value is obtained from the KHI² distribution table [START_REF] Koskska | Statistical tables and formulae[END_REF] . DF is calculated using the following equation:

) 1 ( ) 1 ( DF     C R
(3) Where R, and C are respectively the number of modalities of the first and the second variables. After rejecting all the PEFs that are not correlated (D² ≤ χ²), we will calculate the φ coefficient using the formula (4) for the remaining ones. The φ coefficient is a normalization of the KHI² score (D²), which is used to measure the strength of the dependency between the two variables [START_REF] Farrington | Relative improvement over chance (RIOC) and phi as measures of predictive efficiency and strength of association in 2x2 tables[END_REF]. In our work, that coefficient will be used

PEF: Present PEF: Absent Row Total PE: Malware N1 N2 N PE: Benign M1 M2 M Column total N1+M1 N2+M2 T
to generate the different PEFs" subsets, which are grouped according to their correlation"s strength (relevance).

T D²

  (4)
The value of φ ranges between 0 and 1, therefore, the strength of the relationship can be divided in 4 different classes:

 φ ≈ 0.25: Weak correlation.

 φ ≈ 0.50: Medium correlation.

 φ ≈ 0.75: Strong correlation.

 φ ≈ 1: Very strong correlation.

Our obtained PEFs will be divided into non-disjoints subsets according to the φ values mentioned previously.

Classification

In order to evaluate our malware detection system we have used Rotation Forest classifier [START_REF] Rodríguez | Rotation forest: A New classifier ensemble method[END_REF] that is implemented in WEKA [START_REF] Witten | Data Mining: Practical machine learning tools and techniques[END_REF]. Therefore, our classification module takes as an input the PEFs subsets represented as an .arff file. The .arff file is the data file format supported by WEKA, and it is automatically generated using a python script. The classifier is then trained and models are generated for each feature subset of the training set. The obtained models are then tested on previously unseen PE-files contained in our test set.

Experimentation

Dataset

We collected a dataset composed of 552 PE files (338 malware and 214 benign programs). This dataset will be split into 80% training set and 20% test set. The PE dataset was downloaded from Vxheavens.com and contains 12 different malware categories as shown in table 2. The benign PE files include some utility software downloaded from Softpedia.com and some Windows system files collected from a clean installation of windows XP. We scanned the whole dataset by more than 40 AV available on the website VirusTotal.com, in order to make sure that they are correctly labeled (malware, benign).

Results and evaluation

In this subsection, we will present the obtained experimental results from the feature extraction phase until the decision phase. We first start by the obtained PEFs after the feature extraction phase. As presented in Table 3, we have obtained 590 PEFs with their corresponding frequencies in malware and benign PE (observed frequencies).

Table 3. Overview of the obtained PEFs list and their corresponding frequencies.

We will calculate the KHI² and φ values (as presented in the subsection 4.2) for the obtained PEFs and remove the non-relevant ones that have KHI² < 3.84 (3.84 is the X² value for DF=1 and alpha =0.05). The obtained results are presented in table 4.

Table 4. KHI² scores and values of the selected PEFs

As presented in Table 4, we have obtained a final list of 50 PEFs with their corresponding KHI² scores and φ values. We will divide these features into different groups (subsets) according to their φ values. At the end of the feature selection phase, we have obtained three different subsets: G1, G2, and G3 that contain PEFs that have respectively φ ≥ 0.75, φ ≥ 0.5, and φ ≥ 0.25. We have respectively 11, 14, PEFs in G1, G2, and G3. We have used a forth subset G4 that contains the complete 590 extracted PEFs, the aim from that is to see whether our feature selection method have improved the obtained results or not.

Next, we will evaluate our system"s performance by training the Rotation Forest classifier using different features subsets and see which subset will generate the best results. The performance of a classifier is generally evaluated by calculating three different metrics which are Detection rate (DR), False Alarm rate (FA), and Accuracy (AC) and they are calculated using the equations 5, 6 and 7 respectively:

100% FN TP TP DR    (5)
Where TP (true positive) and FN (false negative) represent respectively malware that were correctly classified as malware and malware that were wrongly classified as benign.

100% TN FP

FP FA    (6)
TN (true negative) and FP (false positive) represent respectively benign programs that were correctly classified as benign, benign program that were wrongly classified as malware. The accuracy (AC) represents the rate of files that were correctly classified in their class.

100% FN FP TN TP TN TP AC       (7)
The fourth metric that we will use to evaluate our system"s performance is the detection time (DT), which represents the average time required for categorizing a file and it is expressed in seconds per file. DT includes the feature extraction time, .arff file generation time, and the classification time. The obtained results are presented in table 5.

Table 5. Experimental results

From the results presented in the above table, we can see that our proposed feature selection method was able to increase the accuracy of our system by +1.84% (from 95.41% with G4 to 97.25% with G2) and that using only 14 PEFs. It was also able to reduce the categorization time by 33% (from 0.116s with G4 to 0.077s with G2). Note that the feature extraction phase took 0.037s, the .arff file generation also required 0.037s, and the classification phase took 0.003s.

Group

Comparison

In this subsection, we will evaluate our system"s performance by comparing it with the previously cited methods. The results are presented in table 6.

Table 6. Results of the comparison with the previously cited methods for malware detection

From the results presented in Table 6, we can see that our system outperforms three of the four presented systems with an improvement in accuracy that varies from 0.14 % to 30%. The system proposed by Salehi et al. [START_REF] Salehi | Using feature generation from API calls for malware detection[END_REF] is more accurate than our system (+1.15%). However, our system has a better detection rate.

If we consider the detection time (categorization time), we can conclude that our system is adequate for real-time detection. The proposed system is able to categorize a file in 0.077s, which is a very satisfying performance, compared with the system proposed by Ye et al. [START_REF] Ye | CIMDS: Adapting postprocessing techniques of associative classification for malware detection[END_REF] which categorizes a file in 0.09s. The system proposed by Salehi et al. [START_REF] Salehi | Using feature generation from API calls for malware detection[END_REF] needs to monitor the analyzed program during 2 minutes in order to extract API calls and their arguments, that represents almost 3000 times the required time by our proposed features extraction method.

Conclusion and future works

In this paper, we have presented a real-time PE-malware detection system that is based on the analysis of the PE-optional Header information. The proposed system uses an efficient feature selection method, which is based on the KHI² test. This latter allowed us to achieve a high accuracy and a low detection time, using only 2% of the initially extracted features. As future works, we project to combine different types of features such as APIs calls, and Opcode, in order to increase the accuracy of our system.

Method

Table 2 .

 2 Used malware dataset

	N° Malware Type Counts N° Malware Type	Counts
	1	Backdoor	27	7	Trojan	59
	2	Email-Worm	19	8	Trojan-Downloader	24
	3	Exploit	28	9	Trojan-Dropper	32
	4	Hacktool	22	10 Trojan-Spy	18
	5	Net-Worm	16	11 Virus	42
	6	P2P-Worm	17	12 Worm	34
			TOTAL = 338

and 22 Frequency N° Optional Header field Value Malware (271) Benign(172) 1

	BaseOfCode	4096	271 (100%)	172 (100%)
	2 BaseOfData	102400	4 (1%)	1 (1%)
	…	…	…	…	…
	86 CheckSum	0	259 (96%)	5 (3%)
	87 CheckSum	102910	1 (1%)	0 (0%)
	… …		…	…	…
	589 Subsystem	2	226 (83%)	106 (62%)
	590 Subsystem	3	45 (17%)	66 (38%)
	N°		PEF	KHI²	φ
	1	CheckSum0		375.21 0.92
	2	MajorImageVersion0	370.57 0.91
	3	DllCharacteristics0	355.91 0.9
	4	MajorOperatingSystemVersion5 346.02 0.88
	5	MinorOperatingSystemVersion0 341.92 0.88
	… …		…	…
	50 SizeOfInitializedData28672	3.86	0.09


Moussa Benaissa
email: moussabenaissa@yahoo.fr

Abderrahmane Khiat
email: abderrahmane_khiat@yahoo.com

A New Approach for Combining the Similarity Values in Ontology Alignment

Keywords: Ontologies, Ontology Alignment, ontology matching, Semantic Correspondences, Similarity, Aggregation of the Similarities, Combination of the Similarities

Ontology Alignment is the process of identifying semantic correspondences between their entities. It is proposed to enable semantic interoperability between various knowledge sources that are distributed and heterogeneous. Most existing ontology alignment systems are based on the calculation of similarities and often proceed by their combination. The work presented in this paper consists of an approach denoted PBW (Precision Based Weighting) which estimates the weights to assign to matchers for aggregation. This approach proposes to measure the confidence accorded to a matcher by estimating its precision. The experimental study that we have carried out has been conducted on the Conference 1 track of the evaluation campaign OAEI 2 2012. We have compared our approach with two methods considered as the most performed in recent years, namely those based on the concepts harmony and local confidence trust respectively. The results show the good performance of our approach. Indeed, it is better in terms of precision, than existing methods with which it has been compared.

Introduction

The Semantic Web Community, defined as a futuristic extension of the current web, has adopted ontologies as the cornerstone for its achieving in order to overcome the crucial problem of semantic heterogeneity that is inherent to its distributed and open nature. However, these ontologies are themselves heterogeneous. This heterogeneity may occur at syntactic, terminological, conceptual or semiotic levels [START_REF] Euzénat | Ontology Matching[END_REF].

Ontology alignment, defined as the process of identification of semantic correspondences between entities of different ontologies to be aligned [START_REF] Euzénat | Ontology Matching[END_REF], is proposed as a solution to the problem of semantic heterogeneity by enabling the semantic interoperability between various sources of information.

We globally distinguish two approaches to identify the alignment between ontologies: reasoning-based approaches and those based on the calculation of similarities [START_REF] Silvana | Ontology and Instance Matching[END_REF].

Most of the existing ontology alignment systems are based on the calculation of similarities between entities to align. In this category, we distinguish two types of systems: [START_REF] Bellahsene | Tuning for Schema Matching Schema Matching and Mapping[END_REF] systems which implement one single technique and (2) systems which combine several techniques, in order to estimate the similarity between two entities. The latter systems have become more frequent due to their flexibility and their easy extension [START_REF] Li | RiMOM: A Dynamic Multistrategy Ontology Alignment Framework[END_REF]. Moreover, with the increasing complexity of ontologies on the Web (number and volume), the alignment cannot be performed reasonably in a purely manually way. Therefore it is imperative to develop automatic or at least semiautomatic systems to identify the alignment [START_REF] Rahm | Towards Large-Scale Schema and Ontology Matching. Schema Matching and Mapping[END_REF]. This situation is dictated by the lack of human expert especially in dynamic systems and by the concern to accelerate the alignment process [START_REF] Bellahsene | Tuning for Schema Matching Schema Matching and Mapping[END_REF].

Precisely, we propose in this paper an ontology alignment approach based on the calculation of similarities and which fits into the category of methods that combine several matchers. It is a statistical approach based on two heuristics to aggregate similarity values calculated by different matchers. The first estimates the candidate final alignment from the alignments identified by matchers, considering their intersection. The second provides an estimate of the weight to be assigned to the matchers with a view of their combination using a weighted summation strategy.

The rest of the paper is organized as follows. In the Section 2, we present some preliminary notions on ontology alignment in order to facilitate the reading of the paper content. The Section 3 contains the description of some related work to our approach. In the Section 4, we present an example in order to illustrate our approach. The Section 5 is dedicated to the presentation of the proposed approach. The Section 6 contains the experimental results obtained during the evaluation of our approach. Finally we give a conclusion and some future perspectives.

Preliminaries

In this section we present some preliminary notions of ontology alignment in order to facilitate the reading of the paper content. We outline the notions of ontology, similarity calculation techniques and alignment, respectively. We refer the reader, for more details, to the following references [START_REF] Euzénat | Ontology Matching[END_REF] [4].

Notion of Ontology

Definition: Ontology is a six tuple [START_REF] Cruz | Efficient selection of mappings and automatic qualitydriven combination of matching methods[END_REF]: O = <C, R, I, H C , H R , X> where:

-C: set of concepts.

-R: set of relations.

-I: set of instances of C and R.

-H C : denotes a partial order relation on C, called hierarchy or taxonomy of concepts. It associates to each concept its super or sub-concepts.

-H R : denotes a partial order relation on R, called hierarchy or taxonomy of relations. It associates to each relation its super or sub-relations.

-X: set of axioms.

Techniques of the Similarities Calculation

There are basically five types of methods to calculate similarities [START_REF] Bellahsene | Tuning for Schema Matching Schema Matching and Mapping[END_REF]:

1. Terminological Methods. These methods are based on string matching and can be applied to the names, labels and descriptions of the entities. We cite as an example of matcher of this category: the edit distance. 2. Linguistic Methods. These methods are based on external resources as dictionary and thesaurus in order to calculate the similarities between the names, labels and descriptions of the entities. We cite as an example of a matcher of this category: similarity based on WordNet (Wu-Palmer). 3. Structure-based Methods. These methods exploit the internal structure (domain, range, properties and cardinality, etc.) and the external structure (hierarchy and the relation-ship between other entities) of the entities in order to calculate their similarities. We cite as an example of a matcher of this category: Resnik similarity. 4. Semantic-based Methods. These methods are essentially deductive and inferential and are based on formal semantic of generic or specific domains. We cite as an example of a matcher of this category: SAT solvers. 5. Instance-based Methods. These methods exploit the instances associated to the concepts (extensions) to calculate the similarities between them. We cite as an example of a matcher of this category: Jaccard similarity.

Notion of Ontology Alignment

The alignment of two ontologies is the process of identification of semantic correspondences between their entities. In this section, we briefly introduce the basic necessary concepts on the alignment in order to facilitate the reading of the paper content.

Notion of Alignment

The alignment can be defined as a set of correspondences. The alignment process (Fig. 1) receives as input two ontologies O and O' and produces as output an alignment A between entities of O and O'. Other elements complete this definition, namely:

 An initial alignment A' to be completed or refined by the process.  The external resources r such as a thesaurus or a dictionary.  The parameters P such as thresholds or weights.

The alignment process consists generally of the following steps:

1. Analysis: This step consists of extracting both the entities (concepts, relations, instances) of the two ontologies O and O ' and their characteristics which will be used to identify the alignment. 2. Calculation of Similarities: this step consists to execute the different matchers in order to calculate the similarities between entities to align. 3. Similarity Values Aggregation: This step consists to combine the similarity values calculated by the matchers in the previous step, into one value. 4. Selection: This step consists of applying a strategy, for example a threshold strategy in order to filter the alignment defined in the previous step. Other optimization techniques can also be applied at this level to optimize the extraction of the final alignment.

5. Improvement of the Alignment: descriptive logic techniques can be applied at this level to improve the final alignment by diagnosing and repairing any inconsistencies identified in the final alignment.

Related Works

The aggregation of similarity values calculated by different matchers consists to combine them into one single value. There are basically three types of approaches to achieve this aggregation: the weighting, the vote and the argumentation [START_REF] Euzénat | Ontology Matching[END_REF]. In the vote strategy, the matchers are considered as independent sources of information and the decision to include a correspondence in the alignment is taken on the basis of a simple majority vote by the matchers for this correspondence. The argument strategy allows negotiating an alignment by exchanging arguments between agents. In the weighting strategy several techniques are proposed to combine the similarity values.

In [START_REF] Do | COMA -A system for flexible combination of schema matching approaches[END_REF], the authors quote the following strategies to combine similarity values calculated by different matchers: (1) Max: this strategy selects the maximum similarity value among the values calculated by different matchers); (2) Min: this strategy selects the minimum similarity value among the values calculated by different matchers); (3) Average (this strategy calculates the average value of the similarities calculated by different matchers); and (4) Weighting (this strategy calculates the weighted sum of the similarities calculated by different matchers). The latter, which is more frequent in ontology alignment systems [START_REF] Li | RiMOM: A Dynamic Multistrategy Ontology Alignment Framework[END_REF], requires an estimate of the weights that reflect the importance of each matcher. In some systems this weights approximation is done manually by a human expert. This approach is difficult to implement given the enormous number of possible configurations [START_REF] Rahm | Towards Large-Scale Schema and Ontology Matching. Schema Matching and Mapping[END_REF] and has the major drawback to run correctly on a specific alignment task and not on another. It is therefore suitable that the weights estimation be specific to the current alignment task [START_REF] Mao | A harmony based adaptive ontology mapping approach[END_REF].

Several studies have addressed the problem of the weights estimation of different matchers. In [START_REF] Wang | Strategies Prediction and Combination of Multi-strategy Ontology Mapping[END_REF], the authors propose an approach based on information theory and estimate the weight of each matcher based on the calculation of entropy (uncertainty of information) from the similarity values calculated by this matcher.

The works described in [START_REF] Martinez-Gil | Optimizing Ontology Alignments by Using Genetic Algorithms[END_REF] and [START_REF] Wang | GAOM: Genetic Algorithm based Ontology Matching[END_REF] present an approach based on genetic algorithms to give an estimate of weights assigned to different strategies used.

In [START_REF] Mao | A harmony based adaptive ontology mapping approach[END_REF] the authors propose the harmony concept for weighting the different matchers. The harmony h of a similarity matrix sim of n rows and m columns is defined by: « the number of pairs of entities (e i , e' j ) for which the similarity sim (e i , e' j ) is the maximum at the same time on the row i and column j, divided by the maximum number of concepts of ontologies to align O and O' ". This value h is assigned as weight to the matcher associated to the matrix sim. In [START_REF] Cruz | Efficient selection of mappings and automatic qualitydriven combination of matching methods[END_REF] the authors propose a local confidence measure for a pair of entities unlike that proposed in [START_REF] Mao | A harmony based adaptive ontology mapping approach[END_REF], which is global to the entire similarity values matrix. This measure, denoted m, is defined for an entity e of the ontology O, by: m = m rm nr where m r is the average of similarity values of enti-ties that are associated to e and m nr is the average of similarity values of entities that are not associated to e.

Other works such as [START_REF] Ichise | Machine learning approach for ontology mapping using multiple concept similarity measures[END_REF] and [START_REF] Ngo | Enhancing Ontology Matching by Using Machine Learning, Graph Matching and Information Retrieval Techniques[END_REF] use machine learning techniques for automatic configuration of weights to be assigned to the matchers. * The approach proposed in this paper is situated in the category of weighting techniques that combine the similarity values calculated by different matchers. It consists of a heuristic that estimates the weights to assign to the matchers. Contrary to the techniques mentioned above, this approach is of statistical nature and estimates the weights by an estimation of the precision standard metric.

Illustrative Example of the Approach

Let two ontologies O and O" which contain the concepts O: {Product, Provider, tor} and O': {Book, Translator, Publisher, Writer} respectively.

The application of the edit distance metric and that based on WordNet between concepts of O and O' has generated the following two matrices of similarities.

1) If we filter out the matrix of similarities (Table 1) calculated with the edit distance, with a threshold s = 0.15 we obtain the following alignment:

A1= {(Product, Translator), (Provider, Translator), (Provider, Publisher), (Provider, Writer), (Creator, Translator), (Creator, Writer)}. The alignment A which consists of the semantic correspondences identified by the two matchers simultaneously is as follows: A = A1  A2 = {(Creator, Translator), (Provider, Writer), (Creator, Writer)}. A represents the estimator of final candidate alignment.

The estimator of the precision of the matcher edit distance is: P 1 =3/6=0.50.

The estimator of the precision of the matcher based on WordNet is: P 2 =3/7=0.43.

The weights to be assigned to matchers are: w 1 = 0.50 and w 2 = 0.43.

The matrix of the combined similarities is as follows: If we filter out the matrix of combined similarities (Table 3), with a threshold s = 0.30 we obtain the following alignment, (Provider, Publisher), (Provider, Writer), (Creator, Translator), (Creator, Writer)}. For more details about the approach see section 5.

5

The Proposed Approach

The architecture of our approach denoted PBW (Precision Based Weighting) is illustrated in Fig. 2. We have in input two ontologies O 1 and O 2 to be aligned. The Analysis Module performs the entities extraction from O 1 and O 2 using API Jena. Then, the Similarities Generation Module calculates for each pair of concepts (C, C')  O 1 O 2 three similarity values using three techniques namely: the edit distance [START_REF] Euzénat | Ontology Matching[END_REF], the Jaro metric [START_REF] Euzénat | Ontology Matching[END_REF] and the similarity metric based on WordNet (Wu-Palmer algorithm) [START_REF] Euzénat | Ontology Matching[END_REF]. It should be noted at this level that the parameter object of the comparison is primarily the aggregation method of similarity values (the estimation of the weights to be assigned to matchers).

For that reason, we have set the same matchers for all three compared methods H, LCD (see the section 3 for the definition of these methods) and PBW in order to not have the results skewed by the choice of matchers. Therefore, the selection of the matchers has not been the subject of special attention. We have limited to the linguistic-based and string-based matchers. These similarity values are used by the Weights Estimation Module in order to calculate the confidence to be associated to the matchers mentioned above. The Similarities Combination Module generates then the combined similarity values using a weighting summation strategy. Finally, the Alignment Extraction Module selects the final alignment. This selection is simply performed by filtering the combined similarity values on a given threshold. The contribution of the paper lies in the combination of similarity values. We detail below the principle of the proposed approach.

The approach proposed in this paper is an aggregation approach of similarity values calculated by several matchers. It fits into the category of automatic techniques for assigning weights to matchers which estimates their importance. We give in this section its principle.

Let O and O" be two ontologies to be aligned and let M 1 ,…, M k k matchers which execute in parallel and calculate the similarity values between entities e 1 ,…, e n for O and e" 1 ,…, e" m for O" respectively. Let us note S 1 ,…, S k the similarities matrices generated by matchers M 1 ,…, M k respectively. The problem here is to assign to each matcher M i a weight w i which expresses its importance in a given alignment task.

The intuition behind this approach consists to assign to the matcher M i the weight w i which is equal to an estimation of the precision of M i . Indeed, as the precision metric is a good estimation of the matcher quality; we propose to use it as an estimator of the weight that will be assigned to the matcher.

We distinguish for the matcher M i two subsets among the set of semantic correspondences between entities of ontologies O and O" to be aligned. On one hand we have the set P i of the correspondences qualified positively and which belong to candidate alignment and On the other hand, we have the set N i of those, negatively qualified and which do not belong to candidate alignment. The set P i is defined as follows: P i = {(e i , e" j )  O x O" / (S i (i, j) ≥ s where s is a given threshold}.

Since to estimate the precision of a matcher, we need a reference alignment and in the absence of such alignment we propose to estimate it (the reference alignment) by the set P which denotes the set of positive correspondences identified simultaneously by all matchers. In other words: P = ∩ i=1,…, k P i . We therefore propose for the matcher M i the following estimator for the precision:

w i =|P i ∩P|/|P i |
Where |E| denotes the number of all elements of the set E. This estimator represents the weight to be assigned to M i .

The approach can be made operational by the following process:

-Calculate, for each matcher M i , the set P i defined above.

-Calculate the set P. In some alignment tasks, the case where P is empty can occur. The weights assigned to the matchers are therefore is null. To overcome this situation, we have estimated P, for each matcher M i , as follows: P = {(e i , e" j )  O x O" / (S i (i, j) ≥ s where s is a threshold relatively high}.

We have retained the following formula to specify the threshold: s = the highest similarity value calculated by the matcher M i from which a particular constant value n is subtracted. For example, if the maximum similarity value is equal to 0.80 and n=0.25 then s = 0.8*0.25=0.40.

-Assign to each matcher M i the weight w i .

-Calculate the matrix of combined similarity values M. the matrix M is calculated by the following formula: M (i, j) = (∑ k w k * S k (i, j)) / (∑ k w k ).

-Filter M according to the threshold s.

The Experimental Study

In order to evaluate our approach, we have used the conference track of OAEI 2012 evaluation campaign. This track consists of a collection of 16 ontologies describing the field of the conferences organization. It is constituted of 21 tests for which reference alignments are available, from a total of 120 possible tests resulting from the pairwise combination of 16 ontologies. Each test consists of two ontologies and a reference alignment.

The tests have been carried as follows: we have implemented the three methods (H, PBW and LCD), then we have executed these methods on ontologies tests of the conference track.

Fig. 3. The Global Results (All Tests of Conference Track) of the Three Methods

As evaluation criteria we have used the standard metrics that are precision, recall and F-measure to evaluate our approach. These metrics are defined as follows:

Where |R| denotes the number of the reference alignment mappings and |A| denotes the number of matches found by our approach.

We envision in this experimental analysis to compare our precision based weighting approach of the similarity values aggregation (Noted PBW-method in the graphs) with the two most efficient aggregation methods [START_REF] Ngo | Enhancing Ontology Matching by Using Machine Learning, Graph Matching and Information Retrieval Techniques[END_REF] [15] namely the method based on the harmony concept [START_REF] Mao | A harmony based adaptive ontology mapping approach[END_REF] (Noted H-method in the graphs) and the method based on the concept of local confidence [START_REF] Cruz | Efficient selection of mappings and automatic qualitydriven combination of matching methods[END_REF] (Noted LCD-method in the graphs).

It should be noted at this level that our approach as well as those with which it has been compared belong to the same category of methods based on the weighting.

We have adopted the following methodology in order to conceive the experimental protocol. For each of the 21 tests of the conference track, we have calculated three matrices of similarities by the matchers edit distance, Jaro and WordNet, respectively. Subsequently, from these matrices we calculated the weights to assign to the matchers by the three compared methods (harmony, local confidence and our method). Then we have calculated the matrices of the combined similarities and we have selected the alignments by filtering using a given threshold s for each of the three methods. Finally, for each test we have calculated precision, recall and F-measure for The results are shown in Fig. 3 and Fig. 4.

The experimental results obtained (Fig. 3) show that globally i.e. for all tests:

1. Our approach PBW is significantly more efficient than the H and LCD methods in terms of precision.

2. Our approach PBW is more efficient than the LCD method and slightly less efficient than the H method in terms of F-measure.

3. Our approach PBW is less efficient than the H and LCD methods in terms of recall.

The analysis of the detailed results on all tests of the conference track (Fig. 4) show that our approach is more efficient than H and LCD methods in terms of precision for all tests of the conference track of OAEI 2012 evaluation campaign, considered individually.

Conclusion and Perspectives

We have presented in this paper a dynamic approach to estimate automatically the weights to be assigned to different matchers in a given alignment task, in order to combine the similarity values calculated by the matchers in a context of ontology alignment.

The experimental results show the good performance of our proposed approach. Indeed, it is better in terms of precision than other methods, local and global, deemed among the most efficient ones in recent years. In addition, it shows a good F-measure relative compared to the local method.

As future perspective we envision to intensify the experiments by considering other tests and combining similarities calculation techniques.

4. 3 . 1 .

 31 Notion of Correspondence Let O and O" two ontologies. A Correspondence M between O and O" is quintuple < Id, e, é, r, n > where:  Id: is a unique identifier of the correspondence M;  e and e" are the entities of O and O" respectively (concepts, relations or instances);  r: is the semantic relation between e and e" (equivalence (≡), more specific (),more general (), disjunction ());  n: is a measure of confidence, typically a value within [0, 1].

Fig. 1 .

 1 Fig. 1. Alignment Process

Fig. 2 .

 2 Fig. 2. The Architecture of the Application.

Fig. 4 .

 4 Fig. 4. The Detailed Results of the Three Methods in Terms of Precision

Table 1 .

 1 The Similarity Values Calculated by Edit Distance.

	O /O"	Book	Translator	Publisher	Writer
	Product	0.14	0.20	0.11	0.14
	Provider	0.12	0.20	0.44	0.50
	Creator	0.14	0.50	0.11	0.43
	2) If we filter out the second matrix of similarities (Table 2) calculated using
	WordNet, with a threshold s = 0.15 we obtain the following alignment:
	A2= {(Product, Book), (Product, Writer), (Provider, Writer), (Provider, Book),
	(Creator, Book), (creator, Translator), (Creator, Writer)}.

Table 2 .

 2 The Similarity Values Calculated Using WordNet.

	O /O"	Book	Translator	Publisher	Writer
	Product	0.18	0.12	0.12	0.15
	Provider	0.17	0.11	0.14	0.29
	Creator	0.18	0.47	0.12	0.15

Table 3 .

 3 The Combined Similarity Values.

	O /O"	Book	Translator	Publisher	Writer
	Product	0.16	0.16	0.11	0.14
	Provider	0.14	0.16	0.30	0.40
	Creator	0.16	0.49	0.11	0.30

http://oaei.ontologymatching.org/2012/conference.

OAEI (Ontology Alignment Evaluation Initiative) organizes evaluation campaigns aiming at evaluating ontology matching technologies. http://oaei.ontologymatching.org/


Abdelkader Khelil
email: khalilabdelkader@gmail.com

Rachid Beghdad
email: rachid.beghdad@gmail.com

Distributed Algorithm for Coverage and Connectivity in Wireless Sensor Networks

Keywords: Wireless Sensor Network (WSN), Coverage, Connectivity, Distributed Algorithm, Connected Dominating Set (CDS)

Even if several algorithms were proposed in the literature to solve the coverage problem in Wireless Sensor Networks (WSNs), they still suffer from some weaknesses. This is the reason why we suggest in this paper, a distributed protocol, called Single Phase Multiple Initiator (SPMI). Its aim is to find Connect Cover Set (CCS) for assuring the coverage and connectivity in WSN. Our idea is based on determining a Connected Dominating Set (CDS) which has a minimum number of necessary and sufficient nodes to guarantee coverage of the area of interested (AI), when WSN model is considered as a graph. The suggested protocol only requires a single phase to construct a CDS in distributed manner without using sensors' location information. Simulation results show that SPMI assures better coverage and connectivity of AI by using fewer active nodes and by inducing very low message overhead, and low energy consumption, when compared with some existing protocols.

Introduction

With the recent advances in micro-electronics technologies and wireless communications, a new type of networks has emerged: Wireless Sensor Networks (WSNs). This type of networks includes a large number of devices called sensors deployed over a geographical area to be monitored. A sensor is able to sense, process and transmit data over a wireless communication channel. The applications of WSNs include battlefield surveillance, healthcare, environmental and home monitoring, industrial diagnosis and so on [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF]. A fundamental issue in WSNs is the coverage problem [START_REF] Huang | A survey of solutions to the coverage problems in wireless sensor networks[END_REF][START_REF] Cardei | Energy-efficient coverage problems in wireless ad hoc sensor networks[END_REF] that mainly consists in ensuring continuous and effective observation of geographical area while taking into account some constraints, in particular the connectivity of active sensors. The coverage can be considered as a measure of the monitoring quality produced by a sensor network [START_REF] Meguerdichian | Coverage problems in wireless ad-hoc sensor networks[END_REF]. WSNs are usually dense and redundant (more than 20 nodes/m 3 [START_REF] Rajavavivarme | An overview of wireless sensor network and applications[END_REF]). So, the coverage of AI can be done, but it is not optimal if all nodes contribute for observing this AI. So, this drawback motivates a connected cover set (CCS) to be employed in a WSN.

Conceptually, a CCS is a set of active nodes, which can ensure coverage and connectivity. So, it provides many advantages to QoS of network. The WSN use the Connected Dominating Set Algorithm to construct a temporary CCS. Only the dominating nodes are responsible for sensing area, and other nodes (dominated nodes) can close the communication modules to save energy, in order to make the network life maximum. Various CDS algorithms [START_REF] Khelil | Coverage and Connectivity Protocol for Wireless Sensor Networks[END_REF][START_REF] Pazand | Minimum Dominating Sets for solving the coverage problem in wireless sensor networks[END_REF][START_REF] Wu | Extended dominating set and its applications in ad hoc networks using cooperative communication[END_REF][START_REF] Yuanyuan | Energy efficient distributed connected dominating sets construction in wireless sensor networks[END_REF][START_REF] Wightman | A3: A Topology Construction Algorithm for Wireless Sensor Network[END_REF][START_REF] Karthikeyan | Topology Control Algorithm for Better Sensing Coverage with Connectivity in WSN[END_REF][START_REF] Shi | A Virtual Backbone Construction Algorithm Based on Connected Dominating Set in Wireless Sensor Networks[END_REF] have been developed but they still suffer from some weaknesses, this is the reason why we focused on the solution of such a problem. In this paper, we present a novel energy-efficient CDS algorithm for WSN called a Single Phase Multiple Initiator (SPMI). The main contributions of our solution are:

(1) high coverage ratio, (2) small number of active nodes, (3) connectivity guaranteed and (4) very low communication overhead, which reduces energy consumption The rest of this paper is organized as follows. Section 2 presents related work; Section 3 presents concepts relative to graph theory, a set of notations, assumptions of our work and the problem definition. Our solution will be described in Section 4. In Section 5, simulation results will be presented and finally, Section 6 concludes this paper.

Related Work

Numerous algorithms for constructing a CDS have been surveyed in literature. We cite some of them as follow: A simple distributed and localized algorithm is proposed in [START_REF] Wu | Extended dominating set and its applications in ad hoc networks using cooperative communication[END_REF] called CDS-Rule-K algorithm. It constructs a CDS in two phases. The first phase uses marked method to generate a non-optimal CDS. Initially all nodes broadcast hello message to receive neighbor tables, and exchange their neighbor tables. If a neighbor node is not covered by other nodes, then it is marked as a node of CDS. The second phase uses pruning rules to cut redundant leaf nodes. The pruning rule specifies that if all adjacent nodes are covered by marked brother nodes, then the node is a redundant leaf node, so it is pruned and broadcasts an updates message. In [START_REF] Yuanyuan | Energy efficient distributed connected dominating sets construction in wireless sensor networks[END_REF], Yuanyuan and al. present an energy-efficient CDS algorithm (EECDS), it is based on two phases. In first phase solves a maximal independent set (MIS). Initially, all nodes are dyed white. The algorithm started from a white node, while it is dyed black and broadcasts a black message. When receiving a black message, a white neighbor node was stained gray and broadcasts a gray message. When receiving a gray message, a white neighbor node broadcasts query messages to get the states and priorities of nodes around, and sets a timer. If the timer times out ago, it did not receive any black message from its adjacent nodes, then it is dyed black and broadcasts a black message, or remain white until all the nodes in the network were stained gray or black. All the black nodes form a MIS. The algorithm in the second phase selects a number of connection nodes to connect the MIS. It starts from a nonindependent node, while it is dyed blue and broadcast a blue message. When receiving a blue message, an independent node is dyed blue and broadcasts invitation messages. When receiving the invitation message, non-independent nodes compute the priority and broadcast update messages. A non-independent node with the greatest priority is stained blue and broadcasts a blue message until all the black nodes were stained blue. All the blue nodes form a CDS. In [START_REF] Wightman | A3: A Topology Construction Algorithm for Wireless Sensor Network[END_REF], Wightman and Labrador have proposed a CDS algorithm called A3. It uses four forms of messages: Hello message, Children recognition message, Parent recognition message and sleeping message. The sink node starts the protocol by transmitting an initial hello message to their neighboring nodes. Nodes which are not in the range of sink node then this node accepts the message has not been covered by another node; it sets its state as covered, selects the transmitter as its parent node and answers back with a Parent recognition message. If a parent node does not accept any Parent recognition messages from its neighbors, it also turns off. The parent node sets a certain amount of time to accept the answers from its neighboring node. Once this time out, the parent node sorts the list in decreasing order according to the selection metric. Then, parent node broadcasts a children recognition message that includes the complete sorted list to all its candidates. Once the candidate nodes accept the list, they set a timeout period proportional to their position on the candidate list. During that timeout nodes wait for sleeping message from their brothers. If a node accepts a sleeping message during the time out period, it turns itself off. In [START_REF] Karthikeyan | Topology Control Algorithm for Better Sensing Coverage with Connectivity in WSN[END_REF], Sajjad Rizvi and al. have proposed a CDS algorithm called TC1 for improving the algorithm in [START_REF] Wightman | A3: A Topology Construction Algorithm for Wireless Sensor Network[END_REF]. It uses only one type of message: Hello message contains the parent ID of the Sender. The initiator node (sink) starts the protocol by transmitting hello message to their neighboring nodes. The neighbor nodes which received a hello message record their parent ID and calculate a timeout period according to their residual energy and distance from the sender. The child node which expires its timeout sends a hello message to its neighboring nodes too. So if the parent node receives this message, it will be a dominator node. This process continues until the complete topology is formed with nodes acting as CDS for rest of the nodes in the network. In [START_REF] Shi | A Virtual Backbone Construction Algorithm Based on Connected Dominating Set in Wireless Sensor Networks[END_REF], ShiTing-jun and al. have proposed a CDS algorithm called IPCDS. It uses the staining and markers methods to solve the MIS and CDS, and uses the pruning rule to further reduce the CDS. Initially, all nodes are dyed white and have been marked. The initiator node (white node) starts the protocol; it is dyed black and broadcasts a black message. When at first receiving black, a white neighbor node is marked as the child of nodes broadcasting message. Upon receiving a black message, if the white neighbor node is not marked, it is dyed gray and broadcasts gray messages. Upon receiving a gray message, if the white neighbor node is not marked, then according the residual energy and RSSI (Received Signal Strength Indicator) sets the timer value. If the timer times out ago, it received a black message by broadcasted the brother node, it is dyed gray and broadcasts gray messages, or it is dyed black and broadcasts black messages. Upon receiving a black message broadcasted by the child node, the gray node was stained black and broadcasts black messages. Upon the black node is in line with the pruning rule, it is dyed gray and broadcasts gray messages. This process continues until all nodes in the network are stained gray or black. At the end of algorithm, all the black nodes form a CDS.

A. WSN Model

The network is modeled by a graph G = (S, E), where S represents the vertices set and E the set of edges. An edge between two vertices u and v exists if u can communicate v. For a sensor u, it characterizes by alone identity denoted ID(u) and we distinguish two different ranges: communication range, denoted CR, and sensing range, denoted by SR. Two sensors are communicated if and only if the distance between them is at most equal to CR. The covered area from a node u (also called monitored or sensed area) is the surface within which if an event occurs it will be sensed by the sensor u. This area is modeled as a disk of radius SR centered at u. Similarly, the communication area, inside which the sensor u can send and receive messages, is modeled by a circle of radius CR centered at u. In this work, we consider CR ≤ 2SR.

B. Definitions

In this subsection we define the concept on which our work is based, i.e. Connected Dominating Set (CDS).

-Connected Dominating Set:

Given an undirected graph G=(S,E), a Dominating Set (DS) of G is a subset of vertices D ⊆ S, such that any vertex u of the graph is either in D or has a neighbor v ∈ D [18]. A graph has more than one dominating set. When a DS is connected, it is denoted as a CDS; that is, any two nodes in the DS can be connected through intermediate nodes from the DS.

C. Solution Assumptions

In this work, we assume a randomly deployed network. Once disseminated, sensors are assumed to be static. The network consists of nodes deployed in high density in order to ensure initial connectivity. Furthermore, the network is homogeneous, that is all sensors have the same sensing radius and the same communication ranges. We also assume that sensors have a unique identifier (ID). Finally, we assume that each sensor knows its degree.

D. Problem Definition

The random deployment of sensors is the most used for a broad range of applications in inaccessible environments. Due to the unplanned nature of this deployment type, a WSN could lead to sensing holes which decrease drastically the reliability of the network. In order to overcome this shortcoming, sensor nodes are disseminated in high density. Although, dense deployment minimizes the sensing holes, allows fault tolerance and increases the reliability of applications, it has its own drawbacks; maximizes the redundancy which decreases energy efficiency. Monitoring the same region of the interest area by several sensors involves a waste of energy. This behavior is in conflict with the most critical constraint of a WSN (energy efficient). Thus, it is crucial to have a solution that reduces redundancy in order to assure a good coverage ratio and connectivity.

SPMI Solution

A. SPMI Overview

The SPMI requires a single phase to generate a CDS. Nodes in the CDS are called dominators while the nonCDS nodes are referred to dominated. The aim of the SPMI is to generate a small set of dominators while keeping the message overhead and energy consumption low. The suggested algorithm allows the construction of CDS which has a minimum number of necessary and sufficient nodes in a distributed manner. In fact, each sensor performs the algorithm independently from the others in order to determine its status: Dominator (active) or Dominated (passive). Initially, all sensors are in uncovered state for a timeout and make their decision to be in active or in passive state. The active nodes form a CDS of the network, they provide coverage (monitoring) of the interest area.

The nodes having a higher level energy than their one hop neighbors, they will be the parents of their neighbors and they form DS. To make this set connected, we activate the child nodes that have a higher degree and further away from their parents. So the brothers of active child node will be in passive state. Figure 1.A represents a simple topology of 08 nodes which are uncovered in initial state; each node computes a timeout based on its level energy. In the figure 1.B, the node A will be in active state because it has a higher level energy than its neighbors, and it broadcasts a message which is received by nodes ( B, C, D, E, F, G andH) under its communication area. After receiving, they will be children of node A and they recalculate (update) their timeout based on the degree and further away from their parents. In the figure 1.C; When the timeout of nodes C, G and H expire without receiving any message from other nodes, they turn themselves in active state and broadcast a message (including their ID and parents ID) to their neighbors. The children nodes E and F are turned themselves in passive state after receiving a message which has the same parent ID from the node C. Also; the children nodes B and D are turned themselves in passive state after receiving a message from the node G. So our algorithm maintains the node A is in active state, and in its communication range, it actives only three nodes (C, G and H) to assure more the coverage and connectivity; and put the other nodes in passive state which never send message to keep their energy.

B. SPMI Description

Each sensor i is characterized by variables: E ini : initial energy (assumed to be the same for all nodes). Degree i : the one-hop neighbors number of node i. RSSI j : the signal strength of parent node j received by the child node i. It uses for estimation the distance between the nodes [START_REF] Pu | Mitigation of Multipath Fading Effects to Improve Indoor RSSI Performance[END_REF] [START_REF] Hood | Estimating DoA From Radio-Frequency RSSI Measurements Using an Actuated Reflector[END_REF]. RSSI c : the minimum required signal strength to ensure connectivity.

The functions used by a node i are: receive msg (ID j , parent j ID): that is the node i which has received a domination message from an active neighbor j. send msg (ID i , parent i ID): that is the node i which has sent a domination message.

calculate (T i ): the node i computes a timeout T i according to the formula (1).

A timeout is inversely proportional to the remaining energy level.

T i = T cons /REP i (1)
Recalculate (T i ): when the node i receives a message from its parent node j, then the node i recalculates the timeout according to the formula [START_REF] Huang | A survey of solutions to the coverage problems in wireless sensor networks[END_REF]. A timeout inversely proportional to the remaining energy level, Degree and distance between the node i and node j.

T i = T cons / ( REP i + Degree i +(RSSI c /RSSI j )) (2)
So, at first each node i computes a timeout Ti according to the formula (1) (line1).

Sensors with a higher residual energy percentage have a shorter timeout that expires earlier. Therefore, these sensors have more chance to be in active state. Sensors with a lower residual energy percentage have a longer timeout that expires later.

During this time, the sensor listens to messages sent by neighbors (lines 2&4): When the first receiving the message (line7), then the node will be the child of node broadcasting message and it recalculates its timeout according to the formula (2) (line8) (sensors with a higher residual energy percentage, higher degree and farther from parent node have a shorter timeout that expires earlier). If the node receives another message and its parent ID is the same of the parent ID in the message received (line11), then the node decides directly to change its state to a Dominated without sending any message (line16). If the timeout expires without receiving any message or receiving massages having parent ID different from the node's parent ID, the node then concludes that it is Dominator node (line19) and broadcasts a message announcing domination to its one-hop neighbors (line20 Case1: if the parent ID of node is different from the parent ID in any received message or the node never receives any message. Case2: if the parent ID in the received message is the same of the node's parent ID.

Simulation

We simulate our solution by using Java language to evaluate SPMI Algorithm and compare its performance to other Algorithms.

A. Simulation Parameters

Experimental results were obtained from randomly generated networks in which nodes are deployed over a square sensing field. The initial graph, the one formed right after the deployment, is connected. Simulations were carried over densities varying from 10 to 100 nodes. The results presented hereafter are the average of 100 iterations for each simulated scenario. The performance metrics include: 1-number of active nodes; 2-number of messages used in the CDS building process; 3-amount of energy used in the process; and 4-coverage ratio.

B. Performance Evaluation

In this subsection, we compare the performances of SPMI with other solutions: A3 algorithm [START_REF] Wightman | A3: A Topology Construction Algorithm for Wireless Sensor Network[END_REF]; EECDS [START_REF] Yuanyuan | Energy efficient distributed connected dominating sets construction in wireless sensor networks[END_REF]; CDS-Rule-K algorithm [START_REF] Wu | Extended dominating set and its applications in ad hoc networks using cooperative communication[END_REF]; TC1 algorithm [START_REF] Karthikeyan | Topology Control Algorithm for Better Sensing Coverage with Connectivity in WSN[END_REF] and the IPCDS algorithm [START_REF] Shi | A Virtual Backbone Construction Algorithm Based on Connected Dominating Set in Wireless Sensor Networks[END_REF].

1-CDS Size :

Figure 3 shows that when the network density increases, the numbers of nodes generated by the six kinds of algorithm are increased. It is clear that SPMI generated less CDS size compared to EECDS and CDS-Rule-k; and it is nearly similar to IPCDS. But it is more than TC1 and A3. This difference of active nodes size is exploited by SPMI for assuring more connectivity and coverage in WSN, such that only 6 to 17 nodes are active for different sensors populations.

Case2 Case1

Uncovered Dominated Dominator Fig. 3. CDS size versus network size.

2-Message Overhead:

Figure 4 shows the message overhead of the six kinds of algorithm with respect to network size. The message overhead was evaluated based on the number of messages sent by nodes during the CDS construction. SPMI requires significantly lower message overhead compared to all five algorithms when the network density increases.

The efficiency of SPMI algorithm in terms of the number of message sent is due to it requires a single phase and one message at most for each node. Contrary to EECDS, CDS-Rule-k and IPCDS which require two phases and high amount of exchanges of messages, the A3 and TC1 need a single phase but the number of message is high than SPMI, they require three messages and one message respectively for each node. In order to evaluate the energy efficiency, we used a discrete energy model. Every node has an initial energy equal to 100 units. An active node consumes 1 unit of energy during 1 unit of time and 0 if it is passive. The energy required to transmit a message is 1 unit and the one spent for its reception is 0.2; the consumption in listening state is the same one as at the reception of a message. Notice that these energy consumptions are in correspondence with the reality. Indeed, for a Mica2 sensor [START_REF]MICA2 Mote Datasheet[END_REF], the energy spent in listening state is equal to that required for the reception of a message and energy used to transmit a message is equal to five times the energy of its reception [START_REF] Ye | A randomized energy-conservation protocol for resilient sensor networks[END_REF][START_REF] Anastasi | Performance measurements of motes sensor networks[END_REF]. Figure 5 represents the total energy consumption by the all six algorithms while varying the deployed nodes number.it is clear that EECDS and CDS-Rule-k algorithms consume a high significant amount of energy and their energy increases linearly with the number of neighbors. The other algorithms consume less amount of energy; they are similar and their energies are nearly constant with the size of network; but the SPMI consumes the lowest energy for constructing the CDS. This can be explained by the low number of messages exchanged between nodes. This shows that our algorithm is scalable and can be used for a large network deployment.

4-Coverage Ratio:

The coverage ratio is evaluated by dividing the deployment area to cells. A cell is considered covered if its center is covered. We can say that although the two algorithms (EECDS and CDS-Rule-k) produce an almost similar coverage with the selected active nodes. The A3 algorithm covers the same or more area compared to EECDS and CDS-Rule-k. SPMI is still better; it covers more area than other algorithms. Such as it provides a better coverage ratio with 86.29% for the lowest density, this ratio increases gradually until it exceeds 99.66% for the highest density. For 100 deployed nodes, it is shown in Figure .5 that SPMI provides an improvement of coverage ratio equal to 3.96%, 2% and 1.96% compared to CDS-Rule-k, EECDS and A3 respectively. This is due to select far nodes from the parent node according to formula (2). Fig. 6. Coverage ratio versus network size.

Conclusion

In paper, we have proposed a distributed algorithm called SPMI that can construct a CDS in a single phase to maintain the coverage and connectivity in Wireless Sensor Networks. The SPMI limits the number of exchanged messages among nodes and keeps the number of active nodes low. Simulation has been done to validate the effectiveness of the suggested algorithm. The results show that, SPMI outperforms the other algorithms [START_REF] Wu | Extended dominating set and its applications in ad hoc networks using cooperative communication[END_REF][START_REF] Yuanyuan | Energy efficient distributed connected dominating sets construction in wireless sensor networks[END_REF][START_REF] Wightman | A3: A Topology Construction Algorithm for Wireless Sensor Network[END_REF][START_REF] Karthikeyan | Topology Control Algorithm for Better Sensing Coverage with Connectivity in WSN[END_REF][START_REF] Shi | A Virtual Backbone Construction Algorithm Based on Connected Dominating Set in Wireless Sensor Networks[END_REF] in terms of coverage ratio which is the most important metric. It also competes perfectly in terms of selected active nodes while reducing the communication overhead significantly, what decreases the energy consumption.

Our future work will focus the coverage and connectivity problem in case of mobile nodes and with the presence of obstacles.

Fig. 1 .

 1 Fig.1. An illustrative example.

  RE i : residual energy. REP i =E ini /RE i : residual energy percentage. T cons : time constant. T i : waiting time or timeout. ID i : identifier of the node i. Parent i ID: parent identifier of the node i. State i : indicates the sensor state, it may take one of values: Uncovered, Dominator or Dominated.

Fig. 2 .

 2 Fig.2. The state diagram of the SPMI algorithm.

Fig. 4 .

 4 Fig.4. Message overhead versus network size

Fig. 5 .

 5 Fig.5. Total energy consumption versus network size.

Figure 6

 6 Figure 6 represents the average coverage ratio which is defined as the percentage of interest area covered by active nodes of the four algorithms.

  ). At the end of the algorithm, all Dominator nodes are members of the CDS.

		Case1	Case2
	SPMI algorithm is formally as follows:
	For all Sensor i
	BEGIN
	1. Calculate(T i ); parent i ID=void; State i =Uncovered; Verf=true;
	2. While (T i <> 0) do
	3. Begin
	4. Listen;
	5. If receive msg (ID j , parent j ID) then
	6. Begin
	7.	If (parent i ID is void) then
	8.	parent i ID =ID j ; recalculate(T i ) ;
	9.	Else
	10.	Begin
	11.	If (parent i ID == parent j ID) then
	12.	Verf=false; Break;
	13.	End if;
	14. End if;
	15. End While;
	16. If (Verf == false) then State i = passif (dominated)
	17. Else
	18. Begin
	19. State i = active ; (dominator)
	20. Send msg (ID i , parent i ID) ;
	21. End if ;
	END.
	Figure 2 illustrates the state diagram of the SPMI algorithm.

Table 1

 1

	lists all the parameters used in


Khedidja Medani
email: khadidja-medani@hotmail.fr

Makhlouf Aliouat
email: aliouat_m@yahoo.fr

Zibouda Aliouat
email: aliouat_zi@yahoo.fr

High Velocity Aware Clocks Synchronization Approach in Vehicular Ad Hoc Networks

Keywords: VANETs, Clocks synchronization, Intelligent Transportation System, Worthwhile Road Traffic, Time Table Diffusion, TTD

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

Introduction

Over the last decade, the use of wireless ad hoc network in transportation domain has drawn particular researchers' attention in order to promote them to a satisfactory rank regarding to the numerous advantages they may provide. So, communications between vehicles (IVC: Inter Vehicular Communications) have becoming one of the most active researching area. This applicative aspect has given a new communication paradigm that ensures to the classical transportation systems more efficiency, security, conviviality, and performances. So this gives rise to the so-called intelligent transportation systems (ITS). Although vehicular ad hoc networks (VANETs) as well as Wireless Sensor Networks (WSNs) are derived from the same source namely Mobile Ad hoc NETwoks (MANETs), the satisfying results obtained from researches and works done in these fields cannot be directly applied in the context of VANETs, be-cause the specificities of the latter are more stringent in one side and plentiful in the other. For example, the velocity of nodes in VANETs may reaches extreme values while energy is abundant and does not represent any constraint. So, the high mobility environments related to road infrastructure imposes new constraints like radio obstacles, the effects of multipath and fading.

Various common services such as communication, coordination, security, and time distribution channel access method for time slot (TDMA: Time Division Multiple Access) depend strongly on the existence of synchronized clocks of different nodes (vehicles) of a considered VANET network. Thus, clock synchronization requires the availability of a common time reference for all vehicles, and since these clocks drifted naturally, it is crucial to realize synchronization with an appropriate period and accuracy.

In contrast to other dynamic networks, high mobility of VANETs imposes new requirements in terms of immediate reactivity and high dynamic connectivity. Consequently, the clock synchronization methods used in Ad Hoc networks (MANETs and WSNs) are not suitable, it is therefore important to adapt them specifically to the context of VANET or proposing new well suited. Few works devoted to the problematic of clocks synchronization in VANETs were reported in the literature, such as: RBS [1] CTS [START_REF] Shizhun | Converging Time Synchronization Algorithm for Highly Dynamic Vehicular Ad Hoc Networks (VANETs)[END_REF], TTT [START_REF] Reza | Time Table Transfer Time Synchronization[END_REF] and HCS [START_REF] Sam | A Time Synchronized Hybrid Vehicular Ad Hoc Network of Roadside Sensors and Vehicles for Safe Driving[END_REF].

The aim of the work reported in this paper is to propose a new protocol, for synchronizing node's clocks in VANETs, independently of the network topology, based on a decentralized approach, and requiring no use of a Global Positioning System (GPS) component or an existing infrastructure. The proposed protocol should be able of providing debrided synchronization where each node moves freely with the time of its local clock, but stores the needed data to synchronize other nodes. It should also provide a good precision (of the order of micro seconds), robustness against failure of nodes, and a low cost in terms of convergence time and number of messages generated. This paper is organized as follows: After an introduction of the problematic in Section I, Section II presents previous work related to clock synchronization in VANETs.

Section III is devoted to the presentation of our proposition (TTD: Time Table Diffusion), while Section IV is dedicated to the exhibition of simulation results of TTD. We conclude our work with a conclusion and future perspectives.

Related Work

Several protocols for clock synchronization in VANETs have been proposed. These protocols are classified into two approaches (Fig. 1):

Centralized approach

Among the proposed algorithms in centralized approach include GNSS: Global Synchronization for Satellite Navigation System [START_REF] Scopigno | GNSS synchronization in Vanets[END_REF] and Synchronization in ad hoc networks based on UTRA TDD [START_REF] Ebner | Synchronization in ad hoc networks based on UTRA TDD[END_REF]. These algorithms have the advantage of implementation simplicity, but however require the use of a GPS component, which may raise the problem of transmission signals power which may interfere with communications in progress within nodes.

2.2

Decentralized approach

Decentralized synchronization algorithms are sufficient for inter vehicular communications and better than the centralized ones in terms of fault tolerance. These algorithms are classified into three categories according to the time information exchange mode between vehicles [START_REF] Rentel | Network Time Synchronization and Code-based Scheduling for Wireless Ad Hoc Networks[END_REF] and are as follows:

 Burst position measurement: Each node programs the periodic transmission of a pulse and corrects its own local after receiving the new burst.  Continuous correlation of timing signals: Each node continuously transmits a signal sequence and calculates the phase offset using the received sequence. Examples of synchronization protocols based on this method are presented in [8] [9].  Clock-sampling methods: Each node reads its clock time and transmits it explicitly to other neighboring nodes. At each reception, the offsets are calculated as the difference between the local time and the time clocks of neighboring nodes. This method is superior to the other two methods in terms of simplicity, because it directly exchanges time information, without regard to phase. Among the protocols based on this method include those described in [START_REF] Elson | Fine-Grained Network Time Synchronization using Referece Broadcasts[END_REF] [2] [START_REF] Reza | Time Table Transfer Time Synchronization[END_REF]. To explain the functioning of TTD, synchronization steps are illustrated in Fig. 2.

Fig. 2. Synchronization steps in TTD.

The synchronization process begins with broadcasting of a message by the transporter node for collecting information. Neighboring nodes respond to transporter node to construct the time table (Time_table). Once the latter one is built, it should be broadcasted later by the transporter node. We describe these steps in the sequel:

Step 1

In this step, the transporter node broadcasts an advertisement message to initiate the synchronization process and to collect information needed to build the time table. The broadcasting message contains the identity of the transporter node T and t 0 , the timestamp indicating the sending instant of this message.

Step 1: Initialization by the transporter node (T) and diffusion of message for collecting information.

Step 2 : Neighbors reply.

Step 3: The transporter node Create and broadcast the time table.

Step4: Transformation and calculation of time tables by the neighbors.

Each node begins this step with sending CTS (Clear to Send) messages. The first node sending its CTS becomes the transporter node in its neighborhood.

3.2

Step 2

A node i that receiving the advertisement message of the transporter node T marks it at the receiving instant of t 1i , and then sends a response message to the transporter node T. The response message contains the identity i of the node, and the timestamps t 0 , t 1i , and t 2i where t 2i represent the instant of sending response message. One node i may join more than one transporter node at the same time.

3.3

Step 3

When T receives the reply from node i at the instant t 3i , using timestamps t 0 , t 1i , t 2i , and t 3i , T can calculate the offset relative to node i ( iT ) according to the equation ( 1) below and saves the result in the time table where the index access is the identity of node i.

 iT = ((t 1i -t 0 ) -(t 3i -t 2i ))/2. ( 1
)
Fig. 3 hereafter illustrates the messages exchange between the transporter node T and a node i: Fig. 3. Messages exchange between the transporter node T and a node i.

After T has completed the construction of the time table, it has to broadcast it to all its neighbors' node allowing them to build their own time tables.

Step 4

When a node i receives the time table from a transporter node T, it can build its own table as follows: Node i will search in the received table the corresponding value to its identity ( iT ), and stores the inverse of this value in its own table in the location corresponding to the identity of the node T ( ( ) -). The principle is the following:

 iT = C i -C T.
(

) 2
Multiplying both sides of (2) by (-1), we obtain:

 Ti = C T -C i. ( 3
) Node i t 1i t 2i Node T t 0 t 3i
Where, C T is the clock value of node T at the instant t, and C i is the clock value of node i in the same instant t.

To synchronize itself with the rest of the nodes table, node i will add  Ti value to all values in the table according to the following principle:

 jT = C j -C T . ( 4
)
 Ti = C T -C i . ( 5
)
By adding the two parts of ( 4) and ( 5) we obtain:

 jT +  Ti = (C j -C T ) + (C T -C i ) = ji . ( 6
)
As shown in Fig. 4, depending on the transporter node (that depend on the random number generated by each node), we can find two neighbors not synchronized (node 2 and node 4 participate to the synchronization process under different transporter nodes, that make nodes 2 and 4 two neighbors not synchronized).

Fig. 4. Problem posed by the random time

A solution to this problem is that inspired from [START_REF] André | Decentralized Slot Synchronization In Highly Dynamic Ad Hoc Networks[END_REF] which consist to larger the range of synchronization packet transmission to be equal double that of data packet transmission. In this way, a transporter node T ensures the synchronization of the nodes joining with all its neighbors (one hop) and in most cases, the synchronization on multi-hop paths. For mobility management, and since the clocks drifted naturally (the live duration of synchronization is an important evaluation criteria of synchronization's algorithms), it is crucial to achieve often synchronization process cycles as shown in Fig. 6.

The number of messages necessary to accomplish the synchronization is calculated as follows: Assuming there are Ni nodes within the synchronization scope of a transporter node Ti, where Ti ∈ T (where T is the set of transporter nodes in the current cycle). We can summarize the number and content of messages required for synchronization, as shown in Table I.

According to this table, the number of messages (nbMsg) necessary to accomplish the synchronization can be estimated as follows: nbMsg ∑ (N i ) n t -1 i [START_REF] Rentel | Network Time Synchronization and Code-based Scheduling for Wireless Ad Hoc Networks[END_REF] Table 1. Exchange message type and their content.

Message Number Content

The avertissement message sent by the transporter node (ADV_T).

, where is the number of transporter nodes in the current cycle.

Transporetr node identity and the timestamp t0.

Neighbords reply (JOIN_RESPONSE).

∑ N i n t 1 Neignbord i identity and timestamps t0, t1i, t2i.

Time table (TIME_TABLE). n t Time table built by the transporter node

Simulation Results

We simulated the proposed protocol using the combination of the simulator NS2 and the mobility generator VanetMobiSim. Clocks values used in simulation are randomly generated according to the law of GAUSS ( average, δ 1 ppm) [START_REF] Lombardi | Frequency Measurement. The Measurement, Instrumentation and Sensors Handbook[END_REF].

We tested a number of scenarios by changing essential parameters to evaluate the performances of our proposed protocol where nodes are initially placed in random positions and their movement direction follows the mobility model implemented by VanetMobiSim in Intelligent Driver Model with Lane Changing (IDM_LC: It regulates vehicle speed based on movements of neighboring vehicles (e.g., if a car in front brakes, the succeeding vehicles also slows down). The implementation reflects restrictions of the spatial environment. Vehicles moving according to the IDM_LC model support smart intersection management: they slow down and stop at intersections, or act according to traffic lights, if present. The implementation reflects re-

No yes

Receive time table and create the once one.

Neighbors replay.

End cycle

Node i

Transporter?

Node i Transporter

Broadcasting of advertissement.

Time table creation.

Receive all responses.

Receive advertissement.

Broadcasting of time table.

strictions of the spatial environment. Also, vehicles are able to change lane and perform overtaking in presence of multi-lane roads). The metrics used to analyze the simulation results are the number of messages generated and the time of convergence (convergence time is the time required to accomplish the synchronization process). Fig. 7 shows that the convergence time in TTD increases with increasing of nodes number, this is due to the large number of neighbors reply messages. In contrast, nodes speed has no influence on the convergence time because TTD solution uses broadcast (Fig. 8). This property is an advantage for the proposed algorithm and makes it usable in different vehicles mobility environments (urban, suburban, and highway). However, convergence time in TTT [START_REF] Reza | Time Table Transfer Time Synchronization[END_REF] increases in urban environments characterized by a minimal speed compared to other vehicles mobility environments. This is because the TTT protocol uses node mobility as an essential factor for time table transfer. Thus, the convergence time shown by our protocol is less than that shown by the reference protocol TTT under the same conditions, as shown in Fig. 9. The number of messages required to accomplish the synchronization process is not fixed and depends on two essentials factors; nodes number and transporter nodes number (that depends on the transmission range). On one hand, the number of messages increases with a large number of nodes (as shown in Fig. 10); logically this is due to the phase of neighborhood replays, the most consuming phase in the synchronization process in term of messages number. On the other hand, depending on the transmission range, that affects the transporter nodes number, the number of messages increases with a the increasing of the number of transporter nodes. For example, in a topology 1000 * 1000 (m 2 ) with a number of nodes equal to 30 (low density network), we can achieve a data transmission range up to 1000 m, in this case, only one transporter node is sufficient to achieve the synchronization process, so we can reach a minimum number of messages that is equal to the nodes number in the network plus one.

Conclusion

Although clock synchronization in VANETs is a very important research area, few works have been reported so far in the specialized literature. In this paper, we propose a new efficient synchronization protocol taking into account the specific constraints imposed by VANET environments. The proposed solution called TTD (Time Table Diffusion) provides released clock synchronization in a vehicular environment independently of the network topology. TTD achieves synchronization with a good accuracy of the order of a microsecond, and in most cases, synchronization of multi-hop paths. The proposed solution is simulated with the combination of VanetMobiSim-NS2 to evaluate its performance in terms of number of messages generated and convergence time. The simulation results showed that TTD provides a best convergence

Fig. 1 .Fig. 1 .

 11 Fig. 1.

Fig. 5 .

 5 Fig. 5. Improved initial model of the synchronization by TTD.

Fig. 6 .

 6 Fig. 6. Clock synchronization using TTD.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Convergence time Vs nodes number in TTD.

Fig. 9 .

 9 Fig. 9. Convergence time in TTD Vs Convergence time in TTT

Fig. 10 .

 10 Fig. 10. Messages number Vs nodes number.

  time compared to its homologues TTT (TTT provide best result than RBS in term of convergence time).

Table Diffusion Protocol

  Transferring time table by the transporter node makes nodes able to calculate their relative clock offsets with the nodes in the time table without even having any message exchanges. Thus, this will offers a great advantage since it contributes to avoid network congestion. TTD provides synchronization in vehicular environments independent of the network topology in which each node has a unique identity in the network.

Our proposition named Time Table Diffusion (TTD) exploits the idea of transferring a time table implemented by the TTT protocol

[START_REF] Reza | Time Table Transfer Time Synchronization[END_REF]

for clock synchronization in mobile sensor networks. The basic idea is to choose a transporter node (T) to transfer a time table containing the offsets related to different nodes. These offsets are calculated by the offset delay estimation method

[START_REF] Mills | Internet Time Synchronisation: The Network Time Protocol[END_REF]

. TTT protocol uses nodes mobility to transfer time table. The clock offset associated to each node will be kept in the memory of node in a time table, and upon communicating with a new node, the time table would be transferred to the other node. This process provides a long convergence time (in order of seconds) which make a conflict with the real time applications of VANETs (alert messages …).

Table 2 .

 2 Simulation Parameters.

	Topologie (m2)	1000*1000
	Nodes number	30/50/100/200/300
	Speed (m/s)	7/10/15/20/25/30/35
	Trafic light	6
	Mobility model	Randomly according to IDM_LC
		with 2 obstacles every 100 m 2
	Range data transmission	250/500/1000
	(m)
	Simulation time (s)	1000