基于目標(biāo)覆蓋感知的WSNs節(jié)點(diǎn)部署算法

符 春

(長(zhǎng)沙民政職業(yè)技術(shù)學(xué)院，湖南 長(zhǎng)沙 410004)

0 引 言

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)[1]已在多個(gè)領(lǐng)域內(nèi)廣泛使用，如環(huán)境監(jiān)測(cè)、戰(zhàn)場(chǎng)勘察、物聯(lián)網(wǎng)。WSNs是由微型的、對(duì)周圍環(huán)境具有感測(cè)能力的傳感節(jié)點(diǎn)組成。這些傳感節(jié)點(diǎn)先感測(cè)數(shù)據(jù)，然后將數(shù)據(jù)傳輸至信宿(Sink)。傳統(tǒng)的WSNs網(wǎng)絡(luò)采用靜態(tài)的Sink。然而，若采用的靜態(tài)Sink方式，則位于Sink鄰近的節(jié)點(diǎn)需要不斷的轉(zhuǎn)發(fā)數(shù)據(jù)，這就加劇它們的能量消耗[2]。一旦能量消耗殆盡，就形成網(wǎng)絡(luò)分裂。為此，研究人員引用動(dòng)態(tài)Sink方式，即每隔一段時(shí)期，Sink就移動(dòng)它的位置[3]。

此外，目標(biāo)覆蓋和網(wǎng)絡(luò)連通是WSNs的兩個(gè)研究熱點(diǎn)。前者保證目標(biāo)區(qū)域被傳感節(jié)點(diǎn)實(shí)時(shí)地監(jiān)控，而后者提供通信質(zhì)量，即保證數(shù)據(jù)傳輸?shù)挠行浴ａ槍?duì)這兩個(gè)熱點(diǎn)，研究人員提出不同策略。這些策略可分為兩類：1)優(yōu)化部署傳感節(jié)點(diǎn)位置；2)優(yōu)化Sink位置。

目前多數(shù)算法是通過優(yōu)化部署傳感節(jié)點(diǎn)位置，提高目標(biāo)覆蓋率和連通率。在文獻(xiàn)[4]中，作者將優(yōu)化部署傳感節(jié)點(diǎn)問題轉(zhuǎn)化成Steiner 最小樹問題，再利用Heuristic算法求解。此外，文獻(xiàn)[5]將節(jié)點(diǎn)部署問題分解成多個(gè)子問題，再“分而治之”。然而，這些算法只是針對(duì)靜態(tài)Sink網(wǎng)絡(luò)。

目前，針對(duì)動(dòng)態(tài)Sink的WSNs，優(yōu)化部署節(jié)點(diǎn)問題的研究較少。為此，本文分析了面向動(dòng)態(tài)Sink的WSNs，節(jié)點(diǎn)部署問題，即如何以最少的節(jié)點(diǎn)數(shù)實(shí)現(xiàn)最大的網(wǎng)絡(luò)覆蓋和連通率。

具體而言，將節(jié)點(diǎn)部署問題化成兩個(gè)子問題：目標(biāo)覆蓋(Target Covering, TC)問題和網(wǎng)絡(luò)連通(Network Connectivity, NC)問題。TC問題是指如何以最少的傳感節(jié)點(diǎn)數(shù)覆蓋所有目標(biāo)；而NC問題是指如何以最少的轉(zhuǎn)發(fā)節(jié)點(diǎn)，連通動(dòng)態(tài)的Sink。對(duì)于TC問題，采用k-means簇算法求解，即先將多個(gè)目標(biāo)劃分成簇，然后在每個(gè)簇內(nèi)，部署傳感節(jié)點(diǎn)實(shí)現(xiàn)簇覆蓋；對(duì)于NC問題，提出貪婪算法求解。實(shí)驗(yàn)數(shù)據(jù)表明，提出的基于目標(biāo)覆蓋感知的節(jié)點(diǎn)部署算法(Target Coverage Aware-based Node Placement, TCA-NP)算法有效地解決節(jié)點(diǎn)部署問題和連通問題。

1 TCA-NP算法

1.1 概述

假定所有的傳感節(jié)點(diǎn)具有相同的感測(cè)半徑Rs和通信半徑Rc，且Rs≠Rc。并且感測(cè)區(qū)域和通信區(qū)域?yàn)閳A形結(jié)構(gòu)，如圖1所示。圖1假定Rs>Rc。

圖1 傳感節(jié)點(diǎn)感測(cè)和通信范圍模型

TCA-NP算法主要解決TC問題和NC問題，并且用k-means算法解決TC問題，然后用貪婪算法求解NC問題。

本文是從兩個(gè)角度分析節(jié)點(diǎn)部署問題，一個(gè)是從覆蓋目標(biāo)角度，優(yōu)化部署節(jié)點(diǎn)，使這些節(jié)點(diǎn)能有效地覆蓋目標(biāo)；另一個(gè)是從連通Sink角度，部署中繼節(jié)點(diǎn)，使網(wǎng)絡(luò)連通。這個(gè)兩個(gè)問題的本質(zhì)均是部署傳感節(jié)點(diǎn)。解決TC問題有利于NC問題解決。換而言之，解決TC問題是優(yōu)化NC問題的基礎(chǔ)。因此，本文先解決TC問題。

1.2 基于k-means的求解TC問題

本小節(jié)，分析如何用最少的傳感節(jié)點(diǎn)數(shù)覆蓋所有目標(biāo)。將目標(biāo)看成一點(diǎn)。如果目標(biāo)間的距離不超過2倍的感測(cè)半徑Rs時(shí)，可用同一個(gè)傳感節(jié)點(diǎn)覆蓋這些目標(biāo)。

為此，將目標(biāo)劃分多個(gè)簇，致使鄰近的目標(biāo)構(gòu)成一個(gè)簇。據(jù)此，引用k-means簇算法[6]。k-means簇算法目的就是使簇內(nèi)的節(jié)點(diǎn)間的平方距離差最小，而使簇間的節(jié)點(diǎn)間平方距離差最大。

(1)

如果d小于Rs，則可以中心位置Oi上部署一個(gè)傳感節(jié)點(diǎn)sr，僅通過這個(gè)傳感節(jié)點(diǎn)，就可以覆蓋Li內(nèi)目標(biāo)。因此，將sr置于Oi。

(2)

(3)

此外，引用傳感節(jié)點(diǎn)集Si，其表示在Li內(nèi)部署的傳感節(jié)點(diǎn)。確定了傳感節(jié)點(diǎn)sr位置后，就將sr加入Si。

一旦部署了傳感節(jié)點(diǎn)后(假定為節(jié)點(diǎn)sr)，就計(jì)算簇Li內(nèi)所有的目標(biāo)節(jié)點(diǎn)與節(jié)點(diǎn)sr的距離。如果d(sr,Tj)小于Rs，則將它從簇Li內(nèi)刪除。刪除后，簇內(nèi)只剩下節(jié)點(diǎn)sr不能覆蓋的目標(biāo)[8]。然后，再重新計(jì)算中心位置，繼續(xù)部署傳感節(jié)點(diǎn)，直到簇Li內(nèi)無目標(biāo)。最終，就形成部署傳感節(jié)點(diǎn)集Si。整個(gè)算法的偽代碼如算法1所示。

圖2顯示了部署傳感節(jié)點(diǎn)過程。在圖2(a)中，先計(jì)算簇內(nèi)中心位置，然后再尋找離中心位置最遠(yuǎn)的目標(biāo)節(jié)點(diǎn)；在圖2(b)中，部署一個(gè)傳感節(jié)點(diǎn)，然后，再將此傳感節(jié)點(diǎn)所覆蓋的目標(biāo)從簇內(nèi)刪除。最后，再重復(fù)上述過程。

圖2 部署傳感節(jié)點(diǎn)的過程

1.3 基于貪婪算法的NC問題

假定在數(shù)據(jù)收集次數(shù)n

令G=(V,E)，其中V表示頂點(diǎn)集，E為邊集。將圖G轉(zhuǎn)化為子圖，且每個(gè)子圖表示一個(gè)連通圖，并引用R={C1,…,Cm}表示這些連通圖的元素。本小節(jié)的目的就是通過添加新的中繼節(jié)點(diǎn)使得所有連通元素均能在第j次數(shù)據(jù)收集時(shí)，連通至Sink。

令C(1)表示在第j次數(shù)據(jù)收集時(shí)還未連通至Sink的元素集合，而C(2)表示在第j次數(shù)據(jù)收集時(shí)，由所有信宿和連通節(jié)點(diǎn)所構(gòu)成的集合。顯然，在初始狀態(tài)時(shí)，C(1)初始為R，而C(2)初始化為所有信宿。通過執(zhí)行Greedy算法，直到C(1)為空。

(1)尋找兩個(gè)元素間的最小距離，一個(gè)元素屬于C(1)，另一個(gè)元素屬于C(2)。假定X、Y為這兩個(gè)元素，且X∈C(1)、Y∈C(2)。然后，將中繼節(jié)點(diǎn)部署于連通X與Y的連線上；

(2)將X內(nèi)的所有元素移動(dòng)C(2)，再將X從C(1)內(nèi)刪除。

圖3 部署中繼節(jié)點(diǎn)示例

圖3顯示了部署中繼節(jié)點(diǎn)的示例。圖3(a)顯示了C(1)內(nèi)幾個(gè)連通的元素集，現(xiàn)從C1和C(2)中尋找X、Y，使它們連線長(zhǎng)度最短。然后，在它們的連線上部署中繼節(jié)點(diǎn)，使這兩個(gè)元素集連通，如圖3(b)所示。最后，再將C(1)內(nèi)所有節(jié)點(diǎn)移到C(2)中，這表明C(1)內(nèi)所有節(jié)點(diǎn)已連通到了Sink，如圖3(c)所示。

2 性能仿真及分析

2.1 仿真參數(shù)

利用MATLAB軟件建立仿真平臺(tái)。考慮2000 m×2000 m的網(wǎng)絡(luò)拓?fù)?，所有傳感?jié)點(diǎn)具有相同的感測(cè)半徑，且為15 m，而通信半徑為30 m。為了更好地體現(xiàn)TCA-NP算法的性能，進(jìn)行三個(gè)實(shí)驗(yàn)。同時(shí)選擇文獻(xiàn)[10]的SMT-MSP算法和文獻(xiàn)[11]的SGA算法進(jìn)行比較，主要分析所需要的傳感節(jié)點(diǎn)數(shù)(Total Number of Required Nodes, TNRN)、運(yùn)行時(shí)間。每次實(shí)驗(yàn)獨(dú)立重復(fù)30次，取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù)。

2.2 實(shí)驗(yàn)一

本次實(shí)驗(yàn)分析Sink數(shù)對(duì)所需的傳感節(jié)點(diǎn)數(shù)TNRN的影響，其中目標(biāo)數(shù)為200，數(shù)據(jù)收集次數(shù)k=5，Sink數(shù)從10至60變化。實(shí)驗(yàn)數(shù)據(jù)如圖4所示。

圖4 TNRN隨Sink數(shù)的變化曲線

從圖4可知，提出的TCA-NP算法的TNRN最少，并且隨著Sink數(shù)的增加而下降。原因在于：當(dāng)信宿數(shù)的增加，信宿與傳感節(jié)點(diǎn)間的距離就減少，因此，所需的中繼節(jié)點(diǎn)數(shù)得到下降。

然而，與TCA-NP算法相比，SMT-MSP算法的TNRN并沒有數(shù)隨Sink數(shù)增加而下降。這主要有兩點(diǎn)原因：一方面，Sink數(shù)的增加降低Sink與傳感節(jié)點(diǎn)間的距離，降低了部署中繼節(jié)點(diǎn)數(shù)；另一方面，在SMT-MSP算法中，在每次數(shù)據(jù)收集時(shí)，必須保證所有傳感節(jié)點(diǎn)與Sink連通，因此，Sink數(shù)數(shù)的增加添加對(duì)中繼節(jié)點(diǎn)的需求。

2.3 實(shí)驗(yàn)二

本次實(shí)驗(yàn)分析數(shù)據(jù)收集次數(shù)對(duì)TNRN的影響，其中目標(biāo)數(shù)為200，Sink數(shù)為10，數(shù)據(jù)收集次數(shù)從5變化至25，實(shí)驗(yàn)數(shù)據(jù)如圖5所示。

圖5 TNRN數(shù)隨數(shù)據(jù)收集次數(shù)的變化曲線

從圖5可知，當(dāng)SMT-MSP算法的TNRN隨數(shù)據(jù)收集次數(shù)的增加上升得最快，而本文提出的TCA-NP算法上升最慢，幾乎不變，原因在于：在SMT-MSP算法中，要求部署中繼節(jié)點(diǎn)，進(jìn)而保證在每次數(shù)據(jù)收集時(shí)是連通的。而SGA算法隨數(shù)據(jù)收集次數(shù)變化很慢，但它所需的TNRN數(shù)遠(yuǎn)高于TCA-NP算法。

2.4 實(shí)驗(yàn)三

本次實(shí)驗(yàn)分析目標(biāo)數(shù)對(duì)TNRN的影響，其中Sink數(shù)為10，數(shù)據(jù)收集次數(shù)為5，其中目標(biāo)數(shù)從10至250變化。實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

圖6 目標(biāo)數(shù)對(duì)TNRN的影響

從圖6可知，TNRNs數(shù)隨目標(biāo)數(shù)的增加而上升。原因在于：目標(biāo)數(shù)越多，就需要更多的傳感節(jié)點(diǎn)覆蓋目標(biāo)。因此，需要部署更多的中繼節(jié)點(diǎn)才能連通Sink。此外，從圖6可知，TCA-NP算法的TNRN最低，但隨著目標(biāo)數(shù)的增加，TCA-NP算法性能與SGA算法逐漸相近。

2.5 實(shí)驗(yàn)四

本次實(shí)驗(yàn)分析算法的執(zhí)行時(shí)間。執(zhí)行時(shí)間越長(zhǎng)，算法越復(fù)雜。執(zhí)行算法的PC參數(shù)為：Intel Core i7-5500U、RAM 8GB。此外，Sink數(shù)為10，數(shù)據(jù)收集次數(shù)為5，其中目標(biāo)數(shù)從10至250變化，實(shí)驗(yàn)數(shù)據(jù)如圖7所示。

圖7 執(zhí)行時(shí)間隨目標(biāo)數(shù)的影響

從圖7可知，執(zhí)行時(shí)間隨目標(biāo)數(shù)的增加而上升。原因很容易理解：目標(biāo)數(shù)越多，需要部署更多節(jié)點(diǎn)才能覆蓋目標(biāo)，這必然增加執(zhí)行時(shí)間。此外，與SMT-MSP算法、SGA算法相比，提出的TCA-NP算法的執(zhí)行時(shí)間最多，且隨著目標(biāo)數(shù)呈增加趨勢(shì)。這也說明，TCA-NP算法是以增加復(fù)雜度換取低的TNRN數(shù)，但是增加的復(fù)雜度并不高，例如，當(dāng)目標(biāo)數(shù)為250時(shí)，TCA-NP算法的執(zhí)行時(shí)間比SGA算法增加了不到50 ms。

3 結(jié) 語

針對(duì)無線傳感網(wǎng)絡(luò)的目標(biāo)覆蓋和網(wǎng)絡(luò)連通問題，展開分析，并提出基于目標(biāo)覆蓋感知的節(jié)點(diǎn)部署算法TCA-NP。TCA-NP算法分別引用k-means算法、Greedy算法求解目標(biāo)覆蓋問題、網(wǎng)絡(luò)連通問題，進(jìn)而優(yōu)化節(jié)點(diǎn)部署，實(shí)現(xiàn)對(duì)目標(biāo)的全覆蓋。實(shí)驗(yàn)數(shù)據(jù)表明，提出的TCA-NP在覆蓋目標(biāo)時(shí)，所需的傳感節(jié)點(diǎn)數(shù)最少。