research-article

Surface skeleton extraction and its application for data storage in 3D sensor networks

Authors:

Jiangchuan Liu,

Bo LiAuthors Info & Claims

MobiHoc '14: Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing

Pages 337 - 346

https://doi.org/10.1145/2632951.2632966

Published: 11 August 2014 Publication History

Abstract

In-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table (GHT) is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to correctly define the bounding box. It is envisioned that the skeleton has the power to facilitate computing a precise bounding box. In existing works, the focus has been on skeleton extraction algorithms targeting for 2D sensor networks, which usually delivers a 1-manifold skeleton consisting of 1D curves. It faces a set of non-trivial challenges when 3D sensor networks are considered, in order to properly extract the surface skeleton composed of a set of 2-manifolds and possibly 1D curves.

In this paper, we study the problem of surface skeleton extraction in 3D sensor networks. We propose a scalable and distributed connectivity-based algorithm to extract the surface skeleton of 3D sensor networks. First, we propose a novel approach to identifying surface skeleton nodes by computing the \textit{extended feature nodes} such that it is robust against boundary noise, etc. We then find the maximal independent set of the identified skeleton nodes and triangulate them to form a compact representation of the 3D sensor network. Furthermore, to react to the dynamics of the sensor networks caused by node failure, insertion, etc., we design an efficient updating scheme to reconstruct the surface skeleton. Finally, we apply the extracted surface skeleton to facilitate the data storage protocol design. Extensive simulations show the robustness of the proposed algorithm to shape variation, node density, node distribution and communication radio model, and its effectiveness for data storage application with respect to load balancing.

References

[1]

D. Andrade, M. Resende, and R. Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18(4):525--547, 2012.

Digital Library

[2]

N. Azimi, H. Gupta, X. Hou, and J. Gao. Data preservation under spatial failures in sensor networks. In Proc. of ACM MOBIHOC, 2010.

Digital Library

[3]

H. Blum. Biological shape and visual science (part i). Theoretical Biology, 38:205--287, 1973.

[4]

S. Bouix and K. Siddiqi. Divergence-based medial surfaces. In Proc. of European Conference on Computer Vision, 2000.

Digital Library

[5]

J. Bruck, J. Gao, and A. A. Jiang. Map: Medial axis based geometric routing in sensor betworks. In Proc. of ACM MOBICOM, 2005.

Digital Library

[6]

J. DAMON. Global medial structure of regions in r3. Geometry and Topology, 10:2385--2429, 2006.

[7]

M. Doddavenkatappa, M. Chan, and A. Ananda. Indriya: a low-cost, 3d wireless sensor network testbed. In Proc. of ICST Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities(TRIDENTCOM), 2011.

[8]

Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. Glider: Gradient landmark-based distributed routing for sensor networks. In Proc. of IEEE INFOCOM, 2005.

[9]

Q. Fang, J. Gao, and L. J. Guibas. Landmark-based information storage and retrieval in sensor networks. In Proc. of IEEE INFOCOM, 2006.

[10]

F.F.Leymarie and B.B.Kimia. Computation of the shock scaffold for unorganized point clouds in 3d. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition, 2003.

Digital Library

[11]

F.F.Leymarie and B.B.Kimia. The medial scaffold of 3d unorganized point clouds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(2):313--330, 2007.

Digital Library

[12]

H. Jiang, W. Liu, D. Wang, C. Tian, X. Bai, X. Liu, and W. Liu. Case: Connectivity-based skeleton extraction in wireless sensor networks. In Proc. of IEEE INFOCOM, 2009.

[13]

H. Jiang, W. Liu, D. Wang, C. Tian, X. Bai, X. Liu, and W. Liu. Connectivity-based skeleton extraction in wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems, 21(5):710--721, 2010.

Digital Library

[14]

H. Jiang, S. Zhang, G. Tan, and C. Wang. Cabet: Connectivity-based boundary extraction of large-scale 3d sensor networks. In Proc. of IEEE INFOCOM, 2011.

[15]

B. Karp and H. Kung. Gpsr: Greedy perimeter stateles routing for wireless networks. In Proc. of ACM MOBICOM, 2000.

Digital Library

[16]

R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85--103. 1972.

[17]

S. Lederer, Y. Wang, and J. Gao. Connectivity-based localization of large scale sensor networks with complex shape. In Proc. of IEEE INFOCOM, 2008.

[18]

F. Li, J. Luo, C. Zhang, S. Xin, and Y. He. Unfold: uniform fast on-line boundary detection for dynamic 3d wireless sensor networks. In Proc. of ACM MOBIHOC, 2011.

Digital Library

[19]

M. Li, Y. Liu, J. Wang, and Z. Yang. Sensor network navigation without locations. In Proc. of IEEE INFOCOM, 2009.

[20]

X. Li, Y. J. Kim, R. Govindan, and W. Hong. Multi-dimensional range queries in sensor networks. In Proc. of ACM SenSys, 2003.

Digital Library

[21]

W. Liu, H. Jiang, X. Bai, G. Tan, C. Wang, and K. Cai. Distance transform-based skeleton extraction and its applications in sensor networks. IEEE Transactions on Parallel and Distributed Systems, 24(9):1763--1772, 2013.

Digital Library

[22]

W. Liu, H. Jiang, X. Bai, G. Tan, C. Wang, W. Liu, and K. Cai. Skeleton extraction from incomplete boundaries in sensor networks based on distance transform. In Proc. of IEEE ICDCS, 2012.

Digital Library

[23]

W. Liu, H. Jiang, C. Wang, C. Liu, Y. Yang, W. Liu, and B. Li. Connectivity-based and boundary-free skeleton extraction in sensor networks. In Proc. of IEEE ICDCS, 2012.

Digital Library

[24]

W. Liu, H. Jiang, Y. Yang, and Z. jin. A unified framework for line-like skeleton extraction in 2d/3d sensor networks. In Proc. of IEEE ICNP, 2013.

[25]

W. Liu, D. Wang, H. Jiang, W. Liu, and C. Wang. Approximate convex decomposition based localization in wireless sensor networks. In Proc. of IEEE INFOCOM, 2012.

[26]

S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu. Data-centric storage in sensornets with ght, a geographic hash table. Mobile Networks and Applications, 8(4):427--442, 2003.

Digital Library

[27]

D. Reniers and A. Telea. Segmenting simplified surface skeletons. In Proc. of the 14th IAPR International Conference on Discrete Geometry for Computer Imagery, 2008.

Digital Library

[28]

D. Reniers, J. J. Wijk, and A.Telea. Computing multiscale curve and surface skeletons of genus 0 shapes using a global importance measure. IEEE Transactions on Visualization and Computer Graphics, 14(2):355--368, 2008.

Digital Library

[29]

R. Sarkar, W. Zeng, J. Gao, and X. D. Gu. Covering space for in-network sensor data storage. In Proc. of ACM/IEEE IPSN, 2010.

Digital Library

[30]

R. Sarkar, X. Zhu, and J. Gao. Double rulings for information brokerage in sensor networks. IEEE/ACM Transactions on Networking, 17(6):1902--1915, 2009.

Digital Library

[31]

R. Tam and W. Heidrich. Shape simplification based on the medial axis transform. In Proc. of IEEE Visualization Conference, 2003.

Digital Library

[32]

G. Tan, H. Jiang, S. Zhang, and A. Kermarrec. Connectivity-based and anchor-free localization in large-scale 2d/3d sensor networks. In Proc. of ACM MOBIHOC, 2010.

Digital Library

[33]

G. Werner-Allen, P. Swieskowski, and M. Welsh. Motelab: a wireless sensor network testbed. In Proc. of ACM/IEEE IPSN, 2005.

Digital Library

[34]

S. Xia, N. Ding, M. Jin, H. Wu, and Y. Yang. Medial axis construction and applications in 3D wireless sensor networks. In Proc. of IEEE INFOCOM, mini-conference, 2013.

[35]

S. Xia, X. Yin, H. Wu, M. Jin, and X. Gu. Deterministic greedy routing with guaranteed delivery in 3d wireless sensor networks. In Proc. of ACM MOBIHOC, 2011.

Digital Library

[36]

X. Yu, X. Yin, W. Han, J. Gao, and X. D. Gu. Scalable routing in 3D high genus sensor networks using graph embedding. In Proc. of IEEE INFOCOM, mini-conference, 2012.

[37]

H. Zhou, N. Ding, M. Jin, S. Xia, and H. Wu. Distributed algorithms for bottleneck identification and segmentation in 3D wireless sensor networks. In Proc. of IEEE SECON, 2011.

[38]

H. Zhou, M. Jin, and H. Wu. A distributed delaunay triangulation algorithm based on centroidal voronoi tessellation for wireless sensor networks. In Proc. of ACM MOBIHOC, 2013.

Digital Library

[39]

D. Zhu, Q. Tao, J. Xing, Y. Wang, W. Liu, and H. Jiang. The extraction and evaluation of skeleton in sensor networks. In Proc. of IEEE Ninth International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2013.

Digital Library

[40]

X. Zhu, R. Sarkar, and J. Gao. Shape segmentation and applications in sensor networks. In Proc. of IEEE INFOCOM, 2007.

Digital Library

Cited By

Lu BWang QFan X(2021) An Optimized L 1 -Medial Skeleton Extraction Algorithm 2021 IEEE International Conference on Industrial Application of Artificial Intelligence (IAAI)10.1109/IAAI54625.2021.9699907(460-466)Online publication date: 24-Dec-2021
https://doi.org/10.1109/IAAI54625.2021.9699907
Yang YLiu WJiang HWang CWang DLin H(2018)SNP: A 1-Manifold Skeleton-Based Navigation Protocol in 3D Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.282269217:12(2912-2924)Online publication date: 1-Dec-2018
https://doi.org/10.1109/TMC.2018.2822692
Liu WJiang HLiu JLiao XLin HDeng T(2016)On the Distance-Sensitive and Load-Balanced Information Storage and Retrieval for 3D Sensor NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.252324224:6(3439-3449)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TNET.2016.2523242
Show More Cited By

Index Terms

Surface skeleton extraction and its application for data storage in 3D sensor networks
1. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Towards Robust Surface Skeleton Extraction and Its Applications in 3D Wireless Sensor Networks

The in-network data storage and retrieval are fundamental functions of sensor networks. Among many proposals, geographical hash table GHT is perhaps most appealing as it is very simple yet powerful with low communication cost, where the key is to ...
Optimize Storage Placement in Sensor Networks

Data storage has become an important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. Storage nodes are introduced in this paper to store the data collected from the sensors in their ...
Data storage placement in sensor networks
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing

Data storage has become a important issue in sensor networks as a large amount of collected data need to be archived for future information retrieval. This paper introduces storage nodes to store the data collected from the sensors in their proximities. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '14: Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing

August 2014

460 pages

ISBN:9781450326209

DOI:10.1145/2632951

General Chairs:
Jie Wu
Temple University
,
Xiuzhen Cheng
George Washington University
,
Program Chairs:
XiangYang Li
Illinois Institute of Technology
,
Saswati Sarkar
University of Pennsylvania

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc'14

Sponsor:

SIGMOBILE

MobiHoc'14: The Fifteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing

August 11 - 14, 2014

Pennsylvania, Philadelphia, USA

Acceptance Rates

MobiHoc '14 Paper Acceptance Rate 40 of 211 submissions, 19%;

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lu BWang QFan X(2021) An Optimized L 1 -Medial Skeleton Extraction Algorithm 2021 IEEE International Conference on Industrial Application of Artificial Intelligence (IAAI)10.1109/IAAI54625.2021.9699907(460-466)Online publication date: 24-Dec-2021
https://doi.org/10.1109/IAAI54625.2021.9699907
Yang YLiu WJiang HWang CWang DLin H(2018)SNP: A 1-Manifold Skeleton-Based Navigation Protocol in 3D Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.282269217:12(2912-2924)Online publication date: 1-Dec-2018
https://doi.org/10.1109/TMC.2018.2822692
Liu WJiang HLiu JLiao XLin HDeng T(2016)On the Distance-Sensitive and Load-Balanced Information Storage and Retrieval for 3D Sensor NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.252324224:6(3439-3449)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TNET.2016.2523242
Liu WDeng TYang Jiang HLiao XLiu JLi BJiang G(2016)Towards Robust Surface Skeleton Extraction and Its Applications in 3D Wireless Sensor NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.251634324:6(3300-3313)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TNET.2016.2516343
Liu WTao QZhang RJiang HWang YXing JWang LGeng Z(2016)ESP: Evaluation-Based Skeleton Pruning in Sensor NetworksIEEE Sensors Journal10.1109/JSEN.2016.253667916:11(4605-4613)Online publication date: Jun-2016
https://doi.org/10.1109/JSEN.2016.2536679
Liu WYang YPeng KJiang HLiao XWei WLi BXing J(2016)A General Framework of Skeleton Extraction in Sensor NetworksIEEE Sensors Journal10.1109/JSEN.2015.249626816:4(1103-1116)Online publication date: Feb-2016
https://doi.org/10.1109/JSEN.2015.2496268

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten