Now, it is assumed that agent a
j
is negotiated by a
i
, the set
of resources owned by a
j
is R
aj
.Ifa
j
has any resources that
are requested by a
i
to implement t, then the set of resources
that a
j
can lend to a
i
for implementing task t is
R
t
a
j
!a
i
¼ rjr 2 R
a
j
^ r 2 R
t
a
i
no
: ð2Þ
Thus, the set of lacking resources of a
i
to implement t will
be reduced as
R
t
a
i
¼ R
t
a
i
R
t
a
j
!a
i
¼ R
t
a
i
R
a
j
: ð3Þ
The initiator agent a
i
will negotiate with the physically
contextual agents according to the PCR-NT,untilall
requested resources are satisfied. The negotiation process
is shown as Algorithm 1.
Algorithm 1. Physically contextual resource negotiation of
agent a:
//a is the initiator agent, A is the physical context of a//
1) Set the tags for all agents in A to 0 initially;
2) Create QueueðQÞ;
3) Insert Queue ðQ; aÞ;
4) Set the tag of a to 1;
5) b ¼ 0;
6) A
t
¼fag; /*The allocated agent set for task t*/
7)
R
t
a
¼ R
t
R
a
; /*The lacking resources of agent a to
implement task t*/
8) If
R
t
a
¼¼ fg, then b ¼ 1; /*Agent a can provide all
resources to implement task t*/
9) While (ð!EmptyQueue ðQÞÞ and ðb ¼¼ 0Þ) do:
9.1) aout ¼ Out QueueðQÞ;
9.2) R
0
¼ R
t
a
R
aout
;
9.3) If R
0
6¼ R
t
a
, then: /*Agent aout can satisfy some
requests of a*/
9.3.1)
R
t
a
¼ R
t
a
R
aout
; /*Agent a obtains resources
from aout to implement t*/
9.3.2) A
t
¼ A
t
[faoutg;
9.4) If
R
t
a
¼¼ fg, then b ¼ 1; /*All resources for
implementing t are satisfied*/
9.5) For 8alocal 2 L
aout
:/*L
aout
is the set of all physical
neighbors of aout*/
if the tag of alocal is 0, then: /*If agent alocal was
not negotiated by a before*/
9.5.1) Insert Queue ðQ; alocalÞ;
9.5.2) Set the tag of alocal to 1;
10) If ðb ¼¼ 1Þ, then Return ðA
t
Þ /*All resources for
implementing t are satisfied*/
else Return (False);
11) End.
Theorem 1. If all resources for implementing task t can be
satisfied by using Algorithm 1, the total communication cost
between the initiator agent and the physically response agents
is the minimum.
Proof. Let a
i
be the initiator agent and the set of lacking
resources of a
i
to implement t be R
t
a
i
. If Algorithm 1 is
used, the set of response agents is A
ðA
¼ A
t
a
i
Þ, and
the total communication cost between a
i
and A
is C
.
Now, if there is a set of agents A
0
, A
0
6¼ A
, which can
provide
R
t
a
i
, and the total communication cost between a
i
and A
0
is C
0
;ifC
0
<C
, it denotes that there are any
agents with higher gradations that provide the required
resources in
R
t
a
i
, but the lower gradation agents with
required resources do not provide the required resources
in
R
t
a
i
. Obviously, such situation cannot take place in
Algorithm 1. Therefore, we have Theorem 1. tu
Example 1. Fig. 2 is an example for constructing the
PCR-NT, where a
22
is the initiator agent. In Fig. 2, the
set of resources owned by agent a
22
is fr
1
;r
2
;r
3
;r
3
g.
Now, we let a task t be allocated to a
22
, and the
resources requested by t be fr
1
;r
1
;r
2
;r
2
;r
3
;r
3
;r
3
;r
3
g;
obviously, a
22
lacks the resources fr
1
;r
2
;r
3
;r
3
g.At
first, a
22
negotiates with a
12
and obtains the requested
resources fr
1
;r
3
g; second, a
22
negotiates with a
21
and
obtains the requested resources fr
2
g;third,a
22
negotiates with a
23
but obtains no requested resources;
at last, a
22
negotiates with a
32
and obt ains the
requested resources fr
3
g; now, the requested resources
of a
22
to implement t are all satisfied. Therefore, the
agents fa
22
;a
12
;a
21
;a
32
g will implement task t corpo-
rately. The negotiation process is shown in Fig. 3.
JIANG AND JIANG: CONTEXTUAL RESOURCE NEGOTIATION-BASED TASK ALLOCATION AND LOAD BALANCING IN COMPLEX SOFTWARE... 643
Fig. 2. An example for constructing the PCR-NT.
Authorized licensed use limited to: Nanjing Southeast University. Downloaded on April 4, 2009 at 23:26 from IEEE Xplore. Restrictions apply.