⃝⃝可在www.sciencedirect.com上在线获取ScienceDirectICT Express 3（2017）33www.elsevier.com/locate/icte用于移动数据卸载的多流管理Yeongjin Kima，Joohyun Leeb，Jiang，Jaeseong Jeongc，Song Chongaa大韩民国大田韩国科学技术高等研究院电气工程学院b美国俄亥俄州立大学电气与计算机工程系c爱立信研究所，瑞典接收日期：2016年7月25日;接收日期：2016年8月27日;接受日期：2016年8月29日2016年9月9日摘要由于智能设备和流量密集型应用的激增，蜂窝网络正面临着移动数据流量的爆炸性增长作为一种具有成本效益的解决方案，延迟Wi-Fi卸载被引入，通过交换额外的延迟将延迟容忍流量从蜂窝网络转移到Wi-Fi网络本文研究了多流速率控制问题，其中每个流具有不同的流量负载和截止时间。为了最大限度地提高用户满意度定义为卸载效率减去负效用所造成的最后期限违规，我们提出了一种基于动态规划的速率控制算法。此外，为了减少计算量和内存，我们提出了一个简单的基于阈值的速率控制算法。c2016韩国通信信息科学研究所。出版社：Elsevier B.V.这是一篇开放获取的文章，CC BY-NC-ND许可证（http：//creativecommons. org/licenses/by-nc-nd/4. 0/）。关键词：延迟Wi-Fi卸载;多流管理;移动数据卸载1. 介绍随着配备有高处理能力和多样化应用的智能设备变得流行，移动数据流量在蜂窝网络中呈指数级增长。思科报告称，过去几年移动数据流量呈指数级增长，并预测2013年至2017年全球移动数据流量总量将增长7倍。业务是具有高清（HD）分辨率的视频内容。这一趋势导致退化*通讯作者。电子邮件地址：osu.edu（J. Lee）。同行评审由韩国通信信息科学研究所负责。本文的会议版本在ICOIN2016上发表，KotaKinabalu，Malaysia，Jan. 15，2016（Kim et al. 2016）[1].这项工作得到了韩国政府（MSIP）资助的信息通信技术促进研究所（IITP）的资助（B 0190 -16-2017，基于物联网设备的物理性，关系和服务语义的弹性/容错自主网络）。这篇论文已经处理教授。金承林在用户体验方面，例如蜂窝数据传输的大量延迟和此外，对于蜂窝数据使用的支付负担也由于蜂窝网络中的移动用户饱和而增加。Wi-Fi卸载是大幅减少蜂窝数据业务的有效解决方案，并且它对于蜂窝网络提供商和移动用户具有若干优点：（i）可以以比蜂窝基站更低的成本部署Wi-Fi，并且Wi-FiAP已经在大多数休闲空间（诸如工作场所和家庭）中分布，例如，全球部署了2.7亿个AP(ii) Wi-Fi接口要求每比特的低传输能量，仅为3G接口的5%[2]，因为Wi-Fi具有高数据速率和短距离内的低通信功率(iii) 移动用户能够通过Wi-Fi网络以较低（或几乎为零）的货币成本享受互联网接入。尽管Wi-Fi具有许多优点，但它具有一个严重的缺点;由于短的通信距离和未计划的部署，Wi-Fi连接是间歇性的，这取决于移动用户的移动模式为了弥补这一限制，引入了延迟Wi-Fi卸载[3]，http://dx.doi.org/10.1016/j.icte.2016.08.0112405-9595/c2016韩国通信信息科学研究所。Elsevier B. V.的出版服务。这是CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4. 0/）。34Y. Kim等人/ICT Express 3（2017）33=+=一∈I|∈L+|∈T∈L={}==∈F=[]=（|，）=t不不不不=T={}∈ I={}i≤ ≤ · ·· ≤我=延迟容忍1应用程序在连接Wi-Fi之前暂停数据传输与现场卸载相比，它使移动用户能够抓住更多的Wi-Fi机会[3]。根据一项关于移动用户在几种类型的应用程序下的延迟容忍度的调查[4]，一旦支持适当的激励措施，用户可以容忍软件更新、云备份和内容下载应用程序的长延迟（几分钟或几小时）这些应用程序比实时应用程序（如Web浏览、消息和电子邮件）产生更大的数据流量。在实践中，存在利用延迟Wi-Fi卸载的若干移动应用，诸如用于云存储的Dropbox和用于VOD（视频点播）服务的hoppin然而，移动用户不能整天等待Wi-Fi操作而没有未来Wi-Fi联系的任何保证。因此，当Wi-Fi不可用时，是否使用蜂窝链路是重要的如果移动终端服务于多个流，其中每个流需要不同的业务量和最后期限，则这变得由于流共享蜂窝和Wi-Fi网络资源，一些流可能在它们自己的期限内没有完成。它降低了满意度的移动用户由于额外的传输时间后的最后期限。因此，多流速率控制算法应当在卸载效率2和由截止期限违反引起的负效用之间平衡。现有的研究主要集中在单流管理或多流的情况下，没有指定的期限。在本文中，我们制定了多流率控制问题作为一个有限时域和离散马尔可夫决策问题。目标是最大化用户满意度，用户满意度由卸载效率减去截止日期后未完成的流量所造成的负效用组成。我们专注于下载情况，因为大多数移动数据是下载流量，3但我们的结果可以很容易地扩展到上传情况。然后，我们提出了两种速率控制算法，并评估他们的基础上跟踪驱动的模拟。2. 该算法在本节中，我们设计了一个延迟的Wi-Fi卸载系统，当多个流共存时，它们有自己的流量负载和截止日期。我们制定了一个优化问题，以最大限度地提高用户满意度，这是一个总的数据流量卸载通过Wi-Fi减去负效用造成的死线违规。该公式基于[6]中的有限时域和离散马尔可夫决策问题，该问题解决了单流情况下的开/关问题。然后，我们提出了两种多流量控制算法：（i）基于动态规划的优化算法和（ii）基于阈值的启发式算法。1 它们没有瞬时延迟约束。2 通过Wi-Fi网络传输的数据流量3 在蜂窝网络中，下载流量大约是上传流量的6倍[5]。2.1. 系统模型流和网络模型。我们考虑一个场景，移动用户保留M个下载流，其中每个流由i1，2，. . .，m.每个流i必须完全传输，直到用户为其分配的最后期限T。我们记为T（T1，T2，. . .，T m）流集合的截止时间的向量，它是按升序排列的(i.e.、T1T2Tm）。我们对时隙系统t1，2，. . . .，T m，并且在每个时隙t，流i的剩余文件大小由fi表示，其中fi（f1，f2，. . .，f m）。f1是初始文件大小向量，当t1和ft0，f1，对于所有的t。我 们用lt表示时间t的网络状态c，w，其中l，tc和l tw分别表示蜂窝和Wi-Fi网络。 在这项工作中，在异构网络中的网络接口选择是我们的范围之外，我们假设移动终端连接Wi-Fi网络，只要它是可能的。我们将网络状态随时间的转变建模为2状态马尔可夫链4，其中0p（ lt+1lt） 1，对于所有lt， lt1。<我们将网络状态l的数据速率表示为rl。为了简单起见，我们假设蜂窝和Wi-Fi网络的数据速率与时间和位置无关状态转换模型。 我们将时间t st（ft，l t）处的系统状态定义为剩余文件大小向量和网络状态的元组。ST1仅取决于先前状态ST1和动作AT。a（a1，a2，. . . A i，A m）被定义为速率控制向量（称为动作向量），其中A i表示在1个时隙期间流i的分配数据速率。我们定义t（f，l）为给定状态s在时间t的可行动作向量集。定义1（可行动作向量集）。 对于所有速率控制动作向量a ∈ At（f，l），它满足：ai≤rl，（1）i∈I0≤a≤f，（2）ai=0，ai s. t. <（3）第一次见面。其中（1）表示所有流的速率总和在当前网络容量内;（2）表示流i的速率不能超过所有i的剩余文件大小 fi（三） 意味着不能激活截止期限已经到期的流。我们用pt（s′s，a）表示当在时间t施加动作a时系统从状态s到s′的状态转移概率。由于网络状态转移是时间无关和动作无关的，因此概率可以分解为两个p t（s′|s，a）= p t（（f ′，l′）|（f，l），a）= p（l′|l）p t（f ′|f，a），其中p ff a1，如果f ′fa，0，否则。4 这是Wi-Fi接触和相互接触的泊松过程的离散版本Y. Kim等人/ICT Express 3（2017）3335不不=+[客户端]∈A∈L∈T==F∈+==+[正][正]=−+∈A（ft[详细]S不不不 +1个不不2.2. 问题定义我们将数据量表示为g（ l，a） =la ll=w，在时间t的系统状态（f，l）的最佳动作可以写为如下。δπ∈（f，l）=argmax{t（f，l，a）}，f∈F，l∈L，t∈T，（6）对于给定的网络状态l和t，作用矢量;作用向量当所有流的截止日期到期时a∈A(i.e.、t=Tm+1），系统状态为s，定义用户负效用函数为cTm+1（s）.c Tm +1（s）= c Tm +1（f，l）= c（f）.负效用仅取决于未完成的文件大小向量f，这降低了用户满意度，因为在截止日期之后会产生它是f的非减函数，用户依赖函数对应于对附加延迟的敏感性。此外，当所有流在其截止日期内完成时（c（0）0），不存在负效用。我们 将用户的 策略表示 为π（δ π （f， l），F，l，t）的。该策略包括针对所有状态s和时间t的动作，其中δπ（f，l）t（f，l）和π- 是的然后，我们的目标是最大化预期满意度（即，在1期间通过Wi-Fi传送的总数据量，Tm减去由在t Tm处的最后期限违反引起的负效用1），通过如下控制速率控制策略π。Tm其中（4）和（6）可以通过逆向归纳来计算。它们是从边界时间t开始递归计算Tm1到初始时间t1。 我们基于DP的算法的最优性可以通过以下pp导出。83在[7]中，由于空间限制，此处省略。然后，我们的基于DP的速率控制算法可以描述如下。maxEπgt（lt，δπ（sπ））−c（sπm），其中sπ=（fπ，lt）是策略π为在系统中应用。2.3. 动态规划算法我们推导出一个最优的多流速率控制算法，使用动态规划（DP）框架。我们定义为vt（s）的最大预期的用户满意度期间的间隔t， Tm1为一个给定的状态s之前，在时间t的速率控制。vt（s）=amax，l）{t（f，l，a）}，（4）其中t（f，l，a）是在对于给定的状态s，在时间t， Tm1处应用动作a，t定义如下。（f，l，a）= g（l，a）+pt（（f ′，l′）|（f，l），a）vt+1（f ′，l′）l′∈Lf′∈F=a1I（l= 1）+p（l′|l）vt+1（f− a，l′）.（五）l′∈L（5）中的第一项表示状态s和动作a在时间t的即时满意度，第二项表示在时间间隔t1，Tm 1期间的预期未来满意度。对于特殊情况，vTm1（s）c（f），因为没有活动流，并且仅在时间Tm1处对未完成的文件大小向量f保持负效用设π是一个最优策略，使我们的目标在[1，Tm+ 1]期间的期望满意度最大化。π∈Πt=136Y. Kim等人/ICT Express 3（2017）33=[客户端]O|不||F||F ||F|尽管基于DP的解决方案具有最优性，但它具有实际局限性;为了找到时间t处的最优动作1，我们必须已经找到了所有的行动，系统状态在间隔1，Tm和存储它们，这需要高处理能力和巨大的内存。复杂度（），其中是时隙的总数，是文件大小状态的数量，其以指数方式增加到流的数量m。因此，我们得到另一个基于阈值的启发式算法，需要低处理和低内存。此外，它不需要关于未来Wi-Fi联系人的概率2.4. 基于指针的算法我们实现了一个基于阈值的速率控制算法，基于以下理由：（i）它保证下载完成的所有流在其截止日期内的概率为1时，它是可能的（ii）以EDF（Earliest DeadlineFirst，最早期限优先）方式顺序分配速率这是因为紧急流量（即，具有短截止期限的流）比其它流具有更少的数据传送机会。(iii)它试图通过在截止日期之前有足够的时间的情况下尽可能多地避免蜂窝数据使用来增加卸载效率。(iv)每个流在截止日期内下载完成的成功或失败应该通过考虑所有未完成流的负载（剩余文件大小、截止日期）来估计然后，我们的基于阈值的速率控制算法可以描述如下。Y. Kim等人/ICT Express 3（2017）3337--=-i=1==图1.一、基于DP、基于阈值和现有算法的满意度，（rc，rw）=（7. 二六9） Mbps，Wi-Fi的时间覆盖率=33%且λ=2。3.2. 比较算法当网络状态为Wi-Fi时，它充分利用了Wi-Fi，通过以EDF方式最大化地分配流速率来实现Fi带宽。另一方面，当网络状态是蜂窝时，在满足具有网络的最低数据速率min（rc，rw）的截止期限完成的情况下，以EDF方式最小地分配流速率。3. 轨迹驱动仿真3.1. 仿真设置在本节中，我们通过测量和跟踪驱动的模拟来评估我们的基于DP和基于阈值的算法。我们考虑的情况下，从一个到四个流共存。我们使用YouTube视频大小的数据集[8]来生成文件大小，因为它适合延迟容忍应用程序。我们重新缩放数据集，使平均文件大小为100 MB。每个流的最后期限由两个组成部分的总和确定：（i）下载具有最低数据速率的文件的基本延迟(ii)移动用户可以容忍的额外延迟。每个流从10 min、30 min、1 h、2 h集合中随机选取其附加延迟对于网络生成，我们将蜂窝和Wi-Fi网络的数据速率我们测量了在KAIST校园内部署的HSPA、LTE和LTE-A技术的蜂窝网络以及Wi-Fi网络（802.11g）的吞吐量。平均数据速率分别为3.3Mbps、此外，我们在KAIST招募了63名使用Android智能手机的学生，在14天内收集他们的Wi-Fi连接。5接下来，我们将负效用函数定义为c（f）M与所有流的未完成文件大小之和成比例，其中λ是延迟敏感性参数。6随着λ变大，我们基于动态编程的调度器通过在未来交换Wi-Fi机会来努力更早地完成流5 在我们的其他工作中已经引入了迹[9]。6 每个流的负效用函数也可以根据应用的特性而不同。在我们的模拟中，我们将我们提出的速率控制算法与现有算法进行比较：现场，现场EDF，Wi-Fi-only，Wi-Fi-only-EDF和ODWO（最佳延迟Wi-Fi卸载）。On-the-spot是一种同时激活所有流的基线无论网络状态如何，流都平等地共享当前网络资源。仅当网络状态为Wi-Fi时，Wi-Fi-only同时激活所有流。on-the-spot-EDF和Wi-Fi- only-EDF分别是on-the-spot和Wi-Fi-only的EDF版本ODWO [6]是用于单流场景的最佳流开/关算法3.3. 仿真结果图1示出了当（r c，r w）（7. 二六9） Mbps，Wi-Fi的时间覆盖33%，λ2. 现场执行几乎零负效用，因为它打开流没有任何延迟。然而，由于失去了未来的Wi-Fi机会，它实现了低卸载效率现场-EDF实现与现场情况几乎相同。在这种情况下，顺序和并行传输不会影响满意度，因为现场有足够的时间在截止日期之前完成所有流程。另一方面，仅Wi-Fi和仅Wi-Fi EDF执行高卸载效率，因为它们充分利用了Wi-Fi机会。然而，高负效用可能会发生，因为许多未完成的流程存在的最后期限。因此，应仔细考虑Wi-Fi的时间覆盖范围。有趣的是，仅Wi-Fi和仅Wi-Fi-EDF之间存在巨大的满意度差距，因为他们没有足够的插槽来下载在最后期限前提交文件与现场相比，ODWO实现了至少88%的满意度增益，这来自于延迟传输，直到Wi-Fi在某种程度上接触每个流的开/关控制最佳地确定在单个意义上的，但由于缺乏关于流之间的网络资源争用的考虑而不是全局最优的。我们基于DP的算法通过联合考虑Wi-Fi接触分布，数据速率，流量负载和负效用函数来优化多流速率控制。令人惊讶的是，我们的基于阈值的算法执行几乎相同的基于DP的算法38Y. Kim等人/ICT Express 3（2017）33表1与ODWO相比，基于阈值的算法的满意度增益。数量的流1234满意度增长（%）0.07.113.319.7在我们的模拟设置中具有低复杂性。基于阈值的算法是一种保守的算法，它总是考虑网络状态在未来的最坏情况，以满足最后期限。因此，当负效用项与卸载效率项相比足够大当λ足够高时）。这些结果表明，我们的理由实现基于阈值的算法是非常适合在移动环境中的多流管理。表1示出了在相同的仿真参数下，对于不同数量的共存流，基于阈值的算法与ODWO相比增益随着流数量的增加而增加。因此，考虑流之间的资源耦合的速率控制变得更加重要，因为用户同时使用许多延迟容忍应用。4. 结论在本文中，为了提高用户的满意度，我们提出了两个多流量控制器与指定的死线延迟Wi-Fi卸载系统。为了提高Wi-Fi网络的利用率，减少由于截止期限违反而造成的负效用，我们考虑了多个流之间的网络资源竞争以及蜂窝网络和Wi-Fi网络之间的网络过渡。通过跟踪驱动的模拟，我们发现与现有的不考虑流之间的网络资源竞争的流管理算法相比，我们的基于动态规划和基于阈值的速率控制算法显著提高了用户满意度。引用[1] Y. Kim ， J. Lee ， J. Jeong ， S. Chong ， Multi-flow rate control indelayed Wi-Fi offloading systems ， in ： Proc. of ICOIN ， KotaKinabalu，Malaysia，2016，pp. 274-279[2] G.阿南塔纳拉亚南岛Stoica，Blue-fi：Enhancing wi-fi performanceusingblue to Oothsignals，in：Proc. ACMMobiSys，Krako'w，Poland，2009，pp.249-262.[3] K. Lee，J. 李，Y。伊岛Rhee，S.Chong，移动数据卸载：多少钱wifi可以送吗？IEEE/ACM Trans.网络21（2）（2013）536[4] S. 哈，S。森角Joe-Wong，Y.Im，M.Chiang，管：时间依赖移动数据定价，见：Proc. of ACM SIGCOMM，Helsinki，Finland，2012，pp. 247-258.[5] N. Ding ， D. Wagner ， X. Chen ， Y.C. Hu ， 黄 毛 菊 A. Rice ，Characterizing and modeling the impact of wireless signal strength onsmartphone battery drain ， in ： Proc. of the ACM SIGMETRICS ，Pittsburgh，PA，USA，2013，pp. 29比40[6] M.H. Cheung， J. Huang， DAWN ： Delay-aware wi-fi offloading andnetworkselection，IEEE J. Sel. Areas Commun. 33（6）（2015）1214-1223。[7] M.L. 马尔可夫决策过程：离散随机动态Programming，Wiley，2005.[8] YouTube视频的统计和社交网络数据集URLhttp://netsg.cs.sfu.ca/youtubedata/网站。[9] J. 郑岛，澳-地易，J. -W. 周，D.Eun，S.Chong，Energy-efficient wi-fisensing policy under generalized mobility patterns with aging ， IEEETrans. Netw. 24（4）（2016）2416-2428。
