LAPDK: A novel dynamic-programming-based algorithm for the LAP-(D, k) query problem in wireless sensor networks

被引：0

作者：

Ma X. ^{[1
]}

Li Y. ^{[1
]}

Li R. ^{[1
]}

Li Y. ^{[1
]}

Liang J. ^{[2
]}

机构：

[1] School of Computer and Information Technology, Xinyang Normal University, Xinyang

[2] School of Computer and Electronics Information, Guangxi University, Nanning

来源：

International Journal of Performability Engineering | 2017年 / 13卷 / 04期

关键词：

Approximation ratio optimization; Distance-constrained Top-k query; Dynamic programming; Hexagonal region partition; Wireless Sensor Networks;

D O I：

10.23940/ijpe.17.04.p21.540550

中图分类号：

学科分类号：

摘要：

In wireless sensor networks, the LAP-(D, k) query problem can be seen as a special Top-k query problem with the constraint that the Euclidean distance between any two locations corresponding to the data items in the Top-k query results should not be smaller than the given value D. To solve this problem, a novel dynamic-programming-based heuristic algorithm named LAPDK is proposed. LAPDK firstly divides the sensing field into hexagonal cells using some geometry methods. Then, it finds the approximate solution of the LAP-(D, k) query problem based on parts of the data generated by the sensor nodes in some preferential cells using the dynamic programming technique. Finally, it further optimizes the solution based on the sensing data received by the Sink node. Simulation results show that LAPDK not only decreases the energy cost of WSNs but also obtains a better approximation ratio compared to the existing state-of-the-art scheme for the LAP-(D, k) query problem. © 2017 Totem Publisher, Inc. All rights reserved.

引用

页码：540 / 550

页数：10

共 16 条

[1]

Naik P., Telkar N., Kotin K., Survey on Wireless Sensor Network with their remaining Challenges, International Journal of Scientific Research in Science and Technology, 2, 6, pp. 321-331, (2016)

[2]

Cheng S., Li J., Yu L., Location Aware Peak Value Queries in Sensor Networks, Proceedings of IEEE INFOCOM, pp. 486-494, (2012)

[3]

Jindal A., Psounis K., Modeling spatially correlated data in sensor networks, ACM Transactions on Sensor Networks, 2, 4, pp. 466-499, (2006)

[4]

Mo S., Chen H., Li Y., Clustering-based routing for top-k querying in wireless sensor networks, Eurasip Journal on Wireless Communications & Networking, 1, pp. 1-13, (2011)

[5]

Fu J., Liu Y., Random and Directed Walk-Based Top-k Queries in Wireless Sensor Networks, Sensors, 15, 6, pp. 12273-12298, (2015)

[6]

Haiping H H., Qi Y., Xiaolin Q., Ruchuan W., A filter-based algorithm for optimizing top-k queries in wireless sensor networks, Journal of Systems Architecture, 58, 2, pp. 73-85, (2012)

[7]

Pan Q., Li M., Wu M., Shu W., Optimization of Accurate Top-k Query in Sensor Networks with Cached Data, Proceedings of the 7th International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 553-558, (2011)

[8]

Chen B., Liang W., Yu J., Energy-efficient top-k query evaluation and maintenance in wireless sensor networks, Wireless Networks, 20, 4, pp. 591-610, (2014)

[9]

Choi D., Chung C., REQUEST+: A framework for efficient processing of region-based queries in sensor networks, Information Sciences, 248, 6, pp. 151-167, (2013)

[10]

Malhotra B., Nascimento M., Nikolaidis I., Exact Top-k Queries in Wireless Sensor Networks, IEEE Transactions on Knowledge and Data Engineering, 23, 10, pp. 1513-1525, (2011)

← 1 2 →