DFDP: A Distributed Algorithm for Finding Disjoint Paths in Wireless Sensor Networks with Correctness Guarantee

Kejia Zhang, Guisheng Yin, Qilong Han and Junyu Lin

International Journal of Distributed Sensor Networks, 2014, vol. 10, issue 6, 258959

Abstract: In wireless sensor networks, routing messages through multiple (node) disjoint paths between two sensor nodes is a promising way to increase robustness, throughput, and load balance. This paper proposes an efficient distributed algorithm named distributedly finding disjoint paths (DFDP) to find k disjoint paths connecting two given nodes s and t . A set of paths connecting s and t are disjoint if any two of them do not have any common nodes except s and t . Unlike the existing distributed algorithms, DFDP guarantees correctness; that is, it will output k disjoint paths if there exist k disjoint paths in the network or the maximum number of disjoint paths otherwise. Compared with the centralized algorithms which also guarantee correctness, DFDP is shown to have much better efficiency and load balance by theory analysis and simulation results.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2014/258959 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:10:y:2014:i:6:p:258959

DOI: 10.1155/2014/258959

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().