Localization method for low-power wireless sensor networks

Localization method for low-power wireless sensor networks Diego Fco. Larios, Julio Barbancho, Fco. Javier Molina and Carlos Le´on Senior Member, IEEE. Department of Electronic Technology, “Escuela Polit´ecnica Superior” University of Seville, Seville, Spain, Phone: +34 954 55 28 38 Fax: +34 954 55 28 33 Email: dflario[email protected], [email protected], fjmolin[email protected], [email protected] Abstract—Context awareness is an important issue in ambient intelligence to anticipate the desire of the user and, in consequence, to adapt the system. In context awareness, localization is very important to enable a responsive environment for the users. Focusing on this issue, this paper presents a localization system based on the use of Wireless Sensor Networks devices. In contrast to a traditional RFID, these devices offer the possibility of a collaborative sensing and processing of environmental information. The proposed system is a range-free localization algorithm that uses fuzzy inference to process the RSSI measurement and to estimate the position of mobile devices. The main goal of the algorithm is to reduce the power consumption and the cost of the devices, especially for the mobiles ones, maintaining the accuracy of the inferred position. Index Terms—Fuzzy system, WSN, localization, RSSI, centroid, AmI I. INTRODUCTION Ambient Intelligence (AmI) refers to electronic environments that improve the user experience of the environment by responding to them intelligently. It implies the use of advanced networking computing technology that is aware of human presence, personalities and needs. In ambient intelligence, devices may work to help people in their everyday activities. These devices would both sense and react based on the environmental context. Intelligent homes are a typical AmI application area, because they increase security and comfort for the users [1]. In the notion of ambient intelligence, the main keys [2] are the followings (figure 1): •Embedded. Many networked devices are integrated into the environment for sensing and controlling it. Ideally, these devices are deployed throughout the environment, but their presence must be undetected for the users. The devices share information to This paper is based on “Locating sensor with fuzzy logic algorithms,” by D. F. Larios, J. Barbancho, F. J. Molina and C. Le´on, which appeared in the Proceedings of the 24th IEEE Symposium on Proceedings of the 8th International Joint Conference on e-Business and Telecomunications (ICETE), Seville, Spain, July 2011. This research has been supported by the “Consejer´ıa de Innovaci´on, Ciencia y Empresa”, “Junta de Andaluc´ıa”, Spain, through the excellence project ARTICA (reference number: P07-TIC-02476) and by the “C´atedra de Telef´onica, Inteligencia en la Red”, Seville, Spain, through the project ICARO. Figure 1. Ambient Intelligence keys. increase user’s comfort. Communication is essential to obtain an adequate response in computing, where control intelligence is spread all over the network. WSN is an example of technology that complies with this key. •Context awareness. The system would recognize the situational context of the users. This implies that the devices can recognize the user [3], his position and the positions of those devices, the users can interact with. •Personalized. The system must adapt to the needs of the users. The system must be intelligent enough to adapt to the desires of the user in function of his natural reactions. •Adaptive. The system must learn the user’s needs. For example, learning the temperature or the illumination that users feel like having in each room, adjusting them automatically. •Anticipatory. The system must anticipate user’s needs without conscious mediation. Anticipatory is related to the user interfaces in the ambient intelligence and it searches for an easy interaction between machines and users [4]. Ideally, these interfaces would not be perceived by the users [5]. JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 45 © 2013 ACADEMY PUBLISHER doi: 10.4304/jnw.8.1.45-58 The ambient intelligence paradigm is often built on pervasive computing, ubiquitous computing and computational intelligence [6]. AmI paradigm started to be developed with the challenge launched by the European Commission in 2001, aiming that the researchers investigate in this area [7]. In context awareness, localization system is essential to enable a more reactive useraware responsive environments [8]. Tracking users offers basic information useful to learn about their habits, or to predict following displacements [9]. For example, before a user enters a room, the air conditioning would be adjusted to his comfort automatically. This paper faces the problem of locating users based in the AmI paradigm, reducing the power consumption and the cost of the devices. Energy efficiency is especially relevant for mobile devices. It improves battery autonomy and increases the user comfort. The proposed method is based on a Wireless Sensor Network (WSN) that can monitor and control the environment intelligently in function of the user desires. The rest of this paper is organized as follows: section II sums up the state of the art about WSN applied to ambient intelligence. Section III describes the localization algorithm. Section IV evaluates the advantages of the proposed localization algorithm over the power consumption. The outcome of the localization algorithm performance is developed by simulations, and the results are shown in section V. Finally, in Section VI we present concluding remarks. II. LOCALIZATION TECHNIQUES A wireless sensor network (WSN) consists of lots of small devices deployed in a physical environment for its study. Each node has special capabilities, such as wireless communications with its neighbours, sensing, data storage and processing. WSN has been widely used in many areas [10], such as environmental monitoring [11] and control [12], healthcare and medical research [13], national defense and military affairs [14] [15], etc. The use of WSN in ambient intelligence offers many advantages [16]. It uses has been proposed by many authors [17] and rejected by others because of the cost and battery consumption that these devices present [18]. But nowadays, the cost has been reduced significantly, and the energy consumption can be reduced with suitable software and hardware design. In this way, it is possible to get years of battery autonomy for the mobile nodes. Using the microcontroller and external sensors and actuators, the current nodes used on WSNs can control the comfort and safety of the users. For example, a device can make emergency calls in case of an accident [19]. Traditionally, in ambient intelligence, the localization solution is based on passive or active RFID technology, but RFID has a very limited capacity to monitor the environment compared to WSNs. Moreover, the prices of RFID tags and some WSNs nodes are currently similar (20-30 $ [20]). Moreover, the in WSN tags and readers share the same economic hardware, but in RFID a reader is much more expensive than a tag (around 1500 $) and more expensive than a WSN device. In this journal, we propose a system to control the localization using WSN devices only. This reduces the cost and the complexity of the system and increases its capabilities and functionalities. 1) Localization Techniques for WSN: For this applications, we are going to consider the following types of nodes: •Anchor nodes: located on a fixed position in the house. Theses devices are used to route the information to the Base Station and for the localization algorithm. These devices act as the readers of the RFID technology. •Tags: are the small devices deployed with the object or users to locate. Their positions are initially unknown and the algorithm would find them. These devices can obtain environmental information through sensors, such as temperature or accelerometers. These devices are also called non-anchor nodes. •Base Station: This is a special anchor node that acts routing the WSN information from the network to a PC. This PC provides the information acquired by the network to the rest of the AmI devices. Localization algorithms presented in the literature can be classified into two categories: •Range-based: These techniques estimate, point-topoint, the distance between all the nodes using sensors such as ultrasound [21]. With this information, using techniques such as triangulation, the absolute position of the non-anchor nodes can be estimated. Generally, these techniques require additional hardware. The most common ones are Received Signal Strength Indication (RSSI) [22], Time Of Arrival (TOA) [23] and angle of arrival (AOA) [24]. •Range-free: In these techniques, the position of non-anchor nodes is obtained according to implicit information provided by anchor nodes, usually based on messages exchanged, commonly called beacons. This information is usually made up of different aspects, such as radio coverage membership or number of hops between devices. The most common ones are Centroid (CL) [25] and DV-Hop [26]. In general, the range-based ones offer good accuracy, but additional hardware is often needed. Therefore, the weight, the cost and the power consumption of node devices increase, and make these sort of techniques unsuitable. RSSI range-based techniques are an exception to this because most of the current transceivers provide this measure by default. However, RSSI techniques are very sensitive to noise and interferences. Figure 2 shows experiments realized by the authors to evaluate the relationship between RSSI and the distance in different situations: free-space without obstacles and long urban area with obstacles. The results do not match with any known models, such as the Friis equation, but in very ideal conditions. In fact, 46 JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 © 2013 ACADEMY PUBLISHER -45 -40-40 -50 -55 -60 -65 5 -70 RSSI (dBm) Distance (meters) 10 15 20 25 30 35 40 45 50 RSSI vs. Distance Free space With obstacles Figure 2. RSSI vs. distance. in common scenarios, with obstacles and/or inside the buildings, there is no direct relationship between distance and RSSI. In fact different distances produce the same RSSI value. Instead of using a mathematical model, the proposed solution uses a fuzzy-logic-based system to derive the distance from RSSI level. This is more robust in noisy and complex scenarios. This idea is not new. Computational Intelligence has been proposed for localization in several papers, such as [27] that uses probabilistic neuronal networks, [28] that applies a fuzzy system and [29] that uses fuzzy neurons. In general, all these algorithms track down current positions based on estimate position changes. But none of them consider the problem of power consumption. III. DESCRIPTION OF THE PROPOSAL SOLUTION To locate the important elements (devices, users, etc) over a WSN, we proposed LIS (Localization Based on Intelligent Systems). LIS is a technique that determines the localization using a fuzzy system. LIS use RSSI, but not associating it to a distance estimation. Due to it, it is a range-free technique, such as weighted centroid. The inputs of the fuzzy system are the RSSI measurements related to the non-anchor node. These RSSI values are measured when anchor nodes receive a message sent from the tag. LIS was designed to be developed in a building. In fact, a prototype is currently deploying in the “Red building” of the University of Seville. This building is in the “Campus de Reina Mercedes” and has 12 classrooms and 38 offices spread over three floors and a basement. This prototype will consist of a mesh of fixed anchor nodes spread throughout the building (figure 3), and any small nonanchor nodes situated together to the elements to locate. The aim of this network is to control the position of any resources, such as laptops, monitors, printers, projectors, etc, to prevent theft. With LIS, all the information is stored and timestamped in a PC attached to the Base Station. This PC stores two different classes of information gathered from the network: Anchor nodes Non-anchor nodes Communication link Message transmission User 1 User 2 User 4 User 3 Figure 3. Infrastructure of LIS •Target location: This information describes the position. •Sensors information: This information is the environmental measurement, such as the temperature, humidity, etc. Despite that range-free and range-based techniques have been extensively studied, nowadays there are some aspects that continue to be a challenge: •The use of additional hardware or lots of beacons increases power consumption. •Centralized processing (i.e. on Base Stations) requires a large amount of messages. Conversely, processing in tags nodes reduces the battery of these devices significantly. •Scalability. Many of range-based algorithms are hard to extend to big sensor networks. LIS has been especially designed to face all of the above problems. As a result, the proposed algorithm is scalable and the power consumption and network autonomy are optimized. LIS combines: (I) a fuzzy system to estimate (actually to qualify) the distance between transmitter and receiver from RSSI measurements, (II) a ubiquitous algorithm executed in anchor nodes that receive the beacon of the non-anchor nodes, to determine relative positions to them, and (III) a cooperative algorithm to derive the most likely location running at the Base Station. LIS algorithm consists of four stages: S1: Anchor nodes wait for non-anchor nodes (tags) beacons. S2: The tag node broadcasts a beacon. S3: Receiver anchor nodes measure RSSI, and execute the Ubiquitous Processing (UP) for relative and JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 47 © 2013 ACADEMY PUBLISHER 1 (B.S.) 23 45 6 7 8 (X?,Y?) Anchor nodes Non-anchor node Communication link Limit of radio coverage Message transmission (a) 1 (B.S.) 23 4 5 6 7 8 (b) 1 (B.S.) 23 45 6 7 8 (Xr7,Yr7) (Xr4,Yr4) (Xr5,Yr5) (c) 1 (B.S.) 23 45 678 (Xr4,Yr4) (Xr5,Yr5) (Xr7,Yr7) (Xest,Yest) (Xest,Yest)=centroid(Xri,Yri) (d) Figure 4. Steps of LIS algorithm: (a) S1; (b) S2; (c) S3; (d) S4 partial positioning. S4: Anchor nodes send partial solutions to the Base Station, where the location is finally determined with the Cooperative Processing (CP). Figure 4 illustrates these stages. When a non-anchor node broadcasts a beacon or any other sort of message, the localization process starts. Just anchor receiver nodes participate in the process. The rest of the nodes can switch off the radio transceiver or hold in a low power state. For localization, the tags periodically send broadcast messages to the anchor nodes. The frequency of the messages would be adjusted in function of the characteristics of the system. A. Ubiquitous Processing (UP) LIS uses the measured RSSI of a node and its neighbours to determine the area where the non-anchor node could be located. This algorithm is based on a fuzzy system distributed on every anchor node of the network. According to the algorithm stages, once an anchor node receives a beacon, it estimates the position of the non-anchor nodes. The localization algorithm has been designed to distribute the computation consumption over the network. The area where the non-anchor node could be located with a certain probability is called Representative Area (RA). A Sector is the minimum area formed by three anchor-node neighbours. A Representative Area (RA) represent the estimation, in terms of sectors, where a node estimate a tag would be. as described below, RA can be made up of one or more sectors with an UP processing higher than a certain threshold. Anchor nodes must execute the distributed Fuzzyfication Algorithm (FA) measurement for every surrounding sector. Figure 5 shows an example with five sectors in which, the fuzzy processing are executed five times. Anchor nodes Comunication link Neighbour 1 Sector 1 Sector 2 Sector 3 Sector 4 Neighbour 2 Neighbour 3 Neighbour 4 Sector 5 Neighbour 1 Figure 5. Example of node with 5 neighbours. Every node that receives a beacon, it measures and broadcasts the RSSI level to its neighbours (figure 4.b). In this way, the closest anchor nodes elaborate a table with the RSSI measured by them and their neighbours. The RSSI table is processed by FA (figure 6) to evaluate the representative area no matter the number of sectors. This area can be formed by the union of one of more sectors (figure 4.c). A sector is considered part of the representative area if its membership degree is higher than the threshold. This value is adjusted experimentally. 48 JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 © 2013 ACADEMY PUBLISHER Output Fuzzification Defuzzification Inference engine Base of rules Fuzzy sets data class fuzzy crips Imputs } Node RSSI Possition Central Neib. 1 Neib. 2 Value (X,Y) Value (X,Y) Value (X,Y) Neib. N Value (X,Y) . . . . . . Membership to actual sector (0 - 1) Figure 6. Inference fuzzy system. Our simulations show that a threshold of 0.1 manages a good trade-off between noise immunity and localization performance. The results of Representative Areas (RA) are sent from the anchor nodes to the Base Station to compute the final solution (figure 4.d). An RA is empty if it does not contain significant sectors, this is if the membership degree for all of them is lower than the threshold. In this case, to save energy, the result is discarded and the algorithm will finish until the next beacon arrives (figure 8). This is especially important in huge networks, where the energy needed for multi-hop transmissions is high. This issue is discussed in detail in section IV. med RSSIsens RSSITX power Input value Membership degree LOW MEDIUM HIGH RSSI 0 1 Figure 7. Sets of the fuzzy imputs. 1) The Fuzzy System Inputs: RSSI tables represent the signal level received in either local and neighbour nodes. Three fuzzy sets qualify the RSSI as High, Medium and Low for each input, as appear in figure 7. This figure is a simplification. The area of the fuzzy imput sets varies in function of the estimated RSSI. Due to it, it may be not symmetrical. The LOW RSSI fuzzy set is represented by a trapezoid. Maximum membership degree (1) is assigned if power falls down the sensibility threshold of the emitter node (RSSIsens). As the power increases, membership degree decreases linearly until zero. The following equation defines this fuzzy set: µ(x) = max min 1,RSSImed −x RSSImed −RSSIsens ,0 (1) The MEDIUM RSSI fuzzy set is represented by a triangle where maximum membership degree corresponds to the medium RSSI value (RSSImed). Zero membership is reached for power RSSI values lower than the sensibility threshold or close to the maximum transmission (RSSIT Xpower). In this paper, medium RSSI value must be computed for every sector using the Friis model equation (equation 2) and assuming the emitter tag is located at the centre. This computation only needs to be executed once because anchor nodes are located at fixed positions. More complex models, such as Two-Ray ground model or ITU indoor model are not considered in this paper for minimizing the complexity of the algorithm, But in can be used to increase the accuracy of the system. The error with led to the use a simplified model is compensated with the redundancy of information and the use of FA and UP Algorithms. PRX PT X =GT X ·GRX ·λ 4πR2 (2) Where GT X and GRX are the gain of TX and RX antennas, Ris the distance between transmitter and receiver and λthe wavelength. Next expression defines the fuzzy set for MEDIUM RSSI: µ(x) = max min x−a b−a,c−x c−b,0(3) Where a=RSSIsens,b=RSSImed and c= RSSIT Xpower. Fuzzy set for HIGH RSSI values is a trapezoid with a lineal increasing from 0 to 1 for RSSI power values ranging between RSSImed and RSSIT Xpower. This fuzzy set is defined by the next expression: JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 49 © 2013 ACADEMY PUBLISHER Nodes with UP output below a threshold do not send information to the base station, saving energy. This information is discarted. Anchor nodes Non-anchor node Communication link Limit of radio coverage 7 Message transmission (B.S.) n hops Centraliced Algorithm 7 (B.S.) n hops Distributed Algorithm In extended networks, redirected messages would waste a lot of energy Any node that receives a beacon sends the associated information to the base station, where it is processed A node decides with this neighbour if it has useful information Figure 8. Distributed algorithm would save Power Energy on extended networks. µ(x) = max min x−RSSImed RSSIT Xpower −RSSImed ,1,0 (4) 2) The Fuzzy System Outputs: The Fuzzy System offers an output for each and every sector. The output associated to a sector is a [0, 1] ranged value that represents the confidence degree that the tag is actually located in that sector. LOW MEDIUM HIGH 0 0.5 1 Confidence degree Output value 0 1 1.5-0.5 Figure 9. Sets of the fuzzy output. As figure 9 shows, the LOW output fuzzy set is a triangle with the central point at zero and the corners at -0.5 and 0.5. The next expression defines this fuzzy set: µ(x) = max min x+ 0.5 0.5,0.5−x 0.5,0(5) MEDIUM output is represented by a triangle with the central point at 0.5 and corners at 0 and 1. Mathematically it can be expressed by the following equation: µ(x) = max min x 0.5,1−x 0.5,0(6) HIGH output qualifier is also defined by a triangle with the central point at 1 and the corners at 0.5 and 1.5. This fuzzy set is defined by the next expression: µ(x) = max min x−0.5 0.5,1.5−x 0.5,0(7) 3) Inference Engine: The inference engine is a Mandani’s rules based one with a centroid defuzzification method and a singleton input fuzzificator. The fuzzy engine evaluates the antecedent of every rule by the intersection of the fuzzy inputs, using the minimum function for the AND operator (Eq. 8), and the maximum function for the OR operator (Eq. 9). The implication between inputs and outputs applies the minimum function. AND(a, b) = min(µ(a), µ(b)) (8) OR(a, b) = max(µ(a), µ(b)) (9) As mentioned, the rules must be evaluated for every single sector to estimate the confidence degree, taking into account the fuzzy qualifications of RSSI values of either the current sector nodes and the surrounding ones. The rules summed up in table I have been derived from multiple simulations in order to obtain the best trade-off between precision and noise immunity. B. Cooperative Processing (CP) The Base Station collects the partial solutions from the anchor nodes, and it processes them cyclically as follows: CP-S1: The Base Station waits to receive the first partial solution. CP-S2: On arrival, the partial solution is saved and a timer starts running. CP-S3: While the timer is running, the next partial solutions are saved in a table as they were received. CP-S4: When the timer expires, the system will compute the final position as the centroid of all these partial solutions (triangle sectors). The centroid computation of a finite set of points ~ P1,~ P2,··· ~ PNcan be simplified as: 50 JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 © 2013 ACADEMY PUBLISHER TABLE I. RULES OF THE INFERENCE ENGINE. RSSI node RSSI Neighbours Output High. All medium. High Low. All low. Low Medium. All medium. High Medium. All low. Low High. All high. Medium Medium. Medium in current sector. High Low in the rest. Medium. High in any sector except the current one. Low Low in the rest. High. High in a neighbour of the current sector. Medium Low in the rest. High. High in a neighbour, except on the current sector. Low Low in the rest. Medium. Medium in a neighbour of the current sector. Medium Low in the rest. Medium. Medium in a neighbour, except on the current sector. Low Low in the rest. Position =PN i=1 ~ Pi N(10) Previous algorithms can be easily extended to locating multiple tags, by simply associating a tag identifier to the transmitted beacons. The final estimated position is timestamped and saved in the Base Station to make it accessible through Internet. IV. POWER CONSUMPTION OF LIS Generally, power consumption is a strong constraint in a WSN application, especially for non-anchor nodes (tags), where mobility and additional constraints like size and weight do not allow use of high capacity batteries. Most node power consumption is caused by radio transmissions. As an example, Telosb platform consumes 41 mW in active mode (POn). The microcontroller consumes only 3mW and the remainder power consumption is caused by the radio transceiver that requires 38 mW in reception mode and 35 mW in transmission mode [30]. Figure 10 represents a localization algorithm computed in the non-anchor node. This is the typical execution phase of range-based or range-free algorithm, such as centroid. As it can be observed, after the tag node broadcasts a beacon (figure 10.a), it waits for the response of all the anchor nodes placed in the radio range (figure 10.b). This phase takes a long time because of the number of surrounding nodes and because of the collisions. After that, the tag node executes the localization algorithm and delivers the result to the Base Station (figure 10.c). During all of this time, the radio transceiver must be in the active state. It wastes a lot of energy and its autonomy is considerably reduced for the non-anchornode. It is in fact, the device with the highest energy constraints. Figure 11 depictd this information. It shows the energy consumption in a generic tag that computes a localization algorithm, Anchor nodes Non-anchor node Communication link Message transmission (B.S.) (B.S.) 23 4 5 6 7 23 4 5 6 7 (B.S.) 23 4 5 6 7 (a) (b) (c) Figure 10. Localization algorithm using the non-anchor node for estimating it position. considering the power consumption of TelosB node [30]. In this simulation the radio transceiver is maintained in the [10 s - 60 s] range, sending messages in the [1 - 60] per hour range. In these graphics, Tx, Rx and idle power consumption of the node are considered. 0,00E+00 5,00E+02 1,00E+03 1,50E+03 2,00E+03 2,50E+03 3,00E+03 3,50E+03 4,00E+03 24 72 120 168 216 264 312 360 408 456 504 552 600 648 696 744 792 840 888 936 984 1032 1080 1128 1176 1224 1272 1320 1368 1416 10 20 40 60 Always ON Energy (J) Messages per day Time ON (s) Figure 11. Energy consumption in non-anchor nodes executing localization algorithms. As this figure shows, the energy consumption of the tag’s processor in idle mode is negligible in comparison with the power consumption of the radio transceiver. Moreover, the power consumption of the node with the radio transceiver in transmission mode (35 mW ) is similar to the power consumption of the node with the transceiver in reception mode (38 mW). Therefore, the power consumption in a WSN node would be estimated as equation 11 shows. Enode,day ∼ =TOn,day ·POn (11) It is important to point out that the power consumption is very high either in transmission and also in reception mode. Because of that, to reduce the power consumption in tags it is necessary to reduce the number of exchange messages, but it is also necessary to stop all the node activity enabling low power modes and switching off the radio transceiver. Therefore, a suitable activity manager is needed. LIS takes this issue into account, also that anchor nodes have more power supply resources than the tags. The algorithm has been designed to be executed mainly in the anchor nodes. Furthermore, the radio transceiver of the tag is activated for a short time, just enough to broadcast the beacon. In the remaining period of time, the tag will JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 51 © 2013 ACADEMY PUBLISHER be in a idle state and its radio transceiver off. The time with the radio transceiver on (Ton) can be estimated, in a worst case, attending equation 12. Ton =Tact +Tmsg +Tdeact ≤17 ms (12) Where Tmsg is the time needed to send a beacon (Tmsg ≤5ms, considering the preamble and a 128 bytes message length). Tact and Tdeact are the times for activating and deactivating the radio transceiver (Tact = Tdeact = 6 ms in telosB nodes). Considering this timing, the energy consumption of a tag sending a message (Emsg) can be obtained attending equation 13. Emsg =Tact ·PRx +Tmsg ·PT x +Tdeact ·PRx (13) Where PRx is the power consumption of the microcontroller with the radio transceiver in reception mode (PRx = 41 mW) and PT x is the power consumption of the microcontroller with the radio transceiver in transmission mode (PT x = 38 mW ) [30]. As it was explained in section III, with LIS non-anchor node only sends a beacon and receive nothing. This is why the energy consumption of reception is not considered. Figure 12 shows these results, and depicts the energy consumption of LIS in a non-anchor node, sending a message in a [1 - 60] per hour range. As it can be seen, its power consumption is very low, practically equal to the power consumption of maintaining always the tags in sleep mode. This represents the best case for saving energy, where Toff >> Ton. 0,00E+00 5,00E-01 1,00E+00 1,50E+00 2,00E+00 2,50E+00 24 72 120 168 216 264 312 360 408 456 504 552 600 648 696 744 792 840 888 936 984 1032 1080 1128 1176 1224 1272 1320 1368 1416 Energy (J) Messages per day Figure 12. Energy consumption in non-anchor nodes executing LIS. However LIS also reduces the power consumption in anchor nodes. It implements a ubiquitous and distributed algorithm that spreads the localization processing amongst the nodes surrounding the tag. In a centralized algorithm, all the information received by the anchor nodes must be delivered to the Base Station (figure 13). By contrast, our proposed algorithm saves power energy because only significant information is delivered (figure 14). In the worst case, LIS delivers practically the same number of messages than a centralized algorithm. But for low dense deployments, for example when medium number of nodes that a beacon receives is lower than the medium number of hops necessary to reach the Base Station, the saved energy is significant. Anchor nodes Non-anchor node Communication link Message transmission (B.S.) (B.S.) 2 3 4 5 6 7 2 3 4 5 6 7 (a) (b) 8 8 Figure 13. Example of centralized algorithm. Anchor nodes Non-anchor node Communication link Message transmission (B.S.) (B.S.) 2 3 4 5 6 72 3 4 5 6 7 (B.S.) 2 3 4 5 6 7 (a) (b) (c) 8 8 8 Figure 14. Example of distributed algorithm. As a consequence, the energy saved with the distributed algorithm varies with the density and complexity of the networks. Figure 15 shows a study about the number of saved messages in function of the number nodes with useful information. From this, it can be derived that in case all the information obtained by the anchor nodes were useful, both methods send practically the same number of messages. But the more number of nodes with useless information, the energy saving performance of the distributed processing increases drastically, due to the reduction of transmissions. Additional savings can be managed clustering the networks, and using the clusterheads as Base Stations. This is, receiving an processing partial estimations from its cluster nodes. Figure 16 shows this idea. For this case, the algorithms must be modified as follows: S1: Anchor nodes wait for non-anchor node beacons. S2: The tag node broadcasts a beacon. S3: Receiver anchor nodes measure RSSI, and execute both, fuzzification algorithm and ubiquitous processing for relative and partial positioning. S4: Anchor nodes send partial solutions to the clusterhead, where the location is finally determined. S5: Clusterhead node executes the cooperative positioning algorithms and delivers the final position to the Base Station. 52 JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 © 2013 ACADEMY PUBLISHER -15 -10 -5 0 5 10 15 20 25 1 2 3 4 5 6 7 8 9 10 Number of nodes Number of message saved 10 8 6 4 2 0 Number of nodes with useful information: Message saved with distributed processing: 3 hops (a) -20 -10 0 10 20 30 40 50 60 1 2 3 4 5 6 7 8 9 10 Number of nodes Number of message saved 10 8 6 4 2 0 Number of nodes with useful information: Message saved with distributed processing: 6 hops (b) -20 0 20 40 60 80 100 1 2 3 4 5 6 7 8 9 10 10 8 6 4 2 0 Number of nodes Number of message saved Number of nodes with useful information: Message saved with distributed processing: 10 hops (c) Figure 15. Messages saved versus the number of nodes: a) Three hops; b) Six hops; c) Ten hops. Anchor nodes Non-anchor node Message transmission Base Station CH i CH j Cluster Head nodes CH 1 Figure 16. Example of the use of clusters. S6: Base Station executes the same cooperative positioning algorithm than the clusterhead nodes, but using the information delivered from these clusterheads. In this way, if the tag positioning comes from just one clusterhead, this position will be considered as the final solution. But, if it is received from more than one clusterhead, the centroid estimation is applied to all of them. Determining when the use of clustering saves more energy is not trivial. It depends on the size and complexity of the network. But in general, it is reasonable to think that clustering techniques are better for wide and complex networks. Additionally, a distributed processing such as the one proposed in this paper, increases throughput and reduces the response delay, because traffic bottleneck and collisions close to the Base Station are avoided. Distributed processing also spreads computational load over the network. This is especially important for wide networks or with multiple non-anchor nodes. V. ACCURACY OF LIS We have compared the accuracy of LIS versus the classic CL algorithm [25] using different simulations. The tested network was made up of 25 anchor devices with a radio range of 200 meters and separated also by about 200 meters. Anisotropic radiation pattern is assumed. The simulator has been developed in C++. It allows the selection of radio range, radiation pattern, noise, sensibility, network deployment and anchor location. Friis equation is used to calculate the received RSSI level in every node. All parameters, in the tests have been selected to model Telosb devices. The results of the simulations are presented in the next subsection. A. Error vs. Position The following experiments include a moving tag. The noise has been neglected and the error is expressed in meters. Figures 17 and 18 show the position error in front of the position of the non-anchor node. Maximum and medium errors of LIS algorithm are considerably smaller than the ones estimated with the (CL) Centroid classic algorithm. As we can see in figure 18, with LIS the errors always remain less than a 25 %of the distance between anchor nodes. B. Error vs. Coverage In this test, radio range is increased while the distance between nodes remains constant. Figure 19 shows the influence of radio range. As the radio range increases, the number of non-anchor nodes that receive a beacon also increases, and the error decreases. In all the cases, LIS gets smaller errors than centroid algorithm. Similar results are obtained fixing the coverage area of the non-anchor nodes and reducing the distance between anchor devices. C. Error vs. Noise In this test we have analysed the error obtained in a fixed position of the non anchor nodes when adding Gaussian noise to the system. All analyses use a coverage area of 200 m for the tag. We have made 1000 analysis at every point for the simulations. The number of errors (figure 21) represents the number of absolute errors bigger than 100 m (1/2 of the coverage area) obtained in the localization. As it can be seen, LIS always has less number of errors bigger than 100 m. than the classic CL algorithm. This result shows that despite the interferences, LIS continues to offer good accuracy for localization. JOURNAL OF NETWORKS, VOL. 8, NO. 1, JANUARY 2013 53 © 2013 ACADEMY PUBLISHER