自組網(wǎng)位置服務中基于哈希函數(shù)的位置分配和檢索方法【文獻綜述】

1、<p><b>　　畢業(yè)論文文獻綜述</b></p><p><b>　　計算機科學與技術</b></p><p>　　自組網(wǎng)位置服務中基于哈希函數(shù)的位置分配和檢索方法</p><p><b>　　一、前言</b></p><p>　　傳統(tǒng)的網(wǎng)絡是有中心且需要基礎設施

2、支持的，而Ad Hoc網(wǎng)絡是無中心且無需基礎設施支持的。對于一些特殊的環(huán)境或情況，如在大海上，我們就不可能建立基礎設施來支持船舶通訊，而Ad Hoc網(wǎng)絡的特點就可以很有效地解決這個問題。在未來，Ad Hoc網(wǎng)絡必定成為我們必不可少的網(wǎng)絡。</p><p>　　在Ad-hoc網(wǎng)絡中，由于節(jié)點是可移動的，所以對于節(jié)點的發(fā)現(xiàn)和選擇是一個比較困難的問題。本文提出了基于哈希函數(shù)的位置分配和檢索方法，目的是在位置服務中利用哈

3、希函數(shù)的特征來提高路由的發(fā)現(xiàn)和位置分配的效率。</p><p>　　二、Ad-hoc網(wǎng)絡相關概述</p><p>　　Ad-hoc網(wǎng)絡的主要特征：（1）獨立性，（2）動態(tài)拓撲，（3）多跳通訊，（4）帶寬受限、鏈路容量動態(tài)變化，（5）節(jié)點功耗受限，（6）分布式特性，（7）生存周期短（8）有限的安全性和服務質量。[1,2]</p><p>　　Ad-hoc網(wǎng)絡的關鍵技術

4、：（1）信道接入技術，（2）路由協(xié)議，（3）網(wǎng)絡體系結構，（4）QoS保證，（5）廣播和多播，（6）安全問題，（7）網(wǎng)絡管理，（8）能耗節(jié)省機制。[2,3]</p><p>　　Ad-hoc網(wǎng)絡的應用：（1）家庭聯(lián)網(wǎng)，（2）緊急服務，（3）傳感器網(wǎng)絡，（4）個人域網(wǎng)絡，（5）軍事無限通訊，（6）其他商業(yè)應用。[2,4]</p><p>　　三、Ad-hoc網(wǎng)絡位置服務相關概述</p&

5、gt;<p>　　在移動Ad-hoc網(wǎng)絡中將遇到的最大難題：各個節(jié)點并不知道其它節(jié)點的位置，這與傳統(tǒng)網(wǎng)絡節(jié)點是固定的有很大區(qū)別，因此，在Ad-hoc網(wǎng)絡中對于路由的發(fā)現(xiàn)和維護所產(chǎn)生的網(wǎng)絡資源耗費將大于傳統(tǒng)網(wǎng)絡。但是隨著信息技術的發(fā)展，全球定位系統(tǒng)（GPS）也逐步成熟和完善，把這種技術加入到移動節(jié)點中，我們便可以準確的獲取節(jié)點的位置信息，這十分有利于路由的發(fā)現(xiàn)和維護。</p><p>　　位置服務是一

6、類位置信息發(fā)布與查詢機制，節(jié)點通過位置服務把自身位置信按照一定的方式發(fā)布到網(wǎng)絡中，通過位置服務，節(jié)點可隨時查詢網(wǎng)絡中其他節(jié)點的位置。在移動Ad Hoc網(wǎng)絡位置服務中，節(jié)點通過GPS等方法獲取自己的位置，位置服務來獲取目的節(jié)點的位置，鄰居節(jié)點的位置可通過一跳廣播來獲取。在Ad Ho網(wǎng)絡中利用位置信息，可以使節(jié)點在尋找目的節(jié)點時避免簡單的洪泛；利用相鄰節(jié)點或目的節(jié)點的位置信息，可以提高路由尋找的效率。[5]</p><p

7、>　　常見的幾種位置服務：Quorum位置服務[5]，ZHLS位置服務[5]，GLS位置服務[16]，DREAM位置服務[17]，GPSR位置服[18]，LAR位置服務[19]。</p><p>　　移動Ad Hoc網(wǎng)絡的位置服務可根據(jù)參與節(jié)點的數(shù)目分為四種類型：（1）部分節(jié)點參與的部分節(jié)點位置服務，典型代表是Quorum位置服務；（2）部分節(jié)點參與的全部節(jié)點位置服務，典型代表是ZHLS位置服務；（3）所有

8、節(jié)點參與的部分節(jié)點位置服務，典型代表是GLS位置服務；（4）所有節(jié)點參與的所有節(jié)點位置服務，典型代表是DREAM位置服務。[5]</p><p>　　移動Ad Hoc網(wǎng)絡的位置服務可根據(jù)基于位置信息的完全與否分為兩類；（1）局部的基于位置信息的位置服務，如LAR和DREAM；（2）完全的基于位置信息的位置服務，如GLS和GPSR。[7]</p><p>　　雖然Ad Hoc網(wǎng)絡中的這些位置

9、服務都各有優(yōu)點，但是也存在著不少的缺點，不過相比之下，我們可以發(fā)現(xiàn)GLS位置服務是一種比較好的位置服務，究其原因是因為在GLS位置服務中采用了哈希函數(shù)的特性來分配節(jié)點。由于Ad Hoc網(wǎng)絡無中心的特點也讓我們不得不考慮以共享方式來獲取資源，而這種方式正是對等網(wǎng)絡（P2P）的強項，并且我們獲知在P2P網(wǎng)絡中同樣存在采用哈希函數(shù)的位置服務路由協(xié)議——Chord，這種環(huán)形的路由協(xié)議必定有著其不可小覷的高效性。在文獻[9][10][20][21

10、]中有詳細介紹這種位置服務路由協(xié)議。</p><p>　　四、Ad-hoc網(wǎng)絡檢索方法相關概述</p><p>　　在Ad-hoc網(wǎng)絡中，對于節(jié)點的查找和路由的發(fā)現(xiàn)是比較困難的事情，尋找一種相對高效的檢索方法是解決的這個問題的關鍵。本文將采用P2P網(wǎng)絡中的Chord路由算法，以此通過環(huán)路優(yōu)化檢索方法，因為這種算法是結合了哈希函數(shù)特性的一種高效算法。在Chord路由算法模型中，每個節(jié)點標識符

11、和存儲數(shù)據(jù)的關鍵字標識符將通過哈希運算分別映射成一個長度為M的二進制序列NID和KID。在M位命名空間里，我們會選取一些節(jié)點作為中心節(jié)點，它們是整個Ad-hoc網(wǎng)絡的中心，這些節(jié)點兼有服務器和路由功能，它們既能存儲信息也能轉發(fā)信息，在環(huán)形網(wǎng)絡中它們還將充當引導節(jié)點的作用，可以引導新節(jié)點的加入和退出，這樣便能很好地適應Ad-hoc網(wǎng)絡節(jié)點的頻繁變化和路由表的快速更新。節(jié)點和節(jié)點之間可以形成小環(huán)路，并選擇其中一個節(jié)點作為該小環(huán)路的代理來存儲

12、該小環(huán)路的數(shù)據(jù)和信息，一個個小環(huán)路可以形成一個大環(huán)路，再找到代理，如此循環(huán)，直至所有節(jié)點分配完畢。這就是我們所做的——結合哈希技術并通過環(huán)路來優(yōu)化檢索方法。當我們要進行查詢時，節(jié)點首先會詢問自己所在環(huán)路的代理，如果沒有目標節(jié)點，再訪問上一級的環(huán)路代理，直至查詢到目的節(jié)點或反饋查詢失敗</p><p><b>　　五、總結</b></p><p>　　現(xiàn)代無線網(wǎng)絡和傳統(tǒng)

13、網(wǎng)絡雖然高速發(fā)展著，但是它們?nèi)孕杌A設施，在一些緊急狀況和特殊環(huán)境下，它們根本無法發(fā)揮作用。比如船載通訊，在茫茫大海中，我們不可能建立基礎設施來保持船只的通信；比如車載通訊，由于車載通訊網(wǎng)絡的拓撲變化十分快，路由表更新頻率快，維護困難。而Ad-hoc網(wǎng)絡無需基礎設施便能快速組建網(wǎng)絡，而它的動態(tài)節(jié)點也需要良好的路由協(xié)議的支持來減少路由表更新時所產(chǎn)生耗費，于此同時隨著信息技術的提高，全球定位系統(tǒng)（GPS）可以幫助我們解決動態(tài)節(jié)點難定位的問題

14、。因此，Ad-hoc網(wǎng)絡在未來必定可以發(fā)揮很大的作用，成為必不可少的一部分。</p><p>　　未來，Ad-hoc網(wǎng)絡的研究重點將會放在如何解決一些關鍵技術的問題上，只有解決了Ad-hoc網(wǎng)絡中遇到的一些關鍵技術，Ad-hoc網(wǎng)絡才能更好地發(fā)展。</p><p><b>　　參考文獻</b></p><p>　　[1] 王海濤.Ad Hoc網(wǎng)

15、絡.電信技術,2005</p><p>　　[2] 雷春娟,李承恕.移動Ad-hoc網(wǎng)絡及其關鍵技術.電信技術,2002.12</p><p>　　[3] 朱亞靜.Ad Hoc網(wǎng)絡技術淺析.價值工程,2008第11期</p><p>　　[4] 方旭明.移動Ad Hoc網(wǎng)絡研究與發(fā)展現(xiàn)狀.數(shù)據(jù)通信,2003第4期</p><p>　　[5]

16、魏文彬.移動Ad Hoc網(wǎng)絡分布式位置服務研究.2008.6</p><p>　　[6] 袁錦繡.基于移動ad hoc網(wǎng)絡服務發(fā)現(xiàn)的研究.2007.6 </p><p>　　[7] 張建.基于位置信息的無線自組織網(wǎng)絡路由技術的研究.北京郵電大學,2007.3</p><p>　　[8] 沈長星.基于地理位置的移動Ad Hoc網(wǎng)絡路由協(xié)議研究.北京郵電大學,2006.

17、3</p><p>　　[9] 鄒東堯,宋美娜,宋俊德.一種基于物理網(wǎng)絡拓撲的高效Chord模型.計算機工程,2008.3</p><p>　　[10] 陳宏亮,李杰,王桃.基于位置的層次式Chord模型.計算機工程,2009.11</p><p>　　[11] 王成,劉金剛.Ad Hoc無線網(wǎng)絡及其路由協(xié)議分析.計算機應用及軟件,2006.8第8期</p&g

18、t;<p>　　[12] 劉元安,唐碧華,胡月梅.Ad hoc網(wǎng)絡中的路由算法.北京郵電大學學報,2004.4</p><p>　　[13] 沈軍,曹元大,張樹東.移動Ad Hoc網(wǎng)絡中基于預測及適時更新的位置信息服務.北京理工大學學報,2005.12第12期</p><p>　　[14] 袁錦繡,錢雪忠,王錦嶺.一種基于位置和DHT的移動ad hoc網(wǎng)絡服務發(fā)現(xiàn)算法.微電子

19、學和計算機,2006第9期</p><p>　　[15] 王志明,劉傳情.基于網(wǎng)格的Ad hoc網(wǎng)絡混合位置服務算法.信陽師范學院學報,2009.4</p><p>　　[16] Jinyang Li. A Scalable Location Service for Geographic Ad Hoc Routing.1998</p><p>　　[17] Stef

20、ano Basagni,Imrich Chlamtac,Violet R.Syrotiuk,et al.a distance routing effect algorithm for mobility (DREAM).1998</p><p>　　[18] Brad Karp,H.T.Kung.GPSR;Greedy Perimeter Stateless Routing for Wireless Network

21、s.2000</p><p>　　[19] Young-Bae Ko and Nitin H. Vaidya .Location-Aided Routing (LAR) in mobile ad hoc networks.1998</p><p>　　[20] 姜守旭,韓希先,李建中.一種改進的Chord路由算法.計算機應用,2006.4</p><p>　　[21