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

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

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

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

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

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

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

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

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

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

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

1　預(yù)備知識(shí)

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

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

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

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

當(dāng)G′=G時(shí)，稱C（V′）為G的完全覆蓋集。

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

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

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

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

引理1［23-24］對(duì)于任意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為以頂點(diǎn)集V為產(chǎn)生點(diǎn)集的Voronoi區(qū)域均為有界區(qū)域，若Voronoi區(qū)域的頂點(diǎn)與網(wǎng)絡(luò)W的邊界不相交，則這樣的Voronoi區(qū)域?yàn)橥苟噙呅螀^(qū)域，否則稱為類凸多邊形區(qū)域。

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

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

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

2　基于Voronoi劃分的冗余節(jié)點(diǎn)檢測(cè)算法

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

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

證明假設(shè)節(jié)點(diǎn)vi∈V是冗余節(jié)點(diǎn)。對(duì)于任意vj∈N（vi）（V，R），刪除vi并對(duì)網(wǎng)絡(luò)G進(jìn)行二次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é)點(diǎn)矛盾，所以假設(shè)不成立。那么當(dāng)節(jié)點(diǎn)vi∈V是冗余節(jié)點(diǎn)，當(dāng)對(duì)于任意點(diǎn)vj∈N（vj）（V，R），刪除vi后對(duì)網(wǎng)絡(luò)G進(jìn)行二次Voronoi劃分，對(duì)于任意點(diǎn)，均滿足d（p，vj）≤Rs。

反之，存在vj∈N（vi）（V，R），若刪除節(jié)點(diǎn)vi且對(duì)網(wǎng)絡(luò)進(jìn)行二次Voronoi劃分后，對(duì)于任意點(diǎn)p∈V（vj）（V/vi，R）-V（vj）（V，R），均滿足d（p，vj）≤Rs。所以對(duì)于任意點(diǎn)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，對(duì)于任意點(diǎn)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）等價(jià)那么vi是冗余節(jié)點(diǎn)。

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

識(shí)別冗余節(jié)點(diǎn)算法（IRN算法）

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

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

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

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

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

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

2.2冗余節(jié)點(diǎn)分類

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

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

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

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

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

輸入：冗余節(jié)點(diǎn)集VR=｛v1，v2，…，vn｝，標(biāo)記ARV為絕對(duì)冗余節(jié)點(diǎn)集，RRV為相對(duì)冗余節(jié)點(diǎn)集

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

步驟1初始ARV和RRV為空

步驟2對(duì)于冗余節(jié)點(diǎn)vi∈VR，當(dāng)vi的鄰居節(jié)點(diǎn)集N（vi）（V，R）中只存在非冗余節(jié)點(diǎn)時(shí)，vi屬于ARV，否則屬于RRV。

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

2.3FBSW算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　仿真模擬

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

3.1定理仿真

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

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

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

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

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

3.2算法仿真

在算法仿真實(shí)驗(yàn)中，仿真的網(wǎng)絡(luò)區(qū)域?yàn)榘霃絉= 10的圓形區(qū)域。

由于本算法在貪婪算法基礎(chǔ)上進(jìn)行改進(jìn)，下面做了與貪婪算法運(yùn)行時(shí)間的對(duì)照。

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

表1　FBSW算法與Greedy算法運(yùn)行時(shí)間對(duì)照

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

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

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

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

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

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

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

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

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

4　結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

［13］呂紅芳，張浩.鏈?zhǔn)坠?jié)點(diǎn)輪換的無(wú)線傳感器網(wǎng)絡(luò)路由算法研究［J］.電子測(cè)量與儀器學(xué)報(bào)，2013，27（7）：610-616.

［14］葉啟明.無(wú)線傳感器網(wǎng)絡(luò)定位算法的睡眠調(diào)度技術(shù)研究［J］.廣州石油化工學(xué)院學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法［J］.軟件學(xué)報(bào)，2006，17（2）：175-184.

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

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

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

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

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

［22］方偉，宋鑫宏.基于Voronoi圖盲區(qū)的無(wú)線傳感器網(wǎng)絡(luò)覆蓋控制部署策略［J］.物理學(xué)報(bào)，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］周培德.計(jì)算幾何［M］.北京：清華大學(xué)出版社，2000.

［25］徐玖平，胡志能.中級(jí)運(yùn)籌學(xué)［M］.北京：科學(xué)出版社，2008.

高潔（1983-），女，2007年于山東大學(xué)威海分校獲得學(xué)士學(xué)位，2010年于華東理工大學(xué)獲得碩士學(xué)位，現(xiàn)為山東華宇工學(xué)院基礎(chǔ)部講師，主要研究方向?yàn)闉橥ㄐ啪W(wǎng)絡(luò)可靠性和優(yōu)化算法，jiegao_1983@ 163.com；

吳延紅（1982-），女，研究生（碩士），畢業(yè)于南開大學(xué)，現(xiàn)為山東華宇工學(xué)院基礎(chǔ)部講師，研究方向?yàn)樾〔ǚ治雠c信號(hào)處理。

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

項(xiàng)目來源：國(guó)家自然科學(xué)基金項(xiàng)目（11471167）

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