Method of routing in an ad hoc network

• US 7,570,602 B2
• Filed: 04/19/2005
• Issued: 08/04/2009
• Est. Priority Date: 04/20/2004
• Status: Expired due to Fees

• Current Assignee: Thales SA
• Original Assignee: Thales SA
• Inventors: Paul, Francois, Delattre, Michel
• Primary Examiner(s): Shah; Chirag G
• Assistant Examiner(s): Shivers; Ashley L
• Application Number:
  US11/108,911
• Publication Number:
  US 20060002312A1
• Time in Patent Office: 1,568 Days
• Field of Search: 370/254, 370/255, 370/256
• US Class Current: 370/254
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method for the routing of information in a network comprises several communication nodes that may be mobile, the routing being done by a route between a source node and a destination node through a set of wireless communication links between the nodes of the network, the entire set forming a graph wherein the method comprises at least one step in which the graph of the network is structured as a unicast two-way link in order to obtain the relationships existing between two nodes and form, during routing decisions, sub-graphs comprising arcs that connect two nodes, the arcs sharing one and the same set of properties.

Claims

1. A method of routing information in a network having several communication nodes that may be mobile, the routing being done on a route between a source node and a destination node through a set of wireless communication links between the network nodes, the method comprising steps of:

structuring a graph in each mobile node, by a link supervision entity on each mobile node, in a form of a bidirectional point-to-point (unicast two-way) link, obtaining substantially all the links Ri,j existing between two nodes Ni and Nj and to form sub-graphs during routing decisions, wherein arcs of these sub-graphs connecting two nodes, substantially share a same set of properties;

transmitting periodically, by the link supervision entity, packets including;

an identity of a sender node Ni; and

a list of the links Ri,j with neighboring node Nj, with characteristics of the links Ri,j;

receiving, by each link supervision entity, the transmitted packets;

determining, by each link supervision entity, all neighboring nodes in addition to any available communication resources in order to exchange packets therewith

transmitting, by a transport entity distributed on each node, information from the source node to the destination node as a function of a sub-graph selected by the source node; and

comparing, at a given node, the properties of the communications communication resources existing between this the given node and the expected properties of the links of the sub-graph considered and creating or breaking the logic links depending on whether or not the observed properties correspond to those expected.

2. The method according to claim 1, wherein the routing mechanism is of the on demand type and, during a phase of searching for a route, comprises propagating route requests only on links belonging to the sub-graph having the properties requested by the application that has made a call on the routing method.

3. The method according to claim 1, wherein transmitting information includes transmitting information packets, the method further comprising:

inserting quality of service QoS characteristics, required by the application making a call on the routing method, into a header of the packets by the source node or ingress node Ne,

interpreting or translating the information by intermediate nodes in order to route the information packet flowing in the network in compliance with the constraint of the sub-graph adapted to the request from the application, and

removing, at the egress node Ns, the information from the header.

4. The method according to claim 1, wherein, comparing the properties of the existing communication resources of the given node and the expected properties of the links includes applying a predefined margin by which the values being compared may differ.

5. The method according to claim 1, wherein, at a node, congestion is detected and policies of scheduling and pre-emption are implemented which, depending on priorities of data transportation required by the applications, define the possibilities of assigning resources to serve one individual stream to the detriment of another stream or to the detriment of one sub-graph in favor of another sub-graph.

6. The method according to claim 1, comprising a step of hop-by-hop resource reservation in a network in order to make a route static and separate from the evolution of the sub-graphs.

7. The routing method according to claim 1, performing a route search on demand applying a routing protocol.

8. The method according to claim 7, wherein the protocol is an AODV protocol.

9. The method according to claim 8, wherein the destination address parameter of the AODV PDUs is used to convey the quality of service or QoS characteristics.

10. The method according to claim 2, wherein transmitting information includes transmitting packets and comprises:

inserting quality of service QoS characteristics required by the application making a call on the routing method, into the header of the packets by the source node or ingress node Ne,

interpreting or translating the information by the intermediate nodes in order to route the information packet flowing in the network in compliance with the constraint of the sub-graph adapted to the request from the application, and

at the egress node Ns, removing the information from the header.

11. The method according to claim 10, wherein, during the comparing of characteristic values defining the properties, a predefined margin is applied.

12. The method according to claim 10, further comprising detecting congestion at a node, and implementing policies of scheduling and pre-emption that depending on priorities of data transportation required by the applications, define the possibilities of assigning resources to serve one individual stream to the detriment of another stream or to the detriment of one sub-graph in favor of another sub-graph.

13. The method according to claim 10, comprising a step of hop-by-hop resource reservation in a network in order to make a route static and separate from the evolution of the sub-graphs.

14. The method according to claim 2, comprising a step of hop-by-hop resource reservation in a network in order to make a route static and separate from the evolution of the sub-graphs.

15. The method according to claim 3, comprising a step of hop-by-hop resource reservation in a network in order to make a route static and separate from the evolution of the sub-graphs.