Methods and apparatus for selecting a device to perform shared functionality in a deterministic and fair manner in a wireless data communication system

• US 9,860,862 B1
• Filed: 11/28/2016
• Issued: 01/02/2018
• Est. Priority Date: 05/21/2013
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Lambert, Paul A.
• Primary Examiner(s): Jain, Raj
• Application Number:
  US15/362,657
• Time in Patent Office: 400 Days
• CPC Class Codes: H04W 40/244 using a network of reference devices, e.g. beaconing
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 56/001 Synchronization between nodes
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 56/002 Mutual synchronization
• CPC Class Codes: H04W 56/0025 synchronizing potentially movable access points
• CPC Class Codes: H04W 76/11 Allocation or use of connection identifiers
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

The present disclosure describes methods and apparatus for selecting a device to perform shared functionality in a deterministic and fair manner in a wireless data communication system. A wireless data communication system includes multiple wireless transceiver devices and certain functionality, such as the transmitting of a beacon used to synchronize the wireless transceiver devices, is distributed among the wireless transceiver devices. Each wireless transceiver device generates a device rank for a given time for itself as well as one or more other wireless transceiver devices in a deterministic and fair manner. Each wireless transceiver device determines the same device ranks for the wireless transceiver devices, and each wireless transceiver device selects the wireless transceiver device having a highest device rank at any given time as the wireless transceiver device that is to perform the functionality at that given time.

Claims

1. A method implemented in a first transceiver device of multiple transceiver devices in a data communication system configured to distribute functionality among the multiple transceiver devices, the method comprising:

sending an identifier of the first transceiver device to other transceiver devices of the multiple transceiver devices;

receiving identifiers of the other transceiver devices;

updating a synchronization value for the data communication system, the updated synchronization value comprising a value used to facilitate keeping the multiple transceiver devices synchronized;

generating for a given time, for each transceiver device of the multiple transceiver devices, a selection measure from the updated synchronization value and the respective identifier of each of the transceiver devices;

ranking for the given time each of the multiple transceiver devices based on the generated selection measures; and

selecting, based on the ranking, one of the multiple transceiver devices as a transceiver to transmit a beacon at the given time.

2. The method of claim 1, wherein the selected one of the multiple transceiver devices is the first transceiver device, and in response to the selecting, further comprising transmitting the beacon at the given time.

3. The method of claim 1, wherein the selected one of the multiple transceiver devices is one of the other transceiver devices, and in response to the selecting, further comprising configuring the first transceiver device to sleep through the given time.

4. The method of claim 1, wherein the given time comprises one or more future times.

5. The method of claim 1, wherein the ranking is performed in a deterministic and fair manner that results in each of the multiple transceiver devices having a highest device rank in the ranking within a threshold amount of the same number of times over a given time range.

6. The method of claim 1, wherein the selection measure for said each transceiver device is generated by concatenation of the updated synchronization value and the respective identifier of each of the transceiver devices.

7. The method of claim 1, wherein the synchronization value is part of an additional beacon received by one of the other transceiver devices, the additional beacon corresponding to a different time than the given time.

8. The method of claim 1, wherein the selected one of the multiple transceiver devices is a highest ranked transceiver according to the ranking.

9. The method of claim 1, wherein the selected one of the multiple transceiver devices is selected from a subset of the multiple transceiver devices comprising less than all of the multiple transceiver devices.

10. The method of claim 1, wherein the identifiers of the other transceiver devices are received from the other transceiver devices.

11. The method of claim 1, further comprising receiving an additional beacon, and responsive to the receiving the additional beacon, sending or receiving data during a particular range of time after the additional beacon.

12. The method of claim 1, wherein the identifier of the first transceiver device and the identifiers of the other transceiver devices comprise network addresses.

13. A first transceiver device of multiple transceiver devices in a data communication system configured to distribute functionality among the multiple transceiver devices, the first transceiver device comprising:

a microprocessor; and

one or more computer-readable media storing computer-executable instructions that, when executed by the microprocessor, implement a selector to;

send an identifier of the first transceiver device to other transceiver devices of the multiple transceiver devices;

receive identifiers of the other transceiver devices;

update a synchronization value for the data communication system, the updated synchronization value comprising a value used to facilitate keeping the multiple transceiver devices synchronized;

generate for a given time, for each transceiver device of the multiple transceiver devices, a selection measure from the updated synchronization value and the respective identifier of each of the transceiver devices;

rank for the given time each of the multiple transceiver devices based on the generated selection measures; and

select, based on the rank, one of the multiple transceiver devices as a transceiver to transmit a beacon at the given time.

14. The first transceiver device of claim 13, wherein the selected one of the multiple transceiver devices is the first transceiver device, and in response to the selection, further comprising to transmit the beacon at the given time.

15. The first transceiver device of claim 13, wherein the selected one of the multiple transceiver devices is one of the other transceiver devices, and in response to the selection, further comprising configuring the first transceiver device to sleep through the given time.

16. The first transceiver device of claim 13, wherein the rank is performed in a deterministic and fair manner that results in each of the multiple transceiver devices having a highest device rank in the rank within a threshold amount of the same number of times over a given time range.

17. The first transceiver device of claim 13, wherein the selected one of the multiple transceiver devices is a highest ranked transceiver according to the rank.

18. A non-transitory computer-readable memory device comprising computer-executable instructions that, when executed, implement a system in a first transceiver device of multiple transceiver devices in a data communication system configured to distribute functionality among the multiple transceiver devices, the system in the first transceiver device configured to:

send an identifier of the first transceiver device to other transceiver devices of the multiple transceiver devices;

receive identifiers of the other transceiver devices;

update a synchronization value for the data communication system, the updated synchronization value comprising a value used to facilitate keeping the multiple transceiver devices synchronized;

generate for a given time, for each transceiver device of the multiple transceiver devices, a selection measure from the updated synchronization value and the respective identifier of each of the transceiver devices;

rank for the given time each of the multiple transceiver devices based on the generated selection measures; and

select, based on the rank, one of the multiple transceiver devices as a transceiver to transmit a beacon at the given time.

19. The non-transitory computer-readable memory device of claim 18, wherein the selected one of the multiple transceiver devices is the first transceiver device, and in response to the selection, further comprising to transmit the beacon at the given time.

20. The non-transitory computer-readable memory device of claim 18, further comprising to receive an additional beacon, and responsive to the reception of the additional beacon, sending first data during a first range of time after the additional beacon and receiving second data during a second range of time after the additional beacon.