嵌入式網(wǎng)絡(luò)計(jì)算中協(xié)作求解問題的研究.pdf

1、嵌入式網(wǎng)絡(luò)計(jì)算中，多服務(wù)代理技術(shù)的優(yōu)勢(shì)就是通過服務(wù)代理之間的協(xié)作，完成單個(gè)服務(wù)代理不能完成的任務(wù)或以更高的效率完成任務(wù)。一方面，嵌入式網(wǎng)絡(luò)設(shè)備由于計(jì)算資源嚴(yán)格受限，隨著對(duì)其功能需求日益增強(qiáng)，在執(zhí)行較復(fù)雜任務(wù)時(shí)任務(wù)的復(fù)雜性和時(shí)間緊迫性常常使其無法在規(guī)定的時(shí)間約束內(nèi)完成。設(shè)備硬件資源的升級(jí)對(duì)大量的早已存在的嵌入式網(wǎng)絡(luò)設(shè)備來說不是一個(gè)現(xiàn)實(shí)的方案。操作系統(tǒng)的性能優(yōu)化也不是一個(gè)根本的解決方法。目前，一個(gè)現(xiàn)實(shí)的解決方法是設(shè)備間通過服務(wù)代理進(jìn)行協(xié)作，

2、充分利用其它設(shè)備暫時(shí)不被使用的計(jì)算資源。另一方面，嵌入式網(wǎng)絡(luò)計(jì)算時(shí)代眾多的嵌入式網(wǎng)絡(luò)設(shè)備需要人們?nèi)ジ深A(yù)和協(xié)調(diào)，為了使人們注意力的中心回歸到要完成的任務(wù)本身，使嵌入式網(wǎng)絡(luò)設(shè)備間自主交互，完成所需要的服務(wù)，就要求解決服務(wù)訪問過程的透明性問題，透明性除了包括人機(jī)交互的透明性以外還包括實(shí)現(xiàn)復(fù)雜任務(wù)求解過程的透明性，復(fù)雜任務(wù)可以通過設(shè)備間自動(dòng)協(xié)作來進(jìn)行高效求解。 在多服務(wù)代理之間進(jìn)行協(xié)作求解，國(guó)內(nèi)外先后提出了一些方法，目前主要有合同網(wǎng)模型

3、、黑板模型、多服務(wù)代理規(guī)劃等。其中應(yīng)用最廣泛的是合同網(wǎng)模型。據(jù)文獻(xiàn)查閱，從2000年進(jìn)入EI檢索的100多篇相關(guān)論文中就這個(gè)問題的研究成果發(fā)表的論文達(dá)10余篇，通過分析發(fā)現(xiàn)，合同網(wǎng)模型在嵌入式網(wǎng)絡(luò)設(shè)備的協(xié)作求解中仍然存在以下不適應(yīng)性： (1)合同網(wǎng)招標(biāo)時(shí)要向所有可能的任務(wù)承攬者發(fā)送標(biāo)書，并等待所有的投標(biāo)回答或截止時(shí)間到時(shí)，這在承攬者較多時(shí)會(huì)帶來較大的通信量和時(shí)間開銷；投標(biāo)過程只能在局域網(wǎng)內(nèi)進(jìn)行；并且招標(biāo)通知由系統(tǒng)內(nèi)的所有節(jié)點(diǎn)進(jìn)行

4、接收和處理，浪費(fèi)了不想?yún)⑴c協(xié)作的節(jié)點(diǎn)的計(jì)算資源； (2)承攬方的能力和承擔(dān)的協(xié)作任務(wù)負(fù)載處在不斷的變化之中，合同網(wǎng)的招標(biāo)方則難于了解和適應(yīng)這種變化，導(dǎo)致協(xié)作任務(wù)的過于集中。 為此，本文提出了等級(jí)域的概念，建立了相應(yīng)的等級(jí)域模型，并將其引入到了合同網(wǎng)當(dāng)中。等級(jí)域是把域內(nèi)各個(gè)服務(wù)代理根據(jù)它們的能力和任務(wù)協(xié)作求解的成功率分成三個(gè)不同的等級(jí)：第一等級(jí)：有服務(wù)能力且成功率較高的服務(wù)代理集合；第二等級(jí)：有服務(wù)能力但成功率較低的服務(wù)代

5、理集合；第三等級(jí)：暫時(shí)無服務(wù)能力的服務(wù)代理集合。協(xié)作發(fā)生在第一等級(jí)的服務(wù)代理集合內(nèi)，這樣就縮小了協(xié)作服務(wù)代理的查找范圍，招標(biāo)服務(wù)代理選擇協(xié)作服務(wù)代理的效率高。通過設(shè)置各個(gè)等級(jí)內(nèi)服務(wù)代理個(gè)數(shù)的閾值，避免了服務(wù)代理個(gè)數(shù)的增長(zhǎng)失控以及由此造成的各種開銷。 等級(jí)域內(nèi)各個(gè)服務(wù)代理所在的等級(jí)并不是一成不變的，而是隨著時(shí)間可以動(dòng)態(tài)地進(jìn)行調(diào)整。各個(gè)服務(wù)代理之間相互競(jìng)爭(zhēng)，以便及時(shí)適應(yīng)設(shè)備能力的變化。服務(wù)代理競(jìng)爭(zhēng)的目標(biāo)是進(jìn)入高等級(jí)的服務(wù)代理集合，競(jìng)

6、爭(zhēng)的條件是自身的能力以及任務(wù)協(xié)作求解的成功率和等級(jí)閾值的變化。這樣就能保證及時(shí)了解各個(gè)服務(wù)代理的能力和成功率的變化，克服合同網(wǎng)中服務(wù)代理能力恒定不變的不合適假設(shè)。對(duì)各個(gè)服務(wù)代理能力和成功率變化了解的及時(shí)程度取決于引起競(jìng)爭(zhēng)的頻率。本文采用現(xiàn)有的隨機(jī)TOP-N算法對(duì)等級(jí)域中不同等級(jí)的各個(gè)服務(wù)代理的等級(jí)躍遷進(jìn)行了算法描述和分析。 同時(shí)，為了平衡各個(gè)設(shè)備服務(wù)代理間的任務(wù)負(fù)載，緩和“忙者越忙，閑者越閑”的“馬太效應(yīng)”，避免協(xié)作時(shí)選取協(xié)作服

7、務(wù)代理的盲目性，盡量滿足緊急任務(wù)的時(shí)間約束，提高多服務(wù)代理系統(tǒng)的吞吐量，本文還考慮了各個(gè)服務(wù)代理協(xié)作時(shí)的時(shí)間開銷問題，通過協(xié)作，采納其它服務(wù)代理的意圖，建立了時(shí)間開銷模型，并據(jù)此對(duì)基于等級(jí)域的合同網(wǎng)模型進(jìn)行了相應(yīng)修改，建立了基于等級(jí)域一時(shí)間開銷的合同網(wǎng)模型，把時(shí)間開銷的計(jì)算融進(jìn)了隨機(jī)TOP-N算法當(dāng)中，避免過載和輕載現(xiàn)象的發(fā)生。 通過仿真程序和應(yīng)用結(jié)果的分析，驗(yàn)證了提出的模型及其實(shí)現(xiàn)算法的有效性，在時(shí)間復(fù)雜性和空間復(fù)雜性增加不大