【正文】 其中b的計算變化為： () 在本文算法中，為緩解無線傳感器網(wǎng)絡(luò)中信標(biāo)節(jié)點的稀疏問題，增加訓(xùn)練樣本數(shù)，對一跳信標(biāo)節(jié)點數(shù)大于等于3的普通節(jié)點，可使用最小二乘測距定位方法法進行位置估計，升級為信標(biāo)節(jié)點。目前，常用的幾種測距技術(shù)包括RSSI、TOA、AOA、TDOA等，而基于RSSI的測距技術(shù)，無需特殊硬件，在成本和功耗方面是最低的，符合無線傳感器網(wǎng)絡(luò)的各方面的約束。因此，在我們算法中也選擇基于RSSI的測距技術(shù)測量普通節(jié)點到各信標(biāo)節(jié)點的距離。一般無線射頻芯片都提供了讀取RSSI的功能，基于RSSI的測距模型就是尋找RSSI值和傳輸距離之間的關(guān)系。目前對無線信號的傳輸問題已經(jīng)進行了許多研究，有些通過在實際應(yīng)用場景中部署節(jié)點，進行離線測量各個位置的信號強度，建立位置和信號強度對應(yīng)的關(guān)系數(shù)據(jù)庫，當(dāng)終端獲取到各信標(biāo)節(jié)點的信號后，通過查詢數(shù)據(jù)庫獲取相應(yīng)的位置，比較復(fù)雜，適用室內(nèi)等較小的應(yīng)用場景。此外，通常用以下幾種信號傳輸?shù)慕?jīng)驗?zāi)Ｐ?，如Friis Freespace模型、Tworay GroundReflection模型和Shadowing模型等。 ㏒ () 其中RSSI(d)表示節(jié)點接收到的信號強度，單位為dBm，d為發(fā)送節(jié)點和接收節(jié)點之間的距離，單位為米；表示發(fā)送的初始能量，PL()表示在參考距離處的路徑損耗；η表示路徑長度和路徑損耗之間的比例因子；理想環(huán)境下，接收節(jié)點離發(fā)送節(jié)點越近，接收到的信號強度越大，然而在實際環(huán)境中，無線信道受環(huán)境影響存在反射、多徑傳播、障礙物干擾等問題會對相同距離產(chǎn)生不同的傳播損耗，所以在公式()中引入了高斯隨機變量，均值為0、方差取。(LSVR) ，比如非測距定位中節(jié)點間的跳數(shù)或測距定位中節(jié)點間的測量距離。假定M個同構(gòu)傳感器節(jié)點部署在二維區(qū)域內(nèi)，采用相同的圓周通信模型，具有相同的通信半徑R。在節(jié)點通信半徑范圍內(nèi)的節(jié)點為鄰節(jié)點，可直接通信，非鄰居節(jié)點之間通過多跳轉(zhuǎn)發(fā)可相互通信。假設(shè)在部署節(jié)點中有N個節(jié)點通過配置GPS接收器或者其它方式能夠獲取自身位置,既信標(biāo)節(jié)點，可表示為，其它普通節(jié)點借助信標(biāo)節(jié)點和定位算法來確定自身位置。并且，假定在網(wǎng)絡(luò)中部署一個具有較強計算和存儲能力的中心節(jié)點，作回歸學(xué)習(xí)。在N維Lipschitz嵌入空間中，節(jié)點的坐標(biāo)可以用近似測量向量表示,其中表示節(jié)點i到節(jié)點j的近似測量。我們的目標(biāo)就是把N個信標(biāo)節(jié)點間的近似測量向量及信標(biāo)節(jié)點對應(yīng)的位置作為訓(xùn)練樣本，使用支持向量回歸學(xué)習(xí)方法找到一個測量向量到物理位置的擬合函數(shù)，把位置估計問題轉(zhuǎn)化為函數(shù)估計問題。然后根據(jù)普通節(jié)點到信標(biāo)節(jié)點的近似測量向量，利用得到的擬合函數(shù)估計節(jié)點的物理位置。同時，為了增加訓(xùn)練樣本數(shù)目，克服信標(biāo)節(jié)點的稀疏問題，對鄰居節(jié)點中包含三個以上的信標(biāo)節(jié)點使用最小二乘測距定位算法進行位置估計，升級為新的信標(biāo)節(jié)點。在最小二乘定位中，近似測量即為測量距離，在剩余節(jié)點使用回歸模型計算位置中僅使用連通信息，近似測量使用跳數(shù)來表示。實際上本章算法為一混合算法，測距非測距混合，以及集中式和分布式定位混合。在接下來各節(jié)，對算法進行詳細的描述。 無線傳感器網(wǎng)絡(luò)的顯著特點是傳感器節(jié)點體積較小、成本低，節(jié)點能夠大規(guī)模的部署到應(yīng)用場景。在網(wǎng)絡(luò)部署時，每個節(jié)點均配置GPS接收器勢必增加節(jié)點成本，并且GPS接收器消耗較大的能耗，而傳感器節(jié)點通常使用有限能量的電池供電，容易造成節(jié)點因能源的耗盡而導(dǎo)致網(wǎng)絡(luò)過早死亡，所以信標(biāo)的節(jié)點通常是非常有限的。由上節(jié)描述可知，信標(biāo)節(jié)點越少，在支持向量回歸訓(xùn)練中訓(xùn)練樣本也越少，不能夠很好的刻畫樣本空間上的數(shù)據(jù)特征，所獲取的回歸函數(shù)的推廣能力相對較差。為此，可以借鑒增量式定位算法思想，引入最小二乘測距定位算法，對一跳信標(biāo)節(jié)點數(shù)大于等于三個的普通節(jié)點進行位置估計，定位成功后升級為信標(biāo)節(jié)點。 在目前測距定位算法中，最小二乘方法是一種比較經(jīng)典的定位算法。當(dāng)網(wǎng)絡(luò)部署后，信標(biāo)節(jié)點廣播自身位置信息，其它節(jié)點接收后進行轉(zhuǎn)發(fā)，通過節(jié)點間的相互通信。當(dāng)普通節(jié)點獲取三個或三個以上鄰居信標(biāo)節(jié)點距離時，即可執(zhí)行最小二乘定位算法。假定信標(biāo)節(jié)點位置為，普通節(jié)點位置為(x,y),普通節(jié)點到各信標(biāo)節(jié)點的測量距離分別為，則可以建立一個線性方程組：AX=b ()其中,得到線性方程組后，由最小二乘法求解即可得到普通節(jié)點的估計位置： () 當(dāng)信標(biāo)節(jié)點間的連通信息（包括新信標(biāo)節(jié)點）收集完成后,。為避免復(fù)雜的測距過程及測距誤差的影響，在回歸定位中使用節(jié)點間的跳數(shù)來表示兩點間的近似測量。假定節(jié)點的真實位置為到信標(biāo)節(jié)點的最短路徑跳數(shù)為h(,)則近似測量向量可表示為[h(,),h(,),…,h(,]39。，q為信標(biāo)節(jié)點數(shù)（）?；貧w定位主要包括兩個階段：機器學(xué)習(xí)和定位階段。在學(xué)習(xí)階段，q個信標(biāo)節(jié)點的近似測量向量及位置集合m={ ,…, }作為訓(xùn)練樣本（這里只給出了x軸坐標(biāo)情況，y軸坐標(biāo)使用類似的方法），經(jīng)過回歸訓(xùn)練可得到公式()所表示的回歸函數(shù)。獲取回歸函數(shù)后分發(fā)到各普通節(jié)點，進入定位階段，未定位的普通節(jié)點即可根據(jù)到各信標(biāo)節(jié)點的近似測量向量（測試樣本）和接收的回歸函數(shù)來估計自身位置。位置輸出SVR學(xué)習(xí)訓(xùn)練樣本節(jié)點間的連通信息 回歸函數(shù) 測試根本 對于支持向量學(xué)習(xí)來說，核函數(shù)的選擇對輸入數(shù)據(jù)的映射及測試樣本的預(yù)測結(jié)果有著重要的影響。目前常用的核函數(shù)有線性核、多項式核、高斯徑向基核（Radial Basis Function，RBF）核及一階ANOVA RBF核。高斯徑向基核參數(shù)較少，具有很好的普適性，適用各種分布的樣本。在我們的回歸定位中也選擇高斯徑向基作為核函數(shù)：e其中表示2范數(shù)，核函數(shù)的形狀參數(shù)γ以及支持向量回歸模型中的懲罰系數(shù)C可通過網(wǎng)格優(yōu)化搜索算法獲取恰當(dāng)?shù)闹怠? 本節(jié)對LSVR算法的具體步驟給出詳細描述，如下： Step1:當(dāng)節(jié)點部署完成后，各節(jié)點建立一個信標(biāo)節(jié)點鏈表，以記錄到信標(biāo)節(jié)點的最短跳數(shù)、節(jié)點ID和位置等信息。接著，信標(biāo)節(jié)點向鄰居節(jié)點廣播包含節(jié)點ID、位置及跳數(shù)的數(shù)據(jù)包，跳數(shù)的初始值設(shè)為0。然后，信標(biāo)節(jié)點等待一個時間段后，向中心節(jié)點發(fā)送到其它信標(biāo)節(jié)點的近似測量向量（用兩節(jié)點間的最短跳數(shù)表示）。 Step2:當(dāng)某個節(jié)點接收到鄰節(jié)點發(fā)送的數(shù)據(jù)包后，首先對跳數(shù)加1，然后根據(jù)ID號查詢信標(biāo)節(jié)點鏈表，判斷是否已經(jīng)存在，如果不存在，直接存儲在信標(biāo)節(jié)點鏈表，并向鄰居節(jié)點廣播。若此信標(biāo)節(jié)點信息已經(jīng)存在，與存儲的對應(yīng)項的跳數(shù)相比較，小于存儲的跳數(shù)則用新的跳數(shù)去更新信標(biāo)節(jié)點鏈表，接著向鄰居節(jié)點繼續(xù)廣播。否則，直接丟棄此數(shù)據(jù)包； Step3:對于普通節(jié)點來說，如果接收的鄰居信標(biāo)節(jié)點數(shù)等于或者大于三個，獲取位置估計后升級為信標(biāo)節(jié)點。接著，類似于原始信標(biāo)節(jié)點廣播包含節(jié)點ID、位置及跳數(shù)的數(shù)據(jù)包到鄰居節(jié)點； Step4:經(jīng)過一輪數(shù)據(jù)包的相互轉(zhuǎn)發(fā)后，每個節(jié)點能夠獲取到各信標(biāo)節(jié)點的最短跳數(shù)（存儲在信標(biāo)節(jié)點鏈表）。當(dāng)信標(biāo)節(jié)點等待一個時間周期后，把到其它信標(biāo)節(jié)點的最短跳數(shù)向量以及自身位置發(fā)送到中心節(jié)點，作為訓(xùn)練樣本； Step5:中心節(jié)點收集各信標(biāo)節(jié)點的發(fā)送信息后，獲得回歸函數(shù)的各參數(shù)及支持向量，得到公式()所表示的的回歸函數(shù)。接著，中心節(jié)點向其它節(jié)點發(fā)送判別函數(shù)相關(guān)的信息； Step6:當(dāng)普通節(jié)點收到判別函數(shù)相關(guān)信息后，根據(jù)存儲的到各信標(biāo)節(jié)點的近似測量向量，利用公式()即可完成自身位置的估計。 對于LSVR算法來說，回歸訓(xùn)練部分的計算強度較大，因此，在網(wǎng)絡(luò)模型中可選擇一臺計算機作為中心節(jié)點，能夠提供足夠的計算能力和存儲能力。與計算復(fù)雜度相比，在傳感器網(wǎng)絡(luò)的應(yīng)用中，消息復(fù)雜度更為重要。所謂消息復(fù)雜度是學(xué)位論文指執(zhí)行定位算法的過程中，網(wǎng)絡(luò)節(jié)點所需要發(fā)送的數(shù)據(jù)量。在系統(tǒng)的能耗中，節(jié)點的通信能耗要遠遠大于計算能耗，而傳感器節(jié)點通常是電池供電，能量有限，所以在定位算法中減小通信開銷具有重要意義。為此，我們對LSVR算法和MDS算法的通信開銷做一簡單分析。假定網(wǎng)絡(luò)中部署的節(jié)點總數(shù)目為m個，信標(biāo)節(jié)點數(shù)為q個。~3主要是獲取節(jié)點間的近似測量，對于LSVR算法，只需要轉(zhuǎn)發(fā)信標(biāo)節(jié)點的信息，以獲取到各信標(biāo)節(jié)點的近似測量向量，而對于經(jīng)典MDS算法來說，則需要收集整個網(wǎng)絡(luò)內(nèi)節(jié)點間的信息，然而通常情況下m要遠大于q，所以這個步驟中LSVR算法的通信開銷要大于MDS算法的。在LSVR算法的Step4中，每個信標(biāo)節(jié)點需發(fā)送到其它q1個信標(biāo)節(jié)點的近似測量向量到中心節(jié)點，假定轉(zhuǎn)發(fā)的數(shù)據(jù)包中節(jié)點位置占2字節(jié),節(jié)點ID占1字節(jié)，跳數(shù)為1字節(jié)，則每個信標(biāo)節(jié)點發(fā)送數(shù)據(jù)包的大小為4字節(jié)，那么消息發(fā)送復(fù)雜度為，假定為最大發(fā)送跳數(shù)，而MDS算法相應(yīng)的消息發(fā)送復(fù)雜度則為。由于在網(wǎng)絡(luò)應(yīng)用中信標(biāo)節(jié)點數(shù)q要遠小于總的節(jié)點數(shù)目m，所以我們可以看出，在這兩個過程中LSVR算法的消息發(fā)送復(fù)雜度要小于MDS算法的消息發(fā)送復(fù)雜度。此外，在LSVR中完成回歸訓(xùn)練后分發(fā)k個支持向量和b值到各節(jié)點，普通節(jié)點在自身完成定位。而MDS算法收集信息后在中心節(jié)點完成各節(jié)點位置估計，然后需分發(fā)(mn)個位置信息到各節(jié)點，數(shù)據(jù)發(fā)送量也大于LSVR算法。整體上說LSVR算法與經(jīng)典MDS算法相比減少了通信開銷，從而也能夠節(jié)約系統(tǒng)能耗，延長網(wǎng)絡(luò)壽命。第4章分布式的混合禁忌搜索定位算法 在上一章中討論了靜態(tài)無線傳感器網(wǎng)絡(luò)中的定位問題，給出了一種基于支持向量回歸的混合定位算法，從計算模式上來看，實質(zhì)上仍屬于需要中心節(jié)點的集中式定位算法。通常集中式定位能夠從全局角度統(tǒng)籌規(guī)劃，獲取較好的定位性能，并且節(jié)點的計算開銷通常比較小，但需要收集較多的網(wǎng)內(nèi)節(jié)點信息，通信開銷較大，可擴展性差。在一些應(yīng)用中，可能部署成百上千個節(jié)點，規(guī)模較大。并且，在實際應(yīng)用中隨著時間的變化，可能出現(xiàn)某些節(jié)點功能失效需要重新補充節(jié)點，構(gòu)成新的網(wǎng)絡(luò)拓撲，新加入節(jié)點也需確定自身位置，且不可能重新收集全網(wǎng)絡(luò)信息。對于這些情況，集中式算法無法很好應(yīng)用，需要設(shè)計更通用的定位機制。本章繼續(xù)對靜態(tài)無線傳感器網(wǎng)絡(luò)的定位問題進行研究，針對上述問題，運用了一個基于混合禁忌搜索的二階段分布式定位算法。定位算法的執(zhí)行過程分布到各個普通節(jié)點，普通節(jié)點僅通過與一跳或者多跳鄰居節(jié)點通信，獲取局部網(wǎng)絡(luò)信息進行位置估計。本章主要的工作有：（1）通過對信標(biāo)節(jié)點位置對定位精度影響的分析，運用了一個信標(biāo)節(jié)點選擇算子，選擇合適的信標(biāo)節(jié)點參與定位；（2）引入一種簡單方法估計普通節(jié)點的初始位置，進而運用一種禁忌搜索和模擬退火相結(jié)合的混合策略對獲取的初始位置作進一步優(yōu)化，提高定位精度. 這里考慮的網(wǎng)絡(luò)模型為隨機生成的網(wǎng)絡(luò)拓撲，各節(jié)點同構(gòu)，全向通信，通信半徑為R。網(wǎng)路中具有一定比例的、預(yù)先獲取位置的信標(biāo)節(jié)點，普通節(jié)點到信標(biāo)節(jié)點的測量距離使用DVdistance方法獲?。焊餍艠?biāo)節(jié)點首先廣播位置信息包，包含標(biāo)識ID、位置、累積距離、跳數(shù)等信息，其它節(jié)點接收位置包后使用測距技術(shù)進行距離估計，若接收到新的信標(biāo)節(jié)點ID，直接存儲。若此次接收包中的距離值小于已存儲的，則進行更新。若傳輸?shù)奶鴶?shù)小于最大跳數(shù)，進行距離累加、跳數(shù)增1后轉(zhuǎn)發(fā)收到的位置信息包，否則刪除。當(dāng)節(jié)點等待一定時間后，使用獲取的信標(biāo)節(jié)點信息進行位置估計。假定普通節(jié)點的估計位置為,則節(jié)點定位可歸結(jié)為使公式()最小的無約束優(yōu)化問題 ()其中為信標(biāo)節(jié)點的位置。針對此優(yōu)化問題，本章運用了一個二階段定位算法：首先根據(jù)獲取的信標(biāo)節(jié)點信息獲取初始位置，接著以此初始位置為初始解、公式()為適配值函數(shù)，使用禁忌搜索和模擬退火結(jié)合的混和策略進行最優(yōu)解搜索。同時，考慮信標(biāo)節(jié)點位置對定位誤差的影響，設(shè)計了一個選擇算子，僅選出三個合適信標(biāo)節(jié)點參與位置估計，以下幾節(jié)將給出詳細介紹。通過分析信標(biāo)節(jié)點位置對定位精度的影響，指出如果信標(biāo)節(jié)點共線或接近共線，測距誤差對定位精度的影響較大。若信標(biāo)節(jié)點能夠均勻分布在普通節(jié)點周圍（即構(gòu)成以普通節(jié)點為中心，信標(biāo)節(jié)點為頂點的正多邊形），能夠有效減少定位誤差。為了提高定位精度、減少計算開銷，本文利用三角形相關(guān)性質(zhì)設(shè)計了一個信標(biāo)節(jié)點選擇算子，選出三個呈相對均勻分布的信標(biāo)節(jié)點參與定位。由于在我們定位算法中，使用信標(biāo)節(jié)點信息生成搜索區(qū)域，若使用均勻分布的信標(biāo)節(jié)點的信息來構(gòu)建，那么鄰域解能夠很好的分布在節(jié)點真實位置周圍，增加獲取最優(yōu)解的可能性。再者，定位只是應(yīng)用的基礎(chǔ)，如果僅使用選出的相對均勻分布的節(jié)點進行數(shù)據(jù)的轉(zhuǎn)發(fā)，既能保證很好的感知覆蓋，又能節(jié)約傳輸能耗。△ABC是正三角形，為理想分布，△ABD相對接近共線。顯然若三點接近共線則必然存在某個角度較小，如△ABD的內(nèi)角,若變化到，由于三角形內(nèi)角和不變，三內(nèi)角的差別將相對變小，分布也相對均勻，最好情況呈正三角形分布。因此，在進行信標(biāo)節(jié)點選擇時，可選擇信標(biāo)節(jié)點所形成三角形中具有最大的最小內(nèi)角者。根據(jù)三角形性質(zhì)可知三角形中最小內(nèi)角小于60度，正弦值為單調(diào)增，因此可使用正弦值代替角度作選擇標(biāo)準(zhǔn)。由三角形正弦定理可知，最小內(nèi)角必定對應(yīng)最小邊，結(jié)合余弦定理，可定義一個節(jié)點選擇算子△E，其中q表示信標(biāo)節(jié)點構(gòu)成的三角形中最短邊，s和t是另兩較長邊： （） 若信標(biāo)節(jié)點距離普通節(jié)點較近，也有助于提高定位精度，因此可加入距離因素，得到選擇算子： ()其中為到三信標(biāo)節(jié)點的測量距離，maxHop表示位置信息的最大傳輸跳數(shù)，與傳輸半徑的乘積用來對到信標(biāo)節(jié)點的平均距離進行標(biāo)準(zhǔn)化。當(dāng)信標(biāo)節(jié)點位置信息轉(zhuǎn)發(fā)完成后，根據(jù)接收的信標(biāo)節(jié)點信息，使用公式()進行節(jié)點選擇，選擇使得ΔE′值最大的三個信標(biāo)節(jié)點參與定位，公式()可改為： () 禁忌搜索算法具有