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.
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.
CONSEL
Routing
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.