徐會彬

無線傳感網(wǎng)絡(luò)覆蓋算法的研究進(jìn)展

徐會彬

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

為了進(jìn)一步研究無線傳感網(wǎng)絡(luò)(WSNs)應(yīng)用中的傳感節(jié)點覆蓋問題，對相關(guān)技術(shù)性能和研究進(jìn)展進(jìn)行了闡述：對WSN進(jìn)行多維分類，給出全覆蓋、部分覆蓋的概念；著重分析近年來具有代表性的部分覆蓋技術(shù)及其優(yōu)缺點，并從覆蓋度、節(jié)點分布特性、節(jié)點類型以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)4個方面進(jìn)行比較分析；最后，總結(jié)出部分覆蓋技術(shù)的未來可能的研究策略與突破方向。

無線傳感網(wǎng)；網(wǎng)絡(luò)分類；全覆蓋；部分覆蓋；覆蓋度

0 引言

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

依據(jù)節(jié)點的分布類型，可將WSN劃分為隨機(jī)WSN[8]和確定性WSN[9]。在有些環(huán)境中，如災(zāi)難區(qū)域，相比于決定性部署，隨機(jī)部署傳感節(jié)點更便利。

若依據(jù)WSN結(jié)構(gòu)，可將WSN劃分為平坦結(jié)構(gòu)和簇結(jié)構(gòu)。相比平坦結(jié)構(gòu)，簇結(jié)構(gòu)更簡單，更利于數(shù)據(jù)傳輸[10]。

圖1 WSNs的分類

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

覆蓋是WSN應(yīng)用的基礎(chǔ)。所謂覆蓋是指利用部署的傳感節(jié)點感測興趣區(qū)域的每點信息。因此，也將覆蓋稱為服務(wù)質(zhì)量（quality of service, QoS）。同時，覆蓋也可據(jù)類型和等級進(jìn)行劃分。

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

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

1 WSN覆蓋問題的研究工作

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

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

圖2 現(xiàn)存覆蓋問題的研究工作

圖3 覆蓋分類

1.1 全覆蓋問題

1.2 部分覆蓋問題

1.2.1 Point覆蓋

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

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

Target覆蓋是指對已知位置的靜態(tài)目標(biāo)進(jìn)行連續(xù)覆蓋。目前，研究人員針對S-WSN的Target覆蓋進(jìn)行大量的分析與討論[17]。

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

1.2.2 Path覆蓋

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

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

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

1.3 Trap覆蓋

2 性能分析

接下來從覆蓋度、特性（集中C、分布D）、傳感節(jié)點類型（同構(gòu)HM、異構(gòu)HT）、移動（H）、混合（H）、機(jī)器人（R）以及網(wǎng)絡(luò)拓?fù)洌ㄆ教梗‵）、簇（CL））等方面分析現(xiàn)存的部分覆蓋相關(guān)的文獻(xiàn)工作，如表1所示。

表1 現(xiàn)在的部分覆蓋算法性能

續(xù)表1

3 結(jié)束語

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

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

[2] 班冬松, 溫俊, 蔣杰, 等. 移動無線傳感網(wǎng)絡(luò)-柵欄覆蓋的構(gòu)建算法[J]. 軟件學(xué)報, 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-柵欄構(gòu)建算法[J]. 計算機(jī)學(xué)報, 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

徐會彬.無線傳感網(wǎng)絡(luò)覆蓋算法的研究進(jìn)展[J].導(dǎo)航定位學(xué)報,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

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

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