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

趙 煜，降愛蓮

(太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原030024)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)廣泛應(yīng)用在很多重點(diǎn)領(lǐng)域，如國(guó)防、環(huán)境監(jiān)測(cè)、工農(nóng)業(yè)控制等，具有較高的應(yīng)用價(jià)值。傳感器節(jié)點(diǎn)由電池供電，電量有限，能量一旦耗盡將不能繼續(xù)正常工作，所以，在保證網(wǎng)絡(luò)連通的前提下，如何能夠更有效地提高能量使用效率，延長(zhǎng)系統(tǒng)生命周期，是目前亟待解決的重要問題。

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

1 現(xiàn)有算法描述

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

文獻(xiàn)［7］利用分布式算法Leader Election 構(gòu)建一棵有根樹，接著找到MIS，最后在此基礎(chǔ)上求解CDS。在文獻(xiàn)［7］的基礎(chǔ)上，文獻(xiàn)［8，9］分別對(duì)連接MIS 的頂點(diǎn)方式和構(gòu)造MIS 的方式做出了改進(jìn)。

文獻(xiàn)［6］在文獻(xiàn)［8，9］的基礎(chǔ)上，提出首先通過BFS 建立一棵有根樹，獲得頂點(diǎn)的等級(jí)和優(yōu)先次序表，再次憑借優(yōu)先次序表得到MIS，最后找到連接點(diǎn)將MIS 中的節(jié)點(diǎn)連接起來形成MCDS。文獻(xiàn)［10］在文獻(xiàn)［6］啟發(fā)下，考慮了能量問題，但是需要連續(xù)兩個(gè)算法才能降低能耗，稍顯復(fù)雜。

本文在參考以上文獻(xiàn)基礎(chǔ)上，提出一種參考能量的MCDS 高效近似算法。本算法既可以得到一個(gè)MCDS，還可以均衡整個(gè)網(wǎng)絡(luò)的能耗，有效延長(zhǎng)生命周期。

2 CDS 相關(guān)術(shù)語

2.1 CDS 基本概念

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

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

圖1 頂點(diǎn){3，6，7}為MDSFig 1 Vertex{3，6，7}as MDS

圖2 頂點(diǎn){4，5，7}為MCDSFig 2 Vertex{4，5，7}as MCDS

2.2 相關(guān)定義及其說明

Value 的定義:對(duì)圖中任意一個(gè)節(jié)點(diǎn) u，定義Value(u)=(weight(u)，id(u))，其中，weight(u)為節(jié)點(diǎn)u的度與剩余能量的權(quán)值，id(u)為節(jié)點(diǎn)U 的編號(hào)。對(duì)于任意兩個(gè)節(jié)點(diǎn)A，B，若Value(A)＞ Value(B)，當(dāng)且僅當(dāng)weight(A)＞weight(B)。

表1 中所列符號(hào)為文中需要的重要符號(hào)。

3 構(gòu)造參考能量的MCDS 算法

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

表1 符號(hào)說明Tab 1 Symbol description

接下來將對(duì)以上步驟進(jìn)行詳細(xì)闡述。

3.1 構(gòu)造頂點(diǎn)優(yōu)點(diǎn)次序表

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

式中 du為節(jié)點(diǎn)u 的度，n 為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，Eu為節(jié)點(diǎn)u的當(dāng)前剩余能量，Emax為節(jié)點(diǎn)u 及其鄰居節(jié)點(diǎn)中剩余能量的最大值，α 為權(quán)重因子。

2)計(jì)算全網(wǎng)每一個(gè)節(jié)點(diǎn)的Value 值，并根據(jù)Value 值從大到小對(duì)節(jié)點(diǎn)進(jìn)行排序，將節(jié)點(diǎn)相對(duì)應(yīng)的ID 保存到節(jié)點(diǎn)優(yōu)先次序表L 的表項(xiàng)li中。

通過上述步驟可知，在全網(wǎng)中優(yōu)先選擇連通度大、剩余能量更多的節(jié)點(diǎn)作為CDS 節(jié)點(diǎn)，增強(qiáng)了CDS 節(jié)點(diǎn)選擇的針對(duì)性，并且，由于MCDS 組成的骨干網(wǎng)絡(luò)節(jié)點(diǎn)在信息轉(zhuǎn)發(fā)時(shí)會(huì)消耗更多的能量，所以，考慮了節(jié)點(diǎn)的剩余能量，使網(wǎng)絡(luò)能量保持動(dòng)態(tài)平衡。

3.2 構(gòu)造MIS

1)設(shè)置全網(wǎng)節(jié)點(diǎn)為未標(biāo)號(hào)，表示節(jié)點(diǎn)未遍歷。

2)根據(jù)L 中的優(yōu)先級(jí)順序由高到低依次對(duì)各節(jié)點(diǎn)進(jìn)行標(biāo)記，L 中第一個(gè)節(jié)點(diǎn)li標(biāo)記為Black，并將其ID 加入到M 的表項(xiàng)m1中。

3)從L 中第二個(gè)節(jié)點(diǎn)l2起，若N(li)中沒有任何一個(gè)節(jié)點(diǎn)標(biāo)記為Black，則將節(jié)點(diǎn)ID 加入到M 的表項(xiàng)mj中;否則，i=i+1。

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

3.3 連接MIS

1)將M 中的節(jié)點(diǎn)賦予集合C;

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

3.4 構(gòu)造MCDS

構(gòu)造的CDS 中可能有冗余節(jié)點(diǎn)，將按以下步驟進(jìn)行優(yōu)化得到較小的MCDS:

1)刪除集合C 中所有度為1 的節(jié)點(diǎn);

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

4 算法仿真與性能分析

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

第一組實(shí)驗(yàn)是計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目為300 時(shí)，不同通信半徑條件下各算法得到的MCDS 平均大小，結(jié)果如圖3 所示。

圖3 不同通信半徑對(duì)應(yīng)的MCDS 平均大小Fig 3 Average size of MCDS according to different communication radius

第二組實(shí)驗(yàn)是計(jì)算節(jié)點(diǎn)發(fā)送半徑r 為30 m 時(shí)，分布不同傳感器節(jié)點(diǎn)數(shù)目條件下各算法得到的MCDS 的平均大小，結(jié)果如圖4 所示。

圖4 不同傳感器節(jié)點(diǎn)數(shù)目對(duì)應(yīng)的MCDS 平均大小Fig 4 Average size of MCDS according to different number of sensor nodes

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

第三組實(shí)驗(yàn)比較隨機(jī)產(chǎn)生的500 個(gè)節(jié)點(diǎn)在不同算法作用下，其平均能量隨時(shí)間的變化，結(jié)果如圖5 所示。

圖5 節(jié)點(diǎn)平均能量變化趨勢(shì)Fig 5 Change trend of average energy of nodes

5 結(jié) 論

本文設(shè)計(jì)出一種參考能量的求解MCDS 的近似算法，經(jīng)過實(shí)驗(yàn)仿真結(jié)果證明:本算法在減小CDS 規(guī)模和延長(zhǎng)網(wǎng)絡(luò)生命周期方面是有效的，為延長(zhǎng)無線傳感器使用壽命創(chuàng)造了條件。

［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］ 卞永釗，于海斌，曾 鵬.無線傳感器網(wǎng)絡(luò)中一種啟發(fā)式最小連通支配集算法［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 中基于能量代價(jià)的最小權(quán)和支配集拓?fù)淇刂扑惴ǎ跩］.電子與信息學(xué)報(bào)，2010，32(4):857－863.

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

［7］ Alzoubi K M，Wan P J，F(xiàn)reider 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，F(xiàn)u 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］黃行波，程紅舉.無線傳感器網(wǎng)絡(luò)中使用連通支配集的最小能耗廣播算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2014(1):74－79.