ARDCH：適于多媒體傳感器網絡的自適應周期分簇機制

李瑞芳，李仁發，羅娟

（湖南大學 計算機與通信學院，湖南 長沙 410082）

1 引言

隨著人們對信息獲取的需求不斷增加，傳統傳感器網絡所獲取的簡單數據不能滿足人們對信息獲取的全面需求，而迫切需要獲取信息量豐富的圖像、音頻、視頻等多媒體信息。無線多媒體傳感器網絡（WMSN,wireless multimedia sensor network）受到越來越多研究者的重視。多媒體傳感器網絡傳輸質量保障的一個關鍵問題是流媒體路由選擇，網絡中節點能量、帶寬等資源的嚴重受限，使得支持實時可靠的大數據流媒體傳輸相當困難，如何設計新型的傳感器網絡路由，實現實時、可靠的流媒體信息傳輸，值得深入探討[1]。由于層次結構特別是簇結構有利于減少數據傳輸延遲、增強網絡的可擴展性以及易于實現數據聚合，因此，近年來，研究者對分簇以及簇頭競爭方式進行了廣泛研究。

在本文中，針對多媒體傳感器網絡的需求，提出了一種基于剩余能量與傳輸距離的自適應周期分布式簇頭競爭機制（ARDCH,adaptive round distributed cluster head），不同于以前的研究工作，協議采用一種基于地理位置的分簇方式，通過綜合考慮節點剩余能量以及通信代價選舉簇頭，同時根據剩余能量來動態調節簇頭的工作周期，使節點均衡能耗，延長網絡生命周期，同時采用多信道簇間通信，避免簇間干擾。

本文第2節介紹相關工作，第3節對本文采用的系統模型及提出問題進行描述，第4節給出算法的詳細設計，第5節對算法性能進行分析，第6節進行協議仿真實驗、分析實驗結果，第7節是結束語。

2 相關工作

Heinzelman等人在文獻[2]中提出的 LEACH(low energy adaptive clustering hierarchy)協議假設基站被部署在網絡外的一個固定位置，并且所有節點都可以與基站直接通信。為了節省能量，LEACH協議在部署前確定簇頭的比例 p，剩余的節點作為普通節點加入信號最強的簇頭，成為該簇頭的簇成員。為了將能量負載均勻地分配到各節點上，LEACH協議按輪運行，并在每一輪中對簇頭進行輪換。在每一輪中，當簇生成以后，簇頭將聚合其收到的各成員節點的采集信息，并將聚合信息直接傳輸到基站。由于減少了與基站直接通信的節點數量以及通信量，LEACH協議可以有效地延長網絡生命周期。但是，協議中簇頭的選舉忽略了節點剩余能量、地理位置等信息，容易導致簇頭節點很快失效。

文獻[3]提出了一種分布式的節能分簇算法HEED(a hybrid,energy-efficient,distributed clustering approach)。HEED算法綜合節點的剩余能量和其他參數(如候選節點與鄰居節點的鄰近性)來周期性地選擇簇頭。HEED算法在O(1)內結束，與傳統的簇算法具有更小的消息開銷相比，HEED可以保證簇頭節點在整個網絡中分布良好。然而，由于HEED算法在簇形成階段仍然需要廣播多條消息，因而增大了能量開銷。

文獻[4]提出了一種隨機簇組織局部算法，并在此基礎上，提出了建立層次化簇結構的思路。其同文獻[2]的重要區別在于在簇頭選舉時不需要時間同步，并且沒有考慮簇首輪換和簇重組問題。

在文獻[5]中，每個節點需要估計網絡中所有節點的總能量來計算自己成為簇頭的概率，高能量的節點有更大的機率成為簇頭，但是由于協議需要每個節點獲得全局信息，因此，該協議的可擴展性受到影響。

文獻[6]提出的非均勻分簇EEUC（energy-efficient uneven clustering)算法，利用非均勻的競爭半徑，使得靠近匯聚點的簇的成員數目相對較小，從而簇首能夠節約能量以供數據轉發使用，達到均衡簇首能量消耗的目的。此外，在簇首選擇其路由的下一跳節點時，同時考慮候選節點相對匯聚點的位置以及候選節點的剩余能量。文獻主要解決簇間通信的“熱區”問題，對于多媒體傳感器網絡并無涉及。

DAEA(data aggregation-exact and approximate)[7]算法是一個3層分簇算法，它首先依據地理位置將所有的傳感器區域分成大小相等且不互相重疊的正方形區域，為每個區域選擇能量最多的節點作為簇頭LA，然后在所有的LA中選取能量最多的節點作為簇頭的上層簇頭節點MA，LA與MA通信，MA負責與基站通信。分層協議雖然節省了能量，但同時增加了延遲，不適于多媒體傳感器網絡。

3 信道模型及問題描述

3.1 信道模型

本文假設N個多媒體傳感器節點隨機均勻分布在一個區域 A內部（為方便起見，在方案中令 A為正方形），并假設該傳感器網絡具有如下性質。

1) 基站位于區域外部較遠處，傳感器節點和基站均靜止不動。

2) 每個節點功能相同，均具備數據聚合能力，即把接收到的多個數據包根據應用的具體要求聚合成一個數據包。

3) 節點的無線發射功率可控，即節點可以根據到信號接收方距離的遠近調節發射功率以節省能量，例如Berkeley Motes節點具有100個發射功率等級，與采用固定發射功率相比，能顯著減少節點的能量損耗，從而延長無線傳感器網絡的壽命。

4) 系統能通過GPS、有向天線或定位算法等定位技術得到各節點的具體位置信息。由于對大多數應用，不知道傳感器位置而感知的數據是沒有意義的，尤其對多媒體傳感器網絡，多媒體節點對其位置、方向角度等要素都有要求，傳感器節點必須明確自身位置才能詳細說明“在什么位置或區域發生了特定事件”，從而實現對外部目標的準確定位和追蹤。目前許多研究者對傳感器節點的定位進行了大量的研究，取得了諸多成果。

3.2 無線通信能耗模型

近年來，許多學者在低能量無線通信方面進行了大量的研究工作。本方案與文獻[4]使用了相同的無線通信模型。該無線通信模型給出了一個閾值d0(d0是常數，數值取決于使用環境)，當發送節點與接收節點的距離小于d0時，發送方發送數據的能量損耗與距離的平方成正比，否則與距離的4次方成正比。上述的2種能量衰減模型分別稱為自由空間(free space) 模型和多路衰減(multipath fading)模型。因此，根據發送節點和接收節點之間的距離，發送節點可以使用不同的能耗模型計算發送數據所需要的能量。例如，節點 a 向距離 d 外的另一節點b 發送k byte的數據，可以使用下面的公式計算其能量消耗：

而b 接收a發送的消息，其無線接收裝置產生的能耗為

式(1)、式(2)中，Eelec表示無線收發電路所消耗的能量。Eamp表示放大器消耗的能量，其大小取決于發送節點與接收節點間的距離以及可接受的位錯誤率。此外，大部分協議和算法都采用了數據聚合技術來減少發送和接收的數據量，從而達到節省能量的目的。此外，本文假設無線信道是對稱的，即從節點a 傳送消息m 到節點b 消耗的能量等于從節點b 傳送消息m 到節點a 消耗的能量。

3.3 問題描述

傳感器網絡路由協議的一個重要目標，就是合理高效地使用網絡中各傳感器節點的能量，延長網絡的存活時間。在以分簇方式組織的傳感器網絡中，路由分為簇內通信和簇間通信2部分。當簇成員與簇頭之間傳輸數據時，采用單跳通信的方式，這樣易于調度各成員節點的數據傳輸，當簇頭向匯聚點進行長距離數據傳輸時，研究表明采用多跳路由的方式更能降低能耗[8]。

由于多媒體傳感器節點成本的提高，無法像傳統傳感器網絡使用大量冗余節點的隨機部署，多媒體傳感器網絡一般采用有計劃的部署節點。此外，由于多媒體數據（尤其是視頻信息）的位置相關性，任何節點的信息對于整個網絡而言都是重要的，因此，網絡的生存周期與所有節點的生存周期密切相關。這樣，如何均衡節點能耗、提高能耗有效性、延長每個節點的生命周期顯得至關重要[9]。

本文創新地設計了一種基于剩余能量與傳輸距離的自適應周期分布式簇頭競爭機制。與前人的方法相比，本文提出的方法在均衡網絡中節點的能量消耗，延長網絡生存周期有顯著提高，更適于多媒體傳感器網絡傳輸要求。

4 協議設計

4.1 分簇及簇頭競爭方式

4.1.1 簇的生成

以往的各種分簇協議，大都采用節點以一定的概率通過競爭產生簇頭，其余普通節點根據信號接收強度加入，自發形成簇的方式。由于多媒體傳感節點相比傳統傳感器節點硬件成本高，且節點（尤其圖像、視頻傳感節點）與其傳感方向相關，故一般情況下不采用傳統傳感器網絡隨機大量冗余部署，而是采取有計劃的部署。本文在假設節點的具體地理位置已知的情況下，根據節點的具體位置信息，將區域A劃分為若干正方形區域Aij，各區域Aij成為一個簇，如圖1所示。由于網絡采取有計劃部署，相對傳統WSN，WMSN的節點部署較為均勻，采取如下分簇方式，并不會造成嚴重的分簇不均勻。

圖1 分簇示意圖

4.1.2 簇間通信

協議采用多信道接入方式，使相鄰各簇的信道不同，如圖2所示，劃分4種不同信道。簇內各成員節點根據簇頭的廣播消息計算與簇頭的距離調整其發射功率，即使在最壞的情況，當簇頭位于區域頂點而成員節點位于對角線的另一端頂點時，即在圖 2中A22簇，簇頭位于其頂點，若在其對角頂點存在節點，如圖2中虛線圓圈所代表的通信覆蓋范圍，則在相同信道的 A20以及 A02簇存在范圍較小的干擾區，但是由于簇頭選舉的競爭指標其一為各成員節點到簇頭距離之和相對較小，故這種情況在實際簇頭競爭的過程中幾乎不存在，如當簇頭位于接近頂點的位置，圖 2 A22黑色實心點位置，此時，通信覆蓋范圍為圖中實線圓圈所示，簇間不存在干擾，即信道相同的相鄰簇之間的簇間干擾可基本消除。

圖2 簇間多信道接入示意圖

4.1.3 簇頭的產生

設邊長為a的簇Aij隨機分布m個節點。假設節點q成為候選簇頭，本文假設無線信道是對稱的，則簇內各成員節點向候選簇頭發送k byte數據所消耗的能量，與候選簇頭向各成員節點發送k byte數據所耗能量相等。簇內能量衰減模型采用自由空間模型，即可見，決定了網絡能耗的高低，即網絡能量開銷指標為。候選簇頭的競爭指標(CI,competition index)與SEtr(k,d)以及ER（剩余能量）有關，即與以及 ER相關，假設節點初始能量為E0，則已消耗能量為E0～ER，且存在如下關系：

標準化參數，則轉化為

即，

式(4)中α、β的取值根據簇內節點位置的分布及能量均衡的程度，具體的值將通過多次實驗進行最優選擇。

由于消息的發送、接收以及聚合所消耗的能量可以預知，所以當一個節點成為簇頭所需要消耗的最小能耗Emin可以計算，把Emin稱之為閾值，當節點的剩余能量小于閾值時，該節點不再參與簇頭競爭。

其中，cycle表示每輪數據收集的次數，E_fusion表示聚合所消耗的能量，l表示數據包的長度，dC表示相鄰簇間的距離（同信道相鄰簇頭之間的距離），由于本文采用簇間多信道接入，相鄰簇之間信道各不相同（圖 2所示），故同信道相鄰簇頭之間的距離假設其大于閾值d0。

簇頭產生后，采用自適應周期的方式，依據簇頭節點的剩余能量動態調節其工作周期，當簇頭節點消耗的能量為成為簇頭節點之前能量的ρ%時，簇頭本輪工作結束。即

在協議中，簇頭產生的方式如圖3所示。

圖3 簇頭產生方式

簇頭的生成依照以下規則。

規則1 簇內各節點廣播節點信息SN_Msg（ID,Locatin(x,y),Er）。

規則2 簇內各剩余能量大于Emin的節點均有機會參與簇頭節點競爭，節點產生一個[0,1]隨機數q，q大于p（p的取值取決于簇內節點密度及分布狀態）時，節點根據公式（4）計算其自身的競爭指標CI，廣播競爭簇頭消息Compete_CH_Msg(ID,CI)。

規則3 根據廣播的競爭消息，建立鄰居競爭簇頭集合 S.CH，比較其 CI，CI最小的節點成為最終簇頭，廣播競爭勝利消息 CH_Msg(ID,Locatin(x,y))。其余競爭節點接收到競爭勝利消息，退出競爭。

規則 4 當簇頭節點消耗的能量為成為簇頭節點之前能量的ρ%時，以及自身能量小于或等于 Emin時，本輪周期結束，簇頭節點廣播CH_Quit_Msg，簇內各節點開始重新競爭簇頭。

5 協議分析

在這一節里，主要對協議的復雜度性能進行分析。

假設網絡中共有N個節點，分成m簇，每簇平均有naverage個節點。

在協議中，每一輪（round）開始時，所有節點廣播其節點信息 SN_Msg，符合要求參與簇頭競爭的節點廣播Compete_CH_Msg，競爭成功的節點廣播勝利消息CH_Msg，當簇頭節點經過若干周期傳輸后，其自身剩余能量小于或等于Emin時，簇頭節點廣播CH_Quit_Msg，即一輪中網絡控制消息數目如表1所示。

表1 消息格式及說明

由表1可知網絡中總的消息開銷為

因此，整個網絡的控制消息復雜度為O(N)。

6 實驗及分析

6.1 仿真環境及參數設置

本文采用NS2與MATLAB2008對自適應周期分布式簇頭競爭機制 ARDCH進行性能分析與評估。為簡單起見，假設采用理想的MAC協議，忽略無線鏈路中可能發生的分組丟失錯誤。實驗中統計傳感器節點接收數據、融合數據和發送數據所消耗的能量，計算網絡的存活時間，來分析競爭機制的能量效率。為了證明本文提出的路由協議的能耗均衡以及能量高效，將ARDCH與LEACH、DAEA分簇協議進行比較。實驗中所用的參數如表2所示，其中能量消耗模型相關的參數取自文獻[4]。

表2 仿真實驗中的參數設置

6.2 實驗結果及性能分析

文中考慮網絡的生存周期以及節點剩余能量的分布，由于多媒體傳感器網絡大多采用有計劃部署，節點有位置及方向相關性，文中用第一個節點死亡的時間衡量網絡完整生存周期，但是，如若有一個節點死亡就放棄整個網絡，這無疑造成極大的浪費，實驗中同時衡量網絡基本生存周期，即網絡剩余50%節點的持續時間。

6.2.1 ARDCH算法參數分析

由式(4)可知，ARDCH算法的簇頭競爭指標與參數α、β密切相關，同時由簇頭生成規則4可知簇頭的工作周期由參數ρ決定，圖4分析了在α、β以及ρ取不同值的情況下ARDCH算法在網絡生存周期方面的表現，實驗分析得知，算法在α=0.1，β＝0.9，ρ＝0.05的時候，網絡完整生存周期達到較為理想的狀態。

圖4 ARDCH算法參數取值比較

6.2.2 網絡生存周期比較

圖 5(a)比較了 ARDCH算法與 LEACH及DAEA算法的網絡完整生存周期，由于文中采用基于地理位置的分簇劃分方法，實驗中假設 LEACH與DAEA在既定的簇內選取一個簇頭。由圖可知，ARDCH算法的網絡完整生存周期相較于其他算法有明顯的提高。

圖5(b)比較了3種算法的基本生存周期，即從網絡中第一個節點死亡到 50%節點死亡的持續時間，由圖可知，ARDCH算法比DAEA算法基本生存周期有一定的增長，變化趨勢則基本相似，隨著節點增多，網絡基本生存周期延長，但是當節點增加到一定程度，基本生存周期緩慢減小，而LEACH算法隨著節點的增加，基本生存周期單向增加，且比前2種算法有較大的增幅。

圖5(c)比較了3種算法從初始工作到50%節點死亡的網絡持續時間，可以看出，ARDCH算法相比于其余2種算法，無論從網絡完整生存周期還是網絡總持續時間都有明顯優勢。

6.2.3 節點剩余能量分析

圖5 網絡生存周期比較

圖6比較了3種算法在100個節點的情況下網絡中節點剩余能量分布，由圖6(a)可知，當網絡中第一個節點死亡時，LEACH算法節點剩余能量分布最為不均勻，某些節點幾乎未消耗能量而有些節點的能量幾乎消耗完畢，DAEA算法能量消耗分布最為均勻，當網絡中出現節點死亡的情況時，其余各節點剩余能量均在0.15J左右，而ARDCH算法在出現節點死亡時，一部分節點的剩余能量在0.15J附近，一部分節點能量在0.1J附近，一部分節點的剩余能量在 0.02J附近，這樣就有利于一部分節點能繼續充當簇頭節點，而不至于使整個簇內全部節點全部癱瘓。圖6(b)所示為網絡中50%節點死亡時，節點的剩余能量分布，LEACH算法的能量分布仍然最為不均勻，ARDCH算法相比DAEA算法能量消耗的更為徹底。

通過剩余能量的分析印證了上小節的網絡生存周期的實驗結果，由于在第一節點死亡時，LEACH算法的節點剩余能量最多且最為不均勻，所以從網絡中第一個節點開始死亡到 50%節點死亡，LEACH算法持續時間最長，而DAEA算法的節點能耗最均勻，而作為分簇協議，簇頭相比簇內成員節點需要消耗的能量要大得多，所以能量略為不均勻的ARDCH算法的基本生存周期相比DAEA算法略有優勢。

圖6 節點剩余能量分布比較

總結實驗結果,本文提出的適于多媒體傳感器網絡的分簇機制具有以下優點：1)分簇穩定；2)能量消耗低，并且有效平衡了簇內節點的能量消耗；3)顯著延長了網絡完整存活時間，同時保證了網絡基本生存周期。對于多媒體傳感器網絡的要求，ARDCH分簇機制相較于其他分簇協議更為適合。

7 結束語

本文依據多媒體傳感器網絡的需求，提出了一種基于剩余能量與傳輸距離的自適應周期分布式簇頭競爭機制，其核心思想是綜合考慮通信代價及地理位置進行簇頭選取，同時根據剩余能量來動態調節簇頭的工作周期，以此均衡網絡中節點的能量消耗，理論分析和仿真試驗證明，和已有的幾個分簇協議相比，顯著地延長了網絡的生存周期，同時采用多信道簇間通信，避免簇間干擾。

如何利用傳感器網絡實時、可靠地傳輸大數據量流媒體信息，而盡量節省網絡能量，延長網絡生存期，是多媒體傳感器網絡研究的重要內容，結合路由層和MAC層綜合考慮多媒體信息可靠高效傳輸是下一步工作研究方向。

[1] 馬華東,陶丹.多媒體傳感器網絡及其研究進展[J].軟件學報,2006,17(9): 2013-2028.MA H D,TAO D.Multimedia sensor network and its research progresses[J].Journal of Software,2006,17(9): 2013-2028.

[2] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[A].Proc of the Hawaii Int’l Conf on System Sciences[C].San Francisco: IEEE Computer Society,2000.3005-3014.

[3] YOUNIS O,FAHMY S.Distributed clustering in ad-hoc sensor networks: a hybrid,energy-efficient approach[A].Proc of the IEEE INFOCOM[C].San Francisco: IEEE Computer Society Press,2004.

[4] BANDYOPADHYAY S,COYLE E J.An energy efficient hierarchical clustering algorithm for wireless sensor networks[A].INFOCOM 2003,the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies[C].IEEE,2003.1713-1723.

[5] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[6] 李成法,陳貴海,葉懋.一種基于非均勻分簇的無線傳感器網絡路由協議 [J].計算機學報,2007,30(1):27-36.LI C F,CHEN G H,YE M,WU J.An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Journal of Computers,2007,30(1):27-36.

[7] AL-KARAKI J N,UL-MUSTAFA R,KAMAL A E.Data aggregation in wireless sensor networks—exact and approximate algorithms[A].Proc of the IEEE Workshop on High Performance Switching and Routing.Phoenix: IEEE Communications Society[C].2004.241-245.

[8] SOHRABI K,GAO J,AILAWADHI V,et al .Protocols for self-organization of a wireless sensor network[J].IEEE Personal Communications 2000,7(5): 16-27.

[9] 李瑞芳,李仁發,羅娟.無線多媒體傳感器網絡 MAC協議研究綜述[J].通信學報,2008,29(8): 111-123.LI R F,LI R F,LUO J.Survey of MAC protocol in wireless multimedia sensor networks [J].Journal on Communications,2008,29(8): 111-123.