双向拍卖（精选4篇）
双向拍卖 篇1
引言
网格资源预留[1]可以视作网格资源管理系统(GRMS)中调度功能的一部分,它一方面根据用户的请求,为用户在特定的时间内预留一定数量的资源,从而可以保证任务在开始执行时获得必要的资源,为用户提供一定的QoS(Quality of Service)保证,另一方面,资源预留也可以优化资源的使用,提高资源的利用率。因此,资源预留自提出之日起便受到人们的关注。
在为资源预留建模的过程中,可以运用经济学的原理。基于竞争性的市场经济的网格资源预留模型更适合分布的、复杂的、带激励性质的环境下的资源管理:资源用户相当于商品消费者,资源提供者相当于商品供应商,用户使用供应商的资源并支付费用。这种利用经济模式管理网格资源的方式,将权利交到用户和资源的拥有者手中,用户和资源拥有者为实现效用或收益最大化做出他们自己的决策,这就使调度由以系统为中心转向了以用户为中心,用户可以自己作出决定以最小的代价获取最好的性能。
经济机制中的拍卖机制是通过多个资源需求者以不同的价格竞争资源,最后由“拍卖师”依据不同的准则选定中标人并确定资源成交的价格。常见的拍卖都属于单向拍卖形式,即“一对多”(1:N)的市场结构。而双向拍卖是一种全新的拍卖形式,它的市场结构是“多对多”(M:N),即买卖双方都不止一个的情形[2]。这种拍卖形式使买卖双方同时失去了各自在单向拍卖中的相对优势,他们之间的关系变为一种供给和需求的平等关系。双向拍卖特别适合于网格环境下众多买卖方的交易,在网格资源管理中具有广阔的前景。近些年来,双向拍卖在经济学研究领域备受关注。
本文重点研究经济模型在网格资源预留机制中的应用,针对网格环境存在多资源提供者和多资源请求者等特点,引入双向拍卖价格机制,提出了一种基于双向拍卖机制的网格资源预留策略,实现网格资源灵活有效的管理。
1 相关工作
目前,对网格资源提前预留的研究主要包括:文献[3]提出了一种兼顾排队任务的资源预留机制,优化非预留任务的平均等待时间,有效的控制了资源预留的滥用,提高了预留的有效性;文献[4]提出了一种基于动态资源预留的任务映射算法,该算法基于为关键任务动态预留资源来缩短任务的执行时间,优化调度性能;文献[5]提出了一种统一的资源预留策略,将计算资源和其它资源统一调度来提高调度效率等等。
从目前对资源预留的研究来看,预留系统还存在两个急需改进的问题:
(1)已有模型中,用户预留请求虽然包含有明确的或灵活的任务开始时间、结束时间、资源数量需求等约束条件,但是由于资源被不同的组织所拥有,要吸纳各类资源拥有者加入网格,就必须满足他们各自的需求,因此,传统的资源分配方法已经不能满足需要。
(2)许多已有的研究局限于单一的资源提供者,采用集中式的优化算法选择预留请求,实现资源利用率的最大化,而没有考虑网格资源的可选择性问题。
鉴于此,本文引入价格因素,建立包含价格机制的资源预留服务,使得资源的拥有者可以通过贡献其资源为他人所用来获得利益的激励。同时,针对问题(2),本文借鉴近年在经济学领域备受关注的双向拍卖的特点,提出特别适合于网格环境下众多买卖方交易的M:N的资源定价模型,这增强了对网格资源进行有效激励、方便灵活的管理,具有广阔的前景。
2 有价格的网格资源预留模型
在 GGF GRAAP 工作组制定的有关提前预留技术的文档“Advance reservations: State of the Art”[6] 中,明确了网格环境下资源提前预留的定义:由资源的请求者通过协商过程向资源的所有者获取对该资源在某一时间段内的授权。从定义我们可看出资源预留有三个要素:第一个要素确定了预留资源的未来占用时间,第二个要素确定了对资源性能的需要,第三个要素指出了预留获得的方式要通过用户和资源所有者的协商。
在有价格的网格资源预留模型中,我们依据上述三个要素定义资源预留请求,并在已有的资源预留模型中加入价格机制,采用双向拍卖的策略对资源进行定价,实现有价格的资源预留,以此来激励资源的拥有者提供可用资源,吸引更多的资源加入网格。资源预留过程如下图1所示:
3 基于双向拍卖的资源定价策略
3.1 系统的参与者
双向拍卖机制中分三类参与者,系统框架如下图2所示:
a、资源供应商代理(Resource Supplier Agents,RSA):
资源供应商代理代表资源的拥有者提供其所有拥有的资源为用户提供有偿服务,资源将通过双向拍卖的方式进行有偿预定。这里我们只考虑单一的系统资源,例如CPU、内存、存储器、网络带宽等。
b、资源消费者代理(Resource Consumer Agents,RCA):
资源消费者代理代表用户按照用户的需求参与资源竞争,将用户的应用请求转换为对资源的请求,在网格市场发布资源需求。RCA可以是计算机软件或直接是用户本人。
c、拍卖管理者(Auction Manager,AM):
匹配资源买卖双方。网格资源管理者负责管理和监控系统中资源的竞拍和预留过程,受理合法的竞拍请求,发布当前的资源价格,决定拍卖的胜者等任务。
3.2 系统思想和拍卖流程
在基于拍卖的市场中,由于资源的交易是不断进行的,因此,拍卖的过程也是连续的,但是为了方便统计以及交易双方可以调整自己的价格,可将拍卖过程按轮进行,每轮拍卖持续的时间Tg由AM统一设定。
双向拍卖定价策略是在交易的多个资源买方和多个资源卖方中进行匹配。假设网格资源消费者(买方)的个数记为m,资源供应商(卖方)的个数记为n,系统共有L=m+n个参与者。拍卖流程如下:
(1)资源供应商代理和资源消费者代理分别代表各自的资源域向资源的管理者发布供求信息,信息包括资源的类型、起始时长、持续时间、起始价格、涨幅(对于RSA是跌幅)、底限价格、当前价格。
(2)RCA根据对市场的了解情况和自己对计算资源的需求程度向AM提交自己的资源预留请求;RSA根据自己的成本情况向AM提交自己的资源供应情况;AM对本轮中接受到的买卖双方的初始价格分别进行排序,资源消费者i向AM提交的单位计算资源出价(biddingprice)记为x[i],资源供应商j向AM提交的单位计算资源开价(askingprice)记为y[j].,AM对RCA的标价进行降序排序,设为:x1> x2> x3>…>xm 。AM对RSA的开价进行升序排序,设为:y1
(3)提供最低价格的RSA与出价最高的RCA进行匹配(当x[j] >= y[i],成交价则为双方出价的均值),然后出价第二高的RCA与要价第二低的RSA交易,这样的过程持续下去,直到余下的RCA的出价均低于RSA的要价。如果存在出价相同的情况,则按照先来先服务的原则进行匹配。
(4)拍卖按轮次连续进行。当供需双方条件相符,但是价格达不成一致时,在下一轮拍卖前,资源提供方的价格按照提前设定的拍卖策略,减少Pchange,资源需求方则按照拍卖策略增加Pchange,重新转到步骤(2)。成交前,供给方和需求方可实时修改价格方面的参数,例如根据拍卖状况适当调整底限价格。
(5)成功匹配的RCA退出拍卖系统,发送到资源管理者处,进入已接受的资源请求队列,询问是否能够在[Tstart ,Tstart + Tlast]时刻段内预留资源量 N。如果资源调度系统能接受该请求,则返回给用户一个表示预留成功的信号。同时资源预留请求进入资源上的预留队列,等待调度。如果不能接受预留请求,则它响应一组可以开始预留的时间,用户可以选择一个和 Tstart 相近的实际开始时间 Ta,或重新排入需求队列,寻找新的资源提供者。
五个过程循环进行,形成活跃的计算市场。在这过程中,可能要有新的参与者加入,也可能有参与者退出,在参与者众多的市场中,少量参与者的进入与退出市场不会影响市场的正常运转。
4 双向拍卖的定价算法
我们将网格中m个资源消费者(买方)的资源请求队列表示为X=
Function sort(x[m],y[n])
/* 对资源消费者价格数组降序排序 */
for j from 1 to m-1
for i from 1 to m-j
if x[i].price < x[i+1].price
then x[i]与 x[i+1]交换
endif
endfor
endfor
/* 对资源供应商的要价数组升序排序 */
for j from 1 to n-1
for i from 1 to n-j
if y[i].price > y[i+1].price
then y[i]与 y[i+1]交换
endif
endfor
endfor
AM对拍卖价格的匹配算法如下:
/* 资源消费者价格数组x[m]
资源供应商价格数组y[n] */
Function match(x[m],y[n])
for i from 1 to m
if x[i].price >= y[i].price
then 匹配成功 flag[i=1;
/* 中标价格为资源供应商和消费者的均值 */
x[i].price = ( x[i].price + y[i].price )/2
else
匹配失败 结束循环
end-if
end-for
Function reprice(x[i])
/* 一轮拍卖结束后,资源消费者的重定价 */
x[i].price = x[i].price + x[i].Pchange;
if x[i].price > x[i].Plimit
x[i].price = x[i].price - x[i].Pchange;
end-if
return x[i].price;
5 实验与结果
为了验证提出的基于双向拍卖的网格资源预留机制的效率,我们编制了仿真程序进行仿真试验。首先,假设资源供应商提供的资源的成本是 cost,对于资源消费者其价值是value,卖者和买者分别同时选择要价s和出价p,cost、value、s、p分别在[0,1000]上取值。如果s≤p,则双方在p=(s+p)/2上成交,卖者的效用为us=(s+p)/2-cost,买者的效用为ub=value-(s+p)/2;如果s>p,则没有交易发生,双方的效用均为零。
在此,我们只考察买卖双方个数相等或相近时参与者个数对双方效用的影响。在实验中,资源消费者对CPU资源的需求量和资源供应商对CPU资源的供给量分别服从均匀分布f1=f2=U(1000,10000)(单位:Mflops)。资源供应商边际成本服从均匀分布fc=U(50,80)(单位:Grid$/1000Mflops),资源消费者边际支出fv分别服从均匀分布U(30,60),U(50,80),U(70,100)。买卖双方个数相等,即m=n,取值分别为20,60,100,300,600,800,1000。每种情况的效率取100次实验的平均值。实验结果如图4所示:
从图4中可以看出,效率是和参与拍卖的买卖双方的个数成正比的,参与的用户越多,效率也就越高,由这个实验结果,可以看出该拍卖机制适用于有大量拍卖参与者的情况,这非常符合网格系统的要求。随着资源消费者边际支出由U(30,60)变化到U(50,80),再变化到U(70,100),相应的效率在不断增加,这说明资源消费者相对资源供应商的边际成本越高时,成交的机率增大,相应地效率也增加,这符合经济活动中的实际情况。
模拟试验表明,基于双向拍卖的资源预留机制中,资源供应商和资源消费者双方只有充分把握市场行情,合理的出价要价,才能提高预留请求的接受率,双方才能获得最大收益。
6 结论
运用市场机制解决网格资源分配问题是网格资源管理的重要研究方向。针对不可存储的网格资源,资源利用率低,价格波动大,将拍卖理论应用于网格资源预留,结合原有的预留模型给出了一种可行的灵活市场定价策略,即基于双向拍卖理论的网格资源预留机制。模拟试验表明这种灵活的市场定价策略很适合网格资源预留机制,本文采用定价和竞标拍卖分配空闲网格资源来实现QoS的方法为网格资源管理开辟了一条新的思路。
参考文献
[1] Zhixing Huang, A Research of Economic-based Approaches to Supporting Advance Reservation in Grid Environment[D]. Chongqi:Southwest China Unversity, 2006.
[2]WENG ChuLiang,LU XinDa.A double Auction Method for Resource Allocationon Computational Grid[J].Chinese Jour-nal of Computers,2006.29(6).
[3] HU Zhigang, CHEN Ren. A Resource Reservation Mechanism Considering Queued Tasks[J]. ComputerEngineering,2006,32(12):61.
[4]HUZhi-gang,LV Zhen-heng.A Task-mapping Algorithm Based on Dynamic Resource Reservation[J].Application Re-search of Computers,2005,(7):12-13.
[5]Yang Changxing,LV Zhenheng.A Unified Resource Reserva-tion Pollicy[J].Computer Engineering and Applications,2005,(24):144-145.
[6]MacLaren J.Advance Reservations:State of the Art[R]Global GridForum,ggf-draft-sched-graap-2.0,2003.
双向拍卖 篇2
1、实验设计
市场实验最早由Chamberlain(1948)开创。史密斯在Chamberlain实验基础上改进并设计了双向口头拍卖实验,其出价、交易价格都是公开信息(Smith,1962)。实验表明,即使交易者缺乏经验,市场最终也将达到均衡(Davis& Holt,1993)。
实验选取中南财经政法大学经济学院经济学专业2012级的本科生采取纸笔实验方式进行。在公布实验说明后,首先随机抽取了18名学生,然后随机决定其中的9名为卖方,9名为买方,分坐在教室两侧。介绍实验具体规则后,买方随机抽取一张交易信息卡片,卡片上标注了每轮交易产品的保留价值,而卖方随机抽取的交易信息卡片上标注其每轮交易产品的生产成本。买方保留价值由最高5元,依次下降0.25元到最低3元,而卖方生产成本由最低2.25元依次上升0.25元到最高4.25元。每组实验重复进行6轮。每轮实验开始时,买方和卖方在指定交易区域交易,买方(或卖方)与卖方(或买方)会自主进行协商直到交易达成或规定时间用完,限定交易价格不得低于卖方的生产成本,也不得高于买方的保留价值。每当有交易达成时,交易价格会即时在黑板上公布,达成交易的双方在本轮不再进行交易。首轮交易限定的时间为5分钟,随后每轮交易的时间为3分钟。6轮实验全部完成后,交易所得计算方式如下:买方获取每轮的保留价值与其相应的交易价格之间的差额总和,卖方获取每轮的交易价格与其生产成本之间的差额总和。
2、实验结果
由上述实验设计,预期随着实验不断进行,市场交易应该会逐步趋向均衡价格和均衡数量。上述简单的供求实验中,预估市场交易的均衡价格会在3.5元到3.75元之间, 交易达成个数应为5-7个。实际每轮的交易价格如表1所示,标 * 号的交易价格表明该价格是位于均衡价格区间内,表1的最后一行给出了每轮的平均交易价格。
由表1可知,随着实验轮次的进行,每轮交易中处于预期价格区间的个数在逐步增加,同时,每轮实验的平均价格也在逐步向理论预测的交易均衡价格趋近。可见,当市场制度是双向口头拍卖市场时,市场行为能够很好地符合完全竞争模型。
二、买方明码标价
1、实验设计
作为双向口头拍卖市场交易的一个变形,接下来我们进行了买方明码标价的实验。实验参数设计与双向口头拍卖的基本相同,不同之处主要有两点:一是我们进行的实验是跨被试实验。实验的参与者是重新随机选择,并且与双向口头拍卖实验的参与者完全不同,交易中的买方或卖方角色也是随机确定的,以避免实验中的“次序效应”;二是在此组实验中,买方先行报价,卖方有选择接受与否的权利。具体而言,买方先行确定产品报价并上交给实验管理者后公布在黑板上。卖方从实验管理者手中随机抽取一张数字可能为1-9中的某一个整数的排序卡片,以确定交易的顺序。依照抽取的数字卡片的顺序,从第1号开始,每个卖方都被问到其是否选择接受某一买方的报价,当然他们可能拒绝所有买方的报价。若卖方接受某一报价,该交易即达成,并在黑板上划去该报价。整个实验直到所有的卖方完成回答。每一轮实验开始时,买方可以重新报价,价格可以与上一轮的价格存在差异。卖方的交易排序数字卡片也会收回和重新发放。实验同样进行6轮,6轮实验全部完成后,交易所得计算方式与双向口头拍卖实验相同。
2、实验结果
可以预期随着实验不断进行,市场交易应该会逐步趋向均衡价格和均衡数量。买方明码标价实验中,由设计的生产成本和保留价值的数值,可以预估市场交易的均衡价格应该会在3.5元到3.75元间,理论上的交易达成个数应为5-7个。实验中每轮的交易价格如表2所示,标 * 号的交易价格表明其是位于均衡价格区间内,表2最后一行给出了每轮的平均交易价格。
由表2可知,随着实验轮次的进行,每轮交易中处于预期价格区间的个数在逐步增加,同时,每轮实验的平均数也在逐步向理论预测的交易价格趋近。
三、卖方明码标价
1、实验设计
作为双向口头拍卖市场交易的另一个变形,随后进行了卖方明码标价实验。参数设计与双向口头拍卖基本相同,不同之处主要有两点:一是实验仍然是跨被试实验。二是卖方先行报价,买方有选择接受与否的权利。具体而言, 卖方先行确定产品报价并上交给实验管理者后公布在黑板上。买方从实验管理者手中随机抽取一张数字为1—9中的某一个整数的数字卡片,以确定交易顺序。依照抽取数字卡片的顺序,从第1号开始,每个买方都被问到是否接受某一卖方的报价,当然他们可能拒绝所有卖方的报价。如果买方接受某一报价,该交易达成,并在黑板上划去该报价。整个实验直到所有的买方完成回答。每一轮实验开始时,卖方可以重新报价,价格可以与上一轮的价格存在差异。买方的交易数字卡片也会收回和重新发放。实验同样进行6轮,6轮实验全部完成后,交易所得计算方式与双向口头拍卖实验相同。
2、实验结果
可以预期随着实验不断进行,市场交易应该会逐步趋向均衡价格和均衡数量。卖方明码标价实验中,由生产成本和保留价值的数值,可以预估市场交易的均衡价格应该会在3.5元到3.75元间,理论上的交易达成个数应为5—7个。实验中每轮的交易价格如表3所示,标 * 号的交易价格表明其是位于均衡价格区间内,表3的最后一行给出了每轮的平均交易价格。
由表3可知,随着实验轮次的进行,每轮交易中处于预期价格区间的个数与双向口头拍卖和买方明码标价实验中存在一定差异,同时,每轮实验的平均数也在与理论预测的交易价格存在明显不同之处。
四、结论
综合表1、表2、表3,可得到以下结论。
第一,均衡价格的排序上,卖方明码标价市场的价格高于双向口头拍卖市场的价格,买方明码标价市场的交易价格则低于双向口头拍卖市场的交易价格。理论上交易价格应该在3.5元到3.75元间,双向口头拍卖的平均交易价格几乎每轮都落在该区间中,每轮中至少有一个以上的交易价格也是位于该价格区间。明码标价实验中,位于价格区间的交易个数明显减少,原因在于:买方明码标价实验中, 买方初始尝试压低价格,以获取尽可能多的消费者剩余, 但由于市场卖方力量作用,价格逐步提高并向均衡价格趋近;卖方明码标价实验中,为获取尽可能高的利润,卖方初始报价较低,但随着实验的进行,报价有不断走高趋势。
双向拍卖 篇3
动态频谱分配作为认知无线电技术的关键技术之一,也是国内外研究的热点问题。目前常见的有四种频谱分配模型:1)基于图论的频谱分配模型,peng和zheng等人提出的标签机制将动态频谱问题归纳成一个对CSGC图的染色问题[2];2)基于博弈论的频谱分配模型,HuiyeMa采用博弈论方法研究了P2P网络中的带宽分配问题[3];3)干扰温度模型,吴等认为在满足干扰温度门限的用户中间,频谱可以再用[4];4)基于拍卖的频谱分配模型,
基于定价拍卖的系统模型
利用微观经济学中定价拍卖原理而定制的无线电资源分配机制在近几年得到广泛的研究,而且已经被证明是认知无线电网络的频谱分配问题的有效解决方法[5]。在这种基于拍卖的频谱分配模型中网络结构一般采用集中式结构,认知无线电用户是投标者,中心接入点(AP)或基站(BS)在一次拍卖中充当拍卖人。在一个拍卖轮回中,每个投标者为满足自身需要给频谱资源投标,由拍卖人根据认知无线电网络收益等原则确定胜利者[6]。
基于定价拍卖的频谱分配模型根据不同的网络效用需要来确定自身的目标函数,即确定赢家胜出的规则[7]。例如采用最大系统吞吐量原则将某段频谱分配给在其上吞吐量拍卖值最大的用户,利用效用公平原则和时间公平原则保证投标者在竞争频谱资源过程中的效用公平和时间公平。基于定价拍卖的频谱分配模型的特点:1)非合作的用户行为。2)分配算法需要合理的执行时间和合理的计算开销。3)信令开销小。
1 系统模型
本文采用系统模型如图1。
在一个认知无线电网络中,有多个主用户和多个次级用户。主用户可以是中心接入点(AP)或基站(BS)[8]。次级用户是一些移动的认知设备,主用户是授权用户,可以使用一定范围的频段,这些授权频段被分为若干互不重叠的子频段,当这些子频段空闲时,主用户希望将这些频段出租以获取收益;次级用户希望租赁这些空闲的子频段满足自己的需求。
假定一个认知无线电网络中共有M个相互正交的空闲子频段组成一个频谱池,有N个次级用户。假设子频段是完全相同的(相同的中心频率、带宽、调制方式等)。每个有者对空闲子频段的成本为ci,(i=1,2……M),第j个次级用户对于空闲子频段的估价为vji,(i=1,2,……M,j=1,2,……,N)
假设每个子频段只能分配给一个次级用户使用,且一个次级用户在同一时刻只能使用一个空闲的子频段。
定义:1)矩阵V={vji}N×M为次级用户和主用户之间的子频段估价矩阵
2)矩阵R={rji}N×M为分配矩阵,rji=1表示频谱拥有者i分配一个空闲频段给次级用户j使用,反之,不分配。
3)当频谱拥有者i分配一个空闲频段给次级用户j,则主用户的收益为pi-ci
4)当主用户以pi的价格将空闲频段卖给次级用户j,则次级用户的收益为vji-pi
次级用户的最大收益为:
则追求最大经济利益的目标函数为:
2 拍卖机制设计
多物品双向拍卖机制设计以确定市场出清价为中心,最长用的是马歇尔路径法[9],但该模型中每个买方卖方只交易一个物品。本文建立了一个简洁实用的模型以确定市场出清价,并在交易多个物品的买方和卖方中进行匹配。该模型假设交易的是无差别的同类物品,每个买方和卖方可交易多个物品,他们的出价可能相同。
一个多物品双向拍卖,有B个买家和S个卖家共有G=B+S个参与者,每个参与者各自出价,将所有的出价从大到小排列,假设参与者i出价pi交易xi个物品。卖方出价销售的物品总数为M,买方出价购买的物品总数为N,则M=∑xi,N=∑xi yj=∑xi。
规则求满足yt≤M
规则2求满足yt≤M
价格调整,随着时间的变化,频谱的数量和频谱需求也是不断变化的,为了追求利益的最大化,在供过于求时提高频谱的利用率,在供不应求时获得更高的经济利益。在上一次拍卖成交价的基础上,及时调整买家、卖家报价。买家的报价高于P的减小一个步长,p'=p-ε卖家报价低于p的,报价增加一个ε。
3 系统仿真
假设在一个100×100的区域内有B=5个频谱拥有者,每个频谱拥有者有4个可用空闲信道,有S=3到15个次级用户,用户需求频谱数为(1,2,3,4,5)中随机选取一个。假设频谱池中的频谱成本均匀分布在(5,15)范围内,估价均匀分布在(10,30)范围内,图1比较了轮流报价得到的总收益和竞争均衡得到的均衡收益,由图可以看出实际收益与均衡收益的俩条曲线基本保持平衡,这说明频谱分配基本接近理想的分配。图2是实际成交价格和均衡价格的比较。从图中可以看出,随着次级用户数的增加,实际成交价格和均衡价格曲线变化一致,成交价格的总体趋势是上升的,。这是由于次级用户的增加,频谱由供过于求向供求平衡改变,导致竞争加剧、价格上升,这一现象与经济学原理相符。
4 结束语
本文提出了轮流报价的双向拍卖模型运用经济学理论来解决非合作的动态频谱分配问题,仿真结果表明本文的快速出清算法具有很高的频谱分配效率。由于拍卖机制的自身的缺陷,买方卖方有可能串谋,从而降低分配效率,影响成交价格和总的收益,所以双向拍卖机制中如何避免用户的串谋,还有待进一步研究。
摘要：认知无线网络中,有多个主用户和次级用户。主用户是授权用户,当频谱空闲时希望出租这些空闲频谱以获取一定的收益,次级用户希望租赁这些空闲的频段满足自己的需求。基于微观经济学原理,提出轮流报价的双向拍卖策略。在频谱拍卖过程中,建立了一个简洁实用的模型以确定市场出清价,并在交易多个物品的买方和卖方中进行匹配,并在上一次拍卖成交价的基础上,及时调整买家、卖家报价,快速完成交易。
关键词：认知无线电,动态频谱分配,拍卖理论
参考文献
[1]Mitola J.Cognitive Radio:Making Software Radios More Personal[J].IEEE Personal Communications,1999,6(4):13-18.
[2]Peng C,Zheng H,Zhao B Y.Utilization and fairness in spectrum assignment for opportunistic spectrum access[J].Mobile Networks andApplications,2006,11(4):555—576.
[3]Wang W.Liu List-Coloring based channe1 allocation for open—spectrum wireless networks[C]//2005 IEEE 62nd Vehicular TechnologyConference(VTC).Dallas:IEEE Communications Society Press,2005:690—694.
[4]Nie N,Comaniciu C.Adaptive channel allocation spectrum etiquette for cognitive radio networks[J].Mobile Networks and Applications,2006,¨(6):779—797.
[5]Krishna V.Auction Theory[M].San Diego:Academic Press,2002.
[6]Zhou X,Gandhi S,Suri S,et a1.eBay in the Sky:Strategy Proof Wireless Spectrum Auctions[C]//Proceedings of the 14th ACM Internation-al Conferenceon Mobile Computing and Networking.New York,USA:ACM,2008:2-13.
[7]Krishna V.Auction Theory[M].America:Academic Press,2002:43257.
[8]Huang J,Berry R A,Honig M L|Auction-based spectrum sharing[J].Mobile Networks and Applications,2006,11(3):405 408.
双向拍卖 篇4
由于无线电频谱的限制,通信网络面临频谱资源稀缺的问题,另一方面,许多许可频谱仍然长时间[1]未被占用。认知无线电(CR)可提高频谱资源利用率,在CRs中,部分用户可以智能地监控环境并在分配的频段都处于闲置状态时能够与许可用户共享频谱,通过许可用户(PUs即主用户)和未经许可的用户(SUs即次级用户)[2]之间的频谱共享实现CR网络频谱利用率的增加。
本文提出了一种基于双向拍卖融合贝叶斯推理模型的频谱共享算法,假设主用户和次级用户是自相关博弈玩家,他们为了达到最大化收益的目的而做出决策。本文算法自适应地响应不断变化的系统环境和玩家数量,具有良好的可扩展性,为了达成有效拍卖共识,本文算法适用于现实世界CR系统的操作,同时能尽可能高的保持频谱效率。
1 相关研究
学者们提出了许多用于CRs中有效频谱共享的拍卖博弈模型[3],可更为有效地解决有限稀有资源分配问题。拍卖博弈模型通过减少未分配的频段数量可以提供更好的频谱共享,提高了整体资源利用率[4]。
文献[5]中的战略型频谱拍卖(SPSA)方案是一种真实且计算高效的频谱拍卖,支持类似e Bay的动态频谱市场,该方案允许无线用户获取并根据要求支付频谱。此外,SPSA方案通过分配频谱给最重视它的投标人能使频谱所有者利润最大化。然而,SPSA方案仅考虑购买者的单向频谱拍卖,该SPSA方案可直接扩展为真实双向频谱拍卖(TDSA)方案[6],TDSA方案支持真实双向频谱拍卖,其中多方可根据个性化需求交易频谱,该方案运用一种新的赢家确定和定价机制选择获胜买家和卖家,然而TDSA方案只假定简单的频谱需求/请求格式。文献[7]中重复拍卖贝叶斯学习(RABL)方案建模为一个重复拍卖博弈,该方案研究了由监控成本和访问成本构成的认知无线电系统的频谱接入问题。因此,重复拍卖模式已用于最大限度地权衡访问频段的收益和成本。此外,为了设计一种具有不完整信息的方案,构建了基于狄利克雷过程的非参数信念更新算法。文献[8]中的自适应拍卖频谱共享(AASS)方案是一种基于非合作博弈模型描述PUs和SUs之间竞争力的拍卖,该方案采用Hackner效用函数定义二次用户的频谱出价。此外,AASS方案为每个PU的成本函数提出了一种动态更新算法,这有助于在动态频谱共享博弈的每个阶段PUs从SUs实现更多的要求。文献[9]中的基于双向拍卖频谱共享(DASS)方案是一种基于动态频谱共享方案的双向拍卖,该方案允许免费频段在运营商之间交易,以提高频谱利用率,DASS方案使用自适应调节投标/询问策略研究实际的无线通信模型。
上述方案存在的主要问题有:首先,这些方案依赖于高复杂性和额外开销,无法在现实的系统操作中实施,因此仅限于较小的网络模型;其次,现有的方案不能自适应估计当前网络条件,在动态网络环境中可能造成潜在的错误决策;再次,这些方案有一些固定的系统参数操作网络系统,而在动态的网络环境中,操作现实世界的网络系统是不恰当的方法。受到上述讨论的启发,本文提出了一种新的CR频谱共享方案,将其设计为一个重复贝叶斯拍卖博弈。
2 提出的频谱共享算法
2.1 博弈模型
博弈理论在无线网络中可应用于资源分配[10],然而传统的博弈模型假设任意玩家需要的所有信息都完全已知,这并不符合现实情况。基于此,传统博弈模型不能直接应用于实际网络运营,文献[11]引入了贝叶斯博弈模型,该模型放宽了所有信息完全已知的假设,可以用于预测不确定性结果。
本文采用贝叶斯博弈方法解决CR系统中频谱共享问题,贝叶斯模型由一组玩家、一组动作、玩家类型和每个玩家的效用函数等组成[12],提出的贝叶斯拍卖博弈如下:
玩家:CR系统中PUs和SUs,N={1,2,...,N}和M={1,2,...,M}分别表示PU集合和SU集合,PUi∈N运行在频带Bi上,其与PUs其他的频带不重叠,即Bi∩Bk=Ø,∀i,k∈N。
动作集:任何PUi都具有所有可能报价的集合,是预计出售Bi频段的价格。任何SUj都具有所有可能出价的集合,这是SUi可以支付的价格。
玩家类型:玩家的类型是一个概率分布,用来表达有关博弈玩家不确定或未知信息的概念,类型独立且在重复拍卖阶段动态变化,每个玩家完全知道自己的类型,而不知道其他玩家的类型,因此概率分布用于假设其他玩家的类型。
效用函数:效用函数可量化玩家从特定结果获得的满意度,PUs的效用函数代表货币收益(即频谱交易收入),对于SUs,拍卖价格越高,效益越低,因此SUs的效用函数定义为PUs的保留效用,如果PUs或SUs频段交易失败,该收益将保持0。
本文算法可归结为一种重复博弈[13],该算法将时间轴划分为等长度间隔time_period(即Pt,t=0,1,2,⋯)。
2.2 双向拍卖协议
传统的拍卖主要涉及一个拍卖商(卖方)和多个投标人(买家),该结构称为单向拍卖,而在频谱共享的拍卖场景中,存在几个买家和卖家对频段进行投标(即愿意支付的价格)及报价(即预期的销售价格)的情况,该情况下的拍卖模式设计为多对多的双向拍卖结构。
模型中的系统操作员定义为拍卖商,负责定价和交易频段。N中PUs可以是卖方,卖家可以报价给拍卖商,以显示其在价格上的偏好,M中SUs可以是投标人,投标人投标购买频段。每个time_period,玩家之间的频谱拍卖(即PUs和SUs)周期性运行,对于每个拍卖阶段,买卖双方基于其效用函数估计频段价值,当所有的报价和出价送到拍卖商之后,拍卖商设置频谱共享交易价格,并决定哪个投标人从哪个卖家获得频段。采用普雷斯顿⁃迈克菲双向拍卖(Preston⁃Mc Afee Double Auction,PMDA)协议的基本概念决定商品价格,在每一轮拍卖结束后,拍卖商收集所有有关报价和出价的信息,并通过分类和匹配技术[14]决定交易价格,然后拍卖商对所有玩家宣布决定的商品价格,因此,玩家学习CR系统中当前频谱共享条件,SUs(即投标人)获得所需频段,在接下来的一轮拍卖不会提交新出价,如果一些SUs竞标频段失败,他们将提交新的出价给拍卖商,同时,如果一些PUs没有售出自己的频段,他们在下次拍卖时也将提交新的报价。因此,在每一轮拍卖中,剩下的玩家自适应地调整自己的价格,这种动态的拍卖程序依次重复每一个time_period(即串行拍卖),以达成有效拍卖共识。
2.3 贝叶斯推理和学习
贝叶斯博弈模型中,玩家学习修改自己的先验知识并自适应地调整策略。该方法并不假定玩家总是根据完整信息作出最佳决策,贝叶斯博弈的过程中,玩家有机会重新考虑目前的策略和应对以最大化期望收益,因此它提供了真实世界环境下更现实的模型。
玩家对频谱交易的渴望度强烈影响玩家的出价方案,通常情况下,玩家不知道其他玩家的愿望,但它实际上隐藏在每一轮拍卖中拍卖商的交易价格中。为了提交新的买价和卖价,买卖双方推断出下一轮交易价,这称为拍卖商类型。在每一轮拍卖中,玩家可以通过拍卖商的建议了解到别人的出价信息,基于该推论,每个玩家都可以为下一次拍卖做出更好的价格决策。
贝叶斯学习方法用来推断他人的渴望水平,根据贝叶斯定理和更新规则,贝叶斯推理公式[13]如下所示:
基于贝叶斯学习方法,开发每个玩家的价格调整过程,为了推断出下一轮交易价格,定义两个参数:拍卖商的让步比CRa和渴望水平η,它们用于贝叶斯推理公式中的假说,CRa估算如下:
式中:TP[t],TP[t-1]分别表示第t次和第(t-1)次博弈阶段的交易价格,如果CRa(t)是负值,则意味着拍卖商增加了交易价格。拍卖商第t个博弈阶段的渴望水平表示为η(t),η(t)值越高,对应于进行光谱段交易的愿望越强烈。假定η值范围固定在-0.5~0.5之间,且均匀地分成10个间隔,η值是离散集合的一个元素,即η∈{η0=-0.5,η1=-0.4,...,η9=0.4,η10=0.5}。
P(CRa(t)|ηi(t))为给定拍卖商渴望水平ηi(t)下拍卖商的让步比,P(CRa(t)|ηi(t))越高,在给定期望值η(t)时,拍卖商的让步比更可能是CRa(t)。本文假设概率密度函数P(CRa(t)|ηi(t))服从正态分布[15]:
式中:θ=(1-CRp(t))×ηi(t),CRp(t)为玩家自己的拍卖让步比,平均值μ和标准差σ产生不同的正态密度曲线,每个玩家有不同的μ值和σ值,使用式(3)定义另一个条件概率P(ηk(t)|CRa(t)),拍卖商在给定CRa(t)条件下的渴望水平ηk(t),根据贝叶斯更新规则,该P(ηk(t)|CRa(t))值如下:
基于Pt(ηk(t)|CRa(t)),Pt(ηk(t))值为:
式中:ηk={η0,η1,η2,...,η10}。
根据Pt(ηk(t))概率分布更新,当前拍卖人的愿望水平ηe可估计如下:
为了获得更精确的ηe值,贝叶斯推理过程重复迭代每一time_period,玩家持续监视当前的拍卖情况,以分布式方式决定自己的策略,最后,卖家和投标人可为下一轮拍卖调整自己的报价(Oft+1)和投标(Bit+1):
式中T_Pt为已公布的当前拍卖的交易价格(即第t个博弈阶段)。
2.4 本文算法的主要步骤
通过使用贝叶斯博弈模型为CR系统设计了一个新的频谱共享方案。提出的方案中,PUs和SUs(即博弈玩家)自适应地选择自己的拍卖价格分享频段。基于反馈学习过程,玩家可以捕捉如何调整自己的价格策略,为达成共识,该过程制定为重复拍卖模型。每一轮拍卖结束后,玩家定期检查目前的交易价格,并以完全分布式的方式迭代调整价格,因此玩家的数量增加时计算复杂度不会显著增加,这种交互式反馈过程持续进行,直到达成共识。提出的频谱共享算法的流程图如图1所示,主要步骤如下:
步骤1:初始迭代(t=0),每个拍卖商渴望水平Pt(ηk)的初始概率为均匀分布(Pt(ηk)=1/|L|,∀i,其中|L|是η时间间隔的总数)。
步骤2:每次拍卖阶段,频谱卖家i∈N={1,2,...,N}和频谱买家j∈M={1,2,...,M}发送报价oi和出价bj给拍卖商。
步骤3:拍卖商收集所有报价{o1,o2,...,on}和出价{b1,b2,...,bm},然后按递减排序报价,按升序排序出价。
式中π和σ为上述定义的顺序统计排列。
步骤4:拍卖商发现k,使得bπ(k)≥oσ(k)且bπ(k+1)<oσ(k+1),如果bπ(1)<oσ(1),继续执行步骤(5),否则拍卖商确定当前交易价格(T_P)。
步骤5:卖家提供的价格比T_P低,买家出价高于T_P,以T_P价格成功交易频段。
步骤6:拍卖商宣布目前T_P,并发送拒绝消息给当前一轮拍卖交易频段都不成功的卖家和投标人。
步骤7:以分布式方式,交易失败的卖家和投标人通过式(2)~式(7)动态调整拍卖价格。
步骤8:如果至少有一个卖方、一个投标人提交新的报价和出价,则转到步骤3进行下一轮拍卖,该迭代反馈过程一直持续到卖家和投标人达成共识,否则,进入终止步骤。
终止:拍卖博弈处理时间暂时结束,而CR系统持续自我监控,当新的频谱共享要求(即报价和出价)到达,它可以重新触发频谱共享算法。
3 仿真实验
进行仿真实验评估本文算法的性能,将本文算法与其他现有方案的性能做比较,并确认了本文算法的性能优势,为了确保该模型充分通用且在真实世界有效,假设如下:
(1)新的应用程序请求服务生成过程服从速率为λ(服务/秒)的泊松分布,提供的负载变化范围从0~3.0;
(2)CR系统的总频谱容量为5 Mb/s;
(3)基于50次模拟运行获得的结果,系统性能测量值绘制为每秒提供负载的函数;
(4)N中PU总数为30,M中SU总数为15;
(5)通过模拟获得的性能标准为PUs的收益、交易成功概率、频谱利用率、系统吞吐量、SUs请求阻塞概率、平均每轮拍卖次数等;
(6)频谱利用率定义为归一化的频谱效率,该值基于网络传输数据量进行测量;
(7)PUs的收益为频谱共享总价格;
(8)网络吞吐量为归一化值,为成功提供服务数据量与总数据量比值;
(9)为了表示各种多媒体应用,假设有四个不同的通信类型,基于连接的持续时间、频谱需求和Qo S要求,它们以相同的概率生成;
(10)对于不同的多媒体运用,应用程序服务的持续时间服从不同均值的指数分布。
对于多个应用程序,每个服务具有不同的流量特性,为了模拟真实的网络并进行公平的比较,本文使用现实模拟模型中给定的应用类型、特性和系统参数。表1为模拟中使用的多媒体应用程序类型和系统参数。
将本文算法与三个现有方案:RABL方案[1],AASS方案[6],DASS方案[7]的性能进行比较。
图2显示了所有方案的PUs总收益,从主用户角度看,收益是一个非常重要的因素,结果表明,应用程序请求率非常低(k<0.4)时,所有方案收入几乎相同。而当请求速率增加时,本文算法的PUs收益比其他方案更好。
图3给出了SUs服务阻塞率方面的性能比较,从次级用户的角度来看,服务阻塞概率是一个关键问题。由于适应性共享机制,本文提出的方案可避免频谱浪费,在各种流量负荷强度下,本文提出的方案可以提供比其他方案更低的服务阻塞率,这在实际网络运营中非常有用。
图4是系统吞吐量的比较,一旦应用程序服务完成,该服务的总传输速率即为系统的吞吐量。在服务连接中间没有增益累计的拒绝或终止服务,当服务请求速率增加时,拒绝服务的数量增加,则CR系统的吞吐量降低。基于自适应频谱共享策略,本文算法比其他方案更好地提高了系统的吞吐量。
图5显示了各种方案的频谱利用率,为了最大化系统性能,频谱利用率是一个重要的性能指标,所有的方案都有类似的趋势,而在各种请求速率下,本文提出的方案的频谱利用率比其他方案更好。
图6比较了各种方案中交易成功概率方面的性能。在不同系统负载情况下,本文算法比其他方案具有更好的成功概率,这确保本文算法能够提供一个有效的拍卖机制以共享频谱资源。
图7给出了各种方案平均拍卖轮数,拍卖轮数是指每轮拍卖频谱交易的平均数量,所有方案趋势类似,然而,基于贝叶斯学习过程的智能方法可以使拍卖模式更加适应当前的系统状况,因此本文算法可以比其他方案保持较低的拍卖轮数。
从图2~图7的模拟结果可以看出,在一般情况下,本文算法在多样化系统负荷强度下比其他现有算法更好。本文算法始终监视当前系统状态,且灵活度高、适应性强,能够感应到动态变化的系统环境,有显著的性能改进和更好的系统收益。因此,本文算法可以保持均衡的系统性能。
4 结语
本文提出了一种新的频谱共享算法,将其设计为一种重复贝叶斯拍卖博弈,在不具有完整信息的情况下,PUs和SUs通过贝叶斯学习过程自适应决定报价或出价。拍卖过程周期性进行,直到达成共识。由于自相关特性,价格调整决策以完全分布式方式进行,在现实世界系统操作中,该分布式控制方式是最终实现的适应方法。本文算法具有较好的适应性、可行性和有效性,能平衡系统的性能。仿真结果表明,本文算法在PU受益、交易成功率、频谱利用率、网络吞吐量等方面显著优于现有方案。