Robust scheduling mechanm for efficient band-width usage in muliticell wireless local networks
First Claim
1. A method of dynamically managing wireless communications in a wireless communications network comprised of a local area network connected to a plurality of nodes defined as base stations, each of which has a geographic area, defined as a cell, within which mobile stations can communicate with a node, with at least two of the cells overlapping with one another, with each such node being capable of performing bidirectional wireless communication with one or more of said mobile stations under control of a controller, said method comprising the steps of:
- 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;
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;
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
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.
1 Assignment
0 Petitions
Accused Products
Abstract
A wireless communications network includes a local area network connected to a plurality of nodes which perform bidirectional wireless communication with mobile stations as controlled by a controller. Each node has a geographic area, termed a cell, within which mobile stations can communicate with the node associated with the cell. A cell interference graph is read into the controller, and a maximal independent set of nodes is determined. Each node in the maximal independent set of nodes is put in a set termed ACTIVE for performing wireless communication with mobile stations in their respective cells. Nodes which are not in the maximal independent set of nodes is put in a set termed WAITING to wait for permission to enter the set ACTIVE. A node in the set ACTIVE which has completed communications sends a completion signal to the controller. The controller then examines which of the nodes in the set WAITING is not adjacent to another node in the set ACTIVE, and such nodes are entered in a set termed CANDIDATES. Nodes in the set CANDIDATES are moved to the set ACTIVE according to a predetermined criteria.
53 Citations
8 Claims
-
1. A method of dynamically managing wireless communications in a wireless communications network comprised of a local area network connected to a plurality of nodes defined as base stations, each of which has a geographic area, defined as a cell, within which mobile stations can communicate with a node, with at least two of the cells overlapping with one another, with each such node being capable of performing bidirectional wireless communication with one or more of said mobile stations under control of a controller, said method comprising the steps of:
-
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; 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; 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 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. - View Dependent Claims (2, 3, 4)
-
-
5. 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. - View Dependent Claims (6, 7, 8)
-
Specification