Home Tsinghua Science and Technology Article
PDF (1.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref Google Scholar
[23]
S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.
Crossref
[24]
R. G. Gallager, Stochastic Processes: Theory for Applications. Cambridge, UK: Cambridge University Press, 2014.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return