孫澤宇，李傳鋒，邢蕭飛，來純曉

1.洛陽理工學院計算機與信息工程學院，河南洛陽471023

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

3.廣州大學計算機科學與網絡工程學院，廣州510006

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

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

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

（1）引入覆蓋模型并對該模型進行有效分析，給出相關定義及模型分析過程。

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

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

1 覆蓋模型建立與分析

1.1 假設與基本定義

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

（1）在監(jiān)測區(qū)域內，忽略傳感器節(jié)點邊界效應，其感知半徑遠小于監(jiān)測區(qū)域邊界長度。

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

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

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

（5）每個傳感器節(jié)點工作時均與時間同步，網關節(jié)點不可移動。

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

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

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

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

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

其中，KA為S(A)區(qū)域的覆蓋重數(shù)；ki為第i個節(jié)點感知范圍。在某些應用環(huán)境下，并非對全網進行完全覆蓋，只要完成對所關注目標節(jié)點覆蓋即可，這稱為部分覆蓋或有效覆蓋。

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

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

定義5（覆蓋時間）目標被完全覆蓋或者跟蹤時，所有工作節(jié)點從啟動到就緒所需要的時間[16]。

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

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

Fig.1 Network coverage model of mobile target nodes under cluster structure圖1 分簇結構下的移動目標節(jié)點的網絡覆蓋模型

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

1.2 覆蓋模型分析

在上述分析的基礎上，為了進一步提高覆蓋效率，延長網絡生存周期，優(yōu)化簇內結構，本文引入了智能算法中的遺傳算法對覆蓋率和簇結構進行優(yōu)化，以達到覆蓋最優(yōu)效果。

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

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

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

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

算子形式定義為：

在采用不同的交叉算子對GA 定性計算時影響較大，在不同的簇內隨機選取兩個不同節(jié)點si、sj，可按下列進行交叉操作。

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

適應值函數(shù)是評價重新組建簇內成員覆蓋質量的可行解集，是評價所需要的關于節(jié)點適應值函數(shù)的計算次數(shù)。顯然，該值越小說明相應的GA 的搜索效率越高。適應值函數(shù)分為在線搜索和離線搜索兩種形式。

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

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

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

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

2 覆蓋質量與OCC-CT 算法分析

2.1 有效覆蓋分析

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

定理1傳感器節(jié)點的覆蓋率為p，對移動目標節(jié)點完成N次覆蓋后，該傳感器節(jié)點覆蓋期望值為E(X)=[1-(1-p)N]p-1。

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

計算式（17）可得：

即：

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

證明完畢。

推論1傳感器節(jié)點的覆蓋率為p，傳感器節(jié)點首次完成對移動目標節(jié)點覆蓋的期望值為：E(X)=1/p，D(X)=(1-p)/p2。

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

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

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

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

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

計算可得：

化簡式（28）可得：

化簡式（29）可得：

由于傳感器節(jié)點在工作中彼此之間相互獨立，根據(jù)概率理論中獨立性質可知，移動目標節(jié)點被k個傳感器節(jié)點所覆蓋的期望值為：

證明完畢。

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

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

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

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

求k：

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

證明完畢。

2.2 成簇分析

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

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

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

證明完畢。

定理4當m個移動目標節(jié)點經過某簇時，至少存在一條路徑，使得m個目標節(jié)點所移動的最優(yōu)路徑的概率Pr(?Pm) 大于或等于1-(1-cm-1p)S，其中，，且C=(1-ρ)L。

證明當且僅當，設從源節(jié)點到目的節(jié)點的所構成的邊集為(k,l)，有限多的路由路徑為u，則：

因為Δτkl≥0 且ρ＞0，對于從源節(jié)點到目的節(jié)點所構成的邊集而言，即τkl的值在m+1 周期相同的，如果常數(shù)C＞0，則：

由式（37）和式（38）計算可得：

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

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

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

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

由于節(jié)點之間相互獨立，由概率理論相關知識可得：

證明完畢。

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

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

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

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

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

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

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

步驟6當移動目標節(jié)點被k個節(jié)點所覆蓋時，簇首節(jié)點重新在鏈表中進行遍歷，查找滿足覆蓋條件的節(jié)點，并返回步驟5；否則執(zhí)行步驟7。

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

3 體系評估與分析

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

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

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

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

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

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

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

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ù)下的網絡覆蓋率與節(jié)點數(shù)量比對

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ù)下的網絡覆蓋率與節(jié)點數(shù)量比對

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

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ù)下的網絡覆蓋率與節(jié)點數(shù)量比對

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結

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