IEEE 802.11 無線網路免競爭期間允入控制之最佳化

Optimization of Call Admission Control in IEEE 802.11 WLAN Contention-Free Periods

施翔騰(Hsiang-Teng Shih)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.02103

摘要

隨著網際網路的快速發展，許多的資料傳輸相關應用已是人們日常生活中不可或缺的一部分。而無線網路所提供不受實體限制的便利性，更讓行動通訊成為當前炙手可熱的議題之一。

由於市場的快速成長，在無線區域網路 (wireless LAN)上提供即時及多媒體服務的需求與日遽增，因此相關的服務品質保證 (Quality of Service, QoS)成為是否可讓使用者得到較佳傳輸品質的重要關鍵。然而無線網路與傳統有線網路在本質上就有許多截然不同的特性；加上在IEEE 802.11標準中，主要是以載波偵測多重存取及碰撞避免法 (CSMA/CA : Carrier Sense Multiple Access with Collision Avoidance) 為其媒介存取控制協定 (Medium Access Control protocol)。在這樣的前提之下，需要一套更有效率的機制用以提供相關的服務品質保證。

在本篇論文中，我們提出將IEEE 802.11 WLAN的免競爭期間 (contention-free period) 以時槽 (time slot) 方式加以切割的概念，並配合IEEE 802.11e的標準，考量四種不同優先等級的資料訊框型態 (data frame type)。因此，在有限的無線頻譜 (wireless spectrum) 資源下，不同的時槽分配策略 (policy) 及允入控制 (call admission control) 機制將會導致系統有不同的收益、效能及服務品質。再者，使用者QoS的需求與系統收益常存在著互為消長的關係，因此我們希望能在提供不同資料訊框差異化品質保證 (Differentiated Service, DiffServ) 的同時，最佳化整個系統的長期收益。

本研究針對IEEE 802.11免競爭期間時槽分配的問題，提出兩種數學模型。兩者的目的皆為在給定不同資料訊框的流量參數後，找出一個最好的時槽分配策略，藉以最佳化系統的長期收益。兩個模型的主要差別在於時間的型態，第一個模型是考慮連續的時間 (Continuous-Time) ，而第二個模型是考慮離散 (Discrete) 的形式。由於這兩個數學模型的結構及問題規模的特性，我們利用馬可夫決策過程 (Markovian Decision Process) 來解決我們的問題。

由優異的實驗數據結果顯示，我們成功地以馬可夫決策過程在我們提出的數學模型下，找到使整體系統長期收益最大化的時槽分配原則。而建構於該基礎上的解題程序比起一般的經驗法則，更可使收益達到數倍以上的成長，證明我們的方法可以提供系統營運者及網路規劃人員良好的決策。

關鍵字

DiffServ ； IEEE 802.11 ； 服務品質保證 ； 無線區域網路 ； 允入控制 ； 時槽分配 ； 馬可夫決策過程 ； 媒介存取控制協定 ； CSMA/CA ； IEEE 802.11e

並列摘要

With the rise of the Internet, now many data transfer applications are essential to people’s daily life. In addition, wireless networks can support people’s mobility to access information regardless of where they are. Hence mobile communication has become a popular topic in today’s technology world.

Due to the rapid growth of the wireless LAN market, the need of transmitting real-time and multimedia traffic, such as voice, images, video and …, etc, over wireless LAN will gradually increase. Therefore, the relevant Quality of Service (QoS) problem has also become a critical issue. However, as there are some inherent differences between wireless networks and traditional wired networks. So with this pre-determined condition, such as using CSMA/CA in its MAC protocol under IEEE 802.11, we will need more and more effective mechanism to provide QoS assurance.

In this thesis, we bring up the concept of slotting the contention-free period in IEEE 802.11 WLAN. In addition, to be compatible with IEEE 802.11e, we consider four data frame types with different priorities. As a result, in the limited wireless spectrum resource, different slot allocation policy will generate results varying in revenue, throughput and QoS of the system. However, there is always a tradeoff between the users’ QoS requirement and the system revenue. Therefore, we hope to provide differentiated service while maximizing the long-term system revenue.

We propose two mathematical models to solve the slot allocation problem in this thesis. The goal of our model is to find the best slot allocation policy to maximize the long-term system revenue under the capacity constraint. The main difference is the time type. The first model is continuous-time, while the second one is discrete-time. We apply Markovian Decision Process to deal with our problem due to the problem size and the structure of our model.

According to the good computational results, we can successfully find the best slot allocation policy that maximizes the long-term system profit by Markovian Decision Process. Compared with the heuristics that venders often use, the policy we find has great improvement in the system revenue. Therefore, our model can indeed provide good decision for system venders and network planners.

並列關鍵字

CSMA/CA ； Time Slot Allocation ； IEEE 802.11 ； Quality of Service ； IEEE 802.11e ； Call Admission Control ； WLAN ； MAC Protocol ； Markovian Decision Process ； DiffServ

參考文獻

[2] IETF “Differentiated Service” Working Group.

[5] I. Aad, and C. Castelluccia, “Differentiation Mechanisms for IEEE 802.11,” IEEE INFOCOM 2001, vol. 1, pp.209-218, Apr. 2001.

[6] A. Grilo, and M. Nunes, “Performance Evaluation of IEEE 802.11e,” The 13th IEEE International Symposium on Indoor and Mobile Radio Communications, vol.1, pp.511-517, Sep. 2002.

[8] R.A. Howard, “Dynamic Programming and Markov Process,” sixth printing, Wiley, 1970.

[10] B. Kolman, “Introductory Linear Algebra with Applications,” sixth edition, Prentice-Hall, Inc, 1997.