Name
Title | ||
|---|---|---|
OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks |
Abstract | ||
|---|---|---|
This paper investigates the MINimum-length-$$k$$k-Disjoint-Paths (MIN-$$k$$k-DP) problem: in a sensor network, given two nodes $$s$$s and $$t$$t, a positive integer $$k$$k, finding $$k$$k (node) disjoint paths connecting $$s$$s and $$t$$t with minimum total length. An efficient distributed algorithm named Optimally-Finding-Disjoint-Paths (OFDP) is proposed for this problem. OFDP guarantees correctness and optimality, i.e., (1) it will find $$k$$k disjoint paths if there exist $$k$$k disjoint paths in the network or the maximum number of disjoint paths otherwise; (2) the disjoint paths it outputs do have minimum total length. To the best of our knowledge, OFDP is the first distributed algorithm that can solve the MIN-$$k$$k-DP problem with correctness and optimality guarantee. Compared with the existing centralized algorithms which also guarantee correctness and optimality, OFDP is shown to be much more efficient by simulation results. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s10878-015-9845-2 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Disjoint paths,Minimum total length,Sensor networks,Distributed algorithm | Integer,Mathematical optimization,Disjoint sets,Correctness,Theoretical computer science,Distributed algorithm,Wireless sensor network,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 4 | 1382-6905 |
Citations | PageRank | References |
1 | 0.36 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kejia Zhang | 1 | 8 | 3.86 |
| qilong han | 2 | 1 | 0.36 |
| Guisheng Yin | 3 | 25 | 8.30 |
| Haiwei Pan | 4 | 52 | 21.31 |