Call For Papers
Contact Us

  Advanced Routing Techniques for Large - Scale 2D/3D Sensor Networks using Segmentation  
  Authors : Aparna K Menon; Dr.Gnana Sheela K
  Cite as:


A sensor network generally consists of large number of sensor nodes which are deployed either inside the phenomenon or very close to it. Large scale 2D/3D sensor networks generally have irregular and complex topological structures. The traditional algorithms that are in use currently works well in convex geometry rather than in concave regions. Generally the existing segmentation algorithms are based on concave node detection that results in sensitivity of performance to boundary noise. In this work, the complex network is segmented into simple convex regions using connectivity based segmentation in large scale 2D/3D networks – CONSEL algorithm. The CONSEL is a scalable and distributed algorithm that is designed based on Morse function and convex components in Reeb graph of a network. The algorithm makes use of only connectivity information for segmentation. Firstly the boundary nodes in the network flood the region to construct the reeb graph. Then the mutex pairs are computed by the ordinary nodes in the region and coarse segmentation is done locally. The neighboring regions that are not mutex pairs are then merged together. It has both 2D and 3D segmentation capability. The traditional algorithm like greedy routing or geographic routing is thus adapted into a complex large scale 2D/3D environment.


Published In : IJCSN Journal Volume 5, Issue 1

Date of Publication : February 2016

Pages : 99-105

Figures :07

Tables : 01

Publication Link : Advanced Routing Techniques for Large - Scale 2D/3D Sensor Networks using Segmentation




Aparna K Menon : completed her B.Tech in Electronics and Communication Engineering under Mahatma Gandhi University. Presently she is pursuing M.Tech in Electronics with specialization in Wireless Technology under Cochin University of Science and Technology(CUSAT).

Dr. Gnana Sheela K : received her Ph D in Electronics and Communication from Anna University, Chennai. She is now working as a Professor, Department of ECE, Toc H Institute of Science and Technology. She has published more than 40 international journal papers. She is reviewer, editor and evaluator in various international papers. Also she is life member of ISTE.










Morse function

Reeb graph

Mutex pairs

Concave nodes

Convex nodes

Large scale 2D/3D sensor networks generally have complex irregular geometry, in which traditional algorithms does not exhibit optimum performance. The observed parameters such as like Packet Delivery Ratio (PDR), Signal-to-Noise Ratio, and energy consumption, from simulations of geographic routing as well as routing with help of CONSEL algorithm, indicated that traditional algorithms like geographic routing cannot be used to guarantee efficient routing in such large scale complex networks. The Greedy algorithms cannot resolve such dead-end or local minimum situation as in network concavities. Even techniques like convex segmentation fails to deliver accurate results due to the dependence of the routing and localization techniques on concave node detection. The CONSEL is a scalable and distributed algorithm that segments the network based on connectivity information alone and performs routing and localization with better accuracy. With this technique traditional algorithms like greedy routing and geographic routing are adapted into a large scale complex 2-D/3-D environment.










[1] B.Karp and H.T.Kung, “GPSR: Greedy perimeter stateless routing for wireless networks,” in Proc. ACM MOBICOM, pp. 243–254, 2000. [2] Savvides, C.Han, and M. B. Strivastava, “Dynamic fine-grained localization in ad hoc networks of sensors,” in Proc. ACM MOBICOM, pp. 166–179, 2001. [3] T.K.Dey, J.Giesen, and S.Goswami, “Shape segmentation and matching with flow discretization,” in Proc. Workshop Algor. DataStruct., pp. 25– 36,2003. [4] Panangadan and G.S.Sukhatme,“Data segmentation for region detection in a sensor network,” in Proc. DCOSS, pp. 1–12,2005. [5] Xianjin Zhu, Rik Sarkar and Jie Gao “Topological Data Processing for Distributed Sensor Networks with Morse-Smale Decomposition” IJEIT Vol 2, No. 12, 2005. [6] Stefan Funke " Topological Hole Detection in Wireless Sensor Networks and its Applications," DIALM-POMC'05, September 2005. [7] Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu and Chonggang Wang “Approximate Convex Decomposition Based Localization in Wireless Sensor Networks” in Proc.National Nat-ural Science Foundation of China under Grant, 2006. [8] X. Zhu, R. Sarkar, and J. Gao, “Shape segmentation and applications in sensor networks,” in Proc. IEEE INFOCOM, pp. 1838–1846, 2007. [9] B.Leong, B. Liskov, and R. Morris, “Greedy virtual coordinates for geographic routing,” in Proc. IEEE ICNP, pp. 71–80, 2007. [10] J.-M. Lien and N. M. Amato, “Approximate convex decomposition of polyhedra,” in Proc.ACM Symp.SolidPhys.Model, pp.121–131, 2007. [11] J. Bruck, J. Gao, and A. A. Jiang, “Map: Medial axis based geometric routing in sensor networks,” in Proc. Wireless Netw.,Vol.13, No.6, pp.835–853, 2007. [12] Nguyen, N. Milosavljevic, Q. Fang, J. Gao, and L. J. Guibas, “Landmarkselection and greedy landmarkdescent routing for sensor networks,” in Proc. IEEE INFOCOM, pp. 661–669, 2007. [13] M. Li and Y. Liu, “Rendered path: Range-free localization in anisotropic sensor networks with holes,” in Proc. ACM MobiCom, pp. 51–62, 2007. [14] O.Saukh, R.Sauter, M.Gauger, P.J. Marron, and K.Rothernel, “On boundary recognition without location information in wireless sensor networks,” in Proc. IPSN, pp. 207–218, 2008. [15] G. Tan, M. Bertier, and A.-M. Kermarrec, “Convex partition of sensor networks and its use in virtual coordinate geographic routing,” in Proc. IEEE INFOCOM, pp. 1746–1754, 2009. [16] G. Tan, H. Jiang, S. Zhang, and A.-M. Kermarrec, “Connectivity-based and anchor-free localization in large-scale 2D/3D sensor networks,” in Proc. ACM MobiHoc, pp. 191–200, 2010. [17] Bi Jun Li, Min Jung Baek, Se Ung Hyeon, and Ki-Il Kim, “Load Balancing Parameters for Geographic Routing Protocol in Wireless Sensor Networks, ” in Proc. IEEE INFOCOM, pp. 661–669, 2010. [18] 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. IEEE SECON, pp. 494–502, 2011. [19] H.Jiang, S.Jin, and C.Wang, “Predictionornot? An energy-efficient framework for clustering-based data collection in wireless sensor networks,” IEEE Trans. Parallel Distrib. Syst., Vol. 2, No. 6, pp.1064–1071, Jun. 2011. [20] S. Xia, X. Yin, H. Wu, M. Jin, and X. D. Gu, “Deterministic greedy routing with guaranteed delivery in 3D wireless sensor networks,” in Proc. ACM MobiHoc, Art. no.1, 2011. [21] Chi Zhang, Jun Luo, Liu Xiang, Feng Li, Juncong Lin and Ying He “Harmonic Quorum Systems: Data Management in 2D/3D Wireless Sensor Networks with Holes,” in Proc. AcRF Tier 2 Grant ARC15/11, 2011. [22] Hongbo Jiang, Tianlong Yu, Chen Tian, Guang Tan and Chonggang Wang, “CONSEL: Connectivitybased Segmentation in Large-Scale 2D/3D Sensor Networks,” in Proc. IEEE INFOCOM, 2012. [23] H. Jiang, S. Zhang, G. Tan, and C. Wang, “CABET: Connectivity-based boundary extraction of largescale 3D sensor networks: Algorithm and Applications,” in Proc. IEEE INFOCOM, 2014.