[發明專利]無線傳感器網絡覆蓋空洞面積的計算方法在審

申請號：	201410375384.5	申請日：	2014-07-31
公開（公告）號：	CN104135732A	公開（公告）日：	2014-11-05
發明（設計）人：	洪浩瀚;宋佳;陳彬;劉揚;劉宏日;王佰玲	申請（專利權）人：	哈爾濱工業大學(威海)
主分類號：	H04W16/18	分類號：	H04W16/18
代理公司：	北京科億知識產權代理事務所(普通合伙) 11350	代理人：	湯東鳳
地址：	264209***	國省代碼：	山東;37
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	無線傳感器網絡覆蓋空洞面積計算方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及無線傳感器領域，特別是涉及一種無線傳感器網絡覆蓋空洞面積的計算方法。

背景技術

在一個無線傳感器網絡中(WSN)，傳感器節點被隨機的分布在一個區域中，以用來感應、處理、并將數據傳輸到遠程通信基站。為了保證一個區域的通信暢通，通常需要將足夠的傳感器節點部署到這個區域中，這樣也會造成一定的冗余。然而由于單個傳感器節點的處理能力、內存空間、電池容量、通信范圍和通信帶寬都非常有限，傳感器網絡的監測就顯得尤為重要。

隨著無線傳感器網絡的不斷運行，總會有一個個傳感器節點失效(通常是由于電量損耗、環境變化等)，于是就會出現傳感器網絡覆蓋空洞(coverage?hole)的出現，這時就需要使用一定的算法來檢測出覆蓋空洞的有關信息，以設法彌補來維持無線傳感器網絡的持續運行。

檢測覆蓋空洞的算法通常可以分為三類：計算幾何法、統計方法和拓撲方法。計算幾何法利用傳感器節點的坐標和幾何工具來檢測覆蓋空洞，這種方法要求必須知道覆蓋區域的幾何信息以及每一個節點的坐標；統計方法假設大量節點被均勻一致地分布在區域中，缺點是這種基于概率的方法需要傳感器網絡節點密集且一致的分布。

發明內容

本發明的目的是提供一種能夠檢測出覆蓋空洞的邊界和網絡的外邊界以便于更高效地部署修補節點以用最少的代價維護網絡的最高效運行的無線傳感器網絡覆蓋空洞面積的計算方法。

為解決上述技術問題，作為本發明的一個方面，提供了一種無線傳感器網絡覆蓋空洞面積的計算方法，包括：步驟1，計算出由鄰接節點構成的無向圖；步驟2，計算出各鄰接節點之間的交點；步驟3，根據交點找出空洞的邊界節點并構造出空洞的邊界圖；步驟4，廣度遍歷邊界圖，從中找出所有的最小多邊形以形成字典D；步驟5，遍歷字典D，判斷網絡中的節點是否被其中的一個最小多邊形包圍，如果是，則將該最小多邊形從字典D中刪除；步驟6，計算字典D內的每個最小多邊形的面積，如果結果為負則表示沒有空洞；否則表示有空洞。

進一步地，步驟1包括：遍歷所有隨機生成的節點，若兩個節點的距離小于2倍的通信半徑，則為鄰居節點；收集所有節點的鄰居節點的信息，并標記出來從而形成無向圖。

進一步地，步驟3包括：遍歷交點，找出對應的鄰居節點集；如果一鄰居節點到交點的距離小于通信半徑，則表示此交點被覆蓋，不是邊界交點；如果所有鄰居節點都沒覆蓋此交點，則此交點為邊界交點。

進一步地，步驟4包括：對邊界圖進行廣度優先遍歷，從而得到邊界圖中所有的最小多變形；對每個最小多變形的節點坐標進行排序，并進行哈希處理，存入字典D中，以保證字典D中沒有重復的最小多邊形。

進一步地，步驟6包括：計算每一個最小多邊形的面積，并減去覆蓋圓弧和邊界三角形的面積；如果結果為負，則舍棄；若結果為正，則保存；最后，將結果相加，即得整個網絡中的覆蓋空洞的面積和。

本發明便于排查冗余節點，在檢測覆蓋空洞邊界節點時能夠判斷一個節點是否是冗余的，即除掉此節點后傳感器網絡是否還能夠保持覆蓋面積不變；能夠檢測出覆蓋空洞的邊界和網絡的外邊界，這樣便于更高效地部署修補節點以用最少的代價維護網絡的最高效運行；能夠測量出無線傳感器中覆蓋空洞的面積來評估網絡的質量和使用價值。

附圖說明

圖1示意性示出了隨機生成的無線傳感器網絡；

圖2示意性示出了對應于圖1的鄰居節點連通無向圖；

圖3示意性示出了生成的邊界交點信息；

圖4示意性示出了生成的邊界節點連通無向圖。

具體實施方式

以下對本發明的實施例進行詳細說明，但是本發明可以由權利要求限定和覆蓋的多種不同方式實施。