System for network discovery and synchronization

Patent metadata

Field	Value
Publication number	US-10051587-B2
Application number	US-201514795859-A
Country	US
Kind code	B2
Filing date	Jul 9, 2015
Priority date	Jul 9, 2015
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for maintaining, by a cloud controller, data representing a topology of a network of nodes; receiving, at the cloud controller from the first group of nodes, one or more requests to connect to the network; selecting, by the cloud controller, a first node in the first group of nodes that sent the request; and generating, by the cloud controller, instructions configured to cause the first node to communicate a timestamp of the first node to each neighboring node of the first node and to cause each neighboring node to communicate the timestamp of the first node to each other neighboring nodes of the neighboring node; and sending the instructions to the first node, thereby synchronizing the nodes in the network to the timestamp of the first node.

First claim

What is claimed is:

1. A method comprising:
maintaining, by a cloud controller, topology data for a network of a plurality of nodes, wherein the topology data indicates, for each node in the network, one or more respective neighboring nodes for the node, and wherein neighboring nodes are nodes in the network that are configured to communicate wirelessly by forming directional steering pairs wherein a transmitter node of a directional steering pair steers a first directional antenna of the transmitter node in a first direction of a receiver node of the directional steering pair, and wherein a receiver node of the directional steering pair steers a second directional antenna of the receiver node in a second direction of the transmitter node of the directional steering pair;
receiving, at the cloud controller, one or more requests to connect to the network provided by one or more requesting nodes of the plurality of nodes;
selecting, by the cloud controller among the one or more requesting nodes, a hub node to which all other nodes in the network will synchronize timestamps; and
generating, by the cloud controller, instructions operable to cause the selected hub node to communicate a timestamp of the hub node to each neighboring node of the hub node according to the topology data and to cause each neighboring node of the hub node to forward the timestamp received from the hub node to each of one or more other neighboring nodes of the neighboring node according to the topology data, wherein each node receiving a forwarded timestamp of the hub node is configured to synchronize a local timestamp maintained by the node to the forwarded timestamp of the hub node; and
synchronizing the nodes in the network to the timestamp of the hub node including sending the generated instructions to the hub node, thereby causing the hub node to forward the timestamp to one or more neighboring nodes of the hub node.

2. The method of claim 1 , further comprising:
receiving, by the hub node, the instructions; and
performing, by the hub node, a scan to identify one or more neighboring nodes; and
forwarding, by the hub node, the instructions to each of the identified one or more neighboring nodes.

3. The method of claim 2 , further comprising:
performing, by each neighboring node of the hub node, a scan to identify one or more other respective neighboring nodes of the neighboring node; and
forwarding, by each neighboring node, the instructions to each of the identified one or more other neighboring nodes.

4. The method of claim 1 , further comprising:
pushing, by the cloud controller to the hub node, a schedule to be propagated to each node in the network, wherein the schedule specifies when each node in each directional steering pair is a transmitter node or a receiver node of the directional steering pair.

5. The method of claim 1 , further comprising:
determining, from the topology data, a second group of nodes that have not been synchronized to the timestamp of the hub node;
identifying neighboring nodes of each node in the second group of nodes from the topology data;
generating additional instructions operable to cause the neighboring nodes of each node in the second group of nodes to continue communicating the timestamp until the neighboring nodes receive an indication that each node of the second group of nodes has been synchronized to the timestamp of the hub node; and
sending the additional instructions to the neighboring nodes of each node in the second group of nodes.

6. The method of claim 1 , wherein the hub node comprises a plurality of millimeter wave radios, and wherein the instructions are operable to cause the hub node to perform operations comprising:
selecting, by the hub node, a first timestamp of one of the millimeter wave radios of the plurality of millimeter wave radios;
synchronizing timestamps of each of the other millimeter wave radios to the first timestamp; and
communicating the timestamp to neighboring nodes of the hub node using one or more of the plurality of millimeter wave radios.

7. The method of claim 1 , wherein the hub node comprises a first directional antenna, and wherein a neighboring node of the hub node comprises a second directional antenna, and further comprising:
identifying, by the cloud controller, coordinates of the second directional antenna from the topology data;
and wherein generating the instructions comprises generating instructions that identify the coordinates of the second directional antenna and cause the hub node to steer the first directional antenna toward the coordinates of the second directional antenna.

8. The method of claim 1 , wherein each node in the network comprises one or more processors and a plurality of directional millimeter wave radios.

9. The method of claim 1 , wherein the first group of nodes are nodes that are capable of communicating directly with the cloud controller without communicating through any intermediary node in the network.

10. The method of claim 1 , where a particular node in the network periodically sends a request for synchronization to its neighboring nodes to cause the neighboring nodes to synchronize their respective timestamps to a timestamp of the node and to cause each neighboring node to send a request for synchronization to other neighboring nodes of the neighboring node.

11. A method comprising:
maintaining, by a cloud controller, topology data for a network of a plurality of nodes, wherein the topology data indicates, for each node in the network, one or more respective neighboring nodes for the node, and wherein neighboring nodes are nodes in the network that are configured to communicate wirelessly by forming directional steering pairs wherein a transmitter node of a directional steering pair steers a first directional antenna of the transmitter node in a first direction of a receiver node of the directional steering pair, and wherein a receiver node of the directional steering pair steers a second directional antenna of the receive node in a second direction of the transmitter node of the directional steering pair;
selecting, by the cloud controller, an undiscovered node that has not been added to the network according to the topology data;
using the topology data to determine, by the cloud controller, neighboring nodes around the undiscovered node;
generating, by the cloud controller, instructions operable to cause the neighboring nodes of the undiscovered node to discover the undiscovered node; and
sending the instructions to the neighboring nodes, thereby causing the neighboring nodes to discover the undiscovered node.

12. The method of claim 11 , wherein the instructions cause the undiscovered node to synchronize a local timestamp maintained by the undiscovered node to a forwarded timestamp received from one of the neighboring nodes.

13. The method of claim 12 , further comprising distributing, by the cloud controller, a schedule across the network of nodes, wherein the schedule coordinates future communication between each node in the network.

14. The method of claim 11 , wherein a first node in the network comprises a first directional antenna and a second node in the network comprises a second directional antenna, and wherein the first node is configured to communicate data to the second node when the first directional antenna is steered to the second directional antenna and the second directional antenna is steered to the first directional antenna.

15. The method of claim 11 , wherein the instructions operable to cause the neighboring nodes to discover the undiscovered node cause each neighboring node

Assignees

• Google Inc
• Google Llc

Inventors

• Jayaraman Arunkumar
• Samuel Rajkumar
• Gelbman Peter Paul
• Hart Michael John

Classifications

• H04W56/001 Primary

  Synchronization between nodes · CPC title

• H04W40/24

  Connectivity information management, e.g. connectivity discovery or connectivity update · CPC title

• H04W48/16

  Discovering, processing access restriction or access information · CPC title

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W56/0025

  synchronizing potentially movable access points · CPC title