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

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

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

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

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

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

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

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

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

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

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