ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

The Implementation of Light Weight Localization Algorithms in Wireless Sensor Network Applications

Rekha.K.S1, Aparna.S2, Archana.T.C3, Dr.T.H.Sreenivas4
  1. Assistant Professor, Department of C.S., The National Institute of Engineering, Mysore, India
  2. Student, Department of C.S., The National Institute of Engineering, Mysore, India
  3. Student, Department of C.S., The National Institute of Engineering, Mysore, India
  4. Professor, Department of I.S., The National Institute of Engineering, Mysore, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

A wireless sensor network (WSN) is a major field of interest and number of sensors are placed in region where data has to be sensed. The sensors are usedto monitor physical or environmental conditions, such astemperature,pressure,in military application, emergency and rescue operation etc. and to cooperatively pass their data through the network to a main verification centre. In this cases the location of a sensor places an important role and this location has to be verified. In order to do the verification we are using two verification method i.e.,on-spot and inregion verification method, which are based on GFT and GFM algorithms. Once the location has verified as trustable, then the sensor and the data it is sensing can be trusted and can be further processed as required by the application.

Keywords

Localization, Wireless Sensor Network(WSN), On-spot, In-region, GFM,GFT, Verification Center(VC), Tracker mapping tool.

I. INTRODUCTION

LOCALIZATION in wireless sensor networks, i.e., knowing the location of sensor nodes, is very important for many applications such as environment monitoring, target tracking, 5and geographical routing. Since wireless sensor networks may be deployed in hostile environment, sensors’ localization is subjected to many malicious attacks. For example, attackers can compromise sensors and inject false location information; they can also interrupt signaltransmission between sensors and contaminate distance measurements. Hence, the locations estimated in the localization process are not always correct[1]. The author define the problem of localization as estimating the position or spatial coordinates of wireless sensor nodes. Localization is an inevitable challenge when dealing with wireless sensor nodes, and a problem which has been studied for many years[3].
The core function of a WSN is to detect and report events which can be meaningfully assimilated and responded to only if the accurate location of the event is known. Also, in any WSN, the location information of nodes plays a vital role in understanding the application context[2]. Sensor network localization algorithms estimate the locations of sensors with initially unknown location information by using knowledge of the absolute positions of a few sensors and inter sensor measurements such as distance and bearing measurements. Sensors with known location information are called anchors and their locations can be obtained by using a global positioning system (GPS), or by installing anchors at points with known coordinates. In applications requiring a global coordinate system, these anchors will determine the location of the sensor network in the global coordinate system. In applications where a local coordinate system suffices (e.g., smart homes), these anchors define the local coordinate system to which all other sensors are referred. Because of constraints on the cost and size of sensors, energy consumption, implementation environment (e.g., GPS is not accessible in some environments) and the deployment of sensors (e.g., sensor nodes may be randomly scattered in the region), most sensors do not know their locations. These sensors with unknown location information are called non-anchor nodes and their coordinates will be estimated by the sensor network localization algorithm[4].
image
Fig 1.1: Overview of Light weight location verification for WSN

II. RELATED WORK

Many different methods and algorithms are used to estimate the trustable location of the sensors and their neighbours. Along with the trustable location they are trying to reduce the cost of implementation by using different technologies. Mobile Wireless Sensor Networks(MWSN’s), here the sensor nodes are mobile phones, MWSN can be classified as three different layers.
 One Layer: Flat or planar,network architecture comprises a set of heterogeneous devicesthat communicate in an ad hoc manner. The devices can be mobile or stationary, but all communicate over the same network
 Two Layer:This architecture consists of a set of stationary nodes, and a set of mobile nodes.The mobile nodes form an overlay network or act as data mules to help move data through the network.The overlay network can include mobile devices that have greater processing capability,longer communication range, and higher bandwidth.
 Three Layer:This architecture, a set of stationary sensor nodes pass data to a set of mobile devices, which then forward that data to a set of access points. This heterogeneousnetwork is designed to cover wide areas and be compatible with several applicationssimultaneously[5].
In sequence based localization, the 2D localization space is divided into distinct regions by theperpendicular bisectors of lines joining pairs of reference nodes (nodes with known locations). Each distinct region formed in this manner can be uniquely identified by a location sequence that represents the distance ranks of reference nodes to that region. There is an algorithm to construct the location sequence table that maps all these feasible location sequences to the corresponding regions by using the locations of the reference nodes. This table is used to localize an unknown node (that is, the node whose location has to be determined). The unknown node first determines its own location sequence based on the measured strength of signals between itself and the reference nodes. It then searches through the location sequence table to determine the “nearest” feasible sequence to its own measured sequence. The centroid of the corresponding region is taken to be its location[11].
Localization algorithms are classified into two categories:Range-based algorithms and range-free algorithms.Range-based algorithmsestimate the coordinates of nodes from pairwise distances using special hardware. This hardware is used to measure angle of arrival (AOA), time of arrival (TOA),time of difference arrival (TDOA), received signal strength indicator (RSSI)[8], and so forth. In Range-free algorithms, the localization between normal nodes is obtained through connectivity with the neighboring sensors which do not require any additional hardware. Thissignificantly reduces the overall cost and energy consumption. Some of these algorithms are the area based approach (centroid DV based positioning (DV hop), the convex position estimation (CPE), and Monte Carlo localization (MCL)[9].
As visualization technologies for wireless sensor networks using Augmented Reality (AR) technology, Embodied Visualization with AR for Network Systems (EVANS) and uMegane have been proposed. In these systems, sensor device information is visualized, by recognizing AR markers attached to the sensor device through image processing, and by displaying the virtual object super imposedly by way of calculating the location of the sensor device[7].
The Probabilistic approaches are ideal for handling noisy measurements in indoor localization scenarios where RSSI measurements suffer from severe multipath effects. Two distinct tracks are pursued in probabilistic approaches. One relies on mappings between the RSSI measurements and the locations, while the other manages to capture the statistical relationship between the RSSI measurements and the distances. Both can work with off-line recording and on-line measurements in localizing the nodes with RSSI capability[10].

III. PROBLEM STATEMENT

In the existing system, sensors locations plays an important role in Wireless Sensor Networks (WSNs). When sensor nodes are deployed in places where manual interaction cannot be done easily or frequently, then there are chances of vulnerable attack on these sensor nodes such as range reduction or enlargement attack, misplacement of the sensors, addition of unauthorized sensors, etc.Therefore, sensors locations are not trustworthy. Eventhough we have different methods for overcoming the above issues and make the sensor trustworthy they are of high cost and difficult to implement. Thus, this paper concentrates to overcome from the above disadvantages using a simply implementable and low cost system.
Two location verification approaches used they are on-spot and in-region. In On-spot Verification the verification method is carried out by comparing the sensors current location with its registered location. In In-region verification method the location of the sensor is calculated with respect to its neighbouring sensor nodes.The location centre records the location of the sensors from which data is received, along with the location of its neighbours.The distance between the sensor node and the neighbouring sensor nodes are also recorded. They are compared with the stored values. The location of the sensors are found using GPS(global positioning system) by calculating its latitude and longitude. Two algorithms are used for demonstrating the on-spot verification methods namelyGreedy Filtering using Matrix(GFM) andGreedy Filtering using Trustability-indicator(GFT).

IV. ALGORITHMS USED

First, to provide on-spot verification service, two algorithms can be used by our system, namely, the Greedy Filtering by Matrix (GFM) algorithm and the Greedy Filtering by Trustability-indicator (GFT) algorithm. Both algorithms exploit the inconsistency between sensors’ estimated locations and their neighborhood observations. Second, to perform in-region verification, a verification region is first calculated according to the applications functions, then a probabilistic algorithm is used to compute the confidence that a sensor is inside the verification region[12].

4.1: GFM

Suppose there are totally n sensor nodes in the field denoted by S1,S2,….Sn. For convenience, we assume sensor Si’s ID is integer i where i =0,1,2,3,……. In GFM algorithm, five n* n square matrixes are calculated based on the reported information from sensors[13].

4.2: GFT

Here, VC computes a trustabilityindicator(TI) for each sensor and updates the indicator’s value in multiple rounds[13].

Algorithm of GFT

In Each round, if TI > threshold Sensor is accepted as the correctly localized sensor
iteration stops when all sensor’s indicators become stable.
Finally, the sensors that have TI< threshold are detected and revoked[13].

V. EXISTING METHODOLOGIES

5.1: The Ellipse Centroid Localization Algorithm

The ellipse centroid localization algorithm is the combination of ellipse localization and weighted centroid localization. In the ellipse centroid localization algorithm, several unknown nodes are located by ellipse localization algorithm and then the located nodes are extended as the anchors that increase the anchor density in wireless sensor networks. Finally, other unknown nodes are located by weighted centroid localization algorithm[14].

5.2: MDS-MAP

The advantage of this scheme is that it does not need anchor or beacon nodes to start with. It builds a relative map of the nodes even without anchor nodes and next with three or more anchor nodes; the relative map is transformed into absolute coordinates. This method works well in situations with low ratios of anchor nodes. A drawback of MDSMAP [15] is that it requires global information of the network and centralized computation

5.3: Distributed Localization

In Distributed localizations all the relevant computations are done on the sensor nodes themselves and the nodes communicate with each other to get their positions in a network. Distributed localizations can be categorized into three classes[16].
1.Beacon-based distributed algorithms: Beacon-based distributed algorithms start with some group of beacons and nodes in the network to obtain a distance measurement to a few beacons, and then use these measurements to determine their own location.
Beacon-based distributed algorithms Categorized into three parts:
Diffusion: In diffusion the most likely position of the node is at the centroid of its neighbouring known nodes. APIT requires a high ratio of beacons to nodes and longer range beacons to get a good position estimate. For low beacon density this scheme will not give accurate results.
Bounding box: Bounding box forms a bounding region for each node and then tries to refine their positions. The collaborative multi lateration enables sensor nodes to accurately estimate their locations by using known beacon locations that are several hops away and distance measurements to neighbouring nodes. At the same time it increases the computational cost also.
Gradient: Error in hop count distance matrices in the presence of an obstacle.
a).Relaxation-based distributed algorithms:In relaxation-based distributed algorithms use a coarse algorithm to roughly localize nodes in the network. This coarse algorithm is followed by a refinement step, which typically involves each node adjusting its position to approximate the optimal solution..
b).Coordinate system stitching based distributed algorithms: In Coordinate system stitching the network is divided into small overlapping subregions, each of which creates an optimal local map. Next the scheme merges the local maps into a single global map
c).Hybrid localization algorithms: Hybrid localization schemes use two different localization techniques such as : multidimensional scaling (MDS) and proximity based map (PDM) or MDS and Ad-hoc Positioning System (APS) to reduce communication and computation cost.
d).Interferometric ranging based localization: Radio interferometric positioning exploits interfering radio waves emitted from two locations at slightly different frequencies to obtain the necessary ranging information for localization.
e).Error propagation aware localization: When sensors communicate with each other, error propagation can be caused due to the undesirable wireless environment, such as channel fading and noise corruption. To suppress error propagation [17] has proposed a scheme called error propagation aware (EWA) algorithm[16].

5.4: Hop-Counting Techniques

To provide localization innetworks where seed density is low, hop-counting techniques propagate location announcements throughout the network. DV-HOP uses a technique based on distance vector routing. Each node maintains a counter denoting the minimum number of hops to each seed, and updates that counter based on messages received. Seed location announcements propagate through the network. When a node receives a new seed announcement, if its hop count is lower than the stored hop count for that seed, the recipient updates it hop count to the new value and retransmits the announcement with an incremented hop count value[18].

5.5: Anchor free Approaches

It tries to compute nodes’ positions without the use of anchor nodes (i.e. anchor-free). In this case, instead of computing absolute node positions, the algorithm estimates nodes’ positions relative to a coordinate system established by a reference group of nodes. Relative positioning can be sufficient for many applications to work efficiently, for example, location-aided routing . Moreover, a relative coordinate system can still be transformed to absolute coordinate system by using only three anchor nodes in case of 2-D (or four anchors in case of 3-D)[19].

5.6: Anchor-based algorithms

Algorithms that rely on anchornodes assume that a certain minimum number or fraction of the nodes know their position, e.g., by manual configuration or using some other location mechanism. The final coordinate assignment of individual nodes will therefore be valid with respect to another possibly global coordinate system. Any positioning scheme built around such algorithms has the limitation that it needs another positioning scheme to bootstrap the anchor node positions, and cannot be easily applied to any context in which another location system is unavailable (e.g., strictly interior to a building). It turns out that in practice a large number of anchor nodes are needed for the resulting position errors to be acceptable[20].

VI. PROPOSED WORK

Many existing sensor localization scheme are not good for indoor applications because when sensors are deployed very close to each other within a small range the latitude and longitudinal values of these sensors does not vary much as a result the location of the sensor cannot be trusted .
This paper helps in overcoming the above issue.
 This can be implemented using low cost.
 This demonstrates two verification methods i.e., on-spot and in-region.
 Easy to implement as we are not using complicated hardware and software.

6.1: MODULES

6.1.1: Android app( Sensor nodes )

Since we are implementing the system in a low-cost way we use android phones as sensors. The android phones contain two components namely accelerometer and gyrometer which are used to sense the vibrations . In order to do this we develop an android application using java and install it in the phones and run the application. The sensors(android phones) are differentiated using the IMEI number
The International Mobile Equipment Identity(IMEI) is a unique number used by a mobile networks to identify valid devices and stop other devices from accessing that network

6.1.2: Verification Centre(VC)

The laptop or the desktop systems can be used as verification center. Here all the information such as IMEI number of the android phone, latitude, longitude, radius range, tolerance etc. of the sensor nodes deployed for the particular application are stored. This initiates the functionalities such as register, find, delete, update and also the verification methods. For dynamic activities at the verification center where XML is used .

6.1.3:AES (Advanced Encryption Standard) Algorithm

For encryption and decryption of the data sensed by the sensors AES algorithm is used which is based on symmetric key encipherment.

6.1.4: Tracker mapping tool

When we use many sensors in a small region, which are deployed close to each other( indoor application) their location cannot be differentiated using normal GPS system. Because when many sensors are deployed close to each other GPS indicates that all the sensors are placed in the same location. In order to overcome this issue we develop a tracker mapping tool which helps in finding the location of the sensor when two or more sensors are placed close to each other. As a result the exact location of the sensor and the minute variation in its location can be predicted easily. The tracker mapping tool is based on GPS system .The VC and Sensors should be connected using wifi technology during implementation.

6.2: STEPSIN VERIFYING SENSOR LOCATION

 Sensors are placed in region where vibration has to be sensed.
 The sensors are registered at the VC using the IMEI number , a unique number for all cell phones.
 The android application is installed in the phone and it is run. Thus we can get the latitude, longitude and vibration value using GPS .
 During registration along with IMEI number other information such as latitude and longitude of the deployed position, radius range and the tolerace are stored at VC.
 We can use the functions such as find, Update and delete for finding the sensor node,updating it and deleting the registered sensor node respectively.
 When the vibrations are sensed by the sensor nodes its information is passed to the VC.
 At VC, the current GPS location of the sensor which is sending the data(vibration) is compared with the registered location values. If the new value is in the tolerable and radius range . Then the data is accepted or else it is rejected. It is on-spot verification method.
 In in-region verification method the location details of the sensor which is sending data and its neighbouring sensor nodes location is compared with the previous values with respect to the sensor which is sending data. If they are in the tolerable range then the data is accepted or else it is rejected

VII.RESULTS

When the user starts the application he can see the welcome page that shows the simple arrangement of VC andsensors with the continue button as shown in Fig.1.
image
Fig.1: welcome screen
If the user press the continue button he will get the main screen it has a main menu button on the left top corner and if he presses the main menu, a drop down with sub option will get displayed if he select the register device option it will take him to the page which displays all the functionalities as shown in Fig.2.
image
Fig.2: functionality window
And he can do operation like register the device if it is successful it popup a window indicating the register is successful as in Fig.3.
image
Find option to find the devices that are already registered successfully in the list as shwn in Fig.4.
image
Fig.4: find device
The delete option helps to delete/unregister the devices as in Fig.5., the update option helps to update the devices that already registered.
image
Fig.5: delete device
On the other side the android device has to be installed with the software that provides the latitude, longitude and vibration values. On the start of the application we will see a text box where we need to enter the IP address of the VC and press save button , it will take to a page where all the information will be displayed it has two options Exit and IMEI. If user select exit it will end the application and if select the IMEI option it gives the IMEI number of the phone, which he can use to register the device at the VC. These are shown in Fig.6.
image
Fig.6:android app screens
The other option of the main menu is track data which help us to track the sensors(android phone sensors) if the user select this option it will show a window with options like start,stop, clear data, on-spot and in-region these provide the respective operation and is shown in the Fig.7.
image
Fig 7: Tracker and its functionalities

VIII.CONCLUSION AND FUTURE WORK

This paper implements light weight location verification method using on-spot and in-region verification method that uses GFT and GFM algorithms. We make use of GPS and tracker mapping tool for finding the location of the sensors this can be implemented in a low cost as it does not make use of costly hardware or software system. Many localization schemes does not provide sufficient information for indoor application. But this paper uses the tool called tracker mapping tool in order to support indoor applications.
The new webpage can be created which displays the information of the sensor stored at the verification centre(VC) such as location trustability, data authentication. This helps the organization that work on the application related to WSN’s to have localization information of the sensors that are deployed in hostile envorinment where manual interaction cannot be done frequently

References

  1. Yawen Wei and Yong Guan, “Lightweight Location Verification Algorithms for Wireless Sensor Networks”, IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 24, NO. 5, MAY 2013.
  2. AvinashSrinivasan and Jie Wu, “A Survey on Secure Localization in Wireless Sensor Networks”.
  3. VaidyanathanRamadurai, Mihail L. Sichitiu, “Localization in Wireless Sensor Networks:A Probabilistic Approach”.
  4. AnouarAbdelhakimBoudhir, Bouhorma Mohamed, Ben Ahmed Mohamed, “New Technique of Wireless Sensor Networks Localization based on Energy Consumption”, International Journal of Computer Applications (0975 – 8887)Volume 9– No.12, November 2010.
  5. JavadRezazadeh, MarjanMoradi, Abdul Samad Ismail, “Mobile Wireless Sensor Networks Overview”, IJCCN International Journal of Computer Communications and Networks , Volume 2, Issue 1, February 2012.
  6. Flora Salim, Mani Williams, Nishant Sony, Mars Dela Pena, YuryPetrov, Abdelsalam Ahmed Saad, Bo Wu, “Visualization of Wireless Sensor Networks using Zigbee’s Received Signal Strength Indicator (RSSI) for Indoor Localization and Tracking”,
  7. Yukihiro Kanamaru, Hidekazu Suzuki, Kensaku Asahi, Akira Watanabe, “Proposal for a Wireless Sensor Network Visualization System Using Location Estimation Technology”, 2014 Seventh International Conference on Mobile Computing and Ubiquitous Networking(ICMU).
  8. Sukhyun Yun , Jaehun Lee, Wooyong Chung, Euntai Kim, Soohan Kim, “A soft computing approach to localization in wireless sensor networks”, Expert Systems with Applications 36 (2009) 7552–7561.
  9. RaghavaSrinivasaNallanthighal ,VeeranjaneyuluChinta, “Improved Grid-Scan Localization Algorithm for Wireless Sensor Networks”,Hindawi Publishing Corporation Journal of EngineeringVolume 2014, Article ID 628161, 5 pages.
  10. Jing WANG, R. K. GHOSH, Sajal K. DAS , “A survey on sensor localization”, South China University of Technology and Academy of Mathematics and Systems Science, CAS and Springer-Verlag Berlin Heidelberg 2010.
  11. KiranYedavalli ,BhaskarKrishnamachari, “Sequence-Based Localization in Wireless Sensor Networks”, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO. 1, JANUARY 2008.
  12. M.M.Chithra, A.Gayathri, S. SelvaBirunda, “Securing and Region Based Algorithms ForWireless Sensor Networks”, International Journal of Innovative Research in Computer and Communication Engineering(An ISO 3297: 2007 Certified Organization) Vol.2, Special Issue 1, March 2014 .
  13. K.Rajesh,S.Manikandan, “ROBUST VIRTUAL ENERGY KEY MANAGEMENTBASED LOCATION VERIFICATION SYSTEM FOR WSN”, International Journal of Innovative Research in Science, Engineering and Technology (An ISO 3297: 2007 Certified Organization)Vol. 3 , Issue 4 , April 2014.
  14. Shyi-Ching Liang, LunHao Liao, Yen-Chun Lee , “Localization Algorithm based on Improved Weighted Centroid in Wireless Sensor Networks”, JOURNAL OF NETWORKS, VOL. 9, NO. 1, JANUARY 2014.
  15. VimeeWaliaand Simarpreetkaur. (August, 2014). “SURVEY OF DIFFERENT LOCALIZATION TECHNIQUES OF WIRELESS SENSOR NETWORKS”. IJEEE, Vol. 1, Issue 4 (August, 2014) e-ISSN: 1694-2310 | p-ISSN: 1694-2426.
  16. Amitangshu Pal. (2010). “Localization Algorithms in Wireless Sensor Networks: Current Approaches and Future Challenges”. ISSN 1943-3581 2010 Vol. 2, No.1. Charlotte, North Carolina.
  17. N. A. Alsindi, K. Pahlavan, and B. Alavi. (October 2006). “An Error Propagation Aware Algorithm for Precise Cooperative Indoor Localization”. http://dx.doi.org/10.1109/MILCOM.2006.302311 .Washington, DC, USA: in Proceedings of IEEE Military Communications Conference MILCOM 2006, pp. 1-7.
  18. LingxuanHu ,David Evans, “Localization for Mobile Sensor Networks”, In Tenth Annual International Conference on Mobile Computing and Networking (MobiCom 2004). Philadelphia, 26 September - 1 October 2004.
  19. Adel Youssef , Ashok Agrawala, Mohamed Younis, “ Accurate Anchor-Free Node Localization in Wireless Sensor Networks”.
  20. Nissanka B. Priyantha, HariBalakrishnan, Erik Demaine, Seth Teller, “Anchor ssssFreeDistributed Localization in Sensor Networks”.