# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## Part I Introduction
Moreover, linear optimization forms the basis of _non-linear optimization_ and other advanced optimization types like _mixed integer problems_ and a large number of WSN problems can be formulated as linear optimization problems. In the linear optimization part, we explain classical special structured problems like _minimum spanning tree_, and _network flow_ problems as these seem to us to be highly useful when it comes to WSNs. We state our own examples of how these classical linear special structured problems can be used to model, and hence solve, design problems in WSNs. Nonlinear programming also receives some good attention in this tutorial paper we focus on its theoretical concepts and present some of the different methods available in the OR literature. Finally, for part II of the paper, we discuss _decomposition_ solution schemes, which are suitable for linear or non linear optimization problems. Decomposition schemes are attractive for WSNs, which are mainly of ad-hoc nature i.e., no central controller responsible for managing the resources for communications purposes, and have been used in some of the papers we consider in this tutorial. Being able to decompose the optimization problem into a number of smaller ones that can be solved separately by each sensor node, would be highly desirable to reduce the computational effort compared to centrally solving the problem. Since we target researchers who  
Figure 1: Taxonomy of the wireless sensor network (WSN) design problems considered in this paper. are new in using optimization techniques, we strongly believe that part II of this paper is necessary to understand some of the techniques used in part III of this paper. Distributed algorithms are highly desirable since a sensor node has limited processing capabilities, and hence using one node to solve the problem would consume too much processing energy. Moreover after the problem is solved, the components of the solution specific to each node need to be transmitted to the respective nodes. For a centralized scheme, these transmissions will be from the solving node to all the nodes in the network, while in the distributed scheme these will only be to a subset of nodes (usually the neighbors only). Therefore the communication overhead in distributed algorithms are lower. We believe that in order to exploit the full strength of the extensive tools in the optimization literature, good formulation is necessary to reduce the design problem to one of the classical optimization problems for which those well studied solution techniques could be used. In this paper, such techniques are illustrated for the different design problems in WSNs mentioned earlier, for which we have selected a paper for each. One section is dedicated to explain each design problem which is further divided into subsections that emphasize on the following:  
* the system model and design objectives,
* problem formulation,
* any reformulation methods,
* solution methods,
* any important results,
* our comments on some or all of the above. The purpose of our observations and comments on some of the problems is to shed some light on the points that we believe should be taken into account in the future when using optimization techniques for solving WSN design problems. As much as we could we used similar notation and definitions to those used in the corresponding papers to make it easy for the reader to relate to them if they wish to get back to them for more details.