1
Orchestrating Data Collection and Computation in Green IoT Networks
arXiv:2605.23152v1 [cs.NI] 22 May 2026
Abstract—Future Internet of things (IoT) networks will host applications that involve data collection and computation tasks on one or more servers. To this end, this paper proposes the first mixed integer linear program (MILP) to schedule and embed applications on energy harvesting nodes, where it optimizes (i) the sampling time of devices, (ii) whether to run an application, and (iii) the energy usage of devices, gateways and servers. To ensure applications are run often, we adopt the maximum age of service (AoS) metric, and set the MILP’s objective to minimize the maximum AoS or min-max AoS of applications. This paper also proposes two novel solutions: (i) a receding horizon control (RHC) based method, and (ii) a solution that greedily embeds applications according to their AoS. The results show that the min-max AoS of RHC and greedy approach is respectively 1.07x and 1.13x higher than MILP. Index Terms—Renewable energy, Resource allocation, Model Predictive Control, Virtualization, Information Freshness.
I. I NTRODUCTION In the near future, Internet of things (IoT) networks will have to optimize computing, communication, and storage resources to run artificial intelligence (AI) driven applications [1]. In addition, they will employ virtualization, whereby devices and servers run containers or virtual machines so that different users can share an IoT network [2]. Apart from that, nodes are likely to use renewable energy sources, where devices and servers may be powered by solar [3]. This will likely become standard given the massive energy requirements of future networks, especially those that run AI models [4]. Given the said so called green IoT network, a key issue is scheduling and embedding applications with dependent tasks on nodes; e.g., such an application may perform video analytics where it first acquires videos from devices with a camera followed by tasks such as object detection and recognition [5]. Figure 1 shows an example IoT network, where we aim to run two such applications. Their corresponding tasks, which are run as virtual network functions (VNFs), are deployed at gateways and at servers. VNF-Cs run on sensor devices. VNFPs run on gateways or servers to process collected data, after which results are sent to the sink. Author Zhan is with the Jinan University-University of Birmingham Joint Institute, Jinan University, Guangzhou, China, and also with the Department of Electrical and Systems Engineering, University of Pennsylvania, PA, USA (email: [email protected]). Author He and Chen are with the College of Information Science and Technology, Jinan University, Guangzhou, China (email: [email protected], [email protected]. Author Chin is with the School of Electrical, Computer and Telecommunications Engineering, University of Wollongong, NSW, Australia (email: [email protected]). Author Song is with the School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing, China (email: [email protected]).
AoS
Junfei Zhan, Tengjiao He, Kwan-Wu Chin, Benyu Chen, Fei Song
1
Time
Sink
2 2
3
Fig. 1. An example with server M1 and M2 . The gateways (G1 to G3 ), devices, and servers rely on solar energy. The VNFs (denoted as a circle) of two DAGs have a different color, i.e., green and red. These VNFs include (i) VNF-Cs, labeled as C in a circle, which are deployed at a gateway to download data from a device, and (ii) VNF-Ps, labelled as P in a circle, which process data from VNF-Cs. Lastly, the traffic between VNFs are indicated by their corresponding arrow, and dotted arrows indicate result from a VNF-P.
When running applications, a key issue is ensuring they are run frequently so that they are able to acquire and process the latest data. Hence, we adopt age of service (AoS) [6] as a performance metric, where the AoS of an application is equal to the time elapsed since the data generation time of the most recent service of the application to its completion time; i.e., an application with a low AoS equates to it having an up to date result. Compared to the age of information (AoI) [7], AoS emphasizes the freshness of services, which include time taken to acquire and process data. For example, a video analytics application may have one or more VNF-Cs to collect images from different cameras, which are then processed by a VNF-P that runs an object detection algorithm. The VNF-P then sends its computed result to a sink node. Here, the application’s AoS corresponds to when a target is last (or not) detected in an area. There are a number of challenges when scheduling and embedding applications in the aforementioned network. First, solar energy arrivals exhibit spatio-temporal properties, meaning the energy level of nodes varies over time and space. This has an impact on their ability to run a given VNF, or equivalently, the number of VNFs they can run in each time slot. Consequently, an energy outage may result in a VNFC/VNF-P not being run in a time slot to collect or compute data, which leads to a higher AoS. Moreover, a VNF may be run on a server that is far from the sink, which also increases its AoS. The second issue is fair resource allocation, where a network must not starve an application in favor of other
2
applications, meaning the AoS of an application must not grow significantly larger than the AoS of other applications. Henceforth, this paper makes the following contributions: C1 It is the first to study embedding of applications in a solarpowered network; as we will highlight in Section II, our problem is open where past works have not jointly considered AoS, energy harvesting servers, and applications with dependent tasks. C2 It outlines a novel mixed integer linear program (MILP) that can be used to optimally embed the tasks of applications over a planning horizon, where it aims to minimize the maximum AoS or min-max AoS of these applications. The MILP is the first to jointly optimize (i) device selection and sampling time, (ii) embedding of dependent tasks, and (iii) energy usage of devices, gateways and servers. C3 It outlines the first heuristic solution called GreedyOL, which embeds applications according to their AoS. In addition, it presents a novel receding horizon control (RHC) approach called RHCOP that uses causal information to embed applications. C4 It reports on the first study of a novel system, problem and solutions. It presents a number of theoretical properties, including the said problem’s hardness, and computation complexity of MILP and GreedyOL. Then it presents numerical results that showed that the min-max AoS of RHCOP and GreedyOL is respectively 1.07x and 1.13x higher than MILP. Additional gateways, servers and a larger solar panel size help reduce min-max AoS. By contrast, more applications led to larger min-max AoS values. Further, when applications have equal number of VNF-Cs and VNF-Ps, they the lowest min-max AoS as compared to the case when they have more VNF-Cs versus VNF-Ps, and vice-versa. Next, we discuss prior works. Section III presents our network model, and Section IV defines the problem formally. Section V outlines our RHC-based solution. Section VI presents the heuristic solution. Section VII lists some properties of the formulated MILP and proposed solutions. Our evaluation and results are discussed in Section VIII. Section IX concludes the paper. II. R ELATED W ORKS Our research overlaps with works that aim to (i) embed service function chains (SFCs) or applications modeled as directed acyclic graphs (DAGs) in a network, (ii) minimize some freshness related metric, and (iii) age of network service. A. SFC/DAGs Embedding Past works have considered the optimal mapping of virtual networks onto a network substrate. For example, the work in [8] aims to minimize the energy consumption of wireless sensor networks (WSNs), whereas the work in [9] considers multi-access edge computing (MEC) to name a few. However, the nodes in these works are not powered by a renewable energy source. By contrast, the authors of [10], [11] consider
the problem of embedding virtual networks onto a radiofrequency (RF) powered Internet of things (IoT) network. Both works aim to optimize the charging power used by a hybrid access point, VNFs placement, routing and/or link schedule. The work in [12] considers sharing of nodes between different operators. These nodes are also powered by RF and support virtualization. The authors formulated a Stackelberg game that jointly controls node sharing, the charging strategy of an RF transmitter and caching in order to maximize profit. Liang et al. [13] proposed a solution to minimize the energy cost of their network by optimizing VNF placement of SFCs and traffic routing. The key challenges include timevarying wireless links and uncertain energy arrivals. However, the aforementioned works do not aim to minimize AoI or AoS, where they aim to maximize the number of embedded SFCs/VNFs. They also consider a network with a dedicated power source as opposed to a renewable energy source. B. Information Freshness To date, many works have proposed metrics that aim to quantify the freshness of collected data. Examples include [14], and [15]. We emphasize that our work is different to AoI works, which do not consider computation and DAGs. To this end, we only consider works that aim to ensure the freshness of computed results. In this respect, a number of works have considered devices that collect and process data that is required by users. In this respect, timeliness of processed data is critical, where data is processed by a device or offloaded to a server. Reference [16] jointly considers the problem of executing sensed data locally at devices or offloaded to a cloud server in order to minimize AoI. In the latter case, a key problem is scheduling data transmissions. Ling et al. [17] consider devices that have energy capability. These devices consider their available energy when processing data locally or offloading data to a server in order to minimize AoI. The work in [18] considers devices that decide whether to process data locally or offloaded to a server to drive a co-located actuator. In [19], the authors consider tasks associated with autonomous driving, where their aim is to ensure these tasks have the latest sensing data for vehicle control. They design a reinforcement learning-based solution to optimize sensor data selection and task placement, aiming to minimize the maximum AoI of tasks. Li et al. [20] proposed the age of processing (AoP) metric, which they then study in a system with a single server and server. They consider sampling frequency as well as task offloading in order to minimize AoP. In [21], ground users contend for a wireless channel and computing resources at an edge server and a unmanned aerial vehicle (UAV). Their aim is to achieve a trade-off between information freshness and system energy cost. C. Age of Network Service Some works have studied AoI and network virtualization. For example, reference [22] aims to minimize the energy cost of embedding SFCs whilst ensuring the AoI of each SFC remains below a threshold at all times. In [23], each user has
3
TABLE I A COMPARISON BETWEEN WORKS . Ref [6] [8] [9] [10] [11][13] [12] [14] [15] [17] [16][18][19] [20][21] [22][23] [24] [26] Our Work
Only VNF Placement
SFC Embedding X
DAG Embedding
Computation Resource Allocation X
X X X
Energy Harvesting
X X
X X X
X
X
X
X X X
a SFC that involves data collection. The authors of [23] aim to minimize the weighted sum of SFC embedding cost and the maximum AoI of users, where the AoI of a user is determined by the VNFs schedule of its SFC. References [24], [25] study partial offloading problem with task dependencies. Its aim is to minimize the weighted sum of AoI, task processing latency and energy consumption. Both references, however, only consider a linear directed graph; i.e., a sequence of tasks. Reference [6] uses AoS to measure the freshness of service in industrial applications. It embeds SFCs from different devices, and aims to minimize the average AoS of these SFC requests. In [26], the execution of serverless functions at servers relies on the freshness of data from devices related to the function. It jointly optimizes data update at devices and data reception of servers to minimize the weighted sum of AoS of serverless functions. D. Discussion Table I compares prior works, where they have considered embedding VNFs/SFCs in energy harvesting networks, namely [10][11][12][13], do not have the same system setup nor address the same problem. More specifically, these works assume there are dedicated power sources that can be controlled to deliver energy to nodes. In contrast, the nodes in our network are ambient sources that exhibit spatio-temporal properties. Further, these works do not consider scheduling of DAGs to minimize AoS. In addition, they do not consider data collection from energy harvesting nodes. The works in Section II-B do not consider energy harvesting servers nor embedding of DAGs that include tasks that require one or more energy harvesting devices to collect data. Lastly, the works in Section II-C do not consider energy harvesting nodes. In summary, although prior works have considered (computed) information freshness and embedding of SFCs/VNFs, they have not jointly considered the following aspects: • End-devices and servers with energy harvesting capabilities, which govern the amount of data collected and number of applications run over time. • Orchestrating applications with dependent tasks, where tasks may involve both data collection and computation.
X X X X X X X
X X X X X
X
Information Freshness X
X X X X X X X X X
Data Collection
X X
X X
This generalizes prior works that only consider a single sensor device or/and application. • Unlike prior works, the AoS of applications is a function of the time varying energy and computation resources at nodes. In particular, an application can only run when all its VNFs have sufficient resources to run, and the amount of resources consumed by an application are impacted by other applications. III. S YSTEM M ODEL We optimize over discrete time slots in set T ; each time slot has index t and duration δ. For convenience, we will assume δ is one second, meaning the term energy and power are used interchangeably. The network substrate is represented as a graph G(V ∪ {o}, E), where V and E denote the set of nodes and links. The sink has label o. Each node n ∈ V has battery capacity Enmax . There are three types of substrate nodes: (i) devices, (ii) gateways, and (iii) servers. We will use d for device, i for gateway and s for server. Let VD , VG and VS denote the set of devices, gateways and servers, respectively. Each device d is only associated to one gateway in VG . Define Ni as the set of devices connected to gateway g. In addition, gateways assign an orthogonal frequency to their associated devices. Note that frequency/channel assignment is beyond the scope of this paper. The respective processing capacity of each gateway i ∈ VG and server s ∈ VS is Cimax and Csmax . A. Interconnections The wireless link between devices and their respective gateway is recorded in set EW . We model these links as block fading Rician channels, where the gain of a channel is fixed t during a slot but varies between two adjacent slots. Let gdi be the channel power gain between device d and gateway i in slot t, which is given by −α Ddi t , ∀(d, i) ∈ EW , (1) gdi = hC0 D0 where h is drawn from an Exponential distribution with unity mean, C0 indicates the path loss at a reference distance D0 ,
4
TABLE II A SUMMARY OF NOTATIONS .
1.
Sets
T G V s E VD VG VS Ni EW EG ES R Gr r VG VSr Er 2.
Set of time slots. Graph. Set of nodes. The sink. Set of links. Set of devices. Set of gateways. Set of servers. Set of devices associated to gateway i. Set of wireless links. Set of wired links between gateways and servers. Set of wired links between servers and the sink. Set of DAG requests. DAG of request r. Set of VNF-Cs in DAG r. Set of VNF-Ps in DAG r. Set of direct links in DAG r. Constants
δ Enmax Cnmax t gdi B R̄ Wnt Γru Cur r Buv Φrui Pi0 Pi1 ρ Ψ 3.
Duration of a time slot. Battery capacity of node n. Processing capacity of node n. Channel power gain between device d and gateway i. Bandwidth. Capacity of a wired link. The amount of solar energy arrival. Data rate requirement of VNF u of DAG r. Processing requirement of VNF u of DAG r. Bandwidth requirement of link (u, v) of DAG r. A binary variable to indicate the location of VNF-C. Base power of node i. Peak power of node j. Energy consumption of sensing one bit. A large positive value to disable constraints. Variables
wnt etn xtrui Uit φtdi t Pdi t yrvj tis lruv
The amount of energy stored at node n in slot t. Energy level at node n in slot t. A binary variable to indicate the activation of VNF-C. CPU utilization of gateway i is active in slot t. A binary variable to indicate the activation of device. Transmit power of device d at time slot t. A binary variable to indicate the activation of VNF-P. A binary variable shows when edge (u, v) of DAG r uses the link (i, s) in t. A binary variable to indicate the activation of VNF-M. AoS value of DAG request r in slot t. A non-negative variable.
t zros atr λtr
B. Energy Harvesting Let Wnt be the amount of solar energy that arrives at node n ∈ V in time slot t. This amount is governed by the Markov model proposed in [28]. Briefly, the model has four states, each corresponding to a weather condition, namely “Excellent”, “Good”, “Fair” and “Poor”, which are denoted as ωE , ωG , ωF and ωP , respectively. For each state, there is a Gaussian distribution with a given mean µω and variance σω2 , where ω ∈ {ωE , ωG , ωF , ωP }. Further, there is a transition probability between states, denoted as Pab , where a, b ∈ {ωE , ωG , ωF , ωP }. A key advantage of the Markov model is that the mean and variance of the Gaussian distribution of each state, and the transition probability between states can be set as per solar irradiance measurements from a test-bed. Each node n can only store up to Enmax amount of energy. Let wnt denote the amount of energy stored by node n in slot t. This amount is constrained by (i) the amount of solar energy arrivals, and (ii) the available battery capacity of node n. Let etn record the energy level of node n at the end of slot t. Formally, the value of wnt is constrained by wnt ≤ Wnt , ∀n ∈ V, ∀t ∈ T , wnt ≤ Enmax − etn ,
∀n ∈ V, ∀t ∈ T .
(2) (3)
C. Applications We model applications as DAGs. Define R as the set of requests to embed DAGs. Each DAG request r has three types of of tasks that are run as the following VNFs: VNF-C, VNFP and VNF-M. VNF-C u of DAG r is located at a given gateway. Its responsibilities include (i) collecting data from a device at a rate of Γru (bit/s), (ii) aggregating these raw data into a sample, and (iii) sending the sample to a VNF-P. Each VNF-P, which runs at a server, combines and processes samples from one or more VNF-Cs before sending the result to the sink. The sink runs VNF-M, meaning each DAG request r is rooted at sink o to merge all data. r We model each DAG as a graph G r (VG ∪ VSr ∪ r r r r {VNF-M}, E ), where VG , VS , and E represent the set of VNF-C, VNF-P and directed edges, respectively. We will use u, v and m to refer to VNF-C, VNF-P and VNF-M, respectively. Let Cur denote the processing requirement, i.e., r CPU cycles, of VNF u of DAG r, where u ∈ VG ∪ VSr . Each r r directed edge (u, v) ∈ E requires bandwidth Buv . Next, we outline constraints relating to the placement or activation of VNFs at gateways, servers and devices. D. Gateways
α is the path loss exponent, and Ddi is the Euclidean distance between device d and gateway i. There are two types of wired channels: (i) gateways-servers, and (ii) servers-sink o. These channels are recorded in set EG and ES , respectively. Without loss of generality, we assume these channels have capacity R̄ (bps). Note that in practice such links can be established by a software defined network (SDN) controller, where it installs a flow entry in switches along a path between two nodes [27].
The VNF-Cs of DAG requests are pre-loaded at gateways. Define an indicator Φrui ∈ {0, 1}, where we have Φrui = 1 if VNF-C u of DAG r is located at gateway i; otherwise, Φrui = 0. Let xtrui ∈ {0, 1} denote whether VNF-C u of DAG r located at gateway i is active in slot t; we have xtrui = 1 (xtrui = 0) when VNF-C is active (inactive) in slot t. For each gateway i, its processing capacity is constrained as X X Φrui xtrui Cur ≤ Cimax , ∀i ∈ VG , ∀t ∈ T . (4) r r∈R u∈VG
5
Each VNF-C runs on one gateway. We thus have X r Φrui xtrui ≤ 1, ∀u ∈ VG , ∀r ∈ R, ∀t ∈ T .
(5)
Next, we consider the energy expenditure at gateway i, which is dependent on its utilization. It has base power Pi0 and peak power Pi1 . The utilization at gateway i is P P t t r r Φrui xrui Cu r∈R u∈VG t , ∀i ∈ VG , ∀t ∈ T . (6) Ui = Cimax The energy level of gateway i is constrained as
Next, we consider the energy consumed by server s. Let its base power be Ps0 , and peak power when fully utilized is Ps1 . Define the processing utilization of server s as P P t r r yrvs Cv r∈R V ∈VS t , ∀s ∈ VS , ∀t ∈ T . (15) Us = Csmax The energy consumed ets by server s is by 0 ≤ ets ≤ Esmax , ∀s ∈ VS , ∀t ∈ T .
(7)
(16)
The energy evolution of server s during each slot t ∈ T is
The energy at gateway i evolves as eti = et−1 + wit−1 − (Pi1 − Pi0 )Uit , ∀i ∈ VG , ∀t ∈ T . (8) i
ets = et−1 + wst−1 − (Ps1 − Ps0 )Ust ≥ 0, ∀s ∈ VS . (17) s G. Sink
E. Devices Device d must meet two conditions before uploading any data. First, its associated gateway i is active in slot t. Second, gateway i selects device d in slot t. Let φtdi ∈ {0, 1} denote whether device d uploads data to its associated gateway i in slot t, where in the case of upload, we have φtdi = 1. Otherwise, we have φtdi = 0. Formally, we have P P t X r xrui ∀r∈R ∀u∈VG t P , ∀i ∈ VG , ∀t ∈ T , (9) φdi ≥ r r∈R |VG | d∈Ni X φtdi ≤ 1, ∀i ∈ VG , ∀t ∈ T , (10) d∈Ni
where Eq. (9) ensures φtdi is non-zero when a VNF-C on gateway i is active in slot t. Further, Eq. (10) ensures gateway i selects at most one device in each time slot. A device must have sufficient energy to support a VNF-C at its associated gateway. In particular, it must have sufficient energy to sense and transmit at a given rate Γru to each VNF-C u of DAG r. To this end, let ρ denote the energy consumption t of sensing one bit. Define Pdi to be the transmission power required to achieve a rate of Γru , which is calculated as t Pdi =
(2Γru /B − 1)N0 . t gdi
t etd = et−1 + wdt−1 − φtdi (Pdi + ρΓru ). d
We assume sink o has sufficient energy and computing resource. Sink o runs VNF-M of DAG r only when all VNFs t in DAG r are active. Let zrmo ∈ {0, 1} denote whether sink t t o runs VNF-M of DAG r (zrmo = 1) or not (zrmo = 0). To this end, we have X t r zrmo ≤ xtrui , ∀r ∈ R, ∀u ∈ VG , ∀t ∈ T , (18) i∈VG
t ≤ zrmo
X
t , yrvs
∀r ∈ R, ∀v ∈ VSr , ∀t ∈ T .
(19)
s∈VS
H. Routing The total traffic routed between a gateway and a server, and tis ∈ between a server and sink o must not exceed R̄. Define lruv tis {0, 1}; it is set to lruv = 1 when edge (u, v) of DAG r uses the link between gateway i and server s in slot t. Otherwise, tis = 1 when (i) VNF-C of DAG it is zero. Further, we have lruv r is active at gateway i in slot t, i.e., xtrui = 1, (ii) VNF-P of t DAG r is mapped to server s in slot t, i.e., yrvs = 1. To this end, for each DAG request r ∈ R in each slot t ∈ T , we have X tis xtrui = lruv , ∀(u, v) ∈ E r , ∀i ∈ VG , (20) s∈VS
(11)
The total energy cost of device d, which includes transmist sion and sensing, in time slot t is φtdi (Pdi + ρΓ). For each t ∈ T , the energy at each device d ∈ VD associated to each gateway i ∈ VG evolves as (12)
F. Servers The servers in VS run VNF-Ps. Let the binary variable t yrvs ∈ {0, 1} denote whether VNF-P v of DAG r is mapped to server s in slot t. As the computation resource of server s is finite, we have X X t yrvs Cvr ≤ Csmax , ∀s ∈ VS , ∀t ∈ T. (13) r r∈R v∈VS
(14)
s∈VS
i∈VG
0 ≤ eti ≤ Eimax , ∀i ∈ VG , ∀t ∈ T .
Each VNF-P of a DAG runs on one server: X t yrvs ≤ 1, ∀v ∈ VSr , ∀r ∈ R, ∀t ∈ T .
X
tis t lruv = yrvs ,
∀(u, v) ∈ E r , ∀s ∈ VS .
(21)
i∈VG
In addition, VNF-C u and VNF-P v of DAG r run only when the path between gateway i and server s has sufficient bandwidth. Formally, we have X X X tis t lruv Buv ≤ R̄, ∀(i, s) ∈ EG , ∀t ∈ T . (22) r v∈V r r∈R u∈VG S
Lastly, recall each server has only one link to sink s, the value t of yrvs indicates whether edge (v, m) is active on link (s, o) in slot t. Thus, for each slot t ∈ T , we have X X t t yrvo Bvm ≤ R̄, ∀s ∈ VS , ∀t ∈ T , (23) r r∈R v∈VS
where edge (v, o) is active when the channel between server s and sink o has sufficient bandwidth resource.
6
I. Age of Service (AoS) We assume the generate-at-will and just-in-time policy [29], where each device generates a sample for a given DAG if all its VNFs are allocated resources to run in a given time slot. This means the VNF-Ps of a DAG will receive all required samples from VNF-Cs and generate a result to sink o. Note that for each DAG r, a sample is generated by each of its VNF-C only after sink o receives the result from its VNF-P(s). We emphasize that AoS under generate-at-will is different with transmission delay. This is because AoS accounts for the entire time since the generation time of the most recent processing update, whereas transmission delay only refers to the transmission time of data from a source to a destination. As an aside, we note that metrics such as delay and AoI are not suitable for our problem. The reason is because it neglects (i) computation process, and (ii) multiple data sources. To incorporate both factors, we define the AoS of an application as being equal to the time elapsed since the data generation time of the most recent service of the application to its completion time. It accounts for the entire time elapsed since the data generation of the most recent service completion. It specifically emphasizes the freshness of a service completion, which includes data collection, multi-stage VNF computation, and delivery of the final result. We denote atr as the AoS value of DAG request r. It is t = 1. set to one when DAG r is active in slot t, i.e., zrmo Otherwise, the AoS of DAG r increases by one. The value of AoS evolves as per t atr = (1 − zrmo )at−1 + 1, ∀r ∈ R, ∀t ∈ T . r
slot t, meaning sink s received a sample from DAG r in slot t. Otherwise, atr increases by one. IV. P ROBLEM F ORMULATION We aim to optimize the min-max AoS of |R| DAG requests over |T | slots. Before presenting our MILP, we have to t first linearize Eq. (24), i.e., zrmo at−1 r . To do so, we replace t−1 t zrmo ar in Eq. (24) with a new variable λtr . Let Ψ1 be a large positive integer value. We note that the AoS of request r increases by one in each time slot if it is not served. Therefore, the maximum value of atr is |T | over a finite planning horizon of |T | slots. Hence, it is appropriate to set Ψ = |T |. We also introduce the following constraints to set the value of λtr : t λtr ≥ at−1 − (1 − zrmo )Ψ, r t t−1 t λr ≤ ar + (1 − zrmo )Ψ, atr = at−1 − λtr + 1, r
(25)
∀r ∈ R, ∀t ∈ T , ∀r ∈ R, ∀t ∈ T ,
(26) (27)
∀r ∈ R, ∀t ∈ T .
(28)
Observe that Eq. (25)-(28) present two scenarios. The first t scenario is when DAG r is inactive (zrmo = 0), which forces t λr to zero, see Eq. (25). Further, Eq. (26) and Eq. (27) are disabled. In addition, the value of atr increases by one when t we have zrmo = 0, see Eq. (28). The second scenario is when t DAG r is active (zrmo = 1). We use Eq. (26) and Eq. (27) to 1 This is also called the big-M method.
t∈T
s.t.
r∈R
(2)-(5), (7)-(10), (12)-(14), (16)-(23), (25)-(28).
We conclude with the following remarks. First, δ represents one unit of time, which is defined by an operator; note, our formulation remains the same for any unit of time. However, care has to be taken in terms of sizing resources such as energy and computation to reflect a chosen new time duration. Second, the proposed MILP can be solved by a commercial solver for small problem instances. As shown in Proposition 2, the proposed MILP becomes intractable in large scale networks. Further, VNF Placement and Traffic Routing (VPTR) problem [30], an NP-hard problem, is a special case of our problem, see Proposition 1. Lastly, noncausal information, i.e., future wireless channel coefficients and solar energy arrival, is required to solve P1, meaning it is not practical and serves only as a theoretical benchmark. In the following sections, we present solutions that can be run by a central controller, where the first solution uses historical information, and the second solution only uses current resource information at devices, gateways and servers. Next, we present a practical solution that only requires historical information.
(24)
Thus, we have atr = 1 when VNF-M of DAG r is active in
t 0 ≤ λtr ≤ zrmo Ψ, ∀r ∈ R, ∀t ∈ T ,
force λtr to at−1 r . Consequently, as per Eq. (28), the value of ats becomes one. Finally, we have our MILP: ) ( X at r , (P1) min max t t |T | φtdi ,xtrui ,yrvj ,ltis ruv ,zrmo
V. A R ECEDING H ORIZON S OLUTION We design an RHC based solution called Receding Horizon Solution Optimization (RHCOP). Briefly, RHC is a well-known feedback control strategy. It builds a time horizon/window, and employs a prediction model to estimate future information within the said window. It then optimizes over the time slots in the window and adopts the computed solution for the current time slot. It then shifts the said window by one time slot, and repeats the process. In our case, RHCOP constructs a time window with K time slots. It employs a Gaussian mixture model (GMM) to estimate the probability distribution of wireless channel gains and solar energy arrivals at each node over K time slots. The reason of selecting GMM is that the solar energy arrivals at devices can be characterized as a Markov model with four states. Each state has a Gaussian distribution with its own mean and variance. Consequently, energy arrivals are governed by a mixture of Gaussian distribution, i.e., a GMM. Using the said GMM, RHCOP determines the energy arrivals over the said K time slots, and formulates MILP (P1) that optimizes over these K time slots. It then solves the MILP, and applies the computed decision for slot t, i.e., φtdi , xtrui , t t , and zros . Lastly, it shifts the window by one time slot yrvj to cover slot t + 1, . . . , K + 1, and repeats the aforementioned steps to obtain the decision for time t + 1. Figure 2 gives an overview of RHCOP. RHCOP has three phases: Training, Prediction, and Decision. In the Training phase, it collects historical data of (i)
7
Historical Data
Train GMM
Predict
Window t
Time
Solve MILP
Fig. 2. An overview of RHCOP in a network with a single device and server.
channel gains for links in EW , (ii) solar arrivals of nodes in V. For both (i) and (ii), RHCOP trains the GMM of each node using historical data; note, there is a GMM for each wireless link in EW and node in |V|. Briefly, each GMM includes a finite number of weighted Gaussian distributions/components with a corresponding mean and variance, where the mean and variance of each distribution is computed by the ExpectationMaximization (EM) algorithm [31]. We use NG to record the number of Gaussian components of GMM. Note, instead of GMM, other methods, such as a recurrent neural networks, can be used without changing our solution. The Training phase can also be scheduled periodically to incorporate new data that improves the GMM of nodes. Each slot t contains two phases: (i) Prediction, and (ii) Decision. In the Prediction phase, RHCOP constructs a time horizon window with size K. It acquires channel gain at the beginning of slot t via standard pilot-based estimation techniques. It then calls the GMM of each device, gateway or server to obtain an energy arrival estimate and channel gain estimate of time slots in the said window. In the Decision phase, RHCOP solves MILP P1 over the given time window, and applies the solution in slot t. After that, in time slot t + 1, RHCOP shifts its time window by one slot, and repeats the previous steps. Algorithm 1 shows the details of RHCOP. Each server in VS and gateways in VG collect a data set of their historical energy arrivals. Let the corresponding data be stored in set Ei and Gd , see lines 2-7. Let Ggd be the GMM of the wireless channel of device d ∈ VD . Denote GWn as the GMM that models the energy arrivals at each node n ∈ V. RHCOP calls Train(.) to train GMM Ggd and GWn , see lines 8-13. After that, RHCOP runs the Prediction phase and the Decision phase in each slot, see lines 14-26. To do so, RHCOP builds a time window, denoted as K, that has K slots, see line 16. Let {W̄nt }t∈K record the estimated energy arrivals at node n t over the said time window; similarly, denote {ḡdi }t∈K as the estimated channel gains of wireless link (d, i). In lines 1722, RHCOP calls PredictEH(.) and PredictCha(.) to estimate t the value of {W̄nt }t∈K and {ḡdi }t∈K , respectively. RHCOP runs the Decision phase, which solves MILP P1 over the fixed time window using SolveMILP(.); it uses Φ to record the results of MILP P1, see line 24. Lastly, RHCOP runs t , UpdateParameters(.) to update the value of φtdi , xtrui , yrvj t t zros , and ei , see line 25.
Algorithm 1: Pseudocode of RHCOP. t Input: {ĝdi }∀(d,i)∈EW , {Ŵnt }∀n∈V Output: {atr }r∈R 1 for n ∈ V do 2 En = CollectData(n) 3 end 4 for (d, i) ∈ EW do 5 Gdi = CollectData(d) 6 end 7 for n ∈ V do 8 GWn = Train(Gdi) 9 end 10 for (d, i) ∈ EW do 11 Ggd = Train(En ) 12 end 13 for t ∈ T do 14 K = {t, t + 1 . . . , t + K} 15 for n ∈ V do 16 {W̄nt }t∈K = PredictEH(n, K, GWn ) 17 end 18 for (d, i) ∈ EW do t 19 {ḡdi }t∈K = PredictCha(d, K, Ggd ) 20 end t 21 Φ = SolveMILP(K, {W̄nt }t∈K , {ḡdi }t∈K ) 22 UpdateParameters(Φ, t) 23 end
VI. A H EURISTIC S OLUTION : G REEDYOL Greedy Online (GreedyOL) embeds and schedules DAG requests according to their AoS. It has three key phases in each time slot: (i) Sort, (ii) Embed, and (iii) Update. The Sort phase sorts all DAG requests in decreasing order of their AoS value. The Embed phase aims to find gateways, servers and physical links that have sufficient computation, energy and communication resources to support DAGs. The Update phase determines whether to activate a DAG using the result in the Embed phase. Next, we explain each phase in detail using Algorithm 2, which is run in each time slot. In the Sort phase, GreedyOL calls SortDAoS(.) to place DAG requests in set R in descending order of their AoS, i.e., atr , where GreedyOL records the results in set R̄, see line 1. The Embed phase checks DAGs in R̄ using three steps. First, it finds a gateway i in set VG for each VNF-C u of DAG r, where gateway i must satisfy three conditions: (i) gateway i has sufficient energy to support VNF-C u, (ii) gateway i has computation resource to run VNF-C u, and (iii) there is at least one device that has sufficient energy of collect data for gateway i. These conditions are checked by GatewayECD(.), and it stores the suitable gateway in ηur . After finding a gateway for VNF-C u of DAG r, it moves to the next VNF-C of DAG r, see line 5-6. The second step of the Embed phase is to find a server s for each VNF-P v in each DAG request r. Server s must satisfy two conditions: (i) it has sufficient energy to embed VNF-P v, and (ii) it has sufficient CPU cycles for VNFP v. GreedyOL calls ServerEC(.) to check the said conditions, and the corresponding server s is stored in ψvr . After that, it
8
moves to the next VNF-P, see line 12. The last step of the r Embed phase relates to communication resource. Denote γuv as a binary variable associated with each edge of DAG r. GreedyOL calls CheckBand(.) to check whether the link ηur and ψvr have sufficient bandwidth to support the demand of r r edge (u,v) (γuv = 1) or not (γuv = 0). r In the Update phase, GreedyOL uses γuv and CheckDAG(.) to check whether all VNF-Cs and VNF-Ps of DAG r are embedded successfully. If yes, GreedyOL calls UpdateRe(.) to update the energy, computation and communication resource of gateways and servers, see line 20. After that, GreedyOL embeds DAG r and set its AoS to one. Otherwise, the value of atr increases by one. Algorithm 2: Pseudocode of GreedyOL. t Input: {gdi }∀(d,i)∈EW , {Wnt }∀n∈V Output: {atr }r∈R t 1 R̄ = SortDAoS({ar }∀r∈R ) 2 for r ∈ R̄ do r 3 for u ∈ VG do 4 for i ∈ VG do 5 ηur = GatewayECD(i) 6 Break 7 end 8 end 9 for v ∈ VSr do 10 for s ∈ VS do 11 ψvr =ServerEC(s) 12 Break 13 end 14 end 15 for (u, v) ∈ E r do r 16 γuv = CheckBand(u,v,ηur ,ψvr ) 17 Break 18 end r 19 if CheckDAG({γuv }(u,v)∈E r ) then r 20 UpdateRe({ηur }u∈V G , {ψvr }v∈V S , {γuv }(u,v)∈E r ) t 21 ar = 1 22 else 23 atr = atr + 1 24 end 25 end
VII. A NALYSIS Here, we present facts relating to the hardness of our problem, and computational complexity of MILP and GreedyOL. Proposition 1. Problem P1 is at least NP-hard. Proof. We show that the NP-hard VPTR problem [30] is a special case of our problem. Consider a substrate network and a set of requests. Specifically, each substrate node has limited energy and computational resources. Each link has limited bandwidth capacity. Each request includes a set of VNFs with specific energy, computational and bandwidth requirements. VPTR aims to place VNFs on substrate nodes, and finds routes between two VNFs without violating node and link resource
capacity. To this end, we remove three types of constraints from our problem: (i) energy constraints at devices, gateways and servers, which include Eq. (2), (3), (7), (8), (12), (16), (17), (ii) device selection constraints at each gateway, which include Eq. (9) and (10), (iii) AoS constraints of each DAG request, meaning Eq.(25)-(28). Thus, VRTP is a special case of our problem, meaning our problem is at least NP-hard. P r | + |VSr | + Proposition 2. The MILP P1 has |T |( r∈R (|VG r r |E ||VG |+|E ||VS |)+|EGP |+4|VS |+4|R|+2|V|+5|V G |+|VD |) P r r |V |V ||V | + constraints and (|V | + G D S ||VS | + G r∈R r∈R P r r r∈R |VG ||VS ||VG ||VS | + |R|)|T | decision variables.
Proof. We start with decision variables. There are four types of t tis t decision variables, i.e., φtdi , xtrui , yrvs , lruv and zrmo . As each device is associated with at most one gateway in each time slot, we have |VD ||T | of φtdi . Next, the variable xtrui exists for each VNF-C ofP each DAG request at each gateway in each slot. r t Thus, there are r∈R |VG ||VG ||T | such variables. As for yrvs , each VNF-P of each DAG request at each server in each slot P t has one yrvs . We thus have r∈R |VSr ||VS ||T | such variables. tis The variable lruv exists for edge of request at each Peach DAG r ||VSr ||VG ||VS ||T | link in each slot. Thus, we have r∈R |VG such constraints. Lastly, as the VNF-M of each DAG runs only on the sink in each slot, there are P |R||T | such varir ables. In summary, We thus have (|V | + D r∈R |VG ||VG | + P P r r r r∈R |VS ||VS | + r∈R |VG ||VS ||VG ||VS | + |R|)|T | decision variables, as desired. We now quantify the number of constraints in MILP P1. Each device, gateway and server has one constraint of type (2) and (3) in each slot, where there are 2|V||T | such constraints. Each gateway has one constraint of type (4), (7) and (8), (9) and (10), resulting in 5|VG ||T | constraints. Each device has one constraint of type (12) in each slot, which results in |VD | constraints. Each server has one constraint of type (13), (16), and (17) in each slot, we have 3|VS ||T | such constraints. The VNF-C of each DAG request has one of type P constraint r |V ||T | such (5) and (18) in each slot, resulting in G r∈R constraints. The VNF-P of each DAG request has one conP straint of type (14) and (19), resulting in r∈R |VSr ||T | such constraints. Next, as for constraint (20) and (21), they exist on one edge of each DAG in eachP slot for each gateway and server, respectively. Thus, we have r∈R |E r ||T |(|VG |+|VS |) such constraints. Constraint (22) exists for each link between gateways and servers in each slot. Thus, we have |EG ||T | such constraints. Constraint (23) exists for each link between servers and sink in each slot, where we have |VS ||T | such constraints. Lastly, each DAG request has one constraint of typeP (25)-(28). Hence, we have 4|R||T |, In summary, we have r |+|VSr |+|E r ||VG |+|E r ||VS |)+|EG |+4|VS |+ |T |( r∈R (|VG 4|R| + 2|V| + 5|VG | + |VD |) constraints Next, we consider the run-time complexity of RHCOP. Recall that it has two parts, i.e., offline training and online execution. Since the training phase is performed offline using historical data, it does not consume real-time computational resources. Thus, we focus only on its online execution part. Proposition 3. The run-time complexity of RHCOP per time slot is O((|V| + |EW |)K + 2KQ ).
9
Proof. In each slot, RHCOP’s online phase includes a prediction phase and a decision phase. In the prediction phase, RHCOP calls the trained GMMs over a time window with a size of K, see Lines 17-22. The time complexity of this phase is O((|V| + |EW |)K). Next, in the decision phase, RHCOP solves the formulated MILP over the given time window. Let Q denote the number of integer variables per time slot in the MILP. in Proposition 2, the P P As shown r r |V ||V |V ||V | + value of Q is |V | + S| + G D S G r∈R r∈R P r r r∈R |VG ||VS ||VG ||VS | + |R|. The worst-case complexity of solving this MILP using standard branch-and-bound methods is O(2KQ ). Lastly, both of the prediction phase and the decision phase run in each slot. Hence, the time complexity of the online execution in RHCOP is O((|V| + |EW |)K + 2KQ ). Note that the online execution phase of RHCOP can be sped up by pre-computing solutions offline and storing them in a neural network, see [32] for an example work. This means an operator does not have to solve an MILP in each time slot. Instead, it retrieves the corresponding solution from the neural network based on energy information at gateways and servers. Proposition 4. The time complexity of GreedyOL is r O(|T ||R|(|R|log|R| + |VG ||VG ||Ni | + |VSr ||VS | + |E r |)). Proof. The Sort function has time complexity O(|R|log|R|). In lines 3-8, each VNF-C calls function GatewayECD(.) that runs at most |Ni | times. Thus, lines 3-8 run at most r |VG ||VG ||Ni | times to select a gateway for VNF-C. Lines 9-14 run at most |VSr ||VS | times when selecting a server for VNF-P. Lines 15-18 run at most |E r | times when checking whether link (ηur , ψvr ) supports edge (u,v) or not. UpdateRe(.) searches all gateways and servers, and determine whether to update their energy, computing and bandwidth resources. Its time complexity is thus O(|VG |+|VS |). Next, we observe that lines 2-25 run at most |R| times to check all DAGs. Further, as GreedyOL works over |T | slots, the time complexity of GreedyOL is r O(|T ||R|(|R|log|R| + |VG ||VG ||Ni | + |VSr ||VS | + |E r |) VIII. E VALUATION We conduct our simulation using Python 3.8.5 and Gurobi 9.9.1. Gateways, devices, servers and sink s are randomly deployed on a 1000×1000 m2 area. Devices have a solar panel of size 30 × 30 cm2 with efficiency 20%. Tables III and IV list parameter values of the solar energy arrival process [28]. As per [28], the mean of four solar energy arrival states are 94.6, 76.0, 45.6 and 17.9 mW/cm2 . Further, their respective variance is 0.31, 1.55, 1.48 and 0.71. The battery size of a device, a gateway and a server is set to 10 J, 100 J and 100 J, respectively. Gateways and servers have a CPU capacity of 1000 Megacycles [33]. Their base and peak power are set to 170 W and 500 W, respectively [33]. We set ρ to 150 nJ/bit. We set B and N0 to 200 kHz and -95 dBm/Hz, respectively. The path loss exponent α is 2.5 and the path loss at the reference distance of one meter is 30 dB. Wired links have a capacity of 1000 Mbps [33]. Each DAG request has five VNFs that includes at least one VNF-C and one VNF-P. Other VNF types are generated randomly. The computation resource of each VNF is drawn uniformly from the range [10,100] (in
Megacycles). Each VNF-C randomly connects to a VNF-P with a probability of 0.9. The bandwidth demand between VNFs is randomly drawn from [10, 50] (in kb/s). The data requirement of VNF-C is 100 kb/s, and we set Ψ = |T |. TABLE III M EAN AND VARIANCE OF THE S OLAR E NERGY A RRIVAL State Mean (mW/cm2 ) Variance
Poor 1.75 0.65
Fair 4.21 1.04
Good 7.02 2.34
Excellent 9.38 0.54
TABLE IV T RANSITION P ROBABILITY OF THE S OLAR E NERGY A RRIVAL State
Poor
Fair
Good
Excellent
Poor
0.979
0.015
0.006
0
Fair
0.005
0.988
0.007
0
Good
0.006
0.009
0.975
0.010
Excellent
0
0
0.007
0.993
A. Benchmark Solution We benchmark against two solutions called Random and GMMPre. Random selects a random number of DAGs to embed in each slot, and then runs MILP. If the MILP is solvable, Random embeds the DAGs and updates the computing, bandwidth and energy resources of devices, gateways and servers, respectively. Otherwise, it does not embed the selected DAGs, and moves to the next slot. GMMPre employs ′ GMM to estimate the energy arrivals of K = 8 future time slots. Next, it calculates the average energy harvesting rate of each device, gateway and server. Lastly, it uses this average value to replace the energy level in GreedyOL, and then calls GreedyOL. We study eight parameters, i.e., |VG |, |VS |, |Ni |, |R|, K, L, VNF-C/VNF-P in a DAG, and number of VNFs. We report the average result of 50 runs. B. Simulation Results We first study how the number of gateways, i.e., |VG |, impact max-min AoS. We set |VS |, |Ni |, |R|, K and L to 3, 3, 3, 8 and 30 cm, respectively. There are 12 slots, i.e., |T | = 12. As shown in Figure 3a, min-max AoS decreases with |VG |. For example, the min-max AoS of MILP and RHCOP decreases from 6.50 and 6.50 to 1.58 and 1.69, respectively. The value of GreedyOL, GMMPre and Random decreases from 6.50 to 1.83, 2.03 and 3.43, respectively. The reason is because there are more potential gateways to deploy the VNF-Cs of a DAG in each slot when |VG | increases. Thus, more computation, bandwidth and energy resources can be used to support a VNFC in each slot, which reduces AoS. Another observation is that the min-max AoS of all solutions is bounded to 6.50 when |VG | = 1. This reason is because one gateway has insufficient energy, computing and bandwidth resource to service DAG requests. All DAG requests cannot be active during |T | slots, causing ats to increase by one in each slot. As the AoS of each
10
6 5 4
4
3
5
Number of gateway
7
9
1
3
5
Number of erver
7
6 5 4
7
MILP RHCOP Greed)OL GMMPre Rando
6 5
3
3
10
Size of time window
13
1 20
5
7
Number of devices er gateway
9
8
MILP RHCOP GreedyOL GMMPre Random
7 6
60
3
80
Solar panel side length (c )
100
(f)
2 2
5
7
9
8
10
Number of DAG requests
7
Gateways/* */Se ve s */*
6 5 4 3 2
3
40
1
(d)
4
2
(e)
2
5
3
7
2 1
9
4
4
3
(c)
Min- a( age of service
Min-max age of ervice
7
2 1
4
(b) MILP RHCOP GreedyOL GMMPre Random
5
3
(a) 8
6
Min-max age of service
1
6
MILP RHCOP GreedyOL GMMPre Ra dom
7
4
2
2
7
8
MILP RHCOP GreedyOL GMMPre Random
5
3
3
8
Mi -max age of service
5
MILP RHCOP GreedyOL GMMPre Random
Min-max age of se vice
Min-max age of ervice
6
7
Min-max age of service
MILP RHCOP GreedyOL GMMPre Random
Min-max age of ervice
7
4
6
8
The ratio of VNF-C to VNF-P in a DAG
(g)
10
1
2
4
6
Number of VNFs in each DAG (h)
Fig. 3. Impact of various parameters on min-max AoS: (a) number of gateways |VG |, (b) number of servers |VS |, (c) number of devices associated to a gateway |Ni |, (d) number of DAG requests |R|, (e) window size K, (f) panel size of servers and gateways L, (g) the ratio of VNF-C to VNF-P in a DAG, (h) infinite resource.
DAG request over |T | = 12 frames is 1 + 2 + · · · + |T |, its average value is 6.5. Next, we vary the number of servers, where |VS | ∈ {1, 3, 5, 7, 9}. The value of |VG |, |Ni |, |R| is set to three. The value of K, L and |T | is 8, 30 cm and 12 slots, respectively. Referring to Figure 3b, the min-max AoS of MILP decrease from 6.50 to 1.22 as |VS | increases from one to nine. RHCOP shows a reduction from 6.50 to 1.55, while GreedyOL decreases from 6.50 to 1.71. The value of GMMPre and Random decreases by 64.15% and 49.69% from 6.50, respectively. The reasons are as follows. First, more servers provide more energy, communication and computing resources for VNF-Ps in DAG requests. Further, a higher |VS | value leads to more paths from gateways to the sink, where a DAG request selects a path that consumes less energy to deliver sensor data. This then allows a DAG to activate more times over |T | slots in higher |VS | case. Next, we consider the number of devices associated to each gateway, i.e., |Ni |. We set |VG | = |VS | = |R| = 3, K = 8, L = 30 cm and |T | = 12 slots. As per Figure 3c, the number of devices associated at each gateway has limited impact on min-max AoS. For example, the min-max AoS of MILP ranges between 2.43 to 2.23 when |Ni | increases from one to nine. For RHCOP, it ranges between 2.59 to 2.61 whereas for GreedyOL it ranges from 2.86 to 2.70. The reason is because devices harvest sufficient energy for sensing and data upload. As a result, the number of devices associated to each gateway has limited impact on the min-max AoS. Next, we consider the number of DAG requests, where |R| ∈ {1, 3, 5, 7, 9}. We set |VS |, |VG |, |Ni | = 3. The value of K, L and |T | is 8, 30 cm and 12 slots, respectively. As
shown in Figure 3d, the min-max AoS of MILP increased by 357.75% from 1.42 when |R| increased from one to nine. The min-max AoS of RHCOP, GreedyOL, GMMPre and Random increases by 333.33%, 348.28%, 271.43% and 38.30%, where these values are 6.50 when |R| = 9. This is because higher number of DAG requests require more energy, communication and computation resources to run all DAG requests. As these resources are fixed, the min-max AoS of all solutions increases. The next experiment studies the following window sizes: K ∈ {1, 4, 7, 10, 13}, where |VS | = |VG | = |Ni | = |R| = 3. The value of L and |T | is set to 30 cm and 12 slots, respectively. From Figure 3e, the time window size has no impact on the performance of MILP, GreedyOL, GMMPre and Random. For example, the min-max AoS of MILP ranges from 2.47 to 2.50 when K increases from one to 13. This is because MILP, GreedyOL and Random do not use a time horizon window. Further, the window size of GMMPre is fixed ′ to K = 8. Consequently, the value of K has no impact on the performance of GMMPre. Another observation is that the min-max AoS of RHCOP decreases from 4.28 to 2.61 when K increases from one to seven. The reason is because RHCOP has more wireless channel gain and energy arrival information of future slots when K increases. This thus allows RHCOP to make decision using more prediction information. However, due to estimation errors, with more future slots, a solution computed by RHCOP for the current time slot is less likely to be optimal. Thus, the min-max AoS of RHCOP increases from 2.61 to 3.17 when K further increases to 13. Next, we study the impact of solar panel size L, where L increases from 20 cm to 100 cm with an interval of 20 cm.
11
7 6
Min-Max AoS (Min-Max Obj) Average AoS (Avg Obj) Max AoS acro DAG reque t (Avg Obj)
Age of Service
5 4 3 2 1 1
3
5
7
Number of DAG reque t
9
Fig. 4. Min-max AoS vs. average AoS.
105 104 103
Runtime (s)
We set |VS | = |VG | = |Ni | = |R| = 3, K=8 and |T | = 12. Referring to Figure 3f, the min-max AoS of MILP decreased by 61.59% from 4.27 when L increased from 20 cm to 100 cm. The min-max AoS of RHCOP and GreedyOL is 4.41 and 4.51 when L = 20 cm, respectively. These values decrease to 1.75 and 1.83 when L further increases to 100 cm. This is because gateways and servers have more energy to support VNF-Cs and VNF-Ps, leading to lower AoS values. We now study DAGs with different ratio of VNF-Cs versus VNF-Ps. We fix the number of VNFs in a DAG to six, and study the following ratio of VNF-C to VNF-P in each DAG: {1/6, 2/6, 3/6, 4/6, 5/6}. We set |VS | = |VG | = |Ni | = |R| = 3, where K and L is 8 and 30 cm, respectively. As per Figure 3g, min-max AoS decreases when the ratio of VNF-C to VNFP increases from 1/6 to 3/6. For example, the min-max AoS of MILP increases from 3.71 to 2.38. However, as the ratio of VNF-C to VNF-P further increases from 3/6 to 5/6, the min-max AoS increases. For instance, the min-max AoS of MILP increases from 2.38 to 4.06. The reason is because the increasing ratio of VNF-Cs to VNF-Ps resulting in fewer VNF-Ps. Hence, fewer VNF-Ps share energy, communication and computation resources of servers, leading to lower minmax AoS values. However, as the ratio of VNF-Cs to VNFPs further increases, more VNF-Cs share the resources of gateways, resulting in higher min-max AoS values. This experiment studies how resource limit at gateways and servers impact performance, where we study three scenarios: (i) gateways with unlimited resources, (ii) servers with unlimited resources, (iii) servers and gateways with unlimited resources. We set |VS | = |VG | = |Ni | = |R| = 3. The value of L, K and |T | is 30 cm, 8, and 12 slots, respectively. The number of VNFs in a DAG increases from two to ten with an interval of two. Referring to Figure 3h, the min-max AoS of scenario (iii) is one, meaning the network has sufficient resources to activate all DAGs in each slot. The min-max AoS of scenario (i) and (ii) increases by 212.84% and 128.87% from 1.09 and 1.42, respectively, with increasing number of VNFs. This is expected as more resources are required to run VNFs. In scenario (i), more VNF-Ps share the resource of servers when the number of VNFs increases. Thus, the min-max AoS of MILP increases. When servers have infinite resource in scenario (ii) additional VNFs mean more VNFCs will require the resource of gateways, which increases the min-max AoS of MILP. We now discuss optimizing min-max AoS versus average AoS, and the trade-off between fairness and network efficiency. We set |VS | = |VG | = |Ni | = 3, K=8 and |T | = 12, and increase |R| from one to nine. We compare three schemes: (i) the min-max AoS achieved by MILP P1, (ii) the average AoS, which the the average AoS of all DAG requests, (iii) the maximum average AoS. As illustrated in Figure 4, the average AoS is lower than min-max AoS. For example, the average AoS is 82.16% that of the min-max AoS for |R| = 5. This means our approach achieves higher performance when we optimize the average AoS. However, the min-max AoS is lower than the maximum value of average AoS. For example, the value of min-max AoS is 91.42% that of the maximum value of average AoS when |R| = 5. It shows that relying
102
MILP RHCOP GreedyOL GMMPre Rand m
101 100
10−1 10−2 10−3 1
3
5
7
Number f DAG requests
9
Fig. 5. Runtime of MILP, RHCOP, GreedyOL, GMMPre and Random.
solely on the average AoS leads to significantly higher AoS for certain nodes, resulting in poor fairness. In contrast, our min-max AoS metric ensures fairness across all nodes. We now analyze the runtime of MILP, RHCOP, GreedyOL, GMMPre and Random as the number of DAG requests varies, where |R| ∈ {1, 3, 5, 7, 9}. We set |VS | = |VG | = |Ni | = 3, K=8 and |T | = 12. Referring to Figure 5, the runtime of MILP increases as |R| grows, rising from 0.22 seconds at |R| = 1 to 4685.04 seconds at |R| = 9. RHCOP increases from 17.73 seconds to 1403.92 seconds over the same range. This rapid growth occurs because both MILP and RHCOP rely on a solver to solve MILP, where the number of decision variables and constraints increases with |R|. For GreedyOL, the runtime increases from 0.12 seconds to 0.78 seconds when |R| increases one to nine, which empirically validates the complexity analysis in Section VII. Lastly, we consider the min-max AoS gap between MILP, RHCOP, GreedyOL, GMMPre and Random. In particular, compared to the min-max AoS of MILP, the performance of RHCOP, GreedyOL, GMMPre and Random is 1.07, 1.13, 1.29 and 1.92 higher than that of MILP. The reason is because MILP uses non-causal information to make decision, i.e., future wireless channel gains and energy arrivals over
12
|T | slots. By contrast, RHCOP, GreedyOL, GMMPre and Random have only causal information. Further, RHCOP and GMMPre use GMM to predict wireless channel gains and energy arrivals, resulting in prediction error. In addition, we observe that the performance of RHCOP is better than that of GreedyOL, GMMPre and Random. This is because (i) RHCOP uses historical data, and (ii) RHCOP makes decision using estimates across multiple slots. GreedyOL has better performance as compared to GMMPre. The reason is because GMMPre uses the average energy arrivals at gateways or servers, meaning in some time slots, a gateway or server may have insufficient energy to support the decision of GMMPre. IX. C ONCLUSION This paper has considered a novel DAG requests embedding problem in solar powered networks. Its aim is to minimize the maximum AoS of DAGs/applications. It presented the first MILP for the problem, and proposed a RHC-based solution called RHCOP, and a heuristic solution called GreedyOL. The results showed that the min-max AoS of RHCOP and GreedyOL is 1.07x and 1.13x higher than MILP. Further, more gateways, servers and larger solar panel sizes helped reduce min-max AoS. By contrast, increasing the number of DAG requests led to higher min-max AoS values. All solutions had the lowest min-max AoS when the ratio of VNF-C to VNF-P is 0.5. A potential future work is to consider applications that require specific services or data. R EFERENCES [1] A. H. Sodhro, S. Pirbhulal, and V. H. C. de Albuquerque, “Artificial intelligence-driven mechanism for edge computing-based industrial applications,” IEEE Trans. on Ind. Inform., vol. 15, no. 7, pp. 4235–4243, 2019. [2] L. Zhang and K.-W. Chin, “VNF scheduling and sampling rate maximization in energy harvesting IoT networks,” IEEE Trans. on Mob. Comp., vol. 23, pp. 14441–14458, Dec. 2024. [3] T. He, M. Zheng, K.-W. Chin, T. Liu, and Y. Luo, “Malware aware UAV-assisted data collection and processing in solar-powered IoT networks,” IEEE Trans. Ind. Informat., 2026. Early Access, doi: 10.1109/TII.2025.3644942. [4] R. Desislavov, F. Martı́nez-Plumed, and J. Hernández-Orallo, “Trends in AI inference energy consumption: Beyond the performance-vsparameter laws of deep learning,” Sustainable Computing: Informatics and Systems, vol. 38, p. 100857, 2023. [5] T. Bai, H. Zhao, L. Huang, Z. Wang, D. I. Kim, and A. Nallanathan, “A decade of video analytics at edge: Training, deployment, orchestration, and platforms,” IEEE Commun. Surveys Tuts., pp. 1–1, 2025. [6] Y. Liu, B. Yang, X. Yang, Y. Wu, and C. Li, “Microservice dynamic migration based on age of service for edge computing,” in IEEE ICIT, (Shanghai, China), pp. 1–6, Aug. 2022. [7] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?,” in IEEE INFOCOM, (Orlando, FL, USA), pp. 1–5, Mar. 2012. [8] R. Katona, V. Cionca, D. O’Shea, and D. Pesch, “Virtual network embedding for wireless sensor networks time-efficient QoS/QoI-aware approach,” IEEE Internet Things J., vol. 8, pp. 916–926, Jan. 2021. [9] R. Xie, H. Zhu, Q. Tang, Q. Chen, S. Qiao, and T. Huang, “Joint task scheduling and load balancing in computing power networkenabled edge computing systems,” in 8th IEEE ICCC, (Chengdu, China), pp. 563–568, Dec. 2022. [10] T. He, K. Chin, H. Ren, and X. Liu, “Maximizing virtual network embedding requests in RF-charging IoT networks,” IEEE Commun. Lett., vol. 26, pp. 863–867, Apr. 2022. [11] H. Ren, K. W. Chin, and T. He, “Orchestrating virtual network functions in wireless-powered IoT networks,” IEEE Internet Things J., vol. 9, pp. 15874–15885, Sept. 2022.
[12] Y. Cheng, J. Zhang, L. Yang, C. Zhu, and H. Zhu, “Joint multioperator virtual network sharing and caching in energy harvesting-aided environmental internet of things,” IEEE Internet Things J., vol. 7, pp. 7689– 7701, Aug. 2020. [13] J. Liang, S. Huang, Y. Qiu, L. Liu, F. Aziz, and M. Chen, “Sustainable virtual network function placement and traffic routing for green mobile edge networks,” IEEE Trans. on Green Commun. and Netw., vol. 4, pp. 1450–1465, Dec. 2024. [14] X. He, S. Wang, X. Wang, S. Xu, and J. Ren, “Age-based scheduling for monitoring and control applications in mobile edge computing systems,” in IEEE INFOCOM, (Virtual), pp. 1–10, May 2022. [15] M. Xiao, Y. Xu, J. Zhou, J. Wu, S. Zhang, and J. Zheng, “AoI-aware incentive mechanism for mobile crowdsensing using stackelberg game,” in IEEE INFOCOM, (New York, USA), pp. 1–10, May 2023. [16] Y. Jiang, J. Liu, I. Humar, M. Chen, S. A. AlQahtani, and M. S. Hossain, “Age-of-information-based computation offloading and transmission scheduling in mobile-edge-computing-enabled IoT networks,” IEEE Internet Things J., vol. 10, pp. 19782–19794, Nov. 2023. [17] X. Ling, J. Gong, R. Li, S. Yu, Q. Ma, and X. Chen, “Dynamic age minimization with real-time information preprocessing for edge-assisted IoT devices with energy harvesting,” IEEE Trans. Netw. Sci. Eng., vol. 8, pp. 2288–2300, Sept. 2021. [18] S. Jayanth and R. V. Bhat, “Age of processed information minimization over fading multiple access channels,” IEEE Trans. on Wirel. Commun., vol. 22, pp. 1664–1676, Mar. 2023. [19] T. Shi, Q. Xu, J. Wang, C. Xu, K. Wu, K. Lu, and C. Qiao, “Enhancing the safety of autonomous driving systems via AoI-optimized task scheduling,” IEEE Trans. Veh. Technol., vol. 74, pp. 3804–3819, Mar. 2025. [20] R. Li, Q. Ma, J. Gong, Z. Zhou, and X. Chen, “Age of processing: Agedriven status sampling and processing offloading for edge-computingenabled real-time IoT applications,” IEEE Internet Things J., vol. 8, pp. 14471–14484, Oct. 2021. [21] X. Chen, C. Wu, T. Chen, Z. Liu, H. Zhang, M. Bennis, and Y. Ji, “Information freshness-aware task offloading in air-ground integrated edge computing systems,” IEEE J. Sel. Areas Commun., vol. 40, pp. 243– 258, Jan. 2022. [22] M. Akbari, A. Syed, W. S. Kennedy, and M. Erol-Kantarci, “Constrained federated learning for AoI-limited SFC in UAV-aided MEC for smart agriculture,” IEEE Trans. on Machine Learning in Commun. and Netw., vol. 1, pp. 277–295, Sept. 2023. [23] M. Akbari, M. R. Abedi, R. Joda, M. Pourghasemian, N. Mokari, and M. Erol-Kantarci, “Age of information aware VNF scheduling in industrial IoT using deep reinforcement learning,” IEEE J. Sel. Areas Commun., vol. 39, pp. 2487–2495, Aug. 2021. [24] K. Peng, P. Xiao, S. Wang, and V. C. Leung, “AoI-aware partial computation offloading in IIoT with edge computing: A deep reinforcement learning based approach,” IEEE Trans. Cloud Comput., vol. 11, pp. 3766–3777, Oct. 2023. [25] X. He, C. You, and T. Q. S. Quek, “Age-based scheduling for mobile edge computing: A deep reinforcement learning approach,” IEEE Trans. on Mob. Comp., vol. 23, pp. 9881–9897, Oct. 2024. [26] S. Wakisaka, Y.-H. Chiang, H. Lin, and Y. Ji, “Timely information updates for the internet of things with serverless computing,” in IEEE ICC, (Rome, Italy), pp. 1–6, June 2021. [27] S. Agarwal, M. Kodialam, and T. V. Lakshman, “Traffic engineering in software defined networks,” in IEEE INFOCOM, (Turin, Italy), pp. 1– 10, Apr. 2013. [28] M.-L. Ku, Y. Chen, and K. J. R. Liu, “Data-driven stochastic models and policies for energy harvesting sensor communications,” IEEE J. Sel. Areas Commun., vol. 33, pp. 1505–1520, Aug. 2015. [29] M. A. Abd-Elmagid, N. Pappas, and H. S. Dhillon, “On the role of age of information in the Internet of things,” IEEE Commun. Mag., vol. 5, pp. 72–77, Dec. 2019. [30] S. Yang, F. Li, S. Trajanovski, R. Yahyapour, and X. Fu, “Recent advances on resource allocation in network function virtualization,” IEEE Trans. Parallel Distrib. Syst., vol. 32, pp. 295–314, Feb. 2021. [31] C. M. Bishop, Pattern Recognition and Machine Learning. Springer, 2006. [32] K. Wang, C. Yang, K.-W. Chin, and J. Xian, “Deep-learning-assisted complete targets coverage in energy-harvesting IoT networks,” IEEE Internet Things J., vol. 12, pp. 17780–17790, June 2025. [33] M. Chen, Y. Sun, H. Hu, L. Tang, and B. Fan, “Energy-saving and resource-efficient algorithm for virtual network function placement with network scaling,” IEEE Trans. Green Commun. Netw., vol. 1, pp. 29–40, Mar. 2021.