Abstract:
The design of a Wireless sensor network (WSN) involves the optimal deployment and activity scheduling of the sensors as well as optimal deployment or routing of sinks and optimal routing of data flows. In this thesis, we first attempt to reflect the limited nature of the mobile sink by considering nonzero sink travel times and taking the data accumulated during the sink travel time into account. The total sink travel time is considered as a part of the network lifetime. We provide two mixed integer linear programming (MILP) models that are flexible enough to handle multiple sink tours as well as a hop limited data routing protocol in which data is routed from sensors towards the sink through the shortest paths including at most a predefined number of hops. We propose heuristic procedures for the solution of the MILP models and show the importance of considering nonzero sink travel times by numerical experiments. An extension to these MILP models that possess a framework with multiple mobile sinks is also developed and it is demonstrated that sink travel times can be neglected for multiple sinks. Later on, we develop several MILP models which integrate sensor placement, activity scheduling and data routing issues with the static sink placement or mobile sink routing design issues. The breadth of the integration changes from the integration of the sink routing problem with the data routing problem to the integration of the sensor placement, activity scheduling, sink routing problems with data routing problems. We study the effect of the integration ofWSN design issues by comparing the objective value of the models on a large set of randomly generated problem instances. We also devise heuristics and a branch-and-price algorithm for the solution of the proposed MILP models and empirically test their accuracy and efficiency on a large set of test instances.
