# Research on the WSN Node Localization Based on TOA

Authors: Qing-hui Wang; Ting-ting Lu; Meng-long Liu; Li-feng Wei
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Regarding the tracking of moving target in the large-scale fixed scene, a new routing algorithm of LAODV in the principle of TOA localization is proposed. Then, the participation field of the fixed node based on the node location information is properly controlled, while the routing request area is reduced through combination of AODV and LAR during transmission of the location information. Simulation results show that the proposed algorithm renders satisfactory performance in terms of average delay reduction from end to end, packet loss rate, and routing overhead. As a result, the delay and system overhead during localization could be minimized.


---

## Body

## 1. Introduction

LBS service is developing along with rapid economic growth and great market potential. Also, wireless localization technology is one of the favorite research topics in recent years, where the position of the event or the node position is crucial for detection of sensor node [1, 2]. Normally, the wireless localization can be realized through satellite technology or ground technology [3]. Due to constraints of the node, such as the limited electric energy, huge quantity, and specific application environments, it is difficult to obtain the node coordinate with artificial measurement or allocation. Thus, implementation of expensive satellite wireless localization seems infeasible [4]. As for the ground wireless localization technology, the target localization is realized through multipoint coordination, the advantages of which include the distributed feature, low complexity, high precision, and good generality. The TOA-based (Time of Arrival) localization technology has been widely applied in the ground wireless localization [5–7]. Also, the moving node will send the location package to the neighboring node periodically, while the fixed node will respond back to the moving node once received. Therefore, there are alot of fixed nodes participating in the localization process, which will generate heavy communication overhead and reduced localization bandwidth.There is a high demand for low-cost high-precision localization scheme in various fields, such as industrial field, safety production management, security, and training. In the security monitoring, the current patrol system could be totally replaced, and the real-time position and route of the security personnel are clearly visible, so that prompt action of emergency can be taken. Moreover, the “virtual fence” is set up based on the geographic location of the visitors and the authorized condition to track the visitor. Then, entrance permission to particular region is conditionally issued. With increasing coalmine accidents, safety production situation is highly desired, as the administrative staff can monitor the location and situation of each miner remotely through the electronic tag wear by the miner or equipped on the delivery vehicles [8]. Furthermore, in the training of firemen, the training personnel in the building can be located and tracked through the allocated node in each floor. Such specific subject simulation can significantly improve the training quality and effectiveness.In this paper, the TOA-based distance measurement method is proposed to localize the moving node. During the distance measurement and localization, limited nodes are chosen, so that the localization delay and system overhead could be reduced. During data transmission, the location information of the node is applied to restrict the routing request region through combination of AODV (Ad hoc On-Demand Distance Vector Routing) with LAR (Location-Aided Routing). As a result, the transmit time of the RREQ (Route Request) package is reduced along with improved system transmission performance, which is verified by simulation study with NS2 emulator.


## 2. TOA Localization Algorithm

TOA [9] refers to the time for the signal to travel from the sending node to the receiving node. Given signal transmission speed, by measuring the signal transmission time to calculate the distance between two nodes. In this paper, by measuring RTOF (Roundtrip-Time Of Flight) to calculate the distance between two nodes, as shown in Figure 1 the equation for the distance between two nodes is
(1)d=[(T3-T0)+(T2-T1)]×V2,
where T0 is the moment when the sending node sends signals, T1 is the moment when the receiving node receives signals, T2 is the moment when the receiving node sends response signals, T3 is the moment when the sending node receives response signals, and d is the distance between the sending node and receiving node.Figure 1
Round trip travel time.In the large-scale fixed field, the moving node is required for localization, while the fixed node is the one with known information. The neighboring nodes are those within the radius of sensor node communication. The distance from the moving node to the fixed one can be obtained with TOA distance measurement method, as described earlier. When the distance from the moving node to at least three fixed nodes is known, the location of moving node can be calculated with trilateration [10].


## 3. AODV Protocol

AODV is the routing protocol based on the distance vector algorithm, which integrates the target serial number of DSDV and the on-demand routing discovery in DSR [11]. This protocol mainly includes routing discovery and routing maintenance, where the former is only requested upon need to save the routing overdue.When the source node communicating with other nodes fails to reach the routing of destination node, it requires the grouping of RREQ. After other nodes receive this RREQ, whether such information exists or not is checked. Then, the information should be abandoned when necessary. Otherwise, it should record the RREQ in this routing table and broadcast this RREQ continuously until some central node reaches the routing of destination node, or the routing request grouping reaches the destination node.


## 4. LAODV Algorithm

In this paper, localization of the moving node is desired, while the fixed one provides assistance. First, the moving node broadcasts a data package with location information of the moving nodes to the neighboring node periodically. Then, the distance between this node and the moving one should be calculated once the fixed nodes receive it within the broadcasting range, and decision of whether response information back to the moving nodes should be sent is made. In this algorithm, only four fixed nodes near to the moving node participate, so that the quantity of the involved nodes is limited. Therefore, the average delay and system overhead of the localization are minimized.In AODV protocol, the node requests for the routing of the destination node through broadcasting RREQ message gradually. Such a flooding routing method will unfortunately generate substantial RREQ message, resulting in a tremendous signal conflict and protocol overhead. The proposed protocol will add the thought of LAR protocol [12], which will transfer the data package selectively during the process of routing discovery within the appointed routing area.As shown in Figure2, node S is the moving node, D is the gateway, others are fixed nodes, and their location coordinates are known. Each fixed node broadcasts its location information to the whole network, after other fixed nodes receive it, record information to their location information table, so that each fixed node has the position information of the other nodes. The moving node S broadcasts a location package, including the location coordinate of S calculated in the last moment. After the fixed nodes receive this package within the broadcasting scope, it can calculate the distance between the node and other fixed nodes with the moving node S. Through comparison, to judge whether the node is one of the four nodes closest to the moving node S, if it is, just send a response information, including the location coordinates of fixed nodes. In this case, only nodes A, B, P, and M send response information.Figure 2
Node location distribution.Moving node S gets the location coordinates of A, B, P, and M which are(x1,y1), (x2,y2), (x3,y3), and (x4,y4), respectively through the response information, and through the TOA-based distance measurement method can get the distances between them and the moving node S as d1, d2, d3, and d4, respectively. Given the coordinate of the moving node S by (x,y), the following equation can calculate the location coordinate of the moving node:
(2)(x-x1)2+(y-y1)2=d1(x-x2)2+(y-y2)2=d2(x-x3)2+(y-y3)2=d3(x-x4)2+(y-y4)2=d4.Meanwhile, the source node S sends its location coordinate to the destination node D. As the routing information of D is not reachable, node S will send RREQ to seek for the routing to D with its location information included in RREQ. At first, a rectangular request region with two apexes of nodes S and D is determined. When node P out of the region receives the request package, decision of whether it is within the request region will be made, and the invalid grouping could be abandoned according to the location information. Then, node M within the region will transfer the grouping in the request region with its own location information included in the RREQ package. The new request region is established by the source node and destination node, until the node within the region reaches the radio-frequency scope of node D and the routing discovery is successful. Hence, the source node could send its own location coordinate information to the gateway according to this new route.


## 5. The Specific Process of Algorithm

(1)
Each fixed nodes broadcasts a location package including its location information to the whole network. After other fixed node receive it, record information to their location information table.
(2)
The moving node broadcasts a location package, including the location coordinate calculated in the last moment.
(3)
After fixed nodes receive the package, calculate the distance between the node and other fixed nodes with the moving node.
(4)
To determine whether the node is one of the four nodes closest to the moving node, if it is, just send a response information.
(5)
Given four fixed node coordinates, and through the TOA-based distance measurement method can get the distances between them and the moving node, again through the trilateration it can calculate the moving node coordinate.


## 6. Simulation and Analysis

### 6.1. Principle of NS2

In this study, the NS2 network emulator is adopted for performance verification [13]. NS2 simulation process in general is shown in Figure 3.Figure 3
NS2 simulation flow chart.


### 6.2. The Simulation Scene Set

As shown in Figure4, a rectangular simulation field of 1000 m * 1000 m with 33 nodes is assumed, 26 of which are fixed nodes and the others are moving nodes. The distance of the adjacent fixed nodes is 150 m, and four nodes form the square grid. The highest movement speed of the node is 13 m/s, and the simulation time is set as 200 seconds. The CBR data flow will be established from every moving node to the gateway, and the data package of 512 bytes will be sent with a speed of 4 packet/s. More simulation parameters are illustrated in Table 1.Table 1
Parameter setting for simulation environment.
Parameter
Parameter value
channelType
Channel/wireless channel
phyType
Phy/wirelessPhy
macType
Mac/802_11
ifqType
Queue/drop tail/PriQueue
llType
LL
antType
Antenna/omni antenna
businessType
CBR
nodeQuantity
33Figure 4
Simulation scene and node distribution.After simulation scene has been setted, writing TCL script simulation is carried out on the protocol. After the simulation will be get trace and nam files, the trace file is a data storage, nam file is the whole process of simulation of dynamic demonstration. In order to analyze a large amount of data of the trace file, we need to write the gawk program for the extraction and processing of effective data (calculate the average end-to-end delay, Package loss probability, etc.). In the end, using gnuplot drawing tools will be extracting data into two-dimensional graphics which can be more intuitive to analyze the protocol performance.


### 6.3. Analysis of Location Delay and System Overhead

In this paper, average localization delay refers to the average time for the moving node to send localization package until receiving response package, the system overhead refers to the proportion between the fixed nodes send response package number and the moving nodes send localization package number. Figures5 and 6 show that the average localization delay of the algorithm is 0.00021, the system overhead is 4.8, while the AODV and system overhead are 0.00033 and 7.7, respectively. Obviously, the new algorithm is advantageous in terms of localization delay and system overhead. This is mainly because the quantity of the fixed nodes participating in location is limited, and the relative distance from the fixed nodes to the moving nodes is short.Figure 5
Average localization delay.Figure 6
System overhead during location process.


### 6.4. Performance Analysis of Data Transmission

In this paper, the performance index, including the average end-to-end delay of the network, the packet loss probability and routing overhead, is evaluated.(1)  Average End-to-End Delay. The average time for the moving node to send the data package until the gateway receives the data package successfully, which is related to smoothness of the network. The smaller the delay is, the smoother the network will be. The unit is second.Figure7 compares the average end-to-end delay of LAODV and AODV. Clearly, the delay of the LAODV protocol is smaller than that of the AODV protocol, as the location information of the node is added into the improved protocol. Through the calculation of the routing request area, it improves the seeking efficiency of the node for routing. When the flexible routing is interrupted due to the moving node, it will establish a new routing towards the destination node rapidly through the discovery mechanism of LAODV. Then, the seeking time for the route could be reduced, and the smoothness of the data transmission in the network is guaranteed.Figure 7
Average end-to-end delay.(2) Package Loss Probability. The proportion of the total lost data grouping is against the sent data grouping in the network. Then, the successful data transmission proportion in the whole network can be known, as well as the proportion of the lost data package during the transmission process due to the link failure. This parameter is related to the efficiency of the data transmission.Figure8 shows comparison of the packet loss probability between the two protocols. It can be seen that the packet loss probability decreases gradually after the routes are established, and the packet loss probability of LAODV is smaller than that of AODV.Figure 8
Packet loss probability.(3)  Routing Overhead. The proportion between the total number of bytes and total message bytes of all the messages controlled by the route (including RREQ, RREPs and RERR messages). As for the grouping transmitted by various routes, a single bounce will trigger a message transmission. The routing overhead is mainly used for balancing the efficiency of the routing protocol. The smaller the routing overhead is, the narrower bandwidth is needed to reach the destination node.Figure9 shows the comparison of the routing overhead for two protocols. The routing overhead of LAODV is obviously smaller than that of AODV, as LAODV sets the routing request region utilizing the node location information. Then, the quantity of the transferred RREQ is smaller than that with AODV protocol, and the redundant routing request information is reduced. As a result, the routing overhead decreases accordingly.Figure 9
Routing overhead.


## 6.1. Principle of NS2

In this study, the NS2 network emulator is adopted for performance verification [13]. NS2 simulation process in general is shown in Figure 3.Figure 3
NS2 simulation flow chart.


## 6.2. The Simulation Scene Set

As shown in Figure4, a rectangular simulation field of 1000 m * 1000 m with 33 nodes is assumed, 26 of which are fixed nodes and the others are moving nodes. The distance of the adjacent fixed nodes is 150 m, and four nodes form the square grid. The highest movement speed of the node is 13 m/s, and the simulation time is set as 200 seconds. The CBR data flow will be established from every moving node to the gateway, and the data package of 512 bytes will be sent with a speed of 4 packet/s. More simulation parameters are illustrated in Table 1.Table 1
Parameter setting for simulation environment.
Parameter
Parameter value
channelType
Channel/wireless channel
phyType
Phy/wirelessPhy
macType
Mac/802_11
ifqType
Queue/drop tail/PriQueue
llType
LL
antType
Antenna/omni antenna
businessType
CBR
nodeQuantity
33Figure 4
Simulation scene and node distribution.After simulation scene has been setted, writing TCL script simulation is carried out on the protocol. After the simulation will be get trace and nam files, the trace file is a data storage, nam file is the whole process of simulation of dynamic demonstration. In order to analyze a large amount of data of the trace file, we need to write the gawk program for the extraction and processing of effective data (calculate the average end-to-end delay, Package loss probability, etc.). In the end, using gnuplot drawing tools will be extracting data into two-dimensional graphics which can be more intuitive to analyze the protocol performance.


## 6.3. Analysis of Location Delay and System Overhead

In this paper, average localization delay refers to the average time for the moving node to send localization package until receiving response package, the system overhead refers to the proportion between the fixed nodes send response package number and the moving nodes send localization package number. Figures5 and 6 show that the average localization delay of the algorithm is 0.00021, the system overhead is 4.8, while the AODV and system overhead are 0.00033 and 7.7, respectively. Obviously, the new algorithm is advantageous in terms of localization delay and system overhead. This is mainly because the quantity of the fixed nodes participating in location is limited, and the relative distance from the fixed nodes to the moving nodes is short.Figure 5
Average localization delay.Figure 6
System overhead during location process.


## 6.4. Performance Analysis of Data Transmission

In this paper, the performance index, including the average end-to-end delay of the network, the packet loss probability and routing overhead, is evaluated.(1)  Average End-to-End Delay. The average time for the moving node to send the data package until the gateway receives the data package successfully, which is related to smoothness of the network. The smaller the delay is, the smoother the network will be. The unit is second.Figure7 compares the average end-to-end delay of LAODV and AODV. Clearly, the delay of the LAODV protocol is smaller than that of the AODV protocol, as the location information of the node is added into the improved protocol. Through the calculation of the routing request area, it improves the seeking efficiency of the node for routing. When the flexible routing is interrupted due to the moving node, it will establish a new routing towards the destination node rapidly through the discovery mechanism of LAODV. Then, the seeking time for the route could be reduced, and the smoothness of the data transmission in the network is guaranteed.Figure 7
Average end-to-end delay.(2) Package Loss Probability. The proportion of the total lost data grouping is against the sent data grouping in the network. Then, the successful data transmission proportion in the whole network can be known, as well as the proportion of the lost data package during the transmission process due to the link failure. This parameter is related to the efficiency of the data transmission.Figure8 shows comparison of the packet loss probability between the two protocols. It can be seen that the packet loss probability decreases gradually after the routes are established, and the packet loss probability of LAODV is smaller than that of AODV.Figure 8
Packet loss probability.(3)  Routing Overhead. The proportion between the total number of bytes and total message bytes of all the messages controlled by the route (including RREQ, RREPs and RERR messages). As for the grouping transmitted by various routes, a single bounce will trigger a message transmission. The routing overhead is mainly used for balancing the efficiency of the routing protocol. The smaller the routing overhead is, the narrower bandwidth is needed to reach the destination node.Figure9 shows the comparison of the routing overhead for two protocols. The routing overhead of LAODV is obviously smaller than that of AODV, as LAODV sets the routing request region utilizing the node location information. Then, the quantity of the transferred RREQ is smaller than that with AODV protocol, and the redundant routing request information is reduced. As a result, the routing overhead decreases accordingly.Figure 9
Routing overhead.


## 7. Conclusion

In this paper, an approach for tracking the moving target and transmitting the location information in the large-scale fixed scene is developed. During the localization process, the quantity of fixed nodes participating in location is limited, so that the network overhead is reduced and the bandwidth of the system location by taking advantage of the location information of the located nodes is optimized. During the process of uploading the location information of moving nodes to the gateway, the quantity of request package transferred during the routing discovery with the node location information is also properly controlled. The effectiveness of the algorithm has been verified by the simulation results.



---

*Source: 706064-2013-10-09.xml*