Finding Multiple Length-Bounded Disjoint Paths in Wireless Sensor Networks
- 1
- 2
Abstract
In a wireless sensor network, routing messages between two nodes <i>s</i> and <i>t</i> 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 <i>s</i> and <i>t</i> 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 <i>s</i> and <i>t</i> in a sensor network, finding as many as possible disjoint paths connecting <i>s</i> and <i>t</i> whose lengths are no more than <i>L</i>, where <i>L</i> 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.
- A. Bley, “On the Complexity of Vertex-Disjoint Length-Restricted Path Problems,” Computational Complexity, Vol. 12, No. 3, 2003, pp. 131-149. doi:10.1007/s00037-003-0179-6
- D. Ronen and Y. Perl, “Heuristics for Finding a Maximum Number of Disjoint Bounded Paths,” Networks, Vol. 14, No. 4, 1984, pp. 531-544. doi:10.1002/net.3230140405
- K. Ishida, Y. Kakuda and T. Kikuno, “A Routing Protocol for Finding Two Node-Disjoint Paths in Computer Networks,” Proceedings of 1995 International Conference on Network Protocols, Tokyo, 7-10 November 1995, pp. 340-347. doi:10.1109/ICNP.1995.524850
- V. Shnayder, M. Hempstead, B. Chen, G. W. Allen and M. Welsh, “Simulating the Power Consumption of Large- Scale Sensor Network Applications,” Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, 3-5 November 2004, pp. 188- 200.
- P. Gupta and P. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Information Theory, Vol. 46, No. 2, 2000, pp. 388-404. doi:10.1109/18.825799
- D. Ganesan, R. Govindan, S. Shenker and D. Estrin, “Highlyresilient, Energy-Efficient Multipath Routing in Wireless Sensor Networks,” ACM SIGMOBILE Mobile Computing and Communications Review, Vol. 5, No. 4, 2001, pp. 11-25. doi:10.1145/509506.509514
- A. Srinivas, G. Theory and E. Modiano, “Minimum Energy Disjoint Path Routing in Wireless Ad-Hoc Networks,” Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, 14-19 September 2003, pp. 122-133. doi:10.1145/938985.938999
- S. Li and Z. Wu, “Node-Disjoint Parallel Multi-Path Routing in Wireless Sensor Networks,” The 2nd International Conference on Embedded Software and Systems, Xi’an, 16-18 December 2005. p. 6.
- J. W. Baek, Y. J. Nam and D. W. Seo, “An Energyefficient k-Disjoint-Path Routing Algorithm for Reliable Wireless Sensor Networks,” Software Technologies for Embedded and Ubiquitous Systems of Lecture Notes in Computer Science, Vol. 4761, 2007, pp. 399-408. doi:10.1007/978-3-540-75664-4_42
- B. Deb, S. Bhatnagar and B. Nath, “Reinform: Reliable Information Forwarding Using Multiple Paths in Sensor Networks,” Proceedings of 28th Annual IEEE International Conference on Local Computer Networks, Bonn/ Konigswinter, 20-24 October 2003, pp. 406-415. doi:10.1109/LCN.2003.1243166
- R. Ogier, V. Rutenburg and N. Shacham, “Distributed Algorithms for Computing Shortest Pairs of Disjoint Paths, ” IEEE Transactions on Information Theory, Vol. 39, No. 2, 1993, PP. 443-455.