一種移動數據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.