一種高效的無線傳感器網絡目標覆蓋算法*

吳鋒

信陽農林學院 信息工程學院， 河南 信陽 464000

無線傳感器網絡(Wireless sensor networks， WSN)是由傳感器節點組成的分布式傳感網絡[1-2]， 在安全監控、 事件跟蹤和目標檢測等與監控相關的應用中起著至關重要的作用[3]． 傳感器包括通信、 電源、 傳感3個單元． 通信單元承擔著通過空間傳輸和接收信息的責任， 電源單元負責向通信和傳感單元有效地供電， 感測單元感測預期信息． 傳感器網絡的運行需要高效的算法來進行拓撲管理、 多通道訪問、 本地化、 連接和覆蓋． 由于WSN節點電池容量有限， 如何有效地利用節點能量成為WSN研究的熱點之一． 傳感器節點通常需要以延長網絡壽命的方式進行編程[4-5]， 通常采用間歇的休眠方式保存節點能量[6]． 將整個區域劃分為多個覆蓋集， 每個覆蓋集監視所有目標， 在保證能檢測目標節點的前提下， 僅一個傳感器節點覆蓋區域處于活動模式， 其余傳感器節點可以處于休眠模式[7]， 從而節省能量．

連通性用來解決從源傳感器到匯聚節點傳遞感知數據的問題． 如果網絡中每對節點間至少有一條路徑， 則稱傳感器網絡是連接的． 在單跳網絡中傳感器直接與中心節點/基站通信， 如果傳感器不能直接到達匯聚節點， 則需要多跳中繼， 傳感器可以作為中繼轉發數據[8]． 連通性受到拓撲修改、 節點丟失等的影響． 網絡連通性是無線傳感器網絡必不可少的重要服務質量， 在網絡的整個生命周期中， 傳感器應該在彼此的傳輸半徑內[9]．

在保證網絡節點覆蓋率和連通性的同時延長網絡壽命是WSN需要解決的主要問題， 學者們已經對延長網絡壽命進行了研究． 針對目標覆蓋， 各種優化算法用以提升WSN的性能， 如優先級、 部分覆蓋的優化． 文獻[10]提出基于優先級的具有可調整感知范圍的目標覆蓋方法， 該算法選擇最合適的感應范圍和傳感器方向滿足所有目標的覆蓋質量要求， 并最大化網絡壽命． 文獻[11]提出一種基于學習自動機來實現睡眠調度方法的新算法， 用來解決連續監視感興趣區域的部分覆蓋問題． 文獻[12]提出基于貪婪的部分覆蓋算法使用選定節點的鄰居節點來保留選定節點的連通性， 同時使用節點之間的重疊來達到所需的覆蓋率， 具有較高的能源效率． 但是， 現有的WSN目標覆蓋算法忽略了尋找最小可能跳數路徑， 并優化路徑損耗的問題， 導致能力覆蓋率和網絡生存周期具有進一步提升的空間．

在研究了現有WSN目標覆蓋算法的基礎上， 為了進一步提高能量高效覆蓋率， 延長網絡生存周期， 本文提出一種高效的無線傳感器網絡目標覆蓋算法來解決WSN的壽命優化問題． 該算法首先為每個傳感器找到距匯聚節點的最小跳躍距離， 隨后所有目標覆蓋傳感器都將各自具有目標身份的信息發送到匯聚節點， 請求尋找從傳感器覆蓋目標到匯聚節點使用最小能量的最小跳躍路徑． 當所有請求都到達匯聚節點時， 開始生成目標覆蓋傳感器的覆蓋集． 匯聚節點選擇一組不為空的覆蓋集， 獲得應答數據包的傳感器開始搜索到匯聚節點的最小可能跳數路徑(Minimum Possible Hop Count Path， MPHCP)， 最后通過跟蹤傳感器正在監控的目標數量和剩余能量尋找從覆蓋集到接收器的能量優化路徑， 為感測數據提供可擴展的連通性． 實驗結果顯示， 與其他算法相比， 本文算法的目標覆蓋平均網絡壽命延長， 同時消耗的平均能量更少．

1 準備工作

1.1 能耗模型

收發器消耗的能量用于在傳感器處發送和接收數據、 發射機電子設備的能量使用、 放大過程中的能量耗散和在感知目標時的能量使用． 本文使用etx(b，d)，erx(b)和esx(b)來表示兩個距離為d的傳感器間鏈路發送、 接收和感測b位數據所消耗的能量．

etx(b，d)=eelb+eambdη

(1)

erx(b)=eelb

(2)

esx(b)=esb

(3)

其中，eel表示發射機電子設備消耗的能量，eam表示運行發射器每位消耗的能量，η表示路徑損耗指數， 取值范圍在2～6之間， 取決于環境的衰落條件．es是感測1比特數據所消耗的能量， 發送、 接收和感測數據的b比特能量需求可以表示為：

el(b，d)=etx(b，d)+erx(b)+esx(b)

(4)

發送、 接收和感測b位數據后的剩余能量可以表示為：

er(b)=ei-et(b，d)

(5)

其中，ei表示傳感器的初始能量．

1.2 覆蓋集定義

感測區域中的傳感器形成網絡， 其中如果d(si，sj)≤R， ?1≤i，j≤N， 則兩個傳感器通過無線鏈路連接，R表示傳輸范圍． 本文將傳感器集合劃分為兩個不相交的集合St和Sr，St為覆蓋至少一個目標的傳感器集合，Sr為不覆蓋任何目標的傳感器集合． 設Ck?St∪Sr?k=1， 2， …，N是一組傳感器， 使T被Ck覆蓋和連接， 則可以用數學公式表示為：

1) 當ti∈T?i， 1≤i≤N時， 如果至少存在一個傳感器j， 1≤j≤N使得d(si，sj)≤r和sj∈Ck， 則稱T被Ck覆蓋．

2) 當ti∈T?i， 1≤i≤N時， 如果存在一組傳感器Ckj?Ck使得Ck包含來自St的僅一個成員和Sr的零個或多個成員， 且存在通過這些傳感器從匯點到屬于St傳感器的路徑， 則稱T由C連接．

1.3 模型定義

本文需要解決的問題是在保證Ck?k=1，2，…，N的傳感器數量最優和最小化網絡整體能耗的情況下， 最大限度地減少覆蓋集的數量， 即尋找可能的最大覆蓋數量， 其中每個傳感器Si， 1≤i≤N僅屬于一個覆蓋集Ck．

本文將尋找可能最大覆蓋數量的問題表述為整數線性規劃(Integer Linear Program， ILP)問題． 令C={C1，C2，C3…Cu}表示所有可能的覆蓋集集合， 每個覆蓋集覆蓋所有目標．

(6)

(7)

ILP的目標為：

(8)

(9)

式(8)的目標函數用來最大化不相交集合的數量， 每個集合覆蓋所有目標并通過將待激活傳感器的數量乘以小的正系數ρ(ρ≤1)來施加約束， 從而最小化每個集合中所使用的傳感器數目． ILP存在k個變量和(n+k)個約束條件， 式(9)規定了傳感器至多用于一個覆蓋集的條件． 上述ILP公式提供了最優解， 但對于大型問題實例是不可行的， 本文基于多項式時間算法來逼近問題的解．

1.4 模型假設

匯聚節點的位置對網絡性能有很大影響， 因此位置非常重要． 無線傳感器網絡中匯聚節點的優化定位存在參數多、 路由算法不同、 涉及大量傳感器節點、 傳感器節點不同能力等諸多挑戰． 因為會影響諸如能量消耗、 延遲、 吞吐量和網絡連接等性能指標， 匯聚節點定位需要精確地選擇匯聚節點的位置． 調整匯聚節點的位置可以提高WSN的可靠性， 因為匯聚節點最理想的初始位置可能會由于網絡的變化而變得無效． 本文匯聚節點位于目標節點附近， 將WSN限制為網狀拓撲， 如圖1所示． 圖1中黑色圓點表示傳感器網絡節點． 對系統模型進行如下假設：

圖1 具有網狀拓撲的WSN

1) 所有傳感器節點都是靜止的， 并且位于具有相同大小單元的二維正方形網格中．

2) 所有傳感器節點具有相同的初始能量．

3) 范圍是固定的， 等于網格中兩個相鄰節點之間的距離， 即一跳是一個網格單元邊長．

4) 傳感器節點通過沿最短路徑的多跳將數據中繼到匯聚節點．

傳感器網絡可以由點和邊組成的圖G(V，E)來表示， 其中V是傳感器節點的頂點，E邊緣充當兩個相鄰節點間的單跳連接． 如果傳感器節點通過一跳連接到匯聚節點， 那么數據以簡單的方式進行轉發， 否則將通過多跳進行數據轉發．

2 高效的無線傳感器網絡目標覆蓋算法

本文提出的算法首先為每個傳感器找到距匯聚節點的最小跳躍距離， 隨后所有目標覆蓋傳感器都將各自具有目標身份的信息發送到匯聚節點， 請求尋找從傳感器覆蓋目標到匯聚節點使用最小能量的最小跳躍路徑． 當所有請求都到達匯聚節點， 開始生成目標覆蓋傳感器的覆蓋集． 匯聚節點選擇一組不為空的覆蓋集， 獲得應答數據包的傳感器開始搜索到匯聚節點的最小可能跳數路徑(Minimum Possible Hop Count Path， MPHCP)， 匯聚節點按照用于偵聽的相同路徑向這些傳感器發送許可數據包， 選定的發送器在獲得許可數據包后開始感測． 在重新計算能量后， 通過先前找到的最節能路徑將生成的數據發送到匯聚節點， 一旦這組覆蓋集的壽命結束， 匯聚節點就為另一組傳感器做同樣的工作， 當完成了所有這樣的覆蓋集后， 匯聚節點就終止感測過程， 具體流程如圖2所示．

圖2 本文算法流程圖

2.1 為每個傳感器尋找距匯聚節點的最小跳躍距離

匯聚節點生成一個0跳的跳包， 并在其周圍的傳輸范圍Rc中轉發該數據包． 假設匯聚節點位于感測區域的中間(圖3)， 所有傳感器都用1跳和初始能量進行初始化， 獲得跳包的傳感器存儲跳數和能量的值． 如果跳數小于所存儲的跳數值， 更新跳數． 傳感器在等待一段時間后廣播相同的內容， 每個傳感器中的能量也會根據能耗模型進行更新． 每個相鄰節點處的剩余能量也與跳數信息一起被廣播到相鄰節點， 以便傳感器具有關于其最小距離和來自匯聚節點最小能量的信息． 在將跳數轉發到下一個傳感器之前， 傳感器會將其遞增1， 這有助于下一個傳感器知道從匯聚節點到自身的確切跳數及路由， 因為數據包還包含其所經過的傳感器ID． 傳感器具有關于自身能量、 鄰居能量、 傳感器ID和跳數的信息， 每個傳感器重復此廣播和更新過程， 直到覆蓋整個網絡．

圖3 跳包轉發

傳感器存儲有關傳感器的信息， 傳感器已向它們發送了具有最小跳數的數據包、 每個鄰居節點的剩余能量及自身的剩余能量． 用于存儲關于跳包信息的表包含以下字段： 跳數、 傳感器身份和剩余能量． 如果某個節點剩余能量相比其他節點嚴重不足時， 不能作為中繼節點使用．

跳距的目標是將最小跳數和剩余能量傳遞給每個傳感器， 因此必須確保在可能的范圍內具有較低跳計數值的傳感器必須開始參考數據包， 以避免冗余傳輸并延長使用壽命． 等待時間應該是傳感器可用跳數的函數， 引入等待時間的曲線可以防止跳包碰撞． 具體表達為：

Di=φie-φit

(10)

φi=f(λ，hci)， 1≤i≤N

(11)

(12)

該算法在線性時間內運行， 算法中沒有循環， 除了傳感器的等待時間外， 幾乎每個傳感器都需要恒定的時間來執行數據包轉發． 傳感器的等待時間由式(12)求得， 雖然是指數型， 但隨著時間t的增加迅速收斂．

2.2 發送請求尋找從自身到匯聚節點的可能最短路徑

該過程由覆蓋至少一個目標的所有傳感器啟動， 隨后搜索其鄰居的列表發送包含其身份及所覆蓋目標身份的請求數據包， 跳包轉發生成最初從匯點到所有傳感器的多跳路徑池． 為了找到最短路徑， 傳感器總是將請求數據包轉發到從中獲得最小跳數數據包和高剩余能量的同一傳感器， 所有收到請求數據包的傳感器都會向發送方傳感器發送確認． 如果傳感器未收到確認， 會將數據包重新發送到另一個傳感器， 該傳感器是其列表中下一個最遠的傳感器．

“現在的模式不是最終的版本，也并非完美，由于醫院的目標在變，所以要不停地修訂。”施秉銀說，為了醫院的發展，怎么調整目標或完善目標，是非常難的事情。最難的是，有些部門的工作很難考核。如后勤輔助部門，通下水道、修管道、環境巡視及一些外包服務，很難考核。

由于本節只有一個循環在所有傳感器上運行， 因此本節算法以線性時間運行， 不需要任何額外的傳輸來探索從傳感器到接收器的最小跳躍路徑． 通過這種方法， 可以保證算法運行時除數據感知和信息發送外的能耗最小．

2.3 尋找目標覆蓋的可能最大覆蓋數量

本文基于多項式時間算法來逼近問題的解． 一旦生成覆蓋集， 就從st中移除屬于該覆蓋集的相應傳感器， 并且再次按照式(8)和式(9)來求解問題， 重復這個過程可迭代地生成所有可能數量的覆蓋集． 本文采用貪婪的方法尋找最小成本覆蓋集作為上述問題的解決方案， 為此選擇包含覆蓋目標最多并且具有最高能量的傳感器． 該算法從左到右遍歷傳感器覆蓋目標的鄰接表， 如果兩個傳感器具有相同數量的覆蓋目標， 則選擇那個具有較大能量值的傳感器． 將已取走的傳感器刪除， 重復該過程到沒有需要刪除的傳感器為止．

2.4 尋找最小可能跳數路徑

在生成第一個覆蓋集后匯聚節點向傳感器發送應答數據包允許感測． 按照覆蓋集的生成順序選擇允許的傳感器組， 應答數據包包含數據包要遵循的路徑、 接收傳感器的標識、 覆蓋集編號和開始感測的時間， 應答包遵循的路徑與底層傳感器請求包的路徑保持相同． 通過這種機制， 可以節省大量的時間和能量， 并且應答包在盡可能短的時間內到達目的地．

所有收到請求應答包的傳感器都會啟動MPHCP算法． 在該算法下， 傳感器找到從自身到匯聚節點的最小可能跳數路徑， 位于覆蓋集中的傳感器不需要找到這樣的路徑． 傳感器使用MPHCP算法獲取應答包的相同路徑， 此路徑是從匯聚節點到傳感器的最小可能路徑． 之所以說“最小可能”， 是因為需要找到從底層傳感器到匯聚節點的最短路徑， 但是路徑的任何部分都不應與另一條路徑共用， 任何傳感器只能參與一條路徑． 一旦一組傳感器找到MPHCP， 匯聚節點啟動另一組覆蓋集開始查找其MPHCP． 在此算法中， 已經屬于另一條路徑的傳感器不計入路徑查找中．

2.5 優化路徑損耗

為了優化路徑的能量消耗， 傳感器從多跳路徑池中選擇路徑， 該多跳路徑池由跳包從匯聚節點轉發到所有傳感器． 本文選擇具有優化能耗最小跳數的路徑進行數據傳輸． 參與數據包傳輸、 接收和檢測目標的路徑的所有傳感器所消耗的能量ep表示為：

ep=[etx(b，d)+erx(b)+esx(b)]×h

(13)

其中， 路徑p由h個跳數組成，h個跳數連接p中的1個傳感器． 最小化路徑p中的跳數意味著最小化路徑能量ep， 最小化ep可設置為優化準則， 并表示為：

Minep=[etx(b，d)+erx(b)+esx(b)]×Max(δ)

(14)

其中，δ是每跳的平均進度， Max(δ)表示最大單跳距離， 并且eq表示在移除一個或多個躍點之后通過新的路由q從源傳感器向匯聚節點傳輸數據的能量消耗．

最小化路徑中的跳數， 使得在移除路徑中的一個或多個跳數(具有較少跳數的新路由)之后， 通過新路由q從源傳感器向匯聚節點傳輸數據所產生的能量消耗小于現有路由p的能耗． 本文通過最大化朝向匯聚節點的單跳進度來最小化跳數． 路徑中的平均單跳距離E(s)和平均跳數E(c)由以下公式給出：

(15)

(16)

根據本文提出的能量模型， 傳感器在發射、 接收和感知目標時消耗能量， 傳輸過程中消耗的能量是發送方傳感器和接收方傳感器之間距離的冪． 在兩個相鄰傳感器之間傳輸b比特數據， 每跳的平均能量消耗E(et(b，d))可以表示為：

(17)

因此， 參與包傳輸、 接收和檢測目標的路徑中所有傳感器消耗的平均能量E(ep)可以表示為：

E(ep)=E(et(b，d))×E(c)

(18)

3 通信開銷分析

在本文所提出的算法中， 當匯聚節點生成一個跳包時， 匯聚節點只發送一次信標， 其計數值為0， 并且在跳距算法的初始化階段將其轉發到周圍的傳輸范圍， 從而循環關于其跳計數值1和初始能量的信息． 在發送請求階段， 不需要發送額外的協調消息． 在發送請求階段， 每個傳感器節點將請求數據包轉發到獲得最小跳數數據包的同一傳感器， 并為ACK發送一次信標進行確認． 應答包遵循的路徑與傳感器請求包的路徑保持相同， 這將節省時間和能量， 并且使應答包在盡可能短的時間內到達目的地． 由于發送或接收單個數據包而消耗的能量幾乎與傳感器之間傳遞的指令數量相同， 當考慮實際的傳感器網絡時， 由于競爭而導致的重傳將能量消耗提高到很高的水平， 甚至發送消息． 因此， 在本文提出的協議中傳輸消息數量非常少， 這對于最小化能量消耗和延長系統壽命是可取的． 與減少通信開銷所節省的能量相比， 復雜計算所消耗的任何額外能量都可以忽略不計．

4 實驗結果與分析

本文在MATLAB中開發的模擬器中生成了模擬場景， 模擬器由傳感器部署模塊、 拓撲生成模塊等不同模塊組成， 模擬了一個由400個傳感器節點按照泊松點過程隨機分布的網絡， 每個傳感器的感應范圍為10 m， 傳輸范圍為50 m． 每次模擬運行20次， 取平均值來計算結果， 每個目標生成1 kb的恒定數據流量． 本文算法的仿真參數如表1所示． 將實驗結果與文獻[13]中提到的優化連接覆蓋集啟發式 (Optimized Connected Coverage Heuristic， OCCH)算法和文獻[14]中提到的通信加權貪婪覆蓋(Communication Weighted Greedy Cover， CWGC)算法進行分析和比較， OCCH和CWGC算法以能夠覆蓋所有目標的貪婪方式選擇源， 生成到信宿的最短路由路徑， 并更新通信開銷避免選擇具有低剩余能量的節點， 因此選擇這兩個算法與本文算法進行比較分析．

表1 實驗參數

圖4給出了在邊長為200 m，250 m和300 m的網絡區域中部署30個目標、 傳感器從50～400個變化時， 本文算法的平均能耗． 在本實驗中， 平均能耗包括為滿足覆蓋性和連接性要求而花費的能量．

由圖4可以看出， 在邊長為200 m的網絡區域中部署200～225個傳感器的能耗最小， 邊長為250 m的網絡區域中部署325～350個傳感器的能耗最小， 在邊長為300 m的網絡區域中部署375～400個傳感器的能耗最小． 因此， 實現最小能耗的傳感器數量隨著邊長增加而增加， 這是因為平均單跳距離隨著網絡面積增加而增加， 傳輸的能量需求是任意兩個相鄰傳感器之間距離因子的冪．

圖4 不同邊長網絡區域節點數的優化分析

圖5給出了期望路徑能量相對于跳數的分析結果． 期望路徑能量定義為所有參與傳輸、 接收和感知路徑的傳感器節點所消耗的能量． 該模擬使用30個隨機部署的目標， 傳感器數量從50～300個變化． 由圖5可以看出， 在較少的跳數下路徑節點消耗的能量要高得多． 當跳躍從10增加到20時， 路徑能量增加． 這是因為每跳距離隨著跳數增加而減小， 需要更多的多跳傳輸， 從而消耗了更多的能量． 對于5～10個跳數， 路徑能量保持最小． 因此， 應該首先考慮5～10跳范圍內的替代節能路由．

圖5 預期路徑能量與跳躍數

覆蓋時間定義為生成所有可能的覆蓋集所需的時間． 圖6給出了節點數不同時各算法的覆蓋時間， 覆蓋時間表示為生成所有可能的覆蓋集所需的時間．

由圖6可以看出， 覆蓋時間隨著節點密度增加而增加， 這是因為當節點密度增加時， 重復執行相同操作所消耗的時間增加． 本文算法的性能比OCCH和CWGC好， 這是因為本文算法首先為每個傳感器找到距匯聚節點的最小跳躍距離， 然后請求尋找從傳感器覆蓋目標到匯聚節點使用最小能量的最小跳躍路徑， 最后獲得應答數據包的傳感器開始搜索到匯聚節點的最小可能跳數路徑． 通過這種機制， 可以節省大量的時間和能量．

圖6 節點數不同時各算法的覆蓋時間

圖7給出了節點數不同時各算法的平均能量消耗． 平均能耗是網絡中所有傳感器總能耗與傳感器數量的比率， 包含傳感器在滿足覆蓋性和連通性要求時所消耗的能量． 由圖7可以看出， 平均能耗隨著傳感器數量的增加而下降， 這是因為任何兩個傳感器之間的平均距離隨傳感器數量的增加而減小， 所消耗的能量也隨之減少． 本文算法的平均能量消耗低于OCCH和CWGC， 這是因為本文算法除了采用最小跳躍距離、 最小跳躍路徑和最小可能跳數路徑這種機制進行數據傳輸外， 另外采用貪婪的方法尋找最小成本覆蓋集， 包含覆蓋目標最多并且具有最高能量的傳感器， 節省了大量能量．

圖7 節點數不同時各算法的平均能耗

網絡生存周期是指一個目標不能被任何傳感器節點監控或任何傳感器節點不能再將數據轉發到接收器的持續時間． 圖8給出了在由300個傳感器和30個目標組成的WSN環境下， 本文算法與OCCH算法和CWGC算法的網絡壽命隨區域面積的變化情況．

由圖8可以看出， 通信距離隨著面積的增加而增加， 導致傳感節點的密度降低． 由于節點密度降低， 網絡可靠性降低， 導致吞吐量降低和通信開銷增加， 使得各算法對區域變化敏感． 本文算法在網絡生命周期方面比其他兩個算法高出20%～30%．

圖8 面積不同時各算法的網絡生存周期

圖9給出了在由300個傳感器和面積為200×200 m2組成的WSN環境下， 本文算法與OCCH算法和CWGC算法的網絡壽命隨目標數量的變化情況． 由圖9可以看出， 網絡壽命隨著目標數量的增加而縮短， 這是因為隨著網絡中放置目標數量增加， 需要更多的傳感器處于活動狀態， 并且由于數據量的增加， 通信量負載也會加重． 本文算法在不同目標數量的網絡生存周期比OCCH和CWGC高出近20%．

圖9 目標數不同時各算法的網絡生存周期

圖10給出了在固定面積和目標的情況下， 本文算法與OCCH算法和CWGC算法的網絡壽命隨傳感器數量的變化情況． 由圖10可以看出， 網絡壽命隨節點密度增加而減少， OCCH算法和CWGC算法的網絡壽命較短． 本文提出的算法DCCA比在不同節點數的網絡生存周期OCCH和CWGC高出近50%．

圖9和圖10中本文算法性能都優于OCCH和CWGC算法． 這是因為本文算法在發送請求階段， 每個傳感器節點將請求數據包轉發到獲得最小跳數數據包的同一傳感器， 并為ACK發送一次信標進行確認． 應答包遵循的路徑與傳感器請求包的路徑保持相同， 并且應答包在盡可能短的時間內到達目的地， 減少了冗余， 節省了通信開銷． 而OCCH和CWGC使用公共節點通過增加關鍵節點的通信權重來中繼數據， 增加了通信開銷．

圖10 節點數不同時各算法的網絡生存周期

圖11給出了3種算法在區域200×200 m2網絡字段中部署的節點數量的最小網絡壽命， 數據由20個模擬生成． 由圖11可以看出， 最小網絡生存周期隨著節點數量增加而增加． 與OCCH和CWGC算法相比， 本文算法的最小網絡生存周期優于所對比的方法． 當節點比較多時， 本文算法的可擴展性優于OCCH和CWGC算法． 這是因為算法的性能與網絡拓撲結構有關， 增加節點數量會削弱這種影響．

圖11 節點數不同時各算法的最小網絡生存周期

5 結論

為了延長網絡壽命和降低WSN的平均能耗， 本文提出一種高效的無線傳感器網絡目標覆蓋算法． 該算法通過生成不相交的覆蓋集來延長覆蓋的持續時間， 通過提供多個覆蓋集來使傳感器消耗的能量相當， 達到最大化使用壽命的目的， 并跟蹤傳感器正在監控的目標數量及剩余能量尋找從信源到信宿的最小能量路徑為感測數據提供擴展的連接性． 實驗表明， 在節點數為200時， 本文方法的覆蓋時間為63 s， OCCH算法為60 s， CWGC算法為80 s； 本文方法的平均能耗為3 J， OCCH算法為5.5 J， CWGC算法為6.3 J； 本文方法的網絡生存周期為22 h， OCCH算法為10 h， CWGC算法為4 h． 由此， 說明本文方法性能優于OCCH算法和CWGC算法． 另外， 不同面積和不同目標的實驗結果也表明了本文方法的優越性． 未來的工作是評估分布式環境中的目標覆蓋， 并將其用于其他類型的覆蓋問題， 例如區域覆蓋或k-覆蓋問題．