Ocena wydajności systemów wieloagentowych

Technologie agentowe wspierają rozwój oprogramowania komercyjnego i przemysłowego, charakteryzującego się dużymi rozmiarami i złożonością funkcjonalną. Jest to możliwe dzięki paradygmatom systemu wieloagentowego (ang. MultiAgents System- MAS), które określają elastyczność oprogramowania w przystosowywaniu się do zmian środowiska, w sposobie realizacji postawionych zadań oraz w możliwości rozszerzania liczby spełnianych funkcji, w możliwości przemieszczania się zarówno danych, jak i programów itd. Podstawowe znaczenie w wytwarzaniu oprogramowania wieloagentowego odgrywają możliwości posiadanych narzędzi programistycznych wspierających ten proces. Znaczenie takich narzędzi wynika z faktu, że tworzenie oprogramowania wieloagentowego charakteryzuje się dużą złożonością procesów formułowania wymagań, analizy, projektowania i tworzenia wykonywalnej postaci oprogramowania. Jednym z podstawowych typów aplikacji tworzonych przez projektantów oprogramowania wieloagentowego są systemy wyszukiwania informacji w heterogenicznych środowiskach rozproszonych, gdzie informacja przechowywana jest w wielu formatach: relacyjnych baz danych, baz wiedzy, programów, HTML, XML, itp. Pozyskiwanie właściwej informacji wymaga od systemów MAS: analizowania danych, odrzucania bezużytecznej informacji oraz odtwarzania niekompletnej informacji.

Podstawowe cechy architektury systemów wieloagentowych są rozwijane w kierunku wspierania wydajności procesów dystrybucji, pozyskiwania i odzyskiwania informacji w środowisku rozproszonym. Prowadzi to do tworzenia systemów zawierających agentów o zróżnicowanych cechach: od agentów posiadających pełną wiedzę (ang. Fat Agents) - Grubych Agentów, do agentów z wiedzą ograniczoną (ang. Thin Agents) -Cienkich Agentów, poruszających się w sieci. Taka organizacja systemu wieloagentowego redukuje złożoność komunikacji z kwadratowej do liniowej [CGM2002] dzięki ograniczeniu redundancji w przesyłanej informacji. Wiedza nabyta przez Cienkich Agentów jest gromadzona w dedykowanym podsystemie, pełniącym często rolę systemu planowania działań agentów z wiedzą ograniczoną (podstawową).

Specyficzną cechą systemów wieloagentowych jest komunikacja realizowana współbieżnie w środowisku rozproszonym. Protokół komunikacji jest realizowany za pomocą zbiorów przesyłanych komunikatów, zwanych często konwersacjami (ang. Conversations). Zakłada się przy projektowaniu protokołów komunikacji, że: środowisko, w którym działa system, jest środowiskiem zamkniętym, zachowanie agenta ma charakter deterministyczny, agenty komunikują się za pomocą konwersacji i mogą one wykonywać wiele ról oraz brać udział w wielu konwersacjach w tym samym czasie, każda konwersacja może rozpoczynać się wewnątrz innej konwersacji oraz zmiany w środowisku rozproszonym mogą wpłynąć niekorzystnie na przebieg konwersacji.

Ważną rolę w projektowaniu systemów wieloagentowych pełni język meta-UML [OVDPB2001], [FIPA], [DWS2001], który wspiera rozwojowy charakter tworzonego oprogramowania począwszy od etapu zbierania wymagań i definiowania celów, do etapów analizy, projektowania i implementacji. Cechą charakterystyczną jest zastosowanie diagramów klas do definiowania typów agentów oraz diagramów sekwencji i diagramów stanów do projektowania protokołów komunikacji.

W systemach wieloagentowych jednym z podstawowych problemów jest zagadnienie czasu dostarczania odpowiedzi na żądania formułowane do tych systemów. Na ten czas składają się czasy aktywności agentów oraz czasy komunikacji między nimi. W literaturze omawiane są rezultaty badania wydajności następujących systemów wieloagentowych: ZEUS [CACM2002], JADE [CACM2002], SkeletonAgent [CACM2002], ACORN [CGM2002], Aglety IBM [DKS2001], [FS], [JI2001], [YN1999], Concordia [DKS2001], [JI2001], Voyager [DKS2001], [JI2001]. Badane są następujące charakterystyki: czas odpowiedzi w funkcji liczby żądanych dokumentów [CACM2002], średni czas generowania nowego agenta w funkcji całkowitej liczby tworzonych agentów, średni czas na wysłanie jednego komunikatu między agentami w funkcji liczby komunikatów, średni czas na synchronizacje między dwoma agentami w funkcji liczby synchronizacji [DKS2001], czas tworzenia grupy agentów w funkcji liczby agentów, liczby słów kluczowych na jednego agenta [CGM2002], czas odpowiedzi w zależności od czasu przetwarzania na serwerze i wielkości katalogu, liczby punktów (shops) odwiedzanych przez mobilnego agenta [JI2001]. W omawianych artykułach prezentowane są wyniki badań istniejących MAS. W projektowaniu nowych systemów z wymaganiami na wydajność niezbędne jest uwzględnianie wymagań wydajnościowych na wszystkich etapach cyklu życia systemów. Projektowaniu systemów z wymaganiami na wydajność służy inżynieria wydajności oprogramowania [S1990].

W metodologii bazującej na inżynierii wydajności oprogramowania, wymagania czasowe traktowane są we wszystkich fazach cyklu życia systemu. Trudno podczas początkowych faz (specyfikacji wymagań, analizy, projektu) dysponować dokładnymi oszacowaniami, jednak należy dążyć do uzyskania wstępnych ocen wydajności. Można to robić z pomocą ocen wydajności istniejących składowych oprogramowania, które będą wkomponowane w opracowywany system bez zmian lub z modyfikacjami. Oceny takie powinny być przeskalowane do stosowanego w projekcie sprzętu i systemu operacyjnego. Ponadto, bardzo ważna jest rola modelowania tych fragmentów systemu, dla których trudno znaleźć ich pierwowzory. Analiza wydajnościowa we wczesnych fazach cyklu życia jest zwykle oparta na modelowaniu systemu, czy jego fragmentów z parametrami czasowymi uzyskanymi na podstawie ocen istniejącego oprogramowania lub intuicji projektantów. Stąd, w fazach tych niezbędne są modele wydajnościowe. Analiza spełniania wymagań czasowych przez projektowany system w znacznej części oparta jest na modelach dynamicznych. W języku UML, do modelowania dynamiki systemów zastosowano mapy stanów. Zatem, w zakresie modeli czasowych w projektowaniu obiektowym, szczególna jest rola wydajnościowych rozszerzeń map stanów. Mapy takie przedstawiono w pracach [BHM2001], [BHM2003], gdzie zastosowano je do oceny wydajności protokołu transportowego do transmisji mediów ciągłych [BHM2001] oraz do analizy sygnalizacji w sieciach ATM [BHM2003].

Struktura rozdziału jest następująca. W podrozdziale drugim przedstawiono system, dla którego prowadzona jest analiza wydajności. W podrozdziale następnym omówiono wydajnościowe mapy stanów. W podrozdziale czwartym zaprezentowano model wydajnościowy badanego systemu. Następnie przedstawiono wyniki eksperymentów i ich interpretacje. Całość zakończona jest podsumowaniem.

Wybrano system wieloagentowy FIPA (ang. The Foundation for Intelligent Agents) wspierający specyfikację i tworzenie oprogramowania o charakterze wieloagentowym [FIPA]. Na rysunku 1. przedstawiono model tego systemu, który prezentuje środowisko działania Agentów FIPA, wyspecjalizowanych w czynnościach niezbędnych do racjonalnego działania w środowisku rozproszonym: tworzenie, działanie i usuwanie agentów. Komponenty DF (ang. The Directory Facilitator), AMS (ang. Agent Management System), ACC (ang. Agent Communicator Channel) oraz MTS (ang. Message Transport System) są specyficznymi typami agentów, które wspierają zarządzanie agentami aplikacji. Agent jest procesem obliczeniowym, który reprezentuje autonomiczne i komunikacyjne funkcjonalności aplikacji, posiada umiejętności istnienia w organizacji składającej się z innych agentów. MTS jest systemem komunikacji między różnymi Platformami Agentów (AP). FIPA wspiera komunikację między agentami pochodzących z AP działających w pojedynczych procesach, zawierających wątki, oraz z w pełni rozproszonych platform, opartych na otwartych środowiskach sieciowych FIPA dostarcza interfejs programisty oraz różne ułatwienia przy tworzeniu oprogramowania.

Na rysunku 2. przedstawiono przykład fizycznej realizacji komunikacji między trzema agentami o następujących AID: Mngr, Bidder_1 oraz Searcher_1. Komunikacja między agentami jest określana za pomocą protokołu interakcji IP (ang. Interaction Protocol). System FIPA oferuje zestaw wzorców protokołów, dedykowanych różnym typowym aplikacjom oraz wspiera projektowanie protokołów użytkownika na podstawie przyjętych kryteriów. Protokół interakcji zawiera typowe elementy: obsługę wyjątków, reakcję na: gubienie komunikatów, odrzucanie komunikatów, przekroczenia czasu, kasowanie komunikatu itp. Protokoły interakcji (IP) są definiowane za pomocą języków zgromadzonych w Systemowej Bibliotece Języków Protokołów Interakcji (ang. FIPA Content Language Library). Wzorce protokołów znajdują się w Systemowej Bibliotece Protokołów Interakcji (ang. FIPA Interaction Protocol Library Maintenace). Przy tworzeniu nowych protokołów interakcji należy przyjąć następujące kryteria: do projektowania protokołu należy użyć języka AUML [OVDPB2001], należy starannie udokumentować nowy protokół, wykazać jego reprezentatywność.

Podstawowym językiem modelowania systemów wieloagentowych jest język UML wspierający budowę modeli:

• przypadków użycia, modelujących zewnętrzne wymagania stawiane aplikacji

• statycznych, począwszy od modelu klas agentów w fazie analizy i projektowania, a skończywszy na modelu pakietów (poziom logiczny implementacji) i modelu komponentów (poziom fizyczny implementacji)

• dynamicznych: diagramy sekwencji i współpracy, diagramy stanów oraz diagramy aktywności.

Do opisania ograniczeń, niezmienników, warunków przed- i po- każdej z operacji, ścieżek nawigacji używa się języka OCL (ang. Object Constraint Language). W systemie FIPA zastosowano język UML do wykonania diagramów modelujących strukturę i zachowania agentów, dokonując pewnych zmian pojęciowych w porównaniu z obiektami: aktywność agentów bazuje na ich wewnętrznych stanach zawierających cele i warunki określające sposób wykonania zdefiniowanych zadań. Obiekty muszą być sterowane zewnętrznie w celu wykonania swoich metod, natomiast agenty działają w grupach, współpracując ze sobą, znają swoje warunki i oczekiwane efekty swoich akcji oraz odpowiedzialność za swoje poczynania.

Wprowadzono nowe diagramy, zwane diagramami protokołów (ang. PD - Protocol Diagrams), oparte na diagramach sekwencji UML. Nowe elementy diagramów PD wyrażono w języku meta-UML, nadając mu nazwę AUML (ang. Agent UML) [OVDPB2001]. Diagram protokołu PD reprezentuje interakcje, które są sterowane zbiorem wiadomości wymienianych między agentami pełniącymi różne role, w celu osiągnięcia zamierzonego efektu. Na rysunku 3. przedstawiono diagram PD przykładowej aplikacji. Prostokąty reprezentują role spełniane przez podany typ agenta i oznaczone są następująco: wystąpienie_agenta_w_roli: typ_agenta. Linia życia (prostokąt na pionowej przerywanej linii) startuje wtedy, gdy jest tworzony agent, występujący w danej roli i kończy się, gdy agent jest usuwany. W zaprojektowanym protokole na rysunku 3. przy przesyłaniu komunikatów wykorzystano równoległość typu AND oraz decyzje (jeden z wielu). Równoległość typu AND wyraża się za pomocą pionowej pogrubionej linii z wyprowadzonymi strzałkami komunikatów, natomiast decyzję wyraża wypełniony romb z wyprowadzonymi strzałkami komunikatów. Linie życia odbiorców tych komunikatów są przedstawiane w postaci wątków umieszczonych jeden za drugim wzdłuż pionowej przerywanej linii. Etykiety na strzałkach reprezentują nazwę wystąpienia wiadomości jednego z typów komunikatów (przedrostek nazwy), podanych w Systemowej Bibliotece Typów Wiadomości (ang. FIPA Communicative Act Library)- inform, failure, propose, request, itd. Są one poprzedzone warunkiem spełnianym przez komunikat (np. [failed]) i zakończone listą parametrów umieszczonych w nawiasie okrągłym np. (task). Opis pełnej postaci diagramów PD jest w dokumentacji [FIPA].

W protokole przedstawionym na rysunku 3. zakłada się, że w systemie wieloagentowym agent typu manager (typ Grubego Agenta) otrzymuje kolejne zadanie i informuje zbiór agentów (przynajmniej dwóch agentów) typu bidder (typ Grubego Agenta) o potrzebie jego wykonania. Agenty typu bidder przekazują żądanie wykonania poszukiwania informacji agentom typu searcher (typ Cienkiego Agenta). Po podjęciu działań agenty typu searcher podają wyszukaną informację lub informują o negatywnym wyniku poszukiwań.. W przypadku braku odpowiedzi od wszystkich agentów typu searcher, po upływie czasu przeterminowania tb agenty typu bidder kończą z nimi współpracę. Agenty typu bidder dokonują wyboru najlepszej z dostarczonej informacji ze względu na przyjęte kryteria lub stwierdzają negatywny wynik poszukiwań w przypadku złej informacji lub braku informacji Wynik tych działań wysłany jest w postaci komunikatu do agenta typu manager. W przypadku braku odpowiedzi od wszystkich agentów typu bidder, po upływie czasu przeterminowania tm agent typu manager kończy z nimi współpracę. Dokonuje on wyboru jednego zwycięzcy wśród agentów typu bidder lub stwierdza negatywny wynik poszukiwań w przypadku złej informacji lub braku informacji. O wyniku swoich działań powiadamia on agentów typu bidder. Prawdopodobieństwo uzyskania poprawnej odpowiedzi jest równe ilorazowi liczby poszukiwań zakończonych sukcesem wg agenta typu manager do liczby żądań szukania zgłoszonych do agenta typu manager.

Na rysunkach 4., 5. i 6. przedstawiono diagramy stanów agentów, wynikające ze zdefiniowanego protokołu komunikacji, określonego jako bidder-net.

W pierwszej kolejności przestawiona będzie definicja map stanów (bez czynnika czasu), a następnie definicja wydajnościowych map stanów, która zawiera definicję map stanów.

Mapa stanów [BHM2001] jest grafem zdefiniowanym szóstką uporządkowaną:

S = <BoxN, childB, typeB, defaultB, ArcN, Arc>, gdzie:

BoxN jest skończonym zbiorem nazw stanów, które są wierzchołkami grafu obrazowanymi prostokątami z zaokrąglonymi rogami.

childB ⊆ BoxN × BoxN jest relacją hierarchii: <b1, b2>∊childB oznacza, że b2 jest “dzieckiem” “ojca”, którym jest b1. Zbiór BoxN wraz z relacją hierarchii childB definiuje drzewo stanów <BoxN,childB>. Korzeń r drzewa nie ma rodziców, liście nie mają dzieci.

typeB : BoxN → {PRIM, XOR, AND} jest funkcją, która każdemu wierzchołkowi przyporządkowuje jego typ. Korzeń r musi być typu XOR (stan będący automatem sekwencyjnym), liście są typu PRIM, a pozostałe wierzchołki mogą być typu XOR lub AND (stan z podstanami współbieżnymi).

defaultB : BoxN → 2BoxN jest funkcją częściową wierzchołków początkowych. Funkcja ta dla wierzchołka XOR wyznacza zbiór zawierający dokładnie jeden wierzchołek (stan początkowy automatu), a dla wierzchołka AND - zbiór zawierający wszystkie jego dzieci.

ArcN jest skończonym zbiorem nazw łuków. BoxN ∩ ArcN =∅.

Arc ⊆ BoxN × ArcN × BoxN jest zbiorem łuków. Łuk α∊Arc jest trójką uporządkowaną <b1,a,b2> z wierzchołkiem początkowym source(α) = b1, wierzchołkiem końcowym target(α)=b2 i nazwą name(α) = a. Zakładamy, że <b1,a,b2> jest jednoznacznie identyfikowany przez jego nazwę a. Łuki obrazują przejścia między stanami.

Strukturalną konfiguracją mapy stanów S jest zbiór wierzchołków B⊆BoxN takich, że r∊B i dla każdego wierzchołka b∊B, jeśli typeB(b)=AND to wszystkie jego dzieci są elementami B, a jeśli typeB(b)=XOR to dokładnie jedno jego dziecko jest elementem B.

Wydajnościowa mapa stanów [BHM2001], [BHM2003] jest uporządkowaną trójką

WMS=<S, A, L>, gdzie:

S jest mapą stanów,

A jest zbiorem atrybutów. Atrybut ma nazwę i wartość. Wartość może być typu logicznego, całkowitego, rzeczywistego lub typu czasu. Atrybuty wyrażają parametry formalne występujące w elementach funkcji etykietującej L

L jest funkcją etykietującą łuki. Każdemu łukowi α∊Arc takiemu, że α=<b1,a,b2> przypisana jest etykieta l. Etykieta l jest piątką uporządkowaną:

l = < un, pr, te,[gc], al, de >

ze znaczeniem składowych podanym dalej.

un jest funkcją rozkładu prawdopodobieństwa czasu odblokowania łuku. Czas ten liczony jest od chwili wejścia do stanu reprezentowanego wierzchołkiem początkowym rozpatrywanego łuku. Jest to minimalny czas, po jakim może nastąpić przejście do stanu reprezentowanego wierzchołkiem, do którego łuk jest skierowany. Zbiór zdarzeń odblokowania łuków będzie oznaczany symbolem UnbEVENT = {unb(a) : a ∊ArcN}, gdzie unb(a) jest zdarzeniem odblokowania łuku o nazwie a.

pr∊Nat={1,2,...} jest priorytetem łuku; większa liczba oznacza wyższy priorytet.

te=name(formal_parameters_list) jest zdarzeniem przełączającym łuk, gdzie: name∊ ExtEVENT ∪ IntEVENT

ExtEVENT jest skończonym zbiorem nazw zdarzeń zewnętrznych, a IntEVENT jest skończonym zbiorem nazw zdarzeń wewnętrznych. Brak zdarzenia oznaczamy kreską ‘-‘.

gc jest dozorem. Dozór jest wyrażeniem logicznym, którego wartość jest wyznaczana w chwili odbioru zdarzenia te, a w przypadku braku zdarzenia przełączającego w etykiecie łuku - w dowolnej chwili po odblokowaniu łuku.

Aby mogło nastąpić przejście ze stanu początkowego łuku do stanu końcowego łuku, muszą być spełnione warunki:

• w przypadku istnienia zdarzenia przełączającego w etykiecie łuku: upłynął czas odblokowania łuku, te występuje co najmniej po czasie odblokowania łuku, w chwili wystąpienia zdarzenia te, dozór gc jest spełniony

• w przypadku braku zdarzenia przełączającego w etykiecie łuku: upłynął czas odblokowania łuku, dozór jest spełniony po odblokowaniu łuku.

Przejście następuje w najwcześniejszej chwili spełnienia tych warunków.

al=<a1,...,an> jest listą akcji. Akcje są wykonywane w porządku ich wystąpienia. Akcje są atomowe i wykonywane w chwili przejścia między stanami. Akcje mogą zmieniać wartości atrybutów lub generować zdarzenia, które są dostępne natychmiast. Wymagamy aby zbiory atrybutów modyfikowanych przez łuki należące do stanów współbieżnych WMS były rozłączne. Generowane zdarzenia są postaci

ge=name(actual_parameters_list), gdzie name∊IntEVENT.

de jest listą odłożonych zdarzeń wewnętrznych <<ge1,pdf1>,...,<gei,pdfi>,...,<gen,pdfn>>, gdzie gei=name(actual_parameters_list) przy warunku name∊IntEVENT, pdfi jest funkcją rozkładu prawdopodobieństwa. Zdarzenie gei wystąpi po czasie opisanym zmienną losową o rozkładzie pdfi. Czas opóźnienia liczony jest względem chwili przejścia między stanami.

Opóźnienie odblokowania łuku α=<b1,a,b2> jest wprowadzone w celu zamodelowania czasu trwania aktywności wykonywanej w stanie b1. Dopiero po tym czasie może nastąpić przejście ze stanu b1 łukiem α do stanu b2. Natychmiastowe i opóźnione zdarzenia wewnętrzne są wprowadzone, aby zamodelować zdarzenia zakończenia akcji, które są inicjowane w chwili przechodzenia łukiem α.

Przykład 1: Na diagramie stanów (rysunek 6) w stanie search jets wykonywana operacja find(), za pomocą której Searcher wyszukuje informację. Przy badaniach wydajnościowych modelujemy tylko czas wykonania tej operacji, opisując następującą etykietą, przedstawioną dalej na wydajnościowej mapie stanów Searcher’a (rysunek 10): s3: <range(0,2),1,-,[resp],< >, < < i_r(akt_task_s1,1),erl(2,1) >>>. Zmienna losowa czasu wykonania operacji find() jest wyrażona funkcją rozkładu prawdopodobieństwa czasu odblokowania łuku jako rozkład jednostajny na przedziale [0, 2). Priorytet (pr) tego łuku wynosi 1. Brak zdarzeń przełączających (te=-) oznacza, że przejście wzdłuż tego łuku zajdzie natychmiast po jego odblokowaniu i spełnieniu dozoru. Dozór (gc) jest atrybutem logicznym resp. Jak przedstawiono w punkcie 4, atrybut ten reprezentuje wynik działania operacji find(), wartość „prawda” oznacza wynik pozytywny, „fałsz” – negatywny. Lista akcji (al) jest pusta, ponieważ podczas wykonywania przejścia nie są wykonywane akcje natychmiastowe. Lista odłożonych zdarzeń wewnętrznych (de) zawiera jedną parę: < i_r(akt_task_s1,1),erl(2,1) >, gdzie i_r wyraża wysłanie komunikatu inform-result przez Searcher’a do Bidder’a (rysunek 6). Atrybut akt_task_s1 reprezentuje numer wykonywanego zadania, natomiast drugi atrybut wyraża adres Bidder’a, do którego kierowany jest komunikat. Czas transmisji tego komunikatu jest zamodelowany zmienną losową o rozkładzie Erlanga drugiego stopnia z parametrem λ=1 dla każdego ze stopni.

Pojęcie konfiguracji strukturalnej dla WMS jest identyczne z tym samym pojęciem wprowadzonym uprzednio dla map stanów. Obecnie przedstawimy zachowanie WMS.

Konfiguracja WMS jest parą Conf = <ComConf, EvConf>, gdzie ComConf jest konfiguracją obliczeń, natomiast EvConf jest konfiguracją zdarzeń.

Konfiguracja obliczeń jest parą ComConf = <SConf, AConf>, gdzie SConf jest konfiguracją strukturalną (zdefiniowaną tak jak dla mapy stanów), natomiast AConf jest wartościowaniem atrybutów.

Konfiguracja zdarzeń WMS jest zdefiniowana jako czwórka: EvConf =<BA,UA,IE,DE> ze znaczeniem składowych podanym dalej.

BA jest listą zablokowanych łuków. Lista zawiera pary: <a1,t1>,...,<ai,ti>,...,<an,tn>, gdzie a1,...,ai,...,an ∊ ArcN są nazwami łuków istotnych dla strukturalnej konfiguracji SConf, natomiast t1,...,ti,...,tn są chwilami odblokowania łuków.Zbiór łuków istotnych dla strukturalnej konfiguracji Wartość chwili ti określona jest zależnością ti = t_entry+re(un), gdzie t_entry jest chwilą wejścia do stanu początkowego łuku o nazwie ai, natomiast re(un) jest realizacją zmiennej losowej czasu odblokowania tego łuku o rozkładzie un.

UA ⊆ ArcN jest zbiorem nazw odblokowanych łuków, przy czym UA⊆relevant(P), gdzie relevant(P) jest zbiorem łuków istotnych dla konfiguracji P,

IE ⊆ IntEVENT jest zbiorem natychmiastowych zdarzeń wewnętrznych,

DE jest listą zdarzeń opóźnionych postaci <ge1,t1>,...,<gei,ti>,...,<gen,tn>, gdzie gei jest generowanym zdarzeniem, natomiast t1,...,ti,...,tn są chwilami wygenerowania tych zdarzeń w przyszłości. Wartość początkowa chwili ti określona jest zależnością ti = t_pass +re(pdfi) , gdzie t_pass jest chwilą przejścia po łuku, którego lista odłożonych zdarzeń wewnętrznych zawiera element <gei, pdfi>. re(pdfi) jest realizacją zmiennej losowej czasu odblokowania tego łuku o rozkładzie pdfi

WMS zmienia konfiguracje w czasie. Przejścia między konfiguracjami są inicjowane poprzez wystąpienie zdarzenia e∊EVENT. Zdarzenia mogą być: zewnętrznymi e∊ExtEVENT, wewnętrznymi e∊IntEVENT lub odblokowaniem łuku e∊UnbEVENT. Przejścia czasowe związane są z upływem czasu, natomiast przejścia natychmiastowe występują w zerowym czasie. Jeśli WMS jest w konfiguracji <ComConf,EvConf> w chwili t, natomiast zdarzenie e∊EVENT występuje w chwili t' to następuje przejście do nowej konfiguracji <ComConf',EvConf'> w chwili t' co oznaczamy następująco:

<ComConf,EvConf> -e→ <ComConf',EvConf'>.

Przykład 2: Przyjmijmy, że w chwili t=1000, w komponencie modelującym pewnego searcher’a następuje wejście do stanu report (rysunek 10). Do listy zablokowanych łuków (BA) dopisywane są dwie pary, jeśli przyjmiemy, że została wygenerowana wartość re(range(0,2))=1.5, pary te są następujące: <s3, 1001.5> oraz <s4, 1002>. W chwili t=1001.5 para związana z łukiem s3 usuwana jest z listy BA, a łuk s3 dodawany jest do zbioru nazw łuków odblokowanych (UA). Następnie sprawdzane jest wartościowanie atrybutu resp występującego w wyrażeniu dozoru łuku s3. Jeśli dozór jest spełniony, następuje przejście łukiem s3. Nie zmienia to zbioru natychmiastowych zdarzeń wewnętrznych (IE), natomiast do listy zdarzeń opóźnionych (DE) dopisywana jest para związana ze zdarzeniem i_r. Jeśli została wygenerowana wartość re(erl(2,1)=0.3, a wartość akt_task_s1=300, to para ta ma następującą postać: <i_r(300, 1), 1001.8>. W chwili t=1001.8 para ta usuwana jest z listy DE, a do zbioru IE dodane jest zdarzenie i_r(300,1).

Przedstawiony teraz będzie wydajnościowy model systemu wieloagentowego. Został on zapisany przy użyciu wydajnościowych map stanów opisanych w podrozdziale 3. W modelu wydajnościowym pominięto pewne elementy protokołu, opisanego szczegółowo w podrozdziale 2., nie mające wpływu na parametry wydajnościowe badanego modelu. Przykładowo, nie uwzględniono końcowego powiadamiania agentów o przyjęciu ich propozycji lub jej odrzuceniu. W modelu przedstawionym w podrozdziale 2. przyjęto niejawnie założenie, że wszelkie informacje i komunikaty przesyłane są za pośrednictwem protokołu transmisyjnego gwarantującego dostarczanie danych do odbiorcy w tej samej kolejności, w jakiej zostały wysłane. Przykładowym protokołem spełniającym te założenia jest powszechnie stosowany protokół TCP/IP. W naszych eksperymentach nie modelowaliśmy warstwy sieciowej. W pewnych przypadkach okazało się jednak konieczne modelowanie elementów tej warstwy mających wpływ na działanie modelu oraz jego parametry czasowe. Czas transmisji wszelkich komunikatów modelowany jest jako losowy o rozkładzie Erlanga drugiego stopnia z parametrem λ=1 dla każdego ze stopni. W etykietach łuków rozkład ten oznaczany jest erl(2,1). W jednym przypadku, okazało się konieczne zamodelowanie bufora odbiorczego należącego do warstwy sieciowej.

Badane są dwa systemy wieloagentowe. W pierwszym z nich na poziomie wykonawczym są trzy agenty, w drugim - pięć. Rysunek 7. przedstawia pierwszy system. System ten zawiera stan typu AND z podstanami obrazującymi agentów typów manager, bidder oraz searcher, a także bufory odbiorcze Bidder'ów. Na kolejnych rysunkach zawarte są diagramy poszczególnych typów agentów. Większość zdarzeń umieszczonych na tych diagramach ma parametry. Pierwszy z nich ”t_n” jest numerem zadania, do którego jest przypisane zdarzenie. Ewentualny drugi parametr określa adres odbiorcy – Bidder’a – ”b_n” lub Searcher’a – ”s_n”. W celu zachowania unikalności nazw zdarzeń stosowane są przyrostki ”_m” dla Mngr’a, ”_b1”, ”_b2”, dla Bidder’ów, ”_bb1”, ”_bb2” dla buforów Bidder’ów oraz ”_s1” ,”_s2”, ”_s3” dla Searcher’ów.

Rysunek 8. pokazuje model agenta Mngr. Jak wspomniano, nie zawiera on elementów nie mających wpływu na badane parametry wydajnościowe takich jak tworzenie i usuwanie list oraz informowanie agentów typu bidder o wynikach. Zawiera natomiast parametry czasowe modelu i sieci transmisyjnej, a także akcje służące pomiarom w opisanym niżej eksperymencie. W celu skrócenia tekstów etykiet zmieniono nazwy komunikatów stosując pierwsze litery wyrazów np. zamiast „inform-of-announce” mamy ”i_o_a”. Wprowadzono zdarzenie ”t_o_m” oznaczające upłynięcie czasu przeterminowania oczekiwania Mngr’a na odpowiedzi Bidder’ów. Symbol tm oznacza maksymalny czas czekania przez agenta typu manager na odpowiedzi od agentów typu bidder (podrozdział 2.3).

Rysunek 9. obrazuje agenta Bidder_1wraz z fragmentem jego bufora odbiorczego. Bufor ten wprowadzony został, aby zagwarantować, że komunikat "c_f_p_i" pojawi się u Bidder’a po komunikacie "i_o_a". Ponieważ zdarzenia w mapach stanów muszą mieć unikalne nazwy, komunikat wysłany przez Mngr’a nosi nazwę "c_f_p_i", natomiast po przejściu przez bufor u Bidder’a pojawia się jako "c_f_p_i_r". Konieczność modelowania bufora istnieje tylko dla tej pary komunikatów, bowiem tylko one wysyłane są jeden po drugim, bez potwierdzenia w warstwie aplikacji. Tak jak dla Mngr’a, pominięte są nieistotne dla badania wydajności elementy. Tworzenie list odpowiedzi zastąpiono ich zliczaniem, gdyż tylko ilość odpowiedzi była istotna w badaniach wydajnościowych. Wprowadzono zdarzenie ”t_o_b1” oznaczające upłynięcie czasu tb przeterminowania oczekiwania agenta Bidder_1 na odpowiedzi Searcher’ów (podrozdział 2.3).

Rysunek 10. przedstawia agenta Searcher_1. Łuk "s2" wraz ze stanem "report" modeluje aktywność wewnętrzną "find()" z rysunku 6., która w wydajnościowych mapach stanów nie jest dopuszczalna. Przyjęto następujący model wydajnościowy tego typu agenta.

Agent przeszukuje pewną bazę danych znajdując w niej potrzebne informacje z prawdopodobieństwem _f_rate. Modelowane jest to poprzez generowanie na łuku s2 zmiennej losowej resp przyjmującej wartość 1 z takim prawdopodobieństwem. Zmienna ta występuje w wyrażeniach dozorów łuków s3 i s4 sprawiając, że zachodzi przejście tylko wzdłuż jednego z nich. Łuki te symulują czas poszukiwań, który w przypadku powodzenia opisany jest zmienną losową o rozkładzie jednostajnym (range) na odcinku [0,2), natomiast w przypadku porażki – stałym opóźnieniem o wartości 2.

Rysunki 11a i 11b dotyczą systemu z jednym agentem typu manager, dwoma agentami typu bidder i trzema agentami typu searcher (rysunek 3). Wykres z rysunku 11a został uzyskany dla czasu tm przeterminowania agenta typu manager równego nieskończoności.

Z wykresu tego wynika, że zwiększenie czasu tb przeterminowania agentów typu bidder powyżej 8 jednostek czasu w niewielkim stopniu zwiększa prawdopodobieństwo uzyskania dobrej odpowiedzi. Wykres z rysunku 11b otrzymano dla czasu tb równego 8 jednostkom. Z tego wykresu wynika, że zwiększanie czasu tm powyżej 15 jednostek w niewielkim stopniu zwiększa prawdopodobieństwo uzyskania dobrej odpowiedzi.

Dalsze badania dotyczą dwu systemów. Pierwszym z nich jest badany poprzednio system z trzema agentami typu searcher na poziomie wykonawczym. W drugim z analizowanych systemów, jeden agent typu bidder pracuje z dwoma agentami typu searcher, natomiast drugi agent typu bidder – z trzema agentami typu searcher. Stąd na poziomie wykonawczym jest pięć agentów.

Z rysunku 12. można wywnioskować, że dla systemu z większą liczbą agentów poziomu wykonawczego, prawdopodobieństwo uzyskania dobrej odpowiedzi jest większe, jednak kosztem większego średniego czasu odpowiedzi. Większy średni czas odpowiedzi systemu z większą liczbą agentów spowodowany jest potrzebą czekania na odpowiedzi od większej liczby agentów poziomu wykonawczego. Z zależności przedstawionych na rysunku 13., dla różnych liczb agentów poziomu wykonawczego, można przy zadanym prawdopodobieństwie otrzymania odpowiedzi wyznaczyć średnie czasy otrzymania odpowiedzi. Ponadto dla zadanego średniego czasu odpowiedzi można określić prawdopodobieństwa otrzymania odpowiedzi dla różnych liczb agentów wykonawczych.

Przebadano system wieloagentowy o trzech poziomach hierarchii. System ten służy wyszukiwaniu informacji. Dwa wyższe poziomy hierarchii są poziomami zarządzającymi, natomiast poziom najniższy jest wykonawczym. Pomiędzy kolejnymi poziomami hierarchii zastosowano mechanizm przeterminowania w oczekiwaniu na odpowiedź z niższego poziomu. Dynamikę systemu zamodelowano za pomocą map stanów. Do badania charakterystyk wydajnościowych zastosowano wydajnościowe mapy stanów. Przebadano zależności prawdopodobieństwa uzyskania satysfakcjonującej menedżera odpowiedzi oraz średniego czasu otrzymywania odpowiedzi przez menedżera od wartości czasów przeterminowania, ilości agentów poziomu wykonawczego- przy ustalonych rozkładach prawdopodobieństwa czasów transmisji między agentami oraz ustalonych rozkładach prawdopodobieństwa czasu szukania w bazach danych i prawdopodobieństwach znalezienia szukanej informacji w bazach.

Na podstawie eksperymentów dobrano czasy przeterminowania w czekaniu na odpowiedź z niższego poziomu hierarchii. Porównano dwa systemy z różną liczbą agentów poziomu wykonawczego. Porównanie dotyczyło prawdopodobieństwa uzyskania odpowiedzi i średniego czasu odpowiedzi w funkcji czasów przeterminowania. System o większej liczbie agentów wykonawczych ma lepsze własności. Z otrzymanych zależności, dla różnych liczb agentów poziomu wykonawczego, można przy zadanym prawdopodobieństwie otrzymania odpowiedzi wyznaczyć średnie czasy otrzymania odpowiedzi. Ponadto dla zadanego średniego czasu odpowiedzi można określić prawdopodobieństwa otrzymania odpowiedzi dla różnych liczb agentów wykonawczych.