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

With the popularity of federated learning, federated domain generalization (FedDG) has attracted more and more attention. Existing works of federated learning indicate that the generalization performance of the global model can be improved when the global model is obtained by aggregating local models according to suitable weights. However, existing methods to calculate weights do not fully utilize the data influences on the global model update, which gives us an opportunity to improve the generalization performance of the global model further. In this paper, we propose the method DI (data influences), which utilizes data influences on the global model update to calculate dynamical weights of local model in each round of training. Specifically, the first component data influence calculator (DIC) of DI calculates local weights of local model from the influences of data on the global model update and we introduce the influence function to complete the calculation process. The second component data influence adjuster (DIA) of DI calculates global weights (which are used in the aggregation process of the global model) from local weights. Extensive experiments indicate that our method improves the generalization performance of models significantly. In particular, our method improves model accuracy on benchmark datasets PACS, OfficeHome, and Office-31 by 1.79%, 1.61%, and 2.39% on average, respectively. Source code is publicly available at github-https://github.com/zikunZHOUHH/Fed-DI.

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

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

Skin diseases are one of the most common diseases worldwide, and the mismatch between skin disease patients and dermatologists leads to a huge waste of healthcare resources. Accurately matching skin disease patients to appropriate dermatologists by an image-based method of skin disease recognition can reduce the waste of healthcare resources. However, existing image-based methods of skin disease recognition do not fully utilize multi-source and multi-scale features, which leaves us the chance to improve skin disease recognition further. In this paper, we propose a fusion method of multi-source image features and multi-scale image features to improve skin disease recognition. First, we design a fusion module of multi-source image features to integrate multi-source image information. By dual Convolutional Block Attention Module (CBAM) blocks, the fusion module of multi-source image features enhances the feature representation of key regions and then obtains a comprehensive representation of skin diseases. Second, we propose a fusion module of multi-scale image features. By two parallel backbone networks, the fusion module of multi-scale image features can extract deep feature representations from different scales and exploit their complementarity. To validate the effectiveness of our method, we conduct extensive experiments. The experiment results demonstrate that our method outperforms the state-of-the-art method, achieving improvements of 6.30%, 12.52%, 10.85%, 12.16%, and 5.06% in accuracy, precision, recall, F1-score, and AUC, respectively.

Recently, deploying static directional chargers to construct timely and robust Wireless Rechargeable Sensor Networks (WRSNs) has become an important research issue for solving the limited energy problem of wireless sensor networks. However, the established fixed power distribution lacks flexibility in response to dynamic charging requests from sensors and may render some sensors to be continuously impacted by destructive wave interference. This results in a gap between energy supply and practical demand, making the charging process less efficient. In this paper, we focus on the real-time sensor charging requests and formulate a dynamic power disTributIon controlling for Directional chargErs (TIDE) problem to maximize the overall charging utility. To solve the problem, we first build a charging model for directional chargers while considering wave interference and extract the candidate charging orientations from the continuous search space. Then we propose the neighbor set division method to narrow the scope of calculation. Finally, we design a dynamic power distribution controlling algorithm to update the neighbor sets timely and select optimal orientations for chargers. Extensive simulations and field experiments are conducted to evaluate the performance of our solution. The results demonstrate the effectiveness and efficiency of the proposed scheme, it outperforms the comparison algorithms by 132.09% on average.

In the field of class-agnostic counting (CAC), counting only objects of interest that are similar to exemplars in multi-class scenarios has been a challenging task. To address this challenge, recent research has proposed the extract-and-match paradigm based on the vision transformer (ViT) architecture. However, although this paradigm can improve the accuracy of exemplar-similar object identification, it overly emphasizes the role of the ViT structure. To address this shortcoming, this work introduces a more generalized prompt-before-extract paradigm on top of the extract-and-match paradigm and designs a pure convolutional neural network (CNN) model named PBECount. In addition, an innovative loss function, a post-processing strategy, and a dynamic threshold method are proposed to enhance the detection performance of the proposed model when the probability maps are used as ground truth during model training. The experimental results on the FSC-147 and CARPK datasets demonstrate that the proposed PBECount can identify whether unknown class objects are similar to exemplars and outperform the state-of-the-art CAC methods in terms of accuracy and generalization.

With the popularity of federated learning, federated domain generalization (FedDG) has attracted more and more attentions. Existing works of federated learning indicate that the generalization performance of the global model can be improved when the global model is obtained by aggregating local models according to a suitable weights. However, the existing methods to calculate weights do not fully utilize the data influences on the global model update, which gives us an opportunity to improve the generalization performance of the global model further. In this paper, we propose the method DI (data influences), which utilizes the data influences on the global model update to calculate dynamical weights of local model in each round of training. Specifically, the first component data influences calculator (DIC) of DI calculates the local weights of local model from the influences of each data on the global model update and we introduce the influences function to complete the calculation process. The second component data influences adjuster (DIA) of DI calculates the global weights (which are used in the aggregation process of the global model) from local weights. Extensive experiments indicate that our method improves the generalization performance of models significantly. In particular, our method improves model accuracy on benchmark datasets PACS, OfficeHome, and Office-31 by 1.79%, 1.61%, and 2.39% on average, respectively. Source code is publicly available at github.

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

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

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

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

Recently, Wireless Rechargeable Sensor Networks (WRSNs) have emerged as a promising solution to address the energy limitations of wireless sensor networks. In practical applications of WRSNs, environmental objects are ubiquitous, reflecting radio waves and causing them to reach sensors via multiple paths. These multipath effects significantly impact the power intensity received by sensors. In this paper, we study a fundamental issue of charGing schEduling with mulTipath effectS (GETS), that is, how to schedule a mobile charger by comprehensively considering the multipath effects to maximize the overall charging utility. To this end, we first establish a charging model with environmental objects to investigate the impact of multipath effects on power distribution. Then, we propose a charging scheduling scheme that not only selects a series of sojourn locations for the MC (Mobile Charger) to maximize the total power received by nearby sensors but also construct a charging path that avoids environmental objects. We conduct extensive simulations as well as indoor and outdoor field experiments to evaluate the performance of our scheme. The results demonstrate that, on average, our scheme outperforms baseline algorithms by 48.87%

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

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.

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.

Accurately forecasting long-term future wind power is critical to achieve safe power grid integration. This problem is quite challenging due to wind power's high volatility and randomness. In this paper, we propose a novel time series forecasting method, namely Deep Conditional Generative Spatio-Temporal model (DCGST), and its high accuracy is achieved by tackling two critical issues simultaneously: a proper handling of the non-stationarity of multiple wind power time series, and a fine-grained modeling of their complicated yet dynamic spatio-temporal dependencies. Specifically, we first formally define theSpatio-Temporal Concept Drift(STCD) problem of wind power, and then we propose a novel deep conditional generative model to learn probabilistic distributions of future wind power values under STCD. Three different tailored neural networks are designed for distributions parameterization, including a graph-based prior network, an attention-based recognition network, and a stochastic seq2seq-based generation network. They are able to encode the dynamic spatio-temporal dependencies of multiple wind power time series and infer one-to-many mappings for future wind power generation. Compared to existing methods, DCGST can learn better spatio-temporal representations of wind power data and learn better uncertainties of data distribution to generate future values. Comprehensive experiments on real-world datasets including the largest public turbine-level wind power dataset verify the effectiveness, efficiency, generality and scalability of our method.

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.

To improve the charging performance, employing multiple wireless chargers to charge sensors concurrently is an effective way. In such charging scenarios, the radio waves radiated from multiple chargers will interfere with each other. Though a few work have realized the wave interference, they do not fully utilize the high power caused by constructive interference while avoiding the negative impacts brought by the destructive interference. In this paper, we aim to investigate the power distribution regularity of concurrent charging and take full advantage of the high power to enhance the charging efficiency. Specifically, we formulate a concurrent charGing utility mAxImizatioN (GAIN) problem and build a practical charging model with wave interference. Further, we propose a concurrent charging scheme, which not only can improve the power of interference enhanced regions by deploying chargers, but also find a set of points with the highest power to locate sensors. Finally, we conduct both simulations and field experiments to evaluate the proposed scheme. The results demonstrate that our scheme outperforms the comparison algorithms by 40.48% on average.

With the popularity of artificial intelligence and cloud computing, many neural network models can be placed on the cloud server as an open service, such as Google Goggles and the online face recognition system of Baidu. The data owner sends his data to the cloud server to get the prediction result of data. Obviously, the cloud service provider can access model parameters and private data if there is no additional protection mechanism. On the one hand, if the adversary can access private data, they can freely use the artificial intelligence model and Big Data technologies to analyze the data owner. On the other hand, when the adversary can access model parameters, the interest of model owner would be harmed. Thus, preserving model parameters (model privacy) and private data (data privacy) becomes the key for applying neural network models as open cloud services. In this article, to protect the model privacy and data privacy in neural network prediction even when a cloud service provider colludes with the data owner or the model owner, we first propose a new system model with two no-colluding cloud servers and a corresponding security model. Then, we propose a new non-interactive outsourcing scheme, which can protect model privacy together with data privacy. Our scheme is able to resist collusive attacks of one server and the data owner as well as collusive attacks of one server and the model owner. At last, the security analyses indicate that our scheme just needs no collusion between cloud servers. The performance analyses indicate that our scheme is very lightweight for the data owner, and it is about tens of milliseconds for a neural network model with 1000 parameters.

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

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

Sequential Recommendation (SR) predicts the next interaction behavior via modeling the interaction between the user and the item over a time sequence. A series of works applied Self-Supervised Learning (SSL) in SR to obtain better user representations. Although these efforts proved effective, they only focused on the information of the user itself and ignores self-supervised signals from other users. Due to the widely observed homogeneity in recommender systems, these signals from other users are also vital for user representation. To this end, we propose a novel framework, Self-Supervised Learning based on Similar users for Sequential Recommendation (SSLSRec). We present a contrastive learning objective in SSLSRec to consider augmented views from the same user and similar users as positive samples. Moreover, we propose novel Insert and Substitute augmentation methods to construct more reasonable augmentation views for user sequences. Extensive experiments demonstrate the effectiveness of SSLSRec.

Identifying structural hole spanners that benefit from acting as bridges between communities is a core study in social network analysis. Existing methods for identification mainly focus on measuring the ability of users to control information propagation by bridging holes, while ignoring the impact of reinforcement of the holes themselves on the benefits of bridging spanners. A recent sociological study shows that the more reinforced a hole is, the more likely it is to bring high benefits to its spanners. In this paper, we propose a node embedding-based method ReHSe for identifying reinforced structural hole spanners in social networks. Specifically, an integrated embedding method is devised to extract features encoding reinforcement properties of nodes into a low-dimensional space. Further, to improve the robustness and accuracy of identification, an incremental learning strategy based on a reserved set is employed to train a scoring network in this subspace, to find top-k reinforced hole spanners. Extensive experimental results show that the performance of hole spanners identified by the proposed method outperforms several existing methods.

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.

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.

Conversational recommender systems model user dynamic preferences and recommend items based on multi-turn interactions. Though the conversational recommender system has achieved good performance, it has two limitations. On the one hand, researchers usually random select an anchor item from user's historical interactions to simulate the interaction with the real user, but some items in the historical interactions do not fit the user realistic preferences (item noise). On the other hand, it pays too much attention to user dynamic preferences, but nurses some static preferences that are difficult to change over a short period. In fact, when there is no explicit attribute preference in user's conversation, the user static preferences can also be used to make recommendations. To address the aforementioned issues, a novel method that combines graph path reasoning with multi-turn conversation is proposed, called Graph Path reasoning for conversational Recommendation (GPR). In GPR, a soft-clustering is designed to classify items and then set operations are utilized to filter the noise in the user's historical interactions. To capture user dynamic preferences and take account of the user inherent static preferences, GPR asks questions about attributes in the attribute-level reasoning and asks whether the items fit user static preferences in the item-level reasoning on a heterogeneous graph. In the multi-turn of two-level graph path reasoning, a reinforcement learning is used to obtain the optimal path and accurately recommend items to users. Extensive experiments conducted on two benchmark datasets verify that GPR can significantly improve recommendation performance and reduce the turn of path reasoning.

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

Attention Deficit Hyperactivity Disorder (ADHD) is a common psychiatric disorder among young children. However, there is no accurate and efficient method to diagnose ADHD up to now, due to the complexity of the pathological mechanism and clinical symptoms. This paper aims to present a spatio-temporal method for classification of ADHD and Typical Developing Children (TDC) using Resting-State functional Magnetic (rs-fMRI). To extract the most discriminative features in both space and time dimensions, 3-Dimensional Convolutional Neural Network (3D-CNN) and Gated Recurrent Unit (GRU) were respectively used to process 3D spatial and 1D temporal information in rs-fMRI. Before GRU, 1D filters with different scales were employed to capture significant features of different time intervals from temporal input. To evaluate proposed method, the 5-fold cross validation was employed using ADHD-200 global competition dataset. As a result, the average accuracy, sensitivity, specificity were 71.65 %, 68.00 % and 73.80 %, respectively. Experiment results show that our method performs better than existing methods, and our model not only has good generalization ability, but maintains a balance between sensitivity and specificity. We believe that our method can be used to build a more accurate automatic assistant diagnosis tool of ADHD.

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

The study of time series forecasting is significant and useful in a variety of scenarios. However, due to the high degree of randomness and the complex contextual factors, it remains a difficult challenge. While several works based on machine learning and deep neural network have been proposed in recent years to address these challenges, most of them mine sequence features based on discrete points and overlook the fact that shape similarity plays an important role in inferring the future values. In this paper, we propose a seq2seq model with Shape Attention and Dilated Convolution (SADC) to tackle this problem. SADC contains two important phases: (1) Embedding with multi-scale dilated convolution. We first define the shape as a set of discrete points in a fixed-length window. The features hidden in the shape are then learned using multiple dilated convolutions with different kernels. (2) Inferring with shape attention. During this phase, we first present the shape attention, which aims to provide support information for inferring future values by generating the embedding vector of each prediction window based on shape similarity. The PreNet network is then built to predict the values using the embedding vector for each prediction window. The experimental results conducted on two datasets show that the performance of SADC model outperforms the state-of-the-art models on time series forecasting.

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}$.

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

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

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

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

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

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

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

In this paper we study 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.

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.

Due to the rapid development of the sharing economy, shared bikes have become one of the most popular and convenient traveling tools in intelligent transport systems. Aiming to save the time spent on waiting for or searching bikes at bike stations, the operators of bike-sharing systems need to dynamically dispatch bikes. Predicting the number of bikes for each station can help to optimize the repository of bikes. The usage of bikes is affected by several uncertain factors, so bike number prediction becomes a challenging and difficult problem. To manage this problem, we propose an algorithm called bimodal Gaussian inhomogeneous Poisson (BGIP) to predict the number of bikes. The BGIP includes three steps. First, the inhomogeneous Poisson process is adopted to describe the process that people arrive at a bike station to pick up or return bikes. Second, the bimodal Gaussian function is used to describe the intensity function of inhomogeneous Poisson process. In order to dynamically uncover the changing trend in the usage state of bikes, we propose a method to measure the influences of external factors on the usage of bikes. Third, the number of bikes is predicted by calculating the mean usage of bikes on the basis of checking-out and checking-in sequences. Experiments demonstrated that our algorithm outperformed the baseline algorithms in solving the bike prediction problem: accurately predicting the number of bikes and determining whether there is at least one bike available at a bike station.

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.

In wireless rechargeable sensor networks (WRSNs), prior studies mainly focus on the optimization of power transfer efficiency. In this work, we consider the cost for building and operating WRSNs. In the network, sensor nodes can be charged by mobile chargers, that have limited energy which is used for charging and moving. We introduce a novel concept called “shuttling” and introduce an optimal charging algorithm, which is proven to achieve the minimum number of chargers in theory. We also point out the limitations of the optimal algorithm, which motivates the development of solutions named Push-Shuttle-Back (PSB). We formally prove that PSB achieves the minimum number of chargers and the optimal shuttling distance in a 1D scenario with negligible energy loss. When the loss in wireless charging is non-negligible, we propose to exploit detachable battery pack (DBP) and propose a DBP-PSB algorithm to avoid energy loss. We further extend the solution to 2D scenarios and introduce a new circle-based “shortcutting” scheme that improves charging efficiency and reduces the number of chargers needed to serve the sensor network. We carry out extensive simulations to demonstrate the performance of the proposed algorithms, and the results show the proposed algorithms achieve a low overall cost.

The authors of "Low-Cost Collaborative Mobile Charging for Large-Scale Wireless Sensor Networks" which appeared in August issue of this journal [ibid., vol. 16, no. 8, pp. 2213–2227, Aug. 2017] would like to correct a typo that occurred in Fig. 1. The numbers above the X axis were wrong. The corrected Fig. 1 is provided

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.

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.