User:Cx.guo/sandbox

Wireless Sensor Networks have been proposed for a multitude of location-dependent applications. For such systems, the cost and limitations of the hardware on sensing nodes prevent the use of range-based localization schemes that depend on absolute point- to-point distance estimates. APIT is a range-free localization algorithm, which performs well when an irregular radio pattern and random node placement are considered, and low communication overhead is desired.

Algorithm

The theoretical method used to narrow down the possible area in which a target node resides is called the Point-In-Triangulation Test (PIT). In this test, a node chooses three anchors from all audible anchors (anchors from which a beacon was received) and tests whether it is inside the triangle formed by connecting these three anchors. APIT repeats this PIT test with different audible anchor combinations until all combinations are exhausted or the required accuracy is achieved. At this point, APIT calculates the center of gravity (COG) of the intersection of all of the triangles in which a node resides to determine its estimated position.

Pseudocode

The APIT algorithm can be broken down into four steps: 1) Beacon exchange, 2) PIT Testing, 3) APIT aggregation and 4) COG calculation. These steps are performed at individual nodes in a purely distributed fashion. The below is the basic pseudo code for our algorithm: Receive location beacons (Xi,Yi) from N anchors.

   InsideSet = Φ // the set of triangles in which I reside 
   For (each triangle Ti ∈ (3N ) triangles) { 
       If (Point-In-Triangle-Test (Ti) == TRUE) 
           InsideSet = InsideSet ∪ { Ti } 
       If( accuracy(InsideSet) > enough ) break; 
   } 
   /* Center of gravity (COG ) calculation */ 
   Estimated Position = COG ( ∩Ti ∈ InsideSet);

Description

Perfect PIT Test (PIT)

• Propositions I:

If M is inside triangle ∆ABC, when M is shifted in any direction, the new position must be nearer to ( further from) at least one anchor A, B or C. (Figure 1A)

• Proposition II:

If M is outside triangle ∆ABC, when M is shifted, there must exist a direction in which the position of M is further from or closer to all three anchors A, B and C. (Figure 1B)

Figure 1: Propositions I and II

• Perfect P.I.T Test Theory:

If there exists a direction such that a point adjacent to M is further/closer to points A, B, and C simultaneously, then M is outside of ∆ABC. Otherwise, M is inside ∆ABC.

Approximation of the Perfect PIT Test (APIT)

Approximate PIT Test takes advantage of the relatively high node density of these networks (usually with connectivity above 6). The basic idea behind the APIT test is to use neighbor information, exchanged via beaconing, to emulate the node movement in the Perfect PIT test. The APIT test is formally described below.

• Approximate P.I.T Test:

If no neighbor of M is further from/closer to all three anchors A, B and C simultaneously, M assumes that it is inside triangle ∆ABC. Otherwise, M assumes it resides outside this triangle.

We further explain the APIT test through an example. The figure A above presents a scenario where none of M’s neighbors, 1, 2, 3 or 4, is further from/closer to all three anchors A, B and C simultaneously. In this scenario, M will assume that it is inside the triangle ∆ABC according to the definition. The other scenario is shown in The figure B above, where neighbor 3 will report to node M that it is further away from A, B, and C than M. This allows M to assume it resides outside of triangle ∆ABC.

Incorrect Decision of APIT

Because APIT can only evaluate a finite number of directions (the number of neighbors), APIT can make an incorrect decision. The two scenarios where incorrect decisions are made are depicted in the figure below.

Figure 2: Error Scenarios for the APIT Test.

Edge effect: Figure 2A shows what we deem InToOut error, where the node is inside the triangle, but concludes based on the APIT test that it is outside the triangle. This can happen when M is near the edge of the triangle, while some of M’s neighbors (3 in this case) are outside the triangle and further from all points ABC, in relation to node M.

'Regular placement: Figure 2B depicts a scenario where M is outside of triangle ABC and none of its neighbors is further.

APIT Aggregation

Once the individual APIT tests finish, APIT aggregates the results (inside/outside decisions among which some may be incorrect) through a grid SCAN algorithm. In this algorithm, a grid array is used to represent the maximum area in which a node will likely reside. The figure 3 is an example of grid SCAN.

Figure 3: SCAN Approach

For each APIT inside decision (a decision where the APIT test determines the node is inside a particular region) the values of the grid regions over which the corresponding triangle resides are incremented. For an outside decision, the grid area is similarly decremented. Once all triangular regions are computed, the resulting information is used to find the maximum overlapping area (e.g. the grid area with value 2 in the figure above), which is then used to calculate the center of gravity for position estimation. The pseudo code for APIT aggregation is as follows:

   For (each triangle Ti ∈ (3N ) triangles) { 
       If (APIT(Ti) == Out ) AddNegtiveTriangle(Ti); 
       If (APIT(Ti) == In ) AddPositiveTriangle(Ti); 
   };

   Find the area with Max values; 

1. Having received beacons from anchors A, B, and C, each node maintains a table (Anchor ID, Location, Signal Strength) for each anchor heard.

figure 4:Table of heard Anchors

2. Each node beacons once to exchange anchor tables with its neighbors. These tables are merged at every node to maintain neighborhood state.

Figure 5: Combined Anchor Table

3. APIT runs on every column of the node’s table to determine whether a neighboring node exists that has consistently larger/smaller signal strengths from the three anchors A, B 2 and C. If such a neighbor is found, M assumes that it is outside triangle ABC. If no such neighbor is found, M assumes it is inside this region.

4. Each node repeats step 3 for varying combinations of three anchors. (The figure above only demonstrates 1 combination of three anchors in this example).

5. Grid Scan Approach is then used to determine the area with maximum overlap.

6. Finally, the center of gravity of this area is used as the final location estimation.

APIT Performance Analysis

Since APIT requires each anchor and node to broadcast once, if considering a static sensor network with N anchors and M nodes the communication overhead of our APIT algorithm is N+M under collision-free situation. The maximum number of polygons partitioned by these anchors can be achieved by placing all anchors on a convex curve. This anchor placement creates (K-1)(K-2)/2 + K(K-1)(K-2)(K-3)/24 partitions. Assuming the nominal anchor radio range is R, the average size of each partition is then:

πR2/((K −1)(K −2)/2 + K(K −1)(K −2)(K −3)/24)

It only indirectly reflects the upper bound performance of the Perfect PIT test. APIT has less accuracy due to approximation. By using our SCAN algorithm during APIT aggregation, the computational complexity of the APIT algorithm is O(L) (L is the number of APIT tests and each test only requires several comparisons). If using a geometric algorithm to perform APIT aggregation precisely, the computational complexity will be O(L^2).