基于概率感知模型的N段有向覆蓋與K重全向覆蓋研究

摘 要： 針對(duì)無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的概率感知模型，在滿足覆蓋要求的條件下，給出了傳感器節(jié)點(diǎn)工作在有向感知模型下的分段數(shù)N與全向感知模型下的覆蓋重?cái)?shù)K之間的關(guān)系表達(dá)式。之后加入時(shí)間積累因素，給出了時(shí)間m、分段數(shù)N與覆蓋重?cái)?shù)K的表達(dá)式?；谝陨涎芯浚梢詫⒏怕矢兄Ｐ拖碌挠邢蚋兄采w問題轉(zhuǎn)化為求取全向感知下的覆蓋重?cái)?shù)問題。

關(guān)鍵詞： N段有向； K重覆蓋； 概率感知模型； 覆蓋要求

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）16?0001?04

無線傳感器網(wǎng)絡(luò)[1?5]的冗余性很大，即網(wǎng)絡(luò)布置的傳感器節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)大于網(wǎng)絡(luò)滿足應(yīng)用需求條件下所需要的節(jié)點(diǎn)數(shù)。如何從全部網(wǎng)絡(luò)節(jié)點(diǎn)中選出滿足感知需求的工作節(jié)點(diǎn)集合，是無線傳感器網(wǎng)絡(luò)的覆蓋性所要解決的問題。依據(jù)節(jié)點(diǎn)感知范圍的不同，可分為全向覆蓋和有向覆蓋[6]。目前全向感知模型覆蓋方面的研究[7?10]已經(jīng)很多，本文致力于用全向覆蓋的方法解決有向覆蓋的問題，力圖建立起兩者之間的相互關(guān)系。

1 問題提出

在節(jié)點(diǎn)為概率感知模型的前提下，假設(shè)節(jié)點(diǎn)工作為有向感知，即節(jié)點(diǎn)的視場(chǎng)范圍為[θ]且以一定的角速度[ω]周期掃描。相比較于全向感知，節(jié)點(diǎn)的感知范圍被分為[N=2πθ]段，任意時(shí)刻只能工作在其中一段，稱之為[N]段有向感知。直接進(jìn)行有向覆蓋研究時(shí)存在的節(jié)點(diǎn)扇形感知區(qū)域模型較復(fù)雜、相位無規(guī)則性等問題，本文旨在尋找分段數(shù)[N]與假設(shè)節(jié)點(diǎn)工作在全向感知下覆蓋重?cái)?shù)[K]的相互關(guān)系；從而，在已知覆蓋要求[σ]以及分段數(shù)[N]的前提下，將[N]段有向感知下的單重覆蓋問題，轉(zhuǎn)化為求取節(jié)點(diǎn)在全向感知下的最小覆蓋重?cái)?shù)[K]的問題。

2 [N]段有向覆蓋與[K]重全向覆蓋的關(guān)系

概率感知模型的思想就是節(jié)點(diǎn)感知到目標(biāo)的能力隨兩者之間距離的增大而衰減。對(duì)此，學(xué)術(shù)界目前有兩種比較流行的表示方法[11]。因?yàn)楸疚闹胁粻砍兜骄唧w的感知模型細(xì)節(jié)內(nèi)容，因此在這里不進(jìn)行詳述。并假設(shè)全向條件下的[K]重覆蓋，采用理想情況下區(qū)域中所有點(diǎn)均且僅被[K]個(gè)節(jié)點(diǎn)集合分別單重覆蓋。

2.1 不考慮時(shí)間積累的情況

定理1：概率感知模型下，節(jié)點(diǎn)在有向感知中以恒定角速度[ω]及恒定視場(chǎng)范圍[θ]進(jìn)行周期掃描的情況下，任意一點(diǎn)[Oxi，yi]在有向模型下的感知概率[Pi′=1NPi]。其中：[Pi]為該點(diǎn)在全向模型下的被感知概率；[N=2πθ]。

證明：在角速度[ω]恒定不變的情況下節(jié)點(diǎn)掃描一周所需時(shí)間[T]為：

[T=2πω] （1）

而節(jié)點(diǎn)可以感知到點(diǎn)[Oxi，yi]的區(qū)域?yàn)閇θ=2πN]，掃描過該區(qū)域所需的時(shí)間[t]為：

[t=2πNω] （2）

聯(lián)立式（1）、式（2），可以得到點(diǎn)[Oxi，yi]被節(jié)點(diǎn)在有向模型下感知到的概率[Pi′]為：

[Pi′=tTPi=1NPi] （3）

得證。

對(duì)于區(qū)域內(nèi)任意一點(diǎn)[Oxi，yi]，根據(jù)假設(shè)必存在[K]個(gè)節(jié)點(diǎn)集合分別對(duì)其滿足單重覆蓋，當(dāng)傳感器節(jié)點(diǎn)由全向感知變?yōu)橛邢蚋兄獣r(shí)，根據(jù)定理1，任意一個(gè)節(jié)點(diǎn)集[Ui]中的任意一個(gè)節(jié)點(diǎn)[Uij]可以感知到該點(diǎn)的概率[Pi′j]變?yōu)椋?/p>

[Pi′j=1NPij] （4）

式中：[Ui]為可以覆蓋到該點(diǎn)[Oxi，yi]的[K]個(gè)節(jié)點(diǎn)集合中的第[i]個(gè)節(jié)點(diǎn)集，[i=1，2，…，K]；[Uij]為節(jié)點(diǎn)集[Ui]中的第[j]個(gè)節(jié)點(diǎn)，[j=1，2，3，…]；[Pij]為節(jié)點(diǎn)集[Ui]中的第[j]個(gè)節(jié)點(diǎn)[Uij]對(duì)該點(diǎn)[Oxi，yi]在全向條件下的覆蓋概率；[Pi′j]為節(jié)點(diǎn)集[Ui]中的第[j]個(gè)節(jié)點(diǎn)[Uij]對(duì)該點(diǎn)[Oxi，yi]在[N]段有向條件下的覆蓋概率。

而點(diǎn)[Oxi，yi]被節(jié)點(diǎn)集[Ui]全向條件下覆蓋的聯(lián)合概率[PiOxi，yi]為：

[PiOxi，yi=1-j=1，2，3，…1-Pij] （5）

點(diǎn)[Oxi，yi]被節(jié)點(diǎn)集[Ui]在[N]段有向條件下覆蓋的聯(lián)合概率[Pi′Oxi，yi]為：

[Pi′Oxi，yi=1-j=1，2，3，…1-Pi′j =1-j=1，2，3，…1-1NPij] （6）

則該點(diǎn)被[K]個(gè)節(jié)點(diǎn)集[Ui]（i=1，2，…，K）在[N]段有向條件下共同作用覆蓋的總聯(lián)合概率[POxi，yi]為：

[POxi，yi=1-i=1，2，…，K1-Pi′Oxi，yi =1-j=1，2，3，…1-1NP1j?j=1，2，3，…1-1NP1j… j=1，2，3，…1-1NPKj] （7）

而根據(jù)已知條件，任何一個(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]都可分別滿足對(duì)點(diǎn)[Oxi，yi]的覆蓋要求，即[PiOxi，yi≥σ]，根據(jù)式（5），得到：

[1-j=1，2，3，…1-Pij≥σ] （8）

而最終目的是，在覆蓋要求[σ]已知情況下，確定有向感知模型下分段數(shù)[N]與覆蓋重?cái)?shù)[K]的關(guān)系，使得任意一點(diǎn)[Oxi，yi]處的[POxi，yi]均滿足：

[POxi，yi≥σ] （9）

很明顯，最終目的就是式（7）與式（9）的聯(lián)立，通過分析可以發(fā)現(xiàn)因?yàn)槭孪炔恢烂恳粋€(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]中節(jié)點(diǎn)的具體個(gè)數(shù)，因此難以表示出分段數(shù)[N]與覆蓋重?cái)?shù)[K]之間的明確表達(dá)式。這里采用一種近似，即對(duì)于任何一個(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]而言，其節(jié)點(diǎn)集內(nèi)所有節(jié)點(diǎn)在[N]段有向感知下對(duì)點(diǎn)[Oxi，yi]的聯(lián)合覆蓋概率均大于覆蓋要求[σ]的[1N]倍。

定理2：當(dāng)不等式[1-j=1，2，3，…1-Pij≥σ]成立時(shí)，有[1-j=1，2，3，…1-1NPij≥σN]。其中，[Ui]為可以覆蓋到點(diǎn)[Oxi，yi]的[K]個(gè)節(jié)點(diǎn)集合中的第[i]個(gè)節(jié)點(diǎn)集[i=1，2，…，K]；[Uij]為節(jié)點(diǎn)集[Ui]中的第[j]個(gè)節(jié)點(diǎn)[j=1，2，3，…]；[Pij]為節(jié)點(diǎn)集[Ui]中的第[j]個(gè)節(jié)點(diǎn)[Uij]對(duì)該點(diǎn)[Oxi，yi]在全向條件下的覆蓋概率；[σ]為覆蓋要求，滿足[0<σ<1]。

證明：上式等價(jià)式為當(dāng)[j=1，2，3，…1-Pij≤1-σ]時(shí)， [j=1，2，3，…1-1NPij≤1-σN]成立。

利用數(shù)學(xué)歸納法來證明，當(dāng)節(jié)點(diǎn)集中節(jié)點(diǎn)個(gè)數(shù)為1時(shí)，即[1-Pi1≤1-σ]時(shí)，顯然[1-1NPi1≤1-σN]成立。當(dāng)節(jié)點(diǎn)個(gè)數(shù)為2時(shí)，即[1-Pi1?1-Pi2≤1-σ]時(shí)，易證不等式[1-1NPi1?1-1NPi2≤1-σN]成立。假設(shè)節(jié)點(diǎn)個(gè)數(shù)為[t]時(shí)， 并且[j=1，2，3，…，t1-Pij≤1-σ，] 不等式[j=1，2，3，…，t1-1NPij≤1-σN]成立。

現(xiàn)證節(jié)點(diǎn)個(gè)數(shù)為[t+1]，[j=1，2，…，t，t+11-Pij≤1-σ]成立時(shí)，[j=1，2，…，t，t+11-1NPij≤1-σN]同樣成立。

具體證明如下：

[j=1，2，…，t，t+11-Pij=j=1，2，…，t1-Pij?1-Pit+1]

而根據(jù)已知條件：

[j=1，2，…，t，t+11-Pij≤1-σ]

則：

[j=1，2，…，t1-Pij≤1-σ1-Pit+1=1-σ-Pit+11-Pit+1]

令：

[σ′=σ-Pit+11-Pit+1]

則根據(jù)假設(shè)，有：

[j=1，2，…，t1-1NPij≤1-σ′N=1-1Nσ-Pit+11-Pit+1]

則：

[j=1，2，…，t，t+11-1NPij=j=1，2，…，t1-1NPij?1-1NPit+1 ≤1-1Nσ-Pit+11-Pit+1?1-1NPit+1]

將上式化簡(jiǎn)可得[j=1，2，…，t，t+11-Pij≤1-σ]同樣成立。

證畢。

根據(jù)定理2，用[σN]來代替節(jié)點(diǎn)集[Ui]在[N]段有向感知下對(duì)點(diǎn)[Oxi，yi]的聯(lián)合覆蓋概率，通過模擬仿真發(fā)現(xiàn)替代概率[σN]比較接近實(shí)際概率，與簡(jiǎn)化計(jì)算比較而言，其誤差完全可以接受。則式（6）可以簡(jiǎn)化為：

[Pi′Oxi，yi=1-j=1，2，3…1-Pi′j =1-j=1，2，3…1-1NPij≥σN] （10）

式（10）的等價(jià)式為：

[j=1，2，3…1-1NPij≤1-σN] （11）

根據(jù)式（11）中的結(jié)論，可以對(duì)式（7）進(jìn)行簡(jiǎn)化便可得到：

[POxi，yi≥1-1-σNK] （12）

將式（9）與式（12）聯(lián)立，即可得到分段數(shù)[N]、覆蓋重?cái)?shù)[K]、覆蓋要求[σ]三者之間的關(guān)系表達(dá)式為：

[1-1-σNK≥σ] （13）

2.2 考慮時(shí)間積累的情況

加入時(shí)間積累的因素，節(jié)點(diǎn)以恒定角速度[ω]及恒定視場(chǎng)范圍[θ]進(jìn)行周期掃描。即：給定覆蓋要求[σ]、有向分段數(shù)[N]（其中[N=2πθ]）、掃描角速度[ω]的前提下，求取全向條件下最小覆蓋重?cái)?shù)[K]的值，以保證[m]時(shí)間內(nèi)可以檢測(cè)到目標(biāo)。在此情況下，需要研究的是時(shí)間[m]、覆蓋重?cái)?shù)[K、]分段數(shù)[N]、覆蓋要求[σ]、角速度[ω]之間的關(guān)系。顯然，在時(shí)間起始時(shí)刻起，傳感器節(jié)點(diǎn)就已經(jīng)有[θ=2πN]范圍的覆蓋區(qū)域，則如果可以滿足在[m]時(shí)間內(nèi)，節(jié)點(diǎn)掃描過的區(qū)域弧度可以超過或者達(dá)到[N-12πN]，即[mω≥N-12πN]時(shí)，滿足對(duì)整個(gè)圓盤區(qū)域覆蓋一次，此情況下，覆蓋重?cái)?shù)[K]值取1即可達(dá)到覆蓋要求。故節(jié)點(diǎn)[Uij]對(duì)點(diǎn)[Oxi，yi]的覆蓋概率[Pi′j]為[Pi′j=Pij， m≥2πω-2πNωmω+2πNPij2π， m<2πω-2πNω] （14）

則點(diǎn)[Oxi，yi]在[m]時(shí)間內(nèi)被全向條件下感知到該點(diǎn)的任意一個(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]感知到的聯(lián)合概率為：

[Pi′Oxi，yi≥σ， m>2πω-2πNωPi′Oxi，yi=1-j=1，2，3，…1-mω+2πNPij2π， m<2πω-2πNω] （15）

則點(diǎn)[Oxi，yi]在[m]時(shí)間內(nèi)被全向條件下感知到該點(diǎn)的[K]個(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]感知到的總聯(lián)合概率[POxi，yi]為：

[POxi，yi≥σ， m≥2πω-2πNωPOxi，yi=1-i=1，2，…，K1-Pi′Oxi，yi m<2πω-2πNω，] （16）

針對(duì)[m<2πω-2πNω]的情況時(shí)，此時(shí)有：

[Pi′Oxi，yi=1-j=1，2，3，…1-mω+2πNPij2π] （17）

令[N′=2πmω+2πN]，則根據(jù)定理2的結(jié)論，任意一個(gè)節(jié)點(diǎn)集[Ui][i=1，2，…，K]在有向感知下的覆蓋概率：

[Pi′Oxi，yi=1-j=1，2，3，…1-1N′Pij ≥σN′=mω+2πNσ2π] （18）

根據(jù)式（18），點(diǎn)[Oxi，yi]在[m]時(shí)間內(nèi)被[K]個(gè)節(jié)點(diǎn)集[Ui]感知到的總聯(lián)合概率[POxi，yi]為：

[POxi，yi≥σ， m≥2πω-2πNωPOxi，yi≥1-1-mω+2πNσ2πK， m<2πω-2πNω] （19）

因此，覆蓋重?cái)?shù)[K]、分段數(shù)[N]、覆蓋要求[σ]、角速度[ω]、時(shí)間[m]之間的關(guān)系是：

[當(dāng)m≥2πω-2πNω 時(shí)]，最小覆蓋重?cái)?shù)[K]取1即可；[當(dāng)m<2πω-2πNω 時(shí)]，必須要保證不等式[1-1-mω+2πNσ2πK≥σ]成立才可被覆蓋。

3 仿真分析

節(jié)點(diǎn)在任意時(shí)刻下，分別采用布爾感知模型及概率感知模型，覆蓋要求[σ]已知情況下分段數(shù)[N]與覆蓋重?cái)?shù)[K]的關(guān)系。分別取[σ]=0.9以及0.95兩種情況下，分段數(shù)[N]分別從2逐一遞增到20，觀察覆蓋重?cái)?shù)[K]的變化如圖1所示。從圖1可以看出，概率感知模型下，在覆蓋要求已知前提下，覆蓋重?cái)?shù)[K]隨著分段數(shù)[N]的增加而增加，且覆蓋重?cái)?shù)[K]的增加趨勢(shì)要快過分段數(shù)[N]的增加趨勢(shì)。在覆蓋要求相等前提下，布爾感知模型的情況所需的最小覆蓋重?cái)?shù)都小于概率感知模型下的最小覆蓋重?cái)?shù)，這也正符合布爾感知模型就是概率感知模型中概率為1時(shí)的最理想情況。同樣在節(jié)點(diǎn)感知模型相等前提下，覆蓋要求低的情況所需的最小覆蓋重?cái)?shù)都小于覆蓋要求高的最小覆蓋重?cái)?shù)。

其次，考慮時(shí)間因素，在一定的時(shí)間積累下，同樣是分別采用布爾感知模型和概率感知模型，覆蓋要求[σ]已知情況下的分段數(shù)[N]與覆蓋重?cái)?shù)[K]的關(guān)系。

取角速度[ω=π12][s-1]，分別取時(shí)間[m]為1 s，2 s，3 s，12 s，的情況，當(dāng)覆蓋要求[σ]=0.9以及0.95兩種情況，分段數(shù)[N]分別從2逐一遞增到20，觀察覆蓋重?cái)?shù)[K]的變化如圖2所示。

通過與圖1進(jìn)行對(duì)比，可以發(fā)現(xiàn)，因?yàn)橛辛藭r(shí)間上的積累，導(dǎo)致檢測(cè)概率更大，從而同等條件下，在滿足覆蓋要求的情況下，考慮時(shí)間積累所需的覆蓋重?cái)?shù)[K]比任意時(shí)刻所需的覆蓋重?cái)?shù)[K]的值要小。并且，隨著時(shí)間[m]的積累，其所需的覆蓋重?cái)?shù)[K]不斷減小，當(dāng)時(shí)間足夠長(zhǎng)時(shí)，肯定可以達(dá)到單重覆蓋即[K]=1即可滿足條件的情況。而且同樣可以發(fā)現(xiàn)，同等條件下，布爾感知模型的情況會(huì)比概率感知模型好一些，其所需的最小覆蓋重?cái)?shù)一般都小于概率感知模型下的最小覆蓋重?cái)?shù)。

4 結(jié) 語

本文詳細(xì)分析了在概率感知模型下，滿足覆蓋要求[σ]前提下，節(jié)點(diǎn)為有向感知模型對(duì)應(yīng)的分段數(shù)[N]與全向感知模型下的覆蓋重?cái)?shù)[K]之間的關(guān)系。分別給出了不考慮時(shí)間積累與考慮時(shí)間積累時(shí)有向分段數(shù)[N]與全向覆蓋重?cái)?shù)[K]之間的關(guān)系表達(dá)式，從而將概率感知模型下難以直接求解的有向感知覆蓋問題轉(zhuǎn)化為求取節(jié)點(diǎn)在虛擬全向感知下的覆蓋重?cái)?shù)問題。

參考文獻(xiàn)

[1] 孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] 衣曉，劉瑜.無線傳感器網(wǎng)絡(luò)Range?free自身定位算法仿真分析[J].海軍航空工程學(xué)院學(xué)報(bào)，2009，24（4）：369?375.

[3] 衣曉，鄧露，劉瑜.基于基站劃分網(wǎng)格的無線傳感器網(wǎng)絡(luò)分簇算法[J].控制理論與應(yīng)用，2012，29（2）：145?150.

[4] 劉瑜.一種高密度無線傳感器網(wǎng)絡(luò)分簇定位算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（8）：1581?1586.

[5] 劉瑜.基于分治求精的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（9）：1906?1913.

[6] 陶丹，馬華東.有向傳感器網(wǎng)絡(luò)覆蓋控制算法[J].軟件學(xué)報(bào)，2011，22（10）：59?76.

[7] HE X， YANG H ， GUI X L. The maximum coverage set calculated algorithm for WSN area coverage [J]. Journal of Networks， 2010， 5（6）： 650?657.

[8] SU Y X， WANG D. An energy?balanced probability coverage algorithm for WSN [J]. Advanced Materials Research， 2011， 403： 1420?1423.

[9] 權(quán)建國(guó)，王國(guó)軍，邢蕭飛.無線傳感器網(wǎng)絡(luò)中基于異構(gòu)節(jié)點(diǎn)的覆蓋控制算法[J].傳感技術(shù)學(xué)報(bào)，2010（5）：863?867.

[10] 陶洋，曾曉玲，羅衛(wèi).無線傳感器網(wǎng)絡(luò)中覆蓋控制算法研究及改進(jìn)[J].計(jì)算機(jī)應(yīng)用，2010，30（6）：1459?1462.

[11] 常光強(qiáng).無線傳感器網(wǎng)絡(luò)中連通與覆蓋控制算法研究[D].長(zhǎng)沙：中南大學(xué)，2011.