無線傳感網絡覆蓋算法的研究進展

徐會彬

無線傳感網絡覆蓋算法的研究進展

徐會彬

（湖州師范學院 信息工程學院，浙江 湖州 313000）

為了進一步研究無線傳感網絡(WSNs)應用中的傳感節點覆蓋問題，對相關技術性能和研究進展進行了闡述：對WSN進行多維分類，給出全覆蓋、部分覆蓋的概念；著重分析近年來具有代表性的部分覆蓋技術及其優缺點，并從覆蓋度、節點分布特性、節點類型以及網絡拓撲結構4個方面進行比較分析；最后，總結出部分覆蓋技術的未來可能的研究策略與突破方向。

無線傳感網；網絡分類；全覆蓋；部分覆蓋；覆蓋度

0 引言

無線傳感網絡（wireless sensor networks, WSNs）由大量的傳感節點構成，且通過這些節點觀察或測量環境[1]，或者檢測事件的發生，再將感測數據傳輸至基站（信宿）[2]。依據節點部署類型、部署策略、網絡結構、節點移動、所需的覆蓋類型以及感測模型，可將WSNs劃分為不同的類型，即靜態[3]、移動的[4]、混合[5]以及移動機器人[6-7]等，如圖1所示。在靜態的WSNs(S-WSNs)中，所部署的節點均是靜態；相反，如果所有節點是移動的，則稱為移動WSN（M-WSN）；若既有靜態的，也有移動節點，則稱為混合（H-WSN）。機器人能夠攜帶靜態節點，而不是靜態節點，則稱為無線傳感和機器人網絡（WSRN）。

依據節點的分布類型，可將WSN劃分為隨機WSN[8]和確定性WSN[9]。在有些環境中，如災難區域，相比于決定性部署，隨機部署傳感節點更便利。

若依據WSN結構，可將WSN劃分為平坦結構和簇結構。相比平坦結構，簇結構更簡單，更利于數據傳輸[10]。

圖1 WSNs的分類

移動是影響WSN覆蓋的另一個因素[11]。所謂移動是指部署后節點改變了自己的位置。無意移動會導致覆蓋空洞[12]；相反，有意移動可以提高覆蓋率、連通率，甚至提高網絡壽命[13]。

覆蓋是WSN應用的基礎。所謂覆蓋是指利用部署的傳感節點感測興趣區域的每點信息。因此，也將覆蓋稱為服務質量（quality of service, QoS）。同時，覆蓋也可據類型和等級進行劃分。

盡管可以預設傳感節點的位置進而獲取高的覆蓋率，但是，多數應用區域是偏遠且危險的。在這種情況下，只能隨機部署傳感節點。然而，隨機部署傳感節點難以保持覆蓋率。導致覆蓋率低的另一個原因是傳感節點失效，如能耗殆盡或硬件問題。一旦節點失效，就會形成覆蓋空洞。

本文在分析WSN的分類基礎上，討論覆蓋問題并進行分類；然后著重分析了部分覆蓋技術，并將具有代表性的技術進行比較。

1 WSN覆蓋問題的研究工作

目前，研究人員從不同角度討論了覆蓋問題。有些研究人員面向SWSN提出了基于能效的覆蓋算法，而有些研究人員面向MWSN，從維持連接和延長網絡壽命的角度提出覆蓋算法。圖2對目前有關覆蓋問題的研究工作的視角進行了歸類。

有些研究人員從移動和靜態角度討論覆蓋問題，如圖2最外層所示。也有部分研究人員從移動模型、連通和壽命、應用、感測模型和覆蓋類型討論覆蓋問題。

圖2 現存覆蓋問題的研究工作

圖3 覆蓋分類

1.1 全覆蓋問題

1.2 部分覆蓋問題

1.2.1 Point覆蓋

Point覆蓋又可分為Focused 覆蓋和Target覆蓋。在有些應用中，如污染監測，靠近某事件的區域覆蓋比遠區域覆蓋具有更高的優先權，這類覆蓋稱為Focused 覆蓋（F-Coverage）[15]。在文獻[15]中，作者提出了2個定位自部署算法，即貪婪優先（greedy advance, GA）和貪婪-旋轉-貪婪算法（greedy-rotation-greedy, GRG）。這2個算法使用等邊三角形棋盤形布置（equilateral triangle tessellation）最大化興趣區域的覆蓋率，并維持網絡連通率。這2個算法對節點失敗具有很強的魯棒性。然而GRG并沒有保證最大覆蓋半徑。

此外，研究人員也使用移動節點去獲取F-Coverage。例如，文獻[16]分析了利用機器人去修復覆蓋空洞的性能，并提出基于運載的覆蓋增強協議（carrier-based coverage augmentation protocol, CBCA）。CBCA通過機器人將靜態節點移至失效節點的位置，進而彌補未被覆蓋的位置。

Target覆蓋是指對已知位置的靜態目標進行連續覆蓋。目前，研究人員針對S-WSN的Target覆蓋進行大量的分析與討論[17]。

在文獻[18]中，作者利用移動特性去提高Target覆蓋，并討論了移動節點的移動策略，進而減少檢測時延。同時，將移動節點和靜態節點結合。此外，文獻[19-20]分析了靜態目標的問題，提出了光譜多尺度（spectral multiscale）覆蓋算法。文獻[21]分析了移動目標覆蓋而不是靜態目標覆蓋，并提出了動態光譜多尺度覆蓋（spectral multiscale coverage, SMC）算法。而文獻[22]提出了基于移動節點的目標覆蓋算法：移動節點調整自己位置去提高覆蓋率，并向未覆蓋的目標移動。

1.2.2 Path覆蓋

Barrier覆蓋更適合于入侵檢測和邊界監測應用[23-25]。在這類應用中，要求傳感節點監測“腰帶”（belt）區域。文獻[25]提出基于虛力的-Barrier覆蓋。該算法試圖利用閉合的belt區域的節點數實現-Barrier覆蓋，同時分析了該算法在靜態邊界比動態邊界的收斂時間更低。此外，文獻[26]提出了分布式動作協調算法，其利用移動節點提高Barrier覆蓋的初始部署，隨后保持靜態。

Sweep覆蓋是指要求周期性地監測一些點區域。例如，文獻[27]作者討論了預定興趣點（points of interest, PoI）的Sweep覆蓋問題。而文獻[28]對此問題進行了擴展，在動態而不是靜態POIs的H-WSN討論了Sweep問題。此外，文獻[29]提出巡邏點算法（patrol point algorithm, PPA）。同時，文獻[30]提出了2個啟發式算法，即MinExpand和OSweep。

文獻[31]討論了平臺的線部Sweep覆蓋，并提出基于移動節點的線Sweep的覆蓋算法。此外，文獻[32]提出了基于時限目標巡邏（time-constrained targets patrolling, TCTP）的算法。TCTP算法給每個目標分配一個權值，且移動節點依據它的權值巡邏監視每個目標。然而該算法的性能受到巡邏路徑的影響。為此，文獻[33]強調了文獻[32]的不足，并提出基于時限權重的目標巡邏（TCWTP）機制。TCWTP算法構建了不止一條巡邏路徑。

1.3 Trap覆蓋

2 性能分析

接下來從覆蓋度、特性（集中C、分布D）、傳感節點類型（同構HM、異構HT）、移動（H）、混合（H）、機器人（R）以及網絡拓撲（平坦（F）、簇（CL））等方面分析現存的部分覆蓋相關的文獻工作，如表1所示。

表1 現在的部分覆蓋算法性能

續表1

3 結束語

本文首先分析了WSNs的分類，然后對WSNs的覆蓋技術進行了討論與分析。隨后，對部分覆蓋技術進行分類，并對各類型中具有代表性的技術進行分析和比較。通過本文分析可知，理想的部分覆蓋技術應具有以下特點：采用分布式而非集中式；保證網絡的連通；滿足興趣區域的覆蓋要求；擴展性強。總之，目前國內外針對不同的WSNs應用場景提出較多的部分覆蓋技術，但是在部分覆蓋技術的研究領域中，仍有較多的問題需要解決，新的研究方向還有待發現。

[1] 唐林俊. 無線傳感網絡中部分覆蓋與擬連通冗余節點的研究[J]. 傳感技術學報, 2011, 24(6): 895-901.

[2] 班冬松, 溫俊, 蔣杰, 等. 移動無線傳感網絡-柵欄覆蓋的構建算法[J]. 軟件學報, 2011, 22(9): 2089-2103.

[3] CARDEI M, THAI M T, LI Yingshu, et al. Energy-efficient target coverage in wireless sensor networks[EB/OL]. [2019-01-27]. http://www.cse.fau.edu/~mihaela/HTML/PAPERS/TCinfocom05.pdf.

[4] YANMAZ E, GUCLU H. Stationary and mobile target detection using mobile wireless sensor networks[EB/OL]. [2019-01-27]. https://mobile.aau.at/publications/yanmaz-2010-infocom-event-detection.pdf.

[5] OZTURK C, KARABOGA D, GORKEMLI B. Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm[J]. Sensors, 2011, 11(6): 6056-6065.

[6] CHANG C Y, CHANG C T, CHEN Y C, et al. Obstacle-resistant deployment algorithms for wireless sensor networks[J]. IEEE Transaction Vehicle Technology, 2014, 58(6): 2925-2941.

[7] MEI Yongguo, XIAN Changjiu, DAS S et al. Sensor replacement using mobile robots[J]. Computing Communication, 2016, 30(13): 2615-2626.

[8] AHMED N, KANHERE S S, JHA S. Probabilistic coverage in wireless sensor networks[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/221081089_Probabilistic_Coverage_in_Wireless_Sensor_Networks.

[9] JUANG P, OKI H, WANG Y. Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with zebranet[J]. SIGARCH Computing Architecture News, 2013, 30(5): 96-107.

[10] LIAO W H, KAO Y, WU R T. Ant colony optimization based sensor deployment protocol for wireless sensor networks[J]. Expert System Application, 2014, 38(6): 6599-6605.

[11] BARTOLINI N, CALAMONERI T, PORTA T L, et al. Mobile sensor deployment in unkown fields[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/224137107_Mobile_Sensor_Deployment_in_Unknown_Fields.

[12] LUO J, WANG D, ZHANG Q. Double mobility: coverage of the sea surface with mobile sensor networks[EB/OL]. [2019-01-27]. http://www4.comp.polyu.edu.hk/~csdwang/Publication/INFOCOM09-Double.pdf.

[13] R?MER K, MATTERN F. The design space of wireless sensor networks[EB/OL]. [2019-01-27]. http://www.vs.inf.ethz.ch/publ/papers/wsn-designspace.pdf

[14] WU Yiwei, AI Chunyu, GAO Shan, et al. P-percent coverage in wireless sensor networks[EB/OL]. [2019-01-27]. https://grid.cs.gsu.edu/yli/papers/S-wasa08.pdf.

[15] LI X, FREY H, SANTORO N, et al. Focused-coverage by mobile sensor networks[EB/OL]. [2019-01-27]. http://people.scs.carleton.ca/~santoro/Reports/mass09.pdf.

[16] FALCON R, LI X, NAYAK A. Carrier-based coverage augmentation in wireless sensor and robot networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of IEEE 30th International Conference on Distributed Computing Systems Workshops. Genova, Italy: IEEE, 2015: 234-239.

[17] WANG Jianxin, LIU Ming, LU Mingming, et al. Target coverage algorithms with multiple sensing ranges in wireless sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of 2010 Military Communications Conference. San Jose, CA: IEEE, 2010: 130-135.

[18] TAN Rui, XING Guoliang, WANG Jianping, et al. Collaborative target detection in wireless sensor networks with reactive mobility[EB/OL]. [2019-01-27]. https://www.ntu.edu.sg/home/tanrui/pub/mobidetect-IWQoS.pdf.

[19] MATHEW G, MEZI? I. Spectral multiscale coverage: a uniform coverage algorithm for mobile sensor networks[EB/OL]. [2019-01-27]. http://www.geoggy.net/resources/SMC_CDC09.pdf.

[20] MATHEW G, MEZI? I. Metrics for ergodicity and design of ergodic dynamics for multi-agent systems[J]. Physica D, 2013, 240(45): 432-442.

[21] MATHEW G, SURANA A, MEZI? I. Uniform coverage control of mobile sensor networks for dynamic target detections[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 49th IEEE Conference on Decision and Control. Atlanta, GA: IEEE, 2015: 7292-7299.

[22] LIAO Zhuofan, ZHANG Shigeng, CAO Jiannong, et al. Minimizing movement for target coverage in mobile sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 32nd International Conference on Distributed Computing Systems Workshops. Macau, China: IEEE, 2012: 194-200.

[23] GHOSH A, DAS S K. Coverage and connectivity issues in wireless sensor networks: a survey[J]. Pervasive Mobile Computing, 2014, 4(3): 303-334。

[24] 范興剛, 王超, 楊靜靜, 等. 一種基于選擇框的有向K-柵欄構建算法[J]. 計算機學報, 2016, 39(5): 946-961.

[25] KONG Linghe, LIU Xuemei, LI Zhi, et al. Automatic barrier coverage formation with mobile sensor networks[EB/OL]. [2019-01-27]. http://wirelesslab.sjtu.edu.cn/~klh/2012AndBefore/KongICC2010BarrierCoverageFormation.pdf.

[26] CHENG T M, SAVKIN A V. Decentralized control of a mobile sensor network for deployment in corridor coverage[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/221042848_Decentralized_control_of_ a_mobile_sensor_network_for_deployment_in_corridor_coverage.

[27] LI Mo, CHENG Weifang, LIU Kebin, et al. Sweep coverage with mobile sensors[J]. IEEE Transactions on Mobile Computing, 2014, 10(11): 1534-1545.

[28] XI Min, WU Kui, QI Yong, et al. Run to potential: sweep coverage in wireless sensor networks[EB/OL]. [2019-01-27].https://dspace.library.uvic.ca/bitstream/handle/1828/2615/Run%20to%20potential%20Sweep%20coverage% 20in%20wireless%20sensor%20networks.pdf?sequence=1&isAllowed=y.

[29] CHU H C, WANG W K, LAI Y H. Sweep coverage mechanism for wireless sensor networks with approximate patrol times[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 7th International Conference on Ubiquitous Intelligence Computing and 7th International Conference on Autonomic Trusted Computing. Xi'an, China: IEEE, 2013: 82-87.

[30] DU Junzhao, LI Yawei, LIU Hui , et al. On sweep coverage with minimum mobile sensors[EB/OL]. [2019-01-27]. http://mail.tku.edu.tw/jingo/wireless/paper/4-30.pdf.

[31] GORAIN B, MANDAL P S. Line sweep coverage in wireless sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 6th International Conference on Communication Systems and Networks. Bangalore, India: IEEE, 2014: 1-6.

[32] WU T L, CHANG C Y. Path construction and visit scheduling for targets by using data mules[J]. IEEE Transaction System, 2014, 44(10): 1289-1300.

[33] CHANG C Y, CHEN G. Time-constrained weighted targets patrolling mechanism in wireless mobile sensor networks[J]. IEEE Transaction System, 2015, 45(6): 901-914.

[34] BALISTER P, ZHENG Zizhan, KUMAR S, et al. Trap coverage: allowing coverage holes of bounded diameter in wireless sensor networks[EB/OL]. [2019-01-27]. https://www.memphis.edu/cs/santosh-kumar/papers/trap-coverage.pdf.

[35] CHEN J, LI J.Trapping mobile targets in wireless sensor networks: an energy-efficient perspective[J]. IEEE Transaction Vehicle Technology, 2013, 62(7): 3287-3300.

Research progress of partial coverage algorithm in wireless sensor networks

XU Huibin

（School of Information Engineering, Huzhou University, Huzhou, Zhejiang 313000, China）

In order to further study on the coverage of deployed sensors in the application of WSNs, the paper discussed the related technology and development: the multidimensional classification of WSNs was given, and the concepts of full coverage and partial coverage were introduced; then the existing representative partial coverage algorithms for WSNs were summarized with their advantages and disadvantages, and the four aspects of coverage degree, distribution characteristics, sensor types and network topology were comparatively analyzed; finally, the possible research direction and trends of partial coverage algorithms were prospected.

wireless sensor network; network classification; full coverage; partial coverage; coverage degree

P228

A

2095-4999(2019)04-0019-05

徐會彬.無線傳感網絡覆蓋算法的研究進展[J].導航定位學報,2019,7(4): 19-23.（XU Huibin.Research progress of partial coverage algorithm in wireless sensor networks[J].Journal of Navigation and Positioning,2019,7(4): 19-23.）

10.16547/j.cnki.10-1096.20190404.

2019-03-03

湖州師范學院博士啟動基金項目（RK24051）；湖州師范學院科研基金項目（KX24086）。

徐會彬，男（1982—），博士，講師，研究方向為VANET安全技術/路由技術。