王艷 張明 劉衍民 張博揚

摘 要：與其他移動網(wǎng)絡(luò)相比，移動自組網(wǎng)絡(luò)的自組織性、健壯性、高效性更強，特點鮮明優(yōu)勢明顯，而移動自組網(wǎng)絡(luò)中對節(jié)點進行定位的方法多數(shù)基于GPS系統(tǒng)和固定或移動基站，限制了移動自組網(wǎng)絡(luò)優(yōu)勢的發(fā)揮。文章基于定位系統(tǒng)的空間特性對移動自組網(wǎng)絡(luò)定位方法進行研究，重點分析了不依賴GPS系統(tǒng)進行網(wǎng)內(nèi)節(jié)點定位的技術(shù)可行性。

關(guān)鍵詞：移動自組網(wǎng)絡(luò)；定位；無GPS

1 典型定位技術(shù)和定位系統(tǒng)

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

1.1 位置概念

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

1.2 定位方法

本節(jié)從定位方法的算法角度出發(fā)，重點介紹三角定位法和對照定位法的實現(xiàn)方法和特點，并對每種定位方法的優(yōu)缺點進行比較分析。

1.2.1 三角定位法

三角定位算法根據(jù)三角形的幾何特征來計算頂點的位置，最初由英國歷史學家湯姆·布魯克斯提出，廣泛應(yīng)用在全球衛(wèi)星定位技術(shù)中。定位系統(tǒng)所提供的位置信息的精確程度是衡量定位系統(tǒng)的重要指標，目前常用的定位算法橫向?qū)Ρ龋嵌ㄎ环椒ǖ亩ㄎ痪仁潜容^高的。

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

（1）接觸測距法。

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

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

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

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

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

1.2.2 對照定位法

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

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

2 移動自組網(wǎng)中的定位技術(shù)

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

2.1 問題的提出

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

相對坐標系確定后，明確節(jié)點的分布情況是實現(xiàn)網(wǎng)內(nèi)節(jié)點定位的重要一步?？梢圆捎蒙弦还?jié)介紹的三角定位法實現(xiàn)待定位節(jié)點與其他節(jié)點之間的距離和夾角計算。選取網(wǎng)內(nèi)不共面的4個節(jié)點作為基準節(jié)點，通過三角函數(shù)計算這4個節(jié)點與待定為節(jié)點之間的距離和夾角，從而可以得到待定位節(jié)點與4個節(jié)點間的空間關(guān)系和相對位置。節(jié)點的分布情況不僅影響相對坐標系的建立，而且對系統(tǒng)定位的準確性影響很大，為提高定位方法的通用性，可選取隨機分布模型進行節(jié)點分布。

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

2.2 研究假設(shè)

本節(jié)基于上述問題的提出和描述，提出研究假設(shè)并分析其中關(guān)鍵技術(shù)實現(xiàn)的可行性，為建立物理模型奠定基礎(chǔ)。

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

2.3 可行性分析

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

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

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

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

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

3 結(jié)語

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

[參考文獻]

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

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