# Travel Route Planning with Optimal Coverage in Difficult Wireless Sensor Network Environment
## 4 Our Presented TRP-MC Algorithm  
### Coverage Problem Formulation  
In this section, we first transform the travel route planning problem of the mobile collector into the coverage problem of SPs. As we all know, two sensors can communicate with each other only when they are both in their communication range. Although the mobile collector possesses a better performance than the common sensors, their valid communication ranges are the same. We assume that the mobile collector only stops for data gathering because moving data gathering will result in a high package loss rate and much energy will be dissipated for retransmission. The places where the mobile collector stops are called SPs. When the mobile collector stops at one SP, it can communicate with the sensors within its transmission range. We define the covered area as the place where the mobile collector can communicate with when it stops at SPs. A coverage sample is shown in Figure 5.  
Where \(SP_{1}\), \(SP_{2}\) and \(SP_{3}\) represent three different covered areas of SPs, respectively. As Figure 5 describes, the area \(A_{1}\), \(A_{2}\) and \(A_{3}\) are covered by 2 SPs and \(A_{4}\) is covered by 3 SPs simultaneously. We define those areas which are covered by at least one SP as covered area, and those areas which are covered by more than one SP as overlapped covered areas. One sensor can upload its monitored data to the mobile collector if it is deployed at any covered area of the SP. However, overlapped covered areas dissipate the resource of the mobile collector and increase the travelling distance of the mobile collector. The mobile collector will work more efficiently if the overlapped covered areas are decreased. Due to the round shape of each covered area, it is difficult to calculate the overlapped covered areas, especially the areas covered by multiple SPs. Hence, we introduce anchor points to assist in calculating the overlapped coverage rate. The anchor points are virtual points evenly distributed in the sensor field, as is shown in Figure 6.  
Each anchor point can calculate its distance to the SP to confirm whether it is covered by the SP. Therefore, we define the coverage rate and overlapped coverage rate using Formulas (6) and (7). \[r_{cover} =\frac{n_{cover}}{n} \tag{6}\] \[r_{overlap\_cover} =\frac{n_{overlap\_cover}}{n_{cover}} \tag{7}\]  
Figure 5: Covered areas of the mobile collector. where \(n\) denotes the number of anchor points. \(n_{cover}\) and \(n_{overlap\_cover}\) denote the anchor points cover by at least one SP and more than one SPs, respectively. Additionally, the accuracy of \(r_{cover}\) and \(r_{overlap\_cover}\) is corresponding to the density of anchor points. In Figure 5, the coordinates of SPs \(SP_{1}\), \(SP_{2}\) and \(SP_{3}\) are (180,240), (120,120), and (240,120), respectively. The corresponding transmission range is 90 and the density of the anchors is one. The coverage rate and the overlapped coverage rate are 0.5214 and 0.1718, respectively. In our presented TRP-MC, we regard the sensor nodes as the anchor points mentioned above. The TRP-MC can be formalized after all the SPs are selected. When the mobile collector stops at the SPs, sensors which are in the transmission range of the mobile collector are called the neighbors of SPs. Our goal is to use a fixed number of SPs to cover as many sensors as possible and the overlapped coverage rate is as low as possible at the same time. The object of TRP-MC can be transformed into mixed-integer programming using Formula (8). \[\textit{Maximizer}\ r_{cover}\ \&\ \&\ \textit{Minimize}\ r_{overlap\_cover} \tag{8}\]  
where \(r_{cover}\) and \(r_{overlap\_cover}\) can be calculated using Formulas (9) and (10). \[r_{cover}=\frac{\sum_{i=1}^{n}c_{i}}{n} \tag{9}\]  
\[r_{overlap\_cover}=\frac{\sum_{i=1}^{n}o_{i}}{\sum_{i=1}^{n}c_{i}} \tag{10}\]  
where \(n\) is the number of sensors, \(c_{i}\) and \(o_{i}\) are illustrated in Formulas (11) and (12), respectively. \[c_{i}=\left\{