跳到主要內容

臺灣博碩士論文加值系統

(18.207.132.116) 您好!臺灣時間:2021/07/29 21:32
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:洪浩翔
研究生(外文):Hao-Hsiang Hung
論文名稱:在無線隨意網路下建立及維持一具連結性之k-中繼點控制集
論文名稱(外文):Constructing and Maintaining a Connected k-hop Dominating Set in Mobile Ad Hoc Networks
指導教授:蔡明哲蔡明哲引用關係
指導教授(外文):Ming-Jer Tsai
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:28
中文關鍵詞:控制集路由無線隨意網路連結性
外文關鍵詞:dominating setroutingmobile ad hoc networksconnected
相關次數:
  • 被引用被引用:0
  • 點閱點閱:141
  • 評分評分:
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
在一圖形中之一k-中繼點控制集為一節點之子集合,而此子集合外之點相隔此控制集其中一點至多k個中繼點。若一k-中繼點控制集中之任兩點間皆存在經過控制集內之路徑,則稱其具有連結性(connected)。在無線隨意網路中之節點可藉由在頻道內傳送訊信息,或透過網路之路由(routing)與其鄰近節點進行溝通。經由階層式的路由協定來建立並維護具有連結性之k-中繼點控制集,可節省傳輸功率及網路溝通成本。本文發現一屬於具有連結性之k-中繼點控制集之特性,並證明:若圖中所有點皆符合此特性,則k-中繼點控制集具有連結性。且藉由此特性,建立並維護一具有連結性之k-中繼點控制集僅需2個中繼點之資訊。模擬結果顯示,隨著k遞增,所建立具有連結性之k-中繼點控制集也穩定地縮小。
In a graph G = (V,E), a k-hop dominating set Dk is a subset of such that all nodes in V are either in or at most k-hop to a node Dk. A k-hop dominating set Dk is connected if there is a path, in which each node is in Dk, between any two nodes in Dk. In a mobile ad hoc network, a node communicates with its neighbors by sending messages across channels, and the others by routing messages via the network. The hierarchical routing protocol that constructs and maintains a connected k-hop dominating set attempts to reduce transmission power and communication overhead. In this paper, the node property of a connected k-hop dominating set is found, and it is proved that a k-hop dominating set is connected if all nodes in V belong to the node property. By its aid, a connected k-hop dominating set is constructed and maintained using only 2-hop neighbor information. Our simulation shows that the connected dominating set shrinks consistently as the hop count of k grows.
Abstract I
Contents III
List of Figures IV
Chapter 1 Introduction 1
Chapter 2 Notations and Preliminaries 3
Chapter 3 The Proposed Method 9
3.1 Shrinking the dominating set 10
3.2 Extending the dominating set 11
3.3 Switching on 15
3.4 Switching off 16
Chapter 4 Simulation 22
Chapter 5 Conclusion 26
References 27

List of Figures
Figure 1.Two dominating sets 4
Figure 2.An example of binary relation R 5
Figure 3.The measurement of paths 7
Figure 4.Algorithm CKDS 9
Figure 5.An example of Algorithm CKDS 10
Figure 6.Procedure Shrink_Set 11
Figure 7.An example of shrinking the dominating set 12
Figure 8.Procedure Extend_Set 12
Figure 9.Procedure Wake_Up 13
Figure 10.An example of extending the dominating set 15
Figure 11.Procedure Switch_On 16
Figure 12.An example of switching on 17
Figure 13.Procedure Switch_Off 17
Figure 14.An example of switching off 19
Figure 15.The size of the k-hop dominating set 23
Figure 16.The number of changed nodes in the k-hop dominating set 25
[1] “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications,” IEEE Standard 802.11, 1997. [2] D. J. Baker and A. Ephremides, “The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm,” IEEE Transactions on Communications, pp.1694—1701, 1981.
[3] Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” ACM Wireless Networks Journal, 2002.
[4] C. C. Chiang and M. Gerla, “Routing and Multicast in Multihop, Mobile Wireless Networks,” Proceedings of IEEE International Conference on Universal Personal Communications, pp.28—33, 1997.
[5] T. Imielinski and J. C. Navas, “GPS-based Addressing and Routing,” IETF RFC 2009, 1996.
[6] D. Johnson and D. Maltz., “Dynamic Source Routing in Mobile Ad hoc Networks,” Mobile Computing, pp.153—181, 1996.
[7] C. R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE Journal on Selected Areas in Communications, vol.15, no.7, pp.1265—1275, 1997.
[8] M. Mauve, J. Widmer, and H. Hartenstein, “A Survey on Position-Based Routing in Mobile Ad Hoc Networks,” IEEE Network Magazine, pp.30—39, 2001.
[9] C. Perkins, “Ad Hoc On Demand Distance Vector (AODV) Routing,” http://www.ietf.org/internet-drafts/draft-ietf-manet-aodv-02.txt.
[10] C. Santivanez, R. Ramanathan, and I. Stavrakakis, “Making Link-State Routing Scale for Ad Hoc Networks,” The ACM Symposium on Mobile Ad Hoc Networking & Computing, pp.22—32, 2001.
[11] B. Stefano, “Finding a Maximal Weighted Independent Set in Wireless Networks,” Telecommunication Systems, pp.155—168, 2001.
[12] D. C. Su, S. F. Hwang, C. R. Dow, and Y. W. Wang, “An Efficient K-hop Clustering Routing Scheme for Ad hoc Wireless Networks,” pp. 139—146, Journal of the Internet Technology, 2002.
[13] J. Wu and H. Li, “A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks,” Telecommunication Systems, pp. 13—36, 2001.
[14] Fabian Garcia Nocetti, Julio Solano Gonzalez and Ivan Stojmenovic, “Connectivity Based k-Hop Clustering in Wireless Networks,” Telecommunication Systems, pp. 205—220, 2003.
[15] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Communication & Mobile Computing(WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, pp. 483—502, 2002.
[16] A.D. Amis, R. Prakash, T.H.P. Vuong, and D.T. Huynh, “Max-Min d-cluster Formation in Wireless Ad Hoc Networks,” Proceedings of IEEE INFOCOM, pp. 32—41, 2000.
[17] http://www.webopedia.com/TERM/N/network_interface_card_NIC.html
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top