臺灣博碩士論文加值系統

在大多數無線感測網路的研究中，無線感測器與匯集點皆假設為靜止不動，使得其應用也相對的受到限制。然而，許多真實的應用環境需要多個匯集點移動到各個感測領域，以便執行所需的任務。由於網路拓樸時常改變，無線感測器若仍然採用一般繞路協定，會使得感測資料無法有效率的傳遞到行動匯集點。此外，為了減少整體資料傳送次數，群播(multicast)技術在無線感測網路就成為重要的議題。而由於感測器有電量、記憶體和計算能力上的限制，如何有效的將資料散播給特定的接收者，一直是許多學者研究的目標。本篇論文提出了階層式網格的群播技術，在網路上建立位置伺服器並以簡單、有效率的方式建立群播樹，將資料正確的傳送至行動匯集點，當行動匯集點在移動時也能減少位置更新所需的封包量，進而降低整體網路能量消耗。我們所建立的群播樹亦能支援多個source，以共享路徑方式減少重新建立群播樹的能量消耗。此外，我們還提出適當的維護機制，使整個群播樹更加穩定、強健。最後，我們跟無線感測網路中的兩個群播技術DMRP和HGMR比較，模擬結果顯示在source和receiver數量變多和網路環境增大的情況下，我們的方法在能量、群播效率及擴充性上皆有較佳的表現。

In most researches of wireless sensor networks (WSNs), sensor nodes and sinks are usually stationary and thus throttling the applications. However, mobile sink brings extensive application areas in real-life environment. Due to frequent changing topology, it is inefficient to deliver sensing data to mobile sinks by employing ordinary routing protocols. Besides, in order to minimize the number of transmissions, multicast becomes an important issue in WSNs. Since sensor nodes have limit energy, storage and computation capability, how to send data to specific receivers efficiently is the objective of many researches in recent years. In this paper, we proposed grid multicast (GM) protocol which is a grid-based hierarchical multicast routing protocol for sensor networks. We use location servers to manage the information of receiver’s locations and then build a multicast tree to reduce the update cost caused by sink mobility and the power consumption. The multicast tree can be shared by multiple sources thus decreasing path construction overhead. Moreover, appropriate maintenance mechanisms are presented which makes the multicast tree more stable and robust. Finally, the performance of the proposed GM is investigated by means of simulations, we compare our protocol with DMRP and HGMP, both of them are multicast protocols in sensor networks. Simulation results show that our protocol has better energy consumption and multicast efficiency, and is also more robust than others, especially when increasing the number of sources, receivers, as well as the size of the network.

摘要 I
ABSTRACT II
目錄 III
圖目錄 V
表目錄 VIII
第一章 簡介 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 4
第二章 相關研究 5
第三章 GRID MULTICAST 16
3.1 階層式網格建立 16
3.2 網格內容管理 18
3.2.1 非網格管理者 18
3.2.2 網格管理者選擇 19
3.2.3 感測點的能量消耗模式 20
3.3 網路階層化管理 21
3.3.1 位置伺服器階層化 22
3.3.2 階層位置伺服器內容管理 23
3.4 群播樹的建立和資料傳遞 29
3.4.1 最近網格(Nearest Grid)的尋找 30
3.4.2 群播樹的建立與資料傳遞 32
3.5 MULTI-SOURCE共用路徑建立 36
3.5.1 群播樹直接連接 36
3.5.2 群播樹間接連接 37
3.5.3 雙向資料傳送 38
3.6 群播樹的維護機制 39
3.6.1 Sink移動 39
3.6.2 群播樹分支維護 41
3.6.3 網格無感測點 42
3.6.4 群播樹的優化 45
第四章 模擬結果與分析 47
4.1模擬環境假設 47
4.2模擬環境參數設定 48
4.3模擬結果分析與討論 48
4.3.1 平均能量消耗 48
4.3.2 平均更新能量消耗 51
4.3.3 群播效率分析 55
4.3.4 平均Hop Count 58
4.3.5 行動匯集點移動速度 61
第五章、結論及未來工作 68
參考文獻 69

[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks:a survey,” Computer Networks, Vol. 38, No. 4, pp. 393–422, 2002.
[2] R. H. Katz, J. M. Kahn, and K. S. J. Pister, “Mobile Networking for Smart Dust,” Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 271–278, 1999.
[3] R. Min, M. Bhardwaj, S. H. Cho, E. Shih, A. Sinha, A. Wang, and A. Chandrakasan, “Low Power Wireless Sensor Networks,” Proceedings of the 14th International Conference on VLSI Design, pp. 205–210, 2001.
[4] J. Rabaey, J. Ammer, J. da Silva, D. Patel, and S. Roundy, “PicoRadio supports ad hoc ultra low power wireless networking,” IEEE Computer, Vol. 33, pp. 42–48, 2000.
[5] M. Tubaishat, S. Madria, and “Sensor networks:an overview,” IEEE Potentials, Vol. 22, No. 2, pp.20–23, 2003.
[6] K. Akkaya, and M. Younis, “A survey on routing protocols for wireless sensor networks,” Ad Hoc Networks, Vol. 3, No. 3, pp.325–349, 2005.
[7] C. Perkins, Ad Hoc Networks, Addison-Wesley, Reading, MA, 2000.
[8] R. Agrodia, M. Gerla, J. Hsu, W. Su, S.-J. Lee, “A performance comparison study of ad hoc wireless multicast protocol,”; Proceedings of IEEE Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 2 , pp. 565 –574, 2000.
[9] E. Cheng, T. Kunz, “On-demand multicasting in ad-hoc networks: comparing AODV and ODMRP,” Proceedings of 22nd International Conference on Distributed Computing Systems, pp. 410–411, 2002.
[10] C.-C. Chiang, M. Gerla, “On-demand multicast in mobile wireless networks,” Proceedings of Sixth International Conference on Network Protocols, pp. 262–270, Oct. 1998.
[11] C. M. Cordeiro, H. Gossain and D. P. Agrawal, "Multicast over Wireless Mobile Ad Hoc Networks: Present and Future Directions," to Appear in IEEE Network, Special Issue on Multicasting: An Enabling Technology, Jan./Feb. 2003.
[12] S. K. Das, B. S. B. S. Manoj, C. S. R. Murthy, “A dynamic core based multicast routing protocol for ad hoc wireless networks,” Proceedings of the third ACM international symposium on Mobile ad hoc networking & computing, pp. 24-35, June 2002.
[13] R. C. Durst, C. S. Raghavendra, K. Scott, and M. J. Zukoski, “Comparing multicast protocols in mobile ad hoc networks,” Proceedings of IEEE Aerospace Conference, Vol.3, pp. 1051-1063, 2001.
[14] M. Gerla, S. H. Bae; S.-J. Lee, “Unicast performance analysis of the ODMRP in a mobile ad hoc network testbed,” Proceedings of Ninth International Conference on Computer Communications and Networks, pp. 148 –153, 2000.
[15] M. Maleki, K. Dantu, and M. Pedram, “Power-aware source routing protocol for mobile ad hoc networks,” Proceedings of the 2002 International Symposium on Low Power Electronics and Design, pp. 72-75, 2002.
[16] Y. C. Tay, C. W. Wu, “AMRIS: a multicast protocol for ad hoc wireless networks,” Proceedings of IEEE Military Communications Conference, Vol. 1, pp. 25 –29, 1999.
[17] J. Xie, R. R. Talpade, A. Mcauley, M. Liu, “AMRoute: ad hoc multicast routing protocol,” Mobile Networks and Applications, Dec. 2002.
[18] H. ZHOU, S. SINGH “Content Based Multicast (CBM) in Ad Hoc Networks,” Proceedings of the ACM/IEEE Workshop on Mobile Ad Hoc Networking and Computing, pp. 5160, Aug. 2000.
[19] Matthias Transier, Holger F���愮er, J�宁g Widmer, Martin Mauve, and Wolfgang Effelsberg. “A Hierarchical Approach to Position-Based Multicast for Mobile Ad-Hoc Networks, ” Proceedings of IEEE Wireless Networks, pp.447-460, 2007.
[20] C. E. Perkins, E. M. Royer, “Ad hoc on demand distance vector (AODV) routingin Mobile Ad-hoc Networks (manet),” http://www.ietf.org/html.charters/manet- charter.html, Aug. 1998.
[21] T. Ballardie, P. Francis, and J. Crowcroft, “Core Based Tree(CBT) – An Architecture for Scalable Inter-Domain Multicast Routing,” In Proceedings of ACM SIGCOMM’93, San Francisco, CA, pp. 85-95, Oct. 1993.
[22] Y.-B. Ko, N. H. Vaidya, “Geocasting in mobile ad hoc networks: location-based multicast algorithms,” Proceedings of Second IEEE Workshop on Mobile Computing Systems and Applications, pp. 101-110, Feb. 1999.
[23] Y.-B. Ko, N. H. Vaidya, “Location-aided routing (LAR) in mobile ad hoc networks,” Wireless Networks, Vol. 6 no. 4, pp. 307-321, Jul. 2000.
[24] V. Devarapalli and D. Sidhu, “MZR: a multicast protocol for mobile ad hoc networks,” Proceedings of IEEE International Conference on Communications, Vol. 3, pp 886–891, 2001.
[25] Z. Hass and M. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Mobile Networks,” in IETF MANET Draft, Jun. 1999.
[26] Jianming Zhu, Weiping Shang, and Xiaodong Hu, “New Algorithm for Minimum Multicast Time Problem in Wireless Sensor Networks, ” Proceedings of IEEE Wireless Communications and Networking Conference, pp. 3529 -3534, 2007.
[27] Liang-Liang Xie, Kumar, P.R. ”Multisource, Multidestination, Multirelay Wireless Networks, ” Proceedings of IEEE Information Theory, pp. 3586 -3595, 2007.
[28] Zeng, Guokai, Wang, Chen, and Li Xiao, “Grid Multicast: an Energy-Efficient Multicast Algorithm for Wireless Sensor Networks, ” Proceedings of IEEE Fourth International Conference on Networked Sensing Systems, pp. 267-274 2007.
[29] Shah, S. Waqar, Khan, L., Babar, Inayatullah, Hassnain, S. Riaz ul, Arbab, M. Naeem, Yahya, K.M., Ahmad, G. and Ali, S., “Coordination through multicast messaging in a multiple-mobile agent system (MMAS)”, Proceedings of IEEE International Conference on Electrical Engineering, April, 2007.
[30] Yang Min, Han Peng, Yu Bo, Mao Xiaofeng, Mao Dilin and Gao Chuanshan, ” A Light-Weight Multicast Schema for Wireless Sensor Network with Multi-Sinks,” Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing, pp.1-4, 2006.
[31] K. Dimitrios, D. Saumitra, H. Y. Charlie and S. Ivan, ” Hierarchical Geographic Multicast Routing for Wireless Sensor Networks,” Proceedings of International Conference on Sensor Technologies and Applications, pp. 347-354, Oct. 2007.
[32] J. Sanchez, P. Ruiz, X. Liu, and I. Stojmenovic, “GMR: Geographic Multicast Routing for Wireless Sensor Networks,” in Proc. of IEEE SECON, 2006.
[33] Qing Cao, Tian He, Tarek Abdelzaher, "uCast: Unified Connectionless Multicast for Energy Efficient Content Distribution in Sensor Networks," Accepted to IEEE Transactions on Parallel and Distributed Systems, 2007.
[34] R. Flury, R. Wattenhofer, “Routing, Anycast, and Multicast for Mesh and Sensor Networks,” Proceedings of IEEE 26th Computer Communications, pp. 946- 954, 2007.
[35] Sa Silva, J., Camilo, T., Rodrigues, A., Silva, M., Gaudencio, F., and Boavida, F., “Multicast in Wireless Sensor Networks The next step, ” Proceedings of IEEE 2nd International Symposium on Wireless Pervasive Computing, 2007.
[36] Zhao Gang Liu, Xiangqian Kumar Anup, ” Destination Clustering Geographic Multicast forWireless Sensor Networks, ” Proceedings of IEEE International Conference on Parallel Processing Workshops, pp. 48-48, 2007.
[37] Shibo Wu, Candan, K.S. “GMP: Distributed Geographic Multicast Routing in Wireless Sensor Networks, ” Proceedings of IEEE International Conference on Distributed Computing Systems, pp. 49-49, 2007.
[38] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the 33rd IEEE Hawaii International Conference on System Sciences, pp. 1–10, 2000.
[39] Brad Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, ” Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom 2000), pp.243-254, Boston, Massachusetts, USA, August 2000.