An Improved Localization Method of Wireless Sensor Networks with a Three Anchor DV-Hop Algorithm

An Improved Localization Method of Wireless Sensor Networks with a Three Anchor DV-Hop 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 hop-based 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).

1. 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. Range-based 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 DV-Hop based on the estimated hop distance. In a network for the DV-hop 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 DV-Hop, based on the estimated distance to the nearest anchor. An [14], improved DV-Hop algorithm consists of selective Three-anchor DV-hop 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: DV-Hop 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.

2. DV-HOP ALGORITHM

   Dargos Niculesu and Badri Nath proposed a algoritm called DV-HOP 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 one-hop 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 Range-free

     j i ij

     (1)

     techniques are centroid algorithm, DV-Hop algorithm, APIT algorithm [11], and Sequence-Based algorithm [12].The localization results offered by range-based approaches are more accurate than the range-free 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 hop-size 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)

3. LOCALIZATION CRISIS

   Due to the difference between the estimated co-ordinate and the actual co-ordinate 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 co-ordinates of node N are

     (x' , y' ) respectively and the actual co-ordinates 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.

4. 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 2

   x 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 DV-hop 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 3-anchor 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.

   1. Familiarity:

      The results of simulations corresponding to location errors for different combinations are tabulated as follows:

      TABLE-1 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 DV-Hop is also present in this table.

      TABLE-2 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 DV-Hop 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.

   2. 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.

     TABLE-3 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.

5. THE IMPROVED ALGORITHM STEPS

   The proposed algorithm contains 4 steps:

   Step 1: In the initial step, the DV-HOP 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

6. 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

   1. 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:

      TABLE-4 Relationship Between the Minimal Error And The Nearest Anchor With Addition of Virtual Node N7.

      Ratio Anchor	DV-Hop	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 DV-Hop algorithm.

   2. Familiarity 2

   In this, we change the parameter of anchor amount is 20%, and the total number of nodes changes from 20 to 60.

   TABLE-5 Relationship Between the Minimal Error And The Nearest Anchor With Addition of Virtual Node N7.

   Number of unknown nodes	DV-Hop 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.

7. CONCLUSION

In this paper we propose, an improved DV-Hop 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

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

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

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

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

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

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

7. 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.

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

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

2. 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.

3. 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.

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

5. 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.

6. 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.

7. 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.

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

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

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

11. 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.