Routing protocol for ad hoc networks

• US 7,719,989 B2
• Filed: 07/23/2004
• Issued: 05/18/2010
• Est. Priority Date: 07/25/2003
• Status: Expired due to Fees

• Current Assignee: Royal Holloway And Bedford New College, Royal Holloway University of London
• Original Assignee: Royal Holloway And Bedford New College
• Inventors: Yau, Po-Wah
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Cehic; Kenan
• Application Number:
  US10/897,631
• Publication Number:
  US 20050030921A1
• Time in Patent Office: 2,125 Days
• Field of Search: 370/236, 370221-224, 370/241, 370/248, 370/312, 370/348, 370/249, 370/310, 370/395.2, 370/395.52, 455/455, 455/7, 455/11.1, 455/15, 455/41.2, 455/50, 455/73
• US Class Current: 370/248
• 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 neighboring node when the one-hop neighboring 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 neighboring 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 neighboring node when the two-hop neighboring node receives the message from the one-hop neighboring node.

Claims

1. A routing method for an ad hoc network, the network comprising three 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 generated by the one-hop neighouring 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 generated by the two-hop neighbouring node when the two-hop neighbouring node receives the message from said one-hop neighbouring node;

each intermediate node in the path of communication, in turn, receiving an acknowledgement signal generated by a respective one-hop neighbouring node downstream of it in said path, from the respective one-hop neighbouring node 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, generated by the 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;

wherein each acknowledgment signal is generated by its respective sending node and states, by using a digital signature which verifies the respective acknowledgement signal, that the sending node has received the message.

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. A computer readable medium encoded with software for implementing the method of claim 1.

5. An ad hoc network comprising a start node, a finish node and one or more intermediate nodes, the start node, a finish node and one or more intermediate 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, and generated by the 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, and generated by the two-hop neighbouring node, when the two-hop neighbouring node receives the message from the respective one-hop neighbouring node, wherein each acknowledgement signal is generated by the node sending the acknowledgment signal and states, by using a digital signature which verifies the respective acknowledgement signal, that the generating node has received the message.

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 one 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 a node should resend the message to a 1-hop neighbouring node that has not responded with a acknowledgement signal.

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

11. An ad hoc network comprising:

a start node, a finish node and one or more intermediate nodes, the start node, a finish node and one or more intermediate 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, and wherein each acknowledgment signal is verified using a digital signature, the acknowledgment signal being generated by the one-hop neighbouring node, when the one-hop neighbouring node receives the message from a respective one of the start node or 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 a second acknowledgement signal from a respective two-hop neighbouring node, the second acknowledgement signal being generated by the two-hop neighbouring node, when the two-hop neighbouring node receives the message from respective one-hop neighbouring node;

in which each node has a routing table including a set of addresses for its one-hop and two-hop neighbouring nodes, wherein the routing table includes a beacon value indicating the length of time since a beacon message has not been received; and

wherein the routing table includes a retry value indicating the number of times a node should resend the message to a 1-hop neighbouring node that has not responded with an acknowledgement signal, wherein the retry value for said 1-hop neighbouring node is determined from the reputation value of the 1-hop neighbouring node.

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, the acknowledgment signal being generated by the one-hop neighbouring node, when the one-hop neighbouring node receives a message from said node and said node being configured to receive an acknowledgement signal from a two-hop neighbouring node, the acknowledgment signal being generated by the two-hop neighbouring node, when the two-hop neighbouring node receives the message from the one-hop neighbouring node

wherein each acknowledgment signal is generated by its respective sending node and states, by using a digital signature which verifies the respective acknowledgement signal, that the sending node has received the message.

15. A computer readable medium encoded with software for implementing operation of the node according to claim 13.