跳到主要內容

臺灣博碩士論文加值系統

(18.97.9.169) 您好!臺灣時間:2025/02/18 00:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:徐紫菱
研究生(外文):Tzu-Lin Shiu
論文名稱:隨意網路上以連結支配集合為基礎的骨幹繞送協定
論文名稱(外文):A Connected Dominating Set Routing Protocol for Ad Hoc Networks
指導教授:劉如生
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:39
中文關鍵詞:盲目的泛傳廣播風暴支配集合骨幹網路
外文關鍵詞:blind floodingbroadcast stormdominated setbackbone
相關次數:
  • 被引用被引用:0
  • 點閱點閱:188
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
在進行繞送路徑的搜尋時,為了讓所有節點都能收到相同的一件訊息,無線隨意網路的繞送協定均採用廣播的方式。 而在廣播時,最常使用的策略為『盲目的泛傳』,在此策略下,每個節點在第一次收到廣播封包時都會主動將此封包再次廣播出去,因而造成封包資料被重覆傳送,衍生出廣播風暴的問題。 為解決此問題,遂有學者提出“以連結支配集合為基礎的骨幹繞送協定”的方法:選出一組可與所有節點連結的支配節點集合,負責將廣播封包轉送出去。 該方法可有效的減少廣播封包的發送數量,節省電力,並降低封包在傳輸時發生競爭及碰撞問題,唯其在建立骨幹網路時需要較多的額外工作。
針對上述建立骨幹網路之方式,本論文提出一套有效的改進方法。基本上,我們將設計一個選舉演算法,在無線隨意網路上以投票的方式,選舉出一組支配節點集合,同時以AODV為基礎將選票的資訊包含在hello message中進行投票工作,如此即可以最少的成本完成骨幹網路的建構,且該骨幹網路可有效地減少廣播封包,節省電力,以及降低封包傳輸時發生競爭與碰撞之機率。
In order to transmit the same message information to all the nodes over the network, the routing protocol for discovering the routing path will utilize broadcasting mechanism for Ad hoc network and the blind blooding strategy is usually adopted for broadcast. The blind blooding is a strategy that each node rebroadcasts the packet to other nodes after receiving the packet at the first time. Then, the same packet is transmitted repeatedly and the broadcast storm will happen. In order to solve the broadcast storm problem, some researchers proposed an approach that the dominating set is selected as the forwarding nodes to rebroadcast the packet to control the number of packets effectively. Then, the number of packets transmission, the power consumption, the contention and the collision problem can be reduced. However, their methods may need more overhead for creating the dominating set.
This paper will propose an efficient approach to improve the above problem. Basically, we will design an election algorithm to select a connected dominating set from Ad Hoc Networks. The election algorithm is based on the AODV, with which the hello message may contain the election information to select the connected dominating set. In this way, the backbone can be established with the minimum cost. After the backbone is created, the number of rebroadcast packets can be reduced effectively.
摘要 ii
Abstract iii
誌謝 iv
目錄 v
圖目錄 vi
表目錄 vii
第一章 導論 8
1.1 研究背景 8
1.2 研究目的與動機 10
1.3 論文架構 11
第二章 相關研究 12
2.1 轉送節點 12
2.2 獨立支配集合 16
2.3 連結支配集合 18
第三章 研究方法 22
3.1 取得2-hop鄰居資訊 22
3.2 符號說明 23
3.2 骨幹節點選舉 24
3.4 骨幹網路修復機制 27
第四章 模擬實驗 29
4.1 模擬環境與參數設定 29
4.2 分析骨幹節點的數目 30
4.3 骨幹網路建立的效益 32
4.4 骨幹網路建立的成本 33
第五章 結論 35
參考文獻 37
[1]C.E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers”, in Proceedings of Special Interest Group on Data Communication (SIGCOMM), Aug. 1994
[2]S. Murth and J.J. Garcia, “An Efficient Routing Protocol for Wireless Networks,” ACM Mobile Networks and Application Journal - Special Issue on Routing in Mobile Communication Networks, Vol. 1, No. 2, pp. 183-197, Oct, 1996
[3]G. Pei, M. Gerla and T. W. Chen, “Fisheye State Routing in Mobile Ad Hoc Networks,” in Proceedings of Workshop on Wireless Networks and Mobile Computing (WNMC), April 2000, pp 71-78
[4]C. E. Perkins and E. M. Royer, “Ad Hoc On-Demand Distance Vector Routing,” in Proceedings of Workshop on Mobile Computing Systems & Applications (WMCSA), Feb. 1999, pp. 90-100
[5]J. Broch, D.B. Johnson and D. A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,” Internet Draft of the IETF MANET Working Group, Dec. 1998
[6]V. D. Park, J. P. Macker and M.S. Corson, “Applicability of the Temporally-Ordered Routing Algorithm for Use in Mobile Tactical Networks,” in Proceeding of IEEE Military Communications Conference (MILCOM), Oct. 1998, pp. 426-430
[7]S.Y. Ni, Y.C. Tseng, Y.S Chen, J.P Sheu, “The broadcast storm problem in a mobile ad hoc network,” Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, 1999, pp. 151 - 162
[8]M. R. Pearlman and Z. J. Haas, “Determining the Optimal Configuration for the Zone Routing Protocol,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, pp. 1395-1414, Aug. 1999
[9]M. Joa and I. T. Lu, “A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, vol. 17, No. 8, pp.1415-1425, Aug. 1999
[10]S. Guha and S. Khuller, “Approximation algorithms for connected domination sets,” Tech. Rep. 3660, Univ. of Maryland Inst. For Adv. Computer Studies-Dept. of Computer Sci., 1996
[11]Yuanzhu P. Chen, Arthur L. Liestman, and Jiangchuan Liu, “Clustering Algorithms for Ad Hoc Wireless Networks,” in Ad Hoc and Sensor Networks, 2004
[12]Wei Lou and Jie Wu, “Efficient Broadcast with Forward Node Set in Clustered Mobile Ad Hoc Networks,” Proceedings of the 11th International Conference on Computer Communications and Networks, Oct. 2002, pp.398-403
[13]T. C. Hou and T. J. Tsai, "Adaptive clustering in a Hierarchical Ad Hoc Network," in Proceedings of ICS Workshop on Computer Networks, Internet and Multimedia, Dec. 1998, pp.3149-3155
[14]C. C. Chiang and M. Gerla, "Routing and Multicast in Multihop, Mobile Wireless Network," in Proceedings of IEEE International Conference on Universal Personal Communications (ICUPC), Oct. 1997, pp. 546-551
[15]M. Chatterjee, S. K. Sas and D. Turgut, "An On-Demand Weighted Clustering Algorithm (WCA) for Ad Hoc Networks," in Proceedings of IEEE Gobeeom 2000, Nov. 2000, pp.1697-1701
[16]J. Wu and H. Li, “A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks,” Special Issue on Wireless Networks in Telecommunication Systems Journal, Vol3, pp. 63-84, 2001
[17]Bevan Das and Vaduvur Bharghavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” in IEEE International Conference on Communications, 1997
[18]J. Wu and H. Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks,” Proc. of the 3rd Int''l Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication, pp7-14, 1999

[19]H. Lim and C. Kim, “Multicast tree construction and flooding in wireless ad hoc networks,” in Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, Aug. 2000, pp. 61-68
[20]Royer, E.M. Chai-Keong Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” in Personal Communications, IEEE [see also IEEE Wireless Communications, Apr 1999, pp. 46-55
[21]Fei Dai, Jie Wu, “Performance analysis of broadcast protocols in ad hoc networks based on self-pruning,” in Parallel and Distributed Systems, IEEE Transactions on, Nov 2004, pp. 1027- 1040
[22]Marco A. Spohn and J. J. Garcia-Luna-Aceves, “Enhanced dominant pruning applied to the route discovery process of on-demand routing protocols,” in Proceedings of the 12th IEEE international conference on computer communications and networks, Oct 2003, pp.497–502
[23]Marco A. Spohn and J. J. Garcia-Luna-Aceves, “Enhancing broadcast operations in ad hoc networks with two-hop connected dominating sets,” in Proceedings of the IEEE international conference on mobile ad-hoc and sensor systems, Oct 2004, pp. 543–545
[24]Marco A. Spohn and J. J. Garcia-Luna-Aceves, “Enhancing the route discovery process of on-demand routing in networks with directional antennas,” in Lecture notes in computer science, Jan 2004, pp. 1000–1011
[25]Marco A. Spohn and J. J. Garcia-Luna-Aceves, “Improving broadcast operations in adhoc networks using two-hop connected dominating sets,” in Proceedings of the IEEE global telecommunications conference workshops, Nov 2004 , pp. 147–152
[26]Marco A. Spohn and J. J, "Garcia-Luna-Aceves, “Improving the efficiency and reliability of the route discovery process in on-demand routing protocols,” in Proceedings of the IEEE wireless communications and networking conference, March 2005, pp. 2008–2013
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top