Unmanned Aerial Vehicle (UAV) can be used as wireless aerial mobile base station for collecting data from sensors in UAV-based Wireless Sensor Networks (WSNs), which is crucial for providing seamless services and improving the performance in the next generation wireless networks. However, since the UAV are powered by batteries with limited energy capacity, the UAV can not complete data collection tasks of all sensors without energy replenishment when a large number of sensors are deployed over large monitoring areas. To overcome this problem, we study the Real-time Data Collection with Laser-charging UAV (RDCL) problem, where the UAV is utilized to collect data from a specified WSN and is recharged using Laser Beam Directors (LBDs). This problem aims to collect all sensory data from the WSN and transport it to the base station by optimizing the flight trajectory of UAV such that real-time data performance is ensured It has been proven that the RDCL problem is NP-hard. To address this, we initially focus on studying two sub-problems, the Trajectory Optimization of UAV for Data Collection (TODC) problem and the Charging Trajectory Optimization of UAV (CTO) problem, whose objectives are to find the optimal flight plans of UAV in the data collection areas and charging areas, respectively. Then we propose an approximation algorithm to solve each of them with the constant factor. Subsequently, we present an approximation algorithm that utilizes the solutions obtained from TODC and CTO problems to address the RDCL problem. Finally, the proposed algorithm is verified by extensive simulations.

Cyberbullying has caused serious consequences especially for social network users in recent years. However, the challenge is how to fight against the cyberbullying effectively from the algorithmic perspective. In this article, we study the fighting against the cyberbullying problem, i.e., identify an initial witness set with a budget to spread the positive influence to protect the users in a specific target set such that the number of cybervictim users in the target set being activated by the seed set of cyberbullying is minimized. We first formulate this problem and show its NP-hardness. We further prove that the objective function is submodular with respect to the size of witnesses set when we convert the original problem into the maximal version. Then we propose a stochastic approach to solve this maximal version problem based on the Reverse Sampling Technique with a constant factor guarantee. In addition, we provide theoretical analysis and discuss the relationship between the optimal value and the value returned by the proposed algorithm. To evaluate the proposed approach, we implement extensive experiments on synthetic and real datasets. The experimental results show our approach is superior to the comparison methods.

Following the recent advances in the Internet of Things (IoT), it is drawing lots of attention to design distributed algorithms for various network optimization problems under the SINR (Signal‐to‐Interference‐and‐Noise‐Ratio) interference model, such as spanner construction. Since a spanner can maintain a linear number of links while still preserving efficient routes for any pair of nodes in wireless networks, it is important to design distributed algorithms for spanners. Given a constant t > 1 as the required stretch factor, the problem of our concern is to design an efficient distributed algorithm to construct a t‐spanner of the communication graph under SINR such that the delay for the task completion is minimized, where the delay is the time interval between the time slot that the first node commences its operation to the time slot that all the nodes finish their task of constructing the t‐spanner. Our main contributions include four aspects. First, we propose a proximity range and proximity independent set (PISet) to increase the number of nodes transmitting successfully at the same time in order to reduce the delay. Second, we develop a distributed randomized algorithm SINR‐Spanner to construct a required t‐spanner with high probability. Third, the approximation ratio of SINR‐Spanner is proven to be a constant. Finally, extensive simulations are carried out to verify the effectiveness and efficiency of our proposed algorithm.

In traditional viral marketing, the goal is to reach out to the maximum number of people. However, some studies have demonstrated that spreading a product indiscriminately in a network can cause some counter effect because it may reach people who evaluate it negatively. In this paper, we study how to make use of social networks to avoid negative people so that the 'positive effect' of viral marketing can be maximized, and this optimization problem is called Strengthening the Positive Effect (SPE). SPE has a non-monotone and non-submodular objective function, and it is NP-hard to be approximately solved with any positive factor. Although SPE is almost impossible to solve approximately, we make the pioneer contribution by discovering that: 1) The almost optimal solution is obtainable in some network; 2) For the general network, a polynomial algorithm that yields a multiplicative guarantee is also possible under a reasonable assumption. We test our solution on various realworld social networks with a comprehensive set of experiments. The result affirms that besides its performance analyzability, our solution is more scalable than the current heuristic.

One significant problem in exchange networks is finding the equilibrium. To solve this problem, the concept of stable outcome has been developed. However, there are few effective methods to solve it from the point of graph theory. In this paper, we propose a minimum cost stable outcome (MCSO) problem, which is to find a stable outcome whose total transaction cost is minimized. Two algorithms have been designed to solve this problem on unit and general profit networks respectively. For unit profit networks, we use minimum cost edge cover based method to give the optimal solution. For general profit networks, we develop an approximate algorithm and prove that performance ratio is no more than twice the optimal value. Moreover, we provide the probabilistic analysis. At last, extensive experiments have been conducted on synthetic and real-life datasets. Experimental results validate the performance of the proposed algorithms.

We study the problem to maximize the profit for a social network host who offers viral marketing to multiple company campaigners. Each campaigner has its special interest for social network users, and she pays the host commission when a target user adopts her product. The campaigners decide the cost they are willing to pay for viral marketing, and the host collects cost from all campaigners and uses it for marketing. We call our optimization problem Competitive PROfit maximization for the host (CPro), and its solution is the seed allocation for campaigners, such that the profit (commission) campaigners given back to the host is maximized. CPro is NP-hard with a non-monotone and non-submodular objective function, which means existing techniques in influence or profit maximization cannot give guaranteed performance. To solve this issue, we design an efficient approximation algorithm that works on billion-scale networks, and more importantly, we give the performance bound of our algorithm. As far as we know, this is the first bounded scalable approximation algorithm for competitive profit maximization. A comprehensive set of experiments are set on various real networks with up to several billion edges from diverse disciplines, and our solution identifies the top choices for the host in only a few minutes on network that contains 1.5 billion edges.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume that all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper, by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic independent cascade and linear threshold models, respectively, which is a pioneer work. Two pricing strategies are designed, one is binary pricing (BYC), in which the seeds are offered free samples. The other is panoramic pricing (PAP), in which the seeds are offered different discounts. Furthermore, we find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. Based on this observation under PR frame, by adopting a parameter to denote the decision maker's preference toward influence and profit, we propose balanced influence and profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the nonmonotony, we show BIP objective function is submodular under certain conditions. Two unbudgeted greedy algorithms separately, named algorithm of BYC and algorithm of PAP are devised. We conduct extensive simulations on real world data sets, test the effectiveness of our proposed parameters, compare the algorithms' performances, and evaluate the superiority of our algorithms over existing ones.

Following the recent advances in drone technologies, various algorithmic optimization problems related to the effective operation of drones are drawing lots of attentions. This paper considers two interesting multiple-drone-assisted search-and-reconnaissance scenarios, in each of which, the trajectory optimization of multiple drones is of great significance to minimize the latency in the system. In the first scenario, multiple drones, whose moments of mobilization are not necessarily the same, are trying to urgently collect intelligence from a given point of interest, and we would like to minimize the task completion time, i.e., the time period between the moment that the first drone commences its operation to the moment that the intelligence from all of the points are collected, by optimizing their trajectories. In the second scenario, multiple drones with different speeds, are hovering around the same routes to regularly collect intelligence from highly geographically-diversified points of interest over an extended time period, and we would like to minimize the worst-case data refreshment rate, the largest time gap between two consecutive observations over the same point of interest. In this paper, we formally define each problem, prove its NP-hardness, and propose an approximation algorithm for it. We also conduct a simulation to study the performance of our result.

We wonder that in a competitive environment, how an influence uses the minimum cost to choose seeds such that its influence spread can reach a desired threshold under thwarting from its competitors. At first we take a simple fact into account: the information arriving first has heavy impact, and present Competitive — Independent Cascade (C-IC) model to characterize how different influences competing with others in a social network. We have found that a specific influence's spread is monotone and submodular, and these nice properties make algorithm performance tractable. We then propose Minimum Cost Seed Set problem (MinSeed) to answer our original concern and give a greedy algorithm. We analyze the ratio of greedy algorithm, and give result significantly better than similar ones analyzed by others. Noticing that the computation of real information spread is hard to compute and simple greedy is too time consuming, we design an effective method for estimating information spread in C-IC model, and devise scalable algorithm applying for large social networks. Through simulation on real world datasets, we confirm that, our scalable algorithm outputs seed set with small total cost comparable to that given by simple greedy, with very fast computation.

Many distributed systems use a client-server model in which client assignment strategy plays an important role on the system performance. People use two criteria to evaluate server loads-1) total load and 2) load balance. The total load increases when the load balance decreases, and vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design algorithms based on semidefinite programming. We study the identical server case and general server case, present two algorithms (BSP and ABSP), and analyze these algorithms' bounds. In simulation, we evaluate that our client assignement strategies give the satisfiable total load and load balancing using reasonable time compared to the state-of-the-art, thus proving the effectiveness of our algorithms.

Visual sensor networks (VSNs) can track multiple pedestrians and capture high-quality videos of the monitored area. Therefore, VSNs is ideal for providing good broadcast service. In sports broadcasting, a basic requirement for broadcasters is to report the significant events as quickly as possible when they take place. To meet this requirement, we propose the Camera Scheduling for selected area coverage problem (CamS). Considering that Pan-Tilt-Zoom (PTZ) camera sensor has the flexibility of configuring its angle of view in both horizontal and vertical dimensions, we apply PTZ camera sensors to solve CamS. A polynomial time optimal algorithm that schedules PTZ camera sensors elegantly is devised for CamS. We set many realistic application scenarios in simulation and thoroughly study how our algorithm's performance is affected by different environmental parameters, including angle velocity, the number of camera sensors and the number of sub-areas.

Underwater Wireless Sensor Networks (UWSNs) are vulnerable to attack because of the broadcast nature of the transmission. The sensor nodes in UWSN are highly constrained in terms of computational capabilities and communication bandwidth. Authentication schemes for ground WSNs might not be applicable for UWSNs due to their less computation and communication capacity. Thus, it is necessary to design special schemes tailored to underwater environments. In this paper, a low computational complexity authentication scheme is proposed. By using Vandermonde matrix, we replace the matrix multiplication by matrix addition to greatly reduce the computation overhead. Moreover, our scheme is self-correctable and irreversible which further enhances the security of the UWSNs. Experiment results indicate our algorithm has advantages in energy and time consumption over traditional RSA and Blom's scheme.

The aim of influence maximization problem is to find a k-size seed set that has the maximum influence. In previous works the modification of user's attitude is seldom paid attention to. However from the psychology research, we know that people's opinions are affected by their friends. Base on this, we present a new Linear Threshold model with Instant Opinions (LT-IO). We devise an attitude function Atuthat describes node u's attitude at time t, and the broadcast attitude which is the attitude when a node becomes active. To simulate information propagation in real world, we define a trust threshold η to justify whether a node follows or opposes the influence from its neighbor. We propose a heuristic algorithm IMLT-IOA to solve our problem, prove its submodularity and monotonicity and then obtain its approximation ratio which is (1 - 1/e). To the best of our knowledge, this is the first work that focuses on the influence maximization with user's attitude modification. To verify our IMLT-IOA algorithm, we conduct extensive experiments on a large data collection obtained from real social networks, the results show that IMLT-IOA reduces the running time and meanwhile keeps effectiveness comparing to other algorithms.

This paper investigates two new groups of trajectory optimization problems which stem from networked multi-robotic systems. In particular, we study how to efficiently collect data from stationary sensor nodes using multiple robotic vehicles such as data ferries under different circumstance. The first group includes two new problems which aim to find the tours and the paths, respectively, of k robot vehicles with different mobilization conditions to collect data from ground sensor nodes with minimum latency. The second group consists of one new problem whose goal is to determine the quality tours of k robot vehicles with different speeds, where each of which follows its corresponding tour to repeatedly collect data from stationary sensors. We prove the three problems are NP-hard and propose constant factor approximation strategies for them. Through a simulation, an analytical study is conducted to evaluate the average performance of our core contribution.

Effectiveness of MapReduce as a big data processing framework depends on efficiencies of scale for both map and reduce phases. While most map tasks are preemptive and parallelizable, the reduce tasks typically are not easily decomposed and often become a bottleneck due to constraints of data locality and task complexity. By assuming that reduce tasks are non-parallelizable, we study offline scheduling of minimizing makespan and minimizing total completion time, respectively. Both preemptive and non-preemptive reduce tasks are considered. On makespan minimization, for preemptive version we design an algorithm and prove its optimality, for non-preemptive version we design an approximation algorithm with the worst ratio of 3/2-1/2h where h is the number of machines. On total complete time minimization, for non-preemptive version we devise an approximation algorithm with worst case ratio of 2-1/h, and for preemptive version we devise a heuristic. We confirm that our algorithms outperform state-of-art schedulers through experiments.

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

We study competitive influence propagation in social networks based on Independent Cascade (IC) model. First we propose two new models, in both of which each individual in the network is allowed to propagate multiple influences to its neighbors. In the first Deadline Independent Cascade (DIC) model, each individual has a deadline of following the final single influence and before that it may accept different influences. In the second Latency Independent Cascade (LIC) model, once an individual firstly receives any influence, it has a latency to make the final decision and in the latency it continues receiving influences. Second we analyze the combinatorial properties of our proposed models. We prove that the influence spread under DIC model is monotone and sub modular, which implies that the last influence source has a strategy that returns at least 1 -- 1/e of the best response. We also give examples showing that the influence spread under LIC model is neither monotone nor sub modular, which implies that even for the last influence source, it is hard to find the strategy with guaranteed performance.

Social influence has been widely studied in areas of viral marketing, information diffusion and health care. Currently, most influence models only deal with a single influence without the interference of other influences. Also, the influence spreading in previous models must be triggered by individuals who have been activated by the influence. In this paper, we argue that it is the attraction from a specific influence makes an individual choose to spread it among multiple influences. Inspired by charged system theory in physics, a new influence model is proposed, considering individual features and social structure features. It also gives a natural description about how individuals make decisions among multiple influences. Then a novel algorithm based on this model is provided to predict human behavior. Extensive experiments on three real-world datasets demonstrate that our model and algorithm statistically outperform the state-of-the-art methods in terms of prediction accuracy.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic IC and LT models respectively, which is a pioneer work. We find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. We propose Balanced Influence and Profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the non-monotony, we show BIP objective function is sub modular under certain conditions. Two unbudgeted greedy algorithms separately are devised. We conduct simulations on real-world datasets and evaluate the superiority of our algorithms over existing ones.

Online Social Networks (OSNs) have recently emerged as an effective medium for information sharing. Unfortunately, it has been frequently observed that malicious rumors being spread over an OSN are not controllable, and this is not desirable. This paper proposes a new problem, namely the γ - k rumor restriction problem, whose goal is, given a social network, to find a set S of nodes with k protectors (γ * k protectors from the contaminated set, and (1 - γ) * k protectors from the decontaminated set) to protect the network such that the number of decontaminated nodes is maximum. We show that the objective function of the γ - k rumor restriction problem is submodular, and use this result to design a greedy approximation algorithm with performance ratio of 1 - 1/e for the problem under the linear threshold model and independent cascade model, respectively. To verify our algorithms, we conduct experiments on real word social networks including NetHEPT, WikiVote and Slashdot0811. The results show that our algorithm works efficiently and effectively.

In this paper we present a middleware named SmartPrint to provide cloud print service in office, where many heterogeneous networks exist. The goal of the system is to shield the communication heterogeneity of the devices in the office and make authorized users freely connect to all the printers with no modification on their terminals. SmartPrint can manages all the printers in an office building, and it provides friendly service for the users who know nothing about the printers. SmartPrint can also automatically choose printers for the office staffs. We propose and implement two printer allocation methods, one aims to improve the experience of the user with short print job, and the other is a multiple attributes decision algorithm which considers all factors including spatial information that impact the user experiences. Through experiments we validate the methods, and prove that SmartPrint achieves high user satisfaction from collected real data.