ENHANCED COMPOSITE APPROACH WITH MOBILE BEACON SHORTEST PATH TO SOLVE LOCALIZATION PROBLEM IN WIRELESS SENSOR NETWORKS
1.9.2 Future challenges in location discovery approaches:
Research on localization in wireless sensor networks can be classified into two
broad categories centralized and distributed. These algorithms are given by
researchers but there are some aspects which we will consider as a challenge in
126.96.36.199 Distributed Localization: If each node collects partial data and
executes the algorithm then localization algorithm is distributed.
188.8.131.52.1 Beacon-based distributed algorithms: Categorized into three parts:
• Diffusion: In diffusion the most likely position of the node is at the
centroid  of its neighboring known nodes. APIT requires a high ratio of
beacons to nodes and longer range beacons to get a good position estimate. For
low beacon density this scheme will not give accurate results.
• Bounding box: Bounding box forms a bounding region for each node
and then tries to refine their positions. The collaborative multilateration enables
sensor nodes to accurately estimate their locations by using known beacon
locations that are several hops away and distance measurements to neighboring
nodes. At the same time it increases the computational cost also.
• Gradient: Error in hop count distance matrices in the presence of an
184.108.40.206.2- Relaxation-based distributed algorithms:
The limitation of this approach is that the algorithm is susceptible to local
220.127.116.11.3- Coordinate system stitching based distributed algorithms:
The advantage of this approach is that no global resources or communications
are needed. The disadvantage is that convergence may take some time and that
nodes with high mobility may be hard to cover.
18.104.22.168.4- Hybrid localization algorithms:
The limitation of this scheme is that it does not perform well when there are
only few anchors. SHARP gives poor performance for anisotropic network.
22.214.171.124.5- Interferometric ranging based localization:
Localization using this scheme requires considerably larger set of measurement
which limits their solution to smaller network.
126.96.36.199 Centralized Localization:
If an algorithm collects localization related data from one station and execute it
from the same station then it is called centralized. In centralized model the
problem is that if computing server fails due to some problem then entire
processing goes down. Scalability is another problem when we consider the
centralized model for computation of our data. For security reasons this
approach is also not best. The techniques which are based on centralized model
are explained below.
The advantage of this scheme is that it does not need anchor or beacon nodes to
start with. It builds a relative map of the nodes even without anchor nodes and
next with three or more anchor nodes, the relative map is transformed into
absolute coordinates. This method works well in situations with low ratios of
anchor nodes. A drawback of MDS-MAP  is that it requires global
information of the network and centralized computation.
• Localize node based on Simulated Annealing:
This algorithm does not propagate error in localization. The proposed flip
ambiguity mitigation method is based on neighborhood information of nodes
and it works well in a sensor network with medium to high node density.
However when the node density is low, it is possible that a node is flipped and
still maintains the correct neighborhood. In this situation, the proposed
algorithm fails to identify the flipped node
• A RSSI-based centralized localization technique:
The advantage of this scheme is that it is a practical, self-organizing scheme that
allows addressing any outdoor environments . The limitation of this scheme
is that the scheme is power consuming because it requires extensive generation
and need to forward much information to the central unit.
188.8.131.52 Locally centralized approach:
This approach is combination of both centralized and distributed approach. It
has the advantage of both the approaches. It follows the cluster approach.
Problem is that the system become more complex and need more computation
for handling the network.
1.10 PROBLEM DEFINITION
There are many localization schemes for the localization of wireless sensor
network. Since each algorithm was developed to fulfill a different goal, they
vary widely in many parameters including accuracy, cost, size, configurability,
security, and reliability [9, 10]. The node localization problem for wireless
sensor networks has received considerable attention, driven by the need to
obtain higher location accuracy without incurring a large per-node cost
(monetary cost, power consumption and form factor). Despite the exports made,
no system has emerged as a robust, practical, solution for the node localization
problem in realistic, complex, outdoor environments . One such challenge is
how to accurately find the location of each sensor node, at a low cost. The node
localization problem has received tremendous attention from the research
community, thus emphasizing that it is an important problem and it’s hard to
resolve this problem. Despite the attention the localization problem for wireless
sensor networks has received no universally acceptable solution for realistic,
outdoor, environments. There are many problems regarding the localization but
accuracy and cost are more concerned.
1.10.1 Accuracy: Accuracy is very important in the localization of wireless
sensor network. Higher accuracy is typically required in military installations,
such as sensor network deployed for intrusion detection. However, for
commercial networks which may use localization to send advertisements from
neighboring shops, the required accuracy may not be lower.
1.10.2 Cost: Cost is a very challenging issue in the localization of wireless
sensor network. There are very few algorithms which give low cost but those
algorithms don’t give the high rate of accuracy.
1.10.3 Power: Power is necessary for computation purpose. Power play a major
role in wireless sensor network as each sensor device has limited power. Power
supplied by battery.
1.10.4 Static Nodes: All static sensor nodes are homogeneous in nature. This
means that, all the nodes have identical sensing ability, computational ability,
and the ability to communicate. We also assume that, the initial battery powers
of the nodes are identical at deployment.
1.10.5 Mobile Nodes: It is assumed that a few number of GPS enabled mobile
nodes are part of the sensor network. These nodes are homogeneous in nature.
But, are assumed to have more battery power as compared to the static nodes
and do not drain out completely during the localization process. The
communication range of mobile sensor nodes are assumed not to change
drastically during the entire localization algorithm runtime and also not to
change significantly with in the reception of four beacon messages by a
particular static node.
The following issues will be addressed in this thesis.
• How to develop a localization algorithm fulfilling the tight bounds of
• How to get high accuracy and shortest path to solve localization
problem in wireless sensor network.
• How to approach the universal use of a single algorithm.
The goal of this thesis is to provide a good solution for localization problems in
the wireless sensor networks with high accuracy and low cost which comes
when the mobile beacon moves the shortest path in deployment area. The focus
will mainly be on accuracy in the localization of wireless sensor network as well
as low cost. Some existing algorithms for localization will be analyzed and
propose a new approach that can be used in more situations. Many of the
existing algorithms will be evaluated to understand the problem. A survey of
existing algorithms for localization in wireless sensor networks will be made,
and be used as a basis to design an algorithm that can be used in many
In next chapter 2 we present related work in wireless sensor network. A lot of
research has been done in this area and much more is still needed because of
cost, power and accuracy are the constraints, where we need to improve. We
propose an approach which works in both, range free and range based technique
to improve all the constraints. In chapter 3 we present our proposed work which
is enhancement of previous composite approach. We propose an algorithm with
mobile beacon shortest path to solve localization problem in wireless sensor
network, we combined the proposed work with DV-hop method, called
Enhanced composite approach. This is unique approach which follow both
range based and range free techniques in wireless sensor network. In chapter 4
we have presented and compared the simulation results of enhanced composite
approach with mobile beacon method, DV-hop method and previous composite
approach. In chapter 5 we present conclusion and future scope of this enhanced
ALGORITHMS FOR LOCALIZATION
The existing algorithm for localization can be broadly classified into two basic
1. Range based techniques and Range Free Techniques.
In range based mechanisms, the location of a sensor node can be determined
with the help of the distance or angle metrics. These metrics are Time of Arrival
(ToA), Time Difference of Arrival (TDoA), Angle of Arrival (AoA), Received
Signal Strength Indicator (RSSI). Range based techniques are highly accurate
but, they are equipped with highly expensive hardware and requires a lot of
computation. It increases the cost of the network and is inefficient in terms of
computations. The various range based techniques are Radio Interferometric
Measurement (RIM) , Multidimensional Scaling (MDS) , 3D -
Landscape , DV-distance, DV-hop, Euclidean distance  etc. In range
free techniques, the position of sensor node is identified on the basis
information transmitted by nearby anchor nodes or neighboring nodes, based on
hop or on triangulation basis. The various range free techniques are APIT ,
chord selection approach , three dimensional multilateration approach ,
SerLOC , centroid scheme  etc. Many more techniques are discussed in [4,
8, 13, 15, 17, 18] . The range free techniques have an error in accuracy up to
10% of the communication range of individual node . But, these techniques
are much cheaper than the range based techniques.
In , Ou and Ssu have proposed a range free localization approach for three
dimensional wireless sensor networks. In this approach a GPS equipped flying
anchor is moved around a region under surveillance and it continuously
broadcasts its position information. These messages help other sensor nodes to
compute their location. This scheme was proved to be better than any existing
range free localization scheme for three dimensional wireless sensor networks.
The basic assumption in this work is that the nodes are static. Thus, for every
run of the algorithm the flying anchor will be required to fly in the network. As,
the flying anchor node is not a participating node in the WSN, it is impractical
to be used in case of applications where sensors are more prone to
displacements. In such applications, the network needs to have the ability to
self-localize, whenever required. For this purpose, we need have few GPS
enabled sensor nodes within the region to be monitored. These nodes will help
other nodes to determine their location based on the positional information
about themselves. Further, in case of any discrepancy, the sensor nodes may
send an error message to base station regarding its dislocation. The base station
will generate a query message to other stations.
The Global positioning system (GPS) enabled sensor nodes will broadcast their
locations. With the help of this location information, the displaced node can
compute its new location. The above discussed strategy can be achieved by two
1. Enable a few static sensor nodes in the network with GPS equipped
devices. These nodes will help in locating their neighbors depending on the
placement strategy. The rest of sensor nodes will collectively get localized with
the help of their respective neighboring nodes.
2. Take a few GPS enabled mobile sensor nodes to move within the network
and help in locating the other sensor nodes.
The main drawback in using static sensor nodes is that, these nodes get their
location computed with the help of locations of their neighboring nodes as
proposed in . If there is an error while computing the nodes location, this
error gets rippled in computations related to next tiers of neighbors and so on.
Hence, the anchor nodes which are the most vital part of the localizing scheme
must be a part of the network and preferable mobile in nature.
Here we will discuss some existing algorithms and techniques which are used to
solve localization problem in wireless sensor network. Each algorithm has some
merits and demerits, play important role as per the application requirement. We
discuss here only two type of algorithm DV-hop and mobile beacon.
Localization with high accuracy and low cost in wireless sensor network is still
under exploration. Only a few researchers have tried to address the problem
using both range based and range free techniques. S.Rao  addressed a
scheme “A Composite approach to deal with localization problem in wireless
sensor network”. In this technique combined two approaches (A) DV- Hop and
(B) Mobile beacon.
A. DV-HOP ALGORITHM FOR LOCALIZATION
DV- hop algorithm composed of 3 steps.
1. Information of position at each node.
2. Estimation of distance for one hop.
3. Estimation of position.
Figure 2.1: DV-HOP analysis diagram.
The first step of the algorithm is the flooding of the position of sources through
the network. Each node and sources record their hop-distance with other sources
in the network. Sources try to find out the average length of one node and this
process is called hop correction . The other nodes wait for the first
It broadcast this information to the other nodes after accepting this. Now, the
nodes do not need to wait any more and it directly goes to next step. In the last
step, the nodes try to find out their position according to number of hops
recorded for each source and to the hop correction.
Landmarks K1, K2, K3 are shown below in figures 2.1. Actual distance
between landmarks is also mentioned. The landmarks calculate the average
distance of each hop.
• K1: (12+18)/ (3+4) =4.23.
• K2: (12+10)/ (3+2) = 4.40.
• K3: (10+18) / (2+4) = 4.67.
The average distance can be used to correct the position. The node A is getting
its direction from K2. The distance can be obtained as:
• A-K1: 2*4.4=8.8.
• A-K2: 1*4.4=4.4.
• A-K3: 2*4.4=8.8.
Accuracy of this algorithm varies with the accuracy of distance between the
hops. The node A gets the direction from the given landmarks as in figure 2.1
but problem is that there are three different landmarks. So node A will get three
coordinates which is more ambiguous because A will get three distances from
its actual position in the mean time. The concept of beacon is used to solve this
problem. More than three beacon nodes are needed to overcome this problem.
Accuracy of this algorithm is very low because the average distance per-hop is a
rough estimation so it is difficult to find the accurate distance between the hops.
This algorithm works properly when shapes are same or shapes are regular but it
does not work for irregular shapes. This is the biggest drawback of this
algorithm. There are many problems which need to be resolved. The solution of
these problems is available in the improved DV-Hop algorithm. DV-hop
algorithm is invalid for irregular shapes. The accuracy level is very low, and it
is difficult to find out the actual distance between the hops.
B. MOBILE BEACON ALGORITHM FOR LOCALIZATION
This method is an alternative for centralized approach. A node which locates
itself is called Beacon node. A mobile beacon could be a human, machine, plane
or any vehicle which is movable in deployment area. Trajectory is a path
followed by moving beacon in the deployment area. This algorithm is expensive
because of GPS system. Both DV-hop and mobile beacon approaches have its
own merits and demerits. S.Rao  combined both approaches and designs a
composite approach which is a bit better than other two methods.
Mobile beacon trajectory
Figure 2.2: mobile beacon trajectories
In mobile beacon approach a mobile beacon traverse the area randomly where
sensors are deployed. Using trilateration method some blind node estimate its