# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 4 Network Flow Programming Models
### Terminology  
The following are the main the terms used when referring to linear network problems [25]:  
1. **Nodes and Arcs**: The network flow model consists of nodes and arcs. In the context of modeling a problem, each node, shown as a circle, represents some aspect of the problem, such as a physical location, an individual worker, or a point in time. In WSNs it is commonly the sensor, or could refer to the sensor node in a number of discrete spacial positions if the sensor is mobile for example [3]. Arcs are directed line segments that generally pass from an origin node to a terminal  
Figure 3: Taxonomy of the relationships of Linear Programs (LPs), network flow programs (NFPs) and their special classical sub-classes [25]. Figure 2: Example of a network flow programming model. node, although in the case of external flow, an arc may be incident to only one node. If an arc does not have a direction, it is sometimes referred to as an edge. 2. **Arc Flow**: Flow is associated with the network, entering and leaving at the nodes and passing through the arcs. The flow in arc \(k\) is \(x_{k}\). When flow is conserved at the nodes, the total flow entering a node must equal the total flow leaving the node. The arc flows are the decision variables for the network flow programming model. 3. **External Flows**: The external flow at node \(i\), denoted by \(b_{i}\), is the flow that must enter node \(i\) from sources, or leave node \(i\) for destinations outside the network. A positive external flow enters the node, and a negative external flow leaves the node. In the network diagram in Figure 2, the external flow is shown in square brackets adjacent to the node. External flows can model for e.g., the required data rate a sensor node should receive when it is the destination of a particular transmission. Also, they can model the source rate of a wireless sensor node that senses an external phenomena and converts it to electrical signal, then encodes it to a digital bit stream having specific bit rate. 4. **Upper and Lower Bound on Flow**: Flow is limited in an arc by lower and upper bounds. Sometimes the term capacity refers to the upper bound on flow. In wireless sensor networks, the capacity depends on the received signal to noise ratio (SNR) at the node on which the flow arc converges to, given the assumption that the network uses _time division multiple access_ (TDMA), and hence a noise limited system. If radio power control is considered in the problem, the capacity becomes a nonlinear logarithmic function in the power decision variable. This is an example of a possible non-linear network _flow and capacity_ problem in a WSN. The capacity of an arc \(n\) is given by \(c_{n}=\Delta B_{n}log_{2}\left(1+g_{n}p_{i}\right)\), where \(\Delta B_{n}\) is the bandwidth for the link represented by arc \(n\), \(g_{n}\) is the channel gain for the link and \(p_{i}\) is the transmitted power on the link, given that \(n\equiv(i,j)\). In the case power management is not considered, then the transmission power becomes constant instead of a decision variable, and the entire link capacity becomes constant. 5. **Cost**: The criterion for optimality is cost. Associated with each arc \(k\) is the cost per unit of flow \(c_{k}\). Negative values of \(c_{k}\) correspond to revenues. In WSNs, this can be equivalent to the battery energy expended per flow, where our flow would be in bits per second (bps). Therefore the cost has the units Joules-per-bit. In this case, we are assuming the power to be constant, i.e., we have constant arc capacities. A modulation scheme which decides on the number of bits per second is our decision variable on the flows. 6. **Gain**: The arc gain \(G_{k}\) multiplies the flow at the beginning of the arc to obtain the flow at the end of the arc. When a flow \(x_{k}\) is assigned to an arc, this flow leaves the origin node of the arc. The flow entering the terminal node is \(G_{k}x_{k}\). The arc's lower bound, upper bound, and cost all refer to the flow at the beginning of the arc.