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

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

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

1 引言

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

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

另一方面，數(shù)據(jù)融合技術(shù)也是降低節(jié)點的能耗，延長網(wǎng)絡(luò)生命周期的重要手段。數(shù)據(jù)融合是多跳網(wǎng)絡(luò)中數(shù)據(jù)聚集和路由的一種方式，其特點是數(shù)據(jù)采集的中間節(jié)點在收到不同信息源的數(shù)據(jù)后，以去除冗余信息為目的對所接收到的多個數(shù)據(jù)進(jìn)行融合處理，進(jìn)而能夠?qū)崿F(xiàn)減小傳輸數(shù)據(jù)量，降低節(jié)點由于大量數(shù)據(jù)傳輸而帶來的能量消耗，延長網(wǎng)絡(luò)生命周期[3]。

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

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

2 問題描述

1) 所有節(jié)點采集的數(shù)據(jù)均被匯聚到sink節(jié)點；

本文中對于沖突的定義，采用協(xié)議沖突模型[10]，約定網(wǎng)絡(luò)中任意節(jié)點均可以發(fā)送和接收數(shù)據(jù)，但二者不能同時進(jìn)行，且所有節(jié)點的干擾半徑均相同，記為Ir。

定義1 鏈路沖突。在協(xié)議沖突模型中，2個通信鏈路沖突，當(dāng)且僅當(dāng)其中一個鏈路的接收端在另一個鏈路發(fā)送端的干擾半徑范圍內(nèi)。

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

圖1 鏈路間沖突關(guān)系

根據(jù)引言中的分析，構(gòu)造出的調(diào)度序列應(yīng)該盡可能同時滿足3個方面的特性需求。相關(guān)定義如下。

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

對于任意結(jié)構(gòu)的數(shù)據(jù)融合樹，其融合延時有

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

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

定義 3 平均加權(quán)時延。在一個融合周期內(nèi)，若G中節(jié)點i采集的數(shù)據(jù)共經(jīng)歷了 ti個時隙后到達(dá)sink節(jié)點，則該節(jié)點數(shù)據(jù)的加權(quán)時延為 Di= wi× ti，融合周期內(nèi)所有節(jié)點的平均加權(quán)時延可計算為

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

圖2 平均加權(quán)時延計算示例

定義4 網(wǎng)絡(luò)生命周期。對于任意調(diào)度算法，若經(jīng)歷了L個融合周期后網(wǎng)絡(luò)中出現(xiàn)了第一個能量耗盡的節(jié)點，則稱該調(diào)度算法下的網(wǎng)絡(luò)生命周期為L。

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

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

3 基于最大獨立集的數(shù)據(jù)融合樹構(gòu)建算法T-MIS

3.1 算法思路

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

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

3.2 算法描述

算法1 數(shù)據(jù)融合樹構(gòu)建算法T-MIS。

1) 以 vs為根，r為網(wǎng)絡(luò)半徑，構(gòu)造G的廣度優(yōu)先搜索樹；

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

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

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

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

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

② 廣播 M esg(Bjoin)；

③ M ark(i)=1；

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

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

② 廣播 M esg(Gjoin)；

③ M ark(i)=1；

10) 以DS為樹干，其余節(jié)點為葉節(jié)點（ Pi為其支配節(jié)點）形成樹結(jié)構(gòu)；

11) 對所有非根節(jié)點vi∈V，標(biāo)記其子節(jié)點個數(shù)為

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

4 基于最大獨立集的數(shù)據(jù)融合調(diào)度算法S-MIS

4.1 算法思路

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

圖3 數(shù)據(jù)融合樹構(gòu)建過程

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

圖4中給出了2個不同時隙內(nèi)邊沿鏈路集選取的示例。在t=1時，樹中所有以葉子節(jié)點為發(fā)送端的鏈路均為邊沿鏈路，即當(dāng)經(jīng)過n-1個時隙后，黑色節(jié)點均被調(diào)度完畢，此時有

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

圖4 不同時隙內(nèi)邊沿鏈路集的選取

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

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

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

除了通過選取激活鏈路作為調(diào)度對象外，為了保證對高權(quán)重數(shù)據(jù)的優(yōu)先傳送，本文希望能夠構(gòu)造出每個時隙內(nèi)激活鏈路集合的最大加權(quán)獨立集作為該時隙內(nèi)的調(diào)度序列，但由于該集合的求解過于復(fù)雜，本文提出了一種構(gòu)造最大加權(quán)獨立集的近似算法。

4.2 算法描述與分析

算法2 數(shù)據(jù)融合調(diào)度算法S-MIS。

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

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

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

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

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

8) 如果 DAT中仍有標(biāo)記為未調(diào)度的鏈路，則t = t + 1，轉(zhuǎn)至步驟2)；

算法2的輸出結(jié)果即為每個時間片中傳輸?shù)逆溌芳希摷媳貪M足以下3個條件：

2) 每個節(jié)點采集的數(shù)據(jù)均到達(dá)sink節(jié)點；

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

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

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

證畢。

5 實驗結(jié)果與分析

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

表1 仿真參數(shù)設(shè)置

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

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

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

圖6 算法平均加權(quán)時延隨節(jié)點密度變化比較

圖7 網(wǎng)絡(luò)生命周期隨節(jié)點密度變化比較

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

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

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

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

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

圖8 節(jié)點具有不同權(quán)重時融合時延隨節(jié)點密度變化比較

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

圖9 節(jié)點具有不同權(quán)重時平均加權(quán)時延隨節(jié)點密度變化比較

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

圖10 節(jié)點具有不同權(quán)重時網(wǎng)絡(luò)生命周期隨節(jié)點密度變化比較

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

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

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

圖11 不同節(jié)點數(shù)量下融合時延隨閾值δ的變化比較

圖12 不同節(jié)點數(shù)量下平均加權(quán)時延隨閾值δ的變化比較

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

圖13 不同節(jié)點數(shù)量下網(wǎng)絡(luò)生命周期隨閾值δ的變化比較

6 結(jié)束語

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

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

[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.