Method and apparatus for ad hoc mesh routing

• US 8,185,653 B2
• Filed: 08/09/2005
• Issued: 05/22/2012
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Christopher J. Ngan, Johnny Yau
• Original Assignee: Christopher J. Ngan, Johnny Yau
• Inventors: Yau, Johnny, Ngan, Christopher J.
• Primary Examiner(s): Barot, Bharat N
• Application Number:
  US11/572,439
• Publication Number:
  US 20080002599A1
• Time in Patent Office: 2,478 Days
• Field of Search: 709202-203, 709227-230, 709238-242, 714746-750
• US Class Current: 709/238
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

Packets are routed in a wireless mesh network by assigning a probability of packet retransmission based on certain factors which may include the number of hops the packet has made, whether the destination is within a certain number of known hops of the receiving node, the number of nearby nodes, whether the receiving node is a member of a past known route to the destination and/or whether a nearby neighbor of the receiving node is a member of a past known route to the destination. Once a probability is assigned, a random number generator may be used to make a decision between retransmitting the packet and dropping the packet. Signal quality may also be used as a factor in the probability of retransmission. In a preferred embodiment, Bloom filters are used to store information in the header of a data packet containing the identifiers of forwarding nodes and the identifiers of nodes on a previously-successful route from the source to the destination.

Claims

1. A method for routing data packets non-deterministically in a wireless mesh network comprising:

calculating in a node of the wireless network a probability of forwarding a received packet via re-transmission;

generating in the node a threshold value that is a function of a random number;

comparing the calculated probability to the generated threshold value; and

,

re-transmitting the packet if the calculated probability is greater than the generated threshold value.

2. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted.

3. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination.

4. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions.

5. A method as recited in claim 4 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

6. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether a member of a set of nodes pre-determined to be within a known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

7. A method as recited in claim 6 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

8. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted and whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination.

9. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted and whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions.

10. A method as recited in claim 9 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

11. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted and whether a member of a set of nodes pre-determined to be within a known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

12. A method as recited in claim 11 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

13. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination and whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions.

14. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination and whether a member of a set of nodes pre-determined to be within a known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

15. A method as recited in claim 14 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

16. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the destination is a member of a set of nodes pre-determined to be within a first known number of transmissions and whether a member of a set of nodes pre-determined to be within a second known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

17. A method as recited in claim 16 wherein the probability of re-transmitting a received packet is additionally a function of the first known number of transmissions and the second known number of transmissions.

18. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted, whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination and whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions.

19. A method as recited in claim 18 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

20. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted, whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination and whether a member of a set of nodes pre-determined to be within a known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

21. A method as recited in claim 20 wherein the probability of re-transmitting a received packet is additionally a function of the known number of transmissions.

22. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted, whether the destination is a member of a set of nodes pre-determined to be within a first known number of transmissions and whether a member of a set of nodes pre-determined to be within a second known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

23. A method as recited in claim 22 wherein the probability of re-transmitting a received packet is additionally a function of the first known number of transmissions and the second known number of transmissions.

24. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination, whether the destination is a member of a set of nodes pre-determined to be within a first known number of transmissions and whether a member of a set of nodes pre-determined to be within a second known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

25. A method as recited in claim 24 wherein the probability of re-transmitting a received packet is additionally a function of the first known number of transmissions and the second known number of transmissions.

26. A method as recited in claim 1 wherein the probability of re-transmitting a received packet is a function of the number of times the packet has been transmitted, whether the receiving node is a member of a set of nodes comprising a previously-successful route to the destination, whether the destination is a member of a set of nodes pre-determined to be within a first known number of transmissions and whether a member of a set of nodes pre-determined to be within a second known number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination.

27. A method as recited in claim 26 wherein the probability of re-transmitting a received packet is additionally a function of the first known number of transmissions and the second known number of transmissions.

28. A method as recited in any of claims 1 through 27 further comprising:

inserting the identifier of the receiving node into the header of each packet to be retransmitted;

incrementing the number of transmissions contained in the header of each packet to be retransmitted;

updating a table containing the identifiers of nodes that are one transmission away to contain the identifier of the last forwarding node; and

, updating a table containing the identifiers of nodes known to be the number of transmissions away that is equal to the number of times the packet has been transmitted to contain the identifier of the source node.

29. A method for routing data packets in a wireless mesh network comprising:

calculating in a node of the wireless network a probability of re-transmitting a received packet based on at least one factor selected from the group consisting of the signal quality of the packet, the number of times the packet has been transmitted, whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions, whether a node known to be within a predetermined number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination, whether the receiving node is member of a set of nodes that comprised a previously-successful route to the destination, and the number of nodes previously determined to be within receiving range of the receiving node;

generating in the node a threshold value that is a function of a random number;

comparing the threshold value to the calculated probability;

re-transmitting the packet if the calculated probability is greater than the threshold value; and

dropping the packet if the calculated probability is less than the threshold value.

34. A method as recited in claim 29 further comprising using a Bloom filter to determine whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions, whether a node known to be within a predetermined number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination, and whether the receiving node is member of a set of nodes that comprised a previously-successful route to the destination.

30. A processor based system for routing data packets in a wireless mesh network comprising a medium storing instructions for causing the processor to:

calculate a probability of re-transmitting a received packet based on at least one factor selected from the group consisting of the number of times the packet has been transmitted, whether the destination is a member of a set of nodes pre-determined to be within a known number of transmissions, whether a node known to be within a predetermined number of transmissions is a member of a set of nodes that comprised a previously-successful route to the destination, whether the receiving node is member of a set of nodes that comprised a previously-successful route to the destination, and the number of nodes previously determined to be within receiving range of the receiving node;

generate a randomized threshold value;

compare the randomized threshold value to the calculated probability; and

, re-transmit the packet if the calculated probability is greater than the randomized threshold value.

31. A system as recited in claim 30 further comprising instructions for causing the processor to insert the identifier of the receiving node into the header of each packet to be retransmitted, to increment the number of transmissions contained in the header of each packet to be retransmitted, to update a table containing the identifiers of nodes that are one transmission away to contain the identifier of the last forwarding node and to update a table containing the identifiers of nodes known to be the number of transmissions away that is equal to the number of times the packet has been transmitted to contain the identifier of the source node.

32. A system as recited in claim 31 further comprising instructions to clear the tables containing the identifiers of nodes known to be a certain number of transmissions away after a pre-selected interval has elapsed.

33. A system as recited in claim 31 further comprising instructions to clear an entry in the tables containing the identifiers of nodes known to be a certain number of transmissions away after a pre-selected interval has elapsed since the entry was inserted in the table.