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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、學(xué)和計(jì)算機(jī),2006第9期</p><p>　　[15] 王志明,劉傳情.基于網(wǎng)格的Ad hoc網(wǎng)絡(luò)混合位置服務(wù)算法.信陽師范學(xué)院學(xué)報(bào),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] 姜守旭,韓希先,李建中.一種改進(jìn)的Chord路由算法.計(jì)算機(jī)應(yīng)用,2006.4</p><p>　　[21