A Topology Control Algorithm for Sensor Networks Based on Robust Optimization

Junfeng Qiao, Sanyang Liu and Wei Duan

International Journal of Distributed Sensor Networks, 2015, vol. 11, issue 1, 140709

Abstract: 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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2015/140709 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:11:y:2015:i:1:p:140709

DOI: 10.1155/2015/140709

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().