Fig. 4: Minimum Base Distance estimation of unknown node nearest to multiple anchor nodes.
The anchor nodes- A1, A2, and A3 are at a distance of one hop from the intended unknown node ‘U’ as shown. Similarly ‘B’ is at a distance of three hops and ‘C’ is at a distance of four hops from ‘U’. In this case, the anchor nodes- A1, A2, and A3 are closest to the unknown node ‘U’ in comparisons to the other anchor nodes. The centroid of A1, A2, and A3 is considered as a notion of the approximated location of the unknown node ‘U’ only, represented by Fig. 4. Now, let ‘K’ is a set of all anchor nodes which are at the equal hop count from an unknown node ‘U’ such that the hop count between ‘K’ and ‘U’ is less than the hop counts between other anchor nodes \({\{A}_{n}-K\}\) and ‘U’\((i.e.\ {h_{\text{count}}}_{\text{KU\ }}<{h_{\text{count}}}_{\left(A_{n}-K\right)\text{U\ }})\). Whereas \({}^{\prime}A_{n}^{\prime}\) is a set of all anchor nodes. In Fig. 4-
\(K=\left\{A1,\ A2,\ A3\right\}\text{and\ }A_{n}=\left\{A1,\ A2,\ A3,\ B,\ C\right\}\).
Now a centroid \(\text{CN}{(C}_{x},\ C_{y})\) is obtained by -
\begin{equation} C_{x}=\ \frac{\sum_{\forall i\epsilon K}x_{i}}{N(K)},\ and\ C_{y}=\ \frac{\sum_{\forall i\epsilon K}y_{i}}{N(K)}\nonumber \\ \end{equation}
Now similarly as that of the previous case of the Fig. 3, find out the intersections from the other connected anchor nodes with the communication periphery of ‘CN’, say\(\text{pt}_{1},\ and\ \ \text{pt}_{2}\). The communication periphery of ‘CN’ is calculated with the help of \(C_{r}\) shown in Fig. 4; where\(C_{r}\) is a product of the minimum hop size of\(K=\{A1,\ A2,\ A3\}\) and the hop count (i.e. one) between ‘K’ and ‘U’. Then it implies that the distances B \(\text{pt}_{2}\) and C\(\text{pt}_{1}\) are the minimum possible distance from ‘B’ and ‘C’ respectively.
The situations considered in Fig. 3 and 4 show the nearest anchor nodes from ‘U’ are just one hop away; where the value of \(C_{r}\) is a hop size of the ‘A’ or ‘CN’. But there may be the cases where the nearest anchor nodes may exist at a distance of more than one hop.
Let ‘U’ exists beyond one hop count from its nearest anchor nodes set. Then the value of \(C_{r}\) is the product of the minimum hop size of\(K=\{A1,\ A2,\ A3\}\) and the hop count between ‘K’ and ‘U’.
The hop size of each anchor node is estimated by DV-Hop with the help of the equation (1). But in DV-Hop the calculated hop size is erroneous that needs to be rectified. So we improve the hop size of DV-Hop by removing an average error value from it. The average error\({(\varnothing}_{p})\) for an arbitrary anchor node ‘p’ is calculated by using equation (5).
\begin{equation} \varnothing_{p}=\frac{{\left(H_{\text{coun}t_{\text{ps}}}\times\ H_{\text{siz}e_{p}}\right)-d}_{\text{ps}}}{H_{\text{coun}t_{\text{ps}}}};\ \forall\ p,s\ \epsilon\ A_{n};^{\prime}A_{n}^{\prime}is\ a\ set\ of\ all\ anchor\ nodes\ \ \ \ \ \ \ \ \ \ \ \ \ (5)\nonumber \\ \end{equation}
where ‘s’ is an anchor node located at a maximum distance from the anchor node ‘p’, \(H_{\text{siz}e_{p}}\) is a hop size of the anchor node \({}^{\prime}p^{\prime}\) by using DV-Hop algorithm, and\(H_{\text{coun}t_{\text{ps}}}\) is a hop count in-between\({}^{\prime}p^{{}^{\prime}}and\ ^{\prime}s^{\prime}\).
Therefore the corrected hop size of ‘p’, \(C{H_{\text{size}}}_{p}\) is-
\(C{H_{\text{size}}}_{p}\) =\({H_{\text{size}}}_{p}-\ \varnothing_{p}\) (6)
Now by using equation (6), the value of \(C_{r}\) is calculated by equation (7)-
\(C_{r}=\left(H_{\text{coun}t_{\text{pU}}}\ \times\ CH_{\text{siz}e_{p}}\right)\); (7)
\(\text{where\ }\text{CH}_{\text{siz}e_{p}}=minimum\left(CH_{\text{siz}e_{p1}},\ \text{CH}_{\text{siz}e_{p2}},\ldots,CH_{\text{siz}e_{\text{pt}}}\right),\ \ t=N\left(K\right),\ \ p=A\ or\ CN\)and \(H_{\text{coun}t_{\text{pU}}}\) is a hop count in-between the closest anchor nodes set ‘K’ (e.g. K = {A1, A2, A3} about Fig. 4) and ‘U’;
After obtaining the value of \(C_{r}\) a circle with radius \(C_{r}\)centered at ‘A’ or CN is drawn to cover the area under which the unknown node may exist. Further to get a minimum distance between an unknown node and an anchor node, we calculate appropriate intersection points\(pt_{1},\ pt_{2}\) formed by the circle and a straight line joining the points ‘B’ and ‘C’ to ‘A’ or CN as shown in Fig. 3 and 4. For each anchor node, there will be two intersecting points on a circle with radius \(C_{r}\), because whenever a straight line passes through a circle center the equations of both the geometric shapes produce a quadratic equation.
Therefore an anchor node collects two intersecting points on the circle which is shown in Fig. 5.
Fig. 5: Representation of circle with radiusCr and a line passing through anchor node B and CN.
Here the equation of the circle represented by Fig. 5 is-
\({(x-C_{x})}^{2}+{(y-C_{y})}^{2}={C_{r}}^{2}\) (8)
And the equation of a line passing through \({}^{\prime}B^{{}^{\prime}}\)and CN -
\(y=m_{s}x+c;\) (9)
where \(m_{s}=\ \frac{B_{y}-C_{y}}{B_{x}-C_{x}}\), and\(c=\ C_{y}-\ m_{s}\ C_{x}\)
On solving the equations (8) and (9), we get a quadratic equation (10)-
\(x^{2}+{C_{x}}^{2}-2xC_{x}+{(m_{s}x)}^{2}+{(c-C_{y})}^{2}+2m_{s}x{(c-C_{y})}^{2}=\ {C_{r}}^{2}\)(10)
Now solving the quadratic equation (10), we get two points of intersection- \(p_{1}\left(x1,\ y1\right),\ and\ \ p_{2}(x2,\ y2)\), where-
\begin{equation} x1=\ \frac{dX+f_{a}}{1+{m_{s}}^{2}};\ x2=\ \frac{dX-f_{a}}{1+{m_{s}}^{2}}\nonumber \\ \end{equation}\begin{equation} y1=\ \frac{dY+{m_{s}f}_{a}}{1+{m_{s}}^{2}};\ y2=\ \frac{dY-m_{s}f_{a}}{1+{m_{s}}^{2}}\nonumber \\ \end{equation}
where\(f_{a}=\ \sqrt{{C_{r}}^{2}\left(1+{m_{s}}^{2}\right)-\left(C_{y}-m_{s}C_{x}-c\right)^{2}}\),\(dX=\ C_{x}+C_{y}m_{s}-cm_{s}\text{\ and\ }\)
\(dY=\ c+C_{x}m_{s}+C_{y}{m_{s}}^{2}\ \).
The selection of a point out of the two points\(p_{1}\text{\ and\ }p_{2}\) , as shown in Fig. 5, is based upon a routing table of the anchor node which takes part in the centroid calculation and draws a route to the unknown node\({}^{\prime}U^{\prime}\). Here, the proposed method employs the same routing table which is populated during the network establishment. The anchor node which takes part in a route establishment as an intermediate node to the unknown node from another anchor node is considered as a ‘participative node’. The routing table helps to draw the decision to consider any one of the intersecting points. The intersecting point \(\text{pt}_{i}=p_{2}\) is selected for the anchor node \({}^{\prime}B^{\prime}\) if and only if a route \({}^{\prime}\text{rt}^{{}^{\prime}}\)exist in a routing table \({}^{\prime}T^{\prime}\) from \({}^{\prime}B^{{}^{\prime}}to\ ^{\prime}U^{\prime}\) and the route \({}^{\prime}rt^{\prime}\)consists any of the participative node from \({}^{\prime}K^{\prime}\). Similarly, if a route does not exist on the same line then the intersecting point\(\text{pt}_{i}=p_{1}\) is selected. The different possibilities about the Fig. 5 are summarised in equation (11) where\(d(B,p_{1}\text{or\ }p_{2})\) represents the distance between\({}^{\prime}B^{{}^{\prime}}and\ ^{\prime}p_{1}\text{\ or\ }p_{2}^{\prime}\).
\begin{equation} \text{pt}_{i}=\left\{\begin{matrix}p_{2}|\ d\left(B,p_{1}\right)<d\left(B,p_{2}\right)\ and\ rt\in T\left(B,U\right);\ \forall B\in A_{n}\&\\ p_{1}|\ d\left(B,p_{1}\right)<d\left(B,p_{2}\right)\ and\ rt\notin T\left(B,U\right);\ \forall B\in A_{n}\\ \end{matrix}\right.\ \ \ \ \ \ \ \ \ \ \ (11)\nonumber \\ \end{equation}
The selection of point \(p_{1}\)from an anchor node\(\ {}^{\prime}B^{\prime}\)produces the minimum possible distance but the selection of point \(p_{2}\)is not suitable to find the minimum possible distance. Instead of the point\(p_{2}\)is able to signify that the unknown node ‘U’ is beyond the centroid point CN (as shown in Fig. 5) only. So the point\(p_{2}\) in the equation (11) must be replaced by CN, therefore equation (11) can be rewritten as-
\begin{equation} \text{pt}_{i}=\left\{\begin{matrix}CN\ |\ d\left(B,p_{1}\right)<d\left(B,p_{2}\right)\ and\ rt\in T\left(B,U\right);\ \forall B\in A_{n}\&\\ p_{1}|\ d\left(B,p_{1}\right)<d\left(B,p_{2}\right)\ and\ rt\notin T\left(B,U\right);\ \forall B\in A_{n}\\ \end{matrix}\right.\ \ \ \ \ \ \ \ \ \ \ (12)\nonumber \\ \end{equation}
The equation (12) signifies that the unknown node \({}^{\prime}U^{\prime}\) is somewhere in a region surrounded by \(\text{CN\ and\ }p_{1}\). There must be multiple \(p_{1}\)with respect to each of their anchor nodes as shown in Fig. 6 are- \(p_{1}^{l},\ p_{1}^{m},\ p_{1}^{n},\ and\ p_{1}^{o}\).
Fig. 6: Expected region formed by CN and intersecting points\(\mathbf{p}_{\mathbf{1}}^{\mathbf{l}}\mathbf{,\ }\mathbf{p}_{\mathbf{1}}^{\mathbf{m}}\mathbf{,\ }\mathbf{p}_{\mathbf{1}}^{\mathbf{n}}\mathbf{,\ and,\ }\mathbf{p}_{\mathbf{1}}^{\mathbf{o}}\)from their respective anchor nodes l, m, n, and o.
Now the base distance values from the anchor nodes\(\left(A_{n}-K\right)\)are obtained, which are Euclidean values, but still the unknown node \({}^{\prime}U^{\prime}\) may exist beyond their respective\(p_{1}\)or \({}^{\prime}CN^{\prime}\), as shown by the shaded area in Fig. 6. So the location is still needed to be estimated, which is described in the next step- Location Estimation.