基于分享度的最小連通支配集求解算法

趙學鋒，陳祥恩

(西北師范大學 a. 計算機科學與工程學院；b. 數學與統計學院，蘭州 730070)

1 概述

支配集問題在無線網絡設計、社交網絡和Web 圖中有許多應用和研究[1-2]。無線傳感器網絡(Wireless Sensor Network,WSN)中節點往往隨機散落在區域中，具有相同的通信半徑，常用單位圓盤圖(Unit Disk Graph,UDG)作為研究網絡的基本模型，所關注的問題如構建虛擬骨干網、網絡分簇和拓撲控制等都與UDG 的連通支配集(Connected Dominating Set,CDS)有關。在UDG 類拓撲結構上構造最小連通支配集(Minimum Connected Dominating Set,MCDS)是NP 難題，而出于無線網絡中節點計算能力和能量消耗等因素的考慮，MCDS 算法應具有分布式、局部化的特性。文獻[1]提出鄰居指定的局部化算法，從節點的多點中繼集合中選定幾個支配節點，這類算法得到的CDS 規模較大。在基于支配樹的MCDS 算法中，較常見的是2 階段構造方式，即首先構造極大獨立集，然后另外選擇一些連接點共同組成CDS[3-4]，文獻[4]給出了這類算法的近似比為7.6。文獻[5]將2 階段合為一個階段，在與上一輪選出的支配點相距2-跳的節點中選出新的支配點，并由與新舊支配點相距1-跳的節點連接，生成網絡的支配樹。文獻[6]在廣度優先搜索樹上構造分層的支配集，然后通過相鄰層的中間節點將不連通的支配點連接為一個支配樹，除了CDS 的大小外，還提出了以支配樹的平均跳數距離(Average Hop Distance,AHD)作為新的評價準則，AHD 小，則網絡通信的平均代價小且更可靠。在構造支配樹時，需要確定節點權值和支配點的連接方式，最簡單的權值是節點標識[3]，但對CDS不是本質的[1]，更多的研究以節點度數為主要指標[5-6]，文獻[7]將節點局部轉發因子作為選擇支配點的優先級。文獻[8]計算的CDS 規模較小，但該文設計的是集中式算法，而面對無線傳感器網絡和大數據的復雜網絡，利用局部信息求解問題成為新的要求[9]，集中式算法不能適應這一要求。另外，對MCDS 的研究還延伸到一些新的問題，如文獻[10]要求網絡節點要被多個節點所支配，文獻[11]將分享度(Share Degree,SD)作為量化指標選舉網絡的覆蓋集。以上述內容為基礎，本文提出一種基于分享度的最小連通支配集求解算法。

2 符號與概念

設N(u)={v|v∈V,(u,v)∈E}是節點u∈V 的鄰接點集合；u 的度d(u)=|N(u)|；T 表示SD 算法構造的支配樹；VT為T的節點集；u.prev 是u∈VT的父節點；h (u,v)表示網絡G 中u,v∈V 之間最短通信鏈路的跳數，最大的h (u,v)稱為網絡直徑；hT(u,v)是T 中節點u、節點v 之間唯一通信鏈路的跳數。特別地，當u 為T 的根節點時，將h(u,v)和hT(u,v)分別記為h (v)和hT(v)；G 的AHD 的計算公式為：∑h (u,v)/n(n-1)，T 的AHD 為：∑hT((u,v)/|VT|(|VT|-1)，∑分別是對各自圖中的所有點對求和。

定義1(UDG)n 個點隨機均勻分布在區域[0,R]2上，2 點鄰接?其歐氏距離不超過r。當R=1 時，UDG 存在臨界半徑rc，滿足πnrc2=lnn 且對r≥rc，UDG 幾乎是連通的。

定義2(SD)設節點v∈N(u)，即v 是u 的d(u)個鄰居中的一個成員，則v 對u 的分享度為1/d(u)。現將N(u)中度數相同的節點歸為一類，設|{v|v∈N(u)∧d(v)=i}|=ki，稱ki/i 為u 關于度數i 的分享度。

稱fu(x)=k1x+k2x2+…+kn-1xn-1為u 的度分布，顯然fu(1)=d(u)。

稱gu(x)=k1x+k2x2/2+…+kn-1xn-1/(n-1)為u 的分享度分布。

設v 的分享度分布為：gv(x)=b1x+b2x2/2+…+bn-1xn-1/(n- 1)。若k1=b1,k1=b2,…,ki-1=bi-1，但ki＞bi，則稱gu(x)＞gv(x)。

若gu(x)＞gv(x)對?v∈{w|w∈N(u)∧s(w)=0}成立，則u為局部剩余SD 最大節點，稱u 是局部分享度占優的。分享度的意義在于，gu(x)越大則鄰居點被支配的比例下降得越快。

節點u 的權值Q(u)=＜gu(x),u＞，Q(u)＞Q(v)?(gu(x)＞gv(x))∨(gu(x)=gv(x)∧u＜v)。

3 基于SD 的MCDS 求解算法

3.1 算法規則與流程

SD 算法的支配樹構造表示一個迭代過程，記Ai為第i 次迭代后V 中所有狀態為4 的節點集合，即Ai={u|u∈V∧s(u)=4}。初始階段，A0={I}，一般情況下，Ai=SD(Ai-1)，i=1,2,…，若迭代進行到Ak=?時結束，則k 為迭代復雜度。算法可形式化地描述為一個4 元組：＜G,SD,s,A0＞，其中，s 為節點狀態變遷，s(u)∈{0,1,2,3,4,5}。初始時只有根節點I 狀態為4，其余節點狀態為0。其中，1(支配點)、2(連接點)和5(退化點)為穩定狀態；s(u)=3 表明u 是支配點的子節點；若沒有轉到狀態2，迭代結束后維持3 狀態不變；s(u)=4，是3 狀態節點的子節點，是一個臨時狀態。算法的迭代運行將當前4 狀態節點的狀態轉為{1,3,5}中的一種。對節點w∈Ai，狀態變遷為4→1，表明w 在局部分享度占優；狀態變遷為4→5，即w 的局部分享度為0；狀態變遷為4→3，表明在w 的鄰居N(w)∩Ai中新產生了1 態點u，則令w.prev=u，而N(w)中的0 態點隨后轉為新的4 態點，完成一次迭代。算法結束時狀態為1、2 的節點組成CDS。節點的狀態變遷如圖1 所示，邊上的數字表示接收的消息種類。

圖1 節點狀態變遷

基于分享度構造支配樹的算法描述如下：

3.2 算法分析

在執行While 的迭代過程中依次產生的4 狀態節點集合為A0,A1,…,Ak，現設相應的1 狀態節點集合為D0,D1,…,Dk，顯然Di是Ai(1≤i≤k)的子集且A0=D0={I}，而D=D1∪D2∪…∪Dk={u|u∈V∧s(u)=1}為支配點集；C={u|u∈V∧s(u)=2}為連接點集。

定理1 SD 算法得到的是網絡的支配樹。

證明 迭代結束時Ak=?意味著G 中已無4 態點，也不存在0 態點，網絡節點的狀態為{1,2,3,5}，進入穩定狀態。設第次i 迭代完成時1、2 狀態節點組成了一個樹，設u∈Di+1，由步驟9、步驟10，u 將選擇Di與Di+1之間的一個3 態節點v 為唯一的父節點，并使s(v)=2，由于網絡中的每個3 態點都是1 態點的子節點，因此存在唯一的w∈Di，使w 為v 的父節點，因此，u 通過v 與w 連接，形成一個隨迭代次數增長的樹。若以根節點I 為0 層，則算法結束時形成一個偶層為1 態點，奇層由2 態點組成的交錯支配樹T。T 的節點集VT=D∪C 為G 中MCDS 的近似解，T 的邊集ET={(u,v)|u,v∈VT∧(u=v.prev)}。

引理1 設G 是n 個節點的UDG，r2=arc2，參數a＞1 調節網絡連通性和節點密度。記△為G 中節點的最大度數，則對常數δ≥6，以1-(1/n3a)的概率，使△≤δalnn。

證明 用D(u,r)表示以u∈V 為中心r 為半徑的圓盤，則N(u)中的節點都分布在D(u,r)中，按照UDG 模型，G 中節點分布在區域[0,R]2中，當u 接近區域邊界時，D(u,r)不會完全包含在[0,R]2中，相交部分的面積為Area{D(u,r)∩[0,R]2}＜Area{D(u,r)}=πr2。為方便分析，令D(u,r0)是另一個圓盤，滿足：r0＞r 且Area{D(u,r0)∩[0,R]2}=πr2，設D(u,r0)∩[0,R]2中的節點數為μ，其期望值為E[μ]=(n-1)×πr2/R2=(n-1)×alnn/n=alnn-O(1)，于是：

其中，第3 個≤依據的是文獻[12]的定理4.4。

網絡中節點的期望度數為alnn，引理1 說明G 中節點度數超出alnn 較大倍數幾乎是不可能的，因此，在下面的分析中將G 中節點度數看作alnn。

定理2 SD 算法的時間復雜度為O(nlnn)。

證明 控制算法運行時間關鍵步驟是支配點的選舉。?u∈D，需要收集鄰居點v∈A∩N(u)的Q(v)=＜gv(x),v＞，并與自己的權值Q(u)=＜gu(x),v＞比較，因此，在u 上選舉的時間代價最多為O((lnn)2)，從而算法的執行時間為O(|D|(lnn)2)。由于V 隨機分布在[0,R]2中，G 的支配集大小由[0,R]2中所能填充的半徑為r/2 的圓盤數量決定，即|D|≤1/(π(r/2)2)≤4n/lnn，因此|D|(lnn)2≤4nlnn，即結論成立。

引理2 ?u∈Di,?v∈Di-1,1≤i≤k，成立h(u)≥h(v)+1。

引理3 ?u,v∈Di,1≤i≤k，成立hT(u)=hT(v)。

定理3 ?u∈Di,1≤i≤k，成立hT(u)≤2h(u)。

證明 依歸納法證明。當i=1 時，hT(u)=h(u)=2，符合；假設結論對i(≥2)成立，考慮i+1 的情況。?u∈Di+1，如果u.prev∈Ai-Di，則u.prev 的狀態變遷為0→4→3，則?v∈Di為u.prev 的更新后唯一的父節點，這時hT(u)=hT(v)+2，按照歸納假設，hT(v)≤2h(v)，所以，hT(u)≤2h(v)+2=2(h(v)+1)=2h(u)；如果u.prev 的狀態變遷為0→3，此時，hT(u)=hT(v)+2≤2h(v)+2=2h(u)-2＜2h(u)。這表明T 中從根節點I 開始的每條路徑長度不超過網絡直徑的2 倍。

4 實驗結果與分析

本文算法用Java 語言實現。為驗證其有效性，在UDG上進行了實驗，并與文獻[6]的CDS-BD-C2 算法進行比較，以文獻[8]集中式算法——BCOP 算法作為MCDS 測試基準。每個實驗數據都是在隨機產生的100 個連通網絡拓撲圖上運行結果的均值。2 組實驗數據如下：

(1)節點數n 從300 開始以增量100 變化至900，區域邊長R=500 m，通信半徑r=50 m，CDS 中的點數隨網絡節點數的變化如圖2 所示，平均跳數距離隨節點數的變化如圖3 所示。隨著節點數的變化，本文算法的計算結果總是保持較優。

圖2 CDS 中的點數隨網絡節點數的變化

(2)節點數n=1000，R=100 m，半徑r 以5 為步長從10 m 增加至40 m，隨著r 的增大，網絡密度逐漸增加。CDS中的點數隨網絡通信半徑的變化如圖4 所示，平均跳數距離(Average Hop Distance,AHD)隨網絡通信半徑的變化如圖5 所示，在較為稀疏的網絡中，本文算法有明顯的優勢。

圖4 CDS 中的點數隨網絡通信半徑的變化

圖5 平均跳數距離隨網絡通信半徑的變化

上述實驗結果中的G-AHD 表示圖G 的AHD，是任何支配樹的AHD 下界，在此作為算法比較的參照。綜合2 組實驗的數據進行對比分析可見，在不同的網絡參數下，無論是CDS 的大小還是支配樹的平均跳數距離，這2 個性能指標上本文算法都對CDS-BD-C2 算法有所改進，構造的支配樹的平均跳數距離平均減少12%，得到的CDS 更接近BCOP 算法。

5 結束語

本文提出一種基于分享度求解最小連通支配集的SD 算法。從根節點開始迭代交替選擇支配點和連接點，支配點的選取主要依賴于1-跳鄰居中0 狀態節點分享度的比較。連接點將本次生成的支配點和上次產生距根節點近的支配點連通起來，使得所有選擇出的具有局部分享度占優的節點恰好是連通的。算法具有分布式特點，由1 個階段完成構造，避免了2 次構造的通信開銷。在UDG 模型上分析了時間復雜度和支配樹的特性。實驗結果表明，和現有構造支配樹的分布式相比，該算法得到的CDS 點數較少，支配樹的平均跳數也比近期具有代表性的CDS-BD-C2 算法計算得到的值小，便于實際應用。研究新的節點權值和連接方式，以網絡局部信息改進MCDS 算法的性能是今后的研究重點。

[1]Wu Jie,Lou Wei,Dai Fei. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[J]. IEEE Transactions on Computers,2006,55(3): 334-347.

[2]Cooper C,Klasing R,Zito M. Lower Bounds and Algorithms for Dominating Sets in Web Graphs[J]. Internet Mathematics,2005,2(2): 275-300.

[3]Wan Pengjun,Alzoubi K M,Frieder O. Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks[J]. Mobile Networks and Applications,2004,9(2):141-149.

[4]Wu Weili,Du Hongwei,Jia Xiaohua,et al. Minimum Connected Dominating Sets and Maximal Independent Sets in Unit Disk Graphs[J]. Theoretical Computer Science,2006,352(1-3): 1-7.

[5]Funke S,Kesselman A,Meyer U. A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs[J].ACM Transactions on Sensor Networks,2006,2(3): 444-453.

[6]Kim D,Wu Yiwei,Li Yingshu,et al. Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J]. IEEE Transactions on Parallel and Distributed System,2009,20(2): 147-157.

[7]解文斌,李 佳,鮮 明,等. 基于拓撲特性的分布式虛擬骨干網算法[J]. 軟件學報,2010,21(6): 1416-1425.

[8]Butenko S,Cheng Xiuzhen,Oliveira C,et al. A New Heuristics for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks[C]//Proc. of Recent Developments in Cooperative Control and Optimization. New York,USA:Kluwer Academic Publisher,2004.

[9]Borgs C,Brautbar M,Chayes J,et al. The Power of Local Information in Social Networks[C]//Proc. of the 8th International Conference on Internet and Network Economics.Berlin,Germany: Springer,2012.

[10] Wang Feng,Du Hongwei,Camacho E,et al. On Positive Influence Dominating Sets in Social Networks[J]. Theoretical Computer Science,2011,412(3): 265-269.

[11] Li Shaohua,Wang Jianxin,Chen Jianer,et al. An Algorithm for Minimum Vertex Cover Based on Max-I Share Degree[J].Journal of Computers,2011,6(8): 1781-1788.

[12] Mitzenmacher M,Upfal E. Probability and Computing:Randomized Algorithms and Probabilistic Analysis[M].Cambridge,UK: Cambridge University Press,2005.