基于二次獨立集的數據融合調度算法

許建，楊庚，陳正宇，王海勇，楊震

(1. 南京郵電大學 寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003；

2. 南京郵電大學 計算機學院，江蘇 南京 210003；3. 金陵科技學院 信息技術學院，江蘇 南京 211169)

1 引言

無線傳感器網絡由具有感知能力、存儲能力和通信能力的無線節點組成，大多數情況下節點在資源方面受到很多的限制，其中最為突出的是節點能量方面的受限。因此，如何降低節點的能耗，延長網絡節點的生命周期成為無線傳感器網絡應用的關鍵問題。

在傳統的無線網絡中，媒體訪問控制協議（MAC）是決定網絡生命周期的關鍵因素，這一點對于無線傳感器網絡同樣適用。現有的傳感器網絡MAC協議基本上可分為2類，基于競爭的訪問控制協議和時分復用的訪問控制協議。其中，基于競爭的訪問控制協議，如IEEE 802.11，在沖突處理和監聽過程中會浪費大量的能量消耗。而對于TDMA協議來說，節點按照預先分配的傳輸時隙進行數據的發送和接收，在避免了由于沖突而造成能量消耗的同時也保證了數據聚集過程的時延[1]。文獻[2]中對2種MAC協議下的網絡生命周期進行了測試，相同條件下TDMA協議的能耗僅為IEEE 802.11協議的約1/120，可見TDMA協議在降低能耗方面要顯著優于基于競爭的訪問控制協議。

另一方面，數據融合技術也是降低節點的能耗，延長網絡生命周期的重要手段。數據融合是多跳網絡中數據聚集和路由的一種方式，其特點是數據采集的中間節點在收到不同信息源的數據后，以去除冗余信息為目的對所接收到的多個數據進行融合處理，進而能夠實現減小傳輸數據量，降低節點由于大量數據傳輸而帶來的能量消耗，延長網絡生命周期[3]。

綜合以上2個方面，在數據融合聚集的過程中采用TDMA為MAC層協議，可以從不同層次減少節點的能量消耗。在時分復用的無線傳感器網絡中，數據融合技術的關鍵在于融合調度策略，衡量融合調度算法有效性主要體現在以下3個方面。首先通過合理調度降低由于沖突而造成的網絡傳輸時延增加；其次，由于多次通信和融合操作會造成網絡中節點能耗的增加，融合調度過程應該盡可能地減少調度次數，并實現節點間能量消耗的平衡，進而延長網絡的生命周期；第三，加權公平性保證，即對于具有不同權重的數據應該區別對待，保證高優先級的數據優先調度。然而，現有算法大多僅針對其中的某一個方面進行了相應研究。如文獻[4,5]主要從融合樹構建的角度分析了如何進一步降低融合過程的能量消耗、延長網絡的生命周期；文獻[6~8]從降低融合過程時延的角度對基于 TDMA的數據融合調度算法進行了研究，并分別提出了不同的低時延調度策略；而文獻[9]則單純考慮加權公平性，并沒有涉及其與另外兩方面性能的平衡。總體來說，這些研究成果均沒有綜合考慮3個方面的因素，因而各自具有不同的局限性。

針對上述不足，本文從調度算法的3個有效性指標入手，通過分析融合樹結構以及調度算法對各方面性能的影響，提出了一種基于二次獨立集的TDMA融合調度算法 MISS(twice maximum independent set based aggregation scheduling algorithm)。該算法由 2個子算法組成：基于最大獨立集的數據融合樹構建算法(T-MIS)和基于最大獨立集的數據融合調度算法(S-MIS)。T-MIS以最大獨立集方法構建樹型結構，并根據節點能量消耗預測模型對樹結構進行調整和優化，最終構造出能量消耗平衡的數據融合樹。S-MIS根據融合樹中的鏈路沖突關系構建近似最大加權獨立集，最終確定每個時隙中的傳輸鏈路序列；并在該過程中，重點研究了不同鏈路權重參數設置下融合調度策略的調整方法。

2 問題描述

1) 所有節點采集的數據均被匯聚到sink節點；

本文中對于沖突的定義，采用協議沖突模型[10]，約定網絡中任意節點均可以發送和接收數據，但二者不能同時進行，且所有節點的干擾半徑均相同，記為Ir。

定義1 鏈路沖突。在協議沖突模型中，2個通信鏈路沖突，當且僅當其中一個鏈路的接收端在另一個鏈路發送端的干擾半徑范圍內。

如圖1所示，節點j的父節點jP在節點i的干擾半徑范圍內，則通信鏈路ie和je是相互沖突的。

圖1 鏈路間沖突關系

根據引言中的分析，構造出的調度序列應該盡可能同時滿足3個方面的特性需求。相關定義如下。

定義2 融合時延。對于一次數據聚集過程，若所有節點采集的信息經過 t個時隙后全部到達 sink節點，即，則該融合周期的時延為t，記做

對于任意結構的數據融合樹，其融合延時有

其中，ξi和hi分別表示節點i在該樹中子節點的個數以及該節點到樹根節點的跳數，Baljeet等人在文獻[11]中對該問題予以了證明。

由于傳感器節點所監測區域的重要性不同，每個節點被分配一個反映其重要性的權值，節點i的權重值表示為 wi。直觀地，如果 wi＞wj，則希望i節點采集的數據能夠比 j節點采集的數據更早到達sink節點。為了量化這種加權公平性，本文使用平均加權時延作為公平性度量，其定義如下。

定義 3 平均加權時延。在一個融合周期內，若G中節點i采集的數據共經歷了 ti個時隙后到達sink節點，則該節點數據的加權時延為 Di= wi× ti，融合周期內所有節點的平均加權時延可計算為

圖2為一種平均加權時延計算示例，圖2(a)中給出了一個由3個節點組成的數據融合樹，其中，；圖 2(b)對 2種可能調度序列下的avg分別進行了計算。在第1種調度序列中，t1和 t2分別為1和2，所以；同理，若調度序列為{e1} }，則 D avg= 2 .5。顯然，即使這2種不同調度策略具有相同的融合時延，但其對加權公平性的保證也可能是不同的。

圖2 平均加權時延計算示例

定義4 網絡生命周期。對于任意調度算法，若經歷了L個融合周期后網絡中出現了第一個能量耗盡的節點，則稱該調度算法下的網絡生命周期為L。

在基于TDMA機制的數據融合過程中，節點主要有3種不同狀態，發送、接收和睡眠，其中，睡眠狀態下的功耗遠遠小于其他2種狀態[12]，文中將該狀態下的能量消耗忽略不計。此時，每個融合周期內節點 i的能耗可計算為，其中， pt、 pr分別表示節點進行一次發送和接收的能耗，ti和 ri則表示節點i發送和接收的次數。假設所有節點具有相同的初始能量EN，則對于任意的數據融合樹其生命周期可表示為

從以上對3種性能的定義和分析可以看出，融合算法的性能主要和融合樹結構以及調度策略有關。因此最優的融合調度即通過以上2個步驟構造出調度鏈路集合序列實現min(d)、min(D avg)以及max(L)3個方面性能平衡。因此，本文提出的MISS算法分為融合樹構建和融合調度2個階段，其具體實現過程將在接下來分別進行闡述。

3 基于最大獨立集的數據融合樹構建算法T-MIS

3.1 算法思路

融合樹的構建是數據融合過程的準備工作，在所有基于樹的數據融合過程中均需要預先建立起一個融合樹結構。之所以選擇樹型結構，主要有2個方面的原因：首先無線傳感器網絡中僅有一個或極少量基站節點，樹結構很適用于這一類型的網絡環境中；另一方面，樹結構自身的特點有助于節省傳輸中的能量開銷，這對于能量受限的無線傳感器網絡來說尤為重要[9]。然而最優融合樹構造已被證明是NP-hard問題[13]，現有的融合樹構建算法均是從某一方面出發的近似優化算法，主要焦點集中在如何延長網絡生命周期或降低融合時延等。從現有的研究成果分析，融合樹對生命周期和時延性能的影響主要包括2個方面因素，樹中節點的度數以及樹的深度。

文獻[14]中提出了一種融合樹構建算法。該算法通過最大獨立集構造出最小連通支配集，并以該支配集為樹干生成樹結構。由最小連通支配集的定義可知，該樹結構具有葉子節點最多而樹的深度最小等特性，從而可以增加節點間并發通信的幾率，減少中間轉發次數，進而降低融合時延。但該算法并沒有考慮節點的能耗平衡，容易產生由于局部節點能量耗盡而導致的網絡生命周期縮短。無線傳感器網絡中節點處理器執行指令的能耗遠小于數據傳輸的能耗，節點的能量消耗主要取決于其發送和接收數據的次數。為了減少能量消耗，往往會限制節點發送數據的次數，此時子節點最多的節點將成為整個網絡中能量最先耗盡的瓶頸節點，顯然為了延長網絡的生命周期必須實現樹中節點的度數平衡。為此，T-MIS在構造出該樹型結構后，再根據節點的能量消耗預測對樹結構進行調整。能量消耗預測指的是根據節點在樹中的位置對其在融合過程中可能消耗的能量進行的估計。

3.2 算法描述

算法1 數據融合樹構建算法T-MIS。

1) 以 vs為根，r為網絡半徑，構造G的廣度優先搜索樹；

2) 對所有vi∈V，C(i)=White，Mark(i)= 0 ，

4) 對于收到 M esg(B)節點 vj，如果則，廣播 M esg(G)；

5) 對于 vj，如果，且所有 vi,且，都向其發送了 M esg(G)，則，廣播 M esg(B)；

7) 根節點 vs廣播 M esg(Gjoin)；

8) 對于收到 M esg(Gjoin)的節點 vi，如果且vi?DS

② 廣播 M esg(Bjoin)；

③ M ark(i)=1；

9) 對于收到 M esg(Bjoin)的節點 vi，如果Mark(i) = 0，C(i)=Black且vi?DS

① vi→DS（Pi為Mesg(Bjoin)的發送節點）；

② 廣播 M esg(Gjoin)；

③ M ark(i)=1；

10) 以DS為樹干，其余節點為葉節點（ Pi為其支配節點）形成樹結構；

11) 對所有非根節點vi∈V，標記其子節點個數為

該算法中首先構造G的廣度優先搜索樹，若節點 i所在的層數為 leveli，則標記 R (i) = ( l e veli,i )；算法經過前 5個步驟后，所有黑色節點構成一個支配集，即然后通過步驟7)~10)構造出一個連通的樹型結構；最后對所有非根節點選擇子節點最少的上層節點為父節點，形成最終的數據融合樹，記為。圖3為T-MIS算法的執行過程示例。如圖3(a)所示，該網絡中共有15個節點，其中，sink節點s位于網絡的拓撲中心。算法中首先通過構造最大獨立集(MIS)的方法形成網絡的最小連通支配集(圖 3(b)中的灰色節點)；以該連通支配集為樹干，連接形成樹型結構如圖3(c)所示；最后，根據能量消耗預測進行調整，最終形成一個平衡融合樹如圖3(d)所示。

4 基于最大獨立集的數據融合調度算法S-MIS

4.1 算法思路

調度算法的最終目的是為節點分配傳輸時隙，本文提出了基于近似最大加權獨立集的調度算法，其主要過程分為 2個步驟。首先，選中樹中允許通信的鏈路集合，通過融合樹結構中鏈路間的沖突關系，構建鏈路沖突矩陣，然后在沖突矩陣的基礎上，通過構造近似最大加權獨立集確定每個時隙中的通信鏈路集合。特別要強調的是，已有算法中，為了最大程度降低節點的能耗，都采用了每個鏈路僅調度一次的限制策略，但是這種策略無法保證對高權重數據的優先調度（即加權公平性保證）。但如果對鏈路的通信次數不做任何限制又會造成網絡能耗的急劇增加，可見如何調整通信次數是在低加權時延和高生命周期之間實現性能平衡的關鍵。為此，S-MIS算法采取了折中的調度策略，相關定義如下。

圖3 數據融合樹構建過程

定義5 邊沿鏈路集。對于樹 T = ( V,E?)，若經歷t-1個時隙后，節點vi的所有子節點均被調度完畢，則以vi為發送端的鏈路ei為t時刻樹T的邊沿鏈路，記 F LS(T )t為t時刻樹中所有邊沿鏈路的集合。

圖4中給出了2個不同時隙內邊沿鏈路集選取的示例。在t=1時，樹中所有以葉子節點為發送端的鏈路均為邊沿鏈路，即當經過n-1個時隙后，黑色節點均被調度完畢，此時有

定義6 累積權重。對于 ei∈E?，t時隙中，節點i中仍未被傳輸數據的權重之和稱做該鏈路上的累積權重，記做 A CW(ei)t。

圖4 不同時隙內邊沿鏈路集的選取

定義7 激活鏈路集。時隙t中可以作為調度對象的鏈路集合，包括邊沿鏈路以及累積權重達到閾值 δ的非邊沿鏈路，記 t時刻的激活鏈路集合為ALS(T )t，則

定義 8 沖突鏈路集。對于不在鏈路集合 Et中的 ei，若 ei和 Et中的n個鏈路沖突，則稱這n個鏈路組成的集合為 Et中 ei的沖突鏈路集，該集合中所有鏈路權重的和為 ei相對于 Et的沖突集權重。

在限定鏈路通信次數的調度算法中，僅將邊沿鏈路作為調度的對象，所以即使出現了需要優先調度的中間鏈路，在其成為邊沿鏈路之前均得不到調度。而S-MIS中，將激活鏈路集作為調度對象，通過設置閾值δ將高優先級的中間鏈路納入到調度對象中，并可以通過對δ的調整實現加權時延和能量消耗之間的性能平衡。以圖4(b)中的調度對象為例，假設，則

除了通過選取激活鏈路作為調度對象外，為了保證對高權重數據的優先傳送，本文希望能夠構造出每個時隙內激活鏈路集合的最大加權獨立集作為該時隙內的調度序列，但由于該集合的求解過于復雜，本文提出了一種構造最大加權獨立集的近似算法。

4.2 算法描述與分析

算法2 數據融合調度算法S-MIS。

2) 對每個標記為未調度的鏈路 ei，如果 ei∈FLS(T )t或，則

3) 構造 A SL(T )t中鏈路的沖突矩陣 I Mt，若ASL(T )t中第i和j個鏈路在T中沖突，則

4) 構造以 I Mt為鄰接矩陣的最大獨立集MISt；

5) 對于所有不在 M ISt中的激活鏈路 ej，若 ei未調度則以其累計權重從高至低進行如下操作：

若 A CW(ei)t大于其相對于 M ISt的沖突集權重，則在 M ISt中以 ej取代其沖突鏈路集，構造出近似的最大加權獨立集 M WISt；

8) 如果 DAT中仍有標記為未調度的鏈路，則t = t + 1，轉至步驟2)；

算法2的輸出結果即為每個時間片中傳輸的鏈路集合，該集合必滿足以下3個條件：

2) 每個節點采集的數據均到達sink節點；

證明 首先，對于DAT鏈路集合E?中任意元素ei，顯然有 ei∈E?。若算法執行完畢后仍然有鏈路有，則經過t個時隙后，DAT中仍有未調度的鏈路，與題設矛盾，因此必有另一方面，對于任意鏈路，則ej必是DAT中的一個邊，即有 ej∈E?。因此，必有∪ E (t )。

其次，采用反證法。假設融合周期結束后節點 i上仍有數據沒有被匯聚到sink節點。若該節點為DAT中的葉子節點，則表明由前面證明可知與題設矛盾，即 i只可能為中間節點。不妨設在第次調度后，該數據到達中間節點 i，則鏈路 ei在前面的 m - 1次調度中均不可能被標記為已調度，而由假設前提可知此后 ei也未被調度（數據依然在節點 i中），則同樣有綜上，調度完畢后必能保證所有節點的數據都被匯聚到sink節點。

最后，對于調度序列集合中的 E (s)(1 ≤ s≤t)，由算法2可知，該集合為s時刻以 I Ms為鄰接矩陣的最大加權獨立集，若，則IMs中對應元素，因此 ei, ej必然彼此不沖突。

證畢。

5 實驗結果與分析

在本節中，對MISS算法進行了仿真實現，并將其性能和已有算法DAS[7]、IAS[8]等進行了比較。表1中給出了仿真參數設置。在實驗中，節點隨機均勻的分布在200 m×200 m的區域中，假設基站節點 sink位于區域的拓撲中心。彼此間距離小于等于通信半徑r的2個節點可以相互通信；相互間不沖突的多個鏈路可以同時通信，本文實驗中將干擾半徑取值為Ir r= ；所有節點具有相同的初始能量EN=1 000，為了不失一般性，參考文獻[15]中的測量結果，將節點進行一次發送和接收所消耗的能量分別取值為 Pt=2，Pr=1；節點的權重為 0～10之間的隨機數。

表1 仿真參數設置

為了全面深入地對算法性能進行比較分析，本文共設計了3組不同的仿真實驗，每組中均對算法在融合時延d，平均加權時延Davg以及生命周期L 3個方面的性能進行了比較。實驗中對于節點密度ρ的定義采用和文獻[11]相同的表示方法，即，在通信半徑相同的情況下，節點數量是影響密度的唯一因素。

由于現有調度算法大多沒有考慮節點權重的因素，為了和這些算法進行性能比較，第一組實驗中首先假設所有節點的權重均為 1，此時累計權重ACW(ei)t表示t時刻節點i中未傳輸的數據個數。并設置MISS算法中閾值δ為節點個數N，融合過程中沒有中間鏈路能夠被調度，即限制每個節點均只能發送1次。圖5~圖7為第一組實驗中算法在不同節點密度下的性能比較。

圖5 算法融合時延隨節點密度變化比較

圖6 算法平均加權時延隨節點密度變化比較

圖7 網絡生命周期隨節點密度變化比較

由圖5中的變化曲線可以看出，由于節點密度增大后，節點間沖突程度增加，所以3種算法的融合時延均隨著節點密度有較大幅度的增加。IAS算法和 DAS算法在時延方面的性能相差不大，本文提出的MISS算法相對于這2種算法來說優勢較為明顯。當節點密度從10增加到60時（節點個數約從 200增加到 1 200），前 2種算法的時延從約25個時隙增加 90左右，相同情況下 MISS算法僅從18增加到了 72。時延性能提升的主要原因在于本文算法通過構造最大獨立集的方式選取每個時隙中的發送序列，能夠在每個時隙中實現最大并發度的通信，從而更快地完成數據匯聚過程。

算法的平均加權時延同樣隨節點密度的增加而增大，其結果如圖6所示。由于本組實驗中假設將節點權重設置為1，所以3種算法在加權時延方面差異并不明顯。MISS算法由于能夠找出最大可傳輸集合，其平均加權稍優于另外2種算法。

圖7則給出了網絡生命周期隨節點密度增加時的變化情況。首先可以看出，在節點傳輸半徑不變的情況下，隨著節點密度的增加，開始階段網絡生命周期迅速減少，如ρ從10變為20時，3種算法下的生命周期幾乎均減少了一半，但隨著節點密度的進一步增加，生命周期下降的速率變得逐漸緩慢。從第2節中對網絡生命周期的定義和分析可以知道，出現這種情況的主要原因在于，ρ從10變為20時樹中節點的最大度數幾乎增加了一倍；而當節點不斷增加時，節點度數雖然還在增加但增加的比例降低了，因此生命周期會出現圖中所示的變化過程。值得一提的是，雖然此時3種算法都限定了節點的發送次數為1次，但是由于 MISS在構建數據融合樹時根據節點的能量消耗預測進行了調整，因此其生命周期要略高于IAS和DAS。

在第2組實驗中對算法在節點具有不同權重下的各方面性能進行了比較，其中MISS算法中閾值分別取值為 0、40和無窮大，實驗結果如圖 8~圖10所示。

圖8中對MISS算法在δ=0、δ=40以及δ=無窮大時融合時延性能同DAS、IAS算法進行了比較。從該圖中可以看出，當δ=0時，表示所有中間鏈路均可成為激活鏈路，MISS算法中會選擇權重較大的中間鏈路進行調度，使得此時的融合時延明顯增大。而當δ=無窮大時則表示不允許任何中間節點進行權重比較和替換，此時的融合時延在各種算法中為最優的。δ取中間值時，如δ=40，算法的融合時延也處于中間位置。對于DAS和IAS算法來說，由于它們均沒有在調度算法中考慮加權因素，所以其性能和第一組實驗基本相似。

圖8 節點具有不同權重時融合時延隨節點密度變化比較

圖9 中則對比了第2組實驗中不同算法的平均加權時延。由于本文算法MISS中以閾值δ來篩選出權值達到一定限制的中間鏈路來進行優先調度，所以此時MISS算法能夠很好地實現加權公平性保證，即優先調度那些權重更高的節點。但是如果將δ取值為 0，則會有太多的中間鏈路參與調度，將會導致融合時延的迅速增加（如圖 8所示），最終使得加權時延性能也隨之下降。通過對比實驗數據，當節點密度小于20時，加權時延對閾值δ并不敏感，節點密度大于20后，δ=40下的MISS算法具有最低的平均加權時延。

圖9 節點具有不同權重時平均加權時延隨節點密度變化比較

當節點具有不同的調度權重時，MISS算法調整調度對象后同樣會造成網絡生命周期的降低，如圖 10所示。同前面的分析類似，當閾值為無窮大時，每個節點僅能夠發送一次數據，此時的網絡生命周期最長，雖然IAS和DAS也限定了發送次數為1，但由于這2種算法中均沒有考慮節點能耗的平衡問題，所有生命周期小于閾值足夠大的 MISS算法。隨著對節點通信次數限制的放寬（主要通過調整δ），節點的能耗也會明顯的增加，最終導致網絡生命周期的減少。顯然δ越小，限制條件也就越松，節點通信的次數也就越多，進而網絡生命周期也就越短，如圖10中所示δ等于0時網絡的生命周期最短。

圖10 節點具有不同權重時網絡生命周期隨節點密度變化比較

從前面的實驗結果中可以看出閾值δ對MISS算法的性能影響非常明顯，為了進一步研究和分析算法對δ取值的敏感性，在第3組實驗中對節點數量N等于200、400和1 000這3種情況下，算法性能隨δ的變化情況進行了仿真比較。

圖11為3種不同節點數量下MISS算法融合時延隨閾值δ的變化曲線，δ的取值從0增加至320。當δ從0變化至40時，3種節點數量下的融合時延降低的非常明顯，如N=1 000時的融合時延從160左右降低至約100，減少了約40%。隨著δ取值的不斷增加，N=200的融合時延首先進入穩定階段，δ從40增加到320時，其融合時延基本穩定在18左右。

第3組實驗中平均加權時延的比較如圖12所示。通過對比不同節點數量下加權時延的變化情況可以發現，δ的取值為某一個中間值時加權時延最優。從MISS調度算法的角度來分析，在選取每個時隙中的調度隊列時，如果 δ=0，則表示選擇所有鏈路的近似最大加權獨立集，即該調度序列的權重最大，但可能鏈路數量相對較少，且其中必然有滿足條件的中間鏈路，這2種情況都會導致整體傳輸時延的增大，并最終使得加權時延總和的增加，所以此時平均加權時延并非最優。另一個方面，如果δ足夠大，則會限制中間鏈路的傳輸，增加邊沿鏈路的并發數量，進而降低融合時延，但卻無法保證加權公平性，即平均加權時延也不能得到優化。此時，需要找到最優的 δ，該數值能夠很好地在加權公平性保證和融合時延之間實現平衡，并最終得到最小的平均加權時延，如N=1 000時，δ=80其加權時延最低。

圖11 不同節點數量下融合時延隨閾值δ的變化比較

圖12 不同節點數量下平均加權時延隨閾值δ的變化比較

圖13 為不同節點數量下網絡生命周期隨閾值δ的變化情況。MISS算法和其他算法相比，其最主要的特點之一是通過閾值來調節對節點通信次數的限制。不難理解的是當δ取值為0時，表示沒有調度次數的限制，對于任意的中間鏈路，只要其權重滿足一定條件均可以多次進行通信，此時網絡的生命周期最小。隨著δ的增加，限制也越來越嚴格，只有當中間節點接收到一定數量的數據，其累計權重達到限定條件時才會被納入到激活鏈路集合中，作為可以被調度的對象。當δ增大到一定的程度時，中間鏈路成為激活鏈路的幾率將保持在穩定狀態，網絡的生命周期也隨之穩定。從實驗結果可以看出，當δ≥120時，3種節點數量下的網絡生命周期都基本保持不變。

圖13 不同節點數量下網絡生命周期隨閾值δ的變化比較

6 結束語

本文針對無線傳感器網絡中的數據融合調度問題，提出了一種基于二次獨立集的調度算法。該調度算法分為2個階段，第一階段中通過選取最大獨立集然后構成以最小連通支配集為骨干的數據融合樹；第二階段中則通過閾值δ優化允許進行調度的鏈路集合，即激活鏈路集，并將某一時刻融合樹中激活鏈路集的近似最大加權獨立集作為該時隙內的調度隊列。實驗結果分析表明，一方面該算法通過調度最大加權獨立集以降低加權時延，保證加權公平性；另一方面通過引入閾值δ調節鏈路的發送次數限制，有效地實現了加權公平性與融合時延、網絡生命周期三者之間的性能平衡。

在下一步工作中，筆者將重點研究如何在各種不同類型的數據融合下設計高性能調度算法，而不僅僅局限于本文中設定的完全融合。另外，算法在控制開銷和數據傳送成功率等方面的性能也將是一個需要深入研究的方向。

[1] ERGEN S C, VARAIYA P. TDMA scheduling algorithms for wireless sensor networks[J]. Wireless Networks, 2010, (16):985-997.

[2] ERGEN S C, VARAIYA P. PEDAMACS: Power efficient and delay aware medium access protocol for sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 5(7):920-930.

[3] FASOLO E, ROSSI M, WIDMER J, et al. In-network aggregation techniques for wireless sensor networks: a survey[J]. IEEE Transactions on Wireless communication, 2007, 14(2):70-87.

[4] LUO D J, ZHU X J, WU X B. Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. Shanghai, China, 2011.1566-1574.

[5] GHOSH A, INCEL O D, ANILKUMAR V S. Multi-channel scheduling and spanning trees: throughput-delay tradeoff for fast data collection in sensor networks[J]. IEEE/ACM Transactions on Networking, 2011, 19(6): 1731-1744.

[6] HUANG S C, WAN P J, VU C T, et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[A].Proceedings of the IEEE INFOCOM[C]. Alaska, USA, 2007.366-372.

[7] YU B, LI J Z, LI Y S. Distributed data aggregation scheduling in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C].Rio, Brazil, 2009.2159-2167.

[8] XU X H, LI X Y, MAO X F. A delay-efficient algorithm for data aggregation in multi-hop wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(1):163-175.

[9] JOO C H, CHOI J G, SHROFF N B. Delay performance of scheduling with data aggregation in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. San Diego, USA, 2010.1-10.

[10] GUPTA P, KUMAR P R. The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000, 46(2):388-404.

[11] BALJEET M, IOANIS N, MARIO A N. Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011,17:319-335.

[12] WU Y W, LI X Y, LIU Y H, et al. Energy-efficient wake-up scheduling for data collection and aggregation[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(2):275-287.

[13] WU Y, FAHMY S, SHROFF N B. On the construction of a maximum lifetime data gathering tree in sensor networks: np-completeness and approximation algorithm[A]. Proceedings of the IEEE INFOCOM[C].Phoenix, USA, 2008.1013-1021.

[14] HAN B, FU H H, LIN L D, et al．Efficient construction of connected dominating set in wireless ad hoc networks[A]. Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor System[C]. Florida, USA, 2004.570-572．

[15] CHALERMEK I, RAMESH G, DEBORAH E. Directed diffusion: a scalable and robust communication paradigm for sensor networks[A].Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00)[C]. Boston, USA, 2000.