劉志坤，劉 忠，夏清濤，李朝旭

（海軍工程大學(xué)電子工程學(xué)院，武漢 430033）

基于網(wǎng)格劃分的無線傳感器網(wǎng)絡(luò)多重覆蓋算法*

劉志坤，劉 忠，夏清濤，李朝旭

（海軍工程大學(xué)電子工程學(xué)院，武漢 430033）

為了延長無線傳感器網(wǎng)絡(luò)的工作周期，在滿足網(wǎng)絡(luò)覆蓋性能的前提下，可利用調(diào)度算法讓一部分節(jié)點(diǎn)進(jìn)入休眠以節(jié)省能量。提出了一種基于網(wǎng)格劃分的無線傳感器網(wǎng)絡(luò)多重覆蓋算法，新算法包括冗余節(jié)點(diǎn)判斷和節(jié)點(diǎn)調(diào)度兩部分。將節(jié)點(diǎn)覆蓋區(qū)域劃分為多個網(wǎng)格，通過判斷各個網(wǎng)格是否滿足覆蓋要求，進(jìn)而判斷節(jié)點(diǎn)是否冗余。新算法給出了邊界冗余節(jié)點(diǎn)判據(jù)，在調(diào)度過程中能夠克服邊界效應(yīng)的影響，同時通過冗余節(jié)點(diǎn)能量比較，避免了休眠沖突和覆蓋盲區(qū)的產(chǎn)生。仿真結(jié)果表明，與傳統(tǒng)的CPNSS算法相比，新算法對冗余節(jié)點(diǎn)的判斷更為準(zhǔn)確，在網(wǎng)絡(luò)工作集和平均覆蓋度兩項(xiàng)性能評價指標(biāo)上均優(yōu)于傳統(tǒng)調(diào)度算法，且對網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量增加造成的影響不敏感，能夠有效地減少網(wǎng)絡(luò)冗余，起到了提升網(wǎng)絡(luò)性能的效果。

無線傳感器網(wǎng)絡(luò)，多重覆蓋，網(wǎng)格，冗余

引言

無線傳感器網(wǎng)絡(luò)在工業(yè)控制、環(huán)境監(jiān)測、醫(yī)療衛(wèi)生、智能家居、戰(zhàn)場監(jiān)測等諸多民用和軍事領(lǐng)域有著廣泛的應(yīng)用［1-2］。在這些應(yīng)用中，各個傳感器節(jié)點(diǎn)分別采集其周圍的信息，將這些數(shù)據(jù)發(fā)送并整合，從而獲得整個區(qū)域內(nèi)的完整狀況。因此，覆蓋問題是該領(lǐng)域的基礎(chǔ)性問題之一。根據(jù)節(jié)點(diǎn)散布方式不同，覆蓋可分為確定覆蓋和隨機(jī)覆蓋兩種［3］。確定覆蓋常用于友好型環(huán)境，比如室內(nèi)［4］。而在污染區(qū)域或是戰(zhàn)場等惡劣環(huán)境中，由于難以準(zhǔn)確布放節(jié)點(diǎn)，大多采用飛機(jī)、艦船等進(jìn)行隨機(jī)散播，稱之為隨機(jī)覆蓋。

對于隨機(jī)覆蓋，為了保證網(wǎng)絡(luò)覆蓋質(zhì)量，必須采用高密度節(jié)點(diǎn)部署，以免出現(xiàn)覆蓋盲區(qū)，這樣做的后果是在覆蓋區(qū)域內(nèi)出現(xiàn)大量冗余節(jié)點(diǎn)。這些冗余節(jié)點(diǎn)如果處于工作狀態(tài)，不但浪費(fèi)了整個網(wǎng)絡(luò)的能量，縮短了網(wǎng)絡(luò)的存活周期，而且會帶來通信干擾等一系列問題［5］。通常較合理的做法是采用節(jié)點(diǎn)調(diào)度控制算法，僅保留能夠保證網(wǎng)絡(luò)連通度和覆蓋質(zhì)量的部分節(jié)點(diǎn)處于工作狀態(tài)，讓其他節(jié)點(diǎn)進(jìn)入休眠狀態(tài)以節(jié)省能量，從而延長網(wǎng)絡(luò)壽命。調(diào)度控制算法研究的關(guān)鍵之處在于冗余節(jié)點(diǎn)的判別［6-12］。

通過文獻(xiàn)［6-12］的分析，發(fā)現(xiàn)存在的缺陷主要集中于兩點(diǎn)：一是給出的冗余節(jié)點(diǎn)判據(jù)不準(zhǔn)確，二是集中式算法不適合大規(guī)模網(wǎng)絡(luò)。例如文獻(xiàn)［6］沒有考慮節(jié)點(diǎn)覆蓋區(qū)域可能出現(xiàn)過多的覆蓋重疊，導(dǎo)致工作節(jié)點(diǎn)數(shù)量過多。文獻(xiàn)［7］給出的冗余節(jié)點(diǎn)判據(jù)為必要而非充分條件，因此，會出現(xiàn)覆蓋盲點(diǎn)。同時，該協(xié)議沒有考慮節(jié)點(diǎn)由休眠狀態(tài)轉(zhuǎn)入工作狀態(tài)對網(wǎng)絡(luò)覆蓋度的貢獻(xiàn)，因此，導(dǎo)致覆蓋效率偏低，產(chǎn)生節(jié)點(diǎn)冗余。文獻(xiàn)［8-9］的冗余判據(jù)則為充分非必要條件，同樣會導(dǎo)致多余的工作節(jié)點(diǎn)。文獻(xiàn)［10］則需要集中式計(jì)算并且無法保證對目標(biāo)區(qū)域的完全覆蓋。文獻(xiàn)［11］則僅給出了集中式算法?；谏鲜龅难芯浚疚奶岢鲆环N基于網(wǎng)格劃分的分布式k-覆蓋調(diào)度算法，簡稱 GPSA（Grid Plotting based Scheduling Algorithm）。

1 模型及相關(guān)定義

1.1 網(wǎng)絡(luò)模型

假設(shè)目標(biāo)區(qū)域?yàn)槎S平面，區(qū)域中已隨機(jī)布放足夠多的節(jié)點(diǎn)，通過合理的調(diào)度算法選出其中部分節(jié)點(diǎn)工作即可以滿足k重覆蓋要求，其他節(jié)點(diǎn)可進(jìn)入休眠狀態(tài)，在必要的時候再被喚醒。節(jié)點(diǎn)的感知模型采用常見的0-1模型（布爾模型）［13］：傳感器節(jié)點(diǎn)的感知區(qū)域?yàn)橐怨?jié)點(diǎn)為圓心，探測距離為半徑的圓。網(wǎng)絡(luò)中所有節(jié)點(diǎn)為同構(gòu)節(jié)點(diǎn)，具有相同的探測半徑和通信半徑，并且滿足通信半徑大于兩倍的探測半徑，文獻(xiàn)［7］證明了在此條件下，網(wǎng)絡(luò)的連通性問題包含在覆蓋性問題之中，不需要單獨(dú)作考慮。網(wǎng)絡(luò)通過同步時鐘保持時間同步，網(wǎng)絡(luò)中的節(jié)點(diǎn)位置通過GPS設(shè)備或者自定位算法［14］獲得，本文中作為已知條件使用。節(jié)點(diǎn)在部署后不再移動，也不允許外界進(jìn)行維護(hù)。

1.2 相關(guān)定義

定義2：對于區(qū)域A中的節(jié)點(diǎn)si和任意其他節(jié)點(diǎn)sj，sj與si之間的歐式距離小于等于它們的探測距離之和，即d（si，sj）≤rsi+rsj，則稱節(jié)點(diǎn)sj為si的鄰節(jié)點(diǎn)。由于本文假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)同構(gòu)，因此，滿足d（si，sj）≤2rs即可。

定義3：區(qū)域A中的任何一點(diǎn)至少可以被k個節(jié)點(diǎn)感知到，則稱區(qū)域A被k覆蓋。

定義4：區(qū)域A內(nèi)的節(jié)點(diǎn)si，其覆蓋圓域內(nèi)的任何一點(diǎn)都可以被其他k個節(jié)點(diǎn)感知到，則稱節(jié)點(diǎn)si為k重覆蓋要求下的冗余節(jié)點(diǎn)。

2 節(jié)點(diǎn)調(diào)度算法GPSA

對于傳感器網(wǎng)絡(luò)而言，如果非冗余節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，網(wǎng)絡(luò)的覆蓋水平會下降，而冗余節(jié)點(diǎn)進(jìn)入休眠后，不僅不會降低覆蓋水平，而且可以提升網(wǎng)絡(luò)性能。因此，為了保證網(wǎng)絡(luò)的覆蓋質(zhì)量，首先應(yīng)甄別出冗余節(jié)點(diǎn)，而后采用合理的調(diào)度算法使之進(jìn)入休眠狀態(tài)。

2.1 冗余節(jié)點(diǎn)判定準(zhǔn)則

本文給出一種基于網(wǎng)格劃分的冗余節(jié)點(diǎn)判定法則。具體描述如下：

設(shè)網(wǎng)絡(luò)要求k覆蓋，對節(jié)點(diǎn)si的覆蓋圓作以其坐標(biāo)（xi，yi）為中心，2rs為邊長的外切正方形，而后對其采用正方形網(wǎng)格劃分，計(jì)算節(jié)點(diǎn)si與各網(wǎng)格中心點(diǎn)Oi的距離，若在rs之內(nèi)，將此網(wǎng)格中心點(diǎn)放入集合M，依次檢測M中的元素是否被k覆蓋。顯然，節(jié)點(diǎn)si只可能與其鄰節(jié)點(diǎn)存在覆蓋重疊部分，因此，只需判斷M中的元素是否被si的鄰節(jié)點(diǎn)k覆蓋即可。如果存在某網(wǎng)格未被k個鄰節(jié)點(diǎn)覆蓋，則認(rèn)為節(jié)點(diǎn)si非冗余節(jié)點(diǎn)，如果M中所有點(diǎn)均被k個鄰節(jié)點(diǎn)覆蓋，則判斷si為冗余節(jié)點(diǎn)。

顯然有一部分網(wǎng)格在節(jié)點(diǎn)si的覆蓋范圍之外，因此，不需要檢測，如下頁圖1所示，標(biāo)注T的網(wǎng)格是需要進(jìn)行覆蓋檢測的。網(wǎng)格是否需要檢測的判據(jù)是：網(wǎng)格中心到節(jié)點(diǎn)的距離小于等于節(jié)點(diǎn)的探測半徑。設(shè)網(wǎng)格中心坐標(biāo)為（gx，gy），則判決式為：

網(wǎng)格劃分得越小，結(jié)果越準(zhǔn)確，但計(jì)算越復(fù)雜，因此，網(wǎng)格的大小可以根據(jù)實(shí)際情況確定，以滿足具體應(yīng)用要求為準(zhǔn)。

該判定準(zhǔn)則不僅對普通節(jié)點(diǎn)有效，進(jìn)一步完善后同樣適用于處于監(jiān)測區(qū)域邊界的節(jié)點(diǎn)，這是很多傳統(tǒng)算法無法實(shí)現(xiàn)的。如下頁圖2所示，以目標(biāo)矩形區(qū)域的左下頂點(diǎn)為坐標(biāo)原點(diǎn)O，矩形的下邊界和左邊界為x軸和y軸，以上述方法對邊界節(jié)點(diǎn)s1的覆蓋圓進(jìn)行網(wǎng)格劃分后，處于目標(biāo)區(qū)域外的網(wǎng)格中心坐標(biāo)為（x1i，y1i），則x1i和y1i必然有負(fù)值或者大于區(qū)域的最大邊界值xmax或ymax的情況出現(xiàn)。因此，只需在找出待檢測網(wǎng)格中心后，刪除集合中坐標(biāo)值為負(fù)值或者大于區(qū)域的最大邊界值xmax或ymax的點(diǎn)，即可得到最終的待檢測網(wǎng)格集合。

圖1 檢測網(wǎng)格示意圖

圖2 邊界節(jié)點(diǎn)冗余判別示意圖

2.2 調(diào)度算法

以冗余節(jié)點(diǎn)判斷準(zhǔn)則為基礎(chǔ)，下一步可以建立節(jié)點(diǎn)調(diào)度協(xié)議，使各個節(jié)點(diǎn)盡可能處于合理的狀態(tài)，提升網(wǎng)絡(luò)的監(jiān)測效率。

在GPSA算法中，節(jié)點(diǎn)存在4種狀態(tài)：工作狀態(tài)、待工作狀態(tài)、休眠狀態(tài)和待休眠狀態(tài)。第一步是初始化階段，此階段節(jié)點(diǎn)剛剛隨機(jī)部署完畢，所有節(jié)點(diǎn)處于工作狀態(tài)，各節(jié)點(diǎn)廣播自己的位置信息，獲取鄰節(jié)點(diǎn)的位置信息，建立自己的鄰節(jié)點(diǎn)集合，為節(jié)省能量，廣播半徑取兩倍探測半徑，這是因?yàn)閮杀短綔y半徑距離之外不可能存在鄰節(jié)點(diǎn)。第2階段是節(jié)點(diǎn)狀態(tài)判定階段，主要是通過冗余節(jié)點(diǎn)判定準(zhǔn)則找出冗余節(jié)點(diǎn)。第3階段是退避階段，如果所有節(jié)點(diǎn)同時作出判定，很可能會出現(xiàn)覆蓋盲點(diǎn)。如圖3所示，節(jié)點(diǎn)s1和節(jié)點(diǎn)s1根據(jù)冗余節(jié)點(diǎn)判定準(zhǔn)則均認(rèn)為自身為冗余節(jié)點(diǎn)（單重覆蓋的情況下），但如果同時進(jìn)入休眠狀態(tài)，則會出現(xiàn)覆蓋盲區(qū)，如圖3（b）所示，因此，需要引入退避機(jī)制，從兩者之中選出一個進(jìn)入休眠，另一個則保留作為工作節(jié)點(diǎn)。本文采用一種基于能量選擇的策略［11］：在分別判定自身位冗余節(jié)點(diǎn)之后，節(jié)點(diǎn)s1和節(jié)點(diǎn)s2進(jìn)入待休眠狀態(tài)，等待Tw時間段再確定是否進(jìn)入休眠狀態(tài)，在Tw時間內(nèi)分別向各自的鄰節(jié)點(diǎn)廣播一個包含自身能量信息的Quit消息，收到鄰節(jié)點(diǎn)的Quit消息后，s1和s2將比較當(dāng)前各自的能量，能量較低的進(jìn)入休眠狀態(tài)，并廣播一個Sleep消息，使其鄰節(jié)點(diǎn)更新鄰節(jié)點(diǎn)集合，能量較高的則繼續(xù)工作。如果直到Tw溢出都沒有收到Quit消息，則進(jìn)入休眠狀態(tài)。進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)，設(shè)置休眠計(jì)時器Ts，當(dāng)Ts溢出，則轉(zhuǎn)入待工作狀態(tài)，廣播一個ASK消息，索取鄰節(jié)點(diǎn)信息，收到ASK消息的節(jié)點(diǎn)則再次廣播自身的位置信息，并更新自己的鄰節(jié)點(diǎn)集合。

圖3 冗余節(jié)點(diǎn)休眠沖突

整個調(diào)度過程如圖4所示。

圖4 調(diào)度算法示意圖

3 仿真及性能評估

因?yàn)樵诩僭O(shè)中已承認(rèn)目標(biāo)區(qū)域內(nèi)節(jié)點(diǎn)密度足夠大，因此，本文主要采用工作集和平均覆蓋度兩項(xiàng)指標(biāo)來評估算法的性能。工作集是指為滿足監(jiān)測要求，由調(diào)度算法從網(wǎng)絡(luò)中選出的工作節(jié)點(diǎn)的數(shù)量。工作集越小，傳感器網(wǎng)絡(luò)總體能耗就越小，通信沖突越少，調(diào)度算法的性能越好。平均覆蓋度是指工作集中，能夠監(jiān)測到區(qū)域內(nèi)發(fā)生的任一事件源的節(jié)點(diǎn)數(shù)量［15］。平均覆蓋度越低，說明冗余節(jié)點(diǎn)數(shù)量越少，調(diào)度算法的性能越出色。在仿真中平均覆蓋度的計(jì)算方法為：將目標(biāo)區(qū)域劃分為單元格，假設(shè)每個單元格的中心有1個事件發(fā)生，計(jì)算能夠覆蓋該單元格中心的節(jié)點(diǎn)數(shù)量，即為該事件的覆蓋度。將所有事件的覆蓋度之和取平均，即得到網(wǎng)絡(luò)平均覆蓋度。

將本文提出的GPSA算法與文獻(xiàn)［6］中提出的經(jīng)典算法CPNSS進(jìn)行仿真比較，仿真工具采用Matlab7.1進(jìn)行，為了便于算法比較，參數(shù)設(shè)置與文獻(xiàn)［6］相同，具體為：區(qū)域大小為50 m×50 m，節(jié)點(diǎn)數(shù)取100個～300個，節(jié)點(diǎn)的探測半徑為10 m，通信半徑為20 m。在相同條件下取10次仿真的均值作為最終的結(jié)果進(jìn)行比較。

圖5是不同調(diào)度算法下的工作集數(shù)量（單重覆蓋需求）。可以看出，在部署節(jié)點(diǎn)總數(shù)相同的條件下，GPSA算法的工作集均小于CPNSS算法，也就是說GPSA算法較之CPNSS算法可以用更少的節(jié)點(diǎn)滿足區(qū)域監(jiān)測要求。同時發(fā)現(xiàn)，隨著節(jié)點(diǎn)部署數(shù)量的增加，CPNSS算法的工作集在緩慢增大，分析主要有兩點(diǎn)原因造成：一是由于該算法沒有考慮邊界節(jié)點(diǎn)的影響，隨著隨機(jī)部署節(jié)點(diǎn)數(shù)量的增加，靠近區(qū)域邊界的節(jié)點(diǎn)數(shù)也在增加，這部分節(jié)點(diǎn)不會被判定為冗余節(jié)點(diǎn)，從而導(dǎo)致了整個工作集的增大。另一個可能的原因是，由于其判據(jù)為充分非必要條件，因此，節(jié)點(diǎn)部署總數(shù)越多，漏判的數(shù)量也會有所增大。而GPSA算法由于其判據(jù)相對精確且考慮了邊界效應(yīng)，因此，工作集大小受節(jié)點(diǎn)數(shù)量影響較小，相對保持穩(wěn)定。

圖5 節(jié)點(diǎn)數(shù)與工作集的關(guān)系

圖6 節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)平均覆蓋度的關(guān)系

圖6是不同調(diào)度算法下的網(wǎng)絡(luò)平均覆蓋度（單重覆蓋需求）。在初始情況下，即沒有進(jìn)行任何節(jié)點(diǎn)調(diào)度，所有節(jié)點(diǎn)均處在活躍狀態(tài)時，部署100個節(jié)點(diǎn)時網(wǎng)絡(luò)的平均覆蓋度高達(dá)11.283，并且隨著節(jié)點(diǎn)數(shù)量的增大而急劇增加，說明網(wǎng)絡(luò)處于高度冗余覆蓋狀態(tài)。經(jīng)CPNSS算法調(diào)度之后，部分節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，100個節(jié)點(diǎn)時網(wǎng)絡(luò)的平均覆蓋度降低到4.727，網(wǎng)絡(luò)的冗余程度得到了明顯的改善，隨著節(jié)點(diǎn)總數(shù)增加到了300個，網(wǎng)絡(luò)平均覆蓋度緩慢增加到了7.182，說明CPNSS調(diào)度算法能夠有效地降低冗余度。而經(jīng)過本文GPSA算法對網(wǎng)絡(luò)進(jìn)行優(yōu)化后，網(wǎng)絡(luò)的平均覆蓋度得到了進(jìn)一步降低，并且對部署節(jié)點(diǎn)數(shù)量增加造成的影響不敏感，說明該算法對網(wǎng)絡(luò)中冗余節(jié)點(diǎn)的判別非常準(zhǔn)確，其降低網(wǎng)絡(luò)冗余效果最優(yōu)。

對于滿足不同覆蓋要求情況下，兩種算法的工作集大小進(jìn)行比較，網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量為600個，網(wǎng)絡(luò)的覆蓋要求從1重增加到3重，其他仿真條件不變，結(jié)果如表1所示。從表1可以看出，隨著覆蓋重數(shù)的增加，CPNSS算法和GPSA算法的工作集都會增大。對于不同的覆蓋重數(shù)，GPSA算法得到的工作集均小于CPNSS算法的結(jié)果。

表1 重覆蓋下的節(jié)點(diǎn)工作集大小

4 結(jié) 論

本文提出的GPSA調(diào)度算法，通過對每個節(jié)點(diǎn)覆蓋區(qū)域進(jìn)行網(wǎng)格劃分，能較準(zhǔn)確地找出網(wǎng)絡(luò)中的冗余節(jié)點(diǎn)并使之休眠，可以克服邊界效應(yīng)，同時該算法考慮到了節(jié)點(diǎn)能量這一因素，保護(hù)了低能量節(jié)點(diǎn)，均衡了節(jié)點(diǎn)能耗，避免了由休眠節(jié)點(diǎn)造成的覆蓋盲區(qū)，從而在不影響網(wǎng)絡(luò)監(jiān)測性能的前提下，降低了網(wǎng)絡(luò)整體能耗，延長了網(wǎng)絡(luò)存活期。仿真試驗(yàn)表明，該算法優(yōu)于經(jīng)典的CPNSS算法。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks:a Survey ［J］.Computer Networks，2002，38（4）:393-422.

［2］李建中，高 宏.無線傳感器網(wǎng)絡(luò)的研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2008，45（1）：1-15.

［3］王 偉，林 峰，周激流.無線傳感器網(wǎng)絡(luò)覆蓋問題的研究進(jìn)展［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（1）：32-35.

［4］霍宏偉，郜 帥，牛延超，等.基于室內(nèi)傳播模型的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略研究［J］.中國工程科學(xué)，2008，10（9）：64-69.

［5］王換招，孟凡治，李增智.高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議［J］.軟件學(xué)報，2010，21（12）：3124-3137.

［6］ Tian D I，Georganas N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks［C］// Proceedings of ACM Workshop on Wireless Sensor Networks and Applications.New York:ACM，2002:124-128.

［7］Wang X R，Xing G L，Zhang Y F.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks［C］// Proceedings of the 1st ACM Conference on Embedded Networked Sensor Systems.New York:ACM，2003:234-236.

［8］Huang C F，Tseng Y C.A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks［J］.Journal of Internet Technology，Special Issue on Wireless ad Hoc Sensor Networks，2004，12（3）:2356-2359.

［9］孫 超，趙路路，張 影，等.無線傳感器網(wǎng)絡(luò)分簇拓?fù)涞母采w區(qū)域節(jié)點(diǎn)調(diào)度優(yōu)化算法研究［J］.傳感技術(shù)學(xué)報，2010，23（1）：116-121.

［10］鮑喜榮，張 石，薛定宇.基于改進(jìn)的Voronoi劃分的集中式算法的無線傳感器網(wǎng)絡(luò)覆蓋問題研究［J］.信息與控制，2009，38（5）：620-623.

［11］陶 洋，曾曉玲，羅 衛(wèi).無線傳感器網(wǎng)絡(luò)中覆蓋控制算法研究及改進(jìn)［J］.計(jì)算機(jī)應(yīng)用，2010，30（6）：1459-1462.

［12］陸克中，孫宏元.無線傳感器網(wǎng)絡(luò)最小覆蓋集的貪婪近似算法［J］.軟件學(xué)報，2010，21（10）：2656-2665.

［13］Onur E，Ersoy C，Delic H.How Many Sensors for an Acceptable Breach Probability Level［J］.Computer Communications，2006，29（2）：172-182.

［14］劉志坤，劉 忠，唐小明.基于改進(jìn)型粒子群優(yōu)化的節(jié)點(diǎn)自定位算法［J］.中南大學(xué)學(xué)報（自然科學(xué)版），2012，43（4）：1371-1376.

［15］陶 洋，林艷芬，黃宏成.無線傳感器網(wǎng)絡(luò)中的覆蓋優(yōu)化算 法 研 究 ［J］.計(jì) 算 機(jī) 工 程 ，2011，37（1）：119-121，124.

Multi-coverage Algorithm Based on Grid-plotting in WSN

LIU Zhi-kun，LIU Zhong，XIA Qing-tao，LI Chao-xu
（School of Electronic Engineering，Naval University of Engineering，Wuhan 430033，China）

In order to prolong the lifetime of Wireless Sensor Netwoks（WSN）while keeping the coverage performance，the scheduling algorithm can make some nodes sleep and the energy is saved.A multi-coverage algorithm based on grid-plotting in WSN is proposed，it contains two parts which are redundant node judging and node scheduling.The node coverage area is divided into grids and the redundant nodes are determined through judging each grid can satisfy the coverage requirement or not. The boundary redundant node judging rule is given and the boundary effect influence can be overcome in the scheduling process.Besides，the off-duty conflict and coverage blind area are avoided. Simulation results show that，compares with CPNSS，the new algorithm can judge redundant nodes more correctly and has better performance on two evaluating indicators:on-duty node number and average coverage degree.It's not sensitive to the influence of the increase of node number and can reduce the redundancy of network effectively.It achieves the purpose of improving the performance of network.

wireless sensor networks，multi-coverage，grid，redundancy

TP393.1

A

1002-0640（2014）11-0080-04

2013-08-05

2013-11-07

國家自然科學(xué)基金（60972160）；“十二五”國防科技預(yù)研基金；海軍工程大學(xué)自然科學(xué)基金資助項(xiàng)目（201300000446）

劉志坤（1984- ），男，山東壽光人，博士，講師。研究方向：系統(tǒng)工程、水下自組織網(wǎng)絡(luò)。