基于學習自動機的異構有向傳感器節點調度算法

李 ,

(1.重慶工商大學 重慶市檢測控制集成系統工程實驗室,重慶 400067;2.電子科技大學 自動化工程學院,成都 611731)

0 概述

隨著微機電技術的發展,由視頻傳感器、紅外傳感器和超聲波傳感器等構成的有向傳感器網絡在實踐中得到了廣泛應用[1],且受到越來越多研究者的重視。如何在保證監測質量的前提下減少網絡能耗、延長網絡工作時間,成為有向傳感器網絡領域的重點研究方向之一。節點調度技術通過對傳感器節點的資源進行時間和空間的優化,實現了網絡工作時間的延長[2-4]。文獻[5]提出一種鄰居節點調度協議,引入局部覆蓋集的概念,通過局部覆蓋集來判斷當前節點是否為冗余節點,并在考慮節點剩余能量時決定其是否可以轉為休眠狀態。該調度協議允許一個節點加入多個覆蓋集,覆蓋集輪流工作使網絡生存期達到最大化。文獻[6]研究最大有向區域覆蓋問題,通過調整有向傳感器的工作方向使覆蓋的區域面積達到最大值,但其在調整過程中未考慮能量消耗。文獻[7]提出2種啟發式有向傳感器網絡節點調度算法,以解決監測目標在有優先級情況下的網絡覆蓋問題并延長網絡壽命,但該算法需要大量的消息交換,算法復雜度較高。文獻[8]提出一種基于遺傳算法的節點調度策略,用其來延長網絡的生命周期。文獻[9]將網絡中的節點劃分為互不相交的子集合,每個子集合都能將數據傳送到sink節點,每次只有一個子集合處于工作狀態,其他子集合處于休眠狀態,通過這種方式來延長網絡的生命周期。文獻[10]提出一種基于遺傳算法的有向傳感器節點調度方法,可以延長網絡壽命。文獻[11]提出一種基于網格劃分的有向傳感器最大覆蓋調度算法。

上述方法都是針對感知角度、感知半徑和攜帶相同能量的同構有向傳感器網絡的,均未考慮節點異構性特別是能量異構性對節點調度算法的影響,且算法計算復雜度均較高,未考慮傳感器節點資源的局限性。此外,由同構節點構成的網絡擴展性較差,不利于在出現節點故障后對網絡進行維護[12]。盡管文獻[13]針對無線傳感器網絡服務質量會隨著網絡運行而下降這一現象,提出了一種基于目標覆蓋的異構有向傳感器網絡分布式節點調度策略,但該策略需要頻繁地進行消息交換,通信消耗較大,影響了節點的壽命。

針對上述算法存在的不足,本文提出一種基于學習自動機的異構有向傳感器網絡節點調度算法。利用學習自動機的自適應能力將網絡節點劃分成互相獨立的子集合,使每個子集合都能保證網絡完全覆蓋,并通過不同子集合休眠、工作狀態的切換來實現網絡生命周期的延長。

1 異構節點調度算法的原理與實現

1.1 系統模型與假設

在二維平面內隨機分布著M個需要監測的目標點Ti(i=1,2,…,M),目標點位置信息已知。在二維平面內部署N個有向傳感器節點Si(i=1,2,…,N),其感知半徑為RSi(i=1,2,…,N),通信半徑為RCi(i=1,2,…,N),感知方向Di的數量為|Di|(i=1,2,…,N),感知角度為Ai(i=1,2,…,N),攜帶能量為Ei(i=1,2,…,N),所在位置Pi(i=1,2,…,N)已知或者可以通過其他定位技術獲得[14]。這些有向傳感器節點的系統參數,即感知半徑、通信半徑、感知方向的數量、感知角度和所攜帶能量均不相同。假定有向傳感器節點在同一時刻只能在一個感知方向上處于工作狀態,即同一時刻某個節點只有一個感知方向處于工作狀態,其他感知方向均處于休眠狀態。

定義1(目標點Ti被有向傳感器節點Si覆蓋) 目標點Ti與有向傳感器節點Si所在位置Pi的距離小于等于Si的感知半徑,且Si與目標點Ti之間的連線與Si感知方向的夾角小于Si感知角度的一半。

本文要解決的問題是如何對有向傳感器節點進行集合劃分,使得劃分的集合數最多,同時保證集合中的傳感器節點能夠滿足目標覆蓋的要求,進而實現網絡生命周期的最大化。該問題形式化描述為:

(2)

(3)

(4)

其中,tk表示每個集合的工作時間,K表示劃分的覆蓋集合的最大數量,Di,j表示節點Si的第j個感知方向,Ck表示第k個滿足條件的覆蓋集合,Li表示節點Si的壽命,C_Tm表示能覆蓋監測目標Tm的感知方向的集合,m=1,2,…,M。式(2)保證節點的工作時間不會超過其壽命;式(3)保證在滿足條件的集合中最多只有一個感知方向處于工作狀態;式(4)保證每個監測目標都能被覆蓋集合中的至少一個感知方向所監測到。

1.2 學習自動機算法的原理與實現

1.2.1 學習自動機基本原理

學習自動機在學習過程中基于以下規則更新其動作概率[17]:

1)對于有利的響應,根據式(5)來更新動作概率。

(5)

2)對于不利的響應,根據式(6)來更新動作概率。

(6)

其中,a、b分別表示獎勵參數與懲罰參數。

學習自動機的結構可以分為固定結構和可變結構,可變結構學習自動機的行為數量可以發生變化。學習自動機的控制規則簡單易用,無需耗費計算資源,適用于傳感器這種內存和計算資源受限的硬件節點。此外,學習自動機具有收斂性能好、優化能力強的特點,能迅速通過與環境的交互在反饋學習中找到優化的解。因此,本文采用可變結構的學習自動機來進行問題求解。

1.2.2 基于學習自動機的異構節點調度算法

現有的節點調度算法多數針對參數相同的節點,而本文提出的基于學習自動機的異構節點調度算法借助學習自動機與環境的交互和候選動作集的獎懲,能夠實現網絡覆蓋率和網絡壽命的優化。基于學習自動機的異構節點調度算法分為3個步驟:算法初始化,求解滿足覆蓋要求的異構節點集合,算法參數更新。各步驟具體內容如下:

1)算法初始化主要對學習自動機的一些參數進行初始化。根據求解問題的特點,定義候選動作集為所有有向傳感器節點的感知方向,即α={Di,j},i=1,2,…,N;j=1,2,…,|Di|。相應地,取候選動作集的概率為該感知方向覆蓋的監測目標數與所有需要監測的目標數的比值,即:

u=1,2,…,t;i=1,2,…,N;j=1,2,…,|Di|

其中,|Ti,j|表示第i個節點第j個感知方向覆蓋的監測目標數。

設置2個全局變量Guncovered和Gloop分別用于存儲未覆蓋的監測目標數和最大迭代次數,Guncovered的初值設為所有的監測目標數。

2)求解滿足覆蓋要求的異構節點集合時,算法以迭代的方式運行,用變量k記錄當前的迭代次數,并賦其初值為1。每次迭代能得到一個滿足覆蓋要求的節點感知方向集合,若新得到的感知方向集合的基(即集合中元素的個數)小于已得到的、最好的滿足覆蓋要求的集合中的基,則新集合中感知方向對應的候選動作概率將得到獎勵(變大),并按照式(5)進行更新,否則,將按照式(6)進行更新。然后,將已得到的、最好的滿足覆蓋要求的集合更新為新得到的集合,并更新節點的剩余能量,若該節點能量已耗盡,則將該節點涉及的所有感知方向從候選動作集中刪除,相應地,將其對應的概率設為0。最后,將當前迭代次數k加1,若k的值已大于最大迭代次數Gloop,則算法結束,否則,進入下一次迭代。

每次迭代過程的具體步驟為:

步驟1學習自動機隨機選擇一個節點的一個感知方向。

步驟2根據該感知方向信息計算得到覆蓋的目標信息。

步驟3更新Guncovered變量,將集合中已覆蓋的目標信息刪去。

步驟4若該變量已變成空集,說明所有的目標都已覆蓋,則該次迭代結束,重新將變量Guncovered賦值為監測目標的集合,否則,繼續步驟1。

有向傳感器節點某個特定時刻只能工作在一個感知方向,因此,為提高算法效率,在上述步驟1中,若該節點的某個感知方向已被選擇,則將候選動作集中該節點的其他感知方向刪去,并將其對應的動作概率設為0。同時,為避免已經選擇的感知方向被重復選擇,將已被選中的感知方向從候選動作集中刪去,并將其對應的動作概率設為0。此外,在節點能量消耗方面,用tw表示每個集合的工作時間,本文假定節點消耗的能量與節點工作時間成正比,即Esi=ε·tw,ε為比例系數,本文設為1。

從上述算法步驟可以看出,本文基于自動學習機的節點調度算法通過自動學習機與環境的交互和結果反饋,借助對動作概率更新并經過一定次數的強化學習后,能夠得到問題的解。相比現有的節點調度算法,該算法運算規則簡單,適用于傳感器這類計算資源受限的網絡。

1.3 運用貪婪算法對節點調度問題進行求解

運用貪婪算法對有向異構節點調度問題進行求解,主要分為3個步驟:

步驟1參數初始化,對節點的能量、剩余能量和網絡工作時間進行初始化。

步驟2求解滿足條件的節點集合。在每次迭代中,選取節點感知方向時綜合考慮節點對監測目標的覆蓋情況和節點自身的能量狀況,即按照式(7)的貪婪策略進行選擇。

其中,B1、B2表示權重系數,取值范圍均為(0,1)且B1+B2=1,Nmc(di,j)表示在當前的迭代次數還未被覆蓋的目標中,感知方向di,j所能覆蓋的目標數,Nuncovered表示還未被覆蓋的目標數,Ere(Si)表示節點Si的剩余能量,E(Si)表示節點Si的初始能量。

步驟3節點和監測目標狀態更新。每次選取符合條件的感知方向后,將該節點的其他感知方向從候選集合中刪去。每次迭代結束后,更新節點的能量狀態,將能量為0的節點的所有感知方向從候選集合中刪去。

貪婪算法的具體步驟如下:

步驟1判斷當前可用的感知方向集合是否能完全覆蓋目標,若能完全覆蓋,則執行步驟2,否則,執行步驟7。

步驟2設置變量tw和集合E、T、F并初始化tw=常數,E=T,F=空。其中,tw為每個集合的工作時間,T表示全體監測目標集合,E和F是用來記錄算法中間結果的臨時變量集合,分別存儲監測目標和滿足條件的感知方向。

步驟3判斷集合E是否為空,若為空,則執行步驟6,否則,執行步驟4。

步驟4對當前的感知方向集合按照式(7)計算每個感知方向的cost值。

步驟5選取最大cost值所對應的感知方向,將該感知方向加入集合F中,同時將該感知方向對應的覆蓋目標從集合E中刪去,并將該感知方向所對應節點的其他感知方向從當前感知方向集合中刪去,然后返回步驟3。

步驟6將{F,tw}加入集合Result_set中,更新F集合中感知方向所對應的節點的剩余能量,若剩余能量為0,則將該感知方向對應的節點的所有感知方向從當前可用的感知方向集合中刪去,然后返回步驟1。

步驟7返回結果Result_set。

2 仿真結果與性能分析

為分析本文算法的性能,在Windows 7 64位和MATLAB 2013平臺上進行仿真實驗。其中,每個實驗數據均是30次實驗結果的平均值。

2.1 仿真參數

假定40 m×40 m區域內均勻分布120個監測目標,隨機部署2種類型的有向傳感器節點,為保證一定的節點冗余度,節點數目設為210(2種類型的節點數目相同)。節點部分參數設置如表1所示。

表1 有向傳感器節點參數設置

其他參數設置為:式(7)中B1、B2、μ的取值分別為0.50、0.50、0.01。網絡壽命定義為傳感器節點能完全覆蓋監測目標的時間。

2.2 結果分析

2.2.1 網絡壽命與集合工作時間tw的關系

為驗證網絡壽命與集合工作時間之間的關系,將部署節點數分別設置為50和75,將tw分別設置為0.25 s、0.50 s、0.75 s、1.00 s,圖1所示為網絡壽命隨集合工作時間的變化曲線。

圖1 網絡壽命與集合工作時間的關系

從圖1中可以看出,每個覆蓋集合工作時間不同,網絡的壽命也不同。原因是每個節點的能量消耗在不同的覆蓋集合中,每個集合工作時間不同,消耗的能量也不同,其中較短的集合工作時間導致其能夠構建較多的滿足條件的覆蓋集合,從而使網絡的壽命得以延長。此外,在相同的覆蓋集合工作時間條件下,節點數目較多的傳感器網絡壽命較長。

2.2.2 算法運行時間與集合工作時間tw的關系

為驗證算法運行時間與集合工作時間之間的關系,將部署節點數分別設置為50和75,將tw分別設置為0.25 s、0.50 s、0.75 s、1.00 s,圖2所示為算法運行時間隨集合工作時間的變化曲線。

圖2 算法運行時間與集合工作時間的關系

從圖2中可以看出,隨著集合工作時間的增加,算法運行時間減少。原因是集合工作時間增加,即節點在該覆蓋集合中消耗的能量增加,導致其構建的符合要求的覆蓋集合減少,從而使得算法很快收斂。在相同的集合工作時間條件下,節點數目較多的網絡需要較多的時間去構建符合條件的覆蓋集合。

2.2.3 網絡壽命與節點個數的關系

為比較本文基于自動學習機的節點調度算法和貪婪算法的性能,將節點數目分別設為50、75、90、100,每個覆蓋集合的工作時間設為0.25 s,即tw=0.25 s,監測目標數設為15,然后分析網絡壽命與節點個數之間的關系。圖3所示為網絡壽命隨節點數目的變化曲線。

圖3 網絡壽命與節點個數的關系

從圖3中可以看出,節點個數增加時2種算法的網絡壽命均延長。但在部署節點數相同的條件下,本文算法的網絡壽命明顯長于貪婪算法,該結果驗證了本文算法的有效性。

2.2.4 網絡壽命與監測目標個數的關系

為分析監測目標個數對算法網絡壽命的影響,將監測目標個數分別設為10、15、20、25,每個覆蓋集合的工作時間設為0.25 s,部署節點數設為100,然后分析網絡壽命與監測目標個數的關系。圖4所示為網絡壽命隨監測目標個數的變化曲線。

圖4 網絡壽命與監測目標個數的關系

從圖4中可以看出,監測目標個數增加時2種算法的網絡壽命均減少。但在監測目標個數相同的情況下,本文算法網絡壽命明顯長于貪婪算法。

3 結束語

本文提出一種基于學習自動機和貪婪算法的異構有向節點調度算法。學習自動機算法通過與環境的交互來更新節點感知方向選取概率,以達到覆蓋集合的優化;貪婪算法根據節點覆蓋目標的情況和節點能量情況構建符合要求的感知方向集合,從而達到延長網絡壽命的目的。仿真結果表明,與貪婪算法相比,本文算法能有效延長網絡壽命。下一步將設計基于連通覆蓋的異構有向節點調度算法。