在這篇論文中，我們考慮在無限隨意及感測網路中群播的問題。在群播時，群組成員必須群播訊息給群組中的其他節點。這些群組成員可能散佈在感測網路中並寫需要其他節點來幫忙傳遞訊息。一個常見實用的方法便是在群組成員間建立一個樹狀或網狀的覆疊式架構，並沿著此覆疊式架構散佈訊息。
在這篇論文中，我們覺得覆疊式群播必須和底層的路由演算法互相配合。我們提出要以無狀態來源路由來做為底層的路由方法，而不像以往只使用單純的單播。在無狀態來源路由的方法中，發送端會將目標位址和傳遞者紀錄在封包標頭檔中。藉由這種方法，節點只需要廣播一次封包，在標頭檔被指定的鄰居們就知道是否該繼續傳遞封包，以及傳遞給誰。但是如果底層是使用單播的話，節點必須使用多次的單播將資料傳遞給對應的目標，連帶造成了多餘的能源消耗。在我們提出的整合覆疊式群播中，我們將覆疊式群播加在無狀態來源路由方法上。透過模擬實驗我們比較我們的方法和沒有覆疊架構的無狀態來源群播，而實驗結果顯示出我們的方法能更省電並有更好的負載平衡。

In this thesis, we consider the problem of group multicast in wireless sensor networks. In group multicast, group members need to multicast messages to all other nodes in the group. The group members may scatter around in the sensor network and require other nodes to relay the message. A common practice is to build an overlay, such as a mesh or a tree, among the group members and then disseminate the messages following the overlay structure. In this thesis, we argue that the overlay multicast must be matched by the underlay routing. We propose to use stateless source routing as the underlay routing scheme instead of straightforward unicast. Stateless source routing encodes the destinations and forwarders into packet header. In this way, a node only needs to transmit the packet once and multiple neighboring nodes that are designated in the header know they should forward the packet and where to forward. On the other hand, using unicast as the underlay, a node needs to transmit the packet once for each destination, consuming more energy in the nodes. In the proposed Aggregation Overlay Multicast (AOM) protocol, we build our overlay multicast on top of stateless source routing schemes like Differential Destination Multicast (DDM). Since wireless sensor nodes are often stationary, it is reasonable to distribute some membership control to group members instead of centralizing at the source node as in DDM. Through simulation we compare our protocol with stateless DDM and the results show that our protocol can achieve better energy efficiency and balance.

1 Introduction 1
2 Related Works 7
2.1 State Multicast on Ad Hoc Networks 7
2.2 Overlay Networks 7
2.3 Stateless Source-routing-style Multicast Routing Protocols 8
2.4 Protocols for Energy-efficiency or Maximizing Lifetime 10
3 Preliminaries and Problem Statement 12
3.1 Maximum Capacity Path Scheme 12
3.2 Stateless Multicast 14
3.3 Problem Statement 17
4 Aggregation Overlay Multicast 18
4.1 Virtual Mesh and Data Delivery Tree 18
4.2 Membership Management 21
5 Comparison and Analysis 23
5.1 Comparison of Membership Management Functions 23
5.2 Analysis Energy Consumption before Simulation 24
6 Performance Evaluation 27
6.1 Simulation Environment and Metrics 27
6.2 Simulation Results 28
6.2.1 Group member size 28
6.2.2 Network region size 32
6.2.3 Transmission radio range 34
6.2.4 Neighbor threshold 36
7 Conclusion and Future Work 38

[1] R. Boivie, N. Feldman and C. Metz, “Small Group Multicast: A New Solution for Multicasting on the Internet,” IEEE Internet Computing, June 2000.
[2] J. Chang and L. Tassiulas, "Energy Conserving Routing in Wireless Ad-hoc Networks," In Proc. of IEEE Infocom, 2000
[3] C. Chiang, M. Gerla, and L. Zhang, “Forwarding Group Multicasting Protocol for Multihop, Mobile Wireless Networks,” ACM-Baltzer Journal of Cluster Computing, Special Issue on Mobile Computing, 1998.
[4] J. Chen, L. Jia, X. Liu, G. Noubir and R. Sundaram, "Minimum Energy Accumulative Routing in Wireless Networks," In Proc. of IEEE Infocom, 2005
[5] K. Chen, K. Nahrstedt, "Effective Location-Guided Overlay Multicast in Mobile Ad Hoc Networks," In International Journal of Wireless and Mobile Computing, 2005
[6] Y. Chu, S. Rao, and H. Zhang, “A Case for End System Multicast,” In Proc. of ACM Sigmetrics, June 2000.
[7] M. Ge, S. V. Krishnamurthy, and M. Faloutsos, "Overlay Multicasting for Ad Hoc Networks," In Proc. of The Third Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), 2004
[8] C. Gui and P. Mohapatra, "Efficient Overlay Multicast for Mobile Ad Hoc Networks," In Proc. of IEEE Wireless Communications and Networking Conference, 2003
[9] X. Hong, M. Gerla, R. Bagrodia, J.k. Taek, P. Estabrook and P. Guangy, ”The Mars Sensor Network: Efficient, Power Aware Communications”, In Proc. of MILCOM, 2001.
[10] S. C. Huang and R. H. Jan, "Energy-Aware, Load Balanced Routing Schemes for Sensor Networks," In Proc. of the International Conference on Parallel and Distributed Systems, 2004
[11] L. Ji and M. S. Corson, “Differential Destination Multicast - A MANET Multicast Routing Protocol for Small Groups,” In Proc. of IEEE Infocom, 2001
[12] H. Jiang, S. Cheng, Y. He, B. Sun, "Multicasting Along Energy-efficient Meshes in Mobile Ad Hoc Networks," In Proc. of IEEE WCNC, 2002.
[13] Intae Kang, R. Poovendran, "On The Lifetime Extension and Route Stabilization of Energy-Efficient Broadcast Routing over MANET", In Proc. of INC (International Network Conference), 2002
[14] M. Kwon and S. Fahmy, “Topology-Aware Overlay Networks for Group Communication,” In Proc. of ACM NOSSDAV, May, 2002.
[15] S. J. Lee, M. Gerla, and C.-C. Chiang, “On-Demand Multicast Routing Protocol,” In Proc. of IEEE WCNC, 1999.
[16] A. Okura, T. Ihara and A. Miura, "BAM: Branch Aggregation Multicast for Wireless Sensor Networks," In Proc. of IEEE International Conference on Mobile Ad Hoc and Sensor Systems Conference, 2005.
[17] S.Y. Ou, H.C. Hsiao, C.K. Chiang, C.T. King, “Designing Power-aware Overlays in Heterogeneous Wireless Sensor Networks,” In Proc. of IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC), 2006
[18] T. Ozaki, J. Kim, and T. Suda, “Bandwidth-Efficient Multicast Routing Protocol for Ad-Hoc Networks,” In Proc. of IEEE ICCCN, 1999
[19] J. Park, S. Sahni, "Maximum Lifetime Broadcasting in Wireless Networks," In IEEE Transactions on Computers, 2005
[20] J. Park and S. Sahni, “Maximum Lifetime Routing in Wireless Sensor Networks.” In IEEE Transactions on Computers, 2006
[21] A. Patil, Y. Liu, L. Xiao, A.-H. Esfahanian, and LM Ni, "SOLONet:. Sub-Optimal Location-Aided Overlay Network for MANETs," In Proc. of IEEE International Conference on Mobile Ad-hoc and. Sensor Systems (MASS), 2004
[22] E. M. Royer, and C. E. Perkings, “Multicast Operations of the Adhoc On-Demand Distance Vector Routing Protocol,” In Proc. of ACM MOBICOM, August 1999.
[23] S. Sahni and X. Xu, "Algorithms for Wireless Sensor Networks," In International Journal of Distributed Sensor Networks, 2005
[24] J.E. Wieselthier, G.D. Nguyen, and A. Ephremides, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” In Proc. of IEEE Infocom, 2000
[25] L. Xiao, A. Patil, Y. Liu, L. M. Ni, and A.-H. Esfahanian, "Prioritized Overlay Multicast in Ad-hoc Environments," In IEEE Computer Magazine, February, 2004.
[26] J. Zhu, C. Qiao and X. Wang, "A Comprehensive Minimum Energy Routing Scheme for Wireless Ad hoc Networks," In Proc. of IEEE Infocom, 2004
[27] J. Zhu, X. Wang, “PEER: A Progressive Energy Efficient Routing Protocol for Wireless Ad Hoc Networks,” In Proc. of IEEE Infocom, 2005
[28] UCLA Computer Science Department Parallel Computing Laboratory and Wireless Adaptive Mobility Laboratory, GloMoSim: A Scalable Simulation Environment for Wireless and Wired Network Systems,
http://pcl.cs.ucla.edu/projects/domains/glomosim.html