Routing protocol for ad hoc networks

• US 20050030921A1
• Filed: 07/23/2004
• Published: 02/10/2005
• Est. Priority Date: 07/25/2003
• Status: Active Grant

• Current Assignee: Royal Holloway And Bedford New College, Royal Holloway University of London
• Original Assignee: Royal Holloway University of London
• Inventors: Yau, Po-Wah
• Granted Patent: US 7,719,989 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A routing method for an ad hoc network is disclosed, the network comprising two or more nodes (A, B, C, D, E, F), and the method comprising: sending a message from a start node (A) to a finish node (F) via one or more intermediate nodes (B, C, D, E); each of the start node (A) and intermediate nodes (B, C, D, E) receiving an acknowledgement signal (AckB, AckC, AckD, AckE, AckF) from a one-hop neighbouring node when the one-hop neighbouring node receives the message from the start node (A;F) or intermediate nodes (B, C, D, E) and, in the case of the one-hop neighbouring node not being the finish node (F), the start node and intermediate nodes receiving an acknowledgement signal (AckC, AckD, AckE, AckF) from a two-hop neighbouring node when the two-hop neighbouring node receives the message from the one-hop neighbouring node.

Claims

1. A routing method for an ad hoc network, the network comprising two or more nodes, the method comprising sending a message from a start node to a finish node via one or more intermediate nodes forming an ad hoc path of communication through the network;

the start node receiving an acknowledgement signal from a one-hop neighbouring node when the one-hop neighbouring node receives the message from the start node, and the start node receiving an acknowledgement signal from a two-hop neighbouring node when the two-hop neighbouring node receives the message from said one-hop neighbouring node;

the or each intermediate node in the path of communication, in turn, receiving an acknowledgement signal from a respective one-hop neighbouring node downstream of it in said path when the respective one-hop neighbouring node receives the message from the respective intermediate node upstream in said path and, except in the case of the one-hop neighbouring node being the finish node, each intermediate node receiving an acknowledgement signal from a respective two-hop neighbouring node, which is downstream of it in said path, when the two-hop neighbouring node receives the message from the one-hop neighbouring node which is upstream of said two-hop neighbouring node in said path.

2. The routing method of claim 1, in which the message is a route packet and the start node is the originator node of the route packet and finish node is the destination node of the route packet.

3. The routing method of claim 1, in which the message is a data packet and the start node is the originator node of the data packet and the finish node is the destination node of the data packet.

4. The routing method of claim 1, in which the start node is the destination node of a data packet and the finish node is the originator node of the data packet;

and the message is a route reply message indicating that the destination node has received the data packet.

14. Software encoded in a machine-readable medium for implementing the method of claim 1.

16. Computer program control code adapted to carry out all the steps of the method of claim 1 on a node of the ad hoc network.

5. An ad hoc network comprising a start node, a finish node and one or more intermediate nodes, the nodes being configured to send a message from the start node to the finish mode via the intermediate nodes, wherein each of the start node and intermediate nodes is configured to receive an acknowledgement signal from a one-hop neighbouring node when the one-hop neighbouring node receives the message from a respective one of the start node and intermediate nodes and, in the case of the one-hop neighbouring node not being the finish node, each of the start node and intermediate nodes being configured to receive an acknowledgement signal from a respective two-hop neighbouring node when the two-hop neighbouring node receives the message from the respective one-hop neighbouring node.

6. A network as claimed in claim 5, in which each node is configured to broadcast a beacon message periodically to its 1-hop neighbouring node to indicate that it is still present and operational.

7. A network as claimed in claim 5, in which each node has a routing table including a set of addresses for its one-hop and two-hop neighbouring nodes.

8. A network as claimed in claim 7, in which the routing table, in use of the network, includes one or more reputation values, the or each reputation value representing how much a respective neighbouring node has been cooperating in the routing of messages.

9. A network as claimed in claim 7, in which the routing table includes a beacon value indicating the length of time since a beacon message has not been received.

10. A network as claimed in claim 9, in which the routing table includes a retry value indicating the number of times the node should resend the message to a 1-hop neighbouring node that has not responded with an acknowledgement signal.

11. A network as claimed in claim 10, in which the retry value for a 1-hop neighbouring node is determined from the reputation value of the 1-hop neighbouring node.

12. A network as claimed in claim 5, in which each message sent by a node is accompanied by a digital signature.

13. A node for use in an ad hoc network, the node being configured to receive an acknowledgement signal from a one-hop neighbouring node when the one-hop neighbouring node receives the message from said node and said node being configured to receive an acknowledgement signal from a two-hop neighbouring node when the two-hop neighbouring node receives the message from the one-hop neighbouring node receives the message from the one-hop neighbouring node.

15. Software encoded in a machine-readable medium for implementing operation of the node according to claim 13.