## 4 Problem Formulation for Cross-Layer Design
### Problem Formulation  
In this section, the joint routing and resource allocation problem is modeled as a MDP. The MDP can be represented as a tuple \((S,A,T,R)\), where \(S\) denotes the set of environment states; \(A\) is the set of candidate actions at each state; \(T=\left\{P_{s,s^{\prime}}(a)\right\}\) is the set of state transition probabilities, where \(P_{s,s^{\prime}}(a)\) is the state transition probability from state \(s\) to \(s^{\prime}\) when taking action \(a\) in state \(s\); and \(R:S\times A\mapsto\Re\) specifies the reward at \(s\in S\) when taking action \(a\in A\). It is necessary to identify the states of SU nodes, actions of the agent and the associate rewards:  
1. States  
For a given \(SU_{i}\) node, the network state at time slot \(t\) is denoted as \(s_{t}=\{n_{i},\psi_{i}\}\), where \(n_{i}\in\{0,1,\ldots,N-1\}\) represents the index of the current SU node and \(\psi_{i}\) is the responsibility rating of \(SU_{i}\). Since we consider a large-scale CRN with a great deal of transmission power levels, the size of state space is particularly large.  
2. ActionsA cross-layer scheme is studied that jointly addresses routing, spectrum access and power assignment problem in CRN. We denote \(a_{t}=\left\{n_{j},\ c_{i},p_{\psi_{i}}\right\}\in A\) as candidate actions of the \(SU_{i}\) node at time slot \(t\), where \(n_{j}\in J\subset\left\{0,1,\ldots,N-1\right\}\) is the selection of next-hop SU node, and \(J\) is the neighboring nodes set of \(n_{i}\cdot c_{i}\in C_{i}\) represents the operating channel, \(p_{\psi_{i}}\) denotes the transmit power described in (14). Since the size of \(J\) and \(C_{i}\) is relatively small, and \(p_{\psi_{i}}\) is a fixed value corresponding to \(\psi_{i}\), the action space is limited for each SU.  
(3) Rewards  
Our objective is to reduce the end-to-end delay while improving the energy efficiency in multi-hop CRN. \(\tau_{i}\) in (8) represents one-hop transmission delay, and the Power Consumption Ratio (PCR) is proposed to describe the power efficiency:  
\[\epsilon_{i}=\left.p_{\psi_{i}}\right/W\log_{2}\left(1+\frac{h_{ijc}p_{\psi_{ i}}}{\sigma+\phi_{ijc}^{\Pi l}}\right) \tag{16}\]  
PCR denotes the energy consumption when getting per unit throughput. The reward \(r_{t}\) assesses the immediate return incurred due to the assignment of action \(a_{t}\) at state \(s_{t}\). The considered reward function is:  
\[r_{t}=-(\tau_{i}+\alpha\epsilon_{i}) \tag{17}\]  
where \(\alpha\) is the proportional coefficient to make \(\tau_{i}\) coincide with order of magnitude in \(\epsilon_{i}\). Our algorithm aims to maximize this reward so that the end-to-end delay and power consumption are below the thresholds.  
\(n_{i}\) is the index of current SU nodes. It is only decided by the previous SU nodes and is irrelevant to the historical nodes. In addition, the current responsibility rating is relevant to the previous \(\psi_{i}\) as shown in (14) and has nothing to do with the historical states. So the joint design problem can be modeled as a Markov process. Furthermore, the model-free reinforcement learning is applied in this paper, in which an accurate model for the environment is unnecessary, so that it is unnecessary to calculate the state transition probabilities. We take a minor example consisting three SU nodes and two levels of transmission power. The state transition diagram is shown as following.  
Figure 3 shows a simplest CRN containing three nodes. \(n_{0}\) is the source node, \(n_{1}\) is the relay node and \(n_{2}\) is the destination node. \(s_{4}\) and \(s_{5}\) are the terminal states.