A Topology Control Algorithm for Sensor Networks Based on Robust Optimization
In recent years, wireless sensor networks have been widely used in data acquisition, surveillance, event monitoring, and so forth. Topology control is an important issue in designing sensor networks. Considering the uncertainty of distance between nodes, a distributed topology control algorithm name...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-01-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2015/140709 |
| _version_ | 1826821206339223552 |
|---|---|
| author | Junfeng Qiao Sanyang Liu Wei Duan |
| author_facet | Junfeng Qiao Sanyang Liu Wei Duan |
| author_sort | Junfeng Qiao |
| collection | DOAJ |
| description | In recent years, wireless sensor networks have been widely used in data acquisition, surveillance, event monitoring, and so forth. Topology control is an important issue in designing sensor networks. Considering the uncertainty of distance between nodes, a distributed topology control algorithm named as LRMST, which is based on the local minimum spanning tree (LMST) algorithm, is proposed by applying the 0-1 robust discrete optimization theory. Firstly, when only the cost coefficients are subject to uncertainty, it is proved that the robust counterpart of the 0-1 discrete optimization problem on n variables can be solved by solving at most n + 1 - Γ deterministic problems, where Γ denotes the number of cost coefficients which change in an uncertainty set. Then we present a robust model for the MST problem under distance uncertainty. According to the proved conclusion, an algorithm is proposed to obtain the robust solution of uncertain MST problem by solving only one deterministic MST problem, after which LRMST algorithm is designed when the distance between nodes is affected by uncertainty. Simulation results show that LRMST algorithm tends to select some edges whose estimated distance is slightly longer and obtains the robustness when the distance is uncertain at the expense of less optimal value compared with LMST algorithm. |
| first_indexed | 2024-03-12T05:50:47Z |
| format | Article |
| id | doaj.art-b34f6fd4fa16423fac554507e4309297 |
| institution | Directory Open Access Journal |
| issn | 1550-1477 |
| language | English |
| last_indexed | 2025-02-16T06:42:20Z |
| publishDate | 2015-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj.art-b34f6fd4fa16423fac554507e43092972025-02-03T06:43:15ZengWileyInternational Journal of Distributed Sensor Networks1550-14772015-01-011110.1155/2015/140709140709A Topology Control Algorithm for Sensor Networks Based on Robust OptimizationJunfeng QiaoSanyang LiuWei DuanIn recent years, wireless sensor networks have been widely used in data acquisition, surveillance, event monitoring, and so forth. Topology control is an important issue in designing sensor networks. Considering the uncertainty of distance between nodes, a distributed topology control algorithm named as LRMST, which is based on the local minimum spanning tree (LMST) algorithm, is proposed by applying the 0-1 robust discrete optimization theory. Firstly, when only the cost coefficients are subject to uncertainty, it is proved that the robust counterpart of the 0-1 discrete optimization problem on n variables can be solved by solving at most n + 1 - Γ deterministic problems, where Γ denotes the number of cost coefficients which change in an uncertainty set. Then we present a robust model for the MST problem under distance uncertainty. According to the proved conclusion, an algorithm is proposed to obtain the robust solution of uncertain MST problem by solving only one deterministic MST problem, after which LRMST algorithm is designed when the distance between nodes is affected by uncertainty. Simulation results show that LRMST algorithm tends to select some edges whose estimated distance is slightly longer and obtains the robustness when the distance is uncertain at the expense of less optimal value compared with LMST algorithm.https://doi.org/10.1155/2015/140709 |
| spellingShingle | Junfeng Qiao Sanyang Liu Wei Duan A Topology Control Algorithm for Sensor Networks Based on Robust Optimization International Journal of Distributed Sensor Networks |
| title | A Topology Control Algorithm for Sensor Networks Based on Robust Optimization |
| title_full | A Topology Control Algorithm for Sensor Networks Based on Robust Optimization |
| title_fullStr | A Topology Control Algorithm for Sensor Networks Based on Robust Optimization |
| title_full_unstemmed | A Topology Control Algorithm for Sensor Networks Based on Robust Optimization |
| title_short | A Topology Control Algorithm for Sensor Networks Based on Robust Optimization |
| title_sort | topology control algorithm for sensor networks based on robust optimization |
| url | https://doi.org/10.1155/2015/140709 |
| work_keys_str_mv | AT junfengqiao atopologycontrolalgorithmforsensornetworksbasedonrobustoptimization AT sanyangliu atopologycontrolalgorithmforsensornetworksbasedonrobustoptimization AT weiduan atopologycontrolalgorithmforsensornetworksbasedonrobustoptimization AT junfengqiao topologycontrolalgorithmforsensornetworksbasedonrobustoptimization AT sanyangliu topologycontrolalgorithmforsensornetworksbasedonrobustoptimization AT weiduan topologycontrolalgorithmforsensornetworksbasedonrobustoptimization |