基于VF-CS的移動傳感器網絡覆蓋優化算法

李光輝，胡世紅

?

基于VF-CS的移動傳感器網絡覆蓋優化算法

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

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

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

移動傳感網絡；虛擬力；布谷鳥搜索；覆蓋率；優化

1 引言

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

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

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

2 預備知識

2.1 問題模型

所有傳感器節點同時對像素點進行感知的聯合感知概率為

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

2.2 Voronoi圖及泰森多邊形

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

圖2 泰森多邊形

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

圖3 多邊形形心

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

2.3 布谷鳥搜索算法

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

CS算法有以下3個規則[25]。

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

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

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

這里，和都服從標準正態分布，即

滿足

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

2.4 最佳部署定理

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

圖4 最佳部署示意

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

3 基于Voronoi圖的VF-CS算法

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

3.1 虛擬力分析

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

3.1.1 多邊形頂點的作用力

3.1.2 相鄰節點間的作用力

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

3.1.3 虛擬力擾動因子的計算

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

5) end for

9) end for

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

算法2 VF-CS算法

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

6) end for

9) forfrom 1 to

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

13) end if

14) end for

17) forfrom 1 to

18) 調用虛擬力擾動因子算法；

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

20) end for

26) end if

27) end while

3.2.1 算法描述

3.3 基于VF-CS算法的覆蓋優化策略

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

Step7 重復Step3~Step5，直至所有節點在所屬泰森多邊形內找到最優移動位置并進行一次性移動。

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

3.4 算法時間復雜度分析

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

4 實驗分析

4.1 仿真場景及參數設置

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

表1 參數設置

4.2 覆蓋率

表2給出了實驗1所有情形下取得的最終覆蓋率，3種部署環境下，隨著部署傳感器節點數量的增加，覆蓋率也隨之提高，由表2可看出，本文VF-CS算法的覆蓋率高于其他3種算法，且當部署節點數量較小時，VF-CS算法取得的覆蓋率優勢更為明顯。例如，在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 不同規模的傳感器網絡覆蓋率隨著迭代次數的變化趨勢

表2 不同傳感器節點數量下的區域最終覆蓋率

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

圖9 不同規模的傳感器網絡覆蓋率隨著迭代次數的變化趨勢

4.3 節點平均移動距離

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

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

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

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

表3 實驗1算法耗時

4.4 算法耗時

表3給出了4種覆蓋優化算法在3種部署環境下不同節點規模中的計算時間。由表3可知，VF-CS算法平均耗時比BCBS小很多，例如，部署區域為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節的實驗分析可知，VF-CS算法的覆蓋率比CIVDA要高很多。CIVDA算法耗時最少，主要是由于該算法的全局優化能力弱，出現“早熟”現象所致，但其覆蓋率是最低的。而BCBS算法由于其在分析盲區構造與多邊形盲區相近的多邊形時，計算復雜度高，導致算法耗時偏長。

表4 節點覆蓋效率對比

4.5 節點覆蓋效率

為了檢驗算法在不同環境的適應能力，實驗測試了算法的覆蓋效率，以檢驗算法在不同的網絡節點分布密度情況下的性能。表4給出了VF-CS和BCBS這2種覆蓋優化算法在3種部署環境下不同節點規模中的覆蓋效率。

由表4可知，在3種環境下VF-CS算法的覆蓋效率C均大于BCBS算法，證明VF-CS算法的節點冗余度低于BCBS算法，網絡中節點的分布更加均勻。例如，監測區域大小為350 m×350 m、1 000時，VF-CS算法最終的覆蓋效率為0.703 4，比BCBS算法大2.69%。在每種部署環境下，隨著節點數量的增加，覆蓋效率降低，表明節點冗余程度增大。例如，監測區域大小為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%。由此說明，在部署環境節點數量變化的情況下，VF-CS算法相比于BCBS算法，覆蓋效率能保持更高的水平。

5 結束語

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

[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] 劉惠, 柴志杰, 杜軍朝,等. 基于組合虛擬力的傳感器網絡三維空間重部署算法研究[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] 石為人, 袁久銀, 雷璐寧. 無線傳感器網絡覆蓋控制算法研究[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] 丁旭, 吳曉蓓, 黃成. 基于改進粒子群算法和特征點集的無線傳感器網絡覆蓋問題研究[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] 李勁, 岳昆, 劉惟一. 基于融合的無線傳感器網絡-集覆蓋的分布式算法[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] 莊曜銘, 吳成東, 張云洲, 等. 無線傳感器網絡中復合事件柵欄覆蓋問題[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] 涂志亮, 王強, 沈毅. 移動傳感器網絡中目標跟蹤與監測的同步優化[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圖盲區的無線傳感器網絡覆蓋控制部署策略[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] 周彤, 洪炳镕, 樸松昊. 基于虛擬力的混合感知網節點部署[J]. 計算機研究與發展, 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）；江蘇省重點研發計劃基金資助項目（No.BE2016627）；中央高校基本科研業務費專項資金基金資助項目（No.RP51635B）；無錫市國際科技研發合作基金資助項目（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-），男，湖南郴州人，博士，江南大學教授、博士生導師，主要研究方向為無線傳感器網絡、容錯計算、無損檢測技術。

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