## 3 Task Assignment Algorithm Based on Extended CNP
### Distributed Multi-Constraint Dynamic Task Assignment Algorithm
*/
11: end if
12: end for
13: /* Step 2: Generate bidding scheme */
14: for\(j\) from the first index of leader UAVs to the last one
15: for\(i\) from the first index of tenderee leader UAVs to the last one
16: if\(V_{j}\) belongs to \(\{V_{p,i}\}\)
17: Receive \(I_{i}\) and broadcast it to \(V_{j}\)'s followers
18: end if
19: end for
20: for\(m\) from the first index of followers of \(V_{j}\) to the last one
21:\(\{\textit{Task}^{a,m}\}=\) checkTaskConstants(\(\{I_{i}\textit{Task}k_{i}\}\)) /* Select the executable subtasks from \(\{\textit{Task}k_{k}\}\) */
22:\(\{\textit{Seq}^{m}_{m}\}=\) combineTasks(\(\textit{Task}^{a,m}\)!) /* Generate the set of alternative sequence */
23:\(\{\textit{B}_{m,n}\}=\) biddingFuncCalcI(\(\{\textit{Seq}\textit{Set}_{m}\}\)) /* Calculate the bidding function of each sequence */
24:\(\textit{Seq}^{m,m}=\textit{Seq}^{m}_{m_{out}}\), \(\textit{n}_{best}=\underset{n}{\text{argmax}}(\textit{B}_{m,n})\) /* Determine the sequence to execute */
25: end for
26:\(\textit{B}_{g,k}=\underset{m}{\text{max}}(\textit{B}_{m,n})\)
27: end for
28: /* Step 3: Determine the winners */
29: for\(i=1\) to number of tenderee leader UAV \(i\)
30: for\(k=1\) to number of targets tendered by leader UAV \(i\)
31:\(\textit{B}_{g,k}=\text{max}[\textit{B}_{g,k}\}\), \(\textit{Winner}_{g,k}=\underset{j}{\text{argmax}}\Big{(}\textit{B}_{g,k} \Big{)}\) /* Determine winner of tendering for Target \(k\) */
32: end for
33: end for
34: /* Step 4: Perform the tasks */
35: for\(n=1\) to number of subsets
36: for\(m=1\) to number of follower UAV \(m\) of Subset \(n\)
37:\(\textit{A}_{m}=\textit{A}_{m}\oplus\textit{Seq}^{min,m}\) /* Add the signing subtask sequence to task execution sequence \(\textit{A}_{m}\). */
38: end for
39: end for
```

**Algorithm 2**The extended Contract Network Protocol. Analyze the worst time complexity of the algorithm and take the case of task assignment by the top leader as an example:

The time complexity of the top leader issuing \(N_{T}\) targets with subtasks bidding information to \(N_{G}\) subset leaders is \(O(N_{T}N_{G})\), the complexity of the initial evaluation of 4 types of constraints presented in Section 2.5 by \(N_{G}\) subset leaders is \(4O(N_{T}N_{G})\), the complexity of the bidding of potential bidder subsets \(\{V_{p,i}\}\) is \(O(K)\), where \(K\) is the number of elements in \(\{V_{p,i}\}\); after \(K\) potential bidder subsets are determined, each potential bidder subset needs to pre-assign the subtasks and generate the bidding scheme of the subset. Assume that each target has \(N_{t}\) subtasks, each subtask needs the most \(N_{p}\) participants and each subset consists of \((N_{f}+1)\) UAVs. Each subset will generate the target scheme based on the CNP within the subset. The time complexity of the subset leaders issuing \(N_{t}\) subtasks to their \(N_{f}\) followers is \(O(N_{T}N_{t}N_{f})\). The sequential task selection is an arrangement combination problem, of which the time complexity is \(N_{T}\bullet O(N_{t}^{3})\), and the time complexity of bidding to the subset leader in each subset is \(O(N_{T}N_{t}N\beta)\). Subset-leader-selecting cooperators can be regarded as a sorting problem, and the quick sort algorithm can be adopted so that the time complexity is \(N_{T}N_{t}\bullet O(N_{p}\text{log}_{2}N_{p})\). Therefore, the time complexity of the subtask pre-assignment is \(2O(N_{T}N_{t}N\beta)+N_{T}\bullet O(N_{t}^{3})+N_{T}N_{t}\bullet O(N_{p}\text{ log}_{2}N_{p})\). After the bidding schemes of each subset are generated, the bidding winner subset will be determined. It is a quick sort process, so the time complexity is \(N_{T}\bullet O(N_{G}\text{log}_{2}N_{G})\). To conclude, the whole worst time complexity is \(2O(N_{T}N_{t}N\beta)+N_{T}\bullet O(N_{t}^{3})+N_{T}N_{t}\bullet O(N_{p}\text{ log}_{2}N_{p})+N_{T}\bullet O(N_{c}\text{log}_{2}N_{c})\). It indicates that the algorithm is a polynomial one.