張清國，張勇，張偉，席瑞潔

（1.華中師范大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430079；2.華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430074）

0 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）廣泛應(yīng)用于環(huán)境監(jiān)控、反恐救災(zāi)、軍事、醫(yī)療健康、動(dòng)物跟蹤等領(lǐng)域［1］。傳統(tǒng)的靜態(tài)WSN 完全由固定傳感器組成，所有的傳感器在部署完之后位置都保持不變，只能通過將網(wǎng)絡(luò)中部署的冗余傳感器從睡眠狀態(tài)喚醒的方法來完成覆蓋洞修補(bǔ)，該覆蓋洞修補(bǔ)方式需要監(jiān)控區(qū)域能被傳感器網(wǎng)絡(luò)全覆蓋，而這在敵對(duì)或惡劣的自然環(huán)境中（如戰(zhàn)場(chǎng)、森林火場(chǎng)等）是不切實(shí)際的，在這些場(chǎng)景中很難對(duì)WSN 進(jìn)行人工部署。通過飛機(jī)撒播、火箭彈射等隨機(jī)部署方式，在遇到障礙物時(shí)即使提高節(jié)點(diǎn)的部署密度，也難以一次就將所有傳感器部署到適當(dāng)?shù)奈恢?，極易造成節(jié)點(diǎn)分布過密或過疏從而形成覆蓋重疊區(qū)和覆蓋盲區(qū)，難以實(shí)現(xiàn)區(qū)域全覆蓋。

近年來，研究人員提出由固定傳感器和移動(dòng)傳感器組成的混合無線傳感器網(wǎng)絡(luò)（Hybrid Wireless Sensor Network，HWSN）［2-3］，與完全由固定傳感器組成的靜態(tài)WSN 不同，HWSN 可以對(duì)移動(dòng)傳感器進(jìn)行重新部署［4-5］，修復(fù)傳感器網(wǎng)絡(luò)由于節(jié)點(diǎn)分布不均或節(jié)點(diǎn)因能量耗盡而失效等原因形成的覆蓋洞［6-7］，從而優(yōu)化網(wǎng)絡(luò)覆蓋性能［8-10］。

針對(duì)HWSN 的覆蓋控制問題，學(xué)術(shù)界進(jìn)行了大量研究。文獻(xiàn)［11-13］提出基于虛擬力的WSN 覆蓋算法，但該算法容易陷入局部最優(yōu)，導(dǎo)致網(wǎng)絡(luò)覆蓋優(yōu)化失敗。由于覆蓋問題是NP-難問題［14］，因此研究人員將各種智能算法應(yīng)用于HWSN 覆蓋控制任務(wù)，如魚群算法［15-17］、遺傳算法［18-20］、差分演化算法［21-22］、蟻群算法［23-25］、粒子群算法［26-27］等，且取得了較好的效果，但是，這些方法存在的最大問題是算法時(shí)間復(fù)雜度高，計(jì)算量大，收斂速度慢，有時(shí)甚至收斂于局部最優(yōu)解，導(dǎo)致覆蓋優(yōu)化失敗。

在HWSN 中，能耗主要來源于2 個(gè)方面，即相鄰傳感器之間的通信以及移動(dòng)傳感器節(jié)點(diǎn)的機(jī)械運(yùn)動(dòng)。文獻(xiàn)［28］指出，將移動(dòng)傳感器節(jié)點(diǎn)移動(dòng)1 m 所消耗的能量是傳感器發(fā)送一個(gè)消息所消耗能量的300 倍，因此，HWSN 的能耗主要體現(xiàn)在重新部署移動(dòng)傳感器位置時(shí)移動(dòng)傳感器所耗費(fèi)的能量。本文用移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離（Average Moving Distance，AMD）作為移動(dòng)傳感器機(jī)械運(yùn)動(dòng)能耗的度量標(biāo)準(zhǔn)，因此，優(yōu)化移動(dòng)節(jié)點(diǎn)的AMD 具有十分重要的意義。文獻(xiàn)［29］提出一種基于蜂窩結(jié)構(gòu)的HWSN 覆蓋優(yōu)化算法HWSNBCS，根據(jù)移動(dòng)節(jié)點(diǎn)和其倍感知半徑范圍內(nèi)固定節(jié)點(diǎn)間的位置關(guān)系，基于蜂窩結(jié)構(gòu)和漏洞修補(bǔ)策略對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行重新部署，以改善網(wǎng)絡(luò)的覆蓋性能。該算法包括2 個(gè)階段：第一階段基于蜂窩結(jié)構(gòu)計(jì)算每個(gè)移動(dòng)傳感器的候選目標(biāo)位置，其中，算法給出了4 種情況下移動(dòng)節(jié)點(diǎn)的移動(dòng)方案；第二階段對(duì)所有移動(dòng)節(jié)點(diǎn)的候選目標(biāo)位置進(jìn)行進(jìn)一步優(yōu)化，確定移動(dòng)節(jié)點(diǎn)的最終目標(biāo)位置。算法通過移動(dòng)傳感器移動(dòng)距離優(yōu)化算法來減少移動(dòng)傳感器的AMD，從而降低移動(dòng)節(jié)點(diǎn)的能耗，確定移動(dòng)節(jié)點(diǎn)的最終目標(biāo)位置。HWSNBCS 算法能顯著改善網(wǎng)絡(luò)的覆蓋性能，且執(zhí)行效率較高，但算法第二階段的移動(dòng)傳感器移動(dòng)距離優(yōu)化算法只是通過簡(jiǎn)單地將移動(dòng)傳感器的候選目標(biāo)位置兩兩互換，以尋找移動(dòng)節(jié)點(diǎn)移動(dòng)距離的可能優(yōu)化結(jié)果，這種啟發(fā)式方法得到的解不一定是最優(yōu)解，本文將在第2 章對(duì)其進(jìn)行例證和分析。

本文將HWSN 移動(dòng)節(jié)點(diǎn)移動(dòng)距離之和最小化問題轉(zhuǎn)化為二分圖最優(yōu)匹配問題，用帶權(quán)二分圖匹配算法KM（Kuhn-Munkres）對(duì)文獻(xiàn)［29］中的HWSNBCS算法進(jìn)行改進(jìn)，具體地，利用KM 算法對(duì)HWSNBCS算法第一階段移動(dòng)節(jié)點(diǎn)的移動(dòng)距離進(jìn)行優(yōu)化，在保持算法第一階段網(wǎng)絡(luò)覆蓋率不變的前提下，減少移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離以及單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離，從而降低系統(tǒng)能耗。

1 HWSNBCS 算法

設(shè)由n個(gè)傳感器節(jié)點(diǎn)S=｛s1，s2，…，sn｝組成的HWSN 隨機(jī)分布在二維平面區(qū)域A中。為了討論方便，對(duì)HWSN 作如下假設(shè)：

1）每個(gè)傳感器都知道自己的位置信息。

2）所有傳感器的通信半徑Rc相同，感知半徑R也相同，且Rc=2R。

3）在區(qū)域A中存在一個(gè)Sink 節(jié)點(diǎn)，該節(jié)點(diǎn)負(fù)責(zé)完成算法的移動(dòng)距離優(yōu)化。

在分析HWSNBCS 算法之前先介紹算法中的2 個(gè)概念：

定義1設(shè)R為傳感器sa的感知半徑，以傳感器節(jié)點(diǎn)sa為圓心、以R為半徑的圓周稱為節(jié)點(diǎn)sa的鄰接蜂窩節(jié)點(diǎn)軌跡圓（Neighboring Cellular Node Locus Circle，NCNLC）［29］。

定義2若移動(dòng)節(jié)點(diǎn)ma在固定節(jié)點(diǎn)sa的NCNLC上，則稱sa的NCNLC為ma的候選蜂窩節(jié)點(diǎn)軌跡圓（Candidate Cellular Node Locus Circle，CCNLC）［29］。

1.1 基于蜂窩結(jié)構(gòu)的節(jié)點(diǎn)移動(dòng)策略

HWSNBCS 算法第一階段給出4 種情況下移動(dòng)傳感器的移動(dòng)方案：

1）若移動(dòng)傳感器ma的NCNLC 內(nèi)沒有固定傳感器，則ma不需要移動(dòng)［29］。如圖1 所示，虛線圓周是移動(dòng)傳感器ma的NCNLC，由于ma的NCNLC 內(nèi)沒有固定傳感器，因此ma不需要移動(dòng)。

圖1 移動(dòng)節(jié)點(diǎn)ma的NCNLC 內(nèi)無固定節(jié)點(diǎn)的情況Fig.1 No static node within the NCNLC of the mobile node ma

2）若移動(dòng)傳感器ma位于某個(gè)固定傳感器sa的NCNLC 內(nèi)，記sa的NCNLC 為⊙sa，則ma沿直線sama移動(dòng)到⊙sa上距ma較近的點(diǎn)［29］。如圖2所示，ma沿直線sama移動(dòng)到⊙sa上的A點(diǎn)。

圖2 移動(dòng)節(jié)點(diǎn)ma在某個(gè)固定節(jié)點(diǎn)NCNLC 內(nèi)的移動(dòng)方案Fig.2 Mobile scheme of mobile node ma in NCNLC of a fixed node

3）當(dāng)移動(dòng)傳感器ma位于某個(gè)固定傳感器的NCNLC 內(nèi)，且ma有一個(gè)CCNLC 時(shí)，ma移動(dòng)到CCNLC 與固定節(jié)點(diǎn)的NCNLC 的交點(diǎn)中距離ma較近的點(diǎn)［29］。如圖3 所示，ma有一個(gè)CCNLC，為sa的NCNLC，記為⊙sa，同時(shí)ma位于sb的NCNLC 內(nèi)，記sb的NCNLC 為⊙sb，則ma移動(dòng)到⊙sa與⊙sb的2 個(gè)交點(diǎn)中距離ma較近的B點(diǎn)［29］。

圖3 移動(dòng)節(jié)點(diǎn)ma只有一個(gè)CCNLC 時(shí)的移動(dòng)方案Fig.3 Mobile scheme of mobile node ma when ma has only one CCNLC

4）若移動(dòng)傳感器ma位于某個(gè)固定傳感器的NCNLC 內(nèi)，且ma有2 個(gè)CCNLC 時(shí)，ma移動(dòng)到3 個(gè)固定傳感器的NCNLC 的交點(diǎn)中距離ma較近的外層交點(diǎn)［29］。如圖4 所示，ma有2 個(gè)CCNLC，分別是固定節(jié)點(diǎn)sa、sb的NCNLC，且ma位于固定節(jié)點(diǎn)sc的NCNLC內(nèi)，則ma移動(dòng)到這3 個(gè)NCNLC 的交點(diǎn)中距離ma最近的最外層交點(diǎn)A［29］。

圖4 移動(dòng)節(jié)點(diǎn)ma有2 個(gè)CCNLC 時(shí)的移動(dòng)方案Fig.4 Mobile scheme of mobile node ma when ma has two CCNLC

1.2 節(jié)點(diǎn)移動(dòng)距離優(yōu)化

HWSNBCS 算法第二階段通過對(duì)移動(dòng)節(jié)點(diǎn)的移動(dòng)距離進(jìn)行優(yōu)化，從而確定移動(dòng)節(jié)點(diǎn)的最終目標(biāo)位置［29］。通過將移動(dòng)傳感器的候選目標(biāo)位置兩兩交換，尋找移動(dòng)節(jié)點(diǎn)移動(dòng)距離的可能優(yōu)化結(jié)果，其原理如圖5 所示。假設(shè)Pa、Pb分別為移動(dòng)節(jié)點(diǎn)ma、mb的候選目標(biāo)位置，如果|maPa|+|mbPb|＞|maPb|+|mbPa|，則交換ma、mb的候選目標(biāo)位置Pa、Pb。

圖5 HWSNBCS 算法移動(dòng)節(jié)點(diǎn)移動(dòng)距離優(yōu)化方案Fig.5 Optimization scheme of moving distance of mobile nodes in HWSNBCS algorithm

1.3 算法描述

基于蜂窩結(jié)構(gòu)的HWSN 覆蓋優(yōu)化算法HWSNBCS 描述如下：

算法1HWSNBCS 算法

輸入目標(biāo)區(qū)域A，初始節(jié)點(diǎn)集合S=｛s1，s2，…，sn｝，其中s1，s2，…，sm為移動(dòng)節(jié)點(diǎn)，其余為固定節(jié)點(diǎn)

輸出移動(dòng)節(jié)點(diǎn)重新部署的目標(biāo)位置P=｛p1，p2，…，pm｝，其中p1，p2，…，pm分別為移動(dòng)節(jié)點(diǎn)s1，s2，…，sm的新目標(biāo)位置

步驟1Fori：=1 tomdo

對(duì)移動(dòng)傳感器節(jié)點(diǎn)mi，根據(jù)圖1～圖4 所示的4 種情況，計(jì)算其候選目標(biāo)位置Pi。

步驟2隨機(jī)選取2 個(gè)移動(dòng)傳感器ma、mb，設(shè)其初始位置分別為Pa0、Pb0，當(dāng)前候選目標(biāo)位置分別為Pa1、Pb1。如果|Pa0Pa1|+|Pb0Pb1|＞|Pa0Pb1|+|Pb0Pa1|，則Pa1?Pb1，其中|·|表示節(jié)點(diǎn)之間的歐式距離。

步驟3重復(fù)步驟2，直至整個(gè)HWSN 的AMD不能減少為止。

步驟4輸出集合P。

顯然，步驟2～步驟3 不會(huì)改變整個(gè)網(wǎng)絡(luò)的覆蓋率，但可減少移動(dòng)節(jié)點(diǎn)的AMD，從而進(jìn)一步優(yōu)化移動(dòng)節(jié)點(diǎn)的布局。

2 基于蜂窩結(jié)構(gòu)的改進(jìn)HWSN 覆蓋控制算法

HWSNBCS 算法的步驟2 簡(jiǎn)單地將移動(dòng)節(jié)點(diǎn)的候選目標(biāo)位置兩兩互換，以尋找移動(dòng)節(jié)點(diǎn)移動(dòng)距離的可能優(yōu)化結(jié)果，這是一種啟發(fā)式方法，得到的解不一定是最優(yōu)解。圖6 所示為一個(gè)簡(jiǎn)單的帶權(quán)二分圖，Pa、Pb、Pc分別為移動(dòng)傳感器ma、mb、mc的候選部署位置，ma、mb、mc分別到Pa、Pb、Pc的距離如圖中所示。不失一般性，移動(dòng)傳感器按照ma、mb、mc的順序依次選擇候選部署位置，將會(huì)選擇Pb、Pa、Pc分別作為ma、mb、mc的目標(biāo)位置，3 個(gè)移動(dòng)節(jié)點(diǎn)移動(dòng)距離之和為|maPb|+|mbPa|+|mcPc|=3+5+8=16，比原來的|maPa|+|mbPb|+|mcPc|=5+4+8=17 僅減少1，但實(shí)際上最短距離之和為|maPc|+|mbPb|+|mcPa|=4+4+4=12。因 此，HWSNBCS 算法中移動(dòng)節(jié)點(diǎn)移動(dòng)距離優(yōu)化方案得到的解并非全局最優(yōu)解，移動(dòng)節(jié)點(diǎn)的移動(dòng)距離還可以進(jìn)一步優(yōu)化。

圖6 簡(jiǎn)單的帶權(quán)二分圖Fig.6 Simple weighted bipartite graph

HWSNBCS 算法中距離優(yōu)化的實(shí)質(zhì)是尋找移動(dòng)傳感器節(jié)點(diǎn)初始位置與其候選目標(biāo)位置之間的最優(yōu)匹配，使得移動(dòng)節(jié)點(diǎn)移動(dòng)距離之和最小化。為此，本文采用帶權(quán)二分圖最優(yōu)匹配算法KM 來解決這一匹配問題，以實(shí)現(xiàn)對(duì)HWSNBCS 算法的改進(jìn)。

2.1 算法描述

KM 是用于求解帶權(quán)二分圖最優(yōu)匹配問題的經(jīng)典算法。本文通過構(gòu)造帶權(quán)二分圖，將HWSN 移動(dòng)傳感器移動(dòng)距離優(yōu)化問題轉(zhuǎn)化為二分圖最優(yōu)匹配問題。設(shè)HWSN 中移動(dòng)節(jié)點(diǎn)s1，s2，…，sm的初始位置為Q=｛q1，q2，…，qm｝，qi為移動(dòng)節(jié)點(diǎn)si的初始位置，通過HWSNBCS 算法步驟1 得到的移動(dòng)節(jié)點(diǎn)候選目標(biāo)位置為P=｛p1，p2，…，pm｝，pi為移動(dòng)節(jié)點(diǎn)si的候選目標(biāo)位置。構(gòu)造帶權(quán)二分圖G=（V，E），頂點(diǎn)集V=Q∪P，邊集E=｛（u，v，wuv）|u∈Q，v∈P，wuv=-|uv|｝，wuv表示邊（u，v）的權(quán)值，為頂點(diǎn)u、v之間歐式距離的相反數(shù)。用KM 算法求出圖G的最優(yōu)匹配，即可得到移動(dòng)節(jié)點(diǎn)移動(dòng)距離之和最小化的目標(biāo)位置。本文所提基于蜂窩結(jié)構(gòu)的改進(jìn)HWSNBCS算法（IHWSNBCS）描 述如下：

算法2IHWSNBCS 算法

輸入移動(dòng)節(jié)點(diǎn)s1，s2，…，sm初始位置Q，通過HWSNBCS 算法步驟1 得到的候選目標(biāo)位置P

輸出集合Q與集合P移動(dòng)距離之和最小的匹配結(jié)果

步驟1定義初始可行頂點(diǎn)標(biāo)記L：

步驟2設(shè)El={（qi，pj）|L(qi)+L(pj)=}，Gl=(V，El}，設(shè)X為Gl的一個(gè)匹配。若Q中每個(gè)點(diǎn)都是X的飽和點(diǎn)，則X就是所求的移動(dòng)傳感器移動(dòng)距離之和最小的匹配結(jié)果，計(jì)算結(jié)束；否則，取X的非飽和點(diǎn)qi∈Q，令A(yù)=｛qi｝，B=?，A、B為2 個(gè)集合。

步驟3令(A)={pj|qi pj∈El，qi∈Q，pj∈P}，若NGL(A)=B，則Gl沒有最優(yōu)匹配，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟5。NGL(A)?P是與A中節(jié)點(diǎn)鄰接的節(jié)點(diǎn)集合。

步驟4調(diào)整可行頂點(diǎn)標(biāo)記。令d=min{L（qi）+L（pj）-|qi∈A，pj∈P-B}，按式（2）修改可行頂點(diǎn)標(biāo)記：

根據(jù)L'計(jì)算EL'及GL'，令L=L'，GL=GL'，轉(zhuǎn)步驟2。

步驟5取p∈(A) -B，若p是X的飽和點(diǎn)，轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟7。

步驟6設(shè)qp∈X，令A(yù)=A∪｛q｝，B=B∪｛p｝，轉(zhuǎn)步驟3。

步驟7GL中的（u，p）路是X增廣路，記為path，并令X=X⊕path，轉(zhuǎn)步驟2，最終求得X。

從IHWSNBCS 算法可以看出，其輸入和HWSNBCS 算法第二階段的輸入完全一樣，但HWSNBCS 算法第二階段采用啟發(fā)式方法，而IHWSNBCS 算法采用全局優(yōu)化方法，即KM 算法，KM 算法的正確性早已得到證明，因此，本文IHWSNBCS 算法能得到一個(gè)較好的解。

IHWSNBCS 算法并不改變HWSNBCS 算法的網(wǎng)絡(luò)覆蓋率，僅改變HWSNBCS 算法中移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離，這是因?yàn)镮HWSNBCS 算法只對(duì)HWSNBCS 算法移動(dòng)節(jié)點(diǎn)的初始位置和目標(biāo)位置進(jìn)行重新匹配，在整個(gè)HWSN 中，固定節(jié)點(diǎn)的位置沒有發(fā)生變化，因此，其監(jiān)測(cè)區(qū)域也沒有變化，相比HWSNBCS 算法而言，IHWSNBCS 中移動(dòng)節(jié)點(diǎn)整體監(jiān)測(cè)的區(qū)域?qū)嶋H上也沒有發(fā)生變化，變化的只是單個(gè)傳感器的監(jiān)測(cè)區(qū)域。因此，IHWSNBCS 算法傳感器節(jié)點(diǎn)的監(jiān)測(cè)區(qū)域與HWSNBCS 算法相同，即IHWSNBCS 算法并未改變HWSNBCS 算法的網(wǎng)絡(luò)覆蓋率。

2.2 復(fù)雜度分析

首先分析IHWSNBCS 算法的時(shí)間復(fù)雜度。IHWSNBCS 的輸入是運(yùn)行HWSNBCS 算法步驟1 的輸出，其時(shí)間復(fù)雜度為O（m（n-m））［29］。IHWSNBCS 算法中的KM 算法通過不斷尋找從未匹配點(diǎn)qi∈Q出發(fā)的可增廣路，以擴(kuò)充當(dāng)前的匹配情況，執(zhí)行次數(shù)為m，利用深度優(yōu)先搜索可增廣路，其時(shí)間復(fù)雜度為O（m2），即KM 算法的時(shí)間復(fù)雜度為O（m3）［30］。因 此，IHWSNBCS 算法的時(shí)間復(fù)雜度為O（mn+m3），高于HWSNBCS 算法的時(shí)間復(fù)雜度O（mn）［29］，原因是IHWSNBCS 算法要調(diào)用KM 算法，提高了運(yùn)算復(fù)雜度。

然后分析IHWSNBCS 算法的空間復(fù)雜度。IHWSNBCS 算法和HWSNBCS 算法的內(nèi)存消耗主要來源于移動(dòng)節(jié)點(diǎn)的初始位置和候選目標(biāo)位置，因此，空間復(fù)雜度均為O（m），改進(jìn)算法并未增加空間開銷。

最后分析IHWSNBCS 算法的通信復(fù)雜度。為了得到IHWSNBCS 算法的輸入而運(yùn)行HWSNBCS算法的步驟1，其通信開銷為O（m）［29］。IHWSNBCS算法中KM 算法的輸入是各移動(dòng)傳感器節(jié)點(diǎn)的初始位置和候選目標(biāo)位置，對(duì)于給定的目標(biāo)監(jiān)測(cè)區(qū)域A，設(shè)移動(dòng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包到Sink 節(jié)點(diǎn)的平均跳數(shù)為h，則移動(dòng)節(jié)點(diǎn)將其初始位置信息和候選目標(biāo)位置信息發(fā)送到Sink 節(jié)點(diǎn)的通信開銷為O（mh），Sink 節(jié)點(diǎn)將KM 算法計(jì)算出的各移動(dòng)節(jié)點(diǎn)的最終目標(biāo)位置信息發(fā)送至各移動(dòng)節(jié)點(diǎn)的通信開銷為O（mh）。因此，IHWSNBCS 算法的總通信開銷為O（mh），高于HWSNBCS 算法的通信開銷O（m）［29］，其原因也是因?yàn)檎{(diào)用KM 算法時(shí)需要向Sink 節(jié)點(diǎn)發(fā)送消息。

3 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估本文算法的性能，在Win 10 下用Visual studio 2019 進(jìn)行仿真，仿真場(chǎng)景為一個(gè)125 m×125 m 的矩形區(qū)域，其中隨機(jī)分布著若干傳感器，傳感器的感知半徑和通信半徑分別為10 m 和20 m。

為了更好地評(píng)價(jià)算法性能，本文引入式（3）所示的ΔCov-Dist 指標(biāo)：

其中：平均移動(dòng)距離是HWSN 中所有移動(dòng)節(jié)點(diǎn)移動(dòng)距離的平均值，平均移動(dòng)距離越小，系統(tǒng)因重新部署移動(dòng)傳感器節(jié)點(diǎn)的總能耗越低；ΔCov-Dist 是單位移動(dòng)距離下網(wǎng)絡(luò)覆蓋率的變化，為網(wǎng)絡(luò)覆蓋率的變化與移動(dòng)節(jié)點(diǎn)平均移動(dòng)距離的比值，ΔCov-Dist 越大，移動(dòng)節(jié)點(diǎn)移動(dòng)相同距離時(shí)網(wǎng)絡(luò)覆蓋率提升越大，HWSN 能效越高。

圖7（a）所示為一個(gè)由40 個(gè)固定傳感器和20 個(gè)移動(dòng)傳感器所組成的HWSN，對(duì)圖7（a）所示的HWSN 分別運(yùn)行HWSNBCS 和IHWSNBCS 算法，得到圖7（b）、圖7（c）所示的實(shí)驗(yàn)結(jié)果，圖中小空心圓表示傳感器節(jié)點(diǎn)，深色填充大圓表示移動(dòng)傳感器的感知區(qū)域，淺灰色填充大圓表示固定傳感器的感知區(qū)域，線段表示移動(dòng)傳感器初始位置和目標(biāo)位置之間的直線距離，線段越長(zhǎng)，表示移動(dòng)傳感器移動(dòng)距離越遠(yuǎn)。從圖7 可以看出，圖7（a）中傳感器分布不均，區(qū)域中有明顯的覆蓋洞，其網(wǎng)絡(luò)覆蓋率為65.29%。圖7（b）、圖7（c）通過對(duì)移動(dòng)傳感器重新部署，網(wǎng)絡(luò)的覆蓋性能明顯改善，其覆蓋率達(dá)到83.39%。雖然圖7（b）和圖7（c）的覆蓋率一樣，但圖7（b）中移動(dòng)傳感器的AMD 為35.45 m，而圖7（c）中移動(dòng)傳感器的AMD 為21.67 m，前者AMD 減少了38.87%，顯然，本文IHWSNBCS 算法中移動(dòng)節(jié)點(diǎn)的AMD 更短。圖7（b）的ΔCov-Dist 為0.51，圖7（c）的ΔCov-Dist 為0.84，后者為前者的1.64 倍，說明網(wǎng)絡(luò)能效更高。此外，從圖7 中還可以看出，圖7（c）中長(zhǎng)度較長(zhǎng)的線段數(shù)量比圖7（b）中少，且最長(zhǎng)線段的長(zhǎng)度比圖7（b）中短，說明本文算法單個(gè)節(jié)點(diǎn)的最大移動(dòng)距離也大幅縮短，單個(gè)節(jié)點(diǎn)的最大移動(dòng)距離過大，會(huì)導(dǎo)致該節(jié)點(diǎn)因能量消耗過快而成為失效節(jié)點(diǎn)，從而形成覆蓋盲區(qū)，影響網(wǎng)絡(luò)的覆蓋性能。

圖7 包含60 個(gè)節(jié)點(diǎn)的HWSN 在2 種算法下的運(yùn)行結(jié)果Fig.7 Running results of HWSN with sixty nodes under two algorithms

圖8 所示為一個(gè)由56 個(gè)固定傳感器和24 個(gè)移動(dòng)傳感器所組成的HWSN，其初始覆蓋率為75.25%。對(duì)圖8 所示的HWSN 分別運(yùn)行HWSNBCS 和IHWSNBCS 算法，得到表1 所示的實(shí)驗(yàn)結(jié)果。從表1可以看出，通過對(duì)部分移動(dòng)節(jié)點(diǎn)進(jìn)行重新部署，2 種算法都大幅提高了網(wǎng)絡(luò)覆蓋率，改善了網(wǎng)絡(luò)的覆蓋性能。雖然本文IHWSNBCS 算法并不改變HWSNBCS 算法的覆蓋率，但I(xiàn)HWSNBCS 算法移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離更小，與HWSNBCS 算法相比減少了43.28%，說明達(dá)到相同的覆蓋性能，本文算法移動(dòng)節(jié)點(diǎn)的能耗更小，且單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離更短，比HWSNBCS 算法減少66.58%，這將降低單個(gè)節(jié)點(diǎn)因能量過早耗完而失效的概率，從而有助于延長(zhǎng)整個(gè)傳感器網(wǎng)絡(luò)的生命周期。此外，IHWSNBCS 算法的ΔCov-Dist 指標(biāo)是HWSNBCS 算法的1.76 倍，說明前者能效更高。

圖8 包含80 個(gè)節(jié)點(diǎn)的HWSNFig.8 HWSN with 80 nodes

表1 包含80 個(gè)節(jié)點(diǎn)的HWSN 在2 種算法下的運(yùn)行結(jié)果Table 1 Running results of HWSN with eighty nodes under two algorithms

在HWSN 傳感器總數(shù)保持不變的情況下，改變移動(dòng)傳感器的比例，分別運(yùn)行HWSNBCS 和IHWSNBCS 算法，實(shí)驗(yàn)中移動(dòng)節(jié)點(diǎn)均為隨機(jī)選取。表2 所示為2 種算法在不同移動(dòng)節(jié)點(diǎn)比例下的覆蓋率和單個(gè)節(jié)點(diǎn)最大移動(dòng)距離。從表2 可以看出：隨著移動(dòng)傳感器節(jié)點(diǎn)比例的提升，通過對(duì)更多的移動(dòng)節(jié)點(diǎn)進(jìn)行重新部署，網(wǎng)絡(luò)的覆蓋率逐漸提升，但本文算法單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離比HWSNBCS 算法減少了22.65%～66.58%，這將大幅減少單個(gè)移動(dòng)節(jié)點(diǎn)重新部署的最大能耗，降低節(jié)點(diǎn)因能量過早耗完而失效的概率。

表2 不同移動(dòng)節(jié)點(diǎn)比例下2 種算法的運(yùn)行結(jié)果Table 2 Running results of two algorithms under different mobile node proportions

圖9 所示為2 種算法移動(dòng)節(jié)點(diǎn)平均移動(dòng)距離在不同移動(dòng)節(jié)點(diǎn)比例下的變化情況。從圖9 可以看出：隨著移動(dòng)節(jié)點(diǎn)比例的增加，有更多的移動(dòng)節(jié)點(diǎn)被重新部署，本文IHWSNBCS 算法移動(dòng)傳感器的AMD 逐漸減少，其AMD 比HWSNBCS 算法中的AMD 小很多，這是因?yàn)閷?duì)于移動(dòng)傳感器移動(dòng)距離最小化問題，本文使用的KM 算法能夠得到全局最優(yōu)解，而HWSNBCS 算法得到的是局部最優(yōu)解，因此，HWSNBCS 算法的AMD 比本文算法大，且隨著移動(dòng)傳感器比例的增大，HWSNBCS 算法移動(dòng)節(jié)點(diǎn)的AMD 變化趨勢(shì)也沒有IHWSNBCS 算法明顯。

圖9 2 種算法在不同移動(dòng)節(jié)點(diǎn)比例下的平均移動(dòng)距離Fig.9 Average moving distance of two algorithms under different mobile node proportions

圖10 所示為2 種算法的ΔCov-Dist 指標(biāo)在不同移動(dòng)節(jié)點(diǎn)比例下的變化情況。從圖10 可以看出，本文算法的ΔCov-Dist 指標(biāo)明顯大于HWSNBCS 算法，這是由于在覆蓋率變化相同的情況下，本文算法的平均移動(dòng)距離更小，因而通過式（3）計(jì)算出的ΔCov-Dist 更大，能效更高。

圖10 2 種算法在不同移動(dòng)節(jié)點(diǎn)比例下的ΔCov-DistFig.10 ΔCov-Dist of two algorithms under different mobile node proportions

對(duì)一個(gè)由56 個(gè)固定節(jié)點(diǎn)和24 個(gè)移動(dòng)節(jié)點(diǎn)組成的HWSN 分別運(yùn)行標(biāo)準(zhǔn)遺傳算法、粒子群算法、HWSNBCS 算法和IHWSNBCS 算法，實(shí)驗(yàn)結(jié)果如表3 所示。其中，粒子群算法和遺傳算法均以最大化網(wǎng)絡(luò)覆蓋率為優(yōu)化目標(biāo)，在達(dá)到與HWSNBCS 以及IHWSNBCS 相同的覆蓋率時(shí)算法停止。粒子群算法和遺傳算法各運(yùn)行50 次，取其平均值，HWSNBCS 和IHWSNBCS 算法各運(yùn)行1 次。實(shí)驗(yàn)中移動(dòng)節(jié)點(diǎn)的初始能量為1 500 J，移動(dòng)節(jié)點(diǎn)每移動(dòng)1 m所消耗的能量為30 J。當(dāng)重新部署某個(gè)移動(dòng)節(jié)點(diǎn)時(shí)，如果其需要耗費(fèi)的能量大于初始能量，則認(rèn)為該節(jié)點(diǎn)失效。從表3 可以看出，本文算法的失效節(jié)點(diǎn)數(shù)明顯少于其他3 種算法，因此，其網(wǎng)絡(luò)生命周期會(huì)更長(zhǎng)。

表3 4 種算法的失效移動(dòng)節(jié)點(diǎn)數(shù)對(duì)比Table 3 Comparison of the number of failed mobile nodes of four algorithms

4 結(jié)束語

本文提出一種基于蜂窩結(jié)構(gòu)的改進(jìn)HWSN 覆蓋優(yōu)化算法IHWSNBCS。將HWSN 中移動(dòng)傳感器的移動(dòng)距離優(yōu)化問題轉(zhuǎn)化為二分圖匹配問題，然后利用帶權(quán)二分圖匹配算法KM 計(jì)算匹配問題的最優(yōu)解，從而實(shí)現(xiàn)對(duì)HWSNBCS 算法的優(yōu)化。實(shí)驗(yàn)結(jié)果表明，IHWSNBCS 算法可在保持原有HWSNBCS 算法網(wǎng)絡(luò)覆蓋率不變的前提下，大幅減少移動(dòng)節(jié)點(diǎn)的平均移動(dòng)距離以及單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離，同時(shí)提高系統(tǒng)能效，延長(zhǎng)網(wǎng)絡(luò)的生命周期。下一步將在單個(gè)移動(dòng)節(jié)點(diǎn)的最大移動(dòng)距離約束下優(yōu)化節(jié)點(diǎn)的位置部署，從而提高網(wǎng)絡(luò)覆蓋性能。