## 2 Network Model and Operation
### Time Schedule
#### 2.2.2 Space-Time Analysis  
In order to find a simple algorithm that in turn finds the optimal schedule of the string network, we start analysing a small network. Later on, in Section 3.1, the limitation on the packet generation rate of every node for queue stability will be established. The optimal schedules found for network sizes \(N=2\), 3, and 4 nodes are shown in Figure 4. The procedure to obtain the optimal schedule consists of applying Equations (2)-(6) to the nodes, trying to minimize the number of idle states, and looking for a periodic operation. It can be noted that for \(N=4\), slots 6 and 2 are equal, and the same will happen with 7-3, 8-4, and so on. Therefore, for \(N=4\), the frame length is \(T=4\). In this schedule, there are only four nodes in an idle state during the whole frame, achieving the busiest operation possible for this network topology. The optimal schedule found for \(N=4\) (see Figure 4) has a period of \(T=4\). It happens that the optimal frame length is also \(T=4\) for \(N>4\). The method to obtain \(Q^{(T)}\) can be extended to any network size, because of the regularity of the network structure (hop distance and conditions of the edge nodes). First, we must define a set of four column vectors \(v_{j}^{(i)}\) for each node \(j\) of the network, \(i\in\{0,1,2,3\}\):  
\[v_{j}^{(0)} =\Big{(}\ \big{[}\ j-1\ \ \ j-1\ \ \ -(j+1)\ \ \ -(j+1)\ \ \ \Big{]}\ \Big{)}^{\prime}\,, \tag{7}\] \[v_{j}^{(1)} =\Big{(}\ \big{[}\ -(j+1)\ \ \ j-1\ \ \ j-1\ \ \ -(j+1)\ \ \ \Big{]}\ \Big{)}^{\prime}\,,\] (8) \[v_{j}^{(2)} =\Big{(}\ \big{[}\ -(j+1)\ \ \ -(j+1)\ \ \ j-1\ \ \ j-1\ \ \ \Big{]}\ \Big{)}^{\prime},\] (9) \[v_{j}^{(3)} =\Big{(}\ \big{[}\ \ j-1\ \ \ -(j+1)\ \ \ -(j+1)\ \ \ j-1\ \ \ \Big{]}\ \Big{)}^{\prime}\,, \tag{10}\]  
where the superscript'stands for transpose. Note that, in this case, \(v_{j}^{(i)}\) represents column vectors, i.e., \(j\) is the column index of matrix \(Q^{(T)}\). It is easy to see that two elements of each vector Equations (7)-(10) will always be negative. These elements represent nodes in a reception state. Finally, the optimal schedule for a string network of \(N\) nodes, which we denote by \(Q^{(4)}_{opt,4\times N}\), is obtained using vectors Equations (7)-(10) in the columns of the \(Q\) matrix corresponding to the node number in the subscript \(j\) of each vector \(v_{j}^{(i)}\), and the superscript \(i=j\) modulo 4. That is, the optimal schedule is:  
\[Q^{(4)}_{opt,\ 4\times N}=\Big{[}\ \ v_{1}^{(1)}\ \ \ v_{2}^{(2)}\ \ \ v_{3}^{(3)}\ \ \ v_{4}^{(0)}\ \ \ v_{5}^{(1)}\ \ \ v_{6}^{(2)}\ \ \ \cdots\ \ \ v_{N}^{(N\ \text{mod 4})}\ \ \Big{]}, \tag{11}\]  
where, in the last vector \(v_{N}^{(N\ \text{mod 4})}\), the negative elements must be replaced by zero because node \(N\) never receives from another node and, instead, it will remain in the idle state. For example, Figure 5 shows the optimal schedule for a string network of size \(N=5\), which is given by:  
Figure 4: Examples of efficient schedules for different network sizes (\(N\)). Matrix \(Q^{(T)}\) is provided for each case, and the first frame is highlighted in a dashed line. The perfect schedule is only possible for \(N=2\), with period \(T=1\). If \(N=3\), the solution is trivial, with period \(T=2\). For \(N=4\), the optimal solution is shown (\(T=4\)). A geometric interpretation can be given to find and to prove this optimal schedule. Let us imagine a 2D space-time lattice, where the node number is in the \(x\)-axis and the time slot number is in the \(y\)-axis. The problem can be formulated as to set the state (Tx/Rx/Idle) of every node in that 2D space-time lattice, with two constraints: minimize the number of idle states and be periodic in time. We call the pattern the set of states that is repeated in space and time. A final consideration concerns the size of the pattern: the minimum size is \(3\times 3\), because \(2\times 2\) is trivial, and does not lead to a valid solution when it is repeated within the 2D lattice. The proposed procedure to find the best scheduling includes three steps.