[go: up one dir, main page]

WO2008078016A1 - System and method for estimating data packet loss in an ad hoc network - Google Patents

System and method for estimating data packet loss in an ad hoc network Download PDF

Info

Publication number
WO2008078016A1
WO2008078016A1 PCT/FR2007/051650 FR2007051650W WO2008078016A1 WO 2008078016 A1 WO2008078016 A1 WO 2008078016A1 FR 2007051650 W FR2007051650 W FR 2007051650W WO 2008078016 A1 WO2008078016 A1 WO 2008078016A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
data packets
count
values
nodes
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2007/051650
Other languages
French (fr)
Inventor
Laurent Reynaud
Ignacy Gawedzki
Khaldoun Al Agha
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Publication of WO2008078016A1 publication Critical patent/WO2008078016A1/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W40/00—Communication routing or communication path finding
    • H04W40/02—Communication route or path selection, e.g. power-based or shortest path routing
    • H04W40/12—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality
    • H04W40/14—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality based on stability
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/14—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic
    • H04L63/1408—Network architectures or network communication protocols for network security for detecting or protecting against malicious traffic by monitoring network traffic
    • H04L63/1416—Event detection, e.g. attack signature detection
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W12/00—Security arrangements; Authentication; Protecting privacy or anonymity
    • H04W12/12—Detection or prevention of fraud
    • H04W12/121—Wireless intrusion detection systems [WIDS]; Wireless intrusion prevention systems [WIPS]
    • H04W12/122—Counter-measures against attacks; Protection against rogue devices

Definitions

  • the invention relates to the field of ad hoc networks and more particularly to the evaluation of the loss of data packets in such a network.
  • Ad hoc networks are networks formed spontaneously by a set of nodes that can be mobile (eg stationary or portable personal computers, personal assistants, mobile phones, etc.) equipped with wireless network cards and located in the vicinity of a part of the network. 'between them. To communicate with nodes outside its own scope, a node must pass through intermediate nodes.
  • Multihop requires the use of protocols and routing algorithms to allow each node to know which neighbor to transmit the data to a remote node.
  • Ad hoc networks provide a solution in situations where a wired infrastructure does not exist or is not envisaged or not conceivable, for example for the organization of relief in disaster areas. They can also be used to access specific services in public places.
  • Ad hoc mobile networks include mobile nodes that by definition are not controlled by a central entity.
  • These specificities of the ad hoc networks mean that the routing solutions developed for conventional wired networks are not at all adapted and new techniques have to be developed.
  • the first approach is for reactive protocols and the second is for proactive protocols.
  • the nodes do not maintain particular information and seek a route only when it is required, by flooding the network with messages intended to find the shortest path to the destination.
  • the response to this broadcast request allows the source node to obtain the topological information relating to this route.
  • the nodes periodically exchange control messages that allow them to have the necessary information permanently to reach any destination, and to be informed of the evolution of the topology of the network.
  • the proactive protocols we can note the existence of two families of protocols that allow the maintenance of routing tables.
  • the first family concerns the distance vector protocols (or vector distance in English) in which each node periodically exchanges its routing tables with its direct neighbors and updates them according to the received tables.
  • the second family concerns link state protocols in which nodes exchange messages with their immediate neighbors to discover their neighborhood or local topology and then broadcast this information to the entire network so that all nodes can recreate the global topology and calculate routes to all destinations by searching for the shortest path on the global topology.
  • ad hoc network routing protocols are distributed algorithms that only support the appearance and disappearance of nodes over time. From the point of view of a node in the network, it is impossible to distinguish a neighboring node that stops working (because of a failure or simply because it has been powered off) of a neighboring node who has moved away and can not be reached directly.
  • the only type of failure supported by the routing protocols is the type of "stop communication" (or crash-fail in English).
  • the malicious node may for example transmit too weakly for the recipient of the frame can receive it, but strongly enough for the other neighbors (or at least a sufficient proportion of them) detect the transmission and do not broadcast an alert.
  • a malicious node may erroneously warn, accuse a benevolent neighbor, and undermine the detection process.
  • the present invention relates to a method of evaluating a loss of data packets exchanged between nodes of an ad hoc network, the method according to the invention comprising the following steps, implemented by a node of the ad hoc network, said evaluator node: - determining first count values at a node of data packets exchanged between said node and at least one direct neighbor node,
  • This method makes it possible to detect links on which the data are lost, for example intentionally, and thus provide a way to circumvent malicious or selfish nodes in a routing protocol.
  • this process is evolutionary, does not impose strong constraints because it makes no particular assumptions on the underlying hardware layer.
  • Such a method can be implemented in an ad hoc network that has an integrity property ensuring the integrity of the data packets exchanged between the nodes of the network, for example by means of cryptographic solutions.
  • the method according to the invention comprises an update of the evaluation of the intentional loss of data packets.
  • the method can adapt to any unpredictable behavior of the nodes and to a dynamic topology of the ad hoc network.
  • the method according to the invention comprises a diffusion of the first count values to other nodes of said ad hoc network.
  • the method comprises searching for a route between a source node and a destination node bypassing one or more intermediate nodes presenting a loss of data packets. This helps to find a more reliable route to any destination.
  • the determination of counting values of data packets exchanged between said node and one of its direct neighbor nodes comprises all or part of the following counts:
  • the nodes of the network can easily check the conservation of data packet streams.
  • the comparison of the count at said node may comprise all or part of the following comparisons: a first comparison between, on the one hand, the sum of fourth counts of data packets received by said node from its direct neighbors and destined for another node and secondly the sum of second counts of packets retransmitted by said node, a second comparison between on the one hand the sum of the first count and the second count of the number of data packets sent by said node on one side the oriented link, and secondly the sum of the third count and the fourth count of the number of data packets received by the neighboring node on the other side of said oriented link, a third comparison between the fifth count on the one hand the number of data packets transmitted by said node to its neighbor node and on the other hand the third count of the number of data packets received by said neighbor from said node and which is intended for it, and
  • each node can easily perform the consistency checks of the different counts to estimate the reliability of each node and each network link.
  • the first counting values at the said evaluating node are updated each time a data packet is processed, depending on whether the said evaluating node or the direct neighbor node corresponds to a source, a destination or a destination. intermediate of said data packet.
  • the invention also relates to a system for evaluating a loss of at least one data packet, data packets exchanged between nodes of an ad hoc network, the system comprising: means for determining first values for counting, at node level, data packets exchanged between said node and at least one direct neighbor node,
  • receiving means arranged to receive second count values determined by at least one direct neighboring node
  • comparison means arranged to compare the first counting values with the second counting values
  • evaluation means arranged to evaluate a loss of data packets by at least one direct neighboring node as a function of said comparison.
  • the invention also aims at a node of an ad hoc network, the node comprising:
  • means for determining first counting values arranged for counting data packets exchanged with at least one direct neighboring node
  • reception means arranged to receive second count values determined by said at least one direct neighboring node
  • comparison means arranged to compare the first count values with the second count values
  • evaluation means arranged to evaluate a loss of data packets by said at least one direct neighboring node as a function of said comparison.
  • the invention also relates to a computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by microprocessor, comprising code instructions for the execution of the steps of the method of evaluation of the loss. data packets in an ad hoc network according to at least one of the above features, when executed on a computer or a microprocessor.
  • FIG 1 schematically illustrates an ad hoc network formed by a set of nodes, according to the invention
  • FIG. 2 schematically illustrates a system for evaluating the loss of data packets in an ad hoc network of FIG. 1;
  • FIG. 3 illustrates in more detail an example of the evaluation system of FIG. 2.
  • FIGS. 4A to 4D illustrate examples of verification of the conservation of data streams at a node according to the invention.
  • FIG. 1 illustrates an example according to the invention of an ad hoc network formed by a set of nodes N1,... Ni, Nj,... Nn of ranges P1, .., Pi, Pj , ... Pn respectively.
  • a node must therefore pass through intermediate nodes.
  • the node N1 can communicate with the node Nn through the intermediate nodes N2, .., Nj following several communications hops.
  • a node Ni (mobile or fixed) may be provided with a wireless network card and may correspond to a stationary or portable computer, personal assistant, mobile phone, sensor or probe etc.
  • a neighbor node of a node Ni is a node located in the coverage area thereof. I l is therefore in transmission range of the node Ni.
  • a direct neighbor node is a node that is at a jump, in the sense of the routing protocol.
  • the communication between the nodes can be carried out according to a protocol or proactive routing algorithm (for example with a distance vector or a link state) which enables each node to know which neighbor node to transmit the data to. a remote node.
  • the communication between the nodes can be performed according to a reactive routing protocol.
  • FIG. 2 schematically illustrates a system for evaluating the loss of data packets among those exchanged between nodes of an ad hoc network.
  • a node that intentionally loses a data packet destined for another node is called a "selfish node".
  • an egoistic node may decide not to forward a data packet of which it is an intermediate router and lose data to the node transmitting the data packet for example to save its own energy.
  • a selfish knot can baffle the proper functioning of an ad hoc network.
  • the ad hoc network has an integrity property that guarantees the integrity of control messages or data packets exchanged between network nodes.
  • each node is authenticatable and that the integrity of data exchanged between the nodes is guaranteed throughout the network.
  • the integrity property of the ad hoc network can be realized by known cryptographic means adapted to guarantee the confidentiality and the integrity of the data of the communications between the nodes of the network. Moreover, this same cryptographic means can be used to prevent malicious or malfunctioning nodes from falsifying their identity or modifying the contents of control messages sent by other nodes. Moreover, it is possible to guarantee that the information contained in a control message is correct and that the node transmitting the control message has not published false information. A malicious node can not falsify its identity or alter the information contained in the message of another node. For the sake of simplification, the system of FIG. 2 only shows two neighboring nodes Ni and Nj communicating with each other via a link Lij.
  • FIG. 2 is also an illustration of the main steps of the method of evaluating a loss of at least one data packet in an ad hoc network according to a particular embodiment of the invention.
  • each of the nodes Ni and Nj comprises counting means 1 i, 1j, diffusion / reception means 3i, 3j, comparison means 5i, 5j and evaluation means 7i, 7j.
  • the counting means 1 i of this node Ni count the data packets exchanged between it and at least one direct neighboring node Nj. More particularly, the counting means 1 i can determine a set of counting values or counters CM to Q6 (see Figure 3) per node or link that counts the number of data packets transmitted / received per node or link.
  • the node Ni counts the data packets exchanged between it and each direct neighboring node Nj.
  • the broadcast / reception means 3i of the node N1 allow the dissemination of the counting values to other nodes of the network using any ad hoc routing protocol.
  • the broadcast can be provided by an ad hoc routing protocol of the type OLSR (for "Optimized Link State Routing") or DSR (for "Dynamic Source Routing") standardized by the group "MANET".
  • the broadcast / reception means further allow the reception of count values determined by another node.
  • each node Ni may broadcast the values of its counters to its neighboring nodes Nj at "a jump", that is to say its direct neighboring nodes, at "two jumps", "n jumps” or at any other time. the ad hoc network.
  • each node Ni may broadcast the values of its counters periodically according to a predetermined diffusion period. This broadcast period may be a system parameter and may depend on the size of the ad hoc network, the amount of traffic, and the accuracy with which malicious or selfish nodes are to be detected.
  • each node Ni also receives the values of the counters determined by neighboring nodes Nj or possibly by all the other nodes and can thus carry out consistency checks in order to estimate the reliability of each link and of each node.
  • the comparison means 5i of the node N1 compare the counting values of the data packets at the node N1 with the counting values determined by other nodes.
  • the evaluation means 7i of the node N1 evaluate the level of the loss of data packets performed by the other nodes as a function of the comparison of the counters between the different nodes.
  • a value relating to the reliability of each link and of each node can be evaluated according to the result of the comparison of the counters between the different nodes.
  • this reliability value can be used as a metric in the determination of sufficiently reliable paths between two nodes.
  • one can search a more or less reliable route between a source node and a destination node by possibly bypassing one or more selfish nodes or having malfunctions.
  • the evaluation of the loss of data packets is constantly updated in order to adapt to any unpredictable behavior of the nodes and the dynamic topology of the ad hoc network.
  • Figure 3 illustrates in more detail an example of the system for evaluating the loss of data packets in an ad hoc network.
  • the counting means 1 i of the node N 1 determine the counters CM to Q6 and the counting means 1j of the node Nj determine the counters Cj 1 to Cj6. All nodes maintain counters on each of the links to each of their direct neighbors.
  • each node Ni of the network has six counters per oriented link (Ni, Nj) or (Nj, Ni), or twelve counters per link Lij undirected.
  • the counting of data packets exchanged between the node N1 and each of its direct neighboring nodes Nj can be carried out via the counters CM to Q6.
  • the counter CM makes it possible to perform a first count Sij of the number of first data packets whose node Ni is the source, and which are transmitted on an arc or oriented link (Ni, Nj) between the node Ni and the node neighbor Nj.
  • the counter Q2 makes it possible to perform a second count Oij of the number of second data packets whose node Ni is not the source, and which are transmitted on the oriented link (Ni, Nj) between the node Ni and the neighboring node Nj .
  • the counter Q3 makes it possible to make a third count Dij of the number of third data packets whose node Ni is the destination (ie the final destination), and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node Ni.
  • the counter Q4 makes it possible to carry out a fourth count Mj of the number of fourth data packets whose node Ni is not destination, and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node N1.
  • the counter Q5 makes it possible to carry out a fifth count Mij of the number of fifth data packets whose node Nj is the destination, and which are transmitted on the oriented link (Ni, Nj) between the node N1 and the neighboring node Nj.
  • the counter Q6 makes it possible to make a sixth count Rj of the number of sixth data packets whose node Nj is the source, and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node N1.
  • each node Ni broadcasts all of its counters Sj, Dij, Oij, Mj, Mij, Rj has any neighbor node Nj.
  • the diffusion of the values of the counters in the network allows each node Ni to check the coherence of the values.
  • the comparison of the counters of a node N with those of its neighboring nodes Nj makes it possible to check the conservation of the data streams that is to say to verify that everything that a node receives to a destination another node is well retransmitted.
  • FIGS. 4A to 4D illustrate examples of verification of the conservation of data streams at a node N1.
  • Figure 4A illustrates a first comparison of the counters of a node Ni with those of its neighboring nodes Nj 1, Nj2, Nj3, Nj4 to check the consistency of the node Ni.
  • the values of the Ni node counters must be consistent, that is, the total number of packets received by the Node to another node must be equal to the total number of packets that were retransmitted by that node.
  • Ni node when a link (Ni, Nj) does not exist, the values of the counters can be considered as zero.
  • the coherence of the node Ni can be confirmed when the following equality is verified:
  • FIGS. 4B to 4D illustrate the comparison of the counters of a node N with those of its neighbors Nj to check the coherence by link.
  • a node Ni or Nj hatched schematically represents a source node or a destination node.
  • a node Ni whose representation is not particular (i.e. which is not hatched schematically) represents any node of the network.
  • FIG. 4B illustrates a second comparison of the counters of a node Ni with those of its neighbors Nj.
  • the second comparison is made between on the one hand the sum of the first count Sj and the second count Oij of the number of data packets sent by the node Ni on one side of the oriented link (Ni, Nj), and on the other hand the sum of the third count Dji and the fourth count Iji of the number of data packets received by the neighbor node Nj on the other side of the oriented link (Ni, Nj).
  • the link coherence according to FIG. 4B is given by the following equation:
  • FIG. 4C illustrates a third comparison between, on the one hand, the fifth count Mij of the number of data packets transmitted by the node N1 to its neighbor Nj and, on the other hand, the third count Dji of the number of data packets received by the neighboring node Nj from the node N1 and which is intended for it. More formally, the coherence by link according to FIG. 4C is given by the following equation:
  • FIG. 4D illustrates a fourth comparison between, on the one hand, the first count Sij of the number of data packets transmitted by the node Ni as a source to its neighbor node Nj and, on the other hand, the sixth count Pji of the number of packets of data received by this neighbor Nj from the node N1. More formally, the coherence by link according to Figure 4D is given by the following equation:
  • the fourth comparison corresponds to a symmetrical case compared to the third comparison.
  • an intermediate node can not send data packets to a neighboring node without counting them to hide the fact that it has removed the same number of packets destined for the latter node, which a node declares having issued himself to a neighboring node must actually be received as such by him.
  • the counters of a node are not coherent, then we can affirm that the sending node is malicious or more particularly selfish.
  • the counters of a node on a link are not coherent with the counters of the neighboring node at the other end of the link, then one can suspect that the sending node is malicious, saturated or defective.
  • the evaluation of the loss of data packets in an ad hoc network does not assume the hardware used (one or more interfaces, omnidirectional or unidirectional antenna). It is mainly based on the principle of stream conservation, and intervenes at the network or link layer of the OSI model.
  • the counting values at a node N i are updated at each processing of a data packet according to whether the node N or the direct neighbor node of the oriented link corresponds to a source, a destination or an intermediate of this data packet.
  • the node Ni increments the count Oij.
  • the node Nj is the destination, then the node Ni increments the count Mij.
  • the node N1 increments the count Dij. Moreover, if the node Nj is the source, then the node Ni also increments the count Rj.
  • the node Ni increments the count Mj and that counting Oik. Moreover, if the node Nj is the source, then the node Ni also increments the Rj. In addition, if the node Nk is the destination, then the node Ni also increments the count Mik.
  • the node Ni is a source node and the node Nj the node Nj is the next node to which the data packet is sent, then the node Ni increments the count Sij. Moreover, if the node Nj is the destination, then the node Ni increments the count Mij.
  • the invention also relates to a computer program downloadable from a communication network comprising code instructions for performing the steps of the evaluation method according to the invention when it is executed on a computer, a microprocessor or an electronic chip.
  • This computer program can be stored on a computer readable medium.
  • This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any other form desirable shape.
  • the invention also relates to a computer-readable information medium, comprising instructions of a computer program as mentioned above.
  • the information carrier may be any object or device capable of storing the program.
  • the medium may comprise storage means, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording medium, for example a floppy disk or a disk. hard.
  • the information carrier may be a transmissible medium such as an electrical or optical signal, which may be carried by radio or other means.
  • the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

The invention relates to a method for estimating the loss of at least one data packet in the context of data packets exchanged between the nodes of an ad hoc network. It is characterised in that it comprises the following steps implemented by a node (Ni) of the ad hoc network or estimation node: determining first values for numbering the data packets exchanged between said node (Ni) and at least one direct neighbouring node (nj); receiving second predetermined numbering values through said at least one direct neighbouring node (Nj); comparing the first numbering values with the second numbering values; and estimating the loss of data packets through said at leas one direct neighbouring node on the basis of said comparison.

Description

Titre de l'invention Title of the invention

Système et procédé d'évaluation de la perte de paquets de données dans un réseau ad hoc.System and method for evaluating the loss of data packets in an ad hoc network.

Domaine technique de l'inventionTechnical field of the invention

L'invention se rapporte au domaine des réseaux ad hoc et plus particulièrement, à l'évaluation de la perte de paquets de données dans un tel réseau.The invention relates to the field of ad hoc networks and more particularly to the evaluation of the loss of data packets in such a network.

Arrière-plan de l'inventionBackground of the invention

Les réseaux ad hoc sont des réseaux formés spontanément par un ensemble de nœuds pouvant être mobiles (par exemple ordinateurs personnels stationnaires ou portables, assistants personnels, téléphones mobiles, etc) munis de cartes réseau sans fil et situés dans le voisinage d'une partie d'entre eux. Pour communiquer avec les nœuds situés hors de sa propre portée, un nœud doit donc passer par des nœuds intermédiaires.Ad hoc networks are networks formed spontaneously by a set of nodes that can be mobile (eg stationary or portable personal computers, personal assistants, mobile phones, etc.) equipped with wireless network cards and located in the vicinity of a part of the network. 'between them. To communicate with nodes outside its own scope, a node must pass through intermediate nodes.

Cette communication à plusieurs sauts, que l'on appelle « multihop » nécessite l'utilisation de protocoles et algorithmes de routage afin de permettre à chaque nœud de savoir à quel voisin transmettre les données à destination d'un nœud distant. Les réseaux ad hoc apportent une solution dans les situations où une infrastructure filaire n'existe pas ou n'est pas envisagée ou pas envisageable comme par exemple pour l'organisation des secours dans des zones sinistrées. I ls peuvent aussi être utilisés pour accéder à des services particuliers dans des lieux publics.This multi-hop communication, which is called "multihop" requires the use of protocols and routing algorithms to allow each node to know which neighbor to transmit the data to a remote node. Ad hoc networks provide a solution in situations where a wired infrastructure does not exist or is not envisaged or not conceivable, for example for the organization of relief in disaster areas. They can also be used to access specific services in public places.

Les réseaux ad hoc mobiles (ou mobile ad hoc networks ou MANets en anglais) comportent des nœuds mobiles qui par définition ne sont pas contrôlés par une entité centrale. Le fait que les nœuds mobiles ne sont pas contrôlés par une seule entité implique que leur mouvement est très difficilement prévisible et que par conséquent la connectivité radio entre les nœuds change au cours du temps. On est donc en présence de réseaux dont la topologie est dynamique et dont les nœuds ont des caractéristiques particulières (par exemple ressources d'énergie et de calcul limitées). Ces spécificités des réseaux ad hoc font que les solutions de routage mises au point pour les réseaux filaires classiques ne sont pas du tout adaptées et de nouvelles techniques ont dû être élaborées.Ad hoc mobile networks (or mobile ad hoc networks or MANets in English) include mobile nodes that by definition are not controlled by a central entity. The fact that mobile nodes are not controlled by a single entity implies that their movement is very difficult to predict and therefore radio connectivity between the nodes changes over time. We are thus in the presence of networks whose topology is dynamic and whose nodes have particular characteristics (for example limited energy and calculation resources). These specificities of the ad hoc networks mean that the routing solutions developed for conventional wired networks are not at all adapted and new techniques have to be developed.

Actuellement, il existe plusieurs protocoles de routage dans les réseaux ad hoc. Les protocoles les plus aboutis permettent de trouver un chemin faisable en termes de connectivité vers n'importe quelle destination atteignable. La seule forme d'optimalité des chemins est la longueur en nombre de sauts, c'est-à-dire que les chemins fournis sont ceux qui offrent le plus petit nombre de sauts parmi les chemins possibles.Currently, there are several routing protocols in ad hoc networks. The most advanced protocols make it possible to find a feasible path in terms of connectivity to any reachable destination. The only form of path optimality is the number of hops, that is, the paths provided are those that offer the smallest number of hops among the possible paths.

D'une manière générale, on peut distinguer deux approches fondamentalement différentes pour résoudre le problème du routage dans un réseau ad hoc. La première approche concerne les protocoles réactifs et la deuxième approche concerne les protocoles proactifs.In general, one can distinguish two fundamentally different approaches to solve the problem of routing in an ad hoc network. The first approach is for reactive protocols and the second is for proactive protocols.

Selon un protocole réactif les nœuds ne maintiennent pas d'information particulière et ne recherchent une route que lorsqu'elle est requise, en inondant le réseau avec des messages destinés à trouver le chemin le plus court vers la destination. La réponse à cette requête de diffusion permet au nœud source d'obtenir les informations topologiques relatives à cette route.According to a reactive protocol, the nodes do not maintain particular information and seek a route only when it is required, by flooding the network with messages intended to find the shortest path to the destination. The response to this broadcast request allows the source node to obtain the topological information relating to this route.

En revanche, selon un protocole proactif, les nœuds échangent périodiquement des messages de contrôle qui leur permettent d'avoir l'information nécessaire en permanence pour joindre n'importe quelle destination, et d'être informés de l'évolution de la topologie du réseau. Parmi les protocoles proactifs, on peut noter l'existence de deux familles de protocoles qui permettent le maintien de tables de routage.On the other hand, according to a proactive protocol, the nodes periodically exchange control messages that allow them to have the necessary information permanently to reach any destination, and to be informed of the evolution of the topology of the network. . Among the proactive protocols, we can note the existence of two families of protocols that allow the maintenance of routing tables.

La première famille concerne les protocoles à vecteur de distance (ou distance vector en anglais) dans lesquels chaque nœud échange périodiquement ses tables de routage avec ses voisins directs et les met à jour en fonction des tables reçues.The first family concerns the distance vector protocols (or vector distance in English) in which each node periodically exchanges its routing tables with its direct neighbors and updates them according to the received tables.

La deuxième famille concerne les protocoles à état de liens (ou link state en anglais) dans lesquels les nœuds échangent des messages avec leurs voisins directs pour découvrir leur voisinage ou topologie locale et diffusent ensuite cette information à tout le réseau afin que tous les nœuds puissent recréer la topologie globale et calculer des routes vers toutes les destinations en recherchant le plus court chemin sur la topologie globale. On notera que les protocoles de routage pour réseaux ad hoc sont des algorithmes distribués qui ne supportent que l'apparition et la disparition des nœuds au cours du temps. Du point de vue d'un nœud dans le réseau, il est impossible de distinguer un nœud voisin qui s'arrête de fonctionner (à cause d'une panne ou simplement parce qu'il a été mis hors tension) d'un nœud voisin qui s'est éloigné et n'est plus joignable directement. Ainsi le seul type de panne supporté par les protocoles de routage est celui du type « arrêt de communication » (ou crash-fail en anglais). I l s'agit simplement d'un fonctionnement conforme aux spécifications du protocole. Cependant, il existe bon nombre d'autres pannes qui sont pour le moins indésirables. Si on suppose qu'un nœud peut faire absolument n'importe quoi (on appelle ce nœud un processus byzantin) on doit supposer a fortiori qu'il peut détourner le fonctionnement du protocole en créant, modifiant ou supprimant des messages de contrôle. I I est clair que la fiabilité de ces protocoles de routage repose intégralement sur l'hypothèse que les nœuds fonctionnent correctement. Or cette hypothèse n'est pas réaliste pour un réseau public ouvert où il n'existe pas de moyens pour garantir le bon fonctionnement de chaque nœud. Bien entendu, on peut utiliser des moyens cryptographiques pour sécuriser les réseaux ad hoc. Un tel exemple est décrit parThe second family concerns link state protocols in which nodes exchange messages with their immediate neighbors to discover their neighborhood or local topology and then broadcast this information to the entire network so that all nodes can recreate the global topology and calculate routes to all destinations by searching for the shortest path on the global topology. It should be noted that ad hoc network routing protocols are distributed algorithms that only support the appearance and disappearance of nodes over time. From the point of view of a node in the network, it is impossible to distinguish a neighboring node that stops working (because of a failure or simply because it has been powered off) of a neighboring node who has moved away and can not be reached directly. Thus the only type of failure supported by the routing protocols is the type of "stop communication" (or crash-fail in English). It is simply an operation in accordance with the protocol specifications. However, there are many other failures that are, to say the least, undesirable. If we suppose that a node can do absolutely anything (we call this node a Byzantine process) we must assume a fortiori that it can hijack the operation of the protocol by creating, modifying or deleting control messages. It is clear that the reliability of these routing protocols is based entirely on the assumption that the nodes are working properly. This assumption is not realistic for an open public network where there are no means to guarantee the proper functioning of each node. Of course, cryptographic means can be used to secure the ad hoc networks. Such an example is described by

Avramopoulos et al dans le document intitulé «An on-demand secure routing protocol résilient to byzantine failures » publié dans « ACM Workshop on Wireless Security (WiSe) » à Atlanta en 2004.Avramopoulos et al in the document entitled "An on-demand secure routing protocol resilient to byzantine failures" published in "ACM Workshop on Wireless Security (WiSe)" in Atlanta in 2004.

Toutefois, malgré la protection des communications et du protocole de routage, il est toujours possible qu'un nœud malveillant puisse décider de ne pas faire suivre un paquet de données dont il est un routeur intermédiaire et faire perdre des données à son émetteur. Ainsi, quand bien même le protocole permettrait d'assurer un fonctionnement du routage en présence de tels nœuds, il ne pourra empêcher ceux-ci ne serait-ce que de ne pas relayer les paquets de données des autres nœuds pour économiser son énergie. Par conséquent, il est important de détecter les pertes de paquets de données qu'elles soient intentionnelles ou non. Parmi les solutions proposées pour détecter les nœuds malveillants certaines se basent sur l'hypothèse que les nœuds utilisent des interfaces radio qui émettent toutes sur le même canal et ne sont munies que d'une antenne omnidirectionnelle. Une telle solution est proposée par Sergio Marti et al dans le document intitulé « Mitigating routing misbehaviour in mobile ad hoc networks » publié dans In Mobile Computing and Networking, pages 255-265 en 2000.However, despite the protection of communications and the routing protocol, it is still possible that a malicious node may decide not to forward a data packet of which it is an intermediate router and lose data to its issuer. Thus, even if the protocol would ensure routing operation in the presence of such nodes, it can not prevent them even if not to relay the data packets of other nodes to save energy. Therefore, it is important to detect data packet loss whether intentional or not. Some of the proposed solutions for detecting malicious nodes are based on the assumption that nodes use radio interfaces that all broadcast on the same channel and have only one omnidirectional antenna. Such a solution is proposed by Sergio Marti et al in the document entitled "Mitigating routing misbehavior in mobile ad hoc networks" published in In Mobile Computing and Networking, pages 255-265 in 2000.

Ainsi, lorsqu'un nœud transmet une trame de données pour un nœud voisin, tous les nœuds du voisinage sont en mesure de détecter cette transmission. Lorsqu'un nœud malveillant ne transmet pas une trame de données, l'absence de transmission est détectée par tous les voisins qui peuvent alors diffuser une alerte dans tout le réseau.Thus, when a node transmits a data frame for a neighbor node, all nodes in the neighborhood are able to detect that transmission. When a malicious node does not transmit a frame of data, the absence of transmission is detected by all the neighbors who can then broadcast an alert throughout the network.

Cependant, il existe plusieurs parades possibles. En effet, le nœud malveillant peut par exemple transmettre trop faiblement pour que le destinataire de la trame puisse la recevoir, mais assez fortement pour que les autres voisins (ou au moins une proportion suffisante d'entre eux) détectent bien la transmission et ne diffusent pas d'alerte. Par ailleurs, un nœud malveillant peut émettre des alertes à tort, pour accuser un voisin bienveillant et saper le fonctionnement de la détection.However, there are several possible parries. Indeed, the malicious node may for example transmit too weakly for the recipient of the frame can receive it, but strongly enough for the other neighbors (or at least a sufficient proportion of them) detect the transmission and do not broadcast an alert. In addition, a malicious node may erroneously warn, accuse a benevolent neighbor, and undermine the detection process.

D'autres solutions proposent un moyen d'inciter à la coopération des nœuds en introduisant un système de rémunération et en sécurisant les transactions en incluant les traitements sensibles dans une carte à puce supposée inviolable. Un tel exemple est proposé par LeventeOther solutions offer a way to encourage cooperation nodes by introducing a compensation system and secure transactions including sensitive processing in a smart card supposed inviolable. Such an example is proposed by Levente

Buttyan et al dans le document intitulé «Enforcing service availability in mobile ad- hoc WANs, dans Proceedings of the First IEEBACM Workshop on Mobile Ad Hoc Networking and Computing Mobil HOC, à Boston MA,Buttyan et al in the document entitled Enforcing service availability in mobile ad-hoc WANs, in Proceedings of the First IEEBACM Workshop on Mobile Ad Hoc Networking and Computing Mobil HOC, Boston MA,

USA, 2000.USA, 2000.

Toutefois, cette solution impose l'utilisation d'un matériel particulier qui présente une contrainte très forte pour un réseau ad hoc.However, this solution imposes the use of a particular material which presents a very strong constraint for an ad hoc network.

Objet et résumé de l'inventionObject and summary of the invention

La présente invention concerne un procédé d'évaluation d'une perte de paquets de données échangés entre des nœuds d'un réseau ad hoc, le procédé selon l'invention comportant les étapes suivantes, mises en œuvre par un nœud du réseau ad hoc, dit nœud évaluateur : - détermination de premières valeurs de dénombrement au niveau d'un nœud de paquets de données échangés entre ledit nœud et au moins un nœud voisin direct,The present invention relates to a method of evaluating a loss of data packets exchanged between nodes of an ad hoc network, the method according to the invention comprising the following steps, implemented by a node of the ad hoc network, said evaluator node: - determining first count values at a node of data packets exchanged between said node and at least one direct neighbor node,

- réception de deuxièmes valeurs de dénombrement déterminées par ledit au moins un nœud voisin direct, - comparaison des premières valeurs de dénombrement avec les deuxièmes valeurs de dénombrement, etreceiving second count values determined by said at least one direct neighbor node; comparing first count values with the second count values; and

- évaluation de la perte de paquets de données par ledit au moins un nœud voisin direct en fonction de ladite comparaison.evaluating the loss of data packets by said at least one direct neighbor node as a function of said comparison.

Ce procédé permet de détecter des liens sur lesquels les données sont perdues, par exemple de façon intentionnelle, et ainsi fournir un moyen pour contourner les nœuds malveillants ou égoïstes dans un protocole de routage. De plus, ce procédé est évolutif, n'impose pas de contraintes fortes car il ne fait pas d'hypothèses particulières sur la couche matérielle sous-jacente. Un tel procédé peut être mis en œuvre dans un réseau ad hoc qui comporte une propriété d'intégrité garantissant l'intégrité des paquets de données échangés entre les nœuds du réseau, par exemple au moyen de solutions cryptographiques.This method makes it possible to detect links on which the data are lost, for example intentionally, and thus provide a way to circumvent malicious or selfish nodes in a routing protocol. In addition, this process is evolutionary, does not impose strong constraints because it makes no particular assumptions on the underlying hardware layer. Such a method can be implemented in an ad hoc network that has an integrity property ensuring the integrity of the data packets exchanged between the nodes of the network, for example by means of cryptographic solutions.

Avantageusement, le procédé selon l'invention comporte une mise à jour de l'évaluation de la perte intentionnelle de paquets de données.Advantageously, the method according to the invention comprises an update of the evaluation of the intentional loss of data packets.

Ainsi, le procédé peut s'adapter à tout comportement imprévisible des nœuds et à une topologie dynamique du réseau ad hoc.Thus, the method can adapt to any unpredictable behavior of the nodes and to a dynamic topology of the ad hoc network.

Avantageusement, le procédé selon l'invention comporte une diffusion des premières valeurs de dénombrement à d'autres nœuds dudit réseau ad hoc.Advantageously, the method according to the invention comprises a diffusion of the first count values to other nodes of said ad hoc network.

Avantageusement, le procédé comporte une recherche d'une route entre un nœud source et un nœud destination contournant un ou plusieurs nœuds intermédiaires présentant une perte de paquets de données. Ceci permet de trouver une route plus fiable vers toute destination.Advantageously, the method comprises searching for a route between a source node and a destination node bypassing one or more intermediate nodes presenting a loss of data packets. This helps to find a more reliable route to any destination.

Selon un mode de réalisation particulier de l'invention, la détermination de valeurs de dénombrement de paquets de données échangé entre ledit nœud et l'un de ses nœuds voisins directs comporte tout ou partie des comptages suivants :According to a particular embodiment of the invention, the determination of counting values of data packets exchanged between said node and one of its direct neighbor nodes comprises all or part of the following counts:

-un premier comptage du nombre de premiers paquets de données transmis sur un lien orienté entre ledit nœud et le nœud voisin et dont ledit nœud est la source, -un deuxième comptage du nombre de deuxièmes paquets de données transmis sur le lien orienté entre ledit nœud et le nœud voisin et dont ledit nœud n'est pas la source,a first count of the number of first data packets transmitted on a link oriented between said node and the neighboring node and of which said node is the source, a second count of the number of second data packets transmitted on the link oriented between said node and the neighboring node and of which said node is not the source,

-un troisième comptage du nombre de troisièmes paquets de données transmis sur le lien orienté entre le nœud voisin et ledit nœud et dont ledit nœud est la destination,a third count of the number of third data packets transmitted on the link oriented between the neighboring node and said node and of which said node is the destination,

-un quatrième comptage du nombre de quatrièmes paquets de données transmis sur le lien orienté entre le nœud voisin et ledit nœud et dont ledit nœud n'est pas la destination, -un cinquième comptage du nombre de cinquièmes paquets de données transmis sur le lien orienté entre ledit nœud et le nœud voisin Nj et dont le nœud voisin est la destination, eta fourth count of the number of fourth data packets transmitted on the link oriented between the neighboring node and said node and whose said node is not the destination; a fifth count of the number of fifth data packets transmitted on the oriented link; between said node and the neighboring node Nj and whose neighbor node is the destination, and

-un sixième comptage du nombre de sixièmes paquets de données transmis sur le lien orienté entre le nœud voisin et ledit nœud et dont le nœud voisin est la source.a sixth count of the number of sixth data packets transmitted on the link oriented between the neighboring node and said node and whose neighboring node is the source.

Ainsi, les nœuds du réseau peuvent facilement vérifier la conservation de flots de paquets de données.Thus, the nodes of the network can easily check the conservation of data packet streams.

La comparaison du dénombrement au niveau dudit nœud peut comporter tout ou partie des comparaisons suivantes : -une première comparaison entre d'une part la somme de quatrièmes comptages de paquets de données reçus par ledit nœud depuis ses voisins directs et à destination d'un autre nœud et d'autre part la somme de deuxièmes comptages de paquets retransmis par ledit nœud, -une deuxième comparaison entre d'une part la somme du premier comptage et du deuxième comptage du nombre de paquets de données émis par ledit nœud d'un côté du lien orienté, et d'autre part la somme du troisième comptage et du quatrième comptage du nombre de paquets de données reçus par le nœud voisin de l'autre côté dudit lien orienté, -une troisième comparaison entre d'une part le cinquième comptage du nombre de paquets de données transmis par ledit nœud à destination de son nœud voisin et d'autre part le troisième comptage du nombre de paquets de données reçus par ledit voisin depuis ledit nœud et qui lui est destiné, etThe comparison of the count at said node may comprise all or part of the following comparisons: a first comparison between, on the one hand, the sum of fourth counts of data packets received by said node from its direct neighbors and destined for another node and secondly the sum of second counts of packets retransmitted by said node, a second comparison between on the one hand the sum of the first count and the second count of the number of data packets sent by said node on one side the oriented link, and secondly the sum of the third count and the fourth count of the number of data packets received by the neighboring node on the other side of said oriented link, a third comparison between the fifth count on the one hand the number of data packets transmitted by said node to its neighbor node and on the other hand the third count of the number of data packets received by said neighbor from said node and which is intended for it, and

-une quatrième comparaison entre d'une part le premier comptage du nombre de paquets de données transmis par ledit nœud en tant que source vers son nœud voisin et d'autre part le sixième comptage du nombre de paquets de données reçus par ledit nœud voisin depuis ledit nœud.a fourth comparison between, on the one hand, the first count of the number of data packets transmitted by said node as a source to its neighbor node and, on the other hand, the sixth count of the number of data packets received by said neighboring node since said node.

Ainsi, chaque nœud peut facilement effectuer les vérifications de cohérence des différents comptages afin d'estimer la fiabilité de chaque nœud et chaque lien du réseau.Thus, each node can easily perform the consistency checks of the different counts to estimate the reliability of each node and each network link.

Selon une particularité de l'invention, les premières valeurs de dénombrement au niveau dudit nœud évaluateur sont mises à jour à chaque traitement d'un paquet de données selon que ledit nœud évaluateur ou le nœud voisin direct correspond à une source, une destination ou un intermédiaire dudit paquet de données.According to one particularity of the invention, the first counting values at the said evaluating node are updated each time a data packet is processed, depending on whether the said evaluating node or the direct neighbor node corresponds to a source, a destination or a destination. intermediate of said data packet.

Avantageusement, la diffusion des premières valeurs de dénombrement à d'autres nœuds du réseau est réalisée de manière périodique. L'invention vise également un système d'évaluation d'une perte d'au moins un paquet de données, des paquets de données échangés entre des nœuds d'un réseau ad hoc, le système comportant : -des moyens de détermination de premières valeurs de dénombrement, agencés pour dénombrer au niveau d'un nœud des paquets de données échangés entre ledit nœud et au moins un nœud voisin direct,Advantageously, the diffusion of the first count values to other nodes of the network is carried out periodically. The invention also relates to a system for evaluating a loss of at least one data packet, data packets exchanged between nodes of an ad hoc network, the system comprising: means for determining first values for counting, at node level, data packets exchanged between said node and at least one direct neighbor node,

-des moyens de réception, agencés pour recevoir des deuxièmes valeurs de dénombrement déterminées par au moins un nœud voisin direct, -des moyens de comparaison, agencés pour comparer les premières valeurs de dénombrement avec les deuxièmes valeurs de dénombrement, et -des moyens d'évaluation, agencés pour évaluer une perte de paquets de données par au moins un nœud voisin direct en fonction de ladite comparaison.receiving means, arranged to receive second count values determined by at least one direct neighboring node; comparison means, arranged to compare the first counting values with the second counting values; and evaluation means, arranged to evaluate a loss of data packets by at least one direct neighboring node as a function of said comparison.

L'invention vise aussi un nœud d'un réseau ad hoc, le nœud comportant :The invention also aims at a node of an ad hoc network, the node comprising:

-des moyens de détermination de premières valeurs de dénombrement, agencés pour dénombrer des paquets de données échangés avec au moins un nœud voisin direct,means for determining first counting values, arranged for counting data packets exchanged with at least one direct neighboring node,

-des moyens de réception, agencés pour recevoir des deuxièmes valeurs de dénombrement déterminées par ledit au moins un nœud voisin direct,reception means, arranged to receive second count values determined by said at least one direct neighboring node,

-des moyens de comparaison, agencés pour comparer les premières valeurs de dénombrement avec les deuxièmes valeurs de dénombrement, etcomparison means, arranged to compare the first count values with the second count values, and

-des moyens d'évaluation, agencés pour évaluer une perte de paquets de données par ledit au moins un nœud voisin direct en fonction de ladite comparaison.evaluation means, arranged to evaluate a loss of data packets by said at least one direct neighboring node as a function of said comparison.

L'invention vise aussi un programme informatique téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par microprocesseur, comprenant des instructions de codes pour l'exécution des étapes du procédé d'évaluation de la perte de paquets de données dans un réseau ad hoc selon au moins l'une des caractéristiques ci-dessus, lorsqu'il est exécuté sur un ordinateur ou un microprocesseur.The invention also relates to a computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by microprocessor, comprising code instructions for the execution of the steps of the method of evaluation of the loss. data packets in an ad hoc network according to at least one of the above features, when executed on a computer or a microprocessor.

Brève description des dessinsBrief description of the drawings

D'autres particularités et avantages de l'invention ressortiront à la lecture de la description faite, ci-après, à titre indicatif mais non limitatif, en référence aux dessins annexés, sur lesquels :Other features and advantages of the invention will appear on reading the description given below, by way of indication but not limitation, with reference to the accompanying drawings, in which:

-la figure 1 illustre de manière schématique un réseau ad hoc formé par un ensemble de nœuds, selon l'invention ; -la figure 2 illustre de manière schématique un système d'évaluation de la perte de paquets de données dans un réseau ad hoc de la figure 1 ;FIG 1 schematically illustrates an ad hoc network formed by a set of nodes, according to the invention; FIG. 2 schematically illustrates a system for evaluating the loss of data packets in an ad hoc network of FIG. 1;

-la figure 3 illustre de façon plus détaillée un exemple du système d'évaluation de la figure 2 ; etFIG. 3 illustrates in more detail an example of the evaluation system of FIG. 2; and

-les figures 4A à 4D illustrent des exemples de vérification de la conservation des flots de données au niveau d'un nœud selon l'invention.FIGS. 4A to 4D illustrate examples of verification of the conservation of data streams at a node according to the invention.

Description détaillée de modes de réalisation La figure 1 illustre un exemple selon l'invention d'un réseau ad hoc formé par un ensemble de nœuds N1 ,..Ni, Nj, ... Nn de portées P1 , ..,Pi, Pj, ...Pn respectivement. Ainsi, pour communiquer avec les nœuds situés hors de sa propre portée, un nœud doit donc passer par des nœuds intermédiaires. A titre d'exemple, le nœud N1 peut communiquer avec le nœud Nn en passant par les nœuds intermédiaires N2, ..,Nj suivant plusieurs sauts de communications.DETAILED DESCRIPTION OF EMBODIMENTS FIG. 1 illustrates an example according to the invention of an ad hoc network formed by a set of nodes N1,... Ni, Nj,... Nn of ranges P1, .., Pi, Pj , ... Pn respectively. Thus, to communicate with the nodes located outside its own range, a node must therefore pass through intermediate nodes. For example, the node N1 can communicate with the node Nn through the intermediate nodes N2, .., Nj following several communications hops.

On notera qu'un nœud Ni (mobile ou fixe) peut être muni d'une carte réseau sans fil et peut correspondre à un ordinateur stationnaire ou portable, assistant personnel, téléphone mobile, capteur ou sonde etc. Un nœud voisin d'un nœud Ni est un nœud situé dans la zone de couverture de celui-ci. I l est donc en portée de transmission du nœud Ni. Un nœud voisin direct est un nœud qui se trouve à un saut, au sens du protocole de routage.Note that a node Ni (mobile or fixed) may be provided with a wireless network card and may correspond to a stationary or portable computer, personal assistant, mobile phone, sensor or probe etc. A neighbor node of a node Ni is a node located in the coverage area thereof. I l is therefore in transmission range of the node Ni. A direct neighbor node is a node that is at a jump, in the sense of the routing protocol.

De préférence, la communication entre les nœuds peut être réalisée selon un protocole ou algorithme de routage proactif (par exemple à vecteur de distance ou à état de liens) qui permet à chaque nœud de savoir à quel nœud voisin transmettre les données à destination d'un nœud distant. En variante, la communication entre les nœuds peut être réalisée selon un protocole de routage réactif. Conformément à l'invention, la figure 2 illustre de manière schématique un système d'évaluation de la perte de paquets de données parmi ceux échangés entre des nœuds d'un réseau ad hoc.Preferably, the communication between the nodes can be carried out according to a protocol or proactive routing algorithm (for example with a distance vector or a link state) which enables each node to know which neighbor node to transmit the data to. a remote node. Alternatively, the communication between the nodes can be performed according to a reactive routing protocol. In accordance with the invention, FIG. 2 schematically illustrates a system for evaluating the loss of data packets among those exchanged between nodes of an ad hoc network.

Dans la suite, un nœud qui fait perdre intentionnellement un paquet de données destiné à un autre nœud est appelé un « nœud égoïste ». En effet, un nœud égoïste peut décider de ne pas faire suivre un paquet de données dont il est un routeur intermédiaire et faire perdre des données au nœud émetteur du paquet de données pour par exemple économiser sa propre énergie. Bien entendu, il peut exister d'autres motivations pour ne pas relayer le trafic d'autres nœuds, mais les effets en sont les mêmes. Ainsi, un nœud égoïste peut dérouter le bon fonctionnement d'un réseau ad hoc.In the following, a node that intentionally loses a data packet destined for another node is called a "selfish node". Indeed, an egoistic node may decide not to forward a data packet of which it is an intermediate router and lose data to the node transmitting the data packet for example to save its own energy. Of course, there may be other motivations for not relaying traffic from other nodes, but the effects are the same. Thus, a selfish knot can baffle the proper functioning of an ad hoc network.

Par ailleurs, on suppose que le réseau ad hoc comporte une propriété d'intégrité garantissant l'intégrité de messages de contrôle ou des paquets de données échangés entre les nœuds du réseau.In addition, it is assumed that the ad hoc network has an integrity property that guarantees the integrity of control messages or data packets exchanged between network nodes.

Plus particulièrement, on suppose que chaque nœud est authentifiable et que l'intégrité de données échangées entre les nœuds est garantie dans tout le réseau.More specifically, it is assumed that each node is authenticatable and that the integrity of data exchanged between the nodes is guaranteed throughout the network.

A titre d'exemple, la propriété d'intégrité du réseau ad hoc peut être réalisée par un moyen cryptographique connu adapté pour garantir la confidentialité et l'intégrité des données des communications entre les nœuds du réseau. Par ailleurs, ce même moyen cryptographique peut être employé pour empêcher des nœuds malveillants ou malfonctionnants de falsifier leur identité ou de modifier le contenu des messages de contrôles émis par d'autres nœuds. Plus encore, il est possible de garantir que l'information contenue dans un message de contrôle est correcte et que le nœud émetteur du message de contrôle n'y a pas publié de fausses informations. Un nœud malveillant ne peut donc ni falsifier son identité ni altérer les informations contenues dans le message d'un autre nœud. Dans un but de simplification, le système de la figure 2 montre uniquement deux nœuds voisins Ni et Nj communiquant entre eux par l'intermédiaire d'un lien Lij. Bien entendu, les nœuds Ni et Nj sont deux nœuds voisins quelconques du réseau. Par ailleurs, on notera que la figure 2 est également une illustration des principales étapes du procédé d'évaluation d'une perte d'au moins un paquet de données dans un réseau ad hoc selon un mode particulier de réalisation de l'invention.For example, the integrity property of the ad hoc network can be realized by known cryptographic means adapted to guarantee the confidentiality and the integrity of the data of the communications between the nodes of the network. Moreover, this same cryptographic means can be used to prevent malicious or malfunctioning nodes from falsifying their identity or modifying the contents of control messages sent by other nodes. Moreover, it is possible to guarantee that the information contained in a control message is correct and that the node transmitting the control message has not published false information. A malicious node can not falsify its identity or alter the information contained in the message of another node. For the sake of simplification, the system of FIG. 2 only shows two neighboring nodes Ni and Nj communicating with each other via a link Lij. Of course, the nodes Ni and Nj are any two neighboring nodes of the network. Furthermore, it will be noted that FIG. 2 is also an illustration of the main steps of the method of evaluating a loss of at least one data packet in an ad hoc network according to a particular embodiment of the invention.

Dans la suite on note (Ni, Nj) le lien orienté du nœud Ni vers son nœud voisin Nj et on note (Nj, Ni) le lien orienté du nœud Nj vers Ni. Chacun des nœuds Ni et Nj comprend des moyens de dénombrement 1 i, 1j, des moyens de diffusion/réception 3i, 3j, des moyens de comparaison 5i, 5j et des moyens d'évaluation 7i, 7j.In the following we note (Ni, Nj) the oriented link of the node Ni to its neighbor node Nj and we note (Nj, Ni) the oriented link of the node Nj to Ni. Each of the nodes Ni and Nj comprises counting means 1 i, 1j, diffusion / reception means 3i, 3j, comparison means 5i, 5j and evaluation means 7i, 7j.

Ainsi, en se plaçant au niveau du nœud Ni, les moyens de dénombrement 1 i de ce nœud Ni dénombrent les paquets de données échangés entre lui et au moins un nœud voisin direct Nj. Plus particulièrement, les moyens de dénombrement 1 i peuvent déterminer un ensemble de valeurs de dénombrement ou compteurs CM à Q6 (voir figure 3) par nœud ou par lien qui compte le nombre de paquets de données transmis/ reçus par nœud ou par lien. Avantageusement, le nœud Ni dénombre les paquets de données échangés entre lui et chaque nœud voisin direct Nj.Thus, by placing itself at the node Ni, the counting means 1 i of this node Ni count the data packets exchanged between it and at least one direct neighboring node Nj. More particularly, the counting means 1 i can determine a set of counting values or counters CM to Q6 (see Figure 3) per node or link that counts the number of data packets transmitted / received per node or link. Advantageously, the node Ni counts the data packets exchanged between it and each direct neighboring node Nj.

Les moyens de diffusion/ réception 3i du nœud Ni permettent la diffusion des valeurs de dénombrement à d'autres nœuds du réseau en utilisant un quelconque protocole de routage ad hoc. A titre d'exemple, la diffusion peut être assurée par un protocole de routage ad hoc du type OLSR (pour "Optimized Link State Routing") ou DSR (pour "Dynamic Source Routing") standardisé par le groupe « MANET ». Les moyens de diffusion/réception permettent en outre la réception de valeurs de dénombrement déterminées par un autre nœud. En particulier, chaque nœud Ni peut diffuser les valeurs de ses compteurs à ses nœuds voisins Nj à « un saut », c'est-à-dire ses nœuds voisins directs, à « deux sauts », à « n sauts » ou à tout le réseau ad hoc. Par ailleurs, chaque nœud Ni peut diffuser les valeurs de ses compteurs de manière périodique selon une période de diffusion prédéterminée. Cette période de diffusion peut correspondre à un paramètre du système et peut dépendre de la taille du réseau ad hoc, du volume de trafic et de la précision avec laquelle on veut détecter les nœuds malveillants ou égoïstes. Ainsi, chaque nœud Ni reçoit également les valeurs des compteurs déterminés par des nœuds voisins Nj ou éventuellement par tous les autres nœuds et peut ainsi effectuer des vérifications de cohérence afin d'estimer la fiabilité de chaque lien et de chaque nœud.The broadcast / reception means 3i of the node N1 allow the dissemination of the counting values to other nodes of the network using any ad hoc routing protocol. For example, the broadcast can be provided by an ad hoc routing protocol of the type OLSR (for "Optimized Link State Routing") or DSR (for "Dynamic Source Routing") standardized by the group "MANET". The broadcast / reception means further allow the reception of count values determined by another node. In particular, each node Ni may broadcast the values of its counters to its neighboring nodes Nj at "a jump", that is to say its direct neighboring nodes, at "two jumps", "n jumps" or at any other time. the ad hoc network. Furthermore, each node Ni may broadcast the values of its counters periodically according to a predetermined diffusion period. This broadcast period may be a system parameter and may depend on the size of the ad hoc network, the amount of traffic, and the accuracy with which malicious or selfish nodes are to be detected. Thus, each node Ni also receives the values of the counters determined by neighboring nodes Nj or possibly by all the other nodes and can thus carry out consistency checks in order to estimate the reliability of each link and of each node.

En effet, les moyens de comparaison 5i du nœud Ni comparent les valeurs de dénombrement des paquets de données au niveau du nœud Ni avec les valeurs de dénombrement déterminées par d'autres nœuds. Ainsi, les moyens d'évaluation 7i du nœud Ni évaluent le niveau de la perte de paquets de données réalisée par les autres nœuds en fonction de la comparaison des compteurs entre les différents nœuds. Ainsi, une valeur relative à la fiabilité de chaque lien et de chaque nœud peut être évaluée en fonction du résultat de la comparaison des compteurs entre les différents nœuds. Avantageusement, cette valeur de fiabilité peut être utilisée en tant que métrique dans la détermination de chemins suffisamment fiables entre deux nœuds. Ainsi, on peut rechercher une route plus ou moins fiable entre un nœud source et un nœud destination en contournant éventuellement un ou plusieurs nœuds égoïstes ou présentant des disfonctionnements.Indeed, the comparison means 5i of the node N1 compare the counting values of the data packets at the node N1 with the counting values determined by other nodes. Thus, the evaluation means 7i of the node N1 evaluate the level of the loss of data packets performed by the other nodes as a function of the comparison of the counters between the different nodes. Thus, a value relating to the reliability of each link and of each node can be evaluated according to the result of the comparison of the counters between the different nodes. Advantageously, this reliability value can be used as a metric in the determination of sufficiently reliable paths between two nodes. Thus, one can search a more or less reliable route between a source node and a destination node by possibly bypassing one or more selfish nodes or having malfunctions.

Avantageusement, l'évaluation de la perte de paquets de données est constamment mise à jour afin de s'adapter à tout comportement imprévisible des nœuds et à la topologie dynamique du réseau ad hoc.Advantageously, the evaluation of the loss of data packets is constantly updated in order to adapt to any unpredictable behavior of the nodes and the dynamic topology of the ad hoc network.

La figure 3 illustre de façon plus détaillée un exemple du système d'évaluation de la perte de paquets de données dans un réseau ad hoc.Figure 3 illustrates in more detail an example of the system for evaluating the loss of data packets in an ad hoc network.

Selon cet exemple, les moyens de dénombrement 1 i du nœud Ni déterminent les compteurs CM à Q6 et les moyens de dénombrement 1j du nœud Nj déterminent les compteurs Cj 1 à Cj6. Tous les nœuds maintiennent des compteurs sur chacun des liens vers chacun de leurs voisins directs. Ainsi chaque nœud Ni du réseau dispose de six compteurs par lien orienté (Ni, Nj) ou (Nj, Ni), soit douze compteurs par lien Lij non orienté.According to this example, the counting means 1 i of the node N 1 determine the counters CM to Q6 and the counting means 1j of the node Nj determine the counters Cj 1 to Cj6. All nodes maintain counters on each of the links to each of their direct neighbors. Thus each node Ni of the network has six counters per oriented link (Ni, Nj) or (Nj, Ni), or twelve counters per link Lij undirected.

Par exemple, le dénombrement de paquets de données échangés entre le nœud Ni et chacun de ses nœuds voisins directs Nj peut être réalisé par l'intermédiaire des compteurs CM à Q6.For example, the counting of data packets exchanged between the node N1 and each of its direct neighboring nodes Nj can be carried out via the counters CM to Q6.

En effet, le compteur CM permet de réaliser un premier comptage Sij du nombre de premiers paquets de données dont le nœud Ni est la source, et qui sont transmis sur un arc ou lien orienté (Ni, Nj) entre le nœud Ni et le nœud voisin Nj. Le compteur Q2 permet de réaliser un deuxième comptage Oij du nombre de deuxièmes paquets de données dont le nœud Ni n'est pas la source, et qui sont transmis sur le lien orienté (Ni, Nj) entre le nœud Ni et le nœud voisin Nj.Indeed, the counter CM makes it possible to perform a first count Sij of the number of first data packets whose node Ni is the source, and which are transmitted on an arc or oriented link (Ni, Nj) between the node Ni and the node neighbor Nj. The counter Q2 makes it possible to perform a second count Oij of the number of second data packets whose node Ni is not the source, and which are transmitted on the oriented link (Ni, Nj) between the node Ni and the neighboring node Nj .

Le compteur Q3 permet de réaliser un troisième comptage Dij du nombre de troisièmes paquets de données dont le nœud Ni est la destination (i.e. la destination finale), et qui sont transmis sur le lien orienté (Nj, Ni) entre le nœud voisin Nj et le nœud Ni.The counter Q3 makes it possible to make a third count Dij of the number of third data packets whose node Ni is the destination (ie the final destination), and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node Ni.

Le compteur Q4 permet de réaliser un quatrième comptage Mj du nombre de quatrièmes paquets de données dont le nœud Ni n'est pas la destination, et qui sont transmis sur le lien orienté (Nj, Ni) entre le nœud voisin Nj et le nœud Ni.The counter Q4 makes it possible to carry out a fourth count Mj of the number of fourth data packets whose node Ni is not destination, and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node N1.

Le compteur Q5 permet de réaliser un cinquième comptage Mij du nombre de cinquièmes paquets de données dont le nœud Nj est la destination, et qui sont transmis sur le lien orienté (Ni, Nj) entre le nœud Ni et le nœud voisin Nj.The counter Q5 makes it possible to carry out a fifth count Mij of the number of fifth data packets whose node Nj is the destination, and which are transmitted on the oriented link (Ni, Nj) between the node N1 and the neighboring node Nj.

Finalement, le compteur Q6 permet de réaliser un sixième comptage Rj du nombre de sixièmes paquets de données dont le nœud Nj est la source, et qui sont transmis sur le lien orienté (Nj, Ni) entre le nœud voisin Nj et le nœud Ni.Finally, the counter Q6 makes it possible to make a sixth count Rj of the number of sixth data packets whose node Nj is the source, and which are transmitted on the oriented link (Nj, Ni) between the neighboring node Nj and the node N1.

Ensuite, chaque nœud Ni diffuse l'ensemble de ses compteurs Sj, Dij, Oij, Mj, Mij, Rj a tout nœud voisin Nj. La diffusion des valeurs des compteurs dans le réseau permet à chaque nœud Ni de vérifier la cohérence des valeurs. En outre, la confrontation des compteurs d'un nœud Ni avec ceux de ses nœuds voisins Nj permet de vérifier la conservation des flots de données c'est-à-dire de vérifier que tout ce qu'un nœud reçoit à destination d'un autre nœud est bien retransmis.Then, each node Ni broadcasts all of its counters Sj, Dij, Oij, Mj, Mij, Rj has any neighbor node Nj. The diffusion of the values of the counters in the network allows each node Ni to check the coherence of the values. In addition, the comparison of the counters of a node N with those of its neighboring nodes Nj makes it possible to check the conservation of the data streams that is to say to verify that everything that a node receives to a destination another node is well retransmitted.

En effet, les figures 4A à 4D illustrent des exemples de vérification de la conservation des flots de données au niveau d'un nœud Ni.Indeed, FIGS. 4A to 4D illustrate examples of verification of the conservation of data streams at a node N1.

Rus particulièrement, la figure 4A illustre une première comparaison des compteurs d'un nœud Ni avec ceux de ses nœuds voisins Nj 1 , Nj2, Nj3, Nj4 pour vérifier la cohérence du nœud Ni. Les valeurs des compteurs du nœud Ni doivent être cohérentes, c'est-à-dire que le nombre total de paquets reçus par le nœud Ni à destination d'un autre nœud doit être égal au nombre total de paquets qui a été retransmis par ce nœud Ni. On notera que, lorsqu'un lien (Ni, Nj) n'existe pas, les valeurs des compteurs peuvent être considérées comme nulles. Ainsi, selon l'exemple de la figure 4A, la cohérence du nœud Ni peut être confirmée lorsque l'égalité suivante est vérifiée :Rus particularly, Figure 4A illustrates a first comparison of the counters of a node Ni with those of its neighboring nodes Nj 1, Nj2, Nj3, Nj4 to check the consistency of the node Ni. The values of the Ni node counters must be consistent, that is, the total number of packets received by the Node to another node must be equal to the total number of packets that were retransmitted by that node. Ni node. Note that when a link (Ni, Nj) does not exist, the values of the counters can be considered as zero. Thus, according to the example of FIG. 4A, the coherence of the node Ni can be confirmed when the following equality is verified:

I ij1 + I ij2 + I ij3 + I ij4 = Oij 1 + Oij2 + Oij3 + Oij4. Plus généralement, cette première comparaison est réalisée entre d'une part la somme de quatrièmes comptages Mj de paquets de données reçus par le nœud Ni depuis ses voisins directs et à destination d'un autre nœud et d'autre part la somme de deuxièmes comptages Oij de paquets retransmis par le nœud Ni. Plus formellement, la cohérence par nœud est donnée par l'équation suivante : V/ , ∑/(/ = ∑O(/I ij1 + I ij2 + I ij3 + I ij4 = Oij 1 + Oij2 + Oij3 + Oij4. More generally, this first comparison is made between on the one hand the sum of fourth counts Mj of data packets received by the node Ni from its direct neighbors and to another node and secondly the sum of second counts Oij of packets retransmitted by the node Ni. More formally, the coherence per node is given by the following equation: V /, Σ / (/ = ΣO (/

Les figures 4B à 4D illustrent la confrontation des compteurs d'un nœud Ni avec ceux de ses voisins Nj pour vérifier la cohérence par lien. On notera qu'un nœud Ni ou Nj schématisé de manière hachurée représente un nœud source ou un nœud destination. Par ailleurs, un nœud Ni dont la représentation n'a rien de particulier (i.e. qui n'est pas schématisé de manière hachurée) représente un nœud quelconque du réseau.FIGS. 4B to 4D illustrate the comparison of the counters of a node N with those of its neighbors Nj to check the coherence by link. It will be noted that a node Ni or Nj hatched schematically represents a source node or a destination node. On the other hand, a node Ni whose representation is not particular (i.e. which is not hatched schematically) represents any node of the network.

En particulier, la figure 4B illustre une deuxième comparaison des compteurs d'un nœud Ni avec ceux de ses voisins Nj. La deuxième comparaison est réalisée entre d'une part la somme du premier comptage Sj et du deuxième comptage Oij du nombre de paquets de données émis par le nœud Ni d'un côté du lien orienté (Ni, Nj), et d'autre part la somme du troisième comptage Dji et du quatrième comptage Iji du nombre de paquets de données reçus par le nœud voisin Nj de l'autre côté du lien orienté (Ni, Nj). Plus formellement, la cohérence par lien selon la figure 4B est donnée par l'équation suivante :In particular, FIG. 4B illustrates a second comparison of the counters of a node Ni with those of its neighbors Nj. The second comparison is made between on the one hand the sum of the first count Sj and the second count Oij of the number of data packets sent by the node Ni on one side of the oriented link (Ni, Nj), and on the other hand the sum of the third count Dji and the fourth count Iji of the number of data packets received by the neighbor node Nj on the other side of the oriented link (Ni, Nj). More formally, the link coherence according to FIG. 4B is given by the following equation:

Vi Vj , Sij + Oij — Dji + IjiVi Vj, Sij + Oij - Dji + Iji

Autrement dit, les valeurs des compteurs d'un nœud Ni par rapport à un lien Lij doivent être en accord avec les valeurs des compteurs du nœud Nj à l'autre extrémité par rapport à ce même lien Lij. Ainsi ce qui est émis d'un côté, que le nœud Ni en soit la source ou pas, doit correspondre à ce qui est reçu de l'autre, que le nœud Nj en soit la destination ou pas. La figure 4C illustre une troisième comparaison entre d'une part le cinquième comptage Mij du nombre de paquets de données transmis par le nœud Ni à destination de son voisin Nj et d'autre part le troisième comptage Dji du nombre de paquets de données reçus par le nœud voisin Nj depuis le nœud Ni et qui lui est destiné. Plus formellement, la cohérence par lien selon la figure 4C est donnée par l'équation suivante :In other words, the values of the counters of a node Ni with respect to a link Lij must be in agreement with the values of the counters of the node Nj at the other end with respect to this same link Lij. Thus, what is emitted on one side, whether the node Ni is its source or not, must correspond to what is received from the other, whether the node Nj is its destination or not. FIG. 4C illustrates a third comparison between, on the one hand, the fifth count Mij of the number of data packets transmitted by the node N1 to its neighbor Nj and, on the other hand, the third count Dji of the number of data packets received by the neighboring node Nj from the node N1 and which is intended for it. More formally, the coherence by link according to FIG. 4C is given by the following equation:

Vi Vj , MiJ = DJiVi Vj, MiJ = DJi

Autrement dit, pour qu'un nœud intermédiaire ne puisse pas déclarer les paquets de données qu'il supprime comme ayant été à sa propre destination, ce qu'un nœud Ni déclare ayant été à destination de son nœud voisin Nj doit être effectivement reçu par celui-ci.In other words, for an intermediate node to be unable to declare the data packets that it deletes as having been at its own destination, what a node N1 declares having been destined for its neighbor node Nj must actually be received by this one.

La figure 4D illustre une quatrième comparaison entre d'une part le premier comptage Sij du nombre de paquets de données transmis par le nœud Ni en tant que source vers son nœud voisin Nj et d'autre part le sixième comptage Pji du nombre de paquets de données reçus par ce voisin Nj depuis le nœud Ni. Plus formellement, la cohérence par lien selon la figure 4D est donnée par l'équation suivante :FIG. 4D illustrates a fourth comparison between, on the one hand, the first count Sij of the number of data packets transmitted by the node Ni as a source to its neighbor node Nj and, on the other hand, the sixth count Pji of the number of packets of data received by this neighbor Nj from the node N1. More formally, the coherence by link according to Figure 4D is given by the following equation:

Vi Vj , SiJ = PjiVi Vj, SiJ = Pji

Ainsi, la quatrième comparaison correspond à un cas symétrique par rapport à la troisième comparaison. Autrement dit, pour qu'un nœud intermédiaire ne puisse pas envoyer des paquets de données vers un nœud voisin sans les comptabiliser pour masquer le fait qu'il a supprimé le même nombre de paquets à destination de ce dernier, ce qu'un nœud déclare avoir émis lui-même vers un nœud voisin doit être effectivement reçu comme tel par lui. Dans le cas où les compteurs d'un nœud ne sont pas cohérents, alors on peut affirmer que le nœud émetteur est malveillant ou plus particulièrement égoïste. Par ailleurs, dans le cas où les compteurs d'un nœud sur un lien ne sont pas cohérents avec les compteurs du nœud voisin à l'autre extrémité du lien, alors on peut suspecter que le nœud émetteur est malveillant, saturé ou défectueux.Thus, the fourth comparison corresponds to a symmetrical case compared to the third comparison. In other words, so that an intermediate node can not send data packets to a neighboring node without counting them to hide the fact that it has removed the same number of packets destined for the latter node, which a node declares having issued himself to a neighboring node must actually be received as such by him. In the case where the counters of a node are not coherent, then we can affirm that the sending node is malicious or more particularly selfish. On the other hand, in the case where the counters of a node on a link are not coherent with the counters of the neighboring node at the other end of the link, then one can suspect that the sending node is malicious, saturated or defective.

Ainsi, l'évaluation de la perte de paquets de données dans un réseau ad hoc selon l'invention, ne fait pas d'hypothèse sur le matériel utilisé (une ou plusieurs interfaces, antenne omnidirectionnelle ou unidirectionnelle). Elle est principalement basée sur le principe de la conservation des flots, et intervient au niveau de la couche Réseau ou Liaison du modèle OSI .Thus, the evaluation of the loss of data packets in an ad hoc network according to the invention does not assume the hardware used (one or more interfaces, omnidirectional or unidirectional antenna). It is mainly based on the principle of stream conservation, and intervenes at the network or link layer of the OSI model.

Avantageusement, les valeurs de dénombrement au niveau d'un nœud Ni sont mises à jour à chaque traitement d'un paquet de données selon que le nœud Ni ou le nœud voisin direct du lien orienté correspond à une source, une destination ou un intermédiaire de ce paquet de données.Advantageously, the counting values at a node N i are updated at each processing of a data packet according to whether the node N or the direct neighbor node of the oriented link corresponds to a source, a destination or an intermediate of this data packet.

En effet, au cas où le nœud Ni n'est pas un nœud source et que le nœud Nj est le nœud suivant vers lequel le paquet de données est envoyé, alors le nœud Ni incrémente le comptage Oij. De plus, si le nœud Nj est la destination, alors, le nœud Ni incrémente le comptage Mij.Indeed, in the case where the node Ni is not a source node and the node Nj is the next node to which the data packet is sent, then the node Ni increments the count Oij. Moreover, if the node Nj is the destination, then the node Ni increments the count Mij.

Au cas où le nœud Ni est un nœud destination et que le nœud Nj est le nœud précédent depuis lequel le paquet de données est reçu, alors le nœud Ni incrémente le comptage Dij. De plus, si le nœud Nj est la source, alors, le nœud Ni incrémente également le comptage Rj.In the case where the node N1 is a destination node and the node Nj is the previous node from which the data packet is received, then the node N1 increments the count Dij. Moreover, if the node Nj is the source, then the node Ni also increments the count Rj.

Au cas où le nœud Ni est un nœud intermédiaire et que le nœud Nj est le nœud précédent depuis lequel le paquet de données est reçu et le nœud Nk est le nœud suivant vers lequel il est transmis, alors le nœud Ni incrémente le comptage Mj ainsi que le comptage Oik. De plus, si le nœud Nj est la source, alors, le nœud Ni incrémente également le ∞mptage Rj. En outre, si le nœud Nk est la destination, alors, le nœud Ni incrémente également le comptage Mik.In the case where the node Ni is an intermediate node and the node Nj is the previous node from which the data packet is received and the node Nk is the next node to which it is transmitted, then the node Ni increments the count Mj and that counting Oik. Moreover, if the node Nj is the source, then the node Ni also increments the Rj. In addition, if the node Nk is the destination, then the node Ni also increments the count Mik.

Au cas où le nœud Ni est un nœud source et que le nœud Nj le nœud Nj est le nœud suivant vers lequel le paquet de données est envoyé, alors le nœud Ni incrémente le comptage Sij. De plus, si le nœud Nj est la destination, alors, le nœud Ni incrémente le comptage Mij.In the case where the node Ni is a source node and the node Nj the node Nj is the next node to which the data packet is sent, then the node Ni increments the count Sij. Moreover, if the node Nj is the destination, then the node Ni increments the count Mij.

L'invention vise aussi un programme informatique téléchargeable depuis un réseau de communication comprenant des instructions de codes pour l'exécution des étapes du procédé d'évaluation selon l'invention lorsqu'il est exécuté sur un ordinateur, un microprocesseur ou une puce électronique. Ce programme informatique peut être stocké sur un support lisible par ordinateur.The invention also relates to a computer program downloadable from a communication network comprising code instructions for performing the steps of the evaluation method according to the invention when it is executed on a computer, a microprocessor or an electronic chip. This computer program can be stored on a computer readable medium.

Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any other form desirable shape.

L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus.The invention also relates to a computer-readable information medium, comprising instructions of a computer program as mentioned above.

Le support d'informations peut être n'importe quel objet ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur.The information carrier may be any object or device capable of storing the program. For example, the medium may comprise storage means, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording medium, for example a floppy disk or a disk. hard.

D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé par radio ou par d'autres moyens. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. On the other hand, the information carrier may be a transmissible medium such as an electrical or optical signal, which may be carried by radio or other means. Alternatively, the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.

Claims

REVENDICATIONS 1. Procédé d'évaluation d'une perte d'au moins un paquet de données, des paquets de données étant échangés entre des nœuds d'un réseau ad hoc, caractérisé en ce qu'il comporte les étapes suivantes, mises en œuvre par un nœud (Ni) du réseau ad hoc, dit nœud évaluateur :A method for evaluating a loss of at least one data packet, data packets being exchanged between nodes of an ad hoc network, characterized in that it comprises the following steps, implemented by a node (Ni) of the ad hoc network, said evaluating node: - détermination de premières valeurs de dénombrement de paquets de données échangés entre ledit nœud (Ni) et au moins un nœud voisin direct (Nj), - réception de deuxièmes valeurs de dénombrement déterminées par ledit au moins un nœud voisin direct (Nj),determining first count values of data packets exchanged between said node (Ni) and at least one direct neighboring node (Nj), receiving second counting values determined by said at least one direct neighbor node (Nj), - comparaison des premières valeurs de dénombrement avec les deuxièmes valeurs de dénombrement, etcomparing the first enumeration values with the second enumeration values, and - évaluation de la perte de paquets de données par ledit au moins un nœud voisin direct en fonction de ladite comparaison.evaluating the loss of data packets by said at least one direct neighbor node as a function of said comparison. 2. Procédé selon la revendication 1 , caractérisé en ce qu'il comporte une diffusion des premières valeurs de dénombrement à d'autres nœuds dudit réseau ad hoc.2. Method according to claim 1, characterized in that it comprises a diffusion of the first count values to other nodes of said ad hoc network. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'il comporte une recherche d'une route entre un nœud source et un nœud destination contournant un ou plusieurs nœuds intermédiaires présentant une perte de paquets de données.3. Method according to claim 1 or 2, characterized in that it comprises a search of a route between a source node and a destination node bypassing one or more intermediate nodes with a loss of data packets. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la détermination de valeurs de dénombrement de paquets de données échangés entre le nœud évaluateur (Ni) et l'un de ses nœuds voisins directs (Nj) comporte tout ou partie des comptages suivants : -un premier comptage (Sj) d'un nombre de premiers paquets de données, transmis sur un lien orienté (Ni, Nj) entre ledit nœud (Ni) et ledit nœud voisin direct (Nj), et dont ledit nœud (Ni) est la source, -un deuxième comptage (Oij) d'un nombre de deuxièmes paquets de données, transmis sur le lien orienté (Ni, Nj) entre ledit nœud (Ni) et ledit nœud voisin direct (Nj), et dont ledit nœud (Ni) n'est pas la source, -un troisième comptage (Dij) d'un nombre de troisièmes paquets de données, transmis sur le lien orienté (Nj, Ni) entre ledit nœud voisin direct (Nj) et ledit nœud (Ni), et dont ledit nœud (Ni) est la destination, -un quatrième comptage (Mj) d'un nombre de quatrièmes paquets de données, transmis sur le lien orienté (Nj, Ni) entre ledit nœud voisin direct (Nj) et ledit nœud (Ni), et dont ledit nœud (Ni) n'est pas la destination, -un cinquième comptage (Mij) d'un nombre de cinquièmes paquets de données, transmis sur le lien orienté (Ni, Nj) entre ledit nœud (Ni) et ledit nœud voisin direct (Nj), et dont ledit nœud voisin direct (Nj) est la destination, et4. Method according to any one of claims 1 to 3, characterized in that the determination of counting values of data packets exchanged between the evaluating node (Ni) and one of its direct neighbor nodes (Nj) comprises all or part of the following counts: a first count (Sj) of a number of first data packets, transmitted on an oriented link (Ni, Nj) between said node (Ni) and said forward neighbor node (Nj), and said node (Ni) of which is the source, -a second count (Oij) of a number of second data packets, transmitted on the oriented link (Ni, Nj) between said node (Ni) and said forward neighbor node (Nj), and whose said node ( Ni) is not the source, -a third count (Dij) of a number of third data packets, transmitted on the oriented link (Nj, Ni) between said forward neighbor node (Nj) and said node (Ni) , and wherein said node (Ni) is the destination, -a fourth count (Mj) of a number of fourth data packets, transmitted on the oriented link (Nj, Ni) between said forward neighbor node (Nj) and said node (Ni), and whose said node (Ni) is not the destination, -a fifth count (Mij) of a number of fifth data packets, transmitted on the oriented link (Ni, Nj) between said node (Ni) and said forward neighbor node (Nj), and whose said forward neighbor node (Nj) is the destination, and -un sixième comptage (Rj) d'un nombre de sixièmes paquets de données, transmis sur le lien orienté (Nj, Ni) entre ledit nœud voisin direct (Nj) et ledit nœud (Ni), et dont ledit nœud voisin direct (Nj) est la source.a sixth count (Rj) of a number of sixth data packets, transmitted on the oriented link (Nj, Ni) between said direct neighboring node (Nj) and said node (Ni), and whose said direct neighboring node (Nj ) is the source. 5. Procédé selon la revendication 4, caractérisé en ce que la comparaison des valeurs du dénombrement au niveau dudit nœud (Ni) comporte tout ou partie des comparaisons suivantes : -une première comparaison entre d'une part la somme des quatrièmes comptages (Mj) de paquets de données reçus par ledit nœud (Ni) depuis ses voisins directs et à destination d'un autre nœud et d'autre part la somme des deuxièmes comptages (Oij) de paquets retransmis par ledit nœud (Ni), -une deuxième comparaison entre d'une part la somme du premier comptage (Sj) et du deuxième comptage (Oij) du nombre de paquets de données émis par ledit nœud (Ni) d'un côté du lien orienté (Ni, Nj), et d'autre part la somme du troisième comptage (Dji) et du quatrième comptage (Iji) du nombre de paquets de données reçus par le nœud voisin (Nj) de l'autre côté dudit lien orienté (Ni, Nj), -une troisième comparaison entre d'une part le cinquième comptage (Mij) du nombre de paquets de données transmis par ledit nœud (Ni) à destination de son nœud voisin (Nj) et d'autre part le troisième comptage (Dji) du nombre de paquets de données reçus par ledit voisin (Nj) depuis ledit nœud (Ni) et qui lui est destiné, et -une quatrième comparaison entre d'une part le premier comptage (Sj) du nombre de paquets de données transmis par ledit nœud (Ni) en tant que source vers son nœud voisin (Nj) et d'autre part le sixième comptage (Pji) du nombre de paquets de données reçus par ledit nœud voisin (Nj) depuis ledit nœud (Ni).5. Method according to claim 4, characterized in that the comparison of the counting values at said node (Ni) comprises all or part of the following comparisons: a first comparison between firstly the sum of the fourth counts (Mj) data packets received by said node (Ni) from its direct neighbors and destined for another node and secondly the sum of the second counts (Oij) of packets retransmitted by said node (Ni), -a second comparison between the sum of the first count (Sj) and the second count (Oij) of the number of packets of data transmitted by said node (Ni) on one side of the oriented link (Ni, Nj), and on the other hand the sum of the third count (Dji) and the fourth count (Iji) of the number of data packets received by the neighboring node (Nj) on the other side of said oriented link (Ni, Nj), a third comparison between on the one hand the fifth count (Mij) of the number of data packets transmitted by said node (Ni) to its neighbor node (Nj) and secondly the third count (Dji) of the number of data packets received by said neighbor (Nj) from said node (Ni) and which is intended for it, and a fourth comparison between firstly the count (Sj) of the number of data packets transmitted by said node (Ni) as a source to its neighbor node (Nj) and secondly the sixth count (Pji) of the number of data packets received by said neighbor node (Nj) from said node (Ni). 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce que les premières valeurs de dénombrement au niveau dudit nœud (Ni) évaluateur sont mises à jour à chaque traitement d'un paquet de données selon que ledit nœud (Ni) évaluateur ou le nœud voisin direct (Nj) correspond à une source, une destination ou un intermédiaire dudit paquet de données.6. Method according to any one of claims 1 to 5, characterized in that the first counting values at said evaluating node (Ni) are updated at each processing of a data packet according to whether said node (Ni ) evaluator or the immediate neighbor node (Nj) corresponds to a source, a destination or an intermediary of said data packet. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que la diffusion des premières valeurs de dénombrement à d'autres nœuds du réseau est réalisée de manière périodique.7. Method according to any one of claims 1 to 6, characterized in that the diffusion of the first count values to other nodes of the network is performed periodically. 8. Système d'évaluation d'une perte d'au moins un paquet de données, des paquets de données étant échangés entre des nœuds d'un réseau ad hoc, caractérisé en ce qu'il comporte : -des moyens de détermination de premières valeurs de dénombrement (1 i), agencés pour dénombrer au niveau d'un nœud (Ni) des paquets de données échangés entre ledit nœud (Ni) et au moins un nœud voisin direct (Nj), -des moyens de réception (3i), agencés pour recevoir des deuxièmes valeurs de dénombrement déterminées au moins un nœud voisin direct, -des moyens de comparaison (5i), agencés pour comparer les premières valeurs de dénombrement avec des deuxièmes valeurs de dénombrement, et -des moyens d'évaluation (7i), agencés pour évaluer par ledit nœud (Ni) la perte de paquets de données par au moins un nœud voisin direct en fonction de ladite comparaison.8. System for evaluating a loss of at least one data packet, data packets being exchanged between nodes of an ad hoc network, characterized in that it comprises: means for determining first counting values (1 i), arranged for counting at a node (Ni) data packets exchanged between said node (Ni) and at least one direct neighboring node (Nj), receiving means (3i), arranged to receive second determined count values at least one direct neighboring node, -comparison means (5i), arranged to compare the first count values with second count values, and - evaluation means (7i), arranged to evaluate by said node (Ni) the loss of data packets by at least one direct neighbor node according to said comparison. 9. Nœud d'un réseau ad hoc, caractérisé en ce qu'il comporte: -des moyens de détermination de premières valeurs de dénombrement (1 i), agencés pour dénombrer des paquets de données échangés avec au moins un nœud voisin direct (Nj),9. Node of an ad hoc network, characterized in that it comprises: means for determining first counting values (1 i), arranged for counting data packets exchanged with at least one direct neighboring node (Nj ) -des moyens de réception (3i), agencés pour recevoir des deuxièmes valeurs de dénombrement déterminées par ledit au moins un nœud voisin direct,receiving means (3i), arranged to receive second counting values determined by said at least one direct neighboring node, -des moyens de comparaison (5i), agencés pour comparer les premières valeurs de dénombrement avec les deuxièmes valeurs de dénombrements, etcomparison means (5i), arranged to compare the first count values with the second count values, and -des moyens d'évaluation (7i), agencés pour évaluer une perte de paquets de données par ledit au moins un nœud direct voisin en fonction de ladite comparaison.evaluation means (7i), arranged to evaluate a loss of data packets by said at least one neighboring direct node as a function of said comparison. 10. Programme informatique téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur, caractérisé en ce qu'il comprend des instructions de codes pour l'exécution des étapes du procédé d'évaluation d'une perte d'au moins un paquet de données dans un réseau ad hoc selon au moins l'une des revendications 1 à 7, lorsqu'il est exécuté sur un ordinateur ou un microprocesseur. 10. Computer program downloadable from a communication network and / or stored on a computer readable medium and / or executable by a microprocessor, characterized in that it comprises code instructions for performing the steps of the method of evaluating a loss of at least one data packet in an ad hoc network according to at least one of claims 1 to 7, when executed on a computer or a microprocessor.
PCT/FR2007/051650 2006-07-13 2007-07-12 System and method for estimating data packet loss in an ad hoc network Ceased WO2008078016A1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0652963A FR2903832A1 (en) 2006-07-13 2006-07-13 Data packet`s intentional loss evaluating method for e.g. mobile telephone, involves counting packets exchanged between node of network and direct neighboring node, and broadcasting values of counting to other nodes based on protocol
FR0652963 2006-07-13

Publications (1)

Publication Number Publication Date
WO2008078016A1 true WO2008078016A1 (en) 2008-07-03

Family

ID=37765054

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2007/051650 Ceased WO2008078016A1 (en) 2006-07-13 2007-07-12 System and method for estimating data packet loss in an ad hoc network

Country Status (2)

Country Link
FR (1) FR2903832A1 (en)
WO (1) WO2008078016A1 (en)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050105474A1 (en) * 2003-11-17 2005-05-19 Metzler Benjamin T. System and method for measuring per node packet loss in a wireless network

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2790349A1 (en) * 1999-02-26 2000-09-01 Thierry Grenot Digital communications network non intrusive loss factor/transfer rate measurement having information collected/stored analysed classifying digital packet flow and calculating identification signature then counting packet data.
US6973039B2 (en) * 2000-12-08 2005-12-06 Bbnt Solutions Llc Mechanism for performing energy-based routing in wireless networks
EP1844562A4 (en) * 2004-12-13 2009-12-23 Telcordia Licensing Company Ll Lightweight packet-drop detection for ad hoc networks

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050105474A1 (en) * 2003-11-17 2005-05-19 Metzler Benjamin T. System and method for measuring per node packet loss in a wireless network

Non-Patent Citations (9)

* Cited by examiner, † Cited by third party
Title
ANJUM F ET AL: "LiPaD: lightweight packet drop detection for ad hoc networks", VEHICULAR TECHNOLOGY CONFERENCE, 2004. VTC2004-FALL. 2004 IEEE 60TH LOS ANGELES, CA, USA 26-29 SEPT. 2004, PISCATAWAY, NJ, USA,IEEE, 26 September 2004 (2004-09-26), pages 1233 - 1237, XP010786820, ISBN: 0-7803-8521-7 *
AWERBUCH B ET AL: "AN ON-DEMAND SECURE ROUTING PROTOCOL RESILIENT TO BYZANTINE FAILURES", WISE. PROCEEDINGS OF THE 2002 ACM WORKSHOP ON WIRELESS SECURITY. ATLANTA, GA, SEPT. 28, 2002, PROCEEDINGS OF THE ACM WORKSHOP ON WIRELESS SECURITY, NEW YORK, NY : ACM, US, 28 September 2002 (2002-09-28), pages 21 - 30, XP001047060, ISBN: 1-58113-585-8 *
BRADLEY K A ET AL: "DETECTING DISRUPTIVE ROUTERS: A DISTRIBUTED NETWORK MONITORING APPROACH", IEEE NETWORK, IEEE SERVICE CENTER, NEW YORK, NY, US, vol. 12, no. 5, September 1998 (1998-09-01), pages 50 - 60, XP000875015, ISSN: 0890-8044 *
BRADLEY K A ET AL: "Detecting disruptive routers: a distributed network monitoring approach", SECURITY AND PRIVACY, 1998. PROCEEDINGS. 1998 IEEE SYMPOSIUM ON OAKLAND, CA, USA 3-6 MAY 1998, LOS ALAMITOS, CA, USA,IEEE COMPUT. SOC, US, 3 May 1998 (1998-05-03), pages 115 - 124, XP010280368, ISBN: 0-8186-8386-4 *
BUCHEGGER S ET AL: "Performance analysis of the CONFIDANT protocol (Cooperation Of Nodes: Fairness In Dynamic Ad-hoc Networks)", MOBIHOC 2002. PROCEEDINGS OF THE 3RD. ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING. LAUSANNE, SWITZERLAND, JUNE 9, 9 June 2002 (2002-06-09), pages 226 - 236, XP002369769, ISBN: 1-58113-501-7 *
BUTTYAN L ET AL: "Enforcing service availability in mobile ad-hoc wans Ad-Hoc WANs", MOBILE AND AD HOC NETWORKING AND COMPUTING, 2000. MOBIHOC. 2000 FIRST ANNUAL WORKSHOP ON 11 AUGUST 2000, PISCATAWAY, NJ, USA,IEEE, 2000, pages 87 - 96, XP010511737, ISBN: 0-7803-6534-8 *
IGNACY GAWEDZKI ET AL: "Proactive Resilience to Dropping Nodes in Mobile Ad Hoc Networks", TECHNOLOGIES FOR ADVANCED HETEROGENEOUS NETWORKS II LECTURE NOTES IN COMPUTER SCIENCE;;LNCS, SPRINGER BERLIN HEIDELBERG, BE, vol. 4311, 2006, pages 139 - 158, XP019051346, ISBN: 978-3-540-49364-8 *
MARTI S ET AL: "Mitigating Routing Misbehaviour in Mobile Ad Hoc Networks", MOBICOM. PROCEEDINGS OF THE ANNUAL INTERNATIONAL CONFERENCE ON MOBILE COMPUTING AND NETWORKING, XX, XX, 6 August 2000 (2000-08-06), pages 255 - 265, XP002366740 *
URPI A, BONUCELLI M, GIORDANO S: "Modelling cooperation in mobile ad hoc networks: a formal description of selfishness", WIOPT'03: MODELING AND OPTIMIZATION IN MOBILE, AD HOC AND WIRELESS NETWORKS, INRIA SOPHIA ANTIPOLIC FRANCE, 3 March 2003 (2003-03-03) - 5 March 2003 (2003-03-05), ftp://ftp-sop.inria.fr/maestro/WiOpt03PDFfiles/urpi10.pdf, XP002423055 *

Also Published As

Publication number Publication date
FR2903832A1 (en) 2008-01-18

Similar Documents

Publication Publication Date Title
Mota et al. Protocols, mobility models and tools in opportunistic networks: A survey
EP3066565B1 (en) Method and computer program for the off-site execution of computing tasks of an item of wireless equipment
Sahoo et al. Diagnosis of wireless sensor networks in presence of permanent and intermittent faults
EP3891959A1 (en) Gateway for communicating via radio network with at least one node and via a wired network, by means of a blockchain
EP2084552B1 (en) Method and device for the detection location of radio signal transmitters
EP3891678A1 (en) Device for communicating in a network of heterogeneous gateways via radio network with at least one node and via a long-distance network, with at least one recipient
EP3275217B1 (en) Communication method within a dynamic-depth cluster of communicating electronic devices, communicating electronic device implementing said method and associated system
FR2980939A1 (en) MULTI-SKIP ROUTING PROTOCOL
WO2008078016A1 (en) System and method for estimating data packet loss in an ad hoc network
EP2260481B1 (en) Information system and method for traffic in road network
WO2012131280A1 (en) Data communication in a sensor array
FR3040117A1 (en) METHODS FOR FREQUENCY RESOURCE ANALYSIS AND TRANSMIT FREQUENCY SELECTION IN A WIRELESS COMMUNICATION SYSTEM
Karthik et al. Trust based data gathering in wireless sensor network
WO2023099318A1 (en) Method for obtaining a value of a variable representative of the movement of a mobile terminal, device, and corresponding computer program
EP1418775A1 (en) Method for optimizing the accesses to a cellular radiocommunication network, corresponding system and device
Lundgren Implementation and real-world evaluation of routing protocols for wireless ad hoc networks
Förster et al. Opportunistic Networks
FR3051585B1 (en) METHOD AND SYSTEM FOR TRANSMITTING A GEOLOCALIZED ALERT TO A USER WITH A MOBILE COMMUNICATION TERMINAL
EP3811655B1 (en) Method for evaluating the energy consumption of a service unit in a communications network
FR2923971A1 (en) DETERMINING THE COORDINATES OF A NODE IN A NETWORK OF NODES.
FR3143820A1 (en) Communication and data processing methods for the implementation of a collaborative network, associated devices and systems
FR3160025A1 (en) Processes for certifying the occurrence of an event involving a user device
FR2939267A1 (en) Communication routing management method for home theatre type communication network, involves modifying routing of communication in network by selection of communication path along concentrated energy transmission mode
FR2965138A1 (en) METHOD, COMPUTER PROGRAM AND CONSTRAINT DEVICE FOR COMMUNICATING BETWEEN A MOBILE TERMINAL AND AT LEAST ANOTHER TERMINAL ACCORDING TO THEIR RELATIVE POSITION
WO2023067267A1 (en) Method for transmitting items of data in a mesh network and communication device in such a network

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 07871871

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

NENP Non-entry into the national phase

Ref country code: RU

122 Ep: pct application non-entry in european phase

Ref document number: 07871871

Country of ref document: EP

Kind code of ref document: A1