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 (1) a determination by a device Tj included in the N devices that a current time slot s included in the S time slots is occurring in a time frame included in the time frames and is allocated to the device Tj (2) a selection by the device Tj of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device Tj that the selected Boolean value is true, and (4) a transmission by the device Tj of a map stored in the device Tj to one or more other devices listening to the device Tj, wherein the one or more other devices are included in the N devices and include a device Ti, the device Ti receiving the map and determining the map indicates a conflict between the device Ti and another device, the map including allocations of the S time slots to the N devices and indicating the conflict by including an allocation of a same time slot included in the S time slots to the device Ti and to the other device; 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.
-
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 (1) a determination by a device Tj included in the N devices that a current time slot s included in the S time slots is occurring in a time frame included in the time frames and is allocated to the device Tj (2) a selection by the device Tj of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device Tj that the selected Boolean value is true, and (4) a transmission by the device Tj of a map stored in the device Tj to one or more other devices listening to the device Tj, wherein the one or more other devices are included in the N devices and include a device Ti, the device Ti receiving the map and determining the map indicates a conflict between the device Ti and another device, the map including allocations of the S time slots to the N devices and indicating the conflict by including an allocation of a same time slot included in the S time slots to the device Ti and to the other device; 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 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 (1) a determination by a device Tj included in the N devices that a current time slot s included in the S time slots is occurring in a time frame included in the time frames and is allocated to the device Tj (2) a selection by the device Tj of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device Tj that the selected Boolean value is true, and (4) a transmission by the device Tj of a map stored in the device Tj to one or more other devices listening to the device Tj, wherein the one or more other devices are included in the N devices and include a device Ti, the device Ti receiving the map and determining the map indicates a conflict between the device Ti and another device, the map including allocations of the S time slots to the N devices and indicating the conflict by including an allocation of a same time slot included in the S time slots to the device Ti and to the other device; 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 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 (1) a determination by a device Tj included in the N devices that a current time slot s included in the S time slots is occurring in a time frame included in the time frames and is allocated to the device Tj (2) a selection by the device Tj of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device Tj that the selected Boolean value is true, and (4) a transmission by the device Tj of a map stored in the device Tj to one or more other devices listening to the device Tj, wherein the one or more other devices are included in the N devices and include a device Ti, the device Ti receiving the map and determining the map indicates a conflict between the device Ti and another device, the map including allocations of the S time slots to the N devices and indicating the conflict by including an allocation of a same time slot included in the S time slots to the device Ti and to the other device; 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 Dependent Claims (19, 20)
-
Specification