陳業(yè)綱，徐則同

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

0 引 言

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

1 相關(guān)工作

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

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

2 問題描述

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

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

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

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

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

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

（3）目標區(qū)域的左右邊界總能被Cx中的一個節(jié)點覆蓋。

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

3 節(jié)能算法

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

3.1 1－GBMS

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

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

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

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

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

3.1.2 形成概率

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

圖1 密度分布與形成概率

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

3.2 CBMS算法

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

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

3.2.1 基準柵欄生成

當(dāng)WSN 中的所有節(jié)點都移動到最近的網(wǎng)格，則GBMS最小?；谝陨喜呗裕岢隽松傻幕鶞蕱艡谒悸?，先標記目標區(qū)域的所有節(jié)點ni，然后求出所有節(jié)點到最近網(wǎng)格 （lk）的最小距離d （ni，lk），分別計算 每行的GBMS，找出最小的GBMS即為BG 的位置。其具體算法如下：

算法1：基準柵欄生成算法

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

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

3.2.2 最優(yōu)移動

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

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

3.2.3 算法分析

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

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

圖2 節(jié)點密度與移動距離和

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

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

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

5 性能分析

為了研究此算法，從平均移動距離和與其他的柵欄覆蓋算法進行了比較。

5.1 平均移動距離

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

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

5.2 k－柵欄覆蓋與文獻 ［11］算法的比較

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

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

圖4 k值與平均移動距離

圖5 節(jié)點密度與平均移動距離之和

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

6 結(jié)束語

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

［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.