# 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.1 Low-Level Granularity  
In low-level granularity, the satellites are allowed to negotiate only once to save communication resources. The negotiation process can be described as the following steps (the _TLeaders_' assistance process is ignored in this granularity and is introduced in high-Level granularity) shown in Figure 2:  
* **Step 1:** Preprocessing the missions. The _Follower_ first preprocesses the missions by calculating the time window, profit, and cost.
* **Step 2:** Select a set of desired mission stages. The desired mission stages are selected by decision algorithm in _Follower_.
* **Step 3:** Transmit the mission set. The set of desired mission stages \(MS_{desire}\) and their cost is broadcast, and the _Leader_ records the mission set.
* **Step 4:** Leader process. The _Leader_ finishes the mission assignment using a greedy algorithm. According to the profit calculation model, the profits of each mission stage are the same. That means the mission stages are assigned to the satellite with less cost.
* **Step 5:** Announce temporary result. The _Leader_ announces a temporary result to all _Followers_.
* **Step 6:** Result check and national vote. The _Follower_ logs and checks the result. If the assigned missions \(MS_{actual}\) are all in the desired mission set submitted, the _Follower_ votes in favor, and if not votes against. The national vote result can be expressed as: \[V=\left\{\begin{array}{ll}1&\quad MS_{actual}\subseteq MS_{desire}\\ 0&\quad\quad\quad\quad\quad else\end{array}\right..\] (12)
* **Step 7:** Result release. The _Leader_ records the selection from the _Follower_ who votes in favor. Then the _Leader_ releases the final negotiation result.
* **Step 8:** Execute. The _Follower_ checks the result again, then picks the intersection of the set of assigned missions \(MS_{actual}\) and the set of desired mission stages \(MS_{desire}\), and then executes the mission stages in the intersection.  
Under the process, each _Follower_ needs to decide the desired mission set by itself. It becomes a group knapsack problem with time constraint, which can be described as:  
\[\begin{split} max&\sum_{i=1}^{n}\sum_{j=1}^{5}P_{i,j}s_{i,j }\\ S.T.&\sum_{j=1}^{5}s_{i,j}<2\\ &\quad\forall i^{\prime}andi^{\prime\prime},T_{i^{\prime}}^{S}>T_{i^{ \prime\prime}}^{E}\ OR\ T_{i^{\prime\prime}}^{S}>T_{i^{\prime}}^{E},\end{split} \tag{13}\]  
where \(s_{i,j}\) is mission selection result, \(s_{i,j}=1\) if the \(j\)th stage of \(i\)th target is selected; else \(s_{i,j}=0\). Both of \(i^{\prime}\) and \(i^{\prime\prime}\) are the target ID in the selected mission set. Dynamic programming is chosen to solve the problem.  
In the low-level granularity, the communication resource is most significant. Due to the RAFT algorithm's low consumption, it was selected to be the consistency algorithm work at this level. The algorithm's parameters are adjusted to space usage. The modifications include:  
Heartheeat interval is longer. Due to the time-varying characteristics of satellite networks, the connection may be unstable. Frequent broadcast behavior for heartbeat may cause wastage of bandwidth. Additionally, the network delay may cause misjudgment of the connection between the _Leader_ and _Followers_. The longer interval brings a bigger allowance.  
The election interval is longer. Based on the principle of RAFT, the election happens when the _Leader_ is unconnected. That means the election interval is related to the heartbeat interval. Therefore, the election interval is longer too.  
The negotiation result is not released in a heartbeat message. Based on the principle of RAFT, a longer heartbeat interval causes a delay of mission response. Thus the release negotiation result package is designed to be independent. It usually transmits periodically; besides, it also supports emergency transmission to improve real-time performance for emergency missions.