MASTERLESS SLOT ALLOCATION

• US 20150131647A1
• Filed: 01/22/2015
• Published: 05/14/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
• Granted Patent: US 9,629,112 B2
• Time in Patent Office: Days
• US Class Current: 370/350
• 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

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.

Claims

1. A method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of:

a device T_i 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 T_i 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 T_j 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 T_j (2) a selection by the device T_j of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device T_j that the selected Boolean value is true, and (4) a transmission by the device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, wherein the one or more other devices are included in the N devices and include a device T_i, the device T_i receiving the map and determining the map indicates a conflict between the device T_i 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 T_i and to the other device; and

in response to the step of determining the map indicates the conflict, the device T_i resolving the conflict by allocating another time slot included in the S time slots to the device T_i so that different time slots are allocated to the device T_i 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.

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

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

3. The method of claim 1, wherein the step of receiving the map includes receiving the map that includes the allocation of the S time slots to the N devices, the allocation of the S time slots including first, second and third fields corresponding the S time slots, wherein the first field is a busy field that includes busy field indicators corresponding to the 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 the S time slots is free to be allocated to a device of the N devices, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device of the N devices, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the N devices, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device of the N devices, and wherein the third field which is a life credit field includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in the busy field is.

4. The method of claim 3, wherein the step of resolving the conflict includes the steps of:

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

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

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

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

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

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

5. The method of claim 3, further comprising the steps of:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

determining the busy field corresponding to the time slot x₁ and stored in the map is the third busy field indicator that indicates the time slot x₁ is overbooked;

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

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

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

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

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

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

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

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

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

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

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

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

12. The method of claim 3, further comprising the steps of:

in response to the step of transmitting the map, the device T_j decrementing each entry in the life credit field;

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

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

13. The method of claim 12, further comprising the steps of:

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

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

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

14. The method of claim 1, the method further comprising the step of:

providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable program code in the device T_i, the program code being executed by a processor included in device T_i to implement the steps of communicating, receiving, determining, and receiving.

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 T_i, and the method comprising the steps of;

the device T_i 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 T_i 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 T_j 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 T_j (2) a selection by the device T_j of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device T_j that the selected Boolean value is true, and (4) a transmission by the device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, wherein the one or more other devices are included in the N devices and include a device T_i, the device T_i receiving the map and determining the map indicates a conflict between the device T_i 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 T_i and to the other device; and

in response to the step of determining the map indicates the conflict, the device T_i resolving the conflict by allocating another time slot included in the S time slots to the device T_i so that different time slots are allocated to the device T_i 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.

16. The computer system of claim 15, wherein the step of determining the map indicates the conflict includes the step of determining the conflict is between the device T_i and a device T_k, the device T_k being the other device, wherein the step of determining the conflict is between the devices T_i and T_k is based on T_j=T_k and the device T_j being allocated the same time slot as the device T_i, or based on T_j≠

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

17. The computer system of claim 15, wherein the step of receiving the map includes receiving the map that includes the allocation of the S time slots to the N devices, the allocation of the S time slots including first, second and third fields corresponding the S time slots, wherein the first field is a busy field that includes busy field indicators corresponding to the 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 the S time slots is free to be allocated to a device of the N devices, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device of the N devices, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the N devices, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device of the N devices, and wherein the third field which is a life credit field includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in the busy field is.

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 T_i to implement a method of collaboratively synchronizing devices in an ad hoc network, the method comprising the steps of;

the device T_i 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 T_i 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 T_j 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 T_j (2) a selection by the device T_j of one of two Boolean values, the selected Boolean value having a probability p of being selected, (3) a determination by the device T_j that the selected Boolean value is true, and (4) a transmission by the device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, wherein the one or more other devices are included in the N devices and include a device T_i, the device T_i receiving the map and determining the map indicates a conflict between the device T_i 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 T_i and to the other device; and

in response to the step of determining the map indicates the conflict, the device T_i resolving the conflict by allocating another time slot included in the S time slots to the device T_i so that different time slots are allocated to the device T_i 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.

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

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

20. The computer program product of claim 18, wherein the step of receiving the map includes receiving the map that includes the allocation of the S time slots to the N devices, the allocation of the S time slots including first, second and third fields corresponding the S time slots, wherein the first field is a busy field that includes busy field indicators corresponding to the 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 the S time slots is free to be allocated to a device of the N devices, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device of the N devices, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the N devices, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device of the N devices, and wherein the third field which is a life credit field includes life credit indicators, each life credit indicator indicating how up-to-date a corresponding busy field indicator in the busy field is.