李小龍　段　雪　徐增敏

摘要：立足于無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題，分類總結(jié)近年來(lái)提出的覆蓋算法，詳細(xì)討論了一些典型的無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)覆蓋

中圖法分類：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

0引言

節(jié)點(diǎn)調(diào)度和密度控制是節(jié)約網(wǎng)絡(luò)能量、延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的一種有效辦法。本文立足于無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題，分類總結(jié)了近年來(lái)提出的覆蓋算法，并詳細(xì)討論了一些典型的無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法。

1覆蓋算法的分類

1.1確保完全覆蓋的覆蓋算法和不能確保完全覆蓋的覆蓋算法。假設(shè)部署在目標(biāo)區(qū)域的傳感節(jié)點(diǎn)組成的傳感器網(wǎng)絡(luò)能夠完全覆蓋目標(biāo)區(qū)域。根據(jù)執(zhí)行了算法之后處于活動(dòng)狀態(tài)的節(jié)點(diǎn)能否完全覆蓋目標(biāo)區(qū)域，把節(jié)點(diǎn)調(diào)度覆蓋算法分為：確保完全覆蓋的覆蓋算法和不能確保完全覆蓋的覆蓋算法。前者適用于災(zāi)難救助、軍事監(jiān)測(cè)等對(duì)安全程度要求較高的應(yīng)用領(lǐng)域，后者適用于環(huán)境感知、森林火災(zāi)監(jiān)測(cè)等對(duì)安全程度要求較低的應(yīng)用領(lǐng)域。前者又可分為1－覆蓋和K－覆蓋(K≥2)，屬于K－覆蓋的覆蓋算法確保所有的監(jiān)測(cè)目標(biāo)或監(jiān)測(cè)點(diǎn)同時(shí)都被K個(gè)不同的傳感器節(jié)點(diǎn)所覆蓋。

1.2集中式的覆蓋算法和分布式的覆蓋算法。根據(jù)算法實(shí)施策略來(lái)分，把覆蓋算法分為：集中式的覆蓋算法和分布式的覆蓋算法。前者需要將整個(gè)網(wǎng)絡(luò)的全局信息發(fā)送給一個(gè)處理節(jié)點(diǎn)，由處理節(jié)點(diǎn)單獨(dú)執(zhí)行完算法之后，將控制信息發(fā)送給網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)，因此僅適用于小型的傳感器網(wǎng)絡(luò)，不具備良好的擴(kuò)展性。而后者通過(guò)利用局部信息，由鄰近區(qū)域內(nèi)節(jié)點(diǎn)之間的協(xié)作共同完成，可適用于大型的傳感器網(wǎng)絡(luò)。

1.3確保網(wǎng)絡(luò)連通性的覆蓋算法和不考慮網(wǎng)絡(luò)連通性的覆蓋算法。根據(jù)網(wǎng)絡(luò)連通性來(lái)分，把覆蓋算法分為：確保網(wǎng)絡(luò)連通性的覆蓋算法和不考慮網(wǎng)絡(luò)連通性的覆蓋算。文獻(xiàn)已經(jīng)證明，如果網(wǎng)絡(luò)中的所有節(jié)點(diǎn)同構(gòu)，且節(jié)點(diǎn)的感知模型為圓形區(qū)域感知模型，當(dāng)通信半徑大于或者等于2倍的傳感半徑時(shí)，完全覆蓋目標(biāo)區(qū)域的節(jié)點(diǎn)集構(gòu)成的傳感器網(wǎng)絡(luò)一定是連通網(wǎng)絡(luò)。然而，當(dāng)通信半徑小于2倍的傳感半徑時(shí)，不能保證網(wǎng)絡(luò)的連通性。在不考慮通信半徑與傳感半徑之間的關(guān)系時(shí)，確保網(wǎng)絡(luò)連通性的覆蓋算法能夠保證在任意時(shí)刻，處于活動(dòng)狀態(tài)下的節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)是連通網(wǎng)絡(luò)，因此收集到的傳感數(shù)據(jù)能夠發(fā)送到匯聚節(jié)點(diǎn)。

1.4依賴于節(jié)點(diǎn)位置信息的覆蓋算法和不依賴于節(jié)點(diǎn)位置信息的覆蓋算法。根據(jù)是否利用位置信息，把覆蓋算法分為：依賴于節(jié)點(diǎn)位置信息的節(jié)點(diǎn)調(diào)度覆蓋算法和不依賴于節(jié)點(diǎn)位置信息的覆蓋算法。現(xiàn)有的定位技術(shù)由于硬件成本、能耗以及誤差范圍的限制，難以保證每個(gè)節(jié)點(diǎn)獲得自身精確的物理位置，因此，倚賴于節(jié)點(diǎn)位置信息的覆蓋算法可能會(huì)因?yàn)楣?jié)點(diǎn)不能獲取到準(zhǔn)確的位置信息，導(dǎo)致難以達(dá)到預(yù)定的覆蓋效果。

1.5基于輪次的覆蓋算法和基于分組的覆蓋算法。根據(jù)算法在網(wǎng)絡(luò)生存時(shí)間內(nèi)的執(zhí)行次數(shù)來(lái)分，把覆蓋算法分為：基于輪次的覆蓋算法和基于分組的覆蓋算法?；谳喆蔚母采w算法要求傳感器節(jié)點(diǎn)在每一輪的開(kāi)始執(zhí)行一次算法，按照某種競(jìng)爭(zhēng)機(jī)制從所有節(jié)點(diǎn)中選擇若干個(gè)節(jié)點(diǎn)作為活動(dòng)節(jié)點(diǎn)，這種算法在傳感器網(wǎng)絡(luò)的生存時(shí)間內(nèi)執(zhí)行了多次。而基于分組的覆蓋算法在傳感器節(jié)點(diǎn)部署后僅執(zhí)行一次，通過(guò)分組將所有傳感器節(jié)點(diǎn)劃分到若干個(gè)組內(nèi)，在算法完成之后，依次調(diào)度每一組的傳感器節(jié)點(diǎn)作為活動(dòng)節(jié)點(diǎn)。

2典型的覆蓋算法分析

2.1位置無(wú)關(guān)的覆蓋算法算法屬于不依賴于節(jié)點(diǎn)位置信息的分布式覆蓋算法。該算法僅適用于圓形區(qū)域感知模型，且節(jié)點(diǎn)的傳感半徑與通信半徑相等的情況。各個(gè)節(jié)點(diǎn)根據(jù)如下信息判斷自身的傳感任務(wù)是否可由鄰居節(jié)點(diǎn)完成：1－Hop內(nèi)的鄰居節(jié)點(diǎn)，以及這些鄰居節(jié)點(diǎn)的1－Hop鄰居節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)判斷自身為冗佘節(jié)點(diǎn)，就可以關(guān)閉自身節(jié)點(diǎn)的傳感單元進(jìn)入休眠狀態(tài)。

優(yōu)點(diǎn)：①不依賴于節(jié)點(diǎn)的位置信息；②關(guān)閉冗余節(jié)點(diǎn)之后，不降低原有的覆蓋率。

缺點(diǎn)：①只適用于圓形區(qū)域感知模型，不適用于不規(guī)則的節(jié)點(diǎn)感知模型：②只適用于節(jié)點(diǎn)的傳感半徑與通信半徑相等的情況；③絕大部分的冗余節(jié)點(diǎn)都不能滿足上述判斷條件，因此不能進(jìn)入休眠狀態(tài)；④沒(méi)有考慮網(wǎng)絡(luò)的連通性。

2.2連通的隨機(jī)調(diào)度覆蓋算法算法屬于一種不依賴于節(jié)點(diǎn)位置信息的基于分組的分布式覆蓋算法。算法分4步完成。第1步，將所有的傳感器節(jié)點(diǎn)分為K組，每個(gè)傳感器節(jié)點(diǎn)隨機(jī)取1到K中的某個(gè)值i，并將自身分配到第i組。第2步，每個(gè)節(jié)點(diǎn)獲取到匯聚節(jié)點(diǎn)的最小跳數(shù)。匯聚節(jié)點(diǎn)首先向鄰居節(jié)點(diǎn)廣播包含了到匯聚節(jié)點(diǎn)最小跳數(shù)的消息，最小跳數(shù)的初始值為0。所有節(jié)點(diǎn)將記錄到匯聚節(jié)點(diǎn)的最小跳數(shù)，同時(shí)忽略具有較大跳數(shù)的消息。然后將跳數(shù)值加1，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。通過(guò)這種方法，傳感器網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠記錄下到匯聚節(jié)點(diǎn)的最小跳數(shù)。第3步，各個(gè)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播消息，其中包括自身的ID，到匯聚節(jié)點(diǎn)的最小跳數(shù)以及組號(hào)等信息。第四步，通過(guò)分配一些必要節(jié)點(diǎn)到某些組內(nèi)，使每個(gè)節(jié)點(diǎn)能夠在所屬的分組內(nèi)建立一條到匯聚節(jié)點(diǎn)的最短路徑來(lái)構(gòu)造連通網(wǎng)絡(luò)。分組i內(nèi)的各個(gè)節(jié)點(diǎn)(不妨假設(shè)為A，它的最小跳數(shù)為n)首先判斷在自身鄰近區(qū)域內(nèi)的下游節(jié)點(diǎn)(下游節(jié)點(diǎn)是最小跳數(shù)為n-1的節(jié)點(diǎn))是否有節(jié)點(diǎn)屬于分組i，如果沒(méi)有，則節(jié)點(diǎn)A從這些節(jié)點(diǎn)中任選一個(gè)，并將它同時(shí)劃分到分組i，以確保節(jié)點(diǎn)A從第n跳到第n-1跳是連通的，依此類推，從而建立一條A到匯聚節(jié)點(diǎn)的最短路徑。在執(zhí)行完第4步之后，顯然分組i構(gòu)成的子網(wǎng)絡(luò)是連通的。在算法完成之后，依次調(diào)度每一組的傳感器節(jié)點(diǎn)作為活動(dòng)節(jié)點(diǎn)。

優(yōu)點(diǎn)：①不依賴于節(jié)點(diǎn)的位置信息；②適用于不規(guī)則感知模型：③確保了在任意時(shí)刻網(wǎng)絡(luò)的連通性；(4)算法在節(jié)點(diǎn)的生命周期內(nèi)僅執(zhí)行了一次，節(jié)約了能量。

缺點(diǎn)：①各個(gè)分組內(nèi)的節(jié)點(diǎn)分布不均勻，覆蓋效果較差；②維持分組連通時(shí)額外加入到分組內(nèi)的節(jié)點(diǎn)較多。

3總結(jié)

本文立足于無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋問(wèn)題，分類總結(jié)了近年來(lái)提出的覆蓋算法，并詳細(xì)討論了一些典型的無(wú)線傳感器網(wǎng)絡(luò)覆蓋算法。