無線傳感器網(wǎng)絡部分覆蓋和數(shù)據(jù)收集算法

魏博垚，唐曉嵐，陳文龍

(首都師范大學 信息工程學院，北京 100048)

1 引 言

隨著物聯(lián)網(wǎng)技術不斷發(fā)展，人們對數(shù)據(jù)收集和感知的需求越來越迫切.在無線傳感器網(wǎng)絡(Wireless Sensor Networks，WSNs)中，部署在監(jiān)測區(qū)域中的眾多傳感器節(jié)點協(xié)作地感知、采集和處理信息并發(fā)送給基站，其成本低、靈活多樣且能夠在惡劣的自然環(huán)境(如深海和戰(zhàn)場等環(huán)境)中工作，因此WSNs成為廣泛使用的無線數(shù)據(jù)收集方式[1].由于傳感器節(jié)點攜帶電池能量有限，并且在某些情況下更換電池極其困難，能耗問題成為無線傳感器網(wǎng)絡研究的重點.如何激活少量傳感器節(jié)點，在保證數(shù)據(jù)收集質(zhì)量的前提下，使盡可能多的節(jié)點進入休眠狀態(tài)，節(jié)省數(shù)據(jù)采集和傳輸?shù)哪芎?，從而延長網(wǎng)絡壽命，是無線傳感器網(wǎng)絡面臨的重要挑戰(zhàn)之一.

無線傳感器網(wǎng)絡的覆蓋模型按照覆蓋比例分為完全覆蓋和部分覆蓋，完全覆蓋要求感知節(jié)點對目標場景100%覆蓋，而部分覆蓋只需要對目標場景達到特定比例的覆蓋，例如環(huán)境溫濕度監(jiān)測通常只需要覆蓋目標區(qū)域的一部分即可達到監(jiān)測要求.針對部分覆蓋的網(wǎng)絡應用，選擇盡可能少的傳感器節(jié)點做為感知節(jié)點達到覆蓋率要求，同時保證網(wǎng)絡連通性，令其他節(jié)點進入休眠狀態(tài)，有助于節(jié)約網(wǎng)絡能耗.無線傳感器網(wǎng)絡的覆蓋模型按照節(jié)點部署方式又分為固定覆蓋模型和隨機覆蓋模型，固定覆蓋模型根據(jù)預先設定好的節(jié)點位置來激活部分節(jié)點滿足覆蓋要求；而隨機覆蓋模型則是在節(jié)點位置隨機分布的情況下，依據(jù)特定策略激活部分節(jié)點，完成對目標區(qū)域的覆蓋.隨機覆蓋模型更為靈活，應用更廣，因此本文關注于隨機部署下的部分覆蓋問題.

本文將目標場景劃分為若干個區(qū)域，在區(qū)域內(nèi)使用基于最大獨立集的部分覆蓋算法，選擇盡可能少的感知節(jié)點用于數(shù)據(jù)采集.然后針對所有區(qū)域的感知節(jié)點，構(gòu)建樹結(jié)構(gòu)，通過最少跳數(shù)將數(shù)據(jù)從感知節(jié)點傳輸?shù)絪ink節(jié)點，同時盡可能均衡同層節(jié)點的子節(jié)點個數(shù)，實現(xiàn)傳輸能耗分攤；對于不連通的區(qū)域，激活輔助傳輸節(jié)點，實現(xiàn)數(shù)據(jù)收集.

2 相關工作

近年來，無線傳感器網(wǎng)絡的覆蓋控制和數(shù)據(jù)收集問題得到一定的研究，提出了一系列算法.本文主要在兩個方向進行探索，第一針對部分覆蓋問題，尋找滿足覆蓋要求且激活節(jié)點數(shù)少的解決方案，從而降低能耗；第二確保網(wǎng)絡連通性，建立從感知節(jié)點到sink節(jié)點的數(shù)據(jù)收集路徑.

在無線傳感器網(wǎng)絡的覆蓋研究中，文獻[2]提出了動態(tài)覆蓋優(yōu)化算法，把目標區(qū)域劃分成N個目標點，采用蟻群算法，解決覆蓋與網(wǎng)絡壽命兩個問題，但是未對節(jié)點冗余覆蓋進行深入探究.文獻[3]提出的PCLA算法利用學習自動機實現(xiàn)節(jié)點的休眠調(diào)度，激活較少的節(jié)點滿足部分覆蓋需求.此方法仍然存在監(jiān)測冗余，尤其是當覆蓋限制條件苛刻時，算法性能受影響，同時文章未指出如何計算覆蓋面積.文獻[4]較早提出了多重覆蓋問題，針對不同子區(qū)域具有不同覆蓋需求的場景，提出集中式和分布式的算法來選擇較少的節(jié)點實現(xiàn)p-percent覆蓋.一些研究以感知范圍不重疊的節(jié)點集合建立獨立集，從而將無線傳感器網(wǎng)絡的覆蓋問題轉(zhuǎn)化為圖的最大獨立集問題，該問題是一個 NP難問題[5]，目前主流的解決方案是運用啟發(fā)式算法求解.文獻[6]提出了基于粒子群的優(yōu)化算法，但是該算法時間復雜度高，參數(shù)的配置仍然是一個問題.文獻[7]提出一種基于網(wǎng)格劃分的無線傳感器網(wǎng)絡多重覆蓋算法，采用布爾模型對節(jié)點進行冗余判斷，使冗余節(jié)點進入休眠狀態(tài).

針對節(jié)點能量有限以及能耗不均衡的問題，部分研究關注于無線傳感器網(wǎng)絡中的節(jié)點調(diào)度.文獻[8]設計一種考慮節(jié)點剩余能量、信息傳輸成功率以及節(jié)點到基站之間距離的效用函數(shù)，構(gòu)建博弈模型，提出基于勢博弈的非均勻拓撲控制算法，但是該研究未考慮節(jié)點之間的路由選擇.文獻[9]提出一種與節(jié)點位置無關的休眠調(diào)度算法，通過節(jié)點與 sink 節(jié)點交換數(shù)據(jù)信息，計算出各個節(jié)點的坐標，但是該算法僅考慮2跳之內(nèi)的冗余，未對所有節(jié)點之間的冗余程度對網(wǎng)絡性能產(chǎn)生的影響進行分析.文獻[10]提出了一種基于最優(yōu)跳數(shù)的非均勻分簇算法UCOH，首先計算數(shù)據(jù)直線傳輸?shù)交镜睦硐肼窂?，依?jù)該路徑形成的熱區(qū)調(diào)整簇半徑，均衡簇內(nèi)和簇間通信能耗，但是在分簇的過程中并未考慮部分覆蓋問題.

有關無線傳感器網(wǎng)絡中的數(shù)據(jù)傳輸，文獻[11，12]提出了在有限傳輸半徑下建立連通集的問題及其應用.文獻[13，14]提出了一種可靠的數(shù)據(jù)傳輸模型，對于優(yōu)化傳感器網(wǎng)絡的路由轉(zhuǎn)發(fā)具有較高參考價值.文獻[15]對網(wǎng)絡路由進行等級劃分，使得網(wǎng)絡安全性大大提高.文獻[16]針對目前主流的無線傳感網(wǎng)絡拓撲修復算法進行了大量調(diào)研，對網(wǎng)絡節(jié)點的路由選擇和修復等研究有較高的借鑒意義.

本文采用了與文獻[3]中貪婪法類似的算法來避免監(jiān)測冗余，激活盡可能少的感知節(jié)點；進而適當激活輔助傳輸節(jié)點來保證網(wǎng)絡連通性，實現(xiàn)數(shù)據(jù)從感知節(jié)點到sink節(jié)點的收集.

3 網(wǎng)絡模型

在密集部署的無線傳感器網(wǎng)絡中，每個傳感器節(jié)點具有唯一的標識ID，且具有位置感知能力，已知自己的地理位置坐標.通過位置通告，節(jié)點獲知其通信范圍內(nèi)其他節(jié)點(稱為鄰居節(jié)點)的位置信息.假設所有傳感器節(jié)點的傳輸半徑相同，感知半徑可以不同.為了降低感知節(jié)點選擇算法的計算復雜度，將目標場景劃分為若干個大小相等的區(qū)域，在每個區(qū)域內(nèi)依據(jù)最大獨立集計算滿足覆蓋要求的感知節(jié)點集；然后建立由sink節(jié)點到各個區(qū)域內(nèi)感知節(jié)點的傳輸路徑，本文以最少跳數(shù)和子節(jié)點數(shù)均衡為目標建立樹狀結(jié)構(gòu)實現(xiàn)數(shù)據(jù)收集.

為簡化感知節(jié)點的監(jiān)測面積計算，本文使用網(wǎng)格模型，即將區(qū)域劃分為若干個面積為b×b的小網(wǎng)格，依據(jù)節(jié)點對網(wǎng)格交叉點的覆蓋情況得到節(jié)點的監(jiān)測面積，進而計算所有感知節(jié)點對區(qū)域的覆蓋率.

定義1.(節(jié)點監(jiān)測面積) 區(qū)域內(nèi)部署的傳感器節(jié)點集合記為S={s1，s2，…，sn}，任意傳感器節(jié)點sn的感知范圍是以sn為圓心、以感知半徑r為半徑的圓形區(qū)域，若此范圍內(nèi)包含m個網(wǎng)格交叉點，則稱節(jié)點sn的監(jiān)測面積為m個單位.

定義2.(監(jiān)測冗余) 對于任意兩個傳感器節(jié)點，若其感知范圍存在共同包含的網(wǎng)格交叉點，則稱這兩個傳感器節(jié)點的監(jiān)測區(qū)域有重疊，該重疊區(qū)域稱為監(jiān)測冗余.

定義3.(監(jiān)測貢獻面積) 節(jié)點sn的監(jiān)測貢獻面積是指針對區(qū)域內(nèi)尚未被已選擇節(jié)點感知的部分，節(jié)點sn的感知范圍能夠覆蓋的面積.

若對于區(qū)域內(nèi)任意網(wǎng)格交叉點p，都存在節(jié)點sn∈S使得sn的感知范圍覆蓋p，則稱集合S是對區(qū)域的完全覆蓋.部分覆蓋應用所要求的感知節(jié)點對目標場景的最低覆蓋率記為η.

在本文中使用A(S′)表示節(jié)點集合S′的監(jiān)測面積，以S′中所有節(jié)點的感知范圍所覆蓋的網(wǎng)格交叉點個數(shù)計算.使用E(si，sj)表示節(jié)點si與sj是否存在監(jiān)測冗余，若節(jié)si與sj存在監(jiān)測冗余，則E(si，sj)=1，否則E(si，sj)=0.用int(si)表示與si存在監(jiān)測冗余的其他節(jié)點集合，N(si)=|int(si)|表示此集合的節(jié)點個數(shù)，稱為節(jié)點si的相交節(jié)點個數(shù).

圖1 覆蓋模型圖Fig.1 Coverage model diagram

如圖1所示，實線圓表示節(jié)點的感知范圍，陰影部分表示節(jié)點s1和s2的監(jiān)測冗余.節(jié)點s1與s2的感知范圍分別包含4個交叉點，共同包含7個交叉點，故A({s1})=4，A({s1，s2})=7.s1與s2存在監(jiān)測冗余，故E(s1，s2)=1；s2與s3不存在監(jiān)測冗余，故E(s2，s3)=0.因此，int(s2)={s1}，N(s2)=1.若s1的監(jiān)測貢獻面積為其感知范圍，則s2的監(jiān)測貢獻面積為其感知范圍中除陰影部分以外的區(qū)域.

本文使用網(wǎng)格模型是因為直接計算存在監(jiān)測冗余的多個節(jié)點的監(jiān)測貢獻面積，計算復雜度過高.網(wǎng)格模型既能用于節(jié)點覆蓋面積計算，又能通過調(diào)節(jié)網(wǎng)格粒度來有效地計算最大獨立集，從而找到滿足覆蓋要求的感知節(jié)點集合.網(wǎng)格粗細粒度影響著感知節(jié)點的監(jiān)測面積和監(jiān)測冗余的計算.網(wǎng)格粒度越大，則監(jiān)測面積的計算精度越小，面積較小的監(jiān)測冗余越難以判斷；反之，當網(wǎng)格粒度較小時，雖然會提高覆蓋面積的計算精度，但是對監(jiān)測冗余的判斷過于敏感，生成的最大獨立集中元素個數(shù)過少，迭代過程中節(jié)點集更新頻繁，增加算法的時間復雜度.本文通過實驗，得出網(wǎng)格粒度的合理取值區(qū)間.

無線傳感器網(wǎng)絡的節(jié)點能量消耗主要包括數(shù)據(jù)感知的能量消耗和數(shù)據(jù)傳輸?shù)哪芰肯模疚牟捎梦墨I[6]的能量消耗模型.根據(jù)公式，數(shù)據(jù)傳輸能量消耗較大，依據(jù)相關文獻，節(jié)點發(fā)送q比特的消息，且傳輸距離為d時，所消耗的能量表示為.

(1)

式中Ee和Ete均為數(shù)據(jù)傳輸?shù)哪芰肯膮?shù).相應地，接收q比特數(shù)據(jù)的能量消耗公式為.

Erx(q)=qEe.

(2)

當節(jié)點能量耗盡，則不能繼續(xù)感知或傳輸數(shù)據(jù).若sink節(jié)點收集到數(shù)據(jù)的感知節(jié)點的覆蓋面積不能滿足網(wǎng)絡覆蓋率要求，則網(wǎng)絡失效.

4 基于最大獨立集的部分覆蓋算法

若一個節(jié)點集中任意兩個節(jié)點都不存在監(jiān)測冗余，則稱該節(jié)點集為獨立集.在區(qū)域內(nèi)傳感器節(jié)點集合S的所有子集中，節(jié)點個數(shù)最多的獨立集稱為最大獨立集.舉例來看，圖2的最大獨立集為C={s1，s3，s7}，此集合內(nèi)節(jié)點之間存在監(jiān)測冗余且節(jié)點個數(shù)最多.

圖2 最大獨立集示例Fig.2 An example of maximum independent set

由于尋找最大獨立集是NP難問題，本文提出基于貪心策略的最大獨立集計算方法，稱為最大獨立集生成算法，旨在相對快速地找到最大獨立集.進而以最大獨立集為基礎，通過增加和刪除一些節(jié)點，最終激活較少的節(jié)點來滿足部分覆蓋要求.

4.1 最大獨立集生成算法

最大獨立集生成算法的偽代碼見算法1.初始化候選獨立集C0，0=?，禁忌排序表P0，0=Q.若禁忌排序表Pk，i不為空集，則依次從Pk，i中選擇能夠與候選獨立集中至少一個節(jié)點連通的節(jié)點sj加入候選獨立集Ck，i，并從Pk，i中刪除sj和int(sj)中的節(jié)點.若Pk，i中待選擇的兩個節(jié)點的相交節(jié)點個數(shù)相同，即N(sj)=N(sj+1)，并且這兩個節(jié)點不存在監(jiān)測冗余，即E(sj，sj+1)=0，則Ck，i=Ck，i∪{si，sj+1}，更新Pk，i；否則產(chǎn)生分支Ck，i和Ck，i+1，分別將節(jié)點sj和sj+1加入獨立集，并更新每個分支對應的禁忌排序表Pk，i和Pk，i+1，直到對應的禁忌排序表為空時結(jié)束此分支.如果最終得到多個元素個數(shù)相同的最大獨立集，則隨機選擇一個輸出，不屬于此集合的節(jié)點加入剩余節(jié)點集C’.

算法1.最大獨立集生成算法

輸入：S，N(si)

輸出：maximum independent setC

initialize：C0，0=?，P0，0=Q；

whilePk，i!=?do

select the first two nodessjandsj+1inPk，i；

if(N(sj)==N(sj+1)&&E(sj，sj+1)==0)then

Ck，i=Ck，i∪{sj，sj+1}；

Pk，i=Pk，i-sj-sj+1-int(sj)-int(sj+1)；

else

ifN(sj)==N(sj+1)then

Ck，i+1=Ck，i∪{sj+1}；

Pk，i+1=Pk，i-sj+1-int(sj+1)；

endif

Ck，i=Ck，i∪{sj}；

Pk，i=Pk，i-sj-int(sj)；

endif

endwhile

returnCwith max(|Ck，i|)；

4.2 基于最大獨立集的部分覆蓋算法

基于最大獨立集的部分覆蓋算法(MISA)的偽代碼見算法2.由最大獨立集生成算法計算出最大獨立集C后，初始化感知節(jié)點集為C，計算感知節(jié)點的覆蓋率，即C中所有節(jié)點的監(jiān)測貢獻面積之和A(C)占區(qū)域面積A(R)=b×b的比例.若覆蓋率達不到部分覆蓋要求，則從剩余節(jié)點集C′中選擇監(jiān)測貢獻面積最大且和C中至少一個節(jié)點連通的節(jié)點逐個加入感知節(jié)點集，直到覆蓋率達到要求.在滿足覆蓋要求后，對感知節(jié)點集進行冗余判定，在保證感知節(jié)點集連通的前提下，刪除其中監(jiān)測貢獻面積最小的節(jié)點，直到刪除任意節(jié)點都無法滿足覆蓋要求，則輸出感知節(jié)點集Ψ.不屬于感知節(jié)點集的節(jié)點進入休眠狀態(tài)，從而節(jié)省網(wǎng)絡能量消耗.

算法2.基于最大獨立集的部分覆蓋算法

輸入：C，η

輸出：sensing node set Ψ

initialize：Ψ=C；

whilesihas the smallest sensing contributing area in Ψ and

Ψ=Ψ-{si}；

endwhile

else

Ψ=Ψ+{si} wheresihas the largest sensing contributing area inC′；

C′=C′-{si}；

endwhile

endif

returnΨ；

舉例來看，在圖2所示的7個傳感器節(jié)點構(gòu)成的區(qū)域中，表征節(jié)點之間是否存在監(jiān)測冗余的矩陣M如下：

計算每個節(jié)點的相交節(jié)點個數(shù)N(sj)，從小到大排序，得到排序表Q=，初始化C0，0=?，P0，0=Q.在P0，0中按序選擇節(jié)點s1加入候選獨立集C1，0={s1}，同時更新禁忌排序表P1，0=P0，0-.再從P1，0中依次選擇節(jié)點s7加入候選獨立集C2，0={s1，s7}，同時更新P2，0=P1，0-.繼續(xù)從P2，0中選擇節(jié)點加入候選獨立集，由于N(s3)=N(s4)且E(s3，s4)=1，故產(chǎn)生分支C3，0={s1，s7，s3}和C3，1={s1，s7，s4}.分別更新對應的禁忌排序表P3，0=P2，0-，此時P3，0為空，則停止迭代；同理，P3，1=P2，0-，P3，1為空，亦停止迭代.最終產(chǎn)生2個最大獨立集C3，0={s1，s7，s3}與C3，1={s1，s7，s4}，由于這兩個最大獨立集的元素個數(shù)相同，則隨機選擇一個集合輸出.這里以C={s1，s7，s3}為例，由于不滿足覆蓋率要求，繼續(xù)向感知節(jié)點集中加入監(jiān)測貢獻面積最大的節(jié)點s6，此時滿足覆蓋率要求，終止算法，輸出感知節(jié)點集Ψ={s1，s7，s3，s6}.

5 樹結(jié)構(gòu)的數(shù)據(jù)收集機制

在目標場景中，每個區(qū)域內(nèi)依據(jù)基于最大獨立集的部分覆蓋算法選擇感知節(jié)點，這些感知節(jié)點彼此連通.為進一步實現(xiàn)數(shù)據(jù)向sink節(jié)點的傳輸，本文構(gòu)建從sink節(jié)點到各感知節(jié)點的樹結(jié)構(gòu)，并為不能連通的區(qū)域激活輔助傳輸節(jié)點，實現(xiàn)數(shù)據(jù)收集.

樹結(jié)構(gòu)的建立過程由sink節(jié)點啟動，記sink節(jié)點為第0層，即Lsink=0.sink節(jié)點發(fā)送建樹探測報文JOIN_TREE_REQUEST，其中記錄層次值為0，接收到該消息的節(jié)點向sink節(jié)點發(fā)送建樹應答報文JOIN_TREE_REPLY，選擇sink節(jié)點為父節(jié)點加入樹中，其層次值設為1.進一步地，樹上第一層節(jié)點發(fā)送建樹探測報文JOIN_TREE_REQUEST，其中記錄層次值為1，接收到該消息且未加入樹中的節(jié)點選擇該節(jié)點為父節(jié)點，并將自身的層次值設為2.以此類推，所有能夠與sink節(jié)點連通的感知節(jié)點都加入樹中，且層次值盡可能小，保證了數(shù)據(jù)傳輸跳數(shù)最少，傳輸開銷最小.

在樹結(jié)構(gòu)建立過程中，若一個節(jié)點收到多個上層節(jié)點的建樹探測報文，則選擇已有子節(jié)點個數(shù)較少的上層節(jié)點為父節(jié)點，從而使得上層節(jié)點的能耗盡量均衡，避免一個節(jié)點有過多的子節(jié)點，傳輸能耗大而過早死亡.

對于沒有加入樹中的感知節(jié)點，其所在區(qū)域gu內(nèi)的感知節(jié)點不能與周圍區(qū)域的感知節(jié)點通信，因此需要激活部分休眠節(jié)點來輔助數(shù)據(jù)收集.位于該區(qū)域gu邊界的感知節(jié)點sn向其鄰居節(jié)點發(fā)送輔助傳輸請求報文HELP_TRANS_REQUEST，其通信范圍內(nèi)的休眠節(jié)點定期接收請求并處理.對于休眠節(jié)點hv，若其通信范圍內(nèi)存在其他區(qū)域(例如gu+1)的感知節(jié)點sw(樹上層次值為Lw)，則hv向sn發(fā)送輔助傳輸應答報文HELP_TRANS_REPLY，其中記錄預期層數(shù)為RL=Lw+2.否則，即hv的通信范圍內(nèi)不存在其他區(qū)域的感知節(jié)點，則hv再向其周圍休眠節(jié)點發(fā)送輔助傳輸請求報文HELP_TRANS_REQUEST，以此類推，直到hv通過x跳找到已加入樹中的其他區(qū)域的感知節(jié)點sw，則以預期層次RL=Lw+x+1向sn發(fā)送輔助傳輸應答報文HELP_TRANS_REPLY.接下來，sn從收到的多個應答報文中選擇預期層次RL最小的一個鄰居休眠節(jié)點，向其發(fā)送輔助傳輸確認報文HELP_TRANS_OK，并以該節(jié)點為其在樹上的父節(jié)點.該休眠節(jié)點接收到輔助傳輸確認報文HELP_TRANS_OK，即從休眠狀態(tài)調(diào)整為工作狀態(tài)，并建立到鄰居區(qū)域感知節(jié)點的傳輸路徑，從而將該區(qū)域gu內(nèi)的數(shù)據(jù)多跳轉(zhuǎn)發(fā)到sink節(jié)點.

以圖3為例，目標場景劃分為四個區(qū)域，sink節(jié)點位于場景左上方.以sink為根，構(gòu)建包含盡可能多感知節(jié)點的樹結(jié)構(gòu).區(qū)域g2中的感知節(jié)點因為與其他區(qū)域感知節(jié)點的距離大于通信半徑，不能加入樹中，故激活g2中的休眠節(jié)點h1，使得g2中的感知節(jié)點通過h1與鄰居區(qū)域g1中的感知節(jié)點通信，進而將數(shù)據(jù)傳輸?shù)絪ink節(jié)點.在該示例中，休眠節(jié)點h2也能夠?qū)2中的感知節(jié)點與鄰居區(qū)域g4中的感知節(jié)點連通，但通過h2加入樹中的預期層次數(shù)大于通過h1加入樹中的預期層次數(shù)，即通過h2的數(shù)據(jù)傳輸跳數(shù)大于通過h1的數(shù)據(jù)傳輸跳數(shù)，因此g2中的感知節(jié)點選擇h1做為輔助傳輸節(jié)點.

6 仿真實驗

6.1 實驗參數(shù)配置

本文使用C++與MATLAB進行無線傳感器網(wǎng)絡仿真實驗，目標場景400m×400m，隨機拋灑100個節(jié)點，感知半徑為70m，傳輸半徑是感知半徑的兩倍.網(wǎng)格粒度b為20m，部分覆蓋的覆蓋率要求η設為80%和60%，節(jié)點初始能量為 5 J，能量參數(shù)Ee=100 nJ/bit，Eet=20nJ/(bit·m2).

6.2 實驗結(jié)果與分析

1)工作節(jié)點比率.對比方法選擇文獻[11]所提出的CDS算法和文獻[4]提出的DFS算法.在覆蓋率η分別取80%和60%時，本文所提出的MISA算法和對比方法的工作節(jié)點比率如圖4所示.

圖4 工作節(jié)點比率Fig.4 Working node proportion

如圖4所示，與 CDS和 DFS算法相比，本文提出的MISA算法在η=80%和η=60%的情況下，工作節(jié)點(包括感知節(jié)點和輔助傳輸節(jié)點)的數(shù)量較少，從而使得更多的節(jié)點進入休眠狀態(tài)，節(jié)省能量消耗.這是因為相較于CDS與DFS，MISA算法以最大獨立集為基礎，選擇監(jiān)測貢獻面積大的節(jié)點加入感知節(jié)點集，從而盡可能少地激活感知節(jié)點來滿足最小覆蓋要求.

2)感知節(jié)點計算過程中各類節(jié)點比率.圖5展示了在感知節(jié)點集計算過程中，最大獨立集的節(jié)點、增加節(jié)點和刪除節(jié)點占所有節(jié)點的比率.由圖5可見，在生成最大獨立集后，MISA僅需要增加或者刪除少量的節(jié)點就能滿足覆蓋要求.

圖5 感知節(jié)點計算過程中各類節(jié)點比率Fig.5 Proportions of different kinds of nodes in sensing node calculation process

6.3 參數(shù)分析

1)網(wǎng)絡規(guī)模分析.令目標場景中的傳感器節(jié)點個數(shù)從100到400遞增，在覆蓋率要求80%時，選擇文獻[7]的GPSA算法做為對比方法，本文算法的感知節(jié)點數(shù)和輔助傳輸節(jié)點數(shù)以及GPSA算法的工作節(jié)點數(shù)見圖6.

由圖6可見，網(wǎng)絡規(guī)模變化對本算法的感知節(jié)點和輔助傳輸節(jié)點選擇無明顯影響.覆蓋率要求80%時，雖然感知節(jié)點數(shù)和輔助傳輸節(jié)點數(shù)隨網(wǎng)絡規(guī)模的變化略有差異，但是其差異變化不大，均在合理范圍內(nèi).在部署節(jié)點數(shù)量一致的情況下，MISA算法明顯優(yōu)于GPSA算法.當感知節(jié)點較多時，需要的輔助傳輸節(jié)點較少，這是因為大量的感知節(jié)點使得其彼此之間的連通性更強.

圖6 不同網(wǎng)絡規(guī)模的工作節(jié)點數(shù)量Fig.6 Number of working nodes with different numbers of sensor nodes in the scenario

圖7 不同粒度比的最大獨立集節(jié)點比率Fig.7 MIS node proportion with different B

由圖7可見，隨著粒度比B變大，區(qū)域中的網(wǎng)格交叉點變少，兩個傳感器節(jié)點重疊的監(jiān)測區(qū)域覆蓋網(wǎng)格交叉點的概率變小，從而計算出的監(jiān)測冗余變少，被選到最大獨立集中的節(jié)點變多.當粒度比B較小時，最大獨立集節(jié)點較少，通常需要增加額外的節(jié)點以滿足覆蓋要求；當粒度比B較大時，計算誤差較大，同時最大獨立集節(jié)點個數(shù)偏多，需要對超出覆蓋要求的多余節(jié)點進行刪除，也會增加運算時間與能量開銷.總體來看，粒度比取0.3左右效果較佳.

7 總 結(jié)

本文討論了無線傳感器網(wǎng)絡的部分覆蓋問題，節(jié)點隨機部署導致監(jiān)測區(qū)域相互重疊，產(chǎn)生監(jiān)測冗余.為了激活較少的節(jié)點滿足區(qū)域內(nèi)的部分覆蓋需求，本文提出了MISA算法，首先依據(jù)相交節(jié)點信息，計算最大獨立集，以此為初始感知節(jié)點集；然后針對不同覆蓋率要求，依據(jù)監(jiān)測貢獻面積，增刪少量節(jié)點以達到覆蓋要求.接著通過構(gòu)成以sink節(jié)點為根的樹結(jié)構(gòu)，將感知節(jié)點加入樹中，實現(xiàn)數(shù)據(jù)收集；針對不能連通的區(qū)域，激活輔助傳輸節(jié)點來完成數(shù)據(jù)收集.實驗表明，本文所提出的方法能夠有效降低工作節(jié)點數(shù)，使得更多節(jié)點進入休眠狀態(tài)，從而延長網(wǎng)絡生命期.