Universal Path Tracing for Large-Scale Sensor
Networks
Yi Gao, Wei Dong
∗
, Xiaoyu Zhang, Wenbin Wu
College of Computer Science, Zhejiang University, China.
Zhejiang Provincial Key Laboratory of Service Robot, China.
Email: {gaoyi, dongw, zhangxy1991, wuwb}@zju.edu.cn
Abstract—Most sensor networks employ dynamic routing
protocols so that the routing topology can be dynamically
optimized with environmental changes. The routing behaviors
can be quite complex with increasing network scale and
environmental dynamics. Knowledge on the routing path of each
packet is certainly a great help in understanding the complex
routing behaviors, allowing effective performance diagnosis and
efficient network management. We propose PAT, a universal
sensornet path tracing approach. PAT includes an intelligent path
encoding scheme that allows efficient decoding at the PC side.
To make PAT more scalable, we propose techniques to accurately
estimate the degree information by exploiting timing information,
allowing more compact path encoding. Moreover, we employ
subpath concatenation to infer excessively long paths with a high
recovery probability. We carefully evaluate PAT’s performance
using testbed experiments and and extensive simulations with up
to 4,000 nodes. Results show that PAT significantly outperforms
existing approaches.
I. INTRODUCTION
As an emerging technology that bridges cyber systems
and the physical world, wireless sensor networks (WSNs)
are envisioned to support numerous applications such as
military surveillance, environmental monitoring, infrastructure
protection, etc [1, 2]. In these networks, large numbers of
tiny, low-power wireless sensing devices are self-organized,
collecting the sensing data to a central sink in a multihop
manner.
Most sensor networks employ dynamic routing protocols
so that the routing topology can be dynamically optimized
with environmental changes. The TinyOS CTP protocol [3]
is an instance of dynamic routing protocol with which each
node regularly estimates the expected number of transmissions
(ETX) [4] to the sink and dynamically selects the next-hop
forwarder with a minimum ETX along the path. Due to
the dynamic routing scheme, a node could forward different
packets to different next hops, although these packets have the
same destination, i.e., the sink node.
The routing behaviors can be quite complex with increasing
network scale and environmental dynamics: packets from a
distant sensor node may follow numerous routing paths to the
This work is supported by the National Science Foundation of China
(No. 61502417 and No. 61472360), Zhejiang Provincial Natural Science
Foundation of China (No. LY16F020006), Zhejiang Provincial Key Research
and Development Program (No. 2017C02044), CCF-Tencent Open Research
Fund, and Fundamental Research Funds for the Central Universities
(2016QNA5012, 2016FZA5010).
∗
Wei Dong is the corresponding author.
sink. Knowledge on the routing path of each packet is very
useful in the following ways.
• It is important for understanding the dynamic routing
topology, revealing the complex routing behaviors. Such
a knowledge is essential for topology control, routing
improvement, and load balance, enabling effective man-
agement and optimized operations for deployed WSNs
consisting of a large number of unattended wireless sensor
nodes [5].
• It is essential for deriving important system metrics, e.g.,
per-link loss ratio and per-link delays. Most existing
works on link loss and delay monitoring [5–9] assume
that the routing topology is given a priori. Most of
them are restricted to static routing tree estimation,
which is unrealistic and problematic in real-world WSN
deployments where routing topology is time-varying due to
wireless channel dynamics such as fading and interference
[5]. The investigation into realistic and dynamic routing
topology can significantly improve the values of the works
on WSN loss/delay tomography.
• It is very useful for effective network diagnosis and analy-
sis. Most existing works heavily rely on the obtained net-
work topology for inference, allowing further performance
diagnosis and analysis [10–13]. For example, PAD [10]
relies on dynamic network topology for maintaining the
inference model which encodes the internal dependencies
among different network elements, for online diagnosis of
an operational sensor network system. MAP [11] also relies
on the dynamic network topology for defining the impact
scope of a network event, allowing accurate measurement
on the root causes of packet losses. Clearly, obtaining
the accurate per-packet path in a lightweight manner will
greatly improve the accuracy of the measurement and
diagnosis results.
Attaching each packet with the routing path hop-by-hop is
not an attractive approach due to the large message overhead
for packets with long routing paths (perhaps with routing
loops). It is hence desirable to instrument a small message
overhead to each packet, and reconstruct the routing path at
the sink with a high recovery ratio.
We expect that a good path tracing approach should ideally
meet the following two requirements.
• Universal: Since a sensor network can be usually classified
into periodic monitoring (where all nodes generate data
packets, e.g., environmental monitoring), event-triggered
(where only a few nodes generate data packets, e.g.,
IEEE INFOCOM 2017 - IEEE Conference on Computer Communications
978-1-5090-5336-0/17/$31.00 ©2017 IEEE