## 4 Network Model
### Space-time Network  
To construct  
\(V_{p}\) contains all the vehicular nodes at all time periods. In this way a time expanded network is created of the time horizon of interest. Figure 4a shows the space-time network generated for a single UT and four vehicles. In this figure, vehicles traveling in one direction are shown to aid visualization. It is interesting to note that the space-time network has been considered in the past as the tool to study the performance of routing algorithms in DTNs. In [28] the authors consider the space-time network for sparse networks and suggest the store-carry and forward technique for routing messages. In a similar manner, the work in [29] considers the space-time network with deterministic mobility such that the contact times between nodes can be estimated. Operating on this graph they study the performance of their network instances under different objectives. The clear distinction we try to make here is that for our case, connectivity is not an issue as all nodes can communicate directly with the BS and informed routing decisions can be made. Therefore the space-time network under consideration is not restricted by the contact opportunities as is the case with DTNs. Instead here a densely populated network is considered. Figure 4: Space-time network for the network model under investigation. (a) The time-expanded network captures node positions at future time instances. Node replication is done every \(\tau\) units of time; (b) Connected graph with both transmission and store-carry and forward links. On this network we define the graph \(G=(V,L)\) where \(V=\mathcal{M}\cup V_{p}\cup BS\) is the set of nodes and \(L\) is the set of links containing two subset defined as follows:  
* set of links that represent transmission of messages between two communicating nodes. Communication can be between vehicles, users and the BS;
* set of links where messages are carried from one time period to the next by a mobile node, no communication occurs. Note that in the space-time network, node replication is done every \(\tau\) units of time which is the time needed to transmit a single information message as expressed by Equation (2). As a result, the flow on links in \(L_{1}\) can only take binary values. Consider for example the link \((\mathrm{VR}_{1},1)\mapsto(\mathrm{VR}_{2},2)\) in Figure 4b with the tail of the link showing the node and time at which the transmission started and the head of the link showing the destination node and transmission termination. By utilizing this link, a single message is forwarded from \(\mathrm{VR}_{1}\) to \(\mathrm{VR}_{2}\) during the interval \(\tau\) to \(2\tau\). On the other hand, link \(\mathrm{UT}_{1}\mapsto(\mathrm{VR}_{1},2)\) crosses over 2 time periods. In this case, the users buffers a message for 1 time period and transmits the message during the second time interval. For links in \(L_{2}\), a relay node buffers information messages and carries them at consecutive time periods using the actual node mobility (for example, link \((\mathrm{VR}_{1},1)\mapsto(\mathrm{VR}_{1},2)\) in Figure 4b). For all links, we define the flow variable \(x_{ij}\in\mathbf{Z}\) to be the flow on link \(i\mapsto j\in L\). Further, the capacity \(u_{ij}\) for all links is defined as follows:  
\[u_{ij}=\left\{ \begin{array}{ll}1&\mathrm{i}\mapsto\mathrm{j}\ \in\ \mathrm{L}_{1}\\ \infty&\mathrm{i}\mapsto\mathrm{j}\ \in\ \mathrm{L}_{2}\end{array} \right. \tag{3}\]  
Note that for links in \(L_{1}\) the energy consumption expressed in Equation (2) is a non-linear function with respect to the transmission distance. However for the binary values that the flow variable \(x_{ij}\) can attain, the multiplicative cost \(x_{ij}f_{ij}\) gives the correct energy consumption values. Furthermore, since one unit of flow should leave each user and reach the BSC, we define the supply and demand for all nodes \(i\in V\) as follows:  
\[b(i)=\left\{ \begin{array}{ll}+1&\mathrm{i}\ \in\ \mathcal{M}\\ -M&\mathrm{i}\ =\ \mathrm{BS}\\ 0&\mathrm{otherwise}\end{array} \right.