一種移動(dòng)數(shù)據(jù)offloading的最大權(quán)算法

張小云

摘要：本文提出了一種存在時(shí)變信道、重配置延遲以及干擾限制的無線網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)調(diào)度算法，這種調(diào)度算法主要研究在隨隊(duì)列長度變化的時(shí)間槽中，如何根據(jù)移動(dòng)節(jié)點(diǎn)的拓?fù)湫畔磉x擇節(jié)點(diǎn)進(jìn)行傳輸，使得無線網(wǎng)絡(luò)的容量最大。首先分析了無線網(wǎng)絡(luò)中上行鏈路的容量，然后通過克拉克模型對移動(dòng)信道進(jìn)行建模從而得到每個(gè)移動(dòng)節(jié)點(diǎn)的SINR，然后通過最大權(quán)算法，得出Top-K個(gè)調(diào)度，然后再衡量這K個(gè)調(diào)度造成的重配置損失以及保持原有調(diào)度造成的損失，最后則決定下一個(gè)調(diào)度。通過實(shí)驗(yàn)結(jié)果可以得出，提出的算法比現(xiàn)有的算法吞吐量更大。

關(guān)鍵詞：移動(dòng)云計(jì)算； 重配置延遲； 吞吐域； 最大權(quán)算法

中圖分類號(hào)：TP39141 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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引言

目前，全球范圍內(nèi)蜂窩網(wǎng)絡(luò)中數(shù)據(jù)量正以每年兩倍的速度加速增長，這就使得蜂窩網(wǎng)絡(luò)中的數(shù)據(jù)傳輸對現(xiàn)有的網(wǎng)絡(luò)吞吐帶來了嚴(yán)峻挑戰(zhàn)。而在這種形勢的強(qiáng)力推動(dòng)下，數(shù)據(jù)的Offloading技術(shù)研究即已成為當(dāng)前的熱點(diǎn)和焦點(diǎn)。Offloading技術(shù)研究就是采用非蜂窩設(shè)計(jì)來輔助蜂窩網(wǎng)絡(luò)中移動(dòng)終端的數(shù)據(jù)傳輸?shù)南嚓P(guān)開發(fā)過程。其中，蜂窩網(wǎng)絡(luò)中比較熱門的技術(shù)手段就是采用WiFi接入點(diǎn)來協(xié)助數(shù)據(jù)傳輸。對于使用無線網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)上傳的研究中，基于特定信道模型、并存在干擾限制的無線網(wǎng)絡(luò)中的調(diào)度問題已經(jīng)在很多研究工作中取得了一定進(jìn)展[1-4]，但據(jù)專業(yè)分析可知，在基于無線網(wǎng)絡(luò)的offloading研究中，重配置延遲問題并沒有得到應(yīng)有的重視。重配置延遲指的是，無線網(wǎng)絡(luò)中的設(shè)備在配置參數(shù)發(fā)生改變時(shí)，就會(huì)對其服務(wù)進(jìn)行重新配置，而實(shí)現(xiàn)配置卻是一個(gè)耗費(fèi)時(shí)間的過程。在常規(guī)研究中，因?yàn)閿?shù)據(jù)傳輸速率低，由重配置延遲帶來的影響幾乎可以忽略不計(jì)，所以這種延遲并未見到任何系統(tǒng)研究。但是在高速數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)中，重配置延遲即已成為一個(gè)重要現(xiàn)象，因?yàn)樵诟咚贁?shù)據(jù)傳輸?shù)南到y(tǒng)中，數(shù)據(jù)速率高、延遲要求高，數(shù)據(jù)傳輸?shù)闹嘏渲妙l率也隨之提高，此時(shí)與傳輸周期成比例的重配置延遲對于系統(tǒng)吞吐的影響將無可忽視。在衛(wèi)星網(wǎng)絡(luò)中，從一個(gè)基站切換到另一個(gè)基站的時(shí)間大約是10毫秒左右[5]；在光通信系統(tǒng)中，激光調(diào)制延遲一般在微秒到毫秒級(jí)別[6]；在無線網(wǎng)絡(luò)中，切換信道時(shí)候，鎖相環(huán)中的晶振大約需要200微秒的時(shí)間進(jìn)行重配置。文獻(xiàn)[5，7]在文獻(xiàn)[1]中的研究結(jié)果表明，對于Atheros 5512無線網(wǎng)卡切換信道寬度或者信道中心頻率的時(shí)間大約在4.11/0.244毫秒左右；又有文獻(xiàn)[8]的研究表明，對于一般的無線接入點(diǎn)，信道切換（重配置的一種）的延遲大約在5～45毫秒之間，統(tǒng)計(jì)的眾數(shù)卻是17毫秒。這里的17毫秒比文獻(xiàn)[1]中的4毫秒要大得多，主要是文獻(xiàn)[1]對于驅(qū)動(dòng)實(shí)現(xiàn)了良好的優(yōu)化，而文獻(xiàn)[8]卻只是針對普通的無線接入點(diǎn)而言。

雖然這種重配置延遲曾獲偶一捕捉，但是針對其詳細(xì)研究的文章仍比較少見，最近的有文獻(xiàn)[5]。而關(guān)于WiFi接入點(diǎn)輔助的移動(dòng)數(shù)據(jù)傳輸中，具體考慮重配置延遲的研究中，本文的成果則具較新時(shí)效。本文的貢獻(xiàn)主要有以下幾點(diǎn)：

（1）分析了重配置延遲對基于WiFi網(wǎng)絡(luò)的吞吐域，并指出重配置延遲導(dǎo)致信道的分集特性消失。

（2）提出了一種考慮重配置延遲的調(diào)度算法。在沒有重配置延遲的無線網(wǎng)絡(luò)中，調(diào)度總是將切換到最優(yōu)調(diào)度上以獲得最大的吞吐。但是在實(shí)際的無線網(wǎng)絡(luò)環(huán)境下，并不能簡單地進(jìn)行切換，因?yàn)榍袚Q代價(jià)可能讓重配置帶來的吞吐增益完全抵消。在本文提出的算法中，信道的切換損失、包括調(diào)度帶來的增益以及保持現(xiàn)有調(diào)度造成的吞吐下降都將得以考慮。而且算法能夠給出一個(gè)比較實(shí)際的調(diào)度。

（3）通過實(shí)驗(yàn)證明了本文的算法比現(xiàn)有的算法具有更大的吞吐。

本文后續(xù)章節(jié)安排如下：第一章主要描述對無線網(wǎng)絡(luò)吞吐域進(jìn)行建模，并且對網(wǎng)絡(luò)中的信道模型進(jìn)行建模。第二章分析了調(diào)度的切換延遲、調(diào)度的時(shí)間衰減效應(yīng)，同時(shí)通過衡量這些增益和損失，給出了一個(gè)調(diào)度算法。第三章對提出的調(diào)度算法進(jìn)行試驗(yàn)對比。最后即總結(jié)了全文。

1網(wǎng)絡(luò)建模

1.1數(shù)據(jù)offloading框架

3實(shí)驗(yàn)

實(shí)驗(yàn)的場景布置包含一個(gè)中心控制器、三個(gè)AP以及四個(gè)移動(dòng)終端。其中，控制算法運(yùn)行在控制器上，三個(gè)AP與中心控制器通過有線連接，中心控制器的算法輸出可實(shí)時(shí)傳送到AP上，AP即按照接收到的結(jié)果進(jìn)行終端調(diào)度。每個(gè)移動(dòng)終端勻速進(jìn)入或者離開AP覆蓋范圍，并周期性地向AP傳送拓?fù)湫畔?。AP和移動(dòng)終端則通過控制信道進(jìn)行配置協(xié)商?；诖?，實(shí)驗(yàn)將選用一臺(tái)運(yùn)行Linux操作系統(tǒng)的計(jì)算機(jī)充當(dāng)控制器，而將三個(gè)基于ath5k開源驅(qū)動(dòng)的無線接入點(diǎn)作為AP，同時(shí)配置4個(gè) android手機(jī)作為移動(dòng)終端。實(shí)驗(yàn)對比的結(jié)果參數(shù)主要是吞吐量。具體地，實(shí)驗(yàn)場景布置則如圖3所示。

文中涉及三種算法。第一種是傳統(tǒng)的最大權(quán)算法MW，這種算法在調(diào)度的過程中考慮信道質(zhì)量和移動(dòng)終端上面的數(shù)據(jù)量，但是不考慮重配置延遲帶來的影響，也未曾考慮調(diào)度周期與數(shù)據(jù)量之間的關(guān)系。第二種算法是VFMW，考慮了信道質(zhì)量和移動(dòng)終端上的數(shù)據(jù)量，也考慮調(diào)度周期與總數(shù)據(jù)量之間的關(guān)系，但是卻未考慮重配置延遲中的重配置部分與非重配置部分。第三種算法MWBS則是本文提出的。 在此場景下數(shù)據(jù)于移動(dòng)終端上以一定的隨機(jī)過程得以產(chǎn)生，而在實(shí)驗(yàn)過程中，即是采用泊松過程來產(chǎn)生數(shù)據(jù)。算法過程將數(shù)據(jù)產(chǎn)生的速率從0開始逐步增加，以測試這幾種算法的吞吐能力。 這三種算法的運(yùn)行結(jié)果對比則如圖4所示。

從吞吐結(jié)果可以看出，本文提出的算法在高負(fù)載情況下比其他算法表現(xiàn)更為突出。具體分析可知，簡單的MW算法沒有考慮重配置過程是這種算法在實(shí)際調(diào)度過程中吞吐量較小的主要原因。VFMW雖然考慮了重配置延遲，提出調(diào)度周期應(yīng)該與當(dāng)前的數(shù)據(jù)總量成一定關(guān)系，這也是VFMW比MW更為優(yōu)越的原因，但是這種算法卻仍未考慮重配置帶來的損失以及保持現(xiàn)有調(diào)度帶來的收益。也就是說，VFMW并沒有考慮切換代價(jià)，這也是本文提出算法優(yōu)于MW和VFMW的根本所在。

4結(jié)束語

在本文中運(yùn)用了克拉克-甘模型對通信的信道進(jìn)行建模，并基于無線網(wǎng)絡(luò)的拓?fù)淝闆r，進(jìn)一步提出了一種最大權(quán)算法用于移動(dòng)數(shù)據(jù)的offloading，而與現(xiàn)有的算法相比，本文提出的算法具有更為明顯的效果改進(jìn)與提升。

參考文獻(xiàn)：

[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.