1、第7章 無線傳感器網絡(wnglu)的節(jié)點定位技術 7.1 節(jié)點定位技術簡介(jin ji)7.2 無線傳感器網絡自身定位技術7.3 無線傳感器網絡跟蹤技術7.4 無線傳感器網絡時間同步技術7.5 無線傳感器網絡測距技術共九十八頁7.1 節(jié)點定位技術簡介7.1.1 節(jié)點定位的幾個基本概念1節(jié)點定位概述定位就是確定位置。確定位置在實際應用中有兩種意義，一種是確定自己(zj)在系統(tǒng)中的位置，另一種是確定目標在系統(tǒng)中的位置。在傳感器網絡中，節(jié)點定位技術就是無線傳感器網絡節(jié)點通過某種方法在基于已知節(jié)點位置信息的情況下來計算和確定未知節(jié)點或者目標節(jié)點的坐標位置的技術。在應用中，只有知道節(jié)點的位置信息才能

2、實現對目標信息的監(jiān)測，這就需要監(jiān)測到該事件的多個傳感器節(jié)點之間的相互協作。共九十八頁在傳感器網絡應用中，節(jié)點一般采取隨機放置的方法。由于數目很多，不可能每個節(jié)點都要定位和確定位置信息。因此，通常(tngchng)僅對其中5%10%的節(jié)點使用定位系統(tǒng)，一般的方法是采用GPS定位設備來獲得自身的精確位置。目前研究的主要方向包括兩個：一個是利用錨節(jié)點基于定位算法來確認其他節(jié)點的位置，這些錨節(jié)點事先借助外部設備已經確定好了自身位置；另一個是事先設置好錨節(jié)點建立坐標系，其他節(jié)點隨機擺放，然后再利用定位算法來計算未知節(jié)點的坐標位置。共九十八頁傳統(tǒng)的獲得節(jié)點位置的方法是使用全球定位系統(tǒng)(GPS)來實現(sh

3、xin)。但是GPS全球定位系統(tǒng)受價格高、體積大、功耗大等因素制約，所以大規(guī)模應用十分困難。目前主要的研究工作是利用已知位置的錨節(jié)點通過定位算法來估算和確認其他未知節(jié)點的位置信息。2定位算法的評價標準無線傳感器網絡定位技術的性能十分重要，一般通過以下幾個標準來評定定位技術的性能。共九十八頁(1) 定位精度。無線傳感器網絡定位技術首先要考慮到定位精度。比如，在基于距離定位的算法中，可以用定位坐標與實際坐標的距離來對比；在非距離定位的算法中，常用誤差值和節(jié)點通信半徑的比例來表示。(2) 代價。定位算法需要很多代價，包括時間代價(包括一個系統(tǒng)的安裝時間、配置時間和定位所需時間)、資金(zjn)代價(

4、包括實現定位系統(tǒng)的基礎設施和節(jié)點設備的總費用)和硬件代價(包括一個定位系統(tǒng)或算法所需的基礎設施和網絡節(jié)點的數量、硬件尺寸等)。共九十八頁(3) 規(guī)模。不同的定位算法適用的應用場合范圍和規(guī)模也不同。大規(guī)模的定位算法可在大范圍的場合應用，比如森林或者城市內；中等規(guī)模算法可在大型商場、小區(qū)和學校內進行定位應用；小規(guī)模的定位算法只能在一棟樓內或者一個房間內實現定位應用。(4) 定位覆蓋率。在定位系統(tǒng)中，能夠實現定位的未知節(jié)點的數目占整個未知節(jié)點數目的比例稱為定位覆蓋率。(5) 錨節(jié)點密度。錨節(jié)點通常需要人工部署，這些節(jié)點常常會受到網絡部署環(huán)境的制約，會嚴重影響無線傳感器網絡應用的可擴展性。所以錨節(jié)點的

5、密度會嚴重影響整個傳感器網絡的成本。因此，錨節(jié)點密度也是評價定位系統(tǒng)和算法性能的重要(zhngyo)指標之一。共九十八頁(6) 網絡連通度。在定位系統(tǒng)中，網絡的連通性會直接影響到定位算法的精度。比如，距離向量路由算法對網絡連通度要求就很高。節(jié)點的密度是影響網絡連通度的主要原因，節(jié)點密度提高了，傳感器網絡的成本也隨之升高了。(7) 魯棒性。在理想的實驗室環(huán)境內，大部分定位算法誤差性比較小。但是在實際應用場合，有許多干擾因素影響測量結果。比如，障礙物引起的非視距(NLOS)、大氣中存在嚴重的多徑傳播、部分傳感器節(jié)點電能耗盡、節(jié)點間通信阻塞(zs)等問題容易造成定位誤差突發(fā)性增大，甚至造成整個定位系

6、統(tǒng)的癱瘓。因此，傳感器網絡定位算法必須具有很強的魯棒性，以減小各種誤差的影響，提高定位精度和可靠性。共九十八頁3WSN的定位技術應用除用來提供監(jiān)測區(qū)域內節(jié)點的位置信息外，無線傳感器網絡定位技術還具有下列應用：(1) 定向信息查詢。如果監(jiān)測需要，可以對某一個監(jiān)測區(qū)內的監(jiān)測對象進行定位，需要管理節(jié)點發(fā)送任務給這個區(qū)域內的傳感器節(jié)點。(2) 協助路由。通過(tnggu)節(jié)點的位置信息路由算法可以進行路由的選擇。(3) 目標跟蹤。對目標的行動路線進行實時監(jiān)測，并且預測目標的前進軌跡。(4) 網絡管理。使用定位技術可以實現網絡管理，利用這些節(jié)點傳送過來的節(jié)點位置信息來構成網絡的拓撲結構，可以對整個網絡的

7、覆蓋情況實時觀察，并且也可以對節(jié)點分布情況進行管理。共九十八頁7.1.2 節(jié)點定位技術基本原理在傳感器節(jié)點定位過程中，未知節(jié)點在獲得對于鄰近信標節(jié)點的距離或鄰近的信標節(jié)點與未知節(jié)點之間的相對角度后，通常使用三邊測量法、三角測量法或極大(j d)似然估計法來計算自己的位置，最后對得到的位置值進行修正，提高定位精度，減少誤差。1三邊測量法三邊測量法(Trilateration)如圖7.1所示，已知A、B、C三個節(jié)點的坐標分別為(xa, ya)、(xb, yb)、(xc, yc)，它們到未知節(jié)點D的距離分別為da、db、dc，假設節(jié)點D的坐標為(x, y)，那么可以獲得一個非線性方程組：共九十八頁(

8、7-1) 采用(ciyng)線性化方法求解，可以得到D點的坐標為： (7-2) 共九十八頁圖7.1 三邊(sn bin)測量法 共九十八頁2三角測量法三角測量法原理如圖7.2所示，已知A、B、C三個節(jié)點的坐標分別為(xa, ya)、(xb, yb)、(xc, yc)，節(jié)點D相對于節(jié)點A、B、C的角度分別為ADB、ADC、BDC，假設節(jié)點D的坐標為(x, y)。 對于節(jié)點A、C和ADC，如果弧段AC在ABC內，那么能夠唯一確定一個(y )圓。設圓心為Ol(xo1, yo1)，半徑為rl，那么a=AOlC=(2p-2ADC)，并存在下列公式：(7-3) 共九十八頁圖7.2 三角測量法 共九十八頁由

9、式(7-3)能夠確定(qudng)圓心Ol點的坐標和半徑r1。同理對A、B、ADB和B、C、BDC分別確定相應的圓心O2(xo2, yo2)、半徑r2、圓心O3(xo3, yo3)和半徑r3。最后利用三邊測量法，由點D(x, y)、O1(xo1, yo1)、O2(xo2, yo2)、O3(xo3, yo3)確定點D點的坐標。共九十八頁3極大似然估計法極大似然估計法(Maximum Likelihood Estimation)也稱多邊測量法，如圖7.3所示。已知1、2、3等n個節(jié)點的坐標(zubio)分別為(x1, y1)、(x2, y2)、(x3, y3)、(xn, yn)，以及它們到未知節(jié)點

10、D的距離分別為d1、d2、d3、dn，假設節(jié)點D的坐標為(x, y)。共九十八頁圖7.3 極大(j d)似然估計法 共九十八頁那么，存在下列公式： 從第一個方程開始分別(fnbi)減去最后一個方程，得 (7-4) (7-5) 共九十八頁由式(7-5)得到(d do)線性方程表達式為AX=B，其中：(7-6) 。使用標準最小均方差估計方法可得到(d do)節(jié)點D的坐標為：共九十八頁7.2 無線傳感器網絡自身定位技術7.2.1 無線傳感器網絡節(jié)點定位算法(sun f)的分類目前無線傳感器網絡自身定位系統(tǒng)和定位算法非常多，通常有以下幾種分類。 共九十八頁1物理定位與符號定位定位系統(tǒng)可提供兩種類型的定

11、位結果，即物理位置和符號位置。例如，某個節(jié)點位于(473917N，1221823W)就是物理位置；而某個節(jié)點在建筑物的123號房間就是符號位置。一定條件下，物理定位和符號定位可以相互轉換。與物理定位相比，符號定位更適于某些特定的應用場合。例如，在安裝有無線煙火傳感器網絡的智能建筑物中，管理者更關心(gunxn)某個房間或區(qū)域是否有火警信號，而不是火警發(fā)生地的經緯度。大多數定位系統(tǒng)和算法都提供物理定位服務，符號定位的典型系統(tǒng)和算法有Active Badge、微軟的Easy Living、MIT的Cricket等，其中Cricket定位系統(tǒng)可根據配置實現兩種不同形式的定位。 共九十八頁2絕對定位與

12、相對定位絕對定位與物理定位類似，定位結果(ji gu)是一個標準的坐標位置，如經緯度。而相對定位通常是以網絡中部分節(jié)點為參考，建立整個網絡的相對坐標系統(tǒng)。絕對定位可為網絡提供唯一的命名空間，受節(jié)點移動性的影響較小，有更廣泛的應用領域。但研究發(fā)現，在相對定位的基礎上也能夠實現部分路由協議，尤其是基于地理位置的路由(Geo-routing)，而且相對定位不需要錨節(jié)點。大多數定位系統(tǒng)和算法都可以實現絕對定位服務，典型的相對定位算法和系統(tǒng)有SPA(Self-Positioning Algorithm)、LPS(Local Positioning System)、SpotON，而MDS-MAP定位算法可

13、以根據網絡配置的不同分別實現兩種定位。共九十八頁3緊密耦合與松散耦合所謂緊密耦合定位系統(tǒng)，是指錨節(jié)點不僅被仔細地部署在固定的位置，并且通過有線介質連接到中心控制器；而松散型定位系統(tǒng)的節(jié)點采用無中心控制器的分布式無線協調方式。典型的緊密耦合定位系統(tǒng)包括AT&T的Active Bat系統(tǒng)和Active Badge、HiBall Tracker等。它們的特點是適用于室內環(huán)境，具有較高的精確性和實時性，時間同步和錨節(jié)點間的協調問題容易解決。但這種部署策略限制了系統(tǒng)的可擴展性，代價較大(jio d)，無法應用于布線工作不可行的室外環(huán)境。共九十八頁近年來提出的許多定位系統(tǒng)和算法，如Cricket、AHLo

14、s等都屬于松散(sngsn)耦合型解決方案。它們以犧牲緊密耦合系統(tǒng)的精確性為代價而獲得了部署的靈活性，依賴節(jié)點間的協調和信息交換實現定位。在松散(sngsn)耦合系統(tǒng)中，因為網絡以Ad Hoc方式部署，節(jié)點間沒有直接的協調，所以節(jié)點會競爭信道并相互干擾。針對這個問題，劍橋的Mike Hazas等人提出使用寬帶擴頻技術(如DSSS、DS/CDMA)以解決多路訪問和帶內噪聲干擾問題。這種分類方法與基于基礎設施和無需基礎設施(Infrastructure-based versus Infrastructure-free)的分類方法相似，所不同的是，后者是以整個系統(tǒng)除了傳感器節(jié)點以外是否還需要其他設施

15、為標準的。共九十八頁4集中式計算與分布式計算集中式計算是指把所需信息傳送到某個中心節(jié)點(如一臺服務器)，并在那里進行節(jié)點定位計算的方式；分布式計算是指依賴節(jié)點間的信息交換和協調，由節(jié)點自行計算的定位方式。集中式計算的優(yōu)點在于從全局角度統(tǒng)籌規(guī)劃，計算量和存儲量幾乎沒有限制(xinzh)，可以獲得相對精確的位置估算。它的缺點包括與中心節(jié)點位置較近的節(jié)點會因為通信開銷大而過早地消耗完電能，導致整個網絡與中心節(jié)點信息交流的中斷，無法實時定位等。集中式定位算法包括凸規(guī)劃(Convex Optimization)、MDS-MAP等。N-hop Multilateration Primitive定位算法可以

16、根據應用需求采用兩種不同的計算模式。共九十八頁5基于測距技術的定位和無需測距技術的定位Range-based定位通過測量節(jié)點間點到點的距離或角度信息(xnx)，使用三邊測量(Trilateration)、三角測量(Triangulation)或最大似然估計(Multilateration)定位法計算節(jié)點位置；Range-free定位則無需距離和角度信息(xnx)，僅根據網絡連通性等信息(xnx)即可實現。 共九十八頁6粗粒度與細粒度依據定位所需信息的粒度可將定位算法和系統(tǒng)分為兩類：細粒度定位技術和粗粒度定位技術。根據信號強度或時間(shjin)等來度量與錨節(jié)點距離的稱為細粒度定位技術；根據與錨

17、節(jié)點的接近度(Proximity)來度量的稱為粗粒度定位技術。其中細粒度又可細分為基于距離和基于方向性測量兩類。另外，應用在RadioCamera定位系統(tǒng)中的信號模式匹配專利技術(Signal Pattern Matching)也屬于細粒度定位。粗粒度定位的原理是利用某種物理現象來感應是否有目標接近一個已知的位置，如Active Badge、凸規(guī)劃、Xeror的ParcTAB系統(tǒng)、佐治亞理工學院的Smart Floor等。共九十八頁7三角測量、場景分析和接近度定位定位技術也可分為三角測量、場景分析和接近度三類，其中三角測量和接近度定位與粗、細粒度定位相似。而場景分析定位是根據場景特點來推斷目標

18、位置，通常被觀測的場景都有易于獲得(hud)、表示和對比的特點，如信號強度和圖像。場景分析的優(yōu)點在于無需定位目標參與，有利于節(jié)能并具有一定的保密性；它的缺點在于需要事先預制所需的場景數據集，而且當場景發(fā)生變化時，必須重建該數據集。RADAR(基于信號強度分析)和MIT的Smart Rooms (基于視頻圖像)就是典型的場景分析定位系統(tǒng)。 共九十八頁7.2.2 無線傳感器網絡自身定位系統(tǒng)和算法下面簡單介紹無線傳感器網絡定位系統(tǒng)和幾種典型算法。1Cricket定位系統(tǒng)Cricket是松散耦合定位系統(tǒng)，這種定位系統(tǒng)彌補了緊密耦合定位系統(tǒng)的不足(bz)。它由散布在建筑物內位置固定的錨節(jié)點和需要定位的人

19、或物體攜帶的未知節(jié)點(稱為Listener)組成。錨節(jié)點隨機地同時發(fā)射射頻信號和超聲波信號，射頻信號中包含該錨節(jié)點的位置和ID值。未知節(jié)點使用TDOA(Time Difference of Arrival，到達時間差)技術測量其與錨節(jié)點的距離，當它能夠獲得3個以上錨節(jié)點距離時，使用三邊測量法可獲得物理定位，精度為44平方英尺，否則就以房間為單位提供符號定位。共九十八頁2SPA(Self-positioning Algorithm)相對定位算法相對定位算法是針對無基礎設施的移動無線網絡的一種定位算法。它選擇網絡中密度最大處的一組節(jié)點作為建立網絡全局坐標系統(tǒng)的參考點(稱為Location Refe

20、rence Group)，并在其中選擇連通度最大的一個節(jié)點作為坐標系統(tǒng)的原點。這種算法是先根據節(jié)點間的測距結果在各個節(jié)點建立局部坐標系統(tǒng)，通過節(jié)點間的信息交換與協調(xitio)，以參考點為基準通過坐標變換(旋轉與平移)建立全局坐標系統(tǒng)。共九十八頁3凸規(guī)劃定位算法凸規(guī)劃定位算法是將節(jié)點間點到點的通信連接視為節(jié)點位置的幾何約束，把整個網絡模型化為一個凸集，從而將節(jié)點定位問題轉化為凸約束優(yōu)化問題，然后使用半定規(guī)劃和線性規(guī)劃方法得到一個全局優(yōu)化的解決方案，確定節(jié)點位置。4DV-hop定位算法DV-hop定位算法是由D.Niculescu和B.Nath等人提出的。DV-hop定位算法的原理與經典的距離

21、矢量路由算法比較相似?；?jbn)思想是將未知節(jié)點到信標節(jié)點之間的距離用網絡平均每跳距離和兩者之間跳數乘積表示，使用多邊測量法計算獲得節(jié)點位置信息，其過程大致分為三個階段。共九十八頁(1) 計算未知節(jié)點與每個信標節(jié)點的最小跳數。信標節(jié)點向鄰居節(jié)點廣播自身(zshn)位置信息的分組，其中包括跳數字段，初始化為0。接收節(jié)點記錄具有到每個信標節(jié)點的最小跳數，忽略來自同一個信標節(jié)點的較大跳數的分組。然后將跳數值加1，并轉發(fā)給鄰居節(jié)點，通過這個方法，網絡中的所有節(jié)點能夠記錄下到每個信標節(jié)點的最小跳數。(2) 計算未知節(jié)點與信標節(jié)點的實際跳段距離。每個信標節(jié)點根據第一階段中記錄的其他信標節(jié)點的位置信息和

22、相距跳數，利用以下公式估算平均每跳的實際距離：共九十八頁其中，(xi, yi)、(xj, yj)是信標節(jié)點(ji din)i、j的坐標，hj是信標節(jié)點i與j(ji)之間的跳段數。然后，信標節(jié)點將計算的每跳平均距離用帶有生存期字段的分組廣播至網絡中，未知節(jié)點僅記錄接收到的第一個每跳平均距離，并轉發(fā)給鄰居節(jié)點。這個策略確保了絕大多數節(jié)點從最近的信標節(jié)點接收每跳平均距離值。未知節(jié)點接收每跳平均距離后，根據記錄的跳數，計算到每個信標節(jié)點的跳段距離。 (7-7) 共九十八頁(3) 利用多邊測量法計算自身的位置。例如在圖7.4中，通過(tnggu)前面兩個階段，能夠計算出信標節(jié)點L1與L2、L3之間的實際

23、距離和跳數。那么信標節(jié)點L2計算的每跳平均距離為(40+75)/(2+5)，假設A從L2獲得每跳平均距離，則節(jié)點A與三個信標節(jié)點之間的距離為L1=316.42，L2=216.42，L3=316.42，最后使用多邊測量法。對于網絡中所有節(jié)點性能參數都相同的各向同性網絡，DV-hop算法在網絡平均連通度為10，信標節(jié)點比例為1096時平均定位精度大約為33。其缺點是僅在各向同性的密集網絡中，校正值才能合理地估算平均每跳距離。共九十八頁圖7.4 DV-hop定位(dngwi)算法示意共九十八頁DV-hop算法與基于測距算法具有相似之處，就是都需要獲得未知節(jié)點到錨節(jié)點的距離，但是(dnsh)DV-ho

24、p獲得距離的方法是通過網絡中拓撲結構信息的計算而不是通過無線電波信號的測量。在基于測距的方法中，未知節(jié)點只能獲得到自己射頻覆蓋范圍內的錨節(jié)點的距離，而DV-hop算法可以獲得到未知節(jié)點無線射程以外的錨節(jié)點的距離，這樣就可以獲得更多的有用數據，提高定位精度。共九十八頁5DV-distance定位(dngwi)算法DV-distance算法與DV-hop類似，所不同的是相鄰節(jié)點使用RSSI(Received Signal Strength Indicator)測量節(jié)點間點到點的距離，然后利用類似于距離矢量路由的方法傳播與錨節(jié)點的累計距離。當未知節(jié)點獲得與3個或更多錨節(jié)點的距離后使用三邊測量定位。D

25、V-distance算法也僅適用于各向同性的密集網絡。實驗顯示，該算法的定位精度為20%(網絡平均連通度為9，錨節(jié)點比例為10%，測距誤差小于10%)，但隨著測距誤差的增大，定位誤差也急劇增大。共九十八頁6Euclidean定位算法圖7.5 Euclidean算法示意Euclidean(歐幾里德)定位算法給出了計算與錨節(jié)點相隔兩跳的未知節(jié)點位置的方法。如圖7.5所示，假設節(jié)點擁有RSSI測距能力，已知未知節(jié)點B、C在錨節(jié)點L的無線射程內，BC距離已知或通過RSSI測量獲得，節(jié)點A與B、C相鄰。對于四邊形ABCL，所有邊長和一條(y tio)對角線BC已知，根據三角形的性質可以計算出AL的長度(

26、節(jié)點A與L的距離)。使用這種方法，當未知節(jié)點獲得與3個或更多錨節(jié)點之間的距離后定位自身。 共九十八頁7DV-coordinate定位算法在DV-coordinate算法中，每個節(jié)點首先利用Euclidean算法計算兩跳以內的鄰近節(jié)點的距離，建立局部坐標系統(tǒng)(xtng)(以自身位置作為原點)。隨后，相鄰節(jié)點交換信息，假如一個節(jié)點從鄰居那里接收到錨節(jié)點的信息并將其轉化為自身坐標系統(tǒng)(xtng)中的坐標后，可使用兩種方法定位自身：一種方法是在自身坐標系統(tǒng)(xtng)中計算出距離，并使用這些距離進行三邊測量定位；另一種方法是將自身坐標系統(tǒng)(xtng)轉換為全局坐標系統(tǒng)(xtng)。這兩種方法具有相同的

27、性能。Euclidean和DV-coordinate定位算法雖然不受網絡各向異性的影響，但會受到測距精度、節(jié)點密度和錨節(jié)點密度的影響。實驗顯示，Euclidean和DV-coordinate算法定位誤差分別約為20%和80%(網絡平均連通度為9，錨節(jié)點比例為20%，測距誤差小于10%)。共九十八頁8DV-bearing和DV-radial定位算法DV-bearing和DV-radial算法提出了以逐跳方式(fngsh)(Hop by Hop)跨越兩跳甚至3跳來計算與錨節(jié)點的相對角度，最后使用三角測量定位的方法。兩者的區(qū)別在于，DV-radial算法中每個錨節(jié)點或節(jié)點都安裝有指南針(Compas

28、s)，從而可以獲得絕對角度信息(例如與正北方向的夾角)，并達到減少通信量和提高定位精度的目的。共九十八頁9Cooperative Ranging和Two-Phase Positioning定位算法Cooperative Ranging和Two-Phase Positioning這兩種定位算法是屬于循環(huán)求精定位算法。它們都分為起始和循環(huán)求精兩個階段。起始階段著重于獲得節(jié)點位置的粗略估算。而在循環(huán)求精階段，每一次循環(huán)開始時每個節(jié)點向其鄰居節(jié)點廣播它的位置估算，并根據從鄰居節(jié)點接收的位置信息和節(jié)點間的測距結果，重新執(zhí)行三邊(sn bin)測量，計算自身位置，直至位置更新的變化可接受時循環(huán)停止。共九十

29、八頁Cooperative Ranging算法(sun f)的起始階段又稱為TERRAIN(Triangulation via Extended Range and Redundant Association of Intermediate Nodes)。首先在所有錨節(jié)點上，根據節(jié)點間測距結果使用ABC (Assumption Based Coordinates)算法(sun f)建立局部坐標系統(tǒng)，然后將結果(以這個錨節(jié)點為原點的局部網絡拓撲)傳播到整個網絡。未知節(jié)點根據它所獲得的網絡拓撲確定其與錨節(jié)點的距離，當獲得4個與錨節(jié)點的距離后，使用三邊測量定位自身。然后進入循環(huán)求精階段。共九十八頁與

30、Cooperative Ranging算法不同，為了克服錨節(jié)點稀疏問題，Two-Phase Positioning算法在起始階段使用Hop-TERRAIN算法獲得節(jié)點位置的粗略估算。在循環(huán)求精階段，使用加權最小二乘法進行三邊測量以計算新位置。它有兩個特點：其一是給節(jié)點的位置估算增加了一個權值屬性(shxng)(錨節(jié)點為1，未定位節(jié)點為0.1；未知節(jié)點每執(zhí)行一次定位計算后，將自身權值設為參與定位計算的節(jié)點的均值)，利用加權最小二乘法進行定位計算，使誤差越大的節(jié)點對定位計算影響越小。其二是對因連通度低導致定位誤差大的節(jié)點，通過不讓其參與求精過程來消除它們的影響。共九十八頁7.3 無線傳感器網絡跟蹤

31、技術針對不同的應用，目前已經開發(fā)了多種無線傳感器網絡目標跟蹤系統(tǒng)，比較有影響的目標跟蹤系統(tǒng)與算法也很多，下面簡要介紹面向目標跟蹤的無線傳感器網絡。1目標跟蹤的基本內容目標跟蹤系統(tǒng)是為了(wi le)保持對目標當前狀態(tài)的估計而對所接收到的量測信息進行處理的軟、硬件系統(tǒng)。首先使用傳感器獲取相關的原始數據，然后根據先驗信息(數據庫、數學模型等)對原始數據進行處理，從而得到一些決策支持信息。圖7.6是目標跟蹤系統(tǒng)框圖。 共九十八頁圖7.6 目標跟蹤(gnzng)系統(tǒng)框圖 共九十八頁機動目標跟蹤的實質是一個受被跟蹤目標運動約束的優(yōu)化過程，所涉及的問題是控制、信號處理、通信等技術發(fā)展的前沿問題，最新的研究

32、動向包括采用人工智能來提高跟蹤性能和基于多傳感器的數據融合。機動目標跟蹤的基本流程為遞推過程，其基本原理框圖如圖7.7所示，傳感器接收到的觀測數據首先被考慮用于更新已建立的目標軌跡，然后數據關聯用于測量/軌跡配對是否合理或正確，并根據跟蹤維持方法，即圖中的機動識別和濾波預測，估計出各目標軌跡的真實狀態(tài)，最后在新的測量到達之前(zhqin)，由目標預測狀態(tài)可以確定下一時刻的跟蹤門中心和大小，并重新開始跟蹤過程的遞推循環(huán)。 共九十八頁圖7.7 機動(jdng)目標跟蹤基本原理框圖 共九十八頁隨著跟蹤技術的不斷發(fā)展，目標跟蹤系統(tǒng)各環(huán)節(jié)之間的界限日益模糊，但跟蹤的基本原理大同小異。其基本內容包括：(1

33、) 濾波與預測。濾波和預測的目的是估計當前和未來時刻目標的運動狀態(tài)，包括目標的位置、速度和加速度等?；镜臑V波方法有維納濾波、最小二乘濾波、a-P濾波、a-P斗濾波和卡爾曼濾波等。(2) 機動目標模型。機動目標模型是指描述目標運動狀態(tài)變化規(guī)律的數學模型。估計理論特別是卡爾曼濾波理論要求建立數學模型來描述與估計問題有關的物理現象。經典的模型包括加速度時間相關模型、相關高斯噪聲模型、變維濾波器、交互多模算法(sun f)、機動目標“當前”統(tǒng)計模型等。共九十八頁(3) 數據關聯。數據關聯是目標跟蹤的核心部分。數據關聯過程是將候選軌跡(跟蹤規(guī)則的輸出)與已知目標軌跡相比較，并最后確定正確的觀察/軌跡配

34、對的過程。正確地判定測量信息的來源是有效維持(wich)目標跟蹤的關鍵。數據關聯的研究包括最佳批處理算法、“最近鄰”濾波、概率數據關聯濾波方法、聯合概率數據關聯濾波方法、“全鄰”最優(yōu)濾波器、多假設跟蹤方法等，并有更多的新的相關學科研究成果應用于數據關聯，比如遺傳算法、神經網絡、模糊集論等。共九十八頁2面向跟蹤的無線傳感器網絡傳感器網絡的目標跟蹤實質是協作跟蹤的過程。通過節(jié)點間相互協作對目標進行跟蹤，就能在資源受限的條件下得到比單個節(jié)點獨立跟蹤更加精確的結果(ji gu)。傳感器網絡跟蹤技術的關鍵問題在于如何共享數據信息、協作處理數據和管理參與跟蹤的節(jié)點組，比如哪些節(jié)點參與跟蹤、何時喚醒參與跟蹤

35、的節(jié)點、跟蹤信息的傳播方式范圍、如何傳送跟蹤數據給控制節(jié)點以及節(jié)點需要多長時間進行通信等。這些都需要綜合具體任務要求、網絡環(huán)境等加以確定。圖7.8是面向目標跟蹤的無線傳感器網絡結構體系圖。共九十八頁圖7.8 面向(min xin)目標跟蹤的無線傳感器網絡結構體系圖 共九十八頁3協作跟蹤過程基于傳感器網絡的目標(mbio)跟蹤過程通常包括偵測、定位和通告三個主要階段，在不同的階段采用不同的技術。在偵測階段，可以選擇紅外、超聲或者振動技術偵測目標(mbio)的出現；在定位階段，通過多個傳感器節(jié)點互相協作，采用多邊測量、雙元檢測等算法，確定目標(mbio)的當前位置，根據節(jié)點位置的歷史數據來估計目標

36、(mbio)的運動軌跡；通告階段是節(jié)點交換信息的階段，主要是廣播目標(mbio)的預估軌跡，通知和啟動軌跡附近的節(jié)點加入目標(mbio)跟蹤過程。共九十八頁7.4 無線傳感器網絡時間(shjin)同步技術7.4.1 時間同步模型時間同步是無線傳感器網絡支撐技術的重要組成部分。研究無線傳感器網絡中的時間同步首先要分析其應用需求，在無線傳感器網絡中，由于傳感器節(jié)點分布密度高，而且自身資源有限，因此傳統(tǒng)網絡中高精度、不計成本和能耗的時間同步技術就不再適用于無線傳感器網絡。共九十八頁1時間同步模型隨著時間同步概念的提出，時間同步模型根據應用需求經歷了以下三種模型的演變。(1) 模糊模型：指時間同步僅需

37、知道事件發(fā)生的先后次序，無需了解事件發(fā)生的具體時間。它是將時間同步簡化為先來后到的問題(wnt)，給人直觀的印象，無需將細節(jié)具體化。(2) 相對模型：指在維持節(jié)點間的相對時間。在該模型中，節(jié)點間彼此獨立，不同步，每個節(jié)點都有自己的本地時鐘，且它知道與其他節(jié)點的時間偏移量。根據需要，每個節(jié)點可與其他節(jié)點保持相對同步。(3) 精準模型：特點在于其唯一性，它要求全網所有節(jié)點都與基準參考點保持同步，維持全網唯一的時間標準。共九十八頁7.4.2 時間同步算法與性能對比分析1時間同步算法隨著應用需求的不斷提高，時間同步趨于第三種模型(mxng)，而時間同步算法也逐步成熟，已完成了級間的跳躍。 共九十八頁1

38、)RBSRBS(Reference Broadcast Synchronization)是由J.Elson等人于2002年提出的基于參考廣播接收者與接收者之間的局部時間同步。其具體描述為：第三方節(jié)點定時發(fā)送參考廣播給相鄰節(jié)點，相鄰節(jié)點接收廣播并記錄到達時間，以此時間作為參考與本地時鐘比較。相鄰節(jié)點交換廣播到達時間利用最小方差線性擬合的方法，估算兩者的初始相位差和頻率差，以此調整本地時鐘，達到接收節(jié)點間的同步。為提高同步精度，可以增加參考廣播的個數，也可以多次廣播。RBS消除了發(fā)送節(jié)點的時延不確定性，誤差僅來源于傳輸和接收時延，同步精度較高；但由于多次廣播參考消息，能耗較大，隨著網絡規(guī)模及節(jié)點數

39、目的增多，開銷也會越來越大，因此RBS不適(bsh)用于能量有限的無線傳感器網絡。共九十八頁2) TPSNTPSN(Timing-sync Protocol for Sensor Networks)是由Saurabh Ganeriwal等人于2003年提出的基于成對雙向消息傳送的發(fā)送者與接收者之間的全網時間同步。其具體過程為：同步過程分為分層和同步兩個階段。分層階段是一個網絡拓撲的建立過程。首先確定根節(jié)點及等級，根節(jié)點是全網的時鐘參考節(jié)點，等級為0級，根節(jié)點廣播包含有自身等級信息的數據包，相鄰(xin ln)節(jié)點收到該數據包后，確定自身等級為1級，然后1級節(jié)點繼續(xù)廣播帶有自身等級信息的數據包，

40、以此類推，i級節(jié)點廣播帶有自身等級信息的數據包，其相鄰節(jié)點收到后確定自身等級為i+1，直到網絡中所有節(jié)點都有自身的等級。一旦節(jié)點被定級，它將拒收分級數據包。同步階段從根節(jié)點開始，與其下一級節(jié)點進行成對同步，然后i級節(jié)點與i-1級節(jié)點同步，直到每個節(jié)點都與根節(jié)點同步。成對同步的過程如圖7.9所示。共九十八頁圖7.9 成對同步(tngb)的過程 共九十八頁節(jié)點i在本地時刻T1時向節(jié)點j發(fā)送同步請求，該請求中包含節(jié)點i的等級和T1，節(jié)點j在本地時刻T2時收到請求并在T3時回發(fā)同步應答，該應答包含T2和T3，節(jié)點i于本地時刻T4收到應答信息，根據時間關系可列出方程： (7-8) (7-9)其中，d為消

41、息傳輸遲延，為時鐘(shzhng)偏差。經過計算得 (7-10) (7-11) 共九十八頁節(jié)點i計算出時鐘偏差D，從而調整自己的時鐘，達到同步。TPSN采用層次分級形成拓撲樹結構，從根節(jié)點開始完成了所有葉子節(jié)點與根節(jié)點的同步，在MAC層打時間戳，降低了發(fā)送端的不確定性，減小了傳送時延、傳播時延和接收時延。該算法中任意節(jié)點的同步誤差與其到根節(jié)點的跳數有關，跳數越多，誤差越大，而與網絡節(jié)點總數(zngsh)無關，所以該算法具有較好的可擴展性；但由于全網參考時間由根節(jié)點確定，一旦根節(jié)點失效，就要重新選取根節(jié)點進行同步，其魯棒性不強，再同步還需要大量計算和能量開銷，會增加整個網絡負荷。 共九十八頁3)

42、 DMTSDMTS(Delay Measurement Time Synchronization)是由Ping S于2003年提出的基于基準節(jié)點廣播的發(fā)送者與接收者之間的全網時間同步。其具體描述為：選擇一個基準節(jié)點，廣播包含時間的同步消息，接收節(jié)點根據時間信息(xnx)估算消息傳輸時延，調整自身本地時間為同步消息所帶時間加傳輸時延。消息傳輸時延td等于發(fā)射時延ts加接收處理時間tv；發(fā)射時延為發(fā)射前導碼和起始符所需的時間，等于發(fā)射位數n乘以發(fā)射一位所需的時間t，接收處理時間等于接收處理完成時間t2減消息到達時間t1。因此，可得出以下公式：td=ts+tv=nt+(t2-t1) (7-12)共九

43、十八頁將DMTS應用到多跳網絡中還采用與TPSN相同的分層方法進行同步，只是將每一層看做一個單跳網絡，基準節(jié)點依次定在0級、1級、2級、n級，逐步實現全網同步。為避免廣播消息回傳，每個節(jié)點只接收上一層等級比自己低的節(jié)點廣播。DMTS以犧牲同步精度(jn d)換取低能耗，結合使用在MAC層打時間戳和時延估計技術，消除了發(fā)送時延和接入時延，計算簡單，開銷??；但DMTS沒有估算時鐘頻偏，時鐘保持同步時間較短，時鐘計時精度(jn d)仍然影響同步精度(jn d)，致使精度(jn d)不高，難以用于定位等高精度(jn d)的應用中。共九十八頁4) FTSPFTSP(Flooding Time Synch

44、ronization Protocol)是由Branislav Kusy于2004年提出的基于單向廣播消息傳遞的發(fā)送者與接收者之間的全網時間同步。FFSP是對DMTS的改進，具體不同在于：(1) FTSP降低了時延的不確定性，將其分為發(fā)送中斷處理時延、編碼(bin m)時延、傳播時延、解碼時延、字節(jié)對齊時延和接收中斷處理時延。(2) 類似于RBS，FTSP可通過發(fā)送多個信令包，接收節(jié)點通過最小方差線性擬合計算出發(fā)送者與接收者之間的初始相位差和頻率差。共九十八頁(3) FTSP根據一定時間范圍內節(jié)點時鐘晶振頻率穩(wěn)定的原則，得出各節(jié)點間時鐘偏移量與時間呈線性關系，利用線性回歸的方法通過節(jié)點周期性發(fā)

45、送同步廣播使得接收節(jié)點得到多個數據對構造回歸直線，而且在誤差允許的時間間隔內，節(jié)點可通過計算得出某一時間節(jié)點間的時鐘偏移量，減少了同步廣播的次數，節(jié)省了能量(nngling)。(4) FTSP提出了一套較完整的針對節(jié)點失效、新節(jié)點加入等引起的拓撲結構變化時根節(jié)點的選舉策略，從而提高了系統(tǒng)的容錯性和健壯性。FTSP通過在MAC層打時間戳和利用線性回歸的方法估計位偏移量，降低了時延的不確定性，提高了同步精度，適用于軍事等需要高同步精度的場合。 共九十八頁5) LTSLTS(Lightweight Time Synchronization)是由VanGreunen Jana和Rabaey Jan于2

46、003年提出的基于成對機制的發(fā)送者與接收者之間的輕量級全網時間同步。LTS算法在成對同步的基礎上進行了改進，具體包括兩種同步方式。第一種是集中式，首先構建一個低深度的生成樹，以根節(jié)點作為參考節(jié)點，為節(jié)省系統(tǒng)有限能量，按邊進行成對同步，根節(jié)點與其下一層的葉子(y zi)節(jié)點成對同步，葉子(y zi)節(jié)點再與其下一層的孩子節(jié)點成對同步，直到所有節(jié)點完成同步。因為同步時間和同步精度誤差與生成樹的深度有關，所以深度越小，同步時間越短，同步精度誤差越小。 共九十八頁第二種是分布式，當節(jié)點i需要同步時，發(fā)送同步請求給最近的參考節(jié)點。此方式中沒有利用生成樹，按已有的路由機制尋找參考點。在節(jié)點i與參考節(jié)點路徑

47、上的所有節(jié)點都被動地與參考節(jié)點同步時，已同步節(jié)點不需要再發(fā)出同步請求，減少了同步請求的數量。為避免相鄰節(jié)點發(fā)出的同步請求重復，節(jié)點i在發(fā)送同步請求時詢問相鄰節(jié)點是否也需同步，將同步請求聚合，減少了同步請求的數目和不必要的重復。LTS根據不同的應用需求在可行的同步精度下降低了成本(chngbn)，簡化了計算復雜度，節(jié)省了系統(tǒng)能量。共九十八頁2時間同步算法性能對比分析1) 時間同步算法的性能評價指標根據無線傳感器網絡自身資源有限、節(jié)點成本低、功耗低、自組織網絡等特點，應從以下幾點考慮無線傳感器網絡的時間同步算法。(1) 能耗。由于無線傳感器網絡自身節(jié)點能量有限，其時間同步算法應保證在精度有效的前提

48、下實現低能耗。(2) 可擴展性。在無線傳感器網絡中，節(jié)點數目增減(zn jin)靈活，時間同步算法應滿足節(jié)點數目增減(zn jin)和密度變化，具有較強的可擴展性。共九十八頁(3) 魯棒性。由于環(huán)境、能量等其他因素容易導致無線傳感器網絡節(jié)點無法正常工作，甚至會退出網絡，所以時間同步算法應具有較強的魯棒性，保證(bozhng)通信暢通。(4) 同步壽命。同步壽命是指節(jié)點間達到同步后一直保持同步的時間。同步壽命越短，節(jié)點就需要在較短的時間內再同步，消耗的能量就越高。時間同步需要同步壽命較長的算法。(5) 同步消耗時間。同步消耗時間是指節(jié)點從開始同步到完成同步所需的同步。同步消耗時間越長，所需的通信

49、量、計算量和網絡開銷就越大，能耗也越高。(6) 同步間隔。同步間隔是指節(jié)點同步壽命結束到下一次同步開始所間隔的時間。同步間隔越長，同步開銷就越小，能耗越低。共九十八頁(7) 同步精度。不同的應用要求不同數量級的同步精度，有的時間同步只需知道事件發(fā)生的先后順序，而有些則需精確到微秒級。(8) 同步范圍。同步范圍分為全網同步和局部同步。全網同步難度大、費用高；局部同步較易實現。要權衡整個系統(tǒng)的功能應用及能耗開支等因素才能選擇合適的同步范圍。(9) 硬件限制?？紤]傳感器節(jié)點的體積、大小和成本，時間同步算法會受到傳感器節(jié)點硬件的限制，只有依賴硬件條件，才能設計出滿足(mnz)應用需求的時間同步算法。共

50、九十八頁2) 時間同步算法性能對比分析(fnx)為了對以上時間同步算法作進一步的分析(fnx)比較，使用了Berkerly大學研制的Mica2無線傳感器節(jié)點進行對比實驗，根據這些指標對上述時間同步算法進行比較分析(fnx)。具體性能比較如表7.1所示。共九十八頁表7.1 時間同步算法(sun f)性能對比分析表 共九十八頁7.5 無線傳感器網絡測距技術(jsh)7.5.1 基于距離的定位技術使用三邊定位和多邊定位的方法需要測量距離，有了距離后才能確定節(jié)點位置。測量距離的技術已經很成熟了。測距方法主要包括信號相位差(PDOA)、接收信號強度(RSSI)、信號傳播時間/時間差/往返時間(TOA/T

51、DOA/RTOF)、近場電磁測距(NFER)等。共九十八頁1信號相位差(PDOA)測距信號相位差(Phase Difference Of Arrival，PDOA)測距法是根據(gnj)節(jié)點所處位置不同而造成的信號傳播引起相位差異來計算信號往返所需要的時間，然后再計算節(jié)點之間的距離。節(jié)點間的距離和相位差之間的關系如下：(7-13) 共九十八頁式中，l表示信號傳播的波長；fc表示信號的傳播頻率；j表示發(fā)送信號和反射信號之間的相位差?？梢詮纳厦婀降贸鰀的范圍是0, l。節(jié)點之間的距離會存在差異，如果節(jié)點兩者之間的距離有l(wèi)倍的距離差，那么測量獲得的相位也是相同的。此時可用公式表示如下：式中，n是不

52、小于0的整數(zhngsh)。利用相位差測距，首先要估算節(jié)點間的距離，然后才能確定n的值，最后利用上述公式來計算出距離。相位差測距在小范圍內的監(jiān)測區(qū)域誤差不大，但是在大面積的場所測試的結果誤差會很大。(7-14) 共九十八頁2接收信號強度(RSSI)測距接收信號強度(Receive Signal Strength Indicator, RSSI)法是利用了無線信號會在傳播過程中衰減從而來計算節(jié)點間的距離的。信號強度和距離之間有直接的關系，利用這個關系建立兩者之間的數學模型，使用(shyng)這個數學模型可以求出發(fā)射機和接收機之間的距離。根據推導得出這個數學模型如下： (7-15) 共九十八頁式

53、中：d為節(jié)點之間的距離；n為信號衰減指數，常取值24；d0為參考的距離；PL(d)為距離發(fā)送節(jié)點d處的信號強度；Xs是均值為0，方差為s的高斯隨機噪聲變量；PL(d0)一般可以從經驗得出也可以從硬件說明定義中得到。由于定位系統(tǒng)所處的監(jiān)測區(qū)域(qy)十分復雜，信道會受到外界因素的干擾，所以根據上述公式測量的距離會存在誤差。對于測得的一組數據，可以采用最小二乘估計法來減小其誤差。共九十八頁3信號傳播時間/時間差/往返時間(TOA/TDOA/RTOF)這一類方法使用信號傳播時間來確定節(jié)點間的距離。如圖7.10所示，可以使用單程的信號傳播時間(TOA)方式，也可以使用信號往返的時間(RTOF)，或者利

54、用(lyng)不同類型的信號(如超聲波和電池波)來計算在同一對節(jié)點之間的傳播時間差(TDOA)，從而來計算節(jié)點的距離。到達時間(Time Of Arrival，TOA)法使用發(fā)射機到接收機之間的往返時間來計算收發(fā)機之間的距離。如圖7.10所示，選擇傳播速度v比較慢的信號，比如超聲波來測量到達時間。這種方法要求發(fā)射機和接收機都是嚴格時間同步的。公式表示如下：d=(T1-T0)v (7-16)共九十八頁往返傳播時間(Roundtrip-Time-Of-Flight, RTOF)如圖7.11所示。如果發(fā)射機和接收機屬于(shy)不同的時鐘域，可以用計算往返時間和扣除處理延時的方法估計發(fā)射機和接收機之

55、間的距離，即 (7-17)共九十八頁圖7.10 到達時間(shjin)TOA測量 共九十八頁 圖7.11 往返傳播(chunb)時間RTOF 共九十八頁由于T3-T0和T2-T1分別屬于發(fā)射機和接收機的時鐘域，發(fā)射機和接收機分別測量時間差，因此發(fā)射機和接收機不需要時間同步。異頻雷達收發(fā)機就是使用兩個不同頻率的信道進行往返距離(jl)的計算來測量距離(jl)。在無線傳感器網絡中使用超聲波可以實現比較精確的TOA測距系統(tǒng)。圖7.12 到達時間差TDOA測量與RSSI一樣，測量值的誤差對距離(jl)估計有很大的影響。基于信號傳播時間的測距精度由時間差的測量精度決定，時間差的精度由參考時鐘決定。因此，

56、高精度的距離(jl)測量需要高精度的參考時鐘，有的需要高精度的時鐘同步。對于低成本、低帶寬、無參考時鐘的無線傳感器網絡來說，獲得高精度時鐘本身就是一個挑戰(zhàn)。共九十八頁到達時間差(Time Difference Of Arrival, TDOA)法與TOA方法類似，該方法使用兩種不同的傳播速度的信號，如一個(y )超聲波信號和一個(y )射頻信號，兩個信號向同一個(y )方向發(fā)送即可，如圖7.12所示，收發(fā)機之間的距離為d，Tc時刻發(fā)射機發(fā)送射頻信號，隨后，在T1時刻發(fā)送超聲波信號。接收機分別在T3、T1時刻接收到射頻和超聲波信號。采用TDOA法計算節(jié)點距離的公式是： (7-18) 共九十八頁式

57、中，vRF是射頻信號傳播速度，vUS是超聲波信號傳播速度。由于發(fā)射機在傳送射頻和傳送超聲波的時候有處理時間差，需要通過精確地測量T2-T0來補償這個(zh ge)時間差，獲得精確的距離。共九十八頁4基于AOA的定位在基于到達角度AOA的定位機制中，接收節(jié)點通過天線陣列或多個超聲波接收機感知發(fā)射節(jié)點信號的到達方向，計算接收節(jié)點和發(fā)射節(jié)點之間的相對方位或角度，再通過三角測量法計算出節(jié)點的位置。AOA定位如圖7.13所示，接收節(jié)點通過麥克風陣列感知發(fā)射節(jié)點信號的到達方向。AOA測定方位角和定位的實現過程可分為三個階段： 相鄰(xin ln)節(jié)點之間方位角的測定； 相對信標節(jié)點的方位角測量； 利用方位

58、信息計算節(jié)點的位置。共九十八頁圖7.13 AOA定位(dngwi)圖共九十八頁另外，AOA信息還可以與TOA、TDOA信息一起使用成為混合定位法。采用混合定位法或者可以實現更高的精確度，減小誤差，或者可以降低對某一種測量參數數量(shling)的需求。AOA定位法的硬件系統(tǒng)設備復雜，并且需要兩節(jié)點之間存在視距(LOS)傳輸，因此不適合用于無線傳感器網絡的定位。共九十八頁7.5.2 與距離無關(wgun)的定位算法分布式不基于測距的算法常用的有質心算法、基于距離矢量計算跳數的算法(DV-hop)、無定形的(Amorphous)算法和以三角形內的點近似定位(APIT)算法。DV-hop算法在7.2

59、.2節(jié)已介紹，下面主要介紹其他三種算法。共九十八頁1質心定位算法圖7.14 質心定位算法圖示質心定位算法(質心算法)是南加州大學Nirupama Bulusu等學者提出的一種僅基于網絡連通性的室外定位算法。該算法的中心思想是：未知節(jié)點以所有在其通信范圍內的錨節(jié)點的幾何質心作為自己的估計位置。具體過程為：錨節(jié)點每隔一段時間向鄰居節(jié)點廣播一個信標(xn bio)信號，信號中包含有錨節(jié)點自身的ID和位置信息。當未知節(jié)點在一段偵聽時間內接收到來自錨節(jié)點的信標(xn bio)信號數量超過某一個預設的門限后，該節(jié)點認為與此錨節(jié)點連通，并將自身位置確定為所有與之連通的錨節(jié)點所組成的多邊形的質心。共九十八頁如圖7.14所示，多邊形ABCDE的頂點坐標分別為A(x1, y1)、B(x2, y2)、C(x