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

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

（1.湖南郵電職業(yè)技術學院移動通信系，長沙 410115；2.長沙理工大學計算機與通信工程學院，長沙 410114）

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

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

（1.湖南郵電職業(yè)技術學院移動通信系，長沙 410115；2.長沙理工大學計算機與通信工程學院，長沙 410114）

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

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

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

1 概述

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

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

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

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

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

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

2.1 連通支配集的模型

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

2.2 連通支配集構造描述

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

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

2.2.1 身份階段

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

圖1 連通支配集形成過程

對該階段的描述如下：

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

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

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

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

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

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

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

如果color（νi）=gray，則說明νi的鄰居里面至少有一個1跳的νm，而且2跳的鄰居里面還有一個νk。如果IDm＜IDk，則νi廣播一個Mesg2（νi，νj，νk），這里要求IDm＜IDk是因為ASCDS算法規(guī)定由ID號小的節(jié)點決定是否與其ID號大的節(jié)點連通，如果ν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可以是一個也可以是多個），則比較νl和νj的權值大小，如果Wl＜Wj，則將［νl，νk］刪除并增加［νj，νk］，相反，則不增加［νl，νk］。 如果節(jié)點νi第一次接收到Mesg1和Mesg2消息，則啟動定時器Timer，等待Δ秒，這Δ秒能保證接收到其他鄰居節(jié)點發(fā)來的Mesg1和Mesg2消息。

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

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

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

對于表List2中的每條記錄［νn，νj，νk］，將νn，νj加入集合F中。最后將F放入消息connector（F，2）中并廣播出去，數(shù)字2表示會廣播2次，每被轉發(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ào)度過程依據(jù)服務概率去確定每個時隙中的通信鏈路集合。在其他研究人員提出的算法中，基本上采用的是每個鏈路只調(diào)度一次的原則［11］，這種方法讓權重數(shù)高得無法優(yōu)先調(diào)度，但是又不能無限制調(diào)度，如何調(diào)整通信次數(shù)是實現(xiàn)能量均衡和延長生命周期的關鍵參數(shù)。

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

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

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

（3）構造鏈路的沖突矩陣CM，構造以CM為鄰接矩陣的最大獨立集。

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

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

t=t+1，轉到步驟（2）。

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

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

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

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

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

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

4 仿真結果與性能比較

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

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

4.1 分簇仿真

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

圖3 ASCDS算法和mr-CDS算法分簇對比

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

4.2 生成連通支配集時消耗的能量

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

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

從圖4可以看出，節(jié)點增加的同時，2種算法消耗的能量均呈遞增趨勢，因為隨著節(jié)點數(shù)量的增多，需要接收鄰居節(jié)點發(fā)來的消息也增多，網(wǎng)絡規(guī)模增大，消耗的能量隨之增加。但是也可以從圖中看出，因為生成的支配集要小，所以ASCDS算法比mr-CDS算法消耗的能量要小，節(jié)點的能量可以提供更多輪數(shù)據(jù)的收集。

4.3 網(wǎng)絡生命周期對比

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

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

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

圖5 網(wǎng)絡生命周期對比

表2 不同算法的性能對比

5 結束語

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

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

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

［3］ 趙學鋒.基于 GSO算法的最小連通支配集問題求解［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é)點度和距離的WSN分簇路由算法［J］.計算機工程，2014，40（3）：114-119.

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

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

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

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

［12］ 許 建，楊 庚，陳正宇，等.基于二次獨立集的數(shù)據(jù)融合調(diào)度算法［J］.通信學報，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自適應數(shù)據(jù)調(diào)度算法［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

國家自然科學基金青年基金資助項目（61303043）。

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

2014-09-16

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