Open AccessDFDP: A Distributed Algorithm for Finding Disjoint Paths in Wireless Sensor Networks with Correctness Guarantee
Author(s) -
Kejia Zhang,
Guisheng Yin,
Qilong Han,
Junyu Lin
Publication year - 2014
Publication title -
international journal of distributed sensor networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.324
H-Index - 53
eISSN - 1550-1477
pISSN - 1550-1329
DOI - 10.1155/2014/258959
Subject(s) - computer science , disjoint sets , correctness , distributed algorithm , wireless sensor network , algorithm , distributed computing , robustness (evolution) , routing (electronic design automation) , computer network , node (physics) , mathematics , discrete mathematics , biochemistry , chemistry , gene , structural engineering , engineering
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom