無線傳感器網(wǎng)絡(luò)節(jié)點多目標安全優(yōu)化部署*

孫子文,申 棟

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

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)在許多領(lǐng)域得到了廣泛的應(yīng)用[1-3],對無線傳感器網(wǎng)絡(luò)性能的研究也就成了重要的研究內(nèi)容。網(wǎng)絡(luò)安全是網(wǎng)絡(luò)的基礎(chǔ)[4],網(wǎng)絡(luò)部署是影響WSN性能的關(guān)鍵環(huán)節(jié),而重要的考慮因素包括網(wǎng)絡(luò)部署時的覆蓋質(zhì)量以及網(wǎng)絡(luò)部署時的安全性[5],因而網(wǎng)絡(luò)通信鏈路的安全連接性和網(wǎng)絡(luò)的覆蓋質(zhì)量等問題,成為網(wǎng)絡(luò)節(jié)點部署研究領(lǐng)域的關(guān)鍵問題。

為提高網(wǎng)絡(luò)部署時的節(jié)點覆蓋性能,部分學(xué)者提出了以節(jié)點覆蓋率為目標函數(shù)的單目標優(yōu)化部署方案[6-8]?；谔┥噙呅涡涡牡牟渴鸱桨窩BS(Centroid Based Scheme)將節(jié)點移動到泰森多邊形形心位置[6],把整個網(wǎng)絡(luò)部署區(qū)域覆蓋優(yōu)化問題轉(zhuǎn)換為每個泰森多邊形區(qū)域的覆蓋優(yōu)化問題,從而減小了計算復(fù)雜度,提高了節(jié)點的覆蓋率;在泰森多邊形優(yōu)化覆蓋的基礎(chǔ)上,結(jié)合虛擬力算法,引入Voronoi圖頂點引力和Voronoi圖邊界引力,引導(dǎo)網(wǎng)絡(luò)部署時節(jié)點的位置移動[7,8],以提高節(jié)點覆蓋率?？紤]提高節(jié)點覆蓋率的單目標優(yōu)化網(wǎng)絡(luò)節(jié)點部署優(yōu)化方案雖然提高了網(wǎng)絡(luò)的覆蓋率[6-8]的方案對網(wǎng)絡(luò)的能耗等性能并沒有改善。

為提高網(wǎng)絡(luò)部署時的覆蓋率和降低能耗,研究人員提出了多目標優(yōu)化的節(jié)點優(yōu)化部署方案[9-12]。通過建立最大化節(jié)點覆蓋率和最小化網(wǎng)絡(luò)能耗兩個優(yōu)化目標函數(shù),采用多目標優(yōu)化的二進制粒子群算法,并引入Pareto求解策略,得到高節(jié)點覆蓋率和低能耗的網(wǎng)絡(luò)節(jié)點部署方案[9];一種新的基于信息共享的粒子群優(yōu)化算法PSO(Particle Swarm Optimization),設(shè)計了人工免疫系統(tǒng)多樣性維持機制,將免疫優(yōu)化引入粒子群算法,維持種群多樣性,提高了節(jié)點覆蓋率,減小了能量消耗[10];通過遺傳算法來進行無線傳感器節(jié)點部署,結(jié)合能耗與覆蓋率計算節(jié)點的地理位置,提出了基于模糊主導(dǎo)地位的多目標優(yōu)化算法,利用切比雪夫公式進行多種不同權(quán)值下的子問題優(yōu)化,將個體中每個目標轉(zhuǎn)換為模糊主導(dǎo)因子,利用主導(dǎo)因子來替代支配關(guān)系,使網(wǎng)絡(luò)節(jié)點的覆蓋率提高、網(wǎng)絡(luò)壽命增長、節(jié)點連通性提高[11];一種二進制和概率覆蓋模型的一種集中免疫-Voronoi部署算法,以節(jié)點覆蓋率、節(jié)點移動能耗為優(yōu)化目標,采用多目標集中免疫算法,利用Voronoi圖的特性進行目標優(yōu)化,提高了節(jié)點覆蓋率、減小了節(jié)點移動能耗[12]。以上的多目標優(yōu)化算法已考慮了節(jié)點部署時網(wǎng)絡(luò)覆蓋率,但是沒有考慮節(jié)點之間已有的安全連接問題。

針對目前無線傳感器網(wǎng)絡(luò)節(jié)點多目標覆蓋優(yōu)化方案沒有考慮節(jié)點之間安全連接的問題。本文在節(jié)點部署優(yōu)化中以提高網(wǎng)絡(luò)覆蓋率為優(yōu)化目標的同時,將節(jié)點的安全連接度也作為優(yōu)化目標,以節(jié)點全連通約束和節(jié)點移動能耗作為約束條件,建立多目標節(jié)點安全部署優(yōu)化模型,采用改進的粒子群優(yōu)化算法進行求解,能夠得到最大的網(wǎng)絡(luò)覆蓋率以及最大網(wǎng)絡(luò)安全連通度。

1 多目標節(jié)點安全優(yōu)化部署模型

將無線傳感器網(wǎng)絡(luò)多目標節(jié)點的優(yōu)化部署問題建模為節(jié)點全連通約束和節(jié)點移動能耗兩個約束條件下,以節(jié)點覆蓋率、節(jié)點安全連通度為目標函數(shù)的多目標節(jié)點優(yōu)化部署方案。

1.1 網(wǎng)絡(luò)模型

設(shè)在無線傳感器網(wǎng)絡(luò)二維平面部署區(qū)域T中,隨機部署著N個有相同感知半徑Rs和通信半徑Rc的無線傳感器網(wǎng)絡(luò)節(jié)點(以下簡稱節(jié)點),節(jié)點集為S={S1,S2,S3,…,SN},其中節(jié)點Si的位置坐標表示為(xSi,ySi)。

1.2 多目標節(jié)點安全優(yōu)化部署的數(shù)學(xué)模型

多目標組合優(yōu)化問題,可以看作是一組參數(shù)(決策變量)到一組目標的映射[13]。在無線傳感器網(wǎng)絡(luò)節(jié)點安全優(yōu)化部署問題中,需考慮提高網(wǎng)絡(luò)的安全性的同時提高網(wǎng)絡(luò)覆蓋率,因此,引入多目標優(yōu)化策略,設(shè)計了考慮安全性和覆蓋率的兩個目標函數(shù)。為此,建立基于安全連通度的多目標節(jié)點優(yōu)化部署的數(shù)學(xué)模型:

(1)

1.3 目標函數(shù)

1.3.1 安全連通度目標函數(shù)

無線傳感器網(wǎng)絡(luò)中的節(jié)點連通度是指網(wǎng)絡(luò)中節(jié)點一跳范圍之內(nèi)能夠與其通信的相鄰節(jié)點的數(shù)量與網(wǎng)絡(luò)中節(jié)點總數(shù)量二次方的比值,連通度越大,網(wǎng)絡(luò)中存在的通路就越多,網(wǎng)絡(luò)的連通性能越好。無線傳感器網(wǎng)絡(luò)中的節(jié)點連通度可以描述為:

(2)

式中:ρij為相鄰節(jié)點的連通因子:

(3)

當節(jié)點間距離d(Si,Sj)小于或者等于通信半徑Rc時,ρij=1,即節(jié)點Si與Sj存在無線通信;當節(jié)點間的距離d(Si,Sj)大于通信半徑RS時,ρij=0,即節(jié)點Si與Sj不存在無線通信。

假設(shè)無線傳感器網(wǎng)絡(luò)在節(jié)點部署前使用了密鑰管理方案,節(jié)點能夠通過共享密鑰建立安全的連接。本文將節(jié)點連通度的概念延伸,定義無線傳感器網(wǎng)絡(luò)節(jié)點安全連通度為:

(4)

(5)

進一步建立第1個目標函數(shù)為節(jié)點安全連通度目標函數(shù):

(6)

節(jié)點安全連通度能夠反映網(wǎng)絡(luò)安全性能的高低,節(jié)點的安全連通度越大節(jié)點與更多的鄰居節(jié)點存在共享密鑰,網(wǎng)絡(luò)的安全性能越高。

1.3.2 網(wǎng)絡(luò)覆蓋率目標函數(shù)

將部署區(qū)域T離散化為m×n個目標點集T={T1,T2,T3,…,Tm×n},其中目標點Tl的位置坐標表示為(xTl,yTl)(l=1,2,3,…,m×n)。則目標點Tl與節(jié)點Si的歐氏距離為:

(7)

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

(8)

如果d(Si,Tl)≤Rs,節(jié)點Si對目標點Tl的感知概率為1,即目標點被節(jié)點覆蓋;否則,節(jié)點Si對目標點Tl的感知概率為0,即目標點沒有被節(jié)點覆蓋。

對目標點Tl的聯(lián)合感知概率Il是節(jié)點集S={S1,S2,S3,…,SN}對目標點Tl覆蓋率的并集為:

(9)

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

假設(shè)每個目標點Tl(l=1,2,3,…,m×n)的面積均為Δm×Δn,如果目標點被覆蓋,則目標點的聯(lián)合感知概率為1,覆蓋面積為Δm×Δn,否則為0,所以目標點Tl的覆蓋面積可表示為Il×Δm×Δn;同樣,整個區(qū)域T的總面積為AS=(m×n)(Δm×Δn)。節(jié)點部署后節(jié)點所覆蓋的面積占部署區(qū)域總面積的比值稱為節(jié)點覆蓋率ψ[16],計算如下:

(10)

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

建立第2個目標函數(shù)即網(wǎng)絡(luò)覆蓋率目標函數(shù):

(11)

網(wǎng)絡(luò)覆蓋率能夠反映網(wǎng)絡(luò)對整個覆蓋區(qū)域的監(jiān)測性能,覆蓋率越大表示能夠監(jiān)測的區(qū)域越大。

1.4 約束條件

1.4.1 節(jié)點全連通約束

無線傳感器網(wǎng)絡(luò)節(jié)點全連通保證了網(wǎng)絡(luò)中任意兩個節(jié)點之間均存在至少一條可以直接或者間接進行通信的路徑。節(jié)點全連通約束可以表示為:

?i∈[1,N],?j∈[1,N],i≠j,滿足d(Si,Sj)≤Rc

(12)

1.4.2 節(jié)點移動能耗約束

節(jié)點的能量有限,因此需要考慮節(jié)點移動消耗的能量,對節(jié)點移動的最大距離進行限定。節(jié)點移動能耗約束表示為:

(13)

2 基于改進的多目標粒子群節(jié)點安全部署優(yōu)化求解

多目標優(yōu)化問題中的多個目標不可能同時取得最優(yōu)解,有時會存在沖突甚至相反的情況,與普通單目標優(yōu)化問題不同,它并非是尋找一個最優(yōu)解,而是尋找一個折中了這些目標的非劣解集。本文采用改進的粒子群算法求解節(jié)點多目標部署優(yōu)化問題,采用精英檔案策略保存更新最優(yōu)解集。

2.1 粒子群優(yōu)化求解模型

在本文的WSN位置優(yōu)化部署中,粒子為所有N個節(jié)點在部署過程中的位置坐標。假設(shè)節(jié)點部署中粒子群種群規(guī)模為n,最大迭代次數(shù)即節(jié)點部署過程中最多移動次數(shù)為tmax,由于目標函數(shù)為f1(x)和f2(x)且x=(xS1,yS1,xS2,yS2,…,xSN,ySN),因此,每個粒子k(k=1,2,3,…,n)的維數(shù)為2N。

所有粒子的初始位置為:

lk(0)=[lkxS1,lkyS1,lkxS2,lkyS2,…,lkxSN,lkySN]0

(k=1,2,3,…,n)

(14)

每個粒子以不同的速度迭代,其中第k個粒子第t次迭代的速度,即所有節(jié)點在節(jié)點部署中坐標更新速度為:

vk(t)=[vkxS1,vkyS1,vkxS2,…,vkxSN,vkxSN]t

(15)

式中:每個粒子都能夠計算目標函數(shù)值f1和f2,個體的歷史最優(yōu)位置稱為“個體極值”,即第k個粒子節(jié)點部署節(jié)點最優(yōu)位置,記作:

Pbestk(t)=[PkxS1,PkyS1,PkxS2,…,PkxSN,PkySN]t

(16)

算法種群的粒子全局最優(yōu)的個體位置是通過對比粒子尋優(yōu)過程中的每個粒子的個體極值來確定的,這個全局最優(yōu)個體位置稱為“全局極值”,即所有粒子節(jié)點部署節(jié)點最優(yōu)位置。粒子群算法不斷通過迭代優(yōu)化地搜索并更新個體極值和全局極值,最終求得全局的最優(yōu)位置。

粒子通過式(17)來更新個體極值:

vk(t+1)=ωvk(t)+e1r1[Pbsetk(t)-lk(t)]+e2r2[gbest-lk(t)]

(17)

粒子通過式(18)、式(19)來更新每個粒子的速度與位置:

(18)

lk(t+1)=lk(t)+vk(t+1)

(19)

式中:ω表示慣性權(quán)重,對算法中粒子對當前速度的繼承程度起到了決定性作用,e1、e2表示學(xué)習(xí)因子,決定了粒子飛向個體極值和全局極值位置速度的快慢,r1、r2是[0,1]區(qū)間內(nèi)的隨機數(shù),能夠增強粒子位置的多樣性。

2.2 改進粒子群優(yōu)化策略

①慣性權(quán)重自適應(yīng)調(diào)整

在粒子群算法中,由粒子的速度更新式(18)可知,慣性權(quán)重ω決定了粒子對當前速度的繼承程度。如果慣性權(quán)重ω取值較小,則對當前速度繼承程度較小,粒子的局部搜索能力強,但是容易陷入局部最優(yōu);若慣性權(quán)重取值較大,則對當前速度繼承程度較大,粒子的全局搜索能力強,但是不利于算法局部的尋優(yōu)能力。所以對于慣性權(quán)重ω的最佳的選取是前期取較大值,保證粒子有較強的全局搜索能力,后期為了能夠利于粒子的精細搜索,慣性權(quán)重ω取較小值。為此,改進慣性權(quán)重ω為自適應(yīng)慣性權(quán)重,如式(20)所示:

(20)

隨著迭代次數(shù)t由零增大到tmax,慣性權(quán)重ω由最大值ωmax減小到最小ωmin。

②粒子更新速度調(diào)整

粒子更新速度加上虛擬力的調(diào)整后粒子速度能夠及時調(diào)整,避免了陷入局部最優(yōu),既具有較好的全局搜索能力,又具有較好的局部搜索能力。

(21)

(22)

式中:式(22)虛擬力合力按文獻[17]介紹的方法求解。

③精英檔案Pareto最優(yōu)解策略

由于WSN中的節(jié)點存儲空間有限,而且改進的多目標粒子群算法每次迭代所產(chǎn)生的Pareto最優(yōu)解不是唯一的,因此采用精英檔案策略[18]保存Pareto最優(yōu)解。而在迭代終止后檔案中的成員即是算法的最終解集,檔案內(nèi)存儲解的數(shù)量在一定的范圍內(nèi),即當檔案存儲解的數(shù)量超過某個值時,剔除檔案中的部分解,從而一部分解進入檔案。

為了衡量解的優(yōu)劣,精英檔案策略引入了密集距離概念,通過刪除密集距離較小的解即處在密集位置的解,以限制檔案的成員數(shù)量。而且通過比例選擇的方法為每個粒子選取全局最優(yōu),即Pareto最優(yōu)解中存在的密集距離越大的解會有更大的概率被選為全局最優(yōu)的粒子。

2.3 多目標粒子群優(yōu)化求解算法流程

改進多目標粒子群算法流程如圖1所示。具體算法步驟:

①初始化WSN:初始化種群規(guī)模n,最大迭代次數(shù)tmax,隨機初始化所有粒子的位置和速度,粒子的歷史最優(yōu)位置為當前位置;

②每個粒子的目標函數(shù)值計算:f1和f2;

③粒子更新:首先按照式(20)更新慣性權(quán)重,再根據(jù)式(22)、式(19)更新粒子的速度和位置;

④約束檢驗:若粒子同時滿足約束條件,滿足則轉(zhuǎn)到步驟⑤,否則,轉(zhuǎn)到步驟③重新更新粒子;

⑤個體極值選擇:計算粒子的適應(yīng)度值,更新個體極值;

⑥精英檔案求解:刪除檔案中重復(fù)的成員,根據(jù)密集距離降序排列檔案內(nèi)成員,得到較優(yōu)的存檔。同時,根據(jù)密集距離,采用比例選擇法為每個粒子選取全局最優(yōu);

⑦最優(yōu)解集判斷:若迭代次數(shù)t≥tmax,則結(jié)束循環(huán)迭代,輸出最優(yōu)解集;否則轉(zhuǎn)步驟②繼續(xù)迭代。

3 仿真實驗及其結(jié)果分析

為了研究基于改進的多目標粒子群節(jié)點部署優(yōu)化算法的有效性,對該算法進行了仿真實驗。通過對比僅僅以網(wǎng)絡(luò)覆蓋率為優(yōu)化目標的節(jié)點部署和以網(wǎng)絡(luò)覆蓋率與節(jié)點的安全連通度為優(yōu)化目標的多目標的節(jié)點部署的覆蓋性能;對比改進的多目標粒子群節(jié)點部署算法與多目標粒子群節(jié)點部署算法的覆蓋性能,驗證該算法的有效性。

3.1 環(huán)境與參數(shù)設(shè)置

仿真采用MATLAB 2014a進行,仿真實驗所涉及的參數(shù)如下:

①WSN參數(shù)選擇

表1 WSN參數(shù)的選擇

②改進多目標粒子群算法參數(shù)選擇

表2 改進多目標粒子群算法參數(shù)的選擇

3.2 結(jié)果與分析

仿真的目的是比較僅考慮網(wǎng)絡(luò)覆蓋率的改進的粒子群算法單目標覆蓋優(yōu)化和考慮安全連通度以及網(wǎng)絡(luò)覆蓋率多目標粒子群算法覆蓋優(yōu)化以及改進的多目標粒子群算法覆蓋優(yōu)化的網(wǎng)絡(luò)覆蓋率和安全連接情況進行分析,此外比較了本文算法與粒子群算法的收斂性。

①網(wǎng)絡(luò)覆蓋率

無線傳感器網(wǎng)絡(luò)初始部署以及改進的單目標粒子群算法覆蓋優(yōu)化和考慮安全連通度以及網(wǎng)絡(luò)覆蓋率多目標粒子群算法覆蓋優(yōu)化以及改進的多目標粒子群算法覆蓋優(yōu)化的網(wǎng)絡(luò)覆蓋率的仿真結(jié)果如圖2,圓表示節(jié)點的通信半徑。

由仿真結(jié)果圖2,可知與節(jié)點的初始部署相比,在算法迭代運行200次以后,節(jié)點分布更加均勻,網(wǎng)絡(luò)覆蓋率都有顯著地提高,網(wǎng)絡(luò)覆蓋質(zhì)量有了很大的提高并且網(wǎng)絡(luò)覆蓋率都是隨著算法迭代次數(shù)的增加而增大。初始部署時,節(jié)點的覆蓋率為72.64%,在算法運行200次以后,僅考慮網(wǎng)絡(luò)覆蓋率的單目標覆蓋優(yōu)化算法能夠提高網(wǎng)絡(luò)覆蓋率到98.53%,而考慮安全連通度以及網(wǎng)絡(luò)覆蓋率的粒子群多目標優(yōu)化算法和改進的粒子群多目標優(yōu)化算法能夠提高網(wǎng)絡(luò)覆蓋率分別到95.94和97.69%。

②節(jié)點的安全連通度

假設(shè)在無線傳感器網(wǎng)絡(luò)初始部署時,每一對鄰居節(jié)點都會存在共享密鑰,能夠建立安全的通信連接。在應(yīng)用優(yōu)化算法提高節(jié)點的網(wǎng)絡(luò)覆蓋率時,可能會破壞這些已經(jīng)存在共享密鑰的安全連接,導(dǎo)致節(jié)點的安全連通率降低。初始部署以及改進的單目標粒子群優(yōu)化算法、多目標粒子群優(yōu)化算法和改進多目標粒子群優(yōu)化算法在迭代200次以后存在共享密鑰節(jié)點的安全連接的仿真結(jié)果如圖3,圖中的連線表示節(jié)點之間存在共享密鑰的安全連接。

仿真結(jié)果圖3所示,算法運行200次以后安全連接的個數(shù)都會減少,安全連通度都會降低。具體存在共享密鑰節(jié)點的安全連接個數(shù)以及安全連通度

圖2 網(wǎng)絡(luò)覆蓋情況比較

圖3 安全連接比較圖

如表3所示,節(jié)點初始部署時,節(jié)點間有共享密鑰的安全連接的個數(shù)為262個,算法運行200次以后,僅僅以網(wǎng)絡(luò)覆蓋率為優(yōu)化目標的改進的單目標粒子群算法存在183個安全連接,安全連通度為0.0183,并且在多目標優(yōu)化算法中,粒子群算法與改進的粒子群算法存在安全連接的個數(shù)分別為229、243個,安全連通度分別為0.022 9和0.024 3?？梢?單目標優(yōu)化算法雖然能夠提高網(wǎng)絡(luò)覆蓋率,但是對節(jié)點之間的安全連接破壞嚴重,改進多目標粒子群優(yōu)化算法比多目標粒子群算法在運行200次以后有更高的網(wǎng)絡(luò)覆蓋率以及安全連通度。

表3 存在共享密鑰節(jié)點的安全連接的情況

(3)算法的收斂性

通過對比算法的收斂速度可以反映出算法的運行效率,由仿真結(jié)果圖4得知,本文的改進的粒子群算法比傳統(tǒng)的粒子群算法在迭代次數(shù)相同時,會有更高的節(jié)點網(wǎng)絡(luò)覆蓋率,同時,會更快地達到最大的節(jié)點網(wǎng)絡(luò)覆蓋率。

圖4 收斂過程比較

4 小結(jié)

本文設(shè)計了一種基于改進的多目標粒子群節(jié)點安全部署優(yōu)化方案,通過設(shè)置節(jié)點的安全連通度和網(wǎng)絡(luò)覆蓋率兩個目標函數(shù),尋找滿足節(jié)點全連通約束條件和節(jié)點移動能耗約束條件的最優(yōu)解集,解決無線傳感器網(wǎng)絡(luò)節(jié)點安全部署的問題。采用并通過自適應(yīng)的調(diào)整慣性權(quán)重以及精英檔案策略改進多目標粒子群優(yōu)化算法對節(jié)點安全部署問題求解,與粒子群優(yōu)化算法相比能達到更高的網(wǎng)絡(luò)覆蓋率和節(jié)點安全連通度。