基于混合壓縮感知的分簇式網(wǎng)絡(luò)數(shù)據(jù)收集方法

李哲濤 臧 浪 田淑娟 李仁發(fā)

1(湘潭大學(xué)信息工程學(xué)院 湖南湘潭 411105)2(江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué)) 南京 210003)3(智能計(jì)算與信息處理教育部重點(diǎn)實(shí)驗(yàn)室(湘潭大學(xué)) 湖南湘潭 411105)4 (湖南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410082)(sjtianwork@xtu.edu.cn)

基于混合壓縮感知的分簇式網(wǎng)絡(luò)數(shù)據(jù)收集方法

李哲濤1,2,3臧 浪1,3田淑娟1,3李仁發(fā)4

1(湘潭大學(xué)信息工程學(xué)院 湖南湘潭 411105)2(江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué)) 南京 210003)3(智能計(jì)算與信息處理教育部重點(diǎn)實(shí)驗(yàn)室(湘潭大學(xué)) 湖南湘潭 411105)4(湖南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410082)(sjtianwork@xtu.edu.cn)

為了減少分簇式傳感器網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量并均衡網(wǎng)絡(luò)負(fù)載，提出了一種采用混合壓縮感知(compressive sensing, CS)進(jìn)行數(shù)據(jù)收集的方法.1)選取各臨時(shí)簇中距離簇質(zhì)心最近的一些節(jié)點(diǎn)為候選簇頭節(jié)點(diǎn),然后依據(jù)已確定的簇頭節(jié)點(diǎn)到未確定的候選簇頭節(jié)點(diǎn)的距離依次確定簇頭;2)各普通節(jié)點(diǎn)選擇加入距離自己最近的簇中;3)貪婪構(gòu)建一棵以Sink節(jié)點(diǎn)為根節(jié)點(diǎn)并連接所有簇頭節(jié)點(diǎn)的數(shù)據(jù)傳輸樹，對(duì)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸.仿真結(jié)果表明:當(dāng)壓縮比率為10時(shí)，數(shù)據(jù)傳輸量比Clustering without CS和SPT without CS分別減少了75%和65%，比SPT with Hybrid CS和Clustering with Hybrid CS分別減少了35%和20%；節(jié)點(diǎn)數(shù)據(jù)傳輸量標(biāo)準(zhǔn)差比Clustering without CS和SPT without CS分別減少了62%和81%，比SPT with Hybrid CS和Clustering with Hybrid CS分別減少了41%和19%.

無線傳感器網(wǎng)絡(luò)；壓縮感知；數(shù)據(jù)收集；分簇網(wǎng)絡(luò);負(fù)載均衡

無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)一般由大量能量受限的傳感器節(jié)點(diǎn)與若干個(gè)基站組成,分簇式網(wǎng)絡(luò)結(jié)構(gòu)能有效消除數(shù)據(jù)冗余，減少數(shù)據(jù)通信量與通信距離，具有可擴(kuò)展性強(qiáng)、負(fù)載均衡、魯棒性強(qiáng)等特點(diǎn).在WSN中，節(jié)點(diǎn)間的通信是節(jié)點(diǎn)能量損耗的主要原因[1].WSN中存在感知數(shù)據(jù)流不均衡導(dǎo)致部分節(jié)點(diǎn)過早死亡的情況，在保證傳輸數(shù)據(jù)質(zhì)量的前提下，如何減少數(shù)據(jù)傳輸?shù)哪芰肯囊约熬饩W(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載對(duì)延長(zhǎng)網(wǎng)絡(luò)的生命周期有重要的意義.

近年來，壓縮感知(compressive sensing, CS)[2-4]技術(shù)的發(fā)展為無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集技術(shù)帶來了革命性的突破[5-9].CS可以在遠(yuǎn)低于奈奎斯特采樣速率的條件下完成對(duì)數(shù)據(jù)信息的采集，從而減少網(wǎng)絡(luò)的數(shù)據(jù)傳輸量，降低網(wǎng)絡(luò)能量消耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期.假定網(wǎng)絡(luò)由1個(gè)Sink節(jié)點(diǎn)與N個(gè)感知節(jié)點(diǎn)構(gòu)成.設(shè)x是1個(gè)具有N個(gè)元素的向量，表示網(wǎng)絡(luò)收集的數(shù)據(jù)，則每個(gè)元素對(duì)應(yīng)1個(gè)傳感器節(jié)點(diǎn)收集到的數(shù)據(jù).將x進(jìn)行稀疏化處理，x=ψs，其中,ψ是1個(gè)N×N的變換基，s是系數(shù)向量.如果系數(shù)向量s僅僅含有k個(gè)非零元素(k?N)，則稱x在ψ域上是k-稀疏的.當(dāng)k很小時(shí)，根據(jù)壓縮感知理論，僅需傳輸信號(hào)向量x的M個(gè)觀測(cè)值組成的向量y至Sink節(jié)點(diǎn)即可實(shí)現(xiàn)信息傳輸?shù)哪康?，y=φx，φ是一個(gè)M×N(M?N)的隨機(jī)矩陣.Sink節(jié)點(diǎn)收集到測(cè)量值y后，可以通過求解一個(gè)l1-范數(shù)優(yōu)化問題或者如OMP[10]的啟發(fā)式算法就能重構(gòu)原始數(shù)據(jù)信號(hào)x.

在基于樹的數(shù)據(jù)收集方法中，距離Sink節(jié)點(diǎn)遠(yuǎn)的葉子節(jié)點(diǎn)需要傳遞較少的數(shù)據(jù)包，而距離Sink節(jié)點(diǎn)近的節(jié)點(diǎn)需要傳遞較多的數(shù)據(jù)包.然而，在采用CS對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行處理后，每個(gè)節(jié)點(diǎn)需要傳遞M個(gè)數(shù)據(jù)包，也就是說N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中需要傳遞M×N個(gè)數(shù)據(jù)包，這仍然是一個(gè)很大的數(shù)值.文獻(xiàn)[6,8]提出了混合式壓縮感知方法，距離Sink節(jié)點(diǎn)遠(yuǎn)的葉子節(jié)點(diǎn)傳遞原始數(shù)據(jù)，而距離Sink節(jié)點(diǎn)近的節(jié)點(diǎn)使用壓縮感知技術(shù)進(jìn)行數(shù)據(jù)壓縮.以上方法都是將CS用在路由樹中，分簇式結(jié)構(gòu)相比于樹型結(jié)構(gòu)而言具有魯棒性強(qiáng)與網(wǎng)絡(luò)負(fù)載均衡等優(yōu)勢(shì)[11-12].魯棒性更強(qiáng)是因?yàn)榧词勾貎?nèi)節(jié)點(diǎn)由于物理因素意外死亡，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響不大.均衡負(fù)載是因?yàn)榉执鼐W(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量能夠均衡，可以緩解樹型網(wǎng)絡(luò)中的瓶頸效應(yīng).但是，上述方法都忽視了網(wǎng)絡(luò)的地理位置與節(jié)點(diǎn)的分布狀況.研究表明：在傳感器網(wǎng)絡(luò)中，根據(jù)節(jié)點(diǎn)的分布狀況設(shè)計(jì)收集算法可以減少數(shù)據(jù)的傳輸量[12].文獻(xiàn)[13]提出了一種分簇式傳感網(wǎng)絡(luò)中采用混合CS技術(shù)進(jìn)行數(shù)據(jù)收集的方法，簇內(nèi)不使用CS進(jìn)行數(shù)據(jù)傳遞，而在簇間使用CS進(jìn)行數(shù)據(jù)傳遞.通過最小化簇內(nèi)傳輸消耗有效地減少了數(shù)據(jù)傳輸量，但該方法未考慮大規(guī)模網(wǎng)絡(luò)中靠近簇頭的節(jié)點(diǎn)以及連通度大的節(jié)點(diǎn)的巨大負(fù)荷，網(wǎng)絡(luò)負(fù)載不均衡，同時(shí)忽視了簇間傳輸跳數(shù)對(duì)數(shù)據(jù)傳輸量造成的影響.

分簇式網(wǎng)絡(luò)中，由于簇頭節(jié)點(diǎn)需要融合和轉(zhuǎn)發(fā)大量數(shù)據(jù)，故減少用于簇間傳輸?shù)耐負(fù)涮鴶?shù)與數(shù)據(jù)量對(duì)延長(zhǎng)網(wǎng)絡(luò)的生命周期具有重要的影響.本文通過考慮已確定的簇頭節(jié)點(diǎn)到未確定的候選簇頭節(jié)點(diǎn)間的距離，依次選擇距離父簇頭節(jié)點(diǎn)最短的候選簇頭節(jié)點(diǎn)為子簇頭節(jié)點(diǎn)，以此優(yōu)化網(wǎng)絡(luò)中的簇頭選擇機(jī)制，在犧牲少量簇內(nèi)傳輸量的前提下迅速降低簇間的傳輸量.貪婪構(gòu)建1棵以Sink節(jié)點(diǎn)為根節(jié)點(diǎn)并連接所有簇頭節(jié)點(diǎn)的數(shù)據(jù)傳輸樹，將數(shù)據(jù)傳遞到Sink節(jié)點(diǎn).對(duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)以及用于簇間傳輸?shù)墓?jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸，達(dá)到均衡網(wǎng)絡(luò)負(fù)載和減少數(shù)據(jù)傳輸量的目的.仿真實(shí)驗(yàn)表明，與多種基于樹的數(shù)據(jù)收集算法以及分簇式混合CS數(shù)據(jù)收集算法[13]相比，本文提出的算法能有效地減少網(wǎng)絡(luò)的數(shù)據(jù)傳輸量.相比傳統(tǒng)的基于樹的數(shù)據(jù)收集算法，文獻(xiàn)[8,13]以及未使用CS技術(shù)進(jìn)行數(shù)據(jù)收集的分簇式網(wǎng)絡(luò)均能有效地均衡網(wǎng)絡(luò)負(fù)載.

1 模型建立與理論分析

1.1 模型建立與示例

假設(shè):1) 網(wǎng)絡(luò)中所有節(jié)點(diǎn)獨(dú)立、一致性地分布在傳感區(qū)域；2) 網(wǎng)絡(luò)中所有節(jié)點(diǎn)具有相同的初始能量與傳輸速率；3) 網(wǎng)絡(luò)中所有節(jié)點(diǎn)能通過GPS或者其他定位技術(shù)[14-15]感知到自己的位置信息.

Fig. 1 Data collection diagram in cluster structure based on hybrid CS圖1 簇結(jié)構(gòu)中基于混合CS數(shù)據(jù)收集示例

首先通過簇頭選舉算法得到簇頭節(jié)點(diǎn)，然后各普通節(jié)點(diǎn)選擇加入離自己位置最近的簇頭節(jié)點(diǎn)，將網(wǎng)絡(luò)劃分為若干簇，各普通節(jié)點(diǎn)通過最短路徑算法將數(shù)據(jù)傳遞給簇頭節(jié)點(diǎn)，得到簇內(nèi)數(shù)據(jù)收集模型.各簇頭節(jié)點(diǎn)對(duì)簇內(nèi)數(shù)據(jù)壓縮采樣，進(jìn)而通過貪婪選擇構(gòu)建的路由樹將數(shù)據(jù)傳遞給Sink節(jié)點(diǎn)，得到簇間數(shù)據(jù)收集模型.圖1是基于混合CS的分簇?cái)?shù)據(jù)收集示例圖.簇頭節(jié)點(diǎn)根據(jù)各簇內(nèi)節(jié)點(diǎn)vj由偽隨機(jī)數(shù)字生成器[5]生成的測(cè)量矩陣φi j，對(duì)簇內(nèi)的數(shù)據(jù)進(jìn)行壓縮感知采樣.網(wǎng)絡(luò)中第i個(gè)簇頭節(jié)點(diǎn)CHi通過產(chǎn)生的子矩陣φHi對(duì)簇內(nèi)收集到的原始數(shù)據(jù)xHi進(jìn)行測(cè)量，得到觀測(cè)值φHixHi.簇頭節(jié)點(diǎn)CHi經(jīng)過壓縮測(cè)量后得到M個(gè)觀測(cè)值信號(hào)，M由節(jié)點(diǎn)數(shù)目N以及原始數(shù)據(jù)的稀疏度決定[5].各簇頭節(jié)點(diǎn)經(jīng)貪婪選擇構(gòu)建的數(shù)據(jù)傳輸樹向Sink節(jié)點(diǎn)傳遞數(shù)據(jù).

Sink節(jié)點(diǎn)接收到的測(cè)量值y是所有簇頭節(jié)點(diǎn)經(jīng)壓縮感知采樣后的數(shù)據(jù)之和，如式(1)所示.在每一次傳輸時(shí)，簇頭節(jié)點(diǎn)融合自身數(shù)據(jù)與子簇頭節(jié)點(diǎn)的數(shù)據(jù)，然后經(jīng)貪婪路由樹將觀測(cè)值傳遞給Sink節(jié)點(diǎn).Sink節(jié)點(diǎn)根據(jù)收到的觀測(cè)值y以及測(cè)量矩陣φ可以重構(gòu)出原始信號(hào)x.

(1)

1.2 理論分析與證明

本文的分簇式混合CS數(shù)據(jù)收集方法包括2個(gè)方面的數(shù)據(jù)傳輸：簇內(nèi)節(jié)點(diǎn)經(jīng)過最短路徑算法將數(shù)據(jù)傳遞給簇頭節(jié)點(diǎn)，簇間經(jīng)過貪婪路由傳輸樹將數(shù)據(jù)傳遞給Sink節(jié)點(diǎn).對(duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)以及用于簇間傳輸?shù)墓?jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸.網(wǎng)絡(luò)中任意節(jié)點(diǎn)的通信量為自己的通信量與其所有子節(jié)點(diǎn)通信量的和.節(jié)點(diǎn)的數(shù)據(jù)傳輸跳數(shù)越多，此節(jié)點(diǎn)的數(shù)據(jù)在各級(jí)父節(jié)點(diǎn)中會(huì)被多次傳輸，加大網(wǎng)絡(luò)的通信量.因此，為了節(jié)約網(wǎng)絡(luò)中節(jié)點(diǎn)的能量，所設(shè)計(jì)的數(shù)據(jù)收集方法需盡可能減少網(wǎng)絡(luò)中傳輸量，即盡可能減少數(shù)據(jù)包傳輸?shù)目偺鴶?shù).

1.2.1 網(wǎng)絡(luò)的分簇?cái)?shù)量

在分簇式混合CS數(shù)據(jù)收集方法中，網(wǎng)絡(luò)中劃分簇的數(shù)量對(duì)網(wǎng)絡(luò)傳輸量有重要影響.當(dāng)網(wǎng)絡(luò)中分簇?cái)?shù)量過少時(shí)，簇內(nèi)傳輸量將會(huì)急劇增加.當(dāng)網(wǎng)絡(luò)中分簇?cái)?shù)量過多時(shí)，簇頭節(jié)點(diǎn)數(shù)目會(huì)增加，簇間傳輸量勢(shì)必增加.因此在分簇式混合CS數(shù)據(jù)采集方法中存在最優(yōu)分簇?cái)?shù)量使得網(wǎng)絡(luò)傳輸量最小.文獻(xiàn)[13]對(duì)網(wǎng)絡(luò)中最優(yōu)分簇?cái)?shù)量做了詳細(xì)的理論分析與推導(dǎo)，本文不再贅述.網(wǎng)絡(luò)中最優(yōu)分簇?cái)?shù)量：

(2)

1.2.2 網(wǎng)絡(luò)的簇內(nèi)傳輸

Fig. 2 Intra-cluster transmission diagram圖2 簇內(nèi)傳輸示意圖

Fig. 3 Inter-cluster transmission diagram圖3 簇間傳輸示意圖

網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)位于網(wǎng)絡(luò)中央且靠近Sink節(jié)點(diǎn)的位置，這樣能使得簇內(nèi)節(jié)點(diǎn)傳輸數(shù)據(jù)到簇頭節(jié)點(diǎn)的平均傳輸跳數(shù)最小.與簇頭節(jié)點(diǎn)在同一網(wǎng)格內(nèi)的節(jié)點(diǎn)需經(jīng)1跳將數(shù)據(jù)傳輸?shù)酱仡^節(jié)點(diǎn)，第h層的節(jié)點(diǎn)最多需經(jīng)過h跳將數(shù)據(jù)傳遞給簇頭節(jié)點(diǎn)，最少需經(jīng)過h-1跳將數(shù)據(jù)傳遞給簇頭節(jié)點(diǎn)，第h層網(wǎng)格數(shù)為8(h-1),h≥2.假定網(wǎng)絡(luò)中節(jié)點(diǎn)的分布密度為λ，則單個(gè)網(wǎng)格內(nèi)節(jié)點(diǎn)數(shù)目為λa2.單個(gè)簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)傳遞到簇頭節(jié)點(diǎn)的數(shù)據(jù)傳輸跳數(shù)為

(3)

由于

(4)

故單個(gè)簇內(nèi)感知節(jié)點(diǎn)向簇頭節(jié)點(diǎn)傳遞數(shù)據(jù)的跳數(shù)為

(5)

故網(wǎng)絡(luò)的簇內(nèi)通信傳輸總跳數(shù)的上界值為

(6)

同理可知網(wǎng)絡(luò)的簇內(nèi)通信傳輸總跳數(shù)的下界值為

(7)

1.2.3 網(wǎng)絡(luò)的簇間傳輸

(8)

網(wǎng)絡(luò)的總傳輸跳數(shù)理論值為簇內(nèi)傳輸跳數(shù)與簇間傳輸跳數(shù)之和.網(wǎng)絡(luò)傳輸總跳數(shù)的上界值為

Tub=Tinter+Tub_intra=

(9)

網(wǎng)絡(luò)傳輸總跳數(shù)的下界值為

Tlb=Tinter+Tlb_intra=

(10)

2 算法設(shè)計(jì)

對(duì)于給定的網(wǎng)絡(luò)用圖G=(V,E)表示，其中,V為Sink節(jié)點(diǎn)與N個(gè)傳感器節(jié)點(diǎn)組成的集合，當(dāng)V中節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離在節(jié)點(diǎn)傳輸半徑內(nèi)時(shí),則這2個(gè)節(jié)點(diǎn)間存在邊ei j，E為所有邊ei j組成的集合.

2.1 簇頭選舉算法

算法1. 簇頭選舉算法.

步驟1. 根據(jù)得到的網(wǎng)絡(luò)分簇?cái)?shù)量最優(yōu)值c，隨機(jī)選擇網(wǎng)絡(luò)中c個(gè)節(jié)點(diǎn)為臨時(shí)簇頭；

步驟3. 重復(fù)步驟2直到網(wǎng)絡(luò)拓?fù)洳辉侔l(fā)生變化，得到c個(gè)質(zhì)心位置；

步驟4. 各臨時(shí)簇選擇距離質(zhì)心位置最近的tcandidate個(gè)節(jié)點(diǎn)為候選簇頭；

步驟5. 計(jì)算各臨時(shí)簇中候選簇頭與Sink節(jié)點(diǎn)的距離，選擇臨時(shí)簇中距離Sink節(jié)點(diǎn)最近的候選簇頭節(jié)點(diǎn)為簇頭，確定第1個(gè)簇；

步驟6. 計(jì)算剩余臨時(shí)簇中候選簇頭節(jié)點(diǎn)與上一簇頭節(jié)點(diǎn)的距離，選擇剩余臨時(shí)簇中距離上一簇頭節(jié)點(diǎn)最近的候選簇頭節(jié)點(diǎn)為簇頭；

步驟7. 重復(fù)步驟6得到c個(gè)簇頭節(jié)點(diǎn).

網(wǎng)絡(luò)由算法1選擇c個(gè)簇頭后,其他節(jié)點(diǎn)選擇加入距離自己最近的簇頭節(jié)點(diǎn)中,網(wǎng)絡(luò)劃分成c個(gè)簇.簇內(nèi)普通節(jié)點(diǎn)只需將數(shù)據(jù)傳遞給大致位于簇中心的簇頭節(jié)點(diǎn)處，而簇頭節(jié)點(diǎn)需將收集到的數(shù)據(jù)經(jīng)過多跳將數(shù)據(jù)傳遞給Sink節(jié)點(diǎn).選定的c個(gè)簇頭節(jié)點(diǎn)均靠近簇質(zhì)心的位置，算法1在盡量不增加簇內(nèi)傳輸?shù)那疤嵯拢沟孟噜彺仡^節(jié)點(diǎn)的距離變小且簇頭節(jié)點(diǎn)盡量靠近Sink節(jié)點(diǎn)，這能有效減少網(wǎng)絡(luò)的數(shù)據(jù)傳輸跳數(shù).

2.2 貪婪路由樹構(gòu)建算法

用U表示由算法1得到的所有簇頭節(jié)點(diǎn)與Sink節(jié)點(diǎn)所組成的集合，Uin表示已經(jīng)加入到路由樹中的簇頭節(jié)點(diǎn)集合，則U-Uin為還未加入到樹中的簇頭節(jié)點(diǎn).

算法2. 貪婪路由樹構(gòu)建算法.

步驟1. 初始化：Uin=VSink.

步驟2. 計(jì)算集合U-Uin中的各節(jié)點(diǎn)與集合Uin中各節(jié)點(diǎn)的距離，選擇距離最短的節(jié)點(diǎn)加入到路由樹中；

步驟3. 更新集合Uin；

步驟4. 重復(fù)步驟2與步驟3直到Uin=U.

算法2通過貪婪選擇構(gòu)建了1棵以Sink節(jié)點(diǎn)為根節(jié)點(diǎn)的數(shù)據(jù)傳輸樹，各子簇頭節(jié)點(diǎn)只需將數(shù)據(jù)傳遞給距離自己最近的父簇頭節(jié)點(diǎn)，任意2個(gè)簇頭間的傳輸跳數(shù)都是最小的，保證Sink節(jié)點(diǎn)在收到觀測(cè)值y后能根據(jù)測(cè)量矩陣φ重構(gòu)出原始信號(hào)x.

3 仿真與分析

3.1 仿真參數(shù)與環(huán)境說明

本文用Matlab仿真工具對(duì)提出的分簇式混合CS數(shù)據(jù)收集方法與其他數(shù)據(jù)收集方法進(jìn)行了仿真分析與對(duì)比.Clustering without CS與本文算法具有相同的分簇結(jié)構(gòu)但未使用CS進(jìn)行數(shù)據(jù)壓縮；Short path tree(SPT) without CS中Sink節(jié)點(diǎn)通過構(gòu)建的最短路徑樹收集感知節(jié)點(diǎn)的數(shù)據(jù)；SPT with Hybrid CS中Sink節(jié)點(diǎn)通過構(gòu)建的最短路徑樹收集感知節(jié)點(diǎn)的數(shù)據(jù)，樹中節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)(包括自己)大于觀測(cè)值門限時(shí)，節(jié)點(diǎn)使用CS對(duì)數(shù)據(jù)進(jìn)行壓縮采樣；文獻(xiàn)[8]提出的Optimal Tree with Hybrid CS使用混合CS通過對(duì)節(jié)點(diǎn)構(gòu)建最小生成樹與最短路徑樹，并依次貪婪選擇確定加入數(shù)據(jù)傳輸樹的節(jié)點(diǎn)構(gòu)建了1棵能耗最小傳輸樹；Clustering with Hybrid CS是文獻(xiàn)[13]提出的分簇式混合CS數(shù)據(jù)收集方案，簇內(nèi)節(jié)點(diǎn)通過最短路徑將數(shù)據(jù)傳遞給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行CS采樣后通過構(gòu)建1棵連接所有簇頭節(jié)點(diǎn)與Sink節(jié)點(diǎn)的骨干樹將觀測(cè)值傳遞給Sink節(jié)點(diǎn).

Fig. 4 The number of transmissions of different data collection methods圖4 不同數(shù)據(jù)收集方法傳輸量圖

仿真中測(cè)量4個(gè)指標(biāo)：

1) 數(shù)據(jù)總傳輸量.1次采集周期內(nèi)Sink節(jié)點(diǎn)收到的數(shù)據(jù)量.

2) 傳輸量減少比.本文算法相比于其他算法減少的傳輸量比值.對(duì)比于Clustering without CS的傳輸量減少比為Clustering without CS與本文算法在同一周期內(nèi)數(shù)據(jù)傳輸量的差值除以Clustering without CS在1個(gè)周期內(nèi)的傳輸量.

3) 簇內(nèi)與簇間負(fù)載均衡評(píng)價(jià)指標(biāo)[16].簇內(nèi)成員數(shù)量的平均偏差和簇頭到其他成員節(jié)點(diǎn)的平均距離的平均偏差.簇間負(fù)載均衡評(píng)價(jià)指標(biāo)，相鄰簇頭之間的平均距離和相鄰簇頭之間的距離平均偏差.

4) 網(wǎng)絡(luò)中1次采集周期內(nèi)各節(jié)點(diǎn)傳輸量的標(biāo)準(zhǔn)差以及簇內(nèi)節(jié)點(diǎn)傳輸量的平均標(biāo)準(zhǔn)差.

3.2 數(shù)據(jù)總傳輸量仿真與分析

圖4(a)為本文算法與其他5種數(shù)據(jù)收集算法在壓縮比率為5的條件下數(shù)據(jù)傳輸量的仿真結(jié)果.圖4(b)是壓縮比率為10時(shí)各數(shù)據(jù)收集算法的數(shù)據(jù)傳輸量對(duì)比結(jié)果.

從圖4可知，本文算法相比于Clustering without CS和SPT without CS而言，大大降低了傳輸量，這是因?yàn)楸疚乃惴▽?duì)網(wǎng)絡(luò)中傳輸量超過壓縮感知門限值的節(jié)點(diǎn)進(jìn)行了壓縮采樣，只需要傳輸M個(gè)觀測(cè)值信號(hào).本文算法相比于SPT with Hybrid CS在數(shù)據(jù)傳輸量上也有優(yōu)勢(shì)，這是因?yàn)樵诜执亟Y(jié)構(gòu)中，感知節(jié)點(diǎn)只需將數(shù)據(jù)傳遞到大致位于簇中心的簇頭節(jié)點(diǎn)，而SPT with Hybrid CS中感知節(jié)點(diǎn)將數(shù)據(jù)傳遞到距離Sink節(jié)點(diǎn)近的父節(jié)點(diǎn)上，這會(huì)大大增加傳輸跳數(shù)，增加網(wǎng)絡(luò)中的數(shù)據(jù)傳輸量.本文算法相比于Clustering with Hybrid CS而言有效降低了數(shù)據(jù)傳輸量，這是因?yàn)楸疚乃惴ㄒ罁?jù)已確定的簇頭節(jié)點(diǎn)到未確定的候選簇頭節(jié)點(diǎn)的距離依次確定簇頭，在盡量少增加簇內(nèi)傳輸量的前提下減少數(shù)據(jù)傳輸跳數(shù)，降低簇間傳輸量.對(duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)以及用于簇間傳輸?shù)墓?jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸，減少數(shù)據(jù)傳輸量.本文算法與文獻(xiàn)[8]提出的Optimal Tree with Hybrid CS相比網(wǎng)絡(luò)傳輸量略有減少，但是基于分簇結(jié)構(gòu)的網(wǎng)絡(luò)具有更好的容錯(cuò)性，在基于樹的網(wǎng)絡(luò)結(jié)構(gòu)中當(dāng)樹中的某些節(jié)點(diǎn)能量耗盡而死亡時(shí)，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)就會(huì)發(fā)生變化，導(dǎo)致傳輸樹不再高效.

3.3 傳輸量減少比仿真與分析

圖5(a)為本文算法與其他4種數(shù)據(jù)收集算法在壓縮比率為5的條件下數(shù)據(jù)傳輸量減少比的仿真結(jié)果.圖5(b)為本文算法與其他4種數(shù)據(jù)收集算法在壓縮比率為10的條件下數(shù)據(jù)傳輸量減少比的仿真結(jié)果.

Fig. 5 Reduction ratio of transmissions compared with other data collection methods圖5 對(duì)比其他算法傳輸量減少比

由圖5(b)可知，當(dāng)壓縮比率為10時(shí)，本文算法相比Clustering without CS傳輸量減少了大約75%，相比SPT without CS傳輸量減少了大約65%，相比于SPT with Hybrid CS傳輸量減少了大約35%，相比于文獻(xiàn)[13]提出的Clustering with Hybrid CS傳輸量減少了大約20%.顯然減少比率并未隨著節(jié)點(diǎn)數(shù)目的增大而減小，這說明本文算法具有良好的擴(kuò)展性.由圖5(a)可知，當(dāng)壓縮比率為5時(shí)，相比于Clustering without CS和SPT without CS壓縮比率為10的情況，傳輸量減少比率大約只降低了5%～10%，這說明本文算法即使在采樣信號(hào)較多的情況下也能有效減少網(wǎng)絡(luò)的傳輸量.相比于SPT with Hybrid CS和Clustering with Hybrid CS壓縮比率為10的情況，傳輸量減少比率降低了2%～5%，這是因?yàn)楸疚乃惴ㄖ販p少簇間傳輸量，當(dāng)壓縮比率降低時(shí)，相比于SPT with Hybrid CS和Clustering with Hybrid CS減少的網(wǎng)絡(luò)總傳輸量也會(huì)降低，故傳輸量減少比也會(huì)降低.

3.4 負(fù)載均衡仿真與分析

本節(jié)對(duì)本文算法與其他算法在網(wǎng)絡(luò)負(fù)載均衡方面進(jìn)行了對(duì)比分析.圖6為壓縮比率為10的條件下本文算法與其他5種數(shù)據(jù)收集算法的各個(gè)節(jié)點(diǎn)傳輸量的標(biāo)準(zhǔn)差圖.

Fig. 6 The standard deviation of nodes transmissions when the compress ratio equals 10圖6 壓縮比率為10時(shí)，節(jié)點(diǎn)傳輸量標(biāo)準(zhǔn)差圖

Clustering without CS和SPT without CS由于未使用CS對(duì)傳輸量超過壓縮感知門限值的節(jié)點(diǎn)進(jìn)行壓縮測(cè)量，故骨干樹的節(jié)點(diǎn)傳輸量很大，而葉子節(jié)點(diǎn)傳輸量很少，故節(jié)點(diǎn)間傳輸量的差異很大，即負(fù)載不均衡.因此，簇形網(wǎng)絡(luò)相比于樹型網(wǎng)絡(luò)，具有更好的負(fù)載均衡效果.SPT with Hybrid CS和Optimal Tree with Hybrid CS由于采用樹型拓?fù)浣Y(jié)構(gòu)，導(dǎo)致葉子節(jié)點(diǎn)與融合節(jié)點(diǎn)傳輸量差異很大.相比于Clustering with Hybrid CS，本文算法負(fù)載更均衡，這是因?yàn)閷?duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)以及用于簇間傳輸?shù)墓?jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸.

簇內(nèi)通信消耗的平衡是影響負(fù)載均衡的重要因素之一.簇內(nèi)通信消耗[16]與簇內(nèi)成員節(jié)點(diǎn)數(shù)量、簇頭到其成員之間的距離成正比，因此驗(yàn)證本文算法簇內(nèi)負(fù)載均衡性能主要考慮簇內(nèi)成員數(shù)量平均偏差I(lǐng)ntra-memdevi和簇頭到其成員節(jié)點(diǎn)的平均距離的平均偏差I(lǐng)ntra-disdevi具體結(jié)果如表1所示：

Table 1 Load Balance Performance of Intra-Cluster Transmission

表1中的Intra-memaver表示簇內(nèi)平均成員節(jié)點(diǎn)的數(shù)量，Intra-disaver表示簇頭到其成員節(jié)點(diǎn)的平均距離，2個(gè)平均變量主要反映簇內(nèi)通信消耗的平均負(fù)載，平均負(fù)載越小，則網(wǎng)絡(luò)能耗越小.偏差變量主要反映不同簇之間的差異程度，偏差越小，差異也就越小，負(fù)載也就越均衡.從表1可知.本文算法對(duì)比于文獻(xiàn)[13]而言，簇內(nèi)負(fù)載均衡指標(biāo)偏差以及平均差異略差于文獻(xiàn)[13].這是由于本文算法主要考慮在應(yīng)用CS的背景下盡量降低簇間傳輸.

表2為簇內(nèi)節(jié)點(diǎn)傳輸量的平均標(biāo)準(zhǔn)差Std-intraaver，反映簇內(nèi)節(jié)點(diǎn)傳輸量的平均差異，平均標(biāo)準(zhǔn)差越小，證明簇內(nèi)節(jié)點(diǎn)負(fù)載越均衡.

Table 2 Average Standard Deviation of Intra-Cluster Nodes Transmissions

由表2可知，本文算法的簇內(nèi)節(jié)點(diǎn)傳輸量的平均標(biāo)準(zhǔn)差在400～1 200個(gè)節(jié)點(diǎn)下都低于文獻(xiàn)[13]，證明本文算法對(duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值的節(jié)點(diǎn)進(jìn)行壓縮測(cè)量，減少了簇內(nèi)節(jié)點(diǎn)間傳輸量的差異，均衡了簇內(nèi)負(fù)載.

簇間的通信消耗均衡是衡量負(fù)載均衡的另一個(gè)重要因素，對(duì)相鄰簇頭之間的平均距離以及平均偏差進(jìn)行測(cè)試，具體結(jié)果如表3所示：

Table 3 Load Balance Performance of Inter-Cluster Transmission

相鄰簇頭之間的平均距離Inter-disaver反映簇頭之間的通信消耗，而相鄰簇頭之間的距離平均偏差I(lǐng)nter-disdevi則反映通信消耗的差異程度.由表3可知，本文算法在平均距離和平均偏差上都比文獻(xiàn)[13]要低，這是因?yàn)榇仡^節(jié)點(diǎn)的選擇考慮已確定的簇頭與未確定的候選簇頭節(jié)點(diǎn)間的距離，依次選擇距離父簇頭節(jié)點(diǎn)最短的候選簇頭節(jié)點(diǎn)為子簇頭節(jié)點(diǎn).在貪婪構(gòu)建簇間傳輸樹時(shí)能有效降低簇間傳輸距離，降低通信消耗，均衡負(fù)載.

4 總 結(jié)

本文在分簇式傳感器網(wǎng)絡(luò)提出了一種基于混合CS的數(shù)據(jù)收集方法.為了降低網(wǎng)絡(luò)中數(shù)據(jù)傳輸量以及均衡網(wǎng)絡(luò)負(fù)載，優(yōu)化了網(wǎng)絡(luò)中的簇頭選擇機(jī)制.1)確定距離Sink最近的候選簇頭節(jié)點(diǎn)為首個(gè)簇頭,通過考慮已確定的簇頭節(jié)點(diǎn)到未確定的候選簇頭節(jié)點(diǎn)的距離，依次選擇距離父簇頭節(jié)點(diǎn)最短的候選簇頭節(jié)點(diǎn)為子簇頭節(jié)點(diǎn)，將網(wǎng)絡(luò)劃分成簇；2)貪婪構(gòu)建一棵以Sink節(jié)點(diǎn)為根節(jié)點(diǎn)并連接所有簇頭節(jié)點(diǎn)的數(shù)據(jù)傳輸樹；3)通過數(shù)據(jù)傳輸樹將數(shù)據(jù)傳遞到Sink節(jié)點(diǎn)，并對(duì)簇內(nèi)數(shù)據(jù)傳輸量高于門限值以及用于簇間傳輸?shù)墓?jié)點(diǎn)使用CS壓縮數(shù)據(jù)傳輸，達(dá)到均衡網(wǎng)絡(luò)負(fù)載和減少數(shù)據(jù)傳輸量的目的.實(shí)驗(yàn)結(jié)果表明：本文提出方法比Clustering without CS，SPT without CS，SPT with Hybrid CS，Clustering with Hybrid CS都能大幅減少數(shù)據(jù)傳輸量，且在網(wǎng)絡(luò)負(fù)載均衡方面性能更佳.

[1]Xia Na, Xu Shun’an, Jiang Jianguo. Energy-consumption analysis and testing of sensors in wireless sensor networks [J]. Journal of Computer Research and Development, 2010, 47(Suppl1): 296-301 (in Chinese)(夏娜, 徐順安, 蔣建國(guó). WSNs中節(jié)點(diǎn)能耗分析與測(cè)試[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(增刊1): 296-301)

[2]Dai Qionghai, Fu Changjun, Ji Xiangyang. Research on compressed sensing [J]. Chinese Journal of Computers, 2011, 34(3): 425-434 (in Chinese)(戴瓊海, 付長(zhǎng)軍, 季向陽. 壓縮感知研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 3(34): 425-434)

[3]Jiao Licheng, Yang Shuyuan, Liu Fang, et al. Development and prospect of compressive sensing[J]. Acta Electronica Sinica, 2011, 39(7): 1651-1662 (in Chinese)(焦李成, 楊淑媛, 劉芳, 等. 壓縮感知回顧與展望[J]. 電子學(xué)報(bào), 2011, 39(7): 1651-1662)

[4]Donoho D L. Compressed sensing[J]. IEEE Trans on Information Theory, 2006, 52(4): 1289-1306

[5]Haupt J, Bajwa W U, Rabbat M, et al. Compressed sensing for networked data[J]. IEEE Signal Processing Magazine, 2008, 25(2): 92-101

[6]Luo Chong, Wu Feng, Sun Jun, et al. Compressive data gathering for large-scale wireless sensor networks[C]Proc of the 15th Annual Int Conf on Mobile Computing and Networking. New York: ACM, 2009: 145-156

[7]Luo Chong, Wu Feng, Sun Jun, et al. Efficient measurement generation and pervasive sparsity for compressive data gathering[J]. IEEE Trans on Wireless Communications, 2010, 9(12): 3728-3738

[8]Xiang Liu, Luo Jun, Vasilakos A. Compressed data aggregation for energy efficient wireless sensor networks[C]Proc of the 8th Annual Communications Society Conf on Sensor, Mesh and ad Hoc Communications and Networks (SECON).Piscataway, NJ: IEEE, 2011: 46-54

[9]Wang Jin, Tang Shaojie, Yin Baocai, et al. Data gathering in wireless sensor networks through intelligent compressive sensing[C]Proc of IEEE INFOCOM 2012. Piscataway, NJ: IEEE, 2012: 603-611

[10]Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Trans on Information Theory, 2007, 53(12): 4655-4666

[11]Youssef M A, Youssef A, Younis M F. Overlapping multihop clustering for wireless sensor networks[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(12): 1844-1856

[12]Soro S, Heinzelman W B. Cluster head election techniques for coverage preservation in wireless sensor networks[J]. Ad Hoc Networks, 2009, 7(5): 955-972

[13]Xie Ruitao, Jia Xiaohua. Transmission-efficient clustering method for wireless sensor networks using compressive sensing[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(3): 806-815

[14]Xiao Fu, Sha Chaoheng, Chen Lei, et al. Localization algorithm for wireless sensor networks via norm regularized matrix completion [J]. Journal of Computer Research and Development, 2016, 53(1): 216-227 (in Chinese)(肖甫, 沙朝恒, 陳蕾, 等. 基于范數(shù)正則化矩陣補(bǔ)全的無線傳感網(wǎng)定位算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(1): 216-227)

[15]Xiao Fu, Sha Chaoheng, Chen Lei, et al. Noise-tolerant localization from incomplete range measurements for wireless sensor networks[C]Proc of IEEE Conf on Computer Communications (INFOCOM 2015). Piscataway, NJ: IEEE, 2015: 2794-2802

[16]Su Jinshu,Guo Wenzhong,Yu Chaolong, et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network [J]. Chinese Journal of Computers, 2014, 37(2): 445-456 (in Chinese)(蘇金樹, 郭文忠, 余朝龍, 等. 負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(2): 445-456)

Li Zhetao, born in 1980. PhD of Hunan University. Associate professor and master supervisor in the College of Information Engineering, Xiangtan University. Member of CCF. His main research interests include wireless sensor networks and compressive sensing.

Zang Lang, born in 1993. Master candidate of the Xiangtan University of the China. Student member of CCF. His main research interests focus on wireless sensor networks and compressive sensing.

Tian Shujuan, born in 1982. PhD candidate at the School of Information Science and Engineering, Central South University. Lecturer at the College of Information Engineering, Xiangtan University. Her main research interests focus on compressive sensing, signal processing and wireless sensor networks.

Li Renfa, born in 1957. Professor and PhD supervisor in the School of Information Science and Engineering, Hunan University. His main research interests include networks technology and distributed computing.

Data Collection Method in Clustering Network Based on Hybrid Compressive Sensing

Li Zhetao1,2,3, Zang Lang1,3, Tian Shujuan1,3, and Li Renfa4

1(CollegeofInformationEngineering,XiangtanUniversity,Xiangtan,Hunan411105)2(JiangsuHighTechnologyResearchKeyLaboratoryforWirelessSensorNetworks(NanjingUniversityofPostsandTelecommnications),Nanjing210003)3(KeyLaboratoryofIntelligentComputing&InformationProcessing(XiangtanUniversity),MinistryofEducation,Xiangtan,Hunan411105)4(SchoolofInformationScience&Engineering,HunanUniversity,Changsha410082)

In order to reduce the number of transmissions and balance the network load in wireless sensor network, this paper presents a data collection method by using hybrid compressive sensing (cs) in clustering network. Firstly we choose some nodes that are close to the temporary cluster-centroid as the candidate cluster head(CH), secondly determine the CH nodes on the basis of the distance of the candidate nodes to determined CH orderly. Then the common sensor nodes join their nearest cluster. Lastly we build a data transmission tree root of sink node that connects to all CHs greedy. When the number of data transmissions is higher than the threshold, nodes transmit data by using CS. On scenarios of compressive ratio equals 10，the simulation results demonstrate that the number of transmissions for the proposed method is 75% and 65% less than that of Clustering without CS and SPT without CS, 35% and 20% less than that of SPT with Hybrid CS and Clustering with Hybrid CS; The standard deviation of nodes transmissions for the proposed method is 62% and 81% less than that of Clustering without CS and SPT without CS, 41% and 19% less than that of SPT with Hybrid CS and Clustering with Hybrid CS.

wireless sensor network (WSN); compressive sensing; data collection; clustering network; load balance

2015-09-28；

2016-04-11

國(guó)家自然科學(xué)基金項(xiàng)目(61379115，61110215，61372049,61602398);湖南省自然科學(xué)基金項(xiàng)目(2015JJ4047,12JJ9021,13JJ8006)；江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室開發(fā)課題(WSNLBKF201501)；湖南省重點(diǎn)學(xué)科建設(shè)基金項(xiàng)目 This work was supported by the National Natural Science Foundation of China (61379115, 61110215, 61372049, 61602398), the Natural Science Foundation of Hunan Province of China (2015JJ4047, 12JJ9021, 13JJ8006), the Key Laboratory of Jiangsu High Technology Research for Wireless Sensor Networks (WSNLBKF201501), and the Key Subjects Construction Foundation of Hunan Province.

田淑娟(sjtianwork@xtu.edu.cn)

TP393