在本篇論文中，基於多個群組通訊的已知來源樹路由和鏈結排序，ㄧ個新穎且有效率的群組串流排程機制被提出來使訊框的長度最小化於多點跳躍(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.

[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/