{"id":{"repo_id":"sdstate","oai_identifier":"oai:openprairie.sdstate.edu:etd2-2603"},"canonical_url":"https://search.ndltd.org/etd/sdstate/oai:openprairie.sdstate.edu:etd2-2603","repository":{"repo_id":"sdstate","name":"South Dakota State University","base_url":"https://openprairie.sdstate.edu/do/oai/"},"display":{"title":"Optimality of Minimum Power Broadcasting in Wireless Ad Hoc Networks","abstract":"In the current state of technology, the focus on wireless networks is higher than ever before. It is considered standard that laptops and mobile phones have wireless functionality. It is necessary to keep the battery of these devices alive as long as possible. Some networks, for example wireless ad hoc networks where infrastructures do not exist, rely on ability of all devices to maintain functionality in order to keep the life of the entire network alive. For unicast communication, the shortest path will find an optimal solution which cannot be applied to broadcast or multicast communications. In order to maintain battery life, it is important to find the optimal tree structure that uses the least amount of total power to reach all nodes in the tree. In this thesis, we review algorithms found in the literature that don't necessarily find the optimal solution to the tree problem, but do find the answer in a shorter computing time. We then show how we find the optimal solution using integer programming, and use the results to find the commonalities in these optimal solutions. Our contribution in this work is a rigorous study of theoretical aspects of commonalities of optimal solutions which can be used to create a better heuristic.","abstract_html":"In the current state of technology, the focus on wireless networks is higher than ever before. It is considered standard that laptops and mobile phones have wireless functionality. It is necessary to keep the battery of these devices alive as long as possible. Some networks, for example wireless ad hoc networks where infrastructures do not exist, rely on ability of all devices to maintain functionality in order to keep the life of the entire network alive. For unicast communication, the shortest path will find an optimal solution which cannot be applied to broadcast or multicast communications. In order to maintain battery life, it is important to find the optimal tree structure that uses the least amount of total power to reach all nodes in the tree. In this thesis, we review algorithms found in the literature that don&#x27;t necessarily find the optimal solution to the tree problem, but do find the answer in a shorter computing time. We then show how we find the optimal solution using integer programming, and use the results to find the commonalities in these optimal solutions. Our contribution in this work is a rigorous study of theoretical aspects of commonalities of optimal solutions which can be used to create a better heuristic.","abstract_has_math":false,"creators":["O'Brien, Austin"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis - University Access Only","degree_discipline":"Electrical Engineering and Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T09:05:30Z","subjects":[],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://openprairie.sdstate.edu/etd2/1609","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://openprairie.sdstate.edu/etd2/1609","record_label":"Repository record","record_kind":"record","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://openprairie.sdstate.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aopenprairie.sdstate.edu%3Aetd2-2603","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["O'Brien, Austin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2025-05-30T07:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2009-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering and Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - University Access Only"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://openprairie.sdstate.edu/etd2/1609"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In the current state of technology, the focus on wireless networks is higher than ever before. It is considered standard that laptops and mobile phones have wireless functionality. It is necessary to keep the battery of these devices alive as long as possible. Some networks, for example wireless ad hoc networks where infrastructures do not exist, rely on ability of all devices to maintain functionality in order to keep the life of the entire network alive. For unicast communication, the shortest path will find an optimal solution which cannot be applied to broadcast or multicast communications. In order to maintain battery life, it is important to find the optimal tree structure that uses the least amount of total power to reach all nodes in the tree. In this thesis, we review algorithms found in the literature that don't necessarily find the optimal solution to the tree problem, but do find the answer in a shorter computing time. We then show how we find the optimal solution using integer programming, and use the results to find the commonalities in these optimal solutions. Our contribution in this work is a rigorous study of theoretical aspects of commonalities of optimal solutions which can be used to create a better heuristic."]},{"key":"dc:title","label":"Title","values":["Optimality of Minimum Power Broadcasting in Wireless Ad Hoc Networks"]}]}],"canonical_facts":{"dc:creator":["O'Brien, Austin"],"dc:date.available":["2025-05-30T07:00:00Z"],"dc:date.created":["2009-01-01T08:00:00Z"],"dc:description.abstract":["In the current state of technology, the focus on wireless networks is higher than ever before. It is considered standard that laptops and mobile phones have wireless functionality. It is necessary to keep the battery of these devices alive as long as possible. Some networks, for example wireless ad hoc networks where infrastructures do not exist, rely on ability of all devices to maintain functionality in order to keep the life of the entire network alive. For unicast communication, the shortest path will find an optimal solution which cannot be applied to broadcast or multicast communications. In order to maintain battery life, it is important to find the optimal tree structure that uses the least amount of total power to reach all nodes in the tree. In this thesis, we review algorithms found in the literature that don't necessarily find the optimal solution to the tree problem, but do find the answer in a shorter computing time. We then show how we find the optimal solution using integer programming, and use the results to find the commonalities in these optimal solutions. Our contribution in this work is a rigorous study of theoretical aspects of commonalities of optimal solutions which can be used to create a better heuristic."],"dc:identifier":["https://openprairie.sdstate.edu/etd2/1609"],"dc:title":["Optimality of Minimum Power Broadcasting in Wireless Ad Hoc Networks"],"thesis:degree_discipline":["Electrical Engineering and Computer Science"],"thesis:degree_level":["Thesis - University Access Only"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T09:05:30Z"}