Back to search

Clemson University

Mathematical Models and Algorithms for Network Flow Problems Arising in Wireless Sensor Network Applications

Abstract

dc:description.abstract

We examine multiple variations on two classical network flow problems, the maximum flow and minimum-cost flow problems. These two problems are well-studied within the optimization community, and many models and algorithms have been presented for their solution. Due to the unique characteristics of the problems we consider, existing approaches cannot be directly applied. The problem variations we examine commonly arise in wireless sensor network (WSN) applications. A WSN consists of a set of sensors and collection sinks that gather and analyze environmental conditions. In addition to providing a taxonomy of relevant literature, we present mathematical programming models and algorithms for solving such problems. First, we consider a variation of the maximum flow problem having node-capacity restrictions. As an alternative to solving a single linear programming (LP) model, we present two alternative solution techniques. The first iteratively solves two smaller auxiliary LP models, and the second is a heuristic approach that avoids solving any LP. We also examine a variation of the maximum flow problem having semicontinuous restrictions that requires the flow, if positive, on any path to be greater than or equal to a minimum threshold. To avoid solving a mixed-integer programming (MIP) model, we present a branch-and-price algorithm that significantly improves the computational time required to solve the problem. Finally, we study two dynamic network flow problems that arise in wireless sensor networks under non-simultaneous flow assumptions. We first consider a dynamic maximum flow problem that requires an arc to transmit a minimum amount of flow each time it begins transmission. We present an MIP for solving this problem along with a heuristic algorithm for its solution. Additionally, we study a dynamic minimum-cost flow problem, in which an additional cost is incurred each time an arc begins transmission. In addition to an MIP, we present an exact algorithm that iteratively solves a relaxed version of the MIP until an optimal solution is found.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Industrial Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Curry, Robert M.
Contributors dc:contributor
  • Dr. J. Cole Smith, Committee Chair
  • Dr. Warren Adams
  • Dr. Sandra D. Ekşioğlu
  • Dr. Amin Khademi

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/2226

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Curry, Robert M.. Mathematical Models and Algorithms for Network Flow Problems Arising in Wireless Sensor Network Applications. Dissertation thesis, https://open.clemson.edu/all_dissertations/2226