最优数字分配

最优数字分配（共7篇）

最优数字分配 篇1

1避免当前单元格内违约

当前单元格内的整数不能相同且不能相邻, 如果违反规则, 针对每个存储单元都统计一遍, 出现一次相同, 结果累加100违约分, 双向积分共200分;出现一次相邻, 结果累加5违约分, 双向积分共100分。当前单元格相等违约分200, 相当于“相邻单元格相等违约”5个, “相邻单元格相邻违约10个。当前单元格相邻违约分100, 相当于“相邻单元格相等违约”2.5个, “相邻单元格相邻违约”5个。故在此, 禁止出现当前单元格内相等、相邻。

(1) 判断当前单元格相等违约。本项目中不允许同一格内相等违约存在。判断i行j列单元格第p个元素arr0 (1-30的整数) 与当前单元格其他元素是否相等违约, 返回true不违约, false违约。在类DistributeCount中添加方法:

(2) 判断当前单元格相邻违约。本项目不允许存在同一格内相邻。判断i行j列单元格第p个元素arr0 (1-30的整数) 与当前单元格其他元素是否相邻违约, 返回true不违约, false违约。

代码与“判断当前单元格相等违约”类似, 只需将if (a[i, j, z]!=arr0) 改为if (a[i, j, z]!=arr0-1&&a[i, j, z]!=arr0+1) 。

2实现相邻违约及相邻的相邻违约最小

相邻违约是填入单元格的值与相邻单元格的值相等或相邻。包括:相邻单元格相等违约, 相邻单元格相邻违约。相邻单元格相等违约积20分, 双向积40分, 根据之前的规定违约类型为2;相邻单元格相邻违约积10分, 双向积分20, 根据之前的规定违约类型为1。相邻的相邻违约是填入单元格的值与相邻的相邻单元格的值相等, 相邻的相邻违约积1分, 双向积分2。

要实现相邻违约及相邻的相邻违约最小, 是从相邻违约分最低的1-30的几个数字中, 选出与之对应的相邻的相邻违约最低的。如有3个数4, 10, 15的相邻违约最低为0, 而4的相邻的相邻违约为6, 10的相邻的相邻违约为3, 15的相邻的相邻违约为0, 则这里选15填入。

(1) 相邻违约数组结构

如表1所示。

说明:当前单元格与相邻单元格相邻违约, 类型为1, 违约个数累计1个;当前单元格与相邻单元格相等违约, 类型为2, 违约个数累计2个。初始相邻违约数组30个元素, 值为1-30, 违约个数为30。在项目中新建文件夹entity, entity中新建类Valid。代码如下:

(2) 相邻的相邻违约数组结构

如表2所示。

初始相邻的相邻违约数组31个元素, 0下标未用, 下标对应值1-30, 违约个数为30。

在entity中新建类ValidNear类。代码如下:

(3) 初始化相邻违约数组30个存储单元, 对应1-30的值、相应的违约个数, 及违约位置:

(4) 初始化相邻的相邻违约数组。共31个单元, (0单元未用, 节省计算时间) , 对应下标即为1-30的值。对应存储相邻的相邻违约个数, 及违约位置:

(5) 实现相邻违约及相邻的相邻违约最小。

说明如图1所示。初始相邻的相邻违约数组31个元素, 0下标未用, 下标对应值1-30, 违约个数为30。相邻违约数组中违约分最小的整数有1、2、7、18, 违约分为0。1对应相邻的相邻违约分, 是在相邻的相邻违约数组中找下标为1的, 其违约个数为4。2对应相邻的相邻违约分, 是在相邻的相邻违约数组中找下标为2的, 其违约个数为5。7对应相邻的相邻违约分, 是在相邻的相邻违约数组中找下标为7的, 其违约个数为2。18对应相邻的相邻违约分, 是在相邻的相邻违约数组中找下标为18的, 其违约个数为0。这里18的相邻违约最小, 且18的相邻的相邻违约也最小, 所以选择填入整数为18。

1) 比较当前值arr0 (1-30的整数) 与 (x, y) 单元格内的数据是否相邻违约。validabsolut相邻违约数组, count违约个数, m违约下标:

2) 将违约信息插入相邻违约顺序表, 按违约个数排序:

(6) 查找相邻违约个数最小及相邻的相邻违约个数最小:

参考文献

[1]Nick Randolph.Visual Studio2010高级编程[M].清华大学出版社, 2012, 01.

[2]邱仲潘.Visual Basic2010 (中文版) 从入门到精通[M].电子工业出版社, 2011, 01.

[3]汪沁.数据结构[M].清华大学出版社, 2009, 09.

最优数字分配 篇2

水波纹填充规则是根据从中心向外扩张, 一圈一圈填充单元格, 共25圈, 每圈从8个方向进行填充, 均是由内向外填充。如图1所示。a是1、3、5、7方向填充时, 需判断的相邻单元格与相邻的相邻单元格, b是2、4、6、8方向, 需判断的相邻单元格与相邻的相邻单元格。

2实现过程

判断1个单元格内是否相邻违约valid Data Unit方法, 判断1个单元格内是否相邻的相邻违约valid Near Unit方法, 与顺序型相同。填充1个单元格内2-5个整数full Unit方法, 与S型相同。

(1) 判断是否相邻格违约, 左上1、2, 右上3、4, 左下5、6, 右下7、8。判断4个格:

摘要：水波纹填充规则是根据从中心向外扩张, 一圈一圈填充单元格。

关键词：水波纹填充,相邻违约,相邻的相邻违约

参考文献

[1]Nick Randolph.VisualStudio2010高级编程[M].清华大学出版社, 2012, 01.

[2]邱仲潘.Visual Basic 2010 (中文版) 从入门到精通[M].电子工业出版社, 2011, 01.

最优数字分配 篇3

关键词：顺序填充,S型填充,相邻违约,相邻的相邻违约

1 顺序填充规则

顺序填充规则:行从小到大顺序填充,列从左向右顺序填充单元格。即一行一行地填充每个单元格。填充规则如图1所示。

当前单元格a(i,j),须判断的相邻单元格有4个,相邻的相邻单元格有8个。

(1)判断是否相邻格违约、相等或相邻,判断4个格:

(2)判断1个单元格内是否相邻违约:

(3)判断相邻的相邻格违约,是否相同,判断8个格:

(4)判断1个单元格内是否相邻的相邻违约:

(5)填充三维int数组单元格,即填充50*50矩阵:

2 S型填充规则

S型填充规则:奇数行,从左向右填充,即按照单元格的列下标从小到大顺序填充。偶数行,从右向左填充,即按照单元格的列下标从大到小顺序填充。填充规则如同S型,如图2所示。

判断1个单元格内是否相邻违约valid Data Unit方法,判断1个单元格内是否相邻的相邻违约valid Near Unit方法,与顺序型的方法相同。

(1)判断是否相邻格违约,判断4个格。

奇数行判断第i-1行j-1到j+1列位置,第i行第j-1列相邻位置的值是否相等或相邻。偶数行判断第i-1行j-1到j+1列位置,第i行第j+1列相邻位置的值是否相等或相邻。实现代码如下:

(2)判断相邻的相邻格违约。判断8个格:

(3)填充1个单元格内2-5个整数:

参考文献

[1]Nick Randolph.VisualStudio2010高级编程[M].清华大学出版社,2012,01.

[2]邱仲潘.Visual Basic2010(中文版)从入门到精通[M].电子工业出版社,2011,01.

一种基于能效的最优功率分配策略 篇4

目前, 在改善系统吞吐量方面已有大量的研究, KANG X等人提出了一种基于感知的频谱共享接入模型[3], 有效地提高了系统的吞吐量。在此基础上, 一些学者进一步研究了提高系统吞吐量的方法[4,5,6]。但是, 考虑系统能效问题的文献十分有限, 其中多数研究是关于优化频谱感知时间[7,8], 并未涉及功率分配。本文基于感知系统模型的基础上对传统标准[4]进行改进, 在非完美感知的情况下, 提出了一种考虑能量效率的标准———有效吞吐量收益, 并基于这一标准, 通过速率和功率分配的联合优化, 最大化地有效吞吐量收益。仿真结果表明, 所提标准与参考文献[4]相比, 系统的能量效率有了显著提高。

1 系统模型

整个系统包括授权用户发射端 (PUTX) 和接收端 (PURX) 、认知用户发射端 (SUTX) 和接收端 (SURX) 。gss、gsp、gps分别是SUTX~SURX、SUTX~PURX和PUTX~SURX的信道功率增益。假设所有的信道功率增益在一确定时期内是恒定的。为了接入授权频段, SU在每一帧开始时对PU的信道状态进行周期性感知。用st表示频带在时隙t时的状态, st=0和st=1分别表示PU忙碌和空闲。θ0=Pr{st=0}和θ1=Pr{st=1}分别表示PU频带被占用的概率和PU频带空闲的概率。用来表示SU感知结果, 表示SU感知到PU处于空闲状态, 反之, 表示PU处于忙碌状态。由于感知结果与真实状态之间存在差异性, 这里用 (检测概率) , (虚警概率) 来衡量感知的精确性, 为了更清楚地表示, 定义分别表示SU感知到PU频带被占用和空闲的概率, 其中π0=θ0pde+θ1pfa。由于研究的是长期情况下系统的平均性能, 下面的内容将省去下标t。

2 有效吞吐量收益

2.1 问题描述

SU利用感知结果和感知精确性, 适时调整速率和发送功率, 最大化其有效吞吐量收益。可以将最优化问题 (Problem0) 建模为:

其中, 决策变量r0和x0表示当时SU的速率和功率分配;r1和x1表示当时SU的速率和功率分配。αij表示SU感知结果为时PU真实状态为s=i, i, j=0, 1的后验概率, 例如:, 同时用zj, 表示时PU的真实状态, 所以可以表示为:α0j=Pr{zj=0}, α1j=Pr{zj=1}。n为背景噪声;a为量纲常量;Y为PU的发送功率 (单位为W) 。定义概率函数, j=0, 1, 表示当分配功率为xj时可以保证速率为rj的概率。定义alog2xj为传输速率为rj时SU付出的代价, ηj (rj-alog2xj) 即为时的有效吞吐量收益。文中约束条件采用的是:SU平均传输功率限制和SU对PU平均干扰功率限制, 分别为式 (1) 、式 (2) 。

2.2 传输策略的选择

为了量化的有效吞吐量收益, 基于SU的感知结果分析了以下两种情况 (由于本文是在传统标准基础上进行改进, 为了与其结果分析对比, 传输策略这一部分将仿照参考文献[4]中思想进行描述) :

(1) 当时, 利用定义的z0, 当时, η0=0;当时, η0=α10;当时, η0=1。根据η0=0的取值, SU的有效吞吐量收益可分为以下两种方案。

方案1

方案1表示这时不确定感知结果, 所以就机会地发送一个较小的功率来保证它的传输速率r0, 这种情况下SU发送功率x0可以支持传输速率为r0的概率为α10。

方案2

方案2表示这时SU非常确定感知结果, 为了抵抗PU的干扰就发送一个较大的功率来保证它的传输速率r0。如果PU确实时处于空闲状态, 由于优化对象是有效吞吐量收益, 所以相比传统标准就减小了能量浪费。

(2) 当时, 利用定义的z1, 当时, η1=0;当时, η1=α11;当时, η1=1。根据η1的取值, SU有效吞吐量收益也可分为以下两种方案。

方案3

方案3表示这时SU非常确定感知结果, 所以就机会地发送一个较小的功率来保证它的传输速率, 这种情况下SU发送功率x1可以支持传输速率为r1的概率为α11。

方案4

方案4表示这时SU不确定感知结果, 为了抵抗PU的干扰就发送一个较大的功率来保证它的传输速率r1。如果PU确实时处于空闲状态, 由于优化对象是有效吞吐量收益, 所以相比传统标准同样减小了能量浪费。

根据上述方案1、2 () 和方案3、4 () , problem0可以通过比较以下4种传输策略来解决。

策略1:方案1和方案3的结合

策略2:方案1和方案4的结合

策略3:方案2和方案3的结合

策略4:方案2和方案4的结合

通过比较得出最优的有效吞吐量收益V0*=max{V1*, V2*, V3*, V4*}。以上4种传输策略充分表现了SU在不同外界环境下是怎样权衡功率消耗和所能支持速率之间关系的。很显然, 当SU感知结果完美, 即在pde=1, pfa=0的情况下V3*是最优策略, 由于感知结果存在不确定性, SU可能会选择其他传输策略。

2.3 问题解决

这一部分以策略3为例来说明问题解决。根据以上分析, 策略3可以写为:

s.t.: (1) (2) x0≥0, x1≥0

由于式 (7) 是关于x0, x1的凸函数, 通过构造拉格朗日函数来求解, 关于x0, x1的拉格朗日等式可以表示为:

拉格朗日对偶函数可以写为:

为了便于解决问题, 把原始问题分解为关于优化x0、x1的两个子问题, 如式 (11) 、式 (12) 所示:

由于上述两个问题都是关于x0、x1凸优化问题[10], 因此可以通过构造拉格朗日函数, 利用KKT条件求解出SU感知存在和不存在时的最优发送功率x0和x1。由于篇幅有限, 此处求解算法略去, 请见参考文献[5, 9]。

3 策略选择和仿真结果分析

显然, 文中SU在时最优功率分配x1*要大于时功率分配x0*, 因为CR对感知的精确度有一定的要求 (pde>0.8, pfa≤0.2) , 同时还要求PU接入授权频带的概率小于某个值 (θ0<0.4) [11], 同样的要求也出现在参考文献[3, 5]中。文中假设SU有较宽松的平均传输功率限制, 所以平均干扰功率限制就成为主要的约束条件, 所以当时, Γ2越大, SU更容易接入授权频段;当时, 由于SU为了保证其传输速率, 必须与PU的干扰抗争, PU的传输功率Y越小, SU就越容易接入授权频段。下面分析比较其策略1和策略2。

策略1可以表示为:

策略2可以表示为:

通过比较式 (13) 、式 (14) 可以看出, 如果满足pde≥0.8, 则pfa≤0.2, α11就有很大的值, 所以V1*>V2*。同样, 当时, 由于pde很大, 则SU将不用考虑PU的干扰, 所以V1*>V2*。同样的方法可以比较策略3和策略4。

仿真参数a=0.7, θ0=0.4, Y=0.5, Γ1=10, Γ2=0.2, gss=1, gsp=0.5, gps=0.5, pfa=0.1, pde=0.8。

图1为pde=0.8, pfa=0.1时4种传输策略的有效吞吐量收益比较图。从中可以看出V0*=max{V1*, V3*}, 图1清楚地表明了不同Y情况下最优策略的选择, 并且可以看出这一分界的Y值。

图2为当pde=0.8, pfa=0.01、0.1、0.3时有效吞吐量收益PU和发送功率Y的关系。可以看出, Y一定, 当感知精确度较高时, 策略3要优于策略1, 反之, 当感知精度较低时, 策略1要优于策略3。为了证明最佳策略选择与PU发送功率Y有关, 讨论以下两种情况:

(1) 完美感知的状态:因为pfa→0通过比较 (7) 、 (13) 两式可以看出V3*>V1*。因为pfa→0, 当时, SU更容易相信感知结果, 所以更倾向于选择策略3, 图2中pfa=0.01时可以证明这一点。

(2) 非完美感知状态:当pfa相对较大时, SU不确定其感知结果, 这时就存在一个Y的门限值, 当时, V3*>V1*;反之, V1*>V3*。图1和图2中当pfa=0.1、0.3时都证明了这一点。因为V3*是关于Y的递减函数, 实际上, 给定pde、pfa, 可以利用二分法来找到。

由图3可以看出所提性能标准的能效要优于传统性能标准, 并且随着pde的增大, 这一优势更加明显。从图4可以看出新提性能标准的有效吞吐量收益明显高于通过优化传统性能标准转换而来的有效吞吐量收益, 并且在pde为0.8和0.85时, 相比传统标准有效吞吐量收益分别提高4.9%和4.86%。

本文研究了认知无线电系统基于能效的最优功率分配策略, 提出了一种新的性能衡量标准, 即有效吞吐量收益。通过速率和功率分配的联合优化, 分析了4种不同传输策略下的性能, 以及SU选择不同传输策略的条件。通过最优策略的选择, 可以最大化SU的有效吞吐量收益。仿真结果表明, 基于本文所提优化方案, 可以有效提高系统能效。

参考文献

[1]MIAO G, HIMAYAT N, LI Y, et al.Cross-layer optimization forenergy-efficient wireless communications:A survey[J].Wireless Commun.Mobile Comput., 2009, 9 (4) :529-542.

[2]G U咬R G, ALAG O咬Z F.Green wireless communications via cognitive dimension:an overview[J].IEEE Netw., 2011, 25 (2) :50-56.

[3]KANG X, LIANG Y C, GARG H K, et al.Sensing-based spectrum sharing in cognitive radio networks[J].IEEE Trans.Veh.Technol., 2008, 58 (8) :4649-4654.

[4]WU Y, TSANG D H K, QIAN L, et al.Sensing based joint rate and power allocations for cognitive radio systems[J].IEEE Wireless Commun letters, 2012, 1 (2) :113-116.

[5]STOTAS S, NALLANATHAN A.Optimal sensing time and power allocation in multiband cognitive radio networks[J].IEEE Trans.Commun., 2011, 59 (1) :226-235.

[6]ALMALFOUTH S, STUBER G L.Joint spectrum-sensing design and power control in cognitive radio networks:a stochastic approach[J].IEEE Trans.Wireless Commun., 2012, 11 (12) :4372-4380.

[7]WU Y, TSANG D.Energy-effcient spectrum sensing and transmission for cognitive radio system[J].IEEE Commun.Lett., 2011, 15 (5) :545-547.

[8]SHI Z P, TEH K C, LI K H.Energy-effcient joint design of sensing and transmission durations for protection of primary users in cognitive radio system[J].IEEE Commun.Lett., 2013, 17 (3) :565-568.

[9]BLAND R G, GOLDFARB D, TODD M J.The ellipsoid method:A survey[J].Operations Research, 1981, 29 (6) :1039-1091.

[10]BOYD S, VANDENBERGHE L.Convex optimization[M].Cambridge University Press, 2004.

最优数字分配 篇5

出行时用户或者自由竞争追求费用最短的路径, 或者所有用户都由某个中央部门控制, 前者选择路径的结果是用户均衡, 即没有人能够通过单方面改变路径进一步降低自身费用,后者分配流量的结果是系统最优,即所有用户花费的费用总和最小。当静态交通需求量分配中,Roughgarden证明当路阻函数为系数非负的线性函数时,用户均衡导致的效率损失最多为系统最优的1/3, 当路阻函数是系数非负、 度数最大为d的多项式函数时, 给出纳什均衡流总费用与系统最优流总费用比值的上界是(1-d·(d+1)-(d+1)d)-1, 说明用户均衡与系统最优之间差距较大[1,2];著名计算科学家Papadimitriou等对博弈均衡的复杂性、最劣的均衡以及如何计算均衡做了深入研究[3,4,5];动态的交通流量分配研究还很少,例如,当n次连续的交通需求依次到达出发点选择路径到目的地去, 由于先到的用户并不知道随后有多少流量到达就不得不做出决策选择路径,通常采用占线和竞争策略的方法解决这样的问题,Tobias Harks等[7,8,9,10]给出了用户均衡占线策略(SUE)分配流量,研究了流量任意可分和不可分时的情

形, 给出了与多项式路阻函数最高度数有关的竞争比上界和下界; 随后他研究了带有时间窗的占线交通流量分配问题, 给出了SEQ和SEQ2策略, 并做了相应的竞争分析, 给出了竞争比的上界和下界。在占线问题中, 如果以Con(R)表示采用占线策略分配完流量序列R后所有用户花费的费用总和, 类似地, 以Copt(R)表示离线最优费用, 则占线策略的竞争比可以用系数Con(R)/Copt(R)来度量[6]。对于任意的需求序列R, 如果存在常数c使得Con(R)≤cCopt(R)+β,此处β是与R无关的一个常数,则称占线策略是c竞争的。

在静态流量分配中,用户均衡策略会导致很差的交通状况,而系统最优策略可以使得交通状况达到理想的状况,考虑到以往研究的不足和系统最优策略的优点,本文重点研究在占线交通流量分配中系统最优策略的竞争性能。本文第2节给出占线交通流量分配的数学模型及基本假设;与已有的用户均衡分配策略(SUE)不同,第3节给出流量分配后能使得当前所有用户花费费用总和最小的系统最优策略;第4节先对路阻函数是非负、非递减凸函数的情形进行竞争分析,然后进行路阻函数分别是系数非负线性函数和系数非负多项式函数下的竞争分析并给出相应的竞争比;第5节通过算例给出系统最优策略竞争比的下界。

2 问题描述及基本假设

问题描述:n次连续的交通需求依次到达出发点选择路径到目的地去,第i次交通需求量是ri,由于缺乏信息,第i次交通需求到达时用户只知道需求量r1,r2,…,ri-1,ri,而对于未来的需求量ri+1,ri+2,…,rn无法预知,但此时必须做出决策把ri单位的交通需求分配到网络上去,那么如何分配流量能使得所有用户花费的费用总和尽可能小呢?

给定一个有向交通网络G(V,E), V表示网络的节点集合,E表示路段e的集合;le(x)表示流量为x时通过路段e的费用,它是该路段上流量x非负的、非递减的凸函数;当流量序列r1,r2,…,ri,…,rn依次通过该网络时,第i次分配使用节点κi={i1,i2,…,ini},其中ri={ri1,ri2,…,rini};Pij表示起点sij到迄点tij之间所有路径的集合,fijp≥0是路径p∈Pij上的流量;可行流x就是对于所有的点v∈V, 能使${\displaystyle \sum _{e\in \delta {}^{+}(v)}x}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}x}{}_e^{ij}=\gamma {}_{ij}(v)$成立的流,其中δ+(v),δ-(v)分别表示从节点v流出、流入流量的路段集合, 如果v=sij, 则γij(v)=rij, 若v=tij, 则γij(v)=-rij; 第i次分配通过第j个节点分配到路段e∈E上的流量为$f{}_e^{ij}={\displaystyle \sum _{e\in p}f}{}_p^{ij}$,第i次分配在路段e上累计的流量为$f{}_e^i={\displaystyle \sum _{ij\in \kappa {}_i}f}{}_e^{ij}$; n次分配在路段e上总共分配的流量为$f{}_e={\displaystyle \sum _{i=1}^{n}f}{}_e^i$,用户在网络上花费的总费用为:$C(f)={\displaystyle \sum _{e\in E}l}{}_e(f{}_e)f{}_e={\displaystyle \sum _{e\in E}l}{}_e\left({\displaystyle \sum _{i=1}^{n}f}{}_e^i\right)\left({\displaystyle \sum _{i=1}^{n}f}{}_e^i\right)$。

因为用户在出行时总是追求费用最小的路径,而不考虑其它用户如何选路,从而会导致很坏的交通状况,而系统最优可以使得交通状况达到最优,但是用户必须接受控制才能实现系统最优;用户要改变已经选择好的出行路径,要付出额外费用,如果这个费用很大的,则用户最好的策略还是坚持原来的路径不变。

根据上面的分析以及为了研究方便,本文给出如下假设:

①任何时刻,任何一个点对之间的用户都听从某个中央部门的安排;

②用户一旦被分配到网络上,它的出行路径就不能再改变;

③网络上所有路段的通行能力都没有限制;

④交通流量是无限任意可分的,也就是每个用户携带的流量是无限小的。

3 系统最优策略

实施交通管理,最终的目标就是想使得交通状况达到最好,如果流量分配是静态的过程,只要采用系统最优的分配方式就可以使得交通状况达到最好;如果交通状况是一个动态的过程,需求一个接一个到来,系统最优分配方式分配流量的效果如何呢,这是交通部门关注的一个问题,下面重点研究系统最优策略在动态流量分配过程中的效果。

系统最优策略:对实时到达的交通需求量每一次都按系统最优方式分配,即每次流量分配结束后,网络上所有用户所花费费用总和最小,且流量一旦分配到网络上其出行路径就不能再改变。

根据前面的模型可知,利用系统最优策略分配流量时,求解下面的最优化问题(P1)就可以得到第k次分配到路段上的流量,

$\begin{array}{l}\min C{}^k(f{}^k)\\ \text{s}.\text{t}.{\displaystyle \sum _{e\in \delta {}^{+}(v)}f}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}f}{}_e^{ij}=\gamma {}_{ij}(v),\forall v\in V\\ f{}_e^k\ge 0,\forall e\in E\end{array}(\text{Ρ}1)$

其中,$C{}^k(f{}^k)={\displaystyle \sum _{e\in E}l}{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)$。由于路阻函数是凸函数,第一个约束条件是流量的线性函数,因此,该规划是一个凸规划,可以在多项式时间内求解。

根据Roughgarden[1]可知,求解下面的规划(P2)也可以得到系统最优流:

$\begin{array}{l}\min {\displaystyle \sum _{e\in E}{\displaystyle {\int }_0^{f{}_e^i}(l{}_e\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right)}}\\ +\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right)l^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i-1}f}{}_e^k+z\right))dz\\ \text{s}.\text{t}.{\displaystyle \sum _{e\in \delta {}^{+}(v)}f}{}_e^{ij}-{\displaystyle \sum _{e\in \delta {}^{-}(v)}f}{}_e^{ij}=\gamma {}_{ij}(v),\forall v\in V\\ f{}_e^k\ge 0,\forall e\in E\end{array}(\text{Ρ}2)$

由规划(P2)可知,当交通状况处于系统最优状态时,在边际费用的意义上来说,交通状况处于纳什均衡状态。

4 系统最优策略的竞争分析

衡量一个占线策略好坏的重要指标就是该策略的竞争比,竞争比越小策略就越好。下面重点研究系统最优策略的竞争性能。由于路段上的通行费用随着流量的增加而增加,因此,一般假设路段上的路阻函数是流量非负、非递减的函数。本节先研究一般情形,即路阻函数是非负、非递减凸函数时系统最优策略的竞争比, 然后研究路阻函数分别是系数非负的线性函数和系数非负多项式函数时该策略的竞争比。

为了便于进行竞争分析,特给出以下符号和定义:

定义1 对每一个路段e∈E及其上的路阻函数le,令

$\begin{array}{l}\begin{array}{l}\upsilon {}_e^n(l{}_e,f{}_e)\\ =l{}_e(f{}_e)f{}_e-{\displaystyle \sum _{i=1}^{n}l}{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i\\ -{\displaystyle \sum _{i=1}^n\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}{l}^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i\end{array}\\ \begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)(l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e)}{l{}_e(f{}_e)f{}_e}\end{array}\end{array}$

其中, xe,fe是非负向量,fie是路段e上第i次分配的流量,n是交通需求次数,实数λ>0, d是自然数。令ω(L;$n,\lambda )=\underset{l{}_e\in L}{{\displaystyle \sup }}\omega (l{}_e$;n,λ),其中L是非负、非递减的凸函数组成的集合。

定义2 参数λ的可行集是Γ(L,n)={λ>0|1-(d+1)ω(L;n,λ)>0}。

4.1 非负、非递减凸路阻函数时的竞争比

先研究路阻函数是非负、非递减凸路阻函数时系统最优策略的竞争比。下面的变分不等式是进行竞争分析的基础。

引理1(变分不等式) 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数le是非负、非递减凸函数,采用系统最优策略分配流量时,下面的变分不等式成立:

${\displaystyle \sum _{e\in E}\left(l{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)+\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)l^{\prime }{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)\right)}(f{}_e^k-x{}_e^k)\le 0$

其中, fke是规划问题(P1)的解,xke该规划的任意一个可行解。

定理1 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果网络上的路阻函数le是非负、非递减的凸函数,且对于任意实数x≥0,d≥1, xl′(x)≤dl(x)成立,则系统最优策略的竞争比是:

$\underset{\lambda \in \Gamma (L,n)}{{\displaystyle \inf }}\left(\frac{(d+1)\lambda }{1-\omega (L;n,\lambda )}\right)$

其中, L是非负、非递减的凸函数组成的集合。

证明 令f是按系统最优策略分配时产生的交通流,x是任意一个可行流,则

$\begin{array}{l}C(f)\\ \le {\displaystyle \sum _{e}l}{}_e(f{}_e)f{}_e+{\displaystyle \sum _{i=1}^n{\displaystyle \sum _e(l{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}}\\ +\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)l^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right))(x{}_e^i-f{}_e^i)\\ \le {\displaystyle \sum _{e\in E}(}\upsilon {}_e^n(l{}_e,f{}_e)+(d+1)l{}_e(f{}_e)x{}_e)\\ \le \lambda (d+1)C(x)\\ +{\displaystyle \sum _{e\in E}(}(d+1)(l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e))\\ \le \lambda (d+1)C(x)+\omega (L;n,\lambda )C(f)\end{array}$

第一个不等式是由于引理1,最后一个不等式是由于ω(L;n,λ)的定义及λ属于可行集Γ(L,n)。取x是最优离线解就可以得到定理中的结论。证毕。

该定理给出了计算系统最优策略竞争比的一般方法,如果路阻函数是一般的非负、非递减函数,竞争比是多少无法得知,下面给出系数非负多项式函数的竞争比。

4.2 系数非负线性路阻函数时的竞争比

系数非负的多项式路阻函数是最简单也是最基本的一种,研究这类路阻函数的竞争比具有很重要的意义,因为咱实际中经常会把一般的路阻函数近似为线性或多项式类的函数来研究,具有很强的可操作性,下面研究路阻函数l是系数非负线性函数时的竞争比,先看下面引理。

引理2 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路阻函数是系数非负的线性函数l(x)=ax+b,式子ω(L;n,1)的值至多是(n-2)/2n.

证明 由不等式$(f-x)x\le \frac{1}{4}f{}^2$及柯西-施瓦兹不等式$\left({\displaystyle \sum _{i=1}^{n}a}{}_{i}b{}_i\right){}^2\le {\displaystyle \sum _{i=1}^{n}a}{}_i^2{\displaystyle \sum _{i=1}^{n}b}{}_i^2$可得

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ \le \underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{2\cdot \frac{1}{4}a{}_{e}f{}_e^2-\frac{1}{n}a{}_{e}f{}_e^2}{a{}_{e}f{}_e^2}\\ \le \frac{n-2}{2n}\end{array}$

其中,$\upsilon {}_e^n(l{}_e,f{}_e)=l{}_e(f{}_e)f{}_e-{\displaystyle \sum _{i=1}^{n}l}{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i-{\displaystyle \sum _{i=1}^n\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)}{l}^{\prime }{}_e\left({\displaystyle \sum _{k=1}^{i}f}{}_e^k\right)f{}_e^i=-\frac{1}{n}a{}_{e}f{}_e^2$.证毕。

定理2 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数是线性函数l(x)=ax+b, a,b≥0, 则系统最优策略的竞争比是4。

4.3 系数非负多项式路阻函数时的竞争比

本节考虑路阻函数是系数非负且度数最大是d的多项式时的竞争比,即路阻函数l∈Ld={adxd+…+a1x+a0,as≥0,s=0,1,…,d}。

引理3 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去, 如果路阻函数l∈Md, 则ω(Md;$n,\lambda )=(d+1)\underset{\mu >0}{{\displaystyle \sup }}\mu -\lambda \mu {}^{d+1}$.其中Md是单项式asxs,0≤s≤d组成的集合,参数λ≥1, s,d是正整数且s∈[d]。

证明 令f是由系统最优策略产生的交通流, x是任意一个可行流。 因为${\displaystyle \sum _{e}l}{}_e(f{}_e)f{}_e\le (d+1){\displaystyle \sum _{k=1}^{n}l}{}_e\left({\displaystyle \sum _{i=1}^{k}f}{}_e^i\right)f{}^k$,结合υne(le,fe)的定义,可知υne(le,fe)≤0。因此

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e))x{}_e+\upsilon {}_e^n(l{}_e,f{}_e]}{l{}_e(f{}_e)f{}_e}\\ \le \underset{x{}_e,f{}_e>0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(x{}_e)]x{}_e}{l{}_e(f{}_e)f{}_e}\end{array}$

令μ=xe/fe,可得

$\omega (l{}_e;n,\lambda )=\underset{\mu >0}{{\displaystyle \sup }}\frac{(d+1)[l{}_e(f{}_e)-\lambda l{}_e(\mu f{}_e)]\mu f{}_e}{l{}_e(f{}_e)f{}_e}$

现在考虑路阻函数是单项式函数le(x)=asxs,s∈[d]的情形,

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =\underset{\mu \ge 0}{{\displaystyle \sup }}\frac{(d+1)(a{}_{s}f{}_e^s-a{}_s\lambda \mu {}^{s}f{}_e^s)\mu f{}_e}{a{}_{s}f{}_e^{s+1}}\\ =(d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{s+1}\end{array}$

因为λ≥1,上式的最大值可以在μ≤1处得到。因为s∈[d],所以

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =(d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{s+1}\\ \le (d+1)\underset{\mu \ge 0}{{\displaystyle \max }}\mu -\lambda \mu {}^{d+1}\end{array}$

引理4 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路段上的路阻函数l∈Ld,则ω(le;n,λ)的值至多是d/(d+1),其中λ=(d+1)d-1.

证明 当λ=(d+1)d-1时, ω(le;n,λ)的最大值在μ=1/(d+1)处取得,代入得

$\begin{array}{l}\omega (l{}_e;n,\lambda )\\ =(d+1)\left[\frac{1}{d+1}-(d+1){}^{d-1}(d+1){}^{-d-1}\right]\\ =\frac{d}{d+1}\end{array}$

定理3 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果路阻函数l是系数非负、度数最大是d的多项式函数时,则系统最优策略的竞争比是(d+1)d+1.

5 系统最优策略竞争比的下界

上一节研究了系统最优策略的竞争比,本节研究该策略竞争比的下界。通过下面的算例,在所给定的需求序列下,利用系统最优策略分配流量时所有用户花费的费用与最优费用的比值不小于5/3。

定理4 假设有n次连续的交通需求占线到达路网出发点选择路径到目的地去,如果网络上的路阻函数是系数非负的线性函数,则系统最优策略的竞争比不小于5/3。

证明 考虑下图中给出的网络,网络上的路阻函数分别是l(si,s)(x)=0, l(ti,t)(x)=0, l(si,t1)(x)=i, l(s,t)(x)=x.

需求σ={1,2,…,k,k+1}依次到达,在第i次需求中都有1单位的流量从si到ti(i=1,…,k),在第k+1次需求中有d单位的流量从s到t. 在每一次分流过程中,系统最优策略分给siti路径上的流量是$\frac{1}{2}$,另一半流分配到s,t路径上去,因此,系统最优策略产生的费用是$C{}_{SS{\rm O}}(\sigma )=\frac{1}{2}k(k+1)+\left(\frac{k}{2}+d\right){}^2$;最优的离线解在前k次分流中所产生的费用是${\displaystyle \sum _{i=1}^{k}i}=\frac{1}{2}k(k+1)$,第k+1次产生的费用是d2,因此,离线问题的最优费用是$C{}_{opt}(\sigma )=\frac{1}{2}k(k+1)+d{}^2$,令$k=n-1,d=\frac{n}{2}$可得$\frac{C{}_{SS{\rm O}}(\sigma )}{C{}_{opt}(\sigma )}=\frac{\frac{1}{2}k(k+1)+\left(\frac{k}{2}+d\right){}^2}{\frac{1}{2}k(k+1)+d{}^2}=\frac{5n{}^2-5n+1}{3n{}^2-2n}\le \frac{5}{3}$。

显然,当n=1时,定理2中给出的上界是一个紧界。通过对比可以发现系统最优策略分配流量之后,能够使得网络上流量所花费的费用是最优费用的5/3倍,而已有的用户均衡策略分配流量所产生的费用大于等于系统最优费用的3倍,从这个意义上来说,系统最优策略优于用户均衡策略。

6 结束语

当交通需求动态达到时,本文采用系统最优策略去分配交通需求量。对典型的变分不等式进行合理处理的基础上,得到了计算系统最优策略竞争比的计算方法,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+1)d+1-竞争的,并给出系统最优策略竞争比的下界是5/3;本文研究还有好多不足之处,比如目前还没有证明该策略是最优策略;国内外占线交通流量分配问题研究的还非常少,还有很多值得研究的方向,比如流量不可分的情形; Stacheklberg博弈中的占线交通流量分配问题等。

参考文献

[1]Roughgarden T,Tardos E.How bad is selfishrouting?[J].Journal of the ACM,2002,49(2):236~259.

[2]Roughgarden T.The price of anarchy isindependent of the network topology[J].Journalof Computer and System Science,2003,67:341~364.

[3]Koutsoupias E,Papadimitriou C H.Worst caseequilibria[A].Lecture Notes in Computer Science1563[C].Berlin:Springer,1999:404~413.

[4]Deng X,Papadimitriou C H,Safra S.On the complexity of equilibrium[J].Journal of Computer andSystem Sciences,2003,67(2):311~324.

[5]Papadimitriou C H,Roughgarden T.Computingequilibria in multi-player games[A].Proceedingsof SODA[C].Berlin:Springer,2005:82~91.

[6]Manasse M S,McGeoch L A,Sleator D D.Competitive algorithms for on2line problems[A].Proceedings 20th Annual ACM Symposium onTheory of Computing[C].1988:322~33.

[7]Harks T,et al.Nonadaptive selfish routing withonline demands[Z].CAAN 2007,LNCS 4852:27~45.

[8]Harks,Stefan.Online multicommodity routingwith time windows[Z].Berlin:Konrad-Zuse-Zentrum für Informationstechnik,2007-12-28.

[9]Harks T,Heinz S,Pfetsch M E.Competitiveonline multicommodity routing[Z].ZIB Report 07-16,Zuse Institute Berlin,2007.

最优数字分配 篇6

关键词：城市水务基础设施,资金分配,综合效益,多属性群体决策

1 引言

水资源的短缺、水质的恶化、资金的限制影响了城市水资源供应服务的质量。全面适应城市水务基础设施的不断发展和改革非常重要[1],公共基础设施需要最小化成本,最大化收益以确保水务基础设施的可支付性,以及用水的安全性[2]。因此,提高水务基础设施经济效益水平,做好资金分配是一个亟待深入研究的课题。

以非金融形式存在的公共领域资金分配一直是国内外学者研究的一个重点。例如,Hajkowicz[3]描述了一种决策支持模型,给昆士兰(位于澳大利亚)的14个区域分配环境资金,实践证明Hajkowicz的多标准决策模型可有效改善公共部门资金分配的透明度、可审核性、以及公众的接受度。Yu等[4]提出了一种新的优化模型,对主权财富基金的战略资产进行合理配置,他们将主权财富基金分为战略资产分配基金和策略资产分配基金,并根据战略资产的风险值,将其分为高风险资产、中风险资产、低风险资产、无风险资产4种类型的资产。Yu等学者提出的最优模型以最大相对风险权重系数和最小风险值为目标来决定这四种风险资产的相关权重,并利用NSGA-Ⅱ算法进行了数值仿真,得到了帕累托最优解。Fang等[5]提出了一种新颖的集中资源分配模型,解释了集中资源分配模型的重要性。Fan等[6]利用改进的粒子群算法解决了多目标的资源分配模型。Zayed等[7]认为供、排水管网维修的资金分配问题是极为重要的,提出了基于网络的决策支持工具,科学有效地将水务基础设施的资金分配出来用于管网的维修。国内资金分配方面的研究比较少,从仅有的文献来看,邵东国等[8]以地区的不满意度最小为决策目标,通过构造一个多目标群决策模型解决了防洪工程建设投资资金的分配问题。王威等[9]以经济效益最大化为目标,利用非线性动态规划数学模型解决了震后恢复资金的优化分配问题,并借助MATLAB为平台对其进行了求解。魏权龄等[10]以DEA的原理和模型为基础,提出了一套科学有效的资金分配方案。

综合现有的研究成果,水务基础设施资金分配方面的研究较为缺乏,本文拟建立基于多属性群体决策的城市水务基础设施资金分配模型,将城市水务基础设施资金作为一种资产,通过建立的模型,以综合效益最大为目标来决定水务基础设施的相关权重,并利用lingo对模型进行了求解,以满足我国对水务基础设施资金分配问题的需要。

2 问题描述及模型构建

2.1 问题的描述

假定城市水务基础设施由p个子系统构成,本文将所要研究的水务基础设施资金分配问题具体界定为:部门将资金分n批拨付给水务基础设施的p个子系统。考虑到水务基础设施子系统的相对重要性及对资金所带来的经济效益不同,需对其进行综合评估。根据评估结果对资金进行合理分配,以水务基础设施的综合效益最优为目标,满足子系统的资金需求[11]。

2.2 模型的建立

以获得的综合效益最优为目标,建立模型如下:

其中,t=1,2,…,n;j=1,…,p.θtj表示将第t批资金分配给第j个水务基础设施子系统的资金额比率;μtj表示将第t批资金分配给第j个水务基础设施子系统获得的效益;wt表示第t批资金占总资金的比率;rj表示专家群体对第j个水务基础设施子系统的综合效益的总评估值。

3 基于群体多属性决策方法的资金分配评估

3.1 建立多属性专家群体偏好矩阵

假定有m个专家对p个水务基础设施子系统的l个评判属性进行评估,评估值为ekij(其中i=1,2,…,l;j=1,…,p;k=1,2,…,m)。令Ejk= (ek1j,ek2j,…,eklj)为第k个专家对第j个水务基础设施子系统的评估偏好向量。

设第j个水务基础设施子系统存在两个偏好向量Eji′和Ejj′(k=1,2,…,i′,…,j′,…m)的相聚程度。定义相聚度[12]

其中,‖·‖p表示矢量的p范数,‖·‖q表示矢量的q范数。

对专家的评估进行聚类,并引入阈值γ用来决定专家的聚集情况:

若满足条件(6),则专家群体的偏好向量属于这一聚集。否则,不属于同一聚类。文献[12]、文献[13]认为当γ=0.9时,计算效果最优。

设专家群体共有A个聚集,ξja为第j个水务基础设施子系统第a个聚集的成员数(其中1≤a≤m)。令Cja表示第a个聚集,并设定聚集的偏好向量,为对Gja进行标准化后的偏好向量。

设第j个水务基础设施子系统的群体偏好为,对其进行标准化后得到群体偏好矩阵.

3.2 权重的确定

根据Shannon提出的信息论[14],令第i个评判属性在p个水务基础设施子系统中的均值为。

本文将熵定义为[15]:

根据熵的定义,定义熵权:

令群体偏好的评价属性权向量。最终得到p个水务基础设施子系统的综合评估向量:

其中,R = (r1…rj…rp)。

4 算例

下面通过算例来证明方法的有效性和可行性。城市水资源系统是由城市的供水、用水、污水处理和排水这四个子系统组成。因此,本文将水务基础设施分为供水基础设施子系统、用水基础设施子系统、污水处理基础设施子系统、排水基础设施子系统,并对这4个基础设施子系统进行资金分配研究。

某部门将资金分3批拨付给供水、用水、污水处理和排水4个水务基础设施子系统。首先对水务基础设施子系统进行资金的经济效益评估,由40个专家分别给4个水务基础设施子系统(供水、用水、污水处理、排水)的5个评判属性(内部收益率、期望净现值、对就业的影响、促进区域经济贡献率、水资源安全效益[16])进行评价,对于给定的指标,采用10点标度法。

为了消除不同属性之间量纲不一致的影响,对评价数据进行标准化处理并得到群体成员判断值矢量。

在MATLAB R2011b平台下,计算后可以得到群体成员的偏好情况,整理后如表1所示。

得到了供水子系统、用水子系统、污水处理子系统、排水子系统的综合评估权重,分别为0.4463,0.4469,0.4462,0.4466。

在群体多属性决策问题中,决策者通常需要考虑决策结果的稳定性,因此,通常要对多属性问题进行灵敏度分析[17]。设属性i有微小的扰动Δi,在其他属性权重保持不变的情况下,利用文献[18]中提到的方法,计算出了使得任意两个属性之间优先排序不变的稳定区间,如表2所示。

注:pst,i表示在属性i下,当权重在该区间变化时,s子系统和t子系统的综合评估权重的排序情况不会发生改变。

综合表2,得到了各个属性权重的最大变化区间,当属性1的扰动值在(-0.0153,0.0032)变化时,不会影响最终子系统的综合评价值大小的排序情况,同理可以得到属性2、属性3、属性4、属性5的最大变化区间(见表3)。

将所得到的4 个子系统的综合评估权重带入方程(4),利用lingo软件求解,得到结果如表4所示。

目标函数的最优值为0.1490,从表4 可以看出用水子系统相比其他系统而言的资金分配更加紧急和重要,在进行资金分配时,应将用水子系统的资金分配放在首位,同时可以看到没有必要将资金分为多批次进行分配。

5 结论

最优数字分配 篇7

在21世纪无线通信网络繁荣，快速的发展背景下，人们对有限的信道频谱资源需求越加强烈。在传统的静态频谱分配的政策下，频谱资源没有得到充分利用。为了解决频谱资源紧张，能够充分利用频谱资源的问题，出现了认知无线电（CR）概念。CRN(Cognitive Radio Network,CRN）是一种可以感知侦测、分析处理和智能决策，且可在工作环境中智能学习的网络。

在CRN中，从CR用户的角度看，授权信道是动态可访问的。但是基于授权用户与CR用户之间的公平传输机制设计是一个富有挑战性的问题。到目前为止，研究者提出了很多MAC协议，主要有基于传统的二元假设模型和基于二元假设模型的改进模型——三元假设模型[1][2]。但是三元假设模型的提出，也对CR用户争夺空闲授权信道提出了新的难题——需要设计一套有效机制防止CR用户无序竞争该信道。

目前，很多研究关于CR用户的数据传输都是基于CR用户的可信条件下提出的，当CR用户出现自私行为，将会导致CR用户之间的协调或管理中枢的调节出现错误或失灵。所以需要为CR用户接入信道设计一套机制来避免CR用户出现自私行为。因此本文提出了一种基于不完全信息动态博弈模型的频谱最优分配方案，该方案可以有效解决上述不足。

1 相关工作

近几年，认知无线电技术的优越性越来越受到研究者的青睐。利用该技术进行无线频谱资源再分配的研究更是受到广泛关注，并取得了一定的成果。

在大量相关研究中，主要论及了主用户与CR用户的传输矛盾或优化CR用户的数据传输。但是具体针对CR用户的传输的可信机制未作出系统阐述。

博弈论（Game theory）在建模和分析问题上是一个相当重要的数学工具。文献[3][4]论述了Game theory在CRN中的运用，旨在为未来设计一个高效、自我强化和分布式频谱共享的无线网络。文献[5]利用Game theory提出了动态频谱租赁策略，用来研究分层动态频谱接入，该策略获得了较好的频谱利用率。

本文将针对CR用户的自私行为通过不完全信息动态博弈模型来创建一套机制有效地降低CR用户的自私行为。

2 系统模型与假设

2.1 不完全信息动态博弈模型

本文主要考虑分布式的认知无线电网络模型。模型中存在一个主用户和M个CR用户。在CR网络中，主用户与CR用户共享授权频谱资源，同时主用户对授权频谱有绝对的使用权和控制权，CR用户通过侦测到的频谱空穴，机会地接入空闲授权频谱。文献[6]提出了基于预测机制的透明接入CR用户，通过接收到CR用户的一个时长发送时间，对比每个可用信道的接入机会来判断和确定最佳接入机会。本文认为当信道空闲时，对每个CR用户而言都是最佳的接入机会，也就是说每个CR用户都确定知道授权信道的可利用时间。本文的CR用户将采用时分复用的方式进行数据传输，具体来说，CR用户每次申请接入授权信道时，CR用户的传输信息（有效信息）被打包成一定的数据包大小，本文中将采用“数据帧”这个名称来表示数据包大小。

由于本文模型采用分布式的工作方式，各个CR用户彼此相互合作，持续地对授权频谱状态进行感知，从整体上，我们认为每个CR用户侦测信道的频率相等。当一个或多个CR用户侦测到频谱空穴时，这些CR用户通过控制信道将信道的状态告诉所有CR用户。CR用户将自己本次要传输的数据的大小ζ（亦称：控制信息或传递信息）传递给主用户，主用户接收所有CR用户的控制信息，并确认用户数ν(ν≤M)，我们称用户数为一个传输周期。主用户允许CR用户接入授权信道，并传输信息。每当一个用户传输完成，用户数ν=ν-1，当传输周期归零，主用户将再次允许CR用户发送控制信息，依次循环。我们使用τi表示第i个CR用户的数据包的大小，并认为这个是共同认知的。信道空穴每次可利用时间为T，本文认为CR用户每次传输的数据包较小，且τi≤T,CR用户传输信息不需要变更信道。

如图CR数据包的发送是一个或数据CR用户发送的数据包，且每个CR用户的数据包的传输有时间间隔。我们认为这个时间具有相当小的间隔。信号在每次信道状态周期DT变化时开始可以传输。

主用户在得到CR用户的控制信息后，将比对信道的可利用时间。依次允许CR用户接入信道并传输信息。通常主用户希望每次的信道空穴可以得到最大的利用。既要保证空闲信道的利用率η：

同时CR用户侦测空穴信道，并申请接入空穴信道来传输自己的数据包。CR在一次传输完成时，需要的功耗为：

CR用户的功耗分别在感知信道状态、传递控制信息和数据包的生成和发送等阶段产生。

2.2 自私行为模型

在CR系统网络中，CR传递控制信息时，CR用户会出现自私行为，就会虚报自己的控制信息，导致主用户为该用户分配与其实际不符的占用信道时间，我们称这类用户为自私用户。自私用户不仅影响主用户对CR用户接入的分配，还会导致相同的CR用户的功耗的增加，导致在一个周期内的整体CR用户的功耗的增加。

我们假设模型中的CR用户出现自私行为的概率为λself，则CR用户不会出现自私行为的概率为1-λself，这是共同认知的信息，并且是属于先验概率。当主用户收到CR用户传递的控制信息ζ，使用贝叶斯法则从先验概率的到CR用户的后验概率

同时，主用户设置一种机制保证降低CR用户的自私行为的发生。主用户为每个CR用户设置一个信誉等级Rep。当CR用户的控制信息与实际发送数据包的大小不吻合后，主用户降低该CR用户的信誉等级，即Rep=Rep-1。当自私用户下一次再次申请接入信道时，主用户忽略自私用户的申请请求，也就是停止自私用户用户的申请，等到传输周期结束后，主用户再次允许自私用户用户的接入请求。当信誉等级Rep下降到一定的程度时，主用户认为该用户是完全不可信的，在以后的交互中，将始终拒绝该用户接入信道。

3 博弈均衡与模型分析

该模型中，CR用户的行为导致了CR用户与主用户的博弈。这种博弈属于不完全信息动态博弈。对于主用户而言，CR用户的传输信息只能通过控制信息而计算出后验概率判断。但是主用户根本不可能正确地判断CR用户是否自私。所以需要设计机制来降低或完全禁止CR用户的自私行为。CR用户受到机制的制约，会约束自己的行为，降低自己最终效用的损失。

3.1 分离均衡下的博弈分析

本文将采用分离均衡的思想来分析与处理该模型。分离均衡属于不完全信息动态博弈。主要目的是通过信息的主动方的发布信息，将有利于自己的信息从所有同类信息中分离出来，从而获得收益。同时在信息不对称的环境下，不具备完全信息的一方需要建立有效机制确保筛选出对自己有利的信息从而保证整体效益。本文中CR用户属于信息的发布者，主用户属于信息的分离者。发布者向分离者发布信息，分离者为了确保自己的利益，将有利于自己的信息完全区分并分离出来。

在本文的模型中，我们认为一个CR用户的数据包的大小有两类：τl与τs，分别代表长数据包和短数据包。分离者主用户对CR用户的行为的对策有两种方式：允许（P）与禁止（S）。我们假定博弈参与者是完全理性的，并给出博弈参与者的行动过程。如图2所示。

从图2的行动顺序可以看出。一次博弈共分为3个阶段过程：第一个阶段由“自然”预测CR用户的行为方式，自私或者非自私的出现的概率，因为这是共同认知的；在第二个阶段由CR用户决定选择具体的行为方式，也就是CR用户传递控制信息；第三个阶段由主用户对CR用户的控制信息作出判断，决定是否允许CR用户立即接入信道。

3.2 各策略下的效用收益

在了解了博弈参与者的行动过程后，就需要分析博弈参与者在不同策略下的效用收益。

CR用户的选择不同的控制信息τcontrol时，τcontrol∈{τl,τs}，主用户应对的行为的支出时间为。我们。用Qij,i∈{l,s},j∈{P,S}（i是CR用户选择的控制信息，j是主用户的行为）表示主用户的支出的时间。

当CR用户的控制信息为长数据包的信息，主用户在不同选择下的支出时间函数为：

当CR用户的控制信息为短数据包的信息，主用户在不同选择下的支出时间函数为：

同时，可以知道CR行为对自身功耗的影响。当CR用户的数据包是较大时，CR用户不会传递短数据包的信息给主用户。所以此时CR用户完成传输的功耗为：

当CR用户的数据包较短时，CR用户就有两种选择：传递长数据包的信息和短数据包的信息。若CR用户的控制信息为短数据包，其完成传输的功耗为：

若CR用户此时表现了自私时，自私用户完成传输数据的功耗为：

从式（6）和式（7）可知，CR用户本质是短数据包的用户。由于行为方式的不同而导致其功耗也不相同。同时可知Ps<Psself。

我们进一步分析主用户的空闲信道的利用率。通过式（3）中主用户的行为结果得出授权信道的利用率：

通过式（4）中主用户的行为方式，可以得出授权信道的利用率：

因为主用户无法预知CR用户是否自私，所以只能根据控制信息中的有效信息判断自己的信道利用率。无论如何，主用户对CR用户的接入请求是允许而不是拒绝，因为从式（8）和式（9）可知，主用户拒绝CR用户的请求，授权信道的利用率很小。所以主用户绝不拒绝CR用户的接入请求。

当得知主用户无论都会接收接入请求。从式（3）和式（4）可知φ(τtζl)=1或φ(τtζl)=0时，此时φ(τsζl)=0或φ(τsζl)=1，分别表示CR用户的控制信息为长数据包或短数据包的信息。因为CR用户的是理性的，需要传输长数据包的用户绝不会传递短数据包的控制信息，式（3）可进一步修正为：

当主用户在得知CR用户在此次传输过程中，传递了错误的控制信息，主用户对自私用户的信誉等级Rep=Rep-1，并暂停忽略该用户下一周期的接入申请。与此同时，自私用户的功耗将增加，因为自私用户的传输信息需要等到忽略周期完成后的一个周期内传输完毕。

在主用户确认自私用户以后的行为为非自私行为，将对信誉等级初始化。若是自私用户在下一传输周期中出现自私行为，那么信誉等级将继续下降。当信誉等级下降到一定的等级，主用户就认为该用户就是自私用户，不可信的。最终禁止该用户的接入申请。

从上面的结果可以看出：在一个传输周期内，CR用户的行为不会对自己产生不利的影响。但是本模型中，同一个CR用户与主用户的博弈不是一次完成的，由于主用户设置的信誉机制与CR用户完成传输信息的功耗相一致，导致了CR用户不敢也不希望出现自私行为影响自己以后的传输功耗。CR用户从长远的利益出发，就会减少自私行为发生，尽可能地保持自身的功耗不至于因为自私行为升高。最后，博弈双方的行为就会趋于一个平衡，即CR放弃自私行为，主用户永远不会降低CR用户的信誉等级。

4 总结

在这篇论文中，我们分析了CRN网络中的资源分配的问题。并且提出了一个基于非合作博弈的资源分配方案。在这个博弈方案中，CR用户和主用户彼此作为博弈竞争者，它们为了自身的利益而有动机地博弈。本文中，主用户通过该分配方案，将使自私CR用户的数据传输产生影响，如若主用户未能很好的利用该方案，授权频谱资源的利用率将相对低效。

参考文献

[1] Zhao Y,Song M,Xin C S.Fmac:A fair mac protocol for coexisting cognitive radio networks[C]//INFOCOM,2013Proceedings IEEE.IEEE,2013:1474-1482

[2] Zhao Y,Song M,Xin C,et al.Spectrum sensing based on three-state model to accomplish all-level fairness for coexisting multiple cognitive radio networks[C]//INFOCOM,2012 Proceedings IEEE.IEEE,2012:1782-1790

[3] Wang B,Wu Y,Liu K J.Game theory for cognitive radio networks:An overview[J].Computer Networks,2010,54(14):2537-2561

[4] Akyildiz I F,Lo B F,Balakrishnan R.Cooperative spectrum sensing in cognitive radio networks:A survey[J].Physical Communication,2011,4(1):40-62

[5] Jayaweera S K,Li T.Dynamic spectrum leasing in cognitive radio networks via primary-secondary user power control games[J].Wireless Communications,IEEE Transactions on,2009,8(6):3300-3310