1、l節(jié)點定位技術(shù)概述l節(jié)點定位技術(shù)研究現(xiàn)狀與發(fā)展l節(jié)點定位技術(shù)關(guān)鍵問題l基于測距的定位技術(shù)l無需測距的定位技術(shù)l協(xié)作定位技術(shù)無線節(jié)點定位技術(shù)無線傳感器網(wǎng)絡(luò)節(jié)點定位無線傳感器網(wǎng)絡(luò)節(jié)點定位：依靠網(wǎng)絡(luò)中少量的位置已知的節(jié)點，通過鄰居節(jié)點間有限的通信和某種定位機(jī)制確定網(wǎng)絡(luò)中所有未知節(jié)點的位置。節(jié)點定位在實際應(yīng)用中包含兩種含義： 自定位確定節(jié)點自身在系統(tǒng)中的位置 目標(biāo)定位確定目標(biāo)節(jié)點在系統(tǒng)中的位置l節(jié)點定位技術(shù)概述信標(biāo)節(jié)點信標(biāo)節(jié)點：已知自身位置信息的節(jié)點，可通過GPS定位設(shè)備或手工配置、確定部署等方式預(yù)先獲取位置信息，為其他節(jié)點提供參考坐標(biāo)。未知節(jié)點未知節(jié)點：信標(biāo)節(jié)點以外的節(jié)點統(tǒng)稱為未知節(jié)點，也有文獻(xiàn)稱為

2、盲節(jié)點。鄰居節(jié)點鄰居節(jié)點：一個節(jié)點通信距離范圍內(nèi)的所有節(jié)點的集合。跳數(shù)跳數(shù)：兩個節(jié)點之間跳段的總數(shù)。跳距跳距：兩個節(jié)點之間各跳段的距離之和。節(jié)點連接度節(jié)點連接度：節(jié)點可以探測發(fā)現(xiàn)到的鄰居節(jié)點個數(shù)。網(wǎng)絡(luò)連接度網(wǎng)絡(luò)連接度：所有節(jié)點的鄰居個數(shù)取平均值，可反映傳感器配置的密集程度l節(jié)點定位技術(shù)概述一些概念傳感器網(wǎng)絡(luò)的定位算法通常需要具備以下特點： 自組織性自組織性：傳感器網(wǎng)絡(luò)的節(jié)點隨機(jī)部署，不依賴于全局基礎(chǔ)設(shè)施協(xié)助定位； 健壯性健壯性：傳感器節(jié)點的硬件配置低，能量有限，可靠性較差，定位算法必須能夠容忍節(jié)點失效和測距誤差； 節(jié)能性節(jié)能性：盡可能地減少算法中計算的算法復(fù)雜度，減少節(jié)點間的通信開銷，以盡量延

3、長網(wǎng)絡(luò)的生存周期； 分布式分布式：無線傳感器網(wǎng)絡(luò)通常是大規(guī)模部署網(wǎng)絡(luò)，節(jié)點數(shù)目多，定位任務(wù)將不會是單個節(jié)點所能承擔(dān)的，這就需要定位算法具有一定的分布式，把任務(wù)分派到各個節(jié)點； 可擴(kuò)展性可擴(kuò)展性：無線傳感器網(wǎng)絡(luò)中的節(jié)點數(shù)目可能是成千上萬甚至更多，為了滿足對不同規(guī)模的網(wǎng)絡(luò)的適用性，定位算法必須具有較強(qiáng)的可擴(kuò)展性。l節(jié)點定位技術(shù)概述要求要求作為一種全新的技術(shù)，無線傳感器網(wǎng)絡(luò)具有許多挑戰(zhàn)性的研究課題，而定位就是其中之一，定位也是大多數(shù)應(yīng)用的基礎(chǔ)和前提傳感器節(jié)點的微型化和有限的電池供電能力使其在節(jié)點硬件的選擇上受到很大的限制，低功耗是其最主要的設(shè)計目標(biāo)。必須針對密集性，節(jié)點的計算、存儲和通信等能力都有限

4、的特定場合設(shè)計有效的低功耗低功耗定位算法近十年來，無線傳感器網(wǎng)絡(luò)自身定位問題研究有了許多新穎的解決方案和思想，但是每種系統(tǒng)和算法都是用來解決不同的問題或支持不同的應(yīng)用的，它們用于定位的物理現(xiàn)象、傳感器設(shè)備的組成、能量需求、基礎(chǔ)設(shè)施和時空的復(fù)雜性等許多方面有所不同。對現(xiàn)有的WSN定位研究成果研究比較發(fā)現(xiàn)，沒有一種定位方案能在有效減少通信開銷、降低功耗、節(jié)省網(wǎng)絡(luò)帶寬的同時獲得較高的定位精度。而且大部分停留在仿真和實驗階段。因此，該領(lǐng)域還有待更多的人提出更好的方法，以求更好地解決定位問題，使得無線傳感器網(wǎng)絡(luò)能夠真正在實際生活中得到廣泛的應(yīng)用。l節(jié)點定位技術(shù)的研究現(xiàn)狀和發(fā)展目前，在節(jié)點定位應(yīng)用中，由于

5、受傳感器節(jié)點能量有限、可靠性差、網(wǎng)絡(luò)規(guī)模大且節(jié)點隨機(jī)布放、無線模塊的通信距離有限等影響，對定位算法和定位技術(shù)提出了很高的要求。一般來說我們從定位區(qū)域與精確度、實時性和能耗三個方面來衡量節(jié)點定位技術(shù)的好壞。1定位區(qū)域與精確度定位區(qū)域與精確度定位區(qū)域與精確度是傳統(tǒng)定位方法和無線傳感器網(wǎng)絡(luò)定位都具有的衡量指標(biāo)，而且定位區(qū)域和精度一般都是互補存在的，定位區(qū)域越大，意味著精度越小。2實時性實時性實時性是定位技術(shù)的另外一個關(guān)鍵指標(biāo)，實時性與位置信息的更新頻率密切相關(guān)，位置信息更新頻率越高，實時性越強(qiáng)3能耗能耗能耗是無線傳感器網(wǎng)絡(luò)獨有的一個衡量指標(biāo)。在無線傳感器網(wǎng)絡(luò)中，節(jié)點的電能靠電池來供應(yīng)，電池是不可替換

6、的，因此節(jié)省能量就成了無線傳感器網(wǎng)絡(luò)中一個重要的問題。另外，還有一些小的方面來衡量無線傳感器網(wǎng)絡(luò)定位技術(shù)的好壞，如定位技術(shù)的擴(kuò)展性、魯棒性和節(jié)點帶寬的占用等。l節(jié)點定位技術(shù)的研究現(xiàn)狀和發(fā)展利用信標(biāo)節(jié)點的位置，通過測量和估計信標(biāo)節(jié)點與目標(biāo)節(jié)點的距離，我們就能夠利用它們之間的關(guān)系很容易地算出目標(biāo)節(jié)點的位置。基于測距的定位技術(shù)涉及幾何中的圖形問題，已知節(jié)點的位置，求另外幾個節(jié)點的位置，比較常用的方法有：u三邊定位法u角度定位法角度定位需要另外測量接收信號夾角，測量出夾角后使用數(shù)學(xué)幾何條件，確定節(jié)點的位置。因為測量的信號夾角不可能很精確，所以AOA的精度不理想。l節(jié)點定位技術(shù)基于測距的定位1基本思想基

7、本思想三邊定位法如圖所示，已知A、B、C三個節(jié)點的坐標(biāo)分別為（x1，y1）、（x2，y2）、（x3，y3）。測得它們到未知節(jié)點D的距離分別為d1、d2、d3。假設(shè)節(jié)點D的坐標(biāo)為（x，y）。以A、B、C三點為圓心，d1、d2、d3為半徑做圓，三圓的焦點即為節(jié)點D的坐標(biāo)。l基于測距的定位技術(shù)三邊定位法那么，我們可以列出以下公式：將第一個方程和第二個方程同時減去第三個方程，得到結(jié)果222222131313131322222223232323232()2()2()2()xx xyy yxxyyddxx xyy yxxyydd將其寫成線性方程的形式，AX=B，其中22222213131313132222

8、2223232323232()2()2()2()xxyyxxyyddxxxyyyxxyydd ABXl基于測距的定位技術(shù)三邊定位法由此可以得出節(jié)點D的坐標(biāo)為1222222131313131322222223232323232()2()2()2()xxyyxxyyddxyxxyyxxyydd l基于測距的定位技術(shù)三邊定位法三邊定位技術(shù)的計算方法比較簡單，在已知兩點之間距離的情況下，采用單純的數(shù)學(xué)公式就可以計算出來，節(jié)點之間距離的測量才是三邊定位技術(shù)的最難點，一般來說，有三種算法可以測量兩個節(jié)點之間的距離：u根據(jù)接收信號的強(qiáng)度來計算距離；u根據(jù)信號傳播時間或者時間差來計算距離；u根據(jù)接收信號相位差

9、定位。2主要技術(shù)主要技術(shù)1）根據(jù)接收信號強(qiáng)度定位，信號衰減模型如下式：式中，P(d)、P(d0)分別表示在距離基站d、d0處的信號強(qiáng)度，P(d)是接收節(jié)點實際測得的信號強(qiáng)度RSSI，P(d0)一般可以距天線d0米處的路徑衰減來代替。l基于測距的定位技術(shù)三邊定位法2）根據(jù)信號傳播時間測距（TOA）該技術(shù)是采用信號到達(dá)時間來測量距離的，是一種基于電波傳輸時間的定位技術(shù)。己知信號傳播速度，通過測量信號從發(fā)射機(jī)傳播到多個接收機(jī)所消耗的傳播時間來確定移動用戶的位置TOA測距的基本思想是測量移動臺發(fā)射信號的到達(dá)時間，并且在發(fā)射信號中要包含發(fā)射時間標(biāo)記以便接收基站確定發(fā)射信號所傳播的距離，該方法要求移動臺和

10、基站的時間精確同步為了測量移動臺的發(fā)射信號的到達(dá)時間，需要在每個基站處設(shè)置一個位置測量單元，為了避免定位點的模糊性，該方法至少需要三個位置測量單元或基站參與測量l基于測距的定位技術(shù)三邊定位法如圖所示，有A、B、C三個基站，因為節(jié)點間的距離測量都是一樣的，這里我們就假定先測量基站A到目的節(jié)點的距離。假設(shè)基站A到目的節(jié)點D的距離為d，聲波傳播速度為v，在T1時刻基站A發(fā)射機(jī)發(fā)射一個聲波信號給目的節(jié)點D，D節(jié)點在T2時刻接收到該聲波信號，經(jīng)過短暫的處理之后，在T3時刻目的節(jié)點D回送一個聲波測距信號給A節(jié)點，在T4時刻A節(jié)點接收到該信號。由此可以得出聲波信號在介質(zhì)中傳播的時間為：( 21)( 43)t

11、TTTTl基于測距的定位技術(shù)三邊定位法在這段時間內(nèi)，聲波傳播的距離為2d，我們就可以得到值得注意的是，這里的T1和T4時刻是由節(jié)點A測得的，T2和T3時刻是由目的節(jié)點D測得的，由于時鐘漂移、定位誤差等的存在，兩者的時間會有一定的時間差，但是由于無線采用雙向通信的方式，兩者的時間差相互抵消，對結(jié)果沒有太大影響l基于測距的定位技術(shù)三邊定位法3）根據(jù)到達(dá)時間差測距（Time Difference Of Arrival，TDOA）在基于到達(dá)時間差TDOA的定位機(jī)制中，發(fā)射節(jié)點同時發(fā)射兩種不同傳播速度的無線信號，接收節(jié)點根據(jù)兩種信號到達(dá)的時間差以及已知這兩種信號的傳播速度，計算兩個節(jié)點之聞的距離，再通過

12、已有基本的定位算法計算出節(jié)點的位置。l基于測距的定位技術(shù)三邊定位法如圖所示，發(fā)射節(jié)點在時刻T0同時發(fā)射無線射頻信號和超聲波信號，接收節(jié)點記錄兩種信號到達(dá)的時間T1和T2，己知無線射頻信號和超聲波的傳播速度分別為c1和c2，那么我們可以知道射頻信號和超聲波信號傳播的時間為：TDOA有一些固有的缺陷需要考慮。首先利用TDOA進(jìn)行定位要求傳感節(jié)點上必須附加特殊的硬件（聲波或者超聲波的收發(fā)器等），這會增加傳感節(jié)點的成本；其次，聲波或者超聲波在空氣中的傳輸特性和一般的無線電波并不一樣，空氣的溫度、濕度或者風(fēng)速都會對聲波的傳輸速度產(chǎn)生很大的影響，這就使得距離的估計可能出現(xiàn)較大偏差；最后，TDOA測速的一個

13、很大的假設(shè)是發(fā)送節(jié)點和接收節(jié)點之間是沒有障礙物阻隔的，在有障礙物的情況下會出現(xiàn)聲波的反射、折射和衍射，此時得到的實際傳輸時間將變大，在這種傳輸時間下估算出來的距離也將出現(xiàn)較大的誤差。2120102121() ()ddttTTTTTTccl基于測距的定位技術(shù)三邊定位法可以得出 即：接收信號相位（接收信號相位（PDOA）通過測相位差，求出信號往返的傳播時間，計算出往返距離 其中，fc是信號頻率，是信號的波長，是發(fā)送信號和反射信號的相位差。由上式可知d的范圍是0, 。不同的距離如果相差倍，則測量獲得的相位相同。222ccfcfcdl基于測距的定位技術(shù)三邊定位法常用的角度定位方法有：已知兩個頂點和夾角

14、的射線確定一點，以及已知三點和三個夾角確定一點。1已知兩個頂點和夾角的射線確定一點如圖所示，測得參考點A(x1,y2)和B(x2,y2)收到的信號夾角分別是和，根據(jù)可以計算出待測節(jié)點N的位置坐標(biāo)(x,y)。這是一種參考節(jié)點A和B自身在坐標(biāo)系已經(jīng)矯正的情形，如果參考點A和B方向沒有校正，需要在計算時補償方向偏差。l基于測距的定位技術(shù)三角定位法22112211(tan) (tan)tantan(cot) (cot)cotcotyxyxxxyxyy如圖所示，在測量出角、角和角后，可以使用三角定位的方法計算出N點的位置(x,y)。對于參考點A(x1,y1)、B(x2,y2)和夾角，根據(jù)圓的內(nèi)接四邊形對

15、角互補和弦所對的圓周角等于它所對的圓心角的性質(zhì)，得到弦AB所對應(yīng)的圓心角=22。可以由A、B和N確定一個內(nèi)接圓O的圓心C1（xc1,yc1）和半徑rc1，同理由A、C和N三點就可以確定O2(xc2,yc2,rc2)，由B、C和N三點就可以確定O3(xc3,yc3,rc3)。根據(jù)圓O1、O2、O3，再根據(jù)如下方程組，就可以確定點D(xD,yD)的坐標(biāo)。222221111122222222233333()()()()()()cccccccccxxyyrxxyyrxxyyrl基于測距的定位技術(shù)三角定位法在無線傳感器網(wǎng)絡(luò)中，基于測距的定位技術(shù)往往具有很大的優(yōu)勢，算法比較簡單，實現(xiàn)容易，研究人員一般從幾

16、個方面來評判這些定位技術(shù)的優(yōu)略。（1）定位精度，即測距誤差，為測得的距離與實際距離的差值，一般來說采用超聲波的TDOA協(xié)議最小，而采用功率衰減來判別距離的RSSI測距誤差最大。（2）覆蓋范圍。GPS是全球定位系統(tǒng)，一次覆蓋范圍最好，其次是采用功率衰減的RSSI。而TOA和TDOA定位技術(shù)采用超聲波短波，傳播距離最短，因此覆蓋范圍最小。（3）抗干擾能力。當(dāng)有干擾如電磁干擾，多徑干擾等存在時，節(jié)點是否能夠正常穩(wěn)定工作成為測距定位技術(shù)性能的一個重要指標(biāo)。（4）實現(xiàn)成本。l測距定位技術(shù)比較1基于連通性的定位基于連通性的定位連通性（Connectivity）是指兩個節(jié)點是否連通?；谶B通性的定位基于連通

17、性的定位可以根據(jù)一個節(jié)點能否成功解調(diào)其他節(jié)點傳來的數(shù)據(jù)包作為依據(jù)。如果節(jié)點i和節(jié)點j連通，則表示節(jié)點i能夠通過感知、通信等途徑，確定節(jié)點j在自己周圍的一定范圍內(nèi)，但不知道具體的距離和方向。確切地說，節(jié)點i和節(jié)點j之間的連通性測量Qij，可以依據(jù)接收信號強(qiáng)度表示成0或1的二元變量模型，即： 式中，Pij是節(jié)點i收到的從節(jié)點j發(fā)出的信號的強(qiáng)度，單位是dBm；Pi是數(shù)據(jù)包剛好能被解調(diào)所需的最小接收信號閾值強(qiáng)度。l無需測距的定位技術(shù)基于連通性2基于跳數(shù)的定位基于跳數(shù)的定位在無線傳感器網(wǎng)絡(luò)中，節(jié)點間最基本的通信方式是洪泛，所以很多節(jié)點定位機(jī)制都是采用兩個節(jié)點之間的跳數(shù)（Hop）來估計節(jié)點之間的距離的。跳

18、數(shù)原理就是對信標(biāo)節(jié)點信息洪泛的過程進(jìn)行跳數(shù)統(tǒng)計，通過統(tǒng)計未知節(jié)點與信標(biāo)節(jié)點之間的跳數(shù)，然后根據(jù)信標(biāo)節(jié)點之間的距離和跳數(shù)估算出全網(wǎng)每一跳的平均距離，二者相乘，即可得到兩個節(jié)點之間的距離。l無需測距的定位技術(shù)基于跳數(shù)質(zhì)心定位算法質(zhì)心定位算法的核心思想是：全網(wǎng)約定一段時間t為定位時間。時間t為(1)tST 式中，T為發(fā)信號的時間間隔；S為t時間內(nèi)要發(fā)送的消息個數(shù)；為小于1、大于0的常數(shù)。在這段時間t內(nèi)，信標(biāo)節(jié)點每隔時間T向鄰居節(jié)點廣播一個信標(biāo)信號，信號中包含自身的位置信息。未知節(jié)點記錄從每個發(fā)來信號的信標(biāo)節(jié)點接收到的信標(biāo)信號數(shù)量。i時間結(jié)束后，未知節(jié)點計算與各個信標(biāo)節(jié)點之間的通信成功率指標(biāo)CMi，即

19、： l無需測距的定位技術(shù)質(zhì)心定位算法假設(shè)這些坐標(biāo)分別為（x1，y1）、（x2，y2）、（xk，yk），則未知節(jié)點的坐標(biāo)（xest，yest）可用質(zhì)心公式計算為：11estest(,),kkxxyyxykkl無需測距的定位技術(shù)質(zhì)心定位算法APIT定位算法的理論基礎(chǔ)是最佳三角形內(nèi)點測試法PIT。PIT理論為判斷某一點M是否在三角形ABC內(nèi)，假如存在一個方向，沿著這個方向M點會同時遠(yuǎn)離或接近三角形ABC的三個頂點A、B、C，那么點M位于三角形ABC外；否則，點M位于三角形ABC內(nèi)。l無需測距的定位技術(shù)APTI定位算法在圖（a）中,位置未知節(jié)點M通過與鄰居節(jié)點1交換信息，得知自身如果運動至節(jié)點1，將遠(yuǎn)

20、離信標(biāo)節(jié)點B和C，但會接近信標(biāo)節(jié)點4，與鄰居節(jié)點2、3、4的通信和判斷過程類似，最終確定自身位于三角形ABC中；而在圖（b）中，當(dāng)節(jié)點4可知自身運動至鄰居節(jié)點2處，將同時遠(yuǎn)離信標(biāo)節(jié)點A、B、C，故判斷自身不在ABC中。l無需測距的定位技術(shù)APTI定位算法APIT定位的具體步驟如下：（1）收集信息：未知節(jié)點收集鄰近信標(biāo)節(jié)點的信息，如位置、標(biāo)識號、接收到的信號強(qiáng)度等，鄰居節(jié)點之間交換各自接收到的信標(biāo)節(jié)點的信息。（2）APIT測試：測試未知節(jié)點是否在不同的信標(biāo)節(jié)點組合的三角形內(nèi)部。（3）計算重疊區(qū)域：統(tǒng)計包含未知節(jié)點的三角形，計算所有三角形的重疊區(qū)域。（4）計算未知節(jié)點位置：計算重疊區(qū)域的質(zhì)心位置，

21、作為未知節(jié)點的位置。l無需測距的定位技術(shù)APTI定位算法DV-Hop算法算法的基本思想是將未知節(jié)點到信標(biāo)節(jié)點之間的距離用網(wǎng)絡(luò)中節(jié)點的平均每跳距離和兩節(jié)點之間跳數(shù)的乘積來表示，然后再使用三邊測量法或極大似然估計法來獲得未知節(jié)點的位置信息。DV-Hop算法的定位過程分為以下三個階段：1）計算未知節(jié)點與每個信標(biāo)節(jié)點的最小跳數(shù)首先使用典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點獲得與信標(biāo)節(jié)點之間的跳數(shù)。在算法開始的時候，每個信標(biāo)節(jié)點都發(fā)出一個包括自己位置信息、地址和跳數(shù)值為0的位置信息包，它們周圍所有跳數(shù)為1的鄰居都收到這樣的信息，將信標(biāo)節(jié)點的位置信息和跳數(shù)記錄下來，并將收到信息包的跳數(shù)值加1，再向自己的

22、鄰居節(jié)點廣播。這個過程一直持續(xù)下去，直到網(wǎng)絡(luò)中每個節(jié)點都獲得每個信標(biāo)節(jié)點的位置信息和相應(yīng)的跳數(shù)值為止。l無需測距的定位技術(shù)DV-Hop定位算法2）計算未知節(jié)點與信標(biāo)節(jié)點的平均每跳距離在第二階段，每個信標(biāo)節(jié)點根據(jù)第一階段獲得的其他信標(biāo)節(jié)點位置和相隔跳數(shù)之后，根據(jù)下式計算網(wǎng)絡(luò)平均每跳距離HopSize。式中，（xi，xj）、（yi，yj）是信標(biāo)節(jié)點i 和j 的坐標(biāo)，hji是信標(biāo)節(jié)點i和j（ij）之間的跳段數(shù)。在實驗中，我們發(fā)現(xiàn)，當(dāng)總跳數(shù)大于一定的值之后，每個節(jié)點所計算的平均每跳距離基本一樣。l無需測距的定位技術(shù)DV-Hop定位算法3）利用三邊測量法計算自身位置在未知節(jié)點獲得與3個或3個以上信標(biāo)節(jié)點

23、的距離后，執(zhí)行三邊測量定位。該算法只需要較少的信標(biāo)節(jié)點，計算和通信開銷適中，不需要節(jié)點具備測距能力，是一個可擴(kuò)展的算法，但是該算法對信標(biāo)節(jié)點的密度要求較高，對于各向同性的密集網(wǎng)絡(luò)，才可以得到合理的平均每跳距離，從而能夠達(dá)到適當(dāng)?shù)亩ㄎ痪?。l無需測距的定位技術(shù)DV-Hop定位算法將節(jié)點間點到點的通信連接視為節(jié)點位置的幾何約束，把整個網(wǎng)絡(luò)模型化為一個凸集，從而將節(jié)點定位問題轉(zhuǎn)化為凸約束優(yōu)化問題，然后使用線性矩陣不等式、半判定規(guī)劃或線性規(guī)劃方法得到一個全局優(yōu)化的解決方案，確定節(jié)點位置。同時也給出了一種計算未知節(jié)點有可能存在的矩形空間的方法。l無需測距的定位技術(shù)凸優(yōu)化方法第八章 無線傳感器網(wǎng)絡(luò)節(jié)點定位

24、技術(shù)無線傳感器網(wǎng)絡(luò)自身定位算法的性能對其可用性有直接的影響，如何評價定位算法是一個需要研究的問題?？蓮氖欠裥枰艠?biāo)節(jié)點、信標(biāo)節(jié)點布置方式、計算模式、定位原理和節(jié)點外加設(shè)備等角度對上述無須測距節(jié)點定位技術(shù)進(jìn)行了分析和比較，如下表所示。l無需測距的定位技術(shù)分析比較剛性體理論概述剛性體理論概述剛性，即在不考慮物質(zhì)特性的理想條件下任何兩個連接點之間的歐氏距離不隨其運動狀態(tài)改變的特性。普通剛性理論是一種定義在光滑軌道上的運動特性。當(dāng)圖沿著光滑軌道運動時，任意兩個節(jié)點qi(t)和qj(t)間的歐氏距離不隨時間函數(shù)變化，則qi(t)和qj(t)具有普通剛性特性。用數(shù)學(xué)描述，即當(dāng)幾何圖沿著軌道q(0, )做剛性運動時，則任意時刻的節(jié)點集qi(t)和qj(t)是全等的?？捎脭?shù)學(xué)公式表示為( )0q Rq式中， R(q)是一個mn型的矩陣，稱為剛體矩陣。l協(xié)作定位技術(shù)定理1：在二維的平面空間中，圖形G=(v,L)擁有n個頂點，如果L（L為圖形的邊集）存在一個有2n3條邊的子集E，且對任意一個非空邊集E中有n個頂點且E中元素數(shù)量不超過2n3，那么圖形G=(V,L)在二維平面空間中具有普通剛性。定理2：在一個二維平面空間中圖G內(nèi)包含n4個定點，如果圖G中某個點具有3-連接（3-Connected）結(jié)構(gòu)且該圖形