基于網格劃分的傳感器網絡定位方法的研究

(河南工業大學 人工智能研究所 鄭州 450001)

摘 要：根據實際工程提出一種基于網格劃分的糧庫壓力傳感器網絡布置模型。該方法根據淺圓倉糧庫底部壓力場特點進行了區域劃分及網格劃分密度控制函數的設定，然后對不同區域進行網格劃分，在網格化后的倉底進行了傳感器節點布置。對比文獻中提出的幾種模型，該模型既保證了傳感器區域無盲區即實現了完全無縫覆蓋，又使其所使用的傳感器數量最少，監測精度最高。

關鍵詞：網格劃分； 傳感器網絡； 控制函數

中圖分類號：TP341文獻標志碼：A

文章編號：1001-3695(2009)05-1685-02

Research of localization mode for wireless sensor networks

based on grid partition

CHEN Demin ZHANG Yuan

(Artificial Intelligence Institute Henan University of Technology Zhengzhou 450001 China)

Abstract:According to a practical project this paper presented a gridbased grain storage pressure sensor networks layout model. From pressure characteristics of the grain bottom，set the mesh density control function and partitioned the region disposed the pressure sensor nodes with triangulation method. Compared several models in literatures this model can ensure that there are no blind spots in sensor region that is completely seamless coverage and it can make use of the least number of sensors to get the highest accuracy monitoring.

Key words：grid partition; sensor network; control function

由于糧倉在儲糧過程中，糧食受流動速度、高度等因素的影響，糧堆分布不均，顆粒體堆積時底面壓力分布與堆積過程密切相關。鑒于糧倉糧堆的復雜性，糧庫儲糧數量很難直接測量得到。本文提出一種傳感器部署模型，通過在糧庫底部布置壓力傳感器來監測儲糧數量。

傳感器布置有確定性的和自組織^[1]兩種形式。對于前者，傳感器手動放置且數據按預定的路徑進行路由;對于后者，傳感器節點隨機分布并以Ad hoc方式進行組織^[2]。文獻[3]中提出了基于正方形模型；文獻[4]中提出了基于正三角形模型，這兩種方法均有很好的覆蓋性和連通性，都屬于均勻布置；文獻[5]提出了基于虛擬力的移動傳感器布置算法(virtual force algorithm，VFA)。該方法綜合了勢場和盤包的概念，但VFA沒有解決盲區^[6]的問題模型。上述模型都是在理論上進行分析，在實際工程應用中，這些模型有很大的局限性。在針對本文提到的糧庫中，由于糧堆底部力場的復雜性，這些模型實用性很差。

本文提出一種基于真實糧庫壓力場的傳感器布置模型。該方法將確定性布置和自組織布置兩種方式相結合，運用Delaunay三角化方法和前沿生成法^[7，8]對傳感器節點進行布置，這與目前提出的幾種布置方式有明顯的不同。該模型是結合實際工程中所提出的，既能保證在傳感器區域無盲區即實現了完全無縫覆蓋^[9]，又使得所使用的傳感器數量最少，監測精度較高。大量實驗顯示該模型具有很高的可靠性和適用性。

1 糧堆底部力場特點

文獻[10]中，顆粒堆由外部集中荷載力引起的內力傳遞，在顆粒堆內部的傳遞形成一個力網。顆粒堆的拱效應和由拱效應引起的力分布的雙峰現象。文獻[11]中，在力的作用下，基底各部分發生不均勻沉降，基底中部的顆粒沉降很大，兩側較小。這種沉降引起底層邊側的顆粒發生偏轉，使得顆粒堆的邊側顆粒與中部顆粒形成一個拱形結構。如圖1所示，通過實際實驗發現，B點壓力大于C點和A點。

根據文獻及實驗得知：淺圓糧倉中不出現糧倉效應^[12]；糧堆壓力場可有近似于中心對稱的無數等壓曲線表示，如圖2所示；壓力最大的區域處于中心與邊緣之間。圖2中p1、 p2為壓強。

2 糧庫壓力場網格劃分

2.1 區域劃分

根據淺圓倉中糧堆底部壓力場特點，將糧倉底部區域劃分成三部分，如圖3所示。以O為圓心，R1、R2、R3為半徑畫圓。區域1為中心圓內部，區域2為中間環形帶，區域3為外環形帶。圖1中的C、B、A點就分別落在區域1、2、3內。在區域2內的糧堆底部壓力大于區域1、3內的。

2.2 邊界離散

對于任意的幾何造型系統，一般都提供區域的邊界表述功能，每一個目標實體只有惟一的邊界表述，可通過邊界表述中的拓撲要素來定義網格疏密度的控制信息。對于本文實體糧倉，三個圓即為劃分3區域的邊界線。將邊界線展開，設A、B是邊界線的兩個端點，d(x0)是所要求的網格劃分尺寸。邊界離散就是應該如何在糧倉邊界線上布置節點，才使得在邊界線上節點按要求分布。d(xi)是第i個節點到第i+1個節點間的距離。ρ(x)為邊界線上的節點間距函數，它表示該點的網格尺寸，網格尺寸按函數ρ（x)變化。根據淺圓倉底部壓力場的對稱性，取ρ(xi)=d(x0)，N=(c/d(x0))-1。其中：N為邊界節點總數；c為邊界線長。

2.3 區域內網格控制函數

為了對x′y′坐標系中的不規則區域Ω′進行網格劃分，先將不規則區域Ω′按保角映射原理變換到新的xy坐標系中形成規則矩形區域Ω，如圖4所示。對區域Ω進行網格劃分得到的網格對應每個網格節點可以在x′y′坐標系Ω′中找到相應的位置。

邊界離散后，引入區域內節點間距函數ρ(x，y)控制區域內部網格的疏密過渡。g(xi)為內部節點i到其相鄰左邊節點的距離，在同一水平方向上相鄰節點間距離相同。在豎直方向上每層節點間距離由h(yi)函數控制，成線性變化。ρ(x，y)描述區域內任意點網格尺寸的控制信息。

ρ(x，y)=F(g(xi)，h(yi))g(xi)=log10(（2-x）/2)+x10

h(yi)=d(y0)-(h/d(y0)-d(yn))yx∈[0，2(1-10x20-x10)]，y∈[0，(d(y0)-d(yn)2)/h]



當x=0時，g(x0)=d(x10)；當x=2(1-10x20-x10)時，g(xn)=d(x20)；當y=0時，h(y0)=d(y0)；當y=(d(y0)-d(yn))2/h時，h(yn)=d(yn)。

2.4 節點生成

引入節點間距函數后，用內部節點與三角形同時生成的前沿生成法來生成Delaunay三角形。初始前沿為已離散的區域邊界，記為非Delaunay邊，優先考慮最長邊，并盡可能地保證新生成的邊長度不斷減小，以實現從大到小的過渡。具體步驟如下:

a）從邊界AB、AD開始，連接該邊上的第一個節點，構成三角形AEF。

b）在EF邊右下方取一點H，使得H點滿足控制函數ρ(x，y)，將點H插入節點隊列，H點到邊界AB的距離為h(y1)=d(y0)，H點到AD邊界距離為g(x1)=log10((2-k)/2)+x10。

c）連接AH。將兩個具有共同邊的三角形合成一個多邊形AEHF，以最大空圓準則作檢查，看其第四個頂點是否在三角形的外接圓之內。如果在，修正對角線即將對角線對調，即完成局部優化過程的處理。如圖5所示，刪除EF邊，此時生成Delaunay三角形AEH和AHF。將形成的三角形放入Delaunay三角形鏈表。

d）同理，生成M節點和Delaunay三角形網格MNE和MHE。M到AB邊界的距離為h(y1)=d(y0)，M點到其前一節點H的距離為g(x1)=log10((2-x)/2)+x10。

e）連接TH，在TH邊右下方取一點K，使得K點滿足控制函數ρ(x，y)。K點到邊FH的距離為h(y2)=d(y0)-(h/d(y0)-d(yn))y，K點到AD邊界距離為g(x2)=log10((2-x)/2)+x10。

f）同理，通過修正對角線即將對角線對調，完成局部優化過程的處理，生成Delaunay三角網格KHF和KTF。將形成的三角形放入Delaunay三角形鏈表。

g）依次以相鄰左上方兩節點為參考點，根據網格控制函數逐步生成下一個節點，把生成的節點依次插入隊列；以最大空圓準則修正對角線，刪除不符合的邊，完成局部優化，將形成的三角形放入Delaunay三角形鏈表，形成Delaunay三角形網格。

h）循環執行g)直到滿足下列條件：

ρ(x，y)=F(g(xi)，h(yi))g(xn)≤d(x20)h(yn)≤d(yn)

結束循環。

3 基于網格劃分的糧庫壓力傳感器網絡模型

按照糧庫壓力場分布特點，把傳感器區域分成一個個的Delaunay三角形網格。圖6給出了基于Delaunay三角網格劃分的傳感器節點布置模型。此布置方式使每個傳感器節點位于Delaunay三角形網格的頂點上。在糧堆形成的壓力場中，區域2壓力大于區域1和3，劃分網格時，受力大的區域網格密度大，故傳感器節點數量也多。此模型既能保證在傳感器區域無盲區即實現了完全無縫覆蓋，又使得所使用的傳感器數量最少，而監測精度較高。

4 實驗方法及結果分析

本實驗選用淺圓倉模型：直徑D=500 mm，高度H=900 mm，倉壁厚度t=5 mm；材料為有機玻璃，底部用混凝土澆筑；采用C30號混凝土，厚度120 mm，直徑800 mm的底座。

在利用相同數量的傳感器條件下，通過傳感器節點的不同布置對淺圓倉模型底部壓力進行了實測，結果發現采用本文提出的傳感器網絡模型監測淺圓倉底部壓力，其精度比文獻[3~5]中提出的都高。實驗結果對比如圖7所示。