本論文主要研究在多點跳躍(multi-hop)的無線網路中，基於已知的來源樹路由和無碰撞限制進行多個群組傳播時，如何最小化訊框長度的節點排程問題，稱之為OCF-MGCS(In-Order Collision-Free Multiple Group Communications Scheduling)」問題，我們證明此問題為NP-complete且可以被表示為ILP(integer-linear programming)的數學描述式，而ILP的解都是一個OCF-MGCS的最佳排序，在此我們提出一個新穎且有效率的演算法在多項式時間內可以求得近似解，稱之B-LBL演算法，它的複雜度為O(N2)。再者，不同於鏈結排程，B-LBL利用節點的廣播傳輸特性展現出更好的排程效能;因為通道的多重存取和串流排程機制，使得B-LBL能展現比Tree-based排程演算法和pure color排程演算法有更顯著的效能。
此外，我們為了解決在無線網路中的暴露站台問題(exposed terminal problem)，特別提出一個新穎且同時擁有通道多重存取和節點廣播的特性，稱之CA-LBL演算法。在不造成群組傳輸失敗的前提下，CA-LBL為了提升通道使用率而允許部分無關緊要的碰撞，雖然違反了OCF-MGCS中無碰撞的限制但卻有比B-LBL更好的效能。值得一提，CA-LBL藉由直接地篩選限制項來取代一般著色演算法，不僅能確保成功傳輸亦能避免一般著色演算法中的顏色決定問題(determining color problem)。模擬結果顯示CA-LBL確實有著比其他節點排程演算法更好的效能，節點排程;暴露站台問題;STDMA;無衝突;來源樹;即時的串流;多點跳躍的無線網路;OCF-MGCS而且在固定使用者點數下，隨著最大鄰居數的增加，訊框的長度僅些許變化。

In this thesis, we study for minimizing frame length of group communications in node scheduling, which is based on wireless multi-hop networks given source-specific tree and collision-free, called “In-Order Collision-Free Multiple Group Communications Scheduling (OCF-MGCS)”problem. We prove that OCF-MGCS problem is NP-complete and can be represented as an integer-linear programming (ILP) problem. The solution of the ILP is an optimal solution in OCF-MGCS. Here we develop a novel algorithm in polynomial time to attain an approximate solution efficiently in OCF-MGCS, called “ Broadcasting Level-by-Level ” (B-LBL) algorithm. The complexity of B-LBL is O(N2). Unlike link scheduling, the performance of B-LBL is much better because of the characteristic of “Broadcast”. Moreover, the effect of “Spatial reuse” and stream scheduling scheme make the result that the performance of B-LBL is better than Tree-based scheduling algorithm and pure color scheduling algorithm separately.
Furthermore, for conquering the exposed terminal problem in wireless networks, we propose a new node scheduling algorithm, which has the characteristic of “Spatial reuse” and “Broadcast”, called “Collision Allowed Level-by-Level” (CA-LBL) algorithm. Under the condition that guaranteeing group communications form fail, CA-LBL allows partial and lesser collisions to increase the utilization of channel. Even though CA-LBL is against the collision-free in OCF-MGCS, the performance of CA-LBL is much better than B-LBL. By the way, for guaranteeing group communications form fail and avoiding the determining color problem in general color algorithms, CA-LBL filters constraints directly rather than general color algorithms. In the simulations, the performance of CA-LBL is better than other node scheduling algorithm certainly. Finally, we find that the frame length of CA-LBL varies little as the number of maximal degree increases in a specific number of nodes.

[1] Alberto Leon-Garcia, “Probability and Random Processes for Electrical Engineering,” Second edition, Prentice Hall, 1994.
[2] Andrew S. Tanenbaum, “Computer Networks”, 4th ed. Prentice Hall, 2002.
[3] Douglas B. West, “Introduction to Graph Theory,” Second edition, Prentice Hall 2001.
[4] James F. Kurose, Keith W. Ross, “Computer Networking – a top-down approach featuring the Internet,” second edition, Addison Wesley, 2003.
[5] Richard E. Neapolitan, Kumarss Naimipour, “Foundations of algorithms using C++ pseudocode,” third edition, Jones and Bartlett publishers, 2004.
[6] 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.
[7] Fenner W., “Internet group Management Protocol”, Version 2, RFC 2236, November 1997.
[8] 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.
[9] 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.
[10] Bruce Hajek, Galen Sasaki, “Link scheduling in polynomial time,” IEEE Transactions on Information Theory, vol.34, NO.5, Page(s): 910-917, September 1988.
[11] 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.
[12] 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.
[13] C. G. Prohazka, “Decoupling link scheduling constraints in multi-hop packet radio networks,” IEEE Trans.Comput., vo1. 38, no. 3, pp. 455–458, Mar. 1989.
[14] D.S. Stevens and M.H. Ammar, Evaluation of slot allocation strategies for {TDMA} protocols in packet radio networks, in IEEE MILCOM, Vol. 2 (1990) pp. 835–839.
[15] 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. 67
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] Li Li, Ramjee R., Buddhikot M., Miller S., “Network Coding-Based Broadcast in Mobile Ad-hoc Networks,” INFOCOM 2007, pp. 1739-1747, May 2007.
[24] L. Kleinrock and J. Silvester, “Spatial reuse in multihop packet radio networks,” Proc. IEEE, vol. 75, no. 1, pp. 156–167, Jan. 1987.
[25] 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.
[26] 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.
[27] Roberto Baldoni, "A Positive Acknowledgment Protocol for Causal Broadcasting," IEEE Transactions on Computers, Volume 47, Issue 12, Pages: 1341 - 1350, December 1998.
[28] R. Nelson and L. Kleinrock, “Spatial TDMA: A collision-free multihop channel access protocol,” IEEE Trans. Commun., vol. COM-33, no. 9, pp. 934–944, September 1985.
[29] S. Ramanathan and Errol L. Lloyd, “Scheduling Algorithms for Multi-Hop Radio Networks,” IEEE/ACM Trans. Networking, Page(s): 211-222, Apr. 1993.
[30] S. Ramanathan, “A unified framework and algorithm for channel assignment in wireless networks,” Wireless Networks, Volume 5, Issue 2, Pages: 81-94, March, 1997. 68
[31] S. L. Hakimi, “Steiner’s problem in graphs and its implications,” Network, Vol. 1(1997), pp. 113-133.
[32] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A Media Access Protocol for Wireless LAN’s,” in Proc. ACM SIGCOMM, vol. 24, no. 4, Aug. 1994, pp. 212-225
[33] 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.
[34] 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.
[35] LINGO: a modeling language and solvers for mathematical programming, available at http://www.lindo.com/
[36] Chun-Yen Wang, “Minimize Frame Length in Real-time Group Multicast Scheduling in Wireless Multi-hop Networks”, National Cheng Kung University, Tainan, Taiwan. July 2007