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

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

無線傳感器網(wǎng)絡(luò)最小覆蓋能量優(yōu)化算法*

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

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

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

無線傳感器網(wǎng)絡(luò)；Voronoi圖；最小連通覆蓋集；休眠節(jié)點；能量均衡；

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

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

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

1　預(yù)備知識

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

本文中以傳感器節(jié)點集作為Voronoi圖的產(chǎn)生點集，用Vor（V）表示。Vor（V）構(gòu)成網(wǎng)絡(luò)目標區(qū)域G的一個劃分，用Vor（V，G）表示。

定義2［23］（完全覆蓋）給定無線傳感器網(wǎng)絡(luò)G=（V，E）和目標區(qū)域G′，設(shè)覆蓋點集為V′?V。

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

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

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

在以后的討論中，E（vi）（V，R）表示C（vi）（V，R）的邊界集，其中包括網(wǎng)絡(luò)的邊界；V（vi）（V，R）表示C（vi）（V，R）的頂點集，包括Voronoi區(qū)域的頂點和與G的區(qū)域邊界相交的點；N（vi）（V，R）表示vi節(jié)點的鄰居節(jié)點集。

圖1　無線傳感器網(wǎng)絡(luò)的Voronoi劃分

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

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

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

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

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

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

2　基于Voronoi劃分的冗余節(jié)點檢測算法

2.1冗余節(jié)點判定定理

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

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

反之，存在vj∈N（vi）（V，R），若刪除節(jié)點vi且對網(wǎng)絡(luò)進行二次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），根據(jù)引理2、引理3，可得C（vj）（N（vi），R）?S（vj）（N（vi），R）。根據(jù)引理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是冗余節(jié)點。

利用此定理可找到網(wǎng)絡(luò)中的冗余節(jié)點，其算法步驟如下。

識別冗余節(jié)點算法（IRN算法）

輸入：無線傳感器網(wǎng)絡(luò)G=（V，E），節(jié)點集V=｛vi｝（i=1，2，…，n）。

輸出：冗余節(jié)點集VR

步驟1初始冗余節(jié)點集VR為空。

步驟2構(gòu)造Voronoi圖Vor（V，G），如果V不為空，根據(jù)定理1尋找冗余節(jié)點vi。

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

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

2.2冗余節(jié)點分類

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

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

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

同時刪除網(wǎng)絡(luò)中絕對冗余節(jié)點和必須節(jié)點及其相關(guān)聯(lián)的邊，刪除與距離基站Maxd（vi，BS）以內(nèi)的S2中的節(jié)點及相關(guān)聯(lián)的邊，剩余部分為相對冗余節(jié)點及其相關(guān)聯(lián)的邊組成的G的子圖G′。那么，只需在G′中尋找最大可休眠節(jié)點集。

節(jié)點分類算法（CRN算法）如下：

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

輸出：分類節(jié)點集ARV和RRV

步驟1初始ARV和RRV為空

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

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

2.3FBSW算法

本文算法的核心思想是尋找最大可休眠冗余節(jié)點集合，在不影響網(wǎng)絡(luò)覆蓋的前提下使得最大可休眠冗余節(jié)點集合中節(jié)點休眠，由此設(shè)計了最大權(quán)最小覆蓋的啟發(fā)式算法FBSW。

輸入：無線傳感器網(wǎng)絡(luò)G=（V，E）

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

步驟1尋找冗余節(jié)點集VR。

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

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

①初始I（v）為空，絕對冗余節(jié)點數(shù)為a

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

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

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

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

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

利用算法，可以尋找到網(wǎng)絡(luò)G中同時休眠的最大冗余節(jié)點集。特別的，當網(wǎng)絡(luò)的規(guī)模較大時，網(wǎng)絡(luò)中的瓶頸節(jié)點負載會大大減少。而同時以最少的節(jié)點數(shù)達到了完全覆蓋目的。

2.4算法復(fù)雜度分析

定理算法FBSW的復(fù)雜度為O（n3logn）。

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

3　仿真模擬

本文利用Matlab 7.0作為仿真工具，運行環(huán)境是內(nèi)存為512 MB，操作系統(tǒng)為Windows XP的PC機。

3.1定理仿真

本文中定理1是算法設(shè)計的基礎(chǔ)，下面將定理1進行仿真，證明其的確是有效的。仿真環(huán)境，模擬網(wǎng)絡(luò)范圍為120×180的矩形區(qū)域，隨機布撒19個節(jié)點，并記標記節(jié)點半徑。

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

圖2　冗余節(jié)點示意圖

圖3刪除冗余節(jié)點示意圖

圖3表示刪除坐標為（120，65）的節(jié)點后，仍然在感知半徑為15的環(huán)境下，區(qū)域仍然被完全覆蓋，所以當節(jié)點之間的距離小于感知半徑時，節(jié)點是可以被刪除的。并且刪除后，網(wǎng)絡(luò)區(qū)域仍然被覆蓋。

3.2算法仿真

在算法仿真實驗中，仿真的網(wǎng)絡(luò)區(qū)域為半徑R= 10的圓形區(qū)域。

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

表1列出在不同探測半徑隨機節(jié)點數(shù)目分別為200、300、400的情況下兩種算法運行時間的比較?？梢钥吹?，F(xiàn)BSW算法的運行時間遠小于貪婪算法。這表明FBSW算法的復(fù)雜度優(yōu)于貪婪算法。

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

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

表2　遞增探測半徑能量節(jié)約率

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

表3　不同位置相同探測半徑節(jié)點對應(yīng)可休眠節(jié)點數(shù)與能量節(jié)約率

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

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

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

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

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

4　結(jié)語

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

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

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

［3］崔洋，郭坤亮，何麗莉，等.基于無線傳感器網(wǎng)絡(luò)的傳統(tǒng)發(fā)酵過程監(jiān)測系統(tǒng)［J］.儀器儀表學報，2010，31（7）：1490-1495.

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

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

［6］李明.基于差分算法的異構(gòu)無線傳感器網(wǎng)絡(luò)多重覆蓋節(jié)點調(diào)度方案［J］.傳感技術(shù)學報，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］陽娣蘭，謝政，陳摯，等.無線傳感器網(wǎng)絡(luò)中能耗均衡的覆蓋控制算法［J］.計算機工程與科學，2008，30（12）：15-18.

［11］底欣，張百海.傳感器網(wǎng)絡(luò)層級結(jié)構(gòu)路徑覆蓋控制方法［J］.儀器儀表學報，2011，32（11）：2416-2422.

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

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

［14］葉啟明.無線傳感器網(wǎng)絡(luò)定位算法的睡眠調(diào)度技術(shù)研究［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］蔣杰，方力，張鶴穎，等.無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法［J］.軟件學報，2006，17（2）：175-184.

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

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

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

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

［21］陳業(yè)綱，徐則同.無線傳感器網(wǎng)絡(luò)最小連通覆蓋的節(jié)能算法［J］.計算機仿真，2014，31（3）：324-350.

［22］方偉，宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略［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年于華東理工大學獲得碩士學位，現(xiàn)為山東華宇工學院基礎(chǔ)部講師，主要研究方向為為通信網(wǎng)絡(luò)可靠性和優(yōu)化算法，jiegao_1983@ 163.com；

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

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