ices. When the weight of each vertex is set to be equal to the sum data rate of users scheduled in the specific round, the sum of the weight of all vertices in an independent set equals to the sum data rate of a possible user schedule. The maximum weight independent set then corresponds to the schedule pattern that maximizes the sum data rate. The maximum weight independent set problem involves searching for all possible independent sets and then finding the maximum weight one. Thus a critical step is to construct the scheduling graph in order to find all the scheduling patterns. 9.5.1 Scheduling Graph Construction Let S be the set that includes all the possible scheduling patterns for all the devices and rounds. S E S is a possible schedule. The scheduling graph can be constructed as follows. First, we need to generate vertices. In this graph, a vertex indicates that devices j1,j2, ,jK are scheduled at time t. There are a total of (M) vertices. When creating the edges, the following constraints need to be satisfied. C1: Each device can be scheduled at most once. C2: At most K devices can be scheduled in one round. For two vertices and if = {1, K} (violates C1) or ti=tj (violates C2), Vi and Vj are connected and an edge exists between these two vertices. Then when we select vertices from independent set, Round 1 Round 2 Round T UE u1 UE U2 Figure 9.2 Scheduling diagram. 9.5 Scheduling Algorithm and Power Allocation Figure 9.3 A scheduling graph example. both C1 and C2 will be satisfied. Let us construct a scheduling graph example with M = 4, K = 1, and T = 2, as shown in Figure 9.3. In this case there are (i) x2 = 8 vertices. From this figure, we can find out that the possible independent sets for vertex (1)1 (green node) are {{(1)1, (2)2}, {(1)1, (3)2}, {(1)1,(4)2}}. Similarly, we can find all the independent sets for each vertex in the graph. Because of the edge connection constraints, each independent set has at most T vertices. Since the FL rounds are continuous and the number of FL rounds is T, the independe