Jarmo Saarti
email: jarmo.saarti@uef.fi

Jari Ropponen
email: jari.ropponen@xamk.fi

Satu Soivanen
email: satu.soivanen@xamk.fi

The Karjala database -challenges and solutions for digitizing heterogeneous, old genealogical documents for internet use

Keywords: digitization, genealogical documents, handwriting, Karelia, Finland

The Karjala database contains digitized demographic data of the parish registers from the regions ceded to the Soviet Union in 1944. The objectives of the digitization project have been to promote access to digitized records for scientific research and genealogy as well as encouraging research on the people of the ceded Karelia region. The main sources for the database have been catechetical lists, lists of children, and registers of vital statistics (registers of births, marriages, migrations and deaths) that are available in Digital Archives of the National Archives of Finland from the period of 1681 -1949. The data in the database amounts to about 10.3 million entries, but only data older than 100 years is published openly on the Internet. According to decisions by the Finnish data protection authorities, the Personal Data Act is applied to personal registers less than 100 years old. The digitization process is still going on; it has been calculated that there are 1.2 million entries still to be processed. The database is available to users via https://katiha.mamk.fi/. At present, there are about 6.5 million file entries available on the Internet, each presenting data about one individual, e.g. names, the date of birth and death, the cause of death, age, gender, marital status, occupation, residence, migration, the parish.

The Karjala database can be exploited for diverse research purposes; it improves access to the church records that are sometimes very difficult to read. Information in the database can be utilized for historical research, medical genetics, social sciences, and family and onomastics. The database is can be utilized for clarifying family structures, migratory patterns or child mortality. The database also offers excellent opportunities for interdisciplinary research. Our presentation will describe the digitization process management of old, handwritten documents that consist of non-structured data from a historical period that contains varied linguistic material: several languages from a historical period where nations, states and languages were still evolving, different calendars and spelling rules etc. We will also introduce our plans to use text recognition technology so that the handwritten documents such as the Karjala database will be incorporated into the international READ project network http://read.transkribus.eu/network/. We will also discuss the challenges encountered in this type of heterogeneous data and the possibilities for more defined and structured data management that could enable the automated use of the database. We will also include in our presentation a description of the evolution of the different phases of the database, emphasizing the evolution of the database and its linkage with internet technologies e.g. how they have either hindered or enabled the digitization project.

Introduction

Our paper will describe the digitization process management of old, handwritten documents that contain nonstructured data from a historical period that also contains a variety of linguistic material. During this historical period, several languages were used and it was also an era when nations, states and languages were still evolving, different calendars were in use in different regions and there was no consensus about spelling rules etc. We will also introduce our plans to use text recognition technology to digitize handwritten documents.

The Karjala database will cooperate with the international READ project http://read.transkribus.eu/network There are challenges in handling this type of heterogeneous data but with more defined and structured data management, it should be possible to exploit modern automation techniques to digitize the database. We will also describe the evolution of the different phases of the database e.g. how internet technologies have either hindered or enabled the digitization project.

The Karjala database contains digitized demographic data of the Finnish parish registers from the regions ceded to Soviet Union. This digitization project is intended not only to promote access to digitized records for scientific research and genealogy but also to act as a stimulus to research into the inhabitants of the ceded Karelia region.

The idea of storing the Karelian parish registers into a database was initiated by Raimo Viikki, now the past director of the Provincial Archives of Mikkeli. The pilot project started in 1988 as a research project. It examined how whether the Karelian registers suitable could be converted into a feasible database. The results of the pilot project were very successful and subsequently the Karjala Database Foundation was established in 1990. The database is owned by the Karjala Database Foundation; its members are: the city of Mikkeli, the Finnish Karelian League, the University of Eastern Finland, the University of Jyväskylä, the Finnish Ecumenical Council, the National Archives Mikkeli, the Genealogy Society of Finland and the Population Register Centre.

What is ceded Karelia?

Throughout history, Karelia (Karjala in Finnish) has been a beneficiary but also a victim of its location between the East and West. When the Russian czar, Peter I (the Great), founded the city of St. Petersburg (a.k.a.

Petrograd and Leningrad) in 1703, the security of the city became a major concern for Russia. When Finland became an independent nation and its borders with Russia were defined, the shortest distance from the border to the city, then called Leningrad, was a mere 32 kilometers. When World War II broke out, the Soviet Union feared that Germany would attack it also via Finland in the east. Therefore, the Soviet leaders demanded that part of Karelia should be ceded to Russia, a proposal totally unacceptable to Finland, resulting in the Soviet Union launching an attack on Finland on the 30 th of November 1939.

After two wars (1939-1940 and 1941-1944) with the Soviet Union, Finland was forced to cede Karelia officially as part of the Paris Peace Treatment in 1947.

As the map (fig. 1) shows, the ceded Karelia (red colour) was the South-Eastern region of Finland before the wars. As Finland was still an agrarian country at the beginning of the 20 th century, the citizens of ceded Karelia were mostly farmers. There was also an expanding wood processing industry i.e. before the wars Karelia housed about 25 % of Finnish pulp mills, because there were rivers for suitable generating power. A large proportion of the ceded Karelia consisted of water; half of Lake Ladoga (the largest lake in Europe) had belonged to Finland. In 1939, there were about 410 000 people living in that part of Finland (10 % of the total population); they were members of 50 Lutheran and 20 Orthodox parishes. After the wars, the people from the ceded Karelia moved to other parts of Finland (yellow in the map).

For comparison, there have been two major migrations from Finland; one to North America in the years 1881 -1914 when nearly 300 000 Finns emigrated to the United States and Canada. Another significant wave of emigration from Finland took place in the1960's, this time to Sweden due to the economic opportunities offered there, in that period about 300 000 persons (many of them from eastern Finland) moved to Sweden.

The Age of Sweden

Years 1100 -1809

Swedish county

Swedish regime begun 12th century, Finland was a Swedish county. People spoke Finnish, officials and upper class Swedish Sweden was active internationally, so there were many wars; also the Finns had to serve in the army Especially in 17 th century there were many years of famine (the Little Ice Age)

The Treaties of Tilsit (1807) between Russia and France: France gave Finland to Russia; after war in 1808 the Russians occupied Finland

The Age of Russia Years 1809 -1917

Autonomous position

Finland got an autonomous position in Russia Swedish language was still used by administration, in Karelia also Deutsch and Russia

Because Finland was out of wars, the land begun to develop many ways (industry, traffic, legislation etc.)

Between 1899-1917 the Russians tried to increase their influence in Finland ('russification')

The Age of Independence Since 1917

Independent nation

Finnish Government gave the independence declaration on 6.12.1917

Finland has been an independent nation since 1917

Two wars against the Soviet Union (during [1939][1940][1941][1942][1943][1944] Finland lost Karelia officially in Paris peace treatment in 1947

Background of the documents digitized

In Finland, the Lutheran parishes have kept registers since the 17th century. The instructions for the maintenance of registers came from Swedish church and priests used Swedish for recording the details. This was a normal custom since Swedish was the language of the ruling elite and officers. Nonetheless, in the Karelian region there have been also registers maintained by the Orthodox Church. This was because the Karelian people had lived close to Russia for centuries (fig. 2, The Age of Russia). 1883 Decree: Finning language got official position and parish registers changed from Swedish to Finnish 1895 Finnish Orthodox church (5 % of population belonged to it) founded its own diocese Orthodox church had also its own parish records, partly similar to Lutheran records; they were written in Russian until 1920's

The Age of Independence

The evacuation of the Karelian

Church Books

Although Finland lost Karelia the Karelian parish records were greatly saved

The documents and church books from the Karelian parishes (50 Lutheran, 20 Orthodox) were transported to Finland

The Karelian church books transported finally to Mikkeli, a city in the South-Eastern Finland

Figure 3. The main periods of the Finnish parish records.

The main bodies of the parish records are:

Birth Records: In the oldest lists of born and baptized, there are only details of the day of baptism, the child´s name, the father´s name and the family´s place of residence at the time of birth.

Marriage Records: The lists of banns and marriages have information: days of banns, the day of the wedding, the names of the bride and bridegroom, their social status and their place of residence.

Death Records: The lists of deaths and burials generally give the date of death, the date of burial, the name of deceased, social status, the place of residence, age and cause of death.

Records of Moving in and out: The lists of migrating persons usually contain the name of the person, the parish from where the person moved and the one to which he/she moved as well as references to a page in the main church book.

Catechetical Lists (so called Confirmation Register): The ecclesiastical code of 1686 decreed that it was mandatory to keep church records in every parish. The primary purpose of the confirmation books was to follow the parishioners´ literacy and Christian knowledge and monitor their participation in the communion. The notes in the confirmation register would often encompass a time span of 10 years.

Children´s lists: There were no guidelines regarding children´s books, so different parishes began to use these at different times. The oldest lists of children date back to the early 18 th century. Parish members under 15-years-old were recorded in the children's register and after their confirmation into the congregation; they were transferred to the confirmation register.

Resources for the database project -workers and funds

Three persons began to store the data into the Karjala database in November 1988. The amount of workers varied between three and seven. But fortunately in theyear 1995 the project got more workers, together 21 persons by the contract with the Finnish public employment and business services. So many long-term unemployed people got meaningful work for themselves (5 hours a day and 25 hours a week) and the Karjala database foundation got needed employees for storing the data. One operator worked normally for one year.

The project has had about 600 workers in these 29 years, annual numbers are presented in fig. 4.

Figure 4. The annual numbers of the operators in the Karjala database project.

During 2005 -2010, the number of workers was over 30. At the same time, the number of stored data entries was about 700 000 annually (fig. 5). At present, the data in the database consists of about 10.3 million entries, but only data older than 100 years is published on the internet. This is because the Finnish data protection authorities have decreed that the Personal Data Act protects personal registers less than 100 years old.

Figure 5. The annual numbers of the stored entries to the Karjala database.

The digitization process is still going on. It has been calculated that there are still 1.2 million entries to be processed. The database is available to users via https://katiha.mamk.fi/. At present, the files available on the internet amount to about 6.5 million entries. At the moment, over 10.3 million entries have been saved in the Karjala Database; the target for the year 2020 is that it should contain about 11.5 million entries.

Technical evolution of the database

The planning for the Karjala database system started in August 1988. The plan for pilot project was as follows:

Step 1: Description of source material (church books: what we have and in which form)

Step 2: Determination of need (technical solutions: what we want and how can we achieve this goal)

Step 3: Analysis of information (variables, relations, values, codes, key fields, exceptions, controls)

Step 4: System planning (model of the recording system)

Step 5: Coding the recording system The pilot project had many challenges to resolve some technical problems: how to choose and define the fields which are needed in the recording program and in the database itself and how to express and display the data which has changed with time. The information in different church books varies quite much, there are changes in data (shorter names, synonyms) and lack of data (incomplete birth dates, no definitive names) and language changes (Swedish, Finnish, Russian, German, Latin).

The original database was made with dBase, an old software (management) language. The planned system included six parts with their files: one part for each type of a church book (births 3 files, marriages 3 files, deaths 3 files, migrations 2 files, a book of children 7 files and a book of examinations 10 files). The planned database structure consisted of a total of 28 data files for each of the 70 Karelian parishes. In summary, there were together about 2000 data files in the database.

The original database environment was the dBase -server and mostly housed in the hard drives of computers and CD-ROMs. The dBase was an inexpensive and efficient choice in the 1980's, it suited this kind of research register. It was a spreadsheet type of a database management system but that means there was not any user interface. The backup of the database was arranged by storage on floppy disks. Although convenient at that time, this arrangement was not appropriate for future development. The server required extensive maintenance and simply keeping it running was time consuming. The database had to be divided into two different versions.

Figure 2 .

 2 Figure 2. The main historical periods of Finland.

  : DEMO AncestryAI (an application which uses machine learning to infer family trees and enables visualizing and searching the inferred trees. It has been developed to support genealogical research. AncestryAI includes data mining. http://ancestryai.cs.hut.fi/ The Karjala database is already widely used; it receives between 800 and 1200 Internet visits every day. The Statistical Reports from the beginning of January to the end of March showed the following numbers: the use of Katiha2 (the former online version of the program Katiha) 91,582 visits and the use of Katiha.mamk (the revised version of the database interface) 11,421 visits, i.e. 103,003 visits in 90 days i.e. about 1,144 visits per day.

Acknowledgements

The authors are grateful to Dr. Ewen MacDonald for linguistic advice and Seppo Rapo for the permission to use the map.

The Karjala database project has got financial support since 1988, the sum of money will grow up nearly to 9 million euro to the end of 2019. The main sponsor is the government (fig. 6), the support of the ministries of Employment and Education is about 82 % of the funds which the database project has got. Figure 6. The financial resources of the Karjala database.

The difficulties of recording parish records

All of the church registers are handwritten with ink and a pen. To help the reading of these old handwritten records, we have begun to examine if it is possible to exploit the international READ (Recognition and Enrichment of Archival Documents) -project. The Transkribus-software of the READ project tries to automatically recognize handwritten text (fig. 7).

Unfortunately, the software needs significant 'teaching' in order to manage old texts, but we are looking forward to improvements. (See also [START_REF] Blanke | Open Source Optical Character Recognition for Historical Research[END_REF]

Financial Resources

The script varies from time to time and from parish to parish. For this reason, the recording operators have to be talented in interpreting the texts. Since the language is mostly Swedish in Lutheran books and Russian in Orthodox books, the worker must have a good knowledge of these languages as well as Finnish. They also need to know about the history of the language, because many words and even concepts have disappeared.

Digitization process

The data is stored manually to the Karjala database (fig. 8). The digitization process contains lots of handwork of the operators. At first the data to the database was taken from the original church books. After that the microfilms of the Karelian church books used as the source material to the database. The use of handwritten copies of the parish registers has been one method to make the recording work easier. Nowadays the source material is on internet in the pages of Digital Archives of the National Archives of Finland. Today, when digitizing the old and disordered written registers, the staff team consists of experts, many of whom have recorded parish registers for years, almost everyone has graduated with an MA (humanistic sciences) and some speak Russian as their native tongue. In addition, the organization has access to a couple of advisors with special experience who undertake the analyses of the most difficult texts using a variety of sources (fig. 8). The ultimate goal is that the final database should not have many mistakes, e.g. wrong names, erroneous interpretation of an individual's personal details e.g. emigration, crimes, illnesses and the dates of birth, marriage and death.

Database for research and information use

The user interface to the database called Katiha https://katiha.mamk.fi/User.action?addLocale=en The Karjala database serves many different kinds of research and improves access to the church records that are sometimes very difficult to read for academics without a background in history. Information in the database can be utilized for historical research, medical genetics, social sciences, and family and genealogical research. The entries of the database presenting data from individuals e.g. name, the dates of birth and death, the cause of death, age, gender, marital status, occupation, residence, migration, the parish; so the database is optimal for investigating family structures, migratory movements or child mortality. The database also offers excellent opportunities for interdisciplinary research. Recently there have also been projects that have exploited data mining methods when analyzing the data. (See Räisä and Loponen 2014.)

The researchers could find data e.g. for questions of variations in fertility and mortality, changes in child mortality, causes of death and inherited diseases and the population age distribution in different parishes. The database is a source for statistics of migration for instance from where and to which parish the people have migrated or where did they find their husbands/wives. Researchers of social history can find answers to their interests: How did the industrialization influence professional titles and women´s work situations? Did the knowledge level notations in the confirmation books predict people's futures? How did the social position inherite through the generations in different groups in the community?

The Karjala database is an excellent aid for genealogists to research their family roots. There are data in the database for onomastics to research family names within an area or to research changes in family names within a certain period. Some examples of researches where the Karjala database has been used as a source material:

This solution was made when it was decided to allow access to the database on the internet. The Finnish law has defined that personal data can be made public when it is over 100 years old from an individual's birth.

However, the data of deceased people is public at 50 years from their death. The Karjala database foundation decided to resolve the privacy issue by dividing the database in two. The public data was accessible on internet and private data housed in the National Archives Mikkeli.

Version of database access in Windows -Katiha Version of database access on internet -Katiha1

Version of database access on internet -Katiha2 Version of database access on internet -Katiha Mamk Figure 9. The variety of user interfaces for the Karjala database access.

At present there are four ways to access the data of the Karjala database (fig. 9). This system has too many disadvantages with respect to preserving the data for research access. The objective is to develop the user interface so that there is only one access system and in an open source environment. The modernization will continue in the future in order to ensure an effective utilization so that researchers have easier access to the database.

The original database has already transferred to a new server managed by the South-Eastern Finland University of Applied Sciences. The server has a web service so that the public datadata over 100 years old is already now widely accessible. The system exploits MariaDB, an open source SQL-environment with the web service running on Java. Hopely these changes will allow the data of parish registers to survive so that it can be accessed by future generations in a format that can not only be read but also modified more easily. After the modernization of the database there are many possibilities to exploit it in other projects and develop an interface for versatile access.

Conclusions

The need for digitizing old genealogical resources gives rise to new possibilities, especially for digital research.

Data mining and data combination methods are completely new ways for expanding knowledge also in humanistic research. It also opens opportunities for other branches of research to utilize this data.

It seems that the older texts still need substantial manual processing and thus are expensive and timeconsuming projects. Our case shows that one must also be agile in project management and fundraising. From the point of view of research, it is very important that the original documents are also digitized because one cannot translate all the meanings of the old document especially when trying to make them readable with a machine. On the other hand, for the project leaders this means that their conduct must be critical and ethical: every step of interpretation can change the original meanings of the texts.

The parish registers are only one part of the information originating from ceded Karelia. More information about Karelian citizens is available from the archives of private persons and associations. Some of this information has been digitized and there might be the opportunity to access it. Linking all this data is clearly important but that would need a new project and substantial voluntary work. Some plans have already been made:

1. Integrating geographic information from different areas to the data.

2. Linking the statistical information with the geographic information system.

3. Including different kinds of data into the database, such as photographs, drawings and stories.

4. Connecting the data with the messages in social media.

As the digital realm opens, it offers new possibilities -it is our duty to include human history in this context (see also [START_REF] Parry | Historians Ask the Public to Help Organize the Past; but is the Crowd Up to it?[END_REF][START_REF] Cimtech | Crowdsourcing Project Helps Finnish Library to Digitise Historical Documents[END_REF]).


Cheikh Sarr

Isabelle Guérin

Lassous N°????

Isabelle Guérin Lassous

Estimating Average End-to-End Delays in IEEE 802.11 Multihop Wireless Networks

Keywords: Average end-to-end delay estimation, ad hoc networks, IEEE 802.11, Quality of Service Délai moyen de bout-en-bout, réseaux ad hoc, IEEE 802.11, Qualité de Service

In this paper, we present a new analytic model for evaluating average end-to-end delay in IEEE 802.11 multihop wireless networks. Our model gives closed expressions for the end-to-end delay in function of arrivals and service time patterns. Each node is modeled as a M/M/1/K queue from which we can derive expressions for service time via queueing theory. By combining this delay evaluation with different admission controls, we design a protocol called DEAN (Delay Estimation in Ad hoc Networks). DEAN is able to provide delay guarantees for QoS applications in function of the application level requirements. Through extensive simulations, we compare performance evaluation of DEAN with other approaches like, for instance, DDA.

Introduction

Using Voice-over-IP services in wireless mesh networks is becoming a reality [7]. Such VoIP applications are delay sensitive and require some delay guarantees. Offering and maintaining delay guarantees is a difficult task in wireless mesh networks and more generally in multihop wireless networks.

Recently, the works on quality of service (QoS) guarantees in ad hoc networks have attracted more and more attention. Most of these works assume that the underlying technology used in these networks is the IEEE 802.11 technology [START_REF]Local and Metropolitan Area Network -Specific Requirements -Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF]. This technology is widely available, not so expensive and provides a distributed radio medium access that can be easily used in an ad hoc network. On the other hand, the random radio medium access provided by IEEE 802.11 offers few control on the emissions and makes the radio medium sharing difficult in a multihop context [START_REF] Chaudet | Performance Issues with IEEE 802.11 in Ad Hoc Networking[END_REF]. Many works offer quality of service to IEEE 802.11based ad hoc networks by providing either throughput guarantees or delay guarantees or both. Among these studies, most of them have focused on throughput guarantees (like for instance [START_REF] Yang | Contention Aware Admission Control for Ad Hoc Networks[END_REF][START_REF] Chaudet | BRuIT -Bandwidth Reservation under InTerferences influence[END_REF][START_REF] Badis | QOLSR, QoS routing for Ad Hoc Wireless Networks Using OLSR[END_REF][START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]) and few of them have proposed solutions for delay guarantees.

If solutions for providing throughput guarantees are still not perfect, they are nonetheless more and more efficient. The complex radio medium sharing in IEEE 802.11-based ad hoc networks is better and better integrated in the QoS solutions. In turn, these solutions can provide accurate available bandwidth estimations and thus guarantee the throughput efficiently. Ensuring the delay seems to be a more challenging task. As mentioned in [START_REF] Yang | Achieving Delay Guarantee in Ad Hoc Networks by Adapting IEEE 802.11 Contention Windows[END_REF], it is very difficult to predict the expected delay due to the strong dependency between the flows in a wireless multihop setting. In this article, the authors claim that it is very difficult to design measurement-based admission control protocols for the delay parameter compared to the throughput parameter.

In this article, we propose a new protocol to achieve delay guarantees in wireless multihop networks. With this study, we show that it is possible to design an efficient measurementbased admission control protocol for the delay parameter. The proposed protocol, called DEAN (Delay Estimation in Ad Hoc Networks), is based on a a priori estimation of average end-to-end delay. This estimation is derived from a simple model of IEEE 802.11 nodes and from an accurate evaluation of each link's collision probability. By combining this estimation with accurate admission controls, the estimated delay is guaranteed after a new flow starts. Such guarantees depend mainly on a strong correlation between the estimated delay and the available bandwidth as an efficient estimation of available bandwidth. This latter is estimated with the protocol ABE (Available Bandwidth Estimation) that provides an accurate evaluation [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]. Moreover, our protocol DEAN is not costly in terms of overhead since it uses the control packets required for the estimation of the available bandwidth and provided by ABE and thus does not add any overhead. Finally, extensive simulations show that our protocol DEAN is very efficient to provide delay guarantees.

The remainder of this paper is organised as follows: Section 2 presents related work. Section 3 presents succinctly the protocol ABE used for available bandwidth estimation. Section 4 describes our end-to-end delay estimation mechanism. Section 5 describes the protocol DEAN and simulation results are presented in Section 6. Section 7 concludes our work. Finally, notations for the entire paper can be found in Appendix.

Related Work

One of the goals of VMAC [START_REF] Veres | Supporting Service Differentation in Wireless Packet Networks Using Distributed Control[END_REF] and SWAN [6] is to provide delay guarantees thanks to an admission control based on delay measurements. In [START_REF] Veres | Supporting Service Differentation in Wireless Packet Networks Using Distributed Control[END_REF], a mechanism for evaluating one hop delays in ad hoc networks is presented. This mechanism relies on an estimation of the channel occupancy. Let's consider that a specific node has monitored a channel occupancy equal to U during a measurement interval. If we denote by L the time to transmit successfully a whole packet on this channel, then the one hop delay d can be expressed by:

d = U × d + (1 -U ) × L
If the channel around the node is always free (U = 0), there will be no collision and the one hop delay is equal to the transmission time L. However, when the channel is busy due to close transmissions (U = 0), the parameter d , corresponding to the time spent in the exponential backoff procedure and for retransmitting a collided packet, is taken into account in the delay evaluation. If this approach is effective for a one hop network, it can lead to a false evaluation in presence of hidden nodes configuration: for instance, U can be equal to 0 for an emitter but its transmission can experience collisions due to a hidden flow.

With SWAN [6], the delay requirements of real-time traffic are achieved with a rate control of best effort traffic performed at every node in a distributed manner without keeping per-flow state information. Each node regulates its best effort traffic via an Additive Increase Multiplicative Decrease algorithm. If the delay of best effort packets becomes greater than a threshold delay, then the emitter considers that the network is congested and decreases the rate of best effort traffic it transmits. In [START_REF] Yang | Achieving Delay Guarantee in Ad Hoc Networks by Adapting IEEE 802.11 Contention Windows[END_REF], it is shown that SWAN provides delay violation while reducing the overall throughput in multihop networks. This is mainly due to a certain level of inaccuracy in the available bandwidth estimation.

DDA [START_REF] Yang | Achieving Delay Guarantee in Ad Hoc Networks by Adapting IEEE 802.11 Contention Windows[END_REF] is also a stateless protocol that provides average delay guarantees for QoS applications. Each node is modeled as discrete G/G/1 queue: it allows an evaluation under general traffic arrival patterns. The main contribution of DDA are the following: i) the modeling of the closed-form relationship between contention window size and the distribution of the delay of a flow in an unsaturated network; ii) the regulation of the contention window size is based on locally available information and iii) the contention window allocation converges to a steady state if such an allocation exists. To achieve these goals, DDA relies on some assumptions, some of which are quite restrictive in ad hoc networks. For instance, the end-to-end delay is evenly broken down into per-hop delay requirements, which is not necessarily the case in wireless multihop networks. Or minimizing the impact of collisions in the computation of the contention delay is correct in a single-hop cell but may lead to a high inaccuracy in a multihop network. Some other works model the delay on one hop link with queueing theory techniques, like for instance in [START_REF] Ozdemir | An M/MMGI/1/K Queing Model for IEEE 802[END_REF]. Most of these works base their analysis on the modeling of the IEEE INRIA 802.11 access channel performed by Bianchi [START_REF] Bianchi | Performance Analysis of the IEEE 802.11 Distributed Coordination Function[END_REF]. If these analysis work well in one hop cell where all the nodes are in a same communication area, it is not often the case in multihop wireless networks where collisions due to hidden node configurations can not be neglected. The goal of our work is to better integrate the features of ad hoc networks for achieving more accurate delay guarantees.

Available Bandwidth Estimation

For ensuring delay guarantees, our solution relies on an accurate available bandwidth estimation. Hereafter, we define the available bandwidth between two neighbor nodes as the maximum throughput that can be transmitted between these two peers without disrupting any ongoing flow in the network. This term should not be confused with the link capacity (also called base bandwidth) that designates the maximum throughput a flow can achieve between two neighbor nodes, even at the cost of other flows' level of service degradation.

For the available bandwidth estimation, we choose the protocol ABE (Available Bandwidth Estimation), first proposed in [START_REF] Sarr | A node-based available bandwidth evaluation in ieee 802.11 ad hoc networks[END_REF] and then refined in [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]. In [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF], the authors show that ABE is more accurate than many protocols with the same goal while requiring a small overhead. By considering the overlapping of the silence periods of both emitter and receiver of a link, the collision probability that exists on the link and the backoff window size correlated to this collision probability, ABE provides an accuracy in the estimation that is often not achieved by the other protocols.

As our delay estimation depends strongly on this available bandwidth estimation, this section is devoted to the description of ABE. Of course, we can not include all the details of ABE that is not the novelty of our proposition. The interested reader can refer to [START_REF] Sarr | A node-based available bandwidth evaluation in ieee 802.11 ad hoc networks[END_REF][START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]. For providing an accurate evaluation, some phenomena need to be taken into account when the IEEE 802.11 MAC protocol operates:

• Carrier sense mechanism prevents two close emitters from transmitting simultaneously.

Therefore, an emitter shares the channel bandwidth with all these close emitters. The channel utilization has to be monitored to evaluate the capacity of a node to emit a given traffic volume. As in many protocols, this channel utilization is computed by each node by monitoring the radio medium in its surroundings and measuring the total amount of time that is idle for emitting frames. Therefore, this method does not only take into account the bandwidth used in the transmission range of the nodes but also in the whole carrier sensing area.

• For a transmission to take place, both emitter and receiver need that no jamming occurs during the whole transmission. Therefore, the value of the available bandwidth on a link depends on both peers' respective channel utilization ratios but also on the idle periods synchronization. In [START_REF] Sarr | A node-based available bandwidth evaluation in ieee 802.11 ad hoc networks[END_REF], we propose a probabilistic method to estimate this synchronization. This estimation, for the link (s, r), is denoted E(b (s,r) ) in the following.

• No collision detection is possible in a wireless environment. Therefore, whenever collisions happen, both colliding frames are completely emitted, maximizing the bandwidth loss. It is thus necessary to integrate this bandwidth loss in the available bandwidth estimation. In [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF][START_REF] Sarr | Improving accuracy in available bandwidth estimation for 802.11-based ad hoc networks[END_REF], we provide an estimation of the collision probability on each link. This estimation combines two approaches: i) A on line approach that computes the impact of the medium occupancy distribution at the receiver side thanks to the collision probability on Hello packets. These Hello packets are used in many ad hoc routing protocols and are required for computing the previous estimation E(b) on each link; ii) A off line approach that takes into account the size of the packets sent by the source thanks to an interpolation. The goal of this last approach is to compute the collision probability that packets of known and fixed size will undergo on a link from the collision probability of Hello packets deduced from real measurements on the same link. This collision probability estimation is denoted p, in the following, and depends on the size of packets that will be sent.

• Finally, when collisions happen on unicast frames, the IEEE 802.11 protocol automatically retries to emit the same frame, drawing the backoff counter in a double-sized contention window. The time lost in additional overhead may also have an impact on the available bandwidth. In [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF][START_REF] Sarr | Improving accuracy in available bandwidth estimation for 802.11-based ad hoc networks[END_REF], we compute the mean backoff according to p the collision probability computed in the previous estimation. It is then possible to deduce the proportion of bandwidth consumed by the backoff mechanism. This proportion is denoted by K in the following.

These different estimations are then combined to estimate the available bandwidth on a wireless link, i.e. between an emitter s and a receiver r:

E f inal b (s,r) = (1 -K) • (1 -p) • E b (s,r) (1)

Mean delay estimation

Delay indicates the time to send a packet from a source to a destination node. Contrary to bandwidth, delay is an additive metric. Thus, the delay along a path is equal to the sum of the delays on the one-hop links of this path. With the use of IEEE 802.11, the mean packet delay on a specific one-hop link, denoted by D, can be divided into three parts:

• The mean queueing delay which represents the interval between the time the packet enters in the queue of the link's emitter and the time that the packet becomes the head of line packet in this node's queue. We denote it by D q .

• The mean contention delay is the interval between the time the packet arrives at the head of line and the time the packet is sent to the physical medium. We denote it by D c . This interval reflects the fact that a node may contend to access to the channel because of other transmissions in its carrier sensing area.

INRIA

• The mean transmission delay is the time to transmit the whole packet including possible retransmissions in case of collisions. We denote it by D t .

Therefore we have the relation:

D = D q + D c + D t (2)
In the remainder of this section, we made some assumptions in order to simplify the analysis and to give an analytical expression for (D q + D c ) and secondly for D t .

Assumptions

We model a IEEE 802.11 node as a discrete time M/M/1/K queue. The properties of this queue are:

• The packet arrival follows an exponential law of parameter λ.

• The service rate follows also an exponential law of parameter µ.

• The size of the queue is limited by the value K. When a new packet arrives and if there are already K packets in the queue, then this one is dropped.

• The queue is a classical FIFO (First in First Out).

We assume no use of RTS and CTS messages. The analysis can be easily extended for the cases where such messages are present. The parameter λ represents the number of packets arriving in the queue per second which depends on the application throughput (if such an application exists on the node) and the traffic routed by this node. The service rate µ represents the number of packets leaving the queue per second.

General idea

Our initial goal is to provide delay guarantees to delay sensitive flows. To this end, we need to estimate the mean delay that the packets of such a flow will achieve before transmitting this flow. Therefore, we need to estimate the service rate that can be offered to this flow on each node passed through by this flow. It is also important to remind that the acceptance of a new flow may impact the delays of existing flows. Our goal is then also to minimize such an impact in order to achieve the delay guarantees of existing delay sensitive flows. As for the available bandwidth estimation (see Section 3), we could define the available service rate of a node as the service rate that can be offered to a new flow without increasing the delay of any ongoing flow in the network.

In order to limit the impact on the mean delay of existing flows, a congestion control must be realized. Therefore, the service rate that can be offered by a node to a new flow is directly correlated to the residual bandwidth seen by this node. This residual bandwidth is equal to the medium occupancy seen by this node (including its own transmissions) multiplied by the capacity of this node. This value captures the effect that after the queuing process, a packet which arrives at the head of line of the MAC layer should wait until the channel is free in order to gain the access. More precisely, we model µ res , the service rate that can be offered to a new flow, as the available bandwidth computed by the node rescaled in packets per second.

Estimating the mean queueing and the contention delay

In this section, we estimate D q +D c . When µ > λ, the service rate of the node is higher than the arriving process and there will be no accumulation in the queue involving a queueing and a contention delay which are null.

µ > λ =⇒ D q + D c = 0
When µ ≤ λ. Let's denote by p(n) the probability to have n packets in the queue (n ≤ K). A packet arrives with rate λ and exits with rate µ. So:

p(n) = λ µ × p(n -1) = λ µ n × p(0) Using ρ = λ µ =⇒ p(n) = ρ n × p(0)
The sum of the probabilities being equal to 1, we can simply express p(n) in function of ρ and K:

p(n) =          ρ n 1 -ρ 1 -ρ K+1 if ρ = 1 1 K + 1 if ρ = 1
The mean number of packets Q in the queue is therefore:

Q = K n=0 n × p(n)
Using queueing theory and according to Little's law, the parameter D q + D c is equal to the mean waiting time:

(D q + D c ) = Q λ
So the final expression is:

D q + D c =          ρ 1 -ρ 1 -(K + 1)ρ K + Kρ K+1 1 -ρ K 1 λ if ρ = 1 K 2λ if ρ = 1 (3)

INRIA

We can also notice that, since the queue size is bounded, D q + D c is bounded by a maximum value D max such as:

D max = lim ρ→+∞ (D q + D c ) D max ≈ K × ρ K+2 ρ K+1 × λ
As λ = ρ × µ we have:

D max ≈ K µ (4)
In this estimation, the contention delay only considers the time spent until the medium is free in order to gain the access to the radio medium to send the packet for the first time. We do not consider here the time that may be required to retransmit the packet. This time is included in our transmission delay, described in the next subsection.

Estimating the mean transmission delay

The mean transmission delay is the time to transmit the whole packet. In IEEE 802.11 DCF, when this operation is successful, a positive acknowledgement is sent back to the emitter. However, there is a chance, even for a single frame that when a packet is emitted, the medium is not idle at the receiver's side, provoking a collision. These collisions involve retransmissions of the same packet and increases the contention window size, all these phenomena resulting in an increase of the mean transmission delay.

Modeling the exponential backoff mechanism

As it has been mentioned in Section 3, we have already proposed in our protocol ABE ( [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]) a mechanism to estimate the collision probability on each link.

Let us consider that an arbitrary wireless link suffers from collisions with a probability p (evaluated with the method given in [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]). For every frame, the transmission is successful at the first attempt with probability (1-p). It succeeds at the second attempt with probability p • (1 -p). After C unsuccessful attempts, C depending on the frame size, the IEEE 802.11 standard specifies that the frame should be dropped.

If we denote by X the random variable representing the number of attempts performed for the correct transmission of a given frame, we have:

P (X = k) =    p k • (1 -p) if k ≤ C p k if k = C + 1 0 if k ≥ C + 1
The expected number of retransmissions n for a given frame can be expressed as follows:

n = +∞ k=1 k • P (X = k) = C+1 k=1 k • P (X = k) n = C k=1 k.p k (1 -p) + (C + 1)p (C+1)
Now, we need to compute the expected backoff that impacts the delay transmission. First, let us consider that there is no collision. Then the backoff is drawn according to a uniform law in the interval [0; CW min -1], CW min being determined by the MAC protocol specification. On a large observation window, the backoff can be approximated by its average value CWmin-1 2 . When collisions happen, the exponential backoff mechanism is triggered. After each unsuccessful transmission, the contention window size is doubled up to a maximum value denoted by CW max . In this situation, the average backoff value increases way above CWmin-1 2 and it is necessary to model the time consumed by the exponential backoff process.

The expected number of backoff slots decremented until the end of transmission attempts for a single frame is therefore:

backof f = +∞ k=1 P (X = k) • min(CW max ; 2 k-1 • CW min ) -1 2
To simplify the expression, let us suppose that

CW max = 2 c • CW min with c ≤ C: backof f = c k=1 P (X = k) • 2 k-1 • CW min -1 2 + C k=c+1 P (X = k) • CW max -1 2 backof f = 1 -p 2 • 1 -(2 • p) c 1 -2 • p • CW min + p c -p C 1 -p

Mean transmission delay computation

The different points mentioned above can be combined to estimate the mean transmission delay on a wireless link, i.e. between an emitter and a receiver. To summarize, the mean transmission delay between two neighbor nodes can be estimated by the following formula:

D t = backof f .T slot + n-1 k=0 T c + T m INRIA D t = backof f .T slot + n. T c + T m (5)
where T m is the time to successfully transmit a whole packet of m bytes with IEEE 802.11, T c is the collision duration, n is the mean number of retransmissions depending on collision probability, backof f is the expected number of backoff slots and T slot is the duration of a slot.

To sum up, the mean delay D of a one-hop link consists of:

• the mean delay experienced by a packet on the link's emitter (= D q + D c ). It corresponds to the waiting time before the first transmission of the packet;

• the mean delay experienced by a packet during the transmission (= D t ). It includes the potential retransmissions induced by collisions. 1

The protocol DEAN

As our goal is to ensure delay for delay sensitive flows, we integrate the previous evaluation technique of the mean delay into a protocol. This protocol is called DEAN for Delay Estimation in Ad hoc Networks.

The protocol part, i.e. the setting up and maintenance of reservations, does not include any new or specific feature. It is based on broadcasted route request messages, admission control at each intermediate node and explicit reservation by a unicast route reply message issued by the destination. Our delay estimation requires an available bandwidth estimation. We use the technique designed in the protocol ABE (Section 3), since the obtained results show a high level of accuracy ( [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF]). The congestion control mechanism required to minimize the impact on the delays of existing flows will then be based on the available bandwidth estimation of ABE and will be performed via an admission control on bandwidth.

DEAN: Delay Estimation

In DEAN, neighboring nodes exchange their delay information through Hello messages. Every ∆ seconds, each node locally estimates its medium occupancy ratio and includes this information in a Hello packet. The medium occupancy allows DEAN to estimate the available service rate µ res .

Hello-based techniques generate additional overhead depending on the Hello emission frequency. Ideally, the frequency ∆ of Hello packets should be adapted to the nodes mobility and/or to the flows dynamics. The larger ∆, the more stable the measurements, hiding fast variations in the medium load. However, ∆ should also be small enough to allow fast reactions to long-term load variation and to nodes mobility. In this protocol version of DEAN, we choose, in order to have meaningful comparisons, to fix this value to ∆ = 1 second. Similarly, all compared protocols are tuned accordingly to emit one information frame each second.

DEAN: Admission control and QoS routing

The DEAN routing protocol is a cross-layer routing protocol. The MAC layer of each node estimates proactively and periodically the mean delay of the neighboring links and the routing layer is in charge of discovering QoS routes complying to the applications demands, basing their decisions on the MAC layer result. We try to provide routes for which the end-to-end delay specified by the application level is higher than the mean value estimated along the path. Let's consider a path composed of K hops. The delay constraint can be expressed by the following inequality:

K-1 i=0 D(i; i + 1) ≤ D appli (6)
where D appli is the end-to-end delay specified by the application level and D(i; i + 1) is the one-hop delay between intermediate neighbor nodes i and i + 1 on the path (0

≤ i ≤ K -1).
The routing process of DEAN is strongly inspired by AODV and consists of two major parts: route discovery and route maintenance.

Route discovery

The aim of the route discovery procedure is to find a route between the sender and the receiver that meets delay constraints specified by the application level. Therefore, two flows with the same source and destination can follow different routes depending on the network state.

DEAN performs on-demand route discovery like in AODV. When a source node has data to send, it broadcasts a route request (RREQ) to its neighbors. The RREQ packet contains the address of the sender, the bandwidth and delay requirements at the application level, the destination address, a sequence number and the cumulative delay computed along the path. Each mobile that receives such a RREQ performs three admission controls:

• The first one ensures that Equation 6 is still verified. The computed delay corresponds to the sum of the cumulative delay given in the RREQ packet and of the estimated delay on the link from which the RREQ packet is received. To estimate this latter, we use λ the throughput requirement of the application and µ res the service rate that can be offered to the application by the link's emitter. The service rate that will serve the application on this node corresponds to min(λ, µ res ).

INRIA

• The second one ensures that throughput of the flow to be emitted (deduced from the service rate computed at the previous step) will not be degraded by close flows.

• The third one ensures that the emission of this flow on this link will not degrade the throughput of close flows which are in hidden nodes configuration. These two admission controls are performed in ABE [START_REF] Sarr | Improving Accuracy in Available Bandwidth Estimation for 802.11-based Ad Hoc Networks[END_REF] and we re-use them in DEAN.

Figure 1 represents the cross-layer mechanism and the different admission controls performed in DEAN. If all these controls are positive, the node adds its own address and its mean delay to the cumulative delay of the route and then forwards the RREQ; otherwise it silently discards the message. Finally, when the destination receives a first RREQ, it sends a unicast route reply (RREP) to the initiator of the request along the reverse path. The resources in terms of service rate offered to this flow at each node are then reserved and the new QoS flow can be sent.

Route maintenance

A route maintenance process is essential, especially in case of mobility. We implemented a simple detection and reaction mechanism. DEAN detects a broken route by monitoring the Hello messages. If a node does not receive any Hello packet from a neighbor within a certain time interval (equal to the time to transmit 3 Hello packets in the evaluation part), or if one of its link does not meet the reserved delay any more, it sends a route error (RERR) to the source which subsequently rebuilds its route.

Finally, it is interesting to note that DEAN, as it is described here, only guarantees the mean delay to applications. With slight modifications on the admission control phases, it is possible to guarantee both throughput and delay requirements.

Performance evaluation

In this section, we evaluate and compare, by simulation, the performances of our solution with other approaches. We use the network simulator 2 (NS-2.27)2 and the IEEE 802.11 implementation provided with the simulator.

The parameters used for all scenarii are presented on Table 1. Unless specified, the queue of each node (K) can contain at mot 100 packets of 1000 bytes. We compare the performances of our delay estimation technique through the DEAN protocol described above with DDA [START_REF] Yang | Achieving Delay Guarantee in Ad Hoc Networks by Adapting IEEE 802.11 Contention Windows[END_REF]. We chose DDA because it is one of the most recent solutions that outperforms several measurement-based admission control protocols like SWAN for instance. As DDA relies on any existing protocol for throughput guarantees 3 , we have integrated DDA in ABE. Thus, the comparison between DDA and DEAN is focused on the delay estimation and the delay guarantee since these two approaches are based on the same bandwidth admission control and the same available bandwidth estimation. We also compare DEAN with AODV as a baseline for comparison.

Parameters Values

First results

To compare the different protocols and illustrate the effectiveness of DEAN to provide end-to-end delay guarantees, we generate random topologies with random constant bit-rate flows (random source, random destination and random throughput with fixed 1000 bytes frames). For each of these protocols, similar scenarios (same number of nodes and same number of flows) lead to similar behaviors. Therefore, for this section, we give the results of one scenario and the presented results are obtained over 30 simulation runs with different random seeds. The scenario consists of a static network involving 20 randomly positioned nodes. The channel capacity is set to 2 Mb/s. We distinguish two particular cases:

• In the first case, the three delay-sensitive CBR connections are competing with five best effort CBR flows as background traffic.

• In the second case, these three delay-sensitive CBR connections are now competing with five best effort FTP flows as background traffic.

For each flow, the source is randomly chosen and the destination is also randomly chosen.

The throughput of each delay-sensitive connection is uniformly drawn between 100 kb/s and 300 kb/s and the end-to-end delay requirement is fixed to 50 ms. The background traffic is first started (their throughput is also uniformly drawn between 100 kb/s and 300 kb/s).

Then the delay sensitive flows are started every two seconds. Table 2 gives bandwidth and end-to-end delay requirements for the three delay-sensitive flows.

Accuracy of the estimation

Let us now investigate more scenarii. To evaluate the accuracy of the end-to-end delay estimation in several scenarii, we use the following metric:

α = n N
where n is the number of packets that don't experience delay violation and N is the total number of packets correctly received. We consider that a packet, for which the end-to-end delay may be higher than 5% of the delay requirements when it is emitted, experiences a delay violation. This metric reflects the fact that a falsely admitted flow either degrades delay of close flows or is not able to achieve its own desired end-to-end delay. We measure the value of α by simulation on networks composed of 10 to 40 nodes. The radio medium capacity is of 11 Mb/s. Each simulation lasts 100 seconds and three random sources try to establish delay-sensitive CBR connections towards three random destinations. These three CBR connections are competing with 5 best effort CBR flows, started at the beginning of the simulation. The throughput of each connection is uniformly drawn between INRIA 100 kb/s and 300 kb/s and the end-to-end delay requirements is fixed to 50 ms for all delaysensitive flows. In the following, we evaluate the values for α in function of three parameters: the used protocol; the queue size and the number of delay-sensitive flows 4 . All the results presented below are the average of 30 simulations with different random seed. When the network is not too loaded, α is relatively high for both DEAN and DDA (respectively about 92 and 86% for 10 nodes). By increasing the density of the network, we see that DEAN is more accurate on delay guarantees than DDA. For example, when there are 30 nodes, the value of α is about 79% for DEAN and 61% for DDA. DDA proposes a stateless approach, meaning that no estimation of residual resources are carried out. Each node of DDA regulates dynamically the contention window size in function of its local perception of close transmissions. This regulation is also based on some assumptions. The obtained results let us think that some of these assumptions are maybe too strong, especially when the density of the network increases. Indeed, when the density becomes higher, more collisions may appear involving packets retransmissions. Moreover, the delay on a path may very probably not evenly broken down among the hops of this path. Therefore, DDA handles less efficiently these collisions in the delay evaluation than DEAN. In all cases, the performances of DDA and DEAN are better than AODV for which no admission control and regulation are done. Influence of queue size: Figure 4(b) shows the values of α in function of the queue size of all nodes in the network. Increasing the queue size decreases the value of α. For example, for a density of 10 nodes, α is equal to 97% for a queue size of K =10 and 87% for a queue size of K =1000. It can be explained by the fact that, with small queues, the queueing delays will be smaller as the variance in delay. Therefore, the delays are more stable when nodes have small queues.

Value of K

10 100 1000 % of dropped packets 3.1 5. [START_REF] Chaudet | BRuIT -Bandwidth Reservation under InTerferences influence[END_REF] 7.3

Table 3: % of dropped packets in function of queue size Surprisingly, the rate of dropped packets also decreases with K as shown in Table 3. Here the results are the average of 30 simulations. These results tend to show that the stability in delays is important for α and for the rate of dropped packets and that DEAN is more efficient with a low value for K. Influence of the number of delay-sensitive flows: For this evaluation, the number of nodes is fixed to 20. We increase gradually the total number of delay-sensitive flows from 5 to 20 and compute the values of α. As shown on Figure 4(c), for DDA, α decreases when the number of delay-sensitive flows increases. Actually, DDA only performs an admission control on bandwidth but not on delay and the regulation performed by DDA becomes more and more difficult when the total amount of traffic increases in the network. Therefore, these results show that an admission control on delay that eliminates potential routes is of some interest when the network becomes loaded. For example, when there are 20 delay-sensitive flows, α is equal to 85% for DEAN and 55% for DDA. This part illustrates the scalability of DEAN.

Overhead

Routes establishment and reconstructions require messages exchanges (RREQ, RREP and RERR packets). We evaluate the overhead introduced by AODV, DDA and DEAN which gives an indication on the convergence speed of the routing mechanism and on its stability. The tested random topologies consist of 20 nodes and 5 delay-sensitive flows competing with 5 CBR background traffic. We compute the overhead generated in the network, expressed in total number of exchanged control messages (RREQ, RREP and RERR packets) by all the nodes in the network. 4 represents the total number of control messages exchanged for the routes setup and maintenance. Results are the average of one hundred simulations performed for each protocol. DDA an DEAN generate less overhead than AODV since the admission control phase eliminates routes that can not meet application requirements in term of bandwidth and end-to-end delay. Hence, the admission control reduces significantly the number of INRIA route request packets forwarded in the network. Moreover, AODV suffers from a lot of routes breakages and performs many route reconstructions. These extra requests increase the overhead. We can also see that DEAN generates lower overhead than DDA because in DDA, just one admission control on bandwidth is performed while for DEAN, this admission control on bandwidth is combined to an additional end-to-end delay admission control, leading to fewer route requests propagated in the whole network.

Protocols

Conclusion

In this article, we propose a technique to evaluate a priori the delays that flows will achieve in a wireless multihop network. By combining this technique to admission controls based on available bandwidth and on delay, we design a protocol DEAN that can guarantee delays to delay sensitive flows with a high level of accuracy. Simulations compare the performance of AODV, DDA and DEAN and show that, under different configurations, DEAN is able to provide strict guarantees.

In the future, we plan to work towards three main directions. First, in the presented study, we haven't considered the co-existence of delay sensitive traffic and best effort traffic. If, in simulations, some best effort flows were present, they were transmitted before the starting of delay sensitive flows. Our solution is based on an admission control that ensures that congestion will not appear. It is therefore important to take care that best effort flows started while delay sensitive flows are transmitting will not impact the delays of these latter. To be efficient, it will be also important to let the possibility to use the whole bandwidth to best effort traffics if no delay sensitive flows are transmitted. In [START_REF] Khalfallah | Dynamic bandwidth management for multihop wireless ad hoc networks[END_REF], we have already designed a mechanism to ensure the co-existence between best effort flows and bandwith sensitive flows. We plan to extend this approach to delay sensitive flows. Second, we plan to merge the different QoS solutions we have designed in order to provide a unique solution that will handle best effort traffic, bandwidth sensitive traffic and delay sensitive traffic. Our goal is to provide accurate guarantees while using the bandwidth efficiently. Finally, we plan to test our solution with real delay sensitive applications, like for instance, VoIP applications. Other mechanisms like VoIP packet aggregation and header compression, as mentioned in [7], should also be considered.

A Notation

Here are the different notations used in the paper:

Figure 1 :

 1 Figure 1: Cross-layer and admission controls in DEAN

FlowTable 2 :

 2 identity Throughput (kb/s) End-to-end delay (ms) Bandwidth and end-to-end delay requirements for delay-sensitive flows end-to-end delay of 50ms (c) DEAN

Figure 2 :

 2 Figure 2: End-to-end delay obtained by AODV, DDA and DEAN for delay-sensitive flows and CBR flows as background traffic

Figure 3 :

 3 Figure 3: End-to-end delay obtained by AODV, DDA and DEAN for delay-sensitive flows and FTP flows as background traffic

  Value of α in function of queue size for DEAN Value of α in function of the number of delay-sensitive flows

Figure 4 :

 4 Figure 4: Values of α

1 .

 1 λ: number of packets arriving per second 2. µ: number of packets leaving per second 3. ρ: ratio between λ and µ 4. K: maximum queue size 5. D: mean delay on one hop RR n°0123456789

Table 1 :

 1 General parameters for simulations

	HELLO interval	1 s
	Packet size	1000 bytes
	Radio medium capacity	2 or 11 Mb/s
	Communication range	250 m
	Carrier sensing range	550 m
	Grid size	1000 m×1000 m
	C (Number of retransmissions)	6

Table 4 :

 4 Total number of control packets Confidence interval Routes establishment and maintenance-related messages overhead Table

	AODV	1248	1206 -1290
	DDA	584	553 -615
	DEAN	368	342 -394

RR n°0123456789

Note that for simplicity in the writing, the time spent in DIF S and in the backoff decrease before transmitting the packet for the first time is included in the transmission delay and not in the contention delay, as the definition lets think. Of course, if the reader thinks that it is more appropriate to include this time in the contention delay, a simple shift can be realized.RR n°0123456789

http://www.isi.edu/nsnam/ns/

no protocol is specifically proposed in[START_REF] Yang | Achieving Delay Guarantee in Ad Hoc Networks by Adapting IEEE 802.11 Contention Windows[END_REF].INRIA

In this last case, the number of delay sensitive flows will not be three.RR n°0123456789