Back to Search
Start Over
A Dynamic Combined Flow Algorithm for the Two-Commodity Max-Flow Problem Over Delay-Tolerant Networks
- Source :
- IEEE Transactions on Wireless Communications. 17:7879-7893
- Publication Year :
- 2018
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2018.
-
Abstract
- The multi-commodity flow problem plays an important role in network optimization, routing, and service scheduling. With the network partitioning and the intermittent connectivity, the commodity flows in delay tolerant networks (DTNs) are time-dependent, which is very different from that over the static networks. As an NP-hard problem, existing works can only obtain sub-optimal results on maximizing the multi-commodity flow of dynamic networks. To overcome these bottlenecks, in this paper, we propose a graph-based algorithm to solve the maximum two-commodity flow problem over the DTNs. Through analyzing the relationship between the two commodities, we propose a maximum two-commodity flow theorem to simplify the coupling two-commodity flow problem as the two single-commodity flow ones. Then, with the help of the storage time aggregated graph (STAG) (a DTN model with less memory), we construct a pair of flow graphs to describe the reduced two single-commodity flows (addition flow and subtraction flow), and design the corresponding flow calculation methods. Moreover, we design a STAG-based dynamic combined flow algorithm to maximize the two-commodity flow. Finally, the computational complexity of the proposed algorithm is analyzed, and its efficacy has also been demonstrated through an illustrative example and numerical simulations.
- Subjects :
- Computational complexity theory
business.industry
Computer science
Applied Mathematics
Maximum flow problem
020206 networking & telecommunications
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Graph
Computer Science Applications
Scheduling (computing)
Combined flow
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
Wireless
Electrical and Electronic Engineering
business
Algorithm
Subjects
Details
- ISSN :
- 15582248 and 15361276
- Volume :
- 17
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Wireless Communications
- Accession number :
- edsair.doi...........4760630a9a786c61e36b0abd8a525bb4