能量均衡的最小連通支配集分布式算法*

凌 飛，吳振華

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

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

有關MCDS的構造算法，目前主要分為兩類:集中式算法［5－6］和分布式算法［7－13］。集中式算法要求把整個網絡的拓撲信息集中到某個中心節點，而這將需要花費極大的通信代價和出現局部節點通信量過大的問題，因而不適用于WSN，但獲得的連通支配集(Connected Dominating Set，CDS)通常比分布式的小，這是因為集中式算法擁有整個網絡的拓撲信息。文獻［5］提出了一種集中式算法，其主要思想是把最大度的節點作為根節點開始構建一棵樹，樹包含圖中所有節點，樹的葉子節點為非支配點，非葉子節點為支配點。該算法時間復雜度高。文獻［6］在文獻［5］的基礎上證明了MCDS是圖的一棵包含最多葉子節點的生成樹的非葉子節點集合，根據這個結論設計了一種新的構造MCDS的算法。分布式算法只需要知道當前節點的局部信息，各個節點獨立地計算自己的連接情況，具有較強的自組織能力。根據構造CDS的連通性又可以分為基于鄰節點信息［7］和基于極大獨立集(Maximum Independent Set，MIS)［8－9］兩類。基于鄰節點信息的算法是利用節點N跳(通常為1－2跳)內的拓撲信息啟發式構造CDS；而基于MIS的算法是先構建一個MIS，然后再添加一些網關節點將MIS連通，進而構成CDS。文獻［7］提出了一種簡單的構造CDS的分布式近似算法，其思想是任一節點當它有兩個鄰居節點不相鄰時它為支配點。該方法的缺點是有較多的冗余支配點且在網絡拓撲經常變化時運算過于復雜。文獻［8］提出了一種運用leader-election算法生成一棵樹來構造一個MIS，然后在它的基礎上添加部分網關節點來構造CDS的算法，文獻［9］在文獻［8］的基礎上進行了改進，在構造MIS的同時通過添加MIS中各節點的父節點為支配點來構造CDS。

上述算法均沒有考慮節點能量對網絡性能的影響，網絡能量利用不均衡。為了構造高效的MCDS，文獻［10］提出了一種基于極大權的MCDS分布式算法，文獻［11］利用修剪規則盡量保留權值大的節點充當支配點，但該算法沒有考慮節點的能量限制問題，文獻［12］引入了候選支配點，一方面可以為某個時段能量消耗過快的支配點分流，另一方面可以替代因剩余能量低于一個閾值的支配點工作，但該算法的CDS偏大。

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

1 問題描述

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

1.1 支配集定義

通常情況下，用一個簡單無向圖G=(V，E)來表示WSN的監測區域，其中:V為所有節點的集合，每個節點代表一個傳感器；E為所有邊的集合，每條邊表示兩個傳感器相互在對方的無線通信范圍內。簡單無向圖G=(V，E)的一個非空節點子集D，若對?v∈V－D，D中都至少存在一個節點u與之相鄰，則稱D為圖G的一個支配集。如果由D導出的子圖是連通圖，則稱D為連通支配集。圖G中含節點數最少的連通支配集稱為最小連通支配集。

1.2 符號說明

算法EB-MCDS運行過程中，節點的狀態、顏色和鄰節點集合等都會發生變化，為方便后續算法的描述，現給出相關的基本定義。以節點u為例，定義如下:

S0:初始狀態節點，標記為白色；

S1:被支配狀態節點，標記為灰色；

S2:支配狀態節點，標記為黑色；

N1(u):節點u的一跳開放鄰節點集合；

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

N2(u):距節點u二跳的鄰節點集合；

d(u)=|N1(u)|:節點u的一跳開放鄰節點數；

L1(u):存儲節點u一跳鄰接白色節點信息的列表；

L2(u):存儲節點u二跳鄰接白色節點信息的列表。

2 EB-MCDS算法

2.1 算法主要思想

算法采用分布式，開始時所有節點均為初始狀態，當一個發起節點確定為支配點后，主要工作就是如何選取下一支配點，然后收斂整個網絡。本文下一支配點的選取策略是支配點通過發送消息收集其2跳范圍內所有初始狀態節點的信息后，首先將2跳范圍內權值最大的初始狀態節點置為支配點，然后將1跳范圍內與新置支配點相鄰的權值最大的節點置為支配點，新置的支配點將其1跳鄰接初始狀態節點置為被支配點，一直到整個網絡節點全部置為支配點或被支配點時結束，所有支配點構成連通支配集。

2.2 節點權值公式的構造

基于MCDS理論構造的虛擬骨干網絡中，由于支配點需要長期處于工作狀態，而被支配點可以周期性的進入睡眠，支配點的能耗和消息吞吐量遠遠大于被支配點。因而在構造MCDS時選取質量較優的節點充當支配點至關重要。

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

②剩余能量:在WSN中，節點通常采用電池供電，一旦能量耗盡，短期內將難以獲得補充。為了延長網絡生命周期，不出現因節點能量過早耗盡后死亡而導致的網絡分割和MCDS的頻繁重構，我們應盡量選取剩余能量較多的節點充當支配點。

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

節點權值公式如下:

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

2.3 算法描述

初始化所有節點為白色，設從節點u開始，步驟如下:

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

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

(3)收到Dominatee消息的白色節點廣播含自己Id和權值的Packet消息；

(4)灰色節點將收到的Packet消息存儲于信息列表L1并廣播；

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

(6)網絡中相關節點重復步驟2～5，直到網絡中沒有白色節點。

CDS構造結束后，虛擬骨干網運行的過程中，如果支配點的剩余能量低于能量閾值，則主動退為被支配點。當支配點退為被支配點后，由其支配的被支配點就全部置為初始狀態，然后廣播含自己Id和權值的Packet消息，網絡中相關節點調用EB-MCDS算法將初始狀態節點置為支配點或被支配點。

2.4 圖例

圖1 EB-MCDS算法構造連通支配集實例

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

2.5 算法性能分析

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

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

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

3 模擬仿真與結果分析

為了驗證本文EB-MCDS算法的性能，我們將與沒有考慮剩余能量的HMCDS［9］算法和考慮了剩余能量的EB-CDS［12］算法進行比較。評估它們各自在CDS收斂時間、CDS規模、高權值節點所占比例和網絡生命周期等方面的性能。

本文以OMNET++3.3平臺進行模擬仿真實驗，實驗所用的參數如表1所示。

測試在150 m×100 m的網絡區域內進行，隨機投放一定數量的傳感器節點，假定所有節點都是同質的，具有相同的通信半徑R和初始能量，任何兩個節點間能夠通信當且僅當它們都在對方的通信范圍內。實驗時網絡內節點隨機產生的拓撲圖必須是連通圖(非連通圖無法構造CDS)。通信半徑R固定為25 m，節點數由40個增加到100個，每次遞增10個；對各種組合都隨機生成50個拓撲，對每個拓撲分別執行HMCDS算法、EB-CDS算法和本文算法，待構造完CDS后，隨機挑選節點以1 kbit/s的速度發送消息，并通過CDS進行廣播。最后計算每一個拓撲的CDS收斂時間、CDS大小、高權值節點所占比例和網絡生命周期，最后對結果進行歸一化處理，即構造CDS的時間、支配集與網絡節點數的比例、高權值節點與支配集的比例和算法開始運行至網絡中無法構造CDS為止的時間，作為每個算法的性能評價指標。顯然，算法收斂時間越短，構造的CDS越小，高權值節點占支配集比例越高，網絡生命周期越長，性能越好。實驗結果如圖2所示。

表1 實驗參數取值

由圖2(a)可以看出，三種算法的CDS收斂時間都隨網絡規模的增大而延長，在節點數目比較少的時候，三種算法的收斂時間相差不大，但隨著節點達到80個以后，EB-MCDS的優勢比較明顯，這是因為EB-CDS算法的判斷規則較復雜，而HMCDS算法花費了較多時間來構建leader-election生成樹。

由圖2(b)可以看出，三種算法的CDS所占比例都隨網絡規模的增大而減小。其中EB-MCDS算法和HMCDS算法非常接近，且HMCDS算法略優于EB-MCDS算法，這是因為一方面HMCDS算法在初始化時構建了一棵leader-election生成樹，獲得了較優的從屬關系，另一方面HMCDS算法只考慮了節點的度，因而構造的CDS會小一些。而EB-CDS算法的支配集選取規則易選出較多的冗余支配點，故CDS所占比例較高。

圖2 算法運行結果比較

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

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

為了更好的說明高權值節點所占比例與網絡生命周期的關系，將仿真實驗中節點通信半徑為25 m，節點數目為100個時，本文EB-MCDS算法運行于隨機生成的50個拓撲圖的結果在進行歸一化處理前制作了一張散點圖，如圖2(e)所示，由圖中可以看出，高權值節點所占比例與網絡生命周期是成正比的，隨著高權值節點所占比例的提高，網絡生命周期也相應的得到延長，這也就是說選取質量較優的節點充當支配點可以有效的延長網絡生命周期。

從實驗結果可以看出，本文所提算法考慮了均衡使用網絡能量后，網絡生命周期得到顯著提高。這就告訴我們，在能量受限的WSN中，在追求構造更小規模CDS的同時，也應該考慮網絡能量消耗均衡，從而延長網絡生命周期。

4 總結

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

［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］高文宇.無線傳感器網絡中的連通支配集求解算法［J］.微計算機信息(測控自動化)，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，Freider 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］陳勤，范文濤，張旻.分布式最小連通支配集啟發式算法［J］.計算機工程，2009，35(10):92－94.

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

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

［12］付永生，李善平，周波.無線傳感網絡中能量均衡的連通支配集算法［J］.傳感技術學報，2010，23(8):1142－1145.

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