[發(fā)明專(zhuān)利]一種基于回收替換的覆蓋空洞消除方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310581075.9
• 申請(qǐng)日: 2013-11-19
• 公開(kāi)（公告）號(hào): CN103716806B
• 公開(kāi)（公告）日: 2017-02-15
• 發(fā)明（設(shè)計(jì)）人: 范興剛;林星星;張兆娟;王恒
• 申請(qǐng)（專(zhuān)利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類(lèi)號(hào): H04W24/00
• 分類(lèi)號(hào): H04W24/00;H04W16/18
• 代理公司: 杭州天正專(zhuān)利事務(wù)所有限公司33201
• 代理人: 王兵,黃美娟

1.一種基于回收替換的覆蓋空洞消除方法，所述的方法包括以下步驟：

步驟1，基于網(wǎng)格的覆蓋空洞檢測(cè)算法

在N個(gè)節(jié)點(diǎn)隨機(jī)部署后，采用leach協(xié)議分簇，采用網(wǎng)格法計(jì)算覆蓋度C₀，覆蓋空洞數(shù)H和冗余節(jié)點(diǎn)數(shù)R（網(wǎng)絡(luò)中只有這二類(lèi)節(jié)點(diǎn)）；sink節(jié)點(diǎn)收集這些信息后，通知移動(dòng)節(jié)點(diǎn)；這時(shí)能量充電站，sink節(jié)點(diǎn)，移動(dòng)機(jī)器人處于同一個(gè)位置；基于網(wǎng)格的覆蓋空洞檢測(cè)算法具體操作步驟如下：

基于網(wǎng)格的覆蓋空洞檢測(cè)算法具體操作步驟如下：

（1.1）將感知區(qū)間用邊長(zhǎng)為1的網(wǎng)格劃分出來(lái)，確定網(wǎng)格的中心點(diǎn)；計(jì)算每個(gè)網(wǎng)格中心點(diǎn)與各個(gè)節(jié)點(diǎn)的距離，從而判斷該網(wǎng)格是否被覆蓋；將未被覆蓋的網(wǎng)格位置記錄下來(lái)；被第k個(gè)節(jié)點(diǎn)覆蓋的網(wǎng)格標(biāo)記定義一個(gè)矩陣，其元素表示網(wǎng)格點(diǎn)，由公式1來(lái)判定網(wǎng)格是否屬于節(jié)點(diǎn)k的感應(yīng)區(qū)域。；

aj,ki=1,fji∈Rk0else∀i,j=1,...,M,∀k=1,...,N---(1)]]>

（1.2）設(shè)置網(wǎng)格對(duì)應(yīng)的覆蓋矩陣，覆蓋度為0的網(wǎng)格c_i,j=0，覆蓋度為1的網(wǎng)格，c_i,j=1，依此類(lèi)推；

（1.3）對(duì)連續(xù)的未被覆蓋的網(wǎng)格進(jìn)行合并，合并的時(shí)候，采用寬度搜索和深度搜索相結(jié)合的方法可以得空洞的數(shù)量和每一個(gè)空洞面積，同時(shí)確定漏洞的位置；

（1.4）計(jì)算每個(gè)節(jié)點(diǎn)的覆蓋網(wǎng)格被鄰居節(jié)點(diǎn)重疊覆蓋的比率，如果節(jié)點(diǎn)i覆蓋范圍內(nèi)的網(wǎng)格覆蓋度大于等于2，則此網(wǎng)格被重疊覆蓋；如果重疊覆蓋率大于90%，此節(jié)點(diǎn)為冗余節(jié)點(diǎn)；

（1.5）分別計(jì)算覆蓋空洞總數(shù)、重點(diǎn)空洞總數(shù)和臨界空洞總數(shù)，為下一步的空洞修補(bǔ)作準(zhǔn)備；

步驟2，計(jì)算移動(dòng)機(jī)器人攜帶的節(jié)點(diǎn)數(shù)；

需要回收替換的A類(lèi)節(jié)點(diǎn)數(shù)為H₁，初始布置的網(wǎng)絡(luò)，需要回收的節(jié)點(diǎn)數(shù)為H₁=0，即H₁=0如果空洞面積較大，可能要用2個(gè)或者更多的節(jié)點(diǎn)修補(bǔ)空洞，這里假設(shè)空洞面積較小，最多用2個(gè)節(jié)點(diǎn)修補(bǔ)空洞可以滿(mǎn)足要求；需要用2個(gè)節(jié)點(diǎn)修補(bǔ)的空洞數(shù)為H₂；需要一個(gè)節(jié)點(diǎn)修補(bǔ)的空洞數(shù)為H₃；則修補(bǔ)覆蓋空洞，替換節(jié)點(diǎn)總共需要的節(jié)點(diǎn)數(shù)為M₁；

M₁=M_r+H₁+2H₂+H₃???（2）公式（2）中，M_r表示上一周期中未被替換的剩余節(jié)點(diǎn)數(shù)，該值可能為0；假設(shè)網(wǎng)絡(luò)里冗余節(jié)點(diǎn)數(shù)為R，移動(dòng)機(jī)器人需要攜帶的節(jié)點(diǎn)數(shù)為

Mn=M1-R+In,ifM1>RIn,ifM1=RM1-R+In,ifM1<R---(3)]]>

在公式（3）中，I_n表示在第n輪替換周期中被替換之前沒(méi)有冗余節(jié)點(diǎn)可選的節(jié)點(diǎn)數(shù)；其中第三種情況表示，冗余節(jié)點(diǎn)數(shù)大于修補(bǔ)覆蓋空洞需要的節(jié)點(diǎn)數(shù)時(shí)，移動(dòng)機(jī)器人回收，帶回的冗余節(jié)點(diǎn)數(shù)為R-M₁+I_n；移動(dòng)機(jī)器人實(shí)際攜帶的節(jié)點(diǎn)數(shù)為

M=Mn,ifMn≤QQ,ifMn>Q]]>

如果需要攜帶節(jié)點(diǎn)數(shù)大于Q，這時(shí)有M_r=M-Q，先替換節(jié)點(diǎn)，再修補(bǔ)面積較大的空洞；

步驟3，回收替換路徑計(jì)算；根據(jù)距離空洞最近的冗余節(jié)點(diǎn)修補(bǔ)空洞的原則，移動(dòng)機(jī)器人在網(wǎng)絡(luò)中移動(dòng)，回收冗余節(jié)點(diǎn)，修補(bǔ)空洞；這時(shí)目標(biāo)函數(shù)變?yōu)?/p>

min S=ΣmΣnd(m,n)xmn,m∈R,n∈H]]>

采用粒子群算法進(jìn)行路徑分析，計(jì)算移動(dòng)節(jié)點(diǎn)替換回收節(jié)點(diǎn)的移動(dòng)路徑；

步驟4，移動(dòng)機(jī)器人遍歷各個(gè)服務(wù)點(diǎn)，回收替換節(jié)點(diǎn)，這時(shí)的覆蓋密度為

Cρ=N+MA,]]>覆蓋區(qū)域內(nèi)的能量密度Eρ=(N+M)*eA;]]>

步驟5，移動(dòng)節(jié)點(diǎn)回到能量站后立給回收的節(jié)點(diǎn)充電，給移動(dòng)節(jié)點(diǎn)充電。假設(shè)給移動(dòng)節(jié)點(diǎn)充電時(shí)間為T(mén)_c；

步驟6，計(jì)算下一次回收替換的時(shí)間，回到步驟2，觸發(fā)節(jié)點(diǎn)的回收替換；回收替換周期時(shí)間計(jì)算方法如下：

假設(shè)移動(dòng)機(jī)器人回到充電站的時(shí)間為T(mén)₀，充電完成時(shí)間為T(mén)_c，能量站收到第一個(gè)替換請(qǐng)求的時(shí)間為T(mén)_r1，依次為T(mén)_r2,T_r3......，且T_r1<T_r2<T_r3<…<T_rn<…

T=T0+Tc,ifMr>0T0+Trn,ifn>23Q andTrn>T0+Tc]]>

當(dāng)在T_c內(nèi)，到達(dá)的請(qǐng)求n>1.5Q時(shí)，認(rèn)為網(wǎng)絡(luò)需要增加節(jié)點(diǎn)部署；

當(dāng)在T_c內(nèi)，到達(dá)的請(qǐng)求n<0.1Q時(shí)，認(rèn)為網(wǎng)絡(luò)達(dá)到平衡狀態(tài)。