無線傳感器網絡最小覆蓋能量優化算法*

高潔，吳延紅，白建俠，李琦

（1.山東華宇工學院基礎部，山東德州253000；2.天津大學仁愛學院數學教學部，天津301636）

無線傳感器網絡最小覆蓋能量優化算法*

高潔1*，吳延紅1，白建俠2，李琦1

（1.山東華宇工學院基礎部，山東德州253000；2.天津大學仁愛學院數學教學部，天津301636）

在無線傳感器網絡中，位于基站周圍的節點由于負責所有探測數據的轉發任務而能量消耗水平較高。為了均衡基站周圍節點的能量消耗，提出一種合理有效的節點輪換休眠機制。使得網絡中大量冗余節點處于休眠狀態，從而減少基站周圍重要節點的負載?；谶@種想法提出了冗余節點判定定理，基于Voronoi圖尋找最大可休眠節點集，設計了最小連通覆蓋算法（FBSW）尋找網絡中可休眠的冗余節點，有效地延長網絡的生命周期。仿真結果證明，該算法的運行復雜度優于貪婪算法，由于冗余節點輪換休眠，整個網絡的能量節約了20.01%以上。

無線傳感器網絡；Voronoi圖；最小連通覆蓋集；休眠節點；能量均衡；

EEACC：7230doi：10.3969/j.issn.1004-1699.2016.09.024

無線傳感器網絡是指由大量節點以某種概率分布模型隨機布撒在監測區域內，通過無線通信方式組成的多跳自組織網絡系統［1］。無線傳感器技術已經從最早的軍事國防應用逐步擴展到農業、環境監測、生物醫療、交通管理、危險區域遠程管理乃至家居等諸多領域［2-9］。對于實際應用的高密度網絡，存在大量的可休眠冗余節點，可以設計冗余節點識別算法，在不影響網絡覆蓋和連通性的要求下使得部分節點輪換休眠，這樣既減少了向重要節點發送數據流的流量，又節省重要節點的能量。對于重要節點能量消耗水平較高，可以在重要節點周圍布撒中繼節點，幫助重要節點分擔轉發大量數據流的任務，可以保證重要節點的使用壽命。目前解決此問題的方法主要集中在設計有效的MAC協議、識別冗余節點并使其休眠以保證延長重要節點的生命周期，設計合理的網絡拓撲結構和節點輪換休眠［10-20］。

從研究方法上，文獻［10］將網絡中節點的剩余能量作為點的權值。利用改進的貪婪算法尋找最小加權獨立集。保證最小加權獨立集中的冗余節點首先休眠，而網絡中工作的節點剩余能量水平相對較高，并且滿足整個網絡的全覆蓋。文獻［11］針對路徑覆蓋節點控制策略問題，利用路徑覆蓋的特點，提出了一種基于層級結構的節點覆蓋控制方法。通過對節點監測目標的先后順序，在保障不丟失監測目標的前提下，建立了節點層級模型和關聯模型，設計了以開啟節點數目和均衡能耗為優化目標的覆蓋控制策略文獻［12］。將傳感器節點與目標覆蓋區域的虛擬力操作和節點之間的虛擬力操作按節約能耗的約束同時進行，從而達到覆蓋控制技術的優化目的。文獻［13］通過將網絡區域劃分為若干等寬的子區域，每個子區域內的所有節點形成一個鏈，由鏈首節點負責與基站通信。針對鏈首節點能量消耗太大有可能過早死亡的問題，提出采用鏈首節點輪換的方法來均衡和降低能量消耗。文獻［14］利用冗余節點的思想，讓部分錨節點和已經定位的盲節點進入睡眠，從而降低節點規模和冗余定位信息，保證了節點低能耗下的精確定位.voronoi圖理論常常用在無線傳感器網絡研究。文獻［15］的工作主要集中于利用Vo?ronoi劃分確定網絡的覆蓋集的邊界。文獻［16］基于Voronoi圖構造節點的最大獨立集提出冗余節點休眠的思想。利用最少數量的節點達到網絡的全覆蓋，并提出利用構造最小生成樹尋找節點最大獨立集的多項式時間近似算法。文獻［17］利用Voronoi劃分和Delaunay三角剖分對傳感器網絡進行分割，判別重復覆蓋目標區域的冗余傳感器節點，采用節點到sink點的跳數對節點分層，進而提出選擇休眠節點的方法。文獻［18］提出一種基于Voronoi圖的無線傳感器網絡覆蓋算法，先找出最大可能盲點，然后重新部署節點，以達到用最少的節點獲得最大的監測面積。文獻［19-21］均利用Voronoi劃分網絡，設計尋找網絡最小連通覆蓋集的算法，解決網絡全覆蓋問題。文獻［22］利用Voronoi尋找泰森多邊形解決網絡覆蓋控制問題。本文的思想為尋找網絡中可休眠的冗余節點，采用節點輪換休眠的方式，在減少基站周圍重要節點負載的前提下，同時降低單個節點的能量消耗，使得網絡中的節點能量消耗更加均衡，有效延長了網絡的生命周期。與文獻［16-22］的思想不同的是：節點在休眠后，需要等待再次喚醒。每一輪在保證網絡全覆蓋的前提下，總是能量最少的節點先休眠。保證網絡的能量得到最大程度的均衡?；谶@種想法本文提出了冗余節點判定定理，設計了FBSW算法尋找網絡中可休眠的冗余節點，有效地延長網絡的生命周期。仿真結果證明本文給出的算法是合理有效的。

1　預備知識

定義1［23］（Voronoi劃分）給定二維平面R2上的一個有限點集S=｛s1，s2，…，sn｝。與之相關聯的Voronoi區域表示為：

本文中以傳感器節點集作為Voronoi圖的產生點集，用Vor（V）表示。Vor（V）構成網絡目標區域G的一個劃分，用Vor（V，G）表示。

定義2［23］（完全覆蓋）給定無線傳感器網絡G=（V，E）和目標區域G′，設覆蓋點集為V′?V。

Rs為節點的探測半徑，稱為關于vi的探測區域，C（V′）表示關于覆蓋節點集V′的有界Voronoi劃分區域集合。若滿足

當G′=G時，稱C（V′）為G的完全覆蓋集。

定義3［23］（冗余節點）將網絡圖G進行Voronoi劃分，若刪除節點vi，對網絡圖G進行第2輪Voronoi劃分，C（V′）=那么vi稱為網絡G的冗余節點。

在以后的討論中，E（vi）（V，R）表示C（vi）（V，R）的邊界集，其中包括網絡的邊界；V（vi）（V，R）表示C（vi）（V，R）的頂點集，包括Voronoi區域的頂點和與G的區域邊界相交的點；N（vi）（V，R）表示vi節點的鄰居節點集。

圖1　無線傳感器網絡的Voronoi劃分

在提出冗余節點的劃分定理之前，首先引入以下3則引理：

引理1［23-24］對于任意vj∈V-vi-N（vi）（V，R），則有C（vi）（Vvi，R）=C（vi）（V，R）.

定義4（類凸多邊形區域）由于網絡W區域是以R為半徑的圓心區域，W為以頂點集V為產生點集的Voronoi區域均為有界區域，若Voronoi區域的頂點與網絡W的邊界不相交，則這樣的Voronoi區域為凸多邊形區域，否則稱為類凸多邊形區域。

引理2如果類凸多邊形區域頂點均包含于圓上，則類凸多邊形區域包含于圓上。

引理3［23-24］C（vi）（V，R）?S（vi）（V，R）的充分必要條件是V（vi）（V，R）?S（vi）（V，R）。

首先根據以上3則引理，提出基于Voronoi的冗余節點判定定理。

2　基于Voronoi劃分的冗余節點檢測算法

2.1冗余節點判定定理

定理1節點vi∈V是冗余節點，當且僅當?vj∈N（vj）（V，R）時，刪除vi并對網絡G進行二次Voronoi劃分后，對于任意點p∈V（vj）（V/vi，R）-V（vj）（V，R），均滿足d（p，vj）≤Rs。

證明假設節點vi∈V是冗余節點。對于任意vj∈N（vi）（V，R），刪除vi并對網絡G進行二次Voronoi劃分后，存在p∈V（vj）（V/vi，R）-V（vj）（V，R），使得d（p，vj）＞Rs。即p?S（vj）。根據引理3，則有C（vi）（V，R）?S（vi）（V，R）。這與vi∈V是冗余節點矛盾，所以假設不成立。那么當節點vi∈V是冗余節點，當對于任意點vj∈N（vj）（V，R），刪除vi后對網絡G進行二次Voronoi劃分，對于任意點，均滿足d（p，vj）≤Rs。

反之，存在vj∈N（vi）（V，R），若刪除節點vi且對網絡進行二次Voronoi劃分后，對于任意點p∈V（vj）（V/vi，R）-V（vj）（V，R），均滿足d（p，vj）≤Rs。所以對于任意點vj∈N（vj）（V，R），存在V（vj）（N（vi），R）?S（vj）（N（vi），R），根據引理2、引理3，可得C（vj）（N（vi），R）?S（vj）（N（vi），R）。根據引理1，對于任意點vk∈V-vi-N（vi）（V，R），滿足C（vi）（Vvi，R）=C（vk）（V，R）。所以C（vi）（V，vi，R）?S（vi）（V，vi，R）等價那么vi是冗余節點。

利用此定理可找到網絡中的冗余節點，其算法步驟如下。

識別冗余節點算法（IRN算法）

輸入：無線傳感器網絡G=（V，E），節點集V=｛vi｝（i=1，2，…，n）。

輸出：冗余節點集VR

步驟1初始冗余節點集VR為空。

步驟2構造Voronoi圖Vor（V，G），如果V不為空，根據定理1尋找冗余節點vi。

步驟3當vi為冗余節點，則vi加入到冗余節點集VR中，從節點集V中刪除vi

步驟4集合V不為空，則返回到步驟2，否則算法結束。

2.2冗余節點分類

定理1給出了判定網絡中冗余節點的依據。但不得不注意到，同時刪除互為鄰居的冗余節點可能會形成網絡中新的探測漏洞，造成不必要的損失。所以，并非所有的冗余節點都可以休眠。為此，將冗余節點進一步分類［24］。

定義5（絕對冗余節點和相對冗余節點）若vi是網絡中的冗余節點，當vi的鄰居節點集N（vi）（V，R）中只存在非冗余節點時，這樣的vi被稱為絕對冗余節點。否則為相對冗余節點。

由以上定義可知，由于絕對冗余節點的鄰居節點均為非冗余節點，因此刪除絕對冗余節點不會影響網絡的完全覆蓋。而直接刪除相對冗余節點可能會給網絡帶來新的覆蓋空洞。但相對冗余節點集中仍存在很大一部分節點可以休眠且并不影響網絡的完全覆蓋，如果保留所有的相對冗余節點，同樣會造成網絡能量的不必要消耗。由此，問題轉化為尋找相對冗余節點中的大量可休眠冗余節點。

同時刪除網絡中絕對冗余節點和必須節點及其相關聯的邊，刪除與距離基站Maxd（vi，BS）以內的S2中的節點及相關聯的邊，剩余部分為相對冗余節點及其相關聯的邊組成的G的子圖G′。那么，只需在G′中尋找最大可休眠節點集。

節點分類算法（CRN算法）如下：

輸入：冗余節點集VR=｛v1，v2，…，vn｝，標記ARV為絕對冗余節點集，RRV為相對冗余節點集

輸出：分類節點集ARV和RRV

步驟1初始ARV和RRV為空

步驟2對于冗余節點vi∈VR，當vi的鄰居節點集N（vi）（V，R）中只存在非冗余節點時，vi屬于ARV，否則屬于RRV。

步驟3將vi從VR中刪除，當VR不為空，返回到步驟2，否則算法結束。

2.3FBSW算法

本文算法的核心思想是尋找最大可休眠冗余節點集合，在不影響網絡覆蓋的前提下使得最大可休眠冗余節點集合中節點休眠，由此設計了最大權最小覆蓋的啟發式算法FBSW。

輸入：無線傳感器網絡G=（V，E）

輸出：最大可休眠的節點集合為I（v）

步驟1尋找冗余節點集VR。

步驟2如果VR不為空，尋找相對冗余節點集RRV。

步驟3如果相對冗余節點集RRV不為空，標記相對冗余節點為頂點的圖G（RRV（v）），RRV（v）=｛（vi，wi，di）｝（i=1，2，…，n），di為節點度.wi節點剩余最大能量.I（v）為可休眠節點集。

①初始I（v）為空，絕對冗余節點數為a

②選擇具有最小度的節點集，比較其中節點的剩余能量，選擇節點vi為能量最少的節點作為初始可休眠的節點。

③從G（RRV（v））中去掉vi、相應的邊E（vi）及連接節點N（vi），則相對冗余節點集中將刪除vi和連接節點N（vi），同時vi加入到可休眠節點集I（v）。

④若RRV（v）不為空，則返回到②，否則算法繼續。

步驟4如果絕對冗余節點集ARV不為空，則I（v）中還將包含絕對冗余節點集；

步驟5V中刪除I（v），若V不為空，則返回步驟2，否則算法結束。

利用算法，可以尋找到網絡G中同時休眠的最大冗余節點集。特別的，當網絡的規模較大時，網絡中的瓶頸節點負載會大大減少。而同時以最少的節點數達到了完全覆蓋目的。

2.4算法復雜度分析

定理算法FBSW的復雜度為O（n3logn）。

證明假設本文中構造Voronoi圖的方法為分治法，那么其復雜度為O（nlogn）［25］，算法IRN算法第3步的的時間復雜度為O（nlogn），第4步循環最大時間消耗為O（n3logn），所以算法IRN的最大時間開銷不過O（n3logn）。CRN算法的時間開銷最多為O（n3）。尋找最大休眠冗余節點集的FBS算法，第3步開始是一個大循環，但其中的嵌套循環均可在常數時間內完成。所以此算法的時間復雜度為O（n）。最終算法FBSW調用了以上3個子算法，那么其算法復雜度為（O（n3logn）+ O（n3）+O（n）），所以，算法FBSW的時間復雜度為O（n3logn）。

3　仿真模擬

本文利用Matlab 7.0作為仿真工具，運行環境是內存為512 MB，操作系統為Windows XP的PC機。

3.1定理仿真

本文中定理1是算法設計的基礎，下面將定理1進行仿真，證明其的確是有效的。仿真環境，模擬網絡范圍為120×180的矩形區域，隨機布撒19個節點，并記標記節點半徑。

圖2中選擇3個節點的坐標分別為（120，62），（121，65），（130，77），當感知半徑為15時，顯然節點（121，65）為冗余節點，這個節點是可以休眠的。節點之間的距離顯然比感知半徑要小，并且區域被完全覆蓋。

圖2　冗余節點示意圖

圖3刪除冗余節點示意圖

圖3表示刪除坐標為（120，65）的節點后，仍然在感知半徑為15的環境下，區域仍然被完全覆蓋，所以當節點之間的距離小于感知半徑時，節點是可以被刪除的。并且刪除后，網絡區域仍然被覆蓋。

3.2算法仿真

在算法仿真實驗中，仿真的網絡區域為半徑R= 10的圓形區域。

由于本算法在貪婪算法基礎上進行改進，下面做了與貪婪算法運行時間的對照。

表1列出在不同探測半徑隨機節點數目分別為200、300、400的情況下兩種算法運行時間的比較?？梢钥吹?，FBSW算法的運行時間遠小于貪婪算法。這表明FBSW算法的復雜度優于貪婪算法。

表1　FBSW算法與Greedy算法運行時間對照

由表2可以看出，當探測半徑增大且節點與基站的距離增大時，能量節約率呈現增加的趨勢。也就是說，如果加大節點的工作功率，網絡中節點的能量消耗將得到大幅度的降低。

表2　遞增探測半徑能量節約率

由表3可以得到，當節點的探測半徑為1，隨著節點與基站的距離增大，節點的能量節約率基本保持在21%以上。那么整個網絡的能量消耗率將降低21%以上。

表3　不同位置相同探測半徑節點對應可休眠節點數與能量節約率

通過FBSW算法，單個節點的能量平均可以節省至少21.01%。這表明FBSW算法可以有效地平衡整個網絡的能量消耗并延緩了單個節點的能量消耗時間。

圖4表示運行FBSW算法前后的網絡平均能量消耗情況比較。運行條件為目標半徑R=10，節點探測半徑r=1，節點總數為1 024。并假設r≥4時，不存在可休眠冗余節點。圖中紅色虛線條表示原始網絡節點平均能量消耗情況，藍色實線條表示利用FBSW算法使得節點平均能量消耗較原始網絡有大幅度的減少，使得網絡中節點能量消耗趨于均衡。

圖4　運行FBSW算法前后平均負載比較R=10，r=1，n=1024

圖5　算法運行前后能量消耗比較R=10，r=1，n=1225

圖5同樣表示運行FBSW算法前后的網絡平均能量消耗情況比較。運行條件為目標半徑R=10，節點探測半徑r=1，節點總數為1 024。網絡中均存在可休眠的冗余節點。紅色虛線條表示網絡中原始節點平均能量消耗情況。藍色實線條表示運行FBSW算法后，網絡中節點的平均能量消耗情況。那么，網絡的平均能量消耗明顯降低。

4　結語

本文基于Voronoi劃分的方法，提出了冗余節點判定方法并用數學推理證明其正確性。設計了求最小覆蓋集的啟發式算法FBSW。算法FBSW包含三個子算法，分別為識別冗余節點的IRN算法、對冗余節點分類的CRN算法和構造最大獨立集的FBS算法。最后用仿真結果說明在同等條件的網絡中，算法FBSW比貪婪算法運行時間更短，重要節點的能量被節約至少21.01%。本算法適用于節點較多的大型網絡，具有一定的實用價值。

［1］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14（7）：1282-1291.

［2］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京：清華大學出版社，2005.

［3］崔洋，郭坤亮，何麗莉，等.基于無線傳感器網絡的傳統發酵過程監測系統［J］.儀器儀表學報，2010，31（7）：1490-1495.

［4］王驥，沈玉利，林菁.基于無線傳感器網絡生理參數采集系統設計［J］.電子測量與儀器學報，2009，23（2）：94-99.

［5］曾梅梅，蔣華，王鑫.一種新的無線傳感器網絡惡意節點追蹤方法［J］.傳感技術學報，2013，26（1）：122-127.

［6］李明.基于差分算法的異構無線傳感器網絡多重覆蓋節點調度方案［J］.傳感技術學報，2012，25（6）：826-830.

［7］Tan Li，Chen Yucheng，Yang Minh，et al.Priority Coverage Algo?rithm and Performance Simulation for Node Deployment in Direc?tional Sensor Networks［J］.Sensor Letters，2014，12（2）：275-280.

［8］Xiao Yang L，Kai Liang W，Yanmin Z，et al.Mobility Increases the Surface Coverage of Distributed Sensor Networks［J］.Comput?er Networks，2013，57：2348-2361.

［9］Wei L，Wei Z.Coverage Hole and Boundary Nodes Detection in Wireless Sensor Networks［J］.Journal of Network and Computer Application，2015，45：35-43.

［10］陽娣蘭，謝政，陳摯，等.無線傳感器網絡中能耗均衡的覆蓋控制算法［J］.計算機工程與科學，2008，30（12）：15-18.

［11］底欣，張百海.傳感器網絡層級結構路徑覆蓋控制方法［J］.儀器儀表學報，2011，32（11）：2416-2422.

［12］田一鳴，陸陽，魏臻，等.無線傳感器網絡虛擬力覆蓋控制及節能優化研究［J］.電子測量與儀器學報，2009，23（11）：65-71.

［13］呂紅芳，張浩.鏈首節點輪換的無線傳感器網絡路由算法研究［J］.電子測量與儀器學報，2013，27（7）：610-616.

［14］葉啟明.無線傳感器網絡定位算法的睡眠調度技術研究［J］.廣州石油化工學院學報，2014，24（4）：34-37.

［15］So A M C，Ye Y Y.On Solving Coverage Problems in a Wireless Sensor Network Using Voronoi Diagrams［J］.Internet and Net?work Economics，2005，3828：584-593.

［16］蔣杰，方力，張鶴穎，等.無線傳感器網絡最小連通覆蓋集問題求解算法［J］.軟件學報，2006，17（2）：175-184.

［17］馬震，劉云，沈波.一種無線傳感器網絡的能耗平衡覆蓋模型［J］.電子與信息學報，2008，30（9）：2250-2253.

［18］楊海靂，趙靜.基于Voronoi圖的無線傳感器網絡覆蓋算法研究［J］.信息通信，2015，7：28-30.

［19］陸克中，孫宏元.無線傳感器網絡最小覆蓋集的貪婪近似算法［J］.軟件學報，2010，10（21）：2656-2665.

［20］秦澤峰，譚瑛，趙靜，等.基于Voronoi圖的無線傳感器網絡覆蓋算法研究［J］.太原科技大學學報，2013，34（3）：185-189.

［21］陳業綱，徐則同.無線傳感器網絡最小連通覆蓋的節能算法［J］.計算機仿真，2014，31（3）：324-350.

［22］方偉，宋鑫宏.基于Voronoi圖盲區的無線傳感器網絡覆蓋控制部署策略［J］.物理學報，2014，63（22）：220701-1-10.

［23］CARBUNAR B，GRAMA A，VITEK J.Distributed and Dynamic Voronoi Overlays for Coverage Detection and Distributed Hash Ta?bles in Ad-Hoc Networks［C］//Proceedings of the Tenth Interna?tional Conference on Parallel and Distributed Systems.2004，7：549-556.

［24］周培德.計算幾何［M］.北京：清華大學出版社，2000.

［25］徐玖平，胡志能.中級運籌學［M］.北京：科學出版社，2008.

高潔（1983-），女，2007年于山東大學威海分校獲得學士學位，2010年于華東理工大學獲得碩士學位，現為山東華宇工學院基礎部講師，主要研究方向為為通信網絡可靠性和優化算法，jiegao_1983@ 163.com；

吳延紅（1982-），女，研究生（碩士），畢業于南開大學，現為山東華宇工學院基礎部講師，研究方向為小波分析與信號處理。

The Minimum Coverage Energy Optimization Algorithms in Wireless Sensor Network

GAO Jie1*，WU Yanhong1，BAI Jianxia2，LI Qi1
（1.Foundation Department，Shandong Huyu University of Technology，Dezhou Shandong 253000，China；2.Mathematics department，Ren’ai College of Tianjin University，Tianjin 301636，China）

Nodes around the base station are charged with the task for transferring a large of data to the base station in wireless sensor networks.Therefore，these nodes consume more energy than others.In order to balance the energy consumption of nodes around the base station，this paper puts forword a reasonable and effective node rotation mech?anism.A large number of redundant nodes turn to dormancy so that the load of nodes is reduced around the base sta?tion.A redundant nodes decision theorem is proposed based on the mechanism.The maximum dormant node set is found based on the Voronoi diagram.The Minimum Connected Coverage algorithm（FBSW）is proposed to find out the redundant nodes which can be dormant and to prolong the network lifetime.The Simulation results show that the operation complexity of the FBSW algorithm is superior to the Greedy algorithm.On account of the redundant nodes which turn to dormancy，the energy of the network is saved by 21.01%.

the wireless sensor networks；Voronoi；the minimum connected coverage set；inactive nodes；energy bal?ance

TK393.03；TP212.9

A

1004-1699（2016）09-1435-06

項目來源：國家自然科學基金項目（11471167）

2015-12-29修改日期：2016-05-03