摘  要： 提出了基于網(wǎng)格可預(yù)測(cè)的位置服務(wù)算法(GPLS)。網(wǎng)絡(luò)劃分成網(wǎng)格，通過(guò)HASH函數(shù)對(duì)網(wǎng)格進(jìn)行分組，通信的源節(jié)點(diǎn)通過(guò)與目的節(jié)點(diǎn)所在分組內(nèi)的位置服務(wù)節(jié)點(diǎn)通信，獲得目的節(jié)點(diǎn)的準(zhǔn)確或預(yù)測(cè)的位置信息。在不增加網(wǎng)絡(luò)帶寬的前提下，提高了位置服務(wù)效率，節(jié)約了網(wǎng)絡(luò)的能源和帶寬。
關(guān)鍵詞： 位置服務(wù)；可預(yù)測(cè)；網(wǎng)格；MANET

    移動(dòng)Ad Hoc網(wǎng)絡(luò)MANET(Mobile Ad hoc Networks) 是一種無(wú)基礎(chǔ)設(shè)施、自組織和自配置的多跳無(wú)線(xiàn)網(wǎng)絡(luò)，網(wǎng)絡(luò)結(jié)構(gòu)根據(jù)節(jié)點(diǎn)的移動(dòng)動(dòng)態(tài)地改變。網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)協(xié)作來(lái)傳輸信息，通常節(jié)點(diǎn)既作為主機(jī)又作為路由器。節(jié)點(diǎn)的移動(dòng)性使得網(wǎng)絡(luò)中拓?fù)渥兓l繁且事先無(wú)法預(yù)測(cè)，所以在MANET中發(fā)現(xiàn)和維護(hù)路由是一個(gè)至關(guān)重要的問(wèn)題，一直是研究的熱點(diǎn)和難點(diǎn)問(wèn)題。
    近年來(lái)，利用地理位置信息的路由協(xié)議在MANET中得到了很大發(fā)展。隨著全球定位技術(shù)(GPS)的普遍應(yīng)用，節(jié)點(diǎn)可以獲得自身準(zhǔn)確的位置信息。利用這些信息進(jìn)行路由可以降低路由協(xié)議的控制開(kāi)銷(xiāo)、適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)湟约疤岣呗酚蓞f(xié)議的可擴(kuò)展性。然而在基于位置信息的路由協(xié)議中，在發(fā)送路由包之前，源節(jié)點(diǎn)需要知道目的節(jié)點(diǎn)的具體位置，主要的問(wèn)題是基于位置服務(wù)的路由協(xié)議中需要位置服務(wù)來(lái)確定目的節(jié)點(diǎn)的位置，并返回目的節(jié)點(diǎn)的位置信息。
    本文從穩(wěn)定高效的角度對(duì)基于位置服務(wù)算法進(jìn)行研究，提出了基于網(wǎng)格可預(yù)測(cè)的位置服務(wù)GPLS(Grid-based Predictive Location Service)算法。該算法把整個(gè)網(wǎng)絡(luò)劃分成平面網(wǎng)格以避免洪泛操作。通過(guò)HASH方法對(duì)網(wǎng)格進(jìn)行分組，節(jié)點(diǎn)可以與組內(nèi)任意網(wǎng)格通信，減少了位置更新和查找的步驟和復(fù)雜性，節(jié)約了MANET中的能源和帶寬。根據(jù)同組網(wǎng)格內(nèi)任意位置服務(wù)節(jié)點(diǎn)提供的目的節(jié)點(diǎn)的位置，預(yù)測(cè)出目的節(jié)點(diǎn)的位置，提高M(jìn)ANET中位置服務(wù)的效率，避免洪泛操作。
1 相關(guān)算法
    GLS(Grid Location Service)[1]將整個(gè)網(wǎng)絡(luò)劃分為網(wǎng)格，節(jié)點(diǎn)把它的位置信息分布地存放在網(wǎng)絡(luò)中的一個(gè)或多個(gè)位置服務(wù)器中。通過(guò)位置服務(wù)節(jié)點(diǎn)可隨時(shí)查詢(xún)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的位置，各節(jié)點(diǎn)間采用地理路由轉(zhuǎn)發(fā)進(jìn)行分組傳輸。HNS(Helping Node Selection)[2]根據(jù)位置服務(wù)器中記錄節(jié)點(diǎn)移動(dòng)的速度和記錄的時(shí)間來(lái)預(yù)判節(jié)點(diǎn)的位置，通過(guò)其他移動(dòng)節(jié)點(diǎn)把數(shù)據(jù)包直接攜帶到預(yù)判的位置，再把數(shù)據(jù)包傳輸給目的節(jié)點(diǎn)。這樣既提高了數(shù)據(jù)包的投遞率，又有效地解決了移動(dòng)自組網(wǎng)絡(luò)中節(jié)點(diǎn)動(dòng)態(tài)移動(dòng)和空洞問(wèn)題。PLS(Predictive Location Service)[3]是一個(gè)可預(yù)測(cè)、自適應(yīng)的平面位置服務(wù)。節(jié)點(diǎn)定期向周?chē)?jié)點(diǎn)發(fā)送緩存中的位置信息。節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中洪泛查找目的節(jié)點(diǎn)，接收到信息的節(jié)點(diǎn)根據(jù)緩存中目的節(jié)點(diǎn)的位置信息預(yù)測(cè)出當(dāng)前目的節(jié)點(diǎn)的位置。HBLS(Hashing-Based Location Service)[4]是一個(gè)基于HASH集合和平面結(jié)構(gòu)的位置服務(wù)算法。在當(dāng)前服務(wù)器消失之前選擇一個(gè)新的服務(wù)器，以提高服務(wù)的可靠性和服務(wù)的時(shí)間。整個(gè)網(wǎng)絡(luò)區(qū)域劃分為多個(gè)不重疊的區(qū)域。在伸縮性和可靠性?xún)蓚€(gè)方面權(quán)衡HBLS都是一個(gè)很好的算法。
2 算法描述
2.1 系統(tǒng)模型和假設(shè)
    系統(tǒng)考慮n個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中自由移動(dòng)，節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)技術(shù)彼此進(jìn)行通信，但是沒(méi)有提供固定的網(wǎng)絡(luò)基礎(chǔ)設(shè)施。假設(shè)所有節(jié)點(diǎn)功能相當(dāng)，都有一個(gè)統(tǒng)一的傳輸范圍。每個(gè)節(jié)點(diǎn)配備GPS接收裝置，能確定節(jié)點(diǎn)自己的位置，所有在傳輸范圍內(nèi)的節(jié)點(diǎn)都被認(rèn)為是鄰節(jié)點(diǎn)。節(jié)點(diǎn)既是源，又轉(zhuǎn)發(fā)數(shù)據(jù)，因此形成了MANET。每個(gè)節(jié)點(diǎn)有一個(gè)唯一的身份標(biāo)識(shí)節(jié)點(diǎn)ID。網(wǎng)絡(luò)結(jié)構(gòu)的改變是不可預(yù)測(cè)的。
2.2 網(wǎng)絡(luò)劃分和網(wǎng)格分組
    在地理路由中，通常把網(wǎng)絡(luò)劃分成多個(gè)小網(wǎng)格，每個(gè)網(wǎng)格分配一個(gè)編號(hào)，在每個(gè)網(wǎng)格內(nèi)選擇一個(gè)合適的節(jié)點(diǎn)作為位置服務(wù)節(jié)點(diǎn)(黑點(diǎn)為位置服務(wù)節(jié)點(diǎn))，整個(gè)網(wǎng)絡(luò)劃分成25個(gè)網(wǎng)格，如圖1所示。

    通過(guò)網(wǎng)格ID，建立一個(gè)HASH函數(shù)f(Gi)=Gi%G0，其中，G0為常數(shù)，Gi為網(wǎng)格的ID。把f(Gi)相同的分到一組，把一個(gè)網(wǎng)格G1內(nèi)的節(jié)點(diǎn)位置信息映射到其他網(wǎng)格G2、G3……Gn，映射到的網(wǎng)格被分到一組(G1、G2、G3……Gn)，位置服務(wù)節(jié)點(diǎn)定時(shí)向同組內(nèi)其他位置服務(wù)節(jié)點(diǎn)傳輸本網(wǎng)格內(nèi)節(jié)點(diǎn)的位置信息。同組的網(wǎng)格盡量均勻分布到整個(gè)網(wǎng)絡(luò)中。如圖1所示，G0=7，f(1)=1%7=1，f(8)=8%7=1，f(15)=15%7=1，f(22)=22%7=1。把網(wǎng)格1，8，15，22分到組1中。依次類(lèi)推組2、組3、組4、組5、組6、組0。
    節(jié)點(diǎn)被分配到網(wǎng)格中，每個(gè)節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)產(chǎn)生時(shí)所在的網(wǎng)格來(lái)分配節(jié)點(diǎn)ID。根據(jù)節(jié)點(diǎn)的ID，可以計(jì)算節(jié)點(diǎn)所在的網(wǎng)格及網(wǎng)格所在的分組，通過(guò)組內(nèi)網(wǎng)格的位置，服務(wù)節(jié)點(diǎn)獲得節(jié)點(diǎn)的位置信息。如果同一個(gè)網(wǎng)格內(nèi)的節(jié)點(diǎn)都可以相互直接通信，只需要一個(gè)網(wǎng)格內(nèi)最遠(yuǎn)的距離小于或等于節(jié)點(diǎn)的通信的傳輸半徑即可，即×a，如圖2所示。其中，R為節(jié)點(diǎn)傳輸半徑，a為網(wǎng)格的大小。

2.3 位置服務(wù)器選擇
    每個(gè)網(wǎng)格內(nèi)有位置服務(wù)節(jié)點(diǎn)，選擇離網(wǎng)格中心物理距離最近的節(jié)點(diǎn)作為位置服務(wù)節(jié)點(diǎn)。當(dāng)位置服務(wù)節(jié)點(diǎn)離開(kāi)網(wǎng)格或停止服務(wù)以后，網(wǎng)格內(nèi)的節(jié)點(diǎn)需要重新選擇位置服務(wù)器。
    物理距離計(jì)算公式：
 
式中，(x1，y1)、(x2，y2)為網(wǎng)格中心和節(jié)點(diǎn)的坐標(biāo)。
    網(wǎng)格服務(wù)器節(jié)點(diǎn)保存同組網(wǎng)格區(qū)域產(chǎn)生的節(jié)點(diǎn)信息。源節(jié)點(diǎn)要查找目的節(jié)點(diǎn)信息，源節(jié)點(diǎn)可通過(guò)貪心算法向目的節(jié)點(diǎn)所在同一分組內(nèi)某個(gè)特定的網(wǎng)格發(fā)送查找信息。
2.4 位置的更新
    節(jié)點(diǎn)根據(jù)最初產(chǎn)生時(shí)所在的網(wǎng)格獲得節(jié)點(diǎn)ID。節(jié)點(diǎn)把自己的位置信息登記到所在網(wǎng)格的位置服務(wù)節(jié)點(diǎn)中(位置信息包括節(jié)點(diǎn)ID、位置、移動(dòng)的速度、信息更新的時(shí)刻)，節(jié)點(diǎn)定時(shí)Thello向鄰居節(jié)點(diǎn)發(fā)送hello數(shù)據(jù)包，報(bào)告自己的存在。節(jié)點(diǎn)定時(shí)Tstart從節(jié)點(diǎn)產(chǎn)生時(shí)所在分組的網(wǎng)格中選擇離現(xiàn)在物理距離最近的網(wǎng)格，并通過(guò)貪心算法向該網(wǎng)格報(bào)告自己的位置。位置服務(wù)節(jié)點(diǎn)定時(shí)Tserver通過(guò)貪心算法向同組其他網(wǎng)格位置服務(wù)節(jié)點(diǎn)單播本網(wǎng)格產(chǎn)生的節(jié)點(diǎn)的位置信息。
    節(jié)點(diǎn)位置信息更新規(guī)則：
    (1)節(jié)點(diǎn)定時(shí)Thello向周?chē)従庸?jié)點(diǎn)發(fā)送hello數(shù)據(jù)包，報(bào)告自己的存在。
    (2)當(dāng)節(jié)點(diǎn)離開(kāi)當(dāng)前網(wǎng)格時(shí)，向當(dāng)前網(wǎng)格位置服務(wù)器發(fā)送離開(kāi)請(qǐng)求，位置服務(wù)器對(duì)節(jié)點(diǎn)進(jìn)行相應(yīng)的登記。
    (3)節(jié)點(diǎn)離開(kāi)節(jié)點(diǎn)本身產(chǎn)生時(shí)所在網(wǎng)格后，根據(jù)移動(dòng)的距離S0通過(guò)貪心算法向產(chǎn)生時(shí)所在網(wǎng)格分組最近位置服務(wù)節(jié)點(diǎn)發(fā)送位置更新信息，更新時(shí)間的間隔為T(mén)start。如果移動(dòng)的距離小于S0，時(shí)間間隔到了Tstart，也需要向初始網(wǎng)格服務(wù)器發(fā)送自己的位置信息。
    (4)當(dāng)節(jié)點(diǎn)加入一個(gè)新的網(wǎng)格，節(jié)點(diǎn)向周?chē)惶墓?jié)點(diǎn)廣播hello數(shù)據(jù)包，獲得新的位置服務(wù)節(jié)點(diǎn)。
    (5)位置服務(wù)節(jié)點(diǎn)定時(shí)Tserver向同組內(nèi)其他網(wǎng)格的服務(wù)節(jié)點(diǎn)通過(guò)貪心算法轉(zhuǎn)發(fā)本網(wǎng)格產(chǎn)生節(jié)點(diǎn)的位置信息。
    (6)網(wǎng)格服務(wù)器記錄路過(guò)節(jié)點(diǎn)的位置信息，記錄的時(shí)間Tnode大于本網(wǎng)格或映射到本網(wǎng)格節(jié)點(diǎn)的位置信息的時(shí)間Tserver。
    位置更新的例子如圖3所示。節(jié)點(diǎn)9在網(wǎng)格1產(chǎn)生，所以節(jié)點(diǎn)9所在的網(wǎng)格分組(1，8，15，22)，當(dāng)節(jié)點(diǎn)移動(dòng)到網(wǎng)格4時(shí)，網(wǎng)格組內(nèi)網(wǎng)格的中心距離節(jié)點(diǎn)9物理距離最近的網(wǎng)格是網(wǎng)格8，所以節(jié)點(diǎn)9向網(wǎng)格8報(bào)告自己的位置；當(dāng)節(jié)點(diǎn)移動(dòng)到網(wǎng)格10時(shí)，網(wǎng)格內(nèi)網(wǎng)格的中心距離節(jié)點(diǎn)9物理距離最近的網(wǎng)格是15，所以節(jié)點(diǎn)9向網(wǎng)格15報(bào)告自己的位置，由于移動(dòng)的距離和時(shí)間間隔都還沒(méi)到，所以當(dāng)節(jié)點(diǎn)移動(dòng)到網(wǎng)格5時(shí)，不會(huì)向網(wǎng)格組報(bào)告自己的位置，但是網(wǎng)格10的位置服務(wù)器會(huì)保存節(jié)點(diǎn)9離開(kāi)時(shí)的位置信息。網(wǎng)格15定時(shí)向網(wǎng)格1、網(wǎng)格8、網(wǎng)格15、網(wǎng)格22報(bào)告節(jié)點(diǎn)9的位置信息。傳輸方式全部采用貪心算法。

2.5 位置的查找
    當(dāng)源節(jié)點(diǎn)S需要和目的節(jié)點(diǎn)D通信時(shí)，源節(jié)點(diǎn)S需要查找目的節(jié)點(diǎn)D的位置，源節(jié)點(diǎn)S通過(guò)目的節(jié)點(diǎn)D的ID計(jì)算出目的節(jié)點(diǎn)所在的網(wǎng)格組，根據(jù)目的節(jié)點(diǎn)D產(chǎn)生時(shí)所在的網(wǎng)格組內(nèi)網(wǎng)格(G1、G2、G3……Gn)距離源節(jié)點(diǎn)S物理距離，選擇距離源節(jié)點(diǎn)最近的網(wǎng)格Gi，源節(jié)點(diǎn)向最近的網(wǎng)格Gi的位置服務(wù)節(jié)點(diǎn)查找目的節(jié)點(diǎn)D的位置信息，并利用預(yù)測(cè)公式預(yù)測(cè)目的節(jié)點(diǎn)D的位置。預(yù)測(cè)公式：
 
    根據(jù)Sprediction預(yù)測(cè)目的節(jié)點(diǎn)D所在的網(wǎng)格G′，通過(guò)貪心算法向目的節(jié)點(diǎn)所在的網(wǎng)格G′發(fā)送查找信息。如果目的節(jié)點(diǎn)D在查找包到達(dá)的網(wǎng)格G′內(nèi)，則位置已經(jīng)找到；如果不在，但網(wǎng)格G′有目的節(jié)點(diǎn)D離開(kāi)時(shí)的記錄，則根據(jù)預(yù)測(cè)函數(shù)和離開(kāi)時(shí)的位置信息記錄預(yù)測(cè)網(wǎng)格G″，通過(guò)貪心算法向預(yù)測(cè)的網(wǎng)格G″發(fā)送查找信息；如果網(wǎng)格G′沒(méi)有目的節(jié)點(diǎn)D的位置信息，則目的節(jié)點(diǎn)D未到達(dá)網(wǎng)格G′，則要進(jìn)行折半查找，即向查找獲得的目的節(jié)點(diǎn)D的位置與預(yù)測(cè)的目的節(jié)點(diǎn)D的位置的中點(diǎn)所在的網(wǎng)格G?蓯進(jìn)行查找。中點(diǎn)計(jì)算公式：

    如果網(wǎng)格G?蓯有目的節(jié)點(diǎn)D的位置信息，則可根據(jù)這一位置信息預(yù)測(cè)目的節(jié)點(diǎn)D的位置與網(wǎng)格，并通過(guò)貪心算法轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)D預(yù)測(cè)的網(wǎng)格；如果沒(méi)有，則認(rèn)為目的節(jié)點(diǎn)D未到達(dá)網(wǎng)格G?蓯，再進(jìn)行折半查找；循環(huán)執(zhí)行，直到預(yù)測(cè)的網(wǎng)格中心與提供目的節(jié)點(diǎn)位置信息網(wǎng)格中心小于S0或目的節(jié)點(diǎn)D時(shí)停止。
    查找步驟如下：
    (1)當(dāng)源節(jié)點(diǎn)S需要與目的節(jié)點(diǎn)D通信時(shí)，本地的位置信息表中沒(méi)有目的節(jié)點(diǎn)D的位置信息。
    (2)源節(jié)點(diǎn)S首先向本地網(wǎng)格服務(wù)器查找是否有目的節(jié)點(diǎn)D的位置信息，如果有，則停止查找；如果沒(méi)有，則發(fā)起目的節(jié)點(diǎn)D的位置查找。
    (3)源節(jié)點(diǎn)S需要查找目的節(jié)點(diǎn)D，源節(jié)點(diǎn)S根據(jù)目的節(jié)點(diǎn)D的ID計(jì)算出目的節(jié)點(diǎn)D所屬的產(chǎn)生時(shí)所在的網(wǎng)格G1，利用HASH函數(shù)計(jì)算同組網(wǎng)格G2、G3……Gn，從G1~Gn中選擇一個(gè)離當(dāng)前源節(jié)點(diǎn)物理距離最近的網(wǎng)格Gi，并通過(guò)貪心算法向其發(fā)送節(jié)點(diǎn)查找信息。
    (4)根據(jù)網(wǎng)格Gi的服務(wù)器提供的目的節(jié)點(diǎn)D的信息，通過(guò)預(yù)測(cè)函數(shù)計(jì)算目的節(jié)點(diǎn)D所在的網(wǎng)格G′。
    (5)通過(guò)貪心算法向預(yù)測(cè)的目的節(jié)點(diǎn)所在的網(wǎng)格G′轉(zhuǎn)發(fā)查找信息，如果查找包轉(zhuǎn)發(fā)過(guò)程中發(fā)現(xiàn)有新的目的節(jié)點(diǎn)的位置信息，則進(jìn)行更新并及時(shí)調(diào)整轉(zhuǎn)發(fā)策略。
    (6)如果目的節(jié)點(diǎn)D在路由查找包到達(dá)的網(wǎng)格G′內(nèi)，則位置已經(jīng)找到；如果不在，但有離開(kāi)時(shí)的記錄，則根據(jù)離開(kāi)時(shí)的記錄和預(yù)測(cè)函數(shù)預(yù)測(cè)目的節(jié)點(diǎn)在網(wǎng)格G″內(nèi)，向預(yù)測(cè)的網(wǎng)格G″查找，執(zhí)行第5步；如果G′中沒(méi)有目的節(jié)點(diǎn)D的信息，則認(rèn)為目的節(jié)點(diǎn)D未到達(dá)網(wǎng)格G′，執(zhí)行第7步。
    (7)進(jìn)行折半查找，向中點(diǎn)網(wǎng)格查找是否有該目的節(jié)點(diǎn)D的位置信息，如果有，執(zhí)行第4步；如果沒(méi)有，則說(shuō)明二種可能：(1)初始服務(wù)器的節(jié)點(diǎn)D信息失效，這時(shí)應(yīng)該刪除；(2)節(jié)點(diǎn)異常離開(kāi)網(wǎng)絡(luò)，停止查找。
    目的節(jié)點(diǎn)D接收到查找請(qǐng)求包時(shí)，則通過(guò)貪心算法返回包括目的節(jié)點(diǎn)D的位置的信息包到源節(jié)點(diǎn)S。源節(jié)點(diǎn)S緩存目的節(jié)點(diǎn)D的位置信息，這樣位置服務(wù)實(shí)現(xiàn)了目的節(jié)點(diǎn)D的查找。
    位置查找的例子如圖4所示。節(jié)點(diǎn)123要與節(jié)點(diǎn)9通信，首先節(jié)點(diǎn)123計(jì)算出節(jié)點(diǎn)9在網(wǎng)格1產(chǎn)生，計(jì)算出網(wǎng)格1，網(wǎng)格8、網(wǎng)格15、網(wǎng)格22在同一分組。網(wǎng)格組內(nèi)網(wǎng)格的中心距離節(jié)點(diǎn)123物理距離最近的是網(wǎng)格8，網(wǎng)格8提供節(jié)點(diǎn)9的位置信息是在網(wǎng)格10；向網(wǎng)格10查找節(jié)點(diǎn)9，到了網(wǎng)格10以后沒(méi)有找到節(jié)點(diǎn)9，但有節(jié)點(diǎn)9離開(kāi)時(shí)的位置信息，根據(jù)位置信息預(yù)測(cè)出節(jié)點(diǎn)9在網(wǎng)格5；向網(wǎng)格5查找節(jié)點(diǎn)9，網(wǎng)格5也沒(méi)有節(jié)點(diǎn)9，但是有節(jié)點(diǎn)9的位置信息，再次根據(jù)預(yù)測(cè)函數(shù)，預(yù)測(cè)出節(jié)點(diǎn)9在網(wǎng)格3；向網(wǎng)格3查找節(jié)點(diǎn)9，在網(wǎng)格3查找到節(jié)點(diǎn)9，節(jié)點(diǎn)9通過(guò)貪心算法向節(jié)點(diǎn)123回復(fù)自己的位置信息，節(jié)點(diǎn)123收到節(jié)點(diǎn)9的位置信息，這個(gè)時(shí)候位置查找成功。這里轉(zhuǎn)發(fā)方式全部采用貪心算法。

3 位置服務(wù)算法比較
    表1為幾種有關(guān)位置服務(wù)算法的比較。比較規(guī)則如下：(1)局部信息指位置服務(wù)有無(wú)提供除本節(jié)點(diǎn)位置信息以外的其他局部節(jié)點(diǎn)的信息，記錄局部信息對(duì)于移動(dòng)網(wǎng)絡(luò)的無(wú)狀態(tài)通信非常有優(yōu)勢(shì)；(2)健壯性指網(wǎng)絡(luò)中個(gè)別節(jié)點(diǎn)失敗影響到節(jié)點(diǎn)通信的規(guī)模。健壯性越高，影響節(jié)點(diǎn)的數(shù)量越少；(3)復(fù)雜性指位置服務(wù)執(zhí)行操作的復(fù)雜程度。復(fù)雜性越低，位置服務(wù)越簡(jiǎn)單，服務(wù)效率越高；(4)位置服務(wù)器是位置服務(wù)選擇的依據(jù)(有基于位置、基于節(jié)點(diǎn)和網(wǎng)格ID)和位置服務(wù)器主要節(jié)點(diǎn)位置信息的管理；(5)區(qū)域劃分指網(wǎng)絡(luò)是否根據(jù)區(qū)域劃分成小的網(wǎng)絡(luò).區(qū)域劃分能減少網(wǎng)絡(luò)總體能源和帶寬，對(duì)于能源和帶寬有限的MANET非常有意義；(6)更新和查找策略指更新和查找過(guò)程中位置服務(wù)的策略，有單播、廣播、洪泛、樹(shù)形(按照樹(shù)行的方式有規(guī)則的傳播)。因MANET的能量和帶寬非常有限，應(yīng)盡量避免洪泛操作，按一定規(guī)則方式建立起來(lái)的樹(shù)形傳播方式，則方便了鏈路的建立。

    本文結(jié)合MANET中網(wǎng)格位置服務(wù)、可預(yù)測(cè)的位置服務(wù)和HASH分組的方法提出了基于網(wǎng)格可預(yù)測(cè)的位置服務(wù)算法，該算法使用網(wǎng)格來(lái)劃分網(wǎng)絡(luò)，并使用HASH方法對(duì)網(wǎng)格進(jìn)行分組，通過(guò)建立預(yù)測(cè)模型的方法查找目的節(jié)點(diǎn)位置，提高目的節(jié)點(diǎn)位置查找的準(zhǔn)確性。算法中源節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)所在的網(wǎng)格分組，通過(guò)貪心算法向該分組中的網(wǎng)格發(fā)送查找目的節(jié)點(diǎn)的信息，根據(jù)目的節(jié)點(diǎn)的歷史位置信息來(lái)預(yù)測(cè)目的節(jié)點(diǎn)的位置。把網(wǎng)格和預(yù)測(cè)結(jié)合在一起，避免了洪泛，減少了網(wǎng)絡(luò)的帶寬并提高了包的抵達(dá)率，提高了位置服務(wù)的性能。因此，在不增加網(wǎng)絡(luò)帶寬的前提下提高了位置服務(wù)效率，節(jié)約了網(wǎng)絡(luò)的能源和帶寬。
參考文獻(xiàn)
[1] LI J， JANNOTTI J， DE C， et al. A scalable location service for geographic Ad hoc routing[C]. Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom)， 2000:120-130.
[2] SU K F， CHOU C， WANG Wei Tong， et al. Improving data transmission with helping nodes for geographical Ad hoc routing[J]. Computer Networks， 2007，51:4997-5010.
[3] LUO Xin Wei， CAMP T， NAVIDI W. Predictive methods for location services in mobile Ad hoc networks[C]. Proceedings of the 5th IEEE International Workshop on Algorithms for Wireless， Mobile， Ad Hoc and Sensor Networks(WMAN)， 2005:246-252.
[4] DERHAB A， BADACHE N. Balancing the tradeoffs between scalability and availability in mobile Ad hoc networks with a flat hashing-based location service[J]. Ad Hoc Networks， 2008(6):1013-1030.
[5] 于宏毅.無(wú)線(xiàn)移動(dòng)自組織網(wǎng)[M].北京:人民郵電出版社，2005.
[6] 張帆，李德敏，陶莉.基于位置信息的MANET路由協(xié)議綜述[J].計(jì)算機(jī)工程與應(yīng)用，2005(20):120-123.