## 3 Proposed Protocol
### Data Forwarding Algorithm  
The hardest challenge is how to reduce the traffic in the regions in between of the holes (we call this region the _critical region_). In [37], we proposed a data forwarding algorithm, in which the base path is always the shortest path bypassing the holes. However, in the context of networks with multiple holes, always use the same base path to construct the routing paths may cause a high traffic load in the critical region. To this end, we attempt to use dynamic base paths that vary for every packet. On the one hand, the base paths are probabilistically selected such that a path that is farther from the critical region is more likely to be chosen. On the other hand, the base path length is controlled to guarantee the required routing path upper bound. Specifically, the base paths are the Euclidean paths that bypass all the core polygons and have the length under a predetermined threshold. For each base path, we assign a so-called priority index which indicates how far is it from the holes. When a source has a packet to send, it probabilistically pickups one base path (with the probability being proportional with the path's priority index) and scales up the base path by using homothetic transformations. The scale factors of the transformations are controlled to guarantee the required upper bound of the stretch and the scale centers of the transformations are chosen randomly to guarantee the diversity of routing path. Let \(s\) and \(t\) be a source and a destination, respectively. In the following we will show how a source node \(s\) can exploit the hole information to make a routing decision to a destination \(t\). To simplify the presentation, we use the following notations. Let \(N\) and \(M\) be two arbitrary nodes (\(N\
eq M\)),  
Figure 1: The overview of our approach. then \(\mathcal{C}(N)\) denotes the core polygon containing \(N\), and \(\mathcal{H}(N)\) denotes the hole whose core polygon is \(\mathcal{C}(N)\) (\(\mathcal{H}(N)=\mathcal{C}(N)=\varnothing\) if \(N\) does not stay inside any core polygon). Let \(\mathbb{C}(\overline{N})\) denote the set of all core polygons excepting \(\mathcal{C}(N)\), and \(\mathbb{C}(\overline{N},\overline{M})\) denote the set of all core polygons excepting \(\mathcal{C}(N)\) and \(\mathcal{C}(M)\). Similarly, let us denote \(\mathbb{H}(\overline{N})\) the set of all holes excepting \(\mathcal{H}(N)\), and \(\mathbb{H}(\overline{N},\overline{M})\) the set of all holes excepting \(\mathcal{H}(N)\) and \(\mathcal{H}(M)\). \(N\) is said a \(M\)-aware node, if either \(\mathcal{H}(M)=\varnothing\) or \(N\) has the hole information of \(\mathcal{H}(M)\). Our data forwarding protocol consists of three steps: determining the base path, magnifying the base path to obtain the Euclidean routing path, and forwarding the packet along the Euclidean path. Before going to the detail of each step, we sketch the overview. If \(s\) is a \(t\)-aware node (i.e., \(s\) has information of the hole containing \(t\)), then \(s\) determines the base path as an Euclidean path from \(s\) to \(t\) which bypasses \(\mathcal{H}(s)\), \(\mathcal{H}(t)\) and \(\mathbb{C}(\overline{s},\overline{t})\). This base path then is magnified using a transformation to obtain the Euclidean routing path. Finally, the packet is forwarded along the Euclidean routing path until reaching \(t\). See Figure 2a for the illustration. Otherwise, if \(s\) is a \(t\)-blind node (Figure 2b) (i.e., \(s\) does not have full information of the hole containing \(t\)), \(\mathcal{H}(t)\), thus it cannot determine a Euclidean path to \(t\) which bypasses all the holes. Therefore, \(s\) determines the base path as an Euclidean path from \(s\) to a vertex of \(\mathcal{C}(t)\) which bypasses \(\mathcal{H}(s)\) and \(\mathbb{C}(\overline{s})\). This base path then is magnified through a transformation to obtain the Euclidean routing path.