A Novel Per-Hop Per-Packet Delay Tomography in Wireless Ad Hoc Networks

Packet delivery delay is one of the most important performance metrics in multi-hop wireless ad-hoc networks. Though numerous research efforts have been spent on measuring and optimizing the end-to-end delay performance, there frequently lack precise and lightweight methods for decomposing the end-to-end delay into the per-hop delay for every packet. The per-hop per-packet delay is able to deeply improve the network visibility and create probable network management and measurement. This thesis proposes Domo, an accurate and lightweight delay tomography method for decomposing the packet end-to-end delay into every hop. The basic idea is to formulate the problem into a set of optimization problems by carefully considering the constraints among various timing quantities. At the network side, Domo attaches a small overhead to each packet for constructing constraints for the optimization problems. At the PC side, Domo employs semi definite relaxation and several other methods to efficiently solve the optimization problems. This thesis implements Domo and evaluates its performance extensively using large-scale simulations. Results show that Domo significantly outperforms two existing methods, nearly tripling the accuracy of the state-of-the-art.