摘 要： 提出了基于網格可預測的位置服務算法(GPLS)。網絡劃分成網格，通過HASH函數對網格進行分組，通信的源節點通過與目的節點所在分組內的位置服務節點通信，獲得目的節點的準確或預測的位置信息。在不增加網絡帶寬的前提下，提高了位置服務效率，節約了網絡的能源和帶寬。
關鍵詞： 位置服務；可預測；網格；MANET
移動Ad Hoc網絡MANET(Mobile Ad hoc Networks) 是一種無基礎設施、自組織和自配置的多跳無線網絡，網絡結構根據節點的移動動態地改變。網絡節點通過協作來傳輸信息，通常節點既作為主機又作為路由器。節點的移動性使得網絡中拓撲變化頻繁且事先無法預測，所以在MANET中發現和維護路由是一個至關重要的問題，一直是研究的熱點和難點問題。
近年來，利用地理位置信息的路由協議在MANET中得到了很大發展。隨著全球定位技術(GPS)的普遍應用，節點可以獲得自身準確的位置信息。利用這些信息進行路由可以降低路由協議的控制開銷、適應動態變化的網絡拓撲以及提高路由協議的可擴展性。然而在基于位置信息的路由協議中，在發送路由包之前，源節點需要知道目的節點的具體位置，主要的問題是基于位置服務的路由協議中需要位置服務來確定目的節點的位置，并返回目的節點的位置信息。
本文從穩定高效的角度對基于位置服務算法進行研究，提出了基于網格可預測的位置服務GPLS(Grid-based Predictive Location Service)算法。該算法把整個網絡劃分成平面網格以避免洪泛操作。通過HASH方法對網格進行分組，節點可以與組內任意網格通信，減少了位置更新和查找的步驟和復雜性，節約了MANET中的能源和帶寬。根據同組網格內任意位置服務節點提供的目的節點的位置，預測出目的節點的位置，提高MANET中位置服務的效率，避免洪泛操作。
1 相關算法
GLS(Grid Location Service)[1]將整個網絡劃分為網格，節點把它的位置信息分布地存放在網絡中的一個或多個位置服務器中。通過位置服務節點可隨時查詢網絡中其他節點的位置，各節點間采用地理路由轉發進行分組傳輸。HNS(Helping Node Selection)[2]根據位置服務器中記錄節點移動的速度和記錄的時間來預判節點的位置，通過其他移動節點把數據包直接攜帶到預判的位置，再把數據包傳輸給目的節點。這樣既提高了數據包的投遞率，又有效地解決了移動自組網絡中節點動態移動和空洞問題。PLS(Predictive Location Service)[3]是一個可預測、自適應的平面位置服務。節點定期向周圍節點發送緩存中的位置信息。節點在整個網絡中洪泛查找目的節點，接收到信息的節點根據緩存中目的節點的位置信息預測出當前目的節點的位置。HBLS(Hashing-Based Location Service)[4]是一個基于HASH集合和平面結構的位置服務算法。在當前服務器消失之前選擇一個新的服務器，以提高服務的可靠性和服務的時間。整個網絡區域劃分為多個不重疊的區域。在伸縮性和可靠性兩個方面權衡HBLS都是一個很好的算法。
2 算法描述
2.1 系統模型和假設
系統考慮n個節點在整個網絡中自由移動，節點通過無線技術彼此進行通信，但是沒有提供固定的網絡基礎設施。假設所有節點功能相當，都有一個統一的傳輸范圍。每個節點配備GPS接收裝置，能確定節點自己的位置，所有在傳輸范圍內的節點都被認為是鄰節點。節點既是源，又轉發數據，因此形成了MANET。每個節點有一個唯一的身份標識節點ID。網絡結構的改變是不可預測的。
2.2 網絡劃分和網格分組
在地理路由中，通常把網絡劃分成多個小網格，每個網格分配一個編號，在每個網格內選擇一個合適的節點作為位置服務節點(黑點為位置服務節點)，整個網絡劃分成25個網格，如圖1所示。
通過網格ID，建立一個HASH函數f(Gi)=Gi%G0，其中，G0為常數，Gi為網格的ID。把f(Gi)相同的分到一組，把一個網格G1內的節點位置信息映射到其他網格G2、G3……Gn，映射到的網格被分到一組(G1、G2、G3……Gn)，位置服務節點定時向同組內其他位置服務節點傳輸本網格內節點的位置信息。同組的網格盡量均勻分布到整個網絡中。如圖1所示，G0=7，f(1)=1%7=1，f(8)=8%7=1，f(15)=15%7=1，f(22)=22%7=1。把網格1，8，15，22分到組1中。依次類推組2、組3、組4、組5、組6、組0。
節點被分配到網格中，每個節點根據節點產生時所在的網格來分配節點ID。根據節點的ID，可以計算節點所在的網格及網格所在的分組，通過組內網格的位置，服務節點獲得節點的位置信息。如果同一個網格內的節點都可以相互直接通信，只需要一個網格內最遠的距離小于或等于節點的通信的傳輸半徑即可，即
×a，如圖2所示。其中，R為節點傳輸半徑，a為網格的大小。
2.3 位置服務器選擇
每個網格內有位置服務節點，選擇離網格中心物理距離最近的節點作為位置服務節點。當位置服務節點離開網格或停止服務以后，網格內的節點需要重新選擇位置服務器。
物理距離計算公式：
式中，(x1，y1)、(x2，y2)為網格中心和節點的坐標。
網格服務器節點保存同組網格區域產生的節點信息。源節點要查找目的節點信息，源節點可通過貪心算法向目的節點所在同一分組內某個特定的網格發送查找信息。
2.4 位置的更新
節點根據最初產生時所在的網格獲得節點ID。節點把自己的位置信息登記到所在網格的位置服務節點中(位置信息包括節點ID、位置、移動的速度、信息更新的時刻)，節點定時Thello向鄰居節點發送hello數據包，報告自己的存在。節點定時Tstart從節點產生時所在分組的網格中選擇離現在物理距離最近的網格，并通過貪心算法向該網格報告自己的位置。位置服務節點定時Tserver通過貪心算法向同組其他網格位置服務節點單播本網格產生的節點的位置信息。
節點位置信息更新規則：
(1)節點定時Thello向周圍鄰居節點發送hello數據包，報告自己的存在。
(2)當節點離開當前網格時，向當前網格位置服務器發送離開請求，位置服務器對節點進行相應的登記。
(3)節點離開節點本身產生時所在網格后，根據移動的距離S0通過貪心算法向產生時所在網格分組最近位置服務節點發送位置更新信息，更新時間的間隔為Tstart。如果移動的距離小于S0，時間間隔到了Tstart，也需要向初始網格服務器發送自己的位置信息。
(4)當節點加入一個新的網格，節點向周圍一跳的節點廣播hello數據包，獲得新的位置服務節點。
(5)位置服務節點定時Tserver向同組內其他網格的服務節點通過貪心算法轉發本網格產生節點的位置信息。
(6)網格服務器記錄路過節點的位置信息，記錄的時間Tnode大于本網格或映射到本網格節點的位置信息的時間Tserver。
位置更新的例子如圖3所示。節點9在網格1產生，所以節點9所在的網格分組(1，8，15，22)，當節點移動到網格4時，網格組內網格的中心距離節點9物理距離最近的網格是網格8，所以節點9向網格8報告自己的位置；當節點移動到網格10時，網格內網格的中心距離節點9物理距離最近的網格是15，所以節點9向網格15報告自己的位置，由于移動的距離和時間間隔都還沒到，所以當節點移動到網格5時，不會向網格組報告自己的位置，但是網格10的位置服務器會保存節點9離開時的位置信息。網格15定時向網格1、網格8、網格15、網格22報告節點9的位置信息。傳輸方式全部采用貪心算法。
2.5 位置的查找
當源節點S需要和目的節點D通信時，源節點S需要查找目的節點D的位置，源節點S通過目的節點D的ID計算出目的節點所在的網格組，根據目的節點D產生時所在的網格組內網格(G1、G2、G3……Gn)距離源節點S物理距離，選擇距離源節點最近的網格Gi，源節點向最近的網格Gi的位置服務節點查找目的節點D的位置信息，并利用預測公式預測目的節點D的位置。預測公式：
根據Sprediction預測目的節點D所在的網格G′，通過貪心算法向目的節點所在的網格G′發送查找信息。如果目的節點D在查找包到達的網格G′內，則位置已經找到；如果不在，但網格G′有目的節點D離開時的記錄，則根據預測函數和離開時的位置信息記錄預測網格G″，通過貪心算法向預測的網格G″發送查找信息；如果網格G′沒有目的節點D的位置信息，則目的節點D未到達網格G′，則要進行折半查找，即向查找獲得的目的節點D的位置與預測的目的節點D的位置的中點所在的網格G?蓯進行查找。中點計算公式：
如果網格G?蓯有目的節點D的位置信息，則可根據這一位置信息預測目的節點D的位置與網格，并通過貪心算法轉發到目的節點D預測的網格；如果沒有，則認為目的節點D未到達網格G?蓯，再進行折半查找；循環執行，直到預測的網格中心與提供目的節點位置信息網格中心小于S0或目的節點D時停止。
查找步驟如下：
(1)當源節點S需要與目的節點D通信時，本地的位置信息表中沒有目的節點D的位置信息。
(2)源節點S首先向本地網格服務器查找是否有目的節點D的位置信息，如果有，則停止查找；如果沒有，則發起目的節點D的位置查找。
(3)源節點S需要查找目的節點D，源節點S根據目的節點D的ID計算出目的節點D所屬的產生時所在的網格G1，利用HASH函數計算同組網格G2、G3……Gn，從G1~Gn中選擇一個離當前源節點物理距離最近的網格Gi，并通過貪心算法向其發送節點查找信息。
(4)根據網格Gi的服務器提供的目的節點D的信息，通過預測函數計算目的節點D所在的網格G′。
(5)通過貪心算法向預測的目的節點所在的網格G′轉發查找信息，如果查找包轉發過程中發現有新的目的節點的位置信息，則進行更新并及時調整轉發策略。
(6)如果目的節點D在路由查找包到達的網格G′內，則位置已經找到；如果不在，但有離開時的記錄，則根據離開時的記錄和預測函數預測目的節點在網格G″內，向預測的網格G″查找，執行第5步；如果G′中沒有目的節點D的信息，則認為目的節點D未到達網格G′，執行第7步。
(7)進行折半查找，向中點網格查找是否有該目的節點D的位置信息，如果有，執行第4步；如果沒有，則說明二種可能：(1)初始服務器的節點D信息失效，這時應該刪除；(2)節點異常離開網絡，停止查找。
目的節點D接收到查找請求包時，則通過貪心算法返回包括目的節點D的位置的信息包到源節點S。源節點S緩存目的節點D的位置信息，這樣位置服務實現了目的節點D的查找。
位置查找的例子如圖4所示。節點123要與節點9通信，首先節點123計算出節點9在網格1產生，計算出網格1，網格8、網格15、網格22在同一分組。網格組內網格的中心距離節點123物理距離最近的是網格8，網格8提供節點9的位置信息是在網格10；向網格10查找節點9，到了網格10以后沒有找到節點9，但有節點9離開時的位置信息，根據位置信息預測出節點9在網格5；向網格5查找節點9，網格5也沒有節點9，但是有節點9的位置信息，再次根據預測函數，預測出節點9在網格3；向網格3查找節點9，在網格3查找到節點9，節點9通過貪心算法向節點123回復自己的位置信息，節點123收到節點9的位置信息，這個時候位置查找成功。這里轉發方式全部采用貪心算法。
3 位置服務算法比較
表1為幾種有關位置服務算法的比較。比較規則如下：(1)局部信息指位置服務有無提供除本節點位置信息以外的其他局部節點的信息，記錄局部信息對于移動網絡的無狀態通信非常有優勢；(2)健壯性指網絡中個別節點失敗影響到節點通信的規模。健壯性越高，影響節點的數量越少；(3)復雜性指位置服務執行操作的復雜程度。復雜性越低，位置服務越簡單，服務效率越高；(4)位置服務器是位置服務選擇的依據(有基于位置、基于節點和網格ID)和位置服務器主要節點位置信息的管理；(5)區域劃分指網絡是否根據區域劃分成小的網絡.區域劃分能減少網絡總體能源和帶寬，對于能源和帶寬有限的MANET非常有意義；(6)更新和查找策略指更新和查找過程中位置服務的策略，有單播、廣播、洪泛、樹形(按照樹行的方式有規則的傳播)。因MANET的能量和帶寬非常有限，應盡量避免洪泛操作，按一定規則方式建立起來的樹形傳播方式，則方便了鏈路的建立。
本文結合MANET中網格位置服務、可預測的位置服務和HASH分組的方法提出了基于網格可預測的位置服務算法，該算法使用網格來劃分網絡，并使用HASH方法對網格進行分組，通過建立預測模型的方法查找目的節點位置，提高目的節點位置查找的準確性。算法中源節點根據目的節點所在的網格分組，通過貪心算法向該分組中的網格發送查找目的節點的信息，根據目的節點的歷史位置信息來預測目的節點的位置。把網格和預測結合在一起，避免了洪泛，減少了網絡的帶寬并提高了包的抵達率，提高了位置服務的性能。因此，在不增加網絡帶寬的前提下提高了位置服務效率，節約了網絡的能源和帶寬。
參考文獻
[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] 于宏毅.無線移動自組織網[M].北京:人民郵電出版社，2005.
[6] 張帆，李德敏，陶莉.基于位置信息的MANET路由協議綜述[J].計算機工程與應用，2005(20):120-123.