基于學(xué)習(xí)自動(dòng)機(jī)的異構(gòu)有向傳感器節(jié)點(diǎn)調(diào)度算法

李 ,

(1.重慶工商大學(xué) 重慶市檢測(cè)控制集成系統(tǒng)工程實(shí)驗(yàn)室,重慶 400067;2.電子科技大學(xué) 自動(dòng)化工程學(xué)院,成都 611731)

0 概述

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

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

針對(duì)上述算法存在的不足,本文提出一種基于學(xué)習(xí)自動(dòng)機(jī)的異構(gòu)有向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法。利用學(xué)習(xí)自動(dòng)機(jī)的自適應(yīng)能力將網(wǎng)絡(luò)節(jié)點(diǎn)劃分成互相獨(dú)立的子集合,使每個(gè)子集合都能保證網(wǎng)絡(luò)完全覆蓋,并通過不同子集合休眠、工作狀態(tài)的切換來實(shí)現(xiàn)網(wǎng)絡(luò)生命周期的延長。

1 異構(gòu)節(jié)點(diǎn)調(diào)度算法的原理與實(shí)現(xiàn)

1.1 系統(tǒng)模型與假設(shè)

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

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

本文要解決的問題是如何對(duì)有向傳感器節(jié)點(diǎn)進(jìn)行集合劃分,使得劃分的集合數(shù)最多,同時(shí)保證集合中的傳感器節(jié)點(diǎn)能夠滿足目標(biāo)覆蓋的要求,進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)生命周期的最大化。該問題形式化描述為:

(2)

(3)

(4)

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

1.2 學(xué)習(xí)自動(dòng)機(jī)算法的原理與實(shí)現(xiàn)

1.2.1 學(xué)習(xí)自動(dòng)機(jī)基本原理

學(xué)習(xí)自動(dòng)機(jī)在學(xué)習(xí)過程中基于以下規(guī)則更新其動(dòng)作概率[17]:

1)對(duì)于有利的響應(yīng),根據(jù)式(5)來更新動(dòng)作概率。

(5)

2)對(duì)于不利的響應(yīng),根據(jù)式(6)來更新動(dòng)作概率。

(6)

其中,a、b分別表示獎(jiǎng)勵(lì)參數(shù)與懲罰參數(shù)。

學(xué)習(xí)自動(dòng)機(jī)的結(jié)構(gòu)可以分為固定結(jié)構(gòu)和可變結(jié)構(gòu),可變結(jié)構(gòu)學(xué)習(xí)自動(dòng)機(jī)的行為數(shù)量可以發(fā)生變化。學(xué)習(xí)自動(dòng)機(jī)的控制規(guī)則簡單易用,無需耗費(fèi)計(jì)算資源,適用于傳感器這種內(nèi)存和計(jì)算資源受限的硬件節(jié)點(diǎn)。此外,學(xué)習(xí)自動(dòng)機(jī)具有收斂性能好、優(yōu)化能力強(qiáng)的特點(diǎn),能迅速通過與環(huán)境的交互在反饋學(xué)習(xí)中找到優(yōu)化的解。因此,本文采用可變結(jié)構(gòu)的學(xué)習(xí)自動(dòng)機(jī)來進(jìn)行問題求解。

1.2.2 基于學(xué)習(xí)自動(dòng)機(jī)的異構(gòu)節(jié)點(diǎn)調(diào)度算法

現(xiàn)有的節(jié)點(diǎn)調(diào)度算法多數(shù)針對(duì)參數(shù)相同的節(jié)點(diǎn),而本文提出的基于學(xué)習(xí)自動(dòng)機(jī)的異構(gòu)節(jié)點(diǎn)調(diào)度算法借助學(xué)習(xí)自動(dòng)機(jī)與環(huán)境的交互和候選動(dòng)作集的獎(jiǎng)懲,能夠?qū)崿F(xiàn)網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)壽命的優(yōu)化?；趯W(xué)習(xí)自動(dòng)機(jī)的異構(gòu)節(jié)點(diǎn)調(diào)度算法分為3個(gè)步驟:算法初始化,求解滿足覆蓋要求的異構(gòu)節(jié)點(diǎn)集合,算法參數(shù)更新。各步驟具體內(nèi)容如下:

1)算法初始化主要對(duì)學(xué)習(xí)自動(dòng)機(jī)的一些參數(shù)進(jìn)行初始化。根據(jù)求解問題的特點(diǎn),定義候選動(dòng)作集為所有有向傳感器節(jié)點(diǎn)的感知方向,即α={Di,j},i=1,2,…,N;j=1,2,…,|Di|。相應(yīng)地,取候選動(dòng)作集的概率為該感知方向覆蓋的監(jiān)測(cè)目標(biāo)數(shù)與所有需要監(jiān)測(cè)的目標(biāo)數(shù)的比值,即:

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

其中,|Ti,j|表示第i個(gè)節(jié)點(diǎn)第j個(gè)感知方向覆蓋的監(jiān)測(cè)目標(biāo)數(shù)。

設(shè)置2個(gè)全局變量Guncovered和Gloop分別用于存儲(chǔ)未覆蓋的監(jiān)測(cè)目標(biāo)數(shù)和最大迭代次數(shù),Guncovered的初值設(shè)為所有的監(jiān)測(cè)目標(biāo)數(shù)。

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

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

步驟1學(xué)習(xí)自動(dòng)機(jī)隨機(jī)選擇一個(gè)節(jié)點(diǎn)的一個(gè)感知方向。

步驟2根據(jù)該感知方向信息計(jì)算得到覆蓋的目標(biāo)信息。

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

步驟4若該變量已變成空集,說明所有的目標(biāo)都已覆蓋,則該次迭代結(jié)束,重新將變量Guncovered賦值為監(jiān)測(cè)目標(biāo)的集合,否則,繼續(xù)步驟1。

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

從上述算法步驟可以看出,本文基于自動(dòng)學(xué)習(xí)機(jī)的節(jié)點(diǎn)調(diào)度算法通過自動(dòng)學(xué)習(xí)機(jī)與環(huán)境的交互和結(jié)果反饋,借助對(duì)動(dòng)作概率更新并經(jīng)過一定次數(shù)的強(qiáng)化學(xué)習(xí)后,能夠得到問題的解。相比現(xiàn)有的節(jié)點(diǎn)調(diào)度算法,該算法運(yùn)算規(guī)則簡單,適用于傳感器這類計(jì)算資源受限的網(wǎng)絡(luò)。

1.3 運(yùn)用貪婪算法對(duì)節(jié)點(diǎn)調(diào)度問題進(jìn)行求解

運(yùn)用貪婪算法對(duì)有向異構(gòu)節(jié)點(diǎn)調(diào)度問題進(jìn)行求解,主要分為3個(gè)步驟:

步驟1參數(shù)初始化,對(duì)節(jié)點(diǎn)的能量、剩余能量和網(wǎng)絡(luò)工作時(shí)間進(jìn)行初始化。

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

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

步驟3節(jié)點(diǎn)和監(jiān)測(cè)目標(biāo)狀態(tài)更新。每次選取符合條件的感知方向后,將該節(jié)點(diǎn)的其他感知方向從候選集合中刪去。每次迭代結(jié)束后,更新節(jié)點(diǎn)的能量狀態(tài),將能量為0的節(jié)點(diǎn)的所有感知方向從候選集合中刪去。

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

步驟1判斷當(dāng)前可用的感知方向集合是否能完全覆蓋目標(biāo),若能完全覆蓋,則執(zhí)行步驟2,否則,執(zhí)行步驟7。

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

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

步驟4對(duì)當(dāng)前的感知方向集合按照式(7)計(jì)算每個(gè)感知方向的cost值。

步驟5選取最大cost值所對(duì)應(yīng)的感知方向,將該感知方向加入集合F中,同時(shí)將該感知方向?qū)?yīng)的覆蓋目標(biāo)從集合E中刪去,并將該感知方向所對(duì)應(yīng)節(jié)點(diǎn)的其他感知方向從當(dāng)前感知方向集合中刪去,然后返回步驟3。

步驟6將{F,tw}加入集合Result_set中,更新F集合中感知方向所對(duì)應(yīng)的節(jié)點(diǎn)的剩余能量,若剩余能量為0,則將該感知方向?qū)?yīng)的節(jié)點(diǎn)的所有感知方向從當(dāng)前可用的感知方向集合中刪去,然后返回步驟1。

步驟7返回結(jié)果Result_set。

2 仿真結(jié)果與性能分析

為分析本文算法的性能,在Windows 7 64位和MATLAB 2013平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。其中,每個(gè)實(shí)驗(yàn)數(shù)據(jù)均是30次實(shí)驗(yàn)結(jié)果的平均值。

2.1 仿真參數(shù)

假定40 m×40 m區(qū)域內(nèi)均勻分布120個(gè)監(jiān)測(cè)目標(biāo),隨機(jī)部署2種類型的有向傳感器節(jié)點(diǎn),為保證一定的節(jié)點(diǎn)冗余度,節(jié)點(diǎn)數(shù)目設(shè)為210(2種類型的節(jié)點(diǎn)數(shù)目相同)。節(jié)點(diǎn)部分參數(shù)設(shè)置如表1所示。

表1 有向傳感器節(jié)點(diǎn)參數(shù)設(shè)置

其他參數(shù)設(shè)置為:式(7)中B1、B2、μ的取值分別為0.50、0.50、0.01。網(wǎng)絡(luò)壽命定義為傳感器節(jié)點(diǎn)能完全覆蓋監(jiān)測(cè)目標(biāo)的時(shí)間。

2.2 結(jié)果分析

2.2.1 網(wǎng)絡(luò)壽命與集合工作時(shí)間tw的關(guān)系

為驗(yàn)證網(wǎng)絡(luò)壽命與集合工作時(shí)間之間的關(guān)系,將部署節(jié)點(diǎn)數(shù)分別設(shè)置為50和75,將tw分別設(shè)置為0.25 s、0.50 s、0.75 s、1.00 s,圖1所示為網(wǎng)絡(luò)壽命隨集合工作時(shí)間的變化曲線。

圖1 網(wǎng)絡(luò)壽命與集合工作時(shí)間的關(guān)系

從圖1中可以看出,每個(gè)覆蓋集合工作時(shí)間不同,網(wǎng)絡(luò)的壽命也不同。原因是每個(gè)節(jié)點(diǎn)的能量消耗在不同的覆蓋集合中,每個(gè)集合工作時(shí)間不同,消耗的能量也不同,其中較短的集合工作時(shí)間導(dǎo)致其能夠構(gòu)建較多的滿足條件的覆蓋集合,從而使網(wǎng)絡(luò)的壽命得以延長。此外,在相同的覆蓋集合工作時(shí)間條件下,節(jié)點(diǎn)數(shù)目較多的傳感器網(wǎng)絡(luò)壽命較長。

2.2.2 算法運(yùn)行時(shí)間與集合工作時(shí)間tw的關(guān)系

為驗(yàn)證算法運(yùn)行時(shí)間與集合工作時(shí)間之間的關(guān)系,將部署節(jié)點(diǎn)數(shù)分別設(shè)置為50和75,將tw分別設(shè)置為0.25 s、0.50 s、0.75 s、1.00 s,圖2所示為算法運(yùn)行時(shí)間隨集合工作時(shí)間的變化曲線。

圖2 算法運(yùn)行時(shí)間與集合工作時(shí)間的關(guān)系

從圖2中可以看出,隨著集合工作時(shí)間的增加,算法運(yùn)行時(shí)間減少。原因是集合工作時(shí)間增加,即節(jié)點(diǎn)在該覆蓋集合中消耗的能量增加,導(dǎo)致其構(gòu)建的符合要求的覆蓋集合減少,從而使得算法很快收斂。在相同的集合工作時(shí)間條件下,節(jié)點(diǎn)數(shù)目較多的網(wǎng)絡(luò)需要較多的時(shí)間去構(gòu)建符合條件的覆蓋集合。

2.2.3 網(wǎng)絡(luò)壽命與節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

為比較本文基于自動(dòng)學(xué)習(xí)機(jī)的節(jié)點(diǎn)調(diào)度算法和貪婪算法的性能,將節(jié)點(diǎn)數(shù)目分別設(shè)為50、75、90、100,每個(gè)覆蓋集合的工作時(shí)間設(shè)為0.25 s,即tw=0.25 s,監(jiān)測(cè)目標(biāo)數(shù)設(shè)為15,然后分析網(wǎng)絡(luò)壽命與節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系。圖3所示為網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)數(shù)目的變化曲線。

圖3 網(wǎng)絡(luò)壽命與節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

從圖3中可以看出,節(jié)點(diǎn)個(gè)數(shù)增加時(shí)2種算法的網(wǎng)絡(luò)壽命均延長。但在部署節(jié)點(diǎn)數(shù)相同的條件下,本文算法的網(wǎng)絡(luò)壽命明顯長于貪婪算法,該結(jié)果驗(yàn)證了本文算法的有效性。

2.2.4 網(wǎng)絡(luò)壽命與監(jiān)測(cè)目標(biāo)個(gè)數(shù)的關(guān)系

為分析監(jiān)測(cè)目標(biāo)個(gè)數(shù)對(duì)算法網(wǎng)絡(luò)壽命的影響,將監(jiān)測(cè)目標(biāo)個(gè)數(shù)分別設(shè)為10、15、20、25,每個(gè)覆蓋集合的工作時(shí)間設(shè)為0.25 s,部署節(jié)點(diǎn)數(shù)設(shè)為100,然后分析網(wǎng)絡(luò)壽命與監(jiān)測(cè)目標(biāo)個(gè)數(shù)的關(guān)系。圖4所示為網(wǎng)絡(luò)壽命隨監(jiān)測(cè)目標(biāo)個(gè)數(shù)的變化曲線。

圖4 網(wǎng)絡(luò)壽命與監(jiān)測(cè)目標(biāo)個(gè)數(shù)的關(guān)系

從圖4中可以看出,監(jiān)測(cè)目標(biāo)個(gè)數(shù)增加時(shí)2種算法的網(wǎng)絡(luò)壽命均減少。但在監(jiān)測(cè)目標(biāo)個(gè)數(shù)相同的情況下,本文算法網(wǎng)絡(luò)壽命明顯長于貪婪算法。

3 結(jié)束語

本文提出一種基于學(xué)習(xí)自動(dòng)機(jī)和貪婪算法的異構(gòu)有向節(jié)點(diǎn)調(diào)度算法。學(xué)習(xí)自動(dòng)機(jī)算法通過與環(huán)境的交互來更新節(jié)點(diǎn)感知方向選取概率,以達(dá)到覆蓋集合的優(yōu)化;貪婪算法根據(jù)節(jié)點(diǎn)覆蓋目標(biāo)的情況和節(jié)點(diǎn)能量情況構(gòu)建符合要求的感知方向集合,從而達(dá)到延長網(wǎng)絡(luò)壽命的目的。仿真結(jié)果表明,與貪婪算法相比,本文算法能有效延長網(wǎng)絡(luò)壽命。下一步將設(shè)計(jì)基于連通覆蓋的異構(gòu)有向節(jié)點(diǎn)調(diào)度算法。