Christian Retoré

On the system F as a glue language for natural-language compositional-semantics Du système F comme langage d'assemblage pour la sémantique compositionnelle du langage naturel

Afin de modéliser dans un cadre compositionnel des phénomènes de pragmatique lexicale comme ceux étudiés par [6, 15] et plus particulièrement par Nicholas Asher dans [1], notre équipe a utilisé dans divers travaux [2, 12, 14, 13] le système F de Jean-Yves Girard (1971) [7, 9] pour construire les formules logiques représentant le sens des énoncés -là où d'autres auteurs comme [10] utilisent plutôt la théorie des types (1984) de Per Martin-Löf. [11] Nous expliquons dans cette note les raisons de notre préférence.

Qu'est-ce que le système F? Introduit dans [START_REF] Girard | Une extension de l'interprétation de Gödel à l'analyse et son application: l'élimination des coupures dans l'analyse et la théorie des types[END_REF], (une bonne référence est [START_REF] Girard | Proofs and Types[END_REF] -en anglais et disponible sur Internet -une autre est [START_REF] Girard | Le point aveugle[END_REF]), ce système est la logique propositionnelle intuitionniste du second ordre. On y quantifie sur les propositions: on prouve des formules du genre ∀p (p → p) → (p → p) noté Πp. (p → p) → (p → p) et les preuves s'écrivent comme des termes avec un Λp terme représentant la règle de quantification sur les types (introduction du Π p cidessus), par exemple: Λp. λf p→p λx p f (f (x)) qui est du type Πp. (p → p) → (p → p) -la variable de type sur laquelle on quantifie ne doit pas être libre dans le type d'une variable libre. Symétriquement, un terme générique u de type Πp. T [p] peut être spécialisé sur un type A: le terme correspondant s'écrit u{A}, et il est de type T [A]. Par exemple si u trie de liste de p-objets pour tout p, u{A} trie des listes de A-objets. La beta réduction usuelle sur λ est (λx T . u)t T u[x := t] mais celle sur Λ fait pareil: (Λα. u){T } u[α := T ].

What is system F? Introduced in [START_REF] Girard | Une extension de l'interprétation de Gödel à l'analyse et son application: l'élimination des coupures dans l'analyse et la théorie des types[END_REF], (a good reference freely available on the Web is [START_REF] Girard | Proofs and Types[END_REF] and another is [START_REF] Girard | Le point aveugle[END_REF]), this system is intuitionistic second order propositional logic. In this system one can quantify over propositions and can prove formula like ∀p (p→p)→(p→p) written Πp. (p→p)→(p→p) and proofs are written as terms with Λp denoting the rule introducing quantification over types -the type variable over which one quantifies should not be free in the type of a free variable. Symmetrically, a generic term u de type Πp. T [p] can be specialised to a type A: the corresponding term, which is of type T [A] is denoted by u{A}. For instance, if u sorts lists of p-objects for all p, u{A} sorts lists of A-objects. Usual beta reduction concerns λ: (λx T . u)t T u[x := t] but beta reduction on Λ works just the same:

(Λα. u){T } u[α := T ].
Capacité expressive On remarque facilement que la quantification universelle sur les types permet de définir toutes sortes d'opérateurs de constructions de types, notamment les plus courants, en particulier:

• le produit cartésien de deux types A × B ≡ ΠX.(A → (B → X) → X • la quantification existentielle sur les types ∃pA[p] ≡ Πq. (Πp. (A[p] → q)) → q • les booléens ΠX.X → X → X • les entiers ΠX.(X → X) → (X → X)
• les listes d'objets de type α: ΠX.X → (α → X → X) → X

• ... d'où son succès pour ML, CaML etc.

On peut représenter toutes les fonctions récursives totales dont on peut prouver la totalité dans l'arithmétique de Peano du second ordre (qui pour ce genre d'énoncés coïncide avec l'arithmétique de Heyting).

Expressive power Universal quantification over types let you define lots of type constructors, including the common ones, in particular:

• cartesian product A × B ≡ ΠX.(A → (B → X) → X • existential quantification over types ∃pA[p] ≡ Πq. (Πp. (A[p] → q)) → q • booleans ΠX.X → X → X • integers ΠX.(X → X) → (X → X)
• lists of objects of type α: ΠX.X → (α → X → X) → X

• ... hence its success with ML, CaML etc.

A way to characterise is expressive power is to say that in this system one can define exactly all the total recursive functions whose totality can be proved in second order Peano arithmetic (classical or intuitionistic it makes no difference).

La The glue logic has no relation with the logic used for formulating semantics The system F (intuitionistic second order propositional logic) is used as a glue language, but it glues whichever formulae one likes. and it can be first order formulae -eventhough one uses second order quantifications, these are unrelated languages. A result in the PhD of Bruno Mery [START_REF] Mery | Modélisation de la sémantique lexicale dans le cadre de la théorie des types[END_REF] garantees that when λ-calculus constants are the ones of first (resp. n, ωorder logic, the normal λ-terms of F of type t are formulae of first (resp. n, ω) order logic. This is close to usual Montague semantics where simply typed λ-calculus (intuitionistic propositional logic) with two base types e and t is used to express and to glue formulae of first order logic, n order logic and even ω order logic.

Sous-typage Comme j'en ai parfois fait la remarque, le sous-typage est plus ou moins incompatible le système F malgré diverses tentatives comme [START_REF] Cardelli | An extension of system F with subtyping[END_REF]. Mais je ne suis pas sûr que le sous-typage au sens de la programmation fonctionnelle soit ce dont on a besoin pour la sémantique dans le style de [START_REF] Pustejovsky | The generative lexicon[END_REF][START_REF] Asher | Lexical Meaning in context -a web of words[END_REF] Subtyping As I sometimes said, sub-typing is more or less incompatible with system F despite some attempts like [START_REF] Cardelli | An extension of system F with subtyping[END_REF] But I am not sure that subtyping in its functional-programming meaning is what we are looking for when dealing with the semantic questions of [START_REF] Pustejovsky | The generative lexicon[END_REF][START_REF] Asher | Lexical Meaning in context -a web of words[END_REF]. A typed calculus with subtyping automatically derives inclusions between complex types from inclusions between base types. We should wonder whether it is semantically sound that inclusions between complex types like a → b are all the ones derived from inclusions on a and inclusions on b. For instance, I am not sure that subtyping on verb types derive from their arguments, subject, object, etc. Does classifications of "food"and "eaters" provide a classification of "eating" verbs ( swallow, taste, appreciate)? I do not think so. We are rather looking for an independent "subtyping" mechanism for each type (or type family) and this kind of subtyping has nothing to do with the standard notion subtyping at work in functional programming. One can even observe that language does not allow all the ontological inclusions and that it is not so clear that the idiosyncratic linguistic inclusions define an order. Quantifying over types is great At least, it is useful. In particular we have a single universal quantifier, that is specialised, and not one per sort. Without the Λ one would need ∀ a : (a → t) → t for every type T , including the complex types. Here, one is enough: ∀ : Πa. ((a → t) → t), then it is applied to a type T to obtain the quantifier over T objects: ∀{T } : ((T →t)→t). (One can even have a constant ∀ : Πa. t, without type raising). Similarly one can have a "there exists", a "most of" that are specialised to every particular type. The very same trick can be used for Hilbert's ǫ and τ selecting an object satisfying a property as soon as there is one -we already used it, for instance, in the virtual traveller τ : Πa. ((a → t) → e). [START_REF] Moot | Un calcul de termes typés pour la pragmatique lexicale[END_REF][START_REF] Moot | A discursive analysis of itineraries in an historical and regional corpus of travels[END_REF] We use transformations and instantiations on complex types, for instance to turn a path into a traveller following it, into an event, etc. For instance, as above, we can operate on the type raising:

Intérêt
(path → t) → t qui devient ((human → t) → t.
Questions de complexité En syntaxe avoir une classe de grammaires la plus petite possible permet d'avoir des algorithmes d'analyse plus performants. En sémantique, il n'en est rien: que doit faire au minimum la logique d'assemblage? on n'en sait rien... mais si on le savait cela améliorerait-il la complexité algorithmique de l'analyse sémantique? Non, pas du tout! Ce sont plutôt les choix des différents "sens" de chaque mot qui rendent le processus complexe. Le processus d'analyse est l'analyse syntaxique que vous préférez (et là il y a des questions de complexité), puis on construit un λ-terme avec les λ-termes sémantiques du lexique (un choix dont la complexité ne saurait être améliorée) et les règles syntaxiques, et on le réduit, et bien évidemment on n'a pas de beta réduction problématique -par exemple nécessitant un nombre exponentiel d'étapes de beta réduction en fonction de la longueur du terme à beta réduire.

Complexity issues

In syntax, having a class of grammars as restricted as possible, allows more efficient parsing algorithms. In semantics, it does not make sense: what is the minimum that the glue logic should do? No one knows, but even if this was known, would it help to reduce the algorithmic complexity of semantic analysis? Not at all! The complexity is rather due to the choice, for each word, of its relevant meaning among the possibilities provided by the lexicon. The process of analysis is simply syntactic analysis, and the syntactic analysis of a phrase can be the one you prefer (here is a complexity issue), then a λ-term is constructed following the syntax with the chosen semantic λterms from the lexicon (a choice whose complexity cannot be improved), then it is reduced and obviously the reduction is unproblematic -one does not get a term whose number of reduction steps is exponential with respect to the length of the term.

Comparatif entre la théorie des types de Martin-Löf et le système F pour la sémantique Certains, comme Zhaohui Luo [START_REF] Luo | Contextual analysis of word meanings in type-theoretical semantics[END_REF], utilisent plus volontiers la théorie des types de Martin-Löf (TT) dont il existe plusieurs variantes, l'une des premières étant [START_REF] Martin-Löf | Intuitionistic Type Theory[END_REF]. Une discussion avec un expert des deux systèmes, Thierry Coquand (qui a étendu F ω aux types dépendants, pour faire le calcul des constructions [START_REF] Coquand | The calculus of constructions[END_REF] et qui depuis près de vingt ans travaille sur TT) a achevé de me convaincre: comme logique d'assemblage il vaut mieux choisir le système F pour sa simplicité formelle (4 règles) et conceptuelle (une seule sorte de type, un seul genre de jugements), car on n'a aucun problème de complexité dans la réduction -comme dit plus haut, on ne va pas chercher les fonctions à croissance ultra rapide du système F pour assembler des formules. Si on prend une version faible de TT, celle-ci est, du point de vue des fondements -reconnaissons-leplus simple. La normalisation des termes du système, permet d'établir sans trop de peine la cohérence du système (s'il existait une preuve du faux il en existerait une qui soit normale, et on peut voir assez facilement qu'il n'y en a pas). Pour TT il faut le schéma de compréhension (qui permet de définir un ensemble à partir d'une formule {X|P (X)} pour les formule P i 1 1 c'est-àdire pour les formules de la forme "Pour tout ensemble X Il existe un ensemble Y ..." tandis que pour F le schéma de compréhension pour toutes les formules.

Comparing Martin-Löf 's type theory and system F for semantics Some, like Zhaohui Luo [START_REF] Luo | Contextual analysis of word meanings in type-theoretical semantics[END_REF] rather us Martin-Löf 's type theory (TT), a system with several variants, and early one being in [START_REF] Martin-Löf | Intuitionistic Type Theory[END_REF]. A converging discussion with an expert in both, namely Thierry Coquand (who extended F ω to dependent types, yielding the calculus of constructions [START_REF] Coquand | The calculus of constructions[END_REF], working with TT for twenty years) achieved to convince me: as a glue logic, system F should be preferred, because of its formal complexity, because of its conceptual simplicity (a single sort of types and a single sort of de judgements), because we have no complexity in reduction -as earlier said, we are not going to use extremely fast growing functions and the like when glueing formulae. If one uses a weak variant of TT, this system is admittedly simpler as far as foundations are concerned. Indeed, coherence is derived from normalisation (if there were a proof of a false statement, there would be a normal proof, but it is easily seen that there cannot be a normal proof of something false). For a weak variant of TT, the comprehension axiom (which defines a set {X|P (X)} from a formula P ) is needed for every Π 1 1 formula P (formulae like "for every set X there exists a set Y ....."). For system F the comprehension axiom is needed for every formula.

Records et types dépendants Quant au type de données populaire records, il s'agit simplement d'un produit (définissable dans dont on nomme les projections, un peu comme les attributs d'une base de données. Ils peuvent aussi se voir comme un cas particulier d'une famille d'ensembles indexée par un autre ensemble. Ce sont alors donc des types dépendants particuliers, et certains pensent que, d'une manière générale, les types dépendants sont utiles à la sémantique compositionnelle, ce qui, personnellement, ne me saute pas aux yeux. Néanmoins, pour les inconditionnels des types dépendants, ou si quelqu'un en montrait l'utilité, on peut les ajouter au système F. On peut même les ajouter à F ω ce qui donne un système bien connu: le calcul des constructions de Coquand-Huet, implémenté dans l'assistant de preuve Coq. [START_REF] Coquand | The calculus of constructions[END_REF][START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF] Records and dependent types Regarding the popular data type known as "records", they are just products with named projections, a bit like attributes in a data base. They can be viewed as particular indexed family of sets. Hence they are particular dependent types, and some thinks that dependent types are relevant for compositional semantics, also personnally I am not convinced. In any case, if one is keen on dependent types, or if one show they are useful at semantics, they could be added to system F. They can even be added to F ω yielding a famous system: the calculus of constructions of Coquand-Huet, implemented in the Coq proof assistant. [START_REF] Coquand | The calculus of constructions[END_REF][START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF]


Milenko Jorgić
email: mjorgic@site.uottawa.ca

Ivan Stojmenović

Michaël Hauspie
email: michael.hauspie@lifl.fr

David Simplot-Ryl
email: david.simplot@lifl.fr

Localized algorithms for detection of critical nodes and links for connectivity in ad hoc networks

Ad hoc network normally has critical connectivity properties before partitioning. The timely recognition is important in order to perform some data or service replication. Several existing centralized or globalized algorithms declare an edge or a node as critical if their removal will separate the network into several components. We introduce several localized definitions of critical nodes and critical links, using topological or positional information. A node is critical if the subgraph of k-hop neighbours of node (without the node itself) is disconnected. We propose three definitions of critical links, based on verifying common k-hop neighbours, loop length, and critical status of link endpoints, respectively. The experiments with random unit graph model of ad hoc networks show high correspondence of local and global decisions. For instance, in experiments with 500 nodes in connected random unit graphs, over half of locally estimated critical nodes and links were indeed globally critical even for k=1 (the accuracy increases to over 70% for k=2 and over 80% for k=3), for average number of neighbours ranging from 3 to 15. The errors mostly occur when alternative routes exist but are relatively long, and therefore may not provide satisfactory service in applications. Therefore our localized protocols provide faster and often more reliable partition warnings for possible timely replication decisions.

Introduction

An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any fixed infrastructure. They have potential application in civilian and military environments such as disaster relief, conference, wireless office, and battlefield.

Ad hoc sensor networks for monitoring environment are also being deployed.

In an ad hoc network a message sent by a node reaches all its neighbouring nodes that are located at distances up to the transmission radius. A widely accepted basic graph-theoretical model for ad hoc networks is a unit graph model, defined in the following way. Two nodes A and B in the network are neighbours (thus joined by an edge) if and only if the Euclidean distance between their coordinates in the network is at most R, where R is the transmission radius which is equal for all nodes in the network. Due to the limited transmission radius, the routes between two nodes are usually created through several hops.

A node or link is critical if its removal will disconnect the graph into two (or more) separate components. Suppose we have a user E and a server L (see Figure 1.). When user E requests a service or data from L, the request follows the path ECBAIJL. In this example, nodes A, B and J, and link AB, are critical, since removal (or movement) of any of them will partition the network. Node E may initiate some actions, such as replicating data from L in its own memory, or look for alternative service in different part of network, before it is too late.

Figure 1. Unit graph representation of multi-hop wireless network DFS (depth first search algorithm) was used to detect critical links in [DBS, T, GC]. It is a centralized algorithm, and can be also implemented in globalized distributed manner. A centralized algorithm requires that a node should be aware of global topology. In practice, this method is inefficient and involves a quadratic (in number of nodes) communication overhead in order to update link information when nodes are moving, or when nodes change their status from active to sleeping and vice versa. In a globalized distributed implementation, DFS can be performed in the network without global knowledge at any node, but with memorization at nodes. In [GC] once critical links in an ad hoc network are detected, two ways are proposed to delay or avoid their failure: changing the trajectory of one or both nodes forming the critical link and bringing another node to reinforce the link. Increased delivery rates were reported due to prolonged network connectivity. However, the communication overhead due to running DFS for detecting critical links was not measured. In this article, we propose to apply localized algorithms instead of globalized ones for partition detection. Localized algorithms are distributed in nature and resemble greedy algorithms, where simple local behaviour achieves a desired global objective. In a localized algorithm for detection of critical links each node makes a decision to determine critical nodes or links based only on limited local knowledge.

The purpose of this article is to show that, with high probability, possible partition can be detected by localized algorithms, therefore greatly reducing communication overhead and the speed of detecting, allowing network to replicate data or service in time if needed. The paper is organized as follows. We describe the existing work on critical links and node detection in Section 2. In Section 3 we propose and evaluate localized algorithms for detection of critical links/nodes and compare our localized algorithms with the known global algorithm. Finally, we conclude our work in Section 4.

Literature Review

Critical nodes and links are only considered for a connected graph (or separately for each connected component of a graph). A node A is critical if its removal will disconnect the graph into two components. A straightforward algorithm for detecting critical nodes may consider, for each node A, the subgraph obtained by its removal and removal of all its adjacent edges, and testing whether this subgraph is connected. If it is not connected, the corresponding node A is a critical node. As a consequence, node that has only one neighbour is not critical (e.g. node N in Fig. 1).

A faster global algorithm for detecting critical nodes was described by Duque-Anton, Bruyaux, and Semal [DBS], Tarjan [T], and Goyal and Caffery [GC] who used DFS. It is a centralized algorithm which can be also implemented in globalized distributed manner. While executing DFS on an undirected graph, we start at an arbitrarily chosen node which becomes the root. We keep traversing fresh edges and mark nodes as "visited"; on the way we keep pushing nodes into a stack data structure. This process is continued until we reach a node which is only connected to already visited nodes. At this point we keep backtracking up to a vertex which has edges connecting them to nodes which have hitherto not been visited. With a little thought it can be seen that such a node will always be a critical node of the graph. Alongside the identification of the critical node, it is easy to pop the downstream nodes from the stack into a set which corresponds to a bi-connected component. Since the above steps can be executed during DFS in the same pass, identification of critical nodes takes only linear time.

Critical links can de defined in several ways. One possible definition is that a link AB is critical if both endpoints A and B are critical nodes. However, two critical nodes may have alternate path between them. For example, in Fig. 4, nodes O and Q are critical, but alternate path between them exits via node P. It is therefore better to define critical link as the link connecting two critical nodes so that, when this link is eliminated from the graph, the graph becomes disconnected.

In [GC], once critical links in an ad hoc network are detected, two ways are proposed to delay or avoid their failure: changing the trajectory of one or both nodes forming the critical link and bringing another node to reinforce the link. Increased delivery rates were reported due to prolonged network connectivity. However, the communication overhead due to running DFS for detecting critical links was not measured. Karumanchi, Muralidharan, and Prakash [KMP], Li, and Rus [LR], Vahadat and Becker [VB], Park and Corson [PC] attempt to improve the communication without avoiding or delaying partitioning ('post-partitioning' approaches).

Hara [H] proposed three replica allocation methods to improve data accessibility by replicating data items on mobile hosts. The first method is to make a lot of replicas at each node, while the two others begin with a step in which each mobile host periodically broadcasts its host identifier and information on access frequencies to data items. After all mobile hosts complete their broadcasts, every host knows its connected mobile hosts. This partition detection method clearly requires a lot of communication overhead.

Wang and Li [START_REF] Wang | Efficient and guaranteed service coverage in partitionable mobile ad hoc networks[END_REF][START_REF] Wang | Group mobility and partition prediction in wireless ad hoc networks[END_REF] proposed a mechanism to allow servers in an ad hoc network to detect the future partitions and to replicate them in each predicted partition. However, this solution uses a strong centralized approach to detect partitions (their algorithm captures the network mobility information using pattern recognition technique in the velocity space, so that the time and location of network partitioning can be predicted) and its applicability as such may be questionable.

Hauspie, Simplot and Carle [HSC] proposed to evaluate stability of a path from a source to destination by a function that depends on disjoint path between them, and the hop distance of each of these paths. When the function reaches a threshold, data or service replication is performed.

The protocol has a significant communication overhead for evaluating the function.

Koskinen [K] examined critical transmission ranges for biconnectivity and triconnectivity of ad hoc networks. He experimentally established an asymptotic behaviour that these types of critical links can be determined by a function which is square root of the ratio of area and linear function of number of nodes (coefficients of that function are parameters to be determined).

Hajiaghayi, Immorlica, and Mirrokni [HIM] considered the problem of assigning transmission power to nodes so that the sum of powers is minimized and the network is kconnected. They use energy cost d α for transmission between two nodes at distance d (α is a constant between 2 and 6) and the algorithms are globalized. To guarantee k-connectivity, [BHM] uses a solution where most nodes need to have 3k or more neighbors, by enforcing minimal angle between two selected neighbors.

Shah, Chen, and Nahrstedt [SCN] aimed at enhancing data access in an ad hoc network by detecting partitions in it. They propose a data replication mechanism based on partition detection for allowing one node to access the data from another node even if the connection is physically broken. Each node of a connected group knows the behavior of other members in a group, because each node embeds a positioning system (GPS) by successive measures computes its velocity, and spreads that information to the other nodes. Due to this information, it is possible to predict when a node will leave its group. The 'node-to-leave' picks another node of the group to be a host of the data and performs a data replication on that node. The main advantage of this method is that each node knows exactly when the partition occurs (regular node movement is assumed, without sudden changes in direction). However, this method has two main disadvantages. First, a positioning system is needed. Second, the network is continuously and relatively highly loaded due to information exchange among nodes. While general ideas in [SCN] are good, the essential details are missing. The definition of group of nodes is not given, and one can even assume the whole connected network to be a group, since it also satisfies the vague definition given. The protocol for predicting link breakage, based on predicting future locations and connectivity of two nodes, is described in detail (a similar protocol was described earlier by Stojmenovic, Russell and Vukojevic [SRV]) but there is no description of any protocol to detect group partitioning; it was left up to a node to decide without giving details on how it is actually decided.

Li and Rus [LR] propose an approach in which nodes actively modify their trajectories to transmit messages. They develop algorithm that minimize the trajectory modifications under two assumptions: the movements of all the nodes in the system are known and not known, respectively.

In cooperative caching, discussed by Cao, Yin and Das [CYD], data from server are replicated on some nodes in ad hoc network so that access demands by other nodes can be satisfied by replicated files rather than original files, which should reduce traffic in the network or even provide service if the server becomes disconnected in the meanwhile. The described methods include caching data paths toward replicated copy by current node, or making another copy of data at the node, plus some hybrid method based on some criteria.

Localized algorithms for partition detection

Distributed and dynamic nature of the adhoc networks requires the design of localized algorithms to address scalability, robustness and energy efficiency issues. Localized algorithms that we have developed discover all critical nodes and links very quickly. However, these algorithms may detect some nodes and links as critical although they may not be globally critical. This is unavoidable since local knowledge only is used, therefore with such restriction it is impossible for a node to learn about alternate connections in different parts of the network. On the other hand, in applications, often long alternate paths do not provide satisfactory service, thus localized method may even provide more useful decision. Moreover, the partition detection is done faster and with much less communication overhead.

We first define what is the local knowledge available to nodes and how nodes gain it. We use the notion of k-hop knowledge. Two nodes are considered to be k-hop neighbours if and only if the shortest route between them has k or less hops. Awareness of itself only is represented as 0-hop knowledge. This may or may not include geographic position of the node. Localized algorithms that use position information can only be applied on nodes that are equipped with GPS or find their relative coordinates by measuring signal strengths or time delays in mutual communication. Nodes collect k-hop knowledge by sending 'hello' messages to its neighbours containing the graph of their (k-1)-hop neighbours. Thus 1-hop knowledge is a list of direct neighbours, with or without their geographic positions. We refer to these cases as being topological and positional information, and corresponding knowledge as being k-hop topological or k-hop positional information, respectively. The 2-hop topological information is obtained by transmitting lists of 1-hop neighbours, and the subgraph of 2-hop neighbours therefore includes existing links between 1-hop neighbours, and between a 1-hop and a 2-hop neighbours, but not possible links between 2-hop neighbours. On the other hand, 2-hop positional information includes such links and information, since node learns the position of 2-hop neighbours and may, based on distances between them and the unit graph used, decide whether or not they are neighbours. Generalizing this, k-hop topological information, and corresponding subgraph of k-hop neighbours, include all existing links between a khop and a (k-1)-hop neighbours, but not information on whether or not two strictly k-hop neighbours (that is, two nodes which are k-hop but are not (k-1)-hop neighbours) are connected. Since the information about any node in the positional case includes its position, in case of khop positional information, such information is additionally available. Therefore, localized algorithms with position information have more information than localized algorithms with topological information, and are consequently more accurate; they discover less falsely detected critical links and nodes. Furthermore, if a node/link is declared critical by a local algorithm that uses position information, it is also declared as critical by the localized algorithm that uses the corresponding topological information. The reason is that the graph may only have fewer edges and thus the partition detected by positional information cannot be 'sealed' by the corresponding topological information.

We shall now describe our localized algorithms for detecting critical nodes and links. In each of topological and positional cases, we give one definition of critical nodes and three definitions of critical links. The three definitions are based on verifying common neighbours, loop length, and critical status of link endpoints, respectively.

Localized algorithms for detection of critical nodes

For each node A, consider subgraph of khop neighbours of A, where A and all its incident edges are excluded. In case of positional information, two nodes in that graph are connected if they are connected in the original graph. In case of topological information, two nodes in that graph are connected if they are connected in the original unit graph, and at least one of them is (k-1)-hop neighbour of A.

A node A is k-critical node if the corresponding subgraph of k-hop neighbours of A is disconnected. Based on information used, this is further specified as being topologically or positionally k-hop critical node. The corresponding algorithms are referred to as being k-top_critical_node and k-pos_critical_node algorithms.

Clearly, if a node is globally critical, localized algorithm will detect it as such. Further, if a node is not declared as critical by k-top_critical_node algorithm it is also not declared as critical by k-pos_critical_node algorithm. That is, if a node is declared as critical by k-pos_critical_node algorithm it is also declared critical by k-top_critical_node algorithm. We will now discuss particular cases and give some examples as illustration. For k=1, if topological information is used, no links between neighbours exist in the decision graph, therefore all nodes are declared critical with 1-top_critical_node algorithm. This is obviously not very helpful.

Figure 2 illustrates the localized definitions of critical nodes. 1-hop neighbours of A can be divided into two sets {B, C} and {E,F} (circled in Fig. 2) which are disconnected. Therefore A is positionally (and therefore topologically) 1-hop critical. Node A is not 2-hop critical since its 2-hop neighbour D will connect two sets. Node M is 1-hop critical since its 1-hop neighbours K and N are not connected. However, it is not 2-hop critical since its two hop neighbours K, N, and L create a connected subgraph (marked by a rectangle in Fig. 2), both topologically and positionally. Node G is topologically 3-hop critical since its 3-hop neighbours are divided in two subgraphs with vertices {H, Z, D} and {J, Y, X, Q, P} (the two sets are enclosed by polygons in Fig. 2) which are disjoint. However, when position information is added, node G can recognize that X and D are in fact neighbors, and that two subgraphs are in fact connected, therefore X is not positionally 3-hop critical.

Localized algorithm for detection of critical links based on common k-hop neighbours

If topological information is used, the algorithm, referred to as k-link_top_critical algorithm, applies the following criterion. AB is a critical link if the sets of k-hop neighbours of A and B (assuming that the link AB does not exist) are disjoint. For k=1, this reduced to the following 1-link_top_critical algorithm: AB is critical link if A and B have no common neighbours (that is, there is no node C so that both AC and BC are in the unit graph).

If position information is used, the corresponding k-link_pos_critical algorithm is defined as follows. AB is a critical link if the sets of k-hop neighbours of A and B (assuming again that the link AB is removed first from the graph) are disjoint, and there are no two nodes, one from each set, which are neighbours. For k=1, the criterion is that A and B have no common neighbours that are within transmission range of each other (that is, neighbours).

Localized algorithms for detection of critical links based on loop length

In this section, we introduce critical links definitions which are based on finding the length of shortest loop between two link endpoints. A link UV is k-loop_critical if the hop distance between U and V in the given graph, with only edge UV being eliminated, is >k. There are several possible implementations of this definition, since a common decision should be made between two nodes, link endpoints. In general, we can consider k U -hop neighborhood of U and k V -hop neighbourhood of V, k U +k V =k. If topological information is used, the algorithm is defined as follows. A link UV is (k U ,k V )-loop_top_critical if the sets of k U -hop neighbors of U and k V -hop neighbors of V are disjoint. It follows then that a link is k-link_top_critical if and only if it is (k,k)-loop_top_critical (or 2k-loop_critical in a more general definition). Because of such equivalency, and expectation that k U = k V is reasonable to assume, we did not implement this definition. If positional information is used, the corresponding algorithm applies the following test. A link UV is (k U ,k V )-loop_pos_critical if the sets of k U -hop neighbors of U and k V -hop neighbors of V are disjoint, and there are no two nodes, one from each of these sets, that are neighbours. It follows then that a link is k-link_pos_critical if and only if it is (k,k)-loop_pos_critical (that is, 2k-loop_critical). Note that our initial definition of a k-loop_critical link is equivalent to the new definition of (k,0)-loop_critical link.

Figure 4 illustrates these definitions. For example, after applying 1-and 2-loop_top_critical algorithms on link AB, we declare the link as critical because from node A we can not reach the node B with 2 hops. However, the link will not be detected as critical with 2-loop_pos_critical algorithm, since 2-hop neighbour node D of A is neighbour of node B, based on their geographical positions. The 3-loop_top_critical algorithm detects the link XY as critical, but the 3-loop_position_critical correctly detects the link as not being critical, since 3-hop neighbour F of node Y is a neighbour of X. The link JK is the link where 3-loop_position_critical algorithm wrongly declares it as critical. The loop is too wide, and more hops are needed in order to correctly declare the link as not being critical. The 1-loop_top_critical scheme is very week, which is illustrated on link MN. This scheme only detects the node O, which obviously does not form a loop from M to N, therefore, all the link is declared critical with 1-loop_top_critical algorithm. However, the 1-loop_pos_algorithm correctly declares the link MN as not being critical.

Localized algorithms for detection of critical links based on critical nodes

Perhaps the simplest definition of critical nodes is by using prior recognition of critical nodes, as follows. A link AB is declared k-pos_link-by-node_critical (k-top_link-by-node_critical) if both A and B are declared as k-pos_critical nodes (k-top_critical nodes, respectively). The advantage of this definition over other two is that the implementation of it does not require two nodes to exchange their neighbourhood information beyond already exchanged one. Instead, they need to exchange merely their decisions about being critical nodes.

Alternatively, each node may decide which of its links are k-hop critical by using its (k+1)hop information, which involved more communication overhead for collecting than the suggested decision exchange method. The communication overhead involved with detection of critical links via critical nodes is the smallest among the mentioned definitions and corresponding implementations. However, as already observed, this algorithm is not as accurate for detection of critical links as ktop/pos_critical_link algorithm. Two critical nodes may be connected with more than one link. From Figure 4 we see that nodes O and Q are critical nodes and that they have a direct link between them, yet they also have a common neighbour P, which creates a path OPQ. Therefore, the link OQ is in fact not critical, which can be easily verified with 1-top_critical_link algorithm. These cases are present in our simulations; hence, due to the inaccuracy of this algorithm, we did not perform the experiments for it.

Performance evaluation

We have measured the accuracy of proposed localized critical nodes and links detection algorithms by comparing them with the corresponding globalized algorithm, that is, with the correct conclusion. We will describe here the experimental results obtained by experimenting with connected random unit graphs. The master thesis of the first author (in preparation) contains also data for random unit graphs which are allowed to be disconnected.

We generate connected random unit graphs with n nodes and desired density (average number of neighbors) d using the following method. This method is selected since we wanted to estimate the performance also for very sparse networks. This was a time consuming process with alternative methods (e.g. generating each node at random, deciding proper transmission radius, testing connectivity at end).

An approximate radius r is obtained from the formula d=(n-1)*r*r*π/(a*a). The first node is randomly generated (that is, its xand ycoordinates are chosen at random) in a given square with edge length a. Each of following n-1 nodes is generated repeatedly, at random, and tested whether it is within distance r to at least one of previously generated and accepted nodes, until the test is satisfied. Otherwise (when it is at distance >r to all previously accepted nodes), the node is rejected and another node generated and tested instead.

After selecting n nodes with this procedure, a connected random unit graph is generated. However, its average degree q is not necessarily the desired one, d. We now find the exact average degree d of generated graph, by counting edges and compare it with desired value d. If q<d, more edges need to be added, and graph remains connected. We sort all n*(n-1)/2 possible edges and desired radius R is the n*d/2-th edge in sorted list. Unit graph is then decided using this value of R (that is, two nodes are neighbours if and only if the distance between them is at most R). If q=d then the graph remains unchanged. If q>d, this obtained random unit graph is too dense, and some edges need to be deleted by reducing transmission radius. We sort all n*(n-1)/2 possible edges in increasing order and find the n*d/2-th edge in the sorted list. We use this edge as the transmission radius R, and define the corresponding graph, which may not be connected. Dijkstra's shortest path algorithm is used to check the connectivity of this graph. If the graph is not connected, it is ignored, and the procedure is repeated. If it is connected, which should happen with high probability with this procedure, the graph is accepted.

Our experiments are performed with n=100 and n=500 nodes for several densities, ranging from 3 to 15. In each case, the main measure considered is the detection ratio, which is the probability that a node or link declared as critical by considered localized algorithm is indeed critical when verified by global algorithm. We also measured the average number of critical nodes and links detected in the network. We detection ratios for n=500, which are overall somewhat better (by as much as 10%) than for n=100, which was counterintuitive but encouraging for the scalability of our approach.

Localized algorithms for detection of critical nodes

Tables 1 and2 show the detection ratios for critical nodes, using k-node_top_critical and k-node_pos_critical algorithms, for k=1, 2 and 3, obtained after 20 simulations for different values of d for random connected unit graphs with n=500 nodes.

Detection ratios are generally over 50%, meaning that over half of locally estimated critical nodes were indeed globally critical even for k=1 (the accuracy increases to over 70% for k=2 and over 80% for k=3), for average number of neighbours ranging from 3 to 15. As expected the k-node_pos_critical algorithm performs better than the k-node_top_critical algorithm. It can be observed that there are not many critical nodes in graphs, especially for graphs with medium density and dense graphs. Localized algorithms do not declare too many nodes as critical that are in fact not globally critical.

Localized algorithms for detection of critical links

Tables 5 and6 From these tables we conclude that the localized algorithms give excellent results. In particular, 3-hops localized algorithms have the accuracy greater than 80% for any d, while 2-hop localized algorithms have accuracy greater than 70% in most cases. Even 1-hop localized algorithms declare correctly more than 50% of links.

The average number of critical links detected by local k-link_top_critical/ k-link_pos_critical algorithms and the number of critical links detected by global algorithm are recorded in Tables 7 and8, respectively. From the tables we conclude that local algorithms for detection of critical nodes have approximately the same accuracy as the local algorithms for detection of critical links. This behavior is well expected because if a link is declared as critical, then the two nodes making this link are also declared critical. So, we can expect to have at least two times more critical nodes than links. Some critical nodes are not a part of a critical link. The number of these nodes is not high. For example, no critical nodes that are not part of a critical link was found for d between 10 and 15.

We will now give some insight in order to explain obtained result. Figure 5 shows one of obtained random connected unit graphs with 500 nodes, using our described procedure. The average density is high, d=15. The main problem that lowers the detection ratio of localized algorithms can be associated with creation of ring structures shown in Figure 5. Ring structures (those producing some critical nodes or links are marked by 'R' in Fig. 5) are very common in these graphs and they are the focal problem in detection of critical links/nodes with local algorithms. The critical links detected by 1-top_critical_link algorithm are drown in black in Fig. 5. Critical nodes detected by 1-top_critical_node algorithm are drawn in green in Fig. 5. Rings are often too wide to be detected by 3 hops and most of the nodes/links that are part of a specific ring are then declared as critical. These rings can be detected if we increase the hop count, but then the nature of local algorithms is lost.

Conclusion

We described several localized protocols for fast and mostly accurate detection of critical links and nodes in ad hoc networks. Existing algorithms for detection of critical links and nodes have a high complexity and require knowledge of the topology of a network. This paper showed that the localized criteria could successfully be used in order to detect critical links/nodes. Our experiments show that the localized algorithms are reasonably accurate on strongly connected graphs. Errors recorded for localized algorithms come from the ring structures that are created in graph generation. These rings are too wide and more hops are needed in order to correctly detect if a link or node is critical.

In an upcoming companion article, we applied, with suitable modifications and additional criteria, the proposed localized algorithms for detection of critical links and nodes for service replication. In this scenario, a particular route between a client and a server node is monitored for the presence of critical links or nodes. If such node or link is detected, an alternate service in the network is searched, or service is replicated.

The proposed localized partition detection schemes may be applied in sensor network scenarios. Sensors that detect their criticality or existence of critical links may report to monitoring center, asking for deployment of additional sensors in the area, or wakening up some nearby sleeping sensors. We intend to consider this application of localized partition detection for designing sensor activity scheduling protocols.

We have considered unit graph model in our experiments. However, our protocols based on topological knowledge are graph based protocols, and can be applied for ad hoc networks with nonuniform transmission radii. Protocols based on positional information require to know also transmission radii of nodes in local neighbourhood in addition to their positions.

We originally expected to observe much more significant impact of density on the detection ratios. We expected that critical densities for connectivity will also somehow represent significant changes in detection ratios. However, our experimental results did not indicate any relation. This could be due in part to performing experiments only for connected unit graphs. It is certainly important to further study the relation of connectivity probability and detection ratios.

We are currently designing localized algorithms for deciding, at each node, whether or not graph is k-connected. Another interesting problems is to assign, in localized manner (as opposed to globalized solution [HIM]), transmission radii to each node so that the network is k-connected with high probability.

Figure 2 .

 2 Figure 2. Node A is 1-hop critical, node G is topologically 3-hop critical and positionally 2critical, node M is 1-hop critical

Figure 3 .

 3 Figure 3. Examples of critical links HI, AB, XY and KL

Figure 4 .

 4 Figure 4. Loop length based critical links AB, XY, MN and JK

Figure 5 .

 5 Figure 5. Ad-hoc network for d=15

Table 2 .

 2 Detection ratios for k-node_pos_critical algorithm on connected graphs with 500 nodes.Tables3 and 4present the average numbers of detected critical nodes for each algorithm. The third column shows the average number of critical nodes detected by global algorithms. The fourth and fifth columns show the number of critical nodes detected by local algorithms for k=2 and 3.

	Average degree	Detection Ratio	Detection Ratio
	of neighbours	2-hop algorithms	3-hop algorithms
	(d)	(%)	(%)
	15	50.0	71.4
	11
		64.2	79.5
	10	73.0	90.2
	9	70.4	97.7
	8	73.3	88.7
	7	64.8	82.5
	6	67.9	83.6
	5	71.5	78.6
	4	73.5	91.5
	3	66.7	86.5
	Table 1. Detection ratios for k-node_top_critical
	algorithm on connected graphs with 500 nodes

Table 7 .

 7 Average number of detected critical links by k-link_top_critical and global algorithms

	Average number of neighbours (d)	Average Number of links	Average number of critical links (global alg)	Average Number of critical links (1-hop alg)	Average Number of critical links (2-hop alg)	Average Number of critical links (3-hop alg)
	15	5420	1.5	4.8	3.0	2.1
	11	4523	3.4	8.7	5.3	3.9
	10	4306	4.6	9.1	6.3	5.1
	9	4039	4.2	9.6	5.9	4.2
	8	3785	5.0	12.0	6.4	5.5
	7	3365	4.4	10.0	6.5	5.2
	6	3015	5.1	10.4	7.0	6.1
	5	2785	6.7	14.6	9.3	8.3
	4	2555	8.0	16.8	10.4	8.6
	3	2115	9.1	18.6	13.5	10.5

Table 8 .

 8 Average number of detected critical links by k-link_pos_critical and global algorithms


Michaël Hauspie

Jean Carle

David Simplot

Partition Detection in Mobile Ad-Hoc Networks Using Multiple Disjoint Paths Set

In an ad-hoc network, client-server based application can encounter some problems due to the dynamic topology. One of these problems is when the network splits, leading the server and the client to be physically unreachable from each other. Predicting those partitions could be a very useful feature that can be provided to applications. Indeed, being aware of a future disconnection in the network can help to ensure a better quality of service by adapting the client and/or the server behavior. Algorithms already exists to do this, but they are based on trajectory interpolation which need position information to be provided by a positioning system. This paper propose an original link robustness evaluation method based on the notion of disjoint paths set that allow efficient partition detection without using any kind of positioning system. After showing that the use of disjoint path is relevant for detecting network partitions, we propose a distributed algorithm that collects disjoint paths available between the server and the client and thus show that our partition detection metric can be used in a real network. Moreover, those set of disjoint paths could be used in multipath routing protocols.

Introduction

Wireless networks such as Bluetooth [3] or WiFi (Wireless Ethernet IEEE 802.11b) [START_REF]IEEE standards boards part 11, Wireless LAN medium access control and physical layer specifications[END_REF] can grant users data access regardless of their location without wired connection.

Nowadays, those networks are mostly used by directly communicating with a base station linked to a wired network and internet. Another application of such technologies are networks based neither on a base station nor any kind of fixed infrastructure. Those networks are useful when no wired link is available such as in disaster recovery or more generally when a fast deployment is necessary. In those applications, mobile computers, or nodes, will communicate by routing messages through the network by multi-hopping protocols [START_REF] Royer | A review of current routing protocols for ad-hoc mobile wireless networks[END_REF][START_REF]Handbook of Wireless Networks and Mobile Computing[END_REF][START_REF] Toh | Ad Hoc Mobile Wireless Networks, Protocols and Systems[END_REF]. These networks are called MANET for Mobile Ad-hoc NETworks [START_REF] Simplot | Mobile Ad-hoc NETwork) group of IETF (Internet Enginering Task Force)[END_REF].

In that context, client-server based application can encounter some problems due to the dynamic topology. One of these problems is when the network splits, leading the server and the client to be physically unreachable from each other. If connection breaks are real failure in a wired environment, in ad-hoc networks, we must consider it as a normal network behavior because it can occur after a node has moved or a user has turned his device off. 00000 00000 11111 11111 0000 0000 0000 1111 1111 1111 Client Server 00 00 00 00 00 [START_REF] Johnson | Dynamic source routing in ad hoc wireless networks[END_REF] In the case of node movement (Figure 1), it can be useful to predict partitioning and notify applications. Indeed, being aware of a future disconnection in the network can help to ensure a better quality of service by adapting the client and/or the server behavior. Algorithms already exists to do this but they are based on trajectory interpolation which need position information to be provided by a positioning system. As those systems are often expensive and bulky [START_REF] Benlarbi-Delaï | Using 3D indoor microwave phase sensitive stereoscopic location system to reduce energy consumption in wireless ad-hoc networks[END_REF], it may be relevant to provide algorithms that can be used in a "standard" ad-hoc network (i.e. with objects that only have a wireless communication device but no positioning system and without centralized infrastructure). In this paper, we propose a metric that can be used to detect partitions based on a multiple disjoint paths set and a distributed algorithm that collects this set using an original directed flooding protocol. The first part of this work has already been presented in [START_REF] Hauspie | Partition detection in mobile ad-hoc networks[END_REF].

The paper is organized as follows. First, we describe the existing work on partition detection in section 2. Then, section 3 propose and evaluate two metrics based on disjoint paths. Section 4 describe and evaluate our distributed algorithm. Finally we conclude our work in Section 5.

Related works

Partition detection

In [START_REF] Park | A highly adaptive distributed routing algorithm for mobile wireless networks[END_REF], Park et al. proposed TORA, an adaptive routing protocol for ad-hoc networks. In this protocol, the authors use a method to detect network partitions after they occur. The aim of this detection for their routing algorithm is to find the nodes that are no more reachable and thus, erase the deprecated routes that lead to them. In this paper, we do not focus on detecting partition after its occurrence but before, so that applications can react by modifying their behavior while the nodes are still connected. Detecting network partition before they happen give some time to seamlessly react by finding a new route and/or adapt the application behavior.

In [START_REF] Shah | Cross-layer design for data accessibility in mobile ad hoc networks[END_REF], Shah et al. aimed at enhancing data access in an ad-hoc network by detecting partitions before it happens. In their scenario, a node n 1 , needs data that are stored in another node (say node n 2 ). For allowing n 1 to access the data even if its connection with n 2 physically breaks, they propose a data replication mechanism based on partition detection. Every node embeds a positioning system (such as GPS) and by successive measures computes its velocity. Regularly, it spreads those information to the other nodes. Thus, each node of a connected group knows the behavior of the other members of this group. So, they can predict when a node storing a particular data will leave the group before it effectively does it. At this point, the owner of the data elects a node of the group to be another host of the data and replicates it on this node. The main advantage of this method is that each node knows exactly when the partition occurs if node movements are almost regular (no brutal direction changes). On the other hand, this method has two main disadvantages. First, they need a positioning system, often expensive and bulky. Second, the network has a continuous and relatively high load of the network due to the exchange of position and speed information. Moreover, as the trajectory of nodes are interpolated, it involves some computation that would not be insignificant in the case of small devices such as mobile phones.

Wang et al. proposed a roughly similar partition prediction in [START_REF] Wang | Group mobility and partition prediction in wireless ad-hoc networks[END_REF], although their solution is more centralized. It is based on an extension of the Reference Point Group Mobility (RPGM) by Hong et al. [START_REF] Hong | A group mobility model for ad-hoc wireless networks[END_REF]. They extend this model to handle the velocity of the nodes and thus regroup the node according to their position and speed. For achieving this, each node sends its position and velocity to a server. Then, this server runs a sequential clustering algorithm from the field of pattern recognition [START_REF] Friedman | Introduction to pattern recognition: Statistical, Structural, Neural and Fuzzy Logic approaches[END_REF] to regroup the nodes. Then, as the server knows the groups position and velocity, it can inform nodes of a future partition. Their method has the same problems than those in [START_REF] Shah | Cross-layer design for data accessibility in mobile ad hoc networks[END_REF] with one more disadvantage for the need of a centralized server.

Although those algorithms are giving good results, their inputs are depending on expensive and bulky hardware (GPS) or/and on a node that can be reached by the others. It would be preferable to use a method working on every kind of mobile node equipped with wireless device. So, we want to focus our work on a totally distributed network that does not use any positioning system. Indeed, it then can be applied on every ad-hoc network regardless of the hardware or software provided by the nodes. We think that disjoint paths set can also lead to efficient network partition detection as they have good robustness properties. A set of disjoint paths is a set of paths that have no common nodes except the source and the destination. So if a direct link (also called a one hop link) between two nodes breaks, it can discard one and only one path. Thus, all the other paths are not affected by the failure and the nodes can go on communicating. Moreover, finding disjoint paths set can help developing QoS multipath routing protocols [START_REF] Das | An adaptive framework for QoS routing through multiple paths in ad-hoc wireless networks[END_REF][START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF][START_REF] Leung | A QoS-aware multi-path dynamic source routing protocol for wireless ad-hoc networks[END_REF][START_REF] Lin | Location-based localized alternate, disjoint and multi-path routing algorithms for wireless networks[END_REF].

Disjoint paths computation

In [START_REF] Papadimitratos | Path set selection in mobile ad hoc networks[END_REF], Haas et al. propose a distributed algorithm to compute a disjoint paths set. They computes them iteratively by merging previous paths and an incoming paths that contains backward links (i.e. links that goes from destination to source, see Figure 2). When a node receives a new path, it check it against the paths it already knows. If a link belongs to both paths, one forward (i.e. from source to destination) and the other backward (i.e. from destination to source), two new disjoint paths can be generated by removing the common link and replace it as shown in Figure 2.b where the BC link is the forward one and CB the backward one. But in the context of our experiments, those kind of path are not used to be generated by standard route request methods and so only a few paths are generated. Actually, route request protocol used by most routing protocols are using blind flooding protocols [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF][START_REF] Tseng | The broadcast storm problem in a mobile ad hoc network[END_REF]. A sequence number is used to prevent packets to be broadcast twice or more by each node. The problem of this protocol is that backward links can't be generated in a single flood. Indeed, if we look at Figure 2.a., when the first path (ABCE) is generated, node B and C will store the sequence number associated with the route request. If another instance of the route request reaches the node C, it will discard the request because it has already forwarded one with the same sequence number. So, the path ACBDE can't be generated by using a single flood. Thus, to use this method, we need to send multiple route requests. But sending several route requests has two main problems, the time needed to compute the disjoint paths set and the high number of generated packets. A good disjoint paths computation protocol will then be a protocol that slightly increase the number of packets forward in order to generate the highest disjoint paths number but keep an acceptable network congestion.

In [START_REF] Das | An adaptive framework for QoS routing through multiple paths in ad-hoc wireless networks[END_REF], Das et al. used a flooding protocol no more based on sequence numbers but on the path the packet is currently following. Here is the protocol's algorithm. Let s and d be the source and the destination node respectively. The packet contains a hop count which is decremented at each hop and a route record that store the current path followed by the packet. When a node receives a route request, it performs the following steps :

1. If the node is the destination, a route reply packet is returned to the source along the selected route, as given in the route record that now contains the complete path information between s and d.

2. If maximum hop = 0, the route request packet is discarded.

3. If this node's id1 is already listed in the route record in the request, the route request packet is discarded to avoid looping.

4. The node's id is appended to the route record of the request packet and this request is rebroadcast.

As the node discards the packet only if there were too many hops or if the path is looping, the protocol is more likely to generate a lot of paths. Indeed, a node can rebroadcast a request more than once. Thus, all loop free paths whose length are less than the hop number used for sending the request are found by this method as only path length and test of previous node in it can avoid rebroadcast. The main problem is that the number of generated packet is very high. Actually, it is clear to see that the complexity of the number of forward for each node is O(d n ) where n is the number of hops from the source node and d is the density of the network. Thus, this protocol can be used only in small density and short distance (in hop count).

Lee et al. extend the blind flooding protocol in [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF]. They still using sequence numbers but the decision of a node to forward a packet or not is no more based only on this sequence number. When receiving a packet, a node runs the following algorithm :

1. If the node is the destination, a route reply packet is returned to the source.

2. If a packet with the same sequence number has already been received from the same neighbor, the packet is discarded.

3. The node's id is appended to the route record and the request packet is forwarded.

Here, the complexity of the number of forward for each node will be O(d). We think that we can lower this while generating disjoint paths using an original flooding method.

In the next section, we present how disjoint paths can be used to detect network partition.

Link robustness metrics

We consider the following scenario as the application field of our work. One node of the network is consider as a provider of a given service. Thus, it is acting as server with potentially several clients. Another node is using the service provided by this server, and is the client. We want to give to the client node a method that is able to detect when the server node will be unreachable even by multi-hops routing. To detect this partition, we introduce the notion of link robustness and we propose two metrics based on multiple disjoint paths set to evaluate it. We call link between two nodes the set of paths allowing them to communicate. This link robustness can be seen as its capacity to maintain communication between the two nodes. We will say that a link is strong if the physical disconnection risk is weak.

Preliminaries

Our evaluation methods are based on neighborhood and paths notions that are to be defined. We use G(V, E) as a graph representing the ad hoc network where V represents the set of wireless mobile hosts and E represents the set of edges. Let v and w be two nodes. A path p between v and w is a series of nodes

o 1 , o 2 , . . . , o n such as o 1 = v, o n = w and for all i ∈ 1, n , o i+1 ∈ N (o i ). Let p = n i=1 {o i },
we denote by |p| the number of hops in the path (|p| = n -1). The set of all paths between v and w is denoted by P (v, w).

It is straightforward that each path is not interesting for communications. For instance, extra-long paths or paths with loops are not interesting. Moreover, it is well known that optimal paths in terms of numbers of hops are few, weak and sensible to topological modifications [START_REF] Toh | Associativity based routing for ad hoc mobile networks[END_REF]. That is why in this paper, for two given nodes v and w, we will consider a subset of P (v, w) which will be called sub-optimal loop-free paths.

Let v and w be two nodes, and p ∈ P (v, w). p will be called an optimal path if and only if ∀p ′ ∈ P (v, w) |p ′ | ≥ |p|. If p is optimal, |p| is called distance between v and w and is denoted by d(v, w). Notice that an optimal path is also a loop-free path2 . At last, p is called k-sub-optimal (k ≥ 0) if and only if p is loop-free and |p| < d(v, w) + k. k represents the number of hops added to an optimal path. We denote by SOP k (v, w) the set of k-sub-optimal paths between v and w.

Defining SOP k is motivated by the need of loop-free paths between v and w. Indeed, since optimal paths are few and weak, we need to take account of some other paths near the optimality in number of hops. The set of Loop-Free-Paths (denoted by LF P (v, w)) can then be determined by

LF P (v, w) = lim k→∞ SOP k (v, w) (1)
For a network of size |V |, the longest loop-free path is at most of size |V |-1. So, we have LF P (v, w) = SOP |V |-1 (v, w). We think that there exists a maximal value of k above which SOP k does not change significantly in our evaluation. Decreasing k will help us to efficiently compute the metric. Indeed, a fewer k would reduce the network congestion produced by a distributed algorithm computing a set of disjoint paths. Moreover, it is not desirable to store a lot of paths on each node of an ad hoc network.

Link robustness

Our evaluation method is based on the following idea. The more paths there is between two nodes, the stronger is the path allowing them to communicate. Indeed, if a path breaks, the nodes can go on communicating if and only if it stills being a valid path between them. Figure 3 shows two possible cases. In, Figure 3.a, the nodes have got three paths. If one of them breaks, the nodes can go on communicating. On the other hand, Figure 3.b, it exists only one path connecting node 1 and node 2. If it breaks, the communication will be physically interrupted. In Figure 3 we only consider disjoint paths that seems to be a good robustness criteria as evoked by Haas [START_REF] Papadimitratos | Path set selection in mobile ad hoc networks[END_REF]. Actually, even if it exists hundreds of paths between two nodes, if all of them use the same intermediate node, a simple failure of this node would invalidate all those paths.

For two nodes v and w and a given constant k, the set of parts of SOP k (u, v) (2 SOP k (u,v) ) containing only disjoint path containing only disjointed paths is denoted by DSP k (v, w) (Disjoint Sub-optimal Paths) and is defined by :

DSP k (v, w) = S ∈ 2 SOP k (v,w) | ∀p, p ′ ∈ S p ∩ p′ = {v, w} ⇒ p = p ′ . (2)
Thus, if a node disappear, one and only one paths will break. By this fact, as it stills more than one available disjoint path, one can break without physically breaking the connection. Using this notion of disjoint path, we will propose two link evaluation methods.

We consider k as a fixed system parameter for the definition of our metrics so that the notations remain light.

The first one is only based on the number of disjoint paths available. Indeed, if we have only one paths whereas there were more before, it is strongly possible that this one disappears too, resulting to a physical disconnection. This first metric is denoted LR 1 (for Link Robustness) and is defined by :

LR 1 (u, v) = max A∈DSP k (u,v)
{|A|} .

(3)

For the second one, we aimed at refining the measure given by LR 1 . We can actually notice that the longer is a path, the weaker it is. Thus, all paths do not evenly contribute to the link robustness. Then, We evaluate the probability that at least one path composing the link remains available. The set of disjoint paths that gives the best probability that a path survives gives us our second metric denoted LR 2 :

LR 2 (v, w) = max A∈DSP k (u,v)    1 - p∈DSP k (v,w) P b (p)    , (4)
where P b (p) is the probability that p breaks. The rough calculation of P b (p) is given by the probability that each direct connection composing the path breaks. If p = (o 1 , o 2 , . . . , o n ), we define :

P b (p) = 1 - 1≤i<n µ(o i , o i+1 ), (5)
where µ(x, y) represents the probability that the direct connection between the nodes x and y remains available. This probability has to be evaluated too. For now, we will consider that µ is a constant.

Experiments

The aim of this section is to propose and evaluate the metrics. So, we compute our robustness using the global knowledge of the network and generating disjoint paths using a depth first search algorithm. The distributed algorithm used to compute the disjoint paths set will be discussed in Section 4.

To evaluate the metrics, we did the following experiments :

1. a random graph is generated in a rectangular area, 2. we randomly choose a server node and one of its neighbors as the client node3 , 3. nodes move according to the random way-point model [START_REF] Johnson | Dynamic source routing in ad hoc wireless networks[END_REF]. Each node choose a random destination and goes for it. When he reaches it, he waits for a random time, choose another destination and so on, 4. periodically, we compute the link robustness given by the two methods, 5. when a partition occurs, we go back to step 2 until we reached 300 partitions.

We did our experiments at densities of 4, 6 and 8 nodes by communication area. With higher densities, the network is almost always connected so the physical disconnection is not an important problem. With smaller density, the opposite problem occurs, the network is too unstable to predict anything. We used speeds of 1, 1.5 and 2 meters per second which corresponds to different walking speeds. Nodes communication range are set to 10 meters.

Figure 4 and 5 show the evolution of the value computed by both methods. The density used was 8 nodes by communication area. Nodes' speed was 2 meters per second which is a fast walk speed leading to sudden disconnections.

We can observe that robustness values computed by both methods falls just before the physical disconnection. What is observed at this density and this speed is almost the same with other speeds and densities.

To detect if a partition occur, we introduce the notion of threshold. If the metric falls under a given value (called threshold) during a given amount of time (about 1 second in our experiments), we raise a "warning" flag. The relevance of this warning flag will depend on the efficiency of the metric (i.e. the number of disconnections it predicted) and on the average time between the prediction and the effective disconnection. If this time is too important, the application would always need to change its behavior according to the warning flag. If this time is too short, the application would not have enough time to changes its behavior and some QoS criterion potentially used by application would not be respected.

So, to achieve evaluating the metrics, we have computed their efficiency and the time spent in alert for a range of thresholds. Figures 6 to 11 show the results for the two metrics. Figures 6 to 9 show how the speed influences on those metrics whereas Figures 10 and11 show the density's one. General observations For both metrics, we can say about speed influence that the faster the nodes move, the worse is the prediction. Indeed, if nodes move faster, the topology is less stable so it is harder to have a good prediction. Concerning the influence of the density, as it grows, the stability of the link grows because the number of disjoint paths is potentially higher. This can be observed in Figures 10 and11.

Metrics comparisons

Bypassing the general observations, we can say that the first metric, that only takes care about disjoint paths, produces far better results. Actually, the gap between the efficiency and the alert time is far more important in the first metric. If we want 90 % of efficiency, in the first metric we can take a threshold of 1 and we will only spent 30 to 50 % of connection time in alert depending on the density and on the speed of the nodes. To reach the same efficiency with the second metric, we would need to spend more than 80 % of the total connection time in alert which is not acceptable and tends to always raise an alert flag. Figure 12 shows in an even better way that LR 1 has a better efficiency/alert time ratio than LR 2 using a density of 6 nodes by communication area and 0.5 m/s speed. This can be explained by the fact that this metric is not as stable as the first one and so, topology modification could cause great fluctuation of its value.

Disjoint paths computation

After having shown by our experiments that disjoint paths set provides interesting information which allow efficient partition prediction, we need to find a distributed protocol which computes LR 1 . The main problem of the definition of LR 1 is that it is rather impossible to compute its exact value as we need to know all possible disjoint paths leading to the server. For instance, if we consider a client/server link with distance 5, the number of optimal paths (i.e. k = 0) grows up quickly with the density (see Figure 13). It is clear that finding all paths and compute the subset which maximizes LR 1 requires a lot of network load, memory and CPU time. We must then find an algorithm that gives us an approximative value of LR 1 at low cost in term of network congestion. Moreover, finding disjoint paths set can help developing QoS multipath routing protocols [START_REF] Das | An adaptive framework for QoS routing through multiple paths in ad-hoc wireless networks[END_REF][START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF][START_REF] Leung | A QoS-aware multi-path dynamic source routing protocol for wireless ad-hoc networks[END_REF][START_REF] Lin | Location-based localized alternate, disjoint and multi-path routing algorithms for wireless networks[END_REF].

Protocol description

Our protocol is based on a blind flooding and improved by two mechanism. The blind flooding has two main problems for our purpose. First, as we said in section 2, it does not generate a lot of disjoint paths because each node forwards the packet once and only once. Second, it floods all the network, even nodes that are not involved. Thus, if we increase the number of forward per node in order to generate more paths, it will jam the whole network.

For the first problem, Lee et al. send about d packets per node (where d is the density). The result of this is an increase of the number of paths found but also a high overhead. Our protocol works by controlling the maximum of forward per node using multiple sequence numbers.

To solve the second problem, we used hops information to allow only the nodes which are susceptible of being in a path to forward the packet. As a result our request is directed towards the destination node and does not overhead the whole network.

Our method works in two steps. First, the client sends a disjoint paths set request to the server. This request can be done using a efficient broadcast [START_REF] Cartigny | RNG relay subset flooding protocols in mobile ad-hoc networks[END_REF][START_REF] Qayyum | Multipoint relaying for flooding broadcast messages in mobile wireless networks[END_REF] or a message sent by a routing protocol [START_REF] Broch | A performance comparison of multi-hop wireless ad hoc network routing protocols[END_REF]. When the server receives the request, he sends a reply back. The reply packet contains the following information :

• the id of the server,

• the id of the client,

• the distance between the server and the client (in hop count). This distance is the one acquired from the request packet,

• the number of hops,

• the current sequence number, used to restrict the rebroadcast of the packet (as in the blind flooding protocol),

• a set of sequence numbers, initially filled by the server,

• the path followed by the packet.

Let d(c, s) be the distance between the client and the server, h the number of hops followed by the packet and d(c, u) the distance between the client and the node u. Every node u receiving this reply runs the following algorithm :

1. if the node has already forward a packet with the same sequence number, the packet is discarded,

2. if h + d(c, u) > d(c, s) + k (
where k is a protocol's parameter), the packet is discarded, 3. if the number of hops done by packet is equals to half the distance between the server and client, the node selects a random sequence number in the sequence numbers set included in the packet and rebroadcast the packet using this sequence number else the packet is rebroadcast according to the blind flooding algorithm.

The first rule of the protocol is similar to the blind flooding. The second one is used to target the client with the broadcast as shown in figure 14 where thick black lines are the radio link involved by the reply. As we can see, only a few part of the network is disturbed by our protocol.

For this rule, we need to know the distance between every node and the client node. This can be done in several ways. The simplest is to used an optimized broadcast for the request. Each node forwarding the request stores its distance from the client. But it can also be achieved using periodic hello messages (the ones used by a routing protocol for example). The third rule is used to generate a bit more packets and thus, more paths. As the server sets how many sequence numbers to use, it can control the overhead generated by the reply. This overhead can also be controlled by changing the k value. If k is big, there will be more paths and they will be longer. But, on the other hand, there will be more node that will forward the reply and thus, more overhead.

With our sequence number change policy and our limited rebroadcast, we are able to compute an almost large disjoint paths set by generating a small overhead. That is what we show in the next section.

Experiments

Our experiments were done at several densities using a 200 nodes graph in a 600 meters by 400 meters rectangular area. The nodes' range is adjusted to have the correct density. As in section 3.3, the nodes are following the random way point model. We evaluated one of the two protocols depicted in section 2.2, the one given in [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF], and ours. The reason why we do not report the evaluation of the protocol given in [START_REF] Das | An adaptive framework for QoS routing through multiple paths in ad-hoc wireless networks[END_REF] is because as we said above, the complexity of this protocol is about O(d n ) forward per node. Thus, we were unable to reach the end of the simulation for density up to five node per communication area. To have accurate results, we proceed as the following : 2. two nodes are selected for being the client and the server. We choose them so that they are at a distance of 5 hops and that there is at least 3 disjoint paths between them (checked by a DFS). If no nodes verifying those conditions are found, a new graph is generated and so on, 3. we simulate the two protocols and store the number of forward of every node and the number of disjoint paths found by each protocols, 4. above steps are repeated for 100 different graphs and the results are averaged.

The k parameter was set to 5 in our protocol and the number of sequence numbers included in the reply packet was equal to the density. Figures 15,[START_REF] Park | A highly adaptive distributed routing algorithm for mobile wireless networks[END_REF] Figure 15, reports the number of disjoint paths found by each protocol. As we can see, ours find more than the one depicted in [START_REF] Lee | Split multipath routing with maximally disjoint paths in ad hoc networks[END_REF].

Figure 16 shows the average number of forward for each node. This represents the amount of overhead in the network. We can notice that what we said in section 2.2 concerning the complexity of Lee et al.'s protocol is confirmed by the graph. Indeed, the plot of the number of forward per node is roughly asymptotic to the f (d) = d line. Thanks to our directed broadcast, this number is far beyond for our protocol. Depending on the number of disjoint path we want, we can tune our protocol and thus generate more or less overhead by modifying the k value.

Finally, figure 17 shows the average number of forward per node needed to find disjoint paths. Our experiments shows that our protocol is a real improvement in finding multiple disjoint paths set as the overhead generated is rather small and the number of paths found high.

Conclusion

This paper propose two things. At first, we show through our experiments that multiple disjoint paths set can be used to detection network partition between two nodes. Although the prediction could be more accurate, it is a first step to detect the partition without using any kind of infrastructure. This partition detection must rely on an efficient distributed algorithm which can gather as much disjoint paths as possible without jamming the network. We presented such protocol in the second part of the paper and compared it with the ones depicted in the literature. Our experiments shows that our protocol can efficiently find disjoint paths by involving only a small overhead.

Figure 1 :

 1 Figure 1: Network partition caused by topology changes

Figure 2 :

 2 Figure 2: Iterative computing of disjoint paths using backward links

  Figure 3: Topology examples

Figure 4 :

 4 Figure 4: Evolution of the link robustness value for the first metric

Figure 5 :

 5 Figure 5: Evolution of the link robustness value for the second metric

Figure 6 :

 6 Figure 6: Evaluation of the first metric at 0.5 m/s with density 6

Figure 7 :

 7 Figure 7: Evaluation of the first metric at 2.0 m/s with density 6

Figure 8 :

 8 Figure 8: Evaluation of the second metric at 0.5 m/s with density 6

Figure 9 :

 9 Figure 9: Evaluation of the second metric at 2.0 m/s with density 6

Figure 10 :

 10 Figure 10: Evaluation of the first metric at 2.0 m/s with density 8

Figure 11 :Figure 12 :

 1112 Figure 11: Evaluation of the second metric at 2.0 m/s with density 8

Figure 13 :

 13 Figure 13: Average number of optimal paths with 5 hops distance

Figure 14 :

 14 Figure 14: Directed broadcast

  and 16 reports the results of our experiments.

Figure 15 :Figure 16 :

 1516 Figure 15: Disjoint paths found

Figure 17 :

 17 Figure 17: Average number of forward per node over number of disjoint paths found

the node's identity which is a unique number associated with that node

A path p ∈ P (v, w) is called loop-free if and only if ∀i, j ∈ 1, n , o i = o j ⇒ i = j.

We this, we are sure that the nodes are connected at the start of the simulation