Multicast scheduling systems and methods for leveraging cooperation gains in relay networks

Abstract

Methods and systems for transmitting multicast data in a wireless relay network are described. A tradeoff between the benefits of relay cooperation and session multiplexing can be addressed through careful association of relay stations for resource allocation purposes to maximize the total system throughput. In addition, various complex and greedy scheduling procedures that are based on the distributed pet mutation model and the contiguous permutation model are also described.

What is claimed is: 
     
       1. A method for transmitting multicast data on a wireless relay network comprising:
 associating relay stations into different subsets such that relay stations within a subset employ a cooperation mechanism to transmit multicast data on common transmission resources and employ a resource reuse mechanism to transmit the multicast data independently with respect to relay stations in other subsets; 
 determining a schedule to allocate transmission resources to each subset and thereby implement the cooperation and resource reuse mechanisms; and 
 transmitting the multicast data to users in accordance with the schedule; 
 wherein the determining a schedule further comprises solving a scheduling problem formulated to maximize an aggregate flow for a plurality of multicast sessions 
 wherein the determining a schedule further comprises solving the linear program (LP) relaxation of the scheduling problem in accordance with a contiguous permutation model to obtain a fractional channel allocation to each session of each subset; 
 wherein the determining a schedule further comprises 
 performing integral channel allocation for each subset; 
 determining, for each subset, the loss of flow resulting from the integral channel allocation with respect to the solution of the LP relaxation; 
 selecting and implementing the integral channel allocation for the subset yielding the lowest loss of flow; and 
 updating the maximum flow limit for each session of the selected subset based on the implemented integral channel allocation. 
 
     
     
       2. The method of  claim 1 , wherein the associating further comprises determining, at each given relay station, a set of neighboring relay stations that cause interference exceeding a threshold for users served by the given relay station. 
     
     
       3. The method of  claim 2 , wherein the associating further comprises transmitting training symbols from each relay station and receiving interference power measurements from users served by the given relay station to determine whether the interference exceeds the threshold. 
     
     
       4. The method of  claim 3 , wherein the associating further comprises selecting relay stations for inclusion into subsets by representing relay stations as vertices in a graph, linking relay stations with corresponding neighboring relay stations causing interference exceeding the threshold and defining subsets as disjoint components of the graph. 
     
     
       5. The method of  claim 1 , wherein the performing channel allocation for each subset further comprises successively selecting a session and channel pair, for assignment in the subset, that yields the largest flow such that a maximum flow limit for any corresponding session is not exceeded. 
     
     
       6. The method of  claim 1 , wherein the subsets are relay station subsets and wherein the performing channel allocation for each relay station subset further comprises:
 solving the LP relaxation of a channel allocation problem, for each relay station subset, that is formulated to maximize a flow for a given session in a corresponding relay station subset to obtain a fractional channel allocation of at least one channel subset to the given session in the corresponding relay station subset; 
 assigning a particular channel subset, obtained from the fractional channel allocation of at least one channel subset, to each session in the corresponding relay station subset; 
 for each particular channel that belongs to multiple channel subsets that are assigned to different sessions, assign the particular channel to the session that yields the largest flow with the particular channel such that a maximum flow limit for any corresponding session is not exceeded; and 
 updating the maximum flow limit for each session based on the particular channel assignments. 
 
     
     
       7. The method of  claim 1 , wherein the performing integral channel allocation, the determining the loss of flow, the selecting and implementing the integral channel allocation and the updating are repeated until integral channel allocations for all subsets are implemented. 
     
     
       8. A wireless relay network system comprising:
 a set of relay stations that are associated into different subsets such that relay stations within a subset employ a cooperation mechanism to transmit multicast data on common transmission resources and employ a resource reuse mechanism to transmit the multicast data independently with respect to relay stations in other subsets; and 
 a base station configured to determine a schedule to allocate transmission resources to each subset and thereby implement the cooperation and resource reuse mechanisms, wherein the relay stations are configured to relay multicast data for transmission to a plurality of users in accordance with the schedule; 
 wherein the base station is further configured to determine the schedule by solving a scheduling problem formulated to maximize an aggregate flow for a plurality of multicast sessions; 
 wherein the scheduling problem is based on a distributed permutation model and wherein the base station is further configured to determine the schedule by solving the linear program (LP) relaxation of the problem to obtain a fractional channel allocation to each session of each subset; 
 wherein the base station is further configured to determine the schedule by: 
 performing integral channel allocation for each subset by successively assigning a channel to a session, in the subset, that yields the largest flow such that a maximum flow limit for any corresponding session is not exceeded; 
 determining, for each subset, the loss of flow resulting from the integral channel allocation with respect to the solution of the LP relaxation; 
 selecting and implementing the integral channel allocation for the subset yielding the lowest loss of flow; and 
 updating the maximum flow limit for each session of the selected subset based on the implemented integral channel allocation. 
 
     
     
       9. The system of  claim 8 , wherein the base station is further configured to perform the integral channel allocation, determine the loss of flow, select and implement the integral channel allocation and update the maximum flow limit repeatedly until integral channel allocations for all subsets are implemented. 
     
     
       10. The system of  claim 8 , the base station is further configured to determine the schedule by allocating a channel to a session that yields the largest bottleneck flow among the subsets. 
     
     
       11. The system of  claim 10 , wherein the base station is further configured to determine the schedule by allocating the channel to a session that yields the largest bottleneck flow in subsets in which the session lacks resources that are in fractional excess with respect to a unit of the corresponding bottleneck flow. 
     
     
       12. The system of  claim 11 , wherein the scheduling problem is based on a contiguous permutation model and the base station is further configured to determine the schedule by selecting a channel having the highest gain among unallocated channels in a corresponding subset as the allocated channel. 
     
     
       13. The system of  claim 10 , wherein the base station is further configured to determine the schedule by updating a first variable denoting any resources that are in fractional excess with respect to a corresponding bottleneck flow for the corresponding session and subset to which a channel is allocated and updating a second variable denoting channels that are available for allocation. 
     
     
       14. The system of  claim 13 , wherein the base station is further configured to determine the schedule by successively and repeatedly allocating a channel and updating the variables until no session on any subset can accommodate a unit of a corresponding bottleneck flow with an additional channel allocation.