周劍敏，胡海剛，錢云霞

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

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

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

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

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

1 網絡模型

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

(1)

(2)

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

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

(3)

表1總結了網絡模型中所用符號和定義。

表1 符號和定義

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

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

2 廣義學習自動機(GLA)

2.1 學習自動機

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

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

(4)

(5)

2.2 廣義學習自動機

LA算法的優(yōu)點是無需樣本數據的先驗知識，并且具有較強的抗噪聲能力。但是，LA存在學習速度緩慢的問題。與此相比，廣義學習自動機(GLA)是較快的一種，GLA是對傳統(tǒng)LA結構進行修改，使其可以直接使用單個LA實現分類。

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

(6)

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

1) 輸入一個隨機樣本x(k)。

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

3) 在該環(huán)境中生成一個信號β(k)作為GLA的反饋，β(k)的值表示α(k)的正確與否，當β=1時，代表α(k)正確，當β=0時，代表α(k)錯誤。

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

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

(7)

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

i=1,2,…,N

(8)

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

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

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

3.1 主干節(jié)點網絡構建

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

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

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

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

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

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

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

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

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

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

這組全局變量是在初始化步驟開始時建立的，并在網絡內廣播包含Ps、Pthreshold、Tk值的HELLO消息。接收到這個消息后，在每個節(jié)點上啟動初始化過程，并從CG獲取一個信息以便知道節(jié)點的鄰居。這是整個算法的一個關鍵步驟，因為它從網絡的CG開始尋找合適的節(jié)點，最終的目標是滿足部分覆蓋的要求。

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

(9)

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

主干構建階段的主要目標是在網絡區(qū)域A?中尋找冗余傳感器節(jié)點。在每個節(jié)點上運行GLA有助于識別合適的主干。在初始化步驟之后，隨機選擇節(jié)點并添加到Ψ中。

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

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

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

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

(10)

主干構建階段的算法流程如算法1所示。

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

輸入：

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

輸出：

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

初始化：

在網絡中廣播HELLO消息；

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

Ψ=φ；

初始化Tk和Pthreshold；

發(fā)送DISCOVERY消息；

End for

重復執(zhí)行

隨機選擇一個節(jié)點Si并激活；

重復執(zhí)行

whileSi不活動時，則

激活的節(jié)點被追溯以找到具有可用動作的自動機；

End while

Ψ=Ψ∪Si；

Si根據其p(n)選擇一個鄰居節(jié)點Sj；

每個自動機修剪它的動作集以避免循環(huán)；

Sj被激活；

Γ=?！任幢贿x擇的Si的鄰居節(jié)點；

Si=Sj；

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

計算EΨ；

if |Ψ|En，則

Tn=|Ψ|；

En=EΨ；

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

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

else

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

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

end if

當達到停止條件時，結束；

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

執(zhí)行FormPartialCoverage()；

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

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

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

輸入：

CG=(V,E)；Ps

輸出：

Ψ；Γ

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

ifΨ不滿足條件Ps，則

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

Ψ=Ψ∪Sj；

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

else

停用Sj；

end if

end if

end for

4 仿真實驗分析

4.1 仿真設置

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

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

表2 仿真參數及覆蓋要求

4.2 結果分析

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

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

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

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

圖3顯示當考慮到不同的平均區(qū)域覆蓋度(D?=4、D?=3和D?=2)時，覆蓋要求Ps的變化對工作節(jié)點比例φ的影響?？梢钥吹?，在同樣的平均區(qū)域覆蓋度D?下，φ隨著Ps的增加而呈現上升趨勢。這是因為覆蓋面積要求的增加，需要激活更多的節(jié)點來滿足嚴格的覆蓋約束。

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

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

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

以上仿真結果顯示了本文方法可以更好地利用資源。當有更多的傳感器可用時(例如D?=2)，能獲得比其他算法更好的性能，這是因為其使用最小可能數量的節(jié)點作為主干節(jié)點，以達到部分覆蓋要求并保證它們之間的連通性。

4.2.2平均區(qū)域覆蓋度和覆蓋要求與網絡壽命的關系

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

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

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

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

5 結束語

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