# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 11 Routing in Multi-hop Single Immobile Sink for Different Objectives under Distance Uncertainties
### Formulations for the Three Problems  
A brief description of each of the three different optimization problems that were given in [6] is as follows:  
1. _The Minimum Energy Problem:_ * Decision variables: are the continuous variables \(f_{ij}\) which are the number of bytes transmitted on a link from node \(i\) to node \(j\). * Objective function: is a continuous linear objective function in \(f_{ij}\) which is the sum of the transmission and reception normalized energies of all nodes in the network. The objective is to minimize that aggregate energy function. * Constraints: the first constraint is a minimum data transmission requirement constraint that requires the aggregate data transmitted from all nodes to the sink node, \(n+1\) to be greater than a minimum number of bytes. The second and third constraint sets are conservation of flow constraints that require the difference between the amount of data bytes transmitted and received by a node to be less than the available data bytes at the node and greater than zero. The variables have non-zero constraints also. 2. Decision variables: are \(f_{ij}\) which are the number of bytes transmitted on a link from node \(i\) to node \(j\). * Objective function: maximizes the data transmitted to the sink node. It was given as the sum of data bytes \(f_{ij}\) transmitted from each node \(i\) to the sink node \(n+1\) on the arcs \((i,n+1)\). It is a continuous linear objective function. * Constraints: Besides the conservation of flow and non-negativity constraints in _Minimum Energy Problem_, there is a set of energy limitation constraints for each node, that guarantees that the the sum of transmitted and received energy for each node does not exceed the available energy of the node, i.e., \[\sum_{j|(i,j)\in A}f_{ij}\left(1+\beta d_{ij}^{2}\right)+\sum_{j|(i,j)\in A}f_ {ij}\leq E^{i}\forall i\in N.\] (26) Note that in [6], the energy is normalized such that \(E^{i}\) is the number of bytes that could be transmitted with the available energy and the left hand side of the constraint is the amount of bytes transmitted for an expended amount of energy. All constraints are linear and hence the problem is a linear program ignoring the uncertainties. 3. _Maximum Lifetime Problem_:
* Decision variables: are \(f_{ij}\) which are the number of bytes transmitted on a link from node \(i\) to node \(j\) and \(T\) which is the variable represents the lifetime of the network. * Objective function: maximize the lifetime \(T\) of the network which is defined as the lifetime of the first sensor whose battery gets depleted, i.e., \(T=min\left\{T_{1},T_{2},...,T_{n}\right\}\). * Constraints: Conservation of flow and non-negativity constraints typical to those in _Minimum Energy Problem_, in addition a quadratic constraint with bilinear terms that guarantees that the energy expended by transmission of a node \(i\) does not exceed its available energy, this is given by: \[T\left(\sum_{j|(i,j)\in A}f_{ji}+\sum_{j|(j,i)\in A}f_{ji}\left(1+\beta d_{ij} ^{2}\right)\right)\leq E^{i}\] (27) where the left hand side This gives a quadratically constrained program, which is transformed to a linear program by substituting the variable  
The paper presented two general convex sets for the uncertainty region, these are polyhedral sets and ellipsoidal sets. For both types of uncertainty sets, the three deterministic optimization problems that were considered were formulated to their robust counterparts. The type of optimization problems obtained for the three cases are as follows:  
1. Polyhedral uncertainty sets: Using LP duality, it was shown that optimization problem remains as a linear program with additional variables and constraints. 2. Ellipsoidal sets: Using a known closed form solution for an embedded ellipsoidal optimization subproblem with respect to the uncertainty variables, the robust optimization problem becomes a conic convex problem that can be solved by interior point methods in polynomial time.