經濟網(wǎng)絡[1-3]將資源提供者和網(wǎng)格用戶的需求使用一定的價值表述，通過成本和收益等經濟約束描述網(wǎng)格環(huán)境[4]下用戶與資源之間的交互行為，有助于建立高可擴展性的網(wǎng)格系統(tǒng)。

　　摘要：針對網(wǎng)格環(huán)境下用戶難以獲得資源競價所需的信息而導致的決策風險，將不完全信息資源競價轉化成完全信息下的重復博弈問題。分析了該博弈均衡解的存在性及求解過程，給出了相應的競價算法，討論了對用戶低價聯(lián)盟的抑制方法。仿真實驗表明用戶通過各階段資源預配置的信息調整競價策略，資源配置可逐步逼近均衡解，實現(xiàn)網(wǎng)格資源的優(yōu)化配置。

　　關鍵詞：不完全信息,重復博弈,網(wǎng)格計算,資源配置

　　0引言

　　早期經濟網(wǎng)格的研究普遍采用商品市場[5-7]機制或拍賣[8]機制，但商品市場機制忽略了單個用戶的個體行為對資源價格的影響作用，與實際情況有較大偏差，而拍賣機制則依賴于第三方（如拍賣師）的公正性。此外，另有一些研究[9-11]將用戶之間對資源的競爭使用看作一個博弈過程，在完全信息前提下通過分析均衡價格策略組合來求解網(wǎng)格資源優(yōu)化配置方法，但基于完全信息的前提要求用戶掌握其他用戶的詳細信息，這在動態(tài)、自治的網(wǎng)格環(huán)境中是難以實現(xiàn)的。

　　本文分析了不完全信息情況下的網(wǎng)格環(huán)境中用戶對資源競價的情況，通過“虛擬用戶”的方式將不完全信息情況下的資源博弈轉化成完全信息下的重復博弈。給出用戶競價算法及近似均衡解，克服用戶對競價信息的依賴，避免了用戶盲目競價決策的風險，實現(xiàn)資源的優(yōu)化配置。

　　1不完全信息資源競價模型

　　設N個用戶競爭使用一個有M+1個中間節(jié)點的通信鏈路，節(jié)點k和k+1之間的通信帶寬為Rk，用戶使用資源并付費，系統(tǒng)按用戶的出價比例分配資源，用戶的目標是在預算范圍內使用資源，且使得數(shù)據(jù)傳輸時間最短。模型各參數(shù)設定如下：

　　{Rk}為各通信鏈路的傳輸帶寬。{qki}表示經過中間節(jié)點k后經通信資源Rk傳輸?shù)膩碜杂脩鬷的數(shù)據(jù)包長度。Ci為用戶的總預算。{Cki}表示用戶i對資源k的出價，且∑Mk=1cki≤Ci。aik為用戶i在資源Rk上的出價比例。Ck為第k個資源上所有用戶的競價和。tkip、tkic分別表示任務qkr在資源k上的傳輸時間和任務qki到達新節(jié)點后的處理時間。為了簡化分析，設數(shù)據(jù)處理時間與數(shù)據(jù)包長度成正比例關系。tki表示任務qki完成時間，tki=tkip+tkic。ck為資源Rk的保留底價，保留底價是資源所有者對資源使用成本的評估。只有當用戶出價和不低于ck時，資源提供者才有意愿向用戶提供資源。

　　2競價問題分析

　　2.1多用戶不完全信息博弈問題的轉換

　　雖然用戶i難以獲得所有其他用戶的相關信息，但每個用戶對自己的出價cki信息是可知的，而相應可獲得的資源數(shù)rki則由系統(tǒng)返回。由于資源總量Rk是已知的，對于按競價比例配置資源的方式，用戶即可通過Rk和rki獲得其他所有用戶的競價ck-i和資源數(shù)rk-i。由此推知，理性用戶在擁有私有信息rki、cki基礎之上，再獲得可用資源總數(shù)Rk一個公共信息就可以測算出所有其他用戶競價的信息。

　　在此，可將除用戶i外所有其他用戶的集合虛擬為用戶-i。其中，用戶i的競價信息為（cki，rki），用戶類型-i的競價信息為（ck-i，rk-i），則多用戶不完全信息的資源博弈可轉變成兩個用戶集合i和-i在完全信息下的資源博弈，并據(jù)此而得到資源配置的均衡解{c*i}。第1期林曉鵬：基于不完全信息博弈的網(wǎng)格資源分配方法研究智能計算機與應用第4卷

　　2.2競價策略的求解

　　3.3用戶低價聯(lián)盟的抑制

　　因重復競價博弈中用戶在博弈的后續(xù)階段可對前期的競價策略進行調整，理性用戶可能會在競價初期隱藏自己的真實目的，在前期階段以低價進行競價而導致延長資源配置過程�；蛘哂脩糁�間也可能達成某種默契形成競價聯(lián)盟，聯(lián)合以低價獲得資源的使用權，導致資源提供者的收益可能低于資源的使用成本。

　　為了防止這種情況發(fā)生，設定每個資源的使用者也都參與到資源競價中，競價過程中資源所有者設定為虛擬用戶ξ，利用預先設定的保留價格ckξ參與資源競價。通過虛擬用戶的競價，使得當資源價格低于保留價格ckξ時降低可供應的資源數(shù)量，促使用戶通過提高競價來獲得更好的資源，以保障資源方的利益。

　　4仿真結果和分析

　　4.1仿真環(huán)境

　　文中運用Gridsim仿真軟件包來構建網(wǎng)格用戶、網(wǎng)格資源、GIS等各個網(wǎng)格實體。各實體之間由消息機制進行競價過程的消息傳遞。仿真中資源數(shù)為M=10，各用戶總預算為100～400GCU（GridCurrencyUnit）之間的隨機數(shù)，各資源能力、用戶數(shù)據(jù)包長度分別在范圍1000～5000（Mbps）和0～5000（Mb）內正態(tài)分布。不考慮消息傳遞代價，競價博弈的初始階段用戶按相同的單位任務費用分配預算。

　　4.2結果分析

　　當所有用戶競價價格∑Ni=1cki5結束語

　　在用戶對資源進行競價過程中，需要掌握其他用戶的資源使用策略，或者依賴于公正的第三方才能做出正確的策略圖3博弈過程用戶的總執(zhí)行時間變化選擇。在實際網(wǎng)格環(huán)境中，現(xiàn)競價有關的其他用戶信息則難以獲得。本文提出了基于重復博弈按出價比例分配網(wǎng)格計算資源的模型、求解方法和算法實現(xiàn)，將不完全信息下多用戶競價博弈轉化為完全信息下兩個用戶競價博弈，降低了用戶競價的復雜性。用戶在重復博弈的每個階段通過對所獲資源比例等信息來分析其他用戶的資源使用策略，按照優(yōu)化目標對下一階段的出價進行調整，可在掌握少量信息情況下，達到趨近于均衡的競價策略，實現(xiàn)用戶優(yōu)化目標下的資源分配。通過資源保留價格，可防止用戶合謀低價使用資源，保障資源提供者的利益，進一步促使用戶理性使用資源。

　　參考文獻：

　　[1]MACKIEJK，VARIANHR.Pricingtheinternet[EB/01].http：//ideas.repec.org/p/wpa/wuwpco/9401002.html.

　　[2]CHRISTOSHP.Algorithms，Game，andInternet[EB/01].http：//eecs.harvard.edu/～parkes/cs286r/spring02/papers/stoc01.pdf.

　　[3]BUYYAR，ABRAMSOND，VENUGOPALS.Thegrideconomy[J].ProceedingsoftheIEEE，93（3）：698-714.

　　[4]FOSTERI，KESSELMANC，TUECKES.Theanatomyofthegrid：Enablingscalablevirtualorganizations.Int’lJournalofSupercomputerApplications，2001，15（3）：200-222.[doi：10.1177/109434200101500302].

　　[5]FERGUSOND，YEMINIY，NICKOLAOUC.Microeconomicalgorithmsforloadbalancingindistributedcomputersystems[C]//Proceedingsofthe8thInternationalConferenceonDistributedComputerSystem（ICDCS’88），1988：491-499.

　　[6]FERGUSOND，NIKOLAOUC，YEMINIY.Aneconomyformanagingreplicateddatainautonomousdecentralizedsystems[C]//ProceedingsoftheInternationalSymposiumonAutonomousDecentralizedSystems（ISADS’93），1993：367-375.

轉載請注明來自：http://www.jinnzone.com/jisuanjiwangluolw/33179.html