《一种移动数据offloading的最大权算法.pdf》由会员分享，可在线阅读，更多相关《一种移动数据offloading的最大权算法.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第卷第期年月智能计算机与应用种移动数据 的最大权算法张小云（武警甘肃总队，兰州）摘要：本文提出了一种存在时变信道、重配置延迟以及于扰限制的无线网络中的移动节点调度算法， 这种调度算法主要研究在随队列长度变化的时间槽中，如何根据移动节点的拓扑信息来选择节点进行传输，使得无线网络的容量最大。首先分析了无线网络中上行链路的容量，然后通过克拉克模型对移动信道进行建模从而得到每个移动节点的 ，然后通过最大权算法，得出 个调度，然后再衡量这个调度造成的重配置损失以及保持原有调度造成的损失，最后则决定下一个调度。通过实验结果可以得出，提出的算法比现有的算法吞吐量更大。关键词：移动云计算；重配置延迟；吞吐域；
2、最大权算法中图分类号：文献标识码：文章编号： （）一 （，）： ， ， ， ，：；引言目前，全球范围内蜂窝网络中数据量正以每年两倍的速度加速增长，这就使得蜂窝网络中的数据传输对现有的网络吞吐带来了严峻挑战。而在这种形势的强力推动下，数据的个基站的时间大约是毫秒左右；在光通信系统中，激光调制延迟一般在微秒到毫秒级别；在无线网络中，切换信道时候， 锁相环中的晶振大约需要微秒的时间进行重配置。文献，在文献中的研究结果表明，对于 技术研究即已成为当前的热点和焦点。 无线网卡切换信道宽度或者信道中心频率的时间大约在毫秒左右；又有文献的研究表明，对于一般的无线接入点，信道切换（重配置的一种）的延迟大约在技
3、术研究就是采用非蜂窝设计来辅助蜂窝网络中移动终端的数据传输的相关开发过程。其中， 蜂窝网络中比较热门的技术手段就是采用接入点来协助数据传输。对于使用无线网络进行数据上传的研究中，基于特定信道模型、并存在干扰限制的无线网络中的调度问题已经在很多研究工作毫秒之间，统计的众数却是毫秒。这里的 毫秒比文献中的毫秒要大得多， 主要是文献对于驱动实现了良好的优化，而文献却只是针对普通的无线接人点而言。中取得了一定进展，但据专业分析可知，在基于无线网络的研究中，重配置延迟问题并没有得到应有的虽然这种重配置延迟曾获偶一捕捉，但是针对其详细研究的文章仍比较少见，最近的有文献。而关于重视。重配置延迟指的是，无线网
4、络中的设备在配置参数发生改变时， 就会对其服务进行重新配置，而实现配置却是一个耗费时间的过程。在常规研究中，因为数据传输速率低，由重配置延迟带来的影响几乎可以忽略不计，所以这种延迟接人点辅助的移动数据传输中，具体考虑重配置延迟的研究中，本文的成果则具较新时效。本文的贡献主要有以下几点：（）分析了重配置延迟对基于 网络的吞吐域，并指并未见到任何系统研究。但是在高速数据传输的网络中，重配置延迟即已成为一个重要现象，因为在高速数据传输的系统中， 数据速率高、延迟要求高，数据传输的重配置频率也随之提高，此时与传输周期成比例的重配置延迟对于系统吞吐的影响将无可忽视。在卫星网络中，从一个基站切换到另一收稿
5、日期：一出重配置延迟导致信道的分集特性消失。（）提出了一种考虑重配置延迟的调度算法。在没有重配置延迟的无线网络中， 调度总是将切换到最优调度上以获得最大的吞吐。但是在实际的无线网络环境下，并不能简单作者简介：张小云（一），男，甘肃临夏人，学士，中级职称，主要研究方向：智能系统、无线通信。智 能计算机与 应 用第卷地进行切换，因为切换代价叮能让重配置带来的吞吐增益完全抵消。在本文提出的算法中，信道的切换损失、 包括调度带来的增益以及保持现有调度造成的吞吐下降都将得以考虑。而且算法能够给出一个比较实际的调度。（）通过实验证明了本文的算法比现有的算法具有更大的吞吐。本文后续章节安排如下：第一章主要描
6、述对无线网络吞吐域进行建模，并且对网络中的信道模型进行建模。第二章分析了调度的切换延迟、调度的时问衰减效应，同时通过衡量这些增益和损失，给出了一个调度算法。第三章对提出的调度算法进行试验对比。最后即总结了全文。 网络建模数据框架一个无线网络通常包含几个或者几十个。在此用 ， 来代表这些，总共个。 ，个移动终端表示为，。研究中，假设数据在移动终端上产生的是一个随机过程，而且其产生的速率是（，：，）（表示了凸集），这些产生的数据形成了一个队列：（） ：（，），节点上面的数据队列长度为。当一个移动节点进入某个的覆盖范围内时，这个移动节点将自动连接到此上，并于随后传输需要上传的数据。移动节点的速度为（
7、， ）。移动节点对应的信道过程则为（，）。系统的调度定义为（，），而且意味着没有数据通过这条链路在进行上传。特别地，当（）（）时，即采用新的调度。文中利用， 来表示链路是否将获调度，也就是说，当且仅当，实际上，一个调度就标示着链路是否被调度，并且还表示了链路将在什么信道上而获得调度。研究中，还利用 来表示重配置延迟，也就是在数据 过程中，节点通常需要历经 时间才能与进行连接并实现配置；尤其是，当信道发生改变时也将需要 ，时间段来适配新信道再开始数据传输。重配置延迟会改变从传统最大权算法得出的优化策略的结构，因为重配置延迟弱化甚至抹去了分集增益带来的系统吞吐增益，由此可知对于存在重配置延迟的网络
8、中，无线网络的吞吐将朝着一种平均的模式发展，也就是链路的吞吐不能超过链路的长期平均， 亦不存在分集增益。比如说在一个无记忆信道两终端一个服务器的无线网络中，无记忆表示不同时间片卜的信道质量相互独立：也就是（ ），与信道集合中的其他信道均表现为一个独立同分布过程。并且， 这种网络吞吐已在文献中给出， 具体表述如下：八： 。，这样的话， ， （）公式（）表示的是在具有重配置延迟的网络中，任何策略都不能利用信道的分集增益并达到一个比平均信道增益更大的系统吞吐。 信道建模基于对物理世界的真实考虑， 无记忆信道和有记忆的马尔科夫信道都过于理论化。而且在移动云计算数据传输的现实应用中，类似于多普勒延迟、多
9、径效应等等由于移动造成的因素也应该纳入考虑范围， 也正是由于移动性所形成的这些复杂情况，有记忆和无记忆信道都将无法用于模拟这些复杂时变信道。在本文中，采用的即是一种连续时问衰落信道模型，模型设计如下：（）（） （一（）（ ）（）一其中， （）是发送信号，（）是接收信号。时变多径衰减信道将通过（ ），并且时间延迟为 的路径。公式（）的最后一项（）则是零均值高斯白噪声，其谱密度即是， ，这一项主要用于建模接收端的背景噪声。信号的丢失是由于信号在传输和接收过程中存在的失真所导致，因而信噪比（）就是一种合理的衡量指标。可以用来颦度数据传输的成功率，从文献中可以看出，和传输的成功率是有一定的量值关系，其
10、计算公式则如下： ， ， ， 尺在此，可将公式（）用图表现出来，网形可更好地表达和传输率之问的关系。由图即可看出，能够很好地衡量数据的传送率。图 与成功传输率的函数关系图在本文中，又引用了文献中的卡拉卡一甘模型来对数据包相关的信噪比进行建模。模型的数学实现如下：）（）其中， （）是在时刻发送端和接收端之间的距离，卢是路径衰减因子，（）是在时刻的平均信道增益，则是第期背景噪声（ ）的方差。张小云：一种移动数据 的最大权算法 时变参数口描述了接收的短时变化， 对于多径效应， 在无视距分量的情况下即可利用瑞利分布进行建模；而数， 也就是 二，并且将在每个时间槽上都更新这个函数值， 也就是下一个调度的
11、时间长度将在下一个时间片开始时刻而得到计算。考虑重配置延迟， 研究将衡量新调度带来的收益以及与当存在一定数量的视距分量时， 将使用莱斯分布进行建模。具体地， 莱斯分布如下所示：（）“（）（）其相关的重配置损失， 并与延续现有调度带来的收益进行比较， 而后找出最好的调度方案。如果采用新调度带来的收益其中， 表示接收到的视距分量占接收到的总能量的比例。（）是第一类二阶贝塞尔函数，能量谱密度（厂）分减去其对应损失依然比延续现有调度带来的收益大，那么将采用新的调度方案， 否则就延续之前的调度方案。在此，可布在一，上，并可通过式（）而最终给定：（：兰兰二二（） 一（）式中表示传输信号的载波频率。 调度算
12、法本文提出了一种基于最大权的调度算法，算法的实现思路是：网络控制器能够感知网络拓扑（包括队列长度，移动速度以及距离）变化， 而信道的传输能力能够通过信道模型进行计算，如此控制器将可通过拓扑信息以及信道信息，选取合适的决策变量进行有效调度，以求达到更佳吞吐。基于此，选取时间槽的开始时刻作为调度的时问点，而在调度的时问点上， 存在一些可行调度（）：（）式（）表示信道分配给了，即是一个可行的、相互之间没有干扰的调度， 而且（）的结果也很重要，因为这有可能就是最优调度。该等式的意义在于：将有这样的一些终端得到调度的概率会更高， 也就是这些终端具有大的数据量传输、信道的质量较好并且移动速度也较慢。这在现
13、实生活中多是比较合理的， 大的数据量意味着数据能够被长时间传输， 信道质量好表示传输的速率会很高，终端的移动速率慢则代表其停留在覆盖范围内的时间比较长，并且这些因素的乘积若也比较高的话， 就可推知这样的凋度更有可能达到最高的吞吐量。正如已有研究提出的一样，对于没有重配置延迟的系统， 调度算法总是能够改变到最好的调度上并获得最优的吞吐， 但是如果网络存在重配置延迟，这个重新配置的过程往往就让重配置带来的吞吐改变失去意义，因为在重配置的那个时间中， 被重配置的链路将无法传送数据。传统的解决重配置延迟带来影响的方法是延长调度时问，当调度时间延长到无穷时，重配置延迟引起的吞吐即下降为， 但这显然是不可
14、能的。也就是说存在重配置延迟的无线网络中，调度的有效性除了和调度算法本身相关，还和调度的时间长度有关系。在本文中，采用的调度时间长度是现有覆盖范围内的终端的所有数据量加和的一个函数，函数表达式可如下所不： （）厂 （， （）（）（）根据文献的研究，在此设置厂（）为一个亚线性函用（）代表当前调度方案，而设（）作为下一个调度周期可能的最优方案， 并用表示当前调度和下一个可能最优调度之间的不需要重新配置的链路集合，并将称为相似集， 也就是现有调度的链路中在下一个调度中依然保持现有调度方案的那一部分，因为在新的调度中这部分依然保持相同的调度，而不会再受到重配置过程的影响。如果研究将继续在下一个调度周期
15、中应用（），即可获得一个如下的期望收益：（ ） （ ） （ ） （）（）但是，如果在下一个调度周期中采用新的调度（），则将获得收益计算如下：（）（） （ ） （）（】）一） （一） （）（）在这个等式中，第一部分是那些不需要更改自己调度的链路带来的收益，可以看出这一部分收益并不受到重配置过程的影响。第二部分则将涉及重配置过程的链路带来的收益，并且可以看出在调度开始的部分时间，这一部分链路并不能传送数据，其对应的总调度时间则为，（）一。基于（）和（）的实现结果，可开发一定算法以决定在时刻的行为。如果（）小于（ （），即可保持现有调度（ ），并且根据现有队列过程重新计算下一个调度的持续时问；否则就
16、将调度重配置到（），并计算新调度的持续时间。算法实现的伪代码可如图所示。算法中选取的（）在很大程度上即代表着最优调度，因为重配置过程的存在，这些新选取的调度中重配置的链路均不相同。由此将在调度算法中选取一个（），并形成集合，而随着增大则可知，选取的算法中必然包含最优调度算法，再通过比较集合中的调度带来的增益而确定最优调度。本文算法的工作过程如下：当移动终端进入的覆盖范围的时候，将自己的信息传输给，其中包括上次调度的时间， 本地存储并需要上传的数据量，当前的以及当前的移动速度。控制器即选取最好的个调度，再将选出的个调度以及当前调度对比除去损失之后的期望收益，由此而智 能 计 算机与 应 用第卷给
17、出将使用何种调度的最终决策。输入：节点队列长度向量，节点移动速度向量，节点上次调度的时间， 必须调度的节点。输出：最优调度（）以及调度时间 。（），：；从循环到；节点广播其队列长度，速度，上次调度时间 。，口，（）（）从中选出一个 （），（）（）从循环到， ， 、（）（）、”厶（）一（）一（）（）（），）返回：（）和 （）图基于最大权的移动节点上行链路调度算法 实验实验的场景布置包含一个中心控制器、三个以及四个移动终端。其中， 控制算法运行在控制器上，三个与中心控制器通过有线连接，中心控制器的算法输出可实时传送到上，即按照接收到的结果进行终端调度。每个移动终端匀速进入或者离开覆盖范围，并周期性
18、地向传送拓扑信息。和移动终端则通过控制信道进行配置协商。基于此， 实验将选用一台运行 操作系统的计算机充当控制器，而将三个基于 开源驱动的无线接人点作为，同时配置个 手机作为移动终端。实验对比的结果参数主要是吞吐量。具体地， 实验场景布置则如图所示。图实验场景布置文中涉及三种算法。第一种是传统的最大权算法，这种算法在调度的过程中考虑信道质量和移动终端上面的数据量， 但是不考虑重配置延迟带来的影响，也未曾考虑调度周期与数据量之间的关系。第二种算法是，考虑了信道质量和移动终端上的数据量，也考虑调度周期与总数据量之间的关系，但是却未考虑重配置延迟中的重配置部分与非重配置部分。第三种算法则是本文提出的
19、。在此场景下数据于移动终端上以一定的随机过程得以产生，而在实验过程中，即是采用泊松过程来产生数据。算法过程将数据产生的速率从开始逐步增加， 以测试这几种算法的吞吐能力。这三种算法的运行结果对比则如图所示。从吞吐结果可以看出，本文提出的算法在高负载情况下比其他算法表现更为突出。具体分析可知， 简单的算法没有考虑重配置过程是这种算法在实际调度过程中吞吐量较小的主要原因。虽然考虑了重配置延迟，提出调度周期应该与当前的数据总量成一定关系，这也是比更为优越的原因，但是这种算法却仍未考虑重配置带来【 ） 苫盘最皇 霉的损失以及保持现有调度带来的收益。也就是说，并没有考虑切换代价，这也是本文提出算法优于和的
20、根本所在。 （）图数据进入速率变化时，三种算法有关平均吞吐量的对比关系图，锄结束语在本文中运用了克拉克一甘模型对通信的信道进行建模， 并基于无线网络的拓扑情况，进一步提出了一种最大权算法用于移动数据的 ，而与现有的算法相比，本文提出的算法具有更为明显的效果改进与提升。参考文献：，： ， ，：， 一第期张小云：一种移动数据 的最大权算法 ，：，（）： ， ， ， ， ， ，：， ： ， ， ， ，（）： ：， ： ， ，： ：，（上接第页）古辉，王益义一种基于模板匹配的船铭牌字符分割方法浙 黄炯生，黄敏琪基于模型匹配法的字符识别中国科技信息，江工业大学学报，（）：，（）：程广涛，陈雪， 张文治基于垂直投影和模板匹配的车牌字符分割 何希平，李云峰， 朱庆生彩色文档图像的倾斜自动校正算法 方法北华航天工业学院学报，（）：中国图象图形学报，（）：罗辉武，唐远炎基于结构特征和灰度特征的车牌字符识别方法 计算机科学，（）： ，李瑞萍电器铭牌图像字符识别系统的研究西安：西安理工，：大学，