佳木斯大学学报(自然科学版)Vol. 38 No. 6Nov. 2020
第38卷第6期2020 年11月Journal of Jiamusi University ( Natural Science Edition )文章编号;1008 -1402(2020 )06 -0127 -03
翟月
(安徽电子信息职业技术学院软件学院,安徽蚌埠233000)
摘 要:为了提高5G 网络的服务质量,设计了一个分布式的缓存优化算法。首先,以实现网 络总成本最小化为目标,建立联合优化的数学规划问题。然后,基于数学分解的方法,将联合优 化问题分解为缓存和路由两个子问题,并设计分布式算法进行求解。最后,采用仿真实验验证本 优化算法的性能。实验结果表明,与现有的方法相比,本算法能够获得更好的性能。 关键词:5G ;数据卸载;分布式缓存
中图分类号:TP391
文献标识码:A
0引言
诸如智能电话等移动设备的爆炸性增长产生
了巨大的网络流量,据估计,到2022年,全球的移 动数据流量将增长到每月77 EB,其中智能设备和 连接的份额将增加到73%[I ]。5G 无线网络能为
移动用户更好的服务质量,并具有更高的带宽、更 大的天线规模以及更高效的频率复用等特点。预 计其传输速度将比4G 快20倍左右,并且延迟可 能下降到个位数毫秒,几乎无法检测到滞后时
间[2]。缓存技术是5G 的关键技术之一,将数据内
容缓存到距离用户更近的能够有效降低网络
延迟。因此,为了提高5G 网络的性能,本研究结
合考虑路由算法,设计分布式缓存优化算法。
1问题建模
1.1系统模型
考虑一个由N 个小型和M 套移动用户组 成的5G 无线网络。在每个时间间隔t e {1,2,…, 口,缓存策略和路由策略可以更新。令N = {1, …,N}和M = {1,-,M}分别表示小型集和用 户集。用户集合m 与小型n 之间的连通性被表 示为k nm , k nm - 1说明则用户集m 在小型n 的 服务范围内;否则,k nm =0。用集合F - {1,..., F}表示内容集合,每个内容的大小都是相同的。
来自用户的请求可以由覆盖区域中的小型基 站或大型来服务。在时间t ,用户集合m 对内 容/的请求由心,f 表示。对于用户的请求,最好由 小型进行服务响应,而不是由大型服务。 这是因为小型和用户之间的等待时间短且服 务成本低,同时可以减少回传链路的网络拥塞。
每个小型的缓存策略和路由策略会在每
个时隙t 进行更新,以最小化服务来自所有用户的 请求的成本。缓存策略用变量屮=(X ) t e 表示,
其中H =(心)”十。心的取值是0或者1。心 取值为1时,表明小型n 在时隙t 中缓存有内 容/ ;否则,x n f 取值为0。
路由策略用变量Y T = (F )t e 表示,其中F =
(y n ,m ,f
)
n e,f e
拓m e M 。y n ,m ,f 表
示在时隙t 小型n 服务的用户集合m 中请求 内容/的比例。
显然,每个小型n 不能缓存超出其容量的 数据,即,
Z £C ” (1)
直埋蒸汽管道fe
歹
其中,C n 是小型n 存储容量。
同样,从小型到用户的总流量受带宽容量 B ”的限制,即,
ZZ 代“爲
(2)
fe F m e M
缓存策略和路由策略紧密结合在一起:只有在 小型已经缓存了所请求的内容,否则小型 无法提供请求的内容。缓存策略和路由策略之间
① 收稿日期:2020 - 10 -27
基金项目:2018年安徽省质量工程教学研究项目(2018jyxm0915)。
作者简介:翟月(1980 -),女,安徽砀山人,讲师,硕士,研究方向:计算机。
128佳木斯大学学报(自然科学版)2020年
的这种相互依赖关系由以下约束描述:
y;,m,/W(3)
1.2网络成本函数
目标是通过确定每个小型的缓存和路由
策略,最大程度地降低服务用户的总运营成本。为
了捕获位置多样性和服务成本随时间的变化,让
g t(•)表示小型的服务成本。对于每个小型
n,服务成本由用户的位置、请求的数量以及
所请求内容的服务部分来确定。
覆盖用户集合m的大型和小型接收
从用户集合m发送的关于内容/的请求。大型基
站以集中的方式收集网络的全局信息,确定每个小
型缓存和路由策略,以最大程度地降低网络的
总运营成本。如果内容/被缓存在某些小型
中,则小型可以将内容直接发送到用户。不同
的小型所传输内容的比例由大型控制。
如果内容未在小型中缓存或小型带宽资
源有限,则请求将由大型服务。
对于每一个t,假设g t(•)是关于y;,m/的连
续、可微、严格增的凸函数。使用传输权重参数
心M0来描述用户位置的影响。
成本函数g t(•)的表达式如下所示
g t( Y t)=£££"nmYn,m,/k nm A m,f(4)
m e Mf e F n e N
让f t(•)表示大型服务于来自用户请求
的成本。ft(•)是服务用户请求的成本总和、由用
户的位置、来自用户的请求数量以及小型的路
由策略确定。大型和用户之间的传输参数权
重可以表示为』m。边缘中的小型比大型
更接近用户,因此九远小于』m。小型将首
先服务来自用户的请求,以降低网络的总运营成
本。但是,由于带宽限制和存储容量限制,小型基
站可能无法满足来自用户的所有请求。大型
可以将请求内容的其剩余部分提供给用户。
f t(Y)的表达式如下所示:
ft(Y)=£dm£(1-£代八(5) m e?/e? n e
缓存替换成本捕获了小型中内容替换所产生的能耗和金钱成本。在时隙t,从用户接收到请求后,小型更新缓存策略,从大型获取新内容,并删除需要替换的内容。从时隙t-1到t 的小型的缓存替换成本为
h(X t,X t-1)=££(Cz忒;)+(6)
火炬点火装置n e N f e F
其中是在缓存替换期间产生的成本。1.3联合优化问题
通过确定时间范围T内每个小型的缓存策略和路由策略来最大程度地降低网络的总运营成本,该问题具有如下所示的表达式:
min£(化(Y)+g t(Y)+h(X,X t-1))
t e T
s-1.£w c”
feF
££y;,m,f A"m,f W B n
fe F m e M
y n,m,f W X n,f
£y…,m,f k…m W1(7)
n e N
双端面机械密封2分布式算法设计
假设大型能够决定所有小型的缓存和路由策略。优化问题(7)是一个混合整数规划问题。为了求解该问题,首先提出了一种拉格朗日松弛方法[3],将原始问题解耦为两个的子问题;然后,将离散变量x n f连续化。
目标函数可以分为两个部分,这两个部分分别只包含缓存变量和路由变量y;,m,/。在优化问题的约束条件中,除了约束(3)之外,其他约束条件均只包含变量心或者y;,”/。引入拉格朗日乘数,对约束(3)进行松弛,并得到以下的拉格朗日函数:
L(X n,f,y n,m,f,“”,m/)=
£(/t(Y)+g t(Y)+h(X,X t-1))+
t e T
££££Mlm,(『Im,-/”,/)(8)
n e N m e M fe F t e T
原问题(7)的对偶问题如下所示:
m严min L(心乩m,“爲)
<[L M0(9)将原始问题分解为以下两个子问题:
P1(x):min£(h(X,,X,~')一£££产;/)
t e T n e N m e M fe F
<£x
;,/w c;(10)
f e F
P2(y):min£(f t(Y)+g t(Y)+
e T
£££L”,mif y n,m,f)
n e N m e M f e F
<££y:,m,/A m,/W B n£y n,m,/k”m W1
f e F m e M n e N
(11)
子问题P,x)仅包含缓存变量x nJ,P,x)是缓存子问题。P,x)可以进一步分解为N个独立的子问题。同样,子问题P;(y)仅包含路由变量y:,m,/,P2(y)是路由子问题。P2(y)也可以分解为
第6期
翟 月:面向数据卸载的5G 分布式缓存优化研究129
N 个独立的子冋题。
通过引入拉格朗日乘子对问题进行分解后,提 出了一种对偶算法来解决该问题。对于每次迭代
I ,子问题巴(X )和P 2(y )可以并行地进行。
X ;,/是一个离散型变量,因此需要将其松弛为
连续型变量,即X n j e [0,1]。在松弛之后,子问
题P,x )是线性规划问题,因此可以通过单纯形 法进行求解。子问题P 2(y )的目标函数是连续的 凸函数,其约束条件也是凸函数。因此,路由子问 题可以通过凸优化技术来解决⑷。
内外牙对于对偶问题,采用次梯度方法进行求解。用
g ;,爲表示次梯度,即g ;,爲=X \j - y n ,m ,f 。5’是更新 的步长,该步长的计算方式如下:81 = 1 /I + al ,其 中a 是控制步长的参数。
3实验评估
实验采用的内容集合是从互联网获取的真实
数据集,数据集中一共记录了 50种内容,并记录了
每种内容的随时间变化的请求次数。实验所使用
的网络拓扑中含有一个大型,小型的数量 为3o 在小型和用户之间随机选择40条链 路,以确保每个用户至少连接一个小型。传输 权重参数d nm 为1, d m 服从[80,100]的均匀分布。 参数仔的值设置为100o 将本分布式算法与最近 最少使用(LRU )算法⑸。LRU 是经典的缓存替换 算法,该算法选择最近最久未使用的内容予以淘汰。
灌浆剂•本文算法f-LRU
20
25
30 35
40
MU 数量
O 00O O H
X
-H
径映
图1用户数量对成本的影响
首先探讨网络拓扑对算法性能的影响。通过 改变用户的数量来改变网络拓扑结构,实验结果如 图1所
示。当用户的数量增加时,网络的成本会增 加。这是由于用户越多,服务用户的网络运营商就 会越多。由结果可知,提出的算法的性能仍然明显
优于 LRU 。
接下来,探讨小型的缓存容量和带宽对算 法性能的影响。在图2中,当小型的存储容量 增加时,网络的总运营成本会稍微下降一点。图3 展示了带宽的影响,当带宽容量从500增加到 2000时,总运营成本最多可节省约60%。
o o o c m
x
图2小型缓存容量对成本的影响
O O O O O t X
<;荒膜
-•-本文算法—LRU
500
750
1000 1250 1500
图3带宽对成本的影响
内外网切换器4结论
研究首先建立了缓存和路由的联合优化模型,
然后通过求解该模型设计分布式的缓存算法。最 后采用对比实验对算法的性能进行评估,结果表明 本算法具有一定的有效性。为了适应网络环境的 动态变化,在未来的工作中,将设计动态的实时缓 存算法,进一步降低网络的成本。
参考文献:
[1]
Liu Y , Qin Z , Elkashlan M , et al. Nonorthogonal Multiple Access for 5G and Beyond [ J ].
Proceedings of the IEEE , 2019 ,
105(12) :2347 -2381.
[2] Wei Z , Yang L , Ng D W K , et al. On the Performance Gain of NOMA Over OMA in Uplink Communication Systems [ J]. IEEE Transactions on Communications , 2020, 68 ( 1 ): 536 一
568.
[3 ] Chiang M , Tan C W , Palomar D P , et al. Power Control By
Geometric Programming [ J]. IEEE Transactions on Wireless
Communications , 2017,6(7) :2640 -2651.[4]
Alaviani S S , Elia N . Distributed Multiagent Convex Optimiza tion Over Random Digraphs [J]. IEEE Transactions on Automat ic Control, 2020, 65(3) :986 -998.
[5] Zhong C , Gursoy M C , Velipasalar S . Deep Reinforcement
Learning 一 Based Edge Caching in Wireless Networks [J]. IEEE Transactions on Cognitive Communications and Networking , 2020, 6(1) :48 -61.
(下转148页
)
148佳木斯大学学报(自然科学版)2020年
从表1中的模拟结果可以看出,对于不同的参数以及不同的样本量,参数估计的均方误差都相对较小,并且误差也比较稳定,说明所给出的估计方法能够对未知参数给出较为精确的估计.
3结论
研究了具有缺失数据的混合泊松分布总体参数的估计问题。利用矩估计给出了未知参数的估计,同时考虑了估计的极限性质。也通过模拟分析计算了估计的均方误差,根据模拟结果可知,的估计有较小的均方误差,说明我们的估计方法具有可行性.
参考文献:
[1]赵志文,杨慧超,何静花.具有缺失数据的两个幕分布总体
参数的矩估计与检验[J].吉林师范大学学报:自然科学版,
2016,37(2):62-67.[2]李阳,杨艳秋,王秋爽,等.具有部分缺失数据混合指数分
布参数的估计[J].白城师范学院学报,2018(08):10-15.
[3]刘银萍.具有部分缺失数据时两个Poisson总体的估计和检
验[J].大学数学,2002,18(6):82-86.
[4]刘银萍,马晓悦,赵志文.缺失数据场合泊松分布参数的贝叶
斯估计[J].吉林师范大学学报(自然科学版),2012(03):18
-20+24.
[5]夏元睿,吴俊,叶冬青.泊松分布与概率论的发展一一西蒙•
丹尼尔-泊松[J].中华疾病控制杂志,2019,023(007):881-884.
[6]于子涵.泊松分布与复合泊松分布的性质[J].神州(上旬
刊),2019,000(001):212-213.
[7]何朝兵,杜保建,刘华文.带有不完全信息随机截尾试验下混
合泊松分布参数的点估计[J].数学的实践与认识,2016, 44(12):187-195.
[8]隋崴,李树有,宓影.双变量泊松分布参数的极大似然估计
[J].辽宁工业大学学报(自然科学版),2019,39(01):4-8
+19.
Parameter Estimation of Mixed Poisson Distribution with Missing Data
YANG Hang,YANG Yan一qiu*,YU Xin一long
(College of Mathematics,Jilin Normal University,Siping Jilin136000,China)
Abstract:The parameter estimation and hypothesis testing of mixed Poisson distribution with missing data are studied.The asymptotic normality and consistency of the moment estimators are proved.Moreover,the feasibility of the method is verified by random simulation.
Key words:mixed Poisson distribution;missing data;moment estimation
(上接129页)
Optimization of5G Distributed Caching Algorithm for Data Offloading
ZHAI Yue
(College of Software,Anhui Vocational College of Electronics and Information Technology,Bengbu Anhui233000,China) Abstract:In order to improve the service quality of5G network,this paper designs a distributed cache optimization algorithm.First of all,with the goal of minimizing the total network cost,a mathematical programming problem of joint optimization is established.Then,based on the mathematical decomposition method,the joint optimization problem is decomposed into two sub-problems of caching and routing,and a distributed algorithm is designed to solve it.Finally,the performance of the optimization algorithm is verified by simulation experiments.Experimental results show that compared with the existing methods,the algorithm in this paper can achieve better performance.
Key words:5G;data offloading;distributed caching