無線網狀網路(wireless mesh networks)是一種廣為人知的網路架構，近年來，其相關應用服務亦呈現快速的成長。此類網路主要是運用預先佈建的無線路由器(mesh router)，藉由這些路由器與上網的閘道器(gateway)間互相連結，讓使用者能夠連上網際網路，並形成無線網狀網路的骨幹(backbone)。
由於，無線的環境中，頻寬是較為缺乏的資源且頻道屬於共享式的媒介，因此，群播成為一項重要的通訊技術。尤其，當無線網狀網路的環境中，大量資料需求者針對同一份資料作擷取的動作時，閘道器即可利用群播技術將資料傳送至這些具有相同資料需求的使用者手上，除了提供更有效率的通訊，更能減少無線頻寬的消耗。雖然群播的問題被廣為研究，但是由於大多數的機制並沒有將無線網路的廣播特性加以考量，所以，當應用於無線網路時，無法令其頻寬的利用充分發揮。
在這篇論文中，我們主要探討在無線網狀網路的環境中，如何妥善地利用無線廣播的特性以建立出有效率且低成本的群播樹，且透過此架構將資料從單一或多個網路閘道器推播至資料群組節點。由於我們將無線廣播的特性加入機制的設計中，因此，資料推播成本的計算將由考慮最小化傳遞鏈節數，重新定義為最小化轉傳節點數量。

A wireless mesh network (WMN) is a well-known access network for Internet connectivity. Recently, WMNs are undergoing rapid progress and inspiring numerous applications. In WMNs, a collection of wireless routers forms a mesh of self-configuring, self-healing links among themselves. With interspersed gateways, mobile devices are enabled to be connected to the Internet through mesh routers. The mesh routers have minimal mobility and form the mesh backbone for mesh clients.
In wireless networks, transmission bandwidth is typically limited and communication channels are often shared media, hence, multicast become one of the important communication paradigms. In particular, when a number of data requesters access the same source of data in the WMNs, a gateway may use multicast technique to send the data to those requesters that have the same demands. This may lead to more efficient communications among a group of nodes, and help reduce bandwidth consumption. Although multicast technique has been widely studied in wireless networks, many multicast mechanism have not been usually considered about the broadcast nature of wireless media and therefore are not able to make full use of the bandwidth of networks.
In this thesis, we study the problem of constructing a cost-efficient multicast tree in wireless mesh networks while taking broadcast nature of wireless communication into consideration. We then use the tree structure to push the data from the gateway to these data requesters. We reformulate the communication cost in terms of the number of relay nodes, rather than the number of links, required for performing the multicast operation.

[1] I. F. Akyildiz, Xudong Wang, and Weilin Wang, “Wireless mesh networks: a survey,” Computer Networks, vol. 47, Issue 4, pp. 445-487, Mar. 2005.
[2] J. Berst, “What’s all wrong with today’s push technology,” ZDNet Anchor Desk, http://www5.zdnet.com/anchordesk/story/, 1997.
[3] S. E. Deering, “Host Extensions for IP Multicasting,” RFC 1112, Aug. 1989.
[4] K. Gerwig, “The push technology rage . . . so what’s next?,” in ACM Digital
[5] T. Hara, “Effective Replica Allocation in Ad Hoc Networks for Improving Data Accessibility,” in Proc. of IEEE INFOCOM, pp. 1568-1576, Apr. 2001.
[6] T. Hara, “Replica Allocation in Ad Hoc Networks with Periodic Data Update,” in Proc. Of Intl. Conf. on Mobile Data Management, pp. 79–86, Jan. 2002.
[7] R.M. Karp, “Reducibility among combinatorial problems,” Complexity of Computer Computations, 1972.
[8] R. H. Katz, et. al., “Bay area research wireless access network (BARWAN),” IEEE Computer Society International Conference, pp. 15-20, 1996.
[9] L. Kou, G. Markowsky, and L. Berman, “A fast algorithm for Steiner trees,” Acta Informatica, vol. 15, pp.141–145, 1981.
[10] H, Lim and C. –K. Kim, “Multicast Tree Construction and Flooding in Wireless Ad Hoc Networks,” ACM MSWiM, Aug. 2000.
[11] J. Moy, “Multicast Routing Extensions for OSPF,” Communications of the ACM, VOL. 37, NO. 8, pp. 61-67, Aug. 1994.
[12] J. Plesnik, “Complexity of Designing a Network With Minimum Diameter,” NETWORKS. vol. 11, no. 1, pp. 77-85. 1981.
[13] P. M. Ruiz and A. F. Gomez-Skarmeta, “Heuristic Algorithms for Minimum Bandwidth Consumption Multicast Trees in Wireless Mesh Networks,” Lecture Notes in Computer Science vol. 3738, pp. 258–270, Oct. 2005.
[14] S. Rajagopalan and V. V. Vazirani, “On the bidirected cut relaxation for the metric Steiner tree problem,” in Proc. of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 742–751, 1999.
[15] W. R. Stevens, “TCP/IP Illustrated, Volume 1,” Addision-Wesley , pp. 169-186, 1994.
[16] Y.C. Tseng, S.Y. Ni, Y.S. Chen and J.P. Sheu, “The broadcast storm problem in a mobile ad hoc network”, ACM Wireless Networks, vol. 8, no. 2, pp. 153-167, Mar. 2002
[17] J.E. Wieselthier, G.D. Nguyen, and A. Ephremides, “Energy-efficient broadcast and multicast trees in wireless networks,” Mobile Networks and Applications, pp. 481-492,2002
[18] D. Waitzman, C. Partridge, and S. E. Deering, “Distance Vector Multicast Routing Protocol,” RFC 1075, Nov. 1988.
[19] L. Yin and G. Cao, “Supporting Cooperative Caching in Ad Hoc Networks,” Proc. of IEEE INFOCOM, pp. 2537-2547, 2004.
[20] C.-R. Young and G.-M. Chiu, “Efficient Dissemination of Transaction-Consistent Data in Broadcast Environments,” IEEE Trans. on Knowledge and Data Engineering, vol. 19, no. 3, pp. 384-397, March 2007.
[21] A. Zelikovsky, “An 11/6-approximation algorithm for the network Steiner problem,” Algorithmica, no. 9, pp.463–470, 1993.