有限移動(dòng)WSNs柵欄覆蓋算法

陳業(yè)綱，徐則同

（1.長江師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，重慶408000；2.中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京100190）

0 引 言

覆蓋問題是衡量WSN 服務(wù)質(zhì)量的一項(xiàng)關(guān)鍵指標(biāo)。在研究該問題時(shí)，要考慮節(jié)點(diǎn)的部署方式、感知范圍和通信范圍、能量有效性、算法特征以及節(jié)點(diǎn)的移動(dòng)性這5個(gè)方面。根據(jù)節(jié)點(diǎn)是否具有移動(dòng)性，將覆蓋分為靜止和移動(dòng)覆蓋，由于前者對節(jié)點(diǎn)的部署是隨機(jī)的，可能會(huì)出現(xiàn)空隙，要解決此問題需要提高部署密度，但會(huì)造成節(jié)點(diǎn)的冗余。若節(jié)點(diǎn)具有有限的移動(dòng)能力，當(dāng)隨機(jī)部署完成后，通過節(jié)點(diǎn)的移動(dòng)進(jìn)行重新分布，最終形成滿足條件的柵欄覆蓋。但如何構(gòu)成節(jié)能高效的覆蓋算法是一個(gè)難點(diǎn)。

1 相關(guān)工作

柵欄覆蓋研究了監(jiān)控目標(biāo)穿越WSN 時(shí)被檢測到是與否的問題，它反應(yīng)了對目標(biāo)區(qū)域的感應(yīng)和監(jiān)視能力，其目標(biāo)是找到一條或多條從進(jìn)入到離開目標(biāo)區(qū)域的路徑，不同的模型對監(jiān)控的目標(biāo)提供了不同的質(zhì)量，根據(jù)模型的不同，將柵欄覆蓋分為最佳覆蓋 （best coverage）、最壞覆蓋（worst coverage）和暴露穿越 （exposure）。

最佳覆蓋就是目標(biāo)穿越時(shí)被節(jié)點(diǎn)發(fā)現(xiàn)的最大概率，最壞覆蓋是目標(biāo)穿越時(shí)不被發(fā)現(xiàn)的最小概率，最佳最壞覆蓋只考慮傳感器的節(jié)點(diǎn)距離，在文獻(xiàn) ［1－4］中進(jìn)行了相關(guān)的研究；暴露穿越既考慮了目標(biāo)暴露又考慮了感應(yīng)強(qiáng)度，在文獻(xiàn) ［5－8］研究了此問題。前兩者的缺點(diǎn)是集中式算法，需要預(yù)先知道節(jié)點(diǎn)的位置，沒有考慮實(shí)際中環(huán)境的影響；后者存在運(yùn)行時(shí)間與暴露精度的矛盾，沒有考慮節(jié)點(diǎn)運(yùn)動(dòng)造成的影響。為了解決這些問題，本項(xiàng)目提出了移動(dòng)WSN的柵欄覆蓋節(jié)能算法。

2 問題描述

假定目標(biāo)區(qū)域 （o）是長為l，寬為w 的矩形區(qū)域，在該區(qū)域內(nèi)假定隨機(jī)部署m 個(gè)移動(dòng)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)具有相同的感知半徑 （Rs）和通信半徑 （Rc）。且部署完成后網(wǎng)絡(luò)是連通的。由于部署是隨機(jī)的，不能保證該區(qū)域的柵欄覆蓋，加之節(jié)點(diǎn)能量有限，移動(dòng)時(shí)應(yīng)盡量減少移動(dòng)的距離，以延長網(wǎng)絡(luò)的生命期。滿足要求作如下形式化定義。

定義1 k－柵欄覆蓋：給定一個(gè)狹長區(qū)域，假定所有穿越該區(qū)域的路徑都被至少一個(gè)傳感器覆蓋，則該區(qū)域被柵欄覆蓋。當(dāng)穿越時(shí)至少被K 個(gè)傳感器感知，稱為K－柵欄覆蓋。

定義2 最小移動(dòng)距離和 （barrier coverage min－sum，BCMS）：在該區(qū)域如何找到k個(gè)不相交的子集，且每個(gè)子集中的節(jié)點(diǎn)重新部署后，該區(qū)域是K－柵欄覆蓋，且滿足移動(dòng)距離之和最小。

由于傳感器節(jié)點(diǎn)具有有限的移動(dòng)能力，經(jīng)過定義2后移動(dòng)后可以是任何形式的曲線，為了對目標(biāo)區(qū)域進(jìn)行監(jiān)控，將該區(qū)域劃分成n個(gè)網(wǎng)格，在該區(qū)域的長度方向上的網(wǎng)格數(shù)為int（l／Rs），寬度上的網(wǎng)格數(shù)為int（w／Rc），將網(wǎng)格的中心點(diǎn)作為該網(wǎng)格的重心。當(dāng)目標(biāo)進(jìn)行穿越時(shí)能被一個(gè)傳感器節(jié)點(diǎn)感知，此時(shí)就實(shí)現(xiàn)了1柵欄覆蓋。如果至少能被k個(gè)傳感器節(jié)點(diǎn)感應(yīng)，相應(yīng)就實(shí)現(xiàn)了k柵欄覆蓋。下面對網(wǎng)格和1柵欄覆蓋作如下形式化定義。

定義3 網(wǎng)格柵欄 （GB）：在目標(biāo)區(qū)域和以網(wǎng)格為中心的點(diǎn)集 （g），若傳感器節(jié)點(diǎn)Cx滿足：

（2）Ci屬于除Cx中橫坐標(biāo)最小的節(jié)點(diǎn)，Cj屬除Cx中橫坐標(biāo)最大的節(jié)點(diǎn)，總存在節(jié)點(diǎn)Ck和Cq（k≠q），有：（d（ci，ck）≤2Rs）∩（xk≤xi）且（d（cj，cq）≤2Rs）∩（xq≤xj），即Cx中任意節(jié)點(diǎn)，總有不相同的左右鄰居相互重疊的一個(gè)感知區(qū)域。

（3）目標(biāo)區(qū)域的左右邊界總能被Cx中的一個(gè)節(jié)點(diǎn)覆蓋。

定義4 柵欄網(wǎng)格最小移動(dòng)距離和 （grid barrier minsum，GBMS）：根據(jù)上面的描述，當(dāng)移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)后，在整個(gè)區(qū)域中若形成1條柵欄網(wǎng)格，則稱1－GBMS，若形成k條柵欄網(wǎng)格，則稱k－GBMS。

3 節(jié)能算法

確定性覆蓋的一種是基于網(wǎng)格的覆蓋，為了節(jié)能，提出了一種在有限代價(jià)下，節(jié)點(diǎn)通過移動(dòng)最少距離實(shí)現(xiàn)對目標(biāo)區(qū)域的覆蓋。

3.1 1－GBMS

根據(jù)定義4，先對給定的目標(biāo)區(qū)域進(jìn)行網(wǎng)格化，同時(shí)在目標(biāo)區(qū)域左右邊界處增加一列網(wǎng)格，下面給出了1－GBMS的線性規(guī)劃描述。

3.1.1 1－GBMS的線性規(guī)劃

給定傳感器節(jié)點(diǎn)集 （S）和網(wǎng)格化后的中心點(diǎn)集 （G），增加的左列網(wǎng)格中心點(diǎn)集 （Zl）和右列中心點(diǎn)集 （Zr）增加2個(gè)節(jié)點(diǎn) （O，T），O 節(jié)點(diǎn)只能在增加的左列移動(dòng)，T節(jié)點(diǎn)只能在增加的右列移動(dòng)，對目標(biāo)區(qū)域中所有節(jié)點(diǎn)進(jìn)行編號(hào) （1－m）；用nl表示長度方向上的網(wǎng)格數(shù)；用A 表示所有節(jié)點(diǎn)集 （包括增加的節(jié)點(diǎn)）。G 表示網(wǎng)格中心點(diǎn)集 （包括增加的兩列）。xij當(dāng)其值為1時(shí)表示i節(jié)點(diǎn)移動(dòng)到第j個(gè)網(wǎng)格中心。

為了實(shí)現(xiàn)此算法作了如下假設(shè)：

每個(gè)節(jié)點(diǎn)最多只能移動(dòng)到一個(gè)網(wǎng)格中心，每個(gè)網(wǎng)格中心最多移入一個(gè)節(jié)點(diǎn)，1－GBMS看成節(jié)點(diǎn)O 到節(jié)點(diǎn)T 的一個(gè)流，若ab這2個(gè)節(jié)點(diǎn)相連的節(jié)點(diǎn)，a為前驅(qū)，b為后繼，將a看成流入節(jié)點(diǎn)b，其值為1，根據(jù)能量守恒，有進(jìn)入的流就有離開的流，將 （O，T）節(jié)點(diǎn)所在列移動(dòng)的距離其值為0，其余移動(dòng)距離為節(jié)點(diǎn)到網(wǎng)格中心的距離。在滿足上述約束下，如果找到∑dij×xij的最小值，則實(shí)現(xiàn)了1－GBMS。

3.1.2 形成概率

假定移動(dòng)傳感器節(jié)點(diǎn)以柏淞分布隨機(jī)部署于20×400 m 的區(qū)域，且其Rs為3m，移動(dòng)距離最大為12m，且初始時(shí)是連通網(wǎng)絡(luò)，節(jié)點(diǎn)的密度由0.002到0.04，在隨機(jī)生成80個(gè)／密度值，其形成概率為1－BC的個(gè)數(shù)與80的比值。下面通過100 次實(shí)驗(yàn)，使用matlab11 對1－GBMS 進(jìn)行仿真。結(jié)果如圖1所示。

圖1 密度分布與形成概率

圖1可以看出，當(dāng)密度分布小于0.015 時(shí)形成概率低于0.2，移動(dòng)傳感器網(wǎng)絡(luò)也無法形成1－GBMS，其他情況可形成1－GBMS。后面的實(shí)驗(yàn)都是建立在密度分布在0.015～0.04之間。

3.2 CBMS算法

利用上述算法可以求得最優(yōu)解，但是該算法是NPhard問題，提出一種求解該問題的近似CBMS算法。

對目標(biāo)區(qū)域進(jìn)行劃分，選擇與平行于邊界的1 行，在每個(gè)網(wǎng)格中心放置一個(gè)節(jié)點(diǎn)，這種方式稱為基準(zhǔn)柵欄（BG），本文采用文獻(xiàn) ［6］提供的算法構(gòu)建1－GBMS，當(dāng)移動(dòng)傳感器重新定位后，從節(jié)能的角度，需要移動(dòng)的節(jié)點(diǎn)數(shù)要最少且GBMS要最小。為了實(shí)現(xiàn)上述功能，應(yīng)分兩步實(shí)現(xiàn)，首先構(gòu)建BG，然后使目標(biāo)區(qū)域節(jié)點(diǎn)最少移動(dòng)。

3.2.1 基準(zhǔn)柵欄生成

當(dāng)WSN 中的所有節(jié)點(diǎn)都移動(dòng)到最近的網(wǎng)格，則GBMS最小。基于以上策略，提出了生成的基準(zhǔn)柵欄思路，先標(biāo)記目標(biāo)區(qū)域的所有節(jié)點(diǎn)ni，然后求出所有節(jié)點(diǎn)到最近網(wǎng)格 （lk）的最小距離d （ni，lk），分別計(jì)算 每行的GBMS，找出最小的GBMS即為BG 的位置。其具體算法如下：

算法1：基準(zhǔn)柵欄生成算法

（1）對目標(biāo)區(qū)域所有節(jié)點(diǎn)掃描，并標(biāo)記出每個(gè)節(jié)點(diǎn)到最近網(wǎng)格的gsd（lk）；

該算法1步求出gsd（lk），時(shí)間復(fù)雜度為O（n）；2－8步求出gsd數(shù)組，時(shí)間復(fù)雜度為O（int（w／（2Rc）），9－10步求出每一行得sr（i），時(shí)間復(fù)雜度為O（int（l／（2Rs）），故該算法的時(shí)間復(fù)雜度為O（n）。

3.2.2 最優(yōu)移動(dòng)

上述算法求出了基準(zhǔn)柵欄，下面要從m 個(gè)節(jié)點(diǎn)中如何選取最少的節(jié)點(diǎn)使之移動(dòng)，且滿足GBMS最小。稱此移動(dòng)為最優(yōu)移動(dòng)。

由文獻(xiàn) ［9］證明最優(yōu)移動(dòng)實(shí)質(zhì)上是二部圖的賦值匹配，因此可以利用二部圖的賦值匹配算法求解最優(yōu)移動(dòng)。其求解用文獻(xiàn) ［10］算法，其時(shí)間復(fù)雜度為O（x2y），其中x，y為二部圖中節(jié)點(diǎn)數(shù)，其中x ≤y。

3.2.3 算法分析

20×400m 的區(qū)域內(nèi)，節(jié)點(diǎn)密度在 ［0.015，0.04］變化，對CBMS和最優(yōu)算法進(jìn)行了模擬，如圖2所示。

圖2可以看出當(dāng)密度為0.015時(shí)，二者相差4.5%，當(dāng)密度增加到0.04時(shí)，差值變?yōu)椴坏?%，故提出近似算法能較好地替換最優(yōu)算法。

圖2 節(jié)點(diǎn)密度與移動(dòng)距離和

4 構(gòu)建k－柵欄覆蓋

GBMS算法能夠很好的解決通過上下邊界的穿越，但是當(dāng)目標(biāo)對象水平穿越時(shí)可能會(huì)出現(xiàn)漏洞，同時(shí)由于此算法只能對矩形區(qū)域進(jìn)行進(jìn)行，當(dāng)目標(biāo)區(qū)域是狹長的帶狀區(qū)域時(shí)此算法就不能滿足實(shí)際需要，為了解決上述問題，用隔離柵欄解決漏洞問題，將狹長區(qū)域中用不規(guī)則的區(qū)域分解成矩形和平行四邊形解決此問題。其主要思想如下：①將目標(biāo)區(qū)域平均分為u×v個(gè)矩形或平行四邊形，其中每個(gè)小區(qū)域長為m（l／v）寬為n（w／u）。②在目標(biāo)區(qū)域的右邊界和相鄰的2個(gè)區(qū)域中增加隔離柵欄。③在每個(gè)子區(qū)域分別執(zhí)行GBMS算法，當(dāng)所有節(jié)點(diǎn)移動(dòng)結(jié)束后，在整個(gè)區(qū)域?qū)崿F(xiàn)了k－柵欄覆蓋。

此算法的主要時(shí)間開銷在第3部，在每個(gè)子區(qū)域內(nèi)的時(shí)間復(fù)雜度為O（x2iy），xi與子區(qū)域的面積有關(guān)，y跟子區(qū)域的節(jié)點(diǎn)數(shù)有關(guān)，其節(jié)點(diǎn)的平均數(shù)量為So／（uv），So為目標(biāo)區(qū)域的面積。與全局算法相比，算法的時(shí)間復(fù)雜度低。

5 性能分析

為了研究此算法，從平均移動(dòng)距離和與其他的柵欄覆蓋算法進(jìn)行了比較。

5.1 平均移動(dòng)距離

為了研究移動(dòng)傳感器節(jié)點(diǎn)的平均移動(dòng)距離，在20×1000m 的狹長區(qū)域內(nèi)，按柏淞分布部署節(jié)點(diǎn)，其密度為0.03，在分布密度不變的情況下，圖3給出了區(qū)域長度的范圍從200到1000 m，目標(biāo)區(qū)域的節(jié)點(diǎn)的平均移動(dòng)距離。圖4給出了k－柵欄覆蓋中k值發(fā)生變化目標(biāo)區(qū)域的節(jié)點(diǎn)的平均移動(dòng)距離。

由圖3和圖4知，節(jié)點(diǎn)的平均移動(dòng)距離不隨網(wǎng)絡(luò)的長度和k值得變化而變化，說明此算法的擴(kuò)展性較好。

5.2 k－柵欄覆蓋與文獻(xiàn) ［11］算法的比較

圖5表示了k－柵欄覆蓋與文獻(xiàn) ［11］算法 （簡稱C 算法）在相同密度分布下，節(jié)點(diǎn)移動(dòng)的距離和的比較。

圖3 區(qū)域長度與平均移動(dòng)距離

圖4 k值與平均移動(dòng)距離

圖5 節(jié)點(diǎn)密度與平均移動(dòng)距離之和

由圖5知，k－柵欄覆蓋算法所有節(jié)點(diǎn)的移動(dòng)距離之和隨著密度的增加基本保持不變，而C 算法隨著密度的增加而移動(dòng)距離和增加，此說明提出的算法高于C 算法，能夠有效地改善傳感器網(wǎng)絡(luò)的覆蓋性能，并能有效地延長WSN的壽命。

6 結(jié)束語

k－柵欄覆蓋解決了集中式算法需要預(yù)先知道節(jié)點(diǎn)的位置以及未考慮實(shí)際中環(huán)境的影響的問題；既克服了運(yùn)行時(shí)間與暴露精度的矛盾，又考慮到節(jié)點(diǎn)運(yùn)動(dòng)造成的影響。利用節(jié)點(diǎn)具有有限的移動(dòng)性，通過分治法將狹長的區(qū)域分成子區(qū)域，在子區(qū)域內(nèi)通過節(jié)點(diǎn)向最近的網(wǎng)格中心移動(dòng)，使之平均移動(dòng)距離最小，實(shí)驗(yàn)仿真表明，提出的算法接近最優(yōu)解，時(shí)間復(fù)雜度低，具有可擴(kuò)展性。在后面的研究中擬在混合網(wǎng)絡(luò) （移動(dòng)和靜止）中研究覆蓋。

［1］Yu L，Li JZ，Cheng SY.Approximate continuous aggregation via time window based compression and sampling in WSNs［J］.Wireless Sensor Networks，2010，2 （9）：675－682.

［2］Cortes J，Martinez S，Karatas T，et al.Cove－rage control for mobile sensing networks［J］.IEEE Trans on Robotics and Automation，2004，20 （2）：243－255.

［3］Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage problems in wireless ad－h(huán)oc sensor network ［C］／／Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE，2001：1380－1387.

［4］Li JZ，Cheng SY.（ε，δ）－Approximate aggregation algorithms in dynamic sensor networks［J］.IEEE Trans on Parallel and Distributed Systems，2012，23 （3）：385－396.

［5］Meguerdichian S，Koushanfar F，Qu G，et al.Exposure in wireless ad－h(huán)oc sensor networks［C］／／Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.New York：ACM Press，2001：139－150.

［6］Bi R，Li JZ，Cheng SY.（ε，δ）－Approximate top－k query processing algorithm in wireless sensor networks ［J］.Journal on Communications，2011，32 （8）：45－54.

［7］Veltri G，Huang Q，Qu G，et al.Minimal and maximal exposure path algorithms for wireless embedded sensor networks［C］／／Proceedings of the 1st International Conference on Embedded Networked Sensor Systems.New York：ACM Press，2003：40－50.［8］Adlakha S，Srivastava M.Critical density thresholds for coverage in wireless sensor networks ［C］／／Wireless Communications and Networking.New Orleans：IEEE Press，2003：1615－1620.

［9］BAN Dongsong，WEN Jun，JIANG Jie，et al.Constructing k－barrier coverage in mobile wireless sensor networks ［J］.Journal of Software，2011，22 （9）：2089－2102.

［10］LI Jing，WANG Shiying.An algorithm for constructing the maximum matching graphs on bigraphs ［J］.ACTA Electronica Sinica，2010，38 （1）：161－166.

［11］Shen CX，ChengWF，Liao XK，PengSL.Barrier coverage with mobile sensor［C］／／International Symposium on Parallel Architectures，Algorithms，and Networks.New Jersey：IEEE Press，2008：99－104.