孫曉杰，田 琳

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

1 引言

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

(3)

3)節(jié)點F的相鄰某節(jié)點覆蓋點E的概率為p(x)，對p(x)值實施運算

p(x)=D/πr2

(4)

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

(5)

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

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

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

2.2.1 目標感知概率模型

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

(6)

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

2.2.2 覆蓋控制算法

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

1)覆蓋概率極限

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

2)感知力較強節(jié)點覆蓋集的構建

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

Bi=qi1+qi2+…+qiM

(7)

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

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

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

(8)

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

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

3)不易被感知節(jié)點覆蓋集的構建

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

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

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

(9)

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

③在此基礎上獲得此部分節(jié)點覆蓋集，獲取過程與感知力較強節(jié)點覆蓋集構建步驟③中覆蓋集的求解過程相同。

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

3 實驗結果分析

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

3.1 冗余節(jié)點休眠效果檢驗

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

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

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

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

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

e-σ(r2-r1)≥Nmin

(10)

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

(11)

(12)

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

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

4 結論

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