多址接入無線傳感器網(wǎng)絡(luò)覆蓋控制算法研究

孫曉杰，田 琳

(伊犁師范大學(xué)電子與信息工程學(xué)院，新疆 伊寧 835000)

1 引言

當(dāng)多址接入無線傳感器網(wǎng)絡(luò)的運(yùn)算能力、通訊寬帶以及節(jié)點(diǎn)能量等均被制約時(shí)，運(yùn)用選擇路由或放置傳感器節(jié)點(diǎn)等方式優(yōu)化網(wǎng)絡(luò)各類資源，以此改善網(wǎng)絡(luò)的通訊、傳感及感知等服務(wù)水平，此為多址接入無線傳感器網(wǎng)絡(luò)的覆蓋控制手段[1，2]。通過恰當(dāng)?shù)母采w控制方式，可有效提升網(wǎng)絡(luò)的服務(wù)水平、降低網(wǎng)絡(luò)整體能耗、均衡各節(jié)點(diǎn)能量并延長網(wǎng)絡(luò)的使用壽命[3]。

感知概率模型下的傳感器覆蓋算法是通過感知概率模型，確定概率閾值及各節(jié)點(diǎn)的感知距離界限，依次排序各節(jié)點(diǎn)后，構(gòu)成概率覆蓋實(shí)現(xiàn)覆蓋控制。該算法可適度均衡各節(jié)點(diǎn)能量，但因?qū)嶋H使用中控制精度的制約，降低網(wǎng)絡(luò)能耗的效果有限[4]；非合作博弈的無線傳感器網(wǎng)絡(luò)覆蓋控制算法是通過余下能量及節(jié)點(diǎn)覆蓋率建立收益函數(shù)，并為各節(jié)點(diǎn)挑選恰當(dāng)?shù)倪\(yùn)行方式實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞臉?gòu)造，基于此結(jié)合非合作博弈理論建立覆蓋控制算法實(shí)現(xiàn)對網(wǎng)絡(luò)的覆蓋控制。該算法可為網(wǎng)絡(luò)節(jié)點(diǎn)提供恰當(dāng)?shù)母采w率，但在降低網(wǎng)絡(luò)整體能耗方面效果稍差[5]。

基于以上分析，本文研究一種結(jié)合布爾感知模型與概率感知模型的多址接入無線傳感器網(wǎng)絡(luò)覆蓋控制算法。

2 多址接入無線傳感器網(wǎng)絡(luò)覆蓋控制算法

2.1 基于布爾感知模型的冗余節(jié)點(diǎn)判別與檢測

因多址接入無線傳感器網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)部署具有較強(qiáng)的隨機(jī)性，極易產(chǎn)生存在感知覆蓋的重疊區(qū)間，因此，需采用冗余節(jié)點(diǎn)判別的方式檢測出冗余節(jié)點(diǎn)，并令此類節(jié)點(diǎn)休眠，以此將傳感器網(wǎng)絡(luò)的使用壽命延長[6，7]。在此選用布爾感知模型，實(shí)現(xiàn)冗余節(jié)點(diǎn)的判別與檢查。設(shè)定多址接入無線傳感器網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)i的覆蓋區(qū)間用D(i)表示，其運(yùn)算式為

D(i)={E∈A|d(E，Di)≤r}

(1)

式(1)中，檢測區(qū)間面積與此區(qū)間中的點(diǎn)分別以A和E表示；節(jié)點(diǎn)i的位置以Di表示；點(diǎn)E與Di之間的歐氏距離以d(E，Di)表示。

如圖1(a)所示，節(jié)點(diǎn)i、j重疊覆蓋區(qū)間為圖中陰影部分，針對節(jié)點(diǎn)i而言，若它的覆蓋區(qū)間符合下式

(2)

式中，與節(jié)點(diǎn)i相近的鄰節(jié)點(diǎn)集合用C(i)表示，即與該節(jié)點(diǎn)之間的間距不超出節(jié)點(diǎn)感知半徑r的節(jié)點(diǎn)集，該集合可表示為C(i)={j∈C|d(i，j)≤r，j≠i}，所檢測區(qū)間中的節(jié)點(diǎn)集用C表示，節(jié)點(diǎn)i、j間的歐氏距離用d(i，j)表示。當(dāng)節(jié)點(diǎn)i的覆蓋區(qū)間符合式(2)時(shí)，那么此節(jié)點(diǎn)即為冗余節(jié)點(diǎn)，可令其步入休眠狀況。

圖1 冗余節(jié)點(diǎn)判別檢測模型

如圖1(b)所示，假設(shè)節(jié)點(diǎn)F覆蓋區(qū)間中的隨機(jī)一個(gè)點(diǎn)為E，點(diǎn)E與節(jié)點(diǎn)F之間的間距以變量X表示，那么其取值區(qū)間與概率密度函數(shù)分別用0≤x≤r與fX(x)=2x/r2表示。由節(jié)點(diǎn)F的相鄰節(jié)點(diǎn)覆蓋點(diǎn)E的期望值運(yùn)算過程為

1)假設(shè)節(jié)點(diǎn)F的相鄰節(jié)點(diǎn)覆蓋點(diǎn)E的概率用p(x)表示，若節(jié)點(diǎn)F所具備的相鄰節(jié)點(diǎn)數(shù)目為m個(gè)，那么此類節(jié)點(diǎn)覆蓋點(diǎn)E的概率表示為1-(1-p(x))m。

2)圖1(b)中陰影區(qū)間為半徑為r，對圖1(b)中陰影區(qū)間的面積實(shí)施運(yùn)算：設(shè)節(jié)點(diǎn)F距離節(jié)點(diǎn)E的間距用|FE|=x表示，其中0≤x≤r。運(yùn)算所得陰影區(qū)間的覆蓋面積D可表示為

(3)

3)節(jié)點(diǎn)F的相鄰某節(jié)點(diǎn)覆蓋點(diǎn)E的概率為p(x)，對p(x)值實(shí)施運(yùn)算

p(x)=D/πr2

(4)

若節(jié)點(diǎn)F的相鄰節(jié)點(diǎn)數(shù)量為m，那么此類節(jié)點(diǎn)覆蓋點(diǎn)E的概率期望值G的運(yùn)算式為

(5)

在此設(shè)置冗余節(jié)點(diǎn)的判別規(guī)則為當(dāng)某個(gè)節(jié)點(diǎn)可以被大于等于三個(gè)的相鄰節(jié)點(diǎn)覆蓋時(shí)，即可判別此節(jié)點(diǎn)屬于冗余節(jié)點(diǎn)[8]，以此為依據(jù)檢測無線傳感器網(wǎng)絡(luò)目標(biāo)區(qū)間內(nèi)的冗余節(jié)點(diǎn)，并使此類節(jié)點(diǎn)停止運(yùn)行開始休眠。

2.2 基于概率感知模型的覆蓋控制算法

在以上冗余節(jié)點(diǎn)休眠的基礎(chǔ)上，結(jié)合概率感知模型的覆蓋控制算法，實(shí)現(xiàn)高精度的網(wǎng)絡(luò)覆蓋控制。將經(jīng)過冗余節(jié)點(diǎn)休眠后的網(wǎng)絡(luò)目標(biāo)區(qū)間作為此部分的目標(biāo)感知區(qū)間。

2.2.1 目標(biāo)感知概率模型

通過與x軸、y軸平行的一些直線將多址接入無線傳感器網(wǎng)絡(luò)的目標(biāo)感知區(qū)間劃分成m×m的網(wǎng)格，則網(wǎng)格點(diǎn)數(shù)量為m2個(gè)，m2行m2列的矩陣即為傳感器感知矩陣，該矩陣用B=[qij]表示，其元素?cái)?shù)量為m4個(gè)。若無線傳感器網(wǎng)絡(luò)目標(biāo)感知區(qū)間內(nèi)的節(jié)點(diǎn)總數(shù)為N(N≤M)個(gè)，同時(shí)各節(jié)點(diǎn)可單獨(dú)感知目標(biāo)，那么i網(wǎng)格點(diǎn)目標(biāo)的被感知概率可表示為

(6)

式(6)中，節(jié)點(diǎn)集合數(shù)量用a表示；網(wǎng)格點(diǎn)用k表示；M=m2，且i=1，2，…，m。

2.2.2 覆蓋控制算法

基于概率感知模型的覆蓋控制算法的關(guān)鍵在于構(gòu)建感知力較強(qiáng)節(jié)點(diǎn)覆蓋集與不易被感知到節(jié)點(diǎn)覆蓋集，結(jié)合兩個(gè)覆蓋集，實(shí)現(xiàn)對多址接入無線傳感器網(wǎng)絡(luò)的覆蓋控制。

1)覆蓋概率極限

設(shè)目標(biāo)被感知到的最低概率(即概率極限)用Nmin表示，也就是在Hi大于等于Nmin時(shí)，即為目標(biāo)i被感知到。其中多址接入無線傳感器網(wǎng)絡(luò)的現(xiàn)實(shí)使用環(huán)境、服務(wù)質(zhì)量需求與軟硬件條件等均能夠影響到Nmin值的確定，用戶可指定該值。

2)感知力較強(qiáng)節(jié)點(diǎn)覆蓋集的構(gòu)建

此部分主要針對運(yùn)行次數(shù)少，同時(shí)感知力強(qiáng)的節(jié)點(diǎn)，在各周期內(nèi)首先將此類節(jié)點(diǎn)喚醒，并構(gòu)建覆蓋集以保障傳感器網(wǎng)絡(luò)的覆蓋需求。感知力強(qiáng)節(jié)點(diǎn)的運(yùn)用能夠?qū)⒏采w集節(jié)點(diǎn)的數(shù)量降低；運(yùn)行次數(shù)少的節(jié)點(diǎn)其所擁有的能量更多，喚醒此類節(jié)點(diǎn)運(yùn)行，休眠能量少的節(jié)點(diǎn)可實(shí)現(xiàn)傳感器網(wǎng)絡(luò)的能量均衡，避免部分能量少的節(jié)點(diǎn)功能喪失[9]。使用此覆蓋集實(shí)施覆蓋控制算法所需實(shí)現(xiàn)的目標(biāo)為：以預(yù)先設(shè)置的規(guī)則為依據(jù)，將充足數(shù)量的節(jié)點(diǎn)喚醒，此類節(jié)點(diǎn)的覆蓋能夠達(dá)到無線傳感器網(wǎng)絡(luò)的覆蓋需求，也就是全部網(wǎng)格點(diǎn)位置的目標(biāo)被感知到的概率均大于等于Nmin。可表示為

Bi=qi1+qi2+…+qiM

(7)

式(7)中，Bi值越高則節(jié)點(diǎn)i的感知力越強(qiáng)，在未執(zhí)行算法時(shí)運(yùn)算此值，并將其輸入到各周期運(yùn)算內(nèi)。一個(gè)完整周期覆蓋集的運(yùn)算步驟如下：

①將B、Bi、Nmin、M及m(i)(i=1，2，…，N)輸入，其中，m(i)代表節(jié)點(diǎn)i的運(yùn)行次數(shù)。

②對節(jié)點(diǎn)喚醒次序表實(shí)施運(yùn)算：以之前運(yùn)行周期所提供的各節(jié)點(diǎn)運(yùn)行次數(shù)為依據(jù)，向某個(gè)集合內(nèi)歸類同樣運(yùn)行次數(shù)的節(jié)點(diǎn)，同時(shí)對歸類后的各個(gè)集合依據(jù)運(yùn)行次數(shù)由少至多排序[10]。如果集合數(shù)量總計(jì)為u個(gè)，集合以Ui表示，其中i=1，2，…，u，各集合Ui內(nèi)的節(jié)點(diǎn)均具有統(tǒng)一的運(yùn)行次數(shù)，同時(shí)集合Ui內(nèi)的節(jié)點(diǎn)運(yùn)行次數(shù)比Ui+1低。按照由高到低的次序依次排列集合Ui內(nèi)各個(gè)節(jié)點(diǎn)的感知力，可表示為Bi1≥Bi2≥…≥Biai，其中，ai代表集合Ui內(nèi)節(jié)點(diǎn)的數(shù)量。基于此所獲取到的節(jié)點(diǎn)喚醒次序表融合了感知力與節(jié)點(diǎn)運(yùn)行次數(shù)，可表示為：

(8)

為方便運(yùn)算，可簡化式(8)為B1，B2，…，BN。

③基于以上兩步驟對此部分覆蓋集實(shí)施求解，求解過程為：a.初始覆蓋節(jié)點(diǎn)集屬于空集，將此部分節(jié)點(diǎn)依據(jù)次序表依次向此空集內(nèi)加入；b.以節(jié)點(diǎn)i為例，向覆蓋集內(nèi)加入節(jié)點(diǎn)i，依據(jù)此節(jié)點(diǎn)的運(yùn)行次數(shù)，對覆蓋集內(nèi)節(jié)點(diǎn)i運(yùn)行時(shí)網(wǎng)格點(diǎn)k位置目標(biāo)被感知到的概率Hk實(shí)施運(yùn)算；c.如果min1≤k≤M{Hk}≥Nmin，則運(yùn)算結(jié)束，輸出此部分節(jié)點(diǎn)覆蓋集。

3)不易被感知節(jié)點(diǎn)覆蓋集的構(gòu)建

此部分重點(diǎn)針對運(yùn)行次數(shù)少，但所處網(wǎng)格點(diǎn)位置不易被感知到的節(jié)點(diǎn)，在各個(gè)周期內(nèi)首先將此部分節(jié)點(diǎn)喚醒，同時(shí)構(gòu)建此部分節(jié)點(diǎn)覆蓋集。喚醒不易被感知到的節(jié)點(diǎn)運(yùn)行，能夠?qū)o線傳感器網(wǎng)絡(luò)的感知概率快速提升。在感知概率模型式(6)中使qki為0，能夠在開啟其余節(jié)點(diǎn)的前提下將節(jié)點(diǎn)i位置目標(biāo)被感知到的概率獲取到。在未執(zhí)行算法時(shí)運(yùn)算此概率值，并將其輸入到各周期運(yùn)算內(nèi)。此部分單個(gè)周期覆蓋集運(yùn)算步驟為：

①將B、Nmin、M、m(i)(i=1，2，…，N)及qki輸入。

②此部分節(jié)點(diǎn)喚醒次序表的獲取：此部分各節(jié)點(diǎn)運(yùn)行次數(shù)集合U′i的歸類及排序方式與感知力較強(qiáng)節(jié)點(diǎn)覆蓋集構(gòu)建步驟②相同，在此基礎(chǔ)上，依據(jù)由高到低的次序依次排列集合U′i內(nèi)各節(jié)點(diǎn)網(wǎng)格點(diǎn)位置目標(biāo)的被感知概率，可表示為qi1≤qi2≤…≤qiai，其中，ai代表集合U′i內(nèi)節(jié)點(diǎn)的數(shù)量。綜合以上獲取到一個(gè)將被感知概率與運(yùn)行次數(shù)相結(jié)合的節(jié)點(diǎn)喚醒次序表，可表示為：

(9)

為方便運(yùn)算，簡化式(9)為Q1，Q2，…，QN。

③在此基礎(chǔ)上獲得此部分節(jié)點(diǎn)覆蓋集，獲取過程與感知力較強(qiáng)節(jié)點(diǎn)覆蓋集構(gòu)建步驟③中覆蓋集的求解過程相同。

結(jié)合以上兩個(gè)覆蓋集實(shí)現(xiàn)對多址接入無線傳感器網(wǎng)絡(luò)的覆蓋控制，若傳感器網(wǎng)絡(luò)內(nèi)各目標(biāo)所具備的感知極限不統(tǒng)一，僅需對加入節(jié)點(diǎn)時(shí)各目標(biāo)分別能達(dá)到自身的覆蓋概率極限予以考量。

3 實(shí)驗(yàn)結(jié)果分析

將本文算法應(yīng)用于某多址接入無線傳感器網(wǎng)絡(luò)內(nèi)，對其實(shí)施覆蓋控制，檢驗(yàn)實(shí)際應(yīng)用效果與控制下實(shí)驗(yàn)傳感器網(wǎng)絡(luò)的能耗情況。由實(shí)驗(yàn)傳感器網(wǎng)絡(luò)內(nèi)選取出a、b兩個(gè)區(qū)間作為實(shí)驗(yàn)?zāi)繕?biāo)區(qū)間，其中a區(qū)間位于實(shí)驗(yàn)網(wǎng)絡(luò)的邊緣，其尺寸為60m×60m，此區(qū)間內(nèi)的節(jié)點(diǎn)數(shù)量為80個(gè)，b區(qū)間位于實(shí)驗(yàn)網(wǎng)絡(luò)的正中，其尺寸為90m×90m，此區(qū)間內(nèi)的節(jié)點(diǎn)數(shù)量為180個(gè)。

3.1 冗余節(jié)點(diǎn)休眠效果檢驗(yàn)

設(shè)定實(shí)驗(yàn)網(wǎng)絡(luò)的節(jié)點(diǎn)傳感半徑為11m，在a、b兩個(gè)目標(biāo)區(qū)間中通過本文算法判別并檢測出冗余節(jié)點(diǎn)后實(shí)施冗余節(jié)點(diǎn)休眠，對比休眠前后兩個(gè)目標(biāo)區(qū)間的覆蓋變化情況，如圖2所示。

圖2 本文算法休眠冗余節(jié)點(diǎn)前后各目標(biāo)區(qū)間覆蓋情況

由圖2可看出，在未采用本文算法休眠冗余節(jié)點(diǎn)時(shí)，兩個(gè)不同數(shù)量節(jié)點(diǎn)的目標(biāo)區(qū)間內(nèi)的覆蓋程度均較高，存在過多的冗余節(jié)點(diǎn)干擾，應(yīng)用本文算法休眠冗余節(jié)點(diǎn)之后，明顯降低了兩個(gè)目標(biāo)區(qū)間內(nèi)的冗余節(jié)點(diǎn)數(shù)量，且兩個(gè)目標(biāo)區(qū)間內(nèi)的覆蓋程度均得到顯著改善，與此同時(shí)保證了兩個(gè)目標(biāo)區(qū)間均得到覆蓋，由此可見，本文算法可通過休眠冗余節(jié)點(diǎn)控制無線傳感器網(wǎng)絡(luò)的覆蓋程度，控制效果明顯。

3.2 目標(biāo)區(qū)間整體能量消耗控制效果對比

此實(shí)驗(yàn)中所需用到的對比對象包括感知概率模型的傳感器網(wǎng)絡(luò)覆蓋算法(文獻(xiàn)[4]算法)、非合作博弈的無線傳感器網(wǎng)絡(luò)覆蓋控制算法(文獻(xiàn)[5]算法)以及單位時(shí)間目標(biāo)區(qū)間的整體能量消耗上限值與下限值。以目標(biāo)區(qū)間b為例，該區(qū)間內(nèi)運(yùn)行節(jié)點(diǎn)的單位時(shí)間所消耗能量以We表示，在該區(qū)間內(nèi)全部節(jié)點(diǎn)均處于運(yùn)行狀態(tài)時(shí)，此區(qū)間具有最高的單位時(shí)間整體能量消耗，由于該區(qū)間的節(jié)點(diǎn)總數(shù)量為180個(gè)，則其單位時(shí)間整體能量消耗的上限值可表示為180We。下限值的運(yùn)算過程為：在某個(gè)目標(biāo)僅存在單個(gè)節(jié)點(diǎn)覆蓋的情況下，為了令該目標(biāo)的覆蓋概率達(dá)到極限，那么有

e-σ(r2-r1)≥Nmin

(10)

式(10)中，同傳感器物理性能相關(guān)的可調(diào)類別參數(shù)以σ表示。該式可改寫為

(11)

(12)

圖3 各算法控制下目標(biāo)區(qū)間b的單位時(shí)間整體能量消耗

分析圖3能夠得知，三種算法控制下目標(biāo)區(qū)間b的單位時(shí)間整體能量消耗均高于理想下限值，其中非合作博弈算法控制下的能量消耗值最高，且在不同感知概率極限下幾乎無變化；本文算法與感知概率模型算法控制下的能量消耗均隨著感知概率極限的升高而呈現(xiàn)上升趨勢，但本文算法的上升幅度相對更小，且能量消耗更低，原因是本文算法結(jié)合了布爾感知模型與感知概率模型，控制更加細(xì)膩且精度更高，能夠減少節(jié)點(diǎn)的喚醒數(shù)量，更大的節(jié)約了網(wǎng)絡(luò)能量消耗。

4 結(jié)論

本文針對一種多址接入無線傳感器網(wǎng)絡(luò)覆蓋控制算法展開研究，通過結(jié)合布爾感知模型與感知概率模型，在對網(wǎng)絡(luò)內(nèi)冗余節(jié)點(diǎn)實(shí)施判別檢測后，在休眠所檢測出冗余節(jié)點(diǎn)的基礎(chǔ)上，運(yùn)用感知概率模型覆蓋控制算法，分別構(gòu)建感知力強(qiáng)與不易被感知的兩個(gè)覆蓋集，實(shí)現(xiàn)對多址接入無線傳感器網(wǎng)絡(luò)的覆蓋控制。實(shí)驗(yàn)結(jié)果表明，本文算法可有效休眠冗余節(jié)點(diǎn)，控制無線傳感器網(wǎng)絡(luò)的覆蓋程度，控制效果明顯；在本文算法的控制下，網(wǎng)絡(luò)的目標(biāo)區(qū)間單位時(shí)間整體能量消耗較低，達(dá)到節(jié)約無線傳感器網(wǎng)絡(luò)能耗的效果，為延長多址接入無線傳感器網(wǎng)絡(luò)的使用壽命提供幫助。