Masterless slot allocation

• US 8,972,577 B2
• Filed: 09/08/2010
• Issued: 03/03/2015
• Est. Priority Date: 09/02/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauchot, Frederic, Clement, Jean-Yves, Marmigere, Gerard, Picon, Joaquin
• Primary Examiner(s): JEAN GILLES, JUDE
• Application Number:
  US12/877,210
• Publication Number:
  US 20120059936A1
• Time in Patent Office: 1,637 Days
• Field of Search: 709/248, 709/226, 709/233, 711/137, 711/154, 712/207
• US Class Current: 709/226
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 56/0015 one node acting as a reference for the others
• CPC Class Codes: H04W 56/002 Mutual synchronization
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 74/0841 with collision treatment
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

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 T_j 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 T_j, wherein device T_j, is said second device;

in response to said determining said current time slot s is occurring and is allocated to said device T_j, said device T_j determining a Boolean value with a probability p; and

in response to said determining said Boolean value, said device T_j transmitting said map stored in said device T_j to one or more other devices listening to said device T_j, wherein said one or more other devices are included in said N devices and include a device T_i, wherein said device T_i is said first device, and wherein said receiving said map is performed in response to said transmitting said map.

2. The method of claim 1, wherein said determining said map indicates said conflict includes determining said conflict is between said device T_i and a device T_k, said device T_k being said another device, wherein said determining said conflict is between said devices T_i and T_k, is based on T_j=T_k and said device T_j being allocated said same time slot as said device T_i, or based on T_j≠

T_k and said device T_j previously receiving a transmission of another map from another device of said N devices, said another map indicating said same time slot is allocated to said devices T_i and T_k, and said transmission of said another map having occurred prior to said transmitting said map.

3. The method of claim 1, wherein said transmitting said map includes transmitting said map that includes said allocation of said S time slots to said N devices, said allocation of said S time slots including first, second and third fields corresponding said S time slots, wherein said first field (busy field) includes busy field indicators corresponding to said S time slots, each busy field indicator selected from the group consisting of a first busy field indicator that indicates a corresponding time slot of said S time slots is free to be allocated to a device of said N devices, a second busy field indicator that indicates said corresponding time slot is busy and allocated to exactly one device of said N devices, and a third busy field indicator that indicates said corresponding time slot is overbooked and allocated to two or more devices of said N devices, wherein said second field (ID field) includes identifiers, each identifier identifying a corresponding device of said N devices, and wherein said third field (life credit field) includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in said busy field is.

4. The method of claim 3, wherein said resolving said conflict includes:

determining said current time slot s is allocated to devices T_i and T_j;

in response to said determining said current time slot s is allocated to devices T_i and T_j, determining one or more time slots of said S time slots other than said current time slot s are free to be allocated;

in response to said determining said one or more time slots are free, removing said device T_i from said current time slot s;

selecting a new time slot from said one or more time slots determined to be free and allocating said new time slot to said device T_i;

setting a first value of said busy field to said second busy field indicator to indicate that said new time slot is busy and allocated to exactly one device of said N devices, wherein said exactly one device is said device T_i; and

setting a second value of said life credit field to indicate that said first value of said busy field is information that has maximum freshness according to predetermined criteria.

5. The method of claim 3, further comprising:

subsequent to said receiving said map, said device T_i updating a first set of information corresponding to a time slot x_i allocated to device T_i based on said map; and

subsequent to said receiving said map, said device T_i updating a second set of information corresponding to time slots other than said time slot x_i based on said map.

6. The method of claim 5, wherein said updating said first set of information corresponding to said time slot x_i includes:

setting a first value of said life credit field corresponding to said time slot x_i to indicate that information associated with said time slot x_i and stored in said device T_i has maximum freshness according to predetermined criteria;

determining a second value of said busy field corresponding to said current time slot s is equal to said first busy field indicator that indicates said current time slot s is free to be allocated;

in response to said determining said second value of said busy field is equal to said first busy field indicator, setting said second value of said busy field corresponding to said current time slot s to said second busy field indicator to indicate said current time slot s is busy and allocated only to said device T_j;

in response to said determining said second value of said busy field is equal to said first busy field indicator, setting said ID field corresponding to said current time slot s to a hashed version of an identifier of said device T_j; and

in response to said determining said second value of said busy field is equal to said first busy field indicator, setting said life credit field corresponding to said current time slot s to a value that indicates information associated with said current time slot s and stored in said device T_i has maximum freshness according to said predetermined criteria.

7. The method of claim 5, wherein said updating said first set of information corresponding to said time slot x_i includes:

setting a first value of said life credit field corresponding to said time slot x_i to indicate that information associated with said time slot x_i and stored in said device T_i has maximum freshness according to predetermined criteria;

determining a second value of said busy field corresponding to said current time slot s is equal to said second busy field indicator that indicates said current time slot s is busy and said ID field corresponding to said current time slot s is not equal to a hashed version of an identifier of said device T_j;

in response to said determining said second value of said busy field is equal to said second busy field indicator and said ID field corresponding to said current time slot s is not equal to said hashed version of said identifier of said device T_j, setting said second value of said busy field corresponding to said current time slot s to said third busy field indicator to indicate said current time slot s is overbooked and allocated to said device T_j and to a second device of said N devices that is not said device T_j;

in response to said setting said second value of said busy field to said third busy field indicator to indicate said current time slot s is overbooked, said device T_i detecting a conflict between said device T_j and said second device based on said current time slot s being overbooked; and

in response to said determining said second value of said busy field is equal to said second busy field indicator and said ID field corresponding to said current time slot s is not equal to said hashed version of said identifier of said device T_j, setting said life credit field corresponding to said current time slot s to a value that indicates information associated with said current time slot s and stored in said device T_i has maximum freshness according to said predetermined criteria.

8. The method of claim 5, wherein said updating said first set of information corresponding to said time slot x_i includes:

setting a first value of said life credit field corresponding to said time slot x_i to indicate that information associated with said time slot x_i and stored in said device T_i has maximum freshness according to predetermined criteria;

determining a second value of said busy field corresponding to said current time slot s is equal to said second busy field indicator that indicates said current time slot s is busy and said ID field corresponding to said current time slot s is equal to a hashed version of an identifier of said device T_j;

in response to said determining said second value of said busy field is equal to said second busy field indicator and said ID field corresponding to said current time slot s is equal to said hashed version of said identifier of said device T_j, setting said life credit field corresponding to said current time slot s to a value that indicates information associated with said current time slot s and stored in said device T_i has maximum freshness according to said predetermined criteria.

9. The method of claim 5, wherein said updating said second set of information corresponding to time slots other than said time slot x_i includes:

determining said busy field corresponding to said time slot x_i and stored in said map is said third busy field indicator that indicates said time slot x_i is overbooked;

in response to said determining said busy field corresponding to said time slot x_i is said third busy field indicator that indicates said time slot x_i is overbooked, determining one or more time slots of said S time slots other than said time slot x_i are free to be allocated;

in response to said determining said one or more time slots are free, removing said device T_i from said time slot x_i;

selecting a new time slot from said one or more time slots determined to be free and allocating said new time slot to said device T_i;

setting a first value of said busy field corresponding to said new time slot to said second busy field indicator to indicate that said new time slot is busy and allocated to exactly one device of said N devices, wherein said exactly one device is said device T_i; and

setting a second value of said life credit field corresponding to said time slot x_i to indicate that said first value of said busy field is information that has maximum freshness according to predetermined criteria.

10. The method of claim 5, wherein said updating said second set of information corresponding to time slots other than said time slot x_i includes:

determining a first value of said busy field corresponding to a time slot k of said S time slots other than said current time slot s and stored in said map is greater than a second value of said busy field corresponding to said time slot k and stored in said device T_i;

in response to said determining said first value of said busy field corresponding to said time slot k is greater than said second value of said busy field corresponding to said time slot k, setting said second value of said busy field corresponding to said time slot k and stored in said device T_i to said first value of said busy field corresponding to said time slot k and stored in said map; and

in response to said determining said first value of said busy field corresponding to said time slot k is greater than said second value of said busy field corresponding to said time slot k, setting a third value of said life credit field corresponding to said time slot k and stored in said device T_i to a fourth value of said life credit field corresponding said time slot k and stored in said map.

11. The method of claim 5, wherein said updating said second set of information corresponding to time slots other than said time slot x_i includes:

determining a first value of said busy field corresponding to a time slot k of said S time slots other than said current time slot s and stored in said map is equal to a second value of said busy field corresponding to said time slot k and stored in said device T_i; and

in response to said determining said first value of said busy field corresponding to said time slot k is equal to said second value of said busy field corresponding to said time slot k, setting a third value of said life credit field corresponding to said time slot k and stored in said device T_i to a maximum of said third value of said life credit field corresponding to said time slot k and stored in said device T_i and a fourth value of said life credit field corresponding to said time slot k and stored in said map.

12. The method of claim 3, further comprising:

in response to said transmitting said map, said device T_j decrementing each entry in said life credit field;

determining a first entry in said life credit field indicates that a second entry in said busy field corresponding to said first entry has not been refreshed for a period of time that exceeds a predetermined threshold; and

updating said second entry in said busy field to said first busy field indicator that indicates that a time slot corresponding to said first entry and to said second entry is free to be allocated to said device of said N devices.

13. The method of claim 12, further comprising:

in response to said decrementing each entry in said life credit field, determining all entries in said life credit field are null;

in response to determining all entries in said life credit field are null, updating a state of said device T_j to Dormant; and

subsequent to said updating said state to Dormant and in response to a determination of a subsequent occurrence of time slot s, said device T_j transmitting said map stored in device T_j with a probability q, wherein q is less than p.

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 T_j 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 T_j, wherein device T_j is said second device;

in response to said determining said current time slot s is occurring and is allocated to said device T_j, said device T_j determining a Boolean value with a probability p; and

in response to said determining said Boolean value, said device T_j transmitting said map stored in said device T_j to one or more other devices listening to said device T_j, wherein said one or more other devices are included in said N devices and include a device T_i, wherein said device T_i is said first device, and wherein said receiving said map is performed in response to said transmitting said map.

17. The computer system of claim 14, wherein said determining said map indicates said conflict includes determining said conflict is between said device T_i and a device T_k, said device T_k being said another device, wherein said determining said conflict is between said devices T_i and T_k, is based on T_j=T_k and said device T_j being allocated said same time slot as said device T_i, or based on T_j≠

T_k and said device T_j previously receiving a transmission of another map from another device of said N devices, said another map indicating said same time slot is allocated to said devices T_i and T_k, and said transmission of said another map having occurred prior to said transmitting said map.

18. The computer system of claim 14, wherein said transmitting said map includes transmitting said map that includes said allocation of said S time slots to said N devices, said allocation of said S time slots including first, second and third fields corresponding said S time slots, wherein said first field (busy field) includes busy field indicators corresponding to said S time slots, each busy field indicator selected from the group consisting of a first busy field indicator that indicates a corresponding time slot of said S time slots is free to be allocated to a device of said N devices, a second busy field indicator that indicates said corresponding time slot is busy and allocated to exactly one device of said N devices, and a third busy field indicator that indicates said corresponding time slot is overbooked and allocated to two or more devices of said N devices, wherein said second field (ID field) includes identifiers, each identifier identifying a corresponding device of said N devices, and wherein said third field (life credit field) includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in said busy field is.

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 T_j 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 T_j, wherein device T_j is said second device;

in response to said determining said current time slot s is occurring and is allocated to said device T_j, said device T_j determining a Boolean value with a probability p; and

in response to said determining said Boolean value, said device T_j transmitting said map stored in said device T_j to one or more other devices listening to said device T_j, wherein said one or more other devices are included in said N devices and include a device T_i, wherein said device T_i is said first device, and wherein said receiving said map is performed in response to said transmitting said map.

19. The computer program product of claim 15, wherein said determining said map indicates said conflict includes determining said conflict is between said device T_i and a device T_k, said device T_k being said another device, wherein said determining said conflict is between said devices T_i and T_k, is based on T_j=T_k and said device T_j being allocated said same time slot as said device T_i, or based on T_j≠

T_k and said device T_j previously receiving a transmission of another map from another device of said N devices, said another map indicating said same time slot is allocated to said devices T_i and T_k, and said transmission of said another map having occurred prior to said transmitting said map.

20. The computer program product of claim 15, wherein said transmitting said map includes transmitting said map that includes said allocation of said S time slots to said N devices, said allocation of said S time slots including first, second and third fields corresponding said S time slots, wherein said first field (busy field) includes busy field indicators corresponding to said S time slots, each busy field indicator selected from the group consisting of a first busy field indicator that indicates a corresponding time slot of said S time slots is free to be allocated to a device of said N devices, a second busy field indicator that indicates said corresponding time slot is busy and allocated to exactly one device of said N devices, and a third busy field indicator that indicates said corresponding time slot is overbooked and allocated to two or more devices of said N devices, wherein said second field (ID field) includes identifiers, each identifier identifying a corresponding device of said N devices, and wherein said third field (life credit field) includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in said busy field is.

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 T_j 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 T_j, wherein device T_j is said second device;

in response to said determining said current time slot s is occurring and is allocated to said device T_j, said device T_j determining a Boolean value with a probability p; and

in response to said determining said Boolean value, said device T_j transmitting said map stored in said device T_j to one or more other devices listening to said device T_j, wherein said one or more other devices are included in said N devices and include a device T_i, wherein said device T_i is said first device, and wherein said receiving said map is performed in response to said transmitting said map.