# An eliminating method to improve localization accuracy.

1. IntroductionWireless sensor networks (WSNs) have been widely applied in target tracking, intrusion detection, and some related fields. However, most of such applications are based on the location information of the target. Therefore, node localization is essential and fundamental in the research of WSNs.

So far, there are many localization algorithms exiting in the world. Based on whether they measure the distance or not, those localization algorithms can be grouped into two categories: the range-based method and the range-free method [1,2]. The range-based localization method estimates the node position by measuring the physical distance or the angle among sensor nodes. After the distance or angle has been determined, the location can be estimated. There are many rang-based localization methods which had been proposed during the past decades such as time of arrival (TOA) [3], time difference of arrival (TDOA) [4], angle of arrival (AOA) [5], and received signal strength indicator (RSSI) [6]. And many of them had been applied in practical scene, for example, TOA based indoor human tracking system [7] and the real-time health monitoring system [8]. In spite of the good localization accuracy of the range-based method, the study of node localization is recently focused on the range-free method. That is because the range-free methods such as DV-Hop [9], Amorphous [10], Bounding Box [11], APIT [12], DRLS [13], and SOM [14] do not need additional hardware and can be deployed easily. However, there are some common problems of the present range-free methods: (1) the localization accuracy is low and (2) the computation is complex. These problems cause more energy consumption to the overhead network.

In order to improve the localization accuracy and reduce the computation, based on the possible location area (PLA) of the unknown node, we propose an eliminating algorithm named NPLA. It eliminates the possible location area (PLA) constantly, where the unknown node was located in. In our algorithm, in addition to utilizing the communication range and hop-count message of all nodes, we also take full advantage of the possible location circle (PLC) of the unknown node to improve the accuracy of localization. Given the fact that the unknown node in WSNs is majority, NPLA can still obtain better localization accuracy. Analysis of simulation shows that the proposed NPLA algorithm can improve the localization accuracy significantly.

The rest of the paper is organized as follows. Section 2 lists the related work. Section 3 depicts the definitions and assumptions. Section 4 describes the algorithm. Section 5 describes the algorithm implementation. Section 6 introduces the simulation settings and analyzes the simulation performance. Finally, Section 7 concludes the paper.

2. Related Work

Over the past ten years, node localization algorithm mainly concentrates on the range-free field in wireless sensor network, and many range-free localization algorithms have been proposed, such as DV-Hop [9], Amorphous [10], Bounding Box [11], APIT [12], DRLS [13], and SOM [14].

DV-Hop algorithm proposed by Niculescu and Nath is the earliest range-free localization algorithm [9]. This algorithm first gets hop count between nodes by flooding information. Second, it calculates average hop distance using the hop count between anchor nodes. Third, it calculates the distance between unknown nodes and anchor nodes utilizing average hop distance and hop count. At last, it computes node coordinates using trilateration. DV-Hop algorithm achieves better effects in a homogeneous distribution network. However, if the nodes in the network are unevenly distributed, average hop distance calculation will have larger deviations; for this reason, the localization accuracy will be affected seriously.

Based on the DV-Hop, Nagpal et al. proposed algorithm Amorphous [10] which uses node communication radius as the average distance per hop. By this algorithm, although the network communication overhead is reduced and the calculation is simple, the positioning error is large. And subsequent algorithms modified the average hop distance to improve the positioning accuracy.

Simic and Sastry proposed Bounding Box [11] at the same period. The algorithm reduces the possible location area of unknown node by using the one-hop anchor neighbors of the node. And the implement of this algorithm is simpler. However, in this algorithm, it considers that the communication radius of all nodes is the same which is inconsistent with the real world scenario. And it also needs the higher density of anchor nodes.

He et al. introduced the point-in-triangulation test (PIT) to the wireless sensor networks and proposed APIT [12] localization algorithm. In APIT [12], an unknown node uses the PIT method to test whether it locates in the triangles constituted by its three different one-hop anchor neighbors or not. If the unknown node locates within several triangles, the possible position of it is the overlapping region of those triangles. However, those unknown nodes whose one-hop anchor neighbor number is less than three cannot be located. In addition, the implement of APIT [12] is simple, but the communication cost is relatively large for PIT testing.

To improve accuracy, Sheu et al. proposed a distributed range-free localization scheme (DRLS) [13] for static WSNs. In this scheme, each node gathers the nearby anchors' locations and then estimates its own location. The paper improved the grid-scan algorithm and derived a vector-based refinement scheme.

Giorgetti et al. proposed the SOM (self-organizing maps) algorithm [14], which is based on a neural network formalism known as self-organizing map and generates virtual coordinates that describe the relative positions of nodes [10]. The SOM [14] algorithm estimates the distance between every possible pairs of nodes roughly by using the shortest path algorithm and deduces the pairs of nodes distance by utilizing multidimensional scaling method and locates unknown nodes by using the position of anchor nodes.

To improve the accuracy of existing range-free localization algorithm, we propose a scheme called NPLA. We contrast the localization performance between DV-Hop [9], APIT [12], SOM [14], and NPLA in Section 6. According to the results of simulation, NPLA performs best in most scenarios.

3. Definition and Assumptions

3.1. Definition. To describe our method more conveniently, we list those definitions and symbols used in our paper in the Abbreviations Section. Before describing our method, we explain some definitions as follows.

Figure 1(a) shows [V.sub.PLA]([A.sub.1]) of [A.sub.1]. [V.sub.PLA] ([A.sub.1]) is the possible location area of the anchor node [A.sub.1]. The center, 01, is the coordinate position of anchor node [A.sub.1] measured by GPS. The radius, [Re.sub.g], is the absolute error of [A.sub.1]'s coordinate position measured by GPS.

Figure 1(b) shows [V.sub.PCC]([A.sub.1]) and [V.sub.VCC] ([A.sub.1]) of [A.sub.1]. [V.sub.PCC]([A.sub.1]) is the possible communication circle of the anchor node [A.sub.1]; its radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [V.sub.ICC]([A.sub.1]) is the inevitable communication circle of anchor node A1; its radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Figure1(c) shows [V.sub.PLA]([U.sub.m+1]) and [V.sub.PLC]([U.sub.m+1]) of [U.sub.m+1]. [V.sub.PLA]([U.sub.m+1]) is the possible area of the unknown node [U.sub.m+1]. VPLC([U.sub.m+1]) is the possible circle of the unknown node [U.sub.m+1]; its radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and its center is [O.sub.m+1].

Figure2 shows [V.sub.PCC]([U.sub.m+1]) and [V.sub.ICC]([U.sub.m+1]) of [U.sub.m+1]. [V.sub.PCC]([U.sub.m+1]) is the possible communication circle of the unknown node [U.sub.m+1]; the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the inevitable communication circle of the unknown node [U.sub.m+1];the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Figure 3 shows [V.sub.VCC](d,s). [V.sub.VCC](d,s) is the virtual communication circle of node s relative to node d. If the path with minimum hop-count from the source node s to the destination node d passes through nodes p and p + 1, then the radius of the circle is equal to the sum of those nodes' maximum communication radii. And, O is the center of [V.sub.VCC](d,s).

3.2. Assumptions

Assumption 1. Every anchor node knows its own standard communication radius: the maximum communication radius and the minimum communication radius.

Assumption 2. No auxiliary devices in the wireless sensor network.

Assumption 3. Every node can find its neighbors by utilizing the neighbor discovery algorithm [15,16].

4. Algorithm Description

In NPLA, every unknown node synthesizes the position information and hop-count of its all neighbors to itself, which includes not only anchor neighbors but also unknown neighbors, to determine its estimated position. In detail, every unknown node utilizes its neighbors' virtual communication circles relative to itself and the inevitable communication circles of its neighbors to narrow its own PLA. After traversing all anchor neighbors in the network, every unknown node also traverses all its unknown neighbors to help it to locate itself. When the value of the unknown node's PLA will not change, then the unknown node computes the gravity center of its present PLA as its estimated position.

The concrete method includes the following steps.

Step 1. Unknown node [U.sub.j] puts the network area Q as the initial PLA.

Step 2. Unknown node [U.sub.j] finds all its anchor neighbors in the network by utilizing neighbor discovery algorithm. And, it collects the position information of its anchor neighbors as well as hop-count information between its anchor neighbors and itself.

Step 3. Unknown node [U.sub.j] traverses all its anchor neighbors in the ascending order of hop-count which is from its anchor neighbor to itself. Above all, unknown node [U.sub.j] calculates [V.sub.VCC]([U.sub.j], [A.sub.s]) (the virtual communication circle of anchor neighbor As relative to node [U.sub.j]. If the hop-count from a anchor neighbor to unknown node [U.sub.j] is 1, the virtual communication circle of this anchor neighbor relative to node [U.sub.j] is the possible communication circle of this anchor neighbor). There are two situations of position between circle [V.sub.VCC]([U.sub.j], [A.sub.s]) and PLA of node [U.sub.j]: the circle [V.sub.VCC]([U.sub.j], [A.sub.s]) passes through PLA of node [U.sub.j]; the circle [U.sub.VCC]([U.sub.j], [A.sub.s]) contains PLA of node [U.sub.j]. The descriptions of these two situations are shown as follows.

(1) The circle [V.sub.VCC]([U.sub.j], [U.sub.t]) passes through the PLA of node [U.sub.j]: firstly, the algorithm finds all the vertexes of [U.sub.j]'s present PLA which locates outside the circle [V.sub.VCC]([U.sub.j], [A.sub.s]) and then links every found vertex to the GPS positional coordinates of anchor neighbor [A.sub.s] to get a line, respectively. There is a point of intersection between every line and the circle [V.sub.VCC]([U.sub.j], [A.sub.s]). Secondly, draw a tangent of the circle [V.sub.VCC]([U.sub.j], [A.sub.s]) through every intersection point, respectively. Every tangent cuts node [U.sub.j]'s present PLA to two parts. Lastly, put every tangent as a dividing line to eliminate the region of [U.sub.j]'s present PLA, which is away from the circle [U.sub.VCC]([U.sub.j], [A.sub.s]), respectively. The remaining part is the new PLA of node [U.sub.j].

(2) The circle [U.sub.VCC]([U.sub.j], [A.sub.s]) contains the present PLA of node [U.sub.j]: [U.sub.j] keeps its present PLA unchanged.

Step 4. Unknown node [U.sub.j] traverses all its anchor neighbors in the ascending order of hop-count which is from its anchor neighbor to itself. Here, hop-count is bigger than 1. Above all, unknown node [U.sub.j] determines its present PLC and [V.sub.ICC]([A.sub.k]) (the inevitable communication circle of anchor neighbor [A.sub.k]). There are two situations of position between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([A.sub.k]): there is an intersection between node [U.sub.j]'s present PLC and circle UICC(Ak); there is no intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC] ([A.sub.k]). The descriptions of these two situations are shown as follows.

(1) There is an intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([A.sub.k]): in this case, there must be two intersection points between node [U.sub.j]'s present PLC and the circle [V.sub.ICC]([A.sub.k]). Firstly, the algorithm links these two points of intersection to get a line, and the line cuts node [U.sub.j]'s present PLA into two parts. Lastly, put the line as a dividing line to eliminate the region of [U.sub.j]'s present PLA close to the circle [V.sub.ICC]([A.sub.k]). The remaining part is the new PLA of node [U.sub.j].

(2) There is no intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([A.sub.k]): [U.sub.j] keeps its present PLA unchanged.

Step 5. Every unknown node executes Step 2 to Step 4 to get a new PLA. Unknown node [U.sub.j] finds all its unknown neighbors in the network utilizing neighbor discovery algorithm and gets the position as well as hop-count information of its unknown neighbors to itself.

Step 6. Unknown node [U.sub.j] traverses all its unknown neighbors in the ascending order of hop-count which is from its anchor neighbor to itself. Above all, unknown node [U.sub.j] determines the present [V.sub.VCC]([U.sub.j], [U.sub.t]) (the virtual communication circle of unknown neighbor Ut relative to node Up, if the hop-count which is from an unknown neighbor to unknown node [U.sub.j] is 1, the virtual communication circle of this unknown neighbor relative to node [U.sub.j] is the possible communication circle of this unknown neighbor). There are two situations of position between circle [V.sub.VCC]([U.sub.j], [U.sub.t]) and unknown node [U.sub.j]'s present PLA: the circle [V.sub.VCC]([U.sub.j], [U.sub.t]) passes through unknown node [U.sub.j]'s present PLA; the circle [V.sub.VCC]([U.sub.j], [U.sub.t]) contains unknown node [U.sub.j]'s present PLA. The descriptions of these two situations are shown as follows.

(1) The circle [V.sub.VCC]([U.sub.j], [U.sub.t]) passes through unknown node [U.sub.j]'s present PLA: firstly, the algorithm finds all the vertexes of node [U.sub.j]'s present PLA outside the circle [V.sub.VCC]([U.sub.j], [U.sub.t]) and then links every found vertex to the center of the unknown neighbor [U.sub.t]'s present PLC to get a line, respectively. There is an intersection point between every line and the circle [V.sub.VCC]([U.sub.j], [U.sub.t]). Secondly, draw a tangent of the circle [V.sub.VCC]([U.sub.j],[U.sub.t]) through every intersection point, respectively. Every tangent cuts node [U.sub.j]'s present PLA into two parts. Lastly, put every tangent as a dividing line to eliminate the region of [U.sub.j]'s present PLA, which is away from the circle [V.sub.VCC] ([U.sub.j], [U.sub.t]), respectively. The remaining part is the new PLA of node [U.sub.j].

(2) The circle [V.sub.VCC] ([U.sub.j], [U.sub.t]) contains present PLA of node [U.sub.j]: [U.sub.j] keeps its present PLA unchanged.

Step 7. Unknown node [U.sub.j] traverses all its unknown neighbors in the ascending order of hop-count which is from its unknown neighbors to itself. Here, hop-count is bigger than 1. Above all, unknown node [U.sub.j] determines its present PLC and [V.sub.ICC]([U.sub.p]) (the inevitable communication circle of unknown neighbor Up). There are two situations of position between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([U.sub.p]): there is an intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([U.sub.p]); there is no intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([U.sub.p]). The descriptions of these two situations are shown as follows.

(1) There is an intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([U.sub.p]): in this case, there must be two intersection points between node [U.sub.j]'s present PLC and the circle [V.sub.ICC]([U.sub.p]). Firstly, the algorithm links these two intersection points to get a line, and the line cuts node [U.sub.j]'s present PLA into two parts. Lastly, put this line as a dividing line to eliminate the region of [U.sub.j]'s present PLA close to the circle [V.sub.ICC]([U.sub.p]). The remaining part is the new PLA of node [U.sub.j].

(2) There is no intersection between node [U.sub.j]'s present PLC and circle [V.sub.ICC]([U.sub.p]): [U.sub.j] keeps its present PLA unchanged.

Step 8. Unknown node [U.sub.j] executes Step 2 to Step 7 iteratively until its present PLA is not changed. Then the unknown node [U.sub.j] gets a final PLA. [U.sub.j] computes the gravity center of its final PLA to obtain its estimated position. Similarly, every unknown node in the network executes the same operation as node [U.sub.j] does to obtain an estimated position.

Pseudocode of algorithm NPLA is shown in Pseudocode 1.

PSEUDOCODE 1: Pseudocode of algorithm NPLA. (1) for (j = m + 1; j [less than or equal to] n; j++) (2) do [V.sub.PLA]([U.sub.j]) [less than or equal to] [OMEGA] ([OMEGA]: the area of whole network) (3) Find each [A.sub.s] who is a h-hop anchor neighbor of [U.sub.j] (4) The maximum hop found is [h.sub.m] (5) Phase 1: [U.sub.j] eliminates PLA by utilizing [V.sub.VCC] ([U.sub.j], [A.sub.s]) (6) Phase 2: [U.sub.j] eliminates PLA by utilizing [V.sub.ICC]([A.sub.s]) (7) do Find each [U.sub.t] who is an l-hop unknown neighbor (8) node of [U.sub.j] (9) The maximum hop found is [l.sub.m] (10) Phase 3: [U.sub.j] eliminates PLA by utilizing [V.sub.VCC] ([U.sub.j], [U.sub.t]) (11) Phase 4: [U.sub.j] eliminates PLA by utilizing [V.sub.ICC] ([U.sub.t]) Phase 1: [U.sub.j] eliminates PLA by utilizing [V.sub.VCC]([U.sub.j], As) (1) for (h = 1; h [less than or equal to] [h.sub.m]; h++) (2) { (3) for (s = 1; s [less than or equal to] m; s++) (4) { (5) Draw [V.sub.VCC] ([U.sub.j], [A.sub.s]) (6) if [V.sub.VCC] ([U.sub.j], [A.sub.s]) passes through [V.sub.PLA]([U.sub.j]) (7) then [U.sub.j] eliminates the part of present [V.sub.PLA]([U.sub.j]), (8) which is away from [V.sub.VCC]([U.sub.j], [A.sub.s]) (9) if [V.sub.VCC] ([U.sub.j], [A.sub.s]) contains [V.sub.PLA]([U.sub.j]) (10) then [U.sub.j] keeps present [V.sub.PLA]([U.sub.j]) (11) } (12) } Phase 2: [U.sub.j] eliminates PLA by utilizing [V.sub.ICC]([A.sub.s]) (1) for (h = 2; h [less than or equal to] [h.sub.m]; h++) (2) { (3) for (s = 1; s [less than or equal to] m; s++) (4) { (5) Draw [V.sub.ICC] ([A.sub.s]) (6) if there is a intersection between [V.sub.PLC]([U.sub.j]) and [V.sub.ICC]([A.sub.s]) (7) then [U.sub.j] eliminates the part of present [V.sub.PLA] ([U.sub.j]), (8) which is close to [V.sub.ICC]([A.sub.s]) (9) if [V.sub.ICC] ([A.sub.s]) contains [V.sub.PLA]([U.sub.j]) (10) if there is not a intersection between VPLC(Uj) and [V.sub.ICC](As) (11) } (12) } Phase 3: [U.sub.j] eliminates PLA by utilizing [V.sub.VCC] ([U.sub.j], [U.sub.t]) (1) for (l = 1; l [less than or equal to] [l.sub.m]; l++) (2) { (3) for (t = m + 1; t [less than or equal to] n; t++) (4) { (5) Draw [V.sub.VCC] ([U.sub.j],[U.sub.t]) (6) if [V.sub.VOC] ([U.sub.j], [A.sub.s]) passes through [V.sub.PLA] ([U.sub.j]) (7) then [U.sub.j] eliminates the part of present [V.sub.PLA]([U.sub.j]), (8) which is away from [V.sub.VCC]([U.sub.j],[U.sub.t]) (9) if [V.sub.VCC] ([U.sub.j], [A.sub.s]) contains [V.sub.PLA] ([U.sub.j]) (10) then [U.sub.1] keeps present [V.sub.PLA](Uj) (11) } (12) } Phase 4: [U.sub.j] eliminates PLA by utilizing [V.sub.ICC]([U.sub.t]) (1) for (1 = 2; l [less than or equal to] [l.sub.m], l++) (2) { (3) for (t = m + 1; t [less than or equal to] n; t++) (4) { (5) Draw [V.sub.ICC]([U.sub.t]) (6) if there is a intersection between [V.sub.PLC]([U.sub.j]) and [V.sub.ICC]([U.sub.t]) (7) then [U.sub.j] eliminates the part of present [V.sub.PLA]([U.sub.j]), (8) which is close to [V.sub.ICC]([U.sub.t]) (9) if [V.sub.ICC]([U.sub.t]) contains [V.sub.PLA] ([U.sub.j]) (10) if there is not a intersection between [V.sub.PLC]([U.sup.j]) and [V.sub.ICC]([U.sub.t]) (11) } (12) }

5. Algorithm Implementation

Now we show the specific algorithm steps for unknown node [U.sub.m+1] to explain how the algorithm NPLA is implemented.

Step 1. Unknown node [U.sub.m+1] puts the network area [OMEGA] as its initial PLA.

Step 2. Unknown node [U.sub.m+1] finds all its anchor neighbors in the network utilizing neighbor discovery algorithm and gets the position information and hop-count (hop-count is less than 3) to itself. Three anchor neighbors are found: [A.sub.1]; [A.sub.2], and [A.sub.3]; [A.sub.1] is the 1 hop anchor neighbor of unknown node [U.sub.m+1]; [A.sub.2] and [A.sub.3] are 2 hop anchor neighbors of unknown node [U.sub.m+1].

Step 3. Unknown node [U.sub.m+1] traverses all its anchor neighbors in the ascending order of hop-count which is from its anchor neighbor to itself.

Step 3.1. Unknown node [U.sub.m+1] uses the [V.sub.PCC]([A.sub.1]) of anchor node [A.sub.1] ([V.sub.VCC]([U.sub.m+1], [A.sub.1])), as shown in Figure 4(a).

(1) Draw the circle [V.sub.PCC]([A.sub.1]) of anchor node [A.sub.1].

(2) Find all the vertexes of [U.sub.m+1] 's present PLA outside the circle [V.sub.PCC]([A.sub.1]) and obtain four vertexes: V1, V2, V3, and V4. Then, link anchor node [A.sub.1]'s GPS coordinate position to every vertex to get a line, respectively. Then there are four points of intersection between these four lines and circle [V.sub.PCC]([A.sub.1]): P1, P2, P3, and P4.

(3) Draw the tangent of circle [V.sub.PCC]([A.sub.1]) through P1, P2, P3, and P4, respectively

(4) Every tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts. Then put every tangent as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA away from the circle [V.sub.PCC](Ax), respectively. The remaining part (convex polygon ABCD) is the new PLA of [U.sub.m+1].

Step 3.2. Unknown node [U.sub.m+1] uses the [V.sub.VCC]([U.sub.m+1], [A.sub.2]) of anchor node [A.sub.2], as shown in Figure 4(b).

(1) Draw the circle [V.sub.VCC]([U.sub.m+1], [A.sup.2]).

(2) Find all the vertexes of [U.sub.m+1]'s present PLA outside the circle [V.sub.VCC]([U.sub.m+1], [A.sup.2]) and obtain three vertexes: B, A, and D. Then link anchor node [A.sub.2]'s GPS coordinate position to every vertex to get a line, respectively. Then there are three points of intersection between these three lines and circle [V.sub.VCC]([U.sub.m+1], [A.sub.2]): Q1, Q2, and Q3.

(3) Draw the tangent of circle [V.sub.VCC]([U.sub.m+1], [A.sub.2]) through Q1, Q2, and Q3, respectively

(4) Every tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts. Then put every tangent as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA which is away from the circle [V.sub.VCC]([U.sub.m+1], [A.sub.2]), respectively. The remaining part (convex polygon CEFGH) is the new PLA of [U.sub.m+1].

Step 3.3. Unknown node [U.sub.m+1] uses the [V.sub.VCC]([U.sub.m+1], [A.sub.3]) of anchor node [A.sub.3], as shown in Figure 4(c).

(1) Draw the circle [V.sub.VCC]([U.sub.m+1], [A.sub.3]).

(2) Find all the vertexes of [U.sub.m+1]'s present PLA outside the circle [V.sub.VCC]([U.sub.m+1], [A.sub.3]) and obtain two vertexes: H and G. Then link anchor node [A.sub.2]'s GPS coordinate position to every vertex to get a line, respectively. Then there are two points of intersection between these two lines and circle [V.sub.VCC]([U.sub.m+1], Q3.

(3) Draw the tangent of circle [V.sub.VCC]([U.sub.m+1], [A.sub.2]) through the two points of intersection in (2), respectively.

(4) Every tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts. Then put every tangent as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA which is away from the circle [V.sub.VCC]([U.sub.m+1], [A.sub.3]), respectively. The remaining part (convex polygon CEFIJ) is the new PLA of [U.sub.m+1].

Step 4. Unknown node [U.sub.m+1] traverses all its anchor neighbors in the ascending order of hop-count which is from its anchor neighbor to itself. Here, hop-count is bigger than 1.

Step 4.1. Unknown node [U.sub.m+1] uses the [V.sub.ICC]([A.sub.2]) of anchor node [A.sub.3], as shown in Figure 5.

(1) Draw [U.sub.m+1] 's present PLC and the circle [V.sub.ICC]([A.sub.2]).

(2) There are two points of intersection between [U.sub.m+1]'s present PLC and the circle [V.sub.ICC]([A.sub.2]): T and S. Link T to S to get a line.

(3) The line in (2) cuts [U.sub.m+1]'s present PLA into two parts. Then put the line as a dividing line to eliminate the region of [U.sub.m+1] 's present PLA closing to the circle [V.sub.ICC]([A.sub.2]). The remaining part (convex polygon EFIKL) is the new PLA of [U.sub.m+1].

Step 4.2. Unknown node [U.sub.m+1] uses the [V.sub.ICC]([A.sub.3]) of anchor node [A.sub.3], as shown in Figure 6.

(1) Draw [U.sub.m+1]'s present PLC and the circle [V.sub.ICC]([A.sub.3]).

(2) There are two points of intersection between [U.sub.m+1]'s present PLC and the circle [V.sub.ICC]([A.sub.3]): X and Y. Link X to Y to get a line.

(3) The line in (2) cuts [U.sub.m+1]'s present PLA into two parts. Then put the line as a dividing line to eliminate the region of [U.sub.m+1] 's present PLA closing to the circle [V.sub.ICC]([A.sub.3]). The remaining part (convex polygon FIKMN) is the new PLA of [U.sub.m+1].

Step 5. Every unknown node [U.sub.j] (m + 1 [less than or equal to] j [less than or equal to] n) executes Step 2 to Step 4 to get a new PLA. Unknown node [U.sub.m+1] finds all its unknown neighbors in the network utilizing neighbor discovery algorithm and gets the position information and hop-count (hop-count is less than 3) to itself. Three unknown neighbors are found: [U.sub.m+2], [U.sub.m+3], and [U.sub.m+4]; [U.sub.m+2] is the 1 hop unknown neighbor of unknown node [U.sub.m+1] and [U.sub.m+3] and [U.sub.m+4] are 2 hop unknown neighbors of unknown node [U.sub.m+1].

Step 6. Unknown node [U.sub.m+1] traverses all its unknown neighbors in the ascending order of hop-count which is from its unknown neighbor to itself.

Step 6.1. Unknown node [U.sub.m+1] uses the [V.sub.PCC]([U.sub.m+2]) of unknown node [U.sub.m+2] ([V.sub.VCC]([U.sub.m+1], [U.sub.m+2])), as shown in Figure 7.

(1) Draw the circle [V.sub.PCC] ([U.sub.m+2]).

(2) Find all the vertexes of [U.sub.m+1]'s present PLA outside the circle [V.sub.PCC]([U.sub.m+2]) and obtain one vertex: K. Then link [U.sub.m+2] to vertex K to get a line. Then there is one intersection point between the line and circle [V.sub.PCC]([U.sub.m+2]).

(3) Draw the tangent of circle [V.sub.PCC]([U.sub.m+2]) through the point of intersection in (2).

(4) The tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts. Then put this tangent as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA which is away from the circle [V.sub.PCC]([U.sub.m+2]). The remaining part (convex polygon FIOPMN) is the new PLA of [U.sub.m+1].

Step 6.2. Unknown node [U.sub.m+1] uses the [V.sub.VCC] ([U.sub.m+1], [U.sub.m+3]) of unknown node [U.sub.m+3], as shown in Figure 8.

(1) Draw the circle [V.sub.VCC]([U.sub.m+1],[U.sub.m+3]).

(2) Find all the vertexes of [U.sub.m+1] 's present PLA outside the circle [V.sub.VCC] ([U.sub.m+1], [U.sub.m+3]) and obtain one vertex: N. Then link [O.sub.m+3] to vertex N to get a line. Then there is one point of intersection between the line and circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+3]).

(3) Draw the tangent of circle [V.sub.VCC] ([U.sub.m+1], [U.sub.m+3]) through the point of intersection in (2).

(4) The tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts. Then put this tangent as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA which is away from the circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+3]). The remaining part (convex polygon FIOPMQR) is the new PLA of [U.sub.m+1].

Step 6.3. Unknown node [U.sub.m+1] uses the [V.sub.VCC]([U.sub.m+1], [U.sub.m+4]) of unknown node [U.sub.m+4], as shown in Figure 9.

(1) Draw the circle [V.sub.VCC] ([U.sub.m+1]>[U.sub.m+4]).

(2) Find all the vertexes of [U.sub.m+1]'s present PLA outside the circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+4]) and obtain two vertexes: M and P. Then link [O.sub.m+4] to every vertex to get a line, respectively. Then there are two points of intersection between these two lines and circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+4]).

(3) Draw the tangent of circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+4]) through two points of intersection in (2), respectively.

(4) The tangent in (3) cuts [U.sub.m+1]'s present PLA into two parts, respectively. Then put every tangent as a dividing line to eliminate the region of [U.sub.m+1] 's present PLA which is away from the circle [V.sub.VCC]([U.sub.m+1], [U.sub.m+4]). The remaining part (convex polygon FIOPMQR) is the new PLA of [U.sub.m+1].

Step 7. Unknown node [U.sub.m+1] traverses all its unknown neighbors in the ascending order of hop-count which is from its unknown neighbors to itself. Here, hop-count is bigger than 1.

Step 7.1. Unknown node [U.sub.m+1] uses the [V.sub.ICC]([U.sub.m+3]) of unknown node [U.sub.m+3], as shown in Figure 10.

(1) Draw Hm+1's present PLC and the circle [V.sub.ICC]([U.sub.m+3]).

(2) There are two points of intersection between Hm+1's present PLC and the circle [V.sub.ICC]([U.sub.m+3]). Linkthese two points to get a line.

(3) The line in (2) cuts [U.sub.m+1]'s present PLA into two parts. Then put the line as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA closing to the circle [V.sub.ICC]([U.sub.m+3]). The remaining part (convex polygon FVWTUQR) is the new PLA of [U.sub.m+1].

Step 7.2. Unknown node [U.sub.m+1] uses the [V.sub.ICC]([U.sub.m+4]) of unknown node [U.sub.m+4], as shown in Figure 11.

(1) Draw Hm+1's present PLC and the circle [V.sub.ICC]([U.sub.m+4]).

(2) There are two points of intersection between [H.sub.m+1]'s present PLC and the circle [V.sub.ICC]([U.sub.m+4]). Link these two points to get a line.

(3) The line in (2) cuts [U.sub.m+1]'s present PLA into two parts. Then put the line as a dividing line to eliminate the region of [U.sub.m+1]'s present PLA closing to the circle [V.sub.ICC]([U.sub.m+4]). The remaining part (convex polygon WTUQRXY) is the new PLA of [U.sub.m+1].

Step 8. Unknown node [U.sub.m+1] executes Step 2 to Step 7 iteratively until its present PLA does not change. Unknown node [U.sub.m+1] can get a final PLA. Then [U.sub.m+1] computes the gravity center of its final PLA as its estimated position.

6. Simulation and Evaluation

This section describes the simulation parameters and model we use in our evaluation and then provides a detailed quantitative analysis by comparing the performance of our method with other range-free localization algorithms like DV-HOP [9], APIT [12], and SOM [14]. When evaluating localization schemes, the most important parameters of comparison are localization error, [r.sub.MAX], and P. We use several influence factors to simulate the experiments: (1) anchor node degree, (2) unknown node degree, (3) degree of irregularity (DOI), and (4) GPS error.

6.1. Simulation Placement. Anchor nodes and unknown nodes are distributed in a 1000 * 1000 [m.sup.2] square in our simulations. There are 50 anchor nodes and 620 unknown nodes in the default setting. In order to simplify the computation, average radio radius of each node is assumed to be 100 m. Each simulation experiment tests 20 times to improve computational accuracy. Also, in order to simulate the realistic scenario, we take the degree of irregularity (DOI) and GPS error into consideration.

6.2. Simulation Parameters

6.2.1. Basic Parameters

(1) Anchor node degree (AD) is the average number of anchor nodes per unit circle.

(2) Unknown node degree (UD) is the average number of unknown nodes per unit circle.

(3) Degree of irregularity (DOI) is the maximum radio range variation per unit degree change in the direction of radio propagation. There are upper bound and lower bound of the communication radius. Consider

DOI = [R.sub.max] - [R.sub.min]/ [R.sub.max] x 100%. (1)

(4) GPS error is the position error of the anchor node localized by GPS.

6.2.2. Performance Parameters

(1) Localization error (LE) is as follows:

[L.sub.E] = 1 [[SIGMA].sup.n.sub.i=1][absolute value of [Y.sub.i] - [X.sub.i]/R] x 100%, (2)

where [Y.sub.i] is the estimated coordinate of unknown node (i) and [X.sub.i] is real coordinate of i. The number of unknown nodes is n. [R.sub.i] is i's radio radius. In our simulation test, we not only calculate localization error of localized unknown nodes but also calculate average error of unlocated nodes, which is why the performance of APIT in our paper is different from paper [8].

(2) [r.sub.MAX] is the radius of possible location circle of unknown node.

(3) P is the product of [r.sub.MAX] and the area of the final PLA of the unknown node. For some algorithms, even though the location area of unknown node is small, the localization error may be bigger. So, it is difficult to test the true performance of those algorithms by other parameters. But the performance of algorithm can be evaluated accurately by considering [r.sub.MAX] and the area of the final PLA.

All distances including error estimation are normalized to units of node radio range (R) to ensure the generally applicable results in our evaluation. When evaluating localization schemes, the most important measurements for comparison are localization error, [r.sub.MAX], and P. In our simulation, we take several influence factors into consideration: (1) anchor node degree, (2) unknown node degree, (3) degree of irregularity (DOI), and (4) GPS error.

The final estimated position of both DV-Hop and SOM are points, so the data do not have [r.sub.MAX] and P. The [r.sub.MAX] and P of APIT and NPLA are shown in the following simulation figures: Figures 12(b)-12(c), Figures 13(b)-13(c), Figures 14(b)14(c), and Figures 15(b)-15(c).

6.3. Localization Error, [r.sub.MAX], and P versus AD. We analyze the effect of varying the average numbers of anchor node per unit circle in experiment.

It is found that the localization error decreases as anchor nodes degree increase in Figure 12(a). The reason is that when AD increases, the numbers of anchor nodes increase in the wireless network, so the localization accuracy could be improved inevitably. APIT utilizes the anchor nodes to constitute the triangle. If the density of the anchor node is too low, the number of triangles is less, so the localization result is not so satisfied. NPLA algorithm performs better than APIT on this occasion, which is because NPLA not only uses the communication range of anchor nodes but also utilizes the PLA of the unknown node. As shown in Figure 12(b), the [r.sub.MAX] of NPLA is lower, and it changes slightly when AD increases. The final localization area is a prolate polygon due to the algorithm feature in APIT, so rMAX and P of APIT are bigger.

6.4. Localization Error, [r.sub.MAX], and P versus UD. We research the impact of UD on the precision of localization estimation and other performance in this experiment. The localization error of both APIT and NPLA decreases slightly as UD increases as shown in Figure 13(a), but the localization error of APIT is larger. Because APIT did not utilize unknown nodes to assist in reducing the PLA of unknown node in its design, both [r.sub.MAX] and P of APIT are not be affected as shown in Figures 13(b) and 13(c). However, when UD increases, NPLA has more information of unknown neighbors to utilize. So the localization error of NPLA is smaller than others. The [r.sub.MAX] and P of NPLA decrease as UD increases.

6.5. Localization Error, [r.sub.MAX], and P versus GPS Error. In real environment, the error located by GPS of anchor nodes cannot be ignored; we take the GPS error into consideration in our simulation. The first step of NPLA algorithm is utilizing the information of anchor neighbors to eliminate the PLA. When the position deviation of anchor node's increases, the localization error will increase accordingly as shown in Figure 14(a); also, the [r.sub.MAX] has a rapid change in the same condition as shown in Figure 14(b). Because the shape of the polygon is affected by the communication range of anchor nodes when eliminating the PLA of unknown nodes, the [r.sub.MAX] of NPLA increases as shown in Figure 14(b). But the area of final PLA in NPLA is still small, so the P of NPLA keeps low. In APIT, when GPS error increases, the inaccuracy of nodes' coordinate position will increase and then lead to the deviation of triangle in APIT. So the localization error, [r.sub.MAX], and P are the biggest in all algorithms.

6.6. Localization Error, [r.sub.MAX], and P versus DOI. We also consider the effect of degree of irregularity (DOI) to the performance of the algorithm.

According to the definition of DOI, when DOI increases, the real communication range of node is more uncertain. So the localization error of algorithms which use communication range to locate unknown nodes such as DV-Hop and NPLA is affected obviously. The localization error, [r.sub.MAX], and P in all algorithms increase as DOI increases as we can see in Figures 15(a), 15(b), and 15(c). NPLA utilizes hop-count information only to eliminate unknown node's PLA rather than measure the distance. And it depends on not only hop-count information but also other information to locate unknown nodes, so the performance in NPLA is better than other algorithms.

6.7. Evaluation Discussion. From the comparison above, NPLA performs better than others. To reduce the computational complexity, NPLA, which is a distributed algorithm, just uses unknown node's neighbors within three-hop. And NPLA keeps the PLA of an unknown node as a convex polygon in every step to further reduce the computation overhead. In general, the energy consumption of NPLA is less than most of other algorithms.

7. Conclusion

In this paper, we proposed a novel eliminating method NPLA for unknown nodes, which narrows the possible location area (PLA) of unknown node by utilizing the VCCs and ICCs of its anchor neighbors and unknown neighbors. Even though there are only few anchor nodes in the wireless network, NPLA can still get better localization accuracy. Taking GPS error and DOI into account, the localization error is still acceptable.

Abbreviations [OMEGA]: The whole network area [A.sub.i]: The anchor node, 1 [less than or equal to] i [less than or equal to] m, represents node whose position is known already [U.sub.j]: The unknown node, m + 1 [less than or equal to] j [less than or equal to] n, represents node whose position is unknown R: The standard communication radius of the node [e.sub.g]: The relative error of anchor's coordinate position measured by GPS [Re.sub.g]: The absolute error of anchor's coordinate position measured by GPS [R.sup.k.sub.max]: The maximum communication radius of the node k (1 [less than or equal to] k [less than or equal to] n) [R.sup.k.sub.min]: The minimal communication radius of the node k (1 [less than or equal to] k [less than or equal to] n) [O.sub.i]: The coordinate position of anchor node measured by GPS k (1 [less than or equal to] i [less than or equal to] m) [V.sub.PLA]([A.sub.k]): The possible location area of anchor node: center is [O.sub.i] and radius is [Re.sub.g] [V.sub.PLA]([U.sub.k]): The possible location area of unknown node: a convex polygon [V.sub.PLC]([U.sub.j]): The possible location circle of unknown node: the minimum circle that contains all vertexes of [V.sub.PLA]([U.sub.k]) of the unknown node (the thin circle) [O.sub.j]: The center of [V.sub.PLC]([U.sub.j])k (m + 1 [less than or equal to] j [less than or equal to] n) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: The radius of possible location circle of unknown node [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: The radius of possible communication circle of anchor node: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: The radius of possible communication circle of unknown node: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: The radius of inevitable communication circle of anchor node: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: The radius of inevitable communication circle of unknown node: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [V.sub.PCC]([A.sub.k]): The possible communication circle of anchor node: the center is [O.sub.i] and the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [V.sub.PCC]([U.sub.k]): The possible communication circle of unknown node: the center is [O.sub.j] and the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [V.sub.ICC]([A.sub.k]): The inevitable communication circle of anchor node: the center is [O.sub.j] and the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [V.sub.ICC]([U.sub.k]): The inevitable communication circle of unknown node: the center is [O.sub.j] and the radius is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] {[N.sub.d,s]}: The unknown node set through the path from source node s to destination node d with the least hops, except node s and node d. Here, d is unknown node and s is anchor or unknown node [R.sup.(d,s).sub.VCC]: The radius of the virtual communication circle of node s relative to node d. Conner [R.sup.(d,s).sub.JCC] = [R.sup.S.sub.PCC] + [SIGMA] [R.sup.k.sub.max] (k [member of] {[N.sub.d,s]}) [V.sub.VCC] (d,s): The virtual communication circle of node s relative to node d; the radius is [R.sup.(d,s).sub.VCC]. When s is anchor node, the center is [O.sub.i]. When s is unknown node, the center is [O.sub.j].

http://dx.doi.org/10.1155/2014/257507

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This research is supported partly by China NSF 61373091, 61202478, 6093301, 11102124, and 71102113 and the US NSF Grant CNS-0917097.

References

[1] X. Cheng, H. Shu, Q. Liang, and D. H.-C. Du, "Silent positioning in underwater acoustic sensor networks," IEEE Transactions on Vehicular Technology, vol. 57, no. 3, pp. 1756-1766, 2008.

[2] X. Cheng, A. Thaeler, G. Xue, and D. Chen, "TPS: a time-based positioning scheme for outdoor wireless sensor networks," in Proceedings of the 23rd AnnualJoint Conference of the IEEE Computer and Communications Societies, pp. 2685-2696, Hong Kong, March 2004.

[3] G. J. Pottie and W. J. Kaiser, "Wireless integrated network sensors," Communications of the ACM, vol. 43, no. 5, pp. 51-58, 2000.

[4] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, "The cricket location-support system," in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom 00), pp. 32-43, August 2000.

[5] A. Savvides, C.-C. Han, and M. B. Strivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors," in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom 01), pp. 166-179, July 2001.

[6] J. Hightower and G. Borriello, "A survey and taxonomy of location systems for ubiquitous computing," IEEE Computer, vol. 34, no. 8, pp. 57-66, 2001.

[7] Y. Geng, J. He, H. Deng, and K. Pahlavan, "Modeling the effect of human body on TOA ranging for indoor human tracking with wrist mounted sensor," in Proceedings of the 16th IEEE International Symposium on Wireless Personal Multimedia Communications (WPMC '13), pp. 1-6, Atlantic City, NJ, USA, June 2013.

[8] Y. Geng, J. Chen, and K. Pahlavan, "Motion detection using RF signals for the first responder in emergency operations: a PHASER project," in Proceedings of the IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC '13), pp. 358-364, London, UK, September 2013.

[9] D. Niculescu and B. Nath, "DV based positioning in ad hoc networks," Telecommunication Systems, vol. 22, no. 1-4, pp. 267-280, 2003.

[10] R. Nagpal, H. Shrobe, and J. Bachrach, "Organizaing a global coordirate systerm from local information on an ad hoc sensor network," in Information Processing in Sensor Networks: Proceedings of the 2nd International Workshop, IPSN 2003, Palo Alto, CA, USA, April 22-23, 2003 , vol. 2634 of Lecture Notes in Computer Science, pp. 333-348, Springer, Berlin, Germany, 2003.

[11] S. N. Simic and S. Sastry, "Distributed localization in wireless ad hoc networks," Tech. Rep., 2001.

[12] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher, "Range-free localization schemes for large scale sensor networks," in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03), pp. 81-95, San Diego, Calif, USA, September 2003.

[13] J.-P. Sheu, P.-C. Chen, and C.-S. Hsu, "A distributed localization scheme for wireless sensor networks with improved grid-scan and vector-based refinement," IEEE Transactions on Mobile Computing, vol. 7, no. 9, pp. 1110-1123, 2008.

[14] G. Giorgetti, S. K. S. Gupta, and G. Manes, "Wireless localization using self-organizing maps," in Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN '07), pp. 293-302, Cambridge, Mass, USA, April 2007.

[15] L. Chen, Y. Gu, S. Guo et al., "Group-based discovery in low-duty-cycle mobile sensor networks," in Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '12), pp. 542-550, Seoul, Republic of Korea, June 2012.

[16] L. Chen, S. Guo, Y. Shu et al., "Poster: selective reference mechanism for neighbor discovery in low-duty-cycle wireless sensor networks," in Proceedings of the 9th ACM Conference on Embedded Networked Sensor Systems (SenSys '11), pp. 367-368, Washington, DC, USA, November 2011.

Liangyin Chen, (1) Bingshu Yan, (1) Junjun He, (2) Jingyu Zhang, (1) Wen Chen, (1) Yushi Jiang, (3) Yan Liu, (4) Qian Luo, (5) and Baoqiu Wang (6)

(1) College of Computer Science, Sichuan University, Chengdu 610064, China

(2) College of Electrical Information, Sichuan University, Chengdu 610064, China

(3) School of Economic and Management, Southwest Jiaotong University, Chengdu 610041, China

(4) School of Software and Microelectronics, Peking University, Beijing 100871, China

(5) The Second Research Institute of Civil Aviation Administration of China Logistics Technology Branch, Chengdu 610041, China

(6) Department of Computer Science and Engineering, Jinjiang College, Sichuan University, Pengshan 620860, China

Correspondence should be addressed to Liangyin Chen; chenliangyin@gmail.com

Received 24 January 2014; Revised 15 May 2014; Accepted 18 May 2014; Published 12 June 2014

Academic Editor: Ki-Il Kim

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Chen, Liangyin; Yan, Bingshu; He, Junjun; Zhang, Jingyu; Chen, Wen; Jiang, Yushi; Liu, Yan; Luo, Qia |

Publication: | International Journal of Distributed Sensor Networks |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 8703 |

Previous Article: | An energy-efficient collaborative ground vibration measurement scheme based on compressed sensing and belief propagation. |

Next Article: | DFDP: a distributed algorithm for finding disjoint paths in wireless sensor networks with correctness guarantee. |

Topics: |