An analytical geometric range free localization scheme based on mobile beacon points in wireless sensor network

Abstract

In many applications of wireless sensor network, the position of the sensor node is useful to identify the actuating response of the environment. The main idea of the proposed localization scheme is similar with most of the existing localization schemes, where a mobile beacon with global positioning system broadcast its current location coordinate periodically. The received information of the coordinates help other unknown nodes to localize themselves. In this paper, we proposed a localization scheme using mobile beacon points based on analytical geometry. Sensor node initially choose two distant beacon points, in-order to minimize its residence area. Later using the residence area, sensor node approximate the radius and half length of the chord with reference to one of the distant beacon point. Then the radius and half length of the chord are used to estimate the sagitta of an arc. Later, sensor node estimate its position using radius, half length of the chord, and sagitta of an arc. Simulation result shows the performance evaluation of our proposed scheme on various trajectories of mobile beacon such as CIRCLE, SPIRAL, S-CURVE, and HILBERT.

1 Introduction

WSN is widely used in many fields, including habitat monitoring, environmental data gathering, medical diagnosis, and disaster rescue [1–4]. The gathered data of the sensor node is meaningless until the location is unknown. Sensor node is now able to determine its position more accurately using GPS [5–12]. However, sensor nodes are tiny inexpensive device, usually made to deploy large number of them into the sensing field to gather data as long as possible [13, 14]. Hence, enabling each sensor node with GPS capability reduces the lifetime of the sensor within the network.

Recent research has proposed static and dynamic infrastructure to localize the sensor nodes [15, 16]. In a static infrastructure, sensor nodes are deployed into a sensing field with few anchor nodes equipped with GPS capability. Based on the broadcasting coordinates of any three neighboring anchor nodes, sensor node determine its position either using triangulation or trilateration method [17]. However, to improve the position estimation, these methods require higher density of anchor deployment, which directly increases the cost and energy consumption. On the other hand, with dynamic infrastructure, only a single mobile beacon traverse the sensing field and periodically broadcast its current location coordinate. Each static sensor node record the arrival and departure coordinates of the mobile beacon. Later, using these coordinates sensor node determines its position.

In proposed method of localization, sensor node estimate its position within the residence area created by the communication range intersection of any two distant beacon points. Later, sensor node differentiate its estimated position within the residence area using the third distant beacon point. We use dynamic infrastructure where a mobile beacon traverse the predetermined trajectory. The dynamic infrastructure has two advantages. Firstly, the mobile beacon is able to traverse the entire field and assist each sensor node to determine its position. Secondly, the sensor node can determine its position more accurately.

The main contribution in this paper are discussed as follows:

• 1. The proposed localization scheme sustain less position estimation error even at longer beacon broadcasting intervals.

• 2. It also shows less position estimation error even at different degree of irregularity (DOI) in consideration.

The rest of the paper is organized as follows. Section 2 presents the related work. Section 3 presents the mobile beacon based range free localization scheme using analytical geometry. Section 4 presents the simulation and results. Section 5 presents the conclusion.

2 Related works

In this section, we have discussed about the various mobile beacon trajectory based range free localization methods. Range free scheme is based on proximity information, which derives the position of the sensor node through geometrical interpretation, constraint minimization, and residence area formation.

2.1 Mobile beacon based static node localization methods

The static infrastructure for localization of the sensor node is expensive and requires more number of the anchor nodes with GPS capability. It directly elevates the cost of deployment and also decreases the lifetime of the sensor network within the sensing field. To overcome these problems, many localization methods are proposed using mobile beacon, which assist the sensor nodes to determine their position. Ssu et al. [18] proposed a simple range free localization algorithm using geometry conjecture (perpendicular bisector of the chord), where each sensor node selects three beacon points of the traversing mobile beacon. These beacon points are later used to estimate the position of the sensor node through geometry conjecture. Ssu scheme shows large position estimation error at longer beacon broadcasting interval. It is also vulnerable to radio propagation irregularity. Lee et al. [19] proposed a geometrical constrained based localization method, which is an extension of Ssu scheme. The position of the sensor node geometrically delimits within all possible areas generated by the mobile beacon. Then the intersection of all possible areas determines the position of the sensor node. However, differentiation of the sensor node position within the delimited area may produce the wrong decision due to varying radio propagation irregularity. Galstyan et al. [6] proposed a constraint based distributed localization algorithm, which delimits the areas of the sensor node by using two reference points. Then the sensor node position is estimated within all possible intersection of the areas for any two reference points. Galstyan scheme has less delimited areas, which causes large position estimation error. Xiao et al. [20] proposed a distributed range free method based on mobile beacon. The method allows a sensor node to estimate its position under the arrival and departure overlap (ADO) of the mobile beacon points. Xiao scheme provides better performance in localization accuracy due to more delimited area than Galstyan scheme. However, Xiao’s scheme is computationally expensive and required more number of intersections to delimit the sensor location. Guerrero et al. [21] proposed a range free method based on mobile beacons (ADAL). The mobile beacon is equipped with a rotatory directional antenna, which periodically transmit the beacon messages in a determined azimuth. Each sensor node estimate its position by taking the centroid of all intersection points of the circular sector at varying azimuth. However, it is expensive due to rotatory directional antenna with complex antenna control system. In addition, intersection points of the circular sector at varying azimuth may not provide the small delimited area, resulting large position estimation error. Dong et al. [22] proposed an iterative localization algorithm in which a sensor node makes an initial guess of its position using Levenberg–Marquardt method, and then iteratively refine its new position based on the Gauss–Newton method and using the newly-acquired beacon points. However, initial guess defines the accuracy of the localization and wrong guess may leads to large position estimation error.

2.2 Mobile beacon trajectories

The mobile beacon trajectories has been classified into two categories: deterministic and non deterministic. These trajectories have a significant impact on the localization accuracy. An efficient trajectory of mobile beacon covers the maximum area of region of interest (ROI) with less energy consumption and communication overhead. In this paper, we have only discussed about the deterministic trajectories of mobile beacon. Koutsonikolas et al. [23] discussed about various mobile beacon trajectories such as SCAN, DOUBLE SCAN, and HILBERT. In SCAN method, a mobile beacon moves along one dimension either x-axis or y-axis. DOUBLE SCAN trajectory of mobile beacon is along the x axis and y axis. HILBERT trajectory increases the nonlinear movement for mobile beacon, which increases the energy consumption and traveling path length. Huang et al. [24] proposed a deterministic static path planning scheme for mobile beacon. The proposed path planning schemes CIRCLE and S-CURVE provide non collinear beacon points, which improves the localization accuracy. However, the CIRCLE trajectory does not provide efficient covering to the boundary lying sensor nodes. Han et al. [17] proposed an efficient deterministic mobile beacon trajectory called LMAT. The proposed trajectory provides shortest path length with efficient coverage capability. Hu et al. [25] proposed a deterministic SPIRAL trajectory for mobile beacon, which improves the localization accuracy but in terms of covering, SPIRAL trajectory fails to cover the boundary lying sensor nodes.

In this paper, we proposed a range free localization method based on restricted area. Our method has few economic features other than the existing methods. Firstly, proposed method sustain higher accuracy even at longer beacon broadcasting interval. Secondly, sensor node only needs three non collinear beacon points. Thirdly, proposed method sustain higher accuracy even at irregular pattern of radio signal (varying DOI).

3 Mobile beacon based range free localization scheme

In this section, we present a range free localization method based on geometric formulation. Geometry has various primitive shapes such as triangle, circle, rectangle, and rings, which are used in various range free localization methods [26–30]. Our proposed method is based on analytical geometry of an arc, where sensor node estimate its position using three non collinear beacon points.

Our proposed method of localization has been divided into four phases. In first phase, sensor node estimate its residence area. In second phase, sensor node randomly approximate the radius and half length of the chord. In third phase, sensor node estimate the sagitta of an arc using the radius and half length of chord. In fourth phase, sensor node estimate its position using radius, half length of the chord, and sagitta of an arc (Fig. 1).

Fig. 1

Arc of the circle

3.1 Sensor node residence area formation

Mobile beacon traverses the sensing field in a predefined trajectory and periodically broadcast its current location coordinate. We assume that sensor node listen the beacon messages, once the mobile beacon enters the communication range of the sensor node. Sensor node maintain the list of the beacon messages, while mobile beacon enters and departs from its communication range. Each beacon message holds the basic information such as its current location coordinate, communication range, and transmission power level. From the information of the beacon message, sensor node initially selects the two distant beacon points. Later, the intersection of these two distant beacon point communication range creates the residence area of the sensor node as shown in Fig. 2.

Fig. 2

Steps describing the residence area formation. a Sensor node creating its residence area under the communication range intersection of two farthest beacon points B and C and b the intersection coordinate of their communication range are $\hbox {J}(x_c,y_c)$ and $\hbox {K}(x_g,y_g)$

Let $L={A,B,C,\ldots , n}$ be the list of the beacon points recorded by the sensor node with its communication range r. To select the two distant beacon points, sensor node calculates the euclidean distance $E = {E_{AB}, E_{AC}, E_{BC}\ldots , E_{An}, E_{Bn}}$ between each beacon point of the list L. As shown in Fig. 2, sensor node selects the maximum euclidean distance corresponding beacon points B(x1, y1) and $C (x_2,y_2)$. The intersection of two distant beacon point B (x1, y1) communication range and $C (x_2,y_2)$ communication range, creates the residence area of the sensor node.

$$\varDelta x= x_2-x_1$$

(1)

$$\varDelta y= y_2-y_1$$

(2)

$$D= \sqrt{\varDelta x^2+\varDelta y^2}$$

(3)

$$D_{CL}= (D^2 + r^2 -r^2)/(2*D)$$

(4)

$$x_c= x_1 + (\varDelta x*D_{CL})/D + (\varDelta y/D)*sqrt(r^2 - D_{CL}^2)$$

(5)

$$y_c= y_1 + (\varDelta y*D_{CL})/D - (\varDelta x/D)*sqrt(r^2 - D_{CL}^2)$$

(6)

$$x_g= x_1 + (\varDelta x*D_{CL})/D - (\varDelta y/D)*sqrt(r^2 - D_{CL}^2)$$

(7)

$$y_g= y_1 + (\varDelta y*D_{CL})/D + (\varDelta x/D)*sqrt(r^2 - D_{CL}^2),$$

(8)

where $(x_c,y_c)$ and $(x_g,y_g)$ be the intersection points of their communication range. From Fig. 2, the intersection coordinate $(x_c,y_c)$ and $(x_g,y_g)$ are designated as $J (x_c,y_c)$ and $K (x_g,y_g)$. The line segment joining the intersection point J and K is called radical line JK.

3.1.1 Random approximation of radius and half length of the chord

According to the geometry, if radius and any two points on the circumference of the circle is known, then position of the sensor node can be easily determined. To determine the two points on the circumference of the circle with radius, sensor node assumes a circle which passes through one of the distant beacon point (earlier used for residence area formation). Now sensor node has one point on the circumference of its assumed circle. To approximate the other point on the circumference of its assumed circle with radius, sensor node applies the analytical geometry of an arc. As shown in Fig. 3, the assumed circle of the sensor node is divided into two consecutive arcs (major arc and minor arc) using common line between the two distant beacon points B and C. The line segment joining the beacon points B and C is not a complete chord of the assumed circle. Besides that, the line segment BC has enough length to estimate the radius and half length of the chord. To estimate the radius and half length of the chord, sensor node randomly generates few points on the line segment BC. Sensor node calculates few euclidean distances between the randomly generated points and distant beacon point B. From the calculated euclidean distances, sensor node selects the two euclidean distances, which are named as radius and half length of the chord. However, the selected euclidean distances must satisfy that the half length of the chord can be equal to the radius or less than the radius. The following input parameters are required to set the random approximation range for radius and half length of the chord.

• 1. Given two beacon points $\hbox {B}(x_1,y_1)$ and $\hbox {C}(x_2,y_2)$ as shown in Fig. 3(a), the slope and intercept of line BC are calculated as $m_{BC}=\frac{y_1-y_2}{x_1-x_2}$ and intercept $c_{BC}=-(m_{BC}*x_1)+y_1$ respectively.

• 2. The mid point $\hbox {P}(x_m,y_m)$ of radical line is calculated as $\hbox {P}(x_m=(x_c+x_g)/2$, $y_m=(y_c+y_g)/2)$ using two intersecting points $\hbox {J}(x_c,y_c)$ and $\hbox {K}(x_g,y_g)$ as shown in Fig. 3(b).

• 3. The circle-line intersection coordinate $\hbox {I}(x_i,y_i)$, using the circle with center $\hbox {B}(x_1,y_1)$ and radius r is calculated as:

  $$(x_i-x_1)^2+(y_i-y_1)^2=r^2$$

  (9)

  First, substituting the equation of line $c_{BC}=-(m_{BC}*x_1)+y_1$ in Eq. (9), we get:

  $$(x_i-x_1)^2+(y_i-m_{BC}*x_1-c_{BC})^2=r^2$$

  (10)

  Simplifying above equation we get:

  $$\begin{aligned}&(m_{BC}^2+1) *x_i^2 +2*(m_{BC}*c_{BC}-m_{BC}*y_1-x_1)*x_i\\&\quad + (y_1^2-r^2+x_1^2-2*c_{BC}*y_1+c_{BC}^2)=0 \end{aligned}$$

  (11)

  Equation (11) can be solved using quadratic equation. Let relabel the coefficients to $ax_i^2+bx_i+c=0$, then we get:

  $$x_i= \frac{-b\pm \sqrt{b^2-4*a*c}}{2*a}$$

  (12)
  $$y_i= m_{BC}* \pm x_i+c_{BC}$$

  (13)

  The above quadratic formula generate two roots $\hbox {I}(\pm x_i,\pm y_i)$ as shown in Fig. 3(c). To choose the valid root from $\hbox {I}(\pm x_i,\pm y_i)$, we calculate the euclidean distance between $\hbox {P}(x_m,y_m)$ and $\hbox {I}(\pm x_i,\pm y_i)$ as $E_p$ and $E_n$. Based on comparison between $E_p$ and $E_n$ as $(E_p<E_n)? (-x_i,-y_i) : (x_i,y_i)$, sensor node selects the root which is nearer to $\hbox {P}(x_m,y_m)$ as the circle-line intersection coordinate $\hbox {I}(x_i,y_i)$ or I(-$x_i$,-$y_i)$. Let $\hbox {I}(x_i,y_i)$ is selected as the circle-line intersection coordinate.

• 4. The mid point $\hbox {Z}(x_r,y_r)$ of the residence area is calculated as $\hbox {Z}(x_r=(x_m+ x_i)$, $y_r=(y_m+ y_i))$ using coordinates $\hbox {P}(x_m,y_m)$ and $\hbox {I}(x_i$, $y_i)$ as shown in Fig. 3(d). From the earlier estimated coordinates, $\hbox {P}(x_m,y_m)$, $\hbox {I}(x_i$, $y_i)$, and $\hbox {Z}(x_r,y_r)$, we derive the euclidean distances $E_{PI}$, $E_{PZ}$, and $E_{AZ}$ respectively. Estimated euclidean distances $E_{PI}$, $E_{PZ}$, and $E_{AZ}$ are used to set the random approximation range for radius and half length of the chord.

• 5. The end point coordinates of the radical line JK are $\hbox {J}(x_c,y_c)$ and $\hbox {K}(x_g,y_g)$. Its slope $m_{JK}=\frac{y_c-y_g}{x_c-x_g}$ and intercept $c_{JK}=-(m_{JK}*x_c)+y_c$ are later used to approximate the sagitta (height) of an arc.

All the earlier estimated parameters are successively applied to approximate the radius and half length of the chord as shown in Fig. 4. The relation given below, randomly approximate the radius within the range specified as follows:

$$r_1= E_{AZ}+E_{PI}$$

(14)

$$r_2= E_{AZ}-E_{PZ}$$

(15)

$$R= (r_2-r_1)*rand(k,1)+r_1,\quad j=1,2,\ldots ,n\quad and \quad k= j,$$

(16)

where $r_1$ and $r_2$ are the random approximation range and R represents the random point generating function. Each random value R $(R_1, R_2, R_3,\ldots ,R_n)$ within the range $r_1$ and $r_2$ are considered as the radius, as shown in Fig. 4(b). Each circle drawn against the radius r (corresponding to R) with center $\hbox {B}(x_1,y_1)$, intersect the lines BC and JK. Then the corresponding intersection coordinates of the circle with lines BC and JK are designated as $\hbox {Q}(\pm x_e,\pm y_e)$ and $\hbox {F}(\pm x_t,\pm y_t)$ respectively. The intersection coordinates $\hbox {Q}(\pm x_e,\pm y_e)$ and $\hbox {F}(\pm x_t, \pm y_t)$ are later used to approximate the half length of the chord. The equation of the circle with center $\hbox {B}(x_1,y_1)$ and the radius r corresponding to the random values $R (R_1, R_2, R_3,\ldots ,R_n)$ shown in Eq. (17). The circle-line intersection coordinates $\hbox {Q}({\pm }x_e,{\pm }y_e)$ are calculated as:

$$(x_e-x_1)^2+(y_e-y_1)^2=(R)^2, \quad R=R_1,R_2,R_3,\ldots ,R_n$$

(17)

First, substituting the equation of line $c_{BC}=-(m_{BC}*x_1)+y_1$ in Eq. (17), we get:

$$(x_e-x_1)^2+(y_e-m_{BC}*x_1-c_{BC})^2=(R)^2$$

(18)

Simplifying the above equation we get:

$$\begin{aligned}&(m_{BC}^2+1) *x_e^2 +2*(m_{BC}*c_{BC}-m_{BC}*y_1-x_1)*x_e\\&\quad + (y_1^2- R^2)^2+x_1^2-2*c_{BC}*y_1+c_{BC}^2)=0 \end{aligned}$$

(19)

Equation (19) can be solved using quadratic equation. Let relabel the coefficients to $ax_e^2+bx_e+c=0$, then we get:

$$x_e= \frac{-B\pm \sqrt{B^2-4*A*C}}{2*A}$$

(20)

$$y_e= m_{BC}* \pm x_e+c_{BC}$$

(21)

The above quadratic formula generate two roots $\hbox {Q}(\pm x_e,\pm y_e)$ as shown in Fig. 4(b). To choose the valid root from $\hbox {Q}(\pm x_e,\pm y_e)$, we calculate the euclidean distance between $P(x_m, y_m)$ and $\hbox {Q}(\pm x_e,\pm y_e)$ as $E_p$ and $E_n$. Based on the comparison between $E_p$ and $E_n$ as $(E_p<E_n) ? (-x_e,-y_e) : (x_e,y_e)$, sensor node selects the root which is nearer to $\hbox {P}(x_m,y_m)$ as the circle-line intersection coordinate $(\hbox {Q}(x_e, y_e)$ or $\hbox {Q}(- x_e,- y_e))$, as shown in Fig. 4(c). Let $\hbox {Q}(x_e,y_e)$ is selected as the circle-line intersection coordinate.

To find the other intersection coordinates $\hbox {F}( \pm x_t, \pm y_t)$ on a radical line JK, let relabel the coefficients of Eq. (19) as $m_{BC}$ to $m_{JK}$, $c_{BC}$ to $c_{JK}$ and Q$(x_e$, $y_e)$ to $\hbox {F}(x_t, y_t)$. After rebelling the coefficients $\hbox {F}(\pm x_t, \pm y_t)$ is calculated as:

$$\begin{aligned}&(m_{JK}^2+1) *x_t^2 +2*(m_{JK}*c_{AB}-m_{JK}*y_1-x_1)*x_t\\&\quad + (y_1^2- R^2)^2+x_1^2-2*c_{JK}*y_1+c_{JK}^2)=0 \end{aligned}$$

(22)

Equation (22) can be solved using quadratic equation. Let relabel the coefficients to $ax_t^2+bx_t+c=0$, then we get:

$$x_t=\frac{-B\pm \sqrt{B^2-4*A*C}}{2*A}$$

(23)

$$y_t=m_{AB}* \pm x_t+c_{AB}$$

(24)

The above quadratic formula generate two roots $\hbox {F}(\pm x_e,\pm y_e)$ as shown in Fig. 4(b). Each consecutive roots $\hbox {F}(\pm x_e,\pm y_e)$ with $\hbox {Q}(x_e, y_e)$ are used to approximate the mid point of the chord BC as follows:

$$x_{mid1}= \frac{xe+x_t}{2}$$

(25)

$$x_{mid2}= \frac{xe+x_t}{2}$$

(26)

$$y_{mid1}= \frac{ye-x_t}{2}$$

(27)

$$y_{mid2}= \frac{ye-x_t}{2},$$

(28)

where $\hbox {L}(x_{mid1},y_{mid1})$ and $\hbox {M}(x_{mid2},y_{mid2})$ are the mid points of the line between $\hbox {Q}(x_e,y_e)$ and $\hbox {F}(x_t,y_t)$, and $\hbox {Q}(x_e,y_e)$ and $\hbox {F}(-x_t,-y_t)$ respectively, as shown in Fig. 4(c). A line LM is drawn between the estimated coordinates $\hbox {L}(x_{mid1},y_{mid1})$ and $\hbox {M}(x_{mid2},y_{mid2})$ as shown in Fig. 4(d), whose slope $m_{LM}$, intercept $c_{LM}$, and mid point $\hbox {T}(mid_x,mid_y)$ are calculated as follows:

$$m_{LM}= \frac{y_{mid1}-y_{mid2}}{x_{mid1}-x_{mid2}}$$

(29)

$$c_{LM}= -(m_{LM}*x_{mid1})+y_{mid1}$$

(30)

$$mid_x= \frac{x_{mid1}+x_{mid2}}{2}$$

(31)

$$mid_y= \frac{y_{mid1}+y_{mid1}}{2},$$

(32)

where the mid point $\hbox {T}(mid_x,mid_y)$ of line LM is represented as the mid point of the line BC, slope $m_{LM}$ and intercept $c_{LM}$ are used to the approximate the sagitta of an arc. The half length of the chord is calculated using the euclidean distance $E_{xy}$ between the coordinates $\hbox {B}(x_1,y_1)$ and $\hbox {T}(mid_x,mid_y)$ as follows:

$$E_{xy}=\sqrt{(x_1-mid_x)^2+(y_1-mid_y)^2}$$

(33)

Fig. 3

Estimation of parameters to set the random approximation range for radius and half length of the chord

Fig. 4

Random approximation of radius and half length of the chord

3.1.2 Approximation of sagitta

From the previous calculation we have, half length of the chord $E_{xy}$, mid point of the chord $\hbox {T}(mid_x,mid_y)$, and radius r corresponding to each individual random values R. The approximated half length of the chord $E_{xy}$ is used to estimate the sagitta on an arc [31]. The sagitta is the vertical line from the midpoint of the chord to the arc itself as shown in Fig. 1. The half length of the chord, sagitta, and radius of the arc are inter-related and if we know any two of them, then we can calculate the third. Each generated random values of R and measured half-length of the chord $E_{xy}$ are used to calculate the sagitta H of an arc as follows:

$$H=R - \sqrt{(R^2-E_{xy}^2)}$$

(34)

Sagitta H of minor arc is consider to approximate the point on the circumference of the assumed circle. The minor arc of the assumed circle is differentiated using third beacon point $\hbox {M}(x_3,y_3)$.

Let relabel the input coefficients of Eq. (22) as $m_{JK}$ to $m_{LM}$, $c_{JK}$ to $c_{LM}$, R to sagitta H, and F$(x_t$, $y_t)$ to $\hbox {N}(x_v,y_v)$. After relabeling, $\hbox {N}(x_v,y_v)$ is calculated as follows:

$$\begin{aligned}&(m_{LM}^2+1) *x_v^2 +2*(m_{LM}*c_{LM}-m_{LM}*mid_y-mid_x)*x_v\\&\quad + (mid_y^2- H^2+mid_x^2-2*c_{LM}*mid_y+c_{LM}^2)=0 \end{aligned}$$

(35)

Equation (35) can be solved using quadratic equation. Let relabel the coefficients to $ax_c^2+bx_c+c=0$, then we get:

$$x_v=\frac{-B\pm \sqrt{B^2-4*A*C}}{2*A}$$

(36)

$$y_v=m_{LM}* \pm x_c(1)+c_{LM}$$

(37)

Equations (36) and (37) generate two roots $\hbox {N}(\pm x_v,\pm y_v)$, when sagitta H of an minor arc is consider.

3.1.3 Position estimation

Each generated root $\hbox {N}(\pm x_v,\pm y_v)$ corresponding to the sagitta H of an minor arc are shown in Fig. 5(a). Table 1, shows all combination of the beacon points $\hbox {N}(\pm x_v,\pm y_v)$ and $\hbox {B}(x_1,y_1)$. Let combination of beacon points $\hbox {B}(x_1,y_1)$ and $\hbox {N}(x_v,y_v)$ generates a chord $\overline{BN}$, and $\hbox {B}(x_1,y_1)$ and $\hbox {N}(-x_v,-y_v)$ generates a chord $\overline{BV}$. Each individual random values R is considered as the radius r of the assumed circle. Sensor node decides the valid combination of beacon points $\hbox {B}(x_1,y_1)$ with $\hbox {N}(x_v,y_v)$ or $\hbox {N}(-x_v,-y_v)$ based on the third beacon point $\hbox {M}(x_3,y_3)$.

Fig. 5

Final position estimation and differentiation. a Approximated sagitta H of minor arc generated points on the circumference of the assumed circle, b applies analytical geometry using approximated radius and half length of the chord and c final position is differentiated using third beacon position

Table 1 Generated all possible combination of beacon points

To differentiate the valid combination of beacon points $\hbox {B}(x_1,y_1)$ with $\hbox {N}(x_v,y_v)$ or $\hbox {N}(-x_v,-y_v)$, sensor node measures the euclidean distance $E_{MJ}$ and $E_{MK}$ between the third beacon point $\hbox {M}(x_3,y_3)$ and the end point of radical line $\hbox {J}(x_c,y_c)$ and $\hbox {K}(x_g,y_g)$. Based on the comparison of estimated euclidean distance $E_{MJ}$ and $E_{MK}$, sensor node further redefine its residence area, which is near to the third beacon point $\hbox {M}(x_3,y_3)$. The new residence area of the sensor node always belongs to the major arc of the assumed circle. The previous comparison of euclidean distances $E_{MJ}$ and $E_{MK}$, only differentiates the major arc and minor arc of the assumed circle. Now sensor node further calculates the euclidean distance between the approximated point $\hbox {N}(\pm x_v,\pm y_v)$ and end point of radical line $\hbox {J}(x_c,y_c)$ and $\hbox {K}(x_g,y_g)$. The comparison of euclidean distance $E_{MJ}$ and $E_{MK}$ generates two conditions for selection of the valid point either $\hbox {N}(x_v,y_v)$ or $\hbox {N}(-x_v,-y_v)$ as follows:

$$IF\,\,E_{MJ}<E_{MK}:$$

(38)

$$E_{JN}=\sqrt{(x_c-x_v)^2+(y_c-y_v)^2}$$

(39)

$$E_{JV}=\sqrt{(x_c+x_v)^2+(y_c+y_v)^2}$$

(40)

$$(E_{JN}>E_{JV}) ? (x_v,y_v) : (-x_v,-y_v)$$

(41)

$$ELSE:$$

(42)

$$E_{KN}=\sqrt{(x_g-x_v)^2+(y_c-y_v)^2}$$

(43)

$$E_{KV}=\sqrt{(x_g+x_v)^2+(y_c+y_v)^2}$$

(44)

$$(E_{KN}<E_{KV}) ? (x_v,y_v) : (-x_v,-y_v)$$

(45)

$$END$$

(46)

Based on the above comparison sensor node is now able to select the valid point either $\hbox {N}(x_v,y_v)$ or $\hbox {N}(-x_v,-y_v)$. After identification of the valid point, sensor node estimate its position. Let $\hbox {N}(x_v,y_v)$ be the valid point in combination with the beacon point B. Each random values R is considered as the radius of the assumed circle.

$$Q= \sqrt{(x_1-x_v)^2+(y_1-y_v)^2}$$

(47)

$$Mid_x= (x_1+x_v)/2$$

(48)

$$Mid_y= (y_1+y_v)/2$$

(49)

$$x_{pos1}= Mid_x+\sqrt{(R^2-(Q/2)^2)}*(y_1-y_v)/Q$$

(50)

$$y_{pos1}= Mid_y+\sqrt{(R^2-(Q/2)^2)}*(x_1-x_v)/Q$$

(51)

$$x_{pos2}= Mid_x-\sqrt{(R^2-(Q/2)^2)}*(y_1-y_v)/Q$$

(52)

$$y_{pos2}= Mid_y-\sqrt{(R^2-(Q/2)^2)}*(x_1-x_v)/Q,$$

(53)

where Q is the chord length of the assumed circle between the beacon points $\hbox {B}(x_1,y_1)$ and $\hbox {N}(x_v,y_v), Mid_x$ and $Mid_y$ are the mid points of the chord $\overline{BN}$. Each random value R corresponding to the radius estimates the position $(x_{pos1},y_{pos1})$ and $(x_{pos2},y_{pos2})$. Sensor node applies the polygon test for identification of its valid position among $(x_{pos1},y_{pos1})$ and $(x_{pos2},y_{pos2})$. Whichever coordinate either $(x_{pos1},y_{pos1})$ or $(x_{pos2},y_{pos2})$ lies within the residence area, sensor node identifies its position with that coordinate. The final position of the sensor node is considered as the average of the all position estimated corresponding to the random value R. Let the estimated positions are $(x_{pos1},y_{pos1})$. Then the average of these positions are store in $x_p$ and $y_p$ as $x_p= \left( \frac{\sum _{i=1}^{k}x_{pos1}(i)}{k} \right)$ and $y_p= \left( \frac{\sum _{i=1}^{k}y_{pos1}(i)}{k} \right)$.

4 Simulation and results

The performance of the localization method is evaluated using MATLAB R2013a (8.1.0.604). Table 2 shows the simulation parameters and values. For performance evaluation, unknown sensor nodes are randomly deployed in an area of size $100\times 100\,\hbox {m}^2$, where single mobile beacon traverse the network in the predefined trajectories such as HILBERT, CIRCLE, S-CURVE, and SPIRAL. In first set, we evaluate the performance by considering various influencing factors, for example, communication radius, node density, and radio propagation irregularity. In second set, we evaluate the performance at four different trajectories under same simulation parameters by comparing the density of beacon positions and localization error. In third set, we compare the simulation outcome of each trajectory in terms of localization ability and covering ability in the network.

Table 2 Simulation parameters

4.1 Performance at varying DOI

In this section, we evaluate the performance of proposed localization method at varying degree of irregularity, where DOI defines the radio propagation irregularity per unit degree change in direction. The radio propagation irregularity model [26] used in this paper is shown as follows:

$$K_i =\left\{ \begin{array}{ll} 1, &{} \quad i = 0,\\ K_{i-1} \pm Rand*DOI, &{} \quad 0< i <360, \quad i \in N,\end{array}\right.$$

(54)

where $\left| K_0-K_{359}\right| \le DOI, K_i$ represents the coefficient that defines the per unit degree change in path loss for $360^\circ$. Figure 6 shows different DOI values corresponding to their irregular communication patterns. We have performed the simulation for the scenario where mobile beacon has communication range of 20 m and varying DOI ranges from 0 to 0.05 with beacon broadcasting interval of 5 m. Figure 7 shows the radio propagation irregularity impact on the localization accuracy. The result shows that, as DOI increases, the localization error also increases. In CIRCLE and SPIRAL trajectories of mobile beacon, it is observed that sensor nodes which lies on the corners of the network has a large position estimation error as compared to the nodes lying near the center area of the network. The large position estimation error at the corner of the network is due to irregular radio pattern and ineffective covering capability. When DOI increases, irregularity in the spherical pattern of radio signal also increases, which causes uneven distribution of radio signal, resulting ineffective covering at the corner area of the network in CIRCLE and SPIRAL trajectories. On the other hand, HILBERT and S-CURVE provides more accuracy even at the corner areas of the network. In HILBERT and S-CURVE trajectories, the mobile beacon effectively cover the entire network including corner of the network, resulting uniform distribution of the radio signal even at corner of the network at varying DOI. The average localization error for CIRCLE, SPIRAL, S-CURVE, and HILBERT trajectories are 2.3, 2.4, 2.2, and 2.3 m at a DOI of 0.05 respectively.

Fig. 6

Radio propagation pattern at different values of DOI

Fig. 7

Performance evaluation at varying DOI versus average localization error, at beacon broadcasting interval of 5 m, an area of size $100\times 100\,\hbox {m}^2$, number of 100 unknown sensor nodes, and beacon transmission range of 20 m

4.2 Performance at varying communication range

The mobile beacon traverses the entire network and periodically broadcast its current location, in such a case communication range has vital importance to cover the maximum area of the network with less mobility. Figure 8 shows the effect of varying communication range on localization accuracy by considering the different trajectories for mobile beacon, where DOI is 0.05 and beacon broadcasting Interval is 5 m. As shown in Fig. 8, HILBERT trajectory provides less estimation error as compared to other trajectories of mobile beacon. In HILBERT trajectory, nonlinear movement is more, resulting large number of the sensor nodes can effectively minimize their residence area, which causes less position estimation error. On the other hand, CIRCLE and SPIRAL trajectories also provides nonlinear movement but ineffective to cover the corner area of the network at DOI of 0.05, resulting large position estimation error. The S-CURVE trajectory shows large position estimation error as compared to other trajectories of the mobile beacon. In S-CURVE trajectory, sensor node is unable to acquire enough distant beacon points, in order to effectively minimize its residence area, resulting large position estimation error. At varying communication range of mobile beacon, the average localization error for CIRCLE, SPIRAL, S-CURVE and HILBERT trajectories are <2.5, 2.6, 3, and 2.1 m respectively.

Fig. 8

Performance evaluation at varying communication range versus average localization error, at beacon broadcasting interval of 5 m, an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20, 30, and 40 m, number of 100 unknown sensor nodes, and DOI of 0.05

4.3 Performance at varying density

The performance is evaluated by deploying the sensor nodes randomly into the network size of area $100\times 100\,\hbox {m}^2$, where mobile beacon has the beacon broadcasting interval of 5 m, DOI of 0.05, and communication range of 20 m. Figure 9 shows the impact of varying density of the sensor node in a network size of area $100\times 100\,\hbox {m}^2$. It is observed that the varying density of sensor node deployment shows a minor influence on the localization accuracy because each sensor node has enough beacon points to select three non collinear distant beacon points of mobile beacon. Hence, proposed method is independent from density constraint. The average localization error for CIRCLE, SPIRAL, S-CURVE, and HILBERT trajectories are <2 m.

Fig. 9

Performance evaluation at different density of sensor node deployment versus average localization error, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, and DOI of 0.05

4.4 Performance at varying beacon broadcasting interval

The beacon broadcasting interval has major impact on the localization accuracy. At closer beacon broadcasting interval, the localization error is very less as compared to longer broadcasting interval. The performance is evaluated at DOI of 0.05 and communication range of 20 m with different mobile beacon trajectories. Figure 10 shows the performance at varying beacon broadcasting interval of 3, 5, and 7 m. The large beacon broadcasting interval reduces the number of beacon positions, resulting sensor node cannot effectively minimize its residence area. In CIRCLE trajectory, it is observed that when the beacon broadcasting interval increases, localization error also increases. At 7 m of beacon broadcasting interval, CIRCLE trajectory shows large position estimation error as compared to the other trajectories. The average localization error at varying beacon broadcasting intervals for CIRCLE, SPIRAL, S-CURVE, and HILBERT trajectories are 2.2, 1.89, 1.69, and 1.5 m respectively.

Fig. 10

Performance evaluation at different beacon broadcasting interval of mobile beacon versus average localization error, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, number of 100 unknown sensor nodes, and DOI of 0.05

4.5 Simulation on CIRCLE, SPIRAL, S-CURVE and HILBERT trajectory

The performance of the proposed localization method has been evaluated at different trajectories of mobile beacon, where beacon broadcasting interval of 5 m, communication range of 20 m, and DOI of 0.05 are taken. Each trajectory has a unique shape and ability to cover the entire network. The simulation outcome of the proposed localization method at different trajectories are shown in Figs. 11, 12, 13 and 14 with an error of 1.8, 1.9, 2, and 1.95 m respectively.

Fig. 11

Simulation outcome of proposed localization scheme on CIRCLE trajectory, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, beacon broadcasting interval of 5 m, number of 100 unknown sensor nodes, and DOI of 0.05

Fig. 12

Simulation outcome of proposed localization scheme on SPIRAL trajectory, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, beacon broadcasting interval of 5 m, number of 100 unknown sensor nodes, and DOI of 0.05

Fig. 13

Simulation outcome of proposed localization scheme on S-CURVE trajectory, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, beacon broadcasting interval of 5 m, number of 100 unknown sensor nodes, and DOI of 0.05

Fig. 14

Simulation outcome of proposed localization scheme on HILBERT trajectory, at an area of size $100\times 100\,\hbox {m}^2$, beacon transmission range of 20 m, beacon broadcasting interval of 5 m, number of 100 unknown sensor nodes, and DOI of 0.05

5 Conclusion

In this paper, our proposed range free localization scheme sustain less position estimation error even at longer beacon broadcasting intervals. It also shows less position estimation error even at different DOI in consideration. Our proposed range free localization scheme has been evaluated at varying performance parameters. At DOI of 0.05, proposed localization method shows less position estimation error of 2.3, 2.4, 2.2, and 2.3 m on different mobile trajectories respectively. The performance is also evaluated at varying communication range, where the average localization error for different mobile trajectories are less than 2.5, 2.6, 3, and 2.1 m respectively. At varying density of sensor node deployment, the average localization error for different mobile trajectories are <2 m. At varying beacon broadcasting intervals, the average localization error for different mobile trajectories are 2.2, 1.89, 1.69, and 1.5 m respectively.