簡易檢索 / 詳目顯示
| 研究生： |
李益豪 |
|---|---|
| 論文名稱： |
無線網路下的排程:權重式輪循法 Scheduling in wireless networks: a weighted round robin approach |
| 指導教授： | 蔡榮宗 |
| 學位類別： |
碩士 Master |
| 系所名稱： |
資訊教育研究所 Graduate Institute of Information and Computer Education |
| 論文出版年： | 2002 |
| 畢業學年度： | 90 |
| 語文別： | 英文 |
| 論文頁數： | 97 |
| 中文關鍵詞： | 權重式輪循法 、馬可夫串列 、排程 、公平性 |
| 英文關鍵詞： | weighted round robin, Markov chain, scheduling, fairness |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：176 下載：1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
我們提出一種無線環境中下行(downlink)傳輸排程的方法，叫做Error Avoidance Weighted Round Robin(EAWRR)。EAWRR能夠有效地利用無線頻寬並提供有限的公平性。能達到這些特性主要是藉由整合GPS的方法到WRR並加以改進，以保證有效的頻寬利用。此外，EAWRR沒有GPS計算虛擬時間的負擔，整體的實作複雜度更低。另外，由於我們假設系統在傳送封包前不偵測無線傳輸的品質，因此可減少跟基地台間的控制訊息交換，連帶也就節省了移動設備的電力消耗﹔而為了更進一步提高頻寬的使用效率，我們提出了另一個改良機制叫List-Reordering，或簡稱EAWRR-LR。基本上，EAWRR-LR哲學是避免使用有錯誤的無線連結(wireless link)，而盡量使用品質好的無線連結。雖然EAWRR主要是設計在下行網路，但未來希望可以應用在上行網路。
[1] A. Bedekar, S. Borst, K. Ramanan, P. Whiting, and E. Yeh, “Downlink Scheduling In CDMA Data Networks,” in Proc. IEEE GLOBECOM, 1999.
[2] A. K. Parekh, and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case”, IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 344-357, June 1993.
[3] C. Fragouli, V. Sivaraman, and M. B. Srivastava, “Controlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queuing with Channel-State-Dependent Packet Scheduling,” in Proc. IEEE INFOCOM, 1998.
[4] D. A. Eckhardt, and P. Steenkiste, “Effort-limited Fair(ELF) Scheduling for Wireless Networks,” in Proc. IEEE INFOCOM, 2000.
[5] D. Stiliadis, and A. Varma, “Rate-Proportional Servers: A Design Methodology for Fair Queueing Algorithms”, IEEE/ACM Trans. Networking, vol. 6, no. 2, pp. 164-174, April 1998.
[6] G. Koole, V. Universiteit, Z. Liu, and R. Righter, “Optimal Transmission Policies for Noisy Channels,” preprint.
[7] H. M. Chaskar and U. Madhow, “Fair scheduling with tunable latency: A Round Robin approach”, in Proc. IEEE GLOBECOM, 1999.
[8] J. Gomez, A. T. Campbell, and H. Morikawa, “A System Approach to Prediction, Compensation and Adaptation in Wireless Networks”, in ACM WOWMOM ’98, Dallas, TX, Oct. 1998, pp. 92-100.
[9] J-S Kim, and D. C. Lee, “Weighted round robin packet scheduler using relative service share”, IEEE MILCOM 2001, Vol. 2 , Page(s): 988 –992
[10] L. Tassiulas, and A. Ephremides, “Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity,” IEEE Trans. Inform. Theory, vol. 39, no. 2, pp. 466-478, Mar. 1993.
[11] M. R. Jeong, H. Morikawa, and T. Aoyama, “Fair Scheduling Algorithm for Wireless Packet Networks”, Parallel Processing, 1999. Proceedings. 1999 International Workshops on , 1999 Page(s): 280 –285
[12] P. Bhagwat, P. Bhattacharya, A. Krishna, and S. Tripathi, “Enhancing throughput over wireless LANs using Channel State Dependent Packet Scheduling,“ in Proc. IEEE INFOCOM, 1996.
[13] P. Ramanathan, and P. Agrawal, “Adapting Packet Fair Queueing Algorithms to Wireless Networks,” The fourth annual ACM/IEEE international conference on Mobile computing and networking ,Oct. 1998.
[14] S. Borst and P. Whiting, “Dynamic Rate Control Algorithms for HDR Throughput Optimization,” in Proc. IEEE INFOCOM, 2001.
[15] S. Bucheli, J. R. Moorman, J. W. Lockwood, and S.-M Kang, ”Compensation Modeling for QoS Support on a Wireless Network,” in Proc. IEEE GLOBECOM 2000.
[16] S. Deb, M. Kapoor, and A. Sarkar, “Error Avoidance In Wireless Networks Using Link State History,” in Proc. IEEE INFOCOM, 2001.
[17] S. Lu, V. Bharghavan, and R. Srikant, “Fair Scheduling in Wireless Packet Networks,” IEEE/ACM Trans. Networking, vol. 7, no. 4, pp. 473-489, Aug. 1999.
[18] S. Shakkottal, and R. Srikant, “Scheduling Real-time Traffic With Deadlines over a Wireless Channel,” Proceedings of the second ACM international workshop on Wireless mobile multimedia , Aug. 1999.
[19] T. S. Eugene Ng, I. Stoica, and H. Zhang, “Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors,” in Proc. IEEE INFOCOM, 1998.
[20] V. Bharghavan, S. Lu, and T. Nandagopal, “Fair Queuing in Wireless Networks: Issues and Approaches,” IEEE Personal Communications Magazine, vol. 6, Issue: 1 , pp. 44 –53, Feb. 1999.
[21] W. K. Wong, Y. Qian, and V. C. M. Leung, “Scheduling for Heterogeneous Traffic in Next Generation Wireless Networks”, in Porc. IEEE GLOBECOM 2000.
[22] X. Liu, Edwin K. P. Chong, and Ness B. Shroff, “Transmission Scheduling for Efficient Wireless Utilization,” in Proc. IEEE INFOCOM, 2001.
[23] Y. Cao, and V. O. K. Li, “Scheduling Algorithms in Broad-Band Wireless Networks,” Proceedings of the IEEE , Volume: 89 Issue: 1 , Jan. 2001 Page(s): 76 –87
[24] Z. Jiang, and N. K. Shankaranarayana, “Channel Quality Dependent Scheduling for Flexible Wireless Resource Management,” in Proc. IEEE GLOBECOM 2001.
[25] J. C. R. Bennett and H. Zhang, “WF2Q: Worst-case fair weighted fair queueing,” in Proc. IEEE INFOCOM, 1996.
[26]S. Golestani, “A self-clocked fair queueing scheme for broadband applications,”in Proc. IEEE INFOCOM, 1994.
[27] S. Lu, T. Nandagonpal, and V. Bharghavan, “Design and analysis of algorithm for fair service in error-prone wireless channels,” IEEE Wireless Networks, vol. 6, pp.323-343, 2000.
[28] L. D. Servi, “Capacity Estimation of Cyclic Queues”, IEEE Trans. Commun., vol. COM-33, No.3, pp279-282, Mar. 1985.
[29] L. D. Servi, “Average Delay Approximation of M/G/1 Cyclic Service Queues with Bernoulli Schedules,” IEEE J. Select. Areas Commun. , vol. SAC-4, No.6, Sep. 1986.
[30] D. Berteskas, and R. Gallager, Data Networks ,2nd Ed, Prentice Hall, 1992.
[31] R. Fantacci, and L. Zoppi, “Performance Evaluation of Polling Systems for Wireless Communication Networks,” IEEE Trans. Veh. Technol., vol. 49, No.6, pp.2148-2157, Nov. 2000.
[32] H. Levy and M. Sidi, “Polling systems: Applications, modeling , and optimization,” IEEE Trans. Commun., vol. 38, pp. 1750-1760, Oct. 1990.
[33] J. Keilson and L. D. Servi, “Oscilating Random Walk Models for GI/G/1 Vacation Systems with Bernoulli Schedules,” J. Appl. Prob. 23, pp790-802, 1986.