Maintaining information facilitating deterministic network routing

• US 7,940,716 B2
• Filed: 07/03/2006
• Issued: 05/10/2011
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: TeraHop Networks Incorporated
• Inventors: Twitchell, Jr., Robert W.
• Primary Examiner(s): Santiago-Cordero, Marivelisse
• Assistant Examiner(s): Arevalo, Joseph
• Application Number:
  US11/428,536
• Publication Number:
  US 20070002793A1
• Time in Patent Office: 1,772 Days
• Field of Search: 370/206, 370/447, 370/344, 370/241, 370/458, 370/480, 370/225, 370/328, 370/386, 370/252, 370/254, 370/389, 370/228, 370/400, 370/329, 370/250, 370/338, 370/310, 709/248, 709/220, 709/224, 455/456.1, 455/574, 455/522, 455/10, 455/21, 455/343.1
• US Class Current: 370/328
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In a wireless network that includes a plurality of nodes, a method of maintaining, by a first node, information regarding communications links between nodes in the wireless network includes: for each communications link that is established with another node, recording an identification of the other node; and for each message received by the first node from the other node through the communications link with the other node, recording a network pathway by which the message has been sent in the wireless network, the network pathway identifying the nodes and the communications links therebetween by which the message has been sent. Another method includes recording, by a server, for each message that is received by the server from the wireless network, a network pathway by which the message has been sent, the network pathway identifying the nodes and the communications links therebetween by which the message has been sent.

Claims

1. In a wireless network comprising a plurality of nodes, a method of maintaining, by a first node, information regarding communications links between nodes in the wireless network, the method comprising the steps of:

(I) for each communications link that is established with another node, recording an identification of the other node;

(II) for each message received by the first node from the other node through the communications link with the other node, recording a network pathway by which the message has been sent in the wireless network, the network pathway identifying the nodes and the communications links therebetween in the wireless network by which the message has been sent; and

(III) communicating, by the first node, the message to a subsequent node in the wireless network if the message is intended for receipt by a node other than the first node, the communicating of the message by the first node including the steps of,

(a) determining whether one or more network pathways are known by the first node from the first node to the destination node of the message;

(b) communicating with just a single node within the communications range of the first node if a single network pathway to the destination node is known by the first node, the single node being the node identified next in the single network pathway after the first node, including sending, to the single node,

(i) the message,

(ii) the single network pathway, and

(iii) the link quality between the first node and the other node from which the message was received by the first node;

(c) if more than one network pathway to the destination node is known by the first node, then,

(i) determining a preferred network pathway from the known network pathways in accordance with an algorithm, and

(ii) communicating with just a single node within the communications range of the first node, the single node being the node identified next in the preferred network pathway after the first node, including sending, to the single node,

(A) the message,

(B) the preferred network pathway, and

(C) the link quality between the first node and the other node from which the message was received by the first node; and

(d) if no network pathway to the destination node is known by the first node, then communicating with one or more nodes within the communications range of the first node, including sending,

(i) the message, and

(ii) the link quality between the first node and the other node from which the message was received by the first node.

2. The method of claim 1, further comprising recording, in association with the identification of the other node, data indicative of a link quality between the first node and the other node.

3. The method of claim 1, further comprising recording, for each message received by the first node from the other node through the communications link with the other node, data indicative of a link quality between each communications link in the network pathway by which the message has been sent.

4. The method of claim 1, further comprising recording, for each message received by the first node from the other node through the communications link with the other node, data indicative of class designations of each node in the communications links in the network pathway by which the message has been sent.

5. The method of claim 1, further comprising recording, for each message received by the first node from the other node through the communications link with the other node, data generally indicative of the time at which the message has been sent via the network pathway.

6. The method of claim 1, further comprising recording, for each message received by the first node from the other node through the communications link with the other node, a network pathway to a destination node by which the message is being sent if such network pathway to the destination node is identified with the message.

7. The method of claim 1, wherein said step of determining whether one or more network pathways are known by the first node from the first node to the destination node of the message includes searching the maintained information for a network pathway from the first node to the destination node.

8. The method of claim 7, wherein the maintained information that is searched includes any network pathway to the destination node that is identified with the message.

9. The method of claim 1, wherein determining a preferred network pathway from the known network pathways in accordance with an algorithm comprises comparing the general times at which messages were sent via the network pathways.

10. The method of claim 1, wherein determining a preferred network pathway from the known network pathways in accordance with an algorithm comprises comparing the number of hops between nodes in the known network pathways.

11. The method of claim 1, wherein determining a preferred network pathway from the known network pathways in accordance with an algorithm comprises comparing the overall link quality of the known network pathways.