A Local-Ratio-Based Power Control Approach for Capacitated Access Points in Mobile Edge Computing

The problem of resource allocation has been paid much attention in various fields, and it has many different optimization objectives. Furthermore, resource allocation problems are usually NP-hard problems, and how to get satisfactory results in a short time is a considerable challenge. Aiming at social welfare maximization, reference (Zhang et al., 2022) proposed an auction mechanism for resource allocation in the Cloud Edge collaboration framework based on live video webcast services. Reference (Liu et al., 2018) addressed the problem of heterogeneous physical machines resource management (HPMRM) in heterogeneous clouds. Trade-offs between energy and performance are important for energy-aware scheduling. In reference (Li et al., 2019), a polynomial-time algorithm was designed for energy-aware profit maximizing scheduling problem.

MPCC is a fundamental minimum power coverage (MPC) problem that has been extensively studied in the past two decades. Originally, the problem was introduced for modeling the power control problem in the communication of edge computing. Broadly, MPCC belongs to the family of minimum weight set cover (MWSC) problems. MPCC can be viewed as a special variant of the MWSC that has the following general formulation: Given a universe $E$ of elements (points or terminal devices) and a family ${\mathcal{G}}$ of ranges (or geometric objects like disks and polygons) where each range has a weight assignment $w:\mathcal{G}\mapsto{\mathbb{R}^{+}}$, determine a set $\mathcal{F}\subseteq\mathcal{G}$ of ranges such that every element in $E$ is covered by at least one range in $\mathcal{F}$ and that the total weight $\sum\nolimits_{G\in\mathcal{F}}{w(G)}$ is minimized. Clearly, MPCC can be formulated as a special MWSC, where $\mathcal{G}$ is the set of all possible disks centered at some APs having at least one TD on their boundaries. The difference is that the capacity of each $a\in A$ is limited to $k(a)$; therefore, the capacity of the disk centered at $a$ in $\mathcal{G}$ is also constrained.

The MWSC problem is, in general, challenging to solve optimally, even for some simple versions. For example, Alt et al. and Bilò et al. present a minimum cost covering problem without capacity constraint in (Alt et al., 2006; Bilò et al., 2005), which is still NP-hard for any $\alpha>1$. Thus, finding polynomial time approximation algorithms is the main objective for MPCC problems.

For the geometric minimum weight set cover problem, it was studied from different aspects. For the minimum disk cover problem, in which disks may have different sizes, Mustafa and Ray designed a PTAS using a local search method (Mustafa and Ray, 2010). Considering weight, Varadarajan (Varadarajan, 2010) presented a clever quasi-uniform sampling technique that was improved by Chan et al. (Chan et al., 2012), yielding a constant approximation for the minimum weight disk cover problem. About partial cover problem, Liu et al. (Liu et al., 2021) introduced the $k$-prize-collecting minimum power cover problem ($k$-PCPC), and present a novel two-phase primal-dual algorithm and got an approximation ratio of at most $3^{\alpha}$. The author then introduced the minimum power cover problem with submodular and linear penalties in (Liu et al., 2022) and presented a combinatorial primal-dual $(3^{\alpha}+1)$-approximation algorithm.

In previous studies, the minimum power cover problem has rarely been considered for capacity constraints. However, for the vertex cover problem, another research topic of the set cover problem, many studies consider the minimum capacitated vertex cover problem. Consider a graph $G=(V,E)$ with weights and capacities on the vertices. All edges must be covered by vertices under the capacity constraint, and the objective is to minimize the weight. (Guha et al., 2003) give a primal-dual-based approximation algorithm with an approximation guarantee of 2 (every edge has two vertices). The study of the vertex cover problem with hard capacity constraints (VC-HC) was initiated in (Chuzhoy and (Seffi) Naor, 2006). They established a surprising result that, while this setting admits constant factor approximations, it becomes set-cover hard when $\left\{{0,1}\right\}$-weighted vertices are considered. (Kao, 2021) considered VC-HC on hypergraphs. This literature, which considers a hypergraph $G$ with a maximum edge size of $f$, provides an iterative partial rounding technique and obtains an $f$-approximation, improving upon the previous results of (Cheung et al., 2014).

Consider $m$ APs with same capacity and $n$ TDs randomly distributed in 2-dimensional space. Each TD accesses the edge network through its covering AP. Let $(U,A,k)$ be an instance of the MPCC problem with $U=\left\{{1,2,...,n}\right\}$ and $A=\left\{{1,2,...,m}\right\}$, and let $k\in{\mathbb{Z}^{+}}$ denote the capacity of IP to each AP $a\in A$. Each AP $a$ can adjust its own power, and the relationship between the power $p(a)$ and the radius $r(a)$ of its service area is

where $c$ and $\alpha$ are constants ($\alpha$ is usually called the attenuation factor). The center and radius can be used to define a disk, so $a$ and $u\in U$ can determine a unique disk ${D_{au}}$ whose radius is precisely equal to the distance between $a$ and $u$ ($u$ is on the boundary of ${D_{au}}$ in the optimal case). Therefore, at most $mn$ disks must be considered. We denote the set of such disks by $\mathcal{D}$. Each instance corresponds to a $\mathcal{D}$, and we use $D$ to represent any disk in $\mathcal{D}$. The set of disks with $a$ as the center is a subset of $\mathcal{D}$, denoted by $\mathcal{D}(a)$. To simplify the notation, we use $D$ to represent both a disk in $\mathcal{D}$ and the set of TDs contained in D and use $r(D)$ and $p(D)$ to denote the radius and power of disk $D$, where $p(D)=c\cdot r{(D)^{\alpha}}$. The mapping $k(\cdot):\mathcal{D}\mapsto k$ can determine the capacity of $D\in\mathcal{D}$. Notably, $u$ contained in $D$ means that $u$ is within the range of $D$ ($u\in D$ ) and $u$ is covered by $a$ means that $u$ gains an IP of $a$ to access the edge network (the former does not occupy the resources of the corresponding AP). Clearly, the capacity of $D\in\mathcal{D}(a)$ formed by different power strategies of one AP is equal and changes together. Table 1 summarizes the notation for reference.

Fig. 1 shows an instance with three APs and six TDs. The capacities of AP1, AP2 and AP3 are all 2, respectively (the first number in brackets indicates the AP index, the following represents its capacity). The disk formed by AP1 contains TDs 1, 2 and 4, TDs 3,5 is contained by the disk formed by AP2, and TDs 4, 5 and 6 are contained by AP3’s disk. Notably, TD4 and TD5 are contained by two disks simultaneously. Since the capacity of all APs are only 2, TD4 is eventually covered by AP3 and TD5 is covered by AP2.

In practical situations, a TD may locate outside the maximum coverage that all APs can form, or the number of TDs exceeds the total capacity of all APs. We assume that an AP has no upper power limit and that the entire system has enough capacity to cover all the TDs. In this way, we can obtain a scheme covering all TDs through the technique in this paper, which can provide a reference for the later decision on whether to cover some distant TDs. We can also solve the instance where the demand exceeds the capacity by using the method of this paper many times. Therefore, the above two assumptions are reasonable.

For a subset $\mathcal{\bar{D}}$ of $\mathcal{D}$, $\mathcal{\bar{D}}$ is a feasible solution to the MPCC problem and must meet the following conditions:

1. (1)

   Full coverage condition. $\mathcal{C}(\mathcal{\bar{D}})=\bigcup\nolimits_{D\in\mathcal{\bar{D}}}D$ denotes the TDs covered by $\mathcal{\bar{D}}$; then, $\mathcal{C}(\mathcal{\bar{D}})=U$ must be established.

2. (2)

   Limited capacity condition. Since the IP capacity of each AP is limited, the number of TDs covered by an AP must be less than its capacity.

3. (3)

   Power uniqueness. For any $a\in A$, there are $n$ power strategies, but at most one strategy is selected; that is, there is at most one disk with $a$ as the center in $\mathcal{\bar{D}}$.

According to the above three conditions, we can formulate an integer programming model for the MPCC problem. Variable ${z_{D}}\in\left\{{0,1}\right\}$ indicates whether $D\in\mathcal{D}$ is selected; that is, ${z_{D}}=1$ if and only if $D$ is selected. Variable ${y_{uD}}\in\left\{{0,1}\right\}$ indicates whether $u\in U$ is covered by $D$, where ${y_{uD}}=1$ if and only if $u$ is covered by $D$. The following is the integer program:

Constraint (3) corresponds to the full coverage condition, (4) corresponds to the limited capacity condition, and (6) corresponds to the power uniqueness. Constraint (5) is an implicit condition in this integer program. If $u$ is covered by $D$ in the final result set, then $D$ must be selected as the power strategy of its center AP.

In Algorithm 1, we describe the overall logic of the MLR algorithm in the form of pseudocode. Its input is an MPCC problem instance $(U,A,k)$, a set of disks $\mathcal{D}$ and a mapping of power $p$. $\mathcal{D}$ is a candidate set from which a solution is created. After the input, we define some key variables. $d_{D}$ records the number of TDs that $D$ can currently contain (as the algorithm progresses, $d_{D}$ changes). Let ${\hat{k}_{D}}$ denote the capacity of $D$, which is initialized to $k(D)$. This capacity may change with the continuous allocation of TDs. The variable ${\hat{p}_{D}}$ is the power increment of $D$, which is initialized to $p(D)$. We define $l$ as the set of disks finally selected for all APs, where $l_{a}$ is the disk finally selected for $a$, so $l=\bigcup\nolimits_{a\in A}{{l_{a}}}$. Similarly, $C_{a}$ records the set of TDs that are eventually covered by $a$, and $C=\bigcup\nolimits_{a\in A}{{C_{a}}}$. After Algorithm 2, we can obtain the results of $l$ and $C$, and the final result ${\mathcal{\bar{D}}}$ is the set of non-null values in $l$.

In the main loop of Algorithm 2, each iteration calculates the local ratio $e_{D}$ corresponding to $D\in{\mathcal{D}}$ in the current iteration state. On the basis of lemma 2, the disk ${D^{*}}$ that has the minimum local ratio in each iteration satisfies the inequality ${d_{{D^{*}}}}\leq{\hat{k}_{{D^{*}}}}$. When ${D^{*}}$ is selected, we update the value of ${l_{{a^{*}}}}$ to $D^{*}$, where $a^{*}$ is the center of $D^{*}$, and then assign the TDs contained by $D^{*}$ in the current iteration to $a^{*}$ for coverage.

In the second part of the main loop of Algorithm 2, all the relevant variables are updated. If ${d_{{D^{\text{*}}}}}={\hat{k}_{{D^{*}}}}$ in the current iteration, all the disks in $\mathcal{D}$ with $a^{*}$ as the center are removed. If ${d_{{D^{\text{*}}}}}<{\hat{k}_{{D^{*}}}}$, then there are remaining IP resources for $a^{*}$; we remove these disks in $\mathcal{D}$, with $a^{*}$ as the center and a smaller radius, and ${D^{*}}$ itself. For line 12 of Algorithm 2, the power increment of all remaining disks in $\mathcal{D}$ is updated. We remove all the TDs allocated for the current iteration from the related set in the for loop. We also remove all disks from $\mathcal{D}$ where the number of TDs contained in the disk is 0 or its capacity is 0. Finally, $l$ can record the disk for each AP (an AP may not choose any disk).

To further understand the MLR approach, we cite an instance to illustrate the process of it. In Fig. 2, we present an instance of the MPCC problem $(U,A,k)$, where $U=\{1,2,...,20\}$, $A=\{1,2,3,4,5\}$ and $k=5$. For ease of presentation, we abstract all facilities as dots distributed in 2-dimensional coordinates. The larger blue dots represent APs, and the smaller red dots represent TDs, as shown in Fig. 2. The disk drawn as a solid line is the final disk result obtained by the MLR method. The specific power value that each AP should provide can be calculated by the equation $p(a)=c\cdot r{(a)^{\alpha}}$ (in this case $c=1$, $\alpha=2$). The disk drawn as the dotted line is the disk temporarily selected by the MLR method during processing (that is, the value assigned to the variable $l_{a}$ during the algorithm’s execution). There are nine disks in Fig. 2, indicating that the main loop of the MLR method has been executed nine times in total. Next, we will introduce step by step how MLR obtained the results in this instance.

After inputting the instance $(U,A,k)$ and initializing the relevant variables, the algorithm enters the main loop for the first iteration. After calculating the local ratio $e$ of all disks in $\mathcal{D}$, the disk ${D_{3,10}}$ with the minimum local ratio is selected. In this iteration, $l_{3}$ is temporarily assigned as ${D_{3,10}}$, and TD10 is allocated to AP3. We remove ${D_{3,10}}$ from $\mathcal{D}$ and update local ratio of the remaining disks in $\mathcal{D}$ with ${e_{{D_{3,10}}}}$. Because TD10 is covered, at the end of the current iteration, the entire system must be updated. In the following iterations, this process is repeated continuously. According to the iteration sequence, the disks selected for each iteration are ${D_{3,10}}$, ${D_{4,19}}$, ${D_{5,7}}$, ${D_{3,8}}$, ${D_{1,4}}$, ${D_{2,5}}$, ${D_{4,20}}$, ${D_{2,16}}$ and ${D_{1,6}}$. After the algorithm’s main loop ends, the result set of the algorithm is the union of all ${l_{a}},a\in A$, that is, $\mathcal{\bar{D}}=\{{D_{1,6}},{D_{2,16}},{D_{3,8}},{D_{4,20}},{D_{5,7}}\}$. In addition, the coverage information of all APs is also obtained: ${C_{1}}=\{1,3,4,6\}$, ${C_{2}}=\{2,5,15,16\}$, ${C_{3}}=\{8,10,12,14,18\}$, ${C_{4}}=\{19,20\}$ and ${C_{5}}=\{7,9,11,13,17\}$. These TDs, which are simultaneously contained by some disks in $\mathcal{\bar{D}}$, will be covered by the disk selected first. For example, ${D_{3,8}}$ and ${D_{2,16}}$ contain TD8,10 and 12 in Fig. 2. During the algorithm’s execution, ${D_{3,8}}$ is selected before ${D_{2,16}}$, so ${D_{3,8}}$ covers that TD8, 10, 12.

In this experiment, we analyzed the impact of changes in the number of TDs on the MPCC problem. The main foci are the total system power, algorithm execution time, and AP capacity utilization variance. The number of TDs gradually increases from 20 to 500, and all facilities are distributed in an area with a side length of 40. The ratio between the number of TDs and APs is maintained at 25:1, and the capacity of each AP is $k=40$. For the two constants in equation (1), the values are $c=1$ and $\alpha{\text{ = 2}}$. When the number of TDs is greater than 200, the optimal solution of a single instance cannot be obtained within 10 minutes.

Fig. 3(a) shows the variation in the total power of the three algorithms as the number of TDs increases. Except that the power of the three methods is the same when the number of TDs is 20 (there is only one AP at this time), MLR is significantly better than NCA in all other cases. When the number of TDs changes in the range of 20 to 100, the total power of MLR and NCA increases significantly, while the change in OPT is modest because all facilities are randomly and evenly distributed in a fixed-size area. When the numbers of TDs and APs are small, the result of the optimal solution will not produce a large difference in the total power under different conditions. For MLR and NCA, in some cases, the pursuit of local optimization will produce worse results globally. When the number of TDs increases from 100 to 500, the area remains a fixed size. The total power of MLR and NCA changes only slightly, and the total power of MLR actually decreases. When the number of TDs is small (100), their distribution is sparse, and APs require a larger radius to ensure coverage. When the number of TDs is large (500), the distribution of them and the APs is dense. Although more APs are activated, their coverage radii are reduced. Therefore, under the condition of considering only power (not considering the cost of APs) and a dense distribution of TDs, even if fewer APs can cover all the TDs, more APs have reduced power.

Fig. 3(b) shows that the time required to obtain the optimal solution increases exponentially as the number of terminal devices increases. When the scale is small, both MLR and NCA can produce results in a very short time. Since MLR can still produce better results than NCA in 10 s at the maximum scale, this approach is acceptable in actual application scenarios. As shown in Fig. 3(c), in the results of OPT, AP coverage of TDs is more concentrated, while NCA is the most dispersed, and the result of MLR is somewhere in between.

In this experiment, we explored the impact of variations in the capacity of APs under the condition that the numbers of APs and TDs remain stable. Where $m=4$ and $n=100$, all facilities are randomly and evenly distributed in an area with a side length of 40. The capacity of AP $k$ varies from 25 to 100. Clearly, when $k=25$, all APs can just meet the requirements of covering all TDs.

Fig. 4 shows the total system power, execution time and the variance of IP utilization as $k$ changes. MLR’s performance is not as good as NCA when $k=25$, as shown in Fig. 4(a). In highly tight capacity conditions, the MLR method will have more extreme situations, such as the last few TDs being covered by APs that are far away. However, as $k$ continues to increase, the total power obtained by MLR decreases faster. In practical applications, the extreme situation of capacity shortage is a small probability event (if it occurs frequently, it means that additional APs need to be added). MLR shows better performance when there is surplus capacity. From Fig. 4(b), we know that the OPT method consumes a lot of time when capacity is tight. In contrast, the execution time of the MLR method and NCA is not related to $k$. The variance results shown in Fig. 4(c) indicate that the distribution of TDs tends to become more dense as $k$ increases. Thus, when r = 40, selecting a disk with a larger radius that covers more TDS can save more power. Section 4.3 discusses the influence of the number of APs on the variance under the condition of constant $k$.

In the third experiment, we kept the number of TDs $n$ and the capacity of APs $k$ unchanged, with $n=100$ and $k=25$. In this case, as $m$ increases, the total capacity of the entire system also increases. $m$ gradually grows from 4 to 20, and the corresponding total system capacity increases from 100 to 500.

When $m=4$, the system capacity is just sufficient to cover all TDs. In this case, as shown in Fig. 5(a), the results obtained by MLR and NCP are worse than the optimal solution. Notably, the MLR method is not better than NCP because when capacity is incredibly tight, if some TDs are densely distributed around an AP, the MLR method will fill it more quickly and fall into a local optimum. For example, in Fig. 2, after AP3 covers TDs $\{8,10,12,14,18\}$, AP2 has to provide more power to cover the TDs $\{15,16\}$ far away from it. As the number of APs and the total capacity of the system increase, the total power obtained by the three methods decreases. Fig. 5(b) shows that the performance improvement of the MLR method is the most obvious. Fig. 5(c) shows the variance changes of each method. The most obvious is that the coverage schemes of the OPT method are very intensive in all cases. It reaches the maximum value when m=8 (when m=4, n=100, the variance of OPT is still different from that of the other two methods because the total capacity K of the system may be greater than 100).

In this experiment, we kept the number of TDs $n$ and the total system capacity $K$ constant at 100 and 160, respectively. The number of APs $m$ gradually increases from 4 to 20, and $k$ changes accordingly. All facilities are randomly and evenly distributed in an area with a side length of 40. When $m>12$, OPT cannot produce results within 10 minutes.

As shown in Fig. 6(a), the results of MLR are better than those of NCA. As the number of APs increases, the distribution of APs in a fixed-size area becomes denser. Overall, the average radius of APs will be reduced, and the impact of the decreasing radius on the system is greater than that of the number of APs (more disks). As the number of APs increases and the capacity decreases, the variance of IP utilization among APs becomes more similar, as shown in Fig. 6(c). In Fig. 6(b), the variation in the number of APs also has a considerable impact on the execution time of the OPT method. On the contrary, the other two have almost no fluctuations.