[發(fā)明專利]一種傳感器網(wǎng)絡(luò)骨架提取方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200910060883.4
• 申請(qǐng)日: 2009-02-27
• 公開（公告）號(hào): CN101505487A
• 公開（公告）日: 2009-08-12
• 發(fā)明（設(shè)計(jì)）人: 劉文予;蔣洪波;劉文平;白翔;田臣
• 申請(qǐng)（專利權(quán)）人: 華中科技大學(xué)
• 主分類號(hào): H04W16/24
• 分類號(hào): H04W16/24;H04W40/00;H04W84/18
• 代理公司: 華中科技大學(xué)專利中心
• 代理人: 曹葆青

技術(shù)領(lǐng)域

本發(fā)明涉及無線傳感器網(wǎng)絡(luò)技術(shù)領(lǐng)域，特別是涉及基于連接信息的網(wǎng)絡(luò)骨架提取方法。

背景技術(shù)

許多傳感器網(wǎng)絡(luò)裝置與傳感器節(jié)點(diǎn)所處的集合環(huán)境緊密相關(guān)，關(guān)于傳感器網(wǎng)絡(luò)拓?fù)涞墓羌艹槿〈蟠蟮靥岣吡藗鞲衅骶W(wǎng)絡(luò)中諸如定位、路由選擇等服務(wù)的性能。在計(jì)算機(jī)視覺研究領(lǐng)域中，關(guān)于拓?fù)涑槿〉难芯恐饕性谶B續(xù)空間上，不能直接應(yīng)用到離散的傳感器網(wǎng)絡(luò)上。在現(xiàn)有關(guān)于拓?fù)浒l(fā)現(xiàn)的文獻(xiàn)中，主要集中于邊界識(shí)別技術(shù)，以及在此基礎(chǔ)上找出骨架線。其中具有代表性的是JehoshuaBruck等提出的MAP算法，具體做法是：先識(shí)別出傳感器網(wǎng)絡(luò)的邊界，再利用最大內(nèi)切圓方法，去判定一個(gè)節(jié)點(diǎn)是否為中軸節(jié)點(diǎn)。若某節(jié)點(diǎn)的最大內(nèi)切圓與邊界有兩個(gè)交點(diǎn)，則該節(jié)點(diǎn)即被當(dāng)作中軸節(jié)點(diǎn)。由于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)是離散分布，這種方法往往會(huì)容易受到邊界擾動(dòng)的影響，得到不真實(shí)的中軸節(jié)點(diǎn)，以致中軸線不能很好的代表傳感器網(wǎng)絡(luò)的真實(shí)拓?fù)浣Y(jié)構(gòu)。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有方法的不足，本發(fā)明提出了一種網(wǎng)絡(luò)骨架提取方法，該方法不會(huì)受到邊界擾動(dòng)影響，能得到更加近似的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

一種傳感器網(wǎng)絡(luò)骨架提取方法，包括以下步驟：

1)根據(jù)節(jié)點(diǎn)曲率與預(yù)定曲率閾值的比較結(jié)果確定網(wǎng)絡(luò)邊界上的節(jié)點(diǎn)哪些為角點(diǎn)，相鄰兩個(gè)角點(diǎn)之間的邊界節(jié)點(diǎn)組成邊界分支{C_n，n＝1，…，P}，P為角點(diǎn)數(shù)；

2)搜索到最近兩個(gè)邊界分支C_i，C_j的距離之差的絕對(duì)值小于等于預(yù)定修正量σ_p的節(jié)點(diǎn)，稱其為骨架節(jié)點(diǎn)，邊界分支C_i，C_j對(duì)應(yīng)的骨架節(jié)點(diǎn)形成連通分量，C_i，C_j∈{C_n，n＝1，…，P}；

3)在每一連通分量中，搜索具有最長(zhǎng)連通路徑的兩個(gè)骨架節(jié)點(diǎn)，這兩個(gè)骨架節(jié)點(diǎn)以及它們之間最長(zhǎng)連通路徑上的所有節(jié)點(diǎn)構(gòu)成骨架弦；

4)相鄰的骨架弦端點(diǎn)節(jié)點(diǎn)通過廣播方式相連，再將各角點(diǎn)與其最近的骨架弦端點(diǎn)節(jié)點(diǎn)相連，生成粗糙骨架；

5)采用信息廣播方式找到并刪除粗糙骨架上沒有子節(jié)點(diǎn)且不是角點(diǎn)的骨架節(jié)點(diǎn)，得到最終網(wǎng)絡(luò)骨架。

作為本發(fā)明的改進(jìn)，若連通分量中存在聚合節(jié)點(diǎn)，則該連通分量的骨架弦的一個(gè)端點(diǎn)必為聚合節(jié)點(diǎn)，所述聚合節(jié)點(diǎn)指到三個(gè)或三個(gè)以上最近的邊界分支中，到其中任意兩個(gè)邊界分支的距離之差的絕對(duì)值均小于等于修正量σ_p的骨架節(jié)點(diǎn)。

所述修正量σ_p取值范圍為0＜σ_p＜d(C_i，C_j)，d(C_i，C_j)表示邊界分支C_i與C_j間的節(jié)點(diǎn)距離最大值。

本發(fā)明的技術(shù)效果體現(xiàn)在：

本發(fā)明從任意一個(gè)角點(diǎn)開始，沿著粗糙的骨架廣播，剔除沒有子節(jié)點(diǎn)且非角點(diǎn)的節(jié)點(diǎn)，形成優(yōu)化骨架，其優(yōu)點(diǎn)在于不會(huì)形成類似環(huán)狀之類的情況。同時(shí)，集中式的全局算法并不適合傳感器網(wǎng)絡(luò)這樣的分布式網(wǎng)絡(luò)，應(yīng)該設(shè)計(jì)一個(gè)全局算法的分布式近似方法，在基本保留全局算法的優(yōu)越性的同時(shí)獲得分布式的特性。由于CASE算法為分布式而非集中式算法，它是全局算法的分布式實(shí)現(xiàn)，因此該算法適合應(yīng)用于具有分布式特點(diǎn)的傳感器網(wǎng)絡(luò)；該算法無論是時(shí)間復(fù)雜度還是空間復(fù)雜度，均與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)成線性關(guān)系，因此，提取骨架需要的數(shù)據(jù)包和網(wǎng)絡(luò)延遲不會(huì)因?yàn)閭鞲衅骶W(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)增加而影響性能，因而具有良好的可擴(kuò)展性；同時(shí)，該算法利用不同邊界分支來確定骨架節(jié)點(diǎn)，與傳統(tǒng)的算法相比，不會(huì)受到邊界擾動(dòng)影響，因而能得到更加近似的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而更好的重構(gòu)網(wǎng)絡(luò)。

附圖說明

圖1是本發(fā)明方法流程示意圖；

圖2是本發(fā)明識(shí)別骨架節(jié)點(diǎn)步驟的流程示意圖；

圖3是本發(fā)明的傳感器網(wǎng)絡(luò)模型示例圖；

圖4是本發(fā)明邊界劃分示例示意圖；

圖5是本發(fā)明傳感器網(wǎng)絡(luò)的骨架節(jié)點(diǎn)和聚合點(diǎn)示意圖；

圖6是本發(fā)明傳感器網(wǎng)絡(luò)的骨架弦示意圖；

圖7是本發(fā)明傳感器網(wǎng)絡(luò)的粗糙骨架示意圖；

圖8是本發(fā)明取δ_p＝0.50的傳感器網(wǎng)絡(luò)骨架示意圖；

圖9是本發(fā)明取δ_p＝0.75的傳感器網(wǎng)絡(luò)骨架示例圖；

圖10是本發(fā)明取δ_p＝0.86的傳感器網(wǎng)絡(luò)骨架示例圖。

具體實(shí)施方式

為了更加清楚的表明本發(fā)明，下面結(jié)合附圖及具體實(shí)例詳細(xì)說明。