[發(fā)明專利]一種混合傳感網(wǎng)中基于最少空洞數(shù)柵欄的柵欄修補方法

有效

• 申請?zhí)枺?/td>: 201410283011.5
• 申請日: 2014-06-23
• 公開（公告）號: CN105228160B
• 公開（公告）日: 2018-10-30
• 發(fā)明（設(shè)計）人: 王朝煒;謝歡;林侃成;彭宏玉;康琳;張英海
• 申請（專利權(quán)）人: 北京郵電大學(xué)
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W84/18
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 李迪

1.一種混合傳感網(wǎng)中基于最少空洞數(shù)柵欄的柵欄修補方法，其特征在于，該方法包括在混合傳感網(wǎng)中查找最少空洞數(shù)柵欄：

在監(jiān)測區(qū)域中引入兩個代表區(qū)域邊界的虛擬節(jié)點φ₀和φ₁，假設(shè)φ₀表示監(jiān)測區(qū)域最左側(cè)，即x＝0，φ₁表示監(jiān)測區(qū)域的最右側(cè)，即x＝LL為監(jiān)測區(qū)域的寬度；構(gòu)造一個有向圖G(V，E)，在有向圖G中，V包括了所有的傳感器節(jié)點；每兩個節(jié)點間連線e_ij都有一個權(quán)重ω(e_ij)，該權(quán)重值表示節(jié)點v_i和節(jié)點v_j之間空洞個數(shù)，邊集E的具體構(gòu)造方式如下：

對于所有傳感器節(jié)點，不包括表示邊界的兩個虛擬節(jié)點，權(quán)值ω(e_ij)可表示如下：

其中，dist(v_i,v_j)表示節(jié)點v_i與v_j的距離，R_s為節(jié)點的感知區(qū)域半徑，有其中，x_i為第i個移動節(jié)點，x_j為第j個移動節(jié)點，當(dāng)ω(e)＝0時，即這兩節(jié)點間沒有覆蓋空洞；

將兩個虛擬節(jié)點φ₀和φ₁加入到前面的二分圖G(V,E)中，構(gòu)造一個新的二分圖，其中V'＝V∪φ₀∪φ₁；對于v_i∈V,1≤i≤N，有

對于虛擬節(jié)點權(quán)重ω(e_ij)可表示如下：

根據(jù)以上公式確定任意兩節(jié)點間存在的空洞數(shù)，即完成了二分圖G'(V',E')的初始化過程；由于任意兩節(jié)點連線上的權(quán)值表示的是兩節(jié)點間的空洞數(shù)，那么尋找最少空洞數(shù)柵欄轉(zhuǎn)化為尋找監(jiān)測區(qū)域最左側(cè)φ₀到最右側(cè)φ₁間的最短路徑，這里說的最短即權(quán)值最小，因此我們將圖論中求最短路徑引入，查找最少空洞數(shù)柵欄，圖論中最短路徑算法得到的最短路徑即所尋找的最少空洞數(shù)柵欄。

2.根據(jù)權(quán)利要求1的混合傳感網(wǎng)中基于最少空洞數(shù)柵欄的柵欄修補方法，其特征在于，所述方法還包括確定混合傳感網(wǎng)中柵欄中空洞位置：

對于最少空洞數(shù)柵欄上的任意兩個相鄰的傳感器節(jié)點，由于它們之間的空洞數(shù)為ω(e)，對第k個空洞h_k(x,y)，其位置表示如下：

h_k(x,y)＝(x_i+k×Δx,y_i+k×Δy)k∈[1,w(e)]，

其中ω(e)為最少空洞數(shù)柵欄上的任意兩個相鄰的傳感器節(jié)點之間的空洞數(shù)，根據(jù)以上兩式確定出需修補柵欄中所有的空洞位置。

3.根據(jù)權(quán)利要求1的混合傳感網(wǎng)中基于最少空洞數(shù)柵欄的柵欄修補方法，其特征在于，所述方法還包括尋找空洞與移動節(jié)點的最優(yōu)匹配，減少所有移動節(jié)點的移動距離和：

利用節(jié)點的移動性，移動部分傳感器節(jié)點去修補柵欄中的空洞，因此調(diào)節(jié)移動節(jié)點去修補某一個或多個空洞問題等同于空洞與移動節(jié)點間最優(yōu)匹配的問題，最優(yōu)匹配即要求找到使所有移動節(jié)點移動距離最小，假設(shè)所有的移動節(jié)點表示為

X＝{x₁,...,x_M}

柵欄中覆蓋空洞表示為

Y＝{y₁,...,y_H}

對于由所有移動性節(jié)點與覆蓋空洞組成的二分圖G(V，E)，V＝X∪Y并且其中邊集E＝{e_ij,i∈X,j∈Y}，對于每一條邊e_ij表示移動節(jié)點x_i與覆蓋空洞y_j的連線都有一個權(quán)值，用于表示移動節(jié)點移動到空洞位置進行空洞修補所需要移動的距離。