喻 林，朱曉珺

(1.鄭州財(cái)稅金融職業(yè)學(xué)院 信息技術(shù)系，河南 鄭州 450048；2.鄭州信息科技職業(yè)學(xué)院 信息工程學(xué)院,河南 鄭州 450000)

0 引 言

有向傳感網(wǎng)絡(luò)(Directional Sensor Networks, DSNs )就是利用傳感節(jié)點(diǎn)感知的有向性建立的無(wú)線網(wǎng)絡(luò)[1-3]。在DSNs中，傳感節(jié)點(diǎn)有方向性地感測(cè)環(huán)境數(shù)據(jù)，并將數(shù)據(jù)傳輸至信宿(Sink)。與全向(Omni-directional)傳感節(jié)點(diǎn)不同，有向傳感節(jié)點(diǎn)具有方向性，并且每個(gè)方向的感測(cè)區(qū)域呈扇形狀。DSNs通過(guò)傳感節(jié)點(diǎn)感測(cè)的有向性，提高了通信資源的使用率，并降低了對(duì)其他網(wǎng)絡(luò)的干擾，也滿足了不同目標(biāo)覆蓋的差異懷。目前，DSNs已廣泛應(yīng)用于各類監(jiān)測(cè)領(lǐng)域。這些應(yīng)用的關(guān)鍵在于如何有效地對(duì)覆蓋目標(biāo)進(jìn)行覆蓋，即目標(biāo)覆蓋控制問(wèn)題。

近期，研究人員對(duì)DSNs的覆蓋控制進(jìn)行大量的研究工作。所謂覆蓋控制就是以盡量少的傳感節(jié)點(diǎn)數(shù)實(shí)現(xiàn)區(qū)域的最大覆蓋[4]。然而，文獻(xiàn)[5-6]已證實(shí)，覆蓋控制是NP問(wèn)題，只能獲取次優(yōu)解[7]。因此，覆蓋問(wèn)題成為DSNs復(fù)雜問(wèn)題之一，其主要涉及傳感節(jié)點(diǎn)工作時(shí)間的選擇以及它們感知方向(Sensing sectors)的決策，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)壽命。

目標(biāo)覆蓋是DSNs的基礎(chǔ)，已成為DSNs的研究熱點(diǎn)。不同的目標(biāo)可能具有不同的重要性，因此，它們的覆蓋要求不盡相同。例如，智能交通系統(tǒng)(Intelligent Transportation System, ITS)中的交叉路口的流量監(jiān)控覆蓋，相比其他監(jiān)控覆蓋點(diǎn)，具有高的覆蓋要求。高性能的監(jiān)控覆蓋性能取決于二值扇形模型。所謂扇形模型是指：如果目標(biāo)在傳感節(jié)點(diǎn)的感測(cè)覆蓋區(qū)域內(nèi)，就認(rèn)為目標(biāo)被傳感節(jié)點(diǎn)覆蓋[7-8]。文獻(xiàn)[7-8]中，作者提出了不同的算法解決目標(biāo)覆蓋問(wèn)題，但是它們是假定所有目標(biāo)具有相同的覆蓋重要性。此外，文獻(xiàn)[9-11]利用基于Voronoi單元?jiǎng)澐?，?yōu)化活動(dòng)節(jié)點(diǎn)，進(jìn)而提高覆蓋性能。

然而，這些算法均是采用二值扇形模型。但是，對(duì)于給定目標(biāo)，傳感節(jié)點(diǎn)的感測(cè)質(zhì)量完全取決于它們之間的距離和信號(hào)衰減率[12-13]。在文獻(xiàn)[12]中， 利用關(guān)于傳感節(jié)點(diǎn)離目標(biāo)間的距離函數(shù)，對(duì)覆蓋目標(biāo)質(zhì)量進(jìn)行量化，并將網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)劃分多個(gè)不相交覆蓋集，致使每個(gè)覆蓋集能滿足目標(biāo)的覆蓋要求。同時(shí)，引用最大網(wǎng)絡(luò)壽命分配(Maximal Network Lifetime Scheduling, MNLS)算法，優(yōu)化覆蓋集的工作時(shí)間，進(jìn)而最大化網(wǎng)絡(luò)壽命。類似地，文獻(xiàn)[13]提出面向目標(biāo)可靠性的有向覆蓋集(Directional Cover-set Considering Coverage Reliability, DCCR)算法。DCCR算法利用信號(hào)衰減因子建立目標(biāo)覆蓋質(zhì)量，并通過(guò)優(yōu)化不相交覆蓋集，最大化網(wǎng)絡(luò)壽命，同時(shí)滿足所有目標(biāo)的覆蓋要求。

然而，在真實(shí)環(huán)境中，目標(biāo)檢測(cè)存在不準(zhǔn)確性和異構(gòu)性，并且多數(shù)目標(biāo)服從概率模型[14]。如果不聯(lián)合考慮節(jié)點(diǎn)的剩余能量和覆蓋質(zhì)量，則很難提高網(wǎng)絡(luò)壽命。原因在于：不同傳感節(jié)點(diǎn)的能量消耗率存在較大的差異性。此外，如何分配覆蓋集的工作時(shí)間，對(duì)網(wǎng)絡(luò)壽命有直接的影響。

為此，本文提出覆蓋質(zhì)量感知的最大化網(wǎng)絡(luò)壽命(Coverage Quality aware-based Network Lifetime Maximization，CQ-NLM)算法，提高覆蓋質(zhì)量和網(wǎng)絡(luò)壽命。CQ-NLM算法的主要目的就是以最小的活動(dòng)節(jié)點(diǎn)數(shù)最大化覆蓋質(zhì)量，并且這些活動(dòng)節(jié)點(diǎn)數(shù)能滿足異構(gòu)覆蓋質(zhì)量。實(shí)驗(yàn)數(shù)據(jù)表明，提出的CQ-NLM算法能夠有效地提高網(wǎng)絡(luò)壽命。

1 系統(tǒng)模型及假設(shè)

假定在監(jiān)測(cè)區(qū)域內(nèi)有N個(gè)傳感節(jié)點(diǎn)，且它們隨機(jī)分布于區(qū)域Ω內(nèi)。這些傳感節(jié)點(diǎn)實(shí)時(shí)地感測(cè)環(huán)境數(shù)據(jù)，并將數(shù)據(jù)傳輸至信宿。一旦部署了，這些傳感節(jié)點(diǎn)不再移動(dòng)，即屬于靜態(tài)節(jié)點(diǎn)。此外，考慮同構(gòu)網(wǎng)絡(luò)，節(jié)點(diǎn)具有相同的感測(cè)半徑Rs和初始能量E0。此外，傳感節(jié)點(diǎn)具有活動(dòng)和休眠兩種狀態(tài)，并且能自行切換。

DSNs中每個(gè)傳感節(jié)點(diǎn)有感測(cè)和通信功能：

圖1 有向傳感節(jié)點(diǎn)模型

(2)每個(gè)傳感節(jié)點(diǎn)的通信半徑為Rc，且Rc≥2Rs[15]。通信的角度為θc，0≤θc≤2π。

此外，假定網(wǎng)絡(luò)內(nèi)存在M個(gè)目標(biāo)，且它們的位置已知。N個(gè)傳感節(jié)點(diǎn)隨機(jī)分布于監(jiān)測(cè)區(qū)域，并通過(guò)高密度部署，獲取高的覆蓋率。每個(gè)目標(biāo)具有預(yù)定的覆蓋質(zhì)量，且表示為γ(mk)，其中mk表示第k個(gè)目標(biāo)。

2 CQ-NLM算法

CQ-NLM算法目的就是使用最少的傳感節(jié)點(diǎn)數(shù)獲取高的覆蓋質(zhì)量。為此，CQ-NLM算法利用混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming，MILP)建立目標(biāo)函數(shù)[16]。然后，由目標(biāo)函數(shù)建立候選集，并由候選集節(jié)點(diǎn)覆蓋目標(biāo)。一旦候選集的壽命耗盡，信宿再選擇新的候選集。此外，本文引用如表1所示的標(biāo)識(shí)符。

表1 標(biāo)識(shí)符

2.1 標(biāo)的覆蓋質(zhì)量

為了判斷在傳感節(jié)點(diǎn)ni的sth扇區(qū)內(nèi)是否存在目標(biāo)mk，使用TIS算法[5]。如果目標(biāo)mk離傳感節(jié)點(diǎn)ni的距離小于Rs，并且在其感知扇區(qū)內(nèi)，則將傳感節(jié)點(diǎn)ni的sth扇區(qū)納入ξmk，如式(1)所示：

ξmk←di,s, ifD(ni,mk)≤Rs

(1)

其中D(ni,mk)表示傳感節(jié)點(diǎn)ni離目標(biāo)mk的歐式距離。

圖2 目標(biāo)的概率覆蓋

利用文獻(xiàn)[14]所示的概率覆蓋模型，可將由傳感節(jié)點(diǎn)ni的sth扇區(qū)所覆蓋目標(biāo)的覆蓋質(zhì)量σi,s(mk)表示如式(2)所示：

(2)

其中Ru表示感測(cè)誤差。而α=D(ni,mk)-(Rs-Ru)。λ、β分別參數(shù)，用于測(cè)量檢測(cè)概率。

引入變量χ，其表示傳感節(jié)點(diǎn)集，集內(nèi)的節(jié)點(diǎn)感知扇區(qū)能夠覆蓋目標(biāo)mk。假定有p個(gè)傳感節(jié)點(diǎn)的感知扇形能覆蓋目標(biāo)，則χ={ni|i=1,2,3,…,p}。

因此，累加覆蓋目標(biāo)mk的覆蓋質(zhì)量ρ(mk)如式(3)所示：

(3)

2.2 目標(biāo)函數(shù)

首先建立候選集ψ，其為傳感節(jié)點(diǎn)的感知扇區(qū)η的子集，即ψ?η。候選集ψ內(nèi)節(jié)點(diǎn)能夠覆蓋目標(biāo)，并且滿足每個(gè)目標(biāo)mk的覆蓋要求γ(mk)。

然后，再計(jì)算候選集ψ的壽命。本文從節(jié)點(diǎn)能量定義候選集ψ壽命。如果傳感節(jié)點(diǎn)ni的初始能量為E0，剩余能量為Er(i)，并且能量消耗率為δ(i)，則傳感節(jié)點(diǎn)ni的剩余壽命為：

(4)

依據(jù)式(4)，可得候選集ψ的壽命τ，如式(5)所示：

τ=min{ζi|di,s∈ψ}

(5)

從式(5)可知，候選集ψ的壽命等于集內(nèi)節(jié)點(diǎn)的最小壽命。

在建立目標(biāo)函數(shù)之前，先引入二值變量bi,s，其值反應(yīng)了傳感節(jié)點(diǎn)ni的扇區(qū)di,s是否在候選集ψ內(nèi)。

(6)

CQ-NLM算法的目的就是以最少的傳感節(jié)點(diǎn)實(shí)現(xiàn)覆蓋目標(biāo)的最大化。為此，就是尋找最小的候選集ψ，進(jìn)而滿足覆蓋要求。利用MILP所建立的目標(biāo)函數(shù)如式(7)所示：

(7)

那式(7)的約束條件如式(8)～式(11)所示：

?di,s∈ψ,ψ?η

(8)

式(8)確保了在特定候選集內(nèi)每個(gè)節(jié)點(diǎn)只有某一個(gè)扇區(qū)是活動(dòng)狀態(tài)，其他扇區(qū)是休眠的，這有利于網(wǎng)絡(luò)壽命的提高。

ρ(mk)≥γ(mk), ?mk∈M,1≤k≤|M|

(9)

式(9)保證了每個(gè)目標(biāo)都被覆蓋，并滿足覆蓋要求。即有足夠的節(jié)點(diǎn)最監(jiān)控目標(biāo)。

?mk∈M,1≤k≤|M|

(10)

式(10)保證了滿足每個(gè)目標(biāo)的覆蓋要求。即每個(gè)目標(biāo)的覆蓋質(zhì)量大于或等于目標(biāo)預(yù)定的覆蓋質(zhì)量。

Er(i)≥Eth,di,s∈ψ,ψ?η

(11)

式(11)保證：僅當(dāng)節(jié)點(diǎn)的剩余能量大于能量閾值Eth，該節(jié)點(diǎn)才能加入候選集ψ。

對(duì)于能量閾值，采用局部均值算法求解能量閾值。將每個(gè)扇區(qū)內(nèi)所有節(jié)點(diǎn)的平均剩余能量作為能量閾值。當(dāng)然，計(jì)算扇區(qū)內(nèi)節(jié)點(diǎn)平均剩余能量存在一定的計(jì)算量和通信量，這必然會(huì)引起額外的能耗，但這一定是小于本算法所節(jié)省的能量，總體仍能夠提高能量效率，最終延長(zhǎng)網(wǎng)絡(luò)壽命。后續(xù)的實(shí)驗(yàn)數(shù)據(jù)可證實(shí)。

依據(jù)這些上述約束條件，通過(guò)求解目標(biāo)函數(shù)，實(shí)現(xiàn)覆蓋目標(biāo)最大化，并延長(zhǎng)網(wǎng)絡(luò)壽命。

3 系統(tǒng)仿真及性能分析

3.1 仿真環(huán)境及性能指標(biāo)

為了更好地分析CQ-NLM算法性能，利用離散事件仿真器NS-3建立仿真平臺(tái)。有向傳感節(jié)點(diǎn)和目標(biāo)均勻地分布于160×160 m2區(qū)域。每個(gè)節(jié)點(diǎn)的初始能量為E0=6 J。預(yù)定的覆蓋質(zhì)量ρ從0.1至0.9變化。其他的仿真參數(shù)如下：ω=4、λ=1、β=0.5、Rs=50 m、Ru=25 m。仿真時(shí)間為1000 s，每次仿真獨(dú)立重要50次，取平均值作為最終的仿真數(shù)據(jù)。

選用覆蓋率和網(wǎng)絡(luò)壽命作為評(píng)估算法的性能指標(biāo)。覆蓋率等于覆蓋面積占總體面積的比率。覆蓋率越高，表明DSN網(wǎng)絡(luò)性能越優(yōu)。網(wǎng)絡(luò)壽命表示從部署傳感節(jié)點(diǎn)開始至DSN內(nèi)第一個(gè)節(jié)點(diǎn)失效的時(shí)間差。

為了更好地分析CQ-NLM算法的性能，選擇同類的MNLS[12]和DCCR[13]作為參照。主要分析它們的覆蓋率、網(wǎng)絡(luò)壽命以及活動(dòng)傳感節(jié)點(diǎn)數(shù)。其中覆蓋率等于覆蓋面積占總體面積的比率，覆蓋率越高，算法性能越好。而網(wǎng)絡(luò)壽命是指從網(wǎng)絡(luò)部署開始至第一個(gè)傳感節(jié)點(diǎn)失效的時(shí)間差。

3.2 仿真結(jié)果及分析

首先分析傳感節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命和活動(dòng)節(jié)點(diǎn)數(shù)的影響。目標(biāo)數(shù)M=25，傳感節(jié)點(diǎn)數(shù)從55至80變化，仿真數(shù)據(jù)如圖3所示。

從圖3(a)可知，網(wǎng)絡(luò)壽命隨傳感節(jié)點(diǎn)數(shù)的增加而上升。這主要是因?yàn)閭鞲泄?jié)點(diǎn)數(shù)的增加，增加網(wǎng)絡(luò)的總體能量，進(jìn)而延長(zhǎng)了網(wǎng)絡(luò)壽命。與MNLS和DCCR相比，CQ-NLM算法的網(wǎng)絡(luò)壽命得到有效提高。原因在于：這主要是因?yàn)椋篗NLS和DCCR并沒(méi)有優(yōu)化活動(dòng)節(jié)點(diǎn)數(shù)。同時(shí)，在選擇傳感節(jié)點(diǎn)數(shù)，忽略了覆蓋集的剩余能量。而CQ-NLM算法考慮了節(jié)點(diǎn)剩余能量，進(jìn)而延長(zhǎng)了網(wǎng)絡(luò)壽命。與MNLS和DCCR相比，CQ-NLM算法的網(wǎng)絡(luò)壽命平均延長(zhǎng)低于10秒。原因在于：CQ-NLM算法計(jì)算能量閾值也需要消耗能量，降低了一定的網(wǎng)絡(luò)壽命。

圖3(b)顯示了各算法的活動(dòng)節(jié)點(diǎn) 數(shù)。由于CQ-NLM算法通過(guò)混合整數(shù)線性規(guī)劃，降低了傳感節(jié)點(diǎn)數(shù)。因此，活動(dòng)節(jié)點(diǎn)數(shù)的百分比小于DCCR和MNLS。

圖3 傳感節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命和活動(dòng)節(jié)點(diǎn)數(shù)的影響

圖4 傳感節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命和活動(dòng)節(jié)點(diǎn)數(shù)的影響(N=80)

然后 分析目標(biāo)數(shù)對(duì)網(wǎng)絡(luò)壽命的影響，其中傳感節(jié)點(diǎn)數(shù)N=80，目標(biāo)數(shù)從5至35變化，仿真數(shù)據(jù)如圖4所示。

圖5 傳感節(jié)點(diǎn)數(shù)對(duì)網(wǎng)絡(luò)壽命和活動(dòng)節(jié)點(diǎn)數(shù)的影響(N=50)

從圖4(a)可知，隨著目標(biāo)數(shù)的增加，網(wǎng)絡(luò)壽命逐漸下降。原因在于：目標(biāo)數(shù)越多，需要越多的活動(dòng)傳感節(jié)點(diǎn)去覆蓋目標(biāo)，進(jìn)而縮短了網(wǎng)絡(luò)壽命。與MNLS和DCCR相比，CQ-NLM算法的網(wǎng)絡(luò)壽命得有效地提高。圖4(b)具有與圖3(b)類似數(shù)據(jù)，由于CQ-NLM算法減少了傳感節(jié)點(diǎn)數(shù)量，降低了活動(dòng)節(jié)點(diǎn)數(shù)。

再分析惡劣環(huán)境：目標(biāo)數(shù)多而傳感節(jié)點(diǎn)數(shù)相對(duì)較少的情況。在本次實(shí)驗(yàn)中，目標(biāo)數(shù)從30至50變化，傳感節(jié)點(diǎn)數(shù)為50，實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

從圖5(a)可知，當(dāng)節(jié)點(diǎn)數(shù)為50時(shí)，目標(biāo)數(shù)的增加，導(dǎo)致網(wǎng)絡(luò)壽命的急劇下降，原因在于：目標(biāo)數(shù)越多，需要更多的傳感節(jié)點(diǎn)覆蓋目標(biāo)。而傳感節(jié)點(diǎn)數(shù)一定，這就需要更多的傳感節(jié)點(diǎn)參與目標(biāo)覆蓋，加大傳感的工作時(shí)間，進(jìn)而增加了傳感節(jié)點(diǎn)的能耗，進(jìn)而降低了網(wǎng)絡(luò)壽命。而圖5(b)的數(shù)據(jù)進(jìn)一步說(shuō)明目標(biāo)數(shù)的增加，導(dǎo)致更多的節(jié)點(diǎn)因能量消耗殆盡而無(wú)效，因此，活動(dòng)節(jié)點(diǎn)數(shù)減少。特別是當(dāng)目標(biāo)數(shù)增加到40后，活動(dòng)節(jié)點(diǎn)數(shù)急劇下降。

最后，分析節(jié)點(diǎn)部署方式對(duì)網(wǎng)絡(luò)壽命的影響。在實(shí)驗(yàn)中，考慮均勻部署和隨機(jī)部署兩種方式。具體而言，在160×160m2區(qū)域內(nèi)以均勻和隨機(jī)部署80個(gè)傳感節(jié)點(diǎn)，目標(biāo)數(shù)從5至35變化。實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

圖6 網(wǎng)絡(luò)壽命隨節(jié)點(diǎn)部署方式的變化情況

圖6(a)、6(b)分別描述了均勻部署、隨機(jī)部署傳感節(jié)點(diǎn)環(huán)境下三個(gè)算法的網(wǎng)絡(luò)壽命。從圖6可知，隨機(jī)部署傳感節(jié)點(diǎn)，降低了網(wǎng)絡(luò)的總體壽命。原因在于：均勻部署傳感節(jié)點(diǎn)，使節(jié)點(diǎn)分而更均勻，更有利于檢測(cè)目標(biāo)。而隨機(jī)部署使得節(jié)點(diǎn)分布呈隨機(jī)性，這不利于檢測(cè)目標(biāo)。因此，需要消耗更多的能量去檢測(cè)目標(biāo)，進(jìn)而降低了網(wǎng)絡(luò)壽命。

4 總 結(jié)

針對(duì)DSNs的目標(biāo)覆蓋問(wèn)題，提出基于覆蓋質(zhì)量感知的最大化網(wǎng)絡(luò)壽命CQ-NLM算法。CQ-NLM算法先利用概率感測(cè)模型，計(jì)算每個(gè)目標(biāo)的覆蓋質(zhì)量。然后，建立目標(biāo)函數(shù)，再利用MILP優(yōu)化網(wǎng)絡(luò)壽命，通過(guò)以最少的傳感節(jié)點(diǎn)數(shù)，實(shí)現(xiàn)覆蓋最大化。仿真數(shù)據(jù)表明，提出的CQ-NLM算法有效地提高網(wǎng)絡(luò)壽命。