無線網(wǎng)絡(luò)傳感器定位技術(shù)概述目錄TOC\o"1-3"\h\u28870無線網(wǎng)絡(luò)傳感器定位技術(shù)概述 -1-281371.1無線網(wǎng)絡(luò)傳感器定位 -1-278311.1.1無線網(wǎng)絡(luò)傳感器 -1-59771.1.2無線網(wǎng)絡(luò)傳感器定位基本專用術(shù)語(yǔ) -1-177271.1.3無線網(wǎng)絡(luò)傳感器定位原理 -2-23931.2半正定規(guī)劃 -4-36071.1.1半正定規(guī)劃概述 -4-75281.1.2半正定規(guī)劃形式 -5-94141.1.3半正定規(guī)劃模型的建立 -5-12611.3計(jì)算機(jī)圖形學(xué)基礎(chǔ) -7-325511.3.1計(jì)算機(jī)圖形學(xué)概述 -7-20771.3.2形體在計(jì)算機(jī)內(nèi)的表示 -7-284731.3.3計(jì)算機(jī)圖形學(xué)在大型設(shè)備定位中的應(yīng)用 -10-1.1無線網(wǎng)絡(luò)傳感器定位1.1.1無線網(wǎng)絡(luò)傳感器無線網(wǎng)絡(luò)傳感器是一種通過感知外部環(huán)境所傳遞的特殊物理信息，并通過自身的規(guī)律對(duì)接收到的信息做出反應(yīng)，繼而將獲取得到的信息導(dǎo)出的器件或裝置。由于它的感知功能和信息處理功能的需要，內(nèi)部一般含有轉(zhuǎn)換元件以及敏感元件。它是一種嵌入式設(shè)備，包括控制器、傳感器、通信能力、計(jì)算能力。它通過對(duì)外界物理環(huán)境的感應(yīng)來收集信息，再通過傳感器網(wǎng)絡(luò)把信息傳送給其它的計(jì)算設(shè)備。由于近些年來與無線網(wǎng)絡(luò)傳感器相關(guān)的制造技術(shù)以及信息服務(wù)技術(shù)的飛速發(fā)展，我們已經(jīng)可以制造出微型、具有彈性且低能耗的無線網(wǎng)絡(luò)傳感器。通常來說，單個(gè)傳感器很難發(fā)揮大的作用，只有把它們適量地按照一定規(guī)律擺放到需要的空間環(huán)境中，這樣一來可以組成一個(gè)傳感器網(wǎng)絡(luò)，再通過運(yùn)用與其相適應(yīng)的系統(tǒng)軟件平臺(tái)作為輔助，就能夠?qū)崿F(xiàn)狀態(tài)監(jiān)測(cè)、實(shí)時(shí)跟蹤、環(huán)境監(jiān)測(cè)等強(qiáng)大功能。1.1.2無線網(wǎng)絡(luò)傳感器定位基本專用術(shù)語(yǔ)錨節(jié)點(diǎn):指那些具體位置固定且位置信息可以直接知道的節(jié)點(diǎn)。也叫做信標(biāo)節(jié)點(diǎn)。未知節(jié)點(diǎn)：顧名思義，也就是位置不確定，需要利用已知位置與未知位置節(jié)點(diǎn)之間的位置信息來計(jì)算其位置的節(jié)點(diǎn)。鄰居節(jié)點(diǎn)：鄰居，指某些節(jié)點(diǎn)與某一指定節(jié)點(diǎn)所在的位置關(guān)系。在以某節(jié)點(diǎn)為圓心，傳感器最大通信距離為半徑所確定的圓的面積內(nèi)的其他節(jié)點(diǎn)，即可以和某一傳感器節(jié)點(diǎn)直接通信的其他全部節(jié)點(diǎn)叫做該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。1.1.3無線網(wǎng)絡(luò)傳感器定位原理無線網(wǎng)絡(luò)傳感器定位技術(shù)主要是通過一些定位算法來實(shí)現(xiàn)的，定位算法的基本原理是通過直接或間接的方法，得到相關(guān)節(jié)點(diǎn)之間的距離、方位角或者其他相關(guān)聯(lián)的一些信息數(shù)據(jù)。通過對(duì)這些已知信息的計(jì)算分析，并對(duì)計(jì)算結(jié)果加以修正，從而得到未知節(jié)點(diǎn)的準(zhǔn)確位置信息。其中的距離信息可以通過信號(hào)發(fā)送接收時(shí)間差以及信號(hào)傳送速率來間接得到。以二維平面定位為例，容易知道在二維平面中，一個(gè)未知節(jié)點(diǎn)需要三個(gè)已知節(jié)點(diǎn)來對(duì)其進(jìn)行位置計(jì)算。假設(shè)三個(gè)已知節(jié)點(diǎn)的位置坐標(biāo)分別為A（）、B（）、C（），一個(gè)未知節(jié)點(diǎn)的坐標(biāo)為P（），在平面范圍內(nèi)，傳感器接收傳遞信息的范圍就是一個(gè)圓形區(qū)域，傳感器由于距離信息可以測(cè)出，也就是說三個(gè)已知節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離為已知的，分別為,,,那么通過平面坐標(biāo)距離公式可以得到以下方程組：（2-1）對(duì)上述方程進(jìn)行求解得到：上述求解過程針對(duì)的是一種理想條件下的傳感器定位，如圖2-1左所示，是在認(rèn)為傳感器之間的距離信息準(zhǔn)確無誤的情況下進(jìn)行的，但在實(shí)際操作中，節(jié)點(diǎn)之間的信號(hào)傳送往往會(huì)受到干擾，如傳感器布置區(qū)域存在一些無法移動(dòng)的障礙物，信號(hào)穿過障礙物比穿過空氣的時(shí)間長(zhǎng)，這種情況下測(cè)得的距離信息則是不準(zhǔn)確的，比實(shí)際距離偏大的。如圖2-1右所示，由三個(gè)傳感器測(cè)量確定的三個(gè)圓相交得到一個(gè)確定的公共區(qū)域。容易知道我們所需要確定的未知節(jié)點(diǎn)的位置在這一確定區(qū)域內(nèi)，而傳感器網(wǎng)絡(luò)定位算法，就是要通過計(jì)算在這一確定區(qū)域中找到這一未知節(jié)點(diǎn)，并通過優(yōu)化使得計(jì)算得到的未知節(jié)點(diǎn)的位置與未知節(jié)點(diǎn)的真實(shí)位置之間的誤差最小化。而無線傳感器的通信距離有限，對(duì)定位的算法要求一般也比較高，以致于評(píng)價(jià)定位算法好壞的重要標(biāo)準(zhǔn)之一就是運(yùn)用相應(yīng)的定位算法計(jì)算得到的未知節(jié)點(diǎn)的位置與其實(shí)際位置的偏差大小。關(guān)于無線網(wǎng)絡(luò)傳感器定位技術(shù)的定位算法也有很多，如DV-HOP算法、凸規(guī)劃算法、質(zhì)心算法、APIT算法、半正定規(guī)劃算法，而本論文正是基于半正定規(guī)劃算法來進(jìn)行計(jì)算的。圖2-1無線網(wǎng)絡(luò)傳感器平面定位示意以上是以二維平面為例來解釋無線網(wǎng)絡(luò)定位的原理，在三維立體空間中，利用無線網(wǎng)絡(luò)傳感器定位的原理也是一樣的，假設(shè)空間中有三個(gè)不在同一直線上的已知節(jié)點(diǎn)，那么每個(gè)節(jié)點(diǎn)所能傳遞并接收信息的空間范圍就是一個(gè)球形空間，如果三個(gè)已知傳感器的位置是在地面，那么每個(gè)節(jié)點(diǎn)能夠傳遞并接收的信息的空間范圍就變成半球形（地面以下可以不用考慮），如下圖2-2，兩個(gè)半球形相交，相交的公共部分為一個(gè)半圓形，第三個(gè)半球形與半圓形相交有一個(gè)公共點(diǎn)，這一點(diǎn)就是所要確定的未知節(jié)點(diǎn)的位置。圖2-2空間定位示意圖1.2半正定規(guī)劃1.1.1半正定規(guī)劃概述半正定規(guī)劃（Semi-positiveDefiniteProgramming,簡(jiǎn)稱SDP)問題其實(shí)是凸優(yōu)化問題的一種特殊形式，它具有線性目標(biāo)函數(shù)，約束條件之一是對(duì)稱矩陣的仿射組合半正定，目的是對(duì)線性目標(biāo)函數(shù)的極值進(jìn)行求解。這個(gè)約束條件是凸的，非線性的。二十世紀(jì)六十年代，半正定規(guī)劃的研究就已經(jīng)開始了，F(xiàn)an和Belman[38]兩人在1963年第一次提出一個(gè)半正定規(guī)劃問題，后來又有學(xué)者將半正定規(guī)劃與控制論聯(lián)系起來進(jìn)行分析研究，二十世紀(jì)七十年代初期，Wolf,Donath和Cullumn[39]等人利用半正定規(guī)劃對(duì)圖劃分算法進(jìn)行研究，使得原來復(fù)雜的問題變得簡(jiǎn)單起來。而讓半正定規(guī)劃成為求解組合優(yōu)化問題的重要工具的標(biāo)志，是Shor[40]解決組合優(yōu)化問題時(shí)提出利用半正定規(guī)劃松弛。二十世紀(jì)九十年代，多項(xiàng)式時(shí)間內(nèi)點(diǎn)算法理論由Nesterov[41]和Nemirovski[42]提出，這對(duì)于一般凸優(yōu)化問題的求解是很好的。時(shí)間到達(dá)二十一世紀(jì)，也就是近些年，YinyuYe[43]將線性規(guī)劃內(nèi)點(diǎn)算法推廣到半正定規(guī)劃，使得半正定規(guī)劃的發(fā)展再上新臺(tái)階。其相關(guān)文獻(xiàn)中，有關(guān)傳感器定位問題對(duì)應(yīng)的特殊半正定規(guī)劃模型可以表示為：mins.t.（2-2）如果是一個(gè)關(guān)于Z的凸函數(shù)，那么上述模型就成為一個(gè)凸優(yōu)化問題，特殊情況下，如果是關(guān)于Z的線性函數(shù)，并且是一個(gè)凸集，則上述模型是一個(gè)半正定規(guī)劃模型。半正定規(guī)劃是一種定義在實(shí)數(shù)域上的半正定矩陣錐上的規(guī)劃，它也是線性規(guī)劃的一種推廣。半正定線性規(guī)劃的目標(biāo)函數(shù)及其可行域都為線性，半正定非線性規(guī)劃則容易知道，是目標(biāo)函數(shù)為非線性或者其可行域?yàn)榉蔷€性[44]。半正定規(guī)劃這一算法自提出至今，廣泛應(yīng)用于各種優(yōu)化問題當(dāng)中，對(duì)解決優(yōu)化方面相關(guān)問題起著重要的積極作用。也正因?yàn)樗且环N相當(dāng)有效的算法，能夠解決很多優(yōu)化問題，因而本論文使用半正定規(guī)劃算法作為相關(guān)定位的算法來進(jìn)行定位計(jì)算。1.1.2半正定規(guī)劃形式半正定規(guī)劃算法的標(biāo)準(zhǔn)形式可如下：mins.t.（2-3）其中，、是實(shí)數(shù)矩陣，，是已知數(shù)據(jù)。一般來說，半正定規(guī)劃問題的解為一個(gè)矩陣,且矩陣，如果矩陣滿足所有的約束條件并且，那么求得的解叫做內(nèi)部可行解或者嚴(yán)格可行解。在一些情況中也會(huì)用到SDP的對(duì)偶形式去解決相關(guān)問題，SDP的對(duì)偶形式可如下：maxs.t.（2-4）其中,,求得的解滿足所有的約束條件，則稱其為對(duì)偶內(nèi)點(diǎn)內(nèi)部可行解。1.1.3半正定規(guī)劃模型的建立假設(shè)在一個(gè)d維空間中，有m個(gè)已知錨點(diǎn)（），n個(gè)未知節(jié)點(diǎn)(）。任意兩個(gè)未知節(jié)點(diǎn)i和j之間的距離數(shù)據(jù)可以測(cè)量出來，也就是已知，記為，任意兩個(gè)已知節(jié)點(diǎn)k與未知節(jié)點(diǎn)j之間的距離也可以通過測(cè)量知曉，記為，且任意兩點(diǎn)距離的下界為R。由于任意節(jié)點(diǎn)之間傳遞信息過程中，信號(hào)穿過不同介質(zhì)速度不一樣，導(dǎo)致信號(hào)接收時(shí)間偏長(zhǎng)，測(cè)量距離偏大。因此，定位問題可以描述為一個(gè)混合等式和不等式的誤差最小化問題,問題模型如下：mins.t.（2-5）令為需要確定的矩陣，為第個(gè)位置為1，其余位置為0的向量，為第個(gè)位置為1，第個(gè)位置為-1，其余位置為0的向量。令,將變量松弛，并且引入松弛變量Z,則：,（2-6）原問題即可松弛為半正定規(guī)劃問題，如下：mins.t.（2-7）可知矩陣有個(gè)未知變量。如果全部的測(cè)量結(jié)果都是準(zhǔn)確無誤的并且其他距離邊界是可行的，即誤差項(xiàng)和為0，那么式（2-7）即有唯一取得最小值解:（2-8）此時(shí)，必須要有，而即是我們所要確定的未知傳感器的位置。通過以上分析可知，原問題的求解范圍由于松弛變換的原因增加了，但所求得的最優(yōu)解仍能滿足原問題的約束條件。1.3計(jì)算機(jī)圖形學(xué)基礎(chǔ)1.3.1計(jì)算機(jī)圖形學(xué)概述計(jì)算機(jī)圖形學(xué)指的是利用計(jì)算機(jī)研究圖形的表示、生成、處理和顯示的一門重要的計(jì)算機(jī)學(xué)科分支。隨著世界科技的進(jìn)步，在過去十幾年里，計(jì)算機(jī)系統(tǒng)的硬件、軟件也發(fā)展的十分快，就目前來看，圖形處理功能對(duì)于計(jì)算機(jī)來說已是十分容易實(shí)現(xiàn)，而且現(xiàn)在很多領(lǐng)域都在應(yīng)用計(jì)算機(jī)圖形學(xué)，如CAD設(shè)計(jì)、廣告設(shè)計(jì)、影視娛樂等等。同時(shí)，計(jì)算機(jī)圖形學(xué)技術(shù)憑借著本身的不斷進(jìn)步及其寬泛的應(yīng)用，已成為計(jì)算機(jī)科學(xué)技術(shù)與其他應(yīng)用學(xué)科之間溝通的一座橋梁。計(jì)算機(jī)圖形學(xué)是一門研究圖形在計(jì)算機(jī)中的處理以及顯示的科學(xué)，我們平常在書籍、手機(jī)、電腦和電視等平臺(tái)看到的圖形，往往都有一些共同的屬性，例如，他們都有幾何元素和幾何屬性，而圖片中的點(diǎn)、線、面、體就是幾何元素，有些我們平時(shí)學(xué)習(xí)中遇到的圖形，像地理中的等高線圖、山體剖面圖，工程制圖中的工程圖等，這些圖形所傳達(dá)的信息都是用線條表達(dá)的，具有幾何元素；色彩、灰度、線寬、線型就是幾何屬性，而生活中比較常見的風(fēng)景圖等實(shí)物圖，這些圖形看起來比較真實(shí)，有明暗對(duì)比，也叫做明暗圖，具有幾何屬性。通過對(duì)圖形的分類，我們對(duì)不同類別的圖形的處理技術(shù)也不同。在當(dāng)今社會(huì)生活中，我們?cè)趯W(xué)習(xí)或者工作中往往會(huì)應(yīng)用到很多圖片，有時(shí)是為了記錄自己的生活，有時(shí)是為了更好地完成工作或者學(xué)習(xí)任務(wù)，這時(shí)候，一張出色的圖片往往會(huì)起到令人意想不到的好反饋，而利用計(jì)算機(jī)對(duì)圖形進(jìn)行一系列的加工改造，正好可以滿足我們的需求。實(shí)際應(yīng)用當(dāng)中，有時(shí)圖形的加工處理僅僅依靠計(jì)算機(jī)圖形學(xué)是不可以單獨(dú)完成的，還需要靠計(jì)算機(jī)輔助幾何設(shè)計(jì)和圖像處理技術(shù)來共同處理完成。因此，計(jì)算機(jī)圖形學(xué)這一學(xué)科的研究?jī)?nèi)容也很寬泛，涉及各個(gè)行業(yè)各個(gè)領(lǐng)域。同樣，在當(dāng)今時(shí)代背景下，我們很多人的工作學(xué)習(xí)甚至生活都離不開計(jì)算機(jī)圖形學(xué)。1.3.2形體在計(jì)算機(jī)內(nèi)的表示由于線框模型和表面模型都無法完整地表達(dá)出形體的三維信息，而實(shí)體模型則可以，因此對(duì)實(shí)體模型的研究很早就已經(jīng)開始了，但是，由于早期沒有受到關(guān)注，一直到20世紀(jì)60年代后半期，關(guān)于實(shí)體造型的相關(guān)報(bào)道一直都極少。到了70年代初期時(shí)候，美國(guó)羅徹斯特大學(xué)的PADL-1,PADL-2系統(tǒng)、英國(guó)劍橋大學(xué)的BUILD-1系統(tǒng)、日本北海道大學(xué)的TIPS-1系統(tǒng)、德國(guó)柏林工業(yè)大學(xué)的COMPAC系統(tǒng)等一些實(shí)體造型系統(tǒng)相繼誕生?？慷嗝骟w表示形體,無法精確用曲面表示是早期的實(shí)體造型系統(tǒng)的共同特點(diǎn)。數(shù)據(jù)結(jié)構(gòu)相對(duì)來說較簡(jiǎn)單、能夠快速地生成和顯示明暗圖、集合運(yùn)算是多面體模型的優(yōu)點(diǎn)。但是，精確的曲面表示和近似的多面體逼近表示同時(shí)存在于同一系統(tǒng)中違背了幾何定義的惟一性原則，而且，多面體模型不可以準(zhǔn)確表示曲面模型，用多面體表示出來的模型有誤差，簡(jiǎn)單地增加平面片的數(shù)量并不能夠解決這個(gè)問題。所以，想要很好地解決這個(gè)問題，就需要在表示模型時(shí)采用更加精確的形體。

雖然Coons曲面、B樣條曲線和曲面、Bezier曲線和曲面等設(shè)計(jì)方法在1960-1970年間被提出，但曲面造型系統(tǒng)自身有一定的缺陷，很難構(gòu)造封閉的形體。因?yàn)閺?fù)雜曲面這一問題不能被實(shí)體造型系統(tǒng)合理有效地解決，這在相當(dāng)大程度上使得幾何造型的覆蓋域受束縛。于是，人們開始了新的研究。在1978年,實(shí)體造型系統(tǒng)Romulus被英國(guó)ShapeData公司推出,這是一次巨大的飛躍，因?yàn)樗状我霊?yīng)用代數(shù)方程的形式精確表示的二次曲面。

直到20世紀(jì)80年代末,NURBS曲線曲面設(shè)計(jì)方法的出現(xiàn)使得形體表示有了飛速發(fā)展，它能夠精確的表示出形體，使得形體的表示問題得到有效的解決。線框模型、曲面模型和實(shí)體模型是幾何造型系統(tǒng)里3種能夠有效對(duì)物體進(jìn)行描述的三維模型。其中，線框模型在計(jì)算機(jī)圖形學(xué)和CAD/CAM領(lǐng)域是最先用于表示物體的模型。線框模型，顧名思義，看上去只有一些線組成的框架，而這個(gè)框架是由點(diǎn)和邊組成，很顯然一個(gè)框架是不能表示出曲面信息的。而且它也無法明確對(duì)給定點(diǎn)與物體之間的關(guān)系給出定義，因此很多重要問題不能用線框模型去處理,這在很大程度上限制了它的應(yīng)用范圍。線框模型，也可以說是多邊形網(wǎng)絡(luò)。從直觀上來說，一個(gè)多邊形網(wǎng)絡(luò)是通過運(yùn)用多邊形單元，最常見的如三角形，來對(duì)一個(gè)連續(xù)曲面進(jìn)行分割。這也可以更加形式化描述為：用一個(gè)多元組（V，K）來定義網(wǎng)格M，其中模型的頂點(diǎn)集合（R3中的點(diǎn)），K是包含點(diǎn)之間的連接信息（Adjacencyinformation）還有頂點(diǎn)的連接方式以形成網(wǎng)格的邊和面。例如，可以這樣表示一個(gè)三角形構(gòu)成的網(wǎng)絡(luò)：。其中，多元組中的元素分別代表三個(gè)頂點(diǎn)、三條邊還有其構(gòu)成的三角形。

曲面模型其實(shí)是對(duì)線框模型的完善，在框架上填充了面的信息。曲面模型的建立需要參數(shù)曲線與參數(shù)曲面。而在三維空間中，參數(shù)曲線定義為參數(shù)空間（的子集）到三維空間的映射：（2-9）其中，是曲線參數(shù)，通常的取值范圍是在0-1之間，曲線的起點(diǎn)為，終點(diǎn)為。典型的參數(shù)曲線公式為：（2-10）其中，是控制點(diǎn)，（）是調(diào)和函數(shù)，控制點(diǎn)集合也叫控制多邊形。貝塞爾曲線是計(jì)算機(jī)圖形學(xué)最常用的參數(shù)曲線之一，貝塞爾曲線的數(shù)學(xué)定義如下：（2-11）其中，是控制點(diǎn)，是次伯恩斯坦多項(xiàng)式（BernsteinPolynomial）。次伯恩斯坦多項(xiàng)式定義如下：（2-12）我們能夠比較容易地從參數(shù)曲線擴(kuò)展到參數(shù)曲面，參數(shù)曲面的參數(shù)域是的子集而不是的子集，并且需要使用三個(gè)二元函數(shù)來進(jìn)行定義從參數(shù)到三維空間的映射，相關(guān)定義如下：（2-13）其中，和是曲面參數(shù)。通常，參數(shù)曲面的參數(shù)和的取值范圍為0-1。參數(shù)曲面常用形式之一是張量積曲面（TensorProductSurface）,定義如下：（2-14）其中，是初始控制點(diǎn)，和是調(diào)和函數(shù)，此時(shí)，控制點(diǎn)稱為曲面的控制網(wǎng)絡(luò)（ControlNet）。依據(jù)張量積曲面，貝塞爾曲線的定義可以擴(kuò)展為如下曲面形式：（2-15）其中，是控制網(wǎng)絡(luò)中的點(diǎn)，是n階伯恩斯坦多項(xiàng)式，是m階伯恩斯坦多項(xiàng)式。但在曲面模型中，只有一些面的信息，據(jù)此并不能準(zhǔn)確知道該物體與其他物體的位置關(guān)系，也無法得到的一些準(zhǔn)確信息，如體積、表面積等。作為最高級(jí)的模型，物體的全部形狀信息都可以被實(shí)體模型完整地表示出來,它還可以準(zhǔn)確地表示出一個(gè)點(diǎn)在物體上的具體位置,這種模型能夠滿足物性計(jì)算和有限元分析等一些應(yīng)用的要求。而實(shí)體模型的表示也有很多方式，一般分為邊界表示、構(gòu)造表示、分解表示。邊界表示是利用形體的邊界信息以及邊界圍成的曲面的定義來表示形體，如果可以知道一個(gè)實(shí)體所有的邊界信息，這些邊界就可以構(gòu)成一個(gè)框架，這個(gè)框架上所具有的信息，就是形體的拓?fù)湫畔?，而如果知道這些邊界所圍成的曲面的曲面方程，也就是形體的幾何信息，那么就可以將