一种基于稳定匹配算法的保证需求下限的频谱分配方法

摘要

本发明涉及一种基于稳定匹配算法的保证需求下限的频谱分配方法，根据频谱买家的最低频谱需求和预算成本以及干扰关系，计算为满足所有买家需求下限须保留的频谱数和可自由支配的频谱数量，在此基础上运行改进的递延接受模式的匹配算法，达到稳定的频谱分配结果，保证了频谱分配结果满足次级用户的最低频谱需求和成本预算，提高了初级用户和次级用户的频谱交易成功率和满意度。

说明书

技术领域

本发明属于计算机网络技术领域，尤其涉及基于稳定匹配算法的保证需求下限的频谱分配模型。

背景技术

在当今的互联网时代，无线通信网络的频谱是一种不可或缺的重要资源。然而，由于无线通信流量的日益增长，频谱也成为了一种紧张的资源。为了尽可能更好地利用现有的频谱、避免由于传统的静态频谱分配方法而造成的频谱浪费。动态的频谱分配方法由此诞生，它能够使无线通信服务提供商根据自己的需求买卖过剩的频谱信道。

频谱的交易活动其本质上是频谱买卖双方的一种匹配。相对于最优的频谱匹配结果，稳定的频谱匹配结果是针对自由频谱交易市场的合理的匹配结果。理由如下：(1)交易市场中的买卖双方都是自私性的，只考虑最大化自身的利益，这与整个交易系统的最优化的目标并不一定严格一致。最优的匹配算法只有在存在“控制者”的集中式系统中可以强制执行，而稳定的匹配算法则考虑了买家和卖家的个人偏好，使得任何买家或卖家都能单方面得到更好的匹配结果，保证了匹配算法在分布式的自由频谱交易市场的实行。(2)从计算复杂度上来说，最优的匹配方案往往是NP困难的，而稳定的频谱匹配方法可以在多项式时间内被解决。

稳定的匹配算法源于Gale和Shapley等人的研究。他们最早提出了递延接受Deferred Acceptance(DA)算法，解决了具有需求上限的匹配问题。递延接受算法在计算机科学领域被广泛应用于资源的分配问题，如云端的虚拟机管理、家庭基站中的用户接入、端到端的频谱共享等问题。

区别于传统的匹配问题，频谱分配具有复用性的重要特质。复用性是指在无线通信过程中，由于信号的衰减，距离足够远的两个用户的信号不会相互干扰，因此这两个用户可以使用相同的频谱。同理，在频谱交易市场中可以允许频谱卖家将它的频谱出售给距离足够远、信号不会相互干扰的买家。频谱复用提高了频谱的使用效率，但是给稳定的频谱匹配算法设计带来了挑战。Y.Chen等人曾提出过adapted two-stage deferred acceptance算法，该算法利用了频谱可复用性，并且能给出稳定的匹配结果。然而，这种算法仅仅考虑到了每个买家的频谱需求上限。事实上，为了实现无线通信的正常运营，频谱买家也有其频谱需求下限。传统的递延接受算法并不能满足需求下限，D.Fragiadakis提出了一种拓展递延接受算法，用于解决同时存在需求上限和需求下限的匹配问题。然而，由于频谱具有复用性的特质，这中算法并不能直接被用于解决频谱的匹配问题。

发明内容

本发明针对现有技术的不足，提供一种基于稳定匹配算法的保证需求下限的频谱分配模型。

本发明的技术方案为基于稳定匹配算法的保证需求下限的频谱分配模型，包含以下步骤：

一种基于稳定匹配算法的保证需求下限的频谱分配方法，其特征在于，定义P个频谱买家，Q个频谱卖家，频谱买家为次级用户，频谱卖家为初级用户，该方法包含以下步骤：

步骤1，建立Q个干扰图，每个干扰图对应一个频谱卖家的频谱，即针对频谱卖家s，建立干扰图G^s＝(N,E^s)，其中节点集合N为P个频谱买家的集合，边集合E^s的建立方式如下。对于每一对频谱买家j,j’，如果j，j’在频谱s上干扰，则添加边到边集合E^s中。步骤2，根据频谱买家对频谱卖家的频谱的出价，建立买家对卖家的偏好关系和卖家对买家集合的偏好关系，具体方法是：买方对卖方的偏好关系的生成方法为，如果买家i对卖家j和卖家j’的出价关系为那么偏好关系为j＞＞i j′。卖家对买家集合的偏好关系由买家的出价和干扰图决定决定。假设对于卖家i有买家集合A和B，如果买家集合A中的买家都相互不干扰，即卖家集合B中存在相互干扰的买家，即那么偏好关系为A＞＞_i>那么偏好关系为A＞＞_i>

步骤3，计算可自由支配频谱数θ，具体步骤如下：

步骤3.1、对于每一个需求下限为p_c的买家s，创建p_c个虚拟节点。

步骤3.2、每个新建的虚拟节点均继承原节点的所有的干扰关系，即继承原节点在所有原始干扰图中的边。

步骤3.3、在同一原节点的每两个虚拟节点之间创建冲突边。

步骤3.4、对根据步骤步骤3.1至步骤3.3得到的干扰图，使用Welch>

步骤4，根据每一个买家c的需求下限p_c和需求上限q_c(由买家预算决定)，生成两个新的虚拟买家：常规型c^a和拓展型c^b。c^a的需求下限为0，需求上限为p_c；c^b的需求下限为0，需求上限为q_c-p_c。c^a和c^b均继承c对所有卖家的出价和偏好关系。对所有卖家的频谱，以所有新的虚拟买家为结点建立新的干扰图G^s，具体步骤如下：

步骤4.1、c^a和c^b继承所有c的冲突关系，即继承c在原始干扰图中的边。

步骤4.2、在c^a和c^b之间建立一条边。

步骤5，频谱匹配，具体步骤如下；

步骤5.1、将所有卖家s的候选匹配对象列表A_S置为全体买家N。将所有买家c的候选匹配对象列表W_c置为空集。将所有买家的最终匹配列表μ(c)和所有卖家的最终匹配列表μ(s)置为空集。

步骤5.2、如果存在卖家的候选匹配对象列表A_S不为空集，跳转至步骤5.3；否则，整个算法结束。

步骤5.3、对所有的候选匹配对象列表A_S不为空集的卖家s，使用贪心算法在其干扰图G^s上求出极大独立集

步骤5.4、如果根据步骤5.23求出的所有卖家s的都为空集，则结束步骤5；否则，跳转至步骤5.5。

步骤5.5、对于所有卖家s的极大独立集中的买家c，将s加入c的候选匹配对象列表W_c中；将c从s的候选匹配对象列表A_S中删除，并且在s的冲突图G^s中将代表c的节点以及与其相连的边删除。

步骤5.6、对于所有的候选匹配对象列表W_c不为空的买家c，进行如下处理：

步骤5.61、如果c属于常规型买家，在W_c和μ(c)的并集中选取c最偏好的不超过c的需求上限个数的频谱作为新的μ(c)，并将c加入这些频谱的匹配列表μ(s)中，跳转至步骤5.7；否则，如果c属于拓展型买家时，令临时计数变量count＝0，跳转至步骤5.62。

步骤5.62、当count小于可自由支配频谱数θ，并且存在拓展型买家c满足μ(c)的模小于c的需求上限并且c的候选匹配对象列表W_c不为空集时，依次考虑买家c的匹配频谱，否则，跳转至步骤5.7。考虑买家c_i，如果μ(c_i)的模小于c_i的需求上限且c_i的候选匹配对象列表不为空集，从和μ(c_i)的并集中取c_i最偏好的一个频谱s加入到μ(c_i)中，并且将c_i加入频谱s的匹配列表μ(s)中，将s从中删除，并将干扰图G^s中代表c_i的节点及其所连接的边删除，将计数变量count加1；否则，如果μ(c_i)的模等于c_i的需求上限或者c_i的候选匹配对象列表不为空集时，i＝i+1，重复步骤5.62。

步骤5.7、清空W_c。

步骤5.8跳转至步骤5.2。

在上述的一种基于稳定匹配算法的保证需求下限的频谱分配方法，

在步骤3中，Welch Powell算法包括：

步骤2.1、将干扰图G中的节点按度数递减的次序进行排列(相同度数的结点的排列随意)。

步骤2.2、用第一种颜色对第一个节点着色，并按排列次序对与前面节点不相邻的每一点着同样的颜色。

步骤2.3、用第二种颜色对尚未着色的点重复步骤2.2、,直到所有的点都着上颜色为止。

步骤2.4、所需要的颜色数为coloring。可自由支配的频谱数为θ＝M-coloring。

在上述的一种基于稳定匹配算法的保证需求下限的频谱分配方法，在步骤5中，用于计算求解最大独立集的贪心算法包括：

步骤5.1、对于所有的卖家s，找出买家集合Q_s。在Q_s中的买家满足约束条件：

约束条件1、在候选匹配对象列表A_S中；

约束条件2、不与匹配列表μ(s)中的任何买家c干扰。

步骤5.2、为干扰图G^s里包含Q_s买家的子图，对于中的节点n，weight_n为节点n的权重，degree_n为节点n的度，按照weight_n/(degree_n+1)降序对节点排序。

步骤5.3、取出排在最前面的一个节点n，即weight_n/(degree_n+1)的值最大的节点，将其加入到最大独立集中，将其从删除，并将所有与其相连的节点和边从中删除。

步骤5.4、当中不再存在节点时，结束该算法；否则，跳转至步骤5.2。

本发明具有如下优点：本发明所描述的频谱分配方法可以满足所有频谱买家的频谱需求下限和成本预算，并且保证频谱分配结果的稳定性，即不存在任何一对频谱买家和卖家希望相互替换掉自己当前匹配的频谱卖家和买家。该频谱分配方法的运行效率高，具有多项式的复杂度。与传统的频谱分配方法相比，该发明得到的最终频谱分配结果提高了频谱买家和频谱卖家的交易成功率和满意度。

附图说明

图1是本发明的频谱匹配方法的算法流程图。

图2a是本发明实施例的频谱匹配流程图(第一轮)。

图2b是本发明实施例的频谱匹配流程图(第二轮)。

图2c是本发明实施例的频谱匹配流程图(第三轮)。

图2d是本发明实施例的频谱匹配流程图(最后匹配结果)。

图3是本发明的Welch Powell算法流程图。

图4是本发明最大独立集的贪心算法流程图。

图5是本发明实施例中，假设次级用户(频谱买家)在每条频谱上的干扰图相同的关系示意图。

图6是本发明实施例中，为三个买家创建2、1、2个虚拟节点后的关系示意图。

图7是本发明实施例中，生成的常规型和拓展型买家后的干扰图。

具体实施方式

本发明主要基于满足需求下限的拓展递延算法，考虑频谱可复用的特性，提出的一种基于稳定匹配算法的保证需求下限的频谱分配模型。本方法充分考虑了匹配成功率和买家和卖家的满意度。通过本发明获得的频谱分配结果可以适用于频谱自由交易的频谱市场。

本发明提供的方法能够用计算机软件技术实现流程。参见图1，实施例为对本发明的流程进行一个具体的阐述，实施例如下：

假设存在三个频谱买家A,B,C，六个频谱卖家a,b,c,d,e,f，每个频谱卖家拥有一个频谱。频谱买家对频谱卖家的出价如下表所示。

表1.

买家A买家B买家C卖家a611卖家b423卖家c265卖家d134卖家e552卖家f346需求下限212需求上限333

步骤1，根据次级用户在每个初级用户的频谱上传输的干扰关系建立干扰图G^s＝(N,E^s)，其中节点集合N代表所有的次级用户。如果次级用户c和c’在频谱s上干扰，则添加边到边集合E^s中。

实施例中，假设次级用户(频谱买家)在每条频谱上的干扰图相同，都如图5所示。

步骤2，根据次级用户(频谱买家)对初级用户(频谱卖家)的频谱的出价，建立买家对卖家的偏好关系和卖家对买家集合的偏好关系。

买方对卖方的偏好关系的生成方法为，如果买家i对卖家j和卖家j’的出价关系为那么偏好关系为j＞＞i j′。卖家对买家集合的偏好关系由买家的出价和干扰图决定决定。假设对于卖家i有买家集合A和B，如果买家集合A中的买家都相互不干扰，即卖家集合B中存在相互干扰的买家，即那么偏好关系为A＞＞i B；如果买家集合A中的买家和集合B中的买家都相互不干扰，而A中买家的总出价高于B中买家的总出价，即那么偏好关系为A＞＞i B，反之亦然。

实施例的具体实施方案如下：

根据买家对卖家的出价，可以建立买家对卖家的偏好关系如下：

a＞＞_A>A>A>A>A>

c＞＞_B>B>B>B>B>

f＞＞_C>C>C>C>C>

步骤3，计算可自由支配频谱数θ，具体步骤如下：(1)对于每一个需求下限为p_c的买家s，创建p_c个虚拟节点。(2)每个新建的虚拟节点均继承原节点的所有的干扰关系，即继承原节点在所有原始干扰图中的边。(3)在同一原节点的每两个虚拟节点之间创建冲突边。(4)对根据步骤(1)(2)(3)得到的干扰图，使用Welch>

Welch Powell算法可描述如下：

(1)将干扰图G中的节点按度数递减的次序进行排列(相同度数的结点的排列随意)。

(2)用第一种颜色对第一个节点着色，并按排列次序对与前面节点不相邻的每一点着同样的颜色。

(3)用第二种颜色对尚未着色的点重复(2),直到所有的点都着上颜色为止。

(4)所需要的颜色数为coloring。

实施例的具体实施方案如下：

由于A,B,C的最小匹配数分别为2、1、2，因此分别为三个买家创建2、1、2个虚拟节点，即A,A’,B,C,C’。每个新建的虚拟节点均继承原节点的所有的干扰关系，即继承原节点在所有原始干扰图中的边。在同一原节点的每两个虚拟节点之间创建冲突边。如图6所示。

在由虚拟节点构成的图中，使用Welch Powell法，计算出能覆盖整个图的最小颜色数coloring，具体过程如下：

(1)按度数递减次序对冲突图中的结点进行排序，排序结果为A，A’，C，C’，B。

(2)用颜色1对A着色及不与A相连的节点着色。由于所有节点都与A相连，颜色1只能对A着色。同理，用颜色2对A’着色。用颜色3对C及不与C相连的结点B着色，用颜色4对C’着色。至此所有虚拟节点着色完毕。用了4种颜色。

(3)θ＝6-4＝2。

步骤3，根据每一个买家c的需求下限p_c和需求上限q_c(由买家预算决定)，生成两个新的虚拟买家：常规型c^a和拓展型c^b。c^a的需求下限为0，需求上限为p_c；c^b的需求下限为0，需求上限为q_c-p_c。c^a和c^b均继承c对所有卖家的出价和偏好关系。对所有卖家的频谱，以所有新的虚拟买家为结点建立新的干扰图G^s，具体步骤如下：(1)c^a和c^b继承所有c的冲突关系，即继承c在原始干扰图中的边。(2)在c^a和c^b之间建立一条边。

实施例的具体实施方案如下：

生成的常规型和拓展型买家为：A^a,A^b,B^a,B^b,C^a,C^b,需求下限都为0，需求上限分别为2、1、1、2、2、1，新的干扰图如图7所示。

步骤5，频谱匹配，具体步骤如下；

(1)将所有卖家s的候选匹配对象列表A_S置为全体买家N。将所有买家c的候选匹配对象列表W_c置为空集。将所有买家的最终匹配列表μ(c)和所有卖家的最终匹配列表μ(s)置为空集。

(2)如果存在卖家的候选匹配对象列表A_S不为空集，跳转至(3)；否则，结束步骤5。

(3)对所有的候选匹配对象列表A_S不为空集的卖家s，使用贪心算法在其干扰图G^s上求出极大独立集

(4)如果根据(3)求出的所有卖家s的都为空集，则结束步骤5；否则，跳转至(5)。

(5)对于所有卖家s的极大独立集中的买家c，将s加入c的候选匹配对象列表W_c中；将c从s的候选匹配对象列表A_S中删除，并且在s的冲突图G^s中将代表c的节点以及与其相连的边删除。

(6)对于所有的候选匹配对象列表W_c不为空的买家c，

a)如果c属于常规型买家，在W_c和μ(c)的并集中选取c最偏好的不超过c的需求上限个数的频谱作为新的μ(c)，并将c加入这些频谱的匹配列表μ(s)中，跳转至(7)；否则，如果c属于拓展型买家时，令临时计数变量count＝0，跳转至b)。

b)当count小于可自由支配频谱数θ，并且存在拓展型买家c满足μ(c)的模小于c的需求上限并且c的候选匹配对象列表W_c不为空集时，依次考虑买家c的匹配频谱，否则，跳转至(7)。考虑买家c_i，如果μ(c_i)的模小于c_i的需求上限且c_i的候选匹配对象列表不为空集，从和μ(c_i)的并集中取c_i最偏好的一个频谱s加入到μ(c_i)中，并且将c_i加入频谱s的匹配列表μ(s)中，将s从中删除，并将干扰图G^s中代表c_i的节点及其所连接的边删除，将计数变量count加1；否则，如果μ(c_i)的模等于c_i的需求上限或者c_i的候选匹配对象列表不为空集时，i＝i+1，重复b)。

(7)清空W_c。

(8)跳转至(2)。

用于计算求解最大独立集的贪心算法描述如下：

(1)对于所有的卖家s，找出买家集合Q_s。在Q_s中的买家满足条件：a)在候选匹配对象列表A_S中；b)不与匹配列表μ(s)中的任何买家c干扰。

(2)为干扰图G^s里包含Q_s买家的子图，对于中的节点n，weight_n为节点n的权重，degree_n为节点n的度，按照weight_n/(degree_n+1)降序对节点排序。

(3)取出排在最前面的一个节点n，即weight_n/(degree_n+1)的值最大的节点，将其加入到最大独立集中，将其从删除，并将所有与其相连的节点和边从中删除。

(4)当中不再存在节点时，结束该算法；否则，跳转至(2)。

如图2所示，实施例的具体实施方案如下：

此时进入匹配算法，将所有的买家虚拟节点A^a,A^b,B^a,B^b,C^a,C^b,都加入到卖家a,b,c,d,e,f的候选匹配对象列表A_s中。

在匹配算法的第一轮中，对于卖家a，由于A^a的weight_n/(degree_n+1)值最大，将A^a加入到卖家a的最大权独立集中，将A^a和与其相连的买家虚拟节点从干扰图中删除后，干扰图中不再存在节点，至此，卖家a的最大权独立集为{A^a}。同理，对于卖家b，由于C^a的weight_n/(degree_n+1)最大，将C^a加入到卖家b的最大权独立集中，并删除结点C^a,A^a,A^b,C^b,在剩下的节点中取节点B^a加入到中，干扰图中不再存在节点，至此，卖家b的最大权独立集为同理，剩余卖家的最大权独立集均为{C^a,B^a}。所有卖家均向自己最大权独立集中的买家提出匹配申请，并将其从A_S中删除，买家将提出申请的卖家放在候选匹配对象列表W_c中，并且在自己的干扰图中将提出申请的买家节点删除。即卖家a向A^a提出申请，其余卖家向C^a,B^a提出申请。对于A^a，提出申请的频道数为1，A^a的需求上限为2，由于提出申请的卖家数小于需求上限，A^a接受卖家a的匹配申请。对于B^a，提出申请的卖家数为5，B^a的需求上限为1，由于提出申请的卖家数大于需求上限，B^a接受最偏好的卖家c的申请。对于C^a，提出申请的卖家数为5，C^a的需求上限为2，由于提出申请的卖家数大于需求上限，C^a接受最偏好的卖家c和卖家f的申请。清空所有买家的候选匹配列表。至此，第一轮匹配结束。

在第二轮匹配算法中，由于频道a已经暂时与A^a匹配，因此在求卖家a的最大权独立集时，排除与A^a干扰的节点。至此，不再有结点，频道a的最大权独立集为空集。同理，求得卖家b的最大权独立集为{C^b,B^b}；卖家c的最大权独立集为空集；卖家d、e、f的最大权独立集为{C^b,B^b}。此时，C^b,B^b的候选匹配列表不为空，θ＝2。对于B^b，选择其候选匹配列表中最偏好的卖家e，此时count＝1<θ；对于C^b,选择其候选匹配列表中最偏好的卖家d，此时count＝2<θ。清空所有买家的候选匹配列表。至此，第二轮匹配结束。

第三轮匹配中，卖家b的最大权独立集为{A^a}，其余卖家的最大权独立集为空集。卖家b向A^a提出匹配申请。此时，卖家a暂时与A^a匹配，提出申请的卖家数与暂时匹配的卖家数之和为2，不大于A^a的需求上限，因此A^a接受卖家b的申请。

至此，匹配算法结束。匹配结果为，A^a与卖家a、b相匹配；B^a与卖家c相匹配；B^b与卖家e相匹配；C^a与卖家c、f相匹配；C^b与卖家d相匹配。

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。