無線傳感網(wǎng)絡(luò)監(jiān)測(cè)質(zhì)量的統(tǒng)計(jì)分析

白 雪,程宗毛

(杭州電子科技大學(xué),浙江 杭州 310018)

0 引 言

近年來，隨著科學(xué)技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)的應(yīng)用也越來越廣泛，涉及社會(huì)生活的各個(gè)領(lǐng)域，其中包括數(shù)據(jù)安全[1]、環(huán)境監(jiān)控[2]以及煤礦安全監(jiān)測(cè)[3]等眾多領(lǐng)域。無線傳感器網(wǎng)絡(luò)在迅速發(fā)展的同時(shí)也面臨著許多需要解決的問題。無線傳感網(wǎng)絡(luò)主要是通過部署傳感器構(gòu)成,對(duì)相應(yīng)的區(qū)域進(jìn)行監(jiān)測(cè)覆蓋。覆蓋問題是無線傳感網(wǎng)絡(luò)最基本的一個(gè)問題，其最終目的是用盡可能少的節(jié)點(diǎn)使覆蓋最大化。起初，在一個(gè)固定的區(qū)域內(nèi)，這個(gè)區(qū)域有一些興趣點(diǎn)(Point of Interest， PoI)，即有隨機(jī)事件可能發(fā)生的地方。隨機(jī)拋灑一定量的傳感器用于覆蓋這些興趣點(diǎn)，目的是將傳感器的部署成本降到最低，并且使覆蓋達(dá)到最大化。在以往研究關(guān)于海洋環(huán)境中的覆蓋時(shí)，人們盡量減少實(shí)現(xiàn)這一效果所需的節(jié)點(diǎn)數(shù)，來節(jié)省能源以達(dá)到最佳目標(biāo)覆蓋的目的。同時(shí)傳感器的部署成本不僅取決于放置傳感器的數(shù)量，還取決于所使用的能量收集設(shè)備的成本。文獻(xiàn)[4]編制了基于線性規(guī)劃啟發(fā)式求解算法，又由于解決大規(guī)模的線性問題非常耗時(shí)，為了進(jìn)一步在解決此問題時(shí)節(jié)省時(shí)間，文獻(xiàn)[5]提出了復(fù)雜度較低的TSH算法，處理最低成本目標(biāo)覆蓋問題，取得了良好的效果。以往研究中解決了節(jié)省時(shí)間的問題，但遺憾的是上述問題沒有考慮到興趣點(diǎn)的隨機(jī)事件發(fā)生的特點(diǎn)，如果興趣點(diǎn)上的隨機(jī)事件發(fā)生的間隔時(shí)間過長(zhǎng)或者隨機(jī)事件逗留的時(shí)間過長(zhǎng)，在此期間覆蓋集的傳感器一直打開的情況下，就會(huì)需要很大成本來提供能量，引起能量的巨大浪費(fèi)[6]。在這樣一個(gè)固定區(qū)域內(nèi)的目標(biāo)點(diǎn)覆蓋的問題中，如果適當(dāng)?shù)乜紤]興趣點(diǎn)上的隨機(jī)事件的指數(shù)分布特性，在整個(gè)覆蓋集上同步進(jìn)行適當(dāng)?shù)男菝吆图せ畹闹芷谛怨ぷ鱗7-9]，會(huì)使得隨機(jī)事件的捕獲質(zhì)量提高，同時(shí)又可以節(jié)約相當(dāng)數(shù)量的能量。文獻(xiàn)[10]分析了隨機(jī)事件的監(jiān)測(cè)質(zhì)量(QoM)，用周期傳感器每次對(duì)q時(shí)刻進(jìn)行興趣點(diǎn)(PoI)的監(jiān)測(cè)。因此，在以往研究結(jié)果的基礎(chǔ)上，本文考慮到隨機(jī)事件的特點(diǎn)，結(jié)合統(tǒng)計(jì)知識(shí)進(jìn)行分析，對(duì)傳感器網(wǎng)絡(luò)進(jìn)行同步周期性地開關(guān)，以達(dá)到最大的監(jiān)測(cè)質(zhì)量，最終延長(zhǎng)網(wǎng)絡(luò)壽命。

1 網(wǎng)絡(luò)模型與隨機(jī)事件的參數(shù)分析

1.1 網(wǎng)絡(luò)模型

假設(shè)在無線傳感器網(wǎng)絡(luò)的監(jiān)測(cè)范圍內(nèi)，隨機(jī)拋灑一定數(shù)量的傳感器來覆蓋整個(gè)區(qū)域，隨機(jī)事件在給定的興趣點(diǎn)出現(xiàn)和消失，并由感測(cè)半徑為R的傳感器來進(jìn)行捕獲，傳感器采用布爾圓盤感知模型[11]，即事件如果出現(xiàn)在節(jié)點(diǎn)半徑R內(nèi)，則可以被有效捕獲，如果事件出現(xiàn)在感測(cè)半徑R以外則不能被有效捕獲，即定義在位置p處的傳感器觀察到位置q的時(shí)間概率用二值函數(shù)P(p,q)來表示：

(1)

其中，|p-q|為p、q的歐氏距離，R為布爾感知模型的感知半徑。

1.2 隨機(jī)事件的參數(shù)估計(jì)

假設(shè)隨機(jī)事件發(fā)生的停留時(shí)間X和缺席時(shí)間Y服從參數(shù)未知的指數(shù)分布[12]。在統(tǒng)計(jì)學(xué)理論中，參數(shù)估計(jì)分為點(diǎn)估計(jì)和區(qū)間估計(jì)。由于點(diǎn)估計(jì)在樣本量不足時(shí)，估計(jì)值與參數(shù)真實(shí)值存在較大差異，因此采用區(qū)間估計(jì)來提高估計(jì)精度。以隨機(jī)事件發(fā)生停留時(shí)間X為例，假設(shè)X服從參數(shù)為λ的指數(shù)分布，α>0且α未知，則密度函數(shù)為：

(2)

(3)

(4)

Pt{a≤t≤b}=1-α

(5)

根據(jù)Neyman[15]的區(qū)間估計(jì)理論的基本思想，a、b需要滿足：

(6)

2 監(jiān)測(cè)質(zhì)量及隨機(jī)事件最優(yōu)調(diào)度

2.1 監(jiān)測(cè)質(zhì)量的定義

(7)

因此，將PoIi的QoM和整個(gè)區(qū)域覆蓋定義為：

(8)

2.2 最優(yōu)調(diào)度方案

1)周期傳感器的事件捕獲。

考慮單個(gè)傳感器節(jié)點(diǎn)(p,q)的時(shí)間捕獲性能，對(duì)于其傳感區(qū)域覆蓋興趣點(diǎn)的周期傳感器在i處捕獲事件(事件消失之前)，概率為：

(9)

其中，Pc表達(dá)式是兩項(xiàng)的和，第一項(xiàng)表示傳感器在此期間[0,q]捕獲事件的概率，相當(dāng)于性能度量Pin，因?yàn)檫@些事件是即時(shí)捕獲的。第二項(xiàng)則給出了傳感器在缺席期間[q，p]到達(dá)的捕獲事件的概率，并且保持足夠長(zhǎng)的時(shí)間，以便在下一個(gè)傳感器周期[p，p+q]內(nèi)信息能夠被捕獲到。這些事件被延遲捕獲，因此有助于性能度量Pc。其次由式(9)還可以觀察到主要貢獻(xiàn)的第二項(xiàng)，只要事件保持不變，這個(gè)屬性就成立，就像它們?cè)趯?shí)際應(yīng)用中通常做的那樣，并且不依賴于詳細(xì)的事件動(dòng)態(tài)。可以通過分析這些事件的預(yù)期延遲以及所有捕獲的事件，給出下面的定理：

定理1 對(duì)于獨(dú)立到達(dá)的停留事件，在一個(gè)PoI處的QoM也可由式(10)表示。

(10)

定理2 適用于事件停留時(shí)間的一般分布。隨機(jī)事件用指數(shù)分布來說明這個(gè)結(jié)果，由f(x)表示：

(11)

定理3 對(duì)于PoI捕捉到的在傳感器缺席期間到達(dá)的事件，在i處捕獲之前的預(yù)期延遲將由公式(12)表示。

(12)

對(duì)于在PoI中捕獲的所有事件，預(yù)期的捕獲延遲將由式(13)表示。

(13)

2)同步周期調(diào)度的能量感知優(yōu)化。

首先討論同步周期網(wǎng)絡(luò)調(diào)度(q,p)的優(yōu)化。在這樣的無線傳感網(wǎng)絡(luò)中，所有的傳感器都使用相同的(q,p)時(shí)間表，同時(shí)啟動(dòng)它們的開關(guān)，以便它們?cè)谙嗤闹芷谑峭降?。因此，整個(gè)全局網(wǎng)絡(luò)作為一個(gè)整體的行為就像(q,p)上的一個(gè)大傳感器?？梢钥闯?，公式(9)中Pc的值具有2個(gè)性質(zhì)：①對(duì)相同的p來說，Pc在q=p中單調(diào)遞增；②對(duì)于同一q=p，Pc是單調(diào)遞增地減少p。因此，為了優(yōu)化事件捕獲，如果決定使用較小的q=p，可以使p盡可能小。第一種選擇不會(huì)幫助無線傳感網(wǎng)絡(luò)節(jié)省能量，而第二種選擇在物理上受到頻繁在開關(guān)狀態(tài)之間切換傳感器產(chǎn)生的延遲和能量消耗的限制。為了優(yōu)化時(shí)間周期計(jì)劃，需要明確根據(jù)下面給出的模型來說明能源消耗的情況。具體來說，對(duì)于(p,q)周期性傳感器，它能夠捕捉一小部分Pc的事件，因此，它的每個(gè)捕獲時(shí)間速率由式(14)給出：

(14)

其中c為常數(shù)。

PoI捕獲事件的速率是將上述λ代入得到：

(15)

在整個(gè)網(wǎng)絡(luò)覆蓋中，可能存在多個(gè)PoI在傳感器的范圍里面，同時(shí)也可能相同的PoI在多個(gè)傳感器的監(jiān)測(cè)范圍里面。因此傳感器可能無法捕獲不同的事件。本文假設(shè)在n個(gè)傳感器的范圍里有m個(gè)不同的PoI網(wǎng)絡(luò)，每個(gè)捕獲不同事件數(shù)的整個(gè)網(wǎng)絡(luò)的單位能量用(m×Q′)/(n×E′)來表示。這個(gè)值是上述QE值按m/n的常數(shù)因子標(biāo)度[17]。按常數(shù)因子縮放不會(huì)影響優(yōu)化問題的解。

3 模擬分析

本章給出實(shí)驗(yàn)?zāi)M分析的結(jié)果。同樣使用X和Y分別表示事件停留和缺席時(shí)間變量。實(shí)驗(yàn)測(cè)量QoM在模擬運(yùn)行中實(shí)現(xiàn)了100個(gè)時(shí)間單元，并報(bào)告了10次不同運(yùn)行的平均Qi。

現(xiàn)在說明如何使用上述定理來設(shè)計(jì)算法，優(yōu)化步驟實(shí)用程序的一般周期調(diào)度。從固定長(zhǎng)度n的任何初始周期時(shí)間表開始，都有n！個(gè)直接排列的時(shí)間表，以獲得一個(gè)一般的周期時(shí)間表。但對(duì)于大n，窮舉搜索最優(yōu)調(diào)度在計(jì)算上是不可行的。為了克服這一挑戰(zhàn)，使用算法1模擬退火算法搜索一個(gè)一般的非線性周期調(diào)度，其Q值盡可能地接近最優(yōu)。

不同的運(yùn)行產(chǎn)生的結(jié)果有極小的差異。每個(gè)報(bào)告的實(shí)驗(yàn)對(duì)事件停留和缺席時(shí)間都默認(rèn)使用相同的分布即指數(shù)分布[18]，利用不同的參數(shù)λ來體現(xiàn)不同數(shù)據(jù)的影響，運(yùn)用模擬退火算法[20]對(duì)指數(shù)事件動(dòng)態(tài)事件進(jìn)行優(yōu)化調(diào)度。

算法1 優(yōu)化周期調(diào)度的模擬退火算法

模擬退火算法Simulated Annealing Algorithm

1 best=s=initial periodic schedule//賦于初始周期時(shí)間表

2 Qbest=Qs=QoM(best)//監(jiān)測(cè)質(zhì)量QoM賦值

3 for(i=0；i〈computation_budget；i++)//若i小于預(yù)算值則繼續(xù)運(yùn)行

4p1,p2=random positions inssubjected to selection criteria //s中的隨機(jī)位置以選擇標(biāo)準(zhǔn)為準(zhǔn)，將其賦予p1、p2

5 new=swithp1,p2swapped//p1、p2與s交換賦給best

6 if(new is physically infeasible)

7 continue

8Qnew=QoM(new)

9 if(Qnew≥Qs)

10s=new,Qs=Qnew

11 if(Qnew>Qbest) best=new,Qbest=Qnew

12 else//simulated annealing

13 if(random

14s=new,Qs=Qnew

15 return best//返回值

通過仿真實(shí)驗(yàn)結(jié)果的展示，圖1中曲線顯然表明，通過2次不同的實(shí)驗(yàn)，可看出曲線的波動(dòng)以及走勢(shì)部分重合和相似，它們的曲線部分也存在重合的波動(dòng)情況。同時(shí)波動(dòng)過程會(huì)因每個(gè)傳感節(jié)點(diǎn)放置位置和鏈接路線的長(zhǎng)短不同而不同，因此會(huì)存在一些差別。

圖1 模擬結(jié)果

QoM作為比例份額pi/qi的函數(shù)[19]，表示無線傳感網(wǎng)絡(luò)監(jiān)測(cè)事件的時(shí)間變化，其中事件的觀察時(shí)間隨著事件的持續(xù)時(shí)間的延長(zhǎng)而增加，因此當(dāng)QoM更高時(shí)指數(shù)事件動(dòng)態(tài)的λ較小。從圖2中也可以展示，在比例份額中，可以直觀地得出QoM呈現(xiàn)的曲線不是線性的，這意味著細(xì)粒度間的公平性將得到改善[20]。正如前面所解釋的，QoM隨著λ的減少而增加。此外，QoM收斂到最大值1，即比例份額p/q收斂到0和∞。實(shí)驗(yàn)結(jié)果表明了本文算法在周期性調(diào)度中的優(yōu)化性能。

圖2 實(shí)驗(yàn)結(jié)果(QoM最終接近1)

4 結(jié)束語

本文在研究過程中運(yùn)用了統(tǒng)計(jì)相關(guān)知識(shí)，通過廣泛的分析來了解無線傳感器覆蓋的QoM特性[21]。結(jié)果表明，模擬退火算法能夠有效地計(jì)算出一個(gè)周期調(diào)度幾乎是最大的，最終達(dá)到覆蓋優(yōu)化以及網(wǎng)絡(luò)覆蓋最大化的目的。今后，將進(jìn)一步地研究其他多種分布未知參數(shù)的情況下，不局限于只服從指數(shù)分布的參數(shù)情況，全面地提出更優(yōu)的算法，來解決無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化問題，達(dá)到更好的覆蓋率，最終實(shí)現(xiàn)網(wǎng)絡(luò)壽命最大化。