孔凡鳳，歐紅玉，龍林德，陳 曦

（1.湖南郵電職業(yè)技術(shù)學(xué)院移動(dòng)通信系，長沙 410115；2.長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長沙 410114）

基于連通支配集的WSN自適應(yīng)數(shù)據(jù)調(diào)度算法

孔凡鳳1，歐紅玉1，龍林德1，陳 曦2

（1.湖南郵電職業(yè)技術(shù)學(xué)院移動(dòng)通信系，長沙 410115；2.長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，長沙 410114）

在無線傳感器網(wǎng)絡(luò)中通過構(gòu)建連通支配集來組成虛擬的骨干，使網(wǎng)絡(luò)數(shù)據(jù)的收集變得層次化，更可以防止節(jié)點(diǎn)的死亡造成數(shù)據(jù)鏈的斷裂，然而最小的連通支配集不能均衡各節(jié)點(diǎn)的能量消耗，導(dǎo)致部分節(jié)點(diǎn)過早死亡。為此，基于連通支配集的無線傳感器網(wǎng)絡(luò)，提出一種自適應(yīng)的數(shù)據(jù)調(diào)度算法，通過選擇能量和度比較大的節(jié)點(diǎn)組成支配集，支配集組成較高能量的網(wǎng)絡(luò)骨干，數(shù)據(jù)經(jīng)過自適應(yīng)的調(diào)度沿著較小規(guī)模的網(wǎng)絡(luò)骨干尋找路由直到發(fā)給基站。實(shí)驗(yàn)結(jié)果表明，該算法在較小的網(wǎng)絡(luò)規(guī)模中具有容錯(cuò)性，可以減少能量消耗并延長網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò)；虛擬骨干；連通支配集；數(shù)據(jù)調(diào)度；能量消耗；生命周期

DO I：10.3969/j.issn.1000-3428.2015.10.018

1 概述

現(xiàn)在無線傳感器網(wǎng)絡(luò)的應(yīng)用越來越普遍，網(wǎng)絡(luò)的構(gòu)成都是由若干傳感器節(jié)點(diǎn)通過自組織完成組網(wǎng)。但是，網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量比較多，各個(gè)節(jié)點(diǎn)的數(shù)據(jù)匯聚到匯聚節(jié)點(diǎn)過程中，會(huì)有大量重疊，對(duì)于能量有限的無線傳感器節(jié)點(diǎn)來說會(huì)造成信息冗余、能量浪費(fèi)，影響了信息的實(shí)時(shí)操作［1］。針對(duì)這一問題，人們提出并研究各種數(shù)據(jù)調(diào)度技術(shù)，即通過建立更加高效、靈活、健壯的連通支配集減少通信過程中的能量消耗，延長網(wǎng)絡(luò)生命周期［2］。

所謂連通支配集就是構(gòu)造k-連通和m-支配的支配集作虛擬的骨干網(wǎng)，k-連通是集合中任2個(gè)支配節(jié)點(diǎn)至少存在k條路徑，即使k-1條路徑斷開，

仍然能實(shí)現(xiàn)骨干網(wǎng)數(shù)據(jù)的連通。m-支配是指任一個(gè)被支配節(jié)點(diǎn)至少與m個(gè)支配節(jié)點(diǎn)連接。通過這個(gè)虛擬的骨干網(wǎng)讓無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)構(gòu)造規(guī)模變小，減少節(jié)點(diǎn)間數(shù)據(jù)通信的次數(shù)［3］。

之前不少研究人員提出了一些基于連通支配集的算法。在CDS-BD-D［4］算法中，SINK通過單跳或者多跳給區(qū)域內(nèi)的節(jié)點(diǎn)發(fā)送消息，節(jié)點(diǎn)接收到消息后根據(jù)跳數(shù)可以計(jì)算出距離SINK的距離。在算法初始，節(jié)點(diǎn)首先根據(jù)度的大小決定是否成為支配節(jié)點(diǎn)，度比鄰居節(jié)點(diǎn)的大則首先成為支配節(jié)點(diǎn)，同時(shí)此支配節(jié)點(diǎn)比其他支配節(jié)點(diǎn)距SINK更近，則此節(jié)點(diǎn)發(fā)送一個(gè)connect消息，然后根據(jù)此消息改為支配節(jié)點(diǎn)，依次類推，最后形成以SINK為根的連通支配集。mr-CDS算法［5］根據(jù)能量的大小決定是不是連通支配集，能量高的首先成為支配節(jié)點(diǎn)，并向鄰居節(jié)點(diǎn)廣播消息，此時(shí)非支配節(jié)點(diǎn)可以獲知鄰居中支配節(jié)點(diǎn)的數(shù)量并把此消息廣播出去，這樣鄰居也可以得到2跳的支配節(jié)點(diǎn)，然后搜索可以連通的路徑，如果還沒有通路就自己變?yōu)橹涔?jié)點(diǎn)。但是非支配節(jié)點(diǎn)在自主變?yōu)橹涔?jié)點(diǎn)時(shí)沒有考慮能量因素，這樣會(huì)造成較多的支配節(jié)點(diǎn)和過多的連通集。LDA［6］算法采用CDS-BD-D構(gòu)造一個(gè)1-連通、m-支配的連通支配集。每個(gè)支配節(jié)點(diǎn)根據(jù)鄰居信息構(gòu)造一個(gè)局部k節(jié)點(diǎn)連通子圖。最后每個(gè)支配節(jié)點(diǎn)通知該子圖中的非支配節(jié)點(diǎn)加入連通支配集。

本文提出一種基于連通支配集的無線傳感器自適應(yīng)數(shù)據(jù)調(diào)度算法（Adaptive data Scheduling algorithm Based on Connected Dominating Set，ASCDS），通過選擇能量和權(quán)值較大的節(jié)點(diǎn)為支配節(jié)點(diǎn)并形成連通支配集，非支配節(jié)點(diǎn)首先找到歸屬的支配節(jié)點(diǎn)，然后通過自適應(yīng)的調(diào)度算法進(jìn)行數(shù)據(jù)收集。在此算法中所有的數(shù)據(jù)在小范圍內(nèi)沿著虛擬骨干節(jié)點(diǎn)尋找轉(zhuǎn)發(fā)路由，能節(jié)省能量，防止節(jié)點(diǎn)的早死亡。ASCDS算法通過生成小規(guī)模的連通支配集，防止節(jié)點(diǎn)的失效造成數(shù)據(jù)鏈的斷裂，完成更多輪的數(shù)據(jù)傳遞。

2 系統(tǒng)模型及問題描述

2.1 連通支配集的模型

構(gòu)成的連通支配集需能量消耗均衡，所以應(yīng)該具有以下2個(gè)特點(diǎn)：（1）構(gòu)造的支配集應(yīng)盡可能小，這樣數(shù)據(jù)可以更好地進(jìn)行融合并傳輸，避免干擾和沖突造成能量浪費(fèi)［7］。（2）構(gòu)造的連通支配集應(yīng)具有較高的能量水平，以延長網(wǎng)絡(luò)的生命周期，也就是要求支配集中的匯聚節(jié)點(diǎn)應(yīng)該有較高的能量水平。但是這是一個(gè)NP問題，如果要均衡以上2點(diǎn)，定義權(quán)值Wi=EiDegreei，讓權(quán)重的節(jié)點(diǎn)優(yōu)先成為骨干，其中，Degreei是鄰居數(shù)量，定義為節(jié)點(diǎn)的度［8］。

2.2 連通支配集構(gòu)造描述

在無線傳感器網(wǎng)絡(luò)，基站的數(shù)量較少，所以構(gòu)建連通支配集網(wǎng)絡(luò)很適合這一能量受限的網(wǎng)絡(luò)環(huán)境：（1）連通支配集本身的優(yōu)點(diǎn)有助于節(jié)省能量消耗；（2）支配集是由能量高但是度不一定大的節(jié)點(diǎn)組成，這樣構(gòu)成的連通支配集的規(guī)模比較大［9］。本文從延長網(wǎng)絡(luò)生命周期和能量均衡來構(gòu)造分布式的連通支配集。

定義 一個(gè)傳感器網(wǎng)絡(luò)G=（V，E），其中，V表示節(jié)點(diǎn)集合，有n個(gè)節(jié)點(diǎn)隨機(jī)分布在一個(gè)L×L的區(qū)域內(nèi)，設(shè)定SINK位于區(qū)域的中心［10］，每個(gè)節(jié)點(diǎn)的傳輸半徑均為r。每個(gè)節(jié)點(diǎn)都具有權(quán)值Wi，color，ID屬性，并有一個(gè)與鄰居關(guān)系的LIST列表。

2.2.1 身份階段

第1個(gè)階段ASCDS算法節(jié)點(diǎn)身份確認(rèn)，網(wǎng)絡(luò)中節(jié)點(diǎn)跟鄰居比較，權(quán)值最大者為支配節(jié)點(diǎn)，如果最大權(quán)值相同，則比較ID號(hào)，ID號(hào)小者成為支配節(jié)點(diǎn)，過程如圖1所示，黑色的表示支配節(jié)點(diǎn)，灰色表示非支配節(jié)點(diǎn)，白色表示沒有加入任何支配集。

圖1 連通支配集形成過程

對(duì)該階段的描述如下：

（1）對(duì)于所有的νi∈V，初始化參數(shù)color（νi）= white。

（2）任意一個(gè)節(jié)點(diǎn)跟鄰居的權(quán)值做比較，如果Wi＞W(wǎng)Neigh，則color（νi）=black，如果（Wi=Wj）＞W(wǎng)Neigh，則根據(jù)ID號(hào)決定，如果IDi＜IDj，νi成為支配節(jié)點(diǎn)。此時(shí) color（νi）=black，并廣播消息參數(shù)dominator（νi）告知自己的鄰居。

（3）當(dāng)節(jié)點(diǎn)νj收到從νi來的dominator（νj）消息后，νi查看自己的color值，如果color（νi）=white，則color（νi）=gray，并發(fā)布廣播dominator（νi）消息到周圍鄰居。

（4）如果節(jié)點(diǎn)νi接收到一個(gè)從νj的dominator（νj）消息，如果color（νi）=white，說明此節(jié)點(diǎn)還沒有加入任何一個(gè)支配集。首先νi是否能成為支配節(jié)點(diǎn)，先把νj從νi的鄰居集里面刪除，然后跟其他鄰居比較，如果Wi＞W(wǎng)Neigh，則νi成為支配節(jié)點(diǎn)，或者Wi＞W(wǎng)Neigh且IDi＜IDNeigh，則 νi也成為支配節(jié)點(diǎn)，此時(shí)節(jié)點(diǎn)color（νi）=black，并發(fā)送dominator（νi）通知鄰居。2.2.2 支配集形成階段

第2階段ASCDS算法連通支配集形成過程，根據(jù)能量均衡及鄰居與其他支配節(jié)點(diǎn)連接情況，產(chǎn)生連通支配集，如圖1（d）所示。描述如下：

（1）如果color（νi）=gray，則νi為向相鄰的支配節(jié)點(diǎn)νk廣播消息Mesg1（νi，νk），讓?duì)蚷的鄰居知道νk的存在。

（2）如果節(jié)點(diǎn)νi接收到廣播消息Mesg（νj，νk），則νi要查看自身的color屬性。

如果color（νi）=gray，則說明νi的鄰居里面至少有一個(gè)1跳的νm，而且2跳的鄰居里面還有一個(gè)νk。如果IDm＜IDk，則νi廣播一個(gè)Mesg2（νi，νj，νk），這里要求IDm＜IDk是因?yàn)锳SCDS算法規(guī)定由ID號(hào)小的節(jié)點(diǎn)決定是否與其ID號(hào)大的節(jié)點(diǎn)連通，如果νm決定建立連接，則建立了νm→νi→νj→νk的路徑。

如果color（νi）=black，且IDi＜IDk，則由νi決定是否與νk連通，如果滿足條件，則建立νi→νj→νk的路徑。

現(xiàn)在建立了νi通過νj到νk的路徑，但是并不知道有沒有其他更優(yōu)的數(shù)據(jù)收集路徑。因此，先把路徑［νj，νk］置于列表List1中，如果存在了到νk的路徑［νl，νk］（這里νl可以是一個(gè)也可以是多個(gè)），則比較νl和νj的權(quán)值大小，如果Wl＜Wj，則將［νl，νk］刪除并增加［νj，νk］，相反，則不增加［νl，νk］。 如果節(jié)點(diǎn)νi第一次接收到Mesg1和Mesg2消息，則啟動(dòng)定時(shí)器Timer，等待Δ秒，這Δ秒能保證接收到其他鄰居節(jié)點(diǎn)發(fā)來的Mesg1和Mesg2消息。

（3）如果節(jié)點(diǎn) νi接收到一個(gè)Mesg2（νn，νj，νk），首先查看自己的 color屬性。如果 color（νi）= black，則νi決定是否與2跳之外的νk進(jìn)行連通。為了實(shí)現(xiàn)節(jié)點(diǎn)的能量均衡，延長節(jié)點(diǎn)生命周期，νi會(huì)先把路徑νn→νj→νk存入列表List2中。如果存在其他通往νk的路徑νr→νs→νk，并且（Wr+Ws）＜（Wn+ Wj），則刪除路徑 νr→νs→νk，并增加路徑 νn→νj→νk。如果節(jié)點(diǎn)νi第一次接收到Mesg2消息，則啟動(dòng)定時(shí)器Timer，等待Δ秒，這Δ秒能保證接收到其他鄰居節(jié)點(diǎn)發(fā)來的Mesg1和Mesg2消息。

（4）當(dāng)定時(shí)器Timer結(jié)束后，節(jié)點(diǎn) νi要根據(jù)List1和List2去確定最后的連通路徑。

對(duì)于表List1中記錄的每條路徑［νl，νk］，將 νl加入到集合 F中，由于存在路徑［νl，νk］，則可以刪除表List2中的［νn，νj，νk］。

對(duì)于表List2中的每條記錄［νn，νj，νk］，將νn，νj加入集合F中。最后將F放入消息connector（F，2）中并廣播出去，數(shù)字2表示會(huì)廣播2次，每被轉(zhuǎn)發(fā)一次減1，這說明 νi的2跳記錄都可以收到此消息。如果νi收到消息connector（F，a），首先a減1，如果νi屬于F，并且color（νj）=gray，則color（νj）= black。如果a≥1，則繼續(xù)廣播connector（F，a）。

3 數(shù)據(jù)融合調(diào)度過程

數(shù)據(jù)融合調(diào)度的最終目的是為節(jié)點(diǎn)分配時(shí)隙，本文主要的調(diào)度過程依據(jù)服務(wù)概率去確定每個(gè)時(shí)隙中的通信鏈路集合。在其他研究人員提出的算法中，基本上采用的是每個(gè)鏈路只調(diào)度一次的原則［11］，這種方法讓權(quán)重?cái)?shù)高得無法優(yōu)先調(diào)度，但是又不能無限制調(diào)度，如何調(diào)整通信次數(shù)是實(shí)現(xiàn)能量均衡和延長生命周期的關(guān)鍵參數(shù)。

調(diào)度步驟如下：

（1）鏈路的權(quán)重集合為W=｛w1，w2，…，wn｝，調(diào)度集為Tree，閾值為δ，初始化SCH=?，t=1，標(biāo)記所有鏈路未調(diào)度。

（2）沒有被調(diào)度的鏈路 νi，如果 νi屬于連通支配集中的非邊沿鏈路，且權(quán)重大于δ，則激活為 t時(shí)刻的鏈路集合［12］。

（3）構(gòu)造鏈路的沖突矩陣CM，構(gòu)造以CM為鄰接矩陣的最大獨(dú)立集。

（4）對(duì)于所有不在連通支配集中的激活鏈路，根據(jù)自適應(yīng)的概率計(jì)算器，即節(jié)點(diǎn)的權(quán)重參數(shù)動(dòng)態(tài)調(diào)整各節(jié)點(diǎn)的服務(wù)概率。假設(shè)第i個(gè)節(jié)點(diǎn)的權(quán)重 wi，可以與鄰居節(jié)點(diǎn)形成矩陣并構(gòu)成近似的最大加權(quán)獨(dú)立集，則根據(jù)服務(wù)概率把此節(jié)點(diǎn)變成調(diào)度節(jié)點(diǎn)。

（5）如果Tree中尚存在沒有被調(diào)度的鏈路，則

t=t+1，轉(zhuǎn)到步驟（2）。

（6）返回融合周期每個(gè)時(shí)隙的傳輸鏈路集合SCHE=｛e1，e2，…，et｝，如圖2所示。

圖2 不同時(shí)隙內(nèi)鏈路的選取

此調(diào)度方法執(zhí)行后，有：

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

（2）E（1）∪E（2）∪…∪E（t）=E︵；

（3）對(duì)于E（s）（1≤s≤t），若ei，ej∈E（s），則必有ei和ej相互不沖突。

4 仿真結(jié)果與性能比較

為了證明ASCDS算法的性能，采用Matlab7.0軟件進(jìn)行仿真。仿真環(huán)境如下：在一個(gè)100 m×100 m的正方形區(qū)域內(nèi)，SINK位于區(qū)域的中心，N個(gè)節(jié)點(diǎn)隨機(jī)分布在區(qū)域中，如表1所示。通過設(shè)置不同個(gè)數(shù)的節(jié)點(diǎn)、不同半徑的觀察節(jié)點(diǎn)的支配連通情況，選擇與m r-CDS做比較，實(shí)驗(yàn)結(jié)果來自于20次仿真結(jié)果。

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

4.1 分簇仿真

在節(jié)點(diǎn)數(shù)為100的平臺(tái)上分別仿真ASCDS算法和mr-CDS算法，設(shè)置節(jié)點(diǎn)的通信半徑為20 m，觀察生成的連通支配集情況，實(shí)驗(yàn)結(jié)果仿真如圖3所示。在圖3中，加號(hào)代表連通支配集里面的節(jié)點(diǎn)，而圓圈代表支配節(jié)點(diǎn)，中心的叉號(hào)代表基站。

圖3 ASCDS算法和mr-CDS算法分簇對(duì)比

從圖3中可以看出，ASCDS算法的構(gòu)建覆蓋了所有節(jié)點(diǎn)連通支配集，集合中支配節(jié)點(diǎn)為11個(gè)，比mr-CDS產(chǎn)生的包含14個(gè)支配節(jié)點(diǎn)的連通支配集的規(guī)模要小，因?yàn)閙r-CDS在連通過程中，連接節(jié)點(diǎn)是由非支配節(jié)點(diǎn)決定的，從而造成了支配節(jié)點(diǎn)間可以存在多個(gè)連接節(jié)點(diǎn)，而ASCDS算法的連接節(jié)點(diǎn)是由ID較小的支配節(jié)點(diǎn)決定，它會(huì)選擇能量較大的節(jié)點(diǎn)擔(dān)任連接節(jié)點(diǎn)，而非支配節(jié)點(diǎn)就可以節(jié)省能量做其他工作。

4.2 生成連通支配集時(shí)消耗的能量

在100 m×100 m區(qū)域內(nèi)分別設(shè)置n=100，200，300和400的節(jié)點(diǎn)，計(jì)算在生成連通支配集時(shí)消耗能量的平均值。其中，節(jié)點(diǎn)的通信半徑分別為r=20 m和r=30 m，實(shí)驗(yàn)結(jié)果如圖4所示。從圖中可以看出，節(jié)點(diǎn)增加的同時(shí)，2種算法消耗的能量均呈遞增趨勢(shì)，因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，需要接收鄰居節(jié)點(diǎn)發(fā)來的消息也增多，網(wǎng)絡(luò)規(guī)模增大，消耗的能量隨之增加。但是也可以從圖中看出因?yàn)樯傻闹浼。訟SCDS算法比mr-CDS算法消耗的能量要小，節(jié)點(diǎn)的能量可以提供更多輪數(shù)據(jù)的收集。

圖4 生成連通支配集的能耗比

從圖4可以看出，節(jié)點(diǎn)增加的同時(shí)，2種算法消耗的能量均呈遞增趨勢(shì)，因?yàn)殡S著節(jié)點(diǎn)數(shù)量的增多，需要接收鄰居節(jié)點(diǎn)發(fā)來的消息也增多，網(wǎng)絡(luò)規(guī)模增大，消耗的能量隨之增加。但是也可以從圖中看出，因?yàn)樯傻闹浼?，所以ASCDS算法比mr-CDS算法消耗的能量要小，節(jié)點(diǎn)的能量可以提供更多輪數(shù)據(jù)的收集。

4.3 網(wǎng)絡(luò)生命周期對(duì)比

無線傳感器網(wǎng)絡(luò)因?yàn)槟芰坑邢?，所以用盡可能有限的能量完成更多輪數(shù)據(jù)的收集是WSN網(wǎng)絡(luò)重要的一部分。

當(dāng)前階段有很多算法先將節(jié)點(diǎn)構(gòu)成連通支配集，然后構(gòu)成融合樹，最終把數(shù)據(jù)送到SINK節(jié)點(diǎn)。本文算法數(shù)據(jù)收集采用的是基于近似最大獨(dú)立集的自適應(yīng)數(shù)據(jù)調(diào)度算法，而mr-CDS采用的是距離向量DV算法［13］。

從圖5可以看出，不同網(wǎng)絡(luò)條件下，ASCDS算法比mr-CDS算法的生命周期長，這是因?yàn)锳SCDS算法在構(gòu)建網(wǎng)絡(luò)時(shí)考慮了能量和節(jié)點(diǎn)度的關(guān)系，在數(shù)據(jù)調(diào)度時(shí)通過自適應(yīng)的調(diào)度最大加權(quán)獨(dú)立集降低時(shí)延，通過調(diào)節(jié)參數(shù)來限制發(fā)送次數(shù)，實(shí)現(xiàn)數(shù)據(jù)融合和能量消耗的性能平衡?？梢姡珹SCDS能減少能量消耗，能有效延長網(wǎng)絡(luò)生命周期。然而，ASCDS構(gòu)造的支配集屬于 1-連通、2-支配的支配集，因此ASCDS在可靠性方面的性能仍有待提高。ASCDS與相關(guān)算法的性能對(duì)比如表2所示。

圖5 網(wǎng)絡(luò)生命周期對(duì)比

表2 不同算法的性能對(duì)比

5 結(jié)束語

本文提出基于連通支配集的自適應(yīng)數(shù)據(jù)調(diào)度算法，根據(jù)節(jié)點(diǎn)的能量值和度得出自身權(quán)值，該值大于鄰居節(jié)點(diǎn)時(shí)則成為支配節(jié)點(diǎn)，在連通時(shí)則ID小的支配節(jié)點(diǎn)決定擔(dān)任連接節(jié)點(diǎn)。在數(shù)據(jù)調(diào)度時(shí)采用基于近似最大獨(dú)立集的自適應(yīng)算法。實(shí)驗(yàn)分析結(jié)果表明，該算法比已有的算法網(wǎng)絡(luò)形成的規(guī)模更小，消耗更少的能量，從而獲得較長的網(wǎng)絡(luò)生命周期。在真實(shí)的環(huán)境中設(shè)計(jì)能耗低同時(shí)可靠性高的數(shù)據(jù)調(diào)度算法是接下來的研究方向。

［1］ 于廣州.WSN中面向數(shù)據(jù)收集的網(wǎng)絡(luò)拓?fù)錁?gòu)造算法［J］.計(jì)算機(jī)工程，2014，40（4）：64-70.

［2］ 鄭 嬋，孫世新，黃天云.Ad Hoc網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)中連通支配集的分布式構(gòu)造［J］.軟件學(xué)報(bào)，2011，22（5）：1053-1066.

［3］ 趙學(xué)鋒.基于 GSO算法的最小連通支配集問題求解［J］.計(jì)算機(jī)工程，2013，39（2）：99-102.

［4］ Kim Donghyun，Wu Yiwei，Li Yingshu，et al. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20（2）：147-157. ［5］ Hussain S，Shafique M H，Yang L T.Constructing a CDS-based Network Backbone for Energy Efficiency in Industrial Wireless Sensor Network［C］//Proceedings of the 12th IEEE International Conference on High Performance Computing and Communications.Washington D.C.，USA：IEEE Press，2010：322-328.

［6］ Wu Yiwei，Li Yingshu.Construction Algorithms for kconnected m-dominating Sets in Wireless Sensor Networks［C］//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA：ACM Press，2008：83-90.

［7］ 李 輝，劉書吉.基于節(jié)點(diǎn)度和距離的WSN分簇路由算法［J］.計(jì)算機(jī)工程，2014，40（3）：114-119.

［8］ 奎曉燕，杜華坤，梁俊斌.無線傳感器網(wǎng)絡(luò)中一種能量均衡的基于連通支配集的數(shù)據(jù)收集算法［J］.電子學(xué)報(bào)，2013，41（8）：1521-1528.

［9］ 鄭 嬋，尹 令，孫世新.無線傳感器網(wǎng)絡(luò)中2-連通k-支配的容錯(cuò)連通支配集構(gòu)造［J］.控制與決策，2013，28（5）：650-656.

［10］ 劉文彬，李香寶，付 沙，等.無線傳感器網(wǎng)絡(luò)中的改進(jìn)數(shù)據(jù)聚集調(diào)度算法［J］.計(jì)算機(jī)工程，2014，40（1）：93-97.

［11］ 郜 帥，張宏科.時(shí)延受限傳感器網(wǎng)絡(luò)移動(dòng)Sink路徑選擇方法研究［J］.電子學(xué)報(bào)，2011，39（4）：742-747.

［12］ 許 建，楊 庚，陳正宇，等.基于二次獨(dú)立集的數(shù)據(jù)融合調(diào)度算法［J］.通信學(xué)報(bào)，2014，35（1）：62-71.

［13］ Malhotra R.IP Routing［M］.［S.l.］：O’Reilly Media，Inc.，2002.

編輯 顧逸斐

Adaptive Data Scheduling Algorithm in WSN Based on Connected Dominating Set

KONG Fanfeng1，OU Hongyu1，LONG Linde1，CHEN Xi2
（1.Department of Mobile Communication，Hunan Post and Telecommunication College，Changsha 410115，China；2.School of Computer and Communication Engineering，Changsha University of Science&Technology，Changsha 410114，China）

In Wireless Sensor Network（WSN）constructing connected dominating set based virtual backbone，help to optimize multi-level hierarchical networks，which prevents the node’s death caused by the death of the data link. However，the minimum connected dominating set can not balance the energy consumptions to premature death.This paper presents an adaptive data gathering algorithm in WSN based on connected dominating set.Connected set by selecting the node has high energy and large degree from a dominating set which forms higher energy network backbone.Data through adaptive scheduling along the smaller network backbone seek route until the base station.Simulation results show that the proposed algorithm has a good performance with fault-tolerant in smaller network size，reduces the energy consumption and prolongs the network life cycle.

Wireless Sensor Network（WSN）；virtual backbone；connected dominating set；data scheduling；energy consumption；life cycle

孔凡鳳，歐紅玉，龍林德，等.基于連通支配集的 WSN自適應(yīng)數(shù)據(jù)調(diào)度算法［J］.計(jì)算機(jī)工程，2015，41（10）：94-98，104.

英文引用格式：Kong Fanfeng，Ou Hongyu，Long Linde，et al.Adaptive Data Scheduling Algorithm in WSN Based on Connected Dominating Set［J］.Computer Engineering，2015，41（10）：94-98，104.

1000-3428（2015）10-0094-05

A

TP301.6

國家自然科學(xué)基金青年基金資助項(xiàng)目（61303043）。

孔凡鳳（1979-），女，碩士，主研方向：無線傳感器網(wǎng)絡(luò)；歐紅玉、龍林德，講師；陳 曦，教授。

2014-09-16

2014-11-11E-m ail：maomaokff@163.com