## 5 Routing over the Hierarchical Virtual Topology
### Overview  
In this section, we give an overview of our routing algorithm. Figure 3 shows an example of a three-tiered virtual topology. Each node belongs to one module in each tier. For example, node \(a\) belongs to module \(M_{\text{C}}^{1}\) in the first tier, module \(M_{A}^{2}\) in the second tier and module \(M_{A}^{3}\) in the third tier. The end nodes of each higher-tier link are assigned to physical nodes. In Figure 3, the end nodes of the first-tier link (\(M_{A}^{1}\),\(M_{\text{C}}^{1}\)) are assigned to nodes \(g\) and \(c\), and the end nodes of the second-tier virtual link (\(M_{A}^{2}\),\(M_{B}^{2}\)) are assigned to nodes \(k\) and \(m\). In this paper, as mentioned in Section 3, the VWSN provider calculates the routing tables and sends them along with the traffic patterns to each node. At this time, the VWSN provider informs source nodes of which modules the corresponding destination node belongs to in each tier. Then, source nodes can refer to the information when sending a data packet to their destination nodes.  
Below, we show a method for choosing a next-hop node, which we call a forwarding node, when node \(s\) sends a data packet destined for node \(d\).  
1. Node \(s\) checks the highest tier \((N)\) in which nodes \(s\) and \(d\) belong to different modules. Then, node \(s\) sets the initial destination module as the \(N\)-th-tier module to which node \(d\) belongs.
2. Descending from tier \(N\), node \(s\) chooses a forwarding module in each tier as follows. 1. Node \(s\) chooses a neighboring \(N\)-th-tier forwarding module (\(M_{f}^{N}\)) toward the \(N\)-th-tier destination module according to the path weight. 2. Node \(s\) chooses an \((N-1)\)-th-tier module (\(M_{u}^{N-1}\)) that belongs to the same module as node \(s\) in the \(N\)-th tier and is connected to an \((N-1)\)-th-tier module (\(M_{b}^{N-1}\)) belonging to \(M_{f}^{N}\).  
3. Node \(s\) sets the destination module to \(M_{a}^{N-1}\) when node \(s\) does not belong to \(M_{a}^{N-1}\). Otherwise, node \(s\) sets the destination module to \(M_{b}^{N-1}\), which is connected to \(M_{a}^{N-1}\) and belongs to \(M_{f}^{N}\).
3. By iterating Process 2 until \(N\) becomes zero, node \(s\) can find a forwarding node.  
In this example, node \(s\) and node \(d\) belong to the module, \(M_{A}^{3}\), in the third tier. Therefore, node \(s\) chooses a forwarding module from the second tier. At first, because module \(M_{A}^{2}\) and \(M_{B}^{2}\) are connected directly in the second tier, a forwarding module in the second tier is \(M_{B}^{2}\). The first-tier modules at the end of the second-tier virtual link (\(M_{A}^{2}\),\(M_{B}^{2}\)) are assigned to \(M_{B}^{1}\) and \(M_{E}^{1}\). Therefore, the data packet needs to go through module \(M_{B}^{1}\). Then, node \(s\) needs to choose a first-tier forwarding module to deliver the data packet to module \(M_{B}^{1}\). There are two candidates for the path to module \(M_{B}^{1}\), and node \(s\) selects one of them according to path weight. When node \(s\) chooses module \(M_{D}^{1}\) as the first-tier forwarding module, the data packet needs to go through node \(e\) because the end nodes of the first-tier virtual link (\(M_{C}^{1}\),\(M_{D}^{1}\)) are assigned to nodes \(e\) and \(i\), respectively. Finally, node \(s\) chooses node \(a\) as a forwarding node and sends the data packet to it to deliver the data packet to node \(e\). By the same procedure, each node that receives a data packet chooses a forwarding node.