Opportunistic routing protocol in ad hoc networks

• US 8,027,259 B2
• Filed: 06/30/2006
• Issued: 09/27/2011
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Westphal, Cedric
• Primary Examiner(s): Bost; Dwayne
• Assistant Examiner(s): MAPA, MICHAEL Y
• Application Number:
  US11/479,548
• Publication Number:
  US 20080002640A1
• Time in Patent Office: 1,915 Days
• Field of Search: 370237-238, 370/338, 370/351, 370/395.31, 455/428, 455/445
• US Class Current: 370/238
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

An opportunistic ad hoc routing protocol system and method includes a dynamic ad hoc network having one or more nodes configured to communicate wirelessly with each other. Each node is configured to implement a routing protocol wherein a list of possible relay nodes is stored in each of the one or more nodes'"'"' routing tables. In addition, each node is configured to implement a protocol adapted to allow different nodes to receive the same packet. Further, each node is adapted to update the list of possible relay nodes in order to capture a change in the ad hoc network.

Claims

1. A method comprising:

receiving a broadcast message from a source node at a relay node;

receiving an additional copy of the broadcast message at the relay node from a forwarding node, wherein the additional copy of the broadcast message comprises a hop count that indicates a number of hops between the source node and the relay node via the forwarding node; and

creating, for the forwarding node, an additional entry in a route table of the relay node in response to determining that the hop count is less than a threshold value.

2. The method of claim 1, wherein the additional entry is a list pair identifying the forwarding node and the hop count.

3. The method of claim 1, wherein the broadcast message is a flooded broadcast AODV route request.

4. The method of claim 1, further comprising, after receiving the broadcast message at the relay node:

updating a received packet;

creating a route entry in the route table; and

rebroadcasting the updated packet to one or more neighboring relay nodes.

5. A method comprising:

receiving a broadcast message from a source node at a relay node;

receiving an additional copy of the broadcast message at the relay node from a forwarding node, wherein the additional copy of the broadcast message comprises a hop count that indicates a number of hops between the source node and the relay node via the forwarding node;

receiving a route reply message from a destination node at the relay node, wherein the relay node updates a route table to identify potential forwarding nodes;

sending an acknowledgment from the relay node to the destination node;

forwarding the route reply message to the source node;

comparing the hop count with one or more hop count values stored in the route table; and

creating, for the forwarding node, an additional entry in the route table in response to determining that the hop count is less than a threshold value.

6. The method of claim 5, further comprising, after receiving the broadcast message from the source node at the relay node:

creating an updated packet;

creating a route entry in the route table of the relay node; and

rebroadcasting the updated packet to one or more neighboring relay nodes.

7. The method of claim 5, wherein a MAC address of the relay node is included in a MAC header of the route reply message, and further comprising:

incrementing a hop count to the destination node by one;

inserting a value equal to the minimum number of hops to the source node in a header of a received packet; and

adding an entry to the route table of the relay node identifying a potential forwarding node to the destination node.

8. The method of claim 5, wherein an IP address of the relay node is included in an IP packet header of the route reply message, and further comprising:

incrementing a hop count to the destination node by one;

inserting a value equal to the minimum number of hops to the source node in a header of a received packet; and

adding an entry to the route table of the relay node identifying a potential forwarding node to the destination node.

9. The method of claim 5, wherein the relay node receives the route reply message via a local broadcast address, and further comprising:

in response to determining that the relay node is a candidate for node forwarding, updating a received packet and the route table of the relay node; and

sending an acknowledgment to the forwarding node.

10. A non-transitory computer readable medium storing computer-executable instructions that, when executed, cause a processor to at least perform:

receive a broadcast message from a source node at a relay node;

receive an additional copy of the broadcast message at the relay node from a forwarding node, wherein the additional copy of the broadcast message comprises a hop count that indicates a number of hops between the source node and the relay node via the forwarding node; and

create, for the forwarding node, an additional entry in a route table of the relay node in response to determining that the hop count is less than a threshold value.

11. The non-transitory computer readable medium of claim 10, wherein the computer-executable instructions, when executed, cause the processor, after receiving the broadcast message from the source node at the relay node, to:

create an updated packet;

create a route entry in the route table of the relay node; and

rebroadcast the updated packet to one or more neighboring relay nodes.

12. The non-transitory computer readable medium of claim 10, where the computer-executable instructions, when executed, cause the processor to:

receive a route reply message from a destination node at the relay node;

increment a hop count to the destination node by one;

insert a value equal to the minimum number of hops to the source node in a header of a received packet; and

add an entry to the route table of the relay node identifying a potential forwarding node to the destination node.

13. The non-transitory computer readable medium of claim 10, where the computer-executable instructions, when executed, cause the processor to:

receive a route reply message from a destination node at the relay node;

increment a hop count to the destination node by one in response to determining that an IP address of the relay node is included in an IP packet header of the route reply message;

insert a value equal to the minimum number of hops to the source node in a header of a received packet; and

add an entry to the route table of the relay node identifying a potential forwarding node to the destination node.

14. The non-transitory computer readable medium of claim 10, wherein the computer-executable instructions, when executed, cause the processor to:

receive a route reply message from a destination node at the relay node via a local broadcast address; and

in response to determining that the relay node is a candidate for node forwarding, update a received packet and the route table of the relay node; and

send an acknowledgment to the forwarding node.

15. An apparatus comprising:

a processor; and

a memory unit storing computer-executable instructions that, when executed by the processor, cause the apparatus to;

receive a broadcast message from a source node;

receive an additional copy of the broadcast message from a forwarding node, wherein the additional copy of the broadcast message comprises a hop count that indicates a number of hops from the source node to the apparatus via the forwarding node; and

create, for the forwarding node, an additional entry in a route table in response to determining that the hop count is less than a threshold value.

16. The apparatus of claim 15, wherein the computer-executable instructions, when executed, cause the apparatus, after receiving the broadcast message from the source node, to:

create an updated packet;

create a route entry in the route table; and

rebroadcast the updated packet to one or more neighboring relay nodes.

17. The apparatus of claim 15, wherein a MAC address of the apparatus is included in a MAC header of a route reply message, and the computer-executable instructions, when executed, cause the apparatus, after receiving the route reply message, to:

increment a hop count to a destination node by one;

insert a value equal to the minimum number of hops to the source node in a header of a received packet; and

add an entry to the route table identifying a potential forwarding node to the destination node.

18. The apparatus of claim 15, wherein an IP address of the apparatus is included in an IP packet header of a route reply message, and the computer-executable instructions, when executed, cause the apparatus, after receiving the route reply message, to:

increment a hop count to a destination node by one;

insert a value equal to the minimum number of hops to the source node in a header of a received packet; and

add an entry to the route table identifying a potential forwarding node to the destination node.

19. The apparatus of claim 15, wherein the apparatus receives a route reply message via a local broadcast address, and the computer-executable instructions, when executed, cause the apparatus, after receiving the route reply message, to:

in response to determining that the apparatus is a candidate for node forwarding, update a received packet and the route table; and

send an acknowledgment to the forwarding node.