Masterless slot allocation

• US 9,723,583 B2
• Filed: 01/12/2017
• Issued: 08/01/2017
• Est. Priority Date: 09/02/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauchot, Frederic, Marmigere, Gerard, Clement, Jean-Yves, Picon, Joaquin
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): BHATTI, HASHIM S
• Application Number:
  US15/404,387
• Publication Number:
  US 20170127366A1
• Time in Patent Office: 201 Days
• Field of Search: None
• 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. Responsive to a transmission of a map by a first device to other device(s) listening to the first device, a second device determines the map, which allocates time slots to devices, indicates a conflict by which a same time slot is allocated to the second device and another device. The transmission is responsive to a determination that a Boolean value is true with a probability p if the first device is in an alive mode or a probability q if the first device is in a dormant mode, where p>q and q>0, and where p and q indicate respective likelihoods of performing the transmission. The second device resolves the conflict by allocating another time slot to the second device.

Claims

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

in response to a transmission by a device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, a device T_i determining the map indicates a conflict between the device T_i and another device, the conflict indicated by a same time slot included in S time slots being allocated to the device T_i and the other device, wherein the transmission is performed in response to a determination by the device T_j that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device T_j is in an alive mode reached in response to the device T_j 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 T_j is in a dormant mode reached in response to a delay since a last reception by the device T_j 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; 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 devices in the ad hoc network.

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 devices in the ad hoc network, 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, further comprising the step of the device T_i receiving the map that includes allocations of the S time slots to the devices in the ad hoc network, the allocations of the S time slots including first, second and third fields corresponding to 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 included in the devices in the ad hoc network, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device included in the devices in the ad hoc network, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the devices included in the ad hoc network, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device included in the devices in the ad hoc network, 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 a current time slot s included in the S time slots 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 included in 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 included in the devices in the ad hoc network, 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 a current time slot s included in the S time slots 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 a current time slot s included in the S time slots 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 a current time slot s included in the S time slots 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_i and stored in the map is the third busy field indicator that indicates the time slot x_i is overbooked;

in response to the step of determining the busy field corresponding to the time slot x_i 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 a 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 a 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 transmission of 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 a current time slot s included in the S time slots, the device T_j transmitting the map stored in device T_j with the probability q.

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 determining the map indicates the conflict and resolving the conflict.

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;

in response to a transmission by a device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, the device T_i determining the map indicates a conflict between the device T_i and another device, the conflict indicated by a same time slot included in S time slots being allocated to the device T_i and the other device, wherein the transmission is performed in response to a determination by the device T_j that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device T_j is in an alive mode reached in response to the device T_j 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 T_j is in a dormant mode reached in response to a delay since a last reception by the device T_j 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; 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 devices in the ad hoc network.

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 devices in the ad hoc network, 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 method further comprises the step of the device T_i receiving the map that includes allocations of the S time slots to the devices in the ad hoc network, the allocations of the S time slots including first, second and third fields corresponding to 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 included in the devices in the ad hoc network, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device included in the devices in the ad hoc network, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the devices included in the ad hoc network, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device included in the devices in the ad hoc network, 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 device; and

computer readable program code stored in the computer readable storage device, 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;

in response to a transmission by a device T_j of a map stored in the device T_j to one or more other devices listening to the device T_j, the device T_i determining the map indicates a conflict between the device T_i and another device, the conflict indicated by a same time slot included in S time slots being allocated to the device T_i and the other device, wherein the transmission is performed in response to a determination by the device T_j that a Boolean value is true, the Boolean value having a predetermined probability p of being true if the device T_j is in an alive mode reached in response to the device T_j 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 T_j is in a dormant mode reached in response to a delay since a last reception by the device T_j 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; 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 devices in the ad hoc network.

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 devices in the ad hoc network, 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 method further comprises the step of the device T_i receiving the map that includes allocations of the S time slots to the devices in the ad hoc network, the allocations of the S time slots including first, second and third fields corresponding to 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 included in the devices in the ad hoc network, a second busy field indicator that indicates the corresponding time slot is busy and allocated to exactly one device included in the devices in the ad hoc network, and a third busy field indicator that indicates the corresponding time slot is overbooked and allocated to two or more devices of the devices included in the ad hoc network, wherein the second field is an ID field that includes identifiers, each identifier identifying a corresponding device included in the devices in the ad hoc network, 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.