一种移动数据offloading的最大权算法

张小云

摘要：本文提出了一种存在时变信道、重配置延迟以及干扰限制的无线网络中的移动节点调度算法，这种调度算法主要研究在随队列长度变化的时间槽中，如何根据移动节点的拓扑信息来选择节点进行传输，使得无线网络的容量最大。首先分析了无线网络中上行链路的容量，然后通过克拉克模型对移动信道进行建模从而得到每个移动节点的SINR，然后通过最大权算法，得出Top-K个调度，然后再衡量这K个调度造成的重配置损失以及保持原有调度造成的损失，最后则决定下一个调度。通过实验结果可以得出，提出的算法比现有的算法吞吐量更大。

关键词：移动云计算； 重配置延迟； 吞吐域； 最大权算法

中图分类号：TP39141 文献标识码：A文章编号：2095-2163（2014）04-0113-05

Abstract：A data offloading algorithm for mobile data offloading throughput wireless network is proposed in this paper， by considering the time-varying channels， reconfiguration delays and interference constraints in wireless networks. The paper analyzes the uplink capacity region of multiple mobile users in wireless networks， and uses Clarke Gan's channel model for channel process of mobile terminals. After that， the paper considers the impact of reconfiguration delay of wireless device and its impact to the capacity of the wireless network， further proposes a Max-Weight algorithm for the system. The proposed algorithm makes schedule by considering the impaction of reconfiguration and the expectation throughput of a schedule. And the experiment results shows that the proposed algorithm performs well， and has beter throughout.

Key words：Mobile Cloud Computing； Reconfiguration Delay； Capacity Region； Max-Weight

0引言

目前，全球范围内蜂窝网络中数据量正以每年两倍的速度加速增长，这就使得蜂窝网络中的数据传输对现有的网络吞吐带来了严峻挑战。而在这种形势的强力推动下，数据的Offloading技术研究即已成为当前的热点和焦点。Offloading技术研究就是采用非蜂窝设计来辅助蜂窝网络中移动终端的数据传输的相关开发过程。其中，蜂窝网络中比较热门的技术手段就是采用WiFi接入点来协助数据传输。对于使用无线网络进行数据上传的研究中，基于特定信道模型、并存在干扰限制的无线网络中的调度问题已经在很多研究工作中取得了一定进展[1-4]，但据专业分析可知，在基于无线网络的offloading研究中，重配置延迟问题并没有得到应有的重视。重配置延迟指的是，无线网络中的设备在配置参数发生改变时，就会对其服务进行重新配置，而实现配置却是一个耗费时间的过程。在常规研究中，因为数据传输速率低，由重配置延迟带来的影响几乎可以忽略不计，所以这种延迟并未见到任何系统研究。但是在高速数据传输的网络中，重配置延迟即已成为一个重要现象，因为在高速数据传输的系统中，数据速率高、延迟要求高，数据传输的重配置频率也随之提高，此时与传输周期成比例的重配置延迟对于系统吞吐的影响将无可忽视。在卫星网络中，从一个基站切换到另一个基站的时间大约是10毫秒左右[5]；在光通信系统中，激光调制延迟一般在微秒到毫秒级别[6]；在无线网络中，切换信道时候，锁相环中的晶振大约需要200微秒的时间进行重配置。文献[5，7]在文献[1]中的研究结果表明，对于Atheros 5512无线网卡切换信道宽度或者信道中心频率的时间大约在4.11/0.244毫秒左右；又有文献[8]的研究表明，对于一般的无线接入点，信道切换（重配置的一种）的延迟大约在5～45毫秒之间，统计的众数却是17毫秒。这里的17毫秒比文献[1]中的4毫秒要大得多，主要是文献[1]对于驱动实现了良好的优化，而文献[8]却只是针对普通的无线接入点而言。

虽然这种重配置延迟曾获偶一捕捉，但是针对其详细研究的文章仍比较少见，最近的有文献[5]。而关于WiFi接入点辅助的移动数据传输中，具体考虑重配置延迟的研究中，本文的成果则具较新时效。本文的贡献主要有以下几点：

（1）分析了重配置延迟对基于WiFi网络的吞吐域，并指出重配置延迟导致信道的分集特性消失。

（2）提出了一种考虑重配置延迟的调度算法。在没有重配置延迟的无线网络中，调度总是将切换到最优调度上以获得最大的吞吐。但是在实际的无线网络环境下，并不能简单地进行切换，因为切换代价可能让重配置带来的吞吐增益完全抵消。在本文提出的算法中，信道的切换损失、包括调度带来的增益以及保持现有调度造成的吞吐下降都将得以考虑。而且算法能够给出一个比较实际的调度。

（3）通过实验证明了本文的算法比现有的算法具有更大的吞吐。

本文后续章节安排如下：第一章主要描述对无线网络吞吐域进行建模，并且对网络中的信道模型进行建模。第二章分析了调度的切换延迟、调度的时间衰减效应，同时通过衡量这些增益和损失，给出了一个调度算法。第三章对提出的调度算法进行试验对比。最后即总结了全文。

1网络建模

1.1数据offloading框架

3实验

实验的场景布置包含一个中心控制器、三个AP以及四个移动终端。其中，控制算法运行在控制器上，三个AP与中心控制器通过有线连接，中心控制器的算法输出可实时传送到AP上，AP即按照接收到的结果进行终端调度。每个移动终端匀速进入或者离开AP覆盖范围，并周期性地向AP传送拓扑信息。AP和移动终端则通过控制信道进行配置协商。基于此，实验将选用一台运行Linux操作系统的计算机充当控制器，而将三个基于ath5k开源驱动的无线接入点作为AP，同时配置4个 android手机作为移动终端。实验对比的结果参数主要是吞吐量。具体地，实验场景布置则如图3所示。

文中涉及三种算法。第一种是传统的最大权算法MW，这种算法在调度的过程中考虑信道质量和移动终端上面的数据量，但是不考虑重配置延迟带来的影响，也未曾考虑调度周期与数据量之间的关系。第二种算法是VFMW，考虑了信道质量和移动终端上的数据量，也考虑调度周期与总数据量之间的关系，但是却未考虑重配置延迟中的重配置部分与非重配置部分。第三种算法MWBS则是本文提出的。 在此场景下数据于移动终端上以一定的随机过程得以产生，而在实验过程中，即是采用泊松过程来产生数据。算法过程将数据产生的速率从0开始逐步增加，以测试这几种算法的吞吐能力。 这三种算法的运行结果对比则如图4所示。

从吞吐结果可以看出，本文提出的算法在高负载情况下比其他算法表现更为突出。具体分析可知，简单的MW算法没有考虑重配置过程是这种算法在实际调度过程中吞吐量较小的主要原因。VFMW虽然考虑了重配置延迟，提出调度周期应该与当前的数据总量成一定关系，这也是VFMW比MW更为优越的原因，但是这种算法却仍未考虑重配置带来的损失以及保持现有调度带来的收益。也就是说，VFMW并没有考虑切换代价，这也是本文提出算法优于MW和VFMW的根本所在。

4结束语

在本文中运用了克拉克-甘模型对通信的信道进行建模，并基于无线网络的拓扑情况，进一步提出了一种最大权算法用于移动数据的offloading，而与现有的算法相比，本文提出的算法具有更为明显的效果改进与提升。

参考文献：

[1]RAYANCHU S， SHRIVASTAVA V， BANERJEE S， et al. Fluid： improving throughputs in enterprise wireless lans through flexible channelization[C]//Proceedings of the 17th annual international conference on Mobile computing and networking， MobiCom 11， ACM， New York， NY， USA， 2011：1–12.

[2]NEELY M J， MODIANO E， ROHRS C E. Power and server allocation in a multibeam satellite with time varying channels[C]//Proceedings of IEEE INFOCOM 02， 2002： 1451–1460.

[3]GEORGIADIS L， TASSIULAS M J R. Resource allocation and cross-layer control in wireless networks [C]//Foundations and Trends in Networking， 2006.

[4]CELIK G D， LE L B， MODIANO E. Scheduling in parallel queues with randomly varying connectivity and switchover delay[C]//Proc. IEEE INFOCOM'11， Mini Conference， Apr. 2011.

[5]X l L Blake. Antennas： Fundamentals， Design， Measurement. SciTech， 2009.

[6]BRZEZINSKI， MODIANO E. Dynamic reconfiguration and routing algorithms for IP-over-WDM networks with stochastic traffic[J]. IEEE Journal of Lightwave Tech.， 2005，23（10）：3188-3205.

[7]YUN M， ZHOU Y， ARORA A， et al. Channel assignment and scheduling in wireless mesh networks considering switching overhead[C]//Communications， 2009. ICC 09. IEEE International Conference on， 2009： 1–6.

[8]CHANDRA R， MAHAJAN R， MOSCIBRODA T， et al. A case for adapting channel width in wireless networks[J]. SIGCOMM Comput. Commun. Rev，2008， 38 （4）： 135–146.

[9]D Tse， P Viswanath. Fundamentals of Wireless Communication[M]. Cambridge University Press， New York， NY， USA， 2005.

[10]SADEGHI B， KANODIA V， SABHARWAL A， et al. Opportunistic media access for multirate ad hoc networks[C]//Proceedings of the 8th Annual International Conference on Mobile Computing and Networking， MobiCom 02， ACM， New York， NY， USA， 2002： 24–35.

[11]T. Rappaport. Wireless Communications： Principles and Practice[M]. 2nd Edition. Prentice Hall PTR， Upper Saddle River， NJ， USA， 2001.

[12]National Center for Biotechnology Information. http：//www.ncbi.nlm.nih.gov .

[13]Intel pro/wireless network connection for mobile. http：//www.intel.com/network/connectivity/products .

[14]Walking. http：//en.wikipedia.org/wiki/Walking.