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

劉曉鑫，方旺盛，張永建

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

引 言

隨著無線傳感器網絡（WSN）的發展，節點定位技術已經滲入到生活的各個方面，無線傳感器網絡之間的協作能夠進行目標跟蹤、井下定位、緊急求救、森林火災等［1-2］。

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

在大規模無線傳感網絡中，由于不斷迭代，以至于最后的節點位置出現較大的誤差，所以本文提出分簇算法的節點定位算法，在各分簇中把誤差降低到最低，然后從sink節點開始把各簇的位置的節點合并，最后完成全局節點的定位。在定位算法方面考慮到算法復雜度、成本等，本文選取基于RSSI的定位算法。RSSI節點定位方法通過接收錨節點上的功率，計算傳播功耗，利用理論將RSSI強度轉化為距離，利用最小二乘法估計未知節點位置坐標。但在計算過程中不斷疊加的誤差，使得整個網絡的節點定位誤差增大。故本文從減少通信開支、降低成本和節能角度提出了一種基于分簇的3D-RSSI的定位算法，首先確定各簇內的簇首，簇首內保存著各簇的拓撲結構，各簇內節點之間的距離通過接收到的信號強度來確定，隨后從sink節點開始融合各簇間的未知的位置，來實現整個網絡的定位。

1 本文分簇算法

1.1 LEACH協議

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

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

其中，p 為期望的簇首節點中的百分比；r是當前輪數；r mod（1／p）代表這一輪循環中當選過簇首節點的個數，G是在最后的1／p輪中未成為簇首節點的節點集；T（n）實際上是在第r輪尚未成為簇首節點的節點成為簇首的平均概率。

1.2 基于節點勢的分簇算法

對LEACH 協議作簡要的改進，分簇過程從位于網路中心的sink節點開始，首先以sink節點作為其中一個簇首，簇內節點依次按規則尋找臨近節點，直到找到對應的簇首。簇從sink節點逐漸向網絡各個方向擴展，直到整個網路被覆蓋。尋找相鄰簇首的具體規則如圖1所示。

2 信號模型

2.1 RSSI無線信號傳輸模型

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

圖1 節點尋找簇首流程圖

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

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

在實際環境中，由于存在多徑效應及噪聲的干擾，接收端收到的功率和自由空間傳播模型的計算結果存在較大誤差，利用如下對數損耗模型對其進行修正：

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

2.2 三維RSSI定位模型

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

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

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

3 仿真與分析

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

定位誤差在無線傳感器網絡中是判斷定位算法的重要指標，首先仿真研究錨節點個數與平均定位誤差的關系，路徑耗散指數n取4，通信半徑為60m，信標節點由開始的100（30%）個，每次仿真增加40 個，直至達到300（30%）個，實驗仿真表明，如圖2～圖5所示，平均定位誤差隨著錨節點數量的增加而遞減。由此可證本文分簇3D-RSSI模型優于經典3D-RSSI算法。

覆蓋率也是判斷定位誤差的重要參數。實驗仿真表明，覆蓋率隨著錨節點數量而增大，由此可以推斷在大規模無線傳感網絡中，分簇算法不僅平均誤差減小了，而且也提高了覆蓋率。

圖2 錨節點數量與平均定位誤差關系

圖3 錨節點數量與定位覆蓋率關系

圖4 分簇空間節點的定位效果圖

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

圖5 整個網絡的節點定位效果圖

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

采用CC1100 芯片測試兩節點之間的性能，CC1100是一款超低功耗UHF頻段無線收發芯片，為低功耗無線應用而設計。在接收、傳輸模式下，傳輸速率為1.2kbps，在433MHz時，電流值為15.4mA，在實際應用方面有一定的價值。

結 語

本文首先提出了在三維空間中適用于大規模網絡的節點定位算法，在空間中實現分簇，降低了通信量和復雜度，在使用較小能耗的同時實現對整個網絡的覆蓋。相比集中式算法而言，本文提出的分簇定位算法能夠在空間中最大發揮優勢，避免了某些節點能量過早消耗完。本文還提出運用3D-RSSI算法來實現對節點的精確定位，下一步將研究復雜環境下的分簇定位算法。

［1］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京：北京理工大學出版社，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］王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，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 協議的助理簇首分簇算法［J］.計算機工程，2011，37（7），103-105.

［8］李剛，陳俊杰.基于信標節點RSSI自校正的WSN 的三維定位［J］.華中科技大學學報，2011，39（11）：347-350.

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