Archives and Documentation Center
Digital Archives

Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks

Show simple item record

dc.contributor Ph.D. Program in Industrial Engineering.
dc.contributor.advisor Altınel, İ. Kuban.
dc.contributor.advisor Aras, Necati.
dc.contributor.author Türkoğulları, Yavuz Boğaç.
dc.date.accessioned 2023-03-16T10:35:18Z
dc.date.available 2023-03-16T10:35:18Z
dc.date.issued 2010.
dc.identifier.other IE 2010 T87 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13542
dc.description.abstract A wireless sensor network consists of distributed autonomous tiny electronic devices called sensors. They have limited energy and capability for sensing, data processing and communication, but they can collectively behave to provide an effective network that monitors a region, and transmit information to gateway nodes called sinks. In most of the applications, the network must operate for long periods of time, so the available energy resources of the sensors must be managed efficiently. In this thesis we first develop mixed-integer linear programming models to maximize network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data routes and activity schedules of the deployed sensors over a finite planning horizon subject to coverage, flow conservation, energy consumption and budget constraints. Then, we propose valid inequalities, which we use with a new branch-and-price algorithm to solve the problem exactly. Although they provide stronger linear programming relaxations and thus increase the quality of the formulation, the size of the networks for which the model can be solved exactly is very limited. Hence, we develop approximate solution heuristics using techniques such as the Lagrangean relaxation, column generation and a greedy selection criterion. Based on the computational experiments we can say that they are accurate and efficient. The minimum cost coverage problem, which consists of the deployment of sensors over a sensor field modeled as a set of finite points so that total cost is minimized subject to the coverage requirements, generalizes the famous set covering problem. We provide a polyhedral analysis of this general problem, which has not been studied very much previously. We develope a procedure that generates valid inequalities and a sufficient condition for facet definition, and a cutting plane. Experiments show that the proposed valid inequality cuts of the fractional optimum and improve considerably the linear programming relaxation lowerbound. Finally, we revise the convergence proof of the deflected subgradient algorithm that uses conditional subgradients and suggest some refinements.
dc.format.extent 30cm.
dc.publisher Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2010.
dc.relation Includes appendices.
dc.relation Includes appendices.
dc.subject.lcsh Wireless sensor networks.
dc.title Optimal placement, scheduling and routing to maximize lifetime in wireless sensor networks
dc.format.pages xvii, 177 leaves;


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Digital Archive


Browse

My Account