基于VF-CS的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法

李光輝，胡世紅

?

基于VF-CS的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法

李光輝1,2,3，胡世紅1,3

（1. 江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122；2. 江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003；3. 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程技術(shù)研究中心，江蘇 無錫 214122）

在野外環(huán)境部署大規(guī)模傳感器網(wǎng)絡(luò)時(shí)，往往采用隨機(jī)部署方式，導(dǎo)致覆蓋率不高。為此提出一種基于虛擬力（virtual force）擾動(dòng)和布谷鳥搜索（CS, Cuckoo search）的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法（VF-CS）。首先，對(duì)傳感器節(jié)點(diǎn)進(jìn)行Voronoi圖劃分，形成獨(dú)立的泰森多邊形（Thiessen polygon）。其次，對(duì)泰森多邊形內(nèi)的節(jié)點(diǎn)進(jìn)行虛擬力的分析，將多邊形頂點(diǎn)和鄰居節(jié)點(diǎn)的作用力作為布谷鳥搜索位置更新的擾動(dòng)因子。最后，通過布谷鳥搜索引導(dǎo)節(jié)點(diǎn)移動(dòng)實(shí)現(xiàn)覆蓋優(yōu)化。仿真實(shí)驗(yàn)結(jié)果表明，與以往基于Voronoi圖的覆蓋優(yōu)化算法相比，VF-CS算法提高了覆蓋率，減少了節(jié)點(diǎn)平均移動(dòng)距離。

移動(dòng)傳感網(wǎng)絡(luò)；虛擬力；布谷鳥搜索；覆蓋率；優(yōu)化

1 引言

區(qū)域覆蓋是無線傳感器網(wǎng)絡(luò)中的一個(gè)基本問題，它直接影響了網(wǎng)絡(luò)的服務(wù)質(zhì)量。當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，保持或增加網(wǎng)絡(luò)的整體覆蓋率十分重要[1]。移動(dòng)傳感器網(wǎng)絡(luò)是由配備有移動(dòng)平臺(tái)的傳感器節(jié)點(diǎn)組成，以便在初始部署后允許傳感器節(jié)點(diǎn)移動(dòng)[2]。越來越多的應(yīng)用場(chǎng)合需要移動(dòng)傳感器網(wǎng)絡(luò)，如智能交通系統(tǒng)、安全系統(tǒng)、社會(huì)交互等復(fù)雜場(chǎng)景[3,4]。移動(dòng)傳感器網(wǎng)絡(luò)以其自然優(yōu)勢(shì)能夠很好地適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化，并將節(jié)點(diǎn)移動(dòng)到正確的位置，從而提高區(qū)域覆蓋率。

目前，針對(duì)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題，已經(jīng)有很多研究成果[5~15]。例如，丁旭等[9]通過研究區(qū)域覆蓋的特征，提出特征點(diǎn)集的概念并改進(jìn)了粒子群算法，將傳統(tǒng)的區(qū)域覆蓋轉(zhuǎn)化為基于特征點(diǎn)集優(yōu)化覆蓋問題。李勁等[10]結(jié)合博弈論提出一種分布式的覆蓋優(yōu)化算法，算法收斂時(shí)網(wǎng)絡(luò)能達(dá)到較高的覆蓋率。近年來，由于移動(dòng)傳感器網(wǎng)絡(luò)相比于靜態(tài)的傳感器網(wǎng)絡(luò)在應(yīng)對(duì)拓?fù)渥兓矫娓袃?yōu)勢(shì)[11]，移動(dòng)節(jié)點(diǎn)的部署優(yōu)化研究領(lǐng)域也取得了重要進(jìn)展[16~22]。其中，Voronoi圖是移動(dòng)傳感器網(wǎng)絡(luò)中常用的覆蓋分析方法，涂志亮等[17]針對(duì)移動(dòng)傳感器網(wǎng)絡(luò)中動(dòng)態(tài)目標(biāo)的監(jiān)測(cè)優(yōu)化問題，建立基于Voronoi剖分的監(jiān)測(cè)性能評(píng)價(jià)函數(shù)，提高網(wǎng)絡(luò)覆蓋質(zhì)量，提出基于群集控制的傳感器節(jié)點(diǎn)部署分布式控制方法。Boukerche等[18]提出一種基于Voronoi圖的技術(shù)，在傳感器節(jié)點(diǎn)位置未知的條件下，通過定向天線獲取鄰居節(jié)點(diǎn)位置以及局部平面掃描算法尋找覆蓋漏洞，從而提高全局覆蓋。Lee等[19]提出了一種基于Voronoi多邊形形心的部署策略（CBS, centroid-based scheme），將區(qū)域覆蓋問題轉(zhuǎn)化為每個(gè)傳感器節(jié)點(diǎn)所屬泰森多邊形的覆蓋優(yōu)化問題，但CBS算法沒有考慮鄰居傳感器節(jié)點(diǎn)的覆蓋，容易出現(xiàn)覆蓋重疊等問題。方偉等[20]在CBS的基礎(chǔ)上分析了Voronoi多邊形盲區(qū)情況，提出一種基于Voronoi多邊形盲區(qū)的覆蓋控制部署策略（BCBS, blind-zone centroid-based scheme），有效提高了覆蓋率，但由于其在分析盲區(qū)構(gòu)造與多邊形盲區(qū)相近的多邊形時(shí)，計(jì)算復(fù)雜度高，導(dǎo)致算法耗時(shí)偏長(zhǎng)。Abo-Zahhad等[21]提出一種基于Voronoi圖的集中式免疫部署算法（CIVDA, centralized immune-Voronoi deployment algorithm），其利用Voronoi圖的特性折中異構(gòu)傳感器網(wǎng)絡(luò)的覆蓋與能量消耗，算法收斂快，但存在“早熟”現(xiàn)象，而且在同構(gòu)網(wǎng)絡(luò)中，該算法在覆蓋率方面還有待提高。

針對(duì)以往研究中存在的問題，本文提出了一種基于虛擬力擾動(dòng)和布谷鳥搜索的移動(dòng)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法，該算法在Voronoi圖劃分的基礎(chǔ)上，對(duì)泰森多邊形內(nèi)的傳感器節(jié)點(diǎn)進(jìn)行虛擬力的分析，不僅考慮了多邊形頂點(diǎn)的作用力以分析覆蓋漏洞區(qū)域方向，同時(shí)也考慮了鄰居節(jié)點(diǎn)的作用力以減少重疊覆蓋面積，將節(jié)點(diǎn)所受的總虛擬力作為布谷鳥搜索位置更新的擾動(dòng)因子，引導(dǎo)節(jié)點(diǎn)更新位置朝著存在覆蓋漏洞區(qū)域的方向移動(dòng)，并且移動(dòng)范圍局限在所屬的泰森多邊形，加快了全局收斂速度，提高了整體覆蓋率，也減少了節(jié)點(diǎn)的平均移動(dòng)距離。

2 預(yù)備知識(shí)

2.1 問題模型

所有傳感器節(jié)點(diǎn)同時(shí)對(duì)像素點(diǎn)進(jìn)行感知的聯(lián)合感知概率為

網(wǎng)絡(luò)中所有節(jié)點(diǎn)覆蓋的監(jiān)測(cè)區(qū)域面積與節(jié)點(diǎn)感知范圍面積總和的比值稱為節(jié)點(diǎn)的覆蓋效率。節(jié)點(diǎn)覆蓋效率C反映網(wǎng)絡(luò)中節(jié)點(diǎn)的冗余程度，C越大表示節(jié)點(diǎn)的冗余程度越小，節(jié)點(diǎn)分布越均勻。具體計(jì)算式為

2.2 Voronoi圖及泰森多邊形

其中，p為監(jiān)測(cè)區(qū)域Γ中的任意一點(diǎn)，單元組成的圖稱為監(jiān)測(cè)區(qū)域的Voronoi 圖。例如，當(dāng)8 m×8 m大小的監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署了15個(gè)傳感器節(jié)點(diǎn)，其Voronoi圖如圖1所示，每個(gè)傳感器節(jié)點(diǎn)對(duì)應(yīng)一個(gè)單元。

圖2 泰森多邊形

定義3 泰森多邊形形心。泰森多邊形形心是指將多邊形分成面積相等的2個(gè)部分所有直線的交點(diǎn)[19]，如圖3所示。

圖3 多邊形形心

Voronoi圖在傳感器節(jié)點(diǎn)部署算法中常用于檢測(cè)覆蓋漏洞[23,24]。本文算法基于Voronoi圖，使每個(gè)傳感器節(jié)點(diǎn)以其所在的泰森多邊形為移動(dòng)范圍區(qū)域，實(shí)行以覆蓋率最大化為目標(biāo)的優(yōu)化算法，具體將在第3節(jié)進(jìn)一步介紹。

2.3 布谷鳥搜索算法

布谷鳥搜索是由Deb等[25]提出的一種基于布谷鳥尋窩孵蛋的繁殖習(xí)性以及Levy飛行特性的新型優(yōu)化算法。CS算法具有參數(shù)設(shè)置少、隨機(jī)搜索路徑優(yōu)、收斂速度快等優(yōu)點(diǎn)，已成功應(yīng)用于工程優(yōu)化等實(shí)際問題中[26,27]。

CS算法有以下3個(gè)規(guī)則[25]。

1) 每個(gè)布谷鳥每次只產(chǎn)一個(gè)蛋，并隨機(jī)選擇鳥窩孵化。

2) 在隨機(jī)選擇的一組鳥窩中，最好的鳥窩將被保留到下一代。

在以上3個(gè)基本規(guī)則下，布谷鳥尋窩的路徑和位置更新式為

這里，和都服從標(biāo)準(zhǔn)正態(tài)分布，即

滿足

由此可得，布谷鳥尋窩的路徑和位置更新式為

2.4 最佳部署定理

在傳感器網(wǎng)絡(luò)中，用最少數(shù)量的傳感器節(jié)點(diǎn)部署監(jiān)測(cè)區(qū)域，同時(shí)滿足節(jié)點(diǎn)間沒有覆蓋空隙，從而區(qū)域達(dá)到滿覆蓋率，稱這樣的節(jié)點(diǎn)部署為最佳部署[28]。針對(duì)無線傳感器網(wǎng)絡(luò)的覆蓋率、連通度及容錯(cuò)性能優(yōu)化，Ammari等[28]提出了以下的最佳部署定理。

圖4 最佳部署示意

圖5 傳感器感知圓盤相切的最小間隙

3 基于Voronoi圖的VF-CS算法

本文提出了一種基于虛擬力擾動(dòng)和布谷鳥搜索的覆蓋優(yōu)化（VF-CS）算法。布谷鳥搜索中的萊維飛行過程采用隨機(jī)步長(zhǎng)，為防止其在搜索過程中跳出特定區(qū)域，使位置更新后節(jié)點(diǎn)的移動(dòng)距離過大，VF-CS算法利用了泰森多邊形的概念，把泰森多邊形中的節(jié)點(diǎn)受力作為布谷鳥搜索中位置更新的擾動(dòng)因子，引導(dǎo)節(jié)點(diǎn)朝著存在覆蓋漏洞區(qū)域的方向移動(dòng)，并且移動(dòng)范圍局限在節(jié)點(diǎn)所屬的泰森多邊形，從而減少平均移動(dòng)距離。VF-CS算法在Voronoi圖的基礎(chǔ)上，假設(shè)節(jié)點(diǎn)所屬的泰森多邊形為其移動(dòng)范圍，采用布谷鳥搜索尋找最優(yōu)移動(dòng)位置，并將虛擬力引入布谷鳥搜索路徑中，優(yōu)化路徑，防止算法出現(xiàn)“早熟”現(xiàn)象，同時(shí)加快全局收斂速度。

3.1 虛擬力分析

由于設(shè)定節(jié)點(diǎn)只在所屬泰森多邊形內(nèi)移動(dòng)，所以可假設(shè)其只受所屬泰森多邊形頂點(diǎn)以及相鄰節(jié)點(diǎn)的作用力。監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)完成Voronoi圖分割后，節(jié)點(diǎn)所屬泰森多邊形內(nèi)的覆蓋情況會(huì)根據(jù)節(jié)點(diǎn)的位置以及相鄰節(jié)點(diǎn)的部署發(fā)生變化。為了提高多邊形內(nèi)的覆蓋率，節(jié)點(diǎn)應(yīng)往多邊形中存在覆蓋漏洞的方向移動(dòng)，同時(shí)為了減少覆蓋重疊，相鄰節(jié)點(diǎn)間需保持一定的距離。

3.1.1 多邊形頂點(diǎn)的作用力

3.1.2 相鄰節(jié)點(diǎn)間的作用力

其中，()表示對(duì)引力（斥力）的度量，表示向量的方向。由此可分析，圖7中節(jié)點(diǎn)、和與節(jié)點(diǎn)的歐氏距離大于，對(duì)節(jié)點(diǎn)產(chǎn)生引力；節(jié)點(diǎn)與節(jié)點(diǎn)的歐氏距離為，則不產(chǎn)生任何作用力；節(jié)點(diǎn)與節(jié)點(diǎn)歐氏距離小于，則產(chǎn)生斥力。

3.1.3 虛擬力擾動(dòng)因子的計(jì)算

算法1 虛擬力擾動(dòng)因子計(jì)算

5) end for

9) end for

3.2 虛擬力擾動(dòng)的布谷鳥搜索算法

算法2 VF-CS算法

5) 根據(jù)式(13)，更新位置；

6) end for

9) forfrom 1 to

12) else 根據(jù)式(13)，更新位置；

13) end if

14) end for

17) forfrom 1 to

18) 調(diào)用虛擬力擾動(dòng)因子算法；

19) 根據(jù)式(17)，更新位置；

20) end for

26) end if

27) end while

3.2.1 算法描述

3.3 基于VF-CS算法的覆蓋優(yōu)化策略

本文所提的覆蓋優(yōu)化策略基于Voronoi圖，由Lee等[19]提出的CBS算法利用泰森多邊形形心的性質(zhì)有效地提高了覆蓋率，故將泰森多邊形形心位置用于VF-CS算法的初始化，整個(gè)覆蓋優(yōu)化策略步驟如下。

Step7 重復(fù)Step3~Step5，直至所有節(jié)點(diǎn)在所屬泰森多邊形內(nèi)找到最優(yōu)移動(dòng)位置并進(jìn)行一次性移動(dòng)。

Step8 重復(fù)Step2~Step7，直至全局收斂，產(chǎn)生最終覆蓋率。

3.4 算法時(shí)間復(fù)雜度分析

設(shè)為節(jié)點(diǎn)個(gè)數(shù)，為布谷鳥初始群體數(shù)，max為最大迭代次數(shù)。VF-CS算法首先劃分Voronoi圖，其時(shí)間復(fù)雜度為()；此后，算法的主要計(jì)算過程在于布谷鳥搜索階段，對(duì)于每個(gè)節(jié)點(diǎn)，按照VF-CS算法流程，每迭代一次，最多需要更新3次位置，更新位置的時(shí)間復(fù)雜度為(max()×)，所以在節(jié)點(diǎn)迭代最多的情況下所需的時(shí)間復(fù)雜度為(max×(max()×))，總的覆蓋策略的最壞情況時(shí)間復(fù)雜度則為(+max×(max()×))。而方偉等[20]的BCBS算法的最大時(shí)間復(fù)雜度為(+max×(2))，當(dāng)不大于時(shí)，(+max×(max()×))≤(+max×(2))，一般情況下，取值都小于，所以VF-CS算法時(shí)間復(fù)雜度比BCBS算法要低。

4 實(shí)驗(yàn)分析

4.1 仿真場(chǎng)景及參數(shù)設(shè)置

為了更全面地進(jìn)行對(duì)比，本文設(shè)計(jì)了2組仿真實(shí)驗(yàn)。實(shí)驗(yàn)1考慮了3種不同大小的監(jiān)測(cè)區(qū)域在相同的檢測(cè)區(qū)域部署不同數(shù)量的傳感器節(jié)點(diǎn)情形。1) 100 m×100 m區(qū)域，分別部署90、80、70、60、50和40個(gè)傳感器節(jié)點(diǎn)；2) 200 m×200 m區(qū)域，分別部署340、320、300、280、260和240個(gè)傳感器節(jié)點(diǎn)；3) 350 m×350m區(qū)域，分別部署1 000、900、800、700、600和500個(gè)傳感器節(jié)點(diǎn)。將VF-CS算法和以往3種同類算法在不同部署環(huán)境中、不同節(jié)點(diǎn)規(guī)模下的覆蓋率變化趨勢(shì)進(jìn)行橫向?qū)Ρ?，并?duì)4種算法的平均移動(dòng)距離和算法耗時(shí)進(jìn)行比較。實(shí)驗(yàn)2在實(shí)驗(yàn)1設(shè)置的3種部署環(huán)境中分別選取一種節(jié)點(diǎn)規(guī)模進(jìn)行縱向?qū)Ρ龋?00 m×100 m取=90，200 m×200 m取=340，350 m×350 m取=1 000，觀察VF-CS算法和以往同類算法在3種部署環(huán)境下覆蓋率的變化趨勢(shì)，對(duì)節(jié)點(diǎn)平均移動(dòng)距離和算法耗時(shí)進(jìn)行比較。具體的實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

4.2 覆蓋率

表2給出了實(shí)驗(yàn)1所有情形下取得的最終覆蓋率，3種部署環(huán)境下，隨著部署傳感器節(jié)點(diǎn)數(shù)量的增加，覆蓋率也隨之提高，由表2可看出，本文VF-CS算法的覆蓋率高于其他3種算法，且當(dāng)部署節(jié)點(diǎn)數(shù)量較小時(shí)，VF-CS算法取得的覆蓋率優(yōu)勢(shì)更為明顯。例如，在200 m×200 m的情況下，當(dāng)=240時(shí)，VF-CS算法的最終覆蓋率比BCBS提高2.99%，比CBS提高4.3%，比CIVDA提高13.56%，平均提高約6.95%；在350 m×350 m的情況下，當(dāng)=1 000時(shí)，VF-CS算法的最終覆蓋率比BCBS提高0.92%，比CBS提高1.54%，比CIVDA提高11.79%。

圖8 不同規(guī)模的傳感器網(wǎng)絡(luò)覆蓋率隨著迭代次數(shù)的變化趨勢(shì)

表2 不同傳感器節(jié)點(diǎn)數(shù)量下的區(qū)域最終覆蓋率

圖9為實(shí)驗(yàn)2的覆蓋率比較結(jié)果。從圖9可看出，對(duì)于3種部署環(huán)境，VF-CS算法的覆蓋率都比其他算法高。例如，監(jiān)測(cè)區(qū)域大小為200 m×200 m，為340個(gè)，VF-CS算法最終覆蓋率達(dá)98.72%，BCBS算法、CBS算法以及CIVDA算法最終覆蓋率分別為97.86%、97.88%和90.77%。

圖9 不同規(guī)模的傳感器網(wǎng)絡(luò)覆蓋率隨著迭代次數(shù)的變化趨勢(shì)

4.3 節(jié)點(diǎn)平均移動(dòng)距離

在實(shí)驗(yàn)1和實(shí)驗(yàn)2的基礎(chǔ)上，對(duì)傳感器節(jié)點(diǎn)的移動(dòng)距離進(jìn)行了記錄，取平均移動(dòng)距離作為傳感器節(jié)點(diǎn)能量消耗的衡量指標(biāo)，即平均移動(dòng)距離越小，能耗越低。圖10和圖11分別給出了實(shí)驗(yàn)1和實(shí)驗(yàn)2的節(jié)點(diǎn)平均移動(dòng)距離的比較結(jié)果。

圖10 實(shí)驗(yàn)1的平均移動(dòng)距離對(duì)比

圖11 實(shí)驗(yàn)2的平均移動(dòng)距離對(duì)比

由圖10可知，3種部署環(huán)境下，VF-CS算法的平均移動(dòng)距離均比其他算法小，例如圖10(a)，部署區(qū)域大小為100 m×100 m，當(dāng)=60時(shí)，VF-CS算法平均移動(dòng)距離比CBS算法略大，比其他3種算法小，但當(dāng)=40、50、70、80、90時(shí)，VF-CS算法的平均移動(dòng)距離都明顯小于其他3種算法，其中，CIVDA的平均移動(dòng)距離最大，而且隨著傳感器節(jié)點(diǎn)數(shù)量的增加，VF-CS的平均移動(dòng)距離隨之減小，比其他3種算法穩(wěn)定。由于BCBS算法在覆蓋率方面的表現(xiàn)與本文提出的VF-CS算法相差不多，將VF-CS算法的平均移動(dòng)距離與BCBS算法進(jìn)行單獨(dú)比較可以發(fā)現(xiàn)，VF-CS算法的平均移動(dòng)距離比BCBS算法小很多，如圖10(b)所示，部署區(qū)域大小為200 m×200 m，當(dāng)=300時(shí)，VF-CS的平均移動(dòng)距離比BCBS的平均移動(dòng)距離小近1.5 m。由于CBS和BCBS算法都是在幾何計(jì)算的基礎(chǔ)上進(jìn)行覆蓋優(yōu)化，節(jié)點(diǎn)移動(dòng)范圍雖也是局限于泰森多邊形內(nèi)，但在尋找移動(dòng)位置的過程中，其優(yōu)化進(jìn)程不如VF-CS算法快，所以平均移動(dòng)距離都高于VF-CS算法，而CIVDA中節(jié)點(diǎn)的移動(dòng)范圍并沒有受到限制，導(dǎo)致其平均移動(dòng)距離遠(yuǎn)大于其他3個(gè)算法。由圖11可知，在100 m×100 m、90個(gè)節(jié)點(diǎn)，200 m×200 m、340個(gè)節(jié)點(diǎn)，350 m×350 m、1 000個(gè)節(jié)點(diǎn)這3種情形下，VF-CS算法的節(jié)點(diǎn)平均移動(dòng)距離都比其他算法小。

表3 實(shí)驗(yàn)1算法耗時(shí)

4.4 算法耗時(shí)

表3給出了4種覆蓋優(yōu)化算法在3種部署環(huán)境下不同節(jié)點(diǎn)規(guī)模中的計(jì)算時(shí)間。由表3可知，VF-CS算法平均耗時(shí)比BCBS小很多，例如，部署區(qū)域?yàn)?50 m×350 m，當(dāng)=1 000時(shí)，VF-CS算法耗時(shí)4 228.239 s，BCBS算法耗時(shí)11 507.883 s，CBS算法耗時(shí)6 826.56 s，BCBS算法耗時(shí)是VF-CS算法耗時(shí)的2.72倍，CBS算法耗時(shí)是VF-CS算法耗時(shí)的1.61倍。由此可見，VF-CS算法大大提高了全局收斂速度，盡管VF-CS算法比CIVDA算法耗時(shí)要略多一些，但從4.2節(jié)的實(shí)驗(yàn)分析可知，VF-CS算法的覆蓋率比CIVDA要高很多。CIVDA算法耗時(shí)最少，主要是由于該算法的全局優(yōu)化能力弱，出現(xiàn)“早熟”現(xiàn)象所致，但其覆蓋率是最低的。而BCBS算法由于其在分析盲區(qū)構(gòu)造與多邊形盲區(qū)相近的多邊形時(shí)，計(jì)算復(fù)雜度高，導(dǎo)致算法耗時(shí)偏長(zhǎng)。

表4 節(jié)點(diǎn)覆蓋效率對(duì)比

4.5 節(jié)點(diǎn)覆蓋效率

為了檢驗(yàn)算法在不同環(huán)境的適應(yīng)能力，實(shí)驗(yàn)測(cè)試了算法的覆蓋效率，以檢驗(yàn)算法在不同的網(wǎng)絡(luò)節(jié)點(diǎn)分布密度情況下的性能。表4給出了VF-CS和BCBS這2種覆蓋優(yōu)化算法在3種部署環(huán)境下不同節(jié)點(diǎn)規(guī)模中的覆蓋效率。

由表4可知，在3種環(huán)境下VF-CS算法的覆蓋效率C均大于BCBS算法，證明VF-CS算法的節(jié)點(diǎn)冗余度低于BCBS算法，網(wǎng)絡(luò)中節(jié)點(diǎn)的分布更加均勻。例如，監(jiān)測(cè)區(qū)域大小為350 m×350 m、1 000時(shí)，VF-CS算法最終的覆蓋效率為0.703 4，比BCBS算法大2.69%。在每種部署環(huán)境下，隨著節(jié)點(diǎn)數(shù)量的增加，覆蓋效率降低，表明節(jié)點(diǎn)冗余程度增大。例如，監(jiān)測(cè)區(qū)域大小為350 m×350 m，當(dāng)由600增加到1 000時(shí)，VF-CS算法的覆蓋效率由0.825 3降低到0.703 4，降低了14.8%；而BCBS算法覆蓋效率由0.812 6降低到0.684 5，降低了15.8%。由此說明，在部署環(huán)境節(jié)點(diǎn)數(shù)量變化的情況下，VF-CS算法相比于BCBS算法，覆蓋效率能保持更高的水平。

5 結(jié)束語

本文針對(duì)移動(dòng)傳感器網(wǎng)絡(luò)提出了一種基于Voronoi圖和改進(jìn)布谷鳥搜索的覆蓋優(yōu)化算法。該算法在傳統(tǒng)的Voronoi圖劃分的基礎(chǔ)上，對(duì)傳感器節(jié)點(diǎn)所在的泰森多邊形的頂點(diǎn)以及鄰居節(jié)點(diǎn)進(jìn)行虛擬力分析，將傳感器節(jié)點(diǎn)受到總作用力作為該節(jié)點(diǎn)進(jìn)行布谷鳥搜索位置更新時(shí)的擾動(dòng)因子，從而加快優(yōu)化進(jìn)程；在布谷鳥搜索最佳移動(dòng)位置過程中，結(jié)合Voronoi多邊形形心在覆蓋優(yōu)化中的有效作用，將每個(gè)節(jié)點(diǎn)所在的泰森多邊形形心位置考慮進(jìn)初始化位置集合中，提高了整體覆蓋率。實(shí)驗(yàn)結(jié)果表明，相比于其他3種基于Voronoi圖的節(jié)點(diǎn)部署算法，本文算法提高了網(wǎng)絡(luò)覆蓋率，減少了平均移動(dòng)距離。

[1] ISBITIREN G, AKAN O B. Three-dimensional underwater target tracking with acoustic sensor networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(8):3897-3906.

[2] SHAIMAA M, MOHAMED, HAITHAM S, et al. Coverage in mobile wireless sensor networks (M-WSN): a survey[J].Computer Communications, 2017, 1(66):133-150.

[3] ZHU C, SHU L, HARA T, et al. Research issues on mobile sensor networks[C]//International ICST Conference on Communications and NETWORKING . 2010:1-6.

[4] MUNIR S A, REN B, JIAO W, et al. Mobile wireless sensor network: architecture and enabling technologies for ubiquitous computing[C]//International Conference on Advanced Information NETWORKING and Applications Workshops. 2007:113-120.

[5] 劉惠, 柴志杰, 杜軍朝,等. 基于組合虛擬力的傳感器網(wǎng)絡(luò)三維空間重部署算法研究[J]. 自動(dòng)化學(xué)報(bào), 2011, 37(6):713-723.

LIU H, CHAI Z J, DU J C, et al. Sensor redeployment algorithm based on combined virtual forces in three dimensional space[J]. Acta Automatica Sinica, 2011, 37(6):713-723.

[6] 石為人, 袁久銀, 雷璐寧. 無線傳感器網(wǎng)絡(luò)覆蓋控制算法研究[J]. 自動(dòng)化學(xué)報(bào), 2009, 35(5):540-545.

SHI W R, YUAN J Y, LEI L N. Research on wireless sensor network coverage control algorithm[J]. Acta Automatica Sinica, 2009, 35(5): 540-545.

[7] AHMAD P A, MAHMUDDIN M, OMAR M H. Virtual force algorithm and cuckoo search algorithm for node placement technique in wireless sensor network[C]//The 4th International Conference on Computing and Informatics. 2013:28-30.

[8] JIN L, CHANG G, JIA J. Mobile sensor networks node distribution optimization based on minimum redundant coverage[C]//Chinese Control Conference. 2010:4851-4856.

[9] 丁旭, 吳曉蓓, 黃成. 基于改進(jìn)粒子群算法和特征點(diǎn)集的無線傳感器網(wǎng)絡(luò)覆蓋問題研究[J]. 電子學(xué)報(bào), 2016, 44(4):967-973.

DING X, WU X B, HUANG C. Area coverage problem based on improved PSO algorithm and feature point set in wireless sensor networks[J]. Acta Electronica Sinica, 2016, 44(4):967-973.

[10] 李勁, 岳昆, 劉惟一. 基于融合的無線傳感器網(wǎng)絡(luò)-集覆蓋的分布式算法[J]. 電子學(xué)報(bào), 2013, 41(4):659-665.

LI J, YUE K, LIU W Y. Distributed set-cover algorithms for fusion-based coverage in wireless sensor networks[J]. Acta Electronica Sinica, 2013, 41(4):659-665.

[11] 莊曜銘, 吳成東, 張?jiān)浦? 等. 無線傳感器網(wǎng)絡(luò)中復(fù)合事件柵欄覆蓋問題[J]. 通信學(xué)報(bào), 2017, 38(6):75-84.

ZHUANG Z M, WU C D, ZHANG Y Z, et al. Compound event barrier coverage in wireless sensor network[J]. Journal on Communications, 2017, 38(6):75-84.

[12] ADULYASAS A, SUN Z, WANG N. Connected coverage optimization for sensor scheduling in wireless sensor networks[J]. IEEE Sensors Journal, 2015, 15(7):3877-3892.

[13] ALDURAIBI F, LASLA N, YOUNIS M. Coverage-based node placement optimization in wireless sensor network with linear topology[C]//IEEE International Conference on Communications. 2016: 107-124.

[14] XIA J. Coverage optimization strategy of wireless sensor network based on swarm intelligence algorithm[C]//International Conference on Smart City and Systems Engineering. 2017:179-182.

[15] DAOUDI A, DETIENNE B, AZOUZI R E, et al. Robust coverage optimization approach in wireless sensor networks[C]//International Conference on Wireless Networks and Mobile Communications. 2017:1-7.

[16] SHEN Z, CHANG Y, JIANG H, et al. A generic framework for optimal mobile sensor redeployment[J]. IEEE Transactions on Vehicular Technology, 2010, 59(8):4043-4057.

[17] 涂志亮, 王強(qiáng), 沈毅. 移動(dòng)傳感器網(wǎng)絡(luò)中目標(biāo)跟蹤與監(jiān)測(cè)的同步優(yōu)化[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(3):452-461.

TU Z L, WANG Q, SHEN Y. A distributed simultaneous optimization algorithm for tracking and monitoring of moving target in mobile sensor networks[J]. Acta Automatica Sinica, 2012, 38(3):452-461.

[18] BOUKERCHE A, XIN F. A voronoi approach for coverage protocols in wireless sensor networks[C]//Global Telecommunications Conference.2007:5190-5194.

[19] LEE H J, KIM Y H, HAN Y H, et al. Centroid-based movement assisted sensor deployment schemes in wireless sensor networks[C]//Vehicular Technology Conference Fall. 2009:1-5.

[20] 方偉, 宋鑫宏. 基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J]. 物理學(xué)報(bào), 2014, 63(22):128-137.

FANG W, SONG X H. A deployment strategy for coverage control in wireless sensor networks based on the blind-zone of voronoi diagram[J]. Acta Physica Sinica, 2014, 63(22):128-137.

[21] ABO-ZAHHAD M, SABOR N, SASAKI S, et al. A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J]. Information Fusion, 2016, 30(C):36-51.

[22] 周彤, 洪炳镕, 樸松昊. 基于虛擬力的混合感知網(wǎng)節(jié)點(diǎn)部署[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(6): 965-972.

ZHOU T, HONG B R, PU S H. Hybrid sensor networks deployment based on virtual force[J]. Journal of Computer Research and Development, 2007, 44(6):965-972.

[23] MAHBOUBI H, AGHDAM A G. Distributed deployment algorithms for coverage improvement in a network of wireless mobile sensors: relocation by virtual force[J]. IEEE Transactions on Control of Network Systems, 2016, PP (99):1-14.

[24] MAHBOUBI H, AGHDAM A G. An energy-efficient strategy to improve coverage in a network of wireless mobile sensors with nonidentical sensing ranges[J].Vehicular Technology Conference (VTC Spring), 2013, 14(2382):1-5.

[25] DEB S, YANG X S. Cuckoo search via levy flights[C]//World Congress on Nature & Biologically Inspired Computing. 2009: 210-214.

[26] LIU C, CHUNMING Y E. Cuckoo search algorithm for the problem of permutation flow shop scheduling[J]. Journal of University of Shanghai for Science & Technology, 2013, 35(1):17-20.

[27] YANG X S, DEB S. Multiobjective cuckoo search for design optimization[J]. Computers & Operations Research, 2013, 40(6): 1616-1624.

[28] AMMARI H M, DAS S K. Coverage, connectivity, and fault tolerance measures of wireless sensor networks[M]. Stabilization, Safety, and Security of Distributed Systems. Heidelberg:Springer, 2006:35-49.

Coverage optimization algorithm based onVF-CS in mobile sensor network

LI Guanghui1,2,3, HU Shihong1,3

1. School of Computer Technology, Jiangnan University, Wuxi 214122, China 2. Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Nanjing 210003, China 3. Research Center of IoT Technology Application Engineering (MOE), Wuxi 214122, China

A random placement of large-scale sensor network in the outdoor environment often causes low coverage. An area coverage optimization algorithm of mobile sensor network (MSN) based on virtual force perturbation and Cuckoo search (VF-CS) was proposed. Firstly, the virtual force of the sensor nodes within the Thiessen polygon was analyzed based on the partitioning of Voronoi diagram of the monitoring area. Secondly, the force of polygon vertices and neighbor nodes was taken as the perturbation factor for updating the node’s location of the Cuckoo search (CS). Finally, the VF-CS guided the node to move so as to achieve the optimal coverage. The simulation results demonstrate that the proposed algorithm has higher coverage and shorter average moving distance of nodes than the Voronoi diagram based algorithms in literatures.

mobile sensor network, virtual force, Cuckoo search, coverage, optimization

TP393

A

10.11959/j.issn.1000-436x.2018039

2017-10-12；

2018-02-14

李光輝，ghli@jiangnan.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61472368, No.61174023）；江蘇省重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目（No.BE2016627）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金基金資助項(xiàng)目（No.RP51635B）；無錫市國(guó)際科技研發(fā)合作基金資助項(xiàng)目（No.CZE02H1706）

The National Natural Science Foundation of China (No.61472368, No.61174023), The Key Project of the Jiangsu Provincial Research and Development (No.BE2016627), The Fundamental Research Funds for the Central Universities (No.RP51635B), International Scientific and Technological Cooperation Projects of Wuxi (No.CZE02H1706)

李光輝（1970-），男，湖南郴州人，博士，江南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、容錯(cuò)計(jì)算、無損檢測(cè)技術(shù)。

胡世紅（1993-），女，江蘇連云港人，江南大學(xué)碩士生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化。