Optimal Sampling Strategies for Minimum Latency Routing With Imperfect Link State
Since dynamic wireless networks evolve over time, optimal routing computations need to be performed frequently on time-varying network topologies. However, it is often infeasible or expensive to gather the current state of links for the entire network all the time. The authors provide a thorough analytical characterization of the effect of various link-state sampling strategies operating under a limited sampling budget on the performance of the minimum-latency routing policy in a special class of dynamic networks. They precisely characterize the optimal-latency spatial-sampling schedules for one-shot interrogation. They also present numerical simulation results on comparing various spatio-temporal sampling schedules under an overall sampling rate constraint, and initial results on comparisons of optimal schedules under a StOre-and-Advance (SoA) packet-forwarding latency model.