Masterless slot allocation
First Claim
1. A method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of:
- 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, a device Ti determining the map indicates a conflict between the device Ti and another device, the conflict indicated by a same time slot included in 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 Tj that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device Tj is in an alive mode reached in response to the device Tj 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 Tj is in a dormant mode reached in response to a delay since a last reception by the device Tj 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; 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 devices in the ad hoc network.
1 Assignment
0 Petitions
Accused Products
Abstract
An approach is provided for collaboratively synchronizing devices in an ad hoc network. Responsive to a transmission of a map by a first device to other device(s) listening to the first device, a second device determines the map, which allocates time slots to devices, indicates a conflict by which a same time slot is allocated to the second device and another device. The transmission is responsive to a determination that a Boolean value is true with a probability p if the first device is in an alive mode or a probability q if the first device is in a dormant mode, where p>q and q>0, and where p and q indicate respective likelihoods of performing the transmission. The second device resolves the conflict by allocating another time slot to the second device.
-
Citations
20 Claims
-
1. A method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of:
-
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, a device Ti determining the map indicates a conflict between the device Ti and another device, the conflict indicated by a same time slot included in 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 Tj that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device Tj is in an alive mode reached in response to the device Tj 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 Tj is in a dormant mode reached in response to a delay since a last reception by the device Tj 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; andin 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 devices in the ad hoc network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer system comprising:
-
a hardware-based processor; a hardware-based computer-readable memory unit coupled to the processor, the memory unit containing instructions that are executed by the processor to implement a method of collaboratively synchronizing devices in an ad hoc network, the computer system being a device Ti, and the method comprising the steps of; 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 the device Ti and another device, the conflict indicated by a same time slot included in 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 Tj that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device Tj is in an alive mode reached in response to the device Tj 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 Tj is in a dormant mode reached in response to a delay since a last reception by the device Tj 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; andin 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 devices in the ad hoc network. - View Dependent Claims (16, 17)
-
-
18. A computer program product comprising:
-
a computer readable storage device; and computer readable program code stored in the computer readable storage device, the computer readable program code containing instructions that are executed by a processor included in a device Ti to implement a method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of; 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 the device Ti and another device, the conflict indicated by a same time slot included in 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 Tj that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device Tj is in an alive mode reached in response to the device Tj 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 Tj is in a dormant mode reached in response to a delay since a last reception by the device Tj 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; andin 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 devices in the ad hoc network. - View Dependent Claims (19, 20)
-
Specification