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

有效

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

1.基于Voronoi圖盲區的無線傳感器網絡節點覆蓋優化方法，其特征在于，該方法包括以下步驟：

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

(2)初始化算法的各個參數：傳感器節點數量N，感知半徑Rs，迭代次數itermax，離散化密度TD，按離散化密度TD將監測區域T離散化為a×b的目標點陣，通過rand函數隨機布置節點，生成傳感器節點初始位置，即無線傳感器節點的集合S，表示為S＝{s₁，s₂，…，s_N}；其中每個節點的位置記為s_i＝(x_i，y_i)；

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

(4)當前節點s_i與其鄰居節點集Z＝{z₁，z₂，…，z_n}共同組成節點集合K_i＝{s_i，z₁，z₂，…，z_n}，K_i對應的Voronoi單元集合V_k＝{v_i，v_z1，v_z2，…，v_zn}；計算當前節點s_i所對應v_i的頂點覆蓋情況；若頂點全部已覆蓋轉步驟(9)，若頂點未全部覆蓋進入下一步驟；

(5)計算當前節點s_i在v_i內的泰森盲區多邊形，并計算泰森盲區多邊形形心

(6)計算當前節點s_i在形心B_i處對v_i的覆蓋率

(7)計算當前節點s_i在當前位置(x_i，y_i)對v_i的覆蓋率

(8)比較覆蓋率和如果則更新節點位置使進入下一步驟，轉步驟(9)，否則保留當前節點位置s_i＝(x_i，y_i)進入下一步驟，轉步驟(9)；

(9)在K_i中去除s_i，重構K_i所對應的Voronoi單元集合并計算位于v_i內新產生Voronoi單元的頂點覆蓋情況；若頂點全部被覆蓋則v_i內不存在盲區，計算v_i的形心更新當前節點位置使進入下一步驟；若新頂點沒有全部被覆蓋則v_i內存在盲區轉步驟(5)；

(10)重復步驟(4)～步驟(9)，直至所有節點比較結束；

(11)重復步驟(3)～步驟(10)，直至滿足停止條件。

2.根據權利要求1所述的優化方法，其特征在于：鄰居節點為與當前傳感器節點共同形成與當前傳感器節點對應的Voronoi單元的傳感器節點。

3.根據權利要求1所述的優化方法，其特征在于：Voronoi圖是由相鄰傳感器節點連線形成的Delaunay三角網各邊做垂直平分線所組成的凸多邊形的集合，凸多邊形稱為Voronoi單元。

4.根據權利要求1所述的優化方法，其特征在于步驟(5)中的泰森盲區多邊形為去除Voronoi單元內的節點后,其已覆蓋頂點所對應的鄰居節點感知圓盤的交點集和未覆蓋頂點集，兩者共同所圍成的多邊形；若已覆蓋頂點為邊界點，則取對應鄰居節點感知圓盤與邊界的交點，所有交點均位于Voronoi單元內；具體可分為三種情況；

情況1：Voronoi單元的頂點全部被覆蓋，且存在盲區；取鄰居節點感知圓盤的交點圍成泰森盲區多邊形；

情況2：Voronoi單元的頂點部分已覆蓋，部分未覆蓋；去除Voronoi單元內的節點后，取Voronoi單元已覆蓋頂點所對應的鄰居節點感知圓盤的交點集和Voronoi單元未覆蓋頂點集圍成泰森盲區多邊形；

情況3：Voronoi單元頂點全部未被覆蓋時，泰森盲區多邊形與Voronoi單元相同。

5.根據權利要求1所述的優化方法，其特征在于：Voronoi單元內的盲區判斷方法為去除Voronoi單元內的傳感器節點，使用已去除傳感器節點的鄰居節點在監測區域內重新劃分Voronoi圖；會產生與鄰居節點個數相同的Voronoi單元，在原Voronoi單元內取出新產生Voronoi單元的頂點，并判斷覆蓋情況，若有未覆蓋頂點則存在盲區。