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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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