In this paper, we investigate the multi-resource allocation problem, a unique feature of which is that the multiple resources can compensate each other while achieving the desired system performance. In particular, power and time allocations are jointly optimized with the target of energy efficiency under the resource-limited constraints. Different from previous studies on the power-time tradeoff, we consider a multi-server case where the concurrent serving users are quantitatively restricted. Therefore user selection is investigated accompanying the resource allocation, making the power-time tradeoff occur not only between the users in the same server but also in different servers. The complex multivariate optimization problem can be modeled as a variant of 2-Dimension Bin Packing Problem (V2D-BPP), which is a joint non-linear and integer programming problem. Though we use state decomposition model to transform it into a convex optimization problem, the variables are still coupled. Therefore, we propose an Iterative Dual Optimization (IDO) algorithm to obtain its optimal solution. Simulations show that the joint multi-resource allocation algorithm outperforms two existing non-joint algorithms from the perspective of energy efficiency.
The explosive growth of wireless communication applications has imposed an unprecedented burden on the already scarce radio resources such as spectrum and energy in all networks. So efficiently scheduling the limited resources in future broadband wireless networks is an urgency. Among the resource scheduling methods, two categories could be given, i.e. single resource scheduling and joint multi-resource scheduling. For the joint multi-resource scheduling, their mutual relationship is the potential law behindscheduling. Generally, there are two types of relationships among multi-resources, i.e. the dependence type [1, 2] and the compensation type [3, 4]. The former means that the more resource A is needed the more resource B is consumed, while the later is opposite, meaning that the less resource A is needed the more resource B is consumed. Fig. 1 gives a simple illustration. For example, the bandwidth and the processing resource [1] together with the memory and the CPU [2] belong to mutual dependent resources, while the carrier and the power are the mutual compensating resources [3] as well as the power and the time [4]. When all the resources are limited, the optimization for resources with compensation relationship is difficult to perform comparing with that for resources with dependence relationship.
The category of the multi-resource allocations. Resource A and resource B are mutual dependent, so if one user who used one unit of resource A and one unit of resource B previously, wishes to use three units of resource A, he must request three units of resource B together. Resource C and resource D are mutual compensating, so the user could gain the same system performance in spite of he uses one unit of resource C and three units of resource D or three units of resource C and one unit of resource D.
The mutual-compensating resource allocation problem has been investigated in recent years. In OFDM system, the joint subcarrier and power allocation is researched in lots of studies such as [3][5][6]. The work [3] concludes that it is better to equally allocate resources under utility maximizing target and to selectively allocate resources under fairness target. However, it doesn’t take into account the mutual constraint between power and carrier number. In [5], Chao Xu et al. consider both the spectrum competition among multiusers and the power-subcarrier mutual constraint relationship for each user. The relationship is that the power allocation couldn’t be more than its threshold set by the subcarrier allocation so as to guarantee the primary user’s interference. In [6], three resources, i.e. subcarrier, time and power, are jointly allocated, but due to their complex 3-dimension compensation, the authors have to adopt the artificial intelligence method to solve the problem. In LTE system, the bandwidth resource and power resource are allocated in a joint centralized and distributed approach in [7]. Once the bandwidth allocation is changed in the upper layer, the uplink power allocation is changed consequently in lower layer due to the resource compensation. By virtue of the continuous rate adaption, the power resource and the time resource are usually jointly allocated in order to gain better system performance, such as the work [4] where the energy-delay tradeoff is explored. In wireless relay system, the power and time resource allocations for source node and relay node are compensating while satisfying the information consistent principle in [8]. To summarize, different circumstances may implicate different mechanisms to handle mutual-compensating resources and hence, there is no unified method to borrow from.Power and time resources are our focus here. The emphasis is to efficiently utilize the compensation relationship between the two resources. Sometimes, it is also exhibited as a tradeoff problem, i.e., given a fixed transmission load, consuming less transmitting time would lead to a shorter transmission delay (by virtue of the adaptive coding and modulation scheme in physical layer), but need to expend more power instead; and vice versa. Lots of researches have focused on this topic. Authors in [9] firstly propose the lazy packet scheduling scheme which directly minimize the energy consumption through maximizing the transmission time. Then the work [10] adopts this principle in burst-source case to guarantee the delay performance and minimize the energy. In [11], Eytan Modiano’s academic team maximizes the data throughput in an energy-and-time constrained system over a fading channel, while Munish Goyal in [12] achieves the delay optimal policies in the same circumstance. Similar work can be found in [13], where its bit-allocation policies take the opportunistic (channel-aware) term into consideration. Another work [14] optimizes the power and time allocation iteratively in the energy harvesting downlinks while the work [15] transforms the delay constraint into capacity constraint by effective capacity theory so as to manage the mutual-compensating relationship. All the above researchers consider a single-server scheduling problem, lacking of the consideration of multi-server cases. Neely et al. in [16] research the parallel queuing problem, and allocate the power resource as well as manage the delay performance according to the queuing length. And Xun Zhou et al. investigate the parallel power allocation problem in [17], maximizing the weighted sum-rate over all users. Though the two works are multi-server cases, the amount of servers therein is equal to that of users, which in fact ignores the contention on the time horizon. YingJun in [18] proposes a multi-server PGPS method from an ideal perspective, but it doesn’t consider the service ability interaction incurred by the power sharing in our problem. Another work in [19] considers the power allocation and the user selection among multiple servers, but it assumes the time allocation is given and fixed. Actually, in wireless communication, user number is more than the available server number most of time, which results in that the power-time tradeoff occurs not only between the users in the same server but also between the users in different servers.In this work, we will discuss the power and time scheduling problem combined with the user selection to increase the energy efficiency. The user selection is used to choose the recipients for the multi-resource allocation, different from the intention in MIMO [20] or relay [21] domains where it aims to choose the best transmission pairs to gain the spatial diversity or spatial multiplexing. The selection is performed multiple times in a whole scheduling period in order to serve all the users completely. The emergence of user selection is actually posing extra complexity to the traditional power-time tradeoff problem. As a result, the optimal problem comprises integer programming and nonlinear programming, which has been verified to be NP-hard. A state decomposition model is proposed to facilitate the mathematical optimization, and simplify the inherent complexity of the joint design problem. We verify it a convex optimization problem, but the solution is hard to obtain explicitly since its parameters are coupled. Therefore, we propose an Iterative Dual Optimization (IDO) algorithm to gain the solution. The effectiveness of the algorithm is verified by the simulations.The rest of this paper is organized as follows: section 2 introduces the system model, and the energy saving problem is formulated in section 3. In section 4, we analyze and deduce the exact solutions for two special cases. Section 5 proposes the IDO algorithm to solve the coupled convex optimization problem. From the perspective of the energy consumption, we compare the performance of the proposed algorithm with two existing non-joint algorithms in section 6. Finally, section 7 concludes our work.
2. Multi-server Downlink System
The multi-resource scheduling in this work targets at a radio system where the resource A and resource B are compensatory. This kind of systems is almost resource-limited [22]. In our consideration, we take the beam hopping system [23] in satellite communication as our background, shown in Fig.1. In this system, one beam (usually the spot-beam) is envisioned as a server. Restricted by the satellite payload, beam number is less than the footprints (in this work, we call it ‘cell’). The so-called user in this work represents the cell in this system. Satellite power is limited and the scheduling period is also limited to a given time duration. In this scheduling period, all the cells should be served or scanned at least one time to provide downlink service. Although several precedents [24-26] have made efforts on the cell selection and the time allocation in this framework, none of them studies the joint design.Considering the multi-beam satellite downlinks shown in Fig. 2, the satellite is equipped with N beams through the beam forming technology, whose target direction is controlled by the network control central (NCC). The delay of direction changing could be ignored when the advanced antenna technology is taken into account [27]. The coverage area is divided into K cells ( N ≤ K ) with same illumination shape on earth. One beam serves (transmits signals to) only one cell at a given time instant, and one cell is not allowed to be served by two or more beams (beam diversity is out the scope of this work). Due to the spatial separation, all the beams use the same frequency and their inter-beam interference is ignored. All beams share the fixed power P_{tot}. Let P_{k} denote the downlink transmitting power for cell n , and G denote the directional antenna gain, we obtain the effective isotropic radiated power I_{k} = P_{k}·G . Adaptive coding and modulation (ACM) technology is adopted, and in this design of allocation algorithm, we use the ideal capacity limitation to represent the achievable data rate (in bps) as follows.
PPT Slide
Lager Image
where g_{k} = G×|h_{k}|^{2} / (B×N_{0}) is the effective channel-to-noise ratio (CNR) [28] which could be measured by the feedback information or the estimation of the uplink CNR. And h_{k} is the channel gain from the satellite to the cell k (in this work, the distance from the satellite to each cell on earth is far enough, so the channel gains from different beams to one given cell are equal), N_{0} is the noise power density and B is the allocated bandwidth.
The considered satellite downlink with multiple beams.
Each cell may have different traffic flows, e.g. the voice call, the web browsing, etc., therefore they need different channel capacities at different time to fulfill their quality of service (QoS) performances. By the uplink report, we could obtain the average capacity requirement C_{k} (in bit) of each cell in one allocation1 period T . Hereafter, it is called capacity requirement for simplicity. And all the capacity requirements of the cells we considered are controlled in the systematic stability [16] in the access control stage which is out of our scope here.Some important symbols defined in this work are listed in Table 1.
Hereafter, the scheduling period is also called the allocation period.
3. Multi-resource Allocation and Cell Selection
- 3.1 Mutual-compensating Resources and Problem Formation
As is well known, the power and time resources are mutually compensating in achieving a given capacity. For example, when the g_{k} is very low, a low order modulation (e.g. the BPSK) could be used while prolonging the transmission time so as to maintain the total capacity, and when the g_{k} is high enough to use high order modulation (e.g. 16QAM), short time could be comsumed.In this work, our target is to efficiently allocate the power-time resource so as to satisfy all cells’ capacity requirements with minimal energy consumption in one allocation period. After obtaining the power-time allocation rule, the muiltiple beams could hop correspondingly. The constraint optimization problem is unique considering the following facts.(a) The power and time resources are mutual compensating in achieving a certain capacity, because the ACM scheme is adopted in the physical layer.(b) The capacity requirement of each cell could be satisfied by means of cumulation via more than one times, because each cell could be illuminated multiple times in one allocation period as long as allowed.(c) The maximal served cells in every time instant are limited by the beam (sever) number. In order to understand the issue better, we take the Bin Packing framework to formulate it. And without loss of generality, we consider that the allocation period is one unit time, i.e. T = 1.The total energy is formulated as a box with the maximal usable power P_{tot} as its fixed length and the unit time as its fixed width. Each cell is formulated as the goods to pack. Different from the traditional goods, the goods here have fixed weight representing its required capacity C_{k} and adjustable length and width representing its allocated power p_{k} and serving time τ_{k} . Note that the goods could be dividable, restrained by
PPT Slide
Lager Image
where M_{k} is the maximum number of division items for goods k . The question is that how to minimize the total occupied space while the goods are all packed in box. Another special constraint is that there could be no more than N items at length horizon of the box, limited by the server number. For example, in left part of Fig. 3, at most 2 items are in parallel. Till now, we know this is a variant of 2-Dimension Bin Packing Problem (V2D-BPP), which is a joint non-linear and integer programming problem. It is NP hard.
The V2D-BPP and the state decomposition ( N = 2,K = 4 and S = 6 )
- 3.2 Cell Selection and State Decomposition
From the aforementioned variant of 2D-BPP, we find that the capacity requirement of each cell could be divided into multiple portions to satisfy, and each portion could be with different power-time assignment. So the problem is entirely different from the traditional 2D-BPP. In this work, we transform the formulation into a state decomposition model in Fig. 3.We list all the possible cell combinations observed at any given time, expressed by the following state set (one form of cell combination is defined as one state).
PPT Slide
Lager Image
where δ_{s,k} indicates whether cell k is selected when the state index is s (‘1’ means yes, and ‘0’ means no), and S =
PPT Slide
Lager Image
is the amount of combinations that N is chosen from K . One example is given in Fig. 3. In order to express the beam hopping scheme, we introduce the time ratio π_{s} denoting that the system is in the s -th state, and
PPT Slide
Lager Image
. Therefore the total serving time for cell k is calculated as τ_{k} =
PPT Slide
Lager Image
. Then, using the state decomposition, the parameter system could be expressed as <p_{s,k},π_{s},∀s,k>.
- 3.3 On-demand Resource Allocation with Multiple Servers
Since there are multiple servers, i.e. the multiple beams here, an intrinsic question is that how many of them should be used for the purpose of minimizing energy consumption. To answer this question, we first give the theorem (also be found in [9]) to find which approach is more efficient to save energy, i.e. to save power or serving time.Theorem 1: for a beam, under the condition that its capacity requirement is satisfied, the method of cutting down the power and increasing the serving time could save more energy. Let ΔE denote the volume of the saved energy by increasing a unit serving time when the serving time is τ, then ΔE is decreasing in τ .Proof: the proof is given in Appendix A.From Theorem 1, we can learn the time consumption is more effective than the power consumption for the energy saving. Since the equivalent serving time is proportional to the server number, so it is wise to use all the N beams simultaneously.Based on the state decomposition and the utilization of all the beams, we formulate the energy saving problem in ( P1 ).
PPT Slide
Lager Image
where Ω_{s} is the set of cells with δ_{s,k} = 1 when the system is in s -th state, and ω_{k} is the set of states when the cell k is chosen to serve. The target is to minimize the consumed energy. The first constraint is to satisfy the capacity requirements for all cells, the second is the total power constraint and the third is the total time constraint. Till now, we can get that the variables to optimize are reduced to two continuous types, i.e. p_{s,k} and π_{s}, and the problem is transformed to pure non-linear programming problem.
4. The Optimal Resource Allocation for the Cases ofN= 1 andN=K
In this section, we discuss two special cases when the beam number is 1 and K respectively, i.e. N = 1 and N = K .When N = 1 , only one beam exists, and it has to poll all the cells sequentially. According to Theorem 1, with the objective of energy saving, cutting down the power is more efficient than diminishing the serving time for one beam, so we simplify the ( P1 ) as
PPT Slide
Lager Image
where p_{k} is simplified by p_{s,k} because the number of the system states is equal to the cell number. Substituting the first constraint in this problem into the objective function, we have that
PPT Slide
Lager Image
where τ = (τ_{1},...,τ_{K}) . The convexity of this function is given in the following theorem.Theorem 2: the function f (τ) is convex.Proof: the proof is given in Appendix B.The feasible set of the problem is defined by
PPT Slide
Lager Image
, which is also convex. So the problem (P2) is a convex optimization problem, which is easily solved by the method such as steepest descent [29] in polynomial time. After computing the optimal serving time
PPT Slide
Lager Image
, its associated power
PPT Slide
Lager Image
could be obtained with the first constraint in (P2).When N = K , we just need to allocate the power with the optimal serving time
PPT Slide
Lager Image
= 1, ∀k . And the optimal power allocation is also obvious, which is the least power satisfying the capacity requirement, i.e.
PPT Slide
Lager Image
.
5. The Optimal Resource Allocation for the Case of 1
- 5.1 The Difficulty in the Convex Optimization
The objective function in ( P1) is a sum of functions of f(π_{s},p_{s,k}) = π_{s}·p_{s,k} , whose projection in a random path (say π_{s} = σ_{1}·p_{s,k} + σ_{2},(σ_{1},σ_{2})∈ℜ^{2}) of its domain is convex. So the cumulative convex function is also convex. Moreover, the constraints in ( P1 ) are convex, making the problem a convex optimization problem. In the following, we will adopt the Lagrange Method to derive some optimality conditions.Introduce the 0-1 constants δ_{s,k} into ( P1 ), and then sort the problem. The Lagrangian of the problem is given by
PPT Slide
Lager Image
where λ = (λ_{1},...,λ_{K}) ≥ 0 , β = (β_{1},...,β_{S}) ≥ 0 and γ are the Lagrange multipliers for the constraints in ( P1 ). Applying the Karush-Kuhn-Tucker (KKT) condition, we obtain the following necessary and sufficient conditions for the optimal solutions
PPT Slide
Lager Image
and
PPT Slide
Lager Image
.
PPT Slide
Lager Image
PPT Slide
Lager Image
Differentiating the Lagrangian (9) with respect to p_{s,k} and π_{s} respectively, we obtain
PPT Slide
Lager Image
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
= 0, and associating with the KKT condition in (10), we can obtain
PPT Slide
Lager Image
where (x)^{+} = max(0,x) . From the view of water filling [29], expression (14) clearly indicates that the water-filling levels of different cells at a certain system state are different depending on λ_{k}, and the water-filling levels of the same cell at different system states are also different depending on π_{s} and β_{s}. This indicates that the two types of parameters are coupled, which could not be easily solved by the general non-linear optimization algorithm. So in the next two subsections, we will propose an iterative dual optimization (IDO) algorithm.In addition, we notice that expression (13) does not contain the parameter π_{s}, which indicates that the partial derivative with respect to π_{s} is constant. This will be used for the updating of π_{s} in the following subsections.
- 5.2 Optimal Power Allocation for Given Time Ratios
In this subsection, we present optimal power allocation for given time ratios, while the next subsection is the calculation of optimal time ratios based on the obtained optimal power allocation herein.Define ℵ as the set of all non-negative power matrixes p whose entry is p_{s,k} , satisfying that if δ_{s,k} = 0 , then p_{s,k} = 0. The Lagrange dual function of ( P1 ) is given by
PPT Slide
Lager Image
And the dual optimization problem is formulated as
PPT Slide
Lager Image
Note that the Lagrangian J_{2} (...) is linear in λ_{k} and β_{s} for a given p_{s,k}, so the minimization of the Lagrangian is convex. To solve the dual problem, we first decompose the dual function into S independent optimization problems:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
Substituting the optimality condition (14) into (18), we can obtain the simplified expression:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the allocated power with the dual variables. The subgradients of the dual function are derived using a similar method as in [28]:
PPT Slide
Lager Image
PPT Slide
Lager Image
Denote ▽ = (▽λ_{k}, ▽β_{s}), and the dual variables are updated by
PPT Slide
Lager Image
where the superscript is the step l , and є^{(l)} is the step size of step l . The iterative is guaranteed to converge to the optimal dual variable
PPT Slide
Lager Image
. It is necessary to limit a proper initial choice of the dual variables, using the feasible set of the dual problem by the Lemma 1.After getting the optimal values of the dual variables, the optimal power allocation
PPT Slide
Lager Image
could be obtained by (14). Due to the dual theory, the strong duality for the primary problem holds, which guarantees the optimality of the obtained power allocations.Lemma 1: the optimal dual variables {λ^{*}, β^{*}} must satisfy
PPT Slide
Lager Image
Proof: the proof is given in Appendix C.
- 5.3 Updating of the Time Ratios
The obtained power allocation
PPT Slide
Lager Image
in the last subsection is depending on the given time ratios. Though the optimal allocation of time ratios obeys the KKT conditions, one can’t achieve the optimal value directly due to the absence of π_{s} in (13). Fortunately, the expression (13) is constant after the power
PPT Slide
Lager Image
is obtained. We propose a time ratio updating method to approach the optimality iteratively.The reverse direction of the subgradient of ^{J1(..)} is chosen for the updating direction according to definition of gradient, as follows.
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is the step size of step l for updating the vector ^{π} and
PPT Slide
Lager Image
whose value could be obtained by substituting the
PPT Slide
Lager Image
and
PPT Slide
Lager Image
into (13).Considering the Theorem 1, the optimal time ratios must satisfy
PPT Slide
Lager Image
, so we perform the updating along the criterion all the same.
PPT Slide
Lager Image
This is solved as
PPT Slide
Lager Image
where
PPT Slide
Lager Image
. Let γ^{(l)} denote the solved γ .The updated values are recursively substituted into subsection 5.2 until the following terminal condition is reached.
PPT Slide
Lager Image
where ΔE is the energy difference between two adjacent iterations, ℓ_{OL} is a very small number in the outer loop.Finally, the outline of the optimal resource allocation for the case of 1 < N < K is presented in Table 2.
In this section, numerical results are given to verify the performance of the proposed multi-resource allocation algorithm. The original purpose of resource allocation in the beam hopping is to save energy while satisfying the capacity requirements, and power allocation, time allocation and user selection are jointly considered, which is different from the existing works.Simulation setups: the total usable power in satellite is considered to be P_{tot} = 100w. The effective channel-to-noise ratios (CNRs) of the downlinks are distributing randomly and uniformly in a value region -20dB < g < 0dB for simulation. The allocation period T is set to be unit time (i.e. T = 1 ) for simplicity. The terminal condition of the IDO algorithm is ℓ_{OL} = 10^{-5}. The capacity requirements of all the cells are supportable, which are valued in the access control step before the resource allocation using the following criteria.
PPT Slide
Lager Image
We make some algorithm comparisons. There is no doubt that the beam hopping with the target of energy saving performs better than that without the energy-saving target. We especially wonder its advantage comparing with other energy-saving algorithms. The first comparing algorithm is the Multi-server Packetied General Processor Sharing (MPGPS) in [18], which assigns each user a fixed power value to satisfy the packet loss rate є_{p} as follows.
PPT Slide
Lager Image
The second one is Opportunistic Power Scheduling (OPS) in [19], which schedules the users in a period and also allocates an appropriate transmission power level to scheduled users, but without the time allocation.In the simulation, the ideal algorithm calculates the power allocation with the assumption that the beam number is equal to the cell number, in which case the serving time for each cell is τ_{k} = 1 . It is an ideal energy-saving policy, but it is unrealizable since N < K in our consideration. And our algorithm, i.e. multi-resource allocation and user selection, is called MAUS for short.Fig. 4 shows the consumed energy with different amount of beams, where the number of cells is fixed at K = 8 . The effective channel-to-noise ratio of each cell is generated randomly in aforementioned value region. It is observed that the ideal case needs about 12.5 Joule when there is equivalent amount of beams, but the MPGPS algorithm needs nearly 40 Joule at N = 2 , which is three times larger. As the amount of beams increases, energy needed decreases for all beam hopping schemes. This also verifies the impact of the beam quantity on the energy conservation. This is expected because more resources are invested. When the beam number is also equal to 8, the OPS algorithm gives a hopping scheme with the same performance as the ideal one and our MAUS one, because the serving time for each cell is prolonged to one unit in this case. But the MPGPS algorithm still allocates the fixed transmitting power for all beams, which wastes the energy shown in figure. Evidently, the proposed MAUS algorithm outperforms the other two non-joint algorithms, which verifies its effectiveness. And MAUS could gain nearly the same performance as the ideal one, according to the figure. However, the gap between MAUS and the ideal scheme is intrinsic, because the beams in the calculation of MAUS are less than the cells.
Consumed energy versus the amount of the beams at K=8
From the analysis in the figure 4, we conclude that the beam resource could compensate the energy requirement, if properly utilized. Theoretically, system capacity with only one beam could be referred to as the conservative capacity, and system capacity with N = K beams as the aggressive capacity. In Fig. 5, we study the capacity bounds of two-cell case, precisely the upper bound. The CNR of two cells are set to be -7dB and -2.6dB. One can judge if a given system capacity could be supportable and how many beams are needed from the results.
In Fig. 6, we investigate the influence of traffic intensity of the cell on the energy conservation. For comparability, we maintain the mutual proportion of all the cells’ traffic intensity while increasing the average intensity in simulation. Two cases are investigated, i.e. Large Variance (LV) and Small Variance (SV). The former means that the distribution of cells’ traffic is with a large variance, while the latter is with a small variance. In order to scale the variance, we define the variance coefficient, expressed as:
PPT Slide
Lager Image
We know 0 ≤ ρ_{C} ≤ 1. If ρ_{C} ≥ 0.5 , we call it LV; if ρ_{C} < 0.5 , we call it SV. In the simulation, typical values are considered, i.e. in LV case, C = a×(1/100,1/100,1/100,1/100,1,1,1,1), and in SV case, C = a×(1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2), where a is the varying average intensity. It is observed that our MAUS algorithm performs better in view of energy saving than the other two non-joint algorithms, and the stronger traffic intensity the better comparability performance. From the result, we get that the LV case consumes more energy than the SV case, because that LV case has more cells requiring large capacity and meanwhile large capacity needs nonlinearly large energy based on the Shannon’s Capacity. But the LV case is more suitable for our MAUS algorithm than the SV case, which obviously shows our algorithm’s performance advantage. This is mainly due to the fact that non-joint allocation couldn’t adapt and control all the resources.
Consumed energy with the average traffic intensity (‘LV’ denotes Large Variance, ‘SV’ denotes Small Variance)
Finally, we study the inherent complexity property of the iterative dual optimization algorithm. As far as we know, the complexity of convex programming depends on the number of optimization variables and the number of iterations [30]. In this algorithm, the number of inner-loop iterations required to achieve ℓ_{IL} -optimality, i.e. Δξ < ℓ_{IL} , is on the order of
PPT Slide
Lager Image
. And the number of outer-loop iterations required to achieve
PPT Slide
Lager Image
-optimality, i.e. Δξ <
PPT Slide
Lager Image
, is on the order of
PPT Slide
Lager Image
. Hence, the computational complexity is
PPT Slide
Lager Image
, which is growing with the factorial of K . This could be improved by three ways: one way is to divide all cells into several separating alliances, each of which shares the service of one dedicated beam; another way is to develop some heuristic methods such as always serving the N cells with the best C_{k} / g_{k} ; the last one is to use the artificial intelligence to search for the solution straightforwardly. In any case, this inherent drawback will be the incentive for our future effort.
7. Conclusions and Future Researches
In this paper, we work on to solve the multi-resource allocation problem when the concurrent served users are limited. The resources here have a unique feature that they can compensate each other for the purpose of achieving the same performance. We jointly perform the power allocation, the time allocation and the user selection in the case study of the beam hopping. A state decomposition model is proposed to reduce the complexity of the joint optimization problem. Moreover, we propose an iterative dual optimization algorithm to solve the convex optimization problem. At last, the simulation results show that the proposed algorithm improves the energy efficiency significantly. Our proposed algorithm could also be used in other similar resource-limited radio systems.Future researches could be implemented from the following three directions. Firstly, the computational complexity of our algorithm is one major issue to improve in our future research. The improvement is critical to the realization of the algorithm, as the computation time determines the timeliness of resource allocation directly. Secondly, one potential assumption in our algorithm is that the earth stations in all the cells are capable of adaptive modulation and coding continuously. In fact, the modulation and coding scheme could only be chosen in a limited set, so it is impossible to use up all the possible power-time allocations. So it is necessary to develop the on-demand allocation algorithm based on the limited resource utilization modes. Lastly, the proposed algorithm is performed periodically, without the period optimized. It will be much more effective if the allocation period is properly optimized.
BIO
Han Han received his B.S. degree and M.S. degree from PLA University of Science and Technology, Nanjing, China in 2008 and 2011 respectively. He is currently pursuing his Ph.D degree in PLA University of Science and Technology. His current research interests include cognitive radio, satellite communication, resource allocation and game theory. He is the recipient of the Jiangsu Province Excellent Master Theses Award in 2012. He is also the reviewer of several journals in his research area.
Yuhua Xu received his B.S. degree in Communications Engineering, and Ph.D. degree in Communications and Information Systems from College of Communications Engineering, PLA University of Science and Technology, in 2006 and 2014 respectively. He has been with College of Communications Engineering, PLA University of Science and Technology since 2012, and currently as an Assistant Professor. His research interests focus on opportunistic spectrum access, learning theory, game theory, and distributed optimization techniques for wireless communications. He has published several papers in international conferences and reputed journals in his research area.
Dr. Xu is an Editor for the KSII Transactions on Internet and Information Systems. He served as the Symposium Co-Chair for Advanced Game Theory Framework Applied to Wireless Emerging Communication Networks, in the International Conference on Game Theory for Networks (GameNets 2014), and served as the TPC member: for Track on Cognitive Radio and Spectrum Management in 22th IEEE Symposium on Personal, Indoor, Mobile and Radio Communications (PIMRC 2011), for Track of Intelligent and Cognitive Radio Networking in 9th International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA 2014) and for Track of Networking, Protocols, Cognitive Radio, Wireless Sensor Networks, Services and Applications in 12th International Symposium on Wireless Communication Systems (ISWCS 2015). In 2011 and 2012, he was awarded Certificate of Appreciation as Exemplary Reviewer for the IEEE Communications Letters.
Qinfei Huang received his B.S. degree and Ph.D. degree in communication engineering from the National University of Defense Technology (NUDT), Changsha, China, in 2004 and 2010, respectively. He is currently with the Beijing Capital Highway Development Group Co. Ltd. His research interests are in the area of signal processing for wireless communications and intelligent transport systems.
Zhou Y.
,
Sethu H.
2005
"On achieving fairness in the joint allocation of processing and bandwidth resources: principles and algorithms,"
IEEE/ACM Transactions on Networking
13
(5)
DOI : 10.1109/TNET.2005.858449
Sen C. S.
,
Lan T.
,
Chiang M.
2013
"Multiresource Allocation: Fairness–Efficiency Tradeoffs in a Unifying Framework,"
IEEE/ACM Transactions on Networking
21
(6)
1785 -
1798
DOI : 10.1109/TNET.2012.2233213
Lee H.W
,
Chong Song
2008
"Downlink resource allocation in multi-carrier systems: frequency-selective vs. equal power allocation,"
IEEE Transactions on Wireless Communications
7
(10)
3738 -
3747
DOI : 10.1109/T-WC.2008.061110
Chao X
,
Min S
,
Chungang Y
,
Xijun W
,
Liang W
2014
"Pricing-Based Multiresource Allocation in OFDMA Cognitive Radio Networks: An Energy Efficiency Perspective,"
IEEE Transactions on Vehicular Technology
63
(5)
DOI : 10.1109/TVT.2013.2280617
Quansheng X
,
Xi L
,
Hong J
,
Xiaojiang D
2014
"Energy-Efficient Resource Allocation for Heterogeneous Services in OFDMA Downlink Networks: Systematic Perspective,"
IEEE Transactions on Vehicular Technology
63
(5)
DOI : 10.1109/TVT.2014.2312288
Chungang Y
,
Jiandong L
,
Hongyan L
,
Min S
,
Qin L
,
Wei L
,
Yuzhou L
"Multi-resource allocation for LTE networks: Joint-optimality and distributed algorithm,"
in Proc. of 20th Int. Conf. on Telecommunications (ICT)
6-8 2013
Zijian M
,
Weifeng S
,
Batalama S
,
Matyjas J.D
2014
"Cooperative Communication Protocol Designs Based on Optimum Power and Time Allocation,"
IEEE Transactions on Wireless Communications
13
(8)
DOI : 10.1109/TWC.2014.2315813
Prabhakar B
,
Uysal Biyikoglu E
,
El Gamal A
"Energy-efficient transmission over a wireless link via lazy packet scheduling"
in Proc. of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. (INFOCOM)
2001
386 -
394
Rajan D
,
Sabharwal A
,
Aazhang B
2004
"Delay-bounded packet scheduling of bursty traffic over wireless channels,"
IEEE Transactions on Information Theory
50
(1)
125 -
144
DOI : 10.1109/TIT.2003.821989
Fu A
,
Modiano E
,
Tsitsiklis J N
2006
"Optimal transmission scheduling over a fading channel with energy and deadline constraints,"
IEEE Transactions on Wireless Communications
5
(3)
630 -
641
DOI : 10.1109/TWC.2006.1611093
Goyal M
,
Kumar A
,
Sharma V
"Power constrained and delay optimal policies for scheduling transmission over a fading channel,"
in Proc. of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM)
2003
311 -
320
Lee J
,
Jindal N
2009
"Energy-efficient scheduling of delay constrained traffic over fading channels."
IEEE Transactions on Wireless Communications
8
(4)
1866 -
1875
DOI : 10.1109/T-WC.2008.080037
Tekbiyik N
,
Girici T
,
Uysal-Biyikoglu E
,
Leblebicioglu K
2013
"Proportional Fair Resource Allocation on an Energy Harvesting Downlink,"
IEEE Transactions on Wireless Communications
12
(4)
DOI : 10.1109/TWC.2013.021213.120523
Helmy A
,
Musavian L
,
Tho Le-Ngoc
2013
"Energy-Efficient Power Adaptation over a Frequency-Selective Fading Channel with Delay and Power Constraints,"
IEEE Transactions on Wireless Communications
12
(9)
DOI : 10.1109/TWC.2013.080113.120767
Neely M J
2007
"Optimal energy and delay tradeoffs for multiuser wireless downlinks,"
IEEE Transactions on Information Theory
53
(9)
3095 -
3113
DOI : 10.1109/TIT.2007.903141
Xun Z
,
Rui Z
,
Chin K. H
2014
"Wireless Information and Power Transfer in Multiuser OFDM Systems,"
IEEE Transactions on Wireless Communications
13
(4)
DOI : 10.1109/TWC.2014.030514.131479
Zhang Y J
2007
"A multi-server scheduling framework for resource allocation in wireless multi-carrier networks,"
IEEE Transactions on Wireless Communications
6
(11)
3884 -
3891
DOI : 10.1109/TWC.2007.060288
Lee J W
,
Mazumdar R R
,
Shroff N B
2006
"Opportunistic power scheduling for dynamic multi-server wireless systems,"
IEEE Transactions on Wireless Communications
5
(6)
1506 -
1515
DOI : 10.1109/TWC.2006.1638671
Bayesteh A
,
Khandani A K
2008
"On the user selection for MIMO broadcast channels,"
IEEE Transactions on Information Theory
54
(3)
1086 -
1107
DOI : 10.1109/TIT.2007.915887
Yang D
,
Fang X
,
Xue G
2012
"HERA: An optimal relay assignment scheme for cooperative networks,"
IEEE Journal on Selected Areas in Communications
30
(2)
245 -
253
DOI : 10.1109/JSAC.2012.120202
Pardo F
,
Zuccarello P
,
Boluda J.A
,
Vegara F
2011
"Advantages of Selective Change-Driven Vision for Resource-Limited Systems,"
IEEE Transactions on Circuits and Systems for Video Technology
21
(10)
1415 -
1423
DOI : 10.1109/TCSVT.2011.2162761
Acampora AS
,
Ta-Shing Chu
,
Dragone C
,
Gans M.J
1991
"A metropolitan area radio system using scanning pencil beams,"
IEEE Transactions on Communications
39
(1)
DOI : 10.1109/26.68285
Pecorella T
,
Fantacci R
,
Lasagni C
"Study and Implementation of Switching and Beam-Hopping Tchniques in Satellites with On Board Processing,"
International Workshop on Satellite and Space Communications (IWSSC'07)
2007
206 -
210
Anzalchi J
,
Couchman A
,
Gabellini P
"Beam hopping in multi-beam broadband satellite systems: System simulation and performance comparison with non-hopped systems,"
2010 5th Advanced satellite multimedia systems conference (asma) and the 11th signal processing for space communications workshop (spsc)
2010
248 -
255
Fonseca N J G
,
Sombrin J
2012
"Multi-beam reflector antenna system combining beam hopping and size reduction of effectively used spots,"
IEEE Antennas and Propagation Magazine
54
(2)
88 -
99
DOI : 10.1109/MAP.2012.6230720
Tao M
,
Liang Y C
,
Zhang F
2008
"Resource allocation for delay differentiated traffic in multiuser OFDM systems."
IEEE Transactions on Wireless Communications
7
(6)
2190 -
2201
DOI : 10.1109/TWC.2008.060882
Xiong C
,
Li G Y
,
Zhang S
2012
"Energy-efficient resource allocation in OFDMA networks,"
IEEE Transactions on Communications
60
(12)
3767 -
3778
DOI : 10.1109/TCOMM.2012.082812.110639
Citing 'On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case
'
@article{ E1KOBZ_2015_v9n3_921}
,title={On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case}
,volume={3}
, url={http://dx.doi.org/10.3837/tiis.2015.03.005}, DOI={10.3837/tiis.2015.03.005}
, number= {3}
, journal={KSII Transactions on Internet and Information Systems (TIIS)}
, publisher={Korean Society for Internet Information}
, author={Han, Han
and
Xu, Yuhua
and
Huang, Qinfei}
, year={2015}
, month={Mar}
TY - JOUR
T2 - KSII Transactions on Internet and Information Systems (TIIS)
AU - Han, Han
AU - Xu, Yuhua
AU - Huang, Qinfei
SN - 1976-7277
TI - On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case
VL - 9
PB - Korean Society for Internet Information
DO - 10.3837/tiis.2015.03.005
PY - 2015
UR - http://dx.doi.org/10.3837/tiis.2015.03.005
ER -
Han, H.
,
Xu, Y.
,
&
Huang, Q.
( 2015).
On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case.
KSII Transactions on Internet and Information Systems (TIIS),
9
(3)
Korean Society for Internet Information.
doi:10.3837/tiis.2015.03.005
Han, H
,
Xu, Y
,
&
Huang, Q
2015,
On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case,
KSII Transactions on Internet and Information Systems (TIIS),
vol. 3,
no. 3,
Retrieved from http://dx.doi.org/10.3837/tiis.2015.03.005
[1]
H Han
,
Y Xu
,
and
Q Huang
,
“On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case”,
KSII Transactions on Internet and Information Systems (TIIS),
vol. 3,
no. 3,
Mar
2015.
Han, Han
and
,
Xu, Yuhua
and
,
Huang, Qinfei
and
,
“On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case”
KSII Transactions on Internet and Information Systems (TIIS),
3.
3
2015:
Han, H
,
Xu, Y
,
Huang, Q
On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case.
KSII Transactions on Internet and Information Systems (TIIS)
[Internet].
2015.
Mar ;
3
(3)
Available from http://dx.doi.org/10.3837/tiis.2015.03.005
Han, Han
,
Xu, Yuhua
,
and
Huang, Qinfei
,
“On-demand Allocation of Multiple Mutual-compensating Resources in Wireless Downlinks: a Multi-server Case.”
KSII Transactions on Internet and Information Systems (TIIS)
3
no.3
()
Mar,
2015):
http://dx.doi.org/10.3837/tiis.2015.03.005