Localization Using Classical MDS & NN Implementation

Localization Using Classical MDS & NN Implementation

Urvashi Singh, Manish kumar Jha

Department of ECE

Mody Institute of Technology & Science Lakshmangarh (332311), Rajasthan, India

Abstract

The process of accurate position estimation of sensor nodes, called Localization is vital for many position-dependent applications in wireless sensor networks. Distance estimation between sensor nodes is the fundamental step before any algorithm is applied to obtain accurate estimate of nodes. Most ranging methods give noisy estimate of distance vector between nodes. This work attempts to reduce the effect of noisy estimated range by utilizing neural network. The results suggest that neural networks could be promising domain to achieve higher localization accuracy.

1. Introduction

   In recent years, benefiting from advances in wireless communication and Micro electro mechanical systems technology (MEMS), it became naturalistic for producing a flyspeck sensor node which integrate small size of sensor, processor, memory, power supply in it [1]. Wireless Sensor networks (WSNs) uncover great potential to give economical as well as practical solution to myriad military and civilian applications [2, 3] including environmental monitoring, habitat monitoring, precision agriculture, animal tracking, disaster rescue, etc. In almost all of these applications sensor nodes must collect its data with location of event. Collected data with location helps scientists to perform analysis on incoming information from corresponding sensors [4, 5]. The process of knowing the location of event occurrence called "Localization" [6], is a crucial issue in WSNs.

   This paper focuses on localization techniques of sensors in a network. A very prominent localization algorithm called MDS is implemented and the results are evaluated to obtain the degree of inaccuracy – called stress. Further work is carried out to reduce the stress by implementing neural network (NN) approach. The results obtained after (NN) implementation is encouraging, however the feasibility of such implementations have to be analyzed.

   This paper is organized as follows. Section 2 presents the background of wireless sensor network and sensor node localization. Related work is discussed in Section 3. Section 4 presents MDS algorithm and analysis of this particular algorithm followed by description of neural network and localization then it contains the simulation and evaluation results. Section 5 contains conclusion and future direction.

2. Localization in Wireless Sensor Networks.

   A WSN comprises of few to thousands of nodes that are spatially distributed and connected wirelessly that are used to monitor physical or environmental condition such as temperature, sound, pressure etc. and to cooperatively pass their data through the network to a main location. A sensor node [7] might vary in size, the cost of sensor nodes is similarly

   variable depending on the complexity and function of individual sensor nodes. Unlike current information service such as those on the internet where information can easily get stale or useless because it is too generic, sensor network promises to couple end users directly to sensor measurements and provide information i.e. precisely localized in time and or space, according to user's demand [8].

   Localization, i.e., location estimation of source of occurrence of events is essential in most wireless sensor network applications. For estimating the location, human configuration is a simple way but impossible for large networks and some human restricted area like in jungles, volcanoes [9] and also where sensors are mobile. Another way is to directly add GPS on the sensors but use of GPS is not feasible as (i) it is not suitable for indoors and underwater sensor network, (ii) it require LOS condition, (iii) size of sensors shall increase on adding GPS to it and finally (iv) power consumption of GPS is more which becomes a deterrent to its use in WSN [10 11].

   Basically localization technique are classified into two groups – range based and range free techniques. The taxonomy of such techniques is given in figure 1 [11-20].

   Figure 1. Classification of localization techniques

   *APIT- Approximation Point In Triangle

   • CPE – Convex Position Estimation

   • MDS – Multidimensional Scaling

   • ToA- Time of Arrival

   • TDoA- Time Difference of Arrival

   • AoA- Angle of Arrival

   *RSSI- Received Signal Strength Indicator.

3. Related Work

   Yi Shang et al. in [21] proposed MDS-MAP algorithm that uses connectivity information – who is within communication range of whom – to derive location of nodes in a network. Result demonstrate that given algorithm is more robust to measurement error than previous algorithm. Yi Shang et al. in [22] showed a new variant method MDS-MAP(P) standing for MDS-MAP using patches of relative maps, execute in distributed fashion. Result yielded not only preserve the good performance of original MDS on relatively uniform layout but also perform much better than the original on a irregularly-shaped network. Georgious Latsoudas et al. in [19] propose a two-stage MDS algorithm that employs an algebraic initialization procedure followed by gradient descent. The algebraic initialization step is based on the Fastmap algorithm [23], borrowed from the database literature. Fastmap is a linear- complexity mapping tool, which is, however, sensitive to measurement errors. Parham H. Namin et al. in [24] has shown that most of the localization algorithms have poor performance in irregularly shaped networks. They have applied MDS-MAP on irregular wireless sensor network based on Multidimensional Scaling. The result shows enhanced localization precision. Minhan Shon et al. [11] has shown that some method provide location information by node connectivity

   one of them is MDS-MAP, gives an accurate positioning but has computation of O (n3 ) in a

   network with n nodes resulting significant localization accuracy error in environments with holes. They have applied cluster-based MDS for range-free localization. Result shows the overcoming of shortcoming of MDS and give 23% improvement in localization accuracy.

4. Wireless sensors localization using Multidimensional Scaling(MDS):

   Few algorithm whether range based or range free are based on MDS. In this technique proximities between any kind of objects(sensor nodes) are used as an input and the chief output is a spatial representation, consisting of geometric configuration of points [25]. This technique gives a good estimate of node position, but its computational cost is high O (n3), where n is number of sensor node. Here we focus on classical multidimensional scaling(CMDS). It is the simplest case of MDS.

   Let

   d rs

   be the dissimilarity measure between two objects r and s, and D be the distance

   matrix. euclidean distance between two pints

   2

   X s (xs1 , xs2 ,…..xsm ) is to be calculated as

   X r (xr1 , xr 2 ,….., xrm ) and

   ^

   drs

   m

   (xrk k 1

   • xsk )

     where k is the value of dimension and m is number of dimension.

     • Compute the square of distance matrix D as

       D 2 where D is an

       N N

       matrix

       and N represents number of sensors or object.

     • Apply double centering version to D 2 , denoted by B as

       B 1 JPJ

       2

     • J is a centering operator and compute J I eeT / N and e is vector of all

       ones.

     Compute Eigen decomposition of B as B UVU T where U is an eigen

     vector and V is an diagonal containing eigen value.

     1

     • The classical coordinate matrix is X UV 2 .

       The result of CMDS implementation in MATLAB for 50 nodes is shown in figure 2.

       Localization for 50 Nodes

       1

       Real location

       Mapping after classical MDS

       Y Co-ordinate

       0.5

       0

       -0.5

       -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

       X Co-ordinate

       Figure 2.Localization of nodes after applying Classical MDS

       The above graph shows that the CMDS technique gives an estimate of the position of the nodes. The degree of inaccuracy called stress is defined as

       dij = distance between variables i and j in the configuration.

       rawstress (dij

       ij

       i, j

   • d o )2

   Normalization Factor (sum of squared deviation from mean)

   NF1 (dij

   i, j

   d )2

   Stress

   rawstress NF1

   The stress obtained after implementation of MDS technique is 0.3357. Although this value is less than 1, but it needs to be reduced to obtain better positioning of nodes.

   Neural Network Implementation

   NN is employed to effectively further reduce the stress in the location estimation problem. It provides better location estimation results than other approaches. Traditionally, the term neural network has been used to refer to a network of biological neurons. The modern definition of this term is an artificial construct whose behaviour is based on that of a network of artificial neurons. These neurons are connected together with weighted connections following a certain structure. Each neuron has an activation function that describes the relationship between the input and output of the neuron. Learning is viewed as the establishment of new connections between neurons or the modification of existing connections. Artificial Neural networks imitate functioning of the brain. They use non-algorithmic methods, which use parallel computing technique. Even though inter-neuron communication speed is quite slow for the brain, parallel processing allows it to analyze very complicated data in a short period of time. Neural networks learn directly from current examples.

   The noisy position of nodes obtained after CMDS implementation is applied as input to Neural Network (NN) as shown in figure. 3 trained to give localization results. The NN selected is "newcf" shown in figure 4 and the results of CMDS for 50 nodes is applied to it that yields position of nodes. The implementation is done in MATLAB. Newcf network is a Cascaded- forward network consisting of N1 layers using DOTPROD weight function, NETSUM net input function, and the specified transfer function. The first layer has weight coming from the input. Each subsequent layer has weight coming from the input and all previous layers. All layers have biases.

   Figure 3

   Figure 4

   The localization obtained after NN implementation is shown in figure 5. This figure shows the position of original nodes, position after CMDS and position obtained after NN implementation.

   1

   0.8

   0.6

   Localization for 50 Nodes

   Real location

   Mapping after classical MDS Mapping after neural network

   Y Co-ordinate

   0.4

   0.2

   0

   -0.2

   -0.4

   -0.6

   -0.5 0 0.5 1

   X Co-ordinate

   Figure 5 Localization after Neural Network

   The stress value obtained after neural network implementation is 1.582339949091449e-015 which shows, the stress obtained has reduced drastically after NN implementation compared to Classical MDS technique.

5. Conclusion and future work

In emerging sensor network applications, localization in wireless sensor network is a recent area of research. Accurate localization or tracking of wireless device is a crucial requirement for many emerging location aware systems. Fields of application include search & research, medical care, intelligent transportation, location based billing, security, home automation, industrial monitoring and control, location -assisted gaming, and social networking. Requirement of its applications and availability of resources in WSNs need feasible localization algorithm with lower cost and higher accuracy. The result of NN localization implementation shows higher accuracy in node positioning. However require additional hardware, computational facility and memory that may be a deterrent where small size of sensor nodes is of prime importance. Some of the open problems in the area of localization are as follows [26]: Robust algorithm for mobile sensor networks, Attack the challenges of Information Asymmetry, Finding localization algorithm in three dimensional space.

References

[1]. Mehak Khurana, Ashish Payal, "An Improvement of Centroid Algorithm Based on Distance in Wireless Sensor Network", International Journal of Smart Sensors and Ad Hoc Networks (IJSSAN) Volume-1, Issue-1, 2011, pp.28-32.

[2]. Qingjun Xiao, Bin Xiao, Jiannong Cao and Jianping Wang, "Multihop Range-Free Localization in Anisotropic Wireless Sensor Networks: A Pattern-Driven Scheme", IEEE transactions on mobile computing, Volume. 9, no. 11, November 2010, pp.1592-1607.

[3]. Avinash Kaur, Sonu Agrawal, "Location Detection in Wireless Sensor Network using Classical Optimization Methodology", International Journal of Computer Science And Technology, Volume. 3, Issue 1, Jan. – March 2012, pp. 685-688.

[4]. Shigeng Zhang, Jiannong Cao, Lijun Chen, and Daoxu Chen,"Accurate and Energy-Efficient Range-Free Localization for Mobile Sensor Networks", IEEE transactions on mobile computing, Volume. 9, No. 6, June 2010, pp. 897-910.

[5]. P.Shunmuga Perumal, V.Rhymend Uthariaraj, a, "Novel Localization of Sensor Nodes in Wireless Sensor Networks using Co-Ordinate Signal Strength Database", International Conference on Communication Technology and System Design, Procedia Engineering 30 (2012), pp.662668 (Available online at www.sciencedirect.com).

[6]. Sangin Han. Sungjin Lee. Sanghoon Lee. Jongjun Park, "Node distribution base Localization for large scale wireless sensor networks", Wireless Netw(2010) 16:1389-1406 DOI 10.1007/S11276-009-0210-1, published online: 29 September, © Springer Science+ Business Media LCC. 2009, pp.1389-1406.

[7]. Feng Zaho. Leonidas Guibas," Wireless Sensor Networks, An information processing approach". Elsevier publication.

[8]. Guoqiang Mao & Baris Fidan, "Localization Algorithms and strategies for wireless sensor networks". May 2009, pp.510.

[9]. Samira Afzal," A Review of Localization Techniques for Wireless Sensor Networks", Journal of Basic and Applied Scientific Research, 2(8)7795-7801, 2012, pp.7795-7796.

[10]. Andreas Savvides, ChihChieh Han and Mani B. Srivastava , "Dynamic Fine Grained Localization in AdHoc Networks of Sensors", Proceeding MobiCom 01, Proceedings of the 7th annual international conference on Mobile computing and networking, pp. 166-179, ACM New York, NY, USA, ISBN: 1- 58113-422-3.

[11]. Minhan Shon, Minho Jo, Hyunseung Choo," An interactive cluster based MDS localization scheme for multimedia information in wireless sensor network", Computer communications, volume. 35, Issue 15, 1september 2012, pp.1921-1929, Elsevier publication.

[12]. Guerrero E, Wang Hao, Alvarez J, Rivero L," A three-dimensional range-free Localization algorithm based on mobile beacons for Wireless Sensor Networks", CADDM , volume. 20, No.1, June 2010, pp. 84- 92publication.

[13]. Jungang Zheng, Chengdong Wu, Hao Chu ,Yang Xu," An Improved RSSI Measurement In Wireless Sensor," Advanced in Control Engineering and Information Science, Procedia Engineering, issue 15 , 2011, pp. 876 880, Elsevier publication.

[14]. Attoungble Kouakou Jean Marc, Okada Kazunori," LRD : A Dstributed and Accurate Localization Technique for Wireless Sensors Networks", TENCON 2010- 2010 IEEE Region 10 Conference. pp. 234- 239.

[15]. Huei-Wen Ferng. Issa Arwani," Concentric distributed Localization based on the Tripodal anchor structure and Grid scan for Wireless Sensor Network", wireless press communication DOI.10.1007/S11 271-012- 0546-1, © Springer Science+ Business Media, LLC. 2012, pp. 1-23.

[16]. Azat Rozyyev, Halabi Hasbullah, Fazli Subhan, Muhammad Shafiq," An Overview of Indoor Localization Techniques for Child Tracking in Wireless Sensor Networ",2010 International Conference on Intelligence and Information Technology (ICIIT 2010), pp. v2.535-v2.538.

[17]. A. R. Kulaib , R. M. Shubair , M. A. Al-Qutayri , and Jason W. P. Ng," An Accurate Localization Technique for Wireless Sensor Networks Using MUSIC Algorithm", Journal of Communications, Volume. 7, No. 4, APRIL 2012, pp-281-289.

[18]. Bin Yang · Jinwu Xu · Jianhong Yang · Min Li," Localization algorithm in wireless sensor networks based on semi-supervised manifold learning and its application", Cluster Comput issue 13, DOI 10.1007/s10586- 009-0118-7, © Springer Science+ Business Media, LLC 2010, pp. 435446.

[19]. Georgios Latsoudas, Nicholas D.Sidiropoulos, "A Fast and Effective Multidimensional Scaling Approach for Node Localization in Wireless Sensor Networks, IEEE transaction on Signal Processing, Volume.55,No.10, October 2007, pp.5121-5127.

[20]. L. Doherty, K.S.J. Pister, L.E. Ghaoui, Convex position estimation in wireless sensor networks in: IEEE INFOCOM, Volume.3, 2001,pp. 1655-1663.

[21]. Yi Shang, Wheeler Ruml, Ying Zhang, Markus P. J. Fromherz," Localization from Mere Connectivity", Proceeding MobilHoc '03 Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pp.201-212, ACM New York, NY, USA© 2003.

[22]. Yi Shang, Wheeler Ruml, "Improved MDS-Based Localization", INFOCOM 2004. Twenty-third Annualjoint Conference of the IEEE Computer and Coounications, Date of conference 7-11 march 2004, Deptt. of Comput. Sci., Missouri- Columbia Univ., Columbia, MO, USA Volume 4, pp. 2640-2651.C. Faloutsos and K.-I. Lin, FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, in Proceeding. ACM SIGMOD, 1995, vol. 24, no. 2, pp. 163174.

[23]. Parham H. Namin, Mohammad A. Tinati, "Localization of Irregular Wireless Sensor Networks Based on Multidimensional Scaling", Advanced Technologies for Communications, 2009.ATC '09. International Conference 12-14 October 2009, Fac. of Electr.& Comput. Eng., Univ. of Tabriz, Tabriz Iran Tinat, M.A., pp.79-83.

[24]. Rashmi Agrawal, Brajesh Patel, "Localization in wireless sensor network using MDS", International Journal of Smart Sensors and Ad Hoc Networks (IJSSAN) ISSN No. 2248-9738 Volume.1, Issue-3, 2012, pp. 26-31.

[25]. Ali Shareef, Yifeng Zhu and Mohamad Musavi, "Localization using Neural Networks in Wireless Sensor Networks", Proceeding MOBILWARE '08 Proceedings of the 1st international conference on MOBILE WIRELESS MiddleWARE, Operating Systems, and Applications Article No.4 ICST (Institute for Computer Science, Social-Informatics and Telecommunications Engineering) ICST, Brussels, Belgium,

Belgium ©2007, ISBN: 978-1-59593-984-5

[26]. Amitangshu Pal. "Localization algorithm in WSN: current Approaches and future challenges". Network Protocols and Algorithm ISSN 1943-3581 volume.2, No.1, pp.47-73, 2010.