Pro-MAP: A new Localization Algorithm for Wireless

Sensor Networks







Manel Khelifi 1, Samira Moussaoui 2, Ilham Benyahia 3 and Farid Naït-Abdessalem 4



1  ReSyD, Doctoral School in Computer Science, UAMB University, Bejaia, Algeria maneCette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser., Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

2  Department of Computer Science, USTHB University, Algiers, Algeria

Moussaoui- samCette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser., Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

3  Department of Computer Science, UQO, Outtaouis, CanadaCette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.';document.getElementById('cloak39334bbc111773ec81b34b13b4b4f2cf').innerHTML += ''+addy_text39334bbc111773ec81b34b13b4b4f2cf+'<\/a>';

4  LIPADE, Paris Descartes University, Paris, FranceCette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.';document.getElementById('cloak4c9d67c38ce542178d1b7205252d2688').innerHTML += ''+addy_text4c9d67c38ce542178d1b7205252d2688+'<\/a>';







AbstractKnowing the location of sensor nodes is crucial in wireless network applications including environment monitoring, geographic routing, and topology control. When the  positions  of  the  sensors  are  unknown  and  only  local distance information is given, we need to infer the positions from these local distance measurements. In this paper, we consider the problem of sensor network localization using only the connectivity information. We propose an improved algorithm of MDS-MAP that relies upon distance information to localize nodes. It primarily applies the multidimensional scaling MDS algorithm to construct a relative map and approximate position of each node. Our algorithm uses a new technique to refine the process of conversion from relative coordinates computed by MDS to absolute coordinates.

The performance of our algorithm is demonstrated using a computer simulation technique. The simulation studies are conducted under regular square topology. The initial results show that Pro-MAP significantly outperforms the classical multidimensional scaling MDS and provides lower position estimation error.



Keywords- Sensor Networks, multidimensional scaling, node localization.



  Due to recent advancements in micro-electromechanical systems, sensors are becoming tinier and cheaper and are used in everyday life. More importantly, these sensors have the capability to communicate through wireless networks to

monitor an area of interest and provide information about this area. The knowledge of nodes location is of great importance and actually it is required for many networks applications that rely on the information's location, such as industrial automation, defense applications, and smart environments, just to name a few [1]. For example, some defense applications are monitoring friendly forces, battlefield surveillance, battle damage assessment and nuclear, biological and chemical attack detection. If the sensor network is used for monitoring an area, nodes may be deployed from an airplane and the precise location of most sensors may be unknown. Finding the exact physical locations is a crucial issue for continual network operation and its management. Thus, the information gathered from the network can often be useless if not matched with the location where it is sensed. Hence, the node's geographical information not only serves to identify the source of the collected data in the network, but also for the development of routing protocols and middleware services such as geographic routing protocols, location-aware services and enhanced the coverage of area of interest.

Therefore, a lot of work have been conducted to provide the sensors positions. Most important solutions and schemes designed for localization sensor nodes in WSNs can be categorized into range-based and range-free [2][3].

The range-based algorithms use one of the localization technologies, such as RSS [4], ToA [5], TDoA [6] or AoA [7] to estimate distance or angle between nodes in order to calculate their positions. Range-free approaches, nevertheless, do  not  need  the  distance  or  angle  sensors' information neither require extra hardware to obtain these


information. They exploit the connectivity information between nodes to obtain their estimated locations. Range free  algorithms are  more  attractive than  the  range-based schemes because the estimated location is achieved with low cost and consumes less energy. In contrast, the range- based  schemes  have  highly  accurate  positioning as  they require complex hardware to obtain angle and/or distance measurements.

One of the leading range-free algorithms for WSNs is the MDS-MAP algorithm [8].  This algorithm relies on the Multidimensional Scaling (MDS) technique to determinate the relative nodes positions. MDS is a s-et of analytical techniques that has been used for many years in disciplines such as mathematical psychology, economics and marketing research. This technique can also be used in WSN where only distances between nodes are known. Hence, the MDS- MAP algorithm uses only the connectivity information between nodes to construct a relative map and thus, approximate position of each node.

Of course there is  the  possibility of  map  rotation or incorrect scaling, for  this  reason by  using  at  least  three anchors as sensors that are aware of their positions, a cost function is created and to be refined using a least-squares minimization.

Although this step allows converting the relative map to an absolute one, the anchors involved in the transformation process are selected arbitrarily, thus, the rotation and the translation are also made randomly.

In this paper, we investigate classical multidimensional scaling (MDS) technique for nodes localization in two dimensional  WSN.  We  apply  a  new  technique  on  the relative maps computed by MDS to refine the conversion process. This technique is the Procrustes Analysis [9]. It is applied on the anchors to find the scaling factors, orthogonal rotation, and the translation vector that will be used to the relative coordinates nodes to obtain the estimated ones.


The rest of this paper is organized as follows. In the second section, a collection of relevant localization algorithms related to MDS-MAP are briefly summarized. The  third  section  provides  a  detailed  description  of  the MDS-MAP algorithm and the Procrustes Analysis. Our proposed localization algorithm Pro-MAP is presented in section five. Section six gives an analysis and a complete comparison between our protocol and the original MDS- MAP. Finally, we conclude the paper in section seven



télécharger l'article