無線傳感器網絡部分覆蓋和數據收集算法

魏博垚，唐曉嵐，陳文龍

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

1 引 言

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

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

本文將目標場景劃分為若干個區域，在區域內使用基于最大獨立集的部分覆蓋算法，選擇盡可能少的感知節點用于數據采集.然后針對所有區域的感知節點，構建樹結構，通過最少跳數將數據從感知節點傳輸到sink節點，同時盡可能均衡同層節點的子節點個數，實現傳輸能耗分攤；對于不連通的區域，激活輔助傳輸節點，實現數據收集.

2 相關工作

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

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

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

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

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

3 網絡模型

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

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

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

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

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

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

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

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

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

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

無線傳感器網絡的節點能量消耗主要包括數據感知的能量消耗和數據傳輸的能量消耗，本文采用文獻[6]的能量消耗模型.根據公式，數據傳輸能量消耗較大，依據相關文獻，節點發送q比特的消息，且傳輸距離為d時，所消耗的能量表示為.

(1)

式中Ee和Ete均為數據傳輸的能量消耗參數.相應地，接收q比特數據的能量消耗公式為.

Erx(q)=qEe.

(2)

當節點能量耗盡，則不能繼續感知或傳輸數據.若sink節點收集到數據的感知節點的覆蓋面積不能滿足網絡覆蓋率要求，則網絡失效.

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

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

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

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

4.1 最大獨立集生成算法

最大獨立集生成算法的偽代碼見算法1.初始化候選獨立集C0，0=?，禁忌排序表P0，0=Q.若禁忌排序表Pk，i不為空集，則依次從Pk，i中選擇能夠與候選獨立集中至少一個節點連通的節點sj加入候選獨立集Ck，i，并從Pk，i中刪除sj和int(sj)中的節點.若Pk，i中待選擇的兩個節點的相交節點個數相同，即N(sj)=N(sj+1)，并且這兩個節點不存在監測冗余，即E(sj，sj+1)=0，則Ck，i=Ck，i∪{si，sj+1}，更新Pk，i；否則產生分支Ck，i和Ck，i+1，分別將節點sj和sj+1加入獨立集，并更新每個分支對應的禁忌排序表Pk，i和Pk，i+1，直到對應的禁忌排序表為空時結束此分支.如果最終得到多個元素個數相同的最大獨立集，則隨機選擇一個輸出，不屬于此集合的節點加入剩余節點集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后，初始化感知節點集為C，計算感知節點的覆蓋率，即C中所有節點的監測貢獻面積之和A(C)占區域面積A(R)=b×b的比例.若覆蓋率達不到部分覆蓋要求，則從剩余節點集C′中選擇監測貢獻面積最大且和C中至少一個節點連通的節點逐個加入感知節點集，直到覆蓋率達到要求.在滿足覆蓋要求后，對感知節點集進行冗余判定，在保證感知節點集連通的前提下，刪除其中監測貢獻面積最小的節點，直到刪除任意節點都無法滿足覆蓋要求，則輸出感知節點集Ψ.不屬于感知節點集的節點進入休眠狀態，從而節省網絡能量消耗.

算法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個傳感器節點構成的區域中，表征節點之間是否存在監測冗余的矩陣M如下：

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

5 樹結構的數據收集機制

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

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

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

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

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

6 仿真實驗

6.1 實驗參數配置

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

6.2 實驗結果與分析

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

圖4 工作節點比率Fig.4 Working node proportion

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

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

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

6.3 參數分析

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

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

圖6 不同網絡規模的工作節點數量Fig.6 Number of working nodes with different numbers of sensor nodes in the scenario

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

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

7 總 結

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