研究生: |
楊家華 Jia-hua Yang |
---|---|
論文名稱: |
在無線隨意網路中尋找符合指定權重之節點群的研究 A Study on Finding Any Set of Nodes of a Given Weight in MANET |
指導教授: |
邱舉明
Ge-Ming Chiu |
口試委員: |
鮑興國
Hsing-kuo Pao 李育杰 none 鍾崇斌 Chung-ping Chung |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 資訊工程系 Department of Computer Science and Information Engineering |
論文出版年: | 2005 |
畢業學年度: | 94 |
語文別: | 中文 |
論文頁數: | 42 |
中文關鍵詞: | 權重 、無線隨意網路 |
外文關鍵詞: | MANET, weight |
相關次數: | 點閱:232 下載:1 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在無線隨意網路中,尋找一群權重總和達到一指定值之節點是很重要,但尚未被開發的議題,基於能量和頻寬的考量,尋找的過程不應該耗費太多的訊息負擔;有效率的分群(clustering)機制、多數決的互斥演算法…等,都是這個問題的可能應用。這篇論文的精神,是希望權重請求所得到的節點群,能夠愈接近請求節點愈好。為此目的,我們利用節點間彼此交換權重資訊,來幫助權重請求的分配,並且希望也能減少訊息負擔和端對端的傳輸延遲。在本論文中,我們提出一個演算法來尋找符合指定權重之節點,而我們使用的方法是向鄰居節點發出請求訊息,請鄰居節點幫忙尋找所需要的權重。
節點之間所交換的權重資訊,將會計算成一個分數,夾帶在Hello Message裡,來幫助權重請求的分配,而我們所提出的分數算法中,有兩個重要的參數,一個是分數所包涵權重的範圍,一個是將較遠端和重複的權重資訊弱化的β值。在論文中,我們也將針對不同的環境,提出分數計算的參數設定。在論文的最後,我們也透過模擬,提供了效能的評估。在一般情況下,的確是可以比直觀的方法和Flooding花費比較少的訊息負擔,並且也達到了不錯的搜尋結果。
To find a set of nodes of a given weight in mobile ad hoc networks (MANET) is an important, but unexploited issue. Possible applications include message-efficient clustering or majority-based mutual exclusion algorithms. Due to the constraints on energy and wireless bandwidth, the searching process should have low message overhead. The objective of this thesis is to study this problem and to develop a mechanism for finding a set of nodes of a given weight as close to the request node as possible. To this end, the basic idea of our mechanism is that nodes periodically exchange weight information to help the distribution of the requested weights in order to reduce message overhead as well as end-to-end delay of the request. Our algorithm attacks the problem by properly distributing the requested weight among their neighbors.
The weight information exchanged between nodes is calculated iteratively as a score. These scores are piggybacked on Hello messages to help the distribution of the weight requests. There are two important parameters in our score computation scheme. One is the range (hop) comprised by score, and the other is β, which is used for weakening the weight information apart and for accounting for overlapping. In the thesis, we propose the settings of the parameters according to different scenarios. We also carry out extensive simulations to evaluate the performance of our method. Simulation results show that our mechanism has lower message overhead than naïve and flooding mechanisms, and achieves a better searching result.
[1]M. Benchaiba, A. Bouabdallah, N. Badache, and M. Ahmed-Nacer, “Distributed mutual exclusion algorithms in mobile ad hoc networks : an overview,” January 2004 ACM SIGOPS Operating Systems Review, Volume 38 Issue 1.
[2]Z. Cheng and W.B. Heinzelman, “Flooding strategy for target discovery in wireless networks” September 2003 Proceedings of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems
[3]J. Cho, S. Oh, J. Kim, H.H. Lee, and J. Lee, “Neighbor Caching in Multi-Hop Wireless Ad Hoc Networks,” Communications Letters, IEEE Volume 7, Issue 11, Nov. 2003 Page(s):525-527
[4]C. Carter, S. Yi, P. Ratanchandani, and R. Kravets, “Manycast: Exploring the Space Between Anycast and Multicast in Ad Hoc Networks,”
[5]H. Deng, A. Mukherjee, and D.P. Agrawal, “Threshold and identity-based key management and authentication for wireless ad hoc networks,” Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference on Volume 1, 2004 Page(s):107 - 111 Vol.1
[6]R. Krishnan and D. Starobinski, “Message-efficient self-organization of wireless sensor networks,” Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE Volume 3, 16-20 March 2003 Page(s):1603 - 1608 vol.3
[7]J. Kong, P. Zerfos, H. Luo, S. Lu, and L. Zhang, “Providing Robust and Ubiquitous Security Support for Mobile Ad-hoc Networks,” Network Protocols, 2001. Ninth International Conference on 11-14 Nov. 2001 Page(s):251-260.
[8]C.V. Ramamoorthy, A. Bhide, and J.Srivastava, “Reliable Clustering Techniques for Large, Mobile Packet Radio Networks,” Proc. IEEE INFOCOM ’87, pp. 218-226, 1987.
[9]International Standard ISO/IEC 8802-11; ANSI/IEEE Std 802.11, 1999 Edn. Part 11: wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications.
[10]JSci – A Science API for JavaTM. http://jsci.sourceforge.net/