# High Throughput and Acceptance Ratio Multipath Routing Algorithm in Cognitive Wireless Mesh Network
## 2 Network Model and Problem Description
### Problem Description  
The problem of multi-path routing and spectrum allocation based on channel interference and reusability with the QoS constraints was investigated. For each new arriving wireless request, a primary path and a backup path were constructed simultaneously. In the backup path construction, a strategy based on channel interference and reusability was proposed to meet the following objectives: (1) when link failure occurs on the primary path, the backup path continues to transmit data to reduce the impact on the accepted wireless request, and improve the network throughput; and, (2) in the construction of the backup path, it is desirable to include a link with the interference to the primary path, and with interference, to a plurality of wireless request primary paths to save resources and to improve the acceptance rate of wireless requests and network throughput. Let \(\Delta=\{\gamma_{i}=(s_{i},d_{i},b_{i})\}\) be the set of wireless requests, where \(s_{i}\) and \(d_{i}\) represent the source and destination node of the wireless request \(\gamma_{i}\); and \(b_{i}\) represents the bandwidth constraint of the wireless request \(\gamma_{i}\). The primary path and backup path from the source node \(s_{i}\) to the destination node \(d_{i}\) constructed for the wireless request \(\gamma_{i}\) is denoted as \(\alpha(s_{i},d_{i})\) and \(\beta(s_{i},d_{i})\), respectively. **Definition 1**. : _Primary link, which means that for any one of the links (u,v), if (u,v) \(\in\alpha(s_{i},d_{i})\), then (u,v) is called the primary link._  
**Definition 2**. : _Backup link, which means that for any one of the links (u,v), if (u,v) \(\in\beta(s_{i},d_{i})\), then (u,v) is called the backup link._  
**Definition 3**. : _Idle link, which means that for any one of the links (u,v), if (u,v) \(\
otin\alpha(s_{i},d_{i})\cup\beta(s_{i},d_{i})\), then (u,v) is called the idle link._  
Any link (u,v) \(\in\) E can only be either the primary link, backup link, or idle link. Wireless links (u\({}_{1}\),v\({}_{1}\)) and (u\({}_{2}\),v\({}_{2}\)) that meet the following conditions will interfere with each other. (1) \(d(u_{1},u_{2})\leq I_{R}\), or \(d(u_{1},v_{2})\leq I_{R}\), or \(d(v_{1},u_{2})\leq I_{R}\), or \(d(v_{1},v_{2})\leq I_{R}\); (2) The two links are allocated the same channel, i.e., \(x_{(u_{1},v_{1})}=x_{(u_{2},v_{2})}\). The allocated channel set of links (u,v) is denoted as \(K(u,v)\), which is given by  
\[K(u,v)=K_{u}\cap K_{v} \tag{1}\]  
_I(u,v) represents the set of all the links that interfere with the link (u,v). If the link (u,v) is allocated a different channel, the I(u,v) is different. I(k,v) denotes the link set that interferes with the link (u,v) allocated the channel \(k\), which is given by  
\[I^{k}(u,v)=\{(u_{1},v_{1})|(u_{1},v_{1})\in I(u,v)\ \&\ x(u,v)=x(u_{1},v_{1})\} \tag{2}\]  
**Definition 4**. : _Interference degree, which means the number of links in the F(u,v)._  
\(\delta^{k}(u,v)\) denotes the primary link set that interferes with the link (u,v) allocated the channel \(k\), which is given by  
\[\delta^{k}(u,v)=\left\{(u_{1},v_{1})\Big{|}(u_{1},v_{1})\in I^{k}(u,v)\ \&\ x(u_{1},v_{1})\in\alpha(s_{i},d_{i})\right\}\ \gamma_{i}\in\Delta \tag{3}\]  
**Definition 5**. : _Primary link interference degree, which is the number of links in the set \(\delta^{k}(u,v)\)._  
\(\varepsilon^{k}(u,v)\) denotes the backup link set that interferes with the link (u,v) allocated the channel \(k\), which is given by  
\[\varepsilon^{k}(u,v)=\left\{(u_{1},v_{1})\Big{|}(u_{1},v_{1})\in I^{k}(u,v)\ \&\ x(u_{1},v_{1})\in\beta(s_{i},d_{i})\right\}\ \gamma_{i}\in\Delta \tag{4}\]  
**Definition 6**.