CN102404747A - 高效与公平的动态频谱分配方法 - Google Patents

Abstract

本发明公开了一种高效与公平的动态频谱分配方法，适用于交互式认知无线网络，其包括以下步骤：基于合作微分博弈理论，将交互式认知无线网络划分为不同的联盟，建立交互式认知无线网络“联盟-竞争”型体系结构；设定交互式认知无线网络具有多个认知用户以及每个认知用户的目标函数或支付函数；求解前述目标函数或支付函数。本发明可以有效缓解频谱资源的稀缺，提高频谱的利用率，同时，兼顾频谱使用的公平性和效率。

Description

高效与公平的动态频谱分配方法

技术领域

本发明涉及一种解决认知无线网络动态频谱分配的效率与公平性问题的高效与公平的动态频谱分配方法，属于认知无线通信网络的动态资源划分技术领域。

背景技术

动态频谱分配是分布式、多用户的多方动态博弈问题。各个认知用户在资源有限的情况下，对频谱的占用过程可以看作是一个博弈过程，这种博弈包括通信时间先后的竞争、通信频率的竞争等。每个认知用户在使用频谱时，都希望能够最大程度满足自己的通信需求，但是，对于整个系统来说，无序的竞争反而可能导致整体性能的下降。因此，为了提高多个认知用户的频谱分配效率，就必须让各个认知用户按照一定的规则或算法使用频谱。

目前皆采用博弈论的理论、模型和算法，研究多用户间的频谱分配，解决多个认知用户之间的频谱资源竞争问题。

交互式认知无线网络中的动态频谱管理需要考虑四方面的问题：(1)认知用户对主用户的干扰问题；(2)认知用户之间的竞争问题；(3)频谱时变特性的最优频谱分配问题；(4)认知无线电系统的效率和用户间的公平性问题。对于(1)、(2)两个问题，通常采用静态博弈论的模型和方法。第(3)个问题，特别是连续时变频谱的最优频谱分配问题，是随时间变化的动态博弈和合作的过程。第(4)个问题属于合作与协同，通过协调可实现合作，发挥各方的所长与优势，协同创造共赢的局面。

文献1(Z.Ji，and K.J.R.Liu.Multi-Stage Pricing Game forCollusion-Resistant Dynamic Spectrum Allocation.IEEE Journal on SelectedAreas in Communications，2008，26(1)：182-191.)将动态频谱分配建模为一个多阶段定价博弈，并提出一种抑制冲突的动态定价方法，使用最优保留价格消除冲突，并最大化用户的效用水平。同时，使用纳什讨价还价解分析该方案的边界条件，需要的边界约束更低。仿真结果表明，在不同的用户冲突情况下，均可获得较高的频谱利用率。文献2(Dusit Niyato，Ekram Hossain.CompetitivePricing for Spectrum Sharing in Cognitive Radio Networks：Dynamic Game，Inefficiency of Nash Equilibrium，and Collusion.IEEE Journal on SelectedAreas In Communications，2008，26(1)：192-202.)提出多个主系统间频谱价格博弈的Bertrand模型，但假设参与博弈的主系统完全对称，没有任何差异，这只是认知无线网络的特殊情况。

可见，目前认知无线网络技术中的大部分技术方案都基于静态博弈论和重复博弈展开，虽然以上这些方法在实现高效与公平的动态频谱分配方面取得了一些进步，但是不能真实地反映使用场景。事实上，动态频谱分配是一个随时间动态交互的过程，前一时刻的最优频谱分配方案，可能在下一刻不再保持其最优性。也就是说，在认知无线网络中，无线电环境随着时间和空间的变化有着不同的特性，并且工作频率和带宽等频带信息也具有不同的特性；同时，由于认知无线网络中用户对带宽的需求、可用信道的数量、状况和位置都是随时变化的。因此，灵活有效的频谱分配方法显得至关重要。认知无线网络为了满足用户的QoS需求，必须在时变的可用频带中选出最佳频带。

发明内容

本发明的目的在于提供一种基于合作微分博弈的交互式认知无线网络高效与公平的动态频谱分配方法，以解决目前的动态频谱分配方法尚不能真实地反映时变射频环境的问题。

为解决上述技术问题，本发明提供的高效与公平的动态频谱分配方法包括以下步骤：基于合作微分博弈理论，将交互式认知无线网络划分为不同的联盟，建立交互式认知无线网络“联盟-竞争”型体系结构；设定交互式认知无线网络具有n个认知用户，以及每个认知用户i∈N的目标函数或支付函数为：

i∈N＝{1，2，...，n}，s∈[0，∞)(1)；式(1)中，s表示时刻，N表示认知用户集合，状态变量x(s)表示交互式认知无线网络在时刻s可用频谱的百分比，控制变量ui(s)表示每个认知用户i∈N在时刻s的频谱接入率，正常数r表示交互式认知无线网络的贴现率，可用频谱的百分比x(s)满足如下的动态系统：

对式(1)求解。

本发明通过将“合作微分博弈”与“交互式认知无线网络”相结合，可以基于合作微分博弈理论，对交互式认知无线网络动态频谱分配建模与仿真，解决频谱接入的动态性和合作性问题，同时，还可以兼顾频谱使用的公平性和效率。因此，本发明可以有效缓解频谱资源的稀缺，提高频谱的利用率，对管理者、维护人员、厂商和终端用户都将产生深远的影响。对频谱管理者而言，可以有效改善频谱的利用率，为新的通信应用提供更多可用的频谱。对维护人员而言，通过最大化可利用频谱，可以最大化收益；可以实现异构网络的无缝切换；可以有效降低运维成本。对厂商而言，可以降低成本，并对新的需求做出快速响应。对终端用户而言，可以在任何时间、任何地点，使用任何设备廉价地接入任意网络，实现无线邀游。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例的流程示意图；

图2为基于合作微分博弈的模型求解与分析过程示意图。

具体实施方式

下面将结合本发明的附图，对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

图1示意性的示出了本发明实施例的步骤，如其所示，为了提高交互式认知无线网络动态频谱分配的效率，首先在步骤S11中，提出并建立一种基于合作微分博弈理论的交互式认知无线网络“联盟-竞争”型体系结构，并优选地根据位置、频率范围、频率使用密集程度和发射功率，将认知网络划分为不同的联盟，每个联盟内部有合作，各联盟之间有竞争，这样可以更好地反映现实的认知无线电系统，具有更好的应用价值。

接着如步骤S12，设定交互式认知无线网络具有n个认知用户，考虑该具有n个认知用户的频谱共享场景，其中每个认知用户i∈N的目标函数或支付函数如下：

$\underset{u_i}{\max }{\∫}_0^{\∞}\left[\frac{x\left(s\right)-u_i\left(s\right)}{x\left(s\right)}{u}_i\left(s\right)\right]\exp (-\mathrm{rs})\mathrm{ds},$ i∈N＝{1，2，...，n}，

s∈[0，∞)(1)。

；

在上式(1)中，s表示时刻，N表示认知用户集合，状态变量x(s)表示交互式认知无线网络在时刻s可用频谱的百分比，控制变量u_i(s)表示每个认知用户i∈N在时刻s的频谱接入率，正常数r表示交互式认知无线网络的贴现率，优选地设r＝1.5。

在交互式认知无线网络中，可用频谱的百分比满足如下的动态系统：

$\stackrel{\·}{x}\left(s\right)=x\left(s\right)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i\left(s\right),x\left(0\right)=x_0;---\left(2\right).$

如步骤S13，求解上式(1)，并且优选地，合作微分博弈的求解过程包括以下步骤：

(1)计算总联盟的最大收益；

(2)计算联盟中各个成员在非合作的情况下的纳什均衡解；

(3)计算除总联盟之外的所有可能联盟的收益；

(4)确定特征方程；

(5)计算夏普利值；

(6)确定一个具有时间一致性的收益分配程序(Income DistributionProcedure，简称IDP)。

具体求解与分析过程如图2所示，微分博弈是处理双方或多方连续动态对抗博弈问题的理论，目前主要面向军事、经济等领域，尚未应用于通信资源共享问题，其主要数学基础是贝尔曼的《动态规划》和庞特里亚金的《最优过程的数学理论》。最优化的方法在通信领域的应用非常广泛，如图论、遗传算法、神经网络等。只要找到描述认知无线网络相应模型与算法的目标函数和状态方程(组)，即可将其转换为一个多目标决策问题，最后求解对应的伯努利方程组或里卡提(Riccati)方程组，即可求得最优解，然后再分析解的唯一性等。而这些方程组不论是数值解还是解析解，在一定条件下都是可解的。

为了使得本领域技术人员进一步理解本发明，本发明的一实施例则具体提供了一种求解式(1)的方法，具体如下：

(1)计算总联盟的最大收益。

计算总联盟的最大收益就是解一个标准的动态规划问题，目标函数是最大化所有认知用户频谱使用率，约束条件即为上述式(2)，得到：

$\underset{u_i,u_2,...u_n}{\max }\underset{i\∈N}{\mathrm{\Σ}}{\∫}_t^{\∞}\left[\frac{x\left(s\right)-u_i\left(s\right)}{x\left(s\right)}{u}_i\left(s\right)\right]\exp [-r(s-t)]\mathrm{ds};---\left(3\right)$

$\stackrel{\·}{x}\left(t\right)=x\left(t\right)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i\left(t\right),x\left(0\right)=x_0,x\left(t\right)=x^N\left(t\right);---\left(4\right)$

为了求解博弈(3)-(4)的反馈纳什均衡解，可以得到贝尔曼方程如下：

$\mathrm{rW}(N,x,t)=\underset{u_1,u_2,...u_n}{\max }\{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\frac{x-u_i}{x}{u}_i+W_x(N,x,t)(x-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i)\}---\left(5\right)$

其中，W(N，x，t)表示上述动态规划问题的贝尔曼值函数，对式(5)的两边分别对u_i求偏导数，可得：

$u_i^N=[1-W_x(N,x,t)]x/2,i\∈N$

将

带入式(5)并求解，可得：

$W(N,x,t)=\frac{n+1-\sqrt{2n+1}}{n}x;---\left(6\right)$

$u_i^N=\frac{\sqrt{2n+1}-1}{2n}x,i\∈N;---\left(7\right)$

式(7)显示了在总联盟下频谱接入率

与可用频谱的百分比x的关系。尽管

并不显式依赖于时间t，但x是时变的，所以它真实地反映了时变的射频环境。

交互式认知无线网络最优的可用频谱的百分比如下：

$x^N\left(t\right)=x_0\exp \left(\frac{3-\sqrt{2n+1}}{2}t\right);---\left(8\right)$

(2)计算联盟中各个成员在非合作的情况下的纳什均衡解。

非合作博弈(1)-(2)的反馈纳什均衡解必须满足以下的条件：

$r{V}^i(t,x)=\underset{u_i}{\max }\{\frac{x-u_i}{x}{u}_i+V_x^i(t,x)(x-u_i-\underset{j=1,j\≠i}{\overset{n}{\mathrm{\Σ}}}{u}_j)\};---\left(9\right)$

其中，Vⁱ(t，x)表示第i个认知用户的贝尔曼值函数，对式(9)的两边分别对u_i求偏导数，可得：

$u_i^{*}=[1-V_x^i(t,x)]x/2,i\∈N;---\left(10\right)$

将式(10)带入式(9)并求解，可得：

$V^i(t,x)=\frac{n+1-\sqrt{n^2+2}}{2n-1}x,i\∈N;---\left(11\right)$

每个认知用户i∈N的频谱接入率的反馈纳什均衡解求解如下：

$u_i^{*}=\frac{n-2+\sqrt{n^2+2}}{2(2n-1)}x,i\∈N;---\left(12\right)$

(3)计算除总联盟之外的所有可能联盟的收益。

计算除总联盟和单个认知用户组成的博弈的收益，这样的联盟有2ⁿ-n-2。使用W(K，x，t)表示联盟K的贝尔曼值函数，则W(K，x，t)必须满足以下的贝尔曼方程：

$rW(K,x,t)=\underset{u_i,i\∈K}{\max }\{\underset{i\∈K}{\mathrm{\Σ}}\frac{x-u_i}{x}{u}_i+W_x(K,x,t)[x-\underset{i\∈K}{\mathrm{\Σ}}{u}_i-\underset{j\∉K}{\mathrm{\Σ}}{u}_j^{*}]\};---\left(13\right)$

对式(13)的两边分别对u_i求偏导数，可得：

$u_i^K=[1-W_x(K,x,t)]x/2,i\∈K.$

将带入式(13)并求解，可得：

$W(K,x,t)=\frac{A-\sqrt{A^2-k^2}}{k}x;---\left(14\right)$

$u_i^K=\frac{k-A+\sqrt{A^2-k^2}}{2k}x,i\∈K;---\left(15\right)$

其中： $A=n+1-(n-k)\·\frac{n+1-\sqrt{n^2+2}}{2n-1}.$

(4)定义特征方程。

该合作博弈的特征函数v(K；x，t)定义如下：

v({i}；x，t)＝Vⁱ(t，x)；

$v(K;x,t)=W(K,x,t),K\⊆N;$

其中，特征函数值由下式给定：

$v\left(\right\{i\};x,t)=V^i(t,x)=\frac{n+1-\sqrt{n^2+2}}{2n-1}x,i\∈K;$

$v(K;x,t)=W(K,x,t)=\frac{A-\sqrt{A^2-k^2}}{k}x;$

$A=n+1-(n-k)\·\frac{n+1-\sqrt{n^2+2}}{2n-1},K\⊆N.$

(5)计算夏普利值。

该合作博弈的夏普利值如下：

${\mathrm{\Φ}}_i^v(x,t)=\underset{i\∈K}{\mathrm{\Σ}}\frac{(k-1)!(n-k)!}{n!}[v(K;x,t)-v(K\backslash \{i\};x,t)]$

i＝1，...，n；(16)

当n＝3时有：

${\mathrm{\Φ}}_i^v(x,t)=\frac{4-\sqrt{7}}{9}x,i\∈\left\{\mathrm{1,2,3}\right\};---\left(17\right)$

夏普利值通过概率的方式给出了具体的频谱分配方案，显示了公平性和唯一性，每个认知用户可以获得最优的频谱接入机会。

(6)确定一个具有时间一致性的收益分配程序。

沿着公式(8)表示的交互式认知无线网络最优的可用频谱的百分比x^N(t)，为了对夏普利值

提供一个瞬时的分配，可以使用如下的分配函数：

$B_i\left(t\right)=r{\mathrm{\Φ}}_i^v(x^N\left(t\right),t)-\frac{d}{\mathrm{dt}}{\mathrm{\Φ}}_i^v(x^N\left(t\right),t);---\left(18\right)$

直接计算得：

$B_i\left(t\right)=\frac{4\sqrt{7}-7}{18}{x}^N\left(t\right);---\left(19\right)$

在同一个联盟内部，每个认知用户对频谱的使用没有差异性，显示了模型的公平性，同时能够改善频谱的利用率，真实地反映时变的射频环境。

综上，本发明为了解决认知无线网络动态频谱分配的动态性和合作性方面的问题，基于合作随机微分博弈理论，提出了新的思路和方向，为动态场景的决策选择问题提供了数学依据，也使得寻找稳态解成为了可能，从而，可以有效地利用频谱资源，满足不同用户对频谱资源的需求，增大系统容量，提高频谱利用率。因此，将合作微分博弈引入认知无线网络可以解决认知无线网络动态频谱分配问题，有效缓解频谱资源的稀缺，提高频谱的利用率。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。

Claims (5)

1.一种高效与公平的动态频谱分配方法，适用于交互式认知无线网络，其特征在于，包括以下步骤：

基于合作微分博弈理论，将交互式认知无线网络划分为不同的联盟，建立交互式认知无线网络“联盟-竞争”型体系结构；

设定交互式认知无线网络具有n个认知用户，以及每个认知用户i∈N的目标函数或支付函数为：

$\underset{u_i}{\max }{\∫}_0^{\∞}\left[\frac{x\left(s\right)-u_i\left(s\right)}{x\left(s\right)}{u}_i\left(s\right)\right]\exp (-\mathrm{rs})\mathrm{ds},$ i∈N＝{1，2，...，n}，s∈[0，∞)；(1)

式(1)中，s表示时刻，N表示认知用户集合，状态变量x(s)表示交互式认知无线网络在时刻s可用频谱的百分比，控制变量ui(s)表示每个认知用户i∈N在时刻s的频谱接入率，正常数r表示交互式认知无线网络的贴现率，可用频谱的百分比x(s)满足如下的动态系统：

$\stackrel{\·}{x}\left(s\right)=x\left(s\right)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i\left(s\right)$

x(0)＝x₀；(2)

对式(1)求解。

2.根据权利要求1所述的高效与公平的动态频谱分配方法，其特征在于，将交互式认知无线网络划分为不同联盟的根据为位置、频率范围、频率使用密集程度和发射功率。

3.根据权利要求1所述的高效与公平的动态频谱分配方法，其特征在于，设正常数r＝1.5。

4.根据权利要求1所述的高效与公平的动态频谱分配方法，其特征在于，对式(1)求解进一步包括以下步骤：

计算总联盟的最大收益；

计算联盟中各个成员在非合作的情况下的纳什均衡解；

计算除总联盟之外的所有可能联盟的收益；

确定特征方程；

计算夏普利值；

确定一个具有时间一致性的收益分配程序。

5.根据权利要求4所述的高效与公平的动态频谱分配方法，其特征在于，

在计算总联盟的最大收益步骤中，将计算总联盟的最大收益视为求解一个标准的动态规划问题，则最大化所有认知用户频谱使用率的目标函数或支付函数的约束条件为所述式(2)，借此得到：

$\underset{u_i,u_2,...u_n}{\max }\underset{i\∈N}{\mathrm{\Σ}}{\∫}_t^{\∞}\left[\frac{x\left(s\right)-u_i\left(s\right)}{x\left(s\right)}{u}_i\left(s\right)\right]\exp [-r(s-t)]\mathrm{ds};---\left(3\right)$

$\stackrel{\·}{x}\left(t\right)=x\left(t\right)-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i\left(t\right),x\left(0\right)=x_0,x\left(t\right)=x^N\left(t\right);---\left(4\right)$

计算贝尔曼方程如下式(5)，以求解式(3)-(4)的反馈纳什均衡解：

$\mathrm{rW}(N,x,t)=\underset{u_1,u_2,...u_n}{\max }\{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}\frac{x-u_i}{x}{u}_i+W_x(N,x,t)(x-\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{u}_i)\}---\left(5\right)$

其中，W(N，x，t)表示所述动态规划问题的贝尔曼值函数，对式(5)的两边分别对u_i求偏导数，可得：

$u_i^N=[1-W_x(N,x,t)]x/2,i\∈N;$

将

带入式(5)并求解，可得：

$W(N,x,t)=\frac{n+1-\sqrt{2n+1}}{n}x;---\left(6\right)$

$u_i^N=\frac{\sqrt{2n+1}-1}{2n}x,i\∈N;---\left(7\right)$

式(7)显示在总联盟下频谱接入率

与可用频谱的百分比x的关系，且交互式认知无线网络最优的可用频谱的百分比如下式：

$x^N\left(t\right)=x_0\exp \left(\frac{3-\sqrt{2n+1}}{2}t\right);---\left(8\right)$

在计算联盟中各个成员在非合作的情况下的纳什均衡解的步骤中，式(1)-(2)的反馈纳什均衡解满足下式(9)：

$r{V}^i(t,x)=\underset{u_i}{\max }\{\frac{x-u_i}{x}{u}_i+V_x^i(t,x)(x-u_i-\underset{j=1,j\≠i}{\overset{n}{\mathrm{\Σ}}}{u}_j)\};---\left(9\right)$

其中，Vⁱ(t，x)表示第i个认知用户的贝尔曼值函数，对式(9)的两边分别对u_i求偏导数，可得：

$u_i^{*}=[1-V_x^i(t,x)]x/2,i\∈N;---\left(10\right)$

将式(10)带入式(9)并求解，可得：

$V^i(t,x)=\frac{n+1-\sqrt{n^2+2}}{2n-1}x,i\∈N;---\left(11\right)$

每个认知用户i∈N的频谱接入率的反馈纳什均衡解求解如下：

$u_i^{*}=\frac{n-2+\sqrt{n^2+2}}{2(2n-1)}x,i\∈N;---\left(12\right)$

在计算除总联盟之外的所有可能联盟的收益的步骤中，计算除总联盟和单个认知用户组成的博弈的收益，这样的联盟有2ⁿ-n-2。以W(K，x，t)表示联盟K的贝尔曼值函数，则W(K，x，t)满足以下的贝尔曼方程：

$rW(K,x,t)=\underset{u_i,i\∈K}{\max }\{\underset{i\∈K}{\mathrm{\Σ}}\frac{x-u_i}{x}{u}_i+W_x(K,x,t)[x-\underset{i\∈K}{\mathrm{\Σ}}{u}_i-\underset{j\∉K}{\mathrm{\Σ}}{u}_j^{*}]\};---\left(13\right)$

对式(13)的两边分别对u_i求偏导数，可得：

$u_i^K=[1-W_x(K,x,t)]x/2,i\∈K;$

将带入式(13)并求解，可得：

$W(K,x,t)=\frac{A-\sqrt{A^2-k^2}}{k}x;---\left(14\right)$

$u_i^K=\frac{k-A+\sqrt{A^2-k^2}}{2k}x,i\∈K;---\left(15\right)$

其中： $A=n+1-(n-k)\·\frac{n+1-\sqrt{n^2+2}}{2n-1};$

在确定特征方程的步骤中，将所述合作博弈的特征函数v(K；x，t)定义如下：

v({i}；x，t)＝Vⁱ(t，x)；

$v(K;x,t)=W(K,x,t),K\⊆N;$

其中，特征函数值由下式给定：

$v\left(\right\{i\};x,t)=V^i(t,x)=\frac{n+1-\sqrt{n^2+2}}{2n-1}x,i\∈K;$

$v(K;x,t)=W(K,x,t)=\frac{A-\sqrt{A^2-k^2}}{k}x;$

$A=n+1-(n-k)\·\frac{n+1-\sqrt{n^2+2}}{2n-1},K\⊆N;$

在计算夏普利值的步骤中，该合作博弈的夏普利值如下：

${\mathrm{\Φ}}_i^v(x,t)=\underset{i\∈K}{\mathrm{\Σ}}\frac{(k-1)!(n-k)!}{n!}[v(K;x,t)-v(K\backslash \{i\};x,t)]$

i＝1，...，n   ；(16)

当n＝3时有：

${\mathrm{\Φ}}_i^v(x,t)=\frac{4-\sqrt{7}}{9}x,i\∈\left\{\mathrm{1,2,3}\right\};---\left(17\right)$

在确定一个具有时间一致性的收益分配程序的步骤中，根据式(8)表示的交互式认知无线网络最优的可用频谱的百分比x^N(t)，利用下式(18)的分配函数，对夏普利值

提供一个瞬时的分配：

$B_i\left(t\right)=r{\mathrm{\Φ}}_i^v(x^N\left(t\right),t)-\frac{d}{\mathrm{dt}}{\mathrm{\Φ}}_i^v(x^N\left(t\right),t);---\left(18\right)$

直接计算得：

$B_i\left(t\right)=\frac{4\sqrt{7}-7}{18}{x}^N\left(t\right);---\left(19\right)$