Wireless Sensor Network, 2010, 2, 43-47
doi:10.4236/wsn.2010.21006 anuary 2010 (http://www.SciRP.org/journal/wsn/).
Published Online J
A New Algorithm of Self Organization in Wireless
Sensor Network
Hemanta Kumar KALITA, Avijit KAR
Department of Computer Engineering, Jadavpur University, Kolkata, India
Received September 6, 2009; revised October 10, 2009; accepted October 13, 2009
Abstract
Self organization is one of the most important characteristics in an Ad-hoc Sensor Network. Thousands of
Sensors are deployed in a geographical area randomly without considering the location factor. After deploy-
ment, sensors are to self organize themselves to form a network of their own. How well the network is
formed determines the life of the whole network as well as the quality of data transmission. Self organization
based on clustering has proven to be very useful in this regard. Since hierarchical clustering reduces energy
consumption by routing data from one node to another. In this paper, we discuss a new algorithm for self
organization of sensors deployed in a geographical area. The algorithm forms clusters of sensors by ordering
them using a unique triangulation method. This algorithm not only considers all sensors but also groups them
so that their inherent clustering property is preserved.
Keywords: Self-Organization, Wireless Sensor Network, OPTICS
1. Introduction
Sensor network is a computer network of many spa-
tially distributed devices using sensors to monitor con-
ditions at different locations such as temperature, sound,
vibration, pressure, motion or pollutants. Usually these
devices are small and inexpensive, so that they can be
produced and deployed in large numbers, and so their
resources in terms of energy, memory, computational
speed and bandwidth are severely constrained. Each
device is equipped with a radio transceiver, a small mi-
cro controller and an energy source, usually a battery.
The devices use each other to transport data to a moni-
toring computer [1]. Data from the sensors is aggre-
gated and analyzed by a computer outside the network.
This computer is connected to the network by a special
network node called gateway node [2]. Sensor networks
involve three areas: sensing, communications and
computation. In other words, hardware, software and
algorithms [3,4].
An Ad hoc Sensor Network is a self-organizing multi-
hop wireless network, which relies neither on fixed in-
frastructure nor on predetermined connectivity [5]. This
property enables rapid deployment without precise prior
knowledge of the coverage area of interest - hence serves
well for situations lacking fixed infrastructure or high
risk, e.g., in military communications, disaster manage-
ment, law enforcement, and etc [6]. In this paper we
propose a new algorithm for Self Organization of Sen-
sors in an Ad hoc Sensor Network [7 ].
Remainder of the paper is divided into four sections.
In Section 2, we discuss related work. In Section 3, we
propose a new algorithm for self organization of sensor
nodes in an ad hoc sensor network. Section 4 is for the
experimental results and Section 5 finally concludes the
paper.
2. Related Work
In [8] proposes a Self Organizing Sensor (SOS) network
based on an intelligent clustering algorithm which does
not require many user defined parameters and random
selection to form clusters. The proposed SOS algorithm
can reduce the n umber of clu ster heads.
[9] discusses Ultra-wideband (UWB) technology.
UWB has proven to be useful in short range, high data
rate, robust, and low power communications. These fea-
tures can make UWB systems ideal candidates for reli-
able data communications between nodes of a wireless
sensor network (WSN). However, the low powered
UWB pulses can be significantly degraded by channel
noise, inter-node interference, and intentional jamming.
[9] presents a novel interference suppression technique
for UWB based WSNs that promises self-organization in

H. K. KALITA ET AL. 44
terms of power conservation, scalability, and channel
estimation fo r t he ent i re di st ri buted network.
[5] approaches to achieve an emerging distributed per-
ception of the sensed environment in real-time through
clustering. Research in classifying and recognizing com-
plex concepts has been directing its focus increasingly on
distributed sensing using a large amount of sensors. The
Colossal amount of sensor data often obstructs traditional
algorithms in centralized approaches, where all sensor
data is directed to one central location to be processed.
Spreading the processing of sensor data over the network
seems to be a promising option, but distributed algo-
rithms are harder to inspect and evaluate. By using
self-sufficient sensor boards with short-range wireless
communication capabilities, [5] are exploring this.
Bio-inspired communication methodologies promise
to enable more scalable selforganizing network infra-
structures. Especially in the area of mobile ad hoc sensor
networks, such solutions are required in order to qualify
them for simplified development and deployment based
on autonomously evolving mechanisms to work on
global tasks, i.e. to show an emergent behavior. [10] in-
troduce their ongoing research of Autonomic Network-
ing focused on the developments on efficient data dis-
semination in sensor networks. A particular example of
how to study biological processes and to adapt the results
in communication networks, the feedback loop mecha-
nism, depicts the potentials of this research area.
[11] develop an energy-aware self organized routing
algorithm for the networking of simple battery powered
wireless micro-sensors (as found, for example, in secu-
rity or environmental monitoring applications). In these
networks, the battery life of individual sensors is typi-
cally limited by the power required to transmit their data
to a receiver or sink. Thus effective network routing al-
gorithms allow reducing this power and extending both
the lifetime and the coverage of the sensor network as a
whole. However, implementing such routing algorithms
with a centralized controller is undesirable due to the
physical distribution of the sensors; their limited local-
ization ability and the dynamic nature of such networks
(given that sensors may fail, move or be added at any
time and the communication links between sensors are
subject to noise and interference). Against this back-
ground, [11] present a distributed mechanism that en-
ables individual sensors to follow locally selfish strate-
gies, which, in turn, result in the self organization of a
routing netw or k wi t h desi rable global proper t ie s [12, 13].
3. Proposed Algorithm
The idea of a new algorithm for self organization of sen-
sor nodes in an Ad hoc Sensor Network stems from our
original work on spatial clustering. Again, from our
study of routing issues of wireless sensor network [14],
we have found that–cluster based method has lots of ad-
vantages too. A great spatial clustering algorithm called
OPTICS [15–18] has noble idea of ordering point data to
get arbitrary shaped cluster. Our new algorithm is pri-
marily based on OPTICS. But, the new algorithm, orders
sensor nodes by an unique method of triangulation
[19,20]. When the ordering procedure is over, all the
sensor nodes form a network of their own and become
member of a cluster.
Our goal is to design an algorithm for self organization
of sensor nodes in an Adhoc Sensor Network. The algo-
rithm should be able to connect all sensor nodes. At the
same time, sensor nodes should self organize in such a
way that resource usage, for example, battery power is
minimum [21]. This is possible only when the inherent
clusters are detected by the algorithm [22].
The new algorithm self organizes sensor nodes by
forming cluster. Clusters are formed by an ordering pro-
cedure which has similarity with the OPTICS Algorithm.
In our approach we have assumed that a better quality
cluster means sensor nodes in that cluster use minimal
resource for sensing, communicating and receiving data.
3.1. Definitions
We define some terminologies which will be used while
discussing our Algorithm1.
Definition 1 Point: A Point is a senso r node deployed
in a geographical area. In our algorithm, we assume that
the Point can communicate with another Point using
wireless media.
Definition 2 Edge: An Edge
A
B connects two Points
A and B. Weight of an Edge, is the time required to
send a request from A to B and getting response from B
to A [23]. Such three edges connecting three Points A, B
and C form a triangle.
Definition 3 minTriangle: A triangle |
A
BC formed
by three Points A, B and C is a minTriangle if the sum-
mation of weights of the three edges
A
B, BC and
CA is minimum out o f all possible triangles consid ering
A
B as one Edge in the geographical area.
Definition 4 Live Edge: This is an Edge whose two
Points will be the two Points of the next minTriangle
3.2. The Algorithm
INPUT: A Set of Points spread on a geographical area.
OUTPUT: Clusters of Points connected to each other
based on the W eights.
1The terms defined here are to make it suitable for describing the new
algorithm. We do not know, if exactly the same definition exists fo
r
these or not. Step-1: Choose a Poin t, A randomly.

H. K. KALITA ET AL. 45
Step-2: Find another Point, B such that is minimum.
Mark Points A and B as connected. Initially,
A
B is a
live edge.
the total number of Points. This can be further redu ced if
we make the algorithm distributed.
4. Experimental Results
Step-3: Find a new point C such that triangle |
A
BC
is a minTriangle. Also, mark Point, C as connected.
The algorithm is implemented using Java and experi-
mented on Linux 8.0 platform. We have used synthetic
Point2 data sets. Figure 1 shows initial isolated Points.
Step-4: Choose a new live edge out of
A
C and BC.
Step-5: If then
A
C is the new live edge.
A
BAC.
Step-6: Else, BC is the new live edge.
A
BBC. In Figure 2, the algorithm finds the first minTriangle.
Step-7 Repeat steps 3–6 until all Poin ts are Connected. In Figure 3, we see how the algorithm proceeds by
finding minTriangles step by step.
3.3. Analysis Finally, in Figure 4, we see how the Points get con-
nected. It is clear from Figure 4 that Points are connected
first in their own cluster. Then one cluster gets connected
to another cluster.
The self organization algorithm that we have described is
very simple. Time complexity is , where is
2
()On n
Figure 1. Input—A set of points.
Figure 2. First minTriangle.
2Note that a Point is a Sensor Node.

H. K. KALITA ET AL. 46
Figure 3. After finding few triangles.
Figure 4. Output—Triangulation of the whole points.
Figure 5. Scalability of the proposed algorithm.

H. K. KALITA ET AL.
47
We have performed scalability test of the algorithm in
a machine with CPU speed 2.0 GHz and memory size
128 MB. In this regard, ten experiments were done by
choosing size of Point data set from 10000 to 100000.
Data sets are generated using randomizer. Outcome of
these experiments are shown in the graph of Figure 5.
From the graph we see that the algorithm is scalable for
large Point data set.
5. Conclusions
In this paper, we have proposed a new algorithm for self
organization of sensors in an Ad hoc Sensor Network
based on OPTICS [14] and OPTICS (BOPT) [18]. We
also demonstrated how the algorithm works. And, scal-
ability is not too high but moderate. This can be im-
proved further by making the algorithm distributed. Also,
we did not consider the security [24,25] aspect while
discussing the algorithm. This is part of our ongoing re-
search.
6. References
[1] M. B. Srivastava and C. Schurgers, “Energy efficient
routing in wireless sensor networks,” 2000.
[2] D. Ganeshan, A. Cerpa, W. Ye, Y. Yu, J. Zhao, and D.
Estrin, “Networking issues in wireless sensor network,”
2003.
[3] H. Kumar and K. R. Gurung, “Routing issues in wireless
sensor network,” Network, Data Mining & AI, Narosa
Pub, ISBN 81-7319-755-5, 2006.
[4] J. Ibriq and I. Mahgoub, “Cluster based routing in wire-
less sensor networks: issues and challenges,” SPECTS’04,
No. 759, pp. 1, 2004.
[5] K. V. Laerhoven, E. Catterall, and M. Strohbach,
“Self-organization in ad hoc sensor networks: An em-
pirical study,” in Artificial Life VIII, Standish, Abbass,
Bedau (eds) (MIT Press), pp. 260–263, 2002.
[6] R. Batta, R. Nagi, A. Joshi, and N. Mishra, “Ad hoc
sensor network topology design for distributed fusion: A
mathematical programming approach, ” 2003.
[7] R. Wattenhofer, “Algorithms for ad hoc and sensor net-
works,” 2005.
[8] A. Abraham, K. Shin, and S. Y. Han, “Self organizing
sensors by minimization of cluster heads using intelligent
clustering,” 2004.
[9] A. Spiridon, F. Nekoogar, and F. Dowla, “Self organiza-
tion of wireless sensor networks using ultra-wideband ra-
dios,” UCRL-CONF-205469, 2004.
[10] G. Fuchs, R. German, F. Dressler, and B. Krger,
“Self-organization in sensor networks using bio-inspired
mechanisms,” 2005.
[11] E. David, A. Rogers, and N. R. Jennings, “Self-organized
routing for wireless micro-sensor networks,” 2004.
[12] V. Ailawadhi, K. Sohrabi, J. Gao, and G. J. Pottie, UCLA,
“Protocols for self-organization of a wireless sensor net-
work,” IEEE Personal Communications, 2000.
[13] D. Starobinski and R. Krishnan, “Message-efficient self-
organization of wireless sensor networks,” 2001.
[14] H. K. Kalita, “Securing wireless sensor network,” NCS-
2005, Allied Pub, ISBN 81-7764-931-0, 2005.
[15] M. Ankerst, M. M. Breunig, H. P. Kriegel, and J. Sander,
“Optics: Ordering points to identify the clustering struc-
ture,” In Proceedings of ACM SIGMOD’99, Institute of
Computer Science, University of Munich, Germany,
1999.
[16] J. Han and M. Kamber, “Data mining: Concepts and tech-
niques,” Morgan Kaufmann, San Francisco, CA, USA,
2003.
[17] Z. Huang, “Clustering large data sets with mixed numeric
and categorical values.”
[18] E. Kolatch, “Clustering algorithms for spatial databases:
A survey,” 2001.
[19] H. Kalita, “A new algorithm for ordering of points to
identify clustering structure based on perimeter of trian-
gle: Optics(bopt),” Master’s thesis, Department of Com-
puter Sc & IT, Tezpur University, Assam(India), 2004.
[20] C. Eldershaw and M. Hegland, “Cluster anaysis using
triangulation,” Computational Techniques and Applica-
tions World Scientific, 1997.
[21] D. Estrin, Y. Yu, and R. Govindan, “Geographical and
energy aware routing: A recursive data dissemination
protocol for wireless sensor networks,” 2001.
[22] G. Gupta and M. Younis, “Load-balanced clustering in
wireless sensor networks,” 2003.
[23] J. F. Roddick, K. Hornsby, and D. d Vries, “A unifying
semantic distance model for determining the similarity of
attribute values,” 2003.
[24] W. S. Shi, J. P. Walters, Z. Q. Liang, and V. Chaudhary,
“Wireless sensor network security: A survey,” Sec urity in
Distributed, Grid, and Pervasive Computing, Yang Xiao,
Auerbach Publications, CRC Press, 2006.
[25] C. Karlof and D. Wagner, “Secure routing in wireless
sensor networks: Attacks and countermeasures,” Ad Hoc
Networks 1 (2003) 293315, 2003.