{"id":{"repo_id":"msu","oai_identifier":"oai:d.lib.msu.edu:etd_52675"},"canonical_url":"https://search.ndltd.org/etd/msu/oai:d.lib.msu.edu:etd_52675","repository":{"repo_id":"msu","name":"Michigan State University","base_url":"https://d.lib.msu.edu/oai"},"display":{"title":"Efficient Multi-Commodity Satellite Scheduling and Routing Algorithms for Earth Observation Applications","abstract":"Thesis (M.S.)--Michigan State University. Computer Science - Master of Science, 2025","abstract_html":"Thesis (M.S.)--Michigan State University. Computer Science - Master of Science, 2025","abstract_has_math":false,"creators":["Brenholt, Alisha Valentina"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Xiao, Li","McKinley, Philip","Tu, Guan-Hua"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-11-18T18:59:26Z","subjects":["Computer science"],"languages":["eng"],"rights":["In Copyright"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:52675","local:Brenholt_grad.msu_0128N_21644"],"render_values":[{"text":"etd:52675","href":null,"code":true},{"text":"local:Brenholt_grad.msu_0128N_21644","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://doi.org/doi:10.25335/y4re-sv51","outbound_label":"DOI","outbound_source":"dc:identifier","record_url":"https://doi.org/doi:10.25335/y4re-sv51","record_label":"Repository record","record_kind":"doi","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_52675","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Xiao, Li","McKinley, Philip","Tu, Guan-Hua"]},{"key":"dc:creator","label":"Author","values":["Brenholt, Alisha Valentina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025"]},{"key":"dc:relation","label":"Dc Relation","values":["Electronic Theses & Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["text","Electronic dissertations"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["etd:52675","local:Brenholt_grad.msu_0128N_21644","https://doi.org/doi:10.25335/y4re-sv51"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M.S.)--Michigan State University. Computer Science - Master of Science, 2025","Earth Observation Low Earth Orbit (EOLEO) satellites orbit the Earth, collecting hundreds of gigabytes of data per day, while traveling up to 27,000 km/h. This combination of high velocity and data volume poses a challenge when transmitting the collected data back to Earth. Current state-of-the-art techniques rely on graph solvers, column-generation algorithms, or greedy algorithms to schedule and route data in single-commodity scenarios. A single-commodity scenario only views a single commodity at a time, rather than multiple commodities in a multi-commodity scenario. A multi-commodity scenario can properly model what happens when multiple companies, each with their own commodity, use different algorithms to schedule and route data to the same ground station. We show that while graph solvers can obtain a perfect solution for a defined state, its computational overhead explodes in multi-commodity scenarios, and the algorithm is NP-complete in multi-commodity scenarios. Column generation algorithms can avoid NP-complete restrictions but leak proprietary satellite information. A Greedy algorithm, while fast, gives substantially worse data throughput. We introduce the Multi-commodity Scheduling and Routing Algorithm to solve the computational issue, preserve privacy, and operate in multi-commodity scenarios. The Multi-Commodity Scheduling and Routing algorithm utilizes dynamic weighted Voronoi diagrams to prevent state explosion, preserve privacy, and reduce computational overhead. We demonstrate improvements in data throughput of up to 5.5% in multi-commodity scenarios, and reduced computation time by as much as 800% compared to state-of-the-art algorithms. This is all implemented in, as far as we can find, a first-of-its-kind multi-commodity satellite network simulator.","Description based on online resource. Title from PDF t.p. (Michigan State University Fedora Repository, viewed ).","Includes bibliographical references."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf","1 online resource (63 p.) : ill."]},{"key":"dc:title","label":"Title","values":["Efficient Multi-Commodity Satellite Scheduling and Routing Algorithms for Earth Observation Applications"]}]}],"canonical_facts":{"dc:contributor":["Xiao, Li","McKinley, Philip","Tu, Guan-Hua"],"dc:creator":["Brenholt, Alisha Valentina"],"dc:date":["2025"],"dc:description":["Thesis (M.S.)--Michigan State University. Computer Science - Master of Science, 2025","Earth Observation Low Earth Orbit (EOLEO) satellites orbit the Earth, collecting hundreds of gigabytes of data per day, while traveling up to 27,000 km/h. This combination of high velocity and data volume poses a challenge when transmitting the collected data back to Earth. Current state-of-the-art techniques rely on graph solvers, column-generation algorithms, or greedy algorithms to schedule and route data in single-commodity scenarios. A single-commodity scenario only views a single commodity at a time, rather than multiple commodities in a multi-commodity scenario. A multi-commodity scenario can properly model what happens when multiple companies, each with their own commodity, use different algorithms to schedule and route data to the same ground station. We show that while graph solvers can obtain a perfect solution for a defined state, its computational overhead explodes in multi-commodity scenarios, and the algorithm is NP-complete in multi-commodity scenarios. Column generation algorithms can avoid NP-complete restrictions but leak proprietary satellite information. A Greedy algorithm, while fast, gives substantially worse data throughput. We introduce the Multi-commodity Scheduling and Routing Algorithm to solve the computational issue, preserve privacy, and operate in multi-commodity scenarios. The Multi-Commodity Scheduling and Routing algorithm utilizes dynamic weighted Voronoi diagrams to prevent state explosion, preserve privacy, and reduce computational overhead. We demonstrate improvements in data throughput of up to 5.5% in multi-commodity scenarios, and reduced computation time by as much as 800% compared to state-of-the-art algorithms. This is all implemented in, as far as we can find, a first-of-its-kind multi-commodity satellite network simulator.","Description based on online resource. Title from PDF t.p. (Michigan State University Fedora Repository, viewed ).","Includes bibliographical references."],"dc:format":["application/pdf","1 online resource (63 p.) : ill."],"dc:identifier":["etd:52675","local:Brenholt_grad.msu_0128N_21644","https://doi.org/doi:10.25335/y4re-sv51"],"dc:language":["eng"],"dc:relation":["Electronic Theses & Dissertations"],"dc:rights":["In Copyright"],"dc:subject":["Computer science"],"dc:title":["Efficient Multi-Commodity Satellite Scheduling and Routing Algorithms for Earth Observation Applications"],"dc:type":["text","Electronic dissertations"]},"updated_at":"2026-11-18T18:59:26Z"}