[發明專利]一種三維傳感器網絡面骨架提取方法

在審

• 申請號: 201510791389.0
• 申請日: 2015-11-17
• 公開（公告）號: CN105282759A
• 公開（公告）日: 2016-01-27
• 發明（設計）人: 劉文平;蔣洪波;陶前功;王玉寶;邢婧;耿智林;王磊;朱冬輝
• 申請（專利權）人: 劉文平
• 主分類號: H04W16/24
• 分類號: H04W16/24;H04W40/00;H04W24/00;H04W84/18
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 曹葆青

技術領域

本發明屬于無線傳感器網絡技術領域，更具體地，涉及一種三維傳感器網絡面骨架提取方法。

背景技術

面骨架是三維傳感器網絡的重要架構，可以充分反映其幾何拓撲特征；已有研究表明，利用傳感器網絡的幾何拓撲特征，有助于設計高性能的網絡協議。在計算機視覺研究領域中，關于三維物體面骨架的研究層出不窮，但大多集中于連續域上，且采用集中式算法來進行，因而不能直接應用到具有資源約束特征的離散傳感器網絡中。現有關于傳感器網絡骨架提取的文獻，主要集中于二維傳感器網絡，而XiaSu等提出的面骨架提取方法則是三維傳感器網絡中的唯一研究成果。其具體做法是：首先建立一個單位四面體元(UnitTetrahedronCell,UTC)網絡結構，然后以遞歸方式從內外邊界同時“剝開”UTC網絡結構的每一層，直到沒有任何層可以剝開為止，即得到網絡面骨架。但這種基于形態細化、本質上與Blum提出的燒草模型相類似的方法，對所使用的距離度量標準十分敏感而通常無法準確定位面骨架點。此外，它非常容易受邊界噪聲影響，進而產生繃帶骨架，必須采用事后優化處理過程。更為重要的是，該方法依賴于建立的UTC網絡結構，而建立UTC結構通常需要網絡密度較大，在網絡較為稀疏、存在小尺寸空洞且僅有節點間連接信息(而非節點坐標信息)可供使用時，要得到準確的UTC結果十分困難。最后，由于UTC結構需要事先構建，該方法不能應用于動態網絡中。當網絡拓撲因節點失效或新節點加入而發生改變時，重新構建UTC會帶來巨大的通信開銷。

發明內容

針對現有方法的不足，本發明提出了一種三維傳感器網絡面骨架提取方法，該方法不會受到邊界擾動、網絡密度稀疏和距離舍入誤差等因素的影響，能得到更加真實的網絡拓撲結構。

一種三維傳感器網絡面骨架提取方法，包括以下步驟：

(1)每個內部節點計算其特征點，如果某個內部節點距離最近邊界點的跳數為k，則把距離該內部節點k+1跳的邊界點也看作為特征點；稱其為擴展特征點；

(2)采用限制性廣播方式，把節點的特征點形成多個特征連通分量，并在邊界上進行逐跳擴張來計算特征連通分量之間的測地距離；

(3)將測地距離小于ε的特征連通分量合并成大的ε連通分量。如果ε連通分量個數大于等于2，則相應內部節點為面骨架點；否則，它就不是面骨架點；

作為本發明的創新，首次提出了利用測地ε等價關系來提取穩健的面骨架。如果兩個節點(或聯通分離)a,b間的測地距離小于給定正實數ε，則稱它們是測地ε等價的。這種基于測地ε等價關系的骨架節點識別方法，對于邊界噪聲、節點失效和網絡低密度等因素具有魯棒性，而且它是連續域中面骨架定義在離散傳感器網絡中的推廣。

(4)構造出面骨架點的極大獨立集，使得其中任意兩面骨架點間的跳數距離大于1且小于等于3；這樣得到的極大獨立集中，面骨架點分布相對均勻，能更好反映網絡幾何拓撲特征。

(5)利用極大獨立集中的面骨架節點，得到Voronoi圖，其中每個Voronoi元有且僅有一個面骨架點。基于該Voronoi圖，利用已有方法得到其對偶圖Delaunay三角化，從而得到三維傳感器網絡面骨架。

本發明的技術效果體現在：

本發明通過引入參數ε來得到ε連通分量，并基于ε連通分量識別出面骨架點，它是基于連續域中定義識別出的面骨架子集，其優點在于這種識別方法可以避免舍入誤差、邊界噪聲和網絡低密度等因素造成的不良影響，更加適應于離散的三維傳感器網絡。同時，傳統的集中式面骨架提取算法并不適合傳感器網絡這樣的分布式網絡，而且傳感器節點具有能量和計算能力等的有限性特點，應該設計一個分布式近似方法，在基本保留集中式算法優越性的同時維持分布式特性。由于本發明為分布式算法，適合應用在具有分布式特點的三維傳感器網絡中；該算法的時間、空間復雜度都與網絡規模成線性關系，具有良好的可擴展性，能應用于大規模三維傳感器網絡中；與以往算法相比，它不依賴于任何特殊結構，且對邊界噪聲、網絡稀疏和網絡稀疏等因素的控制更加靈活，能夠提取出更穩健的網絡面骨架。

附圖說明

圖1是本發明方法流程示意圖；

圖2是本發明的三維傳感器網絡模型示例圖；

圖3是本發明的三維傳感器網絡面骨架節點的特征連通分量示意圖；

圖4是本發明的三維傳感器網絡非面骨架節點的特征連通分量示意圖；

圖5是本發明三維傳感器網絡中識別的面骨架節點示意圖；

圖6是本發明三維傳感器網絡中極大獨立面骨架點集示意圖；

圖7是本發明的三維傳感器網絡面骨架示意圖。