Rejoining fragment images of precious artifacts is a meaningful task because complete artifacts could provide valuable clues for the research of human civilization. However, existing rejoining methods face several challenges including time-consuming manual annotation, insufficient rejoining accuracy, and prohibitive computation cost. For rejoining fragment images of bone sticks (a precious artifact), we propose a lightweight vision graph neural network called RejoinViG to address these challenges. First, our method avoids time-consuming manual annotation of ballast contour data by experts. Specifically, our method directly takes a pair of fragment images as input and then determines whether the image pair is rejoinable. Second, our method improves rejoining accuracy by contour, script, and texture through dynamically constructing local and global graphs. Third, our method improves rejoining accuracy while reducing computation cost by introducing a new attention mechanism named node self-attention. Extensive experiments demonstrate that our method outperforms the state-of-the-art methods significantly. For example, the Top-1 accuracy of our method is 3.9 times that of SFF-Siam. Surprisingly, our method successfully rejoins a pair of previously unknown but rejoinable fragment images of bone sticks in a real-world scenario.

Betweenness centrality is one of the key centrality measures in many applications including community detections in biological networks, vulnerability detections in communication networks, misinformation filtering in social networks, etc. The top-K group betweenness centrality problem is to find a group of K nodes from a network so that the total fraction of shortest paths that pass through the K nodes is maximized. Existing studies proposed randomized sampling algorithms for the problem. We notice that the existing studies ensured that, the maximum deviation of the estimated centrality of every group from its expectation is no greater than a small given threshold for all potential groups with no more than K nodes, thereby generating too many samples, as the number of such groups is prohibitively large. In contrast, in this paper we first devise a novel algorithm that enables to estimate the centrality of a tentative group adaptively, and the algorithm immediately stops once the centrality is large enough; otherwise, the algorithm uses more samples to find a better group. We then theoretically show that, even the proposed algorithm uses much less samples, it still can find a performance-guaranteed group with high probability. Experimental results with real-world networks demonstrate that the number of samples used by the proposed algorithm is up to 36 times smaller than the state-of-the-art, while the centrality of the group found by the algorithm is no more than 4.5% smaller than the latter.

Recently, Wireless Rechargeable Sensor Networks (WRSNs) based platforms have become promising for broad applications. However, if an adversary disrupts the wireless charging process in WRSNs, sensors may die due to lack of timely energy supply, compromising the reliability and availability of systems relying on sensing tasks. In this paper, we develop a zero-cost power jamming attack in WRSNs, termed rEflection-based jaMmIng aTtack (EMIT), which introduces an off-the-shelf and inconspicuous reflector such as a Coca-Cola can that intentionally reflects the wave from the charger to destructively interfere with the charging wave at the target sensor. Our approach lifts the limitations of traditional charging attacks, including high cost, complex implementation and ease of detection. We conduct extensive field experiments to evaluate EMIT attack in different types of WRSNs. The results show that on average, the success rate of EMIT attack is 90% in WRSNs with fixed charging locations, and 75% in WRSNs with dynamic charging locations. Finally, we build a real-world WRSN on university campus to study the effectiveness of EMIT attack in complex scenarios. In total, EMIT attack causes 134 sensor deaths over 66 days.

Digital twin is emerging as a key technology to monitor the status of complex industry systems. Valuable insights, such as running statuses and anomalies, can be analyzed from the collected system status timely. Considering that the data updating from each system component (known as a physical object) to its digital twin is performed continuously, timely and accurate streaming analytics based on machine learning models is a key technology to analyze such data efficiently. In this paper, we focus on enabling low-delay yet highly-accurate streaming analytics for digital twin applications in mobile edge computing (MEC) networks. Specifically, we formulate a fundamental optimization problem of digital twin placements and model selections for streaming analytics, with the aim of minimizing both the analytic loss and the processing delay. To this end, we first consider the problem with a single query, for which, we propose an approximation algorithm with provable approximation ratio for a special case, and then devise an efficient algorithm for the original problem with a single query. We then study the online digital twin placement and model selection problem for streaming analytics with multiple queries under real scenarios, where resource demands of arrival queries and resource availability of MEC network are uncertain. We propose an online learning algorithm with a bounded regret to make admission policies. We finally evaluate the performance of the proposed algorithms by extensive simulations. Results show that the weighted sums of the total processing delay and the cumulative loss in the solution delivered by the proposed algorithms outperform their counterparts by 12.5% with a single query and 13.3% with multiple queries, respectively.

Data stream processing is a functionality of various AI applications to obtain continuous insights from data streams. Serverless edge computing (SEC) is a key solution for implementing data stream processing requests by deploying serverless functions into cloudlets. However, existing data stream processing methods focus more on processing delay, ignoring fault tolerance and complex dependencies among functions, resulting in critical events being missed in the event of any fault and processing inefficiency. Besides, due to the uncertainty of data streams, existing function deployment methods may not be suitable for their newly changed data rates, causing resource waste or shortages. To address these problems, we first propose an optimization framework to enable efficient and fault tolerant function deployment, such that the delay of data stream processing is minimized while meeting its fault tolerant requirements and resource capacity constraints of cloudlets in an SEC network. We then design an online learning algorithm that predicts data rate changes through a multi-timescale machine learning method and proactively adjusts instance locations and numbers to absorb data rate uncertainty. Experimental results in a real test-bed show that our proposed algorithms outperform their counterparts by 13.5% on the average delay and 26.3% on the average fault tolerance.

UAVs (Unmanned Aerial Vehicles) are promising tools for disaster monitoring, by obtaining valuable information of important PoIs (Points of Interest) with onboard cameras. Since people trapped at some PoIs are more likely in danger than people in other PoIs, different PoIs have different monitoring priorities, so that the PoIs with high monitoring priorities should be visited more often than those with low priorities. Unlike existing studies that assumed a UAV is required to fly to the location of a PoI to monitor the PoI, we observe that the a UAV can monitor a PoI as long as it hovers at any location around the PoI (e.g., 200 m away horizontally), thereby reducing the flying time of the UAV. In this paper, we first study a problem of finding a sequence of monitoring tours for an energy-constrained UAV to monitor PoIs in a disaster area for a monitoring period T (e.g., 72 hours) persistently, such that the maximum weighted monitoring interval of PoIs is minimized, where the weight associated with a PoI is its monitoring priority, and the monitoring interval of a PoI is the longest time between its two consecutive visits in period T. We then propose a novel approximation algorithm for the problem. We finally evaluate the algorithm performance based on both a real testbed and the simulation. The experimental results show that the maximum weighted monitoring interval by the proposed algorithm is up to 30% shorter than those by existing algorithms.

Betweenness centrality is one of the key centrality measures in many applications including community detections in biological networks, vulnerability detections in communication networks, misinformation filtering in social networks, etc. The top-$K$group betweenness centrality problem is to find a group of$K$nodes from a network so that the total fraction of shortest paths that pass through the$K$nodes is maximized. Existing studies proposed randomized sampling algorithms for the problem. We notice that the existing studies ensured that, the maximum deviation of the estimated centrality of every group from its expectation is no greater than a small given threshold for all potential groups with no more than$K$nodes, thereby generating too many samples, as the number of such groups is prohibitively large. In contrast, in this paper we first devise a novel algorithm that enables to estimate the centrality of a tentative group adaptively, and the algorithm immediately stops once the centrality is large enough; otherwise, the algorithm uses more samples to find a better group. We then theoretically show that, even the algorithm uses much less samples, it still can find a performance-guaranteed group with a large success probability. Experimental results with real-world networks demonstrate that the number of samples used by the proposed algorithm is from 2 to 18 times smaller than the state-of-the-art, while the centrality of the group found by the algorithm is no more than 4% smaller than the latter.

Differential privacy (DP) is introduced into many fields of AI to preserve privacy. However, introducing DP into AI models is extremely error-prone. To verify whether DP AI models can provide privacy guarantee (quantified by privacy budget) as these models claim, existing methods utilize attack methods to audit whether privacy budget of these models is the same as these models claim. To further improve precision of privacy budget auditing, we propose a brand new way to audit privacy budget, namely directly utilizing the parameters of DP AI models to audit privacy budget. In particular, our method utilizes statistical characteristics variance of the output distribution of DP mechanism to audit privacy budget of DP mechanism. DP AI models are regarded as data samples from output distribution of DP AI model training method and are utilized to approximate the variance of output distribution. The approximated variance is leveraged to estimate the variance of noise distribution of DP mechanism and through the relationship between noise variance and privacy budget, our method calculates the audited privacy budget through estimated noise variance. In addition, to reduce computation overhead, our method constructs parameter selection strategy to identify position whose parameter is suitable for privacy budget auditing. Comprehensive experiments are conducted to verify the effectiveness of our auditing method. Comparison results of five competitive auditing methods demonstrate that our method decreases MAE by 18.29% and decreases MSE by 23.17% on experiment datasets.

Auditing the privacy budget of differential privacy (DP) artificial intelligence (AI) models is necessary to ensure that industrial data are protected at the desired level by DP mechanisms. However, existing auditing methods are not general and precise enough to deal with various kinds of AI models, because the existing auditing methods require customizing audit frameworks and utilize information from model parameters insufficiently. In this article, we propose aprecise andgeneral method toauditthe privacy budget of DPAImodels precisely. Our method associates the parameters of the DP AI model with privacy budget through the Bayesian perspective, achieving tight auditing results with a limited number of DP AI models. Extensive experiments show that our method is more precise and general than existing methods. In particular, the experiments involve ten different datasets, five different models, and three different ways to achieve differential privacy, which indicates the generality of our method. According to empirical experiment results, in 35 out of 36 comparison experiments, our method demonstrates improvements in precision.

With the advance of mobile edge computing (MEC) and the Internet of Things (IoT), digital twin (DT) has become an emerging technology for provisioning IoT services between the real world and the cyber world. In this paper, we consider the state updating of DTs in an MEC network through synchronizing DTs with their physical objects. We make use of an energy-constrained UAV for data collection in a sensor network, as an illustrative example for the DT state updating of each object (sensor), and then use the DT data of objects (sensors) later for fidelity-aware query services. To this end, we first formulate a novel DT state staleness minimization, under a given update budget per update round. We then propose an optimal algorithm for a special case of the problem where the budget per update round is exactly$K$objects synchronizing with their DTs. We then devise an algorithm for the DT state staleness minimization problem by reducing to the award collection maximization problem, assuming that the volume of the update data generated by each object per update round is given. Otherwise, we adopt a deep learning method to predict the volume of the update data. To demonstrate the importance of the DT state staleness in practical applications, we consider fidelity-aware query services in the MEC network, and we develop a cost-effective evaluation plan for each query. We finally evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising.

To guarantee the reliability for WRSNs, placing sufficient static chargers effectively ensures charging coverage for the entire network. However, this approach leads to a considerable number of sensors located within charging overlaps. The destructive wave interference caused by concurrent charging in these overlaps may weaken sensors received power, thereby negatively impacting charging performance. This work addresses a CHArging utIlity maximizatioN (CHAIN) problem, which aims to maximize the overall charging utility while considering wave interference among multiple chargers. Specifically, given a set of stationary sensors, we investigate how to determine optimal positions for a fixed number of chargers. To tackle this problem, we first develop a charging model with wave interference, then propose a two-step charger placement scheme to identify the optimal charger positions. In the first step, we maximize the overall additive power of the waves involved in interference by selecting an appropriate initial position for each charger. Then, in the second step, we maximize the overall charging utility by finding the optimal final position for each charger around its initial position. Finally, to evaluate the performance of our scheme, we conduct extensive simulations and field experiments and the results suggest that CHAIN performs better than the existing algorithms.

Deformable medical image registration plays a significant role in medical image analysis. With the advancement of deep neural networks, learning-based deformable registration methods have made great strides due to their ability to perform fast end-to-end registration and their competitive performance compared to traditional methods. However, these methods primarily improve registration performance by replacing specific layers of the encoder-decoder architecture designed for segmentation tasks with advanced network structures like Transformers, overlooking the crucial difference between these two tasks, which is feature matching. In this paper, we propose a novel correlation-guided registration network (CGNet) specifically designed for deformable medical image registration tasks, which achieves a reasonable and accurate registration through three main components: dual-stream encoder, correlation learning module, and coarse-to-fine decoder. Specifically, the dual-stream encoder is used to independently extract hierarchical features from a moving image and a fixed image. The correlation learning module is used to calculate correlation maps, enabling explicit feature matching between input image pairs. The coarse-to-fine decoder outputs deformation sub-fields for each decoding layer in a coarse-to-fine manner, facilitating accurate estimation of the final deformation field. Extensive experiments on four 3D brain MRI datasets show that the proposed method achieves state-of-the-art performance on three evaluation metrics compared to twelve learning-based registration methods, demonstrating the potential of our model for deformable medical image registration.

Gait recognition is a prominent biometric recognition technique extensively employed in public security. Appearance-based and model-based gait recognition are two categories of methods commonly used. Specifically, appearance-based methods, which use silhouettes to represent body information, typically outperform model-based methods that rely on skeleton data, making them more popular. Recently, the shift from single-frame templates to multiframe silhouettes has advanced appearance-based gait recognition with better spatiotemporal representation. However, there is a notable lack of comprehensive studies that deepen the understanding of multiframe appearance-based gait recognition methods. This article reviews various methods to trace the evolution of gait recognition. Furthermore, we unify various performant models in one framework, study the overlooked effects on data arrangement, and explore the scaling ability of existing methods. Besides the advancement in gait recognition, we also summarize the current challenges and future prospects to foster future research.

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K, the problem is to find a subset S with K nodes from a graph G, so that a given submodular function$f(S)$on S is maximized and the induced subgraph$G[S]$by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel$\frac {1-1/e}{2h+2}$-approximation algorithm for the problem, improving the best approximation ratio$\frac {1-1/e}{2h+3}$for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter that depends on the problem and its typical value is 2. In addition, when$h=2$, the algorithm approximation ratio is at least$\frac {1-1/e}{5}$and may be as large as 1 in some special cases when$K\le 23$, and is no less than$\frac {1-1/e}{6}$when$K\ge 24$, compared with the current best approximation ratio$\frac {1-1/e}{7}\left ({{=\frac {1-1/e}{2h+3}}}\right)$for the problem. Finally, experimental results in the application of deploying a UAV network demonstrate that, the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and the throughput of the deployed UAV network by the proposed algorithm is up to 9.7% larger than those by the algorithms. Furthermore, the empirical approximation ratio of the proposed algorithm is between 0.7 and 0.99, which is close to the theoretical maximum value one.

The Digital Twin (DT) technique enables seamless integrations between the physical and virtual worlds. By continuously synchronizing DTs with their physical counterparts, DTs can provide accurate reflections of physical objects and facilitate high-fidelity inference services based on service models. Orthogonal to the DT technology, Mobile Edge Computing (MEC) has been envisioning as a promising paradigm for providing intelligent services to users while meeting stringent delay and accuracy requirements. In this paper, we investigate fidelity-aware inference services in a DT-assisted MEC network where there are multiple source DTs providing new updated training data to service models often. We jointly schedule mobile devices to upload their update data to their DTs, and choose service models for retraining using their updated source DT data over a given time horizon. We further assume that the previous version of each service model can still serve its users during its retraining period, while a retrained service model can provide high-fidelity services to its users. To this end, we first formulate two novel optimization problems: the model instance placement problem that assigns model instances to cloudlets in an MEC network so that the total placement cost of all service models is minimized, and the cumulative utility maximization problem to maximize the cumulative fidelity of all service models over a given time horizon, by jointly scheduling mobile devices to upload their update data to their DTs and service models to be trained using their updated source DT data at each time slot. We then formulate an integer linear programming (ILP) solution for the model instance placement problem when the problem size is small; otherwise we develop an approximate solution to the problem, at the expense of moderate resource violations. We also devise an efficient online algorithm for the cumulative utility maximization problem. We finally evaluate the performance of the proposed algorithms via simulations, and the simulation results demonstrate that the proposed algorithms are promising.

Given an untrimmed video and a sentence query, video moment retrieval using language (VMR) aims to locate a target query-relevant moment. Since the untrimmed video is overlong, almost all existing VMR methods first sparsely down-sample each untrimmed video into multiple fixed-length video clips and then conduct multi-modal interactions with the query feature and expensive clip features for reasoning, which is infeasible for long real-world videos that span hours. Since the video is downsampled into fixed-length clips, some query-related frames may be filtered out, which will blur the specific boundary of the target moment, take the adjacent irrelevant frames as new boundaries, easily leading to cross-modal misalignment and introducing both boundary-bias and reasoning-bias. To this end, in this paper, we propose an efficient approach, SpotVMR, to trim the query-relevant clip. Besides, our proposed SpotVMR can serve as plug-and-play module, which achieves efficiency for state-of-the-art VMR methods while maintaining good retrieval performance. Especially, we first design a novel clip search model that learns to identify promising video regions to search conditioned on the language query. Then, we introduce a set of low-cost semantic indexing features to capture the context of objects and interactions that suggest where to search the query-relevant moment. Also, the distillation loss is utilized to address the optimization issues arising from end-to-end joint training of the clip selector and VMR model. Extensive experiments on three challenging datasets demonstrate its effectiveness.

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget$K$, the problem is to find a subset$S$with$K$nodes from a graph$G$so that a given submodular function$f (S)$on$S$is maximized while the induced subgraph$G[S]$by the nodes in$S$is connected, where the submodular function$f$can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in$S$, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel$\frac{1-1/e}{2h+2}$-approximation algorithm for the problem, improving the best approximation ratio$\frac{1-1/e}{2h+3}$for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where$e$is the base of the natural logarithm,$h$is a parameter depends on the problem and its typical value is 2. In addition. when$h= 2$, the algorithm approximation ratio is at least$\frac{1-1/e}{5}$and may be as large as 1 in some special cases when$K$≤21, and is no less than$\frac{1-1/e}{6}$when$K$≥ 22, compared with the current best approximation ratio$\frac{1-1/e}{7}(= \frac{1-1/e}{2h+3})$for the problem. We finally evaluate the algorithm performance in the application of deploying a UAV network. Experimental results demonstrate the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and its empirical approximation ratio is between 0.7 and 0.99, which is close to the theoretical maximum value one.

UAVs (Unmanned Aerial Vehicles) are promising tools for efficient data collections of sensors in IoT networks. Existing studies exploited both spatial and temporal data correlations to reduce the amount of collected redundant data, in which sensors are first partitioned into different clusters, a master sensor in each cluster then collects raw data from other sensors and compresses the received data. An energy-constrained UAV finally collects the maximum amount of compressed data from different master sensors. We however notice that the compressed data from only a portion of clusters are collected by the UAV in the existing studies, while the data from other clusters are not collected at all. In this paper, we study a problem of finding a data collection trajectory for an energy-constrained UAV, so that the accumulative utility of collected data is maximized, where the accumulative utility measures the quality of spatiotemporally correlated data collected from different clusters. We propose a novel 16+-approximation algorithm for the problem, where is a given constant with >0. Experimental results with real datasets show that the accumulative utility by the proposed algorithm is at least 23% larger than those by the existing studies, and the number of clusters collected by the proposed algorithm is from 45% to 105% larger than those by the existing studies.

Federated continual learning (FCL) is emerging as a key technology for time-sensitive applications in highly adaptive environments including autonomous driving and industrial digital twin. Each FCL trains machine learning models using newly-generated datasets as soon as possible, to obtain a highly accurate machine learning model for new event predictions. Theage of data, defined as the time difference between the generation time of a dataset and the current time, is widely adopted as a key criterion to evaluate both timeline and quality of training. In this paper, we study the problem of age-aware FCL in a mobile edge computing (MEC) network. We not only investigate optimization techniques that optimize the data selection and aggregator placement for FCL but also implement a real system as a prototype for age-aware FCL. Specifically, we first propose an approximation algorithm with a provable approximation ratio for the age-aware data selection and aggregator placement problem for FCL with a single request. In real application scenarios, there are usually multiple FCL requests that require to train models, and delays in the MEC network are usually uncertain. We then study the problem of age-aware data selection and aggregator placement problem for FCL with uncertain delays and multiple requests, by devising an online learning algorithm with a bounded regret based on contextual bandits. We finally implement a prototype for FCL in an MEC network, with various heterogeneous user equipments (UEs) and cloudlets with different computing capabilities in the network. Experiment results show that the performance of the proposed algorithms outperform existing studies, by achieving 47% lower age of data and 12% higher model accuracy.

View change causes significant differences in the gait appearance. Consequently, recognizing gait in cross-view scenarios is highly challenging. Most recent approaches either convert the gait from the original view to the target view before recognition is carried out or extract the gait feature irrelevant to the camera view through either brute force learning or decouple learning. However, these approaches have many constraints, such as the difficulty of handling unknown camera views. This work treats the view-change issue as a domain-change issue and proposes to tackle this problem through adversarial domain adaptation. This way, gait information from different views is regarded as the data from different sub-domains. The proposed approach focuses on adapting the gait feature differences caused by such sub-domain change and, at the same time, maintaining sufficient discriminability across the different people. For this purpose, a Hierarchical Feature Aggregation (HFA) strategy is proposed for discriminative feature extraction. By incorporating HFA, the feature extractor can well aggregate the spatial-temporal feature across the various stages of the network and thereby comprehensive gait features can be obtained. Then, an Adversarial View-change Elimination (AVE) module equipped with a set of explicit models for recognizing the different gait viewpoints is proposed. Through the adversarial learning process, AVE would not be able to identify the gait viewpoint in the end, given the gait features generated by the feature extractor. That is, the adversarial domain adaptation mitigates the view change factor, and discriminative gait features that are compatible with all sub-domains are effectively extracted. Extensive experiments on three of the most popular public datasets, CASIA-B, OULP, and OUMVLP richly demonstrate the effectiveness of our approach.

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%.

Benefitting from the breakthrough of wireless power transfer technology, the lifetime of Wireless Sensor Networks (WSNs) can be significantly prolonged by scheduling a mobile charger (MC) to charge sensors. Compared with omnidirectional charging, the MC equipped with directional antenna can concentrate energy in the intended direction, making charging more efficient. However, all prior arts ignore the considerable energy leakage behind the directional antenna (i.e.,back lobe), resulting in energy wasted in vain. To address this issue, we study a fundamental problem of how to utilize the neglected back lobe and schedule the directional MC efficiently. Towards this end, we first build and verify a directional charging model considering both main and back lobes. Then, we focus on jointly optimizing the number of dead sensors and energy usage effectiveness. We achieve these by introducing a scheduling scheme that utilizes both main and back lobes to charge multiple sensors simultaneously. Finally, extensive simulations and field experiments demonstrate that our scheme reduces the number of dead sensors by$49.5\%$and increases the energy usage effectiveness by$10.2\%$on average as compared with existing algorithms.

To unveil the hidden value in the datasets of user equipments (UEs) while preserving user privacy, federated learning (FL) is emerging as a promising technique to train a machine learning model using the datasets of UEs locally without uploading the datasets to a central location. Customers require to train machine learning models based on different datasets of UEs, through issuing FL requests that are implemented by FL services in a mobile edge computing (MEC) network. A key challenge of enabling FL in MEC networks is how to minimize the energy consumption of implementing FL requests while guaranteeing the accuracy of machine learning models, given that the availabilities of UEs usually are uncertain. In this paper, we investigate the problem of energy minimization for FL in an MEC network with uncertain availabilities of UEs. We first consider the energy minimization problem for a single FL request in an MEC network. We then propose a novel optimization framework for the problem with a single FL request, which consists of (1) an online learning algorithm with a bounded regret for the UE selection, by considering various contexts (side information) that influence energy consumption; and (2) an approximation algorithm with an approximation ratio for the aggregator placement for a single FL request. We third deal with the problem with multiple FL requests, for which we devise an online learning algorithm with a bounded regret. We finally evaluate the performance of the proposed algorithms by extensive experiments. Experimental results show that the proposed algorithms outperform their counterparts by reducing at least 13% of the total energy consumption while achieving the same accuracy.

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.

In this paper we study the deployment of an Unmanned Aerial Vehicle (UAV) network that consists of multiple UAVs to provide emergent communication service for people who are trapped in a disaster area, where each UAV is equipped with a base station that has limited computing capacity and power supply, and thus can only serve a limited number of people. Unlike most existing studies that focused on homogeneous UAVs, we consider the deployment of heterogeneous UAVs where different UAVs have different computing capacities. We study a problem of deploying$K$heterogeneous UAVs in the air to form a temporarily connected UAV network such that the network throughput – the number of users served by the UAVs, is maximized, subject to the constraint that the number of people served by each UAV is no greater than its service capacity. We then propose a novel$O(\sqrt{\frac{s}{K}})$-approximation algorithm for the problem, where$s$is a given positive integer with$1 \le s\le K$, e.g.,$s=3$. We also devise an improved heuristic, based on the approximation algorithm. We finally evaluate the performance of the proposed algorithms. Experimental results show that the numbers of users served by UAVs in the solutions delivered by the proposed algorithms are increased by 25% than state-of-the-arts.

In this paper, we study the deployment of$K$heterogeneous UAVs to monitor Points of Interest (PoIs) in a disaster zone, where a PoI may represent a school building or an office building, in which people are trapped. A UAV can take images/videos of PoIs and send its collected information back to a nearby rescue station for decision-making. Unlike most existing studies that focused on only homogeneous UAVs, we here study the scheduling of$K$heterogeneous UAVs, where different UAVs have different energy capacities and functionalities that lead to different monitoring qualities (monitoring rewards) of each PoI. For example, one type of UAVs can take only visual images while the other type of UAVs can take both visual and thermal infrared images. In this paper, we investigate a problem of scheduling$K$heterogeneous UAVs to monitor PoIs so that the sum of monitoring rewards received by all UAVs is maximized, subject to energy capacity on each UAV. We propose the very first$\frac {1}{3}$-approximation algorithm for this scheduling problem. We also evaluate the performance of the proposed algorithm, using real parameters of commercial UAVs. Experimental results show that the performance of the proposed algorithm is promising, which is improved by 25%, compared with existing algorithms.

In the coming era of Metaverse, Augmented Reality (AR) has become a key enabler of diverse applications including healthcare, education, smart cities, and entertainments. To provide users with interactive and immersive experience, most AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has demonstrated great potentials in meeting such stringent latency requirements and resource demands of AR applications, by implementing AR requests in edge servers within the proximity of users. In this paper, we investigate the reward maximization problem for AR applications with uncertain resource demands in an MEC network, such that the accumulative reward of services provided for AR applications is maximized, while ensuring that the responsiveness of AR applications is enhanced, subject to network resource capacity. To this end, we formulate an exact solution when the problem size is small, otherwise we devise an efficient approximation algorithm with a provable approximation ratio for the problem. We also develop an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of future arrivals of AR requests, by adopting the Multi-Armed Bandits (MAB) technique. Considering maximizing the reward may defer the implementations of some urgent yet low-award requests, we propose a fairness-aware online learning algorithm for the dynamic reward maximization problem, through a data rate prediction mechanism that adopts a multi-task and multi-timescale Long Short-Term Memory (MT2-LSTM) method. Finally, we evaluate the performance of the proposed algorithms for AR applications by building a real test bed. Experimental results show that the proposed algorithms outperform existing studies by improving the award by 13%.

Unmanned Aerial Vehicles (UAVs) have gained increasing attention by both academic and industrial communities, due to their flexible deployment and efficient line-of-sight communication. Recently, UAVs equipped with base stations have been envisioned as a key technology to provide 5G network services for mobile users. In this article, we provide timely services on the data streams of mobile users in a UAV-aided Mobile Edge Computing (MEC) network, in which each UAV is equipped with a 5G small-cell base station for communication and data processing. Specifically, we first formulate a flow-time minimization problem by jointly caching services and offloading tasks of mobile users to the UAV-aided MEC with the aim to minimize the flow time, where the flow time of a user request is referred to the time duration from the request issuing time point to its completion point, subject to resource and energy capacity on each UAV. We then propose a spatial-temporal learning optimization framework. We also devise an online algorithm with a competitive ratio for the problem based upon the framework, by leveraging the round-robin scheduling and dual fitting techniques. Finally, we evaluate the performance of the proposed algorithms through experimental simulation. The simulation results demonstrate that the proposed algorithms outperform their comparison counterparts, by reducing the flow time no less than 19% on average.

In the past decades, explosive numbers of Internet of Things (IoT) devices (objects) have been connected to the Internet, which enable users to access, control, and monitor their surrounding phenomenons at anytime and anywhere. To provide seamless interactions between the cyber world and the real world, Digital twins (DTs) of objects (IoT devices) are key enablers for real time monitoring, behaviour simulations, and predictive decisions on objects. Compared to centralized cloud computing, mobile edge computing (MEC) has been envisioning as a promising paradigm for low latency IoT applications. Accelerating the usage of DTs in MEC networks will bring unprecedented benefits to diverse services, through the co-evolution between physical objects and their virtual DTs, and DT-assisted service provisioning has attracted increasing attention recently. In this article, we consider novel DT placement and migration problems in an MEC network with the mobility assumption of objects and users, by jointly considering the freshness of DT data and the service cost of users requesting for DT data. To this end, we first propose an algorithm for the DT placement problem with the aim to minimize the sum of the DT update cost of objects and the total service cost of users requesting for DT data, through efficient DT placements and resource allocation to process user requests. We then devise an approximation algorithm with a provable approximation ratio for a special case of the DT placement problem when each user requests the DT data of only one object. Meanwhile, considering the mobility of users and objects, we devise an online, two-layer scheduling algorithm for DT migrations to further reduce the total service cost of users within a given finite time horizon. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results show that the proposed algorithms are promising.

The advance of Digital Twin (DT) technology sheds light on seamless cyber-physical integration with the Industry 4.0 initiative. Through continuous synchronization with their physical objects, DTs can power inference service models for analysis, emulation, optimization, and prediction on physical objects. With the proliferation of DTs, Digital Twin Network (DTN) slicing is emerging as a new paradigm of service providers for differential quality of service provisioning, where each DTN is a virtual network that consists of a set of inference service models with source data from a group of DTs, and the inference service models provide users with differential quality of services. Mobile Edge Computing (MEC) as a new computing paradigm shifts the computing power towards the edge of core networks, which is appropriate for delay-sensitive inference services. In this paper we consider Age of Information (AoI)-aware inference service provisioning in an MEC network through DTN slicing requests, where the accuracy of inference services provided by each DTN slice is determined by the Expected Age of Information (EAoI) of its inference model. Specifically, we first introduce a novel AoI-aware inference service framework of DTN slicing requests. We then formulate the expected cost minimization problem by jointly placing DT and inference service model instances, and develop efficient algorithms for the problem, based on the proposed framework. We also consider dynamic DTN slicing request admissions where requests arrive one by one without the knowledge of future arrivals, for which we devise an online algorithm with a provable competitive ratio for dynamic request admissions, assuming that DTs of all objects have been placed already. Finally, we evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising, and the proposed online algorithm improves the number of admitted requests by more than 6% than its counterpart.

In this paper we study the deployment of a UAV (unmanned aerial vehicle) network that consists of multiple UAVs to provide emergent communication services to people trapped in a disaster area, where each UAV is equipped with a base station that has limited computing capacity and power supply, and thus can only serve a limited number of users. Unlike most existing studies focusing on homogenous UAVs, we consider the deployment of heterogeneous UAVs, where different UAVs have different computing capacities. We study a problem of deploying$K$heterogeneous UAVs in the air to form a connected UAV network such that the number of users served by the UAVs is maximized, subject to the constraint that the number of users served by each UAV is no greater than its service capacity, assuming that the maximum number of users can be served by a UAV is given. We then propose a novel$O(\sqrt{\frac{s}{K}})$-approximation algorithm for the problem, where$s$is a given positive integer, e.g.,$s=3$. We finally evaluate the performance of the approximation algorithm. Experimental results show that the number of users served by all UAVs in the approximate solution is improved by 22% compared with the solutions delivered by state-of-the-arts.

Benefitting from the breakthrough of wireless power transfer technology, the lifetime of Wireless Sensor Networks (WSNs) can be significantly prolonged by scheduling a mobile charger (MC) to charge sensors. Compared with omnidirectional charging, the MC equipped with directional antenna can concentrate energy in the intended direction, making charging more efficient. However, all prior arts ignore the considerable energy leakage behind the directional antenna (i.e., back lobe), resulting in energy wasted in vain. To address this issue, we study a fundamental problem of how to utilize the neglected back lobe and schedule the directional MC efficiently. Towards this end, we first build and verify a directional charging model considering both main and back lobes. Then, we focus on jointly optimizing the number of dead sensors and energy usage effectiveness. We achieve these by introducing a scheduling scheme that utilizes both main and back lobes to charge multiple sensors simultaneously. Finally, extensive simulations and field experiments demonstrate that our scheme reduces the number of dead sensors by 49.5% and increases the energy usage effectiveness by 10.2% on average as compared with existing algorithms.

We study the deployment of an unmanned aerial vehicle (UAV) network to provide urgent communications to people trapped in a disaster zone, where each UAV is an aerial base station in the air. Unlike most existing studies that assumed that each user communicates with a UAV directly, we introduce Device-to-Device (D2D) communications, in which a user within the communication range of a UAV can serve as a hotspot (e.g., WiFi hotspot), and provide communication services to his nearby users who are out of the communication range of any UAV. More users thus can have the communication service provided by the UAV network. To ensure that the users within and out of the communication ranges of deployed UAVs havefaircommunication quality, we study a novel UAV deployment and resource allocation problem under the D2D communication model, which is to deploy$K$given UAVs in the top of a disaster zone, allocate the bandwidth of each UAV to its served users, allocate the bandwidth of each hotspot to his served users, determine the data rate of each user, and find the routing paths for data transmissions, such that the accumulative utility of all users is maximized. We also propose a novel$(1-1/e-\epsilon)$-approximation algorithmalgMaxUtilityfor the problem, where$e$is the base of the natural logarithm, and$\epsilon $is a given constant with$0 < \epsilon < 1-1/e$. We finally evaluate the performance of the algorithm. Experimental results show that accumulative utility by the algorithm is up to 18% larger than those by existing algorithms. In addition, more than 16% users are served in the deployed UAV network by the proposed algorithm.

Serverless computing is emerging as an enabling technology for elastic and low-cost AI applications in the edge of core networks. It allows AI developers to decompose a complex training and time-sensitive inference task into multiple functions with dependency, and upload the task to a Multi-access Edge Computing platform (MEC) for execution. Serverless computing adopts a popular design principle: the disaggregation of storage and computation, making the functions ‘stateless’. However, most AI applications are ‘stateful’ and rely on an external storage service to manage their states (ephemeral data). This will incur a prohibitively long delay for delay-sensitive AI applications if external services storing the states are far from the serverless functions. Motivated by this critical issue, in this paper we investigate a fundamental problem in serverless computing – the stateful serverless application placement problem, for which, we first propose an efficient heuristic algorithm, and then devise an approximation algorithm with a provable approximation ratio for one of its special cases. We also consider the online version of the problem, and develop an online learning-driven algorithm with a bounded regret. The crux of the online algorithm is the adoption of the multi-armed bandits technique for dynamic admissions of inference requests, under the uncertainty of both data volumes of requests and network delays. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results show that the proposed algorithms outperform their counterparts, reducing at least 32% in the total cost and 27% of the average delay.

In this paper, we study sensing data collection of IoT devices in a sparse IoT-sensor network, using an energy-constrained Unmanned Aerial Vehicle (UAV), where the sensory data is stored in IoT devices while the IoT devices may or may not be within the transmission range of each other. We formulate two novel data collection problems to fully or partially collect data stored from IoT devices using the UAV, by finding a closed tour for the UAV that consists of hovering locations and the sojourn duration at each of the hovering locations such that the accumulative volume of data collected within the tour is maximized, subject to the energy capacity on the UAV, where the UAV consumes energy on both hovering for data collection and flying from one hovering location to another hovering location. To this end, we first propose a novel data collection framework that enables the UAV to collect sensory data from multiple IoT devices simultaneously if these IoT devices are within the coverage range of the UAV, through adopting the orthogonal frequency division multiple access (OFDMA) technique. We then formulate two data collection maximization problems to deal with full or partial data collection from IoT devices at each hovering location, and show that both defined problems are NP-hard. We instead devise approximation and heuristic algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrated that the proposed algorithms are promising.

Mobile Edge Computing (MEC) promises to provide mobile users with delay-sensitive services at the edge of network, and each user service request usually is associated with a Service Function Chain (SFC) requirement that consists of Virtualized Network Functions (VNFs) in order. The satisfaction of a user on his requested service is heavily impacted by the service reliability. In this paper, we study user satisfaction on services provided by an MEC network through introducing a submodular function based metric to measure user satisfaction. We first formulate a novel user satisfaction problem with the aim to maximize the accumulative user satisfaction, assuming that all available computing resource in the MEC network can be used for service reliability enhancement. We show that the problem is NP-hard, and devise an approximation algorithm with a provable approximation ratio for it. We then consider the problem under a given computing resource budget constraint, for which we devise an approximation algorithm with a provable approximation ratio, at the expense of moderate budget violations. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms outperform the comparison baseline algorithms, improving the performance by more$16.1\%$in comparison with the baseline algorithms.

In this paper, we study the employment of a mobile charger to charge lifetime-critical sensors under the multi-node partial-charging model, in which the charger can simultaneously charge the sensors within its charging range and each sensor may be partially charged each time. We notice that existing studies only scheduled the charger to minimize the number of dead sensors, but did not consider the charging scheduling for the sensors that have already run out of their energy, and the dead sensors will be last charged by the mobile charger. Then, their dead durations may be very long. In this paper, we consider not only how to minimize the number of dead sensors but also reduce the dead durations of sensors. To this end, we first formulate a sensor lifetime maximization problem, which is to find a charging tour for a mobile charger to charge sensors, such that the sum of sensor lifetimes is maximized. We then propose a novel$\frac{1}{3}$-approximation algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experiments. Experimental results show that both the average and maximum sensor dead durations by the proposed algorithm are up to 70% shorter than those by existing algorithms.

Multi-access edge computing (MEC) enables extreme low-latency AI services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. Meanwhile, a 5G hierarchical service market is emerging with both large-scale and small-scale network service providers competing for both computing and network bandwidth resources of an infrastructure provider. In this paper, we investigate the problem of caching services originally deployed in remote clouds to cloudlets in an MEC network in a hierarchical service market. For the service caching problem, we first propose a novel approximation-restricted framework that guarantees the stability of the 5G service market. Under the proposed framework, we first propose an approximation algorithm with a provable approximation ratio for the problem with non-selfish network service providers. We then design an efficient Stackelberg congestion game with selfish network service providers, and analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency loss of the game due to selfishness of network service providers. Considering that the request rate of each service may not be given in advance, we study the service caching problem with the uncertainlity of request rates, and propose an approximation algorithm and a Stackelberg game via leveraging the randomized rounding technique. We finally evaluate the performance of the proposed algorithms and mechanisms by both simulations and implementations in a real test-bed. Results show that the performance of our proposed mechanisms achieve around 9.2% less cost than those of existing approaches.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to reduce the response latency of network services by deploying cloudlets at 5G base stations to form mobile edge cloud (MEC) networks. Network service providers now shift their services from remote clouds to cloudlets of MEC networks in the proximity of users. However, the permanent placement of network services into an MEC network is not economic due to limited computing and bandwidth resources imposed on its cloudlets. A smart way is to cache frequently demanded services from remote clouds to cloudlets of the MEC network. In this paper, we study the problem of service caching in an MEC network under a service market with multiple network service providers competing for both computation and bandwidth resources in terms of Virtual Machines (VMs) in the MEC network. We first propose an Integer Linear Program (ILP) solution and a randomized rounding algorithm, for the problem without VM sharing among different network service providers. We then devise a distributed and stable game-theoretical mechanism for the problem with VM sharing among network service providers, with the aim to minimize the social cost of all network service providers, through introducing a novel cost sharing model and a coalition formation game. We also analyze the performance guarantee of the proposed mechanism, Strong Price of Anarchy (SPoA). We third consider the cost- and delay-sensitive service caching problem with temporal VM sharing, and propose a mechanism with provable SPoA. We finally evaluate the performance through extensive simulations and a real world test-bed implementation. Experimental results demonstrate that the proposed algorithms outperform existing approaches by achieving at least$40\%$lower social cost via service caching and resource sharing among different network service providers.

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given$K$UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the$h$-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with$h=4$. We propose a$\frac {1-1/e}{2h+3}$-approximation algorithm for the$h$-hop independently submodular maximization problem, where$e$is the base of the natural logarithm. Then, one direct result is a$\frac {1-1/e}{11}$-approximate solution to the MCCP problem with$h=4$, which significantly improves its currently best$\frac {1-1/e}{32}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

Federated learning (FL) is a distributed machine learning technique that enables model development on user equipments (UEs) locally, without violating their data privacy requirements. Conventional FL adopts a single parameter server to aggregate local models from UEs, and can suffer from efficiency and reliability issues – especially when multiple users issue concurrentFL requests. Hierarchical FL consisting of a master aggregator and multiple worker aggregators to collectively combine trained local models from UEs is emerging as a solution to efficient and reliable FL. The placement of worker aggregators and assignment of UEs to worker aggregators plays a vital role in minimizing the cost of implementing FL requests in a Mobile Edge Computing (MEC) network. Cost minimization associated with joint worker aggregator placement and UE assignment problem in an MEC network is investigated in this work. An optimization framework for FL and an approximation algorithm with an approximation ratio for a single FL request is proposed. Online worker aggregator placements and UE assignments for dynamic FL request admissions with uncertain neural network models, where FL requests arrive one by one without the knowledge of future arrivals, is also investigated by proposing an online learning algorithm with a bounded regret. The performance of the proposed algorithms is evaluated using both simulations and experiments in a real testbed with its hardware consisting of server edge servers and devices and software built upon an open source hierarchical FedML (HierFedML) environment. Simulation results show that the performance of the proposed algorithms outperform their benchmark counterparts, by reducing the implementation cost by at least 15% per FL request. Experimental results in the testbed demonstrate the performance gain using the proposed algorithms using real datasets for image identification and text recognition applications.

The real-time communication requirement of the Internet of Things (IoT) applications promotes the convergence of IoT and Mobile Edge Computing (MEC). The MEC paradigm greatly shortens the IoT service delay by leveraging cloudlets (edge servers) of MEC in the proximity of IoT devices. Considering limited computing and storage resources in an MEC network, it is challenging to provide efficient IoT-enabled service provisioning in such a network. In this article, we study the service home identification problem of service provisioning for multi-source IoT applications in an MEC network, by identifying a service home (cloudlet) of each multi-source IoT application for its data processing, querying and storage. Each multi-source IoT application consists of multiple sources located at different geographical locations and each source uploads its data stream via a gateway (its nearby access point) to the MEC network and the uploaded data then is aggregated with the stream data of the other sources of the IoT application at the service home. We here focus on two novel service home identification problems: the service operational cost minimization problem with the aim to minimize the total service operational cost by admitting as many multi-source IoT applications as possible, and the online throughput maximization problem with the aim to maximize the number of multi-source IoT application requests admitted. We first show that both the problems are NP-hard. We then formulate an Integer Linear Programming (ILP) solution to the service operational cost minimization problem, and propose a randomized algorithm with high probability and a deterministic approximation algorithm respectively, at moderate resource capacity violations. We third develop an efficient heuristic algorithm for the problem without any resource violation. Furthermore, we deal with the online throughput maximization problem under an assumption that multi-source IoT application requests arrive one by one without the knowledge of future arrivals, for which we formulate an Integer Linear Programming (ILP) solution to its offline version, followed by devising an online algorithm with competitive ratio. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising, and outperform their comparison counterparts.

In this paper, we study the deployment of multiple Unmanned Aerial Vehicles (UAVs) to continuously monitor Points of Interests (PoIs) during an extended period, where there are multiple monitoring rounds during the period. Unlike most existing studies simply dispatched UAVs to visit all PoIs in each monitoring round such to minimize the monitoring latencies of PoIs, we observe that different PoIs own different monitoring priorities which should be taken into account while minimizing the monitoring latencies of PoIs. By existing algorithms, it is possible that each PoI is visited the same number of times during the given period and the monitoring latency of a high-priority PoI is the same as that of a lowpriority PoI. In this paper, we formulate a novel weighted monitoring latency minimization problem to repeatedly collect the data of PoIs using the UAVs, by finding a series of schedulings for UAVs during the given period, such that the maximum weighted monitoring latency of PoIs is minimized, where the monitoring latency of a PoI is equal to the time between two consecutive data receptions from the PoI. As the weighted monitoring latency minimization problem is NP-hard, we propose a heuristic algorithm to deal with the problem and construct a series of schedulings for UAVs. Finally, we evaluate the performance of the proposed algorithm through experimental simulations. Experimental results show that the proposed algorithm is very promising.

With anonymous sessions, session-based recommendation aims to forecast user's next action. It has been a difficult endeavor due to the limited information and lack of user profiles. Recent advances have demonstrated that graph structure is more suited to model complex item transitions than chronological order alone. Most existing GNN-based models mainly concentrate on the current session, mining more intra-session sequential pattern data. Other models that leverage neighbor session information or item co-occurrence to obtain global collaborative signals are too sensitive to noise and are insufficient to infer user preference. In this paper, we propose a novel Intent-Aware Graph Neural Networks (IA-GNN) for session-based recommendation. In IA-GNN, we leverage two encoders to learn item embeddings:(1) Local Transition Encoder (LTE) based on session graph to learn complicated sequence dependencies, and (2) Intent Match Encoder (IME) with the help of intent-aware graph to obtain collaborative signals from the perspective of user intent. Furthermore, a tailored position enhanced soft attention mechanism joins the two levels of item representations to generate user preference. Extensive experiments on three real-world benchmark datasets demonstrate that our model is superior to the state-of-the-art models.

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given K UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a $\frac{{1 - 1/e}}{{2h + 3}}$-approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a $\frac{{1 - 1/e}}{{11}}$-approximate solution to the MCCP problem with h = 4, which significantly improves its currently best $\frac{{1 - 1/e}}{{32}}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

The age of data (AoD) is identified as one of the most novel and important metrics to measure the quality of big data analytics for Internet-of-Things (IoT) applications. Meanwhile, mobile edge computing (MEC) is envisioned as an enabling technology to minimize the AoD of IoT applications by processing the data in edge servers close to IoT devices. In this paper, we study the AoD minimization problem for IoT big data processing in MEC networks. We first propose an exact solution for the problem by formulating it as an Integer Linear Program (ILP). We then propose an efficient heuristic for the offline AoD minimization problem. We also devise an approximation algorithm with a provable approximation ratio for a special case of the problem, by leveraging the parametric rounding technique. We thirdly develop an online learning algorithm with a bounded regret for the online AoD minimization problem under dynamic arrivals of IoT requests and uncertain network delay assumptions, by adopting the Multi-Armed Bandit (MAB) technique. We finally evaluate the performance of the proposed algorithms by extensive simulations and implementations in a real test-bed. Results show that the proposed algorithms outperform existing approaches by reducing the AoD around 10%.

Nowadays, sensor-cloud systems have received wide attention from both academia and industry. Sensor-cloud system not only improves performances of wireless sensor networks (WSNs), but also combines different functional WSNs together to provide comprehensive services. However, a variety of malicious attacks threaten the sensor-cloud security, such as integrity, authenticity, availability and so on. Traditional available security mechanisms (e.g., cryptography and authentication) are still vulnerable. Although there are schemes to provide security by trust evaluation, the evaluation considers whether or not a sensor is credible only by checking the communication behaviors. Furthermore, when mobile sensor sinks are employed to collect sensing data, there appears a type of attacks called replicated sink attacks that are often ignored in the previous work. These attacks may bring serious vulnerability to trustworthy data collection in sensor-cloud systems. In this paper, we propose a comprehensive trustworthy data collection (CTDC) approach for sensor-cloud systems. Three kinds of trust, i.e., direct trust, indirect trust, and functional trust are defined to evaluate the trustworthiness of both sensors and mobile sinks. Except for resisting malicious attacks, the performances of sensor-cloud, such as energy, transmission distance and network throughput are also considered. We also conduct extensive simulations to evaluate the efficiency of CTDC. The simulation results show that CTDC correctly identifies malicious nodes and offers an improved performance in the data collection.

Mobile edge computing (MEC) has emerged as a promising technology that offers resource-intensive yet delay-sensitive applications from the edge of mobile networks. With the emergence of complicated and resource-hungry mobile applications, offloading user tasks to cloudlets of nearby mobile edge-cloud networks is becoming an important approach to leverage the processing capability of mobile devices, reduce mobile device energy consumptions, and improve experiences of mobile users. In this article we first study the provisioning of virtualized network function (VNF) services for user requests in an MEC network, where each user request has a demanded data packet rate with a specified network function service requirement, and different user requests need different services that are represented by virtualized network functions instantiated in cloudlets. We aim to maximize the number of user request admissions while minimizing their admission cost, where the request admission cost consists of the computing cost on instantiations of requested VNF instances and the data packet traffic processing of requests in their VNF instances, and the communication cost of routing data packet traffic of requests between users and the cloudlets hosting their requested VNF instances. We study the joint VNF instance deployment and user requests assignment in MEC, by explicitly exploring a non-trivial usage tradeoff between different types of resources. To this end, we first formulate the cost minimization problem that admits all requests by assuming that there is sufficient computing resource in MEC to accommodate the requested VNF instances of all requests, for which we formulate an Integer Linear Programming solution and two efficient heuristic algorithms. We then deal with the problem under the computing resource constraint. We term this problem as the throughput maximization problem by admitting as many as requests, subject to computing resource capacity on each cloudlet, for which we formulate an ILP solution when the problem size is small; otherwise, we devise efficient algorithms for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising. To the best of our knowledge, we are the first to explicitly explore the usage tradeoff between computing and communication resources in the admissions of user requests in MEC through introducing a novel load factor concept to minimize the request admission cost and maximize the network throughput.

Mobile edge computing (MEC) is an enabling technology for low-latency AI applications, by caching AI services originally deployed in remote data centers to 5G base stations in network edge. Due to limited computing resource of 5G base stations, not all services can be cached in base stations to meet the resource demands of user requests. Also, if the workload of a 5G base station reaches to its resource capacity, the energy consumption of the base station will be pushed up exponentially. To reduce the energy consumption and overcome resource limitations on base stations, an alternative is to allow the base stations to collaborate with each other to admit user requests. In this paper, we investigate the problem of collaborative service caching and request offloading between a 5G-enabled MEC and remote data centers, while meeting the quality of service (QoS) requirements of users, and resource capacities on base stations that are operated by multiple selfish network service providers. We aim to maximize the total payoff of all base stations. To this end, we first propose a two-stage optimization framework: In the first stage, we develop a mechanism that adopts a best-reply rule for dynamically distributed coalition formation. In the second stage, we propose a near-optimal payoff allocation method by devising a randomized algorithm with a provable approximation ratio. We then evaluate the performance of the proposed optimization framework by extensive experimental simulations. Simulation results show that the proposed framework outperforms its counterparts by achieving at least 30% higher payoff and 20% lower energy consumption of base stations.

In this paper, we study the employment of multiple Unmanned Aerial Vehicles (UAVs) to monitor Points of Interests (PoIs) in a disaster area, e.g., collapsed buildings after an earthquake, where the UAVs can take photos and videos for the people trapped at PoIs, because such valuable information is imperative to make rescue decisions. Unlike most existing studies that ignored the monitoring time of PoIs and simply minimized the longest flying distance among the UAVs, we observe that it takes time to monitor the PoIs. Then, it is possible that the flying distance of a UAV in its flying tour may not be too long, the tour however contains many densely-located PoIs. Therefore, it will take a very long time for the UAV to monitor the PoIs in its tour. In this paper, we first formulate a problem of finding flying tours for$K$given UAVs to collaboratively monitor PoIs in a disaster area, such that the maximum spent time of the$K$UAVs among their tours is minimized, where the spent time of a UAV in its tour consists of the flying time and the PoI monitoring time. We then propose a novel$5\frac{1}{3}$-approximation algorithm for the problem, improving the best approximation ratio 6 so far for the problem of minimizing the longest flying distance among the UAVs. In addition, we extend the proposed algorithm to the case that each UAV may not be able to monitor all PoIs assigned to it, due to its limited maximum flying time (e.g., 30 minutes), and the UAV must return to its depot to replace its battery. We finally evaluate the performance of the proposed algorithms via simulation environments, and experimental results show that the proposed algorithms are very promising. Especially, the maximum spent times of the$K$UAVs in their tours by the proposed algorithms are up to 30 percent shorter than those by existing algorithms. In addition, the empirical approximation ratios of the proposed algorithms are no more than 2.4, which are much smaller than their theoretical approximation ratios that are at least$5\frac{1}{3}$.

Provisioning reliable network services for mobile users in edge computing environments is the top priority of network service providers, as unreliable services will result in tremendous losses of revenues and customers. In this paper, we study a novel service reliability augmentation problem in a mobile edge computing (MEC) network, where mobile users request network services with service function chain (SFC) and reliability expectation requirements. To enhance the service reliability of user requests, it is a common practice to make use of redundant virtualized network function (VNF) instance placement in case the primary VNF instance fails. We aim to augment the service reliability of each admitted request to its specified reliability expectation, subject to computing capacity on each cloudlet. To this end, we first formulate a novel service reliability augmentation problem for each request with an SFC and a reliability expectation requirement, by augmenting its reliability through redundant VNF instance deployment. We then show that the problem is NP-hard, and provide an admission framework of user requests by placing primary VNF instances of network functions in the SFC to different cloudlets. We then deal with the service reliability augmentation problem of an admitted request under the assumption that all secondary VNF instances of each primary VNF instance must be placed into the cloudlets no more than$l$hops from the cloudlet of its primary VNF instance for a fixed$l$with$1\leq l \leq n-1$, where$n$is the number of cloudlets in the network, for which we formulate an integer linear program solution, and develop a randomized algorithm with a good approximation ratio and high probability, at the expense of moderate resource constraint violations. We also devise a deterministic heuristic for the problem without any resource violation. We third study the service reliability augmentation problem for a set of admitted requests by extending the proposed algorithm for the service reliability augmentation problem for a single request admission. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts.

Data collection with mobile elements can improve energy efficiency and balance load distribution in wireless sensor networks (WSNs). However, complex network environments bring about inconvenience of path design. This work addresses the network environment issue, by presenting an objective-variable tour planning (OVTP) strategy for mobile data gathering in partitioned WSNs. Unlike existing studies of connected networks, our work focuses on disjoint networks with connectivity requirement and serves delay-hash applications as well as energy-efficient scenarios respectively. We first design a converging-aware location selection mechanism, which macroscopically converges rendezvous points (RPs) to lay a foundation of a short tour. We then develop a delay-aware path formation mechanism, which constructs a short tour connecting all segments by a new convex hull algorithm and a new genetic operation. In addition, we devise an energy-aware path extension mechanism, which selects appropriate extra RPs according to specific metrics in order to reduce the energy depletion of data transmission. Extensive simulations demonstrate the effectiveness and advantages of the new strategy in terms of path length, energy depletion, and data collection ratio.

More and more 5G and AI applications demand flexible and low-cost processing of their traffic through diverse virtualized network functions (VNFs) to meet their security and privacy requirements. As such, the Network Function Virtualization (NFV) market has been emerged as a major service market that allows network service providers to trade their network services among customers. Since each service market usually involves complex interplays among players with different roles, efficient mechanisms that guarantee stable and efficient operations of the NFV market are urgently needed. One fundamental problem in the NFV market is how to maximize the social welfare of all players so that all players have incentives to participate in the activities of the market. In this paper, we first formulate a novel social welfare maximization problem in an NFV market of a multi-tier edge cloud network, with the aim to maximize the total revenue collected from all players, and we implement VNF services on Virtual Machines (VMs) leased by service providers to fulfill customers with service requests, where the edge cloud network consists of both cloudlets in edge networks and remote data centers in the core network. We then design an efficient incentive-compatible mechanism for the problem, and analyze the existence of a Nash equilibrium of the mechanism. Also, we consider an online social welfare maximization problem with uncertain values of customers and without the knowledge of future request arrivals, for which we devise an online learning algorithm by adopting the Multi-Armed Bandits (MAB) method with a bounded regret. We finally evaluate the performance of the proposed mechanisms through simulations and a testbed. Results show that the proposed mechanisms deliver up to 27% higher social welfare than those of existing studies

In this paper we study the deployment of multiple unmanned aerial vehicles (UAVs) to form a temporal UAV network for the provisioning of emergent communications to affected people in a disaster zone, where each UAV is equipped with a lightweight base station device and thus can act as an aerial base station for users. Unlike most existing studies that assumed that a UAV can serve all users in its communication range, we observe that both computation and communication capabilities of a single lightweight UAV are very limited, due to various constraints on its size, weight, and power supply. Thus, a single UAV can only provide communication services to a limited number of users. We study a novel problem of deploying$K$UAVs in the top of a disaster area such that the sum of the data rates of users served by the UAVs is maximized, subject to that (i) the number of users served by each UAV is no greater than its service capacity; and (ii) the communication network induced by the$K$UAVs is connected. We then propose a$\frac {1-1/e}{\lfloor \sqrt {K} \rfloor }$-approximation algorithm for the problem, improving the current best result of the problem by five times (the best approximation ratio so far is$\frac {1-1/e}{5(\sqrt {K} +1)}$), where$e$is the base of the natural logarithm. We finally evaluate the algorithm performance via simulation experiments. Experimental results show that the proposed algorithm is very promising. Especially, the solution delivered by the proposed algorithm is up to 12% better than those by existing algorithms.

In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding a data collection tour for each UAV. To ensure the ‘freshness’ of the collected data, the total time spent in the tour of each UAV that consists of the UAV flying time and data collection time must be no greater than a given delay$B$, e.g., 20 minutes. In this paper, we consider a problem of deploying the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour of any UAV is no greater than$B$. Specifically, we study two variants of the problem: one is that a UAV needs to fly to the location of each IoT device to collect its data; the other is that a UAV is able to collect the data of an IoT device if the Euclidean distance between them is no greater than the wireless transmission range of the IoT device. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio$4\frac {4}{7}$for it so far. For the second variant, we devise the very first constant factor approximation algorithm. We also evaluate the performance of the proposed algorithms via extensive experiment simulations. Experimental results show that the numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms on average.

The Internet of Things (IoT) technology provisions unprecedented opportunities to evolve the interconnection among human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated Mobile Edge Computing (MEC) with remote clouds is a promising platform to enable delay-sensitive service provisioning for IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices. Thus, computation-intensive and sensing data from IoT devices can be offloaded to the MEC network immediately for processing, and the service response latency can be significantly reduced. In this paper, we first formulate two novel optimization problems for delay-sensitive IoT applications, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction on the use of the services provided by the MEC, and show the NP-hardness of the defined problems. We then devise efficient approximation and online algorithms with provable performance guarantees for the problems in a special case where the bandwidth capacity constraint is negligible. We also develop efficient heuristic algorithms for the problems with the bandwidth capacity constraint. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising in reducing service delays and enhancing user satisfaction, and the proposed algorithms outperform their counterparts by at least 10.8 percent.

Augmented Reality (AR) has various practical applications in healthcare, education, and entertainment. To provide a fully interactive and immersive experience, AR applications require extremely high responsiveness and ultra-low processing latency. Mobile edge computing (MEC) has shown great potential in meeting such stringent requirements and demands of AR applications by implementing AR requests in edge servers within the close proximity of these applications. In this paper, we investigate the problem of reward maximization for AR applications with uncertain demands in an MEC network, such that the reward of provisioning services for AR applications is maximized and the responsiveness of AR applications is enhanced, subject to both network resource capacity. We devise an exact solution for the problem if the problem size is small, otherwise we develop an efficient approximation algorithm with a provable approximation ratio for the problem. We also devise an online learning algorithm with a bounded regret for the dynamic reward maximization problem without the knowledge of the future arrivals of AR requests, by adopting the technique of Multi-Armed Bandits (MAB). We evaluate the performance of the proposed algorithms through simulations. Experimental results show that the proposed algorithms outperform existing studies by 17 % higher reward.

In this paper, we study the deployment of Unmanned Aerial Vehicles (UAVs) to collect data from IoT devices, by finding the data collection tour of each UAV. To ensure the `freshness' of the collected data, a strict requirement is that the total time spent in the tour of each UAV, which consists of UAV flying time and data collection time, must be no greater than a given maximum data collection delay B, e.g., 20 minutes. In this paper, we consider a problem of using the minimum number of UAVs and finding their data collection tours, subject to the constraint that the total time spent in each tour is no greater than B. We study two variants of the problem, one is that a UAV needs to fly to the location of each IoT device to collect its data; the other variant is that a UAV is able to collect the data of the IoT device as long as their Euclidean distance is no greater than a given wireless transmission range. For the first variant of the problem, we propose a novel 4-approximation algorithm, which improves the best approximation ratio 4 4/7 so far. For the second variant, we design the first constant factor approximation algorithm. In addition, we evaluate the performance of the proposed algorithms via extensive experiments, and experimental results show that the average numbers of UAVs deployed by the proposed algorithms are from 11% to 19% less than those by existing algorithms.

Energy harvesting rates of sensors in renewable (e.g., solar energy) wireless sensor networks are not only lower than their energy consumption rates but also temporally varying. Existing studies exploited spatial data correlations among sensors to reduce their energy consumptions, where the data correlations mean that the sensing data of nearby sensors have high similarities. They assumed that the sensing data of nearby sensors are very likely to highly correlated. They adopted a coarse-grained spatial-correlation model, in which sensors are partitioned into different clusters such that the sensors in the same cluster have high data similarities with each other. Then, only the sensor with the maximum residual energy in each cluster sends its sensing data, while the other sensors do not. We, however, notice that the data similarities among nearby sensors in real sensor networks may vary significantly, i.e., ranging from very similar to not similar at all. Since the existing algorithms require that the sensors in the same cluster have high data similarities with each other, the sensors in a network may be partitioned into many clusters and each cluster consists of only a few sensors, where two nearby sensors belong to two different clusters if the sensing data of the two sensors are not highly correlated. Therefore, in the existing studies, many sensors have to send all their data as there are many clusters. Unlike the existing studies, in this article, we first propose a fine-grained spatial correlation model, in which sensors are partitioned into only a few clusters and each cluster consists of many sensors. Then, each cluster master sensor sends all its data to the sink, while the majority of other sensors in the cluster transmit only their nonredundant data, thereby significantly saving sensor energy consumptions. We formulate a novel sensor clustering problem under the proposed model, which is to partition sensors into different clusters and choose a representative sensor for each cluster such that the amount of suppressed redundant data transmissions is maximized. We propose a randomized (0.5-ε)-approximation algorithm for the clustering problem, where E is a given constant with 0 <; ε ≤ 0.5. To further reduce sensor energy consumption, we consider temporal data correlations, where the sensing data by a sensor in a short period are likely to be highly correlated. We investigate a data utility maximization problem that allocates sensor data rates and routing so that the accumulative utility of both spatially and temporally correlated data received by the sink is maximized. We devise a near-optimal algorithm for the problem. We finally evaluate the performance of the proposed algorithms through experiments. the experimental results show that the proposed algorithms are very promising.

Using hierarchical CNN, the company's multiple news is characterized as three levels: sentence vectors, chapter vectors, and enterprise sentiment vectors. By combining the stock price data with the news lyric data at the same time, the influence of news on price is used to achieve correlation analysis of news information and stock prices. A two-channel attention mechanism fusion model based on CNN-LSTM is proposed. After the dual-channel feature extraction, the attention layer fusion layer is used to convert the weighted values of LSTM hidden variables, so the stock price can be predicted with the news text.

Mobile edge computing becomes a promising technology to mitigate the latency of various cloud services. In addition, network function virtualization (NFV) has been shown a great potential in reducing the operational cost of cloud services while enhancing the flexibility of virtual network function deployments, by implementing dedicated hardware network functions as pieces of software in generic servers. Recently, the GPU acceleration has been investigated to speed up flow processing in virtual network functions (VNFs), by leveraging the parallelism of GPUs. VNFs that need accelerations prefer to stay at cloudlets (locations) equipped with GPUs. However, little attention has been paid for the VNF placement that takes into account GPU-affinity in cloudlets of mobile edge clouds. In this paper, we consider the affinity-aware throughput maximization problem in a mobile edge cloud via leveraging the parallelism on GPUs for user requests with VNF requirements. We consider two types of affinities in the VNF placement: Thesoft-affinitythat allows VNFs to be executed by either CPUs or GPUs in cloudlets; and thehard-affinitythat only allows VNFs to be placed to the GPUs of a specified set of cloudlets. We formulate two corresponding VNF placement problems in a mobile edge cloud. Specifically, we first propose an exact solution to the soft-affinity throughput maximization problem by formulating an Integer Linear Program (ILP). We then propose an efficient algorithm for the problem, by proposing a randomized algorithm with a provable approximation ratio for the hard-affinity-aware throughput maximization problem and extending the proposed approximation algorithm to the soft-affinity throughput maximization problem. Furthermore, assuming that user requests arrive into the mobile edge cloud one by one without the knowledge of future arrivals, we devise an online algorithm with a good competitive ratio for this dynamic hard-affinity-aware throughput maximization problem. Finally, we evaluate the performance of the proposed algorithms, through simulations and implementations in a real test-bed. Experimental results show that the performance of the proposed algorithms outperform their existing counterparts and achieve higher throughput.

In this work, we simulate the early visual information processing mechanisms in biological visual system (BVS) to solve the visible-infrared image fusion (VIIF) task. Concretely, both infrared and visible images are first processed with a dynamic receptive field (DRF), which is imitated by a Difference of Gaussian (DoG) function whose parameters are adjusted according to local image statistics (e.g., local edge responses). The DRF processing produces two components for each source image (e.g., the visible image or the infrared image) that respectively represent the results of On-center based DRF and Off-center based DRF. Then, the results of On-center based DRF for visible image are fused with the results of Off-center based DRF for infrared image and the results of On-center based DRF for infrared image are fused with the results of Off-center based DRF for visible image, according to the mechanisms of cortex-based center-surround fusion. Algorithmically, this step fuses the visible and infrared images processed by DRF with On-center and Off-center according to the different levels of local homogeneity. Moreover, a feedward signal acting as the sub-cortical flow is also introduced to adjust the results during the fusion. The final output image is simply obtained by the summation of two components after the cortex and sub-cortex based fusion. Qualitative and quantitative tests on four datasets demonstrate that our approach can fuse the infrared and visible images effectively with the good background details and discernible salient areas. We emphasize the importance of corticothalamic feedback, cortex and sub-cortex-based fusion, and the interactions between On-center pathway and Off-center pathway that are ubiquitous in BVS for producing the high-quality visual signals.

Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in wireless rechargeable sensor networks (WRSNs). Existing studies focused mainly on the one-to-one charging scheme that a single sensor can be charged by a mobile charger at each time, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme, the multi-node charging scheme that allows multiple sensors to be charged simultaneously by a mobile charger, becomes dominant, which can mitigate charging scalability and improve charging efficiency. However, most previous studies on this multi-node energy charging scheme focused on the use of a single mobile charger to charge multiple sensors simultaneously. For large scale WRSNs, it is insufficient to deploy only a single mobile charger to charge many lifetime-critical sensors, and consequently sensor expiration durations will increase dramatically. To charge many lifetime-critical sensors in large scale WRSNs as early as possible, it is inevitable to adopt multiple mobile chargers for sensor charging that can not only speed up sensor charging but also reduce expiration times of sensors. This however poses great challenges to fairly schedule the multiple mobile chargers such that the longest charging delay among sensors is minimized. One important constraint is that no sensor can be charged by more than one mobile charger at any time due to the fact that the sensor cannot receive any energy from either of the chargers or the overcharging will damage the recharging battery of the sensor. Thus, finding a closed charge tour for each of the multiple chargers such that the longest charging delay is minimized is crucial. In this paper we address the challenge by formulating a novel longest charging delay minimization problem. We first show that the problem is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, and outperforms existing algorithms in various settings.

In this article we study a generalized team orienteering problem (GTOP), which is to find service paths for multiple homogeneous vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoTs and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this article, we first formulate the GTOP problem, where each node can be served by different vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e)1/2+e)-approximation algorithm for the problem, where ε is a given constant with 0 <; ε ≤ 1 and e is the base of the natural logarithm. In particular, the approximation ratio is about 0.33 when ε = 0.5. In addition, we devise an improved approximation algorithm for a special case of the problem where the profit is the same by serving a node once and multiple times. We finally evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Especially, the profit sums delivered by the proposed algorithms are up to 14% higher than those by existing algorithms, and about 93.6% of the optimal solutions.

Wireless charging has been demonstrated as a promising technology for prolonging device operational lifetimes in Wireless Rechargeable Networks ( WRNs ). To schedule a mobile charger to move along a predesigned trajectory to charge devices, most existing studies assume that the precise location information of devices is already known. Unfortunately, this assumption does not always hold in real mobile application, because the activities of the vast majority of mobile devices carried by mobile agents appear dynamic and random. To the best of our knowledge, this is the first work to study how to wirelessly charge mobile devices with non-deterministic mobility. We aim to provide effective charging service to them, subject to the energy capacity of the mobile charger. We formalize the effective charging problem as a charging reward maximization problem ( CRMP ), where the amount of reward obtained by charging a device is inversely proportional to the residual lifetime of the device. Then, we prove that CRMP is NP-hard. To derive an effective charging heuristic, an algorithm based on Reinforcement Learning ( RL ) is proposed. The evaluation results show that the RL-based charging algorithm achieves excellent charging effectiveness. We further interpret the learned heuristic to gain deep and valuable insights into the design options.

With increasing focus on Artificial Intelligence (AI) applications, Deep Neural Networks (DNNs) have been successfully used in a number of application areas. As the number of layers and neurons in DNNs increases rapidly, significant computational resources are needed to execute a learned DNN model. This ever-increasing resource demand of DNNs is currently met by large-scale data centers with state-of-the-art GPUs. However, increasing availability of mobile edge computing and 5G technologies provide new possibilities for DNN-driven AI applications, especially where these application make use of data sets that are distributed in different locations. One fundamental process of a DNN-driven application in mobile edge clouds is the adoption of “inferencing” - the process of executing a pre-trained DNN based on newly generated image and video data from mobile devices. We investigate offloading DNN inference requests in a 5G-enabled mobile edge cloud (MEC), with the aim to admit as many inference requests as possible. We propose exact and approximate solutions to the problem of inference offloading in MECs. We also consider dynamic task offloading for inference requests, and devise an online algorithm that can be adapted in real time. The proposed algorithms are evaluated through large-scale simulations and using a real world test-bed implementation. The experimental results demonstrate that the empirical performance of the proposed algorithms outperform their theoretical counterparts and other similar heuristics reported in literature.

Charging scheduling plays a significant role in wireless rechargeable sensor networks (WRSNs), which benefit from stable and reliable energy supplements via wireless charging. This paper proposes an importance-different charging scheduling (IDCS) strategy for improving charging utility as well as reducing the data loss. The unique feature of IDCS is that, it distinguishes nodes by means of different importance of data delivery. The Matroid theory is used to achieve our goals. First, two important factors are determined in the Matroid model, i.e., the deadline of the task and the penalty value of the task. Moreover, a greedy algorithm of task classification is designed to minimize the data loss. All tasks are divided into the early tasks and the delayed tasks, and the node with greater importance and shorter deadline has a higher priority of being included into the early tasks. In addition, a charging sequence adjustment approach is proposed to maximize the charging utility. This approach aims to exchange the sequence of different nodes in the trajectory of the mobile charger for exploring a shorter path. Several simulations verified the effectiveness and advantages of our charging scheduling strategy in terms of the node failure rate and total data loss.

Mobile edge computing (MEC) is emerging as an enabling technology of low-latency network services, such as Augmented Reality (AR) and Virtual Reality (VR), by deploying cloudlets in locations close to users. In MEC networks, telcooperators can place their services to cloudlets, such that the service accessing delay of users is minimized. In this paper, we investigate a fundamental problem of caching services that are originally deployed in remote clouds to cloudlets in an MEC network within the proximity of users. Specifically, we focus on the service caching problem in a two-tiered MEC network with both remote clouds and cloudlets that are close to users, in which multiple network service providers competing computing and bandwidth resources. This setting is significantly different from existing studies that focused on offloading user tasks from mobile devices to cloudlets in MEC networks that typically do not consider a service market with multiple network service providers. For the service caching problem in a two-tiered MEC network, we propose a novel approximation-restricted framework that guarantees the stableness of the service market. Under the proposed framework, an approximation algorithm with an approximation ratio for the problem with non-selfish players and an efficient, stable Stackelberg congestion game with selfish players have been proposed. We also analyze the Price of Anarchy (PoA) of the proposed Stackelberg congestion game to measure the efficiency of the proposed game degrades due to selfish behavior of network service providers. We finally evaluate the performance of our mechanism on both simulated environments and a real test-bed. Results show that the performance of our proposed mechanism is promising.

Provisioning reliable network services for mobile users in a mobile edge computing environment is the top priority for most network service providers, as unreliable or severely failed services will result in tremendous loss on their revenues and consumers. In this paper, we study a novel service reliability augmentation problem in a Mobile Edge-Cloud (MEC) network, where mobile users request various network services through issuing requests with service function chain (SFC) requirements and reliability expectations, and an admitted request may not meet its reliability expectation initially. To enhance its service reliability to reach its expectation, it is a common practice to make use of redundant backups, that is to place redundant VNF instances of each Virtual Network Function (VNF) in its SFC in case its primary VNF instance fails. In this paper, we aim to augment the reliability of each admitted request as much as possible with the ultimate objective to reach its reliability expectation, subject to computing capacity on each cloudlet in the network. To this end, we first formulate a novel service reliability augmentation problem. We then deal with the problem for the admitted request under the assumption that all the secondary VNF instances of each primary VNF instance in its SFC must be placed into the cloudlets no more than l hops from the cloudlet of the primary VNF instance, where 1 ≤ l ≤ n − 1 and n is the number of cloudlets in the network, for which we propose an integer linear program (ILP) solution, and develop a randomized algorithm with a provable approximation ratio while a moderate resource constraint violation. We also devise an efficient heuristic algorithm for the problem without any resource constraint violation. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and their empirical results are superior to their analytical counterparts.

With the maturation of wireless charging technology, Wireless Rechargeable Sensor Networks (WRSNs) has become a promising solution for prolong network lifetimes. Recently studies propose to employ a mobile charger (MC) to simultaneously charge multiple sensors within the same charging range, such that the charging performance can be improved. In this paper, we aim to jointly optimize the number of dead sensors and the energy usage effectiveness in such multi-node charging scenarios. We achieve this by introducing the partial charging mechanism, meaning that instead of following the conventional way that each sensor gets fully charged in one time step, our work allows MC to fully charge a sensor by multiple times. We show that the partial charging mechanism causes minimizing the number of dead sensors and maximizing the energy usage effectiveness to conflict with each other. We formulate this problem and develop a multi-node temporal spatial partial-charging algorithm (MTSPC) to solve it. The optimality of MTSPC is proved, and extensive simulations are carried out to demonstrate the effectiveness of MTSPC.

In this paper we study a team orienteering problem, which is to find service paths for multiple vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoT and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this paper, we first formulate the team orienteering problem, where different vehicles are different types, each node can be served by multiple vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e)1/2+ε)approximation algorithm for the problem, where c is a given constant with 0 ≤ ε ≤ 1 and ε is the base of the natural logarithm. In particular, the approximation ratio is no less than 0.32 when ε = 0.5. In addition, for a special team orienteering problem with the same type of vehicles and the profits of serving a node once and multiple times being the same, we devise an improved approximation algorithm. Finally, we evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Precisely, the profit sums delivered by the proposed algorithms are approximately 12.5% to 17.5% higher than those by existing algorithms.

Wireless charging has been demonstrated as a promising technology for prolonging device operational lifetimes in Wireless Rechargeable Networks (WRNs). To schedule a mobile charger to move along a predesigned trajectory to charge devices, most existing studies assume that the precise location information of devices is already known. Unfortunately, this assumption does not always hold in real mobile application, because the activities of vast majority of mobile devices carried by mobile agents appear dynamic and random. To the best of our knowledge, this is the first work to study how to wirelessly charge mobile devices with non-deterministic mobility. We aim to provide effective charging service to them, subject to the energy capacity of the mobile charger. Then, we formalize the effective charging problem as a charging reward maximization problem (CRMP), where the amount of reward obtained by charging a de-vice is inversely proportional to the residual lifetime of the device. To derive an effective charging heuristic, an algorithm based on Reinforcement Learning (RL) is proposed. The evaluation results show that the RL-based charging algorithm achieves excellent charging effectiveness. We further interpret the learned heuristic to gain deep and valuable insights into the design options.

In this paper, we study sensing data collection from IoT devices in a wireless sensor network, using an energy-constrained Unmanned Aerial Vehicle (UAV), where the sensory data is stored in IoT devices while the IoT devices may or may not be within the transmission range of each other. We formulate two novel data collection problems to fully or partially collect data from IoT devices using the UAV, by finding a closed tour for the UAV that includes hovering locations and the sojourn duration at each of the hovering locations such that the accumulative volume of data collected is maximized, subject to the energy capacity on the UAV, where the UAV consumes its energy on both hovering and flying from one hovering location to another hovering location. To this end, we first propose a novel data collection framework that enables the UAV to collect the sensory data from multiple IoT devices simultaneously if the IoT devices are within the hovering coverage range of the UAV. We then formulate two data collection maximization problems, and show that both of the problems are NP-hard. We instead devise efficient approximation and heuristic algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrated that the proposed algorithms are promising.

The Internet of Things (IoT) technology offers unprecedented opportunities to interconnect human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated MEC with remote clouds is a promising platform, where edge-clouds (cloudlet) are co-located with wireless access points in the proximity of IoT devices, thus intensive-computation and sensing data from IoT devices can be offloaded to the MEC network for processing, and the service response latency can be significantly reduced. In this paper, we study delay-sensitive service provisioning in an MEC network for IoT applications. We first formulate two novel optimization problems, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction of using the services provided by the MEC. We then show that the defined problems are NP-hard. We instead devise efficient approximation and online algorithms with provable performance guarantees for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.

Machine learning (ML) has been penetrating into our daily life by facilitating many daily applications, e.g., self-driving, cloud gaming, product fault detection and drones. Meanwhile, there is an emerging trend that adopts ML methods into network optimization problems, such as flow classification, traffic engineering, routing, and etc. Conventional ML methods need careful training for a specific application of a given network structure, and the trained model normally cannot be applied to other applications and network structures. In this paper, we aim to design adaptive ML methods for network optimization problems, with the trained models having the ability of being deployed to any similar problems. In particular, we consider the virtualized network function (VNF) provisioning problem as our target optimization problem. We first propose a deep Q-learning-based optimization framework for VNF provisioning in a mobile edge network with network capacity constraints, by devising an adaptive graph feature embedding method. We then propose a series of deep Q-learning based learning algorithms for the problems of service chaining and the throughput maximization, based on the proposed learning-based optimization framework. We also propose a novel design of master-slave dual neural network that enables the decisions on both cloudlet selections and routing path finding. To stabilize and accelerate the convergence of the proposed methods, we devise a novel environment generation and termination strategy and a new structure for the replay buffer. We also evaluate the performance of the proposed framework and algorithms by extensive simulations. Results show that the proposed algorithms outperform existing methods by around 12%, and the trained model in a network can be directly adapted to other network structures and settings.

In this paper we study the min-max cycle cover problem with neighborhoods, which is to find a given number of K cycles to collaboratively visit n Points of Interest (POIs) in a 2D space such that the length of the longest cycle among the K cycles is minimized. The problem arises from many applications, including employing mobile sinks to collect sensor data in wireless sensor networks (WSNs), dispatching charging vehicles to recharge sensors in rechargeable sensor networks, scheduling Unmanned Aerial Vehicles (UAVs) to monitor disaster areas, etc. For example, consider the application of employing multiple mobile sinks to collect sensor data in WSNs. If some mobile sink has a long data collection tour while the other mobile sinks have short tours, this incurs a long data collection latency of the sensors in the long tour. Existing studies assumed that one vehicle needs to move to the location of a POI to serve it. We however assume that the vehicle is able to serve the POI as long as the vehicle is within the neighborhood area of the POI. One such an example is that a mobile sink in a WSN can receive data from a sensor if it is within the transmission range of the sensor (e.g., within 50 meters). It can be seen that the ignorance of neighborhoods will incur a longer traveling length. On the other hand, most existing studies only took into account the vehicle traveling time but ignore the POI service time. Consequently, although the length of some vehicle tour is short, the total amount of time consumed by a vehicle in the tour is prohibitively long, due to many POIs in the tour. In this paper we first study the min-max cycle cover problem with neighborhoods, by incorporating both neighborhoods and POI service time into consideration. We then propose novel approximation algorithms for the problem, by exploring the combinatorial properties of the problem. We finally evaluate the proposed algorithms via experimental simulations. Experimental results show that the proposed algorithms are promising. Especially, the maximum tour times by the proposed algorithms are only about from 80% to 90% of that by existing algorithms.

Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in Wireless Rechargeable Sensor Networks (WRSNs). Existing studies focused mainly on the 'one-to-one' charging scheme that a sensor can be charged by a single mobile charger at each time, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme - the 'multiple-to-one' charging scheme that allows multiple sensors to be charged simultaneously by a single charger, becomes dominant and can mitigate charging scalability and improve the charging efficiency. Most research studies on this latter scheme focused on the use of a mobile charger to charge multiple sensors simultaneously. However, for large scale WRSNs, it is insufficient to deploy just a single mobile charger to charge many lifetime-critical sensors, and consequently sensor expiration durations will increase dramatically. Instead, in order to charge as many as lifetime-critical sensors, the use of multiple mobile chargers for charging sensors can speed up sensor charging significantly, thereby reducing their expiration durations and improving the monitoring quality of WRSNs. However, this poses great challenges to schedule multiple mobile chargers for sensor charging at the same time such that the longest delay among the chargers is minimized due to multiple critical constraints. One such an important constraint in multiple mobile chargers is that each sensor cannot be charged by more than one mobile charger at each time; otherwise, the sensor cannot receive any energy from either of the chargers. In this paper we address this challenge by first formulating a novel longest delay minimization problem that is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is very promising, which outperforms the other heuristics in various settings.

Unmanned aerial vehicles (UAVs) are emerging as promising devices to provide valuable information in rescue applications, which can be dispatched to take photographs for points of interests in disaster areas where humans are hard to approach. Most existing studies focused on the limited energy capacity issue of UAVs when they take photographs, which however ignored an important fact, that is, the photographs taken by the UAVs usually are highly redundant. In this paper we study a novel monitoring quality maximization problem to find a flying tour for an energy-constrained UAV, such that the amount of nonredundant information of the photographs taken by the UAV in its tour is maximized. Due to NP-hardness of the problem, we first propose an approximation algorithm with a quasi-polynomial time complexity. We then devise a fast yet scalable heuristic algorithm for the problem. We finally evaluate the performance of the proposed algorithms via both a real dataset and extensive simulations. Experimental results show that the proposed algorithms are very promising. Especially, the amounts of nonredundant information by the proposed approximation and heuristic algorithms are about 11% and 8% larger than that by the state-of-the-art, respectively. To the best of our knowledge, we are the first to consider the novel problem of collecting nonredundant information with an energy-constrained UAV.

Sensing data collection in energy harvesting sensor networks poses great challenges, since energy generating rates of different sensors vary significantly. Most existing studies on efficient data collection assumed that the sensing data from a sensor is temporally independent. We however notice that such sensing data usually is highly temporally correlated, rather than independent. In this paper, we study the problem of allocating energy and data rates to sensors, and performing sensing data routing in an energy harvesting sensor network for a given monitoring period, such that the utility sum of temporally correlated data collected from sensors in the period is maximized, subject to the temporally spatially varying harvesting energy constraint on each sensor. We then propose a near-optimal algorithm for the data utility maximization problem. We finally evaluate the performance of the proposed algorithm with real solar energy data. Experimental results show that the proposed algorithm is very promising and the utility sum of collected sensing data is up to 10% larger than that by the state-of-the-art.

Servo drives require high dynamics and reliability on speed control. Conventional cascade linear controllers suffer from the proportional-integral parameters tuning work and low dynamic response, due to their cascaded structure. In this paper, an improved model predictive direct speed control is proposed with rapid speed tracking and very small speed offset. The new control scheme eliminates the cascaded structure by predicting the future speed in discrete steps. The optimal voltage vector to control the motor is then selected according to an evaluation criterion for speed and flux tracking. To reduce the system cost and improve the reliability, a load torque observer is adopted to estimate the actual load torque. Besides, to avoid torque oscillations and overshoots during rapid speed variation, a torque suppression factor is incorporated into the cost function. Furthermore, a myopic prediction correction method is developed to enhance both the dynamic and steady-state responses. Simulation and hardware-in-the-loop results are presented to validate the effectiveness of the proposed method.

Wireless energy transfer technology based on magnetic resonant coupling has emerged as a promising technology for wireless sensor networks, by providing controllable yet continual energy to sensors. In this paper, we study the use of a mobile charger to wirelessly charge sensors in a rechargeable sensor network so that the sum of sensor lifetimes is maximized while the travel distance of the mobile charger is minimized. Unlike existing studies that assumed a mobile charger must charge a sensor to its full energy capacity before moving to charge the next sensor, we here assume that each sensor can be partially charged so that more sensors can be charged before their energy depletions. Under this new energy charging model, we first formulate two novel optimization problems of scheduling a mobile charger to charge a set of sensors, with the objectives to maximize the sum of sensor lifetimes and to minimize the travel distance of the mobile charger while achieving the maximum sum of sensor lifetimes, respectively. We then propose efficient algorithms for the problems. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are very promising. Especially, the average energy expiration duration per sensor by the proposed algorithm for maximizing the sum of sensor lifetimes is only 9 percent of that by the state-of-the-art algorithm while the travel distance of the mobile charger by the second proposed algorithm is only about from 1 to 15 percent longer than that by the state-of-the-art benchmark.

Wireless energy transfer is a promising technology to prolong the lifetime of wireless sensor networks (WSNs), by employing charging vehicles to replenish energy to lifetime-critical sensors. Existing studies on sensor charging assumed that one or multiple charging vehicles being deployed. Such an assumption may have its limitation for a real sensor network. On one hand, it usually is insufficient to employ just one vehicle to charge many sensors in a large-scale sensor network due to the limited charging capacity of the vehicle or energy expirations of some sensors prior to the arrival of the charging vehicle. On the other hand, although the employment of multiple vehicles can significantly improve the charging capability, it is too costly in terms of the initial investment and maintenance costs on these vehicles. In this paper, we propose a novel charging model that a charging vehicle can carry multiple low-cost removable chargers and each charger is powered by a portable high-volume battery. When there are energy-critical sensors to be charged, the vehicle can carry the chargers to charge multiple sensors simultaneously, by placing one portable charger in the vicinity of one sensor. Under this novel charging model, we study the scheduling problem of the charging vehicle so that both the dead duration of sensors and the total travel distance of the mobile vehicle per tour are minimized. Since this problem is NP-hard, we instead propose a (3+ϵ)-approximation algorithm if the residual lifetime of each sensor can be ignored; otherwise, we devise a novel heuristic algorithm, where ϵ is a given constant with 0 < ϵ ≤ 1. Finally, we evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the performance of the proposed algorithms are very promising.

If the local area of a three-dimensional object surface can be considered as a plane, the deformation between its two images captured from different camera placements is modelled by a homography. By tuning the parameters in a homographic mapping, all possible deformations caused by the change of camera placement can be simulated for the local feature matching method. Since aliasing may happen when resampling the original image to the geometry of the simulated image, an antialiasing convolution must be applied before resampling. However, the antialiasing convolution itself must also be homography-adaptive. In the scale invariant feature transform (SIFT) or affine-SIFT (ASIFT) method, the similitude or affine rectification scheme of the convolution is applied to solve this problem under similitude or affine mapping. However, these schemes will not work under homographic or perspective mapping. Although the perspective invariant matching method (perspective-SIFT or PSIFT) has been proposed in some references, the antialiasing scheme with perspective-adaption has not been proposed. This paper will show that the standard convolution is not adaptive to the change of planar mapping, and the simulated images under the same simulated camera placement will not be identical if they are resampled from different original images captured from different camera placements. To solve this issue, a natural extension of the standard convolution, the mapping-adaptive convolution (MA-convolution), is proposed, and its mapping-adaption is proved mathematically in this paper. Based on this novel convolution, the homography invariant simulation scheme can be modelled. We have applied the MA-convolution to the antialiasing scheme in the PSIFT method, and the effectiveness of the MA-convolution has been verified experimentally.

Recent studies show that individuals in a social network can be divided into different groups of densely connected communities, and these individuals who bridge different communities, referred to as structural hole spanners, have great potential to acquire resources/information from communities and thus benefit from the access. Structural hole spanners are crucial in many real applications such as community detections, diffusion controls, viral marketing, etc. In spite of their importance, little attention has been paid to them. Particularly, how to accurately characterize the structural hole spanners and how to devise efficient yet scalable algorithms to find them in a large social network are fundamental issues. In this paper, we study the top-k structural hole spanner problem. We first provide a novel model to measure the quality of structural hole spanners through exploiting the structural hole spanner properties. Due to its NP-hardness, we then devise two efficient yet scalable algorithms, by developing innovative filtering techniques that can filter out unlikely solutions as quickly as possible, while the proposed techniques are built up on fast estimations of the upper and lower bounds on the cost of an optimal solution and make use of articulation points in real social networks. We finally conduct extensive experiments to validate the effectiveness of the proposed model, and to evaluate the performance of the proposed algorithms using real world datasets. The experimental results demonstrate that the proposed model can capture the characteristics of structural hole spanners accurately, and the structural hole spanners found by the proposed algorithms are much better than those by existing algorithms in all considered social networks, while the running times of the proposed algorithms are very fast.

Smartphones now become an indispensable part of our daily life. However, maintaining a smartphone's continuing operation consumes lots of battery energy. For example, a fully-charged smartphone usually cannot support its continuing operation for a whole day. A fundamental issue on a smartphone is its energy issue. That is, how to prolong the lifetime of a smartphone so that it can run as long as possible to meet its user needs. Wireless energy transfer has been demonstrated as a promising technique to address this issue. In this paper, we study a novel smartphone charging problem, through wireless chargers deployed on public commuters, e.g., subway trains, to charge energy-critical smartphones when their users take subway trains to work or go home. Since the amounts of residual energy of different smartphones are significantly different, the charging satisfactions of different users are essentially different. In this paper, we formulate this charging satisfaction problem as a novel optimization problem that schedules the limited number of wireless chargers on subway trains to charge energy-critical smartphones such that the overall charging satisfaction of smartphone users is maximized, for a given monitoring period (e.g., one day). Forthis problem, we first devise a 1/3-approximation algorithm if the travel trajectory of each smartphone user is given. We then propose an online algorithm to deal with dynamic energy-critical smartphone charging requests. We also propose a nontrivial distributed scheduling algorithm for a variant of the problem where the global knowledge of user energy information is unknown. We finally evaluate the performance of the proposed algorithms through experimental simulations, using a real dataset of subway-taking in San Francisco. The experimental results show that the proposed algorithms are very promising, and over 90 percent of energy-critical user smartphones can be satisfactorily charged in a one-day monitoring period.

Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged; another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.

Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the data control plane from the data plane. The forwarding routing table at each of its switch nodes is usually implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited number of entries, and the bandwidth at each of its links is bounded too. Under this new network architecture, providing a quality service to users by admitting user requests to meet their resource demands is challenging, and very little attention has ever been paid in this regard. In this paper, we will study online unicast and multicast request admissions in SDNs with the aim to maximize the network throughput under both critical network resources and user bandwidth demand constraints, for which we first propose a novel model to characterize the usage costs of node and link resources. We then devise efficient online algorithms for unicast and multicast requests. We also analyze the competitive ratios of the proposed online algorithms, which are O(log n) and O(Kϵlog n) for unicasting and multicasting, respectively, where n is the network size, K is the maximum number of members in a multicast request, and ϵ is a constant with 0 <; e ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.

The wireless energy transfer technology based on magnetic resonant coupling has emerged as a promising technology for wireless sensor networks, by providing controllable yet perpetual energy to sensors. In this paper we study the use of a mobile charger to wirelessly charge sensors in a rechargeable sensor network so that the sum of sensor lifetimes is maximized while the traveling distance of the mobile charger is minimized. Unlike existing studies that assumed a mobile charger must charge a sensor to its full energy capacity before moving to charge the next sensor, in this paper we assume that each sensor can be partially charged so that more sensors can be charged by the mobile charger before their energy depletions. Under this new charging model, we first formulate a novel optimization problem of scheduling the mobile charger to charge life-critical sensors with an objective to maximize the sum of sensor lifetimes, while minimizing the traveling distance of the mobile charger. Due to NP-hardness of the problem, we then propose an efficient algorithm for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is very promising.

Wireless energy transfer technology based on magnetic resonant coupling has been emerging as a promising technology for wireless sensor networks (WSNs) by providing controllable yet perpetual energy to sensors. In this article, we study the deployment of the minimum number of mobile charging vehicles to charge sensors in a large-scale WSN so that none of the sensors will run out of energy, for which we first advocate a flexible on-demand charging paradigm that decouples sensor energy charging scheduling from the design of sensing data routing protocols. We then formulate a novel optimization problem of scheduling mobile charging vehicles to charge life-critical sensors in the network with an objective to minimize the number of mobile charging vehicles deployed, subject to the energy capacity constraint on each mobile charging vehicle. As the problem is NP-hard, we instead propose an approximation algorithm with a provable performance guarantee if the energy consumption of each sensor during each charging tour is negligible. Otherwise, we devise a heuristic algorithm by modifying the proposed approximation algorithm. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimal ones. To the best of our knowledge, this is the first approximation algorithm with a nontrivial approximation ratio for a novel scheduling problem of multiple mobile charging vehicles for charging sensors.

Mobile cloud computing is emerging as a main ubiquitous computing platform to provide rich cloud resources for various applications of mobile devices. Although most existing studies in mobile cloud computing focus on energy savings of mobile devices by offloading computing-intensive jobs from mobile devices to remote clouds, the access delays between mobile users and remote clouds usually are long and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and can enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper, we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) consisting of many wireless Access Points (APs). We first formulate the problem as a novel capacitated cloudlet placement problem that places$K$cloudlets to some strategic locations in the WMAN with the objective to minimize the average access delay between mobile users and the cloudlets serving the users. We then propose an exact solution to the problem by formulating it as an Integer Linear Programming (ILP). Due to the poor scalability of the ILP, we instead propose an efficient heuristic for the problem. For a special case of the problem where all cloudlets have identical computing capacities, we devise novel approximation algorithms with guaranteed approximation ratios. We also devise an online algorithm for dynamically allocating user requests to different cloudlets, if the$K$cloudlets have already been placed. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising and scalable.

Abstract In this paper, we consider large‐scale remote environmental monitoring (data gathering) through deploying an unreliable wireless sensor network in a remote region. The data monitoring center is geographically located far away from the region of the sensor network, which consists of sensors and gateways. Sensors are responsible for sensing and relaying data, and gateways are equipped with 3G/4G radios and can store the collected data from sensors temporarily and transmit the data to the remote data center through a third‐party communication service. A service cost of using this service will be charged, which depends on not only the number of gateways employed but also the volume of data transmitted from each gateway within a given monitoring period. For this large‐scale, remote, and unreliable data gathering, we first formulate a problem of maximizing network throughput with minimal service cost with an objective to maximize the amount of data collected by all gateways while minimizing the service cost. We then show that the problem is NP‐complete and propose novel approximation algorithms. The key ingredients of the proposed algorithms include building load‐balanced routing trees rooted at gateways and dynamically adjusting data load among the gateways. Finally, we conduct experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are very promising, and the obtained solutions are fractional of the optimum in terms of network throughput and the data service cost. Copyright © 2015 John Wiley & Sons, Ltd.

Recent studies have shown that in social networks, users who bridge different communities, known as structural hole spanners, have great potentials to acquire available resources from these communities and gain access to multiple sources of information flow. Structural hole spanners are crucial in many applications such as community detections, diffusion controls, and viral marketing. In spite of their importance, not much attention has been paid to them. Particularly, how to characterize the structural hole spanner properties and how to devise efficient yet scalable algorithms to find them are fundamental issues. In this paper, we formulate the problem as the top-k structural hole spanner problem. Specifically, we first provide a generic model to measure the quality of structural hole spanners, by exploring their properties, and show that the problem is NP-hard. We then devise efficient and scalable algorithms, by exploiting the bounded inverse closeness centralities of vertices and making use of articulation points of the network. We finally evaluate the performance of the proposed algorithms through extensive experiments on real and synthetic datasets, and validate the effectiveness of the proposed model. Our experimental results demonstrate that the proposed model can capture the characteristics of structural hole spanners accurately, and the proposed algorithms are very promising.

Smartphones now become an indispensable part of our daily life. However, their continuing operations consume lots of battery energy. For example, a fully-charged smartphone usually cannot support its continuing operation for a whole day. A fundamental problem related to this energy issue is how to prolong the smartphone lifetime so that it can last as long as possible to meet its user needs. Wireless energy transfer has been demonstrated as a promising technique to address this challenge. In this paper, we study the smartphone charging problem, using wireless chargers deployed on public commuters, e.g., subway trains, to charge energy-critical smartphones when their users take subway trains to work or go home. Since the residual energy of different smartphones are significantly different, the charging satisfactions of different users are essentially different too. In this paper we formulate this charging problem as a novel optimization problem that allocates limited wireless chargers on subway trains to charge energy-critical smartphones such that the overall charging satisfaction of mobile users is maximized, for a given monitoring period (e.g., one day). Specifically, we first devise a 1 over 3-approximation algorithm if the travel trajectory of each smartphone user in the monitoring period is given; otherwise, we devise an online algorithm dealing with dynamic energy-critical smartphone charging requests. We finally evaluate the performance of the proposed algorithms through experimental simulations with a real dataset of subway-taking in San Francisco. The experimental results show that the proposed algorithms are very promising, and 93.9% of energy-critical user smartphones can be satisfactorily charged in one-day monitoring period.

In this paper we study the cloudlet placement problem in a large-scale Wireless Metropolitan Area Network (WMAN) that consists of many wireless Access Points (APs). Although most existing studies in mobile cloud computing mainly focus on energy savings of mobile devices by offloading computing-intensive jobs from them to remote clouds, the access delay between mobile users and the clouds usually is large and sometimes unbearable. Cloudlet as a new technology is capable to bridge this gap, and has been demonstrated to enhance the performance of mobile devices significantly while meeting the crisp response time requirements of mobile users. In this paper we consider placing multiple cloudlets with different computing capacities at some strategic local locations in a WMAN to reduce the average cloudlet access delay of mobile users at different APs. We first formulate this problem as a novel capacitated cloudlet placement problem that places K cloudlets to some locations in the WMAN with the objective to minimize the average cloudlet access delay between the mobile users and the cloudlets serving their requests. We then propose a fast yet efficient heuristic. For a special case of the problem where all cloudlets have the identical computing capacity, we devise a novel approximation algorithm with a guaranteed approximation ratio. In addition, We also consider allocating user requests to cloudlets by devising an efficient online algorithm for such an assignment. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising and scalable.

In this paper we study data collection in an energy renewable sensor network for scenarios such as traffic monitoring on busy highways, where sensors are deployed along a predefined path (the highway) and a mobile sink travels along the path to collect data from one-hop sensors periodically. As sensors are powered by renewable energy sources, time-varying characteristics of ambient energy sources poses great challenges in the design of efficient routing protocols for data collection in such networks. In this paper we first formulate a novel data collection maximization problem by adopting multi-rate data transmissions and performing transmission time slot scheduling, and show that the problem is NP-hard. We then devise an offline algorithm with a provable approximation ratio for the problem by exploiting the combinatorial property of the problem, assuming that the harvested energy at each node is given and link communications in the network are reliable. We also extend the proposed algorithm by minor modifications to a general case of the problem where the harvested energy at each sensor is not known in advance and link communications are not reliable. We thirdly develop a fast, scalable online distributed algorithm for the problem in realistic sensor networks in which neither the global knowledge of the network topology nor sensor profiles such as sensor locations and their harvested energy profiles is given. Furthermore, we also consider a special case of the problem where each node has only a fixed transmission power, for which we propose an exact solution to the problem. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are efficient and the solutions obtained are fractional of the optimum.

As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph$G$and an integer$k>0$, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in$G$with an aim to find$k$rootless (or rooted) edge-disjoint cycles covering the vertices in$V$such that the maximum cycle weight among the$k$cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a$(5{ 1\over 3} +\epsilon)$-approximation algorithm; for the uncapacitated rooted min-max cycle cover problem, we devise a$(6{ 1\over 3} +\epsilon)$-approximation algorithm; and for the capacitated rooted min-max cycle cover problem, we propose a$(7+\epsilon)$-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems$6+\epsilon$,$7+\epsilon$, and$13+\epsilon$, respectively, where$\epsilon$is a constant with$0< \epsilon <1$. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.

A random submatrix method (RSM) is proposed to calculate the low-rank decomposition U(m×r)V(n×r)(T) (r < m, n) of the matrix Y∈R(m×n) (assuming m > n generally) with known entry percentage 0 < ρ ≤ 1. RSM is very fast as only O(mr(2)ρ(r)) or O(n(3)ρ(3r)) floating-point operations (flops) are required, compared favorably with O(mnr+r(2)(m+n)) flops required by the state-of-the-art algorithms. Meanwhile, RSM has the advantage of a small memory requirement as only max(n(2),mr+nr) real values need to be saved. With the assumption that known entries are uniformly distributed in Y, submatrices formed by known entries are randomly selected from Y with statistical size k×nρ(k) or mρ(l)×l , where k or l takes r+1 usually. We propose and prove a theorem, under random noises the probability that the subspace associated with a smaller singular value will turn into the space associated to anyone of the r largest singular values is smaller. Based on the theorem, the nρ(k)-k null vectors or the l-r right singular vectors associated with the minor singular values are calculated for each submatrix. The vectors ought to be the null vectors of the submatrix formed by the chosen nρ(k) or l columns of the ground truth of V(T). If enough submatrices are randomly chosen, V and U can be estimated accordingly. The experimental results on random synthetic matrices with sizes such as 13 1072 ×10(24) and on real data sets such as dinosaur indicate that RSM is 4.30 ∼ 197.95 times faster than the state-of-the-art algorithms. It, meanwhile, has considerable high precision achieving or approximating to the best.

Energy is one of the most critical optimization objectives in wireless sensor networks. Compared with renewable energy harvesting technology, wireless energy transfer based on magnetic resonant coupling is able to provide more reliable energy supplies for sensors in wireless rechargeable sensor networks. The adoption of wireless mobile chargers (mobile vehicles) to replenish sensors' energy has attracted much attention recently by the research community. Most existing studies assume that the energy consumption rates of sensors in the entire network lifetime are fixed or given in advance, and no constraint is imposed on the mobile charger (e.g., its travel distance per tour). In this paper, we consider the dynamic sensing and transmission behaviors of sensors, by providing a novel charging paradigm and proposing efficient sensor charging algorithms. Specifically, we first formulate a charging throughput maximization problem. Since the problem is NP-hard, we then devise an offline approximation algorithm and online heuristics for it. We finally conduct extensive experimental simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are efficient.

In this paper, we study the use of multiple mobile charging vehicles to charge sensors in a large-scale wireless sensor network for a given monitoring period, where sensors can be charged by the vehicles with wireless power transfer. Since each sensor may experience multiple charges to avoid its energy expiration for the period, we first consider a charging problem of scheduling the multiple mobile vehicles to collaboratively charge sensors so that none of the sensors will run out of its energy and the sum of traveling distance (referred to as the service cost) of these vehicles can be minimized. Due to NP-hardness of the problem, we then propose a novel approximation algorithm for it, assuming that sensor energy consumption rates do not change over time. Otherwise, we devise a heuristic algorithm through minor modifications to the approximation algorithm. We finally evaluate the performance of the proposed algorithms via simulations. Experimental results show that the proposed algorithms are very promising, which can reduce upto 45% of the service cost in comparison with the service cost delivered by a greedy algorithm.

The emerging wireless energy transfer technology based on magnetic resonant coupling is a promising technology for wireless sensor networks as it can provide a controllable and perpetual energy source to sensors. In this paper we study the use of minimum number of wireless charging mobile vehicles to charge sensors in a sensor network so that none of the sensors runs out of its energy, subject to the energy capacity imposed on mobile vehicles, for which we first advocate an flexible on-demand wireless charging paradigm that decouples sensor energy charging scheduling from data routing protocols design. We then formulate an optimization problem of scheduling mobile vehicles to charge lifetime-critical sensors with an objective to minimize the number of mobile vehicles deployed, subject to the energy capacity constraint on each mobile vehicle. As the problem is NP-hard, we devise an approximation algorithm with a provable performance guarantee for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, and the solution obtained is fractional of the optimal.

In this paper, we study the use of a wireless charging vehicle (WCV) to replenish energy to sensors in a wireless sensor network so that none of the sensors will run out of its energy, where sensor batteries can be recharged. Specifically, we first propose a flexible on-demand sensor energy charging paradigm that decouples sensor energy replenishment and data collection into separate activities. We then formulate an optimization problem of wireless charging with an aim to maximize the ratio of the amount of energy consumed for charging sensors to the amount of energy consumed on traveling of the WCV as the WCV consumes its energy on both traveling and sensor charging. We also devise a novel algorithm for scheduling the tours of the WCV by jointly considering the residual lifetimes of sensors and the charging ratio of charging tours. We finally evaluate the performance of the proposed algorithm by conducting simulation. Experimental results show that the proposed algorithm is promising, and can improve the energy charging ratio of the WCV significantly.

Cooperative caching is a desirable approach to achieve efficient data access in multi-hop wireless networks. Existing cooperative caching algorithms mostly focus on cache placement. Another key issue, cache consistency, has not been adequately addressed. In this paper, we propose CACC, a cooperative approach to maintain cache consistency for wireless mesh networks. CACC combines push and pull by making use of the hierarchical architecture of mesh networks. The key contribution of CACC lies in two techniques that introduce cooperation among network nodes in delivering invalidation reports (IRs) so as to reduce communication cost and tolerate message losses. The first technique, IR integration, buffers and merges IRs at gateway nodes and periodically broadcasts them. The second technique, cooperative IR re-sending, lets intermediate nodes resend missed IR messages upon request. The interval of IR broadcast is optimized to achieve the optimal tradeoff between push and pull. We conduct numerical analysis to find optimal values for different scenarios. We also perform simulation to confirm our analysis results and compare with existing approaches. The results show that CACC can save message cost significantly (50-70 percent).

In this paper we study data collection in an energy harvesting sensor network for traffic monitoring and surveillance purpose on busy highways, where sensors are densely deployed along a pre-defined path and a mobile sink travels along the path to collect data from one-hop sensors periodically. As the sensors are powered by renewable energy sources, the time-varying characteristics of energy harvesting poses great challenges on the design of efficient routing protocols for data collection in such energy harvesting sensor networks. In this paper we first formulate a novel data collection maximization problem that deals with multi-rate transmission mechanism and transmission time slot scheduling among the sensors. We then show the NPhardness of the problem and devise an offline algorithm with a provable approximation ratio for the problem by exploiting the combinatorial property of the problem, assuming that the global knowledge of the network topology and the profile of each sensor are given. We also develop a fast, scalable online distributed solution for the problem without the global knowledge assumption, which is more suitable for real distributive sensor networks. In addition, we consider a special case of the problem for which a optimal polynomial solution is given. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are very efficient, and the solutions are fractional of the optimum.

In mobile cloud computing (MCC) paradigm, cloud service providers not only offer powerful cloud data centers but also provide small-scale cloudlets in some strategic locations for mobile users to access their rich resources. Due to the flexibility and locality of cloudlets, most requests of mobile users can be processed locally. However, the cloudlets usually have limited resources and processing abilities, which implies that they may not be capable to process every incoming request. Instead, some resource-intensive requests need to be sent to remote data centers for processing and such a processing is transparent to users. In this paper, we address the online request admission issue in a cloudlet with an objective to maximize the system throughput, for which we first propose a novel admission cost model to model critical resource consumptions. We then devise efficient control algorithms for online request admissions. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results indicate that the proposed algorithms are promising and outperform other heuristics.

In this paper we consider the use of a link-unreliable wireless sensor network for remote monitoring, where the monitoring center is geographically located far away from the region of the deployed sensor network. The sensing data is transferred to the monitoring center by the third party communication service, which incurs service cost. We first formulate a novel optimization problem of maximizing the network throughput with minimal service cost, which is shown to be NP-hard. We then develop approximation algorithms. We finally evaluate the performance of the proposed algorithms by simulations. Experimental results demonstrate that the solutions delivered by proposed algorithms are fractional to the optimum.

Cooperative caching is especially desirable for multi-hop wireless networks to achieve efficient data access. Existing cooperative caching algorithms for wireless networks mostly focus on cache placement. Another key issue, cache consistency maintenance has not been adequately addressed. In this paper, we propose the first cooperative approach to maintain cache consistency for wireless mesh networks. It basically combines push and pull by making use of the hierarchical architecture of mesh networks. More precisely, we propose two techniques introducing cooperation among network nodes in delivering Invalidation Reports (IR) so as to reduce communication cost and tolerate message losses: IR integration buffers and integrates IRs at the gateway nodes and periodically broadcasts them, Cooperative IR re-sending lets the intermediate nodes resend missed IR messages upon request. The most challenging issue in our design is the determination of the optimal IR broadcast period in order to achieve the optimal tradeoff between push and pull. We conduct numerical analysis to get optimal values for different scenarios. Simulation results confirm our analysis well and comparisons with existing approaches show that our approach can save message cost significantly (50%-70%).