Operating a cluster of peer-to-peer devices

• US 10,003,642 B2
• Filed: 06/02/2014
• Issued: 06/19/2018
• Est. Priority Date: 06/28/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Vandwalle, Pierre B., Hartman, Christiaan A., Liu, Yong
• Primary Examiner(s): Serrao, Ranodhi
• Assistant Examiner(s): Fiorillo, James
• Application Number:
  US14/293,407
• Publication Number:
  US 20150006633A1
• Time in Patent Office: 1,478 Days
• Field of Search: 709204, 709206, 709224, 370312, 370338, 370350, 370390
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/1059 Inter-group management mechanisms, e.g. splitting, merging or interconnection of groups
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04W 48/10 using broadcasted information
• CPC Class Codes: H04W 48/18 Selecting a network or a communication service
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 56/002 Mutual synchronization

Abstract

A system, apparatus, and method are provided for operating a peer-to-peer communication environment. The environment includes one or more clusters of peer devices, wherein devices in a single cluster are organized into a logical hierarchy under an anchor master (at the root of the hierarchy) and any number of synchronization masters; other devices are non-master devices. Synchronization parameters established by the anchor master and disseminated throughout the hierarchy enable the clusters'"'"' devices to rendezvous, discover peers and services, and communicate among themselves. The anchor master may adjust the synchronization parameters to avoid conflict with another hierarchy. Each device issues beacons (e.g., heartbeats, discovery beacons) that identify the number of devices synchronized with the reporting device, which allows the anchor master to calculate the total number of cluster members. Devices may also report details of a neighboring cluster (e.g., its synchronization parameters) via a beacon or some other communication.

Claims

1. A device, comprising:

a processor; and

a memory configured to store;

an identity of a current master of the device; and

synchronization parameters to facilitate synchronization with one or more peer devices, wherein the synchronization parameters comprise information configured to allow a listening device to learn of a sequence of discovery windows that has been imposed by the current master, wherein the synchronization parameters were included in one or more beacons transmitted by the current master of the device and comprise at least one of;

a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows;

wherein the processor is configured to;

utilize the synchronization parameters to attend a rendezvous of the one or more peer devices;

synchronize with the one or more peer devices to form a cluster of devices;

detect one or more parameters of a foreign cluster of devices, wherein the one or more parameters from the foreign cluster of devices were included in one or more beacons transmitted by a master of the foreign cluster of devices that is different from the current master of the device;

inform at least one peer device of the one or more parameters of the foreign cluster of devices; and

receive adjusted synchronization parameters to resolve a conflict with the one or more parameters of the foreign cluster of devices.

2. The device of claim 1, wherein the one or more parameters of the foreign cluster of devices comprise at least a discovery window schedule of the foreign cluster.

3. The device of claim 1, wherein the adjusted synchronization parameters comprise a first schedule of periodic rendezvous of the one or more peer devices that does not overlap with a second schedule of periodic rendezvous of the foreign cluster of devices.

4. A method of operating a synchronized cluster of peer devices, the method comprising, at a first peer device:

applying synchronization parameters of the cluster of peer devices to maintain synchronization with one or more peer devices of the cluster of peer devices, wherein the synchronization parameters comprise information configured to allow a listening device to learn of a sequence of discovery windows that has been imposed by the first peer device,

wherein the synchronization parameters were included in one or more beacons transmitted by the first peer device within the cluster of peer devices and comprise at least one of;

a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows;

utilize the synchronization parameters to attend a rendezvous of the one or more peer devices;

detecting parameters of a foreign cluster of devices wherein the parameters from the foreign cluster of devices were included in one or more beacons transmitted by a master of the foreign cluster of devices that is different from the first peer device within the cluster of peer devices;

reporting the parameters of the foreign cluster of devices to the one or more peer devices;

adjusting the synchronization parameters to resolve a conflict with the parameters of the foreign cluster of devices; and

transmitting a beacon to the one or more peer devices wherein the adjusted synchronization parameters are included into the beacon.

5. The method of claim 4, further comprising:

determining that the parameters of the foreign cluster of devices conflict with the synchronization parameters; and

determining a ranking between the first peer device and an anchor master of the foreign cluster of devices.

6. The method of claim 5, further comprising:

determining that the anchor master of the foreign cluster of devices ranks higher than the first peer device.

7. The method of claim 4, wherein reporting the parameters of the foreign cluster of devices comprises:

transmitting one or more beacons containing the parameters of the foreign cluster, wherein the one or more beacons identify an anchor master of the cluster of peer devices.

8. The method of claim 4, wherein adjusting the synchronization parameters comprises adjusting at least one of a channel of the sequence of discovery windows of the cluster of peer devices and a period of the sequence of discovery windows of the cluster of peer devices.

9. The method of claim 4, wherein adjusting the synchronization parameters comprises:

determining that a number of devices in the cluster of devices is less than a number of devices in the foreign cluster of devices.

10. A non-transitory computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of operating a synchronized cluster of peer devices, the method comprising, at a first peer device:

applying synchronization parameters of the cluster of peer devices to maintain synchronization with one or more peer devices of the cluster of peer devices, wherein the synchronization parameters comprise information configured to allow a listening device to learn of a sequence of discovery windows that has been imposed by the first peer device,

wherein the synchronization parameters were included in one or more beacons transmitted by the first peer device within the cluster of peer devices and comprise at least one of;

a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows;

utilize the synchronization parameters to attend a rendezvous of the one or more peer devices;

detecting parameters of a foreign cluster of devices wherein the parameters from the foreign cluster of devices were included in one or more beacons transmitted by a master of the foreign cluster of devices that is different from the master device within the cluster of peer devices;

reporting the parameters of the foreign cluster of devices to the one or more peer devices;

adjusting the synchronization parameters to resolve a conflict with the parameters of the foreign cluster of devices; and

transmitting a beacon to the one or more peer devices wherein the adjusted synchronization parameters are included into the beacon.

11. A device, comprising:

a processor;

a memory configured to store synchronization parameters to facilitate synchronization with one or more peer devices; and

a wireless transceiver for conducting wireless communications, wherein the processor and the wireless transceiver are configured to;

synchronize the device with the one or more subordinate peer devices to form a synchronized cluster of devices, wherein synchronizing the device uses synchronization parameters that comprise information configured to allow a listening device to learn of a sequence of discovery windows,

wherein the synchronization parameters are included in one or more beacons transmitted by the device to the one or more subordinate peer devices and comprise at least one of a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows;

utilize the synchronization parameters to attend a rendezvous of the one or more subordinate peer devices;

determine that the one or more subordinate peer devices satisfy a predetermined condition, wherein the predetermined condition includes an indication in two or more successive beacons from the subordinate devices that the device is their master;

in response to the determination, tally a number of the one or more subordinate peer devices within the cluster of devices;

increment the tally to account for the device;

report the incremented tally, wherein a beacon is generated comprising the tally and the synchronization parameters; and

transmit the beacon to at least one of a superior device and the one or more subordinate peer devices.

12. The device of claim 11, wherein:

the one or more subordinate peer devices comprise one or more subordinate master peer devices, and to tally the number of the one or more subordinate peer devices within the cluster, the processor and the wireless transceiver are further configured to receive from each subordinate master peer device synchronized with the device a first value identifying a number of devices synchronized with the subordinate master peer device.

13. The device of claim 12, wherein:

the one or more subordinate peer devices comprise one or more subordinate non-master peer devices, and to tally the number of the one or more subordinate peer devices within the cluster, the processor and the wireless transceiver are further configured to receive, from each subordinate non-master peer device synchronized with the device, a communication identifying the device as a synchronization master of the non-master peer device.

14. The device of claim 13, wherein the communication received from a first subordinate non-master peer device comprises a heartbeat beacon.

15. A method of operating a synchronized cluster of peer devices, the method comprising, at a first peer device:

synchronizing with a plurality of subordinate peer devices to form the synchronized cluster of peer devices using synchronization parameters that comprise information configured to allow a listening device to learn of a sequence of discovery windows, wherein the synchronization parameters are included in one or more beacons transmitted by the first peer device to the one or more subordinate peer devices and comprise at least one of;

a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows;

utilize the synchronization parameters to attend a rendezvous of the one or more subordinate peer devices;

receiving, from each subordinate peer device, a first value identifying a number of peer devices synchronized with the subordinate peer device;

determining that the subordinate peer devices satisfy a predetermined condition, wherein the predetermined condition includes an indication in two or more successive beacons from the subordinate devices that the first peer device is their master;

in response to the determination, summing the first values received from the subordinate peer devices;

incrementing the sum of the first values by one;

reporting the incremented sum, wherein a beacon is generated comprising the incremented sum and the synchronization parameters; and

transmit the beacon to a superior peer device with which the first peer device is synchronized.

16. The method of claim 15, wherein the beacon further comprises the synchronization parameters and a hop count.

17. The method of claim 16, further comprising:

after reporting the incremented sum, incrementing the hop count; and

transmitting a new beacon including the incremented hop count and the synchronization parameters.

18. The method of claim 15, wherein receiving the first value comprises receiving a communication from each of the subordinate peer devices identifying the first peer device as a synchronization master of the subordinate peer devices.

19. The method of claim 18, wherein the communication comprises a heartbeat beacon.

20. The method of claim 15, wherein the beacon further comprises an identity of the first peer device and a master preference of the first peer device.

21. The method of claim 15, wherein receiving the first value comprises receiving a communication from each of the subordinate peer devices and the communication comprises a discovery beacon.

22. The method of claim 15, wherein reporting the incremented sum to the superior device comprises:

generating a beacon comprising the incremented sum and an identity of the superior device; and

transmitting the beacon.

23. A network of peer communication devices, comprising:

an anchor master having a highest master preference value among the peer communication devices in a logical hierarchy;

a first stratum comprising a sync master having a master preference value lower than the highest master preference value of the anchor master,

wherein the anchor master and the sync master are configured to transmit discovery beacons to identify the highest master preference value of the anchor master and to synchronize the logical hierarchy,

wherein a discovery beacon transmitted by the anchor master comprises a sum of number of peer communication devices synchronized with the anchor master;

wherein a discovery beacon transmitted by the sync master comprises a sum of number of peer communication devices synchronized with the sync master;

wherein the discovery beacons each comprise synchronization parameters comprising information configured to allow a listening device to learn of a sequence of discovery windows, and wherein the information comprises at least one of;

a channel on which one or more of the discovery windows will occur, a period of the discovery windows, a starting time of a next discovery window, or a duration of the discovery windows; and

a second stratum comprising a non-master peer communication device configured to transmit a heartbeat beacon,

wherein the sync master is configured to determine that the non-master peer communication device satisfies a predetermined condition, wherein the predetermined condition includes an indication in two or more successive heartbeat beacons from the non-master peer communication device that the sync master is its master, and in response to the determination, increase a number of peer devices that are synchronized with the sync master, and

wherein upon detecting parameters of a foreign cluster of devices, the anchor master is configured to determine a priority between the anchor master of a foreign cluster of devices and adjust the synchronization parameters to resolve a conflict with the parameters of the foreign cluster of devices.

24. The network of claim 23, wherein to adjust the synchronization parameters, the anchor master is further configured to configure a first schedule of periodic rendezvous of the peer communication devices to eliminate an overlap with a second schedule of periodic rendezvous of the foreign cluster of devices.

25. The network of claim 24, wherein to configure the first schedule of periodic rendezvous, the anchor master is further configured to set the first schedule to cause the periodic rendezvous of the peer communication devices to commence upon termination of the periodic rendezvous of the foreign cluster of devices.

26. The network of claim 23, wherein to determine the priority between the anchor master and the anchor master of the foreign cluster of devices, the anchor master is further configured to compare the master preference value of the anchor master with a second master preference value of the anchor master of the foreign cluster of devices.

27. The network of claim 26, wherein the anchor master is further configured to identify the second master preference value in the heartbeat beacons.

28. The network of claim 23, wherein the discovery beacon transmitted by the sync master further comprises an identity of the anchor master with which the sync master is synchronized.

29. The network of claim 23, wherein the heartbeat beacon comprises an identity of the sync master with which the non-master peer device is synchronized.

30. The network of claim 23, wherein the one or more

parameters of the foreign cluster of devices comprises at least one of a preference value of an anchor master of the foreign cluster, a size of the foreign cluster, a hop count from the anchor master of the foreign cluster to the device, or a discovery window schedule of the foreign cluster of devices.