Change search
ReferencesLink to record
Permanent link

Direct link
Max Contribution: An Online Approximation of Optimal Resource Allocation in Delay Tolerant Networks
KTH, School of Electrical Engineering (EES), Automatic Control.
Show others and affiliations
2015 (English)In: IEEE Transactions on Mobile Computing, ISSN 1536-1233, E-ISSN 1558-0660, Vol. 14, no 3, 592-605 p.Article in journal (Refereed) Published
Abstract [en]

In this paper, a joint optimization of link scheduling, routing and replication for delay-tolerant networks (DTNs) has been studied. The optimization problems for resource allocation in DTNs are typically solved using dynamic programming which requires knowledge of future events such as meeting schedules and durations. This paper defines a new notion of approximation to the optimality for DTNs, called snapshot approximation where nodes are not clairvoyant, i.e., not looking ahead into future events, and thus decisions are made using only contemporarily available knowledges. Unfortunately, the snapshot approximation still requires solving an NP-hard problem of maximum weighted independent set (MWIS) and a global knowledge of who currently owns a copy and what their delivery probabilities are. This paper proposes an algorithm, Max-Contribution (MC) that approximates MWIS problem with a greedy method and its distributed online approximation algorithm, Distributed Max-Contribution (DMC) that performs scheduling, routing and replication based only on locally and contemporarily available information. Through extensive simulations based on real GPS traces tracking over 4,000 taxies and 500 taxies for about 30 days and 25 days in two different large cities, DMC is verified to perform closely to MC and outperform existing heuristically engineered resource allocation algorithms for DTNs.

Place, publisher, year, edition, pages
2015. Vol. 14, no 3, 592-605 p.
Keyword [en]
Resource allocation, routing, scheduling, optimality, delay tolerant network, mobile ad hoc network
National Category
Telecommunications Control Engineering
URN: urn:nbn:se:kth:diva-161601DOI: 10.1109/TMC.2014.2329001ISI: 000349626100011ScopusID: 2-s2.0-84922901288OAI: diva2:797999

QC 20150325

Available from: 2015-03-25 Created: 2015-03-13 Last updated: 2015-03-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jeong, Jaeseong
By organisation
Automatic Control
In the same journal
IEEE Transactions on Mobile Computing
TelecommunicationsControl Engineering

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

Altmetric score

Total: 19 hits
ReferencesLink to record
Permanent link

Direct link