無線網路由於無線設備的普及和網路社區迅速地擴充，在過去幾年間吸引了許多的注意。無線隨建即連網路（Wireless Ad Hoc Network），不同於一般常見的無線結構式網路（Wireless Infrastructure Network），其是一群沒有固定連結且彼此需相互溝通的移動節點集合。每個節點動態地發現能與其直接溝通的其他節點，並且擔任路由器的角色協助其他節點傳遞封包。由於無線節點移動頻繁，無線隨建即連網路的網路拓樸時常改變且不可預知，因此資料傳遞路線排定和多點廣播（Multicast）變成非常地具有挑戰性。
　　這篇論文主要介紹一個以序列及拓樸為基礎的多點廣播編碼方式（A Sequence and Topology encoding for Multicast Protocol, STMP），並將其應用在配置有全球定位系統接收器的無線隨建即連網路(Ad Hoc Network)節點。各節點廣播其從全球定位測量衛星取得的位置資訊，每個節點能更新它本地端的網路拓樸。並且藉由與OLAM做模擬比較，發現這個多點廣播工作路線排定機制，確實能提高多點廣播傳送時的效率，並降低行動主機CPU運算的負荷，並減少網路頻寬的消耗。

　　An ad hoc network is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Due to the limited radio propagation range of wireless devices, routes are often “multi-hop.” Nodes in these networks move arbitrarily, thus network topology changes frequently and unpredictably. Moreover, bandwidth and battery power are limited. These constraints, in combination with the dynamic network topology make routing and multicast in ad hoc networks extremely challenging.
　　In this paper, we introduce a novel Sequence and Topology encoding for multicast protocol (STMP) in a wireless Ad Hoc network equipped with GPS unit in every node. The mobile nodes with GPS receivers can get the measures from GPS unit; accordingly each node updates its local snapshot of the network topology. The thesis is to find a multicast routing mechanism can reduce the number of packet forwarding and improve the efficiency of ad hoc network routing scheme in such a dynamical environment. The resulting multicast tree based on the mechanism is then encoded by using Sequence and Topology encoding with two integer sequences. Simulation results show that the protocol is more efficient than OLAM that the multicast source can easily computes the situations for all the nodes in the multicast tree，and each node does not have to handle the processes of decoding and encoding when the packet is receiving and forwarding.

[1]A. Dolan and J. Aldous, “Networks and Algorithms – An Introductory Approach”, John Wiley & Sons, 1993.
[2]Beongku An, Symeon Papavassiliou, “A mobility-based hybrid multicast routing in mobile ad-hoc wireless networks”, MILCOM 2001 - IEEE Military Communications Conference, no. 1, October 2001 pp. 316-320
[3]B.Boldon, N. Deo, and N. Kumar. “Minimum-weight degree-constrained spanning tree problem: heuristic and implementation on an AIMD parallel machine,” Technical Report CS-TR-95-02, Department of Computer Science, University of Central Florida, Orlando, Jan. 1995.
[4]C. W. Wu, Y.C. Tay, and C.-K. Toh, “Ad hoc Multicast Routing protocol utilizing Increasing id-numberS （AMRIS） functional Specification”, Internet–Draft draft-ieft-manet-amris-spec-00.txt, Nov. 1998, Work in progress.
[5]Deering, S. and Cheriton, D., “Multicast Routing in Datagram Internetworks and Extended LANs”, ACM Transactions on Computer System, Vol.8, No. 2, May 1990, PP. 85-111.
[6]De Morais Cordeiro, C. Gossain, H. Agrawal, D.P.,” Multicast over wireless mobile ad hoc networks: present and future directions”, Network, IEEE , Volume: 17 , Issue: 1 , Jan.-Feb. 2003,Pages:52 – 59.
[7]E. Bommaiah, M. Liu, A. McAuley, and R. Talpade, “AMRoute: Adhoc Multicast Routing Protocol,” Internet-Draft, draft-talpade-manet-amroute-00.txt, Aug. 1998, Work in progress.
[8]G. Xu, D. Dougherty, and T. Lillys, “Computing the minimum cost pipe network by interior-point branch-and-bound method,” In Conference On Network Optimization problems, Gainesville, FL., Feb. 12-14 1996.
[9]Gupta, S.K.S.; Srimani, P.K.,” Adaptive core selection and migration method for multicast routing in mobile ad hoc networks”, Parallel and Distributed Systems, IEEE Transactions on , Volume: 14 , Issue: 1 , Jan. 2003,Pages:27 – 38.
[10]H. Prüfer, “Neuer beweis eines stazes über permutation,” Arch, Math. Phys., Vol. 27, 1918, pp. 742-744.
[11]Internet Engineering Task Force （IETF） Mobile Ad Hoc Networks （MANET） Working Group Charter. http://www.ietf.org/html.charters/manet-charter.html.
[12]J.J. Garcia-Luna-Aceves and E.L. Madruga, “Core-Assisted Mesh Protocol,” IEEE Journal On Selected Areas in Communications, Vol. 17, no. 8, Aug. 1999, pp. 784-792.
[13]K. Malik and G. Yu. “A branch and bound algorithm for the capacitated minimum spanning tree problem,” Networks, Vol. 23, No. 6, 1993, pp.525-532.
[14]M. Gen, K. Ida and J. KIM, “A spanning tree-based genetic algorithms for bicriteria topological network design,” In Proceedings of IEEE International conference on Evolutionary Computation, 1998, pp. 15-20.
[15]M. Gen and R. Cheng, Genetic algorithms and engineering design, John Wiley & Sons, Inc., New York , 1997.
[16]Sung-Ju Lee; Su, W.; Hsu, J.; Gerla, M. and Bagrodia, R.; “A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols.” INFOCOM 2000, Nineteenth Annual Joint Conference of IEEE Computer and communications Societies. Proceedings, IEEE vol:2 :2000, pages 565-574.
[17]S.J. Lee, M. Gerla, and C.-C Chiang, “On-Demand Multicast Routing Protocol,” In Proceedings of IEEE WCNC’99, New Orleans, LA, Sep. 1999, pp. 1298-1304.
[18]S. Basagni, I. Chlamtac, V. R. Syrotiuk and R. Talebi, “On-Demand Location Aware Multicast （OLAM） for Ad Hoc Networks,” Wireless Communications and Networking Conference, 2000. WCNC, 2000 IEEEE, Volume:3, pages 1323-1328.
[19]S. Basagni, I. Chlamtac, V. R. Syrotiuk. “Geographic messaging in wireless ad hoc networks.” In Proceedings of the IEEE 49th International Vehicular Technology Conference, volume 3, Pages 1957-1961, Houston, TX, May. 16-20 1999.
[20]S.J. Lee, M. Gerla, and C.-C Chiang, “On-Demand Multicast Routing Protocol”, In Proceedings of IEEE WCNC’99, New Orleans, LA, Sep. 1999, pp. 1298-1304.
[21]Tzu-Chiang Chiang; Yueh-Min Huang,” Group keys and the multicast security in ad hoc networks”, Parallel Processing Workshops, 2003. Proceedings. 2003 International Conference on , 6-9 Oct. 2003,Pages:385 – 390.
[22]Tzung-Shi Chen, Yuh-Shyan Chen, Hua-Wen Tsai, “A Hierarchy-Based Multicast Protocol for Wireless Mobile Ad-Hoc Networks”, Ninth IEEE International Conference on Networks (ICON'01), Bangkok, Thailand, October 10 - 12, 2001.
[23]Vijay Devarapalli, Ali A. Selcuk, Deepinder Sidhu “Multicast Zone Routing protocol”, Internet Draft, draft-vijay-manet- mzr-01.txt, work in progress, June 2001.
[24]Yueh-Min Huang and Tzu-Chiang Chiang,” A sequence and topology encoding for multicast protocol （STMP） in wireless ad hoc networks”, Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on , 27-29 Aug. 2003,Pages:351 – 355.
[25]Y.B. Ko and N. H. Vaidya, “Location-based multicast in mobile ad hoc networks”, Tech. Rep. 98-018, CS Dept., Texas A&M University, September 1998.
[26]Y.Ko, N.H.Vaidya, “Location Aided Routing (LAR) mobile ad hoc networks”, MOBICOM98
[27]Zygmunt J. Haas, Marc R. Pearlman, Prince Samar, “The Zone Routing Protocol”, Internet Draft, draft-ietf-manet-zone-zrp-04.txt, work in progress, July 2002.