Efficient Scheduling and Power Allocation for D2D-assisted Wireless Caching Networks

I. INTRODUCTION

• Caching popular files on user devices can serve peak-period requests without heavily relying on backhaul or costly low-power base-station deployment.Source: §I · p. 2
• Unlike cluster-based, the model allows any two close users to form a D2D link when the requested file is cached, and uses scheduling and fair power allocation to manage interference.Source: §I · p. 5
• The non-convex throughput-maximization task is decomposed into scheduling as many links as possible, then allocating power to maximize their minimum transmission rate.Source: §I · p. 5
• Both scheduled D2D-link count and system throughput improve with Zipf caching and the proposed algorithms versus caching schemes and scheduling algorithms in [25] and.Source: §I · p. 5

II. SYSTEM MODEL

• Users independently cache files according to Zipf popularity; an uncached request can use a nearby helper holding the file, selected for highest rate or SINR, or the BS.Source: §II · pp. 6–7
• Zipf caching is a heuristic rather than generally optimal; the paper simplifies presentation to one file and leaves optimal caching for the general model beyond scope.Source: §II · p. 7

III. PROBLEM FORMULATION AND ANALYSIS

• The joint problem is non-convex and computationally difficult, motivating a suboptimal decomposition into link scheduling and power allocation.Source: A. Problem Formulation · p. 9
• The scheduling subproblem seeks the largest link set satisfying SINR and transmit-power constraints, while power allocation seeks to maximize the scheduled links’ minimum rate.Source: A. Problem Formulation · p. 9, 1) D2D Link Scheduling Problem · p. 9
• The decomposition is not optimal, and finding an optimal decomposition is left as future work.Source: 1) D2D Link Scheduling Problem · p. 9

1) D2D Link Scheduling Problem:

• More scheduled links can reduce throughput through added mutual interference, so the scheduling coefficient tightens SINR requirements to favor stronger channels and weaker interference.Source: 1) D2D Link Scheduling Problem · p. 10
• Increasing any scheduled link’s SINR requirement increases each transmit power and leaves the scheduled-link count unchanged or lower.Source: 1) D2D Link Scheduling Problem · p. 10
• The scheduled receiver set and its corresponding D2D links and SINR vector are outputs of the scheduling subproblem, with a corresponding power-allocation vector.Source: 1) D2D Link Scheduling Problem · p. 10

2) Optimal Power Allocation Problem:

• The optimal power-allocation subproblem maximizes the minimum transmission rate for the scheduled links, subject to their transmit-power constraints.Source: 2) Optimal Power Allocation Problem · p. 11, C. Analysis of Subproblem (P3) · p. 12

B. Analysis of Subproblem (P2)

• Problem (P2) is NP-hard, and unlike regular admission control, candidate links may share users, so scheduled links must satisfy a no-shared-user constraint.Source: B. Analysis of Subproblem (P2) · pp. 11–12

C. Analysis of Subproblem (P3)

• After scheduling determines the link set, problem (P3) is a feasible max-min optimization over D2D transmit powers, for which the paper develops an optimal power-allocation algorithm.Source: C. Analysis of Subproblem (P3) · p. 12

IV. D2D LINK SCHEDULING

• The scheduling method divides dependent candidate links into independent groups, solves each group for links meeting both constraints, and selects a suboptimal solution.Source: §IV · pp. 12–13

A. Potential D2D Links Division

• The link groups are formed through edge coloring: an iterative algorithm colors graph edges in successive maximum matchings, with each color representing a link set whose links do not share users.Source: A. Potential D2D Links Division · pp. 13–14

B. CPC Algorithm

• After link grouping ensures C1, the CPC algorithm checks whether each group satisfies C2, the minimum-SINR feasibility condition.Source: B. CPC Algorithm · pp. 14–15
• The BS collects channel gains and minimum SINR requirements, calculates the required powers, and accepts the group only if every calculated power is within its transmitter’s limit.Source: B. CPC Algorithm · pp. 15–16
• Unlike DCPC, CPC performs the calculation centrally at the BS rather than iteratively adapting transmitter powers until convergence.Source: B. CPC Algorithm · pp. 15–16

C. Removal Algorithm

• When CPC finds a link’s required power exceeds its maximum, the algorithm removes a link likely to cause the strongest interference or receive the strongest interference, repeating until the remaining links satisfy C2.Source: C. Removal Algorithm · pp. 16–17
• The removal rule uses relative interference and maximum-power information, whereas DCPC-based removal uses converged power and absolute interference; the paper reports its rule outperforms DCPC-based removal.Source: C. Removal Algorithm · p. 17

D. Scheduling Algorithm and Complexity Analysis

• Algorithm 2 combines iterative edge coloring, CPC, and removal; its reported complexity is dominated by the edge-coloring and CPC computations.Source: D. Scheduling Algorithm and Complexity… · pp. 17–18
• The scheduling algorithm colors links, applies CPC, removes links from infeasible groups, and schedules the group with the largest remaining link count.Source: D. Scheduling Algorithm and Complexity… · pp. 17–18

• The solution of (P2) supplies the scheduled D2D links and their receiver set for the power-allocation stage.Source: §V · p. 18
• Problem (P3) seeks to maximize the scheduled links’ minimum transmission rate or SINR without compromising their number.Source: §V · p. 18
• The section analyzes the optimal solution, develops a binary-search-based allocation algorithm, and examines its computational complexity.Although (P3) can be transformed into a convex problem and solved with a convex optimization toolbox, the authors pursue an analytical solution to clarify optimal power allocation.Source: §V · p. 18

A. Binary-search based Power Allocation

• The algorithm maximizes the minimum SINR by raising the lowest constrained links together in stages, stopping when transmit-power limits would be violated.With ordered initial SINRs, it first raises the lowest link toward the next value, then raises the lowest group together toward the following value.Source: A. Binary-search based Power Allocation · p. 19
• Theorem 3 orders the initial SINR constraints and defines a vector that raises the first m link SINRs to a common value.Source: A. Binary-search based Power Allocation · p. 19
• When power limits permit the allocation at the current threshold but not the next, the optimum lies between those thresholds for the first m links.The theorem’s condition compares required powers with the scheduled links’ initial power vector and maximum-power vector.Source: A. Binary-search based Power Allocation · pp. 19–20
• Because the optimal SINR vector is unknown to the BS, binary search approaches it between feasible SINR vectors subject to transmit-power constraints.The algorithm summarizes this procedure as binary-search-based power allocation.Source: A. Binary-search based Power Allocation · p. 20

B. Complexity Analysis

• The first loop has at most k_D rounds in the worst case, with each round calculating a power vector through matrix inversion and multiplication.Source: B. Complexity Analysis · pp. 20–21
• The second loop uses O(log φ) binary-search rounds, with each round’s cost dominated by calculating the power vector.The passage reports the per-round calculation as O(k2.373_D).Source: B. Complexity Analysis · p. 21
• The authors report the overall complexity of Algorithm 3 as O(k3.373_D).Source: B. Complexity Analysis · p. 21

VI. NUMERICAL RESULTS

• The simulations use a 1-km-square cell, 1,000 files, 1-MHz D2D bandwidth, 20-dBm maximum transmit power, and equal minimum acceptable SINRs.The reported model also uses the same minimum acceptable SINR, vT, at all scheduled D2D receivers.Source: §VI · p. 22, Figure 2 · p. 22
• The optimal help distance declines as K grows; at K=100, kS+kD peaks near r=0.33 km before greater distance raises interference.Initially, a larger r increases potential D2D links; continued growth increases transceiver distance and transmit power.Source: Figure 3 · p. 22, §VI · p. 23, Figure 4 · p. 23
• The optimal caching coefficient is smaller than in, and it is small when γr is small because users request more distinct files.A smaller coefficient lets users cache more different files for D2D transmissions.Source: §VI · p. 24, Figure 5 · p. 24
• The proposed CPC scheduler selects between the exhaustive-search optimum and DCPC [32], with exhaustive search limited to few potential D2D links.The comparison uses a small help distance because exhaustive search is computationally costly when the potential-link count is large.Source: §VI · p. 24, Figure 6 · p. 25
• Binary-search power allocation nearly matches the convex-toolbox optimum and improves throughput by more than 40% over minimum-SINR allocation.The max-min-fair allocation achieves perfect fairness, while throughput can rise further if some unfairness is tolerated.Source: §VI · pp. 25–26, Figure 7 · p. 25
• Increasing cs reduces scheduled links but raises throughput; around 4–6 dB, the proposed algorithms outperform on both measures.The text gives cs = 5 dB as an example and reports the two-metric comparison across different vT settings.Source: §VI · pp. 26–27, Figure 8 · p. 26, Figure 9 · p. 27
• The proposed algorithms outperform [25] and in scheduled D2D links, kS+kD, and system throughput across different user counts.Figure 10 compares these three measures; its algorithms use the specified caching, scheduling, and power-allocation schemes.Source: §VI · pp. 27–28, Figure 10 · p. 28
• The proposed algorithms reduce average download time relative to both comparison algorithms, alongside serving more users from memory or D2D helpers.Figure 11 compares download time; the text attributes the reduction to more users obtaining files locally or through D2D.Source: §VI · pp. 28–29, Figure 11 · p. 29

VII. CONCLUSIONS AND FUTURE DISCUSSIONS

• The proposed Zipf caching, D2D scheduling, and power allocation improve both the number of scheduled links and system throughput compared with the state of the art.The scheduling step increases the number of links meeting SINR and transmit-power constraints; power allocation maximizes their minimum transmission rate.Source: §VII · p. 29
• The optimized Zipf-distribution caching scheme is not generally optimal, and finding the optimal caching distribution for the general model is difficult and beyond this paper’s scope.The scheduling and power-allocation algorithms can be used with any caching scheme.Source: §VII · p. 30
• The algorithms are described for one channel, but the paper says they can also be used in multi-channel systems such as FDMA and TDMA.Links are iteratively scheduled in a frequency band or time slot.Source: §VII · p. 30
• Both algorithms are centralized at the BS, which must track cached content and collect channel-state information across potential D2D links.Developing decentralized scheduling and power-allocation algorithms is identified as future work.Source: §VII · p. 30

A. Proof of Theorem 1

• Theorem 1’s proof is divided into showing that increasing any scheduled link’s SINR raises each scheduled transmit power and that the scheduled-link count stays constant or decreases.The second property follows by considering whether the increased powers remain within their maximum constraints.Source: A. Proof of Theorem 1 · p. 30, 1) Proof of part I in Theorem 1 · p. 31, 2) Proof of part II in Theorem 1 · p. 31

1) Proof of part I in Theorem 1:

• For part I of Theorem 1, maintaining other links’ SINRs after one SINR rises requires increasing their transmit powers.The passage states that each scheduled transmit power increases when any scheduled-link SINR increases.Source: 1) Proof of part I in Theorem 1 · p. 31

2) Proof of part II in Theorem 1:

• For part II of Theorem 1, the number of scheduled links remains unchanged if the increased powers meet their maximum constraints; otherwise, a link can become infeasible and the count falls.The proof considers the power increase needed to satisfy the minimum SINRs.Source: 2) Proof of part II in Theorem 1 · p. 31

B. Proof of Theorem 2

• Problem (P2) is NP-hard because it includes regular admission control as a special case when no two scheduled D2D links share users.The passage states that regular admission control with QoS constraints is NP-hard.Source: B. Proof of Theorem 2 · p. 31

C. Proof of Theorem 3

• Theorem 3’s proof begins with a case where the power constraints hold at one SINR threshold but not at the next, and then considers a second case.In the first case, the proof considers optimal SINRs with v̄_m ≤ v* ≤ v̄_{m+1}.Source: C. Proof of Theorem 3 · p. 32

2) Proof of the First Case:|

• A contradiction argument perturbs one link’s power and SINR against the others to rule out unequal optimal SINRs among the first m links.The proof describes small power and SINR adjustments that preserve the constraints.Source: 1) Proof of the First Case:| · pp. 32–33
• The proof aims to show that the first m optimal SINRs are equal and the remaining scheduled links retain their minimum SINR constraints.It frames the objective as minimizing the maximum reciprocal SINR among the first m links.Source: 1) Proof of the First Case:| · pp. 32–33
• The power constraints ¯P ⪯ P(V(m)(¯v_m)) ⪯ Pmax hold at ¯v_m, but ¯P ⪯ P(V(m)(¯v_{m+1})) ⪯ Pmax does not hold at ¯v_{m+1}.Source: 1) Proof of the First Case:| · p. 32

2) Proof of the Second Case:

• The proof of the second case follows the same approach as the first case.The authors omit its details for page limit.Source: 2) Proof of the Second Case · p. 33