METHOD AND APPARATUS FOR ASSIGNING SLOT

• US 20150071158A1
• Filed: 09/09/2014
• Published: 03/12/2015
• Est. Priority Date: 09/10/2013
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: WANG, Hao, TIAN, Jun, FAN, Xiaojing, XU, Yi, YI, Longteng, KONDO, Taiji
• Granted Patent: US 9,526,102 B2
• Time in Patent Office: Days
• US Class Current: 370/312
• 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 first constructing unit configured to construct a GTS binary tree;

a storing unit configured to store the GTS binary tree constructed by the first constructing unit and pre-store GTS request information of all neighboring nodes within a collision domain of a local node and reservation history information of the local node;

a second constructing unit configured to construct 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; and

a broadcasting unit configured to broadcast the HELLO packet constructed by the second constructing unit, so that a node receiving the HELLO packet performs slot reservation according to information contained in 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 second constructing unit comprises:

a first selecting module configured to select a part of records from a local GTS table according to a predetermined policy and take them as the GTS request information of the neighboring node; and

a first determining module configured to determine 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 first selecting module 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 first determining module comprises:

a first calculating module configured to calculate a period of the requested GTS;

a first judging module configured to judge 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

a first processing module configured to select another GTS and take 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 take 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 first calculating module 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 first calculating module 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, the first processing module searches the GTS binary tree constructed by the constructing unit 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 storing unit 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 second constructing unit comprises:

a second judging module configured to judge whether the local node is a sink node;

a second calculating module configured to obtain 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 add the calculated traffic within the collision domain of the sink node into the HELLO packet; and

a second processing module configured to add the traffic within the collision domain of the sink node saved by the storing unit into the HELLO packet when the local node is not the sink node.

13. The node according to claim 12, wherein the second calculating module 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 first constructing unit 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 node comprises:

a processing unit comprising an updating module, and/or a judging module, and/or a merging module, and/or an authenticating module;

wherein the updating module updates total traffic within a collision domain of a sink node according to a received HELLO packet, the judging module determines a authenticating result given by a sender of the HELLO packet to the locally requested GTS, the merging module merges a GTS list in the HELLO packet with a local GTS table, and the authenticating module authenticates a GTS requested by the sender of the HELLO packet.

16. The node according to claim 15, wherein the updating module 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.

17. The node according to claim 15, wherein the judging module 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.

18. The node according to claim 15, wherein the merging module 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 processing unit 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 processing unit adds the record into the local GTS table, and adds 1 to the distance of the record.

19. The node according to claim 15, wherein the authenticating module 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.

20. A slot assignment method, comprising:

constructing an HELLO packet, the HELLO packet comprising GTS 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; and

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