{'fraction_non_alphanumeric': 0.027758021179073812, 'fraction_numerical': 0.00887071281808124, 'mean_word_length': 4.60480566936109, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Range-free Area Localization Scheme for Wireless Sensor Networks

For large wireless sensor networks, identifying the exact location of every sensor may not be feasible and the cost may be very high. A coarse estimate of the sensors’ locations is usually sufficient for many applications. In this chapter, we describe an efficient Area Localization Scheme (ALS) for wireless sensor networks. ALS is a range-free scheme that tries to estimate the position of every sensor within a certain area rather than its exact location. Furthermore, the powerful sinks instead of the sensors handle all complex calculations. This reduces the energy consumed by the sensors and helps extend the lifetime of the network. The granularity of the areas estimated for each node can be easily adjusted by varying some system parameters, thus making the scheme very flexible. We first study ALS under ideal two-ray physical layer conditions (as a benchmark) before proceeding to test the scheme in more realistic non-ideal conditions modelled by the two-ray physical layer model, Rayleigh fading and lognormal shadowing. We compare the performance of ALS to range-free localization schemes like APIT (Approximate Point In Triangle) and DV (Distance Vector) Hop, and observe that the ALS outperforms them. We also implement ALS on an experimental testbed and, show that at least 80% of nodes lie within a one-hop region of their estimated areas. Both simulation and experimental results have verified that ALS is a promising technique for range-free localization in large sensor networks.


Introduction
Deployment of low cost wireless sensors is envisioned to be a promising technique for applications ranging from early warning systems for natural disasters (like tsunamis and wildfires), ecosystem monitoring, real-time health monitoring, and military surveillance. The deployment and management of large scale wireless sensor networks is a challenge because of the limited processing capability and power constraints on each sensor. Research issues pertaining to wireless sensor networks, from the physical layer to the application layer, as well as cross-layer issues like power management and topology management, have been addressed [1]. Sensor network data is typically interpreted with reference to a sensor's location, e.g. reporting the occurrence of an event, tracking of a moving object or monitoring the physical conditions of a region. Localization, the process of determining the location of a sensor node in a wireless sensor network, is a challenging problem as reliance on technology like GPS [2] is infeasible due to cost and energy constraints, and also physical constraints like indoor environments. In very large and dense wireless sensor networks, it may not be feasible to accurately measure the exact location of every sensor and furthermore, a coarse estimate of the sensor's location may suffice for most applications. A preliminary design of the Area Localization Scheme (ALS) [3] has been proposed, which can only function in an (unrealistic) ideal channel and definitely not in a real environment with fading, shadowing and other forms of interference. In this chapter, we describe algorithms and techniques that will enable the Area Localization Scheme (ALS) to be deployable in a real environment. ALS is a centralized range-free scheme that provides an estimation of a sensor's location within a certain area, rather than the exact coordinates of the sensor. The granularity of the location estimate is determined by the size of areas which a sensor node falls within and this can be easily adjusted by varying the system parameters. The advantage of this scheme lies in its simplicity, as no measurements need to be made by the sensors. Since ALS is a range-free scheme, we compare its performance to other range-free schemes like APIT (Approximate Point In Triangle) [4], DV-Hop [5] and DHL (Density-aware Hopcount-based Localization) [6]. To validate our schemes, we first use simulations developed in Qualnet [31] to evaluate the performance of ALS and show that it outperforms other range-free localization schemes. We then follow with an implementation of ALS on a wireless sensor network test bed and conduct tests in both indoor and outdoor environments. We observe that at least 90% of nodes lie within a 1-hop region of their estimated areas, i.e. within their individual transmission radius. The rest of the paper is organized as follows. Section 2 provides a survey of related work on wireless sensor network localization. Section 3 then describes the key aspects of the basic Area Localization Scheme. Section 4 describes the simulation environment and evaluates the performance of the ALS and compares it to other range-free schemes. Section 5 discusses the performance of the ALS evaluated on a wireless sensor network test bed for both indoor and outdoor environments. This section also discusses how the ALS scheme is extended to a generic physical layer model from the two-ray model used in the simulation studies. Section 6 presents our conclusions and plans for future work.

Related Work
A number of localization schemes have been proposed to date. The localization schemes take into account a number of factors like the network topology, device capabilities, signal www.intechopen.com Range-free Area Localization Scheme for Wireless Sensor Networks 3 propagation models and energy requirements. Most localization schemes require the location of some nodes in the network to be known. Nodes whose locations are known are referred to as anchor nodes or reference nodes in the literature. The localization schemes that use reference nodes can be broadly classified into three categories: range-based schemes, range-free schemes and schemes that use signal processing or probabilistic techniques (hereafter referred to as probabilistic schemes). There also exist schemes that do not require such reference locations in the network.

A. Range-based Schemes
In range-based schemes, the distance or angle measurements from a fixed set of reference points are known. Multilateration, which encompass atomic, iterative and collaborative multilateration techniques, are then used to estimate the location of each sensor node. Range-based schemes use ToA (Time of Arrival), TDoA (Time Difference of Arrival), AOA (Angle of Arrival) or RSSI (Received Signal Strength Indicator) to estimate their distances to anchor nodes. UWB based localization schemes [7] [8], GPS [2], Cricket [9] and other schemes [11][12] [13] use ToA or TDoA of acoustic or RF signals from multiple anchor nodes for localization. However, the fast propagation of RF signals implies that a small error in measurement could lead to large errors. Clock synchronization between multiple reference nodes or between the sender and the receiver is also an extremely critical issue in schemes that use ToA or TDoA. AOA allows sensor nodes to calculate the relative angles between neighbouring nodes [14] [15]. However, schemes that use AOA entail sensors and reference nodes to be equipped with special antenna configurations which may not be feasible to embed on each sensor. Complex non-linear equations also need to be solved [15]. Schemes that use RSSI [16][17] [18] have to deal with problems caused by large variances in reading, multi-path fading, background interference and irregular signal propagation.

B. Range-free Schemes
Range-free localization schemes usually do not make use of any of the techniques mentioned above to estimate distances to reference nodes, e.g. centroid scheme [19] and APIT [4]. Range quantization methods like DV-Hop [5] and DHL [6] associate each 1-hop connection with an estimated distance, while others apply RSSI quantization [20]. These schemes also use multilateration techniques but rely on measures like hop count to estimate distances to anchor nodes. Range-free schemes offer a less precise estimate of location compared to range-based schemes.

C. Probabilistic Schemes
The third class of schemes use signal processing techniques or probabilistic schemes to do localization. The fingerprinting scheme [21], which uses complex signal processing, is an example of such a scheme. The major drawback of fingerprinting schemes is the substantial effort required for generating a signal signature database, before localization can be performed. Hence, it is not suitable for adhoc deployment scenarios in consideration.

D. Schemes without Anchor/Reference Points
The fourth class of schemes is different from the first three in that it does not require anchor nodes or beacon signals. In [22], a central server models the network as a series of equations representing proximity constraints between nodes, and then uses sophisticated optimization techniques to estimate the location of every node in the network. In [23], Capkun et al. propose an infrastructure-less GPS-free positioning algorithm.

E. Area-based Localization
Most of the localization schemes mentioned above calculate a sensor node's exact position, except for [4], which uses an area-based approach. In [4], anchor nodes send out beacon packets at the highest power level that they can. A theoretical method, based on RSSI measurements, called Approximate Point in Triangle (APIT), is defined to determine whether a point lies inside a triangle formed by connecting three anchor nodes. A sensor node uses the APIT test with different combinations of three audible anchor nodes (audible anchors are anchor nodes from which beacon packets are received) until all combinations are exhausted. Each APIT test determines whether or not the node lies inside a distinct triangular region. The intersection of all the triangular regions is then considered to estimate the area in which the sensor is located. The APIT algorithm performs well when the average number of audible anchors is high (for example, more than 20). As a result, a major drawback of the algorithm is that it is highly computationally intensive. An average of 20 audible anchors would imply that the intersection of 20 C 3 = 1140 areas need to be considered. Furthermore, the algorithm performs well only when the anchor nodes are randomly distributed throughout the network, which is not always feasible in a real deployment scenario.

Area Localization Scheme Fundamentals
In ALS, the nodes in the wireless sensor network are divided into three categories according to their different functions: reference nodes, sensor nodes and sinks.

A. Reference/Anchor nodes
The main responsibility of the reference/anchor (both terms will be used interchangeably) nodes is to send out beacon signals to help sensor nodes locate themselves. Reference nodes are either equipped with GPS to provide accurate location information or placed in predetermined locations. In addition, the reference nodes can send out radio signals at varying power levels as required. For an Ideal Isotropic Antenna, the received power at a distance d from the transmitter is given by: while the two-ray ground reflection model considers both the direct path and a ground reflection path, and the received power at a distance d is given by: where P r is the received power, P t is the transmitted power, d is the distance between the transmitter and receiver,  is the wavelength and, h t and h r are the heights of the transmitter www.intechopen.com Range-free Area Localization Scheme for Wireless Sensor Networks 5 and receiver respectively. G t and G r represent the gains of the transmitter and receiver respectively in equations (1) and (2). From the above equations, it can be clearly seen that if the received power is fixed at a certain value, the radio signal with a higher transmitted power reaches a greater distance. Using one of the physical layer models described above and the threshold power that each sensor can receive, the reference node can calculate the power required to reach different distances. Each reference node then devises a set of increasing power levels such that the highest power level can cover the entire area in consideration. The reference nodes then broadcast several rounds of radio signals. The beacon packet contains the ID of the reference node and the power level at which the signal is transmitted (which can be simply represented by an integer value, as explained below.) Let PS denote the set of increasing power levels of beacon signals sent out by a reference node. For now, let us assume that all the reference nodes in the system send out the same set PS of beacon signals. In the ALS scheme, a sensor node simply listens and records the power levels of beacon signals it receives from each reference node. In real environments, small scale fading and shadowing can cause the power levels received by the sensor nodes to vary significantly from the expected power levels calculated by the path loss models in equations (1) and (2). Sending out beacon signals in the set PS only once might lead to inaccurate beacon reception by sensor nodes. As a result, the reference nodes send out the beacon signals in set PS multiple times. The sensor nodes can then calculate the statistical average (mode or mean) of the received power levels from each reference node. Let the number of power levels in set PS be denoted by Np and the N p power levels in set PS be represented by P 1 ,P 2 , P 3 ,…,P Np . The power levels P 1 , P 2 , P 3 ,…,P Np can be represented by simple integers, e.g. increasing values corresponding to increasing power levels; therefore sensor nodes only need to take note of these integer values that are contained in the beacon packets and the hardware design can be kept simple as there is no need for accurate measurement of the received power level. Let the number of times that the same set of beacon signals PS are sent out be denoted by N r , also referred to as the number of rounds. The power MP in dB required to cover the entire area is calculated from equation (1) or (2), based on the physical layer model in consideration. The power LP in dB required to cover a small distance  (say 10 m) is also calculated. The values P 1 ,P 2 , P 3 ,…,P Np are then set to be N p uniformly distributed values in the range [LP, MP] in the dB scale. The simple procedure followed by the reference nodes is shown below: Send beacon signal at power levelP j 4 end for 5 end for The transmissions by the different reference nodes do not need to be synchronized. However, the reference nodes schedule the beacon signal transmissions so to avoid collisions. The transmitted set of power levels PS need not be the same for all the reference nodes, and can be configured by the network administrator. Also, the set of power levels PS need not be uniformly distributed too. It is also not necessary for the reference nodes to know each other's position and levels of transmitted power, but there should be at least one sink or a central agent that stores the location information of all the reference nodes.

B. Sensor node
A sensor node is a unit device that monitors the environment. Sensors typically have limited computing capability, storage capacity, communications range and battery power. Due to power constraints, it is not desirable forsensor nodes to make complex calculations and send out information frequently.

1) Signal Coordinate Representation:
In the ALS scheme, the sensors save a list of reference nodes and their respective transmitted power levels and forward the information to the nearest sink when requested or appended to sensed data. The sinks use this information to identify the area in which the sensors reside in. However, if the number of reference nodes is large, the packets containing location information may be long, which might result in more traffic in the network. A naming scheme is hence designed. The sensor nodes use a signal coordinate representation to indicate their location information to the sinks. Power contour lines can be drawn on an area based on the set of beacon signal power levels PS transmitted by each reference node, and their corresponding distances travelled. The power contour lines divide the region in consideration into many sub-regions (which we refer to as areas) as shown in Figure 1 below. Each area in the region can be represented by a unique set of n coordinates, hereafter referred to as the signal coordinate.
Suppose there are n reference nodes, which are referred to as R1, R 2,… , and R n. For a sensor in an area, let the lowest transmitted power levels it receives from the n reference nodes be S 1 , S 2, …, and S n respectively. S 1 , S 2, …, and S n are simple integer numbers indicating the different power levels rather than the actual signal strengths. The mappings between integer levels and the actual power values are saved at the reference nodes and sinks. The signal coordinate is defined as the representation < S 1 , S 2, …, S n > such that each S i , the i th element, is the lowest power level received from R i . For example, consider a square region with reference nodes at the four corners, as shown in Figure 1. In this case, the set of power levels PS is the same for all the four reference nodes and there are three power levels in the set PS. The smallest power level in the power set PS is represented by the integer 1 while the highest power level is represented by the integer 3. For each node, the contour lines drawn on the region represent the farthest distances that the beacon signals at each power level can travel. Contour lines for beacon power levels 1 and 2 are drawn. The power level 3 for each corner reference node can reach beyond the corner that is diagonally opposite to it and so, its corresponding contour line is not seen on the square region. Thus, for each reference node, the two contour lines corresponding to power levels 1 and 2 divide the region into three (arc) areas. es and ocation may receive localization signals (beacon messages)at different power levels from the same reference node, as explained above. The sensor records its signal coordinate and forwards the information to the sink(s) using the existing data delivery scheme, as and when requested.
Let the signal coordinate of a node be denoted <S 1 , S 2 ,…,S n > where n is the number of reference nodes. A sensor node uses variables L 11 , L 12, …,L 1Nr to represent the lowest power levels received by the sensor from reference node 1 during rounds 1 to N r. Similarly, let L i1 , L i2 ,…,L iNr represent the lowest power levels received by the sensor from reference node i during rounds 1 to N r. Let the number of reference nodes be n. Initially, all the values L 11 , L 12, …, L 1Nr , L 21 , L 22 , …, L 2Nr , …, L n1 , L n2 , …, L nNr are set to zero. The zeros imply that the sensor nodes have received no signals from the reference nodes.
The pseudo-code running on each sensor node is shown below. After initialization, the sensor nodes start an infinite loop to receive beacon messages from reference nodes and follow the algorithm shown below. Since a reference node sends out several rounds of beacon signals, the sensor node may hear multiple rounds of beacon signals from the same reference node. If the sensor receives a signal from reference node i for the first time during round j, it sets L ij to be the lowest received power level for that round; otherwise, if the received power level from reference node i in round j is lower than the current value in L ij , L ij is set to the latest received power level. After all the reference nodes have completed sending out beacon messages, the power levels L i1 to L iNr on each sensor represent the lowest power levels received from reference node i during rounds 1 to N r respectively. This concept is further illustrated by a couple of examples and we assume the same scenario as in Fig. 1. In Fig. 1, we have assumed ideal isotropic channel conditions and each element in the signal coordinate has been ascertained with a high confidence level. Fig. 2 illustrates scenarios of non-ideal channel conditions where beacons messages may be lost. Fig. 2(a) shows the case <{2,3},3,3,3>, where the first element of the signal coordinate is either 1 or 2. This happens when the lowest power level received from reference 1 during the N r rounds of beacon messages oscillates between 1 and 2. Both values (1 and 2) can be considered as possible candidates for S 1, if no power level L 1x occurs with frequency greater than CONFIDENCE_LEVEL in the set {L 11 , ..., L 1Nr }. The union of the black and red regions in Fig. 2(a) represents the region <0, 3, 3, 3>, where the value of 0 implies that there is no information available on the first element. This could happen in the case when no beacon packets are received from reference node 1, and the signal coordinate region <{1,2,3},3,3,3> is considered as a result. Thus, every element S i in the set <S 1 , S 2 , …,S n > need not be a unique value, but could be a set of values as shown in Fig. 2(b). While more than one element of a signal coordinate may have multiple values, we consider a signal coordinate to be valid only if at least half of its values have been determined with a high confidence level. From the above description, it can be clearly seen that the sensor nodes do not perform any complicated calculations to estimate their location. Neither do they need to exchange information with their neighbours.

C. Sink
In wireless sensor networks, data from sensor nodes are forwarded to a sink for processing. From a hardware point of view, a sink usually has much higher computing and data processing capabilities than a sensor node. In ALS, a sensor node sends its signal coordinate (location information) to a sink according to the data delivery scheme in use. The sensor itself does not know the exact location of the area in which it resides nor does it know what its signal coordinate represents. It is up to the sink(s) to determine the sensor's location based on the signal coordinate information obtained from the sensor. One assumption of the ALS scheme is that the sink knows the positions of all the reference nodes and their respective transmitted power levels, whether by directly communicating with the reference nodes, or from a central server, which contains this information. Therefore, with the knowledge of the physical layer model and signal propagation algorithms, the sink is able to derive the map of areas based on the information of the transmitted signals from the reference nodes. With the map and the signal coordinate information, the sink can then determine which area a sensor is in from the received data, tagged with the signal coordinate. In the ALS scheme, the choosing of the signal propagation model plays an important part in the estimation accuracy. For different networks, different signal propagation models can be used to draw out the signal map according to the physical layer conditions. An irregular signal model could divide the whole region into many differently shaped areas, as shown in Fig. 3. Any adjustments made to the underlying physical layer model will have no impact on the sensor nodes, which just need to measure their signal coordinates and forward them to the sink. An immediate observation is the diverse area granularity, which affects the accuracy of the location estimation. The granularity issue will be discussed in the next section.
A key advantage of ALS is its simplicity for the sensors with all the complex calculations done by the sink. Thus, the localization process consumes little power at the sensor nodes, helps to extend the life of the whole network. Furthermore, it has a covert feature whereby anyone eavesdropping on the transmission will not be able to infer the location of sensors from the signal coordinates contained in the packets.

Performance Evaluation of ALS
We evaluate ALS using simulations as well as field experimentation using commercially available wireless sensor nodes.

A. Performance metrics for ALS
The metrics, accuracy and granularity, are used to evaluate the performance of the scheme. High levels of accuracy and granularity are desired; however, accuracy begins to suffer as granularity increases, since the probability of estimating the location of a node correctly in a smaller area decreases. Hence, in order to have a fair evaluation of ALS, we normalize the accuracy with respect to the granularity or average area estimate, that is, normalized accuracy = accuracy / average area estimate. Another metric, average error, is defined to compare the performance of ALS to other range free schemes. The Center of Gravity (COG) or centroid of the final area estimate is assumed to be location of the node. Average error is then defined to be the average of the Euclidian distances between the original and estimated locations for all the nodes in the network.

B. Simulation scenario and parameters
The QUALNET 3.8 simulation environment is used to evaluate the performance of ALS. The system parameters used in our simulations are described below.
 Region of deployment: Square of size 500m × 500m.  Physical layer: For the ideal case, it is modelled by the two-ray model given in equation (2). In the non-ideal case, Rayleigh fading and lognormal shadowing are also factored into the two-ray model.  Node placement: A wireless sensor network with 500 nodes (eight of which are reference nodes) is used. The sensors are placed randomly throughout the region, and the eight reference nodes are positioned at the four corners and the four mid points of the sides of the square region. Although there are eight reference nodes, only four transmit beacon signals during each round of ALS. The sensor nodes in the network are assumed to be static, and the maximum velocity of objects in the surrounding is set to 1 m/s.  Reference-to-Node Range ratio (RNR): This parameter refers to the average distance a reference beacon signal travels divided by the average distance a regular node signal travels. The radio range of sensors is set to 50 m, while the radio range of reference nodes is set to 1000 m, which is large enough for the beacon signals to cover the entire area. Therefore, the RNR value is 20.  Node Density (ND): The node density refers to the average number of nodes within a node's radio transmission area. This value is close to 13 for the network scenario in consideration.  Reference Node Percentage (RNP): The reference node percentage refers to the number of reference nodes divided by the total number of nodes. In our case, the system has a low RNP of 1.6% (8/500).  Receiver Threshold Power: The receiver threshold power refers to the lowest signal strength of a packet that a node can receive. The value is set to -85 dBm.  N r : Number of times each beacon signal is sent out by a reference node. This parameter is set to 20.  CONFIDENCE_LEVEL: 80%.

C. Simulation studyof ALS under ideal conditions
LP is set to -13 dBm and MP is set to 17 dBm. The number of power levels is then increased from 3 to 7 and the performance of the scheme is observed. All the sensors lie in their estimated areas as the experiment is carried out under ideal conditions. On the other hand, the granularity increases as the average area estimate decreases (Table 1), and as a result, the normalized accuracy metric improves, shown in

D. Simulation study of ALS under non-ideal conditions
We first demonstrate the impact of decreasing the difference in adjacent power levels on the signal coordinates measured by the sensors. A signal coordinate <S 1 , S 2 , S 3 , S 4 > is considered to be valid only if at least two of the four elements S i can be measured with a confidence level of 80%. The measured signal coordinate is considered wrong if any valid element, S i , differs from the actual value. LP is set to -13dBm, while MP is set to 17dBm, as in the ideal case, and the number of power levels is increased from 3 to 7. The difference in adjacent power levels is (MP-LP)/(N p -1). For example, when N p is set to 3, the three power levels are -13 dBm, 2 dBm and 17 dBm, and the difference in adjacent power levels is 15 dBm. It is observed that the percentage of nodes that measure their signal coordinate correctly decreases from 96% to 28% as the number of power levels increases from 3 to 7. Fading and shadowing can cause the received signal strength to vary by as much as +10 dBm to -30 dBm of the expected value. The variance in measured signal coordinate increases, as the fading effect causes the received signal strength to vary by much more than the difference in adjacent power levels. As a result, fewer signal coordinates are measured correctly with a high confidence level (Fig. 5.). Nodes that were close to the edges of regions in the area were more prone to error than the nodes that are in the centre a region.  For the non-ideal case, as the number of rounds increases from 1 to 10, the accuracy decreases from 98.47% to 69.9% ( Table 2). The accuracy drops because a wrong signal coordinate measured in any one round of ALS would result in the final area being estimated incorrectly, as the intersection of areas from all rounds is considered in the final area estimate. On the other hand, granularity increases as the average area estimate decreases from 59.99% of the area size to 1.33% of the area size (Table 2) and this is a consequence of the intersection area for each sensor becoming smaller and smaller as the number of rounds increases.  For the non-ideal case, the normalized accuracy metric improves, and starts to flatten out as the number of rounds increases. The performance metric increases as the decrease in average area estimate is greater than the decrease in accuracy after each additional round of ALS. The performance flattens out because of the quantization of power levels, and the constraint of maintaining a significant difference between adjacent power levels. ALS can be stopped once desired accuracy levels and granularity are obtained. The desired average area estimate and accuracy level, as well as the computational complexity of performing an extra round, with the increased overhead in beacon messages should all be taken into account before an additional round is executed. After 10 rounds, the average error drops below 0.5*R (where R is the Radio Range of a sensor) for both the ideal and non-ideal conditions ( Fig. 7(b)).

E. One-hop Neighbourhood
Nodes that are closer to contour line boundaries are more prone to have their signal coordinates measured wrongly. An analysis was carried out to investigate the error patterns of nodes that did not lie in their estimated areas. It was observed that nodes, whose locations were estimated incorrectly, very often lie in an adjacent area to their actual location area. Let the average area estimate of the nodes in the sensor network be denoted by A (for example, A = 1.33% of region size at the end of 10 rounds in our simulation). The area estimate of each node can then be approximated by a circle of area A (of radius  (A/)). Circles with radius  (A/) and 2  (A/) are drawn from the estimated location of the node. The circular ring between radii  (A/) and 2  (A/) is defined as the one-hop neighbourhood region of the node. This concept of one-hop neighbourhood is illustrated with an example in Fig. 8. Referring to Table 2, we observe that the average area estimate is large for the first four rounds. As a result, all nodes lie within their estimated area or in the one-hop neighbourhood. As more rounds of ALS are executed, the accuracy decreases and the number of nodes that fall in the one-hop neighbourhood increases from 9.69% to 21.9%. It can be seen that, when A = 1.33%, more than 90% of nodes either lie in their estimated areas or in an area one-hop away. The significance of the one-hop neighbourhood lies in various application scenarios that ALS can be applied to. Consider an application scenario where a particular sensor in the network detects an event and an unmanned vehicle is sent to the area (estimated by ALS) to investigate. If the vehicle fails to find the sensor in the estimated area, it would then expand its search in the surrounding areas that are one-hop away, two-hop away and so on. The chance of finding the sensor within a one-hop range of the estimated area is very high (> 90%), as evident from Table 2.

F. Comparison with other range-free schemes
In this section, we compare ALS against other range-free localization schemes proposed for wireless sensor networks. The range-free area localization schemes and range-free distance vector based localization schemes chosen for comparison with ALS are the following: PIT (Point in Triangle) and APIT (Approximate Point in Triangle) schemes [4], DV-Hop [5], and DHL [6]. For a fair comparison, the chosen algorithms share a common set of system parameters described in Section 4.B. The results obtained after ten rounds of ALS are compared to the other two categories of range-free schemes.

1) Comparison with area based scheme:APIT (Approximate Point in Triangle)
In the PIT and APIT schemes [4], a node chooses three reference nodes from all audible reference nodes (reference nodes from which a beacon was received) and tests whether it is inside the triangle formed by connecting these three reference nodes. The theoretical method used to determine whether a point is inside a triangle or not is called the Point-In-Triangle (PIT) test. The PIT test can be carried out only under ideal physical layer conditions, when every node in the network is mobile can move around its own position. Due to the infeasibility of conducting such a test, an APIT (Approximate Point in Triangle) test is proposed. The APIT uses RSSI information of beacon signals to determine whether it is inside or outside a given triangle. The PIT or APIT tests are carried out with different audible reference node combinations until all combinations are exhausted. The information is then processed by a central server to narrow down the possible area that a target node resides in. An area scan aggregation algorithm is used to determine the intersection of the areas and determine the final area estimate of the node. Fig. 9 shows all the possible triangles for the given configuration of the eight reference nodes. There are 52 triangles in total ( 8 C 3 -4). The sensor nodes determine whether they are in or out of each of the 52 triangles, and the final area estimate computed is a small region or combination of regions on the area. Since PIT and APIT are area localization schemes, their performance are compared with ALS using the normalized accuracy metric. The following five cases are compared and results shown in Fig. 10: i) ALS under ideal physical layer conditions after six rounds ii) PIT under ideal physical layer conditions iii) APIT under ideal physical layer conditions iv) ALS under non-ideal physical layer conditions after six rounds v) APIT under non-ideal physical layer conditions The PIT and APIT schemes are carried out under ideal conditions to establish the performance limits that can be achieved with the APIT algorithm under non-ideal conditions. For the given scenario, it is observed (as shown in Fig. 7(a)) that ALS under ideal conditions outperforms both PIT and APIT after just six rounds. Not all APIT tests yield correct results, even under ideal physical layer conditions. As a result, the performance of APIT under ideal conditions is slightly lower than PIT, due to lower accuracy levels. Under non-ideal conditions, it is observed that ALS performs much better than APIT. This is primarily because fluctuating RSSI values causes a number of APIT tests to be incorrect. It is also observed that only around 60% of the 52 APIT tests are correct for each sensor. This results in large area estimates on the network area. Thus, lower accuracy levels and higher area estimates cause the performance of the APIT scheme to suffer. ALS, on the other hand, is more resilient to fading and shadowing due to the significant difference in adjacent beacon power levels.

Fig. 10. ALS outperforms PIT and APIT under ideal and non-ideal scenarios respectively
The ALS scheme is much more computationally efficient than APIT. For the scenario in consideration, the area estimate obtained from the intersection of just 10 regions for ALS, one from each round, results in a better performance than APIT, which considers the intersection of 52 regions. Thus, ALS achieves the desired performance level as APIT at a much lower computational cost. The computational complexity in number of areas is given by O(N r ) for ALS and O( N C 3 ) for APIT.

2) Comparison with distance vector based schemes: DV-Hop and DHL
Distance Vector based localization schemes estimate the point location of a node. The location estimation error is then defined to be the Euclidian distance between the actual position and the estimated position of the node. The average of the location estimation errors of all the nodes in the network is used to compare the performance of the three localization schemes. The location errors are normalized with respect to the transmission range of the node. For ALS and APIT, the Center of Gravity (COG) of the final predicted region is used as the estimated position of the node. Again, localization using PIT, APIT and ALS schemes are carried out under ideal conditions to establish the performance limits that can be achieved by the algorithms under non-ideal conditions. DV-Hop localization uses a mechanism that is similar to classical distance vector routing. Each reference node broadcasts a beacon, which contains its location information and a hopcount parameter initialized to one. The beacon is flooded throughout the network. Each sensor node maintains the minimum counter value per reference node of all beacons it receives and ignores those beacons with higher hop-count values. Beacons are flooded outward with hop-count values incremented at every intermediate hop. Through this mechanism, all nodes in the network (including other reference nodes) get the shortest distance, in hops, to every reference node. In order to convert hop-count into physical distance, the system estimates the average distance per hop without range-based techniques. Once a node can calculate the distance estimation to more than three reference nodes in the plane, it uses triangulation (or multilateration) to estimate its position. The DV-Hop scheme performs well in networks with uniform node density, as the size of each hop is assumed to be constant. The DHL scheme is an enhancement to the DV-Hop scheme for networks with non-uniform node density. In the DHL scheme, the size of each hop is not assumed to be constant. Instead, the size of each hop depends on the density of nodes in the neighbourhood. In the simulations, the RNR parameter is set to 1 for DV-Hop and DHL, i.e. the radio range for both the reference and sensor nodes is set to 50m. From the results shown in Fig. 11, it can be observed that even under non-ideal physical layer conditions, ALS performs better than the other range-free schemes. The average estimation error of DV-Hop and APIT under non-ideal conditions is greater than R (radio range of sensor node.) The APIT scheme under non-ideal conditions is severely affected by the fluctuations in RSSI of the beacon packets. APIT would perform better if there were more reference nodes, but the improved performance would be at the expense of a much higher computational cost. For example, it is observed from the APIT simulations in [4] that achieving an average estimation error of close to 0.5R, for a similar set of system parameters used here, would require more than 15 audible reference nodes. This would entail computing the intersection of more than 455 ( 15 C 3 ) areas and hence, is highly computation intensive. The performance of DV-Hop is contingent on the density distribution of nodes in the network and the estimate used for the average distance of a single hop. The performance of DV-Hop suffers if the distribution of nodes in the network is non-uniform. For both schemes, viz. DV-Hop and DHL, we observe that the localization error of the nodes along the sides is higher than nodes at the centre of the region [24].

Performance of ALS on a WSN Test bed
The performance of the ALS depends on the model used for the physical layer. The radio environment can be modelled by the empirical log-distance path loss model, as shown below: where n is the path loss exponent which indicates the rate at which the path loss increases with distance, d 0 is the reference distance (typically set to 1 m), d is the distance between the transmitter and receiver, PL(d 0 ) is the power received at distance d 0 , and X  is a zero-mean Gaussian distributed random variable (in dB) with standard deviation . X  describes the random shadowing effects over a large number of measurements for the same transmitterreceiver separation.
To extend ALS to any generic physical layer model, we implement a testing phase where the parameters n and X  are estimated, which can be achieved by the reference nodes mutually measuring the received signal strength from one another's beacons. The model in equation (3) can then be used to determine the different transmit power levels and to draw out the signal map. We implemented the ALS on a wireless sensor network test bed [25]. MicaZ motes by Crossbow Technology Inc. [32] are used as both reference and sensor nodes. The MicaZ motes allow transmission of signals at only 8 power levels: -25, -15, -10, -7, -5, -3, -1 and 0 dBm, corresponding to MicaZ transmission power settings of 3, 7, 11, 15, 19, 23, 27 and 31 respectively. As a result, we were constrained to use only these eight power levels for the reference nodes. However, for a real deployment, we anticipate the anchor nodes to be more sophisticated devices with the ability to finetune the power at which they transmit beacon signals. Fig. 12. ALS experiment in an obstacle free environment -the experiment was carried out in a 30m×30m region in a soccer field. There were no obstacles present inside the region. The experiments were carried out in both indoor and outdoor environments. For the outdoor scenario, the experiment was first carried out in an environment with no obstacles (Fig. 12), and subsequently in an obstacle-ridden environment (trees, park benches, etc) (Fig.  13). RSSI measurements were made to estimate the path loss exponent of radio signals in each environment. The path loss exponent is calculated using regression analysis on the RSSI measurements, and was determined to be 2.92 for the indoor environment and 2.96 for the outdoor environment. The path loss exponents were then used to estimate the ranges of the beacon signals sent out at different power levels by reference nodes. The measured and estimated range measurements for the indoor and outdoor environments are shown in Table 3, and we observed that the estimated range values tally with the measured range values for different power levels. We observed that the range measurements vary with the height at which the reference nodes are placed, as also noted in [18]. In particular, the communication ranges of the nodes increased when the reference nodes were raised above the ground. We, therefore, raised the height of the reference nodes for our experiments. For the indoor environment, the reference nodes are placed on plastic pots at a height of 12 cm above ground level. Similarly, for the outdoor environment, the reference nodes are mounted on wooden easels at a height of 190 cm above ground level, while the sensors are placed on plastic pots, 12 cm above ground level (as shown in Fig. 14.) We also observed that the range measurements depend on the relative orientation between the transmitter and receiver antennas, and the radio patterns of the MicaZ antennas are not circular. Both these observations are confirmed by the results obtained by Lymberopoulos et al. [26] and Tan et al. [27]. Therefore, we run each ALS experiment four times with four different relative orientations between the transmitter and receiver antennas. For example, all sensors are placed facing a certain direction initially (North). The ALS experiment is then carried out four times, with reference nodes facing North, South, East and West directions respectively. The results are then combined to obtain the final area estimate of each sensor. This helps alleviate the problems caused by the radio irregularity of the sensor antennas. The experimental set up is similar to the set up described in the simulation scenario. An area size of 10m × 10m is chosen for the indoor environment while the area size of 30m × 30m is chosen for the outdoor environment. Between 30 and 35 sensors are deployed randomly throughout the area, with eight reference nodes positioned at the four corners and the four mid-points of the sides of the square region. Since packets are often lost due to varying channel conditions, the CONFIDENCE_LEVEL parameter is set to a relatively low value of 30%. The results of the experiments are summarized in the Table 4 below. We also plot the actual versus point estimated locations for the sensors in the different environments, namely, Fig. 15 for indoor, Fig. 16 for outdoor (open field/no obstacles) and Fig. 17 for outdoor (park/with obstacles). The crosses are the actual locations of the sensors, the circles are the predicted point estimated location of the sensors (the approximate centre of the region) and the squares are the locations of the reference nodes. A shorter line connecting a cross-circle pair denotes higher accuracy.

Fig. 15. Actual versus Estimated Locations of Sensors in Indoor Environment
The set of ideal results refers to the case where every sensor node measures its signal coordinate correctly and hence the area in which it is located, correctly. The average error increases from 2.04 m to 3.37 m as we move from an obstacle-free outdoor environment to an obstacle-ridden environment. Moving from an obstacle-free to an obstacle-ridden environment outdoors, we notice that the accuracy drops but the number of nodes present in the one-hop neighbourhood increases. For all the scenarios, more than 80% of sensor nodes lie within their predicted area or within a one-hop region of the predicted areas with the average area size estimate of less than 3.5%. This means that in real deployments, sensors can be located quickly once the predicted region is calculated. The performance of  In addition, we also compared ALS with other localization schemes that utilize radio signals, which have also been implemented and tested experimentally. From Table 5, show the results of ALS with such schemes, and it is clear that the performance of ALS in the field trials is comparable or better than these other localization schemes.

Conclusion
The ALS is a range free localization scheme that provides a coarse estimation of the location of a sensor within a certain area. While the sensors simply record the signal levels received from reference nodes, the sinks carry out most of the complicated computations. The granularity of the area estimates can be increased easily by modifying certain system parameters. The simulations results in Qualnet show that ALS is a promising scheme as more than 90% of nodes are located in their estimated areas or in a region one-hop away. We implemented the ALS algorithm on a wireless sensor network testbed and tested it in both indoor and outdoor scenarios. We observed that 100% of nodes lie within a one-hop region in an outdoor, obstacle-free environment, and 83% (or more) of nodes of lie within a one-hop region in an indoor or outdoor, obstacle-ridden environment. With high quality transmission device and antennas implemented at the reference nodes (as compared to the motes used in the experiment), it is highly foreseeable that the accuracy of ALS will increase. As part of our ongoing and future work, we have first addressed the issue of non-uniform areas (e.g. as shown in Fig. 6) by aggregating areas of different sizes to create more uniformity [33]. Subsequently, we will be improving the reference nodes and also develop routing protocols that is able to utilize the location information provided by the ALS algorithm. A sensor can therefore estimate whether it is nearer or further away from the destination, compared to its previous hop, based on the signal coordinate information of its neighbour, the destination and itself, and this information can be used for developing fast and efficient routing protocols. Another benefit is the covert nature of the scheme, which can be exploited to meet privacy needs. Over the past decade, there has been a prolific increase in the research, development and commercialisation of Wireless Sensor Networks (WSNs) and their associated technologies. WSNs have found application in a vast range of different domains, scenarios and disciplines. These have included healthcare, defence and security, environmental monitoring and building/structural health monitoring. However, as a result of the broad array of pertinent applications, WSN researchers have also realised the application specificity of the domain; it is incredibly difficult, if not impossible, to find an application-independent solution to most WSN problems. Hence, research into WSNs dictates the adoption of an application-centric design process. This book is not intended to be a comprehensive review of all WSN applications and deployments to date. Instead, it is a collection of state-of-the-art research papers discussing current applications and deployment experiences, but also the communication and data processing technologies that are fundamental in further developing solutions to applications. Whilst a common foundation is retained through all chapters, this book contains a broad array of often differing interpretations, configurations and limitations of WSNs, and this highlights the diversity of this ever-changing research area. The chapters have been categorised into three distinct sections: applications and case studies, communication and networking, and information and data processing. The readership of this book is intended to be postgraduate/postdoctoral researchers and professional engineers, though some of the chapters may be of relevance to interested masterâ€™s level students.

How to reference
In order to correctly reference this scholarly work, feel free to copy and paste the following: