Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks
Li H., Zhang T., Zhang Y., Wang K., Li J. Ad Hoc Networks59 (C):63-70,2017.Type:Article
Date Reviewed: May 26 2017

Searching for maximum flow in a network based on graph theory is essential in planning the route and scheduling transmission. Therefore, it is natural to study the maximum flow on various types of networks. While traditional maximum flow algorithms are applicable to static networks, they are not applicable to emerging delay-tolerant networks such as sensor networks or ad hoc networks because the capacity of those networks is time varying. This paper brings the time-varying capacity into consideration and proposes a maximum flow algorithm using a storage time aggregated graph (STAG).

The network system model in this paper includes a series of time interval capacity instead of a static capacity for an edge (that is, link). A primary feature of the model is that each vertex is associated with a bidirectional storage transfer series, which represents the amount of flow transferred between adjacent time intervals. This implies that each vertex can store received data until the capacity of the next hop becomes available. The proposed algorithm follows the steps of those in traditional maximum flow algorithms; that is, it consists of seeking an augmenting path in a residual STAG (rSTAG), computing the maximum flow of the augmenting path, and getting the residual capacity. The algorithm seeks an augmenting path by searching an edge that has the earliest time of positive capacity. The approach used in the algorithms for computing the maximum flow of the augmenting path and residual capacity is traversing the entire time interval reversely and orderly, respectively.

The main contribution of this paper is proposing a network model representing delay-tolerant networks. The storage transfer series of the proposed network model plays the key role in the proposed algorithms for the three steps. Owing to the proposed algorithm, it is possible to solve the maximum flow in a time-varying network link capacity such as a delay-tolerant network. Because the algorithm is applicable to networks where all parameters are given in advance, it will be useful to obtain the maximum flow and plan the network routing if the time series capacity for all network edges can be estimated.

Reviewer:  Seon Yeong Han Review #: CR145302 (1708-0539)
Bookmark and Share
 
Sensor Networks (C.2.1 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Sensor Networks": Date
Performance analysis of opportunistic broadcast for delay-tolerant wireless sensor networks
Nayebi A., Sarbazi-Azad H., Karlsson G. Journal of Systems and Software 83(8): 1310-1317, 2010. Type: Article
Nov 8 2010
Heartbeat of a nest: using imagers as biological sensors
Ko T., Ahmadian S., Hicks J., Rahimi M., Estrin D., Soatto S., Coe S., Hamilton M. ACM Transactions on Sensor Networks 6(3): 1-31, 2010. Type: Article
Jan 10 2011
Efficient clustering-based data aggregation techniques for wireless sensor networks
Jung W., Lim K., Ko Y., Park S. Wireless Networks 17(5): 1387-1400, 2011. Type: Article
May 8 2012
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy