網(wǎng)格及傳感器網(wǎng)絡(luò)中機(jī)制設(shè)計(jì)問題的研究.pdf

1、分布式系統(tǒng)可以被視為一個(gè)連接許多代理的網(wǎng)絡(luò)。在傳統(tǒng)的分布式系統(tǒng)中，代理們被假定為是服從性的，即他們遵循一定的算法。當(dāng)許多計(jì)算機(jī)聯(lián)結(jié)成為一個(gè)分布式系統(tǒng)時(shí)，系統(tǒng)的各個(gè)組成部分會(huì)有不同的利益關(guān)系。這樣的分布式系統(tǒng)就可能是策略性的，即系統(tǒng)的不同部分有自己不同的動(dòng)因。在一個(gè)策略性分布式系統(tǒng)中，策略性代理根據(jù)各自的利益做出反應(yīng)。當(dāng)每個(gè)理性而自私的代理只關(guān)心自己的私利時(shí)，動(dòng)因問題就成為一個(gè)亟待解決的重要問題。 在本文中，我們將研究網(wǎng)格和傳感器

2、網(wǎng)絡(luò)中的動(dòng)因問題，并設(shè)計(jì)相應(yīng)的機(jī)制保證系統(tǒng)在每個(gè)節(jié)點(diǎn)Selfish的情況下仍能正常運(yùn)行。 我們首先研究了網(wǎng)格系統(tǒng)中資源的動(dòng)態(tài)分配問題?，F(xiàn)存的資源分配算法大都采用靜態(tài)分配機(jī)制，如MinWork機(jī)制等。但靜態(tài)資源分配的效率不高、擴(kuò)展性差且與實(shí)際情況相差較大。針對(duì)靜態(tài)資源分配的這些缺點(diǎn)，我們?cè)O(shè)計(jì)了一個(gè)動(dòng)態(tài)資源分配機(jī)制。該機(jī)制假設(shè)所有的任務(wù)都遵循一定的概率模型隨機(jī)產(chǎn)生，任務(wù)的規(guī)模和發(fā)生時(shí)間均為隨機(jī)分布，目標(biāo)是每個(gè)任務(wù)都能夠在最短時(shí)間內(nèi)完

3、成。我們以二次價(jià)格密封拍賣理論為基礎(chǔ)，提出了動(dòng)態(tài)任務(wù)分配機(jī)制，并證明了我們的機(jī)制能夠提供較高的資源利用率、良好的擴(kuò)展性而且是Strategyproof的。 通過深入研究微軟的Sensor Web項(xiàng)目，我們還提出了針對(duì)無線傳感網(wǎng)絡(luò)的機(jī)制設(shè)計(jì)問題。該項(xiàng)目希望利用Internet連接全國甚至整個(gè)世界的傳感器網(wǎng)絡(luò)，做到信息共享。而且他們還利用了Web 2.0技術(shù)，開放了平臺(tái)的接口，使人們能夠自由上傳自己的傳感器資源。但我們也觀察到了一些

4、問題，其中最大的問題就是在相當(dāng)長的一段時(shí)間里，該平臺(tái)上的傳感器資源并沒有明顯的增長，也就是說很少有人愿意把自己的傳感器資源無償上傳。我們認(rèn)為這正是缺少激勵(lì)機(jī)制造成的后果，因此我們?cè)O(shè)計(jì)了一套激勵(lì)機(jī)制，使人們有動(dòng)因上傳自己的傳感器資源。我們首先把該系統(tǒng)抽象成兩個(gè)博弈方，一方為資源提供者，一方為資源使用者。針對(duì)資源提供者，我們抽象出其成本模型。針對(duì)資源使用者，我們抽象出其價(jià)值模型。然后我們考慮了三種不同的應(yīng)用場(chǎng)景，一是單資源提供者，多資源使用