[發明專利]基于Voronoi圖盲區的無線傳感器網絡節點覆蓋優化方法

有效

• 申請號: 201410282586.5
• 申請日: 2014-06-23
• 公開（公告）號: CN104159236B
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 方偉;宋鑫宏;姜淑琴;吳小俊;孫俊
• 申請（專利權）人: 江南大學
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W24/02;H04W84/18
• 代理公司: 北京愛普納杰專利代理事務所(特殊普通合伙)11419
• 代理人: 何自剛,王玉松

技術領域：

本發明涉及無線傳感器網絡技術領域的覆蓋優化方法，具體涉及一種基于Voronoi圖的無線傳感器網絡節點覆蓋控制的優化方法。

背景技術：

無線傳感器網絡(Wireless SensorNetworks，WSNs)是由大量被部署在監測區域，靜止或移動的，具有感知能力、計算能力和通信能力的傳感器節點所組成的多跳自組織網絡。這些傳感器節點能夠實時感知、采集和處理用戶所需的信息，采用無線傳輸的方式將處理后的信息送到用戶終端。WSN涉及微機電系統(MEMS)、集成電路(IC)、無線通信和低功耗嵌入式等多個學科領域。以其低功耗、低成本、分布式和自組織的特點帶來了一場信息感知的變革。

許多情況下無線傳感器網絡在人員無法到達的惡劣環境下工作，此時傳感器節點只能被隨機拋撒在監測區域，如采用飛行器進行拋撒投放。初次隨機拋撒的傳感器位置分布不均勻，極易出現盲區無法保證監測區域的覆蓋率和確保網絡的連通性，需移動節點進行二次部署調整節點分布的均勻性從而提升無線傳感器網絡的覆蓋率和連通性。

目前無線傳感器網絡節點覆蓋優化方法可以分為三類，虛擬力算法，群體智能算法和計算幾何算法。

優化方法1：在公開號為CN101051973的中國專利申請中，提出了一種基于虛擬力的移動無線傳感器網絡節點布局方法。其主要思路為：無線傳感器網絡工作環境中的各類對象(包括待探測目標、障礙地形、待探測熱點區域、傳感器)均會對傳感器產生虛擬的引力與斥力作用。計算傳感器節點受到虛擬力的大小和方向并使傳感器做相應移動，從而使傳感器節點均勻擴散提升覆蓋率。

優化方法2：在公開號CN101448267的中國專利申請中，提出了一種基于離散二進制的粒子群優化算法的覆蓋機制。將傳統PSO算法的粒子位置編碼方式改變為二進制編碼，二進制的長度等于所有的傳感器數量N。定義“覆蓋率”和“消耗率”兩個適應度函數，使用PSO算法的進化機制對其進行優化。

上述優化方法1與優化方法2的缺陷為：涉及權重參數的選擇。

Voronoi圖是一種解決覆蓋控制問題的有效方法，Voronoi圖中的Voronoi單元與目標點的覆蓋情況存在對應關系可以有效確定盲區位置。對應關系有三種。

關系1：某Voronoi單元內的目標點到相應傳感器節點的距離最近。若目標點被覆蓋，則一定被該Voronoi單元內的傳感器節點覆蓋。若該Voronoi單元內的節點未覆蓋目標點，則該目標點處存在盲區。

關系2：某Voronoi單元各邊上的目標點至與其共邊的Voronoi單元內的節點的距離相等。若目標點被覆蓋，則一定被共邊的兩個Voronoi單元內的節點同時覆蓋。若這兩個節點未覆蓋目標點，則該目標點處存在盲區。

關系3：某Voronoi單元至共點的三個Voronoi單元內的節點的距離相等。若頂點被覆蓋，則一定被共點的三個Voronoi單元內的節點同時覆蓋。若這三個節點未覆蓋頂點，則該頂點處存在盲區。

發明內容：

本發明的目的在于針對無線傳感器覆蓋優化問題，提出一種Voronoi圖盲區的無線傳感器網絡節點覆蓋優化方法，本發明的基本步驟包括：

(1)在L×W的監測區域T內隨機散布N個感知半徑為R_s的無線傳感器；

(2)初始化算法的各個參數(傳感器節點數量N，感知半徑R_s，迭代次數itermax，離散化密度TD)。

N＝L_T×w_T

其中ceil表示正無窮方向取整，floor表示負無窮方向取整，rem表示取余數；

按離散化密度TD將監測區域T離散化為a×b的目標點陣，每個目標點的位置記為t_j＝(x_j,y_j),通過rand函數隨機布置節點，生成傳感器節點初始位置，即無線傳感器節點的集合S，表示為S＝{s₁,s₂,…,s_N}；其中每個節點的位置記為s_i＝(x_i,y_i)。

(3)對監測區域T進行Voronoi圖劃分，Voronoi單元的集合為V＝{v₁,v₂,···,v_N}。