傳感網(wǎng)中帶有可控閾值的優(yōu)化協(xié)同覆蓋算法

孫澤宇，李傳鋒，邢蕭飛，來(lái)純曉

1.洛陽(yáng)理工學(xué)院計(jì)算機(jī)與信息工程學(xué)院，河南洛陽(yáng)471023

2.河南科技學(xué)院信息工程學(xué)院，河南新鄉(xiāng)453003

3.廣州大學(xué)計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣州510006

無(wú)線傳感器網(wǎng)絡(luò)實(shí)現(xiàn)了信息世界與物理世界有機(jī)統(tǒng)一，改變了人類世界對(duì)物理世界交互方式，其廣泛地應(yīng)用在國(guó)防軍事、安全生產(chǎn)、醫(yī)療衛(wèi)生、環(huán)境監(jiān)測(cè)、目標(biāo)跟蹤和智能交通等多種工程領(lǐng)域[1-3]。無(wú)線傳感器網(wǎng)絡(luò)物理特點(diǎn)主要表現(xiàn)在：在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署大量傳感器節(jié)點(diǎn)，以監(jiān)測(cè)移動(dòng)目標(biāo)節(jié)點(diǎn)或某發(fā)射源，傳感器節(jié)點(diǎn)通過(guò)自組織方式形成信息交互和數(shù)據(jù)實(shí)時(shí)采集的大型網(wǎng)絡(luò)[4-6]。監(jiān)測(cè)區(qū)域內(nèi)，任意傳感器節(jié)點(diǎn)都具有一定的存儲(chǔ)能力、通信能力、計(jì)算能力和感知能力，但各種能力均較弱[7]。其工作的動(dòng)力來(lái)源于自身的電池，一旦電能耗盡將無(wú)法補(bǔ)充[8-10]。因此，覆蓋效果的優(yōu)劣直接影響到無(wú)線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)協(xié)議、目標(biāo)定位與跟蹤、能量高效和網(wǎng)絡(luò)通信。為此，構(gòu)建一個(gè)可靠、實(shí)時(shí)、高效的無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)是一項(xiàng)艱巨而有挑戰(zhàn)性的工作。

隨著國(guó)內(nèi)外學(xué)者對(duì)群體智能方面研究的不斷深入，現(xiàn)以智能分簇結(jié)構(gòu)下的覆蓋算法進(jìn)行分析。文獻(xiàn)[9]以節(jié)點(diǎn)能量作為研究背景，以單位時(shí)間作為輪流基數(shù)，讓高能量節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，同時(shí)利用貪婪算法計(jì)算了相鄰節(jié)點(diǎn)之間的最短路徑。文獻(xiàn)[10]利用雙鏈表寫入數(shù)據(jù)傳輸所行走過(guò)的路徑；當(dāng)某一個(gè)路徑出現(xiàn)故障時(shí)，另一個(gè)鏈表中獲取上一級(jí)別的節(jié)點(diǎn)路徑信息重新寫入該鏈表，然后再次更新雙鏈表，以達(dá)到路徑雙備份目的。文獻(xiàn)[11]利用圖論樹(shù)型結(jié)構(gòu)構(gòu)建一棵無(wú)向生成樹(shù)，而后通過(guò)簇內(nèi)中心節(jié)點(diǎn)廣播路由，優(yōu)先搜索得到一棵最小路由生成樹(shù)，再次利用蟻群算法遍歷最小生成樹(shù)，最終得到簇內(nèi)最優(yōu)路由。文獻(xiàn)[12]利用退火算法構(gòu)建路由最小生成樹(shù)，以簇內(nèi)能量最高節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，以能量次高節(jié)點(diǎn)作為副簇首節(jié)點(diǎn)。通過(guò)退火算法計(jì)算得到最小延時(shí)路徑，并將數(shù)據(jù)發(fā)送至基站；在數(shù)據(jù)融合階段，則是利用簇內(nèi)成員節(jié)點(diǎn)的位置信息與相鄰節(jié)點(diǎn)的位置信息構(gòu)建上一層的能量均衡路由樹(shù)，以達(dá)到全網(wǎng)能量平衡的目的。文獻(xiàn)[13]利用非線性優(yōu)化原理，給出了傳感器節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的最大連通計(jì)算方法；然后利用排序算法按照能量的高低進(jìn)行排序并將節(jié)點(diǎn)存儲(chǔ)在有限鏈表中。在對(duì)目標(biāo)節(jié)點(diǎn)覆蓋過(guò)程中，從鏈表中按照節(jié)點(diǎn)能量從高至低的順序進(jìn)行選舉，最終達(dá)到整個(gè)網(wǎng)絡(luò)能量均衡的目的。文獻(xiàn)[14]以數(shù)據(jù)融合時(shí)間作為研究對(duì)象，給出了一個(gè)基于局部數(shù)據(jù)融合信息的分布式路由算法，該算法可以為任意一棵生成樹(shù)建立最優(yōu)傳輸路徑，同時(shí)也為任意一個(gè)傳感器節(jié)點(diǎn)指定了數(shù)據(jù)的時(shí)間間隙，優(yōu)化的網(wǎng)絡(luò)資源。文獻(xiàn)[15]利用退火算法通過(guò)傳感器節(jié)點(diǎn)剩余能量和數(shù)據(jù)的相似性建立節(jié)點(diǎn)的分簇。對(duì)于簇內(nèi)成員所采集的數(shù)據(jù)信息則通過(guò)回歸模型獲取預(yù)測(cè)數(shù)據(jù)，以此決定數(shù)據(jù)的傳輸路徑。文獻(xiàn)[16]給出了一種基于數(shù)據(jù)行為的分布式算法。該算法把靜態(tài)與動(dòng)態(tài)成簇算法相融合對(duì)簇內(nèi)成員進(jìn)行動(dòng)態(tài)劃分，在本周期內(nèi)所在簇內(nèi)成員節(jié)點(diǎn)均保持靜態(tài)；在若干個(gè)周期后，根據(jù)傳感器節(jié)點(diǎn)能量與歐氏距離關(guān)系采用動(dòng)態(tài)成簇方法對(duì)所有節(jié)點(diǎn)再次劃分，最終達(dá)到能量均衡目的。文獻(xiàn)[17]利用傳感器節(jié)點(diǎn)感知能力的連續(xù)性和傳感器節(jié)點(diǎn)連通性等特性，提出了多目標(biāo)連續(xù)跟蹤算法。該算法也是通過(guò)簇間通信完成了對(duì)移動(dòng)目標(biāo)的跟蹤過(guò)程，簇首節(jié)點(diǎn)將簇內(nèi)成員所采集的數(shù)據(jù)信息進(jìn)行有效融合，最終由簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)給基站。文獻(xiàn)[18]對(duì)原始簇首選舉閾值函數(shù)進(jìn)行改良，結(jié)合間距因素、節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)位置因素提出新的簇首選舉函數(shù)，有效延長(zhǎng)網(wǎng)絡(luò)生命周期，但簇首的選取依賴隨機(jī)概率和閾值函數(shù)，因此無(wú)法保證簇首選取結(jié)果的最優(yōu)性。

覆蓋問(wèn)題首先要建立研究的覆蓋模型，提高覆蓋精度及準(zhǔn)確性，同時(shí)要抑制傳感器節(jié)點(diǎn)能量的快速消耗，以達(dá)到延長(zhǎng)網(wǎng)絡(luò)生存周期目的；其次，對(duì)于監(jiān)測(cè)區(qū)域而言，為了抑制節(jié)點(diǎn)的能量的消耗，覆蓋過(guò)程中并不需要對(duì)整個(gè)監(jiān)測(cè)區(qū)域覆蓋，而采用對(duì)關(guān)注目標(biāo)節(jié)點(diǎn)的有效覆蓋。再次，為了更好地對(duì)關(guān)注目標(biāo)節(jié)點(diǎn)進(jìn)行有效覆蓋，這就要求節(jié)點(diǎn)之間建立協(xié)同工作，將網(wǎng)絡(luò)中的地理位置相鄰的節(jié)點(diǎn)劃分為相連的區(qū)域，構(gòu)成分簇結(jié)構(gòu)。為了進(jìn)一步研究覆蓋問(wèn)題，本文以感知智能計(jì)算和可控閾值作為研究背景，提出了優(yōu)化協(xié)同覆蓋算法。本文的主要貢獻(xiàn)體現(xiàn)在以下三點(diǎn)：

（1）引入覆蓋模型并對(duì)該模型進(jìn)行有效分析，給出相關(guān)定義及模型分析過(guò)程。

（2）通過(guò)可控參數(shù)和遺傳算法中變異參數(shù)等特性對(duì)事件域節(jié)點(diǎn)成簇進(jìn)行優(yōu)化，提高覆蓋的精準(zhǔn)度，優(yōu)化了網(wǎng)絡(luò)資源，提升對(duì)全局目標(biāo)節(jié)點(diǎn)的搜索能力。

（3）通過(guò)仿真實(shí)驗(yàn)驗(yàn)證本文OCC-CT（novel optimization cooperative coverage algorithm with controllable threshold-parameters）算法的穩(wěn)定性和有效性。

1 覆蓋模型建立與分析

1.1 假設(shè)與基本定義

本文在研究覆蓋問(wèn)題時(shí)，需要將現(xiàn)實(shí)的物理問(wèn)題轉(zhuǎn)換成抽象的數(shù)學(xué)問(wèn)題。為了便于研究問(wèn)題的方便性，故作出如下假設(shè)：

（1）在監(jiān)測(cè)區(qū)域內(nèi)，忽略傳感器節(jié)點(diǎn)邊界效應(yīng)，其感知半徑遠(yuǎn)小于監(jiān)測(cè)區(qū)域邊界長(zhǎng)度。

（2）網(wǎng)絡(luò)中的每個(gè)傳感器節(jié)點(diǎn)都可以通過(guò)某定位算法獲取自身位置信息，如RSSI（received signal strength indication）、TDOA（time difference of arrival）。

（3）每個(gè)傳感器節(jié)點(diǎn)感知能力不受外界物理環(huán)境影響，具有唯一標(biāo)識(shí)[19-20]。

（4）網(wǎng)絡(luò)初始時(shí)刻，所有節(jié)點(diǎn)呈現(xiàn)同構(gòu)形態(tài)且始終保持圓盤形，感知半徑均相同，所有傳感器節(jié)點(diǎn)的通信半徑均相同[21]。

（5）每個(gè)傳感器節(jié)點(diǎn)工作時(shí)均與時(shí)間同步，網(wǎng)關(guān)節(jié)點(diǎn)不可移動(dòng)。

定義1（覆蓋率）在無(wú)線傳感器網(wǎng)絡(luò)內(nèi)的被所有傳感器節(jié)點(diǎn)監(jiān)控或跟蹤的可靠性，也稱為覆蓋程度或覆蓋度。覆蓋率是所有傳感器節(jié)點(diǎn)覆蓋區(qū)域的大小與整個(gè)目標(biāo)區(qū)域大小的比值[3]。

其中，C為覆蓋率；S(Ai)為第i個(gè)節(jié)點(diǎn)的覆蓋區(qū)域的大小；N為傳感器節(jié)點(diǎn)的數(shù)量；S(A)為監(jiān)測(cè)區(qū)域面積。

定義2（覆蓋效率）在監(jiān)測(cè)區(qū)域內(nèi)，所有傳感器節(jié)點(diǎn)的覆蓋面積并集與所有傳感器節(jié)點(diǎn)覆蓋的面積之和的比值[10]。

覆蓋效率反映了傳感器節(jié)點(diǎn)覆蓋的冗余程度，覆蓋效率與節(jié)點(diǎn)冗余程度成反比，即：高覆蓋率，低冗余度；反之亦然。覆蓋效率也是每個(gè)節(jié)點(diǎn)的平均覆蓋率。

定義3（覆蓋重?cái)?shù)）給定一個(gè)平面監(jiān)測(cè)區(qū)域，如果其中的任意一個(gè)物理位置都至少落在k個(gè)傳感器節(jié)點(diǎn)的感知范圍之內(nèi)，則稱無(wú)線傳感器網(wǎng)絡(luò)k-度覆蓋[14]。

其中，KA為S(A)區(qū)域的覆蓋重?cái)?shù)；ki為第i個(gè)節(jié)點(diǎn)感知范圍。在某些應(yīng)用環(huán)境下，并非對(duì)全網(wǎng)進(jìn)行完全覆蓋，只要完成對(duì)所關(guān)注目標(biāo)節(jié)點(diǎn)覆蓋即可，這稱為部分覆蓋或有效覆蓋。

定義4（覆蓋均勻性）一般用節(jié)點(diǎn)間距離標(biāo)準(zhǔn)差加以表示，即：

其中，U表示為在監(jiān)測(cè)區(qū)域內(nèi)，節(jié)點(diǎn)覆蓋均勻特性參數(shù)，n為傳感器節(jié)點(diǎn)總數(shù)量；Ki為第i個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)；di,j為任意兩個(gè)節(jié)點(diǎn)之間歐拉距離；Mi為第i個(gè)節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)距離的平均值。

定義5（覆蓋時(shí)間）目標(biāo)被完全覆蓋或者跟蹤時(shí)，所有工作節(jié)點(diǎn)從啟動(dòng)到就緒所需要的時(shí)間[16]。

定義6（支配集）在圖G=(V,E)中，若找到一個(gè)V的一個(gè)子集S?V，S≠?，對(duì)于?si?V-S，S都至少與V-S中的一個(gè)節(jié)點(diǎn)相鄰，則稱S是圖G的支配集（dominating set，DS）。DS 中的節(jié)點(diǎn)稱為支配集節(jié)點(diǎn)，不在該集中的節(jié)點(diǎn)稱為被支配節(jié)點(diǎn)，即：圖中的每個(gè)節(jié)點(diǎn)都屬于子集或至少是子集中一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)[18]。

為了進(jìn)一步研究網(wǎng)絡(luò)覆蓋問(wèn)題，本文將傳感器節(jié)點(diǎn)劃分成若干個(gè)簇。分簇的主要目的在于：實(shí)現(xiàn)全網(wǎng)能量的均衡，達(dá)到簇內(nèi)節(jié)點(diǎn)能量的平衡；提高網(wǎng)絡(luò)覆蓋效率；抑制由延時(shí)帶來(lái)的能量快速消耗；增加連通性并減少延時(shí)；實(shí)現(xiàn)最小化簇?cái)?shù)量，從而延長(zhǎng)網(wǎng)絡(luò)生存周期[22-24]。分簇的主要任務(wù)在于：對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)進(jìn)行實(shí)時(shí)連續(xù)覆蓋，并按照分簇要求將若干傳感器節(jié)點(diǎn)劃分成多個(gè)可以相互通信，覆蓋所有傳感器節(jié)點(diǎn)的多個(gè)簇，當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，可以隨時(shí)更新簇結(jié)構(gòu)以便更好修護(hù)和管理簇；共組織形式主要體現(xiàn)在將地理位置不同的若干個(gè)相鄰傳感器節(jié)點(diǎn)通過(guò)感知能力劃分為大小不一的簇，從而便于完全對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的有效覆蓋。分簇結(jié)構(gòu)下的移動(dòng)目標(biāo)節(jié)點(diǎn)的覆蓋如圖1 所示。

Fig.1 Network coverage model of mobile target nodes under cluster structure圖1 分簇結(jié)構(gòu)下的移動(dòng)目標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋模型

圖1 給出了分簇結(jié)構(gòu)下的移動(dòng)目標(biāo)節(jié)點(diǎn)的網(wǎng)絡(luò)覆蓋模型。從圖1 中可以看出，本文將傳感器節(jié)點(diǎn)劃分成四個(gè)簇，當(dāng)移動(dòng)目標(biāo)節(jié)點(diǎn)處于某個(gè)簇當(dāng)中時(shí)，就可以完成對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的有效覆蓋；當(dāng)移動(dòng)目標(biāo)遠(yuǎn)離該簇時(shí)，由該簇的簇首節(jié)點(diǎn)向相鄰簇首節(jié)點(diǎn)發(fā)送消息，并喚醒相鄰的簇首節(jié)點(diǎn)繼續(xù)對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)進(jìn)行有效覆蓋。在研究覆蓋過(guò)程中，不需求對(duì)整個(gè)監(jiān)測(cè)區(qū)域進(jìn)行有效覆蓋，而只對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)進(jìn)行有效覆蓋，其目的是抑制節(jié)點(diǎn)能量的消耗，延長(zhǎng)網(wǎng)絡(luò)生存周期。

1.2 覆蓋模型分析

在上述分析的基礎(chǔ)上，為了進(jìn)一步提高覆蓋效率，延長(zhǎng)網(wǎng)絡(luò)生存周期，優(yōu)化簇內(nèi)結(jié)構(gòu)，本文引入了智能算法中的遺傳算法對(duì)覆蓋率和簇結(jié)構(gòu)進(jìn)行優(yōu)化，以達(dá)到覆蓋最優(yōu)效果。

對(duì)于給定的傳感器節(jié)點(diǎn)集合S={s1,s2,…,sN}，個(gè)體si∈S的適應(yīng)值為f(sj)，其選擇概率為：

式（6）決定了下一周期傳感器節(jié)點(diǎn)集合中個(gè)體的概率分布。其中，上一周期中傳感器節(jié)點(diǎn)的生存期望數(shù)目為：

在節(jié)點(diǎn)集合中，傳感器節(jié)點(diǎn)自身差異性較大，如能量、感知距離等因素，使得最優(yōu)和最差節(jié)點(diǎn)選 擇概率出現(xiàn)明顯不同，因此，在下一周期內(nèi)，最優(yōu)節(jié)點(diǎn)選擇概率將會(huì)較高，而最差節(jié)點(diǎn)被選擇的概率將會(huì)較低。交叉操作是智能進(jìn)化算法中GA（genetic algorithm）算法具備的原始性的獨(dú)有的特征。在動(dòng)態(tài)分簇過(guò)程中，為了增加簇與簇之間的重組，本文采用了交叉操作。對(duì)于選定的多個(gè)簇，隨機(jī)選擇多個(gè)交叉點(diǎn)，構(gòu)成新的交叉集合。

將L位節(jié)點(diǎn)重新劃分到新簇的相關(guān)位置的集合為：

算子形式定義為：

在采用不同的交叉算子對(duì)GA 定性計(jì)算時(shí)影響較大，在不同的簇內(nèi)隨機(jī)選取兩個(gè)不同節(jié)點(diǎn)si、sj，可按下列進(jìn)行交叉操作。

再對(duì)WSNs（wireless sensor networks）中傳感器節(jié)點(diǎn)進(jìn)行重新劃分成簇時(shí)，當(dāng)時(shí)間為t1=T時(shí)，某簇中的節(jié)點(diǎn)重新劃分到另一簇時(shí)，對(duì)于本簇而言，其鏈表結(jié)構(gòu)發(fā)生了變化，就可以認(rèn)為該節(jié)點(diǎn)發(fā)生了變異。在遺傳算法中，變異算子是通過(guò)按變異概率pm隨機(jī)反轉(zhuǎn)某個(gè)傳感器節(jié)點(diǎn)來(lái)實(shí)現(xiàn)的，公式如下：

適應(yīng)值函數(shù)是評(píng)價(jià)重新組建簇內(nèi)成員覆蓋質(zhì)量的可行解集，是評(píng)價(jià)所需要的關(guān)于節(jié)點(diǎn)適應(yīng)值函數(shù)的計(jì)算次數(shù)。顯然，該值越小說(shuō)明相應(yīng)的GA 的搜索效率越高。適應(yīng)值函數(shù)分為在線搜索和離線搜索兩種形式。

在線性能反映了節(jié)點(diǎn)集合平均適應(yīng)值經(jīng)平滑處理后的變化情況，描述了節(jié)點(diǎn)集合的整體性和進(jìn)化能力。

其中，f(a*,t)=max{f(a1,t),f(a2,t),…,f(an,t)}，即當(dāng)前節(jié)點(diǎn)集合中最優(yōu)節(jié)點(diǎn)的適應(yīng)值。該指標(biāo)反映了節(jié)點(diǎn)集合中最優(yōu)節(jié)點(diǎn)適應(yīng)值經(jīng)平滑處理后的變化情況，描述了節(jié)點(diǎn)的進(jìn)化能力和GA 搜索能力。

式（16）中，b的理想值miny=y*，由于|y-b|=a＞0 時(shí)，F(xiàn)it(y)=0.5，故在理想情況下，α是適應(yīng)值為0.5。α、β是閾值參數(shù)，一般情況下α取值為[0.5,1.5]，β取值為[1.5,2.0]。

利用GA 思想可以通過(guò)改變遺傳算子改善簇內(nèi)結(jié)構(gòu)，從而優(yōu)化了網(wǎng)絡(luò)資源，抑制了節(jié)點(diǎn)能量的開(kāi)銷，達(dá)到了延長(zhǎng)網(wǎng)絡(luò)生存周期的目的。其主要原因在于在GA 算法中采用了可控制閾值參數(shù)改變分簇結(jié)構(gòu)，以保持簇內(nèi)節(jié)點(diǎn)的能量的均衡，這樣可以避免大量節(jié)點(diǎn)由于能量消耗過(guò)快而導(dǎo)致的網(wǎng)絡(luò)癱瘓，同時(shí)也克服了由于收斂速度過(guò)快而導(dǎo)致收斂于某一局部的極值點(diǎn)，而出現(xiàn)的早熟現(xiàn)象。當(dāng)某簇內(nèi)成員節(jié)點(diǎn)si和鄰居節(jié)點(diǎn)sj由競(jìng)爭(zhēng)關(guān)系（剩余能量、與簇首之間的距離）進(jìn)入下一周期，由式（16）計(jì)算出si和sj適應(yīng)值，即Fit(si)和Fit(sj)，當(dāng)Fit(sj)-Fit(si)＜0 時(shí)，sj直接進(jìn)入下一周期；否則，將si帶入下一周期，采用上述過(guò)程可以將某簇內(nèi)所有成員均遍歷一次后，保證簇內(nèi)所有成員能量的均衡，進(jìn)一步避免了算法過(guò)早進(jìn)入局部最優(yōu)解的可能性。

2 覆蓋質(zhì)量與OCC-CT 算法分析

2.1 有效覆蓋分析

對(duì)于移動(dòng)目標(biāo)而言，其所行走軌跡與傳感器節(jié)點(diǎn)所覆蓋形成的區(qū)域均顯現(xiàn)出不規(guī)則形狀。為了研究問(wèn)題的方便，本文采用正方形區(qū)域加以說(shuō)明和計(jì)算。計(jì)算正方形監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)期望值和隨機(jī)選擇k個(gè)覆蓋期望值均可以依托概率相關(guān)理論知識(shí)。

定理1傳感器節(jié)點(diǎn)的覆蓋率為p，對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)完成N次覆蓋后，該傳感器節(jié)點(diǎn)覆蓋期望值為E(X)=[1-(1-p)N]p-1。

證明設(shè)X為傳感器節(jié)點(diǎn)首次覆蓋移動(dòng)目標(biāo)節(jié)點(diǎn)時(shí)的轉(zhuǎn)換次數(shù)，即X∈[1,2,…,N]，當(dāng)X=k時(shí)，存在1 ≤k≤N-1 時(shí)，表示傳感器節(jié)點(diǎn)在N-1 次前并沒(méi)有覆蓋移動(dòng)目標(biāo)節(jié)點(diǎn)，因此X的分布密度函數(shù)為：

計(jì)算式（17）可得：

即：

將式（20）代入式（18），可得：

證明完畢。

推論1傳感器節(jié)點(diǎn)的覆蓋率為p，傳感器節(jié)點(diǎn)首次完成對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)覆蓋的期望值為：E(X)=1/p，D(X)=(1-p)/p2。

證明依題意可知，在監(jiān)測(cè)區(qū)域內(nèi)任意傳感器節(jié)點(diǎn)的覆蓋率為p，未被傳感器節(jié)點(diǎn)所覆蓋的概率為1-p，令q=1-p，可得傳感器節(jié)點(diǎn)首次覆蓋移動(dòng)目標(biāo)節(jié)點(diǎn)的期望值為：

覆蓋問(wèn)題的研究本質(zhì)是要在兼顧感知、通信和連通前提下，監(jiān)測(cè)區(qū)域上節(jié)點(diǎn)部署時(shí)使用的節(jié)點(diǎn)數(shù)量少，即重復(fù)最少的無(wú)盲區(qū)覆蓋。在上述分析中，節(jié)點(diǎn)覆蓋的物理模型應(yīng)因不同的物理空間而取不同的形式（如：物理參數(shù)），才能夠使監(jiān)測(cè)區(qū)域上節(jié)點(diǎn)部署時(shí)在保證無(wú)盲區(qū)覆蓋的前提下使用的節(jié)點(diǎn)數(shù)量最少[25-27]。因此，本文引入了定理2 和推論2。

定理2在面積為A監(jiān)測(cè)區(qū)域內(nèi)，隨機(jī)從節(jié)點(diǎn)集合中選擇k個(gè)傳感器節(jié)點(diǎn)，其覆蓋期望值滿足：

證明根據(jù)定義1 可知，在監(jiān)測(cè)區(qū)域內(nèi)，任意傳感器節(jié)點(diǎn)的覆蓋率為：

由于傳感器節(jié)點(diǎn)感知半徑服從于正態(tài)分布(R0,σ2)，R0表示為均值，σ2為方差。對(duì)于移動(dòng)目標(biāo)節(jié)點(diǎn)而言，其被覆蓋到的覆蓋率為：

計(jì)算可得：

化簡(jiǎn)式（28）可得：

化簡(jiǎn)式（29）可得：

由于傳感器節(jié)點(diǎn)在工作中彼此之間相互獨(dú)立，根據(jù)概率理論中獨(dú)立性質(zhì)可知，移動(dòng)目標(biāo)節(jié)點(diǎn)被k個(gè)傳感器節(jié)點(diǎn)所覆蓋的期望值為：

證明完畢。

為了減少網(wǎng)絡(luò)延時(shí)，以最大限度提高網(wǎng)絡(luò)生存周期，在覆蓋過(guò)程中盡量要用最少節(jié)點(diǎn)完成最大面積的覆蓋，因此，本文引入了推論2。

推論2完成監(jiān)測(cè)區(qū)的有效覆蓋，節(jié)點(diǎn)最少數(shù)量為：

證明給定一個(gè)非常小的正整數(shù)ε=10-5，對(duì)于任意傳感器節(jié)點(diǎn)覆蓋期望值均大于ε可得：

對(duì)式（32）兩邊取對(duì)數(shù)，可得：

求k：

即：完成監(jiān)測(cè)區(qū)域內(nèi)有效覆蓋時(shí)，所需最少傳感器節(jié)點(diǎn)數(shù)量為：

證明完畢。

2.2 成簇分析

分簇的目的在于將監(jiān)測(cè)區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)劃分成地位等同的若干相鄰域。每個(gè)簇內(nèi)，均由一個(gè)主簇首節(jié)點(diǎn)和若干個(gè)簇成員節(jié)點(diǎn)組合而成。低一級(jí)網(wǎng)絡(luò)的簇首節(jié)點(diǎn)是高一級(jí)網(wǎng)絡(luò)中的簇成員節(jié)點(diǎn)，由最高層的簇首節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)通信。在分簇拓?fù)涔芾斫Y(jié)構(gòu)中，網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)可能劃分為簇首節(jié)點(diǎn)和簇成員節(jié)點(diǎn)。簇首節(jié)點(diǎn)是按照某種算法或規(guī)則選舉出來(lái)的，用于控制與管理簇成員節(jié)點(diǎn)，協(xié)調(diào)簇內(nèi)各類任務(wù)，完成簇內(nèi)數(shù)據(jù)收集和融合的指揮中心。在經(jīng)過(guò)N輪周期，簇首節(jié)點(diǎn)要按照某種算法進(jìn)行重新選舉，以保證簇首節(jié)點(diǎn)有足夠能量完成上述操作。在分簇過(guò)程中，難免會(huì)出現(xiàn)節(jié)點(diǎn)分配不均勻現(xiàn)象，這樣就形成了冗余節(jié)點(diǎn)存在。當(dāng)移動(dòng)目標(biāo)節(jié)點(diǎn)通過(guò)工作冗余節(jié)點(diǎn)時(shí)，必然產(chǎn)生大量的冗余數(shù)據(jù)，對(duì)簇內(nèi)節(jié)點(diǎn)之間通信造成影響。本文就非對(duì)稱性鏈路的雙通信機(jī)制的研究引入了定理3 和定理4。

定理3刪除非對(duì)稱性鏈路后，子圖Gs連通性保持不變。

證明依據(jù)題意可知，圖Gs是圖G的子圖。則?sj∈C(hi)，hi→sj，即hi與sj之間互相可達(dá)。假設(shè)d(hi,sj)＜R(hi)和d(hi,si)＞R(sj)，則在sj與hi之間存在一條有向路徑l=sj→sl→…→sk→hi。由于簇內(nèi)成員節(jié)點(diǎn)的同構(gòu)性，si→sj?sj→si，因此sk→sl→…→sj。由于R(hi)≥R(sk)，sk→hi?hi→sk。因此，可得到hi→sk→sl→…→sj。即刪除有向邊(hi,si)，也不會(huì)影響hi與sj之間的雙向連通性。

證明完畢。

定理4當(dāng)m個(gè)移動(dòng)目標(biāo)節(jié)點(diǎn)經(jīng)過(guò)某簇時(shí)，至少存在一條路徑，使得m個(gè)目標(biāo)節(jié)點(diǎn)所移動(dòng)的最優(yōu)路徑的概率Pr(?Pm) 大于或等于1-(1-cm-1p)S，其中，，且C=(1-ρ)L。

證明當(dāng)且僅當(dāng)，設(shè)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的所構(gòu)成的邊集為(k,l)，有限多的路由路徑為u，則：

因?yàn)棣う觡l≥0 且ρ＞0，對(duì)于從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所構(gòu)成的邊集而言，即τkl的值在m+1 周期相同的，如果常數(shù)C＞0，則：

由式（37）和式（38）計(jì)算可得：

λkl在m+1 周期與m周期是相同的，因此，使用遞歸計(jì)算法可以得到式（40）：

在不失一般性的條件下，假定期望值ηkl(u)可以使用Γ=1 的方法被規(guī)范化，即對(duì)所有路由邊集(k,l)及全局進(jìn)行優(yōu)化，可得：

由遺傳算法的轉(zhuǎn)移概率公式計(jì)算節(jié)點(diǎn)r?u時(shí)，滿足不等式條件為：

由式（36）和式（43）可得：

由于節(jié)點(diǎn)之間相互獨(dú)立，由概率理論相關(guān)知識(shí)可得：

證明完畢。

2.3 算法描述與實(shí)現(xiàn)

本文OCC-CT 算法是傳感器節(jié)點(diǎn)建立在傳感器節(jié)點(diǎn)協(xié)同覆蓋基礎(chǔ)上，將所有傳感器節(jié)點(diǎn)劃分成若干個(gè)簇，并以節(jié)點(diǎn)能量較高，計(jì)算能力較強(qiáng)，距離Sink節(jié)點(diǎn)較近的節(jié)點(diǎn)充當(dāng)簇首節(jié)點(diǎn)。網(wǎng)絡(luò)運(yùn)行的初始階段，由于每個(gè)傳感器節(jié)點(diǎn)能量均等，成員節(jié)點(diǎn)首先向簇首節(jié)點(diǎn)發(fā)送一個(gè)“Coverage”消息，當(dāng)簇首節(jié)點(diǎn)成功接收后，開(kāi)辟一定存儲(chǔ)空間，構(gòu)建存儲(chǔ)鏈表，并將收集到的消息存放在該鏈表中，其中“Coverage”消息中包含了發(fā)送節(jié)點(diǎn)的ID 信息和當(dāng)前覆蓋特性以及該節(jié)點(diǎn)當(dāng)前的位置信息和覆蓋期望值等。經(jīng)過(guò)一輪或幾輪周期后，簇首收集完成本簇的數(shù)據(jù)信息之后，對(duì)本簇所有節(jié)點(diǎn)按照能量和距離優(yōu)先規(guī)則進(jìn)行重新排序，并將新產(chǎn)生的節(jié)點(diǎn)序列存儲(chǔ)在鏈表之中，同時(shí)對(duì)覆蓋期望值和能量以及距離較優(yōu)的傳感器節(jié)點(diǎn)賦予最高的權(quán)值以充當(dāng)簇首節(jié)點(diǎn)；而后，利用單向查找算法在鏈表中查找滿足下一周期覆蓋條件的節(jié)點(diǎn)，并向該成員發(fā)送“Notice”消息，以調(diào)度該節(jié)點(diǎn)對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的覆蓋。本文OCC-CT 算法分為七個(gè)步驟：

步驟1根據(jù)式（23）和式（24）節(jié)點(diǎn)的協(xié)同特性對(duì)每個(gè)傳感器節(jié)點(diǎn)的覆蓋期望值進(jìn)行計(jì)算以確定分簇結(jié)構(gòu)。

步驟2簇首節(jié)點(diǎn)建立鏈表，接收成員節(jié)點(diǎn)發(fā)送的“Coverage”消息。其中包含了該成員節(jié)點(diǎn)的ID 和覆蓋特性以及位置消息和覆蓋期望值等信息。

步驟3經(jīng)過(guò)多輪周期后，簇首節(jié)點(diǎn)依據(jù)式（29）和式（31）對(duì)存儲(chǔ)在鏈表中的節(jié)點(diǎn)按照覆蓋期望值和能量大小進(jìn)行排序，同時(shí)對(duì)覆蓋期望值和能量以及距離較優(yōu)的傳感器節(jié)點(diǎn)賦予較高的權(quán)值。

步驟4簇首節(jié)點(diǎn)在鏈表中查找符合下一周期覆蓋條件的傳感器節(jié)點(diǎn)，并做以標(biāo)注；同時(shí)利用式（43）選舉出下一輪的簇首節(jié)點(diǎn)。

步驟5當(dāng)簇首完成上述操作后計(jì)算該節(jié)點(diǎn)是否滿足下一周期的覆蓋條件；如果滿足，向該節(jié)點(diǎn)發(fā)送“Notice”消息，該節(jié)點(diǎn)接收到“Notice”消息后啟動(dòng)感知模塊完成對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的覆蓋；否則轉(zhuǎn)入步驟2。

步驟6當(dāng)移動(dòng)目標(biāo)節(jié)點(diǎn)被k個(gè)節(jié)點(diǎn)所覆蓋時(shí)，簇首節(jié)點(diǎn)重新在鏈表中進(jìn)行遍歷，查找滿足覆蓋條件的節(jié)點(diǎn)，并返回步驟5；否則執(zhí)行步驟7。

步驟7當(dāng)移動(dòng)目標(biāo)節(jié)點(diǎn)離開(kāi)本簇時(shí)，由簇首節(jié)點(diǎn)發(fā)送消息給相鄰簇的簇首節(jié)點(diǎn)，重新開(kāi)始下一周期的覆蓋，并返回步驟1，直到移動(dòng)目標(biāo)節(jié)點(diǎn)被傳感器節(jié)點(diǎn)完全覆蓋。

3 體系評(píng)估與分析

為了進(jìn)一步驗(yàn)證本文OCC-CT算法的穩(wěn)定性和有效性，本文仿真工具借助于Matlab2013與文獻(xiàn)[11-13]在網(wǎng)絡(luò)覆蓋率、網(wǎng)絡(luò)生存周期以及網(wǎng)絡(luò)能量開(kāi)銷等方面進(jìn)行對(duì)比實(shí)驗(yàn)，仿真參數(shù)如表1 所示。

Table 1 Parameter list表1 參數(shù)列表

圖2 至圖4 給出了不同時(shí)間下簇首與簇成員的分簇結(jié)構(gòu)示意圖。從圖中可以看出，不同時(shí)間下，簇首與簇成員所形成的簇是不同的。本文采用了動(dòng)態(tài)參數(shù)為α=0.5，β=1.5，λ=1.2，同時(shí)本文考慮到簇首與簇成員節(jié)點(diǎn)之間的距離關(guān)系以及簇首節(jié)點(diǎn)與基站之間的距離關(guān)系，所選擇節(jié)點(diǎn)更趨向于離基站較近和節(jié)點(diǎn)能量較高的節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，這樣就可以有效地減少簇成員節(jié)點(diǎn)在傳輸數(shù)據(jù)時(shí)的能量消耗問(wèn)題。本文OCC-CT 算法依據(jù)節(jié)點(diǎn)在鏈表中的排序以及權(quán)值大小，隨機(jī)選舉多個(gè)節(jié)點(diǎn)作為簇首節(jié)點(diǎn)，簇內(nèi)成員節(jié)點(diǎn)個(gè)數(shù)也顯現(xiàn)隨機(jī)性，這樣可以保證簇的覆蓋范圍較為均衡，平衡了成員節(jié)點(diǎn)在覆蓋過(guò)程能量不均衡等問(wèn)題。而文獻(xiàn)[10]則是利用主副雙簇頭管理方式。在競(jìng)爭(zhēng)簇首時(shí)，由于成簇原因較為復(fù)雜，NDADA（node deployment，assignment method with data association attributes）算法采用主簇頭位于簇中心，以快速收集數(shù)據(jù)；副簇頭位于基站較近位置，以便于將主簇頭發(fā)來(lái)的數(shù)據(jù)快速傳輸給基站，但文獻(xiàn)[10]并未考慮簇內(nèi)節(jié)點(diǎn)能量均衡問(wèn)題，導(dǎo)致簇內(nèi)節(jié)點(diǎn)能量消耗過(guò)快。

Fig.2 t=300 s,clustering structure of cluster head and member nodes圖2 t=300 s，簇首與成員節(jié)點(diǎn)分簇結(jié)構(gòu)

圖5 和圖6 以及圖7 和圖8 給出的是300 m×300 m 和600 m×600 m 監(jiān)測(cè)區(qū)域不同參數(shù)下，傳感器節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)覆蓋率比對(duì)示意圖。本文選取了四組不同參數(shù)，分別為：（α=0.7,β=1.8,λ=1.2），（α=0.5,β=1.5,λ=1.0），（α=0.9,β=2.0,λ=1.5），（α=0.6,β=1.6,λ=1.3）。從上述四個(gè)圖中可以看出，網(wǎng)絡(luò)覆蓋率與傳感器節(jié)點(diǎn)數(shù)量顯現(xiàn)出正比現(xiàn)象，即：網(wǎng)絡(luò)覆蓋率隨傳感器節(jié)點(diǎn)數(shù)量遞增而增加。通過(guò)比對(duì)可知：本文OCC-CT 算法在任意傳感器節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)覆蓋率均高于其他三種算法。在圖5 中，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為90 時(shí)，本文OCC-CT 算法的網(wǎng)絡(luò)覆蓋率達(dá)到了60%和52%，而其他三種算法的網(wǎng)絡(luò)覆蓋率分別為48%、44%和34%；當(dāng)傳感器節(jié)點(diǎn)數(shù)量為130時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)覆蓋率為92%、80%，其他三種算法的網(wǎng)絡(luò)覆蓋率為74%、68%和47%，其本文OCC-CT 算法平均網(wǎng)絡(luò)覆蓋率為86%，高于TMLBSs算法0.12，MWSAC算法0.18和NDADA算法0.39。在圖6 中，在傳感器節(jié)點(diǎn)數(shù)量為90 時(shí)，本文OCC-CT 算法的網(wǎng)絡(luò)覆蓋率達(dá)到了72%和64%，而其他三種算法的網(wǎng)絡(luò)覆蓋率分別為51%、47%和42%；當(dāng)傳感器節(jié)點(diǎn)數(shù)量為130時(shí)，本文OCC-CT算法網(wǎng)絡(luò)覆蓋率為98%、90%，其他三種算法的網(wǎng)絡(luò)覆蓋率為79%、76%和67%，其本文OCC-CT算法平均網(wǎng)絡(luò)覆蓋率為94%，高于TMLBSs 算法0.15，MWSAC 算法0.18 和NDADA算法0.27。綜合上述分析，在參數(shù)為（α=0.7,β=1.8,λ=1.2），（α=0.5,β=1.5,λ=1.0）時(shí)，本文OCC-CT算法網(wǎng)絡(luò)覆蓋率平均高于其他三種算法網(wǎng)絡(luò)覆蓋率為0.23；在參數(shù)為（α=0.9,β=2.0,λ=1.5），（α=0.6,β=1.6,λ=1.3）時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)覆蓋率平均高于其他三種算法網(wǎng)絡(luò)覆蓋率為0.20。

Fig.3 t=500 s,clustering structure of cluster head and member nodes圖3 t=500 s，簇首與成員節(jié)點(diǎn)分簇結(jié)構(gòu)

Fig.4 t=800 s,clustering structure of cluster head and member nodes圖4 t=800 s，簇首與成員節(jié)點(diǎn)分簇結(jié)構(gòu)

Fig.5 Comparison of network coverage rate and number of nodes under different parameters in 300 m×300 m圖5 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.6 Comparison of network coverage rate and number of nodes under different parameters in 300 m×300 m圖6 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)數(shù)量比對(duì)

圖9 和圖10 以及圖11 和圖12 給出的是300 m×300 m 和600 m×600 m 監(jiān)測(cè)區(qū)域不同參數(shù)下，網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)覆蓋率比對(duì)示意圖。本文選取了四組不同參數(shù)，分別為：（α=0.7,β=1.8,λ=1.2），（α=0.5,β=1.5,λ=1.0），（α=0.9,β=2.0,λ=1.5），（α=0.6,β=1.6,λ=1.3）。從圖9 和圖11 可以看出，隨著網(wǎng)絡(luò)運(yùn)行時(shí)間的增加，網(wǎng)絡(luò)覆蓋率也隨之增加。當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間達(dá)到300 s 和700 s 時(shí)，四種算法的網(wǎng)絡(luò)覆蓋率均達(dá)到平衡狀態(tài)，但本文OCC-CT 算法的網(wǎng)絡(luò)覆蓋率要高于其他三種算法。從圖9 中可以看出，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為300 s 時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)覆蓋率達(dá)到了99%、92%，而其他三種算法的網(wǎng)絡(luò)覆蓋率分別為：77%、72%和62%；網(wǎng)絡(luò)運(yùn)行時(shí)間為300 s 時(shí)，本文OCC-CT 算法平均網(wǎng)絡(luò)覆蓋率為96%，分別高于其他三種算法0.19、0.24 和0.34；從圖11 中可以看出，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為700 s 時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)覆蓋率達(dá)到了99%、86%，而其他三種算法的網(wǎng)絡(luò)覆蓋率分別為：78%、70%和65%；網(wǎng)絡(luò)運(yùn)行時(shí)間為700 s時(shí)，本文OCC-CT 算法平均網(wǎng)絡(luò)覆蓋率為93%，分別高于其他三種算法0.15、0.23 和0.28；圖10 和圖12給出的是在監(jiān)測(cè)300 m×300 m，600 m×600 m 不同參數(shù)下的網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)覆蓋率比對(duì)示意圖。圖10 和圖12 采用的參數(shù)為（α=0.9,β=2.0,λ=1.5），（α=0.6,β=1.6,λ=1.3），從圖中可以看出，隨著網(wǎng)絡(luò)時(shí)間的推移四種算法的網(wǎng)絡(luò)覆蓋率均處于平穩(wěn)狀態(tài)，但本文OCC-CT 算法網(wǎng)絡(luò)覆蓋率要高于其他三種算法。在圖10中，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為400 s 時(shí)，本文兩組參數(shù)均達(dá)到了100%，而其他三種算法均低于該值，分別是83%、76%和68%，平均值高于其他三種算法分別為0.17、0.24 和0.32；在圖12 中，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為800 s 時(shí)，本文OCC-CT 算法分別高于其他三種算法分別為0.13、0.22和0.27。綜合上述分析結(jié)果可以看出，本文OCC-CT 算法在傳感器節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)覆蓋率和網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)覆蓋率對(duì)比實(shí)驗(yàn)中，均高于其他三種算法，從而進(jìn)一步說(shuō)明了本文OCC-CT 算法具有較強(qiáng)穩(wěn)定性和有效性。

Fig.7 Comparison of network coverage rate and number of nodes under different parameters in 600 m×600 m圖7 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.8 Comparison of network coverage rate and number of nodes under different parameters in 600 m×600 m圖8 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.9 Comparison of network coverage rate and running time under different parameters in 300 m×300 m圖9 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與運(yùn)行時(shí)間比對(duì)

Fig.10 Comparison of network coverage rate and running time under different parameters in 300 m×300 m圖10 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與運(yùn)行時(shí)間比對(duì)

圖13 至圖16 給出的是300 m×300 m 和600 m×600 m 監(jiān)測(cè)區(qū)域不同參數(shù)下，傳感器節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)生存周期比對(duì)示意圖。從圖13 和圖14 中可以看出，隨著傳感器節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)生存周期也隨之增加，從增加的幅度可以看出，本文OCC-CT 算法的增幅明顯高于其他三種算法。在圖13中，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為90 時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)生存周期分別為525 s、465 s，而其他三種算法的網(wǎng)絡(luò)生存周期分別為375 s、335 s 和260 s，其本文OCC-CT 算法網(wǎng)絡(luò)生存周期平均值分別高于其他三種算法為120 s、160 s和235 s；而在圖14 中，當(dāng)傳感器節(jié)點(diǎn)數(shù)量為70 時(shí)，本文OCC-CT 算法網(wǎng)絡(luò)生存周期分別為615 s、500 s，而其他三種算法的網(wǎng)絡(luò)生存周期分別為405 s、345 s 和315 s，其本文OCC-CT 算法網(wǎng)絡(luò)生存周期平均值分別高于其他三種算法152.5 s、212.5 s 和242.5 s。其主要原因在于本文OCC-CT 算法采用的是對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)局部連續(xù)覆蓋方法，在覆蓋過(guò)程中利用遺傳算法動(dòng)態(tài)參數(shù)的可控性對(duì)網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)覆蓋率進(jìn)行優(yōu)化控制，以達(dá)到網(wǎng)絡(luò)資源的最佳配比結(jié)果；而TMLBSs 算法和MWSAC 算法則采用的是對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)連續(xù)覆蓋方法完成對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的覆蓋控制，而沒(méi)有考慮當(dāng)移動(dòng)目標(biāo)節(jié)點(diǎn)遠(yuǎn)離某簇后，該簇的工作狀態(tài)，NDADA 算法采用的是一種連續(xù)全局覆蓋方法對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)的連續(xù)覆蓋，也就相當(dāng)于對(duì)整個(gè)監(jiān)測(cè)區(qū)域的完全覆蓋，并沒(méi)有考慮網(wǎng)絡(luò)能量的消耗問(wèn)題。圖15和圖16的工作原理與圖13和圖14相似。

Fig.11 Comparison of network coverage rate and running time under different parameters in 600 m×600 m圖11 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與運(yùn)行時(shí)間比對(duì)

Fig.12 Comparison of network coverage rate and running time under different parameters in 600 m×600 m圖12 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)覆蓋率與運(yùn)行時(shí)間比對(duì)

Fig.13 Comparison of network lifetime and number of nodes under different parameters in 300 m×300 m圖13 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)生存周期與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.14 Comparison of network lifetime and number of nodes under different parameters in 300 m×300 m圖14 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)生存周期與節(jié)點(diǎn)數(shù)量比對(duì)

圖17 至圖20 給出的是300 m×300 m 和600 m×600 m 監(jiān)測(cè)區(qū)域不同參數(shù)下，網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)能耗比對(duì)示意圖。從圖中可以看出，隨著網(wǎng)絡(luò)運(yùn)行時(shí)間增長(zhǎng)，四種算法網(wǎng)絡(luò)能耗均有所下降，但本文OCCCT 算法網(wǎng)絡(luò)能耗下降的幅度較少，而NDADA 算法網(wǎng)絡(luò)能耗下降幅度較大。現(xiàn)以圖17 為例進(jìn)行分析，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為400 s 時(shí)，本文OCC-CT 算法剩余能量為585 J 和555 J，而其他三種算法剩余能量為535 J、515 J 和510 J，其本文OCC-CT 算法剩余能量平均值分別高于其他三種算法35 J、55 J 和60 J；在圖18 中，當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)間為500 s時(shí)，本文OCC-CT 算法剩余能量為610 J 和560 J，而其他三種算法剩余能量為560 J、520 J 和485 J，其本文OCC-CT 算法剩余能量平均值分別高于其他三種算法25 J、65 J 和100 J；綜合上述分析結(jié)果，本文OCC-CT 算法網(wǎng)絡(luò)生存周期和網(wǎng)絡(luò)能耗均明顯高于其他三種算法，從而驗(yàn)證了本文OCC-CT 算法的有效性和適應(yīng)性。

Fig.15 Comparison of network lifetime and number of nodes under different parameters in 600 m×600 m圖15 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)生存周期與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.16 Comparison of network lifetime and number of nodes under different parameters in 600 m×600 m圖16 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)生存周期與節(jié)點(diǎn)數(shù)量比對(duì)

Fig.17 Comparison of running time and network energy consumption under different parameters in 300 m×300 m圖17 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)能耗比對(duì)

Fig.18 Comparison of running time and network energy consumption under different parameters in 300 m×300 m圖18 300 m×300 m，不同參數(shù)下的網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)能耗比對(duì)

Fig.19 Comparison of running time and network energy consumption under different parameters in 600 m×600 m圖19 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)能耗比對(duì)

Fig.20 Comparison of running time and network energy consumption under different parameters in 600 m×600 m圖20 600 m×600 m，不同參數(shù)下的網(wǎng)絡(luò)運(yùn)行時(shí)間與網(wǎng)絡(luò)能耗比對(duì)

4 總結(jié)

基于無(wú)線傳感器網(wǎng)絡(luò)在覆蓋過(guò)程出現(xiàn)的節(jié)點(diǎn)能量問(wèn)題和數(shù)據(jù)冗余對(duì)通信鏈路的影響，本文提出了一種帶有可控閾值的優(yōu)化協(xié)同覆蓋算法。本文OCCCT 算法首先利用覆蓋模型對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)進(jìn)行了分析，同時(shí)給出了覆蓋模型的具體分析方法。其次，本文對(duì)覆蓋期望值進(jìn)行了分析和計(jì)算。給出了對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)完成N次覆蓋后，該傳感器節(jié)點(diǎn)覆蓋期望值計(jì)算方法以及完成對(duì)移動(dòng)目標(biāo)節(jié)點(diǎn)所需覆蓋的最少傳感器節(jié)點(diǎn)數(shù)量的計(jì)算過(guò)程以及最優(yōu)路徑選擇的概率計(jì)算方法。再次，本文給出了OCC-CT 算法描述過(guò)程和實(shí)現(xiàn)方法以及本文OCC-CT 算法復(fù)雜度的相關(guān)說(shuō)明。最后，本文利用仿真軟件對(duì)網(wǎng)絡(luò)成簇結(jié)構(gòu)、網(wǎng)絡(luò)覆蓋率、網(wǎng)絡(luò)生存周期以及網(wǎng)絡(luò)能耗四方面進(jìn)行了相關(guān)實(shí)驗(yàn)并給出了仿真實(shí)驗(yàn)對(duì)比步驟和方法，以此進(jìn)一步地說(shuō)明本文OCC-CT 算法具有較高的有效性和穩(wěn)定性。