吳煜瑋，黎 聰

(電子科技大學(xué) 電子科學(xué)技術(shù)研究院，四川 成都611731)

0 引 言

覆蓋質(zhì)量是無線傳感器網(wǎng)絡(luò)(WSNs)最為關(guān)心的重要問題之一。區(qū)域覆蓋的目標(biāo)就是監(jiān)測(cè)區(qū)域中每個(gè)位置都至少被一個(gè)傳感器所覆蓋到，Zhou Z H 等人［1］在該領(lǐng)域提出了著名的k-covered 問題。區(qū)域內(nèi)任一點(diǎn)p 被k 個(gè)傳感器覆蓋，則該區(qū)域是k-covered。文獻(xiàn)［2］提出當(dāng)Rc=2Rs時(shí)(其中，Rc為通信半徑，Rs為感知半徑)，k-covered 可轉(zhuǎn)換為k-connected，并證明了一個(gè)凸區(qū)域是k-covered 只需要保證它所有交點(diǎn)都是k-covered。文獻(xiàn)［3］研究了在保證網(wǎng)絡(luò)k-covered 的前提下，節(jié)點(diǎn)數(shù)、激活概率、感知半徑與覆蓋度之間滿足的關(guān)系。對(duì)于估算最初部署時(shí)需要激活的傳感器數(shù)量有指導(dǎo)性的意義。

Slijepeevic S 等人［4］提出將節(jié)點(diǎn)化為互不相交的集合，每個(gè)集合都能獨(dú)立滿足對(duì)目標(biāo)區(qū)域的覆蓋質(zhì)量。集合劃分的越多，網(wǎng)絡(luò)生存時(shí)間越長(zhǎng)。由于尋找互不相交的集合是NP 完全問題，文獻(xiàn)［5］對(duì)此進(jìn)行了改進(jìn)，允許一個(gè)節(jié)點(diǎn)同時(shí)劃分到多個(gè)集合中。在此前提下，研究了網(wǎng)絡(luò)生存時(shí)間和節(jié)點(diǎn)調(diào)度問題，但不能保證對(duì)區(qū)域的完全覆蓋。文獻(xiàn)［6］用一種適合的算法判定監(jiān)視區(qū)域是否被鄰居節(jié)點(diǎn)覆蓋，若能取代，則將該節(jié)點(diǎn)轉(zhuǎn)入休眠狀態(tài)。文獻(xiàn)［7］通過向周圍區(qū)域發(fā)送探測(cè)半徑為r 的廣播信息，若能收到回復(fù)信息，則將該節(jié)點(diǎn)轉(zhuǎn)入休眠狀態(tài)。這些研究都會(huì)涉及到計(jì)算傳感器感知區(qū)域的重合情況，計(jì)算開銷很大。

為了減小計(jì)算開銷，本文提出一種提高區(qū)域覆蓋的新方法，通過分析和計(jì)算傳感器分布的幾何特征，每次迭代激活最佳位置節(jié)點(diǎn)來達(dá)到有效覆蓋的目的。

1 模型設(shè)計(jì)與問題描述

1.1 傳感器模型

假設(shè)每個(gè)傳感器都精確知道自己所處在的位置坐標(biāo)，并且每個(gè)傳感器都可以工作在激活模式(active)和休眠模式(sleep)，只要節(jié)點(diǎn)被激活就一直工作到能量耗盡為止。工作在激活模式下的節(jié)點(diǎn)集用Sa 表示，休眠模式下用Ss表示。本文所用均為靜態(tài)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的感知半徑Rs 都相同。每個(gè)節(jié)點(diǎn)的通信半徑Rc也相同，且滿足Rc=2Rs。節(jié)點(diǎn)的感知區(qū)域是以該節(jié)點(diǎn)為圓心，半徑為Rs的圓域。節(jié)點(diǎn)的通信區(qū)域是以該節(jié)點(diǎn)所處位置為圓心，半徑為Rc的圓域。所用節(jié)點(diǎn)的感知概率模型為布爾型，如圖1 所示，實(shí)心區(qū)域中的任意位置都能被節(jié)點(diǎn)si感知。

圖1 傳感器模型Fig 1 Sensor model

1.2 問題描述

假設(shè)目標(biāo)監(jiān)視區(qū)域?yàn)橐黄矫婢匦螀^(qū)域A，將足夠多的傳感器均勻隨機(jī)部署在區(qū)域A 中并假定同一位置僅有一只傳感器存在。假設(shè)區(qū)域A 的范圍遠(yuǎn)遠(yuǎn)大于傳感器的尺寸，故可以將傳感器模型簡(jiǎn)化為一個(gè)點(diǎn)。節(jié)點(diǎn)所處的位置代表傳感器部署在區(qū)域中的位置。

當(dāng)前時(shí)刻網(wǎng)絡(luò)的覆蓋情況由此時(shí)所處在激活模式的節(jié)點(diǎn)構(gòu)成的監(jiān)視范圍和監(jiān)視范圍中的漏洞共同決定。監(jiān)視范圍是當(dāng)前激活節(jié)點(diǎn)可以覆蓋的最大范圍。如圖2 所示，黑色和灰色圓域各自代表激活節(jié)點(diǎn)和休眠節(jié)點(diǎn)的感知范圍，黑色虛線代表著當(dāng)前時(shí)刻網(wǎng)絡(luò)的監(jiān)視范圍。

圖2 監(jiān)視范圍與凸包Fig 2 Monitoring range and convex hull

顯然，在監(jiān)視范圍以外的目標(biāo)監(jiān)視區(qū)域還存在的監(jiān)視空白，并且虛線內(nèi)部存在著大量的覆蓋漏洞。當(dāng)前時(shí)刻的覆蓋情況是由監(jiān)視范圍和漏洞面積共同決定的，其關(guān)系如下

其中，Scoverage表示網(wǎng)絡(luò)的覆蓋面積，即已激活節(jié)點(diǎn)覆蓋范圍的并集。SMonitoregion表示監(jiān)視范圍面積，SHole為監(jiān)視范圍中存在的覆蓋漏洞面積。因此，可以從擴(kuò)大SMonitoregion和減小SHole兩方面著手考慮達(dá)到提高Scoverage的目的。

如果將處在激活狀態(tài)傳感器所處位置抽象成為二維平面上的點(diǎn)集，凸包就是將最外層的傳感器連接起來構(gòu)成的凸多邊形，它必須包含點(diǎn)集中所有已激活傳感器。如圖2所示，黑色的實(shí)線圈就是該無WSNs 的凸包。

在圖2 中，當(dāng)前時(shí)刻激活節(jié)點(diǎn)所構(gòu)成的監(jiān)視范圍是黑色虛線的不規(guī)則多邊形內(nèi)部，而黑色實(shí)線是當(dāng)前時(shí)刻工作在激活模式節(jié)點(diǎn)的凸包包絡(luò)?？梢钥闯龊谏珜?shí)線也同樣能夠近似表征當(dāng)前時(shí)刻網(wǎng)絡(luò)的覆蓋情況。特別是當(dāng)目標(biāo)監(jiān)視區(qū)域面積相比傳感器的感知范圍足夠小時(shí)，凸包面積與監(jiān)視范圍相差無幾

其中，ρ=Aarca/Carea為區(qū)域A 的面積與傳感器感知范圍Carea的比值，SConvexHull為凸包面積，并且隨著比值ρ 的不斷增大，凸包的面積將趨近于真正的監(jiān)視范圍。因此，可以用凸包來代替監(jiān)視范圍，式(1)修改如下

這樣提高覆蓋面積SCoverage可以從增大凸包面積SConvexHull和減小覆蓋漏洞SHole兩方面著手。一方面當(dāng)凸包面積SConvexHull一定時(shí)，減小凸包內(nèi)存在的覆蓋漏洞SHole可以提高覆蓋面積SCoverage;另一方面，當(dāng)凸包內(nèi)覆蓋漏洞SHole不存在或者說可以忽略時(shí)，增大凸包面積也能提高覆蓋面積SCoverage。為了達(dá)到盡可能少激活傳感器并且快速增大覆蓋面積的目的，本算法采取在已存在網(wǎng)絡(luò)基礎(chǔ)上每一次僅激活一只傳感器，最有效地利用該傳感器增大凸包面積SConvexHull或者填補(bǔ)覆蓋漏洞SHole。

假設(shè)當(dāng)前狀態(tài)下處于激活狀態(tài)Sa 集合中節(jié)點(diǎn)總數(shù)共有n 個(gè)，處于休眠狀態(tài)Ss 集合節(jié)點(diǎn)個(gè)數(shù)為m。當(dāng)前網(wǎng)絡(luò)的覆蓋面積可表示為

其中，Ci為第i 號(hào)節(jié)點(diǎn)的感知范圍，i∈Sa。SCoverage就是所有處于激活狀態(tài)節(jié)點(diǎn)感知范圍的并集。激活一個(gè)來自Ss節(jié)點(diǎn)集合后網(wǎng)絡(luò)的覆蓋面積用S'Coverage表示，目標(biāo)是使得S'Coverage最大

其中，Cj為第j 號(hào)節(jié)點(diǎn)的感知范圍，j∈Ss。

要使得S'Coverage最大，只有通過比較來自Ss 集合不同節(jié)點(diǎn)產(chǎn)生的效益，選擇激活產(chǎn)生效益最大對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)來達(dá)到在下一個(gè)狀態(tài)時(shí)最好的覆蓋水平。故問題轉(zhuǎn)化為如何選擇激活一個(gè)Ss 集合節(jié)點(diǎn)，使得覆蓋率得到最大提升。

2 解決方案

為了尋找出最佳待激活節(jié)點(diǎn)，本文提出的解決方案如圖3 所示。

2.1 求出Sa 集合凸包和對(duì)Ss 集合節(jié)點(diǎn)分類

求出由當(dāng)前Sa 集合構(gòu)成的最大包絡(luò)外包絡(luò)，簡(jiǎn)化為點(diǎn)集Sa 構(gòu)成的凸包面積。如圖2，區(qū)域中，黑色實(shí)線圍成的封閉凸多邊形就是當(dāng)前狀態(tài)下Sa 點(diǎn)集的凸包。

圖3 算法流程圖Fig 3 Flow chart of algorithm

這樣Ss 集合可劃分為兩類。如圖2 所示，處于黑色凸包包絡(luò)以外的休眠節(jié)點(diǎn)sleep_out 集合，處于黑色凸包包絡(luò)以內(nèi)的休眠節(jié)點(diǎn)sleep_in 集合。選擇激活sleep_out 集合中節(jié)點(diǎn)可以增大凸包面積SConvexHull，選擇激活sleep_in 集合中節(jié)點(diǎn)可以彌補(bǔ)覆蓋漏洞。

2.2 增大凸包面積/減小漏洞面積

考慮激活盡可能少的傳感器數(shù)量完成相同的任務(wù)，故采取每一輪循環(huán)只激活一只傳感器最大化的提升覆蓋面積。最大程度增大凸包面積或者最大程度彌補(bǔ)覆蓋漏洞都是最大化提升覆蓋面積的有效手段。

2.2.1 增大凸包面積

如圖4 所示，區(qū)域H1是Sa 集合的凸包，凸包外部有兩個(gè)處于休眠模式的節(jié)點(diǎn)A 與節(jié)點(diǎn)B，只有處于包絡(luò)外圍的點(diǎn)才有機(jī)會(huì)改變凸包的形狀。假如激活A(yù) 節(jié)點(diǎn)相應(yīng)增大的面積為H1區(qū)域，激活節(jié)點(diǎn)B 后增大的面積為H2區(qū)域。通過計(jì)算可以得出H1面積大于H2區(qū)域面積。所有在當(dāng)前狀態(tài)下把節(jié)點(diǎn)A 選作增大凸包候選激活節(jié)點(diǎn)，稱作T2。

圖4 增大凸包面積Fig 4 Increasing area of convex hull

2.2.2 減小漏洞面積

在Sa 集合的凸包內(nèi)，并不能保證凸包內(nèi)部區(qū)域?qū)崿F(xiàn)完整覆蓋，故需要增加節(jié)點(diǎn)填補(bǔ)凸包內(nèi)部存在的漏洞。

定義 給定平面上一點(diǎn)集P，要求以不在同一直線上的三個(gè)點(diǎn)作一個(gè)圓，要求這樣的圓域內(nèi)部不包含P 集合中的其他點(diǎn)并且圓心位于所限定區(qū)域的內(nèi)部，這樣的圓稱作空?qǐng)A。

定理 當(dāng)空?qǐng)A半徑Rh＞Rs時(shí)，空?qǐng)A中一定存在覆蓋漏洞。

證明 從定義可知，由激活節(jié)點(diǎn)構(gòu)成的空?qǐng)A內(nèi)部不包含其他處在激活模式節(jié)點(diǎn)，顯然，當(dāng)空?qǐng)A半徑Rh＞Rs時(shí)，空?qǐng)A圓心點(diǎn)一定未能被覆蓋到，故這樣的空?qǐng)A中一定會(huì)存在覆蓋漏洞。

空?qǐng)A的半徑越大，意味著節(jié)點(diǎn)與節(jié)點(diǎn)間的距離越大，覆蓋漏洞面積也遠(yuǎn)。因此，選擇激活最大空?qǐng)A內(nèi)的休眠節(jié)點(diǎn)達(dá)到最有效地減小覆蓋漏洞的目的。將最靠近最大空?qǐng)A圓心的休眠節(jié)點(diǎn)激活能最大程度上地消除最大空?qǐng)A內(nèi)部的覆蓋漏洞，該節(jié)點(diǎn)作為減小覆蓋漏洞候選激活節(jié)點(diǎn)，稱作T2。

2.3 選擇最終激活的節(jié)點(diǎn)

上述過程已經(jīng)找出兩個(gè)候選激活節(jié)點(diǎn)。分別計(jì)算假設(shè)激活它們后所對(duì)應(yīng)的凸包增大面積和最大空?qǐng)A面積

其中，Hull_add 為假如激活T1節(jié)點(diǎn)后凸包增大面積，Empty_circle 為最大空?qǐng)A面積，optimum 為最終激活節(jié)點(diǎn)。

如圖5 所示，凸包增大面積是A1區(qū)域，最大空?qǐng)A面積是A2區(qū)域。當(dāng)A1區(qū)域面積大于A2區(qū)域面積時(shí)，將T1節(jié)點(diǎn)作為最終激活節(jié)點(diǎn);否則，將T2作為最終激活節(jié)點(diǎn)。

圖5 最終激活節(jié)點(diǎn)的選擇Fig 5 Choice of final activated node

2.4 重新計(jì)算區(qū)域覆蓋率

將所激活的節(jié)點(diǎn)從Ss 集合中刪除，同時(shí)添加到Sa 集合中，再進(jìn)行判定是否達(dá)到覆蓋要求。若仍小于覆蓋度閾值，則按照此方法繼續(xù)激活Ss 集合節(jié)點(diǎn)，直到該區(qū)域覆蓋度達(dá)到閾值要求。

3 仿真與評(píng)估

本文在Matlab 上對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)。在平面上100 m×100 m 的矩形區(qū)域中一共投放了400 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的感知半徑Rs為10 m，通信半徑Rc為20 m。在最開始隨機(jī)激活50 個(gè)節(jié)點(diǎn)使其保持在工作狀態(tài)，而其余節(jié)點(diǎn)處于休眠狀態(tài)。實(shí)驗(yàn)?zāi)繕?biāo)是使得該區(qū)域99%的面積得到覆蓋。

仿真結(jié)果如圖6 為初始節(jié)點(diǎn)的覆蓋情況，圖7(a)為使用本文提出的算法后的覆蓋情況，圖7(b)為使用隨機(jī)激活算法后的覆蓋情況。圖7(a)總共使用了86 個(gè)節(jié)點(diǎn)達(dá)到目標(biāo)覆蓋，而圖7(b)卻花費(fèi)了高達(dá)147 個(gè)節(jié)點(diǎn)才實(shí)現(xiàn)同等的覆蓋水平。

圖6 初始分布的節(jié)點(diǎn)覆蓋情況Fig 6 Coverage of initial deployed nodes

圖7 兩種算法覆蓋情況Fig7 Coverage of two kinds of algorithms

新增節(jié)點(diǎn)數(shù)和監(jiān)視區(qū)域的覆蓋率之間的關(guān)系如圖8 所示。按照本文的算法，僅僅新激活了10 個(gè)節(jié)點(diǎn)，就將覆蓋度從最初部署時(shí)的77%增加到了90%，而隨機(jī)激活算法新激活了25 個(gè)才達(dá)到同等覆蓋水平。顯然，使用本文的算法能更快速有效地彌補(bǔ)監(jiān)視區(qū)域所存在的漏洞，從而迅速提高覆蓋水平。為了不失一般性，本文模擬了30 次并記錄下統(tǒng)計(jì)結(jié)果，利用本文的算法，達(dá)到95%的覆蓋度平均需要新增18.5 個(gè)節(jié)點(diǎn)，而隨機(jī)調(diào)度算法則需要付出61.5 個(gè)新增節(jié)點(diǎn)。為了探究在相同目標(biāo)覆蓋率下不同的感知半徑和新增節(jié)點(diǎn)數(shù)之間的關(guān)系，進(jìn)行了30 次仿真實(shí)驗(yàn)，結(jié)果顯示:本文提出的算法在不同的感知半徑下都能很好地節(jié)約傳感器資源，感知半徑越小，節(jié)省的節(jié)點(diǎn)資源越多，統(tǒng)計(jì)結(jié)果如圖9。

圖8 覆蓋率與新增節(jié)點(diǎn)數(shù)Fig 8 Coverage ratio and added nodes

4 結(jié) 論

圖9 半徑與新增節(jié)點(diǎn)數(shù)的關(guān)系Fig 9 Relationship between radius and added node numbers

本文針對(duì)已存在網(wǎng)絡(luò)不能滿足覆蓋指標(biāo)的情況，提出了一種根據(jù)網(wǎng)絡(luò)的幾何特征不斷選擇最佳激活節(jié)點(diǎn)，最終達(dá)到覆蓋要求的方法。本文提出的算法避免了傳統(tǒng)調(diào)度算法需要建立在計(jì)算得到各節(jié)點(diǎn)感知模型重疊情況的弊端，大大降低了計(jì)算開銷。仿真結(jié)果證實(shí)了本文作者提出的算法能迅速增大覆蓋率并且很大程度上節(jié)省了節(jié)點(diǎn)資源。在今后的工作中，將引入可移動(dòng)無線傳感器和分布式算法對(duì)該問題進(jìn)行優(yōu)化求解。

［1］ Zhou Z H，Samir D，Gupta H.Connected K－coverage problem in sensor networks［C］∥Proceedings of IEEE the Thirteenth International Conference on Computer Communications and Networks，Chicago，IL，2004.

［2］ Wang X R，Xing G L，Zhang Y F.Integrated coverage and connectivity configuration in wireless sensor networks［C］∥Proceedings of the 1st International Conference on Embedded Networked Sensor Systems，New York，NY，USA:ACM，2003.

［3］ Kumar S，Lai T H，Balogh J.On K－coverage in a mostly sleeping sensor network［C］∥Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，New York，NY，USA:ACM，2004.

［4］ Slijepcevic S，Potkonjak M.Power efficient organization of wireless sensor networks［C］∥IEEE International Conference on Communications(ICC)，Washington:IEEE Computer Society，2001.

［5］ Berman P，Calinescu G，Shah C，et al.Power efficient monitoring management in sensor networks［C］∥IEEE Wireless Communications and Networking Conference(WCNC)，Atlanta:IEEE Computer Society，2004:21－25.

［6］ Tian D，Georganas N D.A coverage－preserving node scheduling scheme for large wireless sensor networks［C］∥Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications，New York，NY，USA:ACM，2002.

［7］ Ye F，Zhong G，Lu S，et al.Energy efficient robust sensing coverage in large sensor networks［R］.Los Angeles:UCLA Technical Report，2002.