基于安全連接的WSN節(jié)點優(yōu)化部署*

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

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

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

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

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

1 WSN覆蓋模型

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

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

(1)

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

(2)

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

對目標點Tj的聯(lián)合感知概率Ij是節(jié)點集對目標點Tj覆蓋率的并集,計算公式為:

(3)

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

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

(4)

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

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

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

2.1 節(jié)點虛擬力受力分析

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

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

2.1.1 節(jié)點虛擬力

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

(5)

圖1 節(jié)點虛擬力

2.1.2 安全連接虛擬力

(6)

2.1.3 泰森多邊形形心虛擬力

①泰森多邊形的劃分

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

圖2 Delaunay三角網

圖3 Voronoi圖

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

②泰森多邊形形心

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

(7)

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

(8)

③節(jié)點的形心虛擬力

圖4 泰森多邊形形心引力

(9)

2.1.4 Voronoi圖頂點虛擬力

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

圖5 Voronoi圖頂點虛擬力

(10)

2.1.5 節(jié)點綜合受力分析

(11)

(12)

2.2 節(jié)點的移動過程

(13)

(14)

2.3 覆蓋方案流程圖

通過節(jié)點虛擬力受力分析,以及節(jié)點移動兩個階段,節(jié)點到達部署位置?；诎踩B接的形心導向虛擬力覆蓋優(yōu)化方案的流程圖如圖6所示。

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

具體算法描述如下:

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

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

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

3 仿真實驗與結果分析

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

3.1 仿真環(huán)境及參數設置

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

表1 仿真實驗參數

圖7 正三角形部署

3.2 仿真結果及分析

3.2.1 存在共享密鑰節(jié)點的安全連接

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

圖8 安全連接比較圖

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

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

3.2.1 節(jié)點的覆蓋率

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

圖10 節(jié)點覆蓋率

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

圖9 節(jié)點覆蓋情況比較

4 結束語

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