[發明專利]一種基于社會效用的網格資源拍賣系統

無效

• 申請號: 201310242121.2
• 申請日: 2013-06-18
• 公開（公告）號: CN103426112A
• 公開（公告）日: 2013-12-04
• 發明（設計）人: 孫紹榮;劉曉露
• 申請（專利權）人: 上海理工大學
• 主分類號: G06Q30/08
• 分類號: G06Q30/08
• 代理公司: 上海德昭知識產權代理有限公司 31204
• 代理人: 郁旦蓉

技術領域

本發明屬于計算機應用技術領域，涉及網格計算環境中的資源分配系統，特別是涉及網格計算環境中考慮社會效用評估的資源分配系統。

背景技術

網格是利用互聯網把地理上廣泛分布的各種資源（包括計算資源、存儲資源、帶寬資源、軟件資源、數據資源、信息資源、知識資源等）連成一個邏輯整體，就像一臺超級計算機一樣，為用戶提供一體化信息和應用服務（計算、存儲、訪問等），最終在虛擬環境下進行資源共享和協同工作。

網格試圖實現互聯網上所有資源的全面連通，在網格系統中，資源分布于不同地理位置，屬于不同的所有者，而且是異構的和動態變化的。網格資源的這些特點使得網格資源的分配成為網格技術的關鍵問題。

簡單地說，網格資源分配就是將n個獨立的任務映射到m個異構的可用資源上，使得總任務的完成時間最小和資源得到充分利用。

目前，國內外網格計算環境中資源分配方法研究主要有：系統優化機制和經濟調度方式。

系統優化機制是一種以系統為中心的集中資源調度策略，是傳統的資源管理方法，主要思想是以系統為中心，以提高系統吞吐率、資源使用率、實現整個系統上所有任務的完成時間最小為目標，來對網格資源進行分配。

這種資源分配方式從提高網格系統性能的角度來研究網格資源的分配，可以有效提高系統的整體性能，但由于網格資源具有分布、異構、自治、動態等特點，這種方法難以適用于網格計算環境中，而且不能很好地滿足用戶的服務質量要求。

經濟調度方式是將用戶和資源提供者的利益目標用一定的價值形式來表述，用戶通過支付一定的費用來獲取資源的使用權，資源提供者則通過提供資源從中獲利，雙方為了獲得最大利益制定使用或共享資源的方法。利用經濟方法研究網格資源分配是當前網格研究新的熱點。其中主要用到的經濟機制有：市場機制、博弈機制和拍賣機制。

拍賣機制是當前網格資源分配的重要方法，通過對現有資源分配中拍賣機制的分析發現。拍賣機制遵循第一價格拍賣規則或者第二價格拍賣規則。其中，第一價格拍賣規則是在競價過程中，成交價為所有用戶報價的最高價；第二價格拍賣規則是在競價的過程中，成交價為所有競價用戶出價中的次高價，即贏得拍賣的用戶并不需要付出自己的報價，而只需要付出次高價。關于第二價格拍賣規則有定理：在第二價格拍賣規則中，講真話是每個用戶最好的競拍策略。

證明：假設有n個買主進行競拍，買主集合為，I＝{1,2,...,n}，所有用戶構成的出價組合為B＝{b₁,b₂,...,b_n}，用戶對單位資源價格的真實評價為V＝{v₁,v₂,...,v_n}，u_i表示買主i的效用函數，下面證明，b_i＝v_i能給買主i帶來最高的支付。

如果b_i＞v_i，則

其中，m_-i＝max{b_j:j≠i}

如果b_i＝v_i，則

兩相比較，如果買主i采取b_i＞v_i的出價策略，除了徒增v_i＜m_-i＜b_i時支付為v_i-m_-i＜0的風險以外，不會帶來任何好處。由此可得b_i≤v_i。

如果b_i＜v_i，則

將b_i＞v_i與b_i＝v_i的兩種情況進行比較，如果買主i采取b_i＜v_i的出價策略，除了徒增v_i＞m_-i＞b_i時失去贏得支付為v_i-m_-i＞0的風險以外，不會帶來任何好處。

因此買主i的最優出價策略為b_i＝v_i，在第二價格拍賣中，講真話是每個用戶最好的競拍策略，買主按照自己的真實評價出價是各自的優勢策略。