Patent ID: 8385211

Claim:
A method of routing messages in an ad hoc wireless network, the method comprising: receiving, at a source node of the ad hoc wireless network, a message that identifies each of a plurality of nodes of the ad hoc wireless network and a position of each of the plurality of nodes, wherein the plurality of nodes includes at least one node that is out of range for direct communication with the source node; in response to receiving the message: generating, based on the message, a list of neighbor nodes corresponding to nodes of the plurality of nodes that are within range for direct communication with the source node; determining a cost of sending a message to each of the plurality of nodes of the ad hoc wireless network via each of the identified neighbor nodes, wherein the cost of sending the messages is determined using a cost function that uses one or more factors, wherein the one or more factors include any combination of: a factor representing a first cost for each hop between nodes, wherein the first cost varies inversely with a predicted duration of time that a link between the nodes will be established; a factor representing a second cost for each hop between nodes, wherein the second cost varies in proportion with a speed of each of the plurality of nodes; and a factor representing a third cost for each hop between nodes, wherein the third cost varies inversely with a distance of a link between each of the plurality of nodes; and generating a routing table that includes a plurality of entries, wherein each of the plurality of entries corresponds to one of the plurality of nodes and includes a first field and a second field, wherein the first field includes address information associated with the corresponding node, wherein the second field identifies a particular neighbor node through which the source node is to send messages addressed to the corresponding node, and wherein the particular neighbor node is identified based on the cost of sending a message from the source node to the corresponding node.