Hybrid Fuzzy Centroid with MDV-Hop BAT Localization Algorithms in Wireless Sensor Networks

Abstract

Many applications employing wireless sensor networks have been available in real-world scenarios. Their popularity is due to distinctive characteristics, for example, small scale, multisensing capability, and cost-effective deployment. However, there are constraints including routing, reliability, and especially localization, in particular without the aid of global positioning services, the lack of satellite coverage. In addition, if embedded, the overhead will be increased with hardware costs and shortened battery life. Thus, a range-free-based localization scheme is promising and is being pursued as a cost-effective approach. Centroid is one of the pioneer low complexity range-free estimation algorithms, and DV-Hop is another algorithm that has no requirements for distance information. However, their main drawbacks are location estimation precision. Recently, a soft-computing-based approach used to address uncertainty and approximation has been proposed as a low cost solution to gain precision, and, therefore, this research investigates its integration and then proposes a novel hybrid localization algorithm utilizing key characteristics of Centroid and DV-Hop. This hybrid scheme employs an extra weight with signal normalization derived from a fuzzy logic function in Centroid. The research also integrates a BAT algorithm of the modified DV-Hop. These combinations demonstrate the effectiveness in the simulation and location error reduction with time complexity trade-off.

1. Introduction

The Internet of Things (IoT) and microelectromechanical systems (MEMS) technology [1] have become feasible in various applications given their distinctive features and characteristics, such as low power consumption with multisensing functionalities and high performance computing within a tiny sensor node embedded with self-contained operational criteria, that is, dedicated storage and transmission logic, for multifunctional uses and applications yielding cost-competitiveness in addition to compactness and portability, which leverage the concept of multipurpose self-organizing sensors [2].

For ubiquitous connectivity supports that alleviate deployment and placement issues, the sensors have integrated wireless transmission logic including the capability to connect a large number of these wireless sensor nodes and then to apply them in several real-world scenarios, leading to the conception of wireless sensor networks (WSNs) [3, 4].

Recently, there have been a diverse number of WSN applications ranging from civil to military, that is, animal tracking, disaster management, health monitoring, health care, inventory control, security and tactical surveillance, traceability, and weather monitoring services [5]. Nevertheless, considering the distinctive characteristics of WSN that have been adopted in diverse real-world applications, many aspects have been explored and investigated for the purpose of improvement, such as quality of service, scalability, data aggregation, fault tolerance, time synchronization, calibration, energy-aware computation, and real-time communication [6].

Moreover, one of the crucial challenges of WSNs is the location discovery, especially without knowledge of a specific location where data are obtained, that is, via global positioning system (GPS) services perhaps provided by satellite. In addition, if equipped in the tiny sensor, the overall overhead of wireless sensors may be increased, including hardware costs and a shortened lifetime of the battery source; thus, further analysis may be misleading and likely inadequate [7–9].

Traditionally, two main approaches have been adopted for WSN location estimation, especially for areas with limited GPS sensing coverage, that is, range-based and range-free localization. The first approach employs either distance or angle to approximate the sensor node position between nearby sensors. To achieve this estimation, various models have been proposed, such as Angle of Arrival (AOA), Time of Arrival (TOA), Received Signal Strength Indicator (RSSI), and Time Difference of Arrival (TDOA) [10, 11].

Additionally, the second location estimation approach is computed without such information being available; however, only the connectivity or proximity information, that is, the number of hops between sensor nodes, is explored instead, such as in the case of Centroid, APIT (Point In Triangulation), DV-Hop (distance vector-hop), and Amorphous. It is worthwhile to note that range-free localization is promising and often pursued as a cost-effective approach due to the cost and limitations associated with additional hardware nodes [12].

In general, with a range-free-based approach, a Centroid-based technique is employed to estimate the location based on the nearby sensor nodes within a predefined radio range to calculate the mean distance. There is a key advantage of this approach in terms of the simplicity of computational complexity but high location estimation error depending on the node density [13, 14]. In addition to Centroid, APIT constructs a triangle from known position nodes (anchor nodes) and then determines the intersection to derive an approximate location using the concept of center of gravity. However, one of the key disadvantages is the high energy consumption, which is extremely unfavorable for WSNs [6].

With DV-Hop, the reference nodes (known location nodes or anchor nodes) broadcast the signal for the purpose of least hop distance retrieval and then estimate the hop size to estimate the unknown distance to a specific node based on a trilateration approach. The key advantage of DV-Hop is accuracy improvement even in the case of low density of reference nodes [15]. In addition to DV-Hop, Amorphous similarly employs hop size only for nodes with the least hop count, leading to lower energy consumption. Nevertheless, in the case of high density of reference nodes, the precision of the location estimation may be low [16, 17].

With the key metric on the location estimation precision for comparative performance, there are several proposals stating that there are advantages to Centroid-based and DV-Hop-based schemes over either APIT or Amorphous [18, 19]. Thus, several techniques based on their approaches are proposed and, in general, used to reduce location error by introducing the weight factor; thus, our focus is on the further optimization of these two schemes, that is, Centroid and DV-Hop.

Recently, there have also been proposals designed to estimate the proper weights to improve the proximity error; some of these promising schemes are based on soft computing [20] as the optimization solver for science and engineering problems given the key characteristics of the approach, which are suited to imprecision, uncertainty, and approximation scenarios to achieve practicability and robustness at low cost, for example, Neural Networks (NN), Genetic Algorithms (GA), Support Vector Machines (SVM), Evolutionary Algorithms (EA), and especially Swarm Intelligence (SI), or bioinspired algorithms [9, 21–23]. In addition to NN and GA [24], fuzzy logic (FL) systems and metaheuristic-based approaches are commonly explored due to the simplicity, which reduces computational time complexity [25–31].

Thus, our main contribution is in the investigation of different range-free-based location estimation schemes, as well as the optimizations of Centroid and DV-Hop with swarm intelligent. There are three components of the optimization: (1) an adaptive weight for Centroid derived from fuzzy processes was used; (2) a modification of hop size was proposed to enhance the location accuracy of traditional DV-Hop; and (3) finally, their combinations were further improved with the integration of swarm intelligent model.

Note that the former two approaches were discussed in our previous work, Katekaew et al. [28]. However, to enhance its performance further, with regard to a variation of signal intensities, here, we included an extra step using RSSI normalization during fuzzy Centroid stage. In addition, the latter integrated BAT [29] to DV-Hop using maximization called Maximum DV-Hop BAT (MDV-Hop) based on its outstanding performance compared to others, such as Particle Swarm Optimization (PSO) and GA [29–31].

These combinations were then integrated as a novel hybrid scheme called Hybrid Fuzzy Centroid and MDV-Hop BAT (E-HFCD) using an additive weight in consideration of node density. In addition to the preliminary investigation in [28], here, we intensively evaluated the impact of node density (both known and unknown nodes) and coverage (signal radius). The investigation of different topologies was also further investigated in both uniform and nonuniform scenarios.

This research article is organized as follows. In Section 2, recent proposals for state-of-the-art range-free localization schemes are discussed, in particular, DV-Hop-based approaches including Centroid derivations. Section 3 describes our optimizations based on the hybrid model for the fuzzy process and distance vector-hop with swarm intelligence. Next, the comparative performance of our proposals with regard to other state-of-the-art localization schemes is discussed in Section 4. Finally, Section 5 presents our conclusions and possible future work.

2. Related Work

As stated in Introduction, several approaches have been proposed to reduce the location error of WSNs. In this section, however, our focus is on recent related work, especially the models related to Centroid and DV-Hop derivatives including the key enhancement of adaptive weights derived from the fuzzy process as well as soft-computing-based integration.

With the Centroid-based approach [12, 13], to achieve higher accuracy, in other words, location error reduction, an (extra) adaptive weight is generally applied over a traditional Centroid. For instance, in 2009, Yun et al. [20] investigated the extra weight derived from fuzzy logic applied to the traditional Centroid and made a comparison against NN. They reported that although NN is slightly higher in terms of location estimation accuracy, the complexity in terms of computational time is much higher than the Centroid with extra weight.

In 2010, Chen et al. [32] also introduced an additional weight to adjust the Centroid-based approach and thus lower the estimation error by employing a fuzzy logic process using a FL Mamdani engine. The results showed that the performance was outstanding in terms of accuracy, especially when compared with a traditional triangulation approach. Moreover, during 2011-2012, Kumar et al. [33] and Larios et al. [34] investigated different FL models, that is, Mamdani and Sugeno, for WSN location approximation including the estimation of moving devices in real-world scenarios.

Furthermore, Monfared et al. [35] applied one of the Fuzzy Inference Engines, that is, Sugeno, to derive the extra weight for the Centroid-based approach in 2012. They reported that, by including an additive white Gaussian noise, the result was promising and even closer to that of real-world scenarios. Note that the extra weight can also be derived from other techniques. For example, Yun et al. [36] applied one of the soft-computing approaches, that is, GA, to generate the proper weights to adjust a membership function based on FL Sugeno, leading to low location estimation error. This improvement was also based on the parameter adjustments with time complexity trade-off.

Considering the DV-Hop-based approach [15], several perspectives of DV-Hop have also been explored to achieve location error reduction. For instance, in 2007, Tian et al. [37] proposed the enhancement of a traditional DV-Hop by using RSSI to approximate the actual distance given the reachable hops within the radio range. Recently, in 2014, Wang et al. [38] further improved the DV-Hop estimation algorithm using weights derived from the RSSI to adjust the trilateration equation.

There are also some approaches in consideration of hop size derivation. For example, in 2011, Wu and Gao [39] introduced another improvement to adjust the hop size selection process whereby, instead of using the lowest hop count as the hop size, the average hop size was multiplied by the hop count, resulting in low location error scheme. A year later, Yu and Li [40] also introduced a correction variable for the adjustment of the actual distance using radio range information.

Note that there have also been attempts to investigate Centroid-based and DV-Hop-based combinations, called hybrid models [41]; for example, in 2010, Zhao and Jia [42] introduced a hybrid approach to DV distance and weighed the Centroid-based approach on DV-Hop accumulative distance to estimate the coordinate for calculating the twice-weighted factor later used in the Centroid computation process.

In 2012, Liu et al. [43] also proposed a hybrid of bounding box and DV-Hop, whereby, with fewer known nodes, the former scheme is applied and DV-Hop is applied in the latter case. In the same year, Chen and Zhang [44] combined traditional DV-Hop and PSO to correct the position estimated by two-dimensional hyperbolic localization. Recently, in 2014, Safa [45] combined the main features of DV-Hop derivatives to gain location estimation precision. In the same year, Katekaew et al. [28] also proposed a hybrid of FL Sugeno and DV-Hop; however, the precision may be affected with diverse topologies including a variation of signal strength. It is worth noting that, in general, the performance of these hybrid models is promising when compared to the performance of traditional models, and, therefore, this research focuses on this hybrid approach.

3. A Hybrid Localization Scheme Using Fuzzy Centroid and MDV-Hop BAT

In addition to the traditional Centroid and DV-Hop, location approximation in WSNs can also be derived from soft-computing techniques [18–45]. In this research, we focus on the integrations of the fuzzy logic system and swarm intelligent algorithm, especially BAT [29], to enhance the location precision of a combination of Centroid and DV-Hop as a hybrid approach. In general, Figure 1 shows the overall architecture of a hybrid location estimation process in the enhancement of localization algorithms consisting of two main steps, enhanced Centroid and enhanced DV-Hop, leading to a hybrid of their combinations called E-HFCD.

Figure 1

Hybrid Fuzzy Centroid with MDV-Hop BAT processes.

3.1. Enhanced Centroid

Although the Centroid localization algorithm yields low complexity when the actual location is approximate, the key limitation is in the precision of estimation, that is, high location error. Therefore, it is likely that several optimizations have made use of Centroid with additional weights to mitigate this effect. In this research, a fuzzy logic system is selected to derive the extra weight, and, as illustrated in Figure 1, there are three main subcomponents excluding the traditional Centroid used to achieve the Fuzzy Weighted Centroid (FWC).

3.1.1. Centroid Localizations

In general, the Centroid-based scheme is used as a baseline for other WSN localization schemes. It should be noted that, in WSN evaluation processes, there is an assumption that the positions of known nodes (anchor nodes) and unknown nodes are mixed in the networks, all of which are randomly deployed.

The location approximation is generally calculated based on RSSI and the coordinates of anchor nodes. The transmission protocol including other overhead costs is left for further implementation aspects. In addition, theoretically, the radio propagation is isotopic; that is, the radio transmission ranges are all identical [7, 14]. The basic idea of the Centroid in WSN localization is as follows.

• (i)

The unknown nodes receive signal strength from beacon announcements from known location nodes.

(ii)

The unknown nodes compute the approximate location ( $x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}$ ) given the anchor node information (1 to n) that is within the acceptable RSSI threshold as stated in the following equation:

$$\begin{array}{cc}& \left(x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}\right)=\left(\frac{{\sum }_{i=\mathrm{1}}^n{x}_i}{n},\frac{{\sum }_{i=\mathrm{1}}^n{y}_i}{n}\right).\end{array}$$

(1)

3.1.2. Signal Normalizations

This step is used as preprocessing to normalize the raw RSSI over the maximum RSSI so that it fits suitably within a particular range, for example, between −1 and 0.1, based on the evaluation measurement, as stated in the following equation:

$$\begin{array}{cc}& {\mathrm{N}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}\_\mathrm{R}\mathrm{S}\mathrm{S}\mathrm{I}}_i=\frac{{\mathrm{R}\mathrm{S}\mathrm{S}\mathrm{I}}_i}{\underset{}{\max }\left|{\mathrm{R}\mathrm{S}\mathrm{S}\mathrm{I}}_i\right|}.\end{array}$$

(2)

3.1.3. Fuzzy Inference Systems

The fuzzy logic system (FLS) is used to manage the reasoning, which is an approximation that does not provide the exact solution, and, in general, the true value will be between 0 and 1 [15, 16]. In the overview, Figure 2 shows the four main processes of FLS as follows. It is worth noting that, in fact, we also evaluated the different Fuzzy Inference Systems, that is, FL Sugeno and FL Mamdani, in our previous work [28]. The result showed that FL Sugeno is promising and this finding is consistent with a mathematical analysis [13].

Figure 2

Fuzzy logic system (FLS).

• (i)

  Fuzzifier: this process is used to transform the input data mapping to the defined membership functions to determine the crossing points of each function. In this research, in fact, we employed a membership function evaluated by various functions, that is, Gaussian, Trapezoid, and Triangular [46]. The results showed that the last function with five criteria, that is, very near, near, medium, far, and very far as inputs and very low, low, medium, high, and very high as weights, is promising in terms of location error reduction, as shown in Figure 3.

• (ii)

  Fuzzy Rule: this process is used to create the mapping between the input and output (weight) given its membership function. Here, we followed the recommendation for rule constructions from Gu et al. [18] by dividing the rules into nine different inference rules as shown in Table 1.

• (iii)

  Fuzzy Inference Engine: this process will be used to derive the output (weight) given the input, that is, RSSI, and rule-based weights with aggregation methods, such as maximization operations, as illustrated in Figure 4.

• (iv)

  Defuzzifier: after the FL inference, CoG (Center of Gravity) will be calculated over the derived output.

Table 1

Fuzzy Rule: example.

Rule	If: state of RSSI	Then: state of weight
1	Very far	Very low (1)
2	Far	Very low (0.3)
3	Far	Low (0.7)
4	Medium	Low (0.3)
5	Medium	Medium (0.5)
6	Medium	High (0.3)
7	Near	High (0.7)
8	Near	Very high (0.3)
9	Very near	Very high (1)

Figure 3

Fuzzy logic: triangular function of input (RSSI).

Figure 4

Fuzzy logic: Fuzzy Inference Engine and Defuzzifier.

3.1.4. Fuzzy Weighted Centroid (FWC)

After the weight is derived from fuzzy interference systems, the position of unknown nodes ( $x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}$ ) can then be estimated based on (3). Typically, a traditional Centroid only averages the two-dimensional positions for reference or anchor nodes ( $x_i,y_i$ ). Nevertheless, to further improve the location error estimation, an extra weight ( $w_i$ ) is embedded as stated in the following equation:

$$\begin{array}{cc}& \left(x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}\right)=\left(\frac{{\sum }_{i=\mathrm{1}}^n{w}_i\times x_i}{{\sum }_{i=\mathrm{1}}^n{w}_i},\frac{{\sum }_{i=\mathrm{1}}^n{w}_i\times y_i}{{\sum }_{i=\mathrm{1}}^n{w}_i}\right).\end{array}$$

(3)

3.2. Enhanced DV-Hop

The estimation precision of the Centroid-based approach is generally outstanding if and only if the percentage of anchor nodes is high [28]. However, DV-Hop is superior in the opposite case (low number of anchor nodes) but with room for further improvement in location estimation precision. Thus, this study investigates its enhancement with the proposal of hop size optimization and then precision adjustment using a metaheuristic approach, that is, BAT [29, 30].

3.2.1. DV-Hop

There are three stages of DV-Hop [15] as follows: first, to utilize a classical distance vector protocol to exchange position and hop count information; this is performed by beacon broadcasting so that all nodes in the network can receive information on distances to reference nodes to compute the minimum hop count; second, to estimate an average size for one hop for the reference node that has the least hops to others using the hop count information stated in (4). In this equation, h denotes a number of hops between known nodes i and j; and finally, an approximate location for unknown nodes is computed by solving (5) to (10). Here, x and y are unknown positions. Note that the known nodes are specified as n nodes with the position indexed by 1 to n. Consider

$$\begin{array}{cc}& {\mathrm{H}\mathrm{o}\mathrm{p}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_i=\frac{\sum \sqrt{{\left(x_i-x_j\right)}^{\mathrm{2}}+{\left(y_i-y_j\right)}^{\mathrm{2}}}}{\sum h_{i,j}}\hspace{1em}\forall j,i\ne j\end{array}$$

(4)

$\begin{array}{cc}& d_{i,j}={\mathrm{H}\mathrm{o}\mathrm{p}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_i\times h_{i,j}\end{array}$

(5)

$\begin{array}{cc}& {\left(x-x_{\mathrm{1}}\right)}^{\mathrm{2}}+{\left(y-y_{\mathrm{1}}\right)}^{\mathrm{2}}={d_{\mathrm{1}}}^{\mathrm{2}}\\ {\left(x-x_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(y-y_{\mathrm{2}}\right)}^{\mathrm{2}}={d_{\mathrm{2}}}^{\mathrm{2}}\\ ⋮\\ {\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}={d_i}^{\mathrm{2}}\end{array}$

(6)

$\begin{array}{cc}& A=-\mathrm{2}\times \left[\begin{array}{cc}\left(x_{\mathrm{1}}-x_n\right)& \left(y_{\mathrm{1}}-y_n\right)\\ \left(x_{\mathrm{2}}-x_n\right)& \left(y_{\mathrm{2}}-y_n\right)\\ ⋮& ⋮\\ \left(x_{n-\mathrm{1}}-x_n\right)& \left(y_{n-\mathrm{1}}-y_n\right)\end{array}\right]\end{array}$

(7)

$\begin{array}{cc}& P=\left[\begin{array}{c}x\\ y\end{array}\right]\end{array}$

(8)

$\begin{array}{cc}& P={\left(A^{T}A\right)}^{-\mathrm{1}}{A}^{T}B\end{array}$

(9)

$\begin{array}{cc}& B=\left[\begin{array}{c}{d_{\mathrm{1}}}^{\mathrm{2}}-{d_n}^{\mathrm{2}}-{x_{\mathrm{1}}}^{\mathrm{2}}+{x_n}^{\mathrm{2}}-{y_{\mathrm{1}}}^{\mathrm{2}}+{y_n}^{\mathrm{2}}\\ {d_{\mathrm{2}}}^{\mathrm{2}}-{d_n}^{\mathrm{2}}-\left({x_{\mathrm{2}}}^{\mathrm{2}}+{x_n}^{\mathrm{2}}-{y_{\mathrm{2}}}^{\mathrm{2}}-{y_n}^{\mathrm{2}}\right)\\ ⋮\\ {d_{n-\mathrm{1}}}^{\mathrm{2}}-{d_n}^{\mathrm{2}}-\left({x_{n-\mathrm{1}}}^{\mathrm{2}}+{x_n}^{\mathrm{2}}-{y_{n-\mathrm{1}}}^{\mathrm{2}}-{y_n}^{\mathrm{2}}\right)\end{array}\right].\end{array}$

(10)

3.2.2. Maximum DV-Hop (MDV-Hop)

In this study, our first DV-Hop enhancement is based on our previous work [28] rather than using a traditional hop size derivation, specifically when the hop counts are equal; that is, the first received hop size is selected. In this case, instead, we propose the use of maximum numbers of hop size as the lower numbers of hop counts, that is, more nearby reference nodes. Thus, the distance will be derived from (11). We called this Maximum DV-Hop (MDV-Hop). In this equation, k denotes the number of the hop size with the least hop counts. It should be noted that we also ran the simulation based on the least and average hop size; however, the performance of its maximum is promising:

$$\begin{array}{cc}& d_{i,j}=\left\{\begin{array}{cc}\max \left\{{\mathrm{H}\mathrm{o}\mathrm{p}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_{i,k}\right\}\times h_{i,j},\hfill & k>\mathrm{1}\hfill \\ {\mathrm{H}\mathrm{o}\mathrm{p}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_{i,k}\times h_{i,j},\hfill & k=\mathrm{1}.\hfill \end{array}\right.\end{array}$$

(11)

3.2.3. BAT

BAT is one of the metaheuristic algorithms similar to PSO that is being used [29, 44] to solve many hard optimization problems. The BAT algorithm is based on echolocation behavior that finds prey using various amplitudes and frequencies given by the sonar of bats, which is then simplified in the algorithm as follows. It should be noted that Algorithm 1 shows a pseudocode of BAT in general.

• (i)

All bats can use echolocation to sense distance, and they are capable of identifying food or prey.

(ii)

Bats generally fly in random with velocity ( $v_i$ ) at position ( $x_i$ ) given a fixed frequency ( $f_{\mathrm{m}\mathrm{i}\mathrm{n}}$ ) and loudness (A) to search for prey. They can automatically and adaptively adjust the frequency of the emitted pulses r $[0\text{-}1]$ based on the target proximity.

(iii)

The loudness can be varied; however, it will range from a large $A_0$ to the minimum constant $A_{\mathrm{m}\mathrm{i}\mathrm{n}}$ .

Algorithm 1: BAT.

Objective Function: $f(x)$ , $x=(x_{\mathrm{1}},\dots ,x_d{)}^T$

( $\mathrm{1}$ )    Initialize bat populations $x_i$ ( $i=\mathrm{1,2},\dots ,n$ ) and $v_i$

( $\mathrm{2}$ )    Define Pulse Frequency ( $f_i$ ) at $x_i$

( $\mathrm{3}$ )    Initialize Pulse Rate ( $r_i$ ) and Loudness ( $A_i$ )

( $\mathrm{4}$ )    while  (Maximum number of iterations)

( $\mathrm{5}$ )     Generate a new solution and update $v_i$ and $x_i$ of Bat

( $\mathrm{6}$ )     Motion (equations (12))

( $\mathrm{7}$ )     if (random > $r_i$ )

( $\mathrm{8}$ )      Select a solution and generate a local solution

( $\mathrm{9}$ )     end if

( $\mathrm{10}$ )  Generate a new solution by flying randomly

( $\mathrm{11}$ )  if  (random < $A_i$ and $f(x_i)$ < $f(x^{\ast })$ )

( $\mathrm{12}$ )   Accept the new solutions

( $\mathrm{13}$ )   Increase $r_i$ and reduce $A_i$

( $\mathrm{14}$ )  end if

( $\mathrm{15}$ )  Rank the bats and find the best $x^{\ast }$

( $\mathrm{16}$ ) end while

In general, there is a specific rule of motion according to which bats fly; that is, how the position $x_i$ and velocities $v_i$ in a d-dimensional search space are updated, and, here, (12) show the derivations of new solutions $x_i^t$ and velocities $v_i^t$ at time step t:

$$\begin{array}{cc}& f_i=f_{\mathrm{m}\mathrm{i}\mathrm{n}}+\left(f_{\mathrm{m}\mathrm{a}\mathrm{x}}-f_{\mathrm{m}\mathrm{i}\mathrm{n}}\right)\beta \\ v_i^{t+\mathrm{1}}=v_i^t+\left(x_i^t-x_{}^{\ast }\right)f_i\\ x_i^{t+\mathrm{1}}=x_i^t+v_i^t.\end{array}$$

(12)

In these equations, β is in the ranges of 0 to 1 derived from a uniform distribution of a random vector. $x^{\ast }$ denotes the best current global solution of n bats.

In addition, the other parameters, that is, $f_i$ , $r_i$ , $v_i$ , and $A_i$ , follow the recommendations of the traditional BAT [29] (lines 1–3 in Algorithm 1). Given t as the number of iterations, (12) still apply with $x^{\ast }$ as the location with the minimum fitness value (lines 5-6). Moreover, after the randomness condition (line 7–10) is applied, line (8) represents the finding of a local solution derived from the following equation:

$$\begin{array}{cc}& x_i^{t+\mathrm{1}}=x_i^t+\beta \times A^t.\end{array}$$

(13)

After applying the fitness function, the new solution will be generated when meeting the conditions (lines 11–14), and then the adjustment in pulse rate (r) and loudness (A) will be updated accordingly (line 13). Loudness and pulse emission both have to be updated according to the number of iterations. Again in line (15), a traditional ranking algorithm is traditionally applied to adjust the population (bat). This process continues with the constraint of iteration threshold.

Generally, the loudness decreases as a bat has found its prey, while the pulse rate increases. As claimed by Yang [29] and Goyal and Patterh [27], the loudness can be chosen in any value. However, there are suggestions for updating these numbers as illustrated in (14). Here, α and γ are the constants such as 0.9. $A^t$ is denoted as the average loudness of all bats at time step t:

$$\begin{array}{cc}& A_i^{t+\mathrm{1}}={\alpha A}_i^t,\\ r_i^{t+\mathrm{1}}=r_i^{\mathrm{0}}\left[\mathrm{1}-\exp \left(-\gamma t\right)\right].\end{array}$$

(14)

3.2.4. MDV-Hop BAT

After the MDV-Hop computation process, BAT is also used to improve the precision of the location estimation given the input location (x) from the approximated location from MDV-Hop. Similar to Algorithm 1, here, when applied to localization optimization, the objective function is defined as the fitness function; that is, the best solution is the lowest fitness value, as shown in the following equation:

$$\begin{array}{cc}& \mathrm{F}\mathrm{i}\mathrm{t}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}\left(Xu\right)={\displaystyle \sum }_{i=\mathrm{1}}^n\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{H}\mathrm{o}\mathrm{p}\times {\left(d_i-\left|Xu-A_i\right|\right)}^2.\end{array}$$

(15)

Here, MaxHop is the maximum hop size with which each sensor (i) can receive RSSI and d is denoted as the straight-line distance between nodes, which are an approximated location ( $Xu$ ) and an anchor node (A).

3.3. Hybrid Fuzzy Centroid with MDV-Hop BAT Localizations (E-HFCD)

As previously stated, Centroid- and DV-Hop-based approaches have their key advantages and limitations. Our final contribution is to propose a hybrid model of these two combinations, called the Hybrid Fuzzy Centroid and MDV-Hop BAT (E-HFCD), as follows (Figure 1).

• (i)

Centroid-based model: the input RSSIs are normalized to the maximum RSSI before applying FL Sugeno using a triangular membership function on nine rules. Then, extra weights are applied that are derived from the fuzzy interference system to adjust the location estimation on the Centroid, called FWC.

(ii)

DV-Hop-based model: after traditional DV-Hop steps, a modification of the approximated distance is derived (MDV-Hop). The model is further improved with a metaheuristic scheme, that is, BAT, leading to MDV-Hop BAT.

(iii)

Hybrid model: with the knowledge of the number of known nodes or anchor nodes, considering node density, we applied the ratio (r) of number of known nodes over total number of nodes as an additive weight to the hybrid model of FWC and MDV-Hop BAT to estimate the unknown node position ( $x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}$ ), as stated in the following equation:

$$\begin{array}{cc}& \left(x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}\right)=\left(r\right)\times \text{FWC}+\left(\mathrm{1}-r\right)\times \text{MDV-hop\hspace{0.17em}\hspace{0.17em}BAT}.\end{array}$$

(16)

3.4. Complexity Analysis

There are two combinations of the Centroid- and DV-Hop-based approaches. For the former, including the normalization step, the complexity is in terms of $O(n)$ given only a single iteration stated in (1) and (2). An extra weight for the traditional Centroid including fuzzy systems, as shown in (3), still maintains the $O(n)$ complexity.

In addition, Kim et al. [47] analyzed the complexity analysis of fuzzy systems based on three operations, fuzzification, interference, and defuzzification, leading to ( $59+31N_{\mathrm{I}\mathrm{F}})N_I$ , ( $63M_{\mathrm{O}\mathrm{D}}+37N_I+19$ ) $L+6$ , and ( $39M_{\mathrm{O}\mathrm{D}}+5)L+15$ such that $N_{\mathrm{I}}$ ,   $N_{\mathrm{I}\mathrm{F}}$ , $M_{\mathrm{O}\mathrm{D}}$ , and L are the number of inputs, input fuzzy sets, output discretization, and rules, respectively. Suppose these are ns; thus, the complexity yields the maximum of $O(n^2)$ .

Considering DV-Hop, including the optimization of hop size as stated in (4) to (11), although there are more operations, they are in sequence with a single iteration resulting in $O(n)$ [48]. Similarly, observing Algorithm 1, aside from the sequencing operation, the complexity of BAT improvement is $O(tn)$ , which reaches the number of iterations stated in (12) to (15). Finally, when combining two approaches, a hybrid model (E-HFCD) results in $O(n^2)$ or the factor of the complexity of the former approach.

In terms of communication costs derived from the number of transmitting packets in the localization process, the optimization of hop size including the fuzzy functions is refined between the anchor and unknown nodes to estimate its location through weighting factors. The information is then saved at the unknown nodes in the DV-Hop algorithm, and therefore there is no extra communication cost [44].

4. Performance Evaluation

This section discusses the performance of our efficient mechanisms, Hybrid Fuzzy Centroid with MDV-Hop (E-HFCD), compared to other localization schemes and their pioneers, that is, DV-Hop-AVG [39] and DV-Hop BAT, including a traditional Centroid and DV-Hop.

4.1. Simulation Configurations

The evaluation test bed is on a standard configuration on Windows 8 operating systems (64 bits): CPU Intel Core Quad i5-2450M 2.50 GHz, 4048 × 2 MB DDR-SDAM, and 750 GB 5400 RPM Disk. For comparative purposes, the simulation model is based on MATLAB [49], similar to what was described by Gu et al. [18] with some recommendations from the surveyed proposals [27–30].

The testing process was carried out over 100 × 100 m² area with random placement of both anchor nodes and unknown nodes in either uniform or nonuniform distributions [27–30]. The random nature was generated from MATLAB functions. Similar to what was described by Tran and Nguyen [50], we modified the nonuniform scenario to have nine holes with a 10-meter radius at the positions of 25, 50, and 75 meters in the x and y coordinates, as in the examples of node placements and location errors shown in Figures 5, 6, 7, and 8.

Figure 5

Node Distribution Deployment (random uniform): cross (anchor) and circle (unknown).

Figure 6

Localization Error (random uniform): cross (anchor), circle (unknown), and line from circle (error to actual location).

Figure 7

Node Distribution Deployment (random nonuniform): cross (anchor) and circle (unknown).

Figure 8

Localization Error (random nonuniform): cross (anchor), circle (unknown), and line from circle (error to actual location).

It should be noted that, upon deployment, there is no mobility involved. In all evaluations, the key metric is an average (location estimation errors) over ten trails. The energy consumption of the computing node as well as transmission logic is not considered in this localization model evaluation [9].

In each distribution, there are also two main scenarios: (1) sensing coverage or signal radius, that is, each node has a signal radius in the range of 20, 40, 60, and 80 meters; and (2) node density; that is, the number of nodes is in the range of 100, 150, 200, and 250 with the degree in the number of anchor nodes ranging from 0.2 to 0.8 with steps in 0.2 increments to make a full signal coverage when the signal propagation follows a log-distance path loss model [18].

In addition to the location estimation precision error, the other evaluation was finally performed to measure the computational time complexity. For the sake of simplification and comparison, only two test cases were set up in uniform distribution as the representation of the lowest (lowest number of all nodes in the smallest range) and the highest (highest number of all nodes in the longest range) computational times, that is, either 100 or 250 nodes with 20 or 80 meters in signal radius when varying the ratio of anchor nodes from 0.2 to 0.8, respectively.

The performance evaluation of our proposal (E-HFCD) competes with four other range-free localizations, that is, Centroid, DV-Hop, DV-Hop AVG [37], and DV-Hop BAT. In particular, the BAT parameters for node localization were fixed with the recommendations provided by Yang [29] and Goyal and Patterh [27] as stated in Table 2. It should also be noted that, as reported from our previous work, Katekaew et al. [28], Centroid with FL Sugeno was used due to the outstanding performance on fuzzy logic systems.

Table 2

BAT parameters.

Parameters	Values
Population size (n)	1
Number of generation (t)	100
Loudness ( $A_0$ )	0.95
Pulse rate ( $R_0$ )	0.6
Minimum frequency ( $f_{\mathrm{m}\mathrm{i}\mathrm{n}}$ )	0
Maximum frequency ( $f_{\mathrm{m}\mathrm{a}\mathrm{x}}$ )	0.0001

To evaluate the performance of WSN localizations for various soft-computing models, average location error (ALR) [44] is the main metric used to measure the precision of each approach based on the approximation of the actual node position ( $x_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}},y_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}$ ) and its estimation ( $x_{\mathrm{e}\mathrm{s}\mathrm{t}},y_{\mathrm{e}\mathrm{s}\mathrm{t}}$ ) based on node radius (R) derived from the following equation:

$$\begin{array}{cc}& \mathrm{A}\mathrm{L}\mathrm{R}=\frac{\sum \sqrt{{\left(x_{\mathrm{e}\mathrm{s}\mathrm{t}}-x_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}\right)}^{\mathrm{2}}+{\left(y_{\mathrm{e}\mathrm{s}\mathrm{t}}-y_{\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}}\right)}^{\mathrm{2}}}}{\text{Number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Sensor\hspace{0.17em}\hspace{0.17em}Nodes}\times R}.\end{array}$$

(17)

4.2. Simulation Results and Discussions

Figures 9–16 show the average location errors (ALR) for the two scenarios in both uniform and nonuniform distributions. Considering uniform distribution (Figures 9–12), in general, given the number of nodes, it is obvious that, for all proposals, a greater number of nodes (100 to 250 nodes) yield higher location estimation accuracy, that is, lower estimation error. This trend is also apparent with greater numbers of anchor nodes.

Figure 9

ALR over ratio of anchor nodes (uniform) with 100 nodes.

Figure 10

ALR over ratio of anchor nodes (uniform) with 150 nodes.

Figure 11

ALR over ratio of anchor nodes (uniform) with 200 nodes.

Figure 12

ALR over ratio of anchor nodes (uniform) with 250 nodes.

Figure 13

ALR over ratio of anchor nodes (nonuniform) with 100 nodes.

Figure 14

ALR over ratio of anchor nodes (nonuniform) with 150 nodes.

Figure 15

ALR over ratio of anchor nodes (nonuniform) with 200 nodes.

Figure 16

ALR over ratio of anchor nodes (nonuniform) with 250 nodes.

In particular, considering the impact of anchor nodes, generally, when the number of anchor nodes is low, that is, there is a higher number of unreachable RSSI nodes, DV-Hop and its derivatives (DV-Hop AVG, DV-Hop BAT, and E-HFCD) seem to outperform the other approach, that is, Centroid, in terms of hop size and hop count.

However, in the other case, RSSI information can lead to a higher probability of estimating the actual location; that is, when the number of anchor nodes is increasing, Centroid and its hybrid derivative (E-HFCD) are some of the most promising approaches. For instance, Figure 9(a) shows that the precision for all proposals is between 0.5 and 0.2 when the ratios of the anchor nodes are from 0.2 to 0.8.

It should be noted that E-HFCD (the optimized hybrid of Centroid and DV-Hop) outperforms both DV-Hop and Centroid (including DV-Hop derivatives) even in scenarios with low and high numbers of anchor nodes. For example, Figure 9(b) shows that the precision for E-HFCD is between 0.22 and 0.12 as opposed to 0.31 and 0.28 for DV-Hop and 0.32 and 0.27 for Centroid, respectively.

In addition, in consideration of DV-Hop-based schemes, E-HFCD still maintains higher estimation precision ratios over DV-Hop AVG and DV-Hop BAT (between 0.29 and 0.27 and 0.26 and 0.21, resp., as shown in Figure 9(c)). It is also worth noting that, for all cases (Figures 9–12), the precision of E-HFCD tends to be the same; in other words, the accuracy of E-HFCD is outstanding for all cases.

Considering the impact of signal radius, that is, sensing coverage, when there is an increase in signal coverage, the location estimation precision of Centroid and its derivative tends to be low (this also depends on the number of nodes or anchor nodes); however, the accuracy of DV-Hop and its derivatives is much better as indicated in Figures 9(a)–9(d), 10(a)–10(d), 11(a)–11(d), and 12(a)–12(d).

For example, Figure 10 shows that, at 150 nodes, the precision of Centroid is between 0.43 and 0.24 with a 20-meter radius and 0.40 and 0.38 with an 80-meter radius. However, with DV-Hop, the figures are between 0.36 and 0.32 with the 20 meter-radius and 0.28 and 0.25 for the 80-meter radius. In addition, the other sets of Figures 11(a)–11(d) and 12(a)–12(d) show trends that are similar to those in Figures 10(a)–10(d). Nevertheless, because there are a large number of nodes, the estimation accuracy tends to also be high.

It should be noted that DV-Hop derivatives (DV-Hop AVG and DV-Hop BAT) outperform the traditional DV-Hop, and, in particular, E-HFCD is the best performer. For instance, the ALR of E-HFCD ranges from 0.37 to 0.12 and from 0.22 to 0.16 for the 20- and 80-meter radiuses, respectively. It is also worth noting that, for all cases, the trends in ALR are likely to be the same (Figures 9–12), including the outstanding performance of E-HFCD.

Considering the effect of node density, Figures 9(a), 10(a), 11(a), and 12(a) show that, with the same radius, the node density has a direct impact on the estimation accuracy, that is, a higher number of nodes yield lower location estimation error. For example, in the 100-node scenario, again, Figure 9(a) shows that almost all techniques exhibit a large number of errors (0.45 to 0.26; 0.46 to 0.43; 0.45 to 0.42; 0.46 to 0.43; 0.49 to 0.19 for Centroid, DV-Hop, DV-Hop AVG, DV-Hop BAT, and E-HFCD, resp.).

However, with more nodes, Figure 12 illustrates the opposite, that is, fewer errors (0.32 to 0.20; 0.31 to 0.30; 0.31 to 0.29; 0.27 to 0.25; 0.26 to 0.11) again for Centroid, DV-Hop, DV-Hop AVG, DV-Hop BAT, and E-HFCD, respectively. In addition, the set of Figures 9(b), 10(b), 11(b), and 12(b); 9(c), 10(c), 11(c), and 12(c); 9(d), 10(d), 11(d), and 12(d) shows similar trends to those of Figures 9(a), 10(a), 11(a), and 12(a). Nevertheless, because the signal radius tends to be of full coverage, the estimation accuracy tends to also be high.

Furthermore, Figures 13–16 show the simulation results with nonuniform distribution while varying the number of nodes as well as the anchor node ratio and sensing radius. In general, although the results may fluctuate with random nonuniform behavior, all of the algorithms follow the trends of those in uniform distribution.

For example, a greater number of nodes (100 to 250 nodes) yield higher location estimation accuracy; the error is gradually decreased when the number of nodes is increased, as shown in Figures 13(a), 14(a), 15(a), and 16(a), with a 20-meter radius. This trend is also applied with other sensing radiuses as in Figures 13(b)–16(b), 13(c)–16(c), and 13(d)–16(d). In addition, the increase in anchor nodes results in efficient gains for DV-Hop and its derivatives compared to those of Centroid.

Considering the diversity of sensing coverage, again with traditional Centroid, the estimation precision tends to be high with wide coverage as shown in Figures 13(a)–13(d), and again other scenarios also follow these trends, as illustrated in Figures 14(a)–14(d), 15(a)–15(d), and 16(a)–16(d); the behavior in these scenarios is in slight opposition to that of DV-Hop and its derivatives.

It should be noted that, with optimizations such as modifying the hop size or embedding the metaheuristic into DV-Hop, the precision may fluctuate slightly. However, it is worth noting that E-HFCD still outperforms the others. It should also be noted that the approximation precision of uniform distribution is generally better than that of nonuniform distribution as in the examples observed in Figures 9(a) and 13(a), which is similar to other comparative results.

Moreover, considering the other metric, that is, the computational time in the two main cases, Figures 17 and 18 show that all Centroid and DV-Hop derivatives have no significant effects on computational time, that is, less than 2 and 10 seconds, respectively. It is also obvious that Centroid has the lowest computational time but a high order of location estimation error (see also the first two scenarios). However, although E-HFCD has greater time complexity, it can still maintain slightly higher time complexity than the traditional DV-Hop. The computation times for DV-Hop AVG and DV-Hop BAT are halfway between these two.

Figure 17

Computational time (seconds) over ratio of anchor nodes (uniform) with 100 nodes and 20 meters in signal radius.

Figure 18

Computational time (seconds) over ratio of anchor nodes (uniform) with 250 nodes and 80 meters in signal radius.

For instance, in particular with 100 nodes and a 20-meter radius with 0.2 to 0.8 as the ratio of anchor nodes, E-HFCD has less than 1.75 seconds and 1 second, respectively, in computation time as opposed to less than one second for the traditional Centroid as well as DV-Hop. Additionally, with 250 nodes and an 80-meter radius, E-HFCD has similar computational time to that of DV-Hop, that is, less than 10 and 8 seconds versus approximately 8 seconds, respectively. Meanwhile, again, the localization precision of E-HFCD is much improved (see again the first two scenarios). Therefore, a balance between the location estimation precision and the practical computation of application deployments is needed.

5. Conclusion and Future Work

Several techniques are proposed to achieve the optimization of WSN localizations when the node estimation has no knowledge of the actual positions, primarily with radio signal strength and the position received from known nodes or anchor nodes in either range-based or range-free localization. However, the latter is the most promising approach, as there are many advantages, especially in terms of cost-effectiveness.

In addition to Centroid-based derivation schemes, a DV-Hop-based scheme is also one of the key approaches, as many of its derivatives are essential to improve the location estimation error. Nevertheless, both have advantages and limitations considering the impact of node density. Thus, this study focuses on the key components of applying soft-computing techniques, namely, fuzzy logic (FL-Sugeno) and Swarm Intelligence (SI-BAT), to adjust the extra weight over Centroid and to improve DV-Hop optimizations, such as the hybrid scheme Hybrid Fuzzy Centroid with MDV-Hop BAT (E-HFCD), which further improves the location estimation accuracy while maintaining computational complexity.

Based on our intensive evaluations of other Centroid and DV-Hop derivatives, E-HFCD yields a high degree of accuracy given the signal coverage and node density factors, and its precision still outperforms the others in both uniform and nonuniform distributions. However, more assumptions, diversities, and constraints could be further explored, that is, quality of service awareness mechanisms and data aggregation techniques, that is, an evaluation of gains in energy consumption that includes different scenarios, such as that with a consideration of node mobility.

In addition, other hybrid schemes and their optimizations of various soft-computing schemes can be further investigated for WSN localizations. Moreover, comprehensive simulation and analysis could be intensively investigated for other factors likely affecting the approximation error, such as scalability considerations, that is, network density and diversity, network dimension, network topology, various signal propagation models, and heterogeneous data traffic considering transmission protocol overheads; all of these are examples of ongoing research.