基于分簇的無線多媒體傳感器網絡數據聚合方案研究

張軍強 王汝傳 黃海平

?

基于分簇的無線多媒體傳感器網絡數據聚合方案研究

張軍強①④王汝傳*①②③黃海平①②③

①(南京郵電大學計算機學院 南京 210003)②(江蘇省無線傳感網高技術研究重點實驗室 南京 210003)③(寬帶無線通信與傳感網技術教育部重點實驗室 南京 210003)④(南京工業大學信息學院 南京 210009)

該文提出了一種基于分簇的無線多媒體傳感器網絡(WMSNs)數據聚合方案(Cluster-based Data Aggregation Algorithm, CDAA)。利用新的分簇方法和數據聚合策略，CDAA可以有效延長網絡生命期。根據多媒體節點數據采集的方向性和節點剩余能耗，該文提出新的無線多媒體傳感器網絡的分簇方法，并基于該分簇方法進行網內多媒體數據聚合。仿真結果表明，該方法能夠有效減少冗余數據的傳送，與LEACH, PEGASIS等傳統WSNs路由協議和針對WMSNs的AntSensNet協議相比，在能耗均衡和節能方面表現出更好的性能。

無線多媒體傳感器網絡(WMSNs)；分簇；數據聚合；網絡生命期

1 引言

無線傳感器網絡(WSNs)中基于分簇的路由協議設計具有擴展性好，易于實現網內數據融合等特點。分簇路由協議將無線傳感器網絡劃分為若干簇，每個簇由一個簇頭節點和多個簇內成員組成，簇內成員負責采集數據，而簇頭節點負責管理簇內成員節點，并進行簇內節點信息的采集、融合及轉發。低功耗自適應分層算法(LEACH)[1]是無線傳感器網絡中經典的分層協議之一，其基本思想是周期性等概率得隨機選擇簇頭，使網絡中節點的能量消耗相對均衡，從而延長網絡生命期。但是，LEACH協議中簇頭是隨機選取的，難以保證簇頭在網絡中的均勻分布，且沒有考慮節點的剩余能量，也沒有對簇內數據進行聚合或融合。能量高效的數據采集協議(PEGASIS)[2]是一種典型的鏈狀結構的路由協議，根據節點的地理位置形成一條相鄰節點間距離最短的鏈。與LEACH協議相比，減少了在簇重構過程中所產生的開銷，降低了能量的消耗，提高了網絡的生存期。其缺點在于簇首節點失效會導致路由失敗，且成鏈算法要求知道其它節點位置，也增加了開銷。LEACH協議關注網絡的最后節點死亡時間(Last Node Dies, LND)，一些穩定選舉協議(Stable Election Protocol, SEP)關注初始節點死亡時間(First Node Dies, FND)，文獻[3]綜合最后節點死亡時間和初始節點死亡時間，提出了一種基于進化算法的節能路由協議，期望在網絡的穩定性和網絡的生命期間取得平衡。以地理位置信息為輔助的路由算法(GAF)[4]將整個區域劃分為若干個格(grid)，其大小須保證相鄰格子中任何一對節點可直接通信。在每個格子中只選擇一個節點作為當前活動節點，而其它節點則進入睡眠狀態。但GAF算法沒有考慮網絡覆蓋，并且要解決等價節點的確定等問題。考慮到無線多媒體傳感器網絡(WMSNs)具有傳輸數據量大，同具體應用相關的服務質量(QoS)保障要求等特點，傳統WSNs路由協議不一定適合WMSNs網絡。文獻[5]提出了支持QoS服務的基于蟻群算法的服務感知路由協議(ASAR)，針對不同類型的業務，選擇合適的路由以滿足相應的QoS要求，從而提高了網絡性能，其設計目標主要是適應網絡的動態變化及支持多參數的QoS路由。文獻[6]提出了基于地理位置的多路徑傳輸協議(TPGF)，可以找到多條路徑來傳輸數據，能夠避免網絡能耗不均的問題，提供了數據傳輸時繞開空洞的方法，找到時延最小的最短路徑。文獻[7]針對WMSNs網絡節能與QoS感知問題，提出了能量高效的多媒體路由協議(PEMuR)。PEMuR協議結合了能量感知的分層路由協議與智能化的數據包調度算法，實現了網絡的負載均衡，減少了視頻數據傳輸率。文獻[8]提出基于蟻群算法的多QoS路由保障協議(AntSensNet)，該算法對網絡進行分層后，通過建立多QoS參數的數學模型，利用蟻群算法找出目標函數值最大的路徑。AntSensNet可以滿足多類型QoS服務，提高網絡利用率，實現較好的網絡覆蓋。文獻[5-8]對于多類型QoS服務進行了研究，但未對網內數據聚合進行充分討論。

傳統WSNs節點感知模型主要為全向感知模型(isotropic sensing model)，即節點的感知范圍是一個以節點為圓心，感知距離為半徑的圓域[9]。有向感知模型是WMSNs網絡中一種典型的感知模型，如視頻傳感器、超聲波傳感器和紅外傳感器等，其感知能力局限于某個視角范圍(Field of View, FoV)。現有的路由協議分簇方法大多基于全向感知模型，針對WMSNs網絡的有向感知模型需要設計新的分簇方法。

對于WMSNs網絡，由于圖像或視頻的數據量大，且數據間往往具有一定的相關性，因此，在傳輸數據時，應首先進行網內數據處理，消除冗余信息，即進行數據聚合。數據聚合包括3方面問題，即聚合點的選擇，聚合時機的選擇和聚合策略[10]。文獻[11]提出了一種基于估計代價的數據聚合樹生成算法，在建立從事件區域源節點到sink節點數據聚合路徑時，中間節點使用估計代價來決定下一個聚合節點。文獻[12]在保證網絡覆蓋的前提下，通過激活網絡中盡可能少的節點來最小化覆蓋重疊區域，以減少WMSNs網絡的冗余數據。文獻[13]提出了一種基于分簇的無線傳感器網絡聚合策略，以節省能量消耗和延長網絡壽命。文獻[14]使用數據聚合的方法來減少數據的時空相關性。將數據聚合的決策置于網絡層和數據鏈路層之間，不需要修改網絡層或MAC層協議，從而減少了傳輸時延。文獻[15]為了減少WMSNs網絡中的數據傳輸，提出了節能的數據壓縮方法，以延長網絡生命期。文獻[16]提出了基于分簇的無線傳感器網絡數據匯聚傳送協議，通過均衡能耗的分簇方法及數據預測傳送機制，減少數據傳輸量。文獻[10-16]對網內數據聚合進行了研究，但未對WMSNs網絡中節點感知的方向性和同一監測區域內數據的相關性進行討論。

本文內容組織如下：第2節對網絡模型進行描述并提出問題；第3節給出基于分簇的數據聚合算法(CDAA)的分簇方法及數據聚合方法的詳細設計；第4節對算法性能進行分析與模擬驗證；最后總結全文。

2 網絡模型和問題描述

2.1 網絡模型

(1)節點采用有向感知模型，如圖1(a)所示。每個節點的感知區域是以節點為圓心，最大感知半徑為，感知視角為的扇形。

(2)網絡節點分布模型為均勻分布。

(3)節點獨立工作，即每個節點的感知范圍和感知任務不依賴其它節點。

(4)各節點可獲知其地理位置和感知方向信息，感知方向不可調。

(5)所有節點是同構的，具有相同的初始能量。

(7)任意節點的通信范圍覆蓋其所在監測區域及相鄰監測區域。

(8)各個節點周期性采集數據，并對采集到的數據進行處理以決定是否轉發該數據；簇頭收到各節點數據后根據需要來決定是否進行融合處理及轉發。

定義3 信息熵[11]：香農定義信息的數學期望為信息熵，即信源的平均信息量，定義式如式(2)。

相對信息熵表現了兩組概率分布之間的差異程度，對于兩組不同的概率分布和，計算其相對信息熵以及，這兩個值越小表明兩組概率分布越近似，即數據冗余則越大。當 時，兩組概率分布完全相等。

2.2 問題描述

如前所述，傳統的WSNs網絡分簇方法大多針對全向感知模型，而WMSNs是有向感知模型，多媒體節點數據采集的方向性強，有些傳感節點的物理位置雖然靠近，但采集數據可能相差很大，為了使后續處理中簇內的數據相關性強且聚合策略有效，這樣的節點并不適宜劃為同一分簇，需要設計新的分簇方法。

在WMSNs網絡中，設計分簇算法應考慮以下問題：

(1)使用分布式的分簇算法，以節省網絡能耗，提高網絡可擴展性。

(2)應考慮多媒體傳感節點的有向性，增強簇內感知數據的相關性。

(3)為了實現節點能耗的均衡，網絡中簇頭分布應盡可能均勻，否則會造成某些節點能量消耗過快，導致感知空洞。

(4)按照傳感器網絡的具體應用與QoS保障要求，根據感知數據在時間或空間上的相關性進行數據聚合與融合，減少冗余數據的傳送。

當前，大多數無線傳感器網絡的分簇算法針對全向感知模型，對多媒體傳感節點的有向性及感知數據的相關性涉及較少。根據多媒體傳感節點的有向性和感知數據的相關性以及節點的能耗均衡，本文提出了一種新的分簇算法，并以此為基礎提出了一種網內數據聚合方案。

3 基于分簇的WMSNs網絡數據聚合方案

3.1 計算節點覆蓋面積進行分簇

(1)整個監測區域內重點監測目標或區域的設置；每個虛擬監測區域應當包含一個或幾個重點監測目標或區域。

圖2 虛擬監測區域劃分

(2)節點的個數及位置分布情況；每個虛擬監測區域應當包含若干個節點。

(3)節點的有效傳感半徑；虛擬監測區域的個數設置與節點的有效傳感半徑成反比，節點的有效傳感半徑越大，虛擬監測區域的個數設置應當越少，反之亦然。

(4)節點的通信半徑；同一虛擬監測區域內任意兩個節點之間應可靠通信，相鄰虛擬監測區域內任意兩個節點之間應可靠通信。

圖3 節點覆蓋面積示意圖

3.2 簇頭選擇

在基于分簇的無線傳感器網絡中，簇頭的能耗遠大于一般節點，在簇頭選舉階段，應考慮節點的剩余能量，選舉剩余能量多的節點作為簇頭節點。

本算法采用與LEACH協議相同的能量衰減模型。根據文獻[1]可知，發送數據和接收數據的無線通信模型為

3.3 數據聚合方案

對于WMSNs網絡，由于圖像或視頻的采集數據量大，并且某些節點的感知數據相關性強，因此，在數據采集的過程中將每個節點的感知數據全部傳輸是不適宜和不必要的。大數據量的傳輸使整個網絡消耗過多能量，導致網絡生命期縮短。采集數據應首先進行網內數據處理，消除冗余信息。數據聚合是指利用傳感器節點的本地處理能力，對采集到的或接收到的多個數據進行網內處理，消除冗余信息，減少數據傳輸量，減小分組沖突概率，如圖4所示[10]。

圖4 數據聚合示意圖

在多媒體節點采集數據時，同一節點的感知數據通常是時間相關的。如果不同節點的傳感域存在重疊，則其采集的數據具有一定的空間相關性。

在CDAA協議中，根據節點角色不同分別進行如下的數據聚合處理。

(3)對于簇頭節點，當其收到簇內成員發送的數據時，若該數據屬于高優先級，則立即發送，否則等到簇內所有節點數據到達后，按照節點間相關度對節點數據進行融合后再發送。

4 仿真實驗

網絡生命期指的是網絡開始運行到第1個節點死亡之間的時間長度[17]。從圖5可以看出，當節點個數為100時，CDAA協議的網絡生命期比PEGASIS和LEACH分別提高了52%和154%，比AntSensNet提高了8%。當節點個數為200時，CDAA協議的網絡生命期比PEGASIS和LEACH分別提高了41%和124%，比AntSensNet提高了11%。對比4種算法的生存輪數，CDAA明顯優于PEGASIS協議和LEACH協議，比AntSensNet協議略高。相比傳統的WSNs網絡，WMSNs的生存輪數要少很多，主要原因是WMSNs網絡中的圖像數據量大，發送的次數多，能量的消耗大，因此節點的生存輪數較少。在網絡節點總數為100，節點的死亡率為50%時，隨機抽取15組節點進行剩余能量數據對比，10次實驗結果的平均值如表1所示。

表1 4種算法的剩余能量對比(J)

表1中，CDAA算法的剩余能量的標準差約為0.65，剩余能耗為40.4 J，而PEGASIS協議和LEACH協議的剩余能量的標準差約為0.8和0.98，剩余能耗分別為30.9 J和26.1 J, AntSensNet協議的剩余能耗為32 J，標準差為0.64。表1表明，CDAA算法在均衡能耗方面要優于PEGASIS協議和LEACH協議，同AntSensNet協議相當，但在節能方面要優于AntSensNet。

本節在其它實驗參數不變，只改變虛擬監測單元設置的情況下對CDAA協議進行模擬仿真。監測區域的設置分為3種情形：

(1)整個監測范圍劃分為16個虛擬監測單元，每個區域的范圍為50 m×50 m。

(2)整個監測范圍劃分為25個虛擬監測單元，每個區域的范圍40 m×40 m。

(3)整個監測范圍劃分為40個虛擬監測單元，每個區域的范圍20 m×50 m。

實驗仿真過程進行10次，取其平均值作為實驗結果，如圖6所示。從圖6中可以看出，虛擬監測單元為16時，總體性能最好。監測單元數增加到25時，網絡性能稍有下降。當監測單元數增至40時，網絡性能下降明顯。監測單元數增加至40時，同一監測區域內節點數變小，使得監測區域內數據冗余度降低，同一簇內數據相關性減弱，數據融合操作得不到充分體現，導致網絡性能降低。監測單元的設置同網絡內節點的個數、分布、覆蓋范圍也有密切聯系，在進行監測單元設置時，應結合具體應用，綜合考慮上述因素，進行合理的監測單元設置。

以上分析可以看出，本文提出的基于分簇的數據聚合方案的在能耗均衡和節能方面較傳統的WSNs網絡協議PEGASIS和LEACH有明顯的改進，略優于AntSensNet協議。CDAA協議中的分簇方法和數據聚合方案使得網絡節點能耗分布均勻，同一簇內數據相關性增強，通過對數據傳輸進行優化，能夠減少冗余數據的發送，顯著減少網絡平均能耗。

5 結束語

在WMSNs網絡信息收集過程中，節點之間采集的數據通常存在冗余，大量數據的傳輸使整個網絡消耗了過多能量，縮短了網絡生命期。本文提出了新的分簇方法與數據聚合方案，分簇方法平衡了節點能耗，增強了簇內數據相關性，并在此基礎上，通過數據聚合減少了冗余數據的傳輸，延長了網絡壽命。理論分析與仿真實驗證明了CDAA協議具有良好的性能。

下一步的工作重點是在考慮網絡節點非均勻分布模型下，完善分簇算法，使得網絡中的分簇更合理；考慮網絡的全覆蓋問題；研究在多媒體節點的采集方向可調及存在障礙物的情況下，如何進行分簇與數據聚合；并根據網絡的具體應用與QoS要求，采用合適的數據聚合策略，減少數據聚合導致的延遲，提高通信效率。

圖5 網絡生命期

圖6 虛擬監測單元對網絡生命期的影響

[1] Heinzelman W B, Chandrakasan A P, and Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]., 2002, 1(4): 660-760.

[2] Lindsey S and Raghavendra C S. PEGASIS: power efficient gathering in sensor information system[C]. Proceedings of the IEEE Aerospace Conference, Montana, USA, 2002: 1125-1130.

[3] Khalil Enan A and Attea Bara’a A. Energy-aware evolutionary routing protocol for dynamic clustering of wireless sensor networks[J].2011, 1(4): 195-203.

[4] Xu Y, Heidemann J, and Estrin D. Geography-informed energy conservation for ad hoc routing[C]. Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking, Rome, Italy, 2001: 70-84.

[5] Sun Yan, Ma Hua-dong, Liu Liang,.. ASAR: an ant-based service-aware routing algorithm for multimedia sensor networks[J]., 2008, 3(1): 25-33.

[6] Shu Lei, Zhang Yan, Yang L T,.. Geographic routing in wireless multimedia sensor networks[C]. Proceedings of Second International Conference on Future Generation Communication and Networking, FGGN’08, Hainan Island, China, 2008: 68-73.

[7] Kandris D, Tsagkaropoulos M, and Pllitis I. Energy efficient and perceived QoS aware video routing over wireless multimedia sensor networks[J]., 2011, 9(4): 591-607.

[8] Cobo L, Quintero A, and Pierre S. Ant-based routing for wireless multimedia sensor networks using multiple QoS metrics[J]., 2010, 54(17): 2991-3010.

[9] 馬華東, 陶丹. 多媒體傳感器網絡及其研究進展[J]. 軟件學報, 2006, 17(9): 2013-2028. Ma Hua-dong and Tao Dan. Multimedia sensor network and its research progresses[J]., 2006, 17(9): 2013-2028.

[10] 于宏毅, 李歐, 張效義. 無線傳感器網絡理論、技術與實現[M]. 北京: 國防工業出版社, 2010: 190-203.

[11] 葉寧, 王汝傳. 傳感器網絡中一種基于估計代價的數據聚合樹生成算法[J]. 電子學報, 2007, 35(5): 806-810. Ye Ning and Wang Ru-chuan. A tree formation algorithm for data aggregation based on estimate cost in sensor networks [J]., 2007, 35(5): 806-810.

[12] Newella A and Akkaya K. Distributed collaborative camera actuation for redundant data elimination in wireless multimedia sensor networks[J].2011, 9(4): 514-527.

[13] 張強, 盧瀟, 崔曉臣. 基于分簇的無線傳感器網絡數據聚合方案研究[J]. 傳感技術學報, 2010, 23(12): 1778-1782. Zhang Qiang, Lu Xiao, and Cui Xiao-chen. Research on the scheme of data aggregation based on clustering for wireless sensor networks[J].. 2010, 23(12): 1778-1782.

[14] He T, Blum B M, Stankovic J A,AIDA: Adaptive application independent data aggregation in wireless sensor networks[J]., 2004, 3(2): 426-457.

[15] Sun En-yan, Shen Xuan-jing, and Chen Hai-peng. A low energy image compression and transmission in wireless multimedia sensor networks[J].2011, 15: 3604-3610.

[16] 楊軍, 張德運, 張云翼, 等. 基于分簇的無線傳感器網絡數據匯聚傳送協議[J]. 軟件學報, 2010, 21(5): 1127-1136. Yang Jun, Zhang De-yun, ZhangYun-yi,.. Cluster-based data aggregation and transmission protocol for wireless sensor networks[J]., 2010, 21(5): 1127-1136.

[17] Chang J H and Tassiulad L. Maximum lifetime routing in wireless sensor networks[J]., 2004, 12(4): 609-619.

張軍強： 男，1976年生，博士生，講師，研究方向為無線傳感器網絡、數據融合.

王汝傳： 男，1943年生，教授，博士生導師，主要研究方向為無線傳感器網絡、計算機軟件、計算機網絡、信息安全、移動代理等.

黃海平： 男，1981年生，博士，副教授，碩士生導師，研究方向為無線傳感器網絡、多媒體傳感器網絡、物聯網和信息安全.

Research on Cluster-based Data Aggregation for Wireless Multimedia Sensor Networks

Zhang Jun-qiang①④Wang Ru-chuan①②③Huang Hai-ping①②③

①(,210003,)②(,210003)③(,210003,)④(,210009,)

A Cluster-based Data Aggregation Algorithm (CDAA) for Wireless Multimedia Sensor Networks (WMSNs) is proposed. CDAA extends effectively the network life cycle by a new clustering method and a data aggregation scheme based on the clustering method. According to the orientation feature and the residual energy of an individual multimedia sensor node, a new clustering method is proposed. Furthermore, a scheme of data aggregation is applied based on the clustering method. Compared with LEACH, PEGASIS and AntSensNet protocols, simulation results show that CDAA can decrease the number of data transmission in WMSNs, balance energy consumption and prolong the networks lifetime.

Wireless Multimedia Sensor Networks (WMSNs); Cluster; Data aggregation; Network lifetime

TP393

A

1009-5896(2014)01-0008-07

10.3724/SP.J.1146.2012.00933

2012-07-19收到，2013-10-08改回

國家自然科學基金(61170065, 61202355)，江蘇省自然科學基金(BK2012436)，江蘇省科技支撐計劃項目(BE2010197, BE2011844)，江蘇省屬高校自然科學研究重大項目(12KJA520002)，高校科研成果產業化推進工程項目(JHB2012-7)和江蘇高校科技創新計劃項目 (CXZZ12_0479)資助課題

王汝傳 wangrc@njupt.edu.cn