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/16—Communication route or path selection, e.g. power-based or shortest path routing based on transmission quality or channel quality based on interference
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L45/00—Routing or path finding of packets in data switching networks
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L45/00—Routing or path finding of packets in data switching networks
  • H04L45/12—Shortest path evaluation
  • H04L45/125—Shortest path evaluation based on throughput or bandwidth

Definitions

• the present invention relates to a method for calculating a path with a defined quality of service in a multi-hop network as well as network node management equipment. It has applications in the field of data exchange management over communication networks, in particular for real-time multimedia applications on ad hoc wireless networks, telephony on ad hoc networks, videoconferencing on ad hoc networks. It allows these applications to coexist with other classic applications such as web (the web), file transfer, etc.
• Routing involves finding a path between a source node and a destination node in a network. This path will be taken by packets of data addressed to the destination.
• a path is a series of links.
• a link is a physical connection that connects two neighboring nodes of the network.
• a metric on a link is a value associated with the state of the link at a given time.
• a metric on a path is a combination (addition, multiplication, minimum, or other function) of the metrics on each link composing the path.
• QoS refers to a set of measurable values that characterize a link between a source and a destination in a network, such as routing delay, maximum possible throughput, packet loss rate, and so on.
• One or more metrics in general are used in so-called quality of service routing, in which it is a question of finding a path respecting the value required by an application for each of these metrics.
• the present invention proposes that the estimation of the metrics is not separated from the calculation of the path itself, since the metrics of a link also depend on the other links that make up the calculated path.
• the metrics of a link also depend on the other links that make up the calculated path.
• the calculated paths meet the requirements of the applications that use them, since the level of quality of service they offer is sufficient. Therefore, applications can work properly.
• This ability to use sufficient quality of service paths ensures that communications between applications that use calculated paths do not use more resources than those offered by the network. Thus the saturation of the network is avoided.
• the resources offered by the network are better shared by the applications, which makes the coexistence of applications of different requirements possible.
• the invention relates to a qualitative data routing method in an ad hoc multi-hop communication network, said method making it possible to determine, as a function of a determinable communication quality criterion, at least one data path through links. between nodes, between a source node and a destination node of said network, the value of the quality criterion of a given path being computable as a function of at least one determinable link metric in said network, the links being able to interfere with each other during the passage of data.
• intra-flow interference is taken into account and for a communication quality criterion which is a minimum value B of bandwidth to be satisfied, an ad hoc network routing protocol is used.
• the interfering links are determined in the following manner:
• each node of the network determines a global conflict graph, defined as follows: each vertex of this global conflict graph represents a link in a partial global topology and each edge of this global conflict graph represents a conflict relationship between two links of the partial global topology, that is to say that these links are separated by at most H jumps according to the partial global topology;
• each node having a global conflict graph determines the maximum complete graphs, referred to as "cliques", of the global conflict graph, and said node determines the path in the network, in particular by solving the following linear system with the following integrality constraints:
• a total local topology of the network is determined
• a partial global topology of the network is determined
• the network is determined as follows:
• each node of the network determines a total local topology of the network comprising, on the one hand, all the nodes corresponding to its direct neighbors, called “one jump”, and all the direct neighbors of its direct neighbors, then called “two "jumps", and, on the other hand, all the links between himself and his neighbors at a jump and between his neighbors at a jump and their own neighbors at a jump; said topology being said local topology with two jumps,
• each node determines a subset of its neighbors, called "MPR" which allows it to join all its neighbors with two jumps and communicates periodically to its neighbors at a jump the list of neighbor (s) who has / have been determined as MPR;
• each node which has been determined as MPR by at least one neighbor periodically broadcasts in the network the list of the neighbor (s) who has chosen it as MPR, said list being referred to as the "MPR-S" list;
• each node reconstructs a partial global topology of the network comprising all the nodes and a set of links between the nodes making it possible to find at least one path to each other node of the network,
• the ad hoc network routing protocol used is OLSR, AODV, DSR TBRPF, or FSR,
• the steps of determining the partial global topology of the network and the conflict graph are carried out separately within a node, the conflict graph being determined after the determination of the partial global topology of the network,
• the empty capacity of each link adjacent to a node is determined by a method which effectively takes into account the conflicts existing between the neighboring links
• the proportion of empty capacity used by the existing links is determined by a method based on the counting of the amount of data sent on each link per unit of time
• the network is a radio wireless network
• the invention also relates to an equipment for managing a node of an ad hoc multi-hop communications network that is specially configured to operate according to the method described.
• Figure 1 which is a diagram of an exemplary wireless communication network with nodes and two paths between the departure nodes a and destination v,
• Figure 2 which is a diagram of another example of a wireless communication network with nodes and two paths between the departure nodes a and destination f.
• a node is at least a reception and retransmission equipment comprising calculation means for managing the flows passing through it.
• the node can be either equipment specifically dedicated to the network, or a equipment also providing other functions such as a microcomputer in a network of microcomputers.
• the node may receive data from one or more other nodes and retransmit them to one or more other nodes.
• the link between the nodes can be wired but it is preferably wireless and in particular radio type.
• the topology can evolve over time and the data pathways can also evolve over time. The management of the paths is done in a distributed way, each node participating in the management.
• a node When a node transmits on a link (eg o to p), no other node in the interference areas of o and p can transmit.
• the available capacity on a link therefore depends on the capabilities used by the links of which at least one end is in the interference zone of at least one end of the link.
• the available capacity of a path depends on the capabilities used by the links of which at least one end is in the interference zone of at least one end of at least one path link. To find satisfactory paths taking into account this phenomenon is therefore very complex and the existing solutions ignore this problem.
• paths are determined that offer at least a given available capacity, while taking into account the correlations between the capabilities of the links.
• network management computers execute calculation algorithms for this determination of the paths. For this, we determine the topology of the network, for example calculated by a proactive routing protocol such as OLSR and we return the path that satisfies the required bandwidth.
• the network topology is determined using a routing protocol for ad hoc networks.
• a routing protocol for ad hoc networks it is possible to use example the OLSR protocol for "Optimized Link State Routing", which works as follows:
• the nodes periodically exchange HELLO messages containing the list of neighboring nodes from which they have recently received a HELLO message;
• each node reconstructs in memory a total local topology of the network, containing all the direct neighbors, called “one jump”, and the neighbors of the neighbors, called “two jumps” "And all the links between himself and his neighbors at a jump and between his neighbors at a jump and their own neighbors at a jump;
• MPR multipoint relays
• each node which has been chosen as MPR by at least one neighbor periodically broadcasts in the network so-called TC messages ("Topology Control") containing the list of neighbors who have chosen it as MPR, and said "MPR-S" for "MPR-selectors";
• TC messages Topic Control
• each node reconstructs in memory a partial global topology of the network containing all the nodes and sufficient links between the nodes to make it possible to find a path to each node.
• One parameter of the solution is the number of hops H below which two links share the same capacity resource (bandwidth).
• bandwidth bandwidth
• nodes using a common radio medium the links can not all be used at the same time.
• each node maintains a conflict graph:
• each vertex of the conflict graph represents a link of the partial global topology
• each edge of the conflict graph represents a conflict relationship between two links of the partial global topology.
• K is the set of cliques of the conflict graph
• Cij is the vacuum capacity of the link (ij)
• B is the empty capacity portion already used.
• the available capacity on the path (a, b, c, d, e, f) is obtained by seeking the maximum value R 0 such that:
• the available capacity on (a, g, h, i, j, k, f) is calculated by looking for the maximum value R 1 such that:
• the capacities of these two paths are 1/12 and 1/6 respectively, thus determining that the second path is the best in terms of capacity.
• the existing techniques would have selected the first path as the best in terms of capacity.
• metrics are used. These metrics can be the capacity in bit / s, the number of hops separating a source from a destination, or the delay in routing packets from the source to the destination. These metrics can be combined together to define the quality criterion. As an example of a combination of metrics, the following can be cited:

Landscapes

• Engineering & Computer Science (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Mobile Radio Communication Systems (AREA)
• Data Exchanges In Wide-Area Networks (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=42269472

Family Applications (1)

Country Status (5)

Families Citing this family (10)

Family Cites Families (6)

• 2009
  • 2009-12-11 FR FR0958890A patent/FR2954028B1/fr not_active Expired - Fee Related
• 2010
  • 2010-12-10 JP JP2012542607A patent/JP2013513987A/ja active Pending
  • 2010-12-10 US US13/515,078 patent/US20120257545A1/en not_active Abandoned
  • 2010-12-10 EP EP10801651A patent/EP2510656A1/de not_active Withdrawn
  • 2010-12-10 WO PCT/FR2010/052669 patent/WO2011070304A1/fr not_active Ceased

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events