基于全局貪心的有向傳感器網(wǎng)絡(luò)覆蓋算法

摘要：針對(duì)分布式貪心算法(DGreedy)以傳感器節(jié)點(diǎn)的剩余能量為優(yōu)先級(jí)，節(jié)點(diǎn)處理順序沒(méi)有考慮相鄰節(jié)點(diǎn)間的關(guān)系對(duì)網(wǎng)絡(luò)覆蓋率的影響，從而影響覆蓋率的不足，在此提出了一種新的有向傳感器網(wǎng)絡(luò)覆蓋算法。基于全局貪心的原則，以節(jié)點(diǎn)一重覆蓋區(qū)域面積的大小為優(yōu)先級(jí)，優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點(diǎn)方向，從而保證傳感器網(wǎng)絡(luò)的一重覆蓋區(qū)域面積更大，重疊覆蓋區(qū)域較少。對(duì)比實(shí)驗(yàn)結(jié)果表明，該算法能有效提高覆蓋率。
關(guān)鍵詞：有向傳感器網(wǎng)絡(luò)；全局貪心；一重覆蓋；Matlab

0 引言
覆蓋問(wèn)題是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)基本問(wèn)題，是近年來(lái)該領(lǐng)域的研究熱點(diǎn)。目前多數(shù)覆蓋控制的研究成果都是基于滿足全向性感知模型的傳感器進(jìn)行的，但在實(shí)際應(yīng)用中，許多有向傳感器，如視頻傳感器，已被廣泛應(yīng)用于無(wú)線多媒體傳感器網(wǎng)絡(luò)中。與基于滿足全向性感知模型的無(wú)線傳感器網(wǎng)絡(luò)相比，有向傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題更復(fù)雜，是該領(lǐng)域的一個(gè)重要研究方向。
Ma等首先提出了有向傳感器網(wǎng)絡(luò)的概念，設(shè)計(jì)了一種有向傳感器感知模型，并研究了有向傳感器網(wǎng)絡(luò)的覆蓋完整性問(wèn)題。文獻(xiàn)等都采用了基于虛擬勢(shì)場(chǎng)的思想進(jìn)行有向傳感器網(wǎng)絡(luò)覆蓋控制。陶丹等在文獻(xiàn)中設(shè)計(jì)了一種方向可調(diào)的感知模型，并以此為基礎(chǔ)首先提出了基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法，通過(guò)引入“質(zhì)心”的概念，將有向傳感器用質(zhì)心點(diǎn)代替，并將有向傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題轉(zhuǎn)化為質(zhì)心分布問(wèn)題，質(zhì)心點(diǎn)在虛擬力的作用下運(yùn)動(dòng)，消除感知盲區(qū)和重疊區(qū)。傳統(tǒng)基于虛擬勢(shì)場(chǎng)的有向傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法只判斷和調(diào)整方向，節(jié)點(diǎn)的調(diào)整量為固定值，針對(duì)這一問(wèn)題，黃帥等在文獻(xiàn)中利用虛擬力與角度調(diào)整量間的關(guān)系，根據(jù)虛擬力的大小改變節(jié)點(diǎn)的角度調(diào)整量，提高了網(wǎng)絡(luò)的調(diào)整效率。但是，以上基于虛擬勢(shì)場(chǎng)思想的無(wú)線傳感器網(wǎng)絡(luò)覆蓋方法，每個(gè)節(jié)點(diǎn)均需計(jì)算多個(gè)相鄰節(jié)點(diǎn)的合力，節(jié)點(diǎn)受力隨轉(zhuǎn)動(dòng)過(guò)程不斷變化，使得算法較復(fù)雜；且節(jié)點(diǎn)根據(jù)力矢量的大小和方向進(jìn)行轉(zhuǎn)動(dòng)，轉(zhuǎn)動(dòng)角度取值過(guò)小會(huì)增加調(diào)整時(shí)間，取值過(guò)大則會(huì)引起頻繁的計(jì)算和傳感方向的反復(fù)調(diào)整，且因合力未必為0，可能導(dǎo)致調(diào)整過(guò)程中角度往復(fù)震蕩。文獻(xiàn)提出了一種分布式貪心算法(DGreedy)，以傳感器節(jié)點(diǎn)的剩余能量為優(yōu)先級(jí)，每個(gè)傳感器基于局部貪心原則選擇工作方向，使傳感器網(wǎng)絡(luò)覆蓋盡可能大的區(qū)域。但是，DGreedy算法受傳感器節(jié)點(diǎn)處理順序影響較大，以剩余能量為優(yōu)先級(jí)的方法沒(méi)有考慮節(jié)點(diǎn)問(wèn)覆蓋區(qū)域的相互影響，從而影響整個(gè)網(wǎng)絡(luò)的覆蓋率。
本文基于全局貪心原則，提出了一種有向傳感器網(wǎng)絡(luò)覆蓋算法。以節(jié)點(diǎn)各方向下一重覆蓋區(qū)域的大小為優(yōu)先級(jí)，優(yōu)先確定一重覆蓋區(qū)域面積最大的傳感器節(jié)點(diǎn)方向，保證了傳感器網(wǎng)絡(luò)的一重覆蓋區(qū)域面積更大，重疊覆蓋區(qū)域較少。對(duì)比實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

1 覆蓋算法
1．1 DGreedy算法
分布式貪心算法DGreedy由程衛(wèi)芳等人提出，并應(yīng)用于有向傳感器網(wǎng)絡(luò)覆蓋中。DGreedy假設(shè)傳感器節(jié)點(diǎn)不同方向的感應(yīng)范圍互不重疊，4個(gè)可選方向的傳感器節(jié)點(diǎn)示例如圖1所示，圖中Si,j表示第i個(gè)傳感器的第j個(gè)方向。文中還假定所有傳感器節(jié)點(diǎn)具有相同的結(jié)構(gòu)。給每個(gè)傳感器分配一個(gè)彼此不同的優(yōu)先級(jí)，并定義Gi,j表示節(jié)點(diǎn)Si的第J個(gè)方向上，沒(méi)有被更高級(jí)的感應(yīng)鄰居所覆蓋的面積。