Keywords

1 Introduction

Wireless Sensor Networks (WSNs) are widely used in reporting of events in the hostile and remote environments [1]. These networks are termed as distributed networks that work without the presence of a centralized control. WSNs are composed of several tiny, low cost, limited energy sensing and communication devices (or sensor nodes (SNs)) and they communicate among them via wireless links. Location information is a vital requirement in various applications such as environmental monitoring, area monitoring, medical and health-care monitoring, traffic control etc., where decisions need to be taken based on location of event. For this, when SNs are deployed in the network, they have to calculate their location data. In conventional wireless networks, it is done by using Global Positioning Systems (GPSs), however, use of GPS may lead to fast energy drain in SNs.

An alternative approach used to evaluate location data is by implementing localization algorithms. Localization in Wireless Sensor Network (WSN) is the process of discovering location by a location unaware node with the help of known locations of reference nodes. WSNs require self-localization capability because sensor data without location information is not useful for necessary action. For this reason, effective localization and positioning of SNs received significant attention, and a many algorithms have been proposed by the researchers in the literature. Most of the research on localization in WSNs assumes that the beacon nodes are equipped with GPS receivers. Beacon locations are then used to determine the positions of normal SNs. Equipping a GPS receiver at SNs may not be feasible due to the limitations of energy resource. GPS based methods are said to be absolute localization methods which acquire the global coordinate in network environment. On the other hand, in relative localization all nodes in the network estimate the range between themselves and their neighboring node [2, 21,22,23].

There exist several localization methods available in the literature. They are broadly classified as Range-Based (RBL) and Range-Free Localization (RFL) methods [3]. Range based method uses angle estimation or absolute point-to-point distance estimation location calculation. Range-based schemes are angle-estimation-based techniques and distance-estimation. Important techniques used in range-based localization are Angle of Arrival (AOA), Time of Arrival (TOA), Received Signal Strength Indication (RSSI), and Time Difference of Arrival (TDOA). Requirement of additional hardware and high energy consumption are the bottleneck for these methods [3]. On the other hand, in range free localization algorithms the position estimation of unknown nodes is obtained not by any measurement technique. Location of unknown node is obtained by the connectivity information of network nodes. In this localization technique, no need to calculate the angle or any distance measurement between the nodes. Location estimation depends upon the connectivity of the nodes. Connectivity has a limited range of communication in the network. Examples of this category are DV-HOP, Concentric Anchor Based (CAB), Centroid, Weighted Centroid (WCL), 2D-Hyperbolic (2DH) and others [3,4,5,6,7,8,9,10,11,12,13,14, 21,22,23]. Range-free localization has received considerable attention in the WSN research due to low processing, memory, and energy overheads. To achieve localization accuracy using range-free localization algorithms, this paper proposes and analyzes DV-HOP based hybrid localization method. Details of the contributions in this paper are

  1. 1.

    Performance of four well-known range-free localization methods such as DV-HOP, 2DH, WCL, and CAB localization with respect to their advantages and limitations.

  2. 2.

    With the experience gained from the analysis, Hybrid Range-Free Localization methods with DV-HOP for WSNs are proposed.

  3. 3.

    The performance of the proposed method is evaluated using MATLAB and found that DV-HOP with 2DH results into high localization accuracy as compared to other methods.

Rest of the paper is organized as follows. Section 2 presents the brief literature survey on localization algorithms and then analyses the four well-known range-free localization methods DV-HOP, 2DH, WCL, and CAB with respect to their advantages and limitations using MATLAB simulations. Section 3 describes the proposed hybrid range-free localization method. The performance of the proposed method is evaluated in Sect. 4 using the simulation study. Finally, Sect. 5 concludes the paper with future work.

2 Related Work

The first part of this section presents a brief literature survey on localization algorithms and the next part presents the performance of DV-HOP, 2DH, WCL, and CAB methods.

2.1 Literature Survey

Figure 1 depicts non exhaustive list of localization methods available in the literature. The descriptions of these algorithms are as follows

Fig. 1.
figure 1

Types of localization algorithms

Full size image

  • Range based localization [3] – Range based localization calculation utilizes different estimation systems for finding the separation between an anchor node and an unknown node. Some examples are Time of Arrival, Time difference of Arrival, etc., are used to estimate the distance. Although RBL methods are more accurate than RFL methods, the distance estimation with topology maintenance and localization in a global coordinate system is not attempted.

  • Range free localization [4] – In these algorithms, the location information of unknown nodes are found without any measurement technique. Location of an unknown node is obtained by the connectivity information of the network. Location data is obtained based on the availability of the nodes.

  • Anchor Based Localization [6] – In this approach, location of few anchor nodes is known to the network. In order to find the location information of other nodes, these anchor nodes are used. Location unaware nodes are localized with the help of these localize nodes.

  • Anchor-Free Localization [7] – These algorithms compute relative positions of nodes instead of absolute position computation.

  • GPS Free Localization [10] – These methods calculate the relative distance between the nodes without GPS.

  • GPS based Localization [10] – In these methods, a GPS device is equipped with each node in the network. Due to the presence of GPS the localization accuracy is very high. Equipping GPS device in each SN is a costly effort.

  • Static Node Localization [11] – Static Localization deals with localizing SNs in a static WSN.

  • Mobile Node Localization [11] – Oppose to the static node localization, SNs are mobile in WSN. Mobile anchors nodes are responsible for disseminating location information such that unknown nodes calculates their location periodically.

  • Centralized Localization [12] – In centralized localization method, one node act as a “sink node”, which is responsible for computing locations of all nodes in the network. The advantage of this method, energy consumption of high configuration sink node is less as compared to the distributed system.

  • Distributed Localization [12] – In these methods, nodes calculates and estimates their positions individually with the help of neighboring nodes.

  • Single Hop Localization [13] – In these methods, location data is communicated and computed between anchor nodes and unknown nodes via a single hop.

  • Multi Hop Localization [14] – In multi-hop localization methods, location computation and communication happens between two nodes is carried out through the number of intermediate nodes. The role of the intermediate nodes is to relay information from on hop to another.

From the above mentioned localization methods, next subsection presents a study on RFL methods.

2.2 Performance Analysis of DV-HOP, 2DH, WCL and CAB Range-Free Localization Methods

This section first briefly describes DV-HOP, 2DH, WCL, and CAB range-free localization methods and then shows the localization accuracy of these methods using the results obtained from MATLAB simulations.

  • Distance Vector-HOP Localization [15,16,17]: In this method, Unknown Nodes (UNs) calculate their location information with the help of location information and the hop count received from Anchor Nodes (ANs). ANs are equipped with GPS devices and periodically broadcasts a beacon contains identity, location information, and hop limit. All UNs in the vicinity of AN check for hop limit. Beacon will be forwarded further by increasing the hop count by 1 if the UNs hop count is less than the hop limit. Else the beacon will be discarded. This way of forwarding message helps to maintain minimum hop count with every AN in the network. UNs calculate hop size (Hopsize) between two ANs i and j with locations \( \left( {x_{i} , y_{i} } \right) \) and \( \left( {x_{j} , y_{j} } \right) \) as follows

$$ HopSize = \sum\nolimits_{i \ne j} {\frac{{\sqrt {\left( {x_{i} - x_{j} } \right)^{2} + \left( {y_{i} - y_{j} } \right)^{2} } }}{{Hop_{i,j} }}} $$
(1)

With this UNs estimates their distance from AN by multiplying HopSize and HopCount. With this distance value, UNs calculate position by applying triangulation or multiliteration.

  • Two Dimensional Hyperbolic Localization [18]: In this method, each UN calculate HopSize with similar procedure followed in DV-HOP method. With the HopSize, in 2DH arrange HopSize is calculated

$$ HopSize_{avg} = \frac{{HopSize_{i} }}{n} $$
(2)

Where n is the number of ANs, \( HopSize_{i} \) is evaluated using Eq. (1). This \( HopSize_{avg} \) is transmitted in the network. UNs evaluate distance with this value by multiplying it using the number of hops between them. UNs use 2DH method to calculate locations instead of triangulation.

  • Weighted Centroid Localization [19]: WCL is an enhancement of centroid localization method. In this, the coordinates of UN remains at the centroid of the polygon constructed by ANs. Let a UN calculates its location (x, y) from the locations of ANs as

$$ \left( {x,y} \right) = \left( {\frac{1}{n}\sum\nolimits_{i = 1}^{n} {x_{i} } ,\frac{1}{n}\sum\nolimits_{i = 1}^{n} {y_{i} } } \right) $$
(3)

Further, distance between UN and ANs is considered as weight and this value is being multiplied by ANs coordinates and then divides by the sum of the weights to get the location information. Let W(i) is the weight value between k anchor nodes using these weight values the location is calculated as follows

$$ \left( {x,y} \right) = \left( {\frac{{\mathop \sum \nolimits_{i = 1}^{k} W\left( i \right)*x_{i} }}{{\mathop \sum \nolimits_{i = 1}^{k} W\left( i \right)}}, \frac{{\mathop \sum \nolimits_{i = 1}^{k} W\left( i \right)*y_{i} }}{{\mathop \sum \nolimits_{i = 1}^{k} W\left( i \right)}}} \right) $$
(4)

  • Concentric Anchor Based Localization [20]: In this method, each AN periodically broadcasts beacons by varying power levels. Each beacon consists of information such as the anchor’s location data, its power level, and the maximum distance that the beacon can transmitted. Nodes observe and record the beacons from the ANs. Nodes then determine within which annular ring they are located using the information received beacons.

The performance of these algorithms has been evaluated using MATLAB. A 500 × 500 \( m^{2} \) network is considered in which 1500 nodes are randomly deployed. The number of beacon nodes is varied from 100 to 500. Each node has 50 m communication range. The results presented here are the average of 10 simulation runs.

Localization error resulted by these algorithms has been verified in two scenarios such as (1) by varying the number of beacon nodes, and (2) by varying communication range of network nodes.

Figure 2(a) shows the localization error in case of increasing number of BN in the network. It is observed from the figure that a CAB method has very low localization error as compared to other RFL methods. It is because CAB can be used to locate nodes in the network.

Fig. 2.
figure 2

(a) Number of beacon nodes vs. localization error; (b) communication range vs. localization error

Full size image

Figure 2(b) shows the localization error in the case of increasing the communication range of nodes in the network. As the communication range increases the number of UNs fall under a BN increases. It is observed from the figure that the CAB method is performing well in varying communication range as compared with other methods.

The localization error is dropped suddenly in the DV-Hop method is due to UNs are able to identify BNs. However, as the communication range increases to 200, DV-HOP, weighted centroid, and 2D-Hyperbolic methods resulted into almost same localization accuracy. Among all communication ranges, CAB method outperforms the other RFL methods.

In addition, some more observations from the simulation results of the four RFL algorithms are

  • Node distribution plays a major role in achieving localization accuracy in DV-Hop localization method. In addition, the number of ANs placed in the network also affects the localization performance such as localization error and localization coverage. Further, DV-Hop method is best suited for isotropic environments and hence some specialized methods are required to improve the localization accuracy in any network environment.

  • Localization accuracy of DV-Hop method is affected by the distance between the ANs and UNs.

  • CAB has many advantages as compared to other range free approaches such as (1) CAB is cost effective as it does not require specialized range-determining hardware in the sensor nodes, (2) CAB is distributed and energy efficient, and (3) CAB is simple to implement.

  • Centroid and WCL methods are showing low localization error than DV-Hop method in high density of the ANs.

UN locations are estimated using location data received from three neighboring ANs. To increase the estimated position accuracy, it is essential to minimize the region of overlapping by choosing the three farthest ANs. This is done by calculating all the possible triangular areas that are made up of the ANs heard and by choosing the three ANs which form the large triangle. In these methods, a UN has a great impact of its nearest AN. Further, these methods will only calculate the coordinates of UN which is directly connected to AN. Therefore, improvements to this method are still required. To this end, in the next section hybrid range free localization methods based on DV-HOP method have been proposed and verified.

3 Proposed DV-HOP Based Hybrid Localization Methods

This section first presents the network model and assumptions considered in the study. Then, proposed hybrid range free localization method is described.

3.1 Network Model and Assumptions

The system model considered for the study is as follows.

  1. 1.

    A set of \( N \) homogeneous sensor nodes is randomly deployed in a \( M\,X\,M\, \text{m}^{2} \) network area.

  2. 2.

    Nodes are static in the network.

  3. 3.

    Each node in the network has a fixed communication range.

  4. 4.

    Communication between each node is symmetric.

  5. 5.

    Only anchor nodes are equipped with GPS.

  6. 6.

    Anchor nodes send out a beacon consists of identity, and location information to initiate the localization process.

3.2 Proposed DV-HOP Based Hybrid Localization Methods

Algorithm 1 and Fig. 3 shows the proposed DV-HOP based hybrid localization method. In order to reduce the positioning error of DV-HOP localization algorithm, a hybrid algorithm using 2D hyperbolic, WCL, and CAB is proposed. Similar to DV-HOP, in the proposed algorithm ANs periodically broadcast beacons consisting of location data and hop limit. Normal nodes receive the beacon packets and save the beacon information that has small hop count. Then, each node calculates the average hop count using Eq. (1). Nodes drop the beacon they receive beacons with higher hop limit. Once average hop count is calculated, each node runs the 2D hyperbolic, WCL, and CAB sequentially with DV-HOP localization to reduce the position error. This process will be repeated till position error is reduced. The simulation analysis of the proposed method is presented in the next section.

Fig. 3.
figure 3

Flow chart of the proposed hybrid localization algorithm

Full size image

Algorithm 1. DV-HOP based hybrid localization method

Input

Location data from anchor nodes (ANs), and hop count from neighbor nodes

Output

Location estimation by unknown nodes (UNs)

Step 1

ANs periodically broadcast beacons consist of identity location data, and hop limit.

Step 2

UNs when receive the beacon record the anchor identity, location data, and hop count.

Step 3

UNs calculate the HopSize using Eq. (1). Forward the beacon further if the hop limit prescribed by AN is not reached. Otherwise, drop the beacon.

Step 4

Once HopSize is calculated, UNs use 2D Hyperbolic, WCL, and CAB methods to evaluate location data individually.

Step 5

With AN beacons, UNs repeat Step 2 to 4 till localization accuracy is improved.

4 Simulation Study

This section first presents the simulation setup and followed by simulation results.

4.1 Simulation Setup

A static WSN deployed in M × N meters area with n sensor nodes is considered. Two categories of nodes are considered. They are Beacon Nodes (BNs) and UNs. Each node including BN is having a fixed communication range. It is assumed that each BN periodically broadcasts a beacon message consisting of node identity, location data, and timestamp. UNs make use of this information to run the RFL methods to compute their location data. Table 1 shows the simulation parameters considered for the study. The proposed algorithm has been evaluated for position accuracy. Localization accuracy is measured by the difference between the actual locations of nodes to the estimated location. The results presented in the next section are the average of 10 simulation runs.

Table 1. Simulation parameters
Full size table

4.2 Simulation Results

Three scenarios are considered to evaluate the localization accuracy of the proposed hybrid localization method. In the first scenario, localization error is tested with increasing number of BNs. In the second scenario, localization error is tested with increasing communication range. Finally in the third scenario, localization error is observed with increasing number of UNs.

Figure 4 shows the first scenario, in which the number of BNs varied from 100 to 450, and the localization accuracy of DV-Hop with 2D-Hyperbolic, Weighted centroid and CAB localization methods is measured. It is observed from the figure that the DV-Hop with 2D method has very low localization error as compared to other methods. It is because DV-Hop with 2D hyperbolic localization combination can be used to locate nodes in the network.

Fig. 4.
figure 4

Number of beacons vs. localization error

Full size image

Figure 5 plots second scenario i.e., the localization error of the proposed method with respect to increase in communication range. It is observed that the DV-hop with WCL and CAB shows similar localization error across varying communication range. On the other hand, DV-hop with 2D hyperbolic localization shows low localization error as compared to other methods. It is due to the reason that the proposed method utilizes the advantage of 2D hyperbolic to minimize the error.

Fig. 5.
figure 5

Communication range vs. localization error

Full size image

Figure 6 plots third scenario i.e., the localization error of the proposed method with respect to increase in number of nodes. The node count is varied from 100 to 500 while keeping total anchors and communication range as constant. It is observed from the figure that DV-Hop with 2D hyperbolic is resulting into low localization error as compared to other RFL method combinations.

Fig. 6.
figure 6

Increasing number of nodes vs. Localization error

Full size image

5 Conclusion and Future Work

This paper proposed DV-Hop based hybrid range free location methods for WSNs. First, the existing range free localization methods are analyzed using a simulation study. In this study, it is observed that each method have several limitations under different network scenarios. To overcome them, hybrid range free localization methods are proposed. The proposed methods are analyzed by conducting a simulation study. It is observed from the simulation results that even though CAB algorithm performs better independently, when it combines with DV-Hop its performance was significantly degraded. Finally, it was observed that DV-Hop with 2D hyperbolic method show significant improvement in position accuracy as compared to other methods. In future, we attempt to extend it to 3 dimensional localizations of sensor nodes.