時(shí)延和能耗均衡的強(qiáng)連通支配集構(gòu)造算法

孫彥景，錢建生，馬姍姍，任鵬

（1. 中國(guó)礦業(yè)大學(xué) 信息與電氣工程學(xué)院，江蘇 徐州 221116；2. 中國(guó)礦業(yè)大學(xué) 煤炭資源與安全開采國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 徐州 221116）

1 引言

與傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)不同，無線傳感器網(wǎng)絡(luò)(WSN, wireless sensor networks)沒有固定的基礎(chǔ)結(jié)構(gòu)。依據(jù)圖論的獨(dú)立集、支配集、連通支配集、獨(dú)立支配集、團(tuán)簇及染色等基本理論[1]，研究人員提出了很多構(gòu)造層次網(wǎng)絡(luò)的方法，作為無線傳感器網(wǎng)絡(luò)的虛擬骨干[2]。在單位圓圖（UDG, unit disk graph）網(wǎng)絡(luò)模型的基礎(chǔ)上，學(xué)者對(duì)使用最小連通支配集構(gòu)造虛擬骨干的方法進(jìn)行了大量的研究[3]，提出了很多最小連通支配集（MCDS, minimum connected dominating set）的構(gòu)造算法。

文獻(xiàn)[4～6]主要研究高效的分布式MCDS算法，或者在一定程度維護(hù)虛擬骨干的冗余以保證容錯(cuò)性和路由的靈活性。文獻(xiàn)[7]針對(duì)最小連通支配集問題提出了具有較高能量效率的啟發(fā)式算法。該算法把網(wǎng)絡(luò)中所有的節(jié)點(diǎn)作為最小連通支配集的一個(gè)初始解，然后利用啟發(fā)式修剪策略剔除冗余節(jié)點(diǎn)從而減小最小連通支配集的規(guī)模。文獻(xiàn)[8]使用圖著色算法求得的極大獨(dú)立集等價(jià)于簇劃分后的簇頭集合，然后搜索網(wǎng)關(guān)節(jié)點(diǎn)使得簇頭連通，由此生成極小連通支配集，形成虛擬主干網(wǎng)。文獻(xiàn)[9]提出一種基于能量代價(jià)的最小權(quán)和連通支配集拓?fù)淇刂扑惴?，解決無線傳感器網(wǎng)絡(luò)中最小連通支配集拓?fù)洳⒎蔷W(wǎng)絡(luò)耗能最小拓?fù)涞膯栴}，最小化網(wǎng)絡(luò)整體能耗。文獻(xiàn)[10]為了提高無線傳感器網(wǎng)絡(luò)的能量利用效率、延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間，提出了用馬爾科夫模型優(yōu)化分布式最小連通支配集算法。文獻(xiàn)[11]在串行最大獨(dú)立集構(gòu)造算法的基礎(chǔ)上，提出了基于權(quán)重和時(shí)序的觸發(fā)式連通支配集構(gòu)造算法。

隨著傳感器網(wǎng)絡(luò)應(yīng)用范圍的迅速擴(kuò)大，不僅要考慮節(jié)能特性，同時(shí)也對(duì)傳輸時(shí)延提出了要求。文獻(xiàn)[12]提出采用一種新型動(dòng)態(tài)樹來組織網(wǎng)絡(luò)拓?fù)涞哪苄c時(shí)延平衡的數(shù)據(jù)收集機(jī)制。文獻(xiàn)[13]提出了一種基于虛擬點(diǎn)優(yōu)先級(jí)的移動(dòng)sink路徑優(yōu)化選擇方法，以滿足時(shí)延要求和最小化網(wǎng)絡(luò)整體能耗。就無線傳感器網(wǎng)絡(luò)而言，在單位長(zhǎng)度下，路徑長(zhǎng)度等相關(guān)因素決定了網(wǎng)絡(luò)數(shù)據(jù)在節(jié)點(diǎn)之間的傳輸時(shí)延。在網(wǎng)絡(luò)圖上，路徑長(zhǎng)度轉(zhuǎn)化為最短路徑樹(SPT,shortest path tree)問題，等效于傳輸時(shí)延。數(shù)據(jù)傳輸帶來的能量功耗則可以看作求解最小支撐樹(MST,minimum spanning tree)問題。文獻(xiàn)[14]的研究結(jié)果表明不可能滿足路徑和費(fèi)用同時(shí)最小的要求。在文獻(xiàn)[15]的基礎(chǔ)上，文獻(xiàn)[16]提出了理想情況下基于無向圖的有界傳輸時(shí)延連通支配樹問題，并給出了構(gòu)建CDT(connected dominating tree)的有效算法，構(gòu)建連通支配樹來平衡連通支配集中功耗和傳輸時(shí)延。

考慮到無線網(wǎng)絡(luò)中通信鏈路的非對(duì)稱性，本文使用加權(quán)有向連通圖建模無線網(wǎng)絡(luò)，在文獻(xiàn)[16]的基礎(chǔ)上提出對(duì)應(yīng)無線傳感器網(wǎng)絡(luò)有界傳輸時(shí)延強(qiáng)連通支配樹聯(lián)合約束問題，并給出基于有向加權(quán)圖的時(shí)延和能耗均衡的強(qiáng)連通支配集算法，驗(yàn)證了算法的有效性。

2 SDTT問題

在無線網(wǎng)絡(luò)中，相鄰節(jié)點(diǎn)間的邊權(quán)重并不是對(duì)稱的，例如，節(jié)點(diǎn)u和v在不同噪聲環(huán)境下，有不同的信號(hào)檢測(cè)閾值，這樣從u到v和從v到u的路徑上發(fā)送的功率也就不同，依圖論理論，本文使用有向圖進(jìn)行網(wǎng)絡(luò)建模。

文獻(xiàn)[14]研究表明不可能同時(shí)滿足最小化權(quán)重和距離的目標(biāo)。為平衡MST和SPT的目標(biāo)要求，本文分別以MST和SPT的費(fèi)用（權(quán)重）表示發(fā)送時(shí)消耗的能量和從發(fā)送方到接收方的路徑長(zhǎng)度，構(gòu)造具有雙重權(quán)值的生成樹。同時(shí)，為簡(jiǎn)化分析，以路徑長(zhǎng)度代替?zhèn)鬏敃r(shí)延。這樣，對(duì)強(qiáng)連通支配集的生成樹而言，目的是在能量消耗(α)和傳輸時(shí)延(β)要求之間進(jìn)行折中。設(shè)加權(quán)有向圖G=(V, E)，要找到支撐G滿足(α,β)約束要求的強(qiáng)連通生成樹C，相關(guān)符號(hào)沿用文獻(xiàn)[16]中的定義：

Puv：從節(jié)點(diǎn)u到v發(fā)送成功所需要的功率

d(u, v) 或d(e)：在單位長(zhǎng)度下，從節(jié)點(diǎn)u到節(jié)點(diǎn)v沿邊e的歐氏距離；

Cv：信號(hào)偵測(cè)閾值常量，與具體環(huán)境條件相關(guān)。無線信號(hào)傳輸消耗的能量正比于dγ，γ的取值是從2到4，本文設(shè)為2；

p(u)：從節(jié)點(diǎn)u到節(jié)點(diǎn)v的最大發(fā)送功率為p(u)=max{puv:(u,v)∈G}；

w(e)：從節(jié)點(diǎn)u到節(jié)點(diǎn)v的邊e的權(quán)重為

w(C)：強(qiáng)連通樹C的權(quán)重w(C) = Σe∈Tw(e)；

p(C)：強(qiáng)連通樹C的能量消耗p(C) = Σu∈Vp(u)；

d(G)：圖G的路徑長(zhǎng)度（傳輸時(shí)延）d(G)=Σe∈Ed(e)。

定義1 無線傳感器網(wǎng)絡(luò)有界傳輸時(shí)延強(qiáng)連通支配樹約束(SDTT)問題：給定無線傳感器網(wǎng)絡(luò)子集，構(gòu)建一個(gè) SCDT-tree，使得d(SCDT)不大于用戶設(shè)定的閾值，并且p(SCDT)有界。

通過構(gòu)建一個(gè)強(qiáng)連通SCDT，同時(shí)滿足能量均衡和傳輸時(shí)延約束的要求。據(jù)文獻(xiàn)[16]SCDT-tree定義如下：

定義2 如果圖G的強(qiáng)連通支配樹C在α≥1且β≥1時(shí)，滿足下面的要求，則稱C為圖G的SCDT-tree：

1) 距離：對(duì)每一個(gè)頂點(diǎn)u，根節(jié)點(diǎn)r與u之間的距離至多是從r到u的最短路徑的α倍；

2) 能耗：C的能量消耗最多是SDTT問題最優(yōu)解的β倍。

針對(duì)鏈路的不對(duì)稱性，本文使用加權(quán)有向連通圖建模無線網(wǎng)絡(luò)，提出對(duì)應(yīng)SDTT問題在有向加權(quán)圖中的SCDT算法。

3 SCDT算法

在加權(quán)有向連通圖上，該圖的最小費(fèi)用樹把節(jié)點(diǎn)對(duì)間的發(fā)送功率作為權(quán)值，最短路徑樹以路徑長(zhǎng)度為權(quán)值，任選根節(jié)點(diǎn)r，SCDT算法構(gòu)建能耗和時(shí)延均衡的強(qiáng)連通支配樹。

算法構(gòu)造以r為根的MSTT和以r為匯聚點(diǎn)的T′，通過二者的疊加得到強(qiáng)連通圖。依據(jù)網(wǎng)絡(luò)的連通信息構(gòu)建H，H包含從根r至每個(gè)頂點(diǎn)的最短路徑；使用文獻(xiàn)[17]提出的MWIA-TC算法構(gòu)建T和T′。

SCDT算法按深度優(yōu)先(DFS, depth first search)的方式遍歷最小生成樹T，當(dāng)訪問節(jié)點(diǎn)u時(shí)，如果在T中從r到u的路徑長(zhǎng)度大于α倍H中的最短路徑，則用H中從r到u的路徑取代T中的路徑。對(duì)于T′執(zhí)行同樣的過程。這樣，在遍歷所有節(jié)點(diǎn)后，SDTT問題得以解決。算法輸入α，r, MSTT，MSTT′和SPTH，最后返回SCDT-treeC。

算法1 SCDT算法

4 分布式強(qiáng)連通支配集算法

分布式強(qiáng)連通支配集算法過程分為2個(gè)階段，首先在單位圓圖構(gòu)建極大獨(dú)立集，然后基于有向圖使用分布式SCDT算法構(gòu)造時(shí)延和能耗均衡的強(qiáng)連通支配集。

4.1 分布式MIS構(gòu)建

采用文獻(xiàn)[18]的方法讓所有的節(jié)點(diǎn)知道自己的排序和鄰居后，根節(jié)點(diǎn)啟動(dòng)染色標(biāo)記過程構(gòu)建極大獨(dú)立集。使用分布式簇頭選擇算法構(gòu)建有根生成樹進(jìn)行等級(jí)排序的機(jī)制，以保證生成的極大獨(dú)立集滿足兩跳的標(biāo)準(zhǔn)。在生成的有根生成樹中每個(gè)節(jié)點(diǎn)把與根節(jié)點(diǎn)之間的跳數(shù)看作自身的級(jí)別，節(jié)點(diǎn)的排序按照級(jí)別和ID標(biāo)識(shí)的有序數(shù)對(duì)進(jìn)行，遵循詞典次序排列，具體過程如文獻(xiàn)[16]所述。當(dāng)所有的節(jié)點(diǎn)標(biāo)記為灰色或黑色，根節(jié)點(diǎn)就開始執(zhí)行下一階段的算法。

4.2 分布式SCDT算法

下面介紹在有向圖模型下的分布式 SCDT算法。算法運(yùn)行在生成的極大獨(dú)立集中的每個(gè)節(jié)點(diǎn)，分為2個(gè)階段：①采用單源分布式dMST, dSPT和dDFS算法分別獲取SPT，MST和DFS的遍歷次序，在無向圖模型中生成連通支配集；②通過改變與節(jié)點(diǎn)關(guān)聯(lián)的邊的方向反轉(zhuǎn)每個(gè)節(jié)點(diǎn)所有的邊，重復(fù)步驟①的過程。通過反轉(zhuǎn)得到的SCDTD邊的方向，生成反轉(zhuǎn)的SCDTD′，聯(lián)合2個(gè)階段生成的SCDT，就得到強(qiáng)連通支配樹。在構(gòu)建過程中，節(jié)點(diǎn)之間使用消息WAKEUP、ADD、ADD_ FINISH、UPDATE、REVERSE實(shí)現(xiàn)信息交換。WAKEUP、ADD、ADD_FINISH 和 UPDATE消息如文獻(xiàn)[16]所述，REVERSE消息如下。

REVERSE：如果節(jié)點(diǎn)收到該消息，反轉(zhuǎn)關(guān)聯(lián)的該節(jié)點(diǎn)的所有邊的方向，把出邊變?yōu)槿脒?，把入邊變?yōu)槌鲞叀?/p>

為構(gòu)建SCDT樹，分布式算法dSPT、dMST和dDFS在每個(gè)節(jié)點(diǎn)執(zhí)行，發(fā)起和終止由根r控制，以串行方式運(yùn)行，網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)同步。按照dDFS過程中得到的順序，首先在MSTT上執(zhí)行算法，每個(gè)節(jié)點(diǎn)u使用p[u]記錄上一級(jí)的父節(jié)點(diǎn)，d[u]記錄距離。每個(gè)節(jié)點(diǎn)在初始時(shí)將d[u]設(shè)定為dT(r,u)，根r依照dDFS所得次序，發(fā)布WAKEUP消息到后續(xù)的節(jié)點(diǎn)，發(fā)起遍歷過程。

消息的傳遞觸發(fā)以下處理規(guī)則。

1) 從節(jié)點(diǎn)v收到WAKEUP消息，節(jié)點(diǎn)u成為當(dāng)前被訪問的節(jié)點(diǎn)，u更新d[u]和p[u]。接著，u檢查是否d[u]>αdSPT(r,u)，若是，添加從r到u的路徑PSPT(r,u)到T；否則，維持不變。為添加該路徑，u發(fā)送給其在SPT中的父親w消息ADD，這里，u是 ADD消息的發(fā)起者。接著，u等待發(fā)起者為u的ADD消息的回復(fù)。

2) 當(dāng)節(jié)點(diǎn)w而不是根節(jié)點(diǎn)收到來自節(jié)點(diǎn)u的發(fā)起者i的ADD消息，w發(fā)送一個(gè)發(fā)起者為i的ADD消息給SPT中的父親x，同時(shí)，w記錄u作為新的子節(jié)點(diǎn)。

3) 當(dāng)根節(jié)點(diǎn)r收到發(fā)起者為i的ADD消息，r記錄u為新的子節(jié)點(diǎn)，并返回ADD_FINISH消息至u，與ADD消息一樣，ADD_FINISH也需要包含發(fā)起者。

4) 當(dāng)節(jié)點(diǎn)u收到w的發(fā)起者i的ADD_FINISH消息，節(jié)點(diǎn)u更新d[u]和p[u]。若u不同于i，u發(fā)送發(fā)起者為i的ADD_FINISH消息給向u發(fā)送發(fā)起者i的ADD消息的節(jié)點(diǎn)；否則，u向由dDFS獲得的下一個(gè)節(jié)點(diǎn)發(fā)送WAKEUP消息，若p[u]由x變?yōu)閥，u發(fā)送一個(gè)發(fā)起者為u的UPDATE消息到x。

5) 當(dāng)節(jié)點(diǎn)x從u收到UPDATE消息，節(jié)點(diǎn)x更新d[x]和p[x]。若p[x]由v變?yōu)閣，x發(fā)送一個(gè)發(fā)起者為x的UPDATE消息到v。

6) 若在dDFS所得序列中的最后一個(gè)節(jié)點(diǎn)u收到發(fā)起者為u的ADD_FINISH消息，就反轉(zhuǎn)與自己關(guān)聯(lián)的邊的方向，并發(fā)送REVERSE消息給其父親。

7) 每個(gè)節(jié)點(diǎn)在收到REVERSE消息時(shí)，反轉(zhuǎn)所關(guān)聯(lián)的邊的方向，并發(fā)送REVERSE消息給自己的父親節(jié)點(diǎn)。

在收到發(fā)起者為u的REVERSE和UPDATE消息，u被標(biāo)記為dDFS隊(duì)列中的最后一個(gè)節(jié)點(diǎn)。根r反轉(zhuǎn)與其關(guān)聯(lián)的邊，結(jié)束第一階段。然后r發(fā)送WAKEUP消息發(fā)起第二階段。在根r收到一個(gè)發(fā)起者為u的UPDATE消息，而且u在dDFS次序中標(biāo)記為最后一個(gè)節(jié)點(diǎn)時(shí)，算法終止。

5 理論分析及算例

把SCDT算法運(yùn)用到圖G，構(gòu)造強(qiáng)連通樹C，設(shè)γ=2且Cv=1，p(opt)為SDTT問題的最優(yōu)解opt的總能耗。

引理1 在有向圖G中，圖G的支配樹C總功率消耗p(C)≤w(G)。

證明

引理2 對(duì)于圖G的SPTH和MSTT和T′，H的功耗至多倍MST功耗。

證明 由文獻(xiàn)[5]證明知，

顯然

由此得證。

引理3w(Topt)≤Δp(opt)，w(T′opt)≤p(opt)Δ是G中最大節(jié)點(diǎn)度。

證明 由文獻(xiàn)[16]可知，w(Topt)≤Δp(opt)。

對(duì)于T′，每個(gè)非根節(jié)點(diǎn)有且僅有一條出邊，因此，w(T′opt) ≤p(opt)，由此得證。

定理1 設(shè)C為由SCDT構(gòu)建的SCDT-tree，那么

證明 設(shè)圖G的SPTH，MSTT和T′，由引理1和2，可得

由此得證。

下面分析分布式算法 SCDT的時(shí)間和消息復(fù)雜度。

定理2 分布式SCDT算法的時(shí)間復(fù)雜度O(n2)，消息復(fù)雜度O(n2)。

證明 由前面過程可知，在每個(gè)節(jié)點(diǎn)同時(shí)執(zhí)行SCDT算法。ROUTE-ADD決定了算法的執(zhí)行時(shí)間，而ROUTE-ADD的最大執(zhí)行時(shí)間正比于RELEXed邊數(shù)，而RELEX的執(zhí)行時(shí)間是O(1)的。因此，考慮最壞的情況下，需要添加長(zhǎng)度為O(n)的路徑，這樣ROUTE-ADD的執(zhí)行時(shí)間為O(n)，由于dSPT、dMST和dDFS等算法的時(shí)間復(fù)雜度最大為O(n2)，顯然算法SCDT的時(shí)間復(fù)雜度也為O(n2)。

在運(yùn)行過程中，每個(gè)節(jié)點(diǎn)發(fā)送 REVERSE和WAKEUP消息 2次。ADD、ADD_FINISH和UPDATE至多O(n)次，因此算法總的消息復(fù)雜度應(yīng)為O(n2)。由此得證。

下面給出SCDT算法執(zhí)行過程示例。

在圖1中，設(shè)圖1(a)是執(zhí)行MIS構(gòu)建過程后形成的網(wǎng)絡(luò)虛擬骨干節(jié)點(diǎn)的無向圖，數(shù)字表示節(jié)點(diǎn)之間的通信距離；圖1(b)是在考慮每個(gè)節(jié)點(diǎn)為實(shí)現(xiàn)有效的傳輸所需要的發(fā)送功率后，形成的一個(gè)強(qiáng)連通雙向加權(quán)信息圖，每邊上的數(shù)字表示該方向上節(jié)點(diǎn)對(duì)間的通信所需的傳輸功率；圖1(c)是邊反轉(zhuǎn)后的加權(quán)圖；圖 1(d)是最短路徑樹H，圖 1(e)和 1(f)是最小支撐樹T和T'；設(shè)節(jié)點(diǎn)1為根節(jié)點(diǎn)，且α=2，對(duì)T按照DFS次序進(jìn)行遍歷，當(dāng)訪問4時(shí)，T中的路徑(1,2,3,4)dT(1,4)=23，此時(shí)在H中，dH(1,4)=11，也就是dT(1, 4)大于2dH(1, 4)=22，于是把邊(1,4)添加到H，同時(shí)p[u]從3更新為1。注意到邊（3,4）沒有刪除，這是因?yàn)樾枰獜拇诉吇厮荨Ｔ诒闅vT之后得到D如圖1(g)，同樣的在遍歷T'后得到D'，如圖 1(h)，括號(hào)內(nèi)的數(shù)字表示路徑長(zhǎng)度(即時(shí)延)，外面的為該邊的功耗，最后聯(lián)合D和D'得到最終的SCDT樹C，如圖1(i)所示。

圖1 SCDT-算法示例

接下來，驗(yàn)證算法的約束能力，分別單獨(dú)計(jì)算圖1所示MST、SDT和SPT的功耗：

以路徑長(zhǎng)度代替時(shí)延計(jì)算如下：

根據(jù)上面的計(jì)算結(jié)果可得：

結(jié)果表明SCDT算法執(zhí)行正確，具有聯(lián)合約束能力，符合預(yù)期效果。

6 仿真實(shí)驗(yàn)

采用與文獻(xiàn)[16]相同的參數(shù)設(shè)置，在網(wǎng)絡(luò)規(guī)模從20到300個(gè)節(jié)點(diǎn)的情況下進(jìn)行仿真，所有的網(wǎng)絡(luò)場(chǎng)景在1 000×1 000的單位區(qū)域內(nèi)生成，對(duì)每個(gè)網(wǎng)絡(luò)場(chǎng)景運(yùn)行20此取統(tǒng)計(jì)平均值。對(duì)每條邊e設(shè)置其權(quán)重為Cvdruv，dru為圖G單位長(zhǎng)度下的歐氏距離，r取值2。Cv為隨機(jī)常量，由網(wǎng)絡(luò)場(chǎng)景參數(shù)為每條鏈路設(shè)定。

圖2的仿真結(jié)果表明，由于算法SCDT僅添加在最小支撐樹中從u到r的權(quán)重2倍以上最短路徑樹中權(quán)重的路徑，算法SCDT能量消耗低于SPT，有效限制了總能耗。另外，在固定區(qū)域范圍內(nèi)，當(dāng)網(wǎng)絡(luò)規(guī)模不斷變大，節(jié)點(diǎn)數(shù)增多時(shí)，鄰居節(jié)點(diǎn)之間的距離在逐漸變小，因此總能量消耗并沒有快速增加。由圖2(b)可知，就能量消耗而言，SCDT/MST要比 SPT/MST低，而且在固定的區(qū)域內(nèi)，隨著節(jié)點(diǎn)數(shù)增加，網(wǎng)絡(luò)密度增加，此時(shí)節(jié)點(diǎn)彼此之間更加接近，分布更均勻，所以比值呈下降趨勢(shì)，都更接近MST，也就是總能耗最小。

本文通過統(tǒng)計(jì)路徑長(zhǎng)度來簡(jiǎn)化傳輸時(shí)延特性分析。由圖3可以看出，對(duì)路徑長(zhǎng)度而言，算法SPT總是最短也就是說傳輸時(shí)延最小，符合最短路徑的特性。由圖3(b)可知，就時(shí)延而言，SCDT與SPT的比值要比 MST低，而且在固定的區(qū)域內(nèi)，隨著節(jié)點(diǎn)數(shù)增加，網(wǎng)絡(luò)密度增加，此時(shí)節(jié)點(diǎn)彼此之間更加接近，分布更均勻，所以比值呈下降趨勢(shì)，都更接近SPT，也就是總路徑長(zhǎng)度最小，傳輸時(shí)延更小。

圖2 能量消耗對(duì)比

圖3 傳輸時(shí)延對(duì)比

綜合圖2和圖3的結(jié)果可知，SCDT具有在最小費(fèi)用MST和最短路徑SPT之間的折中能力。

為分析α參數(shù)的選擇對(duì)算法時(shí)延和能耗約束關(guān)系的影響，分別對(duì)不同α取值時(shí)SCDT、MST和SPT算法總能耗和路徑時(shí)延進(jìn)行仿真，結(jié)果如圖4所示。為分析能耗關(guān)系，如圖4(a)所示，分別把SCDT和SPT能耗與最小能耗MST進(jìn)行比較。當(dāng)α=1時(shí)，SCDT算法構(gòu)建SPT，因此，2條曲線在1處相交，隨著α得增加，SPT/MST保持在5左右；SCDT/MST逐漸降低，當(dāng)α足夠大時(shí)，此時(shí)對(duì)SCDT而言，只考慮能耗而不考慮時(shí)延問題，SCDT成為MST，符合的關(guān)系。

為分析傳輸時(shí)延關(guān)系，如圖4(b)所示，分別把SCDT和MST總路徑長(zhǎng)度與最短路徑SPT進(jìn)行比較。當(dāng)α=1時(shí)，SCDT構(gòu)建 SPT，隨著α的增加，MST/SPT維持在5；然而，SCDT/SPT逐漸增長(zhǎng)，最后與MST相交。這是因?yàn)楫?dāng)α足夠大時(shí)，基本不考慮時(shí)延約束，SCDT等同于構(gòu)建MST。

圖4α對(duì)約束關(guān)系的影響

7 結(jié)束語

為了解決無線傳感器網(wǎng)絡(luò)虛擬骨干構(gòu)造時(shí)能耗和時(shí)延聯(lián)合約束的問題，考慮到無線鏈路的不對(duì)稱性，借鑒平衡MST和SPT樹的(α,β)約束機(jī)制，本文提出基于有向圖構(gòu)造時(shí)延和能耗均衡的強(qiáng)連通支配集的分布式算法，解決了能耗和時(shí)延均衡的問題。理論分析、算例和仿真實(shí)驗(yàn)都證明了提出的算法對(duì)解決該問題的有效性。在實(shí)際應(yīng)用中，可以結(jié)合具體應(yīng)用要求確定參數(shù)α、β調(diào)節(jié)約束關(guān)系。

[1] KIM D, WU Y, LI Y,et al. Constructing minimum connected dominating sets with bounded diameters in wireless networks[J]. IEEE Trans Parallel and Distributed Systems, 2009, 20(2): 147-157.

[2] MISRA R, MANDAL C. Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3): 292-302.

[3] ZHENG C, SUN S X, HUANG T Y. Constructing distributed connected dominating sets in wireless ad hoc and sensor networks[J].Journal of Software, 2011,22(5):1053-1066.

[4] 卞永釗,于海斌,曾鵬. 無線傳感器網(wǎng)絡(luò)中一種啟發(fā)式最小連通支配集算法[J]. 信息與控制，2009, 38 (3): 355-359 BIAN Y Z, YU H B, ZENG P. A heuristic minimum connected dominating set algorithm for wireless sensor network[J]. Information and Control, 2009, 38 (3): 355-359.

[5] 徐洪兵, 祝穎. 基于拓?fù)淇刂频漠愵悷o線傳感器網(wǎng)絡(luò)分簇算法研究[J]. 電子科技大學(xué)學(xué)報(bào), 2006, 35(4): 674-677.XU H B, ZHU Y. A topology-based cluster algorithm of heterogeneous wireless sensor networks[J]. Journal of University of Electronic Science and Technology of China, 2006, 35(4): 674-677.

[6] THAI M T, WANG F. Connected dominating sets in wireless networks with different transmission ranges[J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 1-10.

[7] WU W L, DU H W, JIA X H,et al. Minimum connected dominating sets and maximal independent sets in unit disk graphs[J]. Theoretical Computer Science, 2006, 352(1): 1-7.

[8] 許力，林志偉. 基于圖著色的無線自組網(wǎng)極小連通支配集算法[J].通信學(xué)報(bào), 2007, 28(3):108-114.XU L, LIN Z W. Graph coloring based minimal connected dominating set algorithm in wireless ad hoc networks[J]. Journal on Communications, 2007, 28(3):108-114.

[9] 孫超, 尹榮榮, 郝曉辰. WSNs中基于能量代價(jià)的最小權(quán)和支配集拓?fù)淇刂扑惴╗J]. 電子與信息學(xué)報(bào), 2010, 32(4): 857-863 SUN C, YIN R R, HAO X C. Energy cost based topology control algorithm of minimum-total-weight connected dominating set in WSNs[J]. Journal of Electronics and Information Technology, 2010,32(4): 857-863.

[10] 汪文勇, 向渝, 董傳坤等. 用馬爾科夫模型優(yōu)化分布式最小連通支配集算法[J].電子學(xué)報(bào),2010, 38(10):2441-2446.WANG W Y, XIAGN Y, DONG C K,et al. Optimizing distributed algorithm for minimum connected dominating set with Markov model[J]. Acta Electronica Sinica, 2010, 38(10):2441-2446.

[11] 王玉明, 趙大勝. 基于串行最大獨(dú)立集的連通支配集構(gòu)造及分析[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,39(3):61-65.WANG Y M, ZHAO D S. Construction and analysis of connecteddominating set based on serial maximum independent set[J]. Journal of Huazhong Science and Technology (Natuaral Science Edition),2011,39(3):61-65.

[12] 鄭杰, 郭淑杰, 屈玉貴等. 無線傳感器網(wǎng)絡(luò)能效時(shí)延平衡數(shù)據(jù)收集機(jī)制[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2008, 38(12):1414-1421.ZHENG J, GUO S J, QU Y G,et al.Energy efficiency and delay balancing data gathering for wireless sensor networks[J]. Journal of University of Science and Technology of China, 2008, 38(12):1414-1421.

[13] 郜帥, 張宏科. 時(shí)延受限傳感器網(wǎng)絡(luò)移動(dòng)Sink路徑選擇方法研究[J]. 電子學(xué)報(bào),2011, 39(4):742-747.GAO S, ZHANG H K. Optimal path selection for mobile sink in delay-guaranteed sensor networks[J]. Acta Electronica Sinica, 2011,39(4):742-747.

[14] SAMIR K, BALAJI R, NEAL E. Young balancing minimum spanning trees and shortest path trees[J]. Algorithm, 1994, 120(4):305-321.

[15] LI Y S, THAI M T, WU F. On the construction of a strongly connected broadcast arborescence with bounded transmission delay[J].IEEE Transactions on Mobile Computing, 2006, 5(10):1460-1470.

[16] 孫彥景, 錢建生, 顧相平等.聯(lián)合約束無線傳感器網(wǎng)絡(luò)連通支配集算法[J].電子科技大學(xué)學(xué)報(bào)，2009，38(2)：231-235.SUN Y J, QIAN J S, GU X P,et al. Distributed connected dominating set algorithm with combined constraints in wireless sensor network[J].Journal of University of Electronic Science and Technology of China,2009，38(2)：231-235.

[17] LI Y, CHENG M X, DU D Z. Optimal topology control for balanced energy consumption in wireless networks[J]. Journal Parallel and Distributed Computing, 2005, 65(2): 124-131.

[18] WAN P J, KHALED M A, OPHIR F. Distributed construction of connected dominating sets in wireless ad hoc networks[J]. ACM/Kluwer Mobile Networks and Applications, 2004, 9(2): 141- 149.