基于區(qū)域內(nèi)隨機(jī)喚醒機(jī)制的WSN覆蓋控制方法

鄧鑫，張樂君

(哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001)

無線傳感器網(wǎng)絡(luò)(WSN)是由大量微型傳感器節(jié)點構(gòu)成的，這些微型傳感器結(jié)構(gòu)簡單，計算能力和電池能量等資源有限。因此通常采用節(jié)點高密度部署的方法(20 node/m3)［1］來提高網(wǎng)絡(luò)的整體工作性能、延長網(wǎng)絡(luò)生命周期。如果這種高密度部署的傳感器節(jié)點同時工作，勢必會導(dǎo)致無線信息干擾、能量耗費(fèi)和信息大量冗余等問題，所以節(jié)點調(diào)度技術(shù)就成為了延長網(wǎng)絡(luò)工作時間、保證網(wǎng)絡(luò)工作質(zhì)量的重要技術(shù)之一。節(jié)點調(diào)度技術(shù)是指通過調(diào)度方法合理轉(zhuǎn)換節(jié)點狀態(tài)，以達(dá)到在保證網(wǎng)絡(luò)需求覆蓋質(zhì)量(QoC)的前提下節(jié)省節(jié)點能量，延長網(wǎng)絡(luò)生命周期的目的。

本文利用傳感器節(jié)點可以通過控制功率來調(diào)整通訊半徑的特性，給出了控制工作節(jié)點間相對距離的方法及網(wǎng)絡(luò)覆蓋度與相對距離的關(guān)系，并在此基礎(chǔ)上提出了基于限定區(qū)域內(nèi)隨機(jī)喚醒機(jī)制的WSN覆蓋控制協(xié)議(random wake-up mechanism within a limited region，RWMLR)。

目前針對傳感器網(wǎng)絡(luò)覆蓋控制的問題已取得了一定的進(jìn)展。Hefeeda等利用了幾何圓盤覆蓋的特性，針對圓盤感知模型提出了基于VC維和ξ-net的隨機(jī)選擇活躍節(jié)點的方法，并給出了該方法的集中式和分布式實現(xiàn)方案 RKC 和 DRKC［2］。Zou 等［3］提出了基于蟻群算法的傳感器網(wǎng)絡(luò)的節(jié)能覆蓋算法。孟凡治等［4］提出了的基于聯(lián)合感知模型的連通覆蓋控制協(xié)議，該協(xié)議分析了在節(jié)點隨機(jī)部署方式下，網(wǎng)絡(luò)覆蓋質(zhì)量和網(wǎng)絡(luò)連通性與工作節(jié)點個數(shù)、監(jiān)測區(qū)域面積和節(jié)點性能參數(shù)的關(guān)系。Zhang等［5］針對三維區(qū)域的覆蓋控制問題提出了基于概率模型的覆蓋控制算法，該算法能達(dá)到覆蓋度要求，但是在該算法中傳感器節(jié)點的能量消耗較大。王換招等［6］分析了傳感器感知半徑服從正態(tài)分布的無線傳感器網(wǎng)絡(luò)冗余度計算模型，以及保證網(wǎng)絡(luò)覆蓋質(zhì)量所需最少工作節(jié)點的計算模型，并且在此基礎(chǔ)上提出了一種高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議(energy efficient coverage conserving protocol，EECCP)。李超良等［7］提出了一種節(jié)點覆蓋率和連通率的計算方法，該方法能描述節(jié)點感知半徑、檢測區(qū)域邊長以及節(jié)點數(shù)量與覆蓋率、網(wǎng)絡(luò)連通率之間的關(guān)系，計算所需節(jié)點數(shù)量，該方法考慮檢測邊界對覆蓋的影響。文獻(xiàn)［8］提出了一種節(jié)點判定是否為k重覆蓋的算法，并且提出了CCP(coverage configuration protocol)協(xié)議，該協(xié)議可以根據(jù)應(yīng)用生成不同覆蓋度的網(wǎng)絡(luò)，并且在文中給出了通訊半徑大于等于感知半徑2倍時，能保證網(wǎng)絡(luò)的連通性。Zhou等［9］提出了基于多目標(biāo)優(yōu)化的能量平衡消耗的傳感器網(wǎng)絡(luò)覆蓋控制算法。

上述研究都是在節(jié)點的通訊半徑固定的基礎(chǔ)上展開的，而在文獻(xiàn)［10］中指出傳感器節(jié)點可以通過控制發(fā)送功率來改變其通訊半徑。本文針對這種由可變通訊半徑的傳感器節(jié)點所組成的高密度均勻部署的傳感器網(wǎng)絡(luò)的覆蓋控制問題進(jìn)行研究。

1 網(wǎng)絡(luò)模型和相關(guān)理論

1.1 網(wǎng)絡(luò)模型及問題描述

假設(shè)傳感器網(wǎng)絡(luò)具有如下性質(zhì):

1)網(wǎng)絡(luò)中所有節(jié)點都均勻的隨機(jī)分布在一個平面區(qū)域Z內(nèi)，并且密度足夠大(20 nodes/m2)。

2)每個傳感器節(jié)點的感知區(qū)域為圓形，即若感知半徑為RS，其感知區(qū)域面積S=πRs2。

3)節(jié)點采用布爾感知模型，即在感知范圍內(nèi)的區(qū)域都能被傳感器所感知，屬于有效感知區(qū)域。

4)節(jié)點通訊半徑可通過調(diào)節(jié)發(fā)射功率來放大或縮小，且網(wǎng)絡(luò)工作時通訊半徑大小與節(jié)點感知半徑大小關(guān)系為Rc≥2Rs，以保證網(wǎng)絡(luò)連通性［8］。

5)所有傳感器感知半徑相同，能耗模型相同，無GPS系統(tǒng)。

本文要解決在上述網(wǎng)絡(luò)模型中，如何通過調(diào)度節(jié)點使得網(wǎng)絡(luò)在達(dá)到要求覆蓋度的前提下，生成覆蓋區(qū)域Z的最小節(jié)點集，從而延長網(wǎng)絡(luò)工作時間。

1.2 相關(guān)定義

定義1 鄰居節(jié)點集:對于任意節(jié)點i∈?，其鄰居節(jié)點集的定義為V(i)={j∈?|d(i，j)＜Rc，i≠j}，其中?為部署在區(qū)域Z中所有節(jié)點的集合，d(i，j)表示節(jié)點i和節(jié)點j之間的物理距離，Rc表示節(jié)點i的通訊半徑。

定義2 冗余覆蓋面積:對于全體節(jié)點集合中任意工作節(jié)點i，它與其鄰居節(jié)點集中任意工作節(jié)點感知區(qū)域重合部分的面積即為冗余覆蓋面積Sr=Si∩Sj(j∈V(i))，其中Si表示節(jié)點i的感知區(qū)域面積，Sj表示節(jié)點j的感知區(qū)域面積。

定義3 網(wǎng)絡(luò)覆蓋度:網(wǎng)絡(luò)中所有工作節(jié)點形成的監(jiān)測區(qū)域總面積占被監(jiān)測區(qū)域Z面積的百分比，稱為網(wǎng)絡(luò)的覆蓋度。即

定義4 覆蓋目標(biāo)區(qū)域的最小節(jié)點集合:由文獻(xiàn)［11］可知完全覆蓋特定區(qū)域的最少圓集合的模型如圖1所示。

圖1 覆蓋區(qū)域最小圓集合模型Fig.1 Minimum circle of coverage set model

在感知半徑RS相同的條件下，傳感器節(jié)點間距離為，即每個節(jié)點有6個鄰居節(jié)點時，區(qū)域覆蓋度為100%且所生成的區(qū)域覆蓋圓集為最少覆蓋圓集，其對應(yīng)的傳感器節(jié)點集為覆蓋區(qū)域的最少節(jié)點集。

定義5 限定區(qū)域:對于任意節(jié)點i∈?，其工作時產(chǎn)生的外點限定區(qū)域為S(K)={K|ε1Rs＜d(K，i)≤ε2Rs}，內(nèi)點限定區(qū)域為S(K)={K|d(K，i)≤ε1Rs}，其中 ε1、ε2為傳感器通訊半徑參數(shù)，且1.5 ≤ε1＜ε2≤2，如圖 2所示。

圖2 限定區(qū)域示意圖Fig.2 Limited region schematic

2 網(wǎng)絡(luò)覆蓋質(zhì)量分析

引理1若2個距離為εRs的鄰居節(jié)點產(chǎn)生的冗余覆蓋面積為Sr，那么

式中:Rs為節(jié)點的感知半徑，ε為通訊半徑參數(shù)，并且ε≤2。

證明:如圖3所示，陰影部分為傳感器節(jié)點O1，O2所產(chǎn)生的冗余面積為Sr，O1、O2之間的物理距離為 εRs。

則Sr=2*(S扇ABO2－ SΔABO2)

證畢。

圖3 節(jié)點冗余面積圖Fig.3 Redundant area of working nodes

定理1設(shè)網(wǎng)絡(luò)最低復(fù)雜度要求為k，達(dá)到最低復(fù)雜度要求時，鄰居節(jié)點距離均為εRs，則

式中:ε為通訊半徑參數(shù)。

證明:若使網(wǎng)絡(luò)達(dá)到最低復(fù)雜度要求則節(jié)點間的距離達(dá)到最遠(yuǎn)距離，即εRs。如圖4所示A、B、C為網(wǎng)絡(luò)中3個工作節(jié)點，且任意兩個不同節(jié)點間的物理距離為εRs，圖中虛線部分區(qū)域為節(jié)點間的冗余覆蓋區(qū)域，網(wǎng)格部分區(qū)域為覆蓋盲區(qū)。

圖4 最壞覆蓋度示意圖Fig.4 Worst coverage degree schematic

則3個工作節(jié)點對△ABC區(qū)域的覆蓋度為:

∵ △ABC為等邊三角形，且邊長為εRs

又∵式(1)

證畢。

由式(2)的函數(shù)圖象可知k與ε的關(guān)系如圖5所示。由式(2)可以得出，當(dāng)通訊半徑參數(shù)為2時網(wǎng)絡(luò)的覆蓋度達(dá)到最低點，約為90.8%。并且從圖中可以看出網(wǎng)絡(luò)覆蓋度隨通訊半徑參數(shù)的增大而降低。因此將網(wǎng)絡(luò)要求覆蓋度視為網(wǎng)絡(luò)最壞覆蓋度來計算網(wǎng)絡(luò)通訊半徑參數(shù)，然后按照RWMLR協(xié)議所生成的傳感器網(wǎng)絡(luò)覆蓋都不小于要求的網(wǎng)絡(luò)覆蓋度。

圖5 最壞覆蓋度與通訊半徑參數(shù)關(guān)系Fig.5 Relationship between worst coverage degree and transmission parameter

3 RWMLR協(xié)議

由定義4可知，若要在保證不同的覆蓋質(zhì)量的前提下利用最少的節(jié)點生成網(wǎng)絡(luò)，則節(jié)點間的物理距離應(yīng)該保持在，左右。由定理1可知，網(wǎng)絡(luò)覆蓋度僅與通訊半徑參數(shù)有關(guān)，因此本協(xié)議的目的是根據(jù)網(wǎng)絡(luò)需求的覆蓋質(zhì)量，合理的調(diào)整通訊半徑參數(shù)，使生成的網(wǎng)絡(luò)中工作節(jié)點保持合理的物理距離。

3.1 協(xié)議描述

在協(xié)議開始工作前，傳感器節(jié)點根據(jù)覆蓋度要求由式(2)計算出傳感器網(wǎng)絡(luò)達(dá)到最低覆蓋度要求時的通訊半徑參數(shù)。網(wǎng)絡(luò)初始狀態(tài)時所有的傳感器節(jié)點處于休眠狀態(tài)，在網(wǎng)絡(luò)中隨機(jī)選取一個節(jié)點轉(zhuǎn)換為工作狀態(tài)。

開始工作的節(jié)點會根據(jù)要求覆蓋度計算出的通訊半徑參數(shù)，并以ε1Rs和ε2Rs為通訊半徑兩次廣播Hello包，對其鄰居節(jié)點區(qū)域進(jìn)行內(nèi)點區(qū)域和外點區(qū)域的劃分。Hello包中包含3個域:包類型域，節(jié)點編號域和節(jié)點狀態(tài)域。收到兩個Hello包的區(qū)域為內(nèi)點區(qū)域，收到一個Hello包的區(qū)域為外點區(qū)域。因此外點與工作節(jié)點間的距離被限制為d∈［ε1Rs，ε2Rs］。由定理1可知網(wǎng)絡(luò)的最差覆蓋率只與通訊半徑參數(shù)有關(guān)，因此在外點區(qū)域內(nèi)喚醒節(jié)點而產(chǎn)生的覆蓋度是可控的。工作節(jié)點會根據(jù)節(jié)點的優(yōu)先級在外點區(qū)域內(nèi)喚醒休眠節(jié)點。當(dāng)工作節(jié)點的能量即將耗盡時，工作節(jié)點會根據(jù)節(jié)點優(yōu)先級在內(nèi)點區(qū)域內(nèi)喚醒節(jié)點。

3.2 節(jié)點優(yōu)先級確定

節(jié)點初始優(yōu)先級為零，若i工作節(jié)點，則i的外點集中的節(jié)點優(yōu)先級加1，內(nèi)點集中的節(jié)點優(yōu)先級減1。如圖2所示陰影部分區(qū)域中的節(jié)點優(yōu)先級為1，非陰影部分的節(jié)點優(yōu)先級為 －1。

3.3 節(jié)點狀態(tài)轉(zhuǎn)換模型

本協(xié)議分為兩個階段，初始化階段和穩(wěn)定階段。網(wǎng)絡(luò)中每個節(jié)點都有6種狀態(tài):選舉狀態(tài)(ELECTION)，工作狀態(tài)(WORK)，失效狀態(tài)(DEAD)，休眠狀態(tài)(SLEEP)，預(yù)工作狀態(tài)(PRE_WORK)，預(yù)睡眠狀態(tài)(PRE_SLEEP)。

初始化階段中，被選定的節(jié)點開始工作時會觸發(fā)其外點限定區(qū)域內(nèi)的節(jié)點從SLEEP狀態(tài)轉(zhuǎn)換為ELECTION狀態(tài)。ELECTION狀態(tài)的節(jié)點向觸發(fā)其狀態(tài)轉(zhuǎn)換的工作節(jié)點發(fā)選舉消息，工作節(jié)點選擇優(yōu)先級高的節(jié)點并使其轉(zhuǎn)換為PRE_WORK狀態(tài)，優(yōu)先級低的節(jié)點轉(zhuǎn)為SLEEP狀態(tài)。處于PRE_WORK狀態(tài)的節(jié)點等待時間T，若在此時間段內(nèi)被選為工作節(jié)點則節(jié)點轉(zhuǎn)換為WORK狀態(tài);否則將節(jié)點狀態(tài)轉(zhuǎn)換為SLEEP狀態(tài)。

在穩(wěn)定階段中所有工作節(jié)點的選取發(fā)生在有節(jié)點失效的區(qū)域。當(dāng)節(jié)點即將失效時會觸發(fā)其內(nèi)點限定區(qū)域中的節(jié)點轉(zhuǎn)為ELECTION狀態(tài)，剩余過程與初始化階段節(jié)點狀態(tài)轉(zhuǎn)移相同。因為節(jié)點失效與新節(jié)點選取都是在小范圍區(qū)域內(nèi)進(jìn)行，從而不影響整個傳感器網(wǎng)絡(luò)的感知工作。網(wǎng)絡(luò)中的狀態(tài)轉(zhuǎn)換如圖6所示。

圖6 網(wǎng)絡(luò)中節(jié)點狀態(tài)轉(zhuǎn)移圖Fig.6 Node state transition diagram

4 RWMLR協(xié)議性能分析

為了檢驗協(xié)議的性能，使用omnet++作為仿真實驗平臺。實驗中監(jiān)控區(qū)域大小為20×20 m2，節(jié)點的能耗模型為文獻(xiàn)［4］中所采用的實驗節(jié)點能耗模型，即發(fā)送接收和休眠狀態(tài)的能耗比例為20∶4∶0.01。

圖7為初始節(jié)點規(guī)模不同的情況下，網(wǎng)絡(luò)的覆蓋質(zhì)量和所要求達(dá)到的覆蓋質(zhì)量之間的關(guān)系?？梢钥闯霰疚乃岢龅膮f(xié)議能夠保證網(wǎng)絡(luò)的覆蓋質(zhì)量高于要求的覆蓋質(zhì)量，由于節(jié)點的通訊參數(shù)是按照所要求的網(wǎng)絡(luò)最低覆蓋度計算出的，因此網(wǎng)絡(luò)實際覆蓋質(zhì)量會略高于所需要的覆蓋質(zhì)量，但是從圖中可以看出隨著要求覆蓋度的增加，本協(xié)議所生成的網(wǎng)絡(luò)覆蓋度與最優(yōu)覆蓋度的差距逐漸減小。

圖7 需求覆蓋質(zhì)量與實際覆蓋質(zhì)量的關(guān)系Fig.7 Relationship between require coverage degree and real coverage degree

圖8 滿足不同的QoC網(wǎng)絡(luò)的工作時間Fig.8 Network working time under different Qocs

如圖8所示為在區(qū)域中部署5 000個節(jié)點時，網(wǎng)絡(luò)在不同的覆蓋質(zhì)量要求下工作的時間，從圖中可以看出在不使用調(diào)度策略時，網(wǎng)絡(luò)中所有的節(jié)點始終工作，并且保證網(wǎng)絡(luò)的覆蓋度始終保持在100%，但是在很短的時間內(nèi)隨著節(jié)點的能量耗盡網(wǎng)絡(luò)的覆蓋度迅速下降;在使用了本協(xié)議調(diào)度節(jié)點后，網(wǎng)絡(luò)中的傳感器節(jié)點輪流工作，降低了冗余覆蓋面積，有效的減少了網(wǎng)絡(luò)中的能量消耗，如圖所示達(dá)到同樣覆蓋度的情況下，網(wǎng)絡(luò)工作時間比不使用調(diào)度策略的工作時間延長了約1.3倍。但是由于網(wǎng)絡(luò)中的節(jié)點是隨機(jī)分布的，不同區(qū)域內(nèi)節(jié)點分布不均勻，覆蓋度并沒有快速下降為0。

為了進(jìn)一步體現(xiàn)本協(xié)議的性能，取不需要地理位置的LDAS［12］協(xié)議作為比較。實驗結(jié)果如圖9、圖10所示。如圖9所示，網(wǎng)絡(luò)中不同時間階段工作節(jié)點數(shù)量LDAS協(xié)議普遍高于本文提出的協(xié)議。由圖10可知其網(wǎng)絡(luò)覆蓋度在達(dá)到要求覆蓋度的同時也比本文提出的協(xié)議高。這是由于LDAS協(xié)議判斷節(jié)點自身冗余度時，沒有考慮到其兩跳鄰居節(jié)點對覆蓋度做的貢獻(xiàn)，因此網(wǎng)絡(luò)中仍然存在許多的冗余節(jié)點。從這兩種協(xié)議的比較中得出RWMLR協(xié)議在保證達(dá)到要求的冗余覆蓋度的同時，有效的減少了網(wǎng)絡(luò)中冗余節(jié)點的數(shù)量，從而延長了網(wǎng)絡(luò)的工作時間。

圖9 工作節(jié)點數(shù)量對比Fig.9 Comparison of the number of working nodes

圖10 獲得網(wǎng)絡(luò)覆蓋度對比Fig.10 Comparison between network coverage degrees

5 結(jié)束語

本文針對通訊半徑可控的傳感器節(jié)點組成的傳感器網(wǎng)絡(luò)覆蓋度進(jìn)行了分析，給出了覆蓋度與通訊半徑參數(shù)之間的關(guān)系，提出了基于限定區(qū)域內(nèi)隨機(jī)喚醒機(jī)制的覆蓋控制方法(RWMLR)。仿真實驗表明，本協(xié)議可以在保證網(wǎng)絡(luò)覆蓋度的前提下，使盡量少的傳感器節(jié)點進(jìn)入工作狀態(tài)，從而減少了網(wǎng)絡(luò)的整體能耗，延長了網(wǎng)絡(luò)生命周期。并通過對比實驗體現(xiàn)出本協(xié)議的優(yōu)越性。

［1］SHIH E，CHO S H，ICKES N，et al.Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks［C］//Proc of the 7th Int＇l Conf on Mobile Computing and Networking(MobiCom).Rome:ACM Press，2001:272-287.

［2］HEFEEDA M.Randomized k-coverage algorithms for dense sensor networks［C］//INFOCOM 26th IEEE International Conference on Computer Communications.Anchorage，AK，2007:2376-2380.

［3］ZOU Ming，ZHANG Ping.A novel energy efficient coverage control in WSNs based on ant colony optimization［C］//2010 International Symposium on Computer，Communication，Control and Automation.Tainan，China，2010:523-527.

［4］孟凡治，王換招，何暉.基于聯(lián)合感知模型的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議［J］.電子學(xué)報，2011，39(4):772-779.MENG Fanzhi，WANG Huanzhao，HE Hui.Connected coverage protocol using cooperative densing model for wireless sensor networks［J］.Acta Electronica Sinica，2011，39(4):772-779.

［5］ZHANG Junqing，WANG Ruchuan.A coverage control algorithm based on probability model for three-dimensional wireless sensor networks［C］//2012 11th International Symposium on Distributed Computing and Applications to Business，Engineering ＆ Science，(s.l.)，2012:169-173.

［6］王換招，孟凡志，李增智.高效節(jié)能的無線傳感器網(wǎng)絡(luò)覆蓋保持協(xié)議［J］.軟件學(xué)報，2010，12(21):3124-3137.WANG Huanzhao，MENG Fanzhi，LI Zengzhi.Energy efficient coverage conserving protocol for wireless sensor networks［J］.Journal of Software，2010，12(21):3124-3137.

［7］李超良，邢蕭飛，劉躍華.一種新型覆蓋連通率計算方法［J］.計算機(jī)應(yīng)用，2011，12(31):3204-2306.LI Chaoliang，XING Xiaofei，LIU Yuehua.New method of calculating coverage and connectivity rate［J］.Journal of Computer Applications，2011，12(31):3204-2306.

［8］XING Guoliang，WANG Xiaorui.Integrated coverage and connectivity configuration for energy conservation in sensor networks［J］.ACM Transactions on Sensor Networks，2005，1(1):36-72.

［9］ZHOU Hui，LIANG Tian.Multiobjective coverage control strategy for energy-efficient wireless sensor networks［J］.International Journal of Distributed Sensor Networks，2012:1-10.

［10］JIANG J R，SUNG T M.Maintaining connected coverage for wireless sensor networks［C］//The 28th International Conference on Distributed Computing Systems Workshops.Beijing，China，2008:297-302.

［11］汪學(xué)清，楊永田.無線傳感器網(wǎng)絡(luò)中連通與覆蓋問題的研究［J］.計算機(jī)工程與應(yīng)用，2006，42(36)，136-139.WANG Xueqing，YANG Yongtian.Research on connectivity and cover age problem of wireless sensor networks［J］.Computer Engineering and Applications，2006，42(36):136-139.

［12］WU K，GAO Y，LI F，et al.Lightweight deployment-aware scheduling for wireless sensor networks［J］.ACM/Kluwer Mobile Networks＆ Applications(MONET)，2005，10(6):837-852.