面向群組移動(dòng)的輕型位置服務(wù)研究

杜慧+范小菁

摘 要： 針對(duì)現(xiàn)實(shí)應(yīng)用中大規(guī)模MANET網(wǎng)絡(luò)節(jié)點(diǎn)呈現(xiàn)的群組移動(dòng)特性，提出了面向群組移動(dòng)的輕型位置服務(wù)協(xié)議G?HLLS。G?HLLS協(xié)議將HLLS協(xié)議框架與分簇機(jī)制相結(jié)合，從而保證位置更新及請(qǐng)求機(jī)制適應(yīng)群組移動(dòng)特性。基于OPNET的仿真實(shí)驗(yàn)，從負(fù)載、服務(wù)成功率、存儲(chǔ)開銷多個(gè)方面對(duì)G?HLLS協(xié)議性能進(jìn)行了分析，驗(yàn)證了G?HLLS協(xié)議在大規(guī)模群組移動(dòng)網(wǎng)絡(luò)中表現(xiàn)出的優(yōu)越性能。

關(guān)鍵詞： MANET； G?HLLS； HLLS； OPNET

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）18?0075?06

Research on group mobility oriented HLLS

DU Hui， FAN Xiao?jing

（1. Shaanxi Open University， Xian 710068， China； 2. Fujitsu Research & Development Center， Beijing 100025， China）

Abstract： Group mobility oriented HLLS （G?HLLS） is proposes in this paper， according to the group mobility property of large?scale MANET nodes in many actual applications. G?HLLS combines the protocol frame of history information based light location service （HLLS） with clustering mechanism to ensure the location update and request mechanism to adapt the property of group mobility and reduce the storage cost of HLLS. With the simulation based on OPNET， the protocol performance of G?HLLS is analysed in terms of loading， service success ratio， overhead and storage costs. The resulsts show that G?HLLS has good scalability in MANET with group mobility.

Keywords： MANET； G?HLLS； HLLS； OPNET

移動(dòng)Ad Hoc網(wǎng)絡(luò)（Mobile Ad Hoc Network，MANET）在國(guó)民經(jīng)濟(jì)的多個(gè)領(lǐng)域都有著十分廣闊的應(yīng)用前景?？蓴U(kuò)展性路由協(xié)議的設(shè)計(jì)多年來一直是MANET研究中的一項(xiàng)關(guān)鍵內(nèi)容。基于地理位置的路由協(xié)議具有良好的可擴(kuò)展性能，而地理位置路由必需位置服務(wù)協(xié)議支持，因此可擴(kuò)展位置服務(wù)協(xié)議的研究成為近年來MANET領(lǐng)域內(nèi)學(xué)者們普遍關(guān)注的重點(diǎn)和熱點(diǎn)。

1 國(guó)內(nèi)外現(xiàn)狀

國(guó)外學(xué)者較早開展針對(duì)位置服務(wù)協(xié)議的研究，并已經(jīng)進(jìn)入一定的深度，主要分為基于洪泛和基于團(tuán)體兩大類。早期的研究成果多為基于洪泛的，DLS[1]是這一類的代表。近期的研究多為基于團(tuán)體類型，GLS[2]、XYLS[3]、GHLS[4]是三個(gè)典型代表，當(dāng)前很多位置服務(wù)協(xié)議都從中借鑒了一些思想?？傮w來說，基于團(tuán)體位置服務(wù)器的設(shè)計(jì)核心在于研究位置服務(wù)器的征召算法，上述各協(xié)議的根本區(qū)別也在于此。優(yōu)秀的征召算法能夠保證節(jié)點(diǎn)征召較少的位置服務(wù)器，就能夠達(dá)到較好的位置服務(wù)成功率及準(zhǔn)確率。

國(guó)內(nèi)對(duì)于位置服務(wù)協(xié)議的研究相對(duì)較少，大部分研究成果是在已有經(jīng)典協(xié)議的基礎(chǔ)上做改進(jìn)擴(kuò)充。如MHRLS[5]（MultipleHome Regions based Location Service）、GrLS[6]、HFPT[7]（Hierarchical Forwarding Pointer with Thresholds）。還有學(xué)者獨(dú)創(chuàng)性地利用分簇機(jī)制在可擴(kuò)展性方面的優(yōu)勢(shì)解決位置服務(wù)問題[8?9]，如KCLS[8]。

國(guó)內(nèi)外目前已經(jīng)出現(xiàn)了針對(duì)不同應(yīng)用環(huán)境的多種形態(tài)位置服務(wù)。但是這些位置服務(wù)大多在傳統(tǒng)服務(wù)模式之上改進(jìn)而來，在可擴(kuò)展性方面并未取得明顯的突破，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，協(xié)議的性能將惡化。主要存在的問題可以歸結(jié)為：

（1） 協(xié)議機(jī)制過于復(fù)雜；

（2） 位置更新負(fù)載重；

（3） 網(wǎng)絡(luò)負(fù)載極度不平衡；

（4） 大部分位置服務(wù)協(xié)議都未考慮節(jié)點(diǎn)群組移動(dòng)的特點(diǎn)。

2 基于歷史信息的輕型位置服務(wù)協(xié)議HLLS簡(jiǎn)介

HLLS[10?11]（History information based Light Location Service）打破了上述位置服務(wù)算法傳統(tǒng)格局，創(chuàng)新地基于歷史信息對(duì)接點(diǎn)位置進(jìn)行追蹤。在HLLS中，一個(gè)節(jié)點(diǎn)可以征召任意節(jié)點(diǎn)為自身的位置服務(wù)器，并且為每一條位置信息關(guān)聯(lián)時(shí)間戳，記錄該信息被更新的時(shí)間。因此對(duì)于某單個(gè)節(jié)點(diǎn)，在其移動(dòng)過程中，向沿途遇到的任意其他節(jié)點(diǎn)更新自身當(dāng)前位置信息，并保存當(dāng)前位置記錄時(shí)間，從而使得不同節(jié)點(diǎn)所保存的位置信息新鮮程度不同。當(dāng)其他階段需要請(qǐng)求該節(jié)點(diǎn)位置信息時(shí)，則沿著位置信息的時(shí)間梯度，由較為陳舊的位置信息開始逐漸追蹤到該節(jié)點(diǎn)的最新位置信息，完成最終的位置請(qǐng)求。位置更新的過程利用鄰居節(jié)點(diǎn)之間周期發(fā)送的Hello包完成（鄰居節(jié)點(diǎn)周期交換Hello包被大部分MANET網(wǎng)絡(luò)采用，用于維護(hù)網(wǎng)絡(luò)連通），因此HLLS算法開銷很小，并且位置服務(wù)準(zhǔn)確度高。

3 面向群組移動(dòng)的位置服務(wù)協(xié)議

HLLS協(xié)議設(shè)計(jì)沒有針對(duì)任何特殊的場(chǎng)景，但是群組移動(dòng)的特性廣泛存在于災(zāi)后救援、戰(zhàn)場(chǎng)通信等大規(guī)模移動(dòng)Ad Hoc網(wǎng)絡(luò)應(yīng)用場(chǎng)景[6]，為了提高位置服務(wù)協(xié)議在大規(guī)模群組移動(dòng)性MANET中的可擴(kuò)展性，利用分簇機(jī)制管理群組，在基于歷史信息的輕型位置服務(wù)框架中引入群組移動(dòng)特性，設(shè)計(jì)出面向群組移動(dòng)的位置服務(wù)協(xié)議（Group mobility oriented HLLS，G?HLLS）。

3.1 網(wǎng)絡(luò)模型

3.1.1 G?HLLS協(xié)議位置信息定義

在G?HLLS協(xié)議設(shè)計(jì)中，網(wǎng)絡(luò)節(jié)點(diǎn)劃分為簇首、簇成員兩種類型，因此位置信息也分為兩種類型。簇首節(jié)點(diǎn)位置信息包括：位置坐標(biāo)、速度、時(shí)間戳、成員列表4項(xiàng)元素。簇成員節(jié)點(diǎn)的位置信息包括：位置坐標(biāo)、時(shí)間戳。

3.1.2 G?HLLS協(xié)議群組移動(dòng)模型定義

在G?HLLS協(xié)議所針對(duì)的群組移動(dòng)中，全部網(wǎng)絡(luò)節(jié)點(diǎn)劃分為多個(gè)群組，每個(gè)群組中存在一個(gè)群首節(jié)點(diǎn)。同一群組中的節(jié)點(diǎn)共同移動(dòng)，群首節(jié)點(diǎn)決定移動(dòng)的方向和速度，群組中其他成員移動(dòng)速度、方向與群首相同，因此同一群組具有相似的位置軌跡。具體定義如下：

群首節(jié)點(diǎn)：執(zhí)行Random Waypoint移動(dòng)模型的算法，即從初始位置開始，在網(wǎng)絡(luò)區(qū)域隨機(jī)選定一個(gè)目標(biāo)位置，在[1，Vmax] m/s之間隨機(jī)選取一個(gè)移動(dòng)速率，然后以選定的速率向目標(biāo)位置移動(dòng)。但到達(dá)目標(biāo)位置后需要等待同一群組成員均到達(dá)預(yù)定目標(biāo)，然后再進(jìn)行下一輪目標(biāo)選擇。

普通節(jié)點(diǎn)：從初始位置開始，在以群首目標(biāo)位置為圓心、λR為半徑的圓域內(nèi)，隨機(jī)選取一點(diǎn)為目標(biāo)位置，以群首速率為移動(dòng)速率，向選定的目標(biāo)位置移動(dòng)。到達(dá)目標(biāo)后等待，直至同群組的全部節(jié)點(diǎn)到達(dá)預(yù)設(shè)目標(biāo)后，再進(jìn)行下一輪目標(biāo)選取。此外普通節(jié)點(diǎn)還需要周期性更換簇首。

3.2 面向群組移動(dòng)的輕型位置服務(wù)協(xié)議

3.2.1 G?HLLS協(xié)議思想概述

G?HLLS依賴HELLO包進(jìn)行位置更新，位置請(qǐng)求機(jī)制核心也采用基于歷史信息追蹤對(duì)目的節(jié)點(diǎn)的追蹤形式，但由于單個(gè)節(jié)點(diǎn)維護(hù)的信息量減少，位置更新、位置請(qǐng)求的具體機(jī)制在HLLS算法的基礎(chǔ)上改進(jìn)。圖1顯示了G?HLLS協(xié)議的主要思想。G?HLLS協(xié)議將面型群組移動(dòng)的位置服務(wù)與分簇機(jī)制相結(jié)合，同一移動(dòng)群組的節(jié)點(diǎn)組成一個(gè)簇，并且該移動(dòng)群組的群首節(jié)點(diǎn)作為本簇的簇首，負(fù)責(zé)收集維護(hù)簇內(nèi)成員的位置信息。

圖1 G?HLLS協(xié)議思想示意圖

在G?HLLS協(xié)議中，每個(gè)節(jié)點(diǎn)本地位置數(shù)據(jù)庫(kù)只保存各簇首的位置信息，如圖1所示灰色節(jié)點(diǎn)，顏色越深節(jié)點(diǎn)所保存的信息時(shí)間戳越新。因此對(duì)簇首節(jié)點(diǎn)的位置請(qǐng)求，可以直接基于分布式簇首位置數(shù)據(jù)庫(kù)中的歷史位置信息對(duì)其進(jìn)行追蹤。但是對(duì)簇成員節(jié)點(diǎn)的位置請(qǐng)求需要轉(zhuǎn)化為對(duì)其所在簇簇首節(jié)點(diǎn)的追蹤，并由簇首節(jié)點(diǎn)將位置請(qǐng)求包轉(zhuǎn)交給被請(qǐng)求成員。但簇成員節(jié)點(diǎn)可能更換簇，因此對(duì)簇成員的位置請(qǐng)求過程，需要隨時(shí)檢查該節(jié)點(diǎn)是否已經(jīng)離開原簇、加入新簇，這一過程稱作雙指針追蹤。圖1舉例顯示了對(duì)Dn節(jié)點(diǎn)的位置請(qǐng)求路徑（圖中省略了與本次位置請(qǐng)求無(wú)關(guān)的網(wǎng)絡(luò)節(jié)點(diǎn)）。Dn原本屬于簇首C1所在簇，后加入簇首C2所在簇。源節(jié)點(diǎn)Sn發(fā)起對(duì)Dn的位置請(qǐng)求，根據(jù)本地存儲(chǔ)歷史信息認(rèn)為Dn屬于C1所在簇，因此將位置請(qǐng)求包發(fā)往簇首C1，這一階段按照基于歷史信息的目標(biāo)追蹤策略轉(zhuǎn)發(fā)位置請(qǐng)求包。節(jié)點(diǎn)Pn曾經(jīng)與簇首C2在L0位置相遇，獲知Dn已經(jīng)加入C2所在簇，因而當(dāng)節(jié)點(diǎn)Pn轉(zhuǎn)發(fā)位置請(qǐng)求包時(shí)，不會(huì)再向C1發(fā)送，轉(zhuǎn)而發(fā)往C2的歷史位置L0。諸如Pn這樣的節(jié)點(diǎn)稱作簇指針節(jié)點(diǎn)，能夠指示目的節(jié)點(diǎn)的簇首變更情況。從Pn發(fā)往C2這一階段，繼續(xù)遵照基于歷史信息的目的追蹤策略轉(zhuǎn)發(fā)位置請(qǐng)求包，其中參與了請(qǐng)求包的轉(zhuǎn)發(fā)并且能夠指示目的簇首新位置坐標(biāo)的節(jié)點(diǎn)稱作簇首位置指針節(jié)點(diǎn)，類似于HLLS協(xié)議中的指針節(jié)點(diǎn)。跟隨簇首位置指針節(jié)點(diǎn)的引導(dǎo)，位置請(qǐng)求包被發(fā)送給簇首C2，C2再轉(zhuǎn)交給目的節(jié)點(diǎn)Dn，Dn將其當(dāng)前位置信息通過貪婪路由直接返回給源節(jié)點(diǎn)Sn，最終完成此次位置請(qǐng)求及響應(yīng)。

為了支持上述G?HLLS服務(wù)機(jī)制，簇首及簇成員節(jié)點(diǎn)需要保存并維護(hù)一定的信息，下面分類具體介紹。

（1） 簇首節(jié)點(diǎn)需要維護(hù)：

① 鄰居列表（NT），保存當(dāng)前鄰居ID及位置信息；

② 本地位置數(shù)據(jù)庫(kù)（LLDB），保存網(wǎng)絡(luò)中全部簇首ID及位置信息；

③ 簇成員列表（MT），保存本簇當(dāng)前全部成員ID及位置信息。

（2） 簇成員節(jié)點(diǎn)需要維護(hù)：

① 鄰居列表（NT），保存當(dāng)前鄰居ID及位置信息；

② 本地位置數(shù)據(jù)庫(kù)（LLDB），保存網(wǎng)絡(luò)中全部簇首ID及位置信息。

G?HLLS協(xié)議主要分為四個(gè)部分：首先執(zhí)行協(xié)議初始化機(jī)制在各節(jié)點(diǎn)建立LLDB；然后對(duì)LLDB 進(jìn)行日常位置更新；當(dāng)源節(jié)點(diǎn)需要請(qǐng)求目的位置信息時(shí)觸發(fā)位置請(qǐng)求及響應(yīng)機(jī)制；位置請(qǐng)求失敗則轉(zhuǎn)入請(qǐng)求恢復(fù)機(jī)制。

3.2.2 協(xié)議初始化

G?HLLS協(xié)議初始化機(jī)制的任務(wù)是保證全部網(wǎng)絡(luò)節(jié)點(diǎn)建立起本地位置數(shù)據(jù)庫(kù)LLDB，其中保存了網(wǎng)絡(luò)中全部簇首節(jié)點(diǎn)ID及簇首位置信息，因此每個(gè)簇首節(jié)點(diǎn)需要將自身信息散布全網(wǎng)。為了實(shí)現(xiàn)該目標(biāo)，G?HLLS基于傳染病算法思想實(shí)現(xiàn)低負(fù)載、可靠的多播，每個(gè)簇首節(jié)點(diǎn)將自身的ID及位置信息散布給其他簇首。

在G?HLLS協(xié)議初始化過程中，每個(gè)節(jié)點(diǎn)（無(wú)論簇首還是簇成員）首先通過簇首節(jié)點(diǎn)在直接鄰居范圍內(nèi)廣播的HELLO包收集簇首位置信息，即如果收到簇首節(jié)點(diǎn)發(fā)來地HELLO包，則將其中的位置信息插入LLDB。當(dāng)LLDB中新增記錄數(shù)目超過Ngossip之后，則將新增記錄的簇首ID形成列表作為Gossip信息捆綁在HELLO包中廣播出去，同樣把這種特殊的HELLO包稱作HELLO_GP。鄰居節(jié)點(diǎn)收到HELLO_GP則檢查其中是否存在本地LLDB還未保存的簇首ID，如果有，則單播發(fā)送缺失請(qǐng)求包MREQ包給HELLO_GP源節(jié)點(diǎn)，從而請(qǐng)求缺失的簇首信息；HELLO_GP源節(jié)點(diǎn)收到MREQ，則單播返回MREP，返回被請(qǐng)求的簇首位置信息。這一過程在全網(wǎng)范圍內(nèi)以分布式的方式重復(fù)，則最終每個(gè)簇首位置信息能散布到網(wǎng)絡(luò)中其他簇首并被保存。

3.2.3 位置更新機(jī)制

G?HLLS協(xié)議的位置更新機(jī)制包括兩部分：局部位置更新、全局位置更新。局部位置更新限制在簇內(nèi)，即簇首對(duì)本簇成員的位置信息維護(hù)。全局位置更新主要任務(wù)是對(duì)各節(jié)點(diǎn)LLDB進(jìn)行更新，即在全網(wǎng)范圍內(nèi)更新簇首節(jié)點(diǎn)的位置信息。

（1） 局部位置更新

根據(jù)群組移動(dòng)模型的定義，每個(gè)群組成員（即簇成員節(jié)點(diǎn)）在選擇下一移動(dòng)目標(biāo)時(shí)已知群首（即簇首節(jié)點(diǎn)）的目標(biāo)位置及移動(dòng)速度，并且所有節(jié)點(diǎn)采用勻速直線運(yùn)動(dòng)向著移動(dòng)目標(biāo)靠近。簇成員節(jié)點(diǎn)能夠根據(jù)勻速直線運(yùn)動(dòng)公式計(jì)算任意時(shí)刻本簇首的位置坐標(biāo)，因此局部位置更新的任務(wù)僅為實(shí)現(xiàn)簇首對(duì)全部簇成員的位置信息實(shí)時(shí)可知。

局部位置更新要求在每個(gè)簇內(nèi)，簇成員節(jié)點(diǎn)周期性地向簇首節(jié)點(diǎn)單播發(fā)送成員位置更新包（Member Location Update Packet，MLUP）。MLUP中包含簇成員自身ID及位置信息二元組（即當(dāng)前位置坐標(biāo)、時(shí)間戳），MLUP的路由通過貪婪轉(zhuǎn)發(fā)方式實(shí)現(xiàn)。簇首節(jié)點(diǎn)收到位置更新包，則將其中包含的ID及位置信息插入或更新本地成員列表。

（2） 全局位置更新

全局位置更新的任務(wù)是實(shí)時(shí)更新全網(wǎng)范圍內(nèi)各節(jié)點(diǎn)的LLDB。G?HLLS協(xié)議借助HELLO包、DATA包及LRP包中的位置信息對(duì)LLDB進(jìn)行捎帶更新。具體說明如下，任意節(jié)點(diǎn)在以下三種情況下進(jìn)行全局位置更新：

① 當(dāng)節(jié)點(diǎn)收到HELLO包，如果源節(jié)點(diǎn)為簇首節(jié)點(diǎn)，則利用HELLO包攜帶的簇首ID及位置信息四元組對(duì)本地LLDB及鄰居列表NT同時(shí)進(jìn)行更新；如果源節(jié)點(diǎn)是簇成員，則僅利用HELLO包攜帶的成員ID及位置信息二元組更新NT。

② 當(dāng)節(jié)點(diǎn)收到DATA包，如果源、目的節(jié)點(diǎn)至少有一個(gè)為簇首節(jié)點(diǎn)，則利用相應(yīng)的簇首ID及位置信息四元組對(duì)本地LLDB進(jìn)行更新，然后將DATA包轉(zhuǎn)發(fā)出去；如果源、目的節(jié)點(diǎn)都為簇成員，則不做更新，直接轉(zhuǎn)發(fā)出去。

③ 當(dāng)節(jié)點(diǎn)收到LRP包，如果包中源信息為簇首節(jié)點(diǎn)，則利用該簇首節(jié)點(diǎn)的ID及位置信息對(duì)本地LLDB進(jìn)行更新，然后將LRP轉(zhuǎn)發(fā)出去；如果源信息不是簇首，則不做更新，直接轉(zhuǎn)發(fā)出去。

LLDB的具體更新算法為，利用HELLO/DATA/LRP包中簇首ID搜索本地LLDB，找到該ID所對(duì)應(yīng)記錄，對(duì)比包中簇首位置信息時(shí)間戳與找到記錄的時(shí)間戳，如果包中信息的時(shí)間戳較新，則用包中簇首位置信息代替找到的本地記錄，否則不操作。

3.2.4 位置請(qǐng)求及響應(yīng)機(jī)制

G?HLLS協(xié)議初始化及位置更新機(jī)制在全網(wǎng)范圍內(nèi)的LLDB建立起簇首節(jié)點(diǎn)的分布式位置數(shù)據(jù)庫(kù)，并且其中的位置信息呈現(xiàn)梯度的時(shí)間戳?；谶@樣的分布式簇首位置數(shù)據(jù)庫(kù)，能夠直接利用HLLS協(xié)議的基于歷史信息的追蹤機(jī)制實(shí)現(xiàn)對(duì)簇首節(jié)點(diǎn)的位置請(qǐng)求，而對(duì)簇成員節(jié)點(diǎn)的位置請(qǐng)求將由其所在簇簇首代理，轉(zhuǎn)化為對(duì)其簇首的位置請(qǐng)求。為了實(shí)現(xiàn)上述過程，需要請(qǐng)求源節(jié)點(diǎn)發(fā)起位置請(qǐng)求包（Location Query Packet，LQP），將LQP發(fā)送至被請(qǐng)求的目的節(jié)點(diǎn)；目的節(jié)點(diǎn)收到LQP則發(fā)起位置響應(yīng)包（Location Reply Packet，LRP），將自身當(dāng)前位置信息返回給請(qǐng)求源節(jié)點(diǎn)。任意節(jié)點(diǎn)對(duì)簇首節(jié)點(diǎn)的位置請(qǐng)求可以按照HLLS協(xié)議的位置請(qǐng)求算法執(zhí)行，下面詳細(xì)介紹對(duì)簇成員節(jié)點(diǎn)的位置請(qǐng)求算法。

同樣以一對(duì)請(qǐng)求源、目的節(jié)點(diǎn)為例進(jìn)行說明，Snode為網(wǎng)絡(luò)中任一請(qǐng)求源節(jié)點(diǎn)，Dnode為被請(qǐng)求的目的節(jié)點(diǎn)，且Dnode為簇成員節(jié)點(diǎn)，對(duì)Dnode的位置請(qǐng)求算法步驟如下：

Step1： Snode生成LQP包，將自身ID及位置信息填入LQP作為源節(jié)點(diǎn)信息，根據(jù)Dnode的ID搜索LLDB找到Dnode所屬簇首位置信息記錄，將Dnode的ID、其簇首ID及位置四元組填入LQP，目的節(jié)點(diǎn)位置信息字段不填寫，然后將LQP發(fā)往目的簇首，利用目的簇首位置根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳。

Step2： 任意節(jié)點(diǎn)i收到LQP包，利用Dnode的ID搜索本地LLDB，檢查Dnode是否更換簇首：

（1） 如果更換，則將Dnode新簇首ID、位置信息四元組填入LQP，然后根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳，將LQP發(fā)往新簇首；

（2） 如果沒有更換，則對(duì)比LLDB中的Dnode簇首信息與LQP包中簇首信息時(shí)間戳；

（3） 如果LLDB中簇首信息時(shí)間戳較新，則將LLDB中找到的Dnode簇首位置四元組填入LQP，然后根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳，繼續(xù)將LQP發(fā)往目的簇首；

（4） 如果LQP包中簇首信息時(shí)間戳較新，則用LQP包中簇首位置四元組更新LLDB的記錄，然后根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳，繼續(xù)將LQP發(fā)往目的簇首；

（5） 重復(fù)Step2，直至LQP的目的簇首ID字段所指示節(jié)點(diǎn)接收到LQP，則轉(zhuǎn)Step3。

Step3： LQP的目的簇首ID字段所指示節(jié)點(diǎn)接收到LQP，則用Dnode的ID檢索本地成員列表，檢查自身是否為Dnode當(dāng)前所屬簇首：

（1） 如果是，則將成員列表中Dnode位置信息二元組填入LQP包的目的節(jié)點(diǎn)位置信息字段，通過貪婪路由直接將LQP發(fā)往Dnode；

（2） 如果不是，則轉(zhuǎn)Step2。

Step4： Dnode收到LQP包，則生成LRP包，將自身ID及當(dāng)前位置信息二元組填入LRP包作為源信息，將LQP所攜帶Snode節(jié)點(diǎn)ID及位置信息填入LRP作為目的信息，然后根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳，將LRP直接發(fā)往Snode。

Step5： 任意節(jié)點(diǎn)i收到LRP，Dnode為簇成員節(jié)點(diǎn)故不做捎帶更新，直接根據(jù)貪婪轉(zhuǎn)發(fā)機(jī)制計(jì)算路由下一跳，將LRP發(fā)送出去，重復(fù)Step5，直至LRP被Snode接收。

Step6： Snode接收到LRP，獲得LRP所攜帶Dnode位置信息二元組，則完成此次位置請(qǐng)求及響應(yīng)。

3.2.5 位置請(qǐng)求恢復(fù)機(jī)制

在上述G?HLLS位置請(qǐng)求機(jī)制中也可能出現(xiàn)追蹤困境，即LQP已經(jīng)到達(dá)目的簇首位置字段所指示區(qū)域，且在轉(zhuǎn)發(fā)節(jié)點(diǎn)本地LLDB無(wú)法找到目的簇首更新的歷史位置，則無(wú)法繼續(xù)轉(zhuǎn)發(fā)。G?HLLS協(xié)議的簇首位置信息包含了四個(gè)元素：位置坐標(biāo)、速度、時(shí)間戳和成員列表。因而可以利用簇首的歷史位置坐標(biāo)、速度及時(shí)間戳對(duì)目的簇首的新位置進(jìn)行預(yù)測(cè)，然后將LQP通過貪婪路由發(fā)往目的簇首的預(yù)測(cè)位置，在這一過程中可以繼續(xù)重復(fù)第3.2.4節(jié)位置請(qǐng)求算法步驟中的Step2，恢復(fù)對(duì)目的簇首的追蹤。

4 G?HLLS節(jié)點(diǎn)存儲(chǔ)開銷分析

從上述G?HLLS協(xié)議說明可以看出，只有簇首節(jié)點(diǎn)位置信息參與協(xié)議初始化、全局位置更新，與HLLS協(xié)議相比，有效削減了單個(gè)節(jié)點(diǎn)維護(hù)信息，降低了節(jié)點(diǎn)存儲(chǔ)開銷。為了驗(yàn)證G?HLLS對(duì)HLLS協(xié)議存儲(chǔ)開銷的優(yōu)化效果，本節(jié)將對(duì)G?HLLS、HLLS協(xié)議平均存儲(chǔ)開銷進(jìn)行理論分析；同時(shí)參與分析的還包括GLS及GREASE，進(jìn)一步將G?HLLS、HLLS的存儲(chǔ)開銷與其他位置服務(wù)進(jìn)行對(duì)比。在以下分析中，假設(shè)網(wǎng)絡(luò)中包含N個(gè)節(jié)點(diǎn)。

在HLLS協(xié)議中，每個(gè)節(jié)點(diǎn)需要保存網(wǎng)絡(luò)中其他全部節(jié)點(diǎn)的位置信息，因此本地位置數(shù)據(jù)庫(kù)中需要包括網(wǎng)絡(luò)所有節(jié)點(diǎn)的記錄，存儲(chǔ)開銷為O（N）。

在G?HLLS協(xié)議中，假設(shè)群組移動(dòng)模型中各群組規(guī)模為a。本地位置數(shù)據(jù)庫(kù)LLDB中包含全部簇首節(jié)點(diǎn)位置信息，記錄數(shù)目為[Na]。簇成員節(jié)點(diǎn)只需維護(hù)LLDB，但簇首節(jié)點(diǎn)同時(shí)需要維護(hù)LLDB及簇成員列表MT，MT包含本簇全部成員位置信息，記錄數(shù)目為a。因此，G?HLLS協(xié)議平均每個(gè)節(jié)點(diǎn)需要維護(hù)位置信息記錄數(shù)目用公式表示為：

[NaN-Na+Na+aNaN=Na+1]

則G?HLLS協(xié)議平均節(jié)點(diǎn)存儲(chǔ)開銷為O（[Na]+1 ）。在GLS協(xié)議中，每個(gè)節(jié)點(diǎn)的位置信息記錄需要保存在3log4 （N）個(gè)位置服務(wù)器之上[4]。并且GLS協(xié)議選舉位置服務(wù)器采用的分層哈希函數(shù)保證了位置服務(wù)任務(wù)在各節(jié)點(diǎn)之間均衡分布，即每個(gè)節(jié)點(diǎn)保存的位置信息記錄數(shù)目均衡，因此GLS協(xié)議節(jié)點(diǎn)平均存儲(chǔ)開銷[11]為O（log N）。

在GREASE協(xié)議中，每個(gè)節(jié)點(diǎn)保存曾經(jīng)與自身相遇的其他節(jié)點(diǎn)位置信息，在網(wǎng)絡(luò)節(jié)點(diǎn)整體移動(dòng)性較弱的情況下，每個(gè)節(jié)點(diǎn)只能遇到較少數(shù)目的節(jié)點(diǎn)，相應(yīng)地節(jié)點(diǎn)存儲(chǔ)開銷也較??；反之存儲(chǔ)開銷較大。在存儲(chǔ)開銷最大的情況下，每對(duì)節(jié)點(diǎn)曾經(jīng)相遇并相互保存位置信息，則GREASE平均節(jié)點(diǎn)存儲(chǔ)開銷為O（N）。但實(shí)際GREASE存儲(chǔ)開銷越大，其位置服務(wù)成功率越高。

從表1可以看出，GLS協(xié)議存儲(chǔ)開銷較小，G?HLLS協(xié)議存儲(chǔ)開銷中等，HLLS及GREASE協(xié)議存儲(chǔ)開銷較大。但存儲(chǔ)開銷對(duì)服務(wù)協(xié)議性能的影響相對(duì)較小，與其他幾個(gè)協(xié)議相比，HLLS及G?HLLS協(xié)議的低負(fù)載、高位置服務(wù)成功率使得它們具有更優(yōu)的可擴(kuò)展性，綜合性能相對(duì)較好。

表1 位置服務(wù)存儲(chǔ)開銷比較表

5 G?HLLS協(xié)議性能的仿真分析

本小節(jié)基于OPNET仿真，將G?HLLS協(xié)議與HLLS協(xié)議性能進(jìn)行了對(duì)比分析，分析G?HLLS協(xié)議對(duì)HLLS協(xié)議的改進(jìn)情況，從而證明G?HLLS協(xié)議在大規(guī)模群組移動(dòng)MANET中具有更好的可擴(kuò)展性。

首先介紹了仿真參數(shù)及性能評(píng)價(jià)參數(shù)。以公平對(duì)比為原則，所有仿真實(shí)驗(yàn)采用仿真參數(shù)如表2所示。為了分析對(duì)比G?HLLS協(xié)議與HLLS協(xié)議的可擴(kuò)展性，將這兩個(gè)協(xié)議分別運(yùn)行在不同的網(wǎng)絡(luò)規(guī)模下，網(wǎng)絡(luò)規(guī)模從500個(gè)節(jié)點(diǎn)變化到1 600個(gè)節(jié)點(diǎn)，同時(shí)保持網(wǎng)絡(luò)密度不變，即保持平均節(jié)點(diǎn)度為7，則正方形的網(wǎng)絡(luò)區(qū)域邊長(zhǎng)需要根據(jù)網(wǎng)絡(luò)規(guī)模而相應(yīng)變化。在實(shí)驗(yàn)過程中，主要統(tǒng)計(jì)的性能參數(shù)為平均位置請(qǐng)求成功率：即成功接收的位置響應(yīng)包數(shù)目與發(fā)起的位置請(qǐng)求包數(shù)目比值。為了對(duì)比公平性，位置請(qǐng)求不會(huì)重傳，位置服務(wù)成功率均為第一次服務(wù)成功率。

表2 仿真實(shí)驗(yàn)參數(shù)表

圖2顯示了位置服務(wù)成功率隨網(wǎng)絡(luò)規(guī)模變化的情況。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，G?HLLS協(xié)議與HLLS協(xié)議位置位置服務(wù)成功率都呈下降趨勢(shì)，但G?HLLS協(xié)議位置服務(wù)成功率的下降速率明顯比HLLS協(xié)議更緩慢。當(dāng)網(wǎng)絡(luò)規(guī)模小于1 000個(gè)節(jié)點(diǎn)時(shí)，G?HLLS協(xié)議位置服務(wù)成功率比HLLS協(xié)議較低。因?yàn)榫W(wǎng)絡(luò)規(guī)模小于1 000個(gè)節(jié)點(diǎn)時(shí)，初始化負(fù)載對(duì)HLLS協(xié)議的負(fù)面影響不明顯。

圖2 位置服務(wù)成功率隨網(wǎng)絡(luò)規(guī)模變化實(shí)驗(yàn)圖

初始化結(jié)束之后，除利用HELLO包進(jìn)行全局位置更新，G?HLLS協(xié)議還需要額外進(jìn)行簇內(nèi)局部更新，G?HLLS協(xié)議的日常負(fù)載比HLLS協(xié)議稍大；并且G?HLLS的本地位置數(shù)據(jù)庫(kù)信息量明顯小于HLLS協(xié)議，位置信息的散布較HLLS協(xié)議不夠充分，上述多方面原因使得G?HLLS位置服務(wù)成功率在規(guī)模較小的網(wǎng)絡(luò)中低于HLLS協(xié)議。但隨著網(wǎng)絡(luò)規(guī)模增長(zhǎng)大于1 000節(jié)點(diǎn)，HLLS協(xié)議初始化負(fù)載過大的問題暴露，擁塞沖突等原因使得本地位置數(shù)據(jù)庫(kù)建立不完備，即節(jié)點(diǎn)可能丟失一些其他節(jié)點(diǎn)的初始位置信息，并且網(wǎng)絡(luò)范圍較大，這些節(jié)點(diǎn)長(zhǎng)時(shí)間不會(huì)相遇進(jìn)行位置更新，位置信息缺失較多造成位置服務(wù)成功率明顯下降。但G?HLLS協(xié)議本地位置數(shù)據(jù)庫(kù)需要保存的信息較HLLS協(xié)議明顯減少，初始化負(fù)擔(dān)不會(huì)過重，因此位置服務(wù)成功率緩慢下降，持續(xù)保持較高的服務(wù)成功率。

6 結(jié) 語(yǔ)

為了適應(yīng)大規(guī)模MANET網(wǎng)絡(luò)呈現(xiàn)的群組移動(dòng)特性，同時(shí)從降低協(xié)議存儲(chǔ)開銷和初始化負(fù)載的角度對(duì)HLLS協(xié)議進(jìn)行優(yōu)化，本文提出了面向群組移動(dòng)的輕型位置服務(wù)協(xié)議G?HLLS。G?HLLS將HLLS協(xié)議框架與分簇機(jī)制相結(jié)合，照顧群組移動(dòng)性的同時(shí)，將位置服務(wù)協(xié)議分層執(zhí)行。簇首節(jié)點(diǎn)負(fù)責(zé)局部位置更新，將大量簇成員的位置更新限制在較小范圍，有效削減了本地位置數(shù)據(jù)庫(kù)的存儲(chǔ)開銷；在位置請(qǐng)求階段，簇首節(jié)點(diǎn)作為被請(qǐng)求簇成員的代理，執(zhí)行基于歷史信息的雙指針位置追蹤?；贠PNET仿真實(shí)驗(yàn)對(duì)G?HLLS和HLLS進(jìn)行了性能對(duì)比分析，驗(yàn)證了G?HLLS協(xié)議能夠以較低的存儲(chǔ)開銷、控制負(fù)載保持較高的位置服務(wù)成功率，在大規(guī)模群組移動(dòng)網(wǎng)絡(luò)中表現(xiàn)出優(yōu)越性能。

參考文獻(xiàn)

[1] BASAGNI S， CHLAMTAC I， SYROTIUK V R， et al. A distance routing effect algorithm for mobility （DREAM） [C]// Proceedings of The 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking （MOBICOM）. Dallas， USA： ACM Press， 1998： 76?84.

[2] LI J， JANNOTTI J， DE COUTO D S J， et al. A scalable location service for geographic Ad Hoc routing [C]// Proceedings of The 6th Annual ACM International Conference on Mobile Computing and Networking （MOBICOM）. Boston， USA： ACM Press， 2000： 1?11.

[3] STOJMENOVIC I， VUKOJEVIC B. A routing strategy and quorum based location update scheme for Ad Hoc wireless networks [R]. Ottawa： University of Ottawa， 1999.

[4] DAS S M， PUCHA H， HU Y C. On the scalability of rendezvous?based location service for geographic wireless Ad Hoc routing [J]. Elsevier Computer Networks， 2007， 51 （13）： 3693?3714.

[5] 王國(guó)軍，藺英俊，賈維嘉.移動(dòng)自組網(wǎng)中一種面向群組移動(dòng)性的位置服務(wù)協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng)， 2007， 28 （2）： 210?214.

[6] CHENG H， CAO J， CHEN H， et al. GrLS： group?based location service in mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2008， 57 （6）： 3693?3707.

[7] 李皓，李德敏，蔡元正.一種引入閾值的Ad Hoc網(wǎng)絡(luò)分級(jí)轉(zhuǎn)發(fā)指針的位置管理策略[J].傳感器與微系統(tǒng)， 2008， 27 （1）： 33?35.

[8] LENG S， ZHANG L， FU H， et al. A novel location?service protocol based on k?hop clustering for mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2007， 56 （2）： 810?817.

[9] 閻新芳，劉愛琴，楊挺.基于極小獨(dú)立支配集的MANET虛擬骨干網(wǎng)算法[J].電子學(xué)報(bào)，2007，35 （6）： 1134?1138.

[10] YANG Xin?yu， FAN Xiao?jing， YU Wei， et al. HLLS： a history information based light location service for MANETs [J]. Computer Networks， 2012， 56 （2）： 731?744.

[11] MAUVE M， WIDMER A， HARTENSTEIN H. A survey on position?based routing in mobile Ad Hoc networks [J]. IEEE Networks， 2001， 15 （6）： 30?39.

參考文獻(xiàn)

[1] BASAGNI S， CHLAMTAC I， SYROTIUK V R， et al. A distance routing effect algorithm for mobility （DREAM） [C]// Proceedings of The 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking （MOBICOM）. Dallas， USA： ACM Press， 1998： 76?84.

[2] LI J， JANNOTTI J， DE COUTO D S J， et al. A scalable location service for geographic Ad Hoc routing [C]// Proceedings of The 6th Annual ACM International Conference on Mobile Computing and Networking （MOBICOM）. Boston， USA： ACM Press， 2000： 1?11.

[3] STOJMENOVIC I， VUKOJEVIC B. A routing strategy and quorum based location update scheme for Ad Hoc wireless networks [R]. Ottawa： University of Ottawa， 1999.

[4] DAS S M， PUCHA H， HU Y C. On the scalability of rendezvous?based location service for geographic wireless Ad Hoc routing [J]. Elsevier Computer Networks， 2007， 51 （13）： 3693?3714.

[5] 王國(guó)軍，藺英俊，賈維嘉.移動(dòng)自組網(wǎng)中一種面向群組移動(dòng)性的位置服務(wù)協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng)， 2007， 28 （2）： 210?214.

[6] CHENG H， CAO J， CHEN H， et al. GrLS： group?based location service in mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2008， 57 （6）： 3693?3707.

[7] 李皓，李德敏，蔡元正.一種引入閾值的Ad Hoc網(wǎng)絡(luò)分級(jí)轉(zhuǎn)發(fā)指針的位置管理策略[J].傳感器與微系統(tǒng)， 2008， 27 （1）： 33?35.

[8] LENG S， ZHANG L， FU H， et al. A novel location?service protocol based on k?hop clustering for mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2007， 56 （2）： 810?817.

[9] 閻新芳，劉愛琴，楊挺.基于極小獨(dú)立支配集的MANET虛擬骨干網(wǎng)算法[J].電子學(xué)報(bào)，2007，35 （6）： 1134?1138.

[10] YANG Xin?yu， FAN Xiao?jing， YU Wei， et al. HLLS： a history information based light location service for MANETs [J]. Computer Networks， 2012， 56 （2）： 731?744.

[11] MAUVE M， WIDMER A， HARTENSTEIN H. A survey on position?based routing in mobile Ad Hoc networks [J]. IEEE Networks， 2001， 15 （6）： 30?39.

參考文獻(xiàn)

[1] BASAGNI S， CHLAMTAC I， SYROTIUK V R， et al. A distance routing effect algorithm for mobility （DREAM） [C]// Proceedings of The 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking （MOBICOM）. Dallas， USA： ACM Press， 1998： 76?84.

[2] LI J， JANNOTTI J， DE COUTO D S J， et al. A scalable location service for geographic Ad Hoc routing [C]// Proceedings of The 6th Annual ACM International Conference on Mobile Computing and Networking （MOBICOM）. Boston， USA： ACM Press， 2000： 1?11.

[3] STOJMENOVIC I， VUKOJEVIC B. A routing strategy and quorum based location update scheme for Ad Hoc wireless networks [R]. Ottawa： University of Ottawa， 1999.

[4] DAS S M， PUCHA H， HU Y C. On the scalability of rendezvous?based location service for geographic wireless Ad Hoc routing [J]. Elsevier Computer Networks， 2007， 51 （13）： 3693?3714.

[5] 王國(guó)軍，藺英俊，賈維嘉.移動(dòng)自組網(wǎng)中一種面向群組移動(dòng)性的位置服務(wù)協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng)， 2007， 28 （2）： 210?214.

[6] CHENG H， CAO J， CHEN H， et al. GrLS： group?based location service in mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2008， 57 （6）： 3693?3707.

[7] 李皓，李德敏，蔡元正.一種引入閾值的Ad Hoc網(wǎng)絡(luò)分級(jí)轉(zhuǎn)發(fā)指針的位置管理策略[J].傳感器與微系統(tǒng)， 2008， 27 （1）： 33?35.

[8] LENG S， ZHANG L， FU H， et al. A novel location?service protocol based on k?hop clustering for mobile Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2007， 56 （2）： 810?817.

[9] 閻新芳，劉愛琴，楊挺.基于極小獨(dú)立支配集的MANET虛擬骨干網(wǎng)算法[J].電子學(xué)報(bào)，2007，35 （6）： 1134?1138.

[10] YANG Xin?yu， FAN Xiao?jing， YU Wei， et al. HLLS： a history information based light location service for MANETs [J]. Computer Networks， 2012， 56 （2）： 731?744.

[11] MAUVE M， WIDMER A， HARTENSTEIN H. A survey on position?based routing in mobile Ad Hoc networks [J]. IEEE Networks， 2001， 15 （6）： 30?39.