廖過房，周繼鵬

(暨南大學 信息科學技術學院 計算機系，廣東 廣州 510632)

移動Ad Hoc網(wǎng)絡MANET(Mobile Ad hoc Networks)是一種無基礎設施、自組織和自配置的多跳無線網(wǎng)絡，網(wǎng)絡結構根據(jù)節(jié)點的移動動態(tài)地改變。網(wǎng)絡節(jié)點通過協(xié)作來傳輸信息，通常節(jié)點既作為主機又作為路由器。節(jié)點的移動性使得網(wǎng)絡中拓撲變化頻繁且事先無法預測，所以在MANET中發(fā)現(xiàn)和維護路由是一個至關重要的問題，一直是研究的熱點和難點問題。

近年來，利用地理位置信息的路由協(xié)議在MANET中得到了很大發(fā)展。隨著全球定位技術(GPS)的普遍應用，節(jié)點可以獲得自身準確的位置信息。利用這些信息進行路由可以降低路由協(xié)議的控制開銷、適應動態(tài)變化的網(wǎng)絡拓撲以及提高路由協(xié)議的可擴展性。然而在基于位置信息的路由協(xié)議中，在發(fā)送路由包之前，源節(jié)點需要知道目的節(jié)點的具體位置，主要的問題是基于位置服務的路由協(xié)議中需要位置服務來確定目的節(jié)點的位置，并返回目的節(jié)點的位置信息。

本文從穩(wěn)定高效的角度對基于位置服務算法進行研究，提出了基于網(wǎng)格可預測的位置服務GPLS(Gridbased Predictive Location Service)算法。該算法把整個網(wǎng)絡劃分成平面網(wǎng)格以避免洪泛操作。通過HASH方法對網(wǎng)格進行分組，節(jié)點可以與組內(nèi)任意網(wǎng)格通信，減少了位置更新和查找的步驟和復雜性，節(jié)約了MANET中的能源和帶寬。根據(jù)同組網(wǎng)格內(nèi)任意位置服務節(jié)點提供的目的節(jié)點的位置，預測出目的節(jié)點的位置，提高MANET中位置服務的效率，避免洪泛操作。

1 相關算法

GLS(Grid Location Service)[1]將整個網(wǎng)絡劃分為網(wǎng)格，節(jié)點把它的位置信息分布地存放在網(wǎng)絡中的一個或多個位置服務器中。通過位置服務節(jié)點可隨時查詢網(wǎng)絡中其他節(jié)點的位置，各節(jié)點間采用地理路由轉(zhuǎn)發(fā)進行分組傳輸。HNS(Helping Node Selection)[2]根據(jù)位置服務器中記錄節(jié)點移動的速度和記錄的時間來預判節(jié)點的位置，通過其他移動節(jié)點把數(shù)據(jù)包直接攜帶到預判的位置，再把數(shù)據(jù)包傳輸給目的節(jié)點。這樣既提高了數(shù)據(jù)包的投遞率，又有效地解決了移動自組網(wǎng)絡中節(jié)點動態(tài)移動和空洞問題。PLS(Predictive Location Service)[3]是一個可預測、自適應的平面位置服務。節(jié)點定期向周圍節(jié)點發(fā)送緩存中的位置信息。節(jié)點在整個網(wǎng)絡中洪泛查找目的節(jié)點，接收到信息的節(jié)點根據(jù)緩存中目的節(jié)點的位置信息預測出當前目的節(jié)點的位置。HBLS(Hashing-Based Location Service)[4]是一個基于HASH集合和平面結構的位置服務算法。在當前服務器消失之前選擇一個新的服務器，以提高服務的可靠性和服務的時間。整個網(wǎng)絡區(qū)域劃分為多個不重疊的區(qū)域。在伸縮性和可靠性兩個方面權衡HBLS都是一個很好的算法。

2 算法描述

2.1 系統(tǒng)模型和假設

系統(tǒng)考慮n個節(jié)點在整個網(wǎng)絡中自由移動，節(jié)點通過無線技術彼此進行通信，但是沒有提供固定的網(wǎng)絡基礎設施。假設所有節(jié)點功能相當，都有一個統(tǒng)一的傳輸范圍。每個節(jié)點配備GPS接收裝置，能確定節(jié)點自己的位置，所有在傳輸范圍內(nèi)的節(jié)點都被認為是鄰節(jié)點。節(jié)點既是源，又轉(zhuǎn)發(fā)數(shù)據(jù)，因此形成了MANET。每個節(jié)點有一個唯一的身份標識節(jié)點ID。網(wǎng)絡結構的改變是不可預測的。

2.2 網(wǎng)絡劃分和網(wǎng)格分組

在地理路由中，通常把網(wǎng)絡劃分成多個小網(wǎng)格，每個網(wǎng)格分配一個編號，在每個網(wǎng)格內(nèi)選擇一個合適的節(jié)點作為位置服務節(jié)點(黑點為位置服務節(jié)點)，整個網(wǎng)絡劃分成25個網(wǎng)格，如圖1所示。

圖1 網(wǎng)絡劃分

通過網(wǎng)格 ID，建立一個 HASH函數(shù) f(Gi)=Gi%G0，其中，G0為常數(shù)，Gi為網(wǎng)格的ID。把 f(Gi)相同的分到一組，把一個網(wǎng)格G1內(nèi)的節(jié)點位置信息映射到其他網(wǎng)格G2、G3……Gn，映射到的網(wǎng)格被分到一組(G1、G2、G3……Gn)，位置服務節(jié)點定時向同組內(nèi)其他位置服務節(jié)點傳輸本網(wǎng)格內(nèi)節(jié)點的位置信息。同組的網(wǎng)格盡量均勻分布到整個網(wǎng)絡中。如圖 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中。 依次類推組 2、組 3、組 4、組 5、組 6、組 0。

圖2 通信半徑R與網(wǎng)格大小a

2.3 位置服務器選擇

每個網(wǎng)格內(nèi)有位置服務節(jié)點，選擇離網(wǎng)格中心物理距離最近的節(jié)點作為位置服務節(jié)點。當位置服務節(jié)點離開網(wǎng)格或停止服務以后，網(wǎng)格內(nèi)的節(jié)點需要重新選擇位置服務器。

物理距離計算公式：

式中，(x1，y1)、(x2，y2)為網(wǎng)格中心和節(jié)點的坐標。

網(wǎng)格服務器節(jié)點保存同組網(wǎng)格區(qū)域產(chǎn)生的節(jié)點信息。源節(jié)點要查找目的節(jié)點信息，源節(jié)點可通過貪心算法向目的節(jié)點所在同一分組內(nèi)某個特定的網(wǎng)格發(fā)送查找信息。

2.4 位置的更新

節(jié)點根據(jù)最初產(chǎn)生時所在的網(wǎng)格獲得節(jié)點ID。節(jié)點把自己的位置信息登記到所在網(wǎng)格的位置服務節(jié)點中(位置信息包括節(jié)點 ID、位置、移動的速度、信息更新的時刻)，節(jié)點定時Thello向鄰居節(jié)點發(fā)送hello數(shù)據(jù)包，報告自己的存在。節(jié)點定時Tstart從節(jié)點產(chǎn)生時所在分組的網(wǎng)格中選擇離現(xiàn)在物理距離最近的網(wǎng)格，并通過貪心算法向該網(wǎng)格報告自己的位置。位置服務節(jié)點定時Tserver通過貪心算法向同組其他網(wǎng)格位置服務節(jié)點單播本網(wǎng)格產(chǎn)生的節(jié)點的位置信息。

節(jié)點位置信息更新規(guī)則：

(1)節(jié)點定時Thello向周圍鄰居節(jié)點發(fā)送hello數(shù)據(jù)包，報告自己的存在。

(2)當節(jié)點離開當前網(wǎng)格時，向當前網(wǎng)格位置服務器發(fā)送離開請求，位置服務器對節(jié)點進行相應的登記。

(3)節(jié)點離開節(jié)點本身產(chǎn)生時所在網(wǎng)格后，根據(jù)移動的距離S0通過貪心算法向產(chǎn)生時所在網(wǎng)格分組最近位置服務節(jié)點發(fā)送位置更新信息，更新時間的間隔為Tstart。如果移動的距離小于S0，時間間隔到了Tstart，也需要向初始網(wǎng)格服務器發(fā)送自己的位置信息。

(4)當節(jié)點加入一個新的網(wǎng)格，節(jié)點向周圍一跳的節(jié)點廣播hello數(shù)據(jù)包，獲得新的位置服務節(jié)點。

(5)位置服務節(jié)點定時Tserver向同組內(nèi)其他網(wǎng)格的服務節(jié)點通過貪心算法轉(zhuǎn)發(fā)本網(wǎng)格產(chǎn)生節(jié)點的位置信息。

(6)網(wǎng)格服務器記錄路過節(jié)點的位置信息，記錄的時間Tnode大于本網(wǎng)格或映射到本網(wǎng)格節(jié)點的位置信息的時間Tserver。

位置更新的例子如圖3所示。節(jié)點9在網(wǎng)格1產(chǎn)生，所以節(jié)點 9所在的網(wǎng)格分組(1，8，15，22)，當節(jié)點移動到網(wǎng)格4時，網(wǎng)格組內(nèi)網(wǎng)格的中心距離節(jié)點9物理距離最近的網(wǎng)格是網(wǎng)格8，所以節(jié)點9向網(wǎng)格8報告自己的位置；當節(jié)點移動到網(wǎng)格10時，網(wǎng)格內(nèi)網(wǎng)格的中心距離節(jié)點9物理距離最近的網(wǎng)格是15，所以節(jié)點9向網(wǎng)格15報告自己的位置，由于移動的距離和時間間隔都還沒到，所以當節(jié)點移動到網(wǎng)格5時，不會向網(wǎng)格組報告自己的位置，但是網(wǎng)格10的位置服務器會保存節(jié)點9離開時的位置信息。網(wǎng)格15定時向網(wǎng)格1、網(wǎng)格8、網(wǎng)格15、網(wǎng)格22報告節(jié)點9的位置信息。傳輸方式全部采用貪心算法。

圖3 位置更新

2.5 位置的查找

當源節(jié)點S需要和目的節(jié)點D通信時，源節(jié)點S需要查找目的節(jié)點D的位置，源節(jié)點S通過目的節(jié)點D的ID計算出目的節(jié)點所在的網(wǎng)格組，根據(jù)目的節(jié)點D產(chǎn)生時所在的網(wǎng)格組內(nèi)網(wǎng)格(G1、G2、G3……Gn)距離源節(jié)點S物理距離，選擇距離源節(jié)點最近的網(wǎng)格Gi，源節(jié)點向最近的網(wǎng)格Gi的位置服務節(jié)點查找目的節(jié)點D的位置信息，并利用預測公式預測目的節(jié)點D的位置。預測公式：

式中，T=min (Cprediction/Vrecord，(tnow-trecord))，Srecord為目的節(jié)點 D位置信息的位置，vrecord為目的節(jié)點D的速度，tnow為當前時刻，trecord為記錄信息的時刻，Cprediction為預測因子，用這個常數(shù)避免過度預測。在Cprediction/Vrecord與tnow-trecord中選擇值更小的，能夠更準確地預測目的節(jié)點位置信息并及時調(diào)整查找方向。

根據(jù)Sprediction預測目的節(jié)點D所在的網(wǎng)格G′，通過貪心算法向目的節(jié)點所在的網(wǎng)格G′發(fā)送查找信息。如果目的節(jié)點D在查找包到達的網(wǎng)格G′內(nèi)，則位置已經(jīng)找到；如果不在，但網(wǎng)格G′有目的節(jié)點D離開時的記錄，則根據(jù)預測函數(shù)和離開時的位置信息記錄預測網(wǎng)格G″，通過貪心算法向預測的網(wǎng)格G″發(fā)送查找信息；如果網(wǎng)格G′沒有目的節(jié)點D的位置信息，則目的節(jié)點D未到達網(wǎng)格G′，則要進行折半查找，即向查找獲得的目的節(jié)點D的位置與預測的目的節(jié)點D的位置的中點所在的網(wǎng)格G?進行查找。中點計算公式：

式中|Precond-Pprediction|＞S，Precond為查找獲得的目的節(jié)點 D的位置，Pprediction為預測的目的節(jié)點D的位置，Pnow為查找獲得的目的節(jié)點D的位置與預測的目的節(jié)點D的位置的中點，S0為常數(shù)。當查找獲得的目的節(jié)點D的位置與預測的目的節(jié)點D的位置的距離太短時，預測就沒有意義，所以用S0來限制。

如果網(wǎng)格G?有目的節(jié)點D的位置信息，則可根據(jù)這一位置信息預測目的節(jié)點D的位置與網(wǎng)格，并通過貪心算法轉(zhuǎn)發(fā)到目的節(jié)點D預測的網(wǎng)格；如果沒有，則認為目的節(jié)點D未到達網(wǎng)格G?，再進行折半查找；循環(huán)執(zhí)行，直到預測的網(wǎng)格中心與提供目的節(jié)點位置信息網(wǎng)格中心小于S0或目的節(jié)點D時停止。

查找步驟如下：

(1)當源節(jié)點S需要與目的節(jié)點D通信時，本地的位置信息表中沒有目的節(jié)點D的位置信息。

(2)源節(jié)點S首先向本地網(wǎng)格服務器查找是否有目的節(jié)點D的位置信息，如果有，則停止查找；如果沒有，則發(fā)起目的節(jié)點D的位置查找。

(3)源節(jié)點S需要查找目的節(jié)點D，源節(jié)點S根據(jù)目的節(jié)點D的ID計算出目的節(jié)點D所屬的產(chǎn)生時所在的網(wǎng)格 G1，利用 HASH函數(shù)計算同組網(wǎng)格 G2、G3……Gn，從G1～Gn中選擇一個離當前源節(jié)點物理距離最近的網(wǎng)格Gi，并通過貪心算法向其發(fā)送節(jié)點查找信息。

(4)根據(jù)網(wǎng)格Gi的服務器提供的目的節(jié)點D的信息，通過預測函數(shù)計算目的節(jié)點D所在的網(wǎng)格G′。

(5)通過貪心算法向預測的目的節(jié)點所在的網(wǎng)格G′轉(zhuǎn)發(fā)查找信息，如果查找包轉(zhuǎn)發(fā)過程中發(fā)現(xiàn)有新的目的節(jié)點的位置信息，則進行更新并及時調(diào)整轉(zhuǎn)發(fā)策略。

(6)如果目的節(jié)點D在路由查找包到達的網(wǎng)格G′內(nèi)，則位置已經(jīng)找到；如果不在，但有離開時的記錄，則根據(jù)離開時的記錄和預測函數(shù)預測目的節(jié)點在網(wǎng)格G″內(nèi)，向預測的網(wǎng)格G″查找，執(zhí)行第5步；如果G′中沒有目的節(jié)點D的信息，則認為目的節(jié)點D未到達網(wǎng)格G′，執(zhí)行第7步。

(7)進行折半查找，向中點網(wǎng)格查找是否有該目的節(jié)點D的位置信息，如果有，執(zhí)行第 4步；如果沒有，則說明二種可能：(1)初始服務器的節(jié)點D信息失效，這時應該刪除；(2)節(jié)點異常離開網(wǎng)絡，停止查找。

目的節(jié)點D接收到查找請求包時，則通過貪心算法返回包括目的節(jié)點D的位置的信息包到源節(jié)點S。源節(jié)點S緩存目的節(jié)點D的位置信息，這樣位置服務實現(xiàn)了目的節(jié)點D的查找。

位置查找的例子如圖4所示。節(jié)點123要與節(jié)點9通信，首先節(jié)點123計算出節(jié)點9在網(wǎng)格 1產(chǎn)生，計算出網(wǎng)格 1，網(wǎng)格8、網(wǎng)格 15、網(wǎng)格 22在同一分組。網(wǎng)格組內(nèi)網(wǎng)格的中心距離節(jié)點123物理距離最近的是網(wǎng)格8，網(wǎng)格8提供節(jié)點9的位置信息是在網(wǎng)格10；向網(wǎng)格10查找節(jié)點9，到了網(wǎng)格10以后沒有找到節(jié)點9，但有節(jié)點9離開時的位置信息，根據(jù)位置信息預測出節(jié)點9在網(wǎng)格 5；向網(wǎng)格 5查找節(jié)點 9，網(wǎng)格 5也沒有節(jié)點 9，但是有節(jié)點9的位置信息，再次根據(jù)預測函數(shù)，預測出節(jié)點9在網(wǎng)格3；向網(wǎng)格3查找節(jié)點9，在網(wǎng)格3查找到節(jié)點9，節(jié)點9通過貪心算法向節(jié)點123回復自己的位置信息，節(jié)點123收到節(jié)點9的位置信息，這個時候位置查找成功。這里轉(zhuǎn)發(fā)方式全部采用貪心算法。

圖4 位置查找

3 位置服務算法比較

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

本文結合MANET中網(wǎng)格位置服務、可預測的位置服務和HASH分組的方法提出了基于網(wǎng)格可預測的位置服務算法，該算法使用網(wǎng)格來劃分網(wǎng)絡，并使用HASH方法對網(wǎng)格進行分組，通過建立預測模型的方法查找目的節(jié)點位置，提高目的節(jié)點位置查找的準確性。算法中源節(jié)點根據(jù)目的節(jié)點所在的網(wǎng)格分組，通過貪心算法向該分組中的網(wǎng)格發(fā)送查找目的節(jié)點的信息，根據(jù)目的節(jié)點的歷史位置信息來預測目的節(jié)點的位置。把網(wǎng)格和預測結合在一起，避免了洪泛，減少了網(wǎng)絡的帶寬并提高了包的抵達率，提高了位置服務的性能。因此，在不增加網(wǎng)絡帶寬的前提下提高了位置服務效率，節(jié)約了網(wǎng)絡的能源和帶寬。

表1 相關算法比較

[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ǎng)[M].北京:人民郵電出版社，2005.

[6]張帆，李德敏，陶莉.基于位置信息的MANET路由協(xié)議綜述[J].計算機工程與應用，2005(20):120-123.