符 春

(長沙民政職業(yè)技術學院，湖南 長沙 410004)

0 引 言

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

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

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

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

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

1 TCA-NP算法

1.1 概述

假定所有的傳感節(jié)點具有相同的感測半徑Rs和通信半徑Rc，且Rs≠Rc。并且感測區(qū)域和通信區(qū)域為圓形結構，如圖1所示。圖1假定Rs>Rc。

圖1 傳感節(jié)點感測和通信范圍模型

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

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

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

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

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

(1)

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

(2)

(3)

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

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

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

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

1.3 基于貪婪算法的NC問題

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

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

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

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

(2)將X內的所有元素移動C(2)，再將X從C(1)內刪除。

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

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

2 性能仿真及分析

2.1 仿真參數(shù)

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

2.2 實驗一

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

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

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

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

2.3 實驗二

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

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

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

2.4 實驗三

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

圖6 目標數(shù)對TNRN的影響

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

2.5 實驗四

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

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

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

3 結 語

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