Change search
ReferencesLink to record
Permanent link

Direct link
Path Set Selection in Mobile Ad Hoc Networks
2002 (English)In: Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2002, 1-11 p.Conference paper (Refereed)
Abstract [en]

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on the network ability to support QoS-driven services. A promising technique for addressing this problem is to use multiple redundant paths between the source and the destination. However, while multipath routing algorithms can tolerate network failures well, their failure resilience only holds if the paths are selected judiciously. In particular, the correlation between the failures of the paths in a redundant path set should be as small as possible. However, selecting an optimal path set is an NP-complete problem. Heuristic solutions proposed in the literature are either too complex to be performed in real-time, or too ineffective, or both. This paper proposes a multipath routing algorithm, called Disjoint Pathset Selection Protocol (DPSP), based on a novel heuristic that, in nearly linear time on average, picks a set of highly reliable paths. The convergence to a highly reliable path set is very fast, and the protocol provides flexibility in path selection and routing algorithm. Furthermore, DPSP is suitable for real-time execution, with nearly no message exchange overhead and with minimal additional storage requirements. This paper presents evidence that multipath routing can mask a substantial number of failures in the network compared to single path routing protocols, and that the selection of paths according to DPSP can be beneficial for mobile ad hoc networks, since it dramatically reduces the rate of route discoveries.

Place, publisher, year, edition, pages
2002. 1-11 p.
National Category
Communication Systems
URN: urn:nbn:se:kth:diva-35569OAI: diva2:429018
Third ACM International Symposium on Mobile Ad Hoc Networking and Computing; Lausanne; 9 June 2002 through 11 June 2002
Available from: 2011-07-01 Created: 2011-07-01 Last updated: 2011-09-28Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Papadimitratos, Panagiotis
Communication Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link