二分圖最優(yōu)匹配算法的WSN覆蓋空洞修復(fù)策略

崔麗珍，李曉宇，路靜超，史明泉

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010) E-mail ：1527171123@qq.com

1 引 言

微電子技術(shù)、無線通信技術(shù)及計(jì)算機(jī)網(wǎng)絡(luò)等技術(shù)的進(jìn)步推動(dòng)了自組織WSN(wireless sensor networks)的迅速發(fā)展.WSN在軍事領(lǐng)域、環(huán)境監(jiān)測(cè)、醫(yī)療健康等多個(gè)領(lǐng)域中有著極為廣泛的應(yīng)用，受到越來越多研究者的關(guān)注.覆蓋問題[1-3]對(duì)于WSN的研究至關(guān)重要，網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)由于自身能量消耗殆盡或受外界因素影響而失效，失效節(jié)點(diǎn)的存在會(huì)使網(wǎng)絡(luò)出現(xiàn)覆蓋空洞[4，5]，嚴(yán)重影響網(wǎng)絡(luò)對(duì)周圍物理環(huán)境的監(jiān)測(cè)質(zhì)量.因此，如何準(zhǔn)確獲得空洞的位置并對(duì)其進(jìn)行及時(shí)修復(fù)成為近幾年研究的熱點(diǎn)問題.王良民[6]提出一種三角形貼片式逐步增加移動(dòng)節(jié)點(diǎn)的空洞修復(fù)方法，利用空洞邊緣節(jié)點(diǎn)提供的信息指導(dǎo)移動(dòng)節(jié)點(diǎn)移動(dòng)到最佳位置，但該方法沒有給出空洞邊緣節(jié)點(diǎn)檢測(cè)方法.劉全[7]提出一種三角形網(wǎng)格空洞修復(fù)算法，該方法利用ATN算法檢測(cè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)構(gòu)成的三角形網(wǎng)格是否被完全覆蓋，若沒有則利用TNR算法通過向三角形網(wǎng)格特定位置添加節(jié)點(diǎn)使三角形網(wǎng)格達(dá)到完全覆蓋，該算法無地理信息支持，因此在修復(fù)過程中難免會(huì)出現(xiàn)節(jié)點(diǎn)冗余.Fang[8]提出基于Voronoi圖形心的空洞修復(fù)策略，該方法對(duì)監(jiān)測(cè)區(qū)域作Voronoi劃分得到節(jié)點(diǎn)所在的泰森多邊形，根據(jù)Voronoi多邊形頂點(diǎn)的覆蓋情況得出其中的盲區(qū)，將節(jié)點(diǎn)移動(dòng)到盲區(qū)內(nèi)的目標(biāo)位置進(jìn)行修復(fù)，但節(jié)點(diǎn)0-1感知模型過于理想化，不能準(zhǔn)確反映實(shí)際感知情況.Fan[9]等人提出基于改進(jìn)混合粒子群優(yōu)化算法的空洞消除方法，同時(shí)考慮移動(dòng)節(jié)點(diǎn)的位移、能耗和網(wǎng)絡(luò)能量平衡，將合適的冗余節(jié)點(diǎn)移動(dòng)到空洞處，從而提高事件探測(cè)率，但冗余節(jié)點(diǎn)的判定會(huì)增加算法復(fù)雜度.Kukunuru[10]結(jié)合Voronoi圖劃分和虛擬力算法的優(yōu)勢(shì)，提出一種混合空洞探測(cè)算法，分別利用Voronoi圖和虛擬力算法探測(cè)、修復(fù)空洞，當(dāng)兩個(gè)節(jié)點(diǎn)距離太近時(shí)受虛擬斥力作用相互排斥，距離太遠(yuǎn)時(shí)則受虛擬引力作用相互吸引，修復(fù)節(jié)點(diǎn)在移動(dòng)過程中可能受到其他方向的作用力，整體的合力決定修復(fù)節(jié)點(diǎn)的移動(dòng)方向和移動(dòng)能夠距離.

綜合以上研究成果的分析，本文提出一種基于二分圖最優(yōu)匹配算法的空洞修復(fù)策略.通過對(duì)監(jiān)測(cè)區(qū)域進(jìn)行網(wǎng)格劃分評(píng)價(jià)每個(gè)網(wǎng)格點(diǎn)的探測(cè)率從而檢測(cè)出覆蓋空洞，并對(duì)空洞進(jìn)行虛擬修復(fù).然后采用圖論學(xué)中解決最優(yōu)分配問題的KM算法將網(wǎng)絡(luò)中的修復(fù)節(jié)點(diǎn)與空洞位置進(jìn)行配對(duì)并將修復(fù)節(jié)點(diǎn)移動(dòng)到與之匹配的空洞位置上.仿真結(jié)果證明了該策略的可行性，在保證好網(wǎng)絡(luò)覆蓋率的同時(shí)減少了修復(fù)節(jié)點(diǎn)能耗，延長了網(wǎng)絡(luò)壽命.

2 網(wǎng)絡(luò)模型

覆蓋問題中最常用的節(jié)點(diǎn)探測(cè)模型是0/1模型.0/1模型假設(shè)節(jié)點(diǎn)的探測(cè)范圍是以節(jié)點(diǎn)位置為圓心的一個(gè)圓形區(qū)域，若目標(biāo)出現(xiàn)在探測(cè)圓內(nèi)，則探測(cè)概率為1；若出現(xiàn)在探測(cè)圓外，則探測(cè)概率為0.0/1模型雖得到廣泛應(yīng)用，但該模型過于理想化，在現(xiàn)實(shí)環(huán)境中適應(yīng)性較差.Neyman-Pearson模型同時(shí)考慮了信號(hào)傳輸特性和節(jié)點(diǎn)誤警率，更貼近實(shí)際應(yīng)用.下面建立Neyman-Pearson模型.

節(jié)點(diǎn)i從目標(biāo)所接收到的能量為

(1)

式中，yi為節(jié)點(diǎn)i接收到的能量；H0和H1表示目標(biāo)存在和目標(biāo)缺失的情形；ni為均值為0、方差為σ2的高斯噪聲；β定義為

(2)

其中，S為探測(cè)目標(biāo)節(jié)點(diǎn)的能量，γ為路徑損失系數(shù)；Rij為節(jié)點(diǎn)i與目標(biāo)j的歐式距離.

(3)

在H0和H1狀態(tài)下，yi的概率密度函數(shù)分別為

(4)

(5)

根據(jù)Neyman-Pearson判決準(zhǔn)則，探測(cè)概率PD為

(6)

式中，α為誤警率；φ(·)為標(biāo)準(zhǔn)正態(tài)分布的累積分布函數(shù).

當(dāng)區(qū)域內(nèi)有K個(gè)節(jié)點(diǎn)時(shí)，目標(biāo)j被探測(cè)到的聯(lián)合探測(cè)概率為

(7)

3 KM算法

KM算法是Kuhn和Munkres分別于1955年和1957年提出的一個(gè)解決最優(yōu)分配問題的經(jīng)典算法，可行頂點(diǎn)標(biāo)記和相等子圖是KM算法的理論基礎(chǔ).KM算法涉及的基本概念如下：

二分圖：若圖G的頂點(diǎn)集可分為X，Y兩個(gè)非空子集，且圖中的每條邊都有一個(gè)頂點(diǎn)在X中，另一個(gè)頂點(diǎn)在Y中，則稱圖G為二分圖.

增廣路：若M是圖G的一個(gè)匹配，設(shè)從圖G中某一頂點(diǎn)到另一頂點(diǎn)存在一條路，且這條路是由M中的邊和非M中的邊交替出現(xiàn)的，則稱這條路為增廣路；匹配M中邊的頂點(diǎn)稱為M飽和點(diǎn)，其他點(diǎn)稱為M非飽和點(diǎn).

最優(yōu)匹配：設(shè)二分圖G中每條邊都有權(quán)ωij≥0，若能找到匹配M使得所有單個(gè)匹配的邊權(quán)和最大(最小)，則稱M為G的一個(gè)最優(yōu)匹配.

完備匹配：對(duì)于二分圖G，如果G中每個(gè)頂點(diǎn)都是M中的一個(gè)匹配頂點(diǎn)，則稱M為G的完備匹配.

設(shè)二分圖G=(V，E)，其中兩個(gè)頂點(diǎn)集分別為X={x1，x2，…，xn}，Y={y1，y2，…，yn}，給圖G中任意邊賦權(quán)ωij=ω(xiyj).設(shè)L為二分圖G中頂點(diǎn)集到實(shí)數(shù)集的映射，若對(duì)任意的x∈X，y∈Y，均存在L(x)+L(y)≥ω(xy)，則稱L為此二分圖G的可行頂點(diǎn)標(biāo)記；令EL={xy|e=xy∈E(G)，且L(x)+L(y)=ω(e)}，稱EL為圖G的相等子圖.若二分圖G的相等子圖有完備匹配，則該匹配是圖G的最優(yōu)匹配.該算法是通過給圖中每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)把求最優(yōu)匹配問題轉(zhuǎn)化為不斷尋找增廣路以使二分圖的匹配數(shù)達(dá)到最大的問題.

KM算法的核心思想就是反復(fù)修改頂點(diǎn)標(biāo)號(hào)，使得新的相等子圖的邊不斷增加，直至所有頂點(diǎn)都進(jìn)入相等子圖.算法步驟如下：

設(shè)G為賦權(quán)二分圖，L是其初始可行頂點(diǎn)標(biāo)號(hào)，取

(8)

1)若X的每個(gè)點(diǎn)都是M飽和的，則M是最佳匹配；否則，取M得非飽和點(diǎn)u∈X，令S={u}，T=φ轉(zhuǎn)向2).

2)記NL(S)={v|u∈S，uv∈EL}.若存在NL(S)=T，則GL沒有完備匹配，轉(zhuǎn)向3)；否則，轉(zhuǎn)向4).

3)調(diào)整可行頂點(diǎn)標(biāo)記，計(jì)算

aL=min{L(x)+L(y)-F(xy)|x∈S，y∈Y/T}

(9)

由此可得新的可行頂點(diǎn)標(biāo)記為

(10)

令L=H，GL=GH，重新給出GL的一個(gè)匹配M，轉(zhuǎn)向1).

4)取y∈NL(S)/T，若y是M的飽和點(diǎn)，轉(zhuǎn)向5)；否則，轉(zhuǎn)向6).

5)設(shè)xy∈M，則令S=S∪{x}，T=T∪{y}，轉(zhuǎn)向2).

6)在GL中的(u，y)路是M增廣路，記為P，并令M=M⊕P，轉(zhuǎn)向1).

4 覆蓋空洞修復(fù)算法

4.1 覆蓋評(píng)價(jià)指標(biāo)

本文采用將區(qū)域覆蓋轉(zhuǎn)化為點(diǎn)覆蓋的方法評(píng)價(jià)網(wǎng)絡(luò)覆蓋效果.假設(shè)目標(biāo)監(jiān)測(cè)區(qū)域?yàn)锳×B(m2)的二維平面，將監(jiān)測(cè)區(qū)域劃分成A×B個(gè)單位網(wǎng)格，可得到(A+1)×(B+1)個(gè)單位網(wǎng)格點(diǎn)，根據(jù)公式(7)計(jì)算每個(gè)網(wǎng)格點(diǎn)的聯(lián)合探測(cè)概率.對(duì)每個(gè)網(wǎng)格點(diǎn)的探測(cè)概率設(shè)定一個(gè)閾值Ps，如果計(jì)算所得探測(cè)率值小于Ps，則認(rèn)為該網(wǎng)格點(diǎn)為覆蓋空洞點(diǎn)，反之則認(rèn)為被有效覆蓋；可將第k個(gè)網(wǎng)格點(diǎn)的覆蓋狀態(tài)定義為

(11)

區(qū)域覆蓋率可定義為所有網(wǎng)格點(diǎn)的覆蓋狀態(tài)值之和與監(jiān)測(cè)區(qū)域面積之比，即

(12)

4.2 覆蓋空洞檢測(cè)與虛擬修復(fù)

將一定數(shù)量的靜止節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)混合部署到監(jiān)測(cè)區(qū)域內(nèi)，且所有移動(dòng)節(jié)點(diǎn)切換至休眠狀態(tài)，只保留靜止節(jié)點(diǎn)參與初始覆蓋.在整個(gè)監(jiān)測(cè)區(qū)域內(nèi)，所有節(jié)點(diǎn)的探測(cè)概率呈近似指數(shù)形式衰減，因此各個(gè)網(wǎng)格點(diǎn)位置上的探測(cè)概率是連續(xù)的.通過公式(11)依次計(jì)算每一個(gè)網(wǎng)格點(diǎn)的覆蓋狀態(tài)值，狀態(tài)值為零的網(wǎng)格點(diǎn)不能被任何節(jié)點(diǎn)所探測(cè)到，一定范圍內(nèi)狀態(tài)值連續(xù)為零的區(qū)域即構(gòu)成一個(gè)完整的覆蓋空洞，記錄空洞邊緣各個(gè)網(wǎng)格點(diǎn)的位置信息.

檢測(cè)出監(jiān)測(cè)區(qū)域內(nèi)的全部覆蓋空洞后，對(duì)每一個(gè)空洞分別取其橫向、縱向最大最小四個(gè)邊緣網(wǎng)格點(diǎn)的坐標(biāo)集，并將這些點(diǎn)按順時(shí)針方向排序，記為U={(x1，y1)，(x2，y2)，(x3，y3)，(x4，y4)}，將每個(gè)點(diǎn)集中的點(diǎn)連接起來構(gòu)成一個(gè)四邊形，求該四邊形的形心坐標(biāo)(X0，Y0)[8]，計(jì)算公式定義為

(13)

(14)

(15)

在以上公式計(jì)算所得的空洞四邊形的形心位置上放置一個(gè)虛擬節(jié)點(diǎn)，首先以該虛擬節(jié)點(diǎn)為中心在其左右側(cè)搜索探測(cè)概率最小值點(diǎn)，在此最小值點(diǎn)上放置虛擬節(jié)點(diǎn)，繼續(xù)搜索上一個(gè)虛擬節(jié)點(diǎn)左右側(cè)的探測(cè)概率最小值點(diǎn)并放置虛擬節(jié)點(diǎn)，直至兩端最后一個(gè)虛擬節(jié)點(diǎn)的通信范圍內(nèi)再?zèng)]有探測(cè)率值低于Ps的點(diǎn)出現(xiàn)；然后以上一步水平方向上每個(gè)已放置好的虛擬節(jié)點(diǎn)為中心，再在該點(diǎn)上下側(cè)搜索探測(cè)概率最小值點(diǎn)，直到空洞中再?zèng)]有探測(cè)率值低于Ps的點(diǎn)為止.按照同樣的方法對(duì)網(wǎng)絡(luò)中的所有空洞進(jìn)行虛擬修復(fù).

4.3 KM算法在空洞修復(fù)中的實(shí)際應(yīng)用

KM算法可以很好地解決空洞修復(fù)中虛擬節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)之間的匹配問題.實(shí)際情況中節(jié)點(diǎn)能量有限，如果節(jié)點(diǎn)在修復(fù)過程中移動(dòng)距離太長，則節(jié)點(diǎn)到達(dá)空洞中時(shí)剩余能量已不足，為避免新修復(fù)的空洞因移動(dòng)節(jié)點(diǎn)剩余能量較少而再次出現(xiàn)新的空洞，需限定單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離，記為d.令虛擬節(jié)點(diǎn)集合為X={x1，x2，…，xm}，移動(dòng)節(jié)點(diǎn)集合為Y={y1，y2，…，yn}，計(jì)算虛擬節(jié)點(diǎn)集內(nèi)與移動(dòng)節(jié)點(diǎn)集內(nèi)所有點(diǎn)之間的歐式距離.每個(gè)移動(dòng)節(jié)點(diǎn)與其最大移動(dòng)距離內(nèi)可匹配的虛擬節(jié)點(diǎn)之間的距離權(quán)值為二維矩陣為ω[m，n]，其他超過最大移動(dòng)距離的規(guī)定其權(quán)值為0.

在使用KM算法求最優(yōu)匹配時(shí)要求集合X和集合Y中的頂點(diǎn)個(gè)數(shù)必須相同，但在空洞修復(fù)的應(yīng)用中無法預(yù)先確定所需虛擬節(jié)點(diǎn)的個(gè)數(shù)，因此規(guī)定：如果計(jì)算所得虛擬節(jié)點(diǎn)個(gè)數(shù)多于監(jiān)測(cè)區(qū)域內(nèi)已部署的移動(dòng)節(jié)點(diǎn)個(gè)數(shù)，則添加一部分空移動(dòng)節(jié)點(diǎn)，使它們的數(shù)目相等，與空移動(dòng)節(jié)點(diǎn)相關(guān)的權(quán)值都為0；同理，如果移動(dòng)節(jié)點(diǎn)個(gè)數(shù)多于虛擬節(jié)點(diǎn)個(gè)數(shù)，則添加一些空虛擬節(jié)點(diǎn)使其數(shù)目相等，與空虛擬節(jié)點(diǎn)相關(guān)的權(quán)值也都為0.在經(jīng)過算法匹配后，剔除掉那些權(quán)值為0的匹配和與空節(jié)點(diǎn)相關(guān)的匹配(如果有的話)，從而得到虛擬節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)之間的最優(yōu)匹配方案，最后依次將每個(gè)移動(dòng)節(jié)點(diǎn)移動(dòng)到方案中與其匹配的虛擬節(jié)點(diǎn)位置上，達(dá)到空洞修復(fù)的目的.本文實(shí)現(xiàn)空洞修復(fù)的流程如圖1所示.

圖1 空洞修復(fù)流程圖Fig.1 Coverage hole healing flow chart

5 實(shí)驗(yàn)結(jié)果及分析

設(shè)網(wǎng)絡(luò)由50個(gè)靜止節(jié)點(diǎn)和30個(gè)移動(dòng)節(jié)點(diǎn)混合部署在200m×200m的方形區(qū)域內(nèi)，節(jié)點(diǎn)通信半徑均為20m，節(jié)點(diǎn)誤警率α=0.05，β=20，γ=2，σ=1，限定單個(gè)移動(dòng)節(jié)點(diǎn)最大移動(dòng)距離d=50m，監(jiān)測(cè)區(qū)域內(nèi)每一點(diǎn)的探測(cè)概率閾值Ps=0.5.匯聚節(jié)點(diǎn)定期檢測(cè)空洞并計(jì)算空洞中所需修復(fù)節(jié)點(diǎn)個(gè)數(shù)及網(wǎng)絡(luò)覆蓋率，喚醒移動(dòng)節(jié)點(diǎn)移動(dòng)到指定的位置進(jìn)行修復(fù).將本文算法與文獻(xiàn)[11]的C-V算法和文獻(xiàn)[12]的MNCO算法做對(duì)比以驗(yàn)證本文算法的有效性.

圖2為網(wǎng)絡(luò)空洞修復(fù)前后的節(jié)點(diǎn)分布圖，圖中○表示靜止節(jié)點(diǎn)，☆表示移動(dòng)節(jié)點(diǎn).靜止節(jié)點(diǎn)位置不發(fā)生變化.圖(a)中靜止節(jié)點(diǎn)和移動(dòng)節(jié)點(diǎn)混合部署于監(jiān)測(cè)區(qū)域內(nèi)，節(jié)點(diǎn)整體分布很不均勻，由此產(chǎn)生覆蓋空洞；圖(b)中移動(dòng)節(jié)點(diǎn)都向稀疏處分散，移動(dòng)到特定的空洞位置上.修復(fù)之后的網(wǎng)絡(luò)節(jié)點(diǎn)分布更均勻，網(wǎng)絡(luò)覆蓋率得以提高.由于移動(dòng)節(jié)點(diǎn)成本相對(duì)較高，實(shí)際情況中應(yīng)綜合考慮網(wǎng)絡(luò)覆蓋率與網(wǎng)絡(luò)成本的關(guān)系，合理部署移動(dòng)節(jié)點(diǎn).

圖2 傳感器節(jié)點(diǎn)分布圖Fig.2 Distribution of sensor nodes

圖3 移動(dòng)節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)覆蓋率關(guān)系Fig.3 Relation of mobile nodes number and network coverage rate

圖3為移動(dòng)節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)覆蓋率之間的關(guān)系圖.在檢測(cè)出空洞后，隨著被喚醒移動(dòng)節(jié)點(diǎn)數(shù)量的增加，3種算法的網(wǎng)絡(luò)覆蓋率都在隨之而上升，當(dāng)移動(dòng)節(jié)點(diǎn)數(shù)小于16時(shí)，本文算法的覆蓋率優(yōu)于MNCO算法，略遜于C-V算法，但之后本文算法的覆蓋率可持續(xù)上升，而其他兩種算法則趨于飽和.當(dāng)移動(dòng)節(jié)點(diǎn)數(shù)增加到30時(shí)，本文算法的覆蓋率達(dá)到97.75%，而C-V算法的覆蓋率為93.43%，MNCO算法的覆蓋率為91.77%，本文算法的覆蓋率明顯高于其他兩種算法.

圖4為移動(dòng)節(jié)點(diǎn)數(shù)與平均移動(dòng)距離之間的關(guān)系圖.由圖可知，移動(dòng)節(jié)點(diǎn)數(shù)對(duì)其平均移動(dòng)距離的影響較為明顯，3種算法的平均移動(dòng)距離均隨移動(dòng)節(jié)點(diǎn)數(shù)的增加而降低.相比MNCO算法和C-V算法，本文算法性能相對(duì)較好，在被喚醒移動(dòng)節(jié)點(diǎn)數(shù)相同的情況下平均移動(dòng)距離保持最短，這是由于KM算法不斷尋找二分圖中的增廣路徑，在保證每個(gè)移動(dòng)節(jié)點(diǎn)都有虛擬節(jié)點(diǎn)與之匹配的同時(shí)可使總的平均移動(dòng)距離最短，節(jié)點(diǎn)在移動(dòng)過程中的能耗最低.

圖4 移動(dòng)節(jié)點(diǎn)數(shù)與平均移動(dòng)距離關(guān)系Fig.4 Relation of mobile nodes number and average mobile distance

6 結(jié) 論

針對(duì)WSN中的覆蓋空洞問題，本文采用更加貼近實(shí)際應(yīng)用的Neyman-Pearson節(jié)點(diǎn)探測(cè)模型，提出了基于二分圖最優(yōu)匹配算法的空洞修復(fù)策略.仿真實(shí)驗(yàn)證明了該策略的可行性和優(yōu)越性.在混合WSN中，移動(dòng)修復(fù)節(jié)點(diǎn)能以較短的平均移動(dòng)距離有效提高網(wǎng)絡(luò)覆蓋率，保證修復(fù)節(jié)點(diǎn)有足夠的剩余能量用以網(wǎng)絡(luò)監(jiān)測(cè)，延長了網(wǎng)絡(luò)的生存周期.

[1] Mishra T，Panda A R，Lenka M R，et al.Energy efficient coverage and connectivity with varying energy level in WSN[C].Proceedings of the International Conference on Computational Intelligence and Networks(CINE)，2015：86-91.

[2] Singh D P，Goudar R H，Rao S.Coverage lifetime improvement through efficient deployment of sensor nodes in WSN[J].International Journal of System Assurance Engineering and Management，2016，7(2)：1-12.

[3] Xia J.Coverage optimization strategy of wireless sensor network based on swarm intelligence algorithm[C].Proceedings of the International Conference on Smart City and Systems Engineering(ICSCSE)，2016：179-182.

[4] Nguyen P L，Nguyen K V，Huy V Q，et al.A time and energy efficient protocol for locating coverage holes in WSNs[C].Proceedings of the 41st IEEE Conference on Local Computer Networks(LCN)，2016：180-183.

[5] Qiu C，Shen H，Chen K.An energy-efficient and distributed cooperation mechanism for kcoverage hole detection and healing in WSNs[C].Proceedings of the 12th IEEE International Conference on Mobile Ad Hoc and Sensor Systems(MASS)，2015：73-81.

[6] Wang Liang-ming，Li Fei，Qin Ying.Resilient method for recovering coverage holes of wireless sensor networks by using mobile nodes[J].Journal on Communications，2011，32(4)：1-8.

[7] Liu Quan，Yang Kai，F(xiàn)u Yu-chen，et al.An algorithm for hole recovery in wireless sensor networks based on triangle net[J].Chinese Journal of Electronics，2013，41(2)：209-213.

[8] Fang Wei，Song Xin-hong.A deployment strategy for coverage control in wireless sensor networks based on the blind-zone of Voronoi diagram[J].Acta Physica Sinica，2014，63(22)：128-137.

[9] Fan X，Zhang Z，Lin X，et al.Coverage hole elimination based on sensor intelligent redeployment in WSN[C].Proceedings of the 4th Annual IEEE International Conference on Cyber Technology in Automation，Control，and Intelligent Systems(CYBER)，2014：336-339.

[10] Kukunuru N，Rajyalakshmi D，Damodaram A.Hybrid approach for detecting and healing the coveragehole in Wireless Sensor Network[C].Proceedings of the International Conference on Signal Propagation and Computer Technology(ICSPCT)，2014：110-115.

[11] Hu Nan，Wu Cheng-dong，Yu Xiao-sheng，et al.Network coverage holes detecting and healing algorithm based on C-V model[J].Control and Decision，2016，31(8)：1424-1428.

[12] Huang Yue，Wu Cheng-dong，Zhang Yun-zhou，et al.Coverage optimization of wireless sensor networks based on mobile nodes[J].Journal of Northeastern University(Natural Science)，2012，33(2)：165-168.

附中文參考文獻(xiàn)：

[6] 王良民，李 菲，秦 穎.基于移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)覆蓋洞修復(fù)方法[J].通信學(xué)報(bào)，2011，32(4)：1-8.

[7] 劉 全，楊 凱，伏玉琛，等.一種三角形網(wǎng)格空洞修復(fù)算法[J].電子學(xué)報(bào)，2013，41(2)：209-213.

[8] 方 偉，宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J].物理學(xué)報(bào)，2014，63(22)：128-137.

[11] 胡 楠，吳成東，于曉升，等.基于C-V模型的網(wǎng)絡(luò)覆蓋空洞探測(cè)與修復(fù)算法[J].控制與決策，2016，31(8)：1424-1428.

[12] 黃 月，吳成東，張?jiān)浦?，?基于移動(dòng)節(jié)點(diǎn)的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].東北大學(xué)學(xué)報(bào)自然科學(xué)版，2012，33(2)：165-168.

第35屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議(NDBC 2018)征文通知

第35屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議(NDBC 2018,會(huì)議編號(hào)CCF-18-TC21-01N)將于2018年10月12日至14日在遼寧省大連市舉行.本屆大會(huì)由中國計(jì)算機(jī)學(xué)會(huì)(CCF)主辦，CCF數(shù)據(jù)庫專業(yè)委員會(huì)、大連海事大學(xué)和中國人民大學(xué)承辦，大連理工大學(xué)、大連海洋大學(xué)、遼寧師范大學(xué)，大連外國語大學(xué)、大連大學(xué)、大連計(jì)算機(jī)學(xué)會(huì)協(xié)辦.本屆大會(huì)主要關(guān)注數(shù)據(jù)庫技術(shù)所面臨的新的挑戰(zhàn)問題和研究方向，著力反映我國數(shù)據(jù)庫技術(shù)研究的最新進(jìn)展，為數(shù)據(jù)庫研究人員和數(shù)據(jù)庫開發(fā)和應(yīng)用相關(guān)企業(yè)搭建交流平臺(tái).大會(huì)期間將設(shè)立多個(gè)論壇，將繼續(xù)設(shè)立“系統(tǒng)演示”主題，開設(shè)“研究生論文指導(dǎo)計(jì)劃”研討班等.屆時(shí)還將邀請(qǐng)國內(nèi)外數(shù)據(jù)庫領(lǐng)域著名專家到會(huì)作專題報(bào)告.我們誠征數(shù)據(jù)管理及其應(yīng)用領(lǐng)域的論文、專題討論與系統(tǒng)演示報(bào)告等.

1.征文范圍(不限于這些領(lǐng)域)

數(shù)據(jù)庫實(shí)現(xiàn)新技術(shù)云計(jì)算中的數(shù)據(jù)管理Web數(shù)據(jù)管理查詢處理與查詢優(yōu)化數(shù)據(jù)流管理XML和半結(jié)構(gòu)化數(shù)據(jù)數(shù)據(jù)倉庫和OLAP近似和非確定性數(shù)據(jù)庫內(nèi)容與知識(shí)管理數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)元數(shù)據(jù)管理數(shù)據(jù)集成和遷移嵌入與移動(dòng)數(shù)據(jù)庫并行和分布數(shù)據(jù)庫系統(tǒng)特定領(lǐng)域數(shù)據(jù)庫數(shù)據(jù)庫自管理智能用戶接口技術(shù)空間和時(shí)態(tài)數(shù)據(jù)庫多媒體數(shù)據(jù)庫技術(shù)數(shù)據(jù)隱私和安全信息檢索與數(shù)據(jù)庫物聯(lián)網(wǎng)數(shù)據(jù)管理數(shù)據(jù)庫系統(tǒng)性能評(píng)測(cè)新硬件下的數(shù)據(jù)管理社交網(wǎng)絡(luò)、推薦系統(tǒng)機(jī)器學(xué)習(xí)、智能分析數(shù)據(jù)科學(xué)、大數(shù)據(jù)技術(shù)

2.投稿要求

1)論文應(yīng)是未發(fā)表的研究成果，應(yīng)包括中英文題目、中英文摘要、關(guān)鍵詞、正文和參考文獻(xiàn).由于論文采用匿名評(píng)審，故論文中不能包含任何作者相關(guān)信息(如姓名、單位、電子郵件、通信地址、資助項(xiàng)目等).

2)論文中英文均可，用Word排版，論文篇幅一般不超過A4幅面8頁.其格式需參考《計(jì)算機(jī)科學(xué)與探索》的投稿要求，可見《計(jì)算機(jī)科學(xué)與探索》網(wǎng)站的論文寫作模板(http://fcst.ceaj.org/CN/column/column110.shtml).

3)會(huì)議論文均采用網(wǎng)上提交方式，不支持電子郵件提交論文的方式.

4)投稿網(wǎng)址：https://easychair.org/conferences/?conf=ndbc2018

3.系統(tǒng)演示

本次大會(huì)設(shè)立系統(tǒng)演示程序(Demonstration Program)，歡迎大家踴躍投稿.詳細(xì)信息請(qǐng)見系統(tǒng)演示征文通知.

4.論文出版

會(huì)議錄用論文擬推薦到《計(jì)算機(jī)學(xué)報(bào)》(正刊)、《軟件學(xué)報(bào)》(正刊)、《清華大學(xué)學(xué)報(bào)》(正刊)、《計(jì)算機(jī)科學(xué)與探索》(正刊)、《計(jì)算機(jī)工程與應(yīng)用》(正刊)、《計(jì)算機(jī)科學(xué)》(正刊)、以及英文期刊《Data Science and Engineering》等出版.

5.重要日期

論文提交截止時(shí)間：2018年05月14日

論文錄用通知時(shí)間：2018年06月23日

排版稿件截止時(shí)間：2018年07月01日

6.聯(lián)系方式

會(huì)議網(wǎng)站：http://www.dlmu.edu.cn/ndbc2018

聯(lián)系人：周 新、李翠平

郵件：zhouxin314159@163.com、ruc_li2018@163.com

電話：+86-15840899025、+86-13693153349