基于礦井三維WSNs多重覆蓋和RSSI的加權質心算法

方旺盛，雷高祥，李　寧

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

基于礦井三維WSNs多重覆蓋和RSSI的加權質心算法

方旺盛，雷高祥，李寧

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

摘要:針對無線傳感器網絡(WSNs)的礦井災害無線監測信息系統，提出一種基于礦井三維建模WSNs多重覆蓋和RSSI的加權質心定位算法。根據礦井巷道的幾何結構特征，將礦井建模成規則的拱型模型。介紹了一種礦井巷道固定節點無縫覆蓋部署模型，并運用幾何學求出了滿足多重覆蓋要求時的節點部署間距。在此基礎上，提出了一種基于RSSI比值的加權質心定位算法，利用節點RSSI值求出加權系數,再對質心坐標進行加權處理。仿真實驗表明:改進的質心算法有效地減少了定位誤差，定位精度優于原算法。

關鍵詞：無線傳感器網絡;多重覆蓋；接收信號強度指示；加權系數；質心定位

0引言

無線傳感器網絡(WSNs)逐漸成為工業控制，環境監測和人類生命救援等信息基礎設施的關鍵技術之一，特別是,對于環境復雜的礦井巷道而言，建立礦井災害監測監控系統、人員定位系統等對監測區域實施有效的監測非常重要。

無線傳感器網絡具有可移動、低功耗、低成本、可靠性高、易于安裝和維護等優點，可根據礦井巷道的幾何結構布置傳感器節點，達到對巷道區域的無縫覆蓋[1～3]，實現高效監測。傳感器網絡定位技術可以及時收集施工人員數量和位置信息，為礦井安全生產和災后的人員營救提供了可靠的保障。章堅武,張璐等人[4]和喬鋼柱,曾建潮等人[5]提出了利用RSSI來對目標進行定位,硬件開銷低，定位過程相對簡單，但由于礦井巷道的復雜環境,定位精度較低；韓東升,楊維等人[6]提出的動態獲取路徑損耗指數的加權質心算法減少了定位誤差，并且算法復雜度低；周公博，朱真才等人[7]提出了一種固定節點確定性部署的拓撲控制模型，節點按直線方式部署在巷道側壁，實現了巷道區域的多重覆蓋。

本文根據礦井巷道的幾何結構，利用抽象幾何數學將礦井巷道建模成規則的圖形，并且提出了一種固定節點無縫覆蓋部署模式。根據節點的部署特征，提出了一種改進的質心定位算法，基本原理是利用節點的RSSI值計算出加權系數，然后再對質心坐標進行加權，并且提出的改進算法能夠有效減少定位誤差。

1系統模型

1.1覆蓋模型

節點感知模型采用0～1布爾感知模型[8],感知區域是以節點為球心，rs為感知半徑的球。當兩個傳感器節點的歐氏距離d(i,j)小于rs時，表示節點間能夠直接通信，輸出事件概率為1；反之，則輸出事件概率為0，即

(1)

式中p(i,j)為節點i對事件j的監測概率，d(i,j)為節點i到事件j的歐氏距離。

1.2RSSI測距

根據對數—常態分布模型[9，10]可以計算出距離節點d處的平均接收功率PL(d)，如下式

(2)

左右兩邊取對數

(3)

引入一均值為0的高斯分布ε

(4)

式中距離d處的RSSI值為[PL(d)]dB，dBm；路徑損耗系數為n，一般取2～4，PL(d0)為參考距離1 m處的RSSI。

2節點部署策略

礦井巷道中的無線傳感器網絡節點基本上都按照實際需要布設在巷道內壁上，并且礦井巷道的截面主要劃分為拱形、圓形、矩形。本文對一段巷道進行研究，將礦井巷道建模成三維空間的拱形模型如圖1所示。假設傳感器節點通信范圍為rc，感知范圍為rs,h為隧道側壁的高度,w為隧道的寬度，h1為巷道頂端到地面的高度，且網絡中所有節點具有相同的通信和感測范圍。

為使礦井巷道整個區域實現感知無縫覆蓋，先求出傳感器節點的最小感知半徑。如圖2為巷道截面節點部署方式，A點為傳感器部署位置,則傳感器節點的最小感知半徑為

(5)

在最小感知半徑情況下，傳感器節點按圖3部署方式實現一段礦井巷道的無縫覆蓋,C點在以O1為球心，R1為半徑的球面上，即為節點O1在底邊CD上的最遠感知點，同理，在BE邊上的最遠感知點為E，在O1A上的最遠感知點為A，那么相鄰切面上的傳感器的感知范圍必須至少覆蓋A,C,E點。由幾何關系知:△O2CD≌△O1BC，CD=BC=w，其中,O1A=R1，BE=w。點E在節點O2的最遠覆蓋距離，由對稱性可知，BE=CD=w。當節點感知半徑rs≥R1時，巷道俯視圖如圖4所示，其中，弧面BNM為節點O1與巷道底面的相交面，弧面DMN為節點O2與巷道底面的相交面。

圖3　信標節點部署方式Fig 3　Deployment mode of beacon node

圖4　巷道俯視圖Fig 4　Top view of roadway

在圖4中，根據幾何關系有

(6)

(7)

則當單重覆蓋相鄰切面之間的最大水平距離為

(8)

依次在間隔dmax1的橫切面上部署節點，就能實現礦井一段巷道中橫截面單個節點側壁布局的單重無縫覆蓋。

礦井巷道所需信標節點數為

(9)

式中ceil為向上取整數，L為巷道長度。

3基于RSSI值的加權質心定位算法

3.1傳統的質心算法

傳統的質心定位算法[11～13]的一般過程為：信標節點周期性地向鄰居節點廣播自身坐標位置分組信息，當待定位節點收到來自不同信標節點的信標分組數量超過某一個門限N或接收一定時間后，則節點的估計位置計算公式如下

(10)

式中(X,Y)為待定位節點的坐標，(xi,yi)(i=1,2,…N)為待定位節點所接收到的信標節點坐標。

3.2改進的質心定位算法

(11)

再求出待定位節點收到的RSSI中最大值RSSImax和最小值RSSImin以及兩者平均值：

RSSImax=max[RSSI1,RSSI2,…,RSSIi]

(12)

RSSImin=min[RSSI1,RSSI2,…,RSSIi]

(13)

(14)

(15)

(16)

根據權值wi與信標節點的坐標求出待定位節點的估計坐標

(17)

(18)

圖5　算法原理圖Fig 5　Principle diagram of algorithm

詳細的定位過程如下：

1)信標節點周期性地廣播數據包，數據包中包括節點ID和自身的位置坐標。

3)利用步驟(2)求出的比例因子得到每一個信標節點的加權系數wi,根據式(17)和式(18)計算出未知節點坐標。

4仿真實驗

圖6　礦井巷道傳感器節點分布圖Fig 6　Sensor node deployment of roadway of mine

節點的定位誤差定義為

(19)

式中(xi,yi)為節點的實際坐標，(xj,yj)為算法中估計出的坐標位置。所有待定位節點的平均定位誤差定義為

(20)

式中N為未知節點的個數。

通過部分數據定量分析改進算法的相對定位誤差，表1列出了在通信半徑為R=30 m，信標節點與節點總數比例不同時，兩種定位算法的相對定位誤差。表2列出了在錨節點比例為40 %，通信半徑不同時，兩種算法的相對定位誤差。

表1　相對定位誤差隨錨節點比例變化(R=30 m)

如圖7所示為節點通信半徑分別為30 m和25 m時,兩種算法的相對定位誤差隨信標節點比例變化的仿真結果。

表2　相對定位誤差隨通信半徑的變化關系

在同一實驗環境下，信標節點的比例從20 %變化到60 %時，改進的質心算法的相對定位誤差較傳統質心算法大約降低了10 %；圖8表示信標節點比例分別為30 % 和40 %時，通信半徑從20 m變化到40 m時，兩種算法的相對定位誤差變化曲線。由圖可知：本文的加權質心定位算法誤差大約減少了9.8 %。

圖9表示未知節點數為28個，信標節點數為12個，路徑損耗系數為4時，兩種算法的絕對定位誤差累計概率分布。由圖可知改進的質心算法相對定位誤差落在4 m以內的概率約為68 %，而傳統的質心算法約為50 %。

圖7　不同信標節點比例的相對定位誤差Fig 7　Relative localization error of different beacon node ratio

圖8　不同通信半徑的相對定位誤差比較圖Fig 8　Relative localization error of different communication radius

圖9　絕對定位誤差的累計概率分布Fig 9　Accumulative probability distribution of absolute localization error

5結論

本文建立了一種比較安全的礦井巷道監測模型，并且在此模型的基礎上提出了基于RSSI比值的加權質心定位算法。利用節點的RSSI值，求出待定位節點所接收到的RSSI值的均值和最大最小值，然后再利用這幾個RSSI求解加權系數對待定位節點進行加權處理。仿真實驗表明，改進的質心算法的定位精度優于原質心算法。

參考文獻:

[1]Bai X,Xuan D,Yun Z,et al.Complete optimal deployment patterns for full-coverage and k-connectivity(k≤6)wireless sensor networks[C]∥Proc ACM MobiHoc’08:2008.

[2]Wu Di,Bao Lichun,Li Renfa.A holistic approach to wireless sensor network routing in underground tunnel environments[J].Computer Communications,2010,33(13):1566-1573.

[3]郭秀明，趙春江，楊信廷,等.基于網格掃描的實現目標點覆蓋的確定性傳感器節點部署方法[J].傳感器技術學報，2012，25(1)：104-109．

[4]章堅武,張璐,應瑛,等.基于ZigBee的RSSI測距研究[J].傳感技術學報,2009,22(2):285-288.

[5]喬鋼柱,曾建潮.信標節點鏈式部署的井下無線傳感器網絡定位算法[J].煤炭學報,2010,35(7):1229-1233.

[6]韓東升,楊維,劉洋,等.煤礦井下基于RSSI的加權質心定位算法[J].煤炭學報,2013,38(3):522-528.

[7]周公博，朱真才，陳光柱,等．礦井巷道無線傳感器網絡分層拓撲控制策略[J].煤炭學報,2010,35(2):333-337．

[8]Akkaya K,Newell A.Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks[J].Computer Communications,2009,32:1233-1244.

[9]占宏,黎善斌,胥布工.基于WSNs中距離函數和指數函數的三維質心定位算法[J].傳感器與微系統,2011,30(5):136-138.

[10] 丁恩杰,喬欣,常飛,等.基于RSSI的WSNs加權質心定位算法的改進術[J].傳感器與微系統，2014,32(7):53-56.

[11] Bulusu N,Heidemann J,Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications,2000,7(5):28-34.

[12] 呂振，譚鵬立．一種基于RSSI校正的三角形質心定位算法[J].傳感器與微系統,2010，29(5)：122-123．

[13] Zhang Honghai,Hou Jennifer C.Maintaining sensing coverage and connectivity in large sensor networks[J].Journal of Ad Hoc and Sensor Wireless Networks,2005,1(1-2):89-124．

Weighted centroid algorithm for WSNs based on multiple coverage under three-dimensional modeling of mine and RSSI

FANG Wang-sheng,LEI Gao-xiang,LI Ning

(Faculty of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China)

Abstract:A weighted centroid location algorithm based on multiple coverage under three-dimensional modeling of mine and RSSI is proposed for underground mine disaster monitoring system which based on WSNs.Model underground tunnel as an arched shape according to geometric structure property of mine channel.A deployment model for seamless coverage of fixed node is presented,meanwhile,distance of node deployment to meet requirement of nodes multiple coverage is further figured out.Besides,a weighted centroid location algorithm based on RSSI ratio is presented and use RSSI value to address weighting factor and weighting centroid coordinates.Simulation show that the improved centroid algorithm reduces positioning error and achieves better positioning precision.

Key words:WSNs;multiple coverage;received signal strength indication(RSSI);weighting factor;centroid location

DOI:10.13873/J.1000—9787(2016)05—0128—04

收稿日期：2016—03—14

中圖分類號：TP 393

文獻標識碼：A

文章編號：1000—9787(2016)05—0128—04

作者簡介:

方旺盛(1963-)，男，江西上饒人，碩士研究生導師，主要研究方向為無線傳感器網絡、數字水印、基因表達式編程。