基于服務推薦的移動agent路徑動態(tài)構(gòu)建方法研究.pdf

1、移動agent是一類可以在網(wǎng)絡站點之間連續(xù)遷移，并就地利用站點服務執(zhí)行任務的程序。與基于RPC的分布式計算相比，移動agent計算具有降低網(wǎng)絡負載、適應環(huán)境變化和支持網(wǎng)絡斷連計算等優(yōu)勢，因此，移動agent計算不僅是學術(shù)界的研究熱點，而且成為業(yè)界應用的一個重要發(fā)展趨勢，例如網(wǎng)絡信息檢索、工作流管理、協(xié)同產(chǎn)品商務、智能機器人、無線傳感器網(wǎng)絡、網(wǎng)絡安全監(jiān)測等領(lǐng)域。
　　在遷移工作流研究中，移動agent是業(yè)務過程管理者的任務代理，移動

2、agent執(zhí)行任務的網(wǎng)絡站點稱作工作位置，它由工作流參與者提供并且設(shè)計為參與者的服務代理。移動agent為實現(xiàn)業(yè)務目標所歷經(jīng)的工作位置序列稱作它的工作路徑。為了能夠高效地利用站點服務資源，獲得最大工作流收益并提高工作流執(zhí)行效率，移動agent工作路徑規(guī)劃是遷移工作流研究的關(guān)鍵問題之一。
　　移動agent工作路徑規(guī)劃方法可以區(qū)分為靜態(tài)規(guī)劃(static planning)和動態(tài)規(guī)劃(dynamic planning)兩種類型。前者

3、是指設(shè)計者依據(jù)已知的網(wǎng)絡站點服務信息，在派遣移動agent之前為其生成工作路徑并令其攜帶的方法。因此，靜態(tài)規(guī)劃生成的移動agent工作路徑缺乏對環(huán)境動態(tài)變化的適應性。后者假定移動agent每次位置轉(zhuǎn)移，都要基于對當前環(huán)境的認知，動態(tài)地選擇工作位置。環(huán)境信息既可以由移動agent自己探測，稱作服務發(fā)現(xiàn)，也可以由協(xié)作站點代為探測，稱作服務推薦。因為服務發(fā)現(xiàn)要求移動agent攜帶足夠的服務發(fā)現(xiàn)知識和環(huán)境探測代碼，所以，不僅遷移效率低，而且容易

4、產(chǎn)生遷移故障。服務推薦可以使移動agent輕量化，提高遷移效率，減少遷移故障，但需要建立互信關(guān)系并簽訂服務推薦契約。根據(jù)社會學的研究結(jié)果，社會熟人關(guān)系是一種通過長期合作形成的互信關(guān)系，因此，對于移動agent工作路徑規(guī)劃來說，基于熟人網(wǎng)絡的服務推薦是一種合理的技術(shù)選擇。
　　本論文在國家自然科學基金項目和山東省自然科學基金項目的資助下，以曾廣周教授提出的遷移工作流概念模型為技術(shù)框架，在課題組前期工作的基礎(chǔ)上，研究一類基于服務推薦的

5、移動agent工作路徑動態(tài)構(gòu)建模型與方法，主要工作包括:
　　1.決策空間可變的移動agent工作路徑動態(tài)規(guī)劃模型與方法研究
　　現(xiàn)有的基于服務發(fā)現(xiàn)的移動agent工作路徑動態(tài)規(guī)劃方法，要求移動agent自身具備足夠的服務發(fā)現(xiàn)知識和環(huán)境探測能力，因而移動agent笨重，不利于遷移;基于導航的移動agent工作路徑動態(tài)規(guī)劃方法，可以使移動agent輕量化，但要求事先組織和劃分全局位置空間，不能良好支持動態(tài)開放環(huán)境;基于熟人推薦

6、的移動agent工作路徑動態(tài)規(guī)劃方法，沒有數(shù)學模型刻畫，不能揭示移動agent工作路徑動態(tài)規(guī)劃的動態(tài)性。
　　本文把MDP(Markov Decision Process)模型和推薦網(wǎng)絡框架(ReferralNetwork)引入到移動agent工作路徑動態(tài)規(guī)劃的研究中，以順序型業(yè)務過程執(zhí)行為應用背景，建立了一類決策空間可變的移動agent工作路徑動態(tài)規(guī)劃MDP模型，給出了基于推薦網(wǎng)絡框架的移動agent工作路徑動態(tài)規(guī)劃方法，其中，

7、移動agent工作路徑規(guī)劃的動態(tài)性用MDP刻畫，遷移時可變的決策空間由當前位置成員的所有社會熟人關(guān)系構(gòu)成，服務推薦在當前位置成員的直接熟人和間接熟人鏈上進行。移動agent的遷移時刻不同，當前位置成員的社會熟人關(guān)系也不同。社會成員熟人關(guān)系的變化性和開放性為移動agent工作路徑規(guī)劃提供了一個動態(tài)可變的決策空間。本文第2章討論決策空間可變的移動agent工作路徑動態(tài)規(guī)劃模型與方法。
　　2.基于有界熟人推薦樹的移動agent工作路徑

8、動態(tài)構(gòu)建方法研究
　　社會學研究表明，對于任何一個理性社會成員來說，由其全部直接熟人關(guān)系和間接熟人關(guān)系綜合形成的社會熟人網(wǎng)絡規(guī)模是巨大的，也可能是無界的，因此，基于整個社會熟人網(wǎng)絡為移動agent搜素服務的效率不高，在許多情況下也是不可行的。根據(jù)小世界現(xiàn)象研究中的六度分離原理，社會網(wǎng)絡上任意兩個陌生人之間的平均間隔距離不大于6，因此，基于服務推薦的移動agent路徑規(guī)劃可以在一個有限的社會熟人關(guān)系集合上進行。
　　本文把六度

9、分離原理引入到移動agent工作路徑動態(tài)構(gòu)建方法的研究中，以順序型業(yè)務過程執(zhí)行為應用背景，以移動agent工作路徑動態(tài)規(guī)劃MDP模型為基礎(chǔ)，建立了一種基于有界熟人推薦樹的移動agent路徑動態(tài)構(gòu)建方法，其中，推薦網(wǎng)絡用移動agent當前成員的社會熟人關(guān)系刻畫，有界熟人推薦樹通過剪枝生成，并且可以由成員事先建立并根據(jù)協(xié)作進程動態(tài)維護。本文第3章討論基于有界熟人推薦樹的移動agent工作路徑動態(tài)構(gòu)建方法。
　　3.基于窗口策略的移動a

10、gent工作路徑動態(tài)規(guī)劃模型與方法研究
　　類似于棋類博弈，對于連續(xù)多任務移動agent工作路徑動態(tài)規(guī)劃來說，也存在“看一步，走一步”和“看多步，走一步”兩種遷移策略。前者是指移動agent每次遷移，都只為當前待執(zhí)行的任務尋找合適位置，而不考慮其后剩余任務對全局路徑的影響。后者是指移動agent每次遷移，除關(guān)注當前待執(zhí)行任務的收益外，還綜合考慮其后一個或多個連續(xù)任務對全局目標的貢獻。
　　本文把“看多步，走一步”策略引入到移

11、動agent工作路徑動態(tài)構(gòu)建方法的研究中，以順序型業(yè)務過程執(zhí)行為應用背景，在改進移動agent工作路徑動態(tài)規(guī)劃MDP模型的基礎(chǔ)上，建立了一種基于窗口策略的移動agent工作路徑動態(tài)構(gòu)建方法，其中，遷移時一次被考察的多個連續(xù)任務稱作規(guī)劃窗口，與規(guī)劃窗口中任務一一對應的位置序列稱作窗口路徑，窗口路徑中的第一個位置是移動agent的下一個目的位置。本文第4章討論基于窗口策略的移動agent工作路徑動態(tài)構(gòu)建方法。
　　4.面向結(jié)構(gòu)化業(yè)務過

12、程協(xié)作的移動agent工作路徑動態(tài)規(guī)劃模型與方法研究
　　計算機支持的協(xié)同工作(CSCW)研究表明，任務分擔和結(jié)果共享是多agent協(xié)作求解問題的一種基本模式。因此，對于帶“與/或”結(jié)構(gòu)的復雜業(yè)務過程執(zhí)行來說，可以通過業(yè)務過程分解將復雜業(yè)務過程轉(zhuǎn)化為一組順序任務分支的集合，每個移動agent執(zhí)行一個順序任務分支，并用順序、分叉、合并等連接模式刻畫多移動agent之間的協(xié)作視圖。
　　本文把任務分擔、結(jié)果共享原理和部分可觀測的

13、馬爾科夫過程(PartiallyObservable Markov Decision Process，POMDP)模型引入到移動agent路徑動態(tài)構(gòu)建方法的研究中，以帶“與/或”結(jié)構(gòu)的復雜業(yè)務過程執(zhí)行為應用背景，建立了一類面向結(jié)構(gòu)化業(yè)務過程協(xié)作的移動agent路徑動態(tài)規(guī)劃POMDP模型，給出了移動agent路徑動態(tài)構(gòu)建方法，包括結(jié)構(gòu)化業(yè)務過程分解、協(xié)作視圖和協(xié)作規(guī)則定義、順序業(yè)務分支指派和移動agent工作路徑協(xié)作規(guī)劃四個基本步驟。本文

14、第5章討論面向結(jié)構(gòu)化業(yè)務過程協(xié)作的移動agent路徑動態(tài)規(guī)劃模型與方法。
　　本文的創(chuàng)新點主要體現(xiàn)在:
　　1、提出了一種基于可變決策空間的移動agent路徑動態(tài)規(guī)劃MDP模型和基于有界熟人推薦樹的移動agent路徑構(gòu)建方法。
　　在同類基于服務推薦的移動agent工作路徑動態(tài)規(guī)劃研究中，導航方法沒有采用推薦網(wǎng)絡框架，也沒有建立數(shù)學模型;熟人推薦方法采用了推薦網(wǎng)絡框架，但沒有建立數(shù)學模型，而且固定了移動agent工作環(huán)

15、境，因而上述方法不能良好刻畫移動agent工作路徑規(guī)劃的動態(tài)性，缺乏對環(huán)境變化的適應性。
　　本文建立的移動agent工作路徑規(guī)劃MDP模型，以社會成員的熟人關(guān)系集合為決策空間，遷移時刻不同，服務成員就不同，決策空間也會不同，因而能夠良好刻畫移動agent路徑規(guī)劃的動態(tài)性，有界熟人推薦樹方法可以有效減少服務推薦的時間，提高路徑規(guī)劃的效率。
　　2、提出了一種基于窗口策略的移動agent路徑動態(tài)規(guī)劃MDP模型和窗口寬度可變的移

16、動agent路徑構(gòu)建方法。
　　在同類移動agent工作路徑動態(tài)規(guī)劃研究中，不論是服務發(fā)現(xiàn)方法還是服務推薦方法，都采用了看一步，走一步”的遷移策略，即只為當前待執(zhí)行的任務查找合適位置，而不考慮其后剩余任務對全局路徑規(guī)劃的影響。
　　本文建立的基于窗口策略的移動agent路徑動態(tài)規(guī)劃MDP模型和窗口寬度可變的移動agent路徑構(gòu)建方法，不僅考察當前待執(zhí)行任務的收益，而且綜合考察其后一個或多個連續(xù)任務對全局目標的貢獻，因而更有利

17、于全局路徑的優(yōu)化，決策空間可變的MDP模型能夠良好刻畫移動agent路徑規(guī)劃的動態(tài)性。
　　3、提出了一種面向結(jié)構(gòu)化業(yè)務過程協(xié)作的移動agent工作路徑動態(tài)規(guī)劃POMDP模型和面向協(xié)作的移動agent路徑構(gòu)建方法。
　　在多移動agent協(xié)作問題求解研究中，部分-整體規(guī)劃（Partial-Global Planning）是一種最常用的方法，但它缺少數(shù)學模型刻畫。因為所有移動agent都要參與整體規(guī)劃協(xié)商并且要不斷地將部分規(guī)劃

18、中的執(zhí)行變更通告給其它移動agent，所以，移動agent越多，協(xié)商時間就越長，規(guī)劃效率就越低。
　　本文建立的移動agent路徑規(guī)劃POMDP模型和面向協(xié)作的移動agent路徑構(gòu)建方法，以結(jié)構(gòu)化業(yè)務過程分解和業(yè)務分支指派為基礎(chǔ)，以分叉任務和合并任務的執(zhí)行需求為移動agent的協(xié)作知識，因而不必像部分-整體規(guī)劃那樣，步步進行全局協(xié)商，決策空間可變的POMDP模型能夠良好刻畫移動agent路徑協(xié)作規(guī)劃的動態(tài)性。
　　移動age

19、nt計算是一個發(fā)展中的研究領(lǐng)域，移動agent路徑動態(tài)規(guī)劃模型和規(guī)劃方法的研究還不夠成熟，還有很多值得探索和改進的方面，本文進一步的研究工作主要包括:
　　1、帶時間約束的移動agent路徑動態(tài)構(gòu)建方法。本文方法沒有涉及路徑規(guī)劃中的時間因素。在許多情況下，業(yè)務過程執(zhí)行具有時間限制，因此，需要進一步研究帶時間約束的移動agent路徑動態(tài)構(gòu)建方法。
　　2、基于誠信策略的移動agent路徑動態(tài)構(gòu)建方法。本文方法假設(shè)被推薦位置都是