無線傳感器網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)序列的覆蓋算法

寧菲菲，王國(guó)軍，邢蕭飛

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083)

無線傳感器網(wǎng)絡(luò)是當(dāng)前十分熱門的研究課題，得到了越來越廣泛的關(guān)注[1]。無線傳感器網(wǎng)絡(luò)是一個(gè)由大量廉價(jià)的傳感器節(jié)點(diǎn)組成的無線自組織網(wǎng)絡(luò)。每個(gè)傳感器節(jié)點(diǎn)由計(jì)算單元、存儲(chǔ)單元、傳感器單元和無線通信單元等構(gòu)成[2]。無線傳感器網(wǎng)絡(luò)被廣泛應(yīng)用在國(guó)家基礎(chǔ)設(shè)施、工業(yè)生產(chǎn)環(huán)境的安全監(jiān)控、醫(yī)療護(hù)理監(jiān)控、自然生態(tài)環(huán)境監(jiān)測(cè)和動(dòng)植物棲息地的科學(xué)觀測(cè)等領(lǐng)域。覆蓋作為無線傳感器網(wǎng)絡(luò)中的一個(gè)基本問題，它要解決的問題是在傳感器節(jié)點(diǎn)被布置到目標(biāo)區(qū)域后保證該區(qū)域能夠被傳感器節(jié)點(diǎn)有效監(jiān)控。文獻(xiàn)[3]中將傳感器網(wǎng)絡(luò)的覆蓋問題分為3大類：區(qū)域覆蓋[4-6]、目標(biāo)覆蓋[7-8]和障礙覆蓋[9]。由于傳感器節(jié)點(diǎn)能量有限并且難以給數(shù)目眾多的節(jié)點(diǎn)更換電池，所以，很多應(yīng)用為了保證網(wǎng)絡(luò)的服務(wù)質(zhì)量要求網(wǎng)絡(luò)覆蓋度k＞1[10]。因此，覆蓋度被認(rèn)為是衡量傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的一個(gè)重要標(biāo)準(zhǔn)。人們對(duì)無線傳感器網(wǎng)絡(luò)的覆蓋問題進(jìn)行了深入研究。Huang等[11]提出了一個(gè)多項(xiàng)式時(shí)間復(fù)雜度的算法來判斷網(wǎng)絡(luò)是否被k度覆蓋。該算法通過判斷網(wǎng)絡(luò)內(nèi)每個(gè)傳感器節(jié)點(diǎn)感應(yīng)圓盤的圓周覆蓋情況進(jìn)而得出整個(gè)網(wǎng)絡(luò)的覆蓋情況，并證明了只要網(wǎng)絡(luò)中節(jié)點(diǎn)感應(yīng)圓盤的圓周被充分覆蓋，整個(gè)網(wǎng)絡(luò)區(qū)域就被充分覆蓋。Wang等[12]提出當(dāng)網(wǎng)絡(luò)內(nèi)任意 2個(gè)節(jié)點(diǎn)感應(yīng)圓盤的交點(diǎn)以及節(jié)點(diǎn)感應(yīng)圓盤與區(qū)域邊界的交點(diǎn)都至少被k度覆蓋時(shí)，網(wǎng)絡(luò)區(qū)域一定被k度覆蓋；CCP協(xié)議可以動(dòng)態(tài)配置網(wǎng)絡(luò)以提供不同的覆蓋度來滿足不同的應(yīng)用需求。該協(xié)議利用節(jié)點(diǎn)的局部位置信息進(jìn)行分布式的節(jié)點(diǎn)職能合格性的判斷，合格節(jié)點(diǎn)處于活躍狀態(tài)，而不合格者將暫時(shí)處于休眠或監(jiān)聽狀態(tài)，從而達(dá)到節(jié)省能量的目的。該研究證明了當(dāng)節(jié)點(diǎn)的通信半徑大于或者等于感應(yīng)半徑的2倍時(shí)，如果網(wǎng)絡(luò)k度覆蓋給定凸區(qū)域，那么在該區(qū)域中網(wǎng)絡(luò)是k度連通的。CCP協(xié)議的時(shí)間復(fù)雜度高于文獻(xiàn)[11]中的方法。Shen等[13]提出了Grid Scan算法，其主要思想是通過將網(wǎng)絡(luò)區(qū)域劃分成許多正方形網(wǎng)格并分別對(duì)每個(gè)網(wǎng)格進(jìn)行覆蓋判斷，最終得出整個(gè)網(wǎng)絡(luò)區(qū)域的覆蓋率。只要網(wǎng)格的中心點(diǎn)被k度覆蓋，就可以認(rèn)為該網(wǎng)格被k度覆蓋。如果覆蓋率達(dá)不到應(yīng)用要求，則通過增加節(jié)點(diǎn)的方法增大網(wǎng)絡(luò)的覆蓋率。本文作者提出一個(gè)基于節(jié)點(diǎn)序列的覆蓋算法。CNS算法通過使用節(jié)點(diǎn)序列不僅可以有效地判斷網(wǎng)絡(luò)區(qū)域的1度覆蓋情況，而且對(duì)目標(biāo)區(qū)域的多度覆蓋情況也能夠進(jìn)行準(zhǔn)確判斷。同時(shí)，還提出了動(dòng)態(tài)增大網(wǎng)絡(luò)1/多度覆蓋率的有效方法。

1 算法描述

1.1 基本假設(shè)和基本概念

基本假設(shè)：

(1) 傳感器節(jié)點(diǎn)比較均勻地布撒在網(wǎng)絡(luò)中并且節(jié)點(diǎn)密度較大。

(2) 傳感器節(jié)點(diǎn)的感應(yīng)模型都是圓盤模型。

(3) 傳感器節(jié)點(diǎn)的感應(yīng)半徑是可以調(diào)節(jié)的，變化范圍為 Rs～Rsmax，初始值為 Rs。

(4) 每個(gè)傳感器節(jié)點(diǎn)都知道自身的地理位置信息(如通過配備GPS或某種定位算法獲得)。

為便于描述，這里對(duì)將要用到的基本概念說明如下。

定義1 如果區(qū)域A中點(diǎn)P至少位于k個(gè)不同的傳感器節(jié)點(diǎn)的感應(yīng)圓盤內(nèi)，那么，就稱點(diǎn) P被 k度覆蓋。

定義2 如果區(qū)域A中點(diǎn)P被節(jié)點(diǎn)數(shù)量小于k的傳感器覆蓋，則稱該點(diǎn)P為k度覆蓋漏洞。

1.2 節(jié)點(diǎn)序列

Zhong等[14]提出了節(jié)點(diǎn)序列的概念。下面對(duì)該概念進(jìn)行簡(jiǎn)要介紹。

定義 3 按照區(qū)域中的點(diǎn)與網(wǎng)絡(luò)中各傳感器節(jié)點(diǎn)之間的距離遞增的順序?qū)W(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)排序，所得的序列稱為傳感器節(jié)點(diǎn)序列，簡(jiǎn)稱為節(jié)點(diǎn)序列。

定義 4 將由具有相同節(jié)點(diǎn)序列的點(diǎn)所組成的區(qū)域定義為“面”(face)，記為 fi(fi表示區(qū)域中第 i個(gè)“面”)。

定義 5 把“面”所對(duì)應(yīng)的節(jié)點(diǎn)序列稱為“面”的標(biāo)志節(jié)點(diǎn)序列，簡(jiǎn)稱標(biāo)志序列。fi的標(biāo)志序列記為Sfi。

定義 6 當(dāng)節(jié)點(diǎn) Sj(Sj表示區(qū)域中第 j個(gè)節(jié)點(diǎn))與“面”fi的重心之間的距離小于節(jié)點(diǎn)的感應(yīng)半徑Rs時(shí)，就稱fi被節(jié)點(diǎn)Sj覆蓋。

步驟1 給定節(jié)點(diǎn)S1和S2，整個(gè)區(qū)域被2個(gè)節(jié)點(diǎn)連線的中垂線Div(S2, S1)劃分為左、右2個(gè)部分，如圖 1(a)所示。從幾何的角度來講，位于右半部分區(qū)域中的點(diǎn)距離S2比S1更近，因此，如果按照節(jié)點(diǎn)距離區(qū)域內(nèi)的點(diǎn)由近至遠(yuǎn)的順序?qū)1和S2進(jìn)行排序，那么，右半部分區(qū)域內(nèi)的點(diǎn)都有著共同的節(jié)點(diǎn)序列：(S2, S1)。圖1(a)中共有2個(gè)“面”，分別記為f1和f2，它們的標(biāo)志序列分別為Sf1=(S1, S2)和Sf2=(S2, S1)。當(dāng)節(jié)點(diǎn)數(shù)目為3時(shí)，網(wǎng)絡(luò)區(qū)域被劃分為6個(gè)“面”，每個(gè)“面”都有著唯一的標(biāo)志序列，如圖1(b)所示。

圖1 網(wǎng)絡(luò)區(qū)域劃分Fig.1 Network division examples

對(duì)文獻(xiàn)[14]中所提出的網(wǎng)絡(luò)區(qū)域劃分方法進(jìn)行改進(jìn)。該方法在對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分的過程中，需要對(duì)網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)的連線做中垂線。對(duì)一個(gè)節(jié)點(diǎn)數(shù)量為n的網(wǎng)絡(luò)區(qū)域進(jìn)行劃分共需要做n(n-1)/2條中垂線。這種全局的區(qū)域劃分方法不僅繁瑣而且計(jì)算過程中節(jié)點(diǎn)能量消耗較大，尤其是對(duì)于節(jié)點(diǎn)數(shù)目較多的大規(guī)模傳感器網(wǎng)絡(luò)。改進(jìn)后的區(qū)域劃分方法具體如下：將網(wǎng)絡(luò)區(qū)域劃分為一定面積的正方形網(wǎng)格(邊長(zhǎng)依區(qū)域面積和網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目而定)，如圖1(b)所示。一個(gè)網(wǎng)格為一個(gè)簇，每個(gè)簇都有1個(gè)簇頭節(jié)點(diǎn)。

步驟 2 依次對(duì)網(wǎng)絡(luò)區(qū)域內(nèi)的網(wǎng)格進(jìn)行區(qū)域劃分，即對(duì)同一網(wǎng)格內(nèi)的任意2個(gè)節(jié)點(diǎn)的連線做中垂線。簇頭節(jié)點(diǎn)負(fù)責(zé)計(jì)算和存儲(chǔ)簇內(nèi)所有“面”的標(biāo)志序列。

為了對(duì)比這 2種區(qū)域劃分算法的性能，在 400 m×400 m的區(qū)域內(nèi)隨機(jī)部署1 000個(gè)初始能量為1 J的傳感器節(jié)點(diǎn)，對(duì)改進(jìn)前、后的算法進(jìn)行能耗和時(shí)間的比較，見表1。

表1 改進(jìn)前、后的區(qū)域劃分方法的性能比較Table 1 Performance comparison between two network division algorithms

由表1可以看出：改進(jìn)后的劃分方法無論是在能耗上還是在運(yùn)行時(shí)間上都比改進(jìn)前降低很多。

圖 2(a)和 2(b)所示分別為按照文獻(xiàn)[14]中的方法和改進(jìn)后的方法對(duì)包含有 20個(gè)傳感器節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域進(jìn)行劃分所得的對(duì)比結(jié)果。

通過比較發(fā)現(xiàn)：按照改進(jìn)后的方法來對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分，不僅使得區(qū)域中“面”的總數(shù)大大減少，而且面積較小的“面”的數(shù)目也較改進(jìn)前減少很多；提高了算法的執(zhí)行效率。

1.3 覆蓋度k=1時(shí)CNS算法的實(shí)現(xiàn)

首先討論如何判斷網(wǎng)絡(luò)區(qū)域是否被1度覆蓋，然后對(duì)其產(chǎn)生的覆蓋漏洞的解決方案進(jìn)行描述。

1.3.1 對(duì)網(wǎng)絡(luò)1度覆蓋情況的判斷

對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分后，網(wǎng)絡(luò)區(qū)域可以看作由一定數(shù)目的“面”組成，如圖2(b)所示。在這些“面”中，有些包含有傳感器節(jié)點(diǎn)，有些是不含有傳感器節(jié)點(diǎn)的。根據(jù)這一特點(diǎn)，在判斷網(wǎng)絡(luò)的1度覆蓋情況時(shí)，本文分以下2種情況分別進(jìn)行討論。

圖2 網(wǎng)絡(luò)區(qū)域劃分對(duì)比(節(jié)點(diǎn)數(shù)目為20)Fig.2 Comparison of network divisions after deployed 20 sensors

(1) 包含傳感器節(jié)點(diǎn)的“面”。由于網(wǎng)絡(luò)中節(jié)點(diǎn)密度較大，區(qū)域劃分所得“面”的面積較小，所以，在大多數(shù)情況下，節(jié)點(diǎn)與“面”的重心間的距離比節(jié)點(diǎn)的感應(yīng)半徑要小得多。因而，對(duì)于網(wǎng)絡(luò)區(qū)域中那些包含有傳感器節(jié)點(diǎn)的“面”來說，可以認(rèn)為它們被其所包含的傳感器節(jié)點(diǎn)大致覆蓋。

(2) 不包含傳感器節(jié)點(diǎn)的“面”。“面”的標(biāo)志序列中各傳感器節(jié)點(diǎn)的順序是按照節(jié)點(diǎn)與“面”內(nèi)各點(diǎn)間的距離由近至遠(yuǎn)的規(guī)律排列的。當(dāng)判斷不包含傳感器節(jié)點(diǎn)的“面”的1度覆蓋情況時(shí)，需要根據(jù)“面”的標(biāo)志序列找出距離它最近的傳感器節(jié)點(diǎn)，進(jìn)而判斷此節(jié)點(diǎn)對(duì)該“面”的覆蓋情況即可。如果該節(jié)點(diǎn)能夠覆蓋該“面”，那么該“面”一定被1度覆蓋；如果該“面”不能被距離它最近的節(jié)點(diǎn)所覆蓋，那么，它也一定不能被網(wǎng)絡(luò)中的其他節(jié)點(diǎn)所覆蓋，則該“面”為覆蓋漏洞。

“面”f1，f3和f4各包含1個(gè)傳感器節(jié)點(diǎn)，根據(jù)上述(1)中的描述可以認(rèn)為它們分別被其所包含的節(jié)點(diǎn)覆蓋，如圖1(b)所示。“面”f6不含有傳感器節(jié)點(diǎn)，需根據(jù)上述(2)中的方法判斷其1度覆蓋情況。f6的標(biāo)志序列(S2, S3, S1)表明在 S1，S2和S3這3個(gè)節(jié)點(diǎn)中，S2距離f6最近。所以，要判斷f6的1度覆蓋情況，只需要判斷距離f6最近的節(jié)點(diǎn)S2是否覆蓋f6即可。根據(jù)定義6，計(jì)算S2與f6的重心間的距離d。若d＜Rs，則認(rèn)為f6被節(jié)點(diǎn)S21度覆蓋；反之，則表明f6沒有被1度覆蓋。判斷網(wǎng)絡(luò)1度覆蓋情況的算法如下所示。

For each grid Gk∈G

{

For each Siin Gk

If (i≠j) Div(Sj, Si);

Get the division of Gk;

Calculate the signature sequence Sfiof each fiin Gk, Sfi=

(Sa, Sb, …, Sx);

}

For each fiin G

{

If (there is Si∈S in fi)fiis 1-covered by Si;

Else{

Calculate the center of gravity point Ciof fi;

d=D(Sa, Ci);

If (d＞Rs) fiis not 1-covered;

Else fiis 1-covered;

}

}

1.3.2 動(dòng)態(tài)提高網(wǎng)絡(luò)的1度覆蓋率

按照1.3.1節(jié)中所述方法對(duì)網(wǎng)絡(luò)區(qū)域中的“面”進(jìn)行1度覆蓋判斷后，可以計(jì)算得到網(wǎng)絡(luò)的1度覆蓋率。如果得到的1度覆蓋率不滿足應(yīng)用需要，那么，可通過如下方法提高網(wǎng)絡(luò)覆蓋率。

步驟1 由簇頭節(jié)點(diǎn)對(duì)其簇內(nèi)沒有被1度覆蓋的“面”進(jìn)行統(tǒng)計(jì)。

步驟 2 簇頭根據(jù)它所存儲(chǔ)的“面”的標(biāo)志序列信息找出距離步驟1中每個(gè)“面”最近的節(jié)點(diǎn)，即出現(xiàn)在標(biāo)志序列第1位的節(jié)點(diǎn)。簇頭對(duì)這些節(jié)點(diǎn)按出現(xiàn)次數(shù)由多至少的順序進(jìn)行排序。

步驟3 根據(jù)步驟2所得節(jié)點(diǎn)次序先后增大相應(yīng)節(jié)點(diǎn)的感應(yīng)至Rsmax，直至網(wǎng)絡(luò)當(dāng)前的1度覆蓋率達(dá)到應(yīng)用要求為止。

假設(shè)有一節(jié)點(diǎn)數(shù)量為5的網(wǎng)絡(luò)，經(jīng)區(qū)域劃分并判斷之后，網(wǎng)絡(luò)中共有6個(gè)“面”沒有被1度覆蓋，它們的標(biāo)志序列分別為(Si, …)，(Sj, …)，(Si, …)，(Sk, …)，(Si, …)和(Sk, …)。統(tǒng)計(jì)各節(jié)點(diǎn)在標(biāo)志序列的第1位所出現(xiàn)的次數(shù)，Si共出現(xiàn)3次，Sk出現(xiàn)2次，Sj出現(xiàn)1次。因此，增大Si，Sk和Sj的感應(yīng)半徑分別能使3個(gè)、2個(gè)和1個(gè)未被覆蓋的面可能被覆蓋，故選擇增大Si的感應(yīng)半徑，以最小的能耗使網(wǎng)絡(luò)覆蓋率得到最大的提高。因此，首先選擇增大 Si的感應(yīng)半徑至Rsmax，若覆蓋率還不能滿足應(yīng)用要求，再增大Sk的感應(yīng)半徑至Rsmax，最后增大Sj的感應(yīng)半徑至Rsmax。

1.4 覆蓋度k＞1時(shí)CNS算法的實(shí)現(xiàn)

1.4.1 對(duì)網(wǎng)絡(luò)多度覆蓋情況的判斷

要判斷網(wǎng)絡(luò)的多度覆蓋情況，需要先對(duì)網(wǎng)絡(luò)中的“面”的覆蓋情況進(jìn)行判斷，然后得出網(wǎng)絡(luò)的覆蓋情況。要判斷一個(gè)“面”是否被k(k＞1)度覆蓋，只需要判斷該“面”是否被其標(biāo)志序列中第k個(gè)節(jié)點(diǎn)覆蓋即可。如果第k個(gè)傳感器節(jié)點(diǎn)覆蓋該“面”，那么標(biāo)志序列中的前k-1個(gè)節(jié)點(diǎn)必定覆蓋該面，則該“面”被k度覆蓋。如圖1(b)所示，由f1的標(biāo)志序列(S2, S1, S3)可知：要判斷f1是否被3度覆蓋，只需要判斷f1是否被其標(biāo)志序列中的第3個(gè)傳感器節(jié)點(diǎn)S3覆蓋即可；當(dāng)S3覆蓋f1時(shí)，f1一定被3度覆蓋；若S3沒有覆蓋f1，則f1一定不滿足3度覆蓋。

判斷網(wǎng)絡(luò)區(qū)域是否被k度覆蓋的具體算法如算法2所示。

1.4.2 動(dòng)態(tài)提高網(wǎng)絡(luò)的多度覆蓋率

為了以最小的代價(jià)使網(wǎng)絡(luò)的 k(k＞1)度覆蓋率得到最大提高，采用以下方案來動(dòng)態(tài)提高網(wǎng)絡(luò)的多度覆蓋率：

步驟1 由簇頭節(jié)點(diǎn)對(duì)簇內(nèi)被k-1度覆蓋的“面”進(jìn)行統(tǒng)計(jì)。

步驟2 簇頭對(duì)出現(xiàn)在步驟1中每個(gè)“面”標(biāo)志序列第k位的節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)并按出現(xiàn)次數(shù)的多少對(duì)它們進(jìn)行排序。

步驟 3 增大出現(xiàn)次數(shù)最多的傳感器節(jié)點(diǎn)的感應(yīng)半徑至Rsmax。

步驟4 計(jì)算網(wǎng)絡(luò)當(dāng)前的k度覆蓋率，若達(dá)到應(yīng)用要求則結(jié)束，否則轉(zhuǎn)步驟1。

對(duì)于區(qū)域中被k-1度覆蓋的“面”，只需要增大其標(biāo)志序列中第k個(gè)傳感器節(jié)點(diǎn)的感應(yīng)半徑便有可能使其達(dá)到k度覆蓋。上述方法是大幅度提高網(wǎng)絡(luò)k度覆蓋率的有效方法。

判斷網(wǎng)絡(luò)多度覆蓋情況的算法如下：

For each grid Gk∈G

{

For each Siin Gk

If (i≠j) Div (Sj, Si);

Get the division of Gk;

Calculate the signature sequence Sfiof each fiin Gk, Sfi=

(Sa, Sb, …, Sk, …, Sx);

}

For each fiin G

{

Calculate the center of gravity point Ciof fi;

d=D (Sk, Ci);

If (d＜Rs) fiis k-covered;

Else fiis not k-covered;

}

1.5 理論分析

定理1 CNS算法的平均時(shí)間復(fù)雜性為O(n2)，其中n為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目。

證明 CNS算法由判斷網(wǎng)絡(luò)1/多度覆蓋情況和動(dòng)態(tài)提高網(wǎng)絡(luò)1/多度覆蓋率2個(gè)算法組成。其中判斷網(wǎng)絡(luò)1/多度覆蓋情況的算法中，對(duì)網(wǎng)絡(luò)區(qū)域進(jìn)行劃分的時(shí)間復(fù)雜性為O(n2)，對(duì)區(qū)域中的“面”進(jìn)行覆蓋判斷的時(shí)間復(fù)雜性為O(n2)；而動(dòng)態(tài)提高網(wǎng)絡(luò)1/多度覆蓋率算法的時(shí)間復(fù)雜性取決于步驟2中對(duì)節(jié)點(diǎn)進(jìn)行排序的時(shí)間復(fù)雜性。最慢的排序算法的時(shí)間復(fù)雜性為O(n2)，最快的排序算法的時(shí)間復(fù)雜性為O(nlogn)。故CNS算法的平均時(shí)間復(fù)雜性為O(n2)。

2 性能評(píng)價(jià)

為了評(píng)估本文提出的CNS算法的性能，將CNS與文獻(xiàn)[13]中Grid Scan算法性能進(jìn)行比較。具體的實(shí)驗(yàn)參數(shù)如表2所示。在實(shí)驗(yàn)中，使用網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)生命期作為評(píng)價(jià)算法性能的指標(biāo)。所有實(shí)驗(yàn)均在Windows XP操作系統(tǒng)下采用Java語言編程，運(yùn)行環(huán)境為Eclipse 3.2。

表2 模擬參數(shù)Table 2 Simulation parameters

為方便計(jì)算網(wǎng)絡(luò)覆蓋率，本文采用的方法是將網(wǎng)絡(luò)區(qū)域劃分為1 m×1 m的小方格。如果方格的中心點(diǎn)被覆蓋，就認(rèn)為整個(gè)方格被覆蓋。因此，k度覆蓋率η可以按如下公式計(jì)算：

其中：|T|為整個(gè)網(wǎng)絡(luò)區(qū)域的方格總數(shù)；|t|表示至少被k個(gè)不同節(jié)點(diǎn)所覆蓋的方格數(shù)目。

2.1 網(wǎng)絡(luò)覆蓋率

網(wǎng)絡(luò)覆蓋率是衡量網(wǎng)絡(luò)服務(wù)質(zhì)量的一個(gè)重要指標(biāo)。本實(shí)驗(yàn)根據(jù)1.3.2節(jié)和1.4.2節(jié)所描述的算法選擇網(wǎng)絡(luò)中的某些傳感器節(jié)點(diǎn)，增大它們的感應(yīng)半徑至Rsmax=15 m，以提高網(wǎng)絡(luò)的覆蓋率，網(wǎng)絡(luò)覆蓋率與Rs=Rsmax的節(jié)點(diǎn)數(shù)的關(guān)系如圖3所示。

圖3中，橫坐標(biāo)表示從網(wǎng)絡(luò)中選擇的需增大感應(yīng)半徑的節(jié)點(diǎn)數(shù)量。從圖3可見：當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的感應(yīng)半徑均等于 Rs=10 m時(shí)，網(wǎng)絡(luò)的 1度覆蓋率為85.02%。依據(jù)1.3.2節(jié)中的算法從網(wǎng)絡(luò)中選取20個(gè)傳感器節(jié)點(diǎn)并增大它們的感應(yīng)半徑至Rsmax，網(wǎng)絡(luò)的1度覆蓋率可增大至94.16%。當(dāng)按照1.4.2節(jié)中的算法從網(wǎng)絡(luò)中選取80個(gè)節(jié)點(diǎn)并增大它們的感應(yīng)半徑至Rsmax時(shí)，網(wǎng)絡(luò)的2度覆蓋率和3度覆蓋率分別提高了22.5%和31.42%。

圖3 網(wǎng)絡(luò)覆蓋率與Rs=Rs max的節(jié)點(diǎn)數(shù)的關(guān)系Fig.3 Relationship between coverage rate and number of sensors whose Rs= Rs max

2.2 網(wǎng)絡(luò)生命期

節(jié)點(diǎn)的能耗是無線傳感器網(wǎng)絡(luò)中的一個(gè)重要問題，它在很大程度上決定了網(wǎng)絡(luò)的生命期，因此，希望所提出的算法具有能量高效的特點(diǎn)。圖4所示為網(wǎng)絡(luò)覆蓋率隨時(shí)間的變化關(guān)系。當(dāng)網(wǎng)絡(luò)的1度覆蓋率小于0.7時(shí)，就認(rèn)為網(wǎng)絡(luò)無法實(shí)現(xiàn)完全覆蓋。從圖4可以看出：與Grid Scan算法相比，CNS算法在保持較高的 1度覆蓋率的前提下使網(wǎng)絡(luò)的生命周期延長(zhǎng)了20 h；雖然在網(wǎng)絡(luò)工作的開始階段中，文獻(xiàn)[15]中的DSLE算法所能實(shí)現(xiàn)的2度覆蓋率比CNS算法所實(shí)現(xiàn)2度覆蓋率略高，但是，在網(wǎng)絡(luò)工作26 h之后，DSLE算法所維持的網(wǎng)絡(luò)2度覆蓋率隨著網(wǎng)絡(luò)生命期的延長(zhǎng)迅速降低，而CNS算法可使網(wǎng)絡(luò)的2度覆蓋率保持在50%以上長(zhǎng)達(dá)52 h。較高的網(wǎng)絡(luò)覆蓋率、較長(zhǎng)的網(wǎng)絡(luò)生命期對(duì)保證傳感器網(wǎng)絡(luò)的服務(wù)質(zhì)量是非常重要的。

圖4 網(wǎng)絡(luò)覆蓋率與時(shí)間的關(guān)系Fig.4 Relationship between k-coverage rate and time

3 結(jié)論

(1) 提出一種基于節(jié)點(diǎn)序列的覆蓋算法；討論如何判斷網(wǎng)絡(luò)的1度覆蓋情況，而且可以調(diào)整傳感器節(jié)點(diǎn)的感應(yīng)半徑以解決覆蓋漏洞的問題。

(2) 對(duì)覆蓋度 k＞1，即網(wǎng)絡(luò)多度覆蓋情況的判斷問題進(jìn)行研究并提出解決k度覆蓋漏洞的方案，從而動(dòng)態(tài)提高網(wǎng)絡(luò)的k度覆蓋率。

[1] Megerian S, Koushanfar F, Potkonjak M, et al. Coverage problems in wireless ad-hoc sensor networks[C]//Proceedings of IEEE International Conference on Computer Communications(INFOCOM). Anchorage: IEEE Press, 2001: 1380-1387.

[2] 文戈, 王國(guó)軍, 過敏意. 無線傳感器網(wǎng)絡(luò)中基于 Voronoi圖的覆蓋和連通綜合配置協(xié)議[J]. 傳感器技術(shù)學(xué)報(bào), 2007, 20(10):2294-2302.WEN Ge, WANG Guo-jun, GUO Min-yi. A Voronoi diagram-based integrated protocol for coverage and connectivity configuration in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2007, 20(10): 2294-2302.

[3] Cardei M, WU J. Energy-efficient coverage problems in wireless ad-hoc sensor networks[J]. Journal of Computer Communications on Sensor Networks, 2006, 29(4): 413-420.

[4] He X, Yin K, Gui X. The area coverage algorithm to maintain connectivity for WSN[C]//Proceedings of IEEE International Conference on Computer and Information Technology. Atlanta:IEEE Computer Society Press, 2009: 81-86.

[5] Liu D. On connected area coverage sets in wireless sensor networks[C]//Proceedings of International Conference on Mobile Technology, Applications, and Systems. Singapore: ACM Press,2007: 226-229.

[6] Xing X, Wang G, Wu J, et al. Square region-based coverage and connectivity probability model in wireless sensor networks[C]//Proceedings of International Conference on Collaborative Computing: Networking, Applications and Worksharing(CollaborateCom). Washington DC: IEEE Press, 2009: 1-8.

[7] Cardei M, Du D. Improving wireless sensor network lifetime through power aware organization[J]. Wireless Networks, 2005,11(3): 330-340.

[8] Zorbas D, Glynos D, Kotzanikolaou P, et al. Solving coverage problems in wireless sensor networks using cover sets[J]. Ad Hoc Networks, 2010, 8(4): 400-415.

[9] Chen A, Lai T H, Xuan D. Measuring and guaranteeing quality of barrier-coverage in wireless sensor networks[C]//Proceedings of International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc). Hong Kong: ACM Press, 2008:421-430.

[10] Hefeeda M, Bagheri M. Randomized k-coverage algorithms for dense sensor networks[C]//Proceedings of IEEE International Conference on Computer Communications (INFOCOM),Anchorage: IEEE Press, 2007: 2376-2380.

[11] Huang C, Tseng Y. The coverage problem in a wireless sensor network[C]//Proceedings of International Conference on Wireless Sensor Networks and Applications. New York: ACM Press, 2003: 519-528.

[12] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration in wireless sensor networks[C]//Proceedings of International Conference on Embedded Networked Sensor Systems. Los Angeles: ACM Press, 2003:28-39.

[13] Shen X, Chen J, Sun Y. Grid scan: A simple and effective approach for coverage issue in wireless sensor networks[C]//Proceedings of IEEE International Conference on Communications (ICC). Istanbul: IEEE Press, 2006: 3480-3484.

[14] Zhong Z, Zhu T, Wang D, et al. Tracking with unreliable node sequences[C]//Proceedings of IEEE International Conference on Computer Communications (INFOCOM). Rio de Janeiro: IEEE Press, 2009: 1215-1223.

[15] Li J, Kao H. Distributed k-coverage self-location estimation scheme based on Voronoi diagram[J]. IET Communications,2010, 4(2): 167-177.