# Strategies for Deploying a Sensor Network to Explore Planetary Lava Tubes
## 4 Line-of-Sight Analysis
### Optimal Sensor Placement for Direct Line-of-Sight  
We consider a multi-hop relay channel for communication and power transfer inside a cave, comprising of a source device \(S\), a destination device \(D\), and \(N\) relays in between the source and the destination device such that a direct line-of-sight link is possible between the source device \(S\) and destination device \(D\). Let us consider that the cave is represented by a non-convex polyhedron \(\mathbb{P}_{cave}\) which is the configuration space. Let each obstacle inside the cave be represented by multiple non-convex polyhedrons \(\mathbb{P}_{obs(i)}\):\(i=1,\ldots,n\), \(n\) being the number of obstacles. Thus, the obstacle region is denoted by \(\mathbb{P}_{obs}=\mathbb{P}_{obs(1)}\cup\ \mathbb{P}_{obs(2)}\cup\ \ldots\cup\ \mathbb{P}_{obs(n)}\). The obstacle-free space is then denoted by \(\mathbb{P}_{free}=\mathbb{P}_{cave}\backslash\mathbb{P}_{obs}\). The position of the source device is represented by \(x_{init}\) and that of the destination device by \(x_{goal}\), which are both an element of \(\mathbb{P}_{free}\). The problem is to  
Figure 12: Variation of distance \(d\) in meters on the floor of the pit within which a direct line-of-sight communication link is possible with respect to the deployed boom height \(h\) and orientation of the antenna \(\phi\) for (**a**) Beam width \(B=30^{\circ}\) and \(a=5\) m; (**b**) Beam width \(B=60^{\circ}\) and \(a=5\) m; (**c**) Beam width \(B=30^{\circ}\) and \(a=10\) m; (**d**) Beam width \(B=60^{\circ}\) and \(a=10\) m.  
find the position of the \(N\) relays such that the number of relays \(N\) is minimized while each sensor has a range \(r\). Finding the minimum number of relays \(N\) is equivalent to finding the position of each relay such that the total distance between the source \(S\) and the destination \(D\) through \(N\) hops is minimum considering the path between two successive sensors is a feasible path, i.e., the path between them lies in the obstacle-free space \(\mathbb{P}_{free}\). We used the concept of Rapidly Exploring Random Tree (RRT) to find the position of the \(N\) relay sensors [37]. Although RRT is a common option that creates a graph and finds a direct line of sight path between the source device \(S\) and destination device \(D\), the path will not necessarily be optimal. However, a modified version of RRT called RRT* aims to provide an optimized shortest path, whether by distance or some other metric that will be used here [38]. The algorithm is initialized with a graph that includes the position of the source device, \(x_{init}\) and no edges. At each iteration \(i=1,\ldots\)\(k\), a point \(x_{rand}\in\mathbb{P}_{free}\) is sampled. An attempt is made to connect the nearest vertex \(v\in V\) in the tree to the new sample. If such a connection is successful, \(x_{rand}\) is added to the vertex set, and \((v,x_{rand})\) is added to the edge set. It also considers connections from the new vertex \(x_{new}\) to vertices in \(X_{near}\), i.e., other vertices that are within the range \(r\) of each sensor. However, not all feasible connections result in new edges being inserted into the edge set \(E\). In particular, (i) an edge is created from the vertex in \(X_{near}\) that can be connected to \(x_{new}\) along a path with minimum cost, and (ii) new edges are created from \(x_{new}\) to vertices in \(X_{near}\), if the path through \(x_{new}\) has lower cost than the path through the current parent; in this case, the edge linking the vertex to its current parent is deleted to maintain the tree structure.  
Figure 14 shows the optimal position of sensors inside three different cave models with multiple obstacles (shown by red polygons) inside. The tree maintained is shown in green at 500 iterations, black squares show the sensor positions, and the black line connecting them is the direct line-of-sight connection links. It can be seen that the RRT* algorithm was able to find a feasible connection link from the source device to the destination device.