Multipoint relay set selection methods and their application to multicast channel reservation in overlapping basic service sets in wireless networks

1. A method, said method comprising:

communicating with neighbor nodes in a wireless network;

first determining one-hop neighbor nodes and two-hop neighbor nodes responsive to said communication;

second determining a minimum multipoint relay set responsive to said first determination, wherein said second determination further comprises forming a matrix using said one-hop neighbor nodes and said two-hop neighbor nodes, forming an optimization problem responsive to said matrix, solving said optimization problem or forming a graph using said one-hop neighbor nodes and said two-hop neighbor nodes, initializing said minimum multipoint relay set, initializing a list of all elements of said two-hop neighbor nodes, third determining a node in a set of said two-hop neighbor nodes that has a lowest degree, fourth determining a node in a set of said one-hop neighbor nodes that is a neighbor of said node in said set of two-hop nodes and that has a greatest degree and marking all nodes in said set of two-hop neighbor nodes that are neighbors of said determined one-hop neighbor node; and

communicating over said wireless network using said minimum multipoint relay set, wherein said communicating act further comprises receiving, by an access point, a beacon report from nodes associated with said access point, and wherein said access point is a special purpose node, fifth determining, by said access point, two-hop neighbor access points responsive to said received beacon report, multicasting, by said access point, a request-to-send message and receiving, by said access point, a clear-to-send message responsive to said request-to-send message, and wherein said request-to-send message includes a bitmap control and a partial virtual bitmap of nodes of said minimum multipoint relay set from which a response to said request-to-send message is requested.

2. The method according to claim l, wherein said graph is a bipartite graph.

3. The method according to claim 1 , wherein said clear-to-send message is received in an order specified in said bitmap control and said partial virtual bitmap.

4. The method according to claim 1 , further comprising:

sixth determining if all nodes from which said response to said request-to-send message was requested have responded; and

transmitting data responsive to said sixth determination.

5. An apparatus, comprising:

means for communicating with neighbor nodes in a wireless network;

first means for determining one-hop neighbor nodes and two-hop neighbor nodes responsive to said communication;

second means for determining a minimum multipoint relay set responsive to said first determination, wherein said second means for determining further comprises forming a matrix using said one-hop neighbor nodes and said two-hop neighbor nodes, means for forming an optimization problem responsive to said matrix, means for solving said optimization problem or means for forming a graph using said one-hop neighbor nodes and said two-hop neighbor nodes, means for initializing said minimum multipoint relay set, measn for initializing a list of all elements of said two-hop neighbor nodes, third means for determining a node in a set of said two-hop neighbor nodes that has a lowest degree, fourth means for determining a node in a set of said one-hop neighbor nodes that is a neighbor of said node in said set of two-hop nodes and that has a greatest degree and marking all nodes in said set of two-hop neighbor nodes that are neighbors of said determined one-hop neighbor node; and

means for communicating over said wireless network using said minimum multipoint relay setset, wherein said means for communicating further comprises means for receiving, by an access point, a beacon report from nodes associated with said access point, and wherein said access point is a special purpose node, fifth means for determining, by said access point, two-hop neighbor access points responsive to said received beacon report, measn for multicasting, by said access point, a request-to-send message and means for receiving, by said access point, a clear-to-send message responsive to said request-to-send message, and wherein said request-to-send message includes a bitmap control and a partial virtual bitmap of nodes of said minimum multipoint relay set from which a response to said request-to-send message is requested.

6. The apparatus according to claim 5 , wherein said graph is a bipartite graph.

7. The apparatus according to claim 5 , wherein said clear-to-send message is received in an order specified in said bitmap control and said partial virtual bitmap.

8. The apparatus according to claim 5 , further comprising:

sixth means for determining if all nodes from which said response to said request-to-send message was requested have responded; and

means for transmitting data responsive to said sixth means for determining.