A Novel Lightness Localization Algorithm Based on Anchor Nodes Equilateral Triangle Layout in WSNs

Abstract

Localization, which determines the geographical locations of sensors, is a crucial issue in wireless sensor networks. In this paper, we propose a novel lightweight equilateral triangle localization algorithm (LETLA) that accurately localizes sensors and minimizes the power consumption. In the LETLA, the approximate coordinates substituted for the real coordinates of the unknown node, and the corresponding optimization problem is formulated to minimize the estimation error. With the sequences that represent the ranking of distances from the anchors to the unknown node, a simple and robust technique is developed to quickly and efficiently estimate a region containing the approximate coordinates, and a condition under which the approximate error can be minimized is given. This condition employs a new geometric construct of anchor layout called equilateral triangle diagrams. Extensive simulations show that the LETLA performs better than other state-of-the-art approaches in terms of energy consumption with the same localization precision.

1. Introduction

WSNs (Wireless Sensor Networks) have recently received great attention because they hold the potential to change many aspects of our economy and life [1–8]. Typical networks consist of a large number of densely deployed sensor nodes which could gather local data and communicate with other nodes. The data from these sensor nodes are relevant only if we know their locations. In addition, the accurate location estimation could aid in sensor network services such as routing, information processing, tasking, and querying. Therefore the knowledge of positions becomes imperative [9–17]. Moreover, the minimum resources must be used: typical sensor nodes are battery powered and have a limited processing ability [18, 19]. These constraints impose the new challenges in localization algorithm development and imply that power efficient, computation complexity and location precision should be employed simultaneously. Many methods have been proposed, such as APS (DV-Hop, DV-coordinates) [20], APIT [21–26], triangulation [27–29], Centroid [30–33], Sequence Based [34–38], Voronoi diagrams [39–43], and mathematical programming [44–46].

With regard to the precision of location, most of the localization algorithms can be classified into two broad categories: accuratelocation algorithm and approximate location algorithm. The accuratelocation algorithm produces the exact coordinates of the unknown node through complex calculations and precise measurement of distance. Typical accuratelocation algorithms include triangulation, linear programming, and semidefinite programming. The approximate location algorithms estimate an approximate position of the unknown node, with rough measurement and simple calculation. APS, APIT, Centroid, Sequence Based, and Voronoi diagrams are all approximate location algorithms.

The accurate location algorithms have two major requirements that render them disadvantages; that is, (a) the complexity is high, because triangulation, linear programming, and semidefinite programming usually involve solving higher order nonlinear equations which consume a large amount of energy, and (b) the ranging accuracy should be high enough, otherwise location algorithm will be halted. Under an adverse ranging condition, exact localization is not available; hence the statistical estimation will be introduced [47–49]. When the limited energy, the reduced processor, and the unstable accuracy of ranging results have been given [5, 17, 19], the precise coordinates of the unknown node are usually difficult to be obtained. Furthermore, in the scene of mobile sensor nodes, the precise coordinates need so much time that the location result is not valid anymore.

The approximate location algorithms consume less energy in computing, since the location procedures of APS, APIT, Centroid, Sequence Based, and Voronoi diagrams are made up of simple logical operations and algebraic operations. The aim of approximate location algorithms is to find a rough precise position of the unknown node with the least energy consumption and to achieve a compromise between the accuracy and the complexity. The approximate location algorithms are particularly useful for large-scale wireless sensor networks, because they could extend sensor nodes' life with less computation complexity and energy consumption and tolerate ranging error to a certain degree.

In this paper, we present a novel equilateral triangle localization algorithm (LETLA) that is a lightweight approximate localization algorithm and could provide better precision with less power consumption. In the LETLA, the sensing area is covered by many identical disjoint equilateral triangle diagrams, and the anchors are placed in the vertexes of the equilateral triangle diagrams. The LETLA is an approximate localization based on the concept of substituting the approximate coordinates for the real coordinates, which could loose less accuracy and save more energy. The new geometric construct of the layout, called the equilateral triangle diagrams, has a major contribution to minimize the approximate error and simplify the location procedure. In order to avoid the ranging ambiguities arising from the interference of noise, the LETLA adopts the order of ranging results to represent the location relationship of unknown node and anchors. That is an effective technology and has been employed in many works of literature [34, 36–38].

The rest of the paper is organized as follows. The next section gives a brief overview of the related work. In Section 3, we describe the procedures of the LETLA. To prove the rationality of the LETLA, we calculate the utilization coefficient of the equilateral triangle diagrams, illustrate the geometrical characteristics of the equilateral triangle diagrams, explain the reason for dividing the equilateral triangle into seven distinct regions, and introduce a principle to determine the point of tangency. In Section 4, we demonstrate the localization procedures of the LETLA in a practical scenario. In Section 5, we present a performance study of the LETLA and make a comparison with other four localization techniques. We conclude this paper and mention our future work in Section 6.

2. State of the Art

In this section, we first give a brief summary of centroid, sequence-based, and Voronoi diagrams and then show the inspirations from them.

2.1. Survey of Centroid, Sequence-Based, and Voronoi Diagrams Localization Technology

Recently, many researchers have focused on localization in WSNs. Bulusu et al. [30] demonstrated a location technique called “Centroid” in 2000. Firstly, with the help of basic connectivity or distance information, a rough estimate of relative node distance is made. Then layout of anchors is used to create a relative map of anchor position. Finally the coordinates of the centroid are obtained by calculating the coordinates of anchors which surround the unknown node in a radiation range of communication. The coordinates of the centroid are regarded as the approximate coordinates of the unknown node. In 2007, weighted centroid localization (WCL) was provided by Blumenthal et al. [31]. It is derived from a centroid determination which calculates the position of unknown node by averaging the coordinates of anchors. To improve the precision in real implementations, the weights were used to refine the estimated position [32]. Because the radio device can provide the Link Quality Indication (LQI), received signal strength indication (RSSI), the performance of packet transmission, and even the difference of energy received in packets, it achieves better precision than original centroid localization. In 2011, Jun et al. [33] presented the first theoretical framework for WCL in terms of the localization error distribution parameterized by the node density, the node placement, the shadowing variance, the correlation distance, and the inaccuracy of sensor node positioning. With this analysis, the robustness of WCL has been quantified, and some design guidelines, such as node placement and spacing, for the practical deployment of WCL, have been provided.

Yedavalli et al. [34] described the sequence-based location approach, called Ecolocation, which was quite effective in dense and uniform topologies in 2005. Ecolocation determines the location of unknown nodes by examining the ordered sequence of received signal strength measurements taken at multiple reference nodes. The key features of the Ecolocation algorithm are as follows: (1) it constructs a constraint table based on the RSSI values; (2) it searches the table to find the location. However, the Ecolocation algorithm is imperfect and has a rough localization performance. In 2009, Zhong and He [50] presented a range-free approach to capture a relative distance between 1-hop neighboring nodes from their neighborhood orderings. With little overhead, the proposed method can be conveniently applied as a transparent supporting layer for many state-of-the-art connectivity-based localization solutions.

To improve the localization accuracy, a new algorithm based on the weighted rank order correlation coefficient and the dynamic centroid was proposed by Yu et al. [35] in 2011. The simulations indicate that the localization accuracy and the robustness of the new algorithm are distinctly raised compared with the Ecolocation.

In 2008, Yedavalli et al. [36] introduced a novel sequence-based localization technique (SBL). In the SBL, the localization space can be divided into many distinct regions that can be uniquely identified by the sequences. The sequences represent the ranking of distances from the anchors to that region. The SBL and the Ecolocation are both proposed by Kiran. The Ecolocation picks the location that maximizes the number of satisfied anchor's topology constraints. In contrast, the SBL applies two statistic metrics that capture the difference in the rank orders. For the problem of location error, a new localization technique, based on the SBL, was proposed by Liu et al. [37] in 2009. Because it uses the triangular area which is enclosed by the centroids of the three “nearest” location regions, it improves the accuracy to some extent. In 2011, Hsiao et al. [38] analyzed the deployment strategy of sensor nodes for the SBL algorithm in order to effectively reduce location error such as (1) the standard deviation of the polygon area cut by the perpendicular bisectors should be kept as small as possible; (2) certain amount of space should be maintained between the sensor nodes, and (3) optimization with the angle between the perpendicular bisectors should be utilized.

Voronoi diagrams provide a powerful technique for analysing computational geometric problems. The Voronoi diagrams divide the plane into multiple polygons (known as cells). Specifically, the cells are constructed in the way that any point in a cell is closer to the local site (i.e., the site within the cell) than to any other site on the plane. Recently, the concept of Voronoi diagrams has been applied in robot navigation and map establishing [39].

In 2007, Boukerche et al. [40] proposed a novel approach that adopted Voronoi diagrams. Two types of localization can result from the proposed algorithm: the physical location of the node (e.g., latitude, longitude) or a region limited by the node's Voronoi cell. In 2009, Boukerche et al. improved DV-Hop localization algorithm with Voronoi diagrams to limit the scope of flooding communication and error [41]. In 2010, to achieve “k-coverage” of the sensing area, which means every point in the surveillance area is monitored by at least k sensors, Li and kao [42] presented a novel distributed self-location estimation scheme based on Voronoi diagrams with mobile nodes. Li illustrated that distributed Voronoi diagrams provided a convenient means of analysing the coverage problem in large-scale sensor networks. In the same year, Ampeliotis and Berberidis [43] generalized a notion of the closest point of the approach estimator. While in the closest point of approach estimator, the unknown node may lie close to the closest point of approach node. Hence the unknown node is restricted to lie in a convex set called the sorted order-K Voronoi cell.

2.2. Inspiration of Centroid, Sequence-Based, and Voronoi Diagrams Localization Technology

By the literature in former section, we find some inspirations from centroid, sequence-based, and Voronoi diagrams. They are adopted, developed, and fused in the LETLA.

According to the facts in WSNs, most location applications only require a proximate region instead of the accurate coordinates of the unknown nodes. Especially in the localization of the mobile nodes, the real-time and approximate coordinates of the mobile nodes are more effective than the accurate coordinates with a long computing delay. Moreover, WSNs need to prolong the sensor node's life, as the sensor nodes are powered by batteries and replaced difficultly. Therefore, substituting the approximate coordinates for the real coordinates of the unknown node is an efficient method to balance the location precision and the computation complexity. The purpose of centroid is to substitute the approximate coordinates for the real coordinates, which significantly reduces the location complexity. Enlightened by the centroid, we proposed a method to obtain the approximate coordinates instead of the real coordinates. This method simplifies the arc equations to the tangent equations as described in Section 3.

In WSNs, the unknown nodes can build Voronoi diagrams based on the position information of anchors and the rank of ranging result. Each node also can find the Voronoi diagrams it belongs to. There is a geometric constraint that links the location to the sorting of the distances between the unknown node and the anchors. If we know the correct sorting of the distances, we would restrict the space in which the unknown node may lie. This space is the Voronoi diagrams that corresponds to the correct sorting. Aiming to reduce the computation complexity in building Voronoi diagrams, we propose the equilateral triangle diagrams which have better geometric attribute than Voronoi diagrams in simplifying location process.

The order sequences of ranging result are more robust than the numerical measurement of distance, which has been proved in some papers [34, 36–38]. The measurement noise corrupts the numerical measurement of distance directly and distinctly over the whole location area, but it alters the rank of ranging result slightly in the most of the areas. In the Voronoi diagrams and the equilateral triangle diagrams, each region can be identified by only a sorted sequence of ranging result. Hence, the special limited region covering the unknown node can be determined by the order sequences of ranging result. In some mobile instances, the special limited region can be regarded as a rough location, if a little location delay is demanded. Consequently we apply the sequence-based method in the LETLA to determine the special limited region efficiently.

3. Lightness Equilateral Triangle Localization Method

In the LETLA, the anchors are able to acquire their positions via external device like GPS, but the unknown nodes cannot obtain this information. The unknown nodes can get the positions of the anchors and construct the corresponding location sequence tables. Then, every wireless sensor node is equipped with an omnidirectional antenna which can transfer wireless signal in all directions [21, 50–56].

The localization area is divided into many same equilateral triangles, as shown in Figure 1(a). Each equilateral triangle formed by three anchors is picked out to estimate the position of the unknown node. All anchors are deployed in the vertexes of equilateral triangles and fixed after the initial deployment. Each anchor has six adjacent anchors with the same distance, denoted by a. As shown in Figure 1(a), anchor J has six adjacent anchors K, L, M, N, R, and S, which are the nearest six anchors to J with the distance of a. Each node has the same data transmission radius, denoted by l. In the LETLA $l>2a$ is valid. ▵ denotes an equilateral triangle. The basic procedures of the LETLA can be described as follows.

Figure 1

(a) The anchor layout and a demonstration of Steps 1 and 2; (b) the example of dividing $▵DEC$ in Step 3; (c) an instance of selecting two arcs in Step 4; (d) the intersection of two tangents substituted for the intersection of two arcs in Step 5.

Step 1.

The unknown node measures the distances between itself and the anchors in its transmission range and sorts the ranging result in the ascending order. The node P is an unknown node and resides in an equilateral triangle with the side of a. This equilateral triangle can be found by utilizing the three shortest distances between the anchors and node P. If nodes $A,B$ , and C are the three nearest anchors according to the ranging sequence, the node P will reside in the $▵ABC$ , as shown in Figure 1(a). In Step 1, node P is assigned to $▵ABC$ , only by means of the rank of distance measurement, not related to any numerical computation.

Step 2.

When $▵ABC$ is determined, $▵DEC$ , $▵IBH$ , and $▵AFG$ are selected. As shown in Figure 1(a) the overlap region of $▵DEC$ , $▵IBH$ , and $▵AFG$ is $▵ABC$ and their side lengths are $2a$ . Because node P knows the positions of the anchors, it is feasible to find these three equilateral triangles.

Step 3.

$▵DEC$ , $▵IBH$ , and $▵AFG$ are divided into seven distinct regions, respectively. Figure 1(b) shows the example of dividing $▵DEC$ into seven distinct regions, by means of three arcs with the centers on the vertexes of the $▵DEC$ and the radii equal to r. Node P localizes itself at the fifth region of the $▵DEC$ according to the relation of $DP$ , $EP$ , $CP$ , and r in Table 1. Node P also finds other two regions in $▵IBH$ and $▵AFG$ , respectively, in the same way.

Table 1

The method of determining the sequence number of the region in $▵DEC$ .

Sequence number	Sufficient and necessary condition
1	$DP<r$ , $EP>r$ , $CP>r$
2	$DP<r$ , $EP<r$ , $CP>r$
3	$DP>r$ , $EP<r$ , $CP>r$
4	$DP>r$ , $EP<r$ , $CP<r$
5	$DP>$ r, $EP>r$ , $CP<r$
6	$DP<$ r, $EP>r$ , $CP<r$
7	$DP<$ r, $EP<r$ , $CP<r$

Step 4.

According to the regions including node P in $▵DEC$ , $▵IBH$ , and $▵AFG$ , two arcs are selected. They have an intersection in the position of node P. For the example presented in Step 3, two arcs are shown in Figure 1(c). Because node P is in the fifth region of $▵DEC$ , the third region of $▵IBH$ , and the sixth region of $▵AFG$ in Step 3, the arc with center F and radius $FP$ and the arc with center C and radius $CP$ are selected by Table 2. The length of the arc is limited by the range of region divided in Step 3. As shown in Figure 1(c), because node P is in the sixth region of $▵AFG$ , the length of one arc is limited by the range of the sixth region in $▵AFG$ . In the same manner, length of the other arc is limited by the range of the fifth region in $▵DEC$ .

Table 2

The method of selecting two arcs to indicate unknown node P with their intersection.

Sequence number in $▵DEC$	Sequence number in $▵IBH$	Sequence number in $▵AFG$	Center	Radius
6	2	1	Node A and node H	AP and HP
4	3	2	Node B and node D	BP and DP
5	4	6	Node C and node F	CP and FP
6	3	1	Node A and node E	AP and EP
5	2	1	Node A and node H	AP and HP
4	3	1	Node B and node D	BP and CP
5	3	2	Node B and node G	BP and GP
5	3	6	Node C and node F	CP and FP
5	4	1	Node C and node I	CP and IP
5	3	1	Node A and node B	AP and BP

Step 5.

The intersection of the two tangents is substituted for the intersection of two arcs selected in Step 4. In Figure 1(d), the intersection of the two tangents, denoted by Q, is considered to be the approximation of the intersection of two arcs which is also the position of the unknown node P. The principle of finding the point of the tangency is illustrated in Section 3.3.

3.1. Geometrical Characteristics of Equilateral Triangle Diagram

In Step 1, we propose a proposition: the unknown node P resides in $▵ABC$ , when nodes A, B, and C are the three nearest anchors in Figure 1(a). In this section, we validate the proposition through mathematical proofs. We consider the sides of an equilateral triangle as a part of the inside of the equilateral triangle. Thus, a node is either inside or outside an equilateral triangle.

Proposition 1.

As shown in Figure 1(a), if nodes $A,B$ , and C are the three nearest anchors to node P according to the ranging sequences, node P is inside $▵ABC$ .

Proof.

First, in Figure 1(a), the localization space is cut into many equilateral triangles with the same side length a, and therefore each node in the localization space will be inside an equilateral triangle with the side length a. Second, if a node is inside an equilateral triangle, the distances between the node and the three vertexes of the equilateral triangle are all less than the side length $(a)$ of the equilateral triangle. If a node is outside an equilateral triangle, the longest distance between the node and the three vertexes of the equilateral triangle is more than a.

Let us prove this by contradiction. Nodes $A,B$ , and C are the three nearest anchors to node P according to the ranging sequences. Let us suppose the false proposition that node P is outside $▵ABC$ . Since each node in the localization space will be inside an equilateral triangle with the side length a, node P is inside $▵JKL$ , which is an arbitrary equilateral triangle and differs from the $▵ABC$ . Because node P is inside $▵JKL$ , it can be concluded that $PJ<a$ , $PK<a$ and $PL<a$ . Node P is outside $▵ABC$ simultaneously, if $PA>PB>PC$ , hence it is obtained $PA>a$ . Consequently, we can draw a conclusion that $PA>PJ$ ,   $PA>PK$ , and $PA>PL$ , which is a contradiction as nodes $A,B$ , and C, are the three nearest anchors to node P. Now it is fallacious that node P is outside $▵ABC$ . So the proposition that node P is inside $▵ABC$ is true.

3.2. Reason of Dividing Equilateral Triangle

In this section, we will present the reason why $▵DEC$ , $▵IBH$ , and $▵AFG$ are divided into seven distinct regions, respectively. We first introduce a conclusion which will be proved in Section 3.3. In substituting the intersection of the two tangents for the intersection of the two arcs, as described in Step 5, the approximation error varies directly with the angle and the radius of the two arcs. For a given point of tangency, less radius and angle of the arc will lessen the approximation error.

Take $▵DEC$ for example, only node D, node E, and node C can be considered as the center of the arc in Table 2. Before dividing, the angle of the arc in $▵DEC$ is 60 degrees and the radius of the arc in $▵DEC$ is in the range $[0,a]$ . When $▵DEC$ has been divided into seven distinct regions, the length of the arc is limited by the range of the region which reduces the ranges of angle and radius of the arc in $▵DEC$ . The arcs in the first, third, and fifth regions have less radii which is about a third of the original length, and the arcs in the second, fourth, sixth, and seventh regions have less angles about 30 degrees. We can draw a conclusion that dividing $▵DEC$ into seven regions effectively reduces the range of the angle and the radius of the arc in $▵DEC$ . It will be helpful to lessen the approximate error in Step 5.

As shown in Figure 1(a), $▵ABC$ is the overlap region of $▵DEC$ , $▵IBH$ , and $▵AFG$ ; thereby $▵ABC$ is made up of ten divisions which are superposed by different regions of $▵DEC$ , $▵IBH$ , and $▵AFG$ , respectively. The ten divisions in $▵ABC$ are denoted by α, β, σ, χ, δ, ε, γ, φ, θ, and μ, as demonstrated in Figure 2(b). The definitions of the ten divisions are according the superposition of the region in $▵DEC$ , $▵IBH$ , and $▵AFG$ , as presented in Table 3. By the comparison between Tables 2 and 3, the selection of center and radius of the arc in Step 4 is based upon the division including the unknown node P.

Table 3

The definition of the ten divisions in $▵ABC$ .

Sequence number in $▵DEC$	Sequence number in $▵IBH$	Sequence number in $▵AFG$	Symbol in $▵ABC$
6	2	1	α
4	3	2	δ
5	4	6	γ
6	3	1	β
5	2	1	σ
4	3	1	χ
5	3	2	ε
5	3	6	φ
5	4	1	θ
5	3	1	μ

Figure 2

(a) The angle and the radius of the arc in different regions of $▵DEC$ after dividing; (b) the ten divisions in $▵ABC$ ; (c) applying the cosine theorem of sides to obtain r.

The length of radius in Step 3, denoted by r, is a function of a. Given $a,r$ is presented according to the cosine theorem of sides in Figure 2(c):

$$\begin{array}{cc}& r^{\mathrm{2}}={\left(\mathrm{2}a\right)}^2+{\left(\frac{\sqrt{\mathrm{3}}}{\mathrm{2}}a\right)}^2-\mathrm{2}\times \mathrm{2}a\times \frac{\sqrt{\mathrm{3}}}{\mathrm{2}}a\times \cos \left(\frac{\pi }{\mathrm{6}}\right),\end{array}$$

(1)

$$\begin{array}{cc}& r=\frac{\sqrt{\mathrm{7}}}{\mathrm{2}}a.\end{array}$$

(2)

3.3. Principle of Determining Point of Tangency

An arc is determined by the coordinates of center, the length of radius, and the value of angle. In a given arc, a tangent is determined by the position of the point of tangency. Hence, the selection of the tangent is equivalent to choosing an optimization position of the point of tangency. The tangent which touches the arc in the optimal point can minimize the approximation error in Step 4. The gap between the arc and the tangent is a major effect factor of approximation error in Step 5. To facilitate the calculation, a segment of the tangent is used to substitute the whole tangent. As shown in Figure 3, $FE$ is a segment of the tangent and intercepts by two lines parallel with the bisector of the arc. $AB$ is a given arc with a given radius and a given value of degree, denoted by r and a, respectively. The origin of the coordinate plane is denoted by O, which is located at the center of $AB$ , and the y-axis is the bisector of $AB$ and intersects $AB$ at C. D is the point of tangency and b denotes the degree between the side of $AB$ and the radius perpendicular to $FE$ . D can be any point on $AB$ , so the gap between the arc and the tangent is affected by the position of D.

Figure 3

The definition of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ .

The effects of substituting $EF$ for $AB$ can be evaluated $\text{Erro}{\text{r}}_{\mathrm{gap}}$ . $(x_{\tan },y_{\tan })$ denotes the coordinates of a point on $EF$ and $(x_{\text{arc}},y_{\text{arc}})$ denotes the coordinates of a point on $AB$ . The definition of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ is the difference between $y_{\tan }$ and $y_{\text{arc}}$ when $x_{\tan }$ is equal to $x_{\text{arc}}$ . In Figure 3, a double-headed arrow in the gap between $EF$ and $AB$ is an $\text{Erro}{\text{r}}_{\mathrm{gap}}$ :

$$\begin{array}{cc}& \text{Erro}{\text{r}}_{\mathrm{gap}}=y_{\tan }-y_{\text{arc}},\\ \left(x_{\tan }=x_{\text{arc}}=r\times \cos \left(\frac{\pi -a}{\mathrm{2}}+c\right)\right).\end{array}$$

(3)

The range of both $x_{\tan }$ and $y_{\tan }$ is (4). Because each value of the x-axis in (4) corresponds to an $\text{Erro}{\text{r}}_{\mathrm{gap}}$ , the number of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ approaches infinity:

$$\begin{array}{cc}& r\times \cos \left(\frac{\pi -a}{\mathrm{2}}\right)\le x_{\tan }\le r\times \cos \left(\frac{\pi +a}{\mathrm{2}}\right),\\ r\times \cos \left(\frac{\pi -a}{\mathrm{2}}\right)\le x_{\text{arc}}\le r\times \cos \left(\frac{\pi +a}{\mathrm{2}}\right).\end{array}$$

(4)

As $(x_{\tan },y_{\tan })$ denotes the coordinates of a point on $EF$ and $(x_{\text{arc}},y_{\text{arc}})$ denotes the coordinates of a point on $AB$ , the expressions of $y_{\tan }$ and $y_{\text{arc}}$ can be obtained with the angle a, b, and c.

$$\begin{array}{ll}& y_{\tan }=r\times \tan \left(\pi -\frac{a}{\mathrm{2}}+b\right)\times \left[\sin \left(\frac{a}{\mathrm{2}}-c\right)-\sin \left(\frac{a}{\mathrm{2}}-b\right)\right]\\ +r\times \cos \left(\frac{a}{\mathrm{2}}-b\right),\\ y_{\text{arc}}=r\times \sin \left(\frac{\pi }{\mathrm{2}}-\frac{a}{\mathrm{2}}+c\right)=r\times \cos \left(\frac{a}{\mathrm{2}}-c\right).\end{array}$$

(5)

By combining (3) and (5), the following new expression of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ can be obtained in (6). Specifically, $\text{Erro}{\text{r}}_{\mathrm{gap}}$ is the function of r, a, b, and c and is actually in proportion to r and a according to (6). When $AB$ is fixed, r and a are given. The parameter b is determined by the position of D. The parameter c in (6) has the range of $[0,a]$ . Finding the optimal position of D is equivalent to finding the optimal value of angle b to minimize the $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole feasible range of angle c, in the given radius r and angle a. Three indicators can quantify the effect of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole gap between the $EF$ and $AB$ and are the functions of angle b:

$$\begin{array}{ll}& \text{Erro}{\text{r}}_{\mathrm{gap}}=r\times (\frac{\mathrm{1}-\sin \left(\left(a/\mathrm{2}\right)-b\right)\times \sin \left(\left(a/\mathrm{2}\right)-c\right)}{\cos \left(\left(a/\mathrm{2}\right)-b\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-\frac{\cos \left(\left(a/\mathrm{2}\right)-b\right)\times \cos \left(\left(a/\mathrm{2}\right)-c\right)}{\cos \left(\left(a/\mathrm{2}\right)-b\right)})\\ =r\times \left(\frac{\mathrm{1}-\cos \left(b-c\right)}{\cos \left(\left(a/\mathrm{2}\right)-b\right)}\right).\end{array}$$

(6)

The first indicator is $E({\text{Error}}_{\mathrm{gap}})$ which is defined as the average of ${\text{Error}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ . $x_A$ and $x_B$ denote the coordinates of A and B in the x-axis and $[x_A,x_B]$ represents the whole feasible range on the x-axis over the whole gap between $EF$ and $AB$ . Then the expression of $E({\text{Error}}_{\mathrm{gap}})$ is obtained:

$$\begin{array}{cc}& E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\frac{\mathrm{1}}{x_B-x_A}{\int }_{x_A}^{x_B}\text{Erro}{\text{r}}_{\mathrm{gap}}dx.\end{array}$$

(7)

$[x_A,x_B]$ in the x-axis can be represented by $[0,a]$ in angle c. By differential calculus of (3), we obtain

$$\begin{array}{cc}& dx=-r\times \sin \left(\frac{\pi }{\mathrm{2}}-\frac{a}{\mathrm{2}}+c\right)\times dc.\end{array}$$

(8)

By combining (7) and (8),

$$\begin{array}{ll}& E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\frac{\mathrm{1}}{x_B-x_A}{\int }_{x_A}^{x_B}\text{Erro}{\text{r}}_{\mathrm{gap}}\times dx\\ =\frac{\mathrm{1}}{\mathrm{2}\sin \left(a/\mathrm{2}\right)}{\int }_{\mathrm{0}}^a\text{Erro}{\text{r}}_{\mathrm{gap}}\times \cos \left(\frac{a}{\mathrm{2}}-c\right)\times dc.\end{array}$$

(9)

By combining (6) and (9), the new expression of $E({\text{Error}}_{\mathrm{gap}})$ is given by

$$\begin{array}{ll}& E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\frac{r}{\mathrm{2}\sin \left(a/\mathrm{2}\right)}\\ \times [\frac{\mathrm{8}\sin \left(a/\mathrm{2}\right)-\sin \left(\left(\mathrm{3}/\mathrm{2}\right)a-b\right)}{\mathrm{4}\cos \left(\left(a/\mathrm{2}\right)-b\right)}\\ \hspace{1em}\hspace{1em}-\frac{\sin \left(\left(a/\mathrm{2}\right)+b\right)}{\mathrm{4}\cos \left(\left(a/\mathrm{2}\right)-b\right)}-\frac{a}{\mathrm{2}}].\end{array}$$

(10)

Because $AB$ is given, radius r and angle a are fixed. The value of $E(\text{Erro}{\text{r}}_{\mathrm{gap}})$ only accounts for the value of angle b. The extremum problem can be solved by finding the value of angle b which makes the first derivative of $E(\text{Erro}{\text{r}}_{\mathrm{gap}})$ equal to zero:

• (i)

syms $ab$ ,

(ii)

solve $(\text{diff}{(}^{\prime }(8*\sin (0.5*a)-\sin (1.5*a-b)-\sin (0.5*a+b))/(4*\cos (0.5*a-b){)}^{\prime }{,}^{\prime }{b}^{\prime }){,}^{\prime }{b}^{\prime })$ .

The numerical result given by MATLAB demonstrates that $E(\text{Erro}{\text{r}}_{\mathrm{gap}})$ can be least only if b is equal to 0.5a. It shows that $b=0.5a$ is the condition for minimizing $E(\text{Erro}{\text{r}}_{\mathrm{gap}})$ and means that the point of tangency is the midpoint of the arc. When D is the midpoint of $AB$ in Figure 3, the average of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ is minimal.

The second indicator is $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ which is defined as the variance of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ . $[x_A,x_B]$ represents the whole feasible range on the x-axis over the whole gap between $EF$ and $AB$ . Then the expression of $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ is obtained:

$$\begin{array}{cc}& D\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\frac{\mathrm{1}}{x_B-x_A}{\int }_{x_A}^{x_B}{\left(\text{Erro}{\text{r}}_{\mathrm{gap}}-E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)\right)}^{2}dx.\end{array}$$

(11)

By applying (8) to (11), (12) is obtained:

$$\begin{array}{ll}& D\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\frac{\mathrm{1}}{x_B-x_A}{\int }_{x_A}^{x_B}{\left(\text{Erro}{\text{r}}_{\mathrm{gap}}-E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)\right)}^2\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times dx\\ =\frac{\mathrm{1}}{\mathrm{2}\sin \left(a/\mathrm{2}\right)}{\int }_{\mathrm{0}}^a{\left(\text{Erro}{\text{r}}_{\mathrm{gap}}-E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)\right)}^2\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \cos (\left(a/\mathrm{2}\right)-c)\times dc.\end{array}$$

(12)

Combined with (6), (12) can be changed to (13). It is the new expression of $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ :

$$\begin{array}{ll}& D\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)={\left(\frac{r}{\cos \left(\left(a/\mathrm{2}\right)-b\right)}-E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)\right)}^2\\ +r\times \left(\frac{\cos \left(\left(a/\mathrm{2}\right)-b\right)\times E\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)-r}{\mathrm{co}{\text{s}}^{\mathrm{2}}\left(\left(a/\mathrm{2}\right)-b\right)}\right)\\ \times (\frac{\mathrm{2}\cos \left(\left(a/\mathrm{2}\right)-b\right)+\sin \left(\left(\mathrm{3}/\mathrm{2}\right)a-b\right)}{\mathrm{4}\sin \left(a/\mathrm{2}\right)}\\ \hspace{1em}\hspace{1em}+\frac{\sin \left(\left(a/\mathrm{2}\right)+b\right)}{\mathrm{4}\sin \left(a/\mathrm{2}\right)})\\ +r^2(\frac{3\sin \left(\left(3/2\right)a-2b\right)}{24\sin \left(a/2\right){\cos }^2\left(a/2-b\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\sin \left(\left(5/2\right)a-2b\right)}{24\sin \left(a/2\right){\cos }^2\left(a/2-b\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}-\frac{3\sin \left(a/2-2b\right)}{24\sin \left(a/2\right){\cos }^2\left(a/2-b\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}+\frac{\sin \left(a/2+b\right)+12\sin \left(a/2\right)}{24\sin \left(a/2\right){\cos }^2\left(\left(a/2\right)-b\right)}).\end{array}$$

(13)

Because $AB$ is given, radius r and angle a are fixed. $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ only accounts for the value of angle b. The numerical result given by MATLAB demonstrates that $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ can be least only if b is equal to $0.5a$ . It shows that $b=0.5a$ is the condition for minimizing $D(\text{Erro}{\text{r}}_{\mathrm{gap}})$ and means that the point of tangency is the midpoint of the arc. When D is the midpoint of $AB$ in Figure 3, the variance of ${\text{Error}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ is minimal.

• (i)

syms $a\hspace{0.17em}b\hspace{0.17em}s\mathrm{1}\hspace{0.17em}s\mathrm{2}\hspace{0.17em}s\mathrm{3}\hspace{0.17em}s\mathrm{4}\hspace{0.17em}s\mathrm{5}$ ;

(ii)

$s\mathrm{1}=(\mathrm{1}/(\mathrm{2}*\sin (\mathrm{0.5}*a)))*(((\mathrm{8}*\sin (\mathrm{0.5}*a)+\sin (b-\mathrm{1.5}*a)-\sin (b+\mathrm{0.5}*a))/$   $(\mathrm{4}*\cos (b-\mathrm{0.5}*a)))-(\mathrm{0.5}*a))$ ;

(iii)

$s\mathrm{2}=\mathrm{2}*\sin (\mathrm{0.5}*a)*(\mathrm{1}/(\cos (b-\mathrm{0.5}*a)^\mathrm{2}\mathrm{\hspace{0.17em}\hspace{0.17em}})+(s\mathrm{1})^\mathrm{2}-(\mathrm{2}*(s\mathrm{1}))/(\cos (b-\mathrm{0.5}*a)))$ ;

(iv)

$s\mathrm{3}=((\mathrm{2}*(s\mathrm{1}))/(\cos (b-\mathrm{0.5}*a))-(\mathrm{2})/((\cos (b-\mathrm{0.5}*a))^\mathrm{2}))*((\mathrm{0.5}*\cos (b-\mathrm{0.5}*a))-$   $(\mathrm{0.25}*\sin (b-\mathrm{1.5}*a))+(\mathrm{0.25}*\sin (b+\mathrm{0.5}*a)))$ ;

(v)

$s\mathrm{4}=(\mathrm{1}/(\mathrm{2}*(\cos (b-\mathrm{0.5}*a)^\mathrm{2})))*((\mathrm{0.5}*\sin (\mathrm{1.5}*a-\mathrm{2}*b))-((\mathrm{1}/\mathrm{6})*(\sin (\mathrm{2}*b-\mathrm{2.5}*a)))$   $-(\mathrm{0.5}*\sin (\mathrm{0.5}*a-\mathrm{2}*b))+((\mathrm{1}/\mathrm{6})*(\sin (\mathrm{2}*b+\mathrm{0.5}*a)))+(\mathrm{2}*\sin (\mathrm{0.5}*a)))$ ;

(vi)

$s\mathrm{5}=s\mathrm{2}+s\mathrm{3}+s\mathrm{4}$ ;

(vii)

solve $(\text{diff}(s\mathrm{5}{,}^{\prime }{b}^{\prime }){,}^{\prime }{b}^{\prime })$ .

The third indicator is $\text{MAX}(\text{Erro}{\text{r}}_{\mathrm{gap}})$ which is defined as the maximal value of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ , given a fixed position ofD, when the position ofD is fixed, which means that the degree of angle b is constant. Considering the definition of ${\text{Error}}_{\mathrm{gap}}$ , the maximal value of ${\text{Error}}_{\mathrm{gap}}$ can be found in $c=0$ or $c=a$ and depends on the degree of angle b. Thus, the expression of $\text{MAX}(\text{Erro}{\text{r}}_{\mathrm{gap}})$ is obtained:

$$\begin{array}{cc}& \mathrm{Max}\left(\text{Erro}{\text{r}}_{\mathrm{gap}}\right)=\{\begin{array}{c}r\times \left(\frac{\mathrm{1}-\cos \left(a-b\right)}{\cos \left(\left(a/\mathrm{2}\right)-b\right)}\right),\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{0}\le b<\frac{a}{\mathrm{2}},\hspace{0.17em}\hspace{0.17em}c=a\hfill \\ r\times \left(\frac{\mathrm{1}-\cos \left(a/\mathrm{2}\right)}{\begin{array}{c}\mathrm{1}\\ \end{array}}\right),\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}b=\frac{a}{\mathrm{2}},\hspace{0.17em}\hspace{0.17em}c=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\text{or}\hspace{0.17em}\hspace{0.17em}c=a\hfill \\ r\times \left(\frac{\mathrm{1}-\cos \left(b\right)}{\cos \left(\left(a/\mathrm{2}\right)-b\right)}\right),\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{a}{\mathrm{2}}\le b<a,\hspace{0.17em}\hspace{0.17em}\text{c}=\mathrm{0}.\hfill \end{array}\end{array}$$

(14)

Proposition 2.

As shown in Figure 3 and indicated in (14). If the degree of angle a is constant and the degree of angle b is in the interval $[\mathrm{0,0.5}a)$ , $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ will be reached in $c=a$ when   $b=0.5a$ .

Proposition 3.

As shown in Figure 3 and indicated in (14), if the degree of angle a is constant and the degree of angle b is in the interval $(0.5a,a]$ , $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ will be reached in $c=0$ when $b=0.5a$ .

Proof.

Consider

•  

∵ $\mathrm{0}\le b<a/\mathrm{2}\begin{array}{c}\end{array}\text{and}\begin{array}{c}\end{array}\mathrm{0}<a<\pi$

 

∴ $-a/\mathrm{2}<-b\le \mathrm{0}$

 

∴ $a/\mathrm{2}<a-b\le a$

 

∵ $\mathrm{0}<a/\mathrm{2}<\pi /\mathrm{2}$

 

∴ $\mathrm{1}-\cos (a/\mathrm{2})<\mathrm{1}-\cos (a-b)$

 

∵ $\mathrm{1}>\cos (a/\mathrm{2}-b)$

 

∴ $r\times ((\mathrm{1}-\cos (a/\mathrm{2}))/1)<r\times ((\mathrm{1}-\cos (a-b))/\cos ((a/\mathrm{2})-b))$ .

Proof.

Consider

•  

∵ $a/\mathrm{2}<b\le a\begin{array}{c}\end{array}\text{and}\begin{array}{c}\end{array}\mathrm{0}<a<\pi$

 

∴ $\mathrm{0}<a/\mathrm{2}<\pi /\mathrm{2}$

 

∴ $\mathrm{1}-\cos (a/\mathrm{2})<\mathrm{1}-\cos (b)$

 

∵ $\mathrm{1}>\cos (a/\mathrm{2}-b)$

 

∴ $r\times ((\mathrm{1}-\cos (a/\mathrm{2}))/1)<r\times ((\mathrm{1}-\cos (b))/\cos ((a/\mathrm{2})-b))$ .

Therefore, if a is given, we can obtain the minimal $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ in $b=0.5a$ . It means that $b=0.5a$ is the necessary and sufficient condition for minimizing $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ . Taking $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ into consideration, consequently, the point of the tangent must be the midpoint of the arc. When D is the midpoint of $AB$ in Figure 3, the maximal value of $\text{Erro}{\text{r}}_{\mathrm{gap}}$ over the whole gap between $EF$ and $AB$ is less than other positions of D.

Given an arc, the tangent is dominated by the position of the point of tangency. If the point of tangency is the midpoint of the arc, then $E(\text{Erro}{\text{r}}_{\mathrm{gap}})$ , $D({\text{Error}}_{\mathrm{gap}})$ , and $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ have the least value in each range. It has been used in the LETLA to choose the point of tangency.

3.4. Utilization Coefficient of Equilateral Triangle Diagrams

In Step 4, two anchors are selected from the nine anchors which have the special geometrical relations as shown in Figure 1(a). However, it is hard to satisfy the geometrical requirement in the boundaries of the location space. In Figure 4, the location area, unlocation area, and cover area are defined and illustrated in three examples with the sides $(3a,a)$ , $(4a,2a)$ , and $(5a,3a)$ of the cover area. In this section, the utilization coefficient of equilateral triangle diagrams is obtained, which means the percentage of the location area in the cover area. As the sides of the cover area increase linearly, the number of anchors and the location area, the unlocation area, and the cover area are listed in Table 4.

Table 4

The relation of the five indexes.

The side length of cover area	(3a, 1a)	(4a, 2a)	(5a, 3a)	(6a, 4a)	(7a, 5a)	(8a, 6a)
The number of anchors	18	36	60	90	126	168
Unlocation area	$18\times \frac{a^2\sqrt{3}}{4}$	$30\times \frac{a^2\sqrt{3}}{4}$	$42\times \frac{a^2\sqrt{3}}{4}$	$54\times \frac{a^2\sqrt{3}}{4}$	$66\times \frac{a^2\sqrt{3}}{4}$	$78\times \frac{a^2\sqrt{3}}{4}$
Location area	$4\times \frac{a^2\sqrt{3}}{4}$	$22\times \frac{a^2\sqrt{3}}{4}$	$52\times \frac{a^2\sqrt{3}}{4}$	$94\times \frac{a^2\sqrt{3}}{4}$	$148\times \frac{a^2\sqrt{3}}{4}$	$214\times \frac{a^2\sqrt{3}}{4}$
Cover area	$22\times \frac{a^2\sqrt{3}}{4}$	$52\times \frac{a^2\sqrt{3}}{4}$	$94\times \frac{a^2\sqrt{3}}{4}$	$148\times \frac{a^2\sqrt{3}}{4}$	$214\times \frac{a^2\sqrt{3}}{4}$	$292\times \frac{a^2\sqrt{3}}{4}$

Figure 4

The topological structure of the equilateral triangle diagrams.

$(m\times a,n\times a)$ denotes the length of the sides of the cover area in Figure 4 the formulas of $\text{Nu}{\text{m}}_{\text{anchor}},S_{\text{unlocat}},S_{\text{locat}}$ , and $S_{\text{cover}}$ are obtained as follows. $\text{Nu}{\text{m}}_{\text{anchor}}$ is the number of anchors and S_unlocat is the unlocation area. Because $m-n=2a$ is the relation between m and n in terms of Table 4, (15), (16), (17), and (18) can be simplified to single variable functions of n:

$$\begin{array}{cc}& \text{Nu}{\text{m}}_{\text{anchor}}={\sum }_{k=\mathrm{0}}^{k=n}\left(k+\mathrm{1}\right)\times \mathrm{6},\end{array}$$

(15)

$$\begin{array}{cc}& S_{\text{unlocat}}=\left[\mathrm{18}+\mathrm{12}\times \left(n-\mathrm{1}\right)\right]\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\end{array}$$

(16)

$$\begin{array}{cc}& S_{\text{locat}}=\{\begin{array}{cc}\mathrm{4}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & n=\mathrm{1}\hfill \\ \mathrm{22}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & n=2\hfill \\ \left[\mathrm{4}+\mathrm{18}\times \left(n-\mathrm{1}\right)+{\sum }_{k=\mathrm{1}}^{k=n-\mathrm{2}}\mathrm{12}\times k\right]\hfill & \hfill \\ \hspace{1em}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & \begin{array}{c}n>\mathrm{2}\end{array},\hfill \end{array}\end{array}$$

(17)

$$\begin{array}{cc}& S_{\text{cover}}=\{\begin{array}{cc}\mathrm{22}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & n=\mathrm{1}\hfill \\ \mathrm{22}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & n=2\hfill \\ \left[\mathrm{22}+\mathrm{18}\times \left(n-\mathrm{1}\right)+{\sum }_{k=\mathrm{1}}^{k=n-\mathrm{1}}\mathrm{12}\times k\right]\hfill & \hfill \\ \hspace{1em}\times \frac{a^{\mathrm{2}}\sqrt{\mathrm{3}}}{\mathrm{4}},\hfill & \begin{array}{c}n>\mathrm{1}\end{array}.\hfill \end{array}\end{array}$$

(18)

The utilization coefficient of equilateral triangle diagrams is the complement of ratio of $S_{\text{unlocat}}$ to $S_{\text{cover}}$ :

$$\begin{array}{ll}& \mathrm{1}-\frac{S_{\text{unlocat}}}{S_{\text{cover}}}\\ =\{\begin{array}{ll}\mathrm{1}-\frac{\mathrm{18}}{\mathrm{22}},\hfill & n=1\hfill \\ \mathrm{1}-\frac{\mathrm{18}+\mathrm{12}\times \left(n-\mathrm{1}\right)}{\mathrm{22}+\mathrm{18}\times \left(n-\mathrm{1}\right)+{\sum }_{k=\mathrm{1}}^{k=n-\mathrm{1}}\mathrm{12}\times k},\hfill & n>\mathrm{1}.\hfill \end{array}\end{array}$$

(19)

As (16) and (18) imply, $S_{\text{unlocat}}$ grows linearly with n, and $S_{\text{cover}}$ grows linearly with the power of n. Consequently, the increment of n will lead to the ratio of $S_{\text{unlocat}}$ to $S_{\text{cover}}$ close to zero. It means that the utilization coefficient of equilateral triangle diagrams will get close to one hundred percent as the scale of network increases. In Figure 5 the growth rate of $S_{\text{unlocat}}$ is far less than the growth rate of $S_{\text{cover}}$ as n increases. When the scale of cover area increases, the influence of unlocation area in the LETLA will rapidly vanish.

Figure 5

The utilization coefficient of equilateral triangle diagrams grows along with n's growth.

4. Lightness Equilateral Triangle Localization Algorithm

In this section, the LETLA will be explained by a practical example. This example is shown in Figure 1, and the given conditions are the same as Section 3. When the unknown node P knows the distance between itself and the anchor, the LETLA can be implemented as follows.

• (a)

Sort the ranging results and select the three nearest anchors $A,B$ , and C, then find node P in $▵ABC$ .

(b)

$▵DEC$ , $▵IBH$ , and $▵AFG$ can be determined, for $▵ABC$ is their overlapped region and their side lengths are equal to $2a$ . The geometric relation of equilateral triangles is determined by the deployment of anchors which is known by node P.

(c)

Node P finds the regions in $▵DEC$ , $▵IBH$ , and $▵AFG$ , respectively, through the relationship between the ranging results and r, as exemplified in Table 1.

(d)

As node P is in the fifth region of $▵DEC$ , the third region of $▵IBH$ , and the sixth region of $▵AFG$ in Figure 1(c), the arc with the center F and the radius $FP$ and the other arc with the center C and the radius $CP$ are selected on the basis of Table 2.

(e)

Derive two tangential equations of the arcs obtained in the previous step and solve the two tangential equations.

The main parameters of a tangential equation include the coordinates of the point of tangency and the slope of tangency. When the tangent is perpendicular to the line which goes through C and the point of tangency K, the slope of tangency can be derived by

$$\begin{array}{cc}& \text{slope}\hspace{0.17em}\text{of}\hspace{0.17em}\text{tangent}=-\frac{x_c-x_k}{y_c-y_k}.\end{array}$$

(20)

$(x_c,y_c)$ and $(x_k,y_k)$ are the coordinates of C and K, respectively. P knows $(x_c,y_c)$ , but does not know $(x_k,y_k)$ . In order to determine $(x_k,y_k)$ , a coordinate system is established in Figure 6.

Figure 6

The calculation of the point of the tangent.

The new coordinate system can be built as follows. First, move the original coordinate system to the positive direction of the x-axis with the distance $x_c$ . Second, move the original coordinate system to the positive direction of the y-axis with the distance $y_c$ . Finally, rotate the original coordinate system 180 degree clockwise. In the new coordinate system, the origin is C denoted by $(x_c^{\prime },y_c^{\prime })$ , and the coordinates of K are $(x_k^{\prime },y_k^{\prime })$ . The values of $(x_c^{\prime },y_c^{\prime })$ and $(x_k^{\prime },y_k^{\prime })$ are shown in (21), where $CP$ is a known ranging result:

$$\begin{array}{cc}& x_c^{\prime }=\mathrm{0},\\ y_c^{\prime }=\mathrm{0},\\ x_k^{\prime }=-CP,\\ y_k^{\prime }=\mathrm{0}.\end{array}$$

(21)

The relation of $(x_k,y_k)$ and $(x_k^{\prime },y_k^{\prime })$ is

$$\begin{array}{cc}& x_k^{\prime }=-\left(x_k-x_c\right),\\ y_k^{\prime }=-\left(y_k-y_c\right).\end{array}$$

(22)

Because $(x_c,y_c)$ and $CP$ are known, combined with (21), $(x_k,y_k)$ can be obtained by

$$\begin{array}{cc}& x_k=x_c-x_k^{\prime },\\ y_k=y_c-y_k^{\prime }.\end{array}$$

(23)

The coordinates of the point of tangency are the function of the coordinates of the center of the arc, the length of radius of the arc, and the angle between the bisector and the x-axis. When the coordinates of the point of tangency are known, the slop of tangency can be drawn from (20). Now the tangential equation can be set up. Solving the intersection of two tangents is equivalent to solving the bivariate system of linear equations.

To sum up, the (a), (b), (c), and (d) in the LETLA are achieved by relational operation and only (e) is implemented by arithmetic operation. The procedure (e) only contains the four arithmetic operations and does not involve solving multivariable nonlinear equations, differentiation, integration, statistical estimation, and mathematical programming. It suggests that the LETLA is a lightness location method.

5. Performance Evaluation

5.1. Localization Error Evaluation

In Section 5.1, a numerical analysis of the performance of localization error will be given. Figure 7 shows the anchor distribution and the coordinate system. It is set up by putting Figure 1(a) in a coordinate system with an origin O on the lower left quarter. In Figure 7, the distance between a pair of adjacent anchors is denoted by a, which is the same in Figure 1(a) and assigned a value of 50. The length of radius to divide $▵DEC$ , $▵IBH$ , and $▵AFG$ is denoted by r, which is also like Figure 1(a) and assigned a value according to (2). To obtain the localization error $\text{Erro}{\text{r}}_{\text{locat}}$ , node P has been placed in the different positions of $▵ABC$ for many times.

Figure 7

A numerical example of Figure 1(a).

Figure 8 shows the distribution of $\text{Erro}{\text{r}}_{\text{locat}}$ in $▵ABC$ . The z-axis in Figure 8 indicates the value of $\text{Erro}{\text{r}}_{\text{locat}}$ in the corresponding testing position. Given $a=50$ , the area of $\text{Erro}{\text{r}}_{\text{locat}}<1$ makes up 72.971% of $▵ABC$ . The area of $\text{Erro}{\text{r}}_{\text{locat}}<3$ covers 90.519% of $▵ABC$ . The maximum and minimum values of $\text{Erro}{\text{r}}_{\text{locat}}$ are 6.13 and 0, respectively. The data transmission radius of node P is l and $l>2a$ . A common evaluation method is computing the ratio of $\text{Erro}{\text{r}}_{\text{locat}}$ and l, and the ratio within 10% is a good indicator of localization performance [57]. Figure 8 illustrates LETLA can achieve the ratio within 10% in 92.655% of $▵ABC$ . It means that the LETLA can obtain a good localization precision and a stable distribution.

Figure 8

The distribution of $\text{Erro}{\text{r}}_{\text{locat}}$ in $▵ABC$ according to the geometrical relation in Figure 7: (a) the side view; (b) the top view. In both (a) and (b), the color indicates the value of $\text{Erro}{\text{r}}_{\text{locat}}$ .

In Figure 8, $\text{Erro}{\text{r}}_{\text{locat}}$ is associated with the division in $▵ABC$ , denoted by α, β, σ, χ, δ, ε, γ, φ, θ, and μ as demonstrated in Figure 2(b) and defined in Table 3. The connecting points of β and χ, ε and φ, and σ and θ have the maximum value of $\text{Erro}{\text{r}}_{\text{locat}}$ . $\text{Erro}{\text{r}}_{\text{locat}}$ in α, δ, and γ is all less than 1 and $\text{Erro}{\text{r}}_{\text{locat}}$ in μ is less than 1 in least 60% area. Moreover, $\text{Erro}{\text{r}}_{\text{locat}}$ is distributed uniformly in α, δ, γ, and μ. The reason of producing the maximum value of $\text{Erro}{\text{r}}_{\text{locat}}$ in the connecting point can be explained as follows. Combine Tables 2 and 3, when node P lies in the connecting point of the divisions in $▵ABC$ , the intersection of two the arcs as determined from Table 2 is far away from the intersection of the two tangents. The reason is that the intersection of the two arcs is on the endpoint of the both arcs which both have a maximum of distance with the tangent. That result has been analyzed in Section 3.3 with the conception of $\mathrm{Max}({\text{Error}}_{\mathrm{gap}})$ and the maximal value of ${\text{Error}}_{\mathrm{gap}}$ is in the endpoint of the arc. Since the connecting point is the intersection of the two arcs' endpoint, ${\text{Error}}_{\mathrm{gap}}$ of the two arcs reaches the maximum value simultaneously. Consequently, ${\text{Error}}_{\mathrm{gap}}$ in the connecting point is greater than other positions of $▵ABC$ obviously.

Figure 9 shows the distribution of $\text{Erro}{\text{r}}_{\text{locat}}$ in $▵ABC$ . Figures 8 and 9 are distinguished by the ranging noise. In Figure 8   $\text{Erro}{\text{r}}_{\text{locat}}$ is produced by the LETLA with accurate ranging results, but in Figure 9   $\text{Erro}{\text{r}}_{\text{locat}}$ is produced by the LETLA with the ranging results which are corrupted by noise following a Gaussian distribution. The ranging noise is represented by ζ, with expectation $E(\zeta )=0$ and variance $D(\zeta )=0.5$ .

Figure 9

The distribution of $\text{Erro}{\text{r}}_{\text{locat}}$ in $▵ABC$ with ranging noise according to the geometrical relation in Figure 7: (a) the side view; (b) the top view.

Given $a=50$ , $E(\zeta )=0$ , and $D(\zeta )=0.5$ , the area of $\text{Erro}{\text{r}}_{\text{locat}}<1$ makes up 65.251% of $▵ABC$ . The area of $\text{Erro}{\text{r}}_{\text{locat}}<3$ covers 82.238% of $▵ABC$ . The maximum and minimum values of $\text{Erro}{\text{r}}_{\text{locat}}$ are 7.26 and 0, respectively. Although the ranging noise lowers the localization precision of the LETLA, the LETLA also achieves the ratio within 10% in 90.14% of $▵ABC$ .

Figure 9 shows that $\text{Erro}{\text{r}}_{\text{locat}}$ is associated with the division in $▵ABC$ , which is the same as Figure 8. $\text{Erro}{\text{r}}_{\text{locat}}$ is distributed uniformly in α, δ, γ, and μ. In β, σ, χ, ε, φ, and θ, $\text{Erro}{\text{r}}_{\text{locat}}$ is affected by the noise, because the areas of these divisions are less than the areas of α, δ, γ, and μ. It leads to the misjudgment of the division including node P more easily:

$$\begin{array}{cc}& P\left\{\left|\xi -E\left(\xi \right)\right|<\mathrm{3}D\left(\xi \right)\right\}\ge \mathrm{0.8889}.\end{array}$$

(24)

By comparing Figures 9 with 8, the range of $\text{Erro}{\text{r}}_{\text{locat}}$ in Figure 8 and in Figure 9 is [0, 6.13] and [0, 7.26]. Based on the Chebyshev inequality of (24), $E(\zeta )=0$ , and $D(\zeta )=0.5$ , we obtain ζ in the range of $[-\mathrm{1.5,1}.5]$ with the probability of 88.89%. It means that the noise cannot change the range of $\text{Erro}{\text{r}}_{\text{locat}}$ obviously in Figure 8; hence the difference between the maximum of Figure 9 and that of Figure 8 is only 1.13. Consequently, the area of $\text{Erro}{\text{r}}_{\text{locat}}<1$ and $\text{Erro}{\text{r}}_{\text{locat}}<3$ only decreases 7.72% and 8.281%, respectively.

5.2. Localization Coverage and Beacon Density

To study the performances of the localization coverage and beacon density, we generate a variety of the test scenarios of the different numbers of anchors. The graphs in Figure 10 illustrate three test scenarios. The whole test area, designed as a circular domain and denoted by $S_{\text{test}}$ , is the whole area of the test scenario. The whole test area is calculated using the following equation:

$$\begin{array}{cc}& S_{\text{test}}=\pi ·{\left(\mathrm{4}a\right)}^2.\end{array}$$

(25)

Figure 10

The topological structure of the test scenarios.

The location area $S_{\text{locat}}$ and the cover area $S_{\text{cover}}$ represent the region in which the node can be located and region covered by anchors. For instance, Table 5 shows the number of anchors, the location area, and the cover area calculated for varying the side length of the cover area. The variable n is a factor used to indicate the side length of the cover area, as shown in Table 5. Because the number of anchors is determined by n, as shown in Table 5, we can replace the anchor number with the variable n to facilitate the calculation of the location area and cover area.

Table 5

The relationship among the four indexes.

The side length of the cover area	The number of anchors	Location area	Cover area
$\mathrm{1}a$	7	0	$\mathrm{3}\sqrt{\mathrm{3}}·a^{\mathrm{2}}/\mathrm{2}$
$\mathrm{2}a$	19	$\mathrm{3}\sqrt{\mathrm{3}}·a^{\mathrm{2}}/\mathrm{2}$	$\mathrm{6}\sqrt{\mathrm{3}}·a^{\mathrm{2}}$
$\mathrm{3}a$	37	$\mathrm{6}\sqrt{\mathrm{3}}·a^{\mathrm{2}}$	$\mathrm{27}\sqrt{\mathrm{3}}·a^{\mathrm{2}}/\mathrm{2}$
$\mathrm{4}a$	61	$\mathrm{27}\sqrt{\mathrm{3}}·a^{\mathrm{2}}/\mathrm{2}$	$\mathrm{24}\sqrt{\mathrm{3}}·a^{\mathrm{2}}$
$\mathrm{5}a$	91	$\mathrm{24}\sqrt{\mathrm{3}}·a^{\mathrm{2}}$	$\mathrm{125}\sqrt{\mathrm{3}}·a^{\mathrm{2}}/\mathrm{2}$
$n·a$	$\mathrm{1}+\mathrm{3}n·(n+\mathrm{1})$	$\mathrm{3}\sqrt{\mathrm{3}}·(n-\mathrm{1}{)}^{\mathrm{2}}·a^{\mathrm{2}}/\mathrm{2}$	$\mathrm{3}\sqrt{\mathrm{3}}·n^{\mathrm{2}}·a^{\mathrm{2}}/\mathrm{2}$

We use the following definitions in the evaluation: localization coverage, $P_r$ , denotes the ratio of the location area to the whole test area:

$$\begin{array}{cc}& P_r=\frac{S_{\text{locat}}}{S_{\text{test}}}=\frac{\mathrm{3}\sqrt{\mathrm{3}}·{\left(n-\mathrm{1}\right)}^2·a^{\mathrm{2}}}{\mathrm{2}\pi ·{\left(\mathrm{4}a\right)}^2}=\frac{\mathrm{3}\sqrt{\mathrm{3}}·{\left(n-\mathrm{1}\right)}^2}{\mathrm{32}\pi },\\ P_d=\frac{\text{NU}{\text{M}}_{\text{anchor}}}{S_{\text{cover}}}=\frac{\mathrm{2}\left(\mathrm{1}+\mathrm{3}n·\left(n+\mathrm{1}\right)\right)}{\mathrm{3}\sqrt{\mathrm{3}}·n^{\mathrm{2}}·a^{\mathrm{2}}}=\frac{\mathrm{2}+\mathrm{6}{n}^{\mathrm{2}}+\mathrm{6}n}{\mathrm{3}\sqrt{\mathrm{3}}·n^{\mathrm{2}}·a^{\mathrm{2}}}.\end{array}$$

(26)

Because the whole test area is a fixed circular domain, as expressed in (25) and illustrated in Figure 10, the localization coverage increases with growing anchor number, as shown in Figure 11(a). When the number of anchor increases to 91, the location area constitutes 82.699 percent of the test area. Figure 11(b) graphs the beacon density for varying the quantity of anchors under the condition of $a=50$ which is the same as assigned in Section 5.1. We see that the beacon density falls sharply with increasing anchor number, until it reaches a density. We refer to this density as the saturation beacon density. The saturation beacon density can be obtained when the value of n approaches to infinity. If $a=50$ , the saturation beacon density will be $4.6188e-004$ . We can reach the same conclusion in Figure 11(b):

$$\begin{array}{cc}& \underset{n\to \infty }{\lim }\hspace{0.17em}{P}_d=\underset{n\to \infty }{\lim }\frac{\mathrm{2}+\mathrm{6}{n}^{\mathrm{2}}+\mathrm{6}n}{\mathrm{3}\sqrt{\mathrm{3}}·n^{\mathrm{2}}·a^{\mathrm{2}}}=\frac{\mathrm{2}}{\sqrt{\mathrm{3}}·a^{\mathrm{2}}}.\end{array}$$

(27)

Figure 11

(a) The number of anchors versus localization coverage; (b) the number of anchors versus beacon density.

5.3. Comparisons

We compare the LETLA with the weighted centroid [33], the sequence based [36], the Voronoi diagrams [43], and the multilateration [58]. In order to study the performances of localization precision and energy consumption in different scenarios, NS2 is adopted in Table 6.

Table 6

The simulation parameters of NS2.

Parameter	Value
Channel bandwidth (kbps)	250
Frequency (GHz)	2.4
Wireless model	Shadowing
MAC protocol	IEEE 802.15.4
Power for transmission (Watt)	0.28183815
Power for idle (Watt)	0.003587
Power for reception (Watt)	0.2182837
RX thresh (Watt)	$1.35685e-11$
RF radius (m)	50
Initial energy (J)	10

The anchors were deployed uniformly in a square field of $1000\hspace{0.17em}\text{m}\times 1000\hspace{0.17em}\text{m}$ , and 1000 testing positions were selected to place the unknown node. The testing positions were evenly distributed across the $1000\hspace{0.17em}\text{m}\times 1000\hspace{0.17em}\text{m}$ . The localization error was obtained by averaging the ten testing values of repeated measurements in each testing position. The anchors placements of the five location algorithms followed the geometric structure as Figure 4. To cover the square field of $1000\hspace{0.17em}\text{m}\times 1000\hspace{0.17em}\text{m}$ , a portion of anchors were moved to the corners. In the experiments, we consider RSS as the range-measurement:

$$\begin{array}{cc}& P_R\left(d\right)=P_T-PL\left(d_{\mathrm{0}}\right)-\mathrm{10}\eta \hspace{0.17em}\text{lo}{\text{g}}_{\mathrm{10}}\frac{d}{d_{\mathrm{0}}-X_{\sigma }}.\end{array}$$

(28)

The most widely used simulation model is the log-normal shadowing model [59], where $P_R$ is the received signal power, $P_T$ is the transmit power, and $P_L(d_0)$ is the path loss for a reference distance of $d_0$ . η is the path loss exponent, and the random variation $X_{\sigma }$ in RSS is generated according to Gaussian distribution with mean 0 and variance ${\sigma }^2$ . In this model, we do not provision separately for any obstructions like walls. In order to compare the performance in energy consumption, we consider that a second in localization computing will consume $8.052518e-5J$ . This value is obtained by dividing power for transmission into 3500. We modify the MAC layer of WPAN protocol in NS2 2.27 to realize the calculation of the energy consumption.

In Figure 12(a) the relationship between the localization error and the variance of noise is investigated when the number of anchors is 36. The result shows that the localization error increases with the variance of noise. We can observe that the performance of the multilateration is the best when the variance is less than six. As the variance increases, the LETLA is more robust than the other four algorithms under the same condition. Some of the reasons for this result can be briefly stated. The multilateration will obtain more precise coordinates if the variance becomes smaller. But its performance rapidly degrades when the effect of noise increases. As a result, the circles do not intersect at a common point and the precise coordinates degenerate into the approximate coordinates. The sequence based rises faster than the weighted centroid, the Voronoi diagrams, and the LETLA, since it needs a lot of iterative computations which are sensitive to the initial value. The weighted centroid and the Voronoi diagrams rise gently, but they are less accurate than the LETLA, because they have not fully utilized the information of the anchor placement.

Figure 12

(a) The relationship between the localization error and the variance of noise; (b) the relationship between the localization error and the number of anchors.

In Figure 12(b), the localization error decreases with the increment of anchors, when the variance of noise is ten. As the number of anchors increases, the density of anchors also grows in the fixed cover area. For this reason the received signal power is enhanced with the decrement of the distances between the anchors and the unknown node. As shown in Figure 12(b), the sequence based, the LETLA, and the Voronoi diagrams descend in steps. The reason is that a few increments of the number of anchors are not sufficient to change the density obviously. Only some degrees of promotion can alter the density adequately and improve precision effectually. It is also interesting to note that the Multilateration is the best when the number of anchors less than 32. However, as anchors began to accumulate, the LETLA, the Voronoi diagrams, and the multilateration are of about the same accuracy.

Figure 13 presents the energy consumptions of five algorithms when the variance of noise is ten. Under the same condition, the multilateration consumes more energy than the other four methods. The multilateration with noisy data as described above is based on solving nonlinear equations with complicated closed-form solutions. However, standard algorithms that provide least-square solutions for large numbers of nonlinear equations have a very high computational cost.

Figure 13

The energy consumption in the localization calculation versus the number of anchors.

In Figure 13 the tendency of the weighted centroid, the sequence based, and the Voronoi diagrams rise with the number of anchors and the energy consumptions of these three methods are less than the multilateration but more than the LETLA. By studying the References [33, 36, 43], we can find some reasons. The Voronoi diagrams spend most of the computing energy in constructing Voronoi diagrams and carrying out iterative computations [43]. The sequence based consumes too many energy in the generalization of location sequence tables and the calculation of the Spearman's Rank Order Correlation Coefficient and the Kendall's Tau [36]. The weighted centroid does not contain iterative computation, so it is simpler than sequence based and Voronoi diagrams. However, the Weighted Centroid has more energy consumption for solving the constrained extremum problems [33].

On the other hand, the energy consumption of the LETLA is the least of all. As mentioned in Section 4, the LETLA only solves binary linear equations, except matching and sorting in a limited range, and does not contain any iterative computations, statistical equilibrium, and multivariate nonlinear equations. It is worthwhile to note that, the energy consumption of the LETLA is stable. There are two reasons. First, only two of the nine ranging results and the coordinates of anchors are used to construct and solve the binary linear equations. It means that the scale of the calculation of the LETLA is fixed and limited. Second, the matching and sorting operations can be implemented with the special data structure, like index point, which trades time for space. In contrast with the weighted Centroid, the sequence based, the Voronoi diagrams, and the multilateration, the results suggest that the LETLA is more energy efficient with the same localization accuracy.

6. Conclusion

In this paper, we presented a novel lightness equilateral triangle localization algorithm (LETLA). In the LETLA, the approximate coordinates were substituted for the real coordinates of the unknown node and an optimization problem was set up to minimize the approximate error. To solve this optimization problem, we proposed a new geometric structure called “equilateral triangle diagrams.” In detail, we probed into the scalability of equilateral triangle diagrams and presented the geometrical characteristic of equilateral triangle diagrams. In the process of substituting the tangent for the arc, we derived that the midpoint of the arc was the most appropriate position of the point of the tangent.

Finally, the performance of the LETLA is much better than those of the other localization techniques, and experimental results indicate that the energy consumption of the LETLA is less than other location algorithm, at the same degree of location precision. As part of future work, we would focus on the implementation of the LETLA in the practical hardware of sensor nodes, such as MicaZ, Mica2, and Telos.