凌 飛，吳振華

(南昌航空大學(xué)軟件學(xué)院，南昌 330063)

集成了傳感器、微機(jī)電系統(tǒng)和網(wǎng)絡(luò)三大技術(shù)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)，近年來受到人們的廣泛關(guān)注［1－2］。WSN是一種大規(guī)模、無線、自組織、多跳、無基礎(chǔ)設(shè)施支持的網(wǎng)絡(luò)，其中節(jié)點(diǎn)成本較低、體積較小，具有傳感、數(shù)據(jù)處理和短距離無線通信等功能，大部分節(jié)點(diǎn)不移動(dòng)，被隨意撒布在監(jiān)測(cè)區(qū)域內(nèi)，在軍事國(guó)防、環(huán)境科學(xué)、醫(yī)療健康、空間探索以及商業(yè)應(yīng)用等領(lǐng)域具有廣闊的應(yīng)用前景［3－4］。為了提高廣播效率、節(jié)能等，最小連通支配集(Minimum Connected Dominating Set，MCDS)被廣泛應(yīng)用于形成虛擬骨干網(wǎng)的分層路由協(xié)議。然而在一個(gè)圖中求解MCDS是一個(gè)NP難問題，在實(shí)際應(yīng)用中通常只能采用近似求解算法。

有關(guān)MCDS的構(gòu)造算法，目前主要分為兩類:集中式算法［5－6］和分布式算法［7－13］。集中式算法要求把整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔⒓械侥硞€(gè)中心節(jié)點(diǎn)，而這將需要花費(fèi)極大的通信代價(jià)和出現(xiàn)局部節(jié)點(diǎn)通信量過大的問題，因而不適用于WSN，但獲得的連通支配集(Connected Dominating Set，CDS)通常比分布式的小，這是因?yàn)榧惺剿惴〒碛姓麄€(gè)網(wǎng)絡(luò)的拓?fù)湫畔?。文獻(xiàn)［5］提出了一種集中式算法，其主要思想是把最大度的節(jié)點(diǎn)作為根節(jié)點(diǎn)開始構(gòu)建一棵樹，樹包含圖中所有節(jié)點(diǎn)，樹的葉子節(jié)點(diǎn)為非支配點(diǎn)，非葉子節(jié)點(diǎn)為支配點(diǎn)。該算法時(shí)間復(fù)雜度高。文獻(xiàn)［6］在文獻(xiàn)［5］的基礎(chǔ)上證明了MCDS是圖的一棵包含最多葉子節(jié)點(diǎn)的生成樹的非葉子節(jié)點(diǎn)集合，根據(jù)這個(gè)結(jié)論設(shè)計(jì)了一種新的構(gòu)造MCDS的算法。分布式算法只需要知道當(dāng)前節(jié)點(diǎn)的局部信息，各個(gè)節(jié)點(diǎn)獨(dú)立地計(jì)算自己的連接情況，具有較強(qiáng)的自組織能力。根據(jù)構(gòu)造CDS的連通性又可以分為基于鄰節(jié)點(diǎn)信息［7］和基于極大獨(dú)立集(Maximum Independent Set，MIS)［8－9］兩類?；卩徆?jié)點(diǎn)信息的算法是利用節(jié)點(diǎn)N跳(通常為1－2跳)內(nèi)的拓?fù)湫畔l(fā)式構(gòu)造CDS；而基于MIS的算法是先構(gòu)建一個(gè)MIS，然后再添加一些網(wǎng)關(guān)節(jié)點(diǎn)將MIS連通，進(jìn)而構(gòu)成CDS。文獻(xiàn)［7］提出了一種簡(jiǎn)單的構(gòu)造CDS的分布式近似算法，其思想是任一節(jié)點(diǎn)當(dāng)它有兩個(gè)鄰居節(jié)點(diǎn)不相鄰時(shí)它為支配點(diǎn)。該方法的缺點(diǎn)是有較多的冗余支配點(diǎn)且在網(wǎng)絡(luò)拓?fù)浣?jīng)常變化時(shí)運(yùn)算過于復(fù)雜。文獻(xiàn)［8］提出了一種運(yùn)用leader-election算法生成一棵樹來構(gòu)造一個(gè)MIS，然后在它的基礎(chǔ)上添加部分網(wǎng)關(guān)節(jié)點(diǎn)來構(gòu)造CDS的算法，文獻(xiàn)［9］在文獻(xiàn)［8］的基礎(chǔ)上進(jìn)行了改進(jìn)，在構(gòu)造MIS的同時(shí)通過添加MIS中各節(jié)點(diǎn)的父節(jié)點(diǎn)為支配點(diǎn)來構(gòu)造CDS。

上述算法均沒有考慮節(jié)點(diǎn)能量對(duì)網(wǎng)絡(luò)性能的影響，網(wǎng)絡(luò)能量利用不均衡。為了構(gòu)造高效的MCDS，文獻(xiàn)［10］提出了一種基于極大權(quán)的MCDS分布式算法，文獻(xiàn)［11］利用修剪規(guī)則盡量保留權(quán)值大的節(jié)點(diǎn)充當(dāng)支配點(diǎn)，但該算法沒有考慮節(jié)點(diǎn)的能量限制問題，文獻(xiàn)［12］引入了候選支配點(diǎn)，一方面可以為某個(gè)時(shí)段能量消耗過快的支配點(diǎn)分流，另一方面可以替代因剩余能量低于一個(gè)閾值的支配點(diǎn)工作，但該算法的CDS偏大。

針對(duì)目前構(gòu)造CDS之不足，本文借鑒了文獻(xiàn)［9］的思想，綜合考慮了剩余能量、能量閾值、節(jié)點(diǎn)度和理想支配節(jié)點(diǎn)數(shù)等影響網(wǎng)絡(luò)能量利用率的因素，提出了一種能量均衡的最小連通支配集分布式算法(Distributed Algorithm for Energy-Balance Minimum Connected Dominating Set，EB-MCDS)。

1 問題描述

近年來，許多學(xué)者對(duì)WSN中運(yùn)用MCDS理論構(gòu)造虛擬骨干網(wǎng)進(jìn)行了深入的研究，提出了一些求解MCDS的算法，但大多數(shù)算法通常只考慮CDS的規(guī)模，雖然獲得了較小規(guī)模的CDS，但因?yàn)闆]有考慮剩余能量，以致低剩余能量的節(jié)點(diǎn)被選為支配點(diǎn)后過早因能量耗盡而死亡，使得網(wǎng)絡(luò)能量消耗不均衡。雖然也有部分算法考慮了能量問題，但都沒能將影響網(wǎng)絡(luò)生命周期的各種因素綜合起來進(jìn)行全面衡量，能量利用率仍然不高。

1.1 支配集定義

通常情況下，用一個(gè)簡(jiǎn)單無向圖G=(V，E)來表示W(wǎng)SN的監(jiān)測(cè)區(qū)域，其中:V為所有節(jié)點(diǎn)的集合，每個(gè)節(jié)點(diǎn)代表一個(gè)傳感器；E為所有邊的集合，每條邊表示兩個(gè)傳感器相互在對(duì)方的無線通信范圍內(nèi)。簡(jiǎn)單無向圖G=(V，E)的一個(gè)非空節(jié)點(diǎn)子集D，若對(duì)?v∈V－D，D中都至少存在一個(gè)節(jié)點(diǎn)u與之相鄰，則稱D為圖G的一個(gè)支配集。如果由D導(dǎo)出的子圖是連通圖，則稱D為連通支配集。圖G中含節(jié)點(diǎn)數(shù)最少的連通支配集稱為最小連通支配集。

1.2 符號(hào)說明

算法EB-MCDS運(yùn)行過程中，節(jié)點(diǎn)的狀態(tài)、顏色和鄰節(jié)點(diǎn)集合等都會(huì)發(fā)生變化，為方便后續(xù)算法的描述，現(xiàn)給出相關(guān)的基本定義。以節(jié)點(diǎn)u為例，定義如下:

S0:初始狀態(tài)節(jié)點(diǎn)，標(biāo)記為白色；

S1:被支配狀態(tài)節(jié)點(diǎn)，標(biāo)記為灰色；

S2:支配狀態(tài)節(jié)點(diǎn)，標(biāo)記為黑色；

N1(u):節(jié)點(diǎn)u的一跳開放鄰節(jié)點(diǎn)集合；

N1［u］:節(jié)點(diǎn) u 的一跳鄰節(jié)點(diǎn)閉集合，N1［u］=N1(u)∪u；

N2(u):距節(jié)點(diǎn)u二跳的鄰節(jié)點(diǎn)集合；

d(u)=|N1(u)|:節(jié)點(diǎn)u的一跳開放鄰節(jié)點(diǎn)數(shù)；

L1(u):存儲(chǔ)節(jié)點(diǎn)u一跳鄰接白色節(jié)點(diǎn)信息的列表；

L2(u):存儲(chǔ)節(jié)點(diǎn)u二跳鄰接白色節(jié)點(diǎn)信息的列表。

2 EB-MCDS算法

2.1 算法主要思想

算法采用分布式，開始時(shí)所有節(jié)點(diǎn)均為初始狀態(tài)，當(dāng)一個(gè)發(fā)起節(jié)點(diǎn)確定為支配點(diǎn)后，主要工作就是如何選取下一支配點(diǎn)，然后收斂整個(gè)網(wǎng)絡(luò)。本文下一支配點(diǎn)的選取策略是支配點(diǎn)通過發(fā)送消息收集其2跳范圍內(nèi)所有初始狀態(tài)節(jié)點(diǎn)的信息后，首先將2跳范圍內(nèi)權(quán)值最大的初始狀態(tài)節(jié)點(diǎn)置為支配點(diǎn)，然后將1跳范圍內(nèi)與新置支配點(diǎn)相鄰的權(quán)值最大的節(jié)點(diǎn)置為支配點(diǎn)，新置的支配點(diǎn)將其1跳鄰接初始狀態(tài)節(jié)點(diǎn)置為被支配點(diǎn)，一直到整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)全部置為支配點(diǎn)或被支配點(diǎn)時(shí)結(jié)束，所有支配點(diǎn)構(gòu)成連通支配集。

2.2 節(jié)點(diǎn)權(quán)值公式的構(gòu)造

基于MCDS理論構(gòu)造的虛擬骨干網(wǎng)絡(luò)中，由于支配點(diǎn)需要長(zhǎng)期處于工作狀態(tài)，而被支配點(diǎn)可以周期性的進(jìn)入睡眠，支配點(diǎn)的能耗和消息吞吐量遠(yuǎn)遠(yuǎn)大于被支配點(diǎn)。因而在構(gòu)造MCDS時(shí)選取質(zhì)量較優(yōu)的節(jié)點(diǎn)充當(dāng)支配點(diǎn)至關(guān)重要。

①節(jié)點(diǎn)度:選取具有最大度的節(jié)點(diǎn)充當(dāng)支配點(diǎn)，可以獲得更小的CDS，這樣就可以減少非支配點(diǎn)之間冗余的無線通信鏈路，大大減少路由表的規(guī)模和通信開銷，可以有效緩解廣播風(fēng)暴。但支配點(diǎn)往往比非支配點(diǎn)承擔(dān)更多消息處理和轉(zhuǎn)發(fā)任務(wù)，因此支配過多節(jié)點(diǎn)時(shí)，該支配點(diǎn)的消息廣播能力會(huì)降低，這將影響整個(gè)網(wǎng)絡(luò)的消息吞吐率。綜合以上因素，設(shè)置一個(gè)N為支配點(diǎn)可以支配其它被支配點(diǎn)的理想值。

②剩余能量:在WSN中，節(jié)點(diǎn)通常采用電池供電，一旦能量耗盡，短期內(nèi)將難以獲得補(bǔ)充。為了延長(zhǎng)網(wǎng)絡(luò)生命周期，不出現(xiàn)因節(jié)點(diǎn)能量過早耗盡后死亡而導(dǎo)致的網(wǎng)絡(luò)分割和MCDS的頻繁重構(gòu)，我們應(yīng)盡量選取剩余能量較多的節(jié)點(diǎn)充當(dāng)支配點(diǎn)。

③能量閾值:在由MCDS構(gòu)造的虛擬骨干網(wǎng)中，支配點(diǎn)需要長(zhǎng)期處于工作狀態(tài)，不斷地與非支配點(diǎn)和支配點(diǎn)之間進(jìn)行數(shù)據(jù)、指令等轉(zhuǎn)發(fā)，它的耗能速度較快，而非支配點(diǎn)可能間歇性的關(guān)閉通信設(shè)備來減少能量消耗，并且它們只需要和所屬的支配點(diǎn)通信，這樣就大大地節(jié)約了能量。所以本文設(shè)置了一個(gè)能量閾值，一方面在選取支配點(diǎn)時(shí)，盡量選取能量大于閾值的節(jié)點(diǎn)，另一方面當(dāng)支配點(diǎn)能量低于閾值時(shí)，即表示它已不再適合充當(dāng)支配點(diǎn)，主動(dòng)退出支配集成為被支配點(diǎn)，這就避免了支配點(diǎn)因能量耗盡而死亡。

節(jié)點(diǎn)權(quán)值公式如下:

其中d(u)為節(jié)點(diǎn)u的度；N是一個(gè)支配點(diǎn)可以支配其它被支配點(diǎn)的理想數(shù)量，其取值與網(wǎng)絡(luò)密度和通信距離有關(guān)，通常取網(wǎng)絡(luò)平均節(jié)點(diǎn)度；δ是恒大于零的常數(shù)；Eu是節(jié)點(diǎn)剩余能量；Ethr是節(jié)點(diǎn)剩余能量閾值；α和β為常數(shù)，且α+β=1，如果α較大，那么節(jié)點(diǎn)度在權(quán)值中所占比重更大，傾向于構(gòu)造支配點(diǎn)的度與N接近的CDS，如果β較大，則剩余能量在權(quán)值中所占比重較大，傾向于構(gòu)造剩余能量較均衡的CDS；γ是恒大于零的常數(shù)，當(dāng)剩余能量一旦小于閾值時(shí)，權(quán)值將迅速減小，選擇該節(jié)點(diǎn)的可能性就很小。W(u)值越大表示優(yōu)先級(jí)越高。

2.3 算法描述

初始化所有節(jié)點(diǎn)為白色，設(shè)從節(jié)點(diǎn)u開始，步驟如下:

(1)從N1［u］中選擇權(quán)值最大(量大權(quán)值節(jié)點(diǎn)有多個(gè)時(shí)選Id值最大者，下同)的節(jié)點(diǎn)v，將v著為黑色，并廣播Dominator消息宣布自己為支配點(diǎn)。

(2)收到Dominator消息的白色節(jié)點(diǎn)將自己著為灰色，同時(shí)廣播Dominatee消息，宣布自己為被支配點(diǎn)；

(3)收到Dominatee消息的白色節(jié)點(diǎn)廣播含自己Id和權(quán)值的Packet消息；

(4)灰色節(jié)點(diǎn)將收到的Packet消息存儲(chǔ)于信息列表L1并廣播；

(5)支配點(diǎn)v將接收到的各鄰接灰色節(jié)點(diǎn)發(fā)送的信息列表L1存入其信息列表L2，然后將L2中權(quán)值最大的白色節(jié)點(diǎn)m著為黑色，接著在v的N1(v)中選擇與m相鄰且權(quán)值最大的灰色節(jié)點(diǎn)n著為黑色，著為黑色的節(jié)點(diǎn)廣播Dominator消息宣布自己為支配點(diǎn)；

(6)網(wǎng)絡(luò)中相關(guān)節(jié)點(diǎn)重復(fù)步驟2～5，直到網(wǎng)絡(luò)中沒有白色節(jié)點(diǎn)。

CDS構(gòu)造結(jié)束后，虛擬骨干網(wǎng)運(yùn)行的過程中，如果支配點(diǎn)的剩余能量低于能量閾值，則主動(dòng)退為被支配點(diǎn)。當(dāng)支配點(diǎn)退為被支配點(diǎn)后，由其支配的被支配點(diǎn)就全部置為初始狀態(tài)，然后廣播含自己Id和權(quán)值的Packet消息，網(wǎng)絡(luò)中相關(guān)節(jié)點(diǎn)調(diào)用EB-MCDS算法將初始狀態(tài)節(jié)點(diǎn)置為支配點(diǎn)或被支配點(diǎn)。

2.4 圖例

圖1 EB-MCDS算法構(gòu)造連通支配集實(shí)例

以圖1為例說明EB-MCDS算法的執(zhí)行過程，由于各節(jié)點(diǎn)的權(quán)值在不同時(shí)刻具有不同的值，為了方便說明，各節(jié)點(diǎn)的編號(hào)視為其此時(shí)刻的權(quán)值。假設(shè)從14號(hào)節(jié)點(diǎn)開始，由于其1跳鄰節(jié)點(diǎn)中沒有權(quán)值比它大的節(jié)點(diǎn)，故最先置為支配點(diǎn)，如圖1(a)所示；根據(jù)算法步驟(2)，將1、2、3、4、5、6 號(hào)節(jié)點(diǎn)著為灰色，如圖1(b)所示；根據(jù)算法步驟(3)～(5)，節(jié)點(diǎn)13、6置為支配點(diǎn)，如圖1(c)、(d)所示；然后支配點(diǎn)6重復(fù)執(zhí)行算法，節(jié)點(diǎn)11、12置為支配點(diǎn)，如圖(e)、(f)所示。網(wǎng)絡(luò)中所有節(jié)點(diǎn)置為支配點(diǎn)或被支配點(diǎn)后，得到的 MCDS 為{14、13、6、11、12}。

2.5 算法性能分析

定理在圖G=(V，E)中，通過執(zhí)行EB-MCDS算法所獲得的黑色節(jié)點(diǎn)集為連通支配集。

證明由算法EB-MCDS的執(zhí)行過程可知，所有節(jié)點(diǎn)最終的顏色為黑色或灰色，白色節(jié)點(diǎn)在收到Dominator消息后將自己著為灰色，而只有黑色節(jié)點(diǎn)可以發(fā)送Dominator消息，所以灰色節(jié)點(diǎn)至少與一個(gè)黑色節(jié)點(diǎn)相鄰，即黑色節(jié)點(diǎn)集是一個(gè)支配集。又由算法第5步可知，每一個(gè)黑色節(jié)點(diǎn)的加入，均與之前已獲得的黑色節(jié)點(diǎn)集連通，所以黑色節(jié)點(diǎn)集還是一個(gè)連通支配集。

初始狀態(tài)節(jié)點(diǎn)收到Dominatee消息時(shí)，發(fā)送一條Packet消息，其消息復(fù)雜度為O(1)；初始狀態(tài)節(jié)點(diǎn)收到Dominator消息時(shí)，先發(fā)送一條Dominatee消息，然后向發(fā)送Dominator消息的支配點(diǎn)發(fā)送包含其一跳鄰節(jié)點(diǎn)信息列表L1的消息，其消息復(fù)雜度為O(Δ)，Δ為節(jié)點(diǎn)的最大度數(shù)；一個(gè)節(jié)點(diǎn)當(dāng)被確定為支配點(diǎn)時(shí)，它會(huì)發(fā)送一條Dominator消息，待收集完所有一跳鄰節(jié)點(diǎn)發(fā)送的包含L1的消息后，會(huì)從L2中選出兩個(gè)支配點(diǎn)，其時(shí)間復(fù)雜度為O(Δ2)，消息復(fù)雜度為O(Δ)。綜上所述，EB-MCDS算法的時(shí)間復(fù)雜度為O(Δ2)，消息復(fù)雜度為O(nΔ)。

3 模擬仿真與結(jié)果分析

為了驗(yàn)證本文EB-MCDS算法的性能，我們將與沒有考慮剩余能量的HMCDS［9］算法和考慮了剩余能量的EB-CDS［12］算法進(jìn)行比較。評(píng)估它們各自在CDS收斂時(shí)間、CDS規(guī)模、高權(quán)值節(jié)點(diǎn)所占比例和網(wǎng)絡(luò)生命周期等方面的性能。

本文以O(shè)MNET++3.3平臺(tái)進(jìn)行模擬仿真實(shí)驗(yàn)，實(shí)驗(yàn)所用的參數(shù)如表1所示。

測(cè)試在150 m×100 m的網(wǎng)絡(luò)區(qū)域內(nèi)進(jìn)行，隨機(jī)投放一定數(shù)量的傳感器節(jié)點(diǎn)，假定所有節(jié)點(diǎn)都是同質(zhì)的，具有相同的通信半徑R和初始能量，任何兩個(gè)節(jié)點(diǎn)間能夠通信當(dāng)且僅當(dāng)它們都在對(duì)方的通信范圍內(nèi)。實(shí)驗(yàn)時(shí)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)隨機(jī)產(chǎn)生的拓?fù)鋱D必須是連通圖(非連通圖無法構(gòu)造CDS)。通信半徑R固定為25 m，節(jié)點(diǎn)數(shù)由40個(gè)增加到100個(gè)，每次遞增10個(gè)；對(duì)各種組合都隨機(jī)生成50個(gè)拓?fù)洌瑢?duì)每個(gè)拓?fù)浞謩e執(zhí)行HMCDS算法、EB-CDS算法和本文算法，待構(gòu)造完CDS后，隨機(jī)挑選節(jié)點(diǎn)以1 kbit/s的速度發(fā)送消息，并通過CDS進(jìn)行廣播。最后計(jì)算每一個(gè)拓?fù)涞腃DS收斂時(shí)間、CDS大小、高權(quán)值節(jié)點(diǎn)所占比例和網(wǎng)絡(luò)生命周期，最后對(duì)結(jié)果進(jìn)行歸一化處理，即構(gòu)造CDS的時(shí)間、支配集與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比例、高權(quán)值節(jié)點(diǎn)與支配集的比例和算法開始運(yùn)行至網(wǎng)絡(luò)中無法構(gòu)造CDS為止的時(shí)間，作為每個(gè)算法的性能評(píng)價(jià)指標(biāo)。顯然，算法收斂時(shí)間越短，構(gòu)造的CDS越小，高權(quán)值節(jié)點(diǎn)占支配集比例越高，網(wǎng)絡(luò)生命周期越長(zhǎng)，性能越好。實(shí)驗(yàn)結(jié)果如圖2所示。

表1 實(shí)驗(yàn)參數(shù)取值

由圖2(a)可以看出，三種算法的CDS收斂時(shí)間都隨網(wǎng)絡(luò)規(guī)模的增大而延長(zhǎng)，在節(jié)點(diǎn)數(shù)目比較少的時(shí)候，三種算法的收斂時(shí)間相差不大，但隨著節(jié)點(diǎn)達(dá)到80個(gè)以后，EB-MCDS的優(yōu)勢(shì)比較明顯，這是因?yàn)镋B-CDS算法的判斷規(guī)則較復(fù)雜，而HMCDS算法花費(fèi)了較多時(shí)間來構(gòu)建leader-election生成樹。

由圖2(b)可以看出，三種算法的CDS所占比例都隨網(wǎng)絡(luò)規(guī)模的增大而減小。其中EB-MCDS算法和HMCDS算法非常接近，且HMCDS算法略優(yōu)于EB-MCDS算法，這是因?yàn)橐环矫鍴MCDS算法在初始化時(shí)構(gòu)建了一棵leader-election生成樹，獲得了較優(yōu)的從屬關(guān)系，另一方面HMCDS算法只考慮了節(jié)點(diǎn)的度，因而構(gòu)造的CDS會(huì)小一些。而EB-CDS算法的支配集選取規(guī)則易選出較多的冗余支配點(diǎn)，故CDS所占比例較高。

圖2 算法運(yùn)行結(jié)果比較

由圖2(c)可以看出，由于本文算法優(yōu)先選擇剩余能量較多、節(jié)點(diǎn)度與理想支配節(jié)點(diǎn)數(shù)接近的的節(jié)點(diǎn)作為支配點(diǎn)，并通過能量閾值降低了能量較低的節(jié)點(diǎn)充當(dāng)支配點(diǎn)的機(jī)率，所以高權(quán)值支配點(diǎn)在支配集中所占的比例一直保持較高，并隨著節(jié)點(diǎn)數(shù)增加而不斷提高；HMCDS算法中，由于支配點(diǎn)的選取只考慮節(jié)點(diǎn)的度而不考慮節(jié)點(diǎn)的剩余能量，使得部分剩余能量較少的節(jié)點(diǎn)被選為支配點(diǎn)，雖然高權(quán)值節(jié)點(diǎn)所占比例仍然隨著節(jié)點(diǎn)數(shù)增加而提高，但一直處于60% ～80%之間；EB-CDS算法中，支配點(diǎn)的選取引入了平均剩余能量的權(quán)值公式，即剩余能量與節(jié)點(diǎn)度的比值，比值越大，優(yōu)先級(jí)越高，這在一定程度上提高了高權(quán)值節(jié)點(diǎn)的比例，但從圖中可以看出，隨著節(jié)點(diǎn)數(shù)的增多，高權(quán)值節(jié)點(diǎn)顯著增加，這是因?yàn)楫?dāng)網(wǎng)絡(luò)節(jié)點(diǎn)較稀疏時(shí)，部分度很小的節(jié)點(diǎn)反而獲得了較大的優(yōu)先級(jí)，使得高權(quán)值節(jié)點(diǎn)比例仍然不高，并且該算法雖然設(shè)置了能量閾值，但只在支配集維護(hù)算法中使用，故在支配集構(gòu)造時(shí)仍有部分能量較低的節(jié)點(diǎn)加入，一定程度上也降低了高權(quán)值節(jié)點(diǎn)所占的比例。

由圖2(d)可以看出，綜合了剩余能量的EBMCDS算法和EB-CDS算法要比沒有考慮剩余能量的HMCDS算法具有更持久的壽命，網(wǎng)絡(luò)生命周期提高了近20%。然而EB-CDS算法在節(jié)點(diǎn)規(guī)模較小時(shí)優(yōu)勢(shì)并不明顯，這是因?yàn)镋B-CDS之所以能延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的重要思路是引入了候選支配點(diǎn)為支配點(diǎn)分流的思想，而網(wǎng)絡(luò)節(jié)點(diǎn)較少時(shí)，可選的侯選支配點(diǎn)更少，即難以實(shí)現(xiàn)為支配點(diǎn)分流，隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加，其可選的侯選支配點(diǎn)也就隨之增加，能夠很好的實(shí)現(xiàn)能量均衡。本文EB-MCDS算法的網(wǎng)絡(luò)生命周期一直保持較長(zhǎng)，這是因?yàn)榫W(wǎng)絡(luò)生命周期是以最先死亡的割點(diǎn)(屬于支配集)為標(biāo)準(zhǔn)的，正是考慮了這一點(diǎn)，本文算法不僅在支配集維護(hù)中采用了剩余能量低于能量閾值的支配點(diǎn)主動(dòng)退出支配集的策略，而且在支配集構(gòu)造時(shí)就盡量降低了低于能量閾值的節(jié)點(diǎn)選取為支配點(diǎn)的機(jī)率，即從一開始就考慮了權(quán)值最大化，最大限度地均衡了網(wǎng)絡(luò)能量消耗，從而有效延長(zhǎng)了網(wǎng)絡(luò)生命周期。

為了更好的說明高權(quán)值節(jié)點(diǎn)所占比例與網(wǎng)絡(luò)生命周期的關(guān)系，將仿真實(shí)驗(yàn)中節(jié)點(diǎn)通信半徑為25 m，節(jié)點(diǎn)數(shù)目為100個(gè)時(shí)，本文EB-MCDS算法運(yùn)行于隨機(jī)生成的50個(gè)拓?fù)鋱D的結(jié)果在進(jìn)行歸一化處理前制作了一張散點(diǎn)圖，如圖2(e)所示，由圖中可以看出，高權(quán)值節(jié)點(diǎn)所占比例與網(wǎng)絡(luò)生命周期是成正比的，隨著高權(quán)值節(jié)點(diǎn)所占比例的提高，網(wǎng)絡(luò)生命周期也相應(yīng)的得到延長(zhǎng)，這也就是說選取質(zhì)量較優(yōu)的節(jié)點(diǎn)充當(dāng)支配點(diǎn)可以有效的延長(zhǎng)網(wǎng)絡(luò)生命周期。

從實(shí)驗(yàn)結(jié)果可以看出，本文所提算法考慮了均衡使用網(wǎng)絡(luò)能量后，網(wǎng)絡(luò)生命周期得到顯著提高。這就告訴我們，在能量受限的WSN中，在追求構(gòu)造更小規(guī)模CDS的同時(shí)，也應(yīng)該考慮網(wǎng)絡(luò)能量消耗均衡，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。

4 總結(jié)

本文采用了一個(gè)簡(jiǎn)單高效的連通支配集分布式構(gòu)造算法，在算法中考慮了能量閾值和理想支配節(jié)點(diǎn)數(shù)限制，剩余能量大于閾值且被支配節(jié)點(diǎn)數(shù)與理想支配節(jié)點(diǎn)數(shù)相近的節(jié)點(diǎn)被優(yōu)先考慮作為支配點(diǎn)，使得傳感器網(wǎng)絡(luò)能量消耗均衡，支配節(jié)點(diǎn)消息吞吐率提高，有效地延長(zhǎng)了網(wǎng)絡(luò)的生存周期和提高了廣播效率。

［1］Kassaei H，Mehrandish M，Narayanan L，et al.Efficient Algorithms for Connected Dominating Sets in Ad Hoc Networks［C］//Proceedings of Proceedings 2010 IEEE Wireless Communications and Networking Conference(WCNC).2010.Sydney，Australia IEEE.1－6.

［2］Kim D，Zhang Z，Li X Y，et al.A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs［J］.IEEE Transactions on Mobile Computing，2010，9(8):1108 －1118.

［3］Yin B，Shi H，Shang Y.An Efficient Algorithm for Constructing a Connected Dominating Set in Mobile Ad Hoc Networks［J］.Journal of Parallel and Distributed Computing，2011，71(1):27－39.

［4］Zou F，Wang Y，Xu X H，et al.New Approximations for Minimum-Weighted Dominating Sets and Minimum-Weighted Connected Dominating Sets on Unit Disk Graphs［J］.Theoretical Computer Science，2011，412(3):198－208.

［5］Guha S，Khuller S.Approximation Algorithms for Connected Dominating Sets［J］.Algorithmica，1998，20(4):374－387.

［6］高文宇.無線傳感器網(wǎng)絡(luò)中的連通支配集求解算法［J］.微計(jì)算機(jī)信息(測(cè)控自動(dòng)化)，2010，26(1):47－49.

［7］Wu J.Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links［J］.IEEE Trans.on Parallel and Distributed Systems，2002，13(9):866－881.

［8］Alzoubi K M，Wan P J，F(xiàn)reider O.Distributed Heuristics for Connected Dominating Set in Wireless Ad Hoc Networks［J］.IEEE ComSoc/KICS Journal on Communication Networks，2002，4(1):22－29.

［9］陳勤，范文濤，張旻.分布式最小連通支配集啟發(fā)式算法［J］.計(jì)算機(jī)工程，2009，35(10):92－94.

［10］閻新芳，孫雨耕，胡東華.基于極大權(quán)的最小連通支配集啟發(fā)式算法［J］.電子學(xué)報(bào)，2004，32(11):1774－1777.

［11］張靜，孫雨耕，房朝暉.能量有效的最小連通支配集近似算法［J］.傳感技術(shù)學(xué)報(bào)，2004，12(4):603－610.

［12］付永生，李善平，周波.無線傳感網(wǎng)絡(luò)中能量均衡的連通支配集算法［J］.傳感技術(shù)學(xué)報(bào)，2010，23(8):1142－1145.

［13］孫超，尹榮榮，郝曉辰，等.WSNs中基于能量代價(jià)最小權(quán)和支配集拓?fù)淇刂扑惴ǎ跩］.電子與信息學(xué)報(bào)，2010，32(4):857－863.