Correction of depression after temporal muscle flap: a systematic review of the litterature

Keywords: Literature review, temporal muscle flap, reconstruction, temporal depression, biomaterial

Background

There are several ways to fill the depression created after temporal muscle flap. Historically, many methods have been described but biomaterials are increasingly used for this indication.

We conducted a systematic review of the literature on the use of biomaterials to fill this depression.

Methods

The databases MEDLINE (via PubMed), Cochrane Library, EBSCO, Web of Sciences and Embase were searched for clinical trial reports, case series, case reports and cohort studies from 1991 to 2015. We conducted a systematic review of the use and efficacy of different biomaterials. Patient satisfaction was systematically researched.

Results

We identified 11 articles (196 patients) which were included in the systematic review. The biomaterials used are polymethyl methacrylate (PMMA), polyethylene (PE), lipofilling, Titanium (Ti) and Mersilene Mesh (MM). Complications occurred only with PMMA and MM.

Patient satisfaction was rather good in all the studies.

Conclusion

There is no evidence of the superiority of one biomaterial over another as there was a lack of high quality studies. More randomized and controlled studies are required to draw conclusions on the matter.

Introduction

The temporal muscle flap has been used successfully as a pedicled flap in craniofacial surgery for over a century [START_REF] Shagets | Use of Temporalis Muscle Flaps in Complicated Defects of the Head and Face[END_REF][START_REF] Koranda | The Temporalis Muscle Flap for Intraoral Reconstruction[END_REF]. The capacity to cover large congenital, trauma, skeletal or facial surgery defects has been proven in many studies [START_REF] Habel | The Versatility of the Temporalis Muscle Flap in Reconstructive Surgery[END_REF][START_REF] Colmenero | Temporalis Myofascial Flap for Maxillofacial Reconstruction[END_REF][START_REF] Demas | Transmaxillary Temporalis Transfer for Reconstruction of a Large Palatal Defect: Report of a Case[END_REF]; van der [START_REF] Wal | The Temporal Muscle Flap for Closure of Large Palatal Defects in CLP Patients[END_REF][START_REF] Bradley | The Temporalis Muscle Flap in Oral Reconstruction. A Cadaveric, Animal and Clinical Study[END_REF]. The temporalis muscle is commonly used as a pedicled flap (Spanio di Spilimbergo, 2017) primarily to fill cavities within a radius of about 8 cm from the coronoid process [START_REF] Shagets | Use of Temporalis Muscle Flaps in Complicated Defects of the Head and Face[END_REF]: exenterated orbit (passing through the outer orbital wall) [START_REF] Adenis | Anophthalmic Orbital Implants[END_REF][START_REF] Gola | Repair of orbital exenteration cavities[END_REF][START_REF] Menon | Orbital Reconstruction after Exenteration: Use of a Transorbital Temporal Muscle Flap[END_REF], filling of the cheek or upper maxilla (orbital floor, nasal fossa, ipsilateral palate [START_REF] Koranda | The Temporalis Muscle Flap for Intraoral Reconstruction[END_REF][START_REF] Demas | Transmaxillary Temporalis Transfer for Reconstruction of a Large Palatal Defect: Report of a Case[END_REF]; van der [START_REF] Wal | The Temporal Muscle Flap for Closure of Large Palatal Defects in CLP Patients[END_REF]). It is used to treat temporomandibular ankylosis [START_REF] Su-Gwan | Treatment of Temporomandibular Joint Ankylosis with Temporalis Muscle and Fascia Flap[END_REF][START_REF] Majumdar | Suture of Temporalis Fascia and Muscle Flaps in Temporomandibular Joint Surgery[END_REF]. Temporalis muscle grafts are also used as a cover. Other applications are possible in facial paralysis, where parts of the temporal muscle can be transferred to resuscitate mouth-corner or palpebral occlusion. This technique applied for this indication is called lengthening temporalis myoplasty.

Temporal depression is a common consequence of temporalis muscle flap (TMF). This defect is characterized by a concavity in the soft tissue contour of the temporal region and is associated with marked elevation of the lateral orbital rim and zygomatic arch. This defect is not mentioned by most authors, was dismissed as minimal by [START_REF] Koranda | The Temporalis Muscle Flap for Intraoral Reconstruction[END_REF] (Koranda etal., 1987) and described as being smoothed out by scarring after several months by Huttenbrink (1989) (Huttenbrink, 1989). For several years, no surgical procedure was used to reconstruct this defect.

Instead, it was camouflaged via hair styling which was obviously problematic in bald men. [START_REF] Habel | The Versatility of the Temporalis Muscle Flap in Reconstructive Surgery[END_REF] acknowledged the problem and suggested using only the posterior part of the muscle if possible, to reduce the cosmetic defect [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF]. However, Tan et al. demonstrated that the remaining anterior part was not sufficient to fill the depression [START_REF] Tan | Temporal Flap Variations for Craniofacial Reconstruction[END_REF]. Bradley et al. (1988) suggested two solutions. The first was to avoid replacing the resected arch so that the change in contour was less abrupt, and the second was to use a free fat graft from the buttock.

Other authors transferred the buccal fat pad, bone grafts and other autologous materials. But, over time, these materials tend to be reabsorbed, especially after radiation, with poor long-term cosmetic results. This marked the emergence of the use of biomaterials (BM). The most suitable material must be biocompatible, tissue-friendly, stable, easily malleable, custom-made and radiationfriendly.

Several biomaterials are currently used to fill temporal depressions. Porous high-density polyethylene implants (PHDPE or PE) or polymethyl methacrylate (PMMA) can be used either alone or in combination with residual muscle in the temporal fossa, and represent the most widely used substances in such reconstructions at present [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF][START_REF] Baj | Use of Porous Polyethylene for Correcting Defects of Temporal Region Following Transposition of Temporalis Myofascial Flap[END_REF].

Studies have confirmed the safety and clinical effectiveness of these materials in the restoration of temporal defects.

There are other materials and techniques for this indication, such as titanium implants (TI) [START_REF] Hatamleh | A Novel Approach to Immediate Restoration of the Cosmetic Deformity After Regional Temporalis Flap Reconstruction of a Maxillary Defect: A Case Report[END_REF], Mersilene mesh (MM) [START_REF] Atherton | Augmentation of Temporal Fossa Hollowing with Mersilene Mesh[END_REF] and autologous fat transplantation (lipofilling) [START_REF] Cervelli | Autologous Fat Transplantation for the Temporalis Muscle Flap Donor Site: Our Experience with 45 Cases[END_REF].

Evidently, the range of available techniques is wide and heterogeneous. However, no comparative study was found that assessed the superiority of one or the other. Consequently, we decided to conduct a systematic review of articles concerning the use of biomaterials to reconstruct defects after temporalis muscle flap. We tried to identify the ideal biomaterial to repair soft tissue hollowing.

Search Strategy

Two independent reviewers conducted a systematic review of related articles published between 1991 and 2015 in the MEDLINE (via PubMed), Cochrane Library, EBSCO, Web of Science and Scopus databases. This systematic review respected the PRISMA standard. The following keywords were used for the search: "temporalis muscle flap donor site" or "temporalis muscle flap morbidity" or "temporalis muscle flap complication" or "temporalis muscle flap hollowing" in combination with "reconstruction" or "rehabilitation" or "management" or "restoration". Gray literature was also searched.

Study selection

Article selection was based on an initial screening of titles and abstracts and was followed by screening of full texts. The eligibility criteria for studies were 1) Reconstruction of a defect with a biomaterial following temporalis muscle flap; 2) Evaluation of the cosmetic results at least by the patient; 3) A minimum follow-up of 6 months; 4) Articles written in English.

Exclusion criteria were 1) Animal studies or preclinical studies or reviews; 2) TMF defect non-reconstructed with a BM and 3) Combined treatment (a combination of two BMs, or a combination of a BM with any other technique).

Data collection process and quality assessment

Data were extracted by two independent reviewers (J. L. and J. U.) who used a standard data collection form. Each study was assessed for study quality and level of evidence according to the Oxford Center for Evidence-Based Medicine 2011 guidelines (Howick et al., 2011). Two reviewers independently scored the study quality.

Literature search (Figure 1)

Database searches using predefined keywords yielded 7,386 articles. After adding articles from reference lists and removing duplicates, 543 potential articles were screened by reading the titles. From these, the abstracts of 46 articles were screened. The full texts of 24 articles were then screened. 11 articles fit the inclusion and exclusion criteria, and were included in the systematic review.

Characteristics of studies that were included (Table 1)

The characteristics of the 11 articles (196 patients) in the systematic review are in Tables 1 and2. In four articles, PMMA was used [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF][START_REF] Falconer | Reconstruction of the Defect at the Donor Site of the Temporalis Muscle Flap[END_REF][START_REF] Cheung | The Use of Mouldable Acrylic for Restoration of the Temporalis Flap Donor Site[END_REF][START_REF] Wright | Use of Palacos (R)-40 with Gentamicin to Reconstruct Temporal Defects after Maxillofacial Reconstructions with Temporalis Flaps[END_REF], in another 4 articles PE was used [START_REF] Baj | Use of Porous Polyethylene for Correcting Defects of Temporal Region Following Transposition of Temporalis Myofascial Flap[END_REF][START_REF] Worley | Augmentation of the Anterior Temporal Fossa after Temporalis Muscle Transfer[END_REF][START_REF] Rapidis | The Use of Temporal Polyethylene Implant after Temporalis Myofascial Flap Transposition: Clinical and Radiographic Results from Its Use in 21 Patients[END_REF][START_REF] Lacey | Use of Porous High-Density Polyethylene Implants in Temporal Contour Reconstruction[END_REF], in 1 article lipofilling was used [START_REF] Cervelli | Autologous Fat Transplantation for the Temporalis Muscle Flap Donor Site: Our Experience with 45 Cases[END_REF], in 1 article Titanium was used [START_REF] Hatamleh | A Novel Approach to Immediate Restoration of the Cosmetic Deformity After Regional Temporalis Flap Reconstruction of a Maxillary Defect: A Case Report[END_REF] and in 1 article Mersilene Mesh was used (Atherton etal., 2010).

102 patients benefitted from the use of PMMA, 38 from PE prosthesis, 45 from lipofilling, 1 from a titanium prosthesis and 10 from Mersilene Mesh.

The average ages of the different BM groups are similar: 61.03 years for the PMMA group, 47.55 for the PE group, 52.8 for the lipofilling group, 54 for the titanium group and 40.1 for the Mersilene Mesh group. The average age for all patients in this review is 51.1 years.

With regards to study quality, 10 are level 4 [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF][START_REF] Baj | Use of Porous Polyethylene for Correcting Defects of Temporal Region Following Transposition of Temporalis Myofascial Flap[END_REF][START_REF] Hatamleh | A Novel Approach to Immediate Restoration of the Cosmetic Deformity After Regional Temporalis Flap Reconstruction of a Maxillary Defect: A Case Report[END_REF][START_REF] Atherton | Augmentation of Temporal Fossa Hollowing with Mersilene Mesh[END_REF][START_REF] Falconer | Reconstruction of the Defect at the Donor Site of the Temporalis Muscle Flap[END_REF][START_REF] Cheung | The Use of Mouldable Acrylic for Restoration of the Temporalis Flap Donor Site[END_REF][START_REF] Wright | Use of Palacos (R)-40 with Gentamicin to Reconstruct Temporal Defects after Maxillofacial Reconstructions with Temporalis Flaps[END_REF][START_REF] Worley | Augmentation of the Anterior Temporal Fossa after Temporalis Muscle Transfer[END_REF][START_REF] Rapidis | The Use of Temporal Polyethylene Implant after Temporalis Myofascial Flap Transposition: Clinical and Radiographic Results from Its Use in 21 Patients[END_REF][START_REF] Lacey | Use of Porous High-Density Polyethylene Implants in Temporal Contour Reconstruction[END_REF]) and 1 is level 3 [START_REF] Cervelli | Autologous Fat Transplantation for the Temporalis Muscle Flap Donor Site: Our Experience with 45 Cases[END_REF] (Table 2).

The mean follow-up for this review was 38,72 months (61,1 for PMMA group, 26,22 for PE group, 15,9 for Mersilene Mesh, 22 for lipofilling). The follow-up was not communicated for the article with titanium.

Efficacy

Satisfaction was good for all the studies.

Safety

In terms of safety, we recorded a total of 6 complications for 196 patients (3.06%). There were 2 infections (1.02%). One occurred in the study by Wright et Finally, 2 implants were removed as a result of infection and a dehiscence wound [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF][START_REF] Wright | Use of Palacos (R)-40 with Gentamicin to Reconstruct Temporal Defects after Maxillofacial Reconstructions with Temporalis Flaps[END_REF].

Discussion

Temporal muscle flap is a widely used flap in the reconstruction of the orofacial sphere.

Whether pedicled or free, whole or duplicated, there is always a purely aesthetic defect at the donor site.

For several decades now, there has been a growing interest in repairing this depression, particularly with biomaterials. However, none has yet been clearly proven to be superior over another, which leads to excessive variability in patient care. It is important to know whether some biomaterials are more effective than others in order to generalize their use among maxillofacial surgeons. Therefore, our aim was to reference all the articles that dealt with donor site filling of a temporal muscle flap with a biomaterial, through a review of the literature.

The first step of our work was to identify what is a biomaterial. For example, it is not clearly expressed in the literature if lipofilling is a biomaterial. Many consider a biomaterial as any substance that has been engineered to interact with biological systems for a medical purpose, either a therapeutic (treat, augment, repair or replace a tissue function of the body) or a diagnostic one. It can either be derived from nature or synthesized in the laboratory. So it may also be an autograft (so the lipofilling), allograft or xenograft used as a transplant material.

But, according to the definition of the American National Institute of Health, which at the moment is the internationally accepted one: "Biomaterial is a non-drug substance for inclusion in systems which augment or replace the function of bodily tissues or organs". The aim of the lipofilling is precisely to fill a hollow or create a volume using the patient's fat. So we can consider that lipofilling is an answer to the last definition and is a biomaterial.

Eleven articles were analyzed to assess the effectiveness of the different filling techniques for the TMF donor site. We identified 6 different BMs in this indication. It can be noted that in the literature, the two BMs that were most often used for this indication are PE and PMMA (4 studies each).

Review outcome

Efficacy

All the articles showed good results in terms of patient satisfaction. There is no difference in terms of satisfaction between different BMs. However, in the article by Baj et al., only the satisfaction of the surgeons was evaluated. We believe that patient satisfaction is the most important criteria to judge the efficacy of an aesthetic filling treatment.

Unfortunately, most articles rate patient satisfaction subjectively, without any details on how this was assessed. Finally, only 3 articles use a quantitative satisfaction scale [START_REF] Cheung | The Use of Mouldable Acrylic for Restoration of the Temporalis Flap Donor Site[END_REF][START_REF] Cervelli | Autologous Fat Transplantation for the Temporalis Muscle Flap Donor Site: Our Experience with 45 Cases[END_REF][START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF]. In addition, only Mandlik [START_REF] Mandlik | Use of Polymethyl Methacrylate-Based Cement for Cosmetic Correction of Donor-Site Defect Following Transposition of Temporalis Myofascial Flap and Evaluation of Results after Adjuvant Radiotherapy[END_REF] evaluates satisfaction reliably with a validated questionnaire and imagery.

Safety

PMMA has more complications than PE and other BMs. In fact, of the 6 complications in this study, 5 were found in studies using PMMA (one for Mersilene Mesh), or 4.9% of the patients. (Figure 2)

In terms of complication rates, it would appear that PE and lipofilling are the safest BMs with no complications (38 and 45 patients respectively). With just a case report, no conclusion can be drawn concerning Titanium. On the other hand, PMMA (4.9%) and MM (10%) seem to cause more complications (Figure 2). Nevertheless, there is a lack of completeness in the research of complications. For example, as the Cervelli et al. study shows, there are specific complications with lipofilling such as secondary interventions (multiple procedures) due to lack of results after the first procedure.

Of the 45 patients in their study, 35 underwent a second procedure and one a third procedure to achieve the expected result. A loss of results is also systematic with lipofilling, which is defined by the rate of fat resorption. For Cervelli et al. [START_REF] Cervelli | Autologous Fat Transplantation for the Temporalis Muscle Flap Donor Site: Our Experience with 45 Cases[END_REF], resorption averaged 20.57cc after the first procedure. It is probably this high resorption rate (which ranges from 20 to 80% in some articles [START_REF] Tiryaki | Staged Stem Cell-Enriched Tissue (SET) Injections for Soft Tissue Augmentation in Hostile Recipient Areas: A Preliminary Report[END_REF]) that makes many surgeons doubt the use of lipofilling in first line treatment. This is why new methods are being used today in an attempt to reduce this loss of efficacy and to improve lipofilling, for instance by using stem cells in the recent technique of cell-assisted lipotransfer [START_REF] Laloze | Cell-Assisted Lipotransfer: Friend or Foe in Fat Grafting? Systematic Review and Meta-Analysis[END_REF]. There are also other complications in lipofilling not identified by Cervelli, such as false cysts, abscesses, infections, oily necrosis, etc. [START_REF] Zhou | Combined Flaps Based on the Superficial Temporal Vascular System for Reconstruction of Facial Defects[END_REF].

Limitations

There are many ways to fill temporal muscle donor site defects. A review of the literature already listed all the articles on the subject. They mainly concerned the prevention of this defect [START_REF] Vaca | Review: Postoperative Temporal Hollowing: Is There a Surgical Approach That Prevents This Complication? A Systematic Review and Anatomic Illustration[END_REF]. However, it seemed more relevant to focus on the effectiveness of techniques to treat temporal depression because this defect is constant. We excluded the articles that did not have sufficient data on this specific matter.

We also excluded articles about filling defects in the temporal region by the same BM which did not concern the same indication [START_REF] Jns172574 | Prevention of 'Temporal Hollowing' after Fronto-Orbital Advancement for Craniosynostosis[END_REF][START_REF] Scholz | Reconstruction of the Temporal Contour for Traumatic Tissue Loss Using a CAD/CAM-Prefabricated Titanium Implant-Case Report[END_REF][START_REF] Gordon | Temporal Augmentation With Methyl Methacrylate[END_REF], but rather defects induced by craniotomy or craniectomy, and therefore related to bone and not muscle. Characteristics of the BM and the expected results were actually not comparable.

Furthermore, no data about intervention time was found. It is preferable to carry out the shortest possible procedures to reduce morbidity and mortality. It is therefore essential to collect this specific data in order to be able to compare different BMs for surgical procedures.

One of the main indications for temporal muscle flaps is oncological maxillectomies. A good portion of these patients undergo adjuvant radiotherapy, which can lead to complications ending in the loss of BM. Five of the 11 studies presented in our review analyze the effect of radiation after the introduction of a BM. With regard to PE, 2 studies discuss the effect of radiation. No complications are found in these studies, nor is there any difference in the shape of the implant after adjuvant RT. For PMMA, mersilene mesh and lipofilling, there is also a study that presents such results. No complications are found here either. Cervelli claims that there is no additional fat resorption for lipofilling. In fact, many studies demonstrate the efficacy of lipofilling after RT ( [START_REF] Turnhout | Surgical Outcome and Cosmetic Results of Autologous Fat Grafting After Breast Conserving Surgery and Radiotherapy for Breast Cancer: A Retrospective Cohort Study of 222 Fat Grafting Sessions in 109 Patients[END_REF]. Lipofilling provides post-burn tissue with quality and flexibility. Finally, Mandlik demonstrates that there is no change in the shape and volume of the implant after radiation.

Nowadays, public health and its effects in terms of costs are increasingly important topics.

Health systems tend to choose the least expensive biomaterial. Lipofilling with autologous fat is the least expensive option. A PE or PMMA prosthesis costs about $300 ("Anophthalmic Orbital Implants" n.d.; Morales-Gómez, 2018). Titanium implants cost about $3,000 [START_REF] Höhne | Reconstruction of Extensive Oropharyngeal Defects with the Temporalis Muscle Flap -Our 4-Year Experience in 26 Cases[END_REF]). If we compare the average price of the 4 most frequently used BMs, lipofilling seems to be the least expensive (although several procedures may be necessary before the desired result is obtained).

In the end, the main bias of this review remains that all of the articles that were included in the study have a low power and a low level of evidence. It is essential to perform comparative, randomized, high power studies to draw concrete conclusions.

Conclusion

Lipofilling appears to be one of the best therapeutic choices to fill the donor site after a temporal muscle flap. In fact, it is an autologous transplant, of similar consistency, with an excellent price-effectiveness ratio, few complications, and it is possible after radiotherapy. But according to the findings of this review, we cannot identify the ideal biomaterial to repair this soft tissue hollowing. Only a meta-analysis with randomized high-power studies would provide a concrete answer to the question.

  al. with PMMA (1.96% of the 102 patients) and the other in the study by Atherton et al. with the use of Mersilene Mesh (10% of the 10 patients). Two persistent depressions at the donor site which required reintervention within 21 months were found in the Cheung et al. article (1.96% of PMMA patients). Two other complications occurred in the Mandlik et al. study with the use of PMMA, including 1 seroma (0.98% of patients) and one wound dehiscence (0.98% of patients).

FiguresFigure 1 .

 1 Figures

  Figure 1. Flow chart of study selection

Table 1 . Characteristics of the included studies

 1

Yr : Year; SD : Standard Deviation; Mo : Month; NA : Not Available; PMMA : PolyMethylMethAcrylate

Table 2 . Study design and level of evidence Study

 2

design and level of evidence based on Oxford Center for Evidence-Based Madicine 2011 guidelines (Howick J, Chalmers I, Glasziou P, et al. The Oxford 2011 Levels of Evidence, Oxford Center for Evidence-Based Medicine, Available at: http://www.cebm.net/index.aspx?o=5653. Accessed September 21, 2014).

Figure 2. Complication rate of different biomaterial in percentage.

Conflict of interest

This research received no specific grant from funding agencies in the public, commercial, or non-profit sectors.


Nathalie Eisenbaum

Some percolations involving the Gaussian free fields

Keywords: Percolation, Gaussian free field, permanental process, positive association, Markov chain, local times. MSC2010 subject classifications : 60A10, 60G10, 60G15, 60G17, 60G50, 60G55, 60G60

Consider an infinite, connected, locally finite graph with vertex set V. Intuitively a simple point process on V with attractive properties, should percolate more easily than a Bernoulli point process with the same marginales. Although it seems wrong to imagine that it could be true in general, we confirm this intuition on several examples involving Gaussian free fields and permanental free fields.

Introduction

Consider a non-oriented, infinite, connected, locally finite, graph G, with vertex set V and edge set E. Given a family of Bernoulli variables (Y x , x ∈ V), one may ask whether the random subgraph of G with vertex set {x ∈ V : Y x = 1} and edge set {[x, y] ∈ E : Y x = 1 and Y y = 1}, contains an infinite connected component. In short does {x ∈ V : Y x = 1} percolate? There is a general answer to this question in the case when the variables Y x , x ∈ V are i.i.d. One sets: p = IP [Y x = 1]. There exists a critical probability p site c (G) in [0, 1], such that for p > p site c (G), {x ∈ V : Y x = 1} percolates and for p < p site c (G), {x ∈ V : Y x = 1} does not. For G = Z d , one knows that p site c (Z 2 ) > 1/2 (see [START_REF] Higuchi | Coexistence of the infinite (*) clusters: a remark on the square lattice site percolation[END_REF]) and that for d ≥ 3: p site c (Z d ) < 1/2 (see [START_REF] Campanino | An upper bound on the critical percolation probability for the three-dimensional cubic lattice[END_REF]). When the Bernoulli variables are not independent, it is much more difficult to solve this question. As an example of dependent Bernoulli variables, take: Y x = 1 {ηx>h} , x ∈ Z d , where h is a fixed real level and (η x , x ∈ Z d ) is a centered Gaussian process. One particular case has been intensively studied: the case when η is the Gaussian free field on Z d for d ≥ 3, which means that η is a centered Gaussian process with the following covariance:

IE[η x η y ] = IE x [ ∞ n=0 1 {Un=y} ]
where (U n ) n≥0 is a simple random walk on Z d . By definition, this covariance is the Green function of (U n ) n≥0 . There exists a critical level h * such that -for h < h * , the set {x ∈ Z d : η x > h} a.s. has an infinite connected component.

-for h > h * , the set {x ∈ Z d : η x > h} a.s. has only finite connected component. It has been shown by Bricmont, Lebowitz and Maes [START_REF] Bricmont | Percolation in strongly correlated systems: the massless Gaussian field[END_REF], that h * ≥ 0 and that moreover in dimension 3: h * < ∞. Then Rodriguez and Sznitman [START_REF] Rodriguez | Phase transition and level-set percolation for the Gaussian free field[END_REF] have shown that h * < ∞ in any dimension and that h * > 0 in high dimension. Finally Drewitz, Prévost and Rodriguez [START_REF] Drewitz | The sign clusters of the massless Gaussian free field percolate on Z d , d ≥ 3 (and more)[END_REF] have shown that in any dimension h * > 0 (i.e. IP (η 0 > h * ) < 1/2). In [START_REF] Drewitz | The sign clusters of the massless Gaussian free field percolate on Z d , d ≥ 3 (and more)[END_REF], the authors suggest that their result could be the consequence of the following conjecture:

IP (η 0 > h * ) < p site c (Z d ), (1.1)
based on the intuition that positive correlation should help in forming clusters and hence an infinite cluster. Indeed the Gaussian free field η is positively correlated in the sense that its covariance is positive. But thanks to Pitt [START_REF] Pitt | Positively correlated normal variables are associated[END_REF], this fact implies the much stronger following property called "positive association":

IE[F (η)H(η)] ≥ IE[F (η)]IE[H(η)] (1.2)
for any couple (F, H) of increasing functionals on functions from V into IR (increasing with respect to each coordinate). For example, one has for every x 1 ,..,x n in Z d :

IP [η x 1 > h, .., η xn > h] ≥ IP [η x 1 > h]..IP [η xn > h],
which legitimates (1.1). We test this intuition on another positively associated process: [START_REF] Eisenbaum | On the infinite divisibility of squared Gaussian processes[END_REF]) and is hence positively associated in the sense of (1.2) thanks to [START_REF] Burton | The central limit problem for infinitely divisible random measures[END_REF]. Rodriguez [START_REF] Rodriguez | Level set percolation for random interlacements and the Gaussian free field[END_REF] has proved that there exists h c < ∞ such that for h > h c a.s. the set {x ∈ Z d : |η x | > h} does not percolate. One obviously has: h * ≤ h c . Consequently: 0 < h c < ∞. In view of the above intuition, one would expect that:

(|η x |, x ∈ Z d ). We know that (|η x |, x ∈ Z d ) is positively associated because (η 2 x , x ∈ Z d ) is infinitely divisible (see
IP [|η 0 | > h c ] < p site c (Z d ).
We have the following result:

IP [|η 0 | > h c IE[η 2 0 ]] ≤ p site c (Z d ),
which gives the following lower bound.

Theorem 1.1 For d ≥ 3, one has

h o ≤ h c < ∞
where for N o real standard Gaussian variable, h o satisfies:

IP [|N o | > h o ] = p site c (Z d ).
Since one has: IE[η 2 0 ] ≥ 1, the above result is weaker than its intuition. But as shown in section 2 (Theorem 2.1), this result is "universal" in the sense that it is available for every centered Gaussian process associated to a symmetric transient homogenous Markov chain on any infinite connected graph. In Theorem 2.1 the jumps of the Markov chain are not limited to the closest neighbors. One can extend Theorem 2.1 from absolute value of Gaussian free fields to permanental free fields. This extension consists in relaxing the assumption of symmetry for the associated Markov chain. We remind that the permanental free fields are also positively associated [START_REF] Eisenbaum | On permanental processes[END_REF]. The result is presented in section 2 (Theorem 2.2).

Finally, in section 3, we extend the result of Bricmont, Lebowitz and Maes [START_REF] Bricmont | Percolation in strongly correlated systems: the massless Gaussian field[END_REF] to transient simple symmetric random walks on any regular graph. This extension has been already noticed by Abächerli and Sznitman (Proposition A2 in [START_REF] Abächerli | Level-set percolation for the Gaussian free field on a transient tree[END_REF]). In [START_REF] Drewitz | Geometry of Gaussian free field sign clusters and random interlacements[END_REF], Drewitz, Prévost and Rodriguez go further by showing that h * > 0 for a large class of graphs. The interest of our proof is located in the use of a basic Dynkin isomorphism type theorem.

Extension to all Gaussian and Permanental free fields

For G non-oriented, locally finite, infinite connected graph determined by (V, E), let U = (U n ) n≥0 be a transient homogenous Markov chain on V, with transition matrix P = (P (x, y)) (x,y)∈V×V . The Markov chain U is allowed to have jumps from x to y with [x, y] outside E. The paths of (U n ) n≥0 are not necessarily subgraphs of G. Actually U lives on the graph G(U ) with edge set

E(U ) = {[x, y] ∈ V × V : P (x, y) + P (y, x) > 0}.
We draw attention on a result of Benjamini and Hermon (Theorem 2 in [START_REF] Benjamini | Recurrence of Markov chain traces[END_REF]) according to which if U is irreducible, transient and E(U ) = E (i.e. G(U ) = G) then the simple random walk on G might not be transient. More precisely, if U has the additional property to cover G with positive probability, then the simple random walk on G is recurrent.

Since we are dealing only with homogenous Markov chain, we will omit the term homogenous.

Theorem 2.1 Let G be an infinite connected graph with a locally finite vertex set V and edge set E. Let h G be the nonnegative number such that: In case G is such that p site c (G) = 1, Theorem 2.1 does not bring any information on the percolation properties of the absolute value of the Gaussian free fields. One can extend Theorem 2.1 from absolute value of Gaussian free fields to permanental free fields. This extension consists in relaxing the assumption of symmetry for the associated Markov chain. We first recall that a permanental process (ϕ(x), x ∈ V) with index β > 0 and a kernel k = (k(x, y), (x, y) ∈ V × V) is a nonnegative process with finite dimensional Laplace transforms satisfying, for every x 1 , x 2 ,..,x n in V:

IP [|N o | > h G ] = p site c (G)
E[exp{- 1 2 n i=1 α i ϕ(x i )}] = det(I + αK) -β
where α is the diagonal matrix with diagonal entries (α i ) 1≤i≤n , I is the n × n-identity matrix and K is the matrix (k(x i , x j )) 1≤i,j≤n . Note that the kernel of a permanental process is not unique. In case β = 1/2 and k is symmetric positive semi-definite, (ϕ x , x ∈ V) equals in law (η 2

x , x ∈ V) where (η x , x ∈ V) is a centered Gaussian process with covariance k.

Consider a Markov chain with state space V and finite Green function (g(x, y), (x, y) ∈ V × V). For every β > 0, there exists a permanental process with index β and kernel (g(x, y), (x, y) ∈ V × V) (see [START_REF] Eisenbaum | On permanental processes[END_REF]). The permanental processes obtained that way, can be called, by analogy with the Gaussian free fields, permanental free fields. Note that the permanental free fields are infinitely divisible and hence positively associated (by using again [START_REF] Burton | The central limit problem for infinitely divisible random measures[END_REF]).

Theorem 2.2 Let G be an infinite connected graph with a locally finite vertex set V and edge set E. Let h G be the nonnegative number such that:

IP [|N o | > h G ] = p site c (G)
where N o is a standard Gaussian real variable. Then for every h < h 2 G , for every permanental field (ϕ x ) x∈V with index 1/2 admitting for kernel the Green function of a transient Markov chain on V, the sub-graph {[x, y] ∈ E : ϕ x > h and ϕ y > h} has a.s. an infinite connected component.

Proof of Theorem 2.1 Let (η x , x ∈ V) be a centered Gaussian process with covariance the Green function of a transient symmetric Markov chain on G, U = (U n ) n≥0 . The law of U is characterized by its transition matrix P = (P (x, y)) (x,y)∈V 2 . By assumption: P (x, y) = P (y, x), ∀x, y ∈ V. Denote by g = (g(x, y), (x, y) ∈ V 2 ) its Green function i.e.

g(x, y) = ∞ n=0 IP x [U n = y].
Note that for every x in V: g(x, x) ≥ 1. As usual, one can associate to U a time continuous Markov chain X = (X t ) t≥0 by spending at each site of V an exponential time with parameter 1, independently of the jumps that are then performed according to P to leave the site. Then X is a transient symmetric Markov process with the same Green function as U and admitting a local time process (L x t , x ∈ V, t ≥ 0). Fix a finite subset J = {x 1 , x 2 , .., x n } of V and set: G = (g(x i , x j )) 1≤i,j≤n . We now compute an alternative expression of G. To do so we reproduce an argument used in a particular case in [START_REF] Eisenbaum | On the infinite divisibility of squared Gaussian processes[END_REF] (proof of Theorem 2.1). Set σ = inf{t ≥ 0 : X t ∈ {x 1 , x 2 , .., x n } \ {X 0 }}. The time σ may be infinite in that case the value of X σ is a cemetery point. Set:

b ij = IE x i (L x j σ ) and q ij = IP x i [X σ = x j ]. Note that: b ij = 0 for i = j, q ii = 0 and n j=1 q ij = 1 -IP x i [σ = ∞].
Thanks to the Markov property we have:

g(x i , x j ) = IE x i [L x j ∞ ] = IE x i [L x j σ ] + IE x i [σ < ∞; IE Xσ [L x j ∞ ]] = b ij + n k=1 q ik g(x k , x i ).
Let B and Q be the matrices defined by: B = (b ij ) 1≤i,j≤n and Q = (q ij ) 1≤i,j≤n . The above computation shows that: G = B + QG, equivalently: B = (I -Q)G. Since X spends an exponential time with parameter 1 at each site before leaving it, we have: b ii ≥ 1, for every i = 1, .., n. Consequently B is invertible and hence so are (I -Q) and G. One obtains:

G = (I -Q) -1 B. (2.1)
For λ 1 , ..λ n in IR + , denote by λ the diagonal matrix with entries λ 1 , .., λ n . Note that

det(I + λG) = det(I + λ(I -Q) -1 B) = det(I + λB 1/2 (I -Q) -1 B 1/2 ),
where B 1/2 is the diagonal matrix with entries √ b 11 , .., √ b nn .

Consequently: (|η

x i |) 1≤i≤n (law) = (|φ x i |) 1≤i≤n , where (φ x i ) 1≤i≤n is a centered Gaussian vec- tor with covariance B 1/2 (I -Q) -1 B 1/2 . The centered Gaussian vector ( φx i √ b ii ) 1≤i≤n has (I -Q) -1 for covariance.
Since: (I -Q) ≤ I, one deduces, thanks to Theorem 2.3 in the paper of Karlin and Rinott [START_REF] Karlin | Total positivity properties of absolute value multinormal variables with applications to confidence interval estimates and related probabilistic inequalities[END_REF], that:

(|N x i |) 1≤i≤n ≺ ( |φ x i | √ b ii ) 1≤i≤n ,
where (N x ) x∈V is a family of i.i.d. standard Gaussian variables and the symbol "≺" denotes a relation of stochastic domination. Remember that for every i = 1, .., n: b ii ≥ 1, to conclude that

(|N x i |) 1≤i≤n ≺ (|φ x i |) 1≤i≤n ,
which can also be written:

(|N x |) x∈J ≺ (|η x |) x∈J .
Since the above stochastic domination is true for every finite subset J, by a simple limiting argument, one obtains:

(|N x |) x∈V ≺ (|η x |) x∈V . (2.2)
Consequently by Strassen Theorem, there exists a coupling (|η|, | Ñ |) of |η| and |N | such that for every x in V :

|η x | ≥ | Ñx |. One hence has for every h ≥ 0 {x ∈ V : | Ñx | > h} ⊂ {x ∈ V : |η x | > h}. Let a be an element of V. If IP [| Ña | > h] > p site c (G), then a.s. {x ∈ V : | Ñx | > h} has an infinite connected component and hence {x ∈ V : |η x | > h} has also an infinite connected component.
Proof of Theorem 2.2 Let (ϕ x , x ∈ V) be a permanental process with index 1/2 and kernel (g(x, y), (x, y) ∈ V 2 ), the Green function of a transient random walk on V. This random walk is not assumed to be symmetric. Fix a finite subset J = {x 1 , x 2 , .., x n } of V and set: G = (g(x i , x j )) 1≤i,j≤n . The argument developed in the proof of Theorem 2.1 to establish (2.1) does not require symmetry. Keeping the same notation, one has: G = (I -Q) -1 B, which leads to: det(I + λG) = det(I + λB 1/2 (I -Q) -1 B 1/2 ). One obtains that way that (ϕ x i ) 1≤i≤n admits for kernel the matrix B 1/2 (I -Q) -1 B 1/2 . Consequently the permanental vector ( ϕx i b ii ) 1≤i≤n admits for kernel (I -Q) -1 . We use now an extension of the result of Karlin and Rinott (Theorem 2.1 in [START_REF] Karlin | Total positivity properties of absolute value multinormal variables with applications to confidence interval estimates and related probabilistic inequalities[END_REF]) to permanental vectors established by Marcus and Rosen [START_REF] Marcus | Conditions for permanental processes to be unbounded[END_REF]. They call it the permanental inequality. For simplicity, we enunciate it in the particular case we are interested in.

Permanental inequality Let φ be a permanental vector with index 1/2 admitting for kernel a non-singular matrix K = (K ij ) 1≤i,j≤n . Assume that K -1 = I -Q with Q ii = 0 for every i = 1, .., n. Then :

(N 2 i ) 1≤i≤n ≺ (φ i ) 1≤i≤n ,
where the variables N i , i = 1, .., n, are i.i.d. centered real standard Gaussian variables.

One obtains:

(N 2 x i ) 1≤i≤n ≺ ( ϕ x i b ii ) 1≤i≤n ,
where (N x ) x∈V is a family of i.i.d. standard Gaussian variables. Since for every i = 1, .., n: b ii ≥ 1, one has

(N 2 x i ) 1≤i≤n ≺ (ϕ x i ) 1≤i≤n , which leads to (N 2 x ) x∈V ≺ (ϕ x )
x∈V , and hence to the conclusion.

Remark 2.3 Actually Theorem 2.2 holds for any index β > 0. More precisely, define h G,β as the number such that:

IP [Γ β > h G,β ] = p site c (G)
, where Γ β is a gamma random variable with shape parameter β and scale parameter 1 (i.e. with density x β-1 e -x Γ(β) 1 x≥0 ). Then for every h < h G,β , and every permanental process (ϕ x , x ∈ V) with index β admitting for kernel the Green function of a transient random walk on G: {x ∈ V : ϕ x > h} has a.s. an infinite connected component. This is obtained similarly thanks to the general version of Marcus and Rosen's permanental inequality [START_REF] Marcus | Conditions for permanental processes to be unbounded[END_REF].

Critical level sets for the Gaussian free fields

The graphs that we are considering are always non-oriented, locally bounded, infinite and connected. We assume that they are subsets of IR d for some d ≥ 1. The next proposition extends the result of Bricmont et al [START_REF] Bricmont | Percolation in strongly correlated systems: the massless Gaussian field[END_REF] from the simple symmetric random walk on Z d to any transient simple random walk on an infinite graph. By simple random symmetric walk on a graph G = (V, E), one means a homogenous Markov chain such that its transition matrix P = (P (x, y)) (x,y)∈V 2 satisfies: P (x, y) = P (y, x), P (x, y) > 0 if [x, y] ∈ E and P (x, y ) = P (x, y ) for any y , y such that [x, y ], [x, y ] are in E. The existence of such a process on G implies that G is regular in the sense that the vertices all have the same degree. One can hence assume without changing the matrix P that the edges all have the same length. Such a graph is said to be transient when the simple symmetric random walk on G is transient. Given a graph G = (V, E) and a real valued process (η x , x ∈ V), to mean that the subgraph of G with vertex set {x ∈ V : η x > h} and edge set {[x, y] ∈ E : η x > h and η y > h} contains an infinite connected subset of G, we just write: {η > h} percolates.

The set {x ∈ G : L x ∞ > 0} is a.s. an infinite connected subset of G. It is the support of B. Consequently, thanks to (3.1), one has for every r = 0: To show Proposition 3.1 one could have used Sznitman's interlacement isomorphism Theorem [START_REF] Sznitman | An isomorphism theorem for random interlacements[END_REF] instead of (3.1). The interest of (3.1) lies on the fact that it involves more elementary notions.

  where N o is a standard Gaussian real variable. Then for every h < h G , for every centered Gaussian field (η x ) x∈V with covariance the Green function of a transient symmetric Markov chain on V, the subgraph of G with edge set {[x, y] ∈ E : |η x | > h and |η y | > h} has a.s. an infinite connected component.

1 =

 1 IE[ ηa + r r ; {x ∈ G : (η x + r) 2 > 0} has an infinite connected component] which implies: IP [{x ∈ G : (η x + r) 2 > 0} has an infinite connected component] > 0. (3.2) Let C be an infinite connected subset of G such that : |η x + r| > 0, ∀x ∈ C. Then, because of the continuity of η, either : ηx < -r, ∀x ∈ C; either: ηx > -r, ∀x ∈ C. Using (3.2) one obtains: IP [{x ∈ G : ηx > -r} has an infinite connected component] + IP [{x ∈ G : ηx < -r} has an infinite connected component] > 0. and equivalently: IP [{x ∈ G : ηx > -r} has an infinite connected component] + IP [{x ∈ G : ηx > r} has an infinite connected component] > 0, which leads to: 2IP [{x ∈ G : ηx > -|r|} has an infinite connected component] > 0, for every r = 0. We finally obtain: IP [{x ∈ V : η x > -|r|} has an infinite connected component] > 0 for every r = 0.

Proof Denote by (g(x, y), (x, y) ∈ V 2 ) the Green function of the simple random walk on G. Let (η x , x ∈ V) be a centered Gaussian field with covariance (g(x, y), (x, y) ∈ V 2 ). We extend (η x , x ∈ V) to the whole graph G. To do so we make use of B, Brownian motion on the graph G. We refer to Varopoulos [START_REF] Varopoulos | Long range estimates for Markov chains[END_REF], Chacon and Baxter [START_REF] Baxter | The equivalence of diffusions on networks to Brownian motion[END_REF], Barlow, Pitman and Yor [START_REF] Barlow | On Walsh's Brownian motions[END_REF] or Enriquez and Kifer [START_REF] Enriquez | Markov chains on graphs and Brownian motion[END_REF], for various ways to construct B. This process can be roughly described as follows.

Starting from a point in the interior of an edge of G, B moves along this edge as a real Brownian motion until it reaches one of its end points, call it x o . At this time B chooses uniformly an edge coming out of x o , independently of the past, and moves like a real valued Brownian motion on the chosen edge until it reaches one of its end points.

Since the simple symmetric random walk on G is transient, B is transient. Denote by g = (g(x, y), (x, y) ∈ G) the Green function of B. The restriction of g to V ×V coincides with g. Then define the extension (η x , x ∈ G) of (η x , x ∈ V) to G, by IE[η x ηy ] = g(x, y), for x, y in G. One chooses η independent of B.

One defines a distance d on G by using the Lebesgue distance, inside any given edge and by defining the distance between two vertices of V as the minimal sum of length of edges necessary to connect one to the other. The process B admits a local time process (L x t , x ∈ G, t ≥ 0) which is continuous with respect to d × Leb(IR + ). Indeed, the local time process is obviously continuous at each point of G \ V. What about continuity at a point of V ? Since it is a local question, it is equivalent to study the continuity at 0 of the local time process of a Brownian motion on a graph with one single vertex 0 and n infinite edges coming out of 0, with equal probability to be chosen starting from 0. According to Theorem 2.1 (2.18) in [START_REF] Ichiba | Stochastic integral equations for Walsh semimartingales[END_REF], the local time process at 0 of this process is continuous. Consequently the local time process of B is continuous on G. By Theorem 1 in [START_REF] Marcus | Sample path properties of the local times of strongly symmetric Markov processes via Gaussian processes[END_REF], we hence know that (η x , x ∈ G) is continuous with respect to d. Fix an element a of V. Condition on (B 0 = a), the laws of (L x ∞ , x ∈ G) and (η x , x ∈ G) can be connected thanks to a so-called isomorphism theorem established in [START_REF] Eisenbaum | Une version sans conditionnement du théorème d'isomorphisme de Dynkin[END_REF], as follows:

for every non-zero real number r.


Tawfiq Nebbou

Mohamed Lehsaini

Hacène Fouchal
email: hacene.fouchal@univ-reims.fr

Partial Backwards Routing Protocol for VANETs

Keywords: VANETs, Road Connectivity, Traffic information, Geographic Routing Protocols, Backward strategy

The design and implementation of efficient routing protocols for highly dynamic networks such as Vehicular Ad hoc NETworks (VANETs) is a challenging task, due to the specific features of these networks such as rapid movements of nodes, frequent link disconnections and large scale networks. Efficient routing mechanisms need to adopt to the VANETs characteristics to achieve high routing performances. One alternative is the use of the traffic information in the routing process. In this paper, we propose a novel routing protocol called Partial Backwards Routing Protocol (PBRP), which consists of three integrated strategies: dissemination of road traffic information, partial forwarding algorithm and backwards recovery strategy working together to provide permanent and advanced information about vehicular traffic which widely helps the routing algorithm to stand up to dynamic changes of VANETs topology, and to bypass the local vision which is the drawback of GyTAR/EGyTAR protocols. Our proposed protocol has been developed over OMNET++ simulator, evaluated and compared with some other protocols. The simulation results show that the packet delivery ratio of our proposal is upper about 54% compared to GyTAR/EGyTAR and the end-toend delay of our protocol is reduced by 75% for most of scenarios.

Introduction

A Vehicular Ad hoc Network (VANET) is a highly mobile wireless ad hoc network designed to achieve many objectives related to driving safety, traffic management. VANET is a self-organized network composed of the interconnection of vehicles in which the vehicles can communicate with each other directly via Vehicle-to-Vehicle (V2V) communications, or with infrastructure namely the Road-Side-Unit (RSU) through Vehicle-to-Infrastructure (V2I) communication.

A mixed communication V2V and V2I is also possible in such networks. VANETs have their own features not common with the other classes of wireless ad hoc networks, even with its nearest class which is the Mobile Ad-hoc Networks (MANETs). The high mobility of vehicular nodes implies frequent topology changes causing difficulties to use topology-based routing protocols. Many researches have been proposed to address the routing problems in VANETs, such as geographic routing protocols.

In geographic routing protocols, when an intermediate vehicular node needs to forward data packets to a destination vehicle, the source vehicle transmits the data directly to destination in the case of destination within its communication range i.e. destination is a neighboring node. In the other cases, the source vehicle requests its position through location services such as GLS (Grid Location Service) [START_REF] Li | A Scalable Location Service for Geographic Ad Hoc Routing[END_REF][START_REF] Ayaida | A Comparison of Reactive, Grid and Hierarchical Location-based Services for VANETs[END_REF], HLS(Hierarchical Location Service) [START_REF] Ayaida | PHRHLS: A Movement-prediction-based joint routing and Hierarchical Locatio Service for Vanets[END_REF], RLS (Reactive Location Service) [START_REF] Kasemann | A Reactive Location Service for Mobile Ad Hoc Networks[END_REF] and SFLS (Semi-Flooding Location Service) [START_REF] Renault | Semi-Flooding Location Service[END_REF]. Once the position of the destination node is available, the source node inserts the location information about the destination in the header of packet and selects a neighboring vehicle as a next-hop by using its own forwarding strategy (e.g. nearest neighbor to the destination). When the next-hop receives properly the data packets it becomes the new forwarding node and should repeat the same process until the destination is reached using a greedy approach, note that the forwarding node repeats the same process of source node except the destination position request process, because of the destination position is already in the packet header. The request process is not updated in every hop because when a vehicle sends position request to LIS, in this case, the vehicle cannot forward data until it receives destination position replay from its LIS. So, it is not appropriate to repeat this process because it takes significant time and generates more delay to deliver packets. We suggest that only the last vehicle can repeat the location request process . In the scenario where no suitable neighbour could be found (local optimum), the forwarding node can either switch to recovery mode, or drop data if there is no recovery mode strategy supported by the routing protocol. In the case of the well known recovery mode, the Store Carry and Forward (SCF) and the Perimeter Forwarding are proposed in GPSR protocol [START_REF] Karp | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[END_REF].

This study presents a novel routing protocol for VANETs called Partial Backwards Routing Protocol (PBRP), which consists of three integrated strategies: dissemination of road traffic information, partial forwarding algorithm and backwards recovery strategy working together to provide permanent and advanced information about vehicular traffic which widely helps the routing algorithm to stand up to dynamic changes of VANETs topology, and to bypass the local vision which is the drawback of GyTAR/EGyTAR protocols. We have proposed primary ideas of this work in [START_REF] Nebbou | Advanced Measurement of Road Traffic Information in City Environments[END_REF]. This kind of protocol is very useful for some practical applications as emergency message exchange, entertainment stream exchange between vehicles.

The remainder of the paper is organized as follows. Section 2 is dedicated to related works. Section 3 details our solution. Section 4 details the results of our simulations. Section 5 concludes the study and gives some ideas on future extensions.

Related works

The well known greedy routing protocol for VANETs called Greedy Perimeter Stateless Routing (GPSR) is proposed in [START_REF] Karp | GPSR: Greedy Perimeter Stateless Routing for Wireless Networks[END_REF]. In GPSR protocol, the packet transmission is performed through two routing strategies: Greedy forwarding and Perimeter forwarding. Greedy forwarding strategy consists in selecting the closest node to the destination as the next-hop, in the case where the distance between the forwarding node and the destination is closer than the distance to the destination of its neighbors. In such cases, GPSR switches to the perimeter forwarding strategy which is based on the right-hand rule. GPSR is more efficient on highway environments than in city one due the presence of obstacles, which leads to increase link failures and causes more greedy forwarding fails.

In [START_REF] Boussoufa-Lahlah | Geographic routing protocols for Vehicular Ad hoc NETworks (VANETs): A survey[END_REF], the authors present a recent survey on geographic routing protocols. [START_REF] Dua | A systematic review on routing protocols for Vehicular Ad Hoc Networks[END_REF] is dedicated to a review on various routing protocols, it provides a very useful study on routing over vehicular networks. A detailed distinction of various routing techniques is presented with discussion according to its advantages, and disadvantages, along with its constraints. [START_REF] Oubbati | A survey on position-based routing protocols for Flying Ad hoc NETworks (FANETs)[END_REF] discusses a comprehensive survey of position-based routing protocols for FANETs (Flying Ad hoc Networks) with their various categories. FANETs are a special case of VANETs, they cover a 3-dimension space. Another intelligent routing protocol for vehicular ad hoc networks proposed in [START_REF] Wu | Toward Practical and Intelligent Routing in Vehicular Ad Hoc Networks[END_REF] able to interact with the environment to learn the transmission parameters by taking into account various metrics such as data-rate and route length. This protocol is based on two algorithms: Rate estimation algorithm and Route selection algorithm. The Rate estimation algorithm adopts Q-Learning algorithm to estimate the reception ratio by using Hello messages as an indicator of link quality. In addition, the Route selection algorithm uses the Q-Learning and fuzzy logic-based algorithms to find the best route in term of end-to-end delay and to evaluate the direct link respectively.

In [START_REF] Daas | Optimizing geographic routing protocols for urban vanets using stigmergy, social behavior and adaptive c-n-f mechanisms: An optimized clwpr[END_REF], using the three proposed mechanisms, the authors propose an optimized geographic routing protocol called O-CLWPR based on CLWPR which uses information transport via Stigmergy, Social Behavior and Adaptive Caching Time of the Carry-and-Forward mechanism. The simulations have been done using NS-3 simulator and the obtained results show a real improvement of the end-to-end delay.

In [START_REF] Abbas | Clustering-based reliable low-latency routing scheme using aco method for vehicular networks[END_REF], a new clustering-based reliable low-latency multipath routing (CRLLR) scheme is proposed by using Ant Colony Optimization (ACO) technique. The link reliability is used as criteria for Cluster Head (CH) selection i.e a vehicle will be selected as CH if it has maximum link reliability. The ACO technique is employed to compute the optimal routes among the communicating vehicles for VANETs in terms of reliability, end-to-end latency, throughput and energy consumption. Simulation results demonstrate that the proposed protocol outperforms other protocols in term of overall latency and reliability.

Another geographic routing protocol called Directional Greedy Routing (DGR) [START_REF] Gong | Predictive Directional Greedy Routing in Vehicular Ad hoc Networks[END_REF] solves the previous drawback of GPSR protocol. DGR uses the information about vehicle directions to improve the inter-vehicle communication, it combines two forwarding strategies: 1) Position first forwarding which consists to forward the packets to the closest node towards destination, 2) Direction first forwarding based on a simple geographic greedy forwarding in which it tries to find the closest neighbor node moving towards the destination as nexthop. Predictive Directional Greedy Routing (PDGR) [START_REF] Gong | Predictive Directional Greedy Routing in Vehicular Ad hoc Networks[END_REF] is an extended version of DGR, it uses two-hop neighbor beacons to predict the future neighbors, reducing links failure and improve the next-hop selection mechanism.

Geographic Source Routing (GSR) [START_REF] Lochert | A Routing Strategy for Vehicular Ad Hoc Networks in City Environments[END_REF] is an another alternative of geographic routing protocol that takes the advantage of city environment by using map street information in the routing process. In GSR, the geographic position of destination node is maintained via the reactive-based location service RLS [START_REF] Kasemann | A Reactive Location Service for Mobile Ad Hoc Networks[END_REF]. In addition, GSR uses Djikstra algorithm on a graph containing the geographic information and the urban topology to calculate the shortest path, this path is composed of a sequence of junctions from source to destination. Each packet should follow the sorted list of junctions within the path to reach the destination. However, the major weakness of GSR is that uses a static information to compute the shortest path, this mechanism is almost not suitable in such dynamic networks as VANETs which leads to decrease the performance of routing.

A-STAR (Anchor-based Street and Traffic A ware Routing) [START_REF] Seet | A-STAR: A Mobile Ad Hoc Routing Strategy for Metropolis Vehicular Communications[END_REF] uses traffic vehicular information in the routing process, it assigns a connectivity value to the roads depending of its capacity and number of bus line. The source vehicle computes the shortest path toward the destination by applying Dijkstra algorithm on a graph which is weighed by the road connectivity values.

VPGR (Vertex-Based Predictive Greedy Routing) [START_REF] Shrestha | Vertex-Based Multihop Vehicle-to-Infrastructure Routing for Vehicular Ad Hoc Networks[END_REF] is a vertex-based routing protocol using the hybrid communication V2V and V2I. VPGR predicts a sequence of vertices from the source node to a fixed infrastructure within the location area of the final destination, then uses PDGR forwarding technique to forward packet between vertices. VPGR uses a simple metric RT (Remaining Time) to select the shortest path, this metric aims to select a vertex, which has a large remaining time of vehicles. This mechanism does not add new information for routing process because there are vehicles in the crossroads. Moreover, the shortest path is not optimal because it does not take in consideration the vehicular traffic information between vertices.

GyTAR (Improved Greedy Traffic Aware Routing) [START_REF] Jerbi | Towards Efficient Geographic Routing in Urban Vehicular Networks[END_REF] is a geographical routing protocol conceived for VANETs in urban environment. The main idea of this protocol is the dynamic junction selection mechanism based on road density (number of vehicles on the road) and curvemetric distance to the destination. GyTAR uses Cell Density Packet (CDP) to provide the information about candidate junctions in which the packets must pass, however, the initiation of CDPs is not regular with time because the initiation is based on which vehicle is about to leave its road. EGyTAR (Enhanced Greedy Traffic Aware Routing protocol) [START_REF] Bilal | Enhanced junction selection mechanism for routing protocol in VANETs[END_REF] is an extended ver-sion of GyTAR. In EGyTAR the dynamic junction selection mechanism is based on the number of vehicles moving toward the candidate junctions (directional density).

AQRV (Adaptive Quality of service (QoS) based Routing for VANETs) [START_REF] Li | Adaptive Quality-of-Service-Based Routing for Vehicular Ad Hoc Networks With Ant Colony Optimization[END_REF] adopts ant colony algorithm to solve NP-complet problem which is constrained optimization problem of routing selection issues such as connectivity probability, packet delivery ratio and endto-end delay. Moreover, in order to achieve best QoS the authors propose Ant Colony Optimization (ACO) to address this goal.

In B-MFR (Border node-based most forward withing radius) [START_REF] Raw | B-MFR routing protocol for vehicular ad hoc networks[END_REF] routing protocol, the authors define tree types of nodes based on the location of the neighboring nodes relative to the transmission range, in which the neighboring nodes within the transmission range are called "interior nodes", the nodes which are located on the border of transmission range are called "border nodes", and those outside are referred to as outer nodes. The main idea of this protocol is to forward the packet through the border nodes in order to minimize the number of hops between source and destination.

GPGR (Grid-based Predictive Geographic) routing protocol proposed in [START_REF] Cha | Grid-Based Predictive Geographical Routing for Inter-Vehicle Communication in Urban Areas[END_REF] combines between road topology information and vehicles mobility information in order to improve inter-vehicle communications and reduce local maximum forwarding problem. GPGR can avoid links failure by selecting a suitable next-hop based on the information of topology and vehicles mobility.

In LSGO (Link State Aware Geographic Opportunistic) routing protocol [START_REF] Cai | LSGO: Link State aware Geographic Opportunistic routing protocol for VANETs[END_REF], the authors propose that each node calculates the link Expected Transmission Count (ETX) by the help of Periodic Hello packets. LSGO uses ETX value and destination distance as priority metrics. The higher priority node can forward the packet to its destination directly, in the contrary, the low priority node must wait a predefined timer, if the timer expires, and the high priority node does not transmit the packet, then, this low priority node can send the packet. For this reason LSGO uses multicast communications to perform the transmission, however, this mechanism increases the routing overhead and congests the network throughput.

LOR (Localized Opportunistic Routing) protocol [START_REF] Li | Trading Optimality for Scalability in Large-Scale Opportunistic Routing[END_REF] is an opportunistic routing protocol in which the topology are partitioned into nested Close-Node-Sets (CNSs) based on local information by using Distributed Minimum Transmission Selection algorithm (MTS-B). As result, the network are transformed from network of nodes to network of CNSs, in other words, each CNS acts as single node, then, for routing data. LOR proto-col adopts AODV [START_REF] Chakeres | AODV routing protocol implementation design[END_REF] to find CNSs path which contains CNS sequences.

HLAR (Hybrid Location-based Ad hoc Routing) protocol [START_REF] Al-Rabayah | A New Scalable Hybrid Routing Protocol for VANETs[END_REF] combines between reactive routing protocols and location-based routing protocols. The main idea of HLAR is to use reactive routing protocol as an alternative for routing data when the location information degrades. HLAR combines greedy forwarding algorithm and AODV-ETX which is a modified version of AODV in which the Expected Transmission Count (ETX) [START_REF] De Couto | A highthroughput path metric for multi-hop wireless routing[END_REF] is used as metric instead of minimum hop-count.

Contribution

We aim to propose a novel routing protocol which is robust and efficient for Non Delay Tolerant Networks conceived for VANETs in order to improve the routing performance in city environment. The proposed protocol is composed of three essentials parts: 1) Dissemination of Road Traffic Information, 2) Partial Routing Algorithm, 3) Backwards Recovery Strategy.

Furthermore, in our contribution, we used Manhattan Grid mobility model which describes the vehicles movement in a grid area of 1500mx1500m composed of 16 straight roads in urban area. Moreover, the nature of the roads whether curved or straight does not have an impact on the results since the radio links propagate directly.

Dissemination of Road Traffic Information

The goal of Dissemination of Road Traffic Information (DRTI) is to deal with dynamic nature of VANETs. The main idea of DRTI is to maintain Road Traffic Information (RTI) of each road and share it with its successor roads as shown in Figure 1.

The closest vehicle to a junction (cross roads) is selected as RTIP Initiator Node(RIN) (yellow vehicle). The RINs are responsible to initiate periodically the Road Traffic Information Packet(RTIP), and forward it in the direction of all neighbouring junctions. The RIN node initiates periodically (at each 0.8 second) the RTIP packet in order to compute the connectivity, taking into consideration the vehicle speed in urban environment. The connectivity of a road does nt have significant changes after 0.8 seconds. In other hand, the RTIP lifetime equals to 0.8 seconds which ensures the validity of the connectivity values. The first interesting property of our dissemination mechanism is that the RTIP packet can hold a number of roads information depending on the RTIP lifetime, this is mainly proposed to bypass the local vision which is the case of many routing protocols such as GyTAR [START_REF] Jerbi | Gy-TAR: Improved Greedy Traffic Aware Routing Protocol for Vehicular Ad Hoc Networks in City Environments[END_REF] and EGyTAR [START_REF] Bilal | Enhanced junction selection mechanism for routing protocol in VANETs[END_REF]. Figure 2 shown an example for local vision and advanced vision.

Additionally, DRTI provides a fresh information about roads such as packet crossing delay, the density of roads (number of vehicles) and road connectivity. For achieving this objective, in the following sub-sections we describe Road Dividing scheme, Road Traffic Information Packet (RTIP), the calculation of road connectivity and finally the dissemination of RTIP algorithm.

Road Dividing scheme

In our proposed routing protocol, each road is divided into a fixed number of physical cells in such manner that the area of a given road is fully covered by a certain number of physical cells with the same size depending on the transmission range (R tr ), the road width and the road length. In order to ensure these properties, let us start with an example of two consecutive cells like it shown in Figure 3:

The blue circles represent cells that come into contact in point 'c', the points 'a' and 'e' indicate centres of cells, 'f' and 'g' designate the intersection of cells with the road side as described in the figure , 'b' and'd It should be noted that the physical cells are used to defining a group of vehicles. Moreover, each group have to handle the vehicles information and must be involved in the dissemination of road information process.

The problem posed here is when the vehicles located in the yellow area can not be involved in the dissemination of road information process, this is because they are not belong to any group. We therefore propose to determine the distance between cells in order to avoid the blind area (yellow area) as shown in Figure 4. This new cell distance is computed by pulling the right cell towards the left cell by the length of the segment [bd] as follow :

new cell distance = [ae] -[bd] (1)
Based on the figure 3, we have:

[bd] = 2[cd] = 2([ce] -[de]) (2)
[de]

= [ge] 2 -[gd] 2 = R 2 tr -(Rw/2) 2 (3)
Where Rw represents the road width.

According to (3):

(2)

⇒ [bd] = 2R tr -2 R tr 2 -(Rw/2) 2 (4)
According to ( 4):

(1) Thus, according to (5), the maximum spacing cell in order to avoid blind area is defined as:

⇒ new cell distance = 2 R tr 2 -(Rw/2) 2 (5)
Max cell spacing = 2 R 2 tr - Rw 2 4 (6)
Then, the number of cells for a given road is computed as follows:

Number o f cell = ceiling( road lenght Max cell spacing ) (7)
Where, road lenght represents the road length, the function ceiling(x) give an integer greater than or equal to x as expressed by equation 8.

ceiling(x) =              x i f x ∈ N N N INT (x) + 1 i f x ∈ R R R (8)
Finally, the cell size is given by:

Cell size = road lenght Number o f cell (9)
If we do not assume that the roads are straight, the connectivity will be better and we will have more cells (see Figure 5). In addition, since the radio links are straight, the nature of the road does not have an impact on the connection between vehicles. Except that the modelling of the obstacles cannot be generalised according to an analytical model, however in the part of simulations and following the model of mobility Manhattan Grid, the obstacles are taken into account, this can be reflected on the reality.

Road Traffic Information Packet

The RTIP is designed to store and transfer the roads traffic information. The format of RTIP is pictured in Figure 6, it consists of three parts: In this subsection, we aim to define the Link Connectivity (LC) of: two-consecutive vehicles, cell and road. Note that the lifetime of all these information is equals to 0.8 seconds and it is enough to ensure the validity of these information. Firstly, the LC between two consecutive vehicles measures the remaining communication distance between these vehicles. Consequently, two vehicles are connected as long as the remaining communication distance value is greater than zero, otherwise; the vehicles are not connected (LC = 0). The LC of two-vehicles can be expressed as:

LC nodes (v i , v j ) =              R tr -dist(v i , v j ), i f dist(v i , v j ) ≤ R tr 0 otherwise (10)
Where v i and v j depict the vehicle id i and j respectively, dist stands for distance and R tr is an abbreviation for range of transmission.

Indeed, the physical cell defines a group of vehicles. In this context, the LC of cell is related to the LC of its group members (vehicles), we therefore propose that the LC of a cell is the mean LC nodes of all consecutive vehicles within the cell. LC cell is defined as:

LC cell = N-1 i=1 LC nodes (v i , v i+1 ) N -1 (11)
Where N represents the number of vehicles within in the cell (cell density).

In the similar manner of Link Connectivity of cells, the road is composed of a set of consecutive cells, and by taking into consideration the connectivity inter-cells and the cell density which differs one from another. The completed road connectivity can be expressed as follow:

LC road = N cell i=1 (N i * LC cell i ) + N cell -1 i=1 LC inter (cell i , cell i+1 ) N cell i=1 N i (12) LC inter (cell i , cell i+1 ) = LC nodes (last v (cell i ), f irst v (cell i+1 )) (13)
Where LC inter (cell i , cell i+1 ) is the link connectivity between the last vehicle of cell i and the first vehicle of cell i+1 (the next cell).

Moreover, in order to compute the connectivity of a road with formula 12, we must have the connectivity and density values of all cells located in the road. For the reason of the good exploitation of spaces (e.g. packet size), we aim to compute the road connectivity in a progressive manner by using only two fields: previous cell connectivity and previous cell density, with this context, the road connectivity will be computed from cell to cell progressively as follow:

PLC i (i>1) = D i-1 PLC (i-1) + N i LC cell i + LC inter (cell i-1 , cell i ) D i (14)
Where:

                 PLC 1 = LC cell 1 D i (i>1) = D i-1 + N i = i j=1 N j D 1 = N 1
PLC i indicates Progressive Link Connectivity at cell number i, ( PLC i-1 for previous cells connectivity), D i indicates the previous cells density (the sum of density of all previous cells of the cell number i (the current cell density is included).

Finally, the road connectivity can be also expressed as:

LC road = PLC N cell (15)
We can demonstrate formula 15 by mathematical induction as follow:

• Base case: Show that the formula.15 true for N cell = 1.

-PLC 1 = LC cell 1 by definition (formula 14;

-LC road = 1 i=1 (N i * LC cell i ) + 0 i=1 LC inter (cell i , cell i+1 ) 1 i=1 N i = N 1 * LC cell 1 N 1 = LC cell 1
We see that base case is true for N cell = 1.

• Inductive step: Show that if formula.15 is true for N cell = n(n > 1), then also true for N cell = n + 1.

Using formula 14 for N cell = n + 1:

PLC n+1 = D n PLC n + N n LC cell n D n+1 + LC inter (cell n , cell n+1 ) D n+1 (a)
by assumption, LC road = PLC N cell is true for N cell = n, we have:

PLC n = LC road = n i=1 (N i * LC cell i ) + n-1 i=1 LC inter (cell i , cell i+1 ) n i=1 N i
by multiplying by D n , we have:

D n PLC n = D n n i=1 (N i * LC cell i ) n i=1 N i + D n n-1 i=1 LC inter (cell i , cell i+1 ) n i=1 N i (b)
We have D n = n i=1 N i by using definition of formula.14, by substitution D n in (b) we have:

D n PLC n = n i=1 (N i LC cell i ) + n-1 i=1 LC inter (cell i , cell i+1 ) (c)
by substitution D n PLC n in the right-hand side of (a) we have:

PLC n+1 = n i=1 (N i LC cell i ) + n-1 i=1 LC inter (cell i , cell i+1 ) D n+1 + N n LC cell n + LC inter (cell n , cell n+1 ) D n+1 (d)
As a consequence:

n i=1 N i LC cell i + N n LC cell n = n+1 i=1 N i LC cell i (e) n i=1 LC inter (cell i , cell i+1 ) = n-1 i=1 LC inter ( i , i+1 ) + LC inter (cell n , cell n+1 ) ( f )
by substitution (e) and (f) in the right-hand side of (d) we have:

PLC n+1 = n+1 i=1 N i LC cell i + n i=1 LCI( i , i+1 ) D n+1 (g) We have D n+1 = n+1 i=1 N i ,
by substitution D n+1 , (g) become:

PLC n+1 = n+1 i=1 N i LC cell i + n i=1 LC inter (cell i , cell i+1 ) n+1 i=1 N i = LC road (n+1)
The above calculation proves that formula.15 is true for

N cell = n + 1,
Finally, the base case and the inductive step have been performed by induction proofs, this allows formula.15 to be true.

Maintain and Share Road Traffic Information

Due the high dynamic nature of VANET networks, the topology changes frequently. Therefore, in order to enable the routing decision robust in such dynamic networks, it is very important to maintain a fresh and permanent road traffic information. For this reason we propose a distributed group information able to provide permanent road traffic information included within the RTIP packets. To ensure this property, each road is divided into a number of physical cells defining a group of vehicles (see Section 3.1.1). Each group elects a Group Leader (GL) (i.e. the closest vehicle to the cell center), we also propose that each RTIP packet must pass through all GLs belonging on the road as shown in Figure 7. Moreover, the GLs are mandated to update the RTIPs by including the information of its group (density, connectivity,...) at a fixed frequencies. In addition, since the vehicles are moving in both directions, transmission of route traffic information forwarding mechanism involves vehicles in both directions.

Partial Routing Algorithm

The proposed Partial routing protocol adopts anchorbased routing approach by using road traffic information, thanks to DRTI. Given that the RTIP packet can hold a number of roads information entry depending on the RTIP lifetime. Therefore, the forwarding node will have traffic information about a limited area of roads, in other words, the forwarding node has traffic information such as connectivity, density and road crossing delay about a set of roads which is stored in its Road Traffic Information Table (RTIT).

The proposed protocol is composed of two modules: Partial Path and Partial Path Forwarding Algorithm.

Partial Path

Based on the given traffic information, the forwarding node computes a partial path towards the destination according to algorithm 2.

Firstly, the forwarding node generate a graph G = (V, E) to represent the network, in which V and E represents a set of vertices (network junctions) and a set of edges (network roads) respectively. Moreover, each edge is weighed by the score function described as follows:

S core(road i ) = (16)              α(1 - LC road i R tr ) + β( delay(road i ) RT IP li f etime ), i f road i ∈ RT I table 1 otherwise
Where α and β denote the weight score (α + β = 1).

In equation 16, we tends to compute a score of a given edge in such way that the road score is lower as long as it has higher connectivity and lower delay. In the scenario where the given road does not belong to RTIT, the score is 1 (unknown road traffic information).

Secondly, we compute the shortest path from source position to destination position by applying shortest path algorithm (such as Djikstra algorithm) on a subgraph of the network where we consider only the non visited edges (we remove all visited edges by this current data packet), this is mainly to avoiding the routing loops.

Finally, the partial path is a subpath of the computed shortest path, whereby we keep only edges with known traffic information, in other words, we remove from the shortest path all edges with unknown traffic information (edges with score=1). Figure 8 shows an example of partial path.

Partial Path Forwarding Algorithm

In our proposed routing protocol, the packet-header composed of three essential fields: partial path stack, recovery path stack and visited roads stack. The routing with partial path is very simple as described in algorithm 1, following the scenario depicted in Figures 9 and10, where the source node S want to send data to the destination node D. Firstly the source node computes partial path and inserts it in the partial path stack. Then, by applying greedy forwarding approach the packets are forwarded by following all the junctions within the partial path stack in a sorted way, and when the data packet reaches an intermediate junction, we remove it from partial path stack and add it to recovery path stack. Moreover, we update the visited road stack for each crossed. When the data packet reaches the last junction of partial path (partial path stack becomes empty) (see node 4 in Figure 9), the current forwarding node computes a new partial path, and repeats the same process until the final destination is reached. In the other cases when we occur maximum local problem (the partial path forwarding fails) (see node 5 in Figure 9 ), we switch to Backward Forwarding Algorithm (described in Section 3.2.3). Figure 10 shows an example of backward recovery mode (see node 5 in Figure 10), when the packet reach maximum local problem, the current forwarding node uses recovery stack to go back to the previous junction, when the packet reaches a junction in which we can compute a new path from this junction to the destination, more then, this path should not contain any visited road. If that is the case, the routing switches to partial routing mode to forward the packet to the final destination. Figures 12a, 12b and12c show an example of forwarding data by using partial path forwarding algorithm, and we summarize the fundamental process of the proposed algorithm in the flowchart depicted in Figure 11.

Backwards Forwarding Algorithm

The Backwards Forwarding Algorithm serves as a recovery mode when the partial path forwarding algorithm occurs maximum local problem. Furthermore, for making our proposed routing protocol more suitable for Non-DTN, in our proposed recovery mode, we don't use any delayed process like Carry and Forward approaches. So, when we occur local maximum problem, the forwarding node adds the current road into visited roads stack and returns the data packet back to the previous junction by using recovery path stack and when the data packet has reached the previous junction, the current node computes new partial path. Partial path algorithm does not consider the visited roads in the path calculation, the previous road (where we occur local maximum problem) will not belong to the new partial path. In the case of the new partial path is empty, the forwarding node removes the current junction from recovery path stack and forwards the packet to the previous junction (front of recovery path stack). This process is repeated until we find non empty partial path, or in the other cases, if the previous junction not found (recovery path stack is empty) we will drop the data packet instead of carry forward in order to keep our protocol suitable for Non-DTN. We summarize the fundamental process of the Backwards algorithm in the flowchart depicted in Figure 13 and we give more details in algorithm 6.

Evaluation

In this section, we evaluate the routing performance of our proposed routing protocol PBRP compared to GyTAR and EGyTAR in terms of packet delivery ratio, routing overhead and end-to-end delay. The Packet Delivery Ratio (PDR) metric measures the ratio of the total received packets over the total packets generated from the source, End-to-end delay represents traveling duration for a packet from the source to destination, and the Routing Overhead is measured in terms of control packets size. We consider the size of CDP packets for both protocols GyTAR and EGyTAR and for our proposal protocol, the routing overhead takes into account the RTIP packet size.

In our simulation we use Manhathan Grid mobility model which describes the vehicles movement in a grid area of 1500x1500m composed of 16 straight roads and all these protocols are implemented on OMNET++ simulator.

Working environment

The routing performances of GyTAR, EGyTAR and our proposed protocol PBRP are evaluated using OMNET-5.0 simulator and INET-3.4.0 internet stack framework. We carry out the simulation results depending on the simulation parameters which are summarized in table 1, by running each scenario 10 times, so that, the results are averaged. We includes some obstacles Algorithm 1 : Partial Path Algorithm dst p = data packet .getDestinationPosition(); data packet.setPath(path); End of 1500x1500m which are described in an XML file. In addition, each vehicle has a digital map file to be aware about simulation environment. We also use Manhattan Grid mobility model to describe the movement of vehicular nodes in the simulation environment, Delictric Obstacle Loss Model for radio obstacle and 802.11p [START_REF] Jiang | 11p: Towards an International Standard for Wireless Access in Vehicular Environments[END_REF] protocol for MAC layer. The remaining simulation parameters are summarized in the Table 1.

Simulation Results

In this subsection, we present simulation results obtained for each protocol and compare them.

Packet Delivery Ratio

Figure 14 shows the packet delivery ratio depending on the number of vehicular nodes. As shown in this figure, the packet delivery ratio of all protocols increases as the network density increases, it is due to when the number of nodes increases, the forwarding node will have more chance to find the next hop. Furthermore, we clearly observe that our proposed protocol achieves if (V is RIN ∧ timer > 1sec) then for (all neighboring cells "cell n") do end if 19: end if 20: End higher packet delivery ratio continuously compared to that of GyTAR/EGyTAR. This is mainly because our proposed protocol uses an advanced vision and a permanent road traffic information thanks to DRTI, which makes our protocol able to avoid empty area in which the network is disconnected. Moreover, unlike the full path, the partial path has positive effects for data routing, it is also dynamic, flexible and practical for the dynamic networks such as VANETs, since it can be changed during the forwarding process as the network change by exploiting the variation of road traffic information. In other hand, our Backward recovery mode increases also the packet reception ratio, it serves to give another chance to forward data packet when the forwarding process occurs maximum local problem by forwarding-back the data packet and re-forwarding it through another path. However, GyTAR and EGyTAR show lower packet delivery ratio for the simple reason Algorithm 4 : Road Traffic Information Forwarding Algorithm End der to avoid the empty areas. Moreover, the initiation of CDP packets in the both protocols GyTAR/EGyTAR depends on the movement of the vehicles. This later is not regular all the time which means that GyTAR/EGyTAR can t harness the traffic information permanently.

End-to-end Delay

Figure 15 illustrates the average end-to-end delay. Generally, our proposed protocol shows lower delay than GyTAR/EGyTAR, the reason behind this is that when the maximum problem occurs, GyTAR/EGyTAR use Carry And Forward strategy which consists in holding the packet and carry it thereby increasing the delay. In the contrary, in our proposed recovery mode (Backwards Forwarding Algorithm) we don't use any delayed process as is described in 3.2.3, which would if (V around recovery path . f ront()) then if (next hop found) then end if 21: end if 22: End make lower forwarding delay. As shown in Figure 15, The end to end delay is not optimized before 200 nodes because of overhead generated by the dissemination of RTIP, when the number of nodes increases the number of RTIP transmissions increases which causes more delay.

Routing Overhead

Figure 16 illustrates the routing overhead measured in terms of total size of control messages (we consider CDP packets size for GyTAR/EGyTAR and RTIP packets size for PBRP). As shown in Figure 16, the overhead of all protocols increases as the network density increases, this is because as the number of nodes increases, the number of control packets increases. We observe also, when the number of vehicles is less than 170 vehicles, our proposal has lower routing overhead than GyTAR/EGyTAR. This can be explained by the fact that the lower density of vehicles make more blank spaces allowing the vehicles to move quickly. Since the initiation of CDP packet in GyTAR/EGyTAR depends on mobility of vehicles, the generated CDP increases as the number of vehicles which are leaving the roads increases. In the contrary, our proposal uses a regular dissemination of traffic information. However, when the network density becomes upper than 170 nodes, the routing overhead of PBRP shows higher values due to the effects of RTIP packets that tend to travel through multiple roads by providing an enhanced traffic information which helps the routing process to transmit more packets.

Conclusion and Future Works

In this paper we have proposed a new geographic routing protocol based on a distributed dissemination of road traffic information. This protocol provides a fresh permanent and advanced information about vehicular traffic included within the RTIP packets. We also have proposed a partial routing protocol that exploits the traffic information which is provided by DRTI to forward the data packets through partial connected paths. We have implemented and evaluated our proposal through simulations using OMNET++ simulator. The results obtained showed that our proposal exploits the traffic information in an efficient manner and provides significant performance in terms of packet delivery ratio, end-to-end delay and routing overhead compared to GyTAR/EGyTAR protocols due to the use of an advanced vision and a permanent road traffic information thanks to DRTI and recovery mode. As future works, we tend to optimize RTIP lifetime and RTIP initiation algorithm by using historical traffic statistics.

Figure 1 :

 1 Figure 1: Dissemination of Road Trafic Information

  ' are the projection of the points 'f' and 'g' respectively on segment [ae]. The yellow area represents the remaining area of the confluence of cells with the road, [ae] = 2R tr and [ce] = [eg] = R tr .

Figure 2 :

 2 Figure 2: Local Vision vs. Advanced Vision

Figure 3 :

 3 Figure 3: Cell Size: case1

Figure 4 :

 4 Figure 4: Cell Size: case2

Figure 5 :

 5 Figure 5: example of cell distance of curve road

1 . 3 .

 13 Static Header: Initialized just once by the RTIP Initiator Node (RIN), it consists of two fields: (a) Time-stamp: represents the initiation time of RTIP, (b) Source Junction ID: comprises the current junction ID of the RIN. In addition, these previous fields serve as an identifier of RTIP. 2. Dynamic Header: used by RIN and RTIP Broadcaster Node (RBN), unlike of static header, the dynamic header can be updated at each broadcasting process (described in Algorithm). The latter contains the information relevant to the next road which will be processed. It is composed of: (a) From Junction ID: represents the current junction ID of the forwarding node (RIN or RBN), (b) To Junction ID: denotes the destination junction ID, (c) Time-stamp: designates the start time of the broadcasting process. Roads Information: The most important part, it comprises the roads information entry, where each entry is created by a RBN (or by RIN for the initial RTIP). In addition, all entries contain the following fields: (a) Road ID: the current road identifier, (b) Road Connectivity: indicates the value of the road connectivity, it must be updated (following the Algorithm) at all Group Leaders (GLs) located in the current road, (c) Road Density: denotes the road density (the number of vehicles), (d) Delay: designates the time taken for a to through the current roads, (e) Time-stamp: represents the creation time of the road information table entry.

Figure 6 :

 6 Figure 6: Road Traffic Information Packet (RTIP)

Figure 7 :

 7 Figure 7: Road Trafic Information Forwarding Mechanism

Figure 8 :

 8 Figure 8: Partial path vs Shortest path

Figure 9 :Figure 10 :

 910 Figure 9: Partial path routing (1)

Figure 11 :

 11 Figure 11: Flowchart of Partial Path Routing Algorithm

Figure 12 :Figure 13 :

 1213 Figure 12: Example of partial path forwarding

7 :

 7 path = data packet.getPath(); 8: if (path = null ) then 9: path = PartialPath(sel f p, dst p, G, RT I t ); next j = path. f ront(); 16: if (distance(sel f p, next j) < R tr ) then 17: path.pop(); /* delete front junction */ 18: if (path not empty ) then 19: next j = path. f ront(); 20: else 21: path = PartialPath(next j, dst p, G, RT I t ); 22: next j = path. f ront();

Algorithm 3 :

 3 Periodic Road Traffic Information Initiation 1: Begin -V : Vehicle -rti p : Road traffic information packet -cell n : Neighbor cell -current j : The current junction of V -f irst j : The first junction of cell n -last j : The last junction of cell n -S H : The static header of rti p -DH : The dynamic header of rti p -RIN : Road Traffic Information Initiator Node 2: if (V around cross roads) then 3:if (V receive RIN initiation msg ) then

8 :

 8 rti p = new RT IPacket(); 9: rti p .S H.time stamp = currentT ime(); 10: rti p .DH.time stamp = currentT ime(); 11: rti p .S H.source junction = current j ; 12:

13 :

 13 rti p .DH. f rom junction = cell n. f irst j ; 14: rti p .DH.to junction = cell n.last j ; 15:Forward rti p to GL of cell n;

Algorithm 6 :

 6 Backwards Algorithm 1: Begin -data packet : The data packet -RH : The routing header of data packet -partial path : The partial path of RH -recovery path : The recovery path of RH -V : The forwarding vehicle 2: if (recovery path is empty) then

  recovery path . f ront());13:

Figure 14 :

 14 Figure 14: Packet delivery ratio

Figure 15 :

 15 Figure 15: End-to-end delay

Figure 16 :

 16 Figure 16: Routing Overhead

  N i receives data packet ; 3: if (data packet.destination ∈ neighbor t ) then

	1: Begin
		-path : The partial path (list of junctions)
		-data packet : The data packet
		-G : Network graph
		-N i : Node i
		-dst p : The Destination position
		-sel f p : The self position
		-neighbor t : The neighboring table
		-next hop : The next hop address
		-RT I t : Road Traffic Information Table
		-closest j : The closest junction to N i
		-next j : The next junction
		-R tr : The range transmission
	2: 4:	next hop = data packet.getDestinationAddress();
	5: else
	6:

  E S ub = {e|e ∈ E w ∧ e visited roads} 11: path f ull = getS hortestPath( f rom p, dst p, G w ); 12: for (all edges "e" ∈ path f ull ) do

		Algorithm 2 : Partial Path Algorithm
		1: Begin
			-path partial : The partial path
			-path f ull : The full path
			-G(V, E) : Network graph
			-G w (V, E w ) : Weighted network graph
			-G S ub (V S ub , E S ub ) : Subgraph of G w
			-RT I t : Road Traffic Information Table
			-visited roads : Array of visited roads
			-dst p : The Destination position
			-f rom p : from position
		2: for (all edges "e" ∈ E) do
		3:	if (e ∈ RT I t ) then
		4:	e.weight = S core(e, RT I t );
		5:	else
		6:	e.weight = 1;
		7:	end if
		8:	E w = E w ∪ {e};
		9: end for
		10: 13:	if (e.weight 1) then
		14:	path partial = path partial ∪ {e};
		15:	end if
		16: end for
		17: Return path partial ;
		18:
	25:	end if
	26:	next hop = getClosestNeighboreT o(next j);
	27:	end if
	28: end if
	29: if (next hop null) then
	30:	Forward data packet to the next hop;
	31: else
	32:	Store data packet and carry it;
	33: end if
	34: End
	defined by its shape, location and material in a grid area

  V receive rti p : 3: if ((currentT imerti p .S H.time stamp) > RT I l f ) then to j = rti p .DH.to junction; 12: f rom j = rti p .DH.to junction; 13: if (V is GL of current cell) then delay = current T imerti p .DH.time stamp; End that the Junction Selection Mechanism used in GyTAR and EGyTAR has a local vision of the network traffic and takes into consideration the traffic information for the candidate roads only and not for the next roads. This leads, in some cases, to forward the data packet in or-

	1: Begin -V : Vehicle -RT I l f : Road Traffic Information life time -GL : Group Leader 2: 4: delete rti p ; 5: Return; 6: end if 7: if (rti p is broadcast) then 8: Update RTI table following algorithm.5; 9: Return; 10: end if 11: 14: Update rti p following algorithm.6; 15: if (current cell is last cell) then 16: if (V is around to j ) then 17: Forward rti p to RBN; 18: else 19: Forward rti p to closest neighbor to RBN; 20: end if 21: else 22: Forward rti p to GL of next cell; 23: end if 24: else 25: Forward rti p to GL of current cell; 26: end if 27: if (V is RBN of to j) then 28: road id = getRoadID( f rom j , to j ); 29: 30: rti p .roadT able[road id].delay = delay; 31: Broadcast rti p around to j ; 32: for (all neighboring cells "cell n") do 33: rti p .DH. f rom junction = cell n. f irst j ; 34: rti p .DH.to junction = cell n.last j ; 35: Forward rti p to GL of cell n; 36: end for 37: end if 38: Algorithm 5 : PRP Algorithm 1: Begin -data packet : The data packet -RH : The routing header of data packet -partial path : The partial path of RH -recovery path : The recovery path of RH -visited roads : The visited roads of RH -V : The forwarding vehicle 2: if (partial path is not empty) then 3: next junction = partial path . f ront(); 4: if (V around next junction) then 5: recovery path .add(next junction); 6: partial path .pop(); 7: visited roads.add(current road); 8: if (partial path is empty) then 9: partial path = compute partial path following algorithm.2 10: end if 11: end if 12: next junction = partial path . f ront(); 13: if (next junction NULL ) then 14: next hop = getClosestNeighboreT o(next junction); 15: if (next hop found) then 16: forward data packet to next hop; 17: return; 18: end if 19: end if 20: end if 21: /* at this point, the path or the next hop was not found */ 22: RH.routing mode = Backwards Mode; 23: Switching to BackwardsRoutingAlgorithm; 24:

Table 1 :

 1 Simulation Parameters

	Parameters	Values
	Simulation time	100 Sec
	Beacon interval	0.5 Sec
	RTIP lifetime	0.8 Sec
	MAC protocol	802.11p
	Network area	1500x1500 m 2
	Transmission Range	250 meters
	Mobility model	Manhattan Mobility
	Vehicle speed mean	50 Km/h
	Channel capacity	6Mbps
	Number of intersections	16
	Number of roads	24
	Traffic model	UDPBasicApp
	Packet sending interval	0.2 sec
	Packet size	128 bytes
	Number of vehicles	50-400
	Radio obstacle loss model	Dielectric