In this paper, we present the joint optimization of computation path selection and workload allocation for Directed Acyclic Graph (DAG) tasks in edge computing networks. Existing works primarily focus on end-to-end latency and are often restricted to simple task chains, neglecting critical factors such as server operational costs and the dynamics of arrival of tasks. To bridge this gap, we formulate the online scheduling problem as a mixed integer program to minimize server operational costs and latency.We then decompose this problem into a minimum-latency path selection subproblem and a task scheduling subproblem formulated as a Markov Decision Process (MDP). Our solution consists of a latency-aware transmission scheduling algorithm and a novel online scheduler based on Proximal Policy Optimization (PPO). Furthermore, we leverage Graph Neural Networks (GNNs) and Long Short-Term Memory networks (LSTMs) to encode the system state, thereby significantly improving the agent’s perception of the complex environment. Finally, extensive simulation results demonstrate that the proposed algorithm shows good adaptability and outperforms the state-of-the-art algorithms.

Data collection is a crucial task of IoTs. According to the data collection scheme and the required data granularity, data collection in IoTs can be classified into pull-based/push-based data collection as well as node-level/target-level data collection. Thus, there are four scenarios for data collection: Push-based node-level data collection (Push-Node), Push-based target-level data collection (Push-Target), Pull-based node-level data collection (Pull-Node), and Pull-based target-level data collection (Pull-Target). Energy-Harvesting IoT (EH-IoT) is an important component of IoTs and the Age of Information (AoI) minimization problem has been studied extensively for data collection in EH-IoTs. However, existing works only studied the problem under the scenario of Push-Node, Push-Target and Pull-Node. Therefore, this paper investigates the AoI minimization problem for Pull-based Target-level data collection in EH-IoTs (AoI-Pull-Target) for the first time. AoI-Pull-Target is formally defined and proved to be NP-hard. A two-stage dynamic programming-based node scheduling algorithm and a real-time schedule adjustment scheme are proposed to solve the problem. The proposed algorithm is analyzed theoretically. Extensive simulations and real-world testbed experiments verify the high performance of our algorithm.

Although AI has been extensively adopted and has profoundly transformed our lives, it is not feasible to directly deploy large AI models on edge devices with limited resources. To enhance the performance of Edge Intelligence (EI), model split inference has been proposed. In this approach, an AI model is segmented into sub-models, with the most resource-intensive parts offloaded wirelessly to the edge server. This reduces the resource demands and inference latency on the device. However, previous studies have primarily focused on enhancing and optimizing system Quality of Service (QoS), often overlooking Quality of Experience (QoE), which is another crucial aspect for users. Even though QoE has been extensively studied in Edge Computing (EC), the distinct differences between task offloading in EC and split inference in EI, along with specific QoE issues that remain unaddressed in both fields, render these algorithms ineffective for edge split inference scenarios. Therefore, this paper introduces an effective resource allocation algorithm, dubbed ERA, which aims to: 1) expedite split inference in EI, and 2) balance inference delay, QoE, and resource consumption. ERA incorporates resource consumption, QoE, and inference latency to determine the most optimal model split and resource allocation strategies. Given that it is impossible to simultaneously minimize inference delay and resource consumption while maximizing QoE, we employ a gradient descent-based algorithm to find the best possible compromise. Furthermore, to address the complexity arising from parameter discretization in the gradient descent algorithm, we have developed a pipeline gradient descent approach, known as PipGD. We have also examined the properties of the proposed algorithms, including their convergence, complexity, and approximation error. The experimental results clearly show that ERA outperforms previous studies significantly in terms of performance.

Few-shot knowledge graph completion (FKGC) aims to infer missing triples for long-tail relationships using a small set of References. Existing FKGC models focus mainly on entity representation aggregation, heavily relying on interactions between central entities and their neighbors. However, real-world knowledge graphs contain relations with multiple semantics, and existing models struggle to capture the diverse semantic information of the relations in different contexts. To address this issue, we propose a novel FKGC model, context-aware relational learning and multidimensional matching (CRL-MM). First, CRL-MM enhances the representation of task relations by obtaining semantic information in different scenarios based on the semantic similarity between task relations and background relations. Second, unlike previous models, which rely mainly on neighborhood relations to capture relation information, CRL-MM considers the entity pair and its neighborhood as a unified contextual whole, aggregating neighborhood information through adaptive task relations and paired entity awareness to improve entity encoding. In addition, during the matching phase, we design a matching network from multiple dimensions, which includes not only the similarity score of the entity pairs but also the triple rationality score to further improve the generalizability of the model. Extensive experiments on public benchmark datasets show that CRL-MM outperforms state-of-the-art methods, and the ablation experiments also demonstrate the effectiveness of each module of the proposed CRL-MM.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing at network edges, the recent advances in Mobile Edge Computing (MEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact DT orchestrations. In this paper, we first design a differential privacy-based federated learning framework to build a DT network for DT services in response to user requests in an MEC, thereby enhancing the Quality of Services (QoS). Built upon the proposed framework, we then formulate two novel social-aware DT placement problems: the static social-aware S_DT placement problem, and the dynamic social-aware S_DT placement problem, respectively. We also show the NP-hardness of the defined problems. Then, we formulate an Integer Linear Program (ILP) solution to the static social-aware S_DT placement problem when the problem size is small; otherwise we develop an approximation algorithm with a provable approximation ratio for it. Third, we study the dynamic social-aware S_DT placement problem when requests arrive one by one without the knowledge of future request arrivals over the time horizon, for which we devise an online algorithm with a provable competitive ratio. Finally, we conduct simulations to evaluate the performance of the proposed algorithms. Simulation results show that the proposed algorithms outperform their counterparts, improving the performance compared with their baselines by no less than 14.9%.

ABSTRACT The emerging optical circuit technology, which can establish circuit connections among switches, has been proposed as a promising paradigm for data center networks. This paper investigates the problem of minimizing the completion time of multicast coflows in optical circuit switches (OCSs)‐based data center networks. The existing works either only focused on multicast coflow scheduling or focused solely on circuit scheduling in OCS‐based networks, which greatly limits their performance. Hence, in this paper, we study how to reduce the completion time of multicast coflows by considering circuit scheduling and coflow scheduling simultaneously. First, the problem of multicast coflow scheduling is formulated and proved to be NP‐hard. Then, a Delay‐efficient Multicast Coflow Scheduling (DMCS) algorithm is proposed by integrating multicast coflow scheduling with circuit scheduling. The proposed DMCS algorithm is proved to have an approximation ratio of at most , where represents the number of OCS. Through extensive simulations, it is shown that the proposed DMCS algorithm can achieve high performance compared to state‐of‐the‐art methods.

Age of Information (AoI) has been proposed as a new performance metric to capture the freshness of data. At wireless-powered network edge, the source nodes first need to be charged ready for update transmissions, which means the system AoI is not only decided by the scheduling of update transmissions but also by the designing of charging plan. However, the existing works either only focused on the point of scheduling update transmissions or have a rigid assumption that only one source node can be charged per time. Aiming at making the work more practical and general, we investigate the average AoI optimization problem at wireless-powered network edge with directional charging. Firstly, the theoretical bound of the weighted sum of average AoI of the entire network with a directional charger is analyzed, which is proved to be related to nodes' maximum transmitting interval and the charging strategy. An optimal charging time computation algorithm is proposed to obtain the maximum transmitting interval of each source node by considering the overlapped areas of different charging orientations. After then, an AoI-aware periodical charging scheduling algorithm is proposed to compute a periodical charging schedule while the average AoI is bounded, including a charging period$T$and the charging orientations assigned to each time slot within$T$. The proposed algorithm is proved to have an approximation ratio of up to 1.5625. Furthermore, several approximate algorithms are also proposed for average AoI optimization with multiple chargers and network bandwidth constraint. Finally, the extensive simulations demonstrate the high performance of the proposed algorithm in terms of AoI.

Inferring user status at the edge is essential for delivering personalized services, such as detecting emotional states. However, deploying large-scale models directly on user devices is impractical due to substantial computational overhead and the scarcity of labeled data. Conversely, uploading raw data to the cloud for processing raises significant privacy concerns and incurs prohibitive communication costs. To address this challenge, we propose a privacy-preserving multimodal inference framework that leverages large-scale public data while safeguarding sensitive information and optimizing computational efficiency. Specifically, we first train a teacher model in the cloud using publicly available data. Through a feature distillation process, the knowledge from this teacher model is transferred to a lightweight encoder deployed at the user end. This transfer is tailored to the user's data, ensuring that only relevant knowledge is distilled. To accommodate varying communication constraints, we introduce a feature compression mechanism that significantly reduces communication overhead without compromising inference accuracy. Extensive experiments on emotion recognition tasks demonstrate that the proposed framework effectively balances privacy preservation, resource efficiency, and inference accuracy, facilitating seamless collaboration between cloud and edge devices.

The edge intelligence (EI) has been widely applied recently. Splitting the model between device, edge server, and cloud can significantly improve the performance of EI. The model segmentation without user mobility has been investigated in detail in previous studies. However, in most EI use cases, the end devices are mobile. Few studies have been conducted on this topic. These works still have many issues, such as ignoring the energy consumption of mobile device, inappropriate network assumption, and low effectiveness on adapting user mobility, etc. Therefore, to address the disadvantages of model segmentation and resource allocation in previous studies, we propose mobility and cost aware model segmentation and resource allocation algorithm for accelerating the inference at edge (MCSA). Specifically, in the scenario without user mobility, the loop iteration gradient descent (Li-GD) algorithm is provided. When the mobile user has a large model inference task that needs to be calculated, it will take the energy consumption of mobile user, the communication and computing resource renting cost, and the inference delay into account to find the optimal model segmentation and resource allocation strategy. In the scenario with user mobility, the mobility aware Li-GD (MLi-GD) algorithm is proposed to calculate the optimal strategy. Then, the properties of the proposed algorithms are investigated, including convergence, complexity, and approximation ratio. The experimental results demonstrate the effectiveness of the proposed algorithms.

Wireless Power Transfer technology, which can charge IoT devices over the air, has become a promising technology for IoT networks. In wireless-powered IoT networks, broadcasting is a fundamental networking service for disseminating messages to the whole network. To seek a fast and collision-free broadcast schedule, the problem of Minimum Latency Broadcast Scheduling (MLBS) has been well studied when nodes are energy-abundant. However, in wireless-powered networks, a node can only receive or transmit packets after it has harvested enough energy. In such networks, it is of great importance to exploit the divergent harvested energy to reduce the broadcast latency. Unfortunately, existing works always assume a predetermined tree and a fixed transmission power for broadcast scheduling, which greatly limits their performance. Thus, in this article, we investigate the first work for the MLBS problem in wireless-powered networks without relying on predetermined trees. First, the problem is formulated and proved to be NP-hard. Then, two structure-adaptive scheduling algorithms are proposed with a theoretical bound, which can intertwine the construction of broadcast tree with the computation of an energy-aware schedule simultaneously. Furthermore, a power-aware scheduling method is also proposed to take the structure of the broadcast tree, the adjustment of nodes’ transmission powers, and the interference during transmissions into account simultaneously. Additionally, the algorithm for the MLBS problem under the physical interference model is also studied. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency.

The Internet of Things (IoT) is gathering paces in the new era of Industry 4.0, and the Digital Twin (DT) technology bridges the gap between the bursting amounts of data generated by IoT devices and the user requirements for real-time data processing. DT services maintain living digital models of physical objects, and a DT network enables comprehensive service provisioning with the global knowledge of a group of DTs. On the other hand, exposing serverless computing in network edges, the recent advances in Serverless Edge Computing (SEC) introduce new inspirations to the DT landscape that ensure fine-grained resource management and low network-wide delay of DT services. However, social relationships among IoT devices and DT data privacy impact the orchestration of DTs. In this paper, we design a differential privacy-based federated learning framework to build a DT network for DT services in response to user DT service requests in SEC, thereby enhancing the Quality of Services (QoS). To this end, we first formulate a novel social-aware problem for placing DTs in an SEC network, and show its NP-hardness. We then provide an Integer Linear Program (ILP) solution to the problem when the problem size is small; otherwise, we design an approximation algorithm with a provable approximation ratio. We finally evaluate the algorithm performance through simulations. Simulation results demonstrate the proposed algorithm is promising, which improves by no less than 21.1 % of the performance of benchmarks.

Summary Data broadcast is a fundamental communication pattern in wireless IoT networks, in which the messages are disseminated from a source node to the entire network. The problem of minimum latency broadcast scheduling (MLBS) which is aimed to generate a quick and conflict‐free broadcast schedule has not been extensively explored in duty‐cycled networks. The existing works either work in a centralized scheme or rely on a fixed tree for broadcasting. Additionally, they all employ a strict premise that each node can only utilize one channel for both transmitting and receiving messages. Thus, to address the issues mentioned above, we examine the first distributed broadcasting algorithm in multi‐channel duty‐cycled wireless IoT networks, without relying on a predetermined tree. First, the MLBS problem in such networks is defined and proved to be NP‐hard. Then, in order to avoid transmission conflicts between different links locally, two efficient data structures are designed to help compute the earliest time and channel of receiving messages without conflicts. Based on the above data structures, we introduce an efficient distributed broadcasting algorithm, which can generate a latency‐sensitive broadcast tree while calculating a collision‐free broadcast schedule, simultaneously. Finally, the theoretical analysis and simulations demonstrate the efficiency of the proposed algorithm.

Driven by data and models, the digital twin technique presents a new concept of optimizing system design, process monitoring, decision-making and more, through performing comprehensive virtual-reality interaction and continuous mapping. By introducing serverless computing to Mobile Edge Computing (MEC) environments, the emerging serverless edge computing paradigm facilitates the communication-efficient digital twin services and promises agile, fine-grained and cost-efficient provisioning of limited edge resources, where serverless functions are implemented by containers in cloudlets (edge servers). However, the nonnegligible cold start delay of containers deteriorates the responsiveness of digital twin services dramatically and the perceived user service experience. In this paper, we investigate delay-sensitive query service provisioning in digital twin-empowered serverless edge computing by considering user mobility. With digital twins of users deployed in the remote cloud, referred to as primary digital twins, we deploy their digital twin replicas based on serverless functions in cloudlets to mitigate the query service delay while enhancing user service satisfaction that is expressed as a utility function. We study two optimization problems with the aim of maximizing the accumulative utility gain: the digital twin replica placement problem per time slot, and the dynamic digital twin replica placement problem over a finite time horizon. We first formulate an Integer Linear Program (ILP) solution for the digital twin replica placement problem when the problem size is small; otherwise, we propose an approximation algorithm for the problem with a provable approximation ratio. We then design an online algorithm for the dynamic digital twin replica placement problem, and a performance-guaranteed online algorithm for a special case of the problem by assuming each user issues a query at each time slot. Finally, we evaluate the performance of the proposed algorithms for placing digital twin replicas in MEC networks through simulations. The results demonstrate the proposed algorithms are promising, outperforming their counterparts.

By combining edge computing and parallel computing, distributed edge computing has emerged as a new paradigm to exploit the booming IoT devices at the edge. To accelerate computation at the edge,i.e., the inference tasks for DNN-driven applications, the parallelism of both computation and communication needs to be considered for distributed edge computing, and thus, the problem of Minimum Latency joint Communication and Computation Scheduling (MLCCS) is proposed. However, existing works have rigid assumptions that the communication time of each device is fixed and the workload can be split arbitrarily small. Aiming at making the work more practical and general, the MLCCS problem without the above assumptions is studied in this paper. Firstly, the MLCCS problem under a general model is formulated and proved to be NP-hard. Secondly, a pyramid-based computing model is proposed to consider the parallelism of communication and computation jointly, which has an approximation ratio of$1+\delta$, where$\delta$is related to devices' communication rates. An interesting property under such a computing model is identified and proved,i.e., the optimal latency can be obtained under arbitrary scheduling order when all the devices share the same communication rate. When the workload cannot be split arbitrarily, an approximation algorithm with a ratio of at most$2\cdot (1+\delta )$is proposed. Additionally, for handling the dynamically changing network scenarios, several algorithms are also proposed accordingly. Finally, the theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency. Two testbed experiments are also conducted, which show that the proposed method outperforms the existing methods, reducing the latency by up to 29.2% for inference tasks at the edge.

Iteration based collaborative learning (CL) paradigms, such as federated learning (FL) and split learning (SL), faces challenges in training neural models over the rapidly growing yet resource-constrained edge devices. Such devices have difficulty in accommodating a full-size large model for FL or affording an excessive waiting time for the mandatory synchronization step in SL. To deal with such challenge, we propose a novel CL framework which adopts an tree-aggregation structure with an adaptive partition and ensemble strategy to achieve optimal synchronization and fast convergence at scale. To find the optimal split point for heterogeneous clients, we also design a novel partitioning algorithm by minimizing the idleness during communication and achieving the optimal synchronization between clients. In addition, a parallelism paradigm is proposed to unleash the potential of optimum synchronization between the clients and server to boost the distributed training process without losing model accuracy for edge devices. Furthermore, we theoretically prove that our framework can achieve better convergence rate than state-of-the-art CL paradigms. We conduct extensive experiments and show that our framework is 4.6× in training speed as compared with the traditional methods, without compromising training accuracy.

Mobile Edge Computing (MEC) has been identified as a desirable computing paradigm that provides efficient and effective services for various applications, while meeting stringent service delay requirements. Orthogonal to the MEC computing paradigm, Network Function Virtualization (NFV) technology is another enabling technology that provides the network resource management with great flexibility and scalability, where the instances of Virtual Network Functions (VNFs) are deployed in edge servers as Service Function Chains (SFCs) for SFC-enabled services. Although reliable service provisioning in MEC environments is fundamentally important, the deployed VNF instances usually are not reliable, which can be affected by their software implementation, their execution duration, the workload among edge servers, and so on. Empowered by digital twin techniques, the states of VNF instances can be maintained by their digital twins in a real-time manner and their reliability can be accurately predicted through their digital twins. In this paper, we study digital twin-assisted, SFC-enabled reliable service provisioning in MEC networks by exploiting the dynamics of VNF instance reliability. We concentrate on two novel optimization problems of reliable service provisioning: the service cost minimization problem, and the dynamic service admission maximization problem. We first show their NP-hardness. We then formulate an Integer Linear Program (ILP) solution, and devise an approximation algorithm with a constant approximation ratio for the service cost minimization problem. We thirdly provide an ILP solution to the offline version of the dynamic service admission maximization problem. Built upon this offline ILP solution, we also develop an online algorithm with a provable competitive ratio for the problem, by adopting the primal-dual dynamic updating technique. We finally evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms outperform their comparison benchmarks, and improve the performance of their comparison counterparts by no less than$10.2 \%$.

Digital twins are poised to enter our lives with Industry 4.0. The Digital Twin Network (DTN) paradigm is projected to deliver upon the promise of efficient collaboration among digital twins to enable complicated and systematic services across many domains, through depicting an overall picture of a group of physical objects. To achieve timely data processing of digital twins, Mobile Edge Computing (MEC) shifts the computational power towards the network edge, and network slicing is well-suited to bundle heterogeneous physical resources to build logical networks based on edge servers for accommodating DTNs. In light of this, in this paper we investigate DTN slicing-enabled service provisioning in MEC, where each DTN slice consists of one master digital twin and a set of worker digital twins, and each worker digital twin is synchronized through collecting data from a respective object periodically. The master digital twin aggregates the processed data from worker digital twins to model the DTN continuously for user query services, whilst meeting delay requirements of users. We capture the utility gain of a DTN slicing request based on the DTN model quality at its master digital twin that is impacted by the Age of Information (AoI), and we focus on two novel optimization problems: the utility maximization problem for a single DTN slicing request, and the dynamic utility maximization problem for multiple DTN slicing requests. We propose an approximation algorithm for the former, and an online algorithm with a provable competitive ratio for the latter. We also evaluate the performance of the proposed algorithms through simulations. Experimental results demonstrate that the proposed algorithms are promising, outperforming their counterparts by at least 10.2%.

Propelled by recent advances in Mobile Edge Computing (MEC) and the Internet of Things (IoT), the digital twin technique has been envisioned as a de-facto driving force to bridge the virtual and physical worlds through creating digital portrayals of physical objects. In virtue of the flourishing of edge intelligence and abundant IoT data, data-driven modelling facilitates the implementation and maintenance of digital twins, where simulations of physical objects are usually performed based on Deep Neural Networks (DNNs). A significant advantage of adopting digital twins is to enable decisive prediction on the behaviours of objects in near future without waiting for that really happen. To provide accurate predictions, it is vital to keep each digital twin synchronized with its physical object in real-time. However, it is challenging to maintain the real-time synchronization between a digital twin and its physical object due to the dynamics of physical objects and sensing data drift over time, i.e., the live data from a physical object diverge from the model training data of its digital twin. To address this critical issue, continual learning is a promising solution to retrain models of digital twins incrementally. In this paper, we investigate digital twin synchronization issues via continual learning in an MEC environment, with the aim to maximize the total utility gain, i.e., the enhanced model accuracy. We study two novel optimization problems: the static digital twin synchronization problem per time slot and the dynamic digital twin synchronization problem for a finite time horizon. We first formulate an Integer Linear Program (ILP) solution for the static digital twin synchronization problem when the problem size is small; otherwise, we develop a randomized approximation algorithm at the expense of bounded resource violations for it. We also devise a deterministic approximation algorithm with guaranteed performance for a special case of the static digital twin synchronization problem. We thirdly consider the dynamic digital twin synchronization problem by proposing an efficient online algorithm for it. Finally, we evaluate the performance of the proposed algorithms for continuous digital twin synchronization through simulations. Simulation results show that the proposed algorithms are promising, outperforming counterpart benchmarks by no less than 13.2%, in terms of the total utility gain.

Packet loss inferring can enable a transceiver to distinguish between channel impairment and collision for transmission failures, and thus can improve the network performance by exclusively performing rate adaptation or adjusting the medium access parameter. Machine learning methods from literature have shown great potential in producing models that can detect the loss causes over various network trace, however haven't considered accurate data-driven loss inferring on resource-constrained devices that cannot accommodate deep models. In this paper, we propose a novel packet loss inferring framework that can train lightweight models to distinguish between channel losses and collisions by learning the data trace from both simulation and real devices. Specifically, we first train a sophisticated teacher model based on extensive simulation datasets, whose knowledge is then transferred to a small student model that can be deployed on tiny device. The simulation-reality distillation is conducted via personalized trace from each client correspondingly, whose performance bound is analytically guaranteed. We have implemented our method on real testbed and show that the network access performance can be significantly improved, especially for sudden network variations.

Age of Information, which emerged as a new metric to quantify the freshness of information, has attracted increasing interests recently. To optimize the system AoI, most existing works try to compute an efficient schedule from the point of data transmission. Unfortunately, at wireless-powered network edge, the charging schedule of the source nodes also needs to be decided besides data transmission. Thus, in this paper, we investigate the joint scheduling problem of data transmission and energy replenishment to optimize the maximum peak AoI at network edge with directional chargers. To the best of our knowledge, this is the first work that considers such two problems simultaneously. Firstly, the theoretical bounds of the maximum peak AoI with respect to the charging latency are derived. Secondly, for the minimum peak AoI scheduling problem with a single charger, an optimal scheduling algorithm is proposed to minimize the charging latency, and then a data transmission scheduling strategy is also given to optimize the maximum peak AoI. The proposed algorithm is proved to have a constant approximation ratio of up to 1.5. As for the scenario with multiple chargers, an approximate algorithm is also proposed to minimize the charging latency and the maximum peak AoI. Additionally, when the network bandwidth constraint is considered, the algorithm which considers the parallelism of the charging process and data transmission process is also proposed to reduce the latency and the maximum peak AoI. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency and AoI.

The emerging digital twin technique enhances the network management efficiency and provides comprehensive insights on network performance, through mapping physical objects to their digital twins. The user satisfaction on digital twin-enabled service relies on the freshness of digital twin data, which is measured by the Age of Information (AoI). Due to long service delays, the use of the remote cloud for delay-sensitive service provisioning faces serious challenges. Mobile Edge Computing (MEC), as an ideal paradigm for delay-sensitive services, is able to realize real-time data communication between physical objects and their digital twins at the network edge. However, the mobility of physical objects and dynamics of user query arrivals make seamless service provisioning in MEC become challenging. In this paper, we investigate dynamic digital twin placements for improving user service satisfaction in MEC environments, by introducing a novel metric to measure user service satisfaction based on the AoI concept and formulating two user service satisfaction enhancement problems: the static and dynamic utility maximization problems under static and dynamic digital twin placement schemes. To this end, we first formulate an Integer Linear Programming (ILP) solution to the static utility maximization problem when the problem size is small; otherwise, we propose a performance-guaranteed approximation algorithm. We then propose an online algorithm with a provable competitive ratio for the dynamic utility maximization problem, by considering dynamic user query services. Finally, we evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the algorithm performance by at least$10.7\%$, compared to the baseline algorithms.

The Mobile Edge Computing (MEC) paradigm gives impetus to the vigorous advancement of the Internet of Things (IoT), through provisioning low-latency computing services at network edges. The emerging digital twin technique has been explosively growing in the IoT community, which bridges the gap between physical objects and their digital representations in an MEC network, enabling real-time monitoring and analysis, simulations on the dynamics of systems, accurate predictions on behaviours of objects, and optimization on network resource allocation. In this paper, we consider AoI-aware query services in an MEC network empowered by digital twin technology for diverse IoT applications. We aim to maximize the weighted sum of the accumulative freshness of query results measured by the Age of Information (AoI) and the total query service delay of admitted requests. To this end, we first formulate a novel minimization problem that explores nontrivial trade-offs between the two conflicting optimization objectives: the freshness of query results and service delays, and we show the NP-hardness of the problem. Then, we propose an approximation algorithm with a provable approximation ratio for the problem, at the expense of bounded computing capacity violations. We also develop a heuristic for the problem without any capacity violations. We finally evaluate the performance of the proposed algorithms via simulations. The simulation results demonstrate that the proposed algorithms are promising, and outperform the comparison benchmarks.

Age of Information (AoI) has emerged as a new metric to measure data freshness from the destination's perspective. To optimize the system AoI, most existing works focused on the point of scheduling of update transmissions. While at wireless-powered network edge, the source nodes can only transmit their updates after being charged ready, which means the system AoI is not only determined by the update transmission strategies, but also the charging strategies. Thus, in this paper, we investigate the first work to optimize the weighted peak AoI from the point of charging at wireless-powered network edge. Firstly, the problem of optimizing the weighted sum of average peak AoI with a directional charger is formulated, and then transformed to a charging time optimization problem with respect to the charging orientations and peak AoI, and an approximate algorithm is proposed to obtain the required charging time for each source node. Secondly, an age-based scheduling algorithm is proposed to compute the charging decisions and transmission decisions simultaneously, which can not only optimize the weighted sum of average peak AoI, but also guarantee the maximum peak AoI of each source node is bounded. The proposed algorithm is proved to have an approximation ratio of up to (1+$\varphi$), where$\varphi$is a small value related to the weight of each source node. When there exist multiple chargers, an approximate algorithm is also proposed to minimize the weighted sum of average peak AoI by scheduling the orientations of these chargers cooperatively. Finally, the extensive simulations demonstrate the high performance of the proposed algorithms in terms of peak AoI.

By combing edge computing and parallel computing, distributed edge computing has emerged as a new paradigm to accelerate computation at the edge. Considering the parallelism of both computation and communication, the problem of Minimum Latency joint Communication and Computation Scheduling (MLCCS) is studied recently. However, existing works have rigid assumptions that the communication time of each device is fixed and the workload can be split arbitrarily small. Aiming at making the work more practical and general, the MLCCS problem without the above assumptions is studied in this paper. Firstly, the MLCCS problem under a general model is formulated and proved to be NP-hard. Secondly, a pyramid-based computing model is proposed to consider the parallelism of communication and computation jointly, which has an approximation ratio of 1 + δ, where δ is related to devices’ communication rates. An interesting property under such computing model is identified and proved, i.e., the optimal latency can be obtained under arbitrary scheduling order when all the devices share the same communication rate. When the devices own different communication rates, the optimal scheduling order is also obtained. Additionally, when the workload cannot be split arbitrarily, an approximation algorithm with ratio of at most 2 (1 + δ) is proposed. Finally, the theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency. Two testbed experiments are also conducted, which show that the proposed method outperforms the existing methods, reducing the latency by up to 29.2% in real-world applications.

The emerging digital twin technique enhances the network management efficiency and provides comprehensive insights, through mapping physical objects to their digital twins. The user satisfaction on digital twin-enabled query services relies on the freshness of digital twin data, which is measured by the Age of Information (AoI). Because the remote cloud faces challenges in providing data for users due to long service delays, Mobile Edge Computing (MEC), as a promising technology, offers real-time data communication between physical objects and their digital twins at the edge of the core network. However, the mobility of physical objects and dynamic query arrivals make efficient service provisioning in MEC become challenging. In this paper, we investigate the dynamic digital twin placement for improving user service satisfaction in MEC environments. We focus on two user service satisfaction augmentation problems under both static and dynamic digital twin placement schemes: the static and dynamic utility maximization problems. We first formulate an Integer Linear Programming (ILP) solution to the static utility maximization problem when the problem size is small; otherwise, we propose a performance- guaranteed approximation algorithm for it. We then devise an online algorithm for the dynamic utility maximization problem with a provable competitive ratio. Finally, we evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, and the performance improvement is no less than 11.6%, compared with the baseline algorithms.

Age of Information, which emerged as a new performance metric to quantify the data freshness, has drawn increasing interests recently. At wireless-powered network edge, the source nodes can only transmit their updates after being charged ready, which means the system AoI is not only determined by the update transmission strategies, but also the charging strategies. However, the existing works either only focused on the point of scheduling of update transmissions or have a rigid assumption that only one source node can be charged per time. Aiming at making the work more practical and general, we investigate the average$A$oI optimization problem at wireless-powered network edge without such limitations in this paper. Firstly, the lower bound of the weighted sum of average$A$oI of the whole network with a directional charger is analyzed, which is proved to be related to nodes' maximum transmitting interval and the charging strategy. An optimal charging time allocation algorithm is proposed to obtain the maximum transmitting interval of each source node by considering the overlapped areas of different charging orientations. After then, an AoI-aware periodical charging scheduling algorithm is proposed, which can obtain a periodical charging schedule including a charging period$T$and the charging orientation assigned to each time slot within$T$, while the average AoI is bounded. The proposed algorithm is proved to have an approximation ratio of up to 1.5625. Finally, the extensive simulations demonstrate the high performance of the proposed algorithm in terms of AoI.

Multicast is a fundamental function in network traffic engineering, allowing data traffic to be delivered from the source node to multiple destinations efficiently. To ensure the reliability and security of data traffic, NFV-enabled multicast (Network Function Virtualization) has emerged as a promising technology to reduce deployment and maintenance costs in mobile edge clouds, and has drawn extensive researching interests recently. However, existing works all assume that the Service Function Chain (SFC) follows a fixed-order, which greatly limits its application. Therefore, in this paper, we propose the first work to address the sequential SFC embedding problem without a fixed order for NFV-enabled multicasting in mobile edge clouds. Firstly, we formulate such a minimum cost SFC embedding problem and prove it to be NP-hard. Secondly, we propose a min-path breadth-first based progressive embedding algorithm (MBPE) for NFV-enabled multicasting, which achieves an approximation ratio of 1+K, where K represents the approximation ratio of the Steiner tree problem. Finally, the experiments demonstrate the high efficiency of the proposed method compared to the state-of-the-art algorithms.

Battery-free wireless sensor network (BF-WSN) (including energy harvesting network and energy rechargeable network) is a new network architecture that has been proposed in recent years to solve the lifetime limitation problem of conventional WSNs. Battery-free sensor nodes can harvest energy from environmental energy resources or from artificial power stations. Thus, the lifetime of a BF-WSN is unlimited in terms of energy. The specific properties of BF-WSNs have brought new challenges in fundamental issues, such as energy management, networking, and data acquisition, which means the existing algorithms in WSNs cannot be adopted directly. The BF-WSN can be regarded as a totally new topic in Internet of Things (IoT) and has attracted much attention from researchers. Many algorithms have been proposed to solve the fundamental problems in BF-WSNs. The objective of this survey is to comprehensively summarize and analyze the existing works. In this survey, we first introduce the existing algorithms from three fundamental aspects, including energy management, networking, and data acquisition. Then, we present some specific applications of BF-WSNs.

In recent years, the flourishing of Wireless Power Transfer (WPT) technology brings Wireless Sensor Networks (WSNs) a renewable, reliable, and controllable energy source. To achieve high efficiency, WPT and sensors both adopt directional antennas. Most previous works about directional charging optimize overall charging efficiency, but neglect energy scheduling on nodes for optimizing tasks. This disadvantage may cause a serious imbalance between the energy supply and task loads. This article takes both aspects into consideration. To achieve an overall performance improvement, we jointly schedule rotatable chargers and allocate tasks to nodes in a WSN powered by directional chargers. As far as we know, this is the first work to propose the Task-oriented Energy Scheduling (TOES) problem, i.e., given a set of rotatable directional chargers and some wireless rechargeable sensor nodes, scheduling chargers and nodes to maximize the total utility gained from a set of tasks. We prove the NP-Hardness of TOES. Then we design a 4-approximation algorithm for TOES by jointly solving two subproblems of the original one. We further extend this problem to the windowed task model and propose a \(\frac{4}{1-\gamma }\) approximation algorithm for it, where γ is the proportion of the rotating period. Finally, extensive simulation results show that our algorithms outperform baselines by at least 40.3%.

Age of Information (AoI) has emerged as a new metric to measure data freshness from the destination’s perspective. The problem of optimizing AoI has been attracting extensive interests recently. However, existing works mainly focused on scheduling data transmission for AoI optimization. While at wireless-powered network edge, the charging plan of source nodes also requires to be computed in advance, which means the system AoI is determined by not only the data transmission decision but also the charging plan. Thus, in this paper, we investigate the first work to optimize the weighted peak AoI from the point of charging at wireless-powered network edge with a directional charger. Firstly, to minimize the weighted sum of average peak AoI, the AoI minimization problem is transformed to a charging time optimization problem with respect to the overlapped charging areas and average peak AoI, and an approximate algorithm is proposed to obtain the required charging time for each source node. Then, an age-based scheduling algorithm is proposed to compute the charging and data transmission decisions for each source node simultaneously, which can not only optimize the weighted sum of average peak AoI but also guarantee the maximum peak AoI for each source node. The proposed algorithm is proved to have an approximation ratio of up to (1+φ), where φ is a much smaller value related to the weight of each source node. Finally, the simulation results verify the high performance of proposed algorithms in terms of average and maximum peak AoI.

Age of Information (AoI), emerged as a new metric to quantify the data freshness, has attracted increasing interests recently. Most existing works try to optimize the system AoI from the point of data transmission. Unfortunately, at wireless-powered network edge, the charging schedule of the source nodes also needs to be decided besides data transmission. Thus, in this paper, we investigate the joint scheduling problem of data transmission and energy replenishment to optimize the peak AoI at network edge with directional chargers. To the best of our knowledge, this is the first work that considers such two problems simultaneously. Firstly, the theoretical bounds of the peak AoI with respect to the charging latency are derived. Secondly, for the minimum peak AoI scheduling problem with a single charger, an optimal scheduling algorithm is proposed to minimize the charging latency, and then a data transmission scheduling strategy is also given to optimize the peak AoI. The proposed algorithm is proved to have a constant approximation ratio of up to 1.5. When there exist multiple chargers, an approximate algorithm is also proposed to minimize the charging latency and peak AoI. Finally, the simulation results verify the high performance of proposed algorithms in terms of AoI.

Battery-free wireless sensor networks (BF-WSNs) extend the lifetime of wireless sensor networks (WSNs) using ambient energy sources. Thus, it becomes an emerging research area of Internet of Things (IoT) in recent years. Although many existing works in this area study data collection, few of them focus on optimizing the latency of data collection. In this article, we propose a novel distributed framework (DCF) for low-latency data collection in BF-WSNs. DCF uses an adaptive routing strategy, so battery-free nodes can select receivers depending on their status. It also provides transmitting opportunities for as many nodes as possible in each time slot to achieve high spatial parallelism. We also propose two strategies embedded in DCF to generate local schedules. These strategies allow nodes to determine their schedules based only on information from neighboring nodes. We then analyze the theoretical latency bounds of DCF with and without algorithm parameters, respectively. By comparing with the bound of the existing method, we conclude that the latency bound of DCF is superior. Finally, extensive simulations show that DCF significantly outperforms the existing method.

Entity linking (EL) is a fundamental task in natural language processing. Based on neural networks, existing systems pay more attention to the construction of the global model, but ignore latent semantic information in the local model and the acquisition of effective entity type information. In this paper, we propose two adaptive features, in which the first adaptive feature enables the local and global models to capture latent information, and the second adaptive feature describes effective information for entity type embeddings. These adaptive features can work together naturally to handle some uncertain entity type information for EL. Experimental results demonstrate that our EL system achieves the best performance on the AIDA-B and MSNBC datasets, and the best average performance on out-domain datasets. These results indicate that the proposed adaptive features, which are based on their own diverse contexts, can capture information that is conducive for EL.

With advances in wireless power transfer techniques, battery-free wireless sensor networks (BF-WSNs) which can support long-term applications, has been attracting increasing interests in recent years. Unfortunately, the problem of minimum latency aggregation scheduling (MLAS) is not well studied in BF-WSNs. Existing works always have a rigid assumption that there is only one single query which is targeted at the whole network. Aiming at making the work more practical and general, we investigate the general MLAS problem in BF-WSNs, which is targeted at any subset of nodes in the network and aimed for an arbitrary number of aggregation queries. First, the general MLAS problem when there is one single query is studied. To control the number of nodes participating in the aggregation process, a node selection algorithm is proposed to cover and connect the whole target nodes. Then, a latency and energy aware scheduling algorithm is proposed to integrate the construction of aggregation tree with the chosen nodes, and the computation of a conflict-free schedule simultaneously, relying on non-predetermined structures. Second, the general MLAS problem when there is a group of aggregation queries is studied. Through designing some special structures to avoid collisions between both current and existing aggregation schedules, an algorithm without any waiting time is proposed. Additionally, the algorithm under physical interference model and dynamic energy arrival model are also presented. The theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency and energy efficiency.

Broadcasting is an essential operation in wireless networks for disseminating the message from the source node to all other nodes. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless sensor networks is not well studied. In existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, where a tree-based structure is used as the input of the scheduling algorithm. Relying on a pre-determined tree may result in a much large latency even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled WSNs without the above limitation is investigated in this paper. First, to avoid relying on a pre-determined structure, a two-step scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. To the best of our knowledge, this is the first work that can integrate these two kinds of operations together. Second, a novel transmission mode, i.e., concurrent broadcasting, is first introduced for wireless networks and several techniques are designed to further improve the broadcast latency. Third, the multiple messages broadcasting and all-to-all broadcasting algorithms, which can generate a series of broadcast schedules independently without a pre-determined tree, are also proposed by taking care of the collisions in both the current and the previous broadcast schedules. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in terms of latency.

Battery-free wireless sensor networks (BF-WSNs) have captured the interest of research community in recent years. Compared with traditional battery-powered WSNs (BP-WSNs), BF-WSNs can prolong the lifetime of the network by exploiting ambient energy. Many-to-many communication is widely used in many applications of WSNs and the problem of minimum-latency many-to-many communication scheduling in BF-WSNs is of great significance. However, this problem has not been studied yet. The existing algorithms for BP-WSNs and BF-WSNs are not suitable for minimum-latency many-to-many scheduling problem in BF-WSNs. Also, different from BP-WSNs, energy-bottleneck nodes with low recharge rate and high workload in BF-WSNs make the problem more challenging. To address these issues, in this article, we first study the problem of many-to-many scheduling in BF-WSNs with the purpose of minimizing communication latency. The problem is formally defined and proved to be NP-hard. The energy-adaptive and bottleneck-aware scheduling algorithm for many to many in BF-WSNs is proposed. The correctness and average latency of the proposed algorithm are carefully analyzed. Extensive simulations show that our algorithm has high performance, in terms of communication latency and energy usage ratio. Furthermore, we also extend the proposed algorithm to other network models.

Data aggregation is a fundamental yet popular operation in wireless networks where the sink needs to obtain the combined information of the whole network. However, the problem of minimum latency aggregation scheduling (MLAS) is not well studied in cognitive radio networks. Few studies have addressed this issue and most previous aggregation methods all assume that a fixed-structure based aggregation tree is constructed in advance, which may result in the selection of a node with limited spectrum opportunities as the parent by many nodes and by extension results in a large latency. Thus, the MLAS problem in cognitive radio networks (MLAS-CR) without the above limitation is investigated in this paper. First, the MLAS-CR problem with primary social behaviors where the activity of primary users can be predicted is studied. To make full use of the limited spectrum opportunities, we integrate the construction of the aggregation tree, and the computation of a conflict-free schedule simultaneously, without any predetermined structures. Second, the MLAS-CR problem without the above assumption is also investigated. To reduce the latency, a two-way aggregation scheduling method is proposed to adaptively choose the parent with only current channel information. To further reduce the latency, we also introduce a new data aggregation mode for CRN, i.e., Data Aggregation Scheduling in The Dark, to utilize the spectrum opportunities of scheduled nodes. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency.

The emerging energy-harvesting technology enables charging sensor batteries with renewable energy sources, which has been effectively integrated into Wireless Sensor Networks (EH-WSNs). Due to the limited energy-harvesting capacities of tiny sensors, the captured energy remains scarce and differs greatly among nodes, which makes the data aggregation scheduling problem more challenging than that in energy-abundant WSNs. In this article, we investigate the Minimum Latency Aggregation Scheduling (MLAS) problem in EH-WSNs. First, we identify a new kind of collision in EH-WSNs, named as energy-collision, and design several special structures to avoid it during data aggregation. To reduce the latency, we try to choose the parent adaptively according to nodes’ transmission tasks and energy-harvesting ability, under the consideration of collisions avoidance. By considering transmitting time, residual energy, and energy-collision, three scheduling algorithms are proposed under protocol interference model. Under physical interference model, several approximate algorithms are also designed by taking account of the interference from the nodes several hops away. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency.

Battery-Free Wireless Sensor Networks (BF-WSNs) have been attracting increasing interests in the recent years. To reduce the latency in BF-WSNs, the Minimum Latency Aggregation Scheduling (MLAS) problem with coverage requirement q is proposed recently, which tries to choose q percent of nodes for communication and aggregation. In the existing method, the authors try to select nodes adaptively according to their energy status and schedule these nodes to achieve the minimum latency. Unfortunately, it cannot guarantee the distribution of the aggregated nodes and may result in these nodes being squeezed in a small area and a poor aggregation quality. Thus, we re-investigate the q-coverage MLAS problem in this article, which can guarantee that the aggregated nodes are distributed evenly. Firstly, the 1-coverage MLAS problem, in which each node can be covered by at least one aggregated node, is studied. To reduce the latency, we intertwine the selection of aggregated nodes and the computation of a collision-free communication schedule simultaneously. Two algorithms are proposed by scheduling the communication tasks in the bottom-up and top-down manner respectively. Secondly, to satisfy the arbitrary coverage requirement q, three algorithms are proposed to guarantee the aggregated nodes are evenly distributed in the network with a low latency. Additionally, the method to extend the proposed algorithms for the BF-WSNs with multiple channels is also studied. The theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency.

Broadcasting is a fundamental networking service where the source node tries to disseminate the message to the whole network. The problem of Minimum Latency Broadcast Scheduling (MLBS) which seeks a fast and collision-free broad-cast schedule has been well studied when nodes are energy-abundant. However, in battery-free wireless networks, node can only receive or transmit packets after it has harvested enough energy. In such networks, it is of great importance to exploit the harvested energy smartly to reduce broadcast latency. Un-fortunately, the existing works rely on predetermined structures may greatly increase the latency by choosing a node with large charging latency as the backbone node. In addition, they assume each node can only transmit once which may result in much waiting latency. To address the above issues, we investigate the MLBS problem in battery-free wireless networks without predetermined structures in this paper. Firstly, to make use of the harvested energy smartly, we intertwine the construction of broadcast tree and the computation of an energy-satisfied and collision-free schedule. Secondly, a Delayed Broadcasting technique is proposed for each node to tradeoff between the number of transmissions and its waiting latency. By considering residual energy and transmitting time, two latency and energy aware scheduling algorithms are proposed, in which the broadcast tree can be constructed adaptively according to nodes' energy status. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of broadcast latency.

Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally. Unfortunately, the problem Minimum Latency Beaconing Schedule (MLBS) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MLBSDCA for short) is investigated in this paper. First, a novel kind of coloring problem, named as label coloring problem, is identified and analyzed. Second, an edge-based scheduling framework is designed and the MLBSDCA under protocol interference model is transformed to such coloring problem. Based on label coloring, a group first-fit scheduling algorithm is designed for MLBSDCA under protocol interference model. After that, a (ρ + 1)2|W|-approximation algorithm is proposed to further reduce the beaconing latency, where p denotes the interference radius, and |W| is the maximum number of active time slots per working cycle. When p and |W| is equal to 1, the approximation ratio is only 4, which is better than the one (i.e., 10) in existing works. Furthermore, two approximation algorithms for MLBSDCA under physical interference model are also investigated. The theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.

Broadcasting is a fundamental networking service where the source node disseminates the message to all the other nodes. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless networks is not well studied. In the existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, which may result in a bad-structured broadcast tree and then a large latency is obtained even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled wireless networks without above limitation is investigated in this paper. Firstly, a Two-Step Scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. The proposed method can generate a latency-aware broadcast tree adaptively to reduce the broadcast latency. To the best of our knowledge, this is the first work that can integrate these two kinds of operations together. Additionally, a novel transmission mode, i.e., concurrent broadcasting, is first introduced in wireless networks and several techniques are designed to further improve the broadcast latency. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.

Thanks to the recent advances in energy-harvesting devices, nodes equipped with such devices are produced and enable Wireless Sensor Networks (WSNs) to be energy self-sustainable. Such networks are named as Battery-Free WSNs (BF-WSNs). Data aggregation is an essential operation in WSNs, and the Minimum Latency Aggregation Scheduling (MLAS) problem which seeks a collision-free aggregation scheduling with the minimum latency has been well studied in Battery-Powered WSNs (BP-WSN). In BP-WSNs, latency is mainly caused by the time overhead in collision-avoiding. However, the time-consumption for node recharging is the main cause of latency in BF-WSNs. Moreover, the collisions are time-independent while the recharge rate is time-varying. Therefore, the previous algorithms are not suitable for BF-WSNs. In addition, if aggregating data from all nodes, the latency would be determined by the node with the lowest recharge rate. Thus, we propose to aggregate a subset of nodes which can meet the given coverage quality requirement. Meanwhile, the aggregation tree and scheduling strategy should be adaptive to the current energy condition. We formulate this problem and propose a distributed algorithm which can select nodes adaptively according to their energy condition and schedule these nodes to achieve the minimum latency, simultaneously. To the best of our knowledge, it is the first distributed algorithm to solve the MLAS problem with coverage guarantee in BF-WSNs. The simulation results verify that our algorithm can reduce aggregation latency effectively, especially in bad energy condition.

Broadcasting is a fundamental function for disseminating messages in multihop wireless networks. Minimum-Transmission Broadcasting (MTB) problem aims to find a broadcast schedule with minimum number of transmissions. Previous works on MTB in duty-cycled networks exploit a rigid assumption that nodes have only active time slot per working cycle. In this paper, we investigated the MTB problem in duty-cycled networks where nodes are allowed arbitrary active time slots per working cycle (MTBDCA problem). Firstly, it is proved to be NP-hard and o(ln⁡Δ) -inapproximable, where Δ is the maximum degree in the network. Secondly, an auxiliary graph is proposed to integrate nodes’ active time slots into the network and a novel covering problem is proposed to exploit nodes’ multiple active time slots for scheduling. Then, a ln⁡(Δ+1) -approximation algorithm is proposed for MTBDCA and a (ln⁡(Δ+1)+Δ) -approximation algorithm is proposed for all-to-all MTBDCA. Finally, extensive experimental results demonstrate the efficiency of the proposed algorithm.

The emerging energy harvesting technology enables charging sensor batteries with renewable energy sources, which has been effectively integrated into Wireless Sensor Networks (EH-WSNs). Meanwhile, data aggregation is an essential operation in a WSN. The problem of Minimum Latency Aggregation Scheduling (MLAS) which seeks a fast and collision-free aggregation schedule has been well studied when nodes are energy-abundant. However, due to the limited energy harvesting capacities of tiny sensors, the captured energy remains scarce and differs greatly among nodes. Thus, all of the previous algorithms for MLAS are not suitable in EH-WSNs. In this paper, we investigate the MLAS problem in EH-WSNs. To make use of the harvested energy smartly, we construct an aggregation tree adaptively according to the residual battery level at each node. Furthermore, we identify a new kind of collision, named as energy -collision, and design a special structure to assist in avoiding it. By considering transmitting time, residual energy, and energy-collision, we propose three scheduling algorithms for MLAS problem in EH-WSNs. The theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of aggregation latency compared with the baseline methods.

Data aggregation is an essential operation for the sink to obtain summary information in a Wireless Sensor Network (WSN). The problem of Minimum Latency Aggregation Schedule (MLAS) which seeks a fastest and collision-free aggregation schedule has been well studied when nodes are always awake. However, in duty-cycle WSNs, nodes can only receive data in active state. In such networks, it is of great importance to exploit the limited active time slots to reduce aggregation latency. Unfortunately, few studies have addressed this issue and most previous aggregation methods rely on fixed structures which greatly limit the exploitation of the active time slots from other neighbors. In this paper, we investigate the MLAS problem in duty-cycle WSNs without considering structures. We propose the first distributed aggregation algorithm for duty-cycle WSNs, in which the aggregation tree and a conflict-free schedule are generated simultaneously. Compared with the previous centralized and distributed methods, the aggregation latency and the utilization ratio of available time slots are greatly improved. The theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency and communication cost.

Beaconing is a fundamental networking service where each node broadcasts a packet to all its neighbors locally. Unfortunately, the problem Minimum Latency Beaconing Schedule (MLBS) in duty-cycled scenarios is not well studied. Existing works always have rigid assumption that each node is only active once per working cycle. Aiming at making the work more practical and general, MLBS problem in duty-cycled network where each node is allowed to active multiple times in each working cycle (MLBSDCA for short) is investigated in this paper. Firstly, a modified first-fit coloring based algorithm is proposed for MLBSDCA under protocol interference model. After that, a (ρ + 1)2*|W|-approximation algorithm is proposed to further reduce the beaconing latency, where ρ denotes the interference radius, and |W| is the maximum number of active time slots per working cycle. When ρ and |W| is equal to 1, the approximation ratio is only 4, which is better than the one (i.e., 10) in existing works. Furthermore, two approximation algorithms for MLBSDCA under physical interference model are also investigated. The theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms in term of latency.

Multicast is an important way to diffuse data in duty-cycled wireless sensor networks (WSNs), where nodes can receive data only in active state. The communication delay can be extremely large if inappropriate schedules are adopted. Unfortunately, most previous methods do not consider controlling multicast delay energy-efficiently. This paper studies the minimum active time slot augmentation for delay-bounded multicast (MAADM) problem in duty-cycled WSNs. The MAADM problem is proved to be NP-hard even under the node-exclusive interference model. An optimal algorithm is proposed for the MAADM problem when K = 2 and a heuristic latency bounding algorithm is proposed for source-to-all communications, where K denotes the number of the destination nodes. When K > 2, two (K-1)-approximation algorithms are designed for the MAADM problem. In addition, a low computation-complexity distributed algorithm is proposed. To the best of our knowledge, this is the first work that develops a series of efficient centralized and distributed algorithms for the MAADM problem in dutycycled WSNs. The theoretical analysis and experimental results verify that all the proposed algorithms have high performance in terms of delivery delay and energy consumption.