Finding Multiple Length-Bounded Disjoint Paths in Wireless Sensor Networks

• 作者: Hong Gao Kejia Zhang
• 来源期刊: 无线传感网络(英文)
• 学科: 数学
• 关键词: DISJOINT PATHS SENSOR NETWORKS Length-Bounded PATHS
• 年，卷（期）: 2011,（12）
• 页码范围: 384-390
• 页数: 7页
• 分类号: O1

摘要

In a wireless sensor network, routing messages between two nodes s and t with multiple disjoint paths will increase the throughput, robustness and load balance of the network. The existing researches focus on finding multiple disjoint paths connecting s and t efficiently, but they do not consider length constraint of the paths. A too long path will be useless because of high latency and high packet loss rate. This paper deals with such a problem: given two nodes s and t in a sensor network, finding as many as possible disjoint paths connecting s and t whose lengths are no more than L, where L is the length bound set by the users. By now, we know that this problem is not only NP hard but also APX complete [1,2], which means that there is no PTAS for this problem. To the best of our knowledge, there is only one heuristic algorithm proposed for this problem [3], and it is not suitable for sensor network because it processes in a centralized way. This paper proposes an efficient distributed algorithm for this problem. By processing in a distributed way, the algorithm is very communication efficient. Simulation results show that our algorithm outperforms the existing algorithm in both aspects of found path number and communication efficiency.