S. A. Tegos1, P. D. Diamantoulakis1, D. S. Michalopoulos2, and G. K. Karagiannidis1
1Electrical and Computer Engineering Department, Aristotle University of Thessaloniki, GR-54124, Thessaloniki, Greece
2Nokia Bell Labs, Munich, Germany
With the current advance of the Internet of Things, mobile devices have a significant impact on our lives, such as healthcare, entertainment, daily life, etc. Nevertheless, the successful integration of mobile devices in these applications depends on their capability to execute a massive number of intensive tasks quickly, despite the potentially limited computing resources. Moreover, emerging wireless technologies are characterized by versatile, yet stringent energy efficiency requirements of the deployed devices. A novel paradigm for network decentralization is fog computing, which offers the capability to offload computation-heavy applications, whereas a promising direction to achieve the energy sustainability of the end nodes is based on the utilization of energy harvesting (EH).
Regarding fog computing, it offers the capability to release the mobile devices from heavy computation workloads by offloading tasks to a fog server. Compared with the conventional remote cloud, offloading workload to a fog server reduces the data traffic, the energy consumption of users, and the transmission latency, as it is placed closer to end users. It is noted that the computation offloading can be applied in two ways, i.e. binary and partial offloading [1].
The utilization of the fog computing technique is particularly useful to the real-time execution of computation tasks requested by low-power devices. Therefore, it has received considerable attention in both academia and industry.
Low-cost mobile devices with small battery capacity may obtain satisfactory computation performance by integrating EH techniques into fog computing. When EH is used, energy can be harvested by ambient energy sources, such as wind energy, solar power, human kinetic energy, and ambient radio frequency (RF) signals. Moreover, wireless power transfer (WPT), which utilizes RF signals, is considered an efficient way to increase the battery life of the devices. Specifically, a dedicated RF energy transmitter, which can charge the battery of remote devices, is utilized in this technique. A significant advantage of WPT is that it is controllable in comparison with harvesting from ambient sources. Currently, commercial WPT transmitters can deliver at the order of 10 μW RF power to a larger distance of 10 m, which can provide adequate power for the operation of EH devices [2].
In the existing literature, there are several works that investigate the integration of fog computing and EH. Single EH user fog systems with binary offloading are considered [3, 4]. Furthermore, fog systems consisting of two EH users adopting time division multiple access (TDMA) are examined where the near user operates as a relay for the far user [5, 6]. Moreover, multiuser fog systems adopting TDMA are considered where both binary and partial offloading are utilized [7, 8], whereas nonorthogonal multiple access (NOMA) has also been investigated in similar systems [9].
In this chapter, the integration of fog computing and EH is considered, according to which tasks can either be executed locally or offloaded to a fog server. More specifically, both EH from ambient sources and WPT are examined. Furthermore, a review of resource allocation problems is presented, emphasizing their categorization, comparison, e.g. in terms of a common objective, and the identified challenges. Moreover, some future research challenges are investigated.
In this section, a fog computing system with EH mobile users (MUs) is examined, which is depicted in Figure 8.1. MUs can execute their tasks locally or/and offload them to the fog server. The computing capability of the fog server can improve significantly the computation experience in each MU [10–12].
It is assumed that time is divided into time slots with length T. More specifically, and are used to denote the index sets of MUs and time slots, respectively. The wireless channel is considered to be independent and identically distributed (i.i.d.) block fading. The channel power gain in the tth time slot is denoted as ht, and ht ∼ fH(x), , where fH(x) is the probability density function (PDF) of ht.
We use to represent a computation task of the nth MU, where Ln denotes the input size of the task, which is measured in bits, and denotes the execution deadline. The computation tasks requested at each MU are modeled as an i.i.d. Bernoulli process, i.e. at the beginning of each time slot, there is a task request with probability ρ, while no task is requested with probability 1 – ρ. The variable is used as follows:
i.e. , , . It is assumed that all tasks are delay-sensitive, i.e. their execution deadline is lower or equal to the time slot length and also that no buffer is available for queuing the task requests.
Each MU can either execute the computation tasks locally, and/or offload them to the fog server. However, it is possible that neither of these methods is feasible, i.e. when there is not sufficient energy at the MU and, thus, the task will be dropped.
where and indicate that the task of the nth MU in the nth time slot is executed locally at the tth MU and offloaded to the fog server, respectively, and indicates that the task is dropped. Therefore, the selection of should satisfy the following equation:
and denote the part of the computation task of the nth MU in the tth time slot that is executed locally at the nth MU and offloaded to the fog server, respectively, and indicates the part of the computation task that is dropped. Moreover, (8.3) should be satisfied.
Let X denote the number of central processing unit (CPU) cycles required for the processing of a one bit input. X differs in each application and can be acquired through off-line measurements [13]. Furthermore, Wn = LnX CPU cycles are needed in order for the nth MU to successfully execute the task . The set of the frequencies scheduled for the Wn CPU cycles in the tth time slot is denoted as , which can be implemented by adjusting the chip voltage with dynamic voltage and frequency scaling (DVFS) techniques. Consequently, the delay for the local execution of the computation task requested in the tth time slot at the nth MU is given by
Subsequently, the energy consumption for executing the task in the tth time slot locally at the nth MU can be expressed as
in which denotes the effective energy coefficient that depends on the chip architecture. Furthermore, the CPU-cycle frequencies are considered to be constrained by , i.e.
If a MU offloads a task to the fog server, we assume that adequate computational power is available at the fog server and, thus, the corresponding computation latency is ignored [14–16]. The transmit power of the nth MU is denoted as and it should not exceed the maximum transmitted power pmax.
To this end, considering the existence of multiple users, an access protocol should be adopted in order for the users to transmit their tasks to the fog server. In the existing literature, most of the works consider TDMA due to its simple implementation. Nevertheless, NOMA is also investigated, as it can offer an improved performance compared to TDMA.
where ω denotes the available bandwidth, is the portion of the tth time slot allocated to the nth MU and σ2 is the variance of the equivalent noise at the receiver.
where it is assumed that for fairness reasons.
It is further assumed that the computational complexity is relatively low, thus, if the computation task is executed by the fog server, the execution delay is equal to the time needed for the transmission of the specific task and is given by
where can be the achievable rate adopting either TDMA or NOMA. More-over, the energy consumed by the nth MU for offloading the tasks to the fog server can be expressed as
Fog systems with EH MUs call for redesigned offloading policies, which become more complex than the ones of mobile cloud computing systems. Consequently, an optimal computation offloading strategy should compromise between the computation performance of the current and future tasks, as the battery level in each time slot obtained by the battery level and the consumption in the previous time slot.
Each MU is equipped with an EH circuit, which is capable of harvesting energy from environments such as human kinetic energy, wind energy, and solar power. Each MU is assumed to be powered only by the harvested renewable energy from the EH circuit. To model the EH process, it is assumed that energy packets successively arrive. To this end, let denote the units of energy that arrive at the nth MU in the beginning of the tth time slot. It is assumed that energy packet arrivals in different time slots are i.i.d. with the maximum value of . Even though the i.i.d. model is simple, it captures the intermittent and stochastic nature of the renewable energy processes [17, 18]. In a practical scenario, only a part of the arrived energy can be stored into the battery. In the tth time slot energy will be harvested and stored in the battery of the nth MU and will be available for either computation offloading or local execution starting from the next time slot. Thus, the following equation should be satisfied:
Furthermore, the battery capacity is considered sufficiently large. Moreover, the energy level of the nth MU's battery in the beginning of the tth time slot is denoted as . Without loss of generality, we assume that B0 = 0 and . Furthermore, for the sake of simplicity, energy consumed for purposes other than task offloading and local computation is ignored.
The energy consumed by the nth MU in the tth time slot, denoted as ℰ(Kt, ft, pt), which depends on the selected computation mode, allocated transmit power and scheduled CPU cycle frequencies, is given by
which needs to satisfy the following constraint:
Therefore, the energy level of the nth MU's battery is modified according to the following equation:
The main disadvantage of conventional EH methods is their dependence on ambient energy sources, which are unpredictable and uncontrollable. Subsequently, harvesting energy from intentionally generated RF signals proves to be an interesting alternative. To this end, WPT has attracted growing interest in wireless communication systems. Nevertheless, WPT creates important challenges in the design of communication systems, as a conflict with the information transmission emerges, since nodes cannot receive information and harvest energy simultaneously [19–21]. In this framework, the users deploy the harvested power to sequentially transmit their information utilizing the harvest-then-transmit protocol [22–24], which is also the core idea investigated in the considered system model.
To perform WPT, each MU is equipped with an energy receiver, which is shown in Figure 8.2. In this receiver, the received RF signal is converted to a direct current (DC) signal by a rectifier consisting of a Schottky diode and a passive low pass filter, which is then stored to the battery.
In the considered system model, we assume that in the beginning of each time slot and for time , where an ∈ [0, 1] is the portion of the time slot that is used for EH by the nth MU, the fog server, which is also utilized as base station, transmits power to the nth MU which is utilized by them for EH. The transmitted power by the fog server to the nth MU in the tth time slot is denoted by . In the remaining portion of the time slot with duration 1 − an, the nth MU executes locally its computation tasks or/and offloads them to the fog server. This time allocation is depicted in Figure 8.3. In case that it offloads its tasks to the fog server, the harvest-then-transmit(offload) protocol is utilized.
Depending on the relationship between the harvested energy and the DC signal, two EH models are used in the literature, i.e. the linear EH model and the nonlinear EH model.
It is observed in the above equation that the harvested energy in this EH model is linear with respect to the portion an of the time slot, which is dedicated to harvesting and also to the transmitted power.
where denotes the maximum harvested power of the nth user in the t- th time slot considering the EH circuit is saturated. Moreover, A is a positive constant, which reflects the nonlinear charging rate with respect to threshold. Given the EH circuit, the parameters , A, and B can be determined by the curve fitting.
In the existing literature, some tradeoffs are investigated mainly in the form of optimization problems. Two characteristic examples are presented in this section, i.e. the tradeoff between the energy consumption and the latency and the one between the execution delay and the task dropping cost.
The tradeoff between the energy consumption and the latency is discussed in [8]. More specifically, a multiuser fog system with WPT is investigated. Also, TDMA and partial offloading are deployed. The aim of the formulated optimization problem in this work is the minimization of the energy consumption at the fog server considering both the energy consumption for computation and for WPT, assuring that the N users' computation tasks are successfully executed. The energy consumption is minimized with the optimization of the number of offloaded bits, the local CPU frequencies and the time allocation among all users. The local computing latency and the EH constraints are also taken into account.
The problem is optimally solved by standard convex optimization techniques and some interesting conclusions are extracted. First, if the EH constraint is not tight for a user, i.e. this user harvests adequate wireless energy and should compute all the tasks locally. Moreover, it is always beneficial to process some bits locally, which means that offloading all of them to the fog server is not optimal. Furthermore, the more stringent the EH constraint is, the more bits should be offloaded to the fog with a smaller rate, as more time should be allocated for EH. Also, adopting NOMA instead of TDMA in the considered system may be able to improve the system performance [9]. Finally, using the more practical nonlinear EH model, described in (8.17), instead of the ideal linear one, may result in worse performance and higher complexity optimization problem and, thus, it would be an interesting challenge.
In fog computing systems without EH, a key metric to evaluate the performance is execution delay, which is also utilized for the optimization of the offloading policy of the considered system [14, 16, 31–33]. However, taking into account the stochastic and intermittent nature of the harvested energy, some of the requested tasks cannot be executed and, thus, they are dropped. This phenomenon occurs when the MU has harvested a small amount of energy, because of the fading in the wireless channel between the fog server and the mobile device. In [3], where the considered system consists of the fog server and one MU, a new useful metric, namely execution cost, has been introduced. It is expressed as the weighted sum of the task dropping cost and the execution delay. Taking into account the fact that some tasks may be dropped, each dropped task is penalized by a unit of cost. Considering the earlier, the execution cost in the tth time slot is given by
where ϕ (in seconds) denotes the weight of the task dropping cost, l(·) is the indicator function, and is given by
Moreover, it is assumed that the successful execution of a task is preferred to dropping a task, i.e. . Binary offloading is also deployed. Furthermore, a task, which is decided to be executed, should be completed before the deadline , which means that the following equation should be satisfied:
Therefore, considering the earlier definitions and assumptions, the aim of the optimization problem is the minimization of the sum of the execution costs in all time slots. Regarding the constraints of the problem, neither fog server execution nor local execution should be performed, unless there is a task request i.e.,
Moreover, in each time slot, the amount of consumed battery energy cannot exceed either Emax, which is necessary for limiting the overdischarge of the battery [34], or the battery energy level in the specific time slot Bt, . Furthermore, the whole amount of the arrived energy cannot be harvested and only a part of it is stored, which means that
Also, the transmit power and the CPU-cycle frequency are positive values and cannot exceed pmax and , respectively. Finally, it should be considered that the computation mode indicators are binary variables, because binary offloading is assumed and (8.3) should be satisfied.
A Lyapunov optimization framework is used to solve the above optimization problem, according to which an algorithm is deployed that dynamically computes the optimal offloading policy. The proposed algorithm asymptotically achieves the optimal performance of the optimization problem. However, the optimal solution is achieved at the price of slow convergence and a higher battery capacity requirement. Hence, we can balance the system performance and the required battery capacity/convergence time, by adjusting the control variables.
The integration of EH and WPT in fog computing is a topic that has attracted a lot of interest recently. Although some useful contributions have been made in this direction, there are still several research challenges that need to be addressed.
In practical systems, a large number of offloading tasks may lead the fog server to overloading, i.e. to a point that its computing power has to be allocated among the received offloading tasks. Subsequently, not only the task offloading time, but also the computation delay at the fog server should be taken into consideration.
Moreover, it is useful to extend EH fog systems to fading channels. It should be noted that it is not necessary to locally compute or offload its tasks in each time slot. In this case, it can be preferable for a MU to remain idle in some time slots and solely save the received energy in its energy storage device. This approach would result in a more complicated analysis, as the time allocation problem would be high dimensional.
Another challenge can be cooperative fog EH systems consisting of more than two users. To this end, users can be allowed to share both the radio and the computing resource. In other words, the users with higher computation power can assist weaker users to execute their tasks. In such systems, the optimization is more complicated, as the energy consumption for executing tasks for other MUs and transmitting the results back to them needs to be estimated and compared with that for offloading the tasks to the fog server.
Furthermore, another research challenge is to combine the concepts of WPT and EH utilizing renewable sources by utilizing a power beacon that is co-located with the fog server. The advantage of this deployment is that the limited availability of energy due to the utilization of renewable sources could be mitigated by the controllable transmission of RF signals.
Finally, it is highlighted that the existing works [5–9] that investigate WPT in fog systems consider various idealizing assumptions ignoring the effect of practical constraints, e.g., nonlinear EH characteristics and hardware impairments, which have not been investigated. To this end, nonlinear EH models as the one presented in the previous section can be utilized.
This work was supported by Nokia Bell Labs through the global donation program for Wireless Powered Remote Patient Monitoring (SPRING).