Method and apparatus for assigning slot

• US 9,526,102 B2
• Filed: 09/09/2014
• Issued: 12/20/2016
• Est. Priority Date: 09/10/2013
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Fan, Xiaojing, Wang, Hao, Xu, Yi, Yi, Longteng, Tian, Jun, Kondo, Taiji
• Primary Examiner(s): Kassim, Khaled
• Assistant Examiner(s): BELETE, BERHANU D
• Application Number:
  US14/481,711
• Publication Number:
  US 20150071158A1
• Time in Patent Office: 833 Days
• Field of Search: 370/312
• US Class Current: 1/1
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

Embodiments of the present invention provide a method and apparatus for assigning slot. The method includes: constructing an HELLO packet, the HELLO packet including GTS request information of a local node or including GTS request information of the local node and GTS request information of at least one neighboring node within a collision domain of the local node; and broadcasting the HELLO packet, so that a node receiving the HELLO packet performs slot reservation according to information contained in the HELLO packet. With the method and apparatus for assigning slot provided by the embodiments of the present invention, no central controller is needed any longer in comparison with a centralized slot assignment method, complexity of calculation is lowered, and utilization of slot is improved.

Claims

1. A node, comprising:

a memory; and

a processor coupled to the memory and configured to execute processes including;

constructing a Guaranteed Time Slot (GTS) binary tree;

storing the constructed GTS binary tree and pre-storing GTS request information of all neighboring nodes within a collision domain of a local node and reservation history information of the local node;

constructing an HELLO packet, the HELLO packet comprising GTS request information of the local node or comprising GTS request information of the local node and GTS request information of at least one neighboring node within the collision domain of the local node;

broadcasting the constructed HELLO packet, so that a node receiving the HELLO packet performs slot reservation according to information contained in the HELLO packet;

updating total traffic within a collision domain of a sink node according to a received HELLO packet;

determining a authenticating result given by a sender of the HELLO packet to the locally requested GTS;

merging a GTS list in the HELLO packet with a local GTS table; and

authenticating a GTS requested by the sender of the HELLO packet.

2. The node according to claim 1, wherein GTS request information of the neighboring nodes is stored in a record manner, each record corresponding to a neighboring node and including an address of the neighboring node, an address of a next hop of the neighboring node reaching a sink node, a power of a period of a GTS requested by the neighboring node, an offset of the GTS requested by the neighboring node, traffic of the neighboring node, a distance/hop count from the neighboring node to the local node, and confirmation information of the GTS requested by the neighboring node.

3. The node according to claim 1, wherein the local reservation history information contains a local address, an address of a next hop of the local node reaching a sink node, a power of a period of a GTS requested by the local node, an offset of the GTS requested by the local node, and traffic of the local node.

4. The node according to claim 3, wherein the local reservation history information further contains state of the GTS requested by the local node.

5. The node according to claim 1, wherein the processor is further configured to execute processes including:

selecting a part of records from a local GTS table according to a predetermined policy and taking them as the GTS request information of the neighboring node; and

determining a requested GTS, and take information to which the requested GTS corresponds as the GTS request information of the local node.

6. The node according to claim 5, wherein when a maximum hop count of the neighboring nodes within the collision domain of the local node is n, the processor takes records of all one-hop neighboring nodes within the collision domain of the local node in the local GTS table and records of 2 to n−

1-hop neighboring nodes within the collision domain of the local node with confirmation information being agree in the local GTS table as the GTS request information of the neighboring node, or takes records of all 1 to n−

1-hop neighboring nodes in the local GTS table as the GTS request information of the neighboring node.

7. The node according to claim 5, wherein the processor is further configured to execute processes including:

calculating a period of the requested GTS;

judging whether the period of the requested GTS varies and/or whether state of the requested GTS is invalid according to locally saved reservation history information of the local node; and

selecting another GTS and taking correlation information of the selected GTS as the requested GTS when the period of the requested GTS varies or the state of the requested GTS is invalid, and taking the GTS request information of the local node in the reservation history information as the requested GTS when the period of the requested GTS does not vary and the state of the requested GTS is valid.

8. The node according to claim 7, wherein the processor calculates traffic of the local node, and calculates a period of the requested GTS according to the following formula by using locally saved total traffic within a collision domain of a sink node and the calculated traffic of the local node:

9. The node according to claim 8, wherein the processor obtains the traffic of the local node by traversing each of the records in the local GTS table and adding the traffic to which a record with receiving node being the local node in the records corresponds into the traffic of the local node.

10. The node according to claim 7, wherein in selecting a GTS, corresponding to the calculated period of the requested GTS, processor searches the constructed GTS binary tree according to a predetermined policy, and selects a first idle GTS on the line where the period of the requested GTS is present, or selects a GTS with a GTS offset less than a GTS offset of its receiving node.

11. The node according to claim 10, wherein the predetermined policy is to search the locally constructed GTS binary tree from the left to the right, or to search the locally constructed GTS binary tree from the right to the left.

12. The node according to claim 1, wherein the processor further saves traffic within a collision domain of a sink node, the HELLO packet further comprises total traffic within the collision domain of the sink node, and the processor is further configured to execute processes including:

judging whether the local node is a sink node;

obtaining the traffic within the collision domain of the sink node by traversing each of the records in the local GTS table and adding the traffic to which each of the records corresponds into the traffic within the collision domain of the sink node when the local node is the sink node, and adding the calculated traffic within the collision domain of the sink node into the HELLO packet; and

adding the saved traffic within the collision domain of the sink node into the HELLO packet when the local node is not the sink node.

13. The node according to claim 12, wherein the processor obtains the traffic within the collision domain of the sink node by traversing each of the records in the local GTS table and adding the traffic to which each of the records corresponds into the traffic within the collision domain of the sink node.

14. The node according to claim 1, wherein the processor generates the root Root=(2⁰,0) of the GTS binary tree according to formula GTS=(2^exp,offset);

where, exp=0, and offset=0;

generates a left child GTS of each GTS according to formula GTS_left-child=(2^exp+1,offset);

generates a right child GTS of each GTS according to formula GTS_right-child=(2^exp+1,offset+2^exp); and

constructs the GTS binary tree according to the root of the GTS binary tree, the left child GTS of each GTS and the right child GTS of each GTS.

15. The node according to claim 1, wherein the processor updates the locally saved traffic within the collision domain of the sink node when the total traffic within the collision domain of the sink node in the HELLO packet is greater than the locally saved total traffic within the collision domain of the sink node;

otherwise, keeps the locally saved traffic within the collision domain of the sink node unchanged.

16. The node according to claim 1, wherein the processor scans each record in the GTS list of the HELLO packet to find a record with an address of a transmission node being the address of the local node, and determines that the locally requested GTS as being invalid when confirmation information of the record is denial, and determines that the locally requested GTS as being valid when the confirmation information of the record is agree.

17. The node according to claim 1, wherein the processor merges a record in the GTS list of the HELLO packet with confirmation information being agree into the local GTS table;

wherein, if the record with the confirmation information being agree has been saved in the local GTS table, the processor replaces a corresponding record in the local GTS table with the record in the HELLO packet when a distance of the record is less than a distance of the corresponding record in the local GTS table, and adds 1 to the distance of the record; and

wherein if the record with the confirmation information being agree has not been saved in the local GTS table, the processor adds the record into the local GTS table, and adds 1 to the distance of the record.

18. The node according to claim 1, wherein the processor performs local receiving inference detection, so as to determine whether the GTS requested by the sender of the HELLO packet collides with the GTS requested by a neighboring node which takes the local node as a receiving node, and performs local transmission inference detection, so as to determine whether the GTS requested by the sender of the HELLO packet collides with the locally requested GTS;

in case of no collision, grants agree to the GTS requested by the sender of the HELLO packet; and

in case of collision, grants agree to the GTS requested by the sender of the HELLO packet when an address of the sender of the HELLO packet is greater than an address of the neighboring node or an address of the sender of the HELLO packet is greater than an address of the local node;

otherwise, grants denial to the GTS requested by the sender of the HELLO packet.

19. A slot assignment method, comprising:

constructing an HELLO packet, the HELLO packet comprising GTS (Guaranteed Time Slot) request information of a local node or comprising GTS request information of the local node and GTS request information of at least one neighboring node within a collision domain of the local node;

broadcasting the HELLO packet, so that a node receiving the HELLO packet performs slot reservation according to information contained in the HELLO packet;

updating total traffic within a collision domain of a sink node according to a received HELLO packet;

determining a authenticating result given by a sender of the HELLO packet to the locally requested GTS;

merging a GTS list in the HELLO packet with a local GTS table; and

authenticating a GTS requested by the sender of the HELLO packet.