基于频谱资源共享的动态分配算法

陈书恒，张朝阳，吴广富

(1.海军研究院，上海 200436；2.重庆邮电大学 移动通信技术重庆市重点实验室，重庆 400065)

0 引 言

无线物理网络(wireless physical network, WPN)拥有功率、时隙、频谱等物理资源。虚拟网络(virtual network, VN)从WPN处租赁物理资源，构建不同服务网络，并为用户提供服务。实际场景中用户行为具有随机变化的特性，使得VN实际需求的资源量具有时变性，而VN向WPN申请资源时，往往按照用户峰值需求的资源量进行申请，从而导致大部分时间内VN的资源未被完全使用。这样不仅提高了服务商租赁资源的成本，而且降低了WPN接受率。因此，VN资源请求的时变性是无线网络虚拟化资源分配中需要考虑的重要问题。

当前部分学者对无线网络虚拟化中资源分配问题做了大量研究。文献[1-2]将物理资源以及虚拟网络抽象成时域和频域组成的矩形图，提出了一种近似卡诺图的资源分配算法。其中，文献[1]介绍了一种在线分配算法，考虑了虚拟网络(virtual network, VN)动态地到达和离开特性，有效解决了资源分配过程中的在线虚拟网络请求和映射问题，但并没有考虑当物理资源出现碎片化后动态调整的问题；文献[2]在文献[1]的基础上提出了一种动态资源分配方案，并提出了资源重分配的思想。文献[3-5]研究了正交频分多址(orthogonal frequency division multiple access, OFDMA)系统中基于价格理论的能效优化问题，并利用非合作博弈理论求得纳什均衡解来进行资源分配。文献[6-9]提出了针对节点和链路的资源分配算法，但均未考虑动态性。其中，文献[6]和文献[8]在静态多跳网络中，利用最短路径算法为虚拟网络分配资源，使得干扰最小；文献[7]利用了网络链路可靠性为虚拟网络分配资源，但允许同一虚拟网络的不同节点映射到相同的物理节点上，使得链路间的干扰太大；文献[9]利用动态资源分配，使得重新分配的结果避免了和原分配方案相同，实现了资源的均衡利用。针对资源请求的时变性，文献[10-11]提出了基于频谱资源机会性共享的分配算法，但该算法没有考虑VN请求到达与离开的动态性。

为解决VN资源请求时变性和物理资源碎片问题，本文提出了基于频谱资源共享的动态分配算法(dynamic allocation algorithm based on spectrum resource sharing, DAA-SRS)。该算法结合虚拟请求的生命周期，进行子信道分配和重分配。针对无线虚拟网络资源请求接受率、物理网络收益等性能指标进行仿真分析，验证了DAA-SRS算法的可行性和有效性。

1 系统模型

1.1 资源映射

无线物理网络(wireless physical network, WPN)拥有功率、时隙、频谱等物理资源。虚拟网络(virtual network, VN)从WPN处租赁物理资源，构建不同服务网络，并为用户提供服务。本文主要考虑单个访问节点(access point, AP)的频谱资源分配问题，通过OFDMA技术将其划分为正交的子信道，如图1所示。因此，任意一个VN请求频谱资源，可以表示为请求一定数量的子信道。考虑到实际场景中用户行为具有随机变化的特性，使得VN实际需求的资源量具有时变性，而VN向WPN申请资源时，往往按照用户峰值需求的资源量进行申请，导致大部分时间内VN的资源未被完全使用。这样不仅提高了服务商租赁资源的成本，而且降低了WPN接受率。因此，VN资源请求的时变性是无线网络虚拟化资源分配中十分重要问题。文献[11]中将VN的请求分为2个部分：基本资源请求(basic resource request, BRR)和可变资源请求(varied resource request, VRR)。BRR是在其对应VN整个生命周期内为满足用户的基本需求所垄断的物理频谱资源，即WPN为其分配相应数量的物理子信道；VRR是依概率发生的，并且多个VNs的VRR共享物理子信道。基于机会共享机制，VNs使物理子信道数量减少，从而降低租赁物理资源成本，同时也能够为WPN提供更多VNs的接受机会。

图1 无线资源映射Fig.1 Wireless resource mapping

1.2 机会共享机制

机会性地共享相同频谱会引发碰撞，即多个VNs的VRR同时共享于同一个物理信道。碰撞发生时，会使网络服务质量(quality of service, QoS)和用户体验质量(quality of experience，QoE)恶化。为避免这种情况的发生，文献[10-11]设置了一个碰撞概率的阈值pth。规定当多个VNs在某一物理信道上的碰撞概率不大于pth，就允许VNs共享该物理信道；调节pth的大小会直接影响到频谱利用率，进而会影响QoS和QoE。因此，根据实时要求和系统状态动态地调整并合理地设置pth是至关重要的。假设碰撞阈值为pth=0.1，VN1和VN2的VRR的发生概率分别为0.2，0.3，则VN1和VN2的碰撞概率为0.2×0.3=0.06<0.1，这样VN1和VN2的VRR虚拟信道就可以共享同一物理信道；若VN1，VN2的VRR发生概率分别为0.4，0.3，就不能共享同一信道，因为0.4×0.3=0.12>0.1。

1.3 虚拟网络请求资源

在真实场景中，VN请求是动态地到达与离开，即VN请求并不是长期占有物理资源，而是其在生命周期内占用资源，在生命周期结束后释放所占用的物理资源。因此，某个时间内VN请求并未被成功分配资源，则会被放入缓存区等待下一时隙。

VN请求资源可以表示为(b,v,p,Lt,D)，其中,b表示基本资源请求BRR；v表示可变资源请求VRR；p表示可变请求发生的概率；Lt表示VN的生命周期；D表示VN可忍受的最大时延。

1.4 资源分配问题

ei=bi+pivi

(1)

因此，其为WPN带来的收益为

Rj(ei)=Rj(bi,vi,pi)=alog(1+bi+pivi)

(2)

则时隙资源j分配成功的VN请求所带来的收益为

s.t.

(3)

优化目标函数为

(4)

并使其满足

(5)

2 算法设计

根据上述问题的定义，所要优化的目标函数是一个NP难问题。对于解决NP难问题，已有很多学者提出了启发式或者贪婪算法去求优化解。文献[11]提出了一种启发式算法，但是并没有考虑到VN请求的到达与离去的动态性；同时也没有考虑由于动态性而导致的资源碎片化问题。为解决上述问题，本文提出了基于频谱资源共享的动态分配算法，其流程图如图2所示。

设计一个包含有2种类型的VN请求的缓存区：①前面时隙未被成功分配且在时延忍受范围内的VN；②当前时隙新到达的VN请求。在无线资源分配过程中，首先，将前面时隙的VN按照剩余生命时长大小排序，并优先分配剩余时长小的VN；其次是分配新到达的VN。为体现分配优先级，定义参数ε为

(6)

即在无线资源分配时，应优先考虑：①资源请求大的VN；②生命周期较短的VN。

针对以上2种类型的VN，分别按照相应优先准则进行排序。排序完成后，再将依序完成对VN的资源分配工作。对于任意VNi，首先为BRR分配资源，满足的话则进行VRR的分配，不满足就放入缓存区，在生命周期内都无法满足VN的请求资源，则拒绝该请求；VN分配结束后，再进行当前VRR的重分配过程。

图2 DAA-SRS算法流程图Fig.2 Algorithm flow chart for DAA-SRS

BRR资源分配的具体过程如下。

算法1BRR资源分配算法。

步骤1依据资源分配优先准则对缓存区中的虚拟网络进行排序；

步骤2判断当前时隙是否存在VN因生命周期到期而离开的现象。如果存在，则调用算法3；否则，进行步骤3；

步骤3从缓存区中取出待分配的VNi，并判断可用的频谱资源Rrem是否满足其BRR的请求；

步骤4若不满足，判断是否在其时延忍受范围内。是，则放入缓存区，否则拒绝该请求；

步骤5若满足，则调用算法2进行资源分配并判断是否满足VRR请求；满足则分配完成，不满足则进行步骤4。

3 VRR资源分配

BRR请求生命周期内必须垄断频谱资源，是无线网络虚拟资源分配必须满足的。下面着重介绍VRR请求的分配以及重分配过程，主要包括碰撞概率、子信道分配以及子信道的重分配。

3.1 计算碰撞概率

(7)

(8)

(7)—(8)式中：Sm表示第m条共享子信道；Prno(Sm),Prone(Sm)分别表示第m条共享物理信道没有信道共享和只有一条信道共享时的概率。

当有新的VN到来，且其VRR的发生概率为pi，则该VN的碰撞概率计算公式为

(9)

实际使用过程中，不需要重复上面的计算过程，只需要保存每条共享物理信道上的Prno,Prone即可。当有新的VN时，更新碰撞概率为

(10)

(11)

然后根据 (9) 式计算出碰撞概率大小并和阈值pth进行比较。

3.2 子信道分配

通过计算当前VN与各条共享物理子信道的碰撞概率，统计碰撞概率小于pth的信道作为VRR的候选子信道集合BCH。

(12)

先统计候选子信道的数量nBCH，然后为当前VN的VRR分配子信道，分配情况有如下几种。

1)nBCH≥vi表示VRR请求的频谱资源量小于当前满足条件的共享子信道数量；

此时，应优选出剩余资源量大的vi条共享子信道进行分配。定义crem表示共享子信道的剩余资源量。假设新到VN的VRR发生概率为pnew，则单条子信道剩余资源量可以用该VN的碰撞概率恰好等于阈值pth来进行。

(13)

可以解出

(14)

进而得出

crem=pnew

(15)

再根据crem将候选信道按降序排列，取出最大的vi条共享子信道进行分配。

2)nBCH

3)nBCHRrem-bi，表示共享子信道和剩余空闲子信道均无法满足VRR请求量，无线物理网络无法满足VNi，则将其放入缓存区。

3.3 VRR资源分配算法

结合碰撞概率和子信道分配2个方面，提出一种VRR资源分配算法，该算法主要是根据碰撞概率选出能够分配资源的子信道，再将子信道分配给VN，并更新子信道的碰撞概率，其具体的算法流程如算法2所示。

算法2VRR资源分配算法。

步骤1根据所要分配VRR的发生概率pi，并依次与当前所有的共享子信道计算其碰撞概率；

步骤2统计步骤1中碰撞概率不大于阈值pth的共享子信道集合BCH；

步骤3根据步骤2中BCH得出满足的子信道数量并与VRR请求量进行比较，完成分配；

步骤4根据步骤3中的分配结果，更新对应共享子信道的碰撞概率Prno(Sm),Prone(Sm)。

3.4 VRR重分配算法

由于VN请求到达和离开的动态性，造成频谱资源出现碎片化，使得频谱资源没有得到充分利用。针对这种情况，提出VRR请求的重分配思想并给出具体步骤。

另外由于生命周期的存在，同一时隙有新的VN到达，也有VN离开，导致共享子信道内出现资源空闲，不同的VN占用不同的子信道，新的VN可能因为碰撞概率大于阈值，导致VRR资源得不到满足而遭到拒绝，为了避免这种情况，提出VRR重分配算法，当VN离开物理网络时，在满足碰撞概率的前提下，将分散在多个子信道的VN请求融合在同一个子信道内，这样就能空余更多的子信道供新的VN请求占用。VRR重分配算法如下。

算法3VRR重分配算法。

接到分手电话的时候，我正窝在家里上淘宝。小健说，他们家是地道的本地人，本来就不同意我们在一起。现在我没有工作又不上进，他很难再坚持。大家都是成年人，应该考虑现实问题，所以，分开比较好。

步骤1根据当前共享子信道的情况，统计其数量并按照生成顺序编号为1,2,…,N;

步骤2按照编号从大到小遍历共享子信道，并对所遍历的子信道优先选择其上发生概率最大的VRR进行重分配；

步骤3将步骤2中选择出的VRR与其所在子信道编号之前的子信道依次计算碰撞概率；

步骤4判断是否存在满足碰撞概率不大于阈值pth的共享子信道。若有，进入步骤5;若无，进入步骤2遍历下一个共享子信道；

步骤5在所满足碰撞阈值pth的共享子信道集合中，找出使得碰撞概率最小的子信道做为VRR重分配后的共享子信道；

步骤6判断是否遍历完所有的共享子信道。是，则停止重分配；否则进行步骤2。

4 仿真及分析

4.1 场景设置

利用MATLAB工具验证所提算法的有效性。分别从以下方面进行分析：①一般分配算法(即无频谱共享机制)与频谱共享算法在占用信道数量方面的对比，验证频谱共享的有效性；②不同碰撞阈值对所占信道数量的对比，判断设置阈值的合理性；③在考虑VN请求动态性的条件下，分析其接受率性能。

4.2 仿真结果及性能分析

由于VN的BRR部分是垄断物理资源，因此该实验过程仅考虑VN的VRR部分的分配。在仿真过程中[11]，一般假设物理网络的总信道数C=600，碰撞阈值pth=0.1，单个VN的可变资源请求VRR服从(5,Vmax)的均匀分布，VN所能允许的最大分配时延D=2，VN的到达过程建模为一个服从参数为λ的泊松分布过程，VN的生命周期服从参数为μ的指数分布，且λ=5,μ=10。本实验取了200次运行结果的算术平均值。

4.2.1 频谱共享算法有效性

图3分析不同VN的数量与平均占用信道数量(即消耗的频谱资源)之间关系。其中VRR发生概率服从(0.1,0.2)的均匀分布，Vmax=10。可以发现，随着VN的数量增多，其相应占用的物理信道数量均呈线性增长。一般分配算法在不同VN数量请求下，其占用的信道数量远高于具有共享机制的算法，这是因为没有共享机制，每个VN的VRR请求就会垄断频谱资源，即请求多少就分配多少，不管其是否真实使用；而共享机制允许不同VNs的VRR机会性地共享相同的物理信道，这样同样情况下其真实占用的物理信道数量会显著减少。

图3 pi∈(0.1,0.2)时，平均占用信道数vs虚拟网络数量Fig.3 Average occupied channel number vs number of virtual networks with pi∈(0.1,0.2)

为了验证VRR发生概率的不同对占用信道数量的影响，图4仿真了VRR发生概率服从(0.2,0.3)的均匀分布，Vmax=10时，不同VN的数量与平均占用信道数量(即消耗的频谱资源)之间关系。从图4可以看出，所述频谱共享算法占用的信道数量同样比一般算法低。对比图3和图4，可以发现同样数量的VN，VRR发生概率大则占用的信道数量会高于概率小的，这是因为在概率较小时，在碰撞阈值的约束下，单条物理信道允许共享的VN数量将会增多，相应同样数量的VNs占用的物理信道的数量会更少。但是无论发生概率大或者小，采用频谱共享算法后，频谱共享机制都会降低VN占用的物理信道量，从而提高其网络收益。

4.2.2 阈值设置的合理性

图5仿真了单个VN的VRR的最大值Vmax的变化与占用信道数量的情况。其中，VRR发生概率服从(0.1,0.2)的均匀分布，VNNumber=50。由图5可以看到，随着Vmax的增大，VNs对应占用物理信道的数量随之增长。一般分配算法在Vmax≥25就不会随着Vmax的增大而变化，这是因为此时的物理信道已经被占用完，其占用的物理信道数量稳定在600，即信道总数；而频谱共享算法，其占用物理信道的数量呈线性增长，表明相同的Vmax下其占用的数量要少于一般分配算法，并且能接受更大Vmax的VN，从而会为WPN带来更高的网络收益。

图4 pi∈(0.2,0.3)时，平均占用信道数量vs虚拟网络数量Fig.4 Average occupied channel quantity vs number of virtual networks with pi∈(0.2,0.3)

图5 pi∈(0.1,0.2)时，平均占用信道数vs VRR的VmaxFig.5 While pi∈(0.1,0.2) average occupied channel quantity vs Vmax of VRR

图6仿真了VRR发生概率服从(0.2,0.3)的均匀分布时，Vmax的变化与平均占用信道数量的关系。从图6中可以看出，随着Vmax的增大，占用信道的数量也在增加，最终当Vmax=50时，占用了600的信道数量，这是因为VRR发生的概率增大后，相同数量的VN占用信道数量就更多，所以与VRR发生概率小的时候比起来，则占用的信道就变多。但是在整个仿真过程，占用的信道数都是低于一般分配算法，说明当VRR发生概率较大时，频谱共享算法依然能够在Vmax不够大时占用更少的信道数。

4.2.3 VN请求动态性时的接受率

下面仿真中，DAA-SRS算法基本假设和前提：VN的到达过程服从参数为λ的泊松分布过程，VN的生命周期服从参数为μ的指数分布，且λ=5,μ=10。VNs允许的最大映射时延D=2，物理网络的总信道数C=600，碰撞阈值pth=0.1，收益系数a=1。基本资源请求BRR和可变资源请求VRR均服从(5,15)的均匀分布，可变资源请求发生概率服从(0.1,0.3)的均匀分布。

图6 pi∈(0.2,0.3)时，平均占用信道数vs VRR的VmaxFig.6 While pi∈(0.2,0.3) average occupied channel quantity vs Vmax of VRR

图7是DAA-SRS算法与文献[11]中Heuristic算法和一般分配算法在虚拟网络接受率上的比较。从图7可以发现，分配初期频谱资源较为充足，因此接受率相差不大。随着时间的推移，频谱资源被逐渐占用，接受率随之下降，并趋于稳定。基于频谱资源共享机制的2种算法在接受率上要高于一般分配算法，而DAA-SRS算法又明显高于Heuristic算法。这是因为基于频谱资源共享的机制，使得相同数量的VNs占用更少的物理信道，有更多的物理资源可以接受后续VNs。而DAA-SRS算法在VNs生命周期的结束而离去时，进行有效的资源重分配，使得占用的信道数量相比于文献[11]的算法更少。

图7 VN接受率的变化Fig.7 Change in VN acceptance rate

图8给出了3种算法在网络收益方面的比较。所述网络收益是该时隙内物理网络中正在接受服务的所有虚拟网络带来的收益。可以看到，DAA-SRS算法在网络收益方面要优于其他2种算法。结合图7和图8可以看出，较高的虚拟网络接受率与较高的网络收益趋势一致。DAA-SRS算法在接受率和收益方面均是最优的。

图9给出了不同到达率对接受率的影响，由图9可知，虚拟网络的接受率随着λ的增大而降低。DAA-SRS算法的接受率相较于其他2种算法有显著提高。可以预见，在针对较大规模数量的VN时，DAA-SRS算法仍然会获得比较高的接受率，这得益于该算法模型充分考虑了动态性、时变性和重分配的机制。DAA-SRS算法不仅能够充分利用物理网络资源，而且使得无线网络负载更加均衡。

5 结束语

本文针对虚拟网络请求的动态性以及时变性，在考虑了网络动态性导致物理资源出现碎片化或负载不均的情况下，提出了一种基于频谱资源共享的动态分配算法DAA-SRS。对虚拟网络请求的时变性进行了分析，并建立了请求资源的模型；并根据虚拟网络请求和物理资源的限制条件，建立了最大化网络收益的目标函数；最后，针对频谱资源共享机制中存在的碰撞问题进行了较为详细的讨论，给出了可行的更新方式，即根据虚拟请求的动态性，实时调整VRR资源映射。仿真结果表明，DAA-SRS算法在虚拟网络接受率和物理网络收益方面具有较优性能。

参考文献：

[1] YANG M, LI Y, ZENG L, et al. Karnaugh-map like online embeddingalgorithm of wireless virtualization[C]∥International Symposium on Wireless Personal Multimedia Communications. [S.l.]: IEEE Press, 2012:594-598.

[2] BELT Van de J, AHMADI H, DOYLE L E. A Dynamic Embedding Algorithm for Wireless Network Virtualization[C]∥Vehicular Technology Conference. Vancouver, BC, Canada: IEEE Press, 2015:1-6.

[3] FU F, KOZAT U C. Stochastic game for wireless network virtualization[J]. IEEE/ACM Transactions on Networking, 2013, 21(1):84-97.

[4] PARSAEEFARD S, JUMBA V, DERAKHSHANI M, et al. Joint resource provisioning and admission control in wireless virtualized networks[C]∥Wireless Communications and NETWORKING Conference. New Orleans, LA, USA: IEEE Press, 2015:2020-2025.

[5] ZHU Q, ZHANG X. Bayesian-game based power and spectrum virtualization for maximizing spectrum efficiency over mobile cloud-computing wireless networks[C]∥Computer Communications Workshops. [S.l.]: IEEE Press, 2015:1-6.

[6] YUN D, YI Y. Virtual network embedding in wireless multihop networks[C]∥International Conference on Future Internet Technologies. New York, NY, USA： ACM, 2011:30-33.

[7] 刘川川. 无线网络虚拟化中资源分配算法研究[D]. 长沙：湖南大学, 2013.

LIUChuanchuan. Research in Resource Allocation Algorithm in Wireless Network Virtualization[D]. Changsha, China: Hunan University, 2013.

[8] YUN D, OK J, SHIN B, et al. Embedding of Virtual Network Requests over Static Wireless Multihop Networks[J]. Computer Networks, 2013, 57(5):1139-1152.

[9] ABDELWAHAB S, HAMDAOUI B, GUIZANI M, et al. Efficient Virtual Network Embedding With Backtrack Avoidance for Dynamic Wireless Networks[J]. IEEE Transactions on Wireless Communications, 2016, 15(4):2669-2683.

[10] YANG M, LI Y, LIU J, et al. Opportunistic spectrum sharing for wireless virtualization[C]∥Wireless Communications and Networking Conference. Istanbul, Turkey: IEEE Press, 2014:1803-1808.

[11] YANG M, LI Y, JIN D, et al. Opportunistic Spectrum Sharing Based Resource Allocation for Wireless Virtualization[C]∥International Conference on Innovative Mobile & Internet Services in Ubiquitous Computing. Taichung, Taiwan, China: IEEE Press, 2013:51-58.