# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 4 Network Flow Programming Models
### Special Classes of NFPs
#### 4.2.1 Transportation Problem  
This type of network has a _bipartite structure_, that is the nodes are grouped in two sets and the arcs can only be between nodes in different sets. To understand this class of problems we explain it by an example from [25]. Consider the network in Figure 4a. This problem deals with a set of sources, labeled S1, S2, and S3 at which supplies of some commodity are available, and a set of destinations, labeled D1, D2, and D3 where the commodity is demanded. Shipping costs are specified in the transportation tableau in Figure 4b, and the supply and demand data are shown outside the tableau. Supply and demand data are shown along the margins of the tableau and are denoted symbolically as \(s_{i}\) and \(d_{j}\), respectively, where \(i=1,...,m\) and \(j=1,...,n\). In a classical transportation problem, the problem is _balanced_, which means that the total supply always equals the total demand--i.e \(\sum_{i}^{m}s_{i}=\sum_{j}^{n}d_{j}\). This is the case in Figure 4, and is a sufficient condition for feasibility. Unbalanced instances of the problem can always be put into this form with the addition of a dummy supply point (call it m + 1) when demand exceeds supply, or a dummy demand point (call it \(n+1\)) when supply exceeds demand. If \(\Delta\) denotes the excess, we set \(s_{m+1}=\Delta\) or \(d_{n+1}=\Delta\) depending on the imbalance. The **transportation simplex algorithm** is a variant of the simplex algorithm that exploits the structure of the transportation tableau to reduce the computational effort as compared to the generic simplex. Actually, applying the simplex algorithm to a transportation problem would be inefficient as we could encounter _degenerate_**bfs**[25]. In this case, there is a chance of _cycling_ to occur, which is a situation in which the the algorithm moves from one **bfs** to other adjacent ones that yield the same objective function value and then comes back to the one it started from. i.e., \(A-B-D-C-A-B-D-C-A.....\) The algorithm then gets stuck there until a time limit or iteration limit is hit. In transportation simplex, an initial **bfs** can be obtained by the _[PERSON]'s method_, the _Northwest corner method_ or _[PERSON]'s method_[24], both are much efficient for a transportation problem when compared to the Big M or the dual phase simplex methods. If the researcher is able to recognize that a particular design problem in WSNs can be formulated into a transportation problem, they can benefit from the more efficient transportation simplex instead of using the normal simplex. Good and clear explanation on how the transportation simplex operates and how it exploits the transportation tableau's special structure can be found in [24; 25]. The implementation of of the transportation simplex is easy, as it involves only addition and subtraction operations, a C++ implementation code for the algorithm can be found in [32]. **Example for a Possible Application to WSN**: This class of problems can be used to formulate a simple WSN network where there are three source sensors S1, S2, and S3, that sense different things, like temperature, humidity and pressure. There are possibly also the sink nodes D1, D2 that connect the WSN to another network, the Internet possibly. The arcs would represent the  
Figure 4: An illustrative example of a simple transportation problem. (**a**) NFP model of the transportation problem; (**b**) Tableau of a transportation problem. possible direct transmissions each source sensor node can make to any of the three sinks. The presence of a possible arc could depend on the radio transmission power level, meaning that the sink at which a particular arc is incident on is in the transmission range of the source node. The costs of the arcs can represent the battery energy that would be expended per bit of flow on each arc. This is directly related to the distance between the sensors and the sinks.