ASCERTAINING PRESENCE IN WIRELESS NETWORKS

• US 20100238940A1
• Filed: 01/28/2010
• Published: 09/23/2010
• Est. Priority Date: 01/28/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Payne, Edward Allen, Koop, Lamonte Peter
• Granted Patent: US 8,300,551 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

One of many aspects of the invention relates to an ad hoc network in which inbound messages are communicated from an originating node to a gateway node via a plurality of intermediate nodes. In this respect, a method performed by an intermediate node in communicating the inbound message to the gateway node includes: maintaining a routing table; and using the routing table, selecting a node for use as the next hop by determining whether a maximum number of allowable hops for an inbound message is exceeded by using such node, and comparing a preference of using such node to preferences of using other known nodes by which the maximum number of allowable hops would not be exceeded. Another aspect includes sending a “leave” message when an intermediate node leaves the ad hoc network, whereby the intermediate node is removed from similar routing tables maintained by other intermediate nodes.

Claims

1. In an ad hoc network in which inbound messages are communicated from an originating node to a gateway node via a plurality of intermediate nodes, a method performed by an intermediate node in communicating the inbound message to the gateway node, comprising the steps of:

(a) maintaining a routing table including a set of one or more rows, wherein each row of the set comprises fields including,

(i) a next hop address, representing a unique address of a node,

(ii) a next hop hopcount, representing a hop count to the gateway, and

(iii) a next hop qualifier, representing a preference to using a node as a next hop towards a gateway node relative to other nodes that may be used as a next hop towards a gateway node,

all fields of the row being pertaining to a known intermediate node for use as a next hop towards the gateway node;

(b) selecting a node for use as the next hop towards the gateway node for communicating the inbound message to the gateway node by,

(i) determining whether a sum of the next hop hopcount from a row and a current hopcount of the inbound message exceeds a maximum number of allowable hops for an inbound message, and

(ii) comparing a next hop qualifier of a row to a next hop qualifier of another row, wherein, for both rows, the maximum number of allowable hops for an inbound message is not exceeded; and

(c) communicating the inbound message to the node identified by the next hop address for which the next hop qualifier is determined to be preferred based on said comparison.

3. The method of claim 1, wherein the gateway node maintains pathways among the nodes based on the messages received from each of the other nodes.

9. The method of claim 1, wherein said steps (b)(i) and (b)(ii) are performed a plurality of times corresponding to the number of rows currently in the routing table being maintained.

10. The method of claim 1, wherein the next hop qualifier is determined, at least in part, based on a general traffic load of the node to which the next hop qualifier pertains.

11. The method of claim 1, wherein the next hop qualifier is determined, at least in part, based on transmission failure counts of the node to which the next hop qualifier pertains.

12. The method of claim 1, wherein the next hop qualifier is determined, at least in part, based on signal strength of the node to which the next hop qualifier pertains.

13. The method of claim 1, wherein the next hop qualifier represents both efficiency and success probability associated with using the node to which the next hop qualifier pertains as the next hop towards the gateway node for communicating the inbound message.

14. The method of claim 1, further comprising updating a next hop qualifier pertaining to a node upon a communication with such node.

15. The method of claim 1, further comprising updating a next hop qualifier pertaining to a node upon each communication with such node.

16. The method of claim 1, further comprising updating a next hop qualifier pertaining to a node upon receiving a communication from such node.

17. The method of claim 1, further comprising updating a next hop qualifier pertaining to a node upon receiving an acknowledgment associated with such node.

18. The method of claim 1, wherein an intermediate node does not maintain a routing table of entire pathways from the originating node to the gateway node.

19. The method of claim 1, further comprising transmitting a message for receipt by each hop address in the table when the intermediate node leaves the ad hoc network.

20. The method of claim 1, further comprising transmitting a leaving message for receipt by nodes corresponding to each next hop address in the table when the intermediate node leaves the ad hoc network.

26. The method of claim 1, wherein the ad hoc network comprises a class-based network.

27. The method of claim 26, wherein each set of one or more rows is associated with a class.

28. The method of claim 26, wherein each row of the routing table is associated with a class.

29. The method of claim 26, wherein the routing table is a first routing table associated with a first class, and further comprising the step of maintaining a second routing table including a set of one or more rows, wherein each row of the set comprises fields including,

(i) a next hop address, representing a unique address of a node,

(ii) a next hop hopcount, representing a hop count to the gateway, and

(iii) a next hop qualifier, representing a preference to using a node as a next hop towards a gateway node relative to other nodes that may be used as a next hop towards a gateway node,

all fields of the row being pertaining to a known intermediate node for use as a next hop towards the gateway node;

wherein the second routing table is associated with a second class.

30. The method of claim 29, wherein the step of selecting a node for use as the next hop towards the gateway node comprises determining, based on a class of an incoming message, whether to select a node corresponding to a row of the first routing table or the second routing table.

2. (canceled)

4-8. -8. (canceled)

21-25. -25. (canceled)

31. In an ad hoc network in which inbound messages are communicated from an originating node to a gateway node via a plurality of intermediate nodes and a root primary node, a method performed by each intermediate node in communicating the inbound message to the gateway node via the root primary node, comprising the steps of:

(a) maintaining a routing table including a set of one or more rows, wherein each row of the set comprises fields including,

(i) a next hop address, representing a unique address of another node,

(ii) a next hop hopcount, representing the hop count to the gateway from the other node, and

(iii) a next hop qualifier, representing a preference to using the other node as a next hop towards a gateway node relative to yet other nodes that may be used as a next hop towards a gateway node,

all fields of the row being pertaining to a known node for use as a next hop of the inbound message;

(b) selecting one of the known nodes for use as the next hop of the inbound message by,

(i) determining whether a sum of the next hop hopcount from a row and a current hopcount of the inbound message exceeds a maximum number of allowable hops for an inbound message, and

(ii) comparing a next hop qualifier of a row to a next hop qualifier of another row both rows for which the maximum number of allowable hops for an inbound message is not exceeded; and

(c) communicating the inbound message to the node identified by the next hop address for which the next hop qualifier is determined to be preferred based on said comparison.