移動自組網絡無GPS定位技術可行性研究

王艷 張明 劉衍民 張博揚

摘 要：與其他移動網絡相比，移動自組網絡的自組織性、健壯性、高效性更強，特點鮮明優勢明顯，而移動自組網絡中對節點進行定位的方法多數基于GPS系統和固定或移動基站，限制了移動自組網絡優勢的發揮。文章基于定位系統的空間特性對移動自組網絡定位方法進行研究，重點分析了不依賴GPS系統進行網內節點定位的技術可行性。

關鍵詞：移動自組網絡；定位；無GPS

1 典型定位技術和定位系統

移動自組網絡屬于無線網絡的一種，網內單元由可移動的節點按照一定的協議組織，與其他無線網絡不同的是，移動自組網可以不依賴于中心路由設備，可以以無基站的狀態運行。目前有關終端定位的方法很多，移動自組網中節點的定位方法因為網絡組網形態和無基站運行等因素，是一個涉及交叉學科領域的問題，目前對這一問題的研究也比較多。從分類方法上可從系統使用環境、采用的坐標系、采用的定位算法、采用的無線信號源等方面進行定位。本節從系統采用的定位算法入手，對幾種典型定位方法進行分析比較，對定位方法從算法分析的角度進行分類，為不依賴GPS系統進行網內節點定位的技術可行性分析奠定基礎。

1.1 位置概念

位置，是指某一時刻物體在空間中所處的點。對位置的描述有多種形式，可以是絕對的也可以是相對的，對位置的表征可以是絕對的也可以是相對的。以空間中唯一的位置點為例，西安鐘樓的位置點在某一時刻是唯一固定的，如果采用物理位置對其進行描述，可以采用經緯度加高度的形式，表征為北緯34°15'39.90''，東經108°56'33.32''，海拔586 m；如果采用象征位置對其進行描述，可以表征為南大街以北，北大街以南，東大街以西，西大街以東。當要量化使用位置時，單純的物理位置必須依托于一個數據庫系統進行物理位置向象征位置的轉換后才可以使用。對物理位置的使用必須參考一個坐標系，相對位置和絕對位置的概念就是對應坐標系而來的，一般絕對物理位置對應的是絕對坐標系，常用的有以地心為原點建立的三維坐標系，相對位置對應的是相對坐標系，相對坐標系可以有多種定義方法，可以滿足不同的實際應用需求。

1.2 定位方法

本節從定位方法的算法角度出發，重點介紹三角定位法和對照定位法的實現方法和特點，并對每種定位方法的優缺點進行比較分析。

1.2.1 三角定位法

三角定位算法根據三角形的幾何特征來計算頂點的位置，最初由英國歷史學家湯姆·布魯克斯提出，廣泛應用在全球衛星定位技術中。定位系統所提供的位置信息的精確程度是衡量定位系統的重要指標，目前常用的定位算法橫向對比，三角定位方法的定位精度是比較高的。

下面主要介紹三角定位算法中常用的多邊形定位算法。根據定位過程中是否需要測量節點間的距離，可以將定位算法分為距離有關的定位和距離無關的定位兩種，距離有關的定位方法通過測量相鄰節點間的距離或角度實現對未知位置節點的定位。多邊形定位法屬距離有關的定位算法，是通過計算某一節點到與其不共線的其他3個節點之間的距離來得出該節點的位置。基于測距的原理，多邊形定位法的測距方法可分為3種[1]。

（1）接觸測距法。

接觸測距法顧名思義，是采用物理介質由一個節點出發直接觸碰到相鄰節點，從而直接得到兩節點間的物理距離，這種方法簡單直接，但只適用于距離較小、節點分布簡單的網絡結構，并且測量效率不高。

（2）基于時間及時間差的測距法。

基于時間的測距法首先要知道信號傳播的速度，再測得信號傳播的時間，然后采用三邊或極大似然估計法利用節點間的信號傳播時間計算節點間的距離。在這個過程中，同步時鐘的校準、信號傳播過程中的干擾和測量精度等都會對結果產生影響。為盡量減少這些誤差，還可以采用基于時間差的測距方法，以到達時間差（Time Difference of Arrival ，TDOA）技術為例，發射信號的節點同時發射兩種信號，兩種信號的傳播速度不同，接收節點接收到這兩種信號后，根據接收時間差和信號的傳播速度采用三邊或極大似然估計法計算距離，從而得到發射節點的位置。

（3）基于信號強度及角度的測距法。

信號的傳播距離的平方與信號強度成反比，基于信號強度的測距法就是通過計算信號在傳播過程中的衰減來估計節點之間的距離。基于信號角度的測距法，在接收側布置接收陣列或多個接收節點，通過感知接收到的信號角度不同計算出接收端與發送端之間的角度，再通過三角測量法計算接收端與發送端之間的距離，這個過程一般包括確定鄰節點間夾角、測量信標節點方位角和利用方位信息計算節點間物理距離等三步。

1.2.2 對照定位法

對照定位法也可稱場景定位法，簡單講是將待定位節點發來的信號與已有記錄相對照，選出最接近的結果，再進行一定的修正工作來達到定位的目的。要實現對照定位，首先需要建立基礎數據庫，數據庫中需要包含網絡中所有節點的位置信息等以供參考，這一部分的工作一般在具體實施定位前完成，數據庫可以以離線的方式處理，可以以增量更新的方式實現定期或不定期的刷新。數據庫中節點定位信息的確定方法有很多，可以是人工測量，也可以通過自動掃描實現。當待定位節點發來信號后，將接收到的信號信息與庫中記錄的信息進行比對，得出的結果可能是一個確定的節點，可能是一個范圍內的多個節點，也有可能是一個區域，這取決于數據庫建立時的粒度，粒度越小，精度越高，得到的結果準確性越高。當結果是一個范圍內的多個節點或一個區域時，還需要進行進一步的處理，以得到最佳匹配結果，提高定位精度。對照定位法在室內范圍較小且節點分布復雜度不高的情景下效果較好。

在對照定位法中，最常見的情況是對照返回的結果不是數據庫中已記錄的唯一節點，而是與待定位節點相鄰的節點或一個區域范圍，這樣就需要再優化的機制對結果進行進一步處理，確定待定位節點的位置或區域范圍。再優化機制實現相鄰定位主要有3種方式：感知、計算和監視。感知是一種最直接簡單的方法，可以通過壓力、光線、微電流等多種方式感知待定位節點是否在返回節點附近或返回區域內。感知方式常用在醫學領域，利用微距感知技術實現人體內的定位，保證治療的準確性。計算是一種利用區域覆蓋實現定位的方式，一般認為一個節點的作用范圍不僅局限于節點自身大小而是一個以節點為中心的三維區域內，可以將這樣的節點理解為基站，多個相鄰基站的信號覆蓋范圍是有重疊的，當一個待定位節點同時出現在幾個基站的覆蓋范圍內時，就可以通過計算幾個基站的相交部分實現節點的定位。監視定位方法的實現需要有更加智能的終端系統支持，終端系統可以是刷卡機或計算機終端等，這類系統本身具有身份標示，身份標示可以與安裝使用位置相關聯，從系統發出的數據帶有標示身份信息的內容，定位時通過監視使用信息就可實現對終端的自動定位。

2 移動自組網中的定位技術

從上述分析可以看出，定位方法大部分是依賴于GPS、已知網格結構、已知位置的節點或基站等實現定位的，存在前期工作量大、硬件依賴高和承擔計算任務的基站或節點負載高等問題。為充分發揮自組網絡在擴展性、精確性、移動性和自組織性方面的優勢，我們考慮在移動自組網絡中能否不依賴于GPS和已知網格結構實現節點的快速定位，本節在理論上對這種定位方法的技術可行性進行分析。

2.1 問題的提出

具有高移動性和自組織性網絡可以理解為在一定的空間內，節點以自由或組合的方式分布，為實現無GPS和無已知網格結構定位，可以將問題描述為網絡中節點的定位只依賴于節點間的互聯關系和位置關系，與除節點外的其他定位設備無關，并且節點的自由移動和網絡拓撲的變化對定位能力不產生影響。為實現這種不依賴于外界定位設備的定位，首先需要建立一個對應于網絡結構的相對坐標系，在相對坐標系內標注節點的相對位置，在網內節點相對移動較小時整個網絡對外可呈現為一個整體。當需要對網絡進行整體定位時，可以通過細化網絡結構，選取網內不共面的4個節點作為基準計算絕對坐標，實現相對坐標向絕對坐標的轉換。在本節中，我們的研究對象為網絡內的節點定位問題，下述均為相對坐標系。

相對坐標系確定后，明確節點的分布情況是實現網內節點定位的重要一步。可以采用上一節介紹的三角定位法實現待定位節點與其他節點之間的距離和夾角計算。選取網內不共面的4個節點作為基準節點，通過三角函數計算這4個節點與待定為節點之間的距離和夾角，從而可以得到待定位節點與4個節點間的空間關系和相對位置。節點的分布情況不僅影響相對坐標系的建立，而且對系統定位的準確性影響很大，為提高定位方法的通用性，可選取隨機分布模型進行節點分布。

如何得到節點間距離和夾角值是實現定位的實質問題，節點間的關聯性涉及通信機制和網絡性能等多方面，目前在信號傳輸方面技術相對成熟，實現節點間互通的方法很多，例如可以采用射頻技術、聲波技術、光波技術及多種技術的結合使用。在具體驗證時，可以采用基于時間和時間差的測距方法和基于信號強度和角度的測角方法這兩種方法的結合，兩種方法的結合可以在一定程度上減少某一種方法帶來的誤差，提高精準度，但同時也會增加硬件開銷和計算復雜度，需綜合考量。

2.2 研究假設

本節基于上述問題的提出和描述，提出研究假設并分析其中關鍵技術實現的可行性，為建立物理模型奠定基礎。

目標網絡整體結構是全分布的，其中包含的節點個體間相對獨立，不存依附關系，即節點在網絡中的地位是一致的，沒有作為中心節點為其他節點提供服務的情況，網絡中的每個節點有唯一的標識。節點按隨機分布模型隨機分布在網絡域中，不存在人為設定或按某種規律分布的情況，也不存在網絡域中特定區域對應特定節點的情況；網絡中的通信機制采用無線通信，節點間均可互聯，通信范圍為以發射端為球心的球體，球體內各處通信狀態良好無盲區，網絡中所有節點共享無線信道，通信協議統一，節點間所有傳輸信息均以數據報的形式打包傳輸；網絡內時間同步，可采用基于時間和時間差的測距方法和基于信號強度和角度的測角方法及這兩種方法的結合通過計算節點間的距離和夾角；在相對坐標系建立過程中，為提高坐標系建立的準確度，認為網絡內節點相對位移較小或靜止，保證節點移動距離與網絡通信范圍具有不可比性，網內節點數量不少于4個、節點自身具備數據計算能力是相對坐標系建立的基本需求。

2.3 可行性分析

不依賴于GPS或已知網格對無線自組網絡中節點進行定位必須依靠節點間的通信來實現，節點間的通信狀況直接影響定位能力。上述問題的提出和研究假設中指出，通過計算待定位節點與其他4個與其不共面的4個節點之間的距離和夾角實現定位的首要條件是能夠建立相對坐標系并可以尋找到4個不共面的節點，再通過計算得到結果。在坐標系和4個節點數量滿足條件后，節點間如何實現跳轉通信是計算的前提。

跳轉可分為單跳和多跳兩種方式。如果一個節點發出信號，在其通信范圍內的其他所有節點不需要通過其他節點或設備中繼都可以直接接收到信號，就屬于單跳方式。單跳實現的是本地廣播，只需一次傳播就可以實現信號的范圍內廣播。在單跳方式中，通信范圍內任一節點都可以通過與其不共面的其他4個節點之間的直接通信實現定位。如果一個節點發出信號，其通信范圍內的節點并不是都能直接接收到，有的節點還需要通過其他節點中繼一次或多次才能接受到信號，就屬于多跳方式。多跳方式中，定位可分為兩種，一種與單跳方法原理類似，不能直接通信的節點間通過中繼實現連通并在全網中選取用來計算的4個不共面的節點，再通過中繼的方式將不共面節點的信息向全網廣播，以實現待定位節點的定位。另外一種方法將多跳網絡劃分為多個單跳網絡，每個單跳網絡中的定位方法與單純的單跳網絡相同，待定位節點利用其所在的單跳網絡中的4個不共面的節點來實現定位。第一種方法中，中繼次數和跳數由網絡拓撲和節點分布情況決定，有可能出現中繼次數較多、跳數較多帶來節點計算量和復雜度較大的情況，再加之建立相對坐標的過程中，如果節點間距離和夾角的計算量較大，整個網絡計算量會很大，時間開銷和硬件開銷不好控制，另外，要實現全網絡的廣播通信，任一節點發出的信號其他節點均能直接收到，每個節點中都要存儲相鄰節點的配置信息，重復計算的量也很大。無線自組網絡的帶寬資源非常寶貴，應該盡量避免內部重復計算帶來的消耗。因此，采用第二種方法可以規避過多帶寬的消耗，將網絡看作一個或多個單跳網絡，節點的定位在局部單跳網絡中實現[2]。

具體實現思路是，將待定位節點所在的可建立的最小單跳網絡定義為局部單跳網絡，在其中建立局部坐標系，尋找不共面的4個節點作為基準，利用很小的計算開銷和帶寬實現待定位節點在局部坐標系中的定位，再通過局部坐標系向網絡相對坐標系的轉換實現待定位節點在整個網絡中的定位。在建立坐標系的過程中，節點的實時位置移動對坐標系的建立難易和準確性影響很大，因此，最好選取節點間相對距離和夾角變化較小的情況下建立局部坐標系和相對坐標系，當相對坐標系建立完成，整個網絡就可以作為一個整體，網絡內節點的移動屬坐標系內變化，不影響網絡的整體狀態。通過這種方法，可以盡量減少由建立坐標系和維護相鄰信息帶來的網絡開銷和硬件開銷，同時，在網絡內節點位置發生變化的情況下將變化影響的范圍縮小到其所在的局部單跳網絡中，提高定位效率和精度。

需要注意的是，坐標系的建立依賴于節點的分布情況和節點間的通信情況，所以網絡內部節點數量、相對位置關系、互聯互通能力、呈現的網絡結構、節點移動速度方向等因素都關系到相對坐標系建立、維護和更新，并對節點定位的準確程度、時效性有很大的影響。在上述具體實現思路中，首先需確定待定位節點所在的局部單跳網絡，網絡的劃分和建立取決于能否找到不共面的4個節點，如果找不到這樣的節點，即使網絡內節點再多、范圍再大也無法建立坐標系。另外，如果網內節點相對位移較大或移動速度較快，超出節點自身維護信息的能力和計算能力，勢必會影響定位精度。因此，在選取定位技術之前，需對網絡整體結構、節點分布情況、節點運動情況進行綜合評估，尋找最優、最快、最準確、最適合的定位方法。

上述技術實現思路是以相對靜止自組織網絡為應用場景提出的，即網絡內節點靜止或相對位移很小，小到與網絡覆蓋范圍不可比，那么當網絡內節點自由移動時，定位機制會產生變化，區別主要體現在坐標系維護、節點位置信息更新機制和節點分布情況更新機制等幾個方面。動態數據的更新會帶來通信帶寬和計算量的增大，可能會對定位的時效性和準確性產生影響，如何平衡各因素是后續需要持續研究的問題。

3 結語

本文對典型定位技術和定位系統進行了介紹，針對移動自組網絡中的定位技術背景和相關工作進行了研究，在移動自組網絡面臨的諸多問題中，對節點位置的計算和管理是一個基礎性的問題，如何有效確定對象的位置，還有很多優化工作需要做。本文對一種全新的無GPS、自組織的三維定位系統的可行性進行了分析，為優化工作奠定了理論基礎。

[參考文獻]

[1]彭沛.移動自組網絡中的廣播與路由問題研究[D].長沙：國防科技大學，2001.

[2]PATWARI N.Relative location estimation in wireless sensor network[J].IEEE Transactions on Signal Processing，2003（8）：2137-2148.