無線傳感器網(wǎng)絡(luò)覆蓋算法研究

李小龍　段　雪　徐增敏

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

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

中圖法分類：TP393

文獻標識碼：A

0引言

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

1覆蓋算法的分類

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

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

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

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

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

2典型的覆蓋算法分析

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

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

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

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

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

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

3總結(jié)

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