  Harsh deployment environments and uncertain run-time conditions create
numerous challenges for postmortem time reconstruction methods. For example,
motes often reboot and thus lose their clock state, considering that the
majority of mote platforms lack a real-time clock. While existing time
reconstruction methods for long-term data gathering networks rely on a
persistent basestation for assigning global timestamps to measurements, the
basestation may be unavailable due to hardware and software faults. We present
Phoenix, a novel offline algorithm for reconstructing global timestamps that is
robust to frequent mote reboots and does not require a persistent global time
source. This independence sets Phoenix apart from the majority of time
reconstruction algorithms which assume that such a source is always available.
Motes in Phoenix exchange their time-related state with their neighbors,
establishing a chain of transitive temporal relationships to one or more motes
with references to the global time. These relationships allow Phoenix to
reconstruct the measurement timeline for each mote. Results from simulations
and a deployment indicate that Phoenix can achieve timing accuracy up to 6 ppm
for 99% of the collected measurements. Phoenix is able to maintain this
performance for periods that last for months without a persistent global time
source. To achieve this level of performance for the targeted environmental
monitoring application, Phoenix requires an additional space overhead of 4% and
an additional duty cycle of 0.2%.
