近年來,因為無線網路市場對於即時通訊服務(real-time services)的需求日益增加,網路服務品質保證(Quality of Service, QoS)變成了一個相當重要的議題,特別是在網路通訊協定的設計上面.然而,由於無線頻道容易遭遇受到干擾和一些不可預測的狀況,要設計一個好的無線媒介存取控制(Medium Access Control, MAC)協定,是件相當不容易的事.

在本論文中,我們分析了現存的MAC協定在處理即時通訊服務方面的缺陷,並且提出了一個完整的解決架構.為了提供無線區域網路(Wireless Local Area Networks, WLANs) QoS的支援,我們在架構中提出了一個基於排程演算法的中央管理式MAC協定;為了使得我們所提出的中央管理式MAC協定具備多點傳輸的能力,我們設計了一套多點傳輸(multihop)的機制.另外,由於在多路徑的傳輸過程中容易遺失原本被保證的QoS需求,我們發展了一個具備延遲感應(delay-sensitive)能力的公平排隊模組來補強此一缺陷.

我們所提出的中央式MAC協定是由一個時槽排程(slot-scheduling)演算法,以及一個增強QoS控管的允入控制(admission control)演算法所組成.時槽排程演算法的設計,是為了能有效率的利用網路的頻寬,並且公平的替各種服務作傳輸排程.允入控制演算法的設計,是為了能夠正確的管理頻寬資源以及保障每個服務的QoS需求.我們所提出的多點傳輸機制,可以套用在任何的中央式MAC協定和任何的網路拓樸上;此機制除了解除中央式MAC協定的封閉傳輸限制外,並能改善隱藏終端點(hidden terminal)問題.此外,為了確保所有的服務經過多點轉傳時也能兼顧到QoS的需求,我們在易變的WLAN上提出了一個具備延遲感應能力的公平排隊模組.這個模組可以延緩即時通訊服務的儲列(queue)成長速度,維持傳輸的公平性,並且保證每個網路節點的總吞吐量(throughput)會在一定程度以上.

我們也對於在論文中所提出的協定,機制,模組,提供了實驗和理論分析的模型,藉由這些模組,可以更容易的驗證這些技術的正確性與可行性.總言之,本論文的成果將有助於解決無線區域網路上QoS和多點傳輸方面的難題.

Since the demand for the wireless transmission of real-time services has been growing significantly in recent years, Quality of Service (QoS) becomes a very important issue in the design of network protocols. However, it is not trivial to design a good Medium Access Control (MAC) protocol which provides real-time services large amounts of bandwidth and also supports multihop transmission, since wireless channel suffers much interference and unpredictable problems.

In this dissertation, we analyze the performance of the existing wireless MAC protocols, and propose a framework which provides QoS supports and multihop transmission ability for Wireless Local Area Networks (WLANs). This framework consists of a centralized scheduling-based MAC protocol, a multihop mechanism, and a delay-sensitive fair queueing model.

The scheduling-based MAC protocol contains a slot-scheduling algorithm and a QoS enhanced admission control algorithm. The slot-scheduling algorithm is designed to efficiently utilize the network bandwidth and fairly schedule the transmission for various services while the QoS-enhanced admission control algorithm is designed to manage resources and guarantee the QoS requirements of services. The multihop mechanism that eliminates the restriction on single-hop transmission for centralized MAC protocols and alleviates the hidden terminal problem can be adapted to various protocols and network topologies. Moreover, to ensure that the services in relay stations meet their QoS requirements, the delay-sensitive fair queueing model is proposed for highly variant multihop WLANs. This queueing model slows down the growth of queue length for real-time services, still maintains the property of fairness, and guarantees the throughputs of stations.

This dissertation also provides experimental and analytical models for the proposed protocols, mechanisms and algorithms. With these models, the correctness and feasibility of our framework can be verified. Based on the achievements in this dissertation, the QoS issue in the multihop WLAN can be easily addressed.

[AC04] J.N. Al-Karaki and J.M. Chang, "EPCF: a Lightweight Multi-Priority PCF for QoS Support in IEEE 802.11 Wireless LANs", 2004 IEEE International Conference on Performance, Computing, and Communications, pp. 495-502, Phoenix, Arizona, April 2004.

[AKC00] C.W. Ahn, C.G. Kang and Y.Z. Cho, "Soft Reservation Multiple Access with Priority Assignment (SRMA/PA): A Novel MAC Protocol for QoS-Guaranteed Integrated Services in Mobile Adhoc Networks", Proceedings of IEEE VTC-Fall, Boston, MA, pp.942-947, New York, September 2000.

[Bia00] G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function", IEEE Journal of Selected Areas in Communications, vol. 18, no. 3, pp. 535-547, Mar 2000.

[BTC01] B. Bensaou, D.H.K. Tsang and K.T. Chan, "Credit-Based Fair Queueing (CBFQ): a Simple Service-Scheduling Algorithm for Packet-Switched Network", IEEE/ACM Transactions on Networking, vol.9, pp. 591-604, October 2001.

[BZ96] J.C.R. Bennett and H. Zhang, "WF2Q: Worst-Case Fair Weighted Fair Queueing", Fifteenth Annual Joint Conference of the IEEE Computer Societies (INFOCOM '96), pp. 120-128, San Francisco, CA, March 1996.

[CG00] R. Carces and J.J. Garcia-Luna-Aceves, "Collision Avoidance and Resolution Multiple Access for Multichannel Wireless Networks", Proceedings of IEEE Infocom 2000, pp. 595-602, March 2000.

[CK74] V. Cerf and R. Kahn, "A Protocol for Packet Network Intercommunications", IEEE Trans. on Communication, vol. 22, pp. 637-648, May 1974.

[CW04] Z.T. Chou and S.L. Wu, "A New QoS Point Coordination Function for Multimedia Wireless LANs", 24th International Conference on Distributed Computing Systems, Tokyo, pp. 40-47, Japan, March 2004.

[CWK+97] B.P. Crow, I. Widjaja, J.G. Kim and P.T. Sakai, "Investigation of the IEEE 802.11 Medium Access Control (MAC) Sublayer Functions", Proceedings of INFOCOM'97, vol. 1, pp. 126-133, 1997.

[DC99] D.J. Deng and R.S. Chang, "A Priority Scheme for IEEE 802.11 DCF access method", IEICE Transactions on Communications, pp. 96-102, 1999.

[DH98] J. Deng and Z. Haas, "Dual Busy Tone Multiple Access (DBTMA): A New Medium Access Control for Packet Radio Networks", Proceedings of IEEE ICUPC, Florence, Italy, 1998.

[DKS89] A. Demers, S. Keshav and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm", SIGCOMM Symposium on Communications Architectures and Protocols, pp. 1-12, Texas, USA, September 1989.

[DY05] D.J. Deng and H.C. Yen, "Quality-of-Service Provisioning System for Multimedia Transmission in IEEE 802.11 Wireless LANs", IEEE Journal on Selected Areas in Communications, vol. 23, pp. 1240-1252, 2005.

[FHF02] B. Fong, G.Y. Hong and A.C.M. Fong, "A Modulation Scheme for Broadband Wireless Access in High Capacity Networks", IEEE Transactions on Consumer Electronics, vol. 48, pp. 457-462, 2002.

[GVC96] P. Goyal, H.M Vin and H. Chen, "Start-Time Fair Queueing: a Scheduling Algorithm for Integrated Services", Proceedings of the ACM-SIGCOMM'96, pp. 157-168, Palo Alto, CA, August 1996.

[GW91] D.J. Goodman and S.X. Wei, "Efficiency of Packet Reservation Multiple Access", IEEE Trans. on Vehicular. Technology, vol. 40, pp. 170-176, Feb, 1991.

[HCG01] C. Heegrad, J. Coffey, S. Gummadi, P. A. Murphy, R. Provencio, E. J. Rossin, S. Schrum and M. B. Shoemake, "High Performance Wireless Ethernet", IEEE Communication Magazine, vol. 39, pp. 64-73, November, 2001.

[HLG02] W.C. Hung, K.L.E. Law and A.L. Garcia, "A Dynamic Multi-Channel MAC for Ad-Hoc LAN", Proceedings of the 21 st. Biennial Symposium on Communications pp. 31-35, April 2002.

[IEE02] IEEE draft std 802.15.3, "Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rate Wireless Personal Area Networks", Inst. Elec. Electron. Eng, New York, USA, 2002.

[IEE03] IEEE 802.11 WG, "Draft Supplement to STANDARD FOR Telecommunications and Information Exchange Between Systems - LAN/MAN Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Medium Access Control (MAC) Enhancement for Quality of Service (QoS)", IEEE 802.11e/D4.4, June 2003.

[IEE97] IEEE Std 802.11-1997, "Wireless LAN Medium Access Control (MAC) and Physical (PHY) Layer Specifications", IEEE 802.11, New York, USA, 1997.

[JD01] N. Jain and S. Das, "A Multichannel CSMA MAC Protocol with Receiver-Based Channel Selection for Multihop Wireless Networks", Proceedings of the 9th Int. Conference on Computer Communications and Networks, October 2001.

[JMA01] M. Jeong, H. Morikawa and T. Aoyama, "A Fair Scheduling Algorithm for Wireless Packet Networks", IEICE Trans. of Fundamental, vol. 84, no. 7, pp.1624-1635, July 2001.

[JMB01] D.B. Johnson, D.A. Maltz and J. Broch, "DSR: the Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks", Ad Hoc Networking, Addison-Wesley, ch. 5, pp. 139-172, 2001.

[Joh99] M. Johnson, "HiperLAN/2 - the Broadband Radio Transmission Technology Operating in the 5GHz Frequency Band", available via the H/2 Global Forum version 1.0, http://www.hiperlan2.com, 1999.

[KL03] A. Kanjanavapastit and B. Landfeldt, "An Analysis of a Modified Point Coordination Function in IEEE 802.11", 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, pp. 1732-1736, Beijing, China, September 2003.

[KTB+04] Z.N. Kong, D.H.K. Tsang, B. Bensaou and D. Gao, "Performance Analysis of IEEE 802.11e Contention-Based Channel Access", IEEE Journal on Selected Areas in Communications, vol. 22, pp. 2095-2106, 2004.

[LAS01] A. Lindgren, A. Almquist and O. Schelen, "Evaluation of Quality of Service Schemes for IEEE 802.11 Wireless LANs", Proceedings of LCN 2001, 26th Annual IEEE Conference, pp. 348-351, Florida, USA, November, 2001.

[LBD+00] P. Lin, B. Bensaou, Q.L. Ding and K.C. Chua, "A Wireless Fair Scheduling Algorithm for Error-Prone Wireless Channels", Proceedings of the 3rd ACM International Workshop on Wireless Mobile Multimedia, August 2000.

[LBS99] S. Lu, V. Bharghavan, and R. Srikant, "Fair Scheduling in Wireless Packet Networks." IEEE/ACM Transactions on networking, vol. 7, no. 4, pp. 473-488, August 1999.

[LH00] Y.D. Lin and Y.C. Hsu, "Multihop Cellular: A New Architecture for Wireless Communications", Proceedings of IEEE INFOCOM, pp. 1273-1282, 2000.

[LYG04] H. Li, D. Yu and Y. Gao, "Spatial Synchronous TDMA in Multihop Radio Network", IEEE 59th Vehicular Technology Conference, pp. 1334-1338, Spring 2004.

[MCM+02] S. Mangold, S. Choi, P. May, O. Klein, G. Hiertz and L. Stibor, "IEEE 802.11e Wireless LAN for Quality of Service", Proceedings of the European Wireless, vol. 1, pp. 32-39, Florence, Italy, Feb. 2002.

[MG98] A. Muir and J.J. Garcia-Luna-Aceves, "A Channel Access Protocol for Multihop Wireless Networks with Multiple Channels", Proceedings of IEEE ICC '98, pp.1617-1621, June 1998.

[MKS02] K. Mizuno, M. Katayama and H. Suda, "A New QoS-Guaranteed Multichannel MAC Protocol for Multihop Wireless Networks", IEEE 55th Vehicular Technology Conference, pp. 967-971, May 2002.

[MS98] M.J. Markowski and A.S. Sethi, "Fully Distributed Wireless MAC Transmission of Real-Time Data", 4th IEEE Real-Time Technology and Application Symposium, pp.49-57, Denver, CO, June 1998.

[MWN+03] X. Ma, Y. Wu, Z. Niu and T. Saito, "Performance Analysis of the Packetized Voice Transmission with PCF in an IEEE 802.11 Infrastructure Wireless LAN", The 9th Asia-Pacific Conference on Communications, pp. 571-575, Penang, Malaysia, September 2003.

[ND00] A. Nasipuri and S.R. Das, "Multichannel CSMA with Signal Power-Based Channel Selection for Multihop Wireless Networks", Proceedings of IEEE Vehicular Technology Conference, September 2000.

[NLB02] T. Nandagopal, S. Lu and V. Bharghavan, "A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms", Wireless Networks, vol.8, March 2002.

[NO00] K. Nakano and S. Olariu, "Randomized Initialization Protocols for Ad Hoc Networks", IEEE Transactions on Parallel and Distributed System, vol. 11, pp. 749-759, 2000.

[NSZ98] T.S.E. Ng, I. Stoica and H. Zhang, "Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors", In Proceedings of IEEE INFOCOM, 1998.

[NZD99] A. Nasipuri, J. Zhuang and S.R. Das, "A Multichannel CSMA MAC Protocol for Multihop Wireless Networks", Proceedings of IEEE Wireless Communications and Networking Conference, September 1999.

[Pee01a] J. Peetz, "HiperLAN/2 Multihop Ad Hoc Communication by Multiple-Frequency Forwarding", Proceedings of Vehicular Technology Conference, pp. 2118-2122, May 2001.

[Pee01b] J. Peetz, "A Concept for Interconnecting HiperLAN/2 Ad Hoc Subnets Operating on Different Frequency Channels", Proceedings of the 4th European Personal Mobile Communications Conference session 21, 2001.

[PG93] A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control - The Single Node Case", ACM/IEEE Transactions on Networking, vol. 1, pp. 344-357, June 1993.

[PWS+04] R. Pabst, B.H. Walke, D.C. Schultz, P. Herhold, H. Yanikomeroglu, S. Mukherjee, H. Viswanathan, M. Lott, W. Zirwas, M. Dohler, H. Aghvami, D.D. Falconer and G.P. Fettweis, "Relay-Based Deployment Concepts for Wireless and Mobile Broadband Radio", IEEE Communication Magazine, pp. 80-89, September 2004.

[RA98] P. Ramanathan and P. Agrawal, "Adapting Packet Fair Queueing Algorithms to Wireless Networks", ACM MOBICOM'98, pp.1-9, 1998.

[RGC04] A. Raniwala, K. Gopalan, and T.C. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks", Mobile Computing and Communications Review, vol. 8, no. 2, pp. 50-65, 2004.

[SK96] J.L. Sobrinho and A.S. Krishnakumar, "Real-Time Traffic over the IEEE 802.11 Medium Access Control Layer", Bell Labs Technical Journal, pp. 172-187, 1996.

[SK99] J.L. Sobrinho and A.S. Krishnakumar, "Quality-of-Service in Ad Hoc Carrier Sense Multiple Access Wireless Networks", IEEE Journal on Selected Areas in Communications, vol. 17, no.8, pp. 1353-1368, 1999.

[SLW+04] J.P Sheu, C.H Liu, S.L. Wu and Y.C. Tseng, "A Priority MAC Protocol to Support Real-Time Traffic in Ad Hoc Networks", Wireless Networks, vol.10, pp. 61-69, 2004.

[SS01] S.T. Sheu and T.F. Sheu, "DBASE: A Distributed Bandwidth Allocation/Sharing/Extension Protocol for Multimedia over IEEE 802.11 Ad Hoc Wireless LAN", Proceedings of INFOCOM'01, vol. 3, pp. 1558-1567, 2001.

[SV03] J. So and N.H. Vaidya, "A Multi-Channel MAC Protocol for Ad Hoc Wireless Networks", Technical report, Dept. of Comp. Science, Univ. of Illinois at Urbana-Chamapign, 2003.

[SV04] J. So and N.H. Vaidya, "Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using a Single Transceiver", Proceedings of ACM MobiHoc pp.222-233, May 2004.

[TG01] A. Tzamaloukas and J.J. Garcia-Luna-Aceves, "A Receiver-Initiated Collision-Avoidance Protocol for Multi-Channel Networks", Proceedings of IEEE INFOCOM, 2001.

[TG99] Z. Tang and J.J. Garcia-Luna-Aceves, "Hop-Reservation Multiple Access (HRMA) for Ad-Hoc Networks", Proceedings of IEEE INFOCOM, 1999.

[TKN03] Technical Report TKN-03-019, "An IEEE 802.11e EDCF and CFB Simulation Model for NS-2", Telecommunication Networks Group, Berlin, Germany, 2003.

[VBG00] N.H. Vaidya, P. Bahl and S. Gupta, "Distributed Fair Scheduling in a Wireless LAN", Sixth Annual International Conference on Mobile Computing and Networking, Boston, August 2000.

[WC01] K. Wang and Y.L. Chin, "A Fair Scheduling Algorithm with Adaptive Compensation in Wireless Networks", IEEE Global Telecommunications Conference, vol.6, pp. 25-29, November 2001.

[WLT+00] S.L. Wu, C.Y. Lin, Y.C. Tseng and J.P. Sheu, "A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks", Int's Symposium on Parallel Architectures, Algorithms and Networks, 2000.

[YS93] O. Yaron and M. Sidi, "Performance and Stability of Communication Networks via Robust Exponential Bounds", IEEE/ACM Transactions on Networks, vol. 1, pp. 372-385, 1993.

[ZF02] L. Zhao and C. Fan, "M-PCF: Modified IEEE 802.11 PCF Protocol Implementing QoS", Electronic Letter, vol. 38, pp. 1611-1613, 2002.