一種基于分簇的3D-RSSI的定位算法

劉曉鑫，方旺盛，張永建

（江西理工大學(xué)信息工程學(xué)院，贛州341000）

引 言

隨著無線傳感器網(wǎng)絡(luò)（WSN）的發(fā)展，節(jié)點(diǎn)定位技術(shù)已經(jīng)滲入到生活的各個(gè)方面，無線傳感器網(wǎng)絡(luò)之間的協(xié)作能夠進(jìn)行目標(biāo)跟蹤、井下定位、緊急求救、森林火災(zāi)等［1-2］。

對于大多數(shù)無線傳感器網(wǎng)絡(luò)，沒有與位置相結(jié)合的信息是沒有意義的。在節(jié)點(diǎn)精確定位的同時(shí)，還要提高路由效率，降低功耗，延長整個(gè)網(wǎng)絡(luò)的壽命。現(xiàn)有的算法中按照信息處理方式可分為兩類：集中式算法和分布式算法［3-4］。集中式算法的缺點(diǎn)在于中心節(jié)點(diǎn)位置附近的節(jié)點(diǎn)會因通信數(shù)據(jù)過大導(dǎo)致節(jié)點(diǎn)能量耗完，以致整個(gè)網(wǎng)絡(luò)數(shù)據(jù)處理中心癱瘓。分布式算法則適用于大規(guī)模無線傳感網(wǎng)絡(luò)，典型的分布式算法的優(yōu)點(diǎn)在于獲得精確位置估算的同時(shí)盡可能延長了整個(gè)網(wǎng)絡(luò)的生命周期［5］。

在大規(guī)模無線傳感網(wǎng)絡(luò)中，由于不斷迭代，以至于最后的節(jié)點(diǎn)位置出現(xiàn)較大的誤差，所以本文提出分簇算法的節(jié)點(diǎn)定位算法，在各分簇中把誤差降低到最低，然后從sink節(jié)點(diǎn)開始把各簇的位置的節(jié)點(diǎn)合并，最后完成全局節(jié)點(diǎn)的定位。在定位算法方面考慮到算法復(fù)雜度、成本等，本文選取基于RSSI的定位算法。RSSI節(jié)點(diǎn)定位方法通過接收錨節(jié)點(diǎn)上的功率，計(jì)算傳播功耗，利用理論將RSSI強(qiáng)度轉(zhuǎn)化為距離，利用最小二乘法估計(jì)未知節(jié)點(diǎn)位置坐標(biāo)。但在計(jì)算過程中不斷疊加的誤差，使得整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)定位誤差增大。故本文從減少通信開支、降低成本和節(jié)能角度提出了一種基于分簇的3D-RSSI的定位算法，首先確定各簇內(nèi)的簇首，簇首內(nèi)保存著各簇的拓?fù)浣Y(jié)構(gòu)，各簇內(nèi)節(jié)點(diǎn)之間的距離通過接收到的信號強(qiáng)度來確定，隨后從sink節(jié)點(diǎn)開始融合各簇間的未知的位置，來實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的定位。

1 本文分簇算法

1.1 LEACH協(xié)議

分簇算法［6］最大程度上延長整個(gè)網(wǎng)絡(luò)的壽命，簡化了整個(gè)網(wǎng)絡(luò)定位的復(fù)雜度，并且減少了網(wǎng)絡(luò)通信量，使得整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)定位更加精確。本文選用LEACH 路由協(xié)議［7］，LEACH 協(xié)議是無線傳感網(wǎng)絡(luò)中的一種基于簇類結(jié)構(gòu)和分層技術(shù)的協(xié)議，相比于傳統(tǒng)Flooding和Gossiping協(xié)議，較大程度上節(jié)約了能量。LEACH 路由協(xié)議其基本思想是以循環(huán)方式隨機(jī)選擇簇首節(jié)點(diǎn)，將整個(gè)網(wǎng)絡(luò)的能量負(fù)載平均分配到每個(gè)節(jié)點(diǎn)上，從而降低能耗來延長網(wǎng)絡(luò)的生存時(shí)間。LEACH 定義了“輪”的概念，每一輪由初始化和穩(wěn)定工作兩個(gè)階段組成。在初始化階段，隨機(jī)選擇節(jié)點(diǎn)作為簇首，成為簇首之后廣播其信息，簇首周圍的節(jié)點(diǎn)根據(jù)接收到的信號強(qiáng)度來判斷是否要加入該簇，并告知簇首。在穩(wěn)定工作階段，節(jié)點(diǎn)完成了對周圍壞境的信息采集、數(shù)據(jù)融合，并發(fā)送至匯聚節(jié)點(diǎn)。完成這一輪后進(jìn)入下一工作周期。分簇節(jié)點(diǎn)自定位技術(shù)包括三個(gè)步驟：①各個(gè)簇的構(gòu)建；②簇內(nèi)節(jié)點(diǎn)位置的估算；③各簇節(jié)點(diǎn)的融合和全局節(jié)點(diǎn)的定位。這三個(gè)階段都由LEACH 協(xié)議來完成，這種適合用于二維坐標(biāo)的算法也可推廣到三維空間中。

簇首節(jié)點(diǎn)的選取是LEACH 協(xié)議中的關(guān)鍵，具體的選擇辦法是：啟動(dòng)節(jié)點(diǎn)，各節(jié)點(diǎn)產(chǎn)生一個(gè)［0，1］之間的隨機(jī)數(shù)，若該值小于閥值T（n），則該節(jié)點(diǎn)成為簇首。在每輪循環(huán)中，如果節(jié)點(diǎn)已經(jīng)當(dāng)選為簇首，則把T（n）設(shè)置為0，該節(jié)點(diǎn)在這一輪中不會再次當(dāng)選為簇首。如果節(jié)點(diǎn)尚未當(dāng)選為簇首，則會以概率T（n）參與選擇；并伴隨著當(dāng)選過簇首的節(jié)點(diǎn)數(shù)量的增多，剩余節(jié)點(diǎn)的T（n）增大，產(chǎn)生小于T（n）隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選為簇首的概率增大。剩下一個(gè)節(jié)點(diǎn)未當(dāng)選時(shí)，T（n）＝1，表示該節(jié)點(diǎn)無條件成為簇首。T（n）的計(jì)算公式如下：

其中，p 為期望的簇首節(jié)點(diǎn)中的百分比；r是當(dāng)前輪數(shù)；r mod（1／p）代表這一輪循環(huán)中當(dāng)選過簇首節(jié)點(diǎn)的個(gè)數(shù)，G是在最后的1／p輪中未成為簇首節(jié)點(diǎn)的節(jié)點(diǎn)集；T（n）實(shí)際上是在第r輪尚未成為簇首節(jié)點(diǎn)的節(jié)點(diǎn)成為簇首的平均概率。

1.2 基于節(jié)點(diǎn)勢的分簇算法

對LEACH 協(xié)議作簡要的改進(jìn)，分簇過程從位于網(wǎng)路中心的sink節(jié)點(diǎn)開始，首先以sink節(jié)點(diǎn)作為其中一個(gè)簇首，簇內(nèi)節(jié)點(diǎn)依次按規(guī)則尋找臨近節(jié)點(diǎn)，直到找到對應(yīng)的簇首。簇從sink節(jié)點(diǎn)逐漸向網(wǎng)絡(luò)各個(gè)方向擴(kuò)展，直到整個(gè)網(wǎng)路被覆蓋。尋找相鄰簇首的具體規(guī)則如圖1所示。

2 信號模型

2.1 RSSI無線信號傳輸模型

無線信號的傳輸路徑損耗對于RSSI定位算法［8-9］的精度影響很大。常用的路徑損耗模型有：自由空間傳播模型、對數(shù)距離路徑損耗模型和哈它模型等。自由空間傳播模型是假設(shè)在一個(gè)理想的傳播環(huán)境，在發(fā)送者和接收者之間只存在一條無障礙的直線傳播路徑。接收端收到的信號平均功率pr（d）為：

圖1 節(jié)點(diǎn)尋找簇首流程圖

其中，pt為發(fā)送信號的強(qiáng)度，Gt和Gr分別是發(fā)送端和接收端的天線增益，L（L≥1）為系統(tǒng)損失，λ為波，d為接收端與發(fā)送端之間的距離。通常情況下，取Gt＝Gr＝1，L＝1。

從（1）式可以看出在d＝0時(shí)，接收功率是無意義的，因此對于該模型通常是定義一個(gè)參考距離d0，在d0所接收到的功率當(dāng)成是參考功率，則（1）式可改寫為：

在實(shí)際環(huán)境中，由于存在多徑效應(yīng)及噪聲的干擾，接收端收到的功率和自由空間傳播模型的計(jì)算結(jié)果存在較大誤差，利用如下對數(shù)損耗模型對其進(jìn)行修正：

其中，pr（d）與長度相關(guān)的路徑耗散，d0是從發(fā)送器附近測量的參考距離；α為路徑衰減因子；取值一般2～4之間，N為隨機(jī)噪聲，服從均值為零的高斯分布。

2.2 三維RSSI定位模型

在無線傳感器網(wǎng)絡(luò)中，對于二維定位系統(tǒng)，通過3個(gè)或3個(gè)以上的錨節(jié)點(diǎn)的距離可以確定一個(gè)未知節(jié)點(diǎn)的坐標(biāo)。推廣到三維定位系統(tǒng)中，需要4個(gè)或以上的錨節(jié)點(diǎn)的距離確定一個(gè)未知節(jié)點(diǎn)的坐標(biāo)。假設(shè)在無線傳感器網(wǎng)絡(luò)三維系統(tǒng)中，存在k個(gè)不在同一平面的錨節(jié)點(diǎn)（x1，y1，z1），（x2，y2，z2），（x3，y3，z3），…，（xk，yk，zk），并且錨節(jié)點(diǎn)到未知節(jié)點(diǎn)的距離分別為d1，d2，d3，…，dk。利用最小二乘法定位未知節(jié)點(diǎn)：

將前面k-1個(gè)方程分別減去最后一個(gè)方程得到：

式（5）的線性方程表示方式為A·X＝b，其中：

3 仿真與分析

本文用MATLAB仿真分析經(jīng)典3D-RSSI模型、分簇3D-RSSI模型和參考文獻(xiàn)［6］算法，在1000×1000×1000 m3的正方體空間中，隨機(jī)分布1000 個(gè)節(jié)點(diǎn)，錨節(jié)點(diǎn)占10%～30%。三種算法各仿真50次，仿真結(jié)果取50次的平均值。

定位誤差在無線傳感器網(wǎng)絡(luò)中是判斷定位算法的重要指標(biāo)，首先仿真研究錨節(jié)點(diǎn)個(gè)數(shù)與平均定位誤差的關(guān)系，路徑耗散指數(shù)n取4，通信半徑為60m，信標(biāo)節(jié)點(diǎn)由開始的100（30%）個(gè)，每次仿真增加40 個(gè)，直至達(dá)到300（30%）個(gè)，實(shí)驗(yàn)仿真表明，如圖2～圖5所示，平均定位誤差隨著錨節(jié)點(diǎn)數(shù)量的增加而遞減。由此可證本文分簇3D-RSSI模型優(yōu)于經(jīng)典3D-RSSI算法。

覆蓋率也是判斷定位誤差的重要參數(shù)。實(shí)驗(yàn)仿真表明，覆蓋率隨著錨節(jié)點(diǎn)數(shù)量而增大，由此可以推斷在大規(guī)模無線傳感網(wǎng)絡(luò)中，分簇算法不僅平均誤差減小了，而且也提高了覆蓋率。

圖2 錨節(jié)點(diǎn)數(shù)量與平均定位誤差關(guān)系

圖3 錨節(jié)點(diǎn)數(shù)量與定位覆蓋率關(guān)系

圖4 分簇空間節(jié)點(diǎn)的定位效果圖

在圖2中，仿真表明隨著錨節(jié)點(diǎn)的增加，每次增加10個(gè)錨節(jié)點(diǎn)，仿真平均誤差隨著錨節(jié)點(diǎn)數(shù)量的增加而減小，說明錨節(jié)點(diǎn)的數(shù)量在節(jié)點(diǎn)定位精確度方面有著重要作用，但錨節(jié)點(diǎn)的增加會導(dǎo)致成本費(fèi)用的提高，所以錨節(jié)點(diǎn)數(shù)量控制在15%左右最為合理。在圖3中覆蓋率也是相同的問題。

圖5 整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)定位效果圖

圖4～圖5分別是分簇定位效果和整個(gè)網(wǎng)絡(luò)的定位效果圖。相比集中式算法，本文提出的算法節(jié)省了能耗，提高了定位精確度，且沒有增加硬件成本。

采用CC1100 芯片測試兩節(jié)點(diǎn)之間的性能，CC1100是一款超低功耗UHF頻段無線收發(fā)芯片，為低功耗無線應(yīng)用而設(shè)計(jì)。在接收、傳輸模式下，傳輸速率為1.2kbps，在433MHz時(shí)，電流值為15.4mA，在實(shí)際應(yīng)用方面有一定的價(jià)值。

結(jié) 語

本文首先提出了在三維空間中適用于大規(guī)模網(wǎng)絡(luò)的節(jié)點(diǎn)定位算法，在空間中實(shí)現(xiàn)分簇，降低了通信量和復(fù)雜度，在使用較小能耗的同時(shí)實(shí)現(xiàn)對整個(gè)網(wǎng)絡(luò)的覆蓋。相比集中式算法而言，本文提出的分簇定位算法能夠在空間中最大發(fā)揮優(yōu)勢，避免了某些節(jié)點(diǎn)能量過早消耗完。本文還提出運(yùn)用3D-RSSI算法來實(shí)現(xiàn)對節(jié)點(diǎn)的精確定位，下一步將研究復(fù)雜環(huán)境下的分簇定位算法。

［1］李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京：北京理工大學(xué)出版社，2007.

［2］He T，Cheng D，Blum B M，et al.Rang-free localization schemes in large scale sensor network［C］／／Proceedings of the 9 th Annual International Conference on Mobile Computing and Net-working，MOBIHOC 2003.San Diego（CA，USA），2003.New York（NY，USA）：ACM Press，2003：81-95.

［3］Bal M，Liu M，Shen W，et al.Localization in cooperative wireless sensor networks：a review［C］／／The 13th IEEE International Conference on Computer Supported Cooperative Work in Design.Santiago，April 2009：22-24.

［4］King C，King S L，Vincent T.Localization in sensor networks with limited number of anchors and clustered placement［C］／／Proc.of the IEEE Wireless Communications and Networking Conference，2007：4425-4429.

［5］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，2005，16（5）：857-868.

［6］Miao Y，Cui L.A low complexity cluster localization method for wireless sensor network［J］.Chinese High Technology Letters，2009，19（4）：348-355.

［7］龍際珍，陳沅濤，鄧冬梅，等.基于LEACH 協(xié)議的助理簇首分簇算法［J］.計(jì)算機(jī)工程，2011，37（7），103-105.

［8］李剛，陳俊杰.基于信標(biāo)節(jié)點(diǎn)RSSI自校正的WSN 的三維定位［J］.華中科技大學(xué)學(xué)報(bào)，2011，39（11）：347-350.

［9］張愛清，葉新榮，胡海峰，等.基于RSSI每跳分級和跳距修正的DV-Hop改進(jìn)算法［J］.儀器儀表學(xué)報(bào)，2012，33（11）：2553-2559.