在無線隨意及感測網路中支援覆疊式群播

Supporting Overlay Multicast in Wireless Ad hoc and Sensor Networks

江吉國(Chi-Kuo Chiang)

指導教授 ： 金仲達

國立清華大學/電機資訊學院/資訊工程學系/碩士(2006年)

摘要

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

關鍵字

覆疊 ； 群播 ； 無限 ； 隨意 ； 感測

並列摘要

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.

並列關鍵字

overlay ； multicast ； wireless ； ad hoc ； sensor

參考文獻

[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

[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.