Robust scheduling mechanm for efficient band-width usage in muliticell wireless local networks

Claim 3

The method of claim 1, including the steps of: sending a completion signal to said controller from a given one of said nodes in an ACTIVE state when it has completed wireless communications; examining which neighbor nodes, of said given one of said nodes, which are in said set WAITING and are not adjacent to another active node, with such nodes being put in a set termed CANDIDATES; and examining and reordering which nodes in said set CANDIDATE can be moved into the set ACTIVE according to a predetermined criteria.

Claim 4

The method of claim 2, including the step of: moving a first one of the examined and reordered nodes from said set CANDIDATE into said set ACTIVE for performing wireless communication with mobile stations in its cell.

Claim 5

The method of claim 3, including the step of: removing from said set CANDIDATE any node that is adjacent to said first one of said nodes just put in said set ACTIVE.

Claim 6

In a wireless communications network, the combination comprising: a local area network; a plurality of nodes connected to said local area network, each of which has a geographic area called a cell within which mobile stations can perform communications with a node, with at least two of the cells overlapping with one another; a plurality of said mobile stations which can perform communications with nodes whose cells the mobile stations are occupying; a controller which controls communications between said plurality of nodes and said plurality of mobile stations, said controller including: means for reading a cell interference graph G=(V, E) into said controller, where V is the plurality of nodes and E is the set of all adjacent nodes; means for determining a maximal independent set of the nodes V, where a set of nodes in G is independent if no pair of nodes in the set is adjacent in the graph, and is maximally independent if the addition of another node in the set will make the set not independent; means for activating said maximal independent set of nodes for performing wireless communication with mobile stations in their respective cells, with said maximal set of nodes being in a set termed ACTIVE; and means for putting nodes which are not in said maximal independent set of nodes in a set termed WAITING to wait for permission to enter the set ACTIVE.

Claim 7

In a wireless communications network, the combination comprising: a local area network; a plurality of nodes connected to said local area network, each of which has a geographic area called a cell within which mobile stations can perform communications with a node, with at least two of the cells overlapping with one another; a plurality of said mobile stations which can perform communications with nodes whose cells the mobile stations are occupying; a controller which controls communications between said plurality of nodes and said plurality of mobile stations, said controller including: means for reading a cell interference graph G=(V, E) into said controller, where V is the plurality of nodes and E is the set of all adjacent nodes; means for determining a maximal independent set of the nodes V, where a set of nodes in G is independent if no pair of nodes in the set is adjacent in the graph, and is maximally independent if the addition of another node in the set will make the set not independent; means for activating said maximal independent set of nodes for performing wireless communication with mobile stations in their respective cells, with said maximal set of nodes being in a set termed ACTIVE; and means for putting nodes which are not in said maximal independent set of nodes in a set termed WAITING to wait for permission to enter the set ACTIVE.

Claim 8

The combination claimed in claim 5, including: means for sending a completion signal to said controller from a given one of said nodes in an ACTIVE state when it has completed wireless communications; means for examining which neighbor nodes, of said given one of said nodes, which are in said set WAITING and are not adjacent to another active node, with such nodes being put in a set termed CANDIDATES; and means for examining and reordering which nodes in said set CANDIDATE can be moved into the set ACTIVE according to a predetermined criteria.

Claim 9

The combination claimed in claim 6, including: means for moving a first one of the examined and reordered nodes from said set CANDIDATE into said set ACTIVE for performing wireless communication with mobile stations in its cell.

Claim 10

The combination claimed in claim 7, including: means for removing from said set CANDIDATE any node that is adjacent to said first one of said nodes just put in said set ACTIVE.