Masterless slot allocation
First Claim
1. A method of collaboratively synchronizing devices communicating in an ad hoc network, said method comprising:
- a first device receiving a map from a second device, wherein said first device and said second device are included in devices communicating in said ad hoc network in which no device of said devices acts as a master device or base station in said ad hoc network, said devices collaboratively synchronized at a time frame level based on time frames, each time frame having time slots, and wherein said map includes an allocation of said time slots to said devices;
subsequent to said receiving said map, said first device determining said map indicates a conflict between said first device and another device of said devices, said conflict being indicated by a same time slot of said time slots being allocated to said first device and to said another device;
in response to said determining said map indicates said conflict, said first device resolving said conflict by allocating another time slot of said time slots to said first device so that different time slots of said time slots are allocated to said first device and said another device, and each slot of said time slots is allocated to no more than a single corresponding device of said devices;
N devices being said devices and communicating with each other in said ad hoc network by a Media Access Control (MAC) scheme based on said time frames, said ad hoc network having no network infrastructure, said time slots being S time slots, each time slot of said S time slots allocated to one or more corresponding devices of said N devices, wherein N and S are integers, wherein N is an integer greater than 2, wherein N is less than or equal to S, and wherein no device of said devices acting as a master device or base station in said ad hoc network is indicated by no device of said N devices dictates an allocation of said S time slots to said N devices;
a device Tj of said N devices determining a current time slot s of said S time slots is occurring in a time frame of said time frames and is allocated to said device Tj, wherein device Tj, is said second device;
in response to said determining said current time slot s is occurring and is allocated to said device Tj, said device Tj determining a Boolean value with a probability p; and
in response to said determining said Boolean value, said device Tj transmitting said map stored in said device Tj to one or more other devices listening to said device Tj, wherein said one or more other devices are included in said N devices and include a device Ti, wherein said device Ti is said first device, and wherein said receiving said map is performed in response to said transmitting said map.
1 Assignment
0 Petitions
Accused Products
Abstract
A masterless time slot allocation technique that collaboratively synchronizes, at a time slot level, devices communicating in an ad hoc network. Responsive to determining a current time slot allocated to a first device is occurring, the first device transmits a map to the other devices. The map includes an allocation of time slots to the devices, including indicators for whether each time slot is free, busy or overbooked, devices that own the time slots, and how recently information associated with each time slot was updated. After receiving the map, a second device determines a conflict in which the same time slot is allocated to the second device and to another device. The conflict is resolved by allocating another time slot to the second device and the result of resolving the conflict is each slot is allocated to no more than one device.
-
Citations
20 Claims
-
1. A method of collaboratively synchronizing devices communicating in an ad hoc network, said method comprising:
-
a first device receiving a map from a second device, wherein said first device and said second device are included in devices communicating in said ad hoc network in which no device of said devices acts as a master device or base station in said ad hoc network, said devices collaboratively synchronized at a time frame level based on time frames, each time frame having time slots, and wherein said map includes an allocation of said time slots to said devices; subsequent to said receiving said map, said first device determining said map indicates a conflict between said first device and another device of said devices, said conflict being indicated by a same time slot of said time slots being allocated to said first device and to said another device; in response to said determining said map indicates said conflict, said first device resolving said conflict by allocating another time slot of said time slots to said first device so that different time slots of said time slots are allocated to said first device and said another device, and each slot of said time slots is allocated to no more than a single corresponding device of said devices; N devices being said devices and communicating with each other in said ad hoc network by a Media Access Control (MAC) scheme based on said time frames, said ad hoc network having no network infrastructure, said time slots being S time slots, each time slot of said S time slots allocated to one or more corresponding devices of said N devices, wherein N and S are integers, wherein N is an integer greater than 2, wherein N is less than or equal to S, and wherein no device of said devices acting as a master device or base station in said ad hoc network is indicated by no device of said N devices dictates an allocation of said S time slots to said N devices; a device Tj of said N devices determining a current time slot s of said S time slots is occurring in a time frame of said time frames and is allocated to said device Tj, wherein device Tj, is said second device; in response to said determining said current time slot s is occurring and is allocated to said device Tj, said device Tj determining a Boolean value with a probability p; and in response to said determining said Boolean value, said device Tj transmitting said map stored in said device Tj to one or more other devices listening to said device Tj, wherein said one or more other devices are included in said N devices and include a device Ti, wherein said device Ti is said first device, and wherein said receiving said map is performed in response to said transmitting said map. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A computer system comprising:
-
a hardware-based processor included in a first device; a hardware-based computer-readable memory unit coupled to said processor, said memory unit containing instructions that are carried out by said processor to implement a method of collaboratively synchronizing devices communicating in an ad hoc network; hardware-based processors included in N devices; and hardware-based computer-readable memory units coupled to said processors in a one-to-one correspondence, each memory unit containing instructions that are carried out by a corresponding processor of said processors to further implement said method, said method comprising; said first device receiving a map from a second device, wherein said first device and said second device are included in said devices communicating in said ad hoc network in which no device of said devices acts as a master device or base station in said ad hoc network, said devices collaboratively synchronized at a time frame level based on time frames, each time frame having time slots, and wherein said map includes an allocation of said time slots to said devices; subsequent to said receiving said map, said first device determining said map indicates a conflict between said first device and another device of said devices, said conflict being indicated by a same time slot of said time slots being allocated to said first device and to said another device; in response to said determining said map indicates said conflict, said first device resolving said conflict by allocating another time slot of said time slots to said first device so that different time slots of said time slots are allocated to said first device and said another device, and each slot of said time slots is allocated to no more than a single corresponding device of said devices; said N devices being said devices and communicating with each other in said ad hoc network by a Media Access Control (MAC) scheme based on said time frames, said ad hoc network having no network infrastructure, said time slots being S time slots, each time slot of said S time slots allocated to one or more corresponding devices of said N devices, wherein N and S are integers, wherein N is an integer greater than 2, wherein N is less than or equal to S, and wherein no device of said devices acting as a master device or base station in said ad hoc network is indicated by no device of said N devices dictates an allocation of said S time slots to said N devices; a device Tj of said N devices determining a current time slot s of said S time slots is occurring in a time frame of said time frames and is allocated to said device Tj, wherein device Tj is said second device; in response to said determining said current time slot s is occurring and is allocated to said device Tj, said device Tj determining a Boolean value with a probability p; and in response to said determining said Boolean value, said device Tj transmitting said map stored in said device Tj to one or more other devices listening to said device Tj, wherein said one or more other devices are included in said N devices and include a device Ti, wherein said device Ti is said first device, and wherein said receiving said map is performed in response to said transmitting said map. - View Dependent Claims (17, 18)
-
-
15. A computer program product comprising a computer readable storage medium having a computer readable program code stored therein, said computer readable program code containing instructions that are carried out by a processor of a first device in a computer system to implement a method of collaboratively synchronizing devices communicating in an ad hoc network, said computer program product further comprising other computer readable storage media having corresponding computer readable program code stored therein, each corresponding computer readable program code containing instructions that are carried out by a processor of a corresponding device of N devices in said computer system to further implement said method, said method comprising:
-
said first device receiving a map from a second device, wherein said first device and said second device are included in said devices communicating in said ad hoc network in which no device of said devices acts as a master device or base station in said ad hoc network, said devices collaboratively synchronized at a time frame level based on time frames, each time frame having time slots, and wherein said map includes an allocation of said time slots to said devices; subsequent to said receiving said map, said first device determining said map indicates a conflict between said first device and another device of said devices, said conflict being indicated by a same time slot of said time slots being allocated to said first device and to said another device; in response to said determining said map indicates said conflict, said first device resolving said conflict by allocating another time slot of said time slots to said first device so that different time slots of said time slots are allocated to said first device and said another device, and each slot of said time slots is allocated to no more than a single corresponding device of said devices; said N devices being said devices and communicating with each other in said ad hoc network by a Media Access Control (MAC) scheme based on said time frames, said ad hoc network having no network infrastructure, said time slots being S time slots, each time slot of said S time slots allocated to one or more corresponding devices of said N devices, wherein N and S are integers, wherein N is an integer greater than 2, wherein N is less than or equal to S, and wherein no device of said devices acting as a master device or base station in said ad hoc network is indicated by no device of said N devices dictates an allocation of said S time slots to said N devices; a device Tj of said N devices determining a current time slot s of said S time slots is occurring in a time frame of said time frames and is allocated to said device Tj, wherein device Tj is said second device; in response to said determining said current time slot s is occurring and is allocated to said device Tj, said device Tj determining a Boolean value with a probability p; and in response to said determining said Boolean value, said device Tj transmitting said map stored in said device Tj to one or more other devices listening to said device Tj, wherein said one or more other devices are included in said N devices and include a device Ti, wherein said device Ti is said first device, and wherein said receiving said map is performed in response to said transmitting said map. - View Dependent Claims (19, 20)
-
-
16. A process for supporting computing infrastructure, said process comprising:
-
providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable code in a computer system comprising a processor, wherein said processor carries out instructions contained in said code causing said computer system to perform a method of collaboratively synchronizing devices communicating in an ad hoc network; and providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying other computer-readable code in said computer system further comprising other processors of N devices, wherein said other processors carry out instructions contained in said other code causing said computer system to further perform said method, wherein said method comprises; a first device receiving a map from a second device, wherein said first device and said second device are included in devices communicating in said ad hoc network in which no device of said devices acts as a master device or base station in said ad hoc network, said devices collaboratively synchronized at a time frame level based on time frames, each time frame having time slots, and wherein said map includes an allocation of said time slots to said devices; subsequent to said receiving said map, said first device determining said map indicates a conflict between said first device and another device of said devices, said conflict being indicated by a same time slot of said time slots being allocated to said first device and to said another device; in response to said determining said map indicates said conflict, said first device resolving said conflict by allocating another time slot of said time slots to said first device so that different time slots of said time slots are allocated to said first device and said another device, and each slot of said time slots is allocated to no more than a single corresponding device of said devices; said N devices being said devices and communicating with each other in said ad hoc network by a Media Access Control (MAC) scheme based on said time frames, said ad hoc network having no network infrastructure, said time slots being S time slots, each time slot of said S time slots allocated to one or more corresponding devices of said N devices, wherein N and S are integers, wherein N is an integer greater than 2, wherein N is less than or equal to S, and wherein no device of said devices acting as a master device or base station in said ad hoc network is indicated by no device of said N devices dictates an allocation of said S time slots to said N devices; a device Tj of said N devices determining a current time slot s of said S time slots is occurring in a time frame of said time frames and is allocated to said device Tj, wherein device Tj is said second device; in response to said determining said current time slot s is occurring and is allocated to said device Tj, said device Tj determining a Boolean value with a probability p; and in response to said determining said Boolean value, said device Tj transmitting said map stored in said device Tj to one or more other devices listening to said device Tj, wherein said one or more other devices are included in said N devices and include a device Ti, wherein said device Ti is said first device, and wherein said receiving said map is performed in response to said transmitting said map.
-
Specification