高安迪，吳曉霞，李 峰

（1.河北機(jī)電職業(yè)技術(shù)學(xué)院，信息工程系，河北 邢臺 054000；2.河北科技大學(xué)，信息科學(xué)與工程學(xué)院，河北 石家莊 050018）

1 引言

無線傳感器網(wǎng)絡(luò)在機(jī)械設(shè)備狀態(tài)監(jiān)測領(lǐng)域有著重要的作用，是工業(yè)自動(dòng)化制造水平高低的一個(gè)重要標(biāo)準(zhǔn)。在構(gòu)建無線傳感器網(wǎng)絡(luò)的過程中，需要合理設(shè)置布局以獲得最優(yōu)節(jié)點(diǎn)位置與傳感器個(gè)數(shù)，從而實(shí)現(xiàn)目標(biāo)區(qū)域的監(jiān)測功能，這已經(jīng)成為無線傳感器應(yīng)用的一項(xiàng)關(guān)鍵內(nèi)容，對網(wǎng)絡(luò)監(jiān)測的準(zhǔn)確性起到了決定作用［1-3］。進(jìn)行信息提取時(shí)，當(dāng)構(gòu)建傳感器網(wǎng)絡(luò)后可以實(shí)現(xiàn)對所在區(qū)域的多個(gè)感知節(jié)點(diǎn)進(jìn)行全面監(jiān)測，從而獲得更全面的位置信息，經(jīng)過不同位置的信息融合后達(dá)到比單路以及多路方法更高價(jià)值的信息。并且隨著節(jié)點(diǎn)部署數(shù)量的增加，傳感器網(wǎng)絡(luò)對目標(biāo)區(qū)域的感知能力也越強(qiáng)［4-5］。

傳感器節(jié)點(diǎn)運(yùn)行過程中需消耗能量的部分主要包括信息采集以及數(shù)據(jù)傳輸二個(gè)過程。其中，進(jìn)行數(shù)據(jù)傳輸時(shí)，涉及功率調(diào)節(jié)、信道傳輸、睡眠—激活控制等環(huán)節(jié)。MAC層是調(diào)度享信道傳輸過程的主要部位，該層結(jié)構(gòu)屬于可以實(shí)現(xiàn)物理層與網(wǎng)絡(luò)層數(shù)據(jù)轉(zhuǎn)換的連接部分，由此萬網(wǎng)絡(luò)數(shù)據(jù)的直接調(diào)控，信道能耗以及傳輸損耗情況受到該層控制性能優(yōu)劣性的直接影響［6-8］?，F(xiàn)階段，基本都是以信道介質(zhì)來完成控制協(xié)議的訪問功能，可以將在各時(shí)刻下對網(wǎng)絡(luò)包含的節(jié)點(diǎn)按照多信道方式實(shí)施通信，從而對各類資源達(dá)到充分利用的作用［9-10］。隨著傳輸協(xié)議效率的提高，維護(hù)過程所需的資金也明顯增加，而實(shí)際獲得網(wǎng)絡(luò)壽命延長并未達(dá)到理想的程度，這就要求針對各項(xiàng)參數(shù)采集進(jìn)行傳感器調(diào)度的過程深入分析。例如對系統(tǒng)運(yùn)行數(shù)據(jù)實(shí)施采集的過程中先調(diào)度傳感器，再通過對各類節(jié)點(diǎn)數(shù)據(jù)進(jìn)行分組實(shí)現(xiàn)特定區(qū)間內(nèi)的數(shù)據(jù)收集［11］。文獻(xiàn)［12］利用高斯概率模型仿真測試傳感器網(wǎng)絡(luò)的感知過程，并專門利用概率感知模型確定了傳感器的合理調(diào)度方案：在確?？梢詽M足傳感器網(wǎng)絡(luò)測試要求的情況下，數(shù)據(jù)采集過程中進(jìn)行傳感器網(wǎng)絡(luò)分組來實(shí)現(xiàn)更長的網(wǎng)絡(luò)使用時(shí)間。無線傳感器網(wǎng)絡(luò)在機(jī)械設(shè)備狀態(tài)監(jiān)測領(lǐng)域有著重要的作用，為了解決傳統(tǒng)隨機(jī)優(yōu)化方法不適合某些復(fù)雜場傳感器網(wǎng)絡(luò)布局景的問題，提出了一種基于IGreedy求解CVaR模型。

2 基于CVaR布局模型

2.1 基于CVaR布局模型

考慮到部署過程受到不確定性的影響，函數(shù)值除了會受到子集S的影響之外，外部條件也會對其造成干擾，此時(shí)構(gòu)建的效益函數(shù)內(nèi)包含了與最優(yōu)子集S存在獨(dú)立聯(lián)系的變量y，對布局狀態(tài)造成較大影響。把存在不確定性因素的布局模型表示為下述的形式：

根據(jù)CVaR判斷損失情況，將CVaR加入模型內(nèi)，以其表示處于最差狀態(tài)下形成的互信息均值，包含不確定節(jié)點(diǎn)的情況下，布局過程形成了最大CVaR，使布局過程產(chǎn)生明顯魯棒性。以下是根據(jù)CVaR構(gòu)建的布局模型：

對CVaRα(S)進(jìn)行優(yōu)化時(shí)選擇輔助函數(shù)H(S，τ)的方式來實(shí)現(xiàn)，將其轉(zhuǎn)變成優(yōu)化S與τ的輔助函數(shù)H(S，τ)，由此得到以下的表達(dá)式：

2.2 改進(jìn)算法性能分析

Kf表示效用函數(shù)的曲線斜率，以貪婪算法確定解集子模效用函數(shù)f并計(jì)算最優(yōu)解OPT解集S*子模效用函數(shù)H(S，τ)表達(dá)式如下：

以非標(biāo)準(zhǔn)化單調(diào)子模函數(shù)H(S)，τ完成歸一化后再代入式（4）中可以得到：

對以上式子轉(zhuǎn)換后得到：

利用式（6）計(jì)算出各個(gè)τi對應(yīng)的最優(yōu)解集

設(shè)定上界條件：

對于τ=τi，通過搜索間隔Δ完成求解過程，計(jì)算得到結(jié)果跟最優(yōu)解集H(，τ*)之間滿足下述關(guān)系：

把式（10）代到式（11）中可以得到：

根據(jù)以上式子，利用I-Greedy算法計(jì)算得到解集(SG，τG) 和最優(yōu)解(S*，τ*)的對應(yīng)關(guān)系如下：

2.3 I-Greedy算法

為簡化算法時(shí)間復(fù)雜度，采用惰性賦值的方法完成算法的簡化過程。式（6）表示模型目標(biāo)函數(shù)，算法性能受到參數(shù)τ的明顯影響，為確定最優(yōu)解，為τ設(shè)置了相應(yīng)的搜索間隔Δ和搜索區(qū)間（0，Γ），之后完成有序搜索，防止算法出現(xiàn)局部最優(yōu)解的情況。通過惰性賦值的方式實(shí)現(xiàn)快速搜索的功能。由此得到以下的IGreedy算法的實(shí)現(xiàn)過程：

（1）設(shè)定τ搜索范圍介于（0，Γ）區(qū)間內(nèi)，各參數(shù)依次為置信水平α、間隔Δ、地集V、約束條件I，經(jīng)初始化得到空集。

（2）根據(jù)Δ對搜索范圍中的τ實(shí)施搜索，對符合約束條件I的集合點(diǎn)從中選擇達(dá)到最大效益的元素組成最優(yōu)解，通過惰性賦值的方式提升搜索效率。

3 仿真結(jié)果分析

3.1 實(shí)驗(yàn)步驟

進(jìn)行布局優(yōu)化時(shí)需滿足二個(gè)目標(biāo)，包括獲得良好布局效果以及降低網(wǎng)絡(luò)不確定性引起的損失。根據(jù)互信息評價(jià)布局效果，當(dāng)傳感器網(wǎng)絡(luò)受不確定印刷影響造成的損失通過計(jì)算損失量實(shí)施評估。同時(shí)設(shè)計(jì)對比實(shí)驗(yàn)分析該算法是否滿足有效性。以下為各實(shí)驗(yàn)步驟：

（1）從80個(gè)備選點(diǎn)中選擇40個(gè)組成部署參數(shù)集合，并對該集合進(jìn)行測試。

（2）以Matlab構(gòu)建仿真模型，對不同類型的傳感器布局形式開展仿真處理，通過判斷參數(shù)τ的置信水平α確定最優(yōu)結(jié)果。

（3）對各算法對比差異性，對相同條件下的各算法互信息、不確定因素?fù)p失與時(shí)間復(fù)雜度進(jìn)行測試。

3.2 參數(shù)引起的解集變化分析

圖1（a）顯示，在一個(gè)任意置信水平α下，設(shè)定上限Γ，利用這里的算法按照步長等于1的條件由0至上界Γ有序搜索，最終可以獲得局部最優(yōu)解。并且隨著Γ的增大，便可以得到與全局最優(yōu)解更接近的局部最優(yōu)解，因此需盡量提高Γ的值。根據(jù)互信息評估布局效果，圖1（a）分析發(fā)現(xiàn)，τ搜索上界Γ設(shè)定成50時(shí)，能夠確保各置信水平搜索后得到全局最優(yōu)解。

圖1 參數(shù)τ和α對H（SG）的影響Fig.1 Effect of τ and α on H（SG）

根據(jù)圖1（b）可知，以不同置信水平α計(jì)算得到的最大效益存在一定的差異性。保持固定參數(shù)τ的條件下，對比各個(gè)置信水平α下計(jì)算得到的效益H可以發(fā)現(xiàn)，提高置信水平α之后，根據(jù)最優(yōu)解計(jì)算的布局效益H也持續(xù)提高。

為進(jìn)一步增加傳感器網(wǎng)絡(luò)效益，計(jì)算得到的最終解為α=0.9的部署集合SG0。

3.3 算法互信息對比

為了對I-Greedy算法進(jìn)行有效性驗(yàn)證，在設(shè)置同樣傳感器節(jié)點(diǎn)數(shù)的條件下分別測試了貪婪算法、隨機(jī)部署算法與這里的算法部署結(jié)果與效益。

首先針對各算法設(shè)計(jì)了布局示意圖。從圖2（a）中可以看到，按照隨機(jī)方式部署傳感器節(jié)點(diǎn)時(shí)，形成了無序的位置分布狀態(tài)，中間區(qū)域幾乎不包含部署節(jié)點(diǎn)，無法獲得理想的布局結(jié)構(gòu)。采用傳統(tǒng)貪婪算法處理時(shí)，可保證目標(biāo)區(qū)形成均勻分布的數(shù)據(jù)，并且還需為目標(biāo)區(qū)域靠近邊緣的部位設(shè)置大量節(jié)點(diǎn)，導(dǎo)致大量的資源浪費(fèi)，實(shí)際并不能達(dá)到布局效益的有效提升。圖2（c）顯示，設(shè)計(jì)算法的節(jié)點(diǎn)在目標(biāo)區(qū)域內(nèi)形成了均勻分布的形態(tài)，同時(shí)降低了邊緣位置的節(jié)點(diǎn)數(shù)量，布局效益獲得了明顯提升。

圖2 傳感器網(wǎng)絡(luò)布局Fig.2 Layout of Sensor Networks

利用互信息評價(jià)傳感器網(wǎng)絡(luò)布局性能。逐漸增加傳感器的節(jié)點(diǎn)數(shù)情況下，獲得了更高的布局效益，當(dāng)目標(biāo)區(qū)中部署了40個(gè)傳感器節(jié)點(diǎn)時(shí)，以三種不同部署算法獲得的互信息依次是33、29與18，以這里算法計(jì)算獲得的互信息比隨機(jī)部署方法提升67%，同時(shí)比傳統(tǒng)貪婪算法提高14.3%，由此判斷以該算法能夠達(dá)到理想布局的效果，如圖3所示。

圖3 傳感器網(wǎng)絡(luò)信息增益Fig.3 Information Gain of Sensor Networks

3.4 模型損失對比

根據(jù)表1 結(jié)果可以發(fā)現(xiàn)，傳感器網(wǎng)絡(luò)存在不確定風(fēng)險(xiǎn)時(shí)，CVaR布局模型相對傳統(tǒng)布局模型可以達(dá)到更低損失程度，由在不確定條件下，該模型能夠獲得更優(yōu)布局結(jié)果，提升了模型魯棒性。

表1 模型損失對比Tab.1 Model Loss Comparison

3.5 算法時(shí)間復(fù)雜度對比

分析表2可以發(fā)現(xiàn)，不管出于何種網(wǎng)絡(luò)規(guī)模下，I-Greedy 算法的z都比傳統(tǒng)貪婪算法更小，并且增加傳感器網(wǎng)絡(luò)規(guī)模后，IGreedy算法效率也發(fā)生了持續(xù)升高。這里研究結(jié)果表明，新設(shè)計(jì)的算法能夠顯著降低時(shí)間復(fù)雜度，特別是進(jìn)行大規(guī)模傳感器布局時(shí)表現(xiàn)出了更強(qiáng)的優(yōu)越性。

表2 時(shí)間復(fù)雜度對比Tab.2 Time Complexity Comparison

4 結(jié)論

（1）τ搜索上界Γ設(shè)定成50和置信水平α=0.9時(shí)，能夠確保各置信水平都搜索獲得全局最優(yōu)解。

（2）逐漸增加傳感器節(jié)點(diǎn)數(shù)量后，布局效益獲得了持續(xù)提升。計(jì)算得到互信息相對隨機(jī)部署方法增加69%，與傳統(tǒng)貪婪算法相比增加14.1%。

（3）CVaR布局模型相對傳統(tǒng)布局模型可以達(dá)到更低損失程度，能夠獲得更優(yōu)布局結(jié)果，提升了模型魯棒性。

（4）算法能夠顯著降低時(shí)間復(fù)雜度，特別是進(jìn)行大規(guī)模傳感器布局時(shí)表現(xiàn)出了更強(qiáng)的優(yōu)越性。