Near-Optimal Diagnosis System Deployment in Wireless Sensor Networks

Abstract

Wireless sensor networks (WSNs) have been extensively applied in many important fields with larger scale and more complex structure. The applications of WSNs are regarded as a sustainable solution to provide ongoing and efficient monitoring services in the real world. When such an application of WSNs faces poor performance or unexpected condition, the administrator needs to deploy a diagnosis system to diagnose the task. One possible way is to transform some original motes as diagnosis motes by using reprogramming technique. However, the challenge is how to achieve best efficiency in the diagnosis nodes selection processing. Moreover, the required network evidence is always distributed in multidimensional data spaces. The existing approaches fail to consider this multidimensional feature of evidence in diagnosis nodes selection problem. To address the above issues, we propose a solution for the multidimensional diagnosis nodes selection problem and give the corresponding upper bound. Lastly our experimental results demonstrated that our approach is scalable and applicable for real WSNs.

1. Introduction

Wireless sensor networks (WSNs) have been extensively applied in many important fields, such as environment monitoring, national security, power system, and health care. Usually, to cover the targets being monitored, a huge population of sensors should be deployed in the interested area. Accurate and real-time fault diagnosis is of great significance for ensuring the system functionality and reliability when a large-scale and sophisticated wireless sensor network faces poor performance or unexpected condition; in particular when a few faulty nodes can heavily degrade the system performance and shorten the network lifetime, an efficient diagnosis tool is needed to collect the diagnosis evidence for analyzing and identifying the root cause in an online mode.

Our approach is motivated by a recent WSN project, called CitySee [1]. In this project, we have deployed 1200 sensor nodes in the urban area. For such a long-term large-scale WSN application, CitySee always needs to do some diagnostic tasks for unexpected network condition. So how to deploy a diagnosis system for collecting required network evidence is significant. Furthermore, the network evidence is always distributed in multidimensional data spaces such as physical dimensional evidence (temperature, humidity) and inference dimensional evidence (flow reconstruction, current link capacity).

Usually, the strategy of diagnosis system deployment can by divided into two types, including adding diagnosis nodes into the existing WSNs and changing the usual nodes in existing WSNs to diagnosis nodes. The latter diagnosis pattern can be divided into active detection and passive detection. Borrong Chen et al. [2] propose a passive monitoring mechanism to monitor the whole view of WSNs with a large scale, and [3, 4] also introduce a passive detection and local fusion to collect diagnosis evidence. According to these papers, it is obvious that the collection of diagnosis evidence is the first step for diagnosis, which leads to an important problem that is how to deploy the diagnosis sensor to cover diagnosis evidence in exiting WSNs. However, for WSNs, usually, only one type of information or parameter is considered, such as temperature monitoring system and CO₂ monitoring system; as for diagnosis, there are more than one kind of information needed, such as sensor energy, and communication path status. The required network evidence is always distributed in multidimensional data spaces. So another new important problem is showing up that is efficient-coverage of diagnosis evidence in multidimension information space.

In order to address the above issues, in this paper, we propose a diagnosis system deployment solution for WSNs. The basic idea of our approach is to formulate the diagnosis system deployment problem as an optimization problem and to achieve problem solution by proposing a greedy heuristic algorithm. To the best of our knowledge, there is no previous work addressing the multidimensional diagnosis nodes selection (MDNS) problem for diagnosis system deployment in wireless sensor networks.

Our contributions in this work can be summarized as follows.

• (1)

We formulate diagnosis nodes selection Problem (DNS) and multidimensional diagnosis nodes selection (MDNS) problem in WSNs.

(2)

We prove the complexity of MDNS problem with Theorem 3.

(3)

We propose a greedy heuristic algorithm to solve the MDNS problem and represent an approximation factor to guarantee the correctness and effectiveness of our algorithm in Theorem 4.

(4)

We evaluate our greedy heuristic algorithm in a real WSN system for diagnosing task.

The rest of the paper is organized as follows. Section 2 discusses the related work. Section 3 presents design of diagnosing system deployment. Section 4 evaluates our algorithm, and Section 5 concludes this paper.

2. Related Work

Senor nodes are faced with various failures, which are due to poor quality, lifetime, and harsh environment and during running process. These failures always result in serial network faults, such as fault of terminal systems or route equipment, destroyed internet wire. Therefore, no matter from which part of network system the failure comes; it must be paid attention to an efficient diagnosis tool that should diagnose the type of the fault with enough diagnosis evidence; otherwise the WSNs will face to poor performance, even fault. Although efficient coverage of evidence is a prerequisite for diagnosis, diagnosis evidence coverage is rarely considered in previous diagnosis papers, especially for multidimension data space.

Firstly, diagnosis system deployment problem is a fundamental research problem, where many researchers have studied. There are mainly two approaches to deploy diagnosis system, including centralized approaches and distributed approaches. In centralized approaches, a logically or geographically centralized sensor node, called base station or sink node, with high performance, such as large memory size, fast data processing, and more energy, diagnoses the whole view of network. Staddon et al. [5] proposed a centralized approach that enables the base station to know the node topology. Once the base station learns the whole network topology, the failed nodes can be efficiently located using a simple divide-and-conquer strategy based on adaptive-route updated messages. Koushanfar et al. [6] propose an online model-based testing technique as the solution of incorrect computation faults.

Although the centralized approaches are precise and efficient in some conditions, they cannot be promoted for large-scale networks, because it is very costly for the sink node or base station to process data from every sensor node and diagnose them in a centralized manner in WSNs with a large scale.

In distributed approaches, each sensor node will be transformed to the diagnosis node at a certain level to process the local information; with these approaches, the diagnosis can be allowed to scale easily to much larger and denser WSNs. Many approaches are proposed in this area, such as passive monitoring approach, self-monitoring detection approach, probability-based approach, and watchdog approach. Borrong Chen et al. [2] introduced a group of tools and techniques for rebuilding complex dynamics of live sensor network deployment. They are dependent on passive and external packet monitoring coupled with trace merging and high-level analysis to reconstruct LiveNet. Dong et al. [7] are the first to propose the method of finding the optimized self-monitoring topology for WSNs. They claim that the problem is NP-complete even under the Unit Disk Graph (UDG) model, and give the upper bound on the approximation ratio. Mahapatro and Khilar [8, 9] present a hybrid approach which utilizes both the sensor node coordination and sensor node self-detection to diagnose the local information. The idea of watchdog or local monitoring to relieve attacks in sensor and ad hoc networks is introduced in previous papers [10–15]. Marti et al. [16] are the first to introduce the concept of watchdog in ad hoc networks for detecting mischievous nodes. The straightforward approach is based on the watchdog mechanism, and the main principle is that the diagnostic node catches the packets from its one-hop neighbor by overhearing.

In another aspect, some previous work focusing on target coverage problem in wireless sensor network should be mentioned here. In sensor coverage problems, the most important aim is how the sensor can observe the physical space, especially the centered information. The goal is to cover the interested information or region using as least number of sensors as possible. The problems in sensor coverage can be grouped in two types: point or target coverage [17–20] and area coverage [21–23]. The purpose of point coverage is to cover a set of points or targets and the solving process of point coverage is to identify the maximal support/breach paths that traverse a sensor field, while the purpose of area coverage is to cover or monitor an area and the solving process of area coverage is to collect the whole interesting information in an area as much as possible.

The purpose of both of the two types is to cover the interesting information with lower energy or the less number of sensors. Slijepcevic and Potkonjak described the area coverage problem by modeling the area as a collection of fields; in the collection each field has the property that each enclosed point is covered by the same set of sensors. The most-constrained least-constraining algorithm is introduced to calculate the disjoint covers select sensors that cover the critical element, which is the field covered by a minimal number of sensors. These sensors have the priorities including covering a high number of uncovered fields, sparsely covered fields, and fields without redundancy. Cardei and Du et al. described the target coverage problem where disjoint sensor sets are modeled as disjoint set covers, in which each cover could completely monitor all the target points. This work has proved that disjoint set coverage problem is NP-complete, and it has given a lower bound for any polynomial-time approximation algorithm. Furthermore, this work reduces disjoint set coverage problem as a maximum flow problem, which is then modeled as a mixed integer programming. However, those approaches not only hardly focus on diagnosing system deployment, but also never consider the multidimensional network evidence in problem from a real project standpoint.

Our approach focuses on solving MDNS problem with multidimensional network evidence condition. We formally formulate the DNS and MDNS problems, propose a greedy heuristic algorithm, and give the corresponding upper bound of algorithm. To the best of our knowledge, there is no previous work addressing the MDNS problem for diagnosis system deployment in wireless sensor network.

3. System Design

In this section, we introduce preliminaries and problem formulation of our work. Firstly, we introduce the concept of diagnosis nodes selection problem and basic wireless sensor network coverage model for diagnosing system selection problem, which only focuses on the single dimensional in coverage characteristics. Then, we formulate the general diagnosis nodes selection problem as a multidimensional coverage problem and prove the problem complexity. Lastly, we propose an approximation algorithm and get the corresponding approximation factor.

3.1. Diagnosis Nodes Selection Problem in WSNs

We mainly focus on introducing basic concept of diagnosis nodes selection problem (DNS) in WSNs. If an application of WSN faces poor performance or unexpected condition, the administrator needs to deploy a diagnosis system by transforming some original motes as diagnosis motes by using reprogramming technique. In other word, the administrator selects some motes and changes their roles from the normal motes to the diagnosis motes which can run together as an entire diagnosis system and collect network evidence for problematic application.

However, the key question is how to achieve the best efficiency in this selection processing of diagnosis nodes. The typical solution is to formulate this motes selection processing as a coverage problem. The details are as follows. We consider a number of diagnosis evidence that need to be continuously achieved, and there is at least one set of motes that can obtain those pieces information. So this means that we only need to select minimal number of original motes as diagnosis motes which could achieve the required information in such a way that we can get the most efficient diagnosis system. Then the administrator sends the selecting command to the corresponding motes which change their running mode form original to diagnostic mode.

Figure 1 shows an example with six motes which include 2 motes (2 and 4) facing problem in target areas. If the administrator wants to get the evidence about motes 2 and 4, he/she could select the one-hop neighbors of problematic motes as diagnosis motes (motes 3 and 5) which could collect the evidence efficiently.

Figure 1

Example with diagnosis nodes selection problem. Note that motes 2 and 4 are located in target area, but could not response command. So the administrator chooses motes 5 and 3 as diagnosis motes to achieve the required evidence.

We assume that there are n wireless sensor motes $M=\{m_1,m_2,\dots ,m_n\}$ deployed in a certain geographic region. Each mote delivers the sensing data to the base station which is denoted by $m_1$ . Then we define the communication graph in the network as a directed graph G. If there is a communication link between mote u and v, we say that the two opposite direct links $〈u,v〉$ and $〈v,u〉$ exist. Then we give formal definition of diagnosis nodes selection problem (DNS) in WSNs.

Definition 1.

In diagnosis nodes selection problem (DNS) problem, we are given predefined required network evidence $E=\{e_1,e_2,\dots ,e_k\}$ , $|E|=k$ in one dimensional for diagnosing, and a whole network $M=\{m_1,m_2,\dots ,m_n\}$ that includes n motes, such that $|M|=n$ ; the evidence $e_{m1}$ collected by $m_1$ is part of E, and the corresponding cost is denoted by $c_{m1}$ . An DNS problem is collection C of some of the sets from $m_1,m_2,\dots ,m_n$ whose union is the entire required evidence E. Formally, C is a set of selected motes if ${\bigcup }_{m_i\in C}{e}_{mi}=E$ . We would like to minimize the entire corresponding cost ${\min }_C{\sum }_{m_i\in C}{c}_{mi}$ .

Note that in this problem, we only consider the evidence in only one dimension, for example, physical dimension (temperature). If we consider the evidence in multidimension, the problem would be more complex. Here is a multidimensional example shown in Figure 2. There are two dimensions in this problem including temperature and flow dimensions. Motes 2 could cover motes 1, 3, and 4 in flow dimension, but they only cover motes 1 and 4 in temperature dimension. This fact denotes the different cover capacity of the same mote with different dimensional features. In a word, if we consider multidimensional condition in DNS problem, the original problem would become a multidimensional diagnosis nodes selection (MDNS) Problem. To the best of our knowledge, our work is the first to consider the feature of multidimension in DNS problem. We propose the MDNS problem and the corresponding definition in next subsection.

Figure 2

Comparison of the feature capacity of same node with different dimension. Temperature range denotes the physical metric dimension in WSNs, and flow range represents the network metric dimension in WSNs.

3.2. Multidimensional Diagnosis Nodes Selection in WSNs

As mentioned before, our approach is motivated by CitySee system. In long-term running system, the administrator always faces diagnostic task for finding root cause of poor performance or a better understanding of the insight of system as measurement results. In particular, the administrator of CitySee focuses on 22 types of basic evidence for diagnosing including: temperature, illumination, humidity, RSSI (received signal strength indicator), ETX (expected transmission number), parent changing, and data flow. These types of evidence could be classified as three categories including: probability evidence, inference evidence, and physical evidence. For example, physical evidence always consists of illumination, humidity, and temperature which indicate the physical metric in real world. Unlike physical evidence, probability evidence focuses on the metrics which could be expressed by probability form. In a word, the 22 types of evidence are distributed in multidimensional data spaces. So DNS problem should be extended to a multidimensional environment.

We propose the definition of multidimensional diagnosis nodes selection (MDNS) problem. The basic assumption of problem is the same as the DNS problem mentioned in previous subsection.

Definition 2.

In multidimensional diagnosis nodes selection problem (MDNS) problem, we are given predefined required network evidence $E=\{E_1,E_2,\dots ,E_k\}$ , $|E|=k$ in k-dimension for diagnosing. Each subset $E_k$ consists of a number of evidence elements $\{e_1,e_2,\dots ,e_j\}$ . A whole network $M=\{m_1,m_2,\dots ,m_n\}$ includes n motes, such that $|M|=n$ ; the evidence $e_{m1}$ collected by $m_1$ is part of $E_1$ , and the corresponding cost is denoted by $c_{m1}$ . An MDNS problem is collection C of some of sets from $m_1,m_2,\dots ,m_n$ whose union is the entire required evidence E. Formally, C is a set of selected motes if the selected motes could cover all evidence in k-dimension ( ${\bigcup }_{m_i\in C}{e}_{mi}=E$ ). We would like to minimize the entire corresponding cost ${\min }_C{\sum }_{m_i\in C}{c}_{mi}$ .

Figure 3 shows an example of multidimensional feature with different capacity in a real-world WSN system which is deployed in $500\hspace{0.17em}\text{m}*500\hspace{0.17em}\text{m}$ area. We could learn that the different capacity with different dimension such as the green area and the yellow area denotes RSSI and humidity with different dimension, respectively. For the MDNS problem, there are two problems that need to be resolved. The first is what the complexity of this problem is. The second is how to solve this problem efficiently. To address these issues, firstly we propose a theorem to prove the complexity of MDNS problem shown as follows.

Figure 3

Different dimensional features with different capacity in a real-world WSN system which is deployed in $500\hspace{0.17em}\text{m}*500\hspace{0.17em}\text{m}$ area. The yellow range denotes the humidity sensing range of a mote, and the green denotes the link quality sensing range of the same mote based on RSSI (received signal strength indicator).

Theorem 3.

MDNS Problem is NP-complete.

Proof.

An instance of MDNS problem is given by a universe $U=\{u_1,u_2,\dots ,u_n\}$ which includes all network evidence and motes, a collection of m subsets $S_i\subseteq U$ of that global universe and an integer k. The question is how to select a collection C of motes at most k of these subsets which could cover all universe U and collect all network evidence at the same time.

To prove that MDNS problem belongs to NP, consider that we are given a collection C of set motes $m_1,m_2,\dots ,m_n$ . Then we can verify the constraints in polynomial time whether each evidence $e_i$ in E is collected by at least one time in collection $C=\{m_1,m_2,\dots ,m_n\}$ . To prove that MDNS Problem belongs to NP-complete, we formulate the vertex cover problem as the subproblem of MDNS problem in polynomial time. In the Vertex Cover problem, a vertex cover of a graph $G=〈V,E〉$ is the subset $V^{\prime }$ of V such that for every edge $e=\{i,j\}\in E$ either $i\in V^{\prime }$ or $j\in V^{\prime }$ .

Then we show that the complexity of Vertex Cover problem is equal to or less than the complexity of MDNS problem. Given an instance of vertex cover problem ( $G=〈V,E〉$ and an integer k), we will construct an instance of the MDNS problem. First let $U=E$ define n subsets of U including label the vertex of graph G from 1 to n. So let $S_i$ be the set of edges that is an incident to vertex i. Here $S_i\subseteq U$ for all i. Now we prove that the reduction can be done in a poly time between vertex cover with MDNS. Note that we suppose that all evidence has been already projected to a global dimension for simplicity.

Suppose that G has a vertex cover of size k, and let S be the set of motes. Then $|S|=k$ . Furthermore, C is a collection of motes that covered U and collected all network evidence. To justify this claim, consider that any element in U is also an edge e in graph G. Because S is a vertex cover of G, so one of the endpoint of e belongs to S. Therefore, C contains one of the sets associated with the corresponding endpoints of e.

Conversely, suppose that U has a collection C of size k in our constructed instance of MDNS problem. Each set in C is associated with a vertex in graph G, and S is the set of these vertexes. Note that S at most contains k motes because $|C|=|S|$ . For each edge e belongs to universe U, and the collection C should contain e at least one time. Our special construction ensures that the only sets that include e correspond to vertexes that are endpoints of e. So, S must contain one of the endpoints of e at least one time.

For the second issue, we propose a greedy MDNS heuristic algorithm for the MDNS problem. In MDNS problem, the network evidence is located in multidimensional features $E_1,E_2,\dots ,E_k$ . So firstly we need to choose one dimension for solving problem. Intuitively, we can start by solving the MDNS problem from the most important evidence dimension for diagnosing. However, the object of MDNS problem is to achieve all types of evidence required for diagnosing. That means that we could project the multidimensional network evidence into a global dimension as well as unchanging the final solution of MDNS problem.

Our projection process is based on administrator empirical knowledge. Firstly we define the corresponding cost assignment mechanism for network evidence which needs to be collected. Our main idea is based on a standard normalization process. Consider that the total cost of all network evidence is defined as 100%. Every network evidence would be assigned with a proper cost value in the standard normalization process. The original cost value is assigned by administrator as follows: ${\text{Cost}}_{\text{org}}=\{{\text{cost}}_{\text{org}}^{e1},{\text{cost}}_{\text{org}}^{e2},{\text{cost}}_{\text{org}}^{e3},\dots ,{\text{cost}}_{\text{org}}^{en}\}$ . In our solution, we normalize the value in interval from 1 to 100. Then the new cost value of e should be

$$\begin{array}{cc}& 100*\frac{{\text{cost}}_{\text{org}}^e}{{{\displaystyle \sum }}_{e\in E}{\text{cost}}_{\text{org}}^e}.\end{array}$$

(1)

So the normalized value of the cost is defined as follows:

$$\begin{array}{cc}& {\text{Cost}}_{\text{nor}}=\left\{{\text{cost}}_{\text{nor}}^{e1},{\text{cost}}_{\text{nor}}^{e2},\dots ,{\text{cost}}_{\text{nor}}^{en}\right\},\hspace{1em}e\in E.\end{array}$$

(2)

In this way, we get the normalized network evidence cost. The greedy MDNS heuristic algorithm is shown in Algorithm 1.

Algorithm 1: A greedy heuristic algorithm for MDNS problem.

Input:

  Network evidence $E=\left\{E_1,E_2,\dots ,E_k\right\}$ , $\left|E\right|=k$

   in k-dimension for diagnosing.

  Network $M=\{m_1,m_2,\dots ,m_n\}$ includes n motes.

Output:

  The collection $C_{\text{motes}}$ of some of sets from $m_1,m_2,\dots ,m_n$

  whose union is the entire required evidence E.

Project the multidimensional network evidence into

a global dimension ${\mathrm{E}}_g=\left\{e_1,e_2,\dots ,e_n\right\}$ with new cost:

   ${\text{Cost}}_{\text{nor}}=\left\{{\text{cost}}_{\text{nor}}^{e1},{\text{cost}}_{\text{nor}}^{e2},\dots ,{\text{cost}}_{\text{nor}}^{en}\right\}$ , $e\in E$

   $C_{\text{motes}}=\mathrm{\varphi }$

   ${\mathrm{M}}_{\text{now}}=\mathrm{M}$

  while each evidence e is collected by at least one motes do

  while   ${\mathrm{E}}_g\ne \mathrm{\varphi }$   do

   find a top evidence ${\mathrm{e}}_{\text{top}}\in {\mathrm{E}}_g$ and choose a motes

    $m\in M_{\text{now}}$ with the lowest cost collected $e_{\text{top}}$ .

    $C_{\text{motes}}=C_{\text{motes}}\cup m$

   for all evidence ${\mathrm{e}}_i\in {\mathrm{E}}_g$

    If   $e_i$ is collected by m then

      ${\mathrm{E}}_g={\mathrm{E}}_g-{\mathrm{e}}_i$

    end if

   end for

  end while

  end while

return the collection $C_{\text{motes}}$ as the diagnosis nodes.

For clear understanding the greedy heuristic algorithm for MDNS problem, we give a theorem to analyze the corresponding upper bound of algorithm. Also this theorem could guarantee the correctness of algorithm which we proposed.

Theorem 4 (upper bound of algorithm).

Suppose that an optimal solution (OPT) of MDNS problem contained m selected motes. Our greedy MDNS heuristic algorithm finds a set of motes with at most $|opt|{\log }_{e}n$ motes.

Proof.

Let the network evidence E contain j elements, and suppose that the optimal solution (OPT) has size $|\text{opt}|=m$ . The first mote picked by the greedy MDNS heuristic algorithm has size of evidence at least $n/m$ . Therefore, we still have to collect evidence E after the first mote is selected by

$$\begin{array}{cc}& n_1\le n-\frac{n}{m}=n\left(1-\frac{1}{m}\right).\end{array}$$

(3)

Now we are left with $n_1$ evidence that we have to collect. At least one of the remaining sets must contain more than m motes. After our greedy MDNS heuristic algorithm picks the motes that could collect the largest number of evidence in multidimension, we have nothing except $n_2\le n_1-n_1(m-1)$ uncollected evidence. Notice that ${\mathrm{\hspace{0.17em}\hspace{0.17em}}n}_2\le n_1(1-1/(m-1))\le n_1(1-1/m)\le n_1{(1-1/m)}^2$ . In general, we then have $n_{i+1}\le n_i(1-1/m)\le n{(1-1/m)}^{i+1}$ .

We would like to determine the number of stages after which our greedy MDNS heuristic algorithm will collect all evidence of E. Eventually, the processing would correspond to the maximum number of motes, and the greedy MDNS heuristic algorithm will collect all evidence of E in multidimension. This would correspond to the maximum number of sets which the greedy MDNS heuristic algorithm has to pick in order to collect the entire network evidence.

Suppose that it takes x stages to collect network evidence E in multidimension. We have $n_x<n{(1-1/m)}^x$ , and we need this to be less than one:

$$\begin{array}{cc}& {n\left(1-\frac{1}{m}\right)}^x<1,\\ {\left(1-\frac{1}{m}\right)}^{mx/m}<\frac{1}{n},\\ e^{-x/m}<\frac{1}{n},\\ \frac{x}{m}>{\log }_{e}n,\\ x>{m\log }_{e}n.\end{array}$$

(4)

Now suppose that the upper bound of the greedy MDNS heuristic algorithm is at most $|\text{opt}|{\log }_{e}n$ motes.

4. Evaluation

In this section, we evaluate the performance of our greedy heuristic algorithm for MDNS problem with simulation and real experiments. This section presents the evaluation results in terms of network size, evidence number, and iterations times. We simulate a network with sensor motes which are randomly deployed in $500\hspace{0.17em}\text{m}*500\hspace{0.17em}\text{m}$ square, and the required evidence is located in subsquare. The capacity of collecting evidence of each mote is achieved by the processing of original running system. We predefined this feature in this simulation, and we consider the three following tunable parameters. The simulation solution is based on the Matlab optimization toolbox.

• (i)

The number of required evidence ${\text{num}}_e=|E|$ . We vary this parameter form 5 to 40.

(ii)

The number of evidence dimension k is varying from 1 to 10.

(iii)

n denotes the number of motes in system, varying from 20 to 300.

Figure 4 plots the three curves which denote the number of diagnosis sensor with different network scales. Three curves show different network evidence (10, 20, and 30). We find that the diagnosis node could achieve more evidence along with the network increasing density. Another fact is that the number of diagnosis node does not increase in linear mode, because the variable is also impacted by network topology and physical environment.

Figure 4

Number of diagnosis sensor with different network scale.

Figure 5 shows number of network evidence with number of iterations in greedy MDNS problem. We could learn from this figure that the number of evidence is nonlinear with the number of iteration times. First, the selected diagnostic nodes could collect more network evidence than the following selected nodes based on the characteristic of our algorithm. For better understanding the multidimension, we evaluate the greedy MDNS algorithm varying different number of dimension k as shown in Figure 6. We find that number of iterations is decreasing with the number of dimension of same size evidence. This feature implies that if the network evidence is distributed in more dimensions, we could use less diagnosing nodes to collect these types of evidence.

Figure 5

Number of network evidence with number of iterations.

Figure 6

Number of network evidence with number of iterations varying different number of dimension k (total number of network evidence is equal to 20).

Secondly we conduct our greedy MDNS heuristic algorithm to CitySee diagnosing task shown in Figure 7. CitySee consisted of 1200 sensor nodes in the urban area. The network employs a two-tired structure, including mesh layer and sensor layer. The first layer consists of mesh nodes capable of long-distance and high throughput data communication up to several MB/s. At the second layer, we deployed four sensor networks, each of which consists of about 300 sensor nodes.

Figure 7

Partial deployment information of CitySee.

The subsensor network is shown in Figure 7. The yellow area denotes network evidence area which contains the required evidence for diagnosing task. The white lines denote the wireless link between the notes. The mesh node is located on the southwest of the map.

In this diagnosing task, the administrator tries to collect more than 70 network evidence in CitySee system which consists of TelosB motes with MSP430 MCU and CC2420 radio. Our object is how to select minimal number of diagnostic motes to collect this network evidence. In this task, we need five types of evidence for diagnosing problematic network based on the administrator empirical knowledge.

These types of evidence are distributed on multidimensional data space, which can be classified into 5 types of evidence including temperature, radioOnCounter, RSSI, ETX, and TaskPostCounter. We show the detailed network evidence information in Table 1. Temperature and RSSI could imply the physical environment of this area. ETX and radioOnCounter show the link layer evidence of area which could infer the transmission behaviors with probability. TaskPostCounter potential implies the condition of scheduling inner mote. Figure 8 shows the iteration time of our greedy MDNS heuristic algorithm in diagnosing task. So we are able to lean from curve that the algorithm converges to the steady-state solution after 23 iterations.

Table 1

A diagnosing task in CitySee System.

Required evidence name	Number of evidence
Temperature	10
radioOnCounter	10
RSSI	22
ETX	22
TaskPostCounter	10

Figure 8

The number of iterations times for a real diagnosing task in CitySee project.

5. Conclusion

The applications of WSNs [11, 24] are deemed as an affordable solution to provide sustainable and efficient sensing services in the real world. When an application of WSNs faces problem condition, for example, poor network performance, administrator and service engineers are required to quickly deploy a diagnosis system for exploring the root cause. For administrator and service engineers, unfortunately, it is difficult to achieve network evidence efficiently. Moreover, the required network evidence is always distributed in multidimensional data spaces. The existing approaches fail to consider this multidimensional feature of evidence in diagnosis nodes selection problem. To address the above issues, we propose a solution for the multidimensional diagnosis nodes selection problem and give the corresponding upper bound. The evaluation shows that our greedy heuristic algorithm is scalable and applicable for real WSNs.