×

Masterless slot allocation

  • US 9,629,112 B2
  • Filed: 01/22/2015
  • Issued: 04/18/2017
  • Est. Priority Date: 09/02/2010
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of:

  • a device Ti communicating with other devices in the ad hoc network by a Media Access Control (MAC) scheme based on time frames, each time frame having S time slots, the device Ti and the other devices being N devices in the ad hoc network, the ad hoc network having no network infrastructure, each time slot included in the S time slots is allocated to one or more corresponding devices included in the N devices, wherein N is an integer greater than 2, wherein N is less than or equal to S, wherein S is an integer, and wherein no device of the N devices acts as a master device or base station in the ad hoc network that dictates an allocation of the S time slots to the N devices;

    in response to a transmission by a device Tj of a map stored in the device Tj to one or more other devices listening to the device Tj, the device Ti determining the map indicates a conflict between device Ti and another device, the conflict indicated by a same time slot included in the S time slots being allocated to the device Ti and the other device, wherein the transmission is performed in response to a determination by the device Ti that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device Ti is in an alive mode reached in response to the device Ti hearing messages from peer devices in the ad hoc network or the Boolean value having a predetermined probability q of being true if the device Ti is in a dormant mode reached in response to a delay since a last reception by the device Ti of a message exceeding a delay threshold, wherein p and q are determined by a probability random number generator so that p>

    q and q>

    0, wherein p and q indicate respective likelihoods of performing the transmission, wherein the determination that the Boolean value is true is performed in response to a determination by the device Ti that a current time slot s included in the S time slots is occurring in a time frame which is included in the time frames and that the current time slot s is allocated to the device Ti, wherein the device Ti is included in the N devices, wherein the one or more other devices are included in the N devices and include the device Ti, and wherein the map includes allocations of the S time slots to the N devices; and

    in response to the step of determining the map indicates the conflict, the device Ti resolving the conflict by allocating another time slot included in the S time slots to the device Ti so that different time slots are allocated to the device Ti and the other device and each time slot included in the S time slots is allocated to no more than a single corresponding device included in the N devices.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×