李光輝，胡世紅

?

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

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

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

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

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

1 引言

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

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

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

2 預備知識

2.1 問題模型

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

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

2.2 Voronoi圖及泰森多邊形

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

圖2 泰森多邊形

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

圖3 多邊形形心

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

2.3 布谷鳥搜索算法

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

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

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

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

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

這里，和都服從標準正態(tài)分布，即

滿足

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

2.4 最佳部署定理

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

圖4 最佳部署示意

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

3 基于Voronoi圖的VF-CS算法

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

3.1 虛擬力分析

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

3.1.1 多邊形頂點的作用力

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

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

3.1.3 虛擬力擾動因子的計算

算法1 虛擬力擾動因子計算

5) end for

9) end for

3.2 虛擬力擾動的布谷鳥搜索算法

算法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)用虛擬力擾動因子算法；

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算法的初始化，整個覆蓋優(yōu)化策略步驟如下。

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

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

3.4 算法時間復雜度分析

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

4 實驗分析

4.1 仿真場景及參數(shù)設置

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

表1 參數(shù)設置

4.2 覆蓋率

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

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

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

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

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

4.3 節(jié)點平均移動距離

在實驗1和實驗2的基礎上，對傳感器節(jié)點的移動距離進行了記錄，取平均移動距離作為傳感器節(jié)點能量消耗的衡量指標，即平均移動距離越小，能耗越低。圖10和圖11分別給出了實驗1和實驗2的節(jié)點平均移動距離的比較結(jié)果。

圖10 實驗1的平均移動距離對比

圖11 實驗2的平均移動距離對比

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

表3 實驗1算法耗時

4.4 算法耗時

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

表4 節(jié)點覆蓋效率對比

4.5 節(jié)點覆蓋效率

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

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

5 結(jié)束語

本文針對移動傳感器網(wǎng)絡提出了一種基于Voronoi圖和改進布谷鳥搜索的覆蓋優(yōu)化算法。該算法在傳統(tǒng)的Voronoi圖劃分的基礎上，對傳感器節(jié)點所在的泰森多邊形的頂點以及鄰居節(jié)點進行虛擬力分析，將傳感器節(jié)點受到總作用力作為該節(jié)點進行布谷鳥搜索位置更新時的擾動因子，從而加快優(yōu)化進程；在布谷鳥搜索最佳移動位置過程中，結(jié)合Voronoi多邊形形心在覆蓋優(yōu)化中的有效作用，將每個節(jié)點所在的泰森多邊形形心位置考慮進初始化位置集合中，提高了整體覆蓋率。實驗結(jié)果表明，相比于其他3種基于Voronoi圖的節(jié)點部署算法，本文算法提高了網(wǎ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)絡三維空間重部署算法研究[J]. 自動化學報, 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)絡覆蓋控制算法研究[J]. 自動化學報, 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] 丁旭, 吳曉蓓, 黃成. 基于改進粒子群算法和特征點集的無線傳感器網(wǎng)絡覆蓋問題研究[J]. 電子學報, 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)絡-集覆蓋的分布式算法[J]. 電子學報, 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] 莊曜銘, 吳成東, 張云洲, 等. 無線傳感器網(wǎng)絡中復合事件柵欄覆蓋問題[J]. 通信學報, 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] 涂志亮, 王強, 沈毅. 移動傳感器網(wǎng)絡中目標跟蹤與監(jiān)測的同步優(yōu)化[J]. 自動化學報, 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)絡覆蓋控制部署策略[J]. 物理學報, 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é)點部署[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

國家自然科學基金資助項目（No.61472368, No.61174023）；江蘇省重點研發(fā)計劃基金資助項目（No.BE2016627）；中央高?；究蒲袠I(yè)務費專項資金基金資助項目（No.RP51635B）；無錫市國際科技研發(fā)合作基金資助項目（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-），男，湖南郴州人，博士，江南大學教授、博士生導師，主要研究方向為無線傳感器網(wǎng)絡、容錯計算、無損檢測技術。

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