Path Planning for Sensor Data Collection by Using UAVs

Baichuan Kong; Hejiao Huang; Xiaohua Jia

doi:10.1109/MSN.2018.00033

Path Planning for Sensor Data Collection by Using UAVs

Baichuan Kong
, Hejiao Huang
, Xiaohua Jia^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

7 Citations (Scopus)

Abstract

In sparse wireless sensor networks, a UAV is used to collect the sensing data. Each sensor node has a limited transmission range and the UAV has to traverse the transmission range of all sensor nodes to collect data without exhausting energy of the UAV. To minimize the total energy consumption of the UAV on the flying and collecting data, it is essential to consider the tradeoff between path length and data collection time when planning path. In this paper, we show that the optimization problem can be regarded as the traveling salesman problem with neighborhood, which is known to be NP-hard. To address the problem, we decompose it into two subproblems, 1) weighted set cover problem; and 2) a combined optimization problem. Then we solve the first one by a greedy algorithm and the second by an improved shuffled frog-leaping algorithm. We also simulate the proposed algorithm to evaluate its performance.

Original language	English
Title of host publication	14th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2018
Publisher	IEEE
Pages	199-205
ISBN (Electronic)	9781728105482
ISBN (Print)	9781728105499
DOIs	https://doi.org/10.1109/MSN.2018.00033
Publication status	Published - Dec 2018
Event	14th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2018) - Shenyang, China Duration: 6 Dec 2018 → 8 Dec 2018 https://www.computer.org/csdl/proceedings/msn/2018/19m3npxNnVK

Publication series

Name	Proceedings - International Conference on Mobile Ad-Hoc and Sensor Networks, MSN
Publisher	IEEE

Conference

Conference	14th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2018)
Abbreviated title	IEEE MSN 2018
Place	China
City	Shenyang
Period	6/12/18 → 8/12/18
Internet address	https://www.computer.org/csdl/proceedings/msn/2018/19m3npxNnVK

Research Keywords

UAV
data collection
path planning
energy efficient

Access Output

10.1109/MSN.2018.00033

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{46a582c0c08242c583e197b06a54fd6a,

title = "Path Planning for Sensor Data Collection by Using UAVs",

abstract = "In sparse wireless sensor networks, a UAV is used to collect the sensing data. Each sensor node has a limited transmission range and the UAV has to traverse the transmission range of all sensor nodes to collect data without exhausting energy of the UAV. To minimize the total energy consumption of the UAV on the flying and collecting data, it is essential to consider the tradeoff between path length and data collection time when planning path. In this paper, we show that the optimization problem can be regarded as the traveling salesman problem with neighborhood, which is known to be NP-hard. To address the problem, we decompose it into two subproblems, 1) weighted set cover problem; and 2) a combined optimization problem. Then we solve the first one by a greedy algorithm and the second by an improved shuffled frog-leaping algorithm. We also simulate the proposed algorithm to evaluate its performance.",

keywords = "UAV, data collection, path planning, energy efficient",

author = "Baichuan Kong and Hejiao Huang and Xiaohua Jia",

year = "2018",

month = dec,

doi = "10.1109/MSN.2018.00033",

language = "English",

isbn = "9781728105499",

series = "Proceedings - International Conference on Mobile Ad-Hoc and Sensor Networks, MSN",

publisher = "IEEE",

pages = "199--205",

booktitle = "14th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2018",

address = "United States",

note = "14th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2018), IEEE MSN 2018 ; Conference date: 06-12-2018 Through 08-12-2018",

url = "https://www.computer.org/csdl/proceedings/msn/2018/19m3npxNnVK",

}

Kong, B, Huang, H & Jia, X 2018, Path Planning for Sensor Data Collection by Using UAVs. in 14th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2018., 8691979, Proceedings - International Conference on Mobile Ad-Hoc and Sensor Networks, MSN, IEEE, pp. 199-205, 14th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2018), Shenyang, China, 6/12/18. https://doi.org/10.1109/MSN.2018.00033

Path Planning for Sensor Data Collection by Using UAVs. / Kong, Baichuan; Huang, Hejiao; Jia, Xiaohua.
14th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2018. IEEE, 2018. p. 199-205 8691979 (Proceedings - International Conference on Mobile Ad-Hoc and Sensor Networks, MSN).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Path Planning for Sensor Data Collection by Using UAVs

AU - Kong, Baichuan

AU - Huang, Hejiao

AU - Jia, Xiaohua

PY - 2018/12

Y1 - 2018/12

N2 - In sparse wireless sensor networks, a UAV is used to collect the sensing data. Each sensor node has a limited transmission range and the UAV has to traverse the transmission range of all sensor nodes to collect data without exhausting energy of the UAV. To minimize the total energy consumption of the UAV on the flying and collecting data, it is essential to consider the tradeoff between path length and data collection time when planning path. In this paper, we show that the optimization problem can be regarded as the traveling salesman problem with neighborhood, which is known to be NP-hard. To address the problem, we decompose it into two subproblems, 1) weighted set cover problem; and 2) a combined optimization problem. Then we solve the first one by a greedy algorithm and the second by an improved shuffled frog-leaping algorithm. We also simulate the proposed algorithm to evaluate its performance.

AB - In sparse wireless sensor networks, a UAV is used to collect the sensing data. Each sensor node has a limited transmission range and the UAV has to traverse the transmission range of all sensor nodes to collect data without exhausting energy of the UAV. To minimize the total energy consumption of the UAV on the flying and collecting data, it is essential to consider the tradeoff between path length and data collection time when planning path. In this paper, we show that the optimization problem can be regarded as the traveling salesman problem with neighborhood, which is known to be NP-hard. To address the problem, we decompose it into two subproblems, 1) weighted set cover problem; and 2) a combined optimization problem. Then we solve the first one by a greedy algorithm and the second by an improved shuffled frog-leaping algorithm. We also simulate the proposed algorithm to evaluate its performance.

KW - UAV

KW - data collection

KW - path planning

KW - energy efficient

UR - https://www.scopus.com/pages/publications/85065312156

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85065312156&origin=recordpage

U2 - 10.1109/MSN.2018.00033

DO - 10.1109/MSN.2018.00033

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781728105499

T3 - Proceedings - International Conference on Mobile Ad-Hoc and Sensor Networks, MSN

SP - 199

EP - 205

BT - 14th International Conference on Mobile Ad-Hoc and Sensor Networks, MSN 2018

PB - IEEE

T2 - 14th International Conference on Mobile Ad-hoc and Sensor Networks (MSN 2018)

Y2 - 6 December 2018 through 8 December 2018

ER -

Path Planning for Sensor Data Collection by Using UAVs

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this