# A Simulation of Contact Graph Routing for Mars-Earth Data Communication
## 2 Model of CGR
### Arrangement of the Contact Graph  
If we plan to construct a contact graph using \(n_{1}\) rovers on Mars, \(n_{2}\) relay satellites, and \(n_{3}\) DSN antennas on Earth, it means that we define three groups for our CGR: \(n_{1}\) nodes for the group of rovers, \(n_{2}\) nodes for relay satellites, and \(n_{3}\) DSN antennas on Earth. So, we have \(n_{1}+n_{2}+n_{3}=n\) nodes. Any node in each group connects to any node in the other two groups. No connection exists inside a group. We define a general graph of \(n\) nodes first, because this model construction is open to any modification in the number of nodes and the connectivity arrangement among nodes. Later, we make some assumptions to make the contact graph that we aim for. We use the following formula to find the total number of combinations of any two nodes, defining routes \(r\) from the total \(n\) nodes without considering the order. \[N=\binom{n}{2}=\frac{n!}{2!(n-2)!}=\frac{1}{2}n(n-1). \tag{1}\]  
An illustration of all combinations of every two nodes from the total \(n\) nodes can be seen in Table 1. It is important to define route labels \(r\) so they can be used to identify the pairing of routes. In Column 1 of Table 1, routes \(1\to 2\), \(1\to 3\), \(1\to 4\), up to \(1\to n\), are, respectively, labeled as \(r=1,2,\ldots,n-1\). We define \(I_{1}=n-1\). In Column 2, route \(2\to 3\) is labeled as \(r=I_{1}+1=n\), \(2\to 4\) as \(r=I_{1}+2=n+1\), and so on until route \(2\to n\) as \(r=I_{2}=I_{1}+n-2=2n-3\). We specifically assign \(r=I_{s},s=1,2,\ldots,n-1\) as the last label of columns, which is formulated as follows. \[I_{s}=\sum_{k=1}^{s}(n-k). \tag{2}\]  
Note that \(I_{n-1}=N\). These labels are useful for defining a vector _ids_ whose size \(n-1\) and contains the last label of all non-empty columns in Table 1.  
\[\textit{ids}=(0,I_{1},I_{2},I_{3},\ldots,I_{n-2})=\bigg{(}0,n-1,2n-3,3n-6, \ldots,\frac{1}{2}(n-2)(n+1)\bigg{)}. \tag{3}\]We generate an access matrix with size \(n\times n\) in Table 2, which means there are \(n\times n\) connections. However, there are only a few connections that will be used. The connection is only between a couple of nodes from different groups, which are between Groups 1 and 2, and between Groups 2 and 3. Due to a limitation, there is no connection between Groups 1 and 3. The numbers of available connections between these groups are, respectively, \(n_{1}n_{2}\) and \(n_{2}n_{3}\), so the total number of connections is \(n_{2}(n_{1}+n_{3})\). We now define nodes 1 and 2 as rovers PR and CR, nodes \(3,4,5\), and 6 as relay satellites MRO, ODY, TGO, and MVN, respectively, and nodes \(7,8,9\) and \(9\) as antennas USA, SPN, and AUS, respectively. So, we need 9 nodes for our Contact Graph Routing. Table 2 shows the access matrix, where its entries \(c_{ij}\geq 0\) indicate the storage capacity of satellites. Using Equation (1), for \(n=9\) nodes, we calculate the number of edges (between two nodes) from nine nodes, which is \(N=36\). Two nodes of the rovers can connect to four nodes of the relay satellites, but they cannot connect directly to the last three nodes of the DSN antennas. The very long distance between Mars and Earth does not allow it. The relay satellites can connect to the DSN antennas. So the size of the generated access matrix is 9, but it is sparse, with only 20 non-zero entries, so we have a contact graph of nine nodes with only 20 edges. The usage of the access matrix is important for the indexation of matrix \(x\), which is defined as follows. \[x(p,r,d,t)=\left\{ \begin{array}{rl}dt_{d}(t)&\text{if the route $r$ is chosen,}\\ 0&\text{if not.}\end{array} \right. \tag{4}\]  
where \(p\) is the number of steps between groups, \(r\) is the label of route defined from the combination of nodes, \(d\) is the index of the data packet being sent at time \(t\), and \(dt_{d}(t)\) is the size of data packet \(d\) being sent at time \(t\). We have the values \(p=1,2\), where step 1 is from a rover in Group 1 to a satellite in Group 2, and step 2 is from a satellite in Group 2 to a