跳到主要內容

臺灣博碩士論文加值系統

(3.236.124.56) 您好!臺灣時間:2021/08/02 07:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:王俊彥
研究生(外文):Chun-yen Wang
論文名稱:在無線多段網路下對即時群組通訊最小化訊框長度排程之研究
論文名稱(外文):Minimize Frame Length in Real-time Group Multicast Scheduling in Wireless Multi-hop Networks
指導教授:李忠憲李忠憲引用關係
指導教授(外文):Jung-Shian Li
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電腦與通信工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:84
中文關鍵詞:無衝突多個群組通訊樹排列多點跳躍的無線網路即時的串流來源樹鏈結排序
外文關鍵詞:Multiple Group Communication Trees Schedulingsource-based treeconflict-freelink schedulingmulti-hop wireless networkreal-time flowSTDMARMGCTS
相關次數:
  • 被引用被引用:0
  • 點閱點閱:102
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在本篇論文中,基於多個群組通訊的已知來源樹路由和鏈結排序,ㄧ個新穎且有效率的群組串流排程機制被提出來使訊框的長度最小化於多點跳躍(multi-hop)的無線網路環境上;稱之為「RMGCTS(Real-time Multiple Group Communication Trees Scheduling)」機制。為了去滿足不同的服務要求,舉例來說:每個來源樹的抖動率最小化,我們把RMGCTS區分成兩個種類,一個是「Back-to-Back RMGCTS」,另一個為「General-RMGCTS」。對於Back-to-Back RMGCTS來說,要求每一個群組通訊傳送一個封包都需要被完整的執行過一次且沒有中斷,才能換下一個群組通訊;後者General-RMGCTS則無此項要求,每一個群組通訊的部份可以被分開的排序。

我們證明兩者都是NP-complete的問題。但是我們的研究提出一個有效的演算法來獲得最佳化的結果在Back-to-Back RMGCTS中,稱之為BTBS演算法;它可以降低求得最佳化的複雜度由O(N!)到O((N^2)(2^N))。除此之外,本論文證明General-RMGCTS可以被表示成ILP(integer-linear programming)的數學描述式,而且每一個ILP的解都是一個General-RMGCTS的最佳排序。最後,本研究也提出一個有效的演算法,可以在多項式時間內求得一個近似的解,我們稱它LBL演算法。

本研究所提出來的演算法,都能夠展現出比最糟的情況排列方法(Tree-based RMGCTS)和純粹用顏色來排序(pure color scheduling algorithm)更顯著的效能。最後並發現,在固定的使用者點數下,訊框的長度與最大鄰居數成正比;在固定最大鄰居數下,訊框減少的百分比與使用者點數成正比。
In this thesis, a novel efficient multiple group stream scheduling scheme is proposed for minimizing frame length in multi-hop wireless networks given source-based trees and link scheduling called “Real-time Multiple Group Communication Trees Scheduling” (RMGCTS) scheme. To adapt different requirements, such as minimized jitter in each source-based tree, our research classifies RMGCTS into two categories, “Back-to-Back RMGCTS” and “General-RMGCTS”.

For Back-to-Back RMGCTS, each transmission of a packet in a one-to-all group communication tree should be scheduled without any interruption. It constrains the minimized jitter of each one-to-all group communication strictly. In General-RMGCTS, each part (i.e. link) in a one-to-all group communication can be scheduled without the back-to-back constraint.

We prove both of them are NP-complete. However, our research develops an efficient algorithm to attain the optimal solution in Back-to-back RMGCTS (complexity from O(N!) to O((N^2)(2^N)), called “BTBS (Back-to-Back scheduling)” algorithm. Furthermore, our research proves that the General-RMGCTS can be represented as an integer-linear programming (ILP) problem and the solution of the ILP is an optimal solution in General-RMGCTS. Moreover, we develop an algorithm in polynomial time to attain an approximate solution efficiently in General-RMGCTS, called “Level-by-Level” (LBL) algorithm.

Comparing to the worst case (the Tree-based RMGCTS) or the pure color scheduling scheme, our research shows a great performance improvement. We also find that the length of frame is proportional to number of degree in a specific number of nodes and the percentage of the decreased frame length is also proportional to number of node in a specific degree in RMGCTS.
Chapter1 Introduction.........1
1.1 Introduction.........1
1.2 Motivation and Contribution.........4
1.3 Organization.........6
Chapter2 Background.........7
2.1 Multicast and Group Communication.........7
2.2 Scheduling in Spatial Reuse.........9
2.3 Constraints.........11
2.3.1 Protocol model.........12
2.3.2 Physical Interference model.........15
2.4 Scheduling methods.........17
2.4.1 Link scheduling.........18
2.4.2 Node scheduling.........18
2.4.3 Scheduling procedure.........19
2.4.4 Clique scheduling.........22
Chapter3 Related work.........23
3.1 Store-and-forward scheduling algorithms.........24
3.2 Color table scheduling algorithms.........25
3.3 Real-time flow scheduling algorithms.........27
Chapter4 RMGCTS.........30
4.1 Network framework.........32
4.2 Problem Definition in RMGCTS.........33
4.3 Tree-based RMGCTS.........35
4.4 Pure Color Scheduling Algorithm.........37
4.5 Back-to-Back RMGCTS.........38
4.5.1 BTBS algorithm.........43
4.6 General-RMGCTS.........51
4.6.1 Linear Programming formulation for the General- RMGCTS problem...55
4.6.2 LBL scheduling algorithm.........61
Chapter5 Simulation results.........68
5.1 Color algorithm.........68
5.2 Multiple one-to-all group communication.........70
5.3 A simple scenario.........71
5.4 Simulation in random topology.........74
Chapter6 Conclusion.........80
References.........82
[1] Alberto Leon-Garcia, “Probability and Random Processes for Electrical Engineering,” Second edition, Prentice Hall, 1994.
[2] Douglas B. West, “Introduction to Graph Theory,” Second edition, Prentice Hall 2001.
[3] James F. Kurose, Keith W. Ross, “Computer Networking – a top-down approach featuring the Internet,” second edition, Addison Wesley, 2001.
[4] Richard E. Neapolitan, Kumarss Naimipour, “Foundations of algorithms using C++ pseudocode,” third edition, Jones and Bartlett publishers, 2004.
[5] IEEE Computer Society LAN MAN Standards Committee, IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Std 802.11-1997, The Institute of Electrical and Electronics Engineers, New York, 1997.
[6] Fenner W., “Internet group Management Protocol”, Version 2, RFC 2236, November 1997.
[7] Arash Behzad, Izhak Rubin, “Optimum integrated link scheduling and power control for multihop wireless networks,” IEEE Transactions On Vehicular Technology, Vol. 56, No.1, Page(s): 194-205, January 2007.
[8] A. Kabbani, T. Salonidis, and E. Knightly, "A Distributed Low-Complexity Maximum-Throughput Scheduler for Wireless Backhaul Networks," in Proceedings of IEEE INFOCOM 2007, Page(s): 2063-2071, May 2007.
[9] Bruce Hajek, Galen Sasaki, “Link scheduling in polynomial time,” IEEE Transactions on Information Theory, vol.34, NO.5, Page(s): 910-917, September 1988.
[10] Brian J. Wolf, Joseph L. Hammond, Daniel L. Noneaker, Harlan B. Russell, “A protocol for construction of broadcast transmission schedules in mobile ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 6, NO. 1, Page(s): 74-78, January 2007.
[11] Badia, L., Erta, A., Lenzini, L., Zorzi, M., "A General Interference-Aware Framework for Joint Routing and Link Scheduling in Wireless Mesh Networks," Network, IEEE , vol.22, no.1, pp.32-38, Jan.-Feb. 2008.
[12] Djukic P., Valaee S., "Link Scheduling for Minimum Delay in Spatial Re-Use TDMA",INFOCOM 2007. 26th IEEE International Conference on Computer Communications. Page(s):28 - 36.May 2007.
[13] Gangsheng Wang, Nirwan Ansari, “Optimal broadcast scheduling in packet radio networks using mean field annealing,” IEEE Journal on Selected Areas In Communications, Vol.15, No2, Page(s):250-260, February 1997.
[14] Gregory V. Chockler, Idid Keidar, Roman Vitenberg, "Group communication specifications: a comprehensive study," ACM Computing Surveys, Volume 33, Issue 4, Pages: 427 - 469, December 2001.
[15] Gandham, S., Dawande, M., Prakash, R., “Link scheduling in sensor networks: distributed edge coloring revisited”,INFOCOM 2005, vol. 4 ,page(s): 2492- 2501 ,March 2005.
[16] Hyungsuk Won, Han Cai, Do Young Eun, Guo, K., Netravali, A., Injong Rhee, Sabnani, K., "Multicast Scheduling in Cellular Data Networks," INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pp.1172-1180, May 2007.
[17] J.A. Chen and R.S. Chang, “A distributed link scheduling algorithm for CDMA packet radio networks”, International Journal of Wireless Information Networks, Vol. 2, No. 2, pp. 61-70, 1995.
[18] J. L. Hammond and H. B. Russell, "Properties of a transmission assignment algorithm for multiple-hop packet radio networks," IEEE Transactions on Wireless Communications, vol. 3, no. 4, pp. 1048-1052, July 2004.
[19] Jimmi Grönkvist,"Novel Assignment Strategies for Spatial Reuse TDMA in Wireless Ad hoc Networks," Wireless Networks, Volume 12, Number 2, pp. 255-265, April 2006.
[20] Li Li, Ramjee R., Buddhikot M., Miller S., “Network Coding-Based Broadcast in Mobile Ad-hoc Networks,” INFOCOM 2007, pp. 1739-1747, May 2007.
[21] Mohapatra, P., Chao Gui, and Jian Li,“Group communications in mobile ad hoc networks,” IEEE Computer Society, Volume 37, Issue 2,Page(s): 52-59, Feb 2004.
[22] Praveen K. Appani, oseph L. Hammond, Daniel L. Noneaker, Harlan B. Russell, "An adaptive transmission-scheduling protocol for mobile ad hoc networks," Ad Hoc Networks, Volume 5 , Issue 2, Page(s): 254-271, March 2007.
[23] Roberto Baldoni, "A Positive Acknowledgment Protocol for Causal Broadcasting," IEEE Transactions on Computers, Volume 47, Issue 12, Pages: 1341 - 1350, December 1998.
[24] S. Ramanathan and Errol L. Lloyd, “Scheduling Algorithms for Multi-Hop Radio Networks,” IEEE/ACM Trans. Networking, Page(s): 211-222, Apr. 1993.
[25] S. Ramanathan, “A unified framework and algorithm for channel assignment in wireless networks,” Wireless Networks, Volume 5, Issue 2, Pages: 81-94, March, 1997.
[26] S. L. Hakimi, “Steiner’s problem in graphs and its implications,” Network, Vol. 1(1997), pp. 113-133.
[27] Xiaojun Lin, Rasool S., "A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad-hoc Wireless Networks," INFOCOM 2007. 26th IEEE International Conference on Computer Communications. pp.1118-1126, May 2007.
[28] Yi,Y.,de Veciana,G.,Shakkottai,S.,"On Optimal MAC Scheduling With Physical Interference", INFOCOM 2007. 26th IEEE International Conference on Computer Communications, On page(s): 294-302., May 2007.
[29] AMPL and CPLEX: a modeling language and solvers for mathematical programming, available at http://www.ampl.com/
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top