基于分布式與聯合優化的無線傳感器網絡數據匯聚機制

劉韜，李天瑞，談文蓉，殷鋒

（1. 西南民族大學 計算機科學與技術學院，四川 成都 610041；2. 西南交通大學 信息科學與技術學院，四川 成都 610031）

1 引言

無線傳感器網絡(WSN)中，數據匯聚是指將不同源節點的數據收集到匯聚節點（sink），顯然，數據（信息）匯聚是無線傳感器網絡典型的傳輸形態[1]。根據數據匯報方式，無線傳感器網絡大致可以分為事件驅動型和周期匯報型2類網絡[2]。在事件驅動型傳感器網絡，節點平時很少產生數據，僅在待監測的事件發生時才產生事件報告；而在周期匯報型傳感器網絡中，所有節點周期性地向匯聚節點報告采集到的信息，直到網絡生命周期結束。與事件驅動型網絡相比，周期匯報型網絡中對節點匯報信息實時性要求往往較低，但每個節點都需要向匯聚節點周期性地發送信息，網絡的數據量大，節點能耗高，且節點的無線信號沖突概率高，節點之間的無線信號相互干擾，MAC層設計復雜。

本文針對這些難點，提出了一種適用于周期匯報型網絡的數據匯聚機制(DDSM)。該機制在“梯度匯聚”模型的基礎上，聯合優化MAC層和網絡層功能，采用節點周期性睡眠/工作的節能調度方法，分布式地建立每個節點的優化路由及工作時隙。本文的主要貢獻在于以下幾點。

1) 提出一種完全分布式的由各個節點自行確立優化路由和工作時隙的機制，使該機制具有很強的實用性，并且采用該機制的網絡具有良好的可擴展性和可維護性。

2) MAC層采用分布式TDMA的機制，并采用聯合優化的思想，融合網絡層、MAC層，使節點優化路由的建立、發送時隙的分配以及節點的時鐘同步在一個過程中完成，放棄了單層優化、各層獨立設計的手段，顯然具有更高的效率，且節約了能量。

3) 由于節點間的相互干擾，節點發送時隙的確立是一個難題。DDSM采用RTS/Final_RTS/CTS的辦法來解決該問題，即通過多次向鄰居節點廣播試探性RTS消息，直至沒有收到否定應答幀NAK來確定發送時隙。

2 相關工作

不同于傳統網絡協議棧的層次結構，無線傳感器網絡的協議棧一般被分為4層[3]:應用層、網絡層、媒體介質訪問控制（MAC，medium access control）層和物理層。近年來，研究人員提出了許多數據收集協議，例如:網絡層上，LEACH[4]是比較有代表性的分簇路由算法，而朱紅松等提出了一種精細化梯度的數據匯聚機制 FGS[1]；MAC層上，經典的S-MAC[5]協議通過采用周期性偵聽/睡眠工作方式來減少空閑偵聽；文獻[6]提出了一種由發送節點發起建立連接的異步低占空比、低碰撞的PB-MAC協議算法。這些網絡協議大都采用單層優化的方案，各層相互獨立。這種單層優化的方法雖然給網絡協議的模塊化帶來了方便，但各層之間的相互獨立、不能協作，導致網絡的整體性能不能達到最優[2]。

聯合優化設計的方法是近幾年來提出的主要用于無線網絡的設計方法，其設計思路是融合網絡層、MAC層和物理層設計網絡協議，多個層綜合考慮優化，打破層與層之間的獨立性，從全局的角度對系統的資源進行整合，能最大程度地節約節點的能量[7]。王辛果等在文獻[2]中提出一種時延受限且能量高效的跨層路由協議，該協議在做出路由決定時考慮MAC層的相關信息。但該協議為事件驅動型網絡而設計，在設計中較少考慮節點間信號的沖突和干擾問題，顯然不適用于周期匯報型網絡。李方敏等基于跨層優化的策略提出了一種易于實現能動態適應網絡變化的能量有效的鏈路穩定成簇算法[8]，但該算法沒有分析簇頭到匯聚節點的優化路由，且沒有考慮信號沖突問題。文獻[9]結合MAC層協議與網絡層路由協議，提出了AIMRP協議。該協議根據節點到匯聚節點的跳數，形成一個以匯聚節點為中心的多層環形結構，數據信息從外環逐環向內環傳遞。AIMRP協議同步精度要求高，但動態適應性差，只適用于小范圍的事件驅動型傳感器網絡。

文獻[10]提出了一種基于TDMA調度策略的跨層設計方案，該方案采用了分簇的結構，并通過構建涉及網絡層、MAC層和物理層的跨層優化模型來獲得高能效的調度方案。該方案證明了傳感網的MAC層上采用TDMA機制具有零沖突、高能效的特點。但該方案是一種集中式的優化方案，即由匯聚節點集中計算每個節點的路由或調度方案，再把優化路由或調度方案發送給每個節點。集中式的算法缺乏可擴展性，網絡也不具備可伸縮性[11]且匯聚節點收集源節點自身信息和發布優化方案的過程中會消耗大量能量。

文獻[12]提出了一個基于TDMA機制的跨層優化數據收集協議 LEEMA，建立以匯聚節點為根的路由樹，再通過該路由樹為節點分配工作時隙。LEEMA采用的是最小跳數路由，該路由雖然建立簡單，但是不一定是最小能耗路由，其節能效果不一定最優。另外，LEEMA沒有考慮負載均衡，容易形成能量空洞。

盡管在近幾年來，對無線傳感器網絡的數據匯聚機制已經有了相當的研究成果，但大都或多或少地存在一些缺陷與不足。本文在此基礎上展開研究，在網絡層和 MAC層上進行聯合優化，提出了一個完全分布式、高能效與低成本的數據匯聚機制。

3 系統模型

3.1 網絡模型

與文獻[1]和文獻[9]類似，本文中的傳感器網絡采用“梯度匯聚”模型將節點的數據傳遞給匯聚節點。假設網絡中所有的節點均勻分布于監控區域中，sink位于區域中心，節點密度為p。所有的節點具有相同的最大無線傳輸距離R。網絡被劃分為以sink為圓心的n個相鄰的環狀區域，也稱為“梯度”，d為每個圓環的寬度，所有節點位于各圓環內。從圓心向外，各圓環依次表示為C1，C2，…，Cn，如圖1所示。

圖1 網絡模型(n=3)

針對周期匯報型傳感器網絡的特點，做如下說明。

1) 網絡中的每個節點周期性的采集和發送數據。每個工作周期，每個節點產生一個固定大小的感應數據分組發往匯聚節點。

2) 節點路由采用“梯度匯聚”模型，處于圓環(梯度)Ci中的節點只能選擇圓環Ci-1中的節點作為下一跳的數據轉發節點(1

3) 所有節點能夠動態的調整其發射功率，例如，Berkeley Motes 節點就具有100個發射功率等級[13]。

4) 所有節點的時鐘能夠保持同步。

為了增加網絡的連通性，使

另外，經信道衰減，無線信號最終能否被成功接收取決于接收端的信號與干擾、噪聲功率比SINR[2]。于是，采用式(2)來判斷目的節點能否正確接收無線信號

其中，S表示信號接收功率，W表示噪聲功率，I表示干擾信號功率。SINRthreshold表示一個門限值，通常它的值被設為10。假設噪聲很小，忽略接收端的噪聲功率，并假設B為接收節點，T為干擾節點的集合，可得

其中，Pr(B)與Pt(X)分別為接收節點B的接收信號功率和節點X的發送功率，d(X,B)為節點X與B的距離。

3.2 傳播模型

根據文獻[14]，當節點A發送無線信號到節點B時，節點B的接收信號功率Pr(B)為

其中，Pt(A)是節點A的發射功率，d(A,B)表示節點A和節點B之間的距離。本文假設傳感器網絡位于自由空間，則β=2。并且

其中，Gt和Gr分別是發射天線增益和接收天線增益，λ是信號波長。

3.3 相關定義

定義 1TRCS：載波監聽門限或感應靈敏度。當節點接收信號功率大于等于TRCS時，節點才能感應到有信號發送。

定義 2TRRX：信號接收門限。當節點接收信號功率大于等于TRRX時，節點才能正確接收信號。

定義3RCS：載波最大監聽距離。當節點以最大發射功率PtMax發射信號時，另一節點能感應到此次發送的最遠距離。根據式(4)可得

其中，β=2。

定義4R：最大無線傳輸距離。當節點以最大發射功率PtMax發射信號時，另一節點能正確接收此次發送的最遠距離。根據式(4)可得

4 若干關鍵問題

4.1 隱藏節點問題

目前，網絡通常采用 RTS/CTS(請求發送/允許發送)協議來解決“隱藏節點”的問題[15]。如圖 2所示，節點A欲向節點B發送數據，則：首先，A向B發送RTS信號，B收到RTS后，發CTS信號，表明已準備就緒，A可以發送，而其余收到CTS的節點則暫停發送。此協議認為節點發送CTS的范圍能夠覆蓋所有的隱藏節點，但在實際節點接收模型中，隱藏節點的分布范圍遠大于節點的發送范圍[15]。如圖 2所示，若每個節點能以最大發送功率發送無線數據信號，則節點B的干擾節點區域是以節點B的圓心，RCS為半徑的圓，位于此圓內的節點發送信號都會對節點B的接收造成干擾。很明顯，節點B發CTS信號，最大發送功率為，只有與B的距離小于R的節點才能收到CTS信號，位于圖2中陰影區域內的節點無法收到CTS信號，而這些節點又處于節點B的干擾節點區域內，若它們此時發送數據，會對節點B的接收造成干擾，甚至影響接收，形成“隱藏節點”。這說明RTS/CTS協議在較低信噪比要求的情況下可以防止大部分隱藏節點，但是隨著信噪比要求的逐步提高，網絡中的隱藏節點分布范圍急劇增大，RTS／CTS協議防止隱藏節點的效率也隨之降低[15]。

圖2 RTS/CTS握手協議中的隱藏節點問題

為解決這一問題，本文借鑒文獻[16]的方法來改進RTS/CTS協議，即減小節點發送感應數據的最大發送功率，從而減小接收節點的干擾節點區域，確保接收節點以最大發送功率發送CTS信號時，干擾節點區域內的節點都能夠接收到 CTS信號。假設節點發送數據的最大發送功率限定為為了確保接收節點的干擾節點區域內的節點都能收到來自接收節點的CTS信號，干擾節點區域的最大半徑只能為R，根據式(4)可得

其中，β=2。結合式(7)可得

所以，為了避免“隱藏節點”的問題，“梯度匯聚”模型中每層圓環的寬度d重新調整為

4.2 “梯度匯聚”機制下的最小能耗路由

“梯度匯聚”機制下，節點只能將數據傳遞給相鄰環(梯度)中的節點。例如，如圖 3所示，節點D有2條路由到達sink，分別為D→B→A→sink和D→C→A→sink，節點D選擇哪條路由首先要判斷總能耗的大小。

圖3 “梯度匯聚”機制下的最小能耗路由

假設Emin(X)表示網絡中任一節點X生成一個感應數據分組到達匯聚節點的最小總能耗，Cos(X,Y)表示一個數據分組從節點X到達節點Y的能耗，則

其中，Pt(X)與Pr(Y)分別表示節點X發射功率和節點Y的接收功率，t表示節點發送或接收一個數據分組所花費的時間。為了進一步降低節點的能耗，盡量減小發送節點發送數據的功率，當接收端的接收信號功率等于信號接收門限TRRX時，結合式(4)，可以獲得節點發送信號所需的最小發射功率Ptmin

其中，d(X，Y)表示發送節點X與接收節點Y的距離。根據式(12)與式(13)，可得一個數據分組從節點X到達節點Y的最小能耗

其中，節點的接收功率一般為固定值Pr。若Sn為節點X位于相鄰梯度(相鄰內層圓環)的鄰居節點集合，結合式(14)，Emin(X)可以通過式(15)計算。

如果節點獲得了它所有相鄰梯度的鄰居節點生成一個數據分組到達匯聚節點的最小總能耗，它就能根據式(15)計算得到它相應的最小總能耗，并選擇對應的鄰居節點為下一跳目的節點。當每個節點都確立了下一跳目的節點后，節點到達匯聚節點的優化路由自然就確立了。所以，DDSM中，節點優化路由的建立過程是由內而外，逐環建立的。即先由第1層圓環的節點先確立下跳目的節點，再由第2層圓環的節點確立下跳目的節點，以此類推，直至最外層。這樣做的目的是在內層圓環（梯度）的節點優化路由的建立過程中，通知外層相鄰圓環鄰居節點其優化路由等信息。當輪到外層相鄰圓環鄰居節點建立優化路由時，就可以依據這些信息，通過式(15)做出選擇。

另外，節點選擇其下一跳路由節點時，還要注意平衡節點的負載，避免把某個節點頻繁選作路由中繼節點，從而過快耗盡能量造成能量空洞。

5 DDSM機制描述

TDMA機制是網絡無線信道分配機制之一，具有零沖突、高能效、低時延的特點，可以很好地應用于數據量大的周期匯報型傳感器網絡，所以DDSM采用TDMA機制實現無線信道分配。

DDSM按輪運行，每輪分為2個階段。第一階段是節點優化路由和時隙調度表的建立階段:每個節點分布式地確立自身到匯聚節點的數據發送路由、所需的發送功率以及相應子階段內的工作時隙；第二階段是節點數據匯聚階段，節點根據分配好的工作時隙，周期性地從休眠狀態醒來，發送數據或接收數據，數據則遵循建立好的優化路由，由外而內，逐環(梯度)的方向向匯聚節點傳遞。每輪都要重新建立每個節點的工作時隙和發送路由是為了適應因個別節點位置變化或節點死亡而造成的網絡拓撲結構的變化。

5.1 數據匯聚階段

每輪的數據匯聚階段由若干個數據采集周期組成，所有節點在每個數據采集周期都要生成一個感應數據分組，并向匯聚節點發送。為避免沖突，如圖4所示，將一個數據采集周期再劃分為若干子周期，每個子周期再繼續劃分為m個時隙，單個時隙的長度等于節點發送一個感應數據分組所需的時間，m也必須足夠大使節點能夠有時間發送完所有的數據分組。每個子周期分配給一個圓環(梯度)，位于圓環Ci(1＜i≤n)內的節點只能在每個數據采集周期的第n-i+1個子周期內的相應時隙發送數據，而相鄰圓環梯度的節點則接收數據。例如，第一個子周期第3層圓環的節點發送數據，第2層圓環的節點則接收數據；而第2個子周期第2層圓環的節點發送數據，第1層圓環的節點則接收數據，以此類推，直至發送到匯聚節點。而節點在相應子周期的發送時隙則由 DDSM 在每輪的節點優化路由和時隙調度表的建立階段中確立。

圖4 一個數據采集周期的時間劃分

5.2 節點優化路由和時隙調度表的建立階段

DDSM在本階段采用多層次聯合優化的思想，建立“梯度匯聚”機制下每個節點發往匯聚節點的優化路由，并同時確立每個節點無沖突的時隙調度表。為了避免不同節點在建立路由和時隙調度表的過程中發生信號沖突，所有節點逐個輪流建立自己的優化路由和時隙調度表。因為優化路由的建立過程與時隙建立過程分別依賴不同方向的累積效應，將該階段劃分為2個子階段：節點優化路由建立子階段和節點時隙調度表的建立子階段。

為了方便節點建立優化路由和時隙調度表，每個節點都建立了2張表，內層圓環的鄰居節點信息表和節點的時隙情況表，例表分別如表1與表2所示。

表1中存儲的是節點的相鄰內層圓環中鄰居節點的信息。其中，NodeID是鄰居節點的ID，relayed是需要通過本節點中繼(轉發)數據分組的節點數量。Emin是節點發送一個數據分組到達匯聚節點過程中的最小能耗，dist是本節點到該鄰居節點的距離。assigned_slots[m]表示節點在數據匯聚階段相應的接收子周期內時隙占用情況的數組，1表示該時隙已被占用來接收某節點信號，0表示空閑。注意第1層圓環中節點的表1只需要記錄匯聚節點的相關信息。表2中存儲的是節點在一個子周期的每個時隙的情況表，包括節點在相應時隙內是否處于接收狀態receiving(1表示節點在該時隙內處于接收狀態)和每個時隙的累積干擾信號功率Pinterfere，用于計算SINR。網絡初始化時，2張表為空表。節點在建立路由和時隙調度表的過程中，不斷完善這2張表。

表1 鄰居節點信息

表2 節點時隙情況

5.2.1 節點優化路由建立子階段

以圖5所示為例，顯示了位于圓環Ci中的節點A使用算法1確立下一跳目的節點的過程，算法1具體步驟描述如下。

1) 節點A從表1中挑選負載（relayed）不超過τ的相鄰內層圓環中鄰居節點，即relayed≤τ(τ為節點允許通過本節點轉發的節點數量最大門限值，這樣做的目的是均衡同一層圓環內節點的負載)，并保存到集合Set中。

2) 若集合Set不為空，則以集合Set中的節點為A的中繼節點，結合表1中的相關信息，根據式(15)計算Emin(A)，并獲得中繼節點B，確定該鄰居節點B為下一跳目的節點，進入步驟4)。

3) 若集合Set為空，則τ=2τ，返回步驟1)。

4) 節點A設置發射功率為Ptm，發送消息RTS，消息中包含下一跳目的節點B的NodeID、節點A的梯度值(HC)和最低總能耗Emin(A)。

5) 節點B收到消息RTS后，修改表1中相應內容，然后以功率Ptm發送消息CTS。

6) 若節點A相鄰外層圓環中的鄰居節點收到RTS，如節點D，則據無線信號強度值RSSI（received signal strength indicator）來獲得2個節點的相對距離dist，根據式(4)可得

其中，β=2，Precv為接收端接收到的信號功率。

然后，節點D更新其表1中與節點A對應的相應內容（Emin，dist等）。

7) 若節點B相鄰外層圓環中的鄰居節點收到CTS，如節點F，則更新其表1中與節點B對應的相應內容（relayed=relayed+1）。

節點A完成上述RTS/CTS握手過程后，進入休眠狀態直至節點時隙調度表的建立子階段。

需要注意的是，根據文獻[17]的論證，不同層內節點的能耗是不可能完全均衡的，所以算法1確保同一層圓環內節點的負載均衡。

圖5 RTS/CTS握手過程

圖6給出網絡中節點優化路由的建立過程：首先，由第1層圓環中的節點輪流執行算法1，但要注意此時節點的目的節點只能是匯聚節點，并通知第2層圓環中的節點更新相關信息；然后，第2層圓環中的節點輪流執行算法1，確定其位于第1層圓環中的下一跳目的節點，并通知第3層圓環中的節點更新相關信息；接著第3層，…，直至最外層圓環中節點完成此路由建立過程。

5.2.2 節點時隙調度表的建立子階段

在所有節點均確立了下一跳目的節點后，網絡進入節點時隙調度表的建立子階段。如圖6所示，該子階段與節點優化路由建立的過程相反，所有節點按照由外到內的圓環順序輪流建立時隙調度表。即先由最外層圓環的節點先輪流確立發送時隙，建立時隙調度表，再由次外層圓環的節點建立時隙調度表，…，以此類推，直至第1層圓環。

圖6 節點優化路由及工作時隙的建立順序

該子階段中，每個節點都需要維持變量load記錄一個數據采集周期內自己需要發送的數據分組數量，包括轉發的數據分組和自己生成的數據分組，初始值為1。因為數據匯聚階段中，一個時隙的長度等于節點發送一個感應數據分組所需的時間，所以節點需要的時隙數量等于load。節點在確立一個發送時隙時，既要判斷目的節點在此時隙內是否是空閑的，還要判斷此次發送是否會影響該時隙內處于接收狀態的非目的節點的接收過程。DDSM 擬采用RTS/Final_RTS/CTS握手的辦法來解決該問題，即通過多次向鄰居節點廣播試探性RTS消息，直至沒有收到否定應答幀NAK來確定發送時隙。

位于圓環Ci(1

1) 節點A從表1中選擇下一跳目的節點B的最小空閑時隙，并根據式(13)計算節點A發送信號所需的最小發射功率，然后以最大發射功率發試探性的請求消息RTS，消息中包含欲請求的時隙號ReqSlot與的值。

2) 圓環Ci-1中的節點(除節點B)收到該RTS，則判斷自己在節點A的請求時隙內是否處于接收狀態，若處于接收狀態，則將節點A到節點B的信號發送視為對自己的干擾，結合節點A的發射功率，并根據表 2和式(3)計算SINR，若小于SINRthreshold則發否定應答消息NAK。

3) 目的節點B收到該RTS后，也根據表2和式(3)計算SINR，若小于SINRthreshold則同樣發否定應答消息NAK。

4) 節點A收到NAK或探測到有沖突發生，則說明該請求時隙被否定，重新從鄰居節點信息表中選擇下一跳目的節點B次小的空閑時隙，再次以最大功率PtMax發試探性的請求消息RTS，返回步驟2。

5) 節點A發了RTS后在大小為TimeOut的后續時間內沒有收到NAK或探測到有沖突發生，說明請求成功，節點A以最大功率PtMax再發最終的請求消息Final_RTS。

6) 目的節點B收到消息 Final_RTS后，修改load（load=load+1）及表2中對應時隙的接收狀態（receiving），以最大功率PtMax發送消息CTS；而節點A在相鄰內層圓環中的其他鄰居節點收到消息Final_RTS后，修改表2中對應時隙的累積干擾信號功率Pinterfere。

7) 節點B的相鄰外層圓環中的節點收到消息CTS后，更新其表1中節點B對應的空閑時隙表assigned_slots[m]，把請求時隙的對應位設置為1，表示該時隙已經被占用。

因為一個時隙只能發送一個數據分組，而每個節點有load個數據分組需要發送，所以節點重復執行load次算法2，申請load個時隙。

圖7描述了算法2的一次執行過程（節點I與節點J位于圓環Ci-1中，且為A的鄰居節點）：首先，A發送請求消息RTS；節點I收到后，經判斷，發送否定應答消息NAK；節點A收到NAK后，重新選擇請求時隙，并再次發送請求消息RTS；節點J收到后，經判斷，再發否定應答消息NAK，…，此過程一直重復，直到沒有收到NAK或探測到沖突，于是發消息Final_RTS確認請求時隙，目的節點B發送消息CTS回應。

圖7 時隙請求算法中的消息

當第n層到第2層中的節點完成時隙調度表的建立后，第1層圓環中的節點則輪流直接向匯聚節點發送請求消息RTS，匯聚節點回復消息CTS，包含允許節點發送的發送時隙。

6 相關參數分析

6.1 參數m分析

DDSM中，參數m是一個數據采集周期中每個子周期的時隙數量，并且單個時隙的長度等于節點發送一個感應數據分組所需的時間。如果m的值過小，則可能會造成節點在其相應的發送子周期中沒有足夠的時間發送完所有的數據分組；如果m的值過大，則會增加感應數據傳遞到匯聚節點的時延。

由于感應數據是按梯度逐級向匯聚節點傳遞的，每層圓環的節點都需要轉發外層圓環中節點的感應數據。很明顯，各層圓環中節點所需要發送的數據分組是不相同的，內層圓環中的節點需要發送的數據分組往往較外層圓環中節點的數據分組多，也就需要更多的發送時隙。特別地，第一層圓環中的節點需要發送網絡中所有節點的感應數據分組，包括轉發的數據分組和節點自身生成的數據分組，而且第一層圓環中的節點只能將數據分組發送給匯聚節點，匯聚節點只能逐個接收每個節點的數據分組，所以第一層圓環中的節點發送數據相應的子周期內需要最多的時隙。所以，m應當滿足

其中，N為網絡中節點的數量，ρ為節點分布密度，SA為監控區域面積。

6.2 參數ω分析

如圖8所示，任一節點Q位于圓環Ci，與sink的距離為r。深色區域為節點Q的下一跳可達區域，即位于該區域的節點才能夠接收節點Q的數據，若該區域沒有節點，則造成該節點無法連通，并發送數據。根據文獻[18]，因節點均勻分布，所以節點的部署服從泊松分布，于是，可通過式(18)計算該節點可以連通的概率p。

其中，Sq為節點下一跳可達區域的面積。顯然，p與Sq正相關。根據式(11)，ω（0＜ω＜1）的大小決定了圓環的寬度d。若ω越大，則d越大，網絡中的圓環數量越少，但節點的可達區域（尤其是位于圓環外邊緣的節點）的面積越小，網絡連通性變差；ω變小，節點的可達區域面積增加，網絡連通性變好，但是d減小造成網絡中的圓環數量增加，網絡數據匯聚的總能耗也隨之增加。所以，在滿足節點的連通的概率p大于門限值pt的情況下，合理選擇ω的值。要使p＞pt，則根據式(18)，Sq要滿足

圖8 任意節點Q的下一跳可達區域

若Q位于圓環Ci的外邊緣上(r=id)，結合圖8，Sq可通過式(20)獲得。

顯然，位于圓環Ci的外邊緣上節點的Sq小于該圓環內其他節點的Sq，若位于圓環Ci的外邊緣上節點的Sq滿足式（19），則所有節點的連通性可以得到保證。因網絡中圓環數量有限，采用一種啟發式算法來快速獲得該問題的近似解，描述如下。

1)ω初值取0.99；

2) 利用式(11)計算圓環的寬度d；

3) 利用式(20)計算每層圓環的外邊緣節點的Sq，然后利用式(19)判斷這些節點的連通的概率p是否大于門限值pt；若均滿足條件，則確定ω的值，并退出；否則ω=ω-Δ(Δ為一較小的數，如0.1)，返回步驟2)。

7 性能分析

7.1 模擬實驗環境設置和參數

利用 OPNET作為模擬實驗平臺，對所提DDSM機制進行評估和分析。仿真實驗中，所有節點均勻分布于一個半徑為L的圓中，匯聚節點位于圓心處，且整個圓被劃分為n個寬度為d的圓環。如無特別指定，所有的實驗參數設置如表3所示。

表3 模擬參數

根據式(7)和表3中的參數，可以計算出節點的最大無線傳輸距離R=125 m。正如本文4.1節所述，為了避免隱藏節點問題，需要減小節點發送感應數據的最大發送功率，從而減小接收節點的干擾節點區域。于是，節點發送感應數據的最遠距離由R縮短為rm（式(10)），而每層圓環的寬度d也隨之調整（式(11)）。

另外，為了確保網絡具有很好的連通性，假設節點連通的概率門限值pt=0.95，使用6.2節中的啟發式算法來獲取合理的ω值，使所有節點連通的概率p大于pt，同時使用式(11)計算此時每層圓環的寬度d。經計算，可得ω=0.6，d=33.5 m。如無特別值，ω和d分別設置為0.6和33.5 m。

根據相應的仿真參數，實驗中所采用網絡的拓撲結構如圖9所示。其中，匯聚節點位于圖中心。

圖9 網絡拓撲結構（n=3）

7.2 實驗結果

7.2.1 不同參數取值對網絡性能的影響

根據式(11)，ω的取值會改變網絡中每層圓環的寬度。首先分析ω的不同取值對網絡連通性的影響。

圖10反映了不同ω的取值下，通過式(18)與式(20)計算獲得的網絡中節點最低連通概率。當ω的值越大時，根據式(11)，圓環的寬度也就越大，但是每層圓環外邊緣的節點可以選擇的下一跳節點的范圍也就越小，以至于影響網絡的連通性。

圖 11反映了不同ω的取值下，網絡采用DDSM機制運行120 min后節點數據分組的成功到達率(指到達匯聚節點)。從圖中可以看出，當ω＞0.6時，數據分組的成功到達率明顯下降，這與分析計算結果吻合，說明分析正確。后面的實驗中，為保證網絡的連通性，門限值pt取值0.95，ω則取值0.6。

圖10 不同ω下的節點最低連通概率（n=3）

圖11 不同ω下的數據分組成功到達率（n=3）

接下來分析節點允許轉發的節點數量最大門限值τ對數據分組的成功到達率的影響。當τ的取值比較小時，每個節點作為中繼節點，允許轉發的節點數量得到了嚴格的限制，避免了個別節點頻繁被作為中繼節點，從而過早地耗盡了能量。但是如果τ的取值過小，部分節點可能會找不到下一跳目的節點，從而影響了網絡的連通性。圖 12給出了不同的τ值對數據分組的成功到達率的影響，從τ=2開始，數據分組成功到達率逐漸提高，當τ=4時，數據分組成功到達率達到了90%。

7.2.2 與其他數據收集機制比較

為了評估 DDSM 的性能，比較 AIMRP[9]、S-MAC[5]、LEMMA[12]和DDSM這4種數據收集協議在數據分組成功到達率和功耗方面的性能。S-MAC協議中，假設節點采用最小跳路由到達匯聚節點。

如圖13所示，在4種數據收集協議都不允許數據分組發送失敗重傳的條件下，比較4種協議的數據分組成功到達率。從圖 13可以看出，當圓環的數量增加時，即網絡的規模擴大時，采用AIMRP和S-MAC這2種協議的數據分組成功到達率不斷下降，而DDSM和LEMMA的數據分組成功到達率則基本維持在90%以上。這是因為AIMRP協議每次發送數據分組都需要通過 RTR/CTR/DATA/ACK握手機制實現，過程繁瑣，動態適應性差，只能適用于小范圍的事件驅動型傳感器網絡。S-MAC協議采用周期性的偵聽/睡眠機制，其偵聽/睡眠時間不能根據網絡中負載的變化動態調整，而且 S-MAC協議采用退避發送機制來降低節點間碰撞的概率，當網絡規模擴大時，網絡中數據量增加，采用 S-MAC協議網絡的信道碰撞的幾率急劇增大，易導致網絡堵塞，使網絡的數據分組成功到達率急劇下降。而本文所提的DDSM和LEMMA都采用TDMA機制，充分考慮了干擾和沖突避免，數據匯聚階段沒有數據碰撞重傳的問題，所以網絡規模的擴大對數據分組成功到達率影響不大。

圖12 不同τ下的數據分組成功到達率（n=3）

圖13 不同圓環總數下數據分組成功到達率

圖14給出了網絡采用4種數據收集協議在不同的數據采集周期(T)下的數據分組成功到達率。從圖 14中可以看出，當數據采集周期變大時，即節點的感應數據分組產生頻率降低時，網絡采用DDSM 和 LEMMA協議時的數據分組成功到達率基本保持不變，且維持在90%以上，這是由于這2種協議采用TDMA機制；而AIMRP和S-MAC這2種協議的數據分組成功到達率則相應增加，這是由于隨著感應數據分組產生頻率的降低，節點間碰撞的概率也相應降低。

圖14 不同數據采集周期下數據分組成功到達率

圖15給出了網絡采用4種數據收集協議在不同的節點分布密度下數據分組成功到達率。從圖15可以看出，當節點分布密度增加時，即網絡中節點數量增加，DDSM和LEMMA變化不大，保持在90%以上。DDSM的數據分組成功到達率甚至略有增加，這是因為節點數量的增加提高了節點下一跳可以連通的概率（式(18)），而AIMRP和S-MAC這2種協議的數據分組成功到達率則不斷下降，這是因為節點數量的增加也增加了網絡信道碰撞的幾率。

圖15 不同節點分布密度下數據分組成功到達率

圖16給出了網絡采用3種數據收集協議時節點平均功耗的比值，分別是AIMRP與DDSM的比值，以及S-MAC和DDSM的比值。圖16充分體現了DDSM能量高效的特點，也說明了DDSM中采用的 TDMA機制非常適合無線傳感器網絡節省能量的要求，當網絡中的節點建立了優化路由與時隙調度表后，在感應數據向匯聚節點傳輸的過程中不需要多余的控制信息，也沒有數據碰撞重傳的問題；AIMRP協議中的RTR/CTR/DATA/ACK握手機制，過程繁瑣且耗能；S-MAC協議要求節點周期性的偵聽，并且節點還需要周期性的廣播自己的調度信息，這都大量的消耗了節點的能量。需要注意的是，圖 16中，在網絡中僅有一個圓環時，與網絡中具有多個圓環的情況相比，DDSM中節點的平均功耗要遠低于其他2種數據收集協議，這是因為網絡中僅有一個圓環時，節點不再需要轉發來自外層圓環中節點的數據，只需要把自身感應數據發給匯聚節點，所以在DDSM中，此時節點無需進入偵聽狀態，也就降低了節點的功耗。可見，空閑偵聽的能耗在節點的總能量消耗中占據了較大的比例。

圖16 采用不同協議時節點平均功耗的比值

圖17給出了網絡分別采用DDSM和LEMMA協議時，在不同圓環的總數下節點的平均功耗。可以看出，網絡采用LEMMA協議時，節點的功耗較高，這是因為LEEMA采用的最小跳數路由并不一定是最小能耗路由，其節能效果不如DDSM。

圖18反映了網絡分別采用DDSM和LEMMA協議時，在不同圓環的總數下網絡的生命周期比較。其中，網絡中各節點的初始能量為1 mJ，網絡的生命周期值定義為從網絡開始運行持續到網絡中 1%的節點耗盡能量為止。可以看出，網絡采用DDSM 協議時的生命周期較網絡采用 LEMMA協議時長，這是因為DDSM中，節點在選擇路由時既考慮了路由的能耗，又限制了節點作為中繼節點的次數，從而延長了網絡的生命周期。

圖17 DDSM和LEMMA下節點的平均功耗

圖18 DDSM和LEMMA下網絡的生命周期比較

8 結束語

本文分析了大規模的周期匯報型無線傳感器網絡的特點，并針對大規模的周期匯報型無線傳感器網絡提出了一種基于分布式與聯合優化的數據匯聚機制(簡稱 DDSM)。該機制采用分布式與跨層設計的思想，融合MAC層與網絡層功能，設計基于分布式的跨層數據匯聚機制及其實現算法，有效提高了網絡的能量利用效率，降低了網絡的成本，延長了網絡的生命周期。

[1] 朱紅松, 孫利民, 徐勇軍等. 基于精細化梯度的無線傳感器網絡匯聚機制及分析[J]. 軟件學報,2007,18(5): 1138-1151.ZHU H S, SUN L M, XU Y J,et al. Mechanism and analysis on fine-grain gradient sinking model in wireless sensor networks[J].Journal of Software, 2007, 18(5):1138-1151.

[2] 王辛果, 張信明, 陳國良. 時延受限且能量高效的無線傳感器網絡跨層路由[J]. 軟件學報, 2011,22(7):1626-1640.WANG X G, ZHANG X M, CHEN G L. Delay- constrained and energy-efficient cross-layer routing in wireless sensor networks[J]. Journal of Software, 2011, 22 (7):1626-1640.

[3] LUCAS D P, MENDES, JOEL J P C,et al. A survey on cross-layer solutions for wireless sensor networks[J]. Journal of Network and Computer Applications, 2011, 34(2):523-534.

[4] WENDI B. HEINZELMAN, ANANTHA P,et al. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans. Wireless Comm., 2002, 1(4):660-670.

[5] YE W, JOHN H,et al. An energy-efficient MAC protocol for wireless sensor networks[A]. Proc IEEE INFOCOM[C]. 2002.1567-1576.

[6] 李哲濤,朱更明,王志強等.低占空比、低碰撞的異步無線傳感器網絡MAC協議[J].通信學報, 2013,34(10):9-16.LI Z T, ZHU G M, WANG Z Q,et al. Low duty cycle and low collision asynchronous MAC protocol for wireless sensor network[J].Journal on Communications, 2013,34(10):9-16.

[7] GEOFFREY G. MESSIER, JENNIFER A,et al, DAVIES. A sensor network cross-layer power control algorithm that incorporates multiple-access interference[J]. IEEE Transactions on Wireless Communications, 2008, 7(8):2877-2883.

[8] 李方敏, 劉新華, 徐文君等. 無線傳感器網絡的鏈路穩定成簇與功率控制算法[J]. 計算機學報, 2008, 31(6): 968-978.LI F M, LIU X H, XU W J,et al. Link-stable clustering and power control for wireless sensor networks[J]. Chinese Journal of Computers,2008, 31(6):968-978.

[9] KULKARNI S, IYER A, ROSENBERG C. An address-light, integrated MAC and routing protocol for wireless sensor networks[J].IEEE/ACM Transactions on Networking, 2006, 14(4):793-806.

[10] SHI L Q, ABRAHAM O, FAPOJUW O. TDMA scheduling with optimized energy efficiency and minimum delay in clustered wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2010,9(7):927-940.

[11] 鄭國強, 李建東, 周志李. 多跳無線傳感器網絡的高能效數據收集協議[J]. 軟件學報, 2010, 21(9): 2320-2337.ZHENG G Q, LI J D, ZHOU Z L. Energy-efficient data gathering protocol for multihop wireless sensor networks[J]. Journal of Software,2010, 21(9): 2320-2337.

[12] MACEDO M, GRILO A, NUNES M. Distributed latency-energy minimization and interference avoidance in TDMA wireless sensor networks[J]. Computer Networks, 2009, 53(5):569-582.

[13] 曾志文, 陳志剛, 劉安豐. 無線傳感器網絡中基于可調發射功率的能量空洞避免[J], 計算機學報, 2010, 33(1):12-22.ZENG Z W, CHEN Z G, LIU A F. Energy-hole avoidance for WSN based on adjust transmission power[J]. Chinese Journal of Computers,2010, 33(1):12-22.

[14] RAPPAPORT T. Wireless Communications: Principles and Practice[M]. Prentice Hall, New Jersey, 1996.

[15] 張克旺,張德運,杜君.面向多跳無線網絡的無沖突MAC協議[J]. 軟件學報, 2009,20(7):1895-1908.ZHANG K W,ZHANG D Y,DU J. Collision free MAC protocol for multi- hop wireless networks[J]. Journal of Software, 2009,20(7):1895-1908.

[16] XU K X, GERLA M, SANG B. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[A]. Proc of the IEEE Global Telecommunications Conf[C]. 2002.72-76.

[17] 吳小兵,陳貴海.無線傳感器網絡中節點非均勻分布的能量空洞問題[J].計算機學報,2008,31(2):253-261.WU X B, CHEN G H. The energy hole problem of nonuniform node distribution in wireless sensor networks [J]. Chinese Journal of Computers,2008,31(2):253-261.

[18] WANG Y, WANG X D, XIE B,et al. Intrusion detection in homogeneous and heterogeneous wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2008,7(6):698-711.