# Multi-Granularity Mission Negotiation for a Decentralized Remote Sensing Satellite Cluster
## 2 Proposed Methods
### Multi-Granularity Partition of the Multi-Agent Negotiation Model
#### 2.2.3 High-Level Granularity Model  
High-level granularity is designed to a obtain better negotiation effect in a good communication environment. Differently from the other two levels of granularity, the satellites are divided into a _Leader_ group and several _Followers_, and the _Leader_ group consists of a _Leader_ and _TLeaders_. The process can be divided into the following steps shown in Figure 4:  
* **Step 1:** Apply to join the _Leader_ group. There exists one _Leader_ in the system as the _Leader_ for all levels of granularity. In order to increase the fault tolerance rate, the _Follower_ with a direct connection (only one hop to the _Leader_) applies to join the _Leader_ group. After being authorized by the _Leader_, it becomes a _TLeader_.
* **Step 2:** Preprocessing the missions. Same as before.
* **Step 3:** Select a set of mission stages. The set of mission stages, which contains all the supported mission stages, is selected by decision algorithm in _Followers_ and _TLeaders_.
* **Step 4:** Transmit the mission set. These mission stages are broadcast, including their execution cost and time window, and both the _Leader_ and _TLeaders_ record the set.
* **Step 5:** Leader Process. The _Leader_ and _TLeaders_ assign missions using a greedy algorithm, considering an extra constraint of the maximum cost of each _Follower_.
* **Step 6:** Announce temporary result. The _Leader_ firstly announces a temporary result in the _Leader_ group and votes for the result. Then the temporary result is announced if confirmed by most _TLeaders_. If not they go to **Step 5** to process again.
* **Step 7:** Result check and vote. Same as before.
* **Step 8:** Vote process. If all _Followers_ vote in favor or negotiation fails times too much, the _Leader_ stops negotiations and goes to **Step 9**. If not, the _Leader_ adjusts the set of mission stages still using a greedy algorithm and then goes to **Step 6**.
* **Step 9:** Result release. Same as **Step 6**, the _Leader_ releases the final negotiation result first in the leader group. After being confirmed, the negotiation results are released to all nodes.
* **Step 10:** Execute. Same as before.  
In this process, the nodes chose as many mission stages as possible. All mission stages satisfied cost effectiveness ratio are chosen, described as:  
\[s_{i,j}=\left\{\begin{array}{ll}1&\quad c_{i,j}/P_{i,j}\leq CER^{thd}\\ 0&\quad c_{i,j}/P_{i,j}>CER^{thd}\end{array}\right.. \tag{16}\]  
In the high-level granularity, RIPPLE and PBFT algorithms are combined to improve system stability and negotiation accuracy. The modifications include:  
Leader group member selection method. In RIPPLE algorithm, the _Leader_ group member is selected from all _Followers_. Considering the communication environment, all _Followers_ satisfying a condition should make applications for the group.  
The PBFT verification mechanism is introduced into the leader group. The PBFT verification mechanism could effectively prevent node failure or disturbance. This is well adapted to satellites because of their limited computation resources. Verification in the leader group can reduce the possibility of error information release. In other words, the leader group sacrifices its communication bandwidth and computational resources for other nodes working in lower granularity.