Dynamic Charging Optimization for Mobile Charging Stations in Internet of Things

The increasing use of Internet of Things (IoTs) has brought more advantages in supplying power to electric vehicles (EVs). With the help of IoTs, EVs can be charged more easily by mobile charging stations (MCSs) compared with the fixed charging stations (FCSs). However, previous works in the management of power supply in FCSs have not been properly applied in MCSs, e.g., dynamic of EV users' arrival and variable power supply from MCSs in IoTs. In this paper, we study how to manage MCSs' supply power in IoTs under the condition that MCSs supply multiple kinds of power. First, considering the randomness of power supply and dynamic of EV users' arrival, we develop the dynamic framework of power supply and the economic model. Then, aiming to maximize the long-term average profits of MCSs, a stochastic optimization problem is formulated to decide the optimal strategy of power management. Based on the Lyapunov optimization theory, a Lyapunov-based online distributed algorithm is proposed to obtain the optimal solutions. Meanwhile, the performance of our proposed algorithm is analyzed and simulation results validate the effectiveness of our proposal.

SECTION I. Introduction

Internet of Things (IoTs) as a new paradigm can connect physical devices, vehicles and other items to Internet without human intervention [1], [2]. The IoTs consist of many interconnected sensors to make the Internet even more ubiquitous and pervasive. These sensors and services are used to collect the real-time data continuously to be published in IoTs. As an important role in IoTs, electric vehicles (EVs) have been widely paid attentions to [3]–​[5]. With the spread application of renewable generation, more and more EVs have currently been applied in urban areas, e.g., photovoltaic (PV) power plants and wind generations.

Due to the limited capacity of batteries, EVs usually need to be charged with low state of charge (SOC). Recently, fixed charging stations (FCSs) have attracted much attentions and been recognized as a convenient approach to supply charge service [6], [7]. However, considering the growing number of EV users, both waiting time and power bill account for a major part of their expenditure. Although some incentive mechanism and power management have been developed, there are still some problems to be solved. For example, the optimal strategy of power management is usually designed based on the static information of EV users, which neglects the randomness of EV users’ arrival. Besides, wireless communication should be optimized for FCSs with the wireless sensor network (WSN) and the heterogeneous network (HetNet) [8]–​[10].

Based on the rapid development of mobile technologies, mobile charging stations (MCSs) have attracted a lot of attentions [11]–​[17]. MCSs are designed to supply better charging service to EV users compared with FCSs [18], [19]. Through the application of IoTs, there are lots of advantages for both MCSs and EV users as follows [20], [21]: i) It is very convenient for MCS to exchange information with EV users and make the optimal decision on the power supply in time. ii) EV users with low SOC will pay little attention to the amount of power in batteries, due to MCS’s flexible mobility. iii) It can reduce the waiting time of EV users to be charged, when EV users can obtain the real-time information from MCSs to avoid the peak time.

Meanwhile, there exist significant challenges in the power distribution approaches for EV users charged by MCS in IoTs [22]–​[24]: i) Limited power supply: As the number of EVs keeps increasing rapidly, the amount of power in MCSs becomes limited to provide each EV user. ii) Different power requirements: EV users may have different interests in the kinds of power supply, considering traditional power and renewable power supplied in each MCS. However, the existing power distribution approaches cannot be efficiently applied by MCSs in IoTs [25]–​[28]. On one hand, the dynamic feature of renewable power needs to be taken into account. On the other hand, the arrival or departure of EV users follows a random distribution which will affect MCS’s decisions on the power management [29], [30]. Therefore, an efficient and fair policy of power management is desired, considering the factors mentioned above.

Motivated by the above discussion, we tackle the stochastic optimization problem of MCSs’ power supply in IoTs, considering the time-varying renewable power supply and EV users’ arrival. Based on the Lyapunov theory, this problem can be solved to minimize the cost of MCSs, while the queue backlog can be stabilized. We propose a Lyapunov-based online distributed algorithm to achieve the optimal solutions. The main contributions of this work are summarized as follows:

• We analyze and design the economic model based on the energy trading between EV users and MCS in IoTs. Two kinds of power supply in each MCS are taken into account, including the traditional power and renewable power. Due to the variable feature of renewable power supply and EV users’ arrival, we develop the dynamic framework state in each MCS.

• In order to reduce MCSs’ cost, we formulate this economic problem as a stochastic optimization problem. Inspired by the Lyapunov theory, this problem is transferred into two subproblems, which can be solved to decide EV users’ power supply and the control power of MCS’s outlets.

• Through the theoretical analysis, the performance of our proposed algorithm is analyzed. Then, based on the proposed Lyapunov-based online distributed algorithm, the optimal solutions can be achieved to minimize MCSs’ cost and stabilize the queue backlog in each MCS.

The rest of this paper is organized as follows. Section II presents a brief overview of the related work. The system model is developed in section III. We propose a Lyapunov-based online distributed algorithm to minimize MCSs’ cost function in Section IV. The simulation results of our proposal are shown in Section V. Finally, the conclusions are provided in Section VI.

SECTION II. Related Work

A. Wireless Communication Technology in Charging Electric Vehicles

With the development of wireless communication technology, more and more research focuses on the power management to improve the quality of service (QoS). Manshadi et al. in [31] presented the short-term operation of charging station by exploiting the relationship between the electricity network and the transportation network. The authors proved that the coordination between the electricity network and the transportation network could mitigate the congestion in the electricity network. Sun et al. in [32] proposed a software defined framework for EV charging networks by jointly considering the wired charging and wireless charging. The results showed that the proposed framework could ensure efficient and stable charging services for EV users. Yang et al. in [33] proposed a wireless navigation system based on EV users’ power consumption, in order to minimize the driving cost. Rao et al. in [34] studied the wireless charging problem based on the proposed scheduling NP-Hard in the wireless sensor network. Eldjalil and Lyes in [35] made a research on the scheduling strategy of EV users’ charging based on the proposed cloud computing algorithm in the cloud communication. By considering a software-defined V2G network, Hu et al. in [36] presented an energy management scheme for charging stations to utilize energy efficiently. The simulation results showed that the proposed scheme achieved delightful performance on global optimization in the V2G network. In order to minimize the cost of charging service and payment in the charging system, Liu et al. in [37] presented a real-time scheduling scheme in the communication. However, the proposed approaches in above works are mostly developed to study the wireless communication and cannot be properly used to study the power scheduling strategy in MCSs, in which the real-time information of EV users are not enough.

B. Power Scheduling Approach for Electric Vehicles

Several power management policies have been designed to study the problem of power supply or consumption in the existing works. As a promising approach, the game-theoretical mechanism has been used to make the optimal strategy for EV users or power retailers. Yoon et al. in [25] adopted the Stackelberg game theory to describe the relationship between power retailers and consumers. Based on both wireless aggregators and road side units (RSUs), Kaur et al. in [38] studied the scheduling problem on how to manage EVs’ discharging and charging, in order to smooth the load in the power grid based on the game approach and the 0/1 knapsack, and stabilized the power grid with the minimal gap between energy demand and supply. Lee et al. in [39] studied the relationship among EV charging stations and designed the supermodular game scheme. Based on the non-cooperative game approach, Tan and Wang in [40] addressed the charging problem to obtain the optimal strategy of power supply. Moreover, the contract-based theory has been designed to study the charging problem. In order to improve the profits of power retailers, Gao et al. in [41] proposed the contract-based incentive mechanism. Besides the approaches mentioned above, artificial intelligence approaches have been developed to decide the power distribution for EV users [24], [42].

In the existing work, the research on the power scheduling approaches with the wireless technology can be divided into two kinds. The first one is to minimize the expenditure of EV users or power retailers, including the waiting time and the delay of power supply [31], [33], [35], [38], [42]. The second is to maximize the profits of EV users or power retailers [25], [39]–​[41]. In order to design the objective function, various variables have been analyzed based on different optimization theories, e.g., the constraints associated with power supply.

The strength of the above approaches is that they can minimize the cost or maximize the profits, where practical variables are taken into account based on the power demand and power supply. At the same time, there are also deficiencies as follows: i) The optimal strategy cannot be directly used in the dynamic conditions, in which neither the randomness of EV users’ arrival nor the dynamic feature of power supply is considered. ii) The optimal strategies in these two approaches are designed to minimize the cost or maximize the profits, respectively, where the finiteness of power supply is neglected. In our work, different from the previous works, we focus on the dynamic information of EV users and the limited renewable power supply, through which a dynamic charging scheme is proposed with MCSs in IoTs.

SECTION III. System Model

In this section, we firstly develop the network model in IoTs. Secondly, the model of charging EVs is designed with constraints. Thirdly, we define the time-varying queue model of power supply in each MCS. At last, the structure of the economic model is elaborated in detail.

A. Network Model

As shown in Fig. 1, we consider that there are many MCSs and several EVs with power demand in IoTs. Sensors in each EV and MCS can continuously sense and collect data, including the amount of power in batteries and locations. When EV users have to be charged with low SOC in batteries, sensors equipped in EVs will transmit these data to base station (BS). Meanwhile, MCSs will also transmit the data related to the power supply service to BS, when there are enough amount of power to be supplied. Then, base station operators (BSOs) will schedule charging service for both EV users and MCSs. Here, the total number of EV users in each MCS is assumed to be known at each time slot, $\forall t \in \mathcal {T}=\{1, {\dots }, T\}$ . We suppose that EV user $j$ can be charged by MCS $i$ , satisfying $\forall j \in \mathcal {K}_{i}=\{1, {\dots }, K_{i}\}$ , $\forall i\in \mathcal {I}=\{1, {\dots }, I\}$ , $K_{i}\triangleq |\mathcal {K}_{i}|$ , $I\triangleq |\mathcal {I}|$ .

FIGURE 1.

System model in IoTs.

B. Model of Charging Electric Vehicles

Assuming that each MCS supplies traditional power and renewable power shown in Fig. 1, the effect of power’s performance on MCSs’ satisfaction is different from each other. Thus, the satisfaction function is formulated as \begin{equation*} U_{j,i}(t)=A_{j,i}\ln (\alpha _{j,i}+\omega _{1}x_{j,i}(t)+\omega _{2}x_{j,i,0}(t)).\tag{1}\end{equation*} Here, $A_{j,i}$ denotes the preset parameter for EV user $j$ . $\alpha _{j,i}$ is a parameter to ensure the satisfaction function nonnegative. $x_{j,i}(t)$ and $x_{j,i,0}(t)$ denote EV user $j$ ’s power demand of renewable power and traditional power in MCS $i$ , respectively. $\omega _{1}$ and $\omega _{2}$ denote the effect of the kind of power supply on MCS’s satisfaction. $\omega _{1}>\omega _{2}$ implies that MCS $i$ prefers supplying renewable power for EV user $j$ .

With consideration of the limited capacity in EV users’ batteries, the relationship between these two kinds of power supply can be formulated as \begin{equation*} x_{j,i,0}(t)=\varphi _{j,i}(t)-x_{j,i}(t),\tag{2}\end{equation*} where $\varphi _{j,i}(t)$ denotes the maximum power demand of EV user $j$ charged by MCS $i$ at time slot $t$ .

Therefore, by substituting (2) into (1), we have \begin{equation*} U_{j,i}(t)=A_{j,i}\ln (\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t)+(\omega _{1}-\omega _{2})x_{j,i}(t)).\tag{3}\end{equation*} Here, based on the limited total power supply, EV users’ power demand will be bounded by the upper limited power supply in MCS $i$ at each time slot. Thus, we have \begin{equation*} \sum _{j=1}^{K_{i}}\bigg (x_{j,i}(t)+\breve {x}_{j,i}(t)\bigg)\leq \sum _{j=1}^{K_{i}}\bigg (x_{j,i}(t)+\delta _{j,i}(t)\bigg)\leq D_{i}(t),\tag{4}\end{equation*} where $D_{i}(t)$ is the total maximum power supply. $\breve {x}_{j,i}(t)$ denotes EV user $j$ ’s power loss with the upper constraint $\delta _{j,i}(t)$ in the process of charging.

Moreover, at each time slot, the limited capacity of batteries in each EV has to be considered when it is charged by each MCS. Namely, the power supply for each EV user cannot enlarge its capacity. Thus, we have \begin{equation*} x_{j,i}'(t)+x_{j,i}(t)\leq G_{j,i,\max },\tag{5}\end{equation*} where $x_{j,i}'(t)$ denotes the rest amount of power stored in EV $j$ ’s batteries. $G_{j,i,\max }$ is the capacity of EV $j$ ’s batteries.

Considering the fairness of power supply for each EV user and the limited renewable power supply, the power supply of renewable power for EV user $j$ should be satisfied by \begin{equation*} 0\leq x_{j,i}(t)\leq s_{j,i}^{\max }(t).\tag{6}\end{equation*} Here, $s_{j,i}^{\max }(t)$ is the maximum power supply for EV user $j$ .

C. Charging Queue Model in Mobile Charging Station

In this power supply system, it is responsible for each MCS to charge EV users based on their power demand so that MCSs can obtain profits. Combing the choice of each EV user, he arrives at each MCS with power demand, which can be seen as a power supply task. Due to the limited number of outlets in each MCS, this workload will be buffered and served in a queue through an approach of First-In-First-Out (FIFO). Let $Q_{j,i}(t)$ denote the queue backlog of EV user $j$ supplied by MCS $i$ at time slot $t$ . The queue model on the power supply of each MCS can be formulated as a dynamic state, which can be denoted by \begin{align*} Q_{j,i}(t+1)=\max (Q_{j,i}(t)-r_{j,i}(t)\tau,0)+x_{j,i}(t),\quad \forall t\geq 0, \\\tag{7}{}\end{align*} where $\tau$ is the time duration. $r_{j,i}(t)$ is the charging rate of outlets. It is powered and controlled by MCS $i$ , denoted by \begin{equation*} r_{j,i}(t)=B_{j,i}\ln (\xi _{j,i}+\varpi _{j,i}d_{j,i}(t)).\tag{8}\end{equation*} Here, both $B_{j,i}$ and $\xi _{j,i}$ are the preset parameters decided by MCS $i$ . $\varpi _{j,i}$ is the weight parameter based on the power consumption $d_{j,i}(t)$ applied to control the charging rate of outlets for EV user $j$ in MCS $i$ at time slot $t$ . Here, all the queues are initially zero, i.e., $Q_{j,i}(0)=0$ , $\forall j\in \mathcal {K}_{i}$ , $\forall i\in \mathcal {I}$ .

D. Economic Model of Mobile Charging Station

In order to improve MCSs’ profits, each MCS tends to minimize its cost besides the investment expense, which is assumed to be composed of two parts. The first part is that each MCS has to pay for power consumption in controlling outlets. The second part considers the satisfaction of EV users’ power demand, which increases with the increase of $x_{j,i}(t)$ . Therefore, the total cost function of MCSs can be formulated as \begin{equation*} C(t)=\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [p_{i}d_{j,i}(t)+\gamma _{j,i}-U_{j,i}(t)\bigg].\tag{9}\end{equation*} Here, $\gamma _{j,i}$ is the fixed investment. $p_{i}$ is the fixed price of control power applied in MCS $i$ ’s outlets.

In this paper, MCSs aim to minimize the average cost function so that MCSs decide the optimal strategy to improve their long-term profits. Therefore, this problem can be formulated as an optimization problem shown by \begin{align*}&\min ~\overline {C}=\lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\}, \tag{10}\\&s.t.~(2)-(9), \\&\overline {Q}=\lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\mathbb {E} \{Q_{j,i}(t)\}< \infty, \qquad \tag{11}\\&\sum _{j=1}^{K_{i}}d_{j,i}(t)\leq d_{i,\max }(t),\quad \forall i\in \mathcal {I}, \tag{12}\end{align*} where (11) is used to ensure the queue backlog strongly stable in (7). (12) means that the total power consumption in all outlets is bounded by $d_{i,\max }(t)$ , which denotes the maximum control power supply.

SECTION IV. Distributed Algorithm Design for Charging Service System

In this section, a dynamic scheme is proposed to transfer the charging problem into two subproblems, through which we can determine power distribution and manage the control power in each MCS. Through our proposed algorithm, we can solve the optimization problem and achieve the optimal solutions.

A. Lyapunov Optimization Scheme for Charging Service

As a promising method, Lyapunov optimization theory is efficient in solving the dynamic problems [43]–​[45]. In this paper, considering the dynamic arrival of EV users with power demand, the Lyapunov drift-plus-penalty method will be further studied to make optimal decisions on the problem of real-time power management.

With few number of outlets in each MCS, EV users have to wait for being charged in a queue. Here, we define that the aggregate queue backlog vector is denoted by ${\mathbf {Q}}(t)=\{Q_{j,i}(t)\,\,| \forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}\}$ based on (7). Thus, the Lyapunov function is formulated as \begin{equation*} L(\mathbf {Q}(t))=\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\frac {1}{2}\mathbf {Q}(t)^ {\mathbb {T}} \mathbf {Q}(t),\tag{13}\end{equation*} where $\mathbf {Q}(t)^{\mathbb{T}}$ denotes the conjugation-transpose of $\mathbf {Q}(t)$ .

Here, $L(\mathbf {Q}(0))=0$ when all of the queues are initially empty, $\forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}$ . Based on (13), we develop the one-slot conditional Lyapunov drift $\Delta (\mathbf {Q}(t))$ as \begin{equation*} \Delta (\mathbf {Q}(t))\triangleq \mathbb {E} \{ {L(\mathbf {Q}(t+1))}-{L(\mathbf {Q}(t))}|\mathbf {Q}(t) \},\tag{14}\end{equation*} where the expectation is taken with respect to the randomness of EV users’ arrival in the queue.

In order to maximize MCSs’ profits and stabilize the queue backlog, we add MCSs’ cost into Lyapunov drift in a slot and design a scheduling scheme to minimize the drift and penalty (cost) problem. We have \begin{equation*} \min _{d_{j,i}(t), x_{j,i}(t)} \{ \Delta (\mathbf {Q}(t))+V\mathbb {E} [C(t)|\mathbf {Q}(t)]\}.\tag{15}\end{equation*} Here, the first part is the growth of queue backlog, and the second part is the expected MCSs’ cost. $V$ is a control parameter used to adjust the tradeoff among the queue backlog constraints.

Therefore, based on the analysis above, this problem can be further rewritten as \begin{align*}&\min _{d_{j,i}(t), x_{j,i}(t)}~\{\Delta (\mathbf {Q}(t))+V\mathbb {E} [C(t)|\mathbf {Q}(t)] \}, \\&\quad \, s.t.~(4)-(15).\tag{16}\end{align*}

B. Performance Analysis

Our objective is to minimize the drift-plus-penalty problem shown in (16), and then we ensure the upper bounds through the following lemma.

Lemma 1:

For each time slot, we have \begin{align*}&\hspace {-0.6pc}\Delta (\mathbf {Q}(t))+ V\mathbb {E} [C(t)|\mathbf {Q}(t)] \\&\,\,\,\quad \leq R+ V\mathbb {E} [C(t)|\mathbf {Q}(t)] +\mathbb {E} \{[\mathbf {X}(t)-\mathbf {r}(t)\tau]^{\mathbb{T}} \mathbf {Q}(t) |\mathbf {Q}(t)\}, \\\tag{17}{}\end{align*} where $\mathbf {X}(t)$ is the vector of EV users’ power supply, denoted by $\mathbf {X}(t)=\{x_{j,i}(t)\,\,| j\in \mathcal {K}_{i}, i\in \mathcal {I}\}$ . $\mathbf {r}(t)$ is the vector of the charging rate of outlets, denoted by $\mathbf {r}(t)=\{r_{j,i}(t)\,\,| j\in \mathcal {K}_{i}, i\in \mathcal {I}\}$ . $R$ is a finite and positive constant, bounded by \begin{equation*} R\geq \frac {\tau ^{2}}{2}\mathbf {r}(t)^{\mathbb{T}} \mathbf {r}(t) +\frac {1}{2}\mathbf {X}(t)^{\mathbb{T}} \mathbf {X}(t).\tag{18}\end{equation*}

Proof:

See Appendix A.

Further, based on Lemma 1, we can obviously know that the left side of (17) is bounded by its right side. We will use the Lyapunov drift-plus-penalty function to minimize the right side of (17) through the following theorem, where $R$ is a constant.

Theorem 1:

Assuming that $\mathbb {E}\{ L(\mathbf {Q}(0)) \}< \infty$ and $C_{opt}$ is the desired target cost, there exist finite and positive constant $R$ , $V$ , and $\epsilon$ such that $\forall t\in \{ 0, 1, {\dots }, T-1\}$ for all time slots. For all queue backlogs $\mathbf {Q}(t)$ , the Lyapunov drift function satisfies \begin{align*} \Delta (\mathbf {Q}(t))+ V\mathbb {E} [C(t)|\mathbf {Q}(t)] \leq R-\epsilon \sum _{i=1}^{I}\sum _{j=1}^{K_{i}}Q_{j,i}(t)+VC_{opt}.\!\! \\\tag{19}{}\end{align*} Then, the average queue backlog growth rate is bounded by \begin{equation*} \overline {Q}\leq \frac {R+V(C_{opt}-\overline {C})}{\epsilon },\tag{20}\end{equation*} and the average cost of MCSs is bounded by \begin{equation*} \overline {C}=\lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\}\leq C_{opt}+\frac {R}{V}.\tag{21}\end{equation*}

Proof:

See Appendix B.

From Theorem 1, we can know that the average cost of MCSs obtained by our proposed algorithm can be adjusted close to the desired target cost $C_{opt}$ through increasing $V$ shown in (21). However, it will increase the delay of all queue backlogs based on the fact that the upper bound is linear with respect to $V$ in (20). The tradeoff between the average cost of all MCSs and queue backlog delay performance can be presented, so that we can control value $V$ to balance the cost-delay performance.

C. Optimal Scheme Design for Mobile Charging Station

Aiming to minimize the right side of (17), an optimal strategy is designed to decide $Q_{j,i}(t)$ with EV users’ power demand as workload and MCSs’ power consumption in controlling outlets at each time slot. Since $R$ is a known constant, the rest terms in (17) can be rewritten as \begin{align*}&\hspace {-1.2pc}VC(t)+[\mathbf {X}(t)-\mathbf {r}(t)\tau]^{\mathbb{T}} \mathbf {Q}(t) \\=&~\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [Q_{j,i}(t)x_{j,i}(t)-VA_{j,i}\ln \bigg (\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t) \\&+\,(\omega _{1}-\omega _{2})x_{j,i}(t)\bigg)\bigg] +\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [Vp_{i}d_{j,i}(t)-\tau Q_{j,i}(t)B_{j,i} \\&\times \,\ln \bigg (\xi _{j,i}+\varpi _{j,i}d_{j,i}(t)\bigg)\bigg]+\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}V\gamma _{j,i}.\tag{22}\end{align*} Through the analysis above, the problem on minimizing the right side of (17) is transferred into two subproblems with respect to $x_{j,i}(t)$ and $d_{j,i}(t)$ , respectively. Therefore, we will study and analyze how to efficiently solve each of them in the following subsection.

Remark:

Based on the statement in this paper, instead of minimizing the right hand of drift-plus-penalty problem (17) directly, we need to minimize the optimization problem in (22), which is a non-convex problem and has a high computational complexity. However, according to the theory of Lyapunov optimization, the objective function is separable from EV users’ power demand variable $x_{j,i}(t)$ and control power variable $d_{j,i}(t)$ of outlets in MCSs ($\forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}$ ) [43]–​[45]. Then, the optimization problem in (22) can be divided into two independent subproblems, through which this non-convex optimization problem is transferred into two convex optimization problems. As shown in (22), the first term of (22) is only affected by the EV users’ power demand variables $x_{j,i}(t)$ , while the second term of (22) is only affected by the control power variable $d_{j,i}(t)$ of outlets in MCSs ($\forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}$ ). Namely, the two subproblems are independent with each other. Since there is no interaction with each other, these two subproblems cannot be jointly addressed. The optimal solutions can be achieved through our proposed algorithm, respectively.

D. Online Distributed Optimization Algorithm

1) Scheduling of Power Supply

Since each MCS is independent of each other, the first term of (22) has no interaction with the others. In order to maximize the profits of MCSs, the problem can be formulated as an optimization problem, shown by \begin{align*}&\max \sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [VA_{j,i}\ln \bigg (\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t) +(\omega _{1}-\omega _{2}) \\&\qquad \qquad \qquad \times \, x_{j,i}(t)\bigg)-Q_{j,i}(t)x_{j,i}(t)-V\gamma _{j,i}\bigg], \\&s.t.~(4)-(6),~x_{j,i}(t)\geq 0.\tag{23}\end{align*} It implies that (23) is a concave function with respect to $x_{j,i}(t)$ , and it is bounded by the linear constraints.

Therefore, based on the multiple constraints in (23), the Lagrange dual decomposition method is used to handle this problem and achieve optimal solutions. The Lagrange function is defined as \begin{align*}&\hspace {-1.2pc}\mathscr {L}(\mathbf {X}(t),\boldsymbol {\varsigma }(t),\boldsymbol {\mu }(t),\boldsymbol {\eta }(t)) \\=&~\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [VA_{j,i}\ln \bigg (\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t) +(\omega _{1}-\omega _{2})x_{j,i}(t)\bigg) \\&-\,Q_{j,i}(t)x_{j,i}(t)\bigg]-\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\varsigma _{j,i}(t)\bigg (x_{j,i}(t)-s_{j,i}^{\max }(t) \bigg) \\&-\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [\mu _{j,i}(t)\bigg (x_{j,i}'(t)+x_{j,i}(t)-G_{j,i,\max }\bigg)+V\gamma _{j,i}\bigg] \\&-\sum _{i=1}^{I}\eta _{i}(t)\left[{\sum _{j=1}^{K_{i}}\bigg (x_{j,i}(t)+\delta _{j,i}(t)\bigg)-D_{i}(t)}\right],\tag{24}\end{align*} where $\boldsymbol {\varsigma }(t)$ , $\boldsymbol {\mu }(t)$ , and $\boldsymbol {\eta }(t)$ denote the set of Lagrange multipliers related to the constraints in (4)–​(6), respectively, i.e., $\boldsymbol {\varsigma }(t)=\{\varsigma _{j,i}(t), \forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}\}$ , $\boldsymbol {\mu }(t)=\{\mu _{j,i}(t), \forall j\in \mathcal {K}_{i}, \forall i\in \mathcal {I}\}$ , and $\boldsymbol {\eta }(t)=\{\eta _{i}(t), \forall i\in \mathcal {I}\}$ .

Then, the Lagrange dual function is given by \begin{align*}&\hspace {-2pc}\mathscr {D}(\boldsymbol {\varsigma }(t),\boldsymbol {\mu }(t),\boldsymbol {\eta }(t)) \\=&~\max \mathscr {L}\bigg (\mathbf {X}(t),\boldsymbol {\varsigma }(t), \boldsymbol {\mu }(t), \boldsymbol {\eta }(t)\bigg) \\=&~\sum _{i=1}^{I}\sum _{j=1}^{K_{i}} \mathcal {L}_{j,i}(t)-\sum _{i=1}^{I}\eta _{i}(t)\left({\sum _{j=1}^{K_{i}}\delta _{j,i}(t)-D_{i}(t)}\right) \\&-\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [\mu _{j,i}(t)\bigg (x_{j,i}'(t)-G_{j,i,\max }\bigg) +V\gamma _{j,i} \\&-\,\varsigma _{j,i}(t)s_{j,i}^{\max }(t)\bigg],\tag{25}\end{align*} where \begin{align*} \mathcal {L}_{j,i}(t)=&~VA_{j,i}\ln \bigg (\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t) +(\omega _{1}-\omega _{2})x_{j,i}(t)\bigg) \\&-\,\bigg (Q_{j,i}(t)+\varsigma _{j,i}(t)+\mu _{j,i}(t)+\eta _{i}(t)\bigg)x_{j,i}(t).\tag{26}\end{align*}

Based on (26), the dual problem can be formulated as the following optimization problem, expressed by \begin{align*}&\min \mathscr {D}(\boldsymbol {\varsigma }(t),\boldsymbol {\mu }(t),\boldsymbol {\eta }(t)), \tag{27}\\&s.t.~\boldsymbol {\varsigma }(t)\geq 0,\quad \boldsymbol {\mu }(t)\geq 0,~ \boldsymbol {\eta }(t)\geq 0. \tag{28}\end{align*}

In order to solve the problem, we firstly take the first derivative of $\mathcal {L}_{j,i}(t)$ with respect to $x_{j,i}(t)$ , given $\varsigma _{j,i}(t)$ , $\mu _{j,i}(t)$ , and $\eta _{i}(t)$ . Then, we have \begin{align*} \frac {\partial \mathcal {L}_{j,i}(t)}{\partial x_{j,i}(t)}=&~\frac {VA_{j,i}(\omega _{1}-\omega _{2})}{\alpha _{j,i}+\omega _{2}\varphi _{j,i}(t)+(\omega _{1}-\omega _{2})x_{j,i}(t)} \\&\qquad \,\,-\,Q_{j,i}(t)-\varsigma _{j,i}(t)-\mu _{j,i}(t)-\eta _{i}(t).\tag{29}\end{align*}

Through adopting the Karush-Kuhn-Tucker (KKT) conditions, we can obtain the optimal solution by solving $\frac {\partial \mathcal {L}_{j,i}(t)}{\partial x_{j,i}(t)}=0$ , and it follows \begin{align*}&\frac {\partial \mathcal {L}_{j,i}(t)}{\partial x_{j,i}(t)}=0 \\&\Longrightarrow x_{j,i}(t)=\frac {1}{\omega _{1}-\omega _{2}}\bigg [\bigg (\frac {VA_{j,i}(\omega _{1}-\omega _{2})}{Q_{j,i}(t)+\varsigma _{j,i}(t) +\mu _{j,i}(t)+\eta _{i}(t)} \\&\,\,\qquad \qquad -\,\alpha _{j,i}-\omega _{2}\varphi _{j,i}(t)\bigg)\bigg]^{+}\!,\tag{30}\end{align*} where [*]⁺ = max[*, 0].

For the dual Lagrange multiples in (24), we use the subgradient method to update them, respectively, which can be denoted by \begin{align*} \varsigma _{j,i}(t)^{h+1}=&~\bigg [\varsigma _{j,i}(t)^{h}+\vartheta _{1}\bigg (x_{j,i}(t)-s_{j,i}^{\max }(t)\bigg)\bigg]^{+}\!, \tag{31}\\ \mu _{j,i}(t)^{h+1}=&~\bigg [\mu _{j,i}(t)^{h}+\vartheta _{2}\bigg (x_{j,i}'(t)+x_{j,i}(t)-G_{j,i,\max }\bigg)\bigg]^{+}\!, \\ \tag{32}\\ \eta _{i}(t)^{h+1}=&~\left[{\eta _{i}(t)^{h}\!+\!\vartheta _{3}\left({\sum _{j=1}^{K_{i}}\bigg (x_{j,i}(t)\!+\!\delta _{j,i}(t)\bigg) \!-\!D_{i}(t)}\right)}\right]^{+}. \\\tag{33}{}\end{align*}

Here, $\vartheta _{1}$ , $\vartheta _{2}$ , and $\vartheta _{3}$ denote the small positive step sizes, respectively. When the step sizes are chosen properly, they can ensure that dual variables $\varsigma _{j,i}(t)^{h}$ , $\mu _{j,i}(t)^{h}$ and $\eta _{i}(t)^{h}$ will converge to the dual optimal value $\varsigma _{j,i}^{*}(t)$ , $\mu _{j,i}^{*}(t)$ and $\eta _{i}^{*}(t)$ . We induce the convergence criteria $||x_{j,i}^{h}(t)-x_{j,i}^{h-1}(t)||/||x_{j,i}^{h-1}(t)||\leq \sigma _{j,i,1}(t)$ , in which $\sigma _{j,i,1}(t)$ is the convergence factor at time slot $t$ . When $\sigma _{j,i,1}(t)$ is satisfied, the initial power supply $x_{j,i}^{0}(t)$ will converge to the optimal solution $x_{j,i}^{*}(t)$ .

2) Control Power Consumption Optimization

In order to realize the fairness of limited renewable power distribution, each MCS should decide the optimal strategy to manage the control power of outlets at each time slot. Thus, based on (22), the problem can be formulated as an optimization problem, shown by \begin{align*}&\max \sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg [\tau Q_{j,i}(t)B_{j,i}\ln (\xi _{j,i}+\varpi _{j,i}d_{j,i}(t))-Vp_{i}d_{j,i}(t)\bigg], \\ \tag{34}\\&s.t.~\sum _{j=1}^{K_{i}}d_{j,i}(t)\leq d_{i,\max }(t),\quad d_{j,i}(t)\geq 0. \tag{35}\end{align*}

Since the objective function of (34) is a convex function and the constraints are all linear, the optimization problem can be solved by the Lagrange dual decomposition. Moreover, based on (34) with its corresponding constraints, the Lagrange function can be described as \begin{align*}&\hspace {-1.2pc}\overline {\mathscr {L}}(\boldsymbol {d}(t), \boldsymbol {\theta }(t)) \\=&~\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\bigg (\tau Q_{j,i}(t)B_{j,i}\ln (\xi _{j,i}+\varpi _{j,i}d_{j,i}(t)) \\&~-\,Vp_{i}d_{j,i}(t)\bigg)-\sum _{i=1}^{I}\theta _{i}(t)\left({\sum _{j=1}^{K_{i}}d_{j,i}(t)-d_{i,\max }(t)}\right),\tag{36}\end{align*} where $\boldsymbol {d}(t)$ and $\boldsymbol {\theta }(t)$ denote the set of control power in each MCS and Lagrange dual multipliers related to the constraints in (35), respectively, i.e., $\boldsymbol {d}(t)=\{d_{j,i}(t), j\in \mathcal {K}_{i}, i\in \mathcal {I}\}$ , $\boldsymbol {\theta }(t)=\{\theta _{i}(t), \forall i\in \mathcal {I}\}$ .

Following (36), the Lagrange dual function can be obtained by \begin{align*} \overline {\mathscr {D}}(\boldsymbol {\theta }(t))=&~\max \overline {\mathscr {L}}(\boldsymbol {d}(t), \boldsymbol {\theta }(t)) \\=&~\sum _{i=1}^{I}\sum _{j=1}^{K_{i}} \overline {\mathcal {L}}_{j,i}(d_{j,i}(t))+\sum _{i=1}^{I}\theta _{i}(t)d_{i,\max }(t).\tag{37}\end{align*} where \begin{align*} \overline {\mathcal {L}}_{j,i}(d_{j,i}(t))=&~\tau Q_{j,i}(t)B_{j,i}\ln (\xi _{j,i}+\varpi _{j,i}d_{j,i}(t)) \\&\qquad \quad~ \qquad -\,Vp_{i}d_{j,i}(t)-\theta _{i}(t)d_{j,i}(t).\tag{38}\end{align*}

Based on (37), the dual optimization problem can be expressed by \begin{align*}&\min ~\overline {\mathscr {D}}(\boldsymbol {\theta }(t)), \tag{39}\\&s.t.~\boldsymbol {\theta }(t)>0, \quad \boldsymbol {d}(t)\geq 0. \tag{40}\end{align*}

Similarly, combing the KKT conditions, the optimal decision on the power control can be obtained by taking the first derivation of (38) with respect to $d_{j,i}(t)$ , which can be given by \begin{align*}&\frac {\partial \overline {\mathcal {L}}_{j,i}(d_{j,i}(t))}{\partial d_{j,i}(t)}=0 \\&\Longrightarrow d_{j,i}(t)=\!\left[{\frac {1}{\varpi _{j,i}}\left({\frac {\tau \varpi _{j,i}Q_{j,i}(t)B_{j,i}}{Vp_{i}+\theta _{i}(t)}\!-\!\xi _{j,i}}\right)}\right]^{+}\!.\tag{41}\end{align*}

The optimal value of $\theta _{i}(t)$ can be decided by solving the problem shown in (34) and (35). Here, a subgradient method is applied to search for the optimal value $\theta _{i}^{*}(t)$ , which is given by \begin{equation*} \theta _{i}(t)^{n+1}=\left[{\theta _{i}(t)^{n}+\vartheta _{4}\sum _{j=1}^{K_{i}}\bigg (d_{j,i}(t) -d_{i,\max }(t)\bigg)}\right]^{+}\!,\tag{42}\end{equation*} where $\vartheta _{4}$ is the small positive step size.

In addition, an online distributed iteration algorithm is proposed to determine the optimal solutions on $d_{j,i}^{*}(t)$ for each EV user in MCSs, through which it can minimize MCSs’ cost shown in (10). In this presented iterative algorithm, we induce the convergence criteria $||d_{j,i}^{n}(t)-d_{j,i}^{n-1}(t)||/||d_{j,i}^{n-1}(t)||\leq \sigma _{j,i,2}(t)$ to achieve the optimal solution. Here, $\sigma _{j,i,2}(t)$ denotes the small convergence factor to obtain precise results. This algorithm is shown in Algorithm 1, which describes the whole procedure of solving the problem in (22).

Algorithm 1 An Online Distributed Scheduling Algorithm

1:

Initialization: Set $\mathbf {Q}(0)$ and ${X}(0)$ , $\boldsymbol {d}(0)$ . Given the initialization $\boldsymbol {\varsigma }(t)$ , $\boldsymbol {\mu }(t)$ , $\boldsymbol {\eta }(t)$ and $\boldsymbol {\theta }(t)$ .

2:

Repeat.

3:

for each time slot $t=0:1:T-1$ do

4:

for $i=1:1:I$ do

5:

for $j=1:1:K_{i}$ do

6:

for $h=1:1:h_{\max }$ do

7:

EV user $j$ in MCS $i$ calculates $x_{j,i}^{h}(t)$ based on (30).

8:

For each EV user in MCS $i$ , the Lagrange multipliers can be updated according to (31)–(33).

9:

end for

10:

Until $||x_{j,i}^{h}(t)-x_{j,i}^{h-1}(t)||/||x_{j,i}^{h-1}(t)||\leq \sigma _{j,i,1}(t)$ .

11:

Output: The optimal solution $x_{j,i}^{*}(t)$ .

12:

for $n=1:1:n_{\max }$ do

13:

The optimal decisions on $d_{j,i}^{n}(t)$ can be obtained based on (41).

14:

MCS will update the Lagrange multipliers $\theta _{i}(t)^{n}$ based on (42).

15:

end for

16:

Until $||d_{j,i}^{n}(t)-d_{j,i}^{n-1}(t)||/||d_{j,i}^{n-1}(t)||\leq \sigma _{j,i,2}(t)$ .

17:

Output: The optimal solution $d_{j,i}^{*}(t)$ .

18:

end for

19:

end for

20:

if $t\geq 0$ then

21:

The queue backlogs $\mathbf {Q}(t)$ will also be updated based on (7).\begin{equation*} \mathbf {Q}(t+1)=[\mathbf {Q}(t)-\mathbf {r}(t)\tau]^{+}+\mathbf {X}(t).\tag{43}\end{equation*}

22:

end if

23:

end for

24:

Output: All of the optimal solutions at each time slot.

SECTION V. Performance Evaluation

A. Simulation Setting

This section evaluates the performance of our proposed Lyapunov-based strategy in this paper. Assuming that the time duration is one hour, we investigate our proposed strategy from 9:00 a.m to 16:00 p.m, i.e., $t\in \{1, {\dots }, 8\}$ . According to [46], we suppose that the total power supply for EV users is distributed in Fig. 2, while the total control power applied in outlets is shown in Fig. 3. Other parameters are set in Table 1 $(i=1, j\in \{1,2\})$ .

TABLE 1 Parameters of Economic Model

FIGURE 2.

Total power supply for all EV users in MCS with variable time.

FIGURE 3.

Total power supply for outlets with variable time.

B. Simulation Results

Based on the parameters set above, we firstly investigate the relationship between the state of queue backlog and the time slots in our proposed scheme. Fig. 4 illustrates the variable procedure of all EV users’ queue backlogs in each time slot. From the results in Fig. 4, we can know that the dynamic optimal decisions are decided to minimize MCSs’ cost based on the different slots, and then the length of all queue backlogs is variable. In addition, from Fig. 4, we can know that all of the queue backlogs are strictly bounded with 1.2, which implies that the queue backlog can be stabilized within a limited value.

FIGURE 4.

Total queue backlogs of all EV users with variable time.

At the same time, following the results in Fig. 4, we investigate the dynamic state of cost in MCS from 9:00 a.m to 16:00 p.m. Combing with Fig. 4, we can observe the minimum cost of MCS shown in Fig. 5 based on (11), which is bounded between 2.6 and 4.2. Since the renewable power is dynamically supplied, different optimal strategies are decided to minimize the cost of MCS in different time slots and stabilize the queue backlog in MCS. Namely, through our proposed strategy, EV users have less delay and the cost of MCS also can be simultaneously minimized based on Fig. 4 and Fig. 5.

FIGURE 5.

Total cost of MCS with variable time.

Further, we study the effect of control parameter $V$ on the average queue backlog of all EV users in MCSs. Combining Fig. 2 and Fig. 3, we obtain the relationship between the average queue backlog $\overline {Q}$ and the variable control parameter $V$ in Fig. 6. From Fig. 6, we can know that $\overline {Q}$ increases with the increase of $V$ , which illustrates the conclusion in (20) based on Theorem 1. It also implies that there exists a proper upper value used to restrain $\overline {Q}$ in Fig. 6. This validates the results that the average queue backlog can be strongly stabilized in Theorem 1.

FIGURE 6.

Average queue backlog of all EV users with control parameter ${V}$ .

Since our proposed algorithm depends on the control parameter $V$ , we investigate the relationship between the average cost of MCS and the control parameter $V$ . Fig. 7 depicts that the average cost of MCS decreases with the increase of $V$ based on (21). At the same time, we can know that the optimum with our proposed strategy is close to the desired target cost $C_{opt}$ , when both $R$ and control parameter $V$ are chosen properly.

FIGURE 7.

Average cost of MCS with control parameter ${V}$ .

Based on the mobility of MCS, MCS can supply charging service to EV users by moving to the location of EV users. Especially, it is convenient for EV users in low SOC to be charged by MCS, when the rest power in EVs is not enough to ensure their arrival at charging stations to be charged. In addition, the peak load shifting of EV users in overload charging stations can be achieved, when EV users can obtain charging service at any place or any time from MCS. It will improve the number of EV users with more profits than that without consideration of the mobility of MCS. Thus, the mobility of MCS can benefit both EV users and MCS. In order to maximize the coverage of MCS’s charging service to reach more EVs, MCS needs to plan its trajectory in a region. At the same time, both EV users and MCS should update the real-time location information to be collected by sensors in EVs for making the optimal decision of MCS’s trajectory.

According to [47] and [48], there is a positive correlation between the driving distance and utility function of EVs. Then, we study the relationship between the average cost of MCS and the mobility based on (10)–(12). Here, the maximum power demand of EV user 1 and EV user 2 are $\varphi _{1,1}=2MW.h$ and $\varphi _{2,1}=1.5MW.h$ , respectively. The control parameter ${V}$ =0.1 is used to balance the cost-delay performance.

From Fig. 8, we can know that the average cost of MCS $\overline {C}$ increases with the increase of the driving distance. Here, we also study the effect of power supply on $\overline {C}$ . In Fig. 8, we can know that $\overline {C}$ decreases with the increase of $\omega _{1}$ , when $\omega _{2}$ is fixed. And $\overline {C}$ decreases with the increase of $\omega _{2}$ , when $\omega _{1}$ is fixed. As the distance increases, the difference among them becomes low. It implies that MCS can make the balance between the mobility and the cost.

FIGURE 8.

Average cost of MCS with different driving distances.

In order to investigate our proposed online distributed scheme, we design a balance ratio to keep balance between the average time-delay performance and the average cost of all MCSs, shown by \begin{align*} F(\mathbf {X}(t),\mathbf {d}(t))=&~(1-g)\lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\mathbb {E} \{Q_{j,i}(t)\} \\&\qquad ~\,\,\,+\,g\lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\},\tag{44}\end{align*} where $g$ is the weight parameter, i.e., $g\in (0,1)$ .

In Fig. 9, we compare the proposed scheme with other approaches, including the approach without online scheme and greedy approach, respectively. Based on the approach without online scheme, MCS makes the optimal decisions on power supply without considering the dynamic of EV users’ arrival at each time slot. In the greedy approach, MCS firstly supplies power to EV users with maximum power demand as much as possible at each time slot. Fig. 9 illustrates the relationship between the balance ratio of MCS in (44) and the control parameter $V$ . It can be obviously known that the balance ratio of MCS in our proposed strategy is smaller than those in other two approaches. Therefore, we obtain the conclusion that the proposal in this paper is more efficient than other schemes.

FIGURE 9.

Comparison of different schemes with variable control parameter ${V}$ .

SECTION VI. Conclusion

In this paper, we have proposed a Lyapunov-based online distributed scheme to make the optimal decisions for MCSs with minimum cost in IoTs, when multiple power supply in MCSs are supplied to each EV user. We formulate this problem as a stochastic optimization problem. Then, we solve this problem and achieve the optimal solutions based on our proposed algorithm. Through the theoretical analysis, the performance of our proposed algorithm is analyzed. Simulation results confirm the effectiveness of our proposal, and the cost of MCSs can be minimized while the queue backlog can be stabilized with less time-delay in MCSs. For future work, it is to analyze the performance when EV users form social community to make interactions for charging. Further, the virtual queue associated with the real-time energy demand of EV users will be analyzed based on the theory of Lyapunov optimization.

Appendix A Proof of Lemma 1

Proof:

In order to prove the results shown in Lemma 1, we use the following inequality as $[\max (\psi -\lambda,0)+\varrho]^{2}\leq \psi ^{2}+\lambda ^{2}+\varrho ^{2}+2\psi (\varrho -\lambda)$ , which holds for any positive parameters $\psi$ , $\lambda$ and $\varrho$ . Thus, based on (7), we have \begin{align*} Q_{j,i}^{2}(t+1)=&~\bigg \{[Q_{j,i}(t)-r_{j,i}(t)\tau]^{+}+x_{j,i}(t)\bigg \}^{2} \\&\hspace {-1pc}\Longrightarrow Q_{j,i}^{2}(t+1)\leq Q_{j,i}^{2}(t)+r_{j,i}^{2}(t)\tau ^{2}+x_{j,i}^{2}(t) \\&+\,2Q_{j,i}(t)[x_{j,i}(t)-r_{j,i}(t)\tau] \\&\hspace {-1pc}\Longrightarrow \frac {Q_{j,i}^{2}(t+1)-Q_{j,i}^{2}(t)}{2}\leq \frac {r_{j,i}^{2}(t)\tau ^{2}+x_{j,i}^{2}(t)}{2} \\&+\,Q_{j,i}(t)[x_{j,i}(t)-r_{j,i}(t)\tau].\tag{45}\end{align*} For all EV users in each MCS at any time slot, (14) can be further rewritten as \begin{align*}&\hspace {-0.6pc}\frac {{\mathbf {Q}(t+1)}^{\mathbb {T}} \mathbf {Q}(t+1)}{2}-\frac {\mathbf {Q}(t)^{\mathbb {T}} \mathbf {Q}(t)}{2} \\&\qquad \leq \frac {\tau ^{2}}{2}\mathbf {r}(t)^{\mathbb{T}} \mathbf {r}(t)+ \frac {1}{2}\mathbf {X}(t)^{\mathbb{T}} \mathbf {X}(t) +[\mathbf {X}(t)-\mathbf {r}(t)\tau]^{\mathbb{T}} \mathbf {Q}(t). \\\tag{46}{}\end{align*} Therefore, substituting (46) into (14), we have \begin{align*}&\hspace {-0.6pc}\mathbb {E} \{ L(\mathbf {Q}(t+1))-L(\mathbf {Q}(t)) |\mathbf {Q}(t) \} \\&\qquad \qquad \qquad \leq R+\mathbb {E} \{[\mathbf {X}(t)-\mathbf {r}(t)\tau]^{\mathbb{T}} \mathbf {Q}(t) |\mathbf {Q}(t)\}.\tag{47}\end{align*} By adding $V\mathbb {E} [C(t)|\mathbf {Q}(t)]$ to the both sides of (47), we can prove the results in Lemma 1.

Appendix B Proof of Theorem 1

Proof:

First of all, we can know that the condition shown in (19) holds for any time slot. Summarizing all the inequations in (14) over $\forall t\in \{ 0, 1, {\dots }, T-1\}$ , we have \begin{align*}&\hspace {-0.6pc}\mathbb {E} \{L(\mathbf {Q}(T))\}-\mathbb {E} \{L(\mathbf {Q}(0))\} \leq (R+VC_{opt})T \\&\quad \qquad -\,V\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\} -\epsilon \sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\mathbb {E} \{Q_{j,i}(t)\}.\tag{48}\end{align*} And dividing both sides by $\epsilon T$ in (48), we get \begin{equation*} \frac {1}{T}\sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\mathbb {E} \{Q_{j,i}(t)\} \leq \frac {R+V(C_{opt}-\overline {C})}{\epsilon }.\tag{49}\end{equation*}

Then, we take the superior limits in both sides of (49) with $T\rightarrow \infty$ . We have \begin{align*} \lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}}\mathbb {E} \{Q_{j,i}(t)\} \leq \frac {R+V(C_{opt}-\overline {C})}{\epsilon }. \\\tag{50}\end{align*} Therefore, based on (50), we prove the results shown in (20).

In addition, we rearrange the terms in (48), and then we have \begin{align*} \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\}\leq&~C_{opt}+\frac {R}{V} -\frac {\mathbb {E} \{L(\mathbf {Q}(T))\}}{VT} \\&\qquad -\,\frac {\epsilon }{VT}\sum _{t=0}^{T-1}\sum _{i=1}^{I}\sum _{j=1}^{K_{i}} \mathbb {E} \{Q_{j,i}(t)\}.\tag{51}\end{align*} Since both the expectations of $L(\mathbf {Q}(T))$ and all queue backlogs are nonnegative, (51) can be rewritten as \begin{equation*} \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\} \leq C_{opt}+\frac {R}{V}.\tag{52}\end{equation*} Therefore, we take the superior limits in both sides of (52) with $T\rightarrow \infty$ . We have \begin{equation*} \lim _{T\rightarrow \infty }\sup \frac {1}{T}\sum _{t=0}^{T-1}\mathbb {E} \{C(t)\} \leq C_{opt}+\frac {R}{V}.\tag{53}\end{equation*} As a result, we prove the result in (21) based on (53). Through the analysis above, we complete the proof of Theorem 1.