关键词:
Sensors
Autonomous aerial vehicles
Approximation algorithms
Disasters
Wireless sensor networks
Capacitive sensors
Water pollution
Social networking (online)
Contamination
Computer science
UAV deployment
sensor placement
submodular function maximization
approximation 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 1-1/e/2h+2 -approximation algorithm for the problem, improving the best approximation ratio 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 1-1/e/5 and may be as large as 1 in some special cases when K <= 23 , and is no less than 1-1/e/6 when K >= 24 , compared with the current best approximation ratio 1-1/e/7(=1-1/e/2h+3) 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.