{"id":{"repo_id":"vcu","oai_identifier":"oai:scholarscompass.vcu.edu:etd-1569"},"canonical_url":"https://search.dev.ndltd.org/etd/vcu/oai:scholarscompass.vcu.edu:etd-1569","repository":{"repo_id":"vcu","name":"Virginia Commonwealth University","base_url":"https://scholarscompass.vcu.edu/do/oai/"},"display":{"title":"ON RELAY NODE PLACEMENT PROBLEM FOR SURVIVABLE WIRELESS SENSOR NETWORKS","abstract":"Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks.","abstract_html":"Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks.","abstract_has_math":false,"creators":["Jung, Changyong"],"institution":null,"degree_name":"Doctor of Philosophy","degree_level":"Dissertation","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":["Yu Meng"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-12-03T08:00:00Z","date_published":"2013-12-03T08:00:00Z","updated_at":"2026-07-24T05:54:02Z","subjects":["Wireless Sensor Networks","Relay Node Placement","Survivability.","Engineering"],"languages":[],"rights":["© The Author"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarscompass.vcu.edu/etd/570"],"render_values":[{"text":"https://scholarscompass.vcu.edu/etd/570","href":"https://scholarscompass.vcu.edu/etd/570","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.25772/YAHD-QT19","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yu Meng"]},{"key":"dc:creator","label":"Author","values":["Jung, Changyong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2018-12-13T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Wireless Sensor Networks","Relay Node Placement","Survivability.","Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["© The Author"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://doi.org/10.25772/YAHD-QT19","https://scholarscompass.vcu.edu/etd/570"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks."]},{"key":"dc:title","label":"Title","values":["ON RELAY NODE PLACEMENT PROBLEM FOR SURVIVABLE WIRELESS SENSOR NETWORKS"]}]}],"canonical_facts":{"dc:contributor":["Yu Meng"],"dc:creator":["Jung, Changyong"],"dc:date.available":["2018-12-13T08:00:00Z"],"dc:description.abstract":["Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks."],"dc:identifier":["https://doi.org/10.25772/YAHD-QT19","https://scholarscompass.vcu.edu/etd/570"],"dc:rights":["© The Author"],"dc:subject":["Wireless Sensor Networks","Relay Node Placement","Survivability.","Engineering"],"dc:title":["ON RELAY NODE PLACEMENT PROBLEM FOR SURVIVABLE WIRELESS SENSOR NETWORKS"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy"]},"updated_at":"2026-07-24T05:54:02Z"}