Sensor nodes inWireless Sensor Networks (WSNs) are prone to failures due to the fragile hardware, malicious attacks, or hostile or harsh environment. In order to assure reliable, long-term monitoring of the phenomenon under investigation, a major challenge is to detect node malfunctions as soon as possible and with an energy efficient approach. We address this problem by using a system-level diagnosis strategy in which the sink issues to the WSN a self-diagnosis task that involves a number of mutual tests among sensors. Based on the test outcomes, the sink executes the diagnosis procedure. This work presents an algorithm for the assignment of tests among the sensors of a WSN that assures the desired system diagnosability and that is aware of energy consumption. We show by simulation experiments that the present approach, as compared to a previous one, enables consistent energy savings on the sensors.

A plethora of applications of Wireless Sensor Networks (WSN) [1], including medical diagnosis, infrastructure monitoring, environmental sensing, between others [5,9,16] incur on reliability issues. Corke et al. [9] emphasises the need for software utilities and hardware tools to remotely control and monitor deployed nodes and networks in such a way that slow degradations in transducer performance or battery capacity, for example, are detected and rectified. In this paper, we are concerned with an energy-aware testing approach for identifying node malfunctions in a WSN. As in [28], we adopt asystem-level diagnosis strategy in which we assume that extreme readings produced by presumable faulty sensors are detected by the sink, which establishes a connection assignment, i.e., that requests the execution of a set of mutual tests in the neighborhood of the nodes under monitoring. The results of such tests are collected by the sink which, in turn, executes a diagnosis algorithm in order to detect the faulty sensors (if any).

The field ofsystem-level diagnosis has evolved from the work of Preparata, Metze, and Chien, which proposed the first diagnosis model, known as PMC [19]. In the PMC model, a system is considered as a set of units that are able to execute mutual tests among themselves. The system is represented as a directed graph where vertices represent the system units, and a testing link exists between unitsu_i andu_j if there is a communication link between them and unitu_i tests unitu_j. The set of test outcomes, known as thesyndrome, is decoded by a centralized system supervisor. Preparata et al. [19] and later Hakimi and Amin [14] characterized the PMC model stating the topological properties of the diagnostic graph under which a system is diagnosable. An efficient syndrome decoding algorithm for the PMC model able to identify all faulty units was proposed by Dahbura–Masson [12]; another algorithm able to identify almost all faulty units was later proposed in [4].

Although many system-level diagnosis approaches have been proposed so far [2,3,13,20,23], the fact that the PMC model relies on a central supervisor finds applicability in WSN due to the presence of the sink that can collect and process the diagnostic information.

The present work considers the problem of building a connection assignment of the sensors in a WSN in order to ensure an energy-aware diagnosable system. The PMC model defines a system ofn units ast-diagnosable if all faulty units can be diagnosed provided the number of faulty units does not exceedt [19] (t is also called thediagnosability of the system). In order to diagnoset units, the following conditions must hold: (c1) the numbern of units in the system must be greater than or equal to 2t+1, and (c2) a unit must be tested by at leastt other units [19].

The conditions (c1) and (c2) above are necessary and sufficient fort-diagnosability provided there are not reciprocal tests, i.e., no two units test each other. On the other hand, if there are units that test each other, a third diagnosability condition is formulated in replacement of (c2) [14], for which a corollary is given: (c3) letG be a digraph of a system ofn units; ifκ(G) ≥t then the system ist-diagnosable, whereκ(G) stands for the connectivity ofG, i.e., the minimum number of vertices whose removal disconnectsG [10].

Specifically, we present an heuristic that chooses the set of sensors to be involved in the tests in order to meet the conditions above. This heuristic, calledEnergy Efficient Test Assignment without reciprocal tests (EETA) builds over our preliminary work [28].

The rest of this work is organized as follows: the next section presents related work. Sections3 and4 present the diagnostic model and the energy model, respectively. In Sect.5, the energy efficient test strategy is described. In Sect.6, simulation results are evaluated in comparison with a previous approach. Section7 presents concluding remarks.

The work of Corke et al. [9] is concerned with outdoor applications of wireless sensor networks involving natural environment or agriculture like microclimate monitoring for farms and rain forests, water-quality monitoring and cattle monitoring and control. Nevertheless, the work also addresses the challenges faced by the authors to ensure the reliability of the deployed sensors and networks. For soil moisture monitoring application, the sensor board includes power supply, solar charging circuit, and sensing for on-board temperature, battery voltage and charging current. In rainforest monitoring, in the default mode of operation, all energy for the devices come from rechargeable batteries working in combination with solar panels. In the event no further energy is harvested for long periods, the system switches to nonrechargeable energy supply when the rechargeable battery voltage falls below a threshold, and switches back whenever this voltage rises again. In a lake water quality monitoring application, a robot is used to crosscheck the calibration of deployed nodes using its own higher quality temperature transducer in such a way that anomalous events detected by the network are automatically investigated.

In [6], Chessa and Santi present a comparison based testing strategy in which the diagnosis model exploits the one-to-many communication paradigm typical of ad-hoc networks. Both hard and soft faults are considered and the diagnosis is based upon comparison of the results generated by testing tasks assigned to pairs of units with a common neighbor.

In [27], the problem of determining a connection assignment of the sensors in a WSN is considered. Two strategies are shown, one for the scenario in which reciprocal tests among sensors are possible and other for the scenario in which there are no reciprocal tests. In both cases, a square regionR which encloses all sensors that raised an alarm is considered. The testing strategies establish the way the sensors in the regionR coordinate actions to perform the testing tasks. The strategy with reciprocal tests defines that a sensor must test all its neighbors, and considers that the number of sensors in regionR is big enough to reach the desired diagnosability. In the strategy without reciprocal tests, the regionR is partitioned into four quadrants of equal size. Sensors present in the same quadrant do not execute reciprocal tests. The sensors in one quadrant ask for tests to the sensors in the successor quadrant and they are asked for tests by the sensors in the predecessor quadrant. Simulations show for which topological properties of the diagnostic graph a desired level of system diagnosability is ensured for both strategies. More details of the approach presented in [27] are shown in Sect.6.

Some works fit the research trend of diagnosis in WSN. In [30], the authors propose a comparison-based fault locating arithmetic for multisource network cluster nodes. The approach is based on layer-built topology structure and one-to-many communication mode. In [8], the authors present a distributed adaptive scheme for detecting faults in WSN where each node makes a local decision based on comparisons between neighbors, along with the dissemination of the decision to them. Time redundancy is used to enhance the accuracy of detection and tolerate transient faults in sensing and communication.

Energy-aware testing strategies are presented in [7,24], and [25]. In [7], Chessa and Santi proposed an energy-efficient fault diagnosis protocol for wireless sensor networks. This protocol, calledWSNDiag, is capable of diagnosingcrash faults.Crash faults are permanent and the faulty sensors can not do any kind of communication. The diagnosis process begins after a fault-free sensor, or an external unit, asks for the diagnosis. Thus, the diagnosis works on demand, resulting in an economy of energy for the whole system. The protocol is capable of correct diagnosis in a system with up tot faulty units, wheret<k(G) andk(G) stands for the connectivity of the system. In [24], an energy-efficient distributed approach improves network lifetime by detecting data faults locally in cluster heads. The type of data faults is identified by using trust and reputation concepts. The sensors that belong to the same cluster share and compare their readings. From these comparisons, each sensor generates a set of possible faulty neighbor sensors. The cluster head verifies which sensors present more fault indications to find the set of possible faulty sensors in the cluster. In [25], another energy-efficient cluster-based approach avoids performance degradation aiming at detecting in advance the failures that may cause connectivity loss.

Some other works relevant to ours study topological properties of networks. In [18], a formal proof is presented for the minimum degree a network must have in order to bek-connected with high probability provided the numbern of the nodes in the network is big enough. In [29], the authors show how many neighbors the nodes of a network withn randomly placed nodes should be connected to in order to the overall network to be connected. The problem of determining the critical transmitting range (CTR) for connectivity in mobile ad hoc networks is studied in [22]. In this work, Santi investigates the relations between the CTR in case of stationary networks with uniformly distributed nodes and two other cases. The first is the CTR in the presence of M-like node mobility (where M is an arbitrary bounded and obstacle free mobility model) and the second is the case of RWP mobility [15] (which is the most common mobility model used in the simulation of ad hoc networks).

In our model, we consider a WSN composed of sensors deployed in a sensing area with uniform distribution. We assume that the topology of the WSN is known to the sink. We also assume that each sensor knows its geographical coordinates within the sensing area and that this information is known to the sink. The WSN is modeled as the system graphG=(V,E) where each vertexv inV represents a sensor and an edge (v_i,v_j)∈E if and only ifv_i andv_j∈V are within the transmission range of each other.

The sensors perform a monitoring task aimed at raising an alarm when they detect anomalous events (for example, in agriculture, the sensors may check for the level of some chemical reactants in a large cultivated area and raise alarms when such level exceeds a given threshold). The alarms are sent to the sink, which before forwarding the alarm to the user, start a diagnosis procedure to check for their correctness. The diagnosis procedure may also be started by the sink on demand or when anomalous readings are reported by a set of sensors. We assume that a setT (of cardinalityt) of sensors have had their readings reported. In response, the sink asks a number of mutual tests among a set of nearby sensorsQ, whereT⊂Q.

The nature of the test is application dependent; in WSNs, some of the most common causes of failures include sensor calibration faults, hardware faults due to harsh environments, connection failures, low battery, between others [26]. In general, a test (v_i,v_j) consists of a set of input stimuli that are produced by the testing sensorv_i and sent to the tested sensorv_j. In turn,v_j produces a test result that is sent back tov_i. Finally,v_i compares the output produced byv_j with the expected output and it produces the test result that is a binary outcome: it is 0 if the two results match (and then the test succeeds), and it is 1 otherwise (i.e., the test fails). As in the PMC model it is assumed that the outcome of a test performed by a fault-free sensor is always reliable (i.e., it is 0 if the tested sensor is fault-free and it is 1 if the tested sensor is faulty), while it is completely unreliable if the testing sensor is faulty. All the test outcomes are finally collected by the sink and decoded by using a suitable diagnosis algorithm.

In the PMC model, the execution of the test requires a bidirectional link betweenv_i andv_j. However, as observed in [6], in WSN the tests may also be executed in presence of unidirectional links. In particular, a sensor may start a self-test on a predefined set of stimuli and it may send the output to another sensor that compares it with the expected results. Clearly, this second test model does not require a bidirectional communication link between the tested and the testing sensors, but it is sufficient only that the tested sensor be able to send its output to the tester. In this paper, we consider tests executed in presence of unidirectional links, and the case in which there are no reciprocal tests. Thus, the diagnosability can be derived by conditions (c1) and (c2) described in Sect. 1.

Our goal is for the sink to define a test connection assignment to be used by the sensors to perform the tests. The connection assignment is a testing graphD=(V_D,E_D), whereV_D⊂V,E_D⊂E and an edge (v_i,v_j)∈E_D if and only ifv_i testsv_j. We definen as the cardinality ofV_D.

The heuristic for the definition of the graphD also seeks for the reduction of the energy consumption needed for the execution of the tests. This is obtained by limiting the number of sensors that take part in the testing procedure. The selection of the sensors ofV_D also takes into account their geographical position in order to minimize the distance between the tested and testing sensors. This ensures tests with smaller energy cost.

For the definition of the testing graphD, the sink at first identifies the geographic regionR where the readings were generated. This region is defined as the smallest rectangular area that comprises all of the sensors inT. Figure 1 shows an example of the definition of the regionR witht=3. In the figure, circles represent sensors. Sensors shown with an “X” belong toT.

Network with the definition of the regionR, witht=3

Full size image

The sensors inV are divided into 4 groups, or quadrants, using the pointR_c, the center of regionR, as the basis for the division. Figure2 shows an example of the division of the network into quadrants. We defineV_i as the set of sensors present in quadranti (i=0,…,3). Thus, we haveV=V₀∪V₁∪V₂∪V₃.

Example of the division of the network in quadrants usingR_c

Full size image

Similarly to [27], tests are executed in a predefined order between the quadrants, which ensures that reciprocal tests do not occur. Each quadrant has two neighbors. In a counterclockwise order, they are called the predecessor quadrant and the successor quadrant. As opposed to that strategy, in which the sensors seek fort testers between the sensors in the successor quadrant and build the testing graph in a distributed way, in the present strategy the sensors ofV_D, defined by the sink, execute a predefined diagnosis task, whose output is sent to their testing sensors located in the predecessor quadrant. These sensors, in turn, send the binary outcome to the sink.

It should be observed that, in order for the diagnostic graphD to bet-diagnosable, the conditions (c1) (i.e., thatn≥2t+1) and (c2) (i.e., the indegree of each vertex inD is at leastt, or, in other words, each sensor is tested by at leastt other sensors) should be met [19].

In order to estimate the energy consumption of a given testing assignment, we consider the one-slope model [17], a widely used propagation model in wireless communications. This model assumes a linear dependence between the path loss (dB) and the logarithm of the distance d between the transmitter and the receiver, as expressed in1:

(1)

wherel₀ is the path loss at a reference distance of 1 meter (though the paper we express distances in meters), andα is the power decay index (also called path loss exponent). In general, to ensure a communication between a transmittert and a receiverr placed at distanced from each other it is necessary that the packet sent byt reachesr with a power level higher than the sensitivity of the receiver. In other words, lettingE_t be the transmission power of the transmitter,E_r the power of the signal at the receiver (whereE_r depends onE_t and the distanced), and Em be the sensitivity of the receiver, must beE_r>E_m.

By (1) must be

(2)

IntroducingE_r>E_m in2, we obtain that the minimum transmission powerE_t at the transmitter that ensures that the packet reaches the receiver with the required power is

(3)

Now (3) depends on the distanced, the sensitivity of the receiver and the parametersl₀ andα. For the latter parameters, we take in the simulations typical values [21] (in particular, we setl₀=10 andα=3), whileE_m depends on the actual hardware of the WSN.

From (3), it follows that the energy spent grows polynomially with the distanced, with an exponent equal toα.

The Energy Efficient Test Assignment without reciprocal tests (EETA) algorithm builds the testing graphD by taking into account the total energy cost needed for the sensors to execute all the tests of the connection assignment. To this purpose, EETA definesC_i,j as the energy cost spent by the sensorsv_i andv_j when the sensorv_i executes a test over the sensorv_j.

Initially, EETA initializes setV_D as the set of sensors in regionR. Considering the division in four quadrant of the WSN, alsoR results divided in four quadrants accordingly. As a result also the sensors in setV_D can be considered split into four subsets, each corresponding to a quadrant. Specifically, we defineQ_i (with 0≥i≤3) as the set of sensors positioned in quadranti and selected for the connection assignment. Thus, we haveV_D=Q₀∪Q₁∪Q₂∪Q₃, withQ_i⊂V_i.

In order to satisfy the conditions stated in Sect.3, each of theQ_i must be composed of at leastt sensors (with the sensors ofT included). Witht sensors in each quadrant, each sensor can be tested byt others (c2) and the number of sensors that participate to the diagnosis is sufficient to satisfy (c1), once we have 4t≥2t+1. As long as the testing strategy tries to diminish the number of sensors inV_D, we haven=4t, the minimumn required in our heuristic. Furthermore, the distance toR_c, the center of regionR, is also taken into account to choose the sensors inV_D.

Note that the initial selection ofV_D may not be sufficient to ensure thatt sensors per quadrant are chosen, hence, in this case, other sensors outsideR should be added toV_D. However, in cases where the regionR is near the border of the network, it may not be possible to have at leastt sensors in each quadrant. In order to guarantee the number of testers per quadrant, the centerR_c of the regionR is then shifted toward the center of the network andR is enlarged accordingly.

The total energy cost spent by the tests made by the sensors present in quadranti is defined as, i.e.,∀(v_i,v_j)∈E_D∣v_i∈Q_i and. We also define the total energy cost spent by all tests made byD asC_T(D). Thus, we have. The selection of sensors ofV_D is made to minimize the total energy consumption by tests between sensors.

For the diagnosis to be possible, condition (c2) must be fulfilled. As |Q_i|=t, we can conclude that a sensorv_k∈Q_i will test all sensors present in, i.e.,E_D={(v_k,v_l)∀v_k∈Q_i and fori=0,…,3}.

It should be observed that edge (v_i,v_j)∈E_D may not exist initially inE, i.e., the sensorv_i may not be on the transmission range of the sensorv_j. In order to make possible that the sensorv_i testsv_j it is necessary that the transmission range ofv_j be tuned. So the sink asks the sensors that are not neighbors of their testing sensors, i.e., that make and edge inE_D, to augment their transmission ranges (i.e., the transmission power) in order to enable the test. The underlying assumption is that the network is dense and large andt is relatively small with respect to the network density so that the cases in which a sensor must augment its transmission power is unlikely to happen.

In order to permit that the selection of sensors in each quadrant makes the reduction ofC_T(D) possible, an initial heuristic is used. At first, the sensors inT are selected for each of the quadrants in which they are positioned, since those sensors must participate to the testing procedure. Thus, we defineT_i as the set of sensors ofT geographically positioned in quadrant i. The cardinality ofT_i is equal tot_i. Thus, we haveT_i⊂Q_i and. Considering the energy model presented in this work, the energy cost needed for the execution of a test grows polynomially with the geographic distance between the sensors. Thus, if sensors that are geographically near are selected forV_D, we have a higher probability of generating a testing graphD with a value ofC_T(D) that is reduced.

The initial selection of sensors inV_D is thus based on the distance of the sensors to a common point,R_c in this case. Based on this principle,Q_i is initially formed by thet_i sensors ofT_i and thet−t_i sensors of the quadranti geographically nearer fromR_c. Thus,V_D is formed mainly by sensors near toR_c. Figure 3 shows an example of the definition of the setV_D. Black bullets represent sensors that belong toV_D. It should be observed that the simple strategy of picking up any initial set oft sensors does not lead to an optimal solution.

Definition of the initial setV_D with the sensors ofT (marked with an “X”) and the sensors geographically nearest fromR_c, witht=3

Full size image

Even though the initial heuristic has the goal of selecting the nearest sensors to the pointR_c, it should be observed that a sensorv_k∈T_i may be farther fromR_c than a sensorv_l∈(V_i−Q_i). Nevertheless, every sensorv∈T must participate to the diagnosis procedure, regardless of its distance to the pointR_c.

Although the sensors selected by the initial heuristic are the nearest from the center ofR, farther sensors may be less distant from the majority of sensors present in their predecessor and successor quadrants, and may produce smaller test costs. This case can be seen in Figs.4 and5. In the example of the figures, the exchange of a sensor farther fromR_c than another, but nearer from the majority of the chosen sensors in the neighbor quadrants may diminishC_T(D). In order to evaluate the possible sets of sensors that guarantee a minor value forC_T(D) than that obtained by the initial heuristic, an algorithm is executed.

Example of choice of sensor farther fromR_c with lower energy cost

Full size image

The network after the exchange of the sensors that participate to the testing graphD

Full size image

Consider the sensorsv_k∈V_i andv_l∈V_i. The sensorv_k is defined as the sensor farthest fromR_c that belongs toQ_i, andv_l is defined as the sensor geographically nearest to the sensorv_k, and farther fromR_c thanv_k, so thatv_l∉Q_i. In other words,v_l is the sensor nearest fromR_c that was not selected forQ_i. The algorithm consists in verifying if the exchange of any sensorv_n∈Q_i by the sensorv_l produces a reduction inC_T(D). The exchange that produces the higher reduction inC_T(D) is performed. The process is repeated searching for other possible exchanges and is finished once the exchange of a sensorv_n∈Q_i by any sensorv_l∉Q_i does not generate a reduction inC_T(D).

This process is performed in all of the quadrants, one quadrant at a time, i.e., at first the possible exchanges are verified in quadrant 0, until no exchange is performed, then the process is initiated in quadrant 1, and so on. The strategy is finished when there is no exchange in any of the four quadrants.

Although the quadrants may be visited more than once in the searching for possible exchanges, the strategy is finite once at some point every farther sensor will produce a higher cost. It is also clear that this heuristic iterates at most a number of times equal to the number of the sensors in the network.

In this section, simulation results whose goal is to evaluate the energy consumption of the testing strategy are presented.

The simulation results presented in this section show a comparison analysis of the energy consumption between the strategy with no reciprocal tests presented in [27], TAWR (Test Assignment Without Reciprocal tests), and the EETA heuristic.

TAWR [27] divides the regionR into four quadrants. Sensors of a quadrant ask for tests for sensors on the successor quadrant and test sensors on the predecessor quadrant. Thus, the sensors themselves define the testing graph. Furthermore, the test procedure is not based on a self-test as in EETA, which produces greater information exchange between the sensors and thus greater overhead. More specifically, in TAWR each node asks for tests broadcasting a message seeking for testers. Sensors in the neighbor quadrant that receive the messages answer sending testing stimuli. Then the tested sensors send test replies to the testers. Thus, the overhead is greater than that of EETA, in which the sink defines the testers of each node and the tested sensors send replies to a predefined set of testing stimuli.

In all of the simulations, networks of size 100×100 m² composed of 512 and 1024 sensors are considered. For each simulation experiment, a region with 10% of the total size of the network is randomly defined.t sensors of this region are randomly selected as the sensors ofT. Experiments were run for the following values oft: 5, 8, 10, 12, and 15.

For each set of input values, a set of 100 different random network graphs were generated. For each graph, the simulator creates the diagnostic graphD and calculates the energy costC_T(D), based on the models presented in Sects. 4 and 5.

In EETA, the cost of a test executed by sensorv_i on sensorv_j at a distanced from each other is computed as the sum of the energy spent byv_j to send the output sequence of a self-test tov_i, and byv_i to receive such outcome. In particular, for each packet sent we consider (3) instantiated with typical values of class mote sensors, taken from their datasheets [11], and we make the assumption that each test involves 100 packet’s transmissions.

In TAWR, the testing links are bidirectional, as in the traditional PMC model. Thus, the cost of a test executed by sensorv_i on sensorv_j is equal to the sum of the energy spent sending a test task from sensorv_i to sensorv_j plus the test reply by the tested sensorv_j back to sensorv_i. As opposed to the results presented in [28], in which only the cost of sending an output test sequence was computed for comparison with EETA, in the present work the overall cost of TAWR is taken into account for comparison purposes.

Four sets of experiments were run. Figure 6 shows the ratio between the total energy costC_T(D) consumed by the tests of graphD of both strategies, and for different values of t. Not surprisingly, the strategy EETA presents smallerC_T(D) in all simulation experiments, either on networks with 512 sensors or on networks with 1,024 sensors.

Ratio between the total energy cost presented by strategies EETA and TAWR, for different values oft

Full size image

Furthermore, the algorithm of strategy EETA employs a smaller number of sensors in the diagnosis process. Thus, less tests are performed, generating smaller total energy costsC_T(D). TAWR uses more thant sensors in each quadrant; ast sensors are needed for each sensor that participates in the diagnosis that makesn>4t in that heuristic. Figure7 shows a comparison between the number of sensors used in the diagnosis process in both strategies. For strategy EETA, a number of 4t sensors is always used. For strategy TAWR, on the other hand, the number of sensors used in the diagnosis process increases with the network density. Even though the increase in the network density ensures tests with a smaller cost in both strategies, the use of a greater number of sensors increments the total energy cost in strategy TAWR. It should be observed that in Fig.7 the results of strategy EETA for 512 sensors and for 1,024 sensors are overwritten, once they are the same (4t), i.e., strategy EETA always uses the minimum number of sensors in the diagnosis process. Figures 8 and 9 show the testing graphs generated in each strategy for the same set of initial nodes under monitoring. It should be observed that the number of sensors used by EETA is reduced if compared to the number of sensors used by strategy TAWR.

Number of sensors used by strategies EETA and TAWR, with different values oft

Full size image

Testing graph for strategy TAWR

Full size image

Testing graph for strategy EETA

Full size image

Figure 10 shows the ratio between the average energy costs used by both strategies. The average cost is calculated by the division of the total energy costC_T(D) by the number of sensors used in the diagnosis process. Similarly to the total energy costC_T(D), the average cost is also smaller for strategy EETA.

Ratio between the average energy cost presented by strategies EETA and TAWR, for different values oft

Full size image

The strategies have their maximum costs compared in Fig.11. The maximum energy cost used by one strategy,C_M(D) is equal to the energy consumption presented by the sensor with maximum cost, i.e., between all of the sensors that participate to the process, the sensor with highest energy consumption is chosen. The cost of this sensor is then named the maximum cost ofD. Thus, we haveC_M(D)=max(C_i∀v_i∈V_D), whereC_i is the total cost presented by the sensorv_i. Again, EETA performs better than TAWR.

Ratio between the maximum energy cost presented by strategies EETA and TAWR, for different values oft

Full size image

In this paper, we have addressed the problem of building a connection assignment of the sensors in a WSN in order to ensure an energy-efficient test procedure. The EETA heuristic (Energy Efficient Test Assignment without reciprocal tests) is compared with a previous approach named TAWR (Test Assignment Without Reciprocal tests). Both strategies divide the network in four quadrants to construct a testing graph in which reciprocal tests do not occur. However, EETA seeks to minimize the energy consumption of the testing procedure by reducing the number of sensors that take part to the diagnosis procedure and by reducing the distance between them. An energy model is adopted, in which the energy cost of a test between sensors grows polynomially with the distance between them.

Experimental results show that EETA presents total, average and maximum energy costs smaller than TAWR. Furthermore, EETA applies a smaller number of sensors than TAWR. Future work includes simulation experiments to evaluate the scalability of the solution presented, and the comparison with other energy-efficient approaches. We also plan to investigate the fairness in the energy consumption of the sensors, and strategies that assign testing tasks to sensors with more residual energy.

Authors and Affiliations

1. Dept. Informatics Centro Politécnico, Federal University of Paraná, Jdim. Américas, 81531-990, Curitiba, Pr, Brazil

   Andréa Weber & Alexander Robert Kutzke

2. Institute for Science and Technology of Information, Via G. Moruzzi, 1, 56124, Pisa, Italy

   Stefano Chessa

3. Computer Science Department, University of Pisa, Largo Pontecorvo 3, 56127, Pisa, Italy

   Stefano Chessa

Corresponding author

Correspondence toAndréa Weber.

Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0 ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Reprints and permissions