基于連通支配集的WSN自適應數據調度算法

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

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

基于連通支配集的WSN自適應數據調度算法

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

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

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

無線傳感器網絡；虛擬骨干；連通支配集；數據調度；能量消耗；生命周期

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

1 概述

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

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

仍然能實現骨干網數據的連通。m-支配是指任一個被支配節點至少與m個支配節點連接。通過這個虛擬的骨干網讓無線傳感器網絡的網絡構造規模變小，減少節點間數據通信的次數［3］。

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

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

2 系統模型及問題描述

2.1 連通支配集的模型

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

2.2 連通支配集構造描述

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

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

2.2.1 身份階段

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

圖1 連通支配集形成過程

對該階段的描述如下：

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

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

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

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

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

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

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

如果color（νi）=gray，則說明νi的鄰居里面至少有一個1跳的νm，而且2跳的鄰居里面還有一個νk。如果IDm＜IDk，則νi廣播一個Mesg2（νi，νj，νk），這里要求IDm＜IDk是因為ASCDS算法規定由ID號小的節點決定是否與其ID號大的節點連通，如果νm決定建立連接，則建立了νm→νi→νj→νk的路徑。

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

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

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

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

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

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

3 數據融合調度過程

數據融合調度的最終目的是為節點分配時隙，本文主要的調度過程依據服務概率去確定每個時隙中的通信鏈路集合。在其他研究人員提出的算法中，基本上采用的是每個鏈路只調度一次的原則［11］，這種方法讓權重數高得無法優先調度，但是又不能無限制調度，如何調整通信次數是實現能量均衡和延長生命周期的關鍵參數。

調度步驟如下：

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

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

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

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

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

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

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

圖2 不同時隙內鏈路的選取

此調度方法執行后，有：

（1）所有被采集數據被匯聚到SINK節點；

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

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

4 仿真結果與性能比較

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

表1 仿真參數設置

4.1 分簇仿真

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

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

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

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

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

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

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

4.3 網絡生命周期對比

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

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

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

圖5 網絡生命周期對比

表2 不同算法的性能對比

5 結束語

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

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

［2］ 鄭 嬋，孫世新，黃天云.Ad Hoc網絡和無線傳感器網絡中連通支配集的分布式構造［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］ 李 輝，劉書吉.基于節點度和距離的WSN分簇路由算法［J］.計算機工程，2014，40（3）：114-119.

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

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

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

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

［12］ 許 建，楊 庚，陳正宇，等.基于二次獨立集的數據融合調度算法［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自適應數據調度算法［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-），女，碩士，主研方向：無線傳感器網絡；歐紅玉、龍林德，講師；陳 曦，教授。

2014-09-16

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