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.