無線傳感器網絡覆蓋算法研究

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

關鍵詞：無線傳感器網絡 覆蓋

中圖法分類：TP393

文獻標識碼：A

0 引言

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

1 覆蓋算法的分類

1.1確保完全覆蓋的覆蓋算法和不能確保完全覆蓋的覆蓋算法。假設部署在目標區域的傳感節點組成的傳感器網絡能夠完全覆蓋目標區域。根據執行了算法之后處于活動狀態的節點能否完全覆蓋目標區域，把節點調度覆蓋算法分為：確保完全覆蓋的覆蓋算法和不能確保完全覆蓋的覆蓋算法。前者適用于災難救助、軍事監測等對安全程度要求較高的應用領域，后者適用于環境感知、森林火災監測等對安全程度要求較低的應用領域。前者又可分為1－覆蓋和K－覆蓋(K≥2)，屬于K－覆蓋的覆蓋算法確保所有的監測目標或監測點同時都被K個不同的傳感器節點所覆蓋。

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

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

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

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

2 典型的覆蓋算法分析

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

優點：①不依賴于節點的位置信息；②關閉冗余節點之后，不降低原有的覆蓋率。

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

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

優點：①不依賴于節點的位置信息；②適用于不規則感知模型：③確保了在任意時刻網絡的連通性；(4)算法在節點的生命周期內僅執行了一次，節約了能量。

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

3 總結

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