Journal Home > Volume 26 , Issue 2
Tsinghua Science and Technology 2021, 26(2): 219-229 https://doi.org/10.26599/TST.2019.9010060
Open Access | Issue | Published: 24 July 2020

Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks

Show Author's Information Ji Li,  Akshita Maradapu Vera Venkata Sai,  Xiuzhen Cheng,  Wei Cheng,  Zhi Tian,  Yingshu Li( )
Kennesaw State University, Marietta, GA 30060, USA.
Georgia State University, Atlanta, GA 30303, USA.
The George Washington University, Washington, DC 20052, USA.
Department of Computer Science, Virginia Commonwealth University, Richmond, VA 23284, USA.
Department of Electrical & Computer Engineering, George Mason University, Fairfax, VA 22030, USA.
Keywords:
data aggregation, sampling, IoT networks
Cite this article:
Li J, Sai AMVV, Cheng X, et al. Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks. Tsinghua Science and Technology, 2021, 26(2): 219-229. https://doi.org/10.26599/TST.2019.9010060
Download citation
EndNote(RIS)
BibTeX

575

Views

21

Downloads

Citations

13

Crossref

N/A

WoS

14

Scopus

4

CSCD

Abstract Full text About this article

The ever increasing requirements of data sensing applications result in the usage of IoT networks. These networks are often used for efficient data transfer. Wireless sensors are incorporated in the IoT networks to reduce the deployment and maintenance costs. Designing an energy efficient data aggregation method for sensor equipped IoT to process skyline query, is one of the most critical problems. In this paper, we propose two approximation algorithms to process the skyline query in wireless sensor networks. These two algorithms are uniform sampling-based approximate skyline query and Bernoulli sampling-based approximate skyline query. Solid theoretical proofs are provided to confirm that the proposed algorithms can yield the required query results. Experiments conducted on actual datasets show that the two proposed algorithms have high performance in terms of energy consumption compared to the simple distributed algorithm.


menu
Abstract
Full text
Outline
About this article

Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks

Show Author's information Ji Li, Akshita Maradapu Vera Venkata Sai, Xiuzhen Cheng, Wei Cheng, Zhi Tian, Yingshu Li( )
Kennesaw State University, Marietta, GA 30060, USA.
Georgia State University, Atlanta, GA 30303, USA.
The George Washington University, Washington, DC 20052, USA.
Department of Computer Science, Virginia Commonwealth University, Richmond, VA 23284, USA.
Department of Electrical & Computer Engineering, George Mason University, Fairfax, VA 22030, USA.

Abstract

The ever increasing requirements of data sensing applications result in the usage of IoT networks. These networks are often used for efficient data transfer. Wireless sensors are incorporated in the IoT networks to reduce the deployment and maintenance costs. Designing an energy efficient data aggregation method for sensor equipped IoT to process skyline query, is one of the most critical problems. In this paper, we propose two approximation algorithms to process the skyline query in wireless sensor networks. These two algorithms are uniform sampling-based approximate skyline query and Bernoulli sampling-based approximate skyline query. Solid theoretical proofs are provided to confirm that the proposed algorithms can yield the required query results. Experiments conducted on actual datasets show that the two proposed algorithms have high performance in terms of energy consumption compared to the simple distributed algorithm.

Keywords: data aggregation, sampling, IoT networks

References(37)

[1]
A. Cocchia, Smart and digital city: A systematic literature review, in Smart City. New York, NY, USA: Springer, 2014, pp. 13-43.
DOI
[2]
R. G. Hollands, Will the real smart city please stand up? intelligent, progressive or entrepreneurial? City, vol. 12, no. 3, pp. 303-320, 2008.
DOI Google Scholar
[3]
Z. Cai and Z. He, Trading private range counting over big IoT data, in Proc. of the 39th IEEE International Conference on Distributed Computing Systems, Dallas, TX, USA, 2019, pp. 144-153.
DOI
[4]
A. Belhassena and H. Wang, Trajectory big data processing based on frequent activity, Tsinghua Science and Technology, vol. 24, no. 3, pp. 317-332, 2019.
DOI Google Scholar
[5]
L. Liu, X. Chen, Z. Lu, L. Wang, and X. Wen, Mobile-edge computing framework with data compression for wireless network in energy internet, Tsinghua Science and Technology, vol. 24, no. 3, pp. 271-280, 2019.
DOI Google Scholar
[6]
Y. Yuan, F. Li, D. Yu, J. Yu, W. Lv, and X. Cheng, Fast fault-tolerant sampling via random walk in dynamic networks, in Proc. of the 39th IEEE International Conference on Distributed Computing Systems, Dallas, TX, USA, 2019, pp. 536-544. 2019.
DOI
[7]
H. Jin, N. Wang, D. Yu, Q.-S. Hua, X. Shi, and X. Xie, Core maintenance in dynamic graphs: A parallel approach based on matching, IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 11, pp. 2416-2428, 2018.
DOI Google Scholar
[8]
D. Yu, L. Ning, Y. Zou, J. Yu, X. Cheng, and F. C. Lau, Distributed spanner construction with physical interference: Constant stretch and linear sparseness, IEEE/ACM Transactions on Networking, vol. 25, no. 4, pp. 2138-2151, 2017.
DOI Google Scholar
[9]
Z. Cai and X. Zheng, A private and efficient mechanism for data uploading in smart cyber-physical systems, IEEE Transactions on Network Science and Engineering, .
DOI Google Scholar
[10]
S. Cheng, Z. Cai, J. Li, and H. Gao, Extracting kernel dataset from big sensory data in wireless sensor networks, IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 4, pp. 813-827, 2016.
DOI Google Scholar
[11]
S. Cheng, Z. Cai, J. Li, and X. Fang, Drawing dominant dataset from big sensory data in wireless sensor networks, in Proc. of IEEE Conference on Computer communications, Hong Kong, China, 2015, pp. 531-539.
DOI
[12]
D. Yu, Y. Zhang, Y. Huang, H. Jin, J. Yu, and Q.-S. Hua, Exact implementation of abstract MAC layer via carrier sensing, in Proc. of IEEE Conference on Computer Communications, Honolulu, HI, USA, 2018, pp. 1196-1204.
DOI
[13]
X. Gong, Q.-S. Hua, L. Qian, D. Yu, and H. Jin, Communication-efficient and privacy-preserving data aggregation without trusted authority, in Proc. of IEEE Conference on Computer Communications, Honolulu, HI, USA, 2018, pp. 1250-1258.
DOI
[14]
S. Cheng, Z. Cai, and J. Li, Curve query processing in wireless sensor networks, IEEE Transactions on Vehicular Technology, vol. 64, no. 11, pp. 5198-5209, 2014.
DOI Google Scholar
[15]
Z. Cai, G. Lin, and G. Xue, Improved approximation algorithms for the capacitated multicast routing problem, in Proc. of International Computing and Combinatorics Conference, Berlin, Germany, 2005, pp. 136-145.
DOI
[16]
Z. Cai, Z.-Z. Chen, and G. Lin, A 3.4713-approximation algorithm for the capacitated multicast tree routing problem, Theoretical Computer Science, vol. 410, no. 52, pp. 5415-5424, 2009.
DOI Google Scholar
[17]
Z. Cai, R. Goebel, and G. Lin, Size-constrained tree partitioning: Approximating the multicast k-tree routing problem, Theoretical Computer Science, vol. 412, no. 3, pp. 240-245, 2011.
DOI Google Scholar
[18]
J. Elson and D. Estrin, Time synchronization for wireless sensor networks, in Proc. of the 2001 International Parallel and Distributed Processing Symposium, San Francisco, CA, USA, 2001.
[19]
J. Li and J. Li, Data sampling control, compression and query in sensor networks, International Journal of Sensor Networks, vol. 2, nos. 1&2, pp. 53-61, 2007.
DOI Google Scholar
[20]
K. Deng, X. Zhou, and H. Tao, Multi-source skyline query processing in road networks, in Proc. of IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey, 2007, pp. 796-805.
DOI
[21]
Z. Peng and C. Wang, Member promotion in social networks via skyline, World Wide Web, vol. 17, no. 4, pp. 457-492, 2014.
DOI Google Scholar
[22]
C. Wang, C. Wang, G. Guo, X. Ye, and S. Y. Philip, Efficient computation of g-skyline groups, IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 4, pp. 674-688, 2017.
DOI Google Scholar
[23]
H. Chen, S. Zhou, and J. Guan, Towards energy-efficient skyline monitoring in wireless sensor networks, in Proc. of European Conference on Wireless Sensor Networks, Istanbul, Turkey, 2007, pp. 101-116.
DOI
[24]
Z. He, Z. Cai, S. Cheng, and X. Wang, Approximate aggregation for tracking quantiles and range countings in wireless sensor networks, Theoretical Computer Science, vol. 607, pp. 381-390, 2015.
DOI Google Scholar
[25]
G. Hartl and B. Li, Infer: A Bayesian inference approach towards energy efficient data collection in dense sensor networks, in Proc. of 25th IEEE International Conference on Distributed Computing Systems, Columbus, OH, USA, 2005, pp. 371-380.
[26]
J. Li, M. Siddula, X. Cheng, W. Cheng, Z. Tian, and Y. Li, Sampling-based δ-approximate data aggregation in sensor equipped IoT networks, in Proc. of International Conference on Wireless Algorithms, Systems, and Applications, Tianjin, China, 2018, pp. 249-260.
DOI
[27]
R. Lachowski, M. E. Pellenz, M. C. Penna, E. Jamhour, and R. D. Souza, An efficient distributed algorithm for constructing spanning trees in wireless sensor networks, Sensors, vol. 15, no. 1, pp. 1518-1536, 2015.
DOI Google Scholar
[28]
S. Cheng and J. Li, Sampling-based (ϵ, δ)-approximate aggregation algorithm in sensor networks, in Proc. of IEEE International Conference on Distributed Computing Systems, Montreal, Canada, 2009, pp. 273-280.
DOI
[29]
MPR-Mote Processor Radio Board User’s Manual, Crossbrow Inc., Milpitas, CA, USA, 2004.
DOI
[30]
G. Anastasi, A. Falchi, A. Passarella, M. Conti, and E. Gregori, Performance measurements of motes sensor networks, in Proceedings of the 7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Venice, Italy, 2004, pp. 174-181.
DOI
[31]
Statistics and data about the vehicle miles travelled by vehicle type, road category and region, https://www.gov.uk/government/collections/road-traffic-statistics, 2013.
[32]
Z. Huang, L. Wang, K. Yi, and Y. Liu, Sampling-based algorithms for quantile computation in sensor networks, in Proc. of International Conference on Management of Data, Athens, Greece, 2011, pp. 745-756.
DOI
[33]
B. Gedik, L. Liu, and S. Y. Philip, ASAP: An adaptive sampling approach to data collection in sensor networks, IEEE Transactions on Parallel and distributed systems, vol. 18, no. 12, pp. 1766-1783, 2007.
DOI Google Scholar
[34]
A. S. Silberstein, R. Braynard, C. Ellis, K. Munagala, and J. Yang, A sampling-based approach to optimizing top-k queries in sensor networks, in Proc. of the 22nd International Conference on Data Engineering, Atlanta, GA, USA, 2006, pp. 68-68.
DOI
[35]
S. Wang, B. C. Ooi, A. K. Tung, and L. Xu, Efficient skyline query processing on peer-to-peer networks, in Proc. of IEEE 23rd International Conference on Data Engineering, Providence, RL, USA, 2007, pp. 1126-1135.
DOI
[36]
J. Li, S. Cheng, Z. Cai, J. Yu, C. Wang, and Y. Li, Approximate holistic aggregation in wireless sensor networks, ACM Transactions on Sensor Networks, vol. 13, no. 2, pp. 1-11, 2017.
DOI Google Scholar
[37]
J. Li, S. Cheng, Z. Cai, Q. Han, and H. Gao, Bernoulli sampling-based (ϵ, δ)-approximate frequency query in mobile ad hoc networks, in Proc. of the 10th International Conference on Wireless Algorithms, Systems, and Applications, Qufu, China, 2015, pp. 315-324.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 08 October 2019
Accepted: 11 November 2019
Published: 24 July 2020
Issue date: April 2021

Copyright

© The author(s) 2021.

Acknowledgements

This work was partly supported by the National Science Foundation of USA (Nos. 1741277, 1741287, 1741279, 1851197, and 1741338).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return