Masterless slot allocation
First Claim
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.
1 Assignment
0 Petitions
Accused Products
Abstract
An approach is provided for collaboratively synchronizing devices in an ad hoc network. No device is acting as a master device or base station dictating time slot allocation to devices. A first device communicates with the other devices by a Media Access Control scheme based on time frames having time slots. Responsive to a determination that a current time slot allocated to a second device is occurring, a determination that a Boolean value selected according to a predetermined probability is true, and a transmission of a map of allocations of time slots to the devices, the first device determines the map indicates a conflict in which the same time slot is allocated to the first device and another device. The first device resolves the conflict by allocating another time slot to the first device, so that each time slot is allocated to no more than one corresponding device.
16 Citations
20 Claims
-
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; 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 the N devices. - 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; the 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; 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 the N devices. - View Dependent Claims (16, 17)
-
-
18. A computer program product comprising:
-
a computer readable storage medium; and computer readable program code stored in the computer readable storage medium, 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; the 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 the 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; 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 the N devices. - View Dependent Claims (19, 20)
-
Specification