基于蜂窩結構的改進混合無線傳感器網絡覆蓋優(yōu)化算法

2022-12-13 13:52:30張清國張勇張偉席瑞潔

計算機工程 2022年12期

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

（1.華中師范大學計算機學院，武漢 430079；2.華中科技大學計算機科學與技術學院，武漢 430074）

0 概述

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

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

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

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

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

1 HWSNBCS 算法

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

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

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

3）在區(qū)域A中存在一個Sink 節(jié)點，該節(jié)點負責完成算法的移動距離優(yōu)化。

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

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

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

1.1 基于蜂窩結構的節(jié)點移動策略

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

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

圖1 移動節(jié)點ma的NCNLC 內無固定節(jié)點的情況Fig.1 No static node within the NCNLC of the mobile node ma

2）若移動傳感器ma位于某個固定傳感器sa的NCNLC 內，記sa的NCNLC 為⊙sa，則ma沿直線sama移動到⊙sa上距ma較近的點［29］。如圖2所示，ma沿直線sama移動到⊙sa上的A點。

圖2 移動節(jié)點ma在某個固定節(jié)點NCNLC 內的移動方案Fig.2 Mobile scheme of mobile node ma in NCNLC of a fixed node

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

圖3 移動節(jié)點ma只有一個CCNLC 時的移動方案Fig.3 Mobile scheme of mobile node ma when ma has only one CCNLC

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

圖4 移動節(jié)點ma有2 個CCNLC 時的移動方案Fig.4 Mobile scheme of mobile node ma when ma has two CCNLC

1.2 節(jié)點移動距離優(yōu)化

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

1.3 算法描述

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

算法1HWSNBCS 算法

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

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

步驟1Fori：=1 tomdo

對移動傳感器節(jié)點mi，根據(jù)圖1～圖4 所示的4 種情況，計算其候選目標位置Pi。

步驟3重復步驟2，直至整個HWSN 的AMD不能減少為止。

步驟4輸出集合P。

顯然，步驟2～步驟3 不會改變整個網絡的覆蓋率，但可減少移動節(jié)點的AMD，從而進一步優(yōu)化移動節(jié)點的布局。

2 基于蜂窩結構的改進HWSN 覆蓋控制算法

圖6 簡單的帶權二分圖Fig.6 Simple weighted bipartite graph

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

2.1 算法描述

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

算法2IHWSNBCS 算法

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

輸出集合Q與集合P移動距離之和最小的匹配結果

步驟1定義初始可行頂點標記L：

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

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

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

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

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

步驟6設qp∈X，令A=A∪｛q｝，B=B∪｛p｝，轉步驟3。

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

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

IHWSNBCS 算法并不改變HWSNBCS 算法的網絡覆蓋率，僅改變HWSNBCS 算法中移動節(jié)點的平均移動距離，這是因為IHWSNBCS 算法只對HWSNBCS 算法移動節(jié)點的初始位置和目標位置進行重新匹配，在整個HWSN 中，固定節(jié)點的位置沒有發(fā)生變化，因此，其監(jiān)測區(qū)域也沒有變化，相比HWSNBCS 算法而言，IHWSNBCS 中移動節(jié)點整體監(jiān)測的區(qū)域實際上也沒有發(fā)生變化，變化的只是單個傳感器的監(jiān)測區(qū)域。因此，IHWSNBCS 算法傳感器節(jié)點的監(jiān)測區(qū)域與HWSNBCS 算法相同，即IHWSNBCS 算法并未改變HWSNBCS 算法的網絡覆蓋率。

2.2 復雜度分析

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

然后分析IHWSNBCS 算法的空間復雜度。IHWSNBCS 算法和HWSNBCS 算法的內存消耗主要來源于移動節(jié)點的初始位置和候選目標位置，因此，空間復雜度均為O（m），改進算法并未增加空間開銷。

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

3 實驗結果與分析

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

為了更好地評價算法性能，本文引入式（3）所示的ΔCov-Dist 指標：

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

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

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

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

圖8 包含80 個節(jié)點的HWSNFig.8 HWSN with 80 nodes

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

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

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

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

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

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

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

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

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

4 結束語

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