ABSTRACT

The error will inevitably appear in triangle location in WSNs (wireless sensor networks), and the analysis of its character is very important for a reliable location algorithm. To research the error in triangle location algorithm, firstly, a triangle location model is set up; secondly, the condition of the minimal error is got based on the analysis of the location model; at last, by analyzing the condition, the law of error’s changing is abstracted, and its correctness is validated by some testing. The conclusions in this paper are all proved, and they provide a powerful foundation and support for reliable location algorithm’s research.

1.  Introduction

The information usually binds with the node’s position in pervasive computing [1,2] as approximately 80% information is related with position in this computation [3]. Therefore, the location study becomes an essential topic in pervasive computing [4]. Nowadays, most existing location algorithms [5-7] contain two basic steps: 1) distance (or angle) measurement; 2) location computation.

Currently, the triangle location is a hot research topic [8,9]. Because of the unavoidable location error, the key problem of reliable location is how to decrease the error as much as possible. But many literatures about the triangle location are lack of researches on the change law of location error, and they did not consider the error’s distribution in a triangle. This article draws a conclusion: the error’s change in triangle is stochastic, and the errors in different position are different. If a location algorithm has not considered the error’s changing law, its application scope will be confined or even can not be applied at all. So, the analysis of error is very important for a reliable triangle location algorithm.

2.  Mathematical Model of Location Question

In the three-dimensional space, it can determine the coordinate of a location point according to the distance from the location point to four reference points, and this is the same with the basic principle of global positioning system (GPS) [10]. In pervasive computing, however, the most coordinate systems are two-dimensional space and they also do not need the clock synchronization. Therefore, it can fix on the position of a location point as long as the distance from this location point to three reference points is known. As shown in Figure 1, the basic principle of trilateral location is the solution of three circles’ intersection whose radii and the coordinate of circle center are known.

Due to the limit of pervasive terminal's hardware and energy consumption, the ranging error between nodes is usually biggish. Here, it supposes the ranging error's scope is in (0, ±e) and takes (e>0). So three circles are no longer intersect at a point, but constitute a small region, denoted by C_p. Supposes the coordinate of the point to be located p is (x, y), then it can locate this point and get three reference points denoted by p_i which constitutes the triangle. The coordinate of p_i is respectively (x_i, y_i), i=1, 2, 3, the distance to the location point is r_i, and e_i is the ranging error, makes Cp_i, C_p and S_p:

(1)

(2)

(3)

In order to simplify the analysis, supposes ranging error is equal, namely e_i=e, i=1,2,3, then, when eº0, the set of points C_p in Formula (2) will assemble into one point (e.g. Figure 1); However, when e>0, C_p will be a convex small region, and its area represents location error size, as shown in Figure 2.

In the figure above, supposes lpp_i is a straight line which pasts point p, p_i and intersects the circle S_p in Formula (3) at two points q_ij, j=1, 2. Make tangent lq_ij for Sp pasting q_ij, then the tangent will intersect as arbitrary hexagon like Figure 3, and region Cp_i is between the straight line lq_i1 and lq_i2. Take Cp=Cp₁∩Cp₂∩Cp₃, then the final C_p will be the hexagon abcdef in Figure 3. The area of C_p edge can be linearized as measuring error e is less, and it will be estimated as C_p, namely C_p will approximately be regard as C_p, it may also find in Figure 3 that the C_p region cut by arc is almost the same with hexagon region C_p. Thus, the node location question in the two-dimensional space is transformed into discussing how to arrange three reference points for minimizing the area S (C_p) of region C_p.

3.  Condition of Minimum Location Error

Lemma 1: Supposes a, b, c is three numbers whose value is bigger than 0, then and the equal sign holds only when a=b=c.

Supposes α₁, α₂, α₃ is respectively the angle (central angle) between vector PA and PB, PB and PC, PC and PD. The region constituted by C_p is a circumscribed hexagon of circle S_p as shown in Figure 3, then

(4)

As to α₁, α₂, α₃, it has the following relationship:

when 0£x£π/2, then (tan x)²=2tanx(1+tanx)³0, and we may derive the following expression using Lemma 1:

(5)

Theequality above holds only when α₁ = α₂ = α₃=π/3, namely conclusion 1: S (C_p) can obtain the minimum value only when α₁ = α₂ = α₃.

As α₁ = α₂ = α₃=π/3, it is not difficult to deduce according to the geometry principle that the angle of three linked lines formed by three reference points and a point to be located P is mutually 120°. Therefore, only when the angle of three linked lines formed by three reference points and the point to be located is mutually 120°, error zone C_p can become the circumscribe hexagon of the circle. In this case, the location error of the location point can achieve minimum, and this conclusion is the so-called formation condition of the minimum location error.

As shown in Figure 4,in the triangle which formed by three arbitrary arranged reference points, there is only one error zone of the point to be located presents hexagon at most, and the location error increases along with the distance from this point to point P. For instance, as the location point is S and its error zone is an anomalous hexagon; its error zone area will be obviously bigger than the error zone area of point P.

4.  The Change Law of Location Error

Take Figure 4 as an example, after the offset of arbitrary point (S) and the minimum error point (P), all three angles formed mutually by point S and three reference points of the triangle will change. Supposes α₄, α₅, α₆ is respectively the angle formed by intersection of vector Sa and Sb, Sb and Sc, Sc and Sd. According to computation, the location error zone area of point S is:

(6)

After the change of point S, α₄, α₅ and α₆ are all changed compared with α₁, α₂, α₃ in the Formula (4), supposed these three angles’ variation isα₄,α₅,α₆, then there must be increment and decrement among them, and the sum of these three variation should be 0 .meanwhile, the size ofα₄,α₅,α₆ is decided by the angle which is formed mutually by point S and three reference points. For instance, angle P₁SP₂ in Figure 4 is equal to the sum of α₄ and α₆, it means the sum of α₄ and α₆ will be smaller as angle P₁SP₂ gets smaller, and as the sum of α₄, α₅ and α₆ is 180° based on the preceding text, the value of α₅ will be bigger.

The angle of point S and three reference points is not equal to 120°, and α₄/2, α₅/2 and α₆/2 is not equal to 30°.α₅ in Figure 4 is increment, and the other two are decrement. The error zone area can reach its minimum value when α₁/2, α₂/2 and α₃/2 are all equal to 30° in terms of the Formula (5). For the quantitative investigation on relationship between the central angle variation of hexagon and the error zone area, this article has made the following deduction: 

(7)

The Formula (7) is the derivative formula of tangent function, when x is 0, the tangent derivative value is 1, namely when tangent function in (0, 0) the tangent slope is the same with the slope of y=x. Tangent slope of tangent function will be bigger than 1 if, and it increases along with the increase of x, as shown in Figure 5.

In Figure 5, A is a point whose abscissa is π/6 on the tangent function curve, and the abscissa of point B is equal to a radian corresponds to α₅ in Formula (6); the ordinate is tan (π/6+α₅). BC is the variation of tangent function corresponds toα₅, makes the slope of straight line AB as K_AB, then K_AB>K_FA>K_GA. Since BC=α₅K_AB, AF₁₌α₄K_AF and AG₁=α₆K_AG, supposes BC>AF₁+ AG₁, then after the angle in Formula (4) change into the angle in Formula (6), the variation of the error zone area is:

(8)

Because:

So the supposition is correct, namely BC>AF₁+AG₁. After central angle’s relative minimum error point (P) was changed, the error zone area will increase, and this has confirmed the conclusion 1 in Formula (5). It can be also seen from the figure above, BC is to be bigger ifα₅ enlarged, meanwhile, it deduces that along with the increase of α₅ the error zone area will also increase, the deduce process is as follows:

Supposesα₄≤α₆, then K_AG≤K_AF, therefore:

(9)

In the above expression, AF₁+AG₁=α₆K_AF only whenα₄=α₆ and K_AG=K_AF, andα₆=α₅/2 holds at this time according to the geometry principle, so the variation of error zone area here can express as:

(10)

In the above expression, asα₅ gets bigger, K_AB increases, K_AF reduces, then we may get from the tangent function characteristic that the difference of K_AB and K_AF/2 will increase along withα₅, and the variation of error zone area will increase ifα₅ enlarged.

Therefore, it can draw the conclusion 2: after an arbitrary location point offset with the minimum location error point P, once one or two central angles’ degree increase which among 6 central angles of the new formed hexagon, the error zone will be bigger along with the increase amplitude of the central angle, and.

Synthesizes the above conclusion and Figure 4, it can be seen that when α₅ approaches to π, straight line be will be parallel with straight line ce, and the area of quadrangle Sbec will be close to infinity. Therefore, the final error zone area will be also close to infinitely.

5.  Application of the Location Error Change Law

According to the conclusion above, since distribution of the location error in a triangle is stochastic, it will definitely appear the maximum location error and the minimum location error in a triangle. The minimum location error in a triangle can only appear on one point, whereas the maximum location error influences positioning system's accuracy directly, as a result, this article has conducted a research to the layout shape of the reference point in view of the maximum location error.

As shown in Figure 6, there are two different kinds of reference point layout schemes under the premise of the same coverage area.

P and P₁ is respectively minimum error point in two triangles, as the point to be located S in ABC approaches to point A, angle BSC can only reduce to 60° at most, and according to the relation between central angle and included angle in Figure 4, since point S arrives at

point A, three central angles will be respectively 30°,30°,120°; as the point D in A₁BC approaches to point B, angle A₁DC can reduce to the value which is smaller than 60°, it is not difficult by the geometry principle to deduce that if point D arrives at point B, three central angles will be respectively smaller than 30°, smaller than 30°, bigger than 120°, and the location error of point A in ABC is bigger than the location error of point B in A₁BC by conclusion 2. Point A is the maximum error point in ABC, and the error of point B in A₁BC is bigger than the maximum error in ABC, so this article obtains the inference 1: The equilateral triangle positioning system's accuracy is higher than non-equilateral triangle positioning system under the same condition.

In order to verify the above deduction, this article designs an experiment as following figure. Under the platform of MicaZ node, laying the point to be located uniformly in the region encircled by three reference points, the layout graph is as follows:

The settings of nodes’ parameters are as table 1:

The location error of each point to be located is shown in Figure 8, and it can be seen that as the reference point is an equilateral triangle, the maximum location error will be about 0.14m²; when the reference point is arranged as a non-equilateral triangle, its maximum location error will be 0.153m² as seen in Figure 8, so the maximum location error is higher than the equilateral

triangle obviously. Therefore, inference 1 is correct, and it also indicates the analysis on the error change law in this article conforms to reality.

An experiment is designed to research the distribution of error in a triangle, the platform is the same with the above, and the result is shown in Figure 9:

In Figure 9, the axis X and Y construct a 100m×100m area, ABO is in the area; Axis Z is the precision of location in a triangle. It is shown in Figure 9 that, the precision in the center of a triangle is higher than the fringe areas. So, while in applications, it is better that, keep the unknown nodes in the center area of the three reference nodes.

6.  Conclusions

This article mainly studied the formation condition of minimum error and the changing law of error on location

point in arbitrary triangle according to the theory deduce. The change law of error was verified by practical test, and the research results indicate that the change law of error studied in this article may provide basis and theory instruction for the high performance and reliable location algorithm.

7.  References

[1]       W. K. Edwards, “Discovery systems in ubiquitous computing,” IEEE Pervasive Computing [J], Vol. 5, No. 2, pp. 70-77, 2006.

[2]       R. Milner, “Ubiquitous computing: Shall we understand it? [J],” Computer Journal, Vol. 49, No. 4, pp. 383-389, 2006.

[3]       J. Y. Junq, “Human-centred event description for ubiquitous service computing [A],” 2007 International Conference on Multimedia and Ubiquitous Engineering [C], pp. 1147-1151, 2007.

[4]       D. Noh and H. Shin, “An effective resource discovery in mobile ad-hoc network for ubiquitous computing [J],” Journal of KiSS: Computer Systems and Theory, Vol. 33, No. 9, pp. 666-676, 2006.

[5]       G. M. Huang, “A novel TDOA location algorithm for passive radar [C],” CIE international Conference of Radar Proceedings, pp. 41484-41888, 2007.

[6]       G. V. Zaruba, “Indoor location tracking using RSSI readings from a single Wi-Fi access point [J],” Wireless Networks, Vol. 13, No. 2, pp. 221-235, 2007.

[7]       J. Su, “Location technology research under the environment of WLAN [J],” WSEAS Transactions on Computers, Vol. 6, No. 8, pp. 1050-1055, 2007.

[8]       J. Ding, L. R. Hitt, and X. M. Zhang, “Markov chains and dynamic geometry of polygons [J],” Linear Algebra and Its Applications, pp. 255-270, 2003.

[9]       J. Ding, L. R. Hitt, and X. M. Zhang , “Sierpinski pedal triangles [J],” Linear Algebra and Its Application, pp. 1-15, 2005.

[10]    J. Hightower, G. Borriello, and R. Want, “An indoor 3D location sensing technology based on RF signal strength [R],” Technical Report, University of Washington, Seattle WA, pp. 1-16, 2000.