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.

Digital twin (DT) technology enables smooth integrations of cyber and physical worlds in alignment with the Industry 4.0 initiative. DTs are virtual presentations of physical objects. Through synchronizations with physical objects in real-time, DTs can reflect the states of their objects with high fidelity. Orthogonal to the DT technology, mobile edge computing (MEC) is a promising computing paradigm that shifts computing power to the edge network, which is appropriate for delay-sensitive intelligent services. In this paper, we study fidelity-aware inference services in a DT-assisted MEC environment, where machine learning-based inference models must be continuously retrained using updated DT data in order to provide high-fidelity services for consumers. To this end, we first formulate two novel optimization problems: the initial DT and model placement problem with the aim of minimizing the total cost of various resources consumed, and the cumulative fidelity maximization problem to maximize the long-term cumulative fidelity of service models while minimizing the cost of resource consumption on service model fidelity enhancements over a given time horizon, through jointly scheduling mobile devices to upload their update data to synchronize with their DTs and determining whether DTs and/or models to be migrated at each time slot. We then develop an efficient algorithm for the initial DT and model placement problem, through a reduction to a series of minimum-cost maximum matching problems in auxiliary graphs. We also devise an online algorithm with a provable competitive ratio for the cumulative fidelity maximization problem, by designing an elegant service request admission strategy. Finally, we evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the proposed algorithms are promising, and outperform their baselines by no less than 28%.

Mobile Edge Computing (MEC) shifts the computing power to the edge of core networks and provides important impetus in the flourishment of delay sensitive services at the network edge. Digital Twin (DT) technique enables object behavior monitoring, analysis, and prediction through data analytics and artificial intelligence, which facilitates inference service provisioning based on machine learning models. In this paper, we deal with the Quality-of-Experience (QoE) issue of user satisfaction on inference services in DT-assisted MEC networks, through executing user tasks locally or offloaded to the MEC network. We formulate two novel optimization problems: the utility maximization problem, and the dynamic utility maximization problem, with the aim to maximize the total utility of user task executions in terms of QoEs and service delays of users with the services. We first provide an Integer Linear Programming solution for the utility maximization problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, at the expense of bounded resource violations. We then develop an efficient online heuristic for the dynamic utility maximization problem. We also devise an online algorithm with a provable competitive ratio for a special case of the dynamic utility maximization problem without the bandwidth constraint. We finally evaluate the performance of proposed algorithms through simulations. The simulation results show that the proposed algorithms are promising.

With the advance of emerging digital twin (DT) technology, the combination of DT with edge intelligence brings great potential for high-fidelity, delay-sensitive inference services at the network edge. Due to the training data drift over time, the accuracy of an inference model degrades dramatically. To maintain and/or enhance its accuracy, the service model requires to be continuously retrained using newly generated update data. However, model retraining and inference services compete with each other for the limited computing resource in a mobile edge computing network (MEC), which may decrease user satisfaction with services due to unbearable service delays caused by insufficient resource supplies. Therefore, to ensure high fidelity of service models by choosing models for retraining while maximizing user satisfaction, it becomes a great challenge to allocate the limited computing resource in an MEC to both model retraining and inference services. In this paper, we investigate fidelity-aware, delay-sensitive services in a DT-assisted MEC network over a given time horizon. We study a novel user satisfaction maximization problem with the aim to maximize the long-term user satisfaction on services. We first formulate an integer linear programming (ILP) solution to its offline version. We then devise an online algorithm for the problem with a bounded expected cumulative regret, by leveraging an efficient prediction mechanism and a multi-armed bandit (MAB) based resource allocation strategy. Finally, we evaluate the performance of the proposed algorithm via simulations. Simulation results demonstrate that the proposed algorithm is promising, outperforming the comparison benchmarks.

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

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.

Serverless computing are invented to free developers of analytic services from the management of cloud resources. Developers only need to submit their code to a serverless edge cloud (SEC) and the cloud platform matches the submitted code to itsserverless functions, enabled by the paradigm of Function as a Service (FaaS). However, serverless functions usually are short-lived with limited resources. In this paper, we aim to address the challenge of how to fully utilize the short-lived serverless functions to enable continuous analysis of the most freshly-generated big data. We first formulate an optimization problem of age-aware big data query evaluation in an SEC network so that theage of datais minimized, where the age of data is the duration between the generation time of the data and the current time. We then propose approximation algorithms for the age-aware big data query evaluation problem of a single query, by proposing a parameterized virtualization technique that smartly handles the large resource demands of big data queries in short-lived and resource-constraint serverless functions. We further consider the scenario where big data queries arrive into the system one-by-one and their resource demands are uncertain. To this end, we devise an online learning algorithm with bounded regret by leveraging a memory repacking mechanism to improve resource utilization, for the problem of online age-aware big data query evaluation. We evaluate the performance of the proposed algorithms through extensive simulations to testify their performances in large scales. We also validate the effectiveness of the proposed mechanism in a real test-bed built on Kubernetes and OpenWhisk with TPC-DS benchmarks. Experimental results show that the proposed algorithms outperform the state-of-the-arts, by reducing the age of data by$8.82\%$on average.

Edge intelligence enables mobile users to benefit from real-time inference services based on deep neural networks (DNN). Federated learning (FL) provides a solution for using DNN training while protecting privacy. FL over mobile edge computing (MEC) can aggregate models at the edge and process them in parallel, providing far more real-time results for realworld applications. However, edge nodes have limited computing capacities and bandwidth, and not all user equipments (UEs) can be selected to upload their trained local models. In addition, private information of users can still be leaked while attackers analyze the uploaded model parameters, and users' privacy requirements vary. Thus, we proposed a novel optimization framework - Federated learning with personalized differential privacy over MEC based on deep reinforcement learning. We use deep reinforcement learning (DRL) to maximize the total utility, i.e., the overall accuracy of all global FL models, by choosing UEs for uploading their updated local models due to limited bandwidth on access points (APs) and computing resource capacities on cloudlets (edge servers). Then, we inject differential private noise into local models to enhance privacy and satisfy users' personalized privacy requirements while guaranteeing model accuracy. We finally evaluate the performance of the proposed approach through experiments. Experimental results show that the proposed approach outperforms the comparison counterparts significantly, using public accessible datasets.

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.

The collaboration between end devices and edge servers has been extensively investigated to enable adaptive service provisioning, particularly in scenarios requiring trade-offs between differential model accuracies and heterogeneous resource consumption costs. In this paper, we propose freshness-aware hierarchical inference service provisioning in a Mobile Edge Computing (MEC) network, where inference models are trained and maintained in edge servers to address resource limitations on devices. Devices dynamically download updated models to maintain local inference fidelity, mitigating performance degradation caused by model staleness. We formulate a freshness and cost minimization problem that maximizes overall inference fidelity while minimizing total costs, subject to long-term average energy budgets on devices and computing capacities on cloudlets. We design an online algorithm with provable competitive ratio, by leveraging Lyapunov optimization and randomized rounding techniques. We conduct simulations to evaluate the performance of the proposed online algorithm. Simulation results demonstrate that the proposed algorithm is promising.

A multi-tenant metaverse enables multiple users in a common virtual world to interact with each other online. Information sharing will occur when interactions between a user and the environment are multicast to other users by an interactive metaverse (IM) service. However, ineffective information-sharing strategies intensify competitions among users for limited resources in networks, and fail to interpret optimization intent prompts conveyed in high-level natural languages, ultimately diminishing user immersion. In this paper, we explore reliable information sharing in a multi-tenant metaverse with time-varying resource capacities and costs, where IM services are unreliable and alter the volumes of data processed by them, while the service provider dynamically adjusts global intent to minimize multicast delays and costs. To this end, we first formulate the information sharing problem as a Markov decision process and show its NP-hardness. Then, we propose a learning-based system GTP, which combines the proximal policy optimization reinforcement learning with feature extraction networks, including graph attention network and gated recurrent unit, and a Transformer encoder for multi-feature comparison to process a sequence of incoming multicast requests without the knowledge of future arrival information. The GTP operates through three modules: a deployer that allocates primary and backup IM services across the network to minimize a weighted goal of server computation costs and communication distances between users and services, an intent extractor that dynamically infers provider intent conveyed in natural language, and a router that constructs on-demand multicast routing trees adhering to users, the provider, and network constraints. We finally conduct theoretical and empirical analysis on the proposed algorithms for the system. Experimental results show that the proposed algorithms are promising, and superior to their comparison baseline algorithms.

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.

Human digital twin bridges humans with digital avatars in the fabric metaverse, assisting users and healthcare professionals with real-time visualization, analysis, and prediction of personal data sensed by fabric sensors. The human digital twin-assisted healthcare monitoring (HHM) service refreshment refers to sending personal health data to corresponding services hosted on nearby edge servers and receiving the results to update local digital avatars continuously. However, the malicious nature and resource limitations of edge servers may lead to user privacy leaks and refreshment timeout, thereby impacting diagnostics. In this paper, we investigate a novel privacy-enhanced HHM service refreshment maximization problem in the fabric metaverse by considering privacy data encryption, model compression, and personalized user requirements. To this end, we first formulate the above issue as an Integer Linear Programming (ILP) problem, and prove its NP-hardness. Then, a resource scheduler named Wiper is designed, consisting of a shallow-deep distiller and an agile refresher library. To enable efficient inference while preserving user privacy, the former replaces violation modules in existing models with approximations and conducts shallow distillation on model layers to meet operation type and depth limits of homomorphic encryption, and then deep distillation on model parameters to decrease end-to-end refreshment delay. Finally, to satisfy user requirements on accuracy and delay during encrypted refreshments while maximizing the throughput of HHM services in offline and online situations with different problem scales, a series of HHM service refreshment algorithms are merged into the latter, including exact, performance-guaranteed approximation, and residual diffusion reinforcement learning algorithms. Theoretical analyses and experiments demonstrate that our algorithms are promising compared with baseline algorithms.

The integration of Artificial Itelligence (AI) and edge computing has sparked significant interest in edge inference services. In this paper, we consider delay-sensitive, differential accuracy inference services in a Mobile Edge Computing (MEC) network while meeting user stringent delay and accuracy requirements. We formulate two novel profit maximization problems under static and dynamic settings of service request arrivals, with the aim of maximizing the accumulative profit of admitted requests. We assign differential accuracy service requests to the corresponding resolution instances of their requested service models, assuming that each resolution instance can serve up to$L\geq 1$the same type of service requests. Since the profit maximization problem is NP-hard, we first formulate an Integer Linear Program (ILP) solution if the problem size is small or medium; otherwise, we devise a constant randomized algorithm with high probability. Then, we consider dynamic service request admissions without the knowledge of future request arrivals for a given finite time horizon, for which we develop a simple yet effective prediction mechanism to accurately predict the number of different resolution instances of each model needed, and pre-deploy the predicted number of resolution instances into cloudlets to reduce instantiating delays. We then devise an online algorithm with a provable competitive ratio for the dynamic profit maximization problem by leveraging the primal-dual dynamic updating technique. Finally, we evaluate the performance of the proposed algorithms by simulations. The simulation results demonstrate that the proposed algorithms are promising.

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.

The past decade witnessed an explosive growth on the number of IoT devices (objects/suppliers), including portable mobile devices, autonomous vehicles, sensors and intelligence appliances. To realize the digital representations of objects, Digital Twins (DTs) are key enablers to provide real-time monitoring, behavior simulations and predictive decisions for objects. On the other hand, Mobile Edge Computing (MEC) has been envisioned as a promising paradigm to provide delay-sensitive services for mobile users (consumers) at the network edge, e.g., real-time healthcare, AR/VR, online gaming, smart cities, and so on. In this paper, we study a novel DT migration problem for high quality service provisioning in an MEC network with the mobility of both suppliers and consumers for a finite time horizon, with the aim to minimize the sum of the accumulative DT synchronization cost of all suppliers and the total service cost of all consumers requesting for different DT services. To this end, we first show that the problem is NP-hard, and formulate an integer linear programming solution to the offline version of the problem. We then develop a Deep Reinforcement Learning (DRL) algorithm for the DT migration problem, by considering the system dynamics and heterogeneity of different resource consumptions, mobility traces of both suppliers and consumers, and workloads of cloudlets. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

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.

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

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.

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

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.

Federated Learning (FL) offers collaborative machine learning without data exposure, but challenges arise in the mobile edge network (MEC) environment due to limited resources and dynamic conditions. This paper presents a Digital Twin (DT)-assisted FL platform for MEC networks and introduces a novel multi-FL service framework to address resource dynamics and mobile users. We leverage DT models to optimize device scheduling and MEC resource allocation, aiming to maximize utility across FL services. Our work includes heuristic and constant approximation algorithms for offline multi-FL service scenarios and we also investigate an online setting of our solution with dynamic bandwidth and moving client conditions. To adapt to changing network conditions, we utilize historical bandwidth data in DTs and implement a deep reinforcement learning algorithm, Ra_DDPG, for automatic bandwidth allocation. Evaluation results demonstrate a significant 49.8% increase in system utility compared to a benchmark algorithm, showcasing 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%.

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

Edge-enabled Vehicular Metaverse (EVM) is a new paradise supported by various compute-intensive Virtual Vehicle Services (VVSs), where users can immerse and enjoy their spiritual world. User immersion is critical during VVS provisioning in the EVM, yet it can be weakened or curtailed by a sense of disengagement caused by unknown failures. Providing redundant backups VVSs (BVVSs) and keeping the Age of Backup Information (AoBI) could effectively resist and avoid this disengagement when failures occur. However, the trajectories of mobile vehicles are unknown and dynamic, which makes it challenging to optimally migrate VVSs and BVVSs or adjust the update frequency of backup information in real-time, so as to ensure service reliability and AoBI while minimizing the cost of accepting VVS-based metaverse services. In this paper, the above long-term issue is first decomposed into discrete single-slot sub-problems that are modeled as integer linear programming problems. Then, a comprehensive resource explorer named spotlighter is designed, where the first and second parts are a metaverse service home prediction algorithm based on deep learning and a VVS migration algorithm based on randomized rounding, respectively. By tracking the dynamical locations of service homes based on current and historical information, the former can help the latter to adaptively minimize migration costs on VVS re-instantiation and traffic transmission among services and moving vehicles. Finally, a cost-adaptive AoBI guarantee algorithm is merged in spotlighter to ensure the freshness of backup status, by trading-off synchronization cost on BVVS migration, backup update, and backup synchronization. Theoretical analyses and experiments based on real databases show that our algorithms are promising compared with baseline algorithms.

Fabric metaverse employs intelligence fibers embedded with flexible sensors to unknowingly gather and transmit massive hypermodal data around humans to a deep neural network-based metaverse inference service (DMS) for continual and real-time analysis. Each DMS has one primary branch and multiple side branches that allow early termination of service with differential accuracy and energy consumption. However, the continual provisioning of compute-intensive DMS with varying requirements for service model, accuracy, delay, and reliability poses a challenge for edge servers characterized by restricted computing resources and intermittent green energy. In this paper, we focus on a continual individualized DMS provisioning problem in the fabric metaverse consisting of a side branch insertion subproblem and a server activation and service deployment subproblem, and formulate them as Integer linear Programming and Markov Decision Process, respectively. Then, we propose a green continual inference (GCI) system, where a pruner with provable approximation ratios trims superfluous branches of every model to the given number$K$to minimize total overflow accuracy between accuracy demands and reserved branches assigned to users. Based on this exit result, each DMS is further divided into several blocks with dependencies to exploit constrained resources of computing and energy in a fine-grained manner. Finally, a learning-based scheduler is merged into GCI to maximize request throughput while minimizing the activation number of edge servers on different demand scenarios, by adaptively activating suitable servers and deploying required blocks and their corresponding backups on selected servers. Theoretical analyses, simulations, and experiments demonstrate that the GCI is promising compared with baseline algorithms.

Satellite-terrestrial networks are emerging as the next-generation networking paradigm for Beyond-5 G (B5G) and 6 G networks. Meanwhile, Mobile Edge Computing (MEC) is envisioned as the key technology to provide network services within the proximity of users, by deploying computing resource in ground locations that are close to users. With the fast deployment of Low-Earth-Oribt (LEO) satellites, a new paradigm of MEC is emerging by enabling LEO satellites serving as edge servers in lower orbits that are close to ground users. In this way, the ground users can be further served by LEO satellites in lower orbits instead of conventional high-orbit satellites. Also, since LEO satellites provide shorter paths from users to services, the performance is enhanced compared with ground MEC networks. In this paper, we aim to enable low-latency network services in a Satellite Edge Computing (SEC) network that integrates the MEC and satellite-terrestrial networks. In particular, we consider that each network service is composed of a sequence of Virtualized Network Functions (VNFs), where the traffic of user requests has to be processed by the VNFs in a service chain in the specified order before reaching its destination. To this end, we first formulate a delay-aware service chaining problem in an SEC network to minimize the average delay of implementing a user request, by jointly placing VNFs to LEO satellites in the SEC network and routing the traffic of each user request from its source to destination. We then devise an approximation algorithm with an approximation ratio for the problem in an SEC network with a single user request, by devising a novel concept ofchaining orbitand auxiliary graph construction technique. We also design an online algorithm for the online delay-aware service chaining problem in an SEC network, if user requests arrive into the system without the knowledge of their arrivals and the network delays are uncertain. We finally evaluate the performance of the proposed algorithms using real satellite network topologies, and results show that the proposed algorithms achieve 28.5% lower delay than their counterparts.

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.

Digital twin (DT) has been emerging as an enabling technology to provide seamless interactions between the virtual cyber world and the real world. The explosion of IoT devices (objects) further fuels the development of the DT technology, and paves the way to real-time monitoring, behavior simulations and decisive predictions on objects through their digital counterparts. Meanwhile, mobile edge computing (MEC) has been envisioned as a promising computing paradigm for various IoT applications with stringent delay requirements. In this paper, we study mobility-aware, delay-sensitive service provisioning in a DT-empowered MEC network with the mobility of both users and objects through DT replica placements of mobile objects. To this end, we first formulate two novel optimization problems: the DT replica placement problem and the dynamic DT replica placement problem, respectively, and show NP-hardness of the two problems. We then formulate an Integer Linear Programming (ILP) solution to the DT replica placement problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, provided that the mobility profiles of each object and each user are given. Meanwhile, We also develop an online algorithm for the dynamic DT replica placement problem, where for a given time horizon, service requests arrive one by one without the knowledge of future arrivals, each arrived request must be responded immediately by accepting or rejecting it. However, the heterogeneity and dynamics of user requests on resource demands may lead to the removals and re-instantiations of DT instances frequently. To mitigate this, we propose an efficient prediction mechanism to reserve a certain number of DTs for future by introducing the timestamp concept. We finally evaluate the performance of the proposed algorithms by simulations. Simulation results show that the proposed algorithms are promising, and outperform the performance of other comparison counterparts.

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.

Internet-of-Things (IoT) applications from many industries, such as transportation (maritime, road, rail, air) and fleet management, offshore monitoring, and farming are located in remote areas without cellular connectivity. Such IoT applications continuously generate stream data with hidden values that need to unveiled in real time. Streaming analytics is emerging as a popular type of Big Data analytics to process large volume of stream data for IoT applications in remote regions. Built upon terrestrial-satellite integrated networks, Satellite Edge Computing (SEC) equipped with computing resource in satellites has been envisioning as a key enabling technology to timely analyze stream data of IoT applications in remote regions on the Earth. Considering the dynamically-moving property of satellites in an SEC network, it is vital to optimize the responsiveness of each Big Data analytical query, such that none of such queries takes much longer time to wait for available satellites with sufficient computing resource. Furthermore, the uncertain data volumes of Big Data queries in SEC networks make the resources in satellites fragmented, particularly when the collaboration among satellites is intermittent. Therefore, directly application of existing methods may not guarantee the timelineness of streaming analytics in an SEC network. To address the afore-mentioned unique challenges of streaming analytics in SEC networks, it is urgent to design new algorithms and methods for timely Big Data processing. Specifically, we use theflow timeto capture the responsiveness of streaming analytics in satellite edge computing, which is the time between the generation of the first unit of a dataset and the finish time of the data processing. We consider the flow time minimization problem for query evaluation of Big Data analytics in an SEC network with the aim of minimizing the average flow time of Big Data analytical queries, under an assumption of uncertain volumes of datasets. To this end, we first propose an approximation algorithm with a provable approximation ratio for the offline version of the flow time minimization problem. We then devise an online learning algorithm, referred to the customized Lipschitz bandit learning algorithm, with a bounded regret for the online version of the problem. We finally evaluate the performance of the proposed algorithms in a real SEC network topology. Experiment results show that the performance of the proposed algorithm outperforms its counterparts by at least 13% in terms of flow time.

Mobile Edge Computing (MEC) has emerged as a promising platform to provide various services for mobile applications at the edge of core networks while meeting stringent service delay requirements of users. Digital twin (DT) that is a mirror of a physical object in cyberspace now becomes a key player in smart cities and the Metaverse, which can be used to simulate or predict the behaviours of the object in future. To enable such a simulation or predication to be more accurate and robust, the state of the digital twin needs to be synchronized (updated) with its object quite often. The quality of inference services in a DT-empowered MEC network usually is determined by the state freshness of service models, while a service model further is determined by the state freshness of its source DT data. It is vital to refresh the states of service models frequently in order to provide high quality inference services. In this paper, we study how to maximize the state freshness of both digital twins and a set of inference service models that are built upon digital twins in an MEC network, while the state freshness of a DT or a service model is achieved through frequent synchronizations between the DT and its physical object. Specifically, we first study a novel cost-aware average model freshness maximization problem with the aim to maximize the average freshness of the states of inference service models while minimizing the cost of achieving the model freshness, and show the NP-hardness of the problem. We then formulate an integer linear programming solution for the offline version of the problem, and devise a performance-guaranteed approximation algorithm for a special case of problem when the monitoring period consists of a single time slot only. Also, we develop an efficient online algorithm for the problem through scheduling objects to upload their update data to their digital twins in the network at each time slot efficiently. We finally evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate 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.

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.

Both Byzantine resilience and communication efficiency have attracted tremendous attention recently for their significance in edge federated learning. However, most existing algorithms may fail when dealing with real-world irregular data that behaves in a heavy-tailed manner. To address this issue, we study the stochastic convex and non-convex optimization problem for federated learning at edge and show how to handle heavy-tailed data while retaining the Byzantine resilience, communication efficiency and the optimal statistical error rates simultaneously. Specifically, we first present a Byzantine-resilient distributed gradient descent algorithm that can handle the heavy-tailed data and meanwhile converge under the standard assumptions. To reduce the communication overhead, we further propose another algorithm that incorporates gradient compression techniques to save communication costs during the learning process. Theoretical analysis shows that our algorithms achieve order-optimal statistical error rate in presence of Byzantine devices. Finally, we conduct extensive experiments on both synthetic and real-world datasets to verify the efficacy of our algorithms.

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.

Mobile Edge Computing (MEC) has emerged as a promising paradigm catering to overwhelming explosions of mobile applications, by offloading compute-intensive tasks to MEC networks for processing. The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and edge intelligence arises to provision real-time deep neural network (DNN) inference services for users. To accelerate the processing of the DNN inference of a user request in an MEC network, the DNN inference model usually can be partitioned into two connected parts: one part is processed in the local IoT device of the request, and another part is processed in a cloudlet (edge server) in the MEC network. Also, the DNN inference can be further accelerated by allocating multiple threads of the cloudlet to which the request is assigned. In this paper, we study a novel delay-aware DNN inference throughput maximization problem with the aim to maximize the number of delay-aware DNN service requests admitted, by accelerating each DNN inference through jointly exploring DNN partitioning and multi-thread execution parallelism. Specifically, we consider the problem under both offline and online request arrival settings: a set of DNN inference requests is given in advance, and a sequence of DNN inference requests arrives one by one without the knowledge of future arrivals, respectively. We first show that the defined problems are NP-hard. We then devise a novel constant approximation algorithm for the problem under the offline setting. We also propose an online algorithm with a provable competitive ratio for the problem under the online setting. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising

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.

The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and the rise of edge intelligence enables provisioning real-time deep neural network (DNN) inference services for mobile users. To perform efficient and effective DNN model training in edge computing environments while preserving training data security and privacy of IoT devices, federated learning has been envisioned as an ideal learning paradigm for this purpose. In this article, we study energy-aware DNN model training in edge computing. We first formulate a novel energy-aware, Device-to-Device (D2D) assisted federated learning problem with the aim to minimize the global loss of a training DNN model, subject to bandwidth capacity on an edge server and energy capacity on each IoT device. We then devise a near-optimal learning algorithm for the problem when the training data follows the i.i.d. data distribution. The crux of the proposed algorithm is to explore using the energy of neighboring devices of each device for its local model uploading, by reducing the problem to a series of weighted maximum matching problems in corresponding auxiliary graphs. We also consider the problem without the assumption of the i.i.d. data distribution, for which we propose an efficient heuristic algorithm. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the proposed algorithms are promising.

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.

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

This paper studies the privacy-preserving adaptive ranking problem for multi-armed-bandit crowdsourcing, where according to the crowdsourced data, the arms are required to be ranked with a tunable granularity by the untrustworthy third-party platform. Any online worker can provide its data by arm pulls but requires its privacy preserved, which will increase the ranking cost greatly. To improve the quality of the ranking service, we propose a Privacy- Preserving Adaptive Ranking algorithm called PPAR, which can solve the problem with a high probability while differential privacy can be ensured. The total cost of the proposed algorithm is ${\mathcal{O}}(K\ln K)$, which is near optimal compared with the trivial lower bound Ω(K), where K is the number of arms. Our proposed algorithm can also be used to solve the well-studied fully ranking problem and the best arm identification problem, by proper setting the granularity parameter. For the fully ranking problem, PPAR attains the same order of computation complexity with the best-known results without privacy preservation. The efficacy of our algorithm is also verified by extensive experiments on public datasets.

The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and edge intelligence arises to provision real-time deep neural network (DNN) inference services for mobile users. To perform efficient and effective DNN model training in edge environments while preserving training data security and privacy of IoT devices, federated learning has been envisioned as an ideal learning paradigm for this purpose. In this paper we study energy-aware DNN model training in an edge environment. We first formulate a novel energy-aware, device-to-device (D2D) assisted federated learning problem with the aim to minimize the global loss of a training DNN model, subject to bandwidth capacity on an edge server and the energy capacity on each IoT device. We then devise an efficient heuristic algorithm for the problem. The crux of the proposed algorithm is to explore the energy usage of neighboring devices of each device for its local model uploading, by reducing the problem to a series of maximum weight matching problems in corresponding auxiliary graphs. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results show that the proposed algorithm is promising.

Machine learning (ML) is powering a rapidly-increasing number of web applications. As a crucial part of 5G, edge computing facilitates edge artificial intelligence (AI) by ML model training and inference at the network edge on edge servers. Compared with centralized cloud AI, edge AI enables low-latency ML inference which is critical to many delay-sensitive web applications, e.g., web AR/VR, web gaming and Web-of-Things applications. Existing studies of edge AI focused on resource and performance optimization in training and inference, leveraging edge computing merely as a tool to accelerate training and inference processes. However, the unique ability of edge computing to process data with context awareness, a powerful feature for building the web-of-things for smart cities, has not been properly explored. In this paper, we propose a novel framework named Pyramid that unleashes the potential of edge AI by facilitating homogeneous and heterogeneous hierarchical ML inferences. We motivate and present Pyramid with traffic prediction as an illustrative example, and evaluate it through extensive experiments conducted on two real-world datasets. The results demonstrate the superior performance of Pyramid neural networks in hierarchical traffic prediction and weather analysis.

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.

Data sensing and gathering is an essential task for various information-driven services in smart cities. On the one hand, Internet of Things (IoT) sensors can be deployed at certain fixed locations to capture data reliably but suffer from limited sensing coverage. On the other hand, data can also be gathered dynamically through crowdsensing contributed by voluntary users but suffer from its unreliability and the lack of incentives for users’ contributions. In this article, we explore an integrated paradigm called “ hybrid sensing ” that harnesses both IoT-sensing and crowdsensing in a complementary manner. In hybrid sensing, users are incentivized to provide sensing data not covered by IoT sensors and provide crowdsourced feedback to assist in calibrating IoT-sensing. Their contributions will be rewarded with credits that can be redeemed to retrieve synthesized information from the hybrid system. In this article, we develop a hybrid sensing system that supports explicit user privacy—IoT sensors are obscured physically to prevent capturing private user data, and users interact with a crowdsensing server via a privacy-preserving protocol to preserve their anonymity. A key application of our system is smart parking, by which users can inquire and find the available parking spaces in outdoor parking lots. We implemented our hybrid sensing system for smart parking and conducted extensive empirical evaluations. Finally, our hybrid sensing system can be potentially applied to other information-driven services in smart cities.

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.

Mobile edge computing (MEC) has emerged as a promising technology to push the cloud frontier to the network edge, provisioning network services in proximity of mobile users. Serving users at edge clouds can reduce service latency, lower operational cost, and improve network resource availability. Along with the MEC technology, network function virtualization (NFV) is another promising technique that implements various network service functions as pieces of software in cloudlets (servers or clusters of servers). Providing virtualized network service for mobile users can improve user service experience, simplify network service deployment, and ease network resource management. However, mobile users move in networks arbitrarily, and different users usually request different services with different resource demands and delay requirements. It thus poses a great challenge to providing reliable and seamless virtualized network services for mobile users in an MEC network while meeting their individual delay requirements, subject to resource capacities on the network. In this paper, we focus on the provisioning of virtualized network function services for mobile users in MEC that takes into account user mobility and service delay requirements. We first formulate two novel optimization problems of user service request admissions with the aims to maximize the accumulative network utility and accumulative network throughput for a given time horizon, respectively. We then devise a constant approximation algorithm for the utility maximization problem. We also develop an online algorithm for the accumulative throughput maximization problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.

With the integration of Mobile Edge Computing (MEC) and Network Function Virtualization (NFV), service providers are able to provide low-latency services to mobile users for profit. In this paper, we study the online service placement and request assignment problem in an MEC network, where service requests arrive one by one without the knowledge of future arrivals, and each arrived request demands a specific service with a tolerable service delay requirement with the aim to maximize the profit of the service provider, through admitting as many service requests as possible for a given monitoring period. This optimization objective is achieved by assigning service requests to appropriate cloudlets in the MEC network, pre-installing service instances into cloudlets to shorten service delays, and accommodating new services by revoking some idle service instances from cloudlets due to limited computing resources in MEC networks. In this paper, we first show that the problem is NP-hard. We then devise an efficient deep reinforcement learning algorithm for the online service placement and request assignment problem that consists of a deep reinforcement learning-based prediction mechanism for dynamic service placement, followed by a dynamic request assignment procedure to assign requests to cloudlets. We finally evaluate the performance of the proposed algorithms by conducting experiments through simulations. Simulation results demonstrate that the proposed algorithm is promising, improving performance by 46.8% compared with that of the comparison algorithms.

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.

We are embracing an era of Internet of Things (IoT). The latency brought by unstable wireless networks caused by limited resources of IoT devices seriously impacts the quality of services of users, particularly the service delay they experienced. Mobile Edge Computing (MEC) technology provides promising solutions to delay-sensitive IoT applications, where cloudlets (edge servers) are co-located with wireless access points in the proximity of IoT devices. The service response latency for IoT applications can be significantly shortened due to that their data processing can be performed in a local MEC network. Meanwhile, most IoT applications usually impose Service Function Chain (SFC) enforcement on their data transmission, where each data packet from its source gateway of an IoT device to the destination (a cloudlet) of the IoT application must pass through each Virtual Network Function (VNF) in the SFC in an MEC network. However, little attention has been paid on such a service provisioning of multi-source IoT applications in an MEC network with SFC enforcement. In this article, we study service provisioning in an MEC network for multi-source IoT applications with SFC requirements and aiming at minimizing the cost of such service provisioning, where each IoT application has multiple data streams from different sources to be uploaded to a location (cloudlet) in the MEC network for aggregation, processing, and storage purposes. To this end, we first formulate two novel optimization problems: the cost minimization problem of service provisioning for a single multi-source IoT application, and the service provisioning problem for a set of multi-source IoT applications, respectively, and show that both problems are NP-hard. Second, we propose a service provisioning framework in the MEC network for multi-source IoT applications that consists of uploading stream data from multiple sources of the IoT application to the MEC network, data stream aggregation and routing through the VNF instance placement and sharing, and workload balancing among cloudlets. Third, we devise an efficient algorithm for the cost minimization problem built upon the proposed service provisioning framework, and further extend the solution for the service provisioning problem of a set of multi-source IoT applications. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

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.

More and more artificial intelligence (AI) applications, such as virtual reality (VR) and video analytics, are rapidly progressing towards enterprise and end-users with the promise of bringing immersive experience. Driven by the desire to improve users’ experience and promote business scenarios, such AI applications have unprecedented requirements for ultra-low latency as well as abundant computing resource in networks. Data centers in the core network can meet these demands by deploying various AI services and providing abundant resources. However, data transmission delay from data centers to end-users is too time-consuming because of traffic congestion in the core network, which compromises the performance of the AI applications. 5G and edge computing are emerging technologies to guarantee the timeliness for the delay-sensitive applications. The delay experienced by AI users can be significantly reduced, by ‘caching’ various services that are initially deployed at data centers to cloudlets in edge networks. Although ubiquitous edge service caching is always preferable for improving user experiences, it is impractical to cache all services from data centers to edge cloudlets, due to often limited caching budget of service providers and resource capacity constraints of cloudlets. Therefore, a service provider has to cautiously decide how many instances of a service can be cached, and where to cache the service instances. In this article, we investigate a fundamental problem ofservice cachingfrom remote data centers to edge cloudlets in a multi-tiered edge cloud network. We first develop two approximation algorithms with approximation ratios to solve the problem for users demanding a single type of service. We then devise an efficient heuristic to solve the problem that users require different types of services. We finally conduct extensive experiments on a real test-bed to evaluate the performance of the proposed algorithms, and experimental results demonstrate that our algorithms can outperform some existing algorithms significantly.

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.

With the fast development of next-generation networking techniques, a Network Function Virtualization (NFV) market is emerging as a major market that allows network service providers to trade various network services among consumers. Therefore, 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 they have incentives to participate in activities of the market. In this paper, we first formulate the social welfare maximization problem, with an aim to maximize the total revenue of all players in the NFV market. For the social welfare maximization problem, we design an efficient incentive-compatible mechanism and analyze the existence of a Nash equilibrium of the mechanism. We also consider an online social welfare maximization problem without the knowledge of future request arrivals. We devise an online learning algorithm based on Multi-Armed Bandits (MAB) to allow both customers and network service providers to make decisions with uncertainty of customers' strategy. We evaluate the performance of the proposed mechanisms by both simulations and test-bed implementations, and the results show that the proposed mechanisms obtain at most 23% higher social welfare than existing studies.

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.

Mobile Edge Computing (MEC) has emerged as a promising paradigm catering to overwhelming explosions of mobile applications, by offloading the compute-intensive tasks to an MEC network for processing. The surging of deep learning brings new vigor and vitality to shape the prospect of intelligent Internet of Things (IoT), and edge intelligence arises to provision real-time deep neural network (DNN) inference services for users. To accelerate the processing of the DNN inference of a request in an MEC network, the DNN inference model usually can be partitioned into two connected parts: one part is processed on the local IoT device of the request; and another part is processed on a cloudlet (server) in the MEC network. Also, the DNN inference can be further accelerated by allocating multiple threads of the cloudlet in which the request is assigned.In this paper, we study a novel delay-aware DNN inference throughput maximization problem with the aim to maximize the number of delay-aware DNN service requests admitted, by accelerating each DNN inference through jointly exploring DNN model partitioning and multi-thread parallelism of DNN inference. To this end, we first show that the problem is NP-hard. We then devise a constant approximation algorithm for it. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising.

With the integration of Mobile Edge Computing (MEC) and Network Function Virtualization (NFV), service providers are able to provide low-latency services to mobile users for profit. In this paper, we study the problem of service instance placement and request assignment in an MEC network for a given monitoring period, where service requests arrive into the system without the knowledge of future arrivals. Each incoming request requires a specific service with a maximum tolerable service delay requirement. The problem is to maximize the profit of the service provider by admitting service requests for the monitoring period, which can be achieved by preinstalling service instances into cloudlets to shorten service delays, and accommodating new services by removing some idle service instances from cloudlets due to limited computing resources. We then devise an efficient deep-reinforcement-learning-based algorithm for this dynamic online service instance placement problem. We finally evaluate the performance of the proposed algorithm by conducting experiments through simulations. Simulation results demonstrate that the proposed algorithm is promising.

Data collection in Wireless Sensor Networks (WSNs) has been a hot research topic owing to the accelerated development in the Internet of Things (IoT). With high agility, mobility and flexibility, the Unmanned Aerial Vehicle (UAV) is widely considered as a promising technology for data collection in WSNs. Under the one-to-many data collection scheme, where a UAV is able to collect data from multiple sensors simultaneously within its reception range, the identification of hovering locations of the UAV impacts the efficiency of data collection significantly. Most existing studies either neglect this critical issue or discretize the UAV serving area into small regions with a given size, which results in the inevitable utility loss of data collection. In this paper, we jointly consider the hovering location positioning of the UAV and the utility maximization of data collection. Specifically, we first formulate a novel data collection utility maximization problem (UMP) and show that it is an NP-hard problem. We then devise an efficient algorithm for precisely positioning (potential) UAV hovering locations, which improves the data collection utility significantly. We also propose an approximation algorithm for UMP with approximation ratio (1 - 1/e), where e is the base of the natural logarithm. We finally evaluate the performance of the proposed algorithms through simulation experiments, and demonstrate that the proposed algorithms significantly outperform four heuristics.

The accelerated development of the Internet of Things (IoT) incurs a great demand for data acquired from Wireless Sensor Networks (WSNs), leading to considerable attention on data collection of WSNs in recent years. With the high agility, mobility and flexibility, the Unmanned Aerial Vehicle (UAV) is widely considered as a promising technology for data collection in WSNs. Along with the Orthogonal Frequency Division Multiple Access (OFDMA) technique, the UAV is capable to collect data from multiple sensors simultaneously within its communication range (referred to as the one-to-many data collection scheme), which improves data collection efficiency significantly. In this paper, we focus on the improvement of the data collection efficiency in WSNs under the one-to-many data collection scheme via the trajectory finding of a UAV for data collection. To this end, we first formulate a novel data collection maximization problem in WSNs via deploying an energy-constrained UAV and show the NP-hardness of the problem. We then devise an efficient algorithm for the problem by investigating the impact of UAV hovering locations on the data collection. We finally evaluate the performance of the devised algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is promising, and outperforms the other heuristics significantly.

Mobile Edge Computing (MEC) has emerged as a promising networking paradigm that provides delay-sensitive service for mobile users at the edge of core networks, where mobile users can offload their computing-intensive tasks to MEC networks for processing on no time. Furthermore, with the advance of communication and fabrication technologies, mobile devices now have adequate computing and storage processing capabilities. The device-to-device (D2D) offloading as a new offloading technique enables mobile users to offload their tasks to other mobile devices (referred as helper mobile devices) for processing, thereby alleviating the processing burden on servers in MEC. However, fully utilizing the D2D technique in an MEC network for task offloading service is challenging. Particularly, the mobility of both mobile users and their helper mobile devices makes efficient offloading service placement become difficult. In this paper, we study a novel Mobility-aware Dynamic Offloading Service Placement (MDOSP) problem in a D2D-assisted MEC environment with the aim to minimize the total cost of offloading task services that consists of the computing cost, communication delay cost and migration cost, without the knowledge of future mobility information of mobile users and helper mobile devices. We first formulate an Integer Nonlinear Programming (INP) for the offline setting of the problem. We then prove the NP-hardness and develop an online algorithm with a provable competitive ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline 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.

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.

Network Function Virtualization (NFV) has attracted significant attention from both industry and academia as an important paradigm change in network service provisioning. Most existing studies on admissions of NFV-enabled requests focused on deploying dedicated Virtualized Network Function (VNF) instances to serve each individual request without exploring the sharing of VNF instances among multiple user requests. However, with ever-growing demands of user services, exclusive usages of VNF instances in most networks drastically degrade the network performance and largely under-utilize the VNF instance resources. In this paper, we jointly explore two different VNF instance scaling techniques, horizontal scaling and vertical scaling techniques, to improve the network throughput while minimizing the operational cost of the network, where horizontal scaling that migrates some existing VNF instances from their current locations to new locations to allow the VNF instances to be shared by multiple requests to reduce the resource consumption and operational cost of the network, and vertical scaling that instantiates new VNF instances to meet the demands of new request admissions if existing VNF instances sharing becomes more expensive or the end-to-end delay requirements of currently executing requests will be violated. We first propose a unified framework of maximizing the network throughput, by admitting as many as NFV-enabled requests while meeting the end-to-end delay requirements of the admitted requests. We then provide an Integer Linear Programming (ILP) solution for the problem when the problem size is small. Otherwise, we devise an efficient algorithm through a non-trivial reduction that reduces the problem to the minimum-weight feedback arc set problem and the generalized assignment problem (GAP). We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm outperforms a baseline algorithm and achieves a performance on a par with its optimal ILP solution.

Conventional Internet of Things (IoT) applications involve data capture from various sensors in environments, and the captured data then is processed in remote clouds. However, some critical IoT applications (e.g., autonomous vehicles) require a much lower response latency and more secure guarantees than those offered by remote clouds today. Mobile edge clouds (MEC) supported by the network function virtualization (NFV) technique have been envisioned as an ideal platform for supporting such IoT applications. Specifically, MECs enable to handle IoT applications in edge networks to shorten network latency, and NFV enables agile and low-cost network functions to run in low-cost commodity servers as virtual machines (VMs). One fundamental problem for the provisioning of IoT applications in an NFV-enabled MEC is where to place virtualized network functions (VNFs) for IoT applications in the MEC, such that the operational cost of provisioning IoT applications is minimized. In this paper, we first address this fundamental problem, by considering a special case of the IoT application placement problem, where the IoT application and VNFs of each service request are consolidated into a single location (gateway or cloudlet), for which we propose an exact solution and an approximation algorithm with a provable approximation ratio. We then develop a heuristic algorithm that controls the resource violation ratios of edge clouds in the network. For the IoT application placement problem for IoT applications where their VNFs can be placed to multiple locations, we propose an efficient heuristic that jointly places the IoT application and its VNFs. We finally study the performance of the proposed algorithms by simulations and implementations in a real test-bed, Experimental results show that the performance of the proposed algorithms outperform their counterparts by at least 10 percent.

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.

With the advent of Network Function Virtualization (NFV) technology, more and more mobile users make use of virtual network services in Mobile Edge Computing (MEC) networks. Each service request not only requests for a service but also a Service Function Chain (SFC) associated with the request. How to effectively allocate resources in MEC to meet the resource demands of user service requests to maximize the expected profit of the network service provider poses a great challenge. Most existing studies considered resource allocation and scheduling in MEC for user request admissions, under the assumption that the amounts of different resources demanded by each request are givena priorand do not change during the execution of the request. In practice, the resource demands during the implementation of a request are dynamically evolving. This uncertainty of resource demands at different execution stages of the request does impact the service quality and the profit of network service providers. Thus, providing robust services to users against their resource demand uncertainties is a critical issue. In this paper, we study the robust service function chain placement (RSFCP) problem under the uncertainty assumption of both computing resource and data rates demanded by request executions, through the placement of SFCs. We first formulate the RSFCP problem as a Quadratic Integer Programming (QIP) and show that the problem is NP-hard. We then develop a near-optimal approximation algorithm for it, by adopting the Markov approximation technique. We also analyze the proposed approximation algorithm with the optimality gap, and the bounds on the convergence time and perturbation caused by resource demand uncertainties. We finally evaluate the performance of the proposed algorithm through analytical and empirical analyses. Experimental results demonstrate that the proposed algorithm is promising, compared with existing baseline algorithms.

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.

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.

The rise of big data brings extraordinary benefits and opportunities to businesses and governments. Enterprise users can analyze their consumers' data and infer the business value obtained, such as purchasing goods correlations, customer preferences, and hidden patterns. Meanwhile, with the emerge of big data processing frameworks, such as Hadoop and Tensor-flow, more and more mobile users are embracing big data analytics by issuing queries to analyze their data. In this paper, we investigate the problem of Quality-of-Service (QoS) aware query evaluation for big data analytics in a mobile edge cloud to maximize the system throughput while minimizing the query evaluation time of each admitted query, by exploring the materialization of intermediate query results. We consider dynamic big-data query evaluations where user queries arrive one by one without the knowledge of future arrivals, and the system needs to respond to each query by accepting or rejecting the query immediately. We propose an online algorithm for query admissions within a finite time horizon, the proposed algorithm can intelligently determine whether some immediate results during a query evaluation need to be materialized for later use of other queries, by making use of the Reinforcement Learning (RL) method with predictions. We finally investigate the performance of the proposed algorithm by simulations, and results show that the performance of the proposed algorithm is promising, by achieving a higher system throughput while reducing the average evaluation cost per query by from 20% to 52% compared to the comparison benchmarks.

Data collection in wireless sensor networks (WSNs) as a fundamental problem has been extensively studied in the past. With the fast deployment of 5G networks, the use of unmanned aerial vehicles (UAVs) for data collection in WSNs has become a promising technology due to its high flexibility, low cost and ease of deployment. Most existing studies of using UAVs for data collection focused on the one-to-one data collection scheme, where a UAV can collect the sensing data from one sensor at each time. There is another one-to-many data collection scheme where the UAV can collect sensing data from multiple sensors simultaneously through the Orthogonal Frequency Division Multiple Access technique. In this paper, we study data collection in WSNs by adopting the one-to-many data collection scheme with the aim to maximize the volume of data collected, subject to the energy capacity on the UAV. Specifically, we first formulate a novel multisensor data collection optimization problem and show that the problem is NP-hard. We then devise a (1 - 1/e)-approximation algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. Simulation results demonstrate that the proposed algorithm is promising, and outperforms other heuristics significantly.

Mobile Edge Computing (MEC) has been envisioning as a promising technology to address limited computing and storage resources in mobile devices. The virtual services provided by the MEC platform are implemented as instances of Virtual Network Functions (VNFs). However, these VNF instances as pieces of software that run in virtual machines (VMs) are not always reliable. To provide reliable services for their users while meeting user service reliability requirements, the service providers of MEC usually adopt the replica policy that deploy a certain number of service replicas for each VNF instance. In this paper, we study reliable service provisioning in an MEC network through redundant placement of instances of VNFs. We assume that each service request consists of a Service Function Chain (SFC) requirement and a service reliability requirement. We formulate a novel reliability-aware service function chain provisioning problem with the aim to maximize the number of requests admitted, while meeting the specified reliability requirement of each admitted request. We first show that the problem is NP-hard, and formulate an ILP solution for the problem when the problem size is small. We then develop a randomized algorithm with a provable approximation ratio and high probability for the problem when the problem size is large, and the achieved approximation ratio is at the expense of moderate computing capacity and reliability constraint violations. We also devise an efficient heuristic for the problem without any resource and requirement constraint violations. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising.

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.

Mobile edge computing (MEC) is envisioned as an enabling technology for extreme low-latency services in the next generation 5G access networks. In a 5G-enabled MEC, computing resources are attached to base stations. In this way, network service providers can cache their services from remote data centers to base stations in the MEC to serve user tasks in their close proximity, thereby reducing the service latency. However, mobile users usually have various dynamic hidden features, such as their locations, user group tags, and mobility patterns. Such hidden features normally lead to uncertainties of the 5G-enabled MEC, such as user demand and processing delay. This poses significant challenges for the service caching and task offloading in a 5G-enabled MEC. In this paper, we investigate the problem of dynamic service caching and task offloading in a 5G-enabled MEC with user demand and processing delay uncertainties. We first propose an online learning algorithm for the problem with given user demands by utilizing the technique of Multi-Armed Bandits (MAB), and theoretically analyze the regret bound of the algorithm. We also propose a novel architecture of Generative Adversarial Networks (GAN) to accurately predict the user demands based on small samples of hidden features of mobile users. Based on the proposed GAN model, we then devise an efficient heuristic for the problem with the uncertainties of both user demand and processing delay. We finally evaluate the performance of the proposed algorithms by simulations based on a realistic dataset of user data. Experiment results show that the performance of the proposed algorithms outperform existing algorithms by around 15%.

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.

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.

With the development of 5G technology, mobile edge computing is emerging as an enabling technique to promote Quality of Service (QoS) of network services. In particular, the response latency of network services can be significantly reduced by deploying cloudlets at 5G base stations in mobile edge clouds. Network service providers that usually deploy their services in remote clouds now shift their services from the remote clouds to the network edge in the proximity of users. However, the permanent placement of their services into edge clouds may not be economic, since computing and bandwidth resources in edge clouds are limited and relatively expensive. A smart way is to cache the services that are frequently requested by mobile users in edge clouds. In this paper, we study the problem of service caching in mobile edge network under a mobile service market with multiple network service providers completing for both computation and bandwidth resources of the edge cloud. We propose an Integer Linear Program (ILP) and a randomized rounding algorithm, for the problem without resource sharing among the network service providers. We also devise a distributed and stable game-theoretical mechanism for the problem with resource sharing among the network service providers, with the objective to minimize the social cost of all network service providers, by introducing a novel cost sharing model and a coalition formation game. We analyze the performance of the mechanism by showing a good guaranteed gap between the solution obtained and the optimal one, i.e., Strong Price of Anarchy (SPoA). We finally evaluate the performance of our algorithms by extensive simulations, and the obtained results show that the social cost of all players can be reduced significantly via allowing cooperation among network service providers in service caching.

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.

We are embracing an era of Internet of Things (IoTs). However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices seriously impacts the quality of service of user experienced. To address these shortcomings, the Mobile Edge Computing (MEC) platform provides a promising solution for the service provisioning of IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices, and the service response latency can be significantly reduced. Meanwhile, each IoT application usually imposes a service function chain enforcement for its data transmission, which consists of different service functions in a specified order, and each data packet transfer in the network from the gateways of IoT devices to the destination must pass through each of the service functions in order.In this paper, we study IoT-driven service provisioning in an MEC network for various IoT applications with service function chain requirements, where an IoT application consists of multiple data streams from different IoT sources that will be uploaded to the MEC network for aggregation, processing, and storage. We first formulate a novel cost minimization problem for IoT-driven service provisioning in MEC networks. We then show that the problem is NP-hard, and propose an IoT-driven service provisioning framework for IoT applications, which consists of streaming data uploading from multiple IoT sources to the MEC network, data stream aggregation and routing, and Virtual Network Function (VNF) instance placement and sharing in cloudlets in the MEC network. In addition, we devise an efficient algorithm for the problem, built upon the proposed service framework. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising, compared with the lower bound on the optimal solution of the problem and another comparison heuristic.

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.

A modern Network Function Virtualization (NFV) service is usually expressed in a service chain that contains a list of ordered network functions, each can run in one or multiple virtual machines. Although lots of efforts have been devoted to service chain deployment, the researchers normally consider a simple model of network functions where different service chains have their own network functions no matter whether some of the network function appliances are interdependent. In this paper, we study the service chain deployment by exploiting two types of correlations between network functions: the Coordination Effect due to information exchanges among multiple VMs running the same network function, and the Traffic-Change Effect where the volume of outgoing traffic is not necessarily equal to the volume of its incoming traffic at each network function because of packet manipulations such as compression and encryption. These two effects have not been studied simultaneously in the context of service chaining. With theobjective to maximize the profit measured by the admitted traffic minus the implementation cost, we first formulate a joint service-function deployment and traffic scheduling (SUPER) problem that is proved to be NP-hard. We then devise an approximation algorithm based on the Markov approximation technique and analyze its theoretical bound on the convergence time. Simulation results show that the proposed algorithm outperforms two existing benchmark algorithms significantly.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for business, entertainments and social interactions. This poses a great challenge of building a seamless application experience across different computing platforms. A key issue is the resource limitations of mobile devices due to their portable size, however this can be overcome by offloading computation-intensive tasks from the mobile devices to clusters of nearby computers called cloudlets through wireless access points. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-boxes must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload among cloudlets in an WMAN to optimize mobile application performance. We first introduce a novel system model to capture the response time delays of offloaded tasks and formulate an optimization problem with the aim to minimize the maximum response time of all offloaded tasks. We then propose two algorithms for the problem: one is a fast heuristic, and another is a distributed genetic algorithm that is capable of delivering a more accurate solution compared with the first algorithm, but at the expense of a much longer running time. We finally evaluate the performance of the proposed algorithms in realistic simulation environments. The experimental results demonstrate the significant potential of the proposed algorithms in reducing the user task response time, maximizing user experience.

Satellite-based communication technology has gained much attention in the past few years, where satellites play mainly the supplementary roles as relay devices to terrestrial communication networks. Unlike previous work, we treat the low-earth-orbit (LEO) satellites as secure data storage mediums. We focus on data acquisition from a LEO satellite based data storage system (also referred to as the LEO based datacenters), which has been considered as a promising and secure paradigm on data storage. Under the LEO based datacenter architecture, one fundamental challenge is to deal with energy-efficient downloading from space to ground while maintaining the system stability. In this paper, we aim to maximize the amount of data admitted while minimizing the energy consumption, when downloading files from LEO based datacenters to meet user demands. To this end, we first formulate a novel optimization problem and develop an online scheduling framework. We then devise a novel coflow-like “Join the first K-shortest Queues (JKQ)” based job-dispatch strategy, which can significantly lower backlogs of queues residing in LEO satellites, thereby improving the system stability. We also analyze the optimality of the proposed approach and system stability. We finally evaluate the performance of the proposed algorithm through conducting emulator based simulations, based on real-world LEO constellation and user demand traces. The simulation results show that the proposed algorithm can dramatically lower the queue backlogs and achieve high energy efficiency.

Along with Network Function Virtualization (NFV), Mobile Edge Computing (MEC) is becoming a new computing paradigm that enables accommodating innovative applications and services with stringent response delay and resource requirements, including autonomous vehicles and augmented reality. Provisioning reliable network services for users is the top priority of most network service providers, as unreliable services or severe service failures can result in tremendous losses of users, particularly for their mission-critical applications. In this paper, we study reliability-aware VNF instances provisioning in an MEC, where different users request different network services with different reliability requirements through paying their requested services with the aim to maximize the network throughput. To this end, we first formulate a novel reliability-aware VNF instance placement problem by provisioning primary and secondary VNF instances at different cloudlets in MEC for each user while meeting the specified reliability requirement of the user request. We then show that the problem is NP-hard and formulate an Integer Linear Programming (ILP) solution. Due to the NP-hardness of the problem, we instead devise an approximation algorithm with a logarithmic approximation ratio for the problem. Moreover, we also consider two special cases of the problem. For one special case where each request only requests one primary and one secondary VNF instances, the problem is still NP-hard, and we devise a constant approximation algorithm for it. For another special case where different VNFs have the same amounts of computing resource demands, we show that it is polynomial-time solvable by developing a dynamic programming solution for it. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, and the empirical results of the algorithms outperform their analytical counterparts as theoretical estimations usually are very conservative.

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.

Mobile edge computing and network function virtualization (NFV) paradigms enable new flexibility and possibilities of the deployment of extreme low-latency services for Internet-of-Things (IoT) applications within the proximity of their users. However, this poses great challenges to find optimal placements of virtualized network functions (VNFs) for data processing requests of IoT applications in a multi-tier cloud network, which consists of many small- or medium-scale servers, clusters, or cloudlets deployed within the proximity of IoT nodes and a few large-scale remote data centers with abundant computing and storage resources. In particular, it is challenging to jointly consider VNF instance placement and routing traffic path planning for user requests, as they are not only delay sensitive but also resource hungry. In this article, we consider admissions of NFV-enabled requests of IoT applications in a multi-tier cloud network, where users request network services by issuing service requests with service chain requirements, and the service chain enforces the data traffic of the request to pass through the VNFs in the chain one by one until it reaches its destination. To this end, we first formulate the throughput maximization problem with the aim to maximize the system throughput. We then propose an integer linear program solution if the problem size is small; otherwise, we devise an efficient heuristic that jointly takes into account VNF placements to both cloudlets and data centers and routing path finding for each request. For a special case of the problem with a set of service chains, we propose an approximation algorithm with a provable approximation ratio. Next, we also devise efficient learning-based heuristics for VNF provisioning for IoT applications by incorporating the mobility and energy conservation features of IoT devices. We finally evaluate the performance of the proposed algorithms by simulations. The simulation results show that the performance of the proposed algorithms is promising.

The Mobile Edge-Cloud (MEC) network has emerged as a promising networking paradigm to address the conflict between increasing computing-intensive applications and resource-constrained mobile Internet-of-Thing (IoT) devices with portable size and storage. In MEC environments, Virtualized Network Functions (VNFs) are deployed for provisioning network services to users to reduce the service cost on top of dedicated hardware infrastructures. However, VNFs may suffer from failures and malfunctions while network service providers have to guarantee continuously reliable services to their consumers to meet the ever-growing service demands of users, thereby securing their revenues for the service. In this article, we focus on reliable VNF service provisioning in MECs, by placing primary and backup VNF instances to cloudlets in an MEC network to meet the service reliability requirements of users. We first formulate a novel VNF service reliability problem with the aim to maximize the revenue collected by admitting as many as user requests while meeting their different reliability requirements, assuming that requests arrive into the system one by one without the knowledge of future arrivals, and the admission or rejection decision must be made immediately. We then develop two efficient online algorithms for the problem under two different backup schemes: the on-site (local) and off-site (remote) schemes, by adopting the primal-dual updating technique. Both algorithms achieve provable competitive ratios with bounded moderate resource capacity violations. We finally evaluate the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline algorithms.

Mobile Edge Computing (MEC) reforms the cloud paradigm by bringing unprecedented computing capacity to the vicinity of end users at the mobile network edge. This provides end users with swift and powerful computing and storage capacities, energy efficiency, and mobility- and context-awareness support. Furthermore, Network Function Virtualization (NFV) is another promising technique that implements various network functions for many applications as pieces of software in servers or cloudlets in MEC networks. The provisioning of virtualized network services in MEC can improve user service experiences, simplify network service deployment, and ease network resource management. However, user requests arrive dynamically and different users demand different amounts of resources, while the resources in MEC are dynamically occupied or released by different services. It thus poses a significant challenge to optimize the performance of MEC through efficient computing and communication resource allocations to meet ever-growing resource demands of users. In this paper, we study NFV-enabled multicasting that is a fundamental routing problem in an MEC network, subject to resource capacities on both its cloudlets and links. Specifically, we first devise an approximation algorithm for the cost minimization problem of admitting a single NFV-enabled multicast request. We then develop an efficient algorithm for the throughput maximization problem for the admissions of a given set of NFV-enabled multicast requests. We third devise an online algorithm with a provable competitive ratio for the online throughput maximization problem when NFV-enabled multicast requests arrive one by one without the knowledge of future request arrivals. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

Stringent delay requirements of many mobile applications have led to the development of mobile edge clouds, to offer low latency network services at the network edges. Most conventional network services are implemented via hardware-based network functions, including firewalls and load balancers, to guarantee service security and performance. However, implementing hardware-based network functions usually incurs both a high capital expenditure (CAPEX) and operating expenditure (OPEX). Network Function Virtualization (NFV) exhibits a potential to reduce CAPEX and OPEX significantly, by deploying software-based network functions in virtual machines (VMs) on edge-clouds. We consider a fundamental problem of NFV-enabled multicasting in a mobile edge cloud, where each multicast request has both service function chain and end-to-end delay requirements. Specifically, each multicast request requires chaining of a sequence of network functions (referred to as a service function chain) from a source to a set of destinations within specified end-to-end delay requirements. We devise an approximation algorithm with a provable approximation ratio for a single multicast request admission if its delay requirement is negligible; otherwise, we propose an efficient heuristic. Furthermore, we also consider admissions of a given set of the delay-aware NFV-enabled multicast requests, for which we devise an efficient heuristic such that the system throughput is maximized, while the implementation cost of admitted requests is minimized. We finally evaluate the performance of the proposed algorithms in a real test-bed, and experimental results show that our algorithms outperform other similar approaches reported in literature.

Mobile Edge Computing (MEC) has emerged as a promising paradigm to address the conflict between increasing computing-intensive applications and resource-constrained mobile Internet-of-Thing (IoT) devices with portable size and storage. In MEC environments, Virtualized Network Functions (VNFs) are deployed for provisioning network services to users to reduce the service cost on top of dedicated hardware infrastructures. However, VNFs may suffer from failures and malfunctions while network service providers have to guarantee continuously reliable services to their users to meet ever-growing service demands of the users. In this paper, we focus on reliable VNF service provisioning in MECs, by provisioning primary and backup VNF instances in order to meet the reliability requirements of mobile users. We first formulate a novel VNF service reliability problem with the aim to maximize the revenue collected by admitting as many as user requests while meeting individual user service reliability requirements. We then develop two efficient on-line scheduling algorithms for the problem under two different backup schemes: on-site (local) and off-site (remote) schemes, by adopting the primal and dual updating technique. Particularly for the on-site scheme, the proposed on-line algorithm achieves a provable competitive ratio with bounded moderate resource violations. We finally evaluate the proposed algorithms through experimental simulations. The experimental results demonstrate that the proposed algorithms are promising, compared with existing baseline algorithms.

Mobile Edge Computing (MEC) reforms the cloud paradigm by bringing unprecedented computing capacity to the vicinity of mobile users at the mobile network edge. This provides end-users with swift and powerful computing, energy efficiency, storage capacity, mobility-and context-awareness support. Furthermore, provisioning virtualized network services in MEC can improve user service experience, simplify network service deployments, and ease network resource management. However, user requests usually arrive into the system dynamically and different user requests may have different resource demands. How to optimize and guarantee the performance of MEC is of significant importance and challenging. In this paper, we study the problem of online NFV-enabled multicasting in an MEC network with resource capacity constraints on both cloudlets and links. We first devise an approximation algorithm for the cost minimization problem for a single NFV-enabled multicast request admission. We then propose an online algorithm with a provable competitive ratio for the online throughput maximization problem where NFV-enabled multicast requests arrive one by one without the knowledge of future request arrivals. We admit the requests through placing or sharing VNF instances of network functions in their service chains to meet their computing and bandwidth resource demands, and we introduce a novel cost model to capture the dynamic usages of different resources and perform network resource allocations based on the proposed cost model. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

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.

Driven by stringent delay requirements of mobile applications, the mobile edge cloud has emerged as a major platform to offer low latency network services from the edge of networks. Most conventional network services are implemented via hardware-based network functions, such as firewalls and load balancers, to guarantee service security and performance. However, implementing such hardware-based network functions incurs high purchase and maintenance costs. Network function virtualization (NFV) as a promising technology exhibits great potential to reduce the purchase and maintenance costs by implementing network functions as software in virtual machines (VMs). In this paper, we consider a fundamental problem of NFV-enabled multicasting in a mobile edge cloud, where each multicast request requires to process its traffic in a specified sequence of network functions (referred to as a service chain) before the traffic from a source to a set of destinations. We devise a provable approximation algorithm with an approximation ratio for the problem if requests do not have delay requirements; otherwise, we propose an efficient heuristic for it. We also evaluate the performance of the proposed algorithms against the state-of-the-art NFV-enabled multicasting algorithms, and results show that our algorithms outperform their counterparts.

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.

Multicasting is a fundamental functionality of many network applications, including online conferencing, event monitoring, video streaming, and so on. To ensure reliable, secure, and scalable multicasting, a service chain that consists of network functions (e.g., firewalls, intrusion detection systems, and transcoders) usually is associated with each multicast request. We refer to such a multicast request with service chain requirement as an network function virtualization (NFV)-enabled multicast request. In this paper, we study NFV-enabled multicasting in a software-defined network (SDN) with an aim to maximize network throughput while minimizing the implementation cost of admitted NFV-enabled multicast requests, subject to network resource capacity, where the implementation cost of a request consists of its computing resource consumption cost in servers and its network bandwidth consumption cost when routing and processing its data packets in the network. To this end, we first formulate two NFV-enabled multicasting problems with and without resource capacity constraints and one online NFV-enabled multicasting problem. We then devise two approximation algorithms with an approximation ratio of $2M$ for the NFV-enabled multicasting problems with and without resource capacity constraints, if the number of servers for implementing the service chain of each request is no greater than a constant $M$ (≥1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an efficient heuristic, and for the special case of dynamic request admissions, we devise an online algorithm with a competitive ratio of $O(\log n)$ for it when $M=1$ , where $n$ is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising and outperform existing heuristics.

This paper proposes a unified spatio-temporal model for short-term road traffic prediction. The contributions of this paper are as follows. First, we develop a physically intuitive approach to traffic prediction that captures the time-varying spatio-temporal correlation between traffic at different measurement points. The spatio-temporal correlation is affected by the road network topology, time-varying speed, and time-varying trip distribution. Distinctly different from previous black-box approaches to road traffic modeling and prediction, parameters of the proposed approach have physically intuitive meanings which make them readily amendable to suit changing road and traffic conditions. Second, unlike some existing techniques that capture the variation of spatio-temporal correlation by a complete re-design and calibration of the model, the proposed approach uses a unified model that incorporates the physical factors potentially affecting the variation of spatio-temporal correlation into a series of parameters. These parameters are relatively easy to control and adjust when road and traffic conditions change, thereby greatly reducing the computational complexity. Experiments using two sets of real traffic traces demonstrate that the proposed approach has superior accuracy compared with the widely used space-time autoregressive integrated moving average (STARIMA) and the back propagation neural network approaches, and is only marginally inferior to that obtained by constructing multiple STARIMA models for different times of the day, however, with a much reduced computational and implementation complexity.

Pushing the cloud frontier to the network edge close to mobile users has attracted tremendous interest not only from cloud operators but also from network service providers. In particular, the deployment of cloudlets in metropolitan area networks enables network service providers to provide low-latency services to mobile users through implementing their specified virtualized network functions (VNFs) while meeting their Quality-of-Service (QoS) requirements. In this paper, we formulate a novel task offloading problem in a mobile edge-cloud network, where each offloading task requests a specified network function with a tolerable delay. We aim to maximize the number of requests admitted while minimizing the operational cost of admitted requests within a finite time horizon, through either sharing existing VNF instances or creating new VNF instances in cloudlets. We first show that the problem is NP-hard, and then devise an efficient online algorithm for the problem by reducing it to a series of minimum weight maximum matching problems. Considering dynamic changes of task offloading request patterns over time, we further develop an effective prediction mechanism for new VNF instance creations and idle VNF instance releases to further lower the operational cost of the network service provider. Also, we devise an online algorithm with a competitive ratio for a special case of the problem where the delay requirements of requests are negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results indicate that the proposed algorithms are promising.

Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Function Chains of user requests by steering data traffic along middleboxes in the service function chains before reaching their destinations. Network Function Virtualization (NFV) is a promising virtualization technique that implements network functions as pieces of software in servers or data centers. The integration of NFV and Software Defined Networking (SDN) further simplifies service function chain provisioning, making its implementation simpler and cheaper. In this paper, we consider dynamic admissions of delay-aware requests with service function chain requirements in a distributed cloud with the objective to maximize the profit collected by the service provider, assuming that the distributed cloud is an SDN that consists of data centers located at different geographical locations and electricity prices at different data centers are different. We first formulate this novel optimization problem as a dynamic profit maximization problem. We then show that the offline version of the problem is NP-hard and formulate an integer linear programming solution to it. We third propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of each request is negligible. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.

Enterprise users at different geographic locations generate large-volume data that is stored at different geographic datacenters. These users may also perform big data analytics on the stored data to identify valuable information in order to make strategic decisions. However, it is well known that performing big data analytics on data in geographical-located datacenters usually is time-consuming and costly. In some delay-sensitive applications, the query result may become useless if answering a query takes too long time. Instead, sometimes users may only be interested in timely approximate rather than exact query results. When such approximate query evaluation is the case, applications must sacrifice timeliness to get more accurate evaluation results or tolerate evaluation result with a guaranteed error bound obtained from analyzing the samples of the data to meet their stringent timeline. In this paper, we study quality-of-service (QoS)-aware data replication and placement for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on the problems of placing data samples of the source data at some strategic datacenters to meet stringent query delay requirements of users, by exploring a non-trivial trade-off between the cost of query evaluation and the error bound of the evaluation result. We first propose an approximation algorithm with a provable approximation ratio for a single approximate query. We then develop an efficient heuristic algorithm for evaluating a set of approximate queries with the aim to minimize the evaluation cost while meeting the delay requirements of these queries. We finally demonstrate the effectiveness and efficiency of the proposed algorithms through both experimental simulations and implementations in a real test-bed, real datasets are employed. Experimental results show that the proposed algorithms are promising.

Network Function Virtualization (NFV) and Software-Defined Networking (SDN) have been envisioned an essential milestone in the evolution of communication networks. Their integration provides a more flexible and easier manageable software-based network environment that induces high expectations for reducing capital expenditures (CAPEX) and operational costs (OPEX) of network service providers. They also introduce technical challenges. One such challenge is to manage the placement of VNFs and to steer the data traffic of each NFV-enabled request through its specified network functions. In this paper, we opportunistically adopt the flexibility and cost-efficiency of VNF and SDN for NFV-enabled request admissions in SDNs and formulate profit maximization problems for static and dynamic NFV-enabled request admissions. We first provide an integer linear programming (ILP) solution to the problem in the static version if the problem size is small; otherwise, we devise a fast approximation algorithm with a provable approximation ratio for the static request admissions. We then propose an efficient online algorithm for dynamic request admissions, by leveraging VNF instance migrations and idle VNF releases back to the system. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are very promising.

As the critical supplementary to terrestrial communication networks, the low-earth-orbit (LEO) satellite based communication networks regain growing attentions in recent few years. In this paper, we focus on data gathering for geo- distributed Internet-of-Things (IoT) networks via LEO satellites. Normally, the power supply in IoT data-gathering gateways is a bottleneck resource that constrains the network throughput. Thus, the challenge is how to upload data from IoT gateways to LEO satellites under dynamic uplinks in an energy-efficient way. To address this problem, we first formulate a novel optimization problem, and then propose an online algorithm for green data-uploading in geo-distributed IoT networks. In the proposed framework, we aim to jointly maximize the network throughput and minimize the energy consumption at gateways, while avoiding the buffer overflow at gateways. We finally evaluate the performance of the proposed algorithm through simulations using both real-world and synthetic traces. The simulation results demonstrate that the proposed approach can achieve high efficiency on the power consumption and significantly reduce queue backlogs compared with a benchmark using greedy policy.

Network Function Virtualization (NFV) has attracted significant attentions from both industry and academia as an important paradigm change in network service provisioning. Most existing studies on NFV dealt with admissions of user requests through deploying Virtualized Network Function (VNF) instances for individual user requests, without considering sharing VNF instances among multiple user requests to provide better network services and improve network throughput. In this paper, we study the network throughput maximization problem by adopting two different VNF instance scalings: (i) horizontal scaling by migrating existing VNF instances from their current locations to new locations; and (ii) vertical scaling by instantiating more VNF instances if needed. Specifically, we first propose a unified framework that jointly considers both vertical and horizontal scalings to maximize the network throughput, by admitting as many requests as possible while meeting their resource demands and end-to-end transmission delay requirements. We then devise an efficient heuristic algorithm for the problem. We finally conduct experiments to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm outperforms a baseline algorithm.

Traditional networks employ expensive dedicated hardware devices as middleboxes to implement Service Chains (SC) of user requests by steering data traffic along the middleboxes in the service chains. Network Function Virtualization (NFV) is a promising virtualization technique by implementing network functions as pieces of software in servers or data centers. By leveraging the technique of Software Defined Networking (SDN), NFV can be further enabled in a flexible and dynamic way. In this paper, we consider dynamic admissions of delay-aware NFV-enabled requests in SDNs by leveraging pre-installed NFV instances in data centers. We first formulate a novel revenue maximization problem, and show that the problem is NP-hard. We then propose an online heuristic for the problem. We also devise an online algorithm with a provable competitive ratio for a special case of the problem where the end-to-end delay requirement of requests can be neglected. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are promising.

Traditional network functions (NFs) such as firewalls are implemented in costly dedicated hardware. By decoupling NFs from physical devices, network function virtualization enables virtual network functions (VNF) to run in virtual machines (VMs). However, VNFs are vulnerable to various faults such as software and hardware failures. To enhance VNF fault tolerance, the deployment of backup VNFs in stand-by VM instances is necessary. In case of stateful VNFs, stand-by instances require constant state updates from active instances during its operation. This will guarantee a correct and seamless handover from failed instances to stand-by instances after failures. Nevertheless, such state updates to stand-by instances could consume significant network bandwidth resources and lead to potential admission failures for VNF requests. In this paper, we study the fault-tolerant VNF placement problem with the optimization objective of admitting as many requests as possible. In particular, the VNF placement of active/stand-by instances, the request routing paths to active instances, and state transfer paths to stand-by instances are jointly considered. We devise an efficient heuristic algorithm to solve this problem, and propose a bicriteria approximation algorithm with performance guarantees for a special case of the problem. Simulations with realistic settings show that our algorithms can significantly improve the request admission rate compared to conventional approaches.

Mobile Edge Computing (MEC) is essential for enabling new innovative technologies that depend on low-latency computation environments such as Augmented Reality (AR). As AR applications continue to deliver better graphics with richer interactive features, AR devices will increasingly rely on nearby cloudlets to assist with the demanding computation requirements of AR applications. Supporting multiplayer interactions in an MEC environment brings many challenges. Processing user interactions can be computation-intensive especially when multiple users in close proximity to each other are acting simultaneously; the limited resources of a cloudlet could be overwhelmed if there are too many players involved. In this paper, we envision a scenario in the near future where players wearing AR heads-up display devices engage with other players over a large area with densely deployed cloudlets. We first propose a novel system model, and then formulate the Decentralized Multiplayer Coordination (DMC) Problem with the aim of minimizing the game frame duration among players, and devise an efficient algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. Experimental results demonstrate that the proposed algorithm is promising.

Vertices in a real-world social network can be grouped into densely connected communities that are sparsely connected to other groups. Moreover, these communities can be partitioned into successively more cohesive communities. Despite an ever-growing pile of research on hierarchical community detection, existing methods suffer from either inefficiency or inappropriate modeling. Yet, some cut-based approaches have shown to be effective in finding communities without hierarchies. In this paper, we study the hierarchical community detection problem in large networks and show that it is NP-hard. We then propose an efficient algorithm based on edge-cuts to identify the hierarchy of communities. Since communities at lower levels of the hierarchy are denser than the higher levels, we leverage a fast network sparsification technique to enhance the running time of the algorithm. We further propose a randomized approximation algorithm for information centrality of networks. We finally evaluate the performance of the proposed algorithms by conducting extensive experiments using real datasets. Our experimental results show that the proposed algorithms are promising and outperform the state-of-the-art algorithms by several orders of magnitude.

Cloud computing built on virtualization technologies promises provisioning elastic computing and bandwidth resource services for enterprises that outsource their IT services as virtual networks. To share the cloud resources efficiently among different enterprise IT services, embedding their virtual networks into a distributed cloud that consists of multiple data centers, poses great challenges. Motivated by the fact that most virtual networks operate on long-term basis and have the characteristics of periodic resource demands, in this paper we study the virtual network embedding problem of embedding as many virtual networks as possible to a distributed cloud such that the revenue collected by the cloud service provider is maximized, while the service level agreements (SLAs) between enterprises and the cloud service provider are met. We first propose an efficient embedding algorithm for the problem, by incorporating a novel embedding metric that accurately models the dynamic workloads on both data centers and inter-data center links, provided that the periodic resource demands of each virtual network are given and all virtual networks have identical resource demand periods. We then show how to extend this algorithm for the problem when different virtual networks may have different resource demand periods. Furthermore, we also develop a prediction mechanism to predict the periodic resource demands of each virtual network if its resource demands are not given in advance. We finally evaluate the performance of the proposed algorithms through experimental simulation based on both synthetic and real network topologies. Experimental results demonstrate that the proposed algorithms outperform existing algorithms from 10 to 31 percent in terms of performance improvement.

Real social networks contain many communities, where members within each community are densely connected with each other, while they are sparsely connected with the members outside of the community. Since each member can join multiple communities simultaneously, communities in social networks are usually overlapping with each other. How to efficiently and effectively identify overlapping communities in a large social network becomes a fundamental problem in the big data era. Most existing studies on community finding focused on non-overlapping communities based on several well-known community fitness metrics. However, recent investigations have shown that these fitness metrics may suffer free rider and separation effects where the overlapping region of two communities always belongs to the denser one, rather to both of them. In this paper, we study the overlapping community detection problem in social networks that not only takes the quality of the found overlapping communities but also incorporate both free rider and separation effects on the found communities into consideration. Specifically, in this paper, we first propose a novel community fitness metric - triangle based fitness metric, for overlapping community detection that can minimize the free rider and separation effects on found overlapping communities, and show that the problem is NP-hard. We then propose an efficient yet scalable algorithm for the problem that can deliver a feasible solution. We finally validate the effectiveness of the proposed fitness metric and evaluate the performance of the proposed algorithm, through conducting extensive experiments on real-world datasets with over 100 million vertices and edges. Experimental results demonstrate that the proposed algorithm is very promising.

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.

Data transfer in contemporary networks usually is associated with strict policy enforcement for data transfer security and system performance purposes. Such a policy is represented by a service chain consisting of a sequence of network functions such as firewalls, intrusion detection systems, transcoders, etc. Due to the high cost and inflexibility of managing hardware-based network functions, network function virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain of each data transfer request in a low-cost and flexible way. In this paper, we study policy-aware unicast request admissions with and without end-to-end delay constraints in a software defined network. We aim to minimize the operational cost of admitting a single request in terms of both computing resource consumption for implementing the NFVs in the service chain and bandwidth resource consumption for routing its data traffic, or maximize the network throughput for a sequence of requests without the knowledge of future request arrivals. We first formulate four novel optimization problems and provide a generic optimization framework for the problems. We then develop efficient algorithms for the admission of a single NFV-enabled request with and without the end-to-end delay constraint, where NFV-enabled requests are defined as the requests with policy enforcement requirements. We also devise online algorithms with a guaranteed performance for dynamic admissions of requests without the knowledge of future arrivals. In particular, we provide the very first online algorithm with a provable competitive ratio for the problem without the end-to-end delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the proposed algorithms are promising and outperform existing heuristics.

Data transfers in contemporary networks depend upon network functions for ensuring data security and system performance. These policies are represented by a service chain that consists of different network functions such as firewalls, Intrusion Detection Systems (IDSs), transcoders, etc. Network Function Virtualization (NFV) has emerged as a promising technology to meet the stringent requirement imposed on the service chain. In this paper, we study NFV-enabled unicasting in SDNs with and without end-to-end delay constraints. We aim to maximize the network throughput for a sequence of NFV-enabled unicast requests without the knowledge of future arrivals. We first formulate the problems as novel optimization problems in terms of both computing and bandwidth resource consumptions, and provide a generic optimization framework. We then develop an online algorithm with guaranteed performance without the delay requirement and a heuristic with the delay requirement. We finally evaluate the performance of the proposed algorithms through experimental simulations. The results of the experimental simulations show that the proposed algorithms are promising.

Enterprise users at different geographic locations generate large-volume data and store their data at different geographic datacenters. These users may also issue ad hoc queries of big data analytics on the stored data to identify valuable information in order to help them make strategic decisions. However, it is well known that querying such large-volume big data usually is time-consuming and costly. Sometimes, users are only interested in timely approximate rather than exact query results. When this approximation is the case, applications must sacrifice either timeliness or accuracy by allowing either the latency of delivering more accurate results or the accuracy error of delivered results based on the samples of the data, rather than the entire set of data itself. In this paper, we study the QoSaware data replications and placements for approximate query evaluation of big data analytics in a distributed cloud, where the original (source) data of a query is distributed at different geo-distributed datacenters. We focus on placing the samples of the source data with certain error bounds at some strategic datacenters to meet users' stringent query response time. We propose an efficient algorithm for evaluating a set of big data analytic queries with the aim to minimize the evaluation cost of the queries while meeting their response time requirements. We demonstrate the effectiveness of the proposed algorithm through experimental simulations. Experimental results show that the proposed algorithm is promising.

Network function virtualization (NFV) has been emerging as a new paradigm to enable elastic and inexpensive network services in modern computer networks, through deploying flexible virtualized network functions (VNFs) running in virtual computing platforms. Different VNFs can be chained together to form different service chains, to meet various user data routing demands for different network services. In this paper we consider provisioning network services in an NFV-enabled network that consists of data centers for implementing VNF instances of service chains and switches. We study the throughput maximization problem with the aim to admit as many user requests as possible while minimizing the implementation cost of the requests, assuming that limited numbers of instances of each service chain have been stored in data centers. We first propose an optimal algorithm for the problem if all requests have identical packet rates; otherwise, we devise two approximation algorithms with probable approximation ratios, depending on whether the packet traffic of each request is splittable. We finally conduct experiments to evaluate the performance of the proposed algorithms by simulations. Experimental results show that the proposed algorithms achieve at least 15% more throughput than that of a greedy algorithm.

Software-defined networking (SDN) is a promising technique that has reshaped the landscape of network management. By providing simplified, cost-effective management, SDN has been envisioned as the next-generation network paradigm. However, due to economic, organizational, and technical challenges, replacing all conventional switches in current operational networks by SDN-enabled switches is impractical in the short term. It thus is desirable to deploy SDN-enabled switches into existing networks incrementally, and such a network consisting of SDN-enabled switches and conventional switches is referred to as a hybrid SDN network. The incremental deployment of SDN-enabled switches is challenging because the number of conventional switches that can be replaced is typically limited, due to budget constraints or operational network stability concerns, yet the impact of the deployment should be maximized. In this paper, we deal with the SDN-enabled switch placement problem with the aim to maximize system performance, given $K$ switches to be replaced, for which we first propose heuristics by replacing conventional switches one by one iteratively. We then devise scalable algorithms that replace multiple switches, instead of a single switch, in each iteration. We finally evaluate the performance of the proposed algorithms based on real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms are promising and exhibiting high scalability.

Multicasting is a fundamental functionality of networks for many applications including online conferencing, event monitoring, video streaming, and system monitoring in data centers. To ensure multicasting reliable, secure and scalable, a service chain consisting of network functions (e.g., firewalls, Intrusion Detection Systems (IDSs), and transcoders) usually is associated with each multicast request. Such a multicast request is referred to as an NFV-enabled multicast request. In this paper we study NFV-enabled multicasting in a Software-Defined Network (SDN) with the aims to minimize the implementation cost of each NFV-enabled multicast request or maximize the network throughput for a sequence of NFV-enabled requests, subject to network resource capacity constraints. We first formulate novel NFV-enabled multicasting and online NFV-enabled multicasting problems. We then devise the very first approximation algorithm with an approximation ratio of 2K for the NFV-enabled multicasting problem if the number of servers for implementing the network functions of each request is no more than a constant K (1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an online algorithm with a competitive ratio of O(log n) when K = 1, where n is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms outperform other existing heuristics.

Pushing the cloud frontier to the network edge has attracted tremendous interest not only from cloud operators of the IT service/software industry but also from network service operators that provide various network services for mobile users. In particular, by deploying cloudlets in metropolitan area networks, network service providers can provide various network services through implementing virtualized network functions to meet the demands of mobile users. In this paper we formulate a novel task offloading problem in a metropolitan area network, where each offloaded task requests a specific network function with a maximum tolerable delay and different offloading requests may require different network services. We aim to maximize the number of requests admitted while minimizing their admission cost within a finite time horizon. We first show that the problem is NP-hard, and then devise an efficient algorithm through reducing the problem to a series of minimum eight maximum matching in auxiliary bipartite graphs. We also consider dynamic changes of offloading request patterns over time, and develop an effective prediction mechanism to release and/or create instances of network functions in different cloudlets for cost savings. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results indicate that the proposed algorithms are promising.

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.

With more and more businesses and organizations outsourcing their IT services to distributed clouds for cost savings, historical and operational data generated by the services have been growing exponentially. The generated data that are referred to as big data, stored at different geographic datacenters, now become an invaluable asset to these businesses and organizations, as they can make use of the data through analysis to identify business advantages and make strategic decisions. Big data analytics thus has been emerged as a main research topic in cloud computing. To efficiently evaluate a big data analytic query in a distributed cloud consisting of multiple datacenters at different geographic locations interconnected by the Internet, it poses great challenges: (i) the source data of the query typically are located at different datacenters; and (ii) the resource demands of the query may be beyond the supplies of any single datacenter at that moment. In this paper, we formulate an online query evaluation problem for big data analytic queries in distributed clouds, with an objective to maximize the query acceptance ratio while minimizing the accumulative query evaluation cost, for which we first propose a novel metric to model the usages of different resources in the distributed cloud, by incorporating the capacities and workloads of different datacenters and links, as well as resource demands of different queries. We then devise efficient online algorithms for query evaluations under both unsplittable and splittable source data assumptions. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are promising, and outperform other heuristics at 95% confidence intervals.

Mobile applications are becoming increasingly computation-intensive, while the computing capability of portable mobile devices is limited. A powerful way to reduce the completion time of an application in a mobile device is to offload its tasks to nearby cloudlets, which consist of clusters of computers. Although there is a significant body of research in mobile cloudlet offloading technology, there has been very little attention paid to how cloudlets should be placed in a given network to optimize mobile application performance. In this paper we study cloudlet placement and mobile user allocation to the cloudlets in a wireless metropolitan area network (WMAN). We devise an algorithm for the problem, which enables the placement of the cloudlets at user dense regions of the WMAN, and assigns mobile users to the placed cloudlets while balancing their workload. We also conduct experiments through simulation. The simulation results indicate that the performance of the proposed algorithm is very promising.

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.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve network security and performance. A promising emerging technique to implementing traditional middleboxes is the consolidated middlebox technique, which implements the middleboxes as software in virtual machines in software-defined networks (SDNs), offering economical, and simplified management for middleboxes. This however poses a great challenge, that is, how to find a cost-optimal routing path for each user request such that the data traffic of the request will pass through the middleboxes in their orders in the service chain of the request, with the objective to maximize the network throughput, subject to various resource capacity constraints in SDNs. In this paper, we study the network throughput maximization problem in an SDN under two different scenarios: one is the snapshot scenario where a set of requests at one time slot is given, we aim to admit as many requests in the set as possible to maximize the network throughput; another is the online scenario in which requests arrive one by one without the knowledge of future arrivals. Given a finite time horizon consisting of T equal time slots, the system must respond to the arrived requests in the beginning of each time slot, by either admitting or rejecting the requests, depending on the resource availabilities in the network. For the snapshot scenario, we first formulate an integer linear program (ILP) solution, we then devise two heuristics that strive for fine tradeoffs between the quality of a solution and the running time of obtaining the solution. For the online scenario, we show how to extend the proposed algorithms for the snapshot scenario to solve the online scenario. We finally evaluate the performance of the proposed algorithms through experimental simulations, based on both real and synthetic network topologies. Experimental results demonstrate that the proposed algorithms admit more requests than the baseline algorithm and the quality of the solutions delivered by heuristics is comparable to the exact solution by the ILP in most cases.

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.

With advances in wireless communication technology, more and more people depend heavily on portable mobile devices for businesses, entertainments and social interactions. Although such portable mobile devices can offer various promising applications, their computing resources remain limited due to their portable size. This however can be overcome by remotely executing computation-intensive tasks on clusters of near by computers known as cloudlets. As increasing numbers of people access the Internet via mobile devices, it is reasonable to envision in the near future that cloudlet services will be available for the public through easily accessible public wireless metropolitan area networks (WMANs). However, the outdated notion of treating cloudlets as isolated data-centers-in-a-box must be discarded as there are clear benefits to connecting multiple cloudlets together to form a network. In this paper we investigate how to balance the workload between multiple cloudlets in a network to optimize mobile application performance. We first introduce a system model to capture the response times of offloaded tasks, and formulate a novel optimization problem, that is to find an optimal redirection of tasks between cloudlets such that the maximum of the average response times of tasks at cloudlets is minimized. We then propose a fast, scalable algorithm for the problem. We finally evaluate the performance of the proposed algorithm through experimental simulations. The experimental results demonstrate the significant potential of the proposed algorithm in reducing the response times of tasks.

Today's computer networks rely on a wide spectrum of specialized middleboxes to improve their security and performance. Traditional middleboxes that are implemented by dedicated hardware are expensive and hard to manage. A promising technique of consolidated middleboxes - implementing traditional middleboxes in Virtual Machines (VMs) - offers economical yet simplified management of middleboxes in Software-Defined Networks (SDNs). However there are still challenges to realizing user routing requests with network function enforcement (a sequence of middleboxes) while maximizing the network throughput, due to various resource constraints on SDNs, such as forwarding table capacity at each switch, bandwidth resource capacity at each link, and computing resource capacity at each server (Physical Machine). In this paper, we study the problem of maximizing the network throughput of an SDN by admitting as many user requests as possible, where each user request has both bandwidth and computing resource demands to implement its network functions (consolidated middleboxes). We first formulate the problem as a novel network throughput maximization problem. We then provide an Integer Linear Program (ILP) solution for it if the problem size is small, otherwise, we devise two heuristics that strive for the fine tradeoff between the accuracy of solutions and the running times of achieving the solutions. We finally evaluate the performance of the proposed algorithms by simulations, based on real and synthetic network topologies. Experimental 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.

Facing the spectrum supply-demand gap, heterogeneous network (HetNet) is a promising approach to achieve drastic gains in network coverage and capacity compared with macro-only networks, thus making it especially attractive to network operators. On the other hand, software-defined networking brings a number of advantages along with many challenges. One particular concern is on the resilience for in-band fashioned control plane. Existing approaches mainly rely on a local rerouting policy when performing the routing protection for the target sessions in software-defined networks. However, such a policy would potentially bring congestions in the neighbouring links of the failed one. To this end, we study a weighted cost-minimization problem, where the traffic load balancing and control-channel setup cost are jointly considered. Because this problem is NP-hard, we first propose a near-optimal Markov approximation-based approach for in-band-fashioned software-defined HetNets. We then extend our solution to an online case that handles a single-link failure. We also conduct theoretical analysis on the performance fluctuation due to the single-link failure. We finally carry out experiments by experimental simulation. The extensive numerical results show that the proposed algorithm has fast convergence and high efficiency in resource utilization.

In this paper, we analyze the maximum likelihood decoding performance of Raptor codes with a systematic low-density generator-matrix code as the pre-code. By investigating the rank of the product of two random coefficient matrices, we derive upper and lower bounds on the decoding failure probability. The accuracy of our analysis is validated through simulations. Results of extensive Monte Carlo simulations demonstrate that for Raptor codes with different degree distributions and pre-codes, the bounds obtained in this paper are of high accuracy. The derived bounds can be used to design near-optimum Raptor codes with short and moderate lengths.

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.

Software-defined networking (SDN) is an emerging network paradigm that simplifies network management by decoupling the control plane and data plane, such that switches become simple data forwarding devices and network management is controlled by logically centralized servers. In SDN-enabled networks, network flow is managed by a set of associated rules that are maintained by switches in their local Ternary Content Addressable Memories (TCAMs) which support high-speed parallel lookup on wildcard patterns. Since TCAM is an expensive hardware and extremely power-hungry, each switch has only limited TCAM space and it is inefficient and even infeasible to maintain all rules at local switches. On the other hand, if we eliminate TCAM occupation by forwarding all packets to the centralized controller for processing, it results in a long delay and heavy processing burden on the controller. In this paper, we strive for the fine balance between rule caching and remote packet processing by formulating a minimum weighted flow provisioning ( MWFP) problem with an objective of minimizing the total cost of TCAM occupation and remote packet processing. We propose an efficient offline algorithm if the network traffic is given, otherwise, we propose two online algorithms with guaranteed competitive ratios. Finally, we conduct extensive experiments by simulations using real network traffic traces. The simulation results demonstrate that our proposed algorithms can significantly reduce the total cost of remote controller processing and TCAM occupation, and the solutions obtained are nearly optimal.

With the advancement of information and communication technology, data are being generated at an exponential rate via various instruments and collected at an unprecedented scale. Such large volume of data generated is referred to as big data, which now are revolutionizing all aspects of our life ranging from enterprises to individuals, from science communities to governments, as they exhibit great potentials to improve efficiency of enterprises and the quality of life. To obtain nontrivial patterns and derive valuable information from big data, a fundamental problem is how to properly place the collected data by different users to distributed clouds and to efficiently analyze the collected data to save user costs in data storage and processing, particularly the cost savings of users who share data. By doing so, it needs the close collaborations among the users, by sharing and utilizing the big data in distributed clouds due to the complexity and volume of big data. Since computing, storage and bandwidth resources in a distributed cloud usually are limited, and such resource provisioning typically is expensive, the collaborative users require to make use of the resources fairly. In this paper, we study a novel collaboration- and fairness-aware big data management problem in distributed cloud environments that aims to maximize the system throughout, while minimizing the operational cost of service providers to achieve the system throughput, subject to resource capacity and user fairness constraints. We first propose a novel optimization framework for the problem. We then devise a fast yet scalable approximation algorithm based on the built optimization framework. We also analyze the time complexity and approximation ratio of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. Experimental results demonstrate that the proposed algorithm is promising, and outperforms other heuristics.

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.

Distributed clouds, consisting of multiple data centers located at different geographical locations, provide a plethora of services to users. They however consume enormous amounts of electricity to power their data centers. The electricity bill is almost 30%-50% of their operational costs. Minimizing the electricity cost of distributed clouds thus is crucial to reduce the operational cost of their cloud service providers. In this paper, we study the problem of minimizing the electricity cost of a distributed cloud, by exploring the heterogeneities of cloud resources and user demands, and time-varying electricity prices, for which we first propose a two-stage optimization framework: dispatching user task requests to different data centers by incorporating the resource demands of the task requests, the workload, and the electricity price in each data center, and energy consumption profiles of different servers in each data center; followed by further energy optimization within each data center through consolidating Virtual Machines (VMs) to different servers to improve the resource utilization ratio. One critical constraint on such task dispatch and VM consolidation is to meet various user Service Level Agreements (SLAs), which include average task scheduling delays and resource demand violation limitations. Under the proposed framework, we then devise efficient scheduling algorithms for task dispatching and VM consolidations, while keeping both the average scheduling delay and resource demand violation limitation of each admitted task met. We finally evaluate the performance of the proposed algorithms through experimental simulations, using real data sets - the real electricity prices and task traces. Experimental simulation results demonstrate that the proposed algorithms are 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.

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.

Cloud computing built on virtualization technologies promises provisioning elastic computing and communication resources to enterprise users. To share cloud resources efficiently, embedding virtual networks of different users to a distributed cloud consisting of multiple data centers (a substrate network) poses great challenges. Motivated by the fact that most enterprise virtual networks usually operate on long-term basics and have the characteristics of periodic resource demands, in this paper we study the virtual network embedding problem by embedding as many virtual networks as possible to a substrate network such that the revenue of the service provider of the substrate network is maximized, while meeting various Service Level Agreements (SLAs) between enterprise users and the cloud service provider. For this problem, we propose an efficient embedding algorithm by exploring periodic resource demands of virtual networks, and employing a novel embedding metric that models the workloads on both substrate nodes and communication links if the periodic resource demands of virtual networks are given; otherwise, we propose a prediction model to predict the periodic resource demands of these virtual networks based on their historic resource demands. We also evaluate the performance of the proposed algorithms by experimental simulation. Experimental results demonstrate that the proposed algorithms outperform existing algorithms, improving the revenue from 10% to 31%.

With the advance of energy harvesting technology, more and more sensors now are powered by ambient energy. Energy harvesting sensor networks are a key step in paving the way for truly green systems that can operate `perpetually' and do not adversely impact on the environment. In this paper we consider quality data collection in an energy harvesting sensor network by exploring sink mobility. That is, we consider a mobile sink traveling along a to-be-found trajectory for data collection, subject to a specified tolerant delay constraint. We first formulate this optimization problem as a data quality maximization problem. Since the problem is NP-hard, we then devise a scalable heuristic solution. Also, a distributed implementation of the proposed algorithm is developed too. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithms. Experimental results demonstrate that the proposed algorithms are promising and very efficient.

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 communication effectively enhances the channel capacity of wireless networks by allowing some single-antenna nodes to relay data for other nodes. In such a communication scheme, choosing appropriate relay nodes is critical to maximize the overall network performance. In this paper, we consider the assignment problem of relay nodes in a cooperative wireless network, where physical relay infrastructures and relay supporting services (relay assignment) are independently operated by different selfish entities, each of which is driven by its own benefit. We first formulate the problem as a repeated double auction by taking into account the benefits of all entities in the system. That is, we consider a system consisting of a set of source-to-destination pairs, relay nodes, group agents, and the auctioneer, where source nodes are grouped into different groups and each group is represented by a group agent. The source nodes and group agents seek opportunities to maximize their own benefits through untruthful bidding, colluding with each other, and so on. We then show that these behaviors will jeopardize the social benefit of all entities in the system. To mitigate the effect of such behaviors, we devise a truthful repeated double auction that is able to bound the collusion probability of each entity. We finally conduct experiments by simulations to evaluate the performance of the proposed auction mechanism. Empirical results show that the proposed auction is effective in collusion-resistance with bounded collusion probabilities. To our best knowledge, this is the first auction mechanism for relay assignment in wireless networks that is truthful, collusion-resistant, budget-balance and individual-rational.

Data centers, serving as infrastructures for cloud services, are growing in both number and scale. However, they usually consume enormous amounts of electric power, which lead to high operational costs of cloud service providers. Reducing the operational cost of data centers thus has been recognized as a main challenge in cloud computing. In this paper we study the minimum operational cost problem of fair request rate allocations in a distributed cloud environment by incorporating the diversity of time-varying electricity prices in different regions, with an objective to fairly allocate requests to different data centers for processing while keeping the negotiated Service Level Agreements (SLAs) between request users and the cloud service provider to be met, where the data centers and web portals of a cloud service provider are geographically located in different regions. To this end, we first propose an optimization framework for the problem. We then devise a fast approximation algorithm with a provable approximation ratio by exploiting combinatorial properties of the problem. We finally evaluate the performance of the proposed algorithm through experimental simulation on real-life electricity price data sets. Experimental results demonstrate that the proposed algorithm is very promising, which not only outperforms other existing heuristics but also is highly scalable.

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.

Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l « |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3 log |V|) to O(h × l × |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude.

In this paper we study data collection in an energy harvesting sensor network where sensors are deployed along a given path and a mobile sink travels along the path periodically for data collection. Such a typical application scenario is to employ a mobile vehicle for traffic surveillance of a given highway. As the sensors in this network 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 harvesting sensor networks. In this paper we first formulate a novel optimization problem as a network utility maximization problem, by incorporating multi-rate communication mechanism between sensors and the mobile sink and show the NP-hardness of the problem. We then devise a novel centralized algorithm for it, assuming that the global knowledge of the entire network is available. We also develop a distributed solution to the problem without the global knowledge assumption. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms are promising and very efficient.

In this paper we consider a remote monitoring scenario where the monitoring center is geographically located far away from the region of the deployed sensor network, and the sensing data by the sensors is transmitted to the monitoring center through a third party telecommunication service, thus a cost associated with this service will be incurred, which is related to the amount of data successfully received by the monitoring center within a specified period. For this scenario, we first formulate a novel optimization problem, namely, the throughput guaranteed service cost minimization problem with an objective to minimize the service cost while the specified network throughput requirement is guaranteed. We show that the problem is NP-complete. We then propose a heuristic for it. The key ingredients of the heuristic include identifying gateways and finding an energy-efficient forest of routing trees rooted at the gateways. Finally, we conduct experiments by simulation to evaluate the performance of the proposed heuristic. The experimental results demonstrate the proposed algorithm outperforms other two mentioned algorithms in terms of both service cost and the network lifetime.

To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes, and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multihop relays, while the mobile sinks travel along predetermined trajectories to collect data from nearby gateway nodes. Under this paradigm of data gathering, we formulate a novel constrained optimization problem, namely, the capacitated minimum forest (CMF) problem, for the decision version of which we first show NP-completeness. We then devise approximation algorithms and provide upper bounds for their approximation ratios. We finally evaluate the performance of the proposed algorithms through experimental simulation. In our experiments, the approximation ratio delivered by the proposed algorithms is always less than 2. In the case of arbitrary gateway capacities, this contrasts our theoretical results which show that the approximation ratio is at most linear in the number of gateways. Our experiments thus indicate that for realistic inputs, our worst case analysis of the approximation ratio is very conservative. The proposed algorithms are the first approximation algorithms for the CMF problem, and our techniques may be applicable to other constrained optimization problems beyond wireless sensor networks.

In this paper, we consider an energy harvesting sensor network where sensors are powered by reusable energy such as solar energy, wind energy, and so on, from their surroundings. We first formulate a novel monitoring quality maximization problem that aims to maximize the quality, rather than the quantity, of collected data, by incorporating spatial data correlation among sensors. An optimization framework consisting of dynamic rate weight assignment, fair data rate allocation, and flow routing for the problem is proposed. To fairly allocate sensors with optimal data rates and efficiently route sensing data to the sink, we then introduce a weighted, fair data rate allocation and flow routing problem, subject to energy budgets of sensors. Unlike the most existing work that formulated the similar problem as a linear programming (LP) and solved the LP, we develop fast approximation algorithms with provable approximation ratios through exploiting the combinatorial property of the problem. A distributed implementation of the proposed algorithm is also developed. The key ingredients in the design of algorithms include a dynamic rate weight assignment and a reduction technique to reduce the problem to a special maximum weighted concurrent flow problem, where all source nodes share the common destination. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm is very promising, and the solution to the weighted, fair data rate allocation and flow routing problem is fractional of the optimum.

ABSTRACT With the advances of more and more mobile sink deployments (e.g., robots and unmanned aerial vehicles), mobile sinks have been demonstrated to play an important role in the prolongation of network lifetime. In this paper, we consider the network lifetime maximization problem for time‐sensitive data gathering, which requires sensing data to be sent to the sink as soon as possible, subject to several constraints on the mobile sink. Because the mobile sink is powered by petrol or electricity, its maximum travel distance per tour is bounded. The mobile sink's maximum moving distance from its current location to the next must also be bounded to minimize data loss. As building a new routing tree rooted at each new location will incur an overhead on energy consumption, the mobile sink must sojourn at each chosen location at least for a certain amount of time. The problem, thus, is to find an optimal sojourn tour for the mobile sink such that the network lifetime is maximized, which is subject to a set of constraints on the mobile sink: its maximum travel distance, the maximum distance of each movement, and the minimum sojourn time at each sojourn location. In this paper, we first formulate this novel multiple‐constrained optimization problem as the distance‐constrained mobile sink problem for time‐sensitive data gathering. We then devise a novel heuristic for it. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the performance of the proposed algorithm is very promising, and the solution obtained is fractional of the optimal one. Copyright © 2011 John Wiley & Sons, Ltd.

In this paper we investigate the network lifetime maximization problem in a delay-tolerant wireless sensor network with a mobile sink by exploiting a nontrivial tradeoff between the network lifetime and the data delivery delay. We formulate the problem as a joint optimization problem that consists of finding a trajectory for the mobile sink and designing an energy-efficient routing protocol to route sensing data to the sink, subject to the bounded delay on data delivery and the given potential sink location space. Due to NP-hardness of the problem, we then propose a novel optimization framework, which not only prolongs the network lifetime but also improves the other performance metrics including the network scalability, robustness, and the average delivery delay. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm against other heuristics. The experimental results demonstrate that the proposed algorithm outperforms the others significantly in terms of network lifetime prolongation.

In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e. g., social network analysis, bioinformatics, web link research. Compared with other explicit structures for modeling vertex clusters, such as quasi-clique, k-core, which only set the requirement on vertex degrees, k-edge-connected subgraph further requires high connectivity within a subgraph (a stronger requirement), and hence defines a more closely related vertex cluster.

In this paper we consider data collection in an energy harvesting sensor network with a mobile sink, where a mobile sink travels along a trajectory for data collection subject to a specified tolerant delay constraint T. The problem is to find an optimal close trajectory for the mobile sink that consists of sojourn locations and the sojourn time at each location such that the network throughput is maximized, assuming that the mobile sink can only collect data from one-hop sensors, for which we first show that the problem is NP-hard. We then devise novel heuristic algorithms. We finally conduct extensive experiments to evaluate the performance of the proposed algorithms. We also investigate the impact of different parameters on the performance. The experimental results demonstrate that the proposed algorithms are efficient. To the best of our knowledge, this is the first kind of work of data collection for energy harvesting sensor networks with mobile sinks.

In this paper we consider a sensor network deployed far away from the base station. Each sensor in the network is equipped with two radio interfaces: the low-power IEEE 802.15.4 radio and the high-bandwidth 3G radio. The low-power radios are used on all sensors to transmit data within the network, while the high-bandwidth radios are activated only on a subset of sensors, referred to as gateways, for sending data to the base station. We assume that not all sensors are required to transmit their sensed data to the base station, yet the base station does have a network throughput requirement. A high throughput requirement would cause more energy consumption on sensors and shorten the network lifetime. We investigate the problem of maximizing the network lifetime subject to the network throughput being guaranteed and the data delivery latency from the network to the base station being bounded. We first formulate a novel optimization problem, namely, the throughput guaranteed network lifetime maximization problem. We then devise a heuristic for it, with the key ingredients of gateway assignment technique and energy-efficient routing forest establishment strategy. We finally conduct extensive experiments through simulation to evaluate the performance of the proposed heuristic and show that it outperforms another two algorithms in terms of network lifetime.

Deployment of relay nodes to existing wireless net-works recently has received much attention since the channel capacity from sources to destinations through the cooperation of relay nodes is greatly enhanced. However, choosing appropriate relay nodes is critical to maximize the overall network performance. In this paper, we consider the assignment problem of relay nodes in a cooperative wireless network, where physical relay infrastructures and relay supporting services (relay assignment) are independently operated by different selfish entities with each being driven by its own benefit. We first formulate the problem as a repeated double auction by taking into account the benefits of all entities. Specifically, we consider a system that consists of a set of source-to-destination pairs, where the source nodes are grouped into groups and each of them is represented by a group agent. We assume that both the source nodes and the group agents seek opportunities to maximize their own benefits through various means including untruthful bidding and collusion with each other, and so on. To maximize the social benefit of the system that include the benefits of the source nodes, the relay nodes and the auctioneer, we devise an auction which we refer it to as the repeated multi-heterogeneous-item double auction with collusion resistance. We also analytically show that this auction is not only truthful but also collusion resistant. The experimental results indicate that the proposed auction is effective in collusion-resistance.

Abstract Sensor networks have been receiving significant attention due to their potential applications in environmental monitoring and surveillance domains. In this paper, we consider the design issue of sensor networks by placing a few powerful aggregate nodes into a dense sensor network such that the network lifetime is significantly prolonged when performing data gathering. Specifically, givenKaggregate nodes and a dense sensor network consisting ofnsensors withK≪n, the problem is to place theKaggregate nodes into the network such that the lifetime of the resulting network is maximized, subject to the distortion constraints that both the maximum transmission range of an aggregate node and the maximum transmission delay between an aggregate node and its covered sensor are met. This problem is a joint optimization problem of aggregate node placement and the communication structure, which is NP‐hard. In this paper, we first give a non‐linear programming solution for it. We then devise a novel heuristic algorithm. We finally conduct experiments by simulation to evaluate the performance of the proposed algorithm in terms of network lifetime. The experimental results show that the proposed algorithm outperforms a commonly used uniform placement schema — equal distance placement schema significantly. Copyright © 2010 John Wiley & Sons, Ltd.

In this paper we investigate the benefits of placing optimal number of sinks for a wireless sensor network (WSN) to prolong the network lifetime, provided that the number of hops from each sensor to its nearest sink is no more than h ≥ 1 and the sink location space is given in advance. We first formulate this problem as a joint optimization problem, which consists of finding the optimal number of sinks for placement and devising an energy-efficient routing protocol for data collection. Due to the NP-hardness of the problem, we then propose a novel heuristic by decomposing the problem into two sub-problems and solving them separately. As a result, the proposed optimization framework improves network performance from several aspects, including the network lifetime prolongation, network scalability improvement, and the average data delivery delay reduction. Fur thermore, it also enhances the network robustness substantially, since the sensing data generated by all sensors will be collected by multiple deployed sinks regardless of the network connectivity. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm outperforms another popular heuristic significantly in terms of network lifetime prolongation.

Existing literature in Cooperative Cognitive Radio Networks (CCRNs) always assumed a scenario where only one Primary User (PU) and several Secondary Users (SUs) coexist. However, in practice, multi-PUs and multi-SUs always coexist and the number of SUs is usually greater than that of PUs. Under such complex yet real scenarios, we assume that each PU not only allows a set of SUs to access its pre-allocated channel, but can leverage some of these SUs to improve its transmission rate via cooperative technologies. We consider a joint channel allocation and cooperation set partition problem in CCRNs, in which we aim to allocate a channel and assign a cooperation set that consists of several SUs for each PU, such that for a given period of time, the average transmission rates gained by all the users achieve maximum proportional fairness. We formulate the problem as a 0-1 non-linear programming model. Due to its NP-hardness, we propose a suboptimal Centralized Genetic Algorithm (CGA) for the problem. Extensive simulations demonstrate that CGA not only converges rapidly, but is shown to perform as well as 92% of the optimal solution delivered by brutal search, in terms of the fitness that reflects the fairness degree of the transmission performance gained by all the users.

In this paper we deal with the network lifetime maximization problem under multiple mobile sink environments, namely, the h-hop-constrained multiple mobile sink problem, which is defined as follows. Given a stationary sensor network with K mobile sinks that traverse and sojourn in a given space of locations in the monitoring area, assume that the total travel distance of each sink is bounded by a given value L and the maximum number of hops from each sensor to a sink is bounded by an integer h ≥ 1, the problem is to find an optimal trajectory for each mobile sink and determine the sojourn time at each sojourn location in the trajectory such that the network lifetime is maximized. We first formulate this problem as a joint optimization problem consisting of finding an optimal trajectory and determining the sojourn time at each chosen location. We then show that the problem is NP-hard. We instead devise a novel three-stage heuristic, which consists of calculating the sojourn time profile at each potential sojourn location, finding a high-quality trajectory for each mobile sink, and determining the actual sojourn time at each sojourn location. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm in terms of network lifetime. We also investigate the impact of constraint parameters on the network lifetime. The experimental results demonstrate that the performance of the proposed heuristic is highly comparable to the optimal one, and the ratios of network lifetime of the proposed algorithm to the optimal network lifetime are ranged from 56% to 93%.

The exploitation of sink mobility has been proven to improve various network performance significantly, including network lifetime, data delivery latency, network connectivity, and so on. In this paper we consider a novel network model consisting of sensors, gateways, and a mobile sink, which can be applied to many realistic applications such as city traffic monitoring, patients monitoring, and forest fire surveillance. We assume that there is a roadmap in the monitoring region for the mobile sink to access, and gateways are located on roads. The mobile sink moves at a constant speed along a closed tour of roads to collect data from gateways. The travelling distance of the mobile sink per tour is bounded by a given value. Due to the limited communication time between the sink and each gateway, sometimes it is not possible for the mobile sink to collect the data generated from all sensors, consequently causing monitoring quality loss. In this paper, we study the problem by formulating it to find a closed tour for the mobile sink, such that the monitoring quality loss is minimized, subject to the tour length constraint. Since the problem is NP-hard, we propose a heuristic for it. Also, we design an energy-efficient routing protocol for data collection that balances the energy consumption among sensors. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed schemes. The experiment results show the effectiveness of the proposed heuristic to optimize the network performance.

Technological advances have enabled the deployment of large-scale sensor networks for environmental monitoring and surveillance purposes. The large volume of data generated by sensors needs to be processed to respond to the users queries. However, efficient processing of queries in sensor networks poses great challenges due to the unique characteristics imposed on sensor networks including slow processing capability, limited storage, and energy-limited batteries, etc. Among various queries, top-k query is one of the fundamental operators in many applications of wireless sensor networks for phenomenon monitoring. In this paper we focus on evaluating top-k queries in an energy-efficient manner such that the network lifetime is maximized. To achieve that, we devise a scalable, filter-based localized evaluation algorithm for top-k query evaluation, which is able to filter out as many unlikely top-k results as possible within the network from transmission. We also conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm on real datasets. The experimental results show that the proposed algorithm outperforms existing algorithms significantly in network lifetime prolongation.

In this paper we explore the mobility of a mobile sink in a wireless sensor network (WSN) to prolong the network lifetime. Since the mechanical movement of mobile sink is driven by petrol and/or electricity, the total travel distance of the mobile sink should be bounded. To minimize the data loss during the transition of the mobile sink from its current location to its next location, its moving distance must be restricted. Also, considering the overhead on a routing tree construction at each sojourn location of the mobile sink, it is required that the mobile sink sojourns for at least a certain amount of time at each of its sojourn locations. The distance constrained mobile sink problem in a WSN is to find an optimal sojourn tour for the mobile sink such that the sum of sojourn times in the tour is maximized, subject to the above mentioned constraints. In this paper we first formulate the problem as a mixed integer linear programming (MILP). Due to its NP-hardness, we then devise a novel heuristic for it. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm in terms of network lifetime. The experimental results demonstrate that the solution delivered by the proposed heuristic is nearly optimal which is comparable with the one by solving the MILP formulation but with much shorter running time.

The rapid growth in micro-electronics technology and research in wireless sensor networks (WSNs) has made it possible to realize multimedia delivery on wireless multimedia sensor networks (WMSNs), consisting of tiny sensing devices. The volume and characteristics of multimedia data produced by WMSNs is quite different from the scalar data generated by conventional WSNs. This has raised the need to explore efficient routing protocols for multimedia data delivery in WMSNs, particularly supporting stringent quality of service (QoS). In this paper, we propose a novel cross-layer framework for QoS support in WMSNs, which optimizes the functionalities of communication protocols to maximize the number of video stream requests to be delivered while the imposed distortion constraint on the streams are met. QoS requirements are mapped on joint operations of application, network, MAC and link layers of the underlying communication framework. The experimental results demonstrate that the proposed framework achieves its objective efficiently.

Existing studies on the design of routing protocols for wireless ad hoc networks mainly focused on energy efficiency. However, in many real-time applications such as target tracking and bush fire surveillance, latency is an important concern, and little attention has been paid to it in the design of routing protocols for such applications to meet the specified Quality of Service (QoS) requirements like the end-to-end latency constraint. In this paper we propose an energy-aware, opportunistic routing protocol EARTOR for requests with QoS constraints, through striking the elegant balance between the energy consumption and the end-to-end latency. Our objective is to maximize the number of requests realized when dealing with a sequence of requests arrived one by one. The core techniques adopted include the cross-layer design that incorporates the duty cycle, a bidding mechanism for each relay candidate that takes its residual energy, location information, and relay priority into consideration. We finally conduct experiments by simulations to evaluate the performance of the proposed protocol against existing ones, in terms of the dynamic delivery ratio and the network capacity. The experimental results demonstrated that the proposed protocol outperforms the state-of-the-art protocols significantly.

Wireless ad hoc networks consist of hundreds to thousands of mobile nodes that are powered by batteries. To prolong the network operational time, energy conservation in such networks is of paramount importance. Energy optimization thus is one major objective in the design of routing protocols. However, in some stringent real-time applications including target tracking and bushfire surveillance, latency is an important concern, and little attention has been paid to it in the design of routing protocols for such applications to meet the specified Quality of Service (QoS) requirements like the end-to-end latency constraint. In this paper we focus on online energy-aware routing protocol design for routing requests to meet various end-to-end latency constraints under the multi-rate environment, we aim to maximize the network lifetime through striking the right balance among the node's transmission rate, the end-to-end latency, and energy consumption. Specifically, due to the NP-hardness of the problem of concern, we propose a joint optimization framework consisting of finding a routing path and assigning a specific transmission rate at each node in the path for each request such that the total energy consumption is minimized. We also devise novel heuristic algorithms for the problem, based on different energy cost metrics. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms in terms of network lifetime. The experimental results show that the proposed algorithm incorporating the energy utilization ratio of the residual energy of a node to its initial energy capacity into the cost metric outperforms the others significantly.

Motivated by many applications, top-k query is a fundamental operation in modern database systems. Technological advances have enabled the deployment of large-scale sensor networks for environmental monitoring and surveillance purposes, efficient processing of top-k query in such networks poses great challenges due to the unique characteristics of sensors and a vast amount of data generated by sensor networks. In this paper, we first introduce the concept of time interval top-k query that is to return k highest sensed values from the sensory data generated within a specified time interval. We then propose a filter-based algorithm for time interval top-k query evaluation, which is capable to filter out nearly a half unlikely top-k data from transmission in comparison with a well known existing solution. We also develop a novel online algorithm for answering time interval top-k queries with various ks and time intervals one by one through maintaining a materialized view that consists of historical top-k query results. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on real sensory datasets The experimental results show that the proposed algorithms outperform existing algorithms significantly to prolong the network lifetime.

Skyline query has been received much attention due to its wide application backgrounds for multi-preference and decision making. In this paper we consider skyline query evaluation and maintenance in wireless sensor networks. We devise an evaluation algorithm for finding skyline points progressively and a maintenance algorithm for skyline maintenance incrementally. We also conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on various datasets. The experimental results show that the proposed algorithms significantly outperform existing algorithms in terms of network lifetime prolongation.

Prolonging network lifetime is one of the most important design objectives in energy-constrained wireless sensor net-works (WSNs). Using a mobile instead of a static base sta-tion (BS) to reduce or alleviate the non-uniform energy con-sumption among sensor nodes is an efficient mechanism to prolong the network lifetime. In this paper, we deal with the problem of prolonging network lifetime in data gathering by employing a mobile BS. To achieve that, we devise a novel clustering-based heuristic algorithm for finding a trajectory of the mobile BS that strikes the trade-off between the traf-fic load among sensor nodes and the tour time constraint of the mobile BS. We also conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results show that the use of clustering in con-junction with a mobile BS for data gathering can prolong network lifetime significantly.

With the further development of sensor techniques in wireless sensor networks (WSNs), it is becoming urgent that they should be able to support complicated queries like skyline query for multi-preference and decision making. In this paper, we consider skyline query evaluation in WSNs by devising evaluation algorithms for finding skyline points on a dataset progressively. The core techniques adopted are to partition the dataset into several disjoint subsets and output the skyline points by examining each subsequent subset progressively, using some of the skyline points obtained so far to filter out those unlikely skyline points in the current processing subset from transmission. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on synthetic and real datasets. The experimental results show that the proposed algorithms outperform existing algorithms significantly in network lifetime prolongation.

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.

The skyline query, as an important operator in databases for multi-preference analysis and decision making, has received much attention recently due to its wide application backgrounds. In this paper, we consider the skyline query problem in Wireless Sensor Network with an objective to maximize the network lifetime by proposing filter-based distributed algorithms for skyline evaluation and maintenance. We also conduct preliminary experiments to evaluate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms significantly outperform existing algorithms on various datasets.

Existing solutions for top-k queries in wireless sensor networks mainly focused on energy efficiency and little attention has been paid to the response time to answer a top-k query as well as the relationship between the response time and the network lifetime. In this paper we address this issue explicitly by studying the top-k query problem in sensor networks with the response time constraint. We aim at finding an energy-efficient routing tree and devising an evaluation algorithm for top-k queries on the tree such that the network lifetime is significantly prolonged, provided that the query response time constraint is met too. To do so, we propose a novel joint optimization framework of finding a routing tree and devising a filter-based evaluation algorithm on the tree. We also conduct extensive experiments by simulation to evaluate the performance of the proposed algorithms. The experimental results showed that the joint optimization framework prolongs the network lifetime significantly under a given response time constraint.

In this paper we deal with online broadcasting and multicasting in a WDM optical network with shared light splitter bank. Our objective is to maximize the network throughput. Since light splitting and wavelength conversion switching in WDM optical networks is cost expensive and fabrication difficult, we assume that only a fraction of network nodes are equipped with limited number of light splitting and/or wavelength conversion switches, and they are shared by all incoming and outgoing signals at each installed node. We first propose two cost models of realizing a broadcast or multicast request to model the consumption of network resources, particularly in modelling the light splitting and/or wavelength conversion resources consumption. We then show that under either of the two proposed cost models, finding a cost-optimal broadcast or multicast tree for a broadcast or multicast request is NP-complete, and instead devise approximation and heuristic algorithms for it. We finally conduct experiments to evaluate the performance of the proposed algorithms.

Energy-constrained sensor networks have been deployed widely for monitoring and surveillance purposes. Data gathering in such networks is often a prevalent operation. Since sensors have significant power constraints (battery life), energy efficient methods must be employed for data gathering to prolong network lifetime. We consider an online data gathering problem in sensor networks, which is stated as follows: assume that there is a sequence of data gathering queries, which arrive one by one. To respond to each query as it arrives, the system builds a routing tree for it. Within the tree, the volume of the data transmitted by each internal node depends on not only the volume of sensed data by the node itself, but also the volume of data received from its children. The objective is to maximize the network lifetime without any knowledge of future query arrivals and generation rates. In other words, the objective is to maximize the number of data gathering queries answered until the first node in the network fails. For the problem of concern, in this paper, we first present a generic cost model of energy consumption for data gathering queries if a routing tree is used for the query evaluation. We then show the problem to be NP-complete and propose several heuristic algorithms for it. We finally conduct experiments by simulation to evaluate the performance of the proposed algorithms in terms of network lifetime delivered. The experimental results show that, among the proposed algorithms, one algorithm that takes into account both the residual energy and the volume of data at each sensor node significantly outperforms the others

In this paper we study the end-to-end delay constrained traffic grooming problem in WDM ring networks. Our aim is to incorporate quality of service (QoS) routing constraints into traffic grooming and address them jointly with the objective of maximizing the network throughput. It is well known that many real-time multimedia traffic not only make use of a fraction of the total wavelength capacity, but also have stringent end-to-end delay requirements. Consequently, while provisioning delay-bounded sub-wavelength traffic, it is of paramount importance to take traffic grooming and QoS routing constraints into consideration simultaneously to reduce the total network cost and improve the overall network performance. In this paper we first present an integer linear program (ILP) formulation for the problem, which is applicable when the problem size is small. We then propose three scalable heuristic algorithms. We finally conduct experiments by simulation to evaluate the performance of the proposed algorithms. The experimental results show that, among the three proposed heuristics, the one based on ILP relaxation offers the best performance

A wireless ad hoc network consists of mobile nodes that are equipped with energy-limited batteries. As mobile nodes are battery-operated, an important issue in such a network is to minimize the total power consumption for each operation. Multicast is one of fundamental operations in any modern telecommunication network including wireless ad hoc networks. Given a multicast request consisting of a source node and a set of destination nodes, the problem is to build a minimum-energy multicast tree for the request such that the total transmission power consumption in the tree is minimized. Since the problem in a symmetric wireless ad hoc network is NP-complete, we instead devise an approximation algorithm with provable approximation guarantee. The approximation of the solution delivered by the proposed algorithm is within a constant factor of the best-possible approximation achievable unless P = NP.

In this paper, we present new algorithms for online multicast routing in ad hoc networks where nodes are energy-constrained. The objective is to maximize the total amount of multicast message data routed successfully over the network without any knowledge of future multicast request arrivals and generation rates. Specifically, we first propose an online algorithm for the problem based on an exponential function of energy utilization at each node. The competitive ratio of the proposed algorithm is analyzed if admission control of multicast requests is permitted. We then provide another online algorithm for the problem, which is based on minimizing transmission energy consumption for each multicast request and guaranteeing that the local network lifetime is no less than \gamma times of the optimum, where \gamma is constant with 0 < \gamma\leq 1. We finally conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and transmission energy consumption for each multicast request. The experimental results clearly indicate that, for online multicast routing in ad hoc wireless networks, the network capacity is proportional to the network lifetime if the transmission energy consumption for each multicast request is at the same time minimized. This is in contrast to the implication by Kar et al. that the network lifetime is proportional to the network capacity when they considered the online unicast routing by devising an algorithm based on the exponential function of energy utilization at each node.

Most mobile nodes in a wireless ad hoc network are powered by energy limited batteries; the limited battery lifetime imposes a constraint on the network performance. Therefore, energy efficiency is of paramount importance in the design of routing protocols for the applications in such a network, and efficient operations are critical to enhance the network lifetime. In this paper we consider energy-efficient routing for minimizing energy and maximizing the network lifetime multicast problem in ad hoc networks. We aim to construct a multicast tree rooted at the source and spanning the destination nodes such that the minimum residual battery energy (also referred to the network lifetime) among the nodes in the network is maximized and the total transmission energy consumption is minimized. Due to the NP-hardness of the concerned problem, all previously proposed algorithms for it are heuristic algorithms, and there is little known about the analytical performance of these algorithms in terms of approximation ratios. We here focus on devising approximation algorithms for the problem with provably guaranteed approximation ratios. Specifically, we present an approximation algorithm for finding a multicast tree such that the total transmission energy consumption is no more than /spl gamma/ times the optimum, under the constraint that the network lifetime is no less than /spl beta/ times the optimum, where /spl gamma/ is either 4 ln K or O (K/sup /spl epsiv//), depending on whether the network is symmetric or not, /spl epsiv/ and /spl beta/ are constants with 0 < /spl epsi/, /spl beta/ /spl les/ 1, and K is the number of destination nodes in a multicast session.

This paper considers the problem of on-line multicast routing in WDM grooming optical mesh networks without wavelength conversion capability. In such networks, provisioning of connection requests with fractional wavelength capacity requirements is achieved by dividing a wavelength into multiple time slots and multiplexing traffic on the wavelength. We present an on-line multicast traffic grooming algorithm for the concerned problem. The objective is to efficiently route multicast requests with sub-wavelength capacity requirements onto high-capacity wavelengths, and balance the load on the links in the network at the same time. To do so, we propose a cost function, which not only encourages grooming new requests onto the wavelengths that are being used by existing traffic, but also performs load balancing by intelligently increasing the cost of using wavelengths on links. The performance results obtained by experiments on a representative sized mesh network show that the proposed algorithm outperforms the other existing algorithms.

Recent advances in microelectronic technology have made it possible to construct compact and inexpensive wireless sensors. Sensor networks have received significant attention due to their potential applications from civil to military domains. Since sensors in sensor networks are equipped with energy-limited batteries, energy conservation in such networks is of paramount importance in order to prolong the network lifetime. Sensing coverage and sensor connectivity in sensor networks are two fundamental issues, which have been extensively addressed in the literature, and most existing work on sensing coverage has focused on the (connected) full coverage problem that aims to cover the entire monitored region using the minimum number of sensors. However, in some application scenarios, full coverage is either impossible or unnecessary and a partial coverage with a certain degree guarantee is acceptable. In this paper, we study the connected coverage problem with a given coverage guarantee. We first introduce the partial coverage concept and analyze its properties for the first time in order to prolong the network lifetime. Due to NP-hardness of the concerned problem, we then present a heuristic algorithm which takes into account the partial coverage and sensor connectivity simultaneously. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm.

This paper considers the on-line traffic grooming problem in WDM-TDM switched optical mesh networks without wavelength conversion capability. The objective is to efficiently route connection requests with fractional wavelength capacity requirements onto high-capacity wavelengths and balance the load on the links in the network at the same time. To do so, we propose a cost function, which not only encourages grooming new connection requests onto the wavelengths that are being used by existing traffic, but also performs load balancing by intelligently increasing the cost of using wavelengths on links. The performance results obtained by experiments on a representative sized mesh network show that the proposed algorithm outperforms the existing algorithms.

In this paper we consider on-line disjoint path routing in energy-constrained ad hoc networks. The objective is to maximize the network capacity, i.e., maximize the number of messages routed successfully by the network without any knowledge of future disjoint path connection request arrivals and generation rates. We first present two on-line algorithms for the problem. One is based on maximizing the network lifetime and the other is based on an exponential function of energy utilization at nodes. We then conduct extensive experiments by simulations to analyze the performance of the proposed algorithms. The experimental results show that the proposed algorithms outperform those existing algorithms that do not take into account the power load balancing among the nodes.

Abstract We consider the problem of minimizing the number of wavelengths needed to connect a given multicast set in a multihop WDM optical network. This problem was introduced and studied by Li et al. (Networks, 35(4), 260–265, 2000) who showed that it is NP‐complete. They also presented an approximation algorithm for which they claimed an approximation ratio ofc(1 + 2 log Δ), wherecis the maximum number of connected components in the subgraph induced by any wavelength and Δ is the maximum number of nodes in any connected component induced by any wavelength. In this article we present an example demonstrating that their claim cannot be correct—the approximation ratio is Ω(n), even though the subgraph induced by every wavelength is connected, wherenis the number of nodes in the network. In fact, we show that the problem cannot be approximated withinO(2 ) unlessNP⊆DTIME(npoly log n) for any constant ε > 0, wheremis the number of edges in the network. We complement this hardness result by presenting a polynomial–time algorithm with an approximation ratio of (1 + ln 3 + 2 log Δ) when the subgraph induced by every wavelength is connected, and an approximation ratio of$O(\sqrt{(n \, {\rm log} \, \Delta)/{\rm opt})}$ in the general case, whereoptis the number of wavelengths used in an optimal solution and 1 ≤opt≤n− 1. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 42–48 2005

We consider wavelength rerouting for on-line multicast in all-optical wavelength division multiplexing (WDM) networks where the multicast requests arrive and depart randomly. One limitation of such networks is the wavelength continuity constraint, imposed by the all-optical cross-connect switches, that requires the same wavelength be used on all the links in a multicast tree. With random arrivals and departures of multicast requests, it happens quite often that a new multicast request has to be blocked due to the fact that there are not enough available resources (e.g., wavelengths) to realize the request. Wavelength rerouting, a viable and cost-effective method, has been proposed to improve the blocking probability; it rearranges the wavelengths on certain existing multicast routes to free a wavelength continuous route for the new request. We study the wavelength rerouting problem for on-line multicast in both undirected and directed WDM networks with an objective to minimize the disruption incurred to the existing multicast services, or equivalently, to minimize the number of existing multicast routes to be wavelength-rerouted. We first show that the problem is not only NP-hard but also hard to approximate. We then devise approximation algorithms for it with provable approximation guarantees.

In this paper we assume that a multihop wireless network (also called a wireless ad hoc network) consists of nodes whose transmitting powers are finitely adjustable. We con-sider two fundamental problems related to power consump-tion in this kind of network. One is the minimum-energy broadcast tree problem, which broadcasts a message from a source node to all the other nodes in the network such that the summation of transmission powers at all nodes is min-imized; and another is the minimum-energy multicast tree problem, which multicasts a message from a source node to the nodes in a given subset of nodes such that the sum-mation of the transmission powers at all involved nodes is minimized. We first show the minimum-energy broadcast tree prob-lem is NP-complete. We then present an approximate al-gorithm for the problem in a general setting, which delivers an approximate solution with a bounded performance guar-antee. The algorithm takes O((k + 1)1/n3/) time, where n is the number of nodes in the wireless network, k is the number of power levels at each node, and is constant with 0 < ≤ 1. For a special case of the problem where every node is equipped with the same type of battery, we pro-pose an approximate algorithm which has a better perfor-mance ratio than that in the general case setting, and the algorithm takes O(kn2 log n) time. We finally extend the technique for the minimum-energy broadcast tree problem to solve the minimum-energy multicast tree problem, which leads to a similar result. The technique adopted in this pa-per is to reduce the minimum-energy broadcast (multicast) tree problem on a wireless ad hoc network to an optimiza-tion problem on an auxiliary weighted graph, and solve the optimization problem on the auxiliary graph which in turn gives an approximate solution for the original problem.

This paper considers the problem of establishing robust routes for user connection requests in an WDM network dynamically. The problem is to find two edge-disjoint routes with satisfying certain given properties. One route will serve as the primary path, and another will serve as the backup path which will replace the primary path if there is any link failure in the primary path. Two versions of the problem are studied: one is to find two edge-disjoint paths such that the total cost of the two paths is minimized, in terms of the network resources consumption; the other is to find two edge-disjoint paths to minimize both the network load (link congestion) and the total cost of the two paths. The exact and approximate algorithms for the problem are proposed, and the solutions delivered consist of selecting routes, assigning wavelengths to the links, and setting switches of wavelength conversion at intermediate nodes on the routes. The performance ratio between the approximate solution and the exact solution is also analyzed. The key technique used in the design of the approximate algorithms, is to transform the corresponding version into a well solved optimization problem on an auxiliary graph. To the best of our knowledge, this is the first time that in the design of routing protocols for WDM networks, the network load and the route finding and wavelength assignment are taken into account simultaneously. As results, it not only finds cheap routes but also reduces the number of network re-configurations, thereby improving the performance of the network through utilizing its resources effectively.

Given a graph G=(V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of G in the parallel setting for k=2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: (1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n/sup 3/4/) processors per update and query. (2) It is shown that the biconnectivity problem can be solved in O(log/sup 2 n/) time using O(n/spl alpha/(2n, n)/logn) processors per update and O(1) time with a single processor per query or in O(log n log/sub n///sup m/) time using O(n/spl alpha/(2n, n)/log n) processors per update and O(logn) time using O(n/spl alpha/(2n, n)/logn) processors per query, where /spl alpha/(.,.) is the inverse of Ackermann's function. (3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log/sub n///sup m/+logn log log n//spl alpha/(3n, n)) time using O(n/spl alpha/(3n, n)/log n) processors per update and O(1) time with a single processor per query. (4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to /spl Omega/(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n/sup 3/4/) processors. All the proposed algorithms run on a CRCW PRAM.

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k/sup 2/n+km+kn log(kn)), where n and m are the number of nodes and links in the network, and k is the number of wavelengths. We then analyze that the proposed algorithm requires O(d/sup 2/nk/sub 0//sup 2/+mk/sub 0/ log n) time for a restricted version of the problem in which the number of available wavelengths for each link is bounded by k/sub 0/ and k/sub 0/=o(n), where d is the maximum in-degree or out-degree of the network. It is surprising to have found that the time complexity for this case is independent of k. It must be mentioned that our algorithm can be implemented efficiently in the distributed computing environment. The distributed version requires O(kn) time and O(km) messages. Compared with a previous O(k/sup 2/n+kn/sup 2/) time algorithm, our algorithm has the following advantages. (1) We take into account the physical topology of the network which makes our algorithm outperform the previous algorithm. In particular, when k is small [e.g., k=O(log n)] and m=O(n), our algorithm runs in time O(n log/sup 2/ n), while the previous algorithm runs in time O(n log n). (2) Since our algorithm has high locality, it can be implemented on the network distributively.

A data warehouse collects and maintains a large amount of data from multiple distributed and autonomous data sources. Often the data in it is stored in the form of materialized views in order to provide fast access to the integrated data. However, maintaining a certain level consistency of warehouse data with the source data is challenging in a distributed multiple source environment. Transactions containing multiple updates at one or more sources further complicate the consistency issue.

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. We first present fast, efficient algorithms both for the general problem and for a natural restricted version. The new algorithms outperform earlier work, providing time improvements amounting to an almost linear time factor in most cases. Also, all our algorithms can be implemented on the network in a distributed way.

Computing multiple related group-by aggregates is one of the core operations of online analytical processing (OLAP) applications. This kind of computation involves a huge volume of data operations (megabytes or treabytes). The response time for such applications is crucial, so, using parallel processing techniques to handle such computation is inevitable. We present several parallel algorithms for computing a collection of group-by aggregates based on a multiprocessor system with shared disks. We focus on a special case of the aggregation problem-"Cube" operator which computes group-by aggregates over all possible combinations of a list of attributes. The proposed algorithms introduce a novel processor scheduling policy and a non-trivial decomposition approach for the problem in the parallel environment. Particularly, the hybrid algorithm has the best performance potential among the four proposed algorithms. All the proposed algorithms are scalable.

Mesh is one of the most commonly used interconnection networks and, therefore, embedding between different meshes becomes a basic embedding problem. Not only does an efficient embedding between meshes allow one mesh-connected computing system to efficiently simulate another, but it also provides a useful tool for solving other embedding problems. The authors study how to embed an s/sub 1//spl times/t/sub 1/ mesh into an s/sub 2//spl times/t/sub 2/ mesh, where s/sub i//spl les/t/sub i/ (i=1, 2), s/sub 1//spl les/t/sub 1/=s/sub 2/t/sub 2/, such that the minimum dilation and congestion can be achieved. First, they present a lower bound on the dilations and congestions of such embeddings for different cases. Then, they propose an embedding with dilation [s/sub 1//s/sub 2/]+2 and congestion [s/sub 1//s/sub 2/]+4 for the case s/sub 2//spl ges/s/sub 2/, both of which almost match the lower bound [s/sub 1//s/sub 2/]. Finally, for the case s/sub 1/

It is difficult to partition an arbitrary permutation into a minimum number of groups such that conflict-free paths for all source-destination pairs in each group can be established on an omega network. Based on linear algebra theory, this paper presents an optimal algorithm which solves this problem for the LC class of permutations on a large class of multi-stage networks. This algorithm extends the previous result which deals with the BPC class of permutations on the omega network.