Finding Multiple Length-Bounded Disjoint Paths in Wireless Sensor Networks

Kejia Zhang, Hong Gao

.

DOI: 10.4236/wsn.2011.312045                

Abstract

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.

Keywords

Disjoint Paths, Sensor Networks, Length-Bounded Paths

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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
[3]	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
[4]	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.
[5]	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
[6]	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
[7]	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
[8]	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.
[9]	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
[10]	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
[11]	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.
[12]	Y. Chen, X. Guo, Q. Zeng and G. Chen, “AMR: A Multipath Routing Algorithm Based on Maximum Flow in Ad-Hoc Networks,” Acta Electronica Sinica, Vol. 32, No. 8, 2004, pp. 1297-1301.
[13]	X. Fang, S. Shi and J. Li, “A Disjoint Multi-Path Routing Algorithm in Wireless Sensor Network,” Journal of Computer Research and Development, Vol. 46, No. 12, 2009, pp. 2053-2061.
[14]	A. Itai, Y. Perl and Y. Shiloach, “The Complexity of Finding Maximum Disjoint Paths with Length Constraints,” Networks, Vol. 12, No. 3, 1982, pp. 277-286. doi:10.1002/net.3230120306
[15]	D. Sidhu, R. Nair and S. Abdallah, “Finding Disjoint Paths in Networks,” SIGCOMM Computer Communication Review, Vol. 21, No. 4, 1991, pp. 43-51. doi:10.1145/115994.115998
[16]	R. Bhandari, “Optimal Physical Diversity Algorithms and Survivable Networks,” Proceedings of the 2nd IEEE Symposium on Computers and Communications, Alexandria, 1-3 July 1997, pp. 433-441. doi:10.1109/ISCC.1997.616037
[17]	S. Khuller and B. Schieber, “Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s - t Paths in Graphs,” Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, 30 October - 1 November 1989, pp. 288- 293. doi:10.1109/SFCS.1989.63492
[18]	K. Iwama, C. Iwamoto and T. Ohsawa, “A Faster Parallel Algorithm for k-Connectivity,” Information Processing Letters, Vol. 61, No. 5, 1997, pp. 265-269. doi:10.1016/S0020-0190(97)00015-X
[19]	J. W. Suurballe, “Disjoint Paths in a Network,” Networks, Vol. 4, No. 2, 1974, pp. 125-145. doi:10.1002/net.3230040204
[20]	J. Edmonds, “Paths, Trees and Flowers,” Canadian Journal of mathematics, Vol. 17, No. 3, 1965, pp. 449-467.