LooP: A Low-Overhead Path Reconstruction for Large-Scale IoTs

Internet of Things (IoT) plays a vital role in various smart applications due to its cost-efficiency and good scalability. For safety and management of a large-scale IoT with many gateways, packet-level path reconstruction which exactly reveals the transmission path of each packet is desired. However, the existing path reconstruction schemes rely on correlation between diverse packets, which results in either considerable overhead or poor accuracy. It is particularly difficult to reconstruct the paths by affordable overhead under the intensive deployment, constrained resource, and weak correlation of IoT devices. To this end, we propose a <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Lo</b>w-<bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</b>verhead <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</b>ath reconstruction (LooP) for large-scale IoT. The proposed scheme exploits the nature of incremental update that each node only identifies the changes of its one-hop topology for diverse gateways. The gateway nodes then iteratively recover the complete path of each received packet according to the reported changes and historical information. It removes much redundant overhead (e.g., the common paths information) while guaranteeing the accurate reconstruction in a large scale and dynamic topology network. We analyze the information entropy of LooP and several existing schemes to theoretically prove the superiority of our proposal. The experimental results also demonstrate LooP can achieve 98% reconstruction accuracy on average and at least 3x gain-cost-ratio of the sub-optimal rival.