周劍敏，胡海剛，錢云霞

(1.浙江國際海運(yùn)職業(yè)技術(shù)學(xué)院， 浙江 舟山 316021; 2.寧波大學(xué)， 浙江 寧波 315800)

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)被廣泛用于監(jiān)測、醫(yī)療和環(huán)境監(jiān)測等多個(gè)領(lǐng)域[1]。由于WSN節(jié)點(diǎn)自帶的能量比較少，為此系統(tǒng)生存時(shí)間[2-3]是WSN應(yīng)用中的關(guān)鍵問題。其中，尋找節(jié)點(diǎn)的最優(yōu)位置、降低能量消耗是科研人員研究的主要方向。

區(qū)域覆蓋問題可以分為全覆蓋和部分覆蓋(也稱為百分比覆蓋)[4-8]。全覆蓋需要持續(xù)監(jiān)測整個(gè)感興趣區(qū)域，部分覆蓋不需要全覆蓋整個(gè)監(jiān)測區(qū)域，只要保證網(wǎng)絡(luò)的覆蓋比例達(dá)到一定的值即可。部分覆蓋中通過節(jié)點(diǎn)休眠機(jī)制，在保證服務(wù)質(zhì)量的同時(shí)大量減少工作節(jié)點(diǎn)個(gè)數(shù)，從而延長網(wǎng)絡(luò)的生命周期。

為了提高部分覆蓋時(shí)WSN的網(wǎng)絡(luò)壽命，學(xué)者提出了多種覆蓋方法。例如，文獻(xiàn)[9]中設(shè)計(jì)了一種分散覆蓋方式，可以在監(jiān)控網(wǎng)絡(luò)區(qū)域的同時(shí)保持網(wǎng)絡(luò)連通性，保證一定比例的覆蓋。文獻(xiàn)[10]中分析了期望的覆蓋率和工作傳感器的最小數(shù)量之間的關(guān)系，設(shè)計(jì)了能量感知部分覆蓋協(xié)議，根據(jù)節(jié)點(diǎn)的剩余能量選擇最小工作傳感器數(shù)量。文獻(xiàn)[11]提出一種完全分布式的方法，每個(gè)傳感器節(jié)點(diǎn)不需要任何地理信息來尋找冗余節(jié)點(diǎn)，并把它們置于睡眠狀態(tài)。但是，這些方法在時(shí)間復(fù)雜性方面的效果不是很理想[12]。連通支配集(CDS)是一種連通圖，使得每個(gè)頂點(diǎn)要么在子集中，要么與子集中的頂點(diǎn)相鄰。文獻(xiàn)[13]提出在網(wǎng)絡(luò)中創(chuàng)建CDS的虛擬主干。文獻(xiàn)[14]為了解決WSN中部分覆蓋問題，基于CDS構(gòu)建網(wǎng)絡(luò)，并結(jié)合了一種貪婪方法pPCA，構(gòu)建一種以分布式方式運(yùn)行的CpPCA-CDS算法。這種解決方案的主要缺點(diǎn)是依賴深度首次搜索(DFS)，嚴(yán)重影響時(shí)間復(fù)雜度(本文將CpPCA-CDS簡稱為DFS)。文獻(xiàn)[15]提出了一種分布式自適應(yīng)睡眠調(diào)度算法，每個(gè)節(jié)點(diǎn)使用剩余能量水平和匯聚節(jié)點(diǎn)的反饋來調(diào)度其鄰居節(jié)點(diǎn)的活動(dòng)。

本文提出了一種WSN中基于廣義學(xué)習(xí)自動(dòng)機(jī)(generalized learning automata，GLA)[5]的部分覆蓋方法。其主要?jiǎng)?chuàng)新點(diǎn)在于：① 通過GLA來選擇一組節(jié)點(diǎn)，構(gòu)建能夠滿足預(yù)設(shè)約束的主干節(jié)點(diǎn)網(wǎng)絡(luò)；② 根據(jù)網(wǎng)絡(luò)覆蓋要求和節(jié)點(diǎn)能耗，動(dòng)態(tài)評(píng)估各休眠節(jié)點(diǎn)的覆蓋能力，選擇合適節(jié)點(diǎn)進(jìn)行激活，實(shí)現(xiàn)以最少數(shù)量節(jié)點(diǎn)滿足要求。仿真結(jié)果表明：提出的方法在激活的節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)壽命方面有更好的性能。

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

WSN可以通過一個(gè)無向連通圖來建模，即CG=(V,E)。其中V={S0,S1，…,SN}包含所有隨機(jī)部署的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的感測和通信范圍分別定義為半徑為Rs和Rc的圓。E表示節(jié)點(diǎn)之間的通信鏈路的集合。對(duì)于任意一對(duì)節(jié)點(diǎn)u和v，當(dāng)且僅當(dāng)u和v在彼此的通信范圍內(nèi)時(shí)，邊(u,v)∈E。更確切地說，節(jié)點(diǎn)Si的感測區(qū)域γi定義為以Si為圓心、Rs為半徑的圓。如果點(diǎn)(x,y)位于節(jié)點(diǎn)的感測區(qū)域，則點(diǎn)(x,y)被Si覆蓋。那么，節(jié)點(diǎn)Si的覆蓋函數(shù)Ci(x,y)可定義為：

(1)

(2)

其中j∈cells是區(qū)域劃分的單元格之一。

那么，約束條件可以寫成：

(3)

表1總結(jié)了網(wǎng)絡(luò)模型中所用符號(hào)和定義。

表1 符號(hào)和定義

部分覆蓋中根據(jù)檢測區(qū)域的重要性，設(shè)置不同的覆蓋范圍，從而使WSN的使用壽命更長。圖1顯示了部分覆蓋問題的示例,該感興趣的區(qū)域分為9個(gè)單元，需要不同的覆蓋水平。例如，第1個(gè)單元有一半的關(guān)鍵領(lǐng)域，覆蓋要求為50%。

圖1 具有不同覆蓋率的WSN部分覆蓋

2 廣義學(xué)習(xí)自動(dòng)機(jī)(GLA)

2.1 學(xué)習(xí)自動(dòng)機(jī)

學(xué)習(xí)自動(dòng)機(jī)(learning automata，LA)旨在從一組允許的行動(dòng)中選擇最佳行動(dòng)，它使用由環(huán)境生成的答復(fù)來更新其動(dòng)作概率向量。環(huán)境由一個(gè)三元組(α,β,c)表示，其中：α表示有限輸入集合(動(dòng)作)；β表示輸出集合(強(qiáng)化信號(hào))；c表示一組懲罰概率，每個(gè)元素ci對(duì)應(yīng)于一個(gè)輸入行為αi。變量結(jié)構(gòu)學(xué)習(xí)自動(dòng)機(jī)由(β,α,T)表示，其中：β表示輸入集合；α表示動(dòng)作集合；T表示學(xué)習(xí)算法。它實(shí)際上是一個(gè)概率向量，目的是修改以上所述動(dòng)作的遞推關(guān)系。

令αi(k)∈α，它表示經(jīng)過LA后被選中的動(dòng)作，p(k)表示在第k個(gè)循環(huán)處的動(dòng)作概率向量。令a和b分別表示獎(jiǎng)勵(lì)和懲罰參數(shù)，其中獎(jiǎng)勵(lì)參數(shù)能判定動(dòng)作概率值的增加數(shù)量，懲罰參數(shù)能判定動(dòng)作概率值的減少數(shù)量。r是LA的動(dòng)作次數(shù)。根據(jù)動(dòng)作概率向量p(k)，自動(dòng)機(jī)隨機(jī)選擇一個(gè)動(dòng)作αi(k)，并在環(huán)境中執(zhí)行。式(4)表示動(dòng)作概率向量p(k)在αi(k)的獎(jiǎng)勵(lì)更新，式(5)表示動(dòng)作概率向量p(k)在αi(k)的懲罰更新。當(dāng)a=b時(shí)，式(4)和式(5)可以看作線性獎(jiǎng)勵(lì)-懲罰LR-P機(jī)制；當(dāng)a≥b時(shí)，式(4)和式(5)可以看作線性獎(jiǎng)勵(lì)-ε懲罰LR-εP機(jī)制；當(dāng)b=0時(shí)，式(4)和式(5)可以看作線性獎(jiǎng)勵(lì)-無為LR-I機(jī)制，此時(shí)，動(dòng)作概率矢量不會(huì)因選定操作受到的懲罰而改變。

(4)

(5)

2.2 廣義學(xué)習(xí)自動(dòng)機(jī)

LA算法的優(yōu)點(diǎn)是無需樣本數(shù)據(jù)的先驗(yàn)知識(shí)，并且具有較強(qiáng)的抗噪聲能力。但是，LA存在學(xué)習(xí)速度緩慢的問題。與此相比，廣義學(xué)習(xí)自動(dòng)機(jī)(GLA)是較快的一種，GLA是對(duì)傳統(tǒng)LA結(jié)構(gòu)進(jìn)行修改，使其可以直接使用單個(gè)LA實(shí)現(xiàn)分類。

GLA利用(X,Y,R,u,g,T)等變量來描述，其中X表示輸入集合，Y={y1,y2,…,yr}表示不同的類別，R表示強(qiáng)化信號(hào)，它的值有兩種：0或1；u表示GLA的狀態(tài)向量，g表示概率函數(shù)，T表示學(xué)習(xí)計(jì)劃，其作用是更新u。GLA中的概率函數(shù)g和狀態(tài)向量u將輸入集合X變?yōu)閯?dòng)作Y的概率分布，如式(6)所示。

(6)

在GLA中，u(k)和x(k)的值決定了Y的概率分布。當(dāng)系統(tǒng)給定一個(gè)概率函數(shù)g時(shí)，GLA的目標(biāo)是要得到一個(gè)合理的u值，使得在所有樣本向量通過概率函數(shù)g后所生成的動(dòng)作概率分布中，較高的概率對(duì)應(yīng)正確的動(dòng)作。GLA中，對(duì)于某一時(shí)刻k，學(xué)習(xí)步驟如下。

1) 輸入一個(gè)隨機(jī)樣本x(k)。

2) 根據(jù)由x(k)、u(k)和g生成的動(dòng)作概率分布，選出一個(gè)動(dòng)作α(k)∈Y作為環(huán)境的輸出。

3) 在該環(huán)境中生成一個(gè)信號(hào)β(k)作為GLA的反饋，β(k)的值表示α(k)的正確與否，當(dāng)β=1時(shí)，代表α(k)正確，當(dāng)β=0時(shí)，代表α(k)錯(cuò)誤。

4) GLA根據(jù)x(k)、u(k)、β(k)、α(k)以及T的值更新u(k)，得到u(k+1)。

令樣本向量x?RN，當(dāng)r=2時(shí)，u是一個(gè)N維向量，這種情況下，概率函數(shù)g用式(7)所示函數(shù)表示。

(7)

GLA學(xué)習(xí)得到最優(yōu)的狀態(tài)向量u，并根據(jù)它獲得β的期望值f(u)=E[β|u]的最大值，T的選擇如式(8)所示。

i=1,2,…,N

(8)

式(8)中，ui代表u的第i個(gè)維度，其初始值為u(0)=[0,0,…,0]T，λ代表步長。GLA沿著f(u)的梯度方向更新u(k)，得到u(k+1)。

3 基于GLA的有限區(qū)域覆蓋方法

所提出方法的主要思想是首先確定一組節(jié)點(diǎn)來構(gòu)建一個(gè)能保證所有節(jié)點(diǎn)之間連接的主干網(wǎng)。如果部分覆蓋不滿足，則激活其他節(jié)點(diǎn)。該方法包括兩個(gè)階段：主干節(jié)點(diǎn)網(wǎng)絡(luò)構(gòu)建階段和節(jié)點(diǎn)調(diào)度覆蓋階段。

3.1 主干節(jié)點(diǎn)網(wǎng)絡(luò)構(gòu)建

該階段的目的是選擇數(shù)量有限的一組節(jié)點(diǎn)作為主干。這個(gè)階段包括一個(gè)迭代過程，目的在于發(fā)現(xiàn)一個(gè)與預(yù)定義的約束匹配的主干節(jié)點(diǎn)集合。當(dāng)選定的主干網(wǎng)滿足約束條件或滿足預(yù)定義的停止條件時(shí)，該階段結(jié)束。

為了以分布的方式執(zhí)行提出的方法，給出以下參數(shù)定義。

1)Ps，即感興趣區(qū)域中覆蓋范圍的期望比例。

2)Pthreshold，Ψ集合中的每個(gè)節(jié)點(diǎn)上GLA算法選擇動(dòng)作的最大概率閾值，作為執(zhí)行主干構(gòu)建階段的第1個(gè)停止條件。

3)Tk，算法的循環(huán)次數(shù)，作為執(zhí)行主干構(gòu)建階段的第2個(gè)停止條件。

4)Γ，Ψ集合中未被選中的鄰居節(jié)點(diǎn)組成的集合。

5)EΨ，Ψ集合中節(jié)點(diǎn)的平均剩余能量。

6)n，算法的周期數(shù)，用來檢查停止條件。

7)Tn，在主干構(gòu)建階段的第n個(gè)周期，所選擇的Ψ集合中節(jié)點(diǎn)數(shù)量的一個(gè)動(dòng)態(tài)閾值，初始值為|V|。

8)En，在主干構(gòu)建階段的第n個(gè)周期中，所選擇的Ψ集合中節(jié)點(diǎn)平均剩余能量的一個(gè)動(dòng)態(tài)閾值，初始值為0。

這組全局變量是在初始化步驟開始時(shí)建立的，并在網(wǎng)絡(luò)內(nèi)廣播包含Ps、Pthreshold、Tk值的HELLO消息。接收到這個(gè)消息后，在每個(gè)節(jié)點(diǎn)上啟動(dòng)初始化過程，并從CG獲取一個(gè)信息以便知道節(jié)點(diǎn)的鄰居。這是整個(gè)算法的一個(gè)關(guān)鍵步驟，因?yàn)樗鼜木W(wǎng)絡(luò)的CG開始尋找合適的節(jié)點(diǎn)，最終的目標(biāo)是滿足部分覆蓋的要求。

對(duì)于每個(gè)節(jié)點(diǎn)，每個(gè)動(dòng)作αi表示將相鄰節(jié)點(diǎn)Si添加到Ψ中。動(dòng)作概率向量p(n)被初始化如下：

(9)

其中，r表示動(dòng)作集計(jì)數(shù)，為初始化步驟中的鄰居節(jié)點(diǎn)數(shù)量。例如，如果節(jié)點(diǎn)Si有5個(gè)相鄰節(jié)點(diǎn)，則該節(jié)點(diǎn)的動(dòng)作概率向量初始設(shè)置為{0.2,0.2,0.2,0.2,0.2}，這意味著節(jié)點(diǎn)Si有5個(gè)等概率的動(dòng)作。

主干構(gòu)建階段的主要目標(biāo)是在網(wǎng)絡(luò)區(qū)域A?中尋找冗余傳感器節(jié)點(diǎn)。在每個(gè)節(jié)點(diǎn)上運(yùn)行GLA有助于識(shí)別合適的主干。在初始化步驟之后，隨機(jī)選擇節(jié)點(diǎn)并添加到Ψ中。

每個(gè)傳感器Si為了形成它的動(dòng)作集，向它的鄰居傳播DISCOVERY消息。一旦接收到消息，每個(gè)節(jié)點(diǎn)就回復(fù)發(fā)送者Si，根據(jù)其從鄰居接收到的消息來形成動(dòng)作集。因此，每個(gè)節(jié)點(diǎn)上GLA的動(dòng)作集大小取決于相應(yīng)節(jié)點(diǎn)的網(wǎng)絡(luò)密度，一個(gè)節(jié)點(diǎn)上的GLA根據(jù)它的行動(dòng)概率向量p(n)來選擇一個(gè)鄰居，并添加到Ψ中，而其他未被選擇的鄰居被添加到另一個(gè)集Γ。然后，被選擇的這個(gè)節(jié)點(diǎn)迭代這個(gè)選擇過程。

這個(gè)過程一直持續(xù)到Ψ∪Γ=V。 注意，在這一步之后，CG中的每個(gè)節(jié)點(diǎn)都屬于Ψ或Γ。在每個(gè)節(jié)點(diǎn)選擇GLA的動(dòng)作之后，它更新其數(shù)據(jù)結(jié)構(gòu)(即全局變量的值)。在這個(gè)階段，如果沒有可用的動(dòng)作，則選擇過程被追溯并從另一個(gè)節(jié)點(diǎn)重新開始，以最終確保主干節(jié)點(diǎn)的成功選擇。而且，在節(jié)點(diǎn)被選擇之后，每個(gè)節(jié)點(diǎn)的GLA通過禁用與被選節(jié)點(diǎn)對(duì)應(yīng)的動(dòng)作來修剪其動(dòng)作集合。這樣就不能再選擇已被選擇的節(jié)點(diǎn)，避免了循環(huán)的產(chǎn)生，也提高了算法的收斂速度。

一旦確定了候選主干節(jié)點(diǎn)集合Ψ，就評(píng)估Ψ的適用性。在每個(gè)周期n，將Ψ中的節(jié)點(diǎn)數(shù)量與閾值Tn進(jìn)行比較。如果|Ψ|

上述過程一直持續(xù)到停止條件滿足為止。下面詳細(xì)描述這個(gè)停止條件。首先，計(jì)算上一個(gè)周期中所選節(jié)點(diǎn)的概率。這個(gè)概率值Ps可被定義為在上一個(gè)周期中每個(gè)節(jié)點(diǎn)的GLA所選動(dòng)作的概率的乘積。它可以計(jì)算如下：

(10)

主干構(gòu)建階段的算法流程如算法1所示。

算法1:基于GLA的區(qū)域覆蓋執(zhí)行過程

輸入：

CG=(V,E)，網(wǎng)絡(luò)連通圖；Ps，期望的部分覆蓋；α，行動(dòng)概率向量更新的獎(jiǎng)勵(lì)參數(shù)；Tn，動(dòng)態(tài)閾值；En，能量閾值。

輸出：

Ψ，選擇的節(jié)點(diǎn)；Γ，未選擇的節(jié)點(diǎn)。

初始化：

在網(wǎng)絡(luò)中廣播HELLO消息；

ForV中的所有節(jié)點(diǎn)，執(zhí)行：

Ψ=φ；

初始化Tk和Pthreshold；

發(fā)送DISCOVERY消息；

End for

重復(fù)執(zhí)行

隨機(jī)選擇一個(gè)節(jié)點(diǎn)Si并激活；

重復(fù)執(zhí)行

whileSi不活動(dòng)時(shí)，則

激活的節(jié)點(diǎn)被追溯以找到具有可用動(dòng)作的自動(dòng)機(jī)；

End while

Ψ=Ψ∪Si；

Si根據(jù)其p(n)選擇一個(gè)鄰居節(jié)點(diǎn)Sj；

每個(gè)自動(dòng)機(jī)修剪它的動(dòng)作集以避免循環(huán)；

Sj被激活；

Γ=Γ∪未被選擇的Si的鄰居節(jié)點(diǎn)；

Si=Sj；

直到|Ψ∪Γ|<|V|；

計(jì)算EΨ；

if |Ψ|En，則

Tn=|Ψ|；

En=EΨ；

βi(n)=0 ?i|Si∈Ψ；

向Ψ中所有被選中的節(jié)點(diǎn)發(fā)送REWARD消息；

else

βi(n)=1 ?i|Si∈Ψ；

向Ψ中所有被選中的節(jié)點(diǎn)發(fā)送PENALTY消息

end if

當(dāng)達(dá)到停止條件時(shí)，結(jié)束；

向Ψ中所有的節(jié)點(diǎn)發(fā)送ACTIVATION消息；

執(zhí)行FormPartialCoverage()；

3.2 節(jié)點(diǎn)激活覆蓋階段

在主干構(gòu)建階段結(jié)束時(shí)，需要檢查獲得的主干網(wǎng)絡(luò)是否滿足部分覆蓋要求。如果不滿足，則調(diào)用FormPartialCoverage()函數(shù)。這個(gè)函數(shù)激活Γ中的休眠節(jié)點(diǎn)來滿足部分覆蓋的要求。具體而言，F(xiàn)ormPartialCoverage()利用覆蓋函數(shù)，并通過激活Γ中的每個(gè)節(jié)點(diǎn)來評(píng)估覆蓋性能，以識(shí)別需要激活哪些節(jié)點(diǎn)，如算法2所示。

算法2:FormPartialCoverage()的執(zhí)行過程

輸入：

CG=(V,E)；Ps

輸出：

Ψ；Γ

ForΓ中的所有節(jié)點(diǎn)Sj，執(zhí)行

ifΨ不滿足條件Ps，則

ifSj的鄰居節(jié)點(diǎn)不能覆蓋此區(qū)域，則

Ψ=Ψ∪Sj；

向Sj發(fā)送ACTIVATION消息；

else

停用Sj；

end if

end if

end for

4 仿真實(shí)驗(yàn)分析

4.1 仿真設(shè)置

文獻(xiàn)[13]和文獻(xiàn)[14]的方法都是利用覆蓋圖模型，通過不同算法來獲得主干網(wǎng)絡(luò)，實(shí)現(xiàn)WSN部分覆蓋要求。其中，文獻(xiàn)[13]提出的基于CDS的算法首先利用CDS算法構(gòu)造CDS主干節(jié)點(diǎn)集，然后在應(yīng)用中根據(jù)需求使用一些非CDS節(jié)點(diǎn)來滿足部分覆蓋。文獻(xiàn)[14]則是利用CpPCA-CDS算法(DFS)來構(gòu)建主干集。這些覆蓋方法與本文方法的主體思想類似。因此，根據(jù)網(wǎng)絡(luò)資源和覆蓋要求，在NS-2仿真平臺(tái)上比較了這3種方法的性能。

仿真中，在WSN內(nèi)隨機(jī)部署節(jié)點(diǎn)的總數(shù)為N，感興趣區(qū)域的總面積A?，每個(gè)節(jié)點(diǎn)的感測范圍為Rs，通信范圍為Rc，覆蓋要求為Ps。假設(shè)所有節(jié)點(diǎn)的感測和通信范圍相同，且每個(gè)節(jié)點(diǎn)的能量相對(duì)消耗為w。表2總結(jié)了仿真中使用的仿真參數(shù)和覆蓋要求。其中，網(wǎng)絡(luò)平均區(qū)域覆蓋度D?表示同時(shí)覆蓋特定區(qū)域的多個(gè)節(jié)點(diǎn)的數(shù)量，覆蓋度越高，數(shù)據(jù)可靠性越強(qiáng)。

表2 仿真參數(shù)及覆蓋要求

4.2 結(jié)果分析

4.2.1平均區(qū)域覆蓋度和覆蓋要求與工作節(jié)點(diǎn)比例的關(guān)系

首先評(píng)估平均區(qū)域覆蓋度D?和覆蓋要求Ps與工作節(jié)點(diǎn)數(shù)量比例φ的關(guān)系。定義3種不同的配置：D?=4、D?=3和D?=2。此外，在3種不同的覆蓋要求水平下測試了3種算法：Ps=0.6、Ps=0.8和Ps=1.0。

圖2顯示了當(dāng)考慮到不同的覆蓋要求(Ps=0.6、Ps=0.8和Ps=1.0)時(shí)，平均區(qū)域覆蓋度D?的變化對(duì)工作節(jié)點(diǎn)比例φ的影響。對(duì)于這3種算法，在同樣的覆蓋要求Ps下，φ隨著D?的增加而上升。這是因?yàn)樵谳^高的覆蓋度下，同一塊區(qū)域需要多個(gè)傳感器同時(shí)覆蓋，為此所需的傳感器數(shù)量較多。另外，當(dāng)D?=4和Ps=1時(shí)，并沒有仿真結(jié)果，這是因?yàn)樵谶@種配置下沒有算法滿足連接要求。

相同條件下，本文方法始終優(yōu)于其他兩種算法，所需的節(jié)點(diǎn)數(shù)量都是最少的，能有效延長網(wǎng)絡(luò)的使用壽命。

圖3顯示當(dāng)考慮到不同的平均區(qū)域覆蓋度(D?=4、D?=3和D?=2)時(shí)，覆蓋要求Ps的變化對(duì)工作節(jié)點(diǎn)比例φ的影響?？梢钥吹剑谕瑯拥钠骄鶇^(qū)域覆蓋度D?下，φ隨著Ps的增加而呈現(xiàn)上升趨勢。這是因?yàn)楦采w面積要求的增加，需要激活更多的節(jié)點(diǎn)來滿足嚴(yán)格的覆蓋約束。

同樣，在各種情況下，本文方法所需的節(jié)點(diǎn)數(shù)量都最少。因?yàn)槠鋵?duì)節(jié)點(diǎn)執(zhí)行了更高效的選擇，并持續(xù)檢查激活節(jié)點(diǎn)的適用性，直到滿足部分覆蓋要求。例如，當(dāng)D?=2，且Ps從0.8增加到1時(shí)，本文方法的性能降低的比例最小，所需工作節(jié)點(diǎn)數(shù)量的比例增長了12%，而CDS和DFS分別增長了約20%和30%。

圖2 不同的覆蓋要求Ps下，平均區(qū)域覆蓋度D?對(duì)工作節(jié)點(diǎn)比例的影響

圖3 不同的平均區(qū)域覆蓋度D?下，覆蓋要求Ps對(duì)工作節(jié)點(diǎn)比例的影響

以上仿真結(jié)果顯示了本文方法可以更好地利用資源。當(dāng)有更多的傳感器可用時(shí)(例如D?=2)，能獲得比其他算法更好的性能，這是因?yàn)槠涫褂米钚】赡軘?shù)量的節(jié)點(diǎn)作為主干節(jié)點(diǎn)，以達(dá)到部分覆蓋要求并保證它們之間的連通性。

4.2.2平均區(qū)域覆蓋度和覆蓋要求與網(wǎng)絡(luò)壽命的關(guān)系

圖4和圖5比較了用不同的平均區(qū)域覆蓋度D?和覆蓋要求Ps時(shí)3種方法的網(wǎng)絡(luò)壽命。由圖4、5可以看出：較大的平均區(qū)域覆蓋度會(huì)使3種方法的網(wǎng)絡(luò)壽命更長。相反，較大的覆蓋要求會(huì)使3種方法的網(wǎng)絡(luò)壽命變短。

本文方法能獲得比CDS和DFS更長的網(wǎng)絡(luò)壽命，在各種情況下的平均值上，平均壽命分別比CDS和DFS提高了16%和37%。因?yàn)楸疚姆椒ㄍㄟ^GLA算法選擇了具有較高覆蓋能力的主干節(jié)點(diǎn)集合，并其在激活空閑節(jié)點(diǎn)時(shí)，選擇了具有最小可能重疊的節(jié)點(diǎn)，因此需要更少的節(jié)點(diǎn)來滿足覆蓋要求。另外，在某些情況下，只需主干節(jié)點(diǎn)就能達(dá)到所需的覆蓋要求，減少了活動(dòng)節(jié)點(diǎn)的數(shù)量，并且保證在隨后的周期中可以調(diào)度更多的空閑節(jié)點(diǎn)。而CDS和DFS算法在構(gòu)建主干網(wǎng)絡(luò)和激活空閑節(jié)點(diǎn)時(shí)，會(huì)存在較多的節(jié)點(diǎn)覆蓋區(qū)域重疊情況，這就增加了節(jié)點(diǎn)數(shù)量，降低了網(wǎng)絡(luò)效率。

圖4 不同的覆蓋要求Ps下，平均區(qū)域覆蓋度D?對(duì)網(wǎng)絡(luò)壽命的影響

圖5 不同的平均區(qū)域覆蓋度D?下，覆蓋要求Ps對(duì)網(wǎng)絡(luò)壽命的影響

5 結(jié)束語

為了解決WSN部分區(qū)域覆蓋的問題，提出了一種基于廣義學(xué)習(xí)自動(dòng)機(jī)的有限區(qū)域覆蓋方法。通過構(gòu)建主干網(wǎng)絡(luò)和自適應(yīng)節(jié)點(diǎn)激活策略，使用最少數(shù)量的節(jié)點(diǎn)，使其能夠覆蓋感興趣區(qū)域的所需部分，并保持活動(dòng)節(jié)點(diǎn)之間的連通性。仿真實(shí)驗(yàn)結(jié)果顯示：該方法在工作節(jié)點(diǎn)比率和網(wǎng)絡(luò)壽命方面顯示出更好的性能。在使覆蓋范圍更加嚴(yán)格的情況下，性能下降速度比其他解決方案更慢。