ＧＰＲＳ／ＵＭＴＳ無線數據接入的控制與優化

(1.清華大學 電子工程系， 北京 100084； 2.云南省電子計算中心， 云南 昆明 650223)

摘要：提出了一種新的基于代理的協議框架以提高在GPRS/UMTS網絡中進行無線數據接入的性能。在此框架下研究了延時阻塞調度策略。該策略利用數據業務對延時不敏感的特性，在不增加帶寬的前提下顯著改善系統的響應性能，為實現該策略下的無線信道資源管理，設計了最優信道分配和自適應信道分配兩種算法。理論分析和仿真表明，新的機制和算法可以顯著地提高網絡利用率并縮短系統的平均響應時間。

關鍵詞： GPRS； UMTS； Proxy； 無線Internet訪問

中圖法分類號： TP393； TN92文獻標識碼： A

文章編號： 1001 3695(2006)08 0235 05



Performance Optimization of Internet Access in GPRS/UMTS Networks

WANG Yue1， REN Yong1， SHAN Xiu ming1， WANG Yao xi2

(1.Dept. of Electronic Engineering，Tsinghua University， Beijing 100084， China; 2.Yunnan Computer Center， Kunming Yunnan 650223， China)

Abstract: A proxy based framework for Internet access through GPRS/UMTS networks is proposed. A flow level scheduling scheme called Delay Block (DB) is studied within this framework. By exploiting the relative delay tolerance of data service， DB scheme can educe average response time of users without any additional bandwidth. Two algorithms， the optimal channel allocation algorithm and the adaptive channel allocation algorithm， are developed to managing the wireless resource. Analysis results and simulations show that the new framework and algorithms improve the average response time greatly while keeping network working efficiently.

Key words： GPRS; UMTS; Proxy; Wireless Internet Access

1 引言

Internet的發展對下一代移動通信系統的設計產生了巨大的影響。目前，傳統的GSM網絡已經開始支持GPRS（General Packet Radio Service）業務以提供Internet訪問的能力。同時，歐洲正在采用基于UMTS（Universal Mobile Telecommunication System）的第三代移動通信系統替代第二代的GSM系統。UMTS沿用了GPRS的體系結構，但實現了更高的數據接入速率（最高2Mbps）和更高效靈活的無線資源管理方式。如此高的速率使得通過移動通信系統有效地訪問基于IP的應用和服務成為可能。然而，盡管標稱性能是令人滿意的，但在實際使用中卻往往無法達到標稱值。最近的研究已經指出，現有的GPRS/UMTS系統在支持數據業務上存在著一些性能上的問題 [1] 。

這些問題首先表現在上層的TCP協議和下層的GPRS/UMTS網絡之間的性能適配上。GPRS/ UMTS網絡的一些固有特性（時變的帶寬、大延時和大的延時抖動、突發性的誤碼）嚴重干擾了TCP的正常工作 [2] 。有關TCP在無線網絡上的性能優化已經成為近期的一個研究熱點。

另一方面，我們發現GPRS/UMTS系統在工作模式上并不適合無線Internet訪問。現有的移動通信系統主要是為傳統的語音業務而設計的，它是一個面向連接的、對延時敏感的系統，主要提供固定速率的服務。該系統更適合支持多媒體流業務而并非在Internet中占主導地位的Web訪問等數據業務。因此，如何在不觸動網絡基礎設施的前提下改善無線Internet訪問的性能為研究者們提出了一個新的挑戰 [3，4] 。

針對上述問題，我們提出了一種基于代理的解決方案 [5，6] 。我們在GGSN (Gateway GPRS Support Node) 上設置了一個代理，將無線和有線網絡分割開來。通過在代理上引入類似于TCP分裂（Split TCP）的機制，可以有效地改善傳輸層的性能。同時，更重要的是在代理上可以方便地部署各種調度機制，通過適度地改變現有系統的工作模式來更好地支持無線Internet訪問。

在本文中，我們將詳細討論適應于新架構的調度機制的設計問題。與既有的針對無線系統的調度機制 [3，4] 不同，我們關注的焦點并不是最大化系統的容量，而是如何更好地使用現有的系統，在不加入新資源的前提下改善數據用戶的感觀。因此，新的調度機制將以單文件傳輸作為基本的調度單元，并使用平均響應時間作為系統性能的刻畫。本文將逐步揭示出通過合理地利用數據業務固有的特性（對延時和速率變化不敏感），我們可以極大地改善用戶側性能，縮短系統的平均響應時間。

2 基于代理的無線Internet訪問

Internet中的數據業務具有兩個區別，如語音業務的重要特性：①多數數據業務均是基于文件傳輸的，其目標是將一系列不同格式的文件從源節點傳輸到目的節點；②它對延時和速率變化不敏感。用戶并不在意短的延時和速率的變化，只關心完成每個獨立文件傳輸所用的平均時間。這些特征啟發我們針對文件傳輸過程設計一種調度機制，利用數據業務對延時的不敏感來改善系統的性能。

我們在GPRS/UMTS網絡中引入一個代理來幫助我們實現上述想法。代理位于無線網絡邊緣處的GGSN上，可以方便地獲得有關無線網絡的可用資源以及業務負載的信息。我們的代理可以看作是傳統的Web代理的一種擴展，它以文件為單位工作，主要執行以下三個方面的任務：

(1)緩沖。那些不能立即被傳輸的文件將被送入Cache緩存起來，等待調度。

(2)調度。依據無線資源以及當前負載狀況對文件傳輸過程進行調度，決定每個文件傳輸過程的啟動時間和傳輸速率。

(3)無線資源分配。代理與GGSN以及RNC協作，為每個文件傳輸過程建立RAB （Radio AccessBear），并分配適當的無線資源。

圖1示意了通過代理進行Internet訪問的典型過程。首先，無線終端向代理提交Web訪問的請求，代理接到請求后向Internet轉發。回送的網頁文件由代理緩存，排隊并等候調度。代理確認有足夠的無線資源可供使用后，選擇合適的速率建立RAB啟動文件傳送。文件傳輸結束后，RAB被釋放。

代理的引入將文件傳輸分隔成兩部分，分別使用兩個獨立的連接。從Internet看來，代理如同一個標準的Web客戶端，它請求網頁并緩存下載的文件。而代理與無線終端之間的下行數據連接則根據需要而創建。我們可以引入一個調度機制來決定何時創建連接，并決定連接實際使用的傳輸速率。

更進一步，我們可以對代理面向無線終端一側的TCP協議棧進行修改以提高其性能。注意到在GPRS網絡中，非擁塞丟包和超時會造成TCP擁塞窗口的錯誤變動，這是影響TCP性能的最重要的原因。然而，在我們的系統中無線信道由代理通過GGSN創建，因此代理知道有關發送速率的全部信息，它無須通過自適應的窗口調整來進行速率適配。因此，我們直接采用下行鏈路的帶寬時延積（BDP）作為代理下行的發送窗口大小。這十分類似于文獻[1]中所采用的TCP擁塞窗口鉗位技術，可以在不改動無線終端協議棧的前提下提高傳輸層性能。

具體而言，代理包括三個基本的模塊。其結構如圖2所示。其中緩存模塊用于緩存下載的文件；調度器管理文件傳輸的過程，決定發送的時機和速率；為了支持調度器的決策，我們使用檢測模塊監測系統容量和負載的變化。

在這個框架之下，可以應用不同的調度算法來優化系統性能。調度的對象是系統中下行文件的傳輸過程。調度算法的基本任務是依據網絡狀況來決定文件傳輸的啟動時間和傳輸速率。同時調度算法應盡可能避免在文件的傳輸過程中改變速率，以減少重新分配無線資源所引入的額外開銷。

我們采用了一種稱之為延時阻塞(Delay Block， DB)的調度策略。當代理工作在DB模式時，它相當于一個有限等待時間的排隊系統。下行的傳輸任務到達代理時，如果沒有足夠的無線資源，任務并不是被立即阻塞（Block），而是在緩存中排隊等候，等待正在進行的傳輸結束后，將無線資源被釋放出來。如果累積的等待時間超過某一個門限值（我們稱之為最長等待時間 θ ，它由HTTP的超時參數決定），則該任務被阻塞。工作在DB模式時，傳輸任務的啟動時間決定于隊列的狀態，而傳輸速率則由算法根據系統的狀態動態計算。后面的分析表明，適當選取速率可以顯著地改善系統性能。

需要特別指出的是，當 θ =0時，所有不能立即傳輸的任務都將被阻塞。此時，緩存中的隊列長度將始終為0，系統退化為現有的虛電路交換的工作模式。因此，現有系統也可以納入到我們的框架中，看作DB算法的一種特例。對于這樣的系統，阻塞概率可以用Erlang B公式計算，因此，我們稱之為Erlang Block (EB)。下一節我們將對DB和EB模式進行建模，分析其性能。

3 系統模型和性能分析

考慮UMTS系統中的一個典型小區，一組用戶通過GPRS進行Internet訪問。Web會話由一組Web文件的傳輸過程組成，中間間隔以用戶的閱讀時間 [4] 。為方便分析，在這一節中我們假設文件的到達是泊松過程，到達率為 λ ，而文件長度服從負指數分布，平均文件長度為 L 。在第4節中，我們將通過仿真對更為一般的業務模型進行研究。

眾所周知，UMTS系統的容量是噪聲受限的，當新用戶進入系統時，系統的噪聲升高。而當全系統的噪聲超過某一門限之后，系統將無法正常工作。為了簡化分析，我們假設所有的用戶均是相同的，均使用相同的數據率，都有著相同的信噪比要求，因而對系統增加的噪聲也都相同。在此假設下，給定信道比特率 R和目標信噪比E b/N o，我們可以使用式(1)計算單信道傳輸增加的噪聲 [7] ：

式中v是用戶的活動因子(Active Factor)，Ｗ是WCDMA的碼元速率(Chip Rate)，i是相鄰小區的干擾，α是下行信道正交因子(Orthogonality Factor)。

因此，系統支持的并發信道數由式(２)給出：

式中η_DL是下行鏈路因子（Down Link Factor）。

粗略地認為信道比特率R與用戶最終獲得的數據率r成正比，即r=kR，其中k是比例系數，當使用1/2速率的信道編碼時，k接近于0.5。

當工作在DB模式時，系統可以用有限忍耐度的M/M/c排隊系統（M/M/c Queueing System with Impatient Customer）進行建模。為研究這種特殊的排隊系統，我們引入一個虛擬任務，該任務的大小為0且不考慮超時。當虛擬任務進入系統時，它不會對其他任務產生影響，但卻可以用來監測系統的性能。我們將虛擬任務在系統中等待的時間U稱為系統提供的等待時間（Offered Waiting Time）。利用文獻[8]中的結論，U的分布為而當系統在EB模式下工作的時候，可以用M/M/c/c排隊系統建模，阻塞概率由下式給出（Erlang B公式）[9]：依據上述分析，畫出EB和DB兩種模式下系統的阻塞概率與負載之間的關系，如圖3所示。其中系統的基本參數為C=800kbps，L=30KB，c=4，8，16，32，64，等待時間的門限θ=0.3s。為保證系統的可用性，我們要求最大阻塞概率Pb*不超過1%。以此為基礎比較兩系統的性能可以明顯地看出，由于緩沖的引入，系統的利用率大大提高（表2）。

圖4給出了兩種模式下系統的平均響應時間，其中網絡利用率為80%。兩條曲線靠得很近，這說明在DB模式下工作時，由于排隊延時相對實際傳輸時間而言可忽略不計（事實上由于門限θ的存在，最大排隊時延也不會超過0.3s）。同時，從圖5可以看出，無論在哪一種模式下工作，為了獲得更短的平均響應時間均應當使用盡可能少的信道數。而可以工作的最小并行信道數則受制于阻塞概率的要求。同時，由表2可知，為保證1%的阻塞概率和接近80%的網絡利用率，在EB模式下必須使用64個信道，而DB模式下僅需16個信道。兩者所對應的平均響應時間分別為2.4s (EB)和0.66s (DB)。

工作在DB模式時，可以使用較少的并行信道數進行服務，同時保證阻塞概率和系統利用率的要求，其結果是單信道的傳輸速率得到提高。在考慮到排隊引入的額外開銷之后，系統的平均響應時間還是大大縮短了。下面的問題是，在一個給定的場景中，究竟應該使用多少個信道進行傳輸才能達到系統的最佳性能？這就是下一節信道分配算法關注的焦點。

4信道分配算法設計

4.1最優信道分配算法

DB模式下信道分配算法的設計目標是選擇適當的信道數，在保證基本的QoS要求的前提下盡可能縮短系統的平均響應時間。該目標可以表述為下面的最優化問題：

式中c是并行的信道數，ρ是網絡利用率，而P_b*和T_r*分別是用戶可容忍的最大阻塞概率和最大的平均響應時間，這兩個參量刻畫了用戶的基本QoS要求。系統實際的阻塞概率P_b和平均響應時間T_r分別由式（6）和式（8）給出。

通過圖5可以清楚地看出上述優化問題背后的物理意義。系統的任意一個狀態（c，ρ）均對應圖7上半部分中的一個點。圖中標明“阻塞邊界”的曲線對應于P_b(c，ρ)=P_b*的臨界情況，在該曲線之上的點無法滿足P_bb*的QoS要求。類似地，標明“延時邊界”的曲線對應于T_rDB=T_r*的約束。因此，兩條曲線之間的陰影部分是系統狀態的可行區域。另一方面，正如第3節分析中所指出的，為了獲得更短的響應時間，應當使用盡可能少的并行信道數。因此，最優的信道分配算法必將使系統狀態沿著“阻塞邊界”運動。同時，圖6中也畫出了EB模式下系統的可行區域，該區域明顯小于DB模式的可行區域。這從另一方面說明了DB模式可以獲得更好性能的原因。

綜上所述，我們得到下面的信道分配策略，它包括兩個部分：

4.2自適應信道分配算法（ACAA）

直接依照式（12）計算最優的信道數目在實際中并不可行，因為系統的負載不斷變化很難準確地測量，同時計算也過于復雜。因此，我們設計了一種自適應的信道分配算法替代上面的最優算法。算法的基本原理是在阻塞概率低于P_b*時減少信道數，而在高于P_b*時增加信道數。具體算法可以用下面的偽代碼描述：

set success_count_threshold=(1-P_b*) / P_b*

set success_count=0

set channel_num=2n

set channel_rate_high=C / channel_num

set channel_rate_low=C / channel_num

set transfer_rate=C / channel_num

transfer_rate_adjustment ()

if (file_transfer_timeout)

discard the timeout file

rate_degrade ()

else if (file_transfer_success)

set success_count=success_count + 1

if (success_count=success_count_threshold)

set success_count=0

rate_upgrade ()

endif

endif

rate_degrade ()

set channel_num=channel_num + 1

refresh_rate ()

set transfer_rate=channel_rate_low

rate_upgrade ()

set channel_num=channel_num - 1

refresh_rate ()

set transfer_rate=channel_rate_high

refresh_rate ()

set N= log (channel_num) / log(2)

set N1=the smallest integer that is greater than or equal to N

set N2=the largest integer that is less than or equal to N

set channel_rate_high=C / (2_N2)

set channel_rate_low=C / (2_N1)

圖7給出了仿真的結果，可以看出，ACAA算法的實際效果十分接近于最優算法，而相對于傳統的EB模式，平均響應時間大大縮短。更進一步，我們考慮文件長度具有重拖尾特性，服從有界的Pareto分布[10]。概率密度函數為取α=1.1，分別在平均文件長度L=10KB，20KB，30KB的條件下測試。測試結果如圖8所示。可以看出，在這種更一般的條件下，ACAA仍然表現出顯著優于EB的性能。

5 結論

本文提出了一種基于代理的體系結構用于改善在GPRS/UMTS網絡中進行無線Internet訪問的性能。代理的引入改變了原有網絡的工作模式，使我們可以方便地部署新的調度機制以提高系統的性能。在該框架之下，我們研究了一類稱之為Delay Block（DB）的調度策略。 DB調度器利用了數據業務對延時不敏感的特性，用少量的延時換取了網絡利用率的提高。更重要的是，我們發現通過合理選擇并行信道的數目，DB調度器不僅可以提高網絡利用率，還可以顯著降低系統的平均響應時間。因此，我們設計了兩種信道分配的算法，即最優信道分配算法和自適應信道分配算法，來輔助調度器工作。理論分析和 仿真表明，新的機制和算法可以顯著提高網絡利用率并縮短系統的平均響應時間。

參考文獻：

[1] Rajiv Chakravorty， Sachin Katti， Jon Crowcroft， et al .Flow Aggregation for

Enhanced TCP over Wide area Wireless [C]. Proceedings of the IEEE INFOCOM，2003.

[2] H Inamura， G Montenegro， R Ludwing， et al .TCP Over Second and Third Generation Wireless Networks[S]. RFC 3481， 2003.

[3] Sudhir Ramakrishna， Jack M Holtzman.A Scheme for Throughput Maximization in a Dual class CDMA System[J]. IEEE Journal on Selected Areas in Communications，1998，16(6):830-844.

[4] Cristina Comaniciu， Narayan B Mandayam， David Famolari， et al .Wireless Access to the World Wide Web in an Integrated CDMA System[J]. IEEE Transactions on Wireless Communications，2003，2(3):472-483.

[5] Yue Wang， Y H Song， Y Ren， et al .A Proxy based Framework to Enhance User Level Performance of GPRS/UMTS Networks [C]. IEEE WCNC， 2005.

[6] J X Lu， Yue Wang， Y H Song， et al .New QoS Metrics and Application Layer Proxy for GPRS/UMTS Internet Access[C]. Proc. of IEE QoS， 2004.

[7] H Holma， A Toskala.WCDMA for UMTS Radio Access for Third Generation Mobile Communications[M]. John Wiley Sons， 2000.

[8] Ali Movaghar.On Queueing with Customer Impatience until the Beginning of Service[J]. Queueing Systems， 1998，16(1):337-350.

[9] Donald Gross， Carl M Harris. Fundamentals of Queueing Theory，(2nd ed)[M]. New York: Wiley， 1985.

[10] Nikhil Bansal， Mor Harchol Balter.Analysis of SRPT Scheduling: Investigating Unfairness[C]. Proceedings of the ACM SIGMETRICS， 2001. 

作者簡介：王鉞(1977-)，男，博士研究生，主要研究方向為網絡流量控制；任勇（1963-），男，教授，主要研究方向為無線網絡協議；山秀明（1944-），男，教授，主要研究方向為復雜網絡整體動力學、信號處理；王耀希（1954-），男，研究員，主要研究方向為信息網絡、自動控制、項目管理。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。