Range-Free Localization Scheme in Wireless Sensor Networks Based on Bilateration

Abstract

A low-cost yet effective localization scheme for wireless sensor networks (WSNs) is presented in this study. The proposed scheme uses only two anchor nodes and uses bilateration to estimate the coordinates of unknown nodes. Many localization algorithms for WSNs require the installation of extra components, such as a GPS, ultrasonic transceiver, and unidirectional antenna, to sensors. The proposed localization scheme is range-free (i.e., not demanding any extra devices for the sensors). In this scheme, two anchor nodes are installed at the bottom-left corner (Sink X) and the bottom-right corner (Sink Y) of a square monitored region of the WSN. Sensors are identified with the same minimum hop counts pair to Sink X and Sink Y to form a zone, and the estimated location of each unknown sensor is adjusted according to its relative position in the zone. This study compares the proposed scheme with the well-known DV-Hop method. Simulation results show that the proposed scheme outperforms the DV-Hop method in localization accuracy, communication cost, and computational complexity.

1. Introduction

Wireless sensor networks (WSNs) have gained worldwide attention in recent years. A WSN consists of spatially distributed autonomous sensors that cooperatively monitor a deployed region for physical or environmental conditions, such as temperature, sound, vibration, pressure, motion, and pollutants.

The manufacturing of small and energy efficient sensors has become technically and economically feasible because of recent advances in microelectromechanical systems (MEMSs) technology. A sensor node can sense, measure, and gather information from the environment and, based on some local decision process, transmit the sensed data to sinks (or base stations) through a wireless medium.

The transmission power consumed by a wireless radio is proportional to the distance squared or even a higher order in the presence of obstacles. Thus, multihop routing is usually considered for sending collected data to the sink instead of direct communication. Most WSN routing algorithms require the position information of sensor nodes. However, for some hazardous sensing environments, it is difficult to deploy the sensor nodes to the required locations. Thus, for environments in which it is difficult to plan the location of sensors in advance, localization techniques can be used to estimate sensor positions. The simplest and most common localization technique is to install a GPS receiver on each sensor in the sensor networks. Although the cost of GPS receivers is falling, they are still too costly, in price and energy consumption, to install in a sensor network.

This study proposes a low-cost yet effective WSN localization scheme. This scheme needs only two anchor nodes and uses low-complexity operations to estimate the location of unknown nodes. This study also compares the performance of the proposed scheme with the DV-Hop [1] method to show its superiority.

The rest of this paper is organized as follows. Section 2 reviews related research on WSN localization algorithms. Section 3 presents the communication protocol used to divide the deployed region into zones and the preliminary localization method. Section 4 introduces the more accurate enhanced method to estimate the positions of the unknown sensor nodes. Section 5 provides a simulation of the proposed localization scheme and a comparison of its performance with the DV-Hop method. Finally, Section 6 offers a conclusion.

2. Related Work

Research interest in WSN localization has increased greatly in recent years. Traditional WSN localization technologies can be divided into two categories: range-based methods and range-free methods [2]. A range-based method positions the sensor nodes using additional devices, such as timers, signal strength receivers, directional antennas, and antenna arrays. In contrast, a range-free method requires no additional hardware and instead uses the properties of the wireless sensor network and the appropriate algorithms to obtain location information.

Range-based localization relies on the availability of point-to-point distance or angle information. The distance/angle information can be obtained by measuring time of arrival (ToA) [3], time difference of arrival (TDoA) [4], received signal strength indicator (RSSI) [4], and angle of arrival (AoA) [5]. Range-based localization may produce fine-grained resolution but places strict requirements on signal measurements and time synchronization.

Range-free localization requires no distance or angle measurements among nodes. This technique can be further divided into two categories: local techniques and hop-counting techniques [2].

In the local techniques, a node with unknown coordinates collects the position information of its neighbor beacon nodes with known coordinates to estimate its own coordinate. In the simple centroid algorithm proposed in [6], each sensor estimates its position as the centroid of the locations of the neighboring beacons. A density-adaptive algorithm can reduce the number of computation errors if beacons are well positioned [7]. However, this is unfeasible for ad hoc deployment. Later, He et al. proposed the APIT method [8], which divides the environment into triangular regions between beacon nodes. Each sensor determines its relative position based on the triangles and estimates its own location as the center of gravity of the intersection of all the triangles that the node may reside in. However, APIT requires long-range beacon stations and expensive high-power transmitters.

A hop-counting technique, called DV-Hop method, was proposed by Niculescu and Nath in [1]. In the DV-Hop method, each unknown node asks its neighboring beacon nodes to provide their estimated hop sizes and then attempts to obtain the smallest hop count to its neighbor beacon nodes using the designated routing protocol. Each unknown node estimates the distances to its neighbor beacon nodes by the hop counts to them and the hop size of the closest beacon node. The unknown nodes then apply trilateration to estimate their position based on the estimated distances to three suitable neighbor beacon nodes.

There are many followup studies of the DV-Hop method. The authors of [9] proposed the DV-Loc method, which shows how Voronoi diagrams can be used efficiently to scale a DV-Hop algorithm while maintaining or reducing the DV-Hop localization error. The main concept of the DV-Loc method is to use a Voronoi diagram to limit the scope of the flooding in a DV-Hop localization system. DV-Loc is a scalable solution that uses the Voronoi cell of a node to limit the region that is flooded when computing its position to reduce its localization error.

The authors of [10] proposed a range-free localization algorithm that uses expected hop progress to predict the location of WSN sensors. The algorithm is based on an analysis of hop progress in a WSN with randomly deployed sensors and arbitrary node density. By deriving the expected hop progress from a network model for WSNs regarding network parameters, this system can compute the distance between any pair of sensors.

Traditionally, hop counts between any pair of nodes can only take an integer value, regardless of the relative positions of nodes in the hop. The authors of [11] argued that partitioning a node's one-hop neighbor set into three disjoint subsets according to their hop-count values can transform the integer hop count into a real number. The transformed real number hop count is then a more accurate representation of a node's relative position than an integer-valued hop count. In that paper, the author presented an algorithm termed HCQ (hop-count quantization) to perform this transformation.

Bilateration [12, 13], which is derived from multilateration, is based on the distance differences from an unknown node to two beacons at known locations. Unlike multilateration, which usually uses an iterative method to estimate the location of an unknown node, bilateration uses a basic geometry property, the intersection of two circles, to calculate the location of an unknown node. The computation of bilateration is much simpler than that of multilateration, which usually applies more expensive computation such as the least squares method. The disadvantage of bilateration is that the error rate is sensitive to the distance estimation to the beacon nodes.

In [12], Cota-Ruiz et al. presented a distributed and formula-based bilateration algorithm that can be used to provide an initial set of locations. In their scheme, each node uses distance estimates to beacons to solve a set of circle-circle intersection (CCI) problems, solved through a purely geometric formulation. The resulting CCIs are processed to pick those that cluster together, and the average is then used to estimate an initial node location. A similar bilateration algorithm was also proposed by the authors in [13] independently.

3. Zone-Based Localization Scheme

As mentioned in Section 1, some WSNs encounter difficulty in planning the location of sensors in advance. However, most routing algorithms require the information of sensor location. This section presents the proposed localization scheme to estimate the location of sensors. The following section extends the scheme to obtain a more accurate estimation of sensor locations.

The basic communication protocol used in the proposed scheme is flooding, which is a simple and effective mechanism for sending messages between sinks and sensor nodes. Flooding guarantees that sinks can reach any target node as long as the network is connective. In this scheme, the flooding mechanism serves as the initial routing step to acquire the minimum hop count to each sink for each sensor.

3.1. Localization Scheme

In the proposed localization scheme, called the zone-based localization method (ZBLM), two sink nodes are installed at the lower-left corner (Sink $\hspace{0.17em}\hspace{0.17em}X$ ) and the lower-right corner (Sink $\hspace{0.17em}\hspace{0.17em}Y$ ) of a square monitored region (Figure 1). This scheme assumes that (1) all the sensors are homogeneous, (3) they are uniformly deployed, and (3) the network is connective.

Figure 1

A scenario of 300 sensors with a communication range of 20 m, with the monitored region (200 × 200 m²) divided into zones. The colored irregular arcs are added to facilitate visualization of the zones.

The ZBLM consists of three major steps: compute minimum hop counts, divide the monitored region into zones, and assign the coordinate of sensors for each zone.

Step $\mathrm{1}$ (Compute Minimum Hop Counts). First, we allow both Sink X and Sink Y to broadcast a hop-counting packet (HC packet in short) to their neighbor sensors. The HC packet contains two fields: (1) Min_hc (minimum hop count to the source node), initialized to 0 and (2) the source node ID (0 for Sink X and 1 for Sink Y).

Each sensor records two current minimum hop count values (say, $X_{\text{hop}}$   and $Y_{\text{hop}}$ ) to Sink X and Sink Y, respectively, which are both set to positive infinity initially. Once a sensor receives an HC packet, it checks the hop count field Min_hc in the HC packet. If Min_hc + 1 is smaller than its corresponding current minimum hop count value $X_{\text{hop}}$ (or $Y_{\text{hop}}$ ), then it increases Min_hc by one before forwarding the packet to its neighbors and updates its $X_{\text{hop}}$ (or $Y_{\text{hop}}$ ) to the new Min_hc value accordingly. Otherwise, the sensor discards the current incoming HC packet.

Step 2 (Divide the Monitored Region into Zones). After finishing the flooding of HC packets by Step 1, each sensor should have two minimum hop-count values ( $X_{\text{hop}},Y_{\text{hop}}$ ) for Sink X and Sink Y, respectively. Sensors with the same ( $X_{\text{hop}},Y_{\text{hop}}$ ) pair are in the same zone (note that the following subsection claims that the zone tends to be a geometry quadrilateral), and it is denoted as zone ( $X_{\text{hop}},Y_{\text{hop}}$ ). Figure 1 shows a scenario of dividing the monitored region into zones, in which the color irregular arcs are added for ease of visualization. In this figure, each node has its own ( $X_{\text{hop}},Y_{\text{hop}}$ ) pair. For example, $X_{\text{hop}}$ of Node A is 3 and $X_{\text{hop}}$ is 8. Therefore, Node A is in zone (3, 8). Similarly, Node B is in zone (6, 5), and Node C is in zone (5, 7).

Step 3 (Assign the Coordinate of Sensors for Each Zone). Although we have the hop counts of each sensor and, therefore, know which zone a sensor belongs to, this information is still insufficient for identifying the location of a given sensor. As shown in Figure 1, the distance of each hop is not necessarily the same, and thus the band width corresponding to a hop is not necessarily equal to the communication range. The next subsection analyzes the range of the distance to the sinks for a given sensor node with its minimum hop count values and gives the estimated distance to the sinks. The current subsection assumes that we already have the estimated distances to Sink X and Sink Y for each node.

Suppose that the coordinates of Sink X and Sink Y are (0,0) and ( $w,0$ ), respectively, where w is the length of the square monitored region. Denote the distances from an unknown sensor S to Sink X and to Sink Y as $d_x$ and $d_y$ , respectively. The coordinate ( $x,y$ ) of Sensor S is the intersection of two circles centered at (0,0) and ( $w,0$ ), respectively. Therefore, ( $x,y$ ) can be obtained using the following equations:

$$\begin{array}{cc}& {\left(x-\mathrm{0}\right)}^{\mathrm{2}}+{\left(y-\mathrm{0}\right)}^{\mathrm{2}}=d_x^{\mathrm{2}},\\ {\left(x-w\right)}^{\mathrm{2}}+{\left(y-\mathrm{0}\right)}^{\mathrm{2}}=d_y^{\mathrm{2}}.\end{array}$$

(1)

Thus, $x=(d_x^{\mathrm{2}}-d_y^{\mathrm{2}}+w^{\mathrm{2}})/\mathrm{2}w$ and $y=\pm \sqrt{d_x^{\mathrm{2}}-x^{\mathrm{2}}}$ .

Because sinks are installed at the lower left and lower right corners of the monitored region, we can only take the positive solution of y. Therefore, the coordinate of the unknown sensor S is

$$\begin{array}{cc}& \left(\frac{d_x^{\mathrm{2}}-d_y^{\mathrm{2}}+w^{\mathrm{2}}}{\mathrm{2}w},\sqrt{d_x^{\mathrm{2}}-{\left(\frac{d_x^{\mathrm{2}}-d_y^{\mathrm{2}}+w^{\mathrm{2}}}{\mathrm{2}w}\right)}^{\mathrm{2}}}\right).\end{array}$$

(2)

For (1) to produce a real solution, the sum of $d_x$ and $d_y$ (the radii of two circles) must be greater than or equal to w (the distance between two centers). This constraint is considered when estimating the distances $d_x$ and $d_y$ .

3.2. Estimate the Hop Distances between Sensors and the Sinks

At first, we claim that sensors with the same ( $X_{\text{hop}},Y_{\text{hop}}$ ) pair tend to congregate in a quadrilateral.

Suppose the length of the square monitored region is m, the communication range of each sensor is CR, and the total number of nodes is n. The probability that a node v is within the communication range of another given node u is $(\pi \times \text{C}{\text{R}}^{\mathrm{2}})/m^2$ . Since the total number of nodes is n, the expected number of neighbor nodes, say ρ, for u is $(n-\mathrm{1})((\pi \times \text{C}{\text{R}}^{\mathrm{2}})/m^2)$ . For example, if $m=200$ , $\text{CR}=30$ , and $n=300$ , then $\rho =(\mathrm{300}-\mathrm{1})\times ((3.14\times {30}^2)/{200}^2)\cong 21$ . Previous research [14] provided a more precise estimation of node degree that considers the border effect. According to [14], $\rho =(n-\mathrm{1})(\pi r^2-(8/3{)r}^3+((11/3)-\pi )r^4)$ , where $r=(\text{CR}/m)$ . Therefore, $\rho \cong \mathrm{19}$ for this case.

According to [15], message forwarding between any two nodes through flooding occurs along the straight-line path with a probability greater than 0.85 if the number of neighbor nodes is greater than or equal to 15. According to the previous paragraph, if $\text{CR}=20$ , then ρ is greater than 15 as long as $n>478$ . Alternatively, if $\text{CR}=30$ , then ρ is greater than 15 as long as $n>213$ . Thus, if both the forwarding paths from Sink X and Sink Y progress along straight lines, then the sensors with the same ( $X_{\text{hop}},Y_{\text{hop}}$ ) pair tend to congregate and form a quadrilateral (called a “zone” in this paper). The experiment in this study shows that the “zone effect” still exists for the case $\text{CR}=20$ and $n=300$ ( $\rho \cong \mathrm{9}$ ) (Figure 1).

The following discussion presents two extreme cases in which the message is forwarded along the straight line. The hop distance between sensors is related to the communication range and the density of the sensors in the region [14, 15]. For high density, each sensor has a certain number of sensors within its communication range. Therefore, for Sink X (or Sink Y), it is highly possible that sensors are located at the edge of the communication range. For the extreme case shown in Figure 2, sensor nodes always exist at the edge of the communication range of each hop from the sink. Therefore, assuming that the communication range is CR, the maximum distance of a sensor with hop count n from the sink is $n\times \text{CR}$ .

Figure 2

A scenario of maximum distance to the sink: sensor nodes are located at the edge of the communication range. Thus, the maximum distance of sensors from the sink with hop count n is $n\times \text{CR}$ , where CR is the communication range.

The other extreme case occurs when the density of sensor nodes in the region is low and each sensor node has few neighbors, yet the network remains connective. As Figure 3 shows, sensor nodes are two in a group located close to the edge of the communication range. The first node in each group is within the communication range of the second node of the previous group, but immediately beyond the communication range of the first node of the previous group. Meanwhile, the second node in each group is immediately beyond the communication range of the second node of the previous group.

Figure 3

A scenario of minimum distance to the sink: sensor nodes are two in a group located close to the edge of the communication range.

For example, in Figure 3, Node C is within the communication range of Node B but immediately beyond the communication range of Node A. Node D is immediately beyond the communication range of Node B. Thus, the minimum distance of sensors with hop count n is $\lfloor n/2\rfloor \times \text{CR}+ϵ$ , where ϵ is the distance between the two nodes in the same group. For example, the hop count of Node C is 4, the distance to the sink is $\mathrm{2}\times \text{CR}+ϵ$ , the hop count of Node D is 5, and the distance is $\mathrm{2}\times \text{CR}+ϵ\prime$ , where $ϵ\prime$ is a value larger than ϵ. If the two nodes of each group are very close to each other yet still satisfy these conditions, then we can ignore the small value ϵ and say that the minimum distance of sensors with hop count n is $\lfloor n/2\rfloor \times \text{CR}$ .

This analysis indicates that if the messages are forwarded along a straight line, the distance to the sink for any sensor with hop count n is between $\lfloor n/2\rfloor \times \text{CR}$ and $n\times \text{CR}$ (ϵ is ignored). Therefore, if a sensor S is located in zone ( $m,n$ ) (i.e., it has minimum hop count values ( $m,n$ ) to Sink X and Sink Y), then we can use the following formula to approximate the distances, $d_x$ and $d_y$ , of sensor S to Sink X and Sink Y, respectively,

$$\begin{array}{cc}& d_x=\left\{\lfloor \frac{m}{\mathrm{2}}\rfloor +\left[\left(m-\lfloor \frac{m}{\mathrm{2}}\rfloor \right)*{\alpha }_{\mathrm{1}}\right]\right\}*\text{CR},\\ d_y=\left\{\lfloor \frac{n}{\mathrm{2}}\rfloor +\left[\left(n-\lfloor \frac{n}{\mathrm{2}}\rfloor \right)*{\alpha }_{\mathrm{2}}\right]\right\}*\text{CR},\end{array}$$

(3)

where ${\alpha }_1$ and ${\alpha }_2$ are parameters between 0 and 1. For simplicity, this study uses the same value of α for both ${\alpha }_1$ and ${\alpha }_2$ . To have a real solution for formula (1), it is necessary to rule out the α values that cause $d_x+d_y<w$ . Section 5 shows that the value of α is related to the communication range and the density of the sensors and identifies the best α value that minimizes the location error of ZBLM for each condition in a WSN.

4. Enhanced Zone-Based Localization Method

The last section presents a localization scheme to estimate the positions of unknown sensors and prove that the sensors with the same hop-count pair tend to be clustered in the same zone. Sensors in the same zone have the same estimated coordinates. This can cause a certain amount of estimation error, unless these sensors are located at the same place, and the error increases as the area of each zone increases.

For convenience, this study calls the coordinate of a sensor obtained using the ZBLM scheme the ZBLM coordinate. This section proposes an adjustment algorithm, called the enhanced zone-based localization method (EZBLM), to reduce the estimation error. The basic concept of this algorithm is to determine the possible location of a sensor in the zone where it belongs and adjust the coordinate of the given sensor by the ZBLM coordinates of its relevant neighbor zones.

In a monitored region, each zone generally has eight neighbor zones, except for the boundary zones, which may have less neighbor zones (Figure 4). The following paragraphs detail how to determine which neighbor zones are closer to a given sensor in a zone, and how to adjust the coordinate.

Figure 4

A scenario after broadcasting step. Sensor No. 5 is located at the southwest corner.

Step 1. Each sensor uses half the communication range to broadcast a message that contains its ID, its hop-count pair to Sink X and Sink Y, and its ZBLM coordinate. (According to our simulation, the outcome of broadcasting using a half communication range is better than that of the full communication range, especially for sensors in the boundary zones.) Figure 4 shows a scenario after the broadcasting step. The blue sensors are within a half communication range of Sensor No. 5, indicating that Sensor No. 5 is close to its southwest neighbor zones.

Step 2. Each sensor that receives messages from neighbor nodes adjusts its coordinate according to the following steps.

• (a)

Extract the ZBLM coordinate from each received message, and consider the extracted coordinates (remove the duplicates) as a set of points S. Compute the centroid, say ( $x_c,y_c$ ), of the points in S (i.e., take the arithmetic mean of all the points).

(b)

Suppose the ZBLM coordinate of the sensor to be adjusted is ( $x_u,y_u$ ). The adjusted coordinate is set to the center of the two coordinates (i.e., ${(x}_c+x_u)/2,(y_c+y_u)/2$ ).

The next section provides a comparison of the error rate of the coordinates obtained using both ZBLM and EZBLM, showing that EZBLM significantly improves the error rate of ZBLM.

5. Performance Analysis and Simulation Results

This section first identifies the values of α by experiments and suggests the best choice of the α value for each condition. We then compare two performance metrics, communication overhead, and computation overhead, for algorithms of the ZBLM, EZBLM, and DV-Hop. Finally, we simulate the three methods separately and compare their localization performance, including the location error and range error. The location error and range error are defined as follows.

$$\begin{array}{cc}& \text{Location}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{error}=\sqrt{{\left(X_{\text{real}}-X_{\text{est}}\right)}^{\mathrm{2}}+{\left(Y_{\text{real}}-Y_{\text{est}}\right)}^{\mathrm{2}}},\\ \text{range}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{error}=\frac{\text{location}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{error}\mathrm{\hspace{0.17em}\hspace{0.17em}}}{\text{CR}},\end{array}$$

(4)

where ( $X_{\text{real}},Y_{\text{real}}$ ) and ( $X_{\text{est}},Y_{\text{est}}$ ) are real coordinates and estimated coordinates, respectively, of a given unknown sensor. CR is the communication range.

5.1. Determine the Value of α

The term α is a parameter used to estimate the hop distance for each sensor to the sinks using (3). The value of α represents the ratio of the estimated hop distance to the communication range and depends on the values of the communication range and the node density. However, as far as we know, no formula can calculate the exact value of α. Therefore, this study determines the value of α through experiments. The value of α is tested from 0.05 to 1.0 in 0.05 intervals. Each value of α is used to compute the location error of the ZBLM for each deployment. Table 1 lists the best $\alpha$ value that generates the least location error for each combination of communication range and node density over 500 different deployments.

Table 1

The best α value for different node densities and communication ranges.

		Number of sensors (node density)
Communication range (meters)
		300 (0.0075)	400 (0.01)	500 (0.0125)	500 (0.015)	600 (0.0175)	800 (0.02)	900 (0.0225)	1000 (0.025)
20	α Values of least location error	0.45	0.5	0.55	0.6	0.65	0.65	0.7	0.7
30		0.6	0.65	0.7	0.7	0.7	0.7	0.75	0.75
40		0.65	0.7	0.7	0.7	0.7	0.7	0.75	0.75
50		0.7	0.7	0.7	0.7	0.7	0.7	0.7	0.7
60		0.65	0.65	0.65	0.7	0.7	0.7	0.7	0.7

As Table 1 shows, most of the best α values lie between 0.6 and 0.75, except for the cases of low density (node number ≤500) and low communication range ( $\text{CR}=20$ ). The best α value increases in proportion to the node density under the same communication range. However, under the same node density, the best α value does not necessarily increase as the CR increases. This is because the proposed scheme uses an integral hop-count value, and the multiplication effect of the α value at a larger CR is more significant than that at a small CR. Therefore, larger α values for a larger CR may cause greater location error.

5.2. Performance Analysis

This section analyzes the performance of the proposed scheme in two respects. We first compare two performance metrics, communication overhead, and computation overhead, for algorithms of the ZBLM, EZBLM, and DV-Hop. We then simulate the three methods separately and compare their location errors and range errors.

According to the algorithm proposed in Section 3, the ZBLM individually needs two flooding operations from Sink X and Sink Y. The coordinate estimation simply computes the intersection of two circles, which takes constant time and uses basic arithmetic operations such as addition, multiplication, and the square root.

In addition to the flooding operations needed for the ZBLM, the EZBLM requires one broadcasting operation for each node to determine the position of each unknown node in its zone. The adjustment of coordinate uses two average operations, which takes constant time.

In the DV-Hop method (described in Section 2), each node (both beacon nodes and unknown nodes) needs one flooding operation to calculate the minimum hop counts to all other nodes and the hop size for each beacon node. Each beacon node needs one extra flooding to broadcast the hop size to all the unknown nodes. Therefore, this method requires (number of all nodes + number of beacon nodes) flooding operations. Each unknown node uses trilateration to estimate its location. The trilateration needs a variable number of iterations (from two to hundreds in our experiments) to converge to a point.

Both the ZBLM and EZBLM use only two anchor nodes. The simulations in [1] show that the DV-Hop method requires at least 20% of the sensors to be anchor nodes to obtain better results. Table 2 presents a performance comparison of these methods. The results show that the proposed methods outperform the DV-Hop method in communication cost, computational complexity, and the number of anchor nodes required.

Table 2

Performance comparison of the ZBLM, EZBLM, and DV-Hop (n is the total number of nodes).

Method	Communication cost	Computation cost (for each unknown node)	Number of anchor nodes
ZBLM	2 flooding operations	Constant	2
EZBLM	2 flooding operations + n broadcast operations	Constant	2
DV-Hop	(1 + 20%) × n flooding operations	A variable number of iterations for trilateration	20% × n

5.3. Simulation Experiments

The simulation environments in this study were established as follows. The monitored region measured $200\hspace{0.17em}\text{m}\times 200\hspace{0.17em}\text{m}$ . The number of sensors ranged from 300 to 1000, and the communication ranges are from 20 to 60 m. Sensors were uniformly deployed in the region. The α values were chosen from Table 1. Each simulation included 50 tests, with the mean serving as the final result. All the methods (ZBLM, EZBLM, and DV-Hop) were simulated using Matlab.

Figures 5 and 6 show the location errors and range errors of both the ZBLM and EZBLM, respectively, for different communication ranges and number of sensors. As expected, under the same communication range, the location error decreases as the sensor density increases for both the ZBLM and EZBLM. These simulation results show that the EZBLM improves the ZBLM scheme significantly.

Figure 5

Location errors under different communication ranges (20–60 m) and node densities for ZBLM and EZBLM.

Figure 6

Range errors under different communication ranges (20–60 m) and node densities for ZBLM and EZBLM.

For the simulation of the DV-Hop method, the rate of anchor nodes was set to 20% because its performance drops significantly when using less than 20% of anchor nodes [1]. Figure 7 shows that both the ZBLM and EZBLM outperform DV-Hop, except for the cases of $\text{CR}=20$ and node number less than 500, in which each node may have too few neighbors and thus reduce the measurement accuracy of the proposed scheme. Note that the proposed scheme uses only two anchor nodes, whereas the DV-Hop method uses 20% of sensors as anchor nodes. These simulation results show that the proposed methods are more accurate than the well-known DV-Hop method.

Figure 7

Range errors of the proposed methods (ZBLM and EZBLM) versus DV-Hop under different communication ranges.

6. Conclusions

Many studies have attempted to solve the range-free localization problems of WSNs. Most of them demand many anchor nodes and use the multilateration method, which requires complex computation and a variable number of iterations to estimate the location of sensors. This study proposes two range-free localization methods that use only two anchor nodes and apply the low-complexity bilateration method. Experimental results show that the range error of the EZBLM is less than 0.3 for all cases with a node density greater than 0.0075 (node number = 300 with 200*200 region) when $\text{CR}\ge 40$ . Almost all the simulation results for the proposed method are better than those of the DV-Hop method, which requires many anchor nodes and more complex computations.

This study identifies the best α value to estimate the hop distance under different combinations of communication ranges and node densities. We show that sensors with the same minimum hop count pairs to Sink X and Sink Y tend to form a zone. Therefore, in addition to using the preliminary coordinate estimation method, the ZBLM, for unknown sensors, we use the EZBLM to adjust the coordinates of unknown sensors based on the sensor locations in the zones to which they belong. Simulation results show that this adjustment significantly improves the location estimation performance for unknown sensors.

Although the proposed scheme uses a square monitoring region, the same algorithm can be applied to rectangular monitoring regions.