 Open Access
 Total Downloads : 23
 Authors : Bindu Madhavi P, Dr. M. Nagendra
 Paper ID : IJERTCONV3IS19115
 Volume & Issue : ICESMART – 2015 (Volume 3 – Issue 19)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Improved Localization Method of Wireless Sensor Networks with a Three Anchor DVHop Algorithm
Bindu Madhavi P Dr. M. Nagendra
Ph.D Scholar Professor
Department of computer science & Engg S.K.University, Anantapur, A.P
Department of computer science & Engg S.K.University, Anantapur, A.P
Abstract Location Information of nodes is mandatory for so many applications in WSN. Basically two types of localization algorithms are used in WSN. Range Based & Range free algorithms are used to locate the nodes in WSN. Due to the draw back in Range Base approaches we will use Range free approaches to localize the nodes. In this paper hopbased range free localization method is used. In the hop based method anchors (reference nodes) transmit the location messag es to the entire network based on hop count. Localization of nodes depends up on the received messages from anchors. The individual position of the nodes and the distance between the nodes is measured based on the received messages from the anchors. The estimative distances can results large error, and have an effect on the localization accuracy. To resolve the problem, this paper proposes an algorithm, which makes the mysterious nodes fix the close by anchor as a reference and choose the two other anchors which are the most precise to achieve the estimated location. Compared to the existed DV Hop algorithm, the proposed algorithm has less average localization error and is more efficient from the experiment results.
Keywords Three Anchor DVHop Algorithm, Localization, Average location error, wireless sensor networks (WSNs).

INTRODUCTION
Location Information of nodes is mandatory for so many applications in WSN in order to identify the nodes and to route the packets with minimum distance to the accurate location. Range Based & Range Free is the two types of Localization algorithms. Rangebased algorithm is used to compute the exact distance between the nodes and then use the information to localize the nodes. Range based algorithms attain good localization results, with diverse kinds of techniques such as: Time of arrival (TOA) [6], Time
algorithm achieves high accuracy which is an alternative cost effective approach.
One of the most use full range free localization algorithm is DVHop based on the estimated hop distance. In a network for the DVhop algorithm, the node distribution is random which causes a big error.
To overcome this problem we propose an algorithm [13] to correct the position of DVHop, based on the estimated distance to the nearest anchor. An [14], improved DVHop algorithm consists of selective Threeanchor DVhop algorithm, based on the connectivity vector. In this paper the development of algorithm is specified through two steps in which a mysterious node can calculate its position by selecting three anchors with reference to the nearest one.
The organization of this paper is as follows: DVHop algorithm is presented in Section II, Localization problem is presented in section III. The connection between the nearest anchor and the minimal error is presented in section IV. The proposed and improved algorithm is introduced in section V. Simulation and results are provided in Section VI. Conclusion of the paper is given in the last section.

DVHOP ALGORITHM
Dargos Niculesu and Badri Nath proposed a algoritm called DVHOP which is a distributed hop by hop positioning algorithm.The execution of the program involves three steps.After hop count values to all anchor nodes.In the next step,when the anchor assigns hop count value to other anchors,average size of onehop is approximated.Then the approximated average is conveyed to the whole network.The average size is calculated using the formula:
2
2
difference on arrival (TDOA) [7], Angle of arrival [8], and
Received signal strength indicator (RSSI) [9], [10]. Range free algorithm takes only network connectivity information between anchor nodes and mysterious nodes or information
Hopsizei
j i
=
(xi

x j ) ( y
2
i
i
h

y j )
of hop count to localize the nodes. The various Rangefree
j i ij
(1)
techniques are centroid algorithm, DVHop algorithm, APIT algorithm [11], and SequenceBased algorithm [12].The localization results offered by rangebased approaches are more accurate than the rangefree approaches but it requires additional Hardware which is expensive for implementation. Without any Hardware requirements Range free localization
The coordinates of i and j are (xi ,yj) and (xj,yi) respectively. hij are the hops between anchor i and anchor j. After all mysterious nodes have acknowledged the hopsize from anchor nodes which have the minimum hops between them; they calculate the distance to the anchor nodes based on two
factors: size of the hop and least hop count hid , using the following formula:
di hid * HopSize i (2)


LOCALIZATION CRISIS
Due to the difference between the estimated coordinate and the actual coordinate we will get localization problem. The formula for the fault location is given by
From second step, the position of the mysterious nodes is
measured according to the distance with each anchor node. The coordinates of the mysterious node is (x, y), and the
coordinates of anchor i is ( xi , yi ). Assume di is the distance
Errorn
(x'n
xn )

( y'n
2
2
yn )
(8)
between anchor nodes to mysterious nodes, then we have the following formula:
The estimated coordinates of node N are
(x' , y' ) respectively and the actual coordinates of node
(x x )2 ( y y )2 d 2
n n
N are (xn , yn ) respectively. The Average localization
2
2
2
2
1 1 1
error is the most important decisive factor from the
(x x2
.
)2 ( y y
)2 d 2
localization. The average error articulated in terms of percentage is as follows:
.
.
N
N
1
1
2 2 2
AveError
Errorn *100%
(x xn ) ( y yn ) dn
(3)
NR n1
(9)
The above formula can be introduced with the subsequent linear equation:
AP = B. Where
x
P = y
Here R is the communiquÃ© radius and N is the quantity of nodes.


CONNECTION BETWEEN THE NEARBY ANCHOR AND THE LEAST ERROR
x1 xn
y1 yn
(4)
The principle of our algorithm is elucidated by a distinctive instance of network topology, which operates in a 50*50m 2
x
x
A 2 * 2

xn
y2 yn
area with 10 nodes haphazardly disseminated inside this area. The range of communication for all the nodes is established
…………
…………
to 20m. The known nodes are anchors which know their position in a network. The four known nodes are: A1, A2, A3
xn1 xn
yn1 yn
(5)
and A4, are nearby among the 10 nodes. The left over nodes are the normal nodes that are N1 N2 .N6, which they do not know their positions. The example is shown below
d 2 d 2 x 2 x 2 y 2 y 2
1 n 1 n 1 n
d 2 d 2 x 2 x 2 y 2 y 2
1
B .
.
.
n 1 n 1 n
d 2 d 2 x 2x 2 y 2
y 2
1 n
n1 n
n1 n
(6)
Least square method is used to attain the position of the mysterious node which is articulated as:
P ( AT A)1 AT B
(7)
Fig. 1 10 nodes randomly deployed
The least number of hops and the distance that separates itself from each anchor can be obtained by the standard nodes by using the first two steps of DVhop algorithm. Following
a
a
i
i
which, the mysterious node Ni computes its probable position by multilateration. Consider a network of Na anchors; it is preferred to compute distance of Ni using 3 distances from 3 different anchors by employing trilateration, instead of using all the estimated values. From Na anchors, the total 3anchor groups are C 3 N groups. So, N can
a
a
obtain C 3 N estimated positions. In our instance, the number of anchors is four. Hence we can have four 3 anchor groups that are: (1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4). By the
process of trilateration using (7) we can measure the
estimated position of the mysterious nodes of the above mentioned different combinations.

Familiarity:
The results of simulations corresponding to location errors for different combinations are tabulated as follows:
TABLE1 Comparison Between The Various Errors Of Different Combinations
Nodes\Combi nations
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
N1
9.401
3.925
19.941
72.242
N2
14.369
18.456
74.318
37.352
N3
3.527
13.442
115.28
27.96
N4
6.745
9.977
39.355
14.132
N5
1.524
6.456
12.073
3.401
N6
6.538
1.113
6.014
30.563
Different errors from 4 different combinations for each node are specified in the above table. The minimal error for each node, its equivalent combinations and its nearest anchor are grouped in the following table. The error given by DVHop is also present in this table.
TABLE2 Relationship Between the Minimal Error And The Nearest Anchor
Nodes
DV Hop Error
The minimum Error for Each Node
The equivalent Combination
The Nearest Anchor
N1
8.813
3.925
(1,2,4)
1
N2
12.796
14.369
(1,2,3)
1
N3
8.690
3.527
(1,2,3)
2
N4
7.334
6.745
(1,2,3)
3
N5
3.970
1.524
(1,2,3)
4
N6
3.144
1.113
(1,2,4)
4
We can perceive the following observations from the table 2:

The minimum error values provide a better precision than DVHop error.

Except for node 5 the existence of nearest anchor with its combinations gives the minimal error. The error value for node 5 through its nearby anchor is of "3.401", which is smaller than that given by DV hop.

The only exceptional case is that of Node 2 that has a greater error than indicated by the classical DV Hop algorithm.


Analysis of Results: The results can be comprehended as follows:

It is not necessary that many anchors, always give good results.

It is sufficient if just 3 anchors are well positioned geographically in relation to the anonymous nodes, can improve the accuracy of the position.

The number of hops which lies in between N2 and the anchors A1, A2, A3 and A4 are 1, 2, 3and 4 respectively.

By assuming that there exists a virtual node N7, whose coordinates are the average positions of neighboring anchors, we can reduce the number of hops which exists between N2 and anchors 3 and 4.
where m is the number of anchors and (xi ,yj) are their different coordinates. The following results can be found.
TABLE3 Relationship Between the Minimal Error And The Nearest Anchor With Addition of Virtual Node N7.
Nodes
Minimal Error
Minimal Error with Virtual Node
The equivalent Combination
The Nearest Anchor
N1
3.925
3.925
(1,2,4)
1
N2
14.369
1.1221
(1,2,4)
1
N3
3.527
3.527
(1,2,3)
2
N4
7.334
6.745
(1,2,3)
3
N5
3.401
3.401
(2,3,4)
4
N6
3.144
1.113
(1,2,4)
4

The bold values in the table are modified by the addition of virtual node N7. The number of hops of N2 to anchors A1, A2, A3 and A4 (1, 2, 3 and 3) changes to (1, 2,2 and 2) respectively.

Thus we can infer from these results that It is very significant of adding a virtual node in order to reduce the error of node 2.

In node 2 the nearest anchor remains unchanged, where as the column containing the combination and new minimal error of node 2 is changed.

The other nodes will maintain the same error values, combinations and nearest anchors.

Note: If we change the communication radius from 20 to 21 meters we can find similar results. Hence we can conclude that whenever we change the density of network or the range of communication such errors can be avoided.


THE IMPROVED ALGORITHM STEPS
The proposed algorithm contains 4 steps:
Step 1: In the initial step, the DVHOP algorithm is executed. Then every anchor computes the average distance per hop and sent to the whole network. Every mysterious node fixes its nearby anchor as a reference node.
Step 2: Each and every time, the mysterious node chooses any two anchors by random and is localized by trilateration, along with the reference anchor node and the results of all combinations are recorded. Suppose that we have 4 anchor nodes and the nearest anchor of node N1 is A1. Consequently, the different combinations for N1 are: (A1, A2, A3), (A1, A2, A4) and (A1, A3, A4) respectively giving three different positions: N11, N13.
Step 3: we can select the least error value based on the position error calculation of N1 by using the equation (1).
Step 4:Letsassume for an example that the combination giving the least error is (A1, A2, A4), then N1 will consider N12 as its estimate position

TENTATIVE RESULTS AND SIMULATION
The performance evolutions of the proposed algorithm, determines the localization results based on simulation. We use NS2 simulator to simulate the network state of affairs and find out the localization results.
The trial region is a square with the predetermined size of 50*50m2 and the broadcasting range of sensor nodes (R) is set to 20 meter.
Fig. 2 50 nodes randomly deployed, among them10 are anchor nodes

Familiarity 1
50 sensor nodes are distributed randomly in the simulation area. The anchor nodes ratio is of 10%, respectively,
20%…50%. The simulation results are existed in the following table:
TABLE4 Relationship Between the Minimal Error And The Nearest Anchor With Addition of Virtual Node N7.
Ratio Anchor
DVHop
Developed Algorithm
10%
56.98
32.37
20%
31.49
11.25
30%
28.28
07.20
40%
26.66
05.02
50%
26.06
04.15
The proposed enhanced DV Hop algorithm is based on the nearby anchor. The assessment from the localization crisis is the average localization error. From the experimental results showed in Fig. 4 specifies the average location error of anchor nodes.
Fig. 4 The average location error under different percentage of anchor nodes.
For example, in the anchor node ratio of 30%, improved DV hop algorithm is 07.20%; which is lower by 21.38% than the average error of the traditional algorithm. This shows the pre eminence of the improved algorithm compared with the original DVHop algorithm.

Familiarity 2
In this, we change the parameter of anchor amount is 20%, and the total number of nodes changes from 20 to 60.
TABLE5 Relationship Between the Minimal Error And The Nearest Anchor With Addition of Virtual Node N7.
Number of unknown nodes
DVHop Algorithm
Developed Algorithm
20
59.56
40.66
30
41.67
22.06
40
37.10
18.90
50
34.78
13.48
60
32.16
10.88
This figure shows the enlarge number of nodes, with the average location error of both the algorithms in a decreasing trend. The proposed algorithm results high positioning accuracy than the traditional DV hop algorithm.


CONCLUSION
In this paper we propose, an improved DVHop algorithm with a selection of three anchors based on the nearest one. For this improved method we get the simulation results without additional hardware and software requirements.
But the deficit of the algorithm is the rising cost calculation. The future objective is to suggest an algorithm with less with the improved node Precisions using flexible computing techniques.
REFERENCES

F. Ye, H. Lou, S. Lu, and L. Zhang, Statistical enroute filtering of injected false data in sensor networks, in IEEE INFOCOM, March 2004.

S. Zhu, S. Setia, S. Jajodia, and P. Ning, An interleaved hopbyhop authentication scheme for filtering false data in sensor networks, in IEEE Symposium on Security and Privacy, 2004.

C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro, and M. Yung, Perfectlysecure key distribution for dynamic conferences, in Advances in Cryptology – Crypto92, ser. Lecture Notes in Computer Science volume 740,1992, pp. 471486.

R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and publickey cryptosystems, Communications. of the Assoc. of Comp. Mach., vol. 21, no. 2, pp. 120126, 1978.

T. A. ElGamal, A publickey cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469472, 1985.

H. Wang, S. Sheng, C. Tan, and Q. Li, Comparing symmetrickey and publickey based security schemes in sensor networks: A case study of user access control, in IEEE ICDCS, Beijing, China, 2008, pp. 11 18.

D. Pointcheval and J. Stern, Security proofs for signature schemes, in Advances in Cryptology – EUROCRYPT, ser. Lecture Notes in Computer Science Volume 1070, 1996, pp. 387398.

D. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, vol. 24, no. 2, pp. 84 88, February 1981.

A. Pfitzmann and M. Hansen, Anonymity, unlinkability, unobservabil ity, pseudonymity, and identity management a proposal for terminol ogy,http://dud.inf.tudresden.de/literatur/Anon Terminology v0.31.pdf, Feb. 15 2008.

A. Pfitzmann and M. Waidner, Networks without user observability design options. in Advances in Cryptology – EUROCRYPT, ser. Lecture Notes in Computer Science Volume 219, 1985, pp. 245253.

M. Reiter and A. Rubin, Crowds: anonymity for web transaction, ACM Transactions on Information and System Security, vol. 1, no. 1, pp. 6692,1998. spite of active attacks, in Advances in Cryptology – EUROCRYPT, ser. Lecture Notes in Computer Science Volume 434, 1989, pp. 302319.

D. Pointcheval and J. Stern, Security arguments for digital signatures and blind signatures, Journal of Cryptology, vol. 13, no. 3, pp. 361396, 2000.

L. Harn and Y. Xu, Design of generalized ElGamal type digital signature schemes based on discret logarithm, Electronics Letters, vol. 30, no. 24, pp. 20252026, 1994.

K. Nyberg and R. A. Rueppel, Message recovery for signature schemes based on the discrete logarithm problem, in Advances in Cryptology EUROCRYPT, ser. Lecture Notes in Computer Science Volume 950,1995, pp. 182193.

R. Rivest, A. Shamir, and Y. Tauman, How to leak a secret, in Advances in CryptologyASIACRYPT, ser. Lecture Notes in Computer Science, vol 2248/2001. Springer Berlin / Heidelberg, 2001.

M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in CCS93, 1993, pp. 62 73.

BlueKrypt,Cryptographic key length recommendation,http://www. keylength.com/en/3/.

W. Zhang, N. Subramanian, and G. Wang, Lightweight and compromise resilient message authentication in sensor networks, in IEEE INFOCOM, Phoenix, AZ., April 1517 2008.

A. Perrig, R. Canetti, J. Tygar, and D. Song, Efficient authentication and signing of multicast streams over lossy channels, in IEEE Symposium on Security and Privacy, May 2000.