BLOW-UP: Toward Distributed and Scalable Space Filling Curve Construction in 3D Volumetric WSNs

Abstract

In wireless sensor networks (WSNs), a space filling curve (SFC) refers to a path passing through all nodes in the network, with each node visited at least once. By enforcing a linear order of the sensor nodes through an SFC, many applications in WSNs concerning serial operations on both sensor nodes and sensor data can be performed, with examples including serial data fusion and path planning of mobile nodes. Although a few studies have made efforts to find such SFCs in WSNs, they primarily target 2D planar or 3D surface settings and cannot be directly applied to 3D volumetric WSNs due to considerably more complex geometric features and topology shapes that the 3D volumetric settings introduce. This article presents BLOW-UP, a distributed, scalable, and connectivity-based algorithm to construct an SFC for a 3D volumetric WSN (or alternatively to linearize the 3D volumetric network). The main idea of BLOW-UP is to decompose the given 3D volumetric network into a series of connected and closed layers, and the nodes are traversed layer by layer, incrementally from the innermost to the outermost, yielding an SFC covering the entire network, provably at least once and at most a constant number of times. To the best of our knowledge, BLOW-UP is the first algorithm that realizes linearization in 3D volumetric WSNs. It does not require advance knowledge of location or distance information. It is also scalable with a nearly constant per-node storage cost and message cost. Extensive simulations under various networks demonstrate its effectiveness on nodes’ covered times, coverage rate, and covering speed.

References

1. M. Ahmed and S. Bokhari. 2007. Mapping with space filling surfaces. IEEE Transactions on Parallel and Distributed Systems 18, 9, 1258--1269.
2. I. F. Akyildiz and M. C. Vuran. 2010. Wireless Sensor Networks. John Wiley & Sons.
3. M. Bader. 2012. Space-Filling Curves: An Introduction with Applications in Scientific Computing. Texts in Computational Science and Engineering, Vol. 9. Springer.
4. J. M. Bahi, A. Makhoul, and A. Mostefaoui. 2008. Hilbert mobile beacon for localisation and coverage in sensor networks. International Journal of Systems Science 39, 11, 1081--1094.
5. X. Ban, M. Goswami, W. Zeng, X. Gu, and J. Gao. 2013. Topology dependent space filling curves for sensor networks and applications. In Proceedings of the IEEE INFOCOM Conference (INFOCOM’13). 2166--2174.
6. R. S. Blum, S. A. Kassam, and H. V. Poor. 1997. Distributed detection with multiple sensors II. Advanced topics. Proceedings of the IEEE 85, 1, 64--79.
7. F. Cadger, K. Curran, J. Santos, and S. Moffett. 2013. A survey of geographical routing in wireless ad-hoc networks. IEEE Communications Surveys and Tutorials 15, 2, 621--653.
8. J. Flich, T. Skeie, A. Mejia, O. Lysne, P. Lopez, A. Robles, J. Duato, M. Koibuchi, T. Rokicki, and J. C. Sancho. 2012. A survey and evaluation of topology-agnostic deterministic routing algorithms. IEEE Transactions on Parallel and Distributed Systems 23, 3, 405--425.
9. J. Gao and L. Zhang. 2006. Load-balanced short-path routing in wireless networks. IEEE Transactions on Parallel and Distributed Systems 17, 4, 377--388.
10. M. R. Garey, D. S. Johnson, and R. E. Tarjan. 1976. The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing 5, 4, 704--714.
11. C. Gold. 1999. Crust and anti-crust: A one-step boundary and skeleton extraction algorithm. In Proceedings of ACM Symposium on Computational Geometry. 189--196.
12. C. Gold and J. Snoeyink. 2001. A one-step crust and skeleton extraction algorithm. Algorithmica 30, 2, 144--163.
13. D. Hilbert. 1891. Ueber die stetige abbildung einer line auf ein fachenstuck. Mathematische Annalen 38, 3, 459--460.
14. H. Jiang, T. Yu, C. Tian, G. Tan, and C. Wang. 2015. Connectivity-based segmentation in large-scale 2-D/3-D sensor networks: Algorithm and applications. IEEE/ACM Transactions on Networking 23, 1, 15--27.
15. D. B. Johnson and D. A. Maltz. 1996. Dynamic source routing in ad hoc wireless networks. In Mobile Computing. Kluwer International Series in Engineering and Computer Science, Vol. 353. Kluwer, 153--181.
16. M. Kamat, A. S. Ismail, and S. Olariu. 2007. Modified Hilbert space-filling curve for ellipsoidal coverage in wireless ad hoc sensor networks. In Proceedings of the IEEE ICSPC Conference (ICSPC’07). 1407--1410.
17. S. Kar, J. M. F. Moura, and K. Ramanan. 2012. Distributed parameter estimation in sensor networks: Nonlinear observation models and imperfect communication. IEEE Transactions on Information Theory 58, 6, 3575--3605.
18. D. Koutsonikolas, S. M Das, and Y. C. Hu. 2007. Path planning of mobile landmarks for localization in wireless sensor networks. Computer Communications 30, 13, 2577--2592.
19. F. Kuhn, R. Wattenhofer, and A. Zollinger. 2003. Worst-case optimal and average-case efficient geometric ad-hoc routing. In Proceedings of the ACM MobiHoc Conference (MobiHoc’03). 267--278.
20. F. Li, C. Zhang, J. Luo, S. Xin, and Y. He. 2014. LBDP: Localized boundary detection and parametrization for 3-D sensor networks. IEEE/ACM Transactions on Networking 22, 2, 567--579.
21. W. Liang, P. Schweitzer, and Z. Xu. 2013. Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink. IEEE Transactions on Computers 62, 10, 1932--1944.
22. Y. Luo, L. Pu, M. Zuba, Z. Peng, and J.-H. Cui. 2014. Challenges and opportunities of underwater cognitive acoustic networks. IEEE Transactions on Emerging Topics in Computing 2, 2, 109--211.
23. A. Madhja, S. Nikoletseas, and T. P. Raptis. 2015. Distributed wireless power transfer in sensor networks with multiple mobile chargers. Computer Networks 80, 7, 89--108.
24. E. Masazade, R. Niu, P. K. Varshney, and M. Keskinoz. 2010. Energy aware iterative source localization for wireless sensor networks. IEEE Transactions on Signal Processing 58, 9, 4824--4835.
25. A. Mostefaoui, A. Boukerche, M. A. Merzoug, and M. Melkemi. 2015. A scalable approach for serial data fusion in wireless sensor networks. Computer Networks 79, 14, 103--119.
26. A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis. 2009. On distributed averaging algorithms and quantization effects. IEEE Transactions on Automatic Control 54, 11, 2506--2517.
27. Y. Noh, U. Lee, P. Wang, B. S. C. Choi, and M. Gerla. 2013. VAPR: Void-aware pressure routing for underwater sensor networks. IEEE Transactions on Mobile Computing 12, 5, 895--908.
28. S. Patil, S. R. Das, and A. Nasipuri. 2004. Serial data fusion using space-filling curves in wireless sensor networks. In Proceedings of the IEEE SECON Conference (SECON’04). 182--190.
29. G. Peano. 1890. Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36, 1, 157--160.
30. C. Perera, A. Zaslavsky, C. H. Liu, M. Compton, P. Christen, and D. Georgakopoulos. 2014. Sensor search techniques for sensing as a service architecture for the Internet of Things. IEEE Sensors Journal 14, 2, 406--420.
31. T. L. Porta, C. Petrioli, C. Phillips, and D. Spenza. 2014. Sensor mission assignment in rechargeable wireless sensor networks. ACM Transactions on Sensor Networks 10, 4, 60:1--60:39.
32. R. Rajagopalan and P. K. Varshney. 2006. Data aggregation techniques in sensor networks: A survey. IEEE Communications Surveys and Tutorials 8, 4, 48--63.
33. H. Sagan. 1994. Space-Filling Curves. Springer-Verlag, New York, NY.
34. R. C. Shah, S. Roy, S. Jain, and W. Brunette. 2003. Data mules: Modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks 1, 2, 215--233.
35. F. Spitzer. 2001. Principles of Random Walk. Vol. 34. Springer.
36. R. Sugihara and R. K. Gupta. 2011. Path planning of data mules in sensor networks. ACM Transactions on Sensor Networks 8, 1, 1:1--1:27.
37. G. Tan, H. Jiang, J. Liu, and A.-M. Kermarrec. 2014. Convex partitioning of large-scale sensor networks in complex fields: Algorithms and applications. ACM Transactions on Sensor Networks 10, 3, 41:1--41:23.
38. G. Tan, H. Jiang, S. Zhang, Z. Yin, and A.-M. Kermarrec. 2013. Connectivity-based and anchor-free localization in large-scale 2D/3D sensor networks. ACM Transactions on Sensor Networks 10, 1, 6:1--6:21.
39. R. Tan, G. Xing, J. Wang, and B. Liu. 2011. Performance analysis of real-time detection in fusion-based sensor networks. IEEE Transactions on Parallel and Distributed Systems 22, 9, 1564--1577.
40. O. Tekdas, V. Isler, L. J. Hyun, and A. Terzis. 2009. Using mobile robots to harvest data from sensor fields. IEEE Wireless Communications 16, 1, 22--28.
41. C. Tunca, S. Isik, M. Y. Donmez, and C. Ersoy. 2014. Distributed mobile sink routing for wireless sensor networks: A survey. IEEE Communications Surveys and Tutorials 16, 2, 877--897.
42. R. Viswanathan and P. K. Varshney. 1997. Distributed detection with multiple sensors I. Fundamentals. Proceedings of the IEEE 85, 1, 54--63.
43. C. Wang and H. Jiang. 2015. SURF: A connectivity-based space filling curve construction algorithm in high genus 3D surface WSNs. In Proceedings of the IEEE INFOCOM Conference (INFOCOM’15). 981--989.
44. C. Wang, H. Ma, Y. He, and S. Xiong. 2012. Adaptive approximate data collection for wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems 23, 6, 1004--1016.
45. S. Xia, H. Wu, and M. Jin. 2014. Trace-routing in 3D wireless sensor networks: A deterministic approach with constant overhead. In Proceedings of the ACM MobiHoc Conference (MobiHoc’14). 357--366.
46. S. Xia, X. Yin, H. Wu, M. Jin, and X. D. Gu. 2011. Deterministic greedy routing with guaranteed delivery in 3D wireless sensor networks. In Proceedings of the ACM MobiHoc Conference (MobiHoc’11). 1--10.
47. L. Xie, Y. Shi, Y. T. Hou, and H. D. Sherali. 2012. Making sensor networks immortal: An energy-renewal approach with wireless power transfer. IEEE/ACM Transactions on Networking 20, 6, 1748--1761.
48. K. Yang. 2014. Wireless Sensor Networks. Springer.
49. F. Ye, H. Luo, J. Cheng, S. Lu, and L. Zhang. 2002. A two-tier data dissemination model for large-scale wireless sensor networks. In Proceedings of the ACM MobiCom Conference (MobiCom’02). 148--159.
50. H. Zhang and H. Shen. 2009. Balancing energy consumption to maximize network lifetime in data-gathering sensor networks. IEEE Transactions on Parallel and Distributed Systems 20, 10, 1526--1539.
51. H. Zhou, N. Ding, M. Jin, S. Xia, and H. Wu. 2011. Distributed algorithms for bottleneck identification and segmentation in 3D wireless sensor networks. In Proceedings of the IEEE SECON Conference (SECON’11). 494--502.
52. M. Zhu, S. Ding, Q. Wu, R. R. Brooks, N. S. V. Rao, and S. S. Iyengar. 2010. Fusion of threshold rules for target detection in wireless sensor networks. ACM Transactions on Sensor Networks 6, 2, 18:1--18:7.

Index Terms

• Networks

  • Network protocols