本篇論文主要是研究無線通訊網路的排程(scheduling)演算法。由於行動載具日新月異，很多手持式設備都已經可以播放多媒體影音檔案，然而播放即時影音串流(stream)並不是很順暢，主要原因在於IEEE 802.11e 網路仍無法保證即時影音串流傳輸的服務品質(Quality of Service, QoS)。因此本篇論文會簡單介紹所提出針對IEEE 802.22e 的排程演算法。
本論文討論的排程演算法是運作在感知無線電網路(cognitive radio network)中，也是本篇論文主要研究的演算法，由於無線通訊越來越發達，越來越多的無線通訊技術被發明出來，因此很多的頻譜都已經分配給這些無線通訊技術。然後過去的測量[7]發現，很多頻譜的利用率都不是很高。為了解決這個問題，IEEE802.22 標準因而被發展出來。IEEE 802.22 是以感知無線電(cognitive radio)為基礎，然而IEEE 802.22 並沒有針對Scalable Video Coding (SVC)編碼的多媒體影音串流來定義QoS 機制。因此，為了解決這個問題，本篇論文提出一個以賽局理論(Game Theory)為基礎的跨層(cross-layer)資源分配演算法。此演算法可以根據多媒體影音串流的特性來調整一些參數，讓無線網路的傳輸能適應網路的情況，以達到資源分配最佳化。本篇論文最後的模擬也證明，此演算法不只可以保證多媒體影音串流的傳輸品質，也可以達到資源分配的公平性。
最後的部份，本篇論文還討論多頻道的無線網路環境中時間分配演算法
(TAA)。TAA 專注於SVC 編碼的多媒體影音串流傳輸。在多頻道(multiple channel)的網路環境中，TAA 沒有專屬的控制頻道可以交換訊息，每個使用者(或是行動裝置)會根據本身所擁有的跳躍序列(hopping sequence)來切換頻道。模擬結果證明，TAA 可以有效地分配傳送時間給同頻道中的傳送接收對(source-destination pair)，並且能夠保證多媒體影音串流的傳輸品質。

This dissertation mainly studies the scheduling algorithms. First algorithm in chapter one is about the transmission of live videos and will be simple introduced. The remainder of this dissertation is the major focus, i.e. cognitive radio network.
Recently, the widespread use of mobile devices has led to a rapid growth of wireless local area networks (WLANs). The ability of mobile device is powerful enough to play the video files. However, playing live video is not smooth. That is because the limited capabilities of WLANs and characteristics of live videos such as burstiness and long range dependence, efficient transmission of live videos. Therefore, guaranteeing the quality of service over WLANs have become challenging problems.
Major focus of this dissertation is scheduling algorithm in cognitive radio network. The available unlicensed spectrum is increasingly being used by new wireless technologies, but past measurements [7] show that the licensed spectrum is extremely underutilized. To address this issue, the IEEE 802.22 Working Group is developing a novel wireless air interface standard based on Cognitive Radios (CRs), i.e. IEEE 802.22 wireless regional area networks (WRANs). Moreover, over the last decade wireless multimedia applications have developed rapidly, raising significant concerns about the quality of service of multimedia stream transmissions. In particular, the Joint Video Team (JVT) and ITU-T Video Coding Experts Group (VCEG) jointly proposed Scalable Video Coding as the next generation multimedia compression standard. However, the current IEEE 802.22 WRAN draft does not specify QoS mechanisms for SVC-encoded multimedia stream transmission in CR networks. To resolve this problem, this dissertation developed a cross-layer resource allocation algorithm (CLRAA) and a novel Media Access Control (MAC) protocol to work with the algorithm. The CLRAA adapts to the characteristics of multimedia traffic and variations of wireless channels by determining the weighting of source-destination pair, which is determined by the deadlines of SVC-encoded multimedia streams, the queueing delay and channel conditions. The CLRAA then allocates transmission opportunities to source-destination pairs based on their weightings and game theory. This dissertation also conducted extensive simulations to demonstrate the efficiency of the CLRAA scheme. The simulation results show that the CLRAA scheme not only guarantees QoS for multimedia traffic but also achieves fairness across different streams.
Finally, this dissertation additionally discusses the time allocation algorithm (TAA) in the network with multiple channels. The TAA focuses on the transmission of SVC-encoded multimedia streams. In multiple channel MAC (McMAC), there is not a dedicated control channel and all users (or mobile devices) follow their own hopping sequences to switch channels, respectively. The simulation results show that the TAA can efficiently allocate time to source-destination pairs which are in the same channel. The simulation results also show that the QoS of multimedia stream can be guaranteed.

[1] M. Krunz and S. K. Tripathi, 1997, Scene-based characterization of VBR MPEG-compressed video traffic, ACM Sigmetrics
[2] Y.-H. Tseng, H.-K. Wu, and G.-H. Chen, 2007, Scene-change aware dynamic bandwidth allocation for real-time VBR video transmission Over IEEE 802.15.3 wireless home networks, IEEE Trans. on Multimedia, 9, 3, 642-654.
[3] P. Seeling, F. H.P. Fitzek, and M. Reisslein, 2006, Video Traces for Network Performance Evaluation, Springer.
[4] F. H.P. Fitzek, and M. Reisslein, 2001, MPEG-4 and H.263 Video Traces for Network Performance Evaluation, IEEE Network, 15, 6, 40-54.
[5] P. Seeling, M. Reisslein, and B. Kulapala, 2004, Network Performance Evaluation Using Frame Size and Quality Traces of Single-Layer and Two-Layer Video: A Tutorial, IEEE Communications Surveys and Tutorials, 6, 2, 58-78.
[6] WEN-KUANG KUO, KUO-WEI WU. “Traffic Prediction and QoS Transmission of Real-time Live VBR Videos in WLANs”
[7] Shared Spectrum Company, www.sharedspectrum.com.
[8] Yucek T, Arslan H. A Survey of Spectrum Sensing Algorithms for Cognitive Radio Applications. IEEE Communications Surveys & Tutorials, First Quarter 2009, Vol. 11, No. 1: 116–130. DOI: 10.1109/SURV.2009.090109
[9] Ekram Hossain, Long Le, Natasha Devroye and Mai Vu. Cognitive Radio: From Theory to Practical Network Engineering. New Directions in Wireless Communications Research, 2009, 251-289, DOI: 10.1007/978-1-4419-0673-1_10
[10] Ghurumuruhan Ganesan and Ye (Geoffrey) Li. Cooperative Spectrum Sensing in Cognitive Radio Part I: Two User Networks. IEEE Transactions on Wireless Communications, Volume: 6 , Issue: 6, DOI: 10.1109/TWC.2007.05775
[11] Ganesan, G. and Li Ye. Cooperative Spectrum Sensing in Cognitive Radio Part II: Multiuser Networks. IEEE Transactions on Wireless Communications, 2007, Volume: 6 , Issue: 6, 2214 – 2222, DOI: 10.1109/TWC.2007.05776
[12] Haiquan Wang, En-hui Yang, Zhijin Zhao, and Wei Zhang. Spectrum Sensing in Cognitive Radio Using Goodness of Fit Testing. IEEE Transactions on Wireless Communications, 2009, Volume:8 , Issue:11, 5427–5430, DOI: 10.1109/TWC.2009.081586.
[13] Parthapratim De and Ying-Chang Liang. Blind Spectrum Sensing Algorithms for Cognitive Radio Networks. IEEE Transactions on Vehicular Technology, 2008, Volume: 57 , Issue: 5, 2834 – 2842, DOI: 10.1109/TVT.2008.915520.
[14] Hou-Shin Chen, Wen Gao, and David G. Daut. Spectrum Sensing for OFDM Systems Employing Pilot Tones. IEEE Transactions on Vehicular Technology, 2008, Volume: 57, Issue: 5, 2834 – 2842, DOI: 10.1109/TVT.2008.915520
[15] Stevenson C, Chouinard G, Lei ZD, Hu WD, Shellhammer S, Caldwell W. IEEE 802.22: The First Cognitive Radio Wireless Regional Area network Standard. Communications Magazine, IEEE, 2009, Vol. 47: 130–138, DOI: 10.1109/MCOM.2009.4752688
[16] Cordeiro C, Challapali K, Birru D, Sai Shankar N. IEEE 802.22: An Introduction to the First Wireless Standard based on Cognitive Radios. Journal of Communications, April 2006, Vol. 1, No. 1.
[17] Van der Auwera G, David PT, Reisslein M. Traffic and Quality Characterization of Single-Layer Video Streams Encoded with the H.264/MPEG-4 Advanced Video Coding Standard and Scalable Video Coding Extension. IEEE Transactions on Broadcasting, September 2008, Vol. 54, No. 3: 698-718, DOI: 10.1109/TBC.2008.2000422
[18] Geert Van der Auwera, Prasanth T. David, Martin Reisslein, and Lina J. Karam. Traffic and Quality Characterization of the H.264/AVC Scalable Video Coding Extension. Advances in Multimedia, January 2008, Volume 2008 Issue 2, DOI:10.1155/2008/164027
[19] Schwarz, H, Marpe, D and Wiegand, T. Overview of the Scalable Video Coding Extension of the H.264/AVC Standard. IEEE Transactions on circuits and systems for video technology, September 2007, Vol. 17, No. 9: 1103–1120. DOI: 10.1109/TCSVT.2007.905532
[20]: “Game Theory”, Drew Fudenberg, Jean Tirole, The MIT Press
[21] Fattahi AR, Fu FW, Van der Schaar M, Paganini F. Mechanism-Based Resource Allocation for Multimedia Transmission over Spectrum Agile Wireless Networks. IEEE Journal on Selected Areas in Communications, April 2007, Vol. 25, No. 3: 601–612, DOI: 10.1109/JSAC.2007.070410
[22] Yonghong Zhang and Cyril Leung. Cross-Layer Resource Allocation for Mixed Services in Multiuser OFDM-Based Cognitive Radio Systems. IEEE Transactions on Vehicular Technology, 2009, Volume: 58 , Issue: 8, 4605 – 4619, DOI: 10.1109/TVT.2009.2020801
[23] Jian Tang, Roberto Hincapié, Guoliang Xue, Weiyi Zhang and Roberto Bustamante. Fair Bandwidth Allocation in Wireless Mesh Networks with Cognitive Radios. IEEE Transactions on Vehicular Technology. 2010, Volume: 59, Issue: 3, 1487–1496, DOI: 10.1109/TVT.2009.2038478
[24] Anh Tuan Hoang and Ying-Chang Liang. Downlink Channel Assignment and Power Control for Cognitive Radio Networks. IEEE Transactions on Wireless Communications. 2008, Volume: 7 , Issue: 8, 3106 – 3117, DOI: 10.1109/TWC.2008.070022
[25] Buljore, S., Harada, H., Filin, S., Houze, P., Tsagkaris, K., Holland, O., Nolte, K., Farnham, T. and Ivanov, V. Architecture and Enablers for Optimized Radio Resource Usage in Heterogeneous Wireless Access Networks: The IEEE 1900.4 Working Group. IEEE Communications Magazine, 2009, Volume: 47 , Issue: 1, 122 – 129, DOI: 10.1109/MCOM.2009.4752689
[26] K.–C. Chen, Y.–J. Peng, N. Prasad, Y.–C. Liang and S. Sun. Cognitive Radio Network Architecture: Part I – General Structure. ICUIMC '08, DOI:10.1145/1352793.1352817
[27] Kaneko S, Nomoto S, Ueda T, Nomura S, Takeuchi K. Predicting Radio Resource Availability in Cognitive Radio - an Experimental Examination. Cognitive Radio Oriented Wireless Networks and Communications, 2008, 1–6, DOI: 10.1109/CROWNCOM.2008.4562504
[28] Li XK, Zekavat SA. Traffic Pattern Prediction and Performance Investigation for Cognitive Radio Systems. IEEE Wireless Communications and Networking Conference 2008; 894-899, DOI: 10.1109/WCNC.2008.163
[29] Wen ZG, Luo T, Xiang WD, Majhi S, Ma YH. Autoregressive Spectrum Hole Prediction Model for Cognitive Radio Systems. IEEE International Conference on Communications Workshops 2008, ICC Workshops '08, 154-157, DOI: 10.1109/ICCW.2008.34
[30] Min R, Qu DM, Cao Y, Zhong GH. Interference Avoidance Based on Multi-step-ahead Prediction for Cognitive Radio. 11th IEEE Singapore International Conference on Communication Systems 2008, ICCS 2008, 227–231, DOI: 10.1109/ICCS.2008.4737177
[31] Yarkan S, Arslan H. Binary Time Series Approach to Spectrum Prediction for Cognitive Radio. IEEE Vehicular Technology Conference, VTC-2007, Fall 2007, 1563-1567, DOI: 10.1109/VETECF.2007.332
[32] Kim H, Shin KG. Fast Discovery of Spectrum Opportunities in Cognitive Radio Networks. 3rd IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks, 2008, DySPAN 2008, 1-12, DOI: 10.1109/DYSPAN.2008.30
[33] ftp://ftp.tnt.uni-hannover.de/pub/svc/testsequences
[34] John Nash. Non-cooperative Games. Annals of Mathematics. September 1951, Vol. 54, No. 2
[35] JSVM Software Manual. JSVM 6.8.1, Sep. 25, 2006
[36] Qing Zhao, Lang Tong, Ananthram Swami and Yunxia Chen. Decentralized Cognitive MAC for Opportunistic Spectrum Access in Ad Hoc Networks: A POMDP Framework. IEEE Journal on Selected Areas in Communications. 2007, Volume: 25, Issue: 3, 589 – 600, DOI: 10.1109/JSAC.2007.070409
[37] Piazza, D., Cosman, P., Milstein, L.B. and Tartara, G. A Resource Allocation Algorithm for Real-Time Streaming in Cognitive Networks. IEEE Wireless Communications and Networking Conference, 2009. WCNC 2009, 1–5, DOI: 10.1109/WCNC.2009.4917542
[38] Butun, I., Cagatay Talay, A., Turgay Altilar, D., Khalid, M. and Sankar, R. Impact of Mobility Prediction on the Performance of Cognitive Radio Networks. IEEE Wireless Telecommunications Symposium (WTS), 2010, 1 – 5, DOI: 10.1109/WTS.2010.5479659
[39] Shankar, N.S., Cordeiro, C. and Challapali, K. Spectrum Agile Radios: Utilization and Sensing Architectures. IEEE DySPAN 2005, DOI: 10.1109/DYSPAN.2005.1542631
[40] http://agg.cs.ubc.ca
[41] Albert Xin Jiang, Kevin Leyton-Brown and Navin A.R. Bhat. Action-Graph Games. Games and Economic Behavior, 2010

[42] G. van der Laan, A.J.J. Talman, and L. van der Heyden. Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labelling. Mathematics of Operations Research, 1987, 12(3):377–397
[43] Gupta, U. and Ranganathan, N. A Game Theoretic Approach for Simultaneous Compaction and Equipartitioning of Spatial Data Sets. IEEE Transactions on Knowledge and Data Engineering, 2010, Volume: 22, Issue: 4, 465–478, DOI: 10.1109/TKDE.2009.110
[44] Jeonghoon Mo, Hoi-Sheung Wilson So, “Comparison of Multichannel MAC Protocols”, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 7, NO. 1, JANUARY 2008
[45] Hoi-Sheung Wilson So, Jean Walrand, “Design of A Multi-Channel MAC Protocol for Ad Hoc Wireless Networks”, Technical Report No. UCB/EECS-2006-17
[46] Tung-Yen Lu, “Resource Allocation for Wireless Mesh Networks”, thesis for master, Institute of Computer and Communication Engineering, National Cheng-Kung University.
[47] Hongyan Li, Yibing Gai, Zhiqiang He, Kai Niu and Weiling Wu, “Optimal Power Control Game Algorithm for Cognitive Radio Networks with Multiple Interference Temperature Limits”, Vehicular Technology Conference, 2008.
[48] Drew Fudenberg, Jean Tirole, “Game Theory”, The MIT Press, 1911
[50] Throughput Fairness Index: An Explanation. ATM Forum Document No. ATM_Forum/99-0045, Feb. 1999.
[51] Jahanzeb Farooq, Bilal Rauf, “An Overview of Wireless LAN Standards IEEE 802.11 and IEEE 802.11e”, Department of Computing Science, UMEA University, Sweden