基于隨機游走的無線傳感器網(wǎng)絡覆蓋洞修復

韓　蕊　張書奎,2　陳朋飛

1(蘇州大學計算機科學與技術學院　江蘇 蘇州 215006)2(南京大學計算機軟件新技術國家重點實驗室　江蘇 南京 210023)

?

基于隨機游走的無線傳感器網(wǎng)絡覆蓋洞修復

韓蕊1張書奎1,2陳朋飛1

1(蘇州大學計算機科學與技術學院江蘇 蘇州 215006)2(南京大學計算機軟件新技術國家重點實驗室江蘇 南京 210023)

近年來，無線傳感器網(wǎng)絡逐漸成為研究的熱點。無線傳感器網(wǎng)絡中由于傳感器節(jié)點能力的耗盡或失效導致原先被覆蓋的區(qū)域變成無節(jié)點覆蓋的區(qū)域，即覆蓋空洞。針對覆蓋空洞問題，提出基于隨機游走的移動節(jié)點修復覆蓋空洞算法。通過添加移動節(jié)點，運用融合了能量消耗和時延的隨機游走方式指引移動節(jié)點尋找覆蓋空洞，并進行填補。仿真實驗的結果證明了此方法的有效性，移動節(jié)點尋找出的覆蓋空洞的路徑上在能量以及時延方面較優(yōu)。

無線傳感器網(wǎng)絡覆蓋洞隨機游走移動節(jié)點修復

0　引　言

在傳感器網(wǎng)絡部署中，受自然環(huán)境或本身因素的影響，在檢測區(qū)域形成部分覆蓋空洞。覆蓋空洞的存在極大地影響著無線傳感器網(wǎng)絡的性能。如何修復覆蓋空洞引起了研究者的關注。

有的研究者提出了一些空洞修復方法，如：多重覆蓋[1]，即通過部署較多的冗余節(jié)點，使網(wǎng)絡達到k覆蓋的狀態(tài)，這樣以減少覆蓋空洞的存在。休眠輪值機制[2]將無線傳感器網(wǎng)絡中的節(jié)點分為活躍節(jié)點和非活躍節(jié)點。活躍節(jié)點周圍出現(xiàn)空洞的時候，通過激活其感知范圍內的非活躍節(jié)點，使得非活躍節(jié)點變?yōu)榛钴S節(jié)點，以修復存在的覆蓋空洞，達到修復空洞的目的。二代節(jié)點[3]是當網(wǎng)絡中存在覆蓋空洞時再次散播節(jié)點以減少覆蓋空洞。“虛擬力”[4]中假設節(jié)點之間存在吸引力以及排斥力，在這兩種力之間尋找平衡點?；趲缀螆D形的性質[5-10]，利用已知拓撲結構幾何規(guī)則。通過相關的幾何性質得出移動節(jié)點所要移動的“最佳”位置，并將節(jié)點移動到此“最佳”位置，以填補覆蓋空洞。目前覆蓋空洞的研究工作更多的關注于在已知覆蓋空洞具體位置的情況下，利用空洞邊緣節(jié)點的相關信息，通過添加節(jié)點或者是移動空洞邊緣冗余節(jié)點至計算所得的最佳位置，以達到修復空洞的目的。本文針對用于填補空洞的節(jié)點對覆蓋空洞的具體位置未知的情況下，提出基于隨機游走的覆蓋空洞修復方法，利用移動節(jié)點按照一定的規(guī)則在網(wǎng)絡中尋找空洞邊緣節(jié)點，并且路徑上的能量消耗較少和時延較小。

1　相關工作

在無線傳感器網(wǎng)絡中，覆蓋洞的存在極大地影響著網(wǎng)絡的性能，如何探測出覆蓋洞以及修復覆蓋空洞成為研究的熱點。

目前，覆蓋洞探測的方法有：利用計算幾何中圖形[11,12]的相關性質進行覆蓋洞的探測，利用數(shù)學中的統(tǒng)計概率來初步判斷出覆蓋洞的存在，利用探測點來監(jiān)測空洞。

文獻[13]中提出分布式無坐標洞檢測的方法，每個節(jié)點保存其鄰居節(jié)點的信息，通過判斷其鄰居節(jié)點是否能夠圍成一個環(huán)而判定該節(jié)點是否是覆蓋洞邊緣節(jié)點，進而判定覆蓋洞的存在，此方法雖然能夠探測出覆蓋洞的存在，但卻不能探測出細碎的洞。文獻[14]中利用靜態(tài)節(jié)點探測局部覆蓋洞，即通過判定是否存在覆蓋洞邊緣交點來判定是否存在覆蓋洞。

文獻[15]中選取覆蓋洞邊緣的3個節(jié)點，將它們的感知區(qū)域抽象成一個以節(jié)點為圓心，感知半徑為半徑的圓。通過圓的相關性質計算出節(jié)點所需移至的最佳位置。

文獻[16]的研究指出無線傳感器網(wǎng)絡中移動實體可使網(wǎng)絡對于故障更靈活，簡化數(shù)據(jù)采集，提高能源利用率，增強連通性，提高網(wǎng)絡的生命周期以及網(wǎng)絡的修復能力，增強網(wǎng)絡的健壯性。如使用移動sink節(jié)點、移動簇頭、移動繼電器以及移動傳感器節(jié)點[17]。隨機游走的改進方法[18-21]，其中研究結果顯示，有偏的隨機游走可以在能耗和延遲方面很好地提高網(wǎng)絡的性能。借鑒于以上的研究，將隨機游走模型應用于無線傳感器網(wǎng)絡的覆蓋洞修復過程中移動節(jié)點對覆蓋洞的尋找。

2　問題描述

所謂覆蓋空洞，即網(wǎng)絡中未被任何節(jié)點覆蓋的區(qū)域。如圖1中所示，圓A、B、C、D、E、F所圍成的中間區(qū)域，即為空洞。在無線傳感器網(wǎng)絡中，我們稱之為覆蓋空洞(簡稱覆蓋洞)。

圖1　空洞示意

定義1一系列鄰接于覆蓋洞的邊緣節(jié)點組成了覆蓋洞的邊界。如圖1所示，此覆蓋空洞的邊界即為{A,B,C,D,E,F,G,H}。

覆蓋空洞會影響無線傳感器網(wǎng)絡的連通性，影響節(jié)點之間的通信，目標區(qū)域的信息不能被有效搜集到，嚴重影響無線傳感器網(wǎng)絡在應用中的性能。因此，修復覆蓋洞具有非常重要的意義。

2.1網(wǎng)絡環(huán)境

將無線傳感器網(wǎng)絡抽象成一個無向加權圖G(E,V,ω)，其中V是節(jié)點的集合，節(jié)點個數(shù)為n。E為邊集，每一條邊賦予一定的權重值，包括能量消耗和時延DL,設能量集為E’={e1,e2,e3,…,en}。

網(wǎng)絡中部署兩類節(jié)點：靜態(tài)節(jié)點和動態(tài)節(jié)點。靜態(tài)節(jié)點利用文獻[13]中的覆蓋洞探測算法，通過判定自身是否是空洞邊緣的節(jié)點，來斷定是否存在覆蓋洞，若該節(jié)點是空洞邊緣節(jié)點，則表示覆蓋洞存在。動態(tài)節(jié)點可在目標區(qū)域中任意移動，其作用是尋找覆蓋洞，若找到了覆蓋洞，則此移動節(jié)點就會依據(jù)相應的填補算法，填補覆蓋洞。

網(wǎng)絡中，每個傳感器節(jié)點都能夠對周圍實行全方向的探測感知。傳感器節(jié)點的覆蓋(感知)范圍是一個以節(jié)點為中心、感知半徑為半徑的圓，圓內的探測能力都是相同的。靜態(tài)節(jié)點和動態(tài)節(jié)點都具備相同的感知半徑和通信半徑，節(jié)點的通信半徑大于兩倍的感知半徑。目標區(qū)域內的所有傳感器節(jié)點都位于同一個二維平面內，且節(jié)點的位置已知。

初始狀態(tài)下，所有的靜態(tài)節(jié)點隨機地分布在二維空間。靜態(tài)節(jié)點擁有一個鄰居節(jié)點屬性表，包括鄰居節(jié)點的剩余能量，到該鄰居節(jié)點所要消耗的能量，以及路徑上的時延。同時，可將用來修復空洞的移動節(jié)點看成是一個粒子，這個粒子可以移動并可移至任意一個節(jié)點所在位置處。每個傳感器節(jié)點的通信范圍是一個半徑為Rc的圓。在靜態(tài)節(jié)點部署完畢后，將移動節(jié)點隨機部署在目標區(qū)域內。初始階段，移動節(jié)點擁有鄰居節(jié)點的相關信息，包括到每個鄰居節(jié)點的距離，以及到鄰居節(jié)點所需要的能量消耗，以此來選擇一個在尋找覆蓋洞路徑上的初始節(jié)點作為自己的源點。

2.2設計思想

首先，介紹圖上的隨機游走[22]：定義圖G(V,E,ω)是一個有n個頂點，m條邊的有權無向圖，其中V是頂點集，E是邊集，ω:V×V→R是連接權函數(shù)。進一步假設有一個粒子A，初始時在圖G上的頂點V0處，Pij表示粒子A向它的一個鄰居移動的轉移概率，其計算公式[11]如下：

(1)

式中，ωi為鄰居權重之和，即ωi=∑j∈Γ(i)ωij。

如果粒子A以概率Pij從頂點Vi游動到頂點Vj，并不斷重復這一過程，那么被粒子A訪問過的頂點就組成了一個隨機序列Xn,n=0,1,2,…。

定義 2[22]有權無向圖G(V,E,ω)上的隨機游走為一隨機序列：X0,X1,…,Xn,…,其中Xn表示粒子在n時刻的位置。并且，如果粒子在n時刻位于頂點Vi，那么下一時刻位于頂點Vj的概率為Pij。如圖2所示，

圖2　從Vi轉至Vj的概率

在開始隨機游走前，網(wǎng)絡中的覆蓋洞邊緣節(jié)點都已確定。移動節(jié)點擁有一個鄰居節(jié)點的信息表，并根據(jù)搜集到的鄰居節(jié)點信息，判斷其鄰居節(jié)點集中是否存在覆蓋洞邊緣節(jié)點，若僅有一個，則無需執(zhí)行隨機游走的算法；若有多個，則計算轉移概率，選出概率最大的那個節(jié)點。否則，選擇一個距離其較近的鄰居節(jié)點作為尋找覆蓋洞的較優(yōu)路徑上的初始節(jié)點。移動節(jié)點首次移動的目標位置是此初始靜態(tài)節(jié)點位置，初始靜態(tài)節(jié)點根據(jù)相應的導航規(guī)則選擇下一跳節(jié)點，并指導移動節(jié)點移至此下一跳節(jié)點處。同樣下一跳節(jié)點根據(jù)相同的規(guī)則選擇其下一跳節(jié)點，以此類推，直至移動節(jié)點尋找到覆蓋洞。

3　算法設計

覆蓋洞邊緣節(jié)點用于確定覆蓋洞，移動節(jié)點以找到此類節(jié)點為目的。覆蓋洞邊緣節(jié)點的判定可以通過判定其感知圓上是否存在空洞邊緣交點。利用相關文獻中提出的空洞邊緣交點的算法，以下是該算法描述：

步驟1任意選擇一個節(jié)點S。

步驟2創(chuàng)建節(jié)點S的鄰居節(jié)點列表Ls。

步驟3計算出節(jié)點S與鄰居列表中的鄰居節(jié)點Si的交點Pi。

步驟4判斷鄰居列表Ls中除Si之外的節(jié)點能否覆蓋交點Pi。

步驟5如果無其他鄰居節(jié)點覆蓋Pi，則Pi標志為空洞邊緣交點。

步驟6重復此過程直至網(wǎng)絡中所有空洞邊緣交點標出。

網(wǎng)絡中所有空洞邊緣交點全部標出后，每個節(jié)點可以查看其感知圓上是否有空洞邊緣交點。若有，則該節(jié)點為覆蓋洞邊緣節(jié)點；若無，該節(jié)點不是覆蓋洞邊緣節(jié)點。

3.1轉移概率的計算

在覆蓋洞的修復步驟中，其中需要移動節(jié)點根據(jù)一定的規(guī)則在網(wǎng)絡中尋找存在的覆蓋洞。規(guī)則最關鍵的是轉移概率的計算。轉移概率基于隨機游動模型，相關文獻中也給出了圖上的隨機游動模型的定義。

蟻群算法[23]是M.Dorigo提出的一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，采用正反饋機制實現(xiàn)分布式全局優(yōu)化，通過信息素的不斷更新達到最終收斂于最優(yōu)路徑上。文獻[24]中研究者將蟻群算法用于無線傳感器網(wǎng)絡的路由設計，該算法能夠較好地平衡了網(wǎng)絡的能量消耗，能量消耗越少網(wǎng)絡的生命周期越長。本文采用優(yōu)化的蟻群算法[25]的轉移概率思想，將節(jié)點中的能量消耗以及時延作為信息素矩陣。以下是本文的轉移概率：

(2)

式中，E表示能量消耗的倒數(shù)矩陣，η=1/dl,dl為路徑的時延矩陣,α[25]為控制相關的能量信息的可見性的參數(shù)，β[25]是控制路徑上時延重要性的參數(shù)。Eij為節(jié)點i到鄰居節(jié)點j的能量消耗的倒數(shù)，ηij為從節(jié)點i到節(jié)點j的路徑上的時延的倒數(shù)。這樣節(jié)點i會有較大的概率選擇消耗能量少且延遲小的路徑。

每個節(jié)點在選擇下一跳節(jié)點時，計算鄰居節(jié)點集中各個鄰居節(jié)點的轉移概率，從這些鄰居節(jié)點中選出轉移概率最大的節(jié)點。移動節(jié)點將移至靜態(tài)節(jié)點通過計算轉移概率而挑選出的下一跳鄰居節(jié)點的位置作為自己的下一個時刻的位置。針對無線傳感器網(wǎng)絡中涉及到的信息因素，采用基于蟻群優(yōu)化的轉移概率，在本文的轉移概率中添加相應的信息素[23]，用此轉移概率選出較優(yōu)的路徑。因此，本文將路徑上的時延，能量消耗作為蟻群算法中的信息素來形成轉移概率，指導移動節(jié)點尋找出存在的覆蓋洞時，所經(jīng)過的路徑在能量消耗和延時方面是較優(yōu)的。

3.2移動節(jié)點修復位置的計算

移動節(jié)點在找到覆蓋洞邊緣節(jié)點后，將根據(jù)相應的位置計算方法來確定自己填補空洞的最終位置。以下是修復覆蓋洞中確定移動節(jié)點位置的算法：

步驟1選擇覆蓋洞邊緣節(jié)點B，以及它的周圍鄰居節(jié)點A并且A也是空洞節(jié)點。

圖3　空洞邊緣交點

步驟2計算AB的空洞邊緣交點P(P只能被A，B覆蓋，且不能被其他節(jié)點覆蓋)且PA=PB。

如圖3所示，A、B均為覆蓋洞邊緣節(jié)點，P為A和B的空洞邊緣交點。

步驟3找出一點M使得，PM=R，并且AM=BM，則此點就是移動節(jié)點需要移動的位置。

步驟4算法結束。

圖4　M點的位置

如圖4所示。我們找出了空洞邊緣交點P。在幾何圖形中，根據(jù)幾何圖形的性質得知PA的距離和PB的距離相等。在步驟3中，我們同樣根據(jù)幾何圖形的性質，找出填補覆蓋洞的移動節(jié)點最優(yōu)位置M點處，M點距P點的長度為R(感知半徑)，同時，保證M到A點的距離與M到B點的距離相等。根據(jù)幾何圖形性質，兩個圓的圓心連線，取其中垂線上的點，這樣中垂線上的點到兩個圓心的距離相等。反之如果某個點到兩個圓心的距離相等，這該點必定是在兩圓心連線的中垂線上。步驟3中所取的點M到兩圓的交點的距離為R，這表示M的感知圓和A、B的感知圓交于一點，三個圓的重疊區(qū)域最小。因此，M點填補的空洞的面積最大化，并且不會產(chǎn)生細碎的空洞。

3.3算法描述

利用覆蓋空洞邊緣節(jié)點算法找到覆蓋洞節(jié)點，每個靜態(tài)節(jié)點通過覆蓋空洞交點算法查看自己是否是覆蓋洞邊緣節(jié)點。在網(wǎng)絡中，每個節(jié)點都會設置一標志位flag，若該靜態(tài)節(jié)點為覆蓋洞節(jié)點，則將其flag標志設為1，否則設置為0。在此前提下，執(zhí)行基于隨機游走的移動節(jié)點修復覆蓋洞算法，具體的步驟描述如下：

1. 任意選擇一個移動節(jié)點M。

2. 移動節(jié)點M建立其鄰居靜態(tài)節(jié)點集L{L1，L2，…，Ln}。

3. 針對移動節(jié)點M的鄰居靜態(tài)節(jié)點集L{L1，L2，…，Li，…，Ln}中的所有節(jié)點，

1) 如果鄰居集中有flag標志為1的節(jié)點，則說明此鄰居節(jié)點為覆蓋洞邊緣節(jié)點，若有一個覆蓋洞邊緣節(jié)點，則轉至步驟6。若有多個覆蓋洞邊緣節(jié)點，則計算這些覆蓋洞邊緣節(jié)點的轉移概率Pij，即式(2)，并選擇轉移概率最大的節(jié)點，并轉至步驟6。

2) 否則選取M的鄰居靜態(tài)節(jié)點集L{ L1，L2，…，Li，…，Ln}中距離M最小的節(jié)點i。

4. 判定節(jié)點i的鄰居節(jié)點集中是否有flag標志為1的節(jié)點。只有一個覆蓋洞邊緣節(jié)點，則轉至步驟6；若有多個覆蓋洞邊緣節(jié)點，則計算這些覆蓋洞邊緣節(jié)點的轉移概率Pij，即式(2)，并選擇轉移概率最大的節(jié)點，并轉至步驟6。

否則，計算節(jié)點i的鄰居節(jié)點集Ni{Ni1，Ni2，…，Nij，…，Nin}中各個鄰居節(jié)點的轉移概率Pij，即式(2)。

5. 選擇轉移概率Pij最大的節(jié)點j，并且判定節(jié)點j；如果節(jié)點j是覆蓋洞邊緣節(jié)點，則轉到步驟6，否則，轉到步驟4 。

6. 算法結束。

在上述算法中，所有的覆蓋洞邊緣節(jié)點通過之前的覆蓋洞邊緣交點算法找出并作上標記?；谝颜页龅母采w空洞節(jié)點，在步驟3中，節(jié)點在查看鄰居節(jié)點的時候，首先根據(jù)flag標記位，優(yōu)先判定鄰居節(jié)點集中是否存在覆蓋空洞邊緣節(jié)點，若有，則算法結束，這樣充分利用了覆蓋空洞探測階段的信息。否則，移動節(jié)點查看自己的鄰居節(jié)點集中的每個鄰居節(jié)點，選擇距離M最近的靜態(tài)節(jié)點，這樣可以減少移動節(jié)點的移動時間，縮短整個修復過程的時延。在計算鄰居節(jié)點集中每個鄰居節(jié)點的轉移概率時，能量消耗和時延作為參數(shù)。當所選擇的鄰居節(jié)點的能量消耗值越小，則此節(jié)點的轉移概率值越大；當所選擇的鄰居節(jié)點的時延值dl越小時，ηij的值越大，則轉移概率的值越大，選擇該節(jié)點的概率也就越大。因此，在步驟4中節(jié)點會選出轉移概率最大的鄰居節(jié)點。

4　實　驗

本文的關鍵點是在使用移動節(jié)點尋找存在的覆蓋洞并且尋找過程中所產(chǎn)生的路徑是一條在能量消耗和時延上都較優(yōu)的修復路徑。通過仿真實驗，驗證算法的有效性。

4.1實驗的設置

本文使用Java平臺進行仿真實驗。首先，創(chuàng)建一個矩形區(qū)域，并在此區(qū)域中隨機部署n個傳感器節(jié)點，節(jié)點的感知半徑為20m(其傳輸半徑為50m)節(jié)點。

4.2仿真實驗的分析

4.2.1參數(shù)調整

設置的目標區(qū)域為一個300×300 m2的二維正方形區(qū)域，在此區(qū)域內隨機部署100個節(jié)點，部署后的初始狀態(tài)如圖5所示。

圖5　部署初始狀態(tài)

從圖5中可以看出，部署后，目標區(qū)域中存在著不能被節(jié)點覆蓋的地方，即前文所提及的覆蓋空洞。為了便于描述，將這些覆蓋空洞依次標記出。為了區(qū)分不同的節(jié)點，我們對區(qū)域中的部分節(jié)點進行標號。如圖6所示。

圖6　標號后的部署圖

所標區(qū)域為H1，H2，H3，H4，H5，H6的目標區(qū)域均為空洞區(qū)域。在圖6中，標出了部分節(jié)點, 部分覆蓋空洞邊緣節(jié)點有{15，18，40，11，28，64，35,73，20，17，3，12，46，54，22， 30，27，55，19，33，9 }。

在算法中，轉移概率中參數(shù)的設計在導航中也起到了關鍵作用。α作為控制相關的能量信息的可見性的參數(shù)，β作為控制路徑上時延重要性的參數(shù)。如圖7所示，設置α=0.8，β=0.5，新添加移動節(jié)點最靠近節(jié)點10的位置處。

圖7　α=0.8，β=0.5，目的節(jié)點為55

在實驗結果中，移動節(jié)點根據(jù)算法選擇的初始靜態(tài)節(jié)點為10。根據(jù)本文的規(guī)則，移動節(jié)點所尋找出的覆蓋空洞為H3，所形成的路徑為10→19→55，能量消耗總和為47，總時延為19。

實驗結果顯示，本算法具有一定的可行性。根據(jù)初始條件，移動節(jié)點能夠有效地選擇距離自己較近的靜態(tài)節(jié)點作為路徑上的初始節(jié)點，并且在能量消耗以及時延的約束條件下，找到了覆蓋空洞邊緣節(jié)點55，相應的覆蓋空洞是H3。

通過改變參數(shù)α和β，實驗的結果會有所不同。設置α=0.8，β=0.2時，移動節(jié)點尋找出的空洞邊緣節(jié)點20，而此時的路徑為10→34→1→35→20，能量消耗總和為84，總時延為35。兩種α、β的設置情況下，移動節(jié)點都同樣的找出了覆蓋空洞邊緣節(jié)點，但在α=0.8，β=0.2的條件下，移動節(jié)點找到的覆蓋空洞邊緣節(jié)點是20，相應的找出覆蓋空洞H5。從數(shù)據(jù)上可以看出，移動節(jié)點到節(jié)點55所經(jīng)過的中間節(jié)點個數(shù)比到節(jié)點20所經(jīng)過的中間節(jié)點數(shù)少，移動節(jié)點到節(jié)點55所消耗的能量比到節(jié)點20所消耗的能量少以及時延小。即到達覆蓋洞H5的路徑較到達覆蓋洞H3的路徑短(從節(jié)點個數(shù)來看)，且到覆蓋洞H3的路徑上的能量消耗以及時延較優(yōu)。從圖7中我們可以看出，與覆蓋洞H5相比，移動節(jié)點的初始位置距覆蓋洞H3較近，其中節(jié)點55相對于節(jié)點20距移動節(jié)點較近。當α=0.5，β=0.3時，移動節(jié)點的初始位置不變，所選取的起始靜態(tài)節(jié)點為10，尋找到的覆蓋空洞邊緣節(jié)點為44，其為覆蓋空洞H2的邊緣節(jié)點，路徑為10→34→44。能量消耗和為44，延時為16。

所以，合理的調整參數(shù)α、β的值，能夠使得所找出的覆蓋空洞在路徑上的能量消耗以及時延方面較優(yōu)。

4.2.2算法的有效性

本算法，在實際的實驗中，能夠得出和本文預期的結果相一致的實驗結果。隨機部署一個移動節(jié)點，移動節(jié)點在部署后，能夠根據(jù)自身搜集到的信息，選擇距離自身較近的靜態(tài)節(jié)點，并且能夠尋找到覆蓋空洞邊緣節(jié)點。經(jīng)過不斷的實驗調試顯示，α=0.5、β=0.3時，移動節(jié)點所找出的覆蓋空洞節(jié)點的路徑上能量消耗總和以及時延較優(yōu)。因此，在α=0.5、β=0.3條件下，同樣的，部署一個移動節(jié)點，比較此移動節(jié)點通往不同覆蓋洞時，路徑上能量消耗和時延。如表1中所示。

表1　到各個覆蓋空洞能量消耗總和最

選擇移動節(jié)點初始位置處為靠近節(jié)點10處，對比移動節(jié)點去往其他覆蓋空洞的路徑上所需要的能量總和以及時延總和。表1中，所選出的路徑是指到達這個覆蓋洞的所有路徑中能量消耗和時延較優(yōu)的一條路徑。對比移動節(jié)點分別到達空洞H1,H2,H3,H4,H5,H6的路徑，可以看出，根據(jù)文中的導航規(guī)則，移動節(jié)點到達覆蓋洞H2的這一路徑，所消耗的能量相對于到其他覆蓋洞邊緣節(jié)點所消耗的能量較少，時延較小。6條路徑中，通往H2的路徑最優(yōu)，并且去往H2,H4,H5,H6的路徑中，第二個節(jié)點都選擇了34，這和最優(yōu)路徑上第二節(jié)點選擇節(jié)點34所一致。

5　結　語

本文通過在隨機部署的無線傳感器網(wǎng)絡中，提出了基于隨機游走的覆蓋洞修復算法。通過添加的移動節(jié)點，來尋找覆蓋洞邊緣節(jié)點，即覆蓋洞。移動節(jié)點依據(jù)一定的判定規(guī)則尋找覆蓋洞邊緣節(jié)點，而本文的判定規(guī)則是根據(jù)計算出的轉移概率來尋找下一個節(jié)點，轉移概率綜合考慮了能量消耗和時延這兩個因素。在移動節(jié)點找到覆蓋洞邊緣節(jié)點，即找到覆蓋洞后，又找出移動節(jié)點所需移至的最佳位置，更好地修復填補覆蓋洞。如何在動態(tài)的網(wǎng)絡中利用同樣的隨機游走的方式去修復覆蓋洞是今后的研究方向。

[1] 劉明，曹建農，鄭源,等.無線傳感器網(wǎng)絡多重覆蓋問題分析[J]. 軟件學報，2007，18(1)：127-136.

[2] 胥楚貴，鄧曉衡，鄒豪杰.無線傳感器網(wǎng)絡覆蓋空洞修復策略[J].傳感技術學報，2010，23(2)：256-259.

[3] Wang L，Guo Y，Zhan Y. Security topology control method for wireless sensor networks with node-failure tolerance based on self-regeneration [J]．Eurasip Journal of Wireless Communications and Networking，2014，16(10):1-11.

[4] Novella Bartolini，Annalisa Massini，Simone Silvestri. P&P:an asynchronous and distributed protocol for mobile sensor deployment[J].Wireless Network,2012，18(4) : 381-399.

[5] G Wang，G Cao，T La Porta. Movement-assisted Sensor Deployment[C]//IEEE Transactions on Mobile Computing． LOS ALAMITOS，USA:IEEE，June 2006.

[6] 徐鵬飛，陳志剛，鄧曉衡．無線傳感器網(wǎng)絡中的分布式Voronoi覆蓋控制算法 [J]． 通信學報，2010，31(8):16-25.

[7] 韓春延．基于距離的無線傳感器網(wǎng)絡覆蓋洞修復方法[J]．傳感器與微系統(tǒng),2013，32(4):91-94.

[8] Prasan K, Jang Z T. Vector method based coverage hole recovery in wireless sensor[C]//Proceedings of the Communication Systems and Networks (COMSNETS)．Bangalore，2010.

[9] Hwa-Chun Ma， Prasan Kumar Sahoo，Yen-Wen Chen． Computational geometry based distributed coverage hole detection protocol for the wireless sensor network[J]．Journal of Network and Computer Applications， 2011，34:1743-1756.

[10] 楊凱，劉全，張書奎，等．利用移動內點來修復傳感器網(wǎng)絡空洞的算法[J] ．通信學報，2012，33(9)：116-124.

[11] Zhiping Kang，Honglin Yu，Qingyu Xiong．Detection and Recovery of Coverage Holes in Wireless Sensor Networks[J]． Journal of Networks， 2013，8(4)：822-828.

[12] 戴國勇，陳麓屹，周斌彬，等．基于Voronoi圖的無線傳感器網(wǎng)絡覆蓋空洞檢測算法[J]．計算機應用,2015，35(3):620-623.

[13] Li L，Hunter D K，Yang K．Distributed Coordinate-Free Hole Recovery[C]//IEEE Conference: Global Telecommunications， USA: San Francisco，2008:189-194.

[14] 李紅，宋順林．WSN中基于分布式的覆蓋洞修復算法[J]．計算機工程，2012，38(16): 85-88.

[15] Wang Liangmin, Li Fei, Qin Ying．Resilient method for recovering coverage holes of wireless sensor network by using mobile nodes [J] ．Journal on Communications,2011,32(4) :1-8.

[16] Regis W Anne， Elijah Blessing Rajsingh．Mobile entities in wireless sensor networks: theory and performance analysis [J]．Ictact JOurnal on Communication Technology， 2013， 4(1): 661-668.

[17] Nitin Kumar, Dimitrios Gunopulos, Vana Kalogeraki．Sensor network coverage restoration[C]//IEEE International Conference．Marina del Rey,CA,USA:DCOSS 2005,June 30-July 1,2005.

[18] Wang Yaqi, Yang Xiaoyuan． A random walk evolution model of wireless sensor networks and virus spreading[J]．Chinese Physics B, 2013, 22(1) :1-7.

[19] 李強，何衍，蔣靜坪．一種基于隨機游走的聚類算法[J]．電子與信息學報， 2009， 31(3):523-526.

[20] Agata Fronczak，Piotr Fronczak． Biased random walks on complex networks: the role of local navigation rules[J]．Phys Rev E Stat Nonlin Soft Matter Phys，2009，8(2): 75-89.

[21] Annibaldi S V，Hopcraft K I．Random walks with power-law fluctuation in the number of steps[J]．Journal of Physics A: Mathematical and General，2002，35(2): 8635-8645.

[22] Lovász L．Random walks on graphs: A survey[J]．Bolyai Society Mathematical Study，Combinatorics，1993，2(8):1-46.

[23] Bhanu Prakash Lohani， Monika Jena，Sanjay Kumar Dubey．Energy Efficient Routing Using Random Walk and Best Route Selection for Sensor Networks[J]．International Jounal of Scientific & Engineering Research，2013，4(6):81-93.

[24] Liu Guangcong，Wu Huanhuan,Zheng Huijun．Ant colony optimization-based Qos routing in wireless sensor networks[J]．Computer Engineering and Applications，2011，47(20):102-104.

[25] Dorigo M，Maniezzo V，Colomi A．The ant system:optimization by a colony of cooperating agents[C]//IEEE Transactions on Systems Man & Cybemetics，1996，26(1):29-41.

[26] Heinzelman W，Chandrakasan A，Balajrishnan H．Energy Efficient Communication Protocols for wireless Microsensor Networks[C]// Proceedings of the 3rdAnnual Hawaii International Conference on System Science，2000:926-935.

RANDOM WALK-BASED COVERAGE HOLES RECOVERY IN WSN

Han Rui1Zhang Shukui1,2Chen Pengfei1

1(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)2(StateKeyLabforNovelSoftwareTechnology,NanjingUniversity,Nanjing210023,Jiangsu,China)

In recent years, wireless sensor network has gradually become the focus of research. Because of the energy depletion or failure of the sensor node in WSN, original covered area will not be covered by any nodes, which is known as the coverage hole. In view of the coverage hole problem, we proposed the random walk-based algorithm for recovering coverage hole by mobile nodes. Through adding mobile nodes in wireless sensor network, the algorithm uses the random walk means which integrates the energy consumption and delay to guide the mobile node to find coverage holes, and then fill the holes. Through simulation experiment the result proved the effectiveness of the algorithm, the path of coverage hole searched out by mobile node is optimal in terms of energy and delay.

Wireless sensor networkCoverage holeRandom walkMobile nodeRecovery

2015-04-20。國家自然科學基金項目(61070169)。韓蕊，碩士生，主研領域：無線傳感器網(wǎng)絡。張書奎，教授。陳朋飛，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2016.08.031