## 3 Preliminaries and Problem Statement  
### Network Model and Problem Definition  
We studied the target coverage problem with the following model. All of the networking nodes are located in an obstacle-free predetermined region, including sensors and targets. \(T=\{t_{1},\,t_{2},...,\,t_{M}\}\) is a set of \(M\) targets distributed randomly; the position of each is known. \(S=\{s_{1},\,s_{2},...,\,s_{N}\}\) is a set of \(N\) homogeneous directional sensors with the same field of view \(\theta\) and the same sensing radius \(r\); these sensors should be scheduled to cover all targets. For a directional sensor \(s\) with field of view \(\theta\) and sensing radius \(r\) located at location (\(x,y\)) in the region (Figure 1), the sensing area for sensing orientation \(\alpha\) is a sector of a circle with center (\(x,y\)) and radius \(r\); the sector is bounded by two radii between \(\alpha\) - \(\theta/2\) and \(\alpha+\theta/2\). This sector is represented by \(D_{\alpha}\). Target \(t\) is covered by sensor \(s\) if its location is within \(D_{\alpha}\). The directional sensors can rotate to any direction to monitor a specific target. Because of the limited field of view of each directional sensor, a target may not be covered by a sensor, even if it is located within the sensor's sensing radius. In this case, the directional sensor can rotate to cover the targets (Figure 2). In Figure 2a, three targets, namely, \(t_{1},\,t_{2}\), and \(t_{3}\), are located within the sensing range of deployed sensor \(s\) with original orientation \(\alpha\). Targets \(t_{1}\) and \(t_{2}\) are covered by the sensor; however, target \(t_{3}\) can also be covered if sensor \(s\) rotates its sensing orientation clockwise to \(\beta\). Figure 1: Directional sensing for a rotatable sensor. **Definition 1**. : _For sector \(D_{\alpha}\), \(\mid T(D_{\alpha})\mid\) denotes the number of targets in this sector, where \(T(D_{\alpha})\) is the set of targets in \(T\) covered by sector \(D_{\alpha}\). Then, \(D_{\alpha}\) is called a cover sector of \(T\) if \(\mid T(D_{\alpha})\mid>0\)._  
**Definition 2**. : _Let \(D_{\alpha}\) and \(D_{\beta}\) be two different cover sectors of \(T\) for directional sensor \(s\). Then, \(D_{\alpha}\) is equivalent to \(D_{\beta}\) and vice versa if \(T(D_{\alpha})=T(D_{\beta})\). Furthermore, \(D_{\alpha}\) is dominated by \(D_{\beta}\) or \(D_{\beta}\) dominates \(D_{\alpha}\) if \(T(D_{\alpha})\subset T(D_{\beta})\)._  
**Definition 3**. : _Let \(D_{\alpha}\) be a cover sector of \(T\) for a directional sensor \(s\). Then, \(D_{\alpha}\) is called a maximal cover sector if \(D_{\alpha}\) is not dominated by any other cover sector in sensor \(s\)._  
**Proposition 1**. : _Let \(k\) be the number of targets within the sensing radius \(r\) of sensor \(s\). Then, at most \(k\) different (or nonequivalent) maximal cover sectors exist for sensor \(s\)._  
For the target coverage problem, after the initial deployment of sensors, not all targets are covered under the random deployment fashion. Our goal is to rotate the initial orientations of the sensor to maximize the number of covered targets while minimizing the number of activated sensors. Therefore, the target coverage problem with rotatable sensors is defined as follows:  
**Definition 4**. : _Maximum Coverage with Minimum Rotatable Sensors (MCMRS) Problem: Assume a set of targets \(T\) = {\(t_{1}\), \(t_{2}\),..., \(t_{M}\)} to be covered, a set of homogeneous rotatable directional sensors \(S\) = {\(s_{1}\),\(s_{2}\),...,\(s_{N}\)} with\(p_{i}\) possible orientations each, and a set of cover sectors \(D\) = {\(D_{ij}\), \(1\leq i\leq n\), \(1\leq j\leq p_{i}\)}, where \(D_{ij}\) is the \(j\)th maximal cover sector for sensor \(s_{i}\),\(p_{i}\) denotes the maximum number of cover sectors for sensor \(s_{i}\)_i, and \(T(D_{ij})\) is a subset of \(T\).