Grid-Based Localization Mechanism with Mobile Reference Node in Wireless Sensor Networks

Kuo-Feng Huang, Po-Ju Chen, and Emery Jou

Grid-Based Localization Mechanism with Mobile Reference Node in Wireless Sensor Networks

Kuo-Feng Huang, Po-Ju Chen, and Emery Jou

—Wireless sensor networks (WSNs) are based on monitoring or managing the sensing area by using the location information with sensor nodes. Most sensor nodes require hardware support or receive packets with location information to estimate their locations, which needs lots of time or costs. In this paper we proposed a localization mechanism using a mobile reference node (MRN) and trilateration in WSNs to reduce the energy consumption and location error. The simulation results demonstrate that the proposed mechanism can obtain more unknown nodes locations by the mobile reference node moving scheme and will decreases the energy consumption and average location error.

Index Terms—Localization, mobile sensor node, received signal strength indicator, wireless sensor networks.

1. Introduction

Recently wireless sensor networks (WSNs)[1]-[3]are getting more and more convenient, and both applications and researches are becoming skillful. WSNs will deploy sensor nodes in the target area for monitoring and sensing the environmental information. Awareness of the accurate positions of the sensor nodes could improve the data transmission rate. Meanwhile, the deployment of sensor nodes in WSNs can be categorized into two cases which are random deployment and uniform deployment. In the random distribution case, we usually need other hardware or time costs to estimate the unknown sensor’s position. Furthermore, the costs will affect the accuracy of position estimated and induce the location error to be serious. Hence, the localization mechanism reducing the localization error is an important issue in WSNs[4],[5].

The localization mechanisms can be classified as range-based and range-free approaches. Range-free approaches do not assume the availability or validity of distance information and only rely on the connectivity measurements of undetermined sensors to a number of seeds[1]. Having lower requirements on hardware, the accuracy and precision of range-free approaches are easily affected by the node densities and network conditions, which are often unacceptable for many WSN applications that demand precise localization. Range-based approaches calculate node distances based on some measured quantity[6], whereas they usually require extra hardware support; thus, they are expensive in terms of manufacturing costs and energy consumption. And how to reduce the extra costs becomes an important task to find out. When the sensor node position is estimated, the data transfer speed and other parameters needed to be optimized will have significant improvements.

In this paper we proposed a mechanism using a mobile reference node (MRN) with the received signal strength indicator[7](RSSI) and trilateration in WSNs localization to reduce energy consumption and the location error. The rest of this paper is arranged as follows. Section 2 reviews some range-based and range-free approaches. The proposed MRN mechanism is described in Section 3. Section 4 presents the simulation results. Finally, the conclusions are drawn in Section 5.

2. Related Work

The mechanisms proposed to estimate sensor node positions in literature fall into two categories: range-free and range-based approaches.

2.1 Range-Free Approaches

In an approximate point-in-triangulation test (APIT)[6], some sensor nodes transmit signals with the global position system (GPS) in a high frequency or in other ways to obtain sensor nodes locations, which are called beacon. Each node estimates whether it resides inside or outside several triangular regions bounded by the beacons which are also called seeds, and hears and refines the computed location by overlapping such regions which are usually triangles. As an alternate solution, DV-Hop[8]only makes use of a constant number of seeds. Instead of single-hop broadcasting, seeds flood their locations throughout the network, maintaining a running hop count at each node along the path. Nodes calculate their positions based on the received seed locations, and the hop counts from the corresponding anchors and the average distance per hop through the trilateration method.

2.2 Range-Based Approaches

The time of arrival method (TOA) obtains the range information through signal propagation time[9], and the time-difference-of-arrival method (TDOA) estimates the node locations by utilizing the time differences among signals that are received from multiple senders[9]. As an extension of TOA and TDOA, the angle of arrival method (AOA) allows nodes to estimate the relative directions between neighbors by setting an antenna array for each node[10]. However, all those approaches require expensive hardware costs. RSSI is utilized to estimate the distance between two nodes with ordinary hardware[7]. Various theoretical or empirical models of radio signal propagation have been constructed to map absolute RSSI values into estimated distances. Recently, mobile-assisted localization approaches have been proposed to improve the efficiency of range-based approaches. The location of a sensor node can be calculated with the range measurements from the mobile node to itself.

With the RSSI values from the mobile node to an unknown node in an ideal sense, the distance between other unknown nodes should be calculated according to the log-normal shadowing model in (1), which is widely used in the range-based localization approaches[7]:

whereTPis the transmission power,is the path loss for a reference distance of0d,dis the actual distance between two nodes, and α is the path-loss exponent. The random variation in RSSI is expressed as a Gaussian random variableXσ=N(0,2σ). All values of power are given in decibels relative to 1 mW, and all distances are given in meters. α is set between 2 and 5. σ is set between 4 and 10, depending on the specific environment[7].

3. Localization Mechanism with Mobile Reference Node

The proposed mechanism can be divided into two phases: the node localization phase and mobile reference node moving direction decision phase. We assume that each unknown sensor node (USN) has its unique node ID and mark the upper left corner as the initial position of the mobile reference node. The trilateration[11]is used in this paper to calculate the unknown node location. The sink knows the length (defined asL) and width (defined asM) of the entire environment after the deployment of the sensor nodes. The length of each grid is defined as the transmission radiusRof the mobile reference node (MRN). Moreover, there are two parameters,kandp, which will be used to make the following decisions: 1) divide each virtual grid and tag an grid ID on each virtual grid; 2) determine the mobile reference node’s start position; 3) help MRN to set the first direction needed to turn. Andkandpare

3.1 Node Localization Algorithm

In this section, we present a node localization algorithm which contains two phases: a) MRN broadcast algorithm and b) sensor node localization algorithm.

A. MRN Broadcast Algorithm

As shown in Fig. 1, at first, MRN broadcasts a Wake_up beacon to wake up the USNs in the virtual grid. After that, MRN broadcasts an Initial_start signal and moves R/2. It will broadcast an Initial_stop signal and a Wake_up beacon again to wake up some USNs who have not woke in the first broadcast. Meanwhile, it will broadcast a Middle_start signal and start to move to the end point of a virtual grid’s length. When MRN moves to the end point, it will broadcast a Middle_stop signal which means that MRN has finished moving the length of the grid side. As shown in Fig. 2, it is a single virtual square broadcast. The Initial_stop signal and Middle_stop signal are used to notify the unknown sensor nodes that have already calculated coordinates to return the location coordinates to MRN. The start signal packet contains two fields: the Start_signal_flag and mobile node coordinate. The Start_signal_flag is used to indicate what kind of the signal type is.

Fig. 1. MRN broadcast algorithm.

Fig. 2. Single virtual square broadcast.

However, USN may locate at the special regionxas shown in Fig. 3. The special region is determined by whether the value ofkis an odd value. The USN, located at the position ofx, can receive the start signal when MRNcome to (1) as shown in Fig. 3. USN makes a count on the number of received signals for executing the localization algorithm after receiving the first signal. Meanwhile, the sleeping control strategy is triggered when the USN does not receive any signal more than the threshold of time duration. When MRN moves to (2), it broadcasts the Wake_up beacon to ensure the USN can receive the Middle_start signal. Otherwise, if MRN moves to (3) and (4), it will broadcast an Exception_start signal for USN located at the special region, which can receive the third signal.

Fig. 3. Special regions: (a) one edge situation (1), (b) one edge situation (2), (c) two edges situation, and (d) no edge situation

B. Sensor Node Localization Algorithm

As shown in Fig. 4, we give USNs a threshold time period to wait, defined as R_time which is greater than the moving time. We will make USNs wait for R_time before the USNs get into the sleep state until the Wake_up beacon is accepted in the next action. USNs will estimate its own location through the trilateration after it receives three signals and one end signal. When USN receives three signals, it will keep in the awaking state for receiving the end signal.

Fig. 4. Sensor node localization algorithm.

3.2 MRN Moving Direction Scheme

We propose an MRN moving direction algorithm to determine the moving direction of MRN as shown in Fig. 5, which is divided into two cases: i)kis even and ii)kis odd. There are several variables is used to determine the moving direction here.Sis the special grid number which is equal to the biggest grid number of the next-to-last row. MD_cnt is the number of the rotation. N_cnt is the number of straight moving times.Nis used to determine whether MRN has to change the direction or not. Andtis used to set the direction of rotating (true: left turn, false: right turn).

Fig. 5. MRN moving direction algorithm.

A. When k Is Even

Whenkis even, the MRN moving direction is determined according to the following procedures. Firstly,Swill be set as 1 if the value ofpis even. MRN will determine whether it has moved into the special grid or not through the value ofS. It will utilize MD_cnt and N_cnt to decide the moving direction as shown in Fig. 6.

Fig. 6. MRN moving direction procedure when k is even.

B. When k Is Odd

Whenkis odd, the MRN moving direction is determined according to the following procedures. Firstly,Swill be set as 1 if the value ofpis even. MRN will determine whether it has moved into the special grid or not through the value ofS. It will utilize MD_cnt and N_cnt to decide the moving direction as shown in Fig. 7.

Fig. 7. MRN moving direction procedure when k is odd.

4. Simulation and Analysis

In this section, we use NS2 vision 2.29 as the simulator to analyze the proposed localization mechanism. The simulation parameters are shown in Table 1[12]. We discuss the result in two aspects: i) average location error and ii) energy consumption. Four other RSSI-based localization approaches are compared, which are a range-based approach of trilateration (TRL)[7]and three mobile-assisted localization approaches that are PI[12](perpendicular intersection: locating wireless sensors with mobile beacon), BI[12](localization of WSNs with a mobile beacon), and MBBGC[13](localization with a mobile beacon based on geometric constraints in WSNs).

Table 1: Parameter setting

4.1 Average Location Error Analysis

Six different environment sizes and the corresponding sensor nodes number are shown in Table 2.

As shown in Fig. 8, PI has the similar performance with the proposed MRN method by continuously finding the strongest signal strength and using the triangulation method to achieve the lowest error rate. For the MBBGC, the error rate will increase when the environment size is increasing. The accuracy of MBBGC decreases due to the USNs located at the boundary of intersection or the random move of the mobile node.

Table 2: Sensor nodes number

Fig. 8. Average location error.

4.2 Energy Consumption Analysis

As shown in Fig. 9, the proposed MRN method has lower energy consumption than the others. PI needs to continuously broadcast to find the strongest signal strength for increasing the localization accuracy. The proposed method just needs to broadcast three signals for each edge of the reference node’s route. The proposed method can save significant energy consumption for signaling in this strategy than PI. Otherwise, the energy consumption is increasing due to the random moves of the mobile node when the environment size is increasing. The difference in energy consumption between MBBGC and MRN is 130000 mW when the environment size is 600 m2.

As shown in Fig. 10, The proposed MRN method could save more energy consumption than the others when the environment size increases. The sleeping control mechanism of MRN could avoid the USNs wasting energy with a setting waiting threshold. Sensor nodes have to keep awaking before the mobile node receiving the coordinate information in both PI and MBBGC. The difference in energy consumption between MRN and PI is approximately 43000 mW and the difference between MRN and MBBGC is approximately 59000 mW when the size is 600 m2.

Fig. 9. Mobile node energy consumption.

Fig. 10. Unknown sensor nodes energy consumption.

5. Conclusions and Future Work

In WSNs, the throughput will be high when we can handle all sensor nodes’ locations in the whole environment. Nowadays, there are a lot of localization technologies restricted by the cost or the natural environment. Therefore, in some cases the location error can not be avoided. To reduce the location error we need to find other paths to make the breakthrough.

In this paper, we propose a localization mechanism by using MRN with the RSSI method to estimate distances. Then we use the trilateration method to ensure the location more accuracy. The simulation results show that the mechanism we propose have smaller location errors compared with other methods. And in the energy consumption comparison, the proposed mechanism has a very significant reduction, whether in the mobile node or unknown nodes.

In the future, we will improve our mechanism in the three-dimensional size of the environment, and overcome the obstacles in the moving path to make sure the moving algorithm can cover the whole environment.

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102-114, 2002.

[2] A. Panwar and S. A. Kumar, “Localization schemes in wireless sensor networks,” in Proc. of Int. Conf. on Advanced Computing & Communication Technologies, Rohtak, 2012, pp. 443-449.

[3] U. Nazir, M. A. Arshad, N. Shahid, and S. H. Raza,“Classification of localization algorithms for wireless sensor networks: A survey,” in Proc. of Int. Conf. on Open Source Systems and Technologies, Lohore, 2012, pp. 1-5.

[4] R. Garg, A. L. Varna, and M. Wu, “An efficient gradient descent approach to secure localization in resource constrained wireless sensor networks,” IEEE Trans. on Information Forensics and Security, vol. 7, no. 2, pp. 717-730, 2013.

[5] H. Chenji and R. Stoleru, “Toward accurate mobile sensor network localization in noisy environments,” IEEE Trans. on Mobile Computing, vol. 12, no. 6, pp. 1094-1106, 2013.

[6] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. F. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” ACM Trans. on Embedded Computing System, vol. 4, no. 4, pp. 877-906, 2005.

[7] J. Hightower, G. Borriello, and R. Want, “SpotON: An indoor 3D location sensing technology based on RF signal strength,” M.S. thesis, Department of Computer Science and Engineering, University of Washington, Seattle, USA, 2000.

[8] D. Niculescu and B. Nath, “DV-based positioning in ad hoc networks,” Kluwer J. Telecommunications System, vol. 22, no. 1, pp. 267-280, Jan. 2003.

[9] K. D. Frampton, “Acoustic self-localization in a distributed sensor network,” IEEE Sensors Journal, vol. 6, no. 1, pp. 166-172, Feb. 2006.

[10] F. Dai and J. Wu, “Efficient broadcasting in ad hoc wireless networks using directional antennas,” IEEE Trans. on Parallel and Distributed Systems, vol. 17, no. 4, pp. 335-347, Apr. 2006.

[11] J. Sun, J. Yu, L. Zhu, D. Wu, and Y. Cao, “Construction of generalized ricci flow based virtual coordinates for wireless sensors network,” IEEE Sensors Journal, vol. 12, no. 6, pp. 2109-2112, Jan. 2012.

[12] Z.-W. Guo, Y. Guo, F. Hong, Z.-K. Jin, Y. He, Y. Feng, and Y.-H. Liu, “Perpendicular intersection: locating wireless sensors with mobile beacon,” IEEE Trans. on Vehicular Technology, vol. 59, no. 7, pp. 3501-3509, Sep. 2010.

[13] S. Lee, E. Kim, C. Kim, and K. Kim, “Localization with a mobile beacon based on geometric constraints in wireless sensor networks,” IEEE Trans. on Wireless Communications, vol. 8, no. 12, pp. 5801-5805, Dec. 2009.

Kuo-Feng Huangwas born in Hsinchu in 1979. He received the M.S. and Ph.D. degrees from the Department of Computer Science and Information Engineering, Tamkang University, Taipei in 2007 and 2011, respectively. Presently, he is working at the Institute for Information Industry (III) as a section manager, Taipei. His major research interest is wireless networks.

Po-Ju Chenwas born in Taichung in 1979. She received her M.S. degree from the Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan in 2003. She is currently an engineer at the Institute for Information Industry (III), Taipei. Her research interests include wireless networks and embedded systems.

Emery Jouwas born in Taoyuan in 1950. He received his B.S degree in physics from Tsing Hua University, Hsinchu, his M.S. degree in computer science from University of Texas at Austin, USA, and his Ph.D degree in computer science from University of Maryland at College Park, USA. Dr. Jou had been working at Wall Street, USA over 12 years (Morgan Stanley and JPMorganChase). He had also been working with Thales nCipher at Cambridge UK. In 2009, Dr. Jou was a visiting professor at College of Computer Science, Chiao Tung University, Hsinchu. He was also a consultant with the Industrial Technology Research Institute (ITRI). Dr. Jou is currently a research scientist at the Institute for Information Industry (III), Taipei. His research interests include wireless networks and in-memory computing.

Manuscript received December 3, 2013; revised March 13, 2014.

K.-F. Huang is with the Institute for Information Industry, Taipei 10622 (Corresponding author e-mail: sailerhuang@iii.org.tw).

P.-J. Chen and E. Jou are with the Institute for Information Industry, Taipei 10622 (e-mail: cpoju@iii.org.tw; emeryjou@iii.org.tw).

Color versions of one or more of the figures in this paper are available online at http://www.journal.uestc.edu.cn.

Digital Object Identifier: 10.3969/j.issn.1674-862X.2014.03.008