Advanced
Fuzzy system and Improved APIT (FIAPIT) combined range-free localization method for WSN
Fuzzy system and Improved APIT (FIAPIT) combined range-free localization method for WSN
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jul, 9(7): 2414-2434
Copyright © 2015, Korean Society For Internet Information
  • Received : February 09, 2015
  • Accepted : June 16, 2015
  • Published : July 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xiaofeng Li
Institute of Intelligent Machines, Chinese Academy of Sciences Hefei 230031, China
Liangfeng Chen
Institute of Intelligent Machines, Chinese Academy of Sciences Hefei 230031, China
quinear@hfcas.ac.cn
Jianping Wang
Hefei University of Technology Hefei 230009, China
Zhong Chu
Hefei University Hefei 230601, China
Qiyue Li
Hefei University of Technology Hefei 230009, China
Wei Sun
Hefei University of Technology Hefei 230009, China

Abstract
Among numerous localization schemes proposed specifically for Wireless Sensor Network (WSN), the range-free localization algorithms based on the received signal strength indication (RSSI) have attracted considerable research interest for their simplicity and low cost. As a typical range-free algorithm, Approximate Point In Triangulation test (APIT) suffers from significant estimation errors due to its theoretical defects and RSSI inaccuracy. To address these problems, a novel localization method called FIAPIT, which is a combination of an improved APIT (IAPIT) and a fuzzy logic system, is proposed. The proposed IAPIT addresses the theoretical defects of APIT in near (it’s defined as a point adjacent to a sensor is closer to three vertexes of a triangle area where the sensor resides simultaneously) and far (the opposite case of the near case) cases partly. To compensate for negative effects of RSSI inaccuracy, a fuzzy system, whose logic inference is based on IAPIT, is applied. Finally, the sensor’s coordinates are estimated as the weighted average of centers of gravity (COGs) of triangles’ intersection areas. Each COG has a different weight inferred by FIAPIT. Numerical simulations were performed to compare four algorithms with varying system parameters. The results show that IAPIT corrects the defects of APIT when adjacent nodes are enough, and FIAPIT is better than others when RSSI is inaccuracy.
Keywords
RSSIrange-freefuzzy systemAPITWCL
1. Introduction
R ecently, Wireless Sensor Network (WSN) that consists of many small devices deployed in a physical environment has been widely used in many areas [1] , such as environmental monitoring [2] , healthcare and medical research [3] , national defense and military affairs [4] , etc. Each of such devices forms a sensor node that has special capabilities, such as communicating with its neighbors (other sensor nodes are in the communacation range of the sensor), sensing and data storage and processing. Most of these applications require the knowledge on the position of every node in the WSN [5] . A few known sensor nodes are marked as anchor nodes and their corrdinates can be obtained by Global Position System (GPS). However, attaching a GPS receiver to each common sensor node is highly impractical due to its high power consumption, high price, and inaccessibility (GPS reception might be obstructed in special conditions) [6] .
A number of localization algorithms have been proposed recently specifically for WSN [7] , and are generally classified into the range-based and range-free schemes. The former depends on the distance or angle between nodes estimated by means: angle of arrival (AoA), time of arrival (ToA), time difference of arrival (TDoA), and received signal strength indicator (RSSI) [8] . The range-free approaches infer nodes’ locations by information, such as: radio connectivity among nodes, near-far information etc. Typical range-free methods are Centroid Location (CL) [9] , DV-Hop [10] , MDS-MAP [11] , and APIT [7 , 12] . The range-based techniques except RSSI provided by a common chip generally offer better accuracies than the range-free, due to the additional specific and expensive hardware. On the contrary, the range-free schemes, which is without any additional hardware, provide more economic and simpler locations and are used widely in the large scale WSN.
Among numerous range-free methods, many researches are on improving the location accuracy of the CL or COG (the center of gravity) algorithm due to its simplicity. Many authors continue proposing methods that offer better accuracy by weight obtained with RSSI [13] or with the Link Quality Indicator (LQI) [14] . A proper weight improves the location accuracy obviously, however it’s hardly to provide an accurate weight. Some approaches have focused on inferring the most possible areas where sensor nodes reside to narrow down the whole area formed by all anchors, such as APIT and ROCRSSI [15] . Accuracies of these methods are strongly associated with correctness of the inferred areas. Thus, to improve the correctness in narrowing down areas is to improve location accuracies. Other approaches have studied on the specifications of the CL algorithm to determine the areas where it offers bigger errors [16] .
However, these area-based range-free schemes are not precise when RSSI is irregular due to influences of multipath interference, reflection, refraction, obstruction interference, etc. [17] . The reason is that the basic assumption of these schemes is not always correct with the irregular RSSI. The assumption is that the distance between a transmitter sensor node and a receiver sensor node increases monotonically with the signal power measured by the receiver decreasing. To compensate for negative effects of the irregular RSSI, these range-free schemes require a high anchor-to-node ratio which results in high cost. Hence, the further problem may be solved to maintain the robustness of these range-free algorithms.
Some algorithms [18 , 19] have been proposed to reduce influences of the environmental variation by estimating the path loss exponent of the signal propagation model in real time. They are robust for adapting to varied environmental conditions. However, they are not applied in a large-scale network or a moving scenario due to their complexities of calculating and updating the exponent frequently. Some approaches [20 , 21] have focused on establishing statistical RSSI fingerprints by off-line RSSI values. The statistical models are better than the conventional Log-D model [8] and improve location accuracies obviously. They don’t adapt to varied environments though, since: (1) the difference of the off-line RSSI and the on-line RSSI is significant due to the varied environments, and (2) the models need to be re-established in an unknown environment to maintain accuracies. Meanwhile, those aforementioned schemes are more suitable for the range-based than the range-free. Many range-free localization approaches [22 , 23] explicitly deal with the RSSI inaccuracy by the fuzzy system due to its advantage in handling the uncertainty, noise and imprecision.
In this paper, a range-free localization technique called FIAPIT, which is composed of an improved APIT (IAPIT) and a fuzzy system, is proposed. First, the original APIT is improved in the near and far cases partly to decrease errors of narrowing down areas. In the near case, the original APIT re-proved is always correct. In the far case, the InToOut error of the original APIT is decreased by a proper distance threshold. Second, to reduce negative influences of the irregular RSSI on test results of IAPIT, each triangle area (formed by anchors) where sensors may reside or not is provided with different weight by a fuzzy system instead of a definitive value 0 or 1 by IAPIT or the original APIT. And in the fuzzy system, IAPIT is the core component of the fuzzy inference. Finally, the coordinates of a sensor node are estimated as the average value of COGs of many intersection areas with large weights. In numerical simulations, location errors of four algorithms including WCL (Weighted Centroid Localization [13] ), the original APIT, IAPIT and FIAPIT, are analyzed with varying system parameters. The results show that the InToOut error of the original APIT is reduced by IAPIT when the neighbor nodes are enough, and FIAPIT has a good ability to compensate for negative effects associated with the irregular RSSI and improves location accuracies further.
The remainder of the paper is organized as follows: The original APIT is analyzed and then improved in the near and far cases partly in Section 2. In addition, the influence of irregular RSSI on the original APIT is also presented in Section 2. In order to reduce the influence of irregular RSSI on the original APIT or IAPIT, FIAPIT is proposed in Section 3. In Section 4, the location errors of aforementioned four algorithms are analyzed via numerical simulations with varying system parameters. Finally, Section 5 concludes the paper and recommends future work as using machine learning methods [24 , 25] in location.
2. The analysis of APIT
- 2.1 The defect of APIT
PIT [7] is used to assess the near/far case based on the monotonous RSSI to the distance in the scenario where there are moving sensor nodes. And APIT is proposed in the scenario where the target sensor node is static. The two scenarios of PIT are defined as follows:
Perfect PIT Test Theory: If there exists a direction such that a point adjacent to M is further/closer to points A, B, and C simultaneously, then M is outside of ΔABC. Otherwise, M is inside ΔABC.
Approximate PIT Test: If no neighbor of M is further from/closer to all three anchors A, B and C simultaneously, M assumes that it is inside triangle ΔABC. Otherwise, M assumes it resides outside this triangle.
The paper [7] points out that two errors, named the InToOut error and the OutToIn error, exist even though RSSI decreases monotonously, since APIT can only evaluate a finite number of directions (the number of neighbors). For example, the InToOut error may occur when the point three is selected as a neighbor node of the node M in Fig. 1 (a), and the OutToIn error may occur in the case that the point three does not exist in Fig. 1 (b).
PPT Slide
Lager Image
The InToOut and the OutToIn error.
Obviously, the OutToIn error in Fig. 1 (b) can be decreased by increasing neighbors in many directions. However, the InToOut error can’t be prevented only like this. Since any neighbor node of the target sensor node is further from all anchors simultaneously when the distance between them is very far. The essence of the InToOut error is that the proposition I [7] , which is the converse negative proposition of PIT, is not perfect.
Proposition I: If M is inside triangle ΔABC, when M is shifted in any direction, the new position must be nearer to (further from) at least one anchor A, B or C.
In the proof [7] of the Proposition I, the selected new position of M is also in the triangle. It’s not suitable for the case that the new position is out of the triangle.
Thus, an extra condition of the original APIT is proposed in paper [26] . It’s that the selected neighbors should be also in ΔABC where the target node resides. However, the extra condition is not appropriate. Firstly, it’s hardly to judge whether a selected neighbor node whose position is also unknown is in or out of ΔABC. Secondly, according to the proof of the Proposition I, the neighbor node that is further from all anchors simultaneously is out of the triangle.
To solve the aforementioned problems, the original APIT is analyzed in the near and far cases partly in the next subsection. In the near case, the original APIT re-proved is always correct. On the contrary, an appropriate distance threshold is given to judge whether the test result of the original APIT is suitable or not.
- 2.2 IAPIT: an Improved APIT
A. The near case that a neighbor node is closer to all anchor nodes in a triangle
A new test theory proved in Appendix A is proposed and named Point out of Triangulation (POT) test, which is named APOT in the static scenario. By the APOT test, the target sensor node is out of the triangle surely.
Perfect POT Test Theory: If there exists a direction such that a point to M is closer to points A, B, and C simultaneously, then M is outside of ΔABC.
B. The far case that a neighbor node is further from all anchor nodes in a triangle
In this case, the sensor node may be in or out of the triangle. Thus, the InToOut error cannot be reduced only by increasing neighbor nodes. As in Fig. 2 , a selected neighbor node N is further from the anchor nodes A, B, and C whatever the positon of the sensor node M is M1 or M2.
PPT Slide
Lager Image
the far case
Based on the distance between N and M, the real position of M can be decided.
  • (1) If M is at M1, which means that M is out of the triangle, the distance between N and M can be very small even near to zero.
  • (2) If M is at M2, the minimal distance between N and M is equal to the distance between M1 and M2. Here, the distance between M1 and M2 is assumed as twice as the minimal distance from M to each edge of the triangle.
Therefore, the result whether M is in or out of the triangle can be decided by a proper distance threshold set as twice as the minimal distance from M to each edge. If a selected neighbor is further from all anchors and the distance between it and the sensor is smaller than the provided distance threshold, the sensor node is out of the triangle area. On the contrary, the test result by the original APIT is regarded as invalid. Obviously, the InToOut error can be decreased by the distance threshold so long as the neighbor nodes are enough.
However, the distance threshold cannot be set accurately since the trilateration method [27] shown in Fig. 2 has no solution with irregular RSSI usually. To provide an approximately proper distance threshold with the irregular RSSI, the relationship between RSSI and the distance is analyzed at first.
- 2.3 The influence of irregular RSSI on PIT
Many off-line RSSI values measured by sensor nodes were collected and saved into the database to observe the relationship between RSSI and the distance.
The test requires a heterogeneous WSN composed of two sets of nodes distributed across a planar localization space: a set of anchors served as reference points, and a set of common sensor nodes whose locations are unknown. Both anchors and sensor nodes are equipped with the same hardware, omni-directional antennas and RF transceivers with built-in RSSI circuitry.
The statistic results of the collected RSSI are shown in Fig. 3 . In Fig. 3 , each point is the average value of six thousands RSSI collected at one same place, and the line is a fitting curve by the Log-D model.
PPT Slide
Lager Image
the relationship between RSSI and the distance.
Based on Fig. 3 , some conclusions can be proposed as follows:
  • (1) RSSI received by a sensor node at one place may be same to the value measured at another place.
  • (2) The larger is the distance, the smaller are both the RSSI value and the RSSI D-Value between a value measured at a place and the value at the adjacent place.
  • (3) The larger is RSSI, the smaller is the difference between the average RSSI and the theory value at one place.
Thus, two problems need to be solved to improve the location accuracy of IAPIT further, and they are shown as follows:
  • (1) How to calculate the proper distance threshold with the irregular RSSI under the condition that the trilateration method has no solution as mentioned above.
  • (2) It needs to prevent the InToOut error and the OutToIn error increasing with the irregular RSSI.
To provide approximate solution to the first problem, the probable location of a sensor node is calculated by Formula 1. Based on the aforementioned conclusions, two anchors with the large RSSI are selected to calculate the sensor node’s coordinates.
PPT Slide
Lager Image
where ( x , y ) are the sensor’s Cartesian coordinates, ( x 1 , y 1 ) and ( x 2 , y 2 ) are the coordinates of the anchors, d 1 and d 2 are the distances between the sensor node and each anchor node, and their values can be calculated by the Log-D model.
However, Formula 1 may also have no solution. To propose an approximate distance threshold of IAPIT by Formula 1, three cases are analyzed as follows.
Case A: Formula 1 has only one solution
The threshold is set equal to zero since the sensor node is near to the edge of the triangle. The result of IAPIT is that the sensor node is out of the triangle. In this case, the edge effect [7] cannot be avoided by the original APIT and IAPIT.
Case B: Formula 1 has two solutions
Firstly, calculating the distance of the two solutions. If it is smaller than a given value θ , the threshold and the IAPIT result are the same as Case A. The value of θ doesn’t affect the accuracy of IAPIT significantly with enough neighbors, however its proper value may reduce the computation complexity. If not, deciding which solution is in the triangle area secondly. If both of them are out of the triangle, the case is same as Case A. If there is one solution in the triangle, the threshold is set equal to twice as the minimal distance from the solution to each edge of the triangle. In this case, the InToOut error can be reduced by IAPIT when neighbor nodes are many.
Case C: Formula 1 has no solution
The threshold is very large by definition. The current result that the sensor node is out of the triangle by IAPIT is regarded as invalid. In this case, though the threshold is very small, there is a neighbor node satisfied with the IAPIT’s condition whether the sensor node is in or out of the triangle. The scenario is shown in Fig. 4 .
PPT Slide
Lager Image
the case that Formula 1 has no solution
The approximate proper distance threshold of IAPIT has been discussed above in the far case. Now, the key point is to make a proper decision whether a neighbor node of a sensor node is closer to or further from three anchor nodes simultaneously by the comparison of the irregular RSSI.
3. FIAPIT system
To solve the aforementioned second problem, an approach combined the fuzzy theory with IAPIT is proposed and named FIAPIT. The outputs of FIAPIT are weights of interaction areas of many triangle areas. They are range values belonged to [0, 1] but not certain values such as 0 or 1 by IAPIT or the original APIT.
- 3.1 The structure of FIAPIT
High level overview of FAPIT is illustrated in Fig. 5 . FAPIT can be divided into three phases: (1) beacon exchange phase, (2) fuzzy interference phase, and (3) computation phase. The first step is to collect RSSI by sensor nodes from broadcast beacons of anchors and neighbors. The second phase is the core of FIAPIT, including fuzzification, fuzzy interference and defuzzification. IAPIT is the theoretical principle of the fuzzy interference. The defuzzification results are regarded as weights of intersection areas of triangles. At last, the coordinates of a sensor are computed by the grid SCAN algorithm [7] . However, the intersection area’s increment for an inside decision or its decrement for an outside decision is its weight inferred by FIAPIT in this paper not 1 or -1 in paper [7] . Thus, the coordinates of the sensor are the weighted average values of COGs of intersection areas with large weights instead of COG of the maximum overlapping intersection area in paper [7] .
PPT Slide
Lager Image
high level view of FAPIT
- 3.2 Beacon exchange
To compute the coordinates of a sensor node by FIAPIT, the information that includes coordinates of anchors, RSSI for each anchor heard, RSSI measured by neighbors for each anchor and identifications of every node, are maintained as a table by the sensor node. After every sensor node received anchors’ broadcast beacons, they record RSSI and coordinates for each anchor node heard. And then they exchange the information with their neighbor nodes which are in the communication ranges of themselves. The information are recorded and combined to form an info table by each sensor at last. Based on the info table, the sensor node can execute FIAPIT and locate by itself. On the contrary, in a centralized localization manner, the table of each sensor node is maintained by a computer and FIAPIT is computed by the computer. In the case, the coordinates of anchors are not broadcast to sensors since they are recorded permanently by the computer. In the scenario of moving sensors, the historical RSSI of themselves are recorded and regarded as virtual neighbor nodes.
- 3.3 Fuzzification
K anchors with large RSSI are selected to calculate the coordinates of a sensor node based on the conclusions in section 2. Thus,
PPT Slide
Lager Image
triangular areas formed by the selected anchors need to be tested by IAPIT. The larger is K , the more complex is the location algorithm.
- 3.3.1 Membership function
In the fuzzy system, three fuzzy sets of input variables are established. They are the far set (marked as L), the near set (H) and the static set (Z). In the original APIT or IAPIT, the Z set is equal to the constant value zero, and the H set represents the near case, and L represents the far case. In FIAPIT, the Z set belongs to the range [ α , β ], H belongs to [ β , 90] and L belongs to [ t , α ]. Obviously, Z is equal to the intersection set of H and L and marked as Z=H∩Z. Usually, α is equal to the minus β ( β >0) and their values are related to the degree of irregularity (DOI) [7] . The floor level t can be set equal to -90dBm. However, its value is set much larger than -90 in FIAPIT to weaken negative influences of very far neighbors and reduce the algorithm’s complexity. Meanwhile, t is much smaller than the RSSI D-Value between a sensor and its neighbor while the distance between them is smaller than the approximate distance threshold in Case B in the subsection 2.3. The membership functions of the three fuzzy sets are defined as follows, and shown in Fig. 6 .
PPT Slide
Lager Image
the membership function
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where parameter P is the fuzzification level involved to enable adaptation to various DOI. The value of P ∈[0,1] controls the width of the fuzzy set region.
- 3.3.2 Fuzzy Inference Engine
The fuzzy inference engine is the Mandani’s rules, with a maximum value defuzzification method and a singleton input fuzzificator. The fuzzy engine evaluates the antecedent of every rule by the intersection of the fuzzy inputs, and uses the multiplication function for the AND operator, and the maximum function for the OR operator.
Based on the information maintained by each sensor, a RSSI D-Value between a sensor’s RSSI for an anchor heard and the value of its neighbor is fuzzificated as a fuzzy input. The membership degrees of all fuzzy inputs in one test are shown in Table 1 .
the membership degrees of all neighbor nodes
PPT Slide
Lager Image
the membership degrees of all neighbor nodes
In Table 1 , K is the number of the selected anchors, F is the number of neighbors in the communication range of a sensor node, ∞ is an invalid value that represents the RSSI D-Value that is smaller than the floor level t of the L set or the case that a neighbor node can’t receive the anchor’s beacon.
Based on Table 1 , IAPIT is executed in each triangular area formed by any three anchors. The membership degree of each triangle is analyzed after the variables defined.
Di : the triangle area, and D = { Di ,| i =1, 2, … ,
PPT Slide
Lager Image
( K ≥3)}.
Dij : each anchor of the triangle area Di , where j =1, 2, 3.
PPT Slide
Lager Image
: the membership degree of the RSSI D-Value, where l =1, 2, … , L , and L is the number of neighbor nodes except those whose membership degrees are ∞ in the triangle Di .
μ Di : the membership degree of the triangle where the sensor node belongs. If it’s zero, it means the sensor node is out of the triangle; if it’s one, the sensor node is in.
μ Λi : the membership degree of the intersection area formed by many triangle areas, Λ i is the i -th intersection area, i
PPT Slide
Lager Image
.
To distinguish the near/far case,
PPT Slide
Lager Image
is set with the plus or minus sign. When
PPT Slide
Lager Image
= μ H (x), it’s marked as plus.
PPT Slide
Lager Image
= μ L (x), it’s minus, and
PPT Slide
Lager Image
= μ z (x), it’s zero. The membership degree μ Di is inferred in three cases.
Case A: S>0, where S is the number of the neighbors whose membership degrees including
PPT Slide
Lager Image
are all larger than zero.
The membership degree is calculated by APOT and the result is:
PPT Slide
Lager Image
Case B: S=0, W>0, where W is the number of neighbors whose membership degrees are all smaller than zero.
Here, a flag variable Dis is set to distinguish whether the test result by IAPIT is valid or not, and its value is set zero in default. When Dis is one, the test result that the sensor node is out of the triangle is invalid. In the far case, the membership degree of μ Di is computed by IAPIT in three cases based on subsection 2.3.
Case one: Formula 1 has no solution
Dis is set equal to one. The current IAPIT test is interrupted and the next triangular area is to be tested by IAPIT.
Case two: Formula 1 has only one solution
In this case, the sensor node is out of the triangle by IAPIT. The membership degree is calculated by Formula 6.
PPT Slide
Lager Image
Case three: Formula 1 has two solutions, such as M i ,1 and M i ,2 .
In this case, the pseudo codes for IAPIT with the distance threshold are given as follows:
// θ is a given value mentioned in section 2.3
If
PPT Slide
Lager Image
Di is the same as Case two.}
Else if (M i ,1 is out && M i ,2 is out) {μ Di is the same as Case two.}
Else {
  • // assuming that Mi,1is in the triangle
  • is the distance from Mi,1to edgeDij,k
  • // formed by anchorsDijandDik
  • //δis the approximate distance threshold
  • G=0;
  • // L is the number of neighbor nodes without membership ∞
  • For (index=0; index
  • //Nindexis the index-th neighbor node
  • If
  • If (G>0) {
PPT Slide
Lager Image
  • } Else {Dis=1}
}
Case C: otherwise, the sensor node M is in the triangle area Di , and μ Di = 1. For example, S=0 and W=0, or Dis =1 etc.
After all sub-areas in the assemblage D are tested by IAPIT, the membership degree of each intersection area μ Λi can be calculated by Formula 8.
PPT Slide
Lager Image
where NumIN is the number of the triangular areas sharing the same intersection area Λ i .
- 3.4 Defuzzification and Position
The last step of FIAPIT is to estimate the sensor node’s coordinates by Formula 9.
PPT Slide
Lager Image
where ( X Λi , Y Λi ) calculated by the grid SCAN algorithm are the Cartesian coordinates of the intersection area’s COG; ω Λi is the weight of the intersection area Λ i and is equal to the defuzzfication result μ Λi in number; N Λ is the total number of intersection areas. When it’s far to outweigh three, three intersection areas with the large weights are selected to calculate the coordinates of the sensor node.
A special situation should be considered is that N Λ is zero. If the number of anchor nodes heard by the sensor node is larger than three, the position of the sensor node is COG of the area formed by anchor nodes. The coordinates of COG are calculated by WCL, and the weight of each anchor node is calculated by Formula 10. Otherwise, the coordinates of the sensor node will be calculated at next time.
PPT Slide
Lager Image
where ω i,j is the anchor’s weight, di,j calculated by the Log-D model is the distance between the sensor node i and the anchor j , and g is a degree and set to one in this paper.
4 Numerical simulation results
To demonstrate the improvements of the original APIT, results of four algorithms, including WCL, the original APIT, IAPIT and FIAPIT, are compared and analyzed by Matlab. The numerical simulation scenario is established in NS2 (Network Simulator version 2), and RSSI is collected into a database.
Sensors need to be located and anchors are distributed in a rectangular terrain with areas 10R*10R in two manners.
  • Random: it distributes all sensor nodes and anchors randomly throughout the terrain.
  • Uniform: the terrain is partitioned into grids and sensor nodes and anchors are evenly divided amongst these grids (random distribution inside each grid).
Some system parameters that are similar to the paper [7] and may have influences on the accuracies of the four algorithms are analyzed, include varying 1) placement, 2) Anchors Heard (AH), 3) target sensor Node Density (ND), 4) Anchor to Node Range ratio (ANR), and 5) radio propagation patterns. In addition, the location errors with varying the fuzzification level P, and the fuzzy set boundary α and β are analyzed in this paper.
In most numerical simulations, the default system parameters are set to AH=16, ND=8, ANR=10, P=0.5 and β =- α =1. The parameter θ is set to 0.01 R ( R , the sensor node’s radio transmission range used for normalization only) and t is -10dBm. K is set equal to the number of the anchor nodes heard by the target sensor node, since the influence of DOI on RSSI is regardless of the distance between the sensor and the anchor. However, in reality, K is set smaller than the number of anchors heard as aforementioned, to weaken the influence of the small RSSI heard from very far anchors, and to reduce the computation complexity.
The location estimation error is defined as the Euclidian distance between the real location of a sensor node and its estimated location. The average location error normalized by R as the metric is used to evaluate the accuracy of the location estimation. It is defined as the mean of location estimation errors collected over all determined sensor nodes.
- 4.1 Radio propagation model
The parameter DOI defined in [7] and [15] is the maximum signal straight variation per unit degree change in the direction of radio propagation. The large DOI represents the large variation of the radio irregularity. When it is 0, the radio model is a perfectly circle with no variation in the signal straight.
Based on the DOI radio propagation model, the received signal strength can be calculated at any specific point within the radio range of a transmitter, and defined as C × K ( θ )/ d 2 . Here, it is modified as | C × K ( θ )/ d 2 | due to the minus K ( θ ). In the model, C is a constant, d is the distance between a sensor node and an anchor node, θ ∈ [0, 360°), and K ( θ ) is the coefficient representing the difference in path loss in different directions. K ( θ ) is calculated by Formula 11, where rand is a random number uniformly distributed in the range [-1, 1], s=⌊ θ ⌋, and t =⌈ θ ⌉.
PPT Slide
Lager Image
Fig. 7 shows the examples of DOI=0.1 and DOI=0.2. In Fig. 7 , every point of the green bold curves is the average value of RSSI, which is measured 10 times at one same place in an interval and filtered by Gaussian Filter. Obviously, the filtered RSSI is closer to the ideal value than the original value. However, it increases the network communication pressure to achieve the perfect RSSI by this way.
PPT Slide
Lager Image
Irregular radio patterns for different values of DOI
- 4.2 The influence of Anchors Heard
The average number of AH can be changed by varying anchor’s number or varying ANR. Thus, the location errors are analyzed in two cases.
Case A: varying the anchor node’s number
The quantity of anchors is varying in the Uniform placement and the Random placement to demonstrate influences of the anchors’ number and the placement on location errors. DOI is zero and other parameters are in default. The results are shown in Fig. 8 .
PPT Slide
Lager Image
errors under varying AH
The conclusions are proposed: (1) the errors of IAPIT are almost equal to the original APIT, and they are near to WCL when AH is larger than ten; (2) the errors of WCL are lowest and the performance of FIAPIT is worst; (3) the Uniform placement has better performance than the Random placement.
Here, IAPIT is similar to the original APIT because: (1) the near/far case can be inferred accurately by them when DOI=0; (2) there are few neighbor nodes to satisfy the distance threshold in the far case. The reason that WCL has the highest accuracy is that the weights of WCL is proper due to the ideal RSSI. Since the near/far case is fuzzified by FIAPIT with the default parameters, many near/far cases are considered as the static cases so that the triangle areas cannot be narrowed down properly. However, it can achieve at high accuracy with proper fuzzy parameters and will be introduced next.
Case B: varying Anchor to Node Range ratio
The terrain is set larger than 20R*20R to observe the influences of ANR from 1 to 20. AH is set equal to 16 when ANR is small, DOI is 0.1 and other parameters are in default. The location errors under varying ANR are shown in Fig. 9 .
PPT Slide
Lager Image
the location errors under varying ANR
The analyses of Fig. 9 are shown as follows: (1) the accuracies of the four algorithms decrease with the increasing ANR which leads to anchor nodes decreasing; (2) the location errors of the original APIT are improved by IAPIT and FIAPIT when ANR is smaller than 3 due to the InToOut error is decreased with enough anchors that are also neighbors of a sensor; (3) the errors of WCL are larger than the other algorithms when ANR is larger than 4 due to the few anchor nodes and the irregular RSSI; (4) WCL is better than others in the random placement since errors of test results by the original APIT or IAPIT are increasing when nodes placed randomly; (5) FIAPIT is better than other algorithms when DOI is 0.1.
The conclusion (2) indicates that the edge effect is improved by IAPIT with the distance threshold. And, FIAPIT has the best performance on reducing the edge effect, because the intersection area which the sensor node resides in or closes to the edge of is with a proper weight not zero. The location accuracy is improved obviously by FIAPIT due to the proper weights. For example, when a sensor node and its neighbor are both in a triangle, however, the neighbor’s RSSI heard from three anchors are little larger than the sensor’s due to DOI. In this case, the test result is incorrect by the original APIT or IAPIT, however, it’s correct by FIAPIT with the membership functions.
Base on Case A and Case B, the Uniform placement has the better accuracy than the Random, so the Uniform placement is used in the rest of the simulations.
- 4.3 The influence of sensor Node Density
The simulation results of all algorithms with varying ND are shown in Fig. 10 .
PPT Slide
Lager Image
the location errors under varying ND
Some conclusions are shown as follows: (1) the influence of ND on WCL is little, since WCL does not rely on neighbor nodes; (2) location errors of the other algorithms except WCL decrease obviously with ND increasing when ND is smaller than 18; (3) the location errors of the original APIT increase slightly when ND is larger than 18, however IAPIT and FIAPIT are on the contrary.
Increasing ND reduces the OutToIn error of the algorithms except WCL. Thus, the location accuracy is improved obviously. However, when ND is very large, the errors of the original APIT increase due to the InToOut error of the edge effect. This edge effect is improved by IAPIT and FIAPIT with the proper distance threshold. Thus, the location errors continue to decrease but slightly. FIAPIT has the best performance on reducing the influence of DOI.
- 4.4 The influence of DOI
The range-free method is usually based on the assumption that RSSI is a decreasing function of the distance. However, the assumption is not always correct when DOI is large. Therefore, the stabilities of the four algorithms are analyzed by varying DOI. The results are shown in Fig. 11 .
PPT Slide
Lager Image
location errors under varying DOI
In Fig. 11 , the sub figure (a) shows the results of the four algorithms with default parameters, the parameters of (b) are the same as (a) except that ND is 18, and (c) is same to (a) except ANR=6.
Analyses of Fig. 11 are concluded as: (1) the location errors increase with DOI increasing; (2) the original APIT, IAPIT and FIAPIT have the better anti-interference performance than WCL; (3) IAPIT is better than APIT when ND is large; (4) the errors don’t decrease by increasing anchor nodes when DOI is very large; (5) FIAPIT with fixed fuzzy parameters is worse than other algorithms when DOI is smaller than 0.1. However, its accuracy can be improved by varying parameters P, α and β .
The larger is DOI, the more irregular is RSSI. Each anchor’s weight is very inaccurate due to the influence of the irregular RSSI. Thus, WCL has a bad performance on the location accuracy. While, increasing ND decreases location errors of IAPIT though DOI is large, because it reduces the OutToIn error and makes more neighbors satisfy the approximate inaccurate distance threshold to reduce the InToOut error. FIAPIT is better than IAPIT since the test errors by IAPIT are weakened by the fuzzification outputs.
- 4.5 Location errors under varying P,αandβ
Based on the analyses of varying DOI, the fuzzification level should be set properly by varying parameters P, α or β , to adapt to the changeable DOI. In Fig. 6 , the area of Z is only related to α and β . The larger is β or the smaller is α , the larger is the area. It means that the large RSSI D-Value in FIAPIT is considered as “zero” to reduce the influence of a sudden change of RSSI with a large DOI in coarse-grain. Varying P can also change the membership degree of each set in fine-grain when α and β are fixed. Thus, varying P, α and β properly can adapt to the different DOI. In simulations, DOI is set to 0.1, 0.3 and 0.5 to demonstrate the influences of different parameters on the location errors. The simulation results are shown in Fig. 12 .
PPT Slide
Lager Image
the location errors under varying P, α and β with different DOIs
In Fig. 12 , conclusions are proposed as follows: (1) when DOI is small, β or minus α increases and P decreases with DOI increasing; (2) the influences of varying α or β on location errors are larger than varying P, since the ranges of fuzzy sets are changed obviously by varying α or β ; (3) the accuracy can be improved slightly by varying parameters when DOI is very large.
Obviously, proper values of α , β and P set by the relationships between them and DOI decrease influences of the RSSI inaccuracy on location accuracies. To set proper values when DOI is unknown in reality is introduced. Firstly, α and β are discussed based on the conclusion (1) and (2).
In Fig. 6 , when the RSSI D-Value of a sensor’s RSSI and its neighbor’s is β , the probability that the distance between the sensor and the anchor heard is equal to the distance between the sensor’s neighbor and the same anchor heard is 0.5. On the assumption that RSSI values measured by a sensor at the same place obey the Gauss Distribution, the probability that the RSSI value ( μ +1.18 σ ) measured by the sensor at the same place belongs to the Gauss distribution is 0.5, where μ and σ are the mean and standard deviation of the Gauss Distribution. Thus, β (=- α ) is set equal to 1.18 σ in reality.
Based on Fig. 12 and conclusion (1), P is decreasing with β increasing. The formula proposed based on the relationship between P and β is shown as Formula 12.
PPT Slide
Lager Image
The simulation results by varying DOI are shown in Fig. 13 to demonstrate the proper parameters’ values set dynamically by formulas. Other parameters are set as default. The results also include errors of varying P by Formula 12.
PPT Slide
Lager Image
the location errors by varying P, α, β and DOI
In Fig. 13 , some conclusions are proposed as follows: (1) combined with Fig. 12 , the value of P calculated by Formula 12 is nearer to the optimum value than the default, and it decreases with β increasing; (2) increasing β can improve location accuracies with DOI increasing; (3) FIAPIT with dynamic parameters is better than it with fixed parameters, and it’s obvious when DOI is small.
When DOI is small, the variance of RSSI measured at the same place is small and the value β is small, but P is large. Thus, a few difference between RSSI measured by a sensor and the value measured by its neighbor is considered as near or far due to the accurate RSSI. For example, when DOI is zero, β and α are set to zero, and P is one. In the case, the test result of narrowing down areas by FIAPIT is same to the result by IAPIT. However, the localization accuracy of FIAPIT is better than IAPIT’s, since the coordinates are calculated with many intersection areas by FIAPIT not only one with the largest weight by IAPIT.
When DOI is large, varying P can’t compensate for RSSI inaccuracy with a small fixed β . It’s obvious when the standard deviation of RSSI measured at the same place is larger than the small fixed β . By the formulas, the dynamic value of β is large and P is small. Thus, large RSSI D-Value is considered as static to reduce errors of narrowing down areas.
As shown in all simulations, IAPIT is better than APIT since the InToOut error is decreased especially when ND is larger than 18. To improve location accuracies, other parameters are set as: AH>10 and ANR is from 4 to 8. FIAPIT with dynamic parameters is better than IAPIT due to the compensation for RSSI inaccuracy.
5. Conclusion
This paper presents a novel range-free localization method, called FIAPIT, which is a combination of an improved APIT (IAPIT) and a fuzzy logic system. IAPIT improves the original APIT in the near and far cases partly. In the near case, the original APIT that is re-proved is always correct. On the contrary, IAPIT provides a proper distance threshold to decrease the InToOut error due to the edge effect of the original APIT. Fuzzy logic inference based on IAPIT, as a part of FIAPIT, helps to manage uncertainties associated with the irregular RSSI by the influence of DOI. The proper weights of intersection areas of triangles are given by the defuzzification results of FIAPT. Finally, the coordinates of a sensor node are computed by the weighted average of COGs of the intersection areas narrowed down by FIAPIT. Numerical simulations were performed and the results demonstrate that IAPIT is better than APIT when the Node Density is large enough. In addition, FIAPIT with dynamic parameters performs better than other range-free algorithms due to compensations for RSSI inaccuracy. To improve the location accuracy by other methods and to balance the location accuracy and the power consumption are the further works.
BIO
Xiangfeng Li received the BS from Tianjin University in 1987. Now, he is working as a professor and doctoral supervisor at Hefei Institutes of Physical Science, Chinese Academy of Sciences. His research interests include Network Manage and Auto-Control.
LiangFeng Chen received the MS from Hefei University of Technology in 2011. Now, he is PhD candidate at University of Science and Technology of China and Institute of Intelligent Machines, Chinese Academy of Sciences. His research interests include Network Security and Wireless Sensor Network.
JianPing Wang is working as a professor and doctoral supervisor in School of Electric Engineering and Automation at Hefei University of Technology. His research interests include Wireless Sensor Network and Pattern Recognition.
Zhong Chu is working at Hefei University as a professor. His main research interest is on automatic control.
Qiyue Li is working as professor and postgraduate supervisor in School of Electric Engineering and Automation at Hefei University of Technology. His main research interest is Wireless Sensor Network.
Wei Sun is a faculty member in School of Electric Engineering and Automation at Hefei University of Technology. His main research interest includes wireless sensor network, sensor development, embedded system, and controls.
References
Akyildiz I.F. , Su W. , Sankarasubramaniam Y. , Cayirci E. 2002 “Wireless sensor networks: a survey” Comput. Networks 38 (4) 393 - 422    DOI : 10.1016/S1389-1286(01)00302-4
Yick J. , Mukherjee B. , Ghosal D. 2008 “Wireless sensor network survey,” Comput. Networks 52 (12) 2292 - 2330    DOI : 10.1016/j.comnet.2008.04.002
Chung W. , Lee Y. , Jung S. “A wireless sensor network compatible wearable U-healthcare monitoring system using integrated ECG, accelerometer and SpO2,” in Proc. of 30th Annu. Int. Conf. IEEE Eng. Med.Biol. Soc., EMBS2008 2008 1529 - 1532
Boukerche A. , Oliveira H.A.B. F , Nakamura E.F. , Loureiro A.A.F. 2008 “Secure localization algorithms for wireless sensor networks,” Communications Magazine, IEEE 46 (4) 96 - 101    DOI : 10.1109/MCOM.2008.4481347
Karl H. , Willing A. 2005 “Protocols and Architectures for Wireless Sensor Networks,” John Wiley & Sons
Nicolescu D. , Nath B. 2003 “DV based positioning in ad hoc networks,” Journal of Telecommunication Systems 22 (1) 267 - 280    DOI : 10.1023/A:1023403323460
He T. , Huang C. , Blum B.M. , Stankovic J.A. , Abdelzaher T. “Range-free localization schemes for large scale sensor networks,” in Proc. of the 9th Annual International Conference on Mobile Computing and Networking(MobiCom 2003) 2003 81 - 95
Mao G. , Fidan B. , Anderson B. 2007 “Wireless sensor networks localization techniques,” Computer Networks 51 (10) 2529 - 2553    DOI : 10.1016/j.comnet.2006.11.018
Bulusu N. , Heidemann J. , Estrin D. 2000 “GPS-less low-cost outdoor localization for very small devices,” Personal Communications, IEEE 7 (5) 28 - 34    DOI : 10.1109/98.878533
Gao Guo Qing , Lei Lin “An improved node localization algorithm based on DV-HOP in WSN,” in Proc. of 2nd IEEE Int. Conf. Adv. Comput. Control, ICACC 2010 vol. 4 321 - 324
Shon Minhan , Jo Minho , Choo Hyunseung 2012 “An interactive cluster-based MDS localization scheme for multimedia information in wireless sensor networks,” Computer Communications 35 (15) 1921 - 1929    DOI : 10.1016/j.comcom.2012.05.002
Zhou Y. , Ao X. , Xia S. “An improved APIT node self-localization algorithm in WSN,” in Proc. of World Congr. Intelligent Control Autom. WCICA 2008 7582 - 7586
Blumenthal J. , Grossmann R. , Golatowski F. , Timmermann D. “Weighted centroid localization in Zigbee-based sensor networks,” in Proc. of IEEE International Symposium on Intelligent Signal Processing (WISP2007) 2007 1 - 6
Schuhmann S. , Herrmann K. , Rothermel K. , Blumenthal J. , Timmermann D. “Improved weighted centroid localization in smart ubiquitous environments,” in Proc. of 5th International Conference, UIC 2008 vol. 5061 20 - 34
Liu C. , Scott T. , Wu K. , Hoffman D. 2007 “Range-free sensor localization with ring overlapping based on comparison of received signal strength indicator,” International Journal of Sensor Networks (IJSNet) 2 (5) 399 - 413    DOI : 10.1504/IJSNET.2007.014364
Behnke R. , Salzmann J. , Grobsmann R. , Lieckfeldt D. , Timmermann D. , Thurow K. “Strategies to overcome border area effects of coarse grained localization,” in Proc. of Workshop Positioning, Navig. Commun. WPNC 2009 95 - 102
Whitehouse K. , Karlof C. , Culler D. 2007 “A practical evaluation of radio signal strength for ranging-based localization,” ACM SIGMOBILE Mobile Computing and Communications Review 11 (1) 41 - 52    DOI : 10.1145/1234822.1234829
Mao G , Anderson BDO , Fidan B. 2007 “Path loss exponent estimation for wireless sensor network localization,” Computer Networks 51 (10) 2467 - 2483    DOI : 10.1016/j.comnet.2006.11.007
Ahn Hyo-Sung , Yu Wonpil 2009 “Environmental-adaptive RSSI-based indoor localization,” IEEE Transactions on Automation Science and Engineering 6 (9) 626 - 633
Zhan Jie , Liu Hongli , Tan Jian 2010 “Research on ranging accuracy based on RSSI of wireless sensor network,” Telecommunication Engineering 50 (4) 83 - 87
Milioris Dimitris , Tzagkarakis George , Papakonstantinou Artemis , Papadopouli Maria , Tsakalides Panagiotis 2014 “Low-dimensional signal-strength fingerprint-based positioning in wireless LANs,” Ad Hoc Networks 12 100 - 114    DOI : 10.1016/j.adhoc.2011.12.006
Larios D.F. , Barbancho J. , Molina F.J. , León C. 2012 “LIS: Localization based on an intelligent distributed fuzzy system applied to a WSN,” Ad Hoc Networks 10 (3) 604 - 622    DOI : 10.1016/j.adhoc.2011.11.003
Garcia-Valverde T. , Garcia-Sola A. , Hagras H. , Dooley J.A. , Callaghan V. , Botia J.A. 2013 “A Fuzzy Logic-Based System for Indoor Localization Using WiFi in Ambient Intelligent Environments,” IEEE Transactions on Fuzzy Systems 21 (4) 702 - 718    DOI : 10.1109/TFUZZ.2012.2227975
Li Zechao , Liu Jing , Yang Yi , Zhou Xiaofang , Lu Hanqing 2014 “Clustering-Guided Sparse Structural Learning for Unsupervised Feature Selection,” Knowledge and Data Engineering, IEEE Transactions on 26 (9) 2138 - 2150    DOI : 10.1109/TKDE.2013.65
Li Z. , Liu J. , Tang J. , Lu H. 2015 “Robust Structured Subspace Learning for Data Representation,” Pattern Analysis and Machine Intelligence, IEEE Transactions on (99) 1 - 15
Zhou Yong , Xia Shixiong , Ding Shifei , Zhang Lei , Ao Xin 2009 “An Improved APIT Node Self-Localization Algorithm in WSN Based on Triangle-Center Scan,” Journal of Computer Research and Development 46 (4) 566 - 574
Liu Hunghuan , Lo Weihsiang , Tseng Chihcheng , Shin Hawyun 2014 “A WiFi-Based Weighted Screening Method for Indoor Positioning Systems,” Wireless Personal Communications 79 (1) 611 - 627    DOI : 10.1007/s11277-014-1876-y