# Robust Monitor Assignment with Minimum Cost for Sensor Network Tomography

Authors: Xiaojin Liu; Yi Gao; Wenbin Wu; Wei Dong; Jiajun Bu
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 1. Introduction

Network tomography techniques [1] useend-to-end measurements to calculatehop-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 amongmonitors 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. Section2 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 ashop-by-hop andend-to-end approaches.Hop-by-hop approaches use diagnostic tools such astraceroute,pathchar [7], andNetwork Characterization Service(NCS) [8] to measurehop-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 measurehop-by-hop delays, capacities, and loss rates. NCS also reports available capacities of each hop.End-to-end approaches useend-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 graphG
=
(
V
,
L
), where V is the set of nodes and L is the set of links. Each link l
i
∈
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.Letw
=
(
w
l
1
,
…
,
w
l
n
)
T denote the column vector of all link metrics and c
=
(
c
p
1
,
…
,
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: (1)
R
w
=
c
,where R
=
(
R
i
j
) is a r
×
n matrix, with each R
i
j
∈
{
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 packetk, 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
,
…
,
G
i
,
…
} to generate a robust topology. As described in Algorithm 1, the inputs are a set of packets P
=
{
P
1
,
…
,
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
,
…
,
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
,
…
,
G
t
n
} according to t
(2) L = L
(
G
t
1
)
∪
L
(
G
t
2
)
∪
⋯
∪
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
≥
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 topologyG
r. Before describing the algorithm, we first introduce several graph theory concepts.(i)
A graph isconnected if there is a path from any point to any other point in the graph.
(ii)
Ak-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)
Acut-vertex is a vertex whose removal will disconnect the graph.
(iv)
A2-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 arecut-vertices or part of 2-vertex cuts are called separation vertices.Figure1 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 Algorithm2, 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
∪
M
T
j < 3 then
(7)    Choose 3 − S
T
j
∪
M
T
j nodes in T
j and not in S
T
j
∪
M
T
j with the minimum cost as monitors
(8)  if 0 < C
B
i < 3 and C
B
i
∪
M
B
i < 3 then
(9)   Choose 3 − C
B
i
∪
M
B
i nodes in B
i and not in C
B
i
∪
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 monitorsFor 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, Algorithm2 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.


## 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 packetk, 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
,
…
,
G
i
,
…
} to generate a robust topology. As described in Algorithm 1, the inputs are a set of packets P
=
{
P
1
,
…
,
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
,
…
,
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
,
…
,
G
t
n
} according to t
(2) L = L
(
G
t
1
)
∪
L
(
G
t
2
)
∪
⋯
∪
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
≥
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 topologyG
r. Before describing the algorithm, we first introduce several graph theory concepts.(i)
A graph isconnected if there is a path from any point to any other point in the graph.
(ii)
Ak-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)
Acut-vertex is a vertex whose removal will disconnect the graph.
(iv)
A2-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 arecut-vertices or part of 2-vertex cuts are called separation vertices.Figure1 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 Algorithm2, 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
∪
M
T
j < 3 then
(7)    Choose 3 − S
T
j
∪
M
T
j nodes in T
j and not in S
T
j
∪
M
T
j with the minimum cost as monitors
(8)  if 0 < C
B
i < 3 and C
B
i
∪
M
B
i < 3 then
(9)   Choose 3 − C
B
i
∪
M
B
i nodes in B
i and not in C
B
i
∪
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 monitorsFor 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, Algorithm2 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 periodt 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 confidenceC
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 periodt. 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
168Then we study the impact of the number of merged topologiesN. 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 merge5 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
98Table 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
57Figure 2
The Impact of confidence.From the above, we setN
=
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.
(a)
RoMA
(b)
MMPAlso, we evaluate the performance of RoMA using some other real network topologies. We use theInternet 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.


## 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 periodt 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 confidenceC
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 periodt. 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
168Then we study the impact of the number of merged topologiesN. 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 merge5 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
98Table 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
57Figure 2
The Impact of confidence.From the above, we setN
=
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.
(a)
RoMA
(b)
MMPAlso, we evaluate the performance of RoMA using some other real network topologies. We use theInternet 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.



---

*Source: 512463-2015-08-13.xml*