Connectivity-Based Segmentation in Large-Scale 2-D/3-D Sensor Networks: Algorithm and Applications

	Connectivity-Based Segmentation in Large-Scale 2-D/3-D Sensor Networks: Algorithm and Applications
	Hongbo Jiang; Tianlong Yu; Chen Tian; Guang Tan; Chonggang Wang
刊名	IEEE/ACM Transactions on Networking
	2015
英文摘要	Efficient sensor network design requires a full understanding of the geometric environment in which sensor nodes are deployed. In practice, a large-scale sensor network often has a complex and irregular topology, possibly containing obstacles/holes. Convex network partitioning, also known as convex segmentation, is a technique to divide a network into convex regions in which traditional algorithms designed for a simple network geometry can be applied. Existing segmentation algorithms heavily depend on concave node detection, or sink extraction from the median axis/skeleton, resulting in sensitivity of performance to network boundary noise. Furthermore, since they rely on the network's 2-D geometric properties, they do not work for 3-D cases. This paper presents a novel segmentation approach based on Morse function, bringing together the notions of convex components and the Reeb graph of a network. The segmentation is realized by a distributed and scalable algorithm, named CONSEL, for CONnectivity-based SEgmentation in Large-scale 2-D/3-D sensor networks. In CONSEL, several boundary nodes first flood the network to construct the Reeb graph. The ordinary nodes then compute mutex pairs locally, generating a coarse segmentation. Next, neighboring regions that are not mutex pairs are merged together. Finally, by ignoring mutex pairs that lead to small concavity, we provide an approximate convex decomposition. CONSEL has a number of advantages over previous solutions: 1) it works for both 2-D and 3-D sensor networks; 2) it uses merely network connectivity information; 3) it guarantees a bound for the generated regions' deviation from convexity. We further propose to integrate network segmentation with existing applications that are oriented to simple network geometry. Extensive simulations show the efficacy of CONSEL in segmenting networks and in improving the performance of two applications: geographic routing and connectivity-based localization.
收录类别	SCI
原文出处	http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6670788
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/6890]
专题	深圳先进技术研究院_数字所
作者单位	IEEE/ACM Transactions on Networking
推荐引用方式 GB/T 7714	Hongbo Jiang,Tianlong Yu,Chen Tian,et al. Connectivity-Based Segmentation in Large-Scale 2-D/3-D Sensor Networks: Algorithm and Applications[J]. IEEE/ACM Transactions on Networking,2015.
APA	Hongbo Jiang,Tianlong Yu,Chen Tian,Guang Tan,&Chonggang Wang.(2015).Connectivity-Based Segmentation in Large-Scale 2-D/3-D Sensor Networks: Algorithm and Applications.IEEE/ACM Transactions on Networking.
MLA	Hongbo Jiang,et al."Connectivity-Based Segmentation in Large-Scale 2-D/3-D Sensor Networks: Algorithm and Applications".IEEE/ACM Transactions on Networking (2015).