黃恒杰，龔小龍，王高才

(1.玉林師范學(xué)院教育技術(shù)中心，廣西玉林537000；2.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧530004)

傳感器中基于連通支配集的區(qū)域覆蓋控制算法

黃恒杰1，龔小龍2，王高才2

(1.玉林師范學(xué)院教育技術(shù)中心，廣西玉林537000；2.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧530004)

針對現(xiàn)有無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制算法很難在確保網(wǎng)絡(luò)連通率的同時對網(wǎng)絡(luò)覆蓋率和能耗進(jìn)行優(yōu)化的問題，本文提出一種基于連通支配集的區(qū)域覆蓋控制(area coverage control based on connected dominating set，ACCBCDS)算法。當(dāng)節(jié)點(diǎn)隨機(jī)分布于監(jiān)測區(qū)域后，未連通的節(jié)點(diǎn)移向Sink節(jié)點(diǎn)直至網(wǎng)絡(luò)實(shí)現(xiàn)全連通，之后利用三著色算法構(gòu)建網(wǎng)絡(luò)連通支配集，Sink節(jié)點(diǎn)對非連通支配節(jié)點(diǎn)進(jìn)行集中式優(yōu)化調(diào)整，讓非連通支配節(jié)點(diǎn)移至更優(yōu)位置。在優(yōu)化調(diào)整的過程中同時考慮了網(wǎng)絡(luò)連通率、覆蓋率和節(jié)點(diǎn)移動距離。仿真結(jié)果表明，與典型的基于虛擬力的區(qū)域覆蓋控制(area coverage control based on virtual forces，ACCBVF)算法相比較，本文提出的ACCBCDS算法能使網(wǎng)絡(luò)在確保全連通的前提下獲得更高覆蓋率，并能減少網(wǎng)絡(luò)覆蓋控制中的移動能耗。

傳感器網(wǎng)絡(luò)；連通支配集；覆蓋率；能耗

0 引言

無線傳感器網(wǎng)絡(luò)覆蓋控制是指在考慮網(wǎng)絡(luò)存儲、計(jì)算、通信和能量等資源受限的情況下，通過調(diào)整節(jié)點(diǎn)位置、網(wǎng)絡(luò)路由和節(jié)點(diǎn)狀態(tài)等手段，使各受限資源得到優(yōu)化配置，進(jìn)而使網(wǎng)絡(luò)感知、通信和生存周期等服務(wù)質(zhì)量得到改善[1-3]。根據(jù)覆蓋對象的不同，現(xiàn)有無線傳感器網(wǎng)絡(luò)覆蓋控制方法可分為區(qū)域覆蓋、點(diǎn)覆蓋、柵欄覆蓋3類。

點(diǎn)覆蓋是指對監(jiān)測區(qū)域中某些重要的目標(biāo)點(diǎn)進(jìn)行覆蓋，該問題已被廣泛研究[4-7]。點(diǎn)覆蓋通過單個活動節(jié)點(diǎn)監(jiān)控覆蓋區(qū)域，其他節(jié)點(diǎn)睡眠，從而有效延長整個網(wǎng)絡(luò)生存時間。如何構(gòu)造最大數(shù)量的無交節(jié)點(diǎn)集是一個NP完全問題。柵欄覆蓋是研究運(yùn)動物體通過監(jiān)測區(qū)域時被監(jiān)測到的概率問題。目前，針對柵欄覆蓋已取得一定成果[8-10]。柵欄覆蓋的意義在于：一方面可以確定最佳網(wǎng)絡(luò)部署，使得目標(biāo)檢測概率最大；另一方面，當(dāng)穿越有危險的監(jiān)控區(qū)域時，可以選擇一條最安全的路徑。

區(qū)域覆蓋要求監(jiān)測區(qū)域中的每個點(diǎn)至少被一個節(jié)點(diǎn)覆蓋，這是覆蓋控制中研究最多的一類。Huang等研究了正方形監(jiān)測區(qū)域的網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)感知半徑、監(jiān)測區(qū)域邊長等參數(shù)之間的數(shù)學(xué)關(guān)系，提出可用于網(wǎng)絡(luò)初始部署階段控制覆蓋率[11]，該算法對于全局部署效果不好。Zhang等研究了對于按照泊松分布方式進(jìn)行隨機(jī)初始部署的無線傳感器網(wǎng)絡(luò)，如何實(shí)現(xiàn)目標(biāo)區(qū)域的K覆蓋問題[12]，該算法需要根據(jù)網(wǎng)絡(luò)狀況手工設(shè)定大量參數(shù)，同時只能保證節(jié)點(diǎn)通信距離大于或等于兩倍感知距離時的網(wǎng)絡(luò)連通性。Dhillon等針對二維平面的區(qū)域覆蓋問題，提出利用正方形網(wǎng)格對目標(biāo)區(qū)域進(jìn)行劃分，借助最大化平均覆蓋部署算法(max average coverage deployment，MACD)[13]，但是該算法會消耗過多的節(jié)點(diǎn)能耗。文獻(xiàn)[14]提出一種在構(gòu)建連通支配集的基礎(chǔ)上調(diào)整連通支配集的中間節(jié)點(diǎn)狀態(tài)進(jìn)行節(jié)點(diǎn)優(yōu)化控制的算法。該算法能夠在確保網(wǎng)絡(luò)全連通的前提下提高網(wǎng)絡(luò)覆蓋率，然而其集中式優(yōu)化過程中未考慮節(jié)點(diǎn)移動距離，使得節(jié)點(diǎn)移動能耗仍存在優(yōu)化空間，該方法沒有考慮能耗優(yōu)化問題。Zou等針對二維空間中移動無線傳感器網(wǎng)絡(luò)覆蓋控制問題，提出一種基于虛擬力的覆蓋控制(area coverage control based on virtual forces, ACCBVF)算法[15]。作為典型的移動無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制算法，該算法利用節(jié)點(diǎn)引力避免節(jié)點(diǎn)相互之間出現(xiàn)過大距離，從而能確保網(wǎng)絡(luò)連通率；利用節(jié)點(diǎn)斥力避免節(jié)點(diǎn)相互之間出現(xiàn)過小距離(這會帶來較大覆蓋重疊)，從而能確保網(wǎng)絡(luò)覆蓋率。然而，經(jīng)過科學(xué)分析及必要仿真可知，該算法存在以下不足之處：如無法實(shí)現(xiàn)網(wǎng)絡(luò)的全連通，網(wǎng)絡(luò)覆蓋率可進(jìn)一步優(yōu)化以及過多的網(wǎng)絡(luò)移動能耗。

由于現(xiàn)有的無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制算法很難在確保網(wǎng)絡(luò)全連通的同時對網(wǎng)絡(luò)覆蓋率和能耗進(jìn)行優(yōu)化，本文提出一種基于連通支配集的區(qū)域覆蓋控制(area coverage control based on connected dominating set, ACCBCDS)算法。當(dāng)移動傳感器網(wǎng)絡(luò)以隨機(jī)方式在監(jiān)測區(qū)域完成初始部署后，未連通節(jié)點(diǎn)自主移向Sink節(jié)點(diǎn)直至網(wǎng)絡(luò)實(shí)現(xiàn)全連通，并通過三著色算法構(gòu)建網(wǎng)絡(luò)連通支配集。之后Sink節(jié)點(diǎn)進(jìn)行集中式優(yōu)化計(jì)算，對非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整。仿真結(jié)果表明，所提出的ACCBCDS算法能使網(wǎng)絡(luò)在確保全連通的前提下實(shí)現(xiàn)較高網(wǎng)絡(luò)覆蓋率，并減少網(wǎng)絡(luò)覆蓋過程中的移動能耗。

1 問題定義及算法描述

1.1 問題定義

當(dāng)利用移動無線傳感器網(wǎng)絡(luò)對某些場合(如災(zāi)害救助、軍事監(jiān)控等)進(jìn)行區(qū)域覆蓋時，要求系統(tǒng)除了對監(jiān)測區(qū)域具有較高網(wǎng)絡(luò)覆蓋率之外，還必須具有很強(qiáng)的實(shí)時監(jiān)測性能，所有移動節(jié)點(diǎn)最好能和Sink節(jié)點(diǎn)始終保持通信(即網(wǎng)絡(luò)應(yīng)一直保持全連通)。由于移動無線傳感器網(wǎng)絡(luò)亦具有顯著的能量有效性，為了延長網(wǎng)絡(luò)生存周期，系統(tǒng)在覆蓋過程中應(yīng)盡量減少網(wǎng)絡(luò)能耗。因此，針對該類場合的移動無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制問題，是指在充分考慮網(wǎng)絡(luò)要求和特點(diǎn)的前提下，對初始隨機(jī)部署于監(jiān)測區(qū)域的節(jié)點(diǎn)進(jìn)行位置調(diào)整，以實(shí)現(xiàn)較高網(wǎng)絡(luò)覆蓋率，并盡量減少網(wǎng)絡(luò)在調(diào)整過程中的能耗。

本文對傳感器網(wǎng)絡(luò)節(jié)點(diǎn)做如下合理的假設(shè)：(1)所有傳感器節(jié)點(diǎn)同構(gòu)，具有相同的感知半徑Rs和通信半徑Rc，并各自具有唯一的ID號；(2)傳感器節(jié)點(diǎn)初始時隨機(jī)部署于二維監(jiān)測區(qū)域，之后可自由移動。為了研究簡便，Sink節(jié)點(diǎn)可認(rèn)為一直固定于二維監(jiān)測區(qū)域中心；(3)傳感器節(jié)點(diǎn)均能借助相關(guān)定位裝置或算法確定自身實(shí)時位置；(4)Sink節(jié)點(diǎn)位置信息(即二維監(jiān)測區(qū)域中心的位置信息)在部署前已寫入其他各傳感器節(jié)點(diǎn)內(nèi)存中。Sink節(jié)點(diǎn)內(nèi)存中則寫入二維監(jiān)測區(qū)域的坐標(biāo)信息和傳感器節(jié)點(diǎn)的數(shù)目信息。

下面首先對ACCBCDS算法中如何利用三著色方法構(gòu)建網(wǎng)絡(luò)連通支配集和Sink節(jié)點(diǎn)對非連通支配節(jié)點(diǎn)進(jìn)行的集中式優(yōu)化調(diào)整進(jìn)行詳細(xì)描述，然后概述算法整體實(shí)現(xiàn)過程。

1.2 算法描述

1.2.1三著色算法構(gòu)建網(wǎng)絡(luò)連通支配集

三著色算法構(gòu)建網(wǎng)絡(luò)連通支配集的流程圖如圖1所示。將網(wǎng)絡(luò)中所有節(jié)點(diǎn)分為3個不同狀態(tài)，并用白色、灰色和黑色3個不同顏色表示。未被使用的節(jié)點(diǎn)表示為白色，非骨干節(jié)點(diǎn)表示為灰色，骨干節(jié)點(diǎn)表示為黑色。在構(gòu)建連通支配節(jié)點(diǎn)之前，所有節(jié)點(diǎn)初始狀態(tài)都認(rèn)為是未被使用，并用白色表示。選取Sink節(jié)點(diǎn)作為起始點(diǎn)標(biāo)記為黑色，當(dāng)所有節(jié)點(diǎn)均被標(biāo)記為灰色或黑色時，算法結(jié)束。

三著色算法的具體實(shí)現(xiàn)過程如下：

①將所有節(jié)點(diǎn)均初始化為未被使用狀態(tài)，并用白色表示。選取Sink節(jié)點(diǎn)作為起始點(diǎn)，將該點(diǎn)狀態(tài)標(biāo)記為骨干節(jié)點(diǎn)，并用黑色表示，之后該黑色起始點(diǎn)廣播查詢信息Mf。

②若白色節(jié)點(diǎn)s1收到來自黑色節(jié)點(diǎn)s2的查詢信息Mf，則將自身標(biāo)記為灰色節(jié)點(diǎn)，并根據(jù)自身與黑色節(jié)點(diǎn)s2的距離d(s1,s2)計(jì)算等待時間Tw1，Tw1與距離d(s1,s2)成反比。當(dāng)?shù)却龝r間結(jié)束后，節(jié)點(diǎn)s1廣播查詢信息。

圖1 三著色算法構(gòu)建網(wǎng)絡(luò)連通支配集的流程圖Fig.1 The flow chart of three coloring methods to construct a network connected dominating set

③若白色節(jié)點(diǎn)s1收到來自灰色節(jié)點(diǎn)s2的查詢信息Mf，則根據(jù)自身與灰色節(jié)點(diǎn)s2的距離d(s1,s2)計(jì)算等待時間Tw2，Tw2與距離d(s1,s2)成反比。若在等待時間內(nèi)，節(jié)點(diǎn)s1收到來自黑色節(jié)點(diǎn)的查詢信息，則將自身標(biāo)為灰色節(jié)點(diǎn)；否則將自身標(biāo)記為黑色節(jié)點(diǎn)。

④若黑色節(jié)點(diǎn)或灰色節(jié)點(diǎn)收到查詢信息，則忽略所有查詢信息。

⑤重復(fù)上述步驟，當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的顏色均被標(biāo)記為黑色或者灰色時停止對節(jié)點(diǎn)進(jìn)行顏色標(biāo)記。此時，網(wǎng)絡(luò)中黑色節(jié)點(diǎn)組成的集合即為連通支配集。

1.2.2非連通支配節(jié)點(diǎn)的優(yōu)化調(diào)整

當(dāng)未連通節(jié)點(diǎn)移向Sink節(jié)點(diǎn)使網(wǎng)絡(luò)實(shí)現(xiàn)全連通且通過三著色算法確立網(wǎng)絡(luò)連通支配集后，Sink節(jié)點(diǎn)可對非連通支配節(jié)點(diǎn)位置進(jìn)行集中式優(yōu)化調(diào)整，令非連通支配節(jié)點(diǎn)移至更優(yōu)位置。該位置位于連通支配節(jié)點(diǎn)的通信半徑范圍內(nèi)，且優(yōu)化過程中同時考慮如何提高網(wǎng)絡(luò)覆蓋率和減少節(jié)點(diǎn)移動距離。具體步驟如下：

①Sink節(jié)點(diǎn)根據(jù)非連通支配節(jié)點(diǎn)剩余能量，按照由大到小順序?qū)ζ渲饌€研究，為其計(jì)算更優(yōu)位置。

②設(shè)二維平面區(qū)域中與網(wǎng)絡(luò)連通支配節(jié)點(diǎn)不超過節(jié)點(diǎn)通信半徑Rc的探測點(diǎn)集合為C1，對于某非連通支配節(jié)點(diǎn)si，可將其調(diào)度至C1中的某個點(diǎn)pd(si)，以此實(shí)現(xiàn)在確保全連通的前提下提高網(wǎng)絡(luò)覆蓋率。

③同時，應(yīng)盡量減少節(jié)點(diǎn)移動距離，以減少網(wǎng)絡(luò)移動能耗。因此，可按式(1)為節(jié)點(diǎn)s1在C1中尋找目標(biāo)位置pd(si)：

(1)

其中，oi表示節(jié)點(diǎn)si在被Sink節(jié)點(diǎn)調(diào)度前的舊位置，Cv(oi)表示節(jié)點(diǎn)si在被Sink節(jié)點(diǎn)調(diào)度前的網(wǎng)絡(luò)覆蓋率，Cv(pi)則表示假定節(jié)點(diǎn)si到達(dá)探測點(diǎn)pi時的網(wǎng)絡(luò)覆蓋率。

1.2.3 ACCBCDS算法整體步驟

前面已經(jīng)詳述了ACCBCDS算法的2個主要部分，即網(wǎng)絡(luò)連通支配集的構(gòu)建和非連通支配節(jié)點(diǎn)的優(yōu)化調(diào)整，接下來描述該算法的整體實(shí)現(xiàn)步驟：

①有傳感器節(jié)點(diǎn)初始隨機(jī)分布于監(jiān)測區(qū)域，之后Sink節(jié)點(diǎn)固定于二維監(jiān)測區(qū)域中心，以接收來自各個傳感器節(jié)點(diǎn)所采集的數(shù)據(jù)信息。

②Sink節(jié)點(diǎn)廣播就緒信息Mr，收到該就緒信息的節(jié)點(diǎn)對就緒信息做進(jìn)一步轉(zhuǎn)發(fā)，并將自身位置信息告知Sink節(jié)點(diǎn)；未收到就緒信息的節(jié)點(diǎn)則沿直線移至Sink節(jié)點(diǎn)，并在移動過程中保持對就緒信息的偵聽，直至收到就緒信息，之后將自身位置信息告知Sink節(jié)點(diǎn)。

③若所有節(jié)點(diǎn)均收到就緒信息，則Sink節(jié)點(diǎn)所接收的位置信息數(shù)目應(yīng)等于節(jié)點(diǎn)數(shù)目。Sink節(jié)點(diǎn)可根據(jù)位置信息數(shù)目與節(jié)點(diǎn)數(shù)目是否相等確定網(wǎng)絡(luò)是否實(shí)現(xiàn)全連通，若二者不相等，表明網(wǎng)絡(luò)未全連通，Sink節(jié)點(diǎn)應(yīng)一直等待；若二者相等，則表示網(wǎng)絡(luò)已實(shí)現(xiàn)全連通，轉(zhuǎn)第④步。

④Sink節(jié)點(diǎn)確定網(wǎng)絡(luò)連通支配集。

⑤Sink節(jié)點(diǎn)對網(wǎng)絡(luò)中的非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整。

⑥算法結(jié)束。

2 仿真算例與分析

ACCBVF算法是典型移動無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制算法之一。為了合理評價ACCBCDS算法的性能，選擇ACCBVF算法作為對比算法，以網(wǎng)絡(luò)連通率、覆蓋率和覆蓋控制中的移動能耗作為算法性能評價指標(biāo)，對ACCBCDS算法和ACCBVF算法進(jìn)行對比仿真及分析。

2.1 仿真場景和參數(shù)

利用Matlab進(jìn)行仿真，為消除實(shí)驗(yàn)隨機(jī)性影響，最終結(jié)果取50次實(shí)驗(yàn)的平均值。模擬的二維監(jiān)測區(qū)域?yàn)?00 m×200 m的正方形平面，網(wǎng)格分辨率w=1 m。為盡量提高ACCBVF算法的網(wǎng)絡(luò)覆蓋率和連通率，其運(yùn)行輪數(shù)設(shè)為30。ACCBVF算法和ACCBCDS算法的其余主要參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)表

2.2 仿真結(jié)果與分析

ACCBVF算法和ACCBCDS算法的網(wǎng)絡(luò)連通率對比圖如圖2所示，其中圖2(a)對應(yīng)的仿真場景為節(jié)點(diǎn)數(shù)目變化，通信半徑固定為30 m，圖2(b)對應(yīng)的仿真場景為節(jié)點(diǎn)通信半徑變化，節(jié)點(diǎn)數(shù)目固定為40個?？梢钥闯觯cACCBVF算法相比，ACCBCDS算法始終能確保部署結(jié)束后網(wǎng)絡(luò)達(dá)到全連通(即連通率為1)。由于ACCBVF算法中能夠?qū)W(wǎng)絡(luò)連通率起提高作用的是節(jié)點(diǎn)引力，而節(jié)點(diǎn)的移動由其所受的虛擬力合力決定，因此節(jié)點(diǎn)引力并不能完全控制節(jié)點(diǎn)的移動，造成網(wǎng)絡(luò)無法達(dá)到全連通。而對于ACCBCDS算法，未連通的節(jié)點(diǎn)自主移向Sink節(jié)點(diǎn)直至網(wǎng)絡(luò)達(dá)到全連通，且Sink節(jié)點(diǎn)確定連通支配集后，在確保非連通支配節(jié)點(diǎn)處于連通支配節(jié)點(diǎn)通信半徑范圍內(nèi)的前提下，對非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整，因此調(diào)整結(jié)束后網(wǎng)絡(luò)仍保持全連通。

圖2 網(wǎng)絡(luò)連通率對比圖Fig.2 The comparisons of network connectivity

ACCBVF算法和ACCBCDS算法的網(wǎng)絡(luò)覆蓋率對比圖如圖3所示，仿真場景為節(jié)點(diǎn)數(shù)目變化，通信半徑固定為30 m?？梢钥闯?，與ACCBVF算法相比，在相同的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目下，ACCBCDS算法能使網(wǎng)絡(luò)獲得更高覆蓋率。對于ACCBVF算法，節(jié)點(diǎn)移動由局部范圍內(nèi)所受的虛擬力合力決定，此移動只能從局部角度對覆蓋率起一定提高作用。而對于ACCBCDS算法，Sink節(jié)點(diǎn)在確定網(wǎng)絡(luò)連通支配集后，從全局角度對非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整，因此該移動能帶來更大的覆蓋率提高。

圖3 網(wǎng)絡(luò)覆蓋率對比圖Fig.3 The comparisons of networkcoverage ratio

圖4 節(jié)點(diǎn)總移動能耗對比圖Fig.4 The comparisons of the totalenergy consumption of node

ACCBVF算法和ACCBCDS算法的節(jié)點(diǎn)總移動能耗對比圖如圖4所示，由圖可知，相比于ACCBVF算法，ACCBCDS算法的節(jié)點(diǎn)總移動能耗更小。對于ACCBVF算法，在其運(yùn)行的每一輪中所有節(jié)點(diǎn)都要根據(jù)所受的虛擬力合力進(jìn)行移動，故其總移動距離和總移動能耗較大。而對于ACCBCDS算法，所有節(jié)點(diǎn)在監(jiān)測區(qū)域完成初始隨機(jī)分布后，只有少量未連通節(jié)點(diǎn)移向Sink節(jié)點(diǎn)，且當(dāng)網(wǎng)絡(luò)達(dá)到全連通后，Sink節(jié)點(diǎn)只對部分非連通支配節(jié)點(diǎn)的位置進(jìn)行優(yōu)化調(diào)整，因此總移動距離和總移動能耗較小。

總的來說，相比于ACCBVF算法，本文提出的ACCBCDS算法的優(yōu)點(diǎn)在于：

(1)該算法要求未連通的節(jié)點(diǎn)移向Sink節(jié)點(diǎn)直至網(wǎng)絡(luò)實(shí)現(xiàn)全連通，之后僅對非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整，且調(diào)整后的位置仍位于連通支配節(jié)點(diǎn)的通信半徑范圍內(nèi)，因此網(wǎng)絡(luò)的全連通性能夠一直保持。

(2)該算法對非連通支配節(jié)點(diǎn)的位置優(yōu)化通過Sink節(jié)點(diǎn)進(jìn)行集中式計(jì)算完成，由于Sink節(jié)點(diǎn)能夠獲取網(wǎng)絡(luò)全局信息，因而這樣的集中式優(yōu)化調(diào)整能使網(wǎng)絡(luò)獲得更大覆蓋率提升。

(3)Sink節(jié)點(diǎn)在對非連通支配節(jié)點(diǎn)位置進(jìn)行集中式優(yōu)化調(diào)整時，不僅考慮了如何增加網(wǎng)絡(luò)覆蓋率，而且考慮了如何減少節(jié)點(diǎn)移動距離，因此能夠減少網(wǎng)絡(luò)移動能耗。

3 結(jié)束語

無線傳感器網(wǎng)絡(luò)區(qū)域覆蓋控制就是在確保網(wǎng)絡(luò)盡可能連通時對網(wǎng)絡(luò)覆蓋率和能耗進(jìn)行優(yōu)化。本文提出一種基于連通支配集的區(qū)域覆蓋控制ACCBCDS算法。該算法通過對非連通支配節(jié)點(diǎn)位置進(jìn)行優(yōu)化調(diào)整，持續(xù)保持網(wǎng)絡(luò)的全連通性和極大提高網(wǎng)絡(luò)的覆蓋率。同時通過減少節(jié)點(diǎn)移動距離來減少網(wǎng)絡(luò)移動能耗，從而有效地延長了網(wǎng)絡(luò)生存周期。仿真結(jié)果表明了ACCBCDS算法在各性能指標(biāo)上的優(yōu)勢。為了促使研究成果盡量應(yīng)用至實(shí)際場景，應(yīng)對節(jié)點(diǎn)感知、節(jié)點(diǎn)移動能耗建立更加符合實(shí)際情況的模型是下一步需要開展的研究工作。

[1] 岳才杰, 陳元琰, 朱新華. 一種有效的傳感器網(wǎng)絡(luò)區(qū)域查詢算法[J].廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,33(1):52-58.

[2] ABOUELKHAIR O, ELSAADNY A. Multipath adaptive periodic threshold-sensitive energy efficient protocol for wireless sensor networks[C]//Proceedings of the 6th IEEE International Conference on Computational Intelligence, Communication Systems and Networks. New York:IEEE Press, 2015: 33-37.

[3] JIANG P, LIU J, WU F, et al. Node deployment algorithm for underwater sensor networks based on connected dominating set[J]. Sensors, 2016, 16(3):388. DOI:10.3390/s16030388.

[4] CARDEI M, DU D Z. Improving wireless sensor network lifetime through power aware organization[J]. Wireless Networks, 2005, 11(3): 333-340.

[5] SEN A, DAS N, MURTHY S. Coverage and connected coverage problems for sensors embedded in a temperature-sensitive environment[J]. International Journal of Sensor Networks, 2010, 7(2): 106-123.

[6] 林祝亮, 馮遠(yuǎn)靜, 俞立. 無線傳感網(wǎng)絡(luò)覆蓋的粒子進(jìn)化優(yōu)化策略研究[J]. 傳感技術(shù)學(xué)報(bào), 2009, 22(6): 873-877.

[7] JIANG P, LIU J, WU F. Node non-uniform deployment based on clustering algorithm for underwater sensor networks[J]. 2015, 15(12): 29997-30010.

[8] MEGUERDICHIAN S, KOUSHANFAR F, POTKONJAK M, et al. Coverage problems in wireless ad-hoc sensor networks[C]// Proceedings of the IEEE Conference on INFOCOM. New York: IEEE Press, 2001:1380-1387.

[9] SANTOSH K, TEN H, ANISH A. Barrier coverage with wireless sensors[J]. Wireless Networks, 2007, 13(6): 817-834.

[10] LIU B Y, DOUSSE O, WANG J, et al. Strong barrier coverage of wireless sensor networks[C]// Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York: ACM Press, 2010: 411-419.

[11] HUANG C F, TSENG Y C, LO L C. The coverage problem in three-dimensional wireless sensor networks[J]. Journal of Interconnection Networks, 2011, 8(3): 3182-3186.

[12] ZHANG H, HOU J. On deriving the upper bound of α-lifetime for large sensor networks[J]. ACM Transactions on Sensor Networks, 2005, 1(2): 272-300.

[13] DHILLON S S, CHAKRABARTY K. Sensor placement for effective coverage and surveillance in distributed sensor networks[C]// Proceedings of the Wireless Communications and Networking. New York: IEEE Press, 2003: 1609-1614.

[14] 李海坡,馬向南. 無線傳感器網(wǎng)絡(luò)中基于連通支配集的覆蓋控制算法[C]// 中國通信學(xué)會第六屆學(xué)術(shù)年會論文集(下).北京：北京郵電大學(xué)出版社,2009：658-661.

[15] ZOU Y, CHAKRABARTY K. Sensor deployment and target localization based on virtual forces[C]// Proceedings of the 22th Annual Joint Conference of Computer and Communications. New York： IEEE Press， 2003: 1293-1303.

(實(shí)習(xí)編輯 李 朝)

(責(zé)任編輯 馬殷華)

An Area Coverage Control Algorithm Based on ConnectedDominating Set for Sensor Networks

HUANG Hengjie1, GONG Xiaolong2, WANG Gaocai2

(1. Educational Technology Center,Yulin Normal University,Yulin Guangxi 537000,China;2. School of Computer, Electronics and Information, Guangxi University, Nanning Guangxi 530004, China)

To solve the problem that existing area coverage control algorithms for the mobile WSNs are difficult to ensure the network connectivity rate of the network coverage and energy consumption optimization, an area coverage control algorithm based on connected dominating set (ACCBCDS) algorithm is proposed for the mobile WSNs. When the nodes are randomly distributed in the monitoring area, nodes disconnected to the Sink node are required to move toward the Sink node until full network connectivity is achieved. Then the three-staining method is adopted to construct the network connected dominating set, after which the Sink node performs centralized optimization adjustment on dominated nodes, requiring dominated nodes to move toward better locations. During the adjustment, network coverage rate, connectivity rate and node movement distance are synthetically considered. Simulation results show that compared with typical area coverage control algorithm based on virtual forces (ACCBVF) algorithm, the proposed ACCBCDS can achieve higher network coverage rate under the premise of ensuring full network connectivity, and decrease node movement energy consumption during network coverage control.

sensors networks; connected dominating set; coverage rate; energy consumption

10.16088/j.issn.1001-6600.2016.04.003

2016-06-18

廣西高等學(xué)校優(yōu)秀中青年骨干教師培養(yǎng)工程資助項(xiàng)目；國家自然科學(xué)基金資助項(xiàng)目(61562006，61262003)；廣西自然科學(xué)杰出青年基金資助項(xiàng)目(2013GXNSFGA019006)

王高才(1976—)，男，廣西灌陽人，廣西大學(xué)教授，博士，博士生導(dǎo)師。 E-mail：wanggcgx@163.com

TP393

A

1001-6600(2016)04-0019-07