無線傳感器網(wǎng)絡(luò)覆蓋控制算法分析

張永棠　羅先錄　周富肯

摘 要：網(wǎng)絡(luò)覆蓋算法直接影響無線傳感器網(wǎng)絡(luò)“感知”服務(wù)質(zhì)量。文章根據(jù)傳感器網(wǎng)絡(luò)覆蓋控制理論，對WSN的覆蓋問題進(jìn)行了歸納與總結(jié)，建立了WSN研究框架，從生存時間、部署策略、通信協(xié)議和組網(wǎng)等問題對無線傳感器網(wǎng)絡(luò)的覆蓋控制策略和算法進(jìn)行詳細(xì)分析。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；算法；網(wǎng)絡(luò)通信；覆蓋控制；信息安全

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

Abstract：Network coverage algorithm for wireless sensor network directly affects the perception quality of service.The according to the sensor network coverage control theory，on the WSN coverage problem were summed up and summarized，establishes the framework for WSN research，from the survival time，deployment strategy，communication protocol and network of wireless sensor network coverage control strategies and algorithms were analyzed in detail.

Keywords：wireless sensor networks；algorithm；network communication；covering control；information security

1 引言（Introduction）

由于無線傳感器網(wǎng)絡(luò)（WSN）節(jié)點(diǎn)具備體積小、成本低廉、可無線通信以及有自組織能力等特點(diǎn)，使得其在環(huán)境惡劣以及無人值守場合具有很高應(yīng)用價值。作為一種新興網(wǎng)絡(luò)，WSN目前仍存在許多亟待解決的問題，例如節(jié)能、部署覆蓋、路由規(guī)劃、定位、自組織和協(xié)同性等[1]。其中覆蓋方法對傳感器網(wǎng)絡(luò)的生存時間、部署策略、通信協(xié)議和組網(wǎng)等問題的解決具有十分重要的影響。

由于傳感器和應(yīng)用場景千變?nèi)f化，實(shí)際應(yīng)用中傳感器網(wǎng)絡(luò)的覆蓋問題需要考慮很多方面。通過網(wǎng)絡(luò)傳感器節(jié)點(diǎn)配置以及路由選擇等手段來優(yōu)化WSN資源分配，改善網(wǎng)絡(luò)的感知、監(jiān)視、傳感和通信等各種服務(wù)[2]。目前，WSN的覆蓋控制策略已經(jīng)有多種，下面對無線傳感器網(wǎng)絡(luò)的覆蓋控制策略和算法進(jìn)行詳細(xì)分析。

2 WSN覆蓋控制算法（WSN overlay control

algorithm）

基于傳感器網(wǎng)絡(luò)覆蓋控制理論和覆蓋控制問題描述，建立了WSN研究框架，如圖1所示。依照該框架，可以發(fā)現(xiàn)現(xiàn)有覆蓋控制策略所研究的問題存在很大差異，例如監(jiān)測目標(biāo)（區(qū)域）、節(jié)點(diǎn)能力（是否可移動）、節(jié)點(diǎn)感知模型和信息協(xié)同處理、實(shí)現(xiàn)方案的約束和先決條件（精確定位、時間同步），導(dǎo)致解決的方案和手段也千差萬別。

2.1 最大流覆蓋

考慮監(jiān)控區(qū)域中有一組位置已知的目標(biāo)點(diǎn)（targets），足夠數(shù)量的傳感器節(jié)點(diǎn)（sensors）隨機(jī)地部署在區(qū)域內(nèi)，節(jié)點(diǎn)將自身所能監(jiān)控的目標(biāo)點(diǎn)信息通過無線方式傳輸至集中處理節(jié)點(diǎn)（central processing node），由集中處理節(jié)點(diǎn)根據(jù)所收集的信息利用最大流的研究方法，對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分組，使組群之間相互獨(dú)立，并能完全監(jiān)控區(qū)域中的目標(biāo)點(diǎn)。在任何時刻都只有一個組群處于工作狀態(tài)，各組群循環(huán)工作并保證在任何時刻都能監(jiān)控到目標(biāo)點(diǎn)，從而達(dá)到資源的合理利用。通過合適算法確定分組的最大個數(shù)，可以更加有效地優(yōu)化網(wǎng)絡(luò)資源，延長WSN的工作時間。

在將問題轉(zhuǎn)換成尋求最大流問題后，提出一個啟發(fā)式的算法MC-MIP來計(jì)算頂點(diǎn)Y2處所能獲得的最大流及節(jié)點(diǎn)分組。如圖2中分組為C1={S1，S3}，C2={S2}。

2.2 最壞/最佳覆蓋

考慮一片隨機(jī)部署有傳感器節(jié)點(diǎn)的區(qū)域，從該區(qū)域的一點(diǎn)到另一點(diǎn)，如何選擇路徑使其被WSN網(wǎng)絡(luò)節(jié)點(diǎn)監(jiān)控到的幾率最小/大，則為最壞/最佳覆蓋問題。

定義：設(shè)一條連接起點(diǎn)和終點(diǎn)的路徑P，則裂縫（Breach）定義為P到任意節(jié)點(diǎn)的歐氏距離的最小值；支持（Support）定義為P到其最近節(jié)點(diǎn)的歐氏距離的最大值。

最壞/最佳覆蓋問題轉(zhuǎn)變?yōu)樵趨^(qū)域中尋找“最大裂縫路徑（Maximal Breach Path）”和“最大支持路徑（Maximal Support Path）”[3]，如圖3所示。采用計(jì)算幾何中的Voronoi圖[4]和Delaunay三角形來完成對最大裂縫路徑和最大支持路徑的構(gòu)建和查找?？梢?，最壞/最佳覆蓋問題解決了實(shí)際應(yīng)用中路徑跟蹤問題。

2.3 集成覆蓋與連接

為了驗(yàn)證WSN覆蓋與連接性的關(guān)系，設(shè)RC為通信距離，RS為傳感距離，證明：（1）對于1-覆蓋的區(qū)域，當(dāng)RC≥2RS時，區(qū)域內(nèi)的節(jié)點(diǎn)完全連接；（2）對于KS-覆蓋的區(qū)域，當(dāng)RC≥2RS時，區(qū)域內(nèi)的節(jié)點(diǎn)為KS-連接。

考慮兩個相鄰節(jié)點(diǎn)存在虛擬的“引力”或“斥力”，在虛擬力的作用下，兩個節(jié)點(diǎn)可以相互靠近或者遠(yuǎn)離。若在監(jiān)控區(qū)域中存在兩個相鄰的節(jié)點(diǎn)Si與Sj，其間距為dij，當(dāng)dij>dth時，其中dth為相鄰節(jié)點(diǎn)的最佳間距，則Si與Sj表現(xiàn)為引力；當(dāng)dij

圖4表明利用VFA算法可以有效地改善由于節(jié)點(diǎn)隨機(jī)分布所帶來的覆蓋不均，滿足各種應(yīng)用場合的覆蓋需求。

2.4 信息覆蓋

將環(huán)境參數(shù)（光強(qiáng)、聲強(qiáng)和溫度等）的變化考慮成場，利用場理論以及概率論研究在隨機(jī)部署、不可移動的大規(guī)模WSN中綜合周邊節(jié)點(diǎn)的采集數(shù)據(jù)的基礎(chǔ)上得出監(jiān)控盲點(diǎn)的環(huán)境信息，是一類信息覆蓋問題。如圖5所示，中間“☆”處沒有任何節(jié)點(diǎn)可以監(jiān)控到，然而可以通過綜合周邊部署的節(jié)點(diǎn)監(jiān)控?cái)?shù)據(jù)，根據(jù)場的分布和概率論得出“☆”處的環(huán)境信息θ。

如圖5所示，“●”為傳感器節(jié)點(diǎn)，設(shè)圖中傳感器對環(huán)境的檢測值分別為Sk，k為節(jié)點(diǎn)編號，節(jié)點(diǎn)k與☆處的距離分別為dk，假設(shè)環(huán)境信息θ隨距離衰減，衰減系數(shù)為α（α>0），則在距離d處環(huán)境信息為θ/d。由于在實(shí)際監(jiān)測中存在噪聲nk，則有

通過周邊節(jié)點(diǎn)的監(jiān)測信息Sk，根據(jù)上式以及概率估計(jì)算法可以得出“☆”處的環(huán)境信息。記不大于預(yù)先設(shè)定值A(chǔ)的概率為Pr（A），若Pr（A）≥ε（0≤ε≤1），則稱“☆”處可以被其周邊的K個節(jié)點(diǎn)信息覆蓋（記為（K，ε）-覆蓋）。

當(dāng)K=1時，即為簡單的圓盤覆蓋；當(dāng)K>1時，信息覆蓋不僅僅是K個圓盤覆蓋的組合。可見，信息覆蓋擴(kuò)大了原先的覆蓋范圍，更好的對監(jiān)測區(qū)域?qū)嵭斜O(jiān)控。

3 結(jié)論（Conclusion）

WSN如何對區(qū)域進(jìn)行監(jiān)控是在WSN進(jìn)入工作階段之前必須考慮的問題，網(wǎng)絡(luò)覆蓋控制作為WSN實(shí)施過程中的一個基本問題，反映了網(wǎng)絡(luò)所能提供的“感知”服務(wù)質(zhì)量[5]。本文根據(jù)近年來的覆蓋控制研究成果，對WSN的覆蓋問題進(jìn)行了歸納與總結(jié)，提出了研究WSN覆蓋問題時所需關(guān)注的各個方面，并詳細(xì)介紹了無線傳感器網(wǎng)絡(luò)算法。WSN的覆蓋控制依然存在許多亟待解決的問題。例如，現(xiàn)有的WSN覆蓋控制策略主要集中在解決簡單傳感模型下的覆蓋控制，對于節(jié)點(diǎn)感知存在方向差異的情況的研究，仍然是一個比較復(fù)雜的難題。

參考文獻(xiàn)（References）

[1] 任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學(xué)報，2006（3）：422-433.

[2] 曹峰，劉麗萍，王智.能量有效的無線移動傳感器網(wǎng)絡(luò)部署[J].信息與控制， 2006（2）：147-153.

[3] 王燕莉，安世全.無線傳感器網(wǎng)絡(luò)的覆蓋問題研究[J].傳感技術(shù)學(xué)報，2005，18（2）：307-312.

[4] 任彥，張思東，張宏科.無線傳感器網(wǎng)絡(luò)三維空間最佳覆蓋路由協(xié)議[J].電子學(xué)報， 2006（2）：306-311.

作者簡介：

張永棠（1981-），男，碩士，副教授，系統(tǒng)分析師.研究領(lǐng)域：光通信與傳感器網(wǎng)絡(luò)應(yīng)用.

羅先錄（1973-），男，碩士，副教授，系統(tǒng)分析師.研究領(lǐng)域：軟件與網(wǎng)絡(luò)安全.

周富肯（1982-），男，碩士，講師.研究領(lǐng)域：網(wǎng)絡(luò)安全.