基于安全連接的WSN節點優化部署*

孫子文,申 棟(.江南大學物聯網工程學院,江蘇 無錫 2422;2.物聯網技術應用教育部工程研究中心,江蘇 無錫 2422)

無線傳感器網絡WSN(Wireless Sensor Network)正在改變著人類與物理世界的交互方式[1-3],在許多領域得到了廣泛的應用。在網絡部署初期,特別是在無人觸及或容易受損的環境中,保證網絡的安全性具有重要意義,網絡安全是無線傳感器網絡的首要研究問題之一。無線傳感器網絡節點覆蓋性能的好壞很大程度上決定了無線傳感器網絡的性能,直接體現網絡的感知、監視和通信等服務質量,同時還會影響網絡資源的管理,覆蓋算法的性能優劣同樣影響著網絡的生存期[4-5]。因此,在保證節點安全連接的前提下對無線傳感器網絡覆蓋性能優化的方案的研究具有至關重要的意義。

為了保證無線傳感器網絡初始部署節點間的安全通信,研究人員已經提出了一些無線傳感器網絡密鑰管理方案[6-8],但是此類方案初始部署以后節點往往沒法覆蓋整個無線傳感器網絡部署區域,因此需要進行節點覆蓋優化。文獻[9-10]針對二維部署區域的無線傳感器網絡覆蓋優化展開了基于泰森多邊形形心的部署方案的研究。文獻[9]提出了基于泰森(Voronoi)多邊形形心的部署方案CBS(Centroid-Based Scheme),引入了泰森多邊形形心的概念,將節點移動到泰森多邊形形心位置,提高了節點的覆蓋率,通過把整個網絡部署區域覆蓋優化的問題轉換為每個泰森多邊形區域的覆蓋優化問題,從而減小了計算復雜度,但是此方案沒有考慮鄰居節點的覆蓋影響,因而節點移動后會產生新的盲區。文獻[10]提出了一種基于泰森盲區多邊形形心的覆蓋控制部署方案BCBS(Blind-Zone Centroid-Based Scheme),將鄰居節點對泰森多邊形的覆蓋考慮進來,確保泰森多邊形的形心位于泰森多邊形盲區的中心位置,并構造與盲區位置相似的泰森多邊形,通過將無線傳感器網絡節點移動到泰森多邊形盲區中心位置來提高節點的覆蓋率,此方案雖然考慮了鄰居節點的影響,但是形心確定方法太復雜。

一些網絡優化部署方案在泰森多邊形優化覆蓋的基礎上,開始考慮結合虛擬力算法[11-13]。文獻[11]在泰森多邊形形心的優化策略基礎上,結合虛擬力算法,采用了Voronoi多邊形形心導向的虛擬力自部署的無線傳感器網絡部署策略,在考慮傳感器網絡節點的鄰居節點對其引力斥力的同時加入無線傳感器網絡節點所在的泰森多邊形形心的引力,提高了節點的覆蓋率,減小了節點的移動距離和能量的消耗;文獻[12-13]利用虛擬力算法采用未被無線傳感器網絡節點覆蓋的Voronoi圖頂點和Voronoi圖邊界對無線傳感器網絡節點為引力作用來引導共享密鑰來保證網絡節點間的安全連接,文獻[11-13]的方案雖然改善了無線傳感器網絡部署區域的覆蓋性能,但是節點移動提高節點覆蓋率時會破壞傳感器網絡節點之間已存在共享密鑰的安全連接。

針對目前無線傳感器網絡覆蓋優化方案沒有考慮節點之間已有的安全連接問題,本文采用基于泰森多邊形形心虛擬力和節點安全連接虛擬力的部署方案。該方案以節點覆蓋率為優化目標,結合無線傳感器網絡節點間的共享密鑰,引入安全連接虛擬力,減少了無線傳感器網絡覆蓋優化節點移動時對存在共享密鑰的鄰居節點的安全連接的破壞,以保證節點的安全連接;采用改進泰森多邊形形心虛擬力算法,能夠有效指導節點移動過程和實現全局優化,以提高節點覆蓋率。

1 WSN覆蓋模型

設在無線傳感器網絡二維平面部署區域T中,N個有相同感知半徑Rs和通信半徑Rc的無線傳感器網絡節點(以下簡稱節點)隨機部署在區域T內,設節點集為S={S1,S2,S3,…,SN},其中節點Si的位置坐標表示為(Sxi,Syi)。初始部署時,采用適當的無線傳感器網絡密鑰分配方案進行密鑰分配,使鄰居節點之間存在共享密鑰以建立安全連接。

將部署區域T離散化為m×n個目標點集T={T1,T2,T3,…,Tm×n},其中目標點Ti的位置坐標表示為(Txi,Tyi),則目標點Tj與節點Si的距離為:

(1)

節點Si對目標點Tj的感知概率P(Si,Tj)采用布爾感知模型[14-15]計算:

(2)

如果目標點Tj到節點Si的距離小于或者等于節點的感知半徑Rs,即d(Si,Tj)≤Rs,節點Si對目標點Tj的感知概率為1,即目標點被節點覆蓋;否則,節點Si對目標點Tj的感知概率為0,即目標點沒有被節點覆蓋。

對目標點Tj的聯合感知概率Ij是節點集對目標點Tj覆蓋率的并集,計算公式為:

(3)

只要目標點Tj被節點集S任意一個節點覆蓋,則對目標點的聯合感知概率為1,否則聯合感概率為0[16]。

假設所有目標點Tj的面積均為Δm×Δn,如果目標點被覆蓋,則目標點的聯合感知概率為1,覆蓋面積為Δm×Δn,否則為0,所以目標點Tj的覆蓋面積可表示為Ij×Δm×Δn;同樣可知,整個區域T的總面積為AS=(m×n)(Δm×Δn)。在網絡部署區域T中,節點部署后節點所覆蓋的面積占部署區域總面積的比值稱為節點覆蓋率ψ[17],計算如下:

(4)

式中:AT表示所有節點覆蓋的總面積,AS表示整個部署區域的總面積。

2 基于安全連接的形心導向虛擬力覆蓋方案

基于安全連接的形心導向虛擬力覆蓋方案主要分為兩個階段:節點虛擬力受力分析、節點移動過程。

2.1 節點虛擬力受力分析

虛擬力算法VFA(Virtual Force Algorithm)[18]最早應用于未知環境中的移動機器人實時避障的算法,Zou等人[18]首先將虛擬力算法應用于解決無線傳感器網絡覆蓋優化問題,其基本思想是將每個節點抽象為一個虛擬電荷,各節點受周圍其他節點力的作用為虛擬力。

基于虛擬力的原始定義,本文加以拓展,定義了4種類型的虛擬力:節點虛擬力、安全連接虛擬力、泰森多邊形形心虛擬力、Voronoi圖頂點虛擬力。前兩種虛擬力是節點受到來自其他實體節點的虛擬力,后兩種虛擬力是節點受到來自其他虛擬節點的虛擬力。

2.1.1 節點虛擬力

節點之間的虛擬力用式(5)描述:

(5)

圖1 節點虛擬力

2.1.2 安全連接虛擬力

(6)

2.1.3 泰森多邊形形心虛擬力

①泰森多邊形的劃分

在無線傳感器網絡部署區域中,對部署區域進行Delaunay三角剖分,節點連線形成Delaunay三角網,如圖2所示。

圖2 Delaunay三角網

圖3 Voronoi圖

對每個Delaunay三角形每條邊作垂直平分線,各條垂直平分線與部署區域邊界圍成的凸多邊形稱為泰森多邊形,即圖3中凸多邊形D1D2D3D4D5是其中一個泰森多邊形。泰森多邊形構成的網狀圖則稱為Voronoi圖,即圖3中虛線與部署區域邊界構成的網狀圖稱為Voronoi圖。

②泰森多邊形形心

形心取截面圖形的幾何中心,對于密度均勻的實物體,質心和形心重合。n條邊頂點為(Vixi,Viyi)的泰森多邊形形心(Cix,Ciy)的計算公式為[11]:

(7)

式中:AVi表示泰森多邊形的面積,其計算公式為:

(8)

③節點的形心虛擬力

圖4 泰森多邊形形心引力

(9)

2.1.4 Voronoi圖頂點虛擬力

部署區域進行Voronoi圖劃分之后,可能出現未被節點覆蓋的Voronoi圖頂點,如圖5所示,Voronoi圖頂點D1,D5沒有被任何節點覆蓋。

圖5 Voronoi圖頂點虛擬力

(10)

2.1.5 節點綜合受力分析

(11)

(12)

2.2 節點的移動過程

(13)

(14)

2.3 覆蓋方案流程圖

通過節點虛擬力受力分析,以及節點移動兩個階段,節點到達部署位置。基于安全連接的形心導向虛擬力覆蓋優化方案的流程圖如圖6所示。

圖6 基于安全連接的形心導向虛擬力覆蓋方案流程圖

具體算法描述如下:

①將部署區域T劃分為若干個泰森多邊形,泰森多邊形集合為V={V1,V2,V3,…,VN},泰森多邊形形心集合C={C1,C2,C3,…,CN},根據式(7)和式(8)計Voronoi多邊形形心位置集合為{(C1x,C1y),(C2x,C2y),…,(CNx,CNy)};

②計算節點Si與存在共享密鑰的鄰居節點、Vi形心、未被覆蓋的Voronoi多邊形頂點、無共享密鑰鄰居節點的距離;

⑤計算節點Si位置更新后的覆蓋率為ψ,如果覆蓋率達到要求,節點停止移動,否則重復步驟①～步驟④。

3 仿真實驗與結果分析

為研究該方案的有效性,對該方案進行了仿真實驗,并與文獻[9]方案與文獻[12]方案的性能進行了對比。

3.1 仿真環境及參數設置

仿真采用MATLAB 2014a進行,仿真實驗所涉及的參數如表1所示。

表1 仿真實驗參數

圖7 正三角形部署

3.2 仿真結果及分析

3.2.1 存在共享密鑰節點的安全連接

假設在無線傳感器網絡初始部署時,每一對鄰居節點都會存在共享密鑰,能夠建立安全的通信連接。在修復初始部署的覆蓋空洞移動節點過程中,可能會破壞這些已經存在共享密鑰的安全連接,仿真的目的是比較安全連接的破壞程度。初始部署以及每個方案節點位置更新100次以后存在共享密鑰節點的安全連接的仿真結果如圖8所示。

圖8 安全連接比較圖

由仿真結果圖8所示,圖8中的連線表示節點之間存在共享密鑰的安全連接,節點位置更新100次后所有方案的安全連接都會減少的,具體存在共享密鑰節點的安全連接個數如表2所示。節點初始部署時,節點間有共享密鑰的安全連接的個數為251個,節點位置更新100次以后,本文方案存在236個安全連接,而文獻[9,12]分別存在178、186個安全連接,可見,與文獻[9]方案和文獻[12]方案相比,本文方案節點移動對安全連接的破壞減少。

表2 存在共享密鑰節點的安全連接個數

3.2.1 節點的覆蓋率

提高節點的覆蓋率是無線傳感器網絡覆蓋優化的目標,直接關系到網絡的覆蓋質量。網絡初始部署以及每種方案節點移動100次后的覆蓋情況和覆蓋率仿真結果如圖9和圖10所示。

圖10 節點覆蓋率

由圖9可知,與節點的初始部署相比,可知每種方案在節點移動100次以后,節點分布更加均勻。由圖10可知,節點的覆蓋率都是隨著位置更新次數的增加而增大,本文方案與文獻[9]方案和文獻[12]方案相比在節點位置更新相同的次數時有更高的節點覆蓋率。初始部署時,節點的覆蓋率為72.64%,在節點位置更新100次以后,本文方案的節點覆蓋率提高到98.81%,文獻[9]方案和文獻[12]方案的節點覆蓋率分別為97.57%和96.53%。

圖9 節點覆蓋情況比較

4 結束語

本文設計的基于泰森多邊形形心引力和節點安全連接引力的虛擬力的部署方案,通過引入鄰居節點存在共享密鑰的安全連接虛擬力減小節點安全連接被破壞,同時泰森多邊形形心虛擬力、泰森多邊形頂點虛擬力、節點虛擬力能夠有效指導節點移動過程,提高無線傳感器網絡覆蓋率。