Task allocation based on modified contract net protocol under generalized cluster

Abstract

The generalized cluster characteristics and the multi-user target requirements are analyzed, based on which an improved contract net model is constructed in order to resolve the low communication efficiency and the low task completion quality of the contract net protocol negotiation mechanism under the generalized cluster. In addition, a temporary monitoring unit is configured as a medium for task broadcasting and negotiation to reduce the communication consumption and improve the communication efficiency. In order to provide the tenderers and the bidders with the bidirectional screening constraints, QoS multi-objective constraints are introduced, which can improve the quality of task completion significantly. We also propose the concept of task priority and the tasks are performed sequentially, which can significantly reduce the unwanted task congestion caused by the concurrent multitasking. The simulation results show that this method reduces both the total time of task completion and the communication overhead of the negotiation process under the generalized cluster, and completes the desired task with a high-quality. This fully verified the rationality of the model and the effectiveness of the algorithm.

Keywords

Generalized cluster task allocation improved contract net temporary monitoring unit QoS (quality of service)

1. Introduction

With the rapid development of the pervasive computing model, Generalized-Cluster is widely used, and which is different from a closed computing environment. Generalized cluster, a carrier of pervasive computing [1], is a large-scale computing environment constituted by numerous standalone, cheap compute nodes through the net. The compute node may be the compute elements like PC, WS or cellphone, or the loose “computational swarm” comprised by multiple compute elements, with the purpose of providing the cost-benefit computing power [2]. In addition to the instability, the generalized cluster is also featured by expansibility, perceptibility, autonomy, sociality, as well as extended self-organization capability, learning capability and inferential capability.

Generalized cluster, a carrier of pervasive computing [3], with the deepening of theoretical research on Multi-agent Systems (MASs), the members of generalized cluster gradually present the characteristics of Agent. Compared with MASs, cloud computing, grid computing and other technologies, expansibility and affordability are highlighted in generalized cluster. Therefore, generalized cluster boasts “5M” advantages: more extensive application scenarios, more powerful processing capacity, cheaper resource cost, more loose member relationship and more contracted architecture [4]. And it is very suitable to solve many large-scale scientific computing problems through the cooperation of its own organization, especially repeated, large number of scientific experiments or mathematical operations which can be granular.

As the foundation of generalized cluster operation, task allocation relates to how generalized cluster accomplishes tasks and how compute nodes coordinate. Task allocation is to improve the comprehensive performance of generalized cluster tasks according to the specific conditions, such as reducing the execution time of the total tasks [5], the total communication consumption in task execution [6], and the collision probability of generalized cluster in performing tasks [7], and improving the adaptability of the generalized cluster to the dynamic environment when performing tasks [8].

In the field of distributed intelligent control, task assignment mainly includes Contract net, load balancing, Biological immune mechanism, acquaintance mechanism and so on [9, 10, 11, 12, 13, 14]. Contract net is proposed by Smith to solve the issue of task and resource allocation, the aim of it is to make the distributed system complete the task with lower cost and higher quality. The contract network has the characteristics of simple modeling and can simulate various benefit relationships and so on. At present, it has been widely applied to the manufacturing scheduling, engineering scheduling, satellite autonomous planning and UAV task scheduling [15, 16, 17, 18].

Distributed task allocation is available in the contract net, but it has the following deficiencies, which results in the inefficient actual task allocation:

(1)
Communication efficiency: all bidders can participate in the bidding and the tenderees need to evaluate a large number of bid documents. This may lead to large communication costs and resource occupancy, which results in information congestion in invitation for bids.
(2)
Quality of task completion: the tasks in the traditional contract net are assigned randomly, which causes retention of some tasks; the bidder has a poor ability of screening constraint for the tenderees during allocating task, resulting in the low quality of task completion.

In view of the above problems, the related scholars have improved the traditional contract net.

According to the literature [19], task allocation is to minimize the cost and maximize the effectiveness of the task as to the quality of task completion, therefore, the assignable maximum number of tasks is limited to reduce the complexity of the computation. Zhang et al. put forward a semi-autonomous multi-Agent task allocation method, which combines the mental model with the extended contract net mechanism to eliminate the defect of the large amount of information in the traditional task allocation [20]. In order to reduce the communication cost and improve the system’s index of task completion, Jian et al. introduced strategies of interactive trust, acquaintance trust and threshold value based on the classic contract net [21].

For the communication efficiency, Zhang et al. proposed to simulate the negotiation process of contract net with the cost time Petri net, which can reduce the coordination time between Agents [22]. Liang and Ju designed the circular trust area on the basis of the traditional contract net to narrow the scope of the bid and improve the communication efficiency [23]. Sang et al. proposed an improved contract net protocol based on cycle period to improve the efficiency of the contract net protocol, where the bidding is proposed in an orderly manner through the cycle period, and the bid is limited on quotes by the threshold strategy [24].

The traditional contract net based improvement above can solve the problem of the task completion quality and individual communication efficiency, however, in the face of the situation that the task cannot be completed due to a unit is apoptotic or withdraws from the alliance, no corresponding solution is described in the above literature. Therefore, for the instability of the generalized cluster, the classical contract net model was improved by designing a temporary monitoring unit to replace the tenderee’s broadcast task message and communicate with the bidder, which not only helps reduce the communication consumption between the tenderees and the bidders, but also improves the communication efficiency; QoS was introduced by adopting execution time, trust and utility multi-objective constraints in the two-way screening between the tenderees and the bidders to improve the quality of task completion. Moreover, we proposed the concept of task priority, where the tasks are performed sequentially, to reduce task congestion caused by multi-task concurrency and improve the quality of task completion.
2. Problem description

The task assignment in a Generalized cluster environment is essentially a Combinatorial Optimization Problem and a NP hard problem. Aiming at the multi-objective and complex constraint of the problem, the conditions for the multi-objective constraint satisfaction are summarized as follows.

2.1 Problem description

The improved contract net task allocation model under the generalized cluster can be described by three tuples.

$\displaystyle TA\equiv\ <\textit{Tasks},CE,\textit{Strategies}>$ $\displaystyle CE\equiv\ <T,B,\textit{TMU},S>$ $\displaystyle\textit{Strategies}\equiv\ <\textit{TSS},TS,BS,\textit{SDS},% \textit{TES}>$

(1)
Tasks represent a task set.
(2)
CE indicates the role in the improved contract net. T stands for the tenderee, the decision based computing unit, and B is the bidder, the task based compute node; TMU is the temporary monitoring unit, the communication based compute node, and S is the winning bidder, the task based compute node that is assigned with tasks.
(3)
Strategies represent the task allocation strategy set based on the improved contract net. TSS is the task selection strategy and determines the tasks to be performed according to the task priority; TS stands for the tenderee’s tendering strategy and determines the contents of the tender, and BS for the bidding strategy of the bidder after receiving the tender; SDS refers to the bid evaluation strategy of the tenderee, and TES to the strategy of the bidder in task execution.

2.2 Symbol definition and basic assumptions

The main variables and their meanings are defined and explained in Table 1.

Table 1
Symbols and meanings of the main variables

Symbol	Meaning
$j$	Tenderee number, $j\in[1,m]$
$i$	Task number, $i\in[1,n]$
$T_{i}$	Task $i$
$S_{j}$	Tenderee $j$
$x_{ij}$	Whether task $T_{i}$ is assigned to bidder $S_{j}$
$t^{l}_{i}$	Continuous execution time required by task $T_{i}$
$t^{b}_{ij}$	The time for the bidder $S_{j}$ to start the task $T_{i}$
$t^{e}_{ij}$	Moment for the bidder $S_{j}$ to complete the task $T_{i}$
$t^{d}_{ij}$	The time required by the bidder $S_{j}$ to complete the task $T_{i}$
${td}_{ij}$	Whether the bidder $S_{j}$ completes task $T_{i}$
$R_{j}$	The trustworthiness of the bidder $S_{j}$
$r^{l}_{i}$	Trust degree required by task $T_{i}$
$p_{j}$	The utility of unit running time for the bidder $S_{j}$
$c^{l}_{i}$	The utility of task $T_{i}$
$c^{d}_{ij}$	The utility of the bidder $S_{j}$ to complete the task $T_{i}$
${co}^{d}_{ij}$	The cost of communication required by the bidder $S_{j}$ to complete the task $T_{i}$

We developed the following assumptions in the paper:

Assumption 1 The tasks in the task set are relatively independent and not associated with each other. They have no mutual influence in executing. Assumption 2 The compute-intensive task data flow is studied in this paper.

2.3 Constraint conditions

(1)
If the task $T_{i}$ is assigned to the bidder $S_{j}$ , then $x_{ij}=$ 1, otherwise $x_{ij}=$ 0. That is,

$\displaystyle x_{ij}=\left\{\begin{array}[]{ll}1,&T_{i}\to S_{j}\\ 0,&\text{other}\end{array}\right.$ (1)
(2)
QoS target constraints include execution time, reliability and utility.

$\displaystyle{\varphi}_{ij}(t)=\left\{\begin{array}[]{ll}1,&{\varphi}^{1}_{ij}% (t)={\varphi}^{2}_{ij}(t)={\varphi}^{3}_{ij}(t)=1\\ 0,&\text{other}\end{array}\right.$ (2)

Where ${\varphi}_{ij}(t)={\varphi}^{1}_{ij}(t)\bigwedge\varphi^{2}_{ij}(t)\bigwedge% \varphi^{3}_{ij}(t)$ , “ $\bigwedge$ ” represents the logic “and” operation; ${\varphi}^{1}_{ij}(t)$ indicates that the execution time meets the needs of the task; ${\varphi}^{2}_{ij}(t)$ means the reliability meets the needs of the task; ${\varphi}^{3}_{ij}(t)$ shows that the utility meets the needs of the task; ${\varphi}_{ij}(t)$ indicates that the bidders meet the QoS needs.
(3)
Usually, the bidder can only perform one task at the same time. At $t_{0}$ , for $\forall j\in[1,m]$ and $i,k\in[1,n](k\neq i)$ , then:

$\displaystyle x_{ij}\bigwedge{x}_{kj}=0\text{ and }x_{ij}{\bigvee}{x}_{kj}\leqslant 1$ (3)
(4)
One task can only be assigned to one tenderee or the task is not assigned. For $\forall\ i\in[1,n]$

$\displaystyle\sum^{m}_{j=1}{x_{ij}}\leqslant 1$ (4)
(5)
The execution time of assigned tasks must be greater than or equal to the time required by tasks. For $\forall\ i\in[1,n]$ , there is

$\displaystyle t^{e}_{ij}-t^{b}_{ij}\geqslant t^{l}_{i}$ (5)
(6)
The start time and the arrival time of the task are related to the available time of the bidder’s resources. $\forall\ i\in[1,n]$ , if $x_{ij}=$ 1 with $\exists\ j\in[1,m]$ , then

$\displaystyle t^{b}_{i}=\max\{t^{a}_{i},t^{S_{e}}_{j}+t^{i-1,i}_{j}\}$ (6)

Where $t^{b}_{i}$ represents the target cut-off time of the task $T_{i}$ ; ${t}^{a}_{i}$ is the completion time for the task $T_{i}$ target; $t^{S_{e}}_{j}$ is the moment for the bidder $S_{j}$ to complete the task assigned; $t^{i-1,i}_{j}$ indicates the time required for the bidder $S_{j}$ to prepare $T_{i}$ after $T_{i-1}$ is completed.
(7)
The tasks assigned in the generalized cluster are executed according to the task priority, and the tasks in execution cannot be preempted. If $\forall\ j\in[1,m]$ , $\exists\ i\in[1,n]$ , $x_{i-1,j}=x_{i,j}=x_{i+1,j}=1$ , then

$\displaystyle t^{e}_{i-1,j}\leqslant t^{b}_{ij}<t^{e}_{ij}\leqslant t^{b}_{i+1% ,j}$ (7)
(8)
If the bidder $S_{j}$ completes the task $T_{i}$ while meeting the needs of QoS, then ${td}_{ij}=$ 1, otherwise ${td}_{ij}=$ 0, namely

$\displaystyle{td}_{ij}=\left\{\begin{array}[]{ll}1,&T_{i}\to S_{j}\\ 0,&\text{other}\end{array}\right.$ (8)
(9)
If $n$ is the number of tasks performed by the bidder $S_{j}$ , the trustworthiness of the bidder $S_{j}$ can be expressed as:

$\displaystyle R_{j}=\sum^{n}_{i=1}{{td}_{ij}}$ (9)
(10)
The trustworthiness of the bidder $S_{j}$ must be greater than or equal to the trust degree required by the task. For $\forall\ i\in[1,n]$ ,

$\displaystyle{R_{j}\geqslant r}^{l}_{i}$ (10)
(11)
The utility sum for the bidder $S_{j}$ to complete the task $T_{i}$ must be less than or equal to the utility provided by the task $T_{i}$ , $\forall i\in[1,n],\exists j\in[1,m]\$ , namely

$\displaystyle c^{d}_{ij}+{co}^{d}_{ij}=p_{j}\cdot t^{d}_{ij}+{co}^{d}_{ij}{% \leqslant c}^{l}_{i}$ (11)

3. Description of generalized cluster environment

In this paper, the large-scale scientific computing is processed under the scenario of the generalized cluster. Expansibility and cheapness are highlighted in the generalized cluster. Hence, the compute-intensive task processing under the generalized cluster has the following advantages: the strong processing ability, the low resource cost, the loose member relationship, the simple architecture. The structure of the generalized cluster is shown in Fig. 1.

Figure 1.

Structure of generalized cluster.

The compute nodes in the generalized cluster can be the individual of any computing entity, such as a server, PC, tablet computer and cellphone. It can also be the alliance of computing units or the generalized cluster. The compute nodes in the generalized cluster are unstable and can be detached from the alliance or the generalized cluster at any time.

Based on the generalized cluster theory, the computing units are divided into the decision based computing units and the task based computing units. The former refers to the computing unit with a good communication ability, which is responsible for releasing the bidding information of the task observed and communicating with other compute nodes; the latter has a good behavior execution capability, receives the bidding notice sent by the decision based computing units, and assesses the QoS needs according to its own needs to decide whether to participate in the tender.

3.1 Decision based computing unit

The computing unit with good communication ability, the optimal autonomy and sociality are selected from the generalized cluster as the decision based computing unit, which is responsible for the task management and allocation.

The task of the decision based computing unit is to screen the optimal task based compute nodes in executing the tasks through the QoS target requirement.

3.2 Task based computing unit

The capability of the unit, as the basis for the computing unit to complete the task, is described in this paper, including the way and the effect of completing the task [26]. The computing unit’s capabilities include the basic capabilities and the behavior execution capabilities. The basic capabilities are autonomy, sociability and responsiveness; the execution capability determines the probability of task execution and the effect of task completion, at the same time, it also reflects the differences of the individual abilities among different computing units, and provides an effective guidance for task allocation. The behavior execution capability of the computing units in this paper is defined as the QoS target of the tenderee.

The behavior execution capability is composed of the basic capability BC. BC can be described with the following three tuples:

$\displaystyle BC\equiv\,<\textit{Action},\textit{Property},\textit{Status}>$

Where Action describes the QoS target of the task; Property represents the value that satisfies the QoS index; Status indicates whether the state of the QoS index is satisfied.

The satisfactory values of the QoS index can be represented by the following two-tuples:

$\displaystyle\textit{Property}\equiv\,<\textit{max\_property},\textit{cur\_% property}>$

max_property is the maximum value that satisfies the index Action; cur_property represents the current value.

3.3 Temporary communication unit

The temporary communication unit comprises a temporary broadcast unit and a temporary monitoring unit.

The monitoring unit in the generalized cluster is temporary. First, the computing unit without participating in the task competition in task release is screened by the generalized cluster as the candidate monitoring set; second, the dominant set with the communication ability to satisfy the threshold value $\theta$ is screened from the monitoring set; then the computing unit with the shortest path and the lowest communication consumption in reaching other nodes is selected as the temporary monitoring unit from the monitoring dominant set.

The temporary monitoring unit is formed with the release of the task and terminates with the completion of the task.

The monitoring unit mainly realizes the following purposes in the process of monitoring the performance of the winning bidder:

(1)
It lightened the burden of the tenderer’s correspondence;
(2)
For the task which cannot be completed due to a unit is apoptotic or withdraws from the alliance, it realized task redistribution.

The working mechanism of the temporary monitoring unit is as follows:

Step1:
Monitoring the status of the winning bidders performing the task;
Step2:
If the winning bidders are performing the tasks then continue listening, repeat Step1 else recycling the task.
Step3:
After the task is recovered, the task is put into the task set. At this time, the task has priority execution.
Step4:
The tenderer bids for the task again.
Step5:
After the bid, the successful bidder will start the task, and The monitoring unit will repeat Step1.

3.4 Task description

Under the generalized cluster, the task is usually a series of activities to be completed by a computing unit, Ma Qiaoyun believes that task is a work to be done to achieve the specific goals [25]. In the task allocation process based on the contract net protocol, the bidder needs to evaluate the task and its ability according to the QoS requirement of the task. Therefore, the reasonable description of the task is the key for the bidder to make a reasonable bidding.

Under the complex generalized cluster, because of the diversity of the computing units, the task has deemed an activity that converts the specific input to the specific output. Input and output reflect the constraints and the result of task execution respectively. The task can be represented by one tuple:

$\displaystyle\textit{Task}\equiv\,<\textit{TaskID},\textit{TaskName},T_{R},O_{% R},\textit{Capability},\textit{Level},\textit{Others}>$ $\displaystyle\textit{Capability}\equiv\,<\textit{Action},\textit{Property}>$ $\displaystyle\textit{Others}\equiv\,<E\_\textit{Date},\textit{Dismantlability}>$

Where TaskID represents the unique identity of the task; TaskName describes the name of the task; $T_{R}$ means the task input set; $O_{R}$ represents the task output set; Capability is the ability information to perform the task QoS requirements; Action in Capability shows the QoS target; Property in Capability stands for the lowest attribute value, Level for the priority level of the task, Others for other needs of the task and $E\_\textit{Date}$ for the deadline of the task; Dismantlability indicates whether the task can be divided again.

4. Extended contract net model based on generalized cluster

4.1 Task allocation framework of extended contract net model

According to the generalized cluster theory, the decision based computing unit is mapped to the tenderee, the task based computing unit to the bidder, and the temporary communication unit to the temporary monitoring unit and the temporary broadcast unit. Besides, the open tendering is adopted, and the design of the bidding mechanism is shown in Fig. 2. The task allocation mechanism of the extended contract net is designed in detail from four stages of tendering, bidding, bid evaluation and task execution.

Figure 2.

Task allocation mechanism of the improved contract net.

(1)

In the tendering stage, the decision based computing unit, the tenderee, sends such information as the detail of the tendering task, the deadline for the bid evaluation and the QoS constraint of tendering to the temporary broadcasting unit, which will send the task bid to the bidder according to the task priority.

(2)

In the bidding stage, after the task based computing unit, the bidder, receives the bidding information, the bidder assesses whether its task execution ability meets the requirements according to the task QoS target requirements. If it is satisfactory, it will bid to the tenderee; otherwise, it will give up and wait for the next task notice.

(3)

In the bid evaluation stage, the bidders form the bidding set after the bid deadline. The tenderee chooses the best bidder from the bidding set as the task executor and sends the notice of award according to the target needs of the task QoS. The successful bidder will join the winner set and complete the winning bid. The winner cannot receive any bid information for other tasks to be processed before completing the task.

(4)

In the task execution stage, the winner will be monitored in real time by the temporary monitoring unit which may reflect the basic situation of the successful bidder who completes the task to the bidder. If an accident happens on the successful bidder under emergency, the temporary monitoring unit will take back the tasks and put them into the task set; when completing the task, the winning bidder withdraws from the winner set and may continue to receive other tendering information of the tasks to be allocated.

4.2 QoS objective function

The requirement of QoS (quality of service) is introduced as the two-way screening constraint between the tenderees and the bidders, and three key indexes in the task allocation process are considered respectively: execution time, degree of trust, and utility.

4.2.1 Time objective function

The time objective function indicates that the tenderee assigns the task to the bidder with the shorter task completion time during task allocation. If the time for the bidder $S_{j}$ to complete the task $T_{i}$ is $t^{d}_{ij}$ , the maximum time to complete the task in the tenderee set is:

$\displaystyle{ms}^{ij}_{\max}={\max_{1\leqslant j\leqslant m}t^{d}_{ij}}$

Similarly, the minimum time to complete the task $T_{i}$ in the tenderee set is:

$\displaystyle{ms}^{ij}_{\min}={\min_{1\leqslant j\leqslant m}t^{d}_{ij}}$

Therefore, the time objective function ${TE}_{ij}$ of the task $T_{i}$ on the bidder $S_{j}$ is:

$\displaystyle{TE}_{ij}=\frac{{ms}^{ij}_{\max}-t^{d}_{ij}+1}{{ms}^{ij}_{\max}-{% ms}^{ij}_{\min}+1}$ (12)

According to the Eq. (12), ${0\leqslant TE}_{ij}\leqslant 1$ , the greater ${TE}_{ij}$ , the shorter the time for the bidder $S_{j}$ to complete the task $T_{i}$ .

4.2.2 Trust objective function

The trust objective function indicates that the tenderee assigns the task to the bidder with a high reliability in task allocation. The maximum reliability of the tenderee in the tendering set is:

$\displaystyle{re}^{ij}_{\max}={\max_{1\leqslant j\leqslant m}R_{j}}$

Similarly, the minimum reliability of the tenderee in the tendering set is:

$\displaystyle{re}^{ij}_{\min}={\min_{1\leqslant j\leqslant m}R_{j}}$

The objective function ${ME}_{ij}$ of the task $T_{i}$ for the bidder $S_{j}$ is:

$\displaystyle{ME}_{ij}=\frac{{re}^{ij}_{\max}-R_{j}+1}{{re}^{ij}_{\max}-{re}^{% ij}_{\min}+1}$ (13)

The Eq. (13) shows that ${0\leqslant ME}_{ij}\leqslant 1$ , the smaller the ${ME}_{ij}$ , the higher the reliability of the bidder $S_{j}$ to complete the task $T_{i}$ .

4.2.3 Utility objective function

The objective function indicates that the tenderee selects the least effective bidder from the bidder set to assign the task in task allocation. If the expenditure utility for the bidder $S_{j}$ to complete the task $T_{i}$ is $c^{d}_{ij}$ , the maximum utility for the tenderee set to complete the task $T_{i}$ is

$\displaystyle\textit{cost}^{ij}_{\max}={\mathop{\max}_{1\leqslant j\leqslant m% }c^{d}_{ij}+{co}^{d}_{ij}}$

On the contrary, the minimum consumption utility required to accomplish the task $T_{i}$ is

$\displaystyle\textit{cost}^{ij}_{\min}={\mathop{\min}_{1\leqslant j\leqslant m% }c^{d}_{ij}+{co}^{d}_{ij}}$

Therefore, the utility function ${CE}_{ij}$ of the bidder $S_{j}$ to accomplish the task $T_{i}$ is

$\displaystyle{CE}_{ij}=\frac{\textit{cost}^{ij}_{\max}-c^{d}_{ij}-{co}^{d}_{ij% }+1}{\textit{cost}^{ij}_{\max}-\textit{cost}^{ij}_{\min}+1}$ (14)

$0\leqslant{CE}_{ij}\leqslant 1$ according to Eq. (14), with greater ${CE}_{ij}$ , the bidder $S_{j}$ will require less utility to complete the task $T_{i}$ .

According to the trust objective function, the time objective function and the utility objective function, the comprehensive evaluation criteria for the tenderees to select the tenderee $S_{j}$ for the task $T_{i}$ are defined as follows:

$\displaystyle\textit{Measure}_{ij}=\alpha\cdot{TE}_{ij}+\beta\cdot{ME}_{ij}+% \gamma\cdot CE_{ij}$ (15)

Where $\alpha$ , $\beta$ and $\gamma$ indicate the time preference, the reliability preference and the utility preference in completing the tasks. According to the formula $0\leqslant\alpha,\beta,\gamma\leqslant 1$ , and $\alpha+\beta+\gamma=1$ , the Eq. (15) shows that the greater the value of the comprehensive evaluation standard $\textit{Measure}_{ij}$ , the more the bidder can meet the QoS requirement based on the task $T_{i}$ . ${\max_{1\leqslant j\leqslant m}\textit{Measure}_{ij}}$ is the winner of the task $T_{i}$ .

4.3 Task assignment algorithm for extended contract net model

4.3.1 Task selection strategy

The task selection strategy (TSS) is to determine the tasks in the current bidding round. The task comes from the unallocated task set $T_{un}(T_{un}\subseteq\textit{Task})$ in the total task. In the task allocation stage, the tenderee chooses the task $T_{\textit{now}}$ to be completed according to the task priority. Therefore, the designed target selection strategy can be expressed as:

$\displaystyle T_{\textit{now}}=\text{mas}(T_{un}(\textit{level})),T_{un}% \subseteq\textit{Task}$

Where level is the priority of the Task. The higher level means the higher the priority, and the higher priority task will be executed preferentially. That is, the task with the highest level in $T_{un}$ is the task to be executed currently.

4.3.2 Tendering strategy

The tendering strategy (TS) is to determine the content of the tender. In the traditional contract net protocol, the tenderee broadcasts the task and sends the tender to the task based compute node in the system. This strategy requires a higher communication ability of the tenderee. Therefore, the temporary broadcasting unit is designed and the most powerful computing unit under the generalized cluster is selected as a temporary broadcast unit to broadcast the task, which may reduce the communication load capacity of the bidder. At the same time, QoS requirements are incorporated into the bid design, to enable the bidder to assess whether its ability meets the QoS needs, in order to screen the bidders.

The tender RfP can be formalized as:

$\displaystyle\textit{RfP}\equiv\,<TI,\textit{QoS},S_{\textit{date}},E_{\textit% {date}}>$ $\displaystyle\textit{QoS}\equiv\,<TE,ME,CE>$

Where $T I$ is the basic information of the tasks and describes the content of the tasks; QoS represents the standard of the service quality required for the target task; $S_{\textit{date}}$ and ${E}_{\textit{date}}$ indicate the start date and the deadline of the bid separately. In QoS, $T E$ is the time constraint for task completion; $M E$ represents the trust constraints required for a task; $C E$ is the utility constraint required for a task.

4.3.3 Bidding strategy

The bidding strategy (BS) is to determine whether the bidder will bid after receiving the tender. After receiving the tender, the bidder will assess its ability and decide whether to bid according to the requirement of the task QoS in the tender. With the satisfactory ability, it will send the bid document to the tenderee; if not, the bid is waived. The bidding process is designed as shown in Fig. 3.

Figure 3.

Bidding strategy diagram of task based compute node.

(1) The content of bid document

The contents of the bidder’s bid document can be formally described as follows:

$\displaystyle\textit{BTB}\equiv\,<\textit{From},\textit{TaskID},\textit{Self}_% {\textit{QoS}}>$ $\displaystyle\textit{Self}_{\textit{QoS}}\equiv\,<\textit{Exp}_{TE},\textit{% Exp}_{ME},\textit{Exp}_{CE}>$

Where the bid document BTB is described in detail. From is the identification of the task based compute node for sending the bid document; TaskID is the task sign of the bid; $\textit{Self}_{\textit{QoS}}$ indicates the QoS index that the bidder promises to meet the QoS requirement. $\textit{Exp}_{TE}$ refers to the expected duration of implementation of the commitment; $\textit{Exp}_{ME}$ indicates the degree of trust of the bidders; $\textit{Exp}_{CE}$ represents the expected utility of the bidders.

(2) Bidding strategy

The specific algorithm of the bidding process is described as follows.

Algorithm name: bidding algorithm
Input:
QoS: Target demand,
$t^{l}_{i}$ : The continuous execution time required for task $T_{i}$ ,
$r^{l}_{i}$ : The degree of trust required for task $T_{i}$ ,
$c^{l}_{i}$ : Target utility provided by task $T_{i}$
Output:
Result: Whether or not to bid
Begin
1 if $t^{e}_{ij}-t^{b}_{ij}\geqslant t^{l}_{i}$ // Assess whether the duration of the execution meets the needs of the task
2 if $R_{j}=\sum^{n}_{i=1}{{td}_{ij}}{\geqslant r}^{l}_{i}$ // If the continuous execution time is met, whether the evaluation trust satisfies the task requirement.
3 if $c^{d}_{ij}+{co}^{d}_{ij}=p_{j}\cdot t^{d}_{ij}+co^{d}_{ij}<c^{l}_{i}$ // If the trust satisfies the needs, whether the evaluation utility satisfies the task requirement.
4 $\textit{Result}\leftarrow\textit{Yes}$ // If the duration, trust and utility meet the task QoS requirement, the bid is available.
send BTB to $T$ // Send the bid document to the tenderee
5 else $\textit{Result}\leftarrow No$ end if // If the utility needs are not met, the bid is abandoned.
6 else $\textit{Result}\leftarrow No$ end if // If the demand for trust is not met, the bid is waived.
7 else $\textit{Result}\leftarrow No$ end if // If the demand for continuous execution time is not satisfied, the bid is waived.
8 return Result

4.3.4 Bid evaluation strategy

The bid evaluation strategy (SDS) selects the best bidder from the received bid documents as the executor of the task and send the notice of award. The specific steps of the winning strategy are listed as follows:

Step1.
Sort out the bid document of the task $T_{i}$ upon the tender deadline and determine the bidding set $B i$ . Suppose the bidder set that fulfills the task $T_{i}$ is $Bi=\{b_{1},b_{2},\dots,b_{k},\dots,b_{n}\}$ and $n$ is the number of the bidders in the bidding set.
Step2.
Evaluate the optimal task based compute nodes that satisfy the QoS target service demand in the bidding set. The detailed bid evaluation strategy of the task $T_{i}$ is shown as follows:

(1)
The priority strategy with the shortest time

For the task $T_{i}$ , according to the urgency of the time required for the completion of the task, the priority strategy with the shortest time is applied to select the best bidder.

$\displaystyle\textit{Eft}=\min_{1\leqslant k\leqslant n}{TE}_{ik}$

${TE}_{ik}$ is the time required by the bidder $b_{k}$ to complete the task $T_{i}$ .
(2)
The priority strategy of the highest trust

For task $T_{i}$ , the tenderee, according to the urgency of the highest trust demand in task completion, chooses the best bidder by the priority strategy of the highest trust.

$\displaystyle\textit{Htr}=\max_{1\leqslant k\leqslant n}{ME}_{ik}$

${ME}_{ik}$ means the reliability for the bidder $b_{k}$ to complete the task $T_{i}$ .
(3)
The priority strategy with minimum utility

For task $T_{i}$ , according to the urgency of the minimum utility to complete the task, the tenderee adopts the least utility priority strategy to select the best bidder, then:

$\displaystyle\textit{Mce}=\max_{1\leqslant k\leqslant n}{CE}_{ik}$

${CE}_{ik}$ means the minimum utility required by the bidder $b_{k}$ to complete the task $T_{i}$ .

The comprehensive bid evaluation strategy is adopted:

$\displaystyle\textit{Measure}_{ik}=\alpha\cdot{TE}_{ij}+\beta\cdot{ME}_{ij}+% \gamma\cdot CE_{ij}$

Where $\alpha$ , $\beta$ and $\gamma$ indicate the time preference, the reliability preference and the utility preference in completing the tasks. In selecting the above bid evaluation strategy, different weighting strategies can be chosen according to the different needs of the task.

Step3.
When the bid evaluation is concluded, the best bidder performing the current task is chosen and sent the notice of award.

The content of the winning bid can be formally described as follows:

$\displaystyle\textit{STB}\equiv<\textit{TaskID},To,TI,\textit{Cost},S_{\textit% {date}},E_{\textit{date}}>$

Where the winning bid STB is described in detail, and TaskID is the identification of the winning bid; $T o$ is the identification of the task based compute node of the winning bid; $T I$ indicates the main content of the task completed; Cost means the utility value of the task provided for the bidder; $S_{\textit{date}}$ represents the latest date to start the task; ${E}_{\textit{date}}$ refers to the latest date to complete the task.

4.3.5 Task execution strategy

The task execution stage (TES) means that the successful bidder starts the task after receiving the notice of award. Because the computing unit in the generalized cluster is unstable, the following 4 cases are considered in the task execution:

Figure 4.

Task execution strategy of case 3.

Case 1:

Carry out the task continuously and accomplish it.

Case 2:

In executing the tasks, if the compute nodes suddenly become apoptotic or detach from the cluster, and the task cannot be completed.

At this point, the temporary monitoring unit takes back the task to the task set and notifies the tenderee that the task is not completed, and it has to wait for re-tendering.

Case 3:

In the alliance to receive tasks, a computing unit is apoptotic or withdraws from the alliance.

At this point, the alliance needs to decide whether the task can be completed within the specified time limit. If it can be completed, the task will continue to be performed.

Otherwise, the latest completion time should be returned to the temporary monitoring unit. The temporary monitoring unit, through consultation and communication with the tenderee, will notify the task performer whether it will continue to perform the task. If it continues, the latest completion time in the winning bid shall be amended and the task will continue to be performed; if it is not allowed to continue, the task will be recovered by the temporary monitoring unit and put into the task set, waiting for the re-tendering. The task execution strategy of case 3 is shown in Fig. 4.

Case 4:

In an alliance to receive tasks, if a unit is apoptotic or withdraws from the alliance, and the task cannot be completed, the temporary monitoring unit will recover the unfinished task, puts it in the task set, notifies the tenderee that the task is not completed and it has to wait for the re-tendering.

Figure 5.

Simulation environment.

5. Experiment

In this study, Netlogo6.0.3 [27, 28] simulation platform is employed to build generalized cluster simulation scenarios and the arithmetic system scenario. In the simulation scenario, the mathematical operation task executed by the computing unit is simulated under the generalized cluster. Furthermore, improved contract net and traditional contract net are coordinated to complete the task assignment.

The experimental parameters are set as follows:

(1)
The simulation experiment was completed on the personal PC of the WIN7 system, Intel Core i5 processor, 3.2GCPU and 4.0GRAM.
(2)
The number of the initial computing units is 50; the number of the tasks to be allocated is 50 to 200; the number of the returned alliances is 2.

The scenario of the test simulation is shown in Fig. 5.

Table 2
50 task execution time comparison

No. Group 1 Group 2 Group 3 No. Group 1 Group 2 Group 3

CNP MCNP CNP MCNP CNP MCNP CNP MCNP CNP MCNP CNP MCNP

1 12 .16728 10 .75933 3 .70079 13 .172 4 .47661 11 .02681 26 140 .9427 140 .5975 140 .6867 148 .7733 141 .6895 182 .4691

2 23 .99241 19 .31387 4 .20814 16 .57827 8 .41792 17 .41103 27 147 .8449 154 .0836 151 .0207 162 .938 145 .2055 183 .3475

3 37 .46958 22 .99142 4 .20814 19 .05773 13 .29979 28 .11066 28 157 .7651 160 .8293 163 .3339 172 .4208 147 .4487 182 .306

4 44 .47484 32 .21446 17 .68862 32 .7513 24 .49553 36 .08762 29 160 .2128 161 .0291 171 .2339 179 .8707 151 .0019 180 .3987

5 49 .07264 38 .98561 15 .81299 38 .99702 26 .05541 34 .58412 30 174 .6643 169 .4389 174 .8407 193 .3552 160 .3107 181 .7047

6 56 .38489 40 .27361 21 .13301 40 .70687 25 .6034 42 .16157 31 185 .2383 178 .0844 176 .1811 195 .6299 169 .7772 187 .9777

7 70 .00726 39 .07802 24 .87931 44 .68976 38 .40086 50 .3186 32 191 .1798 178 .3412 190 .1281 199 .4201 174 .6679 195 .9255

8 73 .37651 40 .47703 26 .39858 57 .78129 41 .81184 56 .46933 33 193 .7413 191 .41 201 .8126 197 .3466 183 .1809 205 .0633

9 83 .60603 54 .86731 34 .75996 66 .00586 47 .73815 66 .91957 34 199 .8011 196 .1073 204 .5408 195 .2241 192 .2211 213 .1208

10 87 .56644 60 .33281 41 .82281 74 .19536 56 .86323 79 .5152 35 200 .4216 198 .9639 210 .2931 206 .286 190 .5912 214 .9263

11 90 .61192 72 .617 51 .55807 72 .94677 58 .65597 79 .40488 36 202 .0306 198 .9612 210 .1939 206 .6404 202 .8556 213 .0436

12 103 .1013 74 .80856 51 .65576 72 .94507 67 .08762 84 .12278 37 202 .9143 200 .9264 213 .2541 210 .8522 206 .4593 223 .4923

13 107 .377 75 .71931 57 .20429 75 .47403 71 .14972 94 .08988 38 204 .9654 199 .682 216 .3411 210 .7854 215 .4058 232 .0652

14 111 .1821 74 .34929 61 .75704 86 .24017 80 .37284 96 .2918 39 210 .4841 201 .535 224 .0094 221 .0164 224 .9047 230 .5004

15 111 .0262 73 .06357 61 .94046 88 .13587 86 .07657 101 .4304 40 217 .7112 199 .3302 233 .4352 235 .4773 229 .5799 231 .3757

16 111 .2517 72 .69571 66 .0795 92 .70806 89 .2649 102 .4283 41 228 .3106 203 .9612 234 .3731 248 .5082 230 .3491 239 .8618

17 112 .0703 86 .21004 66 .39345 97 .60533 93 .8508 100 .0462 42 228 .8419 206 .7004 245 .1325 246 .239 231 .1206 242 .5634

18 115 .0631 98 .69806 70 .56794 103 .0556 96 .95473 109 .8358 43 239 .6258 220 .2455 251 .0583 247 .1469 232 .2401 247 .8909

19 115 .4627 107 .1168 75 .41944 107 .7746 99 .2724 115 .0039 44 248 .8296 226 .8713 249 .8308 256 .6708 233 .2908 245 .9522

20 117 .5369 114 .7707 85 .01555 118 .2648 103 .5624 128 .4655 45 252 .6372 225 .4739 260 .5094 260 .6034 245 .7387 254 .9026

21 119 .0018 117 .3027 97 .16495 130 .0734 105 .7407 139 .87 46 250 .9031 232 .1641 271 .1995 260 .7244 254 .9805 254 .7806

22 125 .7286 130 .1869 104 .8525 139 .6885 114 .5351 148 .5548 47 257 .4592 238 .5207 275 .2462 263 .8204 265 .6843 265 .0652

23 128 .6927 133 .8711 116 .7592 139 .6571 124 .3597 148 .137 48 259 .3147 244 .584 278 .8922 263 .7544 272 .6605 274 .4834

24 129 .1186 138 .5235 127 .1325 143 .2344 123 .6815 159 .7646 49 266 .241 254 .9781 287 .4288 276 .0951 283 .1775 272 .1886

25 133 .7414 138 .8812 128 .4449 149 .9599 135 .901 170 .7362 50 273 .8466 253 .6597 286 .4878 279 .8144 290 .8327 271 .5666

By taking the execution tasks as variables, the total execution time of the tasks is investigated under the task allocation strategy of the traditional contract net and the improved contract net respectively. In view of the randomness of the algorithm, the experiment was carried out by using the traditional contract net protocol and the improved contract net protocol as the simulation environment, three sets of data were randomly selected in each experiment. When there are 50 tasks in a Generalized Cluster, the execution time of MCNP and CNP tasks is shown in Table 2, the change trend of the task execution time is shown in Fig. 6.

In Fig. 6, CNP indicates the traditional contract net protocol and MCNP indicates the improved contract net protocol. When the number of tasks is less than 50, the time of the two methods is almost same. Because the two-way QoS evaluation is needed by the MCNP, the advantage of the fast speed is not shown when the number of tasks is less than 50.

Figure 6.
50 task execution time trends.

When the number of tasks is 100, the time change trend of CNP and MCNP execution tasks is shown in Fig. 7. As the number of tasks increases, the execution time of MCNP is gradually separated from the task execution time of CNP.

Figure 7.
100 task execution time trends.

Figure 8.
200 task execution time trends.

When the number of tasks is 200, the change trend of the task execution time of CNP and MCNP is shown in Fig. 8. With the increase of the number of tasks, the time of completing the total task by the improved contract net is significantly superior to that of the traditional contract net when the number of tasks exceeds 50. Therefore, the improved contract net can improve the efficiency of task completion as well as the quality of task completion.
6. Conclusion

No.	Group 1	Group 2	Group 3	No.	Group 1	Group 2	Group 3
	CNP	MCNP	CNP	MCNP	CNP	MCNP		CNP	MCNP	CNP	MCNP	CNP	MCNP
1	12	.16728	10	.75933	3	.70079	13	.172	4	.47661	11	.02681	26	140	.9427	140	.5975	140	.6867	148	.7733	141	.6895	182	.4691
2	23	.99241	19	.31387	4	.20814	16	.57827	8	.41792	17	.41103	27	147	.8449	154	.0836	151	.0207	162	.938	145	.2055	183	.3475
3	37	.46958	22	.99142	4	.20814	19	.05773	13	.29979	28	.11066	28	157	.7651	160	.8293	163	.3339	172	.4208	147	.4487	182	.306
4	44	.47484	32	.21446	17	.68862	32	.7513	24	.49553	36	.08762	29	160	.2128	161	.0291	171	.2339	179	.8707	151	.0019	180	.3987
5	49	.07264	38	.98561	15	.81299	38	.99702	26	.05541	34	.58412	30	174	.6643	169	.4389	174	.8407	193	.3552	160	.3107	181	.7047
6	56	.38489	40	.27361	21	.13301	40	.70687	25	.6034	42	.16157	31	185	.2383	178	.0844	176	.1811	195	.6299	169	.7772	187	.9777
7	70	.00726	39	.07802	24	.87931	44	.68976	38	.40086	50	.3186	32	191	.1798	178	.3412	190	.1281	199	.4201	174	.6679	195	.9255
8	73	.37651	40	.47703	26	.39858	57	.78129	41	.81184	56	.46933	33	193	.7413	191	.41	201	.8126	197	.3466	183	.1809	205	.0633
9	83	.60603	54	.86731	34	.75996	66	.00586	47	.73815	66	.91957	34	199	.8011	196	.1073	204	.5408	195	.2241	192	.2211	213	.1208
10	87	.56644	60	.33281	41	.82281	74	.19536	56	.86323	79	.5152	35	200	.4216	198	.9639	210	.2931	206	.286	190	.5912	214	.9263
11	90	.61192	72	.617	51	.55807	72	.94677	58	.65597	79	.40488	36	202	.0306	198	.9612	210	.1939	206	.6404	202	.8556	213	.0436
12	103	.1013	74	.80856	51	.65576	72	.94507	67	.08762	84	.12278	37	202	.9143	200	.9264	213	.2541	210	.8522	206	.4593	223	.4923
13	107	.377	75	.71931	57	.20429	75	.47403	71	.14972	94	.08988	38	204	.9654	199	.682	216	.3411	210	.7854	215	.4058	232	.0652
14	111	.1821	74	.34929	61	.75704	86	.24017	80	.37284	96	.2918	39	210	.4841	201	.535	224	.0094	221	.0164	224	.9047	230	.5004
15	111	.0262	73	.06357	61	.94046	88	.13587	86	.07657	101	.4304	40	217	.7112	199	.3302	233	.4352	235	.4773	229	.5799	231	.3757
16	111	.2517	72	.69571	66	.0795	92	.70806	89	.2649	102	.4283	41	228	.3106	203	.9612	234	.3731	248	.5082	230	.3491	239	.8618
17	112	.0703	86	.21004	66	.39345	97	.60533	93	.8508	100	.0462	42	228	.8419	206	.7004	245	.1325	246	.239	231	.1206	242	.5634
18	115	.0631	98	.69806	70	.56794	103	.0556	96	.95473	109	.8358	43	239	.6258	220	.2455	251	.0583	247	.1469	232	.2401	247	.8909
19	115	.4627	107	.1168	75	.41944	107	.7746	99	.2724	115	.0039	44	248	.8296	226	.8713	249	.8308	256	.6708	233	.2908	245	.9522
20	117	.5369	114	.7707	85	.01555	118	.2648	103	.5624	128	.4655	45	252	.6372	225	.4739	260	.5094	260	.6034	245	.7387	254	.9026
21	119	.0018	117	.3027	97	.16495	130	.0734	105	.7407	139	.87	46	250	.9031	232	.1641	271	.1995	260	.7244	254	.9805	254	.7806
22	125	.7286	130	.1869	104	.8525	139	.6885	114	.5351	148	.5548	47	257	.4592	238	.5207	275	.2462	263	.8204	265	.6843	265	.0652
23	128	.6927	133	.8711	116	.7592	139	.6571	124	.3597	148	.137	48	259	.3147	244	.584	278	.8922	263	.7544	272	.6605	274	.4834
24	129	.1186	138	.5235	127	.1325	143	.2344	123	.6815	159	.7646	49	266	.241	254	.9781	287	.4288	276	.0951	283	.1775	272	.1886
25	133	.7414	138	.8812	128	.4449	149	.9599	135	.901	170	.7362	50	273	.8466	253	.6597	286	.4878	279	.8144	290	.8327	271	.5666

The task allocation based on the traditional contract net has some deficiencies, such as the low communication efficiency and the inefficient task completion quality and unable to handle outstanding remaining tasks under the generalized cluster. Therefore, we propose an improved contract net model and design a temporary monitoring unit to broadcast and negotiate the task in this paper, which improves the communication efficiency and remains tasks by real-time monitoring. Furthermore, the QoS bilateral constraint is introduced to improve the task completion quality, and the task priority is designed to reduce the task congestion rate. The simulation results show that the improved model can reduce the total time of task completion when the number of tasks exceeds 50, improve the efficiency of task execution and the quality of task completion.

However, the following two issues are not discussed in depth in the study.

(1)

The allocation algorithm for task reallocation caused by the emergency of the computing unit.

(2)

The rational utilization of the surplus resources when the computing units execute the tasks under the generalized cluster.

Therefore, the above issues will be studied in the future work.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China under Grants 51774090, 61170132, 21306022, the Natural Science Foundation of Heilongjiang Province under Grant F2015020, and the Fundamental Research Funds for the Northeast Petroleum University under Grants NEPU80142, NEPU90115. The authors would like to express their gratitude to the anonymous reviewers, whose helpful comments and suggestions were advantageous to improve the quality of this paper.

References

Ebling

M.R.

and Want

, Pervasive computing revisited, IEEE Pervasive Computing 16(3) (2017), 17–19.

Saha

and Mukherjee

, Pervasive computing: a paradigm for the 21st century, Computer 36(3) (2003), 25–31.

Wenhua

Yepang

Chang

X.U.

and Cheung

S.C.

, A survey on dependability improvement techniques for pervasive computing systems, Science China Information Sciences 58(5) (2015), 1–14.

Liu

Y.P.

Cheung

S.C.

Cao

and Lv

, Towards context consistency by concurrent checking for internet ware applications, Science China Information Sciences 56(8) (2013), 1–20.

Liu

Jin

and Wang

, Agent-based load balancing on homogeneous minigrids: macroscopic modeling and characterization, IEEE Transactions on Parallel and Distributed Systems 16(7) (2005), 586–598.

Chow

K.P.

and Kwok

Y.K.

, On load balancing for distributed multiagent computing, IEEE Transactions on Parallel and Distributed Systems 13(8) (2002), 787–801.

Jiang

and Lin

, Decision making of networked multiagent systems for interaction structures, IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans 41(6) (2011), 1107–1121.

Fujita

and Lesser

V.R.

, Centralized task distribution in the presence of uncertainty and time deadlines, Information Processing Society of Japan (IPSJ) (1996), 147–148.

Rui

and Wang

, Research on the multi-platform cooperative guidance tasks allocation based on Contract Net Protocol, International Colloquium on Computing, Communication, Control, & Management (2012), 561–569.

10.

Qin

and Kan

, Production dynamic scheduling method based on improved contract net of multi-agent, Intelligence Computation and Evolutionary Computation (2013), 929–936.

11.

Amador

Okamoto

and Zivan

, Dynamic multi-agent task allocation with spatial and temporal constraints, in: International Conference on Autonomous Agents & Multi-agent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2014.

12.

Cao

Zhou

and Tan

, A Hierarchical Task Allocation Method Based on Task Case and its Application to Multi-Robot Hunting, in: International Conference on Intelligent Networks & Intelligent Systems, 2008, pp. 689–692.

13.

Owliya

Saadat

Jules

G.G.

Goharian

and Anane

, Agent-based interaction protocols and topologies for manufacturing task allocation, IEEE Transactions on Systems, Man, and Cybernetics: Systems 43(1) (2013), 38–52.

14.

Hayano

Hamada

and Sugawara

, Role and member selection in team formation using resource estimation for large-scale multi-agent systems, Neurocomputing 146 (2014), 164–172.

15.

Liekna

Lavendelis

and Grabovskis

, Experimental analysis of contract net protocol in multi-robot task allocation, Applied Computer Systems 13(1) (2012), 6–14.

16.

Liang

and Kang

, A novel task optimal allocation approach based on contract net protocol for agent-oriented UUV swarm system modeling, Optik – International Journal for Light and Electron Optics 127(8) (2016), 3928–3933.

17.

Vytelingum

Cliff

and Jennings

N.R.

, Strategic bidding in continuous double auctions, Artificial Intelligence 172(14) (2008), 1700–1729.

18.

Feng

Chen

Peng

Chen

and Li

, A method of distributed multi-satellite mission scheduling based on improved contract net protocol, in: International Conference on Natural Computation, IEEE, 2015, pp. 1062–1068.

19.

Tang

and Parker

L.E.

, A Complete Methodology for Generating Multi-Robot Task Solutions using ASyMTRe-D and Market-Based Task Allocation, in: IEEE International Conference on Robotics and Automation, IEEE, 2007, pp. 3351–3358.

20.

Zhang

Wang

Zhao

et al., Semi-autonomous multi-Agent task allocation method based on extended contract net and mental model, Computer Integrated Manufacturing Systems 21(11) (2015), 2885–2892.

21.

Jian

Shouyi

and Fanglin

, A collaboration algorithm for computer generated forces based on multi-agent systems, Computer Simulation 27(2) (2010), 113–117.

22.

Zhang

G.S.

Jiang

C.J.

Sha

et al., Research of contract net model based on cost timed Petri net, Journal of System Simulation 20(20) (2008), 5438–5437.

23.

Liang

H.T.

and Ju

K.F.

, Task allocation modeling for agent-oriented UUV collaborative system, Journal of System Simulation 27(9) (2015), 2075–2082.

24.

Sang

Z.L.

Tang

D.B.

and Zheng

, Improved contract net protocol based on cycle period and its application in job shop AGV scheduling, Journal of Nanjing University of Aeronautics & Astronautics 48(6) (2016), 895–900.

25.

Liu

and Zhang

Y.D.

, Mulit-Agent dynamic task allocation based on improved contract net protocol, Journal of Shandong University (Engineering Science) 46(2) (2016), 51–56.

26.

Q.Y.

, Research on dynamic task allocation based on MAS, Wuhan: Huazhong University of Science and Technology, 2006.

27.

Sklar

, NetLogo, a multi-agent simulation environment, Artificial Life 13(3) (2014), 303–311.

28.

Kahn

, An Introduction to agent-based modeling: modeling natural, social, and engineered complex systems with netlogo, Physics Today 68(8) (2015), 55–55.