A Multi-Channel Bulk Data Collection for
Structural Health Monitoring using
Wireless Sensor Networks
Takuto Kuroiwa∗ , Makoto Suzuki∗ , Yasutaka Yamashita∗ ,Shunsuke Saruwatari† , Tomonori Nagayama‡ and Hiroyuki Morikawa∗∗ Research Center for Advanced Science and Technology, The University of Tokyo{kuroiwa, makoto, yasu, mori}@mlab.t.u-tokyo.ac.jp† Faculty of Informatics/Graduate School of Informatics, Shizuoka University

saru@inf.shizuoka.ac.jp‡ Department of Civil Engineering, The University of Tokyo

nagayama@bridge.t.u-tokyo.ac.jp

Abstract—Data-intensive wireless sensor network applications,such as structural health monitoring and earthquake monitoring,
require high throughput bulk data collection. Based on the factthat each node stores the same amount of sensor data, we
propose a Maximum-Subtree-First Collection Protocol (MSFCP),
which adopts Maximum-Subtree-First scheduling on top of multichannel block transfer to maximize overall throughput. We
present the theoretical analysis that MSFCP can achieve optimalthroughput in the ideal propagation environment, and we achieve
overall throughput of 135 kbps on the IRIS Mote platform.
Index Terms—Wireless sensor networks, bulk transfer, multichannel, scheduling

I. I NTRODUCTION
Wireless sensor networks are increasingly used in dataintensive applications such as structural health monitoring[1],[2], earthquake monitoring[3], and volcano monitoring[4].
These applications require bulk transfer of large amounts ofsensed data to a common sink, typically over a tree-based
routing topology. For this class of applications, it is critical tomaximize throughput.
The nature of wireless communications brings several challenges for efficient and reliable collection in multi-hop settings; these include inter-path and intra-path interference [5].
Inter-path interference occurs between multiple flows, while
intra-path interference occurs between multiple hops of thesame flow, where a flow is defined as a set of nodes between
the sink and a source that is actively transmitting packets tothe sink.
Existing bulk transfer protocols such as Flush [6] andPIP [7] consider only one active flow at a time to eliminate
the issue of inter-path interference. A typical sensor node isequipped with a single half-duplex transceiver, which can either transmit or receive only one packet at any time. Therefore,
in Flush and PIP, the sink is idle over half the time since
the child of the sink can be continuously active by eithertransmitting or receiving, whereas the sink only receives, as
shown in Fig. 1.

978-1-4673-4728-0/12/$31.00 ©2012 IEEE

We propose here the Maximum-Subtree First Collection
Protocol (MSFCP), which collects data from multiple flows
to maximize the overall throughput. MSFCP utilizes multiple
channels to eliminate intra-path interference. This protocol
also uses CSMA-based block transfer to mitigate overhead
including channel switching and ACKs and adopts MaximumSubtree-First (MSF) scheduling to reduce inter-path interference and utilize the sink capability.
We present a theoretical analysis in which MSF schedulingachieves the optimal throughput under an ideal communication environment, and we describe our evaluation of overallthroughput on various routing trees using the IRIS Mote
platform. In our laboratory experiments, achieved throughput
is up to 135 kbps.
The rest of this paper is organized as follows. In section II,
we discuss prior work on data collection. In section III, we
describe the design of MSFCP. Section IV presents an analysis
of collection time under an ideal communication environment.
Section V discusses the experimental evaluation on the IRIS
Mote platform. Finally, in section VI, we conclude the paperand discuss our future work.
II. R ELATED W ORK
Traffic patterns of data collection in wireless sensor networks are mainly classified into two types, as indicated in
TABLE I: low-power data collection and high-throughput bulk
data collection. Applications such as environmental monitoring, habitat monitoring, and data center monitoring periodically collect data at a low data-rate over a long period.
To save energy and improve the network lifetime, sensor
data are typically aggregated to eliminate redundancy and tominimize the number of transmissions [8]. In contrast, ourtarget applications such as structural health monitoring andvolcano monitoring attempt to acquire a large amount of data
at a high data-rate, typically over 100 Hz. For signal analysis
or other purposes, these applications collect complete datafrom nodes without aggregation. Because it is not feasible to295

APCC 2012Collection from only one flow at Collection from multiple flows at
a timethe same time
Fig. 1.

Fig. 2.

Block transfer

Data collection from one flow/multiple flows

TABLE IC OLLECTION P ROTOCOLS IN W IRELESS S ENSOR N ETWORKS
Traffic pattern
Low-power data collection
High-throughput bulk datacollection

Applications
Environmental monitoring
Wildlife monitoring
Data center monitoring
Structural health monitoring
Earthquake monitoring
Volcano monitoring

Protocols
CTP [9]
BCP [10]
Fig. 3.

Fetch [4]Flush [6]PIP [7]
SSMH [2]collect such a huge amount of data in real time, nodes store
sensor data in flash memory while sensing and then deliver
the data to a common sink.
Several protocols exist for low-power data collection, forexample, Collection Tree Protocol (CTP) [9] and Backpressure Collection Protocol (BCP) [10]. CTP is widely used inwireless sensor networks, and is a routing approach wherea minimum cost tree with respect to Expected Transmission
Count (ETX) [11] is dynamically constructed based on a linkquality estimation. BCP is an integrated routing and schedulingapproach based on backlogged queue information.
These periodical data collection protocols are designed forlong term collection and mainly focus on handling topological changes to maintain appropriate routes. These protocols
were developed for relatively low traffic rates, and achievablethroughput is limited to a little more than 10 kbps[12].
Several other protocols exist for high-throughput bulk datacollection, including Fetch [4], Flush [6], and PIP [7]. Fetch
was the first bulk transfer protocol in wireless sensor networks;
it achieves a throughput of only 1 kbps because of intra-pathand inter-path interference. Flush [6] and PIP [7] mitigate theseinterferences. Flush reduces intra-path interference by the endto-end rate control and achieves a throughput of about 10 kbps.
PIP uses multiple channels statically assigned by hop count to
reduce intra-path interference and achieves a throughput of
about 60 kbps.
Flush and PIP collect data sequentially from nodes, i.e.,
only one flow at a time, to eliminate inter-path interference.
These sequentially collecting protocols achieve only half the
maximum throughput because the sink becomes idle when its
active child node is receiving.
In our previous study, we proposed a single-sink multi-hop
communication protocol called SSMH, which employs linkby-link block data transfer using multiple RF channels forcollecting large amounts of data [2]. SSMH adopts a sender-

Channel allocation and transmission scheduling

initiated greedy scheduling strategy and does not ensure maximum achievable throughput. Unlike SSMH, MSFCP adopts
a receiver-initiated scheduling strategy to achieve close to
the optimal throughput for an arbitrary topology. Note thatevery node stores the same amount of data in our target
applications, and MSFCP takes advantage of this applicationspecific characteristic.
III. P ROTOCOL D ESIGN
We present a design of Maximum-Subtree-First Collection
Protocol (MSFCP) here. MSFCP uses multi-channel blocktransfer and adopts Maximum-Subtree-First (MSF) schedulingto reduce interference and enhance overall throughput.
A. Channel Assignment
IEEE standard 802.15.4 specifies 16 different nonoverlapping channels in the 2.4-GHz ISM band. If we utilize
available multiple channels effectively, we can exploit paralleltransmission to enhance throughput. For high throughput, it isessential to assign channels to links to minimize interference.
There are two ways to assign multiple channels: dynamic
channel assignment and static channel assignment. Although
dynamic channel assignment schemes can reduce interference
to some degree, frequent negotiations result in large overhead.
In contrast, static channel assignment schemes work with lessoverhead, but they are not suitable for rapidly changeable
propagation environment [13].
In practical deployment, interference occurs between nodes
within a few hops [6], [7], and hence, we assign a communication channel statically based on the hop count toeliminate intra-path interference. This hop count based channel
assignment enables not only packet pipelining as in PIP, butalso reduces inter-path interference to some extent because it
occurs within nodes at the same hop count. Thus, to avoid
inter-path interference, multiple nodes at the same hop countshould not send data at the same time.

296

B. Block Transfer
We use a block transfer where a sender transfers a blockof multiple packets. This block transfer technique mitigates
overhead such as channel switching and control packets including ACKs. Although transferring a block requires morememory than transmitting a packet, it reduces the uncertain
time delay, and the transmission delay over each link becomesalmost equal.
The sequence of the block transfer is shown in Fig. 2. (1)The
receiver initiates the block transfer by sending SYN packets
to the sender repeatedly until receiving a data packet from thesender. (2) After receiving a SYN packet, the sender starts
to send multiple data packets (a block) without performing
clear channel assessment (CCA) or random backoff. Thismechanism shortens the uncertain transmission delay. (3) After
receiving the last packet in a block, if there are any missing
packets, the receiver transmits a Selective Negative ACK(SNACK) that indicates which packet to retransmit. When thelast packet in a block is lost, the receiver uses a timer tosend a SNACK packet. The sender that receives a SNACK
packet transmits packets from the block that are missing at
the receiver. If the receiver has received all packets correctly,
it transmits a FIN packet to complete the block transfer.
C. Maximum-Subtree-First Scheduling
MSFCP adopts MSF scheduling, which is unsynchronized
distributed scheduling based on its own transmission buffer
information.
Each node stores the same amount of data in our target
application. Because of this, and also due to the characteristicsof block transfer, we can reduce interference and enhance theoverall throughput by using a simple strategy.
We describe in the following the MSF scheduling algorithm,
which is run locally by each node. The key idea is to scheduletransmission in parallel along multiple branches of the tree,
and to keep the sink as busy receiving as possible. We assume
that all the nodes are aware of the number of nodes in each
subtree. This can be easily obtained by gathering the routing
information. The subtree of a node is defined as a tree thathas the child of the node as its root, as shown in Fig. 4.
1) All source nodes wait for their parent’s send request if
their buffer is full.
2) All nodes choose the subtree with the largest number of
total remaining blocks, i.e., maximum subtree, and they
request the subtree root to send data if their buffer is
empty.
The sink always follows rule 2 (the sink’s buffer is treatedas always empty). The sink chooses subtrees whose roots havea full buffer, that is, subtrees other than the subtree whose root
previously sent a block to the sink. This strategy can keep thesink as busy as possible and enhance the overall throughput.
In addition, this MSF scheduling ideally realizes one flowat each hop at a time. If only node N1 is transmitting at hoph, only N1 is receiving at the next hop h + 1 after completingthe transmission.

Fig. 4.

Fig. 5.

Subtrees

Slotted behavior of nodes with duration Tlink .

IV. M ATHEMATICAL A NALYSIS OF C OLLECTION T IME
A. Lower Bound on Collection TimeIn this section, we consider a lower bound on the collection
time for a given topology. For simplicity, overhead including
channel switching is ignored, all packets can be received,
and topology is fixed during the collection. We assume thatevery node has a similar amount of data, and we denote thetransmission time of the block transfer for all links as Tlink .
This assumption leads to a slotted transmission behavior ofnodes, as depicted in Fig. 5. We define a slot as the durationof Tlink for transmitting a block of data.
Because of the half-duplex transceivers, when the root s0,jof S0,j is fully busy in either receiving or transmitting, s0,jreceives nj − 1 packets from the children and transmits nj
packets to the sink. Hence, the minimum time of collection
from a subtree TLB,j is described as follows:
TLB,j = (2nj − 1)Tlink .

(1)

This leads to the following theorem.
Theorem 1 (Lower bound of collection time) The
bound of overall collection time TLB is described by
TLB = max(N, 2nmax − 1) · Tlink ,

lower
(2)

where N is the number of sources in the network and nmax
is the maximum number of nodes in any subtree of the sink.
Proof Since the nodes cannot receive multiple packets simultaneously, N Tlink is a trivial lower bound to receive all
packets. However, as in the above discussion, we need at least(2nmax − 1)Tlink for the largest subtrees.


297

B. Collection Time of MSF SchedulingIn the following, we prove that MSF scheduling can achieve
exactly the minimal collection time presented in Theorem 1.
We start to show that all nodes except the sink can always
receive soon after their buffer becomes empty; that is, nodes
can always follow rule 2 of MSF scheduling. Then, we
describe the recurrence formula for the remaining blocks ineach subtree at each 2 k slots. Finally, we derive the recurrence
formula between the total number of nodes and the total timeof collection, and prove that MSF scheduling needs exactly
the minimum time of Theorem 1 to complete collection. We
define a subtree that has remaining blocks to transfer as anactive subtree.
Lemma 1 By applying MSF scheduling, a node with an empty
buffer at slot k can receive all its children which are the root
nodes of the active subtrees.
Proof We prove this by induction of the slot. (i) For all nodes
with an empty buffer at some slot k ≥ 1, suppose that they
can receive from all children that are the roots of the active
subtrees. Then, any node i with an empty buffer receives froma child si,j (= i ), and the buffer node i is empty at the
beginning of the next slot k + 1. We now consider child si ,j 
of node i . The buffer of si ,j  is empty or full at slot k. If nodesi ,j  has an empty buffer at slot k, by the above assumption,
it can receive from one of its children that are roots of its
active subtrees. If node si ,j  has a full buffer at slot k, it isidle at the slot because its parent i is communicating with
node i. Hence, at slot k + 1, node i can receive all the active
children. This holds for all nodes with empty buffers at slot
k + 1.
(ii) At the beginning of collection, i.e., when k = 1, allnodes have a block in their buffers, and a sink’s child s0,jbegins a block transfer. Then, at slot 2, the s0,j ’s buffer
is empty, and s0,j is obviously able to receive from all its
children.
(i) and (ii) indicate that any node with an empty buffer atthe beginning of a slot can receive from all the active children.
Then, we obtain the following corollary directly from
Lemma 1.
Colorally 1 By applying MSF Scheduling, any node with anempty buffer can be ready for transmission after a slot. In otherwords, any node can potentially transmit once every two slots.
Proof Through MSF scheduling, when a node completes a
block transfer at a certain slot, its buffer becomes empty. From
Lemma 1, it can receive from its child node and is ready tosend.
Note that Lemma 1 and Corollary 1 are derived from the factthat a node with an empty buffer immediately can receivefrom its children, and the actual order of the subtrees does
not matter.

Next, we introduce the recurrence formula for the remaining
blocks in each subtree at each 2 k slots. We define a cycle asa couple of slots here. Let Rk = {rjk |r1k ≥ r2k ≥ · · · ≥ rSk 0 }be a set of the number of remaining blocks in S0 subtrees ofthe sink and sorted in nonincreasing order.
Lemma 2 Through MSF scheduling, for Rk={r1k , r2k , r3k , . . . , rSk 0 } at an arbitrary cycle k, Rk+1 is
described by(i)r1k ≥ r2k > 0,

Rk+1 = sort{r1k − 1, r2k − 1, r3k , . . . , rSk 0 }(ii)r1k > r2k = r3k = · · · = rSk 0 = 0,
Rk+1 = {r1k − 1, 0, . . . , 0}

(3)
(4)

where sort represents a descending sort.
Proof Equation (3) gives the number of remaining blocks ineach subtree after the sink receives from the root of the largest
subtree and then receives the root of the second largest subtree
during cycle k. Equation (4) gives the number of remaining
blocks in each subtree after the sink receives from the root of
the largest subtree at the first slot of cycle k and is idle at thesecond slot.
Now, we start to show that equation (3) holds for any cycle
by induction. Suppose equation (3) holds for cycle k. Then,
Rk+1 consists of {r1k − 1, r2k − 1, r3k , . . . , rSk 0 }. Since r1k ≥ r2k ,at the first slot of cycle k + 1, i.e., slot 2k + 1, the sink shouldbe able to receive from the child s0,i where rik+1 = max{r1k −1, r3k , . . . , rSk 0 }. Corollary 1 ensures that the sink can receivefrom an arbitrary node of its children at slot 2k + 1. Similarly,
at the second slot of cycle k + 1, i.e., slot 2k + 2, the sink canreceive from all the nodes except for those that transmitted at
the previous slot. In addition, at the beginning of cycle 1, thesink can receive from all the children trivially. Hence, equation(3) holds for arbitrary cycle k by induction.
Equation (4) is proved in a similar way.

V. I MPLEMENTATION AND E VALUATION
We implemented a prototype of MSFCP using the IRIS
Mote platform, which is based on 802.15.4-compliant RF230
radio. We used the TinyOS software platform. We set thepacket length at 117 bytes including 100 bytes of sensed data
corresponding to 16 samples of a 3-axis accelerometer. We
achieved a throughput of 184 kbps without CCA in thesesettings.
We evaluated the impact of block size and topologies on
the throughput, and we present our findings here.
First, we show the relationship between block size (numberof packets contained in one block) and link throughput in
Fig. 6. For larger block sizes, overhead is reduced, but morememory is required. Although typical sensor nodes havememory limitations (e.q. 8 k bytes on IRIS Mote and 10 kbytes on Tmote Sky), 2–3 k bytes of RAM is adequate for
efficient block transfer, as shown in Fig. 6. Thus, we set the
number of packets in a block at 20.

298

180

interference. We presented the lower bound on collection timeand showed the optimality of MSF scheduling in ideal settings.
We implemented a prototype of MSFCP on the IRIS Mote
platform and evaluated the efficiency of block transfer andoverall throughput of MSFCP.
In the future, we will focus on the construction of a balanced
topology. Theorem 1 indicates that the routing tree should beconstructed in a balanced manner so that nmax ≤ (N + 1)/2.
Constructing a tree where nmax ≤ (N + 1)/2 on an arbitrary
graph G is a kind of Capacitated Minimal Spanning Tree
Problem, and is proven to be NP-complete[14]. For MSFCP,
each node needs information on its subtrees; thus, a balanced
routing tree construction integrated with a function to gather
subtree information is required.

Link throughput

160
throughput [kbps]

140
120
100
80
60
40
20
0
0

5

Fig. 6.

1015
20
packets / block25

30

Efficiency of block transfer

R EFERENCES
Topology 1
Topology 2

Topology 3
Fig. 7.

Topology 4
9-node routing trees

We conducted a test on four 9-node routing trees on the
testbed. The trees had the topologies shown in Fig. 7. In thesesettings, N = 8 and nmax = 8, 6, 3, 2, respectively. The
ideal throughput is the overall throughput without any protocol
overhead, which is calculated based on the link throughput of a
block size of 20 packets. Fig. 8 shows that 80-95 percent of theideal throughput wasis achieved. This throughput degradation
is caused by channel switching and packet losses.
VI. C ONCLUSION AND F UTURE W ORK
We proposed the Maximum-Subtree-First Collection Protocol for high throughput bulk transfer in wireless sensor
networks. When combined with hop-count-based channel assignment and hop-by-hop block transfer, Maximum-SubtreeFirst scheduling can mitigate both intra-path and inter-path140

throughput [kbps]

120

Real
Ideal

100
80
60
40
20
0
1

Fig. 8.

2
3# of topology

4[1] S. Kim, S. Pakzad, D. Culler, J. Demmel, G. Fenves, S. Glaser, and
M. Turon, “Health monitoring of civil infrastructures using wirelesssensor networks,” in Proc. 6th International Conf. on Information
Processing in Sensor Networks, 2007, pp. 254–263.
[2] T. Nagayama, P. Moinzadeh, K. Mechitov, M. Ushita, N. Makihata,
M. Leiri, G. Agha, B. Spencer Jr, Y. Fujino, and J. Seo, “Reliable multihop communication for structural health monitoring,” Smart Structures
and Systems, vol. 6, no. 5-6, pp. 481–504, 2010.
[3] M. Suzuki, S. Saruwatari, N. Kurata, and H. Morikawa, “A high-density
earthquake monitoring system using wireless sensor networks,” in Proc.
5th International Conf. on Embedded Networked Sensor Systems, 2007,
pp. 373–374.
[4] G. Werner-Allen, K. Lorincz, J. Johnson, J. Lees, and M. Welsh,“Fidelity and yield in a volcano monitoring sensor network,” in Proc.
7th Symp. on Operating systems design and implementation, 2006, pp.
381–396.
[5] A. K. Vyas and F. A. Tobagi, “Impact of interference on the throughput
of a multihop path in a wireless network,” in Proc. 3rd International
Conf. on Broadband Communications, Networks, and Systems, 2006, pp.
1–10.
[6] S. Kim, R. Fonseca, P. Dutta, A. Tavakoli, D. Culler, P. Levis, S. Shenker,
and I. Stoica, “Flush: A reliable bulk transport protocol for multihop
wireless networks,” in Proc. 5th International Conf. on Embedded
Networked Sensor Systems, 2007, pp. 351–365.
[7] B. Raman, K. Chebrolu, S. Bijwe, and V. Gabale, “Pip: A connectionoriented, multi-hop, multi-channel tdma-based mac for high throughput
bulk transfer,” in Proc. 8th International Conf. on Embedded Networked
Sensor Systems, 2010, pp. 15–28.
[8] Ö. D. Incel, A. Ghosh, B. Krishnamachari, and K. Chintalapudi, “Fastdata collection in tree-based wireless sensor networks,” IEEE Trans. on
Mobile Computing, vol. 11, no. 1, pp. 86–99, 2012.
[9] O. Gnawali, R. Fonseca, K. Jamieson, D. Moss, and P. Levis, “Collection
tree protocol,” in Proc. 7th International Conf. on Embedded Networked
Sensor Systems, 2009, pp. 1–14.
[10] S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali, “Routing
without routes: The backpressure collection protocol,” in Proc. 9thInternational Conf. on Information Processing in Sensor Networks,
2010, pp. 279–290.
[11] D. Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput
path metric for multi-hop wireless routing,” Wireless Networks, vol. 11,
no. 4, pp. 419–434, 2005.
[12] M. H. Alizai, O. Landsiedel, J. A. B. Link, S. Götz, and K. Wehrle,“Bursty traffic over bursty links,” in Proc. 7th International Conf. on
Embedded Networked Sensor Systems, 2009, pp. 71–84.
[13] Q. Yu, J. Chen, Y. Fan, X. Shen, and Y. Sun, “Multi-channel assignment
in wireless sensor networks: A game theoretic approach,” in Proc. 29th
International Conf. on Computer Communications, 2010, pp. 1127–
1135.
[14] C. H. Papadimitriou, “The complexity of the capacitated tree problem,”
Networks, vol. 8, no. 3, pp. 217–230, 1978.

Impact of topology on throughput

299