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

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

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

1 引言

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 算法思路

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

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

3.2 算法描述

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

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

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

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

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

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

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

② 廣播 M esg(Bjoin)；

③ M ark(i)=1；

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

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

② 廣播 M esg(Gjoin)；

③ M ark(i)=1；

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

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

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

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

4.1 算法思路

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

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

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

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

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

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

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

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

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

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

4.2 算法描述與分析

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

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

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

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

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

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

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

算法2的輸出結(jié)果即為每個(gè)時(shí)間片中傳輸?shù)逆溌芳?，該集合必滿足以下3個(gè)條件：

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

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

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

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

證畢。

5 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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