基于均衡分簇的無(wú)線傳感器網(wǎng)絡(luò)壓縮數(shù)據(jù)收集

喬建華，張雪英

(1.太原理工大學(xué)信息工程學(xué)院，太原030024; 2.太原科技大學(xué)電子信息工程學(xué)院，太原030024)(*通信作者電子郵箱tyzhangxy@163.com)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)的首要制約因素就是能源問(wèn)題，如何降低能耗是WSN需要重點(diǎn)考慮的問(wèn)題。WSN中大部分能量消耗在通信部分，在發(fā)送和接收狀態(tài)下能耗最大。將壓縮感知(Compressed Sensing，CS)理論應(yīng)用在WSN的數(shù)據(jù)收集中，可以大大減少傳送數(shù)據(jù)量，從而降低能耗，延長(zhǎng)網(wǎng)絡(luò)壽命。

Bajwa等［1］最早將CS理論應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集。文獻(xiàn)［2］闡述了基于CS的WSN數(shù)據(jù)采集的實(shí)現(xiàn)過(guò)程，指出CS具有普適的采樣和分散的編碼的特征，并給出了從網(wǎng)絡(luò)節(jié)點(diǎn)到融合中心通過(guò)無(wú)線方式傳送隨機(jī)投影值的兩種方法:直傳式和路由中轉(zhuǎn)式。

文獻(xiàn)［3］首次提出大規(guī)模 WSN的壓縮數(shù)據(jù)收集(Compressive Data Gathering，CDG)方案，不再采用文獻(xiàn)［2］的每個(gè)節(jié)點(diǎn)各自傳送的方式，而是由匯聚節(jié)點(diǎn)(Sink)得到所有讀數(shù)的加權(quán)和。CDG的示意圖如圖1所示。

圖1 多跳路由的壓縮數(shù)據(jù)收集示意圖Fig.1 Schematic diagram of compressive data gathering in a multi-hop routing

CDG基于CS理論，對(duì)M×N 維測(cè)量矩陣的每一行系數(shù)在N個(gè)傳感器節(jié)點(diǎn)上進(jìn)行投影，每個(gè)節(jié)點(diǎn)有M個(gè)投影系數(shù){ Φi，j}Mi=1，然后與本地采集的數(shù)據(jù)進(jìn)行加權(quán)傳輸。例如傳感器節(jié)點(diǎn)s1將它的采集數(shù)據(jù)d1和投影系數(shù)1的乘積v1傳送給下一個(gè)節(jié)點(diǎn)s2，s2將它的d2和投影系數(shù)2的乘積v2再加上v1傳給下一個(gè)節(jié)點(diǎn)s3，沿路由不斷進(jìn)行下去，最后Sink得到一個(gè)加權(quán)和測(cè)量值。每個(gè)節(jié)點(diǎn)經(jīng)過(guò)M次傳送后，Sink就能得到M個(gè)測(cè)量值。然后利用重構(gòu)算法得到原始信號(hào)。基于CS的壓縮數(shù)據(jù)收集將Sink所需的N個(gè)采樣值轉(zhuǎn)化為收集M(M N)個(gè)本地采樣值的加權(quán)和。減少了傳輸?shù)臄?shù)據(jù)量，降低了能耗，延長(zhǎng)了網(wǎng)絡(luò)壽命。因此，該收集方案成為多跳路由收集的基本方案。

如果測(cè)量矩陣是稀疏隨機(jī)投影矩陣，則每行系數(shù)會(huì)出現(xiàn)若干0，與節(jié)點(diǎn)采樣值的乘積也為0，這時(shí)無(wú)需進(jìn)行傳輸，因此對(duì)于稀疏測(cè)量矩陣，只需要傳送非0系數(shù)對(duì)應(yīng)的節(jié)點(diǎn)的加權(quán)結(jié)果。所以，隨機(jī)投影傳輸?shù)臄?shù)據(jù)量更少，從而更加延長(zhǎng)了網(wǎng)絡(luò)壽命。Haupt等［4］最早就指出一個(gè)相對(duì)較小的信號(hào)的隨機(jī)投影數(shù)可以包含其大部分顯著的信息;因此，如果一個(gè)信號(hào)在某些正交基上是可壓縮的，則可以非常精確地從隨機(jī)投影得到重建，因而，稀疏隨機(jī)矩陣成為CS在WSN中應(yīng)用的首選矩陣。文獻(xiàn)［5］利用稀疏隨機(jī)矩陣降低通信成本來(lái)恢復(fù)在信道衰落下由WSN觀測(cè)的稀疏信號(hào)，但重點(diǎn)研究的是信號(hào)恢復(fù)所需的測(cè)量次數(shù)。文獻(xiàn)［6］提出了一種大規(guī)模WSN的自適應(yīng)稀疏隨機(jī)投影算法，主要考慮隨機(jī)投影的稀疏性對(duì)均方誤差和系統(tǒng)時(shí)延的影響，以更好地實(shí)現(xiàn)均方誤差和系統(tǒng)延遲之間的權(quán)衡。文獻(xiàn)［7］利用稀疏隨機(jī)測(cè)量矩陣的優(yōu)點(diǎn)來(lái)減少能量消耗，提出基于簇的加權(quán)壓縮數(shù)據(jù)采集方法，采用最小生成樹(shù)投影來(lái)減少能量消耗，減少傳感器節(jié)點(diǎn)數(shù)。但是僅針對(duì)空間相關(guān)的數(shù)據(jù)收集，也沒(méi)有考慮收集器的最優(yōu)位置。文獻(xiàn)［8］綜述了基于CS的WSN壓縮數(shù)據(jù)收集的不同方法。這些文獻(xiàn)都用到了稀疏隨機(jī)投影矩陣，但都沒(méi)有說(shuō)明采集數(shù)據(jù)的具體收集過(guò)程。

文獻(xiàn)［9－10］提出了一種采用隨機(jī)投影的壓縮數(shù)據(jù)收集方法，即在網(wǎng)絡(luò)中隨機(jī)選擇M個(gè)節(jié)點(diǎn)稱為投影節(jié)點(diǎn)以收集M個(gè)加權(quán)和。投影節(jié)點(diǎn)相當(dāng)于簇頭，測(cè)量矩陣Φ的每一行非0元素對(duì)應(yīng)的節(jié)點(diǎn)分配給一個(gè)投影節(jié)點(diǎn)。每個(gè)投影節(jié)點(diǎn)通過(guò)最小生成樹(shù)路由收集相應(yīng)這一行數(shù)據(jù)的加權(quán)和，并發(fā)送給Sink，從而完成全部數(shù)據(jù)收集，形成M個(gè)測(cè)量值。該方案存在的一個(gè)主要問(wèn)題就是投影節(jié)點(diǎn)的選擇是根據(jù)M/N的概率隨機(jī)選出的。由于其隨機(jī)性，選出的投影節(jié)點(diǎn)無(wú)任何規(guī)律可言，不能保證選擇出位置合適、能量較高、數(shù)量精確的理想的投影節(jié)點(diǎn)。但顯然，投影節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置會(huì)影響聚合算法的效率。其次，由于測(cè)量矩陣每行的非0系數(shù)的位置也是隨機(jī)的，一組遠(yuǎn)近不等的節(jié)點(diǎn)將加權(quán)和傳送到位置不定的投影節(jié)點(diǎn)，這樣的網(wǎng)絡(luò)耗能勢(shì)必會(huì)很不均衡。而且由非0節(jié)點(diǎn)到投影節(jié)點(diǎn)通過(guò)樹(shù)結(jié)構(gòu)建立路由，開(kāi)銷也較大，另外也沒(méi)有說(shuō)明在網(wǎng)絡(luò)運(yùn)行過(guò)程中出現(xiàn)節(jié)點(diǎn)死亡后的情形。

針對(duì)隨機(jī)選擇投影節(jié)點(diǎn)產(chǎn)生的問(wèn)題，本文提出均衡投影節(jié)點(diǎn)的壓縮數(shù)據(jù)收集方法。根據(jù)WSN節(jié)點(diǎn)分布是否均勻提出基于空間位置和基于節(jié)點(diǎn)分布密度的均衡分簇法，然后再進(jìn)行壓縮數(shù)據(jù)收集，并通過(guò)與隨機(jī)投影節(jié)點(diǎn)方法的比較，驗(yàn)證了本文方法能夠有效平衡網(wǎng)絡(luò)能耗、延長(zhǎng)網(wǎng)絡(luò)壽命。

1 均衡分簇原理

1.1 壓縮感知基本理論

壓縮感知［11－12］理論指出［13］:對(duì)于稀疏信號(hào)或可壓縮信號(hào)，可以以遠(yuǎn)低于Nyquist頻率的采樣頻率對(duì)數(shù)據(jù)采樣，然后通過(guò)非線性重建算法完美地重建信號(hào)。設(shè)N維信號(hào)x，在某N×N維的稀疏變換矩陣Ψ下可以表示為:

其中:θ是K稀疏的N×1的列向量，即θ中只有K個(gè)非零項(xiàng)，且K N。然后在M×N維測(cè)量矩陣(或稱投影矩陣、觀測(cè)矩陣)Φ下投影，得M個(gè)觀測(cè)值y，且M N，即:

其中:T稱為傳感矩陣;y為M×1的列向量，即為測(cè)量值。

壓縮感知理論指出，式(2)存在確定解的充分條件是T滿足有限等距性質(zhì)(Restricted Isometry Property，RIP)［14］，即存在δ∈(0，1)使得全部K稀疏信號(hào)θ均滿足:

則可以通過(guò)求解以下凸優(yōu)化問(wèn)題得到重建信號(hào)^θ［12－13］:

式(4)可以采用基追蹤或貪婪算法等方法重構(gòu)原始信號(hào)^x。

1.2 均衡分簇原理

根據(jù)CS理論，設(shè)測(cè)量矩陣Φ是M×N維的矩陣，x為N×1維的列向量，則有:

其中:Xj是將N個(gè)x分成L段的各分段，每段長(zhǎng)度設(shè)為Nj(j=1，2，…，L);每個(gè)Φj為M × Nj(j=1，2，…，L) 維矩陣。這樣，每段x就可以稱為一個(gè)簇，每個(gè)簇可以選擇一個(gè)投影節(jié)點(diǎn)作為簇頭。簇頭收集每個(gè)簇的數(shù)據(jù)傳到Sink，Sink將所有簇的數(shù)

從式(5)可以看出，對(duì)于N個(gè)節(jié)點(diǎn)xj(j=1，2，…，N)，可以將Φ中每行與x乘加的結(jié)果一次算出來(lái)，得M個(gè)測(cè)量值。也可以把N個(gè)節(jié)點(diǎn)分段來(lái)處理，假設(shè)將N個(gè)節(jié)點(diǎn)分成L段，每段可以是不同的點(diǎn)數(shù)量。測(cè)量矩陣Φ，也可以對(duì)應(yīng)分成L塊，每塊為M行的矩陣，列數(shù)與對(duì)應(yīng)x各分段的點(diǎn)數(shù)相等。每個(gè)分塊矩陣與對(duì)應(yīng)的x的每段相乘便得到M×1的列向量，然后L個(gè)列向量再進(jìn)行相加，得M個(gè)測(cè)量值。用公式表示為:據(jù)對(duì)應(yīng)相加，就得到了最終的測(cè)量值。用這個(gè)測(cè)量值及傳感矩陣，就可以進(jìn)行數(shù)據(jù)重構(gòu)。若只對(duì)某些區(qū)域感興趣，也可以只取其中某些段，由于測(cè)量矩陣具有隨機(jī)性，部分隨機(jī)矩陣仍滿足RIP，仍可恢復(fù)信號(hào)，由于測(cè)量比增加，會(huì)得到更高的重構(gòu)性能。

在每個(gè)分段選擇一個(gè)投影節(jié)點(diǎn)，可使投影節(jié)點(diǎn)分布均衡;而且，依據(jù)一定條件來(lái)選擇，可以選出能量較高，位置更優(yōu)越的投影節(jié)點(diǎn)。本文根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布是否均勻，提出了兩種均衡分簇的方法。

2 基于空間位置的均衡分簇法

針對(duì)節(jié)點(diǎn)分布密度均勻的網(wǎng)絡(luò)，提出基于空間位置的均衡分簇法。為了使投影節(jié)點(diǎn)分布均勻，將監(jiān)測(cè)區(qū)域劃分成大小相等的網(wǎng)格，在每個(gè)網(wǎng)格內(nèi)選舉性能最優(yōu)的節(jié)點(diǎn)作為投影節(jié)點(diǎn)。然后投影節(jié)點(diǎn)收集所在簇的加權(quán)和數(shù)據(jù)，再傳送到Sink。具體的實(shí)施過(guò)程如下。

1)選擇第一輪的投影節(jié)點(diǎn)及成簇:

a)確定分簇?cái)?shù)量及網(wǎng)格數(shù)。

b)以相同尺寸劃分整個(gè)監(jiān)測(cè)區(qū)域?yàn)樗?jì)算的網(wǎng)格數(shù)。

c)在每個(gè)網(wǎng)格選擇網(wǎng)格中心周圍位置且能量較高的節(jié)點(diǎn)作投影節(jié)點(diǎn)。

d)發(fā)送投影節(jié)點(diǎn)信息給每個(gè)網(wǎng)格的投影節(jié)點(diǎn)。

e)每個(gè)傳感器節(jié)點(diǎn)依據(jù)距離最近(跳步最少)選擇它相應(yīng)的投影節(jié)點(diǎn)。

2)在一輪簇建立以后，就可以進(jìn)行數(shù)據(jù)收集了，簇內(nèi)數(shù)據(jù)通過(guò)傳感節(jié)點(diǎn)經(jīng)路由傳送到簇內(nèi)投影節(jié)點(diǎn)。全部簇的投影節(jié)點(diǎn)所收集數(shù)據(jù)經(jīng)一定路由傳至匯聚節(jié)點(diǎn)，再將其對(duì)應(yīng)相加，就是全部測(cè)量值，然后通過(guò)重構(gòu)就可以恢復(fù)原始數(shù)據(jù)。

3)接著就可以進(jìn)行下一輪投影節(jié)點(diǎn)的選擇和新簇的建立，其過(guò)程為:

a)簇內(nèi)節(jié)點(diǎn)將其剩余能量值傳送給投影節(jié)點(diǎn)。

b)投影節(jié)點(diǎn)選擇簇中心能量較大者作為新投影節(jié)點(diǎn)。c)每個(gè)原來(lái)的投影節(jié)點(diǎn)將其信息傳給新投影節(jié)點(diǎn)。d)每個(gè)傳感節(jié)點(diǎn)尋找它的新投影節(jié)點(diǎn)，形成新簇。

2.1 簇頭數(shù)目的確定

由于能量問(wèn)題是WSN中路由算法需要考慮的首要問(wèn)題，本文采用了簡(jiǎn)化的網(wǎng)絡(luò)信道損耗模型［15］，如圖2所示。

圖2 信道損耗模型Fig.2 Channel loss model

假設(shè)有N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在半徑為R的區(qū)域內(nèi)，其中簇頭個(gè)數(shù)為h，則簇頭節(jié)點(diǎn)的平均覆蓋面積為πR2/h。假設(shè)簇頭節(jié)點(diǎn)每跳的傳輸距離為D，每個(gè)簇頭的能量消耗在三方面:接收所有簇成員的信息、融合這些數(shù)據(jù)、把融合后的信息傳送給Sink節(jié)點(diǎn)［16］。則在一幀中簇頭節(jié)點(diǎn)消耗的能量為:

其中:k為每個(gè)數(shù)據(jù)的信息位數(shù);Eelect為每比特?cái)?shù)據(jù)在發(fā)射電路或接收電路中所消耗的能量;EDA為數(shù)據(jù)融合的消耗;Efs為耗散能量，與所采用的傳輸信號(hào)模型有關(guān)，為自由空間傳輸常數(shù);D是簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離。

假設(shè)簇內(nèi)傳感器節(jié)點(diǎn)離簇頭的距離不超過(guò)自由空間模型的臨界值［16］，則一個(gè)非簇頭節(jié)點(diǎn)的能量消耗為:

發(fā)送一幀中一個(gè)簇的能量消耗為:

在R區(qū)域每個(gè)簇發(fā)送一幀(忽略數(shù)據(jù)轉(zhuǎn)發(fā)的能量消耗)的總能量消耗為:

由式(9)～(11)整理化簡(jiǎn)得:

對(duì)Etotal求導(dǎo)，得到最優(yōu)簇頭數(shù)為:

若設(shè)定監(jiān)測(cè)區(qū)域大小為100 m×100 m的空間，部署有100個(gè)傳感器節(jié)點(diǎn)，每跳的傳輸距離D為槡50 2 m，半徑R設(shè)為方形區(qū)域的半邊長(zhǎng)50 m，則根據(jù)式(13)得h≈17。為方便計(jì)可將區(qū)域劃分為16個(gè)網(wǎng)格。

2.2 節(jié)點(diǎn)的網(wǎng)格坐標(biāo)

空間投影節(jié)點(diǎn)均衡劃分通過(guò)網(wǎng)格來(lái)實(shí)現(xiàn)，首先考慮節(jié)點(diǎn)分布密度恒定的場(chǎng)合。一個(gè)網(wǎng)格選擇一個(gè)投影節(jié)點(diǎn)，因此100 m×100 m的區(qū)域劃分成4×4的16個(gè)網(wǎng)格，如圖3所示，鄰近網(wǎng)格內(nèi)的節(jié)點(diǎn)都可以互相傳輸信息，并且呈對(duì)角線分布的兩個(gè)網(wǎng)格在對(duì)角線的兩端的節(jié)點(diǎn)都在通信范圍內(nèi)。設(shè)這些網(wǎng)格的邊長(zhǎng)是d，節(jié)點(diǎn)可以傳輸?shù)淖钸h(yuǎn)距離是Rs，則兩個(gè)節(jié)點(diǎn)之間互相傳輸信息的距離是Rs≤ 2d。

圖3 節(jié)點(diǎn)分布密度均勻的網(wǎng)格劃分Fig.3 Grid partition with uniform node distribution density

在劃分好的網(wǎng)格下，首先要確定節(jié)點(diǎn)的網(wǎng)格坐標(biāo)。假設(shè)Sink位于區(qū)域中心，根據(jù)節(jié)點(diǎn)地理位置計(jì)算其在區(qū)域內(nèi)的網(wǎng)格坐標(biāo):

其中:Tx表示節(jié)點(diǎn)的網(wǎng)格橫坐標(biāo);Ty表示節(jié)點(diǎn)的網(wǎng)格縱坐標(biāo);S(i).xd和S(i).yd分別表示節(jié)點(diǎn)本身的橫坐標(biāo)和縱坐標(biāo);Xm和Ym是監(jiān)測(cè)區(qū)域的長(zhǎng)和寬;L1是區(qū)域長(zhǎng)度的等分?jǐn)?shù);L2是區(qū)域?qū)挾鹊牡确謹(jǐn)?shù);floor(x)表示不大于x的整數(shù)。網(wǎng)格坐標(biāo)一樣的節(jié)點(diǎn)視為一組。例如在圖3中，根據(jù)式(14)可得每個(gè)節(jié)點(diǎn)所屬網(wǎng)格的坐標(biāo)，并給每個(gè)網(wǎng)格設(shè)置一個(gè)編號(hào)，分別對(duì)應(yīng)從1到16。

2.3 簇頭選舉及成簇

在每個(gè)網(wǎng)格中，先根據(jù)每個(gè)節(jié)點(diǎn)的剩余能量和該節(jié)點(diǎn)到數(shù)據(jù)收集中心的距離來(lái)選擇簇頭。簇頭選擇節(jié)點(diǎn)競(jìng)爭(zhēng)半徑較大的。競(jìng)爭(zhēng)半徑公式為:

其中:b是(0，1)范圍的一個(gè)隨機(jī)數(shù)字，保證結(jié)果在一定范圍內(nèi);dmax表示該網(wǎng)格內(nèi)節(jié)點(diǎn)與Sink最遠(yuǎn)的距離;dmin表示該網(wǎng)格內(nèi)節(jié)點(diǎn)與Sink最近的距離;dbs表示當(dāng)前節(jié)點(diǎn)到Sink的距離;E0表示節(jié)點(diǎn)初始能量;Ed表示節(jié)點(diǎn)能否傳輸信息的臨界能量;S(i).E表示節(jié)點(diǎn)當(dāng)前所擁有的能量;D表示最大的傳感半徑。競(jìng)爭(zhēng)半徑考慮了節(jié)點(diǎn)的剩余能量以及該節(jié)點(diǎn)與Sink的距離兩個(gè)方面，競(jìng)爭(zhēng)半徑大的節(jié)點(diǎn)當(dāng)選簇頭對(duì)這個(gè)網(wǎng)格內(nèi)的所有節(jié)點(diǎn)是最有利的。

在每個(gè)網(wǎng)格中，將該網(wǎng)格中的每個(gè)節(jié)點(diǎn)計(jì)算出來(lái)的競(jìng)爭(zhēng)半徑進(jìn)行比較，將競(jìng)爭(zhēng)半徑最大的節(jié)點(diǎn)選為簇頭。所有網(wǎng)格內(nèi)都選出一個(gè)簇頭之后，整個(gè)網(wǎng)絡(luò)中的除簇頭以外的其他節(jié)點(diǎn)找到與之距離最近的簇頭，向其發(fā)送要加入該簇頭所創(chuàng)建簇的請(qǐng)求，簇頭收到距離它較近的節(jié)點(diǎn)發(fā)來(lái)的加入簇請(qǐng)求之后，要向這些節(jié)點(diǎn)發(fā)送同意其加入簇的信息。等所有節(jié)點(diǎn)都有了歸屬的簇之后，就組成了無(wú)線傳感器網(wǎng)絡(luò)。

2.4 仿真研究

仿真實(shí)驗(yàn)中，先對(duì)WSN和傳感器節(jié)點(diǎn)作如下的假設(shè):

1)Sink節(jié)點(diǎn)位置固定在區(qū)域中央;

2)傳感器節(jié)點(diǎn)都是靜止的;

3)傳感器節(jié)點(diǎn)不能獲知其自身的位置信息;

4)簇頭融合單位數(shù)據(jù)消耗的能量相同;

5)網(wǎng)絡(luò)中單位面積的區(qū)域需要檢測(cè)的數(shù)據(jù)量相同;

6)每個(gè)節(jié)點(diǎn)的覆蓋面積相同;

7)無(wú)線信道對(duì)稱。

對(duì)基于空間位置的均衡分簇法，并假設(shè)傳感器節(jié)點(diǎn)均勻分布在監(jiān)測(cè)區(qū)域。仿真參數(shù)如見(jiàn)表1所示。

表1 仿真相關(guān)參數(shù)Tab.1 Simulation related parameters

圖4(a)是節(jié)點(diǎn)均勻網(wǎng)絡(luò)基于位置方法選舉的簇頭和成簇效果，可以看出，通過(guò)網(wǎng)格劃分，節(jié)點(diǎn)分布密度均勻的網(wǎng)絡(luò)簇頭選舉也很均勻。圖4(b)所示為該網(wǎng)絡(luò)在300輪時(shí)的節(jié)點(diǎn)分布和成簇情況，圓點(diǎn)為死亡的節(jié)點(diǎn)?？梢?jiàn)在網(wǎng)絡(luò)運(yùn)行過(guò)程中的成簇仍然是均衡的，每個(gè)網(wǎng)格選擇一個(gè)投影節(jié)點(diǎn)。

基于位置和基于隨機(jī)投影節(jié)點(diǎn)的兩種方法的剩余節(jié)點(diǎn)數(shù)的比較如圖5所示。

由圖5可以看出:在網(wǎng)絡(luò)開(kāi)始運(yùn)行階段，基于位置分簇的效果要差一些，死亡節(jié)點(diǎn)出現(xiàn)比較早，剩余節(jié)點(diǎn)數(shù)較少，但不影響網(wǎng)絡(luò)運(yùn)行;當(dāng)運(yùn)行到剩余節(jié)點(diǎn)數(shù)為80%的時(shí)候，基于隨機(jī)投影的死亡節(jié)點(diǎn)迅速增加，并很快超過(guò)了基于位置分簇的死亡節(jié)點(diǎn)數(shù)，剩余節(jié)點(diǎn)數(shù)迅速降低:在385輪時(shí)剩余節(jié)點(diǎn)數(shù)由20點(diǎn)瞬間將為0，網(wǎng)絡(luò)癱瘓，但此輪時(shí)基于位置分簇的網(wǎng)絡(luò)仍有近40%的節(jié)點(diǎn)存活，網(wǎng)絡(luò)仍能運(yùn)行。以剩余節(jié)點(diǎn)數(shù)為20點(diǎn)時(shí)作為網(wǎng)絡(luò)正常運(yùn)行的臨界點(diǎn)來(lái)考慮，低于20點(diǎn)網(wǎng)絡(luò)無(wú)法聯(lián)通，基于位置分簇的網(wǎng)絡(luò)比基于隨機(jī)投影節(jié)點(diǎn)分簇的網(wǎng)絡(luò)生存期延長(zhǎng)了約35%。

圖5 基于位置和隨機(jī)分簇的節(jié)點(diǎn)均勻WSN的剩余節(jié)點(diǎn)數(shù)比較Fig.5 Comparison of remaining nodes of WSN with node even distribution based on location and random clustering

3 基于節(jié)點(diǎn)分布密度的均衡分簇法

針對(duì)節(jié)點(diǎn)分布不均的WSN，每個(gè)網(wǎng)格的節(jié)點(diǎn)數(shù)量多少不等，如果采用第2章的基于位置的分簇法在每個(gè)網(wǎng)格選擇一個(gè)投影節(jié)點(diǎn)，節(jié)點(diǎn)少的網(wǎng)格的投影節(jié)點(diǎn)能量會(huì)很快耗盡，為了適應(yīng)節(jié)點(diǎn)不均的網(wǎng)絡(luò)，本文提出基于節(jié)點(diǎn)密度的均衡分簇法。

3.1 基于分布密度的均衡分簇

對(duì)于節(jié)點(diǎn)分布密度不均的WSN，節(jié)點(diǎn)數(shù)較多的網(wǎng)格組成一個(gè)簇之后可以較好地進(jìn)行節(jié)點(diǎn)與節(jié)點(diǎn)、節(jié)點(diǎn)與簇頭、簇頭與Sink的數(shù)據(jù)傳輸，還可以使收集同一種信息的部分節(jié)點(diǎn)進(jìn)入休眠，節(jié)省能量消耗。而節(jié)點(diǎn)數(shù)較少的網(wǎng)格形成一個(gè)簇之后，簇頭只能在這幾個(gè)節(jié)點(diǎn)之間輪換，加快了該網(wǎng)格的能量消耗，使這些區(qū)域的節(jié)點(diǎn)過(guò)早地死亡，造成網(wǎng)絡(luò)耗能的不均衡。

節(jié)點(diǎn)分布密度的衡量通過(guò)網(wǎng)格來(lái)得到，網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)量少的，說(shuō)明密度小;反之說(shuō)明密度大。因此首先進(jìn)行網(wǎng)格內(nèi)節(jié)點(diǎn)的調(diào)整，計(jì)算每個(gè)網(wǎng)格中的節(jié)點(diǎn)的數(shù)量。如果網(wǎng)格的節(jié)點(diǎn)的數(shù)量少于等于p，這些網(wǎng)格中的節(jié)點(diǎn)就被歸到節(jié)點(diǎn)數(shù)量大于p的其他鄰近網(wǎng)格。所有節(jié)點(diǎn)數(shù)量小于等于p的網(wǎng)格中的節(jié)點(diǎn)都?xì)w到指定網(wǎng)格中之后，就形成了一個(gè)新的網(wǎng)格劃分格局。這樣，就可以避免節(jié)點(diǎn)不均衡的能量消耗，從而提高整個(gè)網(wǎng)絡(luò)的存活周期。接下來(lái)，就可進(jìn)行簇頭選舉和形成簇。

3.2 仿真分析

仿真實(shí)驗(yàn)中，對(duì)WSN和傳感器節(jié)點(diǎn)的假設(shè)同2.4節(jié)。對(duì)基于節(jié)點(diǎn)分布密度的均衡分簇法，并假設(shè)傳感器節(jié)點(diǎn)隨機(jī)非均勻分布在監(jiān)測(cè)區(qū)域。為了研究比較，分別在兩個(gè)場(chǎng)景中進(jìn)行了仿真，具體參數(shù)如表2所示。對(duì)場(chǎng)景2，監(jiān)測(cè)區(qū)域大小為200 m×200 m的空間，部署有400個(gè)傳感器節(jié)點(diǎn)，傳感器節(jié)點(diǎn)的通信半徑D為槡50 2 m，監(jiān)測(cè)區(qū)域半徑R相當(dāng)于為100 m，則根據(jù)式(13)得h≈68。為仿真方便可將區(qū)域劃分為64個(gè)網(wǎng)格。

表2 仿真相關(guān)參數(shù)(場(chǎng)景1、場(chǎng)景2)Tab.2 Simulation related parameters(scene 1 and scene 2)

下面就用同樣節(jié)點(diǎn)布置的網(wǎng)絡(luò)來(lái)測(cè)試基于節(jié)點(diǎn)分布密度分簇法和文獻(xiàn)［9］采用隨機(jī)投影節(jié)點(diǎn)方法的性能。

場(chǎng)景1的基于節(jié)點(diǎn)分布密度均衡分簇法的成簇效果如圖6所示。圖6(a)是第一輪成簇的示意圖，可見(jiàn)節(jié)點(diǎn)密度小的網(wǎng)格，其節(jié)點(diǎn)進(jìn)行了網(wǎng)格的重新分配，加入到了距離鄰近的簇，不再進(jìn)行投影節(jié)點(diǎn)的選擇。圖6(b)是第300輪時(shí)的成簇效果，仍有約60%的節(jié)點(diǎn)存活，可見(jiàn)網(wǎng)絡(luò)仍然運(yùn)行良好。

圖7(a)是文獻(xiàn)［9］采用隨機(jī)投影節(jié)點(diǎn)的方法，它的投影節(jié)點(diǎn)是隨機(jī)產(chǎn)生的，從中可以看出，投影節(jié)點(diǎn)的位置很隨機(jī)，形成的簇大小也不均衡。圖7(b)是其300輪時(shí)的成簇效果，比圖6(b)的節(jié)點(diǎn)數(shù)明顯減少，而且邊遠(yuǎn)的節(jié)點(diǎn)大部分死亡，只有Sink附近的網(wǎng)絡(luò)在運(yùn)行，信息的獲取已經(jīng)失衡。

圖6 基于密度分簇的節(jié)點(diǎn)不均勻分布WSN的成簇特性(場(chǎng)景1)Fig.6 Clustering characteristics of WSN with node uneven distribution based on density clustering(scene 1)

本文方法和隨機(jī)投影節(jié)點(diǎn)方法的剩余節(jié)點(diǎn)數(shù)在場(chǎng)景1下的對(duì)比如圖8所示。從圖8可以看出，隨機(jī)投影節(jié)點(diǎn)方法的死亡節(jié)點(diǎn)出現(xiàn)比較晚，但節(jié)點(diǎn)死亡的速度下降比較快，在剩20個(gè)節(jié)點(diǎn)的時(shí)候驟然癱瘓。而基于節(jié)點(diǎn)密度分簇的方法的死亡節(jié)點(diǎn)數(shù)下降比較緩慢，使得網(wǎng)絡(luò)的運(yùn)行時(shí)間增長(zhǎng)，而且網(wǎng)絡(luò)也沒(méi)有突然終止。以剩余20個(gè)節(jié)點(diǎn)為網(wǎng)絡(luò)正常運(yùn)行狀態(tài)的臨界值來(lái)考慮，隨機(jī)投影方法壽命接近400輪，基于密度分簇的網(wǎng)絡(luò)壽命約為550輪，基于密度分簇法的網(wǎng)絡(luò)生存期延長(zhǎng)了約27%，而且在未癱瘓前，剩余節(jié)點(diǎn)數(shù)也較隨機(jī)投影方法的節(jié)點(diǎn)數(shù)多約20%，運(yùn)行狀態(tài)優(yōu)良。

另外由圖8與圖5比較可見(jiàn)，基于隨機(jī)投影節(jié)點(diǎn)方法在不同節(jié)點(diǎn)分布的網(wǎng)絡(luò)節(jié)點(diǎn)死亡的速度都比較快，在還有約20個(gè)存活節(jié)點(diǎn)數(shù)的時(shí)候，都會(huì)驟然癱瘓，而本文方法的死亡節(jié)點(diǎn)數(shù)下降都比較緩慢，網(wǎng)絡(luò)可以維持較長(zhǎng)的時(shí)間。

對(duì)于場(chǎng)景2，應(yīng)用基于密度分簇法和隨機(jī)投影節(jié)點(diǎn)法對(duì)同樣布置的非均勻節(jié)點(diǎn)進(jìn)行分簇?；诠?jié)點(diǎn)密度分簇法的簇頭分布和成簇效果如圖9所示。同樣可見(jiàn)，節(jié)點(diǎn)數(shù)少的網(wǎng)格不再選擇投影節(jié)點(diǎn)，而是與鄰近網(wǎng)格合并形成一個(gè)簇，從而均衡了能耗。

基于密度分簇法和隨機(jī)投影節(jié)點(diǎn)方法的剩余節(jié)點(diǎn)數(shù)在場(chǎng)景2下的對(duì)比如圖10所示。由圖10可以看出，基于隨機(jī)投影節(jié)點(diǎn)的方法的剩余節(jié)點(diǎn)數(shù)隨輪數(shù)增加迅速下降，同樣在剩20個(gè)節(jié)點(diǎn)時(shí)驟然為0，網(wǎng)絡(luò)停止運(yùn)行。而本文方法在每輪的剩余節(jié)點(diǎn)數(shù)都比隨機(jī)分簇方法的多，在網(wǎng)絡(luò)運(yùn)行中期，可以達(dá)到2倍左右的數(shù)量。而在隨機(jī)分簇網(wǎng)絡(luò)癱瘓后，本文的均衡分簇網(wǎng)絡(luò)仍可運(yùn)行，壽命延長(zhǎng)了約25%。

圖8 基于密度和隨機(jī)投影節(jié)點(diǎn)兩種分簇方法的剩余節(jié)點(diǎn)數(shù)對(duì)比(場(chǎng)景1)Fig.8 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 1)

從圖5、圖8和圖10中本文方法與基于隨機(jī)投影節(jié)點(diǎn)方法的比較來(lái)看，在整個(gè)網(wǎng)絡(luò)的正常運(yùn)行期間，相比隨機(jī)投影節(jié)點(diǎn)方法，本文方法的剩余節(jié)點(diǎn)數(shù)明顯較多，網(wǎng)絡(luò)運(yùn)行時(shí)間長(zhǎng)，運(yùn)行狀態(tài)優(yōu)良，耗能均衡。

圖9 基于節(jié)點(diǎn)密度分簇法的WSN簇頭分布和成簇效果(場(chǎng)景2)Fig.9 Cluster head distribution and clustering effect of WSN based on node density clustering method(scene 2)

圖10 基于密度和隨機(jī)投影節(jié)點(diǎn)兩種分簇方法的剩余節(jié)點(diǎn)數(shù)對(duì)比(場(chǎng)景2)Fig.10 Comparison of remaining nodes based on two clustering methods based on density and random projection nodes(scene 2)

3.3 均衡投影的壓縮數(shù)據(jù)收集

基于均衡投影的壓縮數(shù)據(jù)收集方法的具體實(shí)施環(huán)節(jié)包括以下幾點(diǎn):

1)根據(jù)網(wǎng)絡(luò)參數(shù)，確定劃分網(wǎng)格的數(shù)量，并以此劃分網(wǎng)格。

2)均衡選擇投影節(jié)點(diǎn)并建簇。采用基于空間位置或節(jié)點(diǎn)密度的均衡分簇法，選擇投影節(jié)點(diǎn)，并以投影節(jié)點(diǎn)為中心建立一個(gè)簇。

3)M×N維測(cè)量矩陣的每行非零系數(shù)對(duì)應(yīng)的節(jié)點(diǎn)統(tǒng)一編為一個(gè)號(hào) S(S ∈ {1，2，…，M})。

4)根據(jù)CS理論，每個(gè)投影節(jié)點(diǎn)收集相同編號(hào)的節(jié)點(diǎn)的加權(quán)和并一跳或多跳傳給Sink。若是多跳傳輸，在傳輸過(guò)程中將相同編號(hào)的數(shù)據(jù)相加，再傳給Sink。

5)經(jīng)過(guò)M次傳輸，Sink將收集的所有相同編號(hào)的數(shù)據(jù)相加，就可得M個(gè)測(cè)量值。應(yīng)用重構(gòu)算法，就可重構(gòu)原始數(shù)據(jù)。

采用均衡分簇法，保證了投影節(jié)點(diǎn)的均衡分布，也均衡了網(wǎng)絡(luò)的整體能耗。由于采用了稀疏隨機(jī)投影矩陣，只需傳送非0節(jié)點(diǎn)的加權(quán)數(shù)據(jù)，使得整個(gè)網(wǎng)絡(luò)的能耗降低;而且，如果測(cè)量矩陣的每一列只有一個(gè)非0元素，這樣每一行的非0系數(shù)的節(jié)點(diǎn)互不干擾，就可以同時(shí)進(jìn)行M個(gè)測(cè)量值的傳送，不必間隔時(shí)隙完成，這樣的傳送速度更快，實(shí)時(shí)性更強(qiáng)。

而且，基于網(wǎng)格的建簇較之一般的分簇方法并沒(méi)有增加開(kāi)銷，由于劃分好了網(wǎng)格，只需要在網(wǎng)格中選擇出投影節(jié)點(diǎn)，就可以形成一個(gè)簇。由于網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)量有限，所以投影節(jié)點(diǎn)的選擇比一般分簇的簇頭的選擇速度要快;而且對(duì)基于密度的均衡分簇，當(dāng)網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)少于某閾值就不需要選擇投影節(jié)點(diǎn)了，開(kāi)銷更為減少。因此，本文建簇的方法更為節(jié)能。

4 結(jié)語(yǔ)

針對(duì)投影節(jié)點(diǎn)隨機(jī)選擇、位置不均衡的問(wèn)題，本文提出了基于均衡投影的壓縮數(shù)據(jù)收集方法，并針對(duì)均勻分布節(jié)點(diǎn)WSN，提出基于空間位置的均衡分簇法，以大小相同的網(wǎng)格劃分來(lái)實(shí)現(xiàn)，保證了投影節(jié)點(diǎn)的位置均衡;針對(duì)不均勻節(jié)點(diǎn)分布WSN，提出基于節(jié)點(diǎn)密度的均衡分簇法，同時(shí)考慮了位置和密度因素，減少了孤立點(diǎn)的能耗，均衡了能量，延長(zhǎng)了網(wǎng)絡(luò)壽命。通過(guò)與隨機(jī)投影節(jié)點(diǎn)方法的仿真比較，本文方法運(yùn)行狀態(tài)優(yōu)良，網(wǎng)絡(luò)生存期顯著延長(zhǎng)。但對(duì)于非均勻WSN，按密度分簇的閾值需要根據(jù)實(shí)際應(yīng)用中網(wǎng)絡(luò)規(guī)模、節(jié)點(diǎn)整體分布密度和應(yīng)用需求等綜合因素來(lái)選擇，并需要先進(jìn)行實(shí)驗(yàn)和驗(yàn)證。