隨著網路的蓬勃發展，新興的應用服務不斷湧現，其中群組通訊是近幾年中一個非常熱門的應用。由於大多數的群組通訊屬於即時式的傳輸使得它對於服務品質有一定的要求，像是傳輸的延遲時間、吞吐量以及公平性等。然而，因為現今無線多跳網路大多使用不可靠的媒體存取控制協定使得這些需求難以達到，故如何設計一個穩固的媒體存取控制協定便成為一個重要的研究議題。

因此，本篇論文研究在無線多跳網路有多個群組進行群播情況下，如何確保所有群播群組可以從各個來源到目的點完成一次無碰撞傳輸的排程問題。為了充分利用無線多跳網路的空間再利用特性，我們選用STDMA來排程。藉由以token來控制排程的方式，提出兩個具有分散式特性的節點排程演算法。其中一個在實做上較易實現，而另一個則是在空間利用率和token的繞送上有更好的效率。經由實驗模擬驗證我們提出的演算法在排程的成果上有較短的訊框長度。

Recently, more and more service applications have emerged. Multicast group communication is a popular application, and it usually has Quality of Service (QoS) requirements, such as limit of transmission time, throughput and fairness. However, such requirements may not be easily satisfied in wireless multi-hop networks since unreliable MAC mechanism is used in wireless networks.

In this thesis, we study the scheduling problem for multiple multicast communications in wireless multi-hop networks, which has to ensure that every multicast group can complete one transmission from the source to all destinations without conflict in a frame. Two distributed token based STDMA node scheduling algorithms are proposed that attempt to minimize the frame length. One proposed algorithm is simple and easy to implement in practice. The other one is enhanced to increase the percentage of reuse time slots and reduce the number of unnecessary token forwarding. Simulation results show that our algorithms outperform the existing ones in terms of frame length.

[1]Andrew S. Tanenbaum, “Computer Networks,” 4th ed. Prentice Hall, 2002.
[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, 2003.
[4]I. Chlamtac and S. S. Pinter, "Distributed nodes organization algorithm for channel access in a multihop dynamic radio network," IEEE Trans. Comput., pp.728-737, 1987.
[5]R. Ramaswami and K. K. Parhi, "Distributed Scheduling of Broadcasts in a Radio Network," in Proc. INFOCOM, 1989.
[6]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, pp. 74-78, January 2007.
[7]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.
[8]Praveen K. Appani, Joseph 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, pp. 254-271, March 2007.
[9]S. Ramanathan and Errol L. Lloyd, “Scheduling Algorithms for Multi-Hop Radio Networks,” IEEE/ACM Trans. Networking, pp. 211-222, Apr. 1993.
[10]H. Shen and W. Liang, "Efficient multiple multicast in WDM networks," in Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications, vol. 2, pp. 1028-1033, Jul. 1998.
[11]C. Diot, "Deployment Issues for the IP Multicast Service and Architecture," IEEE Network, pp.78 - 88, 2000.
[12]W. Fenner, “Internet Group Management Protocol,” Version 2, RFC 2236, November 1997.
[13]L. Wei and D. Estrin, "The tradeoffs of multicast trees and algorithms," Proc. Int. Conf. Comp. Comm. Networks, 1994.
[14]J. Zhu, X. Guo, L. L. Yang, W. S. Conner, “Leveraging Spatial Reuse in 802.11 Mesh Networks with Enhanced Physical Carrier Sensing,” Proceedings of IEEE ICC, 2004.
[15]P. Djukic and S. Valaee, "Link Scheduling for Minimum Delay in Spatial Re-Use TDMA," INFOCOM 2007. 26th IEEE International Conference on Computer Communications. pp.28 - 36.May 2007.
[16]G. Wang and N. Ansari, “Optimal broadcast scheduling in packet radio networks using mean field annealing,” IEEE Journal on Selected Areas In Communications, Vol.15, No2, pp.250-260, February 1997.
[17]L. Badia, A. Erta, L. Lenzini, M. Zorzi, "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.
[18]Y. Yi , G. de Veciana, S. Shakkottai, "On Optimal MAC Scheduling With Physical Interference," INFOCOM 2007. 26th IEEE International Conference on Computer Communications, pp. 294-302, May 2007.
[19]M. Joa-Ng and I.T. Lu., “Spread Spectrum Medium Access Protocol with Collision Avoidance in Mobile Ad-hoc Wireless Network,” In IEEE INFOCOM '99, pages 776-83, New York, NY, USA, 21-25 March 1999.
[20]X. Lin and S. Rasool, “A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad Hoc Wireless Networks,” Proc. IEEE INFOCOM, 2007.
[21]A. D. Gore, A. Karandikar, S. Jagabathula, "On high spatial reuse link scheduling in STDMA wireless ad hoc networks," IEEE Global Telecommunications Conference, GLOBECOM '07, pp. 736-741, Nov. 2007.
[22]J. 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]P. Djukic and S. Valaee, "Delay aware link scheduling for multi-hop TDMA wireless networks," IEEE/ACM Transactions on Networking, vol.17, no.3, pp. 870-883, June 2009
[24]A. Kabbani, T. Salonidis, E. Knightly, "A Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks," in Proceedings of IEEE INFOCOM 2007, pp. 2063-2071, May 2007.
[25]S. Sanghavi, L. Bui, R. Srikant, "Distributed link scheduling with constant overhead, " Proc. ACM SIGMETRICS, 2007.
[26]A. Ephremides and T. V. Truong, "Scheduling broadcasts in multihop radio networks," IEEE Trans. Commun., vol. 38, pp. 456 - 460 , 1990.
[27]I. Cidon and M. Sidi, “Distributed Assignment Algorithms for Multihop Packet Radio Networks,” IEEE Transactions on Computers, v.38 n.10, pp.1353-1361, October 1989.
[28]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.
[29]Chien-Hung Wu, “Efficient Real-time Group Multicast Node Scheduling Schemes in Wireless Multi-hop Networks,” National Cheng Kung University, Tainan, Taiwan. June 2010.