1042 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, VOL. 42, NO. 5, SEPTEMBER 2012
a well-known task sharing protocol in which each agent
in a network can be a manager or a contractor at different
times or for different tasks [31]. However, managers
in this method also need to know the information of
negotiated agents. In summary, agent status informa-
tion needs to be acquired in a timely manner for these
related works.
3) Task allocation with uncertain information.
There are some related studies considering task al-
location with uncertain and incomplete information. In
previous approaches, social or economics techniques are
used, such as negotiation, bidding/auction, trust, game
theory, etc. For example, Kraus et al. [17] present a
distributed approach in which a protocol is developed
to enable agents to negotiate and form coalitions to
execute tasks with uncertain heterogeneous information.
Ramchurn et al. [18] present trust-based mechanisms of
task allocation in the presence of execution uncertainty,
which take into account the trust between agents when al-
locating tasks. Mataric et al. [19] use the bidding/auction
mechanism to perform task allocation in uncertain en-
vironments. Game theory is used in the task allocation
of some heterogeneous distributed systems in which the
complete information of agent peers is unknown. For
example, Grosu and Chronopoulos [21] present a game-
theoretic framework for obtaining a user-optimal load
balancing scheme in heterogeneous distributed systems.
Moreover, in multirobot systems, a dynamic task allo-
cation mechanism is investigated, which allows agents
to change their behavior in response to environmental
changes or other agents’ actions to improve overall sys-
tem performance [20]. Such a dynamic allocation mech-
anism needs agents to have sensing and decision-making
abilities.
In summary, the aforementioned approaches may bring
about heavy costs for agents’ computing and communi-
cation, which may influence overall system performance,
particularly when the number of tasks is high.
4) Load balancing in task allocation.
If too many tasks are allocated to certain agents, the
tasks may be delayed and will not receive quick re-
sponses. To minimize the amount of time that tasks re-
main with an agent, tasks may be switched to other agents
with lower task loads, which is called load balancing.
Liu et al. [1] present a macroscopic characterization of
agent-based load balancing, in which complete informa-
tion about the number and size of task teams queuing for
agents is necessary. Chow and Kwok [32] investigate load
balancing for distributed multiagent computing, in which
a novel communication-based load balancing algorithm
is proposed by associating a credit value with each agent;
the credit of an agent depends on its current situation,
such as its affinity to a machine, its current workload,
its communication behavior, etc. Schaerf et al. [12] study
adaptive load balancing, in which information on global
resource distribution must be known to make global
optimal resource selections. Dhakal et al. [33] present a
regeneration-theory approach to dynamic load balancing
in distributed systems in the presence of delays, in which
heterogeneity in the processing rates of the nodes is taken
into account.
From above, we can see that load balancing is an
important idea for the allocation of multiple tasks, where
the number of tasks queuing for an agent is the determi-
native factor of the agent’s rights in future task allocation.
If there are too many tasks queuing for an agent, the
probability of the agent getting new tasks will be reduced
[1]. Therefore, the previous load balancing method of task
allocation accords with the adage “winner does not take
all” [34].
5) Our contribution.
In comparison with the related work, our work makes
the following contributions.
a) Previous load balancing methods based on the “winner
does not take all” theory can effectively reduce the
waiting time of tasks at agents [1]. In contrast to previ-
ous work, our “rich get richer” model can effectively
reduce the communication time of agents attempting
to access resources within the network. In fact, we
combine “rich get richer” and “winner does not take
all” to implement a compromise between preferential
attachment and load balancing, which can achieve
better performance than single preferential attachment
while there are too many waiting tasks.
b) Previous resource-based task allocation and load bal-
ancing methods are often premised on the assumption
that the resources needed by the tasks and resources
available from the agents are known; therefore, each
time that the task allocation is implemented, accurate
resource distribution information needs to be acquired
timely from the system [6]. In contrast with the previ-
ous work, our model is implemented by simply relying
on agents’ experiences of executing tasks and frees
task allocation from knowing the status of available
resources. Our model applies well to large dynamic
NMASs, in which it is difficult to obtain accurate
resource status information timely.
c) Although there are some related studies on the task
allocation with uncertain information, they may bring
about heavy costs to the agents’ computing and com-
munication, which may influence overall system per-
formance, particularly when the number of tasks is
high. Our approach avoids bringing about heavy costs
for agents’ computing and communication because it
is implemented by simply relying on agents’ experi-
ences of executing tasks.
III. NMASs W
ITH RESOURCE CACHING
A. Resource Caching in Multiagent Networks
In previous benchmark work on resource caching, two typi-
cal methods are used: One is plain caching, which means that
resource replicas are placed at the requesting agents [35], and
the other is intermediate caching, which means that resource
replicas are placed at intermediate agents (the agents between
a requesting agent and the agent that holds the requested