Document Text (Pages 31-40) Back to Document

ENHANCED COMPOSITE APPROACH WITH MOBILE BEACON SHORTEST PATH TO SOLVE LOCALIZATION PROBLEM IN WIRELESS SENSOR NETWORKS

by KUMAR, SUNIL


Page 31

position. But as traverse path has no routing algorithm that’s why power
consumption is maximum.

Chapter 3
PROPOSED WORK
3.1 PROPOSED MOBILE BEACON ALGORITHM USING SHORTEST
PATH
Several types of mobile elements capable of free movement are currently
available, e.g., Packbot [11] and Robomote [12]. In practice, the mobile element
cannot visit some positions due to physical obstacles. We assume that the
locations which are not traversable are known. To achieve the shortest path we
partitioned the deployment area into hexagon cells which is visit able location.
We only consider the minimal set of hexagons that cover the visit able region.
Due to power constraints, the mobile element is capable of only low-speed and
short-distance movement in practical deployments. For instance, the normal
speed of several mobile sensor platforms (e.g., Packbot and XYZ) is only 0.5 ~
2 m/s. An ABC mobile sensor node that is powered by two batteries can move
only about 165 meters before exhausting its power. Therefore, the movement
trace of the mobile beacon in deployment area must be efficiently planned or
controlled in order to maximize the number of localized unknown-position
sensors with the required high localization accuracy. Mobile beacon traverse
from the center point of each hexagon cell in deployment area and continuously
broadcast its position message using this information all blind nodes estimate its
position [13]. The mobile beacon assists the unknown nodes in localizing
themselves after the sensor node has been deployed [14]. It could be a human,
machine, a plane or other vehicles. The optimal movement schedule for mobile
beacon in our algorithm needs to achieve the shortest path length so that the
31


Page 32

mobile beacon covers the entire area with the shortest time and consumes the
minimum energy. Based on the derived localization error bound, we propose an
optimal movement schedule for mobile beacon as follows: When the mobile
beacon has no prior information about sensors’ positions, in order to guarantee
that each sensor is localized with error e, the entire geographical region should
be covered by disks with radii r centered at the beacon points of the mobile
beacon.

Figure 3.1: Enhanced mobile beacon trajectory

The most efficient coverage is the hexagonal tiling of the entire region, in which
the edge length of each hexagon is r and each beacon point is at the center of
each hexagon. In the optimal movement schedule of the mobile beacon, the
center of a hexagon is visited by the mobile beacon once. Obviously, the
shortest length of a path that crosses a hexagon is 3r. In the line by line scan as
shown in Figure 3.1, the shortest path length is achieved. Therefore, the line-byline
scan is an optimal movement schedule of the mobile beacon. When each
sensor has coarse prior information about its position, the mobile beacon does
not need to cover the entire region. Suppose there are N sensors and sensor i is
in region Ai with high probability. Let {Hi} denote the minimal set of hexagons
that covers the united regions Ui=1 to N Ai, where Hi is one of the hexagons in
the hexagonal tilings of the entire geographical region. Note that {Hi} can be
found by checking whether each hexagon has intersection with Ui=1 to N Ai,,
and hence in polynomial time. Construct an unidirectional graph G = (V, E),
32


Page 33

where V is the set of centers of {Hi} and E is the set of Euclidean distances
between any two points in V.
The movement schedule of the mobile beacon can be formulated as the shortest
Hamiltonian path problem. Specifically, given a starting point that is a vertex in
V, find the shortest path that visits each vertex in V exactly once. We note that
the problem of finding a Hamiltonian path is NP-complete and therefore the
problem of finding the shortest Hamiltonian path is also NP-complete [18]. This
algorithm is expensive because of using GPS. It is difficult to find the location
of all the nodes in mobile beacon algorithm. The optimal movement schedule of
the mobile anchor when no information about sensors’ positions is available.
The triangles represent the way points of the mobile anchor. The edge length of
each hexagon is r.
Finally the mobile beacon with global positioning system covers the shortest
path as it moves according to the algorithm, from middle of each hexagon cells.
Due to these hexagon cells the coverage error also reduces because there is no
such area where a range can not reach or no overlapping area. Require only one
GPS and covers shortest path which makes this approach cost saver as
compared to other approaches.

[3.2] PROPOSED ENHANCED COMPOSITE APPROACH
Each range free and range based techniques has some drawback, problem,
merits and demerits. To resolve all the problems Enhanced composite approach
is proposed, which is the enhancement of earlier composite approach. The main
aim of this proposed work in this given thesis is to solve localization problem
with high accuracy, low cost and use of minimum battery power.
The position of sensor node is identified by combining both range based and
range free techniques to reduce the positioning error with improved
performance and efficiency.
In this approach we combined the DV-hop method and proposed mobile beacon
33


Page 34

algorithm using shortest path, to give the high accuracy in localization with
minimum cost in wireless sensor network. This enhanced composite approach
has basically three steps. First, mobile beacon traverses the center position of
each hexagon cell and periodically broadcast the message with its position
information. Using this information some blind nodes which are in the range of
broadcasting, estimate its position using trilateration method. In trilateration
method it is must that blind node received more than three packets continuously
broadcast by mobile beacon for estimation of accurate position.

In step two, during mobile beacon movement some blind node locates
themselves as a static node then they play as a landmark role in DV-hop
method.
In third step, static beacon as a landmark when they are out of range of the
mobile beacon because till the mobile beacon in the range they cannot calculate
the hop distances. We need a threshold value to answer “when static node
become landmark in DV-hop”. Threshold value is the number of static node.
When the number of static nodes reaches the threshold value, all static nodes
become landmarks. Another method is when mobile beacon traversing for a
circle. In this way as mobile beacon moves, they can generate new static
beacons to provide the position information by using trilateration method and
after that when mobile beacon then out of range then using DV-hop method rest
of the blind node estimate its position. When blind node locates itself it
becomes beacon node for other blind nodes. So it spreads in the way like the
wave from the center to the outer region. The flow chart of this proposed
composite approach figure 4.1 includes above described three steps.
The proposed algorithm is designed to sole the problems existing in DV-hop
method. The main improvement is when the mobile beacon broadcast the
position information while traversing in the deployment region which is divided
in to hexagon cells and passing at the middle by using any shortest path
technique. When mobile beacon moves it generates new static beacons using
trilateration method. The accumulation and exaggeration of the errors in the
34


Page 35
DV-hop will not be the part of this method.
NO
Yes
Yes
NO
Yes
Yes
NO
Yes
Yes
35
START
Mobile beacon
with GPS
traversing at
middle in
hexagon cells
MB periodically broadcast packets as
moving
Unknown node
receiving packets
as in the range of
MB Count=0
Count++
If Count > 3
Some blind node become static node
using Trilateration method
MB is out of range or
reaches threshold
value

Page 36

No

Yes
Use DV-hop method

End

Figure 3.2: Flow Chart for Enhanced composite approach

Second DV-hop works well in the isotropic network. Even though the network
will be anisotropic, when using the enhanced composite approach and the
changing of topology is not required, because simply change the trajectory of
the mobile beacon solve the problem in simple way.
Third this algorithm is the incorporation of the range based and range free so the
measurement errors can be calibrated by the agitated DV-hop method. This
algorithm increases the flexibility to introduce a threshold value to control the
change agitating the DV-hop method.
The entire working of algorithm we can see in the figure 4.1, flow chart of
enhanced composite approach with mobile beacon shortest path to solve
localization problem in wireless sensor network. Mobile beacon with global
positioning system enabled device moves from the center of each hexagon cells
if yes then it broadcast the beacon message otherwise again start traversing from
initialization point. Unknown node starts receiving message from mobile
beacon as they are in the range of mobile beacon. There also runs a counter on
static node side, which count the number of message received by each blind
node. If counter value greater than three it means localization problem solved by
trilateration method and after we use DV hop method to localize other blind
nodes. If counter value less than three than uses DV-hop method only.

36


Page 37

Chapter 4
EVALUATION
The evaluation defines an inspection simulation experiment where our
algorithm will be evaluated and some important performances will be estimated.
The purpose of the evaluation is to create a virtual environment which imitates
the real environment to conduct the experiment. In this environment, the
proposed algorithm is evaluated and performance is compared to the DV-hop
method. The evaluation is running using MATLAB. The data is collected from
repeated simulations. The first step studies the DV-hop wireless sensor network.
In the second step, the proposed method is evaluated under the same settings. A
performance comparison is then made between the algorithm implemented and
the traditional DV-Hop method to the simulation result. There are two main
attributes to evaluate; average position error, and average communication
traffic. In the simulations, the unknown nodes are deployed randomly in a
region of 100 by 100 units. The mobile beacon traverses the sensor network
along the routine for the sake of precision and simplicity while broadcasting
beacon packets. Obviously, this trajectory is always optimal, so it is at good
enough to cover the simulation and get the anticipated results.
4.1 DV-hop simulation
The distributed unknown nodes are 20 in the given simulation environment.
Choose the number of randomly deployed beacons as the independent variable
and its range is from 3 to 10. Then simulation result of DV-hop is shown. Table
37


Page 38

4.1 illustrates that the nodes’ position computed out through DV-hop method
have deviated from the actual position value completely. Meanwhile, it also
shows that more beacons do not mean the more accuracy. Because of the
random deployment of the beacons, the result values are different in each
simulation. However, it can disclose the drawback of the traditional DV-hop
algorithm, depending on the topology and the error of the correction value used
to calibrating the distance for one hop.

No. of
beacons
Table 4.1 Average position errors and traffic of DV-hop
Average
traffic

Error
Intervals
3 18.87 3.0724
4 26.29 1.6703
5 32.52 1.5776
6 41.00 0.6304
7 50.70 0.7688
8 55.57 0.7015
9 62.07 1.1222
10 70.60 1.1381

38


Page 39

4.2 Mobile beacon simulation
The simulation of mobile beacon is similar to DV-hop algorithm. The
distributed unknown node is 20. Choose the number of randomly deployed
beacons as the independent variable and its range is from 3 to 10. Then
simulation result of mobile beacon is show in Table 4.2. The computed
algorithm shows that the values are different from the actual values. If the value
of the node is different then the position of the node would be completely
different. The result also shows that there are many errors in this evaluation.
These errors will affect the accuracy of the algorithm.

Table 4.2 Average position errors and traffic of the Mobile beacon

No. of
beacons
Average
traffic
Error
Interval
3 19.07 4.0153
4 28.27 1.9061
5 35.11 2.1342
6 44.21 1.0012
7 61.23 0.9105
8 67.11 1.0623
9 69.05 1.520
10 73.90 1.6424

39


Page 40

4.3 Composite approach simulation
The DV-hop performance depends on the network topology to a great extent
[21]. The setting is illustrated in table 4.3. Because of the trajectory of the
mobile beacon is in Figure 2.2, when the mobile beacon finishes the traversing
the whole region, all the beacon will form a relative isotropic topology. The
regular placements of the beacons reduce the errors effects on the algorithm
performance. Seven homogeneous distributor beacons are used for the DV-hop.
The unknown nodes are randomly increasing from the 20 to 100 at the
simulation area.

Table 4.3 Average position error and traffic of composite approach
No. of Average Error
40

© 2009 OpenThesis.org. All Rights Reserved.