Abstract
We consider a cellular wireless network. Our aim is to develop adaptivepower scheduling algorithms that enable area base stations to coordinate, on a timedivision basis, the transmission of multicast packets to identified client nodes, for scenarios under which a prescribed code rate is employed. Such mechanisms can be implemented by 4G long term evolution (LTE) systems using multimedia broadcast multicast services (MBMS), meshed WiFi networks, or mobile backbone based ad hoc wireless networks. We show that the joint scheduling and power control problem can be represented as a mixedinteger linear programming model, which is NPhard. Consequently, we present three heuristic algorithms of polynomial complexity for solving the problem in a practical manner. For small network layouts, our centralized heuristic algorithm is shown to achieve a throughput rate performance that is close to that attained by the optimal scheme. All three of our heuristic algorithms are shown to yield excellent throughput rate performance behavior. The use of power adaptations, when compared with fixed transmit power operations, leads to enhanced throughput rate performance while also lowering communications energy consumption levels. Comparisons with LTE MBMS over single frequency network based schemes have shown our algorithms to offer enhanced spectral efficiency performance, while providing high client coverage.
Keywords:
Long term evolution; Multimedia broadcast/multicast services; Multicast; Scheduling; Power control; Spectral efficiencyIntroduction
Efficient multicasting of messages in multimedia cellular networks to identified multicast group clients is a task of primary importance. Consider a wireless cellular network that consists of base stations that are interconnected through a backbone network, such as a long term evolution (LTE) system as shown in Figure 1. Messages targeted for multicast distribution are delivered across the backbone by content providers to base stations with clients that belong to the underlying multicast group. In this article, we study the coordinated adaptivepower scheduling of transmissions of such multicast packets by area base stations. The developed schemes are used by neighboring base stations to timeshare their downlink channels over a prescribed frequency band. For application to LTE systems, such an operation is supported by the multimedia broadcast and multicast service (MBMS) [1,2]. Our scheduling schemes are also highly effective when applied to meshed WiFi networks, or to mobile backbone based ad hoc wireless networks, whereby the roles of base stations are undertaken by access points or backbone nodes, respectively.
Figure 1 . Illustrative cellular system managed by backbone base stations.
Under LTE MBMS, neighboring base stations may engage in coordinated timesynchronized pointtomultipoint transmissions. Client nodes may realize macrodiversity gains through selective combining or soft combining [2,3]. Under a selective combining scheme used by MBMS over single frequency network (MBSFN), multiple MBMS group base stations may be scheduled to transmit the same message at the same time, at the same rate, using the same modulation/coding scheme (MCS), to produce MIMOtype gains at receiving client nodes. Such an MBSFN operation requires strict symbol synchronization among base stations, thus imposing spatial configurational limitations, and increasing implementational complexity and costs [2,4,5]. In addition to combining operations, coordinated scheduling operations can also be performed across neighboring cells to manage intercell interference [6,7].
In avoiding the use of such combining operations, the scheduling mechanisms developed in this article ensure each multicast transmission to be successfully received by all identified client nodes at targeted error rates, and thus at acceptable signaltointerferenceandnoise ratio (SINR) levels. Using the algorithms developed in this article over LTE MBMS implementations, pointtomultipoint transmissions can be carried out by base stations, in a timecoordinated fashion, across shared OFDMbased downlink channels, rather than using the MBSFN downlink structure. Such an implementation offers the following advantages: (i) different cells may contain different mixes of multicast client groupings. Thus, a base station that does not have clients that belong to a certain multicast group would not be configured to multicast (at the same time slot) packets that belong to this group for the sole purpose of achieving combining gains at client nodes of nearby base stations. This reduces energy consumption and increases spectral utilization efficiency; (ii) client nodes are not required to engage in MIMOtype (multipath combining oriented) operations, enabling the efficient operation of smaller user equipment, such as sensors and handheld smart phone platforms. A wide range of schemes have been proposed to find the optimal link scheduling with power control for unicasting in spatialTDMA networks [810]. Adaptive power control has been utilized by energyaware multicasting schemes to synthesize a multicast structure that minimizes the total energy cost [11,12]. However, to the best of our knowledge, we have found no published articles that solve the scheduling problem jointly with adaptive power control for multicasting in wireless cellular networks, under which base stations share their downlink channels on a coordinated spatialTDMA basis.
The objective of this article is to develop efficient algorithms for such an operation and investigate the extent of throughput enhancement that can be feasibly attained. We first model the problem as a mixedinteger linear programming problem to find an optimal solution, and conclude that the problem is NPhard. We then present three computationally efficient heuristic algorithms that jointly determine the multicast schedule, the underlying base station transmit power levels and the set of client nodes that are addressed by each transmitting base station in each time slot. Consequently, a scheduled base station can make effective use of its allocated time slots to successfully transmit any mix of unicast and multicast packets. For scheduling unicast traffic, time slots allocated to a base station do not need to be renegotiated and reconfigured (hence reducing the ensuing rate of control traffic) as long as its mobile client nodes continue to reside in the geographical region that is targeted for coverage during the allocated time period. The presented algorithms can be readily extended to operations under which base stations use sectorized antennas. Each scheduled downlink transmission is then targeted to cover a sector zone, rather than a diskshaped geographical region.
The article is organized as follows. The system model is presented in Section “System model”. In Section “MILP model”, we model the joint scheduling and power control problem as a mixed integer linear program (MILP). We present our heuristic algorithms in Section “Heuristics algorithms for joint power control and multicast scheduling”. In Section “Simulation results”, we study the performance of the system under our heuristic algorithms, as well as compare with that exhibited under the optimal solution. We also assess the spectral efficiency of our schemes in comparison with the corresponding performance behavior of illustrative LTE MBSFN systems. Conclusions and future works are presented in Section “Conclusions”.
System model
We consider a cellular wireless network that consists of base stations with omnidirectional antennas. Client nodes located in a cell region communicate through the base station with which they associate. We assume that the transmissions of multicast packets are scheduled over a prescribed frequency band, using a fixed transmit rate achieved under a prescribed MCS. Neighboring base stations are timeslot synchronized. They share their downlink channels on a coordinated spatialTDMA basis. The timeslot duration is assumed to be equal to the transmission time of a prescribed load of packets, incorporating a sufficiently long preamble that compensates for incurred propagation delays.
Under our centralized algorithm, a scheduling controller is used to allocate time slots to base stations for the transmission of multicast messages. The controller periodically collects channel quality information (CQI) from client nodes, and uses the data to form a channel gain matrix for each downlink channel. The CQI collection mechanism is part of the LTE infrastructure, and is included in the control plane [13]. We assume here that such updates are executed at a sufficiently fast pace to be of relevance for the time period over which the underlying slot allocation operation is performed. During this period of time, we assume the locations of client nodes and the corresponding downlink transmission gain values to be essentially static. Base station i is capable of adjusting its transmit power continuously in a given range [0, , in a slotbyslot fashion. For the special case in which all base stations are limited by the same maximum power level, we denote the latter as . Further adaptations can be carried out through the dynamic setting of the MCS and its ensuing code rate to attain performance upgrade; however, the purpose in this article is to determine the contributions made by the sole use of transmit power adaptations on the performance behavior of multicast scheduling mechanisms. Moreover, the setting of the data rate (based on the MCS configuration) in the multicasting scenario is dictated by constrains imposed by the critical client nodes of a multicast transmission, i.e. the most interferenceprone client nodes within the multicast group.
Client nodes are initially associated with one of the base stations in the underlying network by selecting the one from which they receive a control signal at the highest power level. As the scheduling operation progresses, when a base station is selected for transmission at a given time slot, the boundary clients of the base station’s neighboring cells may be able to receive multicast packets from the selected base station (depending on surrounding interferences and the SINR requirements at the client nodes). These boundary clients are then scheduled to receive the underlying multicast packets from such a base station, and are then ‘removed’ as multicast clients of their respective initialassociated base stations. We identify such an assignment as a multicast relinking (mlinking) operation. The performance improvement under the mlinking process is thus related to the increase in the geographical coverage span that is attained (so that in the underlying time slot, additional client nodes, the relinked ones, are also accommodated), and the consequent reduction in coverage scope that may be required of residual base stations.
For a unicast transmission scenario, a directed communication link l_{ij} is established from node i to node j if there exists a power level , under which the SNR level measured at the receiver of node j exceeds a prescribed threshold level γ(j); i.e.,
where G_{ij}denotes the propagation gain incurred during the transmission, and η is the thermal noise power monitored at node j (which, without loss of generality, is assumed to be the same for all nodes). Such a model is often identified as the SINRbased interference model [14]. The value of the threshold γ(j) depends on the prescribed block link error rate (BLER), MCS and ensuing data rate (or spectral efficiency) used by node j[15]. We henceforth assume in this article that a specific MCS is employed, so that under a prescribed BLER level for the link terminating at receiver j, the corresponding minimum acceptable SINR level is denoted as γ(j). To simplify our algorithmic schemes, we further assume here that γ(j) = γ for each node j. Consequently, each scheduled base station will transmit its packets in its allocated slots at a prescribed data rate.
For a multicasting scenario, let N^{Tx}represents the set of base stations with multicast messages to distribute and N^{Rx}denotes the set of client nodes interested in the underlying multicast packets. Let G= represents the propagation gain matrix and denotes the subset of client nodes that is associated with base station i_{k}(BSi_{k}). Let and , represent a multicast transmission by BSi_{k}that reaches the entire group of multicast client associated with this base station, and the corresponding transmit power level in time slot t, respectively. For a transmission scenario at time slot t to be feasible under the power vector , a transmission by BSi_{k}must be received at each of its client node with an SINR level that is higher than a prescribed threshold. Hence, for each BSi_{k}, considering all the multicast client nodes that are currently linked with it, we require:
Fact 1: The power vector that satisfies the system of linear inequalities in Equation (2) in its equality form, when it exists, is referred to as the apex solution. If S(t) is a feasible transmission scenario under , then any other power vector under which S(t) is feasible would require at least as much power (i.e., componentwise). Based on Perron–Frobenious theorem [16,17], it is shown that if a transmission scenario S(t) is feasible, the apex solution of the corresponding system of linear inequalities is strongly Pareto optimal with respect to S(t). Thus, this is an energy efficient solution; the apex point yields a solution that employs the lowest power level for each base station.
The number of multicast packets per frame required to be transmitted by base stations with multicast messages to distribute is assigned by the upper layer operations and is determined by the statistics of total offered load and the desired delaythroughput performance metrics. These calculations produce the requirement of packets to be multicasted per frame for every BSi_{k}, where . Using adaptive power control jointly with scheduling, we aim to design a time frame with the shortest schedule length to reach all of the respective multicast clients. The solution specifies the schedule, identifying in each time slot the set of transmitting base stations, their transmit power levels and the set of client nodes that each base station aims to reach. We also strive, as a secondary consideration, to employ a power efficient solution.
MILP model
In this section, we develop and investigate a MILP formulation for the joint adaptivepower multicast scheduling problem. We assume that the initial associations between clients and their base stations are determined based on a prescribed routine, such as that noted above, under which a client associates with the base station whose signal is received at the highest power level. The input for the optimization model is the set of designated base stations with multicast messages to distribute (N^{Tx}), the sets of multicast clients with their associated BSi_{k}(, ), the traffic matrix, the propagation gain matrix (G), maximum transmit power of each BSi_{k}(), minimum required received SINR (γ(j_{k})), and thermal noise power levels impacting the receivers of client nodes (η). To determine the system’s throughput capacity level attainable under the employed scheduling scheme, we assume the allocated multicasting period to include a sufficient number of time slots to accommodate the multicast load targeted for this period, so that the required time frame duration is upper bounded by a finite duration . The decision variables for the optimization algorithm are {} and {}, where the binary variable is defined as:
The solution of the scheduling problem is represented as ( X ,P). The set of quadratic constraint:
where Φ is a sufficiently large positive number, imposes the SINR requirement for a base station multicast transmission at time slot t. Note that if no transmission by BSi_{k} is scheduled to take place at time slot t (), the associated constraint becomes redundant. We next show that this scheduling problem can be modeled as the following MILP formulation:
In Equation (5), ε is a sufficiently small positive number, and c_{t}is a positive constants defined as
It can be seen that the constraints expressed by Equation (6) guarantee that a multicast transmission by BSi_{k}will reach all the multicast clients under its management. The coefficients {c_{t}} are used to ensure that the length of the schedule corresponding to the optimal solution of the MILP formulation is minimal, whereas the positivity of εensures the strongly Pareto optimality of the optimal transmit power levels deduced from the optimum solution of the MILP formulation.
Lemma 1
Every MILP solution yields a feasible transmission scenario at each time slot.
Proof
Consider an arbitrary time slot t under a feasible solution ( X ,P) of the MILP formulation, where and . Assume that . We claim that transmission scenario S(t), when driven by power vector , is feasible. For a transmission in S(t), since , based on Equation (6), we have:
resulting in
which along with the transmit power constraint in Equation (7) confirms the feasibility of each transmission in S(t). Consequently, transmission scenario S(t) is feasible under power vector . QED □
The joint power control and scheduling problem for unicast transmissions, as presented in [9], can be reduced to an edge coloring problem, which is NPhard [18]. Adding in the multicast nature of our problem, which induces further complexity since a single base station transmission has to satisfy the minimum SINR requirement imposed for each one of its multicast clients, implies that the underlying scheduling problem is also NPhard. We therefore conclude the need for developing heuristic algorithms to provide solution schemes to this adaptivepower scheduling problem that is computationally efficient and scalable, when considering networks that may include a large number of base stations and client nodes.
Heuristics algorithms for joint power control and multicast scheduling
We first introduce the notion of a power control multicast interference graph [9], which is used as the basic building block for our heuristic Algorithm 1. Consider a scenario with only two base stations, BSi_{1} and BSi_{2}, with corresponding sets of multicast clients and . The transmission scenario is feasible if and only if the coordinates of the apex power vector solution of the following linear inequalities are in the range :
To reduce the computational complexity of Equation (13), we employ an approximation technique. Instead of inspecting the SINR condition for all multicast clients at each base station, we consider for each pair of such base stations a pair of critical client nodes, one such node in each cell. Client nodes monitor their received interference power levels and report them to their base stations periodically via CQI updates. By using CQI data collected by the base stations (or centralize scheduling controller), critical client nodes are then identified to be those nodes that are measured to experience the most interference (relative to the interference signals that are generated). We denote these critical nodes for BSi_{1} and BSi_{2} as and , respectively. Assume transmissions and are the only two active transmissions in the network. The conditions stated in Equation (13) are simplified to yield:
under a power vector . Thus, the approximation in Equation (14) reduces the complexity of finding the apex power vector solution by considering all the multicast nodes between the two base stations under consideration to only the two critical nodes (one for each of the base station). This approximation is used in all of our numerical computations and simulations.
The multicast interference graph is defined as an undirected graph U = (V , E) whose sets of vertices V and set of edges E are defined as follows. A vertex v_{k} in graph V represents a candidate multicast transmission from BSi_{k} to its set of associated client nodes. Vertices v_{1}and v_{2} in V are connected to each other by an edge (which thus becomes an element of E) if and only if multicast transmissions by BSi_{1}and BSi_{2}cannot be executed simultaneously during the same time slot, i.e., there is no feasible transmit power vector . The latter is established by using Equation (14).
Centralized Algorithm 1: interference graph multicast scheduling
Based on the constructed multicast interference graph, we introduce in this section a centralized heuristic algorithm that solves the problem in a polynomial efficient manner. It is an iterative scheme that consists of the following steps.
(1) Every client node initially associates with a single base station based on the highest received power level.
(2) We construct a multicast interference graph U = (V, E) by considering only those base stations that have outstanding multicast packets to be scheduled, with each vertex representing a multicast transmission by a base station to its presently determined clients.
(3) A maximum weight independent set of vertices of the multicast interference graph is selected. We set the weight of vertex v,w(v)=h(v)/(dU(v) + 1) where h(v) denotes the density of the (as yet uncovered) client nodes of multicast transmission v, expressing the number of such mobile stations per unit area that are designated to receive multicast packet transmission from base station v, whereas dU(v) is the degree of vertex v in the graph U. An efficient greedy heuristic algorithm [19] is employed to obtain a maximal weighted independence set (i.e., transmission scenario) for the interference graph. In each iteration of the algorithm, one vertex is selected from the graph for inclusion into the weighted independent set. Vertex v is selected if it has the highest weight: 15h(v)(dU(v)+1)=maxu∈V(U)h(u)(dU(u)+1).Then, the selected vertex and all its neighbors are removed from the graph. Since nodal degree is indicative of the level of interference imposed by a multicast transmission, the use of this weight function leads to the selection of the next transmission that covers a large number of client nodes (per covered area) while attempting to limit the level of interference that it may cause.
(4) The resulting maximal independent set defines a provisional set of transmissions to be scheduled at this time slot. By definition of the interference graph, every subset of a maximal independent set with cardinality of two is a feasible transmission scenario. However, considering the accumulative effect of interferences, the entire maximal independent set does not necessarily form a feasible transmission scenario. The algorithm verifies the feasibility of the derived maximal independent set by checking the SINR level measured at each scheduled client node. For this purpose, we solve the set of linear equations that correspond to the set of Equation (2) in its equality form, where candidate transmissions are members of the selected independent set. If this set is feasible, there exists a Pareto optimal solution, and the resulting power vector is used to set the transmit power levels of each scheduled base station in the independent set. If no such solution can be obtained, the selected independent set is determined to not be feasible, and we proceed with a pruning process by first removing the vertex that causes the most interference to other vertices in the graph [20]. The pruning procedure is repeated until the resulting transmission scenario is determined to be feasible.
(5) The feasible transmission scenario generated from the previous pruning process is not necessarily maximal with respect to the underlying residual interference graph. To assure its maximality, we iteratively consider other remaining transmissions for possible addition to the currently selected feasible transmission set (see [9, 20] for details).
(6) For each vertex selected as a member of the independent set, if the mlinking process is invoked, we determine if there are additional client nodes that can be covered by the multicast transmissions executed by the corresponding scheduled base station. If so, the identified client nodes are now directed to receive multicast transmissions issued by this base station. Subsequently, the weights of vertices in the current residual interference graph are updated, taking these mlinking actions into account. This concludes the scheduling for the current time slot.
(7) If there are still base stations with outstanding multicast packets, a new residual interference graph is formed by removing the vertices that have already been scheduled and have no more outstanding packets to be multicasted. The scheduling for such residual base stations proceeds to the next time slot by repeating steps 3–6 over the residual graph. This process is terminated when the multicast load of all the base stations are scheduled.
Centralized Algorithm 2: maximal simultaneous multicast transmissions
In this section, we introduce our second centralized heuristic algorithm. For each timeslot t, the algorithm constructs a feasible transmission set by iteratively scheduling additional multicast transmissions until no more such transmissions can be included. In each iteration, the algorithm attaches a weight metric β to every base station that has transmissions that are yet to be scheduled. The base station with the current highest β value is then evaluated. It is added to the set of base stations scheduled for transmission in this time slot if the newly expanded schedule is determined to be feasible. Otherwise, the base station with the next highest β value is considered. Base stations with outstanding multicast packets to be scheduled will remain on the residual base station list (set of base stations that are yet to be scheduled). Clearly, a fairness oriented or priority based mechanism can be readily incorporated to manage the order at which multicast transmission requests are queued at the scheduler, when the capacity (or time period) allocated for multicasting purposes is limited. Such considerations are not included in this article. The iteration process for time slot t is terminated when no additional base stations can be appended. Subsequently, the scheduling process continues in the same fashion at the next time slot.
The weight metric β(i), calculated by BSi is defined as , where ratio(i) is the number of clients associated with the examined BSi, divided by the total number of clients that are associated with all residual base stations. We set , when determined to be nonnegative, to represent the current power margin level at BSi. It is defined as – , where represents the maximal transmit power that can be used by BSi while yielding a currently feasible operation; i.e., without degrading the received SINR values incurred at already scheduled client nodes to levels that are lower than their acceptable SINR levels. The parameter denotes the minimal transmit power that BSi must utilize to reach its targetted client nodes at acceptable SINR levels. Each base station uses CQI data that it periodically receives from its client nodes to calculate the gain matrices for its associated downlink channels and to compute the interference power margins available at its critical client nodes. Base stations exchange such information, or pass it to the central scheduling controller, as well as identify the locations of their critical client nodes (so that the channel gains for transmissions from a base station to critical nodes in neighboring cells can be estimated). The controller, and possibly also each base station, is then able to compute the above mentioned three key parameters and derive its weight metric.
In motivating the setting of the βweight metric, we note the following. In selecting the next multicast transmission to add to the schedule, we provide preference to base stations that serve a higher number of clients. We also prefer to select base stations that exhibit a higher transmit power margin level, since this would potentially realize a higher spatial reuse factor. In addition, we attach higher weights to base stations that require lower minimum power levels; consequently tending to cause a lower level of interference to other transmissions. The steps of the algorithm are described as follows:
(1) As used in Algorithm 1, every client node initially associates with a single base station based on the highest received power level.
(2) The algorithm starts by determining the schedule and power levels for those base stations selected to operate in the first time slot. It continues in the same manner for scheduling outstanding multicast transmissions, if any, for subsequent time slots. At each time slot t, the process proceeds in an iterative manner, whereby the selection of the (k1)st addition of a base station to the transmission schedule is followed by considering the residual base stations and selecting, when feasible, the kth addition of a base station to the schedule.
(3) Initially, and at the end of each iteration step at which a new base station has been added to the schedule, each client node scheduled for reception at this time slot updates its CQI and sends the update to its base station. The latter then computes the level of additional interference at its critical nodes that can be still incurred, identified as the current marginal interference power level, and sends this information to the controller.
(4) Based on data made available to base stations at the termination of step k1, each residual BSi calculates the weight metric β(i) at step k by using the updated parameters ratio(i), Pmin(i) and P″max(i). The latter three parameters are calculated as follows: (a)The ratio(i) is computed by the controller using the data received from BSi that identifies the number of its current uncovered multicast clients. The value of ratio(i) is impacted by the mlinking process employed at previous iterations, when invoked.(b)The minimum power level Pmin(i) at which BSi must operate to successfully cover its multicast clients is calculated by the controller (on behalf of BSi), or by BSi itself, utilizing the marginal interference power levels reported from the critical client nodes and the latest downlink channel gain values of BSi.(c)The calculation of the parameter P″max(i) at the start of iteration k is also based on the collected CQI data, interference margins and channel gain matrices, updated at the conclusion of iteration k1. The controller calculates for each residual BSi, the maximal transmit power P″max(i) at which it can operate, assuring acceptable SINR levels at critical client nodes that have already been scheduled.
(a) The ratio(i) is computed by the controller using the data received from BSi that identifies the number of its current uncovered multicast clients. The value of ratio(i) is impacted by the mlinking process employed at previous iterations, when invoked.
(b) The minimum power level Pmin(i) at which BSi must operate to successfully cover its multicast clients is calculated by the controller (on behalf of BSi), or by BSi itself, utilizing the marginal interference power levels reported from the critical client nodes and the latest downlink channel gain values of BSi.
(c) The calculation of the parameter P″max(i) at the start of iteration k is also based on the collected CQI data, interference margins and channel gain matrices, updated at the conclusion of iteration k1. The controller calculates for each residual BSi, the maximal transmit power P″max(i) at which it can operate, assuring acceptable SINR levels at critical client nodes that have already been scheduled.
(5) Using the calculated β(i) values, only base stations with positive Δmax(i) levels are considered. For each candidate BSi, we set its transmit power level (if selected) to be P(i)=Pmin(i)+Δ(i)≤Pmax″(i), whereby Δ(i),0<Δ(i)<=Δmax(i). It is noted that setting a higher value of Δ(i) increases the residual margin at the receiver of node’s i transmission, but at the same time lowers the residual interference margin at receivers that have already been scheduled at this time slot. To simplify the implementation of the algorithm, we proceed to select the middle value for Δ(i) for the simulation results presented in the latter section.
(6) The base station with the highest weight metric β is then elected for addition to the schedule compiled (at this iteration k) for the current time slot t.
(7) At the conclusion of iteration k, when a new base station is added to the schedule, we determine whether its multicast transmission can be effectively received by client nodes that are currently not associated with it. If such clients are identified, we proceed with the mlinking process, when invoked, by directing these clients to receive the underlying multicast transmissions during this time slot from the newly selected base station.
(8) This process is repeated until no additional base stations can be included in the schedule. If there are still base stations with outstanding multicast packets, the process of scheduling such residual stations is repeated by proceeding to the next time slot.
Distributed Algorithm 3
A distributed heuristic algorithm is developed by implementing the approach described for Algorithm 2. Each BSi calculates a weight metric φ(i) that is similar to the weight metric used in Algorithm 2. It is defined as , where n_{c}(i) is equal to the current number of clients associated with BSi, Δ(i) represents the current power margin level for BSi, and is the current minimum transmit power that is computed for BSi. Each base station BSi includes its current weight metric φ(i) in control packets that it periodically distributes to its neighboring base stations that are within h hops from itself. Through this mechanism, base stations gather metric level data for their hhop neighborhood (also identified here as BSneighborhood), where h> 0. The value of h is selected to allow two base stations that are located at a distance of at least h+1 hops from each other to engage in simultaneous transmissions when using their maximum transmit power levels. For example, when operating under the parameters configured for our simulation scenario (refer to Section “Simulation results”), it is generally sufficient to set h = 2.
During each scheduling iteration step, at each available time slot, the base station with the highest weight φin its hhop BSneighborhood elects itself as a candidate for inclusion in the current schedule. The transmit power levels to be used by such candidates are determined using calculations noted below. If these computations lead to a feasible solution, the contending multicast transmissions of the winning base stations are then added to the set of scheduled multicast transmissions. Such an election mechanism leads to a selfselection outcome under which two winning base stations (at a given time slot) must be at least h+1 hops away from each other. The scheduling process proceeds in this fashion until, in all BSneighborhoods, no more base stations can add themselves to the schedule at the current time slot. The process is then repeated by residual base stations for the subsequent time slot. Steps of the algorithm are described below.
(1) Base stations periodically transmit test signals at their maximum power levels. A preliminary association of multicast clients with a base station is performed based on the base station from which it has received the strongest signal.
(2) Initially, and at the end of each iteration step, each residual base station updates its collected CQI data, interference power margins and channel gain matrices and computes the marginal interference power level for its critical client nodes.
(3) At the start of each iteration in each time slot, each residual base station BSi calculates its weight metric φ(i). The base station includes the value of this parameter in control packets that it periodically distributes in its hhop BSneighborhood. The parameter nc(i) is compiled by BSi by counting the number of its current client nodes, whereas Pmin(i) and P″max(i) are calculated by BSi using the same procedures described in Algorithm 2. Once a scheduling assignment is made and tested, if the received SINR levels are determined to be acceptable, each critical client node notifies its base station as to the interference margin level that it can still sustain. The base station distributes this data in its BSneighborhood. If this margin level is close to zero, no further multicast transmissions that impact this critical client node can be allocated at this time slot.
(4) As used for Algorithm 2, each candidate BSi sets its transmit power level (if selected) to be P(i)=Pmin(i)+Δ(i)≤Pmax″(i), whereby Δ(i),0<Δ(i)<=Δmax(i).
(5) As performed in Algorithm 2, when mlinking is invoked, the value of nc(i) is modified by allowing the effective current number of client nodes served by certain base stations to be updated. Subsequently, BSi updates its φ(i) weight metric.
(6) The BSi that has announced the highest φ value in its hhop BSneighborhood elects itself for inclusion in the transmission schedule agreed upon for the current time slot. It is noted that base stations that belong to different BSneighborhoods may elect themselves as candidates to join the schedule in a time slot. We assume time slots to be synchronized over the region of operation, so that, simultaneous transmissions by elected base stations over the same time slot can be executed.
(7) A BSi that has added itself to the schedule proceeds to transmit a test signal at power level Pmax″(i). The client nodes that are the intended receivers of such multicasts measure the ensuing interference power and SINR levels. For this purpose, measurements may only be performed by critical client nodes. Client nodes that are located in other cells and have been scheduled to receive multicast transmissions at this time slot, inform their respective base stations about the acceptability of newly generated interference signals, if any. If the underlying SINR targets are met (as is expected to usually be the case), the current schedule is deemed feasible under the selected transmit power levels.
If the schedule is determined to not be feasible due to the measurement of unacceptable interference signal levels at client nodes that belong to the BSneighborhood of BSi, the latter base station deletes the addition of its latest transmission to the schedule. It announces this deletion in its BSneighborhood, and terminates the process of contending for scheduling its transmission in this time slot. Base stations with outstanding load that are not impacted by such infeasibility events continue their scheduling process at the next iteration step. When all residual base stations in a BSneighborhood of a base station announce themselves to be in schedulingtermination state (i.e., they are not able to execute any additional transmissions at this time slot), the base station then continues the scheduling process by proceeding to the next time slot.
Computational complexity
In the following section, we show that the computational complexity of our heuristic algorithms is of polynomial order. Assume there are M base stations and N client nodes in the network. Assume that each base station has B neighboring base stations and that C client nodes residing in each cell. Under our Centralized Algorithm 2, each base station calculates its weight level by computing the parameters ratio(i), and . For this purpose, each base station performs an order of (1+C+B) calculations. Each base station then compares its weight level with the weight values announced by other base stations, determining whether its weight level makes it a current winner. Such a determination involves (at most) M comparisons. The iterative process used to obtain the schedule for a single time slot can repeat at most M times. We note that the schedule (serving the given load) will be completed after a finite number K of time slots is assigned, noting that generally K = O(M). Hence, the computational complexity of our Centralized Algorithm 2 is of the order of O(M^{3}) + O(M^{2}(C + B)).
For Distributed Algorithm 3, the analysis is similar except we note that during the contention phase, each contending base station compares its weight level only with those announced by base stations that are in its 2hop neighborhood (which are of the order of B^{2}<M). The number of iterative calculations executed in each time slot is of the order of B^{2}. These considerations lead to computational complexity of the order of O(MB^{4}) + O(MB^{2}(B + C)). To ensure the realized SINR at intended receivers is acceptable, it is now required for each newly scheduled base station to transmit test signals and receive confirmation response messages from critical client nodes. The computational complexity for this process increases when it is determined that the selected transmission is not feasible, since the recently scheduled base station must be dropped from the schedule and the contention phase must be rerun. At any rate, it is still of the order of the number of base stations residing in the 2hop neighborhood, as used for the complexity bound noted above. However, the occurrence rate of such events is generally determined to be low, assuming that sufficient margin is allowed to account for the low impact caused by interference signals that originate by transmissions of scheduled base stations that are located outside the underlying 2hop neighborhood.
We note that the computational complexity associated with Algorithm 1 is much higher than the corresponding levels for Algorithms 2 and 3. The controller proceeds first to construct an interference graph, which involves a number of comparisons of the order O(M^{2}). To find an independent set, in each iteration of the process, a node with the highest weight is selected, which entails an order of M comparisons; this is iterated a number of times that is of the order of M; thus the process is then of the order O(M^{2}). The controller then checks the feasibility of the derived schedule. Such a check is of O(M^{2}), as it requires solving the set described by Equation (2), considering critical nodes (whose number is of the order of M). The pruning and supplemental subsequent stages are each of order O(M^{3}).
Property 1
The iteration process employed by heuristic Algorithms 2 and 3 terminates after a finite number of steps with a feasible schedule.
Proof
Under both algorithms, for each iteration step in a time slot, each residual base station is capable of computing a unique weight metric. The election procedure yields a single winner with the highest metric in each contending neighborhood in which the winner is to be added to the schedule if it passes the feasibility test. The subsequent testing period allows client nodes to measure the underlying SINR levels and report back to their base stations, affirming (or not) the feasibility of new transmission additions (in their cell or in neighborhood cells) to the schedule, and updating the underlying CQI data. It is noted that during each iteration step in a time slot, when the process has not been terminated, at least a single multicast transmission is scheduled in a neighborhood. The number of outstanding packets to be multicasted during the underlying period, which is finite, is therefore reduced during each such step. Furthermore, the addition of new transmissions to an existing schedule in each time slot is executed only if it guarantees the continued feasibility of existing transmissions, therefore avoiding assignment cycles.
For the distributed algorithm, it is possible for residual base stations that belong to distinct hhop BSneighborhoods to simultaneously engage in scheduling processes. As noted above, the employed interference margins assure the feasibility of simultaneous transmissions by base stations that belong to distinct BSneighborhoods. We have assumed an area of operation with a finite number of base stations and thus neighborhoods, so that the complete scheduling process involves a finite number of steps and time slots. For the centralized algorithm, the controller can perform its scheduling of transmissions on a sequential slotbyslot basis, so that the process clearly terminates after a finite number of iteration steps and time slots. QED □
Simulation results
To study the performance of our algorithms, we have used MATLAB to simulate and analyze a homogeneous cellular network with 25 macro base station cells, with intersite distance (ISD) of 1.732 km. The value of the ISD is selected such that the LTE cell transmission radius is equivalent to m. To demonstrate that our heuristic algorithms also yield efficient schedules under heterogeneity, we later consider a heterogeneous network layout that includes both macro and micro base stations. The micro base stations are placed between the macro base stations and are thus used to cover edge clients of the macro cells, as shown in Figure 2. We assume that a micro base station can adjust its transmit power level continuously in the range 0–10 W, whereas a macro base station has an adjustable transmit power range of 0–40 W. The channel propagation gain is modeled as G_{ij} = , where d_{ij} is the distance between the transmitter and its receiver, and αdenotes the path loss exponent. The constant K accounts for propagation losses, such as absorption and penetration losses. We have assumed in our simulations that α = 3.68 and set 10log(K) to be −40 dB, corresponding to a version of the urban Costa Hata model used in LTE network studies [5,21,22]. For comparison purposes, we do not account for random fading components (which consists of mostly shadow fading variations for LTE downlink channels).
Figure 2 . Heterogeneous network grid layout using macro and micro base stations.
In our simulation, we aim to provide coverage to all clients. The realized data rate utilization level (or spectral efficiency), denoted as ψ[bps/Hz], depends upon the implemented MCS. To compare with studies presented in the referenced articles that use a basic rate of 2 [bps/Hz], we set the minimum required SINR level for each client node in our study to be 4 dB. Under an additive white Gaussian noise type channel, this leads to a Shannon’s capacity bound that yields ψ = (1 + SINR) = 2.32 [bps/Hz]. The noise power density N_{0} is set to be −174 dBm/Hz, and the transmission bandwidth is set to 5 MHz. Client nodes are randomly distributed across the area of operation. The attained receive throughput rate is presented in units of [packets/slot/user], whereby the slot duration is set equal to the transmission time of a single packet. Thus, a throughput rate of 1 [packet/slot/user] represents a receive throughput rate of ψ[bps/Hz/user].
We first consider a homogeneous cellular network that consists of 25 macro base station cells. The performance results, depicted in Figure 3, indicate that the centralized heuristic Algorithm 1, though having a much lower computational complexity, yields performance behavior that is only slightly degraded (around 10–15%) when compared with that exhibited by the MILPbased algorithm that yields the optimal schedule and transmit power setting. It is noted that the mlinking process has not been invoked for this comparison.
Figure 3 . Performance comparison between optimized algorithm and centralized Algorithm 1, without the m linking process.
In Figure 4, we compare the peruser receive throughput rate, as a function of the total number of multicast clients in the system, as attained by our algorithms. We observe that Algorithm 2 achieves a slightly lower throughput rate performance (by about 4–7%) than that attained under Algorithm 1, while Algorithm 3 exhibits a throughput rate that is further slightly degraded (by about 8–12%). We note that Algorithms 2 and 3 offer much reduced level of algorithmic computational complexity, and that Algorithm 3 entails a fully distributed implementation. For all three algorithms, we observe that as the number of clients over a prescribed area of coverage increases, an increasing number of time slots per frame is required. However, the corresponding reduction in peruser throughput rate attained under each algorithm becomes much less noticeable with further increases in client population. The synthesized schedules tend to more fully cover the complete geographical area of operation, so that multicast schedules performed to accommodate a larger number of clients will then more often also cover new clients.
Figure 4 . Performance comparison between the heuristic scheduling algorithms.
To assess the throughput gain attained by our adaptive power scheduling algorithms, when compared with LTE MBSFN schemes, we note the following. Assume that our multicasting scheme is used to share a prescribed LTE bandwidth segment, which consists of OFDM downlink channels, among neighboring base stations. Each symbol is transmitted across a narrowband subcarrier, and is attached a cyclic preamble of sufficient length such that with the use of 1tap equalization at the client receivers, no multipath fading interference is incurred [3]. Lognormal shadow fading effects can be readily included, but we neglect their effect in the following discussion since it does not impact our comparisons.
In assessing the performance behavior of OFDMAbased MBSFN systems, the study in [22] uses a bandwidth of 5 MHz and an ISD of 1.732 km. To attain complete coverage of all client nodes (at a BLER of 10%), it is determined in [22] that the common MCS that must be used by all base stations corresponds to CQI 3, which maps to an SINR value of about −3 dB. The corresponding spectral efficiency is shown to be about 0.294 [bps/Hz]. Another MBSFN scheme presented in [5] assures a target coverage probability of 95%. Using an ISD of 1 km and a bandwidth of 5 MHz, it is shown that the best MCS to use for this ISD level is 16 QAM 1/2. Using this MCS, the system is shown to attain a spectral efficiency of about 0.28 [bps/Hz], and thus a throughput rate of about 1.4 Mbps for multicasting over a single cell (see [5] Table III). In comparison, our “worst” performing Distributed Algorithm 3 achieves a throughput rate of about 0.28–0.33 [packets/slot/user], or 0.28ψ0.33ψ [bps/Hz/user]. When the system operation is associated with an MCS code rate with ψ = 2 [bps/Hz], such as 16 QAM 1/2, our scheme yields a throughput rate that is equal to about 0.56–0.66 [bps/Hz/user], leading to a data rate of 2.8–3.3 Mbps. This is higher than the spectral efficiency values of 0.28 and 0.294 [bps/Hz/user] achieved by [5,22], respectively.
By including the cyclic preamble overhead involved in OFDMA systems, the induced reduction in throughput rate is typically in the order of at most 5–10% [5,22]. For all schemes, further reduction in the realized spectral efficiency level is incurred when shadow fading is accounted for. Since the focus of this article is on the role of adaptive power operations alone, we have not included the potential enhancement achievable with data rate adaptations. We further note that under our algorithms, neighboring base stations are not required to employ the same MCS. We conclude that our algorithms achieve performance efficiency that is as high as, or higher than, that attained by the referenced LTE MBSFN operations that employ sophisticated MIMOtype signal combining techniques.
We next consider a system in which clients are divided into two multicast groups. We evaluate two multicast scheduling approaches. Under the first approach, multicast transmissions to each group are separately scheduled—in each time frame, two sequential timedivision subframes are executed, i.e., transmissions to group 1 clients are scheduled in subframe 1, followed by transmissions to group 2 clients in subframe 2. Such an operation mimics the MIMO approach, under which the same packets are scheduled for transmission at the same time by multiple base stations (though we employ no combining operations). In turn, under the second approach, multicast transmissions that belong to the two multicast group sessions are jointly scheduled. In this case, base stations that are scheduled to engage in transmissions in a certain time slot may use the allocated time slot to transmit packets that belong to any multicast group. For both cases, we have implemented the scheduling process by using Centralized Algorithm 2, incorporating the mlinking process. The performance results are displayed in Figure 5. They show that the joint scheduling scheme leads to a higher peruser throughput rate (by about 7–16% for cases under evaluation). As noted above, the joint scheduling operation provides much higher flexibility in accommodating transmissions of varying loading levels of multiple multicast group traffic flows. Such an operation is noted to lead to schedules that achieve higher spatial reuse factors, and therefore attain enhanced peruser throughput rate performance behavior.
Figure 5 . Performance of the scheduling algorithm when multiple multicast groups are involved.
To demonstrate the performance advantage that can be gained through the use of transmit power adaptations, we compare the performance of such adaptivepower algorithms with corresponding scheduling schemes that set the transmit power level of base stations to be fixed at their maximum specified levels. For both schemes, we utilize the scheduling mechanism specified by distributed heuristic Algorithm 3. Performance results are shown in Figure 6. We observe that by fixing the transmit power level, the scheduling scheme realizes a lower spatial reuse factor, requiring therefore a larger number of time slots to complete the execution of multicast transmissions, leading to reduced peruser throughput rates by about 25–35% for the examined mlinking scenario. The results displayed in Figure 6 also demonstrate the advantage gained through the mlinking process; this process is noted to improve the throughput rate for the power adaptation scenario by about 11–16%.
Figure 6 . Performance comparison between adaptivepower scheduling algorithms and those that use fixed base station transmit power levels.
In Figure 7a, we compare the peruser throughput rate performance behavior attained under the homogeneous and heterogeneous layouts. We observe that our adaptivepower scheduling algorithms also operate effectively under a heterogeneous layout. Furthermore, the latter layout is noted to lead to enhanced peruser receive throughput rates since our algorithms effectively use the micro base stations to cover their nearby clients. Under the homogeneous layout, the latter client nodes would reside in high interference celledge regions.
Figure 7 . Performance comparison of the adaptivepower multicasting algorithms for homogeneous and heterogeneous cellular network layouts (a) Peruser receive throughput rate.(b)Throughput rate per unit expanded communications power ratio metric.
To assess the energybased throughput performance gains that are achieved by our schemes, a performance measure that accounts for the total number of multicast bits transported by the system per unit energy expanded is used. The ratio of the corresponding measures attained for the corresponding fixed and adaptive power schemes, denoted as ζ is:
where and represent the number of time slots required by the employed adaptive and fixed power schemes, respectively; and are the corresponding transmit power levels selected for BSi when scheduled to transmit its multicast messages in time slot j, and the indicator function I_{i}(j) is set to 1 if BSi is assigned to transmit at time slot j, and is set to 0, otherwise. The sets and identify the schedule plans enacted under the adaptive and fixed power schemes, respectively.
In computing the ratio metric ζinvolving the receive throughput rate per unit power, we observe in Figure 7b that the adaptive power scheme, when applied to the homogeneous base station layout, achieves a receive throughout rate per unit power performance that is about 20–38% higher than that obtained under the fixed power scheduling scheme. An even better such energy aware performance metric is noted to be attained under the heterogeneous base station layout, yielding performance improvement factors of about 23–51% for the adaptive scheme. Thus, for the investigated simulation scenarios, the adaptive power scheduling scheme has been proven to derive schedules that yield high throughput rate and high throughput rate per unit power performance for homogeneous as well as heterogeneous base station layouts.
Conclusions
In this article, we develop efficient adaptivepower multicast scheduling algorithms for wireless cellular networks, under which base stations with multicast clients share their downlink channels, over an allocated frequency band on a spatialTDMA basis. We model the scheduling problem as a MILP, which is NPhard. Consequently, we present three heuristic algorithms of polynomial complexity for solving the problem in a practical manner. The algorithms make use of the coordinated operations among timeslot synchronized area base stations which jointly interact (through the use of a central controller, or in a distributed fashion) to determine their transmission schedules and transmit power levels. Similarly, our adaptivepower scheduling algorithms lead to enhanced performance for mesh WiFi networks that use such coordinations among the system access points, or mobile backbone based ad hoc wireless networks for which the elected backbone nodes employ such coordinated scheduling schemes. We show that further enhancement in throughput rate performance is achieved by using an mlinking operation under which, when feasible, a client may be directed to receive multicast packets transmitted by a base station which is not the same one that it is associated with.
For smaller systems, our simulation results demonstrate the performance of the system, when scheduling is performed by using our first centralized heuristic algorithm, to be in the 75 percentile of that exhibited by the optimal scheme. When considering larger network layouts, we show our heuristic adaptivepower scheduling algorithms to yield a peruser throughput rate that is higher than that attained by a fixed transmit power scheduling algorithm. Furthermore, our algorithms are shown to be more energy efficient than the corresponding fixed power schemes, on a throughput per unit consumed power basis. We also show that further enhancement in the throughput rate and throughput per unit power level is attained by using our adaptivepower scheduling algorithms in conjunction with a heterogeneous network layout. In assessing the corresponding performance behavior exhibited by the illustrative LTE MBSFN multicast systems, we note our schemes to yield enhanced spectral efficiency levels when high user coverage is required, while involving much less restrictive synchronization mechanisms.
Competing interests
The authors declare that they have no competing interests.
References

3GPP TS 23.246 v.10.2.0, Technical Specification, Universal Mobile Telecommunications System, LTE, Multimedia Broadcast/Multicast Service, Architecture and Functional Description, Release 10

3GPP TS 25.346 v.10.0.0, Technical Specification, Universal Mobile Telecommunications System, Introduction of the Multimedia Broadcast/Multicast Service in the Radio Access Network, Release 10

F Khan, LTE for 4G Mobile Broadband (Cambridge University Press, Cambridge, 2009)

A Alexiou, C Bouras, V Kokkinos, G Tsichrintzis, Communication cost analysis of, MBSFN in LTE. Proceedings of the IEEE 21st International Symposium on Personal Indoor and Mobile Radio Communications, 1366–1371 (2010) (Istanbul, Turkey, 2010)

L Rong, O Ben Haddada, SE Elayoubi, Analytical analysis of the coverage of a MBSFN OFDMA network. Proceedings of the IEEE Global Telecommunications Conference, 1–5 (2008) (New Orleans, LA, 2008)

R Irmer, H Droste, P Marsch, M Grieger, G Fettweis, S Brueck, H Mayer, L Thiele, V Jungnickel, Coordinated multipoint: concepts, performance, and field trial results. IEEE Commun. Mag 49(2), 102–111 (2011)

P Marsch, G Fettweis, On multicell cooperative transmission in backhaulconstrained cellular systems. Ann. Telecommun 63(5), 253–269 (2008). Publisher Full Text

R Cruz, A Santhanam, Optimal routing, link scheduling and power control in multihop wireless networks. Proceeding of the IEEE International Conference on Computer Communications, 702–711 (San Francisco, CA, 2003)

A Behzad, I Rubin, Optimum integrated link scheduling and power control for multihop wireless network. IEEE Trans. Veh. Technol 56(1), 194–205 (2007)

A Behzad, I Rubin, J Hsu, On the performance of the randomized power control algorithms for random multiple access in wireless networks. Proceedings of the IEEE Wireless Communications and Networking Conference, 707–711 (2005) (New Orleans, LA, 2005)

W Liang, Approximate minimumenergy multicasting in wireless ad hoc networks. IEEE Trans. Mobile Comput 5(4), 377–387 (2006)

J Wieselthier, G Nguyen, A Ephremides, On the construction of energyefficient broadcast and multicast trees in wireless networks. Proceeding of the IEEE International Conference on Computer Communications, 585–594 (2000) (TelAviv, Isreal, 2000)

3GPP TS 25.214 v.10.5.0, Technical Specification, Universal Mobile Telecommunications System, Physical Layer Procedures, Release 10

A Behzad, I Rubin, High transmission power increases the capacity of ad hoc wireless networks. IEEE Trans. Wirel. Communi 5(1), 156–165 (2006)

T Rappaport, in Wireless Communications: Principles and Practice, (PrenticeHall, Englewood Cliff, NJ, 2002)

B Noble, J Daniel, in Appied Linear Algebra, (PrenticeHall, Englewood Cliff, NJ, 1988)

N Bambos, S Chen, G Pottie, Radio link admission algorithms for wireless networks with power cotnrol and active link quality protoction. Proceeding of the IEEE International Conference on Computer Communications, 97–104 (1995) (Boston, MA, 1995)

M Pursley, H Russell, J Wysocarski, Energyefficient transmission and routing protocols for wireless multiplehop networks and spreadspectrum radios. Proceeding of the IEEE/AFCEA EUROCOMM 2000, Information Systems for Enhanced Public Safety and Security, 1–5 (2000) ((2000), pp, 2000), . 1–5

M Halldorsson, J Radhakrishnan, Greed is good: approximating independent sets in sparse and boundeddegree graphs. Algorithmica 18(1), 145–163 (1997). Publisher Full Text

T Lee, J Lin, Y Su, Downlink power control algorithms for cellular radio systems. IEEE Trans. Veh. Technol 44(1), 89–94 (1995). Publisher Full Text

V Abhayawardhana, I Wassell, D Crosby, M Sellars, M Brown, Comparison of empirical propagation path loss models for fixed wireless access systems. Proceedings of the IEEE Vehecular Technology Conference, 73–77 (2005) (Stockholm, Sweden, 2005)

A Alexiou, C Bouras, V Kokkinos, G Tsichritzis, Spectral efficiency performance of MBSFNbased LTE networks. Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, 361–367 (2010) (Chengdu, China, 2010)