Metric and Distributed On-Line Algorithm for Minimizing Routing Interference in Wireless Sensor Networks

摘要

First, this paper gives a metric to quantify interference level among multiple routing paths in wireless sensor networks. Unlike the existing metrics, the proposed one can precisely measure interference level among any set of paths, even though these paths have some nodes or links in common. Based on the proposed metric, the Minimizing-Interference-for-Multiple-Paths (MIMP) problem is considered: Given k routing requests {s_1,t_1},..., {s_k,t_k}, find k paths connecting these routing requests with minimum interference. The MIMP problem is NP-hard even for k = 2. This paper proposes heuristic distributed on-line algorithm for the MIMP problem. The efficiency of the proposed algorithm is verified by simulation results.