Patent ID: 8300551

Claim:
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 an inbound message to a gateway node, comprising the steps of: (a) maintaining, at a first node of the plurality of intermediate nodes, a routing table including a set of known intermediate nodes for use as a next hop towards a gateway node, the routing table comprising, for each known intermediate node, fields including, (i) a next hop address, representing a unique address of the respective intermediate node, (ii) a next hop hopcount, representing a hop count to a gateway node, and (iii) a next hop qualifier, representing a preference for using the respective known intermediate 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; (b) receiving, at the first node, an inbound message for communication to a gateway node; (c) selecting, at the first node, a node for use as the next hop towards a gateway node for communicating the inbound message to a gateway node by, (i) determining, for two or more known intermediate nodes maintained in the routing table, whether a sum of the next hop hopcount maintained in the routing table for the respective known intermediate node and a current hopcount of the inbound message exceeds a maximum number of allowable hops for the inbound message, (ii) comparing next hop qualifiers maintained in the routing table for two or more known intermediate nodes for which the maximum number of allowable hops for an inbound message is not exceeded; (d) communicating, by the first node, 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; (e) receiving, at the first node, an acknowledgment from the known intermediate node the inbound message was communicated to, the acknowledgment containing indicators of a general traffic load of the known intermediate node the inbound message was communicated to; (f) updating, at the first node based at least partially on the indicators of a general traffic load contained in the received acknowledgment, the next hop qualifier maintained in the routing table for the known intermediate node the acknowledgment was received from.