Sage Journals: Discover world-class research

Abstract

In wired networks, monitor-based network tomography has been proved to be an effective technology for network internal state measurements. Existing wired network tomography approaches assume that the network topology is relatively static. However, the network topology of sensor networks is usually changing over time due to wireless dynamics. In this paper, we study the problem to assign a number of sensor nodes as monitors in large scale sensor networks, so that the end-to-end measurements among monitors can be used to identify hop-by-hop link metrics. We propose RoMA, a Robust Monitor Assignment, algorithm to assign monitors in large scale sensor networks with dynamically changing topology. RoMA includes two components, confidence-based robust topology generation and cost-minimized monitor assignment. We implement RoMA and evaluate its performance based on a deployed large scale sensor network. Results show that RoMA achieves high identifiability with dynamically changing topology and is able to assign monitors with minimum cost.

1. Introduction

Network tomography techniques [1] use end-to-end measurements to calculate hop-by-hop link metrics, such as delay and packet reception ratio. Recent advances in network tomography techniques [2–4] show that cycle-free measurement paths among monitors can be used to form a linear system on the internal unknown link metrics. Then these unknown link metrics can be calculated by solving the linear system. In order to successfully solve the linear system, sufficient linearly independent measurement paths should be able to be conducted among the monitors, requiring the monitors assignment to comply with certain conditions.

Existing works assume relatively static network topologies and uniform cost of assigning monitors, since they all focus on wired communication networks. Then these works focus on calculating the minimum monitor assignment to enable sufficient linearly independent measurement paths. In wireless sensor networks (WSNs), however, the network topologies keep changing over time [5, 6], due to the wireless dynamics. Further, assigning a monitoring node to different nodes in a deployed network usually requires different cost, depending on the environmental conditions, the location of each node, and so forth. Therefore, existing techniques cannot be applied into WSNs directly.

In this paper, we focus on calculating a minimum cost monitor assignment in a WSN, given the dynamic changing network topology. In particular, we propose RoMA, a Robust Monitor Assignment, algorithm to assign monitors with minimum cost in large scale sensor networks with dynamically changing topology. RoMA includes two components, confidence-based robust topology generation and cost-minimized monitor assignment. The confidence-based robust topology generation merges multiple historical topologies based on a confidence value. It generates a robust topology, which captures the dynamic changing topology over time. Based on this robust topology, the cost-minimized monitor assignment component of RoMA assigns monitors with minimum overall cost.

We implement RoMA and evaluate its performance through extensive simulations based on a deployed large scale sensor network. Compared with MMP [2], RoMA assigns fewer monitors with high link metric identifiability and achieves a much smaller overall cost.

The rest of the paper is organized as follows. Section 2 describes the related work of RoMA. Section 3 formulates the problem. Section 4 describes the design of RoMA. Section 5 presents evaluation results. Finally, Section 6 concludes the paper.

2. Related Work

Based on the model of link metrics, existing work on measuring the network internal state can be broadly classified as hop-by-hop and end-to-end approaches. Hop-by-hop approaches use diagnostic tools such as traceroute, pathchar [7], and Network Characterization Service (NCS) [8] to measure hop-by-hop link metrics directly. By sending multiple probes with different time-to-live fields, traceroute can measure the delay of each hop on the probed path. Pathchar uses a similar approach to measure hop-by-hop delays, capacities, and loss rates. NCS also reports available capacities of each hop.

End-to-end approaches use end-to-end metrics to calculate internal link metrics. They assume the network is controllable; otherwise, the minimum monitor assignment problem has been proved to be NP-hard [9–11]. The basic idea is to build a linear system from the path measurements and use linear algebraic techniques to calculate the unknown link metrics [12, 13]. When cyclic measurement paths are allowed, [14] gives the necessary and sufficient conditions on the network topology. Since routing along cycles is typically prohibited in real networks, [2] gives the necessary and sufficient conditions on the network topology when only cycle-free measurement paths are used.

However, in WSNs, the network topologies keep changing over time and existing techniques cannot be applied into WSNs directly. In this paper, we focus on calculating a minimum cost monitor assignment in a WSN, given the dynamic changing network topology, to calculate all link metrics. We propose RoMA, a Robust Monitor Assignment, algorithm to assign monitors with minimum cost in large scale sensor networks with dynamically changing topology.

3. Problem Formulation

We model the network topology as an undirected graph $G = (V, L)$ , where V is the set of nodes and L is the set of links. Each link $l_{i} \in L$ is associated with an unknown metric $w_{l_{i}}$ . We assume that link metrics are symmetric in both directions. We also assume that the link metric $w_{l_{i}}$ does not change during the measurement period. Taking delay as an example, [15] shows that the delays of the same link within a relatively short period of time are similar. Monitors are certain nodes in V which can initiate/collect cycle-free measurements. They can control the routing of measurement packets.

Let $w = {(w_{l_{1}}, \dots, w_{l_{n}})}^{T}$ denote the column vector of all link metrics and $c = {(c_{p_{1}}, \dots, c_{p_{r}})}^{T}$ the column vector of all available path measurements, where n and r are the number of links and measurement paths, respectively, and $c_{p_{i}}$ is the sum of metrics along measurement path $p_{i}$ . Then we can get a linear system as follows:

\begin{matrix} R w = c, \end{matrix}

(1)

where

R = (R_{i j})

is a

r \times n

matrix, with each

R_{i j} \in {0,1}

means whether link j is on path i. A link is identifiable if we can solve its metric from the above linear system. If and only if

r a n k (R) = n

, the network G is completely identifiable. If

r a n k (R) < n

, it may still be possible to identify some of the link metrics.

We want to assign a number of nodes in the network as monitors to initial/collect measurement packets. In the current problem formulation, we assume that all link metrics are unknown before the network tomography. After assigning monitors, we can use the algorithm STPC [3] to find a set of linearly independent paths between monitors efficiently. Each of these paths represents a row of R and the sum of metrics along the path is an element of c. So we can solve the unknown link metrics by solving for w given R and c. Since assigning a node as a monitor usually needs nonnegligible operational cost (e.g., hardware/software, human efforts), we focus on assigning monitors with minimum cost to identify most of the links.

4. Design

The design of RoMA includes two components: confidence-based robust topology generation and cost-minimized monitor assignment. The confidence-based robust topology generation algorithm uses instant topologies to generate a robust topology. The cost-minimized monitor assignment algorithm provides a subset of nodes in the robust graph as monitors with the minimized cost. The set of monitors can identify all links in the robust graph and the majority of links in future topologies.

4.1. Confidence-Based Robust Topology Generation

Due to wireless dynamics and interference, a node usually transmits its packets to different receivers at different time. Therefore, RoMA first generates a robust topology of a WSN for monitor assignment. The input of RoMA is a number of packets received by sink. In each packet k, there are three data fields related to RoMA, which are the origin $o (k)$ , the parent $p (k)$ , and global packet generation time $t (k)$ . Origin $o (k)$ and parent $p (k)$ are the first two hops of k's routing path. The global packet generation time can be obtained by packet timestamping technique without global time synchronization [16]. By using each packet's origin and parent, we can construct the topology of the WSN. Let $G_{i}$ denote an instant topology constructed by a set of packets sent by nodes to their parents in a period t. With a set of packets having different sending time, a number of instant topologies can be constructed. Then we use a set of instant topologies ${G_{1}, \dots, G_{i}, \dots}$ to generate a robust topology. As described in Algorithm 1, the inputs are a set of packets $P = {P_{1}, \dots, P_{k}}$ received by sink, period t, and confidence $C_{m i n}$ . These packets have different sending time so that we can get a set of instant topologies $G = {G_{t_{1}}, \dots, G_{t_{n}}}$ (line 1). Let L be a set, which contains all instant topologies’ links in $G$ (line 2). For each link l in set L, we compute link l's confidence $C_{l}$ and compare it with the minimum confidence $C_{m i n}$ . $| G |$ denote the number of instant topologies in $G$ and $n_{l}$ the number of instant topologies in $G$ which contain link l. If $C_{l}$ is larger than $C_{m i n}$ , we select l as a link in the robust topology $G_{r}$ (lines 4–7).

Algorithm 1: Confidence-based robust topology generation.

Input: a set of packets $P_{1}$ , …, $P_{k}$ , confidence $C_{\min}$ , period t

Output: A robust topology $G_{r}$

(1) Construct a set of instant topologies $G = {G_{t_{1}}, \dots, G_{t_{n}}}$ according to t

(2) L = $L (G_{t_{1}}) \cup L (G_{t_{2}}) \cup \dots \cup L (G_{t_{n}})$

(3) set $G_{r}$ = ∅

(4) for each link l in L do

(5) $C_{l}$ = $n_{l}$ / $|G|$

(6) if $C_{l} \geq C_{\min}$ and l is not in $G_{r}$ then

(7) select l as an link in $G_{r}$

return $G_{r}$

4.2. Cost-Minimized Monitor Assignment

Then RoMA assigns monitors with minimum cost in the robust topology $G_{r}$ . Before describing the algorithm, we first introduce several graph theory concepts. (i)

A graph is connected if there is a path from any point to any other point in the graph.

(ii)

A k-connected component of G is a maximal subgraph of G that is either (i) k-vertex-connected or (ii) a complete graph with up to k vertices. The case of $k = 2$ is also called a biconnected component and $k = 3$ a triconnected component.

(iii)

A cut-vertex is a vertex whose removal will disconnect the graph.

(iv)

A 2-vertex cut is a set of two vertices ${v 1, v 2}$ such that removing $v 1$ or $v 2$ alone does not disconnect G, but removing both disconnects G. Each vertex of ${v 1, v 2}$ is a 2-cut-v.

(v)

Nodes that are cut-vertices or part of 2-vertex cuts are called separation vertices.

Figure 1 shows an example which illustrates the above concepts. In this example, the whole graph is a connected graph. It contains two biconnected components, which are separated by a cut-vertex. There is also a triconnected component shown in the figure, which is connected to the graph by a 2-vertex cut.

Figure 1

An example that illustrates several graph theory concepts.

If all vertices are assigned as monitors, it is obvious that all links are identifiable. However, assigning a node as a monitor usually needs nonnegligible operational cost (e.g., hardware/software, human efforts); RoMA tries to assign monitors with minimum cost to identify most of the link metrics. A recent work MMP [2] assigns the minimum number of monitors to identify all links in a connected graph. It is actually a special case when all vertices have the same cost to be assigned as monitors. Different with MMP, RoMA calculates a subset of nodes in the robust graph as monitors with the minimum cost.

Ma et al. [2] show that there are 4 rules which must be satisfied to identify a topology with the minimum number of monitors. (i)

A node whose degree is one must be a monitor.

(ii)

A node on a tandem of links (degree is two) must be a monitor.

(iii)

For a subgraph with two cut-vertices or a 2-vertex cut, at least one node other than those cuts must be a monitor.

(iv)

Similarly, for a subgraph with one cut-vertex, at least two nodes other than the cut-vertex must be monitors.

As shown in Algorithm 2, the cost-minimized monitor assignment method follows rules (i) and (ii) to select all vertices with degree less than three as monitors (line 1). Then it partitions the graph into a number of biconnected components. For each biconnected component, it further partitions the biconnected component into a number of triconnected components. Note that there are efficient algorithms to accomplish the above biconnected components and triconnected components partitioning [17, 18].

Algorithm 2: Cost-minimized monitor assignment.

Input: Connected graph G and the set of nodes’ cost

Output: A subset of nodes in G as monitors

(1) choose all the nodes with degree less than 3 as monitors

(2) partition G into biconnected components $B_{1}$ , $B_{2}$ , …

(3) for each $B_{i}$ with $|B_{i}|$ ≥ 3 do

(4) partition $B_{i}$ into triconnected components $T_{1}$ , $T_{2}$ , …

(5) for each $T_{j}$ of $B_{i}$ with $|T_{j}|$ ≥ 3 do

(6) if 0 < $|S_{T_{j}}|$ < 3 and $|S_{T_{j}} \cup M_{T_{j}}|$ < 3 then

(7) Choose 3 − $|S_{T_{j}} \cup M_{T_{j}}|$ nodes in $T_{j}$ and not in $S_{T_{j}} \cup M_{T_{j}}$ with the minimum cost as monitors

(8) if 0 < $|C_{B_{i}}|$ < 3 and $|C_{B_{i}} \cup M_{B_{i}}|$ < 3 then

(9) Choose 3 − $|C_{B_{i}} \cup M_{B_{i}}|$ nodes in $B_{i}$ and not in $C_{B_{i}} \cup M_{B_{i}}$ with the minimum cost as monitors

(10) if the total number of monitors k < 3 then

(11) Choose 3 − k non-monitors nodes with the minimum cost as monitors

For each triconnected and then biconnected component that contains three or more nodes, the cost-minimized monitor assignment makes sure that (i) each triconnected component has at least three nodes that are either separation vertices or monitors with the minimum cost in the component (lines 5–7) and (ii) each biconnected component has at least three or more nodes that are either cut-vertices or monitors with the minimum cost in the component (lines 8-9). Finally, Algorithm 2 selects additional monitors with the minimum cost as needed to ensure that the total number of monitors is at least three (lines 10-11). As described in Algorithm 2, for a component D, let $S_{D}$ denote the number of separation vertices, $C_{D}$ the number of cut-vertices, and $M_{D}$ the number of (already selected) monitors in D.

The cost-minimized monitor assignment component's output is a set of monitors which can be used in algorithm STPC [3] to gain R. As mentioned above, the topology is completely identifiable if and only if the rank of R is n. The matrix R represents a set of measurement paths. Therefore, the rank of R is not directly related to the topology generation process but is directly related to the monitor assignment and path selection process. However, the network topology does have impact on the monitor assignment and the path selection. For example, if the original graph is a triconnected graph, we only need to assign three monitors to identify all links.

5. Evaluation

In this section, we evaluate the performance of RoMA through a set of simulations based on a deployed large scale sensor network, the CitySee project.

5.1. Evaluation Setup

CitySee is deployed in an urban area to collect multidimensional sensing data such as carbon emission, temperature, and humidity. All nodes in CitySee are organized as four subnets. Each subnet has one sink and these four sink nodes transmit data packets to a base station through 802.11 wireless links. And each node in the network transmits 4 data packets back to the sink node every 10 minutes. We use the trace from one subnet to evaluate the performance of RoMA. The main performance metrics are the number of monitors and the identified ratio of links.

We construct a set of instant topologies using period t and merge N topologies into a robust one with different confidence $C_{m i n}$ . Then we assign monitors with minimum cost in the robust topology and use these monitors to identify a future topology.

In the simulations, we study the impacts of different parameters to the performance of RoMA. There are several parameters such as confidence $C_{m i n}$ , period t, and the number of merged topologies N. When changing one parameter, we keep the other parameters as constant.

5.2. Simulation

First we study the impact of period t. While $N = 1$ and $C_{m i n} = 1$ , we set the period t hour, semidaily, and daily, respectively. From Table 1 we can see that, with different temporal resolutions (hour, semidaily, and daily), there is a very drastic change in the number of monitors. That is because, with a high temporal resolution, the topology is sparse and needs more monitors to identify it. As shown in Table 1, when t = hour, we get 168 monitors with the $96.6 %$ of links which can be identified. However, if we set t = daily, with only 46 monitors, the percentage of links which can be identified reaches up to $89.6 %$ . In order to get a set of monitors with a reasonable amount, we choose period t = daily.

Table 1

Impact of temporal resolutions.

Period	t = daily	t = semidaily	t = hour

Identifiability	0.896	0.951	0.966

Monitors	46	117	168

Then we study the impact of the number of merged topologies N. Setting t = daily, we merge different numbers of topologies into a robust one with $C_{m i n} = 0.6$ and $0.8$ , respectively. N has an impact on the structure of the robust topology. But the impact is not linear. That is to say, a larger N does not mean a better performance. On the other hand, to identify more links, we need more monitors, which results in a higher cost. Considering the cost, it is unreasonable to assign a lot of monitors. Table 3 shows the impact of N. While $N = 5$ , the number of monitors and the identifiability are all acceptable. And there is not a big change in the identifiability when N increase. To achieve a balance between the number of monitors and the percentage of identified links, we set N five while t = daily.

The confidence has a positive influence on the number of monitors and links which can be identified. We merge $5$ instant topologies into a robust one with $C_{m i n}$ = 0.4, 0.6, 0.8, 1, respectively, and show the result in Table 2. Then we compare the results with MMP in Figure 2. It is easy to see that high confidence leads to a sparse topology which needs more monitors to be identified. As shown in Figure 2, $C_{m i n} = 0.8$ achieves a better performance than others with a high identifiability and a reasonable number of monitors.

Table 2

Impact of different confidence.

Confidence	0.4	0.6	0.8	1

Identifiability	0.871	0.896	0.919	0.944

Monitors	15	29	58	98

Table 3

Impact of the number of merged topologies.

N	3		5		7		10

Confidence	0.6	0.8	0.6	0.8	0.6	0.8	0.6	0.8

Identifiability	0.905	0.940	0.896	0.919	0.909	0.933	0.895	0.926

Monitors	43	92	29	58	38	71	28	57

Figure 2

The Impact of confidence.

From the above, we set $N = 5$ , $C_{m i n} = 0.8$ , and t = daily and compare the performances of RoMA and MMP. Assuming that each node has a steady cost, we use two sets of monitors which are got from RoMA and MMP, respectively, to identify a future topology and show the results in Figure 3. The points marked as blue are monitors with the different costs denoted by points’ size. These red edges are the links which cannot be identified using those monitors. Figure 3(a) shows RoMA's results and Figure 3(b) MMP's results. Different with MMP, RoMA calculates a subset of nodes in the robust graph as monitors with the minimum cost. Further, RoMA merges multiple topologies to obtain a robust topology, reducing the monitors assigned. Therefore, as shown in Figure 3, the number of monitors got from RoMA is less than MMP's, and the cost of the monitors is not larger than MMP's.

Figure 3

Compare with MMP.

Also, we evaluate the performance of RoMA using some other real network topologies. We use the Internet Service Provider (ISP) topologies from the Rocketfuel [19] project, which represent physical connections between backbone/gateway routers of several major ISPs around the globe. We obtain the cost by randomly generated numbers between 1 and 1000. The network topologies are relatively static so that merging topologies into a robust one is not necessary. We use RoMA to assign monitors with parameters t = daily, $N = 1$ , and $C_{m i n} = 1$ and then use these monitors to identify other topologies. Results are shown in Figure 4. The x-axis is the topologies got from different days, and the y-axis is the percentage of identified links. The identifiability of each topology shown in the figure is higher than $96 %$ , which indicates that RoMA also works well with real network topologies.

Figure 4

The performance of RoMA using ISP topologies.

6. Conclusion

In this paper, we propose RoMA, a Robust Monitor Assignment, algorithm to assign monitors in large scale sensor networks with dynamically changing topology. RoMA merges instant topologies into a robust one and uses the cost-minimized monitor assignment algorithm to get a set of nodes as monitors with the minimum cost. We then analyze the performance of RoMA and the analysis results show that RoMA achieves high percentage of identifiability using monitors with minimum overall cost.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by the National Science Foundation of China under Grant nos. 61472360 and 61202402, the Fundamental Research Funds for the Central Universities, and the Research Fund for the Doctoral Program of Higher Education of China (20120101120179).

References

Lawrence

Michailidis

Nair

V. N.

Network tomography: a review and recent developments

Frontiers in Statistics 2006

World Scientific

345 366

10.1142/9781860948886_0016

MR2326009

Leung

K. K.

Swami

Towsley

Identifiability of link metrics based on end-to-end path measurements

Proceedings of the Conference on Internet Measurement Conference (IMC ′13)

2013

391 404

10.1145/2504730.2504738

Leung

K. K.

Towsley

Swami

Efficient identification of additive link metrics via network tomography

Proceedings of the IEEE 33rd International Conference on Distributed Computing Systems (ICDCS ′13)

July 2013

581 590

10.1109/icdcs.2013.24

2-s2.0-84893266203

Leung

K. K.

Swami

Towsley

Link identifiability in communication networks with two monitors

Proceedings of the IEEE Global Communications Conference (GLOBECOM ′13)

December 2013

Atlanta, Ga, USA

1513 1518

10.1109/glocom.2013.6831288

Gao

Dong

Chen

Guan

Zhang

Liu

Pathfinder: robust path reconstruction in large scale sensor networks with lossy links

Proceedings of the 21st IEEE International Conference on Network Protocols (ICNP ′13)

October 2013

Göttingen, Germany

IEEE

1 10

10.1109/ICNP.2013.6733600

Dong

Liu

Zhu

Chen

Measurement and analysis on the packetdelivery performance in a large scale sensor network

IEEE/ACM Transactions on Networking 2013 22 6 1952 1963

2-s2.0-84887392179

10.1109/tnet.2013.2288646

Downey

A. B.

Using pathchar to estimate internet link characteristics

Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ′99)

1999

241 250

Jin

Yang

Crowley

B. R.

Agarwal

D. A.

Network characterization service (NCS)

Proceedings of the 10th IEEE Interantionsl Symposium on High Performance Distributed Computing

August 2001

289 302

2-s2.0-0034869576

Bejerano

Rastogi

Robust monitoring of link delays and faults in IP networks

IEEE/ACM Transactions on Networking 2006 14 5 1092 1103

10.1109/tnet.2006.882907

2-s2.0-33750338078

10.

Kumar

Kaur

Practical beacon placement for link monitoring using network tomography

IEEE Journal on Selected Areas in Communications 2006 24 12 2196 2209

2-s2.0-33845637281

10.1109/JSAC.2006.884017

11.

Horton

J. D.

López-Ortiz

On the number of distributed measurement points for network tomography

Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement (IMC ′03)

2003

204 209

10.1145/948205.948231

12.

Chen

Bindel

Song

Katz

R. H.

An algebraic approach to practical and scalable overlay network monitoring

Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′04)

2004

55 66

10.1145/1030194.1015475

2-s2.0-21844443150

13.

Gurewitz

Sidi

Estimating one-way delays from cyclic-path delay measurements

Proceedings of the IEEE INFOCOM

2001

1038 1044

14.

Gopalan

Ramasubramanian

On identifying additive link metrics using linearly independent cycles and paths

IEEE/ACM Transactions on Networking 2012 20 3 906 916

10.1109/TNET.2011.2174648

2-s2.0-84862518612

15.

Gao

Dong

Chen

Xia

Liu

Domo: passive per-packet delay tomography in wireless ad-hoc networks

Proceedings of the 34th IEEE International Conference on Distributed Computing Systems (ICDCS ′14)

June-July 2014

Madrid, Spain

419 428

10.1109/icdcs.2014.50

16.

Dong

Zhang

Wang

Gao

Chen

Accurate and robust time reconstruction for deployed sensor networks

Proceedings of the ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ′14)

2014

571 572

10.1145/2591971.2592023

17.

Tarjan

R. E.

Depth-first search and linear graph algorithms

SIAM Journal on Computing 1972 1 2 146 160

MR0304178

10.1137/0201010

18.

Hopcroft

J. E.

Tarjan

R. E.

Dividing a graph into triconnected components

SIAM Journal on Computing 1973 2 3 135 158

10.1137/0202012

MR0327391

19.

Spring

N. T.

Mahajan

Wetherall

Anderson

T. E.

Measuring ISP topologies with rocketfuel

IEEE/ACM Transactions on Networking 2004 12 1 2 16

10.1109/tnet.2003.822655

2-s2.0-1642408605

Robust Monitor Assignment with Minimum Cost for Sensor Network Tomography

Abstract

1. Introduction

2. Related Work

3. Problem Formulation

4. Design

4.1. Confidence-Based Robust Topology Generation

Algorithm 1: Confidence-based robust topology generation.

4.2. Cost-Minimized Monitor Assignment

Algorithm 2: Cost-minimized monitor assignment.

5. Evaluation

5.1. Evaluation Setup

5.2. Simulation

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References