孫子文,申 棟(.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院,江蘇 無(wú)錫 2422;2.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心,江蘇 無(wú)錫 2422)

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

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

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

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

1 WSN覆蓋模型

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

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

(1)

節(jié)點(diǎn)Si對(duì)目標(biāo)點(diǎn)Tj的感知概率P(Si,Tj)采用布爾感知模型[14-15]計(jì)算:

(2)

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

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

(3)

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

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

(4)

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

2 基于安全連接的形心導(dǎo)向虛擬力覆蓋方案

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

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

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

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

2.1.1 節(jié)點(diǎn)虛擬力

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

(5)

圖1 節(jié)點(diǎn)虛擬力

2.1.2 安全連接虛擬力

(6)

2.1.3 泰森多邊形形心虛擬力

①泰森多邊形的劃分

在無(wú)線傳感器網(wǎng)絡(luò)部署區(qū)域中,對(duì)部署區(qū)域進(jìn)行Delaunay三角剖分,節(jié)點(diǎn)連線形成Delaunay三角網(wǎng),如圖2所示。

圖2 Delaunay三角網(wǎng)

圖3 Voronoi圖

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

②泰森多邊形形心

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

(7)

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

(8)

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

圖4 泰森多邊形形心引力

(9)

2.1.4 Voronoi圖頂點(diǎn)虛擬力

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

圖5 Voronoi圖頂點(diǎn)虛擬力

(10)

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

(11)

(12)

2.2 節(jié)點(diǎn)的移動(dòng)過(guò)程

(13)

(14)

2.3 覆蓋方案流程圖

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

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

具體算法描述如下:

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

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

⑤計(jì)算節(jié)點(diǎn)Si位置更新后的覆蓋率為ψ,如果覆蓋率達(dá)到要求,節(jié)點(diǎn)停止移動(dòng),否則重復(fù)步驟①～步驟④。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為研究該方案的有效性,對(duì)該方案進(jìn)行了仿真實(shí)驗(yàn),并與文獻(xiàn)[9]方案與文獻(xiàn)[12]方案的性能進(jìn)行了對(duì)比。

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

仿真采用MATLAB 2014a進(jìn)行,仿真實(shí)驗(yàn)所涉及的參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)

圖7 正三角形部署

3.2 仿真結(jié)果及分析

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

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

圖8 安全連接比較圖

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

表2 存在共享密鑰節(jié)點(diǎn)的安全連接個(gè)數(shù)

3.2.1 節(jié)點(diǎn)的覆蓋率

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

圖10 節(jié)點(diǎn)覆蓋率

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

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

4 結(jié)束語(yǔ)

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