## 3 Ferry Node Ranking Clustering Algorithm (FNRCA)
### Checkpoints Weighting Scheme  
To determine the path of the ferry or which checkpoints to visit first, a weighting scheme is used based on determining the following weights:  
\(\bullet\) Checkpoints with larger number of attached cluster heads:  
Checkpoints with larger number of attached cluster heads will contribute more to the amount of the data collected and in order to reduce data lost, they will have a higher priority of being visited first by the ferry. The weight for such a CP, j, is calculated as:  
\[W_{1}(j)=\frac{Attachedclusterheads(j)}{N_{T}} \tag{12}\]  
where \(N_{T}\) is the total number of cluster heads in the network.  
\(\bullet\) Checkpoints closer to the Base Station:  
Checkpoints closer to the Base Station will be given a higher weight in order for the ferry to start the collection process from them first and then move ones further away. Their weight will be calculated as:  
\[W_{2}(j)=\frac{1}{D(CP(j),BS)} \tag{13}\]  
\(\bullet\) Checkpoints closer to each other:  
Checkpoint closer to each other will reduce the traveling time and distance of the ferry; therefore, they will have a higher priority of being visited first by the ferry and their weight will be calculated as:  
\[W_{3}(j)=\frac{1}{\min[D(CP(j),CP(j))]},l=1,2,..m,l\
eq j \tag{14}\]  
The overall weight (\(W\)) is computed as:  
\[\max W=\sum_{j=1}^{m}W_{1}(j)+W_{2}(j)+W_{3}(j) \tag{15}\]  
Following is the pseudo code for ordering the checkpoint in Travelling Salesman Problem sequence to be visited by the ferry according to the weight given to them:  
* **Input**: a set of checkpoints, their attached cluster heads.
* **Output**: A sequence of checkpoint for the ferry to follow.  
* //Optimal Travelling_Salesman_Problem_tour
* **while** there exist checkpoints **do**
* 1) **do** find the weight W from Equation (15).
* **End for**
* Select CP with maximum weight
* Add it to the TSPour list {CPj,CPj + 1...}
* Remove it from the set
* **end while**
* **return** TSP tour  
The output of the above pseudo code which is the ordered sequence of checkpoint will be used as an input to the next pseudo code of the genetic algorithm. In our work, TSP will be used to find a Hamilton cycle to decide the path of the ferry, where checkpoints represent vertices and the distance between them will represent the edges. The above weight will be used to choose which vertices will be visited first such that the overall consumed energy and roundtrip travelling time will be a minimum.  
Assuming a directed graph (G) with weights on the edges where \(G~{}=~{}(Vertex,Edge)\) we will find a Hamilton cycle where the cycle covers all the vertices only once and seeks a minimal weight subset of edges.  
The abovementioned problem can be solved easily in a short time if the number of checkpoints are four or less by trying all possible paths (4!) and finding the minimum weight among them. However, if the number of checkpoints is more than four there will be permutations of possible paths which will take much longer time and processing capabilities. Therefore, we used a genetic algorithm to find the best path based on our own fitness function, goals and weights as shown in the below subsections.