System and method for timeslot and channel allocation

• US 8,040,857 B2
• Filed: 12/07/2007
• Issued: 10/18/2011
• Est. Priority Date: 12/07/2006
• Status: Active Grant

• Current Assignee: OL Security LLC (Intellectual Ventures LLC)
• Original Assignee: Misonimo Chi Acquisitions LLC (Intellectual Ventures LLC)
• Inventors: Wu, Yun, Tao, Xiaojing, Nova, Michael, Gui, Chao, Wang, Weilin, Wang, Xudong
• Primary Examiner(s): Lin; Kenny S
• Application Number:
  US11/952,948
• Publication Number:
  US 20080137620A1
• Time in Patent Office: 1,411 Days
• Field of Search: 370/337, 370/322, 455/450
• US Class Current: 370/337
• CPC Class Codes: H04L 1/20 using signal quality detector
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames

Abstract

A distributed multi-channel TDMA MAC time slot and channel allocation algorithm for wireless networks is provided. The time slot and channel allocation includes a distributed allocation phase and an allocation adjustment phase. Each phase begins allocation at a first node and continues node-by-node until the last node in the network. The allocation then reflects back from the last node to the first node. At each node in the path, the node can initiate resource allocation between itself and its neighbor nodes. Nodes that are within range of the wireless network but are not on the path do not initiate resource allocation but instead participate in the resource allocation initiated from other nodes.

Claims

1. A method for time division multiple access timeslot and channel allocation in a wireless communication network having a plurality of nodes comprising:

during a distributed allocation phase, a particular node of the plurality of nodes acting as a current distributed-allocation leader node, wherein acting as a current distributed-allocation leader node comprises;

allocating timeslots to active links between the particular node and neighboring nodes,

allocating channels for the allocated timeslots;

selecting a new distributed-allocation leader node from among the plurality of nodes; and

during a subsequent allocation adjustment phase, the particular node acting as a current allocation-adjustment leader node, wherein acting as a current allocation-adjustment leader node comprises;

identifying a maximum number of time slots;

identifying one or more additional timeslots available for allocation based on a difference between the timeslots allocated by the particular node during the distributed allocation phase and the maximum number of time slots;

allocating the one or more additional timeslots and corresponding channels to one or more active links between the particular node and one or more neighboring nodes; and

selectin a new allocation-adjustment leader node from among the plurality of nodes.

2. The method of claim 1, wherein the wireless communication network is one of a WiMAX network, a 802.11 network, and a sensor network.

3. The method of claim 1, wherein the distributed allocation phase further comprises the particular node, in response to receiving a notification that a last node in a path has been reached, forwarding the notification to a parent node.

4. The method of claim 1, further comprising receiving an instruction from a parent node identifying the particular node as a candidate distributed-allocation leader node.

5. The method of claim 4, further comprising in response to receiving a request to act as a current distributed-allocation leader node by a second node different from the parent node, the particular node responsively transmitting a revocation message to the parent node.

6. The method of claim 1, wherein selecting a new distributed-allocation leader node comprises identifying a plurality of candidate distributed-allocation leader nodes and selecting one of the candidate distributed-allocation leader nodes as the new distributed-allocation leader node.

7. The method of claim 6, wherein the selected candidate distributed-allocation leader node is the node with the largest number of connected neighboring nodes.

8. The method of claim 1, further comprising, during the distributed allocation phase, the particular node receiving synchronization timing information from an initiating node.

9. The method of claim 8, further comprising, at a time identified by the synchronization timing information, the particular node using the allocated channels and timeslots to transmit packets to one or more neighboring nodes.

10. The method of claim 1, wherein the neighboring nodes are identified as those network nodes within one communication hop of the particular node.

11. The method of claim 10, wherein ten time slots are assigned to the active links between the particular node and the neighboring nodes.

12. The method of claim 1, wherein identifying the maximum number of time slots comprises determining a largest number of time slots assigned to any one node out of the plurality of nodes in the network during the distributed allocation phase.

13. A wireless communication device supporting time division multiple access timeslot and channel allocation in a wireless communication network and configured to:

during a distributed allocation phase, act as a current distributed-allocation leader node, wherein being configured to act as a distributed-allocation leader node comprises being configured to;

allocate timeslots to active links between the communication device and neighboring nodes in the network,

allocate channels for the allocated timeslots;

select a new distributed-allocation leader node from among the plurality of nodes; and

during a subsequent allocation adjustment phase, act as a current allocation-adjustment leader node, wherein being configured to act as an allocation-adjustment leader node comprises being configured to;

identify a maximum number of time slots;

identify one or more additional timeslots available for allocation based on a difference between the timeslots allocated by the communication device during the distributed allocation phase and the maximum number of time slots;

allocate the one or more additional timeslots and corresponding channels to one or more active links between the communication device and one or more neighboring nodes; and

select a new allocation-adjustment leader node out of the plurality of nodes.

14. The device of claim 13, wherein the wireless communication network is one of a WiMAX network, a 802.11 network, and a sensor network.

15. The device of claim 13, wherein the communication device is further configured to receive a notification that a last node in a path has been reached during the distributed allocation phase and forward the notification to a parent node.

16. The device of claim 13, wherein the communication device is further configured to receive an instruction from a parent node identifying the particular node as a candidate distributed-allocation leader node.

17. The device of claim 16, wherein the communication device is further configured to receive a request to act as a current distributed-allocation leader node by a second node different from the parent node, and in response, to transmit a revocation message to the parent node.

18. The device of claim 13, wherein the communication device is further configured to select the new distributed-allocation leader node by a process comprising:

identifying a plurality of candidate distributed-allocation leader nodes and selecting one of the candidate distributed-allocation leader nodes as the new distributed-allocation leader node.

19. The device of claim 18, wherein the selected candidate distributed-allocation leader node is the candidate node with the largest number of neighboring nodes.

20. The device of claim 13, wherein the communication device is further configured to, during the distributed allocation phase, receive synchronization timing information from an initiating node.

21. The device of claim 20, wherein the communication device is further configured to, at a time identified by the synchronization timing information, use the allocated channels and timeslots to transmit packets to one or more neighboring nodes.

22. The device of claim 13, wherein the neighboring nodes are identified as those network nodes within one communication hop of the communication device.

23. The device of claim 22, wherein ten time slots are assigned to the active links between the communication device and the neighboring nodes.

24. The device of claim 13, wherein the communication device is configured to identify the maximum number of time slots by determining a largest number of time slots assigned to any one node out of the plurality of nodes in the network during the distributed allocation phase.

25. An article of manufacture including a computer readable medium having instructions stored thereon that, in response to execution by a computing device, cause the computing device to perform operations in a wireless communication network comprising:

during a distributed allocation phase, the computing device acting as a current distributed-allocation leader node, wherein acting as a current distributed-allocation leader node comprises;

allocating timeslots to active links between the computing device and neighboring nodes,

allocating channels for the allocated timeslots;

selecting a new distributed-allocation leader node from among the plurality of nodes; and

during a subsequent allocation adjustment phase, the computing device acting as a current allocation-adjustment leader node, wherein acting as an allocation-adjustment leader node comprises;

identifying a maximum number of time slots;

identifying one or more additional timeslots available for allocation based on a difference between the timeslots allocated by the computing device during the distributed allocation phase and the maximum number of time slots;

allocating the one or more additional timeslots and corresponding channels to one or more active links between the computing device and one or more neighboring nodes; and

selecting a new allocation-adjustment leader node from among the plurality of nodes.

26. The article of manufacture of claim 25, wherein the wireless communication network is one of a WiMAX network, a 802.11 network, and a sensor network.

27. The article of manufacture of claim 25, wherein the operations further comprise, during the distributed allocation phase and in response to receiving a notification that a last node in a path has been reached, forwarding the notification to a parent node.

28. The article of manufacture of claim 25, wherein the operations further comprise, receiving an instruction from a parent node identifying the computing device as a candidate distributed-allocation leader node.

29. The article of manufacture of claim 28, wherein the operations further comprise receiving a request to act as a current distributed-allocation leader node by a second node different from the parent node, and in response, transmitting a revocation message to the parent node.

30. The article of manufacture of claim 25, wherein selecting a new distributed-allocation leader node comprises identifying a plurality of candidate nodes and selecting one of the candidate nodes as the new distributed-allocation leader node.

31. The article of manufacture of claim 30, wherein the selected candidate distributed-allocation leader node is the candidate node with the largest number of connected neighboring nodes.

32. The article of manufacture of claim 25, wherein the operations further comprise, during the distributed allocation phase, receiving synchronization timing information from an initiating node.

33. The article of manufacture of claim 32, wherein the operations further comprise, at a time identified by the synchronization timing information, the computing device using the allocated channels and timeslots to transmit packets to one or more neighboring nodes.

34. The article of manufacture of claim 25, wherein the neighboring nodes are identified as those network nodes within one communication hop of the computing device.

35. The article of manufacture of claim 34, wherein ten time slots are assigned to the active links between the computing device and the neighboring nodes.

36. The article of manufacture of claim 25, wherein identifying the maximum number of time slots comprises determining a largest number of time slots assigned to any one node out of the plurality of nodes in the network during the distributed allocation phase.

37. A wireless communication device supporting time division multiple access timeslot and channel allocation in a wireless communication network and comprising:

means for acting as a current distributed-allocation leader node during a distributed allocation phase, wherein acting as a current distributed-allocation leader node comprises;

allocating timeslots to active links between the communication device and neighboring nodes,

allocating channels to the allocated timeslots;

selecting a new distributed-allocation leader node from among the plurality of nodes; and

means for acting as a current allocation-adjustment leader node during a subsequent allocation adjustment phase, wherein acting as a current allocation-adjustment leader node comprises;

identifying a maximum number of time slots;

identifying one or more additional timeslots available for allocation based on a difference between the timeslots allocated by the communication device during the distributed allocation phase and the maximum number of time slots;

allocating the one or more additional timeslots and corresponding channels to one or more active links between the communication device and one or more neighboring nodes; and

selecting a new allocation-adjustment leader node from among the plurality of nodes.