In wireless sensor networks (WSNs), location information plays an important role in many fundamental services which includes geographic routing, target tracking, location-based coverage, topology control, and others. One promising approach in sensor network localization is the determination of location based on hop counts. A critical priori of this approach that directly influences the accuracy of location estimation is the hop-distance relationship. However, most of the related works on the hop-distance relationship assume the unit-disk graph (UDG) model that is unrealistic in a practical scenario. In this paper, we formulate the hop-distance relationship for quasi-UDG model in WSNs where sensor nodes are randomly and independently deployed in a circular region based on a Poisson point process. Different from the UDG model, quasi-UDG model has the non-uniformity property for connectivity. We derive an approximated recursive expression for the probability of the hop count with a given geographic distance. The border effect and dependence problem are also taken into consideration. Furthermore, we give the expressions describing the distribution of distance with known hop counts for inner nodes and those suffered from the border effect where we discover the insignificance of the border effect. The analytical results are validated by simulations showing the accuracy of the employed approximation. Besides, we demonstrate the localization application of the formulated relationship and show the accuracy improvement in the WSN localization.

In recent years, wireless sensor networks (WSNs) which generally consist of a large number of small, inexpensive and energy efficient sensor nodes have become one of the most important and basic technologies for information access [1]. WSNs have been widely used in military, environment monitoring, medicine care, and transportation control. Spatial information is crucial for sensor data to be interpreted meaningfully in many domains such as environmental monitoring, smart building failure detection, and military target tracking. The location information of sensors also helps facilitate WSN operation such as routing to a geographic field of interests, measuring quality of coverage, and achieving traffic load balance. In many monitoring applications, the sensor nodes must be aware its location to explain 'what happens and where'.

While specialized localization devices exist such as GPS, given the large number of sensor nodes involved in building a single WSN, it is cost ineffective to equip every sensor node with such a sophisticated device. Therefore, seeking for an alternative localization technology in WSNs has become one major research in WSNs [2]. Over the past few years, many localization algorithms have been proposed to provide sensor localization [3]. These localization protocols can be divided into two categories: range-based and range-free. The former is defined by methods that use absolute point-to-point distance estimates (range) or angle estimates for computing locations. The latter makes no assumption about the availability or validity of such information. Recently, range-free localization methods have attracted much attention because no extra sophisticated device for distance measurement is needed for each sensor node. Despite the challenge in obtaining virtual coordinates purely based on radio connectivity information [4,5], attempts have been made in developing a practical solution to achieve localization. A few representative protocols of this range-free scheme include DV-Hop [6], APIT [7], DRLS [8], MDS-MAP [9], and LS-SOM [10]. Most of the range-free localization schemes, such as DV-Hop, need to compute the average distance per hop to estimate a node's location. In other words, the performance of these localization schemes relies on the accuracy of the employed hop-distance relationship. Since the determination of an accurate hop-distance relationship depends on various complex factors such as node deployment, node density, and wireless communication technology that cannot be easily quantified, the deduction process is tedious and unlikely to produce an exact close form relationship using, say the geometric methods [11].

Due to lack of any predetermined infrastructure and self-organized nature, in most cases, the sensor nodes are randomly and independently deployed in a bounded area. For simplicity, the vast majority of studies based on the idealized unit-disk graph (UDG) network model, where any two sensors can directly communicate with each other if and only if their geographic distance is smaller than a predetermined radio range. Examples of these research include geo-routing protocols [12,13], localization algorithms [8,14], and topology control techniques [15,16]. Similarly, most of the works related to the hop-distance relationship have been investigated assuming the UDG model [11,17–23]. The probability that two randomly selected stations with a known distance can communicate inK or less hops with omnidirectional antennas has been analyzed by Chandler [17]. Bettestetter and Eberspacher, derived the probability of the distance of two randomly chosen nodes deployed in a rectangular region within one or two hops [18]. However, when the hop counts are larger than two, only simulation results are available. The distribution parameters are computed by the iterative formula which extends from [19] with a linear formation. Ekici et al. [20] studied the probability of the k-hop distance in two dimensional network based on the approximated Gaussian distribution. Dulman et al. [11] derived the relationship between the number of hops separating two nodes and the physical distance between them in one- and two-dimensional topologies considering the UDG model. In the study, the approximated approach based on a Markov Chain in two-dimensional case is rather complicated to compute. Zhao and Liang [21] collected the hop-distance joint distribution from Monte Carlo simulations in a circular region and proposed an attenuated Gaussian approximation for the conditional probability distribution function (pdf) of the Euclidean distance given a known hop count. Ta et al. [22] provided a recursive equation for the two randomly located sensor nodes that arek-hop neighbors given a known distance in homogeneous wireless sensor networks. Ma et al. [23] proposed a method to compute the conditional probability that a destination node has hop-counth with respect to a source node given that the distance between the source and the destination isd.

Despite the current efforts, no fixed communication range exists in actual network environment for the reasons such as multi-path fading and antenna issues. Therefore, a certain level of deviation occurs between the intended operation and actual operation in wireless sensor networks when the UDG model is assumed in a protocol design. To deal with this problem, a practical model called the quasi Unit-disk Graph (quasi-UDG) model is proposed recently [24]. The quasi-UDG model can be characterized by two parameters, the radio rangeR and the quasi-UDG factorα. For any two nodes in the quasi-UDG model, if their distance is longer thanR, no direct communication link exists between the two. Otherwise, if their distance is betweenαR andR, a communication link exists with a probability ofp_l , andp_l = 1 when their distance is shorter thanαR. Given this newly proposed practical property of connectivity, it warrants an investigation of the hop-distance relationship with the quasi-UDG model for the range-free localization schemes to capture practical connectivity characteristics.

In this paper, we focus on exploiting the connectivity property of the quasi-UDG model and analyze the relationship between the hop counts separating two nodes and their geographic distance with a specific node density in a WSN. We seek approximation technique to provide a scalable solution for the two-dimensional case. We further demonstrate the application of the developed hop-distance relationship to a range-free localization scheme.

In our WSN setup, we consider that sensor nodes are deployed into a circular regionS_b with the radiusR_b , where the deployment position follows a Poisson point process with a certain densityλ. We set$p_l=\frac{\alpha }{1-\alpha }\left(\frac{R}{d}-1\right)$ such that a longer distance between two nodes has a lower probability to form a direct communication link. With this setup, we formulate the probability that a pair of nodes with a known distance resulting a particular hop count. Additionally, we also develop the probability that a pair of nodes with a known distance gives a particular hop count. Finally, in our analysis, we present a quantitative evaluation for the border effect of geographic distance distribution with a given hop count.

The rest of this paper is organized as follows. In Section 2, we present our analytical model deriving an approximate recursive formula for the hop-distance relationship considering the quasi-UDG model. Section 3 extends our analytical model by taking the border effect and dependence problem into consideration. Section 4 formulates the probability distribution of distance with known hop counts. In Section 5, we demonstrate the use of our developed hop-distance relationship by applying the relationship to a least squares (LS) based localization algorithm. Finally, we report results in Section 6 and draw important conclusions in Section 7.

In general, the hop-distance relationship is influenced by the density of sensor nodes and their deployment strategy, as well as the radio communication characteristics. Considering the more practical quasi-UDG model, it is recognized that the formulation for the hop-distance relationship with the consideration of quasi-UDG model is tedious and unlikely to produce an exact close form. We seek approximation using a recursive approach to derive an approximated hop-distance relationship. In this section, we focus on analyzing the probability that a particular pair of sensor nodes forms a certain hop count with a known distance.

Suppose thatN sensor nodes are deployed randomly in circular regionS_b with a radiusR_b . The number of nodes in any region is a Poisson random variable with an average node density of$\lambda =\frac{N}{S_b}=\frac{N}{\left(\pi R_b^2\right)}$. Assume that the communication range of a node isR, the communication model between any pair of nodes follows the quasi-UDG model with a factor ofα where 0< α < 1.

With the quasi-UDG model, the communication area between two nodes with the distanced can be further divided into three cases shown as follows.

• Ifd ≤αR, then the two nodes can communicate directly.

• IfαR < d ≤R, then the two nodes can communicate with a probabilityp_l, which is set to (R/d - 1)α/(1 -α). It means that a longer distance between two nodes has a lower probability to form a direct communication link.

• Ifd > R, then the two nodes cannot communicate directly.

The quasi-UDG model is illustrated with an example shown in Figure1. In the figure, we assume that there are two nodesu andv, their distance isd_uv , and their communication probability isP. Let Φ_h (d) be the probability that a particular pair of nodes withd distance apart ish hops away from each other. In the following, we shall first derive Φ_h (d) for the case ofh = 1 and thenh ≥ 2.

Quasi-UDG model.

Full size image

2.1 The case ofh= 1

For the case ofh = 1, owing to the quasi-UDG model, Φ₁ (d) is obviously

2.2 The case ofh≥ 2

We first note that two nodes, namedO₁ andO₂, have no direct link but may communicate throughh - 1 relay nodes. This gives rise to two possibilities, where

• O₂ is not them-hop neighbor ofO₁ ifm < h.

• Within the communication range ofO₂, there is a least one (h - 1)-hop neighbor ofO₁ that has a direct link withO₂.

Form < h, the probability,P_N , thatO₂ is not them-hop neighbor ofO₁ can be obtained as

We shall now consider the second possibility in the following. Considering two circles which one centered atO₁ having a radius ofr and the other centered atO₂ having a radius ofR. We denote the distance between the two centers asd and refer the common region of the two circles asS. The quantityP_r (S) is defined as the probability that in the areaS, there is no (h - 1)-hop neighbor ofO₁ that can communicate withO₂ directly. A differential increment ofdr onr can obtain a differential incremental region ofdS. Assume that the probability Φ_h(d) of any pair of nodes is independent and statistically identical, we haveP_r (S +dS) =P_r (S)P_r (dS). In the following subsections, we calculateP_r (dS) based on three conditions, which ared > R,$\frac{1+\alpha }{2}R<d<R$, and$\alpha R<d\frac{1+\alpha }{2}R$.

2.2.1O₁falls outside the communication range ofO₂whered>R

In Figure2, we see thatdS can be further divided into many differential regionsrdrdθ. Sincedr anddθ are infinitesimal, the probability that there exists more than one sensor node in the regionrdrdθ can be ignored, and the probability that a single sensor node located withinrdrdθ can be approximated asλrdrdθ.

Illustration ofdSwhend > Rfor the case that (a)dSlocates in$\mathcal{A}\left(O_2\right)$, and (b)dSlocates in$\mathcal{C}\left(O_2\right)$and$\mathcal{A}\left(O_2\right)$.

Full size image

We term the circular region centered inO₂ with the radiusαR as$\mathcal{C}\left(O_2\right)$, and the annulus region centered inO₂ with the larger radiusR and the smaller oneαR as$\mathcal{A}\left(O_2\right)$. There are two cases needed to be taken into consideration, which are

• WhendS falls into$\mathcal{A}\left(O_2\right)$ as shown in Figure2(a),r satisfiesd - R ≤ r ≤ d - αR ord +αR ≤ r ≤ d - R. With the definition of the quasi-UDG model, every differential regionrdrdθ ofdS has a corresponding probabilityp_lto communicate withO₂. Therefore,P_r(dS) is given by (3) where

  $$P_r\left(dS\right)=1-2{\Phi }_{h-1}\left(r\right)\lambda rdr\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta .$$

  (3)

As illustrated in Figure2(a), we can get the following relationship

• WhendS covers both$\mathcal{C}\left(O_2\right)$ and$\mathcal{A}\left(O_2\right)$,r will be bounded byd - αR ≤ r < d +αR. The partrdrdθ that falls within$\mathcal{C}\left(O_2\right)$ is surely a one-hop neighbor ofO₂. When that part falls within$\mathcal{A}\left(O_2\right)$, it has a corresponding probabilityp_lthat it has a direct link withO₂. ThenP_r(dS) can be determined by

  $$P_r\left(dS\right)=1-2{\Phi }_{h-1}\left(r\right)\lambda rdr\left[{\phi }_1+\underset{\phi 1}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right]$$

  (6)

and

2.2.2O₁falls within the communication range ofO₁and d satisfies$\frac{1+\alpha }{2}R<d<R$

We use the foregoing strategy for this derivation. We notice that there are three cases needed to be treated individually which are given as follows.

• If 0< r < R - d,dS will be the annulus region and the entire section ofdS will fall within$\mathcal{A}\left(O_2\right)$, which gives

  $$P_r\left(dS\right)=1-2{\Phi }_{h-1}\left(r\right)\lambda rdr\underset{0}{\overset{\pi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta$$

  (8)

• IfR-d ≤r < d-αR ord+αR ≤r <R+d,dS will not be the annulus region but the entire section ofdS will still fall within$\mathcal{A}\left(O_2\right)$. Then we can obtainP_r(dS) by (3).

• Ifd-αR ≤r < d+αR,dS will cover both$\mathcal{C}\left(O_2\right)$ and$\mathcal{A}\left(O_2\right)$. In this case, we can determineP_r(dS) by (6).

2.2.3O₁falls within the communication range ofO₂and d satisfies$\alpha R<d\frac{1+\alpha }{2}R$

There are four cases needed to be considered whenO₁ falls within the communication range ofO₂ andd satisfying the condition$\alpha R<d\frac{1+\alpha }{2}R$, which are

• If 0< r < d-αR,dS will be the annulus region and the entire section ofdS will fall within$\mathcal{C}\left(O_2\right)$. Then we can determineP_r(dS) by (8).

• Ifd-αR ≤r <R-d,dS will still be the annulus region but it covers both$\mathcal{C}\left(O_2\right)$ and$\mathcal{A}\left(O_2\right)$. Therefore, we have

  $$P_r\left(dS\right)=1-2{\Phi }_{h-1}\left(r\right)\lambda rdr\left[{\phi }_1+\underset{{\phi }_1}{\overset{\pi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right]$$

  (9)

• IfR-d ≤r <d+αR,dS will not be will the annulus region and it covers both$\mathcal{C}\left(O_2\right)$ and$\mathcal{A}\left(O_2\right)$. The probabilityP_r(dS) can be obtained by (6).

• Ifd+αR ≤r <R+d,dS will fall within the region$\mathcal{A}\left(O_2\right)$, and hence we can computeP_r(dS) by (3).

2.3 Determination of Φ_h(d) forh≥ 2

Consider thatP_r (dS) only depends onr with a specificd, we setP_r (dS) = 1 -g(r). FromP_r (S +dS) =P_r (S)P_r (dS), the expression ofP_r (S) can be obtained by the following linear differential equation where

Therefore, with (2) and (10), the probability Φ_h(d) withh ≥ 2 can be obtained as

where knowingd, Ω(d) can be determined by one of the following expressions, which are

• Ford > hR ord < αR :

  $$\Omega \left(d\right)=0;$$

  (12)

• ForR < d ≤ hR :

  $$\begin{array}{lll}\hfill \Omega \left(d\right)& ={\int }_{d-R}^{d-\alpha R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(1)}\\ +{\int }_{d-\alpha R}^{d+\alpha R}{\Phi }_{h-1}\left(r\right)r\left({\phi }_1+\underset{{\phi }_1}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right)dr& \hfill \text{(2)}\\ +{\int }_{d+\alpha R}^{d+R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(3)}\\ \hfill \text{(4)}\end{array}$$

  (13)

• For$\frac{1+\alpha }{2}R<d\le R$:

  $$\begin{array}{lll}\hfill \Omega \left(d\right)& ={\int }_0^{R-d}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\pi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(1)}\\ +{\int }_{R-d}^{d-\alpha R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(2)}\\ +{\int }_{d-\alpha R}^{d+\alpha R}{\Phi }_{h-1}\left(r\right)r\left({\phi }_1+\underset{{\phi }_1}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right)dr& \hfill \text{(3)}\\ +{\int }_{d+\alpha R}^{d+R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(4)}\\ \hfill \text{(5)}\end{array}$$

  (14)

• For$\alpha R<d\le \frac{1+\alpha }{2}R$:

  $$\begin{array}{lll}\hfill \Omega \left(d\right)& ={\int }_0^{d-\alpha R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\pi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr& \hfill \text{(1)}\\ +{\int }_{d-\alpha R}^{R-d}{\Phi }_{h-1}\left(r\right)r\left({\phi }_1+\underset{{\phi }_1}{\overset{\pi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right)dr& \hfill \text{(2)}\\ +{\int }_{d-\alpha R}^{d+\alpha R}{\Phi }_{h-1}\left(r\right)r\left({\phi }_1+\underset{{\phi }_1}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta \right)dr& \hfill \text{(3)}\\ +{\int }_{d+\alpha R}^{d+R}{\Phi }_{h-1}\left(r\right)r\underset{0}{\overset{\phi }{\int }}\frac{\alpha }{1-\alpha }\left(\frac{R}{l}-1\right)d\theta dr.& \hfill \text{(4)}\\ \hfill \text{(5)}\end{array}$$

  (15)

In the above analysis, we do not consider borders of a WSN. However, in a realistic scenario, the deployment area of WSNs is finite and hence borders exist. It is known that the probability Φ_h(d) derived assuming that both involved nodes are not near the border of a WSN may give a slightly different result when one or both of them fall near the border. This is known as the border effect. One common handling of the border effect is to consider the toroidal distance metric in the simulation experiment where a node closed to the border can communicate directly with some nodes at the opposite border [25]. While this special setup eliminates the border effect, it creates discrepancy between the study and practical setups which may lead to a certain level of errors.

Clearly, nodes which are closer to the border cover smaller regions than those at leastd away from the border, and therefore intuitively the quantity for Ω(d) should be smaller with the consideration of the border effect. Apparently, the border effect gives a different level of impacts in the measure of Φ_h(d) with a different distance between an involved node and the border. However, it is tedious to derive all cases considering the border effect. For simplicity, we take two key cases of the border effect into consideration. Assuming the center of deployment area isO, we consider two annulus near the border in the following.

• The first annulus, called${\mathcal{A}}_1\left(o\right)$, is between the circles with radius ofR_b-R andR_b-αR.

• The second annulus, called${\mathcal{A}}_2\left(o\right)$, is between the circles with radius ofR_b-R andR_b-αR.

We set an average metricζ(h) which varies from 0 to 1 for each hop to determine the decrement of Ω(d). For the circle area with the radiusR_b -R, which can be called$\mathcal{C}\left(o\right)$, we can setζ(h) = 1 accordingly.

Another factor we have to consider is the dependence. The hop-distance relationship derived as aforesaid relies on an implicit independence assumption, that is the probability Φ_h(d) of any pair of nodes is independent and statistically identical. However as pointed in [22], the events that those nodes with the direct link toO₂ areh - 1 hops away fromO₁ are not mutually independent for cases whenh > 2, and the calculation of Φ_h-1(r) should include appropriate dependence conditions. For example, as shown in Figure3, nodesO₁ andO₂ ared distance apart andh hops away from each other whereh = 3. The probability that nodeM₁ is a 2-hop neighbor of nodeO₁ is the probability that there is at least one node located in the areaS₁ offering packet relay between nodesO₁ andM₁. Here, the areaS₁ is the intersect area between the circles with the centersO₁ andM₁. Similarly, the probability that nodeM₂ is a 2-hop neighbor of nodeO₁ is the probability that there is at least one node located in the areaS₂ which can directly communicate with nodesO₁ andM₂. Here, the areaS₂ is the intersect area between the circles with the centersO₁ andM₂. It is obvious in the figure that the areasS₁ andS₂ share a common areaS₁₂ indicating that the calculated probabilities are not independent.

Illustration of multihop-dependence problem.

Full size image

To include the impact of the dependence, we add a new factor, namelyξ(h), into the expression of Ω(d). Both factorsζ(h) andξ(h) are added to allow Ω(d) to reflect a practical setup, and they can be estimated by statistical results via experiments. With the inclusion ofζ(h) andξ(h) into the expression ofω(h), (11) becomes

In this section, assume that sensor nodes are randomly deployed in a circular region, we derive equations to determine the probability density function of distanced with a known hop count$f_{\mathcal{H}}\left(d\right)$.

Theorem 4.1The probability density function for the distance d between two nodes randomly deployed ina circular region with the radius R_bis$f_{\mathcal{D}}\left(d\right)$,where

We provide the proof of Theorem 4.1 in Appendix A. According to Theorem 4.1, we can obtain the probability density function of distance between any two nodes in the areas$\mathcal{C}\left(o\right)$,${\mathcal{A}}_1\left(o\right)$, and${\mathcal{A}}_2\left(o\right)$. Their probability density functions of distance are$f_{{\mathcal{D}}_c}\left(d\right)$,$f_{{\mathcal{D}}_{{\mathcal{A}}_1}}\left(d\right)$, and$f_{{\mathcal{D}}_{{\mathcal{A}}_2}}\left(d\right)$, respectively. We also term them as$f_{\mathcal{D}*}\left(d\right)$, in general, where the symbol * is appropriately substituted by either${\mathcal{A}}_1$,${\mathcal{A}}_2$ or$\mathcal{C}$. Their expressions are given in (18), (19) and (20) in the following.

where Λ(R,r,d) is given by

By the Bayes' formula, given$f_{\mathcal{D}*}\left(d\right)$ and Φ_h(d), we can obtain the expression$f_{\mathcal{H}*}\left(d\right)$ which is the probability density function of the geographical distanced when the hop counth is known to beH*. This expression is determined by

wherer₀ = 0 whenh = 1, andr₀ =αR whenh > 1.

With the development of the hop-distance relationship for the quasi-UDG model, in this section, we show the application of this new relationship to a particular localization algorithm using LS based localization algorithms [26], and we call this newly designed localization algorithm enhance weighted least squares (EWLS).

In a particular localization scenario in WSNs, we assume that there is a number of nodes whose locations are known, and they shall be called anchor nodes. Other nodes that have no knowledge of their locations are called unknown nodes. Consider that an unknown nodej can obtain the locationx_i, hoph_ji and average hop-distancec_i of an anchor nodei. The distance between nodesj andi can be calculated asd_ji =c_ih_ji . In our test scenario, we place an anchor nodeo in the center and add several other anchor nodes in the map.

We design a simple mechanism to compute the range of distanced_ji . Each anchor nodei collects some information to other anchor nodek, computes and ranks the average hop-distancec_i(k)=d_ik/h_ik, such asc_i(1)≥c_i(2)≥⋯ ≥c_i(n). We set the range of average hop-distance as

Following that, the range of distanced_ji can be computed as$d_{ji}^{\left(M\right)}={\bar{c}}_i\times h_{ji}$ and$d_{ji}^{\left(m\right)}={\underset{}{c}}_i\times h_{ji}$. With the range of distanced_ji , the variancev_h of the pdf$f_{\mathcal{H}}\left(d\right)$, we compute the weights,w_i , of measured distanced_ji as

Finally, we setW = diag(w₁,⋯,w_n ) and compute the location$\widehat{x}$ of an unknown node using the following results, where

and

In this section, we compare the analytical and statistical results through simulation experiments to illustrate the performance of our proposed hop-distance model. To illustrate the benefit of applying our model to LS-based localization algorithms, we compared our enhanced algorithm of EWLS to two classical LS-based localization algorithms namely LS [26] and PDM [27].

6.1 Impacts of boarder effects and dependence

We first illustrate the impacts of the boarder effect and dependence problem. In the experiments, we gather statistics of the hop counts with corresponding distance information using Monte Carlo simulations. All the simulation data are collected from several scenarios whereN sensor nodes are randomly deployed in a circular region of radiusR_b , and the transmission range is set toR with the consideration of the quasi-UDG model. The parameters are set toN = 400,R_b = 200,R = 50,α = 0.75, and the result comparisons are listed in Table1. Leto be the deployment center. The region where nodes are deployed away from the border is denoted as$\mathcal{C}\left(o\right)$, and we term${\mathcal{A}}_1\left(o\right)$ and${\mathcal{A}}_2\left(o\right)$ as the annulus regions in which the distances too are within (R_b-R, R_b-αR] and (R_b-αR, R_b ], respectively.

In Table1 we use cumulative absolute difference (CAD) to measure the sum of absolute differences between the analytical results and statistical data. We set$CAD={\sum }_d|{\Phi }_h\left(d\right)-Si{m}_h|$, where Φ_h(d) andSim_h are the probabilities of two nodes giving a hop count ofh with a known distance ofd obtained from the analysis and simulation, respectively. Moreover, we denote CAD* as the CAD measurement between analytical results without the border effect consideration and statistical data. For${\mathcal{A}}_1\left(o\right)$ and${\mathcal{A}}_2\left(o\right)$, we can see that the CAD* of each hop is larger than that ofCAD because of the impact of the border effect.

6.2 The validation of distribution of distance by a known hop count

We conduct simulation experiments withN = 400,R_b = 200,R = 50,α = 0.75 and present$f_{\mathcal{H}*}\left(d\right)$ in Figures4,5 and6 with the statistical data and our analytical results. In all three cases, we note that the numerical results of$f_{\mathcal{H}*}\left(d\right)$ given in (21) show excellent agreement with the simulation results. This excellent agreement confirms the accuracy of our model for the estimation of the distance given a known hop count between two sensor nodes.

The distribution$f_{{\mathcal{H}}_{\mathcal{C}}}\left(d\right)$ when the hop count falls between 1 and 8.

Full size image

The distribution$f_{{\mathcal{H}}_{{\mathcal{A}}_1}}\left(d\right)$.

Full size image

The distribution$f_{{\mathcal{H}}_{{\mathcal{A}}_2}}\left(d\right)$.

Full size image

6.3 Localization accuracy comparisons

In the following, we conduct several simulation experiments to illustrate the performance of our proposed EWLS algorithm. In the simulation,N = 100 sensor nodes are randomly deployed in the circle${\mathcal{S}}_b$ with the radiusR_b = 200. The number of anchor nodes is 16 and the communication range of each sensor node isR = 80. The factorα of the quasi-UDG model is set to 0.76. In Figure7(a), even within the communication rangeR of node 1, the nodes 30, 38, 53, and 63 cannot communicate directly with node 1 due to the considered quasi-UDG model. With the network topology illustrated in Figure7(a), we show the localization errors of EWLS, LS, and PDM in Figure7. Apparently, the accuracy of EWLS is higher than that of the two classical algorithms where the average localization errors of EWLS, LS, and PDM are 0.26702R, 0.29728R, and 0.28462R, respectively. This confirms that when WSNs exhibit the quasi-UDG connectivity behavior, our new hop-distance relationship that captures the behavior offers an improved accuracy in localization.

Localization error distributions on the quasi-UDG network topology.

Full size image

In the following, we further compare the localization accuracy among EWLS, LS and PDM under various scenarios. In these simulation experiments, we setN = 400, and sensor nodes are deployed uniformly in the circle area with the radiusR_b = 200. The connectivity of nodes follows the quasi-UDG model. The localization error is calculated as$\xi ={\sum }_j\parallel x_j-{\widehat{x}}_j\parallel /\left(N-n\right)$.

Firstly, we focus on the impact of the number of anchor nodes. The factorα of quasi-UDG model is set to 0.76 and the communication rangeR of each sensor node is set to 50. In Figure8, we can see that the localization errorξ of all three algorithms decreases with the increase of number of anchor nodes. Among them, our proposed EWLS always offers the best performance.

Effect on the average localization errorξof anchor fractionρ_a.

Full size image

Secondly, we investigate the impact of the parameterα of quasi-UDG model. In this scenario, we set the number of anchor nodes to 40 and the parameterα varies from 0.72 to 1. The localization error comparison is given in Figure9. We observe that when the parameterα increases, the number of neighbor nodes increases and the number of hops between an unknown node and an anchor node decreases. Thus, the localization error decreases, and our proposed EWLS algorithm remains the best among all for all consideredα values.

Effect on the average localization error of quasi-UDG factorα.

Full size image

Last we study the impact of the communication rangeR of each sensor node. We set the parameterα of quasi-UDG model to 0.76 and set the number of anchor nodes to 40. Similarly, we compare the localization errors in Figure10 with a range ofR values. We observe that because the number of neighbor nodes of a node increases when its communication range increases, and number of hops between an unknown node and an anchor decreases which leads to a decrease in localization errors. Comparing the results for all algorithms, our proposed EWLS outperforms its peers.

Effect on the average localization errorξof nodes' communication rangeR.

Full size image

The hop-distance relationship information can effectively improve the performance of the protocols for wireless sensor networks in many aspects. However, most studies focus on the UDG model which significantly deviates from the real world. In the paper, we presented an analytical modeling to formulate the hop-distance relationship considering the quasi-UDG model. Senor nodes are randomly distributed in a circular region according to a Poisson point process. The probability of a particular hop count given a known distance Ω_h(d) was studied, and the border effect and dependence problem was considered in our analysis. Precisely, we derived the probability density function of a random variable describing the distance between two arbitrary nodes with a given hop count. Simulation results confirmed that our analytical results gave excellent accuracy. From the results, we further illustrated impact of the border effect.

Furthermore, we demonstrated the application of our developed hop-distance relationship considering the quasi-UDG model in WSN localizations. We designed a LS-based localization algorithm using our developed relationship and compared its performance with other popular LS-based localization algorithms. We again confirmed that the explicit use of our developed relationship in the computation of localization algorithms improved the localization accuracy.

Suppose that a nodex(x,y) is randomly deployed in a circular region with the radiusR_b , the joint distributionf_x(x,y) can be obtained from

As the nodesx₁(x₁,y₁) andx₂(x₂,y₂) are selected independently, the joint pdf ofx₁ andx₂ is

We setx_d =x₁ -x₂ andx_m = (x₁ +x₂)/2. The joint distribution ofx_m andx_d can be obtained as

where the constraintsL₁ andL₂ are

We set the probability of the geographical distance$\mathcal{D}$ betweenx₁ andx₂ less thand to be$P\left(\mathcal{D}\le d\right)$, and the constraintL₃ can be expressed by$L_3:{\mathcal{D}}^2=x_d^2+y_d^2\le d^2$, then we have

WithL₁ ∩L₂, thenx_m falls into the intersectional region of two circles with centers (x_d/ 2,y_d/ 2) and (-x_d/ 2, -y_d/ 2). The intersectional area is

Since${f_x}_{d_{},x_m}\left(x_d,y_d,x_m,y_m\right)$ is constant, (29) can be rewritten as

Therefore, we have

where 0 <d < 2R_b .

The authors gratefully acknowledge the support of the Program of Introducing Talents of Discipline to Universities ("111 Project") under grant No. B08002, and the support of the National Natural Science Foundation of China (NSFC) under Grants No. 60802016, 60833002 and 60972010, the support by "the Fundamental Research Funds for the Central Universities" under grant No. 2009JBM007.

Authors and Affiliations

1. School of Electronics and Information Engineering, Beijing Jiaotong University, Beijing, 100044, PR China

   Deyun Gao & Yanchao Niu

2. TEDA College, Nankai University, Tianjin, 300457, PR China

   Ping Chen

3. School of Computer Engineering, Nanyang Technological University, 639798, Singapore

   Chuan Heng Foh

Corresponding author

Correspondence toChuan Heng Foh.

Competing interests

The authors declare that they have no competing interests.

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions