一種參考能量的最小連通支配集近似算法

趙 煜，降愛蓮

(太原理工大學 計算機科學與技術學院，山西 太原030024)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)廣泛應用在很多重點領域，如國防、環境監測、工農業控制等，具有較高的應用價值。傳感器節點由電池供電，電量有限，能量一旦耗盡將不能繼續正常工作，所以，在保證網絡連通的前提下，如何能夠更有效地提高能量使用效率，延長系統生命周期，是目前亟待解決的重要問題。

在無線傳感器網絡中，廣播操作通常使用“泛洪(flooding)”來完成，經過分析表明［1］，“泛洪”可能會帶來廣播風暴問題。在保證覆蓋和連通的前提下，使用連通支配集(CDS)算法可以構造一個臨時轉發數據的骨干網絡。只有網絡中的骨干節點負責轉發數據，而那些非骨干節點在不發送數據時，可關閉通信模塊以節省能量。為了使網絡壽命最大化，需要構造一個最小連通支配集(MCDS)的骨干網絡。然而，求解一個網絡圖的MCDS 是一個NP 難題［2］，目前還沒有成熟算法，因此，需要設計一種高效的近似算法來求解網絡圖的MCDS。

1 現有算法描述

目前求解MCDS 的方法主要有兩種:一是先找出一個CDS，然后逐步對進行CDS 優化，減少其頂點總數從而得到MCDS［3，4］;二是先找出一個極大獨立集(MIS)，再尋找連接點，將MIS 中的頂點連接起來最終得到MCDS［5，6］。

文獻［7］利用分布式算法Leader Election 構建一棵有根樹，接著找到MIS，最后在此基礎上求解CDS。在文獻［7］的基礎上，文獻［8，9］分別對連接MIS 的頂點方式和構造MIS 的方式做出了改進。

文獻［6］在文獻［8，9］的基礎上，提出首先通過BFS 建立一棵有根樹，獲得頂點的等級和優先次序表，再次憑借優先次序表得到MIS，最后找到連接點將MIS 中的節點連接起來形成MCDS。文獻［10］在文獻［6］啟發下，考慮了能量問題，但是需要連續兩個算法才能降低能耗，稍顯復雜。

本文在參考以上文獻基礎上，提出一種參考能量的MCDS 高效近似算法。本算法既可以得到一個MCDS，還可以均衡整個網絡的能耗，有效延長生命周期。

2 CDS 相關術語

2.1 CDS 基本概念

定義1 (獨立集):G=(V，E)是簡單無向圖，S?V 且，若S 中任何兩個頂點都不相鄰，則稱S 為G 的獨立集。如果在S 中再添加任何節點vi∈V，且vi?S，都不再是G 的獨立集，則S 為G 的MIS。

定義2 (支配集):在簡單連通無向圖G=(V，E)中，有S?V 且S≠?，對于?vi∈V，若vi?S，則vi至少與S 中的一個頂點相鄰，稱S 為G 的一個支配集(DS)。若支配集S 中的頂點數最少，則稱S 為G 的MDS;若支配集S 的生成子圖是連通的，則S 為一個CDS，若連通支配集S 中的頂點數最少，則稱S 為G 的MCDS。圖1、圖2 所示分別為圖G的MDS，MCDS。

圖1 頂點{3，6，7}為MDSFig 1 Vertex{3，6，7}as MDS

圖2 頂點{4，5，7}為MCDSFig 2 Vertex{4，5，7}as MCDS

2.2 相關定義及其說明

Value 的定義:對圖中任意一個節點 u，定義Value(u)=(weight(u)，id(u))，其中，weight(u)為節點u的度與剩余能量的權值，id(u)為節點U 的編號。對于任意兩個節點A，B，若Value(A)＞ Value(B)，當且僅當weight(A)＞weight(B)。

表1 中所列符號為文中需要的重要符號。

3 構造參考能量的MCDS 算法

本文設計的求解最小連通支配集算法分為以下若干步驟:1)構造一個以頂點的度和剩余能量值的權值為判斷值的頂點優先次序表;2)根據得出的頂點優先次序表構造MIS;3)根據MIS 中頂點的鄰接點集合和頂點優先次序表找到連接點，構成連通支配集;4)對CDS 進行優化，最終得到MCDS。

表1 符號說明Tab 1 Symbol description

接下來將對以上步驟進行詳細闡述。

3.1 構造頂點優點次序表

1)全網各節點首先廣播Hello 信令，節點在接收到Hello 信令后，各節點計算得到自身的度degree(u)，鄰接點集合N(u)以及鄰居節點剩余能量值energy(u)。計算節點的度與剩余能量的均值公式(1)為

式中 du為節點u 的度，n 為網絡節點總數，Eu為節點u的當前剩余能量，Emax為節點u 及其鄰居節點中剩余能量的最大值，α 為權重因子。

2)計算全網每一個節點的Value 值，并根據Value 值從大到小對節點進行排序，將節點相對應的ID 保存到節點優先次序表L 的表項li中。

通過上述步驟可知，在全網中優先選擇連通度大、剩余能量更多的節點作為CDS 節點，增強了CDS 節點選擇的針對性，并且，由于MCDS 組成的骨干網絡節點在信息轉發時會消耗更多的能量，所以，考慮了節點的剩余能量，使網絡能量保持動態平衡。

3.2 構造MIS

1)設置全網節點為未標號，表示節點未遍歷。

2)根據L 中的優先級順序由高到低依次對各節點進行標記，L 中第一個節點li標記為Black，并將其ID 加入到M 的表項m1中。

3)從L 中第二個節點l2起，若N(li)中沒有任何一個節點標記為Black，則將節點ID 加入到M 的表項mj中;否則，i=i+1。

4)若L 中全部節點均已遍歷完畢，則算法結束;否則，轉至步驟(3)。

3.3 連接MIS

1)將M 中的節點賦予集合C;

2)遍歷M 中各節點及其鄰接點集合N(u)，根據頂點優先次序表L，將N(u)中節點優先級最高的一個節點加入到集合C 中。得到的集合C 即為CDS，算法結束。

3.4 構造MCDS

構造的CDS 中可能有冗余節點，將按以下步驟進行優化得到較小的MCDS:

1)刪除集合C 中所有度為1 的節點;

2)遍歷集合C 中各節點的鄰接點集合N(u)中的每一個節點v，若在N(v)中都可以找到除節點u 以外的集合C中的任意一個節點，則在集合C 中將節點u 刪除，并更新相應的集合;優化后的集合C 即為MCDS，算法結束。

4 算法仿真與性能分析

本文利用Matlab 仿真平臺來考察本算法的性能，仿真環境設為200 m×200 m 的正四邊形區域，隨機投放一定數量的節點傳感器，均具有相同的通信半徑，α=0.1，節點剩余能量在［0.8Emax，Emax］范圍內隨機取值(Emax=1)。為保證仿真結果可靠性，每次仿真實驗運行50 次，取仿真結果平均值。實驗用參數為網絡覆蓋范圍為200 m×200 m;節點個數為100～500 個;通信半徑為20～45 m。

第一組實驗是計算網絡節點數目為300 時，不同通信半徑條件下各算法得到的MCDS 平均大小，結果如圖3 所示。

圖3 不同通信半徑對應的MCDS 平均大小Fig 3 Average size of MCDS according to different communication radius

第二組實驗是計算節點發送半徑r 為30 m 時，分布不同傳感器節點數目條件下各算法得到的MCDS 的平均大小，結果如圖4 所示。

圖4 不同傳感器節點數目對應的MCDS 平均大小Fig 4 Average size of MCDS according to different number of sensor nodes

從上圖中可以看出:在不同通信半徑和分布不同節點數量條件下，本文提出的算法所找到的MCDS 較其他兩個都小，具有較好的性能。

第三組實驗比較隨機產生的500 個節點在不同算法作用下，其平均能量隨時間的變化，結果如圖5 所示。

圖5 節點平均能量變化趨勢Fig 5 Change trend of average energy of nodes

5 結 論

本文設計出一種參考能量的求解MCDS 的近似算法，經過實驗仿真結果證明:本算法在減小CDS 規模和延長網絡生命周期方面是有效的，為延長無線傳感器使用壽命創造了條件。

［1］ Tseng Y，Ni S，Chen Y，et al.The broadcast storm problem in a mobile Ad－Hoc network［J］.Wireless Networks，2002，8(2/3):153－167.

［2］ Gao S，Vu C T，Li Y S.Sensor scheduling for k－coverage in wireless sensor networks［C］∥Proc of the MSN，2006:268－280.

［3］ 卞永釗，于海斌，曾 鵬.無線傳感器網絡中一種啟發式最小連通支配集算法［J］.信息與控制，2009，38(3):193－199.

［4］ Ravi Prakash.A routing algorithm for wireless Ad Hoc networks with unidirectional links［J］.Wireless Networks，2001，7:617－625.

［5］ 孫 超，尹榮榮，郝曉辰，等.WSNs 中基于能量代價的最小權和支配集拓撲控制算法［J］.電子與信息學報，2010，32(4):857－863.

［6］ 廖飛雄，馬 良，范炳全.一種求解最小連通支配集的高效近似算法［J］.小型微型計算機系統，2008，29(5):875－878.

［7］ Alzoubi K M，Wan P J，Freider O.Distributed heuristics for connected dominating set in wireless Ad Hoc networks［J］.IEEE Com Soc/KICS Journal on Communication Networks，2002，4(1):22－29.

［8］ Han Bo，Fu Haohuan，Lin Lidong，et al.Efficient construction of connected dominating set in wireless Ad Hoc networks［C］∥2004 IEEE International Conference on Mobile Ad－Hoc and Sensor Systems，2004:570－572.

［9］ Gao Bo，Yang Yuhang，Ma Huiye.A new distributed approximation algorithm for constructing minimum connected dominating set in wireless Ad Hoc networks［C］∥Proceedings of the Second International Symposium on Parallel and Distributed Processing and Applications，ISPA 2004，Hong Kong，China，2004:3358.

［10］黃行波，程紅舉.無線傳感器網絡中使用連通支配集的最小能耗廣播算法［J］.小型微型計算機系統，2014(1):74－79.