SYSTEM FOR NETWORK DISCOVERY AND SYNCHRONIZATION

• US 20170013572A1
• Filed: 07/09/2015
• Published: 01/12/2017
• Est. Priority Date: 07/09/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Samuel, Rajkumar, Gelbman, Peter Paul, Hart, Michael John, Jayaraman, Arunkumar
• Granted Patent: US 10,051,587 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04B 7/26 at least one of which is mobile
• CPC Class Codes: H04W 16/28 using beam steering
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 56/001 Synchronization between nodes
• CPC Class Codes: H04W 56/0025 synchronizing potentially movable access points
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

Claims

1. A method comprising:

maintaining, by a cloud controller, data representing a topology of a network of nodes, wherein the data indicates a first group of nodes that are connected to the cloud controller and indicate, for each node in the network, one or more respective neighboring nodes for the node, and wherein each node communicates wirelessly with a neighboring node by forming a transmitting node and receiving node pair during a particular time interval, wherein the transmitting node of the pair communicates data to the receiving node of the pair during a particular time interval when the transmitting node is in a transmitting mode and the receiving node is in a receiving mode;

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, wherein nodes synchronize their respective timestamps upon receipt of the timestamp of the first node, wherein communicating the timestamp continues until each node in the network has been synchronized to the timestamp of the first node; and

sending the instructions to the first node, thereby synchronizing the nodes in the network to the timestamp of the first node.

2. The method of claim 1, wherein upon receiving, by the first node, the instructions, the first node scans for neighboring nodes, and wherein each neighboring node synchronizes its respective timestamp with the timestamp of the first node.

3. The method of claim 2, wherein for each neighboring node, the neighboring node scans for other respective neighboring nodes, and wherein each of the other respective neighboring nodes synchronizes its respective timestamp with the timestamp of the first node.

4. The method of claim 1, further comprising:

pushing a schedule to the first node to be propagated to each node in the network, wherein the schedule specifies when each node in each pair of neighboring nodes is in the transmitting mode or the receiving mode.

5. The method of claim 1, wherein the determining comprises:

determining, from a topology database, a second group of nodes has not been synchronized to the timestamp of the first node;

identifying neighboring nodes of each node in the second group of nodes from the topology database;

generating additional instructions configured 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 first 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 first node comprises a plurality of millimeter wave radios, wherein the instructions configured to cause the first node to communicate a timestamp of the first node comprises:

selecting, by the first node, a first timestamp of one of the 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 first node using the plurality of millimeter wave radios.

7. The method of claim 1, wherein the first node comprises a first directional antenna and a node neighboring the first node comprises a second directional antenna, further comprising:

identifying coordinates of the second directional antenna from the data;

and wherein the instructions comprise the coordinates and cause the first directional antenna to steer to the coordinates of the second directional antenna.

8. The method of claim 1, wherein a first node in the network has a first directional antenna and a second node in the network has a second directional antenna, and wherein the first node communicates 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.

9. The method of claim 1, wherein the first group of nodes connect to the cloud controller without going through any other 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 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, data representing a topology of a network of nodes, wherein the data indicates a first group of nodes that are connected to the cloud controller and indicate, for each node in the network, one or more respective neighboring nodes for the node, and wherein each node communicates wirelessly with a neighboring node by forming a transmitting node and receiving node pair during a particular time interval, wherein the transmitting node of the pair communicates data to the receiving node of the pair during a particular time interval when the transmitting node is in a transmitting mode and the receiving node is in a receiving mode;

selecting, by the cloud controller, a first node that has not been added to the network according to the data;

using the data to determine, by the cloud controller, neighboring nodes around the first node;

generating, by the cloud controller, instructions configured to cause the neighboring nodes to discover the first node;

sending the instructions to the neighboring nodes, thereby causing the neighboring nodes to discover the first node; and

receiving an indication that the first node communicates wirelessly with the neighboring nodes.

12. The method of claim 11, wherein the instructions cause the first node to synchronize its timestamp to a timestamp of one of the neighboring nodes.

13. The method of claim 12, further comprising distributing 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 has a first directional antenna and a second node in the network has a second directional antenna, and wherein the first node communicates 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 first node is in receiving mode, and wherein the first node steers a directional antenna in a full range of motion, and wherein the instructions configured to cause the neighboring nodes to discover the first node comprises:

steering directional antennas of the neighboring nodes in a full range of motion while in transmitting node;

determining, for one of the neighboring nodes, the directional antenna of the first node is steered to a respective directional antenna of the neighboring node; and

storing the determination in the data.

16. The method of claim 11, further comprising:

identifying coordinates of a first directional antenna of the first node from the data;

and wherein the instructions comprise the coordinates and cause directional antennas of the neighboring nodes to steer to the coordinates of the first directional antenna.

17. A system comprising:

a processor; and

computer-readable medium coupled to the processor and having instructions stored thereon, which, when executed by the processor, cause the processor to perform operations comprising;

maintaining, by a cloud controller, data representing a topology of a network of nodes, wherein the data indicates a first group of nodes that are connected to the cloud controller and indicate, for each node in the network, one or more respective neighboring nodes for the node, and wherein each node communicates wirelessly with a neighboring node by forming a transmitting node and receiving node pair during a particular time interval, wherein the transmitting node of the pair communicates data to the receiving node of the pair during a particular time interval when the transmitting node is in a transmitting mode and the receiving node is in a receiving mode;

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, wherein nodes synchronize their respective timestamps upon receipt of the timestamp of the first node, wherein communicating the timestamp continues until each node in the network has been synchronized to the timestamp of the first node; and

sending the instructions to the first node, thereby synchronizing the nodes in the network to the timestamp of the first node.

18. The system of claim 17, wherein upon receiving, by the first node, the instructions, the first node scans for neighboring nodes, and wherein each neighboring node synchronizes its respective timestamp with the timestamp of the first node.

19. The system of claim 18, wherein for each neighboring node, the neighboring node scans for other respective neighboring nodes, and wherein each of the other respective neighboring nodes synchronizes its respective timestamp with the timestamp of the first node.

20. The system of claim 17, further comprising:

pushing a schedule to the first node to be propagated to each node in the network, wherein the schedule specifies when each node in each pair of neighboring nodes is in the transmitting mode or the receiving mode.

21. The system of claim 17, wherein the determining comprises:

determining, from a topology database, a second group of nodes has not been synchronized to the timestamp of the first node;

identifying neighboring nodes of each node in the second group of nodes from the topology database;

generating additional instructions configured 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 first node; and

sending the additional instructions to the neighboring nodes of each node in the second group of nodes.

22. The system of claim 17, wherein the first node comprises a plurality of millimeter wave radios, wherein the instructions configured to cause the first node to communicate a timestamp of the first node comprises:

selecting, by the first node, a first timestamp of one of the 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 first node using the plurality of millimeter wave radios.

23. The system of claim 17, wherein the first node comprises a first directional antenna and a node neighboring the first node comprises a second directional antenna, further comprising:

identifying coordinates of the second directional antenna from the data;

and wherein the instructions comprise the coordinates and cause the first directional antenna to steer to the coordinates of the second directional antenna.

24. The system of claim 17, wherein a first node in the network has a first directional antenna and a second node in the network has a second directional antenna, and wherein the first node communicates 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.

25. The system of claim 17, wherein the first group of nodes connect to the cloud controller without going through any other node in the network.

26. The system of claim 17, 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 cause each neighboring node to send a request for synchronization to other neighboring nodes of the neighboring node.