## 3 Upper Bounds on the Number of Channels
### Upper Bounds on the Number of Channels  
We then derive several upper bounds under different network settings in terms of the interference ratio \(r\). **Theorem 1**: _If there are \(n\) nodes in a planar area with the density \(D\) and each node is equipped with an antenna with the identical beamwidth \(\theta_{m}\), for any valid link set \(LS\) derived from the \(n\) nodes, the corresponding conflict graph \(G(LS)\) can be colored by using \(2D-1\) colors._  
**Proof. ** Consider link \(l_{ij}\) that consists of nodes \(X_{i}\) and \(X_{j}\), as shown in Figure 3. The interference region is denoted as two sectors with radius \(R_{i}\) and angle \(\theta_{m}\) (the gray area in Figure 3). From the definition of node density, each sector has at most \(D\) nodes. Other than nodes \(X_{i}\) and \(X_{j}\), there are at most \(D-1\) nodes in either sector. After we combine the nodes in the two sectors, the gray area contains no more than \(2D-2\) nodes excluding nodes \(X_{i}\) and \(X_{j}\). Suppose link \(l_{kl}\) is one of the links that conflicts with \(l_{ij}\). It is obvious that at least one node of that link, e.g., \(X_{k}\), should be in \(X_{j}\)'s interference region, the gray sector centered at \(X_{j}\) in Figure 3. At the same time, the antenna of \(X_{k}\) should be pointed to \(X_{j}\) if it can interfere with \(X_{j}\). Thus, \(X_{k}\)'s interference region must also cover \(X_{j}\). So, \(|X_{k}-X_{j}|\leq R_{i}\). Since the antenna beam of the other node \(X_{l}\) should be turned toward \(X_{k}\), it must also fall in the interference region of \(X_{j}\), as shown in Figure 3. Hence, \(|X_{l}-X_{j}|\leq R_{i}\). It seems that any link that conflicts with link \(l_{ij}\) must fall in the gray area representing the interference regions of nodes \(X_{i}\) and \(X_{j}\). However, consider the case that \(X_{k}^{\prime}\) and \(X_{l}^{\prime}\) form a link \(l_{kl}^{\prime}\) in Figure 3. \(X_{l}^{\prime}\) is outside the gray region of \(l_{ij}\), but \(X_{k}^{\prime}\) can interfere with \(X_{i}\) since its beam covers \(X_{i}\). So, a link conflicting with link \(l_{ij}\) must contain at least one node falling in the gray area. Figure 3: The Interference Region. Therefore, there are at most \(2D-2\) links that conflict with \(l_{ij}\). Hence, the maximum degree of the vertices of \(G\) is \(\Delta(G)\leq 2D-2\). From Lemma 1, the conflict graph can be colored by using \(2D-1\) colors. Theorem 1 can be applied to any settings of the interference ratio \(r\). When \(r\) is greater than 1, we can get tighter upper bounds. Specifically, we have the result when \(r=2\). **Theorem 2**: _When \(r=2\) and \(n\) nodes are distributed in a planar area with density \(D\), and each node is equipped with an antenna with the identical beamwidth \(\theta_{m}\), for any valid link set \(LS\) derived from those \(n\) nodes, the corresponding conflict graph \(G(LS)\) can be colored by using \(\frac{3}{2}D\) colors._  
**Proof. ** Without loss of generality, we assume \(R_{t}=1\) so \(R_{i}=2\). Since the number of nodes \(n\) is a finite number, the number of links derived from \(n\) is also a finite number. Given a finite number of links on the plane, we can always find a line, such that at least one node is on the line, and all the other nodes are on the right hand side of the plane (as shown in Figure 4). We denote the node on the line as \(X_{j}\), and the other node on the corresponding link \(l_{ij}\) is \(X_{i}\). Then we will calculate the number of links that may conflict with link \(l_{ij}\). Let us consider link \(l_{ij}\) consisting of two nodes \(X_{i}\) and \(X_{j}\) (as shown in Figure 5). For any link \(l_{kl}\) that interferes with node \(X_{j}\), at least one node of that link must fall in the interference range of \(X_{j}\). Thus, any interfering link must have an acute angle with link \(l_{ij}\). Therefore, we draw a line in parallel with the line segment \(X_{i}X_{j}\) and a line in parallel with the upper border of the interference region of \(X_{j}\) to bound those interfering nodes.