AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
View PDF
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Reliable Data Storage in Heterogeneous Wireless Sensor Networks by Jointly Optimizing Routing and Storage Node Deployment

College of Computer Science and Technology, Qingdao University, Qingdao 266071, China.
School of Computer Science and Technology, Shandong University, Qingdao 266237, China.
Department of Computer Science, the University of Hong Kong, Hong Kong 999077, China.
School of Computer Science and Technology, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China
Shandong Computer Science Center (National Supercomputer Center in Jinan), Jinan 250014, China.
Show Author Information

Abstract

In the era of big data, sensor networks have been pervasively deployed, producing a large amount of data for various applications. However, because sensor networks are usually placed in hostile environments, managing the huge volume of data is a very challenging issue. In this study, we mainly focus on the data storage reliability problem in heterogeneous wireless sensor networks where robust storage nodes are deployed in sensor networks and data redundancy is utilized through coding techniques. To minimize data delivery and data storage costs, we design an algorithm to jointly optimize data routing and storage node deployment. The problem can be formulated as a binary nonlinear combinatorial optimization problem, and due to its NP-hardness, designing approximation algorithms is highly nontrivial. By leveraging the Markov approximation framework, we elaborately design an efficient algorithm driven by a continuous-time Markov chain to schedule the deployment of the storage node and corresponding routing strategy. We also perform extensive simulations to verify the efficacy of our algorithm.

Keywords

reliable data storageroutingnode deploymentheterogeneous sensor networks

References

[1]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: A survey, Computer Networks, vol. 38, no. 4, pp. 393-422, 2002.
DOI Google Scholar
[2]
C. Y. Ai, F. H. Li, and K. J. Zhang, Detecting isolate safe areas in wireless sensor monitoring systems, Tsinghua Science and Technology, vol. 22, no. 4, pp. 427-436, 2017.
DOI Google Scholar
[3]
R. Arcucci, C. Pain, and Y. K. Guo, Effective variational data assimilation in air-pollution prediction, Big Data Mining and Analytics, vol. 1, no. 4, pp. 297-307, 2018.
DOI Google Scholar
[4]
F. Li, J. Luo, S. Q. Xin, and Y. He, Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing model, Computer Networks, vol. 108, pp. 120-132, 2016.
DOI Google Scholar
[5]
F. Li, J. Luo, W. P. Wang, and Y. He, Autonomous deployment for load balancing k-surface coverage in sensor networks, IEEE Transactions on Wireless Communications, vol. 14, no. 1, pp. 279-293, 2015.
DOI Google Scholar
[6]
L. Xiang, J. Luo, C. W. Deng, A. V. Vasilakos, and W. S. Lin, DECA: Recovering fields of physical quantities from incomplete sensory data, in Proc. 9th Annu. IEEE Communications Society Conf. Sensor, Mesh and Ad Hoc Communications and Networks, Seoul, South Korea, 2012, pp. 182-190.
DOI
[7]
S. Y. Cheng, Z. P. Cai, J. Z. 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, 2017.
DOI Google Scholar
[8]
J. Li, S. Y. Cheng, Z. P. Cai, J. G. Yu, C. K. Wang, and D. M. Li, Approximate holistic aggregation in wireless sensor networks, ACM Transactions on Sensor Networks, vol. 13, no. 2, pp. 1-24, 2017.
DOI Google Scholar
[9]
Z. B. He, Z. P. Cai, S. Y. Cheng, and X. M. 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
[10]
S. Y. Cheng, Z. P. Cai, and J. Z. Li, Curve query processing in wireless sensor networks, IEEE Transactions on Vehicular Technology, vol. 64, no. 11, pp. 5198-5209, 2015.
DOI Google Scholar
[11]
Q. Y. Meng, K. Wang, X. M. He, and M. Y. Guo, QoE-driven big data management in pervasive edge computing environment, Big Data Mining and Analytics, vol. 1, no. 3, pp. 222-233, 2018.
DOI Google Scholar
[12]
M. Albano and S. Chessa, Distributed erasure coding in data centric storage for wireless sensor networks, in Proc. 2009 IEEE Symp. Computers and Communications, Sousse, Tunisia, 2009, pp. 22-27.
DOI
[13]
A. G. Dimakis, V. Prabhakaran, and K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2809-2816, 2006.
DOI Google Scholar
[14]
F. Li, Y. B. Yang, Z. C. Chi, L. Y. Zhao, Y. W. Yang, and J. Luo, Trinity: Enabling self-sustaining WSNs indoors with energy-free sensing and networking, ACM Transactions on Embedded Computing Systems, vol. 17, no. 2, pp. 1-27, 2018.
DOI Google Scholar
[15]
S. Holzer and R. Wattenhofer, Optimal distributed all pairs shortest paths and applications, in Proc. 2012 ACM Symp. Principles of Distributed Computing, Madeira, Portugal, 2012, pp. 355-364.
DOI
[16]
M. Ghaffari and J. Li, Improved distributed algorithms for exact shortest paths, in Proc. 50th Annu. ACM SIGACT Symp. Theory of Computing, Los Angeles, CA, USA, 2018, pp. 431-444.
DOI
[17]
G. Maia, D. L. Guidoni, A. C. Viana, A. L. L. Aquino, R. A. F. Mini, and A. A. F. Loureiro, A distributed data storage protocol for heterogeneous wireless sensor networks with mobile sinks, Ad Hoc Networks, vol. 11, no. 5, pp. 1588-1602, 2013.
DOI Google Scholar
[18]
Q. Liu, K. Zhang, X. D. Liu, and N. Linge, Grid routing: An energy-efficient routing protocol for WSNs with single mobile sink, International Journal of Sensor Networks, vol. 25, no. 2, pp. 93-103, 2017.
DOI Google Scholar
[19]
M. H. Chen, S. C. Liew, Z. Y. Shao, and C. H. Kai, Markov approximation for combinatorial network optimization, IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6301-6327, 2013.
DOI Google Scholar
[20]
X. Zheng, Z. P. Cai, J. Z. Li, and H. Gao, A study on application-aware scheduling in wireless networks, IEEE Transactions on Mobile Computing, vol. 16, no. 7, pp. 1787-1801, 2017.
DOI Google Scholar
[21]
Z. P. Cai, G. H. Lin, and G. L. Xue, Improved approximation algorithms for the capacitated multicast routing problem, in Proc. of the 11th COCOON, Berlin, Germany, 2005, pp. 136-145.
DOI
[22]
Z. P. Cai, Z. Z. Chen, and G. H. 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
[23]
S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
DOI
[24]
R. G. Gallager, Stochastic Processes: Theory for Applications. Cambridge, UK: Cambridge University Press, 2014.
DOI
[25]
R. L. Deng, S. B. He, and J. M. Chen, An online algorithm for data collection by multiple sinks in wireless-sensor networks, IEEE Transactions on Control of Network Systems, vol. 5, no. 1, pp. 93-104, 2018.
DOI Google Scholar
[26]
J. Wang, J. Y. Cao, R. S. Sherratt, and J. H. Park, An improved ant colony optimization-based approach with mobile sink for wireless sensor networks, The Journal of Supercomputing, vol. 74, no. 12, pp. 6633-6645, 2018.
DOI Google Scholar
[27]
G. R. Li, S. C. Peng, C. Wang, J. W. Niu, and Y. Yuan, An energy-efficient data collection scheme using denoising autoencoder in wireless sensor networks, Tsinghua Science and Technology, vol. 24, no. 1, pp. 86-96, 2019.
DOI Google Scholar
[28]
F. Li, J. Luo, G. T. Shi, and Y. He, ART: Adaptive frequency-temporal co-existing of ZigBee and WiFi, IEEE Transactions on Mobile Computing, vol. 16, no. 3, pp. 662-674, 2017.
DOI Google Scholar
[29]
B. Sheng, Q. Li, and W. Z. Mao, Data storage placement in sensor networks, in Proc. 7th ACM Int. Symp. Mobile Ad Hoc Networking and Computing, Florence, Italy, 2006, pp. 344-355.
DOI
[30]
X. J. Yang, X. F. Tao, E. Dutkiewicz, X. J. Huang, Y. J. Guo, and Q. M. Cui, Energy-efficient distributed data storage for wireless sensor networks based on compressed sensing and network coding, IEEE Transactions on Wireless Communications, vol. 12, no. 10, pp. 5087-5099, 2013.
DOI Google Scholar
[31]
A. Talari and N. Rahnavard, CStorage: Decentralized compressive data storage in wireless sensor networks, Ad Hoc Networks, vol. 37, pp. 475-485, 2016.
DOI Google Scholar
[32]
J. Luo, F. Li, and Y. He, 3DQS: Distributed data access in 3D wireless sensor networks, in Proc. 2011 IEEE Int. Conf. Communications, Kyoto, Japan, 2011, pp. 1-5.
DOI
[33]
C. Zhang, J. Luo, L. Xiang, F. Li, J. C. Lin, and Y. He, Harmonic quorum systems: Data management in 2D/3D wireless sensor networks with holes, in Proc. 2012 9th Annu. IEEE Communications Society Conf. Sensor, Mesh and Ad Hoc Communications and Networks, Seoul, South Korea, 2012, pp. 1-9.
DOI
[34]
R. F. Zeng, Y. X. Jiang, C. Lin, Y. F. Fan, and X. M. Shen, A distributed fault/intrusion-tolerant sensor data storage scheme based on network coding and homomorphic fingerprinting, IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 10, pp. 1819-1830, 2012.
DOI Google Scholar
[35]
J. Tian, T. Yan, and G. L. Wang, A network coding based energy efficient data backup in survivability-heterogeneous sensor networks, IEEE Transactions on Mobile Computing, vol. 14, no. 10, pp. 1992-2006, 2015.
DOI Google Scholar
[36]
G. D’Angelo, D. Diodati, A. Navarra, and C. M. Pinotti, The minimum k-storage problem: Complexity, approximation, and experimental analysis, IEEE Transactions on Mobile Computing, vol. 15, no. 7, pp. 1797-1811, 2016.
DOI Google Scholar
Tsinghua Science and Technology
Volume 26 Issue 2,
April 2021
Pages 230-238
DOI: 10.26599/TST.2019.9010061
Cite this article:
Yang H, Li F, Yu D, et al. Reliable Data Storage in Heterogeneous Wireless Sensor Networks by Jointly Optimizing Routing and Storage Node Deployment. Tsinghua Science and Technology, 2021, 26(2): 230-238. https://doi.org/10.26599/TST.2019.9010061

568

Views

50

Downloads

22

Crossref

N/A

Web of Science

26

Scopus

2

CSCD

Altmetrics
Received: 26 November 2019
Accepted: 06 December 2019
Published: 24 July 2020
© The author(s) 2021.

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