Routing method in an ad hoc network

• US 7,924,796 B2
• Filed: 03/01/2007
• Issued: 04/12/2011
• Est. Priority Date: 03/03/2006
• Status: Active Grant

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Vu Duong, Thang, Kettaf, Noureddine, Hafid, Abouaissa, Lorenz, Pascal
• Primary Examiner(s): Lee, Andrew
• Application Number:
  US12/281,622
• Publication Number:
  US 20090073893A1
• Time in Patent Office: 1,503 Days
• Field of Search: 370/338, 370/465
• US Class Current: 370/338
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A routing method in an ad hoc network between a source node (S) and a destination node (M) to guarantee a required quality of service level between the source node and the destination node. The source node (S) sends a route request to the network, request containing required quality of service level and an initial value of cost function (Fg). A node receiving a route request sent by a neighbor node then refuses said request if node is not able to guarantee said required quality of service level, and sends over the network a route request containing required quality of service level and a value of cost function combining a value of the cost function received from a previous neighbor node and a value of The cost function calculated on a connection with a neighbor node. The destination node (M) sends a route response step by step to the source node (S) containing the cumulative value of the cost function (Fg) corresponding to a route formed by successive connections between the source node (S) and the destination node (M). The source node chooses the route between the source node (S) and the destination node (M) having the best cumulative cost function.

Claims

1. A routing method in an ad hoc network between a source node (S) and a destination node (M), wherein, to guarantee a required quality of service level between the source node and the destination node, the method comprises the steps of:

in a preliminary step;

(a) evaluating at each node of the network a quality of service level for each connection between said node and the neighbor nodes;

(b) establishing a cost function (F_g) representative of the cost in terms of resources necessary to guarantee a given quality of service level on a connection between a node and each of the neighbor nodes;

the source node (S) sending a route request to the network, said request containing said required quality of service level and an initial value of said cost function (F_g);

a node receiving a route request sent by a neighbor node then;

(a) refusing said request if said node is not able to guarantee said required quality of service level;

(b) sending over the network a route request containing said required quality of service level and a value of said cost function combining a value of the cost function received from a previous neighbor node and a value of the cost function calculated on a connection with a neighbor node;

the destination node (M) sending a route response step by step to the source node (S) containing the cumulative value of said cost function (F_g) corresponding to a route formed by successive connections between the source node (S) and the destination node (M); and

the source node choosing the route between the source node (S) and the destination node (M) having the best cumulative cost function.

2. The method according to claim 1, wherein, for each node of the network, the quality of service level on each connection between said node and the neighbor nodes is evaluated by means of a neighbor discovery message.

3. The method according to claim 1, wherein a node able to receive route requests sends a route request containing a value of said cost function combining the value of the cost function contained in a route request received first from a preceding neighbor node and a value of the cost function calculated on a connection with a neighbor node.

4. The method according to claim 1, wherein said route request contains a value of said cost function combining a value of the cost function received from a preceding neighbor node and a value of the cost function calculated on a connection with said preceding neighbor node.

5. The method according to claim 1, wherein said route request contains a value of said cost function combining a value of the cost function received from a preceding neighbor node and a value of the cost function calculated on a connection with a subsequent neighbor node.

6. The method according to claim 1, wherein said quality of service level is evaluated as a function of the bandwidth of said connection.

7. The method according to claim 6, wherein the cost function F_b associated with the bandwidth is given by the following equation, where B is the required bandwidth, B_max is the maximum bandwidth on said connection, and B_res is the residual bandwidth:

F_b=B/[B_max−

(B_res+B)].

8. The method according to claim 7, wherein said residual bandwidth is estimated from free times and busy times between two nodes.

9. The method according to claim 8, wherein said free times and said busy times are obtained from the IEEE 802.11 standard.

10. The method according to claim 1, wherein said quality of service level is evaluated as a function of the delay on said connection.

11. The method according to claim 10, wherein the cost function F_d associated with the delay is given by the following equation, in which D is the delay on said connection, D_max the total maximum delay supported, and Σ

_{i to j}D_i the sum of the cumulative delays on the connections i to j already traveled;

F_d=D/[D_max−

(Σ

_{i to j}D_i+D)].

12. The method according to claim 11, wherein said delay is estimated from measured times between a node sending a neighbor discovery message and the same node receiving a response message sent by a neighbor node.

13. The method according to claim 7, wherein said delay is estimated from measured times between a node sending a neighbor discovery message and the same node receiving a response message sent by a neighbor node, and wherein the cost function is a weighted sum of the cost functions F_b and F_d.