DDPS: Dynamic Differential Pricing-based Edge Offloading System with Energy Harvesting Devices

First of all, a common method is applying the Stackelberg game to address challenges related to resource provisioning and pricing between the MUs and server. Tao $et$ $al.$ [7] utilized a Stackelberg game framework to establish the relationship between MEC server resources pricing and offloading data volume. The authors employed a differential evolution algorithm to seek the optimal pricing strategies. Chen $et$ $al.$ [8] decomposed the multi-resources allocation and pricing problem into sub-problems, constructing Stackelberg games for each sub-problem. The authors proposed an iterative algorithm to find equilibrium prices. Li $et$ $al.$ [9] introduced a novel multi-leader single-follower Stackelberg game, where each leader sets an optimal price based on the computation resources required by followers. Qin $et$ $al.$ [10] modeled the interaction between MEC servers and vehicles as a Stackelberg game, presenting a dynamic iterative algorithm to find Nash equilibrium for pricing determination. Wang $et$ $al.$ [11] framed the interaction between UAV-MEC servers and MUs as a Stackelberg game, developing an arithmetic descent-based MRIG algorithm for computing resource price. Mitsis $et$ $al.$ [12] modeled user data offloading decisions as a non-cooperative game and employed semi-autonomous game methods or fully autonomous reinforcement learning to obtain optimal computing service price. Li $et$ $al.$ [13] formulated the resources management and pricing problem between MEC server and IoT devices as a bidirectional auction game, introducing the EWA algorithm to incorporate artificial intelligence for adaptive learning of optimal price.

A large body of literature has used auction theory to study resource pricing in the context of MEC. Hai $et$ $al.$ [14] addressed the resource allocation challenge between MUs and microclouds. The authors proposed a suitable auction mechanism to determine the price charged by microclouds to MUs. Shen $et$ $al.$ [15] delved into edge cloud pricing issues, introducing an FPTAS auction mechanism to achieve socially optimal welfare. Ng $et$ $al.$ [16] presented a full-payment auction mechanism to incentivize edge devices to actively participate in encoding computational tasks. For this mechanism, the bid from each edge device indicates its CPU capability, influencing the allocation of computational tasks. Wang $et$ $al.$ [17] firstly established the relationship between the resources offered by edge clouds and the charges to MUs in a non-competitive environment. Subsequently, in a competitive environment, the authors designed an online PMMRA auction mechanism, effectively determining the price paid by MUs for the resources provided by MEC servers. Sun $et$ $al.$ [18] proposed two auction mechanisms, DAMB and BFDA, where MUs declare bids when requesting multi-task services, and edge servers collaboratively provide services to MUs. Wu $et$ $al.$ [19] designed an auction mechanism for a MEC system comprising multiple MUs and a service provider. They presented a precise algorithm to maximize social welfare and a perturbation-based randomized allocation algorithm to achieve an approximate (1-$\alpha$) optimal social welfare, demonstrating the effectiveness of their auction mechanism. Ma $et$ $al.$ [20] introduced a TCDA auction mechanism, providing distinct pricing strategies based on critical values and VCG mechanisms for MUs and edge servers. Wang $et$ $al.$ [21] devised an auction pricing strategy where the highest bidder in each round could perform task offloading, confirming the efficacy of this strategy. Su $et$ $al.$ [22] proposed a TCA auction mechanism and verified its effectiveness in addressing resource allocation and pricing challenges.

While existing pricing works often rely on abstract concave utility functions, some literature explores dynamic differential pricing based on MUs’ physical layer parameters, contributing to a more nuanced understanding of resource pricing in MEC systems. Han $et$ $al.$ [23] utilized idle computation resources from parked vehicles in MEC systems, the authors dynamically adjusted price based on the current system state to minimize average costs. Chang $et$ $al.$ [24] employed binary search to find optimal offloading delay to guarantee the processing latency, and dynamically adjusting price within the latency range. Liu $et$ $al.$ [25] proposed unified and differential pricing strategies based on the extent of edge cloud awareness of network information. Seo $et$ $al.$ [1], Liang $et$ $al.$ [26], and Kim $et$ $al.$ [27] determined pricing dynamically based on MU utilization of server computing resources, with different approaches such as linear, quadratic, and profit-maximization formulations.

Although existing pricing schemes yielded excellent success, they still suffer from several issues. Most of these schemes[4, 5, 6, 25, 27] define cost as a fixed optimal value per CPU cycle, resulting in a consistent unit price for each data length unit. That is, the payment amount becomes directly proportional to the data volume, disregarding MUs’ computational demands on the server when multiple users offload and process equal amounts of data and applications. This may result in excessive utilization of computing resources on the server. Some papers [28, 29, 30] fail to consider both the quantity of offloaded data and computing resources usage, instead relying on an abstract concave utility function to uniformly price all MUs seeking server access. In other words, regardless of their specific requirements for offloaded data or computing resources used, all MUs are charged equally to maximize total social welfare. By doing so, this approach leads to reduced server utility and user satisfaction due to its inherent unfairness. From a server perspective with limited computing resources available, it is crucial to consider individual user utilization of these resources. Elastic pricing schemes help alleviate resource over-utilization problems by dynamically adjusting prices based on demand fluctuations.

We assume that the total amount of data per task is $l_{i}$ bit, the amount of offloaded data is $q_{i}$ bit, and the server takes $h$ cycles to process a bit of data. Therefore, the energy consumption of local execution is expressed by the following formula [31].

where $k$ denotes the effective switched capacitance based on the chip architecture, and $F_{loc}$ denotes the CPU capacity of the MU. We also assume that the achievable uplink and downlink transmission rates from the user to the server are $R_{u}$ and $R_{d}$, respectively. Since the data size is different from the original size after execution if the amount of task $q_{i}$ is offloaded to the server, and we denote the ratio as $r$ [32], then, the downlink data is $q_{i}r$. To sum up, the uplink transmission time $t_{up}$ and the downlink transmission time $t_{down}$ are expressed as follows.

Assume that the upload and download transmission power are $P_{u}$ and $P_{d}$, respectively. Based on this, the upload transmission energy consumption $E_{u}$ and the download transmission energy consumption $E_{d}$ are accordingly expressed as follows.

Therefore, the total energy consumption $E_{tot}$ of MU $i$ per time slot $t$ is obtained as follows.

In the meantime, the battery itself cannot supply power to the device for a long time since we assume all MUs are difficult to replace batteries in remote areas. However, energy harvesting devices are deployed as aforementioned, and the energy conversion $E_{h}$ is defined by the following equation.

where $A$ is the area of the solar panel, $H$ is the average amount of solar radiation, $k_{a}$ $\in$ [0, 1] is the correction factor, and $\eta$ $\in$ (0,1) is the efficiency of the solar device. It should be noted that correction factors are added to represent the actual energy absorbed by energy devices due to objective reasons such as weather, shelter, etc. To sum up, the energy surplus $E_{r}$ per time slot $t$ of the device is expressed by the following formulas.

where $E_{b}$ is the battery capacity of MU $i$.

Assume that the task arrival follows Poisson distribution and the probability function is expressed as the following formula.

where $\lambda$ is the task arrival rate and the $N$ is the number of tasks. The average waiting delay $t_{w}$ is calculated as follows.

where $\mu$ is the service rate of the queue which represents the number of tasks in the queue processed per unit time. For the proposed scheme, it is assumed that the task is completed within the maximum delay. So, the average completion time $t_{ave}$ is approximately denoted as the mean value of the maximum delay of all MUs. $t_{ave}$ is derived as follows.

where $t_{req}^{i}$ is the delay requirement to be satisfied by the $i^{th}$ MU, and $F_{i}$ is the server CPU capacity utilized by the $i^{th}$ MU, $F_{t}$ denotes the available CPU capacity of the server. $F_{i}$ and $F_{t}$ are illustrated in subsection $C$ detailedly.

Denote $F_{i}$ as the CPU capacity utilization by the $i^{th}$ MU, and the processing time $t_{p}^{i}$ at the server is shown as follows.

Here, a pricing bidding function is proposed which considers the CPU utilization to set the price per unit time. The principle of defining the bidding function is that the function must be an increasing function [1]. The bidding feature should become more expensive as the user consumes more CPU capacity, and the server should be set at a higher price to ease the pressure on the server as it has fewer available resources. Let $F_{t}$ denote the available server CPU capacity, the unit price is defined as the product of the pressure and the resources consumed, which is illustrated as follows.

where $w$ is the unit price. Finally, the total payment is the product of the price per unit time and the processing time, which is calculated as follows.

where $W_{i}$ is the payment of the $i^{th}$ MU. In addition, a discount strategy exists when the MU uses more server resources, we adopt the logarithmic function²²2The $lg(\cdot)$ function we priced is based on a logarithm with a base of 10, this is because computational resources are usually represented in scientific notation, and which is convenient for calculation. as the price bidding function [8, 1]. Then, the payment $W_{i}$ is expressed as

Here, $d$ should not be smaller than 1 since the payoff is always positive. It is important to note that $W_{i}$ should not be too large as well as $w_{i}$, otherwise, the user pays too much and abandons the task processing, which increases the packet loss rate as well as the corresponding penalty function increases. The penalty function $P$ is defined hereinafter.

For either $q_{i}$ or $F_{i}$, their first partial derivatives are greater than zero, so $W_{i}$ is an increasing function.

The utility function of MU is obtained by subtracting the payment to the edge server from the profit of energy saving by offloading tasks. So, the utility function $U_{user}^{i}$ of the MU is expressed as follows.

Subsequently, the execution latency is modeled, for which a partial offloading model is considered [33]. The MU offloads part of the data and the $l_{i}$ is processed both on the server and locally. To this end, the execution delay is expressed as the higher value between the time taken for offloading $t_{off}$ and the local processing time $t_{loc}$, which is expressed as follows.

The time $t_{loc}$ required for all tasks to be executed locally is shown as follows.

The time consumed for processing the offloaded data is set as the sum of waiting delay $t_{w}$, uplink data transmission time $t_{up}$, processing time on the server $t_{p}$, and downlink data transmission time $t_{down}$.

Since the downlink transmission data is less than the uplink transmission data $q_{i}$, and the time consumed for offloading is expressed as follows.

When the offloading delay exceeds the delay tolerance constraint of the task, then, the task is dropped and the penalty function $P$ of packet loss is given by the following equation [23].

where $M$ is the number of dropped packets and $\gamma$ $\in$ (0, 1) is a weight coefficient. It should be noted that since the discarded tasks do not play a game with the server, the optimal $F_{i}$ cannot be determined. Here, we calculate the $F_{i}$ based on the maximum delay tolerance as the pricing directly.

Aiming to obtain the optimal strategy for the MU, a budgeted energy offloading strategy is proposed based on the pricing strategy of the server. $U_{server}^{i}$ consists of two functions, one is to maximize the residual energy $E_{r}^{i}$, and the other is to minimize the expenditure $W_{i}$. For the former, according to the amount of harvested energy $E_{h}^{i}$, the task is executed locally or offloaded, and then the optimal amount of offloading data $q_{i}^{opt}$ is obtained, which is referred to Lemma 2, Lemma 3, Lemma 4. As a consequence, Eq. (19) is converted into the following optimization problem.

According to Eq. (25), it is an increasing function concerning $q_{i}$, which implies offloading data as little as possible. On the contrary, $W$ is a decreasing function concerning $F_{i}$, which indicates the selection of the minimum computing resources. However, fewer computation resources required lead to longer computing time. Therefore, it is necessary to complete the task within the maximum delay tolerance. To this end, MUs prefer to offload the smallest amount of data and less computing resources to be optimal for them. However, since each MU tends to use fewer server resources, it takes a longer time to complete the task. In addition, it causes slow task turnover and less profit for the server, so the server does not allow each MU to achieve the minimum computing resources to maximize its profit.

To solve the optimal offloading decision problem (i.e., Problem 1), we proposed Algorithm 4 to determine the eligibility of offloading conditions for the user. According to the harvested energy, and considering its maximum task delay and cost factors, the MU decides whether to execute locally or partially offload, and its time complexity is $O(n)$.

In the meantime, we set $y$ as a binary variable, when $y$ equals 1, it means offloading. Otherwise, it means local processing. Then, we can obtain the following expression.

The utility of the edge server, $U_{server}$, is equal to the payment of the user minus the penalty function $P$ to discard tasks, which is expressed as the following equations.

Appropriate bidding function should be made by the server to guarantee its utility as non-negative. Here, the bidding function is treated as a logarithmic function of $f(x)=\lg(F_{i}+d)$ [8, 1]. The input is regarded as the usage rate of the MU at the server. Since the bid function must be larger than 0, and the bid function should be 0 when $F_{i}$ = 0, that is, when the MU is not using the server resources, $d=1$; $F_{i}$ is the optimal offloading decision of the MU. However, when $F_{i}$ is large, the service period profit is correspondingly large, but according to the game rule, MU is not willing to request a large $F_{i}$, and when $F_{i}$ is large, the number of users that can be served will be less. That is, as the penalty function increases the server utility becomes low. Therefore, within an acceptable range of $F_{i}$ to the user, the utilization of server resources is maximized, and server profit is maximized simultaneously. In this case, the optimization problem to maximize the $U_{server}$ based on the optimal policy of the MU is expressed as follows.

To fully utilize the server resources and improve the revenue of the server, we add the restriction that each MU must increase $F_{i}$ from the original to fully use the server resources if idle resources exist. MU takes up the extra resources of the server according to the proportion of their offloaded data. As the MUs occupy more server resources, they have to pay more, which implies the revenue of the server is improved. The justification for such a decision by referring to Appendix A.

The joint optimization Problem 1 and Problem 2 are solved by the proposed Algorithm 2, which determines the eligibility of a MU to be served by the server after offloading and calculates the utility for both the server and the user. At the beginning of each time slot, the server first iterates the tasks in Class 2. If the server meets the computing resources requirement by the task in Class 2, it processes the task. At this time, the server gives an optimal initial payment according to the amount of data offloaded and the required computing resources, otherwise, the task continues to wait. After iterating the tasks in Class 2, it continues to iterate the tasks in Class 1. If the computing resources of the server cannot meet the computing resources requirement by the task in Class 1, the task is forwarded into Class 2 and waits. Since the server iterates over Class 1 and Class 2, the entire process takes $O(2n)$ time. For each MU already in the server, if the server has any remaining computing resources, we adopt a redistribution strategy, it needs to iterate through the array $X_{s}$ again,⁶⁶6$X_{s}$ represents the array of MUs to be served. reallocates computing resources and calculates the execution delay, and the time complexity is $O(n)$. Therefore, the entire time complexity is $O(3n)$.

For the simulation setup, we assume that $\lambda$ of MUs are 0.1, 0.2, 0.3 [1]. To specify the services provided by MEC servers, we consider face recognition applications that can be executed in the edge cloud. For the parameters of delay, we rely on some existing works to get the representative values. Specifically, the transmission delay has a very large variance, and the mean value is assumed to be 100 to 300 ms [37]. The execution delay is set as 500 ms [38]. The local CPU frequency $F_{k}$ for each MU $i$ is uniformly selected from the set {0.1, 0.2, …, 1} GHz, the data size for MU $i$ are uniformly distributed with $l_{i}$ $\in$ [100, 500] KB. Unless otherwise noted, the remaining parameters are uniformly defined in Table II [25].

Fig. 3 exhibits the impact of the edge server computation capacity on average execution latency. The computation capacity is progressively augmented in increments of $1\times 10^{9}$ cycles/slot, up to a maximum of $6\times 10^{9}$ cycles/slot.

As shown in Fig. 3, it is discernible that as the computational capacity of the edge server enhances, there is a concomitant diminution of the average latency across all pricing schemes. When the computing capacity is low, DDPS exhibits a relatively high average delay compared with the other schemes except for uniform pricing. The reason is that according to our Algorithm 4, DDPS selects the smallest $F_{i}$ under the maximum delay to reach the optimal offloading decision, which leads to a long average delay. With the increase of server computing resources, Algorithm 2 initially allocates computing resources to MUs, and if any service computing resources remain, the server reallocates resources to delay-sensitive MUs, which accelerates the process of task execution.

In addition, from the perspective of pricing, in the case of low computing resources of the server, which means each MU obtains low computing resources. Compared with linear pricing and nonlinear pricing schemes, the $log(\cdot)$ function of DDPS pricing is higher, which also suppresses MUs from requesting more computing resources. Similarly, with the increase of computing resources, the $log(\cdot)$ function of DDPS is priced relatively lower, which encourages MUs to request more computing resources to reduce the latency accordingly. For the uniform pricing scheme, no matter how many computing resources are used by MUs, the price is uniform for all MUs, which leads to unfairness to a part of MUs that just need little computing resources. It reveals that when the MU executes tasks locally more, resulting in the highest latency, which accords with the original intention of MEC.

Fig. 4 exhibits the impact of the edge server computation capacity on $U_{server}$. The computation capacity is varied as utilized in Fig. 3.

As shown in Fig. 4, with the increase of server computing resources, the revenue of all pricing schemes increases, and the DDPS scheme has the highest revenue. The utility function ($U_{server}$) of the edge server is used as a substitution for revenue to verify the effectiveness of the proposed scheme, and we run the simulations for 1 minute. The reasons are explained as twofold. On the one hand, DDPS allows each MU to select the least server computing resources under the maximum latency, which means that the server can serve more MUs under the same condition. On the other hand, we implement a resource redistribution strategy, so that the server resources are fully utilized. Existing pricing schemes (e.g., Uniform pricing and Differentiated pricing [25]) mainly focus on optimizing the cost per CPU cycle, consequently, when the amount of data offloaded requires the same number of cycles, each MU dedicates to occupying more server computing resources to reduce execution time, which leads to sub-optimal utilization of server computing resources. Therefore, the proposed DDPS scheme gains more revenue than other existing schemes.

Fig. 5 exhibits the impact of $\lambda$ on the average execution latency. Here, $\lambda$ are set as 0.1, 0.2, and 0.3, respectively. As observed from Fig. 5, an uptick with $\lambda$ leads to a concomitant increase in the average latency across all pricing schemes, and the DDPS outperforms the other schemes in terms of average execution latency. This is because the redistribution strategy of DDPS makes full use of server resources, that is, each MU can get more computing resources to quickly complete the task execution. In addition, compared with linear pricing and nonlinear pricing, our pricing scheme is also conducive to MU offloading due to the lower price, thereby reducing the delay. Compared with the uniform pricing scheme, the superiority of our scheme is proved by Appendix B.

Fig. 6 exhibits the impact of $\lambda$ on $U_{server}$. $\lambda$ are set as utilized in Fig. 5. The results presented in Fig. 6 show that DDPS stably generates the highest revenue with the increase of $\lambda$. Compared with existing schemes, in addition to the high income caused by the redistribution strategy, DDPS also has the advantage of attracting more MUs at a lower price compared with linear and nonlinear pricing. In addition, DDPS allocates the least amount of computing resources to each MU at the beginning, which also serves more MUs. Uniform pricing has low revenue performance due to the lack of fairness in pricing and the lack of a strategy to maximize revenue.

Fig. 7 illustrates the average ratio of service (RoS) for MUs. We define the RoS as a binary value, 1 represents if the MU execution delay requirements are satisfied, and 0 otherwise for each MU [1]. The figure illustrates that as $\lambda$ increases, the RoS of the proposed scheme remains relatively stable, whereas the others exhibit a declining trend. This is because Algorithm 4 of the DDPS scheme allocates the least computing resources under the premise of the maximum delay of each MU to avoid the situation that some MUs cannot be served. Therefore, compared with the strategy that MUs freely occupy server resources in other schemes (i.e., uniform pricing and differentiated pricing), DDPS serves more MUs. Notably, the reduction is particularly large for the uniform and differential pricing schemes as $\lambda$ increases. For both pricing schemes, the rapid decrease is attributed to the fact that as the number of MUs increases, they are more likely to compete for more computing resources, which results in serving fewer MUs. However, for the linear and nonlinear pricing schemes, the price constraints prevent MUs from excessive competition for computing resources, thus their RoS is relatively stable.

In addition, the reason of the RoS value is not 1 is that it includes non-offloading case, because they cannot satisfy their requirements for offloading due to the situation such as insufficient server resources or $q_{i}>l_{m}$.