Scheduling method for use in a mesh network
View Patent ↗A scheduling technique useful in a mesh network includes scheduling a selected amount of traffic in the mesh network using a linear program approach that minimizes a time for the selected amount of traffic to reach its intended destination. The linear program is subject to a plurality of constraints that insure that the selected amount of traffic will reach its intended destination within the minimized time. An example is disclosed that uses such a technique for a mesh network having a root node that is a base station for wireless communications and a plurality of child nodes that comprise subscriber stations. A disclosed example is useful for centralized scheduling in a Wimax mesh network.
1. A method of communicating in a mesh network having a root node and a plurality of child nodes associated with the root node, comprising:
scheduling a selected amount of traffic in the mesh network using a linear program that minimizes a time for the selected amount of traffic to reach its intended destination subject to a plurality of constraints that ensure that the selected amount of traffic will reach its intended destination within the minimized time, wherein the plurality of constraints comprises
a constraint requiring that all transmissions from at least one of the plurality of child nodes to the root node will reach the root node within the minimized time, wherein the constraint requires that all uplink traffic via the at least one child node must be transmitted to the at least one child node from an originating child node of the at least one child node before the (K+1−h)th frame, where K is the total number of frames in the minimized time and h is the number of hops between the at least one child node and the root node; and
transmitting the selected amount of traffic.
2. The method of claim 1 , wherein the minimized time comprises a plurality of frames within which the selected amount of traffic will be transmitted between at least two of the nodes for the traffic to reach its intended destination.
3. The method of claim 1 , wherein the number of hops corresponds to a number of nodes between the at least one child node and the root node through which the root node and the at least one child node communicate with each other.
4. The method of claim 1 , wherein the constraint requires that all uplink traffic from the at least one child node to the root node be transmitted before the (K÷2−h)th frame, where K is the total number of frames in the minimized time and h is the number of hops between the at least one child node and the root node.
5. The method of claim 1 , wherein the plurality of constraints comprises
a constraint requiring that all transmissions from the root node to the at least one child node reach the at least one child node within the minimized time.
6. The method of claim 1 , wherein the plurality of constraints comprises
a constraint requiring that a total amount of traffic to and from each of the nodes does not exceed a corresponding capacity of each of the nodes.
7. The method of claim 1 , wherein the plurality of constraints comprises
a constraint requiring that the total uplink traffic transmitted by each of the plurality of child nodes during the minimized time is no greater than any uplink traffic received by one of the child nodes from any other of the plurality of child nodes during the minimized time and any uplink traffic originated by the one child node during the minimized time.
8. The method of claim 1 , wherein the plurality of constraints comprises
a constraint that requires that a total downlink traffic at each of the child nodes during the minimized time be no greater than any downlink traffic received by each child node from a neighbor parent node.
9. The method of claim 1 , wherein the plurality of constraints comprises
a constraint that requires that a child node that has not received any downlink traffic from at least one parent node transmits no downlink traffic during the minimum time.
10. The method of claim 1 , wherein the plurality of constraints comprises
a constraint that requires that the root node has no uplink traffic.
11. The method of claim 1 , comprising
allocating a plurality of mini slots within the minimized time to each of the nodes to accommodate the selected amount of traffic within the minimized time including scheduling all downlink transmissions from a first one of the nodes to any neighbor child node and determining a corresponding sending interval of the first one of the nodes and a receiving interval of any corresponding neighbor child node.
12. The method of claim 11 , comprising scheduling all uplink transmissions from any neighbor child node to the first one of the nodes and determining a corresponding sending interval for the any neighbor child node and a receiving interval of the first one of the nodes.
13. The method of claim 12 , comprising repeating the steps of scheduling the downlink transmissions and scheduling the uplink transmissions sequentially for each of the nodes within the mesh network until all of the selected traffic has been scheduled.
14. A method of communicating in a mesh network having a root node and a plurality of child nodes associated with the root node, comprising:
scheduling a selected amount of traffic in the mesh network using a linear program that minimizes a time for the selected amount of traffic to reach its intended destination subject to a plurality of constraints that ensure that the selected amount of traffic will reach its intended destination within the minimized time, wherein the plurality of constraints comprises
a first constraint requiring that all transmissions from at least one of the plurality of child nodes to the root node will reach the root node within the minimized time, wherein the first constraint requires that all uplink traffic via the at least one child node must be transmitted to the at least one child node from an originating child node of the at least one child node before the (K+1−h)th frame, where K is the total number of frames in the minimized time and h is the number of hops between the at least one child node and the root node;
a second constraint requiring that all transmissions from the root node to the at least one child node reach the at least one child node within the minimized time;
a third constraint requiring that a total amount of traffic to and from each of the nodes does not exceed a corresponding capacity of each of the nodes;
a fourth constraint requiring that the total uplink traffic transmitted by each of the plurality of child nodes during the minimized time is no greater than any uplink traffic received by one of the child nodes from any other of the plurality of child nodes during the minimized time and any uplink traffic originated by the one child node during the minimized time;
a fifth constraint that requires that a total downlink traffic at each of the child nodes during the minimized time be no greater than any downlink traffic received by each child node from a neighbor parent node;
a sixth constraint that requires that a child node that has not received any downlink traffic from at least one parent node transmits no downlink traffic during the minimum time; and
transmitting the selected amount of traffic.
15. The method of claim 14 , wherein the plurality of constraints comprises
a seventh constraint that requires that the root node has no uplink traffic.
16. The method of claim 14 , wherein the number of hops corresponds to a number of nodes between the at least one child node and the root node through which the root node and the at least one child node communicate with each other.
17. The method of claim 14 , wherein the first constraint requires that all uplink traffic from the at least one child node to the root node be transmitted before the (K+2−h)th frame, where K is the total number of frames in the minimized time and h is the number of hops between the at least one child node and the root node.