DOAMI: A distributed on-line algorithm to minimize interference for routing in wireless sensor networks

摘要

This paper investigates the Minimizing-Interference-for-Multiple-Paths (MIMP) problem for routing with minimum interference in wireless sensor networks, which is defined as: Given k routing requests {s(1), t(1)},..., {s(k), t(k)}, find k paths connecting these routing requests with minimum (wireless) interference. A key point to solve this problem is how to quantify interference level among multiple routing paths. However, all the existing metrics cannot measure interference precisely under some certain circumstances, e.g., some of the routing paths have common nodes or links. This paper proposes a metric that can measure interference precisely among any set of paths, even though these paths have some nodes or links in common. For this proposed metric, the MIMP problem is NP-hard even for k = 2. A heuristic Distributed On-line Algorithm for Minimizing Interference (DOAMI) is given to solve the MIMP problem. DOAMI has good communication and time complexity in theory, whose efficiency is also verified by simulation results. (C) 2016 Published by Elsevier B.V.